谱聚类算法及其研究进展.docx
《谱聚类算法及其研究进展.docx》由会员分享,可在线阅读,更多相关《谱聚类算法及其研究进展.docx(10页珍藏版)》请在咨信网上搜索。
1、 谱聚类算法及其研究进展 邢洁清符传谊摘要:谱聚类具有良好的理论基础,被广泛应用于科学研究与工程应用的各个领域,成为聚类分析领域重要的新兴分支,受到越来越多的研究者的重视。然而,国内相关文献较少,该文从谱聚类算法的产生、研究进展、基础理论及代表算法等方面对谱聚类算法作简要综述,有望使读者对该领域形成初步认识。关键词:谱聚类;聚类;图划分:TP311 :A :1009-3044(2016)19-0159-03Spectral Clustering and its Research ProgressXING Jie-qing, FU Chuan-yi(Department of Modern Ed
2、ucation Technology, Qiongtai Normal College, Haikou 571100, China)Abstract:Spectral clustering has good theoretic foundation, and has been applied in various science research and engineering fields. It becomes an important new popular tool for clustering analysis. With its development, spectral clus
3、tering attracts much more attention from researchers. However, there are few literatures on it. This paper gives a brief review about the creation, development, theoretic analysis and classical methods of spectral clustering.Key words: spectral clustering; clustering; graph partition聚类作为无监督学习方法,广泛地应
4、用于统计科学、计算机科学、生物学、社会学以及心理学等,成为应用最多的数据分析技术之一。其中,基于谱图划分理论的聚类方法谱聚类,是目前研究较多、有深厚理论基础、应用广泛的聚类方法。与传统的方法(如k-means,EM等)相比,它不对样本空间的整体结构做任何假设,能够识别样本点在空间上的非凸分布。因此,谱聚类方法适用于具有任何分布形状的样本空间,从而求解到全局最优解。此外,谱聚类使得聚类算法的研究得到很大的拓展,适用于许多现实应用问题,已成功地应用于文本分析、语音分析、图像分割、机器视觉、商业分析、市场营销、计算生物学等等1-3。目前,谱聚类方法的应用还扩展到医学诊断6、DNA和蛋白质等生物信息挖
5、掘5、文本主题分析4等领域。对谱聚类算法的研究具有科学意义和现实意义。同时,谱聚类算法在实现上仅涉及标准的线性代数方法,易于实现。谱聚类算法是以图论当中的谱图理论为基础,重点在于设计合适的距离度量,计算待聚类的数据点之间的距离或相似性,构造邻接图,最后将聚类任务转化为邻接有向图的最优划分问题。本文旨在从基础理论、代表算法、比较分析等方面向读者介绍这种新型的聚类算法。1 谱聚类算法研究进展谱聚类的诞生可以追溯到1973年,Donath和Hoffman 首次基于邻接矩阵构造了图的划分7。在同一年,Fieldler发现图的二划分与Laplacian图的第二小特征向量有密切关系,并且建议使用该特征向量
6、进行图的划分8。从此以后,许多研究者加入到谱聚类方法的研究队伍中,例如,Pothen, Simon, and Liou 9、Bolla 10、Hagen and Kahng 11、Hendrickson and Leland 12、Van Driessche and Roose13和Guattery and Miller14等。谱聚类逐渐成为流行的聚类方法1-6。在算法扩展和理论分析方面涌现了大量的研究成果。Dhillon等人将谱聚类应用于联合聚类问题14,并分析了谱聚类与加权k-means的关系19。Bach等人利用谱聚类辅助学习相似性函数9。Kempe等人分析了再分布式环境下的谱聚类21。
7、Perez等人提出了稀疏核谱聚类并应用于大尺度数据集17。Jia等人将集成学习方法应用于谱聚类22。Zhang等人设计了基于边界的多路谱聚类方法14。最近,王春腾等分析了维数约简与谱聚类的关系,提出了基于维数约简的谱聚类方法:基于非负约束的谱聚类算法(NMFSC)15和基于独立成分分析的谱聚类(ICASC)16。特别地,聚类方法在图像分割任务的应用中,传统的做法提取各像素点的特征向量,利用k-means等聚类方法对像素点进行聚类。这类方法固有的缺陷是对样本点的分布假设,例如k-means方法假定样本点的分布服从高斯分布。然而,在现实应用中该假设未必成立。谱聚类方法的优势在于不需要事先假定样本服
8、从某种特定的分布,计算像素点样本之间的相似性,构造相似性矩阵,通过对相似性矩阵的谱图划分达到划分样本空间的目的,从而避免了对样本空间分布假设的依赖,使得谱聚类方法在理论上能够适应任意分布形状的样本空间。2 理论基础2.1 相似图为说明谱聚类的基本理论,本节首先引入有关的基本记号和相似图概念。已知一个给定的数据集,根据已设计的距离公式可计算出样本点两两之间相似度,构造出相似性矩阵。以每个数据点为顶点,顶点与连通,给其连接边赋予非负权值,即数据点与之间的相似性。此时,基于相似性矩阵构造出无向图,其中,是顶点集合,是边集合。聚类的直接目标是将相似的点尽量放在同一簇中,而不相似的点尽量归入到不同簇中。
9、至此,聚类问题可以转化为该无向图上的划分问题,找到图的某个分割,使得同一簇中点点间的边权值之和最大,而不同簇之间的点点间边权值之和最小。 无向图称为给定数据集的相似图,其中,顶点集,边集。在边上赋予权值,构成无向加权图,顶点与之间赋予非负权值,则有加权邻接矩阵,。特别地,当,表示两顶点间不连通。2.2 谱图划分理论谱聚类算法的思想来源于谱图划分理论19。无向加权图构造完成后,就可以寻找图的最优划分,需要建立图的最优划分准则。图论中常用的划分准则有M-cut, Mbmax-cut, N-cut, Average-cut,Ratio-cut等。限于篇幅,本文仅对常用的划分准则规范割集准则(Norm
10、alized-cut或N-cut)作简要介绍。N-cut是由Shi和Malik提出的,其目标函数的公式如下:其中。以Ncut函数作为最小化目标函数,称为规范割集准则。从该准则的目标函数可以看出,不仅可以度量同簇样本间的相似性,还可以度量不同簇间样本的相异性。Shi和Malik对上述目标函数进行了拓展,提出规范关联目标函数(Nassoc):其中,与分别是在子图,内各自所有顶点间连接权值的总和。该准则衡量了同一簇内的样本间的紧凑程度。进一步的推导,可以得出Ncut函数与Nassoc函数之间的线性关系:。所以,最小化Ncut函数与最大化Nassoc函数是等价的,两个目标函数可以任选其一。在实际应用中
11、,Ncut函数更常用。3 谱聚类算法选用不同的划分准则,可以构造出不同的谱聚类算法,大致可以将谱聚类算法分为两类:迭代谱聚类和多路谱聚类。就迭代谱聚类而言,Peron与Freeman合作提出PF算法,其主要思想是构造样本集的相似图,计算相似性矩阵的最大特征值及其对应的特征向量,以特征向量中零元素对应的数据点为中心生成一个簇类,其余点生成另外一个类,由此迭代,得到最终聚类结果25。其他具有代表性的迭代谱聚类算法有SM算法1、SLH算法6和KVV26算法等。就多路谱聚类而言,Ng和Jordan等人提出NJW算法,其基本思想是计算相似性矩阵的拉普拉斯矩阵,寻找该矩阵的前k个最大特征值及其对应的特征向
12、量,将原数据点投影到k个特征向量构造的新的特征空间中,最后在新的k维空间中实施k-means,得到最终聚类结果2。Meila对NJW算法进行的拓展,将NJW中的k维特征空间再实施了一个线性旋转,构造出新的投影空间,然后在该空间中实施聚类28。不管是上述哪一类方法,谱聚类算法的步骤大致可以归纳为如下三步:Step1:构造无向图,其中,顶点集,边集。根据样本点与之间的相似性,赋予边权值,得到加权邻接矩阵,。此时,将聚类问题转化为图的最优划分问题。最优划分准则的选取直接影响谱聚类算法的效果,也是谱聚类算法研究的集中关注点。谱聚类算法改进大多集中在相似性度量函数和最优划分目标函数的设计上。Step2:
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 谱聚类 算法 及其 研究进展
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【精***】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【精***】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。