融合用戶信任度與相似度的推薦算法研究

徐 毅，葉衛根，戴 鑫,宋 威，周賢泉

(江南大學 物聯網工程學院,江蘇 無錫 214122)

1 引 言

互聯網在給人們帶來便利的同時，也使得人們獲取相關且有價值的信息變得更加的困難，這便是所謂的信息過載(Information Overload)[1].為了解決該問題,推薦系統(Recommendation Systems,RS)應運而生.基于協同過濾的個性化推薦技術，由于其易于實現、領域無關等特點，已被廣泛的運用于推薦系統中.而基于協同過濾的個性化推薦技術又可分為基于模型(model-based)和基于內存(memory-based)兩類[2].其中，基于內存的過濾又可進一步地分為基于用戶的(user-based)和基于項目(item-based)兩種.這兩者的核心步驟都是采取特定的相似度計算方式計算用戶或是項目之間的相似性，然后選擇若干的用戶或者項目作為最相似的近鄰，再根據近鄰的歷史數據通過加權平均的方式預測出目標用戶對未知項目的評分.最終所產生的是一個產品或是服務的推薦列表推送給目標用戶.而基于模型的協同過濾技術通常采用機器學習、數據挖掘、人工智能等技術在線下對用戶-項目評分矩陣進行訓練學習從而得到一個預測模型，然后在線上再利用該模型去預測目標用戶對未知項目的評分.

由于在線社交網絡的迅速發展，越來越多的學者嘗試著將社交網絡中用戶之間的信息融入到推薦算法中.Ma等人首先將社交網絡中用戶之間的信任關系融合到概率矩陣分解模型(Probabilistic Matrix Factorization,PMF)[3]從而提出了SoRec算法[4]，該算法運用概率矩陣分解的方法對用戶項目評分項目分解的同時也運用概率矩陣分解的方法對用戶之間信任系數矩陣進行了分解.在文獻[5]中Ma等人又進一步提出了SoReg算法，在目標函數中對用戶隱式特征向量加入了信任用戶的限制作用，使得當前用戶的隱式特征向量與其信任用戶的隱式特征向量更加相似.Jamali等人在研究了SoRec算法后發現了其中不足，認為直接信任用戶的影響作用應該放置在目標用戶的隱式特征向量上而不是直接放到項目評分預測上，從而提出了SocialMF算法[6].在文獻[7]中Yang等人結合信任關系與被信任關系對目標用戶推薦的影響，提出了TrustMF算法.Bao等人在文獻[8]中將原本的信任關系分解為不同類別的信任關系，并利用支持向量回歸技術將這些不同類別的信任關系融入到概率矩陣因子分解算法中.Guo等人在經典的SVD++算法中融入隱式的和顯式的信任關系的影響作用，提出了TrustSVD算法[9].胡勛等人[10]使用推土機距離(earth mover′s distance,EMD)實現了跨項目的移動用戶相似度計算，從而提出了一種融合項目特征和移動用戶信任關系的協同過濾推薦算法.李衛平等人[11]首先將社交網絡與用戶評分矩陣構成一個大的矩陣，然后采用隨機梯度下降法對該矩陣進行分解，從而提出一種新的推薦算法.

在本文中我們首先對社交網絡中用戶之間的信任關系矩陣進行重構，以突出那些被很多用戶信任的用戶在信任關系網絡中的影響力.其次，基于重構的信任關系網絡，我們利用用戶之間的信任關系和用戶之間的相似度來構造概率矩陣分解中的用戶特征向量.從而提出SimTrsutMF推薦算法.該算法中我們對信任關系網絡進行了重構，突出那些被很多人信任的用戶地位.同時，通過融入用戶之間的相似度使得到的SimTrsutMF算法能夠更好地反映目標用戶與其信任用戶之間不同的興趣偏好.

2 相關工作

