Ієрархічні та неієрархічні процедури кластерного аналізу
Иерархические дивизимные (делимые) методы (DIvisive ANAlysis, DIANA) Эти методы являются логической противоположностью агломеративным методам. В начале работы алгоритма все объекты принадлежат одному кластеру, который на последующих шагах делится на меньшие кластеры, в результате образуется последовательность расщепляющих групп. Иерархические алгоритмы связаны с построением дендрограмм… Читати ще >
Ієрархічні та неієрархічні процедури кластерного аналізу (реферат, курсова, диплом, контрольна)
Методы кластерного анализа можно разделить на две группы:
- — иерархические;
- — неиерархические [5, с.166].
Каждая из групп включает множество подходов и алгоритмов.
Рис. 2.1 Методы кластерного анализа
Используя различные методы кластерного анализа, аналитик может получить различные решения для одних и тех же данных. Это считается нормальным явлением.
Рассмотрим иерархические и неиерархические методы подробно.
Иерархические методы кластерного анализа
Из всех методов кластерного анализа, указанных ранее, самыми распространенными являются иерархические агломеративные методы Суть иерархической кластеризации состоит в последовательном объединении меньших кластеров в большие или разделении больших кластеров на меньшие.
Иерархические агломеративные методы (Agglomerative Nesting, AGNES) Эта группа методов характеризуется последовательным объединением исходных элементов и соответствующим уменьшением числа кластеров.
В начале работы алгоритма все объекты являются отдельными кластерами. На первом шаге наиболее похожие объекты объединяются в кластер. На последующих шагах объединение продолжается до тех пор, пока все объекты не будут составлять один кластер.
Иерархические дивизимные (делимые) методы (DIvisive ANAlysis, DIANA) Эти методы являются логической противоположностью агломеративным методам. В начале работы алгоритма все объекты принадлежат одному кластеру, который на последующих шагах делится на меньшие кластеры, в результате образуется последовательность расщепляющих групп.
Принцип работы описанных выше групп методов в виде дендрограммы показан на рис. 2.2.
Программная реализация алгоритмов кластерного анализа широко представлена в различных инструментах Data Mining, которые позволяют решать задачи достаточно большой размерности. Например, агломеративные методы реализованы в пакете SPSS, дивизимные методы — в пакете Statgraf.
Иерархические методы кластеризации различаются правилами построения кластеров. В качестве правил выступают критерии, которые используются при решении вопроса о «схожести» объектов при их объединении в группу (агломеративные методы) либо разделения на группы (дивизимные методы).
Иерархические методы кластерного анализа используются при небольших объемах наборов данных.
Преимуществом иерархических методов кластеризации является их наглядность.
Иерархические алгоритмы связаны с построением дендрограмм (от греческого dendron — «дерево»), которые являются результатом иерархического кластерного анализа. Дендрограмма описывает близость отдельных точек и кластеров друг к другу, представляет в графическом виде последовательность объединения (разделения) кластеров.
Дендрограмма (dendrogram) — древовидная диаграмма, содержащая n уровней, каждый из которых соответствует одному из шагов процесса последовательного укрупнения кластеров [6, с.115].
Дендрограмму также называют древовидной схемой, деревом объединения кластеров, деревом иерархической структуры.
Дендрограмма представляет собой вложенную группировку объектов, которая изменяется на различных уровнях иерархии.
Существует много способов построения дендрограмм. В дендрограмме объекты могут располагаться вертикально или горизонтально. Пример вертикальной дендрограммы приведен на рис. 2.3.
Числа 11, 10, 3 и т. д. соответствуют номерам объектов или наблюдений исходной выборки. Мы видим, что на первом шаге каждое наблюдение представляет один кластер (вертикальная линия), на втором шаге наблюдаем объединение таких наблюдений: 11 и 10; 3, 4 и 5; 8 и 9; 2 и 6. На втором шаге продолжается объединение в кластеры: наблюдения 11, 10, 3, 4, 5 и 7, 8,9. Данный процесс продолжается до тех пор, пока все наблюдения не объединятся в один кластер.