双MapReduce改进的Canopy-Kmeans算法

刘宝龙，苏 金

(西安工业大学 计算机科学与工程学院，西安 710021)



双MapReduce改进的Canopy-Kmeans算法

刘宝龙，苏 金

(西安工业大学 计算机科学与工程学院，西安 710021)

由于传统的Canopy-Kmeans算法在中心点的选取存在随机性，其迭代过程的冗余计算降低了算法的运行效率.文中基于“最小最大原则”和三角不等式原理，在Hadoop平台上提出了一种基于双MapReduce改进的Canopy-Kmeans算法.实验结果表明：设计的并行算法精确率在不同大小的数据集上平均提高了15.3%，加速比和扩展性随着数据规模和节点的不断增加也相应的提高了1.5～3倍，解决了Canopy中心点选中存在的问题和迭代过程中冗余的距离计算.

Canopy-Kmeans；冗余计算；Hadoop平台；双MapReduce

常用的K-means算法是一种基于划分的聚类挖掘算法，该算法的思路简单、收敛速度快，使用广泛且易于实现，但在K值及中心点的选取上仍然存在很大的随机性和不科学性，容易使聚类结果陷入局部最优，且在迭代过程中存在大量的冗余计算，并行处理能力差，缺乏可伸缩性，大大降低了算法的运行效率.文献[1]针对传统的K-means算法提出了Canopy改进策略，避免了K值选取的盲目性，进一步提高聚类算法的准确率和稳定性.文献[2-3]应用三角不等式原理对传统的K-means算法进行了改进，避免了算法中冗余计算，提高了收敛速度和降低了内存开销，但并行性不高，缺乏扩展性.文献[4]提出了K-meansCan算法，其先对数据进行多次随机采样，再进行K-means预聚类，然后将来自不同簇的聚类点进行合并，最终实现聚类，在很大程度上提高了聚类结果的质量和算法的效率.文献[5]提出了一种基于初始聚类中心改进的选择算法M+Kmeans，在初始中心点及K值的选取上进行了细致的优化.文献[6]提出了一种基于MPI的并行计算的层次聚类算法，它虽然从某种程度上利用集中式存储方式提高了算法的正确性和时效性，但是该算法只能运行在单节点上，在处理大数据任务时，算法的效率还不够高；文献[7]利用遗传算法的粗粒度并行化设计思想提出了在Hadoop平台下将遗传K-means聚类算法进行并行化设计，提高了K-means算法的效率.文献[8]用MapReduce模型实现传统K-means算法的设计，在处理大数据集上，获得了较好的加速比和良好的扩展性.文献[9]通过ACO算法对K-means算法进行了改进，并利用MapReduce并行化K-means算法来处理海量数据中存在的严重内存不足问题，使得聚类算法的可扩展性、收敛性以及在聚类计算时的内存泄漏问题上均得到了显著的改善.文献[10-11]提出了基于Hadoop集群平台的并行化MapReduce编程模型，其借助于开源的MapReduce编程技术和当前流行的分布式技术充分满足了算法并行化执行的需求，实现了K-means分布式聚类[12-14]，提高了聚类算法的加速比和运行效率.文献[15]主要采用Spark和Hadoop技术进行混合式的框架设计，实现了具有迭代式性能的分布式K-means聚类算法，提高算法的加速比、吞吐量和可扩展性.文献[16]针对分布式Canopy-Kmeans算法中的Canopy选取的随机性问题进行了改进，避免了Canopy选取的盲目性.

鉴于传统K-means算法的不足，本文采用三角不等式原理[2-3]和“最小最大原则”[1,16]，在Hadoop云计算平台上提出了一种基于双MapReduce分布式编程模型改进的Canopy-Kmeans算法.

1 Canopy-Kmeans算法

