摘  要： 随着大数据时代的到来，传统的聚类算法很难高效地处理海量数据，而云计算平台凭借负载均衡、网络存储、虚拟化等技术，有效地突破了耗时耗能的瓶颈，为海量数据的处理提供了良好的解决方案。主要研究了Hadoop平台下的MapReduce编程模型及传统K-means算法，提出了一种基于MapReduce的并行化K-means算法的设计方案，包括Map函数和Reduce函数的设计。通过实验，验证了并行化K-means算法适用于较大规模数据集的分析和挖掘。

　　关键词： 云计算；数据挖掘；MapReduce编程模型；K-means聚类算法；并行化

0 引言

　　随着信息化社会的发展，各个行业中产生的数据都在以爆炸式的速度增长。典型的聚类算法——K-means算法是基于划分的聚类算法，因其快速、简单的特性而被广泛应用。但在面对海量数据时，传统的K-means算法无论是在时间复杂度还是空间复杂度上都遇到了瓶颈[1]，而云计算技术的出现为海量数据的处理提供了良好的解决方案。

　　云计算是一种基于互联网的计算方式。Hadoop则是云计算技术的开源实现，具有高容错、跨平台等优势。它主要包含两个部分：分布式文件系统（HDFS）和MapReduce编程模型。本文在基于Hadoop云计算平台，利用MapReduce编程模型实现了传统K-means聚类算法的并行化设计，并进行了相关实验的验证。

1 MapReduce编程模型

　　MapReduce编程模型，顾名思义，由Map（映射）阶段和Reduce（规约）阶段组成，分别用两个函数表示，即Map函数和Reduce函数[2]。MapReduce作业流程如图1所示。

　　Map阶段：Map任务运行在集群的从节点上，多个Map任务相互间是独立运行的。原始数据在进入Map函数前，会将原始大数据集划分并格式化为<key1，value1>键值对的形式。经过Map函数的运算处理后产生一个或多个中间键值对<key2，value2>。

　　Shuffle阶段：它由Partition（数据分割）和Combine（数据合并）组成。Combine就是将Map任务输出的中间结果中有相同key2的<key2，value2>对合并成一对。Partition则是采用默认hash函数将中间结果按照key2值的范围分成R份，发送并保证某一范围内的key2由同一个Reduce任务来处理。

　　Reduce阶段：每个Reduce任务需要从多个Map任务节点取得其负责的key2区间内的中间结果。Reduce函数接收到形如<key2，（list of value2）>形式的输入，进行处理后产生键值对<key3，value3>作为结果，并将结果输出到HDFS上。

　　为了方便理解，上述过程中数据格式的变化如图2所示。

2 基于MapReduce的并行K-means算法的设计

　　2.1 K-means聚类算法的基本思路

　　K-means算法是聚类算法中使用最广泛的基于划分的算法，其基本思想是：将空间中的n个对象集合以K个点为中心进行簇的划分，归类到与其距离最近的中点[3]。通过迭代的方式，逐次更新聚类中心的值并重新划分簇，直至目标函数收敛。K-means算法采用距离作为相似性的评价指标，其目标函数可表示为：

　　其中，xi表示数据集X={x1，x2，…，xN}中第i个样本，N为样本总数；Cj表示第j个簇，K为簇的总个数，zj则表示第j个簇的中心。

　　假设共有n个数据对象，计划划分为K个簇，t为迭代次数，O为一次迭代中计算某一对象到各个类的中心距离的时间复杂度，那么串行实现K-means算法的时间复杂度为n×K×t×O[4]。由此可见，当面对大数据时，算法的时间复杂度将成倍地增加。

　　2.2 K-means聚类算法的MapReduce化的设计

　　K-means算法中，计算数据对象与聚类中心距离是该算法中反复进行的操作，并且每个数据对象到聚类中心距离的计算过程都是相互独立的。图3描述了基于MapReduce的并行K-means算法的设计方法，其中数据的分片由MapReduce环境自行完成，只需要编写Map函数和Reduce函数的实现代码即可。

　　2.2.1 Map函数的设计

