Участник:ЕкатеринаКозырева/Алгоритм динамической иерархической кластеризации CHAMELEON: различия между версиями
| Строка 28: | Строка 28: | ||
== Ресурс параллелизма алгоритма == | == Ресурс параллелизма алгоритма == | ||
== Входные и выходные данные алгоритма == | == Входные и выходные данные алгоритма == | ||
| − | + | ''Входные данные'': | |
1. Симметрическая матрица <math>A</math> расстояний между элементами данных, размера <math>n\times n</math> (элементы <math>a_{ij}</math>). | 1. Симметрическая матрица <math>A</math> расстояний между элементами данных, размера <math>n\times n</math> (элементы <math>a_{ij}</math>). | ||
| Строка 37: | Строка 37: | ||
3. <math>l</math> - наименьшее число вершин, которое может содержать наибольший подкластер на 2-м этапе . Величина этого параметра варьируется от 1 до 5 % от общего числа объектов. | 3. <math>l</math> - наименьшее число вершин, которое может содержать наибольший подкластер на 2-м этапе . Величина этого параметра варьируется от 1 до 5 % от общего числа объектов. | ||
| − | + | ''Объём входных данных'': | |
<math>\frac{n (n - 1)}{2}</math> (в силу симметричности и нулевой главной диагонали достаточно хранить только над/поддиагональные элементы). | <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> чисел <math>u_{1}, u_{2}, \ldots, u_{N}</math>, где <math>u_{i}</math> - целое число, соответствующее кластеру <math>i</math>-го объекта. | ||
| − | + | ''Объём выходных данных'': | |
<math>n</math> | <math>n</math> | ||
Версия 12:05, 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 Общее описание алгоритма
- 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 Математическое описание алгоритма
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_{ij}[/math]). [math]A[/math] – содержит нули на главной диагонали, т.е. [math]d_{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
