李 程，曹 菡，師 軍

(陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院,陜西 西安 710119)

基于MapReduce的混合推薦算法及應(yīng)用

李 程，曹 菡，師 軍

(陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院,陜西 西安 710119)

針對基于項(xiàng)目與基于用戶兩種傳統(tǒng)協(xié)同過濾算法的不足，文中結(jié)合基于用戶以及基于項(xiàng)目的兩種傳統(tǒng)協(xié)同過濾算法，并加以合理改進(jìn)，提出了一種新型的混合型并行推薦算法。通過對新算法MapReduce編譯，使新算法能夠在Hadoop云平臺下順利運(yùn)行。在可以利用以基于用戶的方法為基礎(chǔ)劃定出定量的鄰居范圍，保證了推薦的個(gè)性化，同時(shí)，利用基于項(xiàng)目的協(xié)同過濾算法進(jìn)行推薦，最終根據(jù)綜合因素調(diào)整評分預(yù)測方法得出符合實(shí)際的推薦結(jié)果。實(shí)驗(yàn)結(jié)果表明，在數(shù)據(jù)量相對較大時(shí)新算法不僅在處理速度上表現(xiàn)更加優(yōu)越，而且明顯提高了推薦精確度。同時(shí)文中將該算法應(yīng)用在西安本土旅游推薦服務(wù)上，針對西安市幾大景點(diǎn)進(jìn)行推薦，使新算法的準(zhǔn)確性在實(shí)際應(yīng)用中得到驗(yàn)證。

MapReduce；Hadoop；混合推薦算法；云計(jì)算

0 引 言

隨著互聯(lián)網(wǎng)的不斷迅速發(fā)展，每日產(chǎn)生的數(shù)據(jù)量呈指數(shù)級增長。在面對大數(shù)據(jù)的大容量、多類型天然特性時(shí)，尤其是處理GB級乃至PB級及以非結(jié)構(gòu)化為主的數(shù)據(jù)時(shí)，要滿足這樣的高時(shí)效性變得尤為困難[1]。在稍縱即逝的市場機(jī)會和變幻莫測的大自然面前，大數(shù)據(jù)的高時(shí)效性猶如皇冠上那顆最炫耀奪目的寶石，吸引了從業(yè)者的目光。

大數(shù)據(jù)在給技術(shù)開發(fā)者帶來大量豐富數(shù)據(jù)的同時(shí)，也給技術(shù)人員增加了從大數(shù)據(jù)中得到有效的用戶信息與相關(guān)興趣數(shù)據(jù)的難度[2]。將推薦系統(tǒng)個(gè)性化不僅能夠從海量的帶有很多干擾的數(shù)據(jù)中挖掘到有用信息，使得推薦具有更好的服務(wù)，也可大幅提升推薦的速度及準(zhǔn)確度[3]。伴隨著數(shù)據(jù)存儲需求的不斷提升，智能化商業(yè)的不斷擴(kuò)大，基于大數(shù)據(jù)挖掘的應(yīng)用也得到了越來越廣泛的研究與應(yīng)用。

在云平臺領(lǐng)域，Hadoop是目前較為熱門的研究平臺[4]，它以存儲的廉價(jià)以及計(jì)算的高效著稱。文中以大數(shù)據(jù)為背景、以云計(jì)算為手段，提出了一種新的混合推薦算法，并深入研究個(gè)性化推薦的內(nèi)在原理，且在Hadoop云平臺下設(shè)計(jì)了并行的個(gè)性化推薦算法，通過實(shí)驗(yàn)驗(yàn)證了其理論意義與實(shí)際應(yīng)用價(jià)值[5]。

1 基于鄰域的推薦算法

在眾多的推薦算法之中，最基本的推薦算法就是基于鄰域的推薦算法[6]。此類算法不僅僅是在應(yīng)用領(lǐng)域得到了推廣，而且還在研究者之間得到了較為深入的研究。此類算法包含兩大類，分別為基于項(xiàng)目的協(xié)同過濾算法和基于用戶的協(xié)同過濾算法。

