Сравнительный анализ методов кластеризации: k-means, иерархический и DBSCAN

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

Кластеризация это…

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

Кластеризация — процесс разделения какого-либо числа объектов на подмножества (кластеры) по определенному критерию.

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

Среди основных методов кластеризации называются следующие:

• Иерархическая, предполагающая выстраивание дерева кластера, визуализируется с помощью дендрограммы.
• Разновидности:
• Агломеративная, предполагающая объединение объектов, являющихся единичными кластерами, в общий (снизу вверх).
• Дивизионная, в рамках которой общий кластер подразделяется на множество единичных (сверху вниз).
• Метод k-средних, для работы с которым изначально обязательно обозначение установленной численности кластеров k.
• Принцип метода базируется на минимизации суммы квадратов расстояний, разделяющих точки и центры групп.
• Привлекателен быстротой реализации, но проблематичность проявляется в процессе подготовки и конфигурации групп.
• Метод DBSCAN базируется на понятии плотности, то есть кластеры представляются в пространстве областями определенной плотности.
• Специфика метода заключается в отсутствии необходимости преждевременного определения обязательной численности кластеров.
• Конфигурация кластеров не имеет значения, в рамках метода выбросы классифицируются информационным «шумом».

Метрика расстояния

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

Среди популярных называются:

• Евклидово расстояние – прямая линия, объединяющая точки с координатами x и y.
• Манхэттенское расстояние или расстояние городских кварталов – измерение промежутка, разделяющего две точки, представляется ломаными линиями; для расчёта требуется узнать сумму абсолютных разностей между координатами x и y.
• Косинусное расстояние иди близость представляется мерой, ориентированной на сопоставление двух векторов в многомерном пространстве.
• И т.п.

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

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

Метод k-means: общие характеристики

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

Алгоритм k-means ориентирован на распределение объектов в кластеры. Основание для группировки – схожие характеристики.

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

Характеристика метода

Для начала определимся с целями кластеризации и выяснить, что целью метода k-means является процесс разделения множества (n) объектов на кластеры (k) так, чтобы в одном кластере сосредотачивались элементы с максимальными показателями схожести. При этом между группами должна прослеживаться тенденция к предельным показателям несходства.

Алгоритм

Рассмотрим алгоритм метода k-means, который представляется определенной последовательностью действий:

1. Определения численности групп. На этом этапе исследователь заранее назначает необходимое число кластеров.
2. Установка центроидов. Центры кластеров выбираются посредством рандомного выбора в информационном пространстве k-точек.
3. Назначение элементов групп. Процесс присвоения абсолютно всех информационных точек центрам кластеров, расположенных к точке ближе всего. Традиционным инструментом в этом случае выступает метрика евклидова расстояния.
4. Пересчет центров кластеров. Процесс сопровождается расчетом среднего значения всех точек для каждой группы. Итоговый показатель становится новым центром кластера.
5. Дублирование процессов, обозначенных в предыдущих двух пунктах необходимо для того, чтобы прийти к ситуации, в которой изменения кластеров станут невозможными или их преобразования будут несущественными.

Еще необходимо отметить положительные и отрицательные стороны этого метода.

Плюсы

В перечне преимуществ рассматриваемого метода необходимо отметить:

• Легкость реализации.
• Способность обрабатывать значительные массивы данных за достаточно короткий срок.
• Интуитивно-понятное объяснение итогов.
• Максимальная эффективность проявляется при сферической форме кластеров.

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

Минусы

В перечень недостатков отнесены следующие аспекты:

• Отсутствует неуязвимость к выбросам, которые негативно влияют на реальное положение центров.
• Обязательно предварительное обозначение количества кластеров. При отсутствии верного подхода к выбору k, качество процесса кластеризации снижается.
• Чувствителен к настройкам. Если начальные центры различны, то и результаты получаются идентичными.
• Дает сбой, если плотность кластеров неоднородна. Для работы метода требуется придерживаться приблизительно одинаковой величины групп.

Применение

Остановимся на вопросе того, в каких случаях можно применять метод k-means. Кластеризация по методу k-means уместна тогда, когда:

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

Теперь рассмотрим, что из себя представляет иерархический метод кластеризации.

Иерархический метод: метод многомерного анализа

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

Дерево кластеров допускает возможность урезания веток для того, чтобы численность кластеров совпадала с нужным. Метод эффективен в случаях отсутствия определенности в вопросе структуры данных. Исследователь, используя метод k-means, должен, при выяснении численности групп, руководствоваться критериями адаптивности.

Базовые характеристики метода

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

Алгоритм

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

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

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

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

• Ближний сосед определяет незначительную дистанция между единицами кластера.
• Дальний сосед определяет максимальную дальность.
• Средняя связь определяет средний интервал между парами.
• Метод Уорда раскрывает показатели роста рассеивания внутри кластера в процессе группировки.

Рассмотрим положительные и отрицательные стороны иерархического метода группировки.

Плюсы

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

Недостатки

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

Остался рассмотреть еще один метод кластеризации.

Метод DBSCAN – эффективный алгоритмом кластеризации

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

Принцип работы