本文提出的推薦算法主要通過對用戶-項目評分矩陣和用戶之間信任關系矩陣進行學習訓練，最終利用訓練得到的算法為目標用戶預測未知項目進行評分.具體而言，假設系統中存在m個用戶，其構成一個用戶集合U={u1,u2,…,um}，同時存在n個項目，其構成一個項目集合I={i1,i2,…,in}，則用戶-項目評分矩陣可表示為R=[rui]m×n，其中元素rui表示用戶u對項目i的評分.基于概率矩陣分解的推薦算法首先假設已觀測到的用戶-項目評分的條件概率服從高斯分布，然后利用最大似然的方法學習得到用戶特征向量以及項目特征向量，并利用用戶特征向量以及項目特征向量為目標用戶預測未知項目進行評分.假設P∈Rk×m為用戶特征矩陣，Q∈Rn×k為項目特征矩陣，其中k為隱式特征因子的個數，則可用向量pu以及qi分別表示用戶u的特征向量以及項目i的特征向量.根據以上定義，可以得到已觀測到的用戶-項目評分的條件概率服從高斯分布：

(1)

(2)

(3)

其中，I為協方差矩陣.根據上述的描述，通過貝葉斯推論，有用戶特征向量pu及項目特征向量qi的后驗概率如下：

(4)

3 融合相似度與信任度的矩陣分解(SimTrustMF)推薦算法

3.1 重構用戶之間的信任關系網絡

假設存在一個結點個數為M的信任關系網絡N，其中結點代表用戶，邊代表用戶之間的信任關系.因此，我們可以利用鄰接矩陣T=[tuv]m×m表示用戶之間的信任關系，其中元素tuv代表用戶u對用戶v的信任值.如果用戶u信任用戶v，則tuv為1，否則tuv為0.由于用戶u信任用戶v，并不能代表用戶v同樣也信任用戶u，因此通常情況下矩陣T為非對稱矩陣.

一般來說在系統中如果一個用戶被很多用戶信任，那么這個用戶在信任關系網絡中的影響力應該大于那些只被少數用戶信任的用戶影響作用.這種觀點同樣能反映到對用戶偏好的影響上，即被很多用戶信任的用戶具有較大的影響力，其個人的意見及言論往往會影響其他人的選擇.如在著名的大眾消費點評網站Epinions上，可以通過用戶ua采納了用戶ub對某一商品的評介意見來表明用戶ua信任用戶ub.如果ub的意見被很多采納，我們就認為其是“明星用戶”，其影響力大于系統中那些非“明星用戶”.我們利用類似于Pagerank算法[12]的思想，突出被很多用戶信任的用戶在信任關系網絡中的作用.Pagerank算法的核心思想認為如果一個網頁被很多其他網頁鏈接，便說明這個網頁比較重要，也就是PageRank值會相對較高[12].同樣，我們采用類似的思想，認為在信任關系網絡中被很多用戶信任的用戶的其在社交網絡中的影響也會更大.因而，可以利用如下公式對用戶之間的信任關系進行重構：

(5)

圖1 重構的用戶之間的信任關系網絡Fig.1 Rconstruction of trust relationship between the user network

3.2 SimTrustMF推薦算法

在一個系統中用戶的偏好及選擇很容易受到其信任用戶的影響.基于此原理學者們提出諸如SoRec[5]、SocialMF[6]、TrustMF[7]等許多經典的融合社交網絡中用戶之間信任關系的算法.但這些算法一般都未考慮目標用戶與其信任用戶之間的偏好其實存在一定的差異，這些算法一般都認為只要目標用戶信任一個用戶，這個用戶就會對目標用戶的選擇或是偏好產生影響.為此，本文提出融合用戶之間的相似度和重構的信任關系來反映目標用戶與其信任用戶間的偏好差異.本文利用以下公式來定義用戶u與用戶v的加權關系tsuv：

(6)

(7)

其中，tsuv表示用戶u對v的加權關系值.本文再利用與目標用戶u有關的所有其他用戶v及其與目標用戶u間的加權關系來計算目標用戶u的特征向量pu.

(8)

