基于MapReduce的可扩展协同聚类算法

马 俏，万剑怡，王明文

(江西师范大学计算机信息工程学院，江西 南昌 330022)

0 引言

聚类分析是根据数据集中数据的不同特征，将数据集划分为不同的簇，使得簇内相似度尽可能高，簇间相似度尽可能低的过程。文本聚类是在传统聚类分析的基础上发展的，它基于“聚类假设”:相关文档之间的相似性比无关文档之间的相似性更大。该聚类是一种无监督的文本分类，通常采用向量空间模型来处理，它的主要思想是，每一个词都作为特征空间坐标系的一维，将文档集看作是一组正交特征向量组成的特征空间，每个文档表示为其中的一个规范化特征向量。这种描述方法简单直接，但也使得文本向量空间变得高维而且稀疏，一个文档集可能会包含数十万个不同的特征，高维的特征空间不仅增加聚类算法的处理时间，而且对算法的精度也产生影响。虽然目前有很多对文档特征降维的技术可以减少文本聚类的复杂度，但是在降低维度的同时容易删除对聚类有用的信息。为了最大限度保留这些信息，本文从另一个角度来考虑文本聚类方法——协同聚类(co-clustering)。

协同聚类又称双聚类、二模聚类，是一种允许对一个矩阵的行和列同时聚类的数据挖掘技术。众所周知，文本文档是由一系列特征构建的，而这些特征存在着潜在的相关关系，基于文档的聚类算法无法考虑到这些潜在关系，为此有人提出协同聚类的思想。这种从多维度进行聚类分析的方法对聚类效果的提高具有重要的指导意义。目前协同聚类分析方法广泛应用于文本挖掘、生物信息学、推荐系统和图挖掘等领域。文献［4］从理论上证明了协同聚类算法是收敛的。文献［3］将协同聚类算法应用到基因表达式数据，表现出良好的聚类效果。文献［2］和文献［6］分别将协同聚类算法应用到文本聚类分析和过滤推荐算法中，也取得了很好的效果。然而这些研究都是基于串行算法的，随着数据量的不断增长，势必会存在内存不足以及运行时间太长等问题。为此本文考虑运用MapReduce的并行框架对协同聚类算法进行改进，使得协同聚类算法能在保证效果的同时提高运行的效率。

MapReduce分布式编程模式是对大规模数据集进行并行计算的主要模式之一，也是目前最流行的并行计算框架。它使用简单，易于实现且扩展性强。目前，MapReduce已被广泛地应用于日志分析、海量数据的排序、在海量数据中查找特定模式等场景中。文献［4］提出了一种基于MapReduce的协同聚类算法框架，它综合了各种协同聚类算法的公共特点，以框架的形式搭建了MapReduce并行算法，这种算法简单且易于理解，但是算法的实现复杂，不利于开发人员研究具体的算法。

本文针对最小化残差平方和协同聚类算法提出更简单且更容易理解的并行协同聚类算法(MR_coclustering)，该算法采用分布式存储方式存储数据，读写速度快，存储容量大，实现了算法的可扩展性，提高算法运行速度。实验结果表明，该算法在Hadoop上的运行时间随着集群中机器结点个数的增加急剧下降，说明了算法具有很好的可扩展性。

1 协同聚类算法(co-clustering算法)

在本文中，数据集表示为文档结点的集合和特征结点的集合，其中每个文档结点与每个特征结点之间有一条边，边的权值是文档在特征上的tf-idf值。如果权值为0，则忽略该边。协同聚类试图将该图划分成不相交的簇，其中每个簇由一个文档结点集和一个特征结点集组成。该聚类的目标是最大化簇中文档结点和特征结点之间的边的权值，最小化不同簇的文档结点和特征结点之间边的权值。图1描述的是文档和特征之间的关联关系。左边{d1，...，dn}表示文档集合，右边{t1，…，tm}表示特征集合，文档与特征之间的连线rij表示文档和特征之间的关联程度。

图1 文档和特征之间的关联图

协同聚类算法的基本思想是:先初始化行列矩阵索引，迭代地对矩阵的行和列分别聚类，先对矩阵的行进行聚类，计算聚类簇中各个元素与类中心的关联关系，将其加入到与它相似度最大的一个聚类簇中。列聚类的过程与行聚类类似。每次聚类可将文档划分到与它更相似的行聚类簇中。当各个聚类簇相对稳定时停止迭代过程。调整后的聚类簇的内聚性更强，类间的区分度更大，有效地提高聚类的效果。

