一種聯(lián)合LTR和社交網(wǎng)絡(luò)的Top-k推薦方法

熊麗榮，王玲燕，黃玉柱

1(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，杭州 310023)2(浙江理工大學(xué)，杭州 310018)

1 引 言

推薦系統(tǒng)可以有效地應(yīng)對(duì)信息爆炸問題，越來越多的研究者將其作為學(xué)術(shù)研究的重點(diǎn)[1].大量研究利用用戶-項(xiàng)目評(píng)分矩陣預(yù)測每個(gè)用戶對(duì)每個(gè)項(xiàng)目的評(píng)分值，這些工作致力于提高全局評(píng)分預(yù)測精度即降低評(píng)分預(yù)測誤差值，MAE和RMAE[2].推薦系統(tǒng)的最終目的是為目標(biāo)用戶提供一個(gè)排序的項(xiàng)目列表，但最小化評(píng)分預(yù)測值并不總能得到較好的top-k列表[3，4].因此，本文更關(guān)注于基于top-k的推薦[5]而不是基于評(píng)分預(yù)測的推薦.

如何為用戶產(chǎn)生一個(gè)排序的項(xiàng)目列表被認(rèn)為是Learning-To-Rank (LTR)[7]類問題，可以采用監(jiān)督式的機(jī)器學(xué)習(xí)方法，從訓(xùn)練數(shù)據(jù)中得到用戶特征信息，從而產(chǎn)生推薦結(jié)果.用戶-項(xiàng)目評(píng)分矩陣是top-k推薦系統(tǒng)中至關(guān)重要的內(nèi)容，然而，在現(xiàn)實(shí)生活中用戶往往只會(huì)購買、評(píng)分小部分項(xiàng)目，這導(dǎo)致了top-k推薦系統(tǒng)由于缺少評(píng)分?jǐn)?shù)據(jù)而不能產(chǎn)生較準(zhǔn)確的推薦結(jié)果.另一方面相比于推薦系統(tǒng)產(chǎn)生的推薦結(jié)果，用戶更傾向于朋友推薦的項(xiàng)目.將社會(huì)化網(wǎng)絡(luò)中用戶間的信任信息結(jié)合到top-k推薦算法當(dāng)中可以緩解數(shù)據(jù)稀疏問題的同時(shí)提高用戶對(duì)推薦結(jié)果的接受度.

本文結(jié)合社交網(wǎng)絡(luò)信息，提出一種基于LTR的top-k推薦算法，BTRank相比較于已有的工作，本文有如下幾個(gè)重要貢獻(xiàn)：

1) 提出了一種新的信任計(jì)算模型，可以對(duì)信任信息做預(yù)處理，從全局、局部等多個(gè)方面挖掘用戶間的潛在信任信息；

2) 考慮用戶興趣會(huì)隨著時(shí)間發(fā)生變化，設(shè)計(jì)了時(shí)間衰減效應(yīng)模型，根據(jù)時(shí)間對(duì)用戶的評(píng)分?jǐn)?shù)據(jù)進(jìn)行處理；

3) 綜合考慮用戶對(duì)項(xiàng)目排序以及對(duì)信任用戶排序時(shí)展現(xiàn)出來的興趣偏好信息，構(gòu)建用戶特征矩陣，最終得到top-k推薦列表.實(shí)際數(shù)據(jù)集上的實(shí)驗(yàn)表明，本文的算法效果優(yōu)于傳統(tǒng)推薦算法以及同類的top-k推薦算法.

本文第2章闡述了相關(guān)工作.第3章詳細(xì)介紹了本文提出的算法BTRank.第4章分析了本文算法的復(fù)雜性.第5章給出了實(shí)驗(yàn)與結(jié)果分析.最后第6章總結(jié)全文并指出未來的進(jìn)一步工作.

2 相關(guān)工作

2.1 推薦系統(tǒng)

個(gè)性化推薦系統(tǒng)很好地滿足了用戶對(duì)個(gè)性化服務(wù)的需求，目前比較成熟的個(gè)性化推薦算法包括協(xié)同過濾推薦算法、基于內(nèi)容的推薦算法及混合推薦算法三大類.

