王　維, 楊　宇, 吳清烈

(東南大學(xué) 管理工程研究所，江蘇 南京 211189)

?

結(jié)合信任和相似度的隨機游走推薦算法

王維, 楊宇, 吳清烈

(東南大學(xué) 管理工程研究所，江蘇 南京 211189)

摘要：針對稀疏性和冷啟動問題，提出一種結(jié)合信任和相似度的隨機游走算法，利用兩者的綜合權(quán)重TS，應(yīng)用于隨機游走算法。實驗結(jié)果表明，在全用戶數(shù)據(jù)集和冷啟動數(shù)據(jù)集中，算法比其他參照算法在準(zhǔn)確率和覆蓋率等方面均有提高，時間復(fù)雜度也有改善。本文的信任度采用數(shù)據(jù)集內(nèi)用戶評價的信任度 ，并沒有采用信任度公式計算用戶對其他用戶的信任度。提出的算法改善了推薦精確度、覆蓋率，優(yōu)化了推薦質(zhì)量。

關(guān)鍵詞：信任度;相似度;隨機游走;稀疏性；冷啟動

隨著Web2.0的不斷發(fā)展，人們越來越習(xí)慣于從社交網(wǎng)絡(luò)中獲得服務(wù)，如何高效地搜索并獲得服務(wù)是一個非常有意義的課題。為了滿足用戶的各種需求，出現(xiàn)了推薦系統(tǒng)，推薦系統(tǒng)被廣泛應(yīng)用于為用戶提供高質(zhì)量及有效的推薦[1]。推薦系統(tǒng)的方法分為基于內(nèi)容的推薦，協(xié)同過濾推薦，基于知識的推薦和混合推薦的方法，其中協(xié)同過濾方法是應(yīng)用最廣泛的方法[2]，電子商務(wù)環(huán)境下為用戶提供高效的推薦是非常有意義的課題，但稀疏性和冷啟動問題嚴(yán)重影響著推薦算法的質(zhì)量，同時在社交網(wǎng)絡(luò)中，一些商家為了利益，容易形成欺詐行為。

社交網(wǎng)絡(luò)在不斷拓展，信任被逐漸引入推薦系統(tǒng)?；谛湃蔚耐扑]方法雖然有較好的推薦效果，但存在因素單一性，社交網(wǎng)絡(luò)用戶細(xì)分等問題[3]。

本文將針對稀疏性和冷啟動問題，同時結(jié)合社交網(wǎng)絡(luò)中的信任和相似度，融入到隨機游走算法中，并在試驗中驗證算法的有效性。

協(xié)同過濾推薦算法主要有基于User的CF算法[4]和基于Item的CF算法[5]，算法主要依靠計算用戶或項目間相似度，得到最近鄰居集合，通過鄰居集合來獲得推薦，但算法面臨稀疏性和冷啟動問題，覆蓋率低。

信任逐漸被引入推薦系統(tǒng)來做高質(zhì)量的推薦，結(jié)合信任的推薦系統(tǒng)認(rèn)為人們更愿意考慮朋友的推薦，目前結(jié)合信任的推薦系統(tǒng)已經(jīng)有了廣泛研究與應(yīng)用。Epinions[6]比較早地在系統(tǒng)中結(jié)合了信任這一因素，網(wǎng)站允許用戶將他人納入信任列表或不信任列表，從而獲得社會關(guān)系。文獻[7]提出TidalTrust算法，算法以廣度優(yōu)先的方式，綜合考慮了路徑長度和信任度大小，通過加權(quán)得到節(jié)點與節(jié)點間的信任度。MoleTrust算法[8]類似于TidalTrust算法，但設(shè)定了一個最大路徑長度。文獻[9]提出TrustWalker的隨機游走算法，算法在信任網(wǎng)絡(luò)中隨機遍歷用戶，綜合各個用戶的評分?jǐn)?shù)據(jù)來預(yù)測評分。文獻[10]考慮到用戶興趣變化，采用了重啟動隨機游走算法，能有效提高推薦精度。

一些研究利用信任傳播來計算信任度，同時也改善了冷啟動和稀疏性問題。文獻[11]綜合信任傳播，通過加權(quán)平均來計算信任估計值。文獻[12]利用信任傳播過程中信任值的衰減，設(shè)計了3種計算信任傳播的信任度的方法。

