一種用于大數據的改進的ItemBased推薦算法?

李 洋 黃樹成

（江蘇科技大學計算機學院 鎮江 212003）

1 引言

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

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

2 協同過濾算法

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

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

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

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

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

1）收集用戶信息

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

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

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

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

3）產生推薦結果

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

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

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

1）冷啟動推薦精準度不夠

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

2）稀疏數據推薦可靠性低

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

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

3）可擴展性問題

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

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

圖1 算法工作流程圖

4 實驗結果分析

4.1 實驗平臺及數據說明

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

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

4.2 實驗結果評估指標

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

加速比就是指在相同的系統環境下使用同樣的數據集對目標商品進行選擇推薦，單機運行串行算法與集群運行并行算法所需時間之比。設程序的串行時間為T1，在N個節點上的并行時間為TN，則加速比的公式如式（3）所示。

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

4.3 結果分析

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

表1 數據集詳細數據

在5組實驗數據下將本文提出的算法分別放在非分布式環境和分布式環境下進行推薦，計算MAE值，最終結果如圖2所示。

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

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

圖3 數據集處理加速比變化

該圖顯示三個不同大小的數據集在Hadoop集群上進行算法處理的加速比變化。這表明，針對同一數據集，增加節點數量可以提高算法效率。這種效率的提升在節點數量少的時候還不明顯，當節點數量多之后，效率的提升效果就會非常明顯。因此基于Hadoop集群的ItemBased推薦算法在大數據規模下擁有良好的可擴展性。

5 結語

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