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


推荐相关:

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


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


单击“绘制(T)”按钮,在“系统聚类分析:图”对话框中选择“树状图”、“冰柱”,如图-7 所示, 表示输出的结果将包括聚类图(树状)以及冰柱图(垂直) 。 ...


图˙谱˙马尔可夫过程˙聚类结构_计算机软件及应用_IT/计算机_专业资料。今日推荐 160份文档 2014年度细分行业报告汇集 2014年移动互联网O2O分析报告 休闲农庄项目可行...


机器学习报告 非监督学习---一些聚类算法聚类是数据挖掘中用来发现数据分布和隐含...(三)谱聚类为了能在任意形状的样本空间上聚类,且收敛于全局最优解,现研究利用...


4)在合并过程中要记下合并样品的编号及两类合并时的水平(即距离)并绘制聚类谱...2014年度细分行业报告汇集 2014年移动互联网O2O分析报告 休闲农庄项目可行性研究...


多元统计分析实验报告3-聚类分析_数学_自然科学_专业资料。2015——2016 学年第...2、点击绘制,选中谱系图,点击继续返回主对话框; 1 3、再点击方法按钮,在聚类...


关键词:实验报告13 谱系聚类实验报告谱聚类波士顿住房问题 1/2 相关文档推荐...实验要求:编写程序,结果分析. 实验内容: 要求: 1.写出谱系聚类步骤,类间距离...


实验报告-20114570-朱筱琪_计算机软件及应用_IT/计算机_专业资料。安徽财经大学统计...使用软件名称:MATLAB 1.熟练掌握应用 MATLAB 软件计算谱系数据与 K 均值聚类的...


贾志远-21551063-第三次读书报告_司法考试_资格考试/认证_教育专区。硕士研究生...图聚类中会用到的一些聚 类算法,例如:Mafkov 聚类、谱聚类以及基于密度的聚类...

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