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

CHAMELEON
Последовательный алгоритм
Последовательная сложность	$O(n*n + n*m + n*log{n} + m*log{m})$
Объём входных данных	$n * p$
Объём выходных данных	$n$
Параллельный алгоритм
Высота ярусно-параллельной формы	$O(n)$ - этап 1. $O(q)$ - отдельная итерация этапа 3.
Ширина ярусно-параллельной формы	$O(n)$ - этап 1. $O(q)$ - отдельная итерация этапа 3.

Авторы статьи: Лазовский Р. А. ( разделы 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.5 Схема реализации последовательного алгоритма

Схема представлена в виде C++-подобного псевдокода, макрооперации в алгоритме выделены в соответствии с предыдущим разделом описания.

// First stage.
int k // Number of neighbors.
float v[n][p] // Initial vectors.
float M[n][n] // Adjacency matrix.
for (int i = 0; i < n; ++i) {
 for (int l = 0; l < n; ++l) {
  M[i][l] = Compute_metric(v[i],v[l]);
 }
}
Graph max_graph // Structure/class that represents a graph.
Neighbor_list list // Here neighbors are initially stored.
max_graph.add_vertices // Vertices ~ initial vectors.
for (int i = 0; i < n; ++i) {
 for (int l = i + 1; i < n; ++i) { // "Smart" version - we do not repeat same vertex combinations.
  if (neighbor_number < k) {
    add_neighbor(v[i],v[l]) // Just add.
  }else{
    substitute_neighbor(v[i],v[l]) // Check whether a new element is closer than some of the oldies.
  }
 }
 max_graph.add_neighbors // Looks at neighbor lists of current vector and adds them
}

// Second stage. 
float percent // Determines when to stop splitting graphs. 
Graph graphs[n] // GRAPHS WILL MOST LIKELY TAKE LESS SPACE, IT'S JUST THE UPPER LIMIT. 
max_graph = find_max_graph() // Biggest graph by number of vertices available. 
while (graph_size(max_graph) > n * percent) {
  Split_graph(max_graph); // Split the graph - a macro operation that represents the second phase.
} 

// Third stage. 
Graph graphs[m] // That's how many graphs we got. m <= n. 
bool pairs_exist // Check if the're pairs of clusters to unite.
while (num_graphs > 1 && pairs_exist){
 pairs_exist = false // So we don't repeat if it fails.
 for (int i = 0; i < m; ++i) {
  for (int l = i + 1; l < m; ++l) { // Also a "Smart" version.
    check_pair(pairs_exist, graphs[i], graphs[l]); // Check whether graphs are similar enough by some metrics.
    if (pairs_exist) { Unite_graphs(graphs[i], graphs[l]) }; // Pairs_exist is set to true if something's found.
  }
 }
}

1.6 Последовательная сложность алгоритма

Общая временная сложность последовательного варианта алгоритма CHAMELEON определяется как $O(n*m + n*log{n} + m*log{m})$. Однако эта оценка не учитывает необходимости построения матрицы смежности по исходному набору векторов, что означает дополнительные $O(n^2)$ операций. Итоговая оценка составляет $O(n*n + n*m + n*log{n} + m*log{m})$ операций.

Следует также обратить внимание, что это оценка по числу не сложений и умножений, а достаточно крупных операций. Например, вычисление метрики между двумя векторами рассматривается как одна операция, а она включает в себя $n$ умножений и $2n$ сложений ( для вычисления квадратичной нормы разности векторов).

1.8 Ресурс параллелизма алгоритма

Параллельную сложность алгоритма CHAMELEON следует оценивать отдельно для каждого этапа. На первом этапе алгоритм поиска $k$ ближайших соседей может быть выполнен за $n - 1$ вычислений значения метрики между двумя векторами. На втором этапе итерации алгоритма выполняются строго последовательно, а распараллеливание алгоритма внутри итерации не относится к теме статьи. На третьем этапе итерации также выполняются последовательно, однако возможно распараллеливание обработки пар кластеров внутри итерации. Каждая итерация может быть выполнена за $p - 1$ вычислений значения метрики между двумя кластерами.

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

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

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

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

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

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

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

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

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

2 Программная реализация алгоритма

2.1 Масштабируемость алгоритма и его реализации

Пока ничего нет.

2.2 Существующие реализации алгоритма

Существует несколько последовательных реализаций алгоритма. С одной из таких референсных реализаций можно ознакомиться по ссылке [1].
Возможна реализация алгоритма CHAMELEON с использованием графовых библиотек, как, например METIS [2] , hMETIS [3] и RANN [4].
Параллельных реализаций алгоритма CHAMELEON в графовых библиотеках мною найдено не было. Однако существует исследование, связанное с реализацией CHAMELEON посредством технологии OpenMP, с которым можно ознакомиться здесь [5].