Статья: Анализ существующих алгоритмов кластеризации (часть 1)

8. Алгоритмы кластеризации, основанные на теории графов

Согласно этому типу алгоритмов кластеризация реализуется на графе, где узел рассматривается как точка данных, а ребро рассматривается как отношение между точками данных. Типичными алгоритмами кластеризации такого типа являются CLICK и кластеризация на основе MST. Основная идея CLICK чтобы сгенерировать кластеры с минимальным весовым распределением графа. Генерация минимального связующего дерева из графа данных является ключевым шагом для выполнения кластерного анализа для алгоритма кластеризации на основе MST.

Более подробную информацию об алгоритмах кластеризации такого типа можно найти в [1, 6].

Анализ:

1. Оценка вычислительной сложности представлена в табл. 7, где v - обозначает количество вершин, e - обозначает количество ребер, а f (v, e) - обозначает вычислительную сложность минимального разреза;

2. Преимущества: высокая эффективность кластеризации, высокая точность результатов кластеризации;

3. Недостатки: сложность вычислений резко возрастает с увеличением сложности графа.

Таблица 7 Вычислительная сложность

9. Сеточные алгоритмы кластеризации

Основная идея такого рода алгоритмов кластеризации заключается в том, что исходное пространство данных превращается в сеточную структуру с определенным размером для кластеризации. Типичными алгоритмами кластеризации такого типа являются STING и CLIQUE. Основная идея STING, возможность использования для параллельной обработки - пространство данных разделяется на множество прямоугольных блоков путем построения иерархической структуры, и данные на разных уровнях структуры группируются соответственно. CLIQUE использует преимущества сеточных алгоритмов кластеризации и алгоритмов кластеризации на основе плотности.

Более подробную информацию об алгоритмах кластеризации такого типа можно найти в [10].

Анализ:

1. Оценка вычислительной сложности представлена в табл. 8

2. Преимущества: низкая вычислительная сложность, высокая масштабируемость и возможность параллельной обработки;

3. Недостатки: результат кластеризации чувствителен к размерам ячейки, высокая эффективность вычислений за счет снижения точности кластеризации.

Таблица 8 Вычислительная сложность

10. Алгоритмы кластеризации, основанные на фрактальной теории

Типичным алгоритмом такого рода кластеризации является FC, основной идеей которого является то, что изменение любых внутренних данных кластера не оказывает никакого влияния на внутреннее качество фрактальной размерности.

Более подробную информацию об алгоритмах кластеризации такого типа можно найти в [6, 8].

Анализ:

1. Вычислительная сложность FC составляет O (n);

2. Преимущества: высокая эффективность кластеризации, высокая масштабируемость, пригодность для данных произвольной формы и высокой размерности;

3. Недостатки: результат кластеризации чувствителен к параметрам.

11. Алгоритмы кластеризации, основанные на модели

Основная идея состоит в том, чтобы выбрать конкретную модель для каждого кластера. Существует в основном два вида алгоритмов кластеризации на основе моделей, один из которых основан на методе статистического обучения, а другой на методе обучения нейронной сети.

Типичными алгоритмами, основанными на статистическом методе обучения, являются COBWEB и GMM. Основная идея COBWEB состоит в том, чтобы построить дерево классификации на основе некоторых эвристических критериев, чтобы реализовать иерархическую кластеризацию при условии, что распределение вероятностей каждого атрибута является независимым. Типичными алгоритмами, основанными на методе обучения нейронной сети, являются SOM и ART. Основная идея SOM состоит в том, чтобы построить отображение сокращения размеров из входного пространства высокого измерения в выходное пространство низкого измерения, исходя из предположения, что во входных данных существует топология. Основная идея ART, инкрементального алгоритма, состоит в том, чтобы динамически генерировать новый нейрон, чтобы соответствовать новому шаблону нового кластера, когда текущих нейронов недостаточно.

Более подробную информацию об алгоритмах кластеризации такого типа можно найти в [5, 10].

Анализ:

1. Оценка вычислительной сложности представлена в табл. 9

2. Преимущества: разнообразные и хорошо разработанные модели, обеспечивающие средства для адекватного описания данных, каждая модель имеет значительные преимущества в некоторых конкретных областях;

3. Недостатки: относительно высокая вычислительная сложность в целом, результат кластеризации чувствителен к параметрам выбранных моделей.

Таблица 9 Вычислительная сложность

Выводы

кластеризация алгоритм вычислительный

Основная цель статьи - представить базовую идею традиционных, обычно используемых алгоритмов кластеризации, проанализировать преимущества и недостатки каждого из них. Представить полный список всех существующих алгоритмов кластеризации из-за разнообразия подходов, информации, пересечения областей исследований достаточно сложно. Таким образом, предлагаются 9 классификационных категорий широко используемых алгоритмов кластеризации, имеющих высокую практическую ценность и хорошо изученных, так же один или несколько типичных для каждой категории алгоритмов подробно обсуждаются, чтобы дать систематическое и четкое представление о методе анализа важных данных. Проделанный анализ позволяет легко выбрать подходящую группу алгоритмов исходя из технической задачи. Возможности кластерных алгоритмов позволяют разрабатывать более детальные математические модели для диагностики и проведения вычислительного эксперимента по выявлению диагностических показателей.

В данной статье рассматриваются именно традиционные алгоритмы, во второй части предполагается подробно рассмотреть современные алгоритмы кластеризации.

Библиографические ссылки

1. Козлова О. А., Попова Ю. Б., Шестопалов М. Ю. Диагностика технических объектов на основе методов кластеризации информации : учеб. пособие. СПб., 2009. 114 с.

2. Гитис Л. Х. Статистическая классификация и кластерный анализ. М.: Изд-во МГГУ, 2003. 157 с.

3. Xu R., Wunsch D. Survey of clustering algorithms // IEEE Transactions on Neural Networks and Learning Systems. 2005. P. 645-678.

4. On using class-labels in evaluation of clusterings // MultiClust: 1st international workshop on discovering, summarizing and using multiple clusterings held in conjunction with KDD / Fдrber I., Gьnnemann S., Kriegel H., Krцger P., Mьller E., Schubert E., Seidl T., Zimek A. Washington, DC, 2010.

5. Velmurugan T., Santhanam T. A survey of partition based clustering algorithms in data mining: an experimental approach // Journal of Information Technology. 2011. № 10. P. 478-484.

6. Carlsson G., Mйmoli F. Characterization, stability and convergence of hierarchical clustering methods // Journal of Machine Learning Research. 2010. № 11. P. 14251470.

7. Hцppner F. Fuzzy cluster analysis: methods for classification, data analysis and image recognition. Wiley, Hoboken, 1999.

8. Clustering uncertain data based on probability distribution similarity / Jiang B., Pei J., Tao .Y, Lin X. // IEEE Transactions on Knowledge and Data Engineering. 2013. № 25. P. 751-763.

9. A local-density based spatial clustering algorithm with noise / Duan L., Xu L., Guo F., Lee J., Yan B. // Information Systems. 2007. № 32. P. 978-986.

10.Sheikholeslami G., Chatterjee S., Zhang A. Wavecluster: A multi-resolution clustering approach for very large spatial databases // VLDB. 1998. P. 428-439.