一種用于大數(shù)據(jù)的改進(jìn)的ItemBased推薦算法?

李 洋 黃樹成

（江蘇科技大學(xué)計算機學(xué)院 鎮(zhèn)江 212003）

1 引言

隨著信息化時代的發(fā)展，人們生活與工作中所產(chǎn)生、接收的信息量越來越龐大，對信息的處理和過濾就顯得尤為重要。信息的過濾可以通過推薦算法來實現(xiàn)。好的推薦算法對整個系統(tǒng)的推薦準(zhǔn)確度以及系統(tǒng)性能提升有很大的幫助。近年來，國內(nèi)外涌現(xiàn)了不少高效的推薦算法，有內(nèi)容關(guān)聯(lián)算法、K-means聚類算法等［1］。隨著大數(shù)據(jù)時代來臨，推薦系統(tǒng)中的數(shù)據(jù)量和需要推薦的商品數(shù)量呈指數(shù)倍增長，使得大量數(shù)據(jù)的處理速度過慢，因此推薦算法領(lǐng)域中產(chǎn)生了分布式推薦算法這一研究方向。

在信息泛濫的網(wǎng)絡(luò)世界中，只有擁有對大數(shù)據(jù)的處理能力，才能快速高效地對海量數(shù)據(jù)進(jìn)行過濾、篩選，并在極短的時間內(nèi)對用戶的需求做出響應(yīng)。在本文中，將會介紹傳統(tǒng)協(xié)同過濾推薦算法（Collaborative filtering recommendation），并對User?Based算法和ItemBased算法分別加以介紹，對兩種算法的優(yōu)缺點進(jìn)行分析，并修改原有的ItemBased算法來提升算法的性能、優(yōu)化其短板［2］。

2 協(xié)同過濾算法

協(xié)同過濾推薦算法的原理是統(tǒng)計與目標(biāo)用戶有著相同興趣的用戶，或者有同樣的經(jīng)驗的用戶群體，歸納該用戶群體感興趣的信息，將這些信息推薦給目標(biāo)用戶［3］。個人用戶能夠通過反饋一定的信息（如評價）能夠為其他用戶的推薦提供一定的幫助。協(xié)同過濾算法能夠幫助目標(biāo)用戶發(fā)現(xiàn)他們潛在的興趣或者可能喜歡的物品，并且這種推薦算法推薦的質(zhì)量都比較高。

協(xié)同過濾算法分為以用戶為基礎(chǔ)（UserBased）的協(xié)同過濾和以項目為基礎(chǔ)（ItemBased）的協(xié)同過濾兩大類。

以用戶為基礎(chǔ)的協(xié)同過濾算法，通過使用相似統(tǒng)計的方法，獲取到具有相似興趣的相鄰用戶進(jìn)行推薦，因此該算法又稱為基于鄰居的協(xié)同過濾算法（Neighbor-based Collaborative Filtering）。

以項目為基礎(chǔ)的協(xié)同過濾算法，通過統(tǒng)計用戶本來喜好的、評分高的項目，再找到與之相似的項目，通過計算項目之間的相似性，達(dá)到來代替用戶之間的相似性。該算法認(rèn)為通過這種方法找到的項目更能夠引起用戶的興趣。同時，以用戶為基礎(chǔ)的協(xié)同過濾算法在用戶數(shù)量增加的時候，算法的計算時間會變得更長，而已項目為基礎(chǔ)的協(xié)同過濾算法剛好能夠解決這一問題。在本文中，也正是需要對這一算法進(jìn)行改進(jìn)。

該方法需要以下幾個步驟。

1）收集用戶信息

這里的用戶信息主要指的是用戶對于不同項目的興趣信息，比如說有許多網(wǎng)站會讓用戶在使用過后進(jìn)行評價，根據(jù)用戶的評價好壞以及評價等級來判斷用戶的喜好程度［4］。除此之外，可以根據(jù)用戶在網(wǎng)上的行為進(jìn)行收集信息，系統(tǒng)根據(jù)用戶的行為進(jìn)行喜好程度評價，比如用戶點贊、收藏、分享等行為，或者在次使用等行為，都能夠讓系統(tǒng)進(jìn)行自動評價，不需要用戶去主動地進(jìn)行評價操作或者輸入相關(guān)的評價數(shù)據(jù)。由于在電子商務(wù)網(wǎng)站有許多用戶的商品購買及使用操作記錄，這種算法在電子商務(wù)網(wǎng)站上有很大的優(yōu)勢［5］。

2）針對物品的最近鄰搜索

將待測物品和已評價的物品的相似度作為權(quán)重，加權(quán)已評價物品的分?jǐn)?shù)，就能夠得到待預(yù)測物品的預(yù)測值。比如要同時對A和B兩個物品進(jìn)行計算，就要先找到同時對A和B進(jìn)行評價過的用戶，用這些用戶的組合進(jìn)行計算。目前較為常見的相似度算法有皮爾森相關(guān)系數(shù)公式、余弦相似度公式以及修正的余弦相似度公式等。

