Теоретическое объяснение и пример scikit learn

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

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

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

Иерархическая кластеризация означает создание дерева кластеров путем итеративной группировки или разделения точек данных. Существует два типа иерархической кластеризации:

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

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

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

У нас есть набор данных, состоящий из 9 образцов. Я выбираю числа, связанные с этими образцами, чтобы продемонстрировать концепцию сходства. На каждой итерации (или уровне) самые близкие числа (т. Е. Выборки) объединяются. Как вы можете видеть на рисунке ниже, мы начинаем с 9 кластеров. Ближайшие объединяются на первом уровне, а затем у нас 7 кластеров. Количество черных линий, пересекающихся с синими линиями, представляет количество кластеров.

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

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

Это очень простой набор данных для иллюстрации цели, но наборы данных из реальной жизни, очевидно, более сложны. Мы упоминаем, что ближайшие точки данных (или кластеры) объединяются вместе. Но как алгоритмы выявляют самые близкие? В scikit-learn реализовано 4 различных метода для измерения сходства:

  1. Связь Уорда: сводит к минимуму разброс объединяемых кластеров. Наименьшее увеличение общей дисперсии вокруг центроидов кластера.
  2. Средняя связь: среднее расстояние до каждой точки данных в двух кластерах.
  3. Полная (максимальная) связь: максимальное расстояние между всеми точками данных в двух кластерах.
  4. Одиночная (минимальная) связь: максимальное расстояние между всеми точками данных в двух кластерах.

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

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

  • Остановить после достижения определенного количества кластеров (n_clusters)
  • Установите пороговое значение для связи (distance_threshold). Если расстояние между двумя кластерами превышает пороговое значение, эти кластеры не будут объединены.

Разделяющая кластеризация

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

Плюсы и минусы

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

Плюсы

  • Необязательно заранее указывать количество кластеров. Для алгоритма k-средних необходимо указать количество кластеров.
  • Это легко реализовать и интерпретировать с помощью дендрограмм.
  • Всегда генерирует одни и те же кластеры. Кластеризация K-средних может привести к различным кластерам в зависимости от того, как инициируются центроиды (центр кластера).

Минусы

  • Это более медленный алгоритм по сравнению с k-средними. Иерархическая кластеризация занимает много времени, особенно для больших наборов данных.

Приложения для иерархической кластеризации

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

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

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

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

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

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

  • Еще один распространенный вариант использования иерархической кластеризации - анализ социальных сетей.
  • Иерархическая кластеризация также используется для обнаружения выбросов.

Реализация Scikit Learn

Я буду использовать набор данных iris, который доступен в модуле наборов данных scikit learn. Начнем с импорта набора данных:

import pandas as pd
import numpy as np
from sklearn.datasets import load_iris
iris = load_iris()
X = iris.data

Набор данных Iris включает 150 точек данных. Я буду использовать только первые 50 точек данных, чтобы дендрограмма казалась более четкой.

X = X[:50, :]
X.shape
(50, 4)

Затем мы импортируем класс AgglomerativeClustering и строим модель.

from sklearn.cluster import AgglomerativeClustering
model = AgglomerativeClustering(distance_threshold=0, n_clusters=None)

Имейте в виду, что если параметр distance_threshold не равен None, параметр n_cluster должен иметь значение None. Я не ставлю никаких условий только для того, чтобы визуализировать полное дерево.

Следующим шагом будет подгонка модели к данным:

model = model.fit(X)

Перед тем, как нарисовать дендрограмму, мы можем проверить детали нашей модели, используя доступные методы:

# Number of clusters
model.n_clusters_
50
# Distances between clusters
distances = model.distances_
distances.min()
0.09999999999999964
distances.max()
3.828052620290243

Scikit learn не предоставляет дендрограммы, поэтому мы будем использовать дендрограмму пакета SciPy.

from scipy.cluster.hierarchy import dendrogram
from scipy.cluster import hierarchy

Сначала мы создаем матрицу связей:

Z = hierarchy.linkage(model.children_, 'ward')

Мы используем потомков из модели и критерий связи, который я выбираю как «опекаемую» связь.

plt.figure(figsize=(20,10))
dn = hierarchy.dendrogram(Z)

Метки на листах - это индексы точек данных.

Мы можем контролировать количество кластеров, настраивая параметры distance_thresold или n_cluster. Проверим рассчитанные расстояния между кластерами:

model.distances_
array([0.1       , 0.1       , 0.1       , 0.1       , 0.14142136,        0.14142136, 0.14142136, 0.14142136, 0.14142136, 0.14142136,        0.14142136, 0.17320508, 0.17320508, 0.18257419, 0.2       ,        0.2081666 , 0.21602469, 0.21602469, 0.25819889, 0.27568098,        0.28284271, 0.29439203, 0.29439203, 0.31358146, 0.31464265,        0.31622777, 0.33166248, 0.33665016, 0.34641016, 0.36968455,        0.40620192, 0.42229532, 0.43969687, 0.43969687, 0.46726153,        0.54772256, 0.59441848, 0.6244998 , 0.6363961 , 0.66269651,        0.77628542, 0.81873887, 0.85556999, 0.90998199, 1.10513951,        1.25399362, 1.37126983, 1.91875287, 3.82805262])

Расстояния в порядке возрастания. Если мы можем установить distance_thresold равным 0,8, количество кластеров будет 9. 8 расстояний больше 0,8, поэтому при объединении будет сформировано 9 кластеров.

model = AgglomerativeClustering(distance_threshold=0.8, n_clusters=None)
model = model.fit(X)
model.n_clusters_
9

Спасибо за чтение. Пожалуйста, дайте мне знать, если у вас есть отзывы.

Ссылки