基于Hadoop和Mahout的ASUCF算法并行化研究

摘 要：針對高效的協(xié)同過濾推薦技術(shù)處理大數(shù)據(jù)時的計算效率問題，提出了并行計算的ASUCF算法。該算法采用Hadoop平臺的MapReduce并行編程模型，改善大數(shù)據(jù)環(huán)境下高效的CF算法在單機運行時的計算性能問題。最后在實驗部分，結(jié)合Mahout，實現(xiàn)ASUCF算法的并行化，設(shè)計不同數(shù)據(jù)集上的加速比實驗，驗證算法并行化后在大數(shù)據(jù)環(huán)境中具有較好的計算性能。

關(guān)鍵詞：協(xié)同過濾；計算效率；加速比；Hadoop；Mahout

中圖分類號：TP391 文獻標(biāo)識碼：A

文章編號：2096-1472（2016）-06-17-04

Abstract：Aiming to solve the CF's （Collaborative Filtering） computing efficiency problem in big data processing，the paper proposes parallel ASUCF（Average Similarity of User-Item Collaborative Filtering） algorithm.It applies the MapReduce parallel-programming model in Hadoop platform，which improves the CF's computational efficiency in big data processing on a single PC.Combined with Mahout，the parallelization of ASUCF is achieved.The paper designs speedup experiments on different data sets.The experiment results prove that the parallel algorithm brings out better computing performance in big data processing.

Keywords：collaborative filtering；computing efficiency；speedup；Hadoop；Mahout

1 引言（Introduction）

互聯(lián)網(wǎng)時代，網(wǎng)絡(luò)資源紛雜，信息過載，個性化推薦成為緩解用戶在網(wǎng)絡(luò)中的信息迷茫問題的重要途徑[1]。在多項目、多領(lǐng)域的推薦中，因不依賴用戶或項目內(nèi)容，具有較好通用性的協(xié)同過濾算法[2]成為較為成功的推薦技術(shù)，其改進因而也受到廣泛關(guān)注。然而，改進的算法通常是以犧牲計算效率換取計算準(zhǔn)確度的提升。隨著大數(shù)據(jù)時代的來臨，解決計算效率的問題也迫在眉睫。由于單機模式的計算能力有限，而分布式計算具有多資源、可擴展、高效計算等優(yōu)勢，所以用分布式計算實現(xiàn)高效的CF算法，既能提高推薦準(zhǔn)確度，又能保證計算效率。目前主要使用云計算平臺Hadoop實現(xiàn)算法的并行化，如文獻[3—8]等是通過將算法移植至Hadoop，以得到高計算性能的算法。

本文將基于平均相似度的協(xié)同過濾推薦算法（Average Similarity of User-Item Collaborative Filtering，簡稱ASUCF）與開源分布式平臺Hadoop結(jié)合，改寫Mahout中Item-based CF分布式實現(xiàn)，研究ASUCF算法的并行化，探索其MapReduce過程設(shè)計，并通過在不同規(guī)模的數(shù)據(jù)集上實驗，比較單節(jié)點計算與多節(jié)點計算在計算效率上的差別，證明并行化后的ASUCF算法在計算效率上的優(yōu)勢，更能適應(yīng)大數(shù)據(jù)環(huán)境。

2 Hadoop平臺及ASUCF算法并行化分析（Hadoop and analysis of ASUCF in parallel）

2.1 ASUCF算法概述

文獻[9]詳細描述了ASUCF算法，并通過實驗證明推薦準(zhǔn)確度的提高，在此對其簡單描述，為后續(xù)的并行化分析作鋪墊。ASUCF為避免矩陣預(yù)處理帶來的偏差，改進的算法回歸到最原始的評分矩陣，從用戶行為分析、項目行為分析，引入平均相似度，將計算預(yù)測評分分解成用戶角度的預(yù)測和項目角度的預(yù)測兩部分，綜合兩部分后得到最終的用戶對項目的預(yù)測評分。

用戶的項目平均相似度和項目的用戶平均相似度計算分別如式（1）和式（2），和分別表示用戶已評分項目的集合，對項目已評分的用戶集合：

綜合用戶、項目兩方面，引入UAS、IAS，則目標(biāo)用戶對目標(biāo)項目的預(yù)測評分如式（3）所示。

2.2 Hadoop簡介

Hadoop起源于Apache公司的Lucene和Nutch項目[10]，是谷歌云計算理論的Java語言實現(xiàn)。2006年，實現(xiàn)分布式文件系統(tǒng)和MapReduce的部分從Lucene和Nutch中分離出來，成為新項目Hadoop[11]。對應(yīng)GFS實現(xiàn)的HDFS、并行計算模型MapReduce是Hadoop中最核心的部分。HDFS是Hadoop中的文件管理系統(tǒng)，采用主從結(jié)構(gòu)，一個集群中包括一個主控服務(wù)器，即目錄節(jié)點NameNode，用于索引DataNode、負責(zé)系統(tǒng)內(nèi)文件命名空間操作、數(shù)據(jù)塊和DataNode之間的映射關(guān)系等；以及多個塊服務(wù)器，即數(shù)據(jù)節(jié)點DataNode，用于數(shù)據(jù)物理存儲，文件通常被劃分成若干個數(shù)據(jù)塊，儲存在不同的DataNode中[12]。MapReduce是一種可靠、高效的并行編程模型和計算框架，借助于HDFS等分布式技術(shù)，能夠處理各類PB數(shù)量級的大數(shù)據(jù)[13]，其構(gòu)成部分主要有一個主控服務(wù)JobTracker，若干個從服務(wù)TaskTracker，分布式文件系統(tǒng)HDFS，以及客戶端Client[14]，它們的主要功能分別是：

（1）JobTracker：將作業(yè)劃分成若干個任務(wù)，分發(fā)給多個TaskTracker，管理任務(wù)的執(zhí)行以及輸出反饋。

（2）TaskTracker：完成若干個Map、Reduce任務(wù)，并向JobTracker實時反饋執(zhí)行情況。

（3）HDFS：數(shù)據(jù)、相關(guān)信息的保存及管理。

（4）客戶端Client：Map和Reduce程序的編寫，作業(yè)的提交。

MapReduce通過分解任務(wù)、合并結(jié)果的分而治之思想實現(xiàn)可分解、可并行處理大數(shù)據(jù)集上的并行計算。MapReduce的任務(wù)執(zhí)行過程由Map和Reduce兩階段構(gòu)成，每次Map和Reduce的輸入和輸出均是鍵值對的形式，通過對相同key鍵值對的若干次歸類整理，調(diào)用用戶自定義的Map和Reduce函數(shù)，得到最終輸出結(jié)果。

2.3 ASUCF算法分析

要實現(xiàn)算法的并行性，首先需要分析出算法中的可并行計算部分，以及并行計算部分與串行計算之間的關(guān)系。為方便表述，設(shè)：

通過對改進算法ASUCF的分析，將每次推薦的計算分解為：UAS、IAS、、，其中又可分解為兩兩用戶的相似度計算和目標(biāo)預(yù)測評分的計算；又可分解為目標(biāo)區(qū)域內(nèi)兩兩項目的相似度計算和目標(biāo)預(yù)測評分的計算。UAS、IAS之間不存在計算依賴關(guān)系，兩者之間是可并行的；相似度的計算和目標(biāo)預(yù)測評分計算之間存在先后順序，即目標(biāo)預(yù)測評分須依賴于相似度的計算，兩者之間必須是串行關(guān)系；UAS、IAS與、存在順序性，兩兩之間分別是串行計算；而和之間無依賴關(guān)系，可并行計算；預(yù)測評分計算之間也是可并行的。上述計算過程關(guān)系如圖1所示。需要說明的是：UAS和IAS雖然實質(zhì)上也是相似度的計算，但是由于計算空間不同，所以不與和中的相似度計算部分混合，而是作為單獨的過程進行計算。

3 ASUCF算法并行化計算的過程及實現(xiàn)（Process and implementation of parallel ASUCF）

3.1 UAS和IAS的計算

UAS的計算實際是通過對當(dāng)前用戶已評分項目相似度的綜合衡量，得到當(dāng)前用戶的興趣跨度。變換評分矩陣輸入成鍵值對形式，過程如圖2所示，共包含三個MapReduce過程，每個過程都可并行運行。后續(xù)章節(jié)中的offset代表每條記錄在評分表中的偏移量。

輸入：評分矩陣，當(dāng)前用戶id。

輸出：當(dāng)前用戶的UAS值。

IAS的計算實際是通過對已給出當(dāng)前項目評分的用戶相似度的綜合衡量，得到當(dāng)前項目的適用用戶分布度。變換評分矩陣輸入成鍵值對形式，過程如圖3所示，共包含三個MapReduce過程，每個過程都可并行運行。

輸入：評分矩陣，當(dāng)前項目id。

輸出：當(dāng)前項目的IAS值。

用戶相似度的并行計算過程參照文獻[15]，同理得出項目相似度的并行計算過程，在此不再贅述。

3.2 預(yù)測評分及推薦的計算

綜合3.1內(nèi)容及用戶相似度、項目相似度并行化過程設(shè)計，分析如下：

步驟一：將輸入經(jīng)過MapReduce輸出為<用戶，（項目，評分）>，生成用戶向量矩陣user-vector matrix；將用戶向量矩陣轉(zhuǎn)置為<項目，（用戶，評分）>，生成項目向量矩陣item-vector matrix。

步驟二：用<（用戶，用戶），相似度>構(gòu)成用戶相似度矩陣user-similarity matrix；用<（項目，項目），相似度>構(gòu)成項目相似度矩陣item-similarity matrix。

步驟一和步驟二在文獻[15]中已具體表述。

步驟三：矩陣相乘，公式計算。

（1）項目向量矩陣×用戶相似度矩陣，根據(jù)式（4）計算，如圖4所示。

（2）用戶向量矩陣×項目相似度矩陣，根據(jù)式（5）計算，如圖5所示。

關(guān)鍵4：根據(jù)（用戶，項目）進行聚合，、推薦結(jié)果計算如圖6所示。

當(dāng)目標(biāo)用戶需要推薦時，在Map階段輸入用戶對項目的預(yù)測評分，在Reduce階段根據(jù)預(yù)測分值排序，返回TOP-N推薦集。至此，推薦完成。

在所有階段的MapReduce過程設(shè)計沒有改變算法的數(shù)學(xué)計算關(guān)系，所以對算法的計算結(jié)果沒有影響，在Hadoop平臺上運行與非并行模式下運行的推薦結(jié)果是一樣的，但是，并行模式Hadoop下的算法，有高效的大數(shù)據(jù)集計算能力，可擴展性較高。

3.3 基于Mahout的ASUCF并行化實現(xiàn)

Mahout中的RecommenderJob實現(xiàn)了item-based CF全推薦過程的MapReduce編程，本文在此基礎(chǔ)，改寫RecommenderJob，實現(xiàn)ASUCF的并行化。結(jié)合上一章的分析，算法主要步驟如下[16]：

（1）改寫PreparePreferenceMatrixJob，將USER_VECTORS重命名為USER_RATING_MATRIX，原Item向量RATING_MATRIX重命名為Item_RATING_MATRIX。

（2）以RowSimilarityJob的工作過程為模板，增加UserSimilarityJob，將輸入改成USER_RATING_MATRIX，計算出用戶的相似度。

（3）以AggregateAndRecommend的工作過程為模板，增加asucfaggregateAndRecommend，改寫AggregateAndRecommend中預(yù)測評分計算：