1.1 基于用戶的協(xié)同過濾算法

最基本的基于用戶的協(xié)同過濾系統(tǒng)，是以興趣相似為基礎(chǔ)，先得到一組用戶，在這個(gè)組中的用戶對其命名為“鄰居”。因?yàn)檫@些鄰居是以興趣相似劃分的，所以他們之間的歷史評分帶有非常強(qiáng)的相似相關(guān)性[7]。由這些鄰居之間的得分而推出的結(jié)果稱之為Top-N推薦。為了得到更為精確的結(jié)果，可以用余弦相似法和皮爾遜相似法來測量每組用戶或者鄰居之間的相似度[8]。

基于用戶的協(xié)同過濾算法由以下兩步組成：

(1)以目標(biāo)用戶為中心尋找相似度高的鄰居用戶形成一個(gè)用戶集；

(2)以這個(gè)用戶集為中心向目標(biāo)用戶推薦用戶集中目標(biāo)用戶沒有涉及的物品或項(xiàng)目。

第1步的重點(diǎn)在于計(jì)算目標(biāo)用戶與測試用戶之間的相似度。在這一步中，利用的主要是行為的相似，通過行為相似度推導(dǎo)出興趣的相似度。假設(shè)有u和v兩個(gè)用戶，設(shè)N(u)代表一個(gè)集合，這個(gè)集合是得到u用戶正反饋的物品集合，設(shè)N(v)也代表一個(gè)集合，這個(gè)集合是v用戶正反饋的物品集合。進(jìn)而通過式(1)計(jì)算出u和v的相似度：

(1)

也可用余弦相似度計(jì)算：

(2)

在計(jì)算出用戶與用戶的興趣相似度后，基于用戶的協(xié)同過濾算法就默認(rèn)給一個(gè)用戶推薦一個(gè)與他興趣最相似的K個(gè)用戶喜歡的物品。式(3)度量了算法中用戶u對物品i的感興趣程度：

(3)

式中：S(u,K)為與u用戶興趣度較相近的K個(gè)用戶；N(i)為與i物品有過打分記錄的用戶集合；wuv為u用戶和v用戶相互間的興趣相似度；rvi代表用戶v對物品i的興趣。

盡管以用戶為基礎(chǔ)的協(xié)同過濾算法流行度很廣，但同時(shí)也存在自身局限，例如可擴(kuò)展性和響應(yīng)性等方面[9]。為了解決這里的局限性問題，誕生出了基于項(xiàng)目的協(xié)同過濾算法，這種協(xié)同過濾算法就是以項(xiàng)目為基礎(chǔ)建立推薦模型[10]。

1.2 基于項(xiàng)目的協(xié)同過濾算法

與基于用戶的協(xié)同過濾算法不同，基于項(xiàng)目的協(xié)同過濾算法是以得分來進(jìn)行推薦的，比較的是用戶與用戶之間對同一個(gè)項(xiàng)目的打分。該算法的核心是得到不同用戶都打分的K個(gè)最相似項(xiàng)目[11]。基于項(xiàng)目的協(xié)同過濾算法采用以下兩步：

(1)通過算法計(jì)算，得到項(xiàng)目與項(xiàng)目間的相似度；

(2)通過項(xiàng)目與項(xiàng)目之間的相似度再加上用戶行為綜合生成一個(gè)推薦列表給用戶。

項(xiàng)目相似度定義為：

(4)

因此式(4)可以看成是喜歡項(xiàng)目i的用戶中有多少比例的用戶同時(shí)也喜歡項(xiàng)目j。

