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

Алгоритм кластеризации с использованием представлений
Последовательный алгоритм
Последовательная сложность	[math][/math]
Объём входных данных	[math][/math]
Объём выходных данных	[math][/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math][/math]
Ширина ярусно-параллельной формы	[math][/math]

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

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.6 Последовательная сложность алгоритма

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

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

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

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

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

Недостатки

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

Достоинства

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