基于MapReduce的K-means聚类算法的优化

文章编号：1671 - 4598(2016)07 - 0272 -04

计算机测量与控制.2016. 24(7)

Computer Measurement & Control

DOI: 10. 16526/j. cnki. 11 — 4762/tp

设计与应用

中图分类号：TP311

文献标识码：A

. 2016. 07. 073

基于MapReduce的K-means聚类算法的优化

孙玉程，李媛媛，陆勇

(常州大学信息科学与工程学院，江苏常州2131)

摘要：针对传统的聚类算法初始中心点的选择非常依赖，容易产生局部最优而非全局最优的聚类结果，同时难以满足人

们对海量数据进行处理的需求等缺陷，提出了一种基于MapReduce的改进K-meanS聚类算法。该算法结合系统抽样方法得到具有代表性 的样本集来代替海量数据集；采用密度法和最大最小距离法得到优化的初始聚类中心点；再利用Canopy算法得到粗略的聚类以降低运 算的规模；最后用顺序组合MapReduce编程模型的思想实现了算法的并行化扩展，使之能够充分利用集群的计算和存储能力，从而适应 海量数据的应用场景；文中对该改进算法和传统聚类算法进行了比较，比较结果证明其性能优于后者；这表明该改进算法降低了对初始 聚类中心的依赖，提髙了聚类的准确性，减少了聚类的迭代次数，降低了聚类的时间，而且在处理海量数据时表现出较大的性能优势。

关键词：K均值算法；抽样；Canpy算法；最大最小距离法

Optimization of K-means Clustering Algorithm Based on MapReduce

SunYuqiang，LiYuanyuan，LuYong

2131，China)Abstract： To deal with the problems that traditional K-means clustering algorithm is very dependent on the selection of the initial points， being prone to clustering result of local optimum rather than global optimum，and it is mounts of data，an improved K-means clustering algorithm based on MapReduce is proposed. The algorithm combines systematic samplingmethod to get a representative sample set which s used to replace the massive data set； and uses density method and Max-Mirn distance meth­od to get the optimal rnitial clustering centers； and adopts Canopy algorithm to get a rough clustering which can reduce the computational scale； and finally employs the klea of sequential composition of MapReduce programmrng model to realize the parallel extension of the algo­rithm， which can make full use of the computing and storage capacity of the cluster, in order to adapt to the application of massive data. The improved algorithm is compared with the traditional clustering algorithms in this paper，and the comparative results show that the perform­ance of improved algorithm s better than the latter. The experiments show that the improved method reduces the dependence on the rnitial cluster centers and also reduces the number of kerations of clustering and the clustering tme. Furthermore t shows greater performance ad­vantage rn dealing with massive data.

Keywords： K-means clustering algorithm； sampling； Canopy algorithm； Max-Mm distance method

(School of Information Science^Engineering, ChangZhou University，Changzhou

〇引言

随着数据规模的爆炸性增长，传统的数据挖掘工作在处理 大规模数据时会出现用时过长、存储量不足等缺点。云计算的 提出将这些问题迎刃而解，它是一种基于互联网的计算，是分

布式计算、并行处理和网格计算的进一步发展。由Google提 出的MapReduce编程框架[1]是云计算中代表性的技术，主要 用于海量数据的并行计算。已有多种数据挖掘算法在MapRe­

duce 计算模型的基础上被实现了，而聚类是在数据挖掘中运

理。针对K-means算法的特点以及不足，很多学者提出了相 应的改进K-means算法。邓海等人[3]提出了基于最近高密度 点间的垂直中心点优化初始聚类中心的K-m

eans聚类算法；

王玲等人[4]提出一种密度敏感的相似度度量的方法；马帅等 人[5]提出了一种基于参考点和密度的快速聚类算法。这些研究 通过不同的方法解决了算法对初始中心敏感的问题，但却增加 了算法的复杂度。其他的例如毛典辉等人[]提出了改进的

Canopy和K-means相结合的算法；虞倩倩[7]等人提出了聚类 的蚁群优化算法；马汉达等人[]提出了基于粒子群算法 (PSO)的K-mas算法；贾瑞玉等人[]提出了并行遗传K-

means聚类算法，都是结合一些成熟的算法来改进K-means聚

用比较广泛的一种算法。

K-means算法是一种典型的基于划分的聚类算法[2]，该算 法简单高效，运用于科学研究的各个领域。但是它对初始聚类 中心的选择非常敏感，不能有效地对大规模数据进行聚类处

类算法，虽然在少量数据环境下能够显著提升K-means算法 的性能，但却因为额外的组件增加了算法的复杂性，无法适应 海量数据的处理需求。因此，本文提出了一种基于MapRe­

duce 的高效 K-means 并行算法， 其结合了抽样方法进行预处

收稿日期=2016-01-19； 修回日期：2016 - 02 - 29。

基金项目：国家自然科学基金项目（11271057,51176016);江苏省自 然科学基金项目（BK2009535)。

