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

Авторы статьи: Лазовский Р. А. ( разделы 1.1 - 1.4 , 1.7 , 1.8 ), Мустафаев Э. Э. ( разделы 1.5 , 1.6 , 1.9 , 1.10 , 2.2 )

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

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

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

Алгоритм CHAMELEON работает в 3 этапа. На первом этапе исходное множество объектов организуется в граф по принципу k ближайших соседей. На втором этапе этого граф разбивается на достаточно малые подграфы-кластеры. На третьем этапе происходит агломеративная иерархическая кластеризация полученных подграфов в соответствии с одной из выбранных метрик ( возможные метрики будут подробно описаны далее ).

1.2 Математическое описание алгоритма

Исходные данные:

[math]RI_{(C_{i},C_{j})} = \frac{2*|EC_{(C_{i},C_{j})}|}{|EC_{C_{i}}|+|EC_{C_{j}}|}[/math]

[math] RC_{(C_{i},C_{j})}= \frac{S_{EC_{(C_{i},C_{j})}}}{\frac{|C_{i}|}{|C_{i}+C_{j}|}*S_{EC_{(C_{i})}}+\frac{|C_{i}|}{|C_{i}+C_{j}|}*S_{EC_{(C_{j})}}}[/math]

[math]RC_{(C_{i},C_{j})} \geqslant T_{RC}[/math]

Вычисляемые данные:

Формулы метода:

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

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

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

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

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

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

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

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

1.9 Входные и выходные данные алгоритма

Входные данные:

[math]O[/math] - набор из [math]n[/math] векторов длины [math]p[/math].
[math]k[/math] - число, определяющиее количество ближайших соседей, по которым строится первоначальный граф.

Выходные данные:

[math]B[/math] - вектор длины [math]n[/math], значение [math]i[/math]-го элемента указывает на принадлежность соответствующего вектора одному из кластеров.

1.10 Свойства алгоритма

Соотношение последовательной и параллельной сложности:

Вычислительная мощность:

Детерминированность: Важной особенностью описываемого алгоритма является его недетерминированность. Условия завершения как 1-го, так и 2-го этапа позволяют обозначить CHAMELEON как итерационный алгоритм с выходом по точности. При этом детерминированность 2-го этапа алгоритма можно обеспечить указанием вырожденных условий кластеризации ( такая кластеризация, очевидно, не будет иметь практического смысла ), в то время как 1-ый этап является недетерминированным всегда.