Метод DBSCAN может определять группы объектов, для которых характерно уплотненное расположение. Затем следует процесс разделения областей с плотной и низкой плотностью. Привлекательная характеристика – отсутствие необходимости предварительного определения численности групп.

Алгоритм для DBSCAN

Существует определенный порядок действия для использования DBSCAN как метода кластеризации:

1. Параметры. Для работы DBSCAN требуется определить два показателя, которыми являются:

• ε (эпсилон) – критерий, отражающий радиус окрестности;
• MinPts – показатель самой малой численности точек в определенной окрестности, которые требуются для создания «ядра» кластера.

1. Активированный процесс ориентирован на выявление областей с значительными показателями плотности:

• В этой области любая точка может стать ядром кластера, если в радиусе ε от нее обнаруживается достаточная численность соседей.
• Точки, расположенные возле ядра кластера, автоматически к нему присоединяются.
• Если обнаруживаются точки, не принадлежащие не одному кластеру, то эти точки автоматически переходят в разряд «шума».

1. Важно, что алгоритм DBSCAN может обнаруживать группы вне зависимости от их форм.

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

Стоит обозначить положительные стороны метода DBSCAN, которые проявляются в следующих аспектах:

• Отсутствие необходимости преждевременного обозначения определенной численности групп.
• Сложность форм не мешает определению естественных групп.
• Проявляет стабильность в работе при существенных выбросах или шуме.
• Является отличным инструментом анализа в самых разных исследованиях.

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

Сравнительный анализ

И, для начала, сведем в таблицу определения методов.

Метод	Характеристика
Метод k-means	Процесс разделения множества (n) объектов на кластеры (k). В одном кластере элементы со схожими показателями. Группы разделяют показатели несхожести.
Иерархический метод	Выстраивание иерархической структуры групп в форме дерева. В основу кластеризации закладываются один из двух подходов: агломеративный (от мелкого к крупному) или дивизионный (от крупного к мелкому).
Метод DBSCAN	Алгоритм формирования групп в соответствии с плотностью информации. Форма кластеров может быть любой. Расчетам не мешают шум и выбросы.

На втором этапе сравним базовые показатели и условия функционирования.

Критерий	Метод k-means	Иерархический метод	Метод DBSCAN
Численность групп	k определяется предварительно	Определяется по итогу обработки древовидной диаграммы	Отсутствует необходимость
Конфигурация группы	Сферические	Свободная	Свободная
Чувствительность к выбросам	Значительная	Умеренная	Низкая (в расчеты не принимаются, отбрасываются)
Расширение/сужение пространства, влияние	Сильно влияет	Влияет	Влияет
Степень устойчивости к шуму	Неустойчив	Средняя	Хорошая
Визуализация информационной структуры	Отсутствует	Дендрограмма	Отсутствует

Есть еще несколько параметров, которые необходимо сравнить. Внимание стоит уделить критерию сложности. Вырисовывается следующая картина:

• Метод k-means демонстрирует:
• Низкую сложность реализации;
• Вычисления производятся быстро при соблюдении условия наличия умеренных показателей числа кластеров и размеров пространства.
• Иерархический метод:
• Демонстрирует гибкость при наличии сложностей настройки.
• Реализация характеризуется средней сложностью.
• Вычислительная сложность определяется методом реализации. Особое условие – применение для небольшого объема информации.
• Метод DBSCAN:
• Базовый критерий – плотность сгруппированных объектов.
• Сложность реализации – средняя.
• Обработка больших объемов данных проводится быстрее в иерархическом и медленнее чем в k-means методах.

Представим в табличном варианте информацию, отражающую положительные и отрицательные стороны сравниваемых методов.

Метод	Положительные стороны	Отрицательные проявления
Метод k-means	Несложный, быстрый, без трудностей изменяет масштаб	Обрабатывает только кластеры сферической формой, проявляет высокие показатели чувствительности к двум параметрам – выбросы, инициализация центров
Иерархический метод	Отображение структуры, численность кластеров заранее не выбирается.	Трудности с изменением масштаба, перезапуск алгоритма не помогает с процессом «переобучения».
Метод DBSCAN	Выбросы не мешают, работает с кластерами любой конфигурации.	Трудности с определением параметров, трудности в работе с кластерами, в которых плотность неустойчивая.

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

Метод k-means будет из имеющихся точек формировать сферические кластеры, которые не смогут совпадать с изначальной формой групп. А группа, представленная в форме дуги, может быть разделена неестественным образом.

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

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

Остался еще вопрос применения методов. Рассмотрим этот критерий в материале, представленном в таблице ниже.

Условие/цель	Предпочтительно выбрать
При известном k требуется разделение информации в короткий срок и без сложностей	Метод k-means
Небольшой объем данных, обязательно представление и архитектоника	Иерархический метод
Отсутствует информация о k, сложная конфигурация кластеров, присутствие шума	Метод DBSCAN
Наличие плотных зон, значительная численность выбросов	Метод DBSCAN
Необходимость проведения анализа информации при отсутствии первоначальных гипотез о кластерах	Иерархический метод или Метод DBSCAN

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