基于Hadoop個性化推薦算法設(shè)計與實現(xiàn)

劉　斌， 李　帆， 姚　斌

(陜西科技大學(xué) 電氣與信息工程學(xué)院， 陜西 西安　710021)

0　引言

隨著“互聯(lián)網(wǎng)”的發(fā)展和電子商務(wù)網(wǎng)站的興起，在給人們帶來便利和豐富信息的同時，信息過載的問題[1]也日益凸顯，在這樣的環(huán)境下個性化推薦[2]技術(shù)應(yīng)運而生.傳統(tǒng)推薦系統(tǒng)擴展性差且計算耗費大量時間，面對海量數(shù)據(jù)表現(xiàn)差強人意.大數(shù)據(jù)分析平臺[3]的出現(xiàn)，為個性化系統(tǒng)的改進提供了新的方向，其中Hadoop[4]平臺的分布式文件系統(tǒng)HDFS提供了海量數(shù)據(jù)的存儲能力，MapReduce并行計算框架通過對數(shù)據(jù)并行化處理，有效提高算法性能和系統(tǒng)執(zhí)行效率，提升了系統(tǒng)海量數(shù)據(jù)下的計算能力.目前也有針對特定推薦算法的Hadoop并行化研究，如李改等[5]提出了基于ALS的協(xié)同過濾算法的并行方法，王毅[6]提出了基于Hadoop的Slpoe One及其改進算法實現(xiàn)，但都沒有避免全局掃描帶來的高額開銷.

推薦系統(tǒng)的響應(yīng)速度是影響用戶體驗的關(guān)鍵指標(biāo)，而傳統(tǒng)個性化推薦系統(tǒng)在存在數(shù)據(jù)處理規(guī)模限制和推薦實時性低下的問題，擴展性不強，將其直接部署在分布式平臺上且不能發(fā)揮大數(shù)據(jù)平臺的優(yōu)勢，同時大量數(shù)據(jù)的分散存儲造成計算時占用過多集群寶貴的帶寬資源，影響推薦實時性.針對以上問題，選擇基于聚類和MapReduce并行化算法提高數(shù)據(jù)分析能力和可擴展性，并在其中引入奇異值分解降低數(shù)據(jù)稀疏性對算法效果的影響.

1　分布式個性化推薦算法設(shè)計

個性化推薦算法是推薦系統(tǒng)的核心，其算法多種多樣，選擇不同的算法對推薦的質(zhì)量和實時性有不同的影響.根據(jù)用戶評分?jǐn)?shù)據(jù)的形式，選擇基于用戶協(xié)同過濾[7]個性化推薦算法進行了Hadoop分布式算法的設(shè)計.

(1)收集用戶物品評分矩陣.設(shè)共有m個用戶和n個物品，用戶對物品的評分可以表示為矩陣形式H∈m+n.

(1)

式(1)中：rij表示第i個用戶對第j個物品的評分.

(2)選擇進行相似度計算的用戶.為了提升推薦算法的擴展性，采取將用戶進行聚類[8]并類簇內(nèi)進行推薦，同時將不同類簇的用戶存儲到同一機架方便本地計算，減少帶寬消耗.但隨著物品和用戶數(shù)量的增多，用戶物品評分矩陣存在很強的稀疏性，對用戶進行聚類的效果往往較差[9].為了改善聚類效果，采取奇異值分解[10](Singular Value Decomposition,SVD)對用戶物品評分矩陣降維.

(3)目標(biāo)用戶與所其屬類簇內(nèi)用戶的相似度計算[11]，選擇最近鄰居.本文以余弦相似度為基礎(chǔ)設(shè)計相似度計算.余弦相似度計算如下：

(2)

余弦相似度將用戶評分視為空間中的矢量，通過計算兩矢量之間的夾角進行度量，夾角越大，說明兩用戶興趣方向越相近，相似性越高.

考慮到相似度計算時不同物品對結(jié)果的貢獻度不同，例如潮流商品，購買的人很多，且一般都是追趕流行度，很少表達(dá)自己的興趣，同時在冷門的物品方面用戶購買時往往有很強的目的性，其推薦效果一般，這類物品對相似度計算造成影響，使推薦的長尾挖掘能力降低，因此基于余弦相似度引入物品貢獻權(quán)重進行相似度計算.記所有物品購買次數(shù)集合為c={c1,c2,…,cn}，設(shè)計物品i的貢獻度權(quán)重：

