基于云计算平台的聚类算法

孟海东，任敬佩

（内蒙古科技大学 信息工程学院，内蒙古 包头014010）

0 引 言

目前，针对于大数据［1－3］的处理，多采用并行或分布式架构来提高系统的扩展性，并利用多线程的并行式结构，或者是基于Apache推出的开源云计算Hadoop［4，5］平台实现，其中K－means算法的应用最为广泛。文献 ［6］提出了基于MPI的分布式聚类，它虽然从某种程度上利用集中式存储提高了算法的时效性，但是，由于该算法在计算过程当中是单节点运行的，所以在处理大数据进行聚类分析任务时，该算法的效率还不够快；文献 ［7，8］提出了在Hadoop平台下，利用MapReduce 模型框架，实现了Kmeans［9－11］分布式聚类，提高了聚类算法的加速比；文献［12］利用Spark （Pregel和HaLoop［13］）模型框架，实现了迭代式的分布式聚类，提高算法的可扩展性；文献 ［14］中为了进一步提高聚类算法的效率，解决初始中心点的随机性和盲目性，在该算法在基于MapReduce分布式框架的聚类中，加入了Canopy算法对原数据的预处理，初步的解决了该算法选取初始中心点的随机性与初始确定聚类个数的问题；文献 ［15］中提出基于MapReduce 的Canopy－Kmeans改进算法，针对于Canopy算法的缺点采用了 “最小最大原则”，利用云计算平台的集群计算和存储能力，更进一步提高该算法的时效性和有效性。

鉴于以上改进后的K－means聚类算法的优点，利用文献 ［16］在K－means算法引进了三角不等式原理的基础上，提出一种改进的BRTI－K－means（MapReduce based triangle inequality Canopy K－means，BRTI－K－means）算法。主要通过基于开源云计算平台，利用MapReduce分布式框架，融合了距离三角不等式定理，同时在大数据的预处理过程当中，使用Canopy算法对原始的大数据进行了预处理，进一步实现了K－means算法在聚类分析过程中的改进；为了进一步验证BRTI－K－means算法的优越性，将该算法与Kmeans和Canopy－Kmeans算法进行了算法比较。

1 BRTI－K－means算法

1.1 基于距离三角不等式聚类算法

基于云计算平台下的MapReduce框架下，利用传统的K－means算法与距离三角不等式定理相结合，提出了基于距离三角不等式聚类算法。该算法利用三角不等式定理：任一个三角形两边和大于第三边，两边之差小于第三边；将其扩展到欧几里得空间，由于欧式距离满足三角不等式原理，进一步减少了聚类算法的计算复杂度，提高了大数据的聚类分析效率。

假设在欧几里得空间内有任意3个数据点X、C1、C2，数据点间距离满足三角不等式原理：d（X，C1）＋d（C1，C2）＞＝d（X，C2），d（C1，C2）－d（X，C1）＜＝d（X，C2）；若X 为数据空间中任意一个数据点，C1和C2为两个簇中心点。如果2＊d（X，C1）＜＝d（C1，C2），同时在两边减去d（X，C1），则有：2＊d（X，C1）－d（X，C1）＜＝d（C1，C2）－d（X，C1），即有d（X，C1）＜＝d（C1，C2）－d（X，C1）；由于d（C1，C2）－d（X，C1）＜＝d（X，C2），因此，d（X，C1）＜d（X，C2）；所以，如果2＊d（X，C1）＜＝d（C1，C2），则d（X，C1）＜d（X，C2），即数据点X 属于簇中心点C1。

根据上述原理，BRTI－K－means算法的设计思想为：利用预处理过后的初始中心点，计算各个中心点彼此最短距离；然后，根据三角不等式原理，计算集合中的每个数据点到第一个数据中心点之间的距离。如果数据点到中心点之间的距离的2倍小于或等于第一个数据中心点到其它数据中心点的最短距离，那么，这个数据点就属于第一个数据中心点，标记为第一类，同时从数据集中删除数据这个数据点；根据上述的步骤，依次类推，对集合中的数据点进行标记，同时从数据集中删除标记过的数据点，直到没有符合条件的数据点为止；如果集合中还存在不符合条件的数据点，则根据上述过程中已经求得的不符合条件的数据点到每个中心点距离，把集合V 中没有被标记的数据点，根据欧氏距离分配到相应的簇。当集合中所有数据点都被标识后，更新新的中心点与初始中心点相比较，如果前后变化在一定阈值内或者不变，即达到一种稳定分类状态，则聚类完成。

