融合信任傳播和混合相似性度量的推薦算法

楊 磊，劉美枝

(山西大同大學物理與電子科學學院，山西大同 037009）

協(xié)同過濾(Collaborative Filtering,CF)是最成熟、應用最廣泛的推薦算法之一，它可以分為基于模型的方法和基于內(nèi)存的方法。但是協(xié)同過濾算法的信息源僅僅來自用戶評分矩陣，而用戶評分的項目數(shù)量比較少，甚至用戶從未對任何一個項目進行過評分，會導致稀疏性和冷啟動問題。近年來，為了解決稀疏性和冷啟動問題，學者們致力于挖掘額外信息建立訓練模型，比如將社交網(wǎng)絡信息融入推薦模型，尤其是信任關系。

1 相關工作

經(jīng)典的信任模型有TidalTrust 模型[1]和Mole-Trust 模型[2]，此外，Ma H 等提出一種基于矩陣分解的協(xié)同推薦算法RSTE，將用戶信任關系融合到概率矩陣分解模型中，充分利用用戶之間的信任值來訓練用戶特征向量[3]；Jamali 等在基于項目的協(xié)同過濾算法基礎上融合信任關系，提出隨機游走(Trust Walker)推薦策略，隨后又在矩陣分解的社交推薦模型的基礎上，引入了信任傳播，提出了SocialMF 模型，可以有效緩解冷啟動問題[4]；Ma H 等同樣基于概率矩陣分解，結(jié)合用戶社交與用戶評分信息，提出SoRec 模型[5]；Yao 等結(jié)合顯性和隱性交互信息，提出RoRec 模型[6]；Qian 等提出一種結(jié)合用戶興趣和社交圈的個性化推薦算法，將個人興趣、人際興趣相似性、人際交互三個社會因素融合起來，用于解決冷啟動和數(shù)據(jù)稀疏問題[7-8]；Qu 等將知識圖譜和圖神經(jīng)網(wǎng)絡引入到社交網(wǎng)絡中，提出KNI模型[9]；Wang 等提出一種用于個性化推薦的深度聯(lián)合神經(jīng)網(wǎng)絡，用以解決隱性反饋的推薦問題[10]；Guo等將顯性信任和隱性信任融合到SVD++中，提出TrustSVD 模型[11]；鮮征征等在TrustSVD 的基礎上引入差分隱私保護技術，提出DPTrustSVD 算法[12]；Wang 等從社會學角度出發(fā)，研究信任關系的發(fā)展規(guī)律，提出SocialTrust 模型[13]；Zheng 等在推薦系統(tǒng)中引入超圖拓撲結(jié)構，提出HMF 模型[14]；陳玲姣等將用戶信任關系引入到基于擴散的推薦算法中，提出一種基于信任關系的資源分配算法[15]。上述推薦算法中，有利用局部、全局相似度提高推薦性能的，也有利用信任傳播挖掘用戶隱性信任關系的，但是沒有將信任傳播和混合相似度同時融合到算法中。

在社交網(wǎng)絡推薦算法的基礎上，提出一種融合信任傳播和混合相似性度量的推薦算法(Recommendation Algorithms for Fusion Trust Propagation and Hybrid Similarity Measurement,TPHS)，利用信任傳播機制，預測缺失信任值，完善用戶之間的信任網(wǎng)絡，進而克服信任矩陣的稀疏性和冷啟動問題；利用混合相似性度量，更好地描述用戶之間的相似性；綜合考慮用戶之間的信任關系和相似性關系，進行預測評分，得出推薦列表。

2 算法描述

2.1 社交網(wǎng)絡

在推薦系統(tǒng)中引入社交網(wǎng)絡和信任關系能夠有效緩解稀疏性和冷啟動問題，如圖1(a)所示社交網(wǎng)絡，每個節(jié)點代表一個用戶，每條有向邊代表信任關系。在信任矩陣中T=[Tu,v]N*N，Tu,v代表用戶u對用戶v的信任值為value，其中value∈[0,1]。需要注意的是，信任關系是單向的，即信任矩陣是非對稱的，如圖1(b)所示。

圖1 社交網(wǎng)絡

推薦系統(tǒng)中的信任關系包括顯性信任和隱式信任，通常將數(shù)據(jù)集中明確表明某用戶對其他用戶的信任值稱為顯性信任，如Epinions 數(shù)據(jù)集，用戶u將對其他用戶的信任值添加到自己的信任列表中，但是對于沒有信任關系的數(shù)據(jù)集，如Movielens 數(shù)據(jù)集，可以通過評分矩陣計算其信任關系，將直接通過評分矩陣計算的信任值稱為顯性隱式信任；而隱性信任是在指在數(shù)據(jù)集中沒有明確表明或者通過計算顯性隱式信任依然缺失的信任關系，但可以通過信任傳播推導出來，以彌補信任關系無法獲取或稀疏的問題。

對于沒有信任關系的數(shù)據(jù)集，計算顯性隱式信任值是基于一個假想：用戶u和用戶v共同評價過的項目越多，且對于同一項目i，用戶u對其評分rui與用戶v對其評分rvi的差值越小，表示用戶u與用戶v具有越高的興趣相似度，用戶u和用戶v之間的信任關系越強[16]。利用用戶評分矩陣，可以計算用戶之間的顯性隱式信任值Tu,v，其計算公式如下：

其中，Iuv表示被用戶u用戶v共同評分過的項目集，L 代表評分矩陣中評分最大值與最小值的差值，比如Movielens 數(shù)據(jù)集中最高評分為5，最低評分為0，那么L=5。

但是Tu,v沒有考慮用戶的活躍度以及共同評分項目的數(shù)量，用戶活躍度是指用戶評分過的項目數(shù)量，比如，用戶u是一位批發(fā)商，其活躍度很高，而用戶是一位普通用戶v，活躍度較低，用戶u、用戶v與用戶w共同評分過的項目都為1，且評分差值相同，那么按公式(1)計算信任關系時，Tu,w和Tv,w的值相同，但這顯然是不合常理的，在此引入基于用戶的Jaccard加權相似性度量，將公式(1)改進為：

其中，Iu和Iv分別表示被用戶u和用戶v評價過的項目集。

評分矩陣本身具有稀疏性，當用戶之間不存在共同評價過的項目時，就無法計算用戶之間的顯性隱式信任值，則社交網(wǎng)絡中信任關系也存在著稀疏性問題，為了能夠進一步挖掘用戶之間的信任關系，基于信任關系具有傳遞性的特性，在此引入信任傳播機制。

2.2 信任傳播機制

信任傳播理論是基于一種假想：假如用戶a（源用戶）信任用戶b（中間用戶），用戶b信任用戶c（目標用戶），那么用戶a在某個程度上信任用戶c，即信任可以傳播[16]。如果源用戶到目標用戶之間存在多個中間用戶，即存在多跳路徑，在此，先定義一下信任傳播跳數(shù)。

定義1 信任傳播跳數(shù)k。在社交網(wǎng)絡中，任選兩個用戶作為源用戶和目標用戶，從源用戶傳播信任到目標用戶所經(jīng)過的跳數(shù)，記為k。

在圖1所示社交網(wǎng)絡中，從用戶u1到用戶u3需要兩跳，而從用戶u1 到用戶u5 需要三跳。對于信任多跳傳播，需要一種聚合方法來計算源用戶對目標用戶的信任值，常用的信任路徑聚合方法有：最大值，最小值和平均值。考慮到不同信任傳播跳數(shù)對信任傳播的貢獻不同，所以采用加權平均聚合的方法，對于任意用戶a,b,c∈U，用戶a對用戶c的隱式信任值為：

其中，Na表示用戶a到用戶c的中間用戶的集合，且∈[λ,1]，表示用戶a對用戶b的顯性隱式信任值，參數(shù)λ∈(0,1]是可調(diào)信任閾值；一般認為近距離信任傳播比起遠距離傳播應該分配更高的信任分值，在此引入路徑權值，αk表示傳播路徑的權值，其中，kMAX表示信任傳播的最大跳數(shù)。例如，如果kMAX設置為3，則信任關系最遠傳遞距離為3跳，那么，如果源用戶到目標用戶的路徑為兩跳，則α2=(3-2+1)/3=0.667，如果源用戶到目標用戶的路徑為三跳，則α3=(3-3+1)/3=0.334。

2.3 混合相似度

推薦算法一般根據(jù)用戶的歷史評分數(shù)據(jù)計算用戶相似度，找到與目標用戶相似度較高的鄰居用戶并產(chǎn)生預測值。在計算用戶相似度時，綜合考慮以下三個方面：①用戶對同一項目的評分時間間隔，引入時間衰減函數(shù)f(t)；②項目的活躍度。一般認為，活躍項目對相似度的貢獻應該小于不活躍的項目，引入活躍度衰減因子，對活躍項目進行懲罰；③用戶對共同評分項目的評分差值。一般認為，兩用戶共同評分的項目越多，且對同一項目評分差值越小，用戶之間的相似度越高，皮爾遜相似度可以較好的反映用戶評分差值對相似度的影響，所以采用皮爾遜相似度。綜合考慮上述三個方面，用戶u和用戶v的混合相似度為：

其中，α∈[0,1]，是一個權重因子，λ是一個時間衰減調(diào)節(jié)因子，用于調(diào)節(jié)衰減速度，t表示用戶u和用戶v對同一項目評分的時間間隔，Iuv表示被用戶u和用戶v共同評價過的項目集，Iu和Iv分別表示被用戶u和v評價過的項目集，rui和rvi分別表示用戶u和用戶v對項目i 的評分，分別表示用戶u和用戶v對所有評價過項目的評分均值，是基于時間衰減和活躍項目懲罰的相似度，是基于共同評分項目的評分差值的相似度。

2.4 加權評分預測與推薦

依據(jù)信任傳播機制（即公式3），可以獲取目標用戶u與其他用戶的隱式信任值，采用Top-n方法，選取隱式信任值最高的n 個用戶作為最信任鄰居集合NTrust。同樣，依據(jù)混合相似性度量（即公式5），可以獲取目標用戶u與其他用戶的混合相似性。由于計算混合相似性時，存在用戶冷啟動問題，所以采用相似性閾值法，即選取與目標用戶的混合相似性超過一定閾值的用戶作為最相似鄰居集合NSim。然后利用下述公式進行評分預測。

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

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

實驗采用的數(shù)據(jù)集是Epinions(來源于Epinions.com)和Movielens，評分數(shù)據(jù)均采用5 分制評分，數(shù)據(jù)描述如表1。

表1 數(shù)據(jù)集描述

3.2 評價指標

使用平均絕對誤差(MAE)和均方根誤差(RMSE)來計算評分預測準確性，并引入影響指標(Influence) 來優(yōu)化參數(shù)設置，其值越小，表示推薦效果越好，計算方法如下式：

在衡量方案性能時，還需要用到召回率、準確率，其中召回率和準確率的值越大，說明推薦的效果越好。

3.3 結(jié)果分析

為了評價算法的性能，將提出的算法與以下幾種推薦算法進行對比：

(1) RSTE：基于矩陣分解的協(xié)同推薦算法，在算法中融入了用戶之間的顯性信任關系，但是不考慮信任傳播。

(2) SoRec：基于概率矩陣分解，結(jié)合用戶社交關系與評分信息。

(3) SocialMF:基于矩陣分解的社交推薦模型，引入信息傳播機制。

(4) TPHS：融合信任傳播和混合相似性度量的推薦算法，即本算法。

3.3.1 TPHS 算法中參數(shù)調(diào)優(yōu)

在計算用戶混合相似度時，引入時間衰減調(diào)節(jié)因子λ和權重因子α，因此，需要調(diào)優(yōu)λ和α。首先在Epinions 數(shù)據(jù)集中，設置λ=0.2，使α在0.0 到1.0 范圍內(nèi)以0.1為步長調(diào)優(yōu)，實驗結(jié)果如圖2。從公式可5可知，當α=0 時，則用戶相似度只考慮用戶對共同評分項目的評分差值，此時的相似度為皮爾遜相似度；當α=1 時，則用戶相似度只考慮用戶對同一項目的評分時間間隔、項目的活躍度以及用戶共同評分項目的數(shù)量。由圖可知，當α=0.6時，影響取得最小值。其次，設置α=0.6，使λ在0.0 到1.0 范圍內(nèi)以0.1 為步長調(diào)優(yōu),實驗結(jié)果如圖3。從公式8 可知，當λ=0 時，f(t)=1，表示不考慮用戶對同一項目的評分時間間隔因素，由圖可知，當λ=0.3 時，影響取得最小值。

圖2 參數(shù)α對TPHS算法的影響

圖3 參數(shù)λ對TPHS算法的影響

根據(jù)實驗結(jié)果，可以得出對比單一相似性度量，引入混合相似度和時間衰減因子對推薦效果有積極影響，因此，在下文所述實驗中將α設置為0.6，λ設置為0.3。

3.3.2 推薦性能分析

實驗1 推薦精度對比。為了評價評分預測的準確性，使用平均絕對誤差(MAE)和均方根誤差(RMSE)指標。實驗中隨機選取數(shù)據(jù)集中50%的數(shù)據(jù)當做訓練集，其余50%當做測試集，然后進行不同算法的實驗，實驗結(jié)果為5 次實驗的平均值，具體情況如表2。由表可知，本算法在推薦精度方面相較其他算法效果更好。

表2 不同算法的MAE和RMSE比較

實驗2 算法對稀疏性的影響。為了評價推薦算法改善數(shù)據(jù)稀疏性能力，查看算法性能對訓練數(shù)據(jù)的依賴程度，引入比例因子β，β是訓練集占數(shù)據(jù)集的比例，如β=0.1，表示在數(shù)據(jù)集隨機選取10% 的數(shù)據(jù)作為訓練集，其余90% 的數(shù)據(jù)作為測試集，實驗中，使β以0.1 為步長從0.1增長到0.9。圖4 和圖5 分別表示各種算法在不同比例因子下的召回率和準確率，橫軸表示訓練集占數(shù)據(jù)集的比例，縱軸分別為召回率和準確率。當β值越小，即訓練集中的數(shù)據(jù)越少，評分網(wǎng)絡和信任網(wǎng)絡越稀疏，越符合冷啟動的條件，從圖中可知，提出算法TPHS 在β值較小時，召回率和準確率明顯高于其他三種算法，比如在β=0.2 時，在Epinions 數(shù)據(jù)庫中，召回率相較SocialMF、SoRec 和RSTE 算法分別提高了2.5%、4.1% 和4.7%，在Movielens 數(shù)據(jù)庫中，召回率相較SocialMF、SoRec 和RSTE 算法分別提高了0.27%、1.28% 和2.44%；在Epinions 數(shù)據(jù)庫中，準確率相較SocialMF、SoRec 和RSTE 算法分別提高了3.4%、6.7% 和6.9%，在Movielens 數(shù)據(jù)庫中，準確率相較SocialMF、SoRec 和RSTE 算法分別提高了1.8%、3.1%、3.9%。而且隨著β值，曲線的上升速率也略高于其他算法。也就是說在數(shù)據(jù)稀疏的情況下，提出算法TPHS 融合了信任傳播和混合相似性度量，可以有效克服數(shù)據(jù)稀疏給推薦結(jié)果帶來的負面影響，進而有更好的推薦性能。

圖4 不同算法的召回率

圖5 不同算法的準確率

4 結(jié)論

充分利用用戶評分信息和社交信任關系，提出一種融合信任傳播和混合相似性度量的推薦算法。主要思路為：首先，在社交信任網(wǎng)絡的基礎上，融入一種信任傳播機制，有效解決社交信任網(wǎng)絡稀疏性的問題；其次，在計算用戶間的相似性時，采用混合相似性度量，綜合衡量用戶之間的相似性；最后在進行評分預測時，綜合考慮用戶之間的信任關系和相似性關系，進而給出推薦結(jié)果。實驗結(jié)果表明，本算法在召回率和準確率性能方面明顯優(yōu)于其他算法，尤其是當訓練集數(shù)據(jù)較少時，能夠有效緩減稀疏性和冷啟動問題。下一步工作將考慮信任傳播的時間成本問題以及不同傳播跳數(shù)對推薦性能的影響。