基于云计算与非负矩阵分解的数据分级聚类

赵艳萍+徐胜超

摘 要： 为了提高传统数据聚类算法在大数据挖掘应用中的性能，借助云计算的相关技术，并结合非负矩阵分解方法设计并实现了一种并行的数据层次聚类算法。该算法采用MapReduce编程平台，利用Hadoop的HDFS存储大容量的电信运营商数据；描述了MapReduce的数据分级聚类并行处理的工作机制与流程；通过Map和Reduce这种主?从编程模式很方便地使数据分级聚类的子任务在Hadoop的PC集群上运行。实验结果表明，该方法比传统用于数据聚类的非负矩阵方法具有更好的运行时间与加速比，能够在可以接受的时间范围内完成电信运营商的大数据处理。

关键词： 云計算； 分级聚类； MapReduce； 非负矩阵分解； 聚类算法； 并行数据

中图分类号： TN911.1?34； TP393.03 文献标识码： A 文章编号： 1004?373X（2018）05?0056?05

Abstract： In order to improve the performance of traditional data clustering methods on big data mining application， a parallel data hierarchical clustering algorithm was designed and realized by means of the correlation technologies of cloud computing and non?negative matrix factorization （NMF） method. The MapReduce programming platform is used in the algorithm. The HDFS （Hadoop distributed file system） based on Hadoop is used to store the large?capacity data of telecom operators. The working mechanism and flow of data hierarchical clustering based on MapReduce are described in detail. The master?slave programming mode based on Map and Reduce makes the subtask of data hierarchical clustering operating on PC clusters based on Hadoop easily. The experimental results show that， in comparison with the traditional non?negative matrix method used in data clustering， the proposed method has shorter run time and smaller speedup ratio， and can realize the big data processing of telecom operator within the acceptable time.

Keywords： cloud computing； hierarchical clustering； MapReduce； non?negative matrix factorization； clustering algorithm； parallel data

0 引 言

近年来移动互联网与物联网的急速发展积累了大量的数据资源，这些海量数据中蕴藏着大量可以应用于个性化商务的有效信息[1?3]，然而传统的数据挖掘技术是主要应用于中小规模数据中的信息挖掘，为了从海量数据资源中挖掘出有用信息，必须采用新型的数据挖掘技术，其中基于多维数据相似性的数据聚类作为一种新型数据挖掘技术正好解决上述问题。

非负矩阵分解NMF（Non?negative Matrix Factorization）方法在多维数据相似性的数据聚类、文本聚类、社交网络聚类中都得到了广泛应用，但其串行计算的时间复杂度较高，很难胜任大数据处理任务。早期在多维数据相似性的数据聚类并行处理领域中，有集群计算机与共享内存计算的方式，还有网格计算、对等计算、广域分布式计算等模式，这些模型都取得了很好的成果。但是在云计算、大数据时代，前期的分布式计算模式对海量的PB级的数据处理往往显得不足[4?5]，所以基于云计算的数据分级聚类应该得到足够的重视[6]。因此本文试图探索利用云计算方式优化传统的基于非负矩阵分解的数据相似性聚类方法。

云计算中的MapReduce技术[7]最早被Google用于大数据并行处理，其基本思想是将大数据集分解为成百上千的小数据集splits，采用Mapper和Reducer形式的类似主?从（Master?Slave）模式的并行处理。这一方法由于可以实现海量数据的并行处理，通过PC机就可以实现大型机才能完成的计算任务，因此近年来得到了广泛应用。

本文以基于非负矩阵分解的高维数据相似性聚类算法作为研究对象，以某电信运营商的大容量数据作为实验对象，设计了一种层次聚类方法并实现了数据聚类方法的MapReduce并行化，同时将该算法在Hadoop平台上进行实验和评估，最后的实验结果验证了该算法的高效性与可扩展性。

1 预备知识

1.1 高维数据相似性聚类与非负矩阵分解

相似性聚类[8]是基于数据在不同维度上的相似程度而对数据进行分类，两个数据点是否归于同一类，判断它们的相似度如何。当它们之间的相似度大于某一值时，则归于同一聚类；否则，两个数据点则分属不同的聚类。endprint