基于內(nèi)存的協(xié)同過濾通過使用皮爾遜系數(shù)[12]等方式來計(jì)算用戶間的相似度，并利用相似度過濾出近鄰集合，最后基于這些近鄰產(chǎn)生推薦結(jié)果.基于模型的協(xié)同過濾算法通過訓(xùn)練得到相應(yīng)的特征模型，在數(shù)據(jù)稀疏情況下算法效果優(yōu)于內(nèi)存類協(xié)同過濾算法.矩陣分解可以將一個(gè)高維矩陣分解為兩個(gè)低維特征矩陣的乘積，達(dá)到預(yù)測原矩陣空缺數(shù)據(jù)的效果，并且這兩個(gè)特征矩陣的維度取值遠(yuǎn)遠(yuǎn)小于原矩陣的維度，因此在眾多的模型類協(xié)同過濾算法中[17，25，26，30]矩陣分解是被最廣泛使用的.本文的算法BTRank中也采用了矩陣分解方法.

基于內(nèi)容的推薦算法[13]根據(jù)產(chǎn)品的特征描述和用戶的購買歷史信息，向用戶推薦與他們購買過的產(chǎn)品有著類似特性的產(chǎn)品.一般適用于文本類的推薦，如新聞推薦、閱讀推薦等.基于內(nèi)容的推薦算法推薦結(jié)果過度單一，導(dǎo)致目標(biāo)用戶經(jīng)常得到與曾經(jīng)喜歡的項(xiàng)目類似的其他項(xiàng)目，推薦結(jié)果缺少多樣性.

混合過濾算法將多種個(gè)性化推薦算法進(jìn)行融合[14，15]，然而目前還是不能很好的將協(xié)同過濾推薦和基于內(nèi)容的推薦算法進(jìn)行擬合，并且算法的時(shí)間復(fù)雜度和空間復(fù)雜度都比較高，往往不能很好地滿足實(shí)時(shí)性的推薦需求.此外，大多數(shù)的混合推薦算法都是基于假設(shè)用戶是獨(dú)立的個(gè)體的前提，忽略了社交網(wǎng)絡(luò)中用戶的朋友關(guān)系及信任關(guān)系，因此，準(zhǔn)確度也不高.

以上三類算法是在目前的推薦領(lǐng)域內(nèi)運(yùn)用較為廣泛的方法，研究者們主要用這些方法解決兩大類問題：最小化評(píng)分誤差、優(yōu)化top-k項(xiàng)目排序.

2.2 基于評(píng)分預(yù)測的推薦

在實(shí)際生活中，用戶往往只會(huì)購買并且評(píng)分小部分商品，所以用戶-評(píng)分矩陣存在大量的“0”分?jǐn)?shù)據(jù)，即評(píng)分?jǐn)?shù)據(jù)存在嚴(yán)重的稀疏性.盡管基于模型的協(xié)同過濾算法可以有效地緩解該影響但是并不能完全去除數(shù)據(jù)稀疏對(duì)算法效果的影響.近年來，隨著Facebook，Twitter等社交服務(wù)迅速發(fā)展，基于社會(huì)網(wǎng)絡(luò)的推薦系統(tǒng)得到了越來越多的關(guān)注，很多研究者將社會(huì)化網(wǎng)絡(luò)中的信任信息加入到推薦算法中以緩解用戶數(shù)據(jù)稀疏問題.Jamali等人[16]結(jié)合基于內(nèi)存以及基于模型的協(xié)同過濾算法，利用信任信息提出了隨機(jī)走步框架.該算法可以在較短的路徑中得到更精準(zhǔn)的評(píng)分預(yù)測值，同時(shí)還可以提高推薦結(jié)果的覆蓋率.Ma等人[17]首次提出了聯(lián)合概率矩陣分解(Unified Probabilistic Matrix Factorization，UPMF)方法，在方法的訓(xùn)練模型中，評(píng)分矩陣和信任矩陣共享用戶特征矩陣，從而能夠結(jié)合這兩面信息進(jìn)行推薦.

然而，用戶更希望看到一個(gè)符合自己興趣愛好的top-k項(xiàng)目推薦列表，上述算法主要致力于最小化評(píng)分預(yù)測誤差值RMSE和MAE，并不能得到一個(gè)更好的top-k排序列表.本文的研究重點(diǎn)在于如何找到一個(gè)更好的top-k列表.

2.3 基于top-k排序的推薦

