当前位置: 游戏平台 > 互联网科技 > 正文

详解谱聚类原理

时间:2020-01-24 04:45来源:互联网科技
转自 http://blog.csdn.net/jteng/article/details/49590069 $kmeans$ 的改进算法 -- 谱聚类 公式表达如有不清,请转github 或者加QQ群..[174225475].. 共同探讨 作者 | 荔枝boy  谱聚类(SpectralClustering)算法简

图片 1

转自  http://blog.csdn.net/jteng/article/details/49590069

$kmeans$ 的改进算法 -- 谱聚类
公式表达如有不清,请转 github
或者加QQ群..[174225475].. 共同探讨

作者 | 荔枝boy

 谱聚类(Spectral Clustering)算法简单易行,其聚类性能优于传统的K-means算法。谱聚类将数据的划分转化为对图的分割,是一种基于图论的聚类方法,其直观理解为根据图内点的相似度将图分为多个子图,使子图内部的点相似度最高,子图之间点的相似度最低。

1. 相关概念科普

目录

1. 图论基础

度矩阵

度矩阵为对角矩阵,对角线上的值表示 与该点 有来往的 其他点的个数 即度 为 与节点 相连的 个数

  • 一. 拉普拉斯矩阵性质

  • 二. 拉普拉斯矩阵与图分割的联系

  • 三. Ratiocut

  • 四.总结

1.1 图的表示

  记G=(V,E)表示一个无向加权图,V表示所有顶点的集合V={v1,...,vn},E表示所有边的集合,并且任意两点vi和vj的边具有非负权值wij≥0。图的邻接矩阵为W=(wij)i,j=1,...,n,如果wij=0则表示点vi和vj之间没有连接。由于G为无向图,所以其邻接矩阵具有对称性,即wij=wij。图中任一点vi的度为di=∑nj=1wij,表示一个点与其他所有点的连接情况,图的度矩阵D为每个点的度所构成的对角矩阵D=diag{d1,...,dn}。

邻接矩阵

邻接矩阵 表示图上 各点之间 是否有联系或者联系程度, 可以是 1/0 也可以是 具体权值

图片 2

laplas1

图片 3

laplas2

这篇文章可能会有些枯燥,着重分享了谱聚类的原理中的一些思想,以及自己本人对谱聚类的一些理解。如果在看完这篇文章后,也能解决你对谱聚类的一些疑问,想必是对你我都是极好的。在之前查阅了很多关于谱聚类的资料,博客,但是发现有些地方仍不是很明白,比如为什么用拉普拉斯矩阵L的特征向量就能表示一个样本,为什么L总会有个最小特征值是0等。

1.2 相似度图的构造方法

  给定一组数据集V={v1,...,vn},将其构造为相似度图的意义在于描述点对之间的局部近邻关系。此处介绍三种构造相似度图的方法。 
  (1)ε近邻图。如果两点之间的距离小于给定值ε,则连接两点。ε的值需要根据图中各点的距离选择,使与某一点连接的点不会太多,也不会太少。 
  (2)k近邻图。如果点vj是vi的k近邻点之一,则连接两点。由于近邻点的非相互性,按此方法构造的邻接矩阵不对称,一种方法是采取“或”的方式,即如果vj是vi的k近邻点之一,或vi是vj的k近邻点之一,则连接两点;另一种方法是采取“与”的方式,如果vj是vi的k近邻点之一,并且vi是vj的k近邻点之一,则连接两点。 
  (3)全连接图。不考虑任何因素,直接将所有的点两两相连,由于图表示点之间的局部邻接特性,常用的相似性函数为s(xi,xj)=exp(−∥xi−xj∥22σ2)。

拉普拉斯矩阵

