Участник:Артем Таран/Графо-ориентированный алгоритм кластеризации CHAMELEON: различия между версиями
(Новая страница: «== Свойства и структура алгоритма == === Общее описание алгоритма === Данный алгоритм выполн…») |
ShimchikN (обсуждение | вклад) м (test) |
||
| Строка 11: | Строка 11: | ||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
| + | |||
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
| + | |||
=== Информационный граф === | === Информационный граф === | ||
| + | |||
=== Ресурс параллелизма алгоритма === | === Ресурс параллелизма алгоритма === | ||
| + | |||
=== Входные и выходные данные алгоритма === | === Входные и выходные данные алгоритма === | ||
| + | |||
=== Свойства алгоритма === | === Свойства алгоритма === | ||
Версия 17:41, 13 октября 2016
Содержание
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Данный алгоритм выполняется в два этапа.
На первом этапе CHAMELEON использует алгоритм разделения графа для получения набора относительно малых кластеров. На втором этапе, для объединения кластеров, полученных на первом этапе, в настоящие кластеры, используется иерархическая агломеративная кластеризация. Таким образом, алгоритм, фактически, является гибридным, построенным комбинацией графо-ориентированных и классических иерархических методов. Рассмотрим эти этапы подробнее.
На первом этапе, согласно графо-ориентированному подходу, происходит построение графа на матрице сходства объектов по принципу k ближайших соседей. Две вершины такого графа соединяет ребро, если объект, соответствующий любой из этих вершин попадает в число k наиболее близких объектов для объекта, соответствующего другой вершине из данной пары. На Рисунке 6 изображены: объекты в пространстве – слева, граф по принципу 1-го ближайшего соседа – в середине, граф по принципу 3-х ближайших соседей – справа