原始的Canopy-Kmeans算法是在K-means算法的基础上提出的一种优化，其基本思想是首先通过Canopy算法进行聚类，以确定簇数以及初始簇心，接着通过K-means算法进行迭代运算，收敛出最后的聚类结果.具体描述如下：对于任意的数据集合V,预先设定Canopy算法的两个区域半径(即阈值)，通过粗糙距离计算方法计算集合中各对象的相似性，按照各对象的相似性可把数据划分成若干可重叠的小集合(即Canopy)，经过一系列的计算后，最终可使得所有的对象均落在Canopy覆盖的范围内；对落在同一区域内的对象，利用K-means算法重新迭代计算出新中心点，并根据对象与新中心点之间的距离重新划分对象所属区域；循环迭代执行“划分Canopy-计算中心点”的过程，直到k中心点的位置不再发生变化，即达到一种稳定的聚类状态为止.由上述介绍可知，K-means算法虽然在开始时使用Canopy算法进行了预处理，无需再人为设置初始的聚类中心点及聚类个数K，但Canopy在初始中心点的选取上容易受到区域半径的主观影响，具有较大的盲目性和随机性.而该算法对K-means算法本身并未作出任何的改进，聚类迭代次数依然繁琐，存在大量的冗余计算.针对以上存在的问题，本文同时从以下两个方面的对原始的Canopy-Kmeans算法进行了改进.

1.1 Canopy算法的改进

定义1(Canopy) 给定任意数据集合V={vi|i=1,2,…,n}，对于∀xi∈V，若其满足如下公式{Cj|∃||xi-Cj||≤T1,Cj⊆V,i≠j}，则称xi为Canopy集合，Cj为VCanopy中心点，T1为Canopy集合半径.

