LBSN中融合信任與不信任關系的興趣點推薦

朱敬華，明騫

?

LBSN中融合信任與不信任關系的興趣點推薦

朱敬華，明騫

（黑龍江大學計算機科學與技術學院，黑龍江 哈爾濱 150080）

興趣點（POI, point of interest）推薦是位置社交網(wǎng)絡（LBSN, location-based social network）重要的個性化服務，廣泛用于熱門景點推薦和旅游線路規(guī)劃等。傳統(tǒng)的基于協(xié)同過濾的推薦算法根據(jù)用戶相似性和位置相似性進行推薦，未考慮推薦用戶與目標用戶間的信任關系，而信任關系有助于提高推薦系統(tǒng)的準確性、頑健性和用戶滿意度。首先分析了信任與不信任關系的傳播特征，然后給出了信任度的表示和計算方法，最后提出了融合用戶相似性、地理位置相似性和信任關系的混合推薦模型。實驗結果表明，與傳統(tǒng)協(xié)同過濾推薦方法相比，融合信任關系的混合推薦方法顯著提高了推薦結果的準確性和用戶滿意度。

位置社交網(wǎng)絡；興趣點推薦；協(xié)同過濾；信任關系

1 引言

近年來，隨著智能手機的普及和移動互聯(lián)網(wǎng)技術的飛速發(fā)展，人們使用智能終端來獲取位置信息變得越來越方便、準確?；谖恢玫纳缃痪W(wǎng)絡（LBSN, location-based social network）如Foursquare、Gowalla等逐漸興起，且受到廣大用戶的喜愛[1]。與傳統(tǒng)的社交網(wǎng)絡相比，LBSN中引入了地理位置信息，用戶可以對當前訪問的餐廳、電影院等興趣點（POI, point of interest）簽到，并與好友分享位置等信息。LBSN中包含用戶和興趣點這2類節(jié)點，如圖1所示。其中，1~4代表用戶，1~6代表興趣點，從用戶指向興趣點的有向邊表示用戶在該地點的簽到行為。LBSN中主要包含3種關系：用戶的友鄰關系、用戶與興趣點的簽到關系、興趣點間的地理位置關系。

圖1 用戶—興趣點簽到模型

LBSN中的POI推薦是為用戶推薦新的感興趣位置，并為用戶提供可信、可靠和高滿意度的旅游體驗信息。

傳統(tǒng)的基于協(xié)同過濾（CF, collaborative filtering）的POI推薦方法存在數(shù)據(jù)稀疏、惡意推薦和擴展性等問題[2]。研究表明，社交網(wǎng)絡中的信任關系能夠體現(xiàn)用戶間的興趣相似性和影響力，而興趣度和信任度是正相關的[3]。與系統(tǒng)的推薦相比，人們更喜歡好友的推薦。將社交信任關系融入推薦系統(tǒng)中，能夠解決傳統(tǒng)推薦方法的冷啟動和數(shù)據(jù)稀疏問題。例如，文獻[4]提出基于信任關系的推薦方法CoSRA+T，該方法是對基于用戶相似性的推薦方法CoSRA的改進，將用戶的信任關系融入推薦系統(tǒng)中，能提高推薦的精度。GUO等[5-6]提出利用信任關系進行電影推薦，解決傳統(tǒng)推薦方法的數(shù)據(jù)稀疏和冷啟動問題。在LBSN中，除了社交信任關系外，用戶的地理位置和偏好對POI推薦也有影響。例如，文獻[7]提出基于用戶偏好和背景嵌入的深度神經(jīng)網(wǎng)絡架構，學習用戶和POI相關的各種背景環(huán)境來預測用戶對目標POI的喜好程度。

雖然現(xiàn)有的POI推薦算法中結合了社交信任，但是并沒有考慮用戶間的不信任關系，關于不信任關系對POI推薦的作用研究很少。但是實際的應用系統(tǒng)如Ebay、淘寶等的運營經(jīng)驗表明：在信任模型中引入不信任機制能夠有效抑制用戶的不誠信和惡意推薦。文獻[8]指出不信任關系對推薦起重要的作用，并提出根據(jù)用戶的偏好和信任與不信任關系的推薦系統(tǒng)，實驗結果表明，不信任關系對于推薦質量的提高有顯著的作用。

