Участник:Артем Таран/Графо-ориентированный алгоритм кластеризации CHAMELEON
Содержание
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Данный алгоритм выполняется в два этапа.
На первом этапе CHAMELEON использует алгоритм разделения графа для получения набора относительно малых кластеров. На втором этапе, для объединения кластеров, полученных на первом этапе, в настоящие кластеры, используется иерархическая агломеративная кластеризация. Таким образом, алгоритм, фактически, является гибридным, построенным комбинацией графо-ориентированных и классических иерархических методов. Рассмотрим эти этапы подробнее.
На первом этапе, согласно графо-ориентированному подходу, происходит построение графа на матрице сходства объектов по принципу k ближайших соседей. Две вершины такого графа соединяет ребро, если объект, соответствующий любой из этих вершин попадает в число k наиболее близких объектов для объекта, соответствующего другой вершине из данной пары. На Рисунке 6 изображены: объекты в пространстве – слева, граф по принципу 1-го ближайшего соседа – в середине, граф по принципу 3-х ближайших соседей – справа
