摘要：基于Map-reduce的并行编程方法，针对大规模集群多处理器多集群的聚类算法K-means的应用。提出了基于Canopy的改进K-means优化算法。实验结果证明，多核Canopy－K-means聚类算法的运行效率和准确度与处理器核数成线性比例。
关键词：K-means 多核处理 Map-reduce Canopy
Canopy for efficient K-Means
Qiu Rongtai
(Zhejiang University of Media and Communications，Hangzhou,310018, Zhejiang)
Abstract: In this paper, we develop a applicable parallel programming method which based on Map-reduce . A improved K-means algorithm based on Canopy is presented according to it’s sensitiveity to the initial centers. Our experimental results show basically linear speedup with an increasing number of processors .
Key words: K-means Map-reduce Multi-core Canopy
1.引言
计算机性能的提高将越来越依赖于处理器的数量的增加以及集群的规模.本文核心目标是通过应用Map-reduce并行编程框架，高效的利用数量众多的可并行的处理器核，允许程序员轻松高效地开发一个多核机群机器学习算法canopy-k means。文章改进如下：
a针对传统K-means算法对初始聚类中心依赖，利用Canopy聚类划分来优化初始聚类中心。
b先将数据集进行Canopies有覆盖划分，在计算数据点到哪个K-center最短时，只计算与它在同一个Canopy下的K-centers距离而不必计算其到所有K-centers的距离，效率大大提高。
C每个数据集相对独立，可以使用Map-reduce编程模型进行并行处理。
d处理器核数及处理节点的越多，其执行效率线性增长。
2.基于Mapreduce的Kmeans改进算法
2.1 算法思想
首先所有数据集按某种特征划分成K类，每类的数据成员的特征相同。初始数据根据数据存储节点及mapper核的个数P划分成C1 C2……CP个数据集，每个数据集可以分别分配给某一Mapper节点独立执行。集群中选择一个节点作为master节点进行并行任务的调度，在主节点处设置两个共享文件，这两个文件可以被所有处理器访问，其中一个文件包含初始随机选的K个聚类中心点和每次迭代执行后产生的K个聚类的聚类中心。这是一个全局文档，每次迭代都在这个文件后面增加一些记录。另一个文件保存产生Canopies列表供全局调度用。Master节点负责管理各个Mapper节点和Reduce节点的调度及数据分配与结果的回收，分配给Mapper核相应的小数据块，并且传给每个Mapper节点K个聚类中心以及Canopies列表。每个Mapper核并行计算各自要求的任务后通知Master，然后Master调度相应的Reduce进行处理，返回结果以决定是否下一轮迭代。
首先用Canopy聚类技术分两个阶段执行聚类：第一步就是快速和近似地把数据分成一些子集，称之为罩盖（Canopy）；然后对每个Canopy内的点用精确的计算方法再聚类。它在两个阶段使用了不同的距离度量方法，形成重叠的Canopy.创建好Canopy后，第二步就是针对Canopy内的点使用K-means算法进行聚类。现在只需要对罩盖内的点进行精确的聚类，从而大大避免了传统聚类算法中对所有数据点进行精确计算，另外允许有重叠的子集也增加了算法的容错性和消除孤立点作用。从某种意义上说，只要保证第一步的准确性，整个算法就是准确的，通过实验表明，使用这种罩盖技术后，不仅极大地减少了距离的计算量，其准确程度比一般的聚类方法还略有提高。
2.2 算法流程
2.2.1 数据预处理
将数据进行格式化，每一个数据都按特定的格式（数据值，出现次数）即（datavalue,emergetime）,将每个数据按key为datavalue进行聚合，聚合后的每个数据为数据和出现次数的组合。
Mapper:(offset,datavalue)à(datavalue,1)
Reducer: (datavalue,1) à (datavalue,emergetime)
2.2.2 Canopies划分
⑴ 总体思路：预处理后每一个数据（即datavalue）看作一个中心点，按Canopy算法产生一些可覆盖的划分，初始划分以随机选的第一个数据作为本聚类标识Canopyid。对于每个Mapper节点的数据，都须判断它是否落入先前产生的Canopies中，若落入其中任意一个Canopy则标识自己相应的Canopyid,否则产生一个新的Canopy,并用自己的数据值作为Canopid。
⑵实现过程:在Master计算节点上存储已产生的Canopies,这样若某个节点产生新的Canopid要及时传送给Master节点，以便其他节点读取。
⑶实现方法：
Mapper: (datavalue,emergetime)à(Canopyid,( datavalue,emergetime))
Reducer: (Canopyid,( datavalue,emergetime)) à
(Canopyid,( datavalue,emergetime)，……, ( datavalue,emergetime))
2.2.3 将数据分配到Canopies
（1）总体思路：经过2.2.3.2处理后的数据，整个数据空间的数据划分成了几个Canopies，这些Canopies存储于Master中。每个Mapper节点读取Master中的Canopies，然后判断每一个数据落在哪几个Canopies上，并输出数据和相应的Canopies（用其Canopid表示）。
（2）实现过程:Mapper计算节点上每个数据所属的Canopid。
（3）实现方法：
Mapper: (datavalue,emergetime)à(datavalue,（emergetime， Canopyid_list）)
Reducer: (datavalue,（emergetime， Canopyid_list）) à
(datavalue,（emergetime， Canopyid_list）)
2.2.4 实现Canopy-Kmeans聚类
（1）总体思路：根据Canopy算法产生的Canopies代替初始的K个聚类中心点，由于已经将所有数据点进行Canopies有覆盖划分，在计算数据离哪个k-center最近时，不必计算其到所有k-centers的距离，只计算和它在同一个Canopy下的k-centers。这样可以提高效率。
（2）实现过程:
每次Mapper节点在进行map()前需要通过Master节点加载上一次产生的K-centers和产生的Canopies列表，并计算每个K-center落入哪些Canopies中。
每次迭代过程mapper的输入数据都是2.2.3.3产生的(datavalue,（emergetime， Canopyid_list）)。每个数据只用与落入该数据在同一个Canopy中的K-centers比较距离，选择最短的那个K-center作为要划分的类，再以K-center作为key,产生一条格式为:“k-centerid dativalule emergetime Canopyid_list”的记录。
距离试题函数：每个数据点的dativalule之间差的绝对值。
（3）实现方法：
Mapper: (datavalue,（emergetime， Canopyid_list）)à
(k-centerid,(datavalue,emergetime， Canopyid_list）)
Reducer: (k-centerid,(datavalue,emergetime， Canopyid_list）) à
(new_k-centerid,(datavalue,emergetime， Canopyid_list）)
（4）最终结果的输出：
我们可以把每次迭代后产生的new_k-centers与上一次的k-centers作比较，当他们的距离濒于预先设定的阈值时，认为迭代结束，输出最后一次的(k-centerid,(datavalue,emergetime， Canopyid_list）)格式为：”k-centers，datavalue_list”。
2.3 算法复杂性分析
K-Means法随机选择K个数据作为初始的聚类中心，按照算法的迭代执行，整个算法的结束条件是类的重心(或凝聚点)不再改变。传统的K-Means的计算复杂性是O(dkt)，其中，d为文献数量，k为类的数量，t为迭代次数。在运用Canopy算法对K-Means进行优化的情况下，由于在划分Canopies是可覆盖划分，即某一点有可能同时属于n个Canopies,这样聚类需要比较dkn2t/c次, 其中C为Canopies的数量. 在多核框架下，其理论复杂性是O([dkn2tcp+dkn2log(P)/c]),其中P为处理器核的数量。K-Means 在多核并行执行情况下其效率将近是单核下的P倍，随着核数的增多，效率线性增长。
3 .实验与分析
为了便于研究，把算法分两种情况下执行：一个在我们设计的框架下，另一个以传统的方式顺序执行。实验数据从网络上采集，在实验开始之前在实验环境的存储设备上准备完毕。网络上的数据主要是两个部分，一部分是图书馆的数据，一部分是学校学生成绩的数据。图书馆的数据大概有10G多，存放在Hadoop的分布式文件系统HDFS中。学校学生成绩数据也有将近900M，同样放在HDFS中。我们进行了大量的试验来测试其效率。不仅如此，我们还分别在拥有不同核个数的处理器上执行。我们在 Intel X86 ，Intel(R) Core™ Duo CPU 2 MHz CPUs ， 2GB 物理内存 。并且在运行HP－UNIX的机器HP9000上分别做实验。另外我们通过4，6，8，16 核的处理器上模拟试验得到如下结果。在双处理器执行过程中，执行各个数据的平均效率比原来大约提高了1.9倍。这是由于原始的K-means算法并没有很好的利用处理器时钟周期，然而在我们把任务独立分给不同处理器并行的情况下算法效率得到了很大的提高。通过在2，4，8，16 多处理器机器上实验，我们可以很直观地把我们得到的结果描绘成图2.在图中，实线代表平均加速倍数，虚线分别代表最大与最小的加速倍数。分析图中可知，随着处理器个数的增加，我们得到的加速倍数是线性增长的，然而这个加速斜率略低于1。通过分析可知，没有得到完整的线性增速是由于处理器之间相互通信和集合阶段没有并行的原因。在多核的情况下我们通过模拟试验，结果比现在更理想，因为他们之间共享存储区域，其相互通信比以前少。
图1
4.结语
在处理器的频率不变的情况下，同样可以提高k means的效率而不受限于处理器的频率。，通过多核处理器可以计算更大的数据集和获得更好的效率。利用Map-reduce编程方法，使K-means算法在双核的情况下效率提高了两倍，在64核的情况下得到56倍的执行效率，得到线性增长的效率，并且对的初始点用Canopy算法进行优化提高了聚类的准确度。算法具有很大的适用范围，本文创新之处是我们并没有对原来的算法做根本的改变，只是提出应用Map-reduce并行执行K－means聚类算法以及对K－means初始聚类中心优化方法，显著提高了执行效率。
参考文献：
[1] Jeffrey Dean, Sanjay Ghemanwat, MapReduce: Simplified Data Processing on Large Clusters
[2] K-means算法中的k值优化问题研究，系统工程理论与实践，2006年2期
[3]Kenneth Heafield Hadoop Design and K-Means Clustering Google Inc January 15 2008
[4] The impact of the canopy structure on the spatial variability in forest floor carbon stocks.Geoderma: An International Journal of Soil Science, 2010 3/4
[5] Dummler, Rauber, Runger, Mapping Algorithms for Multiprocessor Tasks on Multi-core Clusters
作者简介：
邱荣太（1982－ ），男，汉族，浙江传媒学院播音学院实验办，工程师，硕士，主要研究分布式及流媒体应用。