基于聯(lián)合聚類和C-RA組合相似度的協(xié)同過濾算法

趙文濤 王春春 成亞飛

(河南理工大學計算機科學與技術(shù)學院 河南 焦作 454000)

?

基于聯(lián)合聚類和C-RA組合相似度的協(xié)同過濾算法

趙文濤 王春春 成亞飛

(河南理工大學計算機科學與技術(shù)學院 河南 焦作 454000)

針對傳統(tǒng)協(xié)同過濾算法由于數(shù)據(jù)稀疏和冷啟動而造成的推薦精度下降的問題，提出一種基于聯(lián)合聚類和C-RA組合相似度的協(xié)同過濾算法。首先，通過聯(lián)合聚類對原始評分矩陣進行用戶和物品兩個維度的聚類；其次，利用聯(lián)合聚類結(jié)果填充原始評分矩陣；最后，利用C-RA組合相似度計算用戶相似度并進行推薦。實驗結(jié)果表明，該方法有效地提高了推薦結(jié)果的精確度，緩解了數(shù)據(jù)稀疏和冷啟動問題。

協(xié)同過濾 冷啟動 數(shù)據(jù)稀疏性 聯(lián)合聚類 C-RA

0 引 言

推薦系統(tǒng)作為一種軟件工具和技術(shù)方法，通過為用戶過濾無關(guān)信息，以滿足用戶的個性化需求，同時解決了因“信息過載”造成的資源浪費問題。推薦系統(tǒng)現(xiàn)已在新聞、視頻、社交網(wǎng)絡(luò)、電子商務(wù)等領(lǐng)域廣泛應(yīng)用。推薦系統(tǒng)可分為六種不同的推薦方法[1]：基于內(nèi)容的方法、協(xié)同過濾方法、基于人口統(tǒng)計學的方法、基于知識的方法、基于社區(qū)的方法和混合推薦系統(tǒng)。其中，協(xié)同過濾推薦技術(shù)通過用戶對商品的評分或者其他行為模式為用戶提供個性化的推薦，而且不需要了解用戶或者商品的大量信息，因此其被廣泛應(yīng)用。

協(xié)同過濾技術(shù)主要包括基于領(lǐng)域的模型和隱語義模型，其中基于領(lǐng)域的模型由于其簡單、直觀、高效的特點而十分流行。然而協(xié)同過濾技術(shù)在實際運用中存在數(shù)據(jù)稀疏和冷啟動等問題，因此造成推薦誤差較大。針對上述問題，國內(nèi)外的研究者對協(xié)同過濾算法進行了相關(guān)改進。Mobasher B[2]等提出基于用戶的事務(wù)和瀏覽量進行聚類，從而找出用戶共同的特征并有效地提高推薦效果。吳杰等[3]利用奇異值分解將具有相似興趣的用戶分成不同的簇，在簇內(nèi)提取用戶評價過的物品的特征向量，同時運用了神經(jīng)網(wǎng)絡(luò)進行訓練，并最終對較高滿意度的物品進行推薦。

本文的貢獻主要包括三個方面：1) 在原始評分矩陣中對用戶維度和物品維度進行聯(lián)合聚類，利用聯(lián)合聚類預測填充原始評分矩陣，不僅充分利用了用戶與物品之間的聯(lián)系，同時也有效地改善了數(shù)據(jù)稀疏性和冷啟動問題。2) 提出一種新的相似度計算方法C-RA，使RA相似性和修正余弦相似性共同作用于用戶之間的相似度計算上，提高了用戶相似度的準確性，同時彌補了以上兩種相似性各自的缺陷。3)通過聯(lián)合聚類對原始矩陣的填充緩解了原始矩陣數(shù)據(jù)的稀疏性，然后計算用戶的相似度，找出目標用戶的K近鄰來進行推薦。

1 相關(guān)研究

1.1 協(xié)同過濾算法

為了建立推薦信息，推薦系統(tǒng)通常需要把兩種有本質(zhì)區(qū)別的實體(即用戶和物品)聯(lián)系起來，為方便比較這兩種實體產(chǎn)生了兩種主要的協(xié)同過濾技術(shù)：基于鄰域的算法和隱語義模型[4]。其中，基于鄰域的算法重點關(guān)注用戶之間的關(guān)系或者物品之間的關(guān)系。因此，基于鄰域的算法又可分為基于用戶的協(xié)同過濾算法和基于物品的協(xié)同過濾算法[5]。

基于用戶的協(xié)同過濾算法主要包括兩個步驟：

1) 通過用戶之間的相似度計算出和目標用戶u相似的用戶集合。計算用戶之間的相似度方法主要包括三種：皮爾遜相關(guān)相似性、余弦相似性、修正余弦相似性。其中修正余弦相似性具有實現(xiàn)簡單、計算速度快以及考慮到用戶評分尺度的問題等優(yōu)點。修正余弦相似性由式(1)所示：

