王磊 任航 龔凱

摘 要：針對現(xiàn)有社會化推薦算法在信任分析方面的不足，研究了從社交輔助信息中充分挖掘用戶信任關(guān)系的方法，進(jìn)而提出一種基于多維信任計算和聯(lián)合矩陣分解的社會化推薦算法。首先，從用戶社交行為、社交圈特征獲得用戶的動態(tài)和靜態(tài)兩種局部信任度，再利用信任網(wǎng)絡(luò)的結(jié)構(gòu)特征提取全局信任度;然后，構(gòu)造一種對增強(qiáng)關(guān)注矩陣和社交信任矩陣進(jìn)行聯(lián)合矩陣分解的社會化推薦算法，并采用隨機(jī)梯度下降法對其求解。基于新浪微博數(shù)據(jù)集的實驗結(jié)果表明，所提出的算法在推薦精度和TopK推薦能力方面明顯優(yōu)于socailMF、 LOCABAL、 contextMF和TBSVD這幾種代表性的社會化推薦算法。

關(guān)鍵詞：推薦算法;信任關(guān)系;社交網(wǎng)絡(luò);交互行為;聯(lián)合矩陣分解

中圖分類號：TP181

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

Abstract： Aiming at the shortages in trust analysis of existing social recommendation algorithms， a social recommendation algorithm based on multidimensional trust and collective matrix factorization was proposed with full use of user trust relationship mined from social auxiliary information. Firstly， the dynamic and static local trust relationships were extracted respectively from social interaction behaviors and social circle features of the user， and the global trust relationship was extracted from the structural features of trust network. Then， a social recommendation algorithm was presented by collective factorizing the enhanced following relationship matrix and the social trust relationship matrix， and a stochastic gradient descent method was utilized to solve the algorithm. The experimental results on the Sina microblog dataset indicate that the proposed algorithm outperforms some popular social recommendation algorithms such as socialMF， LOCABAL， contextMF and TBSVD （Trust Based Singular Value Decomposition）， in terms of recommendation accuracy and TopK performance.

英文關(guān)鍵詞Key words： recommendation algorithm; trust relationship; social network; interaction; collective matrix factorization

0 引言

隨著Facebook、Twitter、微博、微信等社交網(wǎng)絡(luò)媒體的飛速發(fā)展，信息過載問題日益嚴(yán)峻。旨在研究如何從海量社交數(shù)據(jù)中獲取用戶感興趣的項目和內(nèi)容的社會化推薦算法受到了廣泛的關(guān)注[1-5]。與傳統(tǒng)推薦算法相比，社交網(wǎng)絡(luò)中通常存在更加嚴(yán)重的數(shù)據(jù)稀疏和冷啟動問題，這給社會化推薦算法研究帶來了巨大的挑戰(zhàn)。

為解決該問題，一些學(xué)者較早地研究和利用了普遍存在的社交信任進(jìn)行推薦。他們依據(jù)社會學(xué)中的同質(zhì)理論[2]，認(rèn)為用戶偏好受到其信任的社交好友的顯著影響，提出了RSTE（Recommendation with Social Trust Ensemble）[3]、socialMF[4]、StrengthMF[5]等經(jīng)典的基于信任關(guān)系的社會化推薦算法。但是，這些研究大都將信任視為單一、同質(zhì)的關(guān)系，簡單地從項目評分矩陣或關(guān)注/被關(guān)注關(guān)系中估計出用戶信任，具有較明顯的局限性。

