融合時間加權(quán)信任與用戶偏好的協(xié)同過濾算法

張岐山，朱 猛

福州大學 經(jīng)濟與管理學院，福州 350108

在互聯(lián)網(wǎng)信息過載的時代，推薦系統(tǒng)可以幫助用戶快速獲取自身需要的信息，且在解決難以描述的需求以及個性化需求上表現(xiàn)更好[1]。推薦系統(tǒng)主要包括協(xié)同過濾推薦、基于內(nèi)容的推薦以及混合推薦[2]，其中協(xié)同過濾推薦在互聯(lián)網(wǎng)推薦系統(tǒng)中應用的較多，尤其是基于用戶的協(xié)同過濾算法，從用戶的角度挖掘用戶潛在的興趣偏好，更符合個性化的推薦，此外，協(xié)同過濾應用范圍也較廣，對于無法量化的特征，僅使用評級數(shù)據(jù)也能取得較好的效果[3]，但由于數(shù)據(jù)稀疏性[4]以及用戶興趣動態(tài)變化[5]等問題導致推薦精度不足。

現(xiàn)實中，人們更愿意相信好友推薦的物品，因此信任在推薦系統(tǒng)算法中的應用受到了廣泛的關(guān)注，尤其對于數(shù)據(jù)稀疏的問題，輔助使用用戶信任關(guān)系的效果比傳統(tǒng)的協(xié)同過濾更好[6-7]。文獻[8]定義了兩種信任類型，分別是從用戶角度和項目角度的正確推薦占比，并把它們整合到標準的協(xié)同過濾的框架中，提高了推薦的準確性。文獻[9]使用用戶間的預測誤差和用戶共同評分數(shù)來計算直接信任，對于沒有共同評分項的用戶，構(gòu)建間接信任來緩解數(shù)據(jù)稀疏性。文獻[10]利用用戶之間的交互次數(shù)得到直接信任，并通過等效電阻理論的距離度量方式計算間接信任，但計算直接信任時忽略用戶的評分。

雖然信任在推薦算法中的應用在一定程度上改善了推薦結(jié)果，但在數(shù)據(jù)極其稀疏時，根據(jù)用戶對項目的評分行為建立的用戶關(guān)系并不能反應出用戶關(guān)系的真實情況，通過用戶對項目標簽的偏好程度能進一步挖掘出用戶之間的偏好關(guān)系。文獻[11]將用戶對項目標簽的評分頻率作為用戶對項目標簽的偏好程度。文獻[12]將用戶對項目標簽評分的平均值與該用戶對所有項目的評分平均值的比值作為用戶對項目標簽的偏好程度。以上研究通過用戶對項目標簽的偏好程度緩解了數(shù)據(jù)稀疏性。

然而，用戶興趣并非靜態(tài)的，而是會隨時間而變化，因此越來越多的學者在推薦系統(tǒng)中融入時間因素。文獻[13]提出基于遺忘曲線規(guī)律進行時間衰減，擬合艾賓浩斯曲線得到用戶興趣隨時間變化的函數(shù)。文獻[14]提出了一種融合時間因素和用戶評分特性的協(xié)同過濾算法，將用戶對項目評分的時間間隔作為時間權(quán)重并融入到預測偏好得分中進行推薦。文獻[15]使用logistic作為時間衰減函數(shù)，并將其考慮進相似度的計算中，提高了推薦精度。以上融合時間因素的算法均改善了推薦精度，但沒有考慮到用戶評分時間的不均勻，仍有進一步優(yōu)化的空間。

針對以上問題，本文提出了融合時間加權(quán)信任與用戶偏好的協(xié)同過濾算法。該算法首先結(jié)合用戶評分的相對時間間隔和用戶在該時段的評分數(shù)量占比計算出時間權(quán)重，根據(jù)用戶之間共同的評分項目并加入用戶對項目的時間權(quán)重得出用戶的直接信任。其次，將信任傳遞的中間節(jié)點的個人信譽度作為信任傳遞路徑的可靠性權(quán)重得到間接信任。然后，結(jié)合用戶對項目標簽的評分數(shù)量占比以及評分值占比得到用戶對各個項目標簽的偏好程度，建立用戶-項目標簽偏好矩陣，計算出用戶之間的偏好相似度。最后，綜合用戶信任度與偏好相似度對用戶進行推薦。本文的貢獻主要體現(xiàn)在以下三個方面：

