基于均值預估的協同過濾推薦算法改進

蔣宗禮，王 威，陸 晨

(北京工業大學 計算機學院，北京 100124)

基于均值預估的協同過濾推薦算法改進

蔣宗禮，王 威，陸 晨

(北京工業大學 計算機學院，北京 100124)

在協同過濾推薦系統中，用戶-項目矩陣中存在大量未評分元素，且最終預測值由“最近鄰”用戶所評分數的加權平均產生。傳統算法將未評分元素直接計作0，導致預測得分普遍偏低。針對這種稀疏性引起的問題，提出了一種基于均值預估的協同過濾改進算法。該算法以“最近鄰”用戶所給平均值對未評分的數據進行估計，有效降低了未評分項目所帶來的負面影響。同時該方法又不是單純的平均值填充，而是在協同過濾算法的第三階段，需要用到“最近鄰”用戶對預測項目的評分時，才對“最近鄰”評分為0的分值進行替代，這樣不會影響到計算的相似度，預測結果不至于平庸。稀疏度為93.7%的數據上的實驗表明，在不影響相似度計算的前提下，改進算法可顯著降低均方根誤差，提高推薦質量；最佳RMSE值可達1.01。

協同過濾；推薦算法；稀疏性；評分預測；均方根誤差

0 引 言

隨著互聯網2.0的快速發展，信息過載成為了人們遇到的一個問題，怎樣幫助用戶從海量信息中發現自身感興趣的內容變得至關重要，推薦系統由此應運而生[1]。目前，推薦系統已經有一些方法，包括基于內容的方法、協同過濾方法和混合推薦方法。其中協同過濾方法是推薦系統中最基本的方法[2]，該方法又分為基于用戶的協同過濾(User-based)和基于項目的協同過濾(Item-based)[3-4]。

協同過濾方法通過用戶行為建立興趣模型，根據鄰居集的行為預測當前用戶。因此，在相應的用戶-項目矩陣中用戶評分項目越多，推薦質量就越高，但隨著用戶項目的不斷增多，用戶-項目矩陣就越來越稀疏[5-7]，這對推薦結果的改善提出了較大挑戰。將一個用戶的鄰居用戶中距離該用戶比較近的稱為近鄰用戶，簡稱近鄰，稱最近的K個近鄰為“K近鄰”。

針對上述問題，對協同過濾算法進行了改進。對某個用戶，當出現未評分項的情況時，用該項的最近鄰評分均值進行預測替代，其代價是需要維護一個用戶評分平均值矩陣，而不需要更多地增加算法的時間復雜性。在MovieLens上的實驗結果表明，新算法的計算效能有了很大提高。

1 基本協同過濾推薦算法討論

1.1 評分預測方法

協同過濾算法根據鄰居的行為數據對目標用戶產生評分預測或者推薦列表，算法流程分為三個步驟[8]：

(1)利用用戶的評分數據計算用戶或者項目之間的相似程度；

(2)選定K值，為每個用戶尋找K近鄰用戶；

(3)利用最近鄰的評分數據預測用戶對未知項目的評分。

第三步評分預測產生推薦結果。傳統的評分預測方法主要有三種[9-10]。

以基于用戶的協同過濾為例。對于用戶u，最簡單的方法是直接使用鄰居集合中的K個用戶對未知項目i的平均打分來得到預測值Pu,i，如式(1)所示。

(1)

其中，N(u)為u的K近鄰用戶集合；Rv,i為用戶v對項目i的評分。

該方法是把集合中的鄰居用戶同等對待，雖然簡單，但會降低預測結果的個性化程度。事實上，每個鄰居用戶與目標用戶的相關性是不一樣的，他們對目標用戶的評分影響貢獻也應該是不一樣的。

一種改進方法是把鄰居用戶與目標用戶的相似度作為權值，與鄰居用戶的評分進行加權求和，給出預測用戶對項目i的評分。該方法能反映出不同用戶所做出的貢獻。

一般用式(2)計算相應的Pu,i：

(2)

其中，Sim(u,v)表示用戶u和用戶v的相似度。