定义2(Canopy中心点) 给定数据集合V={vi|i=1,2,…,n}，对于∀xi∈V，若其满足如下公式{Cm|∃||xi-Cm||≤T2,T2

很明显，从以上的定义可知，Canopy算法执行的效率受Canopy区域半径T1、T2影响较大，当T1过大时，会使同一点属于多Z个Canopy，增加了计算开销；当T2过大时，会减少聚类的个数，使得聚类过程陷入局部最优.这样就导致了Canopy算法对初始中心点的选取上具有较大的盲目性和随意性.因此，为了解决Canopy区域半径T1、T2以及初始中心点的随机选取问题，本文采用了一种基于“最小最大原则”改进的Canopy算法来提高聚类结果的准确性[16].

为了避免在聚类过程陷入局部最优，应该使Canopy获得的中心点间距尽可能大.最小最大的基本原理[14]是首先随机选取一个种子点作为中心点A，然后计算集合C中剩余点到A点的距离，选取距离最大的点作为第二个种子点B，再计算C中剩余数据点到这两个种子点的距离，得出到这两个种子点的距离，得出到这两个中心距离最小的点Min(dA,dB)，找到这些距离最小者中的最大值Max(Min(dA,dB))，迭代条件若满：

其中dA、dB为数据点到A、B点的距离，若满足以上条件则该数据点为第三个种子点，按照上述方法迭代，最终可以确定所有的中心点，得到K值.

基于上述原理改进的Canopy中心点选取方法避免了区域半径T2的设置(T2为非Canopy中心点区域半径，当所有中心点确定后，该值就无需设置)[16].另外，“最小最大原则”Canopy中心点选择方法在具体应用中呈现如下规律：Canopy个数低于或者超过类别真实值时，DistC变化呈现较小幅度；当Canopy个数临近或达到类别真实值时，该距离呈现较大突变[16-17].因此，为了确定Canopy中心点的最优个数以及区域半径T1，参照文献[16,18]中的边界识别思想，引入了表示DistC变化幅度的深度指标Depth(i)，其定义为

Depth(i)=|Distmin(i)-Distmin(i-1)|+|Distmin(i+1)-Distmin(i)|

当i达到最优聚类时，深度值Depth(i)取得最大值.由以上定义可知，此时Canopy中心点集合中前i个记录即为最优的聚类初始中心点，同时为了保证最终的聚类中心点均落在Canopy范围内，可设区域半径T1=Distmin(i).则基于“最小最大原则”可将Canopy算法进一步改进为

定义3(Canopy) 给定任意数据集合V={vi|i=1,2,…,n}，对于∀xi∈V，若其满足如下公式{Cj|∃||xi-Cj||≤Distmin(i),Cj⊆V,i≠j},则称xi为Canopy集合，Cj为Canopy中心点且∀Cj∈U.Distmin(i)表示数据点xi为所有最小距离中的最大者.

定义4(Canopy中心点) 给定数据集合V={vi|i=1,2,…,n}，对于∀xi∈V，若其满足如下公式

{Cm|∃||xi-Cm||

Cm⊆V,i≠m}

则称Cm为非Canopy候选中心点集合.Distmin(i)为数据点xi为所有最小距离中的最大者.

经过以上的分析可知，经过改进的Canopy算法，解决了人为设置区域半径T1、T2以及中心点和K值选取的盲目性问题，为聚类结果的准确性提供了可靠的理论依据.

1.2 K-means算法的改进

定义6 假设U为所有已聚类中心的集合，当∀x∈X,∃u∈U，使得d(x,u)=mind(x,U),那么u为向量x的聚类中心.

公理1 任意一个三角型，两边之和大于第三边，两边之差小于第三边.由于欧式距离满足三角不等式特性，我们可以将它扩展到多维的欧几里得空间[19-21].对于任意三个向量 x、b、u，其满足以下两个不等式：

d(x,b)+d(b,u)≥d(x,u)；

d(x,b)-d(b,u)≤d(x,u)

根据以上定义及公理，我们可以得到以下应用：假设xp是数据集当中任一个向量，ui是向量xp当前的类中心，d(xp,ui)已知且uj是剩余中心点中除ui外任意的一个，如果2d(xp,ui)≤d(ui,uj)，则有2d(xp,ui)-d(xp,ui)≤d(ui,uj)-d(xp,ui)，化简可得：

d(xp,ui)≤d(ui,uj)-d(xp,ui)

(1)

由公理1中欧式空间的三角不等式特性可得

d(ui,uj)-d(xp,ui)≤d(xp,uj)

(2)

因此，联立式(1)、(2)可得到如下结论：

d(xp,ui)≤d(xp,uj)，即向量点xp属于聚类中心点ui.

由以上推导可知，对于传统的K-means算法，若能在距离迭代计算之前进行一次筛选，则可避免很多的冗余计算.若用d1(xp,uj)表示xp到uj上界约束，用d2(xp,uj)表示xp到uj下界约束，则基于三不等式角原理改进的K-means算法，可以进一步描述为：

定义7 (K-means) 将定义3得到的Canopy中心点集合U中的元素作为K个聚类质心点u1,u2,…,uk∈Rn， 对于Canopy子集中的任意数据点xp：若满足2d1(xp,ui)≤d(ui,uj)，则数据点xp属于聚类中心点ui，不需进行任何距离迭代计算；若满足2d1(xp,ui)≥d(ui,uj)且d2(xp,uj)≤d1(xp,uj)时，需要对数据点xp进行迭代计算.具体迭代步骤如下：

① 计算数据点xp应该属于的类

② 对于每一个类k，重新计算该类的质心

③ 循环执行①、②，直到聚类准则函数

收敛为止，其中c(p)为数据点p到k个类中距离最近的类.通过以上的改进可知，基于三角不等式原理改进的K-means算法能够大幅度地减少迭代过程中不必要的距离计算，从而进一步提高原算法的运行速度.

2 双MapReduce设计的Canopy-Kmeans算法

针对定义3、定义4及定义7的改进理论，本文在Hadoop平台上采用了双MapReduce编程技术，将改进的整个算法分成两个MapReduce子任务来完成，并用第一个MapReduce子任务的输出结果作为下一个MapReduce子任务的输入.算法设计的整体方案如图1所示.

图1 基于双MapReduce改进的Canopy-Kmeans并行算法流程

第一个子任务是在MapReduce编程模型中利用“最小最大原则”对Canopy聚类算法进行“粗糙”聚类.通过计算数据的相似性来对全体数据集进行相似性划分，最终可得到各个分组(Canopy子集)及所需的中心点集合和k值.这样下一步的初始中心点的选择就不至于因为随机选择而偏离实际中心点太远，同时也避免了初始K值设定的盲目性；第二个MapReduce子任务采用基于距离三角不等式原理改进的K-means算法对得到的各个分组(Canopy子集)进行“精细”聚类.在每一次迭代计算之前，通过对各个数据点距离计算的筛选，可减少许多不必要的计算，进一步优化了传统的聚类算法；最后通过Driver对象将以上两个MapReduce子任务作业按线性方式顺序链接并自动化地生成一个可执行序列交给Hadoop平台处理，并将最终得到的聚类结果存入HDFS中.

2.1 Canopy与K-means算法

将待处理数据上传到HDFS中，并将数据分片存储到若干台DataNode中.为了得到K-means算法初始的聚类中心点及K值，第一个MapReduce子任务将Canopy算法分为两个阶段来完成，即Map阶段和Reduce阶段.在Map阶段，根据“最小最大”原则及边界意识对输入的键值对进行Canopy聚类迭代，然后将各个DataNode在Map阶段进行Canopy聚类得到的局部中心点集合Pi作为Reduce阶段的输入；在Reduce阶段，合并所有DataNode输出的Canopy中心点集合Pi，把合并结果存入集合P中，接下来在集合P中进行全局Canopy“粗糙”聚类，重复上述过程，直到数据集List为空.最后输出聚类中心点个数K及全局Canopy中心点集合U.

第二个MapReduce子任务主要将K-means算法分为三个阶段来完成，即Map阶段、Combine阶段和Reduce阶段.在Map阶段，将第一次MapReduce子任务输出的K值及聚类中心点集合U作为本次改进K-means算法的初始簇的个数K及聚类质心，并将这K个质心存储到HDFS上作为一个全局变量.利用距离三角不等式原理对canopy子集中得到数据点进行重新划分；在Combine阶段，由于在Map阶段每个数据节点输出的中间结果比较大，势必会造成多次溢写的发生，消耗大量的系统资源，为了进一步提高算法的运行效率，本算法在不改变最终计算结果的情况下，引进了Combine()函数来优化MapReduce的中间结果，其将键值对中具有相同key值的value合并起来，可大幅度地减少溢写到磁盘的数据量.另外，本阶段还把最后由Combine()函数合并的结果作为Reduce阶段的输入，进一步减轻了Reduce阶段再次合并中间结果的负担，提高了原算法的执行速度；在Reduce阶段，首先读取出从每个Combine中处理的数据样本个数和每个数据样本各维的坐标值，并将对应的各维累加值分别对应相加，再除以总的样本个数，所得的结果即为新的中心点坐标.然后把Reduce阶段输出的结果，作为新一轮迭代计算的中心点坐标并将其上传到HDFS中进行下一轮迭代，最后直到算法收敛为止.

2.2 算法时间复杂度

串行的Canopy-Kmeans算法的时间复杂为o(nkf2t1/c)，其中n为数据量，k为类的数量，t1是迭代次数，c为Canopy的数量，f代表一个数据点被划分到多个Canopy重叠区域内.由于在Hadoop平台中是由多个DataNode数据节点同时进行数据处理的，并且主从节点之间需要彼此通信协同工作.假设实验中有m个DataNode数据节点并行工作，则并行的Canopy-Kmeans算法的时间复杂度为o(nkf2t2/mc)，理论上，相比较串行算法而言，复杂度降低了(mt1/t2)倍，其中t2远小于t1.这是是因为经改进的算法，减少了许多的冗余计算和算法的迭代次数，提高了数据处理的性能.

3 实验结果及分析

3.1 Hadoop集群环境

Hadoop集群一共包括五台计算机，分别通过局域网进行连接，每台计算机的CPU为Intel(R)i5双核2.3 GHz，内存4 G,硬盘500 G,操作系统是windows7 64位.并在每台机器上安装Cygwin虚拟机用它来模拟Linux环境.配置SSH免密码登录，安装Hadoop v2.0，配置分布式的Hadoop集群，并将其中一台机器角色设置为Jobtracker和NameNode服务节点，其余四台机器角色均设置为DataNode和TaskTracker服务节点.JDK版本为1.8.0-i586，安装MyEclipse10.0并在MyEclipse10.0中创建双MapReduce工程，然后通过driver对象进行顺序化链接执行，最后将要处理的数据集导入到HDFS中.

为了测试本文算法的性能及可行性，主要采用了以下几个衡量指标：准确率(样本正确的个数/样本总数)、加速比以及算法的扩展性，并将实验结果分别与传统的K-means算法和原始的Canopy-Kmeans算法进行了比较.另外，算法中的实验数据均选自UCI数据集中的真实数据( http://archive.ics.uci.edu/ml/datasets.html).

3.2 算法的准确性分析

由表1实验结果可知：从总体上看，改进的Canopy-Kmeans算法准确性明显高于其余两个算法，这个容易理解，因为在数据预处理阶段，Canopy算法采用“最小最大”原则对大数据集进行了“粗糙”聚类，避免了随机指定K值、T1、T2、初始中心点的盲目性，大大提高了聚类结果的精确性，同时也减少了K-means算法收敛时的迭代次数；另外，当数据规模与维数成线性增加时，聚类的个数K值也在逐渐变大，这对于一个数据向量来讲，需要计算的数据向量与类中心之间的距离就变得相当多，而基于三角不等式原理改进的K-means算法对数据向量的距离计算进行了预先筛选，减少了迭代过程中的距离计算次数，避免了过多的冗余计算，大幅度地提高了算法的运行效率.

表1 三种算法在Hadoop平台上的结果对比

3.3 算法在Hadoop平台上的加速比分析

为了测试本文算法的加速比，实验数据从UCI数据集中的Poker Hand数据集随机选取了3个样本数据，样本数分别为100万条，400万条，1600万条如图2～4所示.

图2 数据规模为100万条时的加速比曲线图

从图2到图4可以看出，设计的算法加速比基本上是成线性的，当数据规模越大时，改进的Canopy-Kmeans并行算法加速比就越接近线性增长.随着DataNode数据节点的增加，三种算法的加速比增长速度也逐渐趋于减缓，主要是因为当数据规模相同时，节点的增加会导致各个节点之间通信开销变大，占用一部分必要的时间.另外，可以清晰的看到，无论数据规模大小与否，改进后的Canopy-Kmeans并行算法的加速比均明显高于其它两个算法，这是因为文中算法在K-means算法阶段增加了Combine函数的设计，其对Map阶段产生的大量中间结果进行了本地化Reduce预处理，减少了DataNode数据节点之间的I/O传输，大大节省了算法运行的成本，尤其是当数据规模越大时，效果就越明显.

图3 数据规模为400万条时的加速比曲线图

图4 数据规模为1600万条时加速比曲线图

3.4 算法在Hadoop平台上的扩展性分析

为了测试本文算法的扩展性，分别在不同的DataNode数据节点个数下，对不同大小的数据集进行了实验.实验中的数据来源于UCI数据集中的SIFT10M Data Set 数据集,并从中随机抽取了四组样本数据，其样本数分别为200万条，400万条，800万条，1600万条,如图5所示.

图5 Hadoop平台上的扩展率曲线图

从图5中可以看出，在不同规模的测试数据集上，随着DataNode数据节点的递增，算法的运行效率整体上在逐渐下降.这是因为当Hadoop平台上有多个DataNode运行时，在Reduce阶段各节点之间需要传输并合并大量的中间数据，这使得节点之间的通讯代价增大，需耗费很多的系统资源，加大了算法的时间运行成本.另外，对于相同规模的数据集，随着节点的增加，数据量大的样本集运行效率率明显优于数据量小的样本集，尤其在第4个节点时，运行1600万条数据时明显比运行800万条的数据运行效率高，这是因为随着数据量的增加，处理数据的时间远远会大于各个节点的通信开销，这使得Hadoop平台的DataNode节点更容易发挥它的并行计算能力.由此可知，本文算法在节点增加时，可以提高系统对相同规模数据的处理能力，具有良好的扩展性.

4 结 论

1) 将Hadoop云计算平台与基于“最小最大”原则改进的Canopy算法和基于三角不等式原理改进的K-means算法相结合，设计并实现了一种基于双MapReduce编程模型改进的Canopy-Kmeans算法.

2) 与传统的K-means算法相比，改进的算法精确率平均提高了15.3%，且加速比和扩展性随着数据规模的不断增大也相应的提高了1.5～3倍，明显改善了聚类效果，适合运行于大规模的数据处理平台上，且数据量越大，节点数越多，算法所取得的效果就越好.

