基于相似度矩阵的K—neans算法的MapReduce并行化实现

曹奇敏　刘鸿霞

摘要：为了提高基于相似度矩阵的K-Means算法（SMK-means）处理大数据的能力，它使用MapReduce分布式编程模型，并结合SMK-means算法自身的特点，设计出了SMK-means算法基于MapReduce的并行化实现。通过设计Map和Re-duce函数实现了SMK-means算法的并行化。Map函数通过计算样本和聚簇中心的相似度来确定样本的聚簇归属，Re-duce函数用于完成聚簇中心的计算。实验结果证明，基于MapReduce的并行化的SMK-means算法在保证文本挖掘性能不降的前提下，使得运行效率得到了大幅度提升。

关键词：K-Means算法；相似度矩阵；MapReduce模型；并行计算；文本挖掘

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2017）18-0018-03

1概述

随着大数据时代的到来，人们所接触到的数据量成PB级别快速增长，同时还要求快速高效地处理所得到的数据。对于数据处理有两方面的要求，一是要比数据产生的速度快，二是还要达到数据使用者对处理结果的预期。尽管这两个要求通过使用并行计算的框架得到了一定程度上的满足，但是MPI等传统的并行框架还存在不少缺点，像技术人员需要自己实现对任务分配、集群管理等工作的编码，它在可扩展性上也有一定的限制等问题，这样就直接增高了传统并行框架的使用门槛，也无法将成本控制在一个较低的水平。而MapReduce等并行计算框架的出现较好地解决了并行计算实现难和成本高的问题。本文使用MapReduce并行框架，对基于相似度矩阵的K-Means算法（SMK-means）进行并行化处理。

2 MapReduce编程模型

MapReduce处理大数据集，其关键步骤为Map函数和Re-duce函数的设计与实现。用户根据自己的要求对这两个函数进行自定义，函数的输入与输出都是使用键值对的形式。

Map函数中，MapReduce模型首先把数据集平均分割成若干个数据块，再把各数据块解析成in，V_in>对的形式。各个数据块经过Map函数的处理得到一组相应的结果，其结果记录为m，V_m>对。然后这些结果将会被输入到Reduce函数中。

Reduce函数中，第一步先是把各Map函数的输出结果进行预处理包括合并与按一定次序排列，预处理结果的形式为m，list{v_m>对，第二步则使用Reduce函数将预处理结果作为输入执行相应的操作，最后记录其运行结果out，v_out>对。

3 SMK-means算法的并行化实现方法

3.1 SMK-means算法的基本思路

K-means算法是一种经典的文本聚类算法，初始聚簇中心选择的好坏与否直接影响聚类的性能，也就是说初始聚簇中心与真实的聚簇中心越接近，K-means算法的聚类准确度就会越高。SMK-means算法是在传统K-means算法的基础上进行了改进，它通过选择合适的初始中心点来获得较为理想的分析结果。SMK-means算法的改进部分就是通过计算相似度矩阵选取初始聚簇中心，初始聚簇中心选择的过程中用到的计算包括对矩阵的行求和与排序。相比较传统K-means算法易受初始聚簇中心选择的影响，导致多次运行的结果差别很大，即使结果簇相对比较稀疏，SMK-means算法也能得到较好的分析结果，同时还能够降低噪声和孤立点这类数据对分析结果造成的影响。

3.2 SMK-means算法的MapReduce并行化方法

SMK-means算法基于MapReduce的并行化步骤如下：

1）计算相似度矩阵，通过运算相似度矩阵选取K个初始聚簇中心。

2）将数据集解析为行的表达形式，然后由MapReduce模型完成对数据集的分割。

3）为各个数据点分配聚簇，该过程的并行化由Map函数执行。Map函数的输入输出的数据格式分别为<序号，数据向量>和<聚簇标号，数据向量>，其中输入的数据为全部数据点和上一轮迭代输出的聚簇中心（或初始聚簇中心）。运行过程中Map函数通过计算数据点与聚簇中心之间相似度将相似度最大的聚簇设置为数据点的类别标签，然后输出计算结果。Map函数的伪代码如图1所示。

4）计算各个聚簇中数据点的均值來更新聚簇中心，该过程的并行化由Reduce函数执行。Reduce函数输入输出的数据格式为<聚簇标号，{数据向量}>和<聚簇标号，聚簇中心向量>。在运行过程中Reduce函数把数据按照其被分配的聚簇进行整合，使得属于同一聚簇的数据被同一个Reduce函数接收，然后聚簇中心更新为聚簇数据点的均值。Reduce函数的伪代码如图2所示。

5）计算更新前后聚簇中心的距离，用以确定算法结束与否。此过程只需由一个Reduce函数来执行。运行过程中首先计算更新前后聚簇中心的距离，然后将此距离与阀值进行比较，当两者的距离比阀值小时，则算法结束，否则转回3。

4实验与结果分析

在实验过程中，本文所选用的数据集为北京大学的人民日报语料库。

4.1 F值对比分析

为验证MapReduce框架下SMK-means算法的仍能保持较高的聚类F值，将其与DE+K-means算法、Filtering算法、K-means算法和SMK-means算法做了比较。实验中，随机地从语料的娱乐类、体育类、文化类、科技类、经济类和政治类数据中各取20，000篇。实验结果如表1所示。

表1的结果表明，并行化SMK-means算法的聚类F值明显高于DE+K-means算法、和K-means算法的F值，与Filtering算法相比其F值也有一定程度的提高。更重要的是，经过MapRe-duce分布模型并行化处理的SMK-means算法所获得的F值与未经过并行化处理的SMK-means算法的F值属于同一个级别，差别很小，这就说明了经过MapReduce分布模型并行化处理的SMK-means算法仍能保持较好的聚类性能。

4.2聚类时间开销对比分析

为验证MapReduce框架下SMK-means算法的运行效率得到了大幅度提高，将其与DE+K-means算法、Filtering算法、K-means算法和SMK-means算法做了比较。实验结果如图3所示。

图3的结果表明，并行化的SMK-means算法的运行效率最快，Filtering算法具有最高的时间开销，与SMK-means算法和DE+K-means算法相比，K-means算法的运行时间要短一些。由于DE+K-means算法、Filtering算法和SMK-means算法这三种算法均是在K-means算法的基础上进行的改良，计算复杂度相应的增加，因此运行时间变长了。尽管SMK-means算法在提高聚类准确度的同时一定程度上降低了运行效率，但是经过MapReduce分布模型并行化处理后大幅度缩短了运行时间，这就说明了经过MapReduce分布模型并行化处理的SMK-means算法确实可以提升运行效率。

总之，对SMK-means算法进行MapReduce并行化处理是一种有效的方式，它在保持较高的聚类F值的同时还大幅度地提升了运行效率。

5结束语

为了提高基于相似度矩阵的K-Means算法（SMK-means）处理大数据的能力，本文对其进行了并行化处理。文中使用MapReduce分布式编程模型，并结合SMK-means算法自身的特点，对相应的Map函数和Reduce函数进行了设计。通过实验证明了系统的有效性，对SMK-means算法的并行化处理是一种有效的方式。实验结果也表明了它在保持较高的聚类F值的同时还大幅度地提升了运行效率。