其中，pu為預估的目標用戶特征向量，pv為用戶v的特征向量，tsuv為用戶u與v之間的加權關系，Tu為重構信任關系網絡中用戶u信任的用戶集合.公式(8)利用加權的用戶關系tsuv，不但反映了用戶之間信任關系對用戶特征向量的影響，也反映了用戶相似度對用戶特征向量的影響.接著，本文對用戶關系矩陣TS的行向量進行標準化處理:

pu=∑v∈Tutsuvpv

(9)

其中，pu表示標準化后的用戶u特征向量，即與其存在一定聯系的所有用戶特征向量的加權平均.然后基于概率矩陣分解算法，假設已觀測到的用戶-項目評分條件概率服從高斯分布，有如下條件概率：

(10)

(11)

(12)

(13)

從圖2可以看出目標用戶u的特征向量pu的概率分布情況受到與其有加權關系的用戶影響.公式(13)對應的最大似然，可以通過求解其最大值得到.為了減少計算復雜度可以先對公式(13)取對數，然后取負，即求公式(14)的最小值.

圖2 SimTrustMF的圖算法Fig.2 Graph of SimTrustMF

(14)

λT(pu-∑v∈Tutsuvpv)-λT∑{v|u∈Tv}tsvu(pv-∑w∈Tvtsvwpw)

(15)

(16)

其中，g′(x)為g(x)的導數，即g′(x)=e-x/(1+e-x)2.然后，利用反向迭代更新的方法便可求得公式(14)的最小值.

4 實驗結果與分析

本節我們首先簡單地介紹了所使用的數據集，說明了評價標準與對比算法，最后給出了本文算法與其他算法在Ciao數據集上針對不同情況的對比實驗結果并進行了分析，同時還給出了參數α對算法的影響的實驗及分析.

4.1 數據集

這里我們采用的Ciao數據集為Guo等人[13]在Ciao網站上收集的.Ciao的是一個在線社區，里面包含了數以萬計的用戶對不同商品或服務的真實評論，這些評分能為消費者對商品的購買與選擇提供指導性的意見.其中包含了130萬成員發布的關于超過140萬產品的評論，總的評分超過了700萬條，Ciao已成為歐洲最大的購物門戶網站之一.我們采用的Ciao數據集收集了Ciao網站上17，615個用戶對16，121個不同項目的72，665條項目評分記錄，同時Ciao數據集還收集了19，533條用戶之間的信任關系記錄.

4.2 評價指標

我們采用平均絕對誤差(Mean Absolute Error，MAE)以及均方根誤差(Root Mean Square Error，RMSE)[14]作為推薦準確性的評價指標.MAE和RMSE均是推薦系統廣泛采用的評價指標.其中，RMSE評價指標的定義如下：

(17)

(18)

MAE是所有預測評分與實際評分之間的平均絕對誤差，而RMSE則可看作是所有預測評分與實際評分之間的偏差.MAE或是RMSE的值越小則代表預測值與實際值之間的差異越小，同時推薦算法的推薦準確率也越高.

4.3 對比算法與實驗設計

本文選取了下面三種算法作為對比算法.Ma等人[4]提出的SoRec算法，該算法將社交網絡中用戶之間的信任關系融合到概率矩陣分解算法中.其運用概率矩陣分解的方法對用戶項目評分項目分解，同時也運用概率矩陣分解的方法對用戶之間信任關系矩陣進行分解.文獻[6]中Jamali及Ester等人提出的SocilaMF算法，該算法將目標用戶直接信任用戶的影響作用放置在概率矩陣分解過程中目標用戶的隱式特征向量上.Yang等人[7]提出的TrustMF算法，該算法結合了信任關系與被信任關系對目標用戶推薦的影響.

本節的實驗可細分為以下3個實驗.

實驗1.觀察用戶間加權關系的參數α對SimTrustMF算法的推薦準確率的影響.此實驗將在Ciao數據集上隨機抽取80%數據作為訓練集，另外20%數據作為測試集，同時將矩陣分解中的隱式因子的個數k設置為10，而推薦準確率的評價指標這里分別選擇RMSE與MAE，然后將α的取值范圍設置為0到1，并以0.1作為步長進行遞增，以觀察算法推薦準確率的變化情況.

