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

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

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

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

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

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

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

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

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

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

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

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

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

• граф $G = (V, E)$, полученный путём соединения каждой точки с её $k$ ближайшими соседями.

• $C = \{C_{i}\}$ - разбиение множества V на набор попарно непересекающихся связных подмножеств.

• $G_{2} = (C, E_{2})$ - что ита???

• $K = \{K_{i}\}$ - итоговое разбиение множества вершин графа $G_{2}$ на набор кластеров.

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

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

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

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

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

2. $k$ - количество ближайших соседей для вершин (рекомендуемое значение $k$ от 5 до 20 в зависимости от количества анализируемых объектов).

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

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

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

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

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

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

$n$

3 Литература

[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