　　首先，Map函数逐行扫描数据段，按行作为数据对象，记录为<行号，数据内容>键值对；接着，与保存在全局变量中聚类中心进行运算，得出数据对象与各个聚类中心的距离；最后，将数据对象分配给距离最近的类中，产生<聚类ID，数据内容>键值对作为函数输出。Map函数的伪代码如下：

　　void map（LongWritable key，Text point，Context context）{

　　centerIndex=0；//初始化数据对象所在的类

　　minDis=MAXDISTANCE；

　　//初始化数据对象与聚类中心的最小距离

　　for（int i=0；i<k；i++）{//遍历各个聚类中心

　　tempDis=Dis（point，cluster[i]）；

　　//计算数据对象与聚类中心的距离

　　if（tempDis<minDis）{

　　//将数据对象分配至距离最近的类

　　minDis=tempDis；

　　centerIndex=i；

　　}

　　}

　　context.write（centerIndex+1，point）；

　　//输出<类ID，数据对象>键值对

　　}

　　2.2.2 Reduce函数的设计

　　首先，将拥有相同聚类ID的数据对象分配给同一个Reduce任务；接着，Reduce函数将记录所接收到的样本个数并将数据对象各个维坐标分别累加；最后，将各维坐标之和除以样本个数得到各个维坐标的均值，计算结果就是该类新的聚类中心。Reduce函数的伪代码如下：

　　void reduce（IntWritable key，Iterable<Text>value，Context context）{

　　int colnum=value.get（0）.size（）；//数据对象的属性个数

　　for（int i=0；i<colnum；i++）{

　　double sum=0；

　　int rownum=value.size（）；//获取数据对象的个数

　　for（int j=0；j<rownum；j++）{//计算每列的平均值

　　sum+=value.get（j）.get（i）；

　　}

　　avg[i] = sum/rownum；

　　}

　　context.write（key，avg）；

　　//输出<聚类ID，聚类中心>键值对

　　}

　　将本轮reduce函数输出的聚类中心与上一轮的聚类中心比较，若目标函数收敛，则算法结束；否则，本轮的聚类中心将写入中心文件，作为新的聚类中心。

3 实验与分析

　　实验目的是比较在相同的硬件配置下，Hadoop集群中1个运算节点和普通计算机分别使用并行K-means算法和传统串行K-means处理相同规模数据的能力。考虑到K-means算法对初始聚类中心有较强的依赖性，在相同数据集的条件下重复进行实验10次，取平均值作为最终的实验数据，实验结果如表1所示。

　　表1中，t1表示使用传统串行K-means算法处理数据集所花的时间；t2表示使用并行化K-means算法处理数据集所花的时间。通过实验数据可以发现，当数据集的规模较小时，串行K-means算法的执行效率优于并行化K-means算法的执行效率，这是由于数据量小时，其计算任务所消耗的资源较少，但是在Hadoop平台上启动、分配任务以及进行作业间的交互却需要耗费固定的资源。但随着数据集规模的增大，计算任务所占用的资源的比例将不断增大，使并行化算法的优势得以体现，其运行时间的增长速度远小于串行算法。另外，由于串行算法所消耗的资源快速地增长，系统将会报告内存不足。

4 结论

　　本文对Hadoop的MapReduce编程模型以及聚类算法K-means进行了研究，给出了基于MapReduce的并行化K-means算法的设计方案并进行了实验验证。实验结果表明，基于MapReduce的并行化K-means算法适用于处理较大规模的数据挖掘任务，并且具有较好的计算效率。

　　参考文献

　　[1] 谢雪莲，李兰友.基于云计算的并行K-means聚类算法研究[J].计算机测量与控制，2014，22（5）：1510-1512.

　　[2] 冀素琴，石洪波.基于MapReduce的K-means聚类集成[J].计算机工程，2013，39（9）：84-87.

　　[3] 周婷，张君瑛，罗成.基于Hadoop的K-means聚类算法的实现[J].计算机技术与发展，2013，23（7）：18-21.

　　[4] 赵卫中，马慧芳，傅燕翔，等.基于云计算平台Hadoop的并行K-means聚类算法设计研究[J].计算机科学与探索，2011，38（10）：166-168，176.