張維玉,吳　斌,耿玉水,朱　江

(1.北京郵電大學(xué)智能通信軟件與多媒體北京市重點實驗室,北京 100876;2.齊魯工業(yè)大學(xué)信息學(xué)院,山東濟(jì)南 250353)

基于協(xié)同矩陣分解的評分與信任聯(lián)合預(yù)測

張維玉1,2,吳斌1,耿玉水2,朱江1

(1.北京郵電大學(xué)智能通信軟件與多媒體北京市重點實驗室,北京 100876;2.齊魯工業(yè)大學(xué)信息學(xué)院,山東濟(jì)南 250353)

信息評分預(yù)測和信任預(yù)測是社交評價網(wǎng)絡(luò)中的兩大基本問題.為應(yīng)對在提高兩類基本問題預(yù)測準(zhǔn)確性過程中遇到的評分?jǐn)?shù)據(jù)與信任關(guān)系數(shù)據(jù)稀疏問題,本文提出了一種基于協(xié)同矩陣分解的信息評分與信任預(yù)測聯(lián)合模型.該模型在將評分矩陣與信任關(guān)系矩陣進(jìn)行協(xié)同分解時,既能保證被分解的兩個矩陣分解過程共享用戶潛在變量,又能兼顧兩個矩陣分解過程中能夠各自獲得反映本領(lǐng)域知識相關(guān)性的表達(dá).使用分解得到的多個相關(guān)低維潛在變量矩陣乘積即可做出評分與信任兩個問題的預(yù)測.兩個真實網(wǎng)絡(luò)數(shù)據(jù)集上的實驗驗證了提出模型有效性和先進(jìn)性.

推薦算法;信任預(yù)測;概率矩陣分解;社交推薦網(wǎng)絡(luò)

1　引言

隨著Web2.0技術(shù)和計算機(jī)網(wǎng)絡(luò)技術(shù)的不斷發(fā)展,社交媒體已成為人們進(jìn)行信息分享、意見表達(dá)和結(jié)交朋友的主要媒介.一類社交媒體(如:Epinion等)可以方便用戶對各種信息進(jìn)行評論,同時還允許用戶對看到的信息進(jìn)行評分(Rating),另外,這類社交媒體還具備讓用戶根據(jù)對其他用戶做出的評分信息的喜好程度來建立信任(Trust)或朋友關(guān)系的功能.這類社交媒體的流行使人們相對傳統(tǒng)社交媒體更容易獲得信息,更容易結(jié)交朋友.然而人們在享受這種便利的同時,也在面臨著信息過載的困擾.如何更好地向用戶推薦潛在有用的信息以及可信任的用戶,是社交媒體亟需解決的兩大核心問題.

目前信息推薦和好友推薦所面臨的主要問題是數(shù)據(jù)稀疏和冷啟動兩個方面.在以往研究中,朋友推薦和信息推薦一般分開進(jìn)行.然而,在社交媒體中用戶與用戶之間的信任關(guān)系和用戶與信息之間的評分關(guān)系是有關(guān)聯(lián)的.建立信任關(guān)系的用戶在評價信息的時候更容易做出一致的評分,同時,在信息評分相似的用戶間也更容易建立信任關(guān)系.基于這一假設(shè),我們將對信任關(guān)系的預(yù)測和用戶對信息評分的預(yù)測進(jìn)行聯(lián)合研究,旨在同時在這兩個問題上獲得更好的預(yù)測效果.具體來講我們首先將社交媒體中信任和評分兩類關(guān)系使用兩個矩陣進(jìn)行描述,然后對這兩個矩陣進(jìn)行協(xié)同矩陣分解.協(xié)同分解過程中保持潛在用戶特征不變,以使兩個矩陣分解過程中能夠共享特征信息.另外,兩個矩陣分解過程中還各自引入一個表達(dá)本領(lǐng)域潛在特征相關(guān)性的矩陣,使其分解過程能夠充分表達(dá)領(lǐng)域內(nèi)的知識特征.協(xié)同矩陣分解的結(jié)果是一組低維潛在特征矩陣,如潛在用戶特征矩陣,潛在信息特征矩陣等.使用多個相關(guān)潛在特征矩陣的乘積即可做出評分與信任兩類問題的預(yù)測.

