云環(huán)境下基于MaPReduce的用戶聚類研究與實(shí)現(xiàn)

樊同科

（西安外事學(xué)院現(xiàn)代教育技術(shù)中心，陜西西安710077）

云環(huán)境下基于MaPReduce的用戶聚類研究與實(shí)現(xiàn)

樊同科

（西安外事學(xué)院現(xiàn)代教育技術(shù)中心，陜西西安710077）

基于大數(shù)據(jù)背景下海量數(shù)據(jù)人們無(wú)法理解，聚類效率低下等問(wèn)題，采用MapReduce編程模型將Canopy聚類算法和K_means聚類算法在云環(huán)境中相結(jié)合，使之能夠充分利用Hadoop集群的計(jì)算和存儲(chǔ)能力。以淘寶網(wǎng)上海量的購(gòu)買用戶聚類作為應(yīng)用背景，通過(guò)使用Hadoop平臺(tái)的數(shù)據(jù)挖掘組件Mahout對(duì)用戶聚類進(jìn)行了實(shí)例研究，并給出了使用Mahout進(jìn)行挖掘的一般步驟。結(jié)果表明，基于MapReduce的聚類算法在大規(guī)模數(shù)據(jù)集上具有較好的聚類質(zhì)量和運(yùn)行速度。

Hadoop；MapReduce；聚類算法；Mahout

隨著信息技術(shù)的進(jìn)步以及信息化社會(huì)的發(fā)展，出現(xiàn)各式各樣的海量數(shù)據(jù)，大量的數(shù)據(jù)累積在數(shù)據(jù)庫(kù)和數(shù)據(jù)倉(cāng)庫(kù)中，理解它們已遠(yuǎn)遠(yuǎn)超出了人的能力。如何將這些堆積的“數(shù)據(jù)”轉(zhuǎn)變成人們理解的“知識(shí)”，數(shù)據(jù)挖掘技術(shù)應(yīng)運(yùn)而生［1］。從技術(shù)角度看，數(shù)據(jù)挖掘是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的、看似雜亂的實(shí)際數(shù)據(jù)中，提取隱含在其中的、人們不知道的，但又是潛在有用的信息和知識(shí)的過(guò)程。聚類分析［2］是一項(xiàng)非常實(shí)用的數(shù)據(jù)挖掘技術(shù)。但面對(duì)龐大的數(shù)據(jù)集規(guī)模，計(jì)算的效率受限于單機(jī)處理能力。如何提高海量數(shù)據(jù)下的聚類分析能力是迫切需要解決的問(wèn)題。Goog1e實(shí)驗(yàn)室提出的分布式并行編程模型或框架MapReduce［3］，它通過(guò)集群來(lái)處理海量數(shù)據(jù)，是云計(jì)算平臺(tái)主流的并行數(shù)據(jù)處理模型［4_5］。

Apache推出的Hadoop平臺(tái)用Java實(shí)現(xiàn)了MapReduce模型。Mahout是Hadoop平臺(tái)的組件之一，是一個(gè)機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘庫(kù)，它利用MapReduce編程模型實(shí)現(xiàn)了數(shù)據(jù)挖掘中的眾多算法，且具有良好的可擴(kuò)展性。文獻(xiàn)［6］對(duì)Canopy聚類進(jìn)行了研究，文獻(xiàn)［7］對(duì)K_means聚類算法的MapReduce并行化進(jìn)行了研究，但K_means算法與Canopy算法各有優(yōu)缺點(diǎn)。本文在此基礎(chǔ)上，將兩者進(jìn)行了結(jié)合，并基于Mahout進(jìn)行了聚類實(shí)例研究。

1　HadooP技術(shù)框架研究

1.1HadooP簡(jiǎn)介

Hadoop［8］是Apache基金會(huì)旗下的一個(gè)開(kāi)源云計(jì)算平臺(tái)，是由一系列軟件庫(kù)組成的框架。這些軟件庫(kù)也可稱作功能模塊，它們各自負(fù)責(zé)了Hadoop的一部分功能，其中最主要的是遠(yuǎn)程過(guò)程調(diào)用模塊Common、存儲(chǔ)系統(tǒng)HDFS和計(jì)算模型MapReduce。Hadoop被部署在一個(gè)通過(guò)網(wǎng)絡(luò)互連的計(jì)算機(jī)集群上，集群里的每一臺(tái)計(jì)算機(jī)稱作一個(gè)節(jié)點(diǎn)。這個(gè)集群的特點(diǎn)就是它具有十分可觀的海量數(shù)據(jù)吞吐能力，并且能夠?qū)崿F(xiàn)分布式存儲(chǔ)和分布式計(jì)算，擴(kuò)展能力十分優(yōu)秀［9］。

1.2MaPReduce計(jì)算模型

