聚类分析的并行化实现技术研究
2015-01-17齐浩，马力
齐 浩， 马 力
（1.西安邮电大学 计算机学院，陕西 西安 710121；2.西安邮电大学 数字艺术学院，陕西 西安 710061）
根据美国风险基金KPCB（kleiner perkins caufield&byers）在2013年的《互联网趋势报告》中的统计和预测，互联网上的数据在过去五年间增长了9倍，在过去的8年中（2005-2013），数据量几乎严格按照摩尔定律预测的速度在不停的增长。2013年的全网数据量（包括文件、图片、视频等）将达到4 ZB。在数据量急剧爆发的同时，如何能更高效、更深入地利用这些数据，是数据挖掘技术所面临的新一轮挑战。由此也产生了许多并行编程语言及模型，如PARLOG及信息传递接口（Message Passing Interface，MPI）等，但这些方法并不能将一个特定的算法显式的表现出来。当前大部分的研究是对某个特定的传统算法的发展和优化，这些技术已远远不能满足现实的数据挖掘要求及分布式技术的发展。2007年，Chu C等人提出了在多核处理器的计算机上实现部分数据挖掘算法的方法[1]，为分布式系统中的数据挖掘奠定了基础。随着分布式技术的不断发展、网络数据量爆发式的增长，如何更好地利用分布式系统进行数据挖掘成了人们迫切的现实需求。
1 分布式编程模型MapReduce
MapReduce是在2004年由Google的Jeffrey Dean和Sanjay Ghemawat提出的一种分布式编程模型[2]，起初的目标是用于大于1TB的大规模数据集的计算。MapReduce解决了在分布式集群中进行并行计算、分发数据、处理失效的问题时所遇到的种种复杂问题。它将并行、容错、数据分布和负载均衡等散乱的细节包含在一个库里面，从而使程序员将注意力可以集中在如何表达所要执行的运算中，而无需考虑到运算过程中所涉及的每个细节。
MapReduce使用Map和Reduce两个函数来表达整个计算过程。
首先将用户将数据源中的记录 （如数据库中的某条记录）转为键值对的形式
在Map作业执行完毕之后，Reduce函数利用Map的输出作为输入，把列表中键值对的value值合并在一起，构造一个拥有更小value值的集合。一般情况下，每次调用Reduce函数会输出零或一个value值。中间value值通过一个迭代器提供给用户的Reduce函数，以避免因太大而无法适应内存的value值列表的出现。
在分布式架构中，Map函数从不同的数据源中读取不同的输入，并创建不同的中间值。Reduce函数同样可以并行执行，而每个Reduce作业仅接收key值相同的中间值对，换言之，每个Reduce作业所接收的key值都是不同的。根据MapReduce的分布式工作原理可以看出，每个数据源中的数据均是独立处理的[3]。（图1）
图1 MapReduce的工作原理Fig.1 Working principle of MapReduce
2 传统聚类算法的MapReduce并行化
聚类是数据挖掘中的重要组成部分，它是将数据对象根据事先未知的特征分成多个类或簇的过程，其特征是在同一个簇中的数据有着较高的相似度，而不在同一个簇中的数据对象有着明显的差异[4]。通常根据距离来判断数据对象的相似度。在30多年的发展中已经提出了许多种聚类算法。
2.1 K-means算法
K－means算法是最著名及最常用的基于划分的方法之一，也是最早被学者进行并行化研究算法之一[5]。它需要预先输入参数k，将n个对象划分为k个簇，簇内的任意对象之间相似度高，而位于不同簇中的对象有着较低的相似度。相似度根据簇内所有对象的均值度量，可以看作簇的质心。其算法流程如下：
1）在数据样本中随机选取k个点作为聚类中心点；
2）对待聚类的点进行遍历，找到距离各自最近的中心点，并加入到该簇中，产生一个初始的聚类结果，完成第一次迭代过程；
3）每个簇重新计算距离的均值，并将这个均值作为新的聚类中心；
4）重复进行步骤2）3），直到聚类结果趋于收敛。
利用MapReduce实现K－means算法时，Map函数将每个待聚类的点分配给最接近的聚类中心点，Reduce函数负责将更新新的聚类中心点。
Map函数的输入是来自数据源中的键值对，每一个键值对代表数据源中的一条记录。其中的键表示当前数据片距离数据起始点的位置偏移，其值为当前数据片中所包含的字符串。此时，整个数据集已被分割成M片，同时提交给M个Map任务，从而进行并行的距离计算。对于每个Map任务，分布式K－means算法会将簇的ID作为键，将计算得出的聚类中心及包含的样本数量作为值，保存到中间键值对中，提交给Reduce函数。
在Map过程中会产生大量的数据，中间数据被存储在各节点主机的本地磁盘，可以节约网络通信成本。Reduce函数将对各个Combine函数的输出值进行计算，包括迭代次数、簇的ID、新的聚类中心、簇的大小、以及迭代是否可以继续等信息。
2.2 PAM算法
PAM（Partitioning Around Medoids）算法，是一种基于中心点或中心对象进行划分的k中心点算法。是最早提出的k中心点算法之一。它首先在数据集中确定k个初始对象作为代表进行聚类，找出每个簇中最好的对象的集合作为下次迭代中的的代表对象。n次迭代后，最终集合中的代表对象即为簇的代表中心点。其算法流程如下：
1）在数据集中随机选择k个对象作为初始中心点；
2）将数据集中的每个对象分配到距离它最近的中心点所构成的簇中，形成k个簇；
3）重新计算每个簇的中心位置，选择最靠近中心的对象作为新的中心点；
4）重复 2）、3）步，直至各簇不再变化，说明各簇已趋于稳定。
利用MapReduce实现PAM算法时，Map函数为每个对象寻找最近的中心点，并将对象分配给对应的簇，其输入为<簇id，对象>，输出为<新簇id，对象>。Reduce函数负责查找簇中的新的中心点，并将其制定为下次迭代中新的聚类中心，其输入为<簇id，簇中所有对象>，输出为<簇id，新的聚类中心>。
与K－means算法类似，每次迭代完成后都要启动一个新的MapReduce任务，由Map来计算每个对象所属的簇，而由Reduce找出每个簇的中心，直到簇中心点不再改变为止。
2.3 CLARA算法
CLARA（Clustering Large Application）算法是 k－中心点算法针对与大数据集合的一种变种，其思想是基于抽样的，即不考虑整个数据集合，仅在部分抽样中选取中心点。如果抽样是以非常随机的方式选取时，那么它对原有的数据集应有较高的代表性。其算法流程如下：
1）从数据库中随机抽样，调用PAM方法从抽样中选取k个最优中心点；
2）将k个中心点应用在整个数据库中，进行聚类；
3）计算上一步中的聚类总代价，若该值小于当前最小值，则替换当前最小值，保留当前聚类结果作为当前最优聚类结果；
4）循环执行1）～3）步，直到聚类总代价小于预定最小值或达到预定迭代次数。
与K－means算法和PAM算法不同，在MapReduce中实现CLARA算法时，可以将算法步骤转换为两个MapReduce作业，同时执行不同的任务。
第一个MapReduce作业是从数据源中随机选取子集，分别用PAM进行聚类，输出结果，即聚类中心点k。在此作业中，Map函数对所有对象附加一个随机的键random-key。Reduce函数仅读取前n个对象，以random-key的升序进行排列，由于random-key是随机分配的，因此此时对象的排序是完全随机的。对这n个对象执行PAM聚类，找到k个不同的候选中心点。
第二个MapReduce作业是将k放在整个数据集中，对其进行聚类质量计算，并完成本次迭代。在此作业中，Map函数为每个对象找到其最接近的中心点，并计算相对距离，并产生一个输出，以<候选集ID，距离列表>的形式传递给Reduce函数。在Reduce函数中，将候选集ID一样的输出结果相加，得到Reduce的输出结果。即在一个候选集内，每个对象到与最近的中心点的距离之和。最小的输出结果所对应的候选集便是最佳的聚类结果。
2.4 小结
以上3种算法中，K-means算法和PAM算法类似，都需要在每次迭代后重新从文件系统中读取输入数据，而每次迭代都启动一个新的MapReduce作业，作业数量是随着迭代次数的增加线性增长的。而CLARA算法中，执行不同任务的MapReduce作业总是2个，因此CLARA算法能够更好地适应MapReduce框架。
同时，也有一些不适合MapReduce进行分布式化的算法存在，如共轭梯度法等，这些算法的一个普遍特征是迭代复杂，每次迭代都需要执行一个或者更多个MapReduce作业，当迭代次数增加时，需要调度的MapReduce任务也越来越多，造成了大量的时间开销，而真正用于计算的时间却相对较少。对此，Seo S等人对MapReduce进行了优化，提出了一种有效的解决办法[6]。
3 实验分析
在本节中，我们将上述算法在MapReduce框架中进行了实现，并对节点数量对算法性能的影响进行了评估。由于各个算法本身所具有的性质不同，因此对于同样的数据集，其聚类速度和聚类结果有着固有的差异。在这里我们仅将数据集大小和节点数目作为变量，对各算法进行纵向对比，并不关注各算法本身的性能差异。为验证节点数对算法性能的影响，我们对3个算法均使用500 KB，50 MB，1 GB的数据源在节点的数量从1到4的条件下进行聚类。所有实验均在Hadoop平台中进行，使用的Hadoop版本为1.2.1，Java版本为6u33。
由以上实验结果可以看出，对于同一个数据集，随着分布式系统中的节点数量的增加，对该数据集的聚类速度越快，但每增加一个节点所带来的速度提升就越少。这是因为随着节点的增多，在网络通信、任务调度上所带来的开销就越大。因此可以推定，增加k个节点最多只能提升k倍的效率，并且在k趋于某一临界值时，效率提升趋于0。由图2、图3、图4中可以看出，对于无论哪种算法，当数据集越大时，节点增加所带来的速度提升越明显；同时，当节点数目不变时，越大的数据集速度提升的越多。
图2 K-means算法实验结果Fig.2 K-means algorithm results
图3 PAM 算法实验结果Fig.3 PAM algorithm results
图4 CLARA算法实验结果Fig.4 CLARA algorithm results
4 结束语
随着云计算的快速发展以及人们对互联网数据分析的迫切需要，使得分布式技术成为了数据挖掘的必备工具。本文介绍了当下广泛应用的分布式计算模型MapReduce的工作原理，讨论了3种传统数据聚类算法的并行化实现原理，并分别进行了实验分析，讨论了影响算法并行效率的相关因素。后续我们将进一步对更多的传统聚类算法的分布化进行实验，并对其算法复杂度的分析和优化进行更深入的研究。
[1]Chu C，Kim S K，Lin Y A，et al.Map-reduce for machine learning on multicore[J].Advances in neural information processing systems，2007（19）:281.
[2]Dean J，Ghemawat S.MapReduce:simplified data processing on large clusters[J].Communications of the ACM，2008，51（1）:107-113.
[3]Gordon S.Linoff， MapReduce and K-Means Clustering，[EB/OL]，（2008-02-09）， [2014-3-5]http://blog.data-miners.com/2008/02/mapreduce-and-k-means-clustering.html.
[4]Jiawei H，Kamber M.数据挖掘：概念与技术[M].范明，孟小峰.北京：机械工业出版社，2001.
[5]Zhao W，Ma H，He Q.Parallel k-means clustering based on mapreduce[C]//Cloud Computing.Springer Berlin Heidelberg，2009:674-679.
[6]Seo S，Yoon E J，Kim J，et al.Hama:An efficient matrix computation with the mapreduce framework[C]//Cloud Computing Technology and Science （CloudCom）， 2010 IEEE Second International Conference on.IEEE，2010:721-726.
