基于Pairwise排序學習的因子分解推薦算法

周俊宇　戴月明　吳定會

(江南大學物聯網工程學院　江蘇 無錫 214122)

?

基于Pairwise排序學習的因子分解推薦算法

周俊宇戴月明吳定會

(江南大學物聯網工程學院江蘇 無錫 214122)

摘要針對基于內存的協同過濾推薦算法存在推薦列表排序效果不佳的問題，提出基于Pairwise排序學習的因子分解推薦算法(簡稱Pairwise-SVD推薦算法)。新算法將因子分解的預測結果作為排序學習算法的輸入，把排序問題轉化成分類問題使用排序學習理論進行排序產生推薦列表。實驗結果表明相比基于內存的協同過濾推薦算法,Pairwise-SVD推薦算法的排序效果更佳。其在指標Kendall-tau上提高了近一倍，在指標MRR上提高了近30%，且在指標MAP上也有小幅提高。

關鍵詞Pairwise因子分解協同過濾分類排序學習

0引言

隨著大數據時代的到來，信息過載問題成為人們日益關注解決的難題。用戶迫切希望可以從海量數據當中發現對于自己有用的信息，針對這一需求研究人員提出了推薦系統這一研究課題。

推薦系統主要以推薦列表的形式給用戶推送信息也稱為Top-N推薦。基于內存的協同過濾推薦算法主要有基于用戶的協同過濾推薦算法和基于物品的協同過濾推薦算法。這類算法的特點是通過相似度計算來給用戶推送其可能感興趣的物品信息。不過這類算法也有排序效果不佳的不足，主要是其沒有考慮推薦物品與用戶的相關度。為提高推薦算法的預測精度，學術界對評分預測問題展開了大量的研究。其中典型的算法是以因子分解算法為代表的一系列改進算法。下面將介紹推薦系統領域的一些研究情況。

YueShi等[1]人提出了一種將排序學習融入矩陣分解的協同過濾推薦算法。其排序學習算法的類型是列表級排序，通過優化列表級排序的損失函數來進行算法的性能優化。不過這種算法雖然效果很好，但是它只從損失函數的角度進行優化所以這種算法的實用性不是很強。

SeanM.McNee等[2]人提出了新的觀點，即僅僅通過改良預測精度是不足以說明推薦效果的好壞。雖然基于評分預測的改進大大提高了評價指標的結果。但在實際的推薦系統中效果卻不明顯，因為用戶在實際情況下并不會真的喜歡預測精度高的物品。

YueShi等[3]人提出了CLiMF協同過濾推薦算法，該算法優化的主要目標是MRR。該指標反映了用戶最關心的物品在推薦列表中的排序位置，它是信息檢索領域中的重要指標。CLiMF算法在原來的協同推薦算法的基礎之上考慮了排序性能的優化問題，其在MRR指標上的表現較好。

ShuziNiu等[4]人提出了一種新的Top-N推薦算法，并將其命名為FocusedRank算法。該算法有效地降低了原有Top-N算法的時間復雜度，從O(n)降低為O(nlogn)。并且針對新的算法提出了新的評價準則k-NDCG和k-ERR。

雖然排序學習理論在信息檢索領域已經有了大量的研究成果，但是將排序學習理論用于推薦系統的研究卻少之又少。本文在前人工作的基礎之上展開，提出將Pairwise排序學習理論加入到因子分解推薦算法當中，并采用Rank-SVM方法具體實現Pairwise排序。最后通過在三種不同類型的排序指標上進行對比實驗來驗證本文提出的算法的性能優勢。

1理論基礎

這節主要闡述構成本文算法的理論基礎。主要從兩個方面進行介紹，分別是Bias-SVD算法、排序學習理論等內容。

1.1Bias-SVD算法

本文提出的Pairwise-SVD推薦算法借鑒了Bias-SVD推薦算法的思想。所以先簡要地闡述一下Bias-SVD算法的思想。

為了預測用戶物品評分矩陣當中的空缺項需要把評分矩陣進行分解，分解后的矩陣表示成如下的形式：

(1)

這里矩陣R代表的是用戶物品評分矩陣，P和Q是分解后的兩個降維矩陣，P矩陣代表的是用戶的特征，Q矩陣代表的是物品的特征。這里可以通過在訓練集的觀察值上利用最小化均方根誤差來學習P矩陣和Q矩陣[5]。通過這種方法可以把上述矩陣表示成如下的形式：

(2)

為了進一步提高預測精度，Bias-SVD算法在上面的矩陣分解的基礎之上加入了三個偏置項，把上面的公式改變成了如下的形式：

