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 矩阵,给出了两种标准化谱聚类的方 法。


推荐相关:

数字资源检索报告

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


统计分析学习总结

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


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

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


数字资源检索报告

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


科技论文报告

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


开题报告-参考

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


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

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


图像处理相关

“教育部重点实验室第七届学术 周暨 2011 年度学术之秋学术报告心得体会 2011 ...此外,还有谱聚类。 张小华老师的低秩图像处理、王爽老师的 SAR 图像处 理、...


粒计算图像分割

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


应用层DDOS攻击检测技术研究

安全公司卡巴斯基发布的 21 下半年安全监 01控报告中指出,tp型的Do攻击占据了...3 结论本文 提出的基于谱聚类 的应 用层Do攻击检测DS 能够较好的检测出攻击 ...

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