結(jié)合物品流行度的列表級矩陣因子分解算法

周瑞環(huán)，趙宏宇

(西南交通大學(xué) 信息科學(xué)與技術(shù)學(xué)院，成都 611756)(*通信作者電子郵箱nuomimick@163.com)

0 引言

近年來，隨著信息技術(shù)的迅速發(fā)展，互聯(lián)網(wǎng)進(jìn)入到Web 2.0時代。在Web2.0時代，用戶不再是信息的接受者，更是信息的制造者與傳播者。而隨著越來越多的信息充斥著網(wǎng)絡(luò)，用戶無法從大量的信息中獲取對自己真正有用的那部分信息，對信息的使用效率反而降低了，這就造成了“信息過載”問題[1]。

為了解決“信息過載”問題，在互聯(lián)網(wǎng)的發(fā)展過程中出現(xiàn)了分類目錄、搜索引擎、個性化推薦系統(tǒng)。個性化推薦系統(tǒng)主要用于預(yù)測一個用戶是否會喜歡一個特定的物品(評分預(yù)測問題)或者是為一個用戶推薦感興趣的N個物品[2](Top-N推薦問題)。協(xié)同過濾算法[3]是個性化推薦系統(tǒng)中應(yīng)用最廣泛的算法。協(xié)同過濾算法主要的兩種技術(shù)分別是基于近鄰的算法和矩陣因子分解算法。基于近鄰的算法考慮的是用戶或物品之間的相似關(guān)系來解釋用戶對物品的評分。矩陣因子分解算法，考慮的是用戶和物品在隱語義空間中的隱語義因子特征來解釋用戶對物品的評分。相對于基于近鄰的算法，矩陣因子分解算法因其在稀疏數(shù)據(jù)集上的準(zhǔn)確性和穩(wěn)定性得到廣泛的關(guān)注。而隨著硬件的飛速發(fā)展和大數(shù)據(jù)時代的到來，基于深層神經(jīng)網(wǎng)絡(luò)的算法在各個領(lǐng)域都被廣泛地研究。基于自動編碼器的協(xié)同過濾算法[4]解決了評分預(yù)測問題。基于降噪自動編碼器的協(xié)同過濾算法[5]解決了Top-N推薦問題。神經(jīng)協(xié)同過濾算法[6]提出了一個通用框架將矩陣因子分解算法和神經(jīng)網(wǎng)絡(luò)結(jié)合到一起。基于深層神經(jīng)網(wǎng)絡(luò)的推薦算法可以學(xué)習(xí)出用戶和物品之間的非線性關(guān)系，而不像矩陣因子分解算法只能學(xué)習(xí)用戶和物品潛在特征的點乘關(guān)系。然而，基于深層神經(jīng)網(wǎng)絡(luò)的推薦算法網(wǎng)絡(luò)架構(gòu)難以改變，也就難以結(jié)合其他的信息改進(jìn)推薦效果。因而，矩陣因子分解算法仍是推薦系統(tǒng)的利器。

隱語義模型(Latent Factor Model， LFM)算法[7]是最簡單的矩陣因子分解模型。LFM算法認(rèn)為正是用戶與物品之間的交互作用才導(dǎo)致評分間的差異，因此把評分矩陣近似為用戶矩陣和物品矩陣的乘積。用戶矩陣的每一行代表了一個用戶的隱語義因子向量，可以理解為用戶對向量中每個因子的喜好程度。物品矩陣每一行代表了物品的隱語義因子向量，可以理解為物品擁有向量中每個因子的程度。評分中與用戶與物品交互作用無關(guān)的部分稱為偏置因子。產(chǎn)生偏置因子的原因在于每個用戶評分的基準(zhǔn)，每個物品被評分的基準(zhǔn)都是不一致的。Koren[8]提出了奇異值分解(Singular Value Decomposition， SVD)算法，SVD++(transmutative Singular Value Decomposition)算法和Asymmetric-SVD算法。SVD算法認(rèn)為用戶對物品的評分由偏置因子和用戶與物品的交互作用組成。SVD++算法在SVD算法的基礎(chǔ)上考慮了物品之間的隱式相關(guān)性，并意識到隱式反饋數(shù)據(jù)對只擁有少量顯式反饋數(shù)據(jù)的用戶的重要性。Asymmetric-SVD算法將矩陣因子分解思想應(yīng)用到基于近鄰的算法。物品因子相似度模型(Factored Item Similarity Model， FISM)算法[9]是在隱式反饋數(shù)據(jù)集上提出的算法，其主要思想是物品之間的隱式相關(guān)性是物品推薦的重要因素。SVD++算法和Asymmetric-SVD算法的評分規(guī)則用到了用戶有過行為的物品集合。在模型訓(xùn)練階段，集合中包括待評分物品。在模型預(yù)測階段，集合不包括待評分物品。算法的評分規(guī)則在兩個階段并不一致。

