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

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

0 引言

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

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

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

1 國內(nèi)外現(xiàn)狀及分析

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

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

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

2 協(xié)同過濾推薦算法

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

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

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

表1 用戶-項目評分

(1)

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

(2)

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

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

(3)

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

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

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

(4)

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

(5)

其中NESI表示鄰居集。

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

3 雙維度云模型協(xié)同過濾推薦算法

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

圖1 推薦示意圖

3.1 相關(guān)算法的實現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

3.2 推薦過程的MapReduce處理流程

(1)相似度計算的MapReduce

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

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

(2)預(yù)測評分的MapReduce

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

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

3.3 綜合預(yù)測評分

接收以上得出的兩個預(yù)測評分，動態(tài)確定兩個評分的權(quán)值分配，此處引入近鄰群和信任子群：

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

其中φ為調(diào)和參數(shù)。

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

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

(10)

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

4 實驗及分析

4.1 實驗環(huán)境與數(shù)據(jù)度量標準

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

表2 數(shù)據(jù)集描述

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

(11)

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

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

4.2 集群與單機實驗及對比

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

圖2 加速比實驗圖

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

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

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

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

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

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

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

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

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

5 結(jié)論

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

[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] 張光衛(wèi),李德毅,李鵬,等.基于云模型的協(xié)同過濾推薦算法[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] 范波，程久軍. 用戶間多相似度協(xié)調(diào)過濾推薦算法[J]. 計算機科學,2012,39(1)：23-26.

[7] 榮輝桂,火生旭,胡春華，等. 基于用戶相似度的協(xié)同過濾推薦算法[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] 黃創(chuàng)光，印鑒，汪靜, 等.不確定近鄰的協(xié)調(diào)過濾推薦算法[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] 文俊浩,舒珊. 一種改進相似性度量的協(xié)同過濾推薦算法[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.