MapReduce是一種新型的并行計(jì)算模型，利用分布式集群的強(qiáng)大資源，提供一種高效的數(shù)據(jù)計(jì)算和分析能力。MapReduce源于Goog1e發(fā)布的一篇論文，它充分借鑒了分而治之的思想，將一個(gè)數(shù)據(jù)的處理過(guò)程拆分為主要的Map與Reduce兩步。即用戶只需要編寫(xiě)自己的map（）和reduce（）函數(shù)，就能實(shí)現(xiàn)自己的分布式計(jì)算，并在Hadoop上運(yùn)行。MapReduce具有開(kāi)發(fā)簡(jiǎn)單、可擴(kuò)展性強(qiáng)、容錯(cuò)性強(qiáng)等優(yōu)點(diǎn)［10］。

MapReduce計(jì)算模型中的map和reduce任務(wù)能夠自動(dòng)地分配到集群上并發(fā)地執(zhí)行。在進(jìn)行計(jì)算時(shí)，map任務(wù)處理原始數(shù)據(jù)后，會(huì)輸出一系列key/va1ue對(duì)作為中間結(jié)果傳遞給reduce任務(wù)，緊接著reduce任務(wù)處理全部具有相同key值對(duì)應(yīng)的va1ue值，輸出要求的key/va1ue對(duì)即可。計(jì)算過(guò)程如公式（1）所示：

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

1.3Mahout簡(jiǎn)介

Mahout是Apache Software Foundation（ASF）旗下的一個(gè)開(kāi)源項(xiàng)目，其目標(biāo)是快速的建立一個(gè)可擴(kuò)展的、高性能的機(jī)器學(xué)習(xí)的應(yīng)用環(huán)境［11］。它是機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘的一個(gè)分布式框架，它基于MapReduce實(shí)現(xiàn)了機(jī)器學(xué)習(xí)的許多經(jīng)典的算法，包括聚類、分類、推薦過(guò)濾、頻繁子項(xiàng)挖掘等等。它與其他的開(kāi)源數(shù)據(jù)挖掘軟件的區(qū)別就是，通過(guò)使用Apache Hadoop庫(kù)，Mahout可以有效地?cái)U(kuò)展到云中［12］。

2　聚類算法

2.1聚類算法簡(jiǎn)介

將數(shù)據(jù)組織到有意義的群組里是理解和學(xué)習(xí)數(shù)據(jù)的一個(gè)最基本方法［13］。聚類分析就是把若干事物按照某種標(biāo)準(zhǔn)歸為幾個(gè)類別，其中較為相近的聚為一類，不那么相近的聚于不同類。在聚類的過(guò)程中，沒(méi)有任何關(guān)于分類的先驗(yàn)知識(shí)，沒(méi)有教師指導(dǎo)，僅靠事物或樣本間的相似性作為類屬劃分的準(zhǔn)則，因此屬于無(wú)監(jiān)督分類的范疇。聚類方法尤其適合用來(lái)探討樣本間的相會(huì)關(guān)系，從而對(duì)樣本結(jié)構(gòu)做出初步的評(píng)價(jià)。

聚類分析的輸入可以用一組有序數(shù)對(duì)（X，d）來(lái)表示。這里X表示一組用樣本表示的對(duì)象描述，d用來(lái)度量樣本間相似度或相異度（距離）的標(biāo)準(zhǔn)。聚類系統(tǒng)的輸出是一個(gè)分區(qū)∧=｛G1，G2，…，GN｝，其中，GK（K=1，…，N）是X的子集，如公式（2）所示：

∧中的成員G1，G2，…，GN叫做聚類，每個(gè)聚類都通過(guò)一些特征來(lái)描述。

2.2K-means聚類算法

聚類算法中，K_means算法是使用最廣泛的基于劃分的算法。該算法要求事先指定k值，并隨機(jī)選取K個(gè)初始質(zhì)心，通過(guò)迭代操作來(lái)對(duì)數(shù)據(jù)進(jìn)行聚類［14］。

假設(shè)給定n維空間上的N個(gè)樣本，要將它們區(qū)分為K個(gè)聚類｛C1，C2，…，CN｝，每個(gè)分類CK包括nk個(gè)樣本，每個(gè)樣本正好是一個(gè)類，因此Σnk=N，其中k=1，2，…，K。用下面公式（3）的公式定義聚類CK的均值向量MK。

其中，xik是屬于聚類的第i個(gè)樣本，CK的方差是CK中每個(gè)樣本及其重心的歐幾里德距離的平方和。這個(gè)誤差也叫做聚類內(nèi)誤差，如公式（4）所示：

包含K個(gè)聚類的整個(gè)聚類空間的平方誤差是類內(nèi)方差的和，如公式（5）所示。

