Участник:Tikhomirov.mm/Алгоритм устойчивой кластеризации с иcпользованием связей (robust clustering using links, ROCK)

Основные авторы описания: В.А.Простов, М.М.Тихомиров

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

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

Алгоритм устойчивой кластеризации с иcпользованием связей ROCK (RObust Clustering using linKs) был совместно разработан Sudipto Guha, Rajeev Rastogi и Kyuseok Shim при работе в Bell Laboratories. Впервые алгоритм был опубликован в 1999 году в статье под названием "ROCK: A Robust Clustering Algorithm for Categorical Attributes", входящей в "ICDE '99 Proceedings of the 15th International Conference on Data Engineering".

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

Одним из основных понятий для алгоритма ROCK является соседство двух точек. Пусть нам дана функция схожести [math] sim(p_i,p_j) [/math], принимающая значения от 0 до 1, которая выражает схожесть или близость объектов(точек) [math]p_i[/math] и [math]p_j[/math]. Предполагается, что 1 соответствует абсолютной близости, и 0 - наоборот. Тогда при некоторой границе [math]\theta[/math] между 0 и 1, если [math] sim(p_i,p_j) \geq \theta [/math], то [math]p_i[/math] и [math]p_j[/math] будут соседними точками. Выбор Функции [math] sim(p_i,p_j) [/math] и граничного значения [math]\theta[/math] зависит входных данных и особенности реализации.

Вторым ключевым понятием являются связи. Функция связи [math] link(p_i,p_j) [/math] определяется как количество общих соседей у [math]p_i[/math] и [math]p_j[/math]. Из такого определения сразу видно, что чем больше значение связи, тем больше вероятность, что эти точки принадлежат одному и тому же кластеру. Такой подход является более глобальным, по сравнению с использованием только близости двух точек, что позволяет снизить число ошибок, особенно в тех случаях, когда кластеры имеют несколько близких точек.

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

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

Дано множество [math] S [/math] из [math] n [/math] элементов и число [math] k [/math]. Для каждых [math] p_i,p_j \in S [/math] задана функция схожести [math] 0 \leq sim(p_i,p_j) \leq 1[/math]. Также дано число [math] 0 \leq \theta \leq 1[/math].

Требуется разбить [math] S [/math] на [math] k [/math] не пересекающихся подмножеств(кластеров) [math]C_1, \dots, C_k[/math] так, чтобы значение целевой функции [math]E_l[/math]было как можно большим.

Определим следующие функции, полагая, что [math] p_i,p_j \in S. [/math]

Функция, определяющая соседство двух точек:

[math] \begin{align} neib(p_i, p_j) = \begin{cases} 1, sim(p_i, p_j) \geq \theta,\\ 0, sim(p_i, p_j) \lt \theta. \end{cases} \\ \end{align} [/math]

Функция, определяющая количество связей между точками:

[math] link(p_i, p_j) = \sum_{s\in S} neib(p_i,s) neib(p_j,s). [/math]

Определим теперь целевую функцию, считая [math]n_i[/math] количеством элементов в [math]C_i[/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]

Определим функцию связи для двух подмножеств [math] C_i, C_j [/math]:

[math] link[C_i, C_j] = \sum_{p_q \in C_i, p_r \in C_j} link(p_i, p_j) [/math]