图论中的的 拉普拉斯矩阵(也被称为导纳矩阵/吉尔霍夫矩阵/离散拉普拉斯)是图的矩阵表示. 它是 度矩阵 和 邻接矩阵 的差. 拉普拉斯矩阵 结合 吉尔霍夫理论 可以用来计算图的最小生成树的个数。
拉普拉斯矩阵还可用来寻找图的其他属性: 谱图理论(spectral graph theory)
黎曼几何的Cheeger不等式有涉及了拉普拉斯矩阵的离散模拟. 这或许是谱图理论中最重要的定理也是在算法应用中最有用的facts.它通过拉普拉斯矩阵的第二特征值来近似图的最小割
谱的定义 就是:
方阵作为线性算子,它的所有特征值的全体 统称方阵的
方阵的谱半径为最大的特征值;
矩阵A的谱半径:($A^{T} cdot A$)的最大特征值。
其实,这里谱的本质是伪逆,是$SVD$中奇异值的平方

前文简略的介绍了如何将所有样本X构建成拉普拉斯矩阵,利用拉普拉斯矩阵对样本点X进行合适大小的分割,此分割不需要类标,所以是无监督分割。那么这其中具体的原理是什么呢?为什么将n个d维度的样本Xi构建成了相似度矩阵后,构建拉普拉斯矩阵L,就能通过求解L矩阵特征向量后,用特征向量表示Xi,进行kmeans聚类表示Xi的聚类效果呢?

1.3 图的Laplacian矩阵

  这里我们要讲到谱聚类中的关键内容——拉普拉斯矩阵,其定义为L=D–W,其中D和W就是上文定义的图的度矩阵和邻接矩阵。下面我们给出谱聚类中用到的拉普拉斯矩阵的一些性质。 
  (1)对任意的向量f∈Rn,有fTLf=12∑i,j=1nwij(fi−fj)2。 
  证明:(此处用到了W的对称性) 

fTLf=fTDf−fTWf=∑i=1nf2idi−∑i,j=1nwijfifj=∑i,j=1nwijf2i−∑i,j=1nwijfifj=12⎛⎝∑i,j=1nwijf2i+∑i,j=1nwijf2j⎞⎠−∑i,j=1nwijfifj=12∑i,j=1nwij(fi−fj)2

(2)L是对称半正定矩阵,该性质可由(1)直接得到。 
(3)L的最小特征值为0,对应的特征向量为常数向量1,即L的行和或列和为0。 
(4)本文假设L的特征值按照从小到大的顺序排列,0=λ1≤...≤λn。 
  此外,还有normalized Laplacian,分别定义为 
Lsym=D−12LD−12=I−D−12WD−12,和Lrm=D−1L=I−D−1W,其中两个下标sym和rw分别代表symmetric和random walk,此处不再介绍这两个矩阵的性质。

2. 谱聚类的基本思想

这里我们要知道,拉普拉斯矩阵是基于样本Xi之间构建的相似度矩阵构建的,所以拉普拉斯矩阵相当于是一个图G,该矩阵包含了各个样本点,以及样本点之间的联系的信息。假设有6个样本点,通过构建相似度矩阵,生成了拉普拉斯矩阵,有些样本点是没有联系的,如图一:

2. 谱聚类算法

2.1 聚类与图论

所谓聚类(Clustering), 就是要把一堆样本合理地分成两份或者$K​$份. 从图论的角度来说,聚类的问题就相当于一个图的分割问题. 即给定一个图$G = (V, E)​$, 顶点集$V​$表示各个样本,带权的边表示各个样本之间的相似度,谱聚类的目的便是要找到一种合理的分割图的方法,使得分割后形成若干个 子图,连接不同 子图 的边的权重(相似度)尽可能低,同 子图内 的边的权重(相似度)尽可能高.被割掉各边的权值和越小代表被它们连接的子图之间的相似度越小,隔得越远. 物以类聚,人以群分,相似的在一块儿,不相似的彼此远离
至于如何把图的顶点集分割/切割为不相交的子图有多种办法,如

  • cut/Ratio Cut
  • Normalized Cut
  • 不基于图,而是转换成SVD能解的问题

图片 4图一

