結合用戶行為信息和信任傳遞的推薦算法

張邦佐，王佳同，孫 瑋，喬書玉，馮國忠，孫小新

(東北師范大學信息科學與技術學院，吉林 長春 130117)

結合用戶行為信息和信任傳遞的推薦算法

張邦佐，王佳同，孫 瑋，喬書玉，馮國忠，孫小新

(東北師范大學信息科學與技術學院，吉林 長春 130117)

通過用戶行為信息并結合信任傳遞推斷用戶隱式信任關系，提出了基于矩陣分解的PTtrustSVD算法，并在Filmtrust數據集上進行了實驗.結果表明，加入隱式信任關系優(yōu)于僅使用顯式信任關系的推薦方法，證明了隱式信任關系對于改進推薦系統(tǒng)性能的有效性.

推薦系統(tǒng)；隱式信任；信任傳遞

0 引言

20世紀90年代中期，為了有效地解決大數據時代所面臨的信息過載問題，推薦系統(tǒng)[1]便應運而生.推薦系統(tǒng)使用的主流方法是協(xié)同過濾技術，它分為基于記憶和基于模型的協(xié)同過濾：基于記憶的方法是假設用戶過去的歷史可以很好地代表用戶的興趣[2]；而基于模型的方法卻是假定推薦來自某一模型，通過數據訓練來確定.這些方法不考慮用戶之間可能存在的社交關系，但在現實世界中用戶可以從朋友處得到更好的建議.隨著社交網絡的出現，信任關系作為現實世界人際關系在社交網絡中的反映，表達了用戶對其他用戶觀點的認可程度，同時也成為優(yōu)化推薦結果的有力工具[3].研究顯示，相比于有共同愛好的陌生人的在線推薦，目標用戶更傾向于選擇他們信任的朋友的推薦[2].信任關系在大多數的社交網絡中可以直接通過好友關注等方式獲得，這些信任關系稱為顯式信任.在大部分社交網站中，用戶對的數量遠遠大于顯式信任的數量，因此顯式信任是十分稀疏的.但是在一些電子商務網站上，信任關系并沒有明顯的體現，往往需要通過相似的用戶行為來推測，比如用戶評分相同或評論內容相近，即隱式信任關系.

目前，基于用戶社交信任關系的推薦方法是推薦系統(tǒng)中的研究熱點，2015年G.Guo等[4]提出了一種基于用戶信任和評分項目的矩陣分解技術，在SVD++算法[5]基礎上，擴展了隱式信任關系，將顯式和隱式信任關系加入到推薦方法中.對于興趣推薦來說，信任關系比朋友關系更有價值[6].為了更好地發(fā)現隱式信任關系，人們將心理學中的兩個著名理論結構平衡理論和社會地位理論[7-9]推廣到社交網絡中.結構平衡理論基于“朋友的朋友是朋友”、“敵人的敵人是朋友”等原則.在社會地位理論中，正向邊(x，y)意味著x有比y更高的地位，反向邊(x，y)意味著x比y的地位更低.結構平衡理論和社會地位理論可以有效地指導我們利用用戶行為在社交網絡中推斷用戶之間的關系，同時社會地位理論表明社會地位是具有傳遞性.

基于心理學的結構平衡理論和社會地位理論，本文將信任傳遞性加入到隱式信任關系推斷中，同時將顯式信任關系與隱式信任關系相結合，進一步擴展隱式信任關系，大大增加了信任關系的數量，從而緩解了信任關系稀疏的問題.

1 結合用戶行為信息和信任傳遞的推薦算法PTtrustSVD

1.1 信任的定義

在社交網絡中，信任一般是指在用戶交互過程中，一個人對另一個人的信念和預期.在推薦系統(tǒng)中主要關注2個用戶對于相同物品的喜好程度.在Filmtrust數據集中，用戶之間會根據相似的電影喜好來添加信任的用戶.G.Guo等[10]總結了信任關系具有不對稱性、傳遞性、動態(tài)性、上下文依賴性等性質.

1.2 信任的測量

在大多數情況下，用戶在網絡上參與一些評論、評分等用戶行為的時候，基本上都會有一個共同的背景.比如Filmtrust注冊的用戶會給出他們相應的電影評分，這些電影就是一個共同的大背景，只是每個人喜好不同、評分不同，自然會影響著互相之間的信任.M.Papagelis等[11]提出了利用皮爾森相關系數來衡量2個用戶之間信任程度，從而表明2個用戶之間的興趣相似程度，計算公式為

(1)

(2)

