И.С. Енюков, С.Б. Королёва - Факторный дискриминантный и кластерный анализ (1119914), страница 41
Текст из файла (страница 41)
Н!. ОБЗОР МЕТОДОВ КЛАСТЕРНОГО АНАЛИЗА 0 ПРИРОДЕ КЛАСТЕРОВ Главная цель кластерного анализа — нахождение групп схожих объектов в выборке данных. Этн группы удобно называть кластерами. Не существует общепринятого или просто полезного определения термина «кластер», и многие исследователи считают что уже слишком поздно либо вовсе незачем пытаться найти такое определение (Воппег, 1964). Несмотря на отсутствие определения, ясно, что кластеры обладают некоторыми свойствами, наиболее важными из которых являются плотность, дисперсия, размеры, форма и отделимость. Хотя Спит и Сокэл рассматривают эти свойства для случая метрического пространства, очевидно (как они признают), что эти свойства можно логически распростра~нить и на неметрические пространства.
Плотность — это свойство, которое позволяет определить кластер, как скопление точек в пространстве данных, относительно плотное по сравнению с другими областями пространства, содержащими либо мало точек, либо не содержащих их вовсе. Хотя четко определенной меры плотности нет, это понятие очевидно.
Дисперсия характеризует степень рассеяния точек в пространстве относительно центра кластера. Несмотря на то, что между этим свойством и тем, которое используется в теории статистических выводов, есть аналогия, кластеры не всегда представляют многомерные нормальные популяции. Поэтому лучше всего рассматривать дисперсию как характеристику того, насколько близко друг к другу расположены в пространстве точки кластера. Следовательно, кластер можно назвать «плотным», если все точки находятся вблизи его центра тяжести, и «неплотным», если они разбросаны вокруг центра. Свойство кластеров — размеры — тесно связано с дисперсией; если кластер можно идентифицировать, то можно и измерить его «радиус».
Это свойство полезно лишь в том случае, если рассматриваемые кластеры являются гиперсферами (т. е. имеют круглую форму) в многомерном пространстве, описываемом признаками. 165 Форма — это расположение точек в пространстве, Несмотря на то, что обычно кластеры изображают в форме гиперсфер или эллипсоидов, возможны кластеры и другой формы, например удлиненные кластеры.
В последнем случае понятие радиуса или диаметра перестает быть полезным. Вместо этого можно вычислить «связность» точек в кластере — относительную меру расстояния между ~ними. Если же кластеры имеют другие, более причудливые формы (см. Ечег111, 1980), то понятие связности становится менее полезным, а ценность относительных оценок диаметра и плотности, следовательно, уменьшается.
Отделимость характеризует степень перекрытия кластеров и насколько далеко друг от друга они расположены в пространстве. Так, кластеры могут быть относительно близки друг к другу и не иметь четких графинин, или же они могут быть разделены широкими участками пустого пространства. С помощью этих терминов можно описать кластеры любого вида. Согласно Эверитту (1980) кластеры — это «непрерывные области (некоторого) пространства с относительно высокой плотностью точек, отделенные от других таких же областей областями с относительно низкой плотностью точек».
Важность этого определения заключается в том, что оно не сводит понятие кластера к какой-то частной форме до начала анализа данных. Разработанные кластерные методы образуют семь основных семейств: 1) иерархические агломеративные методы; 2) иерархические дивизимные методы; 3) итеративные методы группировки; 4) методы поиска модальных значений плотности; 5) факторные методы; 8) методы сгущений; 7) методы, использующие теорию графов. Эти семейства соответствуют различным подходам к созданию групп, и применение различных методов к одним и тем же дан~ямы может привести к сильно различающимся результатам. В конкретных отраслях науки могут оказаться особенно полезными определенные семейства методов.
Так, иерархические агломеративные методы чаще всего используются в биологии, тогда как факторные аналитические методы большим успехом пользуются в психологии. Когда сталкиваешься с трудной проблемой: «Какой из кластер~ныл методов использовать?», важно помнить, что этот метод должен находиться в согласии с ожидаемым характером классификации, применяемыми признаками и мерой сходства (если она требуется для оценки подобия объектов). Наиболее известными семействами кластерных методов, используемыми в социальных науках, являются иерархические агломеративные, иерархические дивизимные и факторные.
Поэтому каждый из этих трех методов будет рассмотрен более детально на примере двух наборов данных, описанных в разд. 1, Другие, менее известные семейства будут обсуждены более кратко. 166 ИЕРАРХИЧЕСКИЕ АГЛОИЕРАТИВИЬ$Е МЕТОДЫ Из семи семейств кластерных методов наиболее часто в приложениях употребляются иерархические агломеративные методы.
Проанализировав все опубликованные в 1973 г. работы, в которых использовался кластерный анализ, Бг7эшфилд и Олдендерфер (1978Ь) нашли, что в г(з этих статей пРименЯетсЯ какой-либо из иерархических агломеративных методов. Самым легким для ионина~пня из иерархических агломеративных методов является метод одиночной связи. Рассмотрим матрицу сходства размерностью 6Х6, которая была получена в равд.
П спомощью коэффициента Жаккара для данных о захоронениях. Метод одиночной связи начинает процесс кластеризации с поиска двух наиболее похожих объектов в матрице сходства. В этом примере наиболее схожими являются объекты ПЖЭ (подросток, женский пол, элитарный) и ВЖЭ (взрослый, женский пол, элитарный) с уровнем сходства 7=0,750. На следующем шаге к этой группе присоединяется объект ВМЭ, так как его коэффициент сходства с ПЖО равен 0,500.
Дело в том, что по правилу объединения для метода одиночной связи новый кандидат на включение в состав кластера присоединяется к существующей группе в том случае, если он имеет наивысший уровень сходства с каким-либо из членов этой группы, Другими словами, для объединения двух объектов требуется только одна связь между ними. Третий шаг присоединяет объект ПМН к кластеру, содержащему объекты ВЖЭ, ВМЭ и ПЖЭ, потому что он тоже имеет коэффициент сходства с ВМЭ, равный 0,500. Четвертый шаг процесса кластеризации присоединяет объект РМН к группе, образованной объектами ПЖЭ, ВМЭ, ВЖЭ и ПМН с уровнем сходства 7=0,333. 0 225 о гео О ЗЗО О ЗОО О 445 0500 О 555 0 610 О 665 о гго Рис 3 Деидрограмма дли данных о шести за- ХОРОИЕИИЯХ 167 Из этого примера можно вывести четыре важных наблюдения относительно иерархических агломеративных методов, Первое— все эти методы просматривают матрицу сходства размерностью МХУ (где У вЂ” число объектов) и последовательно объединяют наиболее схожие объекты.
Именно поэтому они называются алгомеративными (объединяющими). Второй важный момент, на который стоит обратить внимание, состоит в том, что последовательность объединений кластеров можно представить визуально в виде древовидной диаграммы, часто называемой дендрограммой. Древовидная диаграмма, отражающая применение метода одиночной связи к данным о шести захоронениях, показана на рис. 3. Каждый шаг, на котором объединялась пара объектов, представляется ветвью этого дерева. Заметьте, что дерево изображает иерархическую организацию связей между шестью точками данных. На самом нижнем уровне все шесть точек независимы; ма следующем уровне они объединяются в одну группу и три независимых объекта; наконец, на самом верхнем уровне они все объединяются в одну большую группу.
Третьим важным моментом является то, что для полной кластеризации этими методами на основе матрицы сходства размерностью УХУ требуется ровно М вЂ” 1 шагов. На первом шаге события (объекты) рассматриваются как самостоятельные кластеры. На последнем шаге все события объединяются в одну большую группу. Наконец, для понимания иерархических агломеративных методов не нужны обширные знания, Так, метод одиночной связи не требует понимания матричной алгебры или обширной подготовки по многомерной статистике. Вместо этого дается правило, укаэываюшее, каким образом, исходя из матрицы сходства, объектымогут объединяться в кластеры.
Хотя другие иерархические агломеративные методы несколько сложнее, все они довольно просты и различаются правилами объединения объектов (которые в литературе часто мазываются видами связи объектов). По определению в результате работы этих кластерных методов получаются неперекрывающиеся кластеры, которые, однако, являются вложенными в том смысле, что каждый кластер может рассматриваться как элемент другого, более широкого кластера на более высоком уровне сходства. Самым распространенным способом представления результатов этих кластерных методов является дендрограмма (древновидная диаграмма), которая графически изображает иерархическую структуру, порожденную матрицей сходства и правилом объединения объектов в кластеры.
Несмотря на простоту методов, они обладают некоторыми недостатками. Если не используются специально разработанные алгоритмы, то применение иерархических алгомеративных методов может потребовать вычисления и хранения большой матрицы сходства. Необходимость в хранении такой матрицы фактически ограничивает сверху число объектов, участвующих в процессе кластеризации. Например, для набора данных из 500 объектов потре- 1аа буются хранение и неоднократный просмотр матрицы, содержащей около 125000 элементов. Другим недостатком кластерных методов является то, что в них объекты распределяются по кластерам лишь за один проход, а поэтому плохое начальное разбиение м~ножества данных не может быть изменено на последующих шагах процесса кластеризации (Пожег, 1967). Третий недостаток всех этих методов (за исключением метода одиночной связи) состоит в том, что они могут порождать разные решения в результате простого переупорядочения объектов в матрице сходства и, кроме того, их результаты изменяются, если некоторые объекты исключаются из рассмотрения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