2　相關(guān)工作

信任預(yù)測屬于鏈路預(yù)測的范疇.鏈路預(yù)測的定義最早由Kleinberg等人在文獻(xiàn)[1]中給出.信任預(yù)測方面的文獻(xiàn)目前主要可以分為無監(jiān)督信任預(yù)測和有監(jiān)督信任預(yù)測兩類.無監(jiān)督信任預(yù)測主要是基于信任傳播開展研究的,文獻(xiàn)[2]最早使用信任傳播來研究信任預(yù)測的問題.文獻(xiàn)[3]使用矩陣分解的方式將信任預(yù)測的問題轉(zhuǎn)換為一個優(yōu)化問題進(jìn)行求解.有監(jiān)督信任預(yù)測問題本質(zhì)上講就是構(gòu)建一個二元分類器.文獻(xiàn)[4]將一個在線社交網(wǎng)絡(luò)上的分類特征進(jìn)行了整理,并使用得到的網(wǎng)絡(luò)特征對分類器進(jìn)行訓(xùn)練從而進(jìn)行最終的信任預(yù)測.文獻(xiàn)[5]則從異質(zhì)信任關(guān)系的角度研究了信任預(yù)測、信息推薦等問題.

評分預(yù)測是推薦系統(tǒng)的主要功能.傳統(tǒng)的推薦系統(tǒng)主要分為兩類:基于內(nèi)容過濾推薦算法和基于協(xié)同過濾推薦算法.而基于協(xié)同過濾推薦算法又可細(xì)分為:基于記憶的方法和基于模型的方法.其中基于內(nèi)容過濾推薦算法在擴(kuò)展性方面較差通常無法靈活融合多方面有用信息,而協(xié)同過濾算法則可靈活融合顯式或隱式評分?jǐn)?shù)據(jù)進(jìn)行推薦.

近年來,矩陣分解算法已成為推薦系統(tǒng)的主流方法.傳統(tǒng)的矩陣分解方法有:奇異值分解[6]、非負(fù)矩陣分解[7]等方法.為了從概率生成過程角度描述矩陣分解的過程,文獻(xiàn)[8]提出了概率矩陣分解方法,該方法適用于觀測不完整的評分矩陣.文獻(xiàn)[9]提出了一種協(xié)同矩陣分解的方法,該方法的優(yōu)勢在于可以同時對多個評分矩陣進(jìn)行分解,并且分解的過程中可以共享一些潛在特征信息.文獻(xiàn)[10]使用協(xié)同矩陣分解的方法研究了信息推薦問題,該文章從遷移學(xué)習(xí)的角度利用用戶與信息間的喜好矩陣作為輔助信息進(jìn)而實現(xiàn)用戶對信息的評分預(yù)測.文獻(xiàn)[11]首次把信任預(yù)測和評分預(yù)測進(jìn)行聯(lián)合研究,但是該文獻(xiàn)提出的是一種基于潛在變量的隨機(jī)游走模型.文獻(xiàn)[12]提出了一種基于受限信任關(guān)系和概率矩陣分解的推薦方法.

3　問題定義

社交評價網(wǎng)絡(luò):是一種包含兩種類型節(jié)點和兩種關(guān)系的異質(zhì)網(wǎng)絡(luò).兩種類型的節(jié)點分別為:用戶和信息,分別記為U和I.兩種類型的關(guān)系分別為用戶與用戶之間的信任關(guān)系和用戶與信息之間的評價關(guān)系.社交評價網(wǎng)絡(luò)中的兩類關(guān)系可以使用兩個矩陣表達(dá),即信任關(guān)系使用矩陣T表示,評價關(guān)系使用矩陣R表示.社交評價網(wǎng)絡(luò)的結(jié)構(gòu)一般如圖1所示:

信任與評價聯(lián)合預(yù)測:在社交網(wǎng)絡(luò)中,已知觀測到的不完整的信任關(guān)系和評分關(guān)系,利用兩種關(guān)系的相關(guān)性,同時推斷出缺失的信任關(guān)系與評分信息.

4　JRTPCMF模型

