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

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

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A

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

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

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

2.1 ASUCF算法概述

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

用戶的項(xiàng)目平均相似度和項(xiàng)目的用戶平均相似度計(jì)算分別如式（1）和式（2），和分別表示用戶已評(píng)分項(xiàng)目的集合，對(duì)項(xiàng)目已評(píng)分的用戶集合：

綜合用戶、項(xiàng)目?jī)煞矫?，引入U(xiǎn)AS、IAS，則目標(biāo)用戶對(duì)目標(biāo)項(xiàng)目的預(yù)測(cè)評(píng)分如式（3）所示。

2.2 Hadoop簡(jiǎn)介

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

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

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

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

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

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

2.3 ASUCF算法分析

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

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

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

3.1 UAS和IAS的計(jì)算

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

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

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

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

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

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

用戶相似度的并行計(jì)算過(guò)程參照文獻(xiàn)[15]，同理得出項(xiàng)目相似度的并行計(jì)算過(guò)程，在此不再贅述。

3.2 預(yù)測(cè)評(píng)分及推薦的計(jì)算

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

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

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

步驟一和步驟二在文獻(xiàn)[15]中已具體表述。

步驟三：矩陣相乘，公式計(jì)算。

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

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

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

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

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

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

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

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

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

（3）以AggregateAndRecommend的工作過(guò)程為模板，增加asucfaggregateAndRecommend，改寫AggregateAndRecommend中預(yù)測(cè)評(píng)分計(jì)算：

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部分的相似度計(jì)算域不同于item-based的全局搜索，為用戶i已評(píng)分項(xiàng)目中與項(xiàng)目c相似的項(xiàng)目。需要指出的是，mahout中實(shí)現(xiàn)的CF算法，并沒有利用平均評(píng)分來(lái)懲罰用戶評(píng)分標(biāo)準(zhǔn)的差異，故在ASUCF并行計(jì)算中除引入U(xiǎn)AS、IAS外還需加入平均評(píng)分。

3.4 實(shí)驗(yàn)設(shè)計(jì)與分析

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論（Conclusion）

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

參考文獻(xiàn)（References）

[1] 李樹青.個(gè)性化信息檢索技術(shù)綜述[J].情報(bào)理論與實(shí)踐， 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] 肖強(qiáng)，等.Hadoop環(huán)境下的分布式協(xié)同過(guò)濾算法設(shè)計(jì)與實(shí)現(xiàn)[J].現(xiàn)代圖書情報(bào)技術(shù)，2013（1）：83-89.

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

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

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

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

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

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

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

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

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

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

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

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

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

作者簡(jiǎn)介：

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