作者筒介：李媛媛（1991-)，女，江苏盐城人，硕士研究生，主要从并 行计算、数据挖掘等方向的研究。孙玉强（1956 -)，男，河南人，教授，硕士研究生导师，主要从事并行 计算、软件工程等方向的研究。

理以减少数据量；通过密度思想对初始中心点优化提高聚类准

确性；结合其他算法降低计算规模；再通过MapReduce分布 式并行模型提高运行效率。实现的过程主要有4个子任务：1) 抽取样本；2)计算样本初始聚类中心点；3) Canopy划分； 4) K-means迭代。通过实验结果得出，此改进算法在处理海 量数据时可以体现出更大的优势。

第7期孙玉强，等：基于MapReduce的K-means聚类算法的优化

• 273 •

1背景

MapReduce 简介

MapReduce是一种分布式并行编程模型，数据被存储在

取得最大值时，需求解的最优初始聚类中心点就为前k个记录 值，同时下一轮Canopy的区域半径可设为T

Canopy算法初始值设置的盲目性和随机性。

1.4

Canopy 算法

Canopy算法[2]的思想是使用一种代价低的相似性度量方

i=A

1. 1

«，避免了

分布式文件系统（distributed file system，DFS)中，以键一值 对〈

Vl>

key，value>

的形式来表示数据。MapReduce的具体步骤

Split又分成一批键值对〈K

是：先将数据切割成Split，对

传给M

ap

1,

函数；M

ap

函数对每个键值对进行处理后形成

法，快速粗略地将数据划分成若干个重叠子集，每个子集可以

看成是一个簇。Canopy算法基本流程[13]如下：

1)设 置阈值Ti，T2,其中Ti> T2;2)

新的键值对〈K

2, V2>，并把K2值相同的进行汇总，输出

从数据集中取得一个数据对象，构建初始Canopy，

中间结果〈

K

2，list〈V2>>; Reduce函数对M

ap

函数输出

的中间结果做相应的处理后得到键值对〈K3, V3>。MapRe­

duce 的操作流程如图 1 所示[10] 。

图1

Mapreduce的操作流程图

1.2

密度思想

在一个大规模的数据对象空间中，低密度区域的数据对象

点一般划分着高密度区域的数据对象点，通常所说的噪声点或 孤立点就是这些低密度区域的点。如果在进行聚类分析时，这 些噪声点或孤立点被选为初始聚类中心，就会造成聚类不理想 的结果。因此，初始聚类中心的选取应该集中到高密度区域以 排除孤立点的干扰。为了有效地排除数据样本中存在的噪声点 对象和孤立点对象，可以通过引入高密度点的概念来处理。

定义1高密度点：取数据集中的数据对象％为中心点， 计算此中心点在邻域半径8内包含的样本个数，若样本个数不 少于常数Minds则该中心点就被称为高密度点。其中^的取 值需结合输入的数据对象集，将其取为〃个数据样本间距离均 方根的一半，公式如下：

其中：||%—； ||为公式（2)的欧式距离Aw

)。

1.3最大最小原则

为了避免初值选取时出现的聚类中心过于邻近的情况，最 大最小原则可以用来选取尽可能远的数据对象作为初始聚类中 心。“最大最小原则”11]的算法描述如下：

1) 从n个数据集{叉1，叉2,…中随机选取一个样本 作为第一个初始聚类中心点G;

2)

在剩余的数据对象集中找到距离C1最远的点，作为第 二个初始聚类中心点G;

