Участник:Hromovalexander/Алгоритм динамической иерархической кластеризации CHAMELEON

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

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

Алгоритм CHAMELEON - алгоритм динамической иерархической кластеризации графа.

Кластеризация - разбиение графа на несколько подграфов таким образом, чтобы объекты внутри одного кластера были максимально близки (схожи), а данные двух различных кластеров максимально различались. Различие и схожесть объектов определяются некоей метрикой, известной заранее. Количество кластеров, на которые будет разбит граф, заранее неизвестно, и зависит от свойств объекта и выбранной метрики. Простейшей возможной метриков является расстояние между точками (если предполагать, что у каждой вершины графа есть координаты).

Алгоритм состоит из 3-х основных этапов:

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

2-й этап заключается в разбиении построенного графа на небольшие кластеры (связные подграфы)

3-й этап состоит в формировании итогового множества кластеров

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

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

Множество из n объектов и заданные расстояния между объектами. Эта информация позволяет построить матрицу смежности, в которой будут указаны расстояния между соответствующими объектами по некой метрике. Матрица смежности симметрична, на главной диагонали стоят 0, поэтому достаточно хранить [math]\frac{n(n-1)}{2}[/math] элементов. Кроме того задаются параметры, влияющие на работу алгоритма - число k, по которому на первом этапе строится граф по принципу k ближайших соседей, и два параметра [math]{T_{ri}}[/math] и [math]{T_{rc}}[/math], используемые на третьем этапе для того, что определить, что не нужно далее продолжать кластеризацию.

Первый этап

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

Второй этап

Состоит в итеративном разбиении графа на множество подграфов. Изначально (на первой итерации) разбиение состоит из единственного подграфа. Пусть [math]T[/math] - множество подграфов на текущей итерации. Каждая итерация выполняется следующим образом - выбирается максимальный подграф из имеющихся в разбиении по числу вершин (то есть такой подграф [math]G_1(V_1,E_1)\in{T}: \forall {G_2(V_2,E_2)\in{T}: G_2\neq G_1} =\gt |(V_1)|\gt |(V_2)|[/math] ). Выбранный подграф разбивается на 2 подграфа следующим образом - сначала выбираются все разбиения [math]G_2(V_2,E_2)[/math] и [math]G_3(V_3,E_3)[/math], такие, что [math]\min(|V_2|,|V_3|)\geq\frac{|V_1|}{4}[/math]. Далее среди всех таких разбиений выбирается такое, для которого величина [math]\sum{|E_1^*|},E_1^* [/math]- некое ребро, ведущее из вершины, попавшей в [math]G_2[/math] в вершину, попавшую в [math]G_3[/math]. В определенный момент, когда размер наибольшего кластера [math]|V_b|\leq{q*|V|}[/math], где [math]|V|[/math] - количество вершин в изначальном графе, а [math]q[/math] - предварительно заданный параметр, процесс дальнейшего разибения прекращается и алгоритм переходи на 3-й этап

Третий этап алгоритма: 

Введем несколько определений:

Абсолютной взаимной связностью пары кластеров называется величина [math]EC_{({C_i},{C_j})}[/math], вычисляется как сумма весов ребер, соединяющих вершина 1-го кластера [math]C_i[/math] с вершинами второго кластера [math]C_j[/math]. Внутренняя связность кластера [math]E_{C_i}[/math]вычисляется как сумма весов ребер, входящих в разделитель, разбивающих [math]C_i[/math] на 2 равных подграфа.

Относительная взаимная связность пары кластеров [math]RI_{(C_i,C_j)}[/math] вычисляется по формуле [math]RI_{(C_i,C_j)}=\frac{2*|EC_{(C_i,C_j)}|}{|EC_{C_i}|+|EC_{C_j}|}[/math]

Абсолютное взаимное сходство пары кластеров [math]S_{E_{(C_i,C_j)}}[/math]вычисляется как среднее сходство между связанными вершинами [math]C_i[/math] и [math]C_j[/math]

Относительное взаимное сходство пары кластеров [math]C_i[/math] и [math]C_j[/math] обозначается [math]RC_{(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_j|}{|C_i|+|C_j|}*S_{EC_{(C_j)}}}}[/math]

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

Есть два различных подхода анализа сходства.