由于实际问题中大规模数据的存在，使得存储这类大数据的矩阵非常庞大，且存放的信息分布不均匀，导致现有方法很难高效快速地处理矩阵存放的数据。为了更好地处理这类数据，一类有效的方法是对矩阵进行分解，从而使得描述问题的维度大大消减，同时也能够对数据进行压缩和概括。针对这一点，目前已有很多矩阵分解方法，如奇异值分解、独立成分分析、主成分分析等。基于非负矩阵分解[9]的聚类分析所输出的分解结果可以保证其元素非负，代表真实的物理意义，因此近年来得到特别关注。

基于非负矩阵分解NMF的聚类[10]方法如下：考虑到数据集可以表示为一个向量集而每一个向量代表维数据点， NMF方法的目的是将划分为两个非负低秩矩阵和可通过尽量优化如下公式实现：

根据文献[10]，可以通过以下的乘法更新规则得到：

经过迭代处理后，得到大小为的网络的分割矩阵，其中第行对应第个单元在聚类类型中的成员关系。进一步将标准化，使这样就对应于第个单元属于第个数据聚类的后验概率。

1.2 MapReduce编程模型

Hadoop是一个分布式系统基础框架，它的核心是分布式文件系统机制HDFS（Hadoop Distributed File System）和MapReduce的主?从模式（Master?Slave）的编程机制。MapReduce框架由JobTracker和TaskTracker共同组成，它们分别担任管理节点和执行任务节点的角色，这两个有机结合，从而实现MapReduce的正常运转，保证任务的执行。

MapReduce数据相似性聚类并行处理的工作机制与流程如图1所示，具体步骤如下：

1） 对输入的大数据文件进行设置与切片；

2） 主节点（Master）调度从属节点（Worker）执行Map子任务；

3） 从属节点读取输入源片段；

4） 从属节点执行Map子任务，并将临时结果文件保存在本地；

5） 主节点调度从节点执行Reduce子任务，Reduce阶段的从属节点读取Map子任务的输出文件；

6） 执行Reduce子任务，将最后的结果保存到HDFS分布式文件系统中。

有了这6个步骤，数据分级聚类的编程人员就可以摆脱本身分布式计算的编程细节，可以使用高级语言在规定时间内完成大规模的数据分级聚类。

另外，要实现本文的并行数据聚类算法，必须用到Hadoop的开源实现，目前比较好的是Apache的Hadoop实现，访问地址为http：//hadoop.apache.org/，Apache的Hadoop基于Java环境，它实现了HDFS文件系统和MapReduce。用戶只要继承MapReduceBase，提供分别实现Map和Reduce的两个类，并注册Job即可实现自动分布式运行。

2 NMF算法的MapReduce并行化实现

2.1 基于非负矩阵分解的并行式分级聚类

现有的基于相似性的数据聚类往往根据任意两个高维数据在各个维度上的欧几里德距离的紧密程度将数据划分为几个不同的聚类，属于同一聚类的数据之间的相似度较高，属于不同聚类的数据之间的相似度相对较低。然而这一方法的局限在于，无法像模块度算法[11]那样计算聚类的模块度；无法对聚类内部的相似程度进行排序。

因此，提出基于合适的相似性度量指标来构建高维数据的相似性矩阵，通过对数据集的相似性矩阵进行非负矩阵分解来聚类相似程度较高的数据集合，将新的聚类视为新的数据点，从而在缩小数据规模的同时增加数据的维度，然后重新计算当前数据的相似性矩阵进行非负矩阵分解，反复迭代，直至得到一个较优的聚类序列。在这一计算过程中，计算量较大的阶段是反复计算数据点彼此之间的相似程度。由于数据是多维的，其相似程度往往需要用给定维度数值的欧几里德距离或余弦相似性来描述，在重构相似性矩阵时的计算量非常大，因此，本文在此阶段借用MapReduce分布式编程模型的优势，极大地提高了计算效率。

2.2 基于MapReduce的并行数据处理

首先是大数据存储的问题，可以参考利用HDFS来管理这些海量数据。HDFS的设计本质上是为了大量的数据能横跨成百上千台机器，但是看到的是一个文件系统而不是很多文件系统，对用户透明。例如，MapReduce系统要获取/hdfs/tmp/file1的数据，程序设计中引用的是一个文件路径，但是实际的数据存放在很多不同的机器上。HDFS为用户管理这些海量数据，并通过MapReduce编程模式让其在Hadoop集群上分布运行[12]。

考虑到影响分级聚类算法性能的主要因素是如何计算高维数据彼此之间的相似性，由于该相似性需要同时度量单一数据点在多个数据维度上与其他所有数据点的差异，因此，很适合使用MapReduce进行计算。给定迭代次数，即分级次。级聚类算法表述如下：

