Участник:Екатерина/Алгоритм устойчивой кластеризации с использованием связей

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

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

Задача кластеризации заключается в следующем. Имеется множество [math]n[/math] объектов [math]S=\{s_1,\ldots,s_n\}[/math] и функция расстояния/сходства между объектами [math]\rho (x_i,x_j)[/math]. Требуется разбить множество [math]S[/math] на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из объектов, близких по метрике [math]\rho[/math], а объекты разных кластеров существенно отличались. При этом каждому объекту [math]s\in S[/math] приписывается метка(номер) кластера [math]y_i[/math].

Алгоритм кластеризации - это функция [math]f:X\to Y[/math], которая каждому объекту [math]s\in S[/math] ставит в соответствие метку кластера [math]y\in Y[/math].

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

• эвристические графовые алгоритмы;
• статистические алгоритмы;
• иерархические алгоритмы.

Иерархические алгоритмы кластеризации строят не одно разбиение на непересекающиеся классы, а систему вложенных разбиений. Различают 2 основных типа: дивизимные и алгомеративные алгоритмы. В алгомеративной иерархической кластеризации объекты объединяются во все более и более крупные кластеры.

Одним из алгоритмов алгомеративной иерархической кластеризации является алгоритм устойчивой кластеризации с использованием связей (robust clustering using links, ROCK), предложенный Sudipto Guha (Stanford University), Rajeev Rastogi (Bell Laboratories) и Kyuseok Shim (Bell Laboratories) в 2000 году. Этот алгоритм отлично подходит для объектов с категориальными признаками, то есть признаками, принимающими свои значения из некоторого множества.

В 2005 году была предложена быстрая версия этого ROCK-алгоритма "Quick ROCK"(QROCK).

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

Входные данные: множество точек [math]P = \{p_1, \ldots , p_n\}[/math].

Необходимо разделить множество [math]P[/math] на [math]k[/math] непересекающиеся множества.

Определение 1.Два объекта [math]p_i[/math] и [math]p_j[/math] будут соседями, если они значительно близки друг к другу. Два объекта [math]p_i[/math] и [math]p_j[/math] являются соседями, если [math]sim(p_i, p_j)\geq \theta[/math].

Мера схожести пары точек [math]sim(p_i, p_j)[/math] может быть основана на евклидовом расстоянии, коэффициенте Жаккарда или на какой-либо другой неметрической функции схожести. Поэтому две точки [math]p_i[/math] и [math]p_j[/math] будут соседями, если [math]sim(p_i, p_j)\geq \theta[/math]. Предполагается, что мера [math]sim[/math] принимает значения от 0 до 1, при этом чем ближе значение меры к 1, тем больше схожи точки. [math]\theta[/math] - определенный пользователем параметр, который используется для контроля того, насколько похожи должны быть пары точек, чтобы считаться соседями. Если [math]\theta[/math] равно 1, то соседями будут только идентичные точки, если же 0, то соседями может быть любая произвольная пара точек. В зависимости от желаемой степени близости пользователь выбирает пороговое значение параметра [math]\theta[/math].

Одно из возможных определений функции [math]sim[/math], определение, основанное на коэффициенте Жаккарда (Jaccard coefficient). То есть сходство двух множеств [math]T_1[/math] и [math]T_2[/math] означает следующее [math]sim(T_1,T_2) = \frac{|T_1\cap T_2|}{|T_1\cup T_2|}[/math], где [math]|T_i|[/math] - количество предметов в [math]T_i[/math]. Чем больше элементов в [math]T_1[/math] и [math]T_2[/math] похожи, тем больше значение [math]|T_1\cap T_2|[/math]. Деление его на [math]|T_1\cup T_2|[/math] гарантирует, что значение [math]\theta[/math] окажется в промежутке от 0 до 1. Таким образом уравнение вычисляет похожесть двух множеств на основе похожести элементов, входящих в них.

[math]link(p_i, p_j)[/math] - функция связи, определяемая как число общих соседей между точками [math]p_i[/math] и [math]p_j[/math]. Из определения следует, что чем больше значение функции связи, тем вероятнее, что точки [math]p_i[/math] и [math]p_j[/math] принадлежат одному кластеру.

[math]link[C_i, C_j] = \sum_{\begin{smallmatrix}p_q\in C_i,\; p_r\in C_j\end{smallmatrix}}^{ } link(p_{q},p_r)[/math] - хранит число связей между точками кластеров [math]C_i[/math] и [math]C_j[/math].

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

Основная вычислительная нагрузка в алгоритме приходится на умножение матриц при вычислении числа связей. Оно имеет квадратичную сложность.

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

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

Алгоритм иерархической кластеризации ROCK представлен ниже в виде двух процедур: собственно кластеризации и вычисления связей между точками.

1.5.1 Кластеризация

На вход алгоритм принимает некий набор [math]n[/math] точек [math]S[/math]. Кроме того, заданное значение [math]k[/math] кластеров желаемого разбиения. Изначально каждая точка является отдельным кластером. На шаге 1 вычисляется количество связей между всеми парами точек. На шагах 2 и 3 для каждого [math]s[/math] строится локальная куча [math]q[s][/math]. Локальная куча [math]q[s][/math] содержит те кластеры [math]t[/math], для которых [math]link[s,t][/math] отлична от нуля, причем кластеры в куче упорядочены в порядке убывания, на основе функции их схожести [math]g(s,t)[/math]. На шаге 4 вычисляется глобальная куча [math]Q[/math], содержащая все текущие кластеры, упорядоченные в порядке убывания на основе [math]g(s,max(q[s]))[/math]. Таким образом на каждом шаге лучший кластер в [math]Q[/math] и соответствующий ему максимальный кластер из [math]q[/math] наилучшая пара кластеров для объединения их в один кластер.

