Ким_ Мьюллер и др - Факторный_ дискриминантный и кластерный анализы (1185345), страница 41
Текст из файла (страница 41)
Наконец, для понимания иерархических агломеративных методов не нужны обширные знания, Так, метод одиночной связи не требует понимания матричной алгебры или обширной подготовки по многомерной статистике. Вместо этого дается правило, укаэываюшее, каким образом, исходя из матрицы сходства, объектымогут объединяться в кластеры. Хотя другие иерархические агломеративные методы несколько сложнее, все они довольно просты и различаются правилами объединения объектов (которые в литературе часто мазываются видами связи объектов).
По определению в результате работы этих кластерных методов получаются неперекрывающиеся кластеры, которые, однако, являются вложенными в том смысле, что каждый кластер может рассматриваться как элемент другого, более широкого кластера на более высоком уровне сходства. Самым распространенным способом представления результатов этих кластерных методов является дендрограмма (древновидная диаграмма), которая графически изображает иерархическую структуру, порожденную матрицей сходства и правилом объединения объектов в кластеры.
Несмотря на простоту методов, они обладают некоторыми недостатками. Если не используются специально разработанные алгоритмы, то применение иерархических алгомеративных методов может потребовать вычисления и хранения большой матрицы сходства. Необходимость в хранении такой матрицы фактически ограничивает сверху число объектов, участвующих в процессе кластеризации. Например, для набора данных из 500 объектов потре- 1аа буются хранение и неоднократный просмотр матрицы, содержащей около 125000 элементов. Другим недостатком кластерных методов является то, что в них объекты распределяются по кластерам лишь за один проход, а поэтому плохое начальное разбиение м~ножества данных не может быть изменено на последующих шагах процесса кластеризации (Пожег, 1967).
Третий недостаток всех этих методов (за исключением метода одиночной связи) состоит в том, что они могут порождать разные решения в результате простого переупорядочения объектов в матрице сходства и, кроме того, их результаты изменяются, если некоторые объекты исключаются из рассмотрения. Устойчивость — это важное свойство любой классификации, так как устойчивые группы с большим правдоподобием представляют собой «естественные» группировки по сравнению с теми группами, которые исчезают, если некоторые объекты переупорядочены или исключены из анализа. Вопрос об устойчивости становится особенно .существенным, когда мы имеем дело с малыми выборками объектов ()агб(пе апб В(Ьзоп, 1071).
Иерархические агломеративные методы различаются главным образом по правилам построения кластеров. Некоторые авторы для обозначения способа группировки используют термин «стратегия классификации». Существует много различных правил группировки, каждое нз которых порождает специфический иерархический метод. Известно по крайней мере двенадцать различных методов группировки, четыре из них наиболее распространенные: одиночной связи, полной связи, средней связи и метод Уорда. Ланс и Уильямс (1967) получили формулу, которая позволяет описать правила группировки в общем виде для любого иерархического агломеративного метода. Формула имеет вид г( (Ь й) = А (1) . д (61) +А (1) г1 Щ) + В ° Ц ~1) + + С .АВЯ (г((й,() — д(6,1) ), где и'(й, й) — различие (расстояние) между кластерами и и й, причем кластер й является результатом объединения кластеров (или объектов) 1 и 1' в ходе агломеративного шага, С помощью этой формулы можно вычислить расстояние между некоторым объектом (й) и новым кластером (й), полученным объединением объектов 1 и 1 в единый кластер.
Прописными буквами обозначены параметры, которые определяют конкретный вид группировки; в методе одиночной связи, например, этн параметры принимают следующие значения: А(1)=А(1) =1/2, В=О и С=1/2. Получен~ная формула оказала большую помощь при разработке вычислительных алгоритмов для этих методов. Чтобы проиллюстрировать работу иерархических методов и показать действие разных правил группировки, данные ММР1- теста были обработаны с помощью четырех наиболее известных методов. Метод одиночной связи. В этом методе, описанном Спитом (1957), кластер образуется по следующему правилу: объект будет 169 присоединен к уже существующему кластеру, если по крайней мере один из элементов кластера находится ма том же уровне сходства, что и объект, претендующий на включение.
Таким образом, присоединение определяется лишь наличием единственной связи между объектом и кластером. Главное преимущество этого метода заключается в его математических свойствам; результаты, полученные по этому методу, инвариантны к монотонным преобразованиям матрицы сходства; применению метода не мешает наличие «совпадений» в данных (Лагб)пе апд Бйззоп, 1971). Первое нз этих свойств (инвариантность при монотонных преобразованиям) особенно важно по той причивте, что все другие иерархические агломеративные методы таким свойством не обладают.
Это означает, что метод одиночной связи является одним из немногих методов, результаты применения которых не изменяются при любых преобразованиях данных, оставляющих без изменения относительное упорядочет не элементов матрицы сходства. 458 222 412 035 365 644 319 652 22З 46О 2222 69 161 027 134 Взв ЗВ 694 42 503 Рнс.
4 Дендротрамма метода одиночной связи дия данных ММР1-теста 170 3947 698- 3535 945 3\24 189 271г 494 2390 679 1888 924 1477.169 1065 414 Б53 669 г41995 -~ Рнс 5. Дендрограмма метода полных свяаей для данных ММР1-теста Главный недостаток метода одиночной связи, однако, состоит в том, что, как было показано на практике, метод приводит к появлению «цепочек» («цепной эффект»), т. е.
к образованию больших продолговатых кластеров. Эффект образования цепочек можно показать на примере древовидной диаграммы для данных ММР1-теста (рис. 4). Обратите внимание, что по мере приближения к окончанию процесса кластеризации образуется один большой кластер, а все остающиеся объекты добавляются к нему один за другим. Найденное с помощью метода одиночной связи решение, состоящее из двух кластеров, является тривиальным следствием наличия одного кластера, включающего 89 объектов, и одного кластера, включающего один объект. На рис. 4 можно отметить еще несколько интересных моментов. Во-первых, анализ рисунка не дает возможности определить, 171 как много кластеров содержится в данных.
В противоположяость этому древовидная диаграмма, полученная методом полной связи (см. рис. 5), четко указывает на наличие двух кластеров. Во-вто~рых, диагностируемые классы больных, тесно связанные с профилями данных ММР1-теста, не образуют четко выделенных кластеров на рисунке.
В левой части дерева имеется скопление профилей больных с невротическими заболеваниями (Н), а в середине дерева скопление профилей больных с расстройствами личности (РЛ). Оставшаяся часть дерева состоит из профилей больных психозами (П), неврозами (Н) и нескольких профилей РЛ.
Короче говоря, решение, порожденное методом одиночной связи, не является точным воспроизведением известной структуры данных. Метод полных связей. В этом методе в противоположностьметоду одиночной связи правило объединения указывает, что сходство между кандидатами на включение в существующий кластер и любым из элементов этого кластера не должно быть меньше некоторого порогового уровня (Ьока1 апб М1с)тепег, 1958). Настоящее правило более жесткое, чем правило для метода одиночной связи, и поэтому здесь имеется тенденция к обнаружению относительно компактных гиперсферических кластеров, образованных объектами с большим сходством.
Хотя дерево, порожденное методом полных связей (рис. 5), дает наглядное представление о найденных кластерах данных, все же сравнение полученной классификации с известной не говорит о хорошем их соответствии. Приведенная ниже информация показывает распределение объектов по кластерам и диагностическим классам. Точное решение давало бы взаимооднозначное соответствие между кластерами и диагностическими классами.
Однако в решении, полученном по методу полных связей, оно явно отсутствует. Как распределены объекты по классам и кластерам, показано в таблице: кластеры 1 И !!1 П 10 0 20 лкатасаы тт РЛ 8 4 18 Метод средней связи. Предложенный Сокэлом и Миченером (1958) метод средней связи разрабатывался в качестве «средства борьбы» с крайностями как метода одиночной связи, так н метода полной связи. Хотя есть несколько вариантов метода, по существу, в каждом из них вычисляется среднее сходство рассматриваемого объекта со всеми объектами в уже существующем кластере, а затем, если ~найденное среднее значение сходства достигает илн превосходит некоторый заданный пороговый уровень сходства, объект присоединяется к этому кластеру.
Чаще всего используется вариант метода средней связи, в котором вычисляется среднее арифметическое сходство между объектами кластера и кандидатом на включение. В других вариантах метода средней связи вычисляется сходство между центрами тяжести двух кластеров, подлежащих объединению. Метод средней связи широко использовался в био- 7205 475 7087 000 956 528 832 051 707 576 583 702 458 627 334 753 209 678 85 НМ Рнс 6 Дендрограмма метода средней свяан для данных ММР!-теста логии, н только недавно ~начал по-настоящему применяться в социальных науках Анализ рис. 6 дает интересное соотношение между деревом, порожденным методом средней связи, и известными диагностическими классами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
