理解谱聚类

SIGAI资源

《机器学习与应用》勘误和修改更新：

http://sigai.cn/paper_78.html

（登录即可下载，感谢各位读者的反馈）

资深专家解读论文：

http://sigai.cn/knowledge.html

聚类是典型的无监督学习问题，其目标是将样本集划分成多个类，保证同一类的样本之间尽量相似，不同类的样本之间尽量不同，这些类称为簇（cluster）。与有监督的分类算法不同，聚类算法没有训练过程，直接完成对一组样本的划分。

聚类是数据分析中最常用的技术之一，应用领域包括统计，计算机科学，生物，社会科学，心理学等。在要处理经验数据的几乎所有科学领域，我们都需要通过鉴别数据中相似的样本所构成的分组来建立对数据的直观映像。这篇文章介绍谱聚类算法，是对《机器学习与应用》，清华大学出版社，雷明著一书中第18章“聚类算法”中谱聚类算法的扩充，将在第二版中出版。

谱聚类算法是聚类算法家族中相对年轻的成员。与传统的聚类算法如k-means算法、层次聚类、DBSCAN算法等相比，谱聚类具有很多优势。谱聚类算法所得到的结果经常优于传统方法，谱聚类实现起来非常简单，可以用标准的线性代数方法高效求解。

图论中的基本概念

图是离散数学和数据结构中的一个概念。一个图由顶点和边构成，任意两个节点之间可能都有边进行连接。边可以带有值信息，称为权重，例如两点之间的距离。下图是一个简单的图

图的边可以是有向的，也可以是无向的，前者称为有向图，后者称为无向图。可以将地图表示成一个图，每个地点是顶点，如果两个地点之间有路连接，则有一条边。如果这条路是单行线，则边是有向的，否则是无向的。

顶点的度定义为该顶点所关联的边的数量，对于有向图它还分为出度和入度，出度是指从一个顶点射出的边的数量，入度是连入一个节点的边的数量。无向图可以用三元组形式化的表示：

（V,E, w）

其中V是顶点的集合，E是边的集合，w是边的权重函数，它为每条边赋予一个正的权重值。假设i和j为图的顶点，wij为边(i, j)的权重，由它构成的矩阵W称为邻接矩阵。显然，无向图的邻接矩阵是一个对称矩阵。

定义顶点i的加权度为与该节点相关的所有边的权重之和，即邻接矩阵每一行元素之和

定义加权度矩阵D为一个对角矩阵，其主对角线元素为每个顶点带权重的度

其中n为图的顶点数。后面将要介绍的拉普拉斯矩阵则通过邻接矩阵，加权度矩阵计算而得到。

将聚类问题看作图切割问题

谱聚类是一种基于图的机器学习算法。基于图的算法把样本数据看作图的顶点，根据数据点之间的距离构造边，形成带权重的图，然后通过对图进行处理来完成算法所需的功能。对于聚类问题，通过图的切割实现聚类，即将图切分成多个子图，这些子图就是对应的簇。这类算法的典型代表是谱聚类算法。

谱聚类算法构造样本集的邻接图（也称为相似度图），得到图的拉普拉斯矩阵。接下来对矩阵进行特征值分解，通过对特征向量进行处理构造出簇。

算法首先根据样本集构造出带权重的图G，聚类算法的目标是将其切割成多个子图，每个子图即为聚类后的一个簇。假设图的顶点集合为V，边的集合为E。聚类算法将顶点集合切分成k个子集，它们的并集是整个顶点集

任意两个子集之间的交集为空

对于任意两个子图，其顶点集合为A和B，它们之间的切图权重定义为连接两个子图节点的所有边（即跨两个子图的边）的权重之和：

其中W是图中两个顶点之间边的权重。

切图权重可以看作两个子图之间的关联程度，如果两个子图之间没有边连接，则该值为0。从另一个角度看，这是对图进行切割时去掉的边的权重之和。

下图为图切割示意图

上图中有7个顶点，被切割成蓝色和黄色两个子图，虚线边为被切割掉的边，因此切图权重为

2+3 = 5

对图顶点子集V1, ..., Vk，定义这种分割的代价为

其中

为Vi的补集。该值与聚类的目标一致，即每个子图内部的连接很强，而子图之间的连接很弱，换一种语言来表述就是同一个子图内的样本相似，不同子图之间的样本不相似。但直接通过最小化这个值实现聚类还有问题，它没有考虑子图规模对代价函数的影响，使得这个指标最小的切分方案不一定就是最优切割。因此需要对代价函数进行归一化，具体的方法在后面将会介绍。

