光谱聚类python中的图形

Question

我想使用谱聚类在python中聚类图.

光谱聚类是一种更通用的技术,不仅可以应用于图形,还可以应用于图像或任何类型的数据,但是,它被认为是一种特殊的图形聚类技术.可悲的是,我无法在python在线找到谱聚类图的例子.

• Scikit Learn记录了两种光谱聚类方法:SpectralClustering和spectral_clustering,看起来它们不是别名.

• 这两种方法都提到它们可以在图表上使用,但不提供具体说明.用户指南也没有.我已经向开发人员询问了这样一个例子,但是他们过度工作并没有达到目的.

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

我喜欢如何解决这个问题.如果有人可以帮我搞清楚,我可以将文档添加到scikit learn.

笔记:

• 在这个网站上已经提出了一个类似于这个的问题.

Answer 1

没有太多的Spectral-clustering经验,只是通过文档(跳到最后的结果!):

码:

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和谱聚类来解决这个问题:

如果affinity是图的邻接矩阵,则此方法可用于查找规范化图切割.

这将标准化图形切割描述为:

找到图的顶点V的两个不相交的分区A和B,这样A∪B= V和A∩B=∅

给定两个顶点之间的相似性度量w(i,j)(例如,当它们连接时的同一性),切割值(及其标准化版本)被定义为:cut(A,B)= A中的SUM u,B中的v: w(你,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

这完全符合事实真相!

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]