其中n是2個用戶之間共同的評分個數.我們設定一個相似度閾值θ，超過閾值的可以作為信任關系，計算公式為

(3)

其中tu，v是用戶u與用戶v的隱式信任關系.只有能夠達到閾值的值才能夠判定為信任關系，計算公式為

PtrustSet={(u，v)|tu，v≥θ；u，v∈U}.

(4)

公式(4)能夠通過用戶的評分行為清楚地找到用戶之間隱式的信任關系.

1.3 信任傳遞

信任傳遞是建立在結構平衡理論和社會地位理論之上的，它反映的是信任主體根據一些相關聯(lián)的實體或信息對信任客體進行的間接推斷，這些推斷往往不能直觀判斷，而是需要信任主體對其他信任客體產生的信任關系互相關聯(lián)得到，這種認知的過程稱為信任傳遞.

從社會學和心理學角度的社會地位理論來看，用戶u和w的地位關系可以通過第三方共同關系v來建立.例如，在u，v關系中，u地位低于v；在v對w關系中，v地位低于w；通過判斷得到u相對于w有一個較低的地位.從而可以將社會地位理論拓展到信任傳遞中來[13]，即如果u信任v，v信任w，那么可以推測u對w也具有信任關系，表示為：

(5)

這樣就得到了一個新的隱式信任數據集，即

TtrustSet={(u，C)|u→B，B→C?u→C；u，B，C∈U}.

(6)

根據六度分隔理論[14]，在同一個社交網絡中，任意2個用戶想要找到對方，只需要有限次的關系傳播.當然如果2個距離較遠的用戶要產生聯(lián)系，傳播距離就會較長，相應的影響也就會越低，本文只考慮一跳傳播.

1.4 trustSVD

(7)

但是針對用戶的評分，每個人衡量事物的標準不一樣，有的人只要覺得一般喜歡，可能就會給出高分，而有的人比較苛刻很少給出高分.那么基于這種情況，在SVD方法的基礎上，SVD++加入了基準偏移量bui和用戶評分隱式反饋信息yi，計算公式為

(8)

其中:Iu是用戶u評分過的項目集；buj由評分偏差μ、用戶u與其他用戶之間的評分平均值偏差bu以及項目j和其他項目的評分平均值偏差bi共同組成，即buj=μ+bu+bj；yi提供了用戶隱式反饋信息，是用戶愛好的額外指示.

G.Guo等[4]在SVD++的基礎上加入了顯式信任信息，提出了trustSVD，通過利用用戶之間的信任影響，來探索更加精確的預測評分，其評分模型計算公式為

(9)

其中Tu為用戶之間的信任集合.

1.5 PTtrustSVD

通過用戶行為信息和信任傳遞得出的隱式信任關系公式(見(4)和(5))，結合trustSVD算法得出的新算法，這里稱作PTtrustSVD，評分預測函數為

(10)

本文基于Guo G.等[4]的trustSVD算法較活躍、頻繁的用戶或較流行的物品實施相對小的懲罰，對于冷啟動的用戶或物品實施比較大的懲罰，最終求解的損失函數為

(11)

其中exT是顯式信任相關變量，imT是隱式信任相關變量，最后通過梯度下降法對損失函數進行求解.

2 結果與討論

2.1 數據集

Filmtrust是一個對電影進行評分和評論的社交網站.為了保護用戶的隱私，每個用戶都進行了數字編號，包括了1 508名用戶對2 071部電影進行的35 497個評分.評分范圍為0～4分，遞增步長為0.5.同時還包括609個用戶提供的1 853條信任關系，信任關系數據十分稀疏.

2.2 評估標準

(12)

(13)

2.3 結果對比分析

圖1 2種方法的MAE和RMSE結果對比

從圖1可以看出，當θ在0.45時，只加入了用戶行為相似度的PtrustSVD的MAE可以達到0.587，RMSE達到0.786.而同時融合了信任傳遞的PTtrustSVD的MAE可以達到0.582，RMSE可以達到0.780.可見本文方法是非常高效的.

表1是本文方法和G.Guo等[4]的trustSVD方法的對比結果.從表1中可見，深度挖掘出的隱式信任關系可以有效緩解數據稀疏性問題，從而得到了更好的推薦效果.

由于數據稀疏，在對信任關系進行分解時，大量的空白值需要填補，因而本文方法具有更大的意義.相比于文獻[12]提出的方法，本文方法更加有效.θ的取值能夠決定挖掘信任關系的數量，由圖1可見，無論是PtrustSVD還是PTtrustSVD算法，θ為0.45時效果最好，當θ值再繼續(xù)減小時，效果反而不好，出現了過擬合現象.以上實驗說明深度挖掘隱式信息不僅能緩解數據稀疏問題，而且有助于矩陣分解算法實現更好地推薦效果.

