Spectral Clustering 谱聚类

Notes on MMDS on Coursera

1 衡量聚类的“好坏”

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

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

定义一个聚集的Cut指标(越低越好)为:网络内,只有一端节点在聚集内的边的数量。

先用AGM生成一个网络:

CutPlot1

假设现在有一个聚集A,包括三个节点[0,1,2],计算该聚集的cut指标:

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

另一个可能的指标是Conductance(越低越好):

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

其中:

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

2  图谱理论(Spectral Graph Theory)和谱聚类

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

CutPlot1

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

该矩阵有两个重要属性:

  1. 特征值都是非负实数
  2. 特征向量都是实数,并且相互垂直

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

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

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

  1. 是单位向量:sum_ix_i^2=1
  2. 与第一个特征向量垂直: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 quotientFiedler vector,以及一个挺有帮助的slides

谱聚类步骤:

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

分割点的选择:

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

如果希望有多个聚集,方法有两类:

  1. 递归地进行2分聚类
  2. lambda_2lambda_3等后续特征值对应的特征向量进行K-means

Leave a Reply

Your email address will not be published. Required fields are marked *