有无结构约束的层次聚类

此示例演示了在有和没有连通性约束的情况下的层次聚类。它展示了施加连通性图以捕获数据局部结构的效果。在没有连通性约束的情况下，聚类纯粹基于距离；而在有约束的情况下，聚类会遵循局部结构。

欲了解更多信息，请参阅 层次聚类。

施加连通性有两个优势。首先，使用稀疏连通性矩阵进行聚类通常速度更快。

其次，当使用连通性矩阵时，单连接（single）、平均连接（average）和全连接（complete）算法会变得不稳定，并倾向于产生少量增长非常快的簇。实际上，平均连接和全连接算法通过在合并簇时考虑两个簇之间的所有距离来对抗这种渗透行为（而单连接算法仅考虑簇之间的最短距离，从而放大了这种行为）。连通性图破坏了平均连接和全连接算法的这种机制，使它们变得类似于更脆弱的单连接算法。对于非常稀疏的图（尝试减少 kneighbors_graph 中的邻居数量）和全连接算法，这种效果更为显著。特别是，图中极少数的邻居会强制形成一种接近单连接算法的几何结构，而单连接算法众所周知存在这种渗透不稳定性。

施加连通性的效果在两个不同但相似的显示螺旋结构的数据集上得到了说明。在第一个示例中，我们构建了一个瑞士卷（Swiss roll）数据集，并根据数据的位置运行层次聚类。在这里，我们将无结构的 Ward 聚类与强制执行 k-近邻（k-Nearest Neighbors）连通性的结构化变体进行了比较。在第二个示例中，我们包含了将此类连通性图应用于单连接、平均连接和全连接算法的效果。

# 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()

相关示例

对硬币图像进行结构化 Ward 分层聚类演示

对硬币图像进行结构化 Ward 分层聚类演示

在玩具数据集上比较不同的分层链接方法

在玩具数据集上比较不同的分层链接方法

在数字的 2D 嵌入上进行各种 Agglomerative 聚类

在数字的 2D 嵌入上进行各种 Agglomerative 聚类

在玩具数据集上比较不同的聚类算法

在玩具数据集上比较不同的聚类算法