为了方便阅读，在介绍算法具体流程之前，首先定义一些常用到的符号，如表1所示。

表1 常用符号表示

本文采用的协同聚类算法是基于最小化残差平方和的思想。残差平方和的定义为:数据集的每个输入与协同聚类的平均值的差的平方的总和。即:

协同聚类的串行算法流程如图2所示。

从该算法中可以看出，计算最复杂的部分在第三步的迭代中，每次迭代对列聚类的时间复杂度为O(n)，更新U的时间复杂度为O(m×n)，对行聚类的时间复杂度为 O(m)。由于O(m×n)＞O(m)、O(n)，所以一次迭代的时间复杂度为O(m×n)，而由于迭代的次数不会超过设置的阈值T，所以协同聚类算法的时间复杂度为O(T×m×n)。

图2 协同聚类的串行算法

2 MapReduce分布式编程模式

MapReduce分布式编程模式是由Google实验室首先提出的，主要用于大规模数据集的并行计算。它是鉴于函数式的编程模式，把海量数据集的操作抽象为Map和Reduce两个集合操作，并且对底层分布式过程进行了封装，大大简化了程序并行化的实现。Map(映射)过程和Reduce(规约)过程是MapReduce的2个关键过程。在MapReduce计算模式中需要用户提供Map函数和Reduce函数以实现映射和规约过程，这2个函数对一组输入的键值对(key/value)进行计算，得出另一组键值对:

Map函数接收一组输入键值对(k1，v1)经过处理产生一组中间键值对(k2，v2)，然后MapReduce函数库将所有相同的k2键值对应的v2产生值的集合list(v2)，发送给Reduce函数，进一步处理、归并中间键的集合，最后形成键值对集合list(k3，v3)。图3是数据流在MapReduce计算过程中的传输过程示意图，首先将任务分割后进入Map阶段，然后将Map阶段的中间输出传递给Reduce函数，Reduce函数经过聚合输出相应的键值对。

化学是一门中心的、实用的和创造性的学科，是护理专业基础课程的基础，是医务工作者必须掌握的一门学科。21世纪是生命科学时代，医学教育进入多学科融合和创新的时期，护理人员应具备相应的理论知识和技能，以及较强的实践操作能力。为培养出合格的实用型护理人才，在化学课程中实施STS教育，培养学生科学精神，掌握科学方法，理解科学与社会、文化等的关系。更重要的是使教学与科学、技术、社会实际问题有机结合起来，突出化学和医学的社会价值，培养学生用整体、综合观点解决实际问题能力和创新能力。

图3 MapReduce数据变化的基本模型

MapReduce通过把输入数据自动分割成若干块分布到多台机器上，使输入的块能够在不同的机器上被并行处理。图4显示了一次MapReduce执行的具体流程。

MapReduce集群中有一个称为master的机器用于管理其他机器和调度作业(Map作业或者Reduce作业)，其他机器被称为worker。被分配了Map作业的worker，开始读取对应分片的输入数据，Map作业从输入数据中抽取出键值对，每一个键值对都作为参数传递给map函数，map函数产生的中间键值对被缓存在内存中。缓存的中间键值对会被定期写入本地磁盘，而且被分为R个区，R的大小是由用户定义的，将来每个区会对应一个Reduce作业;这些中间键值对的位置会被通报给master，master负责将信息转发给Reduce worker。master通知分配了Reduce作业的worker它负责的分区在什么位置，当Reduce worker把所有它负责的中间键值对都读过来后，先对它们进行排序，使得相同键的键值对聚集在一起。因为不同的键可能会映射到同一个分区也就是同一个Reduce作业，所以排序是必须的。Reduce worker遍历排序后的中间键值对，对于每个唯一的键，都将键与关联的值传递给reduce函数，reduce函数产生的输出会添加到这个分区的输出文件中。

图4 MapReduce执行流程

3 基于MapReduce的协同聚类算法

文献［5］提出了一种适合协同聚类的并行框架DisCo，可用于大规模数据的聚类分析，并给出了基于MapReduce的协同聚类算法框架。本文在该框架的基础上提出针对最小化残差平方和的协同聚类算法的改进并行算法，在本文中用MR_co-clustering表示。

本文在MapReduce框架的开源项目Hadoop上完成对协同聚类算法的实现。纵观整个协同聚类算法，运算时间主要集中在计算协同簇中心矩阵和对文档、特征聚类的过程中。而之前已经有人研究过对矩阵的并行处理以及k均值的并行实现，本文参考前人的经验，针对算法中计算耗时的部分进行并行化处理，使算法运行的时间大大缩短，提高算法的效率。

