顧軍華，陳 博，王 銳，張素琪

1.河北工業(yè)大學 人工智能與數(shù)據(jù)科學學院，天津300401

2.河北省大數(shù)據(jù)計算重點實驗室，天津300401

3.天津商業(yè)大學 信息工程學院，天津300134

生活在信息交互頻繁的社會，人們在做各種決定時不僅根據(jù)自身的觀察和判斷，還會考慮信任朋友的觀點。因此，在推薦系統(tǒng)中，用戶的偏好很可能受用戶朋友的影響[1]。基于這一假設(shè)，很多研究學者將社交信息融入到推薦算法[2-4]中，以緩解傳統(tǒng)的協(xié)同過濾推薦算法的數(shù)據(jù)稀疏性問題[5-6]和冷啟動問題[7]。

對于社會化推薦算法，眾多學者進行了深入的研究。Ma等人[8]使用概率矩陣分解方法對社交信息和評分信息建模，解決了評分數(shù)據(jù)稀疏性問題和預(yù)測精度差的問題，且可以應(yīng)用于大規(guī)模數(shù)據(jù)集。Yang等人[9]采用矩陣分解技術(shù)，將用戶作為信任者和被信任者兩種身份，根據(jù)用戶之間的信任關(guān)系將用戶映射到低維的特征空間，以更好地挖掘被信任者對信任者的影響，進而得到更為準確的推薦結(jié)果。Rafailidis等人[10]提出了一種利用用戶信任和不信任關(guān)系的學習排序模型，將用戶及其信任用戶喜愛的項目放到推薦列表的最前面，而將其不信任用戶喜愛的項目排在后面。王衛(wèi)紅等人[11]從社交網(wǎng)絡(luò)獲得用戶之間的相似度，再利用聚類算法填充評分矩陣的缺失值，最后通過協(xié)同過濾算法進行推薦。這些方法均利用了社交網(wǎng)絡(luò)中的二值數(shù)據(jù)，在一定程度上提高了推薦算法的有效性，但僅僅利用用戶的直接信任關(guān)系，忽略了用戶之間的間接聯(lián)系。

總體而言，當前的社會化推薦算法未能充分利用社交信息，忽視了用戶之間的間接聯(lián)系，且僅僅利用社交信息中的二值數(shù)據(jù)，未考慮用戶之間信任的權(quán)重問題，降低了推薦算法的精度。因此，本文針對社交信息的稀疏性問題和用戶間信任權(quán)重問題進行研究，提出一種結(jié)合重要節(jié)點信任傳播的社會化推薦算法（INTP-Rec）。首先利用重啟隨機游走算法得到社交網(wǎng)絡(luò)中的重要節(jié)點，然后提出重要節(jié)點信任傳播算法（INTP），來捕獲用戶之間的間接信任關(guān)系，進而豐富社交信息。同時量化用戶之間的信任關(guān)系，以提高推薦算法的準確度。經(jīng)過實驗證明，本文提出的方法能有效地緩解社交信息的稀疏性問題，并提高推薦算法的精度。

1 問題描述

本章首先對社會化推薦算法進行簡要描述，然后提出信任傳播和信任量化問題。

1.1 社會化推薦算法

社交信息可以通過社交網(wǎng)絡(luò)圖表示出來，如圖1（a）所示。其中，圓形表示用戶節(jié)點，節(jié)點之間的連接表示用戶之間的信任關(guān)系。社會化推薦算法，是利用用戶之間的信任關(guān)系，認為在社交網(wǎng)絡(luò)中相互信任的用戶具有相似的偏好，進而向用戶做出推薦[12]。觀察圖1（a）中的用戶節(jié)點1、用戶節(jié)點2和兩個節(jié)點對項目的喜愛關(guān)系，說明社交推薦的過程，如圖1（b）所示。其中，方形表示項目節(jié)點，用戶節(jié)點與項目節(jié)點之間相連的實線邊表示喜愛關(guān)系，虛線邊表示推薦關(guān)系。為用戶節(jié)點2推薦項目，并將社交推薦過程中所需的邊關(guān)系加粗。通過社交網(wǎng)絡(luò)圖可知，用戶2信任用戶1，因此假設(shè)用戶2與用戶1具有相似的偏好，并將用戶1喜愛的項目b推薦給用戶2。