表1 PtrustSVD、PTtrustSVD與trustSVD性能對比

3 結束語

基于心理學中結構平衡理論和社會地位理論，通過分析用戶之間的行為數據，使用Pearson相關系數挖掘出用戶之間的隱式信任關系，結合信任傳遞機制，從而可以有效地改進基于社交網絡的協(xié)同過濾推薦效果.

對于信任關系的處理還可以改進，比如衡量信任關系的標準有很多，信任關系也存在負關系等，信任傳遞時是否還有其他更一般的方法.這些都是我們今后要研究的問題，如果能夠更加深入地考慮信任關系，可以進一步提高推薦的效果.

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

[2] JUDITH MASTHOFF. Recommender systems handbook [M]. Boston：Springer， 2010：85-89.

[3] GUADOMAVICIUS， A TUZHILIN. Towards the next generation of recommender systems：a survey of the state-of-the-art and possible extensions [J]. IEEE Transactions on Knowledge and Data Engineering， 2005，17:634-749.

[4] GUO G， ZHANG J， YORKE-SMITH NEIL. 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.Palo Alto：AAAI Press，2015:123-129.

[5] KOREN Y. Factorization meets the neighborhood：a multifaceted collaborative filtering model[C]//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD). Newyork：ACM， 2008:426-434.

[6] GUO G， ZHANG J， THALMANN D. Merging trust in collaborative filtering to alleviate data sparsity and cold start [J]. Knowledge-Based Systems， 2014， 57 (2)：57-68.

[7] HEIDER F. Attitudes and cognitive organization [J]. Journal of Psychology， 1946， 21(1):107-112.

[8] 程蘇琦， 沈華偉， 張國清， 等. 符號網絡研究綜述[J]. 軟件學報， 2014， 25(1)：1-15.

[9] 王英， 王鑫， 左萬利. 基于社會學理論的信任關系預測模型[J]. 軟件學報， 2014， 25(12)：2893-2904.

[10] GUO G， ZHANG J， THALMANN D， et al. From ratings to trust：an empirical study of implicit trust in recommender systems[C]//ACM Symposium on Applied Computing.Newyork：ACM， 2014:248-253.

[11] PAPAGELIS M， PLEXOUSAKIS D， KUTSURAS T. Alleviating the sparsity problem of collaborative filtering using trust inferences[M]. Berlin：Springer Berlin Heidelberg， 2005：224-239.

[12] WANG JIATONG， FEI ZHENQIAN， QIAO SHUYU， et al. A novel recommendation method based on user’s interest and heterogeneous information[C]//Asia-Pacific Web Conference. Switzerland：Springer International Publishing， 2016:90-101.

[13] BEIGI G， TANG J， WANG S， et al. Exploiting emotional information for trust/distrust prediction[C]//International Conference on Data Mining.Philadelphia：SIAM，2016:81-89.

[14] CALLINGHAM R. Six degrees：the science of a connected age[J]. Times Literary Supplement Tls， 2005， 61(1):93.

Arecommendationalgorithmbasedonuserbehaviorinformationandtrusttransferring

ZHANG Bang-zuo， WANG Jia-tong， SUN Wei， QIAO Shu-yu， FENG Guo-zhong， SUN Xiao-xin

(School of Information Science and Technology， Northeast Normal University， Changchun 130117，China)

Based on the similarity of user behavior information and trust transferring to infer the implicit trust relationship， this paper proposes a novel algorithm that integrated with matrix composition technique， namely， PTtrustSVD. The experimental results show that the purposed method using the implicit trust relation outperforms that only using explicit trust relation in the Filmtrust dataset， and prove that the implicit trust relation is effective for the recommender system.

recommender system； implicit trust； trust transferring

1000-1832(2017)04-0071-05

10.16163/j.cnki.22-1123/n.2017.04.014

2016-10-27

國家自然科學基金資助項目(71473035，11501095)；吉林省科技發(fā)展計劃項目(20150204040GX，20170520051JH)；吉林省發(fā)改委項目(2015Y055)；東北師范大學自然科學基金資助項目(2014015KJ004).

張邦佐(1971—)，男，博士，副教授，主要從事數據庫與數據挖掘、推薦系統(tǒng)研究.

TP 391.3學科代碼520·2040

A

(責任編輯：石紹慶)