K-近鄰矩陣分解推薦系統算法

郝雅嫻，孫艷蕊

(東北大學 理學院，沈陽 110819) E-mail：Hao_yaxian@163.com

1 概 述

近幾年來，隨著Internet的發展以及電子商務網站迅速崛起，推薦系統[1]廣泛應用于電子商務網站，為網站用戶進行商品智能推薦，大大提高了電子商務網站的商業效益.因此，如何提高推薦算法的推薦結果準確性成為電子商務網站的目標追求.協同過濾算法[2]是目前應用最廣泛且效果最好的推薦系統算法.但是，隨著電子商務網站不斷增加的用戶量與商品量，大數據下導致的數據稀疏性使得協同過濾算法已經遠遠不能正確對用戶的評分值做出準確的預測.所以，在協同過濾算法基礎上進行改進的算法不斷出現.例如：基于項目的協同過濾算法及其算法改進[3-5]，基于神經網絡的協同過濾算法[6]以及基于矩陣降維的協同過濾算法[7，8]，基于鄰域的協同過濾算法改進[9]等.

本文算法是在基于鄰域的協同過濾算法與基于矩陣分解的協同過濾算法[10]兩方面基礎上提出的.主要貢獻是解決了大數據導致的極大稀疏性問題，并且能很好的找到與目標用戶對目標項目的評分相關性較大的用戶與項目，使得評分值更加精確，算法主要包括三個方面的內容：一、分別對目標用戶u與目標項目i尋找其最近鄰，這一部分在4.2與4.3詳細給出，二、建立近鄰矩陣并對近鄰矩陣進行矩陣分解，三、預測評分值，二、三部分在4.4中給出.

2 傳統的矩陣分解

2.1 矩陣分解模型

矩陣分解算法具有伸縮性好，靈活性高等特點.最早的矩陣分解算法為奇異值分解算法(Singular Value Decompostion，SVD)，但是SVD有兩方面的缺點：一是在算法執行之前必須補全原始評分矩陣中的缺失值；二是算法執行效率太低.在SVD算法之后Simon Funk將隨機梯度下降算法應用在推薦算法中，他利用隨機梯度下降算法高效的實現了評分值的預測.此后，利用隨機梯度下降算法的矩陣分解被應用于各大電子商務網站，成為了經典的推薦系統算法.

Simon Funk提出的矩陣分解算法是將用戶與項目映射到隱語義空間上，因此該算法也被稱作隱語義模型.以電影為例，影響用戶對電影評分值的隱語義可能是電影的類型：悲劇、喜劇、愛情片等等.矩陣分解算法進行商品推薦的前提是對原始評分數據矩陣的學習，設原始評分矩陣有m個用戶，n個項目，記原始評分矩陣為Rm×n=(rui)m×n.f表示隱語義的個數.每個用戶u對應一個隱語義向量(用戶因子向量)pu∈Rf，每個項目i對應一個隱語義向量(項目因子向量)qi∈Rf.算法通過將用戶因子向量與項目因子向量做內積來對未知評分項做預測[10].

(1)

2.2 隨機梯度下降算法

(2)

1)已知rui-qTpu～N(0，δ2)

3)最大化p(rui)，等價于最大化lnp(rui)，由(2)得：

4)觀察lnp(rui)可知，在等式右邊的兩項中，只有∑∑(rui-qTpu)2為變量，所以最大化lnp(rui)，等價于最小化∑∑(rui-qTpu)2.

(3)

(4)

(5)

其中γ控制迭代的步長，不宜太大，通常利用交叉驗證得到.通過等式(4)的計算分別得到項目因子向量(6)與用戶因子向量(7)參數更改的定義式[10].

qi=qi+γ·(eui·pu-λ·qi)

(6)

pu=pu+γ·(eui·qi-λ·pu)

(7)

利用隨機梯度下降算法得到能夠使等式(3)最優的參數qi∈Rf與pu∈Rf，從而得到預測評分值.Simon Funk提出的矩陣分解算法提高了算法的執行效率，但是在大數據背景下，這一經典算法已經不能夠很好的反映原始數據的真實性，因為原始評分矩陣極大的稀疏性對實驗結果準確造成很大影響.所以在該算法上建立了很多混合算法與改進算法來提高推薦結果的準確性.本文提出了一個基于矩陣分解與最近鄰的混合協同過濾算法，該算法充分利用了矩陣分解算法與最近鄰算法的優點，實驗證明本文算法有較好的推薦效果.

3 傳統的最近鄰算法