綜上所述，現(xiàn)有的POI推薦方法缺少對信任關系和不信任關系傳遞特性的研究，因此本文重點研究LBSN中基于信任和不信任關系的POI推薦方法。

如圖1所示，用戶間的實有向邊表示信任關系，1信任3，3信任4；虛有向邊表示不信任關系，1和4都不信任2。本文研究了信任和不信任關系的傳播特征，給出了信任度和不信任度的計算方法。在推薦系統(tǒng)中融入信任關系，改善推薦質量，規(guī)避不信任用戶的惡意推薦。結合用戶相似性、地理位置和信任關系構建了一個混合的POI推薦模型。實驗結果表明，有信任關系的推薦結果的準確度相較傳統(tǒng)的基于用戶相似性的協(xié)同過濾方法有很大的提高，并且保證了推薦結果的可信度，且能夠有效地抵御惡意推薦。

本文的主要貢獻如下。

1) 將信任關系融合到興趣點推薦中，分析了信任與不信任關系的傳播特征，給出了用戶間信任度和不信任度的計算方法。

2) 結合用戶相似性、地理位置和信任關系構建了一個混合興趣點推薦模型，計算目標用戶在興趣點的簽到概率從而生成推薦列表。

2 相關工作

2.1 基于協(xié)同過濾的推薦

該類推薦方法利用歷史簽到信息進行推薦，協(xié)同過濾推薦可分為基于記憶的推薦和基于模型的推薦。Ye等[9]認為用戶簽到受個人喜好、好友影響和興趣點遠近距離3個方面影響，綜合用戶偏好、好友和地理信息提出混合推薦算法，明顯提高了推薦結果的精準度?；谀Ｐ偷耐扑]通過構建用戶評分模型，預測和計算評分，生成推薦。Liu等[10]認為用戶評分由用戶偏好、興趣點屬性、興趣點間距離共同決定，構建了貝葉斯圖模型計算用戶對候選興趣點的喜好程度。Yang等[7]提出基于用戶偏好和背景嵌入的深度神經(jīng)架構，通過學習用戶和POI相關的各種背景環(huán)境來預測用戶對目標POI的喜好程度。利用泛化的矩陣分解方法和拉普拉斯正則化將協(xié)同過濾方法和半監(jiān)督學習（SSL, semi-supervised learning）進行有效橋接。

上述推薦方法均需要用戶的歷史簽到數(shù)據(jù)，且數(shù)據(jù)稀疏性對推薦質量有較大影響。

2.2 基于信任關系的推薦

Guo等[5-6]在推薦系統(tǒng)中融入了用戶間的信任關系，解決傳統(tǒng)CF方法數(shù)據(jù)稀疏和冷啟動問題。Zhang等[11]基于社交關系和地理因素構建了一個推薦模型，根據(jù)用戶簽到記錄、社交影響和地理影響建立組合模型，利用PageRank算法改進模型的推薦精度。Lee等[8]在CF方法中融入信任和不信任關系，利用矩陣分解和近鄰相結合的方法最大化用戶評級信息和信任信息的效用，實驗結果表明，不信任信息對預測用戶評級有相當好的作用。Victor等[12]在基于信任的推薦系統(tǒng)中引入顯式不信任，可提高推薦結果的精準度。Ma等[13]研究推薦系統(tǒng)中隱式信任關系和不信任關系的預測問題。關于信任度的計算，Zhou等[14]選取了6個現(xiàn)實社交網(wǎng)絡進行對比，衡量利用局部信息相似性預測鏈路的效果，結果顯示共同鄰居方法表現(xiàn)最佳。Symeonidis等[15]提出FriendT-NS推薦算法，基本思想是使用鄰居節(jié)點的度信息進行推薦，比隨機游走和最短路徑等方法準確度高。上述方法為基于節(jié)點相似性計算直接信任度，基于路徑的方法主要用于計算間接信任度，需要考慮單一路徑的信任傳遞問題和多信任路徑的信任合并問題。Tobler等[16]提出TidalTrust算法，采用廣度優(yōu)先搜索計算信任度，尋找源用戶與目標節(jié)點之間的所有最短路徑，通過信任度權重計算用戶對不直接相連目標用戶的信任度。

上述工作與本文工作不同之處在于，本文研究了信任與不信任關系的傳遞特征，計算信任和不信任度的方法開銷低。另外，本文提出的混合推薦系統(tǒng)通過考慮多因素、用戶相似性、地理位置鄰近性和信任關系，線性組合后得到推薦評級，能更好地反映實際情況、提高推薦結果質量。

3 預備知識

3.1 基于用戶相似性的推薦

用戶相似性的計算方法很多，如余弦相似度、皮爾遜相關系數(shù)等，本文采用余弦相似度計算用戶u和u的相似性，計算式[9]為

3.2 基于地理位置的推薦

地理學第一定律認為，人類的行為與所處的地域有很大的關系，人們之間的距離越近，關系就越緊密[16]。在LBSN中，用戶的簽到在地理上會有聚集的現(xiàn)象，這種現(xiàn)象主要是因為用戶在選擇簽到位置時會有2種傾向：1) 傾向于去離家或公司較近的地點；2) 傾向于去感興趣的位置附近的地點，即使這些地點可能離家較遠。

因此，對于一個候選的興趣點l，用戶u在l簽到的條件概率[18]為

4 基于局部信任關系的推薦

信任網(wǎng)絡記錄了用戶間的信任關系，用有向圖=<,>表示。代表用戶集合，代表信任關系即有向邊集合。信任網(wǎng)絡如圖2所示，其中，、、、代表4個用戶，6條有向邊表示用戶間的信任關系，邊上的數(shù)值表示信任度。信任網(wǎng)絡與社交網(wǎng)絡不同，信任網(wǎng)絡中的信任關系是單向信任的，信任，不代表也信任。而社交網(wǎng)絡中的好友關系是雙向的，是的朋友，則也是的朋友。

圖2 信任網(wǎng)絡

在信任網(wǎng)絡中，信任關系分為2種，直接信任和間接信任。在圖2中，實線邊表示用戶間的直接信任關系，可以通過信任評價獲得；虛線邊表示間接信任關系，可以通過直接信任的傳遞獲得。從圖2可以看出，用戶直接信任用戶和用戶，根據(jù)信任的傳遞性[17]推斷出，用戶間接信任用戶。

本文同時考慮信任和不信任關系，下面分析它們的傳遞特性，給出信任度和不信任度的計算方法。

4.1 局部信任及其傳遞

根據(jù)用戶信任度計算時涉及的相關用戶的范圍，信任分為局部信任和全局信任2種。與全局信任相比，局部信任關系由于具有個性化特征，因此更適合度量用戶間的信任度[10]。但是，計算局部信任度時需要計算所有用戶對的信任度，全局信任度計算只為每個用戶計算一次，因此局部信任的計算開銷更大。在系統(tǒng)安全性方面，盡管2種信任都可能受到惡意攻擊，但是由于局部信任的傳遞路徑的起始節(jié)點由用戶自主選取，因此可以降低受攻擊的可能性[16]。

其中，()為被用戶信任的鄰居用戶集，()為被用戶信任的鄰居用戶集。

圖3是一個簡單的局部信任傳播計算實例，用戶間的連線表示信任關系。在本例中，()={,}，()={,}，maxW,k=1，則用戶對用戶的信任度為

4.2 局部不信任及其傳遞

社交網(wǎng)絡中信任問題的研究主要集中于信任的計算和信任的傳遞，然而關于不信任關系的研究才剛剛起步，因此對不信任問題的研究相對較少。在推薦系統(tǒng)中利用不信任關系的算法更是少之又少，主要原因包括：1) 在社交網(wǎng)絡中，很難獲得不信任關系的數(shù)據(jù)；2) 不信任關系的傳遞性與信任關系的傳遞性不同，人們對于怎樣利用不信任關系輔助推薦意見并不統(tǒng)一。

圖4 用戶A到用戶C的簡單二級通路傳遞模型