設(shè)現(xiàn)有兩件物品a和b，用戶u，物品a和物品b都評價過的用戶集合為Uab，用戶u對物品a和物品b的評價分別為rua和rub，物品a和物品b的評分期望值分別為`rˉa和`rˉb，則根據(jù)皮爾森相關(guān)系數(shù)公式可得，物品a和b之間的相似度SIM（a，b）的值如式（1）所示：

3）產(chǎn)生推薦結(jié)果

根據(jù)用戶已評價的物品和待測物品間的相似度，計算出適合推薦的物品作為推薦結(jié)果，進(jìn)而推送給對應(yīng)的用戶［6］。與UserBased推薦算法相比，ItemBased協(xié)同過濾推薦算法在進(jìn)行推薦計算是不需要使用目標(biāo)用戶的歷史數(shù)據(jù)，因此推薦的精準(zhǔn)度不會受到冷啟動的影響。一般情況下不同的物品之間的相似性非常穩(wěn)定，受到用戶數(shù)量變化的影響很小，因此許多關(guān)于推薦計算的步驟可以離線完成［9］，不會影響在線用戶的體驗，效率比UserBased算法要高。當(dāng)然，這一算法更適用于用戶數(shù)量多于數(shù)量的情況。

3 基于Hadoop平臺的ItemBased推薦算法

與其他推薦算法相比，傳統(tǒng)的協(xié)同過濾推薦算法有自己的優(yōu)勢，但是仍然還存在些許不足之處［10］。主要表現(xiàn)在以下幾個方面。

1）冷啟動推薦精準(zhǔn)度不夠

一般的推薦系統(tǒng)在進(jìn)行推薦的時候需要使用大量用戶的歷史評價數(shù)據(jù)，尤其是傳統(tǒng)的User?Based推薦算法，對數(shù)據(jù)的需求尤為明顯。在本文中使用的ItemBased推薦算法對用戶的歷史評價記錄依賴程度并不高，受到冷啟動問題的影響也不大。

2）稀疏數(shù)據(jù)推薦可靠性低

在協(xié)同過濾推薦系統(tǒng)中，用戶評價的數(shù)據(jù)越多，最終根據(jù)算法得出的推薦結(jié)果越可靠，但是當(dāng)用戶的評價數(shù)量很少的時候，或者兩個項目之間共同評價的用戶的數(shù)量很少甚至沒有的時候，通過皮爾森相關(guān)系數(shù)公式計算出的推薦結(jié)果可靠性就會大幅下降。很明顯，數(shù)據(jù)的稀疏性［7］對于推薦的可靠性有非常大的影響。因此在原公式修改為式（2）：

其中λ是對當(dāng)前推薦結(jié)果的可靠性的度量，它的值為原始評價矩陣中項目間評分用戶交集個數(shù)與項目間評分用戶交集大小閾值的商，取值范圍為（0，1］。當(dāng)用戶評價的交集越大，推薦的準(zhǔn)確度越高，λ值也就越大。

3）可擴展性問題

隨著系統(tǒng)的不斷使用，產(chǎn)生的數(shù)據(jù)量會不斷增多，處理數(shù)據(jù)的時間也會相應(yīng)地變長。這時，算法的可擴展性就顯得尤為重要［8］。近年來，越來越多的推薦系統(tǒng)中都遇到了這一問題，推薦算法的可擴展性也受到了越來越多人的關(guān)注［11］。為了解決這一問題，本文中使用了Hadoop集群實現(xiàn)對數(shù)據(jù)的分布式計算和存儲。

Hadoop是一個開源的分布式計算框架，它提供了分布式文件系統(tǒng)HDFS（Hadoop Distributed File System）和MapReduce分布式計算的軟件架構(gòu)。MapReduce框架的計算過程分為Map和Re?duce兩個階段。在MapReduce作業(yè)中，輸入的數(shù)據(jù)集被且分為若干獨立的數(shù)據(jù)塊，現(xiàn)有Map任務(wù)并行處理，對Map的輸出數(shù)據(jù)排序后，再作為輸入數(shù)據(jù)交由Reduce任務(wù)處理，最終輸出計算結(jié)果。每個階段的輸入輸出數(shù)據(jù)格式是以形式呈現(xiàn)的鍵值對。開發(fā)者只需要編寫Map和Reduce階段的映射函數(shù)即可，任務(wù)裝載、調(diào)度和節(jié)點間的通信由Hadoop自動完成。該集群的工作流程如圖1所示。

圖1 算法工作流程圖

4 實驗結(jié)果分析

4.1 實驗平臺及數(shù)據(jù)說明

根據(jù)上述研究，利用7臺計算機作為硬件，其中有1個Master節(jié)點和6個Salave節(jié)點。計算機統(tǒng)一搭載Ubuntu 15.04，Hadoop版本為3.1.2，JDK版本為1.8.0_181。

