基于雙維度云模型的協同過濾推薦算法

劉美博，滿君豐，彭 成，劉 鳴

(湖南工業大學 計算機與通信學院 湖南 株洲 412000)

0 引言

網絡的迅速普及和通信方式的多樣化給人們帶來了極大的便利，同時也造成了信息量的急劇增加。如何從大量信息中篩選出人們需要的信息就需要用到推薦系統。當前，推薦系統受到了廣泛關注，而找到更好的推薦算法并合理應用一直是研究熱點。

現有的推薦算法中，主流應用的推薦算法就是協同過濾推薦算法。傳統的推薦算法在數據比較稀疏時，不能很好的進行相似度計算，導致推薦系統質量較低。同時新用戶引進時，由于數據量比較少，造成不能得到很好的推薦，這就是冷啟動問題[1]。

本文針對上述問題，基于前人的研究成果，提出一種雙維度的協同過濾推薦算法。該算法是基于Hadoop分布式平臺來實現的，充分發揮了Hadoop集群的優勢。并且該算法選取用戶和項目兩個維度的數據展開研究，采用基于云模型的相似度計算方法[2]計算出用戶相似度和項目相似度，然后通過動態度量方法計算出權值，再根據得到的相似度和權值求得用戶對項目的評分預測值。通過實驗，我們發現該算法對于以上問題得到了一定的解決。

1 國內外現狀及分析

國內外學者針對上面提到的問題進行了一定的改進。文獻[3]提出了一種將聚類算法與SVD算法相結合的新方法，通過使用他們的屬性來對用戶進行分類。然后用SVD算法分解評級矩陣，并將它們重新聯合到新的評級矩陣中，以計算每對用戶之間的相似性。該方法不僅可以改善“冷啟動”和“數據稀疏”問題，還可以提高系統的效率和可擴展性。文獻[4]在[0,1]范圍內基于評級矩陣分解為兩個非負矩陣的分量，通過這個分解可以準確地預測用戶的評級，找出相似的用戶組。文獻[3-4]都是通過矩陣分解來解決傳統推薦算法的數據稀疏問題，但該方法還存在不足，通過矩陣分解降維會導致數據失真，之后計算出來的相似性誤差較大，導致推薦系統準確性降低。

文獻[5]提出了一種基于用戶偏好聚類的新型有效協同過濾推薦算法，引入了用戶組以區分具有不同偏好的用戶。通過考慮活動用戶的偏好，從相應的用戶組獲得最近的鄰居集合。分別考慮本地和全局透視中的用戶偏好，以優選地計算用戶之間的相似性。文獻[6]中主要是通過計算用戶間對不同類型項目的評分相似度，并通過這多個相似度更加精確地得出最終的預測評分。文獻[7]中主要通過計算用戶間的屬性相似度和互動相似度，再結合動態權值分配計算綜合的用戶相似度。文獻[5-7]都是屬于基于用戶這一分支的算法，都采用的是用戶—項目評分矩陣。在推薦精度方面做了很多研究，使得推薦系統精確度得到大大提高，但擴展性問題和稀疏性問題還是存在。文獻[8]通過使用多個相似性度量來計算項目之間的相似性，然后使用這些相似性值來預測用戶的評級,并提出了一種基于項目的CF算法的MapReduce優化。該文獻很好地解決了擴展性問題，同時在效率方面也有顯著提高，但數據稀疏問題還是考慮得不全面。

文獻[9]運用了兩維度的數據，再根據兩個維度的評分矩陣進行相似度計算。該算法充分考慮了兩個維度的數據，并引入了不確定近鄰因子的概念，很好地解決了數據稀疏問題，推薦精度也得到了提高。但該算法對于擴展性問題還是沒有很好地解決，處理稀疏數據方面也能得到改進。而本文在此基礎上，在相似度計算時運用云模型，然后通過Hadoop平臺來處理大數據問題。這使得處理數據稀疏的能力得到了進一步的提高，同時對于擴展性問題也提出了解決方案。

