一种基于MapReduce的改进k-means聚类算法研究

郭晨晨，朱红康

（山西师范大学 数学与计算机科学学院，山西 临汾 041000）

一种基于MapReduce的改进k-means聚类算法研究

郭晨晨，朱红康

（山西师范大学 数学与计算机科学学院，山西 临汾 041000）

传统k-means算法的聚类中心需要经过多次迭代运算才能最终稳定，而MapReduce计算框架下的k-means聚类算法在处理迭代运算时效率并不理想．针对上述问题，提出一种新的基于MapReduce的k-means聚类算法．该算法对传统k-means算法进行了改进，通过将k-means聚类问题转化为Map和Reduce两阶段的k-means++算法聚类问题，并将权值概念和单通道技术引入到传统k-means++算法中，提升了算法在MapReduce框架中的执行效率．实验分析表明，该方法较之传统方法具有更好的加速比和可扩展性．

k-means；MapReduce；两阶段；单通道；并行化；加速比

在数据挖掘中，聚类是重要的数据分析方法之一，它是在大量模式、样本点以及对象中发现自然分组的过程．在统计学、模式识别、信息检索、机器学习等广泛的领域都扮演着重要的角色．

然而，由于大数据体量巨大、元素复杂，传统的统计工具和管理系统已经很难适应．一方面，数据集主要存储于主存储器中，海量的数据规模造成主存储器无法容纳．另一方面，一些经典聚类算法，其时间复杂度并不是线性的．如果聚类目标规模过大，必然造成时间消耗超出可容忍的范围．为解决上述矛盾，需要建立新的编程模式和处理模型．MapReduce是目前公认的比较成熟的分布式编程模型．基于其简单的编程范式、线性架构和自动的可扩展性等特点使之成为大数据处理的理想工具．k-means及其改进算法的时间复杂度是线性的，因此可以内置于MapReduce中．但k-means算法在MapReduce中的实际运行存在明显不足，一方面，来源于k-means算法自身的缺陷，即需要预先估计类的数量，高度依赖初始样本点的选取，迭代次数无法估计，缺乏收敛性的保证等；另一方面，来源于MapReduce框架自身的局限性．k-means算法是一个迭代算法，为了得到相对理想的聚类结果，迭代可能需进行多次．而MapReduce本身不支持迭代和递归，需要驱动扩展程序辅助完成运算．该扩展程序通过重复执行算法操作来模拟迭代过程，并且每次迭代过程，整个待处理的数据集都需要加载到内存中，且输出结果需要写入到文件系统中去．这样MapReduce框架中的迭代过程常常伴随着大量的I/O及数据的序列化工作，导致整个系统进程被拖慢．

k-means是最经典的聚类算法之一，改进版本众多．其中包括针对k-means算法运行效率不高提出的并行k-means算法[1-3]，Zhao等提出的一种基于MapReduce的k-means聚类的解决方案[4]．针对k-means算法对初始点选取的依赖性，Bahmani等提出的一种可扩展的k-means算法[5]．另外，还有建立于GraphLab并行框架之上分布式k-means++算法[6]．然而，以上方法在解决迭代问题时都是以整个数据集为迭代对象，因而并不适合MapReduce框架．Hadian等提出一种并行化和单通道技术结合的技术用以解决并行共享存储器的问题[7]，但并没有以MapReduce为框架．目前，也存在一些MapReduce的扩展框架，如Spark[8]、Tw ister[9]、Haloop[10]等．它们都提供了处理迭代和递归问题的能力，k-means算法也能够在这些扩展框架中执行．但这些框架对数据集的规模有严格的限定，并不适合海量数据的处理．

基于此，提出一种MapReduce框架上的k-means改进算法，称为msk-means算法．该算法主要解决了迭代次数作为乘数导致的时间复杂度和空间复杂度的激增，使得系统运行效率大大提升．

1 准备工作

1.1 传统k-means算法

若一个样本集包含n个样本点，d种属性，那么该样本集可以表示为矩阵Mn×d．mi,j表示矩阵M中i行j列的元素．第i行的元素可以表示为向量mi．假定C=C1,C2,……Ck为样本集的一个划分，那么产生的若干个聚类应该满足以下2个条件：

