Участник:ЕкатеринаКозырева/Алгоритм динамической иерархической кластеризации CHAMELEON
Алгоритм динамической иерархической кластеризации CHAMELEON | |
Последовательный алгоритм | |
Последовательная сложность | O(nm + n log n + m^2 log m) |
Объём входных данных | \frac{n (n - 1)}{2} |
Объём выходных данных | n |
Параллельный алгоритм | |
Высота ярусно-параллельной формы | |
Ширина ярусно-параллельной формы |
Автор описания Е.А.Козырева
Содержание
- 1 часть. Свойства и структура алгоритмов
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 часть. Программная реализация алгоритма
- 3 Литература
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.3 Вычислительное ядро алгоритма
1.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
1.6 Последовательная сложность алгоритма
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
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
1.10 Свойства алгоритма
2 часть. Программная реализация алгоритма
2.1 Масштабируемость алгоритма и его реализации
2.2 Существующие реализации алгоритма
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