基于抽样和最大最小距离法的并行K-means聚类算法

刘 燕

(山西大学 商务学院， 太原 030031)

引言

聚类是将物理或抽象的对象分成相似对象集合的过程，簇是数据对象的集合，同一簇中的对象特征相似，而与其它簇中的对象却彼此相异[1]。聚类分析在数据挖掘、模式识别、文本分析、图形处理、市场研究等诸多领域应用广泛。作为一种获得广泛应用的经典聚类划分算法，K-means算法具有算法数学思想清晰且易于实现、收敛速度快等优势[2]，但是需要事先指定初始聚类中心的个数k值，而且由于中心点选取的随机性而容易陷入局部最优解。

随着数据库和网络技术的快速发展，生成的数据呈海量增长，传统的聚类算法很难满足时下的数据分析处理需求。2004年，Google公司研发了一个称为Hadoop的开源MapReduce并行计算框架和系统，给大数据并行处理带来了重大的影响，现已成为迄今为止易于使用、广为接受的业界主流大数据并行处理技术。因此，许多学者运用MapReduce模型陆续展开了有关海量数据的聚类研究。江小平等人[3]提出了一种基于MapReduce的并行K-means聚类算法，该算法的执行效率较高，但由于K-means算法在收敛前需要进行多次迭代计算，不断地重启计算任务及读取原始数据集，因此造成更多的I/O开销。毛典辉[4]提出的基于MapReduce的Canopy-Kmeans改进算法，采用最大最小原则对该算法进行改进。虞倩倩等人[5]提出了基于MapReduce的ACO-Kmeans并行聚类算法，针对K-means聚类算法处理海量数据时存在的内存不足等问题，研究了利用MapReduce实现K-means聚类算法的并行化。

综上这些算法很好地解决了传统K-means算法处理海量数据的一些不足，但是仍存在聚类效果不稳定、准确率不高，也未能充分考虑算法执行过程中的计算量以及通信代价等问题。为此，本文拟基于MapReduce模型，采用抽样技术和最大最小距离法，设计提出一种高效的并行K-means算法。通过在UCI标准数据集地行实验，最终结果表明该算法的收敛速度、聚类精度，以及在处理海量数据时的并行性能都得到了提高。

1 相关理论

1.1 传统的K-means聚类算法

设数据集X={x1,x2,…,xn}，其中xi表示一个数据对象，通常采用欧式距离作为判断2个数据对象之间相似性的依据。任意2个数据对象间的欧式距离为：

(1)

其中，m为数据集的属性维数，xir，xjr为数据对象xi和xj的第r个属性值。距离越小相似性越大，相反则相似性越小。

传统K-means算法的设计流程可描述如下[6]。

(1)针对数据集X={x1,x2,…,xn}，指定聚类个数为k，并随机选取k个数据对象作为初始聚类中心{c1,c2,…,ck}。

(2)根据公式(1)计算每个数据对象xi到k个聚类中心的欧式距离，并把数据对象xi划分到与之距离最近的聚类中心所属的聚类中。

(3)计算每一个类簇中所有数据对象的平均值作为新的聚类中心。

(4)重复执行步骤(2)和步骤(3)进行下一轮聚类，直到各个聚类中心在某个精度范围内不再变化或者达到最大迭代次数为止，算法结束。

1.2 随机抽样

在统计学中，简单随机采样是各类抽样方法的基础，但在大规模的抽样调查中却很少被单独采用，而在数据挖掘技术中，因其呈现的总体确定性，这一限制也随即被消除。

由统计学的大数定律、中心极限定律、贝努利大数定律等可得到如下结论[7]，不论总体服从何种分布，只要其数学期望和方差存在，从中抽取容量为n的样本，这个样本的和或平均数将作为随机变量，当n充分大时，趋于正态分布，则可得随机抽样样本容量n的数学公式为：

(2)

其中，N为数据集总量；t为概率度；δ为标准差；ε为误差限制。通常，随机采样时采用置信度为0.95，概率度为1.96。

1.3 最大最小距离法

最大最小距离法以欧式距离为基础，采取以最大距离原则选取新的聚类中心，以最小距离原则进行模式归类。因此避免了K-means算法初值选取时可能出现的聚类中心过于邻近的情况[8]，而且可以智能确定初始聚类中心的个数，提高了划分初始数据集的效率。算法运行各步骤可详述如下。

(1)有n个对象，Sn={X1,X2,…,Xn}。

