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

Вступление

1 ЧАСТЬ. Свойства и структура алгоритмов

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

Алгоритм устойчивой кластеризации с иcпользованием связей (robust clustering using links, ROCK) решает задачу кластеризации объектов по заранее заданному количеству [math]k[/math] кластеров. В пространстве объектов должна быть определена функция сходства/расстояния между объекта [math]sim(p_i, p_j)[/math]. Данный алгоритм относится к иерархическим методам кластеризации, который начинает с разбиения пространства на большое количество кластеров и постепенно объединяя их до нужного количества. Алгоритм пытается объединить в один кластер точки с максимальным числом общих соседей.

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

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

Пусть дано множество объектов [math]P = \{p_1, \ldots , p_n\}[/math], натуральное число [math]k[/math], функция схожести [math]sim(p_i, p_j)[/math], пороговое значение [math]\theta : 0\leq\theta\leq 1[/math] и функция функция [math] f( \theta ) [/math].

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

Две точки называются соседними, если [math]sim(p_i, p_j) \geq \theta[/math]

Количеством общих соседей [math]link(p_i, p_j)[/math] называется число точек, являющимися соседними для точек [math]p_i, 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] g(C_i, C_j) = \frac{link[C_i,C_j]}{(n_i + n_j)^{1 + 2f(\theta )} - n_i^{1+2f(\theta )} - n_j^{1+2f(\theta )}}[/math], где [math]n_i[/math] - число объектов в кластере [math]C_i[/math].

Алгоритм начинает работу, разбив всё пространство на [math]n[/math] кластеров.

Затем на каждом шаге он вычисляет значение [math]g(C_i, C_j)[/math] для каждой пары кластеров и объединяет эти кластеры в один.

Алгоритм ведёт свою работу до тех пор, пока не получит [math]k[/math] кластеров.

В качестве функции [math]f( \theta )[/math] обычно используется функция [math]f(\theta ) = \frac{\theta - 1}{\theta + 1}[/math] , [math]n_i^{1+2f(\theta )}[/math] - ожидаемое число связей между парами объектов кластера [math]C_i[/math].

Если все признаки категориальны, то в качестве функции схожести можно использовать функцию:

[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]. Данная функция удобна в случае, если все признаки категориальны

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

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

Вычислительное ядро алгоритма состоит из двух основных частей.

1. Попарное вычисление связей между точками. Можно вычислить, умножив матрицу смежности саму на себя. Имеет квадратичную сложность от количества точек.
2. Итеративное объединению кластеров. За [math]n-k[/math] шагов кластеры последовательно объединяются. Реализовывается с помощью структуры данных куча. Для каждого кластера math>i</math> хранится своя куча [math]q[i][/math], содержащая все связанный с ним кластеры, упорядоченная по убыванию функции качества. Также хранится глобальная куча [math]Q[/math], содержащая все кластеры [math]j[/math], упорядоченные по мере убывания функции качества [math]g(j, max(q[j]))[/math]. На каждом шаге итерации, после объединения кластеров требуется перестроить кучи объединённых кластеров в одну и перестроить глобальную кучу.

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

Макроструктура состоит из последовательного выполнения двух шагов, описанных в описании ядра алгоритма:

1. Построении матрицы связей
2. Пересчёте куч и объединении кластеров

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

Реализация основной вычислительной части:

 1 procedure cluster(S, k)
 2 begin
 3     link := compute_links(S)
 4     for s in S do
 5     begin
 6         q[s] := build_local_heap(link, s)
 7     end
 8     Q := build_global_heap(S, q)
 9     while size(Q) > k do
10     begin
11         u := extract_max(Q)
12         v := max(q[u])
13         delete(Q, v)
14         w := merge(u, v)
15         for each x in q[u] or q[v] do
16         begin
17             link[x, w] := link[x, u] + link[x, v]
18             delete(q[x], u)
19             delete(q[x], v)
20             insert(q[x], w, g(x, w))
21             insert(q[w], x, g(x, w))
22             update(Q, x, q[x])
23         end
24         insert(Q, w, q[w])
25         deallocate(q[u])
26         deallocate(q[v])
27     end
28 end

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

Временная сложность:

• Инициализация глобальной кучи - [math]O(n)[/math]
• Инициализация локальной кучи - требует [math]O(n)[/math]
• Вычисление связей между парой точек - в худшем случае алгоритмом Штрассена вычисляется за [math]O(n*n^{2.37})[/math], в среднем за [math]O(n m_\alpha m_m)[/math]
• Построение каждой кучи - [math] O(n)[/math]
• Сортировка каждой кучи - [math] O( n \log{} n)[/math]
• Основной цикл объединения кластеров выполняется в [math]n-k[/math] итераций.
  • Вставить новый кластер в в [math] O(n)[/math] локальных куч размера [math] n[/math] - [math] O( n \log{} n)[/math]

Итого: [math] O(n^2 + n m_m m_a + n^2 \log{} n)[/math]

Сложность по памяти:

• Поскольку каждая точка [math]i[/math] может иметь не более [math]\min \{ m_m m_i, n \} )[/math] связей, то общие затраты памяти не превышают [math] O(\min \{ n m_m m_a, n^2 \} )[/math].
• Хранение связей - [math] O(\min \{ n m_m m_a, n^2 \} )[/math] (поскольку каждая точка [math]i[/math] может иметь не более [math]\min \{ m_m m_i, n \} )[/math] связей)

Итого: [math] O(\min \{ n^2, n m_m m_a \} )[/math]