面向大规模数据快速聚类K-means算法的研究

郭占元 林 涛

(河北工业大学计算机科学与软件学院 天津 300401)

面向大规模数据快速聚类K-means算法的研究

郭占元 林 涛

(河北工业大学计算机科学与软件学院 天津 300401)

为进一步提高K-means算法对大规模数据聚类的效率，结合MapReduce计算模型，提出一种先利用Hash函数进行样本抽取，再利用Pam算法获取初始中心的并行聚类方法。通过Hash函数抽取的样本能充分反映数据的统计特性，使用Pam算法获取初始聚类中心，改善了传统聚类算法依赖初始中心的问题。实验结果表明该算法有效提高了聚类质量和执行效率，适用于对大规模数据的聚类分析。

大规模数据 聚类算法 MapReduce Hash样本抽样 Pam算法

0 引 言

聚类分析是数据挖掘领域中的一个重要分支。聚类的基本思想是，同一个簇中的对象是相似的，不同簇中的对象相差较大。典型的K-means算法对初始化的k个中心依赖性很大，若初始中心选择不当，往往会得不到全局最优解，增加算法的迭代次数和运算时间，降低算法的执行效率[1]。

快速确定优秀的初始聚类中心，最终获取全局最优解，提高聚类算法的收敛速度是K-means聚类算法的重点研究内容。文献[2]选取距离最大的两个数据对象作为初始聚类中心，迭代分裂，直到获取k个中心点；文献[3]利用领导者算法将数据分成不同的部分，从中选择初始中心点；文献[4-5]选取位于高密度区域且相距较远的数据对象作为初始中心。上述研究能有效地获取优秀的聚类初始中心，从而提高聚类算法的质量，但算法的时间复杂度较高，无法适应海量数据的聚类要求[6]。

随着数据量的不断增长，串行环境下的聚类算法在执行效率和准确程度上难以均衡两者之间的关系，因此许多研究将传统的聚类算法进行并行实现，从而满足对海量数据的处理要求。MapReduce是处理大规模数据的并行编程框架，利用MapReduce框架进行数据聚类，能有效地提高算法的执行效率，其分布式集群提供的存储与计算能力能够解决庞大的数据规模和复杂的数据类型所带来的问题。因此，基于MapReduce框架面向大规模数据的并行聚类算法[7]逐渐被学者重视和提出。文献[1]基于MapReduce提出一种先抽样再用最大最小距离算法获取初始中心的K-means并行聚类算法；文献[8]结合MapReduce框架，提出了经过多次随机抽样获取优秀初始中心的K-means并行聚类算法；文献[9]对基于MapReduce的K-means并行聚类算法，从通信模式和初始中心方面，提出了改进思路和具体实现。

本文在此基础上，以典型的K-means为研究对象，结合MapReduce并行编程模型，提出一种先利用Hash函数对数据进行样本抽样，然后通过Pam算法获取初始中心的K-means并行聚类方法。

1 相关概念与描述

1.1 基于Hash函数的取样

传统的抽样方法一般采用简单随机抽样[10]，但这种方法具有不确定性，误差方差较大，不能真正反映数据分布的统计特性。特别当数据分布不均匀时，样本不具有对总体数据统计分布的代表性。

基于Hash函数的取样技术是基于传统的分层抽样提出的。利用Hash桶进行分层，将m维立体数据按等概率进行分桶，使得每层(即通过Hash函数构造的Hash桶)的数据特性相近，以较小的计算代价得到分层的效果，然后进行分层抽样，使样本充分反映数据的统计特性，同时该算法具有较好的时间复杂度O(n)。

1.2 各类型变量的近似分布

(1) 对于连续随机变量x，其估计分布函数服从近似正态分布N(μ,σ2)，分布函数为：

(1)

(2) 对于二元变量x，设其状态为0、1。样本中，0状态的个数为n，1状态的个数为m，则其估计分布函数为：

(2)

(3) 对于标称变量x,所抽样本中各状态出现的个数为n1,n2,…,nt，令pi=ni/(n1+n2+…+nt)，则其估计分布函数为：

(3)

1.3MapReduce并行编程框架

