3986.net
小网站 大容量 大智慧
相关标签
当前位置:首页 >> 学习总结 >>

谱聚类报告


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


推荐相关:

聚类分析学习文档_图文

非层次聚类 划分聚类、谱聚类 聚类方法特征: ? ? 析; 聚类分析简单、直观。 聚类分析主要应用于探索性的研究,其分析的结果可以提供多个可能的解,选择最终的解...


统计分析学习总结

非层次聚类 划分聚类、谱聚类 分析步骤: 定义问题与选择分类变量;聚类方法;确定群组数目;聚类结果评估;结果 的描述、解释 5 典型相关分析和对应分析 典型相关分析(...


数字资源检索报告

数字资源检索报告_计算机软件及应用_IT/计算机_专业资料。检索报告 13 级 数学...袁可红, 黄士国, 王德运, 郭海湘, 一种基于谱聚类分析的粒子群聚类算法,《...


数字资源检索报告

数字资源检索报告_高等教育_教育专区。检索报告 15 级 数学与计算科学 院系 ...袁可红, 黄士国, 王德运, 郭海湘, 一种基于谱聚类分析的粒子群聚类算法,《...


贾志远-21551063-第三次读书报告

贾志远-21551063-第三次读书报告_司法考试_资格考试/认证_教育专区。硕士研究生...Mafkov 聚类、谱聚类以及基于密度的聚类进行了描述,对算法 的过程进行了详细阐述...


科技论文报告

国际会议报告ppt制作 21页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出...[8] 马秀丽,焦李成.基于分水岭-谱聚类的 SAR 图像分割[J].红外与毫米波学 ...


开题报告-参考

开题报告-参考_计算机软件及应用_IT/计算机_专业资料。开题报告的模板 本科生毕业设计(论文)开题报告 题 目: 图像聚类及其 Python 实现 学专班学姓 院: 信息...


2013届毕设开题报告-罗崇珺

毕业设计(论文)开题报告 1.结合毕业设计(论文)课题情况,根据所查阅的文献资料,...谱聚类算法综述[J].计算机科学,2008,35(7):14-18. [2] 周志华,王珏主编....


粒计算图像分割

一种用于谱聚类图像分割的... 暂无评价 10页 10财富值喜欢此文档的还喜欢 ...报告还提供图像熵的措施和目标提取的图像熵的定义 的直方图(双关语,1981 年)和...


专业学位选题报告算法的应用及其在保险企业中的应用

专业学位选题报告算法的应用及其在保险企业中的应用_销售/营销_经管营销_专业资料...谱聚类方法研究及其在 Weka 中的实现[J].计算机工程与设计,2008,29(13) [8...

网站首页 | 网站地图
3986 3986.net
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@qq.com