Spectral Clustering

  谱聚类()是最广泛使用的聚类算法之一。通常分析数据前,我们想获取对数据的第一直观印象,初步识别数据中的某种相似性。本文将介绍谱聚类算法,比起传统的K-Means算法,谱聚类对数据分布的适应性更强,聚类效果也很优秀,同时聚类的计算量也小很多,更加难能可贵的是实现起来也不复杂。下面我们就对谱聚类的算法原理做一个总结。

图论基础

  谱聚类基于图论,也就是我们聚类过程中,实际上会将所有样本点都看成图中的顶点,谱聚类的本质是将聚类问题转化为一个图上关于顶点划分的最优问题。

  图G由顶点集和边集构成,记作,这里考察加权无向图,每两个顶点之间连边的权重都是非负的,并使用图G的邻接矩阵来表示。

  顶点的度定义为:, 该式子实际上只对和相连的顶点之间的边进行求和,和不相连的顶点,实际上就是邻接矩阵行和。这里定义度矩阵为以为对角元素的对角矩阵。

  对于给定的某个顶点集, 定义的补为 ,记作。并定义指示向量, ,该指示向量作用于所有顶点,若, 代表, 否则。为了方便,对于A集合的顶点,简记为

  对于两个不相交的顶点集, 定义,

  考察两种衡量顶点集A大小的方法:考察顶点集A中的顶点个数,将所有与顶点集A中的顶点相连的边的权重累加起来。

  定义顶点集构成的子图为连通的,当且仅当中任意两个顶点都能通过一条路径连通,且路径上的所有中间顶点都在上。

  定义顶点集是连通分量(), 当且仅当A构成的子图是连通的,且中的顶点不存在相连的边。也就是连通的只要求中任意两个顶点存在只经过A中顶点的路径,可能存在与某个顶点相连的边,连通分量进一步约束的顶点不存在相连的边。

  将划分为若干连通分量,,且

相似图

  实际上给定样本集,若把样本看成图上的顶点,此时还构不成图,因为顶点和顶点之间不存在边相连。因此,我们需要设计边,且边上的权重需要使用某种度量方式进行表示,也即需要为邻接矩阵上的值进行刻画。

  一种方式是定义边权重为边相连的两个顶点之间的相似性,任意两个顶点相连当且仅当这两个顶点的相似性为正数或大于某个阈值,此时边权重就用来代表。

  因此,聚类问题可以转化成图切割问题,使得聚类族之间的边权重较低,换句话说,不同聚类族之间的顶点相似性低,这也就意味着这两个聚类族相似性较低。同时,使得聚类族内部的顶点相似性较高。

  剩下的问题是如何度量样本之间的相似性?基本思想是,距离较远的两个点之间的相似性较低,距离近的点之间相似性高()。

  有三种方法,邻近法、近邻法、全连接法。

-邻近法

  邻近法,设置一个距离阈值, 使用欧式距离度量样本间的相似性, 再根据大小关系来确定边权重。

  从中可以看出,两点间的权重要么是,要么是, 整体是一样的,丧失了很多数据间相似性信息,因此该方法适用于无权图。

近邻法

  利用近邻算法遍历所有的样本点,取每个样本的最近的个点作为近邻,只有和样本最近的个点, 此时可以使用高斯相似性函数来计算,否则.

  但这样会造成邻接矩阵不是对称的(我们后面会知道,对称矩阵会带来很多计算上的遍历。)因为我的邻近点中有你,你的邻近点中不一定有我。

  处理成对称矩阵有2种方法。

1) : 中只要有一个点是另一个点的邻近点,则二者的权重都赋值成.

 具体处理过程为,首先按正常近邻得到邻接矩阵,此时可能不等于(一者为0,另一者为高斯相似函数值。若相等则不变)。令:

2), 必须两个点都是彼此的邻近点,否则都赋值成0。

  具体处理过程,首先按正常近邻得到邻接矩阵,令:

  上述的代表, 如果两个矩阵相同位置元素值如果相等,则该位置数值保持不变。如果不相等(也就是说有一个不是另一个的邻近点,此时),则令该位置数值为0。

全连接法

  所有点之间的权重都大于0,距离度量可以选择不同的核函数来定义边权重,常用的有多项式核函数,高斯核函数和核函数。最常用的是高斯核函数,此处使用高斯相似函数。参数控制了领域的宽度,这和邻近法中的作用是相似的。如何理解呢? 考察样本点和其他点的相似性,也就是固定高斯核中心位置在, 则越小,高斯函数越尖,领域宽度越小。意味着同一个样本点,代入为中心的相似性函数,在不同的取值下,得到的和的相似性值不一样,且小的相似性低。这意味着两个样本点在大时可能划分到同一个聚类族里,而当小时,可能就不会划分到同一个聚类族里了,间接反映了聚类族(领域)的大小。

  正常情况下,此时得到的邻接矩阵应该是对称的。不过为了保险,仍然对邻接矩阵进行如下处理:

图拉普拉斯矩阵

  拉普拉斯矩阵是用于谱聚类的主要工具。拉普拉斯矩阵具有很多重要的性质。

  我们假设图是无向带权图,且权重为非负数。当使用矩阵的特征向量时,我们没必要假定图是规范化的,这意味着特征向量, 是一样的。

未规范化的图拉普拉斯矩阵

  有如下性质:

  注意L并不依赖于邻接矩阵对角元素(令W对角元素为,则)。

​ 性质1的证明:

  连通性质:

  则的特征向量为的特征向量且在其他分块的位置全填充为. 形如,.

每一个对应的子图是全连通分量,因此的0特征值重数为1,相应的特征向量为. 因此矩阵零特征值的重数为, 每个特征向量是对应连通分量的指示向量。

规范化图拉普拉斯矩阵

  稍后会看到,规范化的拉普拉斯矩阵对应的是图切割问题中的优化目标。而上述未规范化的拉普拉斯矩阵对应的是图切割问题中的优化目标。稍后会看到,的前k个特征向量构成的矩阵是优化目标中的最优解。

  若令, 可以将优化目标转成,, 改变了约束形式,后者是标准瑞利熵理论形式,其最优解对应的前k个特征向量构成的矩阵。若令, 则的前k个特征向量构成的矩阵。

  性质如下:

无向图切割视角看谱聚类

  对于无向图G的切割,我们的目标是将图切成相互没有连接的个子图, 也即将划分为若干连通分量,,且 。对于任意两个不相交的顶点集,定义切割代价为:

  对于个子图,定义切割代价为:

  上述实际上是思想,每次考察某个顶点集与该顶点集的补,个子图则考虑次。系数是因为无向图,同一条边权重,在考察时会被算两次。

  我们的目标是最小化切割代价,即顶点集内部点的权重大,而顶点集之间顶点连边权重小。

  但是该优化目标存在问题,必然会导致平凡解。例如对于二划分问题,只会选择权重最小的边,然后将某个点和其余的点分开,导致划分出来的顶点集不平衡。

  解决上述问题的思路是改变优化目标,加入对顶点集规模的考虑。由此引出.

  下面重点讨论, 以及它们与拉普拉斯矩阵、谱聚类的关系。

  在目标函数中加入对顶点集中顶点个数的考虑。

  之所以说这样切割得到的子图规模是平衡的,是因为该优化目标会在顶点集大小差不多大时取到较小的值。特别的,的最小值会在全部相等时取到。因此这样的切割得到的顶点集趋向于平衡。

  那么如何优化该目标函数呢?这里引入个指示向量, 指示向量代表第个顶点集的指示向量,它是n维的,n是顶点的个数,也就是该指示向量衡量了所有顶点是否属于该顶点集。

  对于某个顶点集的指示向量, 我们有(有个分量数值为), 且

计算有,其中是未规范的图拉普拉斯矩阵:

  我们惊喜的发现,这样设计的【指示向量】将【谱聚类算法】的【拉普拉斯矩阵求解】与【图切割】问题巧妙的联系在一起了

  这意味着求解二划分图切割问题,即最小化可以转成最小化拉普拉斯矩阵的正定型

  进一步推广到个子图的切割问题,构造顶点集的指示向量矩阵, 每列对应相应顶点集的指示向量,则:

  也就是说图切割问题优化目标就是最小化, 另外根据指示向量的性质,我们有约束.加上该约束后,对求解得到的结果可以近似认为是图切割问题中的指示向量集合。

  然而,H矩阵中每一维指示向量都是n维的,取值要么是0,要么是, 则每个指示向量有种,k个指示向量就有。因此该优化问题是np难的,归根结底是因为指示向量的分量取值为离散值决定的。

  我们考虑松弛约束问题,使H分量的取值可以为任意实数。则转成迹最小化问题:

  这是瑞利熵理论的一种形式。使用拉格朗日方程求解非常容易。考察单独某个指示向量求解问题,

 

  对求导,

  因此,最优解就是拉普拉斯矩阵的特征向量,该特征向量近似为指示向量,且目标函数最小值也就是该特征向量对应的特征值。对于划分问题,矩阵最优解为L的前k个特征向量构成的矩阵,目标函数值为对应特征值的和(H将L对角化为特征值构成的对角矩阵,相当于对对角元素求和了)。

  由于约束的松弛,导致得到的优化后的指示向量h对应的H现在不能完全指示各样本的归属,因此一般在得到nxk维度的矩阵H后还需要对每一行进行一次传统的聚类,比如使用K-Means聚类.

  换了一种方式考察子图的规模,由于子图样本的个数多并不一定权重就大(即相似性高),我们切图时基于权重也更符合我们的目标,因此一般来说Ncut切图优于RatioCut切图。

  对应的,Ncut切图对指示向量做了改进。注意到RatioCut切图的指示向量使用的是标示样本归属,而Ncut切图使用了子图权重来标示指示向量,定义如下:

  此时的指示向量有性质,, 证明:

  同样有: