基于改進用戶相似性度量和評分預測的協同過濾推薦算法

李昆侖，萬品哲，張德智

(河北大學 電子信息工程學院，河北 保定 071000)

1 引 言

隨著互聯網經濟的產生和發展，網絡上的信息量呈爆發式增長.為了讓信息消費者方便的從海量信息中找到自己真正有用的信息，同時使信息生產者及時的將自己的信息展現給目標用戶，大量的學者進行了相關的學習和研究，因此，就有了個性化推薦系統[1]的產生和發展.

推薦算法包含基于內容的推薦[2]、基于關聯規則的推薦[3，4]、基于協同過濾的推薦[5，6]、基于知識的推薦[7]等等.其中基于協同過濾的推薦是最主流的推薦算法之一，它同時也面臨著各種問題和挑戰，例如數據稀疏性問題、新加入用戶冷啟動問題[8]、可擴展性問題等等.

基于用戶的協同過濾推薦算法基于一種假設，如果兩個用戶的興趣愛好比較相似，那么其中一個用戶可能會對另一個用戶感興趣的東西也感興趣.協同過濾推薦算法在用戶建模時候嚴重依賴于用戶的歷史評分數據，而評分數據往往具有很高的稀疏性，這就給我們建立準確的用戶模型帶來了很大的挑戰.目前針對數據集稀疏性問題的優化方案可以分為三大類，第一類是將其它因素引入到相似度的計算中，從而減少單純利用稀疏的評分數據對相似度計算的影響；第二類是將含有缺失值的評分矩陣按照某種方式進行填充，從而減少數據集的稀疏度；第三種就是引入聚類算法[9-11]，此類方法一般是通過計算目標用戶與質心的距離，最后確定目標用戶所在的簇，初步的得到目標用戶的近鄰用戶集.

針對評分數據稀疏性問題，傳統的解決方案是將項目評分進行均值填充或者缺失值補零，這必然給預測結果帶來很大的誤差.針對這種問題，文獻[12]提出了將用戶評論信息轉化為特征矩陣，最后結合特征矩陣和評分矩陣計算出來的相似度得出目標用戶的綜合相似度.文獻[13]中提到綜合考慮用戶評分相似性和用戶評論特點的相似性，然后通過權值來控制兩者的重要程度.它們都有一個共同點，都是靠引入另一種因素來減少相似度對稀疏數據的依賴程度從而達到提高相似度計算準確性的目的.這種算法的優點是能夠很好的降低因數據稀疏性導致的計算近鄰用戶不準確的問題，缺點是增加了算法的復雜度，因此，文獻[14]提出了用均值對缺失值進行填充的方法，這雖然能在一定程度上緩解數據稀疏帶來的問題，但是對于過于稀疏的數據集效果卻并不理想.

另一方面，可擴展性也是衡量推薦系統性能一個非常重要的指標.目前，互聯網上每天都有成千上萬的用戶和商品出現，而推薦系統依然能夠實時快速的為每個用戶提供個性化服務，這是因為算法具有很好的可擴展性[15].協同過濾推薦算法中，在尋找近鄰用戶時往往會遇到高維向量的計算問題，這將占用系統大量的時間，因此，如果能夠實現對高維的評分矩陣進行降維，將大大的增加算法的可擴展性.針對高維數據的處理問題，文獻[16]提出了將PCA主成分分析引入推薦系統，實現數據維數縮減，減少了系統的時間損耗.

針對數據稀疏性問題和可擴展性問題，本文提出了一種新的填充和降維方式，同時將用戶評分的均值差引入對相似度的計算并且將用戶評分的均值引入對目標項目的評分預測，從而大大減少了因用戶評分尺度不同導致的推薦結果不準確的問題.從4.3節中的實驗結果顯示改進后的方法相比于傳統的方法推薦準確度有了較大的提高.

2 傳統的基于用戶的協同過濾推薦算法

傳統的基于用戶的協同過濾推薦算法的關鍵是準確的得出目標用戶的近鄰用戶集.尋找的近鄰用戶集是否準確會影響到推薦系統的推薦精度，推薦系統的推薦精度直接決定了用戶對推薦系統的認可程度和依附程度.傳統的基于用戶的協同過濾推薦算法可以分成以下三步：