圖1 社會化推薦Fig.1 Social recommendation

1.2 信任傳播和信任量化

將社交信息融入到推薦算法中，在一定程度上緩解了數(shù)據(jù)稀疏性問題和冷啟動問題，但是由于用戶間的直接聯(lián)系很少，導(dǎo)致可利用的社交信息較少，降低了社會化推薦算法的準確度。因此，本文提出一種重要節(jié)點信任傳播的算法（INTP），以挖掘社交網(wǎng)絡(luò)中的重要節(jié)點，并通過信任在重要節(jié)點和其間接相連節(jié)點之間的傳播，得到兩者之間的信任關(guān)系。信任傳播過程如圖2所示，其中，節(jié)點1為重要節(jié)點，節(jié)點6通過節(jié)點2與節(jié)點1間接相連，兩者之間以虛線連接，當兩者滿足信任傳播的條件時，建立由節(jié)點6指向節(jié)點1的信任關(guān)系，為社交網(wǎng)絡(luò)圖增加連接邊。本文將在第2章中詳細說明INTP算法。

圖2 信任傳播過程Fig.2 Trust propagation process

為獲得更精確的推薦結(jié)果，本文將優(yōu)化后的社交網(wǎng)絡(luò)上的二值數(shù)據(jù)進行加權(quán)量化，來進一步反映社交網(wǎng)絡(luò)的整體結(jié)構(gòu)信息，具體方法在下面內(nèi)容中詳細說明。

2 INTP算法

本章提出基于重啟隨機游走的重要節(jié)點信任傳播算法（INTP），以增補社交信息中用戶之間關(guān)系的缺失值，進而解決社交信息的稀疏性問題。在該算法中，首先通過重啟隨機游走算法RWR（Random Walk with Restart）得到社交網(wǎng)絡(luò)圖的重要節(jié)點，其次確定在社交網(wǎng)絡(luò)圖中信任通過重要節(jié)點向外傳播的條件，以判斷用戶節(jié)點是否受到重要節(jié)點的影響，然后建立受到影響的用戶節(jié)點與重要節(jié)點之間的連接，從而豐富社交信息，最后為增加連接邊后的社交網(wǎng)絡(luò)圖增加邊權(quán)重，以提高推薦效果。

2.1 確定社交網(wǎng)絡(luò)圖的重要節(jié)點

在社會生活中存在小部分人，他們的個人行為會對很多人造成影響，比如，網(wǎng)紅效應(yīng)，當知名網(wǎng)紅博主使用并推薦一款產(chǎn)品時，眾多信任這位博主的人會去購買這款產(chǎn)品。因此，在社交網(wǎng)絡(luò)圖中，如果一個用戶節(jié)點對很多節(jié)點都具有很大的影響力，那么就把這個用戶節(jié)點定義為重要節(jié)點。在圖1（a）中可以看出節(jié)點1受到大量其他用戶節(jié)點的信任，由此可以認為，節(jié)點1是圖1（a）中的重要節(jié)點，可以影響社交網(wǎng)絡(luò)中的其他節(jié)點。因此，根據(jù)重要節(jié)點被大量其他節(jié)點信任的特點，本文使用重啟隨機游走算法對用戶節(jié)點的重要程度進行排序，以篩選出在整個網(wǎng)絡(luò)中有影響力，值得信任的重要節(jié)點。

重啟隨機游走算法最早用以解決互聯(lián)網(wǎng)頁面的重要性排序問題[13]。本文將用戶節(jié)點比作網(wǎng)頁，用戶間的信任關(guān)系比作網(wǎng)頁間的跳轉(zhuǎn)關(guān)系。RWR確定重要節(jié)點的步驟如下：給定一個加權(quán)有向圖G，用V表示圖G的節(jié)點集合，N表示圖G的節(jié)點個數(shù)，A表示圖G的鄰接矩陣，Aij表示節(jié)點i和節(jié)點j之間有無連接，當從節(jié)點i出發(fā)有邊連向節(jié)點j時，Aij=1，否則Aij=0。用P表示圖G的轉(zhuǎn)移概率矩陣，P里面的每一個元素Pij表示節(jié)點i跳轉(zhuǎn)到節(jié)點j的概率值，具體如公式（1）所示：