已有的一些較好的top-k推薦方法，利用LTR算法思想[7]，從訓(xùn)練數(shù)據(jù)生成個(gè)性化排名列表.基于LTR的top-k推薦方法分為list-wise和pair-wise兩類.Pair-wise模型通過用戶購買、瀏覽信息訓(xùn)練其對(duì)每個(gè)項(xiàng)目對(duì)的相對(duì)偏好[18，19].Pair-wise模型在top-k推薦方面已經(jīng)取得了實(shí)質(zhì)性的改進(jìn)，但存在著高計(jì)算復(fù)雜度的問題.List-wise模型具高可擴(kuò)展性[19，20]和較低的計(jì)算復(fù)雜度，該模型是基于實(shí)際排序列表和預(yù)測列表之間的差距來優(yōu)化預(yù)測每個(gè)用戶的項(xiàng)目排名推薦列表.

將社會(huì)化網(wǎng)絡(luò)中的信任信息加入到推薦算法當(dāng)中，可以緩解評(píng)分?jǐn)?shù)據(jù)稀疏性問題，同時(shí)提高推薦算法的準(zhǔn)確度[8，9，21，30].文獻(xiàn)[9]中提出了一種基于pair-wise的LTR方法，該文主要基于以下假設(shè)：相比于用戶根本不知道的項(xiàng)目，他們更傾向于其朋友喜歡的項(xiàng)目.然而，他們的方法不能直接處理數(shù)字評(píng)分，并且由于pair-wise模型的內(nèi)在特性，該算法具有較高的計(jì)算復(fù)雜度.Yao等人[8]采用文獻(xiàn)[22]中的評(píng)分模型，將用戶的興趣愛好和其朋友的興趣愛好線性結(jié)合，建立了評(píng)分預(yù)測模型.與本文一樣他們也通過使用top-one概率(這將在本文第3章中解釋)來降低算法的復(fù)雜度.然而，他們只關(guān)注用戶對(duì)物品評(píng)分時(shí)存在的興趣偏好，忽略了用戶對(duì)朋友進(jìn)行信任打分時(shí)展現(xiàn)出來的興趣偏好信息.Park[21]等人 中提出了TRecSo算法，從信任、被信任兩種角色來考慮用戶的特征向量，同時(shí)也將信任信息對(duì)top-k排序列表的影響考慮進(jìn)算法當(dāng)中，構(gòu)建了一個(gè)出色的訓(xùn)練模型.但是該算法對(duì)于用戶間信任處理過于簡單，只考慮了用戶的出度、入度信息，同時(shí)由于TRecSo模型中用戶特征向量由多個(gè)向量組成，導(dǎo)致模型的訓(xùn)練復(fù)雜度有所上升.

在本文中，我們結(jié)合評(píng)分、信任信息提出了基于list-wise思想 BTRank算法.在算法模型訓(xùn)練前期我們將從多方面來重組用戶間的信任信息，模型訓(xùn)練時(shí)使用top-one概率來優(yōu)化算法的性能.最后我們?cè)趦蓚€(gè)現(xiàn)實(shí)世界數(shù)據(jù)集上證明，BTRank要優(yōu)于以上幾類優(yōu)秀的方法.

3 基于信任的top-k算法BTRank

為了更好地了解本文提出的算法，本章中3.1節(jié)簡短的介紹核心top-one概率模型，3.2節(jié)中提出本文的時(shí)間效應(yīng)模型，之后3.3以及3.4節(jié)分別介紹如何在評(píng)分、信任信息中應(yīng)用top-one概率模型.最后3.5節(jié)展示如何結(jié)合評(píng)分、信任兩部分信息，給出BTRank模型的目標(biāo)函數(shù).

3.1 Top-one概率模型

Plackett-Luce模型[23]可以用于計(jì)算每個(gè)用戶對(duì)曾經(jīng)評(píng)分過項(xiàng)目的排列分布概率.該模型基于假設(shè)：每個(gè)不同的項(xiàng)目排列都有相應(yīng)的分布概率，而高的排列概率意味著該項(xiàng)目排序更受用戶喜愛.

排列概率：對(duì)于用戶ui，給定含有M個(gè)項(xiàng)目的集合V，π={v1，v2，…，vM}是其中一種可能的項(xiàng)目排序，其對(duì)應(yīng)的評(píng)分信息為{ri1，ri2，…，riM}，那么π排列的分布概率為：

(1)

其中rij是用戶ui對(duì)項(xiàng)目vj的評(píng)分值，exp(r)=er.根據(jù)公式(1)可知，對(duì)于含有M個(gè)項(xiàng)目的集合來說，每個(gè)用戶都有M!種不同的項(xiàng)目排序，計(jì)算復(fù)雜度太高.為了解決這個(gè)問題，我們使用top-one 概率來代替公式(1)中的排列分布概率：

(2)

