基于用戶的協(xié)同過濾推薦算法MapReduce并行化實(shí)現(xiàn)

李沖

摘要：基于用戶的協(xié)同過濾推薦算法是應(yīng)用范圍廣且應(yīng)用效果較好的推薦算法之一。傳統(tǒng)單機(jī)模式下運(yùn)行的基于用戶的協(xié)同過濾推薦算法在面對海量數(shù)據(jù)時存在嚴(yán)重的性能瓶頸問題，很難滿足實(shí)際計算需求，而基于MapReduce的并行計算框架為解決該問題提供了新思路。MapReduce是Hadoop開源框架的核心計算編程模型， MapReduce的設(shè)計目標(biāo)是方便編程人員在不熟悉分布式并行編程的情況下，可將自己的程序運(yùn)行在分布式系統(tǒng)上。根據(jù)基于用戶的協(xié)同過濾推薦算法特點(diǎn)，提出MapReduce并行化實(shí)現(xiàn)方法。實(shí)驗(yàn)結(jié)果表明，在MapReduce并行計算框架下實(shí)現(xiàn)的基于用戶的協(xié)同過濾推薦算法在算法性能及穩(wěn)定性方面都取得了理想效果。

關(guān)鍵詞：MapReduce；Hadoop；分布式計算；推薦算法

DOIDOI：10.11907/rjdk.181108

中圖分類號：TP312

文獻(xiàn)標(biāo)識碼：A 文章編號：1672-7800（2018）010-0076-05

英文摘要Abstract：The recommended algorithm based on collaborative filtering of users is a recommended algorithm which has a wide range of applications and is effective in practical applications. However， the traditional recommendation algorithm based on user-based collaborative filtering running in stand-alone mode encounters a serious performance bottleneck in the case of massive data and is difficult to meet the actual computing requirements. The MapReduce-based parallel computing framework provides a new solution to this problem. MapReduce is a kernel computing programming model of Hadoop open source framework. MapReduce is designed to facilitate programmers to run their own programs on distributed systems without being familiar with distributed parallel programming. Based on the research of the characteristics of user-based collaborative filtering recommendation algorithm， this paper proposes a method based on MapReduce parallel computing framework. The experimental results show that the proposed user-based collaborative filtering algorithm based on MapReduce parallel computing framework achieves the desired performance in terms of performance and stability of the algorithm.

英文關(guān)鍵詞Key Words：MapReduce；Hadoop；distributed computing；recommendation algorithm

0 引言

如今人們生活在一個信息超載的時代，生活各領(lǐng)域充斥著大量信息資源，如何從海量信息資源中快速高效地獲取有用信息一直是研究人員的研究熱點(diǎn)[1]。近年來各種推薦算法的出現(xiàn)為解決信息超載問題提供了解決方案，其中基于用戶的協(xié)同過濾推薦算法是眾多推薦算法中比較經(jīng)典，且應(yīng)用范圍較廣、實(shí)際應(yīng)用效果較好的一個推薦算法[2]。算法基本思想是通過判斷兩個用戶是否具有相似偏好，如果兩人偏好相近，則可以將另一個用戶評分較高的物品推薦給目標(biāo)用戶。但是隨著數(shù)據(jù)量的爆炸式增長，傳統(tǒng)基于單機(jī)模式運(yùn)行的推薦算法在處理海量數(shù)據(jù)時存在嚴(yán)重的性能瓶頸問題，很難滿足實(shí)際計算需求。文獻(xiàn)[3]提出在Hadoop上實(shí)現(xiàn)基于用戶的CF算法，解決了CF的擴(kuò)展性問題，但其采用的利用Hadoop實(shí)現(xiàn)的推薦算法只是在過程中的個別階段實(shí)現(xiàn)了并行化，算法性能仍有很多不足。本文在推薦算法實(shí)現(xiàn)過程中，通過將整個任務(wù)切分成6個任務(wù)串聯(lián)的方式，對整個推薦過程進(jìn)行并行化實(shí)現(xiàn)。近年來基于Hadoop的分布式計算開源框架的出現(xiàn)使各種推薦算法實(shí)現(xiàn)并行化計算成為可能，各種推薦算法可采用基于MapReduce的分布式計算框架實(shí)現(xiàn)算法并行化，從而為解決推薦算法面對海量數(shù)據(jù)時存在的性能瓶頸問題提供了新的思路。近年來，大量研究人員采用基于MapReduce的分布式計算框架對傳統(tǒng)算法進(jìn)行并行化實(shí)現(xiàn)并取得了良好效果，例如文獻(xiàn)[4]針對FCM聚類集成算法隨著數(shù)據(jù)量增加導(dǎo)致時間復(fù)雜度過高的問題，提出一種基于MapReduce框架的并行FCM聚類集成算法；文獻(xiàn)[5]通過對傳統(tǒng)單種群粒子群算法的分析，提出一種基于MapReduce模型的分布式粒子群算法，解決粒子群算法在求解大規(guī)模優(yōu)化問題時求解效率與精度明顯下降等問題；文獻(xiàn)[6]針對傳統(tǒng)單點(diǎn)串行的分類算法在面對新聞數(shù)據(jù)規(guī)模大、分類屬性多時效率較低的問題，提出樸素貝葉斯分類算法在MapReduce下的并行實(shí)現(xiàn)方法。

