基于相似性填充和信任因子的協同過濾算法

王建芳 谷振鵬 劉冉東 劉永利

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

基于相似性填充和信任因子的協同過濾算法

王建芳 谷振鵬 劉冉東 劉永利

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

針對傳統協同過濾算法中用戶交叉評分項較少的情況，提出一種相似度與社交網絡中信任因子結合的新方法。首先利用評分矩陣獲取用戶間相對缺失的評分項。其次通過概率矩陣分解技術進行降維獲得近似評分矩陣，用以動態填充上述缺失項目評分，以填充后的用戶評分計算用戶間相似度。對于部分填充中存在誤差的項目通過信任因子動態調整，獲得更符合實際的相似度。在公開數據集MovieLens的實驗結果顯示，該方法較傳統方法在推薦精度方面提升2.1%以上。

協同過濾 數據稀疏 相似性 填充 信任因子

0 引 言

互聯網由Web1.0時代進入Web2.0時代，用戶逐漸地由信息消費者擴展到信息生產者和消費者。隨著用戶參與信息生產，網絡信息規模呈爆炸式增長。海量信息為信息檢索提供了可能的同時導致了信息過載。為了緩和這種矛盾，幫助用戶在海量數據中準確快速地找到其感興趣的信息，推薦系統應運而生[1]。由于協同過濾能夠處理電影、音樂和商品推薦等難以進行文本描述的項目，因而廣泛應用于電子商務等行業[2]。雖然協同過濾取得顯著優秀性能，但仍面臨許多問題，例如實際應用中數據往往極度稀疏[3]。以電子商務為例，在電子商務系統中用戶購買的商品通常不足網站商品總數的1%。用戶只對極少數商品進行評分。傳統的相似性計算方法僅使用共同評價項目，用戶間具有隱式相似度，但由于沒有共同評分項而無法計算其相似度。

國內外學者提出采用將降維技術來緩解推薦算法中的數據稀疏問題。Sarwar等[4]首先提出采用奇異值分解SVD(Singular Value Decomposition)，以矩陣分解角度實現降維，提取隱因子信息。Salakhutdinov等[5]提出概率矩陣分解PMF(Probabilistic Matrix Factorization)技術，給與SVD概率解釋并加以正則項避免過擬合。臺灣林智仁等[6]提出了支持向量機的研究對降維技術進行改進。降維技術在保留大部分數據信息的情況下減少數據維數，雖然取得一定成果，但不可避免的損失一部分有用信息。為了提高數據利用率，研究人員提出了改進相似性的計算方法[7-10]。Bobadilla等[11]提出利用均值填補缺失信息以充分挖掘用戶特征信息。孫小華等[12]綜合基于SVD的協同過濾算法和基于k近鄰的協同過濾算法兩者的優勢，提出了Pear_Afrer_SVD算法。該算法先使用SVD技術對原始評分矩陣R進行分解。再通過分解矩陣逆向求近似評分矩陣。之后利用填充后的近似評分矩陣進行用戶相似度計算，最后采用k近鄰算法選擇目標用戶的鄰居，并通過鄰居做出推薦預測。

基于上述存在的問題，本文提出了一種基于用戶和相似性填充的協同過濾算法CF-PFCF。該算法通過部分填充評分矩陣，用戶所有的評價行為可以被充分挖掘，同時引入用戶信任因子，能夠有效地衡量每位用戶評價信息的可信性和可靠性，避免用戶的惡意評分行為，從而提高推薦精度。

1 相關工作

經過最近幾年的研究，協同過濾模型已成為個性化推薦系統中應用最廣泛的模型。典型的協同過濾可以分為基于內存的協同過濾和基于模型的協同過濾。基于內存的協同過濾考慮需要用戶對項目的興趣度，該信息通常以評分矩陣的形式表示。

矩陣中每一行ri表示用戶i評價電影的集合，所有用戶集合用U表示；每一列rj表示評價電影j的用戶集合，所有電影集合用V表示。每一個元素ri,j表示用戶i對電影j的評分。傳統的協同過濾算法步驟為計算用戶相似度、由相似度矩陣確定目標用戶鄰居集合，由鄰居集合對目標用戶預測評分三步。

