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


推荐相关:

1 谱聚类谱聚类算法建立在图论中的谱图理论基础上, 其本质是将聚类问题转化为图的最优划分问题,假定将每个 数据样本看作图中的顶点 V, 根据样本间的相似度将...


谱聚类算法_法律资料_人文社科_专业资料。.2谱聚类算法谱聚类算法和很多其他距离算法相比有很多优点,下文会详述此点,同样的,谱聚类也适合解决图切 割问题。 谱聚类...


谱聚类算法 算法简介_数学_自然科学_专业资料。谱聚类算法 算法简介 谱聚类算法建立在谱图理论基础上, 与传统的聚类算法相比, 它具有能在任意形状的样 本空间上聚...


合肥学院数理系 实验报告 实验名称: 面向专业: 实验班级: 聚类分析 数学与应用...title ’使用类平均法的谱系聚类图’; run; 5、 实验结果分析与讨论 根据上述...


分类结果可以画成一张直观的聚类谱系图。 应用系统聚 类法进行聚类分析的步骤...输入多元统计分析软件,经过一些操作输出结果,然后分析一下,再将实验 报告做好就...


实验报告13 谱系聚类_化学_自然科学_专业资料。实验十三实验目的和要求 谱系聚类 掌握谱系聚类分析的理论与方法、 模型的建立; 掌握利用谱系聚类分析的 SAS 过程...


谱聚类算法及其在图像分割... 11页 5财富值 聚类算法讲解 51页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击此处进行反馈。 ...


实验报告13 谱系聚类_数学_自然科学_专业资料。学号: 班级: 姓名: 实验十三实验目的和要求 谱系聚类 掌握谱系聚类分析的理论与方法、模型的建立;掌握利用谱系聚类...


TT]=dendrogram(Z) % 画聚类图,H是一个线的句柄的向量 聚类谱系图如下图所示: 这里没有对聚类的好坏进行评价,读者可以运行 c=cophenet(Z,Y)来看看聚类的 ...


聚类分析实验报告 班级:精算 1104 班 学号:2011161684 指导老师:苗菲 姓名:王...根据聚类表及分类谱系图综合分析可以知道,分成五类是最好的方案,所以 确定为五...

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