Добровецкий Дельцова/ Алгоритм кластеризации с использованием представлений

Основные авторы описания: Добровецкий Д.И., Дельцова А.В.

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

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

Алгоритм CURE (Clustering Using REpresentatives) выполняет агломеративную кластеризацию с использованием набора определяющих точек для определения объекта в кластер.

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

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

В CURE используется особый метод представления кластера: для каждого кластера выбирается определенно заданное точек - представителей данного кластера. Кластеры с наиболее похожими точками-представителями объединяются в один на 3-м шаге алгоритма. Благодаря этой технологии алгоритм CURE устойчив к выбросам и может выделять кластеры сложной формы и различных размеров.

Описание алгоритма:

Шаг 1: Построение дерева кластеров, состоящего из некоторых строк (доля строк задаётся параметром [math]\gamma[/math]) входного набора данных.

Шаг 2: Формирование «кучи» в оперативной памяти, расчет расстояния до ближайшего кластера (строки данных) для каждого кластера. При формировании кучи кластеры сортируются по возрастанию дистанции от кластера до ближайшего кластера. Расстояние между кластерами определяется по двум ближайшим элементам из соседних кластеров. Для определения расстояния между кластерами используются «манхеттенская», «евклидова» метрики или похожие на них функции.

Шаг 3: Слияние ближних кластеров в один кластер. Новый кластер получает все точки входящих в него входных данных. Расчет расстояния до остальных кластеров для новообразованного кластера. Для расчета расстояния кластеры делятся на две группы: первая группа – кластеры, у которых ближайшими кластерами считаются кластеры, входящие в новообразованный кластер, остальные кластеры – вторая группа. И при этом для кластеров из первой группы, если расстояние до новообразованного кластера меньше чем до предыдущего ближайшего кластера, то ближайший кластер меняется на новообразованный кластер. В противном случае ищется новый ближайший кластер, но при этом не берутся кластеры, расстояния до которых больше, чем до новообразованного кластера. Для кластеров второй группы выполняется следующее: если расстояние до новообразованного кластера ближе, чем предыдущий ближайший кластер, то ближайший кластер меняется. В противном случае ничего не происходит.

Шаг 4: Переход на шаг 3, если не получено требуемое количество кластеров.

Далее выбранные точки сдвигаются на [math]\alpha[/math] к центроиду кластера. Алгоритм становится основанным на методе поиска центроида при [math]\alpha = 1[/math], и основанным на всех точках кластера при [math]\alpha = 0[/math].

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

Исходные данные: [math]m[/math] точек размерности [math]n[/math], [math]k[/math] - количество кластеров, на которые их необходимо разбить, [math]c[/math] - количество точек-представителей кластера, [math]\alpha[/math] - параметр сдвига точек к центроиду кластера, [math]\gamma[/math] - доля точек загружаемых на 1-м шаге алгоритма в оперативную память. Расстояние между точками будем считать при помощи «Манхеттенской» метрики: [math]\rho(p,k) =\sum_{i=1}^n |p_{i} - k_{i}|[/math].

Выходные данные: дерево, ветвями которого являются кластеры, а листьями точки из входных данных.

На первом шаге выбираются [math]\lceil \gamma m\rceil[/math] точек из входных данных, далее помещаемые в "кучу" оперативной памяти. Каждая такая точка принимается за кластер, цетроида которого равна самой точке. Далее выполняем следующие итерации, пока количество кластеров не станет равно [math]k[/math]:

1) для каждого [math]i[/math]-го кластера вычисляется центроида [math]\mu_{i}[/math] по формуле: [math]\mu_{i} = \frac{1}{k_{i}}\sum_{p_{j}\in K_{i}} p_{j}[/math], где [math]K_{i}[/math] - множество точек [math]p_{j}[/math], находящихся в [math]i[/math]-м кластере, [math]k_{i}[/math] - их количество;

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

Далее для каждого кластера определяются [math]c[/math] точек-представителей:

1) выберем произвольную точку кластера и назначим её представителем;

2) пока количество точек-представителей меньше [math]c[/math] выбираем представителем точку, расстояние от которой до уже выбранных точек-представителей является максимальным среди всех оставшихся точек;

После чего для каждого представителя выполняем сдвиг к центроиде соответствующего кластера в [math]\alpha[/math] раз.

На последнем шаге происходит присвоение неиспользованных точек к кластерам. Для точки [math]p[/math] вычисляется расстояние до каждого представителя и её добавление в поддерево кластера, которому принадлежит ближайший для неё представитель.

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

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

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

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

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

Схема работы реализации алгоритма CURE

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

Алгоритм CURE в общем случае имеет сложность [math]O(n^2 logn)[/math]. Для двумерного же пространства его сложность равняется [math]O(n^2)[/math].

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

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

Дендрограмма иерархических методов кластеризации

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

Возможности распараллеливания алгоритма имеются на следующих его шагах:

• вычисления центроид для каждого кластера;
• расчет расстояний между кластерами;
• нахождение точек-представителей для каждого кластера;
• сдвиг точек-представителей каждого кластера к его центроиде;

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

Входные данные: [math]m[/math] точек размерности [math]n[/math], [math]k[/math] - количество кластеров, на которые их необходимо разбить, [math]c[/math] - количество точек-представителей каждого кластера, [math]\alpha[/math] - параметр сдвига точек-представителей к центроиду кластера, [math]\gamma[/math] - доля входных точек, загружаемых на 1-м шаге алгоритма в оперативную память.

Выходные данные: дерево, из корня которого выходят [math]k[/math] ветвей, являющиеся искомыми кластерами, а листьями этого дерева являются точки из входных данных.

1.10 Свойства алгоритма

Недостатки

• необходимо задавать пороговые значения и количество кластеров;
• эффективен только для данных низкой размерности;
• работает только на числовых данных;

Достоинства

• выполняет кластеризацию на высоком уровне даже при наличии выбросов;
• выделяет кластеры сложной формы и различных размеров;
• обладает линейно зависимыми требованиями к месту хранения данных;

2 ЧАСТЬ. Программная реализация алгоритма

2.7 Существующие реализации алгоритма

Последовательная реализация алгоритма CURE на Python/C++ представлена в пакете: pyclustering.

Также существует параллельная реализация алгоритма, описанная в сборнике [3].

3 Литература

[1] Воеводин В.В., Воеводин Вл.В. Параллельные вычисления. - СПб.: БХВ-Петербург, 2002. - 608 с.

[2] Guha, Sudipto; Rastogi, Rajeev; Shim, Kyuseok (2001). "CURE: An Efficient Clustering Algorithm for Large Databases". Information Systems. 26 (1): 35–58.

[3] Panagiotis E. Hadjidoukas, Laurent Amsaleg. OpenMP Shared Memory Parallel Programming. Volume 4315 of the series Lecture Notes in Computer Science pp 289-299 Parallelization of a Hierarchical Data Clustering Algorithm Using OpenMP