2 協同過濾推薦算法

協同過濾推薦算法其基本思想是“物以類聚，人以群分”，依據相似性而產生推薦[10-11]。

要想運用協同過濾推薦算法，其數據必須是一個矩陣形式，如表1所示，其中U是用戶，I是項目，Rmn表示用戶集中的用戶m對項目集中的項目n的評分。

該算法的核心就是尋找最近鄰居，要想找到鄰居必需計算相似性，常用的度量相似性的方法有以下三種[12]。

表1 用戶-項目評分

(1)

(2)修正的余弦相似性：在余弦相似性基礎上，考慮不同用戶評分尺度不同的問題，把余弦相似性中的向量減去平均評分向量[8]如式(2)所示：

(2)

式中，Ri,d為用戶i對項目d的評分；Ri為用戶i對項目的平均評分；Rj為用戶j對項目的平均評分；Iij為用戶i與用戶j都評分過的項目。

(3)相關相似性：計算Pearson相關系數來進行度量如式(3)所示：

(3)

以上三種方法為常用的相似性度量方法，而本文采用的是云模型相似性度量方法。

(4)云模型相似性：先根據評分矩陣統計得出用戶或項目的評分頻度向量Ui=(u1,u2,u3,u4,u5)(1≤i≤m),再通過逆向云算法計算特征向量如下：

特征向量Vi=(Exi,Eni,Eei)，Vj=(Exj,Enj,Eej)。

(4)

通過上述方法計算出相似用戶后，再根據公式(5)計算來產生推薦。

(5)

其中NESI表示鄰居集。

算出預測評分后，再把評分值進行排序，然后再根據TOP-N算法做出推薦[13]。

3 雙維度云模型協同過濾推薦算法

本文主要選取了基于項目云模型相似度和基于用戶云模型相似度來綜合得出最終預測評分，下面給出具體推薦示意圖，如圖1所示。

圖1 推薦示意圖

3.1 相關算法的實現

算法1 基于項目云模型相似度計算

輸入：項目集合I、用戶集合U、評分矩陣RU×I

輸出：項目間的相似度矩陣SIMI×I

第1步：遍歷項目集合I對矩陣RU×I中未評分的項目添加為0分；

第2步：統計項目的評分頻度向量Iu=(i1,i2,i3,i4,i5)，再通過逆向云算法計算特征向量；

第3步：參照公式(4)計算兩項目間相似度sim(ix，iy)。

算法2 基于用戶云模型相似度計算

輸入：項目集合I、用戶集合U、評分矩陣RU×I

輸出：用戶間的相似度矩陣SIMU×U

第1步：遍歷用戶集合U對矩陣RU×I中未評分的項目添加為0分；

第2步：統計用戶評分頻度向量Ui=(u1,u2,u3,u4,u5)，再通過逆向云算法計算特征向量；

第3步：根據公示(4)計算用戶ux與uy的相似度sim(ux,uy)。

3.2 推薦過程的MapReduce處理流程

(1)相似度計算的MapReduce

Map階段：接收評分矩陣后，對每個評分數據進行提取，①基于項目這一維度以項目對(ix,iy)作為key值，項目對應的評分對(Sx,Sy)作為value值輸出。②基于用戶這一維度以用戶對(ux,uy)作為key值，用戶對應的評分對(Sx,Sy)作為value值輸出

Reduce階段：接收Map階段的數據，① 基于項目這一維度根據算法1計算項目間的相似度；②基于用戶這一維度根據算法2計算用戶間的相似度；③將結果保存輸出。

(2)預測評分的MapReduce

Map階段：根據相似度的值，①基于項目這一維度得出每個項目相似度最高的N個項目定義為鄰居，以項目為key值，項目鄰居為value值輸出。②基于用戶這一維度得出每個用戶相似度最高的N個項目定義為鄰居，以用戶為key值，用戶鄰居為value值輸出。

