２０１５年１１月第３６卷 第１１期
计算机工程与设计
COM PU T ER ENGINEERING AND DESIGN
Nov ．２０１５Vol 畅３６ No 畅１１
基于云计算平台的聚类算法
孟海东，任敬佩
（内蒙古科技大学信息工程学院，内蒙古包头０１４０１０）
摘 要：针对大数据的海量与高维特性，提出一种在云计算平台上基于MapReduce 框架的距离三角不等式Canopy ‐Kmeans 并行聚类算法。利用三角不等式的原理减少计算冗余，提高原算法的执行速度。实验结果表明，该算法减少了I ／O 以及网络传输的消耗，克服了算法陷入局部最优解的缺点，使之能够充分利用集群的计算和存储能力对大数据进行聚类分析。关键词：云计算；Canopy ‐Kmeans 算法；三角不等式原理；大数据；并行
中图法分类号：T P ３１１ 文献标识号：A 文章编号：１０００‐７０２４（２０１５）１１‐２９９０‐０５doi ：１０畅１６２０８／j 畅issn １０００‐７０２４畅２０１５畅１１畅０２２
收稿日期：２０１４‐１２‐０８；修订日期：２０１５‐０３‐０２基金项目：内蒙古自然科学基金项目（２０１２M S ０６１１）
作者简介：孟海东（１９５８），男，内蒙古包头人，博士，教授，研究方向为数据挖掘技术、矿业系统工程；任敬佩（１９８７），男，河南安阳人，硕士研究生，研究方向为数据挖掘技术。E ‐mail ：haidongm ＠imust 畅edu 畅cn
Clustering algorithm based on cloud computing platform
M ENG Hai ‐dong ，REN Jing ‐p ei
（School of Information Engineering ，Inner Mongolia University of Science and Technology ，Baotou ０１４０１０，China ）Abstract ：For processing massive data ，a MapReduce based triangle inequality Canopy ‐Kmeans algorithm was proposed ．The theory of the triangle inequality was adopted ，and the computational redundancy and operation time were reduced ．The experi ‐
mental results demonstrate that the algorithm reduces the consumption of I ／O and network transmission ，and overcomes the shortage of local optimum ，so it can effectively process big data based on MapReduce framework ．Key words ：cloud computing ；Canopy ‐Kmeans ；triangle inequality ；big data ；p arallel
0 引 言
目前，针对于大数据［１‐３］的处理，多采用并行或分布式架构来提高系统的扩展性，并利用多线程的并行式结构，或者是基于Apache 推出的开源云计算Hadoop ［４，５］平台实现，其中K ‐means 算法的应用最为广泛。文献［６］提出了基于M PI 的分布式聚类，它虽然从某种程度上利用集中式存储提高了算法的时效性，但是，由于该算法在计算过程当中是单节点运行的，所以在处理大数据进行聚类分析任务时，该算法的效率还不够快；文献［７，８］提出了在Hadoop 平台下，利用MapReduce 模型框架，实现了K ‐
means ［９‐１１］分布式聚类，提高了聚类算法的加速比；文献［１２］利用Spark （Pregel 和HaLoop ［１３］）模型框架，实现了迭代式的分布式聚类，提高算法的可扩展性；文献［１４］中为了进一步提高聚类算法的效率，解决初始中心点的随机性和盲目性，在该算法在基于MapReduce 分布式框架的聚类中，加入了Canopy 算法对原数据的预处理，初步的解决了该算法选取初始中心点的随机性与初始确定聚类个数
的问题；文献［１５］中提出基于MapReduce 的Canopy ‐Kmeans 改进算法，针对于Canopy 算法的缺点采用了“最
小最大原则”，利用云计算平台的集群计算和存储能力，更进一步提高该算法的时效性和有效性。
鉴于以上改进后的K ‐means 聚类算法的优点，利用文献［１６］在K ‐means 算法引进了三角不等式原理的基础上，提出一种改进的BRTI ‐K ‐means （MapReduce based triangle inequality Canopy K ‐means ，BRTI ‐K ‐means ）算法。主要通过基于开源云计算平台，利用MapReduce 分布式框架，融合了距离三角不等式定理，同时在大数据的预处理过程当中，使用Canopy 算法对原始的大数据进行了预处理，进一步实现了K ‐means 算法在聚类分析过程中的改进；为了进一步验证BRTI ‐K ‐means 算法的优越性，将该算法与K ‐means 和Canopy ‐Kmeans 算法进行了算法比较。
1 BRTI ‐K ‐means 算法
1畅1 基于距离三角不等式聚类算法
基于云计算平台下的MapReduce 框架下，利用传统的