PU（i，c）=sum（all n from N：（usersimilarity（i，n）-uas（i）*（Item_RATING_MATRIX（i，n）-Average（i））/sum（all n from N：abs（usersimilarity（i，n）-uas（i））

PI（i，c）=sum（all n from mostsimilaritytoitemc：（itemsimilarity（c，n）-ias（c）*（USER_RATING_MATRIX（i，n）-Average（c））/sum（all n from mostsimilaritytoitemc of USER_RATING_MATRIX（i）：abs（itemsimilarity（i，n）-ias（i））

P（i，c）=（PU（i，c）+PI（i，c））/2

其中，PI部分的相似度計算域不同于item-based的全局搜索，為用戶i已評分項目中與項目c相似的項目。需要指出的是，mahout中實現(xiàn)的CF算法，并沒有利用平均評分來懲罰用戶評分標(biāo)準(zhǔn)的差異，故在ASUCF并行計算中除引入UAS、IAS外還需加入平均評分。

3.4 實驗設(shè)計與分析

實驗的Hadoop平臺使用六臺內(nèi)存2G，CPU主頻3.40GHZ的PC機，搭建完全分布式環(huán)境，1臺做namenode和jobtracker，另5臺做datanode和tasktracker，hadoop版本為1.0.0，ubuntu版本為12.10，jdk版本為1.6，編程工具為eclipse 3.7。實驗選取明尼蘇達大學(xué)提供的MovieLens數(shù)據(jù)集，選取不同規(guī)模的數(shù)據(jù)集，模擬大數(shù)據(jù)環(huán)境，包括：

（1）10萬條評分記錄，其中用戶數(shù)為943，電影數(shù)為1682。

（2）100萬條評分記錄，其中用戶數(shù)為6040，電影數(shù)為3900。

（3）1000萬條評分記錄，其中用戶數(shù)為71567，電影數(shù)為10681。

實驗選取算法單機執(zhí)行時間T1與集群執(zhí)行時間Tn的比值作為直觀的評估，即常用的加速比speedup。具體實驗設(shè)計為：為數(shù)據(jù)集中的每個用戶推薦十個項目，啟動集群中的所有節(jié)點，測試隨著數(shù)據(jù)集規(guī)模的增大，加速比的變化；啟動集群中的部分節(jié)點，通過增加節(jié)點，觀察同一個數(shù)據(jù)集上加速比的變化。實驗結(jié)果如圖7所示。

下面從兩方面分析圖7的結(jié)果：

（1）集群節(jié)點數(shù)固定，數(shù)據(jù)集規(guī)模變化

對于每個節(jié)點數(shù)情況，隨著數(shù)據(jù)集規(guī)模的增大，加速比都呈現(xiàn)遞增的趨勢。當(dāng)節(jié)點數(shù)目較少時，其差別不大；當(dāng)節(jié)點數(shù)目較大時，差別越來越明顯。

（2）數(shù)據(jù)集規(guī)模固定，集群節(jié)點數(shù)變化

對于不同的數(shù)據(jù)集，隨著節(jié)點數(shù)量的增加，加速比呈現(xiàn)不同的變化趨勢。當(dāng)數(shù)據(jù)集規(guī)模較小時，加速比甚至呈現(xiàn)降低趨勢；當(dāng)數(shù)據(jù)集規(guī)模較大時，加速比呈現(xiàn)遞增趨勢；當(dāng)節(jié)點數(shù)增加到一定數(shù)量時，加速比趨于穩(wěn)定。

綜合兩方面，可以看出：只有在數(shù)據(jù)規(guī)模足夠大時，集群執(zhí)行的計算效率才比單機執(zhí)行高，并且隨著數(shù)據(jù)集的增加，集群執(zhí)行的優(yōu)勢更突出，但當(dāng)節(jié)點增加到一定數(shù)量時，計算效率也趨于穩(wěn)定，這是由于節(jié)點之間存在通信、磁盤讀寫等開銷，節(jié)點數(shù)增加，Map/Reduce所需要的系統(tǒng)開銷也會隨之增加。