式(2)雖然使用了用戶的加權平均值，但沒有考慮不同用戶的評分尺度。進一步的改進是加入不同用戶更多的個性化因素，充分考慮每個用戶的個性評分尺度，以消除個性化所帶來的負面影響，通常具有更好的準確度。具體用式(3)計算。

(3)

1.2 評分預測分析

從上述三種評分預測方法中可以看出，預測用戶評分需要用到最近鄰的評分數據。但由于數據稀疏性，用戶的最近鄰中存在著大量的未評分元素，由于這些未評分項被簡單地置為0，導致了較大誤差積累的連鎖影響，使得最終推薦結果普遍不理想。究其原因，在這個評價體系中，0表示的是用戶對相應的項目不喜歡。事實上，用戶對某個項目沒有評分，是由于用戶對該項目沒有行為，而并不一定是不喜歡。因為至少存在著諸如已經獲得有關信息、還發現了其他相關信息、時間不允許等導致他不評價的原因。而且這種影響會在算法中出現連鎖反映。

例如，簡單考慮這樣的情景：用戶A對項目a，c都打4分，用戶B對項目a打了4分，用戶C對項目b打了3分。預測一下用戶A對項目b的打分情況。

首先，構建用戶-項目評分矩陣，如表1所示。

表1 用戶-項目評分矩陣

然后找到和用戶A相似的鄰居B，通過B對項目b的打分預測用戶A對項目b的打分，最后求得A對b的打分為0。顯然存在：用戶B對項目b打分為0不一定代表用戶B不喜歡項目b，很可能僅僅是他沒有對項目b有過行為。事實上，用戶B很不活躍的可能性很大。所以，這種連鎖反應使得算法未能夠更好地利用K個近鄰的相關性，對相關項目進行估計。

綜上，三種評分預測方案都未能很好地解決用戶鄰居未評分的情況，不能有效地近似用戶對項目的真實評分，導致推薦質量很不理想。一般來說，可以忽略那些未對項目i評分的最近鄰用戶(比如l個，用其余的k-l個最近鄰用戶計算評分[2])。記這種方法為協同過濾的修正算法。在式(2)的基礎上設計如下修正方案：

(4)

其中，Sim(u,v)表示用戶u和用戶v的相似度；NULL表示不考慮未對項目i評分的近鄰用戶影響，實驗中直接忽略，不納入預測值Pu,i的計算。

2 協同過濾推薦算法的改進

針對基本的協同過濾推薦算法在預測評分時不能有效解決近鄰用戶的大量未評分數據這一問題，有兩種解決途徑。第一種是通過機器學習方法做分類，采用隱語義模型和矩陣分解模型進行降維，它需要構造負樣本，這種方案效果很好，但負樣本的采樣一直沒有得到令人滿意的優化解決，計算代價很大，在實際應用中操作性和實時性不高。第二種是填充缺失值，基于領域進行推薦[2,11-13]。文中利用用戶對項目興趣度的相關性，使用用戶本身的平均評分進行預測的方案。該方案不會影響用戶-項目矩陣中的未評分元素，只是在最后預測評分時對未評分的數據進行替代。它的好處是不需要填充原始用戶-項目矩陣，也就不會影響到用戶之間或者項目之間的相似度計算，其代價是需要維護一張用戶評分平均值表。

下面基于用戶的協同過濾對改進算法進行具體討論。這里將協同過濾推薦算法劃分為三個部分：數據表示、最近鄰構建、結果產生。

2.1 數據表示

用戶對項目評分可以用表2所示的矩陣R(m,n)來表示，其中m表示用戶數，n表示項目數，Rv,i表示用戶v對項目i的評分。評分值可以用0、1來表示。Rv,i=1表示用戶v喜歡項目i；Rv,i=0表示用戶v不喜歡項目i；也可以用一個區間來表達一種喜愛程度。例如，MovieLens中用0～5的整數來表明用戶對電影的喜愛程度。以此為基礎，對矩陣中沒有評分的值進行預測。

表2 數據表示

2.2K近鄰形成