3) 分别计算剩余的数据对象集到已有的个聚类中心之间的距离，取最小距离的最大者：二max { rnn {D(7，1)，D0.，2)，…，D0v) }

}，J =

1，2，…，n，则第 z_+1 个初

始聚类中心点为Cz+1=;;

4)

用来表示乃(汁1)变化幅度的深度指标吵认（）可以 通过边界识别的思想进行引入，其定义为：D吵认（々）=

I

A

卜1) I十I A々十1)一 A々）|，当深度值Depth (k)

从该数据集中删除该数据对象；3) 从剩余的数据集中取出一个数据对象，

计算其与所的有Canopy中心之间的距离，如果该数据对 象与某个Canopy中心的距离在乃内，则将该对象加入到这 个

Canopy中，如果该对象与Canopy中的某个Canopy中心的

距离小于T2，则当该数据对象与所有Canopy中心的距离计算 完成后，将其从数据集中删除，如果该数据对象没有加入到任

何Canopy，则构建一个新的Canopy;

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

2 K-means算法介绍和分析

2. 1

K-means算法思想

K-means算法流程[14]： 1

)首先从n个数据对象中随机选

取々个初始聚类中心点；2)对于剩下的其它数据对象，分别 求它们与这々个聚类中心的欧式距离（相似度），将它们分配 给与其欧式距离最小（相似度最大）的聚类；3)计算新的聚 类中心（聚类中所有对象的均值）；4)不断重复步骤2)和3) 这一过程直到准则函数开始收敛为止。

1 欧式距离公式如下 ：D(l,j)=槡 I xa — X11 I 2 1* +| X2 — Xj2 | 2 +. . . + I x狆— I 2

(2其中：（=(xz1，x2，. . X狆）1 = (x^，x犼2，. . X狆）；它们分别表示一个p—维数据对象。

2)均方差准则函数

犽犈=| p — m, 12

(3)

(=1 pec犻其中：犈为数据集中所有数据的均方差之和；p为数据对 象空间中的一个点；为聚类C(的均值狆和m(都是 的）。

2. 2

K-means算法的不足及其改进

1) 传统K-means算法不能有效处理大规模数据的聚类操

作。而基于MapReduce的分布式并行计算模型，将一个大型

数据切分成多个小数据模块的形式，分配给多台计算机集群进

行分布式计算，与传统的单机运行平台相比，加快了总体的运

行速率，减少了执行时间。

2) 传统的K-means算法通过完全随机的策略对初始聚类中心点进行选取，不能确保聚类结果的准确性，更不能有效处 理海量数据。可以通过抽样方法对初始数据进行预处理操作，

得出有效样本集合。再结合密度思想和最大最小原则求得样本

集的初始聚类中心。在高密度区域选择初始中心点可以排除噪

声点和孤立点的干扰，而最大最小原则可以避免在高密度区域 选取的中心点过于邻近。

点• 274 •计算机测量与控制

Map

第24卷

3)传统的K-means算法在比较数据对象与聚类中心的距 离时，计算了全局对象与中心点之间一一对应的距离，虽然在 一定程度上确保了聚类的效果，但是总体上降低了算法的效 率，而且不能适应大规模数据的聚类处理。对此，引入了 Canopy (华盖）的思想，每次只比较落在同一 Canopy内的对 象与相应中心点之间的距离，通过减少比较次数大大降低整个 聚类的运行时间[13]。实验结果表明，该策略在处理大规模数 据时，与传统方法相比，其收敛速度更快。

函数：

每个M

ap

1) 读取数据G和抽样概率Pi，利用仏进

抽样；

2)将 所有数据作为value，为它们指定相同的key，形成 中间键值对；

Reduce 函 数：

1) 将中间键值对shuffle到同一 Reducer上;2) 输出样本数据集5；

3.2

3改进K-means算法的并行化

改进的K-means算法思想：首先采取系统抽样，得到一

计算样本初始聚类中心点算法2：高密度点生成的并行化。输入：样本集5。输出：高密度点集H

Map 函 数：

D

3. 2.1计算高密度数据集

个具有较少数目并能代表全局数据对象的样本集合；再运用密 度法和最大最小距离法相结合的方法求得样本集合的最佳初始