受到20世紀(jì)末GroupLens研究組和2006年Netflix Prize的影響，在很長一段時間內(nèi)的學(xué)術(shù)研究都是基于優(yōu)化評分預(yù)測指標(biāo)——均方根誤差(Root Mean Squared Error， RMSE)。有研究表明，評分預(yù)測的準(zhǔn)確率和Top-N推薦準(zhǔn)確率之間并沒有直接關(guān)系[10]。直接以提高評分預(yù)測準(zhǔn)確率為優(yōu)化目標(biāo)，并不一定可以提升Top-N推薦準(zhǔn)確率。比如，用戶對兩個物品A和B的實際評分分別為2分和3分，模型一和模型二是由同一種算法采用不同隨機(jī)數(shù)種子訓(xùn)練得到的模型。假設(shè)模型一對兩個物品的預(yù)測評分分別是2.7分和3.5分，那么推薦列表中物品B的位置在物品A前面。模型二對兩個物品的預(yù)測評分分別是2.7分和2.5分，那么推薦列表中物品A的位置在物品B前面。模型一和模型二的均方根誤差相等，兩個物品在推薦列表中的順序卻相反。這就可能導(dǎo)致用戶感興趣的物品不在Top-N推薦列表中，從而得不到推薦。為解決這個問題，有研究者提出了將排序?qū)W習(xí)應(yīng)用于推薦的一些方法[11]。

排序?qū)W習(xí)[12]的思想是為每個用戶，使用訓(xùn)練好的模型產(chǎn)生一個排序好的推薦列表，而不是為預(yù)測每個待推薦物品的評分。排序?qū)W習(xí)根據(jù)輸入樣本的不同可分為點級、對級、列表級。點級方法對用戶的每個待評分物品進(jìn)行評分，按照評分結(jié)果大小進(jìn)行排序得到最后的推薦列表，本質(zhì)上是一個回歸或者多分類問題。SVD算法的目標(biāo)函數(shù)是所有實際評分和預(yù)測評分的平方誤差和，是典型的點級方法。對級方法[13]對用戶的每一對待評分物品順序進(jìn)行判斷，按照物品兩兩之間的順序得到最后的推薦列表，本質(zhì)上是一個二分類問題。列表級方法輸入所有物品的集合，更加全面考慮了物品之間的順序關(guān)系。列表級方法有兩種方法：一種方法是定義列表級的損失函數(shù)并求解排序函數(shù)[14]；另一種方法將排序函數(shù)與最終對其的評價指標(biāo)相關(guān)聯(lián)，認(rèn)為最優(yōu)的排序函數(shù)必定會獲得最優(yōu)的評價指標(biāo)[15]。文獻(xiàn)[16]提出了一種列表的Top-N排序概率公式，該概率公式的不足之處在于相同評分的物品在推薦列表中的位置的概率是一樣的。

針對上述SVD++算法的評分規(guī)則不一致問題和Top-N排序概率公式的不足，本文提出了一種結(jié)合物品流行度的列表級矩陣因子分解算法：1)在模型訓(xùn)練階段，去除評分規(guī)則用到的用戶有過行為的物品集合中的待評分物品，保證兩個階段評分規(guī)則的一致性。2)結(jié)合物品流行度改進(jìn)了列表級Top-N概率公式，保證即使相同評分下，物品在列表中的位置概率也并不相同。3)使用隨機(jī)梯度下降算法求解目標(biāo)函數(shù)并進(jìn)行Top-N推薦。在MovieLens和Netflix兩個數(shù)據(jù)集上進(jìn)行測試和比較分析，實驗結(jié)果表明，與目標(biāo)函數(shù)為點級和列表級的SVD++算法相比，本文算法有較高的Top-N推薦準(zhǔn)確率。

1 基本定義與算法描述

1.1 基本定義

(1)

1.2 SVD++算法

