10_Кластерный анализ. 10. 1 Процедура кластерного анализа 10 1 Основные понятия
![]()
|
10.5 Методы кластерного анализаНа сегодняшний день разработано более сотни различных алгоритмов кластеризации. В результате применения различных методов кластеризации могут быть получены неодинаковые результаты: кластеры различной формы, различное количество или состав кластеров. Это нормально и является особенностью работы того или иного алгоритма. Например, возможны кластеры "цепочного" типа, когда кластеры представлены длинными "цепочками", кластеры удлиненной формы и т.д., а некоторые методы могут создавать кластеры произвольной формы. Различные методы могут стремиться создавать кластеры определенных размеров (например, малых или крупных) либо предполагать в наборе данных наличие кластеров различного размера. Некоторые методы кластерного анализа особенно чувствительны к шумам или выбросам, другие - менее. Полученные результаты требуют дальнейшей интерпретации, исследования и изучения свойств и характеристик объектов для возможности точного описания сформированных кластеров. Процесс кластеризации и ее результат зависит от выбранного метода и способа определения меры расстояния. Методы кластерного анализа можно разделить на две группы:
Каждая из этих групп включает множество подходов и алгоритмов. 10.5.1 Иерархические методы кластерного анализаСуть иерархической кластеризации состоит в последовательном объединении меньших кластеров в большие (агломеративные методы) или разделении больших кластеров на меньшие (дивизимные методы). Иерархические агломеративные методы (Agglomerative Nesting, AGNES) характеризуется последовательным объединением исходных элементов и соответствующим уменьшением числа кластеров. В начале работы алгоритма все объекты являются отдельными кластерами. На первом шаге два наиболее похожих объекта объединяются в кластер. На последующих шагах объединение продолжается до тех пор, пока все объекты не будут составлять один кластер. Иерархические дивизимные (делимые) методы (DIvisive ANAlysis, DIANA) являются логической противоположностью агломеративным методам. В начале работы алгоритма все объекты принадлежат одному кластеру, который на последующих шагах делится на меньшие кластеры, в результате образуется последовательность расщепляющих групп. Сущность этих методов при помощи дендрограммы иллюстрирована рис. 10.4. ![]() Рис. 10.4 Дендрограмма агломеративных и дивизимных методов Программная реализация алгоритмов кластерного анализа широко представлена в различных инструментах Data Mining, которые позволяют решать задачи достаточно большой размерности. Например, агломеративные методы реализованы в пакете SPSS, дивизимные методы - в пакете Statgraf. Преимуществом иерархических методов кластеризации является их наглядность. Однако иерархические методы кластерного анализа используются при небольших объемах наборов данных. Иерархические алгоритмы связаны с построением дендрограмм (от греческого dendron - "дерево"), которые являются результатом иерархического кластерного анализа. Дендрограмма описывает близость отдельных точек и кластеров друг к другу, представляет в графическом виде последовательность объединения (разделения) кластеров. Дендрограмма (dendrogram) - древовидная диаграмма, содержащая ![]() Существует много способов построения дендрограмм. В дендрограмме объекты могут располагаться вертикально или горизонтально. Пример горизонтальной дендрограммы приведен на рис. 10.4, вертикальной дендрограммы - на рис. 10.5. ![]() Рис. 10.5. Вертикальная дендрограмма На рис 10.5 на первом шаге каждое наблюдение представляет один кластер (вертикальная линия), на втором шаге наблюдаем объединение таких наблюдений: 11 и 10; 3, 4 и 5; 8 и 9; 2 и 6. На втором шаге продолжается объединение в кластеры: наблюдения 11, 10, 3, 4, 5 и 7, 8, 9. Данный процесс продолжается до тех пор, пока все наблюдения не объединятся в один кластер. Объединение осуществляется с использованием одного из методов, рассмотренных в п.10.4: метод ближнего соседа, метод удаленного соседа, метод Варда, метод попарного среднего, центроидный метод и пр. |