Иерархическая кластеризация

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

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

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

В отличие от K-Means, иерархическая кластеризация не требует заранее выбирать количество кластеров. Алгоритм запускается один раз, после чего дендрограмма «разрезается» на выбранном пороге расстояния, что позволяет получить любое нужное количество кластеров.

Когда использовать иерархическую кластеризацию

Используйте иерархическую кластеризацию, когда:

• Количество кластеров заранее неизвестно, и вы хотите исследовать несколько вариантов за один прогон.
• Датасет небольшой или среднего размера (тысячи строк, но не миллионы) — сложность O(n²) по памяти делает алгоритм непрактичным для очень больших датасетов.
• Необходимо интерпретируемое представление связей между кластерами (дендрограмма наглядно отображает историю объединений).
• Кластеры могут быть несферической формы — иерархические методы с полной или средней связью справляются с неглобулярными формами лучше, чем K-Means.

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

Существуют две основные стратегии:

Эта страница посвящена агломеративной кластеризации — именно её большинство практиков подразумевают, говоря «иерархическая кластеризация».

Как работает алгоритм

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

1. Каждая из n точек данных рассматривается как отдельный кластер (итого n кластеров).
2. Вычисляется матрица расстояний — попарные расстояния между всеми кластерами.
3. Два кластера с наименьшим расстоянием объединяются в один новый кластер.
4. Матрица расстояний обновляется с учётом нового кластера.
5. Шаги 3–4 повторяются до тех пор, пока не останется один кластер.

Итоговый результат — дендрограмма, кодирующая все n-1 шагов объединения.

Методы связи

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

Ward — наиболее часто используемая отправная точка. Если кластеры вытянутые или невыпуклые, попробуйте average или single связь.

Масштабирование признаков перед кластеризацией

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

from sklearn.preprocessing import StandardScaler

scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

StandardScaler центрирует каждый признак до среднего значения 0 и единичной дисперсии. Альтернативы, такие как MinMaxScaler и RobustScaler, описаны в главе о масштабировании.

Реализация иерархической кластеризации с помощью scikit-learn

Класс AgglomerativeClustering в scikit-learn обучает модель и присваивает метки кластеров за один шаг. Он не строит дендрограмму — для этого используйте SciPy (показано в следующем разделе).

Шаг 1 — Генерация и масштабирование данных

from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler

# 150 points in 3 natural clusters
X, y_true = make_blobs(n_samples=150, centers=3, cluster_std=0.6, random_state=42)

scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

make_blobs создаёт воспроизводимый синтетический датасет, поэтому пример работает без каких-либо CSV-файлов.

Шаг 2 — Обучение агломеративной кластеризации

from sklearn.cluster import AgglomerativeClustering

hc = AgglomerativeClustering(n_clusters=3, linkage='ward')
labels = hc.fit_predict(X_scaled)

print(labels[:10])
# e.g. [2 2 0 1 0 1 2 2 0 1]

fit_predict одновременно обучает модель и возвращает метку кластера (0, 1 или 2) для каждой точки данных.

Шаг 3 — Визуализация кластеров

import matplotlib.pyplot as plt

colors = ['red', 'blue', 'green']
for cluster_id in range(3):
    mask = labels == cluster_id
    plt.scatter(X_scaled[mask, 0], X_scaled[mask, 1],
                s=60, label=f'Cluster {cluster_id + 1}')

plt.title('Agglomerative Clustering (Ward linkage, k=3)')
plt.xlabel('Feature 1 (scaled)')
plt.ylabel('Feature 2 (scaled)')
plt.legend()
plt.tight_layout()
plt.show()

Дендрограммы с помощью SciPy

Дендрограмма — наиболее характерный результат иерархической кластеризации. Она позволяет визуально выбрать количество кластеров, «разрезая» дерево на разной высоте. Модуль scipy.cluster.hierarchy предоставляет функции linkage (для построения дерева) и dendrogram (для его визуализации).

Построение и отрисовка дендрограммы

from scipy.cluster.hierarchy import dendrogram, linkage
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler
import matplotlib.pyplot as plt

# Use a smaller dataset so the dendrogram is readable
X, _ = make_blobs(n_samples=30, centers=3, cluster_std=0.6, random_state=42)
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# Build the linkage matrix
Z = linkage(X_scaled, method='ward')