基于MapReduce框架，BRTI－K－means可以分解为以下几步，具体流程如图1所示，其中每个方框内的过程都是一个独立的过程。

1.2 BRTI－K－means算法设计

BRTI－K－means算法执行过程如下：

（1）将数据集上传到HDFS，数据分片，并将每一分片存储到若干台DataNodes，输入初始中心点的集合U （作为全局变量）；

（2）在每个计算节点，计算每个中心点到其它中心点的最短距离D 集合；

（3）根据距离三角不等式原理，将满足条件的数据点划分到各个中心点所在的簇，同时把已划分的数据点从数据集V 中删除；如果在数据集V 中还有不符合条件的数据点，则根据已经计算得到的数据点到各个中心点的距离分配给相应的簇，并把相应的数据点从V 中删除；

图1 BRTI－K－means算法实现流程

（4）生成新的中心点；

（5）返回到 （2）重新计算数据中心点，直到数据中心点不在发生变化为止，算法结束；

（6）实现子节点的归约，输出聚类结果。

具体实现BRTI－K－means算法的伪代码如下：

Setup函数

输入：初始簇中心点的集合U＝ ｛C，C’｝，K 值；

（1）对所有的中心点C 和C’，计算d（C，C’）；对所有的中心点C，S（C）＝min（d（C，C’））（C≠C’）；

（2）计算所有中心点C 和C’，求出彼此最短距离并保存到相应的数组中；

（3）如果中心点发生改变，则重复步骤 （1）与 （2）。

Map函数

输入：簇中心点的集合U，数据集V（v1，v2，…，vn）；

输出：K 中心点集合U’；

（1）U’＝U；

（2）While（true）

（3）计算出V 中数据点到中心点C 的距离d1；

（4）If（2＊d1＜＝S）标记数据点属于第一个中心点的簇；同时从V 中删除这个数据点，并保存不符合条件的数据点到该中心点的距离到数组D；依次类推，直到计算出V 中所有点的聚类，并标记出其所属簇；

（5）End If

（6）If（V！＝Null）

（7）根据上述中心点的距离D，计算到C 的最短距离，选取到中心点最近的簇，并进行标记，同时从V 中删除该数据点；

（8）End If

（9）计算已被标记点所属簇的新的C；

（10）对比上一个中心与新中心点之间的距离 （Distance＝＝0）；

（11）If（Distance＝＝0）

（12）Break

（13）Else

（14）返回 （3）重新计算；

（15）End while

Combine函数

为了减少大数据在主节点与子节点之间的通讯时间，该算法在Map函数之后设计了一个Combine操作；它的主要功能为：对于本地节点的数据文件进行合并，减少大数据的I／O 传输。

输入：V 中数据点所属簇下标 （Key），Key对应键值对列表；

输出：V 中数据点所属簇下标 （Key），各个簇内被标记数据点的各维累加值，以及Key对应键值对列表；

（1）定义一个列表，用于存储各个簇内被标记数据点的各维累加值；

（2）初始化一个变量Num＝0，记录所属簇内点的个数；

（3）While（V.hasNext（））

（4）在V.next（）中，解析出各维坐标值；

（5）计算上步过程中各维累加值和，并存储到定义的列表当中；

（6）Num＋＋；

（7）End While

Reduce函数设计

输入：V 中数据点所属簇下标 （Key），Key对应的键值对列表；

输出：V 中数据点所属簇下标 （Key），以及新的中心点；

（1）定义一个列表，保存所属簇的各维累加值；

（2）初始化一个变量NUM＝0，记录所属簇内标记点的个数；

（3）While（V.hasNext（））

（4）在V.next（）中，解析出坐标值，计算出样本个数Num；

（5）计算上步解析出v 的各维坐标值的累加和，并存储到相应的列表中；

（6）NUM＋＝Num；

（7）End While

（8）将数组的分量除以NUM；得到新的中心点坐标。

根据上述规约得到的聚类结果，得到新的中心点，更新HDFS中的中心文件，利用Setup 函数，进行初始化，进行下一轮Job，直到算法收敛。

2 BRTI－K－means实验结果分析

2.1 实验平台、测试数据集和评价指标