K_means聚類方法的目標(biāo)是對(duì)于給定的K，找出使E2K最小的、包含K個(gè)聚類的一個(gè)分區(qū)。

K_means算法的基本步驟是：

1）選擇一個(gè)初始分區(qū)，其中的K個(gè)聚類含有隨機(jī)選擇樣本，然后計(jì)算這些聚類的重心。

2）把樣本分配給與其重心距離最近的聚類，生成一個(gè)新分區(qū)。

3）計(jì)算新聚類的中心，作為該聚類的重心。

4）重復(fù)步驟2）和3），直到求出標(biāo)準(zhǔn)函數(shù)的最優(yōu)解（或直到聚類的成員穩(wěn)定）。

K_means聚類是一種快速聚類方法，但對(duì)于異常值或極值比較敏感，穩(wěn)定性差，比較適合處理分布集中的大樣本數(shù)據(jù)集。

2.3CanoPy算法

傳統(tǒng)的聚類算法對(duì)于一般的應(yīng)用問(wèn)題（基本都是小數(shù)據(jù)量）都是可以解決的，但是當(dāng)數(shù)據(jù)變得很大的時(shí)候，就有點(diǎn)“力不從心”了。Canopy算法就是在傳統(tǒng)聚類算法基礎(chǔ)上發(fā)展起來(lái)的一種改進(jìn)算法。

Canopy算法的主要思想是把聚類分為兩個(gè)階段：階段一，通過(guò)使用一個(gè)簡(jiǎn)單、快捷的距離計(jì)算方法把數(shù)據(jù)分為可重疊的子集，稱為“canopy”；階段二，通過(guò)使用一個(gè)精準(zhǔn)、嚴(yán)密的距離計(jì)算方法來(lái)計(jì)算出現(xiàn)在階段一中同一個(gè)canopy的所有數(shù)據(jù)向量的距離。這種方式和之前的聚類方式不同的地方在于使用了兩種距離計(jì)算方式，同時(shí)因?yàn)橹挥?jì)算了重疊部分的數(shù)據(jù)向量，所以達(dá)到了減少計(jì)算量的目的［15］。

2.4基于MaPReduce的CanoPy-Kmeans算法

K_means算法具有算法實(shí)現(xiàn)簡(jiǎn)單、計(jì)算效率較高等優(yōu)點(diǎn)。在K_means算法中引入Canopy后，每次只比較落在同一區(qū)域內(nèi)對(duì)象與中心點(diǎn)之間的距離，通過(guò)減少比較次數(shù)大大降低整個(gè)聚類的運(yùn)行時(shí)間，提高了算法的計(jì)算效率［16］。基于MapReduce實(shí)現(xiàn)Canopy_Kmeans算法大致需要兩個(gè)步驟：

1）生成Canopy的過(guò)程。在map輸入階段，整個(gè)數(shù)據(jù)集被自動(dòng)切片，這樣每個(gè)map任務(wù)的輸入可以被看做是數(shù)據(jù)集的一部分。在map階段，每個(gè)map任務(wù)會(huì)執(zhí)行Canopy算法，生成一些canopy，最后將其全部分發(fā)到一個(gè)reduce上。在reduce階段，將接收到的所有canopy取其中心，再執(zhí)行一次Canopy算法，這樣reduce輸出的Canopy的中心就可以作為K_means算法的初始聚簇中心。

2）K_means過(guò)程。K_means算法是一個(gè)迭代型的算法，這里只取K_means的一次迭代，假設(shè)初始聚簇中心的個(gè)數(shù)為2。Map階段，根據(jù)輸入的兩個(gè)初始聚簇中心，在每個(gè)map任務(wù)中，將輸入的點(diǎn)歸到最近的聚簇中心得到新的聚簇中心并輸出。在shuff1e階段，會(huì)根據(jù)map任務(wù)輸出的聚簇中心的id分發(fā)至不同的reducer里，所以reducer的數(shù)量與初始聚簇中心的數(shù)目，即K值一致。在reduce階段，計(jì)算一次平均值并輸出，就得到了兩個(gè)新的聚簇中心。這兩個(gè)新的聚簇中心將作為下一次迭代的輸入，不停循環(huán)，直到收斂。

3　基于Mahout的聚類實(shí)例

Apache Mahout本質(zhì)上就是一個(gè)用MapReduce實(shí)現(xiàn)的算法庫(kù)，能夠在Hadoop上運(yùn)行并具有極強(qiáng)的擴(kuò)展性，是大數(shù)據(jù)處理的利器。文中以Mahout對(duì)淘寶網(wǎng)中購(gòu)買某類商品的用戶進(jìn)行聚類。首先根據(jù)維度從數(shù)據(jù)倉(cāng)庫(kù)中提取需要的數(shù)據(jù)，并將其整合到一張表并做數(shù)據(jù)歸一化處理，作為Mahout的輸入，接著執(zhí)行聚類操作，最后再將聚類輸出數(shù)據(jù)和聚類輸入數(shù)據(jù)整合得到左后結(jié)果數(shù)據(jù)［17］。