本文中的實驗選取了MovieLens中的電影評價數(shù)據(jù)集，并分別下載了大小為100KB、1MB、10MB的數(shù)據(jù)集進(jìn)行實驗，數(shù)據(jù)集的詳細(xì)信息如下：1）100KB：包括943個用戶對1628部電影的100000條評分記錄；2）1MB：包括6040個用戶對3900部電影的1000209條評分記錄；3）10MB：包括71567個用戶對10681部電影的1000054條評分記錄，評分范圍為1～5，每個用戶至少對20部電影進(jìn)行過評價。

4.2 實驗結(jié)果評估指標(biāo)

本文中的實驗結(jié)果評估指標(biāo)主要有兩項：加速比和平均絕對偏差MAE。

加速比就是指在相同的系統(tǒng)環(huán)境下使用同樣的數(shù)據(jù)集對目標(biāo)商品進(jìn)行選擇推薦，單機運行串行算法與集群運行并行算法所需時間之比。設(shè)程序的串行時間為T1，在N個節(jié)點上的并行時間為TN，則加速比的公式如式（3）所示。

平均絕對偏差MAE在本文中用來衡量推薦準(zhǔn)確度。其基本思想是通過計算預(yù)測值和真實值之間的平均絕對偏差來衡量算法的最終運行結(jié)果和真實值的偏差大小。MAE的值越小，就代表推薦值和真實值之間的誤差就越小，推薦結(jié)果也就越準(zhǔn)確。設(shè)Pi為項目的預(yù)測評分值，Ri為項目的真實評分值，N為實驗中的項目個數(shù)，則MAE值的公式見式（4）。

4.3 結(jié)果分析

本文選取平均絕對誤差（MAE）作為算法推薦質(zhì)量的衡量指標(biāo)。MAE值越小，意味著推薦結(jié)果的準(zhǔn)確度越高。從100KB數(shù)據(jù)集中，分別選取用戶數(shù)量為50、200、400、800和943作為5組實驗數(shù)據(jù)。實驗結(jié)果見表1。

表1 數(shù)據(jù)集詳細(xì)數(shù)據(jù)

在5組實驗數(shù)據(jù)下將本文提出的算法分別放在非分布式環(huán)境和分布式環(huán)境下進(jìn)行推薦，計算MAE值，最終結(jié)果如圖2所示。

圖中，縱軸為MAE值，橫軸為5組實驗數(shù)據(jù)的編號，根據(jù)圖中的折線圖可以看出，本文提出的基于Hadoop平臺的ItemBased推薦算法的MAE值要低于另外兩種算法，并且三種算法最終的MAE值都隨著實驗數(shù)據(jù)量的增大而減小，推薦精度也越高。兩種ItemBased算法在第一組數(shù)據(jù)中存在著一定的數(shù)據(jù)稀疏性的問題，尤其是分布式ItemBased算法，其第一組數(shù)據(jù)中的稀疏性問題頗為嚴(yán)重［12］。而本文的算法在第一組數(shù)據(jù)中克服了數(shù)據(jù)稀疏性的問題，MAE值遠(yuǎn)低于另外兩種算法。這說明本文提出的算法能夠很好地解決數(shù)據(jù)稀疏性問題。

另外，本文使用加速比來比較Hadoop集群對于多種不同規(guī)模數(shù)據(jù)的執(zhí)行效率。由上文可知加速比S=T1/Tn，T1為單個節(jié)點的運算時間，Tn為n個節(jié)點的運算時間。在實驗過程中分別啟動1～7臺運算節(jié)點，分別根據(jù)運行時間繪制曲線圖如圖3。

圖3 數(shù)據(jù)集處理加速比變化

該圖顯示三個不同大小的數(shù)據(jù)集在Hadoop集群上進(jìn)行算法處理的加速比變化。這表明，針對同一數(shù)據(jù)集，增加節(jié)點數(shù)量可以提高算法效率。這種效率的提升在節(jié)點數(shù)量少的時候還不明顯，當(dāng)節(jié)點數(shù)量多之后，效率的提升效果就會非常明顯。因此基于Hadoop集群的ItemBased推薦算法在大數(shù)據(jù)規(guī)模下?lián)碛辛己玫目蓴U展性。

5 結(jié)語

傳統(tǒng)的協(xié)同過濾推薦算法中存在著數(shù)據(jù)稀疏性和可擴展性兩個問題［13］，本文針對這兩個問題進(jìn)行了深入的研究，并通過實驗驗證了自己的優(yōu)化方案。本文將ItemBased推薦算法稍作改進(jìn)，增加了推薦結(jié)果可靠性的權(quán)值，并根據(jù)Hadoop集群的分布式計算特點將算法移植到Hadoop集群進(jìn)行Ma?pReduce化處理。通過實驗證明，改算法能夠顯著改善推薦算法的數(shù)據(jù)稀疏性和可擴展性，從而提高大數(shù)據(jù)環(huán)境下的數(shù)據(jù)處理能力。