步骤1： 将初始聚类序列分割为给定的个片段，对应分配到个Map任务，基于给定指标计算聚类上下文的相似性，利用Reduce框架输出各聚类对之间的相似性集合，重构当前聚类之间的相似性矩阵；

步骤2：输入上一级聚类的相似性矩阵，基于非负矩阵分解输出当前对应聚类ID的归属度。重构当前级别下的聚类序列，输出当前级别下的聚类集合；

步骤3： 重构当前聚类的上下文。重复步骤1， 步骤2共次；

步骤4：输出最终分级聚类结果。

整个算法的框架图如图2所示。

利用本文非负矩阵分解的并行数据处理中Map函数相应的伪代码如下：

Input： text key，vector value

Output：context context

Begin

1： for i=0 to n （cluster sequence） do

2： t=findCatalog（i）；

3： for all k（* textfile） do

4： distance=cosinedistance（k，ji）；

5： context， write（key， vector（t，Distance））；

6： end for

7： end for

End

Reduce函数相应的伪代码如下：

Input： text key， vector value

Output： text key， vector value， context context

Begin

1： for all key and value do

2： array list （vector（t，value））；

3： sort（array list）；

4： new arraylist result

5： if k

6： for i=0 to k do

7： result， add（key，arraylist.get（i））；

8： else

9： system.out，println（“no sufficient training smaples”）

10： context.write（key，tradition KNN（result））；

11： end for

12： end if

End

在MapReduce编程模型中，HDFS将大数据分割成若干blocks，然后存储在不同的节点上。每个节点根据Map函数指定的操作在本地完成相应的功能。

3 实验结果与讨论

3.1 实验数据的选取

作为积累大数据的典型行业，电信行业积累了大量的手机用户行为数据，数据里包括用户拨出电话的基站信息、通话时间、通话时长等丰富信息。这些数据可以用来研究用户之间形成的社交网；另一方面，由于这些行为数据具有地理上下文，因此，也可以基于网络理论结合地理属性研究城市中不同区域之间的关系与功能。

然而，若将区域视为网络中的点，则区域覆盖的基站的数据容量使得该点拥有极高的数据维度，具有上十万用户、上百万的通话记录数，容量都是PB级的。如果用數据库连接查询以及普通的计算平台来计算上述地理空间网络，效率会比较低，甚至难以接受超长的时间，所以本文提取上述电信运营商数据作为实验环境，构造空间网络关系的平台是Hadoop集群。

本文搭建的集群中共有8个节点：1个Master节点和7个Slave节点，所有节点的硬件配置如下：CPU型号 为Intel Xeon E5 3.5 GHz； 内存设为 8 GB。硬盘容量设为1 TB； 这些节点之间通过局域网内的100M网卡连接，具体信息如表1所示。

8个节点上均是RedHat系统，其中Master机器主要配置NameNode和JobTracker，NameNode负责对文件系统的命名空间进行管理，JobTracker负责任务的调度和分发。7个Slave机器主要配置DataNode和TaskTracker，DataNode负责对数据进行分布式存储，TaskTracker主要负责接收JobTracker分发的任务并执行具体的数据处理任务。

3.2 实验结果分析

利用某电信运营商的数据，表2列出了利用本文的数据聚类分析并行处理后的计算结果，从实验结果可以看出，算法的测试结果符合预想的情况，在算法的步骤1阶段，需要的时间比较长，差不多4 h，半个工作日内能够完成，并行处理基本能满足实际大数据处理的需求，然而传统的单机条件下需要30多个小时。在步骤3的阶段比较短，虽然并行处理的时间超过了单机（因为有了通信开销），但是相对于算法的整个过程是不影响速度的。

以上是并行处理与串行单机的比较结果，步骤1～步骤3一共只要4个多小时，而串行单机（一个节点）要30多个小时。但是结果是与串行的比较，而不是并行单节点的比较（接下来看到一个Master，一个Slave共需要的时间是50 h左右）。

接着同时测试了集群配置不同节点数量（2～8个，都只有1个Master，1～7个Slave）条件下算法的处理性能。图3表明整个算法（步骤1～步骤3）随着节点数的增加而运行时间相应减少。

加速比是衡量一个系统扩展性优劣的主要指标，其表达式为：