社交平衡理論[18]研究了3人間的友好和敵對關系。該理論認為，類似于“我朋友的朋友是我的朋友”的社會關系比“我朋友的朋友是我的敵人”更為常見，也更為穩(wěn)定。則由社交平衡理論可知，在只有3個用戶的社交結構中，用戶到用戶的二級通路中只有2種類型是可以穩(wěn)定存在的，第一種類型是用戶不信任中間用戶，中間用戶信任用戶，則到潛在的是不信任關系；第二種類型是用戶信任中間用戶，中間用戶信任用戶，則到潛在的是信任關系。

根據(jù)上述分析可知，當用戶到用戶之間不存在直接信任和不信任關系時，用戶對用戶的不信任度計算式為

其中，表示用戶與用戶之間的中間用戶；out()、out(A)、out(A)分別表示的出鄰居、信任的鄰居和不信任的鄰居；in(+)是信任中間用戶的用戶集合。式(6)右邊的第一個式子中的min運算表示不信任的鄰居中的最小信任度（不信任度為負值，該值表示對最不信任用戶的信任度），第二個式子中的max表示信任的鄰居用戶中的最大信任度。

4.3 綜合2種局部信任關系

綜上所述，在信賴朋友的影響下，用戶u去l的概率為

其中，集合F表示用戶u信賴的朋友集合，W,k表示用戶u對用戶u的信任度，c,j表示用戶u在l的歷史簽到信息，c,j=1表示u去過地點l，c,j=0表示其未去過地點l。

一般地，推薦時人們更傾向于考慮直接信任，因此當兩用戶之間同時存在2種信任關系時，只利用直接信任關系進行推薦。

在信任社交網(wǎng)絡中，根據(jù)Jaccard系數(shù)方法可以計算出相鄰用戶間的信任度和不信任度。具有傳遞條件的非相鄰用戶，根據(jù)社交平衡理論，尋找到所有符合條件的二級通路，計算信任和不信任關系的傳遞，即得非相鄰用戶間的信任度。非相鄰用戶u對用戶u的信任度計算式為

5 融合信任關系的混合推薦系統(tǒng)

5.1 混合框架

在第3節(jié)中，本文詳細介紹了基于用戶相似性和基于地理位置這2種推薦方法。這2種方法雖然能夠為用戶推薦興趣點，但是推薦的質量并不理想?，F(xiàn)實中，人們更傾向于接納信賴的朋友的推薦，因此本文在第4節(jié)詳細分析了信任與不信任關系的傳播和計算方法。在LBSN中，用戶根據(jù)其所信任朋友的簽到歷史考慮去一個新地點的可能性，更符合實際。因此，本文將用戶相似性、地理位置和信任關系這3種影響進行線性組合，確定用戶u到興趣點l的概率為

對于偽造簽到記錄的惡意用戶，即使該用戶的虛假簽到記錄與目標用戶高度相似，也不能對目標用戶的POI推薦產生決定性的影響。根據(jù)式(9)，對目標用戶的POI推薦依賴于用戶相似性、地理相似性和信任關系。一個惡意用戶無法通過建立直接和間接的朋友關系獲得目標用戶的足夠信任，因此也無法對目標用戶進行惡意推薦。

5.2 單因素簽到可能性

根據(jù)式(1)可得基于用戶相似的推薦概率為

根據(jù)式(4)可得基于位置相似的推薦概率為

根據(jù)式(7)可得基于信任關系的推薦概率為

因此，有

5.3 生成推薦

根據(jù)上述構建的混合框架，生成推薦的具體步驟如下。

步驟1 分別實現(xiàn)基于用戶相似性、地理位置和信任關系的推薦。

步驟2 使用步驟1的3個推薦，分別篩選出top-個候選興趣點集合。

步驟3 根據(jù)混合框架線性組合的3組推薦結果，得到最終的推薦序列。

5.4 復雜性分析

6 實驗對比與分析

本節(jié)通過實驗分析，驗證提出的混合推薦算法的性能：1) 分析推薦算法中的不同因素，如用戶相似性、地理位置和信任關系，在推薦中各自的影響權重；2) 對比融合信任關系的推薦算法和傳統(tǒng)算法的推薦結果的準確性以及算法的時間效率。

