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

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

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

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

Алгоритм устойчивой кластеризации с использованием связей (robust clustering using links, ROCK) построен на основе понятия связей между кластеризуемыми точками и их соседства. Две точки считаются соседями, если являются достаточно близким (схожими): [math]sim({p_i}, {p_j}) \gt = \theta[/math], где [math]\theta[/math] - заданное пороговое значение в интервале [math](0, 1)[/math]. Связь [math]link({p_i}, {p_j})[/math] между двумя точками определяется как число общих соседей между точками [math]{p_i}[/math] и [math]{p_j}[/math]. Таким образом, чем большее значение функции связи для двух точек, тем более вероятно они принадлежат одному кластеру.

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

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

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

Задача кластеризации сводится к выделению такого разбиения точек на кластеры, которое максимизирует сумму связей точек принадлежащих одному кластеру, и минимизирует эту функцию для точек из разных кластеров. Таким образом, для разбияния на [math]k[/math] кластеров необходима максимизация следующей функции.

[math]E_l = \sum_{i=1}^k n_i * \sum_{p_q, p_r \in C_i} \frac{link(p_q, p_r)}{n_i^{1+2f(\theta)}}[/math] (1)

Данная функция отличается от простой суммы связей для каждого кластера, так как не обеспечивает распределение точек, имеющих мало связей между собой, по разным кластерам. Поэтому действительную сумму связей в кластере следует разделить на ожидаемую сумму связей. Функция [math]f(\theta)[/math] задается пользователем исходя из свойств обрабатываемых данных и ожидаемого характера кластеризации. Она должна обладать следующим свойством: каждая точка, принадлежащая кластеру [math]C_i[/math], имеет приблизительно [math]n_i^{f(\theta)}[/math] соседей в этом кластере.

Связь между двумя кластерами определяется как

[math]link({C_i}, {C_j}) = \sum^{}_{{p_q}\in{C_i}, {p_r}\in{C_j}}{link[{C_i}, {C_j}]}[/math]

Тогда для выбора кластеров для объединения определяется целевая функция качества:

[math]g(C_i, C_j) = \frac{link[C_i, C_j]}{(n_i+n_j)^{1+2f(\theta)} - f_i^{1+2f(\theta)} - f_j^{1+2f(\theta)}}[/math]

Аналогично целевой функции (1) значение связи между двумя кластерами делится на ожидаемое число связей между кластерами.

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

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

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

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

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

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

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
29 
30 procedure compute_links(S)
31 begin
32     Compute nbrlist[i] for every i in S
33     Set link[i, j] to zero for all i, j
34     for i := 1 to n do
35     begin
36         N := nbrlist[i]
37         for j := 1 to |N| - 1 do
38         begin
39             for l := j + 1 to |N| do
40             begin
41                 link[N[j], N[l]]] := link[N[j], N[l]] + 1
42             end
43         end
44     end
45 end

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

Для вычисления количества связей с помощью возведения матрицы в квадрат можно воспользоваться алгоритмом Копперсмита—Винограда, вычислительная сложность которого равна [math]O(n^{2,37})[/math] [3] ([math]n[/math] - количество точек). Для случаев разреженное матрицы смежности в работе [1] описывается алгоритм, имеющий сложность [math]O(n^2 + n{m_m}{m_a})[/math], где [math]{m_a}[/math] и [math]{m_m}[/math] - это среднее и максимальное количество соседей точки соответственно.

Каждая куча может быть построена за время [math]O(n)[/math] [4]. Внешний цикл итерационной части алгоритма исполняется [math]O(n)[/math] раз. Так как на очередной итерации размер каждой локальной кучи в худшем случае может равняться [math]n[/math], то новый кластер должен быть помещен в [math]n[/math] локальных куч, что дает временную сложность вложенного цикла [math]O(n\log{n})[/math]. Таким образом, сложность внешнего цикла в худшем случае будет [math]O(n^2\log{n})[/math].

Итак, сложность описанного алгоритма будет

[math]L + O(n^2\log{n})[/math],

где [math]L[/math] - сложность алгоритма вычисления количества связей.

1.7 Информационный граф

На рисунке представлен информационный граф алгоритма. Блок L соответствует предварительному подсчету числа связей точек, блок QLs и QG - созданию локальных и глобальной куч соответственно, блок M - слиянию кластеров, блок U - обновлению куч.

TODO

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

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

TODO?

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

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

1. Множество [math]n[/math] точек, которые необходимо клатеризовать
2. Желаемое число кластеров [math]k[/math]

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

1. [math]k[/math] полученных кластеров