同時，社交網(wǎng)絡(luò)中存在著豐富的輔助信息，例如：用戶行為、網(wǎng)絡(luò)結(jié)構(gòu)、標(biāo)簽等，它們與用戶之間的真實信任關(guān)系存在著密切的聯(lián)系[6]。近年來，一些學(xué)者綜合各種社交輔助信息、評分矩陣、社交關(guān)系等從多方面分析用戶信任，用以提高社會化推薦算法的性能[7-13]， 例如，Tang等[7]認(rèn)為用戶決策受到社交好友和全局聲譽(yù)高的其他用戶的影響，他們分別利用評分相似性和PageRank算法獲得用戶的局部和全局信任，基于矩陣分解方法提出了著名的LOCABAL算法; 余永紅等[8]在前者基礎(chǔ)上，研究從不同社交領(lǐng)域分別提取局部和全局信任，進(jìn)一步提升了算法精度; Wang等[9]充分挖掘了評分和社交關(guān)系數(shù)據(jù)，定義勝任度、可信賴度、評分相似性三個指標(biāo)評價用戶信任關(guān)系; 潘一騰等[10]在socialMF算法框架下，進(jìn)一步將信任細(xì)分為隱含的信任者關(guān)系和被信任者關(guān)系，提升了推薦性能; Ma等 [11]結(jié)合用戶標(biāo)簽相似性和社交關(guān)系定義了信任，提出一種微博推薦算法; Jiang等[12]分別從社交文本、微博轉(zhuǎn)發(fā)行為數(shù)據(jù)中計算出用戶的偏好相似性和社交影響力，從這兩方面衡量用戶的信任關(guān)系，提出了contextMF推薦算法; 此外，Xu等[13]分別利用好友關(guān)系和交互行為定義用戶之間的直接和間接信任，在奇異值矩陣分解框架下提出了TBSVD（Trust Based Singular Value Decomposition）推薦算法。

然而，這些方法大多沒有對社交信任關(guān)系進(jìn)行充分的挖掘和利用，特別是沒有充分重視社交行為在信任分析中的作用。實際上，評分和社交關(guān)系數(shù)據(jù)由于人為主觀因素影響容易出現(xiàn)噪聲[6，14]，而社交行為則能更真實地揭示用戶之間的信任狀態(tài)。此外，上述方法大都忽略了用戶偏好和興趣會隨時間動態(tài)變化的特點[15]。

因此，本文以社交網(wǎng)絡(luò)的項目推薦任務(wù)（如：微博推薦、好友推薦等）為研究對象，設(shè)計一種基于多維度信任計算和聯(lián)合矩陣分解的社會化推薦算法（Multidimension Trust and Collective Matrix Factorization based social recommendation algorithm， MTCMF）。具體地，采用用戶的轉(zhuǎn)發(fā)和評論行為的頻率、社交圈重疊度從動態(tài)和靜態(tài)兩個方面度量局部信任度;利用信任網(wǎng)絡(luò)的結(jié)構(gòu)特征定義全局信任度;同時，結(jié)合社交行為和衰減函數(shù)給出“用戶項目”關(guān)注矩陣的增強(qiáng)方法，更準(zhǔn)確地反映用戶偏好的時間變化;最后，基于聯(lián)合矩陣分解技術(shù)給出了本文的社會化推薦模型和算法。

1 社會化推薦問題定義

假設(shè)社交網(wǎng)絡(luò)中存在m個待推薦項目和n個用戶，分別用集合S={s1，s2，…，sm}和U={u1，u2，…，un}表示。每個用戶可以關(guān)注或訂閱若干項目，也可以同若干用戶形成雙向的好友關(guān)系。令矩陣R=[ri， j]n×m表示“用戶項目”關(guān)注關(guān)系，且滿足ri， j∈{0，1}，其中，ri， j=1表示用戶ui關(guān)注項目sj，反之亦然。令矩陣T=[Ti， j]n×n表示用戶間的社交好友關(guān)系，其中，Ti， j=1表示用戶ui和uj是好友，反之亦然。通常，矩陣R和T具有嚴(yán)重的稀疏性[4-5，7，12-13]。另外，假設(shè)社交網(wǎng)絡(luò)中普遍存在豐富的輔助信息，包括社交行為（如轉(zhuǎn)發(fā)、評論等）及其發(fā)生時間、社交網(wǎng)絡(luò)結(jié)構(gòu)特征等， 其中，令Nuri， j和Nuci， j分別表示在特定日期范圍[ts，te]內(nèi)用戶ui對用戶uj的文章的轉(zhuǎn)發(fā)和評論次數(shù);令tsi， j表示用戶ui對項目sj的最近一次交互行為（包括關(guān)注、轉(zhuǎn)發(fā)和評論）的發(fā)生日期。

社會化推薦的任務(wù)是利用關(guān)注關(guān)系R、好友關(guān)系T以及上述輔助信息預(yù)測當(dāng)前用戶u對特定項目s的偏好程度。

2 社交信任的計算

為了更準(zhǔn)確地度量用戶之間的信任關(guān)系，本章利用社交行為、網(wǎng)絡(luò)結(jié)構(gòu)特征等輔助信息，設(shè)計一種從多個維度進(jìn)行信任計算的方法。