Hadoop是一個開源云計算平臺，用戶可以充分利用集群的計算與存儲能力在Hadoop平臺上完成海量數(shù)據(jù)處理[7]。本文根據(jù)基于用戶的協(xié)同過濾推薦算法特點(diǎn)以及MapReduce的運(yùn)行機(jī)制對基于用戶的協(xié)同過濾推薦算法進(jìn)行并行化實(shí)現(xiàn)，并給出了具體步驟描述。最后通過實(shí)驗(yàn)對比并行化前后算法性能，表明本文采用的在MapReduce下實(shí)現(xiàn)的并行化推薦算法有更好的性能。

1 基于用戶的協(xié)同過濾推薦算法

基于用戶的協(xié)同過濾推薦算法基本思想是根據(jù)用戶對有過行為的物品評分刻畫兩個用戶是否是具有相似偏好，如果兩人偏好相近，則可以將另一個用戶評分較高的物品推薦給目標(biāo)用戶[8]。

（1）map階段：①系統(tǒng)根據(jù)設(shè)置的塊大小，對全部數(shù)據(jù)進(jìn)行分塊，每塊數(shù)據(jù)被一個map任務(wù)加以執(zhí)行，map端對數(shù)據(jù)逐條進(jìn)行處理，并將處理結(jié)果以鍵值對形式存儲在一個環(huán)形緩沖區(qū)中。當(dāng)環(huán)形緩沖區(qū)內(nèi)的數(shù)據(jù)量達(dá)到一個閾值（默認(rèn)為緩沖區(qū)大小的80%），此時環(huán)形緩沖區(qū)會將數(shù)據(jù)寫出到本地臨時文件中[11]；②在寫出數(shù)據(jù)之前，系統(tǒng)會根據(jù)設(shè)置的分區(qū)策略進(jìn)行分區(qū)，對屬于相同分區(qū)的數(shù)據(jù)進(jìn)行排序，并且如果有設(shè)置combiner，則會將結(jié)果先combiner之后再放到相同的臨時文件中；③map端將屬于同一分區(qū)的臨時文件進(jìn)行合并，當(dāng)端處理完所有數(shù)據(jù)并合并完成所有臨時文件時，map端會通知相應(yīng)的reduce端收集數(shù)據(jù)[12]。

（2）reduce階段：①reduce端會從各個map端將屬于該reduce的數(shù)據(jù)拉取過來；②reduce端將拉取過來的所有數(shù)據(jù)進(jìn)行合并，并且根據(jù)設(shè)置的分組策略對key值進(jìn)行排序，此時reduce端會將具有相等key值的數(shù)據(jù)放在一個分區(qū)；③reduce端根據(jù)設(shè)置的二次排序策略對數(shù)據(jù)進(jìn)行二次排序，并將最終處理結(jié)果以鍵值對形式輸出[13]。

3 基于用戶的協(xié)同過濾推薦算法并行化實(shí)現(xiàn)

基于用戶的協(xié)同過濾推薦算法是指根據(jù)用戶與物品行為信息得到目標(biāo)用戶的近鄰用戶，根據(jù)近鄰用戶對物品行為信息為目標(biāo)用戶作推薦。具體步驟如下：①根據(jù)用戶對物品的行為信息計算用戶之間相似度；②根據(jù)相似度高低得到目標(biāo)用戶的近鄰用戶；③根據(jù)近鄰用戶對物品的行為信息，得到目標(biāo)用戶的候選推薦列表；④從候選推薦列表中去除用戶已經(jīng)有過行為的物品。

基于用戶的協(xié)同過濾推薦算法采用6個并行化任務(wù)加以實(shí)現(xiàn)，整體流程如圖2所示。

從圖2可以看出，任務(wù)之間通過上一個任務(wù)的輸入作為下一個任務(wù)輸出的形式進(jìn)行連接。從最初的將用戶與物品行為信息作為輸入，經(jīng)過6個任務(wù)的處理，最后輸出為每個用戶進(jìn)行推薦的推薦列表。其中每個任務(wù)具體流程如下：