1）提取數(shù)據(jù)并做歸一化。從購(gòu)物網(wǎng)站的數(shù)據(jù)庫(kù)中提取用戶訂單數(shù)（SubTota1）、用戶訂單評(píng)價(jià)金額（OrdersCount）、用戶訪問(wèn)次數(shù)（SessionCount）3個(gè)字段作為分析維度。其中用戶訂單數(shù)、用戶訂單評(píng)價(jià)金額取自訂單表（Orders），用戶訪問(wèn)次數(shù)取自用戶點(diǎn)擊表（C1ickstrea）。將提取的數(shù)據(jù)保存在Hive的新表c1uster_input中，對(duì)這些數(shù)據(jù)進(jìn)行歸一化處理后，繼續(xù)保存在c1uster_input表中。這里用Z分?jǐn)?shù)法進(jìn)行歸一化處理。語(yǔ)句如下：

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進(jìn)行聚類

使用Mahout將c1uster_input表中的數(shù)據(jù)進(jìn)行聚類，主要的main函數(shù)如下：

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｝

最后，需要編寫(xiě)一個(gè)run函數(shù)。Run函數(shù)主要包括4個(gè)步驟：1）將輸入文件序列化；2）生成Canopy；3）利用生成的Canopy執(zhí)行K_means聚類；4）將聚類輸出。在執(zhí)行過(guò)程中，生成Canopy的速度很快，而K_means的迭代過(guò)程比較耗時(shí)。

4　結(jié)束語(yǔ)

文中在對(duì)Hadoop云計(jì)算平臺(tái)、MapReduce計(jì)算模型、Mahout機(jī)器學(xué)習(xí)算法庫(kù)研究的基礎(chǔ)上，對(duì)Canopy算法和K_ means算法的聚類過(guò)程進(jìn)行了分析研究，提出將兩者進(jìn)行結(jié)合，以提高海量數(shù)據(jù)的聚類效率。以用戶聚類為例，基于Mahout的數(shù)據(jù)模型對(duì)數(shù)據(jù)進(jìn)行歸一化并進(jìn)行了聚類實(shí)現(xiàn)。結(jié)果表明，在云環(huán)境中，基于Mahout的算法庫(kù)對(duì)大規(guī)模數(shù)據(jù)進(jìn)行挖掘分析具有重要的現(xiàn)實(shí)意義。

［1］Han J，Kamber M，Pei J.數(shù)據(jù)挖掘：概念與技術(shù)［M］.范明，孟小峰，等譯.北京：機(jī)械工業(yè)出版社，2012.

［2］Wu X，Kumar V.數(shù)據(jù)挖掘十大算法［M］.李文波，吳素研，等譯.北京：清華大學(xué)出版社，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］余長(zhǎng)俊，張燃.云環(huán)境下基于Canopy聚類的FCM算法研究［J］.計(jì)算機(jī)科學(xué)，2014，11（41）：316_319.

［7］江小平，李成華，向文，張新訪，顏海濤.K_means聚類算法的MapReduce并行化實(shí)現(xiàn)［J］.華中科技大學(xué)學(xué)報(bào)，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技術(shù)內(nèi)幕：深入解析Hadoop Common 和HDFS架構(gòu)設(shè)計(jì)與實(shí)現(xiàn)原理［M］.北京：機(jī)械工業(yè)出版社，2013.

［10］董西成.Hadoop技術(shù)內(nèi)幕：深入理解MapReduce架構(gòu)設(shè)計(jì)與實(shí)現(xiàn)原理［M］.北京：機(jī)械工業(yè)出版社，2013.

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

［12］Giacome11i P.Mahout實(shí)踐指南［M］.靳小波，譯.北京：機(jī)械工業(yè)出版社，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算法解析與案例實(shí)戰(zhàn)［M］.北京：械工業(yè)出版社，2014.

［16］李應(yīng)安.基于MapReduce的聚類算法的并行化研究［D］.廣州：中山大學(xué)，2010.

［17］范東來(lái).Hadoop海量數(shù)據(jù)處理：技術(shù)詳解與項(xiàng)目實(shí)戰(zhàn)［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稿件編號(hào)：201512153

2015年陜西省教育廳科學(xué)研究項(xiàng)目（15JK2113）；2014年度陜西省教育科學(xué)“十二五”規(guī)劃課題（SGH140867）

樊同科（1979—），男，陜西扶風(fēng)人，碩士，副教授。研究方向：數(shù)據(jù)挖掘。