基于最近鄰算法(K-Nearest Neighbor algorithm，KNN)是最常用的協同過濾算法，最先提出的是基于用戶的協同過濾算法[12].其基本思想是利用目標用戶近鄰用戶的評分值去估計目標用戶對項目的評分預測值.隨后基于項目的最近鄰算法被提出[13，14]，因為基于項目最近鄰算法比基于用戶最近鄰算法具有更好的合理性與高效性，被廣泛應用.在這里只介紹基于項目最近鄰算法的基本思想，對于目標項目i的最近鄰尋找，首先定義最近鄰個數k，將計算所得的相似度按從大到小的順序排列，選取前k個作為目標項目i的k個最近鄰用戶.尋找項目最近鄰算法的關鍵問題是通過計算相似度來尋找最近鄰，計算相似度的方法常用的有歐氏距離、余弦相似度以及皮爾遜相似度，本文采用歐氏距離方法計算相似度，計算公式如下：

(8)

公式(7)中的i與j分別表示原始評分矩陣中的任意兩個項目，Ri與Rj分別表示項目i與j對應的評分向量，Sij表示項目i與j之間的相似度大小.將計算所得的相似度大小保存到相似度向量矩陣中，預測評分值由評分值與相似度的加權平均值得到，記Nk(i；u)為項目i的最近鄰集合，j∈Nk(i;u)表示用戶u評過分的項目i的近鄰項目j[11]則：

(9)

基于最近鄰算法是最早期的協同過濾算法，當在原始評分矩陣具有極大的稀疏性時，利用相似度計算目標項目的最近鄰會出現誤差.因此許多學者在KNN算法執行之前會首先對原始評分矩陣進行預處理，從而使算法的準確性提高.本文在對原始數據處理之后，同時對目標用戶與目標項目查找最近鄰，并建立近鄰評分矩陣，對新的評分矩陣進行矩陣分解，實驗證明本文算法提高了推薦結果的精確度.

4 K近鄰矩陣分解算法

為了更好的解決原始評分矩陣稀疏性與推薦結果的準確性，許多學者建立了協同過濾算法的混合型算法，例如Yehuda Koren等人提出的混合算法[14].本文在最近鄰算法與矩陣分解算法的基礎上提出了一個新的混合算法——K近鄰矩陣分解算法，(A K-Nearest Neighbor Matrix Factorization for Recommender systems)簡稱KNNMF.

4.1 初始化評分矩陣

因為原始評分矩陣極大的稀疏性，會影響算法實驗結果的準確性，所以在算法執行之前首先對原始評分矩陣進行初始化，本文采用文獻[14]中的公式(10)對原始評分矩陣進行數據預處理.

(10)

圖1 k=2時RMSE隨參數α、f的變化分布Fig.1 DistributionofRMSEwithα、fbasedonk=2圖2 k=5時RMSE隨參數α、f的變化分布Fig.2 DistributionofRMSEwithα、fbasedonk=5

圖3 k=7時RMSE隨參數α、f的變化分布Fig.3 DistributionofRMSEwithα、fbasedonk=7圖4 k=10時RMSE隨參數α、f的變化分布Fig.4 DistributionofRMSEwithα、fbasedonk=10

5,7,10，固定f，參數α的改變對RMSE的值影響不大，如圖1-圖4.因此本文取α=500作為實驗數據量(見圖1-圖4).

4.2 基于用戶最近鄰計算

本文算法首先計算用戶最近鄰，針對目標用戶u尋找其前k個最近鄰，v∈Nk(u;i)表示對商品i評過分的用戶u的近鄰用戶v，建立用戶u的近鄰集合U={v|v∈Nk(u;i)}.例如表1給出了五個用戶對五個商品的評分情況，如果計算用戶User3對目標項目Item1的評分(在這里取k=2).需首先尋找對項目Item1評過分的用戶，即表1中User1,User2,User3，利用歐氏距離計算目標用戶與以上用戶之間相似度分別為：S13=2.2361，S23=5.8130，S53=4.5826.由歐氏距離的大小可知User1與User5為目標用戶User3的k最近鄰用戶，此時目標用戶的近鄰集合U={User1,User5}.

表1 用戶-商品評分矩陣Table 1 Users- items rating matrix

4.3 基于項目最近鄰計算