郝立燕等[13]提出用SOFT_IMPUTE算法補全稀疏的評分矩陣結合相似度因子與k近鄰算法做出推薦預測，通過補全的評分矩陣加以信任因子限制得到WCF-SOFT算法。基于填補的相似度計算方法不可避免地會使預測評分參與計算，影響原始用戶特征信息。楊興耀等[14]提出基于信任模型填充的協同過濾推薦模型CFTM，該方法通過分析日常人類行為習慣，利用評分矩陣采樣建立信任模型對用戶相似性進行填充。然而單純信任因子無法充分挖掘用戶特征信息。

基于模型的協同過濾則是通過對原始評分矩陣建模，迭代預測出評分矩陣中的缺失項，可有效解決數據稀疏問題和冷啟動問題。PMF[5,15]是現代推薦系統中基于模型的協同過濾基礎算法之一，核心思想是：假設用戶與電影間的關系可以由少數幾個因素的線性組合決定。用矩陣的角度來描述，評分矩陣R分解為兩個低維矩陣的乘積 ，其中矩陣U為k×n階矩陣，描述用戶的k個屬性，矩陣V為k×m階矩陣，描述電影的k個屬性。根據秩的性質，k不得大于矩陣R的秩。通過分解出的用戶特征矩陣U和電影特征矩陣V，逆向可求得近似評分矩陣。

2 CF-PFCF算法思想

CF-PFCF算法是以用戶歷史評分數據為背景，遵循協同過濾的基礎流程，首先對原始用戶-評分矩陣利用PMF算法得到近似矩陣，該近似矩陣與均值相比更能反映用戶行為，因此作為填充數據。其次針對性的填充用戶間一方評價而另一方缺失評價的項目，計算填充相似度和共同評分相似度，以充分挖掘數據。然后計算用戶信任因子，分別以用戶共同評分下的相似度、用戶的評分次數、用戶評分和被評分項目均值之差來限制填充相似度。通過共同評分相似度和信任因子對填充相似度的共同限制，減弱相似性計算中的由填充帶來的假設性，加權得到最終的調和相似度。以該調和相似度為基礎由k-近鄰算法得到用戶鄰居集。最后進行預測評分。

2.1 動態填充

填充稀疏矩陣的目的是更充分地利用已有評分信息計算用戶之間的相似性，使得用戶相似性計算更加準確。研究者已經提出許多填充評分矩陣缺失值的方法。其中最簡單的填充方法以用戶評分均值[16]、項目評分均值、用戶評分中值、項目評分中值進行對用戶并集中缺失值填充。該填充方法保證原始用戶-評分矩陣的評分項參與運算，但用固定值填充導致被填充用戶的特征被平均化。因此在一定程度上減弱了被填充用戶的數據特征，致使計算相似度準確率不高，甚至降低準確率。

Va⊕b=Va∪b-Va∩b

(1)

表1 評分矩陣

表1表示一個具有4個用戶6個項目的評分矩陣，每行表示用戶對所有項目的評分行為，Null代表該用戶沒有對項目進行評分操作。經式(1)填充方法和PMF方法可得填充邏輯表和近似評分矩陣如表2和表3所示。

表2 填充邏輯矩陣

表3 近似評分矩陣

simfill_pearson(a,b)=

(2)

通過該填充算法，在保證充分利用原始評分矩陣用戶特征信息的前提下避免過度填充，減弱填充算法中的假設性。

2.2 信任因子

雖然填充算法保證用戶間評分信息充分參與計算，但由于原始評分矩陣過于稀疏，即使進行部分填充其相似度假設性依然較強，式(2)計算出的相似度沒有考慮用戶之間的實際關系。因此在進行預測評分時，應考慮到多種因素對相似性的影響，這些因素被稱為信任因子[13]。

