- 1 -
中国科技论文在线
基于Hadoop的K-Means聚类算法优化与实
现
陈萍，何健伟*
作者简介：陈萍(1968-),女,高级工程师,无线通信,计算机网络仿真
（北京邮电大学信息与通信工程学院,北京,100876） 5
摘要：本文针对传统 K-Means 聚类算法不适合海量大数据挖掘，并且对异常离群点数据非常
敏感，结合 Hadoop 云计算平台以及 MapReduce 并行编程框架，借鉴 K-Medoids 聚类算法对
离群点数据不敏感的特点，提出了在 Hadoop 平台下改进的并行 K-Means 聚类算法，命名为
HK-Means 聚类算法。其中，map 函数的主要任务是计算数据集合中每条数据记录到聚类中心10
点的距离并确定其所属聚类簇，reduce 函数主要任务是完成更新聚类中心点。通过实验，
验证了 HK-Means 聚类算法确实能降低时间复杂度，且表现出很好的稳定性。
关键词：K-Means 算法;大数据;Hadoop;并行;
中图分类号：TP391
15
Optimization and Realization of K-means Clustering
Algorithm Based on Hadoop
Chen Ping, He Jianwei
(Beijing University of Posts and Telecommunications,Advanced Network
Laboratory,Beijing,100876) 20
Abstract: Combined with hadoop cloud computing platform and MapReduce parallel
programming framework, refered from K-Medoids clustering algorithm not sensitive to the outlier
data, knowing the traditional K-Means clustering algorithm not suitable for large mass of data
mining, this paper proposes an improved parallel K-Means clustering algorithm based on hadoop
and name as HK-Means clustering algorithm. Design Map function to calculate the distance of 25
each data record to each clustering center point and make them belong to one. Design Reduce
function to update the clustering center points. Through the experiment, prove that compared with
the traditional serial algorithm, HK-Means algorithm can indeed reduce the time complexity and
also has good stability.
Key words: K-Means algorithm; big data; Hadoop;parallel; 30
0 引言
聚类分析根据在数据中发现的描述对象及其关系的信息，将对象数据分组。无论是旨在
理解还是使用，聚类分析都在广泛的领域中扮演着重要的角色。这些领域包括：心理学、生
物学、统计学、模式识别、信息检索和机器学习[1]。由于计算机技术的飞速发展，互联网时35
代渗透到社会生活的各个层面，人类每天产生的数据规模越来越大，传统的聚类算法已经很
难在实时性和效率上给出优秀的解决方案[2]。
Hadoop
[3]源于 Google 公司在 OSDL 发表的 MapReduce 和 Google File System(GFS)两大
论文，是由 Apache 基金会开发实现的支持分布式应用程序的软件框架。它能够使应用程序
由成千上万台独立的计算机处理 PB 级数据的工作，并且具有高度容错的特点。本文基于40
Hadoop 云计算平台，实现了 K-Means 聚类算法的并行化，并改进了算法对离群数据敏感的
缺陷。
- 2 -
中国科技论文在线
1 MapReduce 编程框架
MapReduce 是一个通过将处理流程切分为一组独立运行的任务以便处理大数据的并行45
编程框架。它包含两大操作，map 映射与 reduce 规约。在执行 map 映射时，主节点把原始
输入数据集切分成许多大小相同的独立数据片并分配给一定数量的数据节点，每个数据节点
处理分配的独立数据片并映射成 key-value 键值对。在执行 reduce 规约时，数据节点将 map
映射生成的中间结果作为输入，规约出结果集并输出到 HDFS 上。
50
2 K-Medoids 聚类算法
K-Medoids 聚类算法的一般步骤如下：
输入：数据集合大小为 n 的原始数据对象，设定聚类簇数目 k；
输出：生成 k 个聚类簇
步骤： 55
1） 在数据集合中任意找出 k 个数据点对象表示分组聚类中心点；
2） 在剩余的数据对象中，对每个对象比较离 k 个中心点的距离，选择最近的聚类中心点，
归为同簇点集；
3） 在同一簇中，顺序选取每一个非中心点 x 对象代替原来簇中心点对象；
4） 通过计算簇中所有点到 x 对象的距离平方和 S，也就是 SSE； 60
5） 倘若 S 比之前的结果小，则用 x 替换原来的簇中心点，否则不作变化；
6） 重复(2)(3)(4)(5)步骤，直至最后 k 个中心点运算始终保持不变。
很明显，因为 K-Medoids 算法在重新确定中心点时计算了每个簇中所有点到原始中心点的平
方和，且选择最小的 SSE 作为新的中心点，所以 K-Medoids 算法对离群点数据不敏感。
65
3 HK-Means 聚类算法实现
传统 K-Means 聚类算法一般步骤
输入：包含 n 条原始样本数据的数据集合{x(1)，x(2) x(3) ，… ，x(n) }，每个 x(i)∈Rn，聚类簇
数目 k；
输出：k 个聚类簇。 70
步骤[4]：
1) 首先随机选择 k 个数据对象，将它们选作初始聚类中心点；
2) 对其余记录的每一个点，计算到各中心点的距离，并将其归类到最近的中心点；
3) 对归类后的簇，计算其各个维度的平均值，作为新的中心点；
4) 重复 2)，3)步直到新中心点收敛于初始给定的阈值。 75
K-Means 聚类算法的时间复杂度为 O(I*K*m*n)，其中 I 是收敛所需要的迭代次数，n
是数据集合的元素个数，m 是数据的属性维度，K 表示均值中心点数量。
HK-Means 聚类算法实现思路
HK-Means 算法在 MapReduce 上运行时需要解决信息如何共享的问题，有两种解决方
案：1、利用文件存储；2、利用共享变量集。经过多方面考虑，并结合并行 k-means 聚类算80
- 3 -
中国科技论文在线
法的具体实现过程，决定使用文件存储-利用 2 个中心点文件，1 个存放上一轮迭代原始的
聚类中心点文件 oldFile，1 个用来保存经过 MapReduce 计算输出的新的聚类中心点文件
newFile
[5,6]。
1、 在执行 Map 任务时，读取 oldFile 文件，得到 k 个聚类中心点对象；
2、 Reduce 函数在处理完成获得新的聚类中心点对象时，存入 newFile 文件中； 85
3、 在主程序中，读取并比较 oldFile 和 newFile 的聚类簇中心点，如果 newFile 文件的
聚类簇中心点与 oldFile 的中心点仍然相差较大，则在下一轮迭代时，用 newFile
替换 oldFile 文件，否则 newFile 文件的聚类中心点接近或小于设定的阈值，算法停
止，输出最终结果。
图 1 说明了 HK-Means 的实现过程。首先执行的是原始输入数据文件的切片，将原始大90
文件切分为 D1、D2、…、Dn 的相同大小 n 维小数据片，通过 NameNode 主节点，将 n 个数
据片传送到分配的数据节点中。数据计算节点执行 Map 任务时，提取出分配的数据块，将
每个数据对象映射到距离 k 个聚类中心点最近的簇团中，如图中的 centroids（Di）；执行
Reduce 任务时，归并中间结果键值对，生成新的 k 个聚类中心点 global centroids，如果与之
前的聚类中心点变化小于阈值，则算法停止，否则更新新的聚类中心点，重新迭代。 95
数据集
数据块 数据块数据块 数据块 数据块输入
Map Map Map Map MapMap阶段
Reducer Reducer ReducerReduce阶段
初始聚类中心点
中心点初始化
读取中心
点
变化是否
大于阈值
是，则新的中心点替换原始中心点
否
聚类结果 聚类结束，输出结果
当前聚类中心
生产新的聚类中心点
图 1 基于 MapReduce 的 HK-Means 算法流程
Map 函数的设计：
Map(NullWritable DataSet， Text lnRecord){
计算数据记录到每个中心点的距离； 100
比较上述距离；
将该数据标记到最近的那个中心点所属的簇；
将<数据所属簇，数据>键值对映射到中间文件；
}
Map 函数操作的时间复杂度为 O(k*n)，k 代表聚类簇的数目，n 代表数据对象集合的元素总105
- 4 -
中国科技论文在线
数[7]。
Reduce 函数的设计：
Reduce(NullWritable DataSet，Iterator<NullWritable> Datas){
for(对于 key 相同的所有记录){
求每个记录到该 key 其他记录的均方和； 110
选择上述均方和中最小的值对应的数据；
将该数据点作为聚类簇中心点；
}
更新聚类簇中心点；
} 115
Reduce 函数的任务是对 map 函数生成的聚类簇键值对信息规约，生成新的聚类簇中心点。
算法复杂度大约为 O(n2/k)，k 表示聚类簇中心点数，n 表示数据集合中元素总数[8]。
4 HK-Means 算法实验与结果分析
实验数据为不同花瓣的特征数据，通过 HK-Means 聚类算法的 MapReduce 模型对花瓣120
进行分类，从而得到不同花系的花瓣特征。
软硬件环境
实验中集群所用的机器数量为 9台。1台作为NameNode 主节点，另外 8台作为DataNode
数据节点。每台机器的软硬件配置如下：
网络：千兆以太网； 125
CPU：Intel® Core(TM) i5-2450M @；
硬盘：500G/14400rpm；
内存：4GB DDR3；
OS：red hat ；
Java：_11； 130
Hadoop：；
Hbase：Hbase
单机处理比较实验
本实验设计的实验方案为：在一台机器上运行普通的串行 k-means 聚类算法，记录运算
时间 Tk-means；配置集群，分别在一台、二台、三台、四台、五台计算节点上运行 HK-Means135
聚类算法，并分别记录运算时间 T1、T2、T3、T4、T5。实验所用原始数据为表 1 中前四组数
据。
表 1 单机处理比较实验
数据源 数据大小 Tk-means T1 T2 T3 T4 T5
Example1 144s 154s 130s 141s 147s 143s
Example2 489s 512s 323s 208s 184s 177s
Example3 236MB 2576s 2634s 1545s 1047s 717s 564s
Example4 14035s 14231s 7584s 5049s 3891s 2984s
- 5 -
中国科技论文在线
由表 1 可看出：
1、Tk-means 运行速度一直比 T1（HK-Means 运行在 1 个计算节点）快，消耗的时间相对140
少。这是因为 T1 是 HK-Means 运行在一个节点所消耗的时间，由于在 MapReduce 并行计算
框架下，HK-Means 每次迭代都要重新启动一个新的 job，在这个启动的过程中需要
NameNode 主节点和 DataNode 节点之间的相互通信，通信花费的时间代价使得 HK-Means
在单机上处理的时间大于串行 k-means 聚类算法[9]。
2、当随着数据量的增大，且 HK-Means 运算的节点数增加时，k-means 聚类算法的运算145
速度明显比 HK-Means 慢，且与运算节点数量的增加成正比。这是因为多个计算节点处理一
个任务，各节点的底层通信所花费的时间相对于 HK-Means 所带来的速度提升可以忽略，因
此 HK-Means 的处理速度比 k-means 快，且与节点数量的增加成正比。
集群加速比性能实验
在并行计算领域，加速比常常用来表示并行算法与对应的串行算法执行的速度比较。本150
加速比实验主要考察在增加计算节点时，系统处理相同规模的数据时所消耗的时间比值。
实验数据仍采用 小节所使用的数据，实验结果如图 2。
图 2 HK-Means 聚类算法的加速比分析图
从图 2 加速比实验结果中可以看出： 155
1、对于小规模数据集合而言，运算处理器的增加，不一定会提高运算的效率，如
Example1 所示；
2、增加计算节点，会导致计算节点之间底层的相互通信的时间增加，使整体运算的效
率受到影响[10]；
3、随着输入数据集合规模的增加，加速比越来越理想，这是因为计算节点的增加虽然160
会消耗一定的通信时间，但是和计算处理数据带来的速度提升来说，这点时间消耗可以忽略。
5 结束语
本文给出了基于 Hadoop 云计算平台的 K-Means 聚类算法并行实现与优化，通过实验比
较了传统的串行 K-Means 算法与本文提出的 HK-Means 算法在处理海量大数据时的时间效165
- 6 -
中国科技论文在线
率。实验结果表明，在大规模数据量下，HK-Means 算法能显著提高运算效率，并且具有接
近理想的加速比效果。在大数据时代，相对于传统 K-Means 算法，HK-Means 算法具有更实
际意义。
[参考文献] (References)170
[1] 段明秀.层次聚类算法的研究与应用[D].长沙:中南大学,2009.
[2] 钱彦江.大规模数据聚类技术研究与实现[D].成都:电子科技大学,2009.
[3] Lammel 's MapReduce Programming Model - Revisited[J].Science of Computer
Programming,2007,68(3):208-237.
[4] Han Jiawei,Kamber M.数据挖掘概念与技术[M].北京:机械工业出版社,2011:60-74. 175
[5] 刘鹏.实战 Hadoop-开启通向云计算的捷径[M].北京:电子工业出版社,2011:60-74.
[6] Srirama S N, Jakovits P, Vainikko scientific computing problems to clouds using
MapReduce[J].Futrue Generations Computer Systems,2012,28(1):184-192.
[7] 李建江,崔健. MapReduce 并行编程模型研究综述[J].电子学报,2011,39(11):2635-2641.
[8] 谢桂兰,罗省贤.基于 Hadoop MapReduce 模型的应用研究[J].软件天地,2010,29(8):4-7. 180
[9] 李远方 ,邓世昆 ,闻玉彪 . Hadoop-MapReduce 下的 PageRank 矩阵分块算法 [J].计算机技术与发
展,2011,21(8):6-9.
[10] 张圣.一种基于云计算的关联规则 Apriori 算法[J].通信技术,2011,44(6):141-143.
