谱聚类算法总结.doc

谱聚类算法总结
聚类三种方法：k-means聚类、密度聚类、层次聚类和谱聚类SpectrumClustering
简述
谱聚类是一种基于图论的聚类方法——将带权无向图划分为两个或两个以上的最优子图，使子图内部尽量相似，而子图间距离尽量样可以最小化cut(A],A2,..Ak),但是却不是最优的切图，如何避免这种切图，并且找到类似图中"BestCut"这样的最优切图呢？
谱聚类之切图聚类
RatioCut切图
RatioCut切图为了避免最小切图，对每个切图，不光考虑最小化cut(A],A2,..Ak)，它同时还考虑最大化每个子图点的个数，即：
接下来是最小化这个RatioCut函数:引入指示向量hj={h],h2,..hk},j=],2,..k
0*A.
-==“；三j!
{h1,h2,..hk},j=],2,..k，对于任意一个向量hj,它是一个n维向量hj,它是一个n维向量，定义叩为:
对于hiTLhi:
呀匸抚=+im—h说)
In—1
=豆(52^'^(—=7-O)2-I-Y世唤e—)
对应的RatioCut函数表达式为:
ct
血血CW⑷,…山)=ykfLhj=工=tr[HTLH)
f-1
注意到HTH=I,则我们的切图优化目标为:
=I
v
对于hiTLhi,我们的目标是找到最小的L的特征值,e而
i-1
则我们的目标就是找到k个最小的特征值，一般来说，k远远小于n,也就是说，此时我们进行了维度规约，将维度从n降到了k,从而近似可以解决这个NP难的问题。
通过找到L的最小的k个特征值，可以得到对应的k个特征向量，这k个特征向量组成一个nxk维度的矩阵，即为我们的H。一般需要对H矩阵按行做标准化，即
由于我们在使用维度规约的时候损失了少量信息，导致得到的优化后的指示向量h对应的H现在不能完全指示各样本的归属，因此一般在得到nxk维度的矩阵H后还需要对每一行进行一次传统的聚类，比如使用K-Means聚类.
Ncut切图
Ncut切图和RatioCut切图很类似，但是把Ratiocut的分母|Ai|换成vol(Ai).由于子图样本的个数多并不一定权重就大，我们切图时基于权重也更合我们的目标，因此一般来说Ncut切图优于RatioCut切图。
1吕W()
对应的，Ncut切图对指示向量hh做了改进。注意到RatioCut切图的指示向量使用的是
1
标示样本归属，而Ncut切图使用了子图权重
优化目标函数为：
£t
NGiit\A-,A-2....Ak)=工眄L松=工迅工LH衣=tr(HTLH"\
i-1i-1
来标示指示向量h,定义如下:
对于
暉Lht=
3\:〉[他-
T7i-™1西一：y(工比嘶(
_J'J^vol\Aj)
1t
1$—.L
:+皿(生V*)
诚⑷)'
mEAi
JE."
1.-
〒(曲地，脱
_0)3—工理耐刃(0,)
,;”应川(Ay)
V—二7
(11)
HTDH=:
72
J-1
1
加（比）
最终为：
(HTLH)s.£.HTDH=I'