4 結(jié)論（Conclusion）

本文介紹了ASUCF算法，Hadoop云平臺概況，為實現(xiàn)高效的推薦算法，重點研究ASUCF的可并行性，分析了其在MapReduce并行編程上的過程設(shè)計，并結(jié)合Mahout中的Item-based CF分布式算法，在開源云計算平臺Hadoop上實現(xiàn)。通過設(shè)計不同的Movielens數(shù)據(jù)集的實驗，變化集群節(jié)點數(shù)目和數(shù)據(jù)集規(guī)模大小，對加速比進行評估，證明ASUCF并行算法在處理大數(shù)據(jù)時，具有較高的計算效率，解決了ASUCF算法在準(zhǔn)確度提高的同時帶來的計算效率降低的問題，實現(xiàn)較高準(zhǔn)確度、較高計算效率的推薦。但是也存在不足，一方面由于實驗條件的限制，搭建的集群規(guī)模有限；另一方面，是對Hadoop平臺的直接應(yīng)用，下一步可以結(jié)合Hadoop中任務(wù)調(diào)度等方面的性能優(yōu)化，進一步提高計算能力，適應(yīng)不斷壯大的大數(shù)據(jù)。

參考文獻（References）

[1] 李樹青.個性化信息檢索技術(shù)綜述[J].情報理論與實踐， 2009，32（5）：107-113.

[2] Liu Z B，et al.A Hybrid Collaborative Filtering Recommendation Mechanism for P2P Networks[J].Future Generation Computer Systems，2010，26（8）：1409-1417.

[3] 肖強，等.Hadoop環(huán)境下的分布式協(xié)同過濾算法設(shè)計與實現(xiàn)[J].現(xiàn)代圖書情報技術(shù)，2013（1）：83-89.

[4] 程苗，陳華平.基于Hadoop的Web日志挖掘[J].計算機工程，2011，37（11）：37-39.

[5] 張明輝.基于Hadoop的數(shù)據(jù)挖掘算法的分析與研究[D].昆明：昆明理工大學(xué)，2012.

[6] 李改，等.基于大數(shù)據(jù)集的協(xié)同過濾算法的并行化研究[J].計算機工程與設(shè)計，2012，33（6）：2437-2441.

[7] 周源.基于云計算的推薦算法研究[D].成都：電子科技大學(xué)，2012.

[8] 金龑.協(xié)同過濾算法及其并行化研究[D].南京：南京大學(xué)，2012.

[9] 葉錫君，曹萍.ASUCF：基于平均相似度的協(xié)同過濾推薦算法[J].計算機工程與設(shè)計，2014，35（12）：4217-4222.

[10] 陸嘉恒.Hadoop實戰(zhàn)[M].北京：機械工業(yè)出版社，2011.

[11] Chuck Lam，James Warren.Hadoop in Action.Manning Publications，2009.

[12] 劉琨，董龍江.云數(shù)據(jù)存儲與管理[J].計算機系統(tǒng)應(yīng)用，2011， 20（6）：232-237.

[13] 陳全，鄧倩妮.云計算及其關(guān)鍵技術(shù)[J].計算機應(yīng)用，2009， 29（9）：2562-2567.

[14] Tom White.周敏奇，等，譯.Hadoop：權(quán)威指南[M].北京：清華大學(xué)出版社，2011.

[15] 曹萍.基于Hadoop的協(xié)同過濾推薦并行化研究[J].計算機時代，2016（5）：30-33.

[16] Sean Owen，et al.Mahout in Action[M].Manning Publications Co.，2012.

作者簡介：

曹 萍（1989-），女，碩士，助理工程師.研究領(lǐng)域：知識 工程.