聚类中心；最后利用Canopy算法对全局数据对象进行粗略划 分，以改进K-means算法。一方面，该算法可以通过获得优 化的初始聚类中心来提高聚类结果的精确度；另一方面，该算 法能够智能的降低数据比较的次数。最后，将改进后的算法运 用于MapReduce的并行计算模型中，其基本流程如图2所示。

。

1)每个M

ap

读取样本集S，计算每个样本点^与其余样

本点之间的距离Aw)；

Reduce 函 数：

()根据公式（）计算邻域半径心并统计到每个样 本点％距离小于^的样本个数；

2)读取密度阈值M

inds，若个数大于Minds，则把该

D

点定义为高密度点，得到高密度点集合H3.2.2计算优化初始中心点

算法3：样本中心点生成算法。

Map

。

函数：

D

输入：高密度点集H；

m^Z；

输出：中心点的初始集合Q。

()设置初始中心点的集合，Q=()设置迭代次数，W

据规模N)；

hfe

々〈sqrt (N)(当前节点数

()z/集合Q为空，求数据集V (当前节点数据集

VV

)中密度最大点，并保存该点至集合Q； W■^求数据集 中数据点与集合Q中数据点的距离最小值中最大者，并

保存该点至集合Q；

Reduce 函 数：

输入：各节点中心点的初始集合Q= {兑，Q，…，

a

}；

输出：样本中心点的最终集合^以及半径了1；

=Count (Q

3.1抽取样本

系统抽样主要将在H

(1)求取集合Q的数据总量，N

DFS

)；

上存储的spUt文件块进行规则

()设置迭代次数，W

hfek〈

sqrt (N)；

设计与文件读取，设每个部分抽样概率为^，则我们首先在 Map阶段对每个文件块的数据量大小以及文件行数进行预估， 顺序读取文件的前行，并指定为相同的key值传到同一个

Reducer上，在Reduce阶段对每个块的样本数据合并，得到

()求数据集中数据点之间距离最小值中最大者，并保存 该点至集合Q7 ；

(4)求取集合的数据量rn = Count (Cy)；

()

while j

〈rn，求取集合中Depth (々）最大值并输

最终的抽样结果。

指定参数〇〈e〈1来控制样本大小，设

n

为数据集大小，

出了1，同时将集合C7前々个点赋值至集合^。

3. 3 Canopy 划分

算法4： Canopy划分算法。

Map 函 数：

则通过概率^ = 1/ (%2)对整个数据集进行系统抽样，可以 得到均勻的样本。算法1描述了利用MapReduce模型进行系 统抽样（RS)的过程。

算法1:系统抽样算法。输入：初始数据集G;输出：样本集S。

输入：初始数据集G；

输出：标注对应Canopy的数据集C。

()读取样本中心点的最终集合^以及半径了：，计算初 始数据集与样本中心点之间的距离D；

第7期孙玉强，等：基于MapReduce的K-means聚类算法的优化

• 275 •

(2)当_0< = 7\\，则标注该数据点属于对应的Canopy， 并将结果输出。

3. 4 犓-means迭代

该阶段的主要任务是进行精确的聚类计算，其算法流 程为：

算法5: K-Means算法。

输人：标注对应Canopy的数据集C;输出：K中心点集合U\"'。

Map

定性；且改进的Canopy-Kmeans算法与传统的随机选择聚类中 心的K-m

ans

算法相比，表现出了更好的性能优势。但在处理

海量数据时，若用改进Canopy-Kmeans算法，聚类迭代次数会 增加，甚至会造成内存不足。所以提出了这种折中的用样本数 据初始聚类中心代替全局数据初始聚类中心的聚类算法。

实验二：验证改进的K-means算法的有效性。实验说明：用随机产生的记录数来验证方法的有效性，记 录数n (单位：万）分别是1、10、100,环境：单机伪分布条

函数：

1)

集合^作为初始K中心点集合，LT=

件下，聚类方法同上，聚类个数为100时结果见表2。

表2单机下的聚类结果读取样本中心点的最终集合^，将样本中心点的最终

nM丁

2)

通过M

ap

函数比较已标注的输人数据点与对应中心点

的距离，输出当前数据点及对应最近距离的中心点编号；

Reduce 函数：

1)

通过Reduce函数将同一中心点下的数据点归并，计算

均值并将结果输出作为新的中心点；

