谱聚类报告
机器学习报告 一．绪论
聚类是探索性数据分析中广泛采用的一种技术，其应用范围包括统计学、 计算机科学、生物学、社会科学和心理学等等。在处理经验数据的时候，我们 可能倾向于根据数据的“近似表现”将数据确定到一定的类别。而本次我们小 组的实验主要是基于聚类算法中的谱聚类方法，通过对两种谱聚类方法的实验 和一些应用，验证算法的效果，加深对该方法的理解。 由于谱聚类的数值实现很简单，利用简单的线性代数学方法就能有效解决， 而且相比传统的 K 均值方法等聚类方法有很多优点，所以谱聚类方法称为了很 流行的现代聚类算法之一。 以 K 均值方法为例，正如我们所知，该方法主要存在这样一些问题：首先， 其只适用于凸球形的样本空间，如果样本空间非凸，则会陷入局部最优，导致 聚类效果不佳；再有，由于该方法计算使用的是欧氏空间中的原始数据向量， 所以在样本维数很大的时候， K 均值算法的计算量会很大，导致了计算的困难； 聚类数 K 难以确定等等。而谱聚类则能很好地解决这些问题。 在本次实验中，我们小组根据相关文献，认真学习和讨论了谱聚类的先关 概念。首先，我们研究了一般的谱聚类和标准化谱聚类的概念和它们的异同， 并通过实验对比，验证了谱聚类的效果，其中标准化谱聚类有显著的优势。接 下来，将谱聚类应用于图像分割问题，显示出谱聚类良好的应用价值。最后， 我们查阅相关文献，尝试从另外一个角度去理解谱聚类方法。通过这次学习， 我们对谱聚类的理解得到了大大加深，对于很多疑难的地方也通过查看有关文 献和小组讨论得到了解决，并通过小组合作锻炼了自身的团队意识和配合工作 的能力。
二．谱聚类基本思想
谱聚类是一种基于图论的聚类方法，把样本看作图的顶点，样本间的相似 度对应带权值的边（其中相似度可以通过高斯核函数等方法构造），根据类间 相似度最小，类内相似度最大的原则，便可以将样本聚类问题变成了图的分割 问题：分割使得连接不同类之间的边的权值尽可能小，而类内点之间的边的权 值尽可能高。虽然这样对应的最小化图分割问题是一个 NP-HARD 问题，但是我 们可以将其转化为最小化图的 Laplace 矩阵的特征值问题。 具体地，给定样本特征之后，我们首先要计算样本两两之间的相似度值， 并通过这些值构造出近邻矩阵。以高斯核函数为例，计算公式如下：
wij ? e
?|| xi ? x j ||2 (2? 2 )
作为第 i 个样本和第 j 个样本之间相似度的度量。而近邻矩阵如下：
W ? (wij ) 。
然后可以定义第 i 个节点（样本）的阶： di
? ? wij ，以及阶矩阵：
j
D ? diag (d1 , d2 ,?, dn ) 。进一步，拉普拉斯矩阵为 L ? D ? W
根据 Lapalace 矩阵的若干性质，如：
。
1）
f T Lf ?
1 wij ( fi ? f j )2 ? 2 i, j ；
2）L 是对称半正定矩阵； 3）L 的最小特征值为 0，对应特征向量为常数向量 1； 4）L 有 n 个非负的实特征值； 经过一系列推导，可以将最小化图分割问题近似为如下：
min f T Lf n
f ?R
s.t
f T 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 矩阵的定义：
Lrw ? D?1L ? I ? D?1W
； 。
Lsym ? D?1/2 LD?1/2 ? I ? D?1/2WD?1/2
标准化 Laplace 矩阵满足这样一些性质：
1）
f T Lsym f ?
1 wij ( fi / di ? f j / d j )2 ? 2 i, j ；
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. 计算 Lrw 的前 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. 计算 Lsym 的前 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 矩阵，给出了两种标准化谱聚类的方 法。