2.1 信任網(wǎng)絡(luò)圖

令G=（U，E）表示信任網(wǎng)絡(luò)圖，E表示用戶間的信任關(guān)系集合，如圖1所示。與文獻(xiàn)[12-13]的思路不同，本文認(rèn)為雙向好友關(guān)系相對于單向關(guān)注關(guān)系體現(xiàn)了更緊密的社會聯(lián)系和信任度。因此，本文直接從社交好友矩陣T獲得邊集E，其中，任意邊（ui，uj）∈E的權(quán)重為Tli， j，代表用戶ui對uj的局部信任度，用戶節(jié)點ui的權(quán)重為Tgi，表示其全局信任度。

2.2 局部信任度的計算

局部信任體現(xiàn)了用戶對社交好友的信任程度，具有非對稱、差異化特點?，F(xiàn)有的基于信任的社會化推薦算法大都從評分?jǐn)?shù)據(jù)和社交關(guān)系中挖掘出隱含的信任關(guān)系[4-5， 7-12];然而，評分?jǐn)?shù)據(jù)和社交關(guān)系中容易受到用戶主觀因素影響而存在噪聲[10，14]，因此，本節(jié)對社交輔助信息進(jìn)行挖掘，從社交行為、社交圈特征中提取動態(tài)和靜態(tài)兩種局部信任度。

總結(jié)上述實驗可知，本文算法在推薦精度和TopK推薦能力兩方面均優(yōu)于其他4種算法，這得益于MTCMF能夠從社交行為、社交圈特征、信任網(wǎng)絡(luò)結(jié)構(gòu)等多個維度更準(zhǔn)確地計算出用戶之間的信任，從而有效地提升了社會化推薦算法的性能。相比較而言，socialMF和LOCABAL簡單地從社交關(guān)系和評分矩陣估計用戶信任，停留在信任計算的表面，因而推薦性能較差;contextMF和TBSVD算法的推薦性能與本文算法較為接近，這也從側(cè)面說明了從社交行為等輔助信息中提取社交信任是一種更為可靠的信任估計方法。

4.3 參數(shù)的影響

MTCMF算法中，信任因子α和信任正則化參數(shù)λT起到重要作用，它們控制了信任關(guān)系在推薦算法中的影響程度，當(dāng)α=0和λT=0時，算法退化為普通的矩陣分解推薦算法，僅依賴于關(guān)注數(shù)據(jù)來學(xué)習(xí)進(jìn)行推薦;當(dāng)α→∞和λT→∞時，則完全依賴社交信任關(guān)系進(jìn)行推薦。實驗中，考察了k=10和訓(xùn)練集比例為80%時，參數(shù)α和λT對算法性能的影響，具體結(jié)果如圖4和圖5所示。

從圖4的結(jié)果可以看出，信任因子α的確對MTCMF算法的準(zhǔn)確度有明顯影響，它取過大值或過小值時均不能充分發(fā)揮社交信任的作用，其合理的取值區(qū)間為[2， 10]，本文取最優(yōu)值α=5。從圖5的結(jié)果可以看出，信任正則化參數(shù)λT對算法的準(zhǔn)確度的影響相對較小，其在區(qū)間[0.1， 2]取值時，算法均能獲得較好結(jié)果，本文取最優(yōu)值λT=0.2。

5 結(jié)語

本文利用交互行為、社交圈、信任網(wǎng)絡(luò)結(jié)構(gòu)提出一種多維度的社交信任計算方法，然后基于聯(lián)合矩陣分解技術(shù)建立了一種新穎的社會化推薦算法。基于新浪微博數(shù)據(jù)集的實驗結(jié)果表明，本文算法在項目推薦任務(wù)中的推薦精度和TopK推薦能力明顯優(yōu)于幾種代表性的社會化推薦算法，具有良好的應(yīng)用前景。在后續(xù)工作中，將研究把標(biāo)簽、位置等更多的輔助信息融入信任計算過程中，以期望進(jìn)一步提高推薦算法的準(zhǔn)確度。

參考文獻(xiàn) （References）

[1] ??? TANG J， HU X， LIU H. Social recommendation： a review[J]. Social Network Analysis & Mining， 2013， 3（4）： 1113-1133.

