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

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],

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

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

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

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

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

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

Две точки [math]p_i[/math] и [math]p_j[/math] будут соседями если их сходство превышает некоторое пороговое значение [math] \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.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 года.