Первый - для каждой пары кластеров проверяется истинность следующих высказываний

[math]RI(Ci,Cj)\geq{T_{RI}} [/math] и [math]RC_{(C_{i},C_{j})}\geq{T_{RC}}[/math]

В случае, если для некоторого [math]C_i[/math] существует несколько кластеров [math]C_j[/math], удовлетворяющих этим условиям, выбирается такой [math]C_j[/math], что

значение [math]EC_{(C_i,C_j)}[/math] максимально.

Процесс останавливается, когда нет кластеров, удовлетворяющих указанным условиям (либо когда остался только 1 кластер)

Второй подход - выбирается такая пара кластеров, что [math]RI_{(C_i,C_j)}*RC^\alpha_{(C_i,C_j)}[/math] максимально, где [math]\alpha[/math] - заданный заранее параметр.

Процесс останавливается, когда нет кластеров, удовлетворяющих указанным условиям (либо когда остался только 1 кластер)

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

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

На втором этапе вычислительное ядро состоит из повторяющегося нахождения разбиения графа на два подграфа, удовлетворяющего ранее описанным условиям

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

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

В рамках первого этапа макрооперацияй считается построение графа k-ближайших соседей

В рамках второго этапа макрооперациями считаются операции разбиения подграфа.

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

1.5 Схема реализации последовательного алгоритма

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

 int n; // Количество точек.
int k; // Параметр k
int Dist[n][n]; // Матрица расстояний между точками.
 
integer E[n][n]; // Матрица рёбер графа

foreach (int i=0; i<n; i++) ) {
   integer KNeighbours[k]; // список, используемый для хранения ближайших соседей
   integer countN = 0;
   
   foreach (int j=i+1; j<n; j++ ) {
     //Заполняем список k ближайших соседей по матрице Dist
   }
 
   foreach (int j=0; j<k; j++) {
     E[i][KNeighbours[j]] = 1;
   }
 }
 return E;

double q; //Параметр, описание находится в соответствующем разделе. 
Graph g = getBiggestGraph(); //Находим граф максимального размера
int maxSize = getSize(g); //Находим размер данного графа
while (maxSize > n * q) { 
   breakGraph(g); // Разбиваем граф
}

Graph graphs[m]; //Разбиение по кластерам
while (count(graphs)>1){
   pairs_exist = false //Значение будет обновлено позже, если найдется подходящая пара для объединения
   for (int i = 0; i < m; i++) {
      for (int j = i + 1; j < m; j++) { 
         if (checkSimilarity(graphs[i],graphs[j])) { //Проверяем, достаточно ли схожи графы для объединения
			unite(graphs[i], graphs[l]) 
		 } else {
			break;
		 }
      }
   }
}

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

На первом этапе построение графа k-ближайших соседей требует [math]O(n^2)[/math] операций.

На втором этапе для итеративного разбиения требуется [math]O(nm)[/math]операций, где [math]n[/math] - количество вершин графа, а [math]m[/math] - количество подграфов в итоговом разбиении.

На третьем этапе требуется [math]O(m^2logm)[/math] операций, причем вычисление метрики считается за одну операцию.

Итоговая оценка последовательной сложности [math]O(n^2)+O(nm)+O(m^2logm)[/math]

1.7 Информационный граф

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

На первом этапе вычисление [math]k[/math] ближайших вершин для [math]i[/math]-й вершины можно распараллелить между [math]n[/math] процессами (это вычисление независимо для каждой вершины). На втором и третьем этапах процессы разбиения и объединения подграфов происходят последовательно. Получаем оценку параллельной сложности алгоритма [math]O(nm)+O(m^2logm)[/math]

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

На вход алгоритму подается множество из [math]n[/math] векторов длины [math]l[/math], описывающих объекты для кластеризации. Также передаются параметры [math]k[/math] (для построения графа k ближайших соседей на первом этапе) и [math]q[/math] (используется на втором этапе для определения критерия прекращения итерационного процесса). На выходе алгоритм выдает массив длины [math]n[/math], заполненный числами от [math]1[/math] до [math]n[/math], показывающими, в какой кластер попал соответствующий объект.

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

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

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

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

Одна из последовательных реализаций алгоритма находится по ссылке [1] Параллельных реализаций алгоритма найдено не было