Осняч Е. А., д.т.н., профессор Мещеряков Л. И.

Национальный горный университет, Украина

Классификация и сравнение алгоритмов кластерного анализа

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

Основные понятия

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

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

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

 

 

 

 

 

 

 

 

 

 

Рис. 1.  Сравнение задач классификации и кластеризации

Формальная постановка задачи

Пусть  - множество объектов,  - множество номеров (имён, меток) кластеров. Задана функция расстояния между объектами . Имеется конечная обучающая выборка объектов . Требуется разбить выборку на непересекающиеся подмножества, называемые кластерами, так, чтобы каждый кластер состоял из объектов, близких по метрике  , а объекты разных кластеров существенно отличались. При этом каждому объекту приписывается номер кластера  .

Алгоритм кластеризации – это функция , которая любому объекту ставит в соответствие номер кластера . Множество в некоторых случаях известно заранее, однако чаще ставится задача определить оптимальное число кластеров, с точки зрения того или иного критерия качества кластеризации.

Процесс кластерного анализа

Процесс кластерного анализа можно разделить на следующие основные этапы:

1.       Отбор выборки объектов для кластеризации.

2.       Определение признаков, по которым будут оцениваться объекты в выборке.

3.       Нормирование значений признаков (при необходимости).

4.       Выбор меры близости и вычисление ее значений между объектами.

5.       Выбор алгоритма и применение кластерного анализа для создания групп сходных объектов (кластеров).

6.       Представление и интерпретация полученных результатов.

7.       Проверка достоверности результатов кластерного решения.

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

Основные методы кластеризации

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

1.     По способу обработки данных: иерархические и неиерархические.

2.     По способу анализа данных: четкие и нечеткие.

При иерархической кластеризации выполняется не просто разбиение на классы, а иерархия разбиений, т.е. последовательное объединение меньших кластеров в большие или разделение больших кластеров на меньшие. Результатом, как правило, является дендрограмма (рис. 2) – схема, показывающая, в какой последовательности происходило слияние объектов в кластер/разделение объектов на кластеры. На основе полученной в результате работы алгоритма дендрограммы пользователь может сам выбрать желаемое разбиение.

 

 

 

Рис. 2. Пример дендрограммы

Неиерархические алгоритмы, напротив, в результате работы выдают некоторое конкретное разбиение и имеют ряд параметров, позволяющих настраивать алгоритм для имеющихся данных.

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

Иерархические алгоритмы

Иерархические алгоритмы делятся на агломеративные и дивизимные [4].

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

Среди алгоритмов кластеризации, относящихся к данному типу, можно выделить следующие: CURE, ROCK, CHAMELEON и др.

CURE (Clustering Using Representatives). Данный алгоритм выполняет иерархическую кластеризацию с использованием набора определяющих точек для определения объекта в кластер.

Назначение: кластеризация очень больших наборов числовых данных.

Ограничения: является эффективным для данных низкой размерности, работает только на числовых данных.

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

Недостатки: есть необходимость в задании пороговых значений.

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

Среди алгоритмов кластеризации, относящихся к данному типу, можно выделить следующие: BIRCH, MST и др.

BIRCH (Balanced Iterative Reducing and Clustering using Hierarchies). В этом алгоритме предусмотрен двухэтапный процесс кластеризации.

Назначение: кластеризация очень больших наборов числовых данных.

Ограничения: работа с только числовыми данными.

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

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

MST (Algorithm based on Minimum Spanning Trees). Алгоритм минимального покрывающего дерева сначала строит на графе минимальное покрывающее дерево, а затем последовательно удаляет ребра с наибольшим весом.

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

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

Неиерархические алгоритмы

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

К неиерархическим алгоритмам кластеризации относятся алгоритмы k-means (а также его вариации – k-means++ и k-medians), PAM, CLOPE и др.

k-means. Алгоритм k-means строит k кластеров, расположенных на возможно больших расстояниях друг от друга. Основной тип задач, которые решает алгоритм k-средних, - наличие предположений (гипотез) относительно числа кластеров, при этом они должны быть различны настолько, насколько это возможно. Выбор числа k может базироваться на результатах предшествующих исследований, теоретических соображениях или интуиции [3].

Ограничения: небольшой объем данных.

Достоинства: простота использования; быстрота использования; понятность и прозрачность алгоритма.

Качество результата сильно зависит от выбора начального разбиения; медленная работа на больших базах данных; необходимо задавать количество кластеров.

PAM (Partitioning Around Medoids). Этот  алгоритм  аналогичен  алгоритму k-средних, только  при  работе  алгоритма  перераспределяются  объекты  относительно  медианы  кластера,  а  не  его центра.

Ограничения: небольшой объем данных.

Достоинства: простота использования; быстрота использования; понятность и прозрачность алгоритма, алгоритм менее чувствителен к выбросам в сравнении с k-means.

Недостатки: необходимо задавать количество кластеров; медленная работа на больших базах данных.

Fuzzy C-means. Является нечетким алгоритмом кластеризации.

Назначение: кластеризация больших наборов числовых данных.

Достоинства: нечеткость при определении объекта в кластер позволяет определять объекты, которые находятся на границе, в кластеры.

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

Вывод

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

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

Список литературы

1.     Кластерный анализ. Википедия [Электронный ресурс]. Режим доступа:

http://ru.wikipedia.org/wiki/Кластерный_анализ

2.       Технологии анализа данных: Data Mining, Visual Mining, Text Mining, OLAP / А. А. Берсегян, М. С. Куприянов, В. В. Степаненко, И. И. Холод. – 2-е изд., перераб. и  доп. – СПб.: БХВ-Петербург, 2007. – 384с.

3.       Data Mining. Учебное пособие / И. А. Чубукова – М.: Интернет-Университет Информационных технологий; БИНОМ. Лаборатория знаний, 2006. – 382 с.

4.       Кластеризация. Типы алгоритмов [Электронный ресурс]. Режим доступа:

http://wiki.auditory.ru/Лекция_8_-_Кластеризация._Типы_алгоритмов

5.       Классификация и сравнение методов кластеризации / И. М. Нейский [Электронный ресурс]. Режим доступа:

http://it-claim.ru/Persons/Neyskiy/Article2_Neiskiy.pdf