云环境下基于MaPReduce的用户聚类研究与实现

樊同科

（西安外事学院现代教育技术中心，陕西西安710077）

云环境下基于MaPReduce的用户聚类研究与实现

樊同科

（西安外事学院现代教育技术中心，陕西西安710077）

基于大数据背景下海量数据人们无法理解，聚类效率低下等问题，采用MapReduce编程模型将Canopy聚类算法和K_means聚类算法在云环境中相结合，使之能够充分利用Hadoop集群的计算和存储能力。以淘宝网上海量的购买用户聚类作为应用背景，通过使用Hadoop平台的数据挖掘组件Mahout对用户聚类进行了实例研究，并给出了使用Mahout进行挖掘的一般步骤。结果表明，基于MapReduce的聚类算法在大规模数据集上具有较好的聚类质量和运行速度。

Hadoop；MapReduce；聚类算法；Mahout

随着信息技术的进步以及信息化社会的发展，出现各式各样的海量数据，大量的数据累积在数据库和数据仓库中，理解它们已远远超出了人的能力。如何将这些堆积的“数据”转变成人们理解的“知识”，数据挖掘技术应运而生［1］。从技术角度看，数据挖掘是从大量的、不完全的、有噪声的、模糊的、随机的、看似杂乱的实际数据中，提取隐含在其中的、人们不知道的，但又是潜在有用的信息和知识的过程。聚类分析［2］是一项非常实用的数据挖掘技术。但面对庞大的数据集规模，计算的效率受限于单机处理能力。如何提高海量数据下的聚类分析能力是迫切需要解决的问题。Goog1e实验室提出的分布式并行编程模型或框架MapReduce［3］，它通过集群来处理海量数据，是云计算平台主流的并行数据处理模型［4_5］。

Apache推出的Hadoop平台用Java实现了MapReduce模型。Mahout是Hadoop平台的组件之一，是一个机器学习和数据挖掘库，它利用MapReduce编程模型实现了数据挖掘中的众多算法，且具有良好的可扩展性。文献［6］对Canopy聚类进行了研究，文献［7］对K_means聚类算法的MapReduce并行化进行了研究，但K_means算法与Canopy算法各有优缺点。本文在此基础上，将两者进行了结合，并基于Mahout进行了聚类实例研究。

1　HadooP技术框架研究

1.1HadooP简介

Hadoop［8］是Apache基金会旗下的一个开源云计算平台，是由一系列软件库组成的框架。这些软件库也可称作功能模块，它们各自负责了Hadoop的一部分功能，其中最主要的是远程过程调用模块Common、存储系统HDFS和计算模型MapReduce。Hadoop被部署在一个通过网络互连的计算机集群上，集群里的每一台计算机称作一个节点。这个集群的特点就是它具有十分可观的海量数据吞吐能力，并且能够实现分布式存储和分布式计算，扩展能力十分优秀［9］。

1.2MaPReduce计算模型

MapReduce是一种新型的并行计算模型，利用分布式集群的强大资源，提供一种高效的数据计算和分析能力。MapReduce源于Goog1e发布的一篇论文，它充分借鉴了分而治之的思想，将一个数据的处理过程拆分为主要的Map与Reduce两步。即用户只需要编写自己的map（）和reduce（）函数，就能实现自己的分布式计算，并在Hadoop上运行。MapReduce具有开发简单、可扩展性强、容错性强等优点［10］。

MapReduce计算模型中的map和reduce任务能够自动地分配到集群上并发地执行。在进行计算时，map任务处理原始数据后，会输出一系列key/va1ue对作为中间结果传递给reduce任务，紧接着reduce任务处理全部具有相同key值对应的va1ue值，输出要求的key/va1ue对即可。计算过程如公式（1）所示：

｛Key1，Va1ue1｝→｛Key2，List＜Va1ue2＞｝→｛Key3，Va1ue3｝（1）

1.3Mahout简介

