Участник:Kirillov\Графо-ориентированный алгоритм кластеризации CHAMELEON

1 ЧАСТЬ. Свойства и структура алгоритмов

1.1 Общее описание алгоритма

Алгоритм CHAMELEON первые представлен в 1999 департаментом компьютерных наук и инженерии, университет Миннесоты, США. Авторы George Karypis, Eui-Hong (Sam) Han, Vipin Kumar. Кластеризация – процесс разбиения множества данных по некоторому признаку на такие группы, что в пределах одной группы данные максимально схожи по данному признаку, а в разных группах данные максимально различны. Иерархические алгоритмы кластеризации строят не одно разбиение множества данных на кластеры, а систему вложенных разбиений. CHAMELEON является агломеративным методом (снизу вверх), когда после первого разбиения на мелкие кластеры пары близлежащих кластеров итеративно объединяются в общий кластер. На первом этапе CHAMELEON использует алгоритм разделения графа для получения набора относительно малых кластеров. На втором этапе, для объединения кластеров, полученных на первом этапе, в настоящие кластеры, используется иерархическая агломеративная кластеризация. Таким образом, алгоритм, фактически, является гибридным, построенным комбинацией графо-ориентированных и классических иерархических методов. На первом этапе, согласно графо-ориентированному подходу, происходит построение графа на матрице сходства объектов по принципу k ближайших соседей. Две вершины такого графа соединяет ребро, если объект, соответствующий любой из этих вершин попадает в число k наиболее близких объектов для объекта, соответствующего другой вершине из данной пары.