基于聯合聚類和C-RA組合相似度的協同過濾算法

趙文濤 王春春 成亞飛

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

?

基于聯合聚類和C-RA組合相似度的協同過濾算法

趙文濤 王春春 成亞飛

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

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

協同過濾 冷啟動 數據稀疏性 聯合聚類 C-RA

0 引 言

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

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

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

1 相關研究

1.1 協同過濾算法

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

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

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

(1)

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

(2)

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

1.2 聯合聚類

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

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

2 基于聯合聚類和組合相似度的協同過濾算法

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

圖1 算法流程圖

2.1 聯合聚類填充

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

(3)

(4)

(5)

(1≤u≤m)

(6)

(1≤i≤n)

(7)

2.2 C-RA組合相似度

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

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

(8)

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

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

(9)

(10)

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

2.3 基于聯合聚類和C-RA組合相似度的推薦

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

算法：

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

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

過程：

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

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

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

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

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

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

3 實驗分析與結果

3.1 數據集

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

(11)

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

3.2 度量標準

(12)

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

(13)

3.3 實驗結果

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

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

圖2 用戶和物品聚類數目的確定

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

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

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

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

圖4 本文算法的RMSE值

4 結 語

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

[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] 吳杰，馮鋒．綜合用戶偏好和優先新品推薦的協同過濾算法[J]．計算機應用與軟件,2014,31(10)：285-287．

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

[5] 項亮．推薦系統實踐[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] 韋素云，靜靜，業寧．基于聯合聚類平滑的協同過濾算法[J]．計算機研究與發展，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] 喻金平，張勇，廖列法，等.基于混合蛙跳聯合聚類的協同過濾算法[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。河南省科技攻關項目(142402210435)；河南省高等學校礦山信息化重點學科開放基金項目(ky2012-02)。趙文濤，教授，主研領域：信息系統，大數據，數據挖掘。王春春，碩士生。成亞飛，碩士生。

TP393

A

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