2.1 图的分割问题

  谱聚类算法源于图的分割(cut),首先将所有的样本点连接成图,然后将图分割成不同的子图,使得不同子图之间的连接权值最小。 
  定义两个子图之间的连接权值为W(A,B)=∑i∈A,j∈Bwij,记A¯¯¯为A的补集,为了表达方便,我们记vi∈A为i∈A。如果将图分割为k个子图A1,...,Ak,那么最优分割问题可通过最小化如下表达式来实现: 

cut(A1,...,Ak)=12∑i=1kW(Ai,Ai¯¯¯¯)

   然而,此优化问题通常不能生成有效的分割,它会将图中的一个点与其余n−1个点分割开来,如下图所示,导致图的分割不均衡。 

图片 5

解决该问题的有效办法是让每个子图都有合理的大小,子图大小的度量方式不同就会得出不同的最小分割问题,常用的两种方法是RaioCut和Normalized Cut,分别如下: 
RatioCut(A1,...,Ak)=12∑i=1kW(Ai,Ai¯¯¯¯)|Ai|=∑i=1kcut(Ai,Ai¯¯¯¯)|Ai| 
Ncut(A1,...,Ak)=12∑i=1kW(Ai,Ai¯¯¯¯)vol(Ai)=∑i=1kcut(Ai,Ai¯¯¯¯)vol(Ai) 
这两个目标函数均将子图的大小作为分母,这样就可以使每个子图不会太小,其中RatioCut以子图中点的个数|Ai|作为子图大小的度量,Normalized Cut以子图内所有点的度的和作为子图大小的衡量,即vol(Ai)=∑j∈Aidj。 
  下面我们分别讨论RatioCut和Normalized Cut是如何通过谱聚类来求解的。

2.2 最小割

在将数据从点集的结构转换为了图的结构后,我们可以引入更多图论中的概念来帮助理解聚类的本质. 比如说最小割的概念(Minimum cut)
最小割是指去掉图中的一些带权边,在使得图从联通图变为不联通图的前提下,尽可能的让去掉的边权值之和尽可能小。对于数据的相似性图来说,最小割就是要去除一些很弱的相似性,把数据点从一个互相连接的整体分为两个或者多个独立的部分,这其实就是一个聚类的过程。去除的权值就是聚类后不同组别间的相似程度,我们希望这个值尽可能的小,也就是希望不同组别之间的差距尽可能的大
不过,仅仅是用最小割来聚类存在着一些缺陷,因为我们只考虑了不同类的点之间相似度要小,而一个好的聚类还要具有同一类点相似度大的特征。比如下图就是一个例子,一个好的聚类应该是在绿线处分割整个图,但使用最小割却会割在红色的位置

图片 6

specc3

如下图所示,每个顶点是一个样本,共有7个样本(实际中一个样本是特征向量). 边的权值就是样本之间的相似度. 然后我们需要分割,分割之后要使得连接不同组之间的边的权重尽可能低(组间相似度小),组内部的边的权重尽可能高(组内相似度高)

图片 7

specc1

比如我们把中间的边去掉,就满足上面的簇间相似性最小,簇内相似性最大。如下图

图片 8

specc2

我们想要对图中的节点进行分割归类,得到一个比较合理的样本分割。

2.2 求解RatioCut

  首先从二聚类问题开始分析,其目标函数为最小化 

RatioCut(A,A¯¯¯)=cut(A,A¯¯¯)(1|A|+1|A¯¯¯|)

定义向量f=(f1,...,fn)T∈Rn,其每个元素的定义如下: 

fi=⎧⎩⎨⎪⎪|A¯¯¯|/|A|−−−−−−√−|A|/|A¯¯¯|−−−−−−√ifvi∈Aifvi∈A¯¯¯

结合图的Laplacian矩阵,我们可以得到RatioCut问题,推导过程如下:

fTLf=12∑i,j=1nwij(fi−fj)2=12∑i∈A,j∈A¯wij⎛⎝∣∣A¯∣∣|A|−−−√+|A|∣∣A¯∣∣−−−√⎞⎠2+12∑i∈A¯,j∈Awij⎛⎝−∣∣A¯∣∣|A|−−−√−|A|∣∣A¯∣∣−−−√⎞⎠2=12∑i∈A,j∈A¯wij⎛⎝∣∣A¯∣∣|A|+|A|∣∣A¯∣∣+2⎞⎠+12∑i∈A¯,j∈Awij⎛⎝∣∣A¯∣∣|A|+|A|∣∣A¯∣∣+2⎞⎠=12⎛⎝∑i∈A,j∈A¯wij+∑i∈A¯,j∈Awij⎞⎠⎛⎝∣∣A¯∣∣|A|+|A|∣∣A¯∣∣+2⎞⎠=cut(A,A¯)⎛⎝∣∣A¯∣∣+|A||A|+|A|+∣∣A¯∣∣∣∣A¯∣∣⎞⎠=|V|cut(A,A¯)⎛⎝1|A|+1∣∣A¯∣∣⎞⎠=|V|RatioCut(A,A¯) 
其中,|V|表示所有点的个数,给定样本点后,|V|是个常数。 
  因为,求解RatioCut问题可以转变为最小化fTLf的问题,其中f的取值如上面所定义,然而,该离散优化问题是NP-hard,因此,我们将其进行松弛,使fi能够取任意实数。同时,为了和原问题尽量保持一致,我们加入f的两个约束,f⊥1→和∥f∥=n−−√,这两个约束可从f的定义得到。最后,二聚类问题就转化成了有约束的优化问题: 

minf∈RnfTLfs.t.f⊥1→,∥f∥=n−−√

根据Rayleigh-Ritz定理可知,该问题的解为Laplacian矩阵L的最小特征值所对应的特征向量,由于L的最小特征值为0,对应的特征向量为常数向量1,不满足约束条件,因此,应取第2小的特征值所对应的特征向量。 
  求解上述优化问题后,要将数据集分为2个簇,我们可简单地采取如下的方式: 