Step1.獲取到用戶對項目的評分數據，并把它轉化為m行n列的用戶-項目評分矩陣，記為：Rm，n；

Step2.根據第一步確定的評分矩陣，計算每個用戶與其他所有用戶之間的相似度，得到用戶相似度矩陣，最后按照相似度從高到低確定目標用戶的近鄰用戶集Nu；

Step3.使用近鄰用戶集中的用戶評分對目標項目i進行評分預測.

u，i分別表示目標用戶和待預測項目，則預測評分pu，i用公式表示如下：

(1)

對傳統的協同過濾推薦算法而言，相似度計算結果直接影響著近鄰用戶集尋找的結果，因此，對相似度計算方法的改進也是推薦系統研究熱點之一.下面本文將對常見的相似性度量方法進行一些簡單介紹.

2.1 常用相似性度量方法

2.1.1 余弦相似度

通過兩個向量的夾角余弦值[17]sim(u，v)的大小來衡量用戶u、v之間的相似程度，sim(u，v)滿足：-1≤sim(u，v)≤1，且sim(u，v)越大則表明兩個用戶越相似，sim(u，v)用公式表示如下：

(2)

2.1.2 修正余弦相似度

(3)

2.1.3 基于Pearson相關系數的相似度

(4)

2.1.4 基于歐幾里德距離的相似度

歐幾里德距離[19]也稱歐式距離，當采用歐式距離度量相似度時候，其表達式如公式(5)所示，其中，d(x，y)表示兩者之間的歐式距離，simo(x，y)表示兩者之間相似度.

(5)

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

本文的主要思路是將原始的用戶-項目評分矩陣A經過缺失值填充和降維得到新的矩陣B，再用改進的相似度計算方法計算目標用戶和其他用戶之間的相似度，把相似度按照降序排列，取前N個近鄰用戶形成近鄰用戶集Nu，然后根據近鄰用戶集Nu中的每個近鄰用戶分別對目標用戶的目標項目進行評分預測，最后按照公式(9)得出最終的預測評分.

3.1 基于平均歐式距離與均值的填充和降維

3.1.1 基于平均歐式距離和用戶均值的填充

(6)

移項得：

(7)

a3=b3+2

當b3=2時，則a3=4，也就是說，當兩個向量評分尺度有差距時，我們可以用一個向量中的已知項對目標向量中對應的缺失值進行填充，特別是當這兩個向量的平均歐式距離很小的時候，填充效果非常好.

3.1.2 基于平均歐式距離和用戶均值的降維

前面已經介紹了填充的思想，本文接下來簡單介紹是如何實現降維的.首先，看下面的表1.

表1 淘寶店的反饋基本信息Table 1 Taobao shop feedback basic information

經過對該反饋信息進行分析，可以發現當瀏覽量增加或者減少的時候，訪客數也按照一定的規律增加或者減少，同樣的，下單數、成交量、交易額似乎也滿足這個規律.也就是說，當把訪客數、成交量、交易額當作冗余的特征去掉，對了解每天的交易情況沒什么影響.

同樣的道理，如要根據電影評分數據來探究用戶之間的關系，此時，如果把每一部電影當作一個特征，那么這些特征很可能也具有上面類似的關系，當刪除掉某些“特征”時，對研究用戶之間的相似關系并沒有什么影響.

本文對數據集的降維就是基于這種理解，在這里用項目之間的平均歐式距離來度量各個項目之間的相似關系.具體的實現過程如下：

Step1.確定需要進行填充的目標向量，然后選出能夠對目標向量缺失值進行填充的所有向量并組成一個集合A；

Step2.分別找出目標向量和集合A中所有向量的共同評分項目，然后計算出目標向量和集合A中所有向量的平均歐式距離d；

Step3.用集合A中平均歐式距離最小的向量按照公式(7)進行缺失值填充；

Step4.填充完畢后，直接刪出集合A中與目標向量平均歐式距離最小的向量，最終實現降維;

Step5.重復步驟1、2、3、4，直到數據集的維數達到預設值結束.

3.2 基于余弦距離和均值差的相似度