在基于用戶的協同過濾算法中關鍵是維護一張用戶相似表，它要求對于某一個用戶u，需要能夠找到他的K近鄰用戶。定義N(u)={u1,u2,…,uk}表示用戶u的近鄰用戶集序列，序列N(u)中的元素ui根據其與用戶u之間的相似程度由大到小排列。相似度的計算方法很多，在基于用戶的相似度計算中一般采用向量模型，即把矩陣中的一行看成是用戶的特征描述，再用向量模型進行相似度計算。

一般地，相似度的度量方法有三種。

(1)余弦相似度。

把用戶對項目的評分組成一個n維向量，并把它看成用戶的特征向量(FeatureVector)，通過計算特征向量之間的夾角余弦來度量兩個用戶之間的相似性，夾角越小說明用戶的相似性越大，如式(5)所示。

(5)

其中，I表示用戶u和v共同的評分項目集合；Ru,i表示用戶u對項目i的評分；Iu和Iv表示用戶u和v已經評過分的項目集合。

(2)皮爾遜系數。

皮爾遜系數更加重視用戶之間的公共評分項目，其核心思想也是余弦定理。

Sim(u,v)=

(6)

(3)修正余弦相似度。

在余弦相似度的計算過程中，無法考慮不同用戶對項目集合評分在尺度上的差異性，有的用戶可能總體評分偏高，有的可能總體評分偏低，在這種情況下會出現喜愛程度一樣，但評分不一樣的狀況。由此，可以利用修正的余弦相似度評價來對上述公式進行優化，如式(7)所示。

Sim(u,v)=

(7)

從式(7)中可以看出，修正余弦與皮爾遜相關系數不同點是后者在分母方面采用的是用戶共同評分集合，而修正余弦則是單方面用戶的評分。

Sarwar利用MovieLens最小數據集對三種方案進行對比，用MAE作為評測指標說明利用修正后的余弦相似度可以獲得最優MAE[3]。文中相似度計算方法均采用修正余弦的度量方法。

把得到的結果存放在相似度表中，記為矩陣S(m,m)，其中S(u,v)表示用戶u和用戶v的相似度。最后根據K值把S(m,m)中用戶u對應行中K個最大相似的元素放入用戶u的K近鄰集合中，構成N(u)。

2.3 評分預測

在得到用戶的K近鄰后，就可以對未知評分進行預測了。采用改進后的算法對三種方案進行改進。

(1)最簡單平均值預測方案改進。

取：

(8)

(2)面向相似性的鄰居評分加權平均數方案改進。

取：

(9)

其中，Sim(u,v)表示用戶u和用戶v的相似度。

(3)基于每個用戶評分尺度的準確評分公式改進。

取：

(10)

從三種改進方案可以看出，它們的核心是用鄰居用戶的平均分對打分為0的項目進行替代。

通過實驗發現，三種方案各有利弊。第一種方案最簡單，它同等看待所有鄰居用戶的貢獻，改進后會使得預測值更加平庸，個性化程度不明顯，推薦效果也最差。后兩種方法中由于已經采用了修正余弦相似度獲得項目的相似度，考慮了不同用戶的評分尺度，所以文中直接采用較簡單的式(2)及其對應的修正式(4)與改進式(9)對結果進行預測，并對比推薦質量。

3 實 驗

3.1 數據集

采用美國明尼蘇達GroupLens研究組提供的MovieLens數據集，MovieLens是一個基于推薦算法研究的Web站點[13]，用來接收用戶對電影的評分和提供電影推薦列表。現在MovieLens數據集總共分為3個不同大小的版本，文中選用小版本的數據集。它包含了943個用戶對1 682部電影的100 000條評分信息，每個用戶至少有20條以上的評分信息，評分取值從1到5代表用戶的喜好程度。

定義稀疏度為用戶未評分條目數占矩陣中所有數據條目的百分比。實驗中稀疏度為：

(11)

將數據集分為訓練集與測試集，為此引入變量x，表示訓練集占數據集的百分比，在實驗中始終使x=0.8，即訓練集占80%，測試集占20%。另外為了保證評測指標并不是過擬合的，共進行了5次實驗，每次實驗都使x=0.8，而訓練集和測試集都重新隨機生成，保證得到不一樣的訓練集與測試集，最后用5次實驗的平均值作為最后的評測指標。

