Spectral Clustering 谱聚类

Notes on MMDS on Coursera

1 衡量聚类的“好坏”

什么样的聚集是好的聚集？

希望聚集内的相互连接尽量多
希望聚集内的节点与聚集外的节点之间连接尽量少

定义一个聚集的Cut指标（越低越好）为：网络内，只有一端节点在聚集内的边的数量。

先用AGM生成一个网络：

# 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)

# 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指标：

# 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

# 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

Cut值并不是一个非常好的指标，如果包含度为1的节点，那么仅仅由节点一个节点构成的聚类，Cut值为1。

另一个可能的指标是Conductance（越低越好）：

$phi(A) = frac{text{cut(A)}}{min(vol(A), 2m-vol(A))}$

其中：

$cut(A)$ 是聚集A的cut分值
$vol(A)$ 是聚集A的所有节点的度的和
$m$ 是网络内边的总数

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

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）和谱聚类

分析表示网络的矩阵的“谱”。谱为按照对应特征值大小排列的矩阵特征向量。

定义网络的拉普拉斯矩阵为网络的度矩阵与网络的邻接矩阵之差：

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.]]

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.]]

该矩阵有两个重要属性：

特征值都是非负实数
特征向量都是实数，并且相互垂直

一些通过线性代数可获得事实：

令拉普拉斯矩阵的特征值为 $lambda$ ，特征向量为 $x$

特征向量有两个重要属性：

是单位向量： $sum_ix_i^2=1$
与第一个特征向量垂直： $sum_ix_icdot 1 = 0$

特征值 $lambda _2$ 是该表达式的最优解：

$min_{x}frac{x^TMx}{x^Tx}=min_{x}sum_{i,j}(x_i-x_j)^2$

因此上面的最小化问题的物理意义是将节点一部分放在<0出，另一部分放在>0处（ $sum_ixi=0$ ），并且使得连接两端的边尽量地小（ $min_{x}sum_{i,j}(x_i-x_j)^2$ ）

具体参见Rayleigh quotient，Fiedler vector，以及一个挺有帮助的slides

谱聚类步骤：

预处理：用拉普拉斯矩阵表示网络
分解：计算矩阵的特征值和特征向量，找到 $lambda_2$ 对应的特征向量 $x$ （这样每一个节点就用一个值来表示了）
聚类：决定若干分割值，根据特征向量的值与分割值的关系，将各个节点归属到不同聚集

分割点的选择：

简单地选择0或者中位数
尝试最小化正则化的1维cut值

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]

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分聚类
对 $lambda_2$ 或 $lambda_3$ 等后续特征值对应的特征向量进行K-means

Ren’s Cabinet of Curiosities

"Learning is never cumulative, it is a movement of knowing which has no beginning and no end." – Bruce Lee

Spectral Clustering 谱聚类

Notes on MMDS on Coursera

1 衡量聚类的“好坏”

2 图谱理论（Spectral Graph Theory）和谱聚类

Leave a Reply Cancel reply