RWR算法通過一個參數(shù)α來調(diào)節(jié)游走者繼續(xù)跳轉(zhuǎn)或者返回初始節(jié)點的概率，游走者在每次跳轉(zhuǎn)時都有α的概率跳轉(zhuǎn)到當前節(jié)點的鄰接節(jié)點上，或者以1-α的概率返回初始節(jié)點，圖G中的每個節(jié)點都有1/N的概率成為初始節(jié)點，具體如公式（2）所示：

式中，x表示節(jié)點的重要程度向量，t表示迭代次數(shù)，xt和xt+1是經(jīng)過t和t+1次迭代后的向量，x0是一個重啟向量，每個節(jié)點對應(yīng)位置的元素值為1/N。當向量x收斂后結(jié)束RWR算法[14]，向量x中的N個元素表示每個節(jié)點的重要程度值。最后，取重要程度值較高的節(jié)點放入重要節(jié)點集合S，S中節(jié)點的數(shù)目為節(jié)點總數(shù)的1%。

2.2 重要節(jié)點的信任傳播

在社交網(wǎng)絡(luò)圖中，重要節(jié)點對其他用戶節(jié)點有較大的影響。因此，信任可以通過社交網(wǎng)絡(luò)中的邊由重要節(jié)點向其他用戶節(jié)點傳播。

將社交網(wǎng)絡(luò)圖建模為一個加權(quán)有向圖G=(V,E,W)，用V表示圖G的節(jié)點集合，E是邊的集合，W是邊權(quán)重的集合。在圖G中，從用戶節(jié)點u指向重要節(jié)點v的一條邊(u→v)表示用戶u信任用戶v。信任傳播算法的目標是識別出信任重要節(jié)點且沒有與重要節(jié)點直接相連的用戶節(jié)點，并為識別出的用戶節(jié)點與重要節(jié)點建立連接邊，進而減小社交網(wǎng)絡(luò)的稀疏度。

在社交網(wǎng)絡(luò)圖中，邊的權(quán)重由構(gòu)成邊的兩個用戶節(jié)點的結(jié)構(gòu)特征確定。因此，使用直接信任權(quán)重w(uv)表示用戶節(jié)點u對重要節(jié)點v的信任程度，定義為：

其中，Iv表示為用戶節(jié)點v的入度，Ou表示為用戶節(jié)點u的出度。只有當邊的直接信任權(quán)重w(uv)大于等于用戶節(jié)點u的閾值時，該算法認為用戶節(jié)點u信任重要節(jié)點v。

為增加間接信任關(guān)系，算法選擇與用戶節(jié)點u相連而與重要節(jié)點v無連接的用戶節(jié)點p(p→u→v)，判斷用戶節(jié)點p是否信任重要節(jié)點v。當直接信任權(quán)重w(uv)大于等于用戶節(jié)點u的閾值且間接信任權(quán)重w'(pv)大于等于用戶節(jié)點p的閾值時，認為節(jié)點p和v之間存在信任關(guān)系，并為用戶節(jié)點p和重要節(jié)點v建立連接。間接信任權(quán)重w'(pv)的計算方法如下：

其中，decay為信任傳播中的衰減系數(shù)，用于表示信任間接傳播造成的影響。在該算法中，衰減系數(shù)為常數(shù)，取值0.1。

本文提出兩種判斷用戶之間是否信任的閾值條件，并在第4章中對兩種閾值條件進行重要節(jié)點信任傳播算法影響實驗。

條件1：將整個網(wǎng)絡(luò)邊權(quán)值的均值作為閾值，在此條件下，每個節(jié)點的閾值為同一個常數(shù)。

條件2：選擇節(jié)點的所有輸出邊的邊權(quán)值的均值作為閾值，在此條件下，每個節(jié)點的閾值為不同的常數(shù)。