Reduce階段：接收Map階段的數據，根據算法2計算出兩個維度目標用戶對未評分項目的預測評分。

3.3 綜合預測評分

接收以上得出的兩個預測評分，動態確定兩個評分的權值分配，此處引入近鄰群和信任子群：

S(Ua)={Ux|Sim′(Ua,Ux)>μ,a≠x}

(6)

S(Ij)={Ix|Sim′(Ij,Iy)>ν,j≠y}

(7)

近鄰群大小|S(Ua)|=m；|S(Ij)|=n。

S′(Ua)={Ux|Sim′(Ua,Ux)>μ&|IUa∩IUx|>ε,a≠x}

(8)

S′(Ij)={Iy|Sim′(Ij,Iy)>ν&|UIj∩UIy|>δ,j≠y}

(9)

信任子群大小|S′(Ua)|=m′；|S′(Ij)|=n′；其中μ，v，ε，δ為閾值。

如果(m′+n′)>0，則

如果(m+n)>0，則

其他，a=1-a=0.5

其中φ為調和參數。

根據公式(10)計算目標用戶對未評分項目的綜合預測評分，然后通過對評分排列，將最終的結果推薦給目標用戶。

Pay=(1-a)*P1ay+a*P2ay

(10)

式中，a為評分的權值；P1ay為基于項目相似度的目標用戶對未評分項目的預測評分；P2ay為基于云模型用戶相似度的目標用戶對未評分項目的預測評分。

4 實驗及分析

4.1 實驗環境與數據度量標準

用7臺普通的PC搭建Hadoop組成集群，命名為master、slave1～slave6。以Grouplens網站下載的數據MovieLens 100 K、MovieLens 1 M、MovieLens 10 M為例，如表2所示。

表2 數據集描述

對數據MovieLens 100 K的評分矩陣進行隨機劃分，訓練集與測試集比例為4∶1。進行5次隨機劃分，得到5組數據dataset1～dataset5。采用平均絕對偏差(MAE)作為推薦的度量標準[14]，MAE的大小與推薦質量成反比關系。假設預測的評分集為{P1，P2…Pn}，對應的實際評分集{r1，r2…rn}。

(11)

采用加速比表示處理海量數據時集群節點數對性能方面的影響。加速比定義：K=T1/Tn。

T1表示單節點運行耗費的時長，Tn表示n個節點運行耗費的時長。

4.2 集群與單機實驗及對比

將節點數量分別啟動1～7臺TaskTracker節點，構成不同規模的分布式集群，測試該算法在Hadoop平臺下時效性方面是否顯著提升。實驗主要分析兩個方面：(1)算法在海量數據時集群的節點數對性能的影響；(2)同一數據集下，算法在單機環境與集群環境的時效對比。加速比實驗圖如圖2所示。

圖2 加速比實驗圖

從圖2可看出，當集群節點數從1加到5時，加速比幾乎呈線性增長，節點5以后增速下降。說明節點增加確實能提高推薦算法效率，但是理論上增加一個節點提升1倍效率，在實際上很難達到。

單機與Hadoop集群性能對比如表3所示。從表3可看出：(1)數據集的遞增，單機環境下CPU和內存消耗迅速，無法滿足計算所需資源導致性能降低；(2)數據集較小時，單機用時比集群少，效率比集群高，主要由于Hadoop集群創建、啟動作業都要耗時，各節點通信也需要耗時，實際計算用時占比很??；(3)隨數據集增大，集群在時效方面比單機有明顯提升，運行速度明顯加快，并且數據集太大單機會出現溢出現象，集群仍然能高效的計算。

表3 單機與Hadoop集群性能對比

4.3 與其他推薦算法的對比實驗

下面主要對基于雙維度云模型的協同過濾推薦算法(DCCF)、基于用戶的協同過濾推薦算法(UBCF)、基于項目的協同過濾推薦算法(IBCF)和不確定近鄰的協調過濾推薦算法(UNCF)[10]四種算法進行實驗比較，得到各個階段的數據。選取數據MovieLens 100 K的評分矩陣，分別用100、500、900個用戶進行實驗。