(3)

其中，μ表示訓練數據集當中評分的平均情況。因為不同的數據集評分分布情況有很大的不同。比如說有的數據集評分普遍偏高，而有的數據集評分普遍偏低。所以數據集的評分均值對預測有很大的干擾影響，這里為平衡該影響而引入評分均值這一項。

bu表示用戶的評分偏置項。由于不同用戶打分的尺度不相同，會造成對于同一物品相似用戶的打分產生巨大的偏差。例如有的用戶比較苛刻打分普遍偏低，而有的用戶尺度寬松打分普遍較高。通過加入這一偏置項就可均衡這種情況提高預測精度。

bi表示物品偏置項。該項表示物品的受歡迎程度，因為有的物品比較熱門所以評分一般都很高，而有的物品比較冷門打分普遍偏低。通過引入這一項可以懲罰熱門物品，并平衡冷門物品。

為了學習公式中的各個參數，使用最小二乘法來定義損失函數。得出Bias-SVD算法的損失函數如下所示：

(4)

在確定了損失函數之后可以通過隨機梯度下降法學習損失函數中的各參數。下面列出隨機梯度下降學習的策略：

bu←bu+γ·(eui-λ·bu)bi←bi+γ·(eui-λ·bi)pu←pu+γ·(eui·qi-λ·pu)qi←qi+γ·(eui·pu-λ·qi)

(5)

通過上面的學習策略就可以求得各個參數的結果。

1.2排序學習理論

所謂排序學習理論即將信息檢索領域中的排序問題轉化成機器學習問題，以此期望獲得更好的排序結果。一般的排序學習問題可用如圖1的流程來進行說明。

圖1　排序學習算法流程圖

從圖1可以看出排序學習是一種有監督學習，所以它需要訓練集來構造模型。舉例來說，在信息檢索的過程當中一個訓練集包含有n個查詢(在圖中用q1到qn表示)。相應的與查詢相關的文檔可以用x1到xm來表示。這里的m表示對于某一個查詢返回的文檔個數。圖中的模型的獲得可以通過一個具體的學習算法取得(比如組合特征方法)。通過這一學習算法可以使模型盡可能準確地預測出訓練集的標簽。在進行測試的時候只需要運用訓練好的模型就可以產生推薦列表。

根據輸入數據的格式不同，通常情況下排序學習算法主要分為三大類。有基于點的排序算法(Pointwise),基于對的排序算法(Pairwise)，基于列表的排序算法(Listwise)[6]。

本文所采用的排序方法屬于基于對的排序方法，故下面將主要闡述基于對的排序方法的主要思想和實現手段。

基于對的排序方法不關心單個文檔的順序，其主要關注的是文檔對的分類問題。也就是說基于對的排序方法把排序問題轉化為二元分類問題。如果每一個文檔對都能正確的分類那么也就可以得出正確的排列順序。所以基于對的排序方法的主要目標是盡可能快地縮小分類的誤差。

基于對的排序方法實現有很多的方法，比如神經網絡、感知器、boosting、Rank-SVM方法等。由于本文的排序學習方法通過Rank-SVM實現所以下面主要講解Rank-SVM方法的主要思路。

1.3Rank-SVM方法

Rank-SVM方法采用支持向量機模型解決分類問題。Rank-SVM方法在訓練數據集上構造數據樣本對S={(xi,xj),zi}，其中xi與xj表示針對某一個查詢返回的文檔。如果(xi,xj)是正樣本對則zi的值表示為+1，如果(xi,xj)是負樣本對則zi的值表示為-1。Rank-SVM方法的數學表達如下所示[7]：

(6)

從上面的數學公式可以看出Rank-SVM方法與一般的SVM方法非常接近。但所不同的是兩種方法的約束條件有一定的差別。SVM方法的約束條件是基于單個的樣本點構造的，而Rank-SVM方法的約束條件基于樣本對構造。并且Rank-SVM方法的損失函數定義為樣本對上的Hinge損失。舉例來說，有一個查詢q，如果其標簽當中的文檔xu比xv相關。并且如果兩條支持向量的最大間隔大于1，還滿足條件wTxu>wTxv的條件，則其損失函數為0，否則為Hinge損失的0到1的上界。

圖2、圖3用通俗的方法說明Rank-SVM方法的基本思想。

圖2　針對某一個用戶的查詢　　圖3　基于成對排序的Rank-SVM分類

圖2中的橢圓形表示一個用戶的查詢，這里我們選取一個用戶的查詢做成對排序(在推薦系統里這可以看作是針對一個用戶的推薦列表)。

