在数据聚类分析中,图连接性是一种捕捉数据局部结构的有效方法。通过构建一个包含20个最近邻的图,可以分析数据的局部连接性。这种方法具有两个主要优势:首先,使用稀疏连接矩阵的聚类算法通常计算速度更快;其次,当使用连接矩阵时,单链接、平均链接和完全链接方法在合并聚类时可能会产生不稳定的“渗透”行为,导致少数几个聚类迅速增长。平均链接和完全链接通过考虑两个聚类之间的所有距离来抵抗这种渗透行为,而单链接则通过只考虑聚类之间的最短距离来夸大这种行为。连接图破坏了平均链接和完全链接的这种机制,使它们更类似于更脆弱的单链接。对于非常稀疏的图(例如,减少kneighbors_graph中的邻居数量),这种效果更加明显。特别是,图中的邻居数量非常少时,会施加一种接近单链接的几何结构,这是众所周知的渗透不稳定性。
本文的Gael Varoquaux和Nelle Varoquaux在BSD 3条款许可下提供了以下代码示例,用于生成样本数据并创建捕捉局部连接性的图。代码中使用了不同的链接方法和连接矩阵,以展示它们在聚类分析中的表现。
import time
import matplotlib.pyplot as plt
import numpy as np
from sklearn.cluster import AgglomerativeClustering
from sklearn.neighbors import kneighbors_graph
# 生成样本数据
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)
X = np.concatenate((x, y))
X += 0.7 * np.random.randn(2, n_samples)
X = X.T
# 创建捕捉局部连接性的图。邻居数量越多,计算时间越长,但聚类结果更均匀
knn_graph = kneighbors_graph(X, 30, include_self=False)
for connectivity in (None, knn_graph):
for n_clusters in (30, 3):
plt.figure(figsize=(10, 4))
for index, linkage in enumerate(("average", "complete", "ward", "single")):
plt.subplot(1, 4, index + 1)
model = AgglomerativeClustering(linkage=linkage, connectivity=connectivity, n_clusters=n_clusters)
t0 = time.time()
model.fit(X)
elapsed_time = time.time() - t0
plt.scatter(X[:, 0], X[:, 1], c=model.labels_, cmap=plt.cm.nipy_spectral)
plt.title("linkage=%s\n(time %.2f s)" % (linkage, elapsed_time), fontdict=dict(verticalalignment="top"))
plt.axis("equal")
plt.axis("off")
plt.subplots_adjust(bottom=0, top=0.83, wspace=0, left=0, right=1)
plt.suptitle("n_cluster=%i, connectivity=%r" % (n_clusters, connectivity is not None), size=17)
plt.show()