1) 基于傳統皮爾遜相似度對其進行加權調整，通過式(1)對用戶間共同評價項進行計算，得出傳統皮爾遜相似度Simpearson，該相似度計算不帶有任何填充項，可反映用戶間真實關系。通過加權調整，可得調和的用戶相似度，如式(3)：

Sim_adj=αSimfill_pearson+(1-α)Simpearson

(3)

(4)

3) 實際中一些用戶喜歡評高分，一些用戶喜歡評低分，甚至存在惡意評分用戶，單純用戶評價等級不能衡量用戶的信任度，需要加以限制。因此引入評價偏差Du，如式(5)：

(5)

其中：Qu為用戶u所評價過的電影集合，du為用戶u評價偏差較小的電影集合。用戶u對電影i的評價如果小于某個參考值則認為用戶u對電影i的評價偏差較小，該用戶的評價無異常。通常這個參考值取電影的評價均值。通過式(6)進行計算：

(6)

如果式(6)成立，則ru,i∈du。設置ε為0.5，實驗顯示ε越小，偏差要求越苛刻，取值過小會使用戶喪失信任。

基于式(2)-式(6)對相似度進行加權調整，得到調和相似度，如式(7)：

Simtr=αSimfill_pearson+(1-α)Simpearson+w1Nu+w2Du

(7)

關于權重值的設定，可用機器學習算法、專家經驗等，本文采用粒子群算法，不斷交叉驗證，最終獲取一組較優的權重值例如(0.7,0.1,0.2)。通過調和相似度，運用k近鄰算法對用戶評分進行預測。

3 CF-PFCF算法描述

結合相似度部分填充和信任因子，提出CF-PFCF算法，具體步驟如下：

算法1CF-PFCF算法

輸入：用戶-評分矩陣R，待預測用戶-評分項集合Rpre，鄰居數k。

算法實現：

步驟2遍歷原始評分矩陣R計算相似度矩陣Simfill_pearson和Simpearson；

repeat

步驟2.1獲得用戶ua和用戶ub各自評價電影集合的交集Va∩b和并集Va∪b；

until遍歷評分矩陣R；

步驟3遍歷評分矩陣R計算信任因子；

repeat

步驟3.1獲取用戶ua和用戶ub共同評分集合，并計算共同評分下的相似度；

步驟3.2統計每位用戶評價電影總數得到用戶評價數目集合num(u)；

步驟3.3統計每位用戶評價過電影序號獲得用戶歷史評價記錄集合userv；

步驟3.4對每部電影求其平均評價值averv；

步驟3.5通過評分矩陣R得到對電影i評價過的用戶集合UI；

until遍歷評分矩陣R；

步驟5由averv和userv通過式(5)、式(6)計算用戶評價偏差Du；

步驟6利用式(7)計算綜合相似度Simtr；

步驟7通過對UI對應Simtr進行降序排序，取前k個用戶作為用戶ua的鄰居集合Uneighbor；

步驟8預測用戶-評分項集合Rpre；

repeat

until遍歷集合Rpre。

4 實驗結果與分析

4.1 數據集與誤差標準

本實驗采用由美國明尼蘇達大學GroupLens實驗組創建并維護的Movielens-100K數據集包含943名用戶對1 682部電影的100 000條評分，評分集為{1,2,3,4,5}，評分越大說明用戶對電影的認可度越高。數據的稀疏度為100 000/(943×1 692) = 93.7%。為進一步驗證本文算法的通用性，本文額外引用了Movielens-1M數據集，該數據集同樣由GroupLens實驗組提供。與Movielens-100K數據集相比，Movielens-1M數據集具有大的數據量，它包含了6 040個用戶對3 706部電影的1 000 209個評分數據，數據的稀疏度為95.5%。實驗將數據集劃分為比例為8∶2的兩個互不相交的訓練集和測試集。

實驗性能有許多評價標準，例如查全率、均方根誤差、查準率等。本文采用平均絕對誤差(MAE)作為度量標準。假設測試集中實際評分分別為{p1，p2，…，pn},算法預測的評分為{q1，q2，…，qn},則MAE定義為：

