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

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

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

0 引言

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

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

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

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

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

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

1 基本定義與算法描述

1.1 基本定義

(1)

1.2 SVD++算法

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

(2)

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

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

1.3 ListRank-MF算法

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

(3)

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

(4)

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

(5)

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

2 本文算法

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

(6)

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

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

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

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

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

(7)

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

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

(8)

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

(9)

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

(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

計(jì)算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ù)測(cè)階段，根據(jù)式(8)為每個(gè)用戶計(jì)算其未評(píng)分物品排在列表第一個(gè)位置的概率。對(duì)于一個(gè)用戶的所有物品，式(8)分母部分是一樣的，因此只需要計(jì)算分子部分，選擇值最大的Top-N的物品即可。

3 實(shí)驗(yàn)結(jié)果及分析

3.1 數(shù)據(jù)集和實(shí)驗(yàn)設(shè)置

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

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

(11)

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

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

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

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

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

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

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

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

3.2 實(shí)驗(yàn)結(jié)果

3.2.1 不同算法性能對(duì)比

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

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

表2是PopularRec算法在兩個(gè)數(shù)據(jù)集上的不同推薦列表長(zhǎng)度的性能對(duì)比。從表2可以看出，PopularRec算法不穩(wěn)定，不同推薦列表長(zhǎng)度的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種算法在兩個(gè)數(shù)據(jù)集上的不同推薦列表長(zhǎng)度的性能對(duì)比。

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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