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

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

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

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

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

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

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

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

0 引言

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

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

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

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

1.1 信任的定義

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

1.2 信任的測量

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

(1)

(2)

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

(3)

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

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

(4)

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

1.3 信任傳遞

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

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

(5)

這樣就得到了一個新的隱式信任數(shù)據(jù)集，即

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

(6)

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

1.4 trustSVD

(7)

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

(8)

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

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

(9)

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

1.5 PTtrustSVD

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

(10)

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

(11)

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

2 結(jié)果與討論

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

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

2.2 評估標準

(12)

(13)

2.3 結(jié)果對比分析

圖1 2種方法的MAE和RMSE結(jié)果對比

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

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

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

表1 PtrustSVD、PTtrustSVD與trustSVD性能對比

3 結(jié)束語

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

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

[1] 胡勛， 孟祥武， 張玉潔， 等. 一種融合項目特征和移動用戶信任關(guān)系的推薦算法[J]. 軟件學(xué)報， 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] 程蘇琦， 沈華偉， 張國清， 等. 符號網(wǎng)絡(luò)研究綜述[J]. 軟件學(xué)報， 2014， 25(1)：1-15.

[9] 王英， 王鑫， 左萬利. 基于社會學(xué)理論的信任關(guān)系預(yù)測模型[J]. 軟件學(xué)報， 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

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

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

TP 391.3學(xué)科代碼520·2040

A

(責任編輯：石紹慶)