【Spectral Clustering】谱聚类

原理

谱聚类的特点

• 对数据分布的适应性强
• 聚类效果优秀
• 复杂度低、计算量小
• 从图论中演化来的算法

基础理论1：无向有权图

把每个样本点看成一个有向无权图上的节点，两个点之间的距离看成这个有向无权图上的点之间的权重。

于是从样本点获得一个 Graph，G(V,E)G(V,E)

同时，从图的视角，我们定义几个概念：

• 节点 (v1,v2,…,vn)(v1,v2,…,vn)
• 权重。 wijwij 指的是两个点 v_i,v_j之间的 距离。这个距离是你根据任务目标去确定的，例如欧氏距离。性质：
  • wij=wjiwij=wji
  • wii=0wii=0
  • 邻接矩阵，就是 wijwij 组成的矩阵
• 度。一个节点对应的度，定义为其所有权重之和 di=∑j=1nwijdi=∑j=1nwij
  • 度矩阵。节点度组成的对角矩阵 D=diag(d1,d2,…,dn)D=diag(d1,d2,…,dn)
• 邻接矩阵：wij=exp(−∣∣xi−xj∣∣222σ2)wij=exp⁡(−∣∣xi−xj∣∣222σ2)。一般使用上面这个定义，有时候也会按照 TOP-K做个截断，对于一个节点，TOP-K以外的权重都置为0，这样得到的邻接矩阵是稀疏矩阵。

基础理论2：拉普拉斯矩阵

拉普拉斯矩阵定义为 L=D−WL=D−W

它有很多良好的性质：

1. L 是一个对称矩阵。这是因为D和W都是对称矩阵。
2. L 对应的特征值都是实数。这是因为L是一个实对称矩阵
3. 对于任意向量 ff，有 fTLf=1/2∑i,j=1nwij(fi−fj)2fTLf=1/2∑i,j=1nwij(fi−fj)2
4. 根据性质3，拉普拉斯矩阵是半正定的。

性质3的证明：
fTLf=fTDf−fTWf=∑i=1nf2i−∑i,j=1nwijfifjfTLf=fTDf−fTWf=∑i=1nfi2−∑i,j=1nwijfifj
=1/2(∑i=1ndif2i−2∑i,j=1nwijfifj+∑j=1ndjf2j)=1/2∑i,j=1nwni,j=1(fi−fj)2=1/2(∑i=1ndifi2−2∑i,j=1nwijfifj+∑j=1ndjfj2)=1/2∑i,j=1nwi,j=1n(fi−fj)2

基础理论3：图切分

我们做图上的聚类，实际上就是要把图 G(V,E) 分割成k个子图。
这k个子图的点的集合记为A1,A2,…AkA1,A2,…Ak，它们满足 Ai∩Aj=\empty(i≠j)Ai∩Aj=\empty(i≠j),并且 A1∪A2∪…∪Ak=VA1∪A2∪…∪Ak=V

然后我们需要定义一个损失函数，使得“组间距离”最大

我们先定义两个点集之间的“距离”，将其定义为顶点的两两距离之和。写成公司就是：对于A,B⊂V,A∩BA,B⊂V,A∩B，定义W(A,B)=∑i∈A,j∈BwijW(A,B)=∑i∈A,j∈Bwij

基础理论4：损失函数

共有3种，一一列出：

1. cut

很容易想到，损失函数可以是：

cut(A1,A2,…,Ak)=1/2∑i=1k(Ai,A¯i)cut(A1,A2,…,Ak)=1/2∑i=1k(Ai,A¯i)
其中 A¯iA¯i是 AiAi 的补集。

这么做有个严重的缺点：如果有1个离大家都较远的“游离点”，那么这个游离点会被单独归为一类。

2. RatioCut

为了避免上面的问题，加一个权重。

定义 ∣Ai∣∣Ai∣ 为点集A的点的个数

定义 RatioCut(A1,A2,…,Ak)=1/2∑i=1kW(Ai,A¯i)∣Ai∣RatioCut(A1,A2,…,Ak)=1/2∑i=1kW(Ai,A¯i)∣Ai∣

直观理解就是不仅仅让总的组间距离更远，而且还尽量让每个子图的点的个数更多。

为了解 RatioCut 的最大化的条件，做以下推导：

令 hij=⎧⎩⎨⎪⎪01∣Aj∣vi∉Ajvi∈Ajhij={0vi∉Aj1∣Aj∣vi∈Aj

得到，
hTiLhi=12∑m=1∑n=1wmn(him−hin)2=12(∑m∈Ai,n∉Aiwmn(1|Ai|−−−√−0)2+∑m∉Ai,n∈Aiwmn(0−1|Ai|−−−√)2=12(∑m∈Ai,n∉Aiwmn1|Ai|+∑m∉Ai,n∈Aiwmn1|Ai|=12(cut(Ai,A¯¯¯¯i)1|Ai|+cut(A¯¯¯¯i,Ai)1|Ai|)=cut(Ai,A¯¯¯¯i)|Ai|(1)(2)(3)(4)(5)(1)hiTLhi=12∑m=1∑n=1wmn(him−hin)2(2)=12(∑m∈Ai,n∉Aiwmn(1|Ai|−0)2+∑m∉Ai,n∈Aiwmn(0−1|Ai|)2(3)=12(∑m∈Ai,n∉Aiwmn1|Ai|+∑m∉Ai,n∈Aiwmn1|Ai|(4)=12(cut(Ai,A¯i)1|Ai|+cut(A¯i,Ai)1|Ai|)(5)=cut(Ai,A¯i)|Ai|

这里面（1）式根据上面的拉普拉斯矩阵性质3得到

然后，RatioCut(A1,A2,…Ak)=∑i=1khTiLhi=∑i=1k(HTLH)ii=tr(HTLH)RatioCut(A1,A2,…Ak)=∑i=1khiTLhi=∑i=1k(HTLH)ii=tr(HTLH)

注意到 HTH=IHTH=I，优化问题等价于

argmaxtr(HTLH)arg⁡maxtr(HTLH)
s.t.HTH=Is.t.HTH=I

其实这个优化问题也不好解，但是可以用“最大k个特征值”来近似

3. Ncut

类似的，定义为 NCut(A1,A2,…Ak)=12∑i=1kW(Ai,A¯¯¯¯i)vol(Ai)NCut(A1,A2,…Ak)=12∑i=1kW(Ai,A¯i)vol(Ai)

其中，vol(A):=∑i∈Adivol(A):=∑i∈Adi

可以得到类似的最优化问题

不过区别是这里的H不是标准正交的了。

参考文献

https://www.cnblogs.com/pinard/p/6221564.html