(1)

2) 找到和目標用戶u相似的用戶集合中用戶所感興趣的，但目標用戶u沒有評價過的物品集合，選擇相似性最高的前N個物品，推薦給目標用戶u。推薦過程由式(2)所示：

(2)

式(2)中Ru,i表示用戶u對未評分物品i的預測評分。Su為用戶u的最近鄰集合。

1.2 聯(lián)合聚類

聚類算法是數(shù)據(jù)挖掘中重要的算法之一，也是無監(jiān)督學習中的典型案例。聚類的基本思想：通過對象之間的相似度，利用分類的方法將對象分成不同的簇或者子集，使同一個子集中的成員對象都有相似的一些屬性。聯(lián)合聚類作為聚類的重要方法之一，在基因表達、協(xié)同過濾以及數(shù)據(jù)文本分析等領(lǐng)域被廣泛使用。

聯(lián)合聚類的基本原理是在數(shù)據(jù)矩陣中通過在行聚類和列聚類兩個維度上進行循環(huán)迭代直至收斂，發(fā)現(xiàn)隱藏在數(shù)據(jù)空間中的簇集。Cheng等[6]首次在基因表達上提出并使用聯(lián)合聚類，提出同時在基因和條件兩維度上進行聚類，并以最小均方殘差作為評價標準。韋素云等[7]提出基于聯(lián)合聚類平滑的協(xié)同過濾學算法，首先使用聯(lián)合聚類對原始矩陣中用戶和物品兩個維度進行評分預測，然后從用戶聚類、物品聚類和聯(lián)合聚類這三方面對空缺項進行平滑填充，最終結(jié)合基于物品的協(xié)同過濾算法進行推薦。

2 基于聯(lián)合聚類和組合相似度的協(xié)同過濾算法

圖1為本文算法的流程圖。本文的算法主要分為兩個步驟：首先，利用聯(lián)合聚類對原始數(shù)據(jù)矩陣進行填充。然后，在填充后的矩陣中利用C-RA計算用戶相似度對未評分項進行預測。通過聯(lián)合聚類填充后的矩陣在預測過程中緩解了由于數(shù)據(jù)稀疏性而造成的推薦質(zhì)量下降等問題。

圖1 算法流程圖

2.1 聯(lián)合聚類填充

傳統(tǒng)的聚類算法中，數(shù)據(jù)矩陣中的某一行或者某一列只能屬于一個類別，然而在實際的推薦過程中，無論是用戶還是物品，同屬于且只屬于一個類別的可能性很小。而聯(lián)合聚類能同時考慮行聚類和列聚類，與傳統(tǒng)的只是基于用戶的聚類或者基于物品的聚類相比，推薦結(jié)果更加精確。為了降低原始矩陣的維度，本文采用矩陣降秩逼近方法。在使用聯(lián)合聚類的基礎(chǔ)上，利用矩陣加權(quán)降秩逼近方法預測原始矩陣中的未評分項[8]。

(3)

(4)

(5)

(1≤u≤m)

(6)

(1≤i≤n)

(7)

2.2 C-RA組合相似度

在計算用戶之間的相似性時，為了使用戶間相似度更加的穩(wěn)定和準確，本文引入節(jié)點相似性指標。節(jié)點相似性指標廣泛應(yīng)用在圖聚類、鏈路預測、個性化推薦等方面。一個好的指標，一定要有相應(yīng)的穩(wěn)定性。Liu等[9]經(jīng)過大量的實驗發(fā)現(xiàn)相似性指標的穩(wěn)定性有很大差異，而RA相似性指標的穩(wěn)定性很好。

本文將RA相似性引入并進行擴展：

(8)

式(8)中，RAuv表示RA相似性方法中用戶u和用戶v的相似度。Γ(u)表示用戶u評分的物品集合，Γ(v)表示用戶v評分的物品集合，f表示用戶u和用戶v共同評分的物品。K(f)表示對f物品進行評分的用戶個數(shù)。

由于利用RA相似性計算出的相似度值并非在[0,1]之間，并且RA相似性只考慮到用戶之間共同評分的物品，而忽略了用戶對物品的評分。同時，修正余弦相似性僅通過用戶之間共同評分的物品集合計算相似度。因此，本文提出一種新的組合相似度衡量指標Su,v，通過利用同趨化函數(shù)(如式(9)所示)對RAu,v和Cu,v同時進行處理，使得Su,v正確反映RA相似性和修正余弦相似性在不同的作用力上的綜合結(jié)果，使組合相似度充分利用RA相似性和修正余弦相似性的優(yōu)勢，更加準確地綜合衡量用戶間的相似度。

