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

周瑞環，趙宏宇

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

0 引言

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

為了解決“信息過載”問題，在互聯網的發展過程中出現了分類目錄、搜索引擎、個性化推薦系統。個性化推薦系統主要用于預測一個用戶是否會喜歡一個特定的物品(評分預測問題)或者是為一個用戶推薦感興趣的N個物品[2](Top-N推薦問題)。協同過濾算法[3]是個性化推薦系統中應用最廣泛的算法。協同過濾算法主要的兩種技術分別是基于近鄰的算法和矩陣因子分解算法?；诮彽乃惴紤]的是用戶或物品之間的相似關系來解釋用戶對物品的評分。矩陣因子分解算法，考慮的是用戶和物品在隱語義空間中的隱語義因子特征來解釋用戶對物品的評分。相對于基于近鄰的算法，矩陣因子分解算法因其在稀疏數據集上的準確性和穩定性得到廣泛的關注。而隨著硬件的飛速發展和大數據時代的到來，基于深層神經網絡的算法在各個領域都被廣泛地研究?；谧詣泳幋a器的協同過濾算法[4]解決了評分預測問題?；诮翟胱詣泳幋a器的協同過濾算法[5]解決了Top-N推薦問題。神經協同過濾算法[6]提出了一個通用框架將矩陣因子分解算法和神經網絡結合到一起?；谏顚由窠浘W絡的推薦算法可以學習出用戶和物品之間的非線性關系，而不像矩陣因子分解算法只能學習用戶和物品潛在特征的點乘關系。然而，基于深層神經網絡的推薦算法網絡架構難以改變，也就難以結合其他的信息改進推薦效果。因而，矩陣因子分解算法仍是推薦系統的利器。

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

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

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

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

1 基本定義與算法描述

1.1 基本定義

(1)

1.2 SVD++算法

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

(2)

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

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

1.3 ListRank-MF算法

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

(3)

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

(4)

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

(5)

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

2 本文算法

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

(6)

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

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

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

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

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

(7)

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

接著，本文使用與ListRank-MF算法一樣的交叉熵構造目標函數。在加入正則化參數后，最終的目標函數如下：

(8)

不同于文獻[17]的方法，本文使用隨機梯度下降算法求解該最優化問題。隨機梯度下降算法有收斂速度快、時間復雜度低的優點。令：

(9)

則各參數的迭代計算公式如下：

(10)

其中：γ表示學習率；λ表示正則化系數。模型訓練階段算法偽代碼描述如下：

輸入：訓練數據集D，學習率γ，正則化系數λ，隱語義因子特征維數f，迭代次數T。

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

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

矩陣P、Q、Y的值隨機初始到區間(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)

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

3 實驗結果及分析

3.1 數據集和實驗設置

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

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

(11)

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

表1 實驗中使用的數據集

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

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

SVD++_rmse 基于修正的SVD++評分規則，使用點級目標函數，即實際評分與預測評分的平方誤差和，記為點級SVD++算法。

SVD++_ce 基于修正的SVD++評分規則，使用列表級目標函數，即實際評分分布和預測評分分布的交叉熵，記為列表級SVD++算法。

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

本文所有算法均在Windows操作系統下使用Python在Pycharm開發平臺上編寫，計算機配置為4核Intel Core i7處理器2.8 GHz、24 GB內存。

3.2 實驗結果

3.2.1 不同算法性能對比

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

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

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

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

表2 PopularRec算法在兩個數據集上的性能對比

圖2 不同算法在兩個數據集上的性能

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

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

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

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

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

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

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

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

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

4 結語

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