文档视界 最新最全的文档下载
当前位置:文档视界 > 谱聚类报告

谱聚类报告

机器学习报告

一.绪论

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

由于谱聚类的数值实现很简单,利用简单的线性代数学方法就能有效解决,而且相比传统的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矩阵,给出了两种标准化谱聚类的方法。

相关文档
  • 谱聚类算法

  • 用户谱聚类

  • 聚类分析实验报告

  • 谱聚类与社区划分

  • 图聚类算法