Участник: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 Вычислительное ядро алгоритма

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

Первая часть - вычисление всех связей между точками.

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

• • немного общих слов о методах вычисления первой и второй части будет добавлено позже.