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

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

В качестве дистанций между кластерами часто принимают:

максимальное расстояние между двумя точками одно и другого кластера (полная связь);
минимальное расстояние между двумя точками одно и другого кластера (одиночная связь);
среднее расстояние между парами точек одно и другого кластера (средняя связь);
значение совокупной внутрикластерной ошибки при объединении (метод уорда).

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

Сгенерируем и визуализируем набор данных (читай подробнее):

from sklearn.datasets import make_blobs
from scipy.cluster.hierarchy import dendrogram, linkage
import pandas as pd
import matplotlib.pyplot as plt
import seaborn as sns
sns.set()

X, y, centers = make_blobs(n_samples=1000, centers=3, n_features=2, center_box=[2,100], 
                           return_centers=True, random_state=0)
X = pd.DataFrame(X, columns=['feat1', 'feat2'])

plt.figure(figsize=(10,6))
plt.rc('axes', labelsize=20)   
sns.scatterplot(data=X, x='feat1', y='feat2', hue=y, palette= 'rocket')
plt.scatter(centers[:,0], centers[:,1], s=50, c='g', marker='o')

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

cluster_ar = linkage(X, method='ward', metric='euclidean')

link_df = pd.DataFrame(cluster_ar, index=[f'step {i+1}' for i in range(cluster_ar.shape[0])], 
                       columns=['cluster1', 'cluster2', 'dist', 'number elements'])
link_df.head()

Для отображения потребуется link_df передать в dendrogram:

fig = plt.figure(figsize=(25, 10))
row_dendr = dendrogram(link_df)

По вертикальной оси дендрограммы отображается дистанция между кластерами, то есть чем ближе к вершине, тем она больше. На основании этого рисунка можно выбрать количество кластеров, на которое разумно поделить данные (здесь, очевидно, 3).

Теперь предскажем кластер для каждой точки данных с классом AgglomerativeClustering из sklearn.cluster:

from sklearn.cluster import AgglomerativeClustering

cl = AgglomerativeClustering(n_clusters=3, linkage = 'ward', affinity='euclidean')
labels = cl.fit_predict(X)

plt.figure(figsize=(10,6))
plt.rc('axes', labelsize=20)   
sns.scatterplot(data=X, x='feat1', y='feat2', hue=labels)

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