任務(wù)1：將用戶與物品行為信息作為任務(wù)輸入，得到每個用戶產(chǎn)生行為的物品數(shù)量，并將物品Id（itemId）作為key，用戶Id與物品數(shù)量組合（userId：itemSize）作為value。

map階段：map端將用戶與物品行為信息作為輸入，map端對數(shù)據(jù)進(jìn)行分割，將用戶Id作為key值，物品Id作為value輸出。

reduce階段：對map階段發(fā)送的數(shù)據(jù)進(jìn)行處理，并根據(jù)key值進(jìn)行聚合，計算一個用戶發(fā)生行為的物品數(shù)量itenSize，并將物品（itemId）作為key，用戶Id與物品數(shù)量組合（userId：itemSize）作為value。

任務(wù)2：將任務(wù)1的輸出結(jié)果作為輸入，得到對同一物品發(fā)生行為的所有用戶以及兩兩組合結(jié)果。

map階段：將數(shù)據(jù)分割并輸出。

reduce階段：對map端發(fā)送的數(shù)據(jù)進(jìn)行處理，并根據(jù)key值進(jìn)行分組，計算對同一物品發(fā)生行為的所有用戶以及兩兩組合結(jié)果。

任務(wù)3：將任務(wù)2的輸出作為任務(wù)的輸入，計算兩兩用戶之間的相似度。

map階段：將數(shù)據(jù)的value作為輸出的key，NullWritable作為輸出的value。

reduce階段：根據(jù)map端發(fā)送的數(shù)據(jù)，與key值（兩兩用戶之間的組合）進(jìn)行聚合，計算用戶之間相似度。

任務(wù)4：將任務(wù)3的輸出作為任務(wù)的輸出，計算用戶的k近鄰用戶。

（1）map階段：將數(shù)據(jù)分割后直接輸出。

（2）自定義分區(qū)策略：為了計算用戶u1的k近鄰用戶，需要將用戶u1與其他具有一定相似度的用戶進(jìn)行相似度對比，并對兩兩用戶組合<（u1：u2），similarity>中的第一個用戶u1進(jìn)行分區(qū)，以保證用戶u1與其他具有一定相似度的用戶能夠被同一個reduce處理。

（3）自定義分組策略：在步驟（2）中保證了用戶u1與其他具有一定相似度的用戶能夠被同一個reduce處理，要將用戶u1與其他用戶的相似度進(jìn)行對比，需要將這些用戶放在同一個迭代器中，所以還需要根據(jù)<（u1：u2），similarity>中的第一個用戶u1定義分組策略。

（4）reduce階段：根據(jù)自定義的分區(qū)與分組策略在同一個迭代器中計算目標(biāo)用戶的k近鄰用戶。

任務(wù)5：將輸入分為兩部分，一部分是任務(wù)4的輸出，另一部分是用戶與物品的行為信息，最終計算目標(biāo)用戶的候選推薦列表。

map1階段：將任務(wù)4的輸出作為輸入，并將近鄰用戶作為key值、目標(biāo)用戶作為value值進(jìn)行輸出。

map2階段：將用戶與物品的行為信息作為輸入，并將用戶作為key值、物品作為value值輸出。

reduce階段：根據(jù)map1階段與map2階段的輸出，利用key值進(jìn)行聚合，并為目標(biāo)用戶作推薦。

任務(wù)6：將輸入分為兩部分，一部分是任務(wù)5的輸出，另一部分是用戶與物品行為信息，從任務(wù)5產(chǎn)生的候選推薦列表中去除用戶已經(jīng)產(chǎn)生行為的物品。

map1階段：將任務(wù)5的輸出作為輸入，并將用戶Id作為key值、候選推薦列表作為value值進(jìn)行輸出。

map2階段：將用戶與物品行為信息作為輸入，并將用戶作為key值，物品作為value值輸出。

reduce階段：根據(jù)map1與map2階段的輸出，利用key值進(jìn)行聚合，從用戶候選推薦列表中去除用戶已經(jīng)產(chǎn)生過行為的物品。

4 實(shí)驗(yàn)及結(jié)果分析

通過實(shí)驗(yàn)對MapReduce并行計算框架下實(shí)現(xiàn)的基于用戶的協(xié)同過濾推薦算法進(jìn)行性能評估。

4.1 實(shí)驗(yàn)環(huán)境

