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

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

Иерархическая кластеризация (Hierarchical Clustering) — это метод разделения данных на группы (кластеры), который создаёт иерархическую структуру вложенных кластеров. В отличие от K-means, не требует заранее задавать количество кластеров.

Два подхода к иерархической кластеризации

1. Agglomerative Clustering ("восходящий" подход)

Начинаем с каждого объекта как отдельного кластера, затем последовательно объединяем их:

from scipy.cluster.hierarchy import dendrogram, linkage, fcluster
from scipy.spatial.distance import pdist
import matplotlib.pyplot as plt
import numpy as np

# Создаём данные
X = np.array([
    [1, 2],
    [1, 4],
    [1, 0],
    [4, 2],
    [4, 4],
    [4, 0]
])

# Вычисляем матрицу расстояний между всеми точками
Z = linkage(X, method='ward')

# Визуализируем дендрограмму
plt.figure(figsize=(10, 6))
dendrogram(Z, labels=['p1', 'p2', 'p3', 'p4', 'p5', 'p6'])
plt.title('Дендрограмма иерархической кластеризации')
plt.ylabel('Расстояние')
plt.show()

# Выбираем количество кластеров, разрезав дендрограмму на нужную высоту
clusters = fcluster(Z, t=3, criterion='maxclust')  # 3 кластера
print(f"Распределение по кластерам: {clusters}")

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

1. Начинаем с n кластеров (каждый объект отдельный)
2. Находим два ближайших кластера
3. Объединяем их в один кластер
4. Повторяем шаги 2-3 до тех пор, пока не останется один кластер

2. Divisive Clustering ("нисходящий" подход)

Начинаем с одного кластера всех данных, затем последовательно его разбиваем:

from scipy.cluster.hierarchy import dendrogram, linkage

# Divisive подход менее популярен и сложнее в реализации
# Обычно используют scipy или sklearn для agglomerative

from sklearn.cluster import AgglomerativeClustering

model = AgglomerativeClustering(
    n_clusters=3,
    linkage='ward'  # метод связи
)
labels = model.fit_predict(X)
print(f"Метки кластеров: {labels}")

Методы связи (Linkage Methods)

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

1. Single Linkage (наименьшее расстояние)

Z = linkage(X, method='single')
# Расстояние = минимальное расстояние между любыми двумя объектами из разных кластеров
# dist(C1, C2) = min(|p1 - p2|) для p1 из C1, p2 из C2

Плюсы: чувствителен к единичным выбросам, может создавать цепочки Минусы: неустойчив при шуме

2. Complete Linkage (максимальное расстояние)

Z = linkage(X, method='complete')
# Расстояние = максимальное расстояние между любыми двумя объектами
# dist(C1, C2) = max(|p1 - p2|) для p1 из C1, p2 из C2

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

3. Average Linkage (среднее расстояние)

Z = linkage(X, method='average')
# Расстояние = среднее расстояние между объектами
# dist(C1, C2) = (1 / (|C1| * |C2|)) * Σ |p1 - p2|

Плюсы: баланс между single и complete Минусы: чувствителен к выбросам

4. Ward Linkage (минимизирует внутри-кластерную дисперсию)

Z = linkage(X, method='ward')
# Объединяет кластеры, которые минимизируют прирост дисперсии
# Похож на K-means в этом смысле

Плюсы: часто производит наиболее интерпретируемые результаты Минусы: требует больше вычислений

5. Centroid Linkage (расстояние между центройдами)

Z = linkage(X, method='centroid')
# dist(C1, C2) = |центроид C1 - центроид C2|

Практический пример: анализ данных об ирисах

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

# Загружаем данные
iris = load_iris()
X = iris.data

# Нормализуем данные
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# Вычисляем иерархическую кластеризацию
Z = linkage(X_scaled, method='ward')

# Визуализируем дендрограмму
plt.figure(figsize=(12, 6))
dendrogram(
    Z,
    truncate_mode='lastp',  # показываем только последние n объединений
    p=30  # показываем объединения последних 30 листьев
)
plt.title('Дендрограмма для датасета Iris')
plt.ylabel('Расстояние')
plt.xlabel('Размер кластера')
plt.show()

# Выбираем 3 кластера (по количеству классов в Iris)
model = AgglomerativeClustering(n_clusters=3, linkage='ward')
labels = model.fit_predict(X_scaled)

print(f"Распределение: {np.bincount(labels)}")
# Сравниваем с истинными метками
from sklearn.metrics import adjusted_rand_score, silhouette_score

print(f"Adjusted Rand Index: {adjusted_rand_score(iris.target, labels):.3f}")
print(f"Silhouette Score: {silhouette_score(X_scaled, labels):.3f}")

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

Преимущества иерархической кластеризации

1. Не требует k заранее — выбираем после построения дендрограммы
2. Дендрограмма — интерпретируемая визуализация структуры данных
3. Информативность — показывает взаимосвязь между кластерами
4. Гибкость — можно выбрать различные уровни детализации
5. Устойчивость к шуму — зависит от выбранного метода

Недостатки

1. Вычислительная сложность O(n^2 или n^2*log(n)) — медленно на больших данных
2. Необратимость — ошибка на ранних этапах не может быть исправлена
3. Чувствительность к масштабированию — важно нормализовать данные
4. Сложность использования на больших датасетах (>10000 точек)

Практические рекомендации

1. Используй Ward linkage — обычно даёт лучшие результаты
2. Нормализуй данные перед кластеризацией
3. Дендрограмма — визуализируй всегда для выбора количества кластеров
4. Для больших данных используй agglomerative с параметром distance_threshold
5. Комбинируй с другими методами (например, сначала иерархическая, потом K-means)

Выводы

Иерархическая кластеризация — мощный инструмент для исследовательского анализа данных. Хотя она медленнее K-means на больших данных, дендрограмма даёт ценные insights о структуре данных. Идеальна для маленьких и средних датасетов, когда интерпретируемость важнее скорости.