基于云平台的聚类算法并行化研究

发布时间：2017-10-21 06:25

  本文关键词：基于云平台的聚类算法并行化研究

  更多相关文章： 聚类 云计算 Hadoop Kmeans DBSCAN

【摘要】：聚类算法是数据挖掘中的重要内容,能够从数据中提取出隐藏的有用信息和知识来为人们服务,在工业、商业以及科研领域都得到了广泛应用。随着当今社会数据量急剧增加,单机聚类算法的计算能力渐渐无法满足需求,广大互联网公司为了从激烈的商业竞争中脱颖而出以获得商业成功和大量的经济利益,纷纷为大规模数据的处理寻求有效策略,于是多台计算机共同参与运算的分布式聚类算法成为当前研究热点。云计算平台是一个优秀的新型商业计算模型,通过虚拟化技术把互联网中的节点资源相融合来提供优越的计算能力,并且能够根据计算任务中任务量的实时变化情况来动态扩展集群中的节点。系统将待处理的计算任务合理分配到计算机集群中的节点上,根据实际需求得到所需的存储空间和计算能力等资源,用户在无需理解云内部的知识和细节的情况下也可以使用云平台中的基础设施。Hadoop作为Apache基金会开发的开源云计算平台,以一种高效可靠可伸缩的方式处理数据,此外还具有高容错性和低成本等优点,是一个能够分布式处理海量数据的软件框架。Hadoop核心设计是底部HDFS(分布式文件系统)和上层MapReduce(编程模式),分别为海量数据提供存储和计算。本文主要研究如何运用云平台中大量计算机节点的并行计算能力来解决大规模数据聚类的难题。针对Kmeans算法中一些不足之处提出改进:采用Canopy算法作为Kmeans聚类的初始步骤,并基于“最小最大原则”优化初始聚类中心的选取;对Kmeans迭代过程加以优化使整体计算量得到降低,进一步提高算法效率。详细分析DBSCAN算法在参数选择,内存使用、I/O开销等方面存在的问题,提出了一个基于层次的优化算法。既解除了因参数选择不当而对算法效率造成的影响,还在一定程度上降低了查询次数从而减小I/O开销。最后,通过搭建Hadoop平台分别对基于MapReduce的Kmeans和DBSCAN并行优化算法进行一系列的测试实验来验证性能。实验表明:Kmeans优化算法在迭代速度及聚类结果准确率上有所提升;DBSCAN优化算法在正确率和实效性方面均得到改善;并且通过加速比实验证明本文的并行算法更适合处理大规模数据集。
【关键词】：聚类 云计算 Hadoop Kmeans DBSCAN
【学位授予单位】：南京邮电大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP311.13;TP393.09
【目录】：

• 摘要4-5
• abstract5-8
• 第一章 绪论8-11
• 1.1 课题背景8-9
• 1.1.1 大规模数据挖掘8
• 1.1.2 聚类算法8
• 1.1.3 云计算平台8-9
• 1.2 研究目的和意义9
• 1.3 论文研究内容9-10
• 1.4 论文组织结构10-11
• 第二章 数据聚类相关技术11-21
• 2.1 聚类分析概述11-15
• 2.1.1 聚类分析的定义11-12
• 2.1.2 聚类分析中的数据结构12-13
• 2.1.3 聚类分析中的数据类型13
• 2.1.4 聚类的相似性计算方法13-15
• 2.2 聚类基本步骤15
• 2.3 主要聚类算法15-18
• 2.3.1 层次方法16
• 2.3.2 划分方法16-17
• 2.3.3 基于密度的方法17
• 2.3.4 基于网格的方法17
• 2.3.5 基于模型的方法17-18
• 2.4 并行聚类相关技术18-20
• 2.4.1 并行计算简介18
• 2.4.2 并行策略18-19
• 2.4.3 并行算法的性能评价19-20
• 2.5 本章小结20-21
• 第三章 Hadoop云计算平台21-31
• 3.1 Hadoop简介21-22
• 3.2 HDFS分布式文件系统22-27
• 3.2.1 HDFS的特点22-23
• 3.2.2 HDFS的体系结构23-25
• 3.2.3 保障HDFS可靠性措施25-26
• 3.2.4 HDFS缺点及改进26-27
• 3.3 Mapreduce编程模型27-30
• 3.3.1 MapReduce编程思想27-29
• 3.3.2 MapReduce处理流程29-30
• 3.4 本章小结30-31
• 第四章 基于MapReduce的Canopy-Kmeans算法并行优化31-43
• 4.1 Kmeans算法简介31-34
• 4.1.1 Kmeans算法思想31-32
• 4.1.2 Kmeans算法流程32-33
• 4.1.3 Kmeans算法复杂度与性能分析33-34
• 4.2 Canopy- Kmeans算法简介34-36
• 4.2.1 Canopy算法思想34-35
• 4.2.2 Canopy算法流程35-36
• 4.3 改进算法设计36-37
• 4.3.1 初始聚类中心优化36
• 4.3.2 Kmeans迭代过程优化36-37
• 4.3.3 基于Hadoop平台的算法并行化37
• 4.4 基于Hadoop平台的Canopy-Kmeans算法并行实现37-41
• 4.4.1 Canopy中心点生成37-39
• 4.4.2 输入数据标注39
• 4.4.3 Kmeans迭代39-40
• 4.4.4 聚类结果输出40-41
• 4.5 实验及结果分析41-42
• 4.5.1 优化算法性能测试41-42
• 4.5.2 Kmeans并行优化算法算法可扩展性测试42
• 4.6 本章小结42-43
• 第五章 基于MapReduce的DBSCAN算法并行优化43-53
• 5.1 DBSCAN聚类算法介绍43-46
• 5.1.1 DBSCAN算法基本概念43-44
• 5.1.2 DBSCAN算法执行流程44-46
• 5.2 改进算法设计46-48
• 5.2.1 优化算法思想46-47
• 5.2.2 优化算法描述47
• 5.2.3 优化算法性能分析47-48
• 5.3 基于MapReduce的算法并行实现48-50
• 5.4 实验与结果分析50-52
• 5.4.1 优化算法准确率测试50-51
• 5.4.2 优化算法可扩展性测试51-52
• 5.5 本章小结52-53
• 第六章 总结与展望53-55
• 6.1 总结53
• 6.2 展望53-55
• 参考文献55-57
• 附录1攻读硕士学位期间撰写的论文57-58
• 致谢58