（1）考慮到用戶評分時間的不均勻，結(jié)合用戶評分的相對時間間隔和用戶在該時段的評分數(shù)量占比計算出時間權(quán)重，并將時間權(quán)重融入到直接信任計算中，緩解用戶興趣動態(tài)變化的問題。

（2）考慮傳遞中間節(jié)點的個人信譽度，將信任傳遞的中間節(jié)點的個人信譽度作為信任傳遞路徑的可靠性權(quán)重得到間接信任，緩解數(shù)據(jù)的稀疏性。

（3）綜合考慮用戶對每個項目標簽的評分數(shù)量占比以及評分值占比的影響，對二者進行調(diào)和平均，建立用戶-項目標簽偏好矩陣，進一步緩解數(shù)據(jù)的稀疏性。

1 融合時間加權(quán)信任與用戶偏好的協(xié)同過濾算法

1.1 融合時間因素的直接信任計算

1.1.1 時間權(quán)重的改進

用戶的興趣會隨時間的變化而變化，在早期對某個項目不感興趣的用戶可能過段時間會產(chǎn)生興趣，所以用戶最近對項目的評分更能反映用戶當前的興趣。

一些學者[14-16]使用用戶評分時間間隔來刻畫用戶興趣變化，這種方法的理想狀態(tài)是每個用戶評分時間間隔是均勻的，然而實際中并非如此，用戶評分時間存在密集區(qū)和非密集區(qū)，此時，用戶在一段時間內(nèi)對評價項目的記憶程度不僅與間隔的時間長短有關(guān)，還與用戶在該時段內(nèi)評價的項目個數(shù)有關(guān)。通過結(jié)合用戶相對評分時間間隔和用戶在該時段的評分數(shù)量占比作為時間權(quán)重能夠使密集區(qū)的時間權(quán)重適當減小，非密集區(qū)的時間權(quán)重適當增大，從而使用戶興趣隨時間的變化過程更加平滑，在用戶評分時間非均勻的情況下，提升刻畫用戶興趣變化的準確程度。改進后的時間權(quán)重公式如下：

其中t u,i是指用戶u對項目i評分的相對時間間隔，n u,i表示用戶在T u,i到T umax的時段內(nèi)的評分數(shù)量占比，Tu,i表示用戶u對項目i的評分時間，T umax和T umin分別表示用戶u最晚和最早的評分時間，numT umax-Tu,i表示用戶u在T u,i到Tumax的時段內(nèi)的評分個數(shù)。

1.1.2 融合時間因素的直接信任度

傳統(tǒng)的信任模型忽略了時間對用戶興趣變化的影響，從而在一定程度上影響了推薦的準確性。JMSD在計算用戶之間的相似關(guān)系已被證明具有較好的性能[17]，但是沒有考慮到時間因素，因此，本文將改進后的時間權(quán)重融入到JMSD來衡量用戶之間的直接信任關(guān)系，公式如下：

考慮到用戶之間的評分偏好不同，有的用戶評分比較寬松，評分較高，有的用戶評分比較嚴格，評分較低，定義信任調(diào)整因子來增強信任，公式如式（5）所示，其中，μu和σu分別表示用戶u的評分均值和評分方差。

信任具有非對稱性，比如用戶A信任用戶B，但用戶B不一定信任用戶A，或者用戶B信任用戶A，但信任的程度不一定相同，所以用戶u對用戶v的直接信任的公式如下：同理，用戶v對用戶u的直接信任為：

1.2 間接信任計算的改進

直接信任是根據(jù)用戶之間共同評分項目的基礎上進行的，而有的用戶之間可能沒有共同評分的項目，從而導致沒有信任關(guān)系，為了更進一步的挖掘用戶之間的隱藏信息，考慮信任的傳遞性。如果用戶a信任用戶b，用戶b信任用戶c，則認為用戶a也信任用戶c。傳遞信任隨著用戶增多信任度減少，以及傳遞的路徑越長，存在的誤差越大，所以本文采用兩級路徑傳播。