圖3、圖4和圖5為不同用戶數時的MAE值，對比可見，DCCF算法取得了最低的MAE值，明顯提高了推薦準確度，通過云模型數據稀疏問題也得到了合理解決。且用戶數越多，該方法的優勢越明顯，推薦質量越高；同時鄰居集越大，從而使推薦質量增加。

圖3 各種協同過濾推薦算法與DCCF算法的比較(100個用戶)

圖4 各種協同過濾推薦算法與DCCF算法的比較(400個用戶)

圖5 各種協同過濾推薦算法與DCCF算法的比較(900個用戶)

5 結論

針對越來越龐大的網絡資源和以往推薦算法存在的不足，本文提出了一種基于雙維度云模型的協同過濾推薦算法(DCCF)。該算法充分利用了Hadoop集群的優勢，有效結合了云模型，并且通過動態確定權重，使得目標用戶對目標項目的預測評分更加精確。實驗數據表明，該算法能適應大數據環境，并由于利用了云模型和兩個維度數據，數據稀疏性問題得到了合理的解決，推薦質量也上升了一個檔次。而隨著時間的變化，人們的興趣也會發生改變，如何來衡量變化對推薦質量的影響，是下階段的研究重點。

[1] BOBADILLA J,ORTEGA F, HERNANDO A,et al. A collaborative filtering approach to mitigate the new user cold start problem[J]. Knowledge-Based Systems,2012,26:225-238.

[2] 張光衛,李德毅,李鵬,等.基于云模型的協同過濾推薦算法[J]. 軟件學報,2007,18(10)：2403-2411.

[3] BA Q,LI X,BAI Z. Clustering collaborative filtering recommendation system based on SVD algorithm[C]// IEEE International Conference on Software Engineering and Service Science. IEEE,2013:963-967.

[4] HEMANDO A, BOBADILLA J, ORTEGA F.A non negative matrix factorization for collaborative filtering recommender systems based on a Bayesian probabilistic model[J]. Knowledge-Based Systems, 2016, 97(C): 188-202.

[5] ZHANG J,LIN Y,LIN M,et al. An effective collaborative filtering algorithm based on user preference clustering[J]. Applied Intelligence,2016,45(2):230-240.

[6] 范波，程久軍. 用戶間多相似度協調過濾推薦算法[J]. 計算機科學,2012,39(1)：23-26.

[7] 榮輝桂,火生旭,胡春華，等. 基于用戶相似度的協同過濾推薦算法[J]. 通信學報,2014,35(2)：16-24.

[8] Li Chenyang, He Kejing. CBMR: an optimized MapReduce for item-based collaborative filtering recommendation algorithm with empirical analysis[J]. Concurrency and Computation: Practice and Experience,2017.

[9] 黃創光，印鑒，汪靜, 等.不確定近鄰的協調過濾推薦算法[J].計算機學報,2010,33(8)：1369-1377.

[10] YAZDANFAR N, THOMO A. Link Recommender: collaborative-filtering for recommending URLs to twitter users[J].Procedia Computer Science,2013,19:412-419.

[11] PARK Y, PARK S,JUNG W, et al. Reversed CF: a fast collaborative filtering algorithm using a k -nearest neighbor graph[J]. Expert Systems with Applications,2015,42(8):4022-4028.

[12] 文俊浩,舒珊. 一種改進相似性度量的協同過濾推薦算法[J]. 計算機科學,2014, 41(5):68-71.

[13] KUMAR N P,FAN Z.Hybrid user-Item based collaborative filtering[J].Procedia Computer Science,2015, 60(1):1453-1461.

[14] DAS J, AMAN A K, GUPTA P, et al. Scalable hierarchical collaborative filtering using BSP trees[C]// International Conference on Computational Advancement in Communication Circuits and Systems, 2015:269-278.