Примечание
Перейти в конец, чтобы скачать полный код примера или запустить этот пример в браузере с помощью JupyterLite или Binder.
Иерархическая кластеризация со структурой и без неё
В этом примере демонстрируется иерархическая кластеризация с ограничениями связности и без них. Показано, как наложение графа связности помогает учитывать локальную структуру данных. Без ограничений связности кластеризация основана только на расстояниях, а при наличии ограничений учитывает локальную структуру.
Дополнительные сведения см. в разделе Иерархическая кластеризация.
У наложения ограничений связности есть два преимущества. Во-первых, кластеризация с разреженными матрицами связности обычно выполняется быстрее.
Во-вторых, при использовании матрицы связности методы одиночной, средней и полной связи нестабильны и склонны быстро формировать несколько разрастающихся кластеров. Действительно, методы средней и полной связи противодействуют такому поведению, учитывая при объединении все расстояния между двумя кластерами (тогда как метод одиночной связи усугубляет это поведение, учитывая только кратчайшее расстояние между кластерами). Граф связности нарушает этот механизм для методов средней и полной связи, делая их похожими на более хрупкий метод одиночной связи. Этот эффект сильнее выражен для очень разреженных графов (попробуйте уменьшить число соседей в kneighbors_graph) и при использовании полной связи. В частности, очень малое число соседей в графе задаёт геометрию, близкую к геометрии метода одиночной связи, который, как известно, подвержен такой нестабильности из-за перколяции.
Эффект наложения ограничений связности показан на двух различных, но похожих наборах данных со спиральной структурой. В первом примере мы создаём набор данных «швейцарский рулет» и выполняем иерархическую кластеризацию по координатам данных. Здесь мы сравниваем кластеризацию Уорда без структуры с её структурированным вариантом, который обеспечивает связность k ближайших соседей. Во втором примере мы показываем последствия применения такого графа связности к методам одиночной, средней и полной связи.
# Authors: The scikit-learn developers # SPDX-License-Identifier: BSD-3-Clause
Создание набора данных «швейцарский рулет».
import time from sklearn.cluster import AgglomerativeClustering from sklearn.datasets import make_swiss_roll n_samples = 1500 noise = 0.05 X1, _ = make_swiss_roll(n_samples, noise=noise) X1[:, 1] *= 0.5 # Make the roll thinner
Вычисление кластеризации без ограничений связности
print("Compute unstructured hierarchical clustering...")
st = time.time()
ward_unstructured = AgglomerativeClustering(n_clusters=6, linkage="ward").fit(X1)
elapsed_time_unstructured = time.time() - st
label_unstructured = ward_unstructured.labels_
print(f"Elapsed time: {elapsed_time_unstructured:.2f}s")
print(f"Number of points: {label_unstructured.size}")
Compute unstructured hierarchical clustering... Elapsed time: 0.04s Number of points: 1500
Построение графика результата кластеризации без структуры
import matplotlib.pyplot as plt
import numpy as np
fig1 = plt.figure()
ax1 = fig1.add_subplot(111, projection="3d", elev=7, azim=-80)
ax1.set_position([0, 0, 0.95, 1])
for l in np.unique(label_unstructured):
ax1.scatter(
X1[label_unstructured == l, 0],
X1[label_unstructured == l, 1],
X1[label_unstructured == l, 2],
color=plt.cm.jet(float(l) / np.max(label_unstructured + 1)),
s=20,
edgecolor="k",
)
_ = fig1.suptitle(
f"Without connectivity constraints (time {elapsed_time_unstructured:.2f}s)"
)
Вычисление кластеризации с ограничениями связности
from sklearn.neighbors import kneighbors_graph
connectivity = kneighbors_graph(X1, n_neighbors=10, include_self=False)
print("Compute structured hierarchical clustering...")
st = time.time()
ward_structured = AgglomerativeClustering(
n_clusters=6, connectivity=connectivity, linkage="ward"
).fit(X1)
elapsed_time_structured = time.time() - st
label_structured = ward_structured.labels_
print(f"Elapsed time: {elapsed_time_structured:.2f}s")
print(f"Number of points: {label_structured.size}")
Compute structured hierarchical clustering... Elapsed time: 0.06s Number of points: 1500
Построение графика результата структурированной кластеризации
fig2 = plt.figure()
ax2 = fig2.add_subplot(111, projection="3d", elev=7, azim=-80)
ax2.set_position([0, 0, 0.95, 1])
for l in np.unique(label_structured):
ax2.scatter(
X1[label_structured == l, 0],
X1[label_structured == l, 1],
X1[label_structured == l, 2],
color=plt.cm.jet(float(l) / np.max(label_structured + 1)),
s=20,
edgecolor="k",
)
_ = fig2.suptitle(
f"With connectivity constraints (time {elapsed_time_structured:.2f}s)"
)
Создание двумерного набора данных со спиралью.
n_samples = 1500 np.random.seed(0) t = 1.5 * np.pi * (1 + 3 * np.random.rand(1, n_samples)) x = t * np.cos(t) y = t * np.sin(t) X2 = np.concatenate((x, y)) X2 += 0.7 * np.random.randn(2, n_samples) X2 = X2.T
Учет локальной связности с помощью графа
Большее число соседей позволяет получить более однородные кластеры, но увеличивает время вычислений. Очень большое число соседей обеспечивает более равномерное распределение размеров кластеров, однако может не учитывать локальную структуру многообразия данных.
knn_graph = kneighbors_graph(X2, 30, include_self=False)
Визуализация кластеризации со структурой и без неё
fig3 = plt.figure(figsize=(8, 12))
subfigs = fig3.subfigures(4, 1)
params = [
(None, 30),
(None, 3),
(knn_graph, 30),
(knn_graph, 3),
]
for subfig, (connectivity, n_clusters) in zip(subfigs, params):
axs = subfig.subplots(1, 4, sharey=True)
for index, linkage in enumerate(("average", "complete", "ward", "single")):
model = AgglomerativeClustering(
linkage=linkage, connectivity=connectivity, n_clusters=n_clusters
)
t0 = time.time()
model.fit(X2)
elapsed_time = time.time() - t0
axs[index].scatter(
X2[:, 0], X2[:, 1], c=model.labels_, cmap=plt.cm.nipy_spectral
)
axs[index].set_title(
"linkage=%s\n(time %.2fs)" % (linkage, elapsed_time),
fontdict=dict(verticalalignment="top"),
)
axs[index].set_aspect("equal")
axs[index].axis("off")
subfig.subplots_adjust(bottom=0, top=0.83, wspace=0, left=0, right=1)
subfig.suptitle(
"n_cluster=%i, connectivity=%r" % (n_clusters, connectivity is not None),
size=17,
)
plt.show()
Общее время выполнения скрипта: (0 минут 2.207 секунды)
Связанные примеры
© 2007–2026 The scikit-learn developers
Licensed under the 3-clause BSD License.
https://scikit-learn.org/1.9/auto_examples/cluster/plot_ward_structured_vs_unstructured.html