(3)

式(3)中：n為物品總數(shù)，meanc，stdc為集合C的均值和標(biāo)準(zhǔn)差.

從式(3)上看減弱了物品購買人次兩端的權(quán)重，突出了均值附近物品的影響.設(shè)計相似度計算方法為：

(4)

式(4)中：i，j為用戶，Ti,j為兩用戶共同購買的物品集合，xi,u為用戶i對物品u的評分.選擇與目標(biāo)用戶相似度最高的前M個用戶作為其近鄰.

(4)推薦物品.得出目標(biāo)用戶近鄰后，計算目標(biāo)用戶對近鄰觀看但自己沒有觀看的物品的評分，評分預(yù)測公式為：

(5)

式(5)中：i為目標(biāo)用戶，p為待評分物品，K為最近鄰集合，ri,rj分別為目標(biāo)用戶i和近鄰j的平均打分.最終選擇評分最高的前N個物品對目標(biāo)用戶進行推薦.

對比現(xiàn)有協(xié)同過濾算法，對本文算法在以下兩點進行提升：

(1)推薦實時性.現(xiàn)有協(xié)同過濾算法對目標(biāo)用戶或者物品尋找相似用戶或物品，計算相似度時需要遍歷整個用戶物品矩陣，在大數(shù)據(jù)的背景下，計算開銷巨大；同時用戶物品矩陣分布式存儲于HDFS當(dāng)中，完全遍歷同樣會造成過多I/O開銷，降低推薦的實時性.

本文算法首先通過對用戶進行聚類打上類別標(biāo)簽，對目標(biāo)用戶在所屬類內(nèi)進行推薦，避免了全局遍歷計算，減少了計算的時間和空間消耗；在HDFS存儲時進行了類別的分離存儲，將同一類別用戶信息存儲于同一服務(wù)器或機架上，有效減少了節(jié)點間通信造成的I/O消耗.

(2)推薦準(zhǔn)確性.由于數(shù)據(jù)的稀疏性，相似度計算不夠準(zhǔn)確，如兩個用戶有過行為的物品較少，但重疊的物品數(shù)目占比高，即使兩用戶評分有差距，根據(jù)相似度計算公式，也會造成兩者相似度計算結(jié)果較高.本文算法通過SVD進行了特征的篩選，在此基礎(chǔ)上對用戶聚類，類別內(nèi)用戶關(guān)聯(lián)性更強，通過在類簇內(nèi)推薦，精度更高，并添加物品貢獻權(quán)重，增強了推薦的長尾挖掘的能力，提升推薦的覆蓋率.

2　基于Hadoop個性化推薦算法實現(xiàn)

2.1　平臺配置及工作流程

選擇4臺服務(wù)器搭建Hadoop平臺，包括一個Master節(jié)點和3個Slave節(jié)點.節(jié)點配置為：8 G內(nèi)存，500 G硬盤，操作系統(tǒng)為Ubuntu14.04，JDK版本1.7.0，Hadoop版本為2.6.5.集群工作流程如圖1所示.

圖1　基于Hadoop平臺推薦算法流程

2.2　數(shù)據(jù)降維

Deerwester等[12]提出了奇異值分解用于發(fā)現(xiàn)文檔中的潛在因子，該方法被Koren等[13]用于Netfix推薦比賽中.

SVD可以通過矩陣分解來逼近矩陣并從中提取重要特征，保留80%～90%的能量可以得到重要特征并去掉噪聲，同時得到低維度的數(shù)據(jù)，因此將其用于用戶物品矩陣，可以實現(xiàn)降維以增強用戶聚類效果.

通過SVD分解可以提取用戶喜好特征，評分矩陣分解為以下形式：

(6)

式(6)中：Hm*n為戶物品評分矩陣，m代表用戶個數(shù)，n代表商品個數(shù)，∑為m*n的對角奇異值矩陣.奇異值大小表示其重要程度，奇異值越大則影響度越大.U是一個m*m正交矩陣，每行表示一用戶對于奇異值的權(quán)重向量.通過對角線奇異值從大到小排列，通過設(shè)置占總奇異值能量的閾值，選取前K個奇異值實現(xiàn)對原矩陣進行降維：

(7)

(8)

式(8)中：σi為奇異值，k為選擇奇異值個數(shù)，percentage為保留的特征值能量比例.

