Участник:Ruslanlazovskiy/CHAMELEON

1 Свойства и структура алгоритма

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

CHAMELEON – алгоритм иерархической кластеризации графа, то есть процесса разбиения графа на несколько подграфов-кластеров таким образом, что данные внутри одного кластера имеют максимально схожи, а данные в разных кластерах — максимально различны. Особенность алгоритма состоит в учетё им как разницы в характеристиках вершин графа, так и их связей между собой ( ребер графа ), что позволяет произвести точную кластеризацию для графов, не соответствующих некоторой заранее заданной модели.

1.3 Вычислительное ядро алгоритма

В алгоритме 2 основных вычислительных ядра, по одному на каждый этап алгоритма.

На первом этапе алгоритма основная вычислительная нагрузка приходится на итерационный процесс разбиения графа на малые подграфы.

На втором этапе алгоритма вычислительное ядро полностью совпадает с самим этапом, то есть итерационным процессов агломеративной иерархической кластеризации.

1.4 Макроструктура алгоритма

Как уже понятно из предыдущих разделов описания, алгоритм CHAMELEON выполняется в 2 этапа, строго последовательных относительно друг друга. Каждый этап соответствует отдельному алгоритму, который может бысть расссмотрен как макрооперация.

Первый этап работы CHAMELEON – разделение графа для получения набора малых кластеров ( в зависимости от параметров программы — от 1 до 5 % от вершин исходного графа ).

Второй этап работы CHAMELEON – алгомеративная иерархическая кластеризация. Она представляет собой последовательный итеративный процесс. На каждой итерации происходит перебор всех неповторяющихся пар кластеров, имеющихся к началу итерации. Для каждой из этих пар принимается решение об объединении или необъединении её в 1 кластер. Итерационный процесс останавливается, когда на очередной итерации остаётся только 1 кластер либо когда ни одна из имеющихся пар кластеров не удовлетворяет условиям на объединение.