谱聚类中为什么要用拉普拉斯矩阵前K个特征向量组的前k行,做K均值?


如标题,搞不清楚这里为什么这样。过程是比较简单,但是不懂 为什么 。

QQ图片20150331174616.png
已邀请:

岳翼

赞同来自: July LostOsiris SuiterChik JoyceWYJ


今天画了图,才在实践上理解了上面那句话,特把经验分享出来,感觉这样直观一点,少纠结一些。

谱聚类小例子:
1.随便画出一个连接图,加上链接权重。

QQ截图20150401101415.png

2.构造拉普拉斯矩阵:

QQ截图20150401101515.png


此时0 特征值对应的特征向量,除了全1向量之外,只有[1 1 1 0 0 ]T和 [0 0 0 1 1 ]T两个向量,让他们以列排列,形成矩阵:

QQ截图20150401101540.png


那么,这个矩阵的第一列设为x1,第二列设为x2就,将每个行向量作为点,画到x1和x2坐标上去


1111.png


这样一聚类,是不是刚好把原来问题的123点分为一类,4,5点分为了另一类?!
所以,实践上这样是可行的,拉普拉斯矩阵特征向量,包含了我们需要的分类信息。

不过理论和实践相结合才是王道,下面是邹博士给出的理论解释:

为表述方便,给出如下简称:“向量f可取实数”,是指的“n维向量f的每个维度fi都是实数”。下面的行文中,为了上下连贯,在不引起歧义的前提下,凡是“向量的取值为实数域”、“矩阵扩展到实数域”等表述,都是指的它们的元素取实数。

关于谱聚类中求取特征向量以及使用Y矩阵做k-means的解释:

1、首先考虑全图是全连通状态,并且做2分:定义f为子图划分的指示向量,则根据关于RatioCut的论述,f'Lf的值最小即为该待求向量f,即为聚类的最终目标。同时,使用Rayleigh-Ritz定理,在f可取实数的前提下,f'Lf取最小的f,即拉普拉斯矩阵L的次小特征向量。而最终目的是取f为指示向量,而非实数域上的解。因此,将f离散化:最简单的方案——大于0是一簇,小于0是另一簇(当然有别的方案,如:找出这n个数的分割点x,使得sigma(fi-x)^2最小)。

2、若将2分扩展到k分,仍然只考虑全连通状态:这时,目标函数是本来应该是Trace(H'LH)最小,这里,H是k列的,对应k个子图划分的指示向量;H的解即为最终结论,同样由于NP难解,把指示向量组成的矩阵H扩展到实数域上,根据Rayleigh-Ritz定理,L的前k个特征向量组成的矩阵Hr,即为使得Trace(H'LH)最小的解。仿照2分的情况,对这个Hr矩阵离散化,从而近似得到H。类比2分情况离散化的方案,这里仅仅将数值fi(向量f的行向量)扩展到了k维(矩阵Hr的行向量)。最简单的莫过于对Hr的每一行做K-means了。

3、换个角度来理解:对于给定的相似度矩阵W,将这个矩阵W的每一行Wi作为输入点,得到n个点Wi(1≤i≤n),每个Wi也是n维。这n个点Wi做k-means,就是聚类的最终结果。由于维度是n维,使用PCA的方式降维,取特征值最大的k个值对应的特征向量,组成矩阵P,仍然将P的每一行看做一个点(注:1、已经通过PCA把n维的Wi降为k维的Pi了;2、P仍然有n行,即Pi共n个点),做K-means,可以降低时间和空间复杂度。而谱聚类中的拉普拉斯矩阵L定义为D-W,D是每个结点的度。所以,W的前k个最大的特征向量即为L的钱k个最小的特征向量。从而,PCA的做法和谱聚类的做法,完全相同。

要回复问题请先登录注册