基于Hadoop平台Canopy-Kmeans聚类算法优化改进研究

周功建

(厦门大学 嘉庚学院，福建 漳州 363105)

一、引言

大数据时代，随着互联网和信息技术的快速发展，数据量呈指数式增长。如何快速准确地从海量数据里挖掘出有价值的知识和信息是数据挖掘技术最重要的特征，而聚类分析是数据挖掘中一个非常重要的研究领域[1]。传统的聚类分析算法在空间复杂度和时间复杂度上都有一定的局限性，利用云计算平台对其进行并行化改进优化，可以有效降低聚类算法的时间复杂度和空间复杂度，节约聚类时间，从而更好地满足实际问题中数据挖掘的需要[2]。

Hadoop是目前使用最广的云计算平台，利用其中的MapReduce模块来提高聚类算法的效率，已经成为大数据聚类分析研究的热点[3]。针对经典的基于划分的Kmeans聚类算法，人们根据不同的要求和使用环境，在传统Kmeans算法的基础上提出了许多改进思路，其中结合Canopy算法和Hadoop云平台改进生成的Canopy-Kmeans并行聚类算法及其优化就是很有代表性的一类。张石磊、武装等在Hadoop平台上实现了Kmeans和Canopy-Kmeans算法的并行化，并且验证了Canopy-Kmeans并行算法比Kmeans并行算法在不同的数据集下有更高的聚类准确率和更快的收敛速度[4]。李钊、王春梅等基于Hadoop平台设计了Canopy-Kmeans并行化算法，应用“最小最大原则”对Canopy中心点随机性选取问题进行改进，并用海量新闻数据做聚类测试验证改进算法的性能和有效性[5]。李兰英、董义明等采用“平均距离估值”方法对Canopy算法区域半径T1和T2取值具有盲目性问题进行改进，可以得到比较准确的区域半径取值，并在Hadoop云平台上对改进后的Canopy-Kmeans算法进行了实现和验证[6]。

在学习借鉴他人研究基础上，利用统计学思维对数据分组抽样后聚类，并结合数据异度均值抽样法和最小最大法原则对Canopy-Kmeans算法进行优化改进；并在Hadoop平台上对改进的Canopy-Kmeans算法进行并行化设计与实现；最后通过实验验证算法并行执行时的加速比和可扩展性。结果表明改进的Canopy-Kmeans并行算法是有效的、收敛的。

二、Hadoop云计算平台

Hadoop云平台是一个开源分布式系统框架，遵循了Google的Bigtable、GFS、MapReduce三大关键技术及其设计思想[2,7]；在Hadoop框架中，MapReduce和HDFS(Hadoop Distributed File System)是两个最核心模块，分别负责海量数据的存储与计算。HDFS是一种运行在大量普通配置的机器节点上的分布式文件系统[7]。MapReduce是Google提出的一种并行编程框架，用于对海量数据集的并行分析与运算，能够实现程序的自动并行处理，并提供数据分割、任务调度等细节，实现程序高度并行性和可扩展性[3,8]。

三、Canopy-Kmeans算法研究

(一) Kmeans算法原理

Kmeans算法是一种基于划分的聚类算法，利用数据对象间的距离作为相似性的评价指标[4，7]。聚类过程是一个不断循环迭代的过程，对数据点进行簇划分和对簇中心点进行调整交替执行，直到簇中心点不再发生变化为止，最后生成的同一簇内数据相似度高，不同簇间数据相似度低，其算法执行流程如图1所示。

图1 Kmeans算法聚类流程

Kmeans算法思想简单、理论可靠、处理大数据集时有较强的鲁棒性和可伸缩性，实际应用中得到广泛关注，但算法也存在如下不足之处：

(1)Kmeans算法的聚类簇数量k值需人为指定，不同的k值对聚类结果会产生很大影响；并且每个簇的初始中心点是随机选取的，易导致聚类结果不稳定和聚类质量不高[9]。如何准确确定k值和选择初始中心点是使用Kmeans算法聚类时需思考的优化改进方向。