SVD++算法[8]中用戶u對物品i的評分規(guī)則如下：

(2)

其中pu、yj、qi分別為用戶因子矩陣P的第u行向量、物品因子矩陣Y的第j行向量和物品因子矩陣Q的第i行向量。

該算法在SVD算法的基礎(chǔ)上考慮了物品之間的隱式相關(guān)性。而這部分不需要顯式評分，因此可以擴(kuò)展到隱式反饋數(shù)據(jù)集上，從而更好地利用了用戶行為數(shù)據(jù)。從另一個角度考慮，SVD++算法添加了第2個物品因子矩陣，這些新的物品因子向量根據(jù)用戶有過行為的物品集合來描述用戶的特征。

1.3 ListRank-MF算法

ListRank-MF算法[14]是一種列表級排序?qū)W習(xí)思想結(jié)合矩陣因子分解的推薦算法。在文獻(xiàn)[13]中提出了一種列表的Top-N排序概率，假設(shè)用戶u的推薦列表為y(i1,i2,…,in)，那么it表示列表t位置上的物品編號，ruit表示用戶u對it物品的評分，則產(chǎn)生這個推薦列表的概率為：

(3)

為簡化運算，ListRank-MF算法將n取為1，φ(x)=ex，從而得到推薦列表中物品i在列表中第1個位置上的概率，即列表的Top- 1排序概率為：

(4)

接著使用交叉熵表示真實概率分布和預(yù)測概率分布的差異。交叉熵越低，則說明兩個分布越接近。目標(biāo)函數(shù)為：

(5)

其中g(shù)(x)是sigmoid函數(shù)，用于限制輸出范圍。目標(biāo)函數(shù)通過交替固定變量的梯度下降算法進(jìn)行求解。

2 本文算法

SVD++算法的評分規(guī)則的一個問題在于評分規(guī)則在模型訓(xùn)練階段和模型預(yù)測階段的不一致。預(yù)測規(guī)則中的集合R(u)在模型訓(xùn)練階段包括了待評分物品，在模型預(yù)測階段不包括待評分物品，造成了預(yù)測規(guī)則在兩個階段的不一致。理論上來講，模型訓(xùn)練階段是不應(yīng)該有待評分物品的所有信息的，否則會造成信息泄露。文獻(xiàn)[9]在其算法中也指出當(dāng)隱語義因子維度增大時兩種情況的算法性能差異，因此，本文算法首先對評分規(guī)則進(jìn)行修正，評分規(guī)則修正為：

(6)

其中R(u) {i}表示除了i物品外，用戶u有過行為的物品的集合。

式(5)處的Top- 1列表概率的不足之處在于相同評分的物品的概率是一樣的。而現(xiàn)實生活中，評分的等級是有限的。例如豆瓣電影網(wǎng)站，用戶給看過的電影的評分等級就只有很差、較差、還行、推薦、力薦五個等級。假如豆瓣電影網(wǎng)站為某用戶推薦的電影都在力薦這個等級，如果存在某種限制使得用戶只能看列表中的部分電影，那么相同評分下，確定電影的位置順序是很有意義的。尤其對于不活躍的用戶來說，往往只觀看推薦列表中的部分電影。

在現(xiàn)實生活中，物品流行度[18]和用戶活躍度分布滿足長尾分布。一般認(rèn)為，不活躍的用戶更傾向于瀏覽流行度高的物品，而活躍用戶在瀏覽完熱門的物品后會開始瀏覽流行度低的物品[3]。本文定義物品的流行度為物品被評分的次數(shù)。物品被評分的次數(shù)越多，說明該物品越流行。

基于以上分析，本文認(rèn)為大量物品評分一樣的情況下，流行度高的物品被推薦的概率越大，即排在列表第一個位置的概率越大，因此，對式(5)進(jìn)行改進(jìn)得到：

δ(i)=ci/(cmax+α)

(7)

其中：δ(i)表示物品i對評分的修正函數(shù),δ(i)∈(0,1)；ci表示物品i被評分的次數(shù)；cmax表示最流行物品被評分的次數(shù)；伸縮系數(shù)α≥1，控制δ(i)的范圍。將δ(i)限制到(0,1)區(qū)間的原因是本文認(rèn)為物品流行度帶來的影響應(yīng)該小于直接由用戶對物品的評分帶來的影響。

