Дюран Б._ Оделл П. - Кластерный анализ (1977) (1185343), страница 5
Текст из файла (страница 5)
Мера Джеффриса — Матуситы применялась в приложениях дискриминантного анализа к сельскохозяйственным данным для классификации полей 11691. В большинстве работ, указанных в табл. 1.3, рассматриваются одномерные виды мер расстояния. Эти меры обсуждаются в работе Уоккера и Лангриба 13831; там же предлагается их обобщение на многомерный случай. Для более полного ознакомления с мерами, представленными в табл. 1.3, отсылаем читателя к работе 13831., $.6. Кластерные методы, основанные ка евклидовой метрике Основные усилия в развитии методов кластеризации и классификации были направлены на построение мето-' дов, основанных на минимизации внутригрупповых сумм квадратов (отклонений). Они могут быть выражены в терминах евклидовых расстояний и называются методами минимальной дисперсии 13961.
В этом параграфе мы рассмотрим различные методы иластеризации. Кроме Ф о Ь й". ! Е 1 Й СФ + С3. Ф.. ! а !! !! о Я Ф ! Р 8' М е~ Й! а3 жй „а ~ И ч О о $ Ы Ф Й О и о 1 ~ф И '~й ы н Т О в того, мы увидим, что многие приемы кластеризации могут быть охвачены одним алгоритмом посредством общего соотношения, содержащего меры расстояния ды. Рассмотрим матрицу наблюденийХ= (ХьХм...,Х„). Квадрат евклидова расстояния между Х~ и Х; определяется по формуле 4- (Х,-хз) т(Х;-Х,). Сейчас мы рассмотрим различные кластерные методы, основанные на этой мере расстояния. Наше описание методов весьма кратко и за деталями отсылаем читателей к соответствующим источникам. Соренсен [3381 описывает так называемый метод полных связей (сотр1е1е 11пйаде). Суть этого метода заключается в том, что два объекта, принадлежащих одной и той же группе (кластеру), имеют коэффициент сходства, который меньше некоторого порогового значения з.
В терминах евклидова расстояния Н это означает, что расстояние между двумя точками (объектами) кластера не должно превышать некоторого порогового значения г. В этом случае г определяет максимально допустимый диаметр подмножества, образующего кластер. МакНотон-Смит [2341 предлагает последовательную процедуру, которую назвал методом максимального локального расстояния (см. определение 1.9); этот метод имеет много общего с предыдущим.
Каждый индивид ~ ~(объект) рассматривается как одноточечный кластер. ' Объекты группируются последовательно по следующему правилу: два кластера объединяются, если максималь' ное расстояние между точками одного кластера и точками другого минимально. Процедура состоит из п — 1 , шагов и результатом являются разбиения, которые сов, падают со всевозможными разбиениями в методе Соренсена для любых пороговых значений. Ворд [3871 в качестве целевой функции применяет внутригрупповую сумму квадратов (ВСК) отклонений, которая есть не что иное, как сумма квадратов расстояний между каждой точкой (объектом) и средней по кластеру, содержащему этот объект. Его метод также представляет собой последовательную процедуру„на каждом шаге объединяются такие два кластера, которые приводят к минимальному увеличению целевой функции, т.
е. ВСК. При объединении кластеров 1(п, элементов) и ! (п» элементов) это увеличение, какследует из параграфа 1.5, равно: Ȅ— — (Х вЂ” У) т(Х вЂ” У), ]]]ч-]]] где Х и У обозначают векторы средних по кластерам 1 и 1. Метод Ворда направлен на объединение близко расположенных кластеров. Сокал н Миченер [334) описывают процедуру, которую .назвали ценгроидным методом. Расстояние между двумя кластерами 1 и 1 в этом методе определяется как евклидово расстояние между центрами (средними) этих кластеров, т. е.
как 0~» = (Х вЂ” У)т(Х вЂ” У). Кластеризация осуществляется поэтапно (223!: на каждом из и — 1 шагов объединяют два кластера 1 и 1, имеющие мини. мальное значение Н~~ . Если а] много больше лъ то центры 1Ц1 и 1 близки друг к другу и характеристики 1] при объединении кластеров практически игнорируются. Это наталкивает на мысль назвать этот метод методом «взвешенных групп».— Другой метод, предложенный Сокалом н Миченером (334), называется двухгруплоаым н опирается на связь между объектом ! н кластером 1. Эта связь выражается в виде среднего коэффициента сходства между объек.
том ! и всеми объектами, входящими в кластер 1. Для того чтобы средний коэффициент сходства выразить через евклидово расстояние, обозначим векторы, входящие в кластер 1, соответственно через Х], Хь..., Х„], а через Х вЂ” центр кластера 1. Тогда среднее расстояние 1]]] между объектом ! ~1 и всеми объектами нз 1 будет равно: Ф 1 ] Ры= — ~, (Х; — У) (Х; — У) ]ен где У обозначает вектор, соответствующий !]й1. Далее »] 1) ы = х«"' (Х] — Х+ Х вЂ” У) т (Х' — Х+ Х вЂ” У) ]]] ]=1 »- Е(Х]Х)т(Х]Х)+(ХУ)т(ХУ)(1!1) ]]] 1 31 Первое слагаемое правой части уравнения обозначим 8» и назовем внутригрупповай дисперсией объектов из 1; второе слагаемое представляет собой квадрат расстояния между объектом» и центром кластера 1.
Процедура последовательной кластеризации заключается в том, что объект»(ЙХ, для которого Ры минимально, присоединяется к кластеру 1. Из (1.11) легко видеть, что если два кластера имеют сравнимые дисперсии, то среднее расстояние Р»» минимизирует расстояние между объектом» и центром кластера 1. Для кластеров с различными. дисперсиями объединение происходит в первую очередь с кластером меньшей дисперсии. Ланс и Уильямс [2251 обобшают двухгрупповой метод и определяют среднее сходство между двумя кластерами 1 и 1 как среднее сходство между всеми парами объектов из 1 и Х. Этот метод они назвали методом групповь»х средних. Кластеры строятся последовательно; два кластера с минимальным средним коэффициен'том' сходства объединяются.
Для того чтобы среднее сходство выразить в терминах евклидова расстояния, обозначим через Х и У соответственно средние кластеров 1 и Х. Средний квадрат расстояний между объектами кластеров 1 и Х, обозначенный через Р~з~ , будет ра. вен я~ я а 1 Р, = ~ 2 (Х» У!)т(Х, У») и~л г»»» ~~ (у! У)т(у. У)+ »=» ю=» т +'(у — Х,) т(у — Х») — ч (у у) т( у у) +' ~ !» 1 '+= У. (У вЂ” Х,)т(У вЂ” Х»).
и» »» Первое слагаемое правой части выражения есть внутри- групповая дисперсия кластера Х, а второе слагаемое— средний квадрат расстояний между Х» и У, »=1, 2,..., пь Таким образом, второе слагаемое может быть переписано как 2 ! «~ 5, +( (Х, У) = — У; (Х,-Х) г(Х,-Х) +. лс 1=3 ,+ Я-Х) г(у — Х), откуда (! .12) О„=5, +5,+( (Х, У), т. е. минимизация среднего сходства эквивалентна минимизации (1.12). Боннер [331 описывает метод, в котором объект, служащий начальной точкой, выбирается случайно.
Все объекты, лежащие на расстоянии от начальной точки не больше г, принимаются за первый кластер. Из оставшихся точек снова случайным образом выбирается объект и процесс повторяется, как и предшествовавший. В результате все точки будут разбиты на группы. Хиверинен !1711 рассматривает процедуру, аналогичную Боннеру, но в качестве начального объекта кластеризации выбйрает не случайную, а так называемую «типическую» точку.
Для определения «типнческих» точек он пользуется статистикой потери информации, причем эти точки лежат на минимальном расстоянии от центра оставшегося множества объектов. В процедуре Болла и Холла !181 первоначальные К кластеров формируются случайным отбором К точек, к которым затем присоединяется каждая нз оставшихся а — К точек — по минимальному расстоянию к той или иной из них. Затем находятся центры кластеров и два кластера 1 и Х объединяются, если 0' меньше некоторого порогового значения г.
Наоборот, если внутригрупповая дисперсия кластера 5„' по некоторой переменной х превосходит пороговое значение 5', то кластер разбивается. Таким образом, дисперсии 5Р кластеров, получающихся в резупьтате этой процедуры, ограничены: 5т К.р5» где р — число переменных. Вместо центра первоначаль» ного кластера рассматриваются центры новых образо- 3 Заказ 67% вавшихся кластеров и процесс продолжается до тех пор пока не сойдется. Процедура Болла и Холла становится довольно популярной. МакКвин 12З7) предлагает метод, аналогичный ме году Болла и Холла. Случайным образом отбирается й объектов, которые принимаются в качестве центров кластеризации.
Для каждого объекта отыскивается ближайшая точка кластеризации, и если расстояние от выбранного объекта до этой точки не больше заданного уровня г, то объект приписывают к кластеру найденной точки кластеризации. Если это расстояние больше г, то объект образует новый кластер. После этого вычисляются новые центры кластеров. Если расстояние между центрами двух кластеров меньше другого априорно заданного уровня, то соответствующие кластеры объединяют. ся.
Процесс продолжается до сходимости. Метод Себестьена 1315) имеет много общего с предыдущим. Однако по Себестьену объект принадлежит кластеру, если расстояние Й до центра кластера меньше г; если же это расстояние больше Я ()г')г), то этот объект образует новую точку кластеризации. Однако если г(Ы()г, то объект выбывает из рассмотрения до следующей итерации. Дженси 1174) предложил процедуру, сходную с предложенной МакКвином. Однако в методе Дженси случайным образом выбирается й точек не из и рассматриваемых объектов, как в методе МакКвина, а из всего пространства Ег.
В качестве минимизируемой целевой функции берется виутригруццовая сумма квадратов отклонений. Форджи 11141 рассматривает метод, сходный с методом Дженси. Разбиение объектов на кластеры в этом методе близко к разбиению, 'предложенному Дженси. Здесь также пользуются минимизацией внутригрупповой суммы квадратов. Основная причина популярности евклидовой метрики в кластерном анализе заключается скорее всего в том, что она наиболее близка к интуитивному представ- лению о расстоянии, а также, как следует из уравнения (1.7), в том, что она тесно связана с ВСК.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
