谱聚类报告

机器学习报告

一．绪论

聚类是探索性数据分析中广泛采用的一种技术，其应用范围包括统计学、计算机科学、生物学、社会科学和心理学等等。在处理经验数据的时候，我们可能倾向于根据数据的“近似表现”将数据确定到一定的类别。而本次我们小组的实验主要是基于聚类算法中的谱聚类方法，通过对两种谱聚类方法的实验和一些应用，验证算法的效果，加深对该方法的理解。

由于谱聚类的数值实现很简单，利用简单的线性代数学方法就能有效解决，而且相比传统的K 均值方法等聚类方法有很多优点，所以谱聚类方法称为了很流行的现代聚类算法之一。

以K 均值方法为例，正如我们所知，该方法主要存在这样一些问题：首先，其只适用于凸球形的样本空间，如果样本空间非凸，则会陷入局部最优，导致聚类效果不佳；再有，由于该方法计算使用的是欧氏空间中的原始数据向量，所以在样本维数很大的时候，K 均值算法的计算量会很大，导致了计算的困难；聚类数K 难以确定等等。而谱聚类则能很好地解决这些问题。

在本次实验中，我们小组根据相关文献，认真学习和讨论了谱聚类的先关概念。首先，我们研究了一般的谱聚类和标准化谱聚类的概念和它们的异同，并通过实验对比，验证了谱聚类的效果，其中标准化谱聚类有显著的优势。接下来，将谱聚类应用于图像分割问题，显示出谱聚类良好的应用价值。最后，我们查阅相关文献，尝试从另外一个角度去理解谱聚类方法。通过这次学习，我们对谱聚类的理解得到了大大加深，对于很多疑难的地方也通过查看有关文献和小组讨论得到了解决，并通过小组合作锻炼了自身的团队意识和配合工作的能力。

二．谱聚类基本思想

谱聚类是一种基于图论的聚类方法，把样本看作图的顶点，样本间的相似度对应带权值的边（其中相似度可以通过高斯核函数等方法构造），根据类间相似度最小，类内相似度最大的原则，便可以将样本聚类问题变成了图的分割问题：分割使得连接不同类之间的边的权值尽可能小，而类内点之间的边的权值尽可能高。虽然这样对应的最小化图分割问题是一个NP-HARD 问题，但是我们可以将其转化为最小化图的Laplace 矩阵的特征值问题。

具体地，给定样本特征之后，我们首先要计算样本两两之间的相似度值，并通过这些值构造出近邻矩阵。以高斯核函数为例，计算公式如下：

22||||(2)i j x x ij w e σ--=

作为第i 个样本和第j 个样本之间相似度的度量。而近邻矩阵如下：

()ij W w =。

然后可以定义第i 个节点（样本）的阶：i ij j

d w =∑，以及阶矩阵：

12(,,,)n D diag d d d = 。进一步，拉普拉斯矩阵为L D W

=-。

根据Lapalace 矩阵的若干性质，如： 1）2

,1()2T

ij i j i j f Lf w f f =-∑； 2）L 是对称半正定矩阵；

3）L 的最小特征值为0，对应特征向量为常数向量1；

4）L 有n 个非负的实特征值；

经过一系列推导，可以将最小化图分割问题近似为如下：

min .n T T f R f Lf s t f f n ∈=。

而上述问题又可以转化为特征分解问题。我们对L 做特征分解，取最小的前k 个特征值对应的特征向量，用这k 个特征向量组成新的n*k 维样本矩阵。然后把新的矩阵的每一行看作新的数据向量（k 维），对着新的n 个k 维向量进行K 均值聚类，聚类得到第i 行属于哪一族，则最初的第i 个样本就属于哪一族。

谱聚类的优点有：

可以对任意形状的样本空间聚类，不会陷入局部最优，克服了传统聚类只适用于凸形状样本空间的缺点；只需要用数据之间的相似度矩阵进行计算，比起K 均值那样使用n 维欧氏空间中的向量要能大大减少计算量，可以看作是对数据的降维；便于确定聚类数K 。

三．标准化谱聚类

1.非标准化谱聚类

非标准化谱聚类的步骤如下：

1. 按照一定的方法建立近邻图，以及对应的近邻矩阵W ；

2. 计算非标准化Laplace 矩阵L ；

3. 计算L 的前k 个特征向量u1，…，uk ；

4. 设n*k 维矩阵U 为以u1，…，uk 作为列向量的矩阵；

5. 对i=1，…，n ；设k 维向量yi 为U 矩阵的第i 行；

6. 通过K 均值方法对n 个yi 点进行聚类。

2.标准化谱聚类

根据两种标准化Laplace 矩阵，可以给出两种标准化谱聚类方法。 首先我们给出两种标准化Laplace 矩阵的定义：

11rw L D L I D W --==-；

1/21/21/21/2

sym L D LD I D WD ----==-。 标准化Laplace 矩阵满足这样一些性质：

1

）2

,1(//2T

sym ij i j i j f L f w f f =-∑； 2）两种标准化Laplace 都是对称半正定矩阵且有n 个非负特征值；

3）a 为Lrw 的特征向量u 对应的特征值当且仅当a 为Lsym 特征向量w 对应的特征值，其中w=(D^1/2)*u ；

4）0为Lrw 的特征值0，其对应特征向量为常数向量1；而0为Lsym 的特征值，其对应常数向量(D^1/2)*1。

于是就有了两种标准化谱聚类的步骤。第一种方法步骤如下：

1. 按照一定的方法建立近邻图，以及对应的近邻矩阵W ；

2. 计算非标准化Laplace 矩阵L ；

3. 计算rw L 的前k 个特征向量u1，…，uk ；

4. 设n*k 维矩阵U 为以u1，…，uk 作为列向量的矩阵；

5. 对i=1，…，n ；设k 维向量yi 为U 矩阵的第i 行；

6. 通过K 均值方法对n 个yi 点进行聚类。

而第二种方法的步骤如下：

1. 按照一定的方法建立近邻图，以及对应的近邻矩阵W ；

2. 计算非标准化Laplace 矩阵L ；

3. 计算sym L 的前k 个特征向量u1，…，uk ；

4. 设n*k 维矩阵U 为以u1，…，uk 作为列向量的矩阵；

5.将U矩阵的每个行向量规范化为范数为1的向量，再构成n*k维矩

阵T；

6.对i=1，…，n；设k维向量yi为T矩阵的第i行；

7.通过K均值方法对n个yi点进行聚类。

这样，就根据不同的标准化Laplace矩阵，给出了两种标准化谱聚类的方法。