Введем функцию полезности, выражающую то, насколько выгодно объединить подмножества [math] C_i, C_j [/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 [/math] подмножеств, затем делается [math] n - k [/math] шагов, на каждом из которых объединяются два подмножества, для которых значение функции полезности [math] g [/math] наибольшее.

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

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

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

2. Цикл по объединению кластеров, содержит [math] n-k [/math] шагов, на каждом из которых мы находим наилучшие кластеры для объединения и перестраиваем соответствующие кучи.

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

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

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

Процедура кластеризации выглядит следующим образом:

procedure cluster(S, k)
begin
  link := compute_links(S)
  for each s [math]\in[/math] S do
    q[s] := build_local_heap(link, s)
  Q := build_global_heap(S, q)
  while size(Q) > k do {
    u := extract_max(Q)
    v := max(q[u])
    delete(Q, v)
    w := merge(u, v)
    for each x [math]\in[/math] q[u] [math]\cup[/math] q[v] do {
      link[x,w] := link[x, u] + link[x, v]
      delete(q[x], u); delete(q[x], v)
      insert(q[x],w, g(x,w)); insert(q[w], x, g(x,w))
      update(Q, x, q[x])
    }
    insert(Q,w, q[w])
    deallocate(q[u]), deallocate(q[v])
  }
end

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

procedure compute_links(S)
begin
  Compute nbrlist[i] for every point i in S
  Set link[i, j] to be zero for all i, j
  for i := 1 to n do {
    N := nbrlist[i]
    for j := 1 to |N| - 1 do
      for l := j + 1 to |N| do
        link[N[j],N[l]] := link[N[j],N[l]] + 1
  }
end

Дла каждой точки [math]i[/math] строится список соседей [math]nbrlist[i][/math]. Поскольку любые две точки в таком списке имеют nbrlist[i] в качестве общего соседа, то для всех пар точек из списка увеличиваем значение функции связей.

2. Каждая точка объявляется отдельным кластером. Для каждого кластера [math]i[/math] строится локальная куча [math]q[i][/math], которая поддерживается до конца работы алгоритма. [math]q[i][/math] содержит все такие кластеры [math]j[/math], что [math]link[i,j] \neq 0[/math]. Кластеры [math]j[/math] в [math]q[i][/math] отсортированы в порядке убывания функции полезности [math]g(i,j)[/math]. Аналогичным образом создается глобальная куча [math]Q[/math], содержащая все кластеры. Элементы внутри аналогично отсортированы в соответствии с их максимальным значением функции полезности.

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

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

Вычисление связей может рассматриваться как перемножение двух матриц размера <math? n </math>, что можно реализовать за [math] O(n^{2.37})[/math]. Затраты памяти на хранение связей не превышают [math] n(n+1)/2 [/math], когда любая пара точек - соседние. Однако в большинстве случаев среднее число соседей [math] m_a [/math] и максимальное число соседей [math] m_m [/math] значительно меньше [math] n [/math], в связи с этим оценки сложности зависят от данных параметров. Сложность построения списка соседей оценивается [math] O(n^2)[/math], Вычисление связей состоит из трех вложенных циклов и может быть оценено [math] O(n m_m m_a)[/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(n)[/math] времени (поскольку размер каждой кучи не может превышать [math] n [/math]). Рассмотрим теперь основной while-цикл. Он содержит [math] O(n)[/math] итераций, где основная сложность каждого шага приходится на for-цикл. В худшем случае потребуется вставить новый кластер в [math] O(n)[/math] локальных куч размера [math] n[/math], что потребует [math] O( n \log{} n)[/math] времени. Таким образом, сложность всего внешнего цикла составляет [math] O(n^2 \log{} n)[/math] в худшем случае. Затраты памяти зависят от начального размера локальных куч, поскольку при слиянии кластеров их старые кучи удаляются, а размер новой не превышает суммы старых. Поскольку каждая куча сожержит лишь кластеры с ненулевыми связями, то сложность совпадает с первой частью и равна [math] O(\min \{ n m_m m_a, n^2 \} )[/math].

Итоговые оценки для всего алгоритма:

Сложность по времени:

[math] O(n^2 + n m_m m_a + n^2 \log{} n)[/math]

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

[math] O(\min \{ n^2, n m_m m_a \} )[/math]

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

Как видно из графа в алгоритме есть ряд узких мест.

Рассмотрим их подробнее:

1) Вершина построения матрицы links. Данные вычисления не могут быть прямо распараллелены, нельзя для каждого списка соседей запустить данную функцию. Это связано с тем, что во время выполнения данных вычислений необходимо производить запись в матрицу и любой список может писать в любое место матрицы. В худшем случае (когда все соседи всем) при параллельном запуске возможны постоянные конфликты. Но в данной вершине все же есть потенциал для параллельной работы. Он заключается в том, что можно в параллели обрабатывать список соседей. При подходе в лоб нагрузка на ядра будет не равномерна.

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

3) Вершина взятия топ 2 кластеров. Узкая но малозатратная вершина.

4) Вершина обновления куч. Так же узкая вершина в которой нужно в каждой локальной куче вставить в нужное место кластер и так же поступить с глобальной кучей.

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

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

1) На первом этапе происходит вычисление соседей. Затраты данных операций при условии достаточного количества ядер [math]T_1 = O(n)[/math]

2) На этапе построения связей [math]n[/math] этапов в каждом из которых можно сделать [math]k[/math] расчетов(с учетом распараллеливания), где [math]k[/math] - количество соседей. В худшем случае [math]T_2 = O(n^2)[/math] в среднем случае [math]T_2 = O(n * k_m)[/math], где [math]k_m[/math] среднее ожидаемое число соседей.

3) Построение одной кучи это сложность [math]O(n)[/math]. Плюс для каждой кучи сортировка [math]O(n * log(n))[/math]. Соответственно итоговая сложность создания локальных куч [math]T_3 = O(n * log(n))[/math].

4) Построение и сортировка глобальной кучи так же [math]T_4 = O(n * log(n))[/math].

5) Цикл в котором происходит выбор кластеров, сливание, пересчет и обновление куч. Игнорируем выбор кластеров (достать из кучи [math]O(1)[/math] ). Для всех элементов кучи слитых кластеров пересчитываем значение связи, вставляем в кучу выбранного кластера информацию о новом кластере, удаляем старое. Делается это за [math]O(log(n))[/math]. Соответственно в худшем случае, одна итерация цикла это [math]T_i = O(log(n))[/math]. Количество итераций n - k. Значит [math]T_5 = O((n - k) * log(n))[/math]. При k = 1, [math]T_5 = O(n * log(n)[/math]

Итоговая сложность в худшем случае равна:

[math]T_1 + T_2 + T_3 + T_4 + T_5 = O(n) + O(n^2) + O(n * log(n)) + O(n * log(n)) + O(n * log(n)) = O(n^2)[/math]

Итоговая сложность в среднем случае равна [math]O(n * k_m) + O(n * log(n))[/math]. Тут важно понимать, что в зависимости от данных как [math]log(n)[/math] может быть больше [math]k_m[/math], так и наоборот.

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

Входные данные: Множество [math]S[/math] из [math]n[/math] элементов, число кластеров [math]k[/math]. В зависимости от реализации, некоторые параметры алгоритма могут также подаваться на вход или быть определены заранее.

Объем входных данных: Зависит от типа элементов из множества [math]S[/math], поскольку алгоритм может быть реализован для широкого класса данных. В общем случае требуется хранить массив из [math]n[/math] элементов.

Выходные данные: Метки класса (номер кластера) для каждого элемента.

Объем выходных данных: Для каждого входного элемента достаточно вернуть соответствующую ему метку (число), поэтому минимальный размер выхода: массив из [math]n[/math] чисел.