Участник:ЕкатеринаКозырева/Алгоритм динамической иерархической кластеризации CHAMELEON

Алгоритм динамической иерархической кластеризации CHAMELEON
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ O(nm + n log n + m^2 log m) }[/math]
Объём входных данных	[math]\displaystyle{ \frac{n (n - 1)}{2} }[/math]
Объём выходных данных	[math]\displaystyle{ n }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]\displaystyle{ }[/math]
Ширина ярусно-параллельной формы	[math]\displaystyle{ }[/math]

Автор описания Е.А.Козырева

часть. Свойства и структура алгоритмов

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

Алгоритм CHAMELEON был предложен в 1999 году тремя учеными из университета Миннесоты – George Karypis, Eui-Hong (Sam) Han и Vipin Kumar[1].

Предназначен для решения задач кластеризации. Кластеризация (или кластерный анализ) — это задача разбиения множества объектов на группы, называемые кластерами. Внутри каждой группы должны оказаться «похожие» объекты, а объекты разных группы должны быть как можно более отличны.

CHAMELEON - это агломеративный иерархический алгоритм кластеризации, ключевой особенностью которого является то, что он учитывает и взаимную связность, и сходство при определении наиболее похожей пары подкластеров, основываясь на динамической модели. Это означает, что в процессе кластеризации два кластера объединяются, только если их относительная взаимная связность и относительное взаимное сходство являются высокими по отношению к внутренней взаимосвязанности кластеров и близости элементов внутри кластеров. Кроме того, Хамелеон использует подход для моделирования степени взаимосвязанности и близости между каждой парой кластеров, который учитывает внутренние характеристики самих кластеров. Таким образом, он может автоматически адаптироваться к внутренним характеристикам объединяемых кластеров.

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

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

Исходные данные:

• Множество из n точек [math]\displaystyle{ V= {v_{ij}} }[/math] в метрическом пространстве, которое задано симметрической матрицей расстояний [math]\displaystyle{ A }[/math] размера [math]\displaystyle{ n\times n }[/math].
• [math]\displaystyle{ k }[/math] - количество ближайших соседей для вершин, [math]\displaystyle{ k \in N, k \leq n }[/math].
• [math]\displaystyle{ l }[/math] - наименьшее число вершин, которое может содержать наибольший подграф на 2-м этапе, [math]\displaystyle{ l \in N, l \leq n }[/math].

Обозначения:

• [math]\displaystyle{ G = (V, E) }[/math] - граф, полученный путём соединения каждой точки с её [math]\displaystyle{ k }[/math] ближайшими соседями.

• [math]\displaystyle{ K= \{K_{i}\} }[/math] - разбиение множества V на набор попарно непересекающихся связных подмножеств, полученное в результате выполнения второй фазы алгоритма.

• [math]\displaystyle{ G_{2} = (K, E_{2}) }[/math] - взвешенный граф, вершинами которого являются получившиеся подграфы, а ребрами - количество ребер исходного графа, соединяющих соответствующие подграфы.

• [math]\displaystyle{ C = \{C_{i}\} }[/math] - итоговое разбиение множества вершин графа [math]\displaystyle{ G_{2} }[/math] на набор кластеров.

Вспомогательные понятия

• [math]\displaystyle{ EC_{(C_{i},C_{j})} }[/math] - абсолютная взаимная связность пары кластеров [math]\displaystyle{ C_{i}, C{j} }[/math]. Определяется как сумма весов ребер, соединяющих вершины, принадлежащие [math]\displaystyle{ C{i} }[/math] c вершинами из [math]\displaystyle{ C{j} }[/math]. Внутренняя связность [math]\displaystyle{ EC_{(C_{i},C_{i})} }[/math] вычисляется как сумма ребер, входящих в разделитель, разбивающий [math]\displaystyle{ C{i} }[/math] на два равных подграфа.

• [math]\displaystyle{ RI_{(C_{i},C_{j})} = \frac{|EC_{(C_{i},C_{j})}|}{(|EC_{C_{i}}|+|EC_{C_{j}}|)/2} }[/math] - относительная взаимная связность пары кластеров [math]\displaystyle{ C_{i}, C{j} }[/math]

• [math]\displaystyle{ S_{EC_{(C_{i},C_{j})}} }[/math] - абсолютное взаимное сходство пары кластеров [math]\displaystyle{ C_{i}, C{j} }[/math]. Это суть среднее сходство между соединенными вершинами, принадлежащими [math]\displaystyle{ C{i} }[/math] и [math]\displaystyle{ C{j} }[/math] соответственно. Соединения обусловлены разбиением общего графа, полученного на первом этапе алгоритма.

• [math]\displaystyle{ RC_{(C_{i},C_{j})}= \frac{S_{EC_{(C_{i},C_{j})}}}{\frac{|C_{i}|}{|C_{i}+C_{j}|}*S_{EC_{(C_{i})}}+\frac{|C_{i}|}{|C_{i}+C_{j}|}*S_{EC_{(C_{j})}}} }[/math] - относительное взаимное сходство пары кластеров [math]\displaystyle{ C_{i}, C{j} }[/math]

Вычисляемые данные:

[math]\displaystyle{ U = (u_1, u_2, ..., u_n) }[/math] - n-мерный вектор, где [math]\displaystyle{ u_i \in N_{[C]} }[/math] - порядковый номер кластера, к которому принадлежит вершина i исходного множества V.

[math]\displaystyle{ }[/math]

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

Входные данные

1. Симметрическая матрица [math]\displaystyle{ A }[/math] расстояний между элементами данных размера [math]\displaystyle{ n\times n }[/math] с нулями на главной диагонали ([math]\displaystyle{ a_{ii}= 0, i = 1, \ldots, N }[/math]).

2. [math]\displaystyle{ k }[/math] - количество ближайших соседей для вершин (рекомендуемое значение [math]\displaystyle{ k }[/math] от 5 до 20 в зависимости от количества анализируемых объектов).

3. [math]\displaystyle{ l }[/math] - наименьшее число вершин, которое может содержать наибольший подкластер на 2-м этапе . Величина этого параметра варьируется от 1 до 5 % от общего числа объектов.

Объём входных данных

[math]\displaystyle{ \frac{n (n - 1)}{2} }[/math] (в силу симметричности и нулевой главной диагонали достаточно хранить только над/поддиагональные элементы).

Выходные данные

Вектор из [math]\displaystyle{ n }[/math] чисел [math]\displaystyle{ u_{1}, u_{2}, \ldots, u_{N} }[/math], где [math]\displaystyle{ u_{i} }[/math] - целое число, соответствующее кластеру [math]\displaystyle{ i }[/math]-го объекта.

Объём выходных данных

[math]\displaystyle{ n }[/math]

Литература

[1] George Karypis, Eui-Hong (Sam) Han и Vipin Kumar, «Chameleon: Hierarchical Clustering Using Dynamic Modeling», 1999.

[2] http://studopedia.ru/7_41934_algoritm-dinamicheskoy-ierarhicheskoy-klasterizatsii-CHAMELEON.html