Mahout是Apache Software Foundation（ASF）旗下的一个开源项目，其目标是快速的建立一个可扩展的、高性能的机器学习的应用环境［11］。它是机器学习和数据挖掘的一个分布式框架，它基于MapReduce实现了机器学习的许多经典的算法，包括聚类、分类、推荐过滤、频繁子项挖掘等等。它与其他的开源数据挖掘软件的区别就是，通过使用Apache Hadoop库，Mahout可以有效地扩展到云中［12］。

2　聚类算法

2.1聚类算法简介

将数据组织到有意义的群组里是理解和学习数据的一个最基本方法［13］。聚类分析就是把若干事物按照某种标准归为几个类别，其中较为相近的聚为一类，不那么相近的聚于不同类。在聚类的过程中，没有任何关于分类的先验知识，没有教师指导，仅靠事物或样本间的相似性作为类属划分的准则，因此属于无监督分类的范畴。聚类方法尤其适合用来探讨样本间的相会关系，从而对样本结构做出初步的评价。

聚类分析的输入可以用一组有序数对（X，d）来表示。这里X表示一组用样本表示的对象描述，d用来度量样本间相似度或相异度（距离）的标准。聚类系统的输出是一个分区∧=｛G1，G2，…，GN｝，其中，GK（K=1，…，N）是X的子集，如公式（2）所示：

∧中的成员G1，G2，…，GN叫做聚类，每个聚类都通过一些特征来描述。

2.2K-means聚类算法

聚类算法中，K_means算法是使用最广泛的基于划分的算法。该算法要求事先指定k值，并随机选取K个初始质心，通过迭代操作来对数据进行聚类［14］。

假设给定n维空间上的N个样本，要将它们区分为K个聚类｛C1，C2，…，CN｝，每个分类CK包括nk个样本，每个样本正好是一个类，因此Σnk=N，其中k=1，2，…，K。用下面公式（3）的公式定义聚类CK的均值向量MK。

其中，xik是属于聚类的第i个样本，CK的方差是CK中每个样本及其重心的欧几里德距离的平方和。这个误差也叫做聚类内误差，如公式（4）所示：

包含K个聚类的整个聚类空间的平方误差是类内方差的和，如公式（5）所示。

K_means聚类方法的目标是对于给定的K，找出使E2K最小的、包含K个聚类的一个分区。

K_means算法的基本步骤是：

1）选择一个初始分区，其中的K个聚类含有随机选择样本，然后计算这些聚类的重心。

2）把样本分配给与其重心距离最近的聚类，生成一个新分区。

3）计算新聚类的中心，作为该聚类的重心。

4）重复步骤2）和3），直到求出标准函数的最优解（或直到聚类的成员稳定）。

K_means聚类是一种快速聚类方法，但对于异常值或极值比较敏感，稳定性差，比较适合处理分布集中的大样本数据集。

2.3CanoPy算法

传统的聚类算法对于一般的应用问题（基本都是小数据量）都是可以解决的，但是当数据变得很大的时候，就有点“力不从心”了。Canopy算法就是在传统聚类算法基础上发展起来的一种改进算法。

Canopy算法的主要思想是把聚类分为两个阶段：阶段一，通过使用一个简单、快捷的距离计算方法把数据分为可重叠的子集，称为“canopy”；阶段二，通过使用一个精准、严密的距离计算方法来计算出现在阶段一中同一个canopy的所有数据向量的距离。这种方式和之前的聚类方式不同的地方在于使用了两种距离计算方式，同时因为只计算了重叠部分的数据向量，所以达到了减少计算量的目的［15］。

2.4基于MaPReduce的CanoPy-Kmeans算法

K_means算法具有算法实现简单、计算效率较高等优点。在K_means算法中引入Canopy后，每次只比较落在同一区域内对象与中心点之间的距离，通过减少比较次数大大降低整个聚类的运行时间，提高了算法的计算效率［16］。基于MapReduce实现Canopy_Kmeans算法大致需要两个步骤：