3) 本文算法对于非等轴状分布、具有噪声或孤立点的数据较为敏感，不适合非凸面形状、条形状聚类的数据集，或者簇大小差别很大的数据集，且在高维数据空间上Canopy中心点的生成较为耗时，在不影响算法聚类精度的基础上，需进一步提高K-means算法的效率.

[1] 赵庆.基于Hadoop平台下的Canopy-Kmeans高效算法[J].电子科技,2014,27(2):29.

ZHAO Qing.The Canopy-Kmeans Efficient Algorithm Based on Hadoop Platform[J].Electronic Science and Technology,2014,27(2):29.(in Chinese)

[2] 张顺龙,库涛,周浩.针对多聚类中心大数据集的加速K-means聚类算法[J].计算机应用研究,2016,33(2):413.

ZHANG Shunlong,KU Tao,ZHOU Hao.An Accelerated K-means Clustering Algorithm for Large Data Sets in Multi Cluster Centers[J].Computer Application Research，2016,33(2):413.(in Chinese)

[3] 常晋义,何春霞.基于三角不等式原理的K-means加速算法[J].计算机工程与设计,2007,28(21):5094.

CHANG Jinyi,HE Chunxia.K-means Acceleration Algorithm Based on the Principle of Triangle Inequality[J].Computer Engineering and Design,2007,28(21):5094.(in Chinese)

