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

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

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

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

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

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

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

0 引言

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

目前，基于用戶社交信任關(guān)系的推薦方法是推薦系統(tǒng)中的研究熱點(diǎn)，2015年G.Guo等[4]提出了一種基于用戶信任和評分項(xiàng)目的矩陣分解技術(shù)，在SVD++算法[5]基礎(chǔ)上，擴(kuò)展了隱式信任關(guān)系，將顯式和隱式信任關(guān)系加入到推薦方法中.對于興趣推薦來說，信任關(guān)系比朋友關(guān)系更有價(jià)值[6].為了更好地發(fā)現(xiàn)隱式信任關(guān)系，人們將心理學(xué)中的兩個(gè)著名理論結(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)系，同時(shí)社會地位理論表明社會地位是具有傳遞性.

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

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

1.1 信任的定義

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

1.2 信任的測量

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

(1)

(2)

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

(3)

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

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

(4)

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

1.3 信任傳遞

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

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

(5)

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

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

(6)

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

1.4 trustSVD

(7)

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

(8)

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

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

(9)

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

1.5 PTtrustSVD

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

(10)

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

(11)

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

2 結(jié)果與討論

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

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

2.2 評估標(biāo)準(zhǔn)

(12)

(13)

2.3 結(jié)果對比分析

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

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

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

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

表1 PtrustSVD、PTtrustSVD與trustSVD性能對比

3 結(jié)束語

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

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

[1] 胡勛， 孟祥武， 張玉潔， 等. 一種融合項(xiàng)目特征和移動用戶信任關(guān)系的推薦算法[J]. 軟件學(xué)報(bào)， 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é)報(bào)， 2014， 25(1)：1-15.

[9] 王英， 王鑫， 左萬利. 基于社會學(xué)理論的信任關(guān)系預(yù)測模型[J]. 軟件學(xué)報(bào)， 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é)基金資助項(xiàng)目(71473035，11501095)；吉林省科技發(fā)展計(jì)劃項(xiàng)目(20150204040GX，20170520051JH)；吉林省發(fā)改委項(xiàng)目(2015Y055)；東北師范大學(xué)自然科學(xué)基金資助項(xiàng)目(2014015KJ004).

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

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

A

(責(zé)任編輯：石紹慶)