MapReduce编程模型是一个简化的并行计算编程模型，自动实现资源调度，屏蔽了底层复杂的细节。MapReduce的核心是Map和Reduce两个函数，它们的功能是将输入的键值对转换成符合要求的。其中，Map端负责分解任务，Reduce端负责合并任务。当所有Map任务成功完成之后，具有相同key的键值对会被发送到同一个Reduce进行合并。

经Map端处理后的，在被发送到Reduce端前，用户可以通过实现Combine函数进行本地合并，从而减少网络的IO操作以及数据的传输量，使MapReduce更加有效。

2 基于MapReduce的聚类优化算法

传统的基于MapReduce框架的K-means算法从数据集中随机选取k个对象作为初始中心，每次迭代启动一个job任务，Map函数计算所有对象到k个中心的距离并将其分配到离它最近的簇，Reduce函数利用均值等方法更新该类的中心值。经过多次迭代，生成稳定的簇中心。这些算法只是将K-means算法迁移到MapReduce框架下，依然存在依赖初始化中心的问题，同时在执行Map/Reduce方法的过程中，也存在通信量过大、可伸缩性较差等问题。

因此，本文结合MapReduce对算法进行优化和改进，利用Hash函数抽取样本充分反映数据的分布情况，使用Pam算法对样本进行聚类，采用实际样本点作为新的聚类中心，避免噪声点和孤立点的影响，从而提高了算法的聚类效果，加快了算法的处理速度。

2.1 基于Hash函数的样本抽样算法过程

(4)

(2) 按照式(1)-式(3)对每维变量进行近似分布估计，可构造如下Hash函数：

H(x1,x2,…,xm)=F(x1),F(x2),…,F(xm)

(5)

易知该Hash函数的取值范围为[0,1]，设要获取n个样本数据，则将该区间n等分：0 =i1

基于Hash函数的样本抽样算法过程如下：

(1) 确定抽样样本容量n；

(2) 按照式(1)-式(3)估计各列分布函数F(x)；

(3) 构造Hash函数如式(5)；

(4) 将所有数据对象分配到这n个桶中；

(5) 随机地从每个Hash桶抽取一定比例的数据，组成一个样本数为n的样本数据集。

2.2 改进算法方案设计

针对传统K-means聚类算法面对大规模数据，算法时间开销大、执行效率低，另外随机选取初始中心，可能会陷入局部最优解，导致聚类结果不准确的问题。本文提出以下改进方案：

(1) 对于K-means的聚类初始化问题，本文采用一种结合Hash函数的样本抽样方法从数据集X中抽取一部分分布均匀的数据集X={x1,x2,…,xn}，然后应用Pam聚类算法获取样本的聚类中心，作为数据集的初始聚类中心。

(2) 针对K-means算法在处理海量数据时效率低下的问题，本文结合MapReduce计算模型，对K-means聚类算法进行并行实现。

(3) 针对传统Pam算法采用全局顺序替换策略，时间复杂度高的问题，利用MapReduce框架并行实现Pam算法。

2.3 改进算法执行流程

改进算法具体过程如下：

1) 计算数据对象的均值、标准差。

2) 根据式(4)确定抽样的样本数量n。

3) 按照上述利用Hash函数进行样本抽样的过程从数据集X中进行样本抽样。

4) 对抽取的样本利用Pam聚类算法进行聚类，从而获取初始中心，过程如下：

Repeat

(1) 计算样本数据集中的每个非中心点xi与各个中心点之间的距离，将其分配给距它最近的第k个中心点，形成多个类簇；

Repeat

(2) 选择样本数据集中一个未被选择的非中心点xi替换当前簇的中心点；

(3) 如果存在某个非中心点代替当前中心点的代价小于0，则用该非中心点替换中心点，形成一个新的类簇；

Until所有非中心点被选择过；

Until没有类簇进行中心点重新分配；

(4) 将稳定的聚类中心记录为C。

5) 将C作为全局初始聚类中心，输入数据集以及相关参数。

6) 运行并行的K-means聚类算法，直到所有类簇稳定，或者达到最大迭代次数，算法结束。

对应算法流程如图1所示。

图1 算法流程图

2.4 算法时间复杂度分析

设N为数据对象数量，k为类别个数，t为迭代次数，w为每个对象的维度，Map节点的个数为m，Reduce的个数为r，抽取的样本容量为n，则串行条件下K-means算法的时间复杂度为O(Nktw)。

