基于图模型的高效聚类算法研究

发布时间：2017-05-13 19:21

  本文关键词：基于图模型的高效聚类算法研究，由笔耕文化传播整理发布。

【摘要】：近年来,随着社会网络、通信网络、生物网络等在各领域应用的快速发展,其产生的图模型数据更是呈现出快速增长的态势。图作为一种数据结构具有本身其特有的表示方法和信息,一个图模型可能包含几百到几百万的顶点,而这些顶点及其连接的边构成的关联信息在不同领域中都具有不同的意义,随着数据规模的不断增长,如何有效的对这些信息进行综合分析并从中获取有用的信息进行应用,是非常必要的,也是本文研究的主要的方向。聚类分析作为机器学习的一个重要工具目前已经被广泛应用于文本挖掘、生物信息学、模式识别等领域的科学研究,随着图模型数据的广泛应用,图聚类也成为了一类较为重要的聚类分析方法,图聚类是图数据分析的有效技术之一。在构造节点的相似矩阵时经常采用距离作为评价标准,而节点间存在多条等长路径及k短路径,这些路径间的关系都会对节点间相似性产生影响,因此综合考虑节点间的距离关系有助于更好的衡量节点间的相似性。针对这一问题,本文提出一个基于前k短路径的图聚类算法(DRGC),该算法参照谱聚类算法的思想,使用前k短路径模型构造相似矩阵,利用多层自动编码器代替谱聚类算法中的特征分解实现对数据的重构,并且可以大大减少特征分解所用时间,最后利用非参数贝叶斯模型进行聚类,因狄利克雷过程具有很好的聚类性质并且可以实现对数据的自动划分,因此该算法可以在不预先指定聚类数目的情况下得到数据集的正确合理划分。为了克服单一聚类算法对数据集敏感的问题,本文提出了一个基于多数投票的聚类集成算法,该算法利用前k短路径的图聚类算法、k均值算法、谱聚类算法作为基聚类算法,以模块度最高的一组聚类结果的标签作为基准标签,,分析与其他聚类结果的标签之间的关系,并通过计算对其进行统一,最后通过投票计算出数据集最终的聚类划分结果。最后,本文对所提出的两个算法进行了仿真实验,实验证明,本文所提出的算法具有良好的聚类性质,可以得到较为准确的聚类划分结果。
【关键词】：图聚类 k最短路径 聚类集成
【学位授予单位】：北京交通大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5;TP311.13
【目录】：

• 致谢5-6
• 摘要6-7
• ABSTRACT7-11
• 1 引言11-14
• 1.1 研究背景及意义11-12
• 1.2 本文研究的主要内容12-13
• 1.3 论文的组织安排13-14
• 2 图聚类研究理论基础14-25
• 2.1 图聚类研究概述14-20
• 2.1.1 图模型相关概念14-15
• 2.1.2 图聚类主要方法概述15-20
• 2.2 聚类集成20-24
• 2.2.1 聚类集成基本概念20-21
• 2.2.2 聚类成员的构造21-22
• 2.2.3 合并策略22-24
• 2.3 本章小结24-25
• 3 基于前k短路径的图聚类算法25-45
• 3.1 问题提出25
• 3.2 前K短路径的图聚类算法25-33
• 3.2.1 相似矩阵构造25-27
• 3.2.2 数据重构表达27-29
• 3.2.3 聚类阶段29-31
• 3.2.4 算法流程31-33
• 3.3 算法仿真及结果分析33-44
• 3.3.1 实验数据集33-34
• 3.3.2 实验评价标准34-35
• 3.3.3 实验结果分析35-44
• 3.4 本章小结44-45
• 4 基于多数投票的图聚类集成算法45-57
• 4.1 问题提出45
• 4.2 算法设计与分析45-51
• 4.2.1 标签统一策略45-47
• 4.2.2 合并策略47-48
• 4.2.3 算法流程48-51
• 4.3 算法仿真及结果分析51-55
• 4.4 本章小结55-57
• 5 结论与展望57-59
• 5.1 本文总结57
• 5.2 未来展望57-59
• 参考文献59-63
• 作者简历及攻读硕士学位期间取得的研究成果63-65
• 学位论文数据集65

【相似文献】

中国期刊全文数据库 前10条

1 田彦山;;基于山峰聚类的聚类上限确定方法[J];江西师范大学学报(自然科学版);2007年02期

2 赵超;舒红;朱欣焰;戴上平;;气象数据概化中的最佳聚类数研究[J];华中师范大学学报(自然科学版);2008年03期

3 高翠芳;吴小俊;;复杂生物数据集的聚类数自动确定方法[J];生物信息学;2010年04期

4 谢娟英;马箐;谢维信;;一种确定最佳聚类数的新算法[J];陕西师范大学学报(自然科学版);2012年01期