該式存在一定的缺陷，就是當(dāng)j項(xiàng)目為熱門項(xiàng)目時(shí)，其結(jié)果就會接近1，因?yàn)楹芏嗳讼矚g。這就會導(dǎo)致無論什么物品都會跟這種熱門項(xiàng)目有著相似度較大的情況。為了不使這種情況出現(xiàn)，可以運(yùn)用改進(jìn)后的公式：

(5)

從式(5)可以看出，在此公式中對j項(xiàng)目的權(quán)重進(jìn)行了懲罰，從而可以降低熱門項(xiàng)目與其他項(xiàng)目相似的可能。

通過計(jì)算得出項(xiàng)目與項(xiàng)目之間的相似度后，通過式(6)得出u用戶是否對j項(xiàng)目感興趣：

(6)

式中：N(u)是一個(gè)物品集合，代表著用戶喜歡的物品；S(j,k)是和j物品相似度最高的k個(gè)物品集合；wji是物品j和i相互之間的相似度；rui是u用戶對i物品的感興趣程度。

1.3 基于用戶-物品的混合推薦算法

總結(jié)以上兩節(jié)的分析描述，可以利用兩種方法的優(yōu)點(diǎn)，通過融合兩種算法，演變出一個(gè)新的混合型協(xié)同過濾算法。這種新算法的核心就是需要計(jì)算兩類推薦算法的推薦結(jié)果，進(jìn)而進(jìn)行結(jié)果的綜合運(yùn)算[12]。通過這樣的綜合運(yùn)算，可以確保以用戶與用戶相似度動態(tài)計(jì)算出個(gè)性化推薦結(jié)果，同時(shí)也只要用一小部分相似用戶便可以得到很好的推薦質(zhì)量[13]。算法描述如下：

(1)計(jì)算目標(biāo)用戶與其他鄰居用戶的相似度；

(2)預(yù)設(shè)相似度閾值m，若用戶bn的相似度大于閾值m，則作為鄰居；

(3)得到目標(biāo)用戶a的鄰居數(shù)量l；

(4)根據(jù)鄰居利用算法進(jìn)行預(yù)測推薦。

2 基于MapReduce的混合推薦算法

在分布式系統(tǒng)Hadoop運(yùn)算中，第一步是初始化，將每一個(gè)MapReduce過程初始化為兩個(gè)階段[14]，分別是一個(gè)Map過程和一個(gè)Reduce過程。其中，Map過程實(shí)際是一個(gè)Map函數(shù)，Reduce過程實(shí)際是一個(gè)Reduce函數(shù)。在整個(gè)MapReduce過程中，數(shù)據(jù)以一個(gè)的形式進(jìn)行傳輸，首先進(jìn)入Map函數(shù)，經(jīng)過運(yùn)算再以的形式導(dǎo)出。隨后所有的鍵值對經(jīng)過Hadoop，一起傳輸?shù)絉educe階段，經(jīng)過Reduce函數(shù)的鍵值對為的形式，其結(jié)果也會以的形式輸出，形成一組一組的數(shù)據(jù)塊。

在混合協(xié)同過濾算法中，兩個(gè)核心步驟為基于用戶-項(xiàng)目評分矩陣計(jì)算相似度以及基于相似度預(yù)測為評分項(xiàng)目的評分。這兩個(gè)步驟與MapReduce并行處理思想是相契合的，可以編譯實(shí)現(xiàn)。因此，在計(jì)算過程中，輸入的鍵值對可以表示為，輸出的鍵值對可以表示為<(Item1,Item2),Sim>。

第一次MapReduce得出用戶對項(xiàng)目的評分，根據(jù)用戶名進(jìn)行排列；該階段的Map函數(shù)將輸入數(shù)據(jù)轉(zhuǎn)換為相應(yīng)鍵值對，然后用Reduce函數(shù)將相同用戶的項(xiàng)目合并，如圖1所示。