接著，本文使用與ListRank-MF算法一樣的交叉熵構(gòu)造目標(biāo)函數(shù)。在加入正則化參數(shù)后，最終的目標(biāo)函數(shù)如下：

(8)

不同于文獻(xiàn)[17]的方法，本文使用隨機(jī)梯度下降算法求解該最優(yōu)化問題。隨機(jī)梯度下降算法有收斂速度快、時間復(fù)雜度低的優(yōu)點。令：

(9)

則各參數(shù)的迭代計算公式如下：

(10)

其中：γ表示學(xué)習(xí)率；λ表示正則化系數(shù)。模型訓(xùn)練階段算法偽代碼描述如下：

輸入：訓(xùn)練數(shù)據(jù)集D，學(xué)習(xí)率γ，正則化系數(shù)λ，隱語義因子特征維數(shù)f，迭代次數(shù)T。

輸出：向量b(u)、b(i)，矩陣P、Q、Y。

向量b(u)、b(i)的值初始化為0

矩陣P、Q、Y的值隨機(jī)初始到區(qū)間(0,1/sqrt(f))

fort=0,1,…,T-1 do

foru=0,1,…,m-1 do

計算fu,i

sum← 0

fori∈R(u) do

fori∈R(u) do

forj∈R(u) {i} do

yj-=γ(sum(nu-1)-1/2qi+λyj)

模型預(yù)測階段，根據(jù)式(8)為每個用戶計算其未評分物品排在列表第一個位置的概率。對于一個用戶的所有物品，式(8)分母部分是一樣的，因此只需要計算分子部分，選擇值最大的Top-N的物品即可。

3 實驗結(jié)果及分析

3.1 數(shù)據(jù)集和實驗設(shè)置

本文的實驗基于兩個公開數(shù)據(jù)集，分別是MovieLens和Netflix數(shù)據(jù)集。MovieLens是GroupLens研究小組公布的MovieLens電影推薦系統(tǒng)中用戶對電影評分?jǐn)?shù)據(jù)集。Netflix數(shù)據(jù)集是美國Netflix公司在2006年舉辦評分預(yù)測競賽時公布的數(shù)據(jù)集。對于每個數(shù)據(jù)集，本文隨機(jī)選擇75%的評分?jǐn)?shù)據(jù)作訓(xùn)練集，剩余25%的評分?jǐn)?shù)據(jù)作測試集。數(shù)據(jù)集說明如表1所示。

本文實驗采用歸一化折損累積增益(Normalized Discounted Cumulative Gain， NDCG)指標(biāo)[18]。NDCG是一種應(yīng)用廣泛的、和順序相關(guān)的Top-N推薦準(zhǔn)確率評價指標(biāo)，其計算方法如下：

(11)

其中：U表示用戶集合，R(u,p)是用戶u對推薦列表中第p個位置上物品的評分，DCG(Discounted Cumulative Gain)即折損累積增益，IDCG@N(u)為所有DCG@N(u)的最大值。如果推薦列表有物品不在測試集中，則相應(yīng)評分為0。對于不同的NDCG@N，測試集中應(yīng)保證每個用戶至少有N個評分對象。

表1 實驗中使用的數(shù)據(jù)集

本文將基于以下幾個算法作比較分析。

PopularRec 基于物品流行度的推薦算法。為每個用戶推薦未有過行為的物品中最流行的N個物品。

SVD++_rmse 基于修正的SVD++評分規(guī)則，使用點級目標(biāo)函數(shù)，即實際評分與預(yù)測評分的平方誤差和，記為點級SVD++算法。

SVD++_ce 基于修正的SVD++評分規(guī)則，使用列表級目標(biāo)函數(shù)，即實際評分分布和預(yù)測評分分布的交叉熵，記為列表級SVD++算法。

SVD++_cep 基于修正的SVD++評分規(guī)則，根據(jù)物品流行度改進(jìn)了列表的Top- 1排序概率，使用列表級目標(biāo)函數(shù)，即實際評分分布和預(yù)測評分分布的交叉熵，是本文提出的算法，即結(jié)合物品流行度的列表級矩陣因子分解算法。

本文所有算法均在Windows操作系統(tǒng)下使用Python在Pycharm開發(fā)平臺上編寫，計算機(jī)配置為4核Intel Core i7處理器2.8 GHz、24 GB內(nèi)存。

3.2 實驗結(jié)果

3.2.1 不同算法性能對比

