[关闭]
@frank-shaw 2015-08-03T10:39:56.000000Z 字数 17566 阅读 7792

3月机器学习在线班第七课--聚类方法

机器学习


相似度/距离计算方法总结

在我们正式讲解聚类算法之前,让我们来简单总结一下我们已有的距离计算方法。聚类,无法避免的就是需要计算距离,而不同计算距离方法的选择,则有可能导致差异较大的不同结果。

闵可夫斯基Minkowski距离

dist(X,Y)=(i=1n|xiyi|p)1p

p=2时,Minkowski距离即为我们熟悉的欧式距离。

杰卡德相似系数(Jaccard):

J(A,B)=|A||B||A||B|

余弦相似度(cosine similarity):
cos(θ)=aTb|a||b|

Pearson相似系数
ρXY=cov(X,Y)σXσY=E[(XμX)(YμY)]σXσY=ni=1(XiμX)(YiμY)ni=1(XiμX)2ni=1(YiμY)2

相对熵(K-L距离):
D(p||q)=xp(x)p(x)q(x)=Ep(x)logp(x)q(x)

聚类的基本思想

在我们熟悉的机器学习算法和模型中,大部分情况下训练数据都是带有label(标签)的,这样的算法是有监督学习算法。当训练数据没有label(标签)时,便称之为无监督学习。聚类算法就是无监督学习中最常见的一种,给定一组数据,需要聚类算法去挖掘数据中的隐含信息。聚类算法的应用很广:顾客行为聚类,google新闻聚类等。

定义:给定一个有n个对象的数据集,聚类将数据划分为k个簇,而且这k个划分满足两个条件:(1)每个簇至少包含一个对象;(2)每个对象属于且仅属于一个簇。

基本思想:对给定的k,算法首先给出一个初始的划分方法,以后通过反复迭代的方法改变划分,使得每一次改进之后的划分方案都较前一次更好。

基础聚类方法--K-means算法

K-means算法,也被称为K-均值,是一种得到最广泛使用的聚类算法,它也可以成为其他聚类算法的基础。

基本思想: K-means算法首先随机地选择k个对象,每个对象初始地代表一个簇的平均值或中心。对剩余的每个对象根据其与各个簇中心的距离(之前的各种距离的定义,在这里派上了用场,可以根据实际需求来选择不同的距离定义),将它赋给最近的簇。然后重新计算每个簇的平均值。这个过程不断重复,直到准则函数函数收敛(准则函数常常使用最小均方误差)。

算法流程:

设给定输入数据为S=x(1),x(2)...,x(m),K-means算法如下:
(1)选取初始的k个聚类中心μ1,μ2...μkRn;
(2)对每个样本数据而言,将其类别标签设为距离其最近的聚类中心的标签,即label(i)=argminj=||x(i)μj||;
(3)将每个聚类中心的值更新为与该类别中心相同类别的所有样本的平均值,即

μj:=mi=11{label(i)=j}x(i)mi=11{label(i)=j}

(4)重复(2)(3)步,直到聚类中心的变化(Δμj)小于规定的阈值为止。

下图即为一个简单的示例(k=2):
k-means聚类算法流程

在K-means算法中,如何选择初始的聚类中心是一个普遍的问题(该算法是初值敏感的)。同时,K-means算法只能够保证收敛到一个局部极值,无法保证收敛到全局最优。一个较为简单的解决办法是随机初始化多次,以最优的聚类结果为最终结果。

在聚类结束后,如果一个中心没有得到任何样本(这是可能的),那么需要去除这个中心点,或者重新初始化。

密度聚类方法

密度聚类方法的指导思想是:只要一个区域中的点的密度大于某个阈值,就把它加到与之相近的类簇中去。这类算法可以克服基于距离的算法只能够发现“类圆形”(凸)的聚类的缺点,可以发现任何形状的聚类,且对噪声数据不敏感。但是计算密度单元的计算复杂度大,需要建立空间索引来降低计算量。

两个主要的密度聚类方法:DBSCAN算法、密度最大值算法。

DBSCAN算法