(8)

MAE值越小，說明算法可行性越強。

4.2 實驗結果與性能比較

為了驗證本文所使用的填充算法對傳統協同過濾算法的改善作用，首先將皮爾遜、余弦、調整余弦相似度算法在Movielens-100K數據下進行對比測試。如圖1所示。

圖1 傳統相似度對比

實驗結果顯示：余弦相似度誤差最大，皮爾遜相似度誤差最小，三種相似度算法隨著鄰居數增多，誤差逐漸減小并收斂。因此本文選擇以皮爾遜相似度為基礎進行實驗。

以皮爾遜相似度為基礎，對評分矩陣進行全PMF填充、部分PMF填充(本文所用填充方法)進行對比，如圖2所示，其中全PMF填充方法為傳統的填充算法，填充效果如表2所示。

圖2 改進相似度對比

基于皮爾遜相似度算法在鄰居數少的情況下填充算法精度提高，部分PMF填充算法在鄰居數為70的情況下精度達到最優。圖1、圖2表明單純PMF填充相似度下精度提升依然不明顯，為此加入原始皮爾遜相似度進行權重調整。

如圖3所示，依上文式(3)進行相似度調和，實驗結果顯示，單純填充相似度和單純的皮爾遜相似度下的計算結果不理想，在基于全PMF填充算法下的權重調整中，權重因子α=0.8時結果最優。而在基于部分PMF填充算法下，權重因子α=0.7時結果最優，且優于全PMF填充算法的調和結果。

圖3 填充權重對比

如圖4所示，以部分PMF填充算法調和參數α=0.7為基礎，結合式(7)，對參數w1和w2進行調參，其中x軸表示參數w1的變化，y軸表示w2的參數變化，z軸表示MAE，有圖可得在參數w1=0.1和w2=0.2時，MAE達到較優。

圖4 調和權重對比

如圖5所示在確定權重因子情況下對不同鄰居數的實驗結果進行對比，以皮爾遜相似度和部分填充PMF相似度預測誤差作對比。實驗顯示在信任因子限制下，預測精度顯著提升并在鄰居數為40時達到最優。

圖5 CF-PFCF算法結果

將本文CF-PFCF算法與郝立燕等[13]提出的WCF-SOFT算法和楊興耀等[14]提出的基于信任模型填充的協同過濾的CFTM算法做比較。在Movielens-100K數據集和Movielens-1M數據集下實驗結果如圖6、圖7所示。通過計算可知本文方法較傳統方法CFTM能提升3.6%推薦精度以上，較WCF-SOFT算法能提升2.1%推薦精度以上。

圖6 基于Movielens-100K的性能比較

圖7 基于Movielens-1M的性能比較

實驗結果可以看出本文算法精度明顯優于WCF-SOFT、CFTM算法。由于CFTM算法主要計算信任因子沒有對相似度進行恰當改進，所以CFTM算法誤差較大，在鄰居數為90時達到最優，鄰居數為100時誤差上升。WCF-SOFT算法穩定性較強，本文算法對WCF-SOFT算法的填充部分進行改進，以部分填充代替全局填充降低填充評分的假設性成分，并加以共同評分相似度和信任因子共同限制。

5 結 語

本文對填充矩陣和信任因子做了研究，在高維稀疏的數據和基于用戶的協同過濾算法的基礎上提出部分相似性填充和信任因子概念。部分填充保證用戶特征充分利用的前提下避免過度填充，解決了高維稀疏評分矩陣用戶間共同評分稀少甚至缺失的問題，并對填充算法的假設性進行限制。盡管算法提高了整體精確度，但由于用戶信任因子的影響，該算法隨著鄰居數增多精確度非單調下降。下一步需要研究如何增強算法穩定性，使誤差隨著鄰居數增加單調遞減并收斂。

[1] Aleksandra,Mirjana,Alexandros.Recommender systems in e-learning environments:a survey of the state-of-the-art and possible extensions[J].Artificial Intelligence Review,2015,44(4):1-34.

