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

Алгоритм динамической иерархической кластеризации 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. Хамелеон - это агломеративный иерархический алгоритм кластеризации, который позволяет преодолеть ограничения существующих алгоритмов кластеризации. Ключевой особенностью алгоритма является то, что он учитывает взаимосвязанность и близость в определении наиболее похожей пары кластеров. Существующие алгоритмы используют статическую модель кластеров и не используют информацию о характере отдельных кластеров, как они объединяются, поэтому эти алгоритмы могут легко выбрать и объединить неправильную пару кластеров. Кроме того, Хамелеон использует новый подход к модели степень взаимосвязанности и близость между каждой парой кластеров. Этот подход учитывает внутренние характеристики самих кластеров. Таким образом, он не зависит от статической, приобретенной пользователем модели и может автоматически адаптироваться к внутренним характеристикам сливающихся кластеров. Алгоритм применяется к разреженному графу, в котором узлы представляют элементы данных, а взвешенные ребра представляют сходство между элементами данных. Это разреженное представление графа позволяет масштабировать Хамелеон до больших наборов данных и успешно использовать наборы данных, которые доступны только в пространстве подобия, а не в метрических пространствах. Наборы данных в метрическом пространстве имеют фиксированное количество атрибутов для каждого элемента данных, в то время как наборы данных в пространстве подобия только обеспечивают сходство между элементами данных. Хамелеон находит кластеры в наборе данных с помощью двухфазного алгоритма. На первом этапе, Хамелеон использует алгоритм граф-разбиения, группируюoий элементы данных в несколько относительно небольших подкластеров. На втором этапе, он использует алгоритм, чтобы найти подлинные кластеры путем многократного сочетания этих подкластеров.

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