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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

表1 用戶-項(xiàng)目評分

(1)

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

(2)

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

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

(3)

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

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

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

(4)

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

(5)

其中NESI表示鄰居集。

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

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

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

圖1 推薦示意圖

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

算法1 基于項(xiàng)目云模型相似度計(jì)算

輸入：項(xiàng)目集合I、用戶集合U、評分矩陣RU×I

輸出：項(xiàng)目間的相似度矩陣SIMI×I

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

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

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

算法2 基于用戶云模型相似度計(jì)算

輸入：項(xiàng)目集合I、用戶集合U、評分矩陣RU×I

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

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

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

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

3.2 推薦過程的MapReduce處理流程

(1)相似度計(jì)算的MapReduce

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

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

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

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

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

3.3 綜合預(yù)測評分

接收以上得出的兩個(gè)預(yù)測評分，動(dòng)態(tài)確定兩個(gè)評分的權(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)計(jì)算目標(biāo)用戶對未評分項(xiàng)目的綜合預(yù)測評分，然后通過對評分排列，將最終的結(jié)果推薦給目標(biāo)用戶。

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

(10)

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

4 實(shí)驗(yàn)及分析

4.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)度量標(biāo)準(zhǔn)

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

(11)

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

T1表示單節(jié)點(diǎn)運(yùn)行耗費(fèi)的時(shí)長，Tn表示n個(gè)節(jié)點(diǎn)運(yùn)行耗費(fèi)的時(shí)長。

4.2 集群與單機(jī)實(shí)驗(yàn)及對比

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

圖2 加速比實(shí)驗(yàn)圖

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

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

表3 單機(jī)與Hadoop集群性能對比

4.3 與其他推薦算法的對比實(shí)驗(yàn)

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

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

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

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

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

5 結(jié)論

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

[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]. 軟件學(xué)報(bào),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]. 計(jì)算機(jī)科學(xué),2012,39(1)：23-26.

[7] 榮輝桂,火生旭,胡春華，等. 基于用戶相似度的協(xié)同過濾推薦算法[J]. 通信學(xué)報(bào),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].計(jì)算機(jī)學(xué)報(bào),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ìn)相似性度量的協(xié)同過濾推薦算法[J]. 計(jì)算機(jī)科學(xué),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.