(9)

(10)

式(10)中Su,v表示用戶u和v的C-RA相似度。RAu,v表示RA相似性，Cu,v表示修正的余弦相似性。

2.3 基于聯(lián)合聚類和C-RA組合相似度的推薦

通過聯(lián)合聚類將原始評分矩陣進行填充，然后利用C-RA相似度計算用戶之間的相似度，最后利用式(2)預測未評分項的值。本文對于新用戶或者新物品沒有可供參考的評分的情況，通過聯(lián)合聚類各類中的用戶和物品均值，預測新用戶和新物品的評分，緩解了冷啟動問題，最終進行Top N推薦。

算法：

輸入：用戶-物品評分矩陣R、評分標準標識矩陣W、用戶聚類數(shù)目h、物品聚類數(shù)目j、目標用戶u′、待評分物品i′、Top N個數(shù)。

輸出：目標用戶u對待評分物品i的預測評分、Top N推薦集。

過程：

Step1 隨機初始化用戶-物品聯(lián)合聚類(μ,λ)；

Step2 計算聯(lián)合聚類中各類的均值RCOC、用戶聚類中各類的均值RCC、物品聚類中各類的均值RDC；

Step3 利用式(6)更新用戶聚類，利用式(7)更新物品聚類；

Step6 根據(jù)式(10)計算用戶之間的相似度；

Step7 找到用戶u′的最近鄰居集Nu′；

Step8 通過最近鄰居集和式(2)計算出目標用戶u′對物品i的評分，產(chǎn)生Top N推薦。

3 實驗分析與結(jié)果

3.1 數(shù)據(jù)集

本文所采用的MovieLens數(shù)據(jù)集源于美國明尼蘇達大學的GroupLens項目組創(chuàng)辦的MovieLens推薦系統(tǒng)。本文使用的MovieLens數(shù)據(jù)集包含943位用戶對1 682部電影的評分信息。評分總數(shù)為100 000。評分標準為1～5分，某用戶對某部電影所打的分值越高，表明該用戶對該部電影越感興趣。利用數(shù)據(jù)稀疏度公式可計算出該數(shù)據(jù)集的稀疏度。

(11)

式中S表示數(shù)據(jù)稀疏度，m表示用戶數(shù)，n表示物品數(shù)，N為總的評分數(shù)。計算得出MovieLens數(shù)據(jù)集的稀疏度為：93.69%。

3.2 度量標準

(12)

平均絕對誤差(MAE)也常被用來度量預測評分的準確性。當RMSE和MAE的值越小，說明預測的準確度越高。

(13)

3.3 實驗結(jié)果

本文采用五折交叉驗證的方法。將數(shù)據(jù)集隨機分成五份，每次選取其中的4份作為訓練集，剩余的一份作為測試集。通過五次實驗后，計算五次實驗結(jié)果的平均值作為最終的實驗結(jié)果。在交叉驗證之前，需要確定聯(lián)合聚類中用戶聚類的個數(shù)和物品聚類的個數(shù)，聚類個數(shù)的選取對算法最終的性能有直接的影響。

如圖2所示，當最近鄰居的值分別取10、30、50，將用戶和物品的聚類個數(shù)同時設(shè)為5、6、7、8、9、10時MAE值的變化趨勢。隨著用戶與物品聚類個數(shù)的增加，MAE值也在不斷變化，由于聯(lián)合聚類算法對于聚類結(jié)果中每一類元素的個數(shù)存在隨機性。因此，如果選擇較大的聚類個數(shù)或者較高的最近鄰居數(shù)，都可能會出現(xiàn)最近鄰的個數(shù)比類內(nèi)元素總個數(shù)還要多的情況。經(jīng)實驗證明：當用戶和物品的聚類個數(shù)為5時，MAE值達到最優(yōu)，并且在合理范圍之內(nèi)。

圖2 用戶和物品聚類數(shù)目的確定

將本文算法與傳統(tǒng)的協(xié)同過濾算法、文獻[10]的算法作對比。本文中的用戶和物品聚類個數(shù)為5，將最近鄰居個數(shù)從10遞增至60，每次增加10，實驗結(jié)果如圖3所示。

圖3 不同算法的MAE值的比較

從圖3可以看出，本文算法與傳統(tǒng)的協(xié)同過濾算法和文獻[10]中的算法在最優(yōu)情況下對比，MAE值明顯較小，說明本文的算法推薦效果更好。隨著最近鄰個數(shù)的增加，在傳統(tǒng)算法和文獻[10]算法中，MAE值越來越小，而在本文的算法中，通過C-RA相似度能夠更加準確衡量用戶之間的相似性，使確定的最近鄰更加相似。所以，剛開始呈現(xiàn)出較大幅度的增長。隨著最近鄰個數(shù)的增長，鄰居之間相似度變化幅度更大，導致算法推薦性能的提高逐漸變緩。隨著最近鄰個數(shù)的增加，MAE值逐漸增長，且MAE值均比前兩種算法小。

