基于Hadoop平台的K—means算法优化综述
2017-07-12 13:46孟佳伟孙红
软件导刊 2017年6期
孟佳伟+孙红
摘要：在科技高速发展的今天，海量数据处理问题受到人们广泛关注。将K-means聚类算法与Hadoop平台相结合是处理海量数据问题的一条可靠途径。简单介绍Hadoop和K-means算法以及K-means聚类算法MapReduce并行化实现，并阐述目前Hadoop平台下K-means算法的几种优化方式，最后提出研究展望。
关键词：海量数据处理；Hadoop；K-means；MapReduce
DOIDOI：10.11907/rjdk.171405
中图分类号：TP301
文献标识码：A 文章编号：1672-7800（2017）006-0208-04
0 引言
随着科学技术的飞速发展，互联网技术已经深入到社会的各个领域，由此，数据量呈现出一种指数级增长[1]。如何高效地对这些海量数据进行处理和分析已成为当前研究热点。随着数据规模越来越大，在面对海量数据时，传统的数据挖掘工作会出现储存量不足、用时过长等缺点[2]。而云计算的出现则为解决这些问题提供了新思路，将云计算与传统数据挖掘方法相结合并对其进行优化是科学工作者们不断研究的方向。
聚类分析是数据挖掘方法中的常用方法。1975年，Hartigan对聚类算法提出了系统论述[3]。在众多聚类算法中，K-means算法是被应用与研究最广泛的算法。如今，云计算已经得到了人们的广泛关注，而Hadoop平台是一个可以开发和并行处理大数据的云计算平台。作为一种由分布式技术、网络计算机技术及并行技术发展而来的产物，Hadoop可以说是一种为了适应大规模数据存储以及计算而衍生出的模型构架[4]。本文将对当前基于Hadoop平台的K-means算法的各种优化方法进行综述，并提出展望。
1 Hadoop
从最初版本HDFS和MapReduce于2004年开始实施，到2011年1.0.0版本释出标志Hadoop已初具生产规模，经历了短短不到十年的时间。作为一种开源云计算模型，Hadoop模仿并实现了Google云计算的主要技术，不但可移植性强，而且使用Java语言进行编写[5]。其最早是来自于Google的一款名为MapReduce的编程模型包。MapReduce最早是由Google公司在2004年提出的一种可伸缩并且是线性的用于处理海量数据的并行编程模型[6]。Hadoop平台的出现极大地便利了对于处理海量数据和应用程序的算法研究。Hadoop框架中最核心的部分是MapReduce和HDFS。分布式文件系统Hadoop Distributed File System的缩写即HDFS，其具有极高的容错性并且对机器要求不高，适合部署在廉价的机器上，为分布式计算存储提供底层支持。其能够提供高吞吐的数据访问，因而适合于大规模数据集上的应用。
MapReduce可以使程序自动分布到一个超大集群上并发执行，并且这个超大集群可以由普通机器组成[7]。其中，Map将一个任务分解为多个任务。而Reduce则是将分解之后的多任务的处理结果进行汇总并且得出分析結果。由大量机器组成的机器集群可以被视作分布式系统的资源池，通过对并行任务进行拆分并且交给空闲机器资源处理这种方式提高了计算效率。对MapReduce的工作流程进行展示如图1所示，Map对任务进行分解，Reduce则负责合并。通过Map函数及Reduce函数对一组输入键值对（Key/Value）的计算，得到一组输出键值对。一个Mapper类、Reducer类和一个创建JobConf的驱动函数组成了运行于Hadoop平台下的MapReduce应用程序。另外若有需要，还可以有一个Combiner类，实际上该类也是Reducer的一种实现。基本计算流程首先将输入数据划分为数据块，之后处理数据块得到
2 K-means算法
追根溯源，K-means算法是由MacQueen[9]于1967年提出，并且用数学方法对算法进行了证明。K-means算法由于其简单、高效、易实施等特性受到科学工作者的青睐，被不断改进优化并应用于实践，目前被广泛应用于文本聚类、考古和自然语言处理等诸多领域。K-means算法的第一步工作是初始聚类中心的选取，然后对数据点进行分类后通过对每个聚类平均值的计算来调整聚类中心并且不断迭代循环，最终达到使得类间对象相似性最小，而类内对象相似性最大的目的。算法步骤：首先是自样本随机选取K个对象作为初始聚类中心，然后计算其它数据对象到聚类中心距离并将其分配到相应类，接着计算每一类中所有对象平均值作为新聚类中心，循环上一步与此步骤直至目标函数不再变化[10]。K-means算法本身存在全局搜索能力差、对初始聚类中心依赖性大、聚类效率和精度都不高，而且容易陷入局部最优解等缺点[11]。因此，这些都是科学工作者们不断优化和改进K-means算法的方向。
3 K-means算法MapReduce并行化实现
通过MapReduce模型实现K-means算法并行化的基本思路实际上就是每一次迭代都启动一个MapReduce过程。根据计算需求，对数据做按行存储的安排同时可按行分片且片间数据无相关性[12]。具体流程如图2所示，通过Map函数从HDFS的文件中读取数据并通过每条记录得到其与各质心距离，Map函数的输入为原始文件和聚类质心，通过比较得到各记录到质心的距离，对每个记录进行分类，将其归到距离最近质心所属类，最后将记录以及记录所属类写入中间文件，因此Map函数输出为中间结果。在执行Map函数之后，MapReduce首先会对输出结果进行合并，之后再执行Reduce函数，根据Map函数的输出通过Reduce函数进行聚类中心的更新；同时对标准测度函数值进行计算，为主函数是否结束迭代提供判断依据。如果未结束则继续进行循环并且得到的新聚类中心将由下一轮Map函数使用。在主函数中调用MapReduce过程，每次迭代申请一个新Job。迭代结束的判断标准就是两次得到平方误差和差值小于给定阈值，则最后结果就是Map函数最后一次中间结果[13]。
4 Hadoop平台下的K-means算法优化
4.1 粒子群算法引入
有研究者[14]提出了一种并行基于MapReduce的K-PSO算法。马汉达，杨丽娜[15]进一步将PSO-KM全部并行运行，提出了一种用粒子群算法对K-means算法的初始聚类中心进行优化的在Hadoop平台上加以实现的改进方法，这种改进使得K-means算法和PSO算法都可以用MapReduce模型处理。引入PSO算法在一定程度上克服了K-means算法对初始聚类中心敏感的问题。在Map阶段，更新和移动并且评估粒子，之后判断更新单个粒子最优解，如果粒子有更新则进行粒子群最优解的更新；然后进入Reduce阶段，接收更新后粒子并对粒子信息进行合并，且更新粒子群最优解。
其中，进行PSO算法处理操作的第一步是初始化和构建初始粒子群，再以每个粒子为每个Map接收新位置、速度、价值以及单个粒子最优适应度，最终的Key为粒子id。Value属性则是更新后粒子属性字符串，接收Key和List（Value）的为PSO-Reduce函数。特定粒子的id即为这个Key，最新更新的粒子属性信息包含于Value列表。通过Reduce函数实现信息合并，全局更新粒子群最优位置以及粒子群最优适应度并输出粒子群最优粒子。
4.2 Canopy算法与K-means算法相结合
朱蔷蔷、张桂芸等[16]提出了一种在Hadoop平台下将Canopy算法与K-means算法结合使用的优化思想，使用Canopy算法对数据经行预处理，得到K-means算法的K值，并且K值由得到的Canopy个数决定。实验证明，这种优化方式具有良好的加速比及可扩展性。毛典辉[17]针对Canopy-Kmeans算法中的Canopy选择具有随意性和盲目性的问题，提出一种使用“最大最小原则”对算法进行改进，并通过MapReduce并行框架进行并行扩展的优化思想。改进后的算法在抗噪能力和分类准确率上明显优于随机挑选Canopy策略。基于以上研究，卢胜宇、王静宇等[18]提出了一种新的改进方式，针对K-means算法选择初始聚类中心的盲目性使用余弦相似度度量及Canopy算法进行改善，并通过并行计算框架实现并行扩展。Canopy算法的过程首先是进行阈值tl、t2的设定，并且t1要大于t2；然后在数据集里随机选取中心点并且将与之距离不大于t1的数据点放入聚类中心是刚才选取的点的聚簇。之后剔除数据集中与中心点距离不大于t2的点，循环至数据集为空。通过优化之后，在Hadoop平台下通过Map及Reduce阶段获得全局Canopy中心集合，并使用其进行粗糙聚类之后得到数个相互重叠的Canopy聚类集合，将其作为下一步K-means初始聚类中心。所有对象到簇类中心距离是K-means算法每次迭代都必须计算的。优化之后通过实验证明，其在处理海量数据时具有较好的聚类质量、加速比及扩展性。
4.3 Hash算法引入
通过散列函数将任意长度输入转化为固定长度输出即为Hash算法，也称为散列算法[19]。对于海量高维数据在Hadoop平台下使用K-means算法存在聚类效果不好的问题，张波，徐蔚鸿等[20]提出了基于Hash改进的并行化并在算法整体并行化时通过Combine等机制改善执行效率及并行化程度的优化方案。通过Hash改进的并行化方案的原理是将高维数据映射至压缩标识空间，进而实现聚类关系的挖掘以及初始聚类中心的选取。用Hash算法进行初始聚类中心选取就是将不同相似度数据散列至不同的地址空间。对应地将相似度大的数据散列到同一地址空间。初始聚类中心就是选自最多同义词的K个地址空间。在实现并行化时，设计了3个独立运行的Job作业链工作且上一Job输出为下一输入。其中第1个Job用于构造散列表，第2个则是计算初始聚类中心，第3个用于完成对全部数据的K-means聚类。最后通过实验证明，这种优化对聚类稳定性及准确率都有很好的改善作用。
4.4 遗传算法与K-means算法相结合
与K-means算法一样，遗传算法也是广为人知的算法之一[21]。因此将K-means算法与遗传算法相结合的研究也吸引着许多研究者。戴文华、焦翠珍[22]等将K-means聚类算法与并行遗传算法相结合，对聚类的结果及K值进行优化。之后，贾瑞玉、管玉勇等[23]提出了基于MapReduce模型的并行遗传K-means算法，实验证明其优化效果良好。实质上，遗传K-means算法就是把每个聚类中心坐标当成染色体基因。聚类中心个数就是染色体长度，对若干相异染色体进行初始化操作并将其当成一个种群进行遗传操作，最终获得适应度最大染色体，而最优聚类中心坐标就是解析出的各中心点坐标。该算法第一步是初始化聚类个数K和最大遗传代数以及种群个数P；第二步是初始化种群也即随机产生种群个数且每个都表示一个聚类结果的染色体；第三步是对染色体进行K-means操作并評价适应度和记录；第四步是对结束条件进行判断看是否达到，若未满足则进行选择、交叉和变异操作；第五步转到步骤三。在Map和Reduce设计过程中，在Map阶段进行个体初始化和适应度评价以及K-means操作。在Reduce过程中，针对相同键，满足停机条件则输出各子种群中最优个体后选出最终的最优个体。依据是染色体末位适应度值，若否，则需要完成一个子种群的遗传操作。
4.5 人工鱼群算法与K-means算法相结合
将人工鱼群算法与K-means算法相结合也是一种优化思路[24]。陈书会、周莲英[25]利用人工鱼群算法对K-means算法进行优化，并通过MapReduce并行处理框架进行并行处理。通过afsa全局寻优特点在数据集中靠鱼群行为搜索最优解或与之相近解并将其作为K-means初始值。并行人工鱼群算法思想就是对鱼群进行划分，划分之后的各子鱼群在所给数据集中获得此次过程局部最优解。本次运行的全局最优解通过对子鱼群最优解进行汇总之后获得。用人工鱼群算法优化K-means算法后在执行速度和加速比以及准确度等方面都有很大改善。
4.6 对数据多次采样并引入密度法
李欢、刘峰等[26]提出了一种优化思路，即对海量数据通过多次采样的方式进行聚类个数的确定，再加上用密度法来确定采样数据聚类中心，原始数据聚类中心通过归并各样本中心点的方式得到。在数据集合中，一个数据对象邻域内其它数据对象越多，距离它的路径越小，就证明密度越大，则以该数据对象作为聚类中心能很好地反映出数据分布特征[27]。正是由于这一优异特性，因此采用密度法来选择初始聚类中心。李欢，刘峰等[26]在Hadoop平台下实施了改进后的算法，通过实验的方式证明优化后的算法在聚类精度和聚类性能上有了明显提高。
5 结语
Hadoop和K-means算法都经历了很长的一段发展时间，它们所具有的独特优势使得其被广大研究者不断地优化和使用。在互联网高速发展的今天，将Hadoop与K-means算法相结合，并不断地对其加以优化是处理当前海量数据的有效途径。本文介绍的几种基于Hadoop平臺的K-means算法优化大多是通过引入其它算法对K-means算法的初始聚类中心选取及K值进行改善来实现。将一些能够弥补K-means算法本身缺点的、高效的算法与K-means算法相结合，并在Hadoop平台下实现是下一步重点研究方向。
参考文献：
[1]张石磊，武装.一种基于Hadoop云计算平台的聚类算法优化的研究[J].计算机科学，2012，39（s2）：115-118.
[2]孙玉强，李媛媛，陆勇.基于MapReduce的K-means聚类算法的优化[J].计算机测量与控制，2016，24（7）：272-275.
[3]吴夙慧，成颖，郑彦宁，等.K-means算法研究综述[J].现代图书情报技术，2011（5）：28-35.
[4]唐世庆，李云龙，田凤明，等.基于Hadoop的云计算与存储平台研究与实现[J].四川兵工学报，2014（8）：97-100.
[5]王宏宇.Hadoop平台在云计算中的应用[J].软件，2011，32（4）：36-38.
[6]王鑫.基于Hadoop平台的MapReduce的技术研究[J].信息通信，2015（6）：5-6.
[7]向小军，高阳，商琳，等.基于Hadoop平台的海量文本分类的并行化[J].计算机科学，2011，38（10）：184-188.
[8]谢桂兰，罗省贤.基于Hadoop MapReduce模型的应用研究[J].微型机与应用，2010，29（8）：4-7.
[9]MACQUEEN J.Some methods for classification and analysis of multivariate observations[C].Proc.of Berkeley Symposium on Mathematical Statistics and Probability，1967：281-297.
[10]周爱武，于亚飞.K-Means聚类算法的研究[J].计算机技术与发展，2011，21（2）：62-65.
[11]洪月华.蜂群K-means聚类算法改进研究[J].科技通报，2016，32（4）：170-173.
[12]李建江，崔健，王聃，等.MapReduce并行编程模型研究综述[J].电子学报，2011，39（11）：2635-2642.
[13]周婷，张君瑛，罗成.基于Hadoop的K-means聚类算法的实现[J].计算机技术与发展，2013，23（7）：18-21.
[14]WANG J，YUAN D，JIANG M.Parallel K-PSO based on MapReduce[C].International Conference on Communication Technology，2012：1203-1208.
[15]马汉达，杨丽娜.基于Hadoop的PSO-KM聚类算法的并行实现[J].信息技术，2015（7）：90-94.
[16]朱蔷蔷，张桂芸，刘文龙.基于Hadoop平台上面向电影数据集Kmeans算法的改进[J].哈尔滨师范大学：自然科学学报，2012，28（1）：32-36.
[17]毛典辉.基于MapReduce的Canopy-Kmeans改进算法[J].计算机工程与应用，2012，48（27）：22-26.
[18]卢胜宇，王静宇，张晓琳，等.基于Hadoop平台的K-means聚类算法优化研究[J].内蒙古科技大学学报，2016，35（3）：264-268.
[19]KASSELMAN P R.A fast attack on the MD4 hash function[C].COMSIG '97.Proceedings of the 1997 South African Symposium on Communications and Signal Processing，1997：147-150.
[20]张波，徐蔚鸿，陈沅涛，等.基于Hash改进的K-means算法并行化设计[J].计算机工程与科学，2016，38（10）：1980-1985.
[21]李红梅.遗传算法概述[J].软件导刊，2009（1）：67-68.
[22]戴文华，焦翠珍，何婷婷.基于并行遗传算法的K-means聚类研究[J].计算机科学，2008，35（6）：171-174.
[23]贾瑞玉，管玉勇，李亚龙.基于MapReduce模型的并行遗传K-means聚类算法[J].计算机工程与设计，2014，35（2）：657-660.
[24]邹康，刘婷，鲍韦韦，等.人工鱼群算法研究综述[J].山西电子技术，2012（2）：92-93.
[25]陈书会，周莲英.基于 MapReduce的afsa-km聚类算法并行实现[J].软件导刊，2016，15（7）：51-54.
[26]李欢，刘锋，朱二周.基于改进K-means算法的海量数据分析技术研究[J].微电子学与计算機，2016，33（5）：52-57.
[27]ERISOGLU M，CALIS N，SAKALLIOGLU S.A new algorithm for initial cluster centers in K-means algorithm[J].Pattern Recognition Letters，2011，32（14）：1701-1705.
（责任编辑：孙 娟）
英文摘要Abstract：Today， with the rapid development of science and technology， more and more people pay attention to the problem of massive data processing.The combination of K-means clustering algorithm and Hadoop platform is a reliable way to deal with massive data problems.In this paper， we do a brief introduction about Hadoop and K-means algorithm and parallel implementation of K-means clustering algorithm based on MapReduce.At the same time， we do a introduction and elaboration about several optimization methods of K-means algorithm based on Hadoop platform .Finally， the future research directions are discussed.
英文关键词Key Words： Mass Data Processing；Hadoop；K-means；MapReduce