3 实验及结果分析

3.1 实验环境

硬件：6台普通PC机，1台作为主节点，其余5台为从节点。其配置均为3.20GHz的4核CPU，500GB硬盘，4GB内存。

软件：操作系统CentOS6.4，Hadoop2.20，Jdk1.7，Eclipse4.42，Hadoop集群环境采用完全分布式模式部署。

3.2 仿真实验与分析

实验数据为UCI机器学习库中的Synthetic-Control数据集，每条数据的维度为60，共包含6个类别。为验证改进算法处理大规模数据的能力，在此基础上构造了data1～data3三组数据集用于聚类，规模分别为600MB、1 200MB、2 000MB。每次实验均取10次实验结果的平均值为最终结果。

3.2.1 实验1：验证改进算法的加速比

实验说明：本实验在节点个数分别为1、2、3、4、5的Hadoop平台上，利用本文算法对data1～data3三组数据进行聚类，运行时间如图2所示。

图2 各数据集在不同节点下的运行时间

由图2可得出以下结论：

(1) 对于同一数据集，随着集群中参与运算的节点个数不断地增多，单个节点处理的数据逐渐变少，从而导致总体的运行时间减少。而且当数据规模相对较大时，算法运行时间的减少幅度更加明显，说明集群的并行化有效提高了算法处理大规模数据的执行效率。

(2) 随着节点个数的增加，运行时间曲线趋于平缓，这是因为当各节点处理的数据量较少时，各节点进行逻辑运算所消耗的时间占总时长比例较小，而MapReduce在启动任务和各节点之间进行数据通信消耗的时间占据了一定比例，综合两者导致总时长差距不明显。

图3 各数据集在不同节点下的加速比

由图3可知：随着节点数目的增加，算法的加速比接近线性增长，说明本文提出的改进算法具有良好的可扩展性，能很好地适应于并行化。

3.2.2 实验2：验证改进算法的有效性

实验说明：为验证算法的有效性，在节点数为5的集群环境下，利用基于MapReduce的K-means并行聚类算法(算法1)、文献[1]提出的改进算法(算法2)、文献[8]提出的改进算法(算法3)和本文提出的改进算法分别对data1、data2、data3数据集进行聚类实验。记录四种算法的运行时间(单位：分钟)如表1所示，算法执行的迭代次数如表2所示。

表1 各算法运行时间对比表

表2 各算法迭代次数对比表

综合表1、表2可得出以下结论：

(1) 当数据集为data1时，数据记录相对较少，各算法运行时间差距不大，这是因为经过优化后的算法虽然选取了优秀的初始聚类中心，减少了算法的迭代次数，但同时也消耗了时间。随着数据规模的增大，通过样本获取初始中心消耗的时间占总时长的比例逐渐减少，算法本身成为影响执行时间的主要因素，算法运行总时长的差距也相应变大。

(2) 在运行相同条件下，算法2所用时间最长，由于其获取初始中心时，采用串行实现的最大最小距离算法，时间复杂度较高，增加了时间的开销。而本文提出的改进算法，无论是迭代次数还是执行时间，与其他算法相比，都有所减少，说明其能快速有效地获取优秀的初始聚类中心，从而缩短算法的运行时间，提高算法的执行效率。

3.2.3 实验3：验证改进算法的正确性

实验说明：为验证算法的正确性，利用本文提出的改进算法分别对不同的数据集进行聚类。实验数据为UCI机器学习库中的Synthetic-Control数据集、Iris数据集和Wine数据集。其中，Iris和Wine数据集均包含3个类别，每条记录分别由4个和13个属性构成。本实验在此基础上分别将3个数据集扩充为3百万条记录，取10次实验结果的平均值为最终结果。实验结果如表3所示。

表3 各算法准确率对比表 %

由表3可知：同一数据集下，算法2、算法3和本文算法的准确率相对于算法1都有所提高，说明通过获取优秀的初始聚类中心，提高了算法的聚类效果。而本文算法的聚类效果更佳，说明利用Pam算法获取聚类中心，有效降低了异常点的干扰，从而提高了算法的准确率。

3.2.4 实验4：验证改进算法的稳定性

实验说明：为验证算法的稳定性，在节点数为5的集群环境下，分别利用四种算法对data3数据集进行聚类。记录四种算法10次聚类结果的准确率如图4所示。

