基于mapreduce的k_means聚类算法研究

《基于mapreduce的k_means聚类算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ｙ．学校巧巧：１腿７０分类号：ＴＰ３０１学号！１３２如１舶１上辜作絶Ｉ乂多硕±学位论文基于ＭａｐＲｅｄｕｃｅ的Ｋｍｅａｎｓ聚类算法研究学院：倍烏与机电工程学晓专业；计巧机应巧技术■硏究忘向：数据分析与挖掘硏究生姓名：张明微：吴海涛指导教师１６０３月完成日期：２０年ｎ上海师范大学硕士学位论文摘要摘要随着互联网应用的飞速发展，数据量的积累也越来越多。如何更高效快捷地从海量数据中得到有价值的信息并将其应用到相关领域中，成为当前范围内急需解决的前沿问题。为了解决这一难题，研究人员提出了越来越多的聚类分析算法。目前

2、，聚类分析已经在很多领域被广泛应用，例如：金融、军事、医疗、管理等。K_means聚类算法是聚类分析中使用较为广泛的一种，其思想简单且易操作.但是该算法随机选择初始化中心使聚类结果不稳定且易出现局部最优解，此外，当数据集中存在孤立点时聚类结果也会受到影响。随着聚类数据日渐增多，K_means算法迭代次数增加且耗时严重，传统的单机运行模式已经不能满足实际需要。MapReduce是基于Hadoop平台的一种分布式计算模型且是当前运用较为广泛的一种分布式计算框架，HDFS也实现了对文件的分布式存储，所以将单机上的聚类分析算法移植到Hadoop平台上可进行分布式聚类任务。针对上述K_means算法的不

3、足，文章中提出了一种对K_means算法进行优化的算法且对其实现了并行化。首先，本文梳理了聚类分析的研究背景及国内外研究现状并列举了论文的主要工作及创新点。其次介绍了聚类分析技术中的度量和聚类算法的划分等，并通过HDFS分布式文件系统及MapReduce编程模型两方面介绍了Hadoop技术。然后，针对K_means算法随机选择初始中心点和易受孤立点影响问题提出了一种基于最大距离法改进的初始中心点选择算法和孤立点排除法，此外还结合MapReduce编程模型的特征对改进后的K_means算法进行并行化处理，使其能够运行在Hadoop平台上。最后，不仅在单机环境下做了对比实验来证明本文算法在处理聚类

4、问题时的优劣性还在并行环境条件下通过加速比和扩展率来证明文中提出的算法是否适合对其进行并行化处理。关键词：聚类分析；K_means；Hadoop；MapReduce；HDFSIAbstractShanghaiNormalUniversityMasterofPhilosophyAbstractWiththerapiddevelopmentofinternetapplications,moreandmoredataisaccumulated.Howtogetvaluableinformationfromthemassivedatamoreefficientlyandquickly,andapply

5、ittotherelatedfield,becomestotheurgentproblemthatneedstobesolvedurgentlyinthecurrentrange.Inordertosolvethisproblem,researchershaveputforwardmoreandmoreclusteringanalysisalgorithms.Atpresent,clusteringanalysishasbeenwidelyusedinmanyfields,suchasfinance,military,medical,managementandsoon.K_meansclust

6、eringalgorithmiswidelyusedinclusteringanalysis,theideaissimpleandeasytooperate.Butthecenterforrandominitializationwouldmaketheclusteringresultsunstableandpronetolocaloptimalsolution.Inaddition,whenthereareisolatedpointsinthedataset,theclusteringresultswillbeaffected.Withtheincreasingofclusteringdata

7、,thenumberofiterationsoftheK_meansalgorithmisincreasinganditisserioustime-consuming,andthetraditionalstand-aloneoperationmodecan'tmeetthedevelopmentneedsrightnow.MapReduceisakindofdistributedcomputing