[2] ??? MCPHERSON M， SMITHLOVIN L， COOK J M. Birds of a feather： homophily in social networks [J]. Annual Review of Sociology， 2001， 27（1）： 415-444.

[3] ??? MA H， KING I， LYU M R. Learning to recommend with social trust ensemble[C]// Proceedings of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval. New York： ACM， 2009： 203-210.

[4] ??? JAMALI M， ESTER M. A matrix factorization technique with trust propagation for recommendation in social networks[C]// Proceedings of the 4th ACM Conference on Recommender Systems. New York： ACM， 2010：135-142.

[5] ??? 郭磊， 馬軍， 陳竹敏. 一種信任關(guān)系強(qiáng)度敏感的社會化推薦算法 [J]. 計算機(jī)研究與發(fā)展， 2013， 50（9）： 1805-1813. （GUO L， MA J， CHEN Z M. Trust strength aware social recommendation method [J]. Journal of Computer Research and Development， 2013， 50（9）： 1805-1813.）

[6] ??? WANG X，WANG Y，GUO J H. Building trust networks in the absence of trust relations [J]. Frontiers of Information Technology & Electronic Engineering， 2017， 18（10）：1591-1600.

[7] ??? TANG J， HU X， GAO H， et al. Exploiting local and global social context for recommendation [C]// Proceedings of the 23rd International Joint Conference on Artificial Intelligence. Menlo Park， CA： AAAI Press， 2013： 2712-2718.

[8] ??? 余永紅， 高陽， 王皓， 等. 融合用戶社會地位和矩陣分解的推薦算法 [J]. 計算機(jī)研究與發(fā)展， 2018， 55（1）： 113-124. （YU Y H， GAO Y， WANG H， et al. Integrating user social status and matrix factorization for item recommendation [J]. Journal of Computer Research and Development， 2018， 55（1）： 113-124.）

[9] ??? WANG M， MA J. A novel recommendation approach based on users weighted trust relations and the rating similarities [J]. Soft Computing， 2015， 20（10）：1-10.

[10] ?? 潘一騰， 何發(fā)智， 于海平. 一種基于信任關(guān)系隱含相似度的社會化推薦算法 [J]. 計算機(jī)學(xué)報， 2018， 41（1）： 65-81.（PAN Y T， HE F Z， YU H P. Social Recommendation algorithm using implicit similarity in trust [J]. Chinese Journal of Computers， 2018， 41（1）： 65-81.）

[11] ?? MA H， JIA M， ZHANG D， et al. Combining tag correlation and user social relation for microblog recommendation [J]. Information Sciences， 2017， 385（C）：325-337.

[12] ?? JIANG M， CUI P， WANG F. Scalable recommendation with social contextual information [J]. IEEE Transactions on Knowledge and Data Engineering， 2014， 26（11）： 2789-2802.

[13] ?? XU X， YUAN D. A novel matrix factorization recommendation algorithm fusing social trust and behaviors in microblogs[C]// Proceedings of the 2017 IEEE 2nd IEEE International Conference on Cloud Computing and Big Data Analysis. Piscataway， NJ： IEEE， 2017： 283-287.

[14] ?? ZHANG Y， CHEN W， YIN Z. Collaborative filtering with social regularization for TV program recommendation [J]. KnowledgeBased Systems， 2013， 54（4）：310-317.

[15] ?? BAO H， LI Q， LIAO S S， et al. A new temporal and social PMFbased method to predict users interests in microblogging [J]. Decision Support Systems， 2013， 55（3）：698-709.

[16] ?? ZHANG J， LIU B， TANG J. Social influence locality for modeling retweeting behaviors [C]// Proceedings of the 23rd International Joint Conference on Artificial Intelligence. San Francisco： AAAI Press， 2013： 2761-2767.

[17] ?? 陳婷， 朱青， 周夢溪， 等. 社交網(wǎng)絡(luò)環(huán)境下基于信任的推薦算法 [J]. 軟件學(xué)報， 2017， 28（3）： 721-731. （CHEN T， ZHU Q， ZHOU M X， et al. Trustbased recommendation algorithm in social network [J]. Journal of Software， 2017， 28（3）： 721-731.）

[18] ?? SINGH A P， GORDON G J. Relational learning via collective matrix factorization [C]// Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York： ACM， 2008： 650-658.