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

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

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

Возможность человека накапливать и сохранять информацию во многом опирается на нашу же способность систематизировать данные, которые мы получаем извне. Мы упорядочиваем все получаемые нами данные в группы и категории, что помогает нам удерживать их в памяти и осмысливать окружающую действительность. Те же принципы используют многие интеллектуальные приложения, используя алгоритмы кластеризации (clustering).

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

Подавляющее большинство таких алгоритмов позволяют учитывать лишь числовые признаки для описания наблюдаемых объектов. Однако в реальной практике часто встречаются задачи с категориальными признаками, принимающими свои значения из конечного неупорядоченного множества. Одним из алгоритмов кластеризации, хорошо подходящим для категориальных признаков, является алгоритм устойчивой кластеризации с использованием связей (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]sim(p_i, p_j)\geq \theta[/math], где [math]sim(*)[/math] - функция подобия, а [math]\theta[/math] - некоторое пороговое значение. При этом функция [math]sim[/math] принимает значения от 0 до 1, причем чем ближе это значение к 1, тем больше похожи точки [math]p_i[/math] и [math]p_j[/math]. [math]\theta[/math] - определенный пользователем параметр, который используется для контроля того, насколько похожи должны быть пары точек, чтобы считаться соседями. Пи этом если функция [math]sim[/math] возвращает значение 1, то точки идентичны, а если 0, то две точки абсолютно непохожи. В зависимости от желаемой степени близости, соответствующее значение может быть выбрано пользователем.

Одно из возможных определений функции [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. Таким образом уравнение вычисляет похожесть двух множеств на основе похожести элементов в них входящих.

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

[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.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] - количество объектов.