余弦相似度是最經典的相似度計算方法之一，由于它完全忽略了用戶之間評分尺度不同這個重要的因素，所以后來出現了修正余弦相似度和皮爾森相關系數法這些改進型的相似度計算方法，這在一定程度上能夠很好的彌補因用戶評分尺度不同對相似度計算結果的影響.

余弦距離注重兩個向量方向上的差異，同時為了彌補因用戶評分尺度不同對相似度計算結果的影響，本文提出了一種方法，結合兩個用戶評分尺度的相似度和余弦相似度得到一個綜合相似度，然后通過權值k來控制二者的重要程度.最后得到的相似度計算公式如下：

(8)

其中sim(u，v)表示u、v兩個用戶之間的相似度，k是兩者之間的權值，滿足0

3.3 基于用戶評分均值的評分預測

在協同過濾推薦算法中，關鍵是能準確的得到目標用戶的近鄰用戶集.本文給公式(8)中的k賦一個合適權值(k的取值與用戶評分尺度的集中度有關，評分尺度越集中，k值越大)，然后根據該公式計算用戶之間的相似度，最后得到目標用戶近鄰用戶集為Nu.

接下來就是根據Nu對目標項目進行評分預測，可以分成以下4個步驟：

Step1.從Nu中選出一個近鄰用戶un，他與目標用戶u之間的相似度為simu，un;

Step2.把目標項目的評分設成xn，類比于3.1.1中需要填充的缺失值，然后把該近鄰用戶的評分轉化為可以對xn進行填充的向量，最后按照公式(7)對xn的值進行填充.此時的填充值xn作為近鄰用戶un對目標項目的預測值；

Step3.重復步驟1、步驟2，直到遍歷完Nu里面的所有用戶，最終得到的預測值形成一個集合v，則v=[x1，x2，x3…xn]；

Step4.根據下面的公式(9)得到最終的預測評分，valuei表示對項目i的最終預測評分.

(9)

4 實驗結果與分析

本章首先介紹了實驗環境和選取的數據集以及實驗的評價指標，最后根據該數據集將改進的方法和傳統的方法進行對比分析.

4.1 實驗環境和數據集介紹

實驗使用的PC配置是Intel 酷睿i5 3230M的CUP，8GB內存，Windows 8企業版64位操作系統.編程語言使用python語言，版本為python2.7，編輯器用的是pyCharm社區版.

本實驗選用的是由Minnesota大學GroupLens小組給出的100k的movieLens數據集.該數據集包含943個用戶，1682部電影，評分范圍0.5-5分，且每個用戶電影評分次數不少于20次.實驗隨機選取數據中的80%作為訓練集，20%作為測試集，并且進行了交叉驗證.

4.2 實驗評價指標

目前推薦算法性能的評價指標[20]包括平均絕對誤差(Mean Absolute Error，MAE)以及查全率、查準率等.本文算法性能的評價指標選用的是MAE，MAE反映了預測值和真實值之間的差距，其值越小越好.假設推薦系統對項目的預測評分為集合{r1，r2，r3…rn}，項目的實際評分為集合{p1，p2，p3…pn}，則用戶MAE計算公式如下：

(10)

系統的MAE可以用式子(11)表示：

(11)

4.3 實驗結果與分析

本文實驗選用的數據集為100k的movieLens數據集，其稀疏度為93.69%.實驗分兩輪進行，第一輪訓練集數據稀疏度低于93.69%，第二輪訓練集數據稀疏度高于93.69%.

4.3.1 第一輪實驗結果

圖1反映的是把訓練集數據進行填充和降維處理前后，用皮爾森相關系數法計算相似度時，系統的MAE隨近鄰用戶N取值的變化曲線.

從圖1中我們可以看到，訓練集數據經過填充和降維以后，雖然近鄰用戶數量小于200、大于700時，系統MAE明顯比填充、降維前略大，但是近鄰用戶數量在200到600之間時，改進后系統的MAE更低，也就是說當我們選擇合適的近鄰用戶數量時，改進后的結果更可靠.另一方面本文實驗將訓練集數據經過幾輪填充和降維處理，把訓練集中的1345部電影用71個新的‘特征’代替，大大的減少用戶建模過程的時間損耗，增加了系統的可擴展性.

