Обсуждение популярных типов кластеризации

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

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

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

Как начать работу с кластеризацией в Python

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

Кластеризация набора данных

С помощью scikit-learn можно создавать различные наборы данных. Например, вы можете использовать библиотеку для создания набора данных кластеризации. Это можно сделать с помощью функции make_blobs. Он принимает следующие параметры:

  • Размер образца
  • Количество центров
  • Стандартное отклонение каждого кластера
  • Количество функций
#Using make_blobs function to generate a clustering dataset
from sklearn.datasets.samples_generator import make_blobs 
X, y_true = make_blobs(n_samples=400, centers=3, cluster_std=0.50, random_state=3)

Кластеризацию можно продемонстрировать с помощью сгенерированного набора данных. Если вы хотите визуализировать приведенные выше данные, вы можете использовать Matplotlib.

#Visualizing the dataset
plt.figure(figsize=(10,7)) plt.scatter(X[:, 0], X[:, 1], s=30);

Что такое алгоритмы кластеризации?

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

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

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

Ниже приведены типичные кластерные модели:

  • Модели подключения — основаны на дистанционном подключении, таком как иерархическая кластеризация.
  • Центроидальные модели.Эти модели представляют каждый кластер в виде одного среднего вектора, например, кластеризация K-средних.
  • Модели распределения. В этих типах моделей статистические распределения используются для моделирования кластеров.
  • Модели плотности. Эти модели определяют кластеризацию как связанную плотную область в пространстве данных, например DBSCAN и OPTICS.
  • Групповые модели — эти модели не дают уточненных результатов. Их единственная цель — группировать данные.
  • Модели на основе графа. Когда ребра соединяют каждые два узла в подмножестве графа, это подмножество можно считать прототипом кластера.
  • Нейронные модели. Самоорганизующиеся карты — одна из самых популярных неконтролируемых нейронных сетей (НС), и они аналогичны моделям, описанным выше.

Давайте теперь обратим наше внимание на различные алгоритмы кластеризации.

Типы алгоритмов кластеризации

В этом разделе мы рассмотрим, как выбрать алгоритмы кластеризации в зависимости от вашего варианта использования.

Алгоритмы иерархической кластеризации

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

  • В этом алгоритме кластеры формируются путем соединения «объектов» вместе на основе их расстояния.
  • Можно определить кластер на основе максимального расстояния между его частями.
  • При иерархической кластеризации дендрограммы представляют разные кластеры, расположенные на разных расстояниях, откуда и произошло название «иерархическая кластеризация». Эти алгоритмы создают иерархию кластеров, которые объединяются на определенном расстоянии.
  • Ось Y на дендрограмме отмечает расстояние между кластерами. Чтобы предотвратить смешивание кластеров, объекты располагаются вдоль оси x.

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

  1. Агломеративный — он начинается с отдельного компонента, а затем группирует его в единый кластер.
  2. Разделение — с самого начала разделяет набор данных на разделы.

Агломеративная иерархическая кластеризация (AHC)

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

  1. Мы рассматриваем каждую точку данных как кластер. В начале есть K кластеров. Кроме того, в начале будет K точек данных.
  2. В рамках этого шага мы объединим две ближайшие точки данных, чтобы сформировать гигантский кластер. В результате получится кластер К-1.
  3. Чтобы сформировать больше кластеров, необходимо объединить два ближайших кластера. Всего будет создано кластеров K-2.
  4. Пока K не достигнет нуля, повторяйте три вышеуказанных шага, чтобы сформировать один большой кластер. Для присоединения к кластеру больше не требуется никаких данных.
  5. В конце концов, мы могли бы использовать дендрограммы для разделения кластеров на несколько кластеров в зависимости от варианта использования.

На этом изображении показано, как работает иерархическая кластеризация.

Преимущества AHC:

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

Следующие недостатки AHC:

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

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

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

Алгоритмы кластеризации на основе Centroid или Partitioning

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

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

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

Алгоритм кластеризации K-средних