本文所有实验环境搭建的平台的组成为：2 台2GHZ Inter Xeon CPU、2G 内存和4台2GHZ Inter Xeon CPU、1G 内存的PC 构成的，操作系统均为Ubuntu Linux 10.10，Hadoop版本选用1.1.2；Java开发包为JDK1.7版本，程序开发工具为Eclipse－standard－kepler－SR1－linux，算法使用Java实现。

实验数据集采用了UCI数据集下Synthetic＿Control，分别构造了100 M，200 M，300 M，400 M，500 M，1G的60维不同大小的数据集来验证算法的时效性；同时，为了验证算法的有效性，利用了Wine（数据对象178，属性13）数据集，Iris数据集 （数据对象150，属性4），Libras数据集 （数据对象360，属性90）进行了实验。同时，利用节点个数的不同验证了算法的扩展性的效率。

在实验中，为了测试BRTI－K－means算法的性能，本文采用了以下评价指标：加速比 （speedup）、时效性、数据伸缩率和有效性 （采用正确率 （正确的个数／总个数%）表达算法的有效性）。

2.2 实验结果

实验中，由于算法初始中心随机选择，因而对初始中心点进行了10次随机选择，同时进行了10 次运算，最终的结果利用10次实验结果的平均值来获得。

为了验证该算法的有效性，该算法采用了不同大小的数据集进行测试，同时获得了BRTI－K－means算法的加速比，实验结果如图2所示。

图2 BRTI－K－means算法加速比结果的测试

从图2可以发现，BRTI－K－means算法在处理少量数据时加速比的变化是接近线性的；然而，当数据集的规模越来越大时，该算法的加速比的变化会变大，效果越明显。其主要的原因是：①在主节点计算出了K 个中心彼此最短距离，并把结果作为全局变量分配到各个子节点；因而，随着数据集的增大，在主节点所耗费时间所占的比重越来越少；②在该算法中加入了Combine操作，减少了大数据的通讯代价，并且随着数据的增长，效果会更加明显；③由于该算法减少了每个数据点到中心点的计算次数，从而减少了算法的运行时间；因此，当数据规模越大时，算法加速比性能越好，适合用于大数据的聚类分析研究。

为了进一步证明BRTI－K－means算法的优越性，本文通过利用6 个有效节点，把不同的大小的数据集与Kmeans和Canopy－Kmeans聚类算法进行比较，实验结果如图3所示。

图3 3种算法时效性的对比

从图3可以看出，3种算法在不同大小的数据集上执行的时间是不同的，基于MapReduce的距离三角不等式Kmeans算法 （BRTI－K－means）在执行时间上有了明显的改善；同时可以看出，伴随着数据集的增长，BRTI－K－means算法更进一步提高了聚类算法的时效性。

图4 给出了BRTI－K－means算法数据伸缩率的测试结果。在实验中，分别测试了不同节点下不同大小数据集BRTI－K－means算法的运行时间。

从图4可以发现，算法的时效性不仅与数据集的大小有关，而且还与实验平台的数据节点密切相关；当数据节点较少时，时效性呈现出线性变化的特点；当随着数据节点的不断增多，算法的执行效率变化越快。

为了进一步验证算法的有效性，在实验中，使用平台下的3个节点，利用UCI数据集，针对于BRTI－K－means算法与K－means和Canopy－Kmeans算法的有效性进行了比较，实验结果如表1所示。

图4 BRTI－K－means算法的伸缩性

表1 不同算法对UCI数据集的测试结果

通过上述表1 的实验结果表明：Canopy－Kmeans算法与BRTI－K－means算法都从一定的程度上提高了K－means算法的有效性；其主要原因为：在预处理过程中都用Canopy算法对原始数据进行了预处理。

3 结束语

本文通过把距离三角不等式原理与K－means算法的性相结合，在基于云计算平台环境下针对于传统的K－means算法进行了改进，提出了一种改进BRTI－K－means算法，提高原算法的执行速度。实验结果表明：算法具有良好的时效性、加速比、伸缩性和有效性等性能，适合用于大数据的聚类分析。这些算法均以K－means算法为原型，具有K－means的特性，对于非等轴状分布、具有噪声或孤立点的数据对象分布，3 种聚类算法的有效性必然会降低。因此，对于K－means的改进需要在云计算平台下更进一步的研究。

［1］Anand Rajira Man，Jeffrey David Ullman.Mining of massive datasets［M］.WANG Bin，transl.Beijing：The People’s Posts and Telecommunicati Ons Press，2013：176－205 （in Chinese）.［Anand Rajira man，Jeffrey David Ullman.互联网大规模数据挖掘与分布式处理 ［M］.王斌，译.北京：人民出版社，2013：176－205.］