为样本集构造邻接图

对于如何从一组数据点x1,...,xn计算出两点间的相似度Sij或距离dij从而构造出一个图，有几种不同的典型方案。如果是构造相似度图，则其目标是对样本点之间的局部邻接关系进行建模。

ε邻居图。计算任意两点之间的距离，如果距离小于阈值ε，则将这两个数据点设置为联通的。由于所有相连的数据点之间的距离大致上有相同的尺度，即各个边的权重没有区分度，最大为ε，因此为边加权重不会为从数据构造出的图包含更多的信息。因此，ε邻居图通常被认为是无权重的图。

k近邻图。如果顶点vj在vi的k个最近的邻居里，则将vj核vi设置为联通的。但是，这种定义导致的结果是有向图，因为邻居关系不是对称的，即如果vj在vi的k个最近的邻居里，不能推出vi在vj的k个最近的邻居里。将图变为无向的方式有两种。第一种方法是忽略边的方向，即如果vj在vi的k个最近的邻居里，或者vi在vj的k个最近的邻居里，则认为这两点之间是联通的。这种方法生成的图称为k近邻图。第二种是如果vj在vi的k个最近的邻居里，并且vi在vj的k个最近的邻居里，则认为这两点之间是联通的。这种方法生成的图称为互k近邻图。无论是哪种方式，当建立两个点的连接之后，边的权重设置为两个点之间的相似度。

全连接图。简单的为所有的节点对之间建立起边，边的权重为Sij。因为图要表达数据的邻接关系，因此要保证相似度函数本身能够对局部邻居关系进行建模，才能构造出有用的图。典型的相似度函数是高斯相似度函数

其中σ控制邻域的宽度，是人工设置的参数。这个参数所起的作用类似于ε邻居图中的ε参数。

图的拉普拉斯矩阵

谱聚类算法基于图的拉普拉斯矩阵，这是图的一种矩阵表示。没有归一化的图拉普拉斯矩阵定义为

L = D-W

其中W为邻接矩阵，D为加权度矩阵，它们的定义在在前面已经给出。下面介绍拉普拉斯矩阵的一些重要性质。

1.对任意的向量f∈

有

2.拉普拉斯矩阵是对称半正定矩阵。

3.这个矩阵的最小特征值为0，其对应的特征向量为常向量1，即所有分量为1。

4.矩阵L有n个非负实数特征值，并且满足 0=λ1

λ2

...

λn

下面给出证明。根据di的定义，有

因此结论1成立。根据结论1，显然这个矩阵是半正定的，而根据定义，矩阵是对称的的，因此结论2成立。由于

由于D是W经过各列元素累加得到的，因此行列式为0，故0是其特征值。如果f=1，则有

因此1是对应的特征向量。根据结论1-3可以得到结论4。

需要注意的是，根据定义，这种未归一化的拉普拉斯矩阵不依赖于邻接矩阵W的主对角线元素。除了主对角线元素之外，其它位置的元素都相等的各种不同的矩阵W都有相同的拉普拉斯矩阵。特别是，图中的自边不影响图的拉普拉斯矩阵。

未归一化的图拉普拉斯矩阵以及它的特征值，特征向量可以描述图的多种重要的性质。假设G是一个有非负权重的无向图，其拉普拉斯矩阵L的特征值0的重数等于图的联通分量的个数A1,...Ak。特征值0的特征空间由这些联通分量所对应的向量1A1,...,1Ak所张成。

证明如下。先考虑k=1的情况，即图是联通的。假设f是特征值0的一个特征向量，根据特征值的定义有

这是因为Lf=0f=0。因为图是联通的，因此所有的wij>0，要让上面的值为0，必定有fi-fj=0。这意味着向量f的任意元素都相等，因此结论成立。

接下来考虑有k个联通分量的情况。不失一般性，我们假设顶点按照其所属的联通分量排序，这种情况下，邻接矩阵是分块矩阵，同样的，拉普拉斯矩阵也是这样的分块矩阵