圖3表示將一個用戶的查詢信息轉化成成對信息后用Rank-SVM分類的結果。這里有兩個類別+1和-1。其中+1代表正相關，-1代表負相關。舉例來說(X3-X1)表示這個數據分類為-1也就是負相關，也就是說用戶不希望X3文檔排列在X1文檔的前面。所以文檔對(X1-X3)分類為+1就是正相關。

2Pairwise-SVD算法

2.1算法描述

本文提出的算法在Bias-SVD算法的基礎之上進行改進，把只能處理單個數據的Bias-SVD算法改造成可以處理成對數據的Pairwise-SVD算法。

這樣接下來就可以把Bias-SVD算法的評分預測公式進行如下的改造：

(7)

這里簡要解釋一下上面的數學公式的含義。公式的左半部分表示的是一個偏序關系，即對于用戶u我們把物品i排列在物品j的前面這樣的一個偏序關系[8]。等式的右邊是改造的打分函數，即針對這樣的偏序關系依照等式右邊的方法進行打分。在等式的右邊添加sigmoid函數是為了做歸一化處理，使最終的打分函數的取值落在-1到1之間。

下面闡述一下Pairwise-SVD算法的具體執行步驟：

(1) 我們要把數據集中的數據進行Pairwise化處理，因為只有這樣才能進行后續的工作。

(2) 將Pairwise化后的數據集進行分割，分割為訓練集合測試集。

(3) 在訓練集上利用隨機梯度下降算法訓練Pairwise-SVD算法的模型。

(4) 判斷模型訓練是否終止不終止則返回步驟(3)。

(5) 如果訓練終止，在測試集上面測試訓練好的模型的效果。

(6) 如果訓練好的模型的效果達標，用該模型產生的信息作為Rank-SVM方法的輸入。

(7) 訓練Rank-SVM模型。

(8) 判斷Rank-SVM模型訓練是否終止如不終止返回步驟(7)。

(9) 利用Rank-SVM方法進行排序產生推薦列表。

(10) 評估推薦效果的好壞情況。

2.2Pairwise-SVD算法程序流程圖

下面我們通過一個流程圖詳細講述Pairwise-SVD算法在計算機當中執行的每一個步驟。如圖4所示。

圖4　算法程序流程圖

3實驗驗證

3.1實驗用數據集

本文實驗所采用的數據集是GroupLens研究小組的MovieLens100KB數據集。該數據集包含943個用戶對于1682部電影的評分數據。并且每名用戶至少評價20部以上的電影。

3.2評價指標

本文主要采用三種基于排序的評價指標評價推薦效果的好壞。它們分別是Kendall-tau，MRR和MAP。

其中Kendall-tau評價指標用于比較用戶喜歡的物品列表與推薦給用戶的物品列表的關系。Kendall-tau指標越高說明推薦的物品與用戶喜歡的物品越相關。

(8)

指標MRR表示在列表中越早出現的物品其權重越高。指標MRR的高低說明了越早出現用戶喜歡的物品的概率大小。MRR越高說明推薦列表的前幾項就是用戶感興趣的物品(因為習慣上用戶只關注列表的前幾項內容)。

(9)

指標MAP稱為平均準確度，衡量用戶喜歡的物品在列表中出現的頻度。同樣的越早出現在列表中的物品其權重越高。

(10)

3.3對比實驗

在這里設計三組對比實驗分別展示三種算法在這三個評價指標上的優劣程度。

需要說明的是與本文算法進行對比的算法是基于用戶的協同過濾推薦算法(UserCF)和基于物品的協同過濾推薦算法(ItemCF)。

3.3.1第一組對比實驗

在第一組對比實驗中我們比較三種算法在指標MRR上的優劣程度。這里我們隨機給不同的用戶推薦不同數量的物品以此來比較三種算法的情況(用5作為物品列表增加的迭代步長)。

實驗的結果通過圖5的柱狀分析統計圖來進行展示。

通過上面的柱狀分析圖可以得出這樣的結論。Pairwise-SVD算法在指標MRR上其效果要好于基于物品的協同過濾算法和基于用戶的協同過濾算法。其中在推薦列表長度為10的時候效果最明顯(性能提高約30%左右)，而這個長度往往是一般推薦系統所選取的給用戶推薦的物品數量。

3.3.2第二組對比實驗

