Осняч Е. А.,
д.т.н., профессор Мещеряков Л. И.
Национальный
горный университет, Украина
Классификация и сравнение алгоритмов кластерного
анализа
В наше время в связи со стремительным
развитием науки, техники, информационных технологий, особое значение имеет
представление, структурирование и анализ огромных массивов информации, которые
составляют основу функционирования и развития современного общества. Для этого
требуются универсальные и надежные подходы, пригодные для обработки информации
из различных областей. В качестве одного из таких подходов может быть
использован кластерный анализ.
Основные понятия
Кластерный анализ – это задача разбиения заданной выборки объектов на подмножества,
называемые кластерами, так, чтобы каждый кластер состоял из схожих объектов,
а объекты разных кластеров существенно отличались [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.
Кластеризация. Типы алгоритмов [Электронный ресурс]. Режим доступа:
5.
Классификация и сравнение методов кластеризации / И. М. Нейский [Электронный ресурс]. Режим доступа:
http://it-claim.ru/Persons/Neyskiy/Article2_Neiskiy.pdf