3.2 度量指標

在評分預測中，一般可通過均方根誤差(RMSE)和平均絕對誤差(MAE)來計算預測準確度[14-15]。

(12)

(13)

其中，Ri為算法的預測評分；ri為真實評分。

其中RMSE是Netflix衡量協同過濾算法的評估指標[2,11]。同時比較式(11)和式(12)可知，RMSE加大了對預測不準的用戶項目評分的懲罰(平方懲罰)，因而對推薦算法更加嚴苛。所以文中選用RMSE作為最終的評測指標。

3.3 實驗結果

在MovieLens數據集上離線實驗了兩種協同過濾推薦算法和它們對應的改進算法，并采用不同K值(10,20,30,40,50,80)對比推薦質量。

表3給出了K值為10時的部分實驗結果。

表3 部分實驗數據比較

從中可以發現，采用式(4)的修正算法可以對原始結果進行合理的改進，但效果有限，同時修正方案也存在預測評分為0的情況。而改進算法相比前兩者能夠大幅度地提高預測評分的準確性。

分析式(9)可以推測，使用鄰居用戶平均分進行替代，預測結果的起伏不會很大，所以最終的預測結果大部分集中在2～5。在實際應用中，用戶對項目的打分也是如此，大部分人對自己沒有行為的項目或者不是特別喜歡的項目會保守地以中間值附近的分數進行評分，這種結果符合大眾的評分心理。

綜上所述，改進算法可以更加準確地體現用戶現實的狀態，預測用戶的評分數據，預測結果更加趨近于真實結果，同時也不會過度平庸，仍然能夠反映用戶的個性化打分。最終結果的RMSE值對比由圖1～圖3分別給出。

圖1 協同過濾推薦結果

圖2 協同過濾的修正推薦結果

圖3 協同過濾的改進推薦結果

對比推薦結果可以看出，修正算法能夠提高推薦質量。而經過改進后的算法優于前兩種方法，不管是在基于用戶的協同過濾，還是在基于項目的協同過濾上，都能夠顯著提高推薦質量，得到更小的RMSE值。

3.4 分析與討論

修正算法在評分時忽略了用戶對項目評分為0的情況，可以提高推薦質量。但是，這種方法忽略了部分近鄰用戶，難以更準確地體現用戶喜好。由圖2可知，當K值較小時，RMSE值不理想，同時，預測的用戶評分中仍然存在分數為0的情況(K近鄰用戶都未對該項目打分)，這是不合理的。而文中改進算法可以有效避免修正算法的弊端，RMSE值下降了0.2左右。

在解決稀疏性的問題中，機器學習途徑的核心思想是構造負樣本，通過降維的方法補全評分矩陣，一些著名算法在NetflixPrize上的推薦質量很高。例如，在Funk-SVD模型基礎上加入偏置項后的BiasSVD模型，在參數F取96時，能將RMSE值降到0.903 9。加入時間信息的TimeSVD++模型在參數F取50時，RMSE值為0.882 4[2]。但這類方法的計算復雜度較高，一些模型只能運用在幾百個用戶、幾百個項目的實驗上，在實際運用中實時性很難保證。相比之下，文中提出的改進算法在推薦質量和算法復雜度上都達到了可接受的程度，空間上只需要維護一張用戶評分均值表，比機器學習的方法更加易于操作和實用。

4 結束語

針對協同過濾系統中的數據稀疏問題，在預測評分階段以最近鄰用戶打分的平均值對未評分的數據進行替代，可以有效降低數據稀疏帶來的負面影響，同時又不會影響到用戶間的相似度計算，推薦結果不會過度擬合和過度平庸，能更加真實地反映用戶的喜好程度，并且該方案比機器學習更加易于操作和實用。實驗結果表明，改進算法能夠有效避免傳統評分預測階段的弊端，顯著提高了推薦算法的推薦質量。最終取得了最好的RMSE值(1.01)。