當用戶u和v之間只存在一條傳遞路徑時，間接信任為該條路徑上最小的直接信任值，當存在多條傳遞路徑時，采用最小-最大復合的方法得到間接信任[9]，但該方法沒有考慮用戶的個人信譽度。由于本文的直接信任是依據(jù)用戶之間的共同評分項得到的，而用戶個人信譽度是由用戶的評分數(shù)量以及評分準確度組成[18-19]，用戶的評分數(shù)量越多、評分準確度越高，則用戶的個人信譽度越高，通過計算得到的該用戶對其他用戶的信任值也越可靠。其中用戶的個人信譽度PT(u)為：

其中，w(u)、E(u)分別為評分數(shù)量權(quán)重和評分準確度，H為所有用戶的平均評分個數(shù)，|I u|表示用戶u的評分個數(shù)，S為項目的最高評分。

因此，考慮用戶的個人信譽度，使用中間節(jié)點的個人信譽度作為該路徑的可靠性權(quán)重，先選取每條傳遞路徑的最小直接信任，其次將每條傳遞路徑的中間節(jié)點的個人信譽度與對應的最小直接信任相乘，選出產(chǎn)生最大值的傳遞路徑，進而取該條路徑上的最小信任值作為間接信任。改進后的間接信任的公式如下：

其中，K表示用戶u和用戶v之間共同信任的用戶集合，k*為得到的最可靠的傳遞路徑的中間節(jié)點。

綜合用戶的直接信任和間接信任，則用戶間的最終信任如下式所示：

1.3 用戶偏好相似度的改進

用戶對項目標簽的偏好程度可以反映出用戶對各種類型的電影的喜好程度，用戶之間對項目標簽的偏好程度越相似，他們之間的偏好相似度就越高，當數(shù)據(jù)非常稀疏，用戶之間的共同評分項很少時，通過用戶之間對項目標簽的偏好相似程度綜合考慮用戶之間的共同評分項以及非共同評分項，能極大緩解數(shù)據(jù)稀疏性。在計算用戶對項目標簽的偏好程度時，文獻[11]沒有考慮評分值的大小；文獻[12]忽略了用戶在項目標簽上的評分數(shù)量。然而假設用戶A對項目標簽x1的評分記錄為[4，4，4，4，4，4]，對項目標簽x2和x3的評分記錄分別為[5，5]、[2，2，2]，則顯然γA,x1＞γA,x2＞γA,x3，γA,x表示用戶對項目標簽的喜好程度。因此，本文中用戶對項目標簽的偏好程度由重要性權(quán)重和評分率權(quán)重兩部分組成。

（1）重要性權(quán)重

重要性權(quán)重是指用戶在所評價過的項目中，每個項目標簽包含的項目數(shù)量所占的比例，計算公式如下：

其中，N u,x表示用戶u評價過屬于標簽x的項目的數(shù)量。

（2）評分率權(quán)重

評分率權(quán)重是指用戶在所評價過的項目中，每個項目標簽的評分和與該用戶所有評價過的項目的評分和的比值，計算公式如下：

Sumu,x表示用戶u對屬于標簽x項目的評分和，Sumu表示用戶u的評分總和。

重要性權(quán)重和評分率權(quán)重分別從用戶對項目標簽的評價數(shù)量以及評分值兩個角度刻畫用戶對項目標簽的偏好程度，本文認為二者對獲取用戶對項目標簽的綜合偏好程度同等重要，當重要性權(quán)重和評分率權(quán)重同時大時，用戶對項目標簽的綜合偏好程度才大。因此，對二者采用調(diào)和平均計算用戶對項目標簽的綜合偏好程度，且調(diào)和平均受極小值的影響比受極大值的影響更大，在用戶對項目標簽的評價數(shù)量占比較大、評分值占比較小或者評價數(shù)量占比較小、評分值占比較大的情況時，能夠獲得更加合理的綜合偏好程度。用戶對項目標簽x的綜合偏好程度γu,x的公式為：