[2] Conforti R,Leoni M D,Rosa M L,et al.A recommendation system for predicting risks across multiple business process instances[J].Decision Support Systems,2015,69:1-19.

[3] Jing H,Liang A C,Lin S D,et al.A Transfer Probabilistic Collective Factorization Model to Handle Sparse Data in Collaborative Filtering[C]//IEEE International Conference on Data Mining.IEEE,2015:250-259.

[4] Sarwar B M,Karypis G,Konstan J,et al.Incremental SVD-Based Algorithms for Highly Scaleable Recommender Systems[C]//Conference on Computer and Information Technology,2002.

[5] Salakhutdinov B R,Mnih A.Probabilistic matrix factorization[C]//International Conference on Machine Learning,2012:880-887.

[6] Lee C,Lin C.Large-Scale Linear RankSVM[J].Neural Computation,2014,26(4):781-817.

[7] Lin H,Yang X,Wang W,et al.A Performance Weighted Collaborative Filtering algorithm for personalized radiology education[J].Journal of Biomedical Informatics,2014,51(1):107-113.

[8] Bokde D,Girase S.Matrix Factorization Model in Collaborative Filtering Algorithms:A Survey[J].Procedia Computer Science,2015,49(1):136-146.

[9] Algiriyage N,Jayasena S,Dias G.Web user profiling using hierarchical clustering with improved similarity measure[C]//Moratuwa Engineering Research Conference.IEEE,2015:295-300.

[10] Wu Z,Chen Y,Li T.Personalized recommendation based on the improved similarity and fuzzy clustering[C]//International Conference on Information Science,Electronics and Electrical Engineering.IEEE,2014:1353-1357.

[11] Bobadilla J,Serradilla F.A new collaborative filtering metric that improves the behavior of recommender systems[J].Knowledge-Based Systems,2010,23(6):520-528.

[12] 孫小華,陳洪,孔繁勝.在協同過濾中結合奇異值分解與最近鄰方法[J].計算機應用研究,2006,23(9):206-208.

[13] 郝立燕,王靖.基于填充和相似性信任因子的協同過濾推薦算法[J].計算機應用,2013,33(3):834-837.

[14] 楊興耀,于炯,吐爾根·依布拉音,等.基于信任模型填充的協同過濾推薦模型[J].計算機工程,2015,41(5):6-13.

[15] Yang W F,Wang M,Chen Z.Fast Probabilistic Matrix Factorization for recommender system[C]//IEEE International Conference on Mechatronics and Automation,2014:1889-1894.

[16] Mazumder R,Hastie T,Tibshirani R.Spectral Regularization Algorithms for Learning Large Incomplete Matrices[J].Journal of Machine Learning Research,2010,11(11):2287-2322.

ACOLLABORATIVEFILTERINGRECOMMENDATIONALGORITHMBASEDONSIMILARITYFILLINGANDTRUSTFACTOR

Wang Jianfang Gu Zhenpeng Liu Randong Liu Yongli

(SchoolofComputerScienceandTechnology,HenanPolytechnicUniversity,Jiaozuo454000,Henan,China)

Since there are few users cross rating items in the traditional collaborative filtering algorithm, a new method is proposed to combine the similarity with the trust factor in the social network. First, the rating matrix is adopted to obtain the relative missing rating items between the users. Then, an approximate rating matrix is obtained by probabilistic matrix factorization method to selectively fill the missing rating matrix. Meanwhile, the trust factor is presented to adjust the error in process of calculate similarity. The results on the publicly available MovieLens datasets show that the proposed algorithm can improve the recommendation accuracy by above 2.1% on the classic algorithm.

Collaborative filtering Sparsity Similarity Filling Trust factor

TP391

A

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

2016-12-22。國家自然科學基金項目(61202286)；河南省高等學校青年骨干教師資助項目(2015GGJS-068)；2015年度河南省高等學校重點科研項目(15A520074)。王建芳，副教授，主研領域：數據挖掘，人工智能。谷振鵬，碩士。劉冉東，碩士。劉永利，副教授。