KNN分类算法的MapReduce并行化实现

《KNN分类算法的MapReduce并行化实现》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第45卷第4期2013年8月南京航JournalofNanjing空航天大学UniversityofAeronautics学&A报stronauticsKNN分类算法的MapReduce并行化实现闫永刚1马廷淮1’2王建3V01．45No．4Aug．2013(1．南京信息工程大学计算机与软件学院，南京，210044；2．南京信息工程大学江苏省网络监控中心，南京，210044；3．南京大学电子科学与工程学院，南京，210093)摘要：为了提高k-nearestneighboralgorithm(KNN)算法处理大数据集的能力，本文利用MapReduce并行编程模型，同时结合KN

2、N算法自身的特点，给出了KNN算法在Hadoop平台下的并行化实现。通过设计Map、Combine和Reduce3个函数，实现了KNN算法的并行化。Map函数完成每个测试样本与训练样本之间的相似度计算，Combine函数作为一个本地的Reduce操作，用以减少中间计算量及通信开销，Reduce函数则根据上述函数得到的中间结果计算出k近邻并作出分类判断。实验结果表明：较之以往的单机版方法，在Hadoop集群上实现的并行化KNN算法具有较好的加速比和良好的扩展性。关键词：KNN分类；并行计算；MapReduce模型；Hadoop中圈分类号：TP391文献标志码：A文章编号：100

3、5—2615(2013)04一0550—06ParallelImpIementingKNNClassificationAlgorithmUsingMapReduceProgrammingM0deYr口nYro，lgg口，191，^—缸Ti竹g．}l“口i1’-，W口729_，i口竹3(1．SchoolofComputerandSoftware，NanjingUniversityofInformationScience&Technology，Nanjing，210044，China；2．JiangsuEngineeringCenterofNetworkMonitoring，Na

4、njingUniversityofInformationScience&Technology，Nanjing，210044，China；3．SchoolofElectronicScienceandEngineering，NanjingUniversity，Nanjing，210093，China)Abstract：InordertoimprovetheabilityofKNNalgo“thmtoprocessmassivedata，anewtechniquebasedonHadoopplatformisused．Consideringthecharacteristicsoft

5、heKNNalgorithmitself，thepar—allelismofKNNbasedontheMapReduceprogrammingmodelisimplemented．Threefunctionsarede—signedfortheimplementationoftheparallelism，namedMap，CombineandReduce．TheSimilaritybe—tweeneachtestinstancesandthetrainingdatasetareevaluatedbyIⅥapfunction．Forreducingthecom—putation

6、alcomplexityandsavingnetworkbandwidth，theCombinefunctionisusedasalocalReduceop—eration．ReducefunctionisusedtogettheKNNclassificationbasedontheintermediateresults．Theex—perimentontheHadoopplatformshowsthemethodhasexcellentlinearspeedupwithanincreasingnumberofcomputernodesandgoodscalability．K

7、eywords：KNNclassification；paraUelcomputing；MapReduceprogrammingmodel；Hadoop随着信息技术的进步以及信息化社会的发展，在科学研究、计算机仿真、互联网应用和电子商务‘·3等领域，数据量呈现快速增长的趋势。比如，大型强子对撞机每年积累的新数据量为15PB左右；沃尔玛公司每天通过6ooo多个商店，向全球客户销售超过2．67亿件商品等。为了分析和利用这些庞大的数据资源，必须依赖有效的数据分析技术。数据挖掘技术是一种通过分析海量数据从中基金项