Участник: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 Вычислительное ядро алгоритма

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

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

На втором этапе наибольшее время занимает поиск подходящего разбиения очередного подграфа. В элементарном варианте этой процедуры необходимо перебрать все комбинации вершин в этом подграфе, удовлетворяющие условию 1) из математического описания алгоритма, и для каждой из них подсчитать значение, используемое в 2).

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

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

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

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-ый этап является недетерминированным всегда.