На шаге 5 начинает выполняться цикл [math]while[/math], до тех пор, пока в глобальной куче не останется только [math]k[/math] кластеров. На каждой итерации [math]while[/math]-цикла на шагах 6-9 из [math]Q[/math] извлекается лучший кластер [math]u[/math] и соответствующий ему максимальный кластер [math]v[/math] из локальной кучи и удаляется из [math]Q[/math], так как он будет объединен с [math]u[/math], и больше в ней не нужен. Далее кластеры [math]u[/math] и [math]v[/math] объединяются в новый кластер [math]w[/math].

Далее на шагах 10-15 в цикле [math]for[/math] для каждого кластера, который содержит элементы [math]u[/math] и [math]v[/math] в своей локальной куче, они оттуда удаляются и заменяются на новый кластер [math]w[/math]. Для [math]w[/math] создается новая локальная куча.

На 17 шаге новый кластер добывляется в локальную кучу, а на 18 шаге уничтожаются локальные кучи для [math]u[/math] и [math]v[/math].

[math] \begin{align} &\mathbf{procedure}\ cluster (S,k) \\ &\mathbf{begin} \\ &1.\ \ link := compute\_links(S) \\ &2.\ \ \mathbf{for\ each}\ s\in S\ \mathbf{do} \\ &3.\ \ \ \ q[s] := build\_local\_heap(link,s) \\ &4.\ \ Q := build\_global\_heap(S,q) \\ &5.\ \ \mathbf{while}\ size(Q)\ \gt k\ \mathbf{do}\ \{ \\ &6.\ \ \ \ u := extract\_max(Q) \\ &7.\ \ \ \ v := max(q[u]) \\ &8.\ \ \ \ delete(Q,v) \\ &9.\ \ \ \ w := merge(u,v) \\ &10.\ \ \ \mathbf{for\ each}\ x\ \in \ q[u]\ \cup \ q[v]\\ &11.\ \ \ \ \ link[x,w] := link[x,u]\ +\ link[x,v] \\ &12.\ \ \ \ \ delete(q[x],u);\ delete(q[x],v) \\ &13.\ \ \ \ \ insert(q[x],w,g(x,w));\ insert(q[w],x,g(x,w) \\ &14.\ \ \ \ \ update(Q,x,q[x]) \\ &15.\ \ \ \} \\ &16.\ \ \ insert(Q,w,q[w]) \\ &17.\ \ \ deallocate(q[u]);\ deallocate(q[v]) \\ &18.\ \ \} \\ &\mathbf{end} \end{align} [/math]

1.5.2 Вычисление связей

Для вычисления связи между всеми парами точек в [math]S[/math] рассматривается матрица смежности [math]A[/math] размера [math]n*n[/math], где [math]A[i,j][/math] равна 1 или 0 если [math]i[/math] и [math]j[/math] являются или не являются соседями соответственно. В результате умножения [math]A*A[/math] в позиции [math]A[i,j][/math] получим количество связей между [math]i[/math] и [math]j[/math].

[math] \begin{align} &\mathbf{procedure}\ compute\_links(S) \\ &\mathbf{begin} \\ &1.\ \ Compute\ nbrlist[i]\ for\ every\ point\ i\ in\ S \\ &2.\ \ Set\ link[i,j]\ to\ be\ zero\ for\ all\ i,j \\ &3.\ \ \mathbf{for}\ i := 1\ \mathbf{to}\ n\ \mathbf{do}\ \{ \\ &4.\ \ \ \ N := nbrlist[i] \\ &5.\ \ \ \ \mathbf{for}\ j := 1\ \mathbf{to}\ |N| - 1\ \mathbf{do} \\ &6.\ \ \ \ \ \ \mathbf{for}\ l := j+1\ \mathbf{to}\ |N|\ \mathbf{do} \\ &7.\ \ \ \ \ \ \ \ link[N[j],N[l]] := link[N[j],N[l]]+1 \\ &8.\ \ \} \\ &\mathbf{end} \end{align} [/math]

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

Вычислительная сложность алгоритма складывается из сложности инициализации, вычисления связей и собственно кластеризации.

• Инициализация глобальной кучи выполняется за время [math]O(n)[/math].
• Инициализация локальной кучи также требует [math]O(n)[/math].
• Связи между парой точек можно вычислить за [math]O(n^2 m_\alpha)[/math] шагов, где [math]m_\alpha[/math] - среднее число связей.
• В процедуре кластеризации основные вычисления происходят в цикле [math]while[/math]. Сам цикл выполняется [math]O(n)[/math] раз. Внутренний [math]for[/math]-цикл доминирует над сложностью в [math]while[/math]-цикле. Его сложность [math]O(n\log n)[/math], так как размер каждой очереди в худшем случае [math]n[/math] и новый объединенный кластер [math]w[/math] может нуждаться в [math]O(n)[/math] локальных очередей. Следовательно весь [math]while[/math]-цикл выполняется за [math]O(n^2\log n)[/math].

Время работы ROCK-алгоритма равна [math]O(n^2+nm_m m_\alpha + n^2\log n)[/math], где [math]m_m[/math] - максимально возможное количество соседей, [math]m_\alpha[/math] - среднее число соседей, [math]n[/math] - количество объектов.

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

Входные данные: на вход подается [math]n[/math] объектов и [math]k[/math] - количество кластеров, на которое необходимо разделить объекты.

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

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

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

Алгоритм устойчивой кластеризации с использованием связей реализован в библиотеке CBA в июне 2016 года.