將目標用戶k的最近鄰保存于集合U中，接下來對目標項目i尋找其前k個最近鄰，j∈Nk(i；u)表示用戶u評過分的項目i的近鄰項目j，建立項目i的近鄰集合J={j|j∈Nk(i;u)}.計算表1中用戶User3對目標項目Item1的評分(在這里取k=2)，首先尋找用戶User3評過分的項目，即表1中Item2，Item3,Item4,Item5利用歐氏距離計算目標項目與以上項目之間的相似度，分別為S12=3.4641，S13=6.7832，S14=6.4807，S15=5.6569.顯然Item2與Item5為目標項目Item1的k最近鄰用戶，此時目標項目的近鄰集合J={Item2,Item5}.

4.2與4.3主要計算目標用戶與目標項目的前k個最近鄰，并將計算所得的目標用戶與目標項目的最近鄰分別保存到目標用戶近鄰集合U={v|v∈Nk(u;i)}與目標項目集合J={j|j∈Nk(i;u)}，在數據集中，每一個用戶與項目均有最近鄰，所以可以得到用戶近鄰矩陣UKm×k=[U1,U2，…，Um]T與項目近鄰矩陣JKn×k=[J1,J2,…,Jn]T.用戶近鄰矩陣與項目近鄰矩陣為接下來建立近鄰評分矩陣做準備.

4.4 矩陣分解與評分預測

預測評分值rui，目標用戶u的k最近鄰對目標項目i的k最近鄰的評分值構成的矩陣，稱為近鄰評分矩陣，記為KR，則

這是一個k階方陣，rviji表示目標用戶近鄰對目標項目近鄰的評分值，其中vi∈U，ji∈J，I=1,2,…,k.

例如在4.2的例子中，要預測User3對目標項目Item1的評分，根據定義可以建立如下近鄰評分矩陣.本算法提出的近鄰評分矩陣有效的提取了目標用戶對目標項目評分值相關性最大的近鄰用戶與近鄰商品的信息，從而降低了稀疏性對實驗結果的影響，提高了算法的推薦精度.

DRk×k=PQT

(11)

本文提出了計算未知評分值rui的新方法.在公式(11)中，|DRk×k|表示矩陣DRk×k的行列式值，行列式的值是矩陣特征值的乘積，特征值反映了矩陣本身的性質.因為每一個用戶與項目作為目標用戶與目標項目的最近鄰的概率均為1/k，所以rui的值由分解之后矩陣的行列式值乘以1/k.

(12)

對矩陣KR進行分解時需要考慮因子個數對推薦準確度的影響.本文以MovieLine數據集為實驗數據，在參數α=500的條件下，尋找矩陣分解實驗的最優隱因子個數f，如圖5，圖中iterlatent為隱語義個數f，通過實驗可知，當因子個數為5與2時推薦結果的準確度幾乎相近.所以當因子個數取5與2時，推薦結果是最好的，從而下面的實驗中均取f=5.

5 實驗結果與分析

5.1 評價標準

本算法利用均方根誤差(RMSE)驗證實驗結果的準確性，以RMSE值作為實驗準確性的評價指標，RMSE的值越小算法實驗結果越優.計算公式如下：其中TestSet表示測試集[15].

(13)

5.2 實驗結果

本文實驗所采用的數據集為MovieLens數據集，MovieLens數據集是包含943個用戶與1682部電影的評分矩陣.本文算法與三種算法進行比較：

圖6為本文提出的K近鄰矩陣分解算法(K-Nearest Neighbor Matrix Factorization，KNNMF)與原始矩陣分解算法(Matrix Factorization，MF)的實驗結果對比圖，由圖可知，對k=2,5,7,10時，隨著隱因子個數的變化，KNNMF算法所得的RMSE值低于MF算法的RMSE值，所以本文算法的實驗結果更加精確.

圖5 RMSE隨參數的f變化分布Fig.5 DistributionofRMSEwithf圖6 原始矩陣分解與K近鄰矩陣分解算法RMSE比較Fig.6 RMSEcomparisonofmatrixfactorizationandKNNMF

圖7為本文提出的KNNMF算法與Y.Koren等人提出的聯合近鄰插值算法[14]的實驗結果對比，由圖中數據可知，取相同的k近鄰時，本文算法KNNMF的RMSE值遠遠的小于KNNw的RMSE值，所以，本文算法極大的提高了推薦結果的精確度.

圖7 聯合近鄰插值算法與K近鄰矩陣分解算法RMSE比較Fig.7 RMSEcomparisonofKNNwandKNNMF圖8 基于PCA與聯合近鄰權值的協同過濾算法與基于近鄰與矩陣分解混合算法RMSE比較Fig.8 RMSEcomparisonofPCAwithjointlyderivedneighborhoodandKNNMF