實驗2.評價SimTrustMF算法針對不同情況進行推薦的準確率.我們分別針對一般情況與冷啟動情況在Ciao數據集上進行實驗，并隨機抽取80%的數據作為訓練集，而另外的20%數據為測試集，而隱式因子的個數k將分別設置為5和10.推薦準確率的評價指標則分別選擇RMSE與MAE.

實驗3.觀測用戶之間信任關系的大小對SimTrustMF算法推薦準確率的影響.此實驗通過設置用戶之間不同大小的信任關系，以觀測SimTrustMF算法推薦準確率的變化情況.同樣將訓練集設置為80%，而隱式因子的個數k設置為10，推薦準確率的評價指標則分別選用RMSE與MAE.

在實驗2中，冷啟動情況的設置方法參照了文獻[15]，即如果一個用戶的評分數量少于5條，就認為對此用戶進行推薦為冷啟動情況.參數設置方面，SimTrustMF算法中參數設置為λT=1、λU=λV=0.001，而用戶之間的加權關系的參數α則設置為實驗1中其表現最優的參數，即α=0.55.對比算法的參數設置：SocialMF算法的參數設置為λT=1、λU=λV=0.001；TrustMF算法的參數設置為λT=1、λ=0.001；SoRec算法的參數λ設置為0.001，而參數λc則為0.01.實驗3中，各算法對應的參數設置與實驗2中一致，只是改變用戶之間的信任關系多少來觀測各算法對應RMSE值與MAE值的變化情況.為了實驗的公平性，文中所有實驗均進行5次，然后求平均值作為最后的結果.

4.4 實驗結果與分析

實驗1針對用戶間加權關系參數α對算法推薦準確率的影響.圖3和圖4別給出了在Ciao數據集上用戶之間加權關系參數α變化時，SimTrustMF算法對應RMSE值與MAE值，這里隱式因子的個數設置為k=10.

從圖3可以看出，當用戶之間的加權關系參數α在0.5到0.6之間時SimTrustMF算法對應的RMSE值達到最小.而當α=0時，算法對應的RMSE值最大，這表明當加權關系只由用戶之間的信任關系構成時，SimTrustMF算法的推薦準確率并不高.隨著α不斷變大算法對應的RMSE值逐漸變小，這表明在加權關系中融入用戶之間的相似度之后有助于提高算法的推薦準確率.而當α>0.6以后算法對應的RMSE值又開始逐漸變大，這表明當用戶之間的相似度在用戶之間的加權關系所占的比重過大時反而不利于算法推薦準確率的提高.另一方面可以看出當α在(0，0.2)之間逐漸增大時，算法對應的RMSE值變化速率非常明顯，這主要是因為用戶之間的加權關系從單純的由用戶之間的信任關系構成變為由用戶之間的信任關系與用戶之間的相似度兩者構成所引起的.

從圖4可以看出類似的實驗結果，即當用戶之間的加權關系參數α在[0.5,0.6]之間時SimTrustMF算法對應的MAE值達到最小.另一方面對比圖3與圖4，可以發現圖中曲線的形狀整體上較為相似，這是由于RMSE可看作是所有預測評分與實際評分之間的偏差，MAE是所有預測評分與實際評分之間的平均絕對誤差.

圖3 Ciao數據集上，用戶之間加權關系參數α對RMSE值的影響(k=10)Fig.3 Ciao data sets,weighted relationship between user parameters on the influence of the RMSE value (k=10) graph model SimTrustMF