由于用戶更關(guān)心系統(tǒng)推薦給他的top-k個(gè)項(xiàng)目，因此本文在考慮項(xiàng)目可能排序時(shí)只關(guān)注前k個(gè)項(xiàng)目.公式(2)代表對(duì)于用戶ui來說項(xiàng)目vj被排列在第一位的可能性.

3.2 時(shí)間效應(yīng)模型

傳統(tǒng)的推薦算法，將所有的項(xiàng)目平等對(duì)待，沒有考慮用戶的興趣會(huì)隨著時(shí)間的演變產(chǎn)生變化，致使推薦精度不高.根據(jù)19 世紀(jì)德國心理學(xué)家赫爾曼·艾賓浩斯的實(shí)驗(yàn)結(jié)果可得知，遺忘在記憶后會(huì)立刻開始，并且遺忘速率遵循先快后慢的規(guī)律.他根據(jù)實(shí)驗(yàn)結(jié)果將時(shí)間與記憶量的關(guān)系繪制成了著名的艾賓浩斯遺忘曲線[29]：

圖1 艾賓浩斯遺忘曲線Fig.1 Ebbinghaus forgetting curve

學(xué)者Ding也認(rèn)為資源的時(shí)效性隨時(shí)間的變化應(yīng)是一種指數(shù)衰減的過程[28]，因此結(jié)合圖1我們?cè)O(shè)計(jì)資源衰減的時(shí)間效應(yīng)模型為：

h(Δt，λ)=e-λΔt

(3)

其中Δt∈[0，+∞)表示學(xué)習(xí)過后經(jīng)過的時(shí)間，λ代表遺忘速率，不同人群的λ可能不同，h為到目前位置記憶的衰減比例.用戶可以分為兩類：

1)念舊型，喜歡一類事物的周期很長，一段時(shí)間內(nèi)興趣愛好變化不大；

2)多變型，喜歡嘗試新事物，興趣愛好隨時(shí)間呈現(xiàn)跳變型.在推薦系統(tǒng)中，評(píng)分信息可以很好的反映一個(gè)人的興趣愛好變化，本文以3個(gè)月為一個(gè)周期，統(tǒng)計(jì)用戶從第一次評(píng)分到目前為止所有周期內(nèi)平均評(píng)分的變化值作為該用戶的遺忘速率λ.

3.3 評(píng)分模型

基于矩陣分解框架，用戶ui對(duì)項(xiàng)目vj的預(yù)測評(píng)分計(jì)算方法如公式(4)所示：

(4)

但是公式(4)中并未考慮時(shí)間因素對(duì)用戶評(píng)分的影響，考慮時(shí)間效應(yīng)后，改寫公式(4)，得到用戶ui在時(shí)間ti，j對(duì)項(xiàng)目vj的預(yù)測評(píng)分計(jì)算公式：

(5)

同時(shí)為了解決用戶評(píng)分?jǐn)?shù)據(jù)的稀疏性，本文在計(jì)算預(yù)測評(píng)分的模型中加入信任用戶間的影響，更新公式(5)如下所示：

(6)

sik表示用戶ui對(duì)uk的信任評(píng)分值，T(i)是用戶ui信任的用戶集合.參數(shù)β用于平衡控制信任用戶對(duì)目標(biāo)用戶評(píng)分的影響程度，β∈[0，1].當(dāng)β=1時(shí)表示完全沒有影響，反之β=0表示用戶對(duì)項(xiàng)目評(píng)分完全受信任用戶影響.

此時(shí)我們可以利用公式(2)的top-one 概率模型以及交叉熵公式得到目標(biāo)函數(shù)，最小化預(yù)測排序列表與真實(shí)排序列表間的不穩(wěn)定性：

(7)

3.4 信任模型

本文提出了一種新的信任計(jì)算模型，使用全局、局部兩個(gè)方面來刻畫用戶間信任信息.在計(jì)算對(duì)來說uj的全局信任gtij時(shí)，不同于已有的研究，本文主要考慮以下三點(diǎn)：

1) 其余所有用戶對(duì)uj的信任評(píng)價(jià)值；

2) 對(duì)uj有信任評(píng)價(jià)的用戶數(shù)量：

3)ui與這些用戶之間的興趣相似度.最終本文構(gòu)建全局信任計(jì)算公式如下所示：

(8)

本文在計(jì)算與uj的局部信任ltij時(shí)，分兩種情況進(jìn)行考慮：