在算法中设计3个MapReduce过程。第一个MapReduce过程用于计算协同簇中心矩阵(U)，用UMapReduce表示。第二个MapReduce过程是实现对特征的聚类，用ColumnMapReduce表示。第三个MapReduce是实现对文档的聚类，用RowMapReduce表示。下面对各个MapReduce过程进行描述。

(1)UMapReduce:计算协同簇中心矩阵U。由于矩阵U的计算只与属于该行簇和列簇的元组相关，具有相对独立性，可以用MapReduce实现。针对已知的Row和Column，把文档-特征矩阵A按行划分，并行地分析每个元组行和列所属的簇，然后将属于同一行簇和列簇的元组进行求和，计算出U，这样就得到了协同簇中心矩阵。算法伪代码如图5所示。

图5 UMapReduce算法

(2)ColumnMapReduce:对特征进行聚类，将特征分配到距离该簇中心距离最小的簇中。由于每一个特征的聚类都是相对独立的，因此可以用MapReduce实现，即将特征列分发到集群的各台机器中，同时对机器中的特征聚类，输出特征聚类结果。伪代码如图6所示。

图6 ColumnMapReduce算法

(3)RowMapReduce:与Mapreduce2类似，对文档进行聚类，将文档分配到距离簇中心距离最小的簇中。将文档行分发到集群的各台机器中，并行地进行文档聚类，输出文档聚类的结果。伪代码如图7所示。

图7 RowMapReduce算法

图8描述了一次迭代的协同聚类算法的具体流程。首先将文档集和初始化的Row和Column输入UMapReducer中，计算出新的协同聚类簇中心，然后计算RU(特征的簇中心);进入第二个并行过程，对特征的聚类ColumnMapReduce，输出对特征聚类的结果Column，由于特征的聚类结果变化导致协同聚类簇中心的结果也发生变化，所以对文档-特征矩阵再进行UMapReduce过程，计算更新后的U，然后对文档进行聚类，执行RowMapReducer过程，输出文档聚类的结果，最后计算‖A-RUC‖，通过判断与迭代前的结果是否相等判断迭代是否还要再继续下去。

由于串行协同聚类算法的时间复杂度为O(T×m×n)，而并行的协同聚类算法与机器数N相关，它的时间复杂度由机器数的增加而减少，所以并行协同聚类算法的时间复杂度为O(T×m×n/N)

4 实验与结果分析

4.1 实验环境和数据集

Hadoop是MapReduce框架的开源实现，协同聚类算法的实验就是基于此框架实现的。

Hadoop集群中各节点采用相同的配置，即:Hadoop 版本为 Hadoop 0.20.203.0，操作系统为 ubuntu10.10，JDK 版本为 1.6.0;PC 机的硬件环境同为Pentium(R)Dual-core CPU E6300@2.8 GHz双核处理器，ADAT 2G内存，Hitachi 320 GB硬盘。

本实验采用的数据集是复旦中文文档集，总共有8214篇文档。预处理阶段将每篇文档进行分词，采用χ2算法选择维数，抽取了500维的特征，采用tf-idf的方法进行特征抽取。实验时采用随机初始化的原则对Row和Column进行初始化。矩阵文档36M，为了使实验结果更符合预期，将Hadoop的配置文件中的分块设置改为6M，默认情况下是64M。

4.2 实验结果

首先通过对协同聚类算法和常用聚类算法K-means的比较来说明协同聚类算法的优越性。表2显示的是K-means算法，串行协同聚类算法S_co_clustering以及本文提出的并行协同聚类算法MR_co_clustering在纯度、熵和互信息上的结果，结果表明协同聚类算法能够有效提高聚类的效果，对协同聚类算法的并行化不影响聚类的效果。

表2 K-means与串行协同聚类算法和并行协同聚类算法的结果比较

为了说明本文算法的可扩展性，对算法的执行时间与集群中的机器数的关系进行了比较。

表3显示的是一次迭代过程中，各MapReduce过程和对应的串行算法的耗时。图9是对应的折线图。表3和图9显示并行算法的运行时间随着机器数的增加而降低。

表3 一次迭代过程中3个MapReduce过程以及对应串行算法的执行时间(S_computU、S_Column、S_Row分别是计算U、对列聚类和对行聚类的串行方法)

图9 各并行阶段及对应串行算法执行时间折线图

表4显示的是并行算法和串行算法在一次迭代过程中的运行时间，包括表3中的并行过程所耗费的时间以及一些额外开销所耗费的时间。

