基于mapreduce的canopy_kmeans改进算法_毛典辉

《基于mapreduce的canopy_kmeans改进算法_毛典辉》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、222012，48（27）ComputerEngineeringandApplications计算机工程与应用基于MapReduce的Canopy-Kmeans改进算法毛典辉MAODianhui北京工商大学计算机与信息工程学院，北京100048SchoolofComputerandInformationEngineering,BeijingTechnologyandBusinessUniversity,Beijing100048,ChinaMAODianhui.ImprovedCanopy-KmeansalgorithmbasedonMapReduce.ComputerEngineer

2、ingandAp-plications,2012,48（27）：22-26.Abstract：InordertosolvetheproblemthathowtovoidrandomCanopyselectionofCanopy-Kmeansalgorithm,thispaperintroducesanimprovedalgorithmbasedontheminimumandmaximumprincipleandrealizesprocessingmassivedatabasedonMapReduceframework.Meanwhile,thealgorithmiscarriedout

3、inmassiveInternetnewsag-gregation.TheexperimentsshowthatthestrategyofCanopyselectionbasedontheminimumandmaximumprinci-plehashigherclassificationaccuracyandnoiseimmunitycomparedtorandomstrategy.Keywords：Canopy-Kmeans;MapReduce;distributedaggregation摘要：针对分布式Canopy-Kmeans算法中Canopy选取的随机性问题，采用“最小最大原则

4、”对该算法进行了改进，避免了Cannopy选取的盲目性；采用MapReduce并行计算框架对算法进行了并行扩展，使之能够充分利用集群的计算和存储能力，从而适应海量数据的应用场景。以海量互联网新闻信息聚类作为应用背景，对改进后的算法进行了实验分析。实验结果表明：该方法较随机挑选Canopy策略在分类准确率以及抗噪能力上都明显提高，而且在处理海量数据时表现出较大的性能优势。关键词：Canopy-Kmeans算法；MapReduce；分布式聚类文章编号：1002-8331（2012）27-0022-05文献标识码：A中图分类号：TP3011引言算效率较高等优点，因此成为应用最为广泛的分布聚类

5、是按照“物以类聚”的思想将数据集合分成式聚类算法。Canopy-Kmeans是一种对K-means优若干类或簇，使得每个簇中的数据最大程度得相似，化的聚类算法，引入Canopy后，每次只比较落在同一[1]区域内对象与中心点之间的距离，通过减少比较次属于一种无监督的学习过程。当前绝大多数聚类算法适用于集中式数据的处理，算法效率受限于单数大大降低整个聚类的运行时间，提高了算法的计[7]机处理能力，面对日益增长的分布式存储的海量信算效率。算法在实际应用中需预先设置聚类的初息，现有的聚类算法均存在着伸缩性与扩展性较差始种子点（初始Canopy中心点）、聚类个数k（Canopy[2]个数）、Ca

6、nopy区域大小等初始值，初始值选取的好等问题，因此由多台计算机共同参与计算的分布式聚类算法成为当前聚类算法的研究重点。坏对最终聚类的质量有较大影响，如Canopy中心点目前，在已有的分布式聚类算法研究中，K-means选取过密容易导致算法陷入局部最优，Canopy区域半[3]径大小直接影响算法的执行效率与分类准确率等，而算法与基于密度的DBDC算法、基于层次聚类的[4][5]Canopy-Kmeans算法的初始值设置一般依据经验或者RACHET算法、CHC算法以及基于综合主元分析[6]多次实验试取，因此具有较大的盲目性与随机性。的CPCA聚类算法等相比较，具有算法实现简单、计基金项目

7、：国家自然科学基金（No.2009ZX05038-001）；北京市属高等学校科学技术与研究生教育创新工程建设项目（No.PXM2012_014213_000037）。作者简介：毛典辉（1979—），男，博士，讲师，主要研究领域为云计算、基于位置的服务等。E-mail：maodianhui@gmail.com收稿日期：2012-01-16修回日期：2012-05-23CNKI出版日期：2012-07-03DOI：10.3778/j.issn.10