则k-means算法可以简化表示为下面的步骤：

2）将每个点分配到距离初始中心点最近的簇中，并更新中心点；

2个样本间的相似性度量用下面的公式计算：

1.2 k-means++算法

k-means++算法[11]是k-means算法的一个非常重要的改进算法．它主要解决了k-means算法中存在的2大缺陷，即需要预先规定样本集中类的数量和初始种子样本点的随机选取．

k-means++算法可简化为下面的步骤：

1）从输入的数据点集合中随机选择一个点Ci作为第1个聚类中心．

2）对于数据集中的每一个点mi，计算它与最近聚类中心（指已选择的聚类中心）的距离D mi．

4）重复步骤2）和3）直到k个聚类中心被选出来．

5）利用这k个初始的聚类中心来运行标准的k-means算法．

这里定义的另一个属性是聚类中心，它是一个聚类的最佳代表．计算方法由下面的式子给出：

1.3 单通道技术

单通道技术即引用“分而治之”的聚类处理方法[14]．对于k-means聚类问题，设n个点组成的点集，并且存在1个权值函数w:．聚类问题可转化为最小化函数，其中D x,C表示点x到其最近聚类C中点的距离．C=k表示子集数量．

定义1 给定一个关于 k-means的算法A，令 c表示符合样本集的函数（从若干输入样本估计得到），表示符合样本的最优函数．则竞争比定义为最坏情况下的比率，则算法A称为b逼近算法．

定义2 算法B为b逼近算法算法，若输入样本包含ak个聚类中心，且满足a＞1，b＞1，则该算法可称为a,b 逼近算法．

为了之后说明的简化，假设样本空间Rd中的任意一点所占内存为O 1．单通道技术“分而治之”的思想如下：

2 msk-means

2.1 msk-means算法描述

本节主要对msk-means进行详细描述．该方法的基本思路：将一定规模的数据集分割成Chunk，分别存储在每台计算机的主存储器中．然后进行2阶段的工作：Map阶段，每台计算机对分得的数据块运用k-means++算法进行初始阶段的聚类，提取出包含少量聚类中心的数据集，称为中间集；Reduce阶段，将每台计算机产生的中间集通过重组技术形成1个较大的中间集并保存到1台未使用的计算机上，再次使用k-means++算法，对重组后的中间集进行聚类，得到最后的聚类中心．在2阶段，都使用k-means++算法，用于每个Chunk的中间集的提取．如果有c个数据块，每块产生k个聚类中心，那么将产生一组k c的中间集．但实际情况比较复杂，每个Chunk中的每个聚类中心都是由不同数量的样本点产生的，样本点的数量多少反映出该聚类中心的重要性的差异．因此，对于Map阶段产生的中间集中的元素不能统一对待，需要在传统的k-means++算法中引入权值概念，Map阶段在产生若干聚类中心的同时，相应地产生相同数量的权值，以表示每个聚类中心对于整个数据集的影响力，思想来源于文献 [13]．msk-means算法中关于聚类中心的计算和k-means++算法中的概率公式在文献 [13]所提算法的基础上进行了一定的改动，若W mi表示mi的权值，则中心点的计算公式如式 (3)

那么，k-means++算法中的选取概率公式可得

msk-means算法如下．

Map阶段：

2）对于B中的每一个Bi，生成1个Map任务并执行k-means++算法，得到1组包含k个加权中心的输出结果．

Reduce阶段：

1）将Map阶段产生的输出结果作为Reduce阶段的输入．

2）再一次执行k-means++算法得到包含k个中心的最终结果．

2.2 msk-means的竞争比

令M表示测试样本集，B为Chunk集，Ti表示由Bi中提取的一系列聚类中心点集，为msk-means产生的最终中心点集，产生X中到样本p的最近样本，表示Chunk Bi中分配tj个中心点．对msk-means算法进行如下推导

利用三角不等式定理

现在，只需要“+”前后的2部分分别推导即可．