1)對(duì)uj有信任評(píng)分值，即對(duì)uj存在直接信任，那么對(duì)uj間的局部信任基于直接信任進(jìn)行計(jì)算得到；

2)對(duì)uj沒有信任評(píng)分值，根據(jù)信任傳播性得到對(duì)uj的間接信任值作為局部信任值.為了消除用戶間評(píng)分的習(xí)慣差異性，本文對(duì)數(shù)據(jù)集中用戶間的直接信任評(píng)價(jià)值進(jìn)行以下處理：

(9)

(10)

本文主要利用信任傳遞性來計(jì)算用戶間間接信任評(píng)價(jià)值idtij.公式(11)為信任衰減函數(shù)，L是信任傳遞路徑長度，其中最大路徑長度Max_Hop<=6：

(11)

本文選取最有效路徑[6]而不是最短路徑作為用戶間最佳的信任傳播路徑.同時(shí)將網(wǎng)絡(luò)中所有用戶間平均信任值作為判斷的信任閾值Υ.當(dāng)某條路徑上存在兩個(gè)相鄰用戶間的信任評(píng)價(jià)值小于Υ時(shí)，則放棄該條路徑重新尋找有效路徑.某條路徑Pathi的源節(jié)點(diǎn)ui對(duì)目標(biāo)節(jié)點(diǎn)uj的信任評(píng)價(jià)值計(jì)算如公式(12)所示：

(12)

其中uk代表路徑Pathi中第K個(gè)節(jié)點(diǎn)，Tuk-1→uk表示節(jié)點(diǎn)uk-1對(duì)uk的信任評(píng)價(jià)值，當(dāng)信任值大于閾值Υ時(shí)，Iuk-1→uk為1，反之為0.當(dāng)網(wǎng)絡(luò)中存在多條有效路徑時(shí)，本文選取信任值最大的一條，如公式(13)所示：

(13)

綜上所述，用戶間的最終信任值計(jì)算公式如(14)所示，其中α∈[0，1]為平衡參數(shù)，用于調(diào)和全局信任以及局部信任間的比重.

sij=αgtij+(1-α)ltij

(14)

當(dāng)用戶ui對(duì)uj只存在間接信任關(guān)系，考慮到此時(shí)的局部信任比全局信任要可靠的多，特別是在全局網(wǎng)絡(luò)中對(duì)uj有過信任評(píng)分的用戶數(shù)量稀少的情況下.所以此時(shí)α的計(jì)算公式如下所示：其中F+(uj)表示網(wǎng)絡(luò)中信任uj的用戶集合.

(15)

以上是本文提出的信任模型的全部內(nèi)容，它主要用于對(duì)信任的前期處理，對(duì)于訓(xùn)練過程中ui對(duì)uj的信任值可以根據(jù)公式(16)構(gòu)建：

(16)

Ui是用戶ui的特征向量，Tj是用戶uj的信任特征向量.同樣地，對(duì)于用戶間信任評(píng)分?jǐn)?shù)據(jù)也可以用熵公式來衡量真實(shí)訓(xùn)練排序以及預(yù)測排序之間的差異，最小化熵公式如下所示：

(17)

3.5 目標(biāo)函數(shù)

在3.3、3.4節(jié)中，本文定義了如何將評(píng)分、信任信息模型化，最后本文使用公式(18)將公式(7)與公式(17)聯(lián)合進(jìn)一個(gè)統(tǒng)一模型當(dāng)中，并將其作為目標(biāo)函數(shù)：

(18)

為了降低模型復(fù)雜度，本文設(shè)置λu=λv=λt=λ.同時(shí)為了得到相應(yīng)的特征向量，本文采用隨機(jī)梯度下降法來得到它們的局部最優(yōu)值，其計(jì)算公式如下所示：

(19)

(20)

(21)

(22)

(23)

(24)

(25)

(26)

其中g(shù)′(x)是邏輯斯蒂函數(shù)g(x)的導(dǎo)數(shù)，g′(x)=exp(x)/(1+exp(x))2.

4 復(fù)雜性分析

