云计算环境下海量数据的并行聚类算法研究

《云计算环境下海量数据的并行聚类算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据分类号UDC密级单位代码1Q151云计算环境下海量数据的并行聚类算法研究许玉杰指导教师曲雯毓职称学位授予单位大连海事大学教授申请学位级别工学博士学科(专业)计算机应用技术论文完成日期2014年9月答辩日期2014年12月答辩委员会主席万方数据TheResearchofParallelClusteringAlgorithmofMassiveDatainCloudComputingEnvironmentDissertationSubmittedtoDalianMaritimeUniversityInpartialfulfillmentoftherequi

2、rementsforthedegreeofDoctorofEngineeringByYujieXu(ComputerApplicationTechnology)DissertationSupervisor：ProfessorWenyuQuSeptember2014万方数据大连海事大学学位论文原创性声明和使用授权说明原创性声明本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果，撰写成博／硕士学位论文==亟过箕巫境王渔量麴塑笪羞复苤耋簋洼盟童：。除论文中已经注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本论文中

3、不包含任何未加明确注明的其他个人或集体已经公开发表或未公开发表的成果。本声明的法律责任由本人承担。学位论文作者签名：学位论文版权使用授权书本学位论文作者及指导教师完全了解大连海事大学有关保留、使用研究生学位论文的规定，即：大连海事大学有权保留并向国家有关部门或机构送交学位论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将本学位论文的伞部或部分内容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论文。同意将本学位论文收录到《中国优秀博硕士学位论文全文数据库》(中国学术期刊(光盘版)电子杂志社)、《中国学位论文全文数据

4、库》(中国科学技术信息研究所)等数据库中，并以电子出版物形式出版发行和提供信息服务。保密的论文在解密后遵守此规定。本学位论文属于：保密口在——年解密后适用本授权书。不保密11；2"(请在以上方框内打“-4”)论文作者签名：许乏·毛导师签名：。步受琵日期：加／≯年72月；口日万方数据创新点摘要1针对k．means++聚类算法中的初始化方法在MapReduce并行处理框架下需要大量的作业迭代，提出并行可扩展的k．means++聚类算法，它的初始化方法仅需要一个MapReduce作业就可以选出k个点，从而提升了k-means++聚类算法的效率，并且证明此算法是k—

5、means最优聚类结果的O(a2)近似，其中口=8(2+Ink)。2考虑scalablek-means++聚类算法的初始化方法每次迭代需要两个MapReduce作业的问题，提出快速的scalablek-means++聚类算法，它采用过采样修正的方法使scalablek-means++的初始化方法每次迭代仅需要一个MapReduce作业，节省了大量的I／O成本及运行时问。3针对k-means聚类算法在处理海量倾斜数据时会导致Reduce任务负载不均衡，延长整个聚类算法运行时间的问题，提出基于抽样估计的数据划分方法，通过抽样估计理论获得原始数据的分布，根据这些信

6、息制定合理的数据划分方案，并应用于MapReducek—means聚类算法中，缩短了聚类算法的运行时间。万方数据中文摘要摘要聚类是数据分析和管理最基础的算法之一，它已经被广泛应用于计算机科学及其相关领域。然而海量数据的出现使得传统的聚类算法受到了极大的挑战，例如聚类算法的可扩展性差、效率低等。目前，以MapReduce为代表的云计算技术越来越受到商业界和学术界的关注，并且MapReduce已经发展成为最流行的海量数据处理模型之一。本文研究云计算环境下海量数据的并行聚类算法，重点是在MapReduce处理模型中对k-means、k-means++和scalab

7、lek-means++聚类算法的研究，目的是提高这些聚类算法的可扩展性和效率。论文完成的工作和主要的研究成果如下：在MapReduce并行处理框架下，针对k．means++初始化方法序列化特性导致其可扩展性差并且需要大量MapReduce作业迭代的问题，本文提出1r并行可扩展的k-means++聚类算法，它的初始化方法仅需要一次MapReduce作业迭代就可以选出k个中心点，在Map阶段运行标准的k-means++初始化算法，而在Reduce阶段运行加权的k．means++初始化算法。这种方法1i仅提高rk-means++聚类算法在处理海量数据时的效率，而且

8、它被证明是k-means最优聚类结果的o(a21近似