一些研究者將信任度和其他因素結(jié)合，取代傳統(tǒng)CF中的相似度，從而獲得更高的推薦精確度。文獻[13]將相似度和信任度綜合，代替?zhèn)鹘y(tǒng)CF的相似度，并應(yīng)用于推薦系統(tǒng)中。文獻[14]利用評分-信任協(xié)同進行推薦預(yù)測，這種混合推薦的技術(shù)提高了推薦精度和評分覆蓋率。文獻[15]提出了結(jié)合信任度和社會關(guān)系度的電子商務(wù)推薦系統(tǒng)，考慮了關(guān)于推薦資源的多個因素。

基于信任的推薦算法都在一定程度上改善了數(shù)據(jù)稀疏性問題，而作為稀疏性的優(yōu)化方法，近年來，矩陣分解技術(shù)在電子商務(wù)推薦中應(yīng)用越來越廣泛，文獻[16]采用基于隨機梯度矩陣分解的社會網(wǎng)絡(luò)推薦算法，并具有比較好的預(yù)測效果。文獻[17]在結(jié)合社交網(wǎng)絡(luò)的基礎(chǔ)上應(yīng)用矩陣分解。雖然矩陣分解對于稀疏性問題有較好的效果，但對冷啟動問題也無法直接處理，且沒有考慮到信任關(guān)系在網(wǎng)絡(luò)中的傳播。

近些年針對稀疏性和冷啟動問題，基于信任的推薦系統(tǒng)已經(jīng)有了豐富的研究成果，但也存在一些不足之處。

1)文獻大多只考慮了一個因素，比如信任度，相似度，或兩個因素結(jié)合，沒有綜合考慮更多因素，使推薦精度進一步提高。

2)大多推薦算法需要利用到相似度計算，而相似度計算需要共同評分的項目達到一定數(shù)量，而實際上數(shù)據(jù)是稀疏的，兩用戶的共同評分項目有時很少甚至沒有。

3)一些基于信任的推薦算法沒有意識到信任的朋友有時候并不適合作為鄰居用戶，因為朋友間也可能會有不同的興趣偏好，信任用戶不一定是相似用戶，相似的也不一定是互相信任的，所以需要同時考慮這兩個方面。

4)一些隨機游走算法由于要隨機遍歷整個信任網(wǎng)絡(luò)，導(dǎo)致整個算法的計算量明顯增加，時間復(fù)雜度較長。

相比于以前工作的不足，本文綜合考慮了信任和相似度，保證隨機游走選取的用戶既是社交網(wǎng)絡(luò)中的信任用戶，又是興趣偏好相似的用戶，在計算相似度方面采用矩陣分解的方法，避免了共同評分項目過少的情況，在隨機游走的的過程中依據(jù)信任和相似度的綜合權(quán)重進行游走，減少了一定的算法復(fù)雜度，從而提高了推薦精確度。

1隨機游走推薦算法

1.1結(jié)合信任和相似度的隨機游走推薦算法框架

結(jié)合信任和相似度的隨機游走推薦算法分為以下3步。

1)在已知用戶集合、項目集合、評分矩陣的情況下，結(jié)合信任度和相似度，通過加權(quán)計算出權(quán)重TS。

2)在加權(quán)信任網(wǎng)絡(luò)中，依據(jù)權(quán)重TS作為隨機游走的指標(biāo)，遍歷信任網(wǎng)絡(luò)中全用戶。

3)終止游走過程，預(yù)測目標(biāo)用戶對待評分項目的評分，最終得出推薦。

TSWalker算法的流程如圖1所示。

圖1　TSWalker算法流程

1.2權(quán)重TS計算

基于信任的推薦算法主要考慮了用戶間的信任度，這并不能明顯提高推薦的精確度，因為算法選取目標(biāo)用戶的信任用戶作為鄰居用戶，但信任用戶與目標(biāo)可能有不同的偏好，兩者興趣偏好不一致，導(dǎo)致推薦質(zhì)量下降。結(jié)合信任和相似度的隨機游走算法在進行游走前，需要計算權(quán)重TS，同時考慮了信任度和相似度。

其中，sim(u，v)為用戶u和用戶v之間的相似度；t(u，v)為用戶u和用戶v之間的信任度。t(u，v)可以從用戶的直接評價得出，在本文的實驗數(shù)據(jù)集Epinions上，信任網(wǎng)絡(luò)為二值信任網(wǎng)絡(luò)，即用戶v在u的信任列表上，信任度為1，不信任則為0。

現(xiàn)階段計算相似度大多利用協(xié)同過濾、杰卡德公式、皮亞諾余項或改進的相似度計算技術(shù)，同時用戶評分矩陣又很大，導(dǎo)致矢量維度很高，用戶評分矩陣稀疏，在此采用一種基于矩陣分解的計算相似度的方法，可以明顯提高推薦精確度。對于一個m×n的評分矩陣R，將其降維分解至2個低階矩陣P和Q。