通过图4可以得出以下结论：

本文算法准确率曲线走势相对平稳，而其它三种算法准确率曲线偏离中心线幅度较大，其中算法1偏离程度最为严重。由于算法2和算法3在获取聚类初始中心时，随机取样的不稳定性导致选择的初始聚类中心与实际的聚类中心存在一定偏差，但其通过选择优秀的聚类中心，改善了中心点对聚类结果的影响，所以两者的准确率曲线波动范围与算法1相比相对较小。而本文算法利用Hash函数进行样本抽样，客观地反映了数据的分布特性，获取的初始中心与数据集的聚类中心更接近，与其他三种算法相比，表现出更高的稳定性和准确性。

图4 各算法10次实验结果的准确率

4 结 语

本文主要通过Hadoop平台上的MapReduce框架实现了针对大规模数据进行快速聚类的优化算法，实验结果表明：这种改进的方法较快地选取了优秀的初始聚类中心，降低了对初始聚类中心的依赖性，提高了大规模数据集下聚类算法的正确率，加速了聚类的收敛速度。并行环境下，能适应海量数据的快速聚类。下一步工作主要对集群的参数配置进行实验调优，以提高系统负载均衡的能力和鲁棒性。同时聚类中心k值的自动确定，是以后的研究重点。

[1] 韩岩,李晓.加速大数据聚类K-means算法的改进[J].计算机工程与设计,2015,36(5):1317-1320.

[2] 陈光平,王文鹏,黄俊.一种改进初始聚类中心选择的K-means算法[J].小型微型计算机系统,2012,33(6):1320-1323.

[3]KumarKM,ReddyARM.AfastK-meansclusteringusingprototypesforinitialclustercenterselection[C]//InternationalConferenceonIntelligentSystemsandControl,2015:1-4.

[4] 谢娟英,王艳娥.最小方差优化初始聚类中心的K-means算法[J].计算机工程,2014,40(8):205-211.

[5]LinK,LiX,ZhangZ,etal.AK-meansclusteringwithoptimizedinitialcenterbasedonHadoopplatform[C]//InternationalConferenceonComputerScience&Education,2014:263-266.

[6] 张靖,段富.优化初始聚类中心的改进K-means算法[J].计算机工程与设计,2013,34(5):1691-1694,1699.

[7] Kumar A,Kiran M,Prathap B R.Verification and Validation of Map Reduce Program model for Parallel K-Means algorithm on Hadoop Cluster[C]//International Conference on Advanced Computing and Communication Systems,2014:1-8.

[8] 王永贵,武超,戴伟.基于MapReduce的随机抽样K-means算法[J].计算机工程与应用,2016(8):74-79.

[9] 牛新征,佘堃.面向大规模数据的快速并行聚类划分算法研究[J].计算机科学,2012,39(1):134-137.

[10] 王秀华.基于随机抽样的加速K-均值聚类方法[J].计算机与现代化,2013(12):27-29.

RESEARCH ON FAST CLUSTERING K-MEANS ALGORITHM FOR LARGE-SCALE DATA

Guo Zhanyuan Lin Tao

(SchoolofComputerScienceandEngineering,HebeiUniversityofTechnology,Tianjin300401,China)

To further enhance the efficiency of K-means clustering algorithm for large-scale data, combined with MapReduce computational model, a parallel clustering method is proposed, which uses Hash function to extract samples and then obtains initial center by Pam algorithm. The sample extracted by Hash function can fully reflect the statistical characteristics of the data, using Pam algorithm to obtain the initial clustering center, and improve the traditional clustering algorithm to rely on the initial center of the problem. It uses the Pam algorithm to obtain the initial clustering center, and improves the problem of that the traditional clustering algorithms rely on the initial center. The experimental results show that the proposed algorithm can effectively improve the clustering quality and efficiency, and is suitable for the clustering analysis of large-scale data.

Large-scale data Clustering algorithm MapReduce Hash sampling Pam algorithm

2016-06-16。天津市科技支持计划科技服务重大专项(14ZCDZGX00818)。郭占元，硕士，主研领域：数据挖掘，云计算与大数据处理。林涛，教授。

TP311

A

10.3969/j.issn.1000-386x.2017.05.008