机器学习报告 一.绪论
聚类是探索性数据分析中广泛采用的一种技术,其应用范围包括统计学、 计算机科学、生物学、社会科学和心理学等等。在处理经验数据的时候,我们 可能倾向于根据数据的“近似表现”将数据确定到一定的类别。而本次我们小 组的实验主要是基于聚类算法中的谱聚类方法,通过对两种谱聚类方法的实验 和一些应用,验证算法的效果,加深对该方法的理解。 由于谱聚类的数值实现很简单,利用简单的线性代数学方法就能有效解决, 而且相比传统的 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 矩阵,给出了两种标准化谱聚类的方 法。