6.1 實驗數(shù)據(jù)和參數(shù)設置

6.2 評價指標

6.3 實驗結果分析

本文將融合用戶相似性、地理位置和信任關系的混合興趣點推薦方法（TSG）與以下3種推薦方法進行比較。

1) user-based CF(U)：基于用戶相似性的推薦。

2) preference and context embedding(PACE)[7]：基于用戶偏好和背景嵌入的深度神經(jīng)網(wǎng)絡推薦。

3) user social and geographical model (USG)[8]：基于用戶社交關系和地理因素的推薦。

圖5~圖7顯示了在Foursquare和Gowalla數(shù)據(jù)集上運行4種推薦算法的實驗結果。分別考察興趣點個數(shù)=5、10和20時，4種推薦算法的準確率和召回率。

圖5顯示了在=5、10、20情況下，4種推薦算法的準確率和召回率。從圖5可以看出，在推薦過程中，考慮多個因素比單因素得到更好的推薦效果，隨著值的增大，推薦的準確率會有一定程度的下降。但本文的TSG算法在各種情況下都顯示出最佳的推薦性能。這也驗證了融合信任關系后，避免了惡意推薦，提高了推薦結果的準確性和可靠性。

圖5 推薦性能比較

如圖6所示，實驗對比了混合推薦算法中只考慮信任關系和同時考慮信任與不信任關系情況下的推薦結果質量。TSG代表在混合推薦算法中只融合信任關系，TSG-all代表信任和不信任關系同時考慮的推薦算法。

圖6 不信任關系在推薦中的影響

為了說明不信任關系能夠抵制惡意推薦，本文在真實數(shù)據(jù)集中注入了虛假簽到記錄。TSG算法僅考慮信任關系，TSG-all算法考慮了不信任關系。

從圖6可以看出，融合了不信任關系之后，TSG-all推薦算法的準確率和召回率都比只考慮信任關系的TSG算法有改善，這是因為虛假簽到的用戶是目標用戶不信任的，在形成推薦的過程中過濾了虛假用戶的推薦信息。這也證明了引入不信任關系對推薦質量的提高是有效的，能夠抑制惡意推薦。通過研究和合理利用不信任關系及其傳遞可以發(fā)現(xiàn)更多用戶間潛在的信息，以此來提升推薦的性能。

如圖7所示，實驗對比了本文提出的混合推薦算法與單因素的推薦算法的運行時間。從圖7可以看出，在2種數(shù)據(jù)集上，融合了信任關系的混合推薦算法的運行時間要稍高于考慮單因素的傳統(tǒng)推薦算法。這是因為混合推薦系統(tǒng)要分別計算基于用戶相似性、基于地理位置信息以及基于信任關系和不信任關系的簽到概率，然后進行線性組合獲得最終推薦結果，時間開銷分析詳見5.4節(jié)。但是3種推薦系統(tǒng)相對獨立，可以并發(fā)運行，因此時間開銷的增加不是非常大。

圖7 運行時間比較

7 結束語

本文通過對基于位置的社交網(wǎng)絡用戶的信任與不信任關系及其傳遞對興趣點推薦的影響研究發(fā)現(xiàn)，將用戶間的社交影響細化為信任關系，可以改善推薦的性能?；诖?，提出了一個融合用戶相似性、地理位置和信任關系的興趣點推薦框架。與基于用戶的協(xié)同推薦以及基于地理位置的推薦相比，混合推薦算法的推薦結果更準確，用戶的滿意度更好。

POI推薦可能由于敏感信息（如地理位置等的泄露）面臨隱私保護問題。未來將研究POI推薦中的隱私保護和推薦準確度之間的平衡問題。

[1] ZHENG Y. Location-based social networks: users[M]. Springer New York,2011: 243-276.

[2] 張富國. 基于社交網(wǎng)絡的個性化推薦技術[J]. 小型微型計算機系統(tǒng), 2014, 35(7): 1470-1476.

ZHANG F G. Survey of online social network based personalized recommendation [J].Journal of Chinese Computer Systems,2014, 35(7): 1470-1476.

[3] BHUIYAN T. A survey on the relationship between trust and interest similarity in online social networks[J]. Journal of Emerging Technologies in Web Intelligence, 2010,2(4):291-299．