【相似文献】

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

1 刘波;;“算法设计与分析”教学探讨[J];高等理科教育;2007年04期

2 肖小克;陈莉;;《算法设计与分析》实践教学探讨[J];福建电脑;2009年10期

3 穆瑞辉;;计算机算法设计研究与思考[J];数字技术与应用;2012年12期

4 潘博;;构建“算法设计与分析”趣味课堂[J];科教文汇(下旬刊);2013年06期

5 王希常,杨志强;一类考场编排算法的设计[J];山东师范大学学报(自然科学版);2002年04期

6 龙腾芳,高金文;“分而治之”方法在算法设计中的应用[J];渤海大学学报(自然科学版);2004年01期

7 吕国英;;《算法设计与分析》教材建设的实施[J];计算机教育;2007年19期

8 徐子珊;;“算法设计与分析”教学中理论与技术的平衡[J];计算机教育;2008年10期

9 郑红;邵志清;符海波;;“算法设计与分析”课程教学改革初探[J];计算机教育;2008年14期

10 高尚;;“算法设计与分析”课程改革初探[J];计算机教育;2008年14期

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

1 雷咏梅;;椭圆曲线密码体制的算法设计与实现[A];西部大开发 科教先行与可持续发展——中国科协2000年学术年会文集[C];2000年

2 杨盘洪;朱军祥;赵建安;杨静;;机动目标跟踪的模糊变结构交互多模算法[A];2007'中国仪器仪表与测控技术交流大会论文集（二）[C];2007年

3 徐子珊;;《算法设计与分析》课程中的工程教育[A];2005年全国理论计算机科学学术年会论文集[C];2005年

4 王辉;刘治昌;;用一种新算法设计的安全系统[A];2007年中国智能自动化会议论文集[C];2007年

5 舒辉;柳清峰;杜祝平;周蓓;;实践教学模式在本科专业课程教学中的应用[A];中国电子教育学会高教分会2010年论文集[C];2010年

6 彭小宏;阳东升;刘忠;;基于聚类算法的组织协作网设计[A];2006中国控制与决策学术年会论文集[C];2006年

7 李皓;罗熊;;云存储部署优化的进化算法设计[A];2013年中国智能自动化学术会议论文集（第三分册）[C];2013年

8 罗长政;李熙莹;王镇波;罗东华;;一种大流量交叉路口的背景提取与更新算法[A];第十五届全国图象图形学学术会议论文集[C];2010年

9 杨利;李霖;昌月楼;阳国贵;;对称位向量及启发式并行散列连接算法[A];数据库研究与进展95——第十三届全国数据库学术会议论文集[C];1995年

10 张晋;;嵌入式电脑鼠运行算法的研究[A];全国第20届计算机技术与应用学术会议（CACIS·2009）暨全国第1届安全关键技术与应用学术会议论文集（上册）[C];2009年

中国重要报纸全文数据库 前1条

1 ;算法设计的策略[N];电脑报;2003年

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

1 谷伟哲;齐次光滑算法及其应用[D];天津大学;2010年

2 龙海侠;进化算法及其在生物信息中的应用[D];江南大学;2010年

3 谭跃;具有混沌局部搜索策略的粒子群优化算法研究[D];中南大学;2013年

4 尤海峰;求解隐式目标优化问题的交互式进化算法研究[D];中国科学技术大学;2011年

5 张常淳;基于MapReduce的大数据连接算法的设计与优化[D];中国科学技术大学;2014年

6 郭崇慧;地区中长期发展规划若干定量模型、算法及应用研究[D];大连理工大学;2002年

7 蒋蔚;粒子滤波改进算法研究与应用[D];哈尔滨工业大学;2010年

8 孙贺;算法设计中的若干前沿问题[D];复旦大学;2009年

9 陈宁涛;基于二分技术的高效算法设计及其应用[D];华中科技大学;2006年

10 娄晓文;无符号基因组切割再粘贴重组问题的算法研究[D];山东大学;2010年

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

1 李欣园;基于选择偏好的组合聚类算法研究与实现[D];内蒙古大学;2015年

2 杨潇;界约束非线性最小二乘问题的无导数算法[D];上海交通大学;2015年

3 王晓璐;基于Zynq的LS-SVM算法加速器设计[D];哈尔滨工业大学;2015年

4 楼磊磊;医疗保险数据异常行为检测算法和系统[D];浙江大学;2015年

5 齐海龙;基于改进人工蜂群算法的非线性系统辨识方法研究[D];北京化工大学;2015年

6 蔡平梅;结构化稀疏信号的恢复算法研究[D];上海大学;2015年

7 赵晨阳;基于蚁群算法的高阶图匹配方法研究[D];西安电子科技大学;2014年

8 苟清松;多目标粒子滤波检测前跟踪算法研究[D];电子科技大学;2015年

9 李枝勇;蝙蝠算法及其在函数优化中的应用研究[D];上海理工大学;2013年

10 李莲;基于蜂群和粗糙集的聚类算法研究[D];长沙理工大学;2014年

，

本文编号：1071789