第二次MapReduce得出項(xiàng)目間的相似度，將用戶和項(xiàng)目的鍵值對轉(zhuǎn)換成項(xiàng)目和項(xiàng)目之間的鍵值對。該階段通過Map函數(shù)獲得各項(xiàng)目之間同一用戶的評分對比，隨后通過Reduce函數(shù)得出項(xiàng)目之間的相似度，如圖2所示。

最終得出用戶推薦的相似列表，使用Map函數(shù)對目標(biāo)用戶評分進(jìn)行預(yù)測，然后使用Reduce函數(shù)得出推薦結(jié)果，如圖3所示。

圖1 第一次MapReduce

圖2 第二次MapReduce

圖3 第三次MapReduce

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

(1)實(shí)驗(yàn)準(zhǔn)備。

一臺計(jì)算機(jī)作為NameNode和JobTracker主機(jī)節(jié)點(diǎn)，其余九臺機(jī)器作為DateNode和TaskTracher從節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)配置如下：處理器為Intel(R) Core(TM)2 CPU 6320 @1.86 GHz；內(nèi)存為1 GB；系統(tǒng)類型為Ubuntu12.10，32位操作系統(tǒng)。根據(jù)Hadoop官方網(wǎng)站介紹方法配置部署Hadoop集群版本Hadoop1.0.2。

(2)評估標(biāo)準(zhǔn)。

為了驗(yàn)證實(shí)驗(yàn)結(jié)果的精確度，這里采用平均絕對誤差(MAE)。MAE作為推薦系統(tǒng)的標(biāo)準(zhǔn)評判，能夠評判出推薦系統(tǒng)的預(yù)測精度，它的原理就是經(jīng)過推導(dǎo)得出預(yù)測評分與實(shí)際評分的偏差來評測算法的準(zhǔn)確性。

(7)

其中：IP(u)是推薦系統(tǒng)為用戶u推薦出的項(xiàng)目集;IR(u)是用戶u在測試集數(shù)據(jù)上進(jìn)行評分的項(xiàng)目集；N是IP(u)與IR(u)交集的項(xiàng)目個(gè)數(shù)。

計(jì)算出每個(gè)用戶的MAUE，然后計(jì)算該系統(tǒng)的MAE：

(8)

由式(8)得出：當(dāng)MAE值越小時(shí)證明預(yù)測值與實(shí)際值差異越小。

(3)實(shí)驗(yàn)過程。

實(shí)驗(yàn)以數(shù)據(jù)的80%作為訓(xùn)練集，其余20%為測試集。為使實(shí)驗(yàn)比較更加準(zhǔn)確，將文中算法和基于MapReduce用戶推薦算法、基于MapReduce項(xiàng)目推薦算法，以及串行協(xié)同過濾算法一起進(jìn)行實(shí)驗(yàn)。

3.2 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)一對比各算法之間的MAE平均值，見圖4。

圖4 MAE對比圖

實(shí)驗(yàn)二在單機(jī)環(huán)境下對比各算法之間的處理時(shí)效，見圖5。

圖5 單機(jī)時(shí)效對比圖

實(shí)驗(yàn)三在集群環(huán)境下對比各并行算法處理時(shí)效，見圖6。

圖6 集群時(shí)效對比圖

從圖4可看出，隨著鄰居數(shù)的增多，新算法的推薦質(zhì)量有顯著提高，與其他串行算法對比推薦質(zhì)量并無較大差異，并且與同為并行算法的基于MapReduce的項(xiàng)目推薦算法和用戶推薦算法相比有較好表現(xiàn)。

從圖5可看出，在不同數(shù)據(jù)集中隨著數(shù)據(jù)量的加大，并行算法展現(xiàn)出其獨(dú)特優(yōu)勢，即在較小數(shù)據(jù)集時(shí)需花費(fèi)較多運(yùn)算時(shí)間但在較大數(shù)據(jù)集時(shí)所需時(shí)間大大減少。

從圖6可看出，在不同節(jié)點(diǎn)數(shù)數(shù)據(jù)處理對比時(shí)，證明在多節(jié)點(diǎn)處理上并行算法更有出色的表現(xiàn)。