[4] CHEN L J, GAO J. A trust-based recommendation method using network diffusion processes[J].arXiv:1803.08378. 2018:1-14.

[5] GUO G. Integrating trust and similarity to ameliorate the data sparsity and cold start for recommender systems[C]//ACM Conference on Recommender Systems. 2013: 451-454.

[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] YANG C, BAI L, ZHANG C, et al. Bridging collaborative filtering and semi-supervised learning: a neural approach for POI recommendation[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2017: 1245-1254.

[8] ZHANG D C, LI M, WANG C D. Point of interest recommendation with social and geographical influence[C]// IEEE International Conference on Big Data. 2017:1070-1075.

[9] LEE W P, MA C Y. Enhancing collaborative recommendation performance by combining user preference and trust-distrust propagation in social networks[M]. Elsevier Science Publishers BV, 2016.

[10] YE M, YIN P, LEE W C, et al. Exploiting geographical influence for collaborative point-of-interest recommendation[C]//International ACM Sigir Conference on Research & Development in Information Retrieval. 2011:325-334.

[11] LIU B, FU Y, YAO Z, et al. Learning geographical preferences for point-of-interest recommendation[C]//ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2013: 1043-1051.

[12] VICTOR P, VERBIEST N, CORNELIS C, et al. Enhancing the trust-based recommendation process with explicit distrust[J]. ACM Transactions on the Web, 2013, 7(2): 6.

[13] MA X, LU H, GAN Z. Implicit trust and distrust prediction for recommender systems[J]. 2015: 185-199.

[14] ZHOU T, LU L, ZHANG Y C. Predicting missing links via local information[J]. European Physical Journal B, 2009, 71(4): 623-630.

[15] SYMEONIDIS P, TIAKAS E, MANOLOPOULOS Y. Transitive node similarity for link prediction in social networks with positive and negative links[C]//ACM Conference on Recommender Systems. 2010: 183-190.

[16] TOBLER W R. A computer movie simulating urban growth in the detroit region[J]. Economic Geography, 1970, 46(s1): 234-240.

[17] MASSA P, AVESANI P. Trust metrics on controversial users[J]. International Journal on Semantic Web & Information Systems, 2009, 3(1): 39-64.

[18] CARTWRIGHT D, HARARY F. Structural balance: a generalization of heider’ s theory[J]. Psychological Review, 1956, 63(5): 277.

POI recommendation by incorporating trust-distrust relationship in LBSN

ZHU Jinghua, MING Qian

Department of Computer Science and Technology, Heilongjiang University, Harbin 150080, China

POI (point of interest) recommendation is an important personalized service in the LBSN (location-based social network) which has wide applications such as popular sights recommendation and travel routes planning. Most existing collaborative filter algorithms make recommendation according to user similarity and location similarity, they don’t consider the trust relationship between users. And trust relationship is helpful to improve recommendation accuracy, robustness and user satisfaction. Firstly, the propagation property of trust and distrust relationship was analyzed. Then, the measurement and computation method of trust were given. Finally, a hybrid recommendation system which combined user similarity, geographical location similarity and trust relationship was proposed. The experiments results show that the hybrid recommendation is obviously superior to the traditional collaborative filtering in terms of results accuracy and user satisfaction.

LBSN, POI recommendation, collaborative filtering, trust relationship

TP311

A

10.11959/j.issn.1000?436x.2018117

2017?11?08；

2018?05?18

朱敬華，zhujinghua@hlju.edu.cn

國家自然科學基金資助項目（No.61100048, No.61370222）；黑龍江省自然科學基金資助項目（No.F2016034）

The National Natural Science Foundation of China (No.61100048, No.61370222), The Natural Science Foundation of Heilongjiang Province (No.F2016034)

朱敬華（1976?），女，博士，黑龍江大學教授、碩士生導師，主要研究方向為社會網(wǎng)絡推薦、傳感器網(wǎng)絡、數(shù)據(jù)挖掘。

明騫（1991?），男，黑龍江大學碩士生，主要研究方向為基于位置社交網(wǎng)絡的個性化推薦。