BTRank的計(jì)算開銷主要來自于公式(14)中前期信任關(guān)系的訓(xùn)練、公式(18)中目標(biāo)函數(shù)L的計(jì)算以及公式(19)-(26)中各個(gè)特征向量對(duì)應(yīng)的梯度下降的計(jì)算.在訓(xùn)練信任關(guān)系時(shí)，我們假設(shè)存在信任數(shù)據(jù)的用戶數(shù)量為t，且每個(gè)用戶的鄰居集合大小為N，則間接信任關(guān)系的訓(xùn)練時(shí)間復(fù)雜度為O(t2N)，其中N通常較小，可以認(rèn)為是常數(shù)，則時(shí)間復(fù)雜度趨向于O(t2)；目標(biāo)函數(shù)L的時(shí)間復(fù)雜度為O(pRl+pSl)，其中pR，pS分別表示矩陣R，S中非零元素個(gè)數(shù)，由于數(shù)據(jù)稀疏性，pR和ps都很?。惶荻认陆捣ㄖ杏?jì)算復(fù)雜度主要由公式(19)-(21)產(chǎn)生，其時(shí)間復(fù)雜度分別為O(pRk+pSk)，O(pRk)和O(pSk)，k表示最終推薦給用戶的top-k目表中的項(xiàng)目個(gè)數(shù)，因此每次迭代的總時(shí)間復(fù)雜度為O(pRk+pSk).假設(shè)本文算法迭代d次，總的時(shí)間復(fù)雜度為O(t2)+O(dpRk+dpSk)，因此，與pair-wise的LTR方法不同，我們提出的模型可以有效地應(yīng)用到大規(guī)模數(shù)據(jù)集中.

5 實(shí)驗(yàn)與結(jié)果分析

在本章節(jié)中設(shè)計(jì)了幾個(gè)實(shí)驗(yàn)將本文的算法BTRank與其余幾個(gè)出色的算法進(jìn)行比較.實(shí)驗(yàn)的設(shè)計(jì)主要基于以下幾點(diǎn)：

1.如何將本文算法與已有優(yōu)秀算法進(jìn)行比較？

2.考慮時(shí)間因素是否可以提升算法的精度？

3.模型訓(xùn)練前使用第3.4節(jié)中提出的信任模型對(duì)信任數(shù)據(jù)做處理是否對(duì)算法有所幫助？

4.參數(shù)β對(duì)算法推薦準(zhǔn)確率有怎樣的影響？

5.特征向量U、V、T的維度取值對(duì)推薦準(zhǔn)確率有什么影響？

5.1 數(shù)據(jù)集

在實(shí)驗(yàn)中，我們使用兩個(gè)公共現(xiàn)實(shí)世界的數(shù)據(jù)集Epinions*http://www.trustlet.org/wiki/Extended_Epinions_dataset和Ciao*https://www.librec.net/datasets.html，每個(gè)數(shù)據(jù)集都包含用戶項(xiàng)目評(píng)分、用戶之間的信任關(guān)系(數(shù)據(jù)集中的信任關(guān)系都是不對(duì)稱的)和評(píng)分的時(shí)間信息，其中項(xiàng)目評(píng)分是區(qū)間[1，5]內(nèi)的整數(shù).

5.2 實(shí)驗(yàn)規(guī)則

對(duì)于每位用戶我們分別隨機(jī)選取n=10，20，50條項(xiàng)目評(píng)分和信任記錄作為訓(xùn)練數(shù)據(jù)集，余下的都作為測試數(shù)據(jù).為了保證每位用戶至少存在10條測試數(shù)據(jù)，我們會(huì)相應(yīng)的過濾掉數(shù)據(jù)記錄少于20，30，60條的用戶.

參數(shù)設(shè)置：對(duì)于所有的對(duì)比實(shí)驗(yàn)，本文均按照原文設(shè)置最優(yōu)參數(shù)；在算法BTRank中，我們?cè)O(shè)置λ=0.1，γ=0.01，其中γ是迭代過程中的學(xué)習(xí)速率，所有的實(shí)驗(yàn)結(jié)果都是5次實(shí)驗(yàn)的平均值.

5.3 評(píng)價(jià)函數(shù)

均方誤差(RMSE)和平均絕對(duì)誤差(MAE)是傳統(tǒng)推薦系統(tǒng)的標(biāo)準(zhǔn)評(píng)估指標(biāo)，這兩個(gè)指標(biāo)能衡量真實(shí)評(píng)分與預(yù)測評(píng)分之間的差距，但是不能是評(píng)價(jià)top-k項(xiàng)目列表排序準(zhǔn)確性.本文旨在提高top-k推薦質(zhì)量，因此使用信息檢索領(lǐng)域最常用的指標(biāo)NDCG、Recall、Precision作為本文評(píng)價(jià)標(biāo)準(zhǔn).

