融合顯/隱式反饋的社會(huì)化協(xié)同排序推薦算法

李 改，李 磊，張佳強(qiáng)

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

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

0 引言

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

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

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

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

1 預(yù)備知識(shí)

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

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

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

2 TrustSVD算法

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

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

3 SPR_SVD++算法

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

3.1 算法介紹

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

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

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

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

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

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

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

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

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

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

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

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

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

SPR_SVD++算法的偽代碼描述詳見(jiàn)算法1。

算法1 SPR_SVD++算法。

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

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

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

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

4.1 實(shí)驗(yàn)數(shù)據(jù)集

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

4.2 實(shí)驗(yàn)的評(píng)價(jià)標(biāo)準(zhǔn)

本文采用NDGG 和ERR 作為實(shí)驗(yàn)評(píng)價(jià)指標(biāo)，具體定義詳見(jiàn)參考文獻(xiàn)［1-2］。

4.3 實(shí)驗(yàn)設(shè)置

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)語(yǔ)

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