Версия 21:48, 14 октября 2016

Содержание

1 Свойства и структура алгоритма
2 Программная реализация алгоритма
3 Литература

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

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

эвристические графовые алгоритмы; ^[1]
статистические алгоритмы; ^[1]
иерархические алгоритмы.

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

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

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

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

Входные данные: множество объектов [math]P = \{p_1, \ldots , p_n\}[/math], целое число [math]k[/math], пороговое значение [math]\theta[/math], где [math]0\leq\theta\leq 1[/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]sim[/math] принимает значения от 0 до 1, при этом чем ближе значение меры к 1, тем больше схожи точки. Чаще всего используется мера схожести, основанная на коэффициенте Жаккарда (Jaccard coefficient)^[4]: [math]sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}[/math], где [math]|p_i|[/math] - количество атрибутов в [math]p_i[/math]. Чем больше атрибутов в [math]p_i[/math] и [math]p_j[/math] похожи, тем больше значение [math]|p_i\cap p_j|[/math]. Деление его на [math]|p_i\cup p_j|[/math] гарантирует, что значение [math]\theta[/math] окажется в промежутке от 0 до 1. Таким образом уравнение вычисляет похожесть двух множеств на основе похожести элементов, входящих в них.

\\

Одно из возможных определений функции [math]sim[/math], определение, основанное на коэффициенте Жаккарда (Jaccard coefficient)^[5]. То есть сходство двух множеств [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]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.4 Макроструктура алгоритма

Как записано и в описании ядра алгоритма, основную часть метода составляют [math]O(n^2\log n)[/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.7 Информационный граф

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

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

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

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

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

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

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

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

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

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

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

3 Литература

↑ ^1,0 ^1,1 ^1,2 К. В. Воронцов Лекции по алгоритмам кластеризации и многомерного шкалирования, 21 декабря 2007 года
↑ Sudipto Guha, Rajeev Rastogi, Kyuseok Shim: ROCK: A Robust Clustering Algorithm for Categorical Attributes, Volume 25, Issue 5, July 2000, Pages 345-366
↑ M. Duttaa, A. Kakoti Mahantab, Arun K. Pujaric QROCK: A quick version of the ROCK algorithm for clustering of categorical data
↑ Richard O. Duda and Peter E. Hard. Pattern Classification and Scene Analysis. A Wiley-Interscience Publication, New York, 1973.
↑ Richard O. Duda and Peter E. Hard. Pattern Classification and Scene Analysis. A Wiley-Interscience Publication, New York, 1973.

[Voroncov-1] 1,0 ^1,1 ^1,2 К. В. Воронцов Лекции по алгоритмам кластеризации и многомерного шкалирования, 21 декабря 2007 года

[2] Sudipto Guha, Rajeev Rastogi, Kyuseok Shim: ROCK: A Robust Clustering Algorithm for Categorical Attributes, Volume 25, Issue 5, July 2000, Pages 345-366

[3] M. Duttaa, A. Kakoti Mahantab, Arun K. Pujaric QROCK: A quick version of the ROCK algorithm for clustering of categorical data

[4] Richard O. Duda and Peter E. Hard. Pattern Classification and Scene Analysis. A Wiley-Interscience Publication, New York, 1973.

[5] Richard O. Duda and Peter E. Hard. Pattern Classification and Scene Analysis. A Wiley-Interscience Publication, New York, 1973.

[1]

[2]

[3]

[4]

[5]

@@ Строка 16: / Строка 16: @@
 :'''Определение 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> может быть основана на евклидовом расстоянии, коэффициенте Жаккарда или на какой-либо другой неметрической функции схожести. Чаще всего используется мера схожести, основанная на коэффициенте Жаккарда (Jaccard coefficient)<ref>Richard O. Duda and Peter E. Hard. Pattern  Classification  and  Scene  Analysis. A Wiley-Interscience Publication, New York, 1973.</ref>:  <math>sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}</math>, где <math>|p_i|</math> - количество атрибутов в <math>p_i</math>. Предполагается, что мера <math>sim</math> принимает значения от 0 до 1, при этом чем ближе значение меры к 1, тем больше схожи точки.
+:Мера схожести пары объектов <math>sim(p_i, p_j)</math> может быть основана на евклидовом расстоянии, коэффициенте Жаккарда или на какой-либо другой неметрической функции схожести. Предполагается, что мера <math>sim</math> принимает значения от 0 до 1, при этом чем ближе значение меры к 1, тем больше схожи точки. Чаще всего используется мера схожести, основанная на коэффициенте Жаккарда (Jaccard coefficient)<ref>Richard O. Duda and Peter E. Hard. Pattern  Classification  and  Scene  Analysis. A Wiley-Interscience Publication, New York, 1973.</ref>:  <math>sim(p_i,p_j) = \frac{|p_i\cap p_j|}{|p_i\cup p_j|}</math>, где <math>|p_i|</math> - количество атрибутов в <math>p_i</math>. Чем больше атрибутов в <math>p_i</math> и <math>p_j</math> похожи, тем больше значение <math>|p_i\cap p_j|</math>. Деление его на <math>|p_i\cup p_j|</math> гарантирует, что значение <math>\theta</math> окажется в промежутке от 0 до 1. Таким образом уравнение вычисляет похожесть двух множеств на основе похожести элементов, входящих в них.
 \\
-:Одно из возможных определений функции <math>sim</math>, определение, основанное на коэффициенте Жаккарда (Jaccard coefficient)<ref>Richard O. Duda and Peter E. Hard. Pattern  Classification  and  Scene  Analysis. A Wiley-Interscience Publication, New York, 1973.</ref>. То есть сходство двух множеств <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>sim</math>, определение, основанное на коэффициенте Жаккарда (Jaccard coefficient)<ref>Richard O. Duda and Peter E. Hard. Pattern  Classification  and  Scene  Analysis. A Wiley-Interscience Publication, New York, 1973.</ref>. То есть сходство двух множеств <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>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>.

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