云環境下基于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—），男，陜西扶風人，碩士，副教授。研究方向：數據挖掘。