Участник: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 Математическое описание алгоритма

Исходные данные: Первоначально исходными данными алгоритма являются $n$ векторов длины $p$, каждый из которых соответствует одному объекту. На основании значений элементов этих векторов строится матрица смежности размера $n * n$ ( возможно сокращение требуемого объема памяти до $(n*(n - 1))/ 2$ в соответствии с выбранной метрикой.

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

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

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

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

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

Вычисляемые данные: В процессе агломеративной кластеризации для всех объектов, т.е. всех вершин всех кластеров указывается индекс $j$ кластера, к которому они принадлежат. После завершения алгоритма возможно перенумеровать кластеры. В любом случае на выходе будет иметься $n$ значений, так как число объектов в процессе работы алгоритма не изменялось.

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

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

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

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

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

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

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

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

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

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

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

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

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

Соотношение последовательной и параллельной сложности: Различные этапы алгоритма строго последовательны относительно друг друга. На первом этапе отношение последовательной сложности алгоритма к параллельной есть $n$. На втором и третьем этапах различные итерации последовательны относительно друг друга. Однако внутри итераций допускается некоторый параллелизм. Например, для итераций третьего этапа в наилучшем случае отношение сложности последовательной реализации к параллельной есть $p/2$, где $p$ - число кластеров на конкретной итерации.

Вычислительная мощность: графовые алгоритмы, вообще говоря, обладают низкой вычислительной мощностью. В случае CHAMELEON вычислительная мощность первого этапа равна $O(1)$. Для второго и третьего этапов оценка вычислительной мощности по сложениям и умножениям затруднительна, однако в терминах макроопераций можно дать грубую оценку. Вычислительная мощность каждой итерации второго этапа - $1 / \sum C_n^k$, где $n$ - число вершин в выбранном подграфе, а $k$ варьируется от $0.25 * n$ до $0.5 * n$. Вычислительная мощность каждой итерации третьего этапа - $O(1)$

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