[1]DeshpandeM,KarypisG.Item-basedtop-nrecommendationalgorithms[J].ACMTransactionsonInformationSystems,2004,22(1):143-177.

[2] 項 亮,陳 義,王 益.推薦系統實踐[M].北京:人民郵電出版社,2012.

[3]SarwarB,KarypisG,KonstanJ,etal.Item-basedcollaborativefilteringrecommendationalgorithms[C]//Proceedingsofthe10thinternationalconferenceonworldwideweb.[s.l.]:ACM,2001:285-295.

[4] 蔣宗禮,陸 晨.基于級聯二部圖的動態推薦算法[J].計算機工程與設計,2013,34(12):4356-4361.

[5] 馬宏偉,張光衛,李 鵬.協同過濾推薦算法綜述[J].小型微型計算機系統,2009,30(7):1282-1288.

[6] 許海玲,吳 瀟,李曉東,等.互聯網推薦系統比較研究[J].軟件學報,2009,20(2)：350-362.

[7] 冷亞軍,陸 青,梁昌勇.協同過濾推薦技術綜述[J].模式識別與人工智能,2014,27(8):720-734.

[8]RicciF,ShapiraB.Recommendersystemshandbook[M].[s.l.]:Springer,2011.

[9]ZhongZ,SunY,WangY,etal.Animprovedcollaborativefilteringrecommendationalgorithmnotbasedonitemrating[C]//14thinternationalconferenceoncognitiveinformatics&cognitivecomputing.[s.l.]:IEEE,2015:230-233.

[10] 鄧愛林,朱揚勇,施伯樂.基于項目評分預測的協同過濾推薦算法[J].軟件學報,2003,14(9):1621-1628.

[11]PanR,ZhouY,CaoB,etal.One-classcollaborativefiltering[C]//EighthIEEEinternationalconferenceondatamining.[s.l.]:IEEE,2008:502-511.

[12] 王元濤.Netflix數據集上的協同過濾算法[D].北京:清華大學,2009.

[13]SchaferJB,DanF,HerlockerJ,etal.Collaborativefilteringrecommendersystems[C]//Theadaptiveweb,methodsandstrategiesofwebpersonalization.[s.l.]:[s.n.],2015:45-46.

[14] 朱郁筱,呂琳媛.推薦系統評價指標綜述[J].電子科技大學學報,2012,41(2)：163-175.

[15] 朱揚勇,孫 靖.推薦系統研究進展[J].計算機科學與檢索,2015,9(5):513-525.

Improvement of Collaborative Filtering Recommendation Algorithm with Mean Value Estimation

JIANG Zong-li，WANG Wei，LU Chen

(College of Computer Science and Technology,Beijing University of Technology,Beijing 100124,China)

There are a lot of unrated elements in the user-item matrix in collaborative filtering recommendation system,and final prediction value is calculated by the weighted average of nearest-neighbor scores.The values of unrated elements are regarded as 0 by traditional methods,which results in a generally low prediction score for the unrated elements.In order to solve the problem caused by sparsity,an improved collaborative filtering recommendation algorithm with mean value estimation is proposed.The average score of the nearest-neighbor scores are employed to evaluate the unrated data,effective reduction of negative influence of unrated items in this algorithm.At the same time,this method is not a simple average filling,but in the third stage of collaborative filtering algorithm,when needing to use nearest-neighbor users to predict,the 0 score is replaced.This won’t affect the calculation of similarity,and predicted results not mediocrity.The experiment results with 93.7% sparse degree show that the recommendation quality can be improved and that the best RMSE value,1.01,has been reached.

collaborative filtering;recommendation algorithm;sparsity;rating prediction;RMSE

2016-03-12

2016-06-22 網絡出版時間：2017-03-13

國家級精品資源課程建設(007000523339)

蔣宗禮(1956-)，男，教授，CCF會員，研究方向為網絡信息搜索與處理；王 威(1992-)，男，碩士研究生，研究方向為推薦算法。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170313.1545.002.html

TP301.6

A

1673-629X(2017)05-0001-05

10.3969/j.issn.1673-629X.2017.05.001