R=PQT。

其中，P為m×d矩陣；Q為n×d矩陣。將矩陣降維后，采用余弦相似度計算u和v的相似度。

1.3隨機游走過程

從目標(biāo)用戶u0開始進行隨機游走，第k步會抵達用戶u，如果項目i已被u評分，則停止游走，u對i的評分ru，i即為此步的結(jié)果。若u并沒有評價i，則:

u在第k步游走過程中在u處中止的概率φu,k，與i和j的相似度相關(guān)，i和j的相似度越高，概率值越大；φu,k的值也與隨機游走的深度有關(guān)，目標(biāo)用戶u0與用戶u之間的游走距離越長，噪音數(shù)據(jù)也就越多，會嚴(yán)重影響預(yù)測的質(zhì)量，所以φu,k值會隨著k值增加。

其中，sim(i，j)是項目i和項目j之間的相似度，k取值能夠保證當(dāng)k無窮大時，φu,k值接近1，k值比較小時，φu,k值也比較小?，F(xiàn)階段計算項目間相似度值大多依據(jù)協(xié)同過濾方法，比如皮亞諾余項和一些改進的相似度計算方法，然而當(dāng)沒有用戶同時評分過這2個項目時，這些方法就無法計算項目間的相似度了。所以，本文提出一種基于矩陣分解的計算項目之間相似度的方法，同上節(jié)，i和j間相似度公式為

當(dāng)以概率φu,i,k在u處中止時，需要從u的評分項目集中選取項目j,u對j的評分即為此次的結(jié)果。u從評分項目集RIu中選取j概率公式為

2)以概率1-φu,i,k在網(wǎng)絡(luò)中繼續(xù)，從u的直接信任用戶集合TUu中選取一個用戶v作為第k+1步的用戶節(jié)點。

一般的隨機游走算法選取下一步用戶節(jié)點是從直接信任用戶集合TUu中隨機選取，意味著用戶u的直接信任用戶都有著等同的機率被選取，然后用戶的直接信任用戶集合中，每個用戶都有著自己獨特的偏好、習(xí)慣、愛好等，與用戶u的興趣偏好相似的直接信任用戶被選取的概率應(yīng)該要大一些，所以，選取用戶v的概率為

其中，TS(u,v)即為上節(jié)介紹的權(quán)重，TS值越高表明v與u有著越高的信任關(guān)系和興趣偏好相似，可以保證每一步選取的用戶都是u直接信任用戶集合中與u偏好相似的用戶，使評分預(yù)測更加精確。

在結(jié)合信任與相似度隨機游走算法中，u0的預(yù)測評分為每步隨機游走評分綜合。

P(U=u，I=j)是在用戶u處，并選取項目j概率，分為以下3種情況。

其中，Uk=u為選取u為節(jié)點；Iu=j為u選取項目j為預(yù)測項目。

在第k步，

根據(jù)六度分隔理論，任兩個用戶可以在不大于6步的情況下獲得聯(lián)系，所以在此限定隨機游走最大深度為6步，即當(dāng)k=6時，隨機游走停止。經(jīng)計算，此公式的最終計算公式為

其中，ri為每次游走的預(yù)測評分；n為游走的總次數(shù)。

2仿真實驗

2.1實驗數(shù)據(jù)集及評價指標(biāo)

選取Epinions數(shù)據(jù)集進行實驗，Epinions數(shù)據(jù)集開始于1999年，注冊會員可以對商品評分，會員之間還可以把別的會員加入自己的信任列表，數(shù)據(jù)集包括40 163個用戶對139 738個商品的評論，有664 824條評分，包括了487 183條信任關(guān)系。

評價指標(biāo)RMSE(均方差誤差)通過比較預(yù)測值與用戶實際評分之間的差異來度量推薦的準(zhǔn)確性。

Precision(準(zhǔn)確率)為系統(tǒng)推薦商品中用戶偏好的商品與系統(tǒng)推薦商品總數(shù)所占的比例。

其中，Ntp為系統(tǒng)推薦且用戶偏好的商品數(shù);Nfp為系統(tǒng)推薦但用戶不偏好的商品數(shù)；Nfn為系統(tǒng)不推薦但用戶偏好的商品數(shù)。

Coverage(覆蓋率)為系統(tǒng)推薦商品覆蓋全部商品的比例。

F為精確率和覆蓋率的調(diào)和值。

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