2) 判断准则函数是否收敛，若收敛则终止程序，否则进 行下一轮MapReduce的迭代。

4实验结果

本实验在Hadoop分布式集群平台上对多组测试数据进行

了仿真测试[15]，传统的K-means算法K：任意选取是个聚类 中心点后再用K-m

eans算

法进行聚类；改进的Canopy-

Kmeans算

法C

K

：首先结合最大最小原则计算出初始k个

Canopy中心点，利用各个Canopy中心点对数据集进行粗略地 Canopy聚类，再结合K-means算法对每个Canopy类进行精确

地聚类；高效的 DMCanopy-Kmeans (Canopy-KmeansCluste-

ring Algorithm

based on Density Method and Max-min Distance

八lgorithm)算法DMCK

： 1)结合密度法和最大最小距离法计

算已有的抽样数据对象的是个初聚类中心C; 2)利用样本聚 类中心C作为全局数据对象的初始聚类中心，结合Canopy算 法进行Canopy划分；3)再利用K-means算法计算出最终的 聚类结果。数据集的记录数为n，聚类个数为^，具体算法为

M

，迭代次数为r，算法执行时间为了。

实验一：验证改进的K-means算法的可行性。

实验说明：采用50条测试数据进行测试，运行结果见

表1。

表1不同聚类算法和不同聚类个数的聚类结果kM丁

K

3. 529. 115

CK2.422. 62DMCK2.522. K

3.022. 216

CK2.421. 92DMCK2.922. 23K

2.422. 037

CK2.521. 78DMCK

2. 5

22. 19

从表1可以得出以下结论，改进的Canopy-Kmeans算法运 行的聚类结果与高效的DMCanopy-Kmeans算法的聚类结果相 比，其迭代次数和运行时间取得了相似的结果，而且保持了稳

K

6. 3

42. 81

1

CK4. 683. 62DMCK3. 540. 35K

8. 2106. 7910

CK3. 0428.94DMCK2. 636. 57K

7. 21 132.51100

CK时间过长时间过长DMCK

2. 5

581.18

通过表2得出以下结论：改进的Canopy-Km

eans聚类算

法在用最大最小原则计算初始聚类中心点时，随着处理的数据 规模的扩大，迭代时间也会随之增长，会导致算法效率变低。 当处理的数据量不断增加时，这种改进的聚类算法将不再适用

于初始中心点的计算。而提出的高效DMCanopy-Kmeans算 法在面对海量数据量时，大大减少了执行的时间，提高了算法 的运行效率和聚类的精度。

实验三：验证改进算法可以并行执行。

实验说明：4台均是装有Centos5操作系统的虚拟机，其 中一台是master，剩余三台是slave，内存512M，硬盘100G， 2.5Ghz双核CPU。数据：使用实验2中数据，在集群平台下 聚类为100时的运行结果见表3。

表3集群下运行结果

nM丁

K

6. 2

49. 18

1

CK2. 450. 82DMCK2. 017. 53K8. 284. 1810

CK2. 5352.83DMCK2. 131. 15K

6. 85.54100

CK4. 34 126. 72DMCK

3. 2

536. 62

表3与表2对比得出以下结论，在同样的条件下，并行化 与串行相比，其操作时间明显是降低的，且提高了算法的运行 效率，进一步体现了海量数据在集群环境下处理的优势。

5结束语

在处理海量数据时，为减少k-m

ans

算法对初值的依赖性，

