Участник: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] кластеров, или когда все связи между оставшимися кластерами равны нулю.