Notes on MMDS on Coursera
1 衡量聚类的“好坏”
什么样的聚集是好的聚集?
- 希望聚集内的相互连接尽量多
- 希望聚集内的节点与聚集外的节点之间连接尽量少
定义一个聚集的Cut指标(越低越好)为:网络内,只有一端节点在聚集内的边的数量。
先用AGM生成一个网络:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
# import libraries import networkx as nx import matplotlib.pyplot as plt import random import numpy as np # community class definition class community: def __init__(self, member, prob): self.member = member self.prob = prob # AGM def AGM(nodes,communities): # import library from itertools import combinations from random import random # creating an empty graph G=nx.Graph() # add nodes to the graph G.add_nodes_from(nodes) # generate links within communities for c in communities: for nodePairs in combinations(c.member,2): if random() <= c.prob: G.add_edge(nodePairs[0], nodePairs[1]) return G nodes = range(6) communities = [community([0,1,2], 1), community([3,4,5], 1), community([0,5], 1), community([2,3], 1)] G = AGM(nodes,communities) nx.draw_networkx(G) |
假设现在有一个聚集A,包括三个节点[0,1,2],计算该聚集的cut指标:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
# cluster measures class cluster: def __init__(self, member, cut = None): self.member = member self.cut = cut def clusterCutScore(graph, nodes): cutScore = 0 for edge in graph.edges(): if len(set(edge).intersection(set(nodes))) == 1: cutScore += 1 return cutScore clusterA = cluster([0,1,2], clusterCutScore(G, [0,1,2])) print clusterA.cut 2 |
Cut值并不是一个非常好的指标,如果包含度为1的节点,那么仅仅由节点一个节点构成的聚类,Cut值为1。
另一个可能的指标是Conductance(越低越好):
其中:
是聚集A的cut分值
是聚集A的所有节点的度的和
是网络内边的总数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
class cluster: def __init__(self, member, cut = None, conductance = None): self.member = member self.cut = cut self.conductance = conductance def clusterConductanceScore(graph, nodes): m = graph.number_of_edges() volA = sum([len(graph.neighbors(node)) for node in nodes]) cut = clusterCutScore(graph, nodes) return float(cut)/min(volA, 2*m-volA) nodes = [0,1,2] clusterA = cluster(nodes, clusterCutScore(G, nodes), clusterConductanceScore(G, nodes)) print clusterA.clusterConductanceScore 0.25 |
2 图谱理论(Spectral Graph Theory)和谱聚类
分析表示网络的矩阵的“谱”。谱为按照对应特征值大小排列的矩阵特征向量。
定义网络的拉普拉斯矩阵为网络的度矩阵与网络的邻接矩阵之差:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
def laplacianOfGraph(graph): n = graph.number_of_nodes() A = nx.to_numpy_matrix(graph) D = np.matrix(np.zeros((n,n))) for node in graph.degree(): D[node, node] = graph.degree()[node] L = D-A return L print laplacianOfGraph(G) [[ 3. -1. -1. 0. 0. -1.] [-1. 2. -1. 0. 0. 0.] [-1. -1. 3. -1. 0. 0.] [ 0. 0. -1. 3. -1. -1.] [ 0. 0. 0. -1. 2. -1.] [-1. 0. 0. -1. -1. 3.]] |
该矩阵有两个重要属性:
- 特征值都是非负实数
- 特征向量都是实数,并且相互垂直
一些通过线性代数可获得事实:
令拉普拉斯矩阵的特征值为,特征向量为
特征向量有两个重要属性:
- 是单位向量:
- 与第一个特征向量垂直:
特征值是该表达式的最优解:
因此上面的最小化问题的物理意义是将节点一部分放在<0出,另一部分放在>0处() ,并且使得连接两端的边尽量地小(
)
具体参见Rayleigh quotient,Fiedler vector,以及一个挺有帮助的slides
谱聚类步骤:
- 预处理:用拉普拉斯矩阵表示网络
- 分解:计算矩阵的特征值和特征向量,找到
对应的特征向量
(这样每一个节点就用一个值来表示了)
- 聚类:决定若干分割值,根据特征向量的值与分割值的关系,将各个节点归属到不同聚集
分割点的选择:
- 简单地选择0或者中位数
- 尝试最小化正则化的1维cut值
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
def naiveSpectralClustering(graph): L = laplacianOfGraph(graph) evals, evecs = np.linalg.eig(L) values = np.array(evecs[:,1]).reshape(-1).tolist() cluster1 = [i for i in range(n) if values[i] <= 0] cluster2 = [i for i in range(n) if values[i] > 0] return cluster1, cluster2 c1, c2 = naiveSpectralClustering(G) print c1 [0, 1, 2] print c2 [3, 4, 5] |
如果希望有多个聚集,方法有两类:
- 递归地进行2分聚类
- 对
或
等后续特征值对应的特征向量进行K-means