假设Chunk Bi分配的最优聚类中心集为，可得

第2部分：

综合2部分可得，msk-means算法是O log2k逼近算法．

2.3 msk-means聚类质量的度量指标

本文采用SSE（Sum of Squared Errors）评估函数，该函数显示出聚类的紧凑程度，并且紧凑程度与函数值大小成反相关，即函数值越小，聚类越紧凑，效果越好．评估函数定义如下．

其中cj表示C中的任意聚类中心．

得到评估函数标准形式

2.4 Chunk大小的调整

msk-means算法的输入除了数据集还需要2个输入参数，一个是聚类数量k，一个是Chunk大小c．理论上ck,n，n表示数据集样本数．区间两边的值实际均无法取到．实验证明最有效的内存块为，因为较小的Chunk表示可以从数据集中提取较多的中间集元素，有利于聚类结果更符合原始数据集的规则．因此，Chunk设定的大小原则：通常情况下设置为，如果数据集规模较小或者较大的中间集不适合硬件环境，那么可以将Chunk调整为更小的值，如log n或10k等．

2.5 复杂度分析

通常，衡量聚类算法效率主要有3个量度：时间复杂度、I/O复杂度、空间复杂度．由于msk-means包含2阶段的任务，因而在衡量算法复杂度时，也必须分为2个阶段分别考虑．

若k表示聚类数量，n表示数据集中样本数量，c表示Chunk的大小，p表示Chunk的并行数，I表示迭代次数．设定单个样本处理的时间复杂度为O I，包括样本的计算和存储．由于整个数据集仅从存储器中读取1次，因此I=1．则Map阶段的I/O复杂度为O n/p，Reduce阶段的空间复杂度O k n/c．如果， msk-means算法的I/O复杂度为．

msk-means的空间复杂度主要受Chunk大小c和并行数量p共同影响．Map阶段要保证大小为c的Chunk以p并行，则产生的空间复杂度为O c p．Reduce阶段，为了存储Map阶段产生的中间集，需要产生O k n/c的空间复杂度．因此msk-means的空间复杂度为O p c+k n/c．最优情况是，当，空间复杂度表示为．

由于msk-means算法“单遍”的特点，因此在I/O复杂度方面是最优的．以下主要讨论该算法在时间复杂度和空间复杂度上的优势．

为了更好的比较，选取几种有影响力算法进行对比．包括可测k-means++算法[5]，即k-means‖算法以及流式k-means逼近算法[12]，即SKMA算法．以及并行k-means算法和并行k-means++，如表1所示．

表1 msk-means与其他算法的复杂度对比Tab.1 Contrast between msk-means and other algorithms

由表1所示结果可得，msk-means比SKMA算法时间效率上快log k倍，k-means‖算法虽然具有迭代性，但如果聚类数量较大，并且最大迭代数目设置较低（即k的值较大，I的值较低），那么相比SKMA算法来说效率更高．对于msk-means与k-means‖的比较相对复杂．假设k-means‖的时间效率更好，那么可以用下面的式子表示

但实际的MapReduce环境中，处理器的数量p不过是几千这样的数量级，而聚类的数量k显然远远小于数据集中样本的数量n．因此，在MapReduce运行环境中上述不等式是不成立的，即msk-means的时间效率要优于k-means‖算法．

本文所提方法的待改进的方面是较为宽松的误差逼近边界，最优结果相比其他算法效率要低一些，但这并不是实际情况的反映，是理论上存在的理想情况．

3 实验和结果分析

3.1 实验环境

本文采用的分布式实验框架是由40台计算机组成的私有云．每台计算机操作系统为Ubuntu Linux 12.04，CPU为双核2.4GHz Xeon处理器，内存为12GB．实验所用的主要软件包括ApacheHadoop1.2，OpenJDK等．

3.2 单机处理比较实验

