李 改，李 磊，張佳強

（1.順德職業(yè)技術(shù)學(xué)院智能制造學(xué)院，廣東佛山 528333；2.中山大學(xué)計算機學(xué)院，廣州 510006）

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

0 引言

隨著人類進入信息化社會，特別是移動互聯(lián)網(wǎng)和社交網(wǎng)絡(luò)的出現(xiàn)，互聯(lián)網(wǎng)上的信息量呈指數(shù)級爆炸式增長，人們越來越難以從互聯(lián)網(wǎng)上迅速找到所需要的信息。傳統(tǒng)的檢索系統(tǒng)對每個用戶的關(guān)鍵詞檢索都返回相同的結(jié)果，而推薦系統(tǒng)可根據(jù)用戶的個人偏好來更準確地推薦相關(guān)信息，因此在互聯(lián)網(wǎng)工業(yè)界得到了廣泛應(yīng)用。

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

在處理顯式評分的社會化協(xié)同排序推薦算法中，代表性的有Yao 等［5］在國際頂級會議WWW2014 上提出的SoRank 模型。此外，隨著深度學(xué)習(xí)的應(yīng)用與發(fā)展，也出現(xiàn)了一些學(xué)者采用深度學(xué)習(xí)來研究處理顯式評分的社會化協(xié)同排序推薦算法，均顯著提高了該類推薦算法的性能［6-7］。在基于隱式反饋的社會化協(xié)同排序推薦算法研究領(lǐng)域，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］在國際權(quán)威期刊《Journal of Computer Science and Technology》上提出的SocialBPR 模型。上述基于隱式反饋的社會化協(xié)同排序模型均是基于矩陣分解的貝葉斯個性化排序（Bayesian Personalized Ranking based on Matrix Factorization，BPR-MF）模型的改進版本，其目標函數(shù)均是優(yōu)化排序?qū)W習(xí)的評價指標受試者工作特性曲線下面積（Area Under Receiver Operating Characteristic curve，AUC）。

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

1 預(yù)備知識

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

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

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

2 TrustSVD算法

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

有關(guān)TrustSVD算法的詳細描述見文獻［12］。

3 SPR_SVD++算法

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

3.1 算法介紹

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

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

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

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

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

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

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

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

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

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

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

3.2 新算法優(yōu)化求解與偽代碼描述

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

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

算法1 SPR_SVD++算法。

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

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

3.3 算法計算復(fù)雜度分析

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

4.1 實驗數(shù)據(jù)集

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

4.2 實驗的評價標準

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

4.3 實驗設(shè)置

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

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

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

4.4.1 信任規(guī)范化參數(shù)λT對SPR_SVD++算法性能的影響

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

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

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

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

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

4.4.3 SPR_SVD++算法和經(jīng)典協(xié)同過濾推薦算法的比較

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

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

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

MERR_SVD++［3］：這是目前最新的基于排序預(yù)測的融合顯/隱式反饋的協(xié)同排序推薦算法，其核心思想是在改進xCLiMF 算法的基礎(chǔ)上同時融入用戶評分矩陣的顯/隱式反饋信息，優(yōu)化排序?qū)W習(xí)的評價指標ERR。

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

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

5 結(jié)語

本文在xCLiMF 模型和TrustSVD 模型的基礎(chǔ)上，提出了一種新的優(yōu)化排序?qū)W習(xí)評價指標ERR 的融合顯/隱式反饋的社會化協(xié)同排序推薦算法SPR_SVD++。在真實的數(shù)據(jù)集上的實驗結(jié)果表明，SPR_SVD++算法的性能優(yōu)于對比的最新的該類推薦算法，且具有很好的可擴展性，因此，在面向海量數(shù)據(jù)處理的互聯(lián)網(wǎng)工業(yè)界具有廣泛的應(yīng)用前景。