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

谱聚类算法的Maltab仿真设计


谱聚类算法的 Matlab 仿真设计
薛方 (长安大学理学院,陕西 西安 710064)

摘要:本文从理论、程序设计和代码实现等方面,介绍如何将谱聚类算法利用 Matlab 的灵活编程功能进行 仿真设计。 关键字:谱聚类;程序设计;仿真设计

1 引言
谱聚类算法建立在谱图理论基础上,与传统的聚类算法相比,它具有能在任意形状的样本空间上聚类且收敛于 全局最优解的优点。该算法首先根据给定的样本数据,构造相似度函数,计算相似度矩阵,计算矩阵的特征值和特 征向量,然后选择合适的特征向量聚类不同的数据点。谱聚类算法最初用于计算机视觉、VLSI 设计等领域,最近才 开始用于机器学习中,并迅速成为国际上机器学习领域的研究热点。谱聚类算法建立在图论中的谱图理论基础上, 其本质是将聚类问题转化为图的最优划分问题,是一种点对聚类算法,对数据聚类具有很好的应用前景。 将图像的每一个像素看作一个对象,利用上述定义的相似度矩阵,可以将图像分割问题转化为图论中的最小割 问题,而谱聚类算法是最小割问题的有效算法,从而将谱聚类算法应用到图像分割中。

2 谱聚类算法
谱聚类算法建立在谱图理论基础上,与传统的聚类算法相比,它具有能在任意形状的样本空间上聚类且收敛于 全局最优解的优点。该算法首先根据给定的样本数据定义一个相似度函数,得到相似度矩阵,然后计算该矩阵的特 征值和特征向量,然后选择合适的特征向量聚类不同的数据点。步骤如下: Step1:根据给定的样本数据构造相似度矩阵 W ; Step2:计算 W 的特征值 ?1

? ?2 ?

? ?N 和相应的单位正交特征向量 x1 , x2 ,
, N} 计算分类数;

xN ;