圖2中的兩條曲線都是將訓練集數據經過填充和降維處理后，用皮爾森相關系數法計算相似度時得到的系統MAE隨近鄰用戶數量變化的曲線，實線表示在填充和降維的基礎上，還通過公式(7)對預測的評分進行調整，虛線表示沒有經過調整.

從圖2中可以容易的看出，通過近鄰用戶對目標項目進行評分預測時，由公式(7)調整后，大大的減少了系統的MAE，增加了推薦準確度.

從圖2的實線我們可以得出，當近鄰數量為250的時候，系統的MAE最低，接下來，本文實驗用皮爾森相關系數法計算相似度的最好結果與公式(8)計算相似度的結果進行對比，結果如圖3所示.

圖1 系統EAM隨近鄰數量變化曲線Fig.1 System MAE with the number of neighbors near the curve

圖2 系統EAM隨近鄰數量變化曲線Fig.2 System MAE with the number of neighbors near the curve

圖3 系統MAE隨常數k變化曲線Fig.3 System MAE constant k curve of change

改進后的相似度計算方法相比于皮爾森相關系數法求解相似度又有了很大的提高，當k接近于1的時候，改進后的方法越接近于余弦相似度，皮爾森相似度是余弦相似度的改進型，能夠對因評分尺度不同導致的相似度計算不準確的問題進行改善，從圖中可以看出，當k趨近于1的時候，皮爾森相關系數法的優勢不太明顯，這是為什么呢？

首先，對于皮爾森相關系數法或者是修正余弦相似度，它們認為兩個向量夾角越小，模長越接近那么這兩個向量越相似，但是對于改進型的相似度計算方法，當k趨近1的時候，它判斷兩個向量相似的標準就發生了變化，也就是說，它幾乎不考慮向量的模長，但并不是說改進后的方法完全不考慮用戶評分尺度的問題，在3.3中，本文對目標項目進行評分預測時，利用公式(7)對預測結果進行了調整，這里就是針對評分尺度存在差距的用戶進行的優化.從公式(9)可以分析得出，計算相似度的值在本文實驗中僅僅決定了對應近鄰用戶對目標項目預測分值時的權重，最終預測結果是各個權值結果相加.

4.3.2 第二輪預測結果

同樣的，第二次實驗也得出了三張圖，分別為圖4、圖5、圖6.圖5依然是當經過填充和降維處理后，用皮爾森相關系數法求解相似度時，系統MAE隨近鄰用戶的變化曲線，這里的最佳近鄰用戶數量為300，目的是選出皮爾森相關系數法最優的近鄰數量和改進的相似度計算方法做比較，最終得到圖6.

圖4 系統EAM隨近鄰數量變化曲線Fig.4 System EAM with the number of neighbors near the curve

圖5 兩種方法對應的MAE值對比Fig.5 Comparison of the two MAE values corresponding to the two algorithms

圖6 系統MAE隨常數k變化曲線Fig.6 System MAE constant k curve of change

從上面的六張圖中可以看出，第二輪系統的MAE整體都高于第一輪，主要是因為第二輪訓練集數據的稀疏度高于第一輪，因此，通過訓練集建立的用戶模型相對會產生較大的誤差.所以，我們可以得出一個結論，在其他條件不變的情況下，訓練集數據越稠密，建立的模型越可靠.

5 結 論

本文針對傳統的相似性度量在數據稀疏情況下的不足提出了一種改進的協同過濾推薦算法，該方法通過對相似度計算進行一定的改進，并且結合評分矩陣的填充和降維，提高了推薦的準確性，同時減少了在尋找目標用戶的近鄰用戶集時的時間損耗，提高了系統的可擴展性.

[1] Zhao Nan.Practice and algorithm improvement of recommendation system based on mahout[D].Xian：Xidian University，2015.

[2] Hoy E,Rajarajan M.Recommendations in a heterogeneous service environment[J].Multimedia Tools and Applications，2013，62 (3)：785-820.

[3] Suguna R，Sharmila D.Association rule mining for web recommendation[J].International Journal on Computer Science and Engineering，2012，4(10)：1686-1690.

