Участник: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} \\ link(p_i, p_j) = \sum_{s\in S} neib(p_i,s) neib(p_j,s).\\ \end{align} [/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.9 Входные и выходные данные алгоритма

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

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

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

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