李沖

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

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

DOIDOI：10.11907/rjdk.181108

中圖分類(lèi)號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.3 結(jié)果分析

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

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

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

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

5 結(jié)語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

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

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

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

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

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

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

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

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

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

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