Иерархические методы кластерного анализа

Суть иерархической кластеризации состоит в последовательном объединении меньших кластеров в большие или разделении больших кластеров на меньшие.

 

Иерархические агломеративные методы (Agglomerative Nesting, AGNES)

Эта группа методов характеризуется последовательным объединением исходных элементов и соответствующим уменьшением числа кластеров.

В начале работы алгоритма все объекты являются отдельными клас­терами. На первом шаге наиболее похожие объекты объединяются в кла­стер. На последующих шагах объединение продолжается до тех пор, пока все объекты не будут составлять один кластер.

Иерархические дивизимные (делимые) методы (Divisive ANAIysis, DIANA)

Эти методы являются логической противоположностью агломеративным методам. В начале работы алгоритма все объекты принадлежат од­ному кластеру, который на последующих шагах делится на меньшие клас­теры, в результате образуется последовательность расщепляющих групп.

Принцип работы описанных выше групп методов в виде дендрограммы показан на рис.13.3.

 

Шаг 0 Шаг 1 Шаг 2 Шаг 3 Шаг 4

Агломеративные

методы

 

Дивизимные

методы

Шаг 4 Шаг 3 Шаг 2 Шаг 1 Шаг 0

 

Рис. 13.3. Дендрограмма агломеративных и дивизимных методов

Программная реализация алгоритмов кластерного анализа широко представлена в различных инструментах Data Mining, которые позволяют решать задачи достаточно большой размерности. Например, агломератив­ные методы реализованы в пакете SPSS, дивизимные методы — в пакете Statgraf.

 

Иерархические методы кластеризации различаются правилами по­строения кластеров. В качестве правил выступают критерии, которые используются при решении вопроса о "схожести" объектов при их объе­динении в группу (агломеративные методы) либо разделения на группы (дивизимные методы).

Иерархические методы кластерного анализа используются при не­больших объемах наборов данных.

Преимуществом иерархических методов кластеризации является их наглядность.

Иерархические алгоритмы связаны с построением дендограмм (от греческого dendron — "дерево"), которые являются результатом иерархичес­кого кластерного анализа. Дендрограмма описывает близость отдельных точек и кластеров друг к другу, представляет в графическом виде последо­вательность объединения (разделения) кластеров.