在 python 中对图形进行光谱聚类

Question

我想使用谱聚类在 python 中聚类一个图。

谱聚类是一种更通用的技术，不仅可以应用于图形，还可以应用于图像或任何类型的数据，但是，它被认为是一种特殊的 图形 聚类技术。遗憾的是，我在网上找不到 python 中的谱聚类图示例。

• Scikit Learn 记录了两种谱聚类方法： SpectralClustering 和 spectral_clustering ，它们看起来不是别名。

• 这两种方法都提到它们可以用于图形，但没有提供具体说明。 用户指南也没有。我已经 向开发人员索取了这样的示例，但他们工作过度而没有得到它。

• 记录这一点的一个很好的网络是 空手道俱乐部网络。它 作为一种方法包含在 networkx 中。

我很想知道如何去做这件事。如果有人能帮我弄清楚，我可以将文档添加到 scikit learn 中。

笔记：

• 这个站点上已经提出了一个与此非常相似的问题。

原文由 Alex Lenail 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

没有太多的光谱聚类经验，只是通过文档（跳到最后查看结果！）：

代码：

 import numpy as np
import networkx as nx
from sklearn.cluster import SpectralClustering
from sklearn import metrics
np.random.seed(1)

# Get your mentioned graph
G = nx.karate_club_graph()

# Get ground-truth: club-labels -> transform to 0/1 np-array
#     (possible overcomplicated networkx usage here)
gt_dict = nx.get_node_attributes(G, 'club')
gt = [gt_dict[i] for i in G.nodes()]
gt = np.array([0 if i == 'Mr. Hi' else 1 for i in gt])

# Get adjacency-matrix as numpy-array
adj_mat = nx.to_numpy_matrix(G)

print('ground truth')
print(gt)

# Cluster
sc = SpectralClustering(2, affinity='precomputed', n_init=100)
sc.fit(adj_mat)

# Compare ground-truth and clustering-results
print('spectral clustering')
print(sc.labels_)
print('just for better-visualization: invert clusters (permutation)')
print(np.abs(sc.labels_ - 1))

# Calculate some clustering metrics
print(metrics.adjusted_rand_score(gt, sc.labels_))
print(metrics.adjusted_mutual_info_score(gt, sc.labels_))

输出：

 ground truth
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1]
spectral clustering
[1 1 0 1 1 1 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
just for better-visualization: invert clusters (permutation)
[0 0 1 0 0 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]
0.204094758281
0.271689477828

总体思路：

从 这里 介绍数据和任务：

图中的节点代表大学空手道俱乐部的 34 名成员。 （Zachary 是一名社会学家，他是成员之一。）两个节点之间的边表示这两个成员在正常的俱乐部会议之外花费了大量时间在一起。该数据集很有趣，因为在 Zachary 收集他的数据时，空手道俱乐部发生了争执，并且分成了两个派系：一个由“先生”领导。嗨”，还有一个由“约翰 A”领导。事实证明，仅使用连通性信息（边），就有可能恢复这两个派系。

使用 sklearn & spectral-clustering 来解决这个问题：

如果亲和度是图的邻接矩阵，则此方法可用于查找归一化图割。

这 将归一化图形切割描述为：

找到图的顶点 V 的两个不相交分区 A 和 B，使得 A ∪ B = V 和 A ∩ B = ∅

给定两个顶点之间的相似性度量 w(i,j)（例如，它们连接时的同一性），切割值（及其归一化版本）定义为： cut(A, B) = SUM u in A, v in B： w(u, v)

…

我们寻求 A 组和 B 组之间的分离最小化以及每个组内关联的最大化

听起来不错。所以我们创建邻接矩阵（ nx.to_numpy_matrix(G) ）并将参数 affinity 设置为 _预先计算_（因为我们的邻接矩阵是我们预先计算的相似性度量）。

或者，可以使用预先计算的用户提供的亲和力矩阵。

编辑： 虽然对此不熟悉，但我寻找 要调整的参数 并找到 了 assign_labels ：

用于在嵌入空间中分配标签的策略。在拉普拉斯嵌入之后有两种分配标签的方法。 k-means 可以应用并且是一个流行的选择。但它也可能对初始化敏感。离散化是另一种对随机初始化不太敏感的方法。

所以尝试不太敏感的方法：

 sc = SpectralClustering(2, affinity='precomputed', n_init=100, assign_labels='discretize')

输出：

 ground truth
[0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1]
spectral clustering
[0 0 1 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1]
just for better-visualization: invert clusters (permutation)
[1 1 0 1 1 1 1 1 0 0 1 1 1 1 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0]
0.771725032425
0.722546051351

这与基本事实非常吻合！

原文由 sascha 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

这是一个虚拟示例，只是为了了解它对简单相似度矩阵的作用——灵感来自 sascha 的回答。

代码

import numpy as np
from sklearn.cluster import SpectralClustering
from sklearn import metrics
np.random.seed(0)

adj_mat = [[3,2,2,0,0,0,0,0,0],
           [2,3,2,0,0,0,0,0,0],
           [2,2,3,1,0,0,0,0,0],
           [0,0,1,3,3,3,0,0,0],
           [0,0,0,3,3,3,0,0,0],
           [0,0,0,3,3,3,1,0,0],
           [0,0,0,0,0,1,3,1,1],
           [0,0,0,0,0,0,1,3,1],
           [0,0,0,0,0,0,1,1,3]]

adj_mat = np.array(adj_mat)

sc = SpectralClustering(3, affinity='precomputed', n_init=100)
sc.fit(adj_mat)

print('spectral clustering')
print(sc.labels_)

输出

spectral clustering
[0 0 0 1 1 1 2 2 2]

原文由 sinapan 发布，翻译遵循 CC BY-SA 4.0 许可协议