Обзор алгоритмов агломерации и разделения кластеризации и их реализации

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

Что такое кластеризация?

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

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

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

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



Понимание алгоритмов кластеризации K-средних, K-средних ++ и K-medoids
Ознакомьтесь с обзором алгоритмов кластеризации K-средних, K-средних ++ и K-Medoids, а также их отношения. Эта статья… todatascience.com



В этой статье вы сможете разобраться в иерархической кластеризации, ее типах.

Существует два типа методов иерархической кластеризации:

  1. Разделительная кластеризация
  2. Агломеративная кластеризация

Разделительная кластеризация:

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

Шаги разделяющей кластеризации:

  1. Изначально все точки в наборе данных принадлежат одному кластеру.
  2. Разделите кластер на два наименее похожих кластера.
  3. Продолжайте рекурсивно, чтобы сформировать новые кластеры, пока не будет получено желаемое количество кластеров.

В приведенном выше наборе данных видно, что есть 3 кластера, которые находятся далеко друг от друга. Итак, мы остановились после получения 3 кластеров.

Даже если начать разделять еще больше кластеров, ниже будет полученный результат.

Как выбрать, какой кластер разбить?

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

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

Как разбить выбранный кластер?

Как только мы решили, какой кластер разбить, возникает вопрос, как разбить выбранный кластер на 2 кластера. Один из способов - использовать критерий Уорда, чтобы добиться наибольшего сокращения разницы в критерии SSE в результате разделения.

Как справиться с шумом или выбросом?

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

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

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

Этапы агломеративной кластеризации:

  1. Изначально все точки данных представляют собой отдельный кластер.
  2. Возьмите два ближайших кластера и объедините их в один кластер.
  3. Повторяйте шаг 2 рекурсивно, пока не получите желаемое количество кластеров.

В приведенном выше наборе данных видно, что 2 кластера находятся далеко друг от друга. Итак, мы остановились после получения 2 кластеров.

Как объединить два кластера в один кластер?

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

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

  • Расстояние между двумя ближайшими точками в двух кластерах.
  • Расстояние между двумя самыми дальними точками в двух кластерах.
  • Среднее расстояние между всеми точками в двух кластерах.
  • Расстояние между центроидами двух кластеров.

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

Выполнение:

Вывод:

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

Спасибо за чтение