該實(shí)驗(yàn)在北京郵電大學(xué)實(shí)驗(yàn)室集群上運(yùn)行，集群由10臺機(jī)器組成，其中一臺機(jī)器為主節(jié)點(diǎn)，其它機(jī)器均為從節(jié)點(diǎn)，網(wǎng)絡(luò)采用萬兆網(wǎng)絡(luò)，操作系統(tǒng)為centos，Hadoop版本為2.6.4，JDK為1.7.0_25。硬件配置為每臺機(jī)器CPU主頻3.3GHz，內(nèi)存8GB，硬盤1TB。

4.2 實(shí)驗(yàn)數(shù)據(jù)

本次實(shí)驗(yàn)以北京郵電大學(xué)圖書館的讀者借閱信息作為實(shí)驗(yàn)數(shù)據(jù)，數(shù)據(jù)量包括2013年1月～2017年6月的讀者借閱記錄。

4.3 結(jié)果分析

實(shí)驗(yàn)從數(shù)據(jù)量以及節(jié)點(diǎn)數(shù)兩個維度衡量并行化后的推薦算法性能。

從圖3中可以看到，單機(jī)運(yùn)行的協(xié)同過濾推薦算法在處理2013年全年數(shù)據(jù)時需要耗時653s，而采用并行化后的推薦算法隨著節(jié)點(diǎn)數(shù)增加，運(yùn)行時間大幅減少。

從圖4中可以看到，當(dāng)實(shí)驗(yàn)數(shù)據(jù)增加1倍時，基于單機(jī)模型下運(yùn)行時間從原來的653s增加到了1 544s，增幅超過2倍，基于并行計算模型下運(yùn)行的推薦算法則在運(yùn)行時間上增幅較小。

從實(shí)驗(yàn)結(jié)果可以看出，并行模式下運(yùn)行的基于用戶的協(xié)同過濾推薦算法相比于單機(jī)模式，在性能上具有很大優(yōu)勢。

5 結(jié)語

本文針對單機(jī)模型下基于用戶的協(xié)同過濾推薦算法面對海量數(shù)據(jù)時存在的嚴(yán)重性能瓶頸問題，提出MapReduce并行計算框架下的基于用戶的協(xié)同過濾推薦算法。實(shí)驗(yàn)結(jié)果表明，并行化后的基于用戶的協(xié)同過濾推薦算法在處理海量數(shù)據(jù)時，相比于傳統(tǒng)單機(jī)模式在性能上有著巨大優(yōu)勢。

參考文獻(xiàn)：

[1] 張宇，程久軍.基于MapReduce的矩陣分解推薦算法研究[J].計算機(jī)科學(xué)， 2013（1）：19-21，36.

[2] 楊博，趙鵬飛.推薦算法綜述[J].山西大學(xué)學(xué)報：自然科學(xué)版，2011，34（3）：337-350.

[3] 王斯鋒，祝永志，劉文超.運(yùn)行在Hadoop上的基于用戶的協(xié)同過濾推薦算法研究[J].電子技術(shù)，2017，46（11）：73-75.

[4] 馬自堂，茍杰.基于MapReduce的FCM聚類集成算法[J].計算機(jī)應(yīng)用研究， 2016（12）： 3554-3558.

[5] 范德斌，鄧長壽，袁斯昊，等.基于MapReduce模型的分布式粒子群算法 [J]. 山東大學(xué)學(xué)報：工學(xué)版，2016（6）：23-30，61.

[6] 徐保鑫，懷麗波，崔榮一.基于MapReduce的樸素貝葉斯算法在新聞分類中的應(yīng)用[J]. 延邊大學(xué)學(xué)報：自然科學(xué)版， 2017（1）： 55-59.

[7] 符彩珍，周國軍，莫麗清，等.基于Hadoop的排序算法并行化改進(jìn)[J].軟件導(dǎo)刊， 2016（4）： 68-71.

[8] 王興茂.基于用戶的協(xié)同過濾推薦算法研究[D].鄭州：解放軍信息工程大學(xué)，2015.

[9] 劉輝.基于用戶的協(xié)同過濾推薦算法的改進(jìn)研究[D].泉州：華僑大學(xué)，2016.

[10] 李建江，崔健，王聃，等.MapReduce并行編程模型研究綜述[J].電子學(xué)報，2011，39（11）：2635-2642.

[11] 宋杰，徐澍，郭朝鵬， 等.一種優(yōu)化MapReduce系統(tǒng)能耗的任務(wù)分發(fā)算法[J].計算機(jī)學(xué)報，2016，39（2）：323-338.

[12] 郝樹魁.Hadoop HDFS和MapReduce架構(gòu)淺析[J].郵電設(shè)計技術(shù)，2012（7）：37-42.

[13] 王晟，趙壁芳.云計算中MapReduce技術(shù)研究[J].通信技術(shù)，2011，44（12）：159-161.

（責(zé)任編輯：黃 ?。?/p>