將數(shù)據(jù)集分為80%訓(xùn)練集與20%測試集，并選取前面提到UserCF、ItemCF、TidalTrust、MoleTrust、TrustWalker算法作為實驗參照算法，在計算權(quán)重TS時取參數(shù)α為0.5。分別對全用戶集和冷啟動用戶集上的實驗結(jié)果進行推薦質(zhì)量的對比。在40 163個用戶中，認(rèn)為評分?jǐn)?shù)低于5的即為冷啟動用戶，共16 910個冷啟動用戶。表1和圖2為在全用戶集上。

表1　全用戶集比較結(jié)果

圖2　全用戶集比較結(jié)果

根據(jù)表1和圖2，觀察到在全用戶集中，推薦算法的精確度在不斷提高，越往后的算法考慮的因素越多，所以推薦精度在提高?；谛湃蔚耐扑]算法相對于CF算法在精確率上并沒有很明顯優(yōu)勢。CF算法借助用戶評分?jǐn)?shù)據(jù)計算用戶或物品相似度，而基于信任的推薦算法主要考慮的是用戶間的信任，沒有考慮用戶間的興趣偏好，這可以很明顯地提高覆蓋率，卻不能明顯提高精確率。本文提出了權(quán)重TS，同時考慮了相似度與信任度，在計算相似度的時候又采用了矩陣分解的方法避免了沒有用戶同時評分同一商品的情況，通過實驗，在均方差誤差、精確率、覆蓋率、F值等評價指標(biāo)上均優(yōu)于其他算法。

根據(jù)實驗結(jié)果，結(jié)合信任和相似度的隨機游走算法在冷啟動用戶集中具有較好的推薦效果。傳統(tǒng)的協(xié)同過濾算法推薦質(zhì)量最差，因為在冷啟動用戶集中，很少有商品被兩個及以上用戶評分過，意味著用戶或物品相似度很難計算，從而降低推薦質(zhì)量。在推薦算法中引進信任網(wǎng)絡(luò)，能夠明顯提高覆蓋率，但在冷啟動用戶集中精確率仍提升不明顯。TrustWalker算法和TSWalker算法在精確率和覆蓋率上均有優(yōu)勢，相比下TSWalker算法有更高的推薦精度，TSWalker算法同時考慮了信任度和相似度，并將TS權(quán)重應(yīng)用于隨機游走算法，具有很好推薦效果。如表2、圖3所示。

表2　冷啟動用戶集比較結(jié)果

圖3　冷啟動用戶集比較結(jié)果

由于評分?jǐn)?shù)據(jù)集非常大，需考慮推薦算法時間復(fù)雜度，圖4為各種算法復(fù)雜度平均值?？梢杂^察到協(xié)同過濾算法耗費時間最短，因為協(xié)同過濾算法僅主要考慮用戶的評分?jǐn)?shù)據(jù)，相反，其他算法需要考慮到信任度，從而提高了算法計算量。相比于其他隨機游走算法，TSWalker算法的時間復(fù)雜度要低一些，主要因為算法在隨機游走的每一步中，都會依據(jù)TS權(quán)重選取目標(biāo)用戶，而不是隨機選取，從而可以提高計算效率。

圖4　各算法時間復(fù)雜度對比結(jié)果

3結(jié)束語

考慮推薦算法的稀疏性和冷啟動等問題，結(jié)合信任度和相似度，使隨機游走算法下一步選取的用戶既是社交網(wǎng)絡(luò)中的信任用戶，又是興趣偏好相似的用戶，在計算相似度上利用了矩陣分解的方法，防止了傳統(tǒng)算法中共同評分項目過少的局限，并依據(jù)綜合權(quán)重TS進行隨機游走，提高了推薦質(zhì)量。

今后會考慮2個角度。一是本文的信任度直接利用數(shù)據(jù)集上的信任度，需要考慮到信任的變化，在信任網(wǎng)絡(luò)中通過信任傳播等方式計算信任度。二是在電子商務(wù)網(wǎng)站上需要考慮到推薦算法的實時性，能夠及時為用戶推薦真正需要的商品是推薦系統(tǒng)的目的。

參考文獻：

[2]KANG G, LIU J, TANG M, et al. AWSR: active web service recommendation based on usage history[C]. Proceedings of the 19th International Conference on Web Services. IEEE, 2012:186-193.

[3]譚學(xué)清,黃翠翠,羅琳.社會化網(wǎng)絡(luò)中信任推薦研究綜述[J].現(xiàn)代圖書情報技術(shù),2014,30(11):10-16.

