更多内容
发布时间：2020-11-04 00:22 浏览次数：4448
摘要：在科技高速发展的今天，海量数据处理问题受到人们广泛关注。将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则是将分解之后的多任务的处理结果进行汇总并且得出分析�Y果。由大量机器组成的机器集群可以被视作分布式系统的资源池，通过对并行任务进行拆分并且交给空闲机器资源处理这种方式提高了计算效率。对MapReduce的工作流程进行展示如图1所示，Map对任务进行分解，Reduce则负责合并。通过Map函数及Reduce函数对一组输入键值对（Key/Value）的计算，得到一组输出键值对。一个Mapper类、Reducer类和一个创建JobConf的驱动函数组成了运行于Hadoop平台下的MapReduce应用程序。另外若有需要，还可以有一个Combiner类，实际上该类也是Reducer的一种实现。基本计算流程首先将输入数据划分为数据块，之后处理数据块得到键值对。之后进入Map操作将产生的中间结果被区分地写到输出文件里。Mapper输出的中间键值对可根据需要为Mapper指定Combiner类并对该输出进行合并后输出至文件。当Map任务结束，开始Reduce过程。每个Reduce任务包括组合和排序以及聚集数据。根据中间结果中的键Key，MapReduce框架将多个Mapper产生的同一个Key的中间结果传输至处理这个Key的Reducer类。进行组合和排序时将具有相同Key值的对进行合并，这些对来自不同Mapper。通过组合和排序后得到的将被送至Redueer类的Reduce方法中进行处理并且结果将写入HDFS管理的输出文件[8]。
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.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].微电子学与计算�C，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
本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。QQ:522-52-5970
贵公网安备52010202003825