[4] Ujwala H.Wanaskar，Sheetal R.Vij，Debajyoti Mukhopadhyay.A Hybrid Web?recommendation system based on the improved association rule mining algorithm[J].Journal of Software Engineering and Applications，2013，6 (8)：396-404.

[5] Soo-Cheol Kim，Kyoung-Jun Sung，Chan-Soo Park，et al.Improvement of collaborative filtering usingrating normalization[J].Multimedia Tools and Applications，2016，75 (9)：4957-4968.

[6] Cui Bao-jiang，Jin Hai-feng，Liu Zhe-li，et al.Improved collaborative filtering with intensity based contraction[J].Journal of Ambient Intelligence and Humanized Computing，2015，6(5)：661-674.

[7] Hoill Jung，Kyungyong Chung.Knowledge-based diedietary nutrition recommendation for obese management[J].Information Technology and Management，2016，17(1)：29-42.

[8] Ahmad Nurzid Rosli，Tithrottanak You，Inay Ha，et al.Alleviating the cold-start problem by incorporating movies facebook pages[J].Cluster Computing，2015，18(1)：187-197.

[9] Ghazanfar M A,Prtigel-bennett.Leveraging clustering approaches to solve the gray-sheep users problem in recommender systems[J].Expert Systemswith Applications,2014，41(7)：3261-3275.

[10] Liu Wen.Research on ecommerce recommendation algorithm based on singular value decomposition and k-means clustering[D].Wuhan：Central China Normal University，2015.

[11] Gong Song-jie.A collaborative filtering recomme-ndation algorithm based on user clustering and item clustering[J].Journal of Software，2010，5(7)：745-752.

[12] Ye Hai-zhi，Liu Jun-fei.Collaborative filtering recommendation algorithm based on user reviews[J].Journal of Henan Normal University，2017，45(1)：79-84.

[13] Liu Hong-yan，He Jun,Wang Ting-ting，et al.Combining user preferences and user opinions for accurate recommendation[J].Electronic Commerce Research and Applications，2013，12(1)：14-23.

[14] Jang Zong-li，Wang Wei，Lu Chen.Improvement of collaborative filtering recommendation algorithm based on mean estimation[J].Computer Technology and Development，2017，27(5)：1-5.

[15] Balázs Hidasi，Domonkos Tikk.Speeding up ALS learning via approximate methods for context-aware recommendations[J].Knowledge and Information Systems，2016，47(1)：131-155.

[16] Wang Zan，Yu Xue，Feng Nan，et al.An improved collaborative movie recommendation system using computational intelligence[J].Journal of Visual Languages & Computing，2014，25(6)：667-675.

[17] Xia Pei-pei，Zhang Li，Li Fan-zhang.Learning similarity with cosine similarity ensemble[J].Information Sciences，2015，307：39-52.

[18] Chen Gong-ping，Wang Hong.A personalized recommendation algorithm for improving pearson correlation coefficient[J].Journal of Shandong Agricultural University，2016，47(6)：940-944.

[19] Haw-ren Fang，Dianne P.O′Leary.Euclidean distance matrix completion problems[J].Optimization Methods and Software，2012，27(4-5)：695-717.

[20] Zhang Feng，Ti Gong，Victor E.Lee，et al.Fast algorithms to evaluate collaborative filtering recommender systems[J].Knowledge-Based Systems，2016，96：96-103.

附中文參考文獻：

[1] 趙 楠.基于Mahout的推薦系統實踐及算法改進[D].西安：西安電子科技大學，2015.

[10] 劉 雯.基于奇異值分解和k-means聚類的電子商務推薦算法研究[D].武漢：華中師范大學，2015.

[12] 葉海智，劉駿飛.基于用戶評論的協同過濾推薦算法[J].河南師范大學學報，2017，45(1)：79-84.

[14] 蔣宗禮，王 威，陸 晨.基于均值預估的協同過濾推薦算法改進[J].計算機技術與發展，2017，27(5)：1-5.

[18] 陳功平，王 紅.改進Pearson相關系數的個性化推薦算法[J].山東農業大學學報，2016，47(6)：940-944.