綜上得出，文中算法確實(shí)在處理大數(shù)據(jù)方面有著一定優(yōu)勢。

4 實(shí)例分析

最近幾年，隨著人民的旅游需求不斷提高，旅游業(yè)蓬勃發(fā)展?！爸腔勐糜巍币云渲悄?、高效，得到了越來越多用戶的親睞。其中一個(gè)特色技術(shù)就是通過分析提取用戶的某些資料以及以往選擇，通過算法分析出一個(gè)此用戶可能感興趣的景點(diǎn)供其游覽。在此前提下，以西安作為背景，結(jié)合在驢友網(wǎng)上搜集的數(shù)據(jù)，對線上的1 785位網(wǎng)友，以及在一些景點(diǎn)的游客，做了關(guān)于西安十五個(gè)景點(diǎn)的評分，過濾掉無效評分得出了4 339條有效數(shù)據(jù)。其中景點(diǎn)編號從J1至J15分別為兵馬俑、華清池、回民街、半坡遺址、大雁塔、乾陵、鐘鼓樓、太白山、歷史博物館、驪山、小雁塔、翠華山、秦嶺野生動物園、曲江、南門，并生成評分矩陣。其中十五個(gè)景點(diǎn)評分為1～5分，不同人對不同景點(diǎn)心中有不同評分，其中有一些干擾數(shù)據(jù)已經(jīng)排除。

從數(shù)據(jù)中可以看出，旅游者已經(jīng)去過這些景點(diǎn)并對它們依次進(jìn)行了打分，得分少的或許是沒有自己游覽或者只是聽說。若想要為某一用戶L推薦下一個(gè)可能喜歡的景點(diǎn)，使用文中算法為其推薦的是景點(diǎn)12，預(yù)測評分4.27。而實(shí)際數(shù)據(jù)其評分為4。從結(jié)果可以看出文中算法確實(shí)能夠根據(jù)旅游者的興趣得出推薦結(jié)果，但在小規(guī)模數(shù)據(jù)上速度確實(shí)存在不足，在集群環(huán)境下速度明顯低于串行算法，原因就在于Hadoop還需要一定時(shí)間在任務(wù)分配上，而真正的處理時(shí)間幾乎微乎其微。如果要想體現(xiàn)出Hadoop處理速度的優(yōu)勢，數(shù)量至少要達(dá)到千萬級別數(shù)據(jù)才行。所以只有在大數(shù)據(jù)量時(shí)，才可以體現(xiàn)出該算法的高效性以及廉價(jià)設(shè)備性。

5 結(jié)束語

針對基于項(xiàng)目與基于用戶兩種傳統(tǒng)協(xié)同過濾算法的不足，文中提出了一種新型的混合型并行推薦算法。實(shí)驗(yàn)結(jié)果表明，新算法不僅在處理速度上表現(xiàn)更加優(yōu)越，而且明顯提高了推薦精確度。同時(shí)該算法在西安本土旅游推薦服務(wù)上的應(yīng)用也驗(yàn)證了算法的準(zhǔn)確性。

[1] 陳如明.大數(shù)據(jù)時(shí)代的挑戰(zhàn),價(jià)值與應(yīng)對策略[J].移動通信,2012(17):14-15.

[2] 余肖生,孫 珊.基于網(wǎng)絡(luò)用戶信息行為的個(gè)性化推薦模型[J].重慶理工大學(xué)學(xué)報(bào)：自然科學(xué),2013,27(1):47-50.

[3] 項(xiàng) 亮.推薦系統(tǒng)實(shí)踐[M].北京：人民郵電出版社，2012.

[4] 劉 剛.Hadoop應(yīng)用開發(fā)技術(shù)詳解[M].北京：機(jī)械工業(yè)出版社，2014.

