K-means聚类算法的改进研究

发布时间：2017-04-08 00:09

  本文关键词：K-means聚类算法的改进研究，由笔耕文化传播整理发布。

【摘要】：随着计算机网络的普及,人们的工作和生活更多的与数据信息产生联系,制造和使用的数据量越来越巨大,我们进入了一个大数据时代。人们每天接触大量的数据资源,而所需的信息只是其中极小的一部分,或者是隐藏于其中的潜在信息。如何快速高效的从海量的数据资源中获取所需的那部分信息,如何找出数据之间的联系和规律是我们亟需研究的课题,数据挖掘技术便是在这种需求驱动下出现的多学科交叉的技术。数据挖掘技术的核心功能是从大量的信息资源中发现隐藏的、有效的、有价值的知识,从而更好的理解和应用隐藏在数据中的有效信息,充分发挥数据的价值,为科学决策或政策的制定提供帮助。聚类分析是数据挖掘中常用的技术,在图像分割、电子商务、市场分析、生物学、地理学以及文档分类等众多领域有着广泛的应用。聚类分析的基本原理是：在没有先验知识的情况下,将一个数据集划分成多个簇,使得同一个簇中的数据对象的特征较相似,而不同簇间的数据对象的特征相似性小。聚类分析中有众多的聚类算法,其中基于划分的算法应用最为广泛,因为算法的思想原理简单、算法实现相对容易且对大规模数据集聚类收敛性好等优点而成为应用最为广泛的聚类算法之一,其最具代表性的是k-means聚类算法。然而,传统k-means算法也有多个明显的缺点：如聚类需要凭借经验先指定一个聚类数k值,并且随机选择k个初始聚类中心；聚类结果对初始聚类中心和聚类数k值的依赖性强,对孤立点和噪声点敏感。针对以上缺点,本文提出了一个改进的k-means聚类初始中心点选择算法和一种确定聚类数k值的算法,并用实验验证了改进算法的有效性,两个算法的改进之处在于：(1)针对k-means算法聚类结果受初始聚类中心和异常数据的制约,易出现聚类结果不稳定和收敛于聚类局部最优的问题,提出了一种选取数据集中k个处于密集区域的数据对象作为初始聚类中心的改进算法。该算法提出了一个用于表示数据集中每个数据对象密度的参数m-dist,然后根据该密度参数的值,选取k个相对分散且密度较高的数据对象作为初始聚类中心。该算法可以有效的避免选取到数据集中的孤立点和噪声点作为初始聚类中心,能有效减少聚类的迭代次数,对聚类结果的准确性提高显著。(2)经典k-means算法需要凭经验给定一个聚类数k值,k值的确定具有一定的主观性,容易产生偏差,本文提出了一种确定聚类数的方法,首先根据样本的密度从数据集中选择处于高密度区域的若干数据对象产生一个初始聚类中心点候选集合U,然后根据提出的聚类有效性指标AIBWP的值搜索最佳聚类数,当AIBWP的值达到最大时,聚类有效性指标最优,指标值所对应的聚类数就是最佳聚类数。
【关键词】：聚类分析 k-means算法 初始聚类中心 最佳聚类数 样本密度
【学位授予单位】：安徽大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP311.13
【目录】：

• 摘要3-5
• Abstract5-9
• 第1章 绪论9-14
• 1.1 选题背景及研究意义9-11
• 1.2 国内外研究现状及发展趋势11-12
• 1.3 本文主要内容及组织结构12-14
• 1.3.1 本文主要研究内容12-13
• 1.3.2 论文的章节安排13-14
• 第2章 聚类分析技术14-23
• 2.1 聚类分析技术概述14-15
• 2.2 聚类分析中的度量函数15-18
• 2.3 聚类算法的基本要求18-19
• 2.4 常用聚类算法分类19-22
• 2.4.1 基于划分的聚类算法19-20
• 2.4.2 基于层次的聚类算法20
• 2.4.3 基于密度的聚类算法20-21
• 2.4.4 基于网格的聚类算法21
• 2.4.5 基于模型的聚类算法21
• 2.4.6 其他常见聚类算法21-22
• 2.5 本章小结22-23
• 第3章 k-means聚类算法23-28
• 3.1 经典k-means聚类算法介绍23
• 3.2 k-means算法的研究现状23-24
• 3.3 k-means算法实现步骤描述24-26
• 3.4 k-means算法的优缺点分析26-27
• 3.5 本章小结27-28
• 第4章 初始中心点优化k-means算法28-34
• 4.1 问题的提出28-30
• 4.2 密度参数优化的k-means算法30-31
• 4.3 实验结果与分析31-33
• 4.4 本章小结33-34
• 第5章 改进k-means聚类数确定方法34-45
• 5.1 现有的k-means聚类数确定方法34-36
• 5.2 聚类中心优化的k-means最佳聚类数确定方法36-41
• 5.2.1 获得初始中心点候选集36-38
• 5.2.2 新的聚类有效性指标38-40
• 5.2.3 最佳聚类数确定算法描述40-41
• 5.3 实验结果与分析41-44
• 5.4 本章小结44-45
• 第6章 总结与展望45-47
• 6.1 论文总结45
• 6.2 下一步的工作45-47
• 参考文献47-51
• 致谢51-52
• 攻读硕士学位期间学术论文发表情况52-53
• 附录53-54
• 附录A 图索引53
• 附录B 表索引53-54
• Appendix54
• Appendix A Figure Index54
• Appendix B Table Index54

【相似文献】

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

1 周世兵;徐振源;唐旭清;;新的K-均值算法最佳聚类数确定方法[J];计算机工程与应用;2010年16期

2 周世兵;徐振源;唐旭清;;基于近邻传播算法的最佳聚类数确定方法比较研究[J];计算机科学;2011年02期

3 周世兵;徐振源;唐旭清;;一种基于近邻传播算法的最佳聚类数确定方法[J];控制与决策;2011年08期

4 李旭;林伟;温金环;史彩云;;基于图谱理论的图像聚类数的确定及应用[J];工程数学学报;2012年05期

5 秦振涛;杨武年;;一种新的最佳聚类数确定方法[J];电子技术应用;2013年01期

6 宋铭利;高新科;;基于距离的最大聚类数探索算法的探讨[J];矿山机械;2006年09期

7 普运伟;朱明;金炜东;胡来招;;核聚类算法最佳聚类数的自适应确定方法[J];计算机工程;2007年04期

8 杨欣斌,孙京诰,黄道;一种进化聚类学习新方法[J];计算机工程与应用;2003年15期

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

10 褚娜;马利庄;王彦;;聚类趋势问题的研究综述[J];计算机应用研究;2009年03期

中国重要会议论文全文数据库 前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];山东大学;2016年

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

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

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

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

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

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

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

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

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

中国硕士学位论文全文数据库 前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];安徽理工大学;2016年

  本文关键词：K-means聚类算法的改进研究，，由笔耕文化传播整理发布。

本文编号：291629