我們假設(shè)用戶u在信息i上的評價用rui表示,它可以由潛在用戶特征向量Uu∈1×du,潛在信息特征向量Vi∈1×dv和矩陣B∈du×dv的乘積得到.為了說明上的方便,我們設(shè)定du=dv=d.因此我們可以定義出rui的一個條件概率分布:

(1)

(2)

(3)

P(B|β)=N(B|0,(β/q)-1I)

(4)

ln P(U,B,V|R,αr,αu,αv,β)

P(Uu|αu)P(Vi|αv)P(B|β)]yui

(5)

是一個常數(shù).對于矩陣T使用上述類似方法得到其后驗概率:

(6)

將上述兩個后驗概率進(jìn)行加權(quán)求和,最終我們可以將提出的聯(lián)合預(yù)測模型的優(yōu)化問題整理為:

s.t.U∈n×d,V∈m×d

(7)

(1)固定矩陣B和V,求解矩陣U.

我們使用文獻(xiàn)[10]中類似的方法,采用解析的方式得到矩陣U的更新公式,具體過程如下:

(8)

使用上述類似方法,我們固定B和U,可以得到矩陣V的更新公式如式(9)所示:

(9)

(10)

(11)

vec(B)=(AT+βI)-1vec(Z)

(12)

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

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

為了驗證提出模型的有效性和先進(jìn)性,我們使用兩種真實的網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行實驗.其中Epinion是一個信息產(chǎn)品資訊網(wǎng)站,Flixster.com則是一個著名社交服務(wù)網(wǎng)站.兩個數(shù)據(jù)集的基本信息統(tǒng)計情況如表1所示.

表1　數(shù)據(jù)集基本信息統(tǒng)計表

5.2評價指標(biāo)

對于信息評價預(yù)測問題,我們使用最流行的MAE(Mean Absolute Error)指標(biāo)進(jìn)行評估,定義如下:

(13)

對于信任預(yù)測問題,我們使用文獻(xiàn)[3]等廣泛采用的AR(Average Recall)指標(biāo)來進(jìn)行評價,定義如下:

(14)

其中N是測試用戶的個數(shù),TNu代表用戶u真實的信任關(guān)系列表,而TLu則代表預(yù)測算法給出的信任列表,此處我們將N設(shè)定為5.

5.3實驗設(shè)定

對于信息評分和信任預(yù)測兩個問題,我們各自選取三個目前流行的算法進(jìn)行對比實驗.其中,三個信息評分算法分別為:PMF(Probabilistic Matrix Factorization)[8]、CPMF(Constrained Probabilistic Matrix Factorization)[8]和SoRec[13].三個信任預(yù)測算法分別為:TP(Trust Propagation)[2]、MF(Matrix Factorization)[14]和hTrust[3].

對于矩陣分解類算法在進(jìn)行預(yù)測時,潛在變量的維數(shù)與最終預(yù)測的準(zhǔn)確度密切相關(guān).我們通過使用隨機(jī)抽取的數(shù)據(jù)來訓(xùn)練模型,并觀察預(yù)測準(zhǔn)確度與維數(shù)的關(guān)系,最終發(fā)現(xiàn)當(dāng)潛在變量維數(shù)達(dá)到20后,各算法預(yù)測的準(zhǔn)確度增加非常緩慢.因此,本文各矩陣分解類算法的潛在變量維數(shù)d均設(shè)定為20.另外,在沒做特殊說明的情況下,本文給出的預(yù)測結(jié)果都是各算法在參數(shù)最優(yōu)的情況下獲得.本文中進(jìn)行對比實驗的所有算法均使用MATLAB語言進(jìn)行實現(xiàn),程序運行主機(jī)為一臺安裝了Centos 6.0操作系統(tǒng)的PC服務(wù)器,主機(jī)內(nèi)存為32GB,CPU主頻為2.8GHz.

5.4實驗結(jié)果

我們從訓(xùn)練數(shù)據(jù)評分矩陣R中隨機(jī)選出M個評分,并將這M個評分作為驗證數(shù)據(jù)集從而來確定αu,αv,αr以及β的參數(shù)值分別為{0.1,0.1,1,1}.然后,在訓(xùn)練時我們分別隨機(jī)選取數(shù)據(jù)集的50%,70%和90%作為訓(xùn)練數(shù)據(jù)集來對模型進(jìn)行訓(xùn)練,數(shù)據(jù)集中剩余部分作為測試集對預(yù)測算法的效果進(jìn)行測試,我們采取交叉驗證的方式進(jìn)行實驗.實驗得到的預(yù)測結(jié)果分別如圖2～圖5所示.