如圖4所示，當用戶和物品的聚類個數(shù)同時為5時，本文算法的RMSE值在最近鄰個數(shù)為10的時候取得最小值，表示更加接近真實值，具有較好的推薦結(jié)果。而在最近鄰個數(shù)為20的時候取得最大值，使預測值和真實值之間出現(xiàn)更大的偏差。產(chǎn)生這種現(xiàn)象的原因可能是聯(lián)合聚類的隨機性導致最近鄰個數(shù)超過了某個類中元素個數(shù)或者由于實驗中較大誤差樣本值的影響導致RMSE值比較大。

圖4 本文算法的RMSE值

4 結(jié) 語

本文提出一種基于聯(lián)合聚類和C-RA組合相似度的協(xié)同過濾算法。通過聯(lián)合聚類對原始評分矩陣進行填充，有效地解決了數(shù)據(jù)稀疏和冷啟動問題。并提出一種新的相似度計算方法，即C-RA組合相似度更加精確地計算用戶之間的相似度，同時也提高了推薦質(zhì)量。本文中聯(lián)合聚類的個數(shù)是通過大量實驗驗證所得，如何快速精確地劃分聚類將是下一步的研究工作重點。

[1] Burke R. Hybrid Web Recommender Systems[C]//The Adaptive Web: Methods and Strategies of Web Personalization, Lecture Notes in Computer Science，2007:377-408.

[2] Mobasher B, Dai H, Luo T, et al. Discovery of Aggregate Usage Profiles for Web Personalization[C]//Proceedings of the WebKDD Workshop at the ACM SIGKDD,Boston,August 2000.

[3] 吳杰，馮鋒．綜合用戶偏好和優(yōu)先新品推薦的協(xié)同過濾算法[J]．計算機應(yīng)用與軟件,2014,31(10)：285-287．

[4] 弗朗西斯科·里奇. 推薦系統(tǒng):技術(shù)、評估及高效算法[M]. 機械工業(yè)出版社, 2015．

[5] 項亮．推薦系統(tǒng)實踐[M]．北京：人民郵電出版社，2012：44-45．

[6] Cheng Y,Church G M. Biclustering of expression data[C]//Proc of the 8th Int Conf on Intelligent Systems for Molecular Biology.Menlo Park,CA:AAAI,2000:93-103.

[7] 韋素云，靜靜，業(yè)寧．基于聯(lián)合聚類平滑的協(xié)同過濾算法[J]．計算機研究與發(fā)展，2013(50)：163-169．

[8] George T, Merugu S. A scalable collaborative filtering framework based on co-clustering[C]//IEEE International Conference on Data Mining. IEEE Xplore,2005:625-628．

[9] Liu J G, Lei H, Xue P, et al. Stability of similarity measurements for bipartite networks[J].Scientific Reports, 2015, 6:18653.

[10] 喻金平，張勇，廖列法，等.基于混合蛙跳聯(lián)合聚類的協(xié)同過濾算法[J]．微電子學與計算機，2016，1(33)：65-71．

COLLABORATIVE FILTERING ALGORITHM BASED ON CO-CLUSTERING AND C-RA COMBINED SIMILARITY

Zhao Wentao Wang Chunchun Cheng Yafei

(CollegeofComputerScienceandTechnology,HenanPolytechnicUniversity,Jiaozuo454000,Henan，China)

In order to overcome the sparse data and cold start of traditional collaborative filtering recommendation algorithm, a collaborative filtering algorithm based on co-clustering and C-RA combined similarity is proposed. First, co-clustering algorithm is used to simultaneously obtain user and item neighborhoods. Secondly, the result of co-clustering is used on rating matrix. Finally, C-RA combined similarity is used to calculate the similarity of users and recommend. Experimental results show that the proposed method not only effectively improves the accuracy of the recommended results, but also solves problems of user cold start and data sparsity.

Collaborative filtering Cold start Data sparsity Co-clustering C-RA

2016-08-14。河南省科技攻關(guān)項目(142402210435)；河南省高等學校礦山信息化重點學科開放基金項目(ky2012-02)。趙文濤，教授，主研領(lǐng)域：信息系統(tǒng)，大數(shù)據(jù)，數(shù)據(jù)挖掘。王春春，碩士生。成亞飛，碩士生。

TP393

A

10.3969/j.issn.1000-386x.2017.07.047