基于Hadoop和Mahout的ASUCF算法并行化研究
2016-05-14 10:33:51曹萍
軟件工程 2016年6期
摘 要：針對高效的協同過濾推薦技術處理大數據時的計算效率問題，提出了并行計算的ASUCF算法。該算法采用Hadoop平臺的MapReduce并行編程模型，改善大數據環境下高效的CF算法在單機運行時的計算性能問題。最后在實驗部分，結合Mahout，實現ASUCF算法的并行化，設計不同數據集上的加速比實驗，驗證算法并行化后在大數據環境中具有較好的計算性能。
關鍵詞：協同過濾；計算效率；加速比；Hadoop；Mahout
中圖分類號：TP391 文獻標識碼：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）
互聯網時代，網絡資源紛雜，信息過載，個性化推薦成為緩解用戶在網絡中的信息迷茫問題的重要途徑[1]。在多項目、多領域的推薦中，因不依賴用戶或項目內容，具有較好通用性的協同過濾算法[2]成為較為成功的推薦技術，其改進因而也受到廣泛關注。然而，改進的算法通常是以犧牲計算效率換取計算準確度的提升。隨著大數據時代的來臨，解決計算效率的問題也迫在眉睫。由于單機模式的計算能力有限，而分布式計算具有多資源、可擴展、高效計算等優勢，所以用分布式計算實現高效的CF算法，既能提高推薦準確度，又能保證計算效率。目前主要使用云計算平臺Hadoop實現算法的并行化，如文獻[3—8]等是通過將算法移植至Hadoop，以得到高計算性能的算法。
本文將基于平均相似度的協同過濾推薦算法（Average Similarity of User-Item Collaborative Filtering，簡稱ASUCF）與開源分布式平臺Hadoop結合，改寫Mahout中Item-based CF分布式實現，研究ASUCF算法的并行化，探索其MapReduce過程設計，并通過在不同規模的數據集上實驗，比較單節點計算與多節點計算在計算效率上的差別，證明并行化后的ASUCF算法在計算效率上的優勢，更能適應大數據環境。
2 Hadoop平臺及ASUCF算法并行化分析（Hadoop and analysis of ASUCF in parallel）
2.1 ASUCF算法概述
文獻[9]詳細描述了ASUCF算法，并通過實驗證明推薦準確度的提高，在此對其簡單描述，為后續的并行化分析作鋪墊。ASUCF為避免矩陣預處理帶來的偏差，改進的算法回歸到最原始的評分矩陣，從用戶行為分析、項目行為分析，引入平均相似度，將計算預測評分分解成用戶角度的預測和項目角度的預測兩部分，綜合兩部分后得到最終的用戶對項目的預測評分。
用戶的項目平均相似度和項目的用戶平均相似度計算分別如式（1）和式（2），和分別表示用戶已評分項目的集合，對項目已評分的用戶集合：
綜合用戶、項目兩方面，引入UAS、IAS，則目標用戶對目標項目的預測評分如式（3）所示。
2.2 Hadoop簡介
Hadoop起源于Apache公司的Lucene和Nutch項目[10]，是谷歌云計算理論的Java語言實現。2006年，實現分布式文件系統和MapReduce的部分從Lucene和Nutch中分離出來，成為新項目Hadoop[11]。對應GFS實現的HDFS、并行計算模型MapReduce是Hadoop中最核心的部分。HDFS是Hadoop中的文件管理系統，采用主從結構，一個集群中包括一個主控服務器，即目錄節點NameNode，用于索引DataNode、負責系統內文件命名空間操作、數據塊和DataNode之間的映射關系等；以及多個塊服務器，即數據節點DataNode，用于數據物理存儲，文件通常被劃分成若干個數據塊，儲存在不同的DataNode中[12]。MapReduce是一種可靠、高效的并行編程模型和計算框架，借助于HDFS等分布式技術，能夠處理各類PB數量級的大數據[13]，其構成部分主要有一個主控服務JobTracker，若干個從服務TaskTracker，分布式文件系統HDFS，以及客戶端Client[14]，它們的主要功能分別是：
（1）JobTracker：將作業劃分成若干個任務，分發給多個TaskTracker，管理任務的執行以及輸出反饋。
（2）TaskTracker：完成若干個Map、Reduce任務，并向JobTracker實時反饋執行情況。
（3）HDFS：數據、相關信息的保存及管理。
（4）客戶端Client：Map和Reduce程序的編寫，作業的提交。
MapReduce通過分解任務、合并結果的分而治之思想實現可分解、可并行處理大數據集上的并行計算。MapReduce的任務執行過程由Map和Reduce兩階段構成，每次Map和Reduce的輸入和輸出均是鍵值對
2.3 ASUCF算法分析
要實現算法的并行性，首先需要分析出算法中的可并行計算部分，以及并行計算部分與串行計算之間的關系。為方便表述，設：
通過對改進算法ASUCF的分析，將每次推薦的計算分解為：UAS、IAS、、，其中又可分解為兩兩用戶的相似度計算和目標預測評分的計算；又可分解為目標區域內兩兩項目的相似度計算和目標預測評分的計算。UAS、IAS之間不存在計算依賴關系，兩者之間是可并行的；相似度的計算和目標預測評分計算之間存在先后順序，即目標預測評分須依賴于相似度的計算，兩者之間必須是串行關系；UAS、IAS與、存在順序性，兩兩之間分別是串行計算；而和之間無依賴關系，可并行計算；預測評分計算之間也是可并行的。上述計算過程關系如圖1所示。需要說明的是：UAS和IAS雖然實質上也是相似度的計算，但是由于計算空間不同，所以不與和中的相似度計算部分混合，而是作為單獨的過程進行計算。
3 ASUCF算法并行化計算的過程及實現（Process and implementation of parallel ASUCF）
3.1 UAS和IAS的計算
UAS的計算實際是通過對當前用戶已評分項目相似度的綜合衡量，得到當前用戶的興趣跨度。變換評分矩陣輸入成鍵值對形式，過程如圖2所示，共包含三個MapReduce過程，每個過程都可并行運行。后續章節中的offset代表每條記錄在評分表中的偏移量。
輸入：評分矩陣，當前用戶id。
輸出：當前用戶的UAS值。
IAS的計算實際是通過對已給出當前項目評分的用戶相似度的綜合衡量，得到當前項目的適用用戶分布度。變換評分矩陣輸入成鍵值對形式，過程如圖3所示，共包含三個MapReduce過程，每個過程都可并行運行。
輸入：評分矩陣，當前項目id。
輸出：當前項目的IAS值。
用戶相似度的并行計算過程參照文獻[15]，同理得出項目相似度的并行計算過程，在此不再贅述。
3.2 預測評分及推薦的計算
綜合3.1內容及用戶相似度、項目相似度并行化過程設計，分析如下：
步驟一：將輸入
步驟二：用<（用戶，用戶），相似度>構成用戶相似度矩陣user-similarity matrix；用<（項目，項目），相似度>構成項目相似度矩陣item-similarity matrix。
步驟一和步驟二在文獻[15]中已具體表述。
步驟三：矩陣相乘，公式計算。
（1）項目向量矩陣×用戶相似度矩陣，根據式（4）計算，如圖4所示。
（2）用戶向量矩陣×項目相似度矩陣，根據式（5）計算，如圖5所示。
關鍵4：根據（用戶，項目）進行聚合，、推薦結果計算如圖6所示。
當目標用戶需要推薦時，在Map階段輸入用戶對項目的預測評分，在Reduce階段根據預測分值排序，返回TOP-N推薦集。至此，推薦完成。
在所有階段的MapReduce過程設計沒有改變算法的數學計算關系，所以對算法的計算結果沒有影響，在Hadoop平臺上運行與非并行模式下運行的推薦結果是一樣的，但是，并行模式Hadoop下的算法，有高效的大數據集計算能力，可擴展性較高。
3.3 基于Mahout的ASUCF并行化實現
Mahout中的RecommenderJob實現了item-based CF全推薦過程的MapReduce編程，本文在此基礎，改寫RecommenderJob，實現ASUCF的并行化。結合上一章的分析，算法主要步驟如下[16]：
（1）改寫PreparePreferenceMatrixJob，將USER_VECTORS重命名為USER_RATING_MATRIX，原Item向量RATING_MATRIX重命名為Item_RATING_MATRIX。
（2）以RowSimilarityJob的工作過程為模板，增加UserSimilarityJob，將輸入改成USER_RATING_MATRIX，計算出用戶的相似度。
（3）以AggregateAndRecommend的工作過程為模板，增加asucfaggregateAndRecommend，改寫AggregateAndRecommend中預測評分計算：
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中實現的CF算法，并沒有利用平均評分來懲罰用戶評分標準的差異，故在ASUCF并行計算中除引入UAS、IAS外還需加入平均評分。
3.4 實驗設計與分析
實驗的Hadoop平臺使用六臺內存2G，CPU主頻3.40GHZ的PC機，搭建完全分布式環境，1臺做namenode和jobtracker，另5臺做datanode和tasktracker，hadoop版本為1.0.0，ubuntu版本為12.10，jdk版本為1.6，編程工具為eclipse 3.7。實驗選取明尼蘇達大學提供的MovieLens數據集，選取不同規模的數據集，模擬大數據環境，包括：
（1）10萬條評分記錄，其中用戶數為943，電影數為1682。
（2）100萬條評分記錄，其中用戶數為6040，電影數為3900。
（3）1000萬條評分記錄，其中用戶數為71567，電影數為10681。
實驗選取算法單機執行時間T1與集群執行時間Tn的比值作為直觀的評估，即常用的加速比speedup。具體實驗設計為：為數據集中的每個用戶推薦十個項目，啟動集群中的所有節點，測試隨著數據集規模的增大，加速比的變化；啟動集群中的部分節點，通過增加節點，觀察同一個數據集上加速比的變化。實驗結果如圖7所示。
下面從兩方面分析圖7的結果：
（1）集群節點數固定，數據集規模變化
對于每個節點數情況，隨著數據集規模的增大，加速比都呈現遞增的趨勢。當節點數目較少時，其差別不大；當節點數目較大時，差別越來越明顯。
（2）數據集規模固定，集群節點數變化
對于不同的數據集，隨著節點數量的增加，加速比呈現不同的變化趨勢。當數據集規模較小時，加速比甚至呈現降低趨勢；當數據集規模較大時，加速比呈現遞增趨勢；當節點數增加到一定數量時，加速比趨于穩定。
綜合兩方面，可以看出：只有在數據規模足夠大時，集群執行的計算效率才比單機執行高，并且隨著數據集的增加，集群執行的優勢更突出，但當節點增加到一定數量時，計算效率也趨于穩定，這是由于節點之間存在通信、磁盤讀寫等開銷，節點數增加，Map/Reduce所需要的系統開銷也會隨之增加。
4 結論（Conclusion）
本文介紹了ASUCF算法，Hadoop云平臺概況，為實現高效的推薦算法，重點研究ASUCF的可并行性，分析了其在MapReduce并行編程上的過程設計，并結合Mahout中的Item-based CF分布式算法，在開源云計算平臺Hadoop上實現。通過設計不同的Movielens數據集的實驗，變化集群節點數目和數據集規模大小，對加速比進行評估，證明ASUCF并行算法在處理大數據時，具有較高的計算效率，解決了ASUCF算法在準確度提高的同時帶來的計算效率降低的問題，實現較高準確度、較高計算效率的推薦。但是也存在不足，一方面由于實驗條件的限制，搭建的集群規模有限；另一方面，是對Hadoop平臺的直接應用，下一步可以結合Hadoop中任務調度等方面的性能優化，進一步提高計算能力，適應不斷壯大的大數據。
參考文獻（References）
[1] 李樹青.個性化信息檢索技術綜述[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環境下的分布式協同過濾算法設計與實現[J].現代圖書情報技術，2013（1）：83-89.
[4] 程苗，陳華平.基于Hadoop的Web日志挖掘[J].計算機工程，2011，37（11）：37-39.
[5] 張明輝.基于Hadoop的數據挖掘算法的分析與研究[D].昆明：昆明理工大學，2012.
[6] 李改，等.基于大數據集的協同過濾算法的并行化研究[J].計算機工程與設計，2012，33（6）：2437-2441.
[7] 周源.基于云計算的推薦算法研究[D].成都：電子科技大學，2012.
[8] 金龑.協同過濾算法及其并行化研究[D].南京：南京大學，2012.
[9] 葉錫君，曹萍.ASUCF：基于平均相似度的協同過濾推薦算法[J].計算機工程與設計，2014，35（12）：4217-4222.
[10] 陸嘉恒.Hadoop實戰[M].北京：機械工業出版社，2011.
[11] Chuck Lam，James Warren.Hadoop in Action.Manning Publications，2009.
[12] 劉琨，董龍江.云數據存儲與管理[J].計算機系統應用，2011， 20（6）：232-237.
[13] 陳全，鄧倩妮.云計算及其關鍵技術[J].計算機應用，2009， 29（9）：2562-2567.
[14] Tom White.周敏奇，等，譯.Hadoop：權威指南[M].北京：清華大學出版社，2011.
[15] 曹萍.基于Hadoop的協同過濾推薦并行化研究[J].計算機時代，2016（5）：30-33.
[16] Sean Owen，et al.Mahout in Action[M].Manning Publications Co.，2012.
作者簡介：
曹 萍（1989-），女，碩士，助理工程師.研究領域：知識 工程.