在信息評分預(yù)測結(jié)果中,可以看到PMF效果最差,其他三種算法的預(yù)測效果都要比PMF好不少.這是因為PMF在進(jìn)行矩陣分解時,僅使用了評分矩陣R,而矩陣R本身又非常稀疏,所以算法在學(xué)習(xí)過程中并不能將真實的預(yù)測過程包含其中.SoRec和提出的JRTPCMF雖然在進(jìn)行信息評分預(yù)測時都使用了矩陣R和T的信息,但是JRTPCMF的預(yù)測效果明顯要好于SoRec,分析原因應(yīng)該是JRTPCMF在矩陣分解時,既能像SoRec算法那樣共享潛在用戶特征信息,又能對兩種領(lǐng)域知識引入各自相關(guān)性矩陣,從而在表達(dá)用戶評價信息產(chǎn)生過程方面更具優(yōu)勢.另外,各對比算法在兩個數(shù)據(jù)集上的預(yù)測效果是一致的,這說明在不同社交評價網(wǎng)絡(luò)中,利用信任關(guān)系都可以緩解評價數(shù)據(jù)集上的數(shù)據(jù)稀疏問題.

在信任預(yù)測結(jié)果中,四種對比算法的預(yù)測準(zhǔn)確率并沒有隨著訓(xùn)練數(shù)據(jù)比例的增加而提升,反而出現(xiàn)了不同程度的下降.究其原因應(yīng)該與我們所使用的數(shù)據(jù)集不足夠大有關(guān).TP算法在四個算法中預(yù)測效果最差,這是因為它使用的數(shù)據(jù)僅是矩陣T,而矩陣T的稀疏性本身就是對信任預(yù)測問題的一大挑戰(zhàn).除TP以外其他三個算法都是基于矩陣分解的,在預(yù)測中都獲得了較好的結(jié)果,這說明基于矩陣分解的方法在解決該類問題時具有較大的優(yōu)勢.hTrust算法雖然也借助了評分信息來幫助信任的預(yù)測,但是在兩個實驗數(shù)據(jù)集上其預(yù)測效果都不如提出的JRTPCMF.這是因為提出的JRTPCMF在進(jìn)行矩陣分解時能夠使評分信息域和信任關(guān)系信息域互相借助彼此的領(lǐng)域信息,而不是像hTrust算法那樣只是單向借助評分信息解決信任預(yù)測問題.

6　結(jié)論

本文基于協(xié)同矩陣分解提出了一個信任與評分聯(lián)合預(yù)測的模型,該模型在對評分矩陣和信任關(guān)系矩陣進(jìn)行協(xié)同分解時,既能保證分解過程共享潛在用戶特征,又能兼顧兩個矩陣的分解能夠各自表達(dá)本領(lǐng)域內(nèi)的特征信息相關(guān)性.在兩個真實網(wǎng)絡(luò)數(shù)據(jù)集上對提出模型和最新主流算法進(jìn)行了對比實驗,實驗結(jié)果驗證了提出模型的有效性和先進(jìn)性.下一步工作將重點研究面向大數(shù)據(jù)集的并行矩陣分解算法以更好地解決信任與評分預(yù)測的問題.

[1]Liben Nowell D,Kleinberg J.The link-prediction problem for social networks[J].Journal of the American Society for Information Science and Technology,2007,58(7):1019-1031.

[2]Guha R,Kumar R,Raghavan P,et al.Propagation of trust and distrust[A].Proceedings of the 13th International Conference on World Wide Web[C].New York:ACM,2004.403-412.

[3]Tang J,Gao H,Hu X,et al.Exploiting homophily effect for trust prediction[A].Proceedings of the Sixth ACM International Conference on Web Search and Data Mining[C].Rome:ACM,2013.53-62.

[4]Liu H,Lim E P,Lauw H W,et al.Predicting trusts among users of online communities:an epinions case study[A].Proceedings of the 9th ACM Conference on Electronic Commerce[C].Chicago:ACM,2008.310-319.