{vi∈Avi∈(¯A)iffi≥0iffi<0

  上述的二聚类问题可以很容易地推广到k聚类问题,如果将一个数据集分为k个子集Ai,...,Ak,首先定义k个示性向量H=(h1,...,hk)T,其中

hij={1/|Aj|−−−√0ifvi∈Ajotherwise,i=1,...,n;j=1,...,k

由该定义可知,H的列相互正交,即HTH=I。类似上面的推导(此处不再给出详细过程): 

hTjLhj=cut(Aj,Aj¯¯¯¯)|Aj|

此外,hTjLhj=(HTLH)jj,因此

RatioCut(A1,...,Ak)=∑j=1khTjLhj=∑j=1k(HTLH)jj=Tr(HTLH)

所以,多聚类的RatioCut问题可以转化为最小化Tr(HTLH)的问题,H的取值如上面所定义。同样,我们将该NP-hard问题松弛,使H的元素取任意实数,松弛问题就变为:

minH∈Rn×kTr(HTLH),s.t.HTH=I

这是标准的迹最小化问题,其解为L的的前k个特征向量所构成的矩阵。最后采用k-means方法对该矩阵的行进行聚类,就可以实现对该数据集的k聚类。

3. 算法步骤

谱聚类算法主要有下面几部分:

分割成如图二的效果:

2.3 求解Normalized Cut

  类似于RatioCut,下面我们简要给出Normalized Cut的实现过程。 
  首先分析二聚类的情况,定义示性函数如下: 

fi=⎧⎩⎨⎪⎪vol(A¯¯¯)/vol(A)−−−−−−−−−−−√−vol(A)/vol(A¯¯¯)−−−−−−−−−−−√ifvi∈Aifvi∈A¯¯¯

按照该定义,f具有性质(Df)T1→=0和fTDf=vol(V),并且可以证明fTLf=vol(V)Ncut(A,A¯¯¯),加上松弛条件,使f可以取任意实数向量,Normalized Cut可以转化成有约束的优化问题 

minf∈RnfTLf,s.t.Df⊥1→,fTDf=vol(V)

  该问题需要求解广义特征向量问题Lf=λDf, f取L的第二小的广义特征值对应的特征向量。 
  再扩展到k聚类问题,定义k个示性向量H=(h1,...,hk)T,其中

hij={1/vol(Aj)−−−−−−√0ifvi∈Ajotherwise,i=1,...,n;j=1,...,k

按照该定义,H具有性质hTjDhj=1,那么HTDH=I,并且可以证明

hTjLhj=cut(Aj,Aj¯¯¯¯)/vol(Aj)

因此,Ncut(A1,...,Ak)=Tr(HTLH),加上松弛条件,使H的元素可以取任意实数,Normalized Cut就可以转化为如下有约束的优化问题:

minH∈Rn×kTr(HTLH)s.t.HTDH=I

该问题的解为广义特征值问题Lh=λDh的前k个特征向量所构成的矩阵。最后采用k-means方法对该矩阵的行进行聚类,就可以实现对该数据集的k聚类。

3.1 未正则拉普拉斯矩阵 的谱聚类算法

图片 9图二

2.4 小结

  针对以上两种图分割方法,谱聚类算法的步骤如下: 
  Step1:将每个样本看做图的顶点,构造无向加权图; 
  Step2:计算图的邻接矩阵W和拉普拉斯矩阵L; 
  Step3:根据图的分割准则计算拉普拉斯矩阵的前k个特征向量; 
  Step4:将拉普拉斯矩阵的前k个特征向量构成矩阵Y,把Y的每一行看做一个样本,然后用k-means方法对Y进行聚类。

3.1.1 计算得到图的邻接矩阵 $W$,以及拉普拉斯矩阵 $L$;

给定样本的原始特征,我们需要计算两两样本之间的相似度值,才能构造出邻接矩阵$W$ . 我们一般使用高斯核函数来计算相似度。公式如下:

$$S(x,y)=e{-\frac{||x-y||{2}}{2sigma^{2}}}$$

$$S(x,y)=e{-{\frac{\sqrt{\sum_{i=1}{k}left(x_{i}-y_{i}right){2}}}{2\sigma2}}}$$

如果样本$x,y$是对应数据集$dt$的第$i,j$行,则上述公式中的

$$
begin {aligned}
sqrt{sum_{i=1}{k}\left(x_{i}-y_{i}\right){2}}&= sqrt{sum_{i,j=1}{n}(dt[x,]-dt[y,])2}
&= sqrt{sum_{i,j=1}^{n}(dt[i,]-dt[j,]) * t(dt[i,]-dt[j,])}
&=dist(dt)
end {aligned}
$$

高斯核相似度公式用 R 来表达:

S(dt) = exp(-(dist(dt)^2)/(2*sigma^2))

其中$x$ 和 $y$ 是两个样本(行向量),$x_{i}$ $y_{i}$是样本$x,y$对应的第$i$个原始特征向量,我们可以计算出它们二者之间的相关性(高斯核). 注意,邻接矩阵的对角线元素一致等于零. 这样我们就得到了邻接矩阵$W$

拉普拉斯矩阵 $L = D - W$, 其中$D$为上面图的度矩阵,度是图论中的概念,也就是矩阵E行或列的元素之和。后面我们就要基于矩阵$L$来进行研究

不得不感叹前辈们的聪明智慧,将一个表示样本点联系的图分割,通过拉普拉斯矩阵转换成了矩阵求解的问题。先别着急想拉普拉斯矩阵L与图像分割有什么联系,我们先单纯的从数学角度来L矩阵有什么性质。假设一共有n个样本Xi,现已知得到样本点构建的相似度矩阵S(本章不在此展开,构建相似度矩阵有很多种方式,比如欧式距离,高斯距离等),S是大小为nn的矩阵,S_ij记录了Xi与Xj样本间的联系。通过相似度矩阵S构建邻接矩阵W(这里构建W的方式也有很多,比如K近邻,全连接构建W等),通过W_ij创建对角度矩阵D,大小为nn,其中对角线元素,其余位置Dij=0。构建了相似度矩阵W和度矩阵D后,就得到了拉普拉斯矩阵L=D-W。

3. 总结

  谱聚类相当于先进行非线性降维,使原始数据点能够线性可分,最后再使用k-means聚类就可以得到比较好的聚类效果。 
  谱聚类算法也存在以下几点不足: 
  (1) 谱聚类的松弛条件是对原问题的一个近似,但是并不能保证该近似是合适的,其误差有可能非常大,而且导致聚类问题不稳定; 
  (2) 构造相似度矩阵的尺度参数根据经验设定,尺度参数的选择对聚类效果影响较大; 
  (3) 同其他聚类方法一样,聚类数目的选择难以确定; 
  (4) 根据图最小分割的目标函数可知,谱聚类适用于均衡分类问题,即各簇之间点的个数相差不大,对于簇之间点个数相差悬殊的聚类问题,谱聚类则不适用。 
  以下一组图均为采用谱聚类方法进行聚类的结果,左侧一列的数据点个数分布比较均衡,聚类效果比较好,可以看出,右侧一列数据点的分布不均衡,谱聚类算法仍然将数据分成几个均衡的簇,而不能体现数据的分布结构。 

图片 10 图片 11

图片 12 图片 13

图片 14 图片 15

3.1.2 聚类划分准则

关于划分准则的问题是聚类技术中的核心。谱聚类被看作属于图论领域的问题,那个其划分也会和边的权重有关

准则1:最小化进行分割时去掉的边的权重之和
$$cut (A_{1} ldots A_{k}) = frac {1}{2} cdot sum_{i=1}^{k} W (A_{i},overline{A_{i})}$$
这个准则直观地让分割之后簇之间的相似度最小了。但是有个问题,就是这个准则没有考虑到簇的大小,容易造成一个样本就能分为一个簇。为了避免这个问题,有了下面的准则
准则2:考虑簇的大小
$$RationCutleft(A_{1},ldots ,A_{k} right)=frac{1}{2} cdot sum_{i=1}^{k} frac{Wleft(A_{i},overline{A_{i}}right)} {||A_{i}||}$$

准则2相比于准则1的改进,类似于$C4.5$中的增益比率和$ID3$的信息增益的改进。在$RatioCut$中,如果某一组包含的顶点数越少,那么它的值就越大。在一个最小化问题中,这相当于是惩罚,也就是不鼓励将组分得太小。现在只要将最小化$RatioCut$解出来,分割就完成了。不幸的是,这是个$NP$难问题。想要在多项式时间内解出来,就要对这个问题作一个转化了。在转化的过程中,就用到上面提到的L的那一组性质,经过若干推导,最后可以得到这样的一个问题
$$
begin {aligned}
min_{H in mathbb{R}^{n cdot k}} (Tr(H^{T}LH))
s.t. H^{T}H=I
end {aligned}
$$
但到了这关键的最后一步,咱们却遇到了一个比较棘手的问题,即由之前得到的拉普拉斯矩阵的性质$L$最小特征值为$0$,对应的特征值为$1$.其不满足$f$与$1$正交的条件,那该怎么办呢?根据论文“A Tutorial on Spectral Clustering”中所说的Rayleigh-Ritz 理论,我们可以取第$2$小的特征值,以及对应的特征向量$v$
更进一步,由于实际中,特征向量$v$里的元素是连续的任意实数,所以可以根据$v$是大于0,还是小于0对应到离散情况下的$f=(f_{1},ldots ,f_{n}) prime in mathbb{R}^{ncdot k}$,决定$f$是取$sqrt{frac{|A|} {|overline{A}|}}$还是取 $-sqrt{frac{|A|} {|overline{A}|}}$ .而如果能取$v$的前$k$个特征向量,进行$Kmeans$聚类,得到$K$个簇,便从二聚类扩展到了$K$聚类的问题 ( $overline{A}$表示A的补集)
而所要求的这前$K$个特征向量就是拉普拉斯矩阵的特征向量(计算拉普拉斯矩阵的特征值,特征值按照从小到大顺序排序,特征值对应的特征向量也按照特征值递增的顺序排列,取前$K$个特征向量,便是我们所要求的前$K$个特征向量)!
所以,问题就转换成了:求拉普拉斯矩阵的前$K$个特征值,再对前$K$个特征值对应的特征向量进行 $Kmeans$聚类。而两类的问题也很容易推广到$K$类的问题,即求特征值并取前$K$个最小的,将对应的特征向量排列起来,再进行$Kmeans$聚类. 两类分类和多类分类的问题,如出一辙
$RatioCut$巧妙地把一个NP难度的问题转换成拉普拉斯矩阵特征值(向量)的问题,将离散的聚类问题松弛为连续的特征向量,最小的系列特征向量对应着图最优的系列划分方法。剩下的仅是将松弛化的问题再离散化,即将特征向量再划分开,便可以得到相应的类别。不能不说妙哉!

我们发现L矩阵是一个全对称矩阵,对角线元素是度矩阵中对应的Dii,其他位置的元素L_ij=-W_ij。

3.1.3 求出$L$的前$k$个特征值及对应的特征向量

在本文中,除非特殊说明,否则“前$k$个”指按照特征值的大小从小到大的顺序)以及对应的特征向量
PS: $L=D-W$是计算前 $k$小的特征向量,如果是$L=W-D$则是计算前 $k$大

该矩阵第一个性质,任意一个1*n维的f向量,我们都能得到如下公式,具体推导如公式一:

3.1.4 根据新生成的特征矩阵进行$kmeans$聚类

把这$k$个特征(列)向量排列在一起组成一个$n cdot k$的矩阵,将其中每一行看作$k$维空间中的一个向量,并使用$Kmeans$算法进行聚类. 聚类的结果中每一行所属的类别就是原来 Graph 中的节点亦即最初的$n$个数据点分别所属的类别

图片 16公式一

3.1.5 总结一下完整的谱聚类算法的流程

  • 确认输入参数:一个描述数据相似性图的邻接矩阵$W$,和聚类的目标类数目$k$
  • 计算度矩阵 $D$和 拉普拉斯矩阵 $L$
  • 计算特征值方程$Lcdot y = lambda cdot D cdot y$的前$k$个特征向量,记为$y_{1} ldots y_{k}$
  • 通过 $y_{1} ldots y_{k}$按列排成矩阵 $Y in mathbb{R}^{n cdot k}$
  • $Y$ 的第 $i$行的行向量记为 $x_{i} prime (i leq n)$
  • 对 $x_{i} prime$ 进行 $kmeans$ 聚类
  • 将 $x_{i} prime$ 的类别分配给 $x_{i}$, 即 $class(x_{i})=class(x_{i} prime)$
  • 输出聚类结果
    整个过程都只用到了包括求解特征值等基本线性代数运算,因此谱聚类是一种推导有些繁杂,但是实现很简单的聚类算法

性质有什么用呢,举个例子,我们知道L是一个矩阵,假设该L代表的样本Xi是全连接的,一个类。f是任意一个向量,其实Lf=λf,即λ是L的特征值,而f是L的特征向量。所以f’Lf=f’λf=λf’f,而f’*f是一个常数,所以我们会发现f’Lf是一个定值,假如λ=0,则f’Lf=0,求出来的f就是L对应特征值为0的特征向量。根据性质一,我们会发现W_ij>0,则要想f’Lf=0,必须有f_i=f_j。我们发现Xi的真实情况是都在一类中,而求出来的f’Lf=0中的特征向量有f_i=f_j这个性质。我们可以将真实情况中Xi彼此为一类的现象与L的0特征值对应的f_i=f_j这个性质联系,发现二者始终同步且二者只能互相依存。所以在此,我们可以设置拉普拉斯矩阵L的0特征值对应的特征向量f为全1向量,可以用f_i在某种程度代表Xi。求出的L的0特征值对应特征向量f_i=f_j,刚好可以代表Xi与Xj都是同一类。

3.2 正则的拉普拉斯矩阵 的谱聚类算法

编辑:互联网科技 本文来源:详解谱聚类原理

关键词:

  • 上一篇:没有了
  • 下一篇:没有了