選擇條件2作為閾值判斷條件，通過重要節(jié)點信任傳播算法為圖1（a）的社交網(wǎng)絡(luò)圖增加連接邊，具體結(jié)果如圖3所示。其中，邊上的值為節(jié)點間的信任權(quán)重w，利用公式（3）得出。通過條件2得知用戶節(jié)點2的閾值為4，等于w(21)。可進一步判斷與重要節(jié)點1間接相連的節(jié)點6是否信任重要節(jié)點。利用公式（4）得出w'(61)為2.2，大于節(jié)點6的閾值2。因此，用戶節(jié)點6信任重要節(jié)點1，并為兩者建立連接邊。

圖3 重要節(jié)點信任傳播算法Fig.3 Important nodes trust propagation algorithm

2.3 二值數(shù)據(jù)加權(quán)量化

在前面方法中得到了一些新的用戶之間存在信任關(guān)系的邊，將這些新得到的邊加入到社交網(wǎng)絡(luò)圖G=(V,E,W)中，由此得到更豐富的社交信息。之后，為獲得更為精確的推薦結(jié)果，利用公式（5）對社交信息中的二值數(shù)據(jù)進行進一步加權(quán)量化。

其中，為用戶i對用戶j的最終信任權(quán)重，Tij表示用戶i是否信任用戶j，當信任時，值為1，否則值為0。

3 結(jié)合重要節(jié)點信任傳播的社會化推薦算法

SoRec算法是最為經(jīng)典的社會化推薦算法，其假設(shè)用戶評分系統(tǒng)和社交網(wǎng)絡(luò)共享相同的偏好空間，使用概率矩陣分解的方法進行建模。該模型使用矩陣U、V、Z分別表示用戶特征矩陣、項目特征矩陣和信任因子特征矩陣，使用R、T表示評分矩陣和信任矩陣。該模型的概率圖模型如圖4所示。

圖4 SoRec概率圖模型Fig.4 SoRec probabilistic graphical model

SoRec模型定義評分矩陣和信任矩陣的似然函數(shù)分別為：

該模型根據(jù)貝葉斯推斷，后驗概率∝似然函數(shù)?先驗概率，得到特征矩陣的后驗概率為評分矩陣和信任矩陣的似然函數(shù)與特征矩陣U、V、Z的先驗概率分布相乘，最終的結(jié)果為：

通過利用隨機梯度下降方法（SGD）或交替最小二乘法（ALS），求解矩陣U、V使得公式（8）的后驗概率最大化，最后通過預(yù)測用戶Ui對項目Vj的評分[15]。

本文將INTP算法應(yīng)用于SoRec算法中，以判斷INTP算法在豐富社交信息，提高推薦算法精度上的有效性。在算法1中詳細描述了結(jié)合重要節(jié)點信任傳播的社會化推薦算法，其中T(u)表示信任節(jié)點u的節(jié)點集合，集合中任意節(jié)點與節(jié)點u之間存在直接相連的邊。

算法1INTP-Rec

輸入：社交網(wǎng)絡(luò)圖G=(V,E,W)，用戶評分矩陣R。

輸出：預(yù)測評分結(jié)果Rij。

步驟1初始化衰減系數(shù)decay=0.1，訪問系數(shù)visit=0。

步驟2根據(jù)公式（2）計算用戶節(jié)點重要程度排名x，獲得重要節(jié)點集合S。

步驟3根據(jù)公式（3）計算社交網(wǎng)絡(luò)中每條邊信任權(quán)重w，獲得用戶節(jié)點閾值thr。

步驟4for eachv∈Sdo

if?E(u→v)andw(uv)≥thr(u)：

visit=1；

end if

whilevisit=1 do

visit=0；

for eachp∈T(u)

w(pv)=w(pu)×(1+decay)；

ifw(pv)>thr(u)：

E(p→v)//向社交網(wǎng)絡(luò)圖G中增加由節(jié)點p指向重要節(jié)點v的邊

步驟5根據(jù)公式（5）對增加邊之后社交信息進行進一步優(yōu)化，得到。

步驟6將代替T放入公式（8），并利用SGD計算出U、V。

步驟7得到用戶對項目的評分，輸出對用戶的推薦結(jié)果。

4 實驗分析

4.1 數(shù)據(jù)集介紹