显然每个子矩阵Li自身也是一个拉普拉斯矩阵，对应于这个联通分量。对于这些子矩阵，上面的结论也是成立的，因此L的谱由Li的谱相并构成，L对应的特征向量是Li的特征向量，其余位置填充0。由于每个Li都是一个联通分量的拉普拉斯矩阵，因此其特征向量的重数为1，对应于特征值0。而L中与之对应的特征向量在第i个联通分量处的值为常数 ，其它地方为0。因此矩阵L的0特征值对应的特征向量的重数与联通分量的个数相等，并且特征向量是这些联通分量的指示向量。

有两种形式的归一化拉普拉斯矩阵，它们之间密切相关，分别定义为

在这里D 1/2是对该矩阵主对角线上的所有元素计算根号值所得到的矩阵。第一种矩阵为对称矩阵，第二种矩阵与随机漫步有密切的联系。接下来介绍这两种矩阵的重要性质。

1.对任意的向量f∈

有

2. λ是矩阵Lrw的特征值，u是特征向量，当且仅当λ是Lsym的特征值，并且其特征向量为

3.λ是矩阵Lrw的特征值，u是特征向量，当且仅当λ和u是下面广义特征值问题的解

4.0是矩阵Lrw的特征值，其对应的特征向量为常向量1，即所有分量为1。0是矩阵Lsym的特征值，其对应的特征向量为D1/21。

5.矩阵Lsym和Lrw是半正定矩阵，有n个非负实数特征值，并且满足

和未归一化的拉普拉斯矩阵类似，有下面的重要结论：

假设G是一个有非负权重的无向图，其归一化拉普拉斯矩阵Lrw和Lsymm的特征值0的重数k等于图的联通分量的个数A1,...,Ak。对于矩阵Lrw，特征值0的特征空间由这些联通分量所对应的向量1A1,...,1Ak所张成。对于矩阵Lsymm，特征值0的特征空间由这些联通分量所对应的向量D1/21A1,...,D1/21Ak所张成。

RatioCut与NCut

前面说过，需要对图切割的代价函数进行归一化。第一种方法是用图的顶点数进行归一化，由此得到优化的目标为：

其中|Vi|为子集的元素数，称为RatioCut。另外一种归一化方案为

其中vol是图中所有顶点的加权度之和

称为NCut。这两种情况都可以转化成求解归一化后的拉普拉斯矩阵的特征值问题。假设L为图的拉普拉斯矩阵，W为邻接矩阵，D为加权度矩阵。定义归一化后的拉普拉斯矩阵为

对于RatioCut，求解的是如下特征值问题

其中n为样本数，I为单位矩阵，tr为矩阵的迹，下面给出证明。首先考虑最简单的情况，将图切分成两个子图A和

，此时要求解的最优化问题为

为方便表述，给定一个子集A，构造指示向量f=(f1,...,fn) T，表示每个样本所属的簇即子图，其元素的取值为

根据该向量的定义有

即给定任意子图A，上面这个二次型与RatioCut的目标函数一致。另外根据f的定义有

即向量f与全1向量1正交。另外

因此向量f需要满足等式约束。求解的切图问题等价于如下带约束的最优化问题

其中

表示向量正交。向量所有分量的取值必须为定义的两种情况，此问题是一个离散优化问题，为NP难问题，不易求解。对问题进行放松，变成连续优化问题

这个问题的解是L的第二小的特征值所对应的特征向量。因为该矩阵最小的特征值是0，对应的特征向量是1。因此，第二小的特征值对应的特征向量近似是RatioCut的最优解。但是，切图所对应的结果应该是离散的，而这里得到的解是连续的，需要转换成离散的。一种解决方案是

类似于sgn函数。对于超过两个簇的情况，这种简单的阈值化不合适，此时可以将fi当做点的坐标，用聚类算法将其聚成两类。然后按照如下的规则得到聚类结果

推广到多个子图的情况，通过构造指示向量可以得到类似的优化目标。对于NCut最后求解的是如下广义特征值问题

在完成特征值分解之后，保留k个最小的特征值和它们对应的特征向量，构成一个n×k的矩阵，矩阵的每一行为降维后的样本数据。最后用其他聚类算法如均值算法对降维之后的数据进行聚类。

算法流程

根据前面得到推导可以得到具体的谱聚类算法，这里有两个版：

算法1：

算法2：

参考文献

[1] Andrew Y Ng, Michael I Jordan, Yair Weiss. On Spectral Clustering: Analysis and an algorithm. neural information processing systems, 2002.

[2] Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and Computing, 2007.

[3] Shi, J. and Malik, J. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22 (8), 888-905. 2000.