(2)任取一个数据对象，例如X1，作为第一个聚类中心，然后找出集合Sn中到第一个聚类中心距离最远的数据对象作为第二个聚类中心。

(3)对Sn中剩余的其它数据对象Xi，分别计算到第一个、第二个聚类中心的距离，令其中较小的为DXi。

(4)计算maxSn={DXi}。若maxSn={DXi}>m×[average(|X2-X1|)]，则取Xi为新的聚类中心。通常取值为m∈[1/2，1)。

(5)重复执行步骤(1)～(4)，直到不产生新的聚类中心为止。

2 基于抽样和最大最小距离法的并行K-means聚类算法

本算法首先采用抽样技术对原始数据集进行多次随机抽样，以产生新的数据集；然后运用MapReduce模型，2次采用最大最小距离法生成最佳的初始聚类中心；最后基于MapReduce模型利用K-means算法进行迭代聚类。算法的执行过程可表述如下。

输入：原始数据集D和聚类数目k，采样次数J

(1)计算原始数据集D的平均值和方差，并根据公式(2)确定抽样样本量。

(2)对原始数据集D进行J次随机抽样。

(3)初始聚类中心运算

① Map1阶段：对每个抽样样本运用最大最小距离法生成若干的初始聚类中心集合。

② Reduce1阶段：将这些初始聚类中心集合汇总后再次运用最大最小距离法，从而得到最佳的k个初始聚类中心。

(4)新的聚类中心运算

① Map2阶段：计算每个初始聚类中心的欧式距离并重新标记所属类别。

② Reduce2阶段：依据中间结果再次计算新的聚类中心。

(5)经过多次迭代计算，直至收敛，从而得到最终的聚类结果。

3 实验结果与分析

实验选用Hadoop集群平台由一个master节点和9个slavers节点组成。实验运用的数据集均来自UCI数据库，各数据集信息可详见表1。通过一系列实验，测试这些数据集在Hadoop集群环境下本文算法和基于MapReduce的K-means并行算法[3]的收敛速度、聚类精度及其并行性能。对此，将给出研究论述如下。

表1 实验数据集

(1)收敛速度的对比分析。研究中，为了保证仿真实验结果的客观性，则将2种算法各重复运行10次，测试每种算法的收敛速度，即各自完成聚类所需要的迭代次数，对比结果可见表2。

表2 收敛速度对比

从表2中可以看出，本文算法的聚类收敛速度与基于MapReduce的K-means并行算法相比要更快一些。究其原因就在于本文算法运用了最大最小距离法对初值选取进行了优化，K-means聚类过程对初始聚类中心的依赖性有所减小，从而使得该算法聚类时所需要的迭代次数明显减少，收敛速度加快。

(2)聚类精度的对比分析。聚类精度是指数据对象被置于正确的类簇中的数据个数与总的数据对象个数的比值。2种算法的聚类精度对比结果可见表3。从表3中可以看出，本文算法的聚类精度要高于基于MapReduce的K-means并行算法，这也说明本文算法对含噪声数据以及分布异常数据的处理能力有所提升，聚类质量也更高。

表3 聚类精度对比

(3)并行性能的对比分析。加速比是同一个任务在单处理器系统和并行处理器系统中运行消耗的时间的比率，用来衡量并行系统或程序并行化的性能和效果[9]。计算公式为：

Sp=T1/Tp

(3)

其中，T1表示顺序执行算法(即单一PC机)的执行时间，Tp表示并行算法(即p个处理器)的执行时间。加速比越大，说明并行计算消耗的相对时间越少，并行效率越高。

通过对数据集1990 US Census Data扩充为2倍、4倍、8倍不同大小的数据集，分别在不同节点数的Hadoop集群平台下运行本文算法，由此得出加速比的并行性能对比结果。

在Hadoop集群平台下，本文算法的加速比则如图1所示。可以看到，随着节点数增加和数据量增大，加速比也呈现提升态势。由此分析可得，在处理海量高维数据集时，单机由于内存不足将无法运行，而集群则能有效提高算法的计算效率，并行性能堪称优良。

图1 Hadoop集群平台的加速比

4 结束语

针对传统聚类算法处理海量数据的一些问题与不足，本文将基于MapReduce模型，采用抽样技术和最大最小距离法，设计提出一种高效的并行K-means算法。通过在UCI标准数据集进行实验，结果表明该算法的收敛速度、聚类精度，以及在处理海量数据时的并行性能均在一定程度上获得了提升。未来将会在更多的大数据集上展开测试，包括高维数据，从而进一步验证算法的性能并提供后续的改进与完善。