(下转第279页）

第7期

J requestlJ request2j reque5t3^bagjn D-^ bag-$-•—

00000000

刘欢，等：基于FPGA的多路数据单信道传输方法研究

• 279 •

过内部定时产生等间隔的超时发送请求，满足实时传输的要

求。而且由请求信号和bag_en信号的疏密可知，3路视频已 经完整的复用在了最终的数据流bag中，达到了实时复用的

::1

—I'r

_JL

:麵

目的。

由仿真结果可以看出，数据编码、时分复用打包模块达到 了设计的效果，整个多数据单信道复用的传输方法算法有效可 行，达到了预期的目的。

图7高优先级抢占低优先级传输

4结论

本文所设计的多路数据单信道传输时分复用模块，很好地

解决了多路视频同时传输的问题。尤其是发送请求模块，结合

图8低优先级抢占高优先级

进行数据包的发送，而在不同通道包发送过程中，程序不会去 响应其他通道发送请求，能够达到设想的效果。

最终的发送请求和传输细节可由图9看出。

时间轮片和基于优先级的调度算法，在满足各通道实时传输的 条件下，为尽可能多的时分复用信道提供一种可靠方法，理论 上可以复用接近一个串行通道的传输极限，对于2. 5Gbps的 信道，最多可以复用接近2GbPs的传输数据，是一种经济、 实用的图像数据传输方式，可以应用于多路视频同时传输 系统。

参考文献：

[1]吴贺.多通道数字光电转换系统的设计与实现[D].西安：西

安电子科技大学，2013.

[]肖儿良，韦荣明，颜文超.基于Aurora及CamemLmk的高速数字

图像传输[].信息技术，2015 (4): 94 - 97.

[]姚七栋，张春玉.CRC校验及其软件实现[].现代电子技术，

2006 (13)： 67 - 68.

[4]陈忠平，高金定，高见芳.基于Quartus II的FPGA/CPLD设计

与实践[M].北京：电子工业出版社，2010.

[]王诚，蔡海宁，吴继华.AltemFPGA/CPLD设计（基础篇）

[M].北京：人民邮电出版社，2011.

图9信道发送综合效果图

在图中，当视频信号处于消隐期的时候，模块依然可以通

(上接第275页）

我们详细探讨了初始聚类中心的优化选择问题，并提出全新的

DM Canopy-Kmeans算法。为提高算法的运行效率，在Ma­

pReduce 的平台下对改进聚类算法进行实现。并通过实验对其

进行对比分析，验证了基于并行模型下的改进算法更优于传统 的算法，提高了算法的执行效率。下一步的主要工作是进一步 改进抽样数据的样本质量，可以用来更精确地代表全局数据 对象。

参考文献：[1] Dean J， Ghemawat S. MapReduce ： simplified data processing on

large clusters [J]. Communications of the ACM， 2008，51 (1)： 107-113.

[2] Han J，Kamber M. Data Mining： Concepts and Techniques [M].

Fan Ming， Meng Xiaofeng， translation. 2 edition. Beijing ： Me­chanical Industry Press，2007.[3] 邓海，覃华，孙欣.一种优化初始中心的K-means聚类算

法[].计算机技术与发展，2013, 23 (1)： 42 - 45.[4] 王玲，薄列峰，焦李成.密度敏感的普聚类[].电子学报，

2007, 35 (8) ： 1577 - 1581.

[]马帅，王腾蚊，唐世渭，等.一种基于参考点和密度的快速聚

类算法[].软件学报，2003，14 (6)： 10 - 1095.

[6]毛典辉.基于MapReduce的Canopy-Kmeans改进算法[].计算

机工程与应用，2012，48 (27)： 22 - 26.

[7]虞倩倩，戴月明，李晶晶.基于MapReduce的ACO-K-means并行

聚类算法[].计算机工程与应用，2013, 49 (6)： 117-120.[]马汉达，郝晓宇，马仁庆.基于Hadoop的并行PSO-kmeans算法

实现Web日志挖掘[J].计算机科学，2015，42 (6A)： 470 - 473.

[]贾瑞玉，管玉勇，李亚龙.基于MapReduce模型的K-means并行

遗传聚类算法[J].计算机工程与设计，2014，35 (2)： 657 -660.

[10] Isard M，Budiu M，Yu Y，et al. Dryad： Distributed data-parallel

programs from sequential building blocks [A]. Proc. of the 2nd European Conf. on Computer Systems (EuroSys) [C]. 2007 ： 59 -72.

[11] 刘远超，王晓龙，刘秉权.一种改进的K-means文档聚类初值选

择算法[J].高技术通讯，2006 (1)： 11-15.

[2]孙吉贵，刘杰，赵连宇.聚类算法研究[J].软件学报，

2008, 19 (1)： 48-61.

[13] 李应安.基于MapReduce的聚类算法的并行化研究[D].广州：

中山大学，2010.[14] Han Jiawei. Kamber. Data mining： Concepts and techniques [M].

Beijing： Mechanical Industry Press. 2008： 288 -375 (in Chinese).[15] Apache. Hadoop [EB/OL]. [2012-10-10]. http： //hadoop.

apache org