一种基于Hadoop 的高效K -Medoids并行算法
2015-04-17王永贵
王永贵，戴 伟，武 超
WANG Yonggui,DAI Wei,WU Chao
辽宁工程技术大学 软件工程学院，辽宁 葫芦岛125105
College of Software,Liaoning Technical University,Huludao,Liaoning 125105,China
1 引言
在这个大数据的时代，数据量由TB 级升至PB 级快速地增长，其速度远超摩尔定律的增长速度[1]。面对海量的数据，如何正确处理这些数据，挖掘出有价值的信息，成为当今主要的研究方向之一[2]。利用聚类算法进行信息的自动分类是处理这些数据的重要方法。
K-Medoids 算法和K-Means 都是基于划分的聚类算法，此类算法简单，并且容易实现，被广泛应用于科学研究的各个领域[3-4]。但是其对初始聚类中心都比较的敏感[5]，并且无法很好地处理海量数据的聚类问题。针对K-Medoids 算法的特点以及不足，有很多学者提出了各种改进的K-Medoids 算法。文献[6-7]实现了基于MapReduce 的K-Medoids 并行算法，用并行的计算思路解决了处理海量数据的时间问题，但只是针对传统的K-Medoids 算法进行并行化处理，没有解决K-Medoids算法对于初始中心敏感的问题；文献[8]根据密度信息产生初始中心，解决了初始中心敏感的问题，但却增加了算法的复杂度。其他的例如利用遗传算法[9]，ACO[10]，人工蜂群[11]等措施来改进算法，虽然在少量数据环境下能够显著提升K-Medoids 算法的性能，但却因为额外的组件增加了算法的复杂性[12]，无法适应大数据的现实背景。
因此，针对以上提出的问题，结合当前大数据的环境，本文提出了一种基于Hadoop 的高效K-Medoids 并行算法，其初始中心的选择使用了基于样本的预处理解决方案，簇心的替换采用了簇内中心调整策略，计算模型选用了MapReduce 分布式计算模型，存储系统使用了HDFS（Hadoop Distributed File System）分布式存储系统。实验表明，该算法不仅延续了传统K-Medoids 算法的优势，保证了聚类效果的优越性与稳定性，并且在处理海量数据时，算法的执行效率也取得了较大程度的提高。
2 预备知识
2.1 MapReduce编程模型
MapReduce 是一种分布式编程模型，其最初是由Google 实验室提出的一个分布式并行计算框架，后由Apache 组织通过Hadoop 分布式计算平台将其开源实现。MapReduce 计算模型是将海量的数据进行分割从而进行分布式计算。其对数据的处理抽象成Map 和Reduce 两个阶段，每个阶段都以键/值（key/value）作为输入和输出，即有[13]：
每一个map 以及reduce 都会分配到集群中的某一台机器上运行，每一台机器的map 或reduce 操作都相互独立，这样就实现了map 之间的并行，reduce 之间的并行，以及map 和reduce之间的并行操作过程。
在初始阶段，MapReduce 模型通过InputFormat 将数据切分成固定大小的片段（split）形成＜key1，value1＞的数据形式交付给map 进行操作。map 执行完成以后会根据相同的key 合并成＜key2，list(value2)＞的形式，然后在Partition 中使用Hash 算法将相同的key 交付给相应的reduce 进行处理操作，reduce 操作结束后通过OutputFormat形成＜key3，value3＞的形式存储到文件中。
2.2 Top K 查询算法
TopK算法的目的就是从海量的数据中选取最大的K个元素或记录。其主要的基本思想就是维护一个具有K个元素的小顶堆。每当有新的元素加入时，判断其是否大于堆顶元素，若大于则用该元素代替堆顶元素，并重新维护小顶堆，直到处理完所有元素。
3 K -Medoids算法的介绍和分析
3.1 K -Medoids的算法思想
假设有n个h维的对象点，要将其聚类成k(k＜n)个簇，则将第i个对象点的第f维的值定义成Xif(i=1，2，…，n;f=1，2，…，h)。这里使用欧式距离来判定对象点之间的相似度，欧式距离越大代表相似度越小。利用欧氏距离，对象i与对象j之间的距离定义如下：
传统K-Medoids算法描述如下：
输入：聚类的个数k，包含n个数据对象的数据集D。
输出：满足基于各聚类中心对象的距离最小标准的k个簇。
步骤1从数据集D中任意挑选k个对象作为初始中心点。
步骤2循环步骤3 到步骤5 直到每个聚类中心不再变化为止。
步骤3按照最短距离原则，将对象点分配到离其最近的簇中。
步骤4全局随机选择一个对象点Orandom作为替代簇心。
步骤5若替代簇心比原簇心的聚类效果更好，则将替代簇心作为新的聚类中心，否则跳转到步骤2。
3.2 传统K -Medoids的不足
（1）在进行海量数据的聚类时，由于数据量巨大，无法存储在单台计算机的存储器中，导致K-Medoids 算法无法正常进行聚类操作。
（2）由于K-Medoids 算法自身的特性，其算法的时间复杂度较高，无法适应大数据下的聚类操作。
（3）传统K-Medoids 算法在选择初始聚类中心时采用的是完全随机策略，无法保证聚类结果的准确性。
（4）在聚类中心的替换方法上，传统K-Medoids 采用的是全局顺序替换策略，这种方法虽然保证了聚类的效果，但是却降低了算法的执行效率，增加了算法的执行时间。
4 改进的K -Medoids算法
4.1 基于Top K 的并行随机采样
面对海量数据，初始中心的选择显得尤其重要，一些改进的算法为了选出较好的初始中心而在聚类操作之前对全局数据进行预处理，但是随着数据量的增大，预处理的代价也逐渐增加，降低了算法整体的运行效率。所以本文采用了先采样，然后在样本内进行数据预处理，计算初始中心。
常用的文本随机采样一般分为两种：（1）遍历采样（2）按字节偏移采样。
第一种遍历采样方法如按行采样，简单并且能够保证原来的数据格式，但由于其遍历过程随着原数据以及采样量的增加，时间复杂度呈线性增长，对系统的消耗将逐渐增大，不适合大规模的采样操作。
第二种按字节偏移的采样方法，能够适应较大规模的数据采样，但是面对海量数据的采样操作，效率也不理想。
针对以上问题，本文提出了一种基于TopK算法的随机采样过程，并利用Hadoop 平台实现了对数据的并行采样，其具体实现过程如下：
输入：随机数范围H，样本容量N，Reduce 的个数Rn。
输出：N条数据样本。
步骤1在Map 阶段给每一个数据随机产生一个0到H的整数作为其key 值，其数据内容作为value 形成
步骤2将相同key值的数据合并成
步骤3每个Reduce输出前N/Rn条数据。核心代码如下所示：
（1）Map 阶段：
Random rd=new Random（）；
intkey=rd.nextInt（H）；
Context.write（new IntWritable（key），value）；
（2）Reduce阶段：
4.2 K -Medoids算法的改进方案
（1）基于HDFS 的分布式存储策略。因为HDFS 是一种分布式存储系统，其将原本需要一整块连续存储空间的数据，拆分成多个小数据块，分别存储在不同的存储节点上。所以在面对海量数据时，也能够对数据进行高效的存取。
（2）针对传统K-Medoids 算法的时间复杂度较高，无法进行海量数据的聚类计算问题，本文采用了基于MapReduce 的分布式计算模型，将一个大型的数据文件切分成多个小数据模块，分别交付给多台计算机利用MapReduce 计算模型进行分布式计算，减少了单台计算机的计算时间，加快了整体的计算速度。
（3）对于初始中心选取的改进一般有两种方案，一种是结合智能算法，第二种则是采用随机策略。由于智能算法在大数据的环境下学习成本较高，而随机选取策略不利于其聚类效果，所以本文结合文献[14-16]提出一种更加适合MapReduce 编程模型的样本预处理解决方案，其中采样策略使用了4.1 节的并行随机采样，样本容量（N）则根据数据对象个数（M）以及聚类数目（k）进行动态判定。样本容量定义如（2）所示。
数据预处理的计算则使用了（3）中的公式，公式定义如下[9]：
（4）簇内随机替换策略[17-18]。由于顺序替换不能够适应大数据的聚类计算[12]，所以采用簇内随机替换策略即在每个簇的内部进行中心点的随机替换过程。实验表明，相比较原来的顺序替换方式，此方法在处理海量数据时有更快的收敛速度。
4.3 新算法描述
改进的K-Medoids算法的具体流程描述如下：
输入：聚类个数k，包含N个数据对象的数据集，连续次数C。
输出：满足基于各聚类中心对象的距离最小标准的k个聚类。
处理流程：
步骤1并行随机采样。
步骤2样本预处理，计算初始聚类中心，初步聚类：
步骤2-1利用MapReduce 计算模型分布式计算样本内每个节点之间的距离（dij）并保存在相应的文件中，使用的距离测量为公式（1）的欧式距离。
步骤2-2使用上一步所保存的节点间距离关系，对每个节点j利用公式（3）计算Vj的值。
步骤2-3根据Vj按照升序进行排序。选取序列中前k个值所对应的k个点坐标作为初始中心点，写入聚类中心文件，保存。
步骤2-4按照最短距离原则，将对象点分配到离其最近的聚类中心所在簇中。
步骤2-5计算各簇内所有节点与其簇心的距离之和（olddistance）。
步骤3聚类中心替换
各簇内随机选择一个点Orandom替换当前簇心Onow，计算簇内其他对象点与Orandom距离之和（newdistance），若newdistance 较olddistance 更小，则将Orandom作为当前簇心Onow，否则保留原簇心不变。
步骤4分配节点，判断终止。
步骤4-1根据当前的聚类中心，将对象点分配到离其最近的聚类中心所在的簇中。
步骤4-2若k个簇心分别连续C次不变，则终止算法，否则跳转到步骤3 中再次进行。
核心代码如下所示：
（1）KMMapper：map 阶段。对象点分配到离其最近的聚类中心所在的簇中
（2）KMReduce：reduce 阶段。选出Orandom，计算olddistance 以及newdistance。
（3）CenterCompare：判断终止。比较olddistance 和newdistance的大小，重写簇心文件。
Hadoop 下改进的K-Medoids算法流程如图1 所示。
图1 Hadoop 环境下改进的K-Medoids算法流程图
5 实验与性能分析
5.1 实验环境
在Linux 环境下搭建Hadoop 集群，共六台计算机，其中一台作为提供NameNode，ResourceManager 服务的master节点，其他五台作为提供DataNode，NodeManager服务的slave 节点，其中作为master 节点的配置为：CPU型号为Intel core i5-460M；内存为8 GB；硬盘为500 GB。其他五台作为slave节点的配置为：CPU型号为Pentium®Dual-Core E6600；内存为2 GB；硬盘为500 GB。六台机器安装的操作系统都为Ubuntu 12.04，集群上搭建的Hadoop 版本为Hadoop-2.2.0。图2 显示了这六台机器之间的分布关系。
图2 集群结构
5.2 单机处理比较实验
5.2.1 收敛速度比较
实验内容为比较改进的K-Medoids 算法和传统K-Medoids 算法在单机下处理相同数据时，完成聚类所需要的迭代次数及时间。其中改进的K-Medoids 是在Hadoop 伪分布模式下运行，传统K-Medoids 是在普通串行环境下运行。处理的数据集为6 类具有8 206 个对象的三维数据，数据集大小为0.2 MB，选取的聚类中心k为3，具体的收敛时间及迭代次数见表1。
表1 迭代次数及收敛速度
从表1 中可以看出，在单机伪分布环境下改进的K-Medoids 算法平均迭代次数更少，拥有更好的全局收敛性，但是传统K-Medoids串行算法所消耗的时间更少。这是因为在处理少量数据时，Hadoop 计算平台并不能发挥其性能优势。在MapReduce 的计算框架下，不仅要经过提交map 和reduce 作业的步骤，还要经过将作业分片（split）、中间排序（sort）、合并（merge）、分配（partition）等过程，所以在处理少量数据的情况下，实际的计算时间在总消耗时间中所占比例较小，只有在大量数据的条件下才能更好地发挥出MapReduce计算框架的优势。
5.2.2 单机数据负荷测试
实验内容为在不同数据负荷下，单机伪分布下改进的K-Medoids 算法和传统串行K-Medoids 算法执行效率的比较，实验结果如表2，其中T1 代表传统K-Medoids算法所消耗的时间，T2 代表改进的K-Medoids 算法所消耗的时间。
从表2 可以看出，只有在数据量较小时，串行执行的时间要少于伪分布下的执行时间，并且在数据量达到400 MB 以上时，串行算法出现了内存溢出，导致算法无法正常运行，而在Hadoop 平台下改进的K-Medoids 算法却能继续执行。
表2 单机负荷情况
因为传统K-Medoids 算法聚类时，数据需要读入内存中进行操作，随着数据量的增加，算法的时间复杂度也在急剧增长，所以在面对海量数据的时候，传统的K-Medoids 算法会导致内存溢出的情况发生。而在MapReduce 分布式计算框架下结合HDFS 分布式存储系统的支持，将计算及存储过程进行分布式处理，中间数据以
5.2.3 Iris数据集对比
本次实验目的是测试在标准数据集下，算法的精确度，所用数据集Iris 来自UCI Repository（http：//archive.ics.uci.edu/ml/datasets/Iris）。Iris 数据集被分成了三组（Setosa，Versicolor，Virginica），每一组包含50 个数据对象，每个对象都含有4 种属性。分别采用K-Means，传统K-Medoids 以及改进的K-Medoids 算法来测试各算法聚类的效果。这里由于数据量较小，所以不需要采样，直接对全局数据预处理。
表3，表4，表5分别表示K-Means，传统K-Medoids以及改进的K-Medoids算法对Iris的聚类结果。
表3 K-Means聚类结果
表4 传统K-Medoids聚类结果
表5 改进K-Medoids聚类结果
从表中可以得出，K-Means的正确率为62.7%，传统K-Medoids的正确率为86.7%，改进的K-Medoids正确率为92%，其中K-Means的正确率最低，改进的K-Medoids正确率最高。因为传统的K-Medoids 和K-Means 算法初始中心的选取采用的是随机策略，聚类效果随初始中心的变化而波动，并且K-Means 算法无法排除脏数据的干扰。而改进的K-Medoids 算法初始中心的选取采用了数据预处理策略，避免了初始中心的随机性，同时K-Medoids 算法自身的特性也能很好的避免脏数据的干扰。
5.3 集群测试
5.3.1 初始采样测试
实验内容为比较不同随机采样方式的效率。分别使用逐行遍历采样，字节偏移采样以及基于TopK的并行随机采样进行对比。其中并行采样使用的为六台主机所组成的Hadoop 集群，其中一台作为NameNode和ResourceManager，其余五台作为DataNode 和Node-Manager，选用的为1.2 GB 的数据集。实验结果如表6。
从表6 可以看出遍历采样的效率最差。抽取的样本较少时，字节偏移采样的效率最高，但是随着采样量的增加，其时间消耗呈线性增长。并行采样所耗费时间趋于平稳，并且在大规模数据采样下，并行采样所耗费的时间最少。所以本文的并行采样方法更适合大数据环境下的采样操作。
表6 不同采样所耗费时间 s
5.3.2 人造数据集对比
实验内容为在集群环境下，比较分布式K-Means算法和改进的K-Medoids算法的聚类效果。
其中数据集使用的是四组服从二维高斯分布的人造数据集（A：红色实心圆，B：绿色空心圆，C：蓝色正三角，D：蓝绿色五角星），每一组数据包含7 000 条二维坐标，其中图3为四组数据所组成原始数据集，图4，图5分别显示的为使用分布式K-Means 算法和改进的K-Medoids算法的聚类结果。
图3 原始数据集
图4 分布式K-Means聚类效果
图中箭头所指的点即为聚类后的聚类中心点。从图中可以看出，在集群环境下改进的K-Medoids 算法的聚类效果更好，并且其最终的簇心更加接近每一组数据的初始中心。而分布式K-Means 算法的聚类效果却不理想，其A 组数据虽然比较接近原始数据，但是B、C、D 三组数据的聚类结果都有大幅度的偏差，并且C 组数据的簇心指向的是原数据集中不存在的点。这是因为K-Means是根据均值来计算簇心，无法排除脏数据的干扰，导致其最终簇心可能指向的是原本不存在的点，并且由于其初始中心的随机性，不能保证聚类结果的准确性。所以在集群环境下，改进的K-Medoids 算法的聚类效果更为精确。
图5 改进的K-Medoids算法聚类效果
5.3.3 集群负荷测试
实验内容为在Hadoop 集群环境下，比较在不同数量的计算节点下，系统处理相同规模数据的效率。表7描述了几组不同的实验数据集。每条记录由2 维数值型数据组成，程序指定生成3 个中心(k=3)，默认的数据分块大小为128 MB。
表7 数据集情况
由于实验环境是由5 个DataNode 所组成的集群，所以分别选择1，2，3，4，5 个DataNode 节点参与运算，观察在不同数量节点下，系统完成任务的时间，具体的实验结果如图6 所示。
图6 不同节点运行时间图
从图6 可以看出，在数据量较小时，不同数量节点下的时间消耗趋于平稳，而当数据量较大时，随着节点的增加，其收敛所消耗的时间明显减少，说明改进的算法更适合应用于大数据下的聚类操作。
5.3.4 集群环境下的加速比
加速比（speedup），是同一个任务在单处理器系统和并行处理器系统中运行消耗的时间比率，用来衡量并行系统或程序并行化的性能和效果[8]。其计算公式定义为：
其中Tp表示并行算法执行所消耗的时间，Ts表示串行算法执行所消耗的时间，加速比越大，表示并行算法的执行效率越高。这里实验仍然使用5.3.3 节中的数据集，生成4 个类别，分别采用1，2，3，4，5 个DataNode 节点计算其加速比，结果如图7 所示。
图7 加速比
从图中可以看出每个作业的加速比都随着节点数的增加而增加，尤其当数据量较大时，增加节点可以显著地提高并行执行过程。这说明了通过MapReduce 并行计算模型来执行改进的K-Medoids 算法可以有效地提高算法的执行效率。
5.3.5 基于Hadoop 平台的算法优化
Hadoop 中数据是以块（block）为单位进行分布式处理，通常块的个数决定了可以并行的map 个数，所以在不同块大小时，算法执行的效率也不相同。在Hadoop中块大小的计算公式定义如下[19]：
其中minimumSize 默认值为1，maxmumSize 默认值为Long_MAXVALUE，所以可以通过修改blockSize 参数的值来改变块的大小，从而决定map的个数。
这里通过修改blockSize 的值，分别将块的大小设置为32 MB，64 MB，128 MB，256 MB 来比较改进的K-Medoids 算法的执行效率，数据使用5.3.3 节中的数据集，其分块情况如表8 所示。
表8 不同数据集的分块情况
不同数据集在不同数据块大小下的运行时间如图8所示，运行环境为6 台机器所组成的Hadoop 集群，其中5 台作为计算节点。
图8 不同块大小的执行效率
可以看出算法执行的效率并不完全和数据块的大小呈正向或反向的线性关系。当数据量较小时，block-Size 越大，相应的map 个数越少，执行的效率越低；数据量较大时的结果则相反。同时图中显示，数据集C的时间趋势呈一个倒三角，当blockSize 为64 MB 时，其执行效率最高。
这是因为当处理的数据量较小时，较大的blockSize会减少可以并行的map 个数，无法体现集群并行计算的优势；当处理较大数据时，如果blockSize 设置较小，虽然充分利用了集群的并行计算，但却增加了map 任务的分配过程以及运行作业所必须的寻址次数，增加了系统的总消耗，尤其在处理海量数据时，这些消耗是相当巨大的。所以在使用Hadoop 平台处理数据时，需要根据数据量来合理地进行数据块大小的设置。从以上实验可以得出：在当前集群环境下，数据集和数据块大小设置地合理比例为10∶1。
6 总结
本文在对传统K-Medoids算法研究的基础上，提出了一种并行的高效K-Medoids 改进算法，并在Hadoop平台上成功实现。通过标准数据集Iris 以及人造数据集的实验结果，可以看出改进的K-Medoids 算法比K-Means 以及传统K-Medoids 算法有着更好的聚类精度。通过在不同大小数据集以及不同数量计算节点下的实验，表明了改进的K-Medoids 算法在处理海量数据时较传统的K-Medoids 算法有更好的收敛速度，更加适合大数据的聚类计算。最后在Hadoop 并行计算平台下，根据其计算机制，通过调整数据块的大小，实现算法的进一步优化。
当然本文算法还有一些需要改进的地方：在初始化中心节点时，通过保存样本点之间的距离关系，使之后的计算能够反复读取距离值，不需要再次计算，减少了算法的计算量。但是由于没有相关数据库的支持，其数据的存储及读取都是基于文件操作，整体效率较低。所以下一步的目标就是引入HBase 分布式数据库[20]，从而提高算法的整体性能。
[1] 王珊，王会举，覃雄派，等.架构大数据：挑战、现状与展望[J].计算机学报，2011，34（10）：1741-1752.
[2] 覃雄派，王会举，杜小勇，等.大数据分析——RDBMS 与MapReduce的竞争与共生[J].软件学报，2012，23（1）：32-45.
[3] 孙胜，王元珍.基于核的自适应K-Medoids 聚类[J].计算机工程与设计，2009，30（3）：674-675.
[4] 孟颖，罗克，刘建华，等.一种基于差分演化的K-medoids聚类算法[J].计算机应用研究，2010，29（5）：1651-1653.
[5] Zhang Qiaoping，Couloigner I.A new and efficientK-medoid algorithm for spatial[C]//Computational Science and its Applications-ICCSA，2005：181-189.
[6] 张雪萍，龚康莉，赵广才.基于MapReduce 的K-Medoids 并行算法[J].计算机应用，2013，33（4）：1023-1025.
[7] 冀素琴，石洪波.基于MapReduce 的K_means 聚类集成[J].计算机工程，2013，39（9）：84-87.
[8] 姚丽娟，罗可，孟颖.一种新的k-medoids 聚类算法[J].计算机工程与应用，2013，49（19）：153-157.
[9] 郝占刚，王正欧.基于遗传算法和k-medoids算法的聚类新算法[J].现代图书情报技术，2006，136（5）：44-46.
[10] 孟颖，罗可，姚丽娟，等.一种基于ACO 的K-medoids 聚类算法[J].计算机工程与应用，2012，48（16）：136-139.
[11] 李莲，罗可，周博翔.一种改进人工蜂群的K-medoids 聚类算法[J].计算机工程与应用，2013，49（16）：146-150.
[12] 夏宁霞，苏一丹，覃希.一种高效的K-medoids聚类算法[J].计算机应用研究，2010，27（12）：4517-4519.
[13] 虞倩倩，戴月明，李晶晶.基于MapReduce的ACO-K-means并行聚类算法[J].计算机工程与应用，2013，49（16）：117-120.
[14] Park Hae-Sang，Jun Chi-Hyuck.A simple and fast algorithm forK-medoids clustering[J].Expert Systems with Applications，2009，36（2）：3336-3341.
[15] Alper Z G.K-harmonic means data clustering with simulated[J].Applied Mathematics and Computation，2007，184：199-209.
[16] Pei Ying，Xu Jungang，Cen Zhiwang，et al.IKMC：An improved K-medoids clustering method for near-duplicated records detection[C]//International Conference on Computational Intelligence and Software Engineering，2009：1-4.
[17] Cardot H，Cénac P，Monnez J M.A fast and recursive algorithm for clustering large datasets with k-medians[J].Computational Statistics and Data Analysis，2012，56：1434-1449.
[18] Qiao Shaoyu，Geng Xinyu，Wu Min.An improved method for K_medoids algorithm[C]//International Conference on Business Computing and Global Informatization，2011：440-444.
[19] Tom White.Hadoop 权威指南[M].周敏奇，译.北京：清华大学出版社，2011.
[20] 强彦，卢军佐，刘涛，等.基于HBase 的并行BFS 方法[J].计算机科学，2013，40（3）：228-231.