Step3:按 k ? max{i | ?i ? 1, i ? 1, 2,

Step4:将 W 的前 k 个最大特征值对应的单位正交特征向量按列组成矩阵

X ? ( x1, x2 ,

T T , xk ) ? (?1 , ?2 ,

T T , ?n ) ;

Step5:计算矩阵 X 的行向量之间的夹角的余旋

? i? T j ?i
2

?j

,这样就形成了一个新的夹角矩阵 G ,用 K 均值
2

或其他经典算法进行聚类。 把谱聚类算法应用到二维数据聚类中则是把普通数据点聚类问题转化为图论的最优划分问题。在应用谱聚类之 前首先要构造待聚类的随机的二维数据点。 计算机程序流程设计如下: Step1:在 [a1 , a1 ? 0.1] 、 [a2 , a2

? 0.1] 和 [a3 , a3 ? 0.1] 内各随机生成两组数含 p 个数,组成六组

x1 ? [ x11 , x12 , x2 ? [ x21 , x22 , x3 ? [ x31 , x32 ,

, x1 p ], y1 ? [ y11 , y12 , , x2 p ], y2 ? [ y21 , y22 , , x3 p ], y3 ? [ y31 , y32 ,

, y1 p ]; , y2 p ]; , y3 p ];

x1 ? a1 ? 0.1* rand ( p,1); y1 ? a1 ? 0.1* rand ( p,1); x2 ? a2 ? 0.1* rand ( p,1); y2 ? a2 ? 0.1* rand ( p,1); x3 ? a3 ? 0.1* rand ( p,1); y3 ? a3 ? 0.1* rand ( p,1);

x1'
Step2:把这六组数放进一个两列的矩阵中,使得 D ? x ' 2

y2 ' ,此时, D 中每一行存的都是一个行坐标和一个列 y3'

y1'

x3'
坐标, D 就是我们凑出来待分割的随机二维数据。

由于二维数据在二维空间中是因为行和列之间的距离不同导致数据点的分散程度不一,所以构建相似度函数时, 只需要考虑二维数据的距离因素。 L

? ( x1 ? x2 )2 ? ( y1 ? y2 )2

表示的是数据点 ( x1 , y1 ) 和 ( x2 , y2 ) 之间的欧

式距离。接下来根据相似度函数 L 求 D 中二维数据的相似度矩阵,再求相似度矩阵的特征值和对应的特征向量,对 矩阵的特征向量用 K 均值或者其他方法进行聚类。

3 仿真结果

图 1 随机点 1 和 2 的聚类结果

图 2 随机点 3 和 4 的聚类结果

4 结论
Matlab 有极强的编程仿真功能,已经应用于社会生活各个领域。利用 Matlab 进行谱聚类,是一种探索性和优化 性的综合实验。本文很好的对谱聚类算法进行了仿真设计,聚类结果符合逻辑。

参考文献
[1] 宋丽红.K-均值聚类的 Matlab 仿真设计[J].试验技术与管理.2010.10,10(27):101-103 [2] 田铮,李小斌,句彦伟. 谱聚类的扰动分析[J]. 中国科学 E 辑: 信息科学, 2007, 37(4): 527-543 [3] 李小斌, 田铮.基于谱聚类的图像多尺度随机树分割[J].中国科学 E 辑: 信息科学, 2007, 37(8): 1073-1085 [4] 邹小林,陈伟福,冯国灿,刘志勇,汤鑫.基于谱聚类的多阀值图像分割方法[J].计算机科学,2012.3,39(3) [5] 李小斌,田铮,刘密歌,徐海霞.基于加权割的图像分割[J].电子学报.2008,36(1):76-80 [6] 赵凤,焦李成,刘汉强,公茂果.半监督谱聚类特征向量选择算法[J].模糊识别与人工智能.2011,24(1):48-55 [7] 周品,李晓东.数字图像处理[M].北京:清华大学出版社,2012.8,370-384


推荐相关:

谱聚类算法最初用于计算机视觉、VLS I 设计等领域,最近才开 始用于机器学习中, 并迅速成为国际上机器学习领域的研究热点。 谱聚类算法建立在图 论中的谱图理论...


最近,学 者们也开始将谱聚类方法用于机器学习中。Shi 和 Malik[4]在 2000 年根据谱图理 论建立了 2-way 划分的 Normalized-Cut(Ncut)的目标函数,设计了用于...


谱聚类算法(Spectral Clustering) 谱聚类(Spectral Clustering, SC)是一种基于图论的聚类方法——将带权无向图划分为两个或两个以上的最优子图,使子图内部尽量...


聚类算法综述_电脑基础知识_IT/计算机_专业资料。...最后,笔者给出一种谱聚类的 matlab 实 现实例及...该方法设计简单,应用范围广, 本质来说可归结为较...


评价聚类信息 C2=cophenet(Z2,Y2); //0.94698 Step4 创建聚类,并作出系图 T=cluster(Z2,6); H=dendrogram(Z2); Matlab 提供了两种方法进行聚类分析。 ...


Spectral Clustering(谱聚类)是一种基于图论的聚类方法,它能够识别任意形状的样本空间且收敛于全局 最有解,其基本思想是利用样本数据的相似矩阵进行特征分解后得到的...


神经网络学习算法matlab仿真_计算机软件及应用_IT/计算机_专业资料。东南大学自动化...二.系统分析及设计原理(1)神经网络的学习算法学习过程实质上是针对一组给定的...


Matlab 编程实现运用 Matlab 中的一些基本矩阵计算方法,通过自己编程实现聚类...% 第 3 类集合中的元素 % 画聚类图 [H,T]=dendrogram(Z) 聚类谱系图如图...


k-中心点、分层聚类、高斯混合模型和隐 马尔可夫模型...提供的算法和应用的传感器阵列系统的设计,仿真和分析...算法可作为 MATLAB? 功能,系统对象?和 Simulink?的...


matlab聚类分析 MATLAB 提供了两种方法进行聚类分析: 一、利用 clusterdata 函数对数据样本进行一次聚类,这个方法简洁方便,其 特点是使用范围较窄, 不能由用户...

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