Участник: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]n[/math] векторов длины [math]p[/math], каждый из которых соответствует одному объекту. На основании значений элементов этих векторов строится матрица смежности размера [math]n * n[/math] ( возможно сокращение требуемого объема памяти до [math](n*(n - 1))/ 2[/math] в соответствии с выбранной метрикой.

Первый этап алгоритма: На первом этапе на основании матрицы смежности строится граф [math]G = (V, E)[/math] [math]k[/math] ближайших соседей. Указанный граф не обязательно является связным.

Второй этап алгоритма: Граф [math]G = (V, E)[/math] итеративно разбивается на множество подграфов [math]G_{i} = (V_{i}, E_{i}), i = 1 .. m[/math], где [math] \cup V_{i} = V, i = 1 .. m[/math]. На каждой итерации выбирается [math]G_{b}[/math] с числом вершин, наибольшим среди всех подграфов, имеющихся на данной итерации. Этот граф разбивается на 2 подграфа [math]G_{bi}[/math] и [math]G_{bj}[/math] таких, что 1) [math]min(V_{bi},V_{bj}) \gt = 0.25 * V_{b}[/math] ( имеется ввиду количество вершин ) и 2) [math]\sum{E_{kl}}, E_{kl} = (v_{k}, v_{l}), v_{k} \in V_{bi} , v_{l} \in V_{bj} [/math] минимальна среди всех разбиений, удовлетворяющих 1). Итеративный процесс прекращается, когда [math]\sum{v_{b}} \lt = q * \sum{v} , v_{b} \in V_{b} , e \in E[/math] ( имеется ввиду количество вершин ). Здесь [math]q[/math] - задаваемый параметр, на практике он варьируется от [math]0.01[/math] до [math]0.05[/math]. Полученные подграфы называются малыми кластерами.

Третий этап алгоритма: Множество кластеров [math]G_{i} = (V_{i}, E_{i}), i = 1 .. m[/math] итеративно преобразуется в множество кластеров [math]G_{j} = (V_{j}, E_{j}), j = 1 .. l[/math], [math]l \lt = m[/math]. Для этого вводятся следующие понятия:

[math]EC_{(C_{i},C_{j})}[/math] - абсолютная взаимная связность пары кластеров [math]C_{i}, C{j}[/math]. Это суть сумма весов ребер, соединяющих вершины, принадлежащие [math]C{i}[/math] c вершинами из [math]C{j}[/math]. [math]EC_{(C_{i},C_{i})}[/math] вычисляется как сумма ребер, входящих в разделитель, разбивающий [math]C{i}[/math] на два равных подграфа.
[math]S_{EC_{(C_{i},C_{j})}}[/math] - абсолютное взаимное сходство пары кластеров [math]C_{i}, C{j}[/math]. Это суть среднее сходство между соединенными вершинами, принадлежащими [math]C{i}[/math] и [math]C{j}[/math] соответственно. Соединения обусловлены разбиением общего графа, полученного на первом этапе алгоритма.
[math]RI_{(C_{i},C_{j})} = \frac{2*|EC_{(C_{i},C_{j})}|}{|EC_{C_{i}}|+|EC_{C_{j}}|}[/math] - относительная взаимная связность пары кластеров [math]C_{i}, 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]C_{i}, C{j}[/math]

На основании этих показателей осуществляется агломеративная иерерхическая кластеризация. Существует две стратегии их анализа. В первом случае для каждой пары кластеров [math]C{i}, C{j}[/math] проверяется истинность выражений [math]RI_{(C_{i},C_{j})} \gt = T_{RI}[/math] и [math]RC_{(C_{i},C_{j})} \gt = T_{RC}[/math], где [math]T_{RI}, T_{RI}[/math] - заранее заданные пороговые значения. Если для некоторого [math]C_{i}[/math] таких [math]C_{j}[/math] несколько, то конкретная пара определяется по максимуму значения [math]EC_{(C_{i},C_{j})}[/math]. Во втором случае выбираются пары кластеров, максимизирующие функцию вида [math]RI_{(C_{i},C_{j})}*RC_{(C_{i},C_{j})}^\alpha[/math]. Здесь [math]\alpha[/math] - заданный пользователем параметр. В обоих случаях процесс останавливается либо когда на очередной итерации не находится подходящих пар кластеров, либо когда остаётся только один кластер.

Вычисляемые данные: В процессе агломеративной кластеризации для всех объектов, т.е. всех вершин всех кластеров указывается индекс [math]j[/math] кластера, к которому они принадлежат. После завершения алгоритма возможно перенумеровать кластеры. В любом случае на выходе будет иметься [math]n[/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-ый этап является недетерминированным всегда.