[4] 雷小锋,谢昆青,夏征义.一种基于K-means局部最优性的高效聚类算法[J].软件学报,2008,19(7):1683.

LEI Xiaofeng,XIE Kunqing,XIA Zhengyi.An Efficient Clustering Algorithm Based onK-means Local Optimality[J].Journal of Software,2008,19(7):1683.(in Chinese)

[5] 武霞,董增寿,孟晓燕.基于大数据平台Hadoop的聚类算法K值优化研究[J].太原科技大学学报,2015,36(2):1673.

WU Xia,DONG Zengshou,MENG Xiaoyan.Research on K Value Optimization of Clustering Algorithm Based on Large Data Hadoop Platform[J].Journal of Taiyuan University of Science and Technology,2015,36(2):1673.(in Chinese)

[6] QIAN Y J.Research on and Implementation of the Technologies of Mining of Massive Datasets[D].Chengdu:University of Electronic Science and Technology of China.2009.

[7] 贾瑞玉,管玉勇,李亚龙.基于MapReduce模型的并行遗传K-means聚类算法[J].计算机工程与设计,2014,2(2):31.

JIA Ruiyu,GUAN Yuyong,LI Yalong.Parallel Genetic K-means Clustering Algorithm Based on MapReduce Model[J].Computer Engineering and Design,2014,2(2):31.(in Chinese)