从图3中可看出，整个数据聚类算法的时间随着节点的增加而急剧减少。

图4为聚类算法的可扩展性测试结果。

从图4中可看出，多台计算机能够很好地缩短所需时间，这说明MapReduce在处理数据聚类分析算法上具有较好的加速比，当节点数更多时，这种性能优势将更加明显。在一定的规模范围内，系统具有很好的可扩展性。

4 结 论

本文提出云计算环境下基于相似性高维数据的聚类算法的并行化实现。根据非负矩阵分解和聚类方法的特点设计了Map和Reduce函数，并将该算法在Hadoop平台下进行性能测试。实验结果表明，基于MapReduce的算法具有良好的扩展性和加速比。在数据量急剧增长的大数据时代，在云计算平台上实现基于MapReduce的数据挖掘算法具有重要的意义。

注：本文通讯作者为徐胜超。

参考文献

[1] ZHENG Y， CAPRA L， WOLFSON O， et al. Urban computing： concepts， methodologies， and applications [J]. ACM transactions on intelligent systems and technology， 2014（1）： 1?9.

[2] 李应安.基于MapReduce的聚类算法的并行化研究[D].广州：中山大学，2011.

LI Y A. Research on parallelization of clustering algorithm based on MapReduce [D]. Guangzhou： Sun Yat?sen University， 2011.

[3] 曹泽文，周姚.基于MapReduce的JP算法设计与实现[J].计算机工程，2012，38（24）：14?16.

CAO Z W， ZHOU Y. Design and implementation of JP algorithm based on MapReduce [J]. Computer engineering， 2012， 38（24）： 14?16.

[4] 杨燕，王全根，黄波.蚁群聚类算法的并行化设计与实现[J].控制工程，2013，20（3）：411?414.

YANG Yan， WANG Quangen， HUANG Bo. Parallel design and implementation of ant colony clustering algorithm [J]. Control engineering of China， 2013， 20（3）： 411?414.

[5] 杨慧中，董陶，陶洪峰.基于改进K?means聚类算法的组合模型建模[J].控制工程，2013，20（2）：201?203.

YANG Huizhong， DONG Tao， TAO Hongfeng. Combination model based on improved K?means clustering algorithm [J]. Control engineering of China， 2013， 20（2）： 201?203.

[6] 李欢，刘锋，朱二周.基于改进K?means算法的海量数据分析技术研究[J].微电子学与计算机，2016，33（5）：52?57.

LI Huan， LIU Feng， ZHU Erzhou. Research of an improved K?means algorithm for analyzing mass data [J]. Microelectronics & computer， 2016， 33（5）： 52?57.

[7] LI F， OOI B C， ?ZSU M T， et al. Distributed data management using MapReduce [J]. ACM computing surveys， 2014， 46（3）： 31.

[8] 吴诗极，李川，唐常杰.面向大规模信息网络的高效自适应聚类算法[J].计算机科学与探索，2014，8（4）：406?416.

WU Shiji， LI Chuan， TANG Changjie. Efficient adaptive clustering algorithm for large scale information network [J]. Journal of frontiers of computer science & technology， 2014， 8（4）： 406?416.

[9] 任重鲁，李金明.非负矩阵分解在微阵列数据分类和聚类发现中的应用[J].计算机工程与科学，2014，36（7）：1389?1397.

REN Zhonglu， LI Jinming. Application of non?negative matrix factorization in microarray data classification and clustering discovery [J]. Computer engineering and science， 2014， 36（7）： 1389?1397.

[10] 徐森，卢志茂，顾国昌.结合K均值和非负矩阵分解集成文本聚类算法[J].吉林大学学报（工学版），2011，41（4）：1077?1082.

XU Sen， LU Zhimao， GU Guochang. Integrating K?means and non?negative matrix factorization to ensemble document clustering [J]. Journal of Jilin University （engineering and technology edition）， 2011， 41（4）： 1077?1082.

[11] 罗明伟，姚宏亮，李俊照，等.一种基于节点相异度的社团层次划分算法[J].计算机工程，2014，40（1）：275?279.

LUO Mingwei， YAO Hongliang， LI Junzhao， et al. A hierarchical division algorithm for community based on node dissi?milarity [J]. Computer engineering， 2014， 40（1）： 275?279.

[12] Hadoop. Hadoop Open source Web site 2016 [EB/OL]. [2016?10?23]. http：//hadoop.apache.org/.endprint