[5]Tang J,Gao H,Liu H.mTrust:discerning multi-faceted trust in a connected world[A].Proceedings of the Fifth ACM International Conference on Web Search and Data Mining[C].Seattle:ACM,2012.93-102.

[6]Lee D D,Seung H S.Algorithms for non-negative matrix factorization[A].Proceedings of Advances in Neural Information Processing Systems[C].2001 556-562.

[7]Luo X,Zhou M,et al.An efficient non-negative matrix-factorization-based approach to collaborative filtering for recommender systems[J].IEEE Transactions on Industrial Informatics,2014,10(2):1273-1284.

[8]Mnih A,Salakhutdinov R.Probabilistic matrix factorization[A].Proceedings of Advances in Neural Information Processing Systems 2007[C].Vancouver,1257-1264.

[9]Singh A P,Gordon G J.Relational learning via collective matrix factorization[A].Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining[C].Las Vegas:ACM,2008.650-658.

[10]Pan W,Yang Q.Transfer learning in heterogeneous collaborative filtering domains[J].Artificial Intelligence,2013,197:39-55.

[11]Yang S H,Long B,Smola A,et al.Like like alike:joint friendship and interest propagation in social networks[A].Proceedings of the 20th International Conference on World Wide Web[A].Hyderabad:ACM,2011.537-546.

[12]印桂生,張亞楠,董宇欣,韓啟龍.基于受限信任關(guān)系和概率分解矩陣的推薦[J].電子學(xué)報,2014,42(5):904-911.

YIN Gui-sheng,ZHANG Ya-nan,DONG Yu-xin,HAN Qi-long.A constrained trust recommendation using probabilistic matrix factorization[J].Acta Electronica Sinica,2014,42(5):904-911.(in Chinese)

[13]Ma H,Zhou D,Liu C,et al.Recommender systems with social regularization[A].Proceedings of the fourth ACM International Conference on Web Search and Data Mining[C].Hong Kong:ACM,2011.287-296.

[14]Zhu S,Yu K,Chi Y,et al.Combining content and link for classification using matrix factorization[A].Proceedings of the 30th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval[C].Amsterdam:ACM,2007.487-494.

張維玉男,1978年6月生于山東兗州.現(xiàn)在北京郵電大學(xué)攻讀博士學(xué)位,研究方向為社交網(wǎng)絡(luò)分析、數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí).

E-mail:zwy@bupt.edu.cn

吳斌男,1969年11月生于湖南長沙.現(xiàn)為北京郵電大學(xué)博士生導(dǎo)師,研究方向為圖數(shù)據(jù)挖掘、智能信息處理.

Joint Rating and Trust Prediction Based on Collective Matrix Factorization

ZHANG Wei-yu1,2,WU Bin1,GENG Yu-shui2,ZHU Jiang1

(1.Beijing Key Laboratory of Intelligent Telecommunications Software and Multimedia, Beijing University of Posts and Telecommunications,Beijing 100876,China; 2.School of Information,Qilu University of Technology,Jinan,Shandong 250353,China)

Trust prediction and information item rating are two fundamental tasks for social rating network systems.In response to data sparsity of trust relation and rating information encountered when improving the accuracy of predicting the two basic problems,we present a joint model of rating and trust prediction based on collective matrix factorization.In our model,trust relation matrix and information rating matrix are factorized into latent features matrixes collectively.We can make full use of correspondence among users and information items by sharing latent user feature.Moreover,our model can capture the data dependent effect of trust domains and rating domain separately.By using those learned latent features matrixes multiplication,we can obtain predictions of trust and rating.Experimental results on two real network data demonstrate that our model is more accurate than other state-of-the-art methods.

recommendation algorithms;trust prediction;probabilistic matrix factorization;social rating networks

2015-02-06;

2016-01-20;責(zé)任編輯：李勇鋒

國家973重點基礎(chǔ)研究發(fā)展計劃項目(No.2013CB329606);國家自然科學(xué)基金(No.71231002，No.61375058)

TN911.23

A

0372-2112 (2016)07-1581-06

??學(xué)報URL:http://www.ejournal.org.cn

10.3969/j.issn.0372-2112.2016.07.009