Уровень алгоритма

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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 37: Строка 37:
  
 
* <math>C = \{C_{i}\}</math> - итоговое разбиение множества вершин графа <math>G_{2}</math> на набор кластеров.
 
* <math>C = \{C_{i}\}</math> - итоговое разбиение множества вершин графа <math>G_{2}</math> на набор кластеров.
 +
 +
''Вспомогательные понятия''
 +
 +
*<math>EC_{(C_{i},C_{j})}</math> - абсолютная взаимная связность пары кластеров <math>C_{i}, C{j}</math>. Определяется как сумма весов ребер, соединяющих вершины, принадлежащие <math>C{i}</math> c вершинами из <math>C{j}</math>. Внутренняя связность <math>EC_{(C_{i},C_{i})}</math> вычисляется как сумма ребер, входящих в разделитель, разбивающий <math>C{i}</math> на два равных подграфа.
 +
 +
*<math>RI_{(C_{i},C_{j})} = \frac{|EC_{(C_{i},C_{j})}|}{(|EC_{C_{i}}|+|EC_{C_{j}}|)/2}</math> - относительная взаимная связность пары кластеров <math>C_{i}, C{j}</math>
 +
 +
*<math>S_{EC_{(C_{i},C_{j})}}</math> - абсолютное взаимное сходство пары кластеров <math>C_{i}, C{j}</math>. Это суть среднее сходство между соединенными вершинами, принадлежащими <math>C{i}</math> и <math>C{j}</math> соответственно. Соединения обусловлены разбиением общего графа, полученного на первом этапе алгоритма.
 +
 +
*<math> 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>C_{i}, C{j}</math>
 +
  
 
''Вычисляемые данные'':
 
''Вычисляемые данные'':

Версия 15:10, 15 октября 2016


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


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

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

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

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

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

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

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

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

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

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

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

  • [math]G = (V, E)[/math] - граф, полученный путём соединения каждой точки с её [math]k[/math] ближайшими соседями.
  • [math]K= \{K_{i}\}[/math] - разбиение множества V на набор попарно непересекающихся связных подмножеств, полученное в результате выполнения второй фазы алгоритма.
  • [math]G_{2} = (K, E_{2})[/math] - взвешенный граф, вершинами которого являются получившиеся подграфы, а ребрами - количество ребер исходного графа, соединяющих соответствующие подграфы.
  • [math]C = \{C_{i}\}[/math] - итоговое разбиение множества вершин графа [math]G_{2}[/math] на набор кластеров.

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

  • [math]EC_{(C_{i},C_{j})}[/math] - абсолютная взаимная связность пары кластеров [math]C_{i}, C{j}[/math]. Определяется как сумма весов ребер, соединяющих вершины, принадлежащие [math]C{i}[/math] c вершинами из [math]C{j}[/math]. Внутренняя связность [math]EC_{(C_{i},C_{i})}[/math] вычисляется как сумма ребер, входящих в разделитель, разбивающий [math]C{i}[/math] на два равных подграфа.
  • [math]RI_{(C_{i},C_{j})} = \frac{|EC_{(C_{i},C_{j})}|}{(|EC_{C_{i}}|+|EC_{C_{j}}|)/2}[/math] - относительная взаимная связность пары кластеров [math]C_{i}, C{j}[/math]
  • [math]S_{EC_{(C_{i},C_{j})}}[/math] - абсолютное взаимное сходство пары кластеров [math]C_{i}, C{j}[/math]. Это суть среднее сходство между соединенными вершинами, принадлежащими [math]C{i}[/math] и [math]C{j}[/math] соответственно. Соединения обусловлены разбиением общего графа, полученного на первом этапе алгоритма.
  • [math] 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]C_{i}, C{j}[/math]


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

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

[math][/math]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[math]n[/math]

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