融合顯/隱式反饋的社會化協同排序推薦算法

李 改，李 磊，張佳強

（1.順德職業技術學院智能制造學院，廣東佛山 528333；2.中山大學計算機學院，廣州 510006）

（?通信作者電子郵箱ligai999@126.com）

0 引言

隨著人類進入信息化社會，特別是移動互聯網和社交網絡的出現，互聯網上的信息量呈指數級爆炸式增長，人們越來越難以從互聯網上迅速找到所需要的信息。傳統的檢索系統對每個用戶的關鍵詞檢索都返回相同的結果，而推薦系統可根據用戶的個人偏好來更準確地推薦相關信息，因此在互聯網工業界得到了廣泛應用。

信息推薦系統中協同過濾推薦算法是目前應用最成功且最廣泛的信息推薦算法。隨著社交網絡的興起，出現了社會化協同過濾推薦算法。根據所采用的機器學習方法的不同，社會化協同過濾推薦算法分為兩種［1］：一種是基于評分預測的社會化協同過濾推薦算法，一種是基于排序預測的社會化協同排序推薦算法。相關研究表明：基于排序學習的社會化推薦算法沒有基于評分預測的社會化協同過濾推薦算法所具有的預測值與真實排序不匹配的固有缺陷；同時，由于不以預測評分作中介，而是直接通過排序學習對推薦對象進行排序推薦，因此具有更直接的實際應用價值［1-3］。

在處理顯式評分的社會化協同排序推薦算法中，代表性的有Yao 等［5］在國際頂級會議WWW2014 上提出的SoRank 模型。此外，隨著深度學習的應用與發展，也出現了一些學者采用深度學習來研究處理顯式評分的社會化協同排序推薦算法，均顯著提高了該類推薦算法的性能［6-7］。在基于隱式反饋的社會化協同排序推薦算法研究領域，Du 等［8］在國際會議ADMA2011 上提出了UGPMF（User Graph regularized Pairwise Matrix Factorization）模型，Krohn-Grimberghe 等［9］在國際會議WSDM2012 上 提 出 了 MR-BPR（Multi-Relational matrix factorization using Bayesian Personalized Ranking）模型，Zhao等［10］在國際會議ICKM2014 上提出了SBPR（Social Bayesian Personalized Ranking）模型。此類算法的最新模型是Guo等［11］在國際權威期刊《Journal of Computer Science and Technology》上提出的SocialBPR 模型。上述基于隱式反饋的社會化協同排序模型均是基于矩陣分解的貝葉斯個性化排序（Bayesian Personalized Ranking based on Matrix Factorization，BPR-MF）模型的改進版本，其目標函數均是優化排序學習的評價指標受試者工作特性曲線下面積（Area Under Receiver Operating Characteristic curve，AUC）。

傳統的基于排序預測的社會化協同排序推薦算法要么僅關注顯式反饋數據［5-7］，要么僅關注隱式反饋數據［8-11］，沒有充分挖掘這些數據的潛在價值。事實上，在真實的社會化信息推薦系統中，評分矩陣和社交網絡矩陣中的顯式反饋數據和隱式反饋數據是同時存在的。為了同時挖掘用戶評分矩陣和社交網絡矩陣中的顯/隱式信息，Guo 等［12］提出了TrustSVD 模型，該模型通過改進SVD++模型來同時挖掘用戶評分矩陣和社交網絡矩陣中的顯/隱式信息。由于該模型仍然是評分預測算法，因此同樣存在預測值與真實排序不匹配的固有缺陷［4］。為了克服固有缺陷，同時進一步提高社會化推薦算法的推薦性能，本文在TrustSVD 模型和xCLiMF 模型［13］基礎上，提出一種新的優化排序學習評價指標預期倒數排名（Expected Reciprocal Rank，ERR）的融合顯/隱式反饋的社會化協同排序推薦算法SPR_SVD++，以同時挖掘用戶評分矩陣和社交網絡矩陣中的顯/隱式反饋信息。實驗結果表明，SPR_SVD++算法的歸一化折損累計增益（Normalized Discounted Cumulative Gain，NDCG）和ERR 指標［1-2］均優于對比的最新的融合顯/隱式反饋信息的推薦算法，且適合處理大數據，可廣泛應用于互聯網服務中的個性化信息推薦。

1 預備知識

本文用斜體加粗的大寫字母（如：X）表示矩陣，用小寫字母（如：i，j）表示標量。給定矩陣X，Xij表示它的一個元素，X.j和Xi.分別表示X的第j列、第i行，XT表示X的轉置。如X表示顯式評分矩陣，則Xij∈{0，1，2，3，4，5}，該矩陣具有m個用戶、n個對象；表示X的逼近/預測矩陣，V∈Cd×n，一般d?r，r表示X的秩，r≤min(m，n)，U和V分別表示用戶和推薦對象的顯式特征矩陣，d表示特征個數。Pui表示用戶u的推薦對象i的排序得分。如X表示隱式評分矩陣，則，U和Y分別表示用戶和推薦對象的隱式特征矩陣。

T=(Tuv)m×m表示有m個用戶的社交網絡矩陣，Tuv∈{0，1}，“1”表示用戶u信任用戶v，“0”表示不信任。u信任v并不意味著v信任u，也就是說T是不對稱的。表示T的逼近/預測矩陣，，U∈Cd×m，W∈Cd×m，U和W分別表示信任者特征矩陣和被信任者特征矩陣。為了在本模型中統一優化用戶評分矩陣和社交網絡矩陣，假定用戶特征矩陣和信任者特征矩陣共享相同的特征空間，均用U表示，U∈Cd×m，因此。信任者的特征矩陣U和被信任者的特征矩陣W可以通過最小化以下目標函數［1］得到：

其中：T(u)表示用戶u直接信任的用戶的集合。

2 TrustSVD算法

TrustSVD 算法是一種融合顯/隱式反饋的基于評分預測的社會化協同過濾推薦算法，其核心思想是在SVD++模型［14］基礎上融入用戶的社交網絡信息，從而使TrustSVD 算法成為同時融合社交網絡和評分矩陣的顯/隱式信息的基于評分預測的協同過濾推薦算法。文獻［12］中的實驗結果顯示：TrustSVD 算法的性能優于其他已知的融合顯/隱式反饋的協同過濾推薦算法。在TrustSVD 算法中，逼近/預測矩陣中評分項的預測公式如下：

有關TrustSVD算法的詳細描述見文獻［12］。

3 SPR_SVD++算法

本章首先對SPR_SVD++算法進行詳細描述，接著給出該算法完整的求解過程和偽代碼，最后對新算法的時間復雜度進行全面分析。

3.1 算法介紹

在實際的應用中，人們更關注的是推薦對象之間的偏序關系，因此在基于排序預測的協同排序推薦算法能夠更好地滿足用戶的實際需要。xCLiMF 模型是一種處理顯式評分數據的基于排序預測的協同排序推薦算法［13］，其核心思想是在目標函數中優化排序學習的評價指標ERR。文獻［13］中的實驗結果顯示：xCLiMF 模型的性能優于目前已知的優化其他評價指標的基于排序預測的協同排序推薦算法。由于xCLiMF模型優化的是評價指標ERR，使得求解過程易于并行化，計算復雜度與評分矩陣中評分點的總數成正比，非常適合處理大規模數據（詳見文獻［13］和本文3.3 節的算法復雜度分析），因此本文提出的SPR_SVD++算法的核心思想是把TrustSVD算法融入xCLiMF模型，進而形成一種新的優化排序學習指標ERR的基于排序預測的社會化協同排序推薦算法。

在xCLiMF 模型中，用于評價對用戶u所產生的推薦序列的ERRu公式如下所示：

鑒于對數函數的單調性，最大化式（3）所得到的模型參數和最大化一致。因此，可得到如下公式：

和文獻［13］中一樣，運用Jensen 不等式和對數函數的凹性，得到的下限如下：

考慮全部m個推薦對象，SPR_SVD++算法的目標函數變形為：

最大化目標函數（7）等價于最小化公式（8）：

至此，相比目標函數（3），目標函數（8）簡化了很多，可以運用傳統的梯度下降法求解參數bu，bi，U，V，Y和W。

采用TrustSVD 算法中一樣的方法，假定用戶特征矩陣和信任者特征矩陣共享相同的特征空間，均用U表示，因此可以應用信任者的特征向量和被信任者的特征向量來約束用戶的特征向量。得到新目標函數如下：

其中：UuTWv是用戶u對用戶v的預測信任值，UpTWu是用戶p對用戶u的預測信任值；α∈[0，1]，用于控制信任者對最終評分的影響。

采用和參考文獻［12］一致的策略，并引入加權的λ規范化。目標函數（9）變形為：

其中：λ是正則化系數，為了降低模型復雜度，在這里對所有參數bu、bi、U、V、Y和W采用一樣的正則化系數；δ(x)是一個指示函數，當x＞0 時值為1，否則值為0；‖Uu‖F表示Uu的Frobenius 范數；U(i)表示給推薦對象i評分過的用戶集合；在這里采用|I(u)|、T(u)+和T(u)-同時約束用戶的特征向量Uu。

3.2 新算法優化求解與偽代碼描述

采用和參考文獻［1-3］一樣的策略，得到bu、bi、U、V、Y和W的求偏導公式如下：

SPR_SVD++算法的偽代碼描述詳見算法1。

算法1 SPR_SVD++算法。

輸入 評分矩陣X，社交矩陣T，學習率β，正則化參數λ，信任規范化參數λT，折中控制參數α，特征數d，最大迭代輪數itermax；

輸出 評分偏差bu和bi，特征矩陣U、V、Y和W。

3.3 算法計算復雜度分析

4 實驗結果及分析

4.1 實驗數據集

在本實驗中，一共使用3 個數據集：Epinions 數據集、Flixster 數據集和Ciao 數據集。數據集的具體說明詳見參考文獻［1，12］。

4.2 實驗的評價標準

本文采用NDGG 和ERR 作為實驗評價指標，具體定義詳見參考文獻［1-2］。

4.3 實驗設置

采用和文獻［1-2］類似的策略，針對3 個數據集，對每個用戶給出條件：“Given 20”“Given 40”“Given 60”作為訓練集，剩下的用作測試。

所有模型的最優參數值均分別確定。對每個數據集的不同條件數據子集，對實驗中的所有模型均用訓練數據集和五折交叉確認來確定模型參數。對于SPR_SVD++算法，和參考文獻［15］一樣，λT和α的最優值通過交叉確認確定。學習率β∈{χ|χ=0.000 1× 2c，χ≤0.5，c＞0，c是一個正整數}，通過實驗找出最優值。其他參數的設置均參照參考文獻［1］中的設置。對比算法的參數設置詳見相應的參考文獻。

4.4 實驗結果及分析

4.4.1 信任規范化參數λT對SPR_SVD++算法性能的影響

除了參數λ以外，SPR_SVD++算法還有兩個重要參數λT和α。為了確定算法中這兩個算法的最優值，采取的策略是固定其中一個參數，尋找另一個的最優值。找到最優值后把該最優值固定，以尋找下一個參數的最優值。圖1 給出了信任規范化參數λT對SPR_SVD++算法性能的影響，此時：固定α=0.5，同時λT∈{0.01，0.1，1，2，5，10}，其中縱軸表示評價指標NDCG@10 的值，橫軸表示信任規范化參數λT的值。采用Epinions 的子數據集“Given 40”作為實驗數據集。從圖1可以看出：SPR_SVD++算法的性能隨著信任規范化參數λT值的變化而變化；當SPR_SVD++算法的性能最佳時，λT=0.1；在SPR_SVD++算法中引入用戶的信任網絡信息，有助于提高該類推薦算法的性能。

圖1 λT對SPR_SVD++算法性能的影響Fig.1 Influence of λT on performance of SPR_SVD++algorithm

4.4.2 折中控制參數α對SPR_SVD++算法性能的影響

圖2給出了折中控制參數α對SPR_SVD++算法性能的影響，其中縱軸表示評價指標NDCG@10 的值，橫軸表示折中控制參數α的值。本實驗仍然選擇Epinions 數據集的子數據集“Given 40”作為實驗數據集。根據圖1顯示的實驗結果，此時固 定λT=0.1。α取值范圍為：α∈{χ|χ=0.1×c，0 ≤c≤10，c是一個整數}。α=1 表示僅僅考慮被用戶u信任的用戶們對的影響，忽略信任u的用戶對的影響；α=0則正好相反，表示僅僅考慮信任u的用戶對的影響，忽略被用戶u信任的用戶們對的影響；取α∈(0，1)正是為了平衡這兩種極端情況。從圖2可觀察到：當α=0時SPR_SVD++算法的性能優于當α=1 時的性能，這說明在SPR_SVD++算法中，信任者對算法性能的影響高于被信任者；當α=0 和α=1 時的算法性能均遜于α∈(0，1)時，這說明折中考慮信任者和被信任者對算法性能的影響，能夠進一步提高SPR_SVD++算法的性能。

圖2 α對SPR_SVD++算法性能的影響Fig.2 Influence of α on performance of SPR_SVD++algorithm

4.4.3 SPR_SVD++算法和經典協同過濾推薦算法的比較

考慮公平性，在3 個數據集上對比了本文的SPR_SVD++算法與3個經典的同時融入用戶評分矩陣的顯/隱式反饋的推薦算法，結果如圖3。對比算法為：

圖3 SPR_SVD++算法與其他經典協同過濾推薦算法的性能比較Fig.3 Performance comparison of SPR_SVD++algorithm and other classic collaborative filtering algorithms

TrustSVD［12］：這是目前最新的基于評分預測的融合顯/隱式反饋的社會化推薦算法，其核心思想是擴展SVD++算法，以融入用戶的社交網絡信息。

MERR_SVD++［3］：這是目前最新的基于排序預測的融合顯/隱式反饋的協同排序推薦算法，其核心思想是在改進xCLiMF 算法的基礎上同時融入用戶評分矩陣的顯/隱式反饋信息，優化排序學習的評價指標ERR。

SVD++［14］：該算法是最基礎的融合用戶顯/隱式反饋信息的推薦算法，其核心思想是擴展SVD 模型以融入用戶的顯/隱式反饋信息。

從圖3 可以看出，在3 個社會化數據集的各種條件子集下，SPR_SVD++算法的性能均遠優于TrustSVD、MERR_SVD++和SVD++算法，且隨著用戶評分數據量的增長，算法性能提高越顯著；SPR_SVD++算法的性能優于TrustSVD，說明優化排序學習的評價指標ERR 能夠有效克服TrustSVD 的固有缺陷，進一步提高融入用戶評分矩陣的顯/隱式反饋的推薦算法的性能；且兩個評價指標NDCG@10和ERR@10的性能走勢圖趨于一致，這說明SPR_SVD++算法優化排序學習的評價指標ERR 并不影響采用NDCG@10 作為評價指標的算法性能；隨著特征數的增加，SPR_SVD++算法的性能也線性提高，這說明在本算法中訓練數據的增加能夠訓練出更高精度的預測模型。

5 結語

本文在xCLiMF 模型和TrustSVD 模型的基礎上，提出了一種新的優化排序學習評價指標ERR 的融合顯/隱式反饋的社會化協同排序推薦算法SPR_SVD++。在真實的數據集上的實驗結果表明，SPR_SVD++算法的性能優于對比的最新的該類推薦算法，且具有很好的可擴展性，因此，在面向海量數據處理的互聯網工業界具有廣泛的應用前景。