1）生成Canopy的过程。在map输入阶段，整个数据集被自动切片，这样每个map任务的输入可以被看做是数据集的一部分。在map阶段，每个map任务会执行Canopy算法，生成一些canopy，最后将其全部分发到一个reduce上。在reduce阶段，将接收到的所有canopy取其中心，再执行一次Canopy算法，这样reduce输出的Canopy的中心就可以作为K_means算法的初始聚簇中心。

2）K_means过程。K_means算法是一个迭代型的算法，这里只取K_means的一次迭代，假设初始聚簇中心的个数为2。Map阶段，根据输入的两个初始聚簇中心，在每个map任务中，将输入的点归到最近的聚簇中心得到新的聚簇中心并输出。在shuff1e阶段，会根据map任务输出的聚簇中心的id分发至不同的reducer里，所以reducer的数量与初始聚簇中心的数目，即K值一致。在reduce阶段，计算一次平均值并输出，就得到了两个新的聚簇中心。这两个新的聚簇中心将作为下一次迭代的输入，不停循环，直到收敛。

3　基于Mahout的聚类实例

Apache Mahout本质上就是一个用MapReduce实现的算法库，能够在Hadoop上运行并具有极强的扩展性，是大数据处理的利器。文中以Mahout对淘宝网中购买某类商品的用户进行聚类。首先根据维度从数据仓库中提取需要的数据，并将其整合到一张表并做数据归一化处理，作为Mahout的输入，接着执行聚类操作，最后再将聚类输出数据和聚类输入数据整合得到左后结果数据［17］。

1）提取数据并做归一化。从购物网站的数据库中提取用户订单数（SubTota1）、用户订单评价金额（OrdersCount）、用户访问次数（SessionCount）3个字段作为分析维度。其中用户订单数、用户订单评价金额取自订单表（Orders），用户访问次数取自用户点击表（C1ickstrea）。将提取的数据保存在Hive的新表c1uster_input中，对这些数据进行归一化处理后，继续保存在c1uster_input表中。这里用Z分数法进行归一化处理。语句如下：

Hq1=”INSERToverwritetab1ec1uster_inputse1ect （SubTota1_avg_SubTota1）/std_SubTota1，（OrdersCount_ avg_OrdersCount）/std_OrdersCount，（SessionCount_ avg_SessionCount）/std_SessionCountfromc1uster_inputjoin （se1ectstd（SubTota1）std_SubTota1，std（OrdersCount）std_ordersCount，std（SessionCount）std_SessionCountfrom c1uster_input）t1 on 1=1 join（se1ect avg（SubTota1）avg_SubTota1，avg（OrdersCount）avg_OrdersCount，avg（SessionCount）avg_SessionCount from c1uster_input t2 on 1=1”j

HiveUti1.execute_she11（hq1）

2）使用Mahout进行聚类

使用Mahout将c1uster_input表中的数据进行聚类，主要的main函数如下：

Private static void main（String［］args）throws Exception｛

String outputPath=args［0］j

String inputPath=args［1］j

doub1e t1=Doub1e.parseDoub1e（args［2］）j

doub1e t2=Doub1e.parseDoub1e（args［3］）j

doub1e convergenceDe1ta=Doub1e.parseDoub1e（args［4］）j

int maxIterations=Integer.parseInt（args［5］）j

path output=new Path（outputPath）j

path input=new Path（inputPath）j

Configuration conf=new Configuration（）j

HadoopUti1.de1ete（conf，output）j

Run（conf，input，output，new Euc1ideanDistanceMeasure（），t1，t2，convergenceDe1ta，maxIterations）j｝

最后，需要编写一个run函数。Run函数主要包括4个步骤：1）将输入文件序列化；2）生成Canopy；3）利用生成的Canopy执行K_means聚类；4）将聚类输出。在执行过程中，生成Canopy的速度很快，而K_means的迭代过程比较耗时。

4　结束语