# Plot
plt.figure(figsize=(12, 5))
dendrogram(Z, leaf_rotation=90, leaf_font_size=8)
plt.title('Dendrogram (Ward linkage)')
plt.xlabel('Sample index')
plt.ylabel('Merge distance')
plt.tight_layout()
plt.show()

Чтение дендрограммы

• Листья (снизу) представляют отдельные точки данных.
• Горизонтальные линии представляют объединения. Высота линии равна расстоянию между двумя объединяемыми кластерами.
• Разрез дерева на заданной высоте даёт количество кластеров ниже этого разреза.

Чтобы выбрать k, найдите самую длинную вертикальную линию, не пересечённую горизонтальной — этот промежуток указывает на наиболее естественное количество кластеров.

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

После построения матрицы связи Z используйте fcluster для разрезания дерева на нужное количество кластеров:

from scipy.cluster.hierarchy import linkage, fcluster
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler
import numpy as np

X, _ = make_blobs(n_samples=150, centers=3, cluster_std=0.6, random_state=42)
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

Z = linkage(X_scaled, method='ward')

# Cut the tree to get exactly 3 clusters
labels = fcluster(Z, t=3, criterion='maxclust')

print('Unique cluster IDs:', np.unique(labels))   # [1 2 3]  (1-indexed)
print('Sizes:', np.bincount(labels[labels > 0]))   # [50 50 50]

Обратите внимание: метки fcluster индексируются с 1 (начинаются с 1), в отличие от меток scikit-learn, которые индексируются с 0.

Сравнение методов связи

Метод связи существенно меняет форму и размер кластеров. Ниже показано, как сравнить все четыре метода на одном датасете:

from sklearn.cluster import AgglomerativeClustering
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler
import matplotlib.pyplot as plt
import numpy as np

X, _ = make_blobs(n_samples=150, centers=3, cluster_std=0.6, random_state=42)
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

methods = ['ward', 'complete', 'average', 'single']
fig, axes = plt.subplots(1, 4, figsize=(16, 4))

for ax, method in zip(axes, methods):
    hc = AgglomerativeClustering(n_clusters=3, linkage=method)
    labels = hc.fit_predict(X_scaled)
    ax.scatter(X_scaled[:, 0], X_scaled[:, 1], c=labels, cmap='Set1', s=30)
    ax.set_title(f'{method.capitalize()} linkage')
    ax.set_xticks([])
    ax.set_yticks([])

plt.suptitle('Linkage method comparison (k=3)', y=1.02)
plt.tight_layout()
plt.show()

Иерархическая кластеризация vs K-Means

Используйте иерархическую кластеризацию для разведочного анализа на небольших датасетах; переходите к K-Means (или DBSCAN), когда данных миллионы или количество кластеров уже известно.

Распространённые ошибки

Забывать масштабировать признаки. Без масштабирования признаков признак с большими значениями (например, доход) будет доминировать над признаком с малыми значениями (например, возрастной рейтинг), что приведёт к искажённым кластерам.

Использовать Ward с не-евклидовыми расстояниями. Ward действителен только для евклидова расстояния. Для других метрик (например, косинусного расстояния, расстояния Манхэттена) используйте complete или average связь и явно передавайте параметр metric=.

Интерпретировать дендрограммы на очень больших датасетах. Дендрограмма с 10 000 листьями нечитаема. Используйте параметры p= и truncate_mode='lastp' в функции dendrogram() из SciPy, чтобы отображать только последние p объединений.

Считать идентификаторы кластеров стабильными. Идентификаторы кластеров (0, 1, 2) — произвольные метки. При сравнении двух прогонов сопоставляйте кластеры по содержимому, а не по номеру.

Заключение

Иерархическая кластеризация — гибкий и интерпретируемый алгоритм, не требующий заранее задавать k. Полная дендрограмма строится один раз, после чего её можно разрезать на любом уровне. Ward с предобработкой StandardScaler — наиболее безопасный выбор по умолчанию. Для очень больших датасетов предпочтительнее K-Means ввиду его производительности.

Связанные главы:

• Scale — зачем и как стандартизировать признаки перед кластеризацией
• K-Means — плоская кластеризация для больших датасетов
• SciPy Tutorial — подробнее о библиотеке научных вычислений SciPy
• Scatter Plot — визуализация многомерных данных с помощью Matplotlib