[8] 江小平,李成华,向文,等.K-means聚类算法的MapReduce并行化实现[J].华中科技大学报,2011,39(1):120.

JIANG Xiaoping,LI Chenghua,XIANG Wen,et al.MapReduce Parallel Implementation ofK-means Clustering Algorithm[J].Journal of Huazhong University of Science and Technology,2011,39 (1):120.(in Chinese)

[9] 虞倩倩,戴月明,李晶晶.基于MapReduce的ACO-Kmeans并行聚类算法[J].计算机工程与用,2013,49(16):117.

YU Qianqian,DAI Yueming,LI Jingjing.ACO-Kmeans Parallel Clustering Algorithm Based on MapReduce[J].Computer Engineering and Applications,2013,49(16):117.(in Chinese)

[10] QIU R T.Research on MapReduce Application Based on Hadoop[D].Jiaozuo:Henan Polytechnic University,2009.

[11] 温程.并行聚类算法在MapReduce上的实现[D].杭州:浙江大学,2011.

WEN Cheng.Parallel Clustering Algorithm on the MapReduce to Achieve [D].Hangzhou:Zhejiang University,2011.(in Chinese)

[12] 赵卫中,马慧芳,傅燕翔,等.基于云计算平台Hadoop的并行K-means聚类算法设计研究[J].计算机科学,2011，38(10):166.