［2］BAO Xiaodi，ZHANG Fangfang.Reaserchon the key technologies of big data ［J］.Information Construction，2013 （10）：49－54 （in Chinese）.［鲍晓地，张芳芳.大数据处理的关键技术研究 ［J］.信息化建设，2013 （10）：49－54.］

［3］Ciprian Dobre，Fatos Xhafa.Parallel programming paradigms and frameworks in big data era ［J］.International Journal of Parallel Programming，2014，42 （5）：710－738.

［4］LIU Gang，HOU Bing，ZHAI Zhouwei.Open source cloud computing platform for Hadoop ［M］.Beijing：Beijing University of Post and Telecommunications Press，2011：35－72 （in Chinese）. ［刘刚，侯宾，翟周伟.Hadoop开源云计算平台［M］.北京：北京邮电大学出版社，2011：35－72.］

［5］Hadoop ［EB／OL］.http：／／hadoop.apache，2014.

［6］QIAN Yanjiang.Research and implementation on the technologies of mining of massive datasets［D］.Chengdu：University of Electronic Science and Technology of China，2009：27－55（in Chinese）. ［钱彦江.大规模数据聚类技术研究与实现［D］.成都：电子科技大学，2009：27－55.］

［7］QIU Rongtai.Research on Map－Reduce application based on Hadoop ［D］.Jiaozuo：Henan Polytechnic University，2009：17－32 （in Chinese）.［邱荣太.基于Hadoop平台的Map－Reduce应用研究 ［D］.焦作：河南理工大学，2009：17－32.］

［8］WEN Cheng.Parallel clustering algorithm based on MapRedcuce ［D］.Hangzhou：Zhjiang University，2011 （in Chinese）. ［温程.并行聚类算法在MapReduce上的实现 ［D］.杭州：浙江大学，2011.］

［9］ZHAO Weizhong，MA Huifang，FU Yanxiang.Research on parallel K－means algorithm design based on Hadoop platform ［J］.Computing Science，2011，38 （10）：166－178 （in Chinese）. ［赵卫中，马慧芳，傅燕翔.基于云计算平台的并行K－means聚类算法设计研究［J］.计算机科学，2011，38 （10）：166－178.］

［10］ZHOU Lijuan， WANG Hui， WANG Wenbo.Parallel Kmeans algorithm for massive data ［J］.Journal Huazhong University of Science and Technology （Natural Science Edition），2012 （S1）：150－152 （in Chinese）. ［周丽娟，王慧，王文伯.面向海量数据的并行K－means算法 ［J］.华中科技大学学报 （自然科学版），2012 （S1）：150－152.］

［11］Cui Xiaoli，Zhu Pingfei，Yang Xin，et al.Optimized big data K－means clustering using MapReduce［J］.The Journal of Supercomputing，2014，70 （3）：1249－1259.

［12］TANG Zhenkun.Based on the Spark machine learning platform design and implementation ［D］.Xiamen：Amoy University，2014 （in Chinese）.［唐振坤.基于Spark的机器学习平台设计与实现 ［D］.厦门：厦门大学，2014.］

［13］Bu Yingyi，Bill Howe，Magdalena Balazinska，et al.Ha－Loop：Efficient iterative data processing on large clusters［C］／／36th International Conference on Very Large Data Bases，2010：1－12.

［14］ZHAO Qing.Efficient algorithm of Canopy－K－means based on Hadoop platform ［J］.University of Electronic Science and Technology of China，2014，27 （2）：29－32 （in Chinese）.［赵庆.基于Hadoop 平台下的Canopy－K－means 高效算法［J］.电子科技大学，2014，27 （2）：29－32.］

［15］MAO Dianhui.Improved Canopy－Kmeans algorithm based on MapReduce ［J］.Computer Engineering and Applications，2012，48 （27）：22－26 （in Chinese）. ［毛典辉.基于MapReduce的Canopy－K－means改进算法 ［J］.计算机工程与应用，2012，48 （27）：22－26.］

［16］SHAN Yushuang，XING Changzheng.Amore effective Kmeans clustering algorithm ［J］.Computer Systems ＆ Applications，2009 （8）：96－99 （in Chinese）. ［单玉双，邢长征.一种更有效的K－means聚类算法 ［J］.计算机系统应用，2009 （8）：96－99.］