本节通过在单机上运行msk-means算法和其他算法来展示不同算法在Hadoop集群中的1个计算节点上的性能对比．使用单机是由于大多数UCI数据集规模并不大，单机的处理能力可以完成．在单机实验使用真实世界的数据集，从时间效率和聚类质量（SSE）2方面衡量几种算法的性能．文献 [5，12]表明在处理小规模数据集时k-means‖与SKMA比k-means++的性能要弱，因此，本实验并没有将其加入对比．在实验中分别设置每个数据集的聚类数量k为10、50、100，birth数据集由于其自身的聚类数量是100，因而没有考虑其他情况．实验数据采用国际公认的UCI数据集，详情如表2所示．

表2 实验数据集汇总表Tab.2 Summary of experimental data sets

实验1结果如表3所示．

表3 msk-means与其他算法单机环境的性能对比实验Tab.3 Performance comparison of single machine environment with msk-means and other algorithms

从表3可知，msk-means在聚类质量上基本与k-means算法持平，略低于k-means++算法．虽然本次实验实在单机上完成的，但msk-means算法执行效率很高，特别在规模较大的数据集中体现的尤为明显．

3.3 集群加速比性能实验

加速比是衡量系统可扩展性优劣的可靠指标，本节所做的集群加速比性能实验主要考察算法2个方面的性能，实验1是测试当Hadoop集群中的计算节点增加，处理相同规模数据时，系统运行速度是如何提升的．实验2是在40个计算节点满负荷运行时，随着待处理数据集的增加，运行时间相应的变化．由于需要的数据量巨大，本实验采用实验室开发的聚类数据生成器生成的40GB人工数据集进行实验。该数据集从5维边长为500的超立方体中生成，要求生成50个类别，加入的数据点服从标准差为10的高斯分布，初始聚类中心随机产生．

实验1首先选择1个计算节点参与计算，并分别选择2、4、8、16、24、32、40个节点参与计算．考察在逐渐增加计算节点的情况下，分布式系统中完成任务所用的时间，实验结果如图1所示．从图中可以看出：随着计算节点的线性增加，系统运行速度与单机运行速度相比呈现线性变化．如图1所示．

图1 加速比与计算节点数量的关系Fig.1 The relationship between speedup and calculation of the number of nodes

实验2人工生成6个数据集，分别包含10、20、40、60、80、100亿条数据．分别将它们加入系统参与计算，实验结果表明随着待处理数据规模的增加，运行时间的增速亦在可接受的范围，表现出msk-means良好的可扩展性．如图2所示．

图2 数据集大小与运行时间的关系Fig.2 The relationship between the size of dataset and running time

3.4 Chunk大小对算法精度的影响实验

在MapReduce分布式框架中，Chunk大小对结果有一定的影响，本节实验通过调整Chunk大小展示对msk-means算法聚类精度的影响．实验数据采用了USCensus和KDD04数据集进行实验，将Chunk大小从k log n到取值若干，实验结果如表4所示．

表4 Chunk大小对实验结果的影响Tab.4 The effect of chunk size on quality of results

从表4可得，对于USCensus数据集，chunk大小对实验结果的影响很小，但对于KDD04数据集影响很大．特别地，当簇数为10时，随着chunk逐渐增大，聚类质量显著下降．原因在于KDD04数据集规模较小，而chunk大小较大时，中间集会相对较小，不能充分代表原始数据集．而簇数为50和100的测试显示，chunk大小对实验结果影响较小，因为这时的中间集为k n/c，较大的k使得中间集可以很好的代表原始数据集．因此，可以得到这样的结论：当数据集规模巨大，选择为chunk大小更为合理．

3.5 Mahout框架下的对比实验

Apache Mahout是当下十分流行的机器学习与数据挖掘的开源框架，本节旨在通过Mahout框架下完成算法运行效率的比较试验，进一步说明 msk-means算法的优越性．实验数据采用了同3.3节人工合成数据集．实验结果如表5所示．

表5 Mahout框架的聚类质量与效率的比较实验Tab.5 Comparison of quality and efficiency under Mahout

从表5可知，msk-means算法在聚类质量和时间效率方面都有很大的提高．

4 结论