為保證實驗的準確性，本文選擇了三個獨立公開的數(shù)據(jù)集（Epinions數(shù)據(jù)集[16]、FilmTrust數(shù)據(jù)集[17]、Douban數(shù)據(jù)集[18]）進行實驗。三個數(shù)據(jù)集均同時包含評分數(shù)據(jù)和社交信任數(shù)據(jù)，其中Epinions數(shù)據(jù)集和FilmTrust數(shù)據(jù)集中的社交網(wǎng)絡(luò)是有向圖，而Douban數(shù)據(jù)集中的社交網(wǎng)絡(luò)是無向圖，因此，將Douban數(shù)據(jù)集中的每條邊按照雙向信任的規(guī)則進行實驗，各個數(shù)據(jù)集的詳細信息如表1所示。

表1 數(shù)據(jù)集詳細信息Table 1 Dataset details

4.2 實驗指標及對比方法

在社交網(wǎng)絡(luò)圖中，如果一個用戶節(jié)點對很多節(jié)點都具有很大的影響力，實驗使用準確率（Precision）、召回率（Recall）、F1值和均方根誤差（RMSE）作為模型推薦性能的評估標準。每個評估標準的計算方法如下：

其中，F(xiàn)av(u)表示用戶u真實喜愛項目集合，Rec(u)表示推薦算法為用戶u推薦的項目集合。

為了全面地評價本文提出的INTP-Rec模型的推薦效果，本文將對比以下三種算法：

（1）概率矩陣分解算法（PMF）[19]，使用貝葉斯概率矩陣分解的方法對用戶-項目評分矩陣進行分解，得到用戶項目特征矩陣。

（2）基于概率矩陣分解的社會化推薦算法（SoRec）[8]，使用貝葉斯概率矩陣分解的方法建立用戶偏好與信任關(guān)系之間的關(guān)聯(lián)。

（3）基于信任的協(xié)同過濾社會化推薦算法（TrustPMF）[9]，考慮到信任用戶與被信任用戶之間的聯(lián)系。

其中，PMF算法僅利用評分數(shù)據(jù)進行推薦，而SoRec和TrustPMF方法同時使用信任信息和評分數(shù)據(jù)進行推薦。

4.3 實驗結(jié)果

本節(jié)首先通過實驗確定判斷節(jié)點之間是否信任的閾值條件，然后衡量重要節(jié)點信任傳播算法在緩解社交信息稀疏性問題上的有效性，最后通過與其他四種推薦算法的對比，證明本文提出的INTP-Rec方法能有效地提高推薦算法的精度。

4.3.1 用戶節(jié)點閾值選擇實驗

本組實驗的目的是，驗證2.2節(jié)中兩種不同的閾值條件對推薦算法的影響，并根據(jù)實驗結(jié)果選擇最優(yōu)的閾值條件加入到本文的推薦算法INTP-Rec的設(shè)置中。其中閾值是INTP算法中判斷信任能否在節(jié)點之間傳播的重要條件。

本部分實驗將SoRec[8]算法作為基本方法，使用兩種閾值條件與原始的算法進行對比實驗，實驗指標使用RMSE。具體實驗結(jié)果如表2所示。

表2 不同閾值實驗效果對比Table 2 Comparison of different threshold experimental results

表2中的粗體為三種方法得到的實驗結(jié)果在該數(shù)據(jù)集上的最大值。從優(yōu)化前后的對比結(jié)果來看，優(yōu)化后的提升效果較為明顯，說明使用信任傳播算法對社交信息進行優(yōu)化，提高了推薦算法的精度。從條件1與條件2的實驗結(jié)果對比來看，條件2的結(jié)果更為理想，說明選擇節(jié)點的所有輸出邊的邊權(quán)值的均值作為閾值更能夠取得較好的推薦效果。條件2相較于條件1為每一個節(jié)點按照節(jié)點自身結(jié)構(gòu)特征做出判斷，所以更可能取得好的推薦效果。在之后的實驗中，本文均選擇條件2作為閾值確定的條件。

4.3.2 社交信息稀疏度緩解實驗