圖1是本文算法的學(xué)習(xí)率為0.01，正則化系數(shù)為0.001時，在Movielens- 100k數(shù)據(jù)集上，NDCG值隨著迭代次數(shù)變化的趨勢圖。從圖1中可以看出本文算法在迭代次數(shù)為15以后，NDCG值變化幅度已經(jīng)不大，算法已經(jīng)收斂。

圖1 本文算法隨迭代次數(shù)變化的性能趨勢

表2是PopularRec算法在兩個數(shù)據(jù)集上的不同推薦列表長度的性能對比。從表2可以看出，PopularRec算法不穩(wěn)定，不同推薦列表長度的NDCG值在Movielens- 100k數(shù)據(jù)集上遠(yuǎn)大于在Netflix-s數(shù)據(jù)集上。也就是說PopularRec算法在Movielens- 100k數(shù)據(jù)集上能夠有效地進(jìn)行Top-N推薦，在Netflix-s數(shù)據(jù)集上卻不能。

圖2展示了除PopularRec算法外，其他3種算法在兩個數(shù)據(jù)集上的不同推薦列表長度的性能對比。

表2 PopularRec算法在兩個數(shù)據(jù)集上的性能對比

圖2 不同算法在兩個數(shù)據(jù)集上的性能

從圖2中可以看出，同一種算法，不同推薦列表長度的NDCG值不同，推薦列表長度越長，NDCG值越大。都是基于修正的SVD++評分規(guī)則，不同算法在相同推薦列表長度下的NDCG值不同，列表級SVD++算法的NDCG值在兩個數(shù)據(jù)集上都明顯高于點級SVD++算法。在Netflix-s數(shù)據(jù)集上和推薦列表長度為5的時候，列表級SVD++算法和點級SVD++算法的NDCG值差異更為顯著。本文算法相比列表級SVD++算法，不同推薦列表長度的NDCG值都有所提升，具體提升程度如表3所示。

表3 本文算法較列表級SVD++算法的性能提升程度 %

3.2.2 評分規(guī)則包括待評分物品與否對算法的影響

圖3是在MovieLens- 100k數(shù)據(jù)集上，評分規(guī)則中的用戶有過行為的物品集合中是否包括待評分物品對點級SVD++算法和本文算法的性能影響(N=10)。圖3中后綴為ex的表示不包括待評分物品，in表示包括待評分物品。

從圖3中可以看出是否包括待評分物品對本文提出算法的影響不大，兩者曲線基本重合。這種情況下，應(yīng)盡量避免信息泄露帶來的影響，保證評分規(guī)則在兩個階段保持一致，選擇不包括待評分物品更加合理。而對于點級SVD++算法，盡管包括待評分物品會導(dǎo)致兩個階段預(yù)測規(guī)則的不一致，但是從實驗結(jié)果看來，算法性能反而更好。隨著隱語義因子維度增大，兩種算法性能都有所提升。

圖3 算法在不同隱語義因子維度的性能

3.2.3 伸縮系數(shù)α大小對本文算法的影響

圖4展示了推薦列表長度為10，本文算法性能在兩個數(shù)據(jù)集上，隨著伸縮系數(shù)α增大的性能趨勢變化。從圖4中可以看到，隨著α增大，算法性能在MovieLens數(shù)據(jù)集上逐漸下降，而在Netflix數(shù)據(jù)集上性能有微小的提升。α的取值跟具體數(shù)據(jù)集有關(guān)。

圖4 本文算法在不同伸縮系數(shù)α的性能(N=10)

4 結(jié)語

針對SVD++算法預(yù)測規(guī)則和ListRank-MF算法Top- 1排序概率存在的問題，本文提出了一種結(jié)合物品流行度的列表級矩陣因子分解算法。實驗結(jié)果表明本文算法的Top-N推薦準(zhǔn)確率優(yōu)于點級SVD++算法和列表級SVD++算法，同時說明了排序?qū)W習(xí)中的列表級方法更加接近Top-N推薦的本質(zhì)，以及物品流行度對用戶選擇的影響。該方法僅僅只使用了用戶對物品的評分信息，沒有考慮用戶和物品的邊信息(side information)。下一步的工作將研究在矩陣因子分解算法的基礎(chǔ)上如何有效地利用邊信息，以及關(guān)注神經(jīng)網(wǎng)絡(luò)在推薦領(lǐng)域的最新研究。