(2)串行执行时，当聚类数据量为n，聚类簇个数为k，迭代次数为t时，算法的时间复杂度为O(nkt)；可以看出当聚类的数据集较大时，算法的运行时间将大大增加，如果能将聚类过程改为并行化执行，则可有效降低时间复杂度，提升聚类效率[4,8]。

(二)Canopy-Kmeans算法原理

Canopy-Kmeans算法是一种借助Canopy算法进行改进优化后的Kmeans算法，在Canopy-Kmeans算法中，先用Canopy算法对数据集进行“粗”聚类预处理，快速算出k个Canopy中心点，再用Kmeans算法对数据集进行 “细”聚类，生成聚类结果[5,9]。Canopy-Kmeans算法执行步骤如下：

(1) 将待聚类的数据集向量化为一个List集合，并指定两个距离阈值T2和T1(T2

(2)从集合List中随机删除一个数据对象P，构成一个新的Canopy;

(3)对于List中剩余数据对象，如果与P的间距小于T1，就把它指派到P所在的Canopy中; 如果与点P的间距小于T2，则将它从List中删除;

(4)重复步骤(2)和步骤(3)，直到List为空，至此将形成多个Canopy;

(5)将得到的Canopy数目作为k值，每个Canopy的中心点作为初始聚类中心点代入Kmeans算法中进行再次聚类，生成最终聚类结果。

图2 Canopy聚类结果示意图

在Canopy-Kmeans算法中，无须事先指定k值和随机选取初始中心点，而是利用Canopy算法聚类求得，可有效解决k值人为指定和随机选取初始中心点的盲目性；但Canopy-Kmeans算法仍有以下不足之处：

(1)Canopy算法在求解过程中各个Canopy的初始中心点仍然是随机选取的，这种做法可能会造成聚类结果的不稳定[1,5]；

(2)串行执行时，Canopy-Kmeans算法的时间复杂度为O(nktf2/c)，其中c为Canopy的总个数，n为数据的规模，t为算法迭代的次数，k为最终生成的聚类数目，f为平均每个数据对应的Canopy数量[8]；可以看出，在处理海量数据时，仍然有较高的时间复杂度[2,6]。

四、改进的Canopy-kmeans算法

通过对Canopy算法聚类过程、Kmeans算法迭代过程及时间复杂度等方面分别进行优化，改进的Canopy-Kmeans算法执行流程如图3所示。

图3 改进的Canopy-Kmeans算法执行流程

(一) Canopy聚类过程优化

为避免聚类陷入局部最优解，针对Canopy聚类时初始中心点选取随机性问题，利用“最小最大原则”对Canopy算法进行优化，基本思想为:在将数据聚类划分为若干个Canopy过程中，任意两个Canopy中心点之间的距离应尽可能远；即如果已知m个Canopy中心点，则第m+1个Canopy初始中心点应为所有候选数据对象与前m个Canopy中心点之间最小距离中的最大者[6]。具体优化流程如下：

(1)从数据集List中随机删去第一个点P1，计算与其对应的Canopy；

(2) 计算List中剩余的点到点P1的距离，选取其中距离最大的点P2作为第二个Canopy的初始中心点，并从List中删除点P2，计算与其对应的Canopy；

(3)计算List中剩余的点到所有已生成Canopy中心点最小距离d，选取d的数值最大的点作为下一个Canopy的初始中心点，计算与其对应的Canopy；

(4)重复执行步骤(3)，直到数据集List为空。

另外，为了提高下一步Kmeans聚类的稳定性和准确率，还需检测每个Canopy簇中数据对象的个数，若一个Canopy簇只有一个或很少的数据对象，则认为该Canopy簇是孤立的，应将他们从总的Canopy簇中减掉，从而得到Kmeans聚类过程的K值和初始聚类中心。

(二) kmeans迭代过程优化

Canopy算法作为Kmeans聚类的初始化操作，在快速得到k个Canopy中心时，会对每个Canopy中的数据对象进行标注，每个数据对象至少属于一个Canopy，也可能出现在多个Canopy中。可以断定数据在同一Canopy中相似度高，不同Canopy中相似度低，因此在Kmeans迭代时，不属于同一个Canopy中的数据之间可不再计算它们的相似性。当计算数据所属聚类簇时，只需计算它到所属Canopy中心点的距离，并将其归入到距离最近的Canopy中心点所属类簇中，形成相不重叠的簇，从而减少了迭代过程中的计算量。在Canopy较小，且相互间数据重叠不多的情况下可有效降低Canopy-Kmeans算法的时间复杂度。

(三)时间复杂度优化

为进一步降低算法的整体时间复杂度，利用统计学思维对数据集进行分组抽样后聚类，以增强其时效性。具体思路为：先将待聚类数据集进行分组，从每组抽样出一定量的数据，并对各组抽样数据分别进行Canopy聚类，然后对求得的全部Canopy中心点再次进行Canopy聚类，生成k个Canopy中心点，代入Kmeans算法中对全部抽样数据进行聚类划分，产生新的Kmeans聚类簇，最后将所有未被抽样到的数据对象归类到距离最近的Kmeans聚类簇中。

分组的目的是为了更方便在Hadoop平台上进行并行化实现。在对数据抽样时，利用数据异度均值抽样方法来确保数据样本尽量均匀分布在原始数据中，使其能够代表全体数据，从而保证算法的稳定性和正确性。数据异度均值抽样操作步骤如下：

(1)对于非空数据集S={ci|ci=

(ci1,ci2,…,cip),i=1,2,…n},用公式(1)找出集合S中最小数据对象cm=(cm1,cm2,…,cmp),1≤m≤n;

(1)

(2)用公式(2)计算所有其余数据对象到cm的距离，形成一个距离值集合DIS；

(2)

(3)根据DIS中的距离值，按从小到大的顺序对集合S中的全部数据对象进行升序排序；

(4)利用公式(3)从排好序的集合S中均匀地选取t个数据对象作为抽样数据集RIS={c1,c2,…,ct}。

,(i=1,2,…,t)。

(3)

五、基于Hadoop平台Canopy-kmeans改进算法的并行化设计实现

在改进的Canopy-Kmeans算法中，因对数据集采取了分组抽样策略，所有数据对象到各Canopy质心点距离的计算操作都可以独立执行，相互之间不存在任何依赖关系，因此改进算法完全可以应用Hadoop平台上的Map-Reduce编程框架进行并行化设计实现，将执行过程分成三个阶段，具体流程如图4所示：

图4 基于Hadoop平台改进Canopy-Kmeans算法并行化执行流程

(一) Canopy聚类阶段

1.Map过程

从分组数据集split中采用数据异度均值抽样方法抽取t个数据对象，然后对抽取的数据对象利用Canopy算法聚类，得到多个重叠的Canopy，输出Canopy中心点集合。

图5 Map函数执行伪代码

2.Reduce过程

使用改进的Canopy算法将Map过程中得到的多组Canopy中心点合并为一组，再将所有抽样的数据对象划分到距离最近的Canopy中，并重新计算各个Canopy的中心点，将结果保存至HDFS中。

图6 Reduce函数执行伪代码

(二)Kmeans聚类阶段

Kmeans算法每一轮迭代都启动一次Map-Reduce任务，算法所需的k值及初始聚类中心由Canopy算法得到，因Canopy算法对每个数据做了所属Canopy标注，所以Kmeans聚类过程只需计算各数据对象与所属Canopy中心的距离，选择距离最短的Canopy中心对其进行簇归类。

图7 Kmeans迭代执行伪代码

在Kmeans算法每一轮Map-Reduce过程结束后，将本次输出结果与上次进行比较，当两者差值小于给定的阈值T2，就进入后续过程；否则，就将本次的输出结果作为新一轮的Map-Reduce输入传输到HDFS上，再次进入下一轮Kmeans迭代，直到满足前后两次输出结果差值小于阈值T2后进入后续过程。

(三)未抽样数据簇归类阶段

根据Kmeans聚类结果，使用Map函数对未被抽样到的数据集进行归类操作，把数据对象归入到离其距离最近的簇中心点所在的聚类簇中，生成最终聚类结果。

图8 Map函数执行伪代码

六、实验验证与分析

(一)实验平台和实验数据

实验平台采用开源Hadoop分布式框架，由4台计算机组成集群，其中1台作为主节点(Namenode)，另外3台作为从节点(Datanode)。每一台配置为Intel Xeon CPU ES-2620 2GHz, 128GB内存与2TB的硬盘。操作系统为Ubuntu14.04, JDK版本是jdk1.7, Hadoop版本是Hadoop2.5.2。

实验数据采用UCI数据集下60维的Synthetic_ Control数据集，分别采集了100 k、200 k、400 k、800 k、1 000 k五种不同大小的数据集。分组抽样的样本数据占原始数据量的60%，Canopy聚类所需的距离阈值T1和T2的设定可以根据实际情况通过交叉验证给出。另外，为避免算法随机性的影响，每类数据集均取20次运行结果的平均值进行分析。

(二)加速比分析

加速比(speedup) 可用来衡量一个算法并行化执行的有效性，是算法在并行系统和串行系统中运行所消耗时间的比率。其定义为：Sp=Tl/Tp，其中，Tl代表串行时的处理时间，Tp代表并行时的处理时间。当加速比指标Sp越大，算法效率越高。

图9 改进的Canopy_Kmeans算法加速比

可以看出，数据集在100 k、200 k、400 k规模时，随着节点数目的增加，加速比曲线趋向平缓。这是因为100 k、200 k、400 k数据集的数据量相对较小，处理时间相对较短，节点数的增加，使数据传输、任务调度、资源管理等方面的时间开销加大，从而降低了算法的执行效率。而在处理800 k、1 000 k规模的较大数据集合时，加速比曲线呈现线性增长，说明改进的Canopy-Kmeans算法在并行化执行时能够有效提升聚类效率，并且数据量越大时算法的效率越高。

(三)可扩展性分析

可扩展性(scalability) 反映了集群计算节点数目对并行化效率的影响，主要用于检验并行化算法的实用性。其定义为：E=SP/P，其中P表示集群计算节点数目，SP表示加速比；若E越大，则算法可扩展性越好。

可以看出，随着集群节点数的增加，算法的可扩展性会下降，这是因为节点数的增多会增加网络通信、任务调度、资源管理等方面的开销。但当数据的规模越来越大，节点越来越多时，算法的并行扩展比曲线下降的幅度越来越小，最后趋向维持平滑，说明随着节点数的增加，算法在处理大数据时的效率基本保持稳定。

图10 改进的Canopy_Kmeans算法可扩展性

七、结语

综上所述，改进的Canopy-Kmeans聚类算法通过将数据集进行分组抽样后聚类减少了整体计算量；最小最大原则解决了Canopy聚类初始中心点选取随机性问题；数据异度均值抽样法确保能均匀提取数据样本，使其能代表全局数据，避免聚类陷入局部最优解，保证了算法的正确性；对Kmeans迭代计算过程进行优化可进一步降低算法的时间复杂度；最后在分布式Hadoop集群系统中测试实验表明，对海量多维数值数据进行聚类处理时，改进的Canopy-Kmeans算法是有效的、收敛的，在聚类准确率和时效性上都有一定程度的提升。但另一方面，抽样数据规模如何确定以及Canopy过程中的两个距离阈值(T1和T2)的取值如何准确给出都对聚类结果的精度和稳定性有较大影响，这些问题还有待后续更进一步深入研究。