Алгоритм K-средних делит набор данных на заранее определенное (K) количество кластеров на основе определенной метрики расстояния. Одним из наиболее распространенных алгоритмов кластеризации является метод K-средних. Алгоритм основан на центроиде и является простейшим алгоритмом обучения без учителя. Центроиды - это центры кластеров и групп.

Алгоритм K-средних работает следующим образом:

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

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

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

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

DBSCAN

DBSCAN (Пространственная кластеризация приложений с шумом на основе плотности) — самый популярный метод кластеризации на основе плотности. Кроме того, он включает в себя четко определенную модель кластеризации, известную как «достижимость по плотности».

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

На рисунке выше ядро ​​— это точка, которая имеет несколько (m) точек на определенном (n) расстоянии. Граница — это точка, которая имеет хотя бы одну центральную точку на расстоянии n от нее. Шум не является ни границей, ни ядром.

Для определения кластеров DBSCAN использует два параметра:

  • minPts
  • прибыль на акцию

Вот как работает алгоритм DBSCAN:

  1. Алгоритм DBSCAN начинается со случайно выбранной точки данных (непосещенные точки).
  2. Окрестность этой точки извлекается с использованием расстояния эпсилон ε.
  3. Когда в этой области достаточно точек данных, начинается кластеризация, и текущая точка добавляется в новый кластер или помечается как шумовая и посещаемая.
  4. Для первой точки в новом кластере точка в пределах ее окрестности расстояния ε эпсилон также принадлежит тому же кластеру. Процедура включения всех новых точек данных в один и тот же кластер выше должна быть повторена для всех новых точек данных, добавленных в вышеуказанный кластер.
  5. Все точки кластера определяются путем повторения двух предыдущих шагов. Все точки в окрестности ε кластера были исследованы и помечены. Когда текущий кластер завершен, мы извлекаем новую непосещенную точку и обрабатываем ее, что приводит к обнаружению нового кластера. Повторяйте процедуру, пока не будут посещены все точки данных.

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

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

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

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

Смешанная модель Гаусса

Одним из типов кластеризации на основе распределения является смешанная модель Гаусса (GMM). В этих подходах к кластеризации предполагается, что данные состоят из распределений, таких как распределения Гаусса. Алгоритмы на основе распределения объединяют данные в три распределения Гаусса, как показано на рисунке ниже. Вероятность того, что точка принадлежит распределению, уменьшается по мере удаления от распределения.

Так же, как K-Means, GMM можно использовать для поиска кластеров. По мере удаления от распределительного центра вероятность того, что точка принадлежит распределительному центру, уменьшается. На изображении ниже полосы показывают уменьшение вероятности. Мы также можем найти вероятностное назначение кластера с помощью GMM, поскольку он содержит вероятностную модель.

Вот как GMM присваивает вероятности точкам данных:

В GM есть несколько гауссианов, каждый из которых идентифицируется как k ∈ {1,…,K}, где K — количество кластеров в GM. Ниже приведены параметры каждого гауссова K в смеси:

  • Среднее значение (μ): определяет его центр
  • Ковариация (Σ): определяет его ширину
  • Вероятность смешивания: предсказывает размер функции Гаусса.

Ниже приведено изображение, показывающее эти параметры:

Заключение

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

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

Следите за обновлениями!

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

Независимая от редакции, Heartbeat спонсируется и публикуется Comet, платформой MLOps, которая позволяет специалистам по данным и командам машинного обучения отслеживать, сравнивать, объяснять и оптимизировать свои эксперименты. Мы платим нашим авторам и не продаем рекламу.

Если вы хотите внести свой вклад, перейдите к нашему призыву к участию. Вы также можете подписаться на получение нашего еженедельного информационного бюллетеня (Еженедельник глубокого обучения), заглянуть в блог Comet, присоединиться к нам в Slack и подписаться на Comet в Twitter и LinkedIn для получения ресурсов и событий. и многое другое, что поможет вам быстрее создавать более качественные модели машинного обучения.