Участник:ЕкатеринаКозырева/Алгоритм динамической иерархической кластеризации CHAMELEON: различия между версиями
| Строка 12: | Строка 12: | ||
== Общее описание алгоритма == | == Общее описание алгоритма == | ||
| − | Алгоритм | + | Алгоритм CHAMELEON предназначен для решения задач кластеризации. Кластеризация (или кластерный анализ) — это задача разбиения множества объектов на группы, называемые кластерами. Внутри каждой группы должны оказаться «похожие» объекты, а объекты разных группы должны быть как можно более отличны. |
| + | Алгоритм был предложен в 1999 году тремя учеными из университета Миннесоты – George Karypis, Eui-Hong (Sam) Han и Vipin Kumar. | ||
Хамелеон - это агломеративный иерархический алгоритм кластеризации, который позволяет преодолеть ограничения существующих алгоритмов кластеризации. Ключевой особенностью алгоритма является то, что он учитывает взаимосвязанность и близость в определении наиболее похожей пары кластеров. Существующие алгоритмы используют статическую модель кластеров и не используют информацию о характере отдельных кластеров, как они объединяются, поэтому эти алгоритмы могут легко выбрать и объединить неправильную пару кластеров. | Хамелеон - это агломеративный иерархический алгоритм кластеризации, который позволяет преодолеть ограничения существующих алгоритмов кластеризации. Ключевой особенностью алгоритма является то, что он учитывает взаимосвязанность и близость в определении наиболее похожей пары кластеров. Существующие алгоритмы используют статическую модель кластеров и не используют информацию о характере отдельных кластеров, как они объединяются, поэтому эти алгоритмы могут легко выбрать и объединить неправильную пару кластеров. | ||
Кроме того, Хамелеон использует новый подход к модели степень взаимосвязанности и близость между каждой парой кластеров. Этот подход учитывает внутренние характеристики самих кластеров. Таким образом, он не зависит от статической, приобретенной пользователем модели и может автоматически адаптироваться к внутренним характеристикам сливающихся кластеров. Алгоритм применяется к разреженному графу, в котором узлы представляют элементы данных, а взвешенные ребра представляют сходство между элементами данных. Это разреженное представление графа позволяет масштабировать Хамелеон до больших наборов данных и успешно использовать наборы данных, которые доступны только в пространстве подобия, а не в метрических пространствах. Наборы данных в метрическом пространстве имеют фиксированное количество атрибутов для каждого элемента данных, в то время как наборы данных в пространстве подобия только обеспечивают сходство между элементами данных. Хамелеон находит кластеры в наборе данных с помощью двухфазного алгоритма. На первом этапе, Хамелеон использует алгоритм граф-разбиения, группируюoий элементы данных в несколько относительно небольших подкластеров. На втором этапе, он использует алгоритм, чтобы найти подлинные кластеры путем многократного сочетания этих подкластеров. | Кроме того, Хамелеон использует новый подход к модели степень взаимосвязанности и близость между каждой парой кластеров. Этот подход учитывает внутренние характеристики самих кластеров. Таким образом, он не зависит от статической, приобретенной пользователем модели и может автоматически адаптироваться к внутренним характеристикам сливающихся кластеров. Алгоритм применяется к разреженному графу, в котором узлы представляют элементы данных, а взвешенные ребра представляют сходство между элементами данных. Это разреженное представление графа позволяет масштабировать Хамелеон до больших наборов данных и успешно использовать наборы данных, которые доступны только в пространстве подобия, а не в метрических пространствах. Наборы данных в метрическом пространстве имеют фиксированное количество атрибутов для каждого элемента данных, в то время как наборы данных в пространстве подобия только обеспечивают сходство между элементами данных. Хамелеон находит кластеры в наборе данных с помощью двухфазного алгоритма. На первом этапе, Хамелеон использует алгоритм граф-разбиения, группируюoий элементы данных в несколько относительно небольших подкластеров. На втором этапе, он использует алгоритм, чтобы найти подлинные кластеры путем многократного сочетания этих подкластеров. | ||
Версия 00:27, 14 октября 2016
| Алгоритм динамической иерархической кластеризации CHAMELEON | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]O(nm + n log n + m^2 log m)[/math] |
| Объём входных данных | [math][/math] |
| Объём выходных данных | [math][/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math][/math] |
| Ширина ярусно-параллельной формы | [math][/math] |
Автор описания Е.А.Козырева
Содержание
- 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. Хамелеон - это агломеративный иерархический алгоритм кластеризации, который позволяет преодолеть ограничения существующих алгоритмов кластеризации. Ключевой особенностью алгоритма является то, что он учитывает взаимосвязанность и близость в определении наиболее похожей пары кластеров. Существующие алгоритмы используют статическую модель кластеров и не используют информацию о характере отдельных кластеров, как они объединяются, поэтому эти алгоритмы могут легко выбрать и объединить неправильную пару кластеров. Кроме того, Хамелеон использует новый подход к модели степень взаимосвязанности и близость между каждой парой кластеров. Этот подход учитывает внутренние характеристики самих кластеров. Таким образом, он не зависит от статической, приобретенной пользователем модели и может автоматически адаптироваться к внутренним характеристикам сливающихся кластеров. Алгоритм применяется к разреженному графу, в котором узлы представляют элементы данных, а взвешенные ребра представляют сходство между элементами данных. Это разреженное представление графа позволяет масштабировать Хамелеон до больших наборов данных и успешно использовать наборы данных, которые доступны только в пространстве подобия, а не в метрических пространствах. Наборы данных в метрическом пространстве имеют фиксированное количество атрибутов для каждого элемента данных, в то время как наборы данных в пространстве подобия только обеспечивают сходство между элементами данных. Хамелеон находит кластеры в наборе данных с помощью двухфазного алгоритма. На первом этапе, Хамелеон использует алгоритм граф-разбиения, группирую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
