基于Hadoop平台的并行化Canopy聚类算法

李慧敏

摘要：在大数据时代，传统聚类算法已无法满足各领域的应用需求，如何改造使之适应大数据，是当前的研究热点。因此，提出基于Hadoop平台的并行化Canopy聚类算法，采用Map Reduce来实现并进行仿真实验验证，以加速比和聚类精确度作为评价指标，证明该算法在保证精确度的同时大幅提高运算速度。

关键词：Hadoop；Canopy；并行化；聚类算法；大数据

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2018）29-0018-02

Abstract： In the era of big data， the traditional clustering algorithms have been unable to meet the application needs of various fields. So how to transform it to adapt to big data， is the current research hotspot. Therefore， a parallel Canopy clustering algorithm based on Hadoop platform is proposed， which is implemented by Map Reduce and validated by simulation experiments. The acceleration ratio and clustering accuracy are taken as evaluation indicators to prove that the algorithm can greatly improve the operation speed while ensuring the accuracy.

Key words： Hadoop； Canopy； Parallel； clustering algorithm； big data

1 引言

在生活中，我们可以使用聚类解决很多问题，传统的聚类算法已经应用到很多生活领域。但是随着时代发展，海量数据的出现，传统聚类算法就已无法满足应用需求了。Canopy算法[1]就是聚类算法发展到一定阶段，Andrew McCallum等提出的一种改进算法。但随着大数据时代的到来，原有算法已无法满足应用需求，采用Hadoop平台的Map Reduce对算法进行并行化优化是应对急剧增长的大数据的有效方法。

2 Canopy 算法

Canopy算法是一种简单快速的聚类技术，采用简单的间距度量方式计算数据点之间的距离，然后跟预定义的距离阈值T1、T2进行比较，通过多次迭代，得到聚类结果。它最大的特点是不用预先指定聚类个数，因此具有很大的实际应用价值，可以用在预处理阶段，对数据进行粗聚类。

Canopy算法基本流程[2]如下：

1）设置阈值T1、T2，T1>T2（关于阈值的选取可通过交叉验证得到）；

2）从数据集中任取一点P，将P作为第一个Canopy，并將它从数据集中删除；

3）继续从集合中取点，计算其到已经产生的所有Canopy的距离，如果到某个Canopy的距离小于T2，则将其加入该Canopy，如果它到所有Canopy中心的距离都大于T1，则将其作为一个新Canopy，如果该点到某个Canopy距离小于T1，并在其与所有Canopy距离计算完成后仍未加入任何Canopy，则将它作为一个新的Canopy；

4）重复第3）步，直至数据集为空。

根据上面描述，最后每个canopy中至少含有一个数据点，一般来说会含有多个数据点，另外一个数据点可能出现在多个canopy中。

3 基于Hadoop平台的并行化Canopy算法设计

Canopy算法的提出，就是为解决数据规模变大的问题。但当海量数据涌现，Canopy算法也力不从心。所以就需要对其进行并行化优化以适应大数据。Hadoop的Map Reduce是一个软件框架，应用该框架可以改写原算法，使之能够运行在集群上，还提供了相应的机制保障并行处理海量数据的可靠性。所以采用Map Reduce来实现Canopy算法的并行化。

3.1 Map Reduce实现

本文提出了基于Map Reduce的并行化Canopy算法的实现框架。并行化Canopy算法[3]首先将输入数据集分成数据块，分发到Datanode上，在各个Datanode上用map操作并发地进行Canopy聚类，接着在Namenode上采用reduce操作归并各Datanode上的聚类结果，得到全局Canopy中心，最后再用map操作得到完整的聚类结果。实现框架如图1所示。

其中，mapper是对数据集进行Canopy聚类得到多个群组，而reducer则是对生成的群组进行筛选得到全局Canopy中心，筛选依据是以设定好的数据点数量为阈值，当某个群组中数据点小于阈值时，则判定该群组中的数据点多为孤立点，则删除该群组。

具体实现过程如下所示：

Mapper：

输入：分解好的数据块X={x1， x2， … ， xn}，其中xi为一个多维向量；距离阈值T1和T2，T1>T2。输出：canopy中心列表。