SVD不適于分解用于分布式進行計算，需要傳輸所有數(shù)據(jù)到一個節(jié)點中進行計算，但聚類中心是定期更新，因此SVD進行的定期離線計算.

2.3　通過并行化K-means對用戶聚類

K-mean聚類算法時間復(fù)雜度隨數(shù)據(jù)量呈線性關(guān)系，因此適于針對海量數(shù)據(jù)的聚類分析，基于降維后的用戶特征矩陣設(shè)計了對于用戶的基于MapReduce的K-means聚類[14]方法，流程如圖2所示.

圖2　聚類算法MapReduce并行化流程圖

首先隨機選擇k個用戶生成全局的k個類中心的列表，備份到各個計算節(jié)點用于MapReduce任務(wù)計算.

在Mapper階段：輸入降維后用戶物品評分矩陣，輸出以類中心為Key，屬于此類的用戶為Value的鍵值對.依次計算用戶與類中心的距離，選擇距離最近的類中心對用戶進行歸類：

ci=arg minj‖xi-uj‖2

(9)

式(9)中：xi為用戶特征向量，uj為聚類中心，ci即為xi所屬類別.

在Reducer階段：輸入<類中心，用戶>鍵值對，輸出以類中心為Key，所屬此類的用戶列表為Value的聚類結(jié)果.將輸入的<類中心，用戶>鍵值對整合為<類中心，用戶列表>，重新計算類簇中心：

(10)

式(10)中：m為用戶個數(shù)，j為聚類類別，xi為用戶特征向量，uj為類簇中心，即計算該類中所有用戶平均值作為新的類簇中心.

設(shè)置算法收斂條件目標(biāo)函數(shù)為最小化用戶到所屬類簇中心距離的平方和：

(11)

式(11)中：k為選擇聚類的個數(shù)，x為用戶特征向量，ui為類簇中心，dist(ui,x)為歐氏距離，如果算法收斂或達(dá)到最大迭代次數(shù)，輸出聚類結(jié)果，否則返回Map階段進行迭代.

每次聚類時間復(fù)雜度為O(m/n)，m為用戶數(shù)量，n為節(jié)點個數(shù)，時間復(fù)雜度與計算節(jié)點數(shù)量呈反比例關(guān)系.

2.4　計算用戶相似度并進行物品推薦

基于用戶的協(xié)同過濾算法分為兩步：首先計算目標(biāo)用戶與所屬類簇內(nèi)用戶的相似度，選出相似度最高的M個鄰居；對于鄰居購買但目標(biāo)用戶沒有購買的物品預(yù)測評分，選擇評分最高的N個物品進行推薦.其具體的MapReduce實現(xiàn)流程如圖3所示.

(1)輸入：用戶評分信息；輸出：用戶物品評分矩陣.

在Map階段讀入數(shù)據(jù)，取出用戶(U)、物品(M)、評分(R)，輸出鍵值對.在Reduce階段，完成用戶信息的收集，輸出，獲得用戶物品評分矩陣.

(2)輸入：用戶物品評分矩陣；輸出：物品用戶評分矩陣.

在Map階段讀取用戶物品矩陣，將數(shù)據(jù)拆分，輸出鍵值對.在Reduce階段，將輸入數(shù)據(jù)進行組合，輸出，獲得物品用戶評分矩陣.

(3)輸入：物品用戶評分矩陣，用戶聚類信息；輸出：用戶最近鄰居.

在Map階段讀取物品用戶評分矩陣和用戶聚類信息，設(shè)用戶集合為Us，用戶類別集合為c=(c0,c1,…ck)，其中k為用戶類別總數(shù)，對于U1,U2∈Us，如果U1∈ci&U2∈ci，即U1，U2為同一類，則輸出<(U1:U2),(U1_R:U2_R)>的鍵值對，其中Value為用戶對物品評分.在Reduce階段，對用戶對U1，U2根據(jù)式(4)進行相似度計算，得出相似度simU1,U2，根據(jù)相似度對每個用戶選取相似度最高的K個鄰居List(N)，其中N為鄰居，輸出鍵值對.

(4)輸入：用戶最近鄰集合，用戶物品評分矩陣；輸出：用戶推薦物品集合.

