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

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

Давыдов О.А. - ст. преподаватель каф.

«Автоматика и системотехника», (ТОГУ)

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

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

Title: Analysis of Existing Clustering Algorithms (Part 1)

Davydov O. A. - Pacific National University, Khabarovsk, Russian Federation

Abstract: The paper provides an overview of existing approaches to solving cluster analysis problems. We consider the traditional development in the field of cluster analysis. The given paper provides a definition of clustering, discusses the main elements involved in the clustering process, such as measurement indicators and estimates of distance or similarity, and analyzes traditional clustering algorithms. All clustering algorithms considered are compared and reviewed in detail. The evaluation indicators for the result of clustering are listed in the first section, the traditional clustering algorithms in the second section, and the final conclusion made in the third section.

Keywords: cluster, clustering algorithm, diagnostics, malfunction, fuzzy analysis, cluster analysis, graph theory, computational complexity.

Введение

Кластерный анализ - это общее название множества вычислительных процедур, используемых при создании классификации. Кластерный метод - это многомерная статистическая процедура, выполняющая сбор данных, содержащих информацию о выборке объектов, и затем упорядочивающая объекты в сравнительно однородные группы [1]. Кластеризация отличается от классификации тем, что для проведения анализа не требуется иметь выделенную зависимую переменную. Такая задача решается на начальных этапах исследования, когда данные четко не систематизированы, не выделены конкретные диагностические показатели и т.д.

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

Кластерный анализ позволяет рассматривать, сокращать и сжимать в более компактные массивы большие объемы информации, что актуально для проблемы диагностики технических объектов.

Задача кластеризации заключается в следующем [2]: имеется обучающее множество и функция расстояния между объектами. Требуется разбить множество на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из объектов, близких по расстоянию, а объекты разных кластеров существенно отличались. Алгоритм кластеризации -- это функция, которая любому объекту ставит в соответствие метку определенного кластера.

1. Оценка алгоритмов

Расстояние и сходство - основа для построения алгоритмов кластеризации. Что касается количественных характеристик данных, расстояние предпочтительнее для распознавания взаимосвязи между данными, в то время как сходство предпочтительнее при работе с качественными характеристиками данных [3].

Часто используемые функции вычисления расстояния (стандартизированная евклидова, по функции косинуса, корреляционная Пирсона, Махаланобиса и др.). Часто используемые функции подобия для качественных данных (Хэмминга, квадрат евклидова расстояния, Чебышева, Манхэттенское и др.).

Основная цель индикатора оценки - проверить правильность алгоритма. Индикаторы оценки можно разделить на две категории: индикаторы внутренней оценки и индикаторы внешней оценки с точки зрения тестовых данных, находящихся в процессе построения алгоритма кластеризации.

Внутренняя оценка использует внутренние данные для проверки правильности работы алгоритма. Существует три наиболее часто используемых внутренних показателя (индекс Дэвиса - Болдина (DBI), индекс Данна (DI), коэффициент силуэта) [4].

Внешняя оценка использует внешние данные для проверки правильности работы алгоритма. Существует шесть наиболее часто используемых показателей внешней оценки (индекс Rand (RI), F, Жаккара (JI), Фоулкса - Мэллова (FM), энтропия, отклонение в информации (VI)) [4].

Примем следующее обозначения при анализе вычислительной сложности, n - количество общих объектов, точек данных; k - количество кластеров; s - количество выборочных объектов; t - количество итераций.

2. Традиционные алгоритмы

Традиционные алгоритмы кластеризации можно разделить на 9 категорий, обобщенных в табл. 1.

Таблица 1 Традиционные алгоритмы

3. Алгоритм кластеризации на основе разделения

Основная идея такого рода алгоритмов кластеризации состоит в том, чтобы рассматривать центр точек данных как центр соответствующего кластера. K-средних и K-медоидов являются двумя наиболее известными алгоритмами кластеризации такого типа. Основная идея K -средних состоит в том, чтобы обновить центр кластера, который представлен центром точек данных, путем итерационных вычислений. Итерационный процесс будет продолжаться до тех пор, пока не будут выполнены некоторые критерии сходимости. K- медоидов - это усовершенствование K-средних для работы с дискретными данными, в котором точка данных, наиболее близкая к центру точек данных, является представителем соответствующего кластера. Типичные алгоритмы кластеризации на основе разбиения также включают PAM, CLARA, CLARANS.

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

Анализ:

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

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

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

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

4. Иерархические алгоритмы кластеризации

Основная идея такого рода алгоритмов кластеризации заключается в построении иерархических отношений между данными для кластеризации. Предположим, что каждая точка данных вначале обозначает отдельный кластер, а затем два соседних кластера объединяются в новый кластер, пока не останется только один кластер. Типичные алгоритмы такого рода кластеризации включают BIRCH, CURE, ROCK, Chameleon. BIRCH (Сбалансированное итеративное сокращение и кластеризация с помощью иерархий) реализует результат кластеризации, создавая CF-дерево (сбалансированное дерево с двумя параметрами), один узел которого обозначает подкластер. CF -дерево будет динамически расти при появлении новой точки данных. CURE (кластеризация с использованием представителей), подходящий для кластеризации больших баз данных, использует метод случайной выборки, чтобы кластери- зировать выборку отдельно и, наконец, интегрировать результаты. ROCK - это улучшение CURE для работы с данными перечислимого типа, которое учитывает сходство данных вокруг кластера. Chameleon сначала делит исходные данные на кластеры меньшего размера на основе графа ближайшего соседа, а затем кластеры меньшего размера объединяются в кластер большего размера на основе агломеративного алгоритма до тех пор, пока не будут уд о- влетворять условиям.

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

Анализ:

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

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

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

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

5. Нечеткие алгоритмы кластеризации

Основная идея этого типа алгоритмов кластеризации заключается в том, что дискретное значение метки принадлежности {0, 1} заменяется на непрерывный интервал [0, 1], чтобы более разумно описать отношение принадлежности между объектами. Типичные алгоритмы такого рода кластеризации включают FCM, FCS и MM. Основная идея FCM состоит в том, чтобы каждая точка данных принадлежала каждому кластеру путем оптимизации функции объекта. FCS, в отличие от традиционных алгоритмов нечеткой кластеризации, использует многомерную гиперсферу в качестве прототипа каждого кластера. MM используется для нахождения центра кластера.

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

Анализ:

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

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

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

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

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

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

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

Анализ:

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

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

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

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

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

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

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

Анализ:

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

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

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

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