ZHAO Weizhong,MA Huifang,FU Yanxiang,et al.Research on ParallelK-means Algorithm Design Based on Hadoop Platform[J].Computer Science,2011，38(10):166.(in Chinese)

[13] 周丽娟,王慧,王文伯.面向海量数据的并行K-means算法[J].华中科技大学学报,2012(S1) :150.

ZHOU Lijuan,WANG Hui,WANG Wenbo.ParallelK-means Algorithm for Massive Data[J].Journal of Huazhong University of Science and Technology,2012(S1):150.(in Chinese)

[14] CUI X L,ZHU Pingfei,YANG Xin,et al.Optimized Big DataK-means Clustering Using MapReduce[J].The Journal of Supercomputing,2014,70(3):1249.

[15] 唐振坤.基于Spark的机器学习平台设计与实现[D].厦门:厦门大学,2014.

TANG Zhenkun.Design and Implementation of Machine Learning Platform Based on Spark[D].Xiamen:Xiamen University,2014.(in Chinese)

[16] 毛典辉.基于MapReduce的Canopy-Kmeans改进算法[J].计算机工程与应用,2012,48 (27):22.

MAO Dianhui.Improved Canopy-Kmeans Algorithm Based on MapReduce[J].Computer Engineering and Applications,2012,48(27):22.(in Chinese)

[17] 刘远超,王晓龙,刘秉权.一种改进得K-means文档聚类初始值选择算法[J].高技术通讯,2006,16(1):11.

LIU Yuanchao,WANG Xiaolong,LIU Bingquan.An Improved Initial Value Selection Algorithm forK-means Document Clustering[J].High Tech Communication,2006,16(1):11.(in Chinese)

[18] DEAN J,GHEMAWAT S.MapReduce：Simplified Data Processing on Large Clusters[C]//Proceedings of the 6th International Conference on Operation Systems Design & Implementation (OSDI),Berkeley,CA,USA,2004:137.

[19] ELKAN C.Using the Triangle Inequality to AccelerateK-means[C]//Proceedings of the 20th International Conference on Machine Learning,Washington DC,2003.

[20] ANDREW W M.The Anchors Hierarchy:Using the Triangle Inequality to Survive High Dimensional Data[C]//Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence,Stanford University,San Francisco,2000.

[21] 何春霞,常晋义.三角不等式原理对聚类算法的改进[J].常熟理工学院学报(自然科学版),2007,21(2):100.

HE Chunxia,CHANG Jinyi.The Improvement of Clustering Algorithm Based on the Theory of Three Inequalities[J].Journal of Changshu Institute of Technology(Nature Science Edition),2007,21(2):100.(in Chinese)

(责任编辑、校对 肖 晨)

Improved Canopy-Kmeans Algorithm based on Double-MapReduce

LIUBaolong,SUJin

(School of Computer Science and Engineering,Xi’an Technological University,Xi’an 710021,China)

The Canopy-Kmeans algorithm has the disadvantage of great randomness in the selection of center points, and the redundant computation in the iterative process significantly reduces the operation efficiency of the algorithm. So the paper proposes an improved Canopy-Kmeans algorithm based on the Double-MapReduce on the Hadoop platform,which is based on the "minimum maximum principle" and the principle of triangle inequality.The experimental results show that the precision of the designed parallel algorithm is raised by 15.3% on average,and the speedup and scalability are increased by 1.5 to 3 times with the increase of the data size and the number of node. The problem existing in the selection of Canopy center point is successfully solved and the redundant distance calculation in iterative is avoided.

Canopy-Kmeans;redundant computation;hadoop platform;double-MapReduce

10.16185/j.jxatu.edu.cn.2016.09.009

2016-05-09

陕西省科技统筹创新工程计划项目(2015KTCXSF-10-11);西安市未央区科技计划项目(201609).

刘宝龙(1976-)，男，西安工业大学副教授，主要研究方向为信息安全工程.E-mail：b.liu@xatu.edu.cn.

TP301.6

A

1673-9965(2016)09-0730-08