5 王凌峰;;基于构成要素的聚类算法[J];统计与决策;2007年19期

6 程慈;柴瑞敏;;聚类数的自动确定[J];科技信息(科学教研);2008年14期

7 方世良;一个聚类数动态可调的水声信号聚类算法[J];声学学报;1996年S1期

8 李闯;端木京顺;蔡忠义;高建国;;基于判断矩阵的专家模糊核聚类组合赋权方法[J];控制与决策;2012年09期

9 田娟,王崇骏,李静,陈兆乾;一个基于谱图分割的简单聚类算法[J];复旦学报(自然科学版);2004年05期

10 张李军;;改进的FCM聚类算法的实现和有效性研究[J];硅谷;2009年10期

中国重要会议论文全文数据库 前9条

1 高翠芳;吴小俊;;基于二阶差分的聚类数自动确定方法[A];江苏省系统工程学会第十一届学术年会论文集[C];2009年

2 刘洋;江志纲;丁增喜;王大玲;鲍玉斌;于戈;;一种基于图的聚类算法GB-Cluster[A];第十九届全国数据库学术会议论文集（技术报告篇）[C];2002年

3 李浪波;傅彦;刘红;;基于范例推理的网格和密度聚类算法[A];第二十二届中国数据库学术会议论文集（技术报告篇）[C];2005年

4 娄冬梅;陈明;朱有娜;;一种基于密度的无参数聚类算法[A];第二十三届中国数据库学术会议论文集（研究报告篇）[C];2006年

5 魏昕路;洪志令;姜青山;;一种基于样本缩减策略的新窗口式聚类算法[A];第二十四届中国数据库学术会议论文集（研究报告篇）[C];2007年

6 程尊平;周鼎;王晨;周皓峰;汪卫;施伯乐;;SDPHC——基于密度的分割和分层的自校聚类算法[A];第二十一届中国数据库学术会议论文集（研究报告篇）[C];2004年

7 张晓峰;王丽珍;陆叶;;一种基于属性加权的不确定K-means聚类算法[A];第26届中国数据库学术会议论文集（B辑）[C];2009年

8 蔡军;袁华鹏;陈金海;施伯乐;;一种基于相似性分析的聚类新算法:PDS算法[A];第十八届全国数据库学术会议论文集（研究报告篇）[C];2001年

9 胡仲义;郭超;王永炎;刘胜航;王宏安;;基于时间衰减和特征变量的数据流聚类算法[A];第29届中国数据库学术会议论文集（B辑）（NDBC2012）[C];2012年

中国博士学位论文全文数据库 前10条

1 胡雅婷;可能性聚类方法研究及应用[D];吉林大学;2012年

2 王纵虎;聚类分析优化关键技术研究[D];西安电子科技大学;2012年

3 周世兵;聚类分析中的最佳聚类数确定方法研究及应用[D];江南大学;2011年

4 杨燕;基于计算智能的聚类组合算法研究[D];西南交通大学;2006年

5 冯永;基于计算智能的聚类技术及其应用研究[D];重庆大学;2006年

6 刘晨;高伸缩性聚类分析方法研究[D];哈尔滨工程大学;2013年

7 王强;局部叠加基因表达模式聚类分析方法研究[D];哈尔滨工业大学;2012年

8 姜磊;混合演化聚类算法研究及其应用[D];武汉大学;2012年

9 尹学松;半监督聚类分析策略设计及其拓展性研究[D];南京航空航天大学;2009年

10 白亮;聚类学习的理论分析与高效算法研究[D];山西大学;2012年

中国硕士学位论文全文数据库 前10条

1 魏建东;K-means初始化算法研究[D];南京理工大学;2015年

2 张依;基于MapReduce的k-means聚类算法并行化研究[D];中央民族大学;2015年

3 刘婵;蚁群与K均值聚类算法融合研究及其在用户分群中的应用[D];西南科技大学;2015年

4 朱琪;基于减法聚类的混合算法研究[D];湖南科技大学;2015年

5 韩伟森;聚类集成研究与应用[D];贵州大学;2015年

6 谭浩;K-Means算法改进及其在森林健康评价中的应用[D];中南林业科技大学;2015年

7 严巍;以KPCA为核心的FCM算法改进[D];成都理工大学;2015年

8 汪娟;基于权重设计的聚类集成算法研究[D];重庆大学;2015年

9 牛品菽;基于图模型的高效聚类算法研究[D];北京交通大学;2016年

10 乔坤;基于系统能量理论的聚类算法及其应用研究[D];西安建筑科技大学;2007年

  本文关键词：基于图模型的高效聚类算法研究，，由笔耕文化传播整理发布。

本文编号：363430