NDCG更加重視排序列表的前幾位，排序越前面的項(xiàng)目在評(píng)估中所占比重越大.對(duì)于排序在第一位的項(xiàng)目來說，得到5分與得到4分評(píng)分相比，前者的NDCG@1更高.所以對(duì)于ui來說，k個(gè)項(xiàng)目排序列表的 NDCG值為：

(27)

其中Z是一個(gè)常量，它使對(duì)于ui來說最優(yōu)的top-k排序的NDCG為1.

最后我們計(jì)算所有用戶的NDCGi@K值并取平均值得到NDCG@K如下所示：

(28)

其中|U|是用戶集合U的大小.

Precision@K表示推薦精準(zhǔn)度，Recall@K表示召回率，對(duì)于ui，集合Pi={v1，v2，…vK}表示由推薦系統(tǒng)產(chǎn)生的top-k項(xiàng)目列表，Qi={v1，v2，…vz}表示實(shí)際用戶偏愛項(xiàng)目，則

(29)

(30)

5.4 對(duì)比實(shí)驗(yàn)

本文跟以下三類出色的推薦算法對(duì)比：傳統(tǒng)CF方法，僅基于評(píng)分的LTR方法和基于社交網(wǎng)絡(luò)的LTR方法.

a)傳統(tǒng)CF方法

UserKNN[27]：一種基于用戶相似度的傳統(tǒng)協(xié)同過濾推薦算法.

b)基于評(píng)分的LTR方法

BPR[18]：結(jié)合矩陣分解方法的pair-wise類LTR算法.

ListRank[19]：結(jié)合矩陣分解方法的list-wise類LTR算法.

c)基于社交網(wǎng)絡(luò)的LTR方法

SBPR[9]：在BRP的基礎(chǔ)上加入信任信息，提高算法準(zhǔn)確度.

SoRank[8]：結(jié)合信任信息的list-wise類LTR算法，線性結(jié)合信任用戶對(duì)目標(biāo)用戶的影響，從而優(yōu)化top-k推薦算法效果.

BTRank：本文提出的算法.

5.5 信任模型的作用

為了驗(yàn)證3.4節(jié)中提出的信任模型的有效性，我們?cè)O(shè)計(jì)了多個(gè)對(duì)比實(shí)驗(yàn)，將本文算法BTRank與未應(yīng)用信任模型的BTRank進(jìn)行比較，實(shí)驗(yàn)結(jié)果如圖2所示.從圖中可以看出，在各種情況下使用了信任模型的算法結(jié)果明顯好于未使用的算法結(jié)果，證明了本文信任模型對(duì)算法有推進(jìn)作用，在算法訓(xùn)練之前對(duì)信任數(shù)據(jù)做預(yù)先處理是必要的.

5.6 時(shí)間效應(yīng)模型的作用

本文在3.2節(jié)中，根據(jù)艾賓浩斯遺忘曲線提出了一個(gè)時(shí)間效應(yīng)模型，對(duì)用戶的評(píng)分?jǐn)?shù)據(jù)根據(jù)歷史時(shí)間給予相應(yīng)的權(quán)重，越接近當(dāng)前時(shí)間的評(píng)分?jǐn)?shù)據(jù)其權(quán)重值越高，反之則越小.

為了驗(yàn)證該模型的有效性，我們?cè)O(shè)計(jì)了多個(gè)對(duì)比實(shí)驗(yàn)將本文算法BTRank與未應(yīng)用該時(shí)間效應(yīng)模型的BTRank進(jìn)行比較，實(shí)驗(yàn)結(jié)果如圖3所示.從圖中可以看出，在各種情況下使用了時(shí)間效應(yīng)模型的算法結(jié)果明顯好于未使用的算法結(jié)果，證明了該模型對(duì)算法有推進(jìn)作用，考慮用戶評(píng)分?jǐn)?shù)據(jù)時(shí)間效應(yīng)性是有必要的.

圖2 信任模型的影響Fig.2 Impact of trust model

圖3 時(shí)間模型的影響Fig.3 Impact of time attenuation model

圖4 參數(shù)β的影響(n=20，k=5)Fig.4 Impact of parameter β (n=20，k=5)

5.7 參數(shù)β的影響

在文本算法BTRank中參數(shù)β用于控制信任用戶興趣愛好對(duì)項(xiàng)目評(píng)分的影響.本次實(shí)驗(yàn)訓(xùn)練數(shù)據(jù)選取規(guī)則采用n=20，結(jié)果如圖4所示.在不同數(shù)據(jù)集上算法效果趨勢各不一致，但是大體上都呈先上升后下降趨勢.其中β=0.4是一個(gè)閾值，當(dāng)β<0.4時(shí)，算法效果呈上升趨勢，β>0.4時(shí)算法效果呈下降趨勢，所以此時(shí)將β值設(shè)為0.4使得算法效果最優(yōu).