在Map階段讀取最近鄰集合和用戶物品評分矩陣，對最鄰近集合進行拆分，輸出的鍵值對，對于用戶物品評分矩陣，將其直接輸入到Reduce階段.在Reduce階段，根據(jù)式(5)預(yù)測用戶對近鄰購買但自己沒有購買的物品，最終選擇評分最高的前P個物品對目標(biāo)用戶進行推薦.輸出，存儲到HDFS當(dāng)中.

3　實驗測試與分析

3.1　實驗數(shù)據(jù)說明

本文以對電影進行推薦為例，選取用戶對電影的評分?jǐn)?shù)據(jù)作為原始數(shù)據(jù)進行推薦，其中評價信息包括：用戶標(biāo)識，電影標(biāo)識，用戶對電影的評分.實驗數(shù)據(jù)采用從MovieLens下載的大小分別為100 KB、1 MB、10 MB的數(shù)據(jù)集進行實驗.各數(shù)據(jù)集詳細(xì)信息如下：(1)100 KB：包括943個用戶對1 628部電影的100 000條評分記錄.(2)1 MB：包括6 040個用戶對3 900部電影的1 000 209條評分記錄.(3)10 MB：包括71 567個用戶對10 681部電影的10 000 054條評分記錄.評分范圍為1～5，每個用戶至少對20部電影進行過評價.

3.2　評價指標(biāo)

采用準(zhǔn)確率、召回率和覆蓋率[15]作為實驗的評價方式，比較本文設(shè)計算法與原有算法的推薦效果.準(zhǔn)確率表示用戶對系統(tǒng)推薦商品感興趣的概率，召回率表示用戶喜歡商品被推薦概率，覆蓋率表示向用戶推薦商品能覆蓋全部商品的比例，表達(dá)推薦的新穎度.準(zhǔn)確率、召回率和覆蓋率度量如下：

(12)

(13)

(14)

式(12)、(13)中：R(u)是通過訓(xùn)練集生成的推薦列表，T(u)是測試集上的行為列表.

式(14)中：Ip表示推薦的物品集，I為所有物品集.

對于單機與Hadoop分布式計算效率的對比評價，引入加速比S=T1/Tn來驗證集群在不同數(shù)量的節(jié)點下對于大小數(shù)據(jù)集的推薦實時性的提升.其中T1表示算法在單機下的運行時間，Tn表示在集群下的進行推薦所用的時間，S越大，表明集群推薦實時性提升越明顯.

3.3實驗結(jié)果與分析

3.3.1推薦結(jié)果分析

以100 KB數(shù)據(jù)集作為實驗數(shù)據(jù)，采用交叉檢驗的方式，隨機選取80%數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，20%作為測試數(shù)據(jù).分別在推薦鄰居個數(shù)為5、10、20、40、60、80的情況下對基于用戶的協(xié)同過濾方法和本文設(shè)計分布式協(xié)同過濾算法進行對比.

首先對用戶電影矩陣依據(jù)算法設(shè)計流程進行降維，為保證保留足夠能量不失真并達(dá)到降維的目的，在使用SVD降維時一般保留90%奇異值能量就可以得到重要特征并去掉噪聲，在此基礎(chǔ)上對用戶進行聚類，聚類集群個數(shù)為8.最終對目標(biāo)用戶在所屬類內(nèi)進行相似度計算，并引入物品貢獻度權(quán)重，生成推薦結(jié)果，與現(xiàn)有協(xié)同過濾算法具體比較結(jié)果如圖4所示.

圖4　評價指標(biāo)對比圖

在圖4中，CF為現(xiàn)有基于用戶的協(xié)同過濾方法，D-CF為本文設(shè)計協(xié)同過濾方法.從圖4可以看出，隨著近鄰用戶個數(shù)的增加，準(zhǔn)確率和召回率上升，到近鄰個數(shù)為40的時候開始趨于平緩，此時D-CF準(zhǔn)確率和召回率相比CF有所提高.覆蓋率上，兩算法都隨著近鄰用戶個數(shù)的增加遞減，但D-CF較CF數(shù)值上有較大的提升，實驗表明D-CF在提升召回率和準(zhǔn)確率的同時，通過引入物品貢獻度權(quán)重較好的提高了推薦的覆蓋率，增強了推薦效果和個性化推薦的長尾挖掘能力，提高了推薦的新穎度.

3.3.2推薦性能分析