步骤1 从数据集中任取一点P，将P作为第一个Canopy，并将它从数据集中删除；

步骤2 继续从集合中取点，计算其到已经产生的所有Canopy的距离，如果到某个Canopy的距离小于T2，则将其加入该Canopy，如果它到所有Canopy中心的距离都大于T1，则将其作为一个新Canopy，如果该点到某个Canopy距离小于T1，并在其与所有Canopy距离计算完成后仍未加入任何Canopy，则将它作为一个新的Canopy；

步骤3 重复步骤2，直至数据集为空。

Reducer：

输入：各Datanode上生成的canopy中心列表

输出：全局canopy中心列表

步骤 对各Datanode上生成的canopy中心值进行归并，以设定好的数据点数量为阈值，当某个canopy中数据点小于阈值时，则判定该canopy中的数据点多为孤立点，则删除该canopy。

3.2 性能测试与分析

仿真环境：在Linux 环境下搭建Hadoop集群，共5台计算机，其中一台作为NameNode，其他4台作为DataNode。实验所使用的数据是基于UCI的Iris数据集随机生成 106、107、4*107条记录的数据集，它们所占空间大小分别为30MB、300MB、1.2GB，将它们标识为数据集Iris-1、Iris-2和Iris-3。由于数据集不相同，因此Canopy算法得到的初始聚类中心不尽相同，各不相同的初始化质心将会对作业的循环次数造成一定程度的干扰，进而对完成作业所消耗的总时间形成比较大的影响。

在实验中，采用加速比和聚类精确度作为评价指标。

从表1可以看出Canopy聚类算法的加速比近似线性。这表明在数据量大时，随着节点数的增加，优化后的算法运行速度得到了大幅提高。但在数据大规模增长后，节点增加，加速比增长变慢，这是因为随着节点增加，主从节点之间的通信代价也随着增加，对算法性能产生了影响。

从表2可以看出Canopy算法的聚类精确度并不高，所以Canopy经常应用在预处理阶段，对数据进行粗聚类。而并行化后聚类精确度并没有受到很大影响，所以采用并行化在保证精确度的同时大副提高了运算速度。

4 结论

并行化Canopy算法的聚类精确度并没有受到很大影响，运算速度却得到了大幅提升，证明了并行化算法的可行性。但Canopy算法是一种快速近似的聚类技术，从实验结果可以发现它的聚类精确度并不高，在实际应用中经常用在预处理阶段对数据进行粗聚类。針对Canopy算法的低精确度，可以增加后续处理，如应用其他精确聚类算法（K-means、K-Medoids等）在粗聚类的基础上再次进行精准聚类。因为通过粗聚类大量减少了数据量，后续处理保证了精确度，所以聚类算法的一个优化方向[4]就是针对各个应用领域中数据的特点，结合多种传统聚类算法，并进行并行化处理，来获得性能好、高效率的大数据聚类算法。

参考文献：

[1] 万旭.基于Hadoop平台的聚类算法研究[D].西安：西安电子科技大学，2016.

[2] 陈笑.基于Mahout的并行化K-means聚类算法优化研究[D].武汉：华中科技大学，2016.

[3] 牛怡晗，海沫. Hadoop平台下Mahout聚类算法的比较研究[J]. 计算机科学，2015，42（6）：465-469.

[4] 李琪，张欣，张平康，等.基于密度峰值优化的Canopy-Kmeans并行算法[J]. 通信技术， 2018，51（2）：312-317.

[5] 王永贵，戴伟，武超.一种基于Hadoop 的高效K -Medoids 并行算法[J]. 计算机工程与应用， 2015， 51（16）：47-54.

[6] 刘建红.基于Hadoop 平台的聚类算法并行化研究[D]. 吉林：吉林大学， 2017.

[7] 施亮，钱雪忠. 基于Hadoop的并行FP-Growth算法的研究与实现[J]. 微电子学与计算机信，2015， 32（4）：150-154.

[8] 吕婉琪，钟诚，唐印浒，等. Hadoop 分布式架构下大数据集的并行挖掘[J]. 计算机技术与发展， 2014， 24（1）：22-25，30.

【通联编辑：王力】