在這組實驗中我們關注三種算法在指標Kendall-tau上的性能情況。同上一組實驗一樣我們隨機選取幾個用戶進行推薦，設定不同長度的推薦列表(長度從5到12)。比較在不同長度的列表下Kendall-tau值的大小。實驗的結果如圖6的折線統計圖所示。

圖6　三種算法在Kendall-tau上的比較

通過上面的折線圖可以看出Pairwise-SVD算法在指標Kendall-tau上要明顯好于另外的兩種算法。這說明由Pairwise-SVD算法產生的推薦列表其用戶的興趣與物品之間的相關度更高。

3.3.3第三組對比實驗

在這一組實驗當中比較三種算法在指標MAP上的結果。并通過表1來展示，其中N代表推薦給用戶的物品數量。

表1　三種算法在MAP上的比較

通過上面表格中的數據，可以得出這樣的結論。即Pairwise-SVD算法在MAP指標上相比另外的兩種算法也有一定的優勢。說明Pairwise-SVD算法所推薦的物品準確度與覆蓋效果更好。

4結語

本文在前人工作的基礎之上提出了基于Pairwise排序學習的因子分解推薦算法。把原本只適用于預測精度的因子分解推薦算法改造成為適合產生推薦列表的推薦算法。并通過實驗將該算法與基于內存的協同過濾推薦推薦算法進行對比。在三個評價指標上都取得了比較好的效果。此外加入了Rank-SVM方法把排序問題轉化為機器學習問題使得列表排序更加智能化。本文的工作也為其他的機器學習算法融入推薦算法當中做了很好的鋪墊。

在未來的工作中我們將把其他的分類算法比如神經網絡算法等內容用于進行排序學習，并在多維特征的情況下進行測試來驗證其效果。未來將進一步深化排序學習與推薦系統領域的交叉研究。

參考文獻

[1]YueShi,MarthaLarson,AlanHanjalic.List-wiseLearningtoRankwithMatrixFactorizationforCollaborativeFiltering[C]//Recys’10.Barcelona,Spain:ACM,2010.

[2]SeanMMcNee,JohnRiedl,JosephAKonstan.BeingAccurateisNotEnough:HowAccuracyMetricshavehurtRecommendersystem[C]//Montreal.Quebec,Canada:ACM,2006.

[3]YueShi,AlexandrosKaratzoglou,LinasBaltrunas.CLiMF:LearningtoMaximizeReciprocalRankwithCollaborativeLess-is-MoreFiltering[C]//Dublin,Ireland:Recsys’12,2012.

[4]ShuziNiu,JiafengGuo,YanyanLan,etal.Top-kLearningtoRank:Labeling,RankingandEvaluation[C]//Portland,Oregon,USA:SIGIR’12,2012.

[5] 項亮.推薦系統實踐[M].北京:人民郵電出版社,2012.

[6] 林原,林鴻飛,蘇綏.一種應用奇異值分解的Rankboost排序學習方法[C]//中國山東煙臺,第十屆全國計算語言學學術會議,2009.

[7] 丁偉民.排序學習中的RankingSVM算法研究 [J].科技視界,2013(30):84-138.

[8]ChenT,ZhangW,LuQ.SVDFeature:AToolkitforFeature-basedCollabrativeFiltering[C]//Toappearinthe30thInternationalConferenceonMachineLearningResearch,2012:3585-3588.

FACTORISATION RECOMMENDATION ALGORITHM BASED ONPAIRWISERANKINGLEARNING

Zhou JunyuDai YuemingWu Dinghui

(School of Internet of Things,Jiangnan University,Wuxi 214122,Jiangsu,China)

AbstractMemory-based collaborative filtering recommendation algorithm has the problem of poor recommendation list ranking effect, in light of this, we presented a new kind of factorisation recommendation algorithm which is based on Pairwise ranking learning, namely the Pairwise-SVD recommendation algorithm. The new algorithm uses the predictive result of factorisation as the input of ranking learning algorithm, in this way, it converts the ranking problem into a classification problem and then uses the ranking learning theory to rank and generates a recommendation list. Experimental results showed that, compared with the memory-based collaborative filtering recommendation algorithm, the Pairwise-SVD recommendation algorithm had better ranking effect. What’s more, it almost doubled the index of Kendall-tau, and improved about 30% in index of MRR, and reached a small improvement in the index of MAP as well.

KeywordsPairwiseFactorisationCollaborative filteringClassificationRanking learning

收稿日期：2015-01-18。國家高技術研究發展計劃項目(2013AA 040405)。周俊宇，碩士生，主研領域：數據挖掘與推薦系統。戴月明，副教授。吳定會，副教授。

中圖分類號TP3

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.06.061