實驗2是在不同情況下所對應的推薦準確率的實驗.表1和表2分別給出針對一般情況和冷啟動情況時，本文提出的SimTrustMF算法對應的RMSE值和MAE值；同時，也給出了所有對比算法對應的RMSE值以及MAE值.表中帶有“*”的結果表示對比算法中推薦效果表現最好的算法對應的值，隱式因子k分別設置為5和10.而Improve代表本文提出的算法相對于所有對比算法中表現最優的算法的提高率，比如表1中當k=10時所有對比算法中表現最好的算法對應的RMSE值為0.999，而本文提出的算法對應的RMSE值為0.960，由于RMSE越小代表準確率越高，則對應的提高率等于(0.999-0.960)/0.999=3.9%.

圖4 Ciao數據集上，用戶之間加權關系參數α對MAE值的影響(k=10)Fig.4 Ciao Data Sets,Weighted Relationship Between User Parameters Influence On MAE Value(k=10)

表1 Ciao數據集上，針對一般情況時的RMSE值與MAE值(訓練集百分比為80%)
Table 1 Ciao data sets,in view of the general situations of RMSE value with MAE (training set percentage is 80%)

MetricsRMSEMAEFactorsk=5k=10k=5k=10SoRec1．01310．7650．761SocialMF0．981?1．0060．7510．751?TrustMF0．9660．999?0．749?0．753SimTustMF0．9610．960．7450．743Improve2．04%3．90%0．53%1．07%

從表1可以看出在一般情況下進行推薦時，本文提出的SimTrustMF算法對應的RMSE值以及MAE值均高于其他對比算法中表現最優的算法對應的值，最高提高率達到了2.04%，這表明在一般情況時本文提出的算法對應的推薦準確率要更高.

表2 Ciao數據集上，針對冷啟動情況時的RMSE值與MAE值(訓練集百分比為80%)
Table 2 On Ciao data sets,to solve the problem of cold start when the RMSE value with MAE

MetricsRMSEMAEFactorsk=5k=10k=5k=10SoRec1．0381．0210．7880．739?SocialMF0．9921．012?0．7740．75TrustMF0．975?1．0960．752?0．77SimTustMF0．9690．9810．750．735Improve0．62%3．06%0．27%0．54%

從表2針對冷啟動情況的實驗結果可以看出本文提出的SimTrustMF算法對應的RMSE值與MAE值都要高于其他對比算法所對應的值.所提出的算法表現最好時甚至要比對比算法中表現最優的算法提高了3.06%.這表明在冷啟動情況下，本文提出的SimTrustMF算法同樣能取得很好的推薦效果.綜上所述，本文提出的SimTrustMF算法在一般情況和冷啟動情況下均能取得較好的推薦效果.

實驗3是針對用戶之間信任關系的大小對算法推薦準確率的影響.圖5與圖6分別給出了用戶之間信任關系個數變化時，SimTrustMF算法對應的RMSE與MAE值.圖中信任關系個數指的是該用戶被信任與其信任用戶的總個數，只有滿足橫坐標所對應條件的用戶才會用于算法的訓練與測試.

圖5 Ciao數據集上，用戶之間信任關系個數對應RMSE值的影響(k=10)Fig.5 Ciao data set,the user trust rrelationship between the number corresponding to the influence of the RMSE value (k=10)

從圖5以看出在不同信任關系個數時SimTrustMF算法對應的RMSE值均小于對比算法所對應的RMSE值.另一方面各個算法在用戶之間信任關系的個數為1到5時，所對應的RMSE值最大；而用戶之間信任關系個數大于500時，其對應的RMSE值最小.雖然在Ciao數據集上滿足這一條件的數據不多，但是滿足條件的用戶之間的信任關系非常密集，有利于信任關系算法的融入，以提高推薦準確率.

圖6 Ciao數據集上，用戶之間信任關系個數對應MAE值的影響(k=10)Fig.6 Ciao data dets,the user trust relationship between the number corresponding to the iinfluence of MAE value (k=10)

從圖6同樣可以看出在不同信任關系個數時，本文提出的SimTrustMF算法對應的MAE值均小于對比算法對應的MAE值，即在不同信任關系個數下SimTrustMF算法對應的推薦準確率均高于對比算法的推薦準確率.

5 結束語