DBSCAN(Density-Based Spatial Clustering of Applications with Noise,具有噪声的基于密度的聚类方法)是一种基于密度的空间聚类算法。该算法将具有足够密度的区域划分为簇,并在具有噪声的空间数据库中发现任意形状的簇,它将簇定义为密度相连的点的最大集合
可以想象一下人类聚居的过程,黄河(母亲河)边上首先会聚集更多的人,当人数足够多了之后,就会产生城市(类似于簇的概念)。可以想象一下城市的形状是不规则的,但城市是以空间上的人口密度作为划分基础的。

算法设计的基本定义:
1.对象的ϵ-领域:在给定对象的半径ϵ内的区域。
2.核心对象(core point):对于给定的数目m(人为设定的标准),如果一个对象的ϵ-领域至少包含了m个对象,那么称该对象为核心对象。
3.直接密度可达(directly density-reachable):给定一个对象集合D,如果对象p是在对象qϵ-领域内,且q是一个核心对象,那么我们说对象p从对象q出发是直接密度可达的。

Tips:以下图片帮助理解:如图ϵ=1cm,m=5,可以知道q是一个核心对象,从对象q出发到对象p出发是直接密度可达的。
解释密度算法概念图片1

4.密度可达(density-reachable):如果存在一个对象链p1,p2...,pn,令p1=Q,pn=P。假设对任意i[1,n),有piD,且pi+1是从pi关于ϵ和m直接密度可达的,那么对象P是从对象Q关于关于ϵ和m密度可达的。
5.密度相连(density-connected):如果对象集合D中存在一个对象o,使得对象p和q是从o关于ϵ和m密度可达的,那么对象p和q是关于ϵ和m密度相连的。
6.簇(cluster):一个基于密度的簇是最大的密度相连对象的集合
7.噪声:不包含在任何簇中的对象我们称之为噪声。

Tips:以下图片帮助理解:如图m=3,红色部分的点都是核心对象,同样的,他们彼此之间是密度可达的。点B和点C不是核心对象,但是它们关于点A是密度可达的,于是它们属于同一个簇。点N是噪声点。
解释密度算法概念图片2

通过以上定义,我们可以知道这些定义是一层层递进的,慢慢理解下来其实不难。我们也可以发现密度可达并不是双向关系的,而密度相连则是双向关系的。
现在假设点p是一个核心对象,那么通过不断搜索数据(这些数据可以是核心对象也可以不是核心对象)就可形成一个以p为核心对象的簇。每一个簇至少包含一个核心对象,非核心对象可以是簇的一部分,它(非核心对象)构成的是簇的边缘(edge)。

DBSCAN算法流程
DBSCAN需要两个参数:ϵ和m。该算法一开始选择任意一个未访问过的点p作为起始点,通过查看对象p的ϵ-领域中数据点的个数k,如果k<m,那么该点会被看成是异常点(值得注意的是该点有可能是另外一个核心对象的密度相连对象,到后来也可能是簇的一部分);如果k>m,那么就会构造一个以点p为核心对象的簇(所有密度相连对象的集合)。在这个过程中还会有簇的合并的过程。
不断重复以上过程,就可以将原始数据区分为多个簇以及噪声点。
伪代码如下:

DBSCAN(D, eps, MinPts) {
   C = 0
   for each point P in dataset D {
      if P is visited
         continue next point
      mark P as visited
      NeighborPts = regionQuery(P, eps)
      if sizeof(NeighborPts) < MinPts
         mark P as NOISE
      else {
         C = next cluster
         expandCluster(P, NeighborPts, C, eps, MinPts)
      }
   }
}

expandCluster(P, NeighborPts, C, eps, MinPts) {
   add P to cluster C
   for each point P' in NeighborPts { 
      if P' is not visited {
         mark P' as visited
         NeighborPts' = regionQuery(P', eps)
         if sizeof(NeighborPts') >= MinPts
            NeighborPts = NeighborPts joined with NeighborPts'
      }
      if P' is not yet member of any cluster
         add P' to cluster C
   }
}

regionQuery(P, eps)
   return all points within P's eps-neighborhood (including P)

让我们来看看某一个实际的聚类效果图:

解释密度算法概念图片3

密度最大值聚类算法

密度最大值聚类是一种简洁优美的聚类算法,可以识别各种形状的类簇,并且参数很容易确定。这是2014年最新的论文,大家可以点击此处看看论文
首先,让我们给出以下定义:

局部密度ρi:

ρi=jχ(dijdc),χ(x)={1,x<00,otherwise

高局部密度点距离δi:

δi=minj:ρj>ρi(dij)

在密度高于对象i的所有对象中,到对象i最近的距离,即为高局部密度点距离。对于密度最大的那个对象,设置δi=max(dij)
- 如果将局部密度ρi看成是个体i的财富值,那么高局部密度点距离δi可以看做是比个体i有钱并且距离个体i最近的距离。
- 只有那些密度是局部或者全局最大的点才会有远大于正常值的高局部密度点距离。

簇中心的识别:
那些有着比较大的局部密度ρi和很大的高局部密度点距离δi被认为是簇的中心;高局部密度点距离δi很大但是局部密度ρi较小的点时异常点。
下面的图可以给我们清晰演示簇中心与异常点的识别。左图为点的分布,右图横坐标为ρ,纵坐标为δ
密度最大值算法演示图
从右图可以识别出:点1、10都是簇中心,而点28、27、26都是异常点,再反过来看左图,确实如此!

簇中心找到后,剩余的每个点就会被划分到比该点具有更高密度的最近邻居点所属簇当中去,当然,如果该点的最近邻居点还未找到所属簇,那么就会以最近邻居点作为新的起始点,寻找具有更高密度的最近邻居点所属簇。这个过程就相当于:

现在有五个党派(簇中心),国内的每个人都要表明自己是哪个党派的,但是公民A并不清楚他应该属于哪个党派,于是他就去问他的大哥B(比A具有更高密度的最近邻居点),A觉得我大哥B属于哪个党派我就属于哪个党派吧;但是有可能公民B也不知道自己应该属于哪个党派呀,B就回去问他的大哥C,跟随C所属的党派。以此类推下去,所有人都会找到自己的党派(簇中心)。

可靠性分析:对边界和噪声的认识
在聚类分析中,通常需要确定每个点划分给某个簇的可靠性。在该算法中,可以首先为每个簇定义一个边界区域(border region),即划分给该簇但是距离其他簇的点的距离小于dc的点的集合。然后为每个簇找到其边界区域的局部密度最大的点,令其局部密度为ρh.
该簇中所有局部密度大于ρh的点被认为是簇核心的一部分(即将该点划分给该类簇的可靠性很大),其他的点被认为是该类簇的光晕(halo),即可以认为这些点是噪声。

举例分析:下图中A图为生成数据的概率分布,B,C二图为分别从该分部中生成4000,1000个点。D,E分别是B,C两组数据的决策图(decision tree),可以看到两组数据都只有五个点有较大的ρi\delta_i$。这些点作为簇的中心,在确定了簇中心之后,每个点被划分到各个簇中(彩色点),或者是划分为簇的光晕(黑色点)。F图展示的是随着抽样点数量的增多,聚类的错误率在逐渐下降,说明该算法是鲁棒的。
密度最大值算法可靠性分析图

谱聚类

谱聚类算法涉及到较多的矩阵分析中的知识,在正式介绍算法之前,容我简单介绍两个知识点:
1. 实对称矩阵的特征值是实数;
2. 实对称矩阵的不同对称值对应的特征向量是正交的;

看到这两个都是关于实对称矩阵的知识点,我们头脑中的某些知识点就要翻出来了。那么我们来正式介绍谱和谱聚类吧~

谱:方阵作为线性算子,它的所有特征值统称为方阵的
谱半径:方阵的谱半径即为最大的特征值;矩阵A(非方阵)的谱半径:(ATA)的最大特征值;
谱聚类:它是一种基于图论的聚类方法,通过对样本数据的拉普拉斯矩阵(具体含义稍后解释)的特征向量进行聚类,从而达到对样本数据聚类的目的。

谱聚类包含概念

相似度图(similarity graph):给定一组数据x1,x2,...,xn,记任意两个点之间的相似度(是距离的减函数)为sij=<xi,xj>,那么最初始的聚类目标就是将数据集中的数据依据相似度分组,同一组的数据相似度较高,不同组之间的数据相似度较低。假如我们没有获取到比相似度更多的信息,那么一个比较nice的展示数据的方式就是相似度图G=(V,E)【其中V表示点集,E表示边集,图模型的基本概念】。图模型中点集V={v1,v2,...vn},顶点vi表示的是样本数据xi。当点vivj之间的相似度sij大于某一特定阈值的时候,那么我们说vivj是相连着的,vivj之间的边的权重值为sij。注:这里的相似度图是无向的,即相似度函数须满足sij=sji

此时,聚类问题可以转化为相似度图来表示:划分的原则是:组间的边的权重最小化(意味着组间的数据相似度要尽可能低),组内的边的权重最大化(意味着组内的数据相似度尽可能高)。下图即为一个图模型聚类的示例:
谱聚类示例图
在上图中,一共六个定点,定点之间的连线上的数值表示两个顶点的相似度。现在要将这六个点划分为2个类,怎么分割?根据谱聚类的思想,应该去掉用虚线表示的那条边,进而分为两类。

邻接权重矩阵:如果vivj之间的相似度sij大于一定的阈值(这个阈值需要先验给定),那么可以认为这两个点是连接的,满足条件的sij记为wij。如果wij=0即表示这两个点未发生连接。同样的,由于相似度图G是无向的,那么有wij=wji。这样,由wij构成邻接权重矩阵W。

度矩阵:图G中某一个点viV的度可以定义为:

di=j=1nwij

度矩阵D=diag{d1,...,dn}是一个对角矩阵。

子图:图G的子图相当于全集的子集,即图G中的部分点构成的一个新的图。

相似度图G的建立方法

有多种将给定数据集x1,x2,...,xn以及对称性相似度sij(或距离dij)代入到相似度图的方法。构建相似度图G时,主要是要明确数据点相邻点之间的关系。

  1. ϵ近邻图:在这种图中,我们将距离小于ϵ的点连接起来。两点间的权值可以取为距离的倒数。这种建立方法的难点在于ϵ的确定。

  2. k近邻图:在这种图中,以点vi为例,如果vjvi的k近邻之一,那么将vivj连起来。当然,这会造成相似度图G是一种有向图,因为vjvi的k近邻之一,但是vi不一定是vj的k近邻之一。很像我们生活中:你是我的最好朋友,但是我不一定是你的最好朋友。有两种方法可以将此时的图化为无向图:(1)忽略边的方向性,即只要满足vjvi的k近邻之一或者vivj的k近邻之一,那么我们就将vivj连起来。(2)只有满足vjvi的k近邻之一而且vivj的k近邻之一,我们才将vivj连起来。依照(1)方法所得的图被称为k近邻图,依照(2)方法所得的图被称为互k近邻图

  3. 全连接图:在这种图中,我们将所有的点都相互连接起来,同时所有的边的权重设置为相似度sij。这种图建立的关键在于相似度函数的确立,相似度函数能够较好地反映实际中的相邻关系,那么效果较好。一个相似度函数的例子为高斯相似度函数:s(xi,xj)=exp(||xixj||2/(2σ2)),其中参数σ的选取是个难点。该方法中的参数σ的作用与ϵ近邻图中的ϵ的作用是相似的。

让我们看看实际上这几种建立方法的效果如何呢?下图即为三种方法的对比。假设原图中的上半部分为"月牙部分",下半部分为"高斯部分"
相似度图的建立方法

拉普拉斯矩阵及其性质

非正则化拉普拉斯矩阵及其性质

非正则化拉普拉斯矩阵定义如下:

L=DW

其中矩阵D是度矩阵,W为权重矩阵。拉普拉斯矩阵L满足如下性质:

  1. 对于任意向量fRn,满足:
    fLf=12i,j=1nwij(fifj)2
    .
  2. 矩阵L是对称半正定矩阵。
  3. 矩阵L的最小特征值为0,与之相对应的特征向量是常数向量1.
  4. 矩阵Ln非负实特征值0=λ1λ2...λn

证明性质1:

fLf=fDffWf=i=1ndif2ii,j=1nfifjwij=12(i=1ndif2i2i,j=1nfifjwij+j=1ndjf2j)=12i,j=1nwij(fifj)2

证明性质3:当向量f为常数向量1时,我们有fi=fj,代入到性质1中有fLf=0,由半正定矩阵的性质我们可以得到:Lf=0。由此可以得到矩阵L的特征值0对应的特征向量为常数向量1。又因为半正定矩阵的特征值非负,可以知道0是矩阵L的最小特征值。

性质2、4可以很容易得到。

定理:令相似度图G是权值非负的无向图,拉普拉斯矩阵L的特征值为0的重根个数k等于图G中连通分量数(子图数)。记G的连通分量为A1,A2,...,Ak,则特征值0的特征向量即为指示向量1A1,...,1Ak

定理的证明
首先,让我们先来证明k=1的情况,即特征值为0的个数只有一个。由定理的结论可以知道,此时的图是全连接的。假设此时特征值0所对应的特征向量表示为f,那么有:

0=fLf=12i,j=1nwij(fifj)2

由于此时的图是全连接的,那么wij>0,那么必然有fi=fj。即此时的特征向量为常数向量1。由于图是全连接的,此时的指示向量也是常数向量1。得证。

接下来让我们考虑有k个连通分量的情况。不失一般性的前提下,我们假设顶点都是按照连通分量的归属来排序的。这种情况下的权值矩阵W必然是对角块的形式(只有连通分量内的权值wij才不为0,其余全为0),由定义可以知道拉普拉斯矩阵L也是对角块形式

L=(L1L2Lk)

在连通分量Ai内部,拉普拉斯矩阵Li是全连接的,特征值为0的个数只有一个(无重根,仅仅在连通分量Ai内部而言),可知此时的特征向量(等于指示向量)为常数向量1
拉普拉斯矩阵L由众多小的拉普拉斯矩阵Li组成,L的特征向量实际上就是方块Li的特征向量(常数向量1)+其他方块的位置补零得到的(由于指示向量等于特征向量,考虑指示向量的含义即可理解)。

正则化拉普拉斯矩阵及其性质

有两个矩阵都被称为正则化拉普拉斯矩阵,两个矩阵的定义是相似的,具体定义如下:

Lsym:=D1/2LD1/2=ID1/2WD1/2Lrw:=D1L=ID1W.    

矩阵Lsym被称为对称拉普拉斯矩阵,Lrw被称为随机游走(random walk)拉普拉斯矩阵.

注:对角矩阵的(-1/2)次幂依然是对角矩阵,其对角线元素为原矩阵对角线元素的(-1/2)次幂。

正则化拉普拉斯矩阵满足如下性质:

  1. 对于任意向量fRn,满足:
    fLsymf=12i,j=1nwij(fidifjdj)2
    .
  2. (λ,u)Lrw的特征值和特征向量,当且仅当(λ,D1/2u)Lsym的特征值和特征向量;
  3. (0,1)Lrw的特征值和特征向量,当且仅当(0,D1/21)Lsym的特征值和特征向量;
  4. 矩阵LsymLrw是半正定的,有n非负实特征值0=λ1λ2...λn

定理:令相似度图G是权值非负的无向图,拉普拉斯矩阵LsymLrw的特征值为0的重根个数k等于图G中连通分量数(子图数)。记G的连通分量为A1,A2,...,Ak,则特征值0的特征向量又下列指示向量确定。

Lrw            {1A1,...,1Ak}Lsym      {D1/21A1,...,D1/21Ak}

谱聚类算法

在开始介绍算法流程之前,让我们来定义:给定数据集x1,x2,...,xn,相似度矩阵S=(sij)i,j=1,...,n是对称矩阵(因为相似度图G是无向的)。

非正则化谱聚类算法流程
输入:相似度矩阵SRn×n,需要聚类的数目k.

  • 构建相似度图G(具体方法参考前一部分"相似度图G的建立方法"),令W为权重矩阵。
  • 计算非正则化拉普拉斯矩阵L
  • 计算矩阵L的按照从小到大顺序排列的前k个特征向量u1,...,uk
  • 将这k个特征向量(列向量)构造成矩阵URn×k
  • 对于i=1,...,n,将矩阵U的第i行表示成向量yiRk
  • 在k维空间里,使用k均值聚类算法将n个数据点yi聚成k个簇C1,...,Ck

输出:聚类结果A1,...,Ak,其中Ai=j|yjCi

正则化谱聚类算法有两种,取决于采用哪一种正则化拉普拉斯矩阵。实际上,正则化谱聚类算法的流程和非正则化谱聚类算法的流程很相似。

正则化谱聚类算法流程(随机游走拉普拉斯矩阵)
输入:相似度矩阵SRn×n,需要聚类的数目k.

  • 构建相似度图G(具体方法参考前一部分"相似度图G的建立方法"),令W为权重矩阵。
  • 计算非正则化拉普拉斯矩阵L
  • 计算特征值问题Lu=λDu的按照从小到大顺序排列的前k个特征向量u1,...,uk
  • 将这k个特征向量(列向量)构造成矩阵URn×k
  • 对于i=1,...,n,将矩阵U的第i行表示成向量yiRk
  • 在k维空间里,使用k均值聚类算法将n个数据点yi聚成k个簇C1,...,Ck

输出:聚类结果A1,...,Ak,其中Ai=j|yjCi


正则化谱聚类算法流程(对称拉普拉斯矩阵)
输入:相似度矩阵SRn×n,需要聚类的数目k.

  • 构建相似度图G(具体方法参考前一部分"相似度图G的建立方法"),令W为权重矩阵。
  • 计算正则化拉普拉斯矩阵Lsym
  • 计算矩阵Lsym的按照从小到大顺序排列的前k个特征向量u1,...,uk
  • 将这k个特征向量(列向量)构造成矩阵URn×k
  • 将矩阵U的每一行都归一化到1,得到矩阵TRn×k,其中tij=uij/(ku2ik)1/2
  • 对于i=1,...,n,将矩阵U的第i行表示成向量yiRk
  • 在k维空间里,使用k均值聚类算法将n个数据点yi聚成k个簇C1,...,Ck

输出:聚类结果A1,...,Ak,其中Ai=j|yjCi

经验:首选游走拉普拉斯矩阵对应的谱聚类算法。

通过对比三种算法的具体过程,我们发现它们是非常相似的,只不过拉普拉斯矩阵不同从而导致了一丝不同而已。谱聚类算法的主要trick在于将原始数据xi转化为yi的过程(很多时候都是升维的过程)。这个过程之所以有效主要在于拉普拉斯矩阵的性质。经过变化后的数据,往往使用简单的k均值算法就可以实现很好的聚类效果。

那么为什么呢?算法的原理是什么呢?

从图的分割的角度来看待谱聚类

聚类的一开始,我们想的是根据数据点的相似性的大小来分成不同的组。进一步,将聚类问题转化为相似度图的划分来表示:划分的原则是:组间的边的权重最小化(意味着组间的数据相似度要尽可能低),组内的边的权重最大化(意味着组内的数据相似度尽可能高)。在这个维度来看,让我们来分析谱聚类问题如何近似为图的切割问题。

给定一个带权重矩阵W的相似度图,最简单最直接对一个图划分的方法就是最小化切割问题,定义最小化切割问题:选择一组划分:A1,...,Ak,最小化下面的式子:

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

其中A¯iAi的补;W(A,B):=iA,jBwij表示子图的连接权(之前已有定义)。

在实际操作中,发现上述的目标函数存在问题:在很多情况下,mincut的解,将图分成了1个点和其余n1个点。这1个点很有可能是个异常点,这样的切割对于实际聚类来讲是没有什么意义的。为了避免这个问题,目标函数应该显式要求所得到的划分A1,...,Ak应该足够大。最常见的修正后的目标函数有两个:RatioCut 以及 Ncut,定义如下:

RatioCut(A1,...,Ak):=12i=1kW(Ai,A¯i)|Ai|=i=1kcut(Ai,A¯i)|Ai|Ncut(A1,...,Ak):=12i=1kW(Ai,A¯i)vol(Ai)=i=1kcut(Ai,A¯i)vol(Ai)

其中的|Ai|表示Ai的顶点个数,vol(Ai)表示Ai的所有边的权值和,在之前章节都有定义。
那么我们就来分析一下为什么RatioCut和Ncut就能够解决问题呢?上述目标函数以Ai的点数或者权值和作为被除数,使得函数ki=11|Ai|在所有|Ai|相等的时候达到最小值,也就是所有顶点被平均分配到每个子图时最小;函数ki=11vol(Ai)在所有vol(Ai)相等的时候达到最小值。这样,RatioCut和Ncut在一定程度上能够使得最终得到的"簇"趋向于平衡。

上面只是讲了目标函数的修正,那么具体如何求解这个最值问题呢?我们重点分析RatioCut的解法,实际上RatioCut最终推导得到的最优解即为非正则化谱聚类算法的计算结果。而有兴趣的朋友可以去研究一下Ncut最终推导得到的最优解,实际上即为正则化谱聚类算法的计算结果。实际上RatioCut与Ncut的推导过程是相似的。

k=2时的RatioCut

k=2,这个事实目标函数就面成了求解如下问题:

minAVRatioCut(A,A¯)

给定一个子图AV,其中V表示全图,我们定义向量f=(f1,...,fn)Rn,其中
fi=|A¯|/|A|,if viA|A|/|A¯|,if viA¯

向量f表达式定下来以后,由下面的等式,我们可以将求解RatioCut的问题转化为求解拉普拉斯矩阵的问题:

fLf=====12i,j=1nwij(fifj)212iA,jA¯wij(|A¯||A|+|A||A¯|)2+12iA¯,jAwij(|A¯||A||A||A¯|)2cut(A,A¯)(|A¯||A|+|A||A¯|+2)cut(A,A¯)(|A¯|+|A||A|+|A|+|A¯||A¯|)|V|RatioCut(A,A¯).(1)

而经过研究发现,向量f还满足一定的约束条件:
i=1nfi=iA|A¯||A|iA¯|A||A¯|=|A||A¯||A||A¯||A||A¯|=0.

上式表明向量f和常数向量1是正交的。另外
||f||2=i=1nf2i=|A||A¯||A|+|A¯||A||A¯|=|A¯|+|A|=n.

将所有加在一起,我们可以将之前的RatioCut问题转化为:
minAVfLfs.t.fif1,||f||=n

该目标函数的自变量部分,是不同的子图划分A的选择,从而得到不同的f向量。每进行一次子图划分,就会得到一个f向量,进而可以得到不同fLf的值。优化的目标,是使得该目标函数取值最小。但是由于f只能够取2个值(离散化的定义域),而n个数据点的子图划分选择可以有指数级的选择,如果没有一个有效措施的话,这个问题的求解是一个NP问题。

为了解决这个困难,我们将目标条件做一个放松relaxation,将f的严格定义用f的性质来代替,向量f各个分量的取值从离散化的若干个值拓展到整个实数集,那么目标函数变为

minfRnfLfs.t. f1,|||f|=n

如此放松之后,问题就变成了一个非常标准的线性代数问题,找到这样一个f,它和常数向量1是相交的,同时它的模等于n,最终使得函数fLf最小即可。

幸运的是,根据Rayleigh-Ritz定理,该目标函数的解即为矩阵L的次小特征向量。

分为k个子图时的RatioCut

与划分为2个子图的做法相似,我们可以得到与k=2是的RatiCut相似的推导过程与结论:
需要将一个图V划分为k个子图A1,...,Ak,我们定义k个指示向量hj=(h1,j,...,hn,j)如下:

hi,j=1/||Aj|,  if viAj0,       otherwise(i=1,...,n;  j=1,...,k)

将这k个特征向量(列向量)构造成矩阵HRn×k。发现矩阵H中的每一列向量都是相互正交的,即有HH=I

和之前的计算过程相似,我们可以得到:

hiLhi=cut(Ai,A¯i)|Ai|.

更进一步,有:
hiLhi=(HLH)ii

于是可得:
RatioCut(A1,...,Ak)=i=1nhiLhi=i=1n(HLH)ii=Tr(HLH).

经过放松relaxation之后,原问题变成:
minHRn×kTr(HLH)s.t. HH=I

根据Rayleigh-Ritz定理,该目标函数的解矩阵H即为矩阵L的从小到大排序的前k个特征向量。实际上,细心的朋友会发现,此时的矩阵H即为非正则化谱聚类算法流程中的矩阵U。实际上,从RatioCut推导出问题最优解的过程正是在解释“为什么谱聚类的算法是可行的过程”。

后记

除了从图的切割的角度来去看待谱聚类算法以外,还可以用随机游走、扰动论等理论来解释。

前路漫漫!


参考文献:
Clustering by fast search and find of densitypeak. Alex Rodriguez, Alessandro Laio
A tutorial on spectral clustering,Ulrike von Luxburg, 2007

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注