31

我想使用谱聚类在 python 中对图进行聚类。

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

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

笔记：

4

3 回答 3

38

在光谱聚类方面没有太多经验，只看文档（跳到最后看结果！）：

代码：

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 收集他的数据时，空手道俱乐部发生了争执，它分成了两个派别：一个由“先生”领导。嗨”，还有一个由“John A”领导。事实证明，仅使用连接信息（边缘），就有可能恢复两个派系。

使用 sklearn 和光谱聚类来解决这个问题：

如果affinity是一个图的邻接矩阵，这个方法可以用来找到归一化的图割。

这将归一化的图割描述为：

求图的顶点 V 的两个不相交的分区 A 和 B，使得 A ∪ B = V 和 A ∩ B = ∅</p>

给定两个顶点之间的相似性度量 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

这非常符合事实！

于 2017-09-16T22:15:49.113 回答
9

这是一个虚拟示例，只是为了了解它对简单相似矩阵的作用——受 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]
于 2018-08-18T14:12:45.197 回答
0

让我们首先将图 G 聚类为 K=2 个聚类，然后对所有 K 进行泛化。

  • 我们可以使用函数linalg.algebraicconnectivity.fiedler_vector()fromnetworkx来计算图的（对应于图拉普拉斯矩阵的第二小的特征值的特征向量）的 Fiedler 向量，假设该图是一个连通的无向图。

    然后我们可以阈值特征向量的值来计算每个节点对应的集群索引，如下一个代码块所示：

    import networkx as nx
import numpy as np

A = np.zeros((11,11))
A[0,1] = A[0,2] = A[0,3] = A[0,4] = 1
A[5,6] = A[5,7] = A[5,8] = A[5,9] = A[5,10] = 1
A[0,5] = 5

G = nx.from_numpy_matrix(A)
ev = nx.linalg.algebraicconnectivity.fiedler_vector(G)
labels = [0 if v < 0 else 1 for v in ev] # using threshold 0
labels
# [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1]

nx.draw(G, pos=nx.drawing.layout.spring_layout(G), 
           with_labels=True, node_color=labels)

在此处输入图像描述

  • 我们可以通过图拉普拉斯算子的特征分析获得相同的聚类，然后也可以选择与第二个最小特征值对应的特征向量：

    L = nx.laplacian_matrix(G)
e, v = np.linalg.eig(L.todense()) 
idx = np.argsort(e)
e = e[idx]
v = v[:,idx]
labels = [0 if x < 0 else 1 for x in v[:,1]] # using threshold 0
labels
# [1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0]

    再次绘制带有标记的集群的图形：

在此处输入图像描述

  • 使用SpectralClusteringfromsklearn.cluster我们可以得到完全相同的结果：

    sc = SpectralClustering(2, affinity='precomputed', n_init=100)
sc.fit(A)
sc.labels_
# [0 0 0 0 0 1 1 1 1 1 1]

在此处输入图像描述

  • 对于 K > 2 个集群，我们可以将上述概括如下（使用kmeans集群来划分 Fiedler 向量而不是阈值）：

    在此处输入图像描述

    以下代码演示了如何使用 k-means 聚类来划分 Fiedler 向量并获得由以下邻接矩阵定义的图的 3-聚类：

    A = np.array([[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]])

K = 3 # K clusters
G = nx.from_numpy_matrix(A)
ev = nx.linalg.algebraicconnectivity.fiedler_vector(G)
from sklearn.cluster import KMeans
kmeans = KMeans(n_clusters=K, random_state=0).fit(ev.reshape(-1,1))
kmeans.labels_
# array([2, 2, 2, 0, 0, 0, 1, 1, 1])

    现在绘制集群图，用上面获得的集群标记节点：

    在此处输入图像描述

于 2021-11-01T23:00:37.913 回答