選取數(shù)據(jù)量大小分別為100 K、1 MB、10 MB的數(shù)據(jù)分別在不同數(shù)量節(jié)點的Hadoop集群下運行.通過比較S得出不同規(guī)模的集群對算法執(zhí)行效率的影響.實驗結(jié)果如圖5所示.

圖5　加速比對比圖

從圖5可以看出，在實驗數(shù)據(jù)集為100 K時，在單機環(huán)境下執(zhí)行效率更高，這是因為MapReduce過程的中間結(jié)果都會存儲到HDFS之后再進行讀取，期間系統(tǒng)的I/O操作占用了部分時間，說明Hadoop集群在處理小型數(shù)據(jù)集的時候表現(xiàn)并不好，并且不適于數(shù)據(jù)的實時處理.在另外兩個較大數(shù)據(jù)集上，隨著節(jié)點的增加，推薦算法的執(zhí)行效率呈上升趨勢，反映了基于Hadoop的個性化推薦算法提高了推薦的實時性和橫向擴展性.

4　結(jié)論

為了提升個性化推薦系統(tǒng)的大數(shù)據(jù)處理能力，以電影評分為對象，選擇了基于用戶聚類的協(xié)同過濾算法，并在此基礎(chǔ)上進行基于Hadoop個性化推薦的算法設(shè)計與實現(xiàn).對用戶電影矩陣降維，改善對用戶聚類的效果；引入電影貢獻權(quán)重，用于增強算法推薦的新穎度；通過對用戶聚類縮小推薦范圍并對數(shù)據(jù)分類存儲，節(jié)省Hadoop集群的資源計算時間；最終對算法進行了基于MapReduce的并行化實現(xiàn).實驗結(jié)果表明，本文分布式協(xié)同過濾算法提升了個性化推薦新穎度，同時增加了推薦算法的可擴展性和推薦系統(tǒng)的推薦實時性.

[1] Listed N.Information overload[J].Nature,2009,460(7 255):139-143.

[2] Kantor P.B,Ricci F,Rokach L,et al.Recommender systems handbook[M].USA:Springer,2010:1-35.

[3] 王強,李俊杰,陳小軍,等.大數(shù)據(jù)分析平臺的建設(shè)與應(yīng)用綜述[J].集成技術(shù),2016,5(2):2-18.

[4] White T.Hadoop:The definitive guide[M].3rd.USA:O Reilly Media,2012.

[5] 李改，潘嶸，李章鳳，等.基于大數(shù)據(jù)集的協(xié)同過濾算法的并行化研究[J].計算機工程與設(shè)計，2012,33(6):2 437-2 441.

[6] 王毅.基于Hadoop的Slope One及其改進算法實現(xiàn)[D].成都：西南交通大學(xué)，2011.

[7] 黃震華,張佳雯,田春岐,等.基于排序?qū)W習(xí)的推薦算法研究綜述[J].軟件學(xué)報,2016，27(3):691-713.

[8] Truong K,Ishikawa F,Honiden S.Improving accuracy of recommender system by item clustering[J].Ieice Transactions on Information and Systems,2007(9):1 363-1 373..

[9] G.Linden,B.Smith,J.York.Amazon.com recommendation:Item-to-item collaborative filtering[J].IEEE Inter Computing,2003，7(1)：76-80.

[10] Manolis G,Vozalis,Angelos M,et al.Collaborative filtering through SVD-based and hierarchical nonlinear PCA[J].Artificial Neural Networks ICANN,2010,6 352:395-400.

[11] 馬小軍,趙偉.改進相似度的分布式個性化推薦[J].計算機工程與應(yīng)用,2014,50(4):126-131.

[12] Deerwester Scott C,Dumais Susan T,Landauer Thomas K,et al.Indexing by latent semantic analysis[J].Jasis,1990,41(6):391-407.

[13] Koren Y,Bell R,Volinsky C.Matrix factorization techniques for recommender system[J].Computer,2009,42(8):30-37.

[14] Rashid A M,Lam S K,Karyp Is G,et al.Clust KNN:A highly scalable hybrid model & memory-based CF algorithm[C]//The Workshop on in Proc. of Webkdd. Philadelphia,Pennsylvania.USA:ACM,2006:1-59 593-444-8.

[15] 朱郁筱,呂琳媛.推薦系統(tǒng)評價指標(biāo)綜述[J].電子科技大學(xué)學(xué)報,2012,41(2):163-175.