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

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

Материал из Алговики
Перейти к навигации Перейти к поиску


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


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

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

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

Алгоритм ХАМЕЛЕОН был предложен в 1999 году тремя учеными из университета Миннесоты – George Karypis, Eui-Hong (Sam) Han и Vipin Kumar. Хамелеон - это агломеративный иерархический алгоритм кластеризации, который позволяет преодолеть ограничения существующих алгоритмов кластеризации. Ключевой особенностью алгоритма является то, что он учитывает взаимосвязанность и близость в определении наиболее похожей пары кластеров. Существующие алгоритмы используют статическую модель кластеров и не используют информацию о характере отдельных кластеров, как они объединяются, поэтому эти алгоритмы могут легко выбрать и объединить неправильную пару кластеров. Кроме того, Хамелеон использует новый подход к модели степень взаимосвязанности и близость между каждой парой кластеров. Этот подход учитывает внутренние характеристики самих кластеров. Таким образом, он не зависит от статической, приобретенной пользователем модели и может автоматически адаптироваться к внутренним характеристикам сливающихся кластеров. Алгоритм применяется к разреженному графу, в котором узлы представляют элементы данных, а взвешенные ребра представляют сходство между элементами данных. Это разреженное представление графа позволяет масштабировать Хамелеон до больших наборов данных и успешно использовать наборы данных, которые доступны только в пространстве подобия, а не в метрических пространствах. Наборы данных в метрическом пространстве имеют фиксированное количество атрибутов для каждого элемента данных, в то время как наборы данных в пространстве подобия только обеспечивают сходство между элементами данных. Хамелеон находит кластеры в наборе данных с помощью двухфазного алгоритма. На первом этапе, Хамелеон использует алгоритм граф-разбиения, группируюoий элементы данных в несколько относительно небольших подкластеров. На втором этапе, он использует алгоритм, чтобы найти подлинные кластеры путем многократного сочетания этих подкластеров.

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

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

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

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

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

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

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

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

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