表4 MR_co-clustering与S_co-clutering的执行时间比较(单位s)

图10 一次迭代执行时间折线图

由图9和图10可知，串行协同聚类算法运行时间几乎不受集群机器个数的影响，因为串行算法的效率只与运行该算法的机器有关，而与集群中其他机器无关;并行协同聚类算法的运行时间则与集群中机器的个数密切相关。当只有一台机器时，基于MapReduce的并行协同聚类算法比串行算法运行得更慢，这是由于集群需要耗费一定的通讯开销。但是当集群中机器数量增加时，执行时间迅速下降，当集群机器数达到6至8台时基本趋于稳定，这是由于在本文的数据集是分为6(36/6)块被分布到集群上的不同机器上的，也即MapReduce需要处理的任务有6个，所以当机器数目已经满足MapReduce分配的6个之后，增加机器不再对执行时间产生显著影响。

图11 一次迭代加速比曲线图

图11描述了MR_co-clustering算法的加速比曲线，其中各MapReduce子阶段的加速比曲线与MR_co-clustering类似。由于机器数达到6台后执行时间受影响的因素已经不是机器的个数，因此，加速比曲线图里不考虑机器数大于6台以后的现象。从图11中可以看出，随着机器数量的增长MR_co-clustering算法的加速比是趋于线性加速比的，这说明本文的算法具有很好的可扩展性。

由于在运行MapReduce过程中会产生大量中间数据，而这些中间数据直接影响算法的运行时间，为此，对中间数据的优化也是一种算法的改进措施。与DisCo算法相比，本文提出的算法在并行运算中产生的中间数据远远小于DisCo算法，有效减少了中间数据在网络中的传输时间，提高了算法的效率。

由实验结果可知，通过对文档和特征同时聚类的协同聚类算法可以有效地改善聚类的结果，而本文提出的并行协同聚类算法在提高算法效果的同时，还提高了算法的效率，达到了可扩展的并行要求。

5 结束语

本文的研究表明，对协同聚类的算法进行并行化后可以显著缩短算法的执行时间，提高聚类效率，同时，通过它的加速比可以看出该算法具有很好的可扩展性。本文提出的基于MapReduce的协同聚类算法对高维数据和大规模数据的处理具有一定意义。然而本研究还有很多值得进一步研究的地方，例如，如何初始化Row和Column使迭代更快更稳定地收敛到最合适的状态，以及k和l的值的确定。

［1］Jimmy Lin，Chris Dyer.Data-Intensive Text Processing with MapReduce［M］.Morgan ＆ Claypool Publishers，2010.

［2］王明文，付剑波，罗远胜，等.基于协同聚类的两阶段文本聚类方法［J］.模式识别与人工智能，2009，22(6):848-853.

［3］Cho H，Dhillon I，Guan Y，et al.Minimum sum-squared residue co-clustering of gene expression data［C］//Proceedings of the 4th SIAM International Conference on Data Mining.2004:509-514.

［4］Aris Anagnostopoulos，Anirban Dasgupta，Ravi Kumar.Approximation algorithms for co-clustering［C］//Proceedings of the 27th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems.2008:201-210.

［5］Spiros Papadimitriou，Jimeng Sun.DisCo:Distributed coclustering with Map-Reduce:A case study towards Petabyte-scale end-to-end mining［C］//Proceedings of the 8th IEEE International Conference on Data Mining(ICDM’08).2008:512-521.

［6］王明文，陶红亮，熊小勇.双向聚类迭代的协同过滤推荐算法［J］.中文信息学报，2008，22(4):61-65.

［7］Chuck Lam.Hadoop in Action［M］.Manning Publication，2010.

［8］George T，Merugu S.A scalable collaborative filtering framework based on co-clustering［C］//Proceedings of the 5th IEEE International Conference on Data Mining.2005:625-628.

［9］Hartigan J A.Direct clustering of a data matrix［J］.Journal of the American Statistical Association，1972，337(67):123-129.

［10］Madeira S C，Oliveira A L.Biclustering algorithms for biological data analysis:A survey［C］//IEEE/ACM Transactions on Computational Biology and Bioinformatics.2004:24-45.

［11］Banerjee A，Dhillon I，Ghosh J，et al.A generalized maximum entropy approach to Bregman co-clustering and matrix approximation［J］.Journal of Machine Learning Research，2007(8):1919-1986.

［12］Hadoop.The Apache Software Foundation［EB/OL］.http://hadoop.apache.org，2013-06-05.