通過提取項目特征能緩解推薦系統(tǒng)中存在的數(shù)據(jù)稀疏性問題[20]，由于項目標簽遠小于項目數(shù)量，且一個項目又可包含多種項目標簽，則根據(jù)用戶對項目標簽的綜合偏好程度建立用戶-項目標簽的偏好矩陣在稀疏程度上遠小于用戶-項目評價矩陣的稀疏程度，根據(jù)偏好矩陣計算用戶之間的偏好相似度，能夠較準確地挖掘出沒有共同評分項或共同評分項較少的用戶之間的相似度，偏好相似度如式（17）所示，其中X為所有項目標簽的集合。

1.4 融合信任度和偏好相似度推薦

本文通過設置參數(shù)β，綜合考慮用戶的信任度和偏好相似度，將用戶之間的偏好相似度和信任度進行線性加權(quán)，見公式（18）：

根據(jù)融合后的權(quán)重weight(u,v)，從大到小進行排序，取前top-S個用戶作為最近鄰居集S u，用戶u對項目i的喜好程度p ui可由公式（19）計算得出：

2 算法描述

2.1 算法步驟

融合時間加權(quán)信任與用戶偏好的協(xié)同過濾算法的具體推薦步驟如下：

輸入：用戶項目評分矩陣，用戶評分時間矩陣以及項目標簽矩陣。

輸出：用戶的推薦列表

步驟1通過用戶評分時間矩陣和式（1）計算用戶對已評價項目的時間權(quán)重，將時間權(quán)重融入JMSD中，然后依據(jù)公式（6）、（7）計算用戶之間的直接信任。

步驟2根據(jù)公式（8）~（10）計算出用戶的個人信譽度，將個人信譽度作為信任聚合的權(quán)重，利用公式（11）、（12）得到用戶之間的間接信任。

步驟3根據(jù)式（13）得到用戶之間的綜合信任度。

步驟4通過項目標簽矩陣以及式（14）~（16）建立用戶-項目標簽的偏好矩陣，然后利用公式（17）計算用戶之間對項目標簽的偏好相似度。

步驟5將用戶之間的綜合信任度與偏好相似度進行線性加權(quán)得到用戶之間的綜合相似度。

步驟6取步驟5中得到用戶綜合相似度進行降序排列，并取前S個用戶作為最近鄰居集。

步驟7根據(jù)式（19）計算用戶對未評價項目的喜好程度，并對其進行降序排列，取前k個項目作為推薦列表。

步驟8重復步驟6和7，為所有用戶生成推薦列表。

2.2 算法分析

本文提出的融合時間加權(quán)信任與用戶偏好的協(xié)同過濾算法主要由兩部分組成，一部分是考慮用戶興趣動態(tài)變化的信任關(guān)系度量算法，這部分算法結(jié)合用戶評分相對時間間隔與用戶在該時段的評分數(shù)量占比作為時間權(quán)重，能夠使用戶評分密集區(qū)的時間權(quán)重適當減小、非密集區(qū)的時間權(quán)重適當增大，使用戶興趣隨時間的變化過程更加平滑，在一定程度上緩解由近期處于非密集區(qū)的用戶興趣隨時間變化過快的問題，進而獲取更準確的用戶近期信任關(guān)系，提升推薦精度，同時，直接信任是依據(jù)用戶之間的共同評分項，而用戶的評分數(shù)量越多、評分準確度越高，用戶的個人信譽度也越高，計算得到的該用戶對其他用戶的信任值也越可靠，因此，將傳遞中間節(jié)點的個人信譽度作為傳遞路徑的可靠性權(quán)重，能夠修正通過信譽度不高的用戶獲取間接信任的誤差，進而提升推薦精度；另一部分是用戶對項目標簽的偏好相似性度量算法，這部分算法綜合考慮用戶對項目標簽的評價數(shù)量與評分值，緩解用戶對項目標簽的評價數(shù)量與評分值出現(xiàn)一大一小的情況時，僅依據(jù)評價數(shù)量或評分值刻畫出的用戶對項目標簽的偏好程度存在偏大或偏小的問題，從而提高用戶偏好的準確度；最后通過融合這兩部分算法能夠更加準確地刻畫用戶偏好，對于用戶之間共同評分項較少，使得獲取的信任關(guān)系存在誤差的問題，可以通過用戶之間在項目標簽的偏好相似度修正僅依靠信任關(guān)系進行推薦的誤差，獲取更精準的鄰居集，從而緩解由數(shù)據(jù)稀疏性導致的推薦性能不高的問題。

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

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

本次實驗采用的是MovieLens 100K數(shù)據(jù)集，Movie-Lens100k數(shù)據(jù)集是由GroupLens Research采集的多個用戶對多部電影的評級數(shù)據(jù)以及電影標簽信息等數(shù)據(jù)組成。該數(shù)據(jù)集包括943個用戶對1 682部電影的100 000條評分，評分是1~5的整數(shù)，表示用戶對電影的喜好程度，每個用戶的評分個數(shù)不小于20條，電影有18種標簽信息，主要包括喜劇、動作、科幻和動畫等等，隨機選取80%作為訓練集，20%作為測試集。該電影數(shù)據(jù)集的數(shù)據(jù)稀疏度為93.70%。

3.2 評價標準

采用推薦系統(tǒng)常用的召回率recall@k、精確率precision@k以及F1值作為評價指標，k表示給用戶推薦的列表長度。公式如下：其中，R(u)為本文算法通過訓練集獲得的電影推薦列表，T(u)為用戶在測試集中評分的推薦列表。

3.3 實驗結(jié)果分析

3.3.1 實驗參數(shù)分析

（1）參數(shù)α的取值對TTUPCF算法的影響

實驗中，取β為0.3，用戶近鄰個數(shù)為20，推薦列表的長度為20，α值從0增大到1，每次以0.1為單位遞增，從而確定一個最優(yōu)的α值。圖1給出了α的取值對召回率和準確率的影響。從圖1中可以看出，召回率和精確率隨著α的取值總的來說是先增大后減小的趨勢，在α=0.7時，召回率和精確率均取得最大值，比α=1時提高了1.20%，由此可以說明，結(jié)合用戶相對評分時間間隔和用戶在該時段的評分數(shù)量占比作為時間權(quán)重在刻畫用戶興趣隨時間變化的準確程度上比只采用用戶相對評分時間間隔作為時間權(quán)重更高，具有更好推薦效果。

圖1 α值對TTUPCF算法的影響Fig.1 Effect ofαon TTUPCF algorithm

另外，從實驗結(jié)果可以看出，α取得最優(yōu)值時較大，即用戶相對評分時間間隔占比較大、用戶在該時段的評分數(shù)量占比較小。這是由于當某些用戶評分時間的非密集區(qū)的時間跨度較大時，用戶評分數(shù)量占比越大，會使用戶對非密集區(qū)的項目的遺忘程度急劇減小，產(chǎn)生的誤差也越大。因此，在用戶在該時段的評分數(shù)量占比較小時，才能有效地平滑用戶興趣隨時間的變化程度。

（2）參數(shù)β的取值對TTUPCF算法的影響

實驗中，取α為0.3，用戶近鄰個數(shù)為20，推薦列表的長度為20，β值從0增大到1，每次以0.1為單位遞增，從而確定一個最優(yōu)的β值，圖2給出了β的取值對召回率和準確率的影響。從圖2中可以看出，召回率和精確率隨著β的取值先增大后減少，當β=0.3時，算法的召回率和精確率的表現(xiàn)最好，比β=0時提高了1.95%，說明在獲取間接信任緩解數(shù)據(jù)稀疏性后，通過用戶對項目標簽的偏好程度計算用戶的偏好相似度在一定程度上進一步緩解了數(shù)據(jù)稀疏性，提高了推薦精度。

圖2 β值對TTUPCF算法的影響Fig.2 Effect ofβon TTUPCF algorithm

從實驗結(jié)果中可以看出，β取得最優(yōu)值時較小，即用戶信任權(quán)重占比較大、用戶偏好相似度占比較小，這是由于項目標簽只有18種，劃分的粒度較為粗糙，得到偏好相似度較信任度大得多。因此，在偏好相似度占比較小時，才能起到更好的調(diào)節(jié)作用。

3.3.2 對改進間接信任的實驗分析

為了研究改進后的間接信任對本文算法的影響，將考慮信任傳遞中間節(jié)點的個人信譽度的模型與不考慮個人信譽度的模型進行對比。實驗中將算法的參數(shù)均設為最優(yōu)值，比較兩者在推薦列表為20，用戶近鄰數(shù)從10增加到70時的F1值的變化情況。

從圖3中可以看出，二者均在用戶近鄰個數(shù)為20時的F1值達到最大值，但考慮個人信譽度的模型的F1值均高于未考慮個人信譽度的模型。說明考慮個人信譽度得到的間接信任較未考慮個人信譽度的間接信任更為可靠，使本文協(xié)同過濾算法獲取的鄰居集更為精準。

圖3 考慮與不考慮個人信譽度對算法的影響Fig.3 Considering and not considering influence of personal reputation on algorithm

3.3.3 各算法性能對比

為驗證本文提出的融合時間加權(quán)信任與用戶偏好的協(xié)同過濾算法（TTUPCF）的性能，將TTUPCF與基于PCC的協(xié)同過濾（PCC）、基于JMSD的協(xié)同過濾算法（JMSD）以及文獻[21]提出的一種融合隱式信任的協(xié)同過濾推薦算法（TCF）進行比較。

如圖4所示，推薦列表長度取20，α=0.7,β=0.3，設置用戶近鄰個數(shù)從10增加到90，步長為10，分析用戶近鄰個數(shù)對各個算法的影響。從圖4中可以看出，TTUPCF算法的F1值隨著用戶近鄰個數(shù)先是增大，在近鄰個數(shù)為20時達到最大值，然后緩慢降低，在近鄰個數(shù)為60后趨于穩(wěn)定，且在不同的近鄰數(shù)下，TTUPCF算法的F1值均高于其他基準算法。其中，PCC在F1值上表現(xiàn)最差，這是由于PCC僅根據(jù)用戶之間的共同評分項來計算用戶之間的相似程度，存在嚴重的數(shù)據(jù)稀疏問題。JMSD在使用共同評分項來度量用戶相似度的基礎上考慮了用戶之間的共同評分項的數(shù)量多少問題，因此在F1值上高于PCC，但未能有效緩解數(shù)據(jù)的稀疏性。TCF通過挖掘潛在的信任關(guān)系，并與用戶之間的相似度進行調(diào)和平均作為推薦權(quán)重，在一定程度上緩解了數(shù)據(jù)稀疏性，因而在F1值上的表現(xiàn)要高于PCC和JMSD，但是未考慮到用戶興趣動態(tài)變化的問題。與上述三種算法相比，TTUPCF在度量用戶間的關(guān)系時，同時考慮到了時間因素、信任關(guān)系以及用戶的偏好相似度，有效地緩解了用戶興趣動態(tài)變化以及數(shù)據(jù)稀疏性的問題，能更加精確地獲得相似用戶群，有效過濾掉不相關(guān)用戶對實驗結(jié)果的影響。通過從多維度的角度全面衡量用戶之間的關(guān)系，可以更加充分地挖掘用戶偏好得到更為相似的近鄰用戶，相應的F1值也更高。

圖4 不同鄰近數(shù)下各算法的F1值對比Fig.4 Comparison of F1 values of each algorithm under different neighbor numbers

4 結(jié)束語

本文提出一種融合時間加權(quán)信任與用戶偏好的協(xié)同過濾算法，考慮用戶評分時間的不均勻改進時間權(quán)重，并將時間權(quán)重融入到JMSD中度量用戶之間的直接信任，緩解用戶興趣動態(tài)變化的問題，并通過信任的傳遞性以及用戶對項目標簽的偏好來緩解數(shù)據(jù)稀疏性，進而獲得更精準的鄰居集，提高推薦精度。實驗結(jié)果表明，與其他基準算法對比，本文算法在F1值有明顯的提高。在接下來的工作中，考慮將用戶信任與不信任與深度學習相結(jié)合來解決信任與不信任的傳遞問題，同時借助知識圖譜挖掘用戶與項目之間的潛在關(guān)聯(lián)也是一個值得研究的方向。