本文提出一种基于MapReduce的改进k-means聚类算法msk-means，该算法利用单通道思想优化迭代算法的执行过程，并引入基于权的k-means算法相关内容，突出了不同聚类中心对于整体数据集影响力的差异性．搭建Hadoop云计算平台，分别进行了单计算节点和多计算节点的模拟实验，并且为了更好的说明算法的可行性，在Mahout框架下进行性能比较实验．结果表明，msk-means算法在MapReduce并行化后部署在Hadoop集群上运行，具有良好的加速比和可扩展性，在信息量激增、传统统计工具失效的背景下，所做工作具有一定的现实意义．

[1]Nickolls J，Buck I，Garland M，et al．Scalable parallel programming with cuda[J]．ACM Queue，2008，6（2）：40-53．

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

[3]江小平，李成华，向文，等．k-means聚类算法的MapReduce并行化实现 [J]．华中科技大学学报（自然科学版），2011，39（S1）：120-124．

[4]Zhao Wei-zhong，Ma Hui-fang，He Qing．Parallel k-means clustering based on MapReduce[M]．Germany：Springer Berlin Heidelberg，2009：674-679．

[5]Bahmani B，Moseley B，Vattani A，et al．Scalable k-means++[J]．Proceedings of the Vldb Endowment，2012，5（7）：622-633．

[6]Low Y，Bickson D，Gonzalez J，et al．Distributed graphlab：a framework for machine learning and data mining in the cloud[J]．Proceedings of the Vldb Endowment，2012，5（8）：716-727．

[7]Hadian A，Shahrivari S．High performance parallel k-means clustering for disk-resident datasets on multi-core CPUs[J]．Journal of Supercomputing，2014，69（2）：845-863．

[8]Zaharia M，Chowdhury M，Senker S，et al．Spark：cluster computing with working sets[C]//Usenix Conference on Hot Topics in Cloud Computing，2010，15（1）：1765-1773．

[9]Ekanayake J，Li Hui，Gunarathne T，et al．Twister：a runtime for iterative MapReduce[C]//Acm International Symposium on High Performance Distributed Computing，2010：810-818．

[10]Lin Yi-an．Map-Reduce for machine learning on multicore[J]．Advances in Neural Information Processing Systems，2006，19（1）：281-288．

[11]Arthur D，Vassilvitskii S．K-means++：the advantages of careful Seeding[C]//The Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms Society for Industrial and Applied Mathematics，2007：1027-1035．

[12]Ailon N，Jaiswal R，Monteleoni C．Streaming k-means approximation[J]．Advances in Neural Information Processing Systems，2009：10-18．

[13]Kerdprasop K，Kerdprasop N，Sattayatham P．Lecture notes in computer science[M]．Germany：Springer Berlin Heidelberg，2005：488-497．

[14]Guha S，Meyerson A，Mishra N，et al．Clustering data streams：theory and practice[J]．IEEE Transactions on Knowledge and Data Engineering，2003，15（3）：515-528．

[责任编辑 田 丰 夏红梅]

An improved k-means clustering algorithm based on MapReduce

GUO Chenchen，ZHU Hongkang

(School of Mathematics and Computer Science,Shanxi Normal University,Shanxi Linfen 041000,China)

The clustering centers of the traditional K-means algorithm need many iterations to be stable,and the efficiency of the K-means clustering algorithm in the MapReduce computing framework is not ideal.In view of the above problems, a new K-means clustering algorithm based on MapReduce is proposed.This algorithm has improved the traditional K-means algorithm.By sing-pass method,the K-means clustering problem is transformed into Map and Reduce two stages of k-mean algorithm clustering problem.And the concept of the weights is introduced into the traditional k-means++algorithm,which improves the efficiency of the algorithm in the MapReduce framework.Experimental results show that the proposed method is better than the traditional method and has a better speedup and scalability.

k-means;MapReduce;two stages;single pass;parallelization;speedup

TP18

A

1007-2373(2016)05-0035-09

10.14081/j.cnki.hgdxb.2016.05.006

2016-09-27

山西省自然科学基金（2015011040）

郭晨晨（1992-）男（汉族），硕士生．通讯作者：朱红康（1975-），男（汉族），副教授，博士．