[5] 陶劍文.一種分布式智能推薦系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].計(jì)算機(jī)仿真,2007，24(7):296-300.

[6] 熊忠陽,劉 芹,張玉芳,等.基于項(xiàng)目分類的協(xié)同過濾改進(jìn)算法[J].計(jì)算機(jī)應(yīng)用研究,2012,29(2):493-496.

[7] 黃創(chuàng)光,印 鑒,汪 靜,等.不確定近鄰的協(xié)同過濾推薦算法[J].計(jì)算機(jī)學(xué)報(bào),2010,33(8):1369-1377.

[8]WangJ,deVriesAP,ReindersMJT.Unifyinguser-basedanditem-basedcollaborativefilteringapproachesbysimilarityfusion[C]//Proceedingsofthe29thannualinternationalACMSIGIRconferenceonresearchanddevelopmentininformationretrieval.NewYork:ACM,2006:501-508.

[9]DeshpandeM,KarypisG.Item-basedtop-nrecommendationalgorithms[J].ACMTransactionsonInformationSystems,2004,22(1):143-177.

[10]LindenG,SmithB,YorkJ.Amazon.comrecommendations:item-to-itemcollaborativefiltering[J].IEEEInternetComputing,2003,7(1):76-80.

[11]LiuQ.ResearchonsomekeytechnologiesofChinese-Englishmachine-intranslation[D].Beijing:PekingUniversity，2004.

[12]SarwarB,KarypisG,KonstanJ,etal.Item-basedcollaborativefilteringrecommendationalgorithms[C]//Proceedingsofthe10thinternationalworldwidewebconference.[s.l.]:[s.n.],2001:285-295.

[13] 劉平峰,聶規(guī)劃,陳冬林.基于知識的電子商務(wù)智能推薦系統(tǒng)平臺設(shè)計(jì)[J].計(jì)算機(jī)工程與應(yīng)用,2007,43(19):199-201.

[14] 李 莉,廖建偉,歐 靈.云計(jì)算初探[J].計(jì)算機(jī)應(yīng)用研究,2010,27(12):4419-4422.

Hybrid Recommendation Algorithm Based on MapReduce and Its Application

LI Cheng,CAO Han,SHI Jun

(School of Computer Science,Shaanxi Normal University,Xi’an 710119,China)

For the shortcomings of traditional project-based and user-based collaborative filtering algorithm,a new parallel recommendation algorithm is proposed,combined user-based with project-based collaborative filtering algorithm and improved them.Through MapReduce compilation,the new algorithm can run in Hadoop cloud platform.To guarantee the personalized recommendation,it can take advantages of the collaborative filtering algorithm based on user defined a certain number of neighbors.At the same time,the project-based collaborative filtering algorithm is used to recommend.Finally,according to the comprehensive adjusted score prediction method,the recommended results are obtained.The experimental results show that the algorithm becomes more superior in the case of a large number of processing speed,and improves the accuracy of recommendation.Simultaneously,the algorithm is applied in local tourism of Xi’an referral service for several major attractions to recommend.The accuracy of the new algorithm has been verified in practical applications.

MapReduce;Hadoop;hybrid recommendation algorithm;cloud computing

2014-11-25

2015-04-15

時(shí)間：2016-04-00

國家自然科學(xué)基金資助項(xiàng)目(41271387)；西安市科技計(jì)劃基金資助項(xiàng)目(SF1228-3)

李 程(1989-),男,碩士研究生,研究方向?yàn)楦咝阅苡?jì)算、云計(jì)算；曹 菡,博士，教授,研究方向?yàn)閿?shù)據(jù)挖掘、智慧旅游、高性能計(jì)算；師 軍，副教授,研究方向?yàn)橹悄苄畔⑻幚怼?/p>

http://www.cnki.net/kcms/detail/61.1450.TP.20160322.1517.018.html

TP311

A

1673-629X(2016)04-0074-04

10.3969/j.issn.1673-629X.2016.04.016