5.8 特征維度的影響

矩陣分解算法復(fù)雜度隨著特征維度取值增加而增加，本文為了降低模型訓(xùn)練的時(shí)間，在區(qū)間[1，50]上探尋局部最優(yōu)的維度取值，實(shí)驗(yàn)結(jié)果如圖5所示.根據(jù)結(jié)果可以看出，雖然算法效果趨勢都不完全一致，但是都呈先上升后下降的趨勢，在特征維度值取為5的時(shí)候達(dá)到最佳效果，所以在本文之后的實(shí)驗(yàn)中我們將維度設(shè)置為5.

圖5 特征維度取值影響(n=10，k=5)Fig.5 Impact of latent dimensionality (n=10，k=5)

5.9 算法比較

為了驗(yàn)證本文算法的有效性，本實(shí)驗(yàn)將BTRank與其余五個(gè)算法進(jìn)行比較，結(jié)果如圖6所示.從圖中可以看出本文算法BTRank的效果在各種不同情況下普遍好于其余算法，而UserKNN算法效果明顯弱于其它算法，很好地說明傳統(tǒng)的個(gè)性化推薦算法并不適用于top-k推薦.

BTRank、SoRank、ListRank-MF均是基于list-wise的LTR類算法，其中ListRank-MF算法未考慮信任用戶對(duì)目標(biāo)用戶的影響，而SoRank和本文算法均考慮到了信任關(guān)系的影響，并且從實(shí)驗(yàn)結(jié)果中可以明顯看出這兩個(gè)算法效果好于ListRank-MF，說明同時(shí)考慮自身以及朋友因素對(duì)評(píng)分構(gòu)成的影響可以有效提升算法的效果；相比于SoRank，本文算法不但考慮用戶對(duì)項(xiàng)目排序展現(xiàn)出來的興趣偏好，同時(shí)聯(lián)合考慮用戶對(duì)朋友信任排序時(shí)的偏好信息，從而構(gòu)建更準(zhǔn)確的用戶特征矩陣.從這兩個(gè)算法的對(duì)比效果可以看出本文算法明顯好于SoRank，可見綜合考慮用戶對(duì)項(xiàng)目、朋友排序時(shí)的偏好可以有效提高算法效果.

其中BPR以及SBPR均是基于parie-wise的LTR類算法，這兩個(gè)算法與BTRank、SoRank、ListRank-MF對(duì)比，雖然整體效果要弱于list-wise類算法，但是并不明顯，說明pair-wise在top-k推薦中也獲得了較好的效果，但是相比于list-wise類算法還是略遜一籌.

6 總結(jié)與展望

本文提出了一種基于信任的LTR類推薦算法BTRank，通過加入社交網(wǎng)絡(luò)中信任信息來緩解數(shù)據(jù)稀疏問題、優(yōu)化top-k排名預(yù)測精度.具體來說，本文首先使用信任模型重構(gòu)用戶間的信任信息，其次設(shè)計(jì)時(shí)間衰減函數(shù)分階段評(píng)估用戶興趣變化，同時(shí)在預(yù)測用戶評(píng)分時(shí)考慮信任用戶對(duì)目標(biāo)用戶的影響，最終結(jié)合用戶對(duì)項(xiàng)目評(píng)分排序以及對(duì)其他用戶信任評(píng)分排序時(shí)產(chǎn)生的偏好信息，構(gòu)建更準(zhǔn)確的用戶特征矩陣從而得到較好的top-k推薦列表.綜合實(shí)驗(yàn)結(jié)果表明，BTRank推薦的top-k項(xiàng)目列表在準(zhǔn)確度方面顯著優(yōu)于傳統(tǒng)的推薦算法以及同類top-k推薦算法.

圖6 不同算法效果對(duì)比Fig.6 Comparison of different algorithms

為了降低算法的復(fù)雜度，本文提出的BTRank是基于項(xiàng)目top-one 概率而不是top-k概率.在未來的工作中可以研究更好的項(xiàng)目排序概率模型用于top-k排序推薦；其次希望可以研究出更好的時(shí)間衰減模型，能更準(zhǔn)確地衡量評(píng)分?jǐn)?shù)據(jù)十分稀少的用戶興趣變化.