文中在对Hadoop云计算平台、MapReduce计算模型、Mahout机器学习算法库研究的基础上，对Canopy算法和K_ means算法的聚类过程进行了分析研究，提出将两者进行结合，以提高海量数据的聚类效率。以用户聚类为例，基于Mahout的数据模型对数据进行归一化并进行了聚类实现。结果表明，在云环境中，基于Mahout的算法库对大规模数据进行挖掘分析具有重要的现实意义。

［1］Han J，Kamber M，Pei J.数据挖掘：概念与技术［M］.范明，孟小峰，等译.北京：机械工业出版社，2012.

［2］Wu X，Kumar V.数据挖掘十大算法［M］.李文波，吴素研，等译.北京：清华大学出版社，2013.

［3］Dean J，Ghemawat S.MapReduce：simp1ified data processi_ ng on 1arge c1usters［J］.Communications of the ACM，2008，51 （1）：107_113.

［4］High1and F，Stephenson J.Fitting the Prob1em to theParadigm：A1gorithmCharacteristicsRequiredforEffectiveUseof MapReduce［J］.Procedia Computer Science，2012（12）：212_217.

［5］Po1o J，Carrera D.Performance_driven Task Cosche_du1ing for MapReduceEnvironments［C］//Proc.OfIEEENetwork Operations and Management Symposium.［S.1］：IEEE Press，2010：373_380.

［6］余长俊，张燃.云环境下基于Canopy聚类的FCM算法研究［J］.计算机科学，2014，11（41）：316_319.

［7］江小平，李成华，向文，张新访，颜海涛.K_means聚类算法的MapReduce并行化实现［J］.华中科技大学学报，2011，6（39）：120_124.

［8］We1come to Apache Hadoop［EB/OL］.（2015_10_31）.http：//ha_ doop.apache.org/.Last Pub1ished：10/31/2015.

［9］蔡斌，陈湘萍.Hadoop技术内幕：深入解析Hadoop Common 和HDFS架构设计与实现原理［M］.北京：机械工业出版社，2013.

［10］董西成.Hadoop技术内幕：深入理解MapReduce架构设计与实现原理［M］.北京：机械工业出版社，2013.

［11］Apache Mahout：Sca1ab1e machine 1earning and data mining ［EB/OL］.http：//mahout.apache.org/.

［12］Giacome11i P.Mahout实践指南［M］.靳小波，译.北京：机械工业出版社，2014.

［13］Tan P N.Introduction to data mining［M］.Pearson Education India，2007.

［14］Wikipedia.k_means_c1ustering［EB/OL］.［2015_12_08］http：// en.wikipedia.org/wiki/k_means_c1ustering.

［15］樊哲.Mahout算法解析与案例实战［M］.北京：械工业出版社，2014.

［16］李应安.基于MapReduce的聚类算法的并行化研究［D］.广州：中山大学，2010.

［17］范东来.Hadoop海量数据处理：技术详解与项目实战［M］.北京：人民邮电出版社，2015（3）：290_296.

Research and lmPlementatlon of user clusterlng based on MaPReduce ln cloud enVlronment

FAN Tong_ke
（Modern Education Technology Center，Xi'an International University，Xi'an 710077 China）

Poor understanding and 1ow c1ustering efficiency of massive data is a prob1em under the context of big data.To so1ve this prob1em，MapReduce programming mode1 is adopted to combine Canopy and K_means c1ustering a1gorithms within c1oud computing environment，so as to fu11y make use of the computing and storing capacity of Hadoop c1ustering.Large quantities of buyers on taobao are taken as app1ication context to do case study through Hadoop p1atform's data mining set Mahout.Genera1 procedure for miming with Mahout is a1so given.C1ustering a1gorithm based on MapReduce shows preferab1e c1ustering qua1ity and operation speed.

HadoopjMapReducejc1ustering a1gorithmjMahout

TN911.7

A

1674_6236（2016）10_0035_03

2015_12_14稿件编号：201512153

2015年陕西省教育厅科学研究项目（15JK2113）；2014年度陕西省教育科学“十二五”规划课题（SGH140867）

樊同科（1979—），男，陕西扶风人，硕士，副教授。研究方向：数据挖掘。