TAN Xueqing,HUANG Cuicui,LUO Lin.A review of research on trust recommendation in social networks[J].2014,30(11):10-16.

[4]SU X, KHOSHGOFTAAR T M.A survey of collaborative filtering techniques[J].Advances in Artificial Intelligence,2009(12):1-19.

[5]NILASHI M,IBRAHIM O B,ITHNIN N.Hybrid recommendation approaches for multi-criteria collaborative filtering[J].Expert Systems with Applications,2014,41(8):3879-3900.

[6]MASSA P,AVESANI P.Trust metrics in recommender systems[M].Computing with Social Trust. Berlin: Springer, 2009:259-285.

[7]GOLBECK J A. Computing and applying trust in web-based social networks[D].USA:University of Maryland,2005.

[8]MASSA P,AVESANI P.Trust Metrics on controversial users: balancing between tyranny of the majority[J].International Journal on Semantic Web & Information Systems, 2007, 3(1):39-64.

[9]JAMALI M,ESTER M. TrustWalker:a random walk model for combining trust-based and item-based recommendation[C]//Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM,2009:397-406.

[10]俞琰,邱廣華.用戶興趣變化感知的重啟動隨機游走推薦算法研究[J].現(xiàn)代圖書情報技術(shù), 2012(4):48-53.

YU Yan, QIU Guanghua. Research on user interest shift aware random walk with restart recommendation algorithm[J].New Technology, 2012(4):48-53.

[11]韓麗.社交網(wǎng)絡(luò)中的信任推薦和好友搜索過濾算法研究[D].秦皇島： 燕山大學(xué),2012.

HAN Li.Research on recommendation and search filter of friends algorithm in social networks[D].Qinhuangdao:Yanshan University, 2012.

[12]CHAKRABORTY P S, KARFORM S. Designing trust propagation algorithms based on simple multiplicative strategy for social networks[J]. Procedia Technology, 2012, 6(6):534-539.

[13]陳曉城.基于信任傳播模型的協(xié)同過濾推薦算法研究[D].廣州：中山大學(xué),2010.

CHEN Xiaocheng.Research of collaborative filtering recommendation algorithm based on trust propagation model[D].Guangzhou: Zhongshan University,2010.

[14]秦繼偉, 鄭慶華, 鄭德立,等. 結(jié)合評分和信任的協(xié)同推薦算法[J]. 西安交通大學(xué)學(xué)報, 2013, 47(4):100-104.

QIN Jiwei,ZHENG Qinghua,ZHENG Deli ,et al,A collaborative recommendation algorithm based on ratings and trust[J].Journal of Xi′an Jiaotong University,2013, 47(4):100-104.

[15]Li Y M, Wu C T, Lai C Y. A social recommender mechanism for e-commerce: Combining similarity, trust, and relationship[J]. Decision Support Systems, 2013, 3(3):740-752.

[16]李衛(wèi)平,楊杰.基于隨機梯度矩陣分解的社會網(wǎng)絡(luò)推薦算法[J].計算機應(yīng)用研究,2014, 31(6):1654-1656.

LI Weiping,YANG Jie.Stochastic gradient matrix factorization based on social network recommender algorithm[J].Application Research of Computers,2014, 31(6):1654-1656.

[17]MA H,KING I,LYU M R.Learning to recommend with social trust ensemble[C]∥Proceedings of the 32ndInternational ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 2009:203-210.

A Random Walk Recommendation Algorithm Combining Trust and Similarity

WANG Wei, YANG Yu, WU Qinglie

(Graduate Institute of Management Engineering, Southeast University, Nanjing 211189, China)

Abstract：To address the similarity and cold start problem, a random walk algorithm combining trust and similarity is proposed with the weight TS. The experimental results indicate that the algorithm performs better with the all user data sets and cold start data sets than others in the aspect of accuracy rate, coverage rate as well as the time complexity. The trust value of the data set is used rather than the value computed by an effective method. The algorithm in this research improves the precision of recommendation, coverage rate and quality of recommendation.

Key words：trust；similarity；random walk；similarity；cold start

收稿日期：2015- 04- 13

基金項目：江蘇省教育廳人文社會科學(xué)研究基金資助項目(2013ZDIXM017)

作者簡介：王維(1991-)，男，安徽省人，碩士研究生，主要研究方向為個性化推薦.

doi:10.3969/j.issn.1007- 7375.2016.03.011

中圖分類號：TP393

文獻標(biāo)志碼：A

文章編號：1007-7375(2016)03- 0065- 06