圖8為本文提出的KNNMF算法與基于PCA與聯合近鄰權值的協同過濾算法(PCAwKNN)的實驗結果對比，PCAwKNN算法是將主成分分析(Principal Component Analysis，PCA)與文獻[14]中的近鄰插值算法混合，從數據中可知，KNNMF算法的精確度遠遠高于PCAwKNN算法的精確度.

從三組實驗結果的實驗數據對比中可知，本算法極大的剔除了與目標用戶以及目標項目無關的數據影響，不僅降低了原始評分矩陣的稀疏性影響，而且有效的提高了算法的準確性.

6 總 結

本文提出的K近鄰矩陣分解推薦算法，結合了經典矩陣分解算法與最近鄰算法的優點.在對未知評分項預測時，同時考慮目標用戶與目標項目的最近鄰，大大減少了無關用戶與項目的相關評分值影響.并提出了新的近鄰評分矩陣，對近鄰評分矩陣進行矩陣分解，給出了計算未知評分項的新方法.實驗結果證明，本文提出的算法對比傳統的協同過濾推薦算法得到更準確的推薦結果.

[1] Schafer J B，Konstan J A，Riedl J.E-commerce recommendation applications[J].Data Mining and Knowledge Discovery，2001，5(1)：115-153.

[2] Adomavicius G，ATuzhilin.Towards the next generation of recommend systems：a survey of the state-of-the-art and possible extensions[J].IEEE Transactions on Knowledge and Data Engineering，2005，17(6)：734-749.

[3] KaryPis G.Evaluation of item-based top-n recommendation algorithms[C].Proceedings of the 10th International Conference on Information and Knowledge Management，New York：ACM Press，2001：247-254.

[4] Sarwar B，KaryPis G，Konstan J，et al.Item-based collaborative filtering recommendation algorithms[C].Proceedings of the 10th International Conference on World Wide Web,New York：ACM Press，2001：285-295.

[5] Wu Yan-wen,Wang Jie,Wang Fei.Collaborative filtering recommendation model based on hybrid particle swarm optimization and genetic algorithm[J].Journal of Chinese Computer Systems，2017，38(3)：527-530.

[6] Zhang Feng，Chang Hui-you.Employing BP neural networks to alleviate the sparsity issue in collaborative filtering recommendation algorithms[J].Journal of Computer Research and Development，2006，43(4)：667-672.

[7] Sarwar B M，Karypis G，Konstan J A，et al.Application of dimensionality reduction in recommender system-a case study，TR 00—043 [R].Minneapolis，USA：Department of Computer Science and Engineering，University of Minnesota，2000.

[8] Zhao Liang，Hu Nai-jing，Zhang Shou-zhi.Algorithm design for personalization recommendation systems[J].Journal of Computer Research and Development，2002，39(8)：986-991.

[9] Bell R，Koren Y，Volinsky C.Modeling relationships at multiple scales to improve accuracy of large recommender systems[C].Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining(KDD′07)，2007：95-104.

[10] Koren Y，bell R，Volinsky C.Matrix factorization techniques for recommender systems[J].IEEE Computer Society，2009，42(8)：30-37.

[11] Hu Yi-fan，Yehuda Koren，Chris Volinsky.Collaborative filtering for implicit feedback datasets[C].IEEE International Conference on Data Mining(ICDM′08)，2008：263-272.

[12] Herlocker J L，Konstan J A，Riedl J.An algorithmic framework for performing collaborative filtering[C].Proceedings of the 22nd Annual International ACM SIGIR Conference on Research and Development in Information Retrieval，1999：230-237.

[13] Linden G，Smith B，York J.Amazon.com recommendations：item-to-item collaborative filtering[J].IEEE Internet Computing，2003，7(1)：76-80.

[14] Bell and Koren Y.Scalable collaborative filtering with jointly derived neighborhood interpolation weights[C].IEEE International Conference on Data Mining(ICDM′07)，2007：43-52.

[15] Koren Y.Factorization meets the neighborhood：a multifaceted collaborative filtering model[C].Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD′08)，2008：426-434.

附中文參考文獻：

[5] 吳彥文，王 潔，王 飛.混合粒子群遺傳算法的協同過濾推薦模型[J].小型微型計算機系統，2017，38(3)：527-530.

[6] 張 鋒，常會友.使用BP神經網絡緩解協同過濾算法的稀疏性問題[J].計算機研究與發展，2006，43(4)：667-672.

[8] 趙 亮，胡乃靜.張守志.個性化推薦算法設計[J].計算機研究與發展，2002，39(8)：986-991.