本組實驗的目的是，通過對比原始社交網(wǎng)絡(luò)的邊數(shù)和經(jīng)過信任傳播算法優(yōu)化后的社交網(wǎng)絡(luò)的邊數(shù)，來驗證INTP算法是否能夠緩解社交信息的稀疏性問題。實驗將重要節(jié)點信任傳播算法分別應(yīng)用于Epinions、FilmTrust和Douban三個真實數(shù)據(jù)集，對數(shù)據(jù)集中的社交信息進行優(yōu)化。具體實驗結(jié)果如表3所示，其中N-TP表示社交網(wǎng)絡(luò)圖原始的邊數(shù)，TP表示經(jīng)過信任傳播算法優(yōu)化后的新的社交網(wǎng)絡(luò)圖的邊數(shù)。

表3 INTP優(yōu)化前后信任邊數(shù)對比Table 3 Comparison of trust sides before and after INTP optimization

由表3中三個數(shù)據(jù)集上的對比實驗可以看出，經(jīng)過INTP算法優(yōu)化的社交網(wǎng)絡(luò)的邊數(shù)得到增加。實驗結(jié)果表明INTP算法可以有效地緩解社交數(shù)據(jù)的稀疏性問題。

4.3.3 INTP算法應(yīng)用效果實驗

本組實驗的目的是，將INTP算法應(yīng)用到其他推薦算法上，以驗證其在全局數(shù)據(jù)上的推薦效果。實驗分為兩部分：（1）將INTP算法融入到SoRec算法和TrustPMF算法中進行實驗，使用RMSE作為評價指標與原始實驗算法效果對比，來驗證信任傳播算法在提高推薦算法精度上的有效性；（2）使用準確率、召回率和F1值作為衡量推薦質(zhì)量的指標，將INTP算法融入到SoRec算法中與其他方法推薦效果對比，來驗證信任傳播算法在提高推薦算法準確度上的有效性。對比結(jié)果如表4、5所示。

表4 INTP評分預(yù)測精度實驗Table 4 Score prediction accuracy experiment of INTP

通過表4中的實驗數(shù)據(jù)可以看出，將INTP算法融入SoRec算法和TrustPMF算法，能使推薦算法的精度提高，說明將INTP算法融入到推薦系統(tǒng)中可以有效地提高推薦效果。

表5中的粗體為五種方法得到的實驗結(jié)果在該數(shù)據(jù)集上的最大值。從表5中可以看出，與CF、PMF這些傳統(tǒng)的協(xié)同過濾推薦算法相比，融入社交信息的社會化推薦算法INTP-Rec表現(xiàn)更好，說明向推薦算法中融入社交信息能提高推薦算法的有效性。與使用原始社交信息的SoRec算法相比，緩解了社交信息稀疏性問題的INTP-Rec算法表現(xiàn)更好，說明了INTP-Rec算法能有效地提高推薦算法的精度，得到更好的推薦結(jié)果。對于整體實驗結(jié)果而言，本文方法在準確率、召回率和F1值上，均比其他方法在一定程度上得到提高，表明本文方法可以有效地提高推薦算法的質(zhì)量。

表5 項目推薦質(zhì)量實驗Table 5 Recommended quality experiment

5 結(jié)束語

為解決社交網(wǎng)絡(luò)中信任數(shù)據(jù)稀疏問題和二值數(shù)據(jù)難以反映社交網(wǎng)絡(luò)整體結(jié)構(gòu)問題，本文提出結(jié)合重要節(jié)點信任傳播的社會化推薦算法（INTP-Rec）。首先利用重要節(jié)點信任傳播算法（INTP），增加重要節(jié)點與其他節(jié)點之間的連接，并通過實驗驗證了該方法在豐富社交信息上的有效性。之后將優(yōu)化后的社交網(wǎng)絡(luò)上的二值數(shù)據(jù)進行加權(quán)量化，以進一步反映社交網(wǎng)絡(luò)的整體結(jié)構(gòu)信息。最后，在三個公開數(shù)據(jù)集上的實驗表明，本文提出的結(jié)合重要節(jié)點信任傳播的社會化推薦算法可以提高社會化推薦算法的準確率、召回率和F1值，達到了更好的推薦效果。