本文在傳統的概率矩陣分解算法中融入用戶之間的加權關系對用戶特征向量的影響.這種用戶之間的加權關系是通過重構之后的用戶之間的信任關系以及用戶之間的相似度計算得到的.該方法一方面反映了目標用戶所信任的用戶會對該用戶的興趣偏好產生影響；另一方面通過用戶之間的相似度又能區分目標用戶與其信任用戶之間偏好的差異.本文采用Ciao數據集進行實驗，其實驗結果表明本文提出的SimTrustMF相對SocRec、SocialMF和TrustMF算法在一般情況情下得到的RMSE和MAE均有所提高，同時SimTrustMF能更好地解決冷啟動問題.

[1] Borchers A,Herlocker J,Konstan J,et al.Ganging up on information overload [J].Computer,1998,31(4):106-108.

[2] Adomavicius G,Tuzhilin A.Toward the next generation of recommender systems: a survey of the state-of-the-art and possible extensions [J].Knowledge and Data Engineering,IEEE Transactions on,2005,17(6):734-749.

[3] Salakhutdinov R,Mnih A.Probabilistic matrix factorization[C].In: Proc.of the Annual Conf.on Neural Information Processing Systems,Curran Associates Press,2008:1257-1264.

[4] Ma H,Yang H,Lyu M R,et al.Sorec: social recommendation using probabilistic matrix factorization[C].Proceedings of the 17th ACM Conference on Information and Knowledge Management,ACM,2008:931-940.

[5] Ma H,Zhou D,Liu C,et al.Recommender systems with social regularization[C].Proceedings of the Fourth ACM International Conference on Web Search and Data Mining,ACM,2011: 287-296.

[6] Jamali M,Ester M.A matrix factorization technique with trust propagation for recommendation in social networks[C].Proceedings of the Fourth ACM Conference on Recommender Systems,ACM,2010:135-142.

[7] Yang B,Lei Y,Liu D,et al.Social collaborative filtering by trust[C].Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence,AAAI Press,2013:2747-2753.

[8] Bao Y,Fang H,Zhang J.Leveraging decomposed trust in probabilistic matrix factorization for effective recommendation[C].Proceedings of the 28th AAAI Conference on Artificial Intelligence,AAAI Press,2014:30-36.

[9] Guo G,Zhang J,Yorke-Smith N.Trustsvd:collaborative filtering with both the explicit and implicit influence of user trust and of item ratings[C].Proceedings of the 29th AAAI Conference on Artificial Intelligence(AAAI),2015.

[10] Hu Xun,Meng Xiang-wu,Zhang Yu-jie,et al.A fusion of project characteristics and mobile users trust recommendation algorithm [J].Journal of Software,2014,25(8):1817-1830.

[11] Li Wei-ping,Yang Jie.Social network is recommended based on stochastic gradient matrix decomposition algorithm [J].Computer Application Research,2014,31(6):1654-1656.

[12] Sergey Brin and Lawrence Page.The anatomy of a large-scale hypertextualweb search engine[J].Computer Networks and ISDN Systems,1998,30(1):107-117.

[13] Guo G,Zhang J,Thalmann D,et al.ETAF: an extended trust antecedents framework for trust prediction[C].Advances in Social Networks Analysis and Mining (ASONAM),IEEE/ACM International Conference on,IEEE,2014:540-547.

[14] Herlocker J L,Konstan J A,Terveen L G,et al.Evaluating collaborative filtering recommender systems [J].ACM Transactions on Information Systems (TOIS),2004,22(1): 5-53.

[15] Massa P,Avesani P.Trust-aware recommender systems[C].Proceedings of the 2007 ACM Conference on Recommender Systems.,ACM,2007: 24.

附中文參考文獻：

[10] 胡 勛,孟祥武,張玉潔,等.一種融合項目特征和移動用戶信任關系的推薦算法[J].軟件學報,2014,25(8): 1817-1830.

[11] 李衛平,楊 杰.基于隨機梯度矩陣分解的社會網絡推薦算法[J].計算機應用研究,2014,31(6):1654-1656.