融合鄰居選擇策略和信任關系的興趣點推薦*

劉 輝，曾 斌,劉子愷

(1.重慶郵電大學通信與信息工程學院，重慶 400065;2.重慶郵電大學通信新技術應用研究中心，重慶 400065; 3.重慶信科設計有限公司，重慶 401121;4.重慶郵電大學計算機科學與技術學院，重慶 400065)

1 引言

近年來，隨著互聯網技術的不斷進步，人們通過智能終端獲取位置信息越來越方便和準確，促使基于位置的社交網絡LBSN(Location-Based Social Network)的推薦趨于火熱，如國外的Foursquare、Gowalla和Yelp挑戰賽等。LBSN與傳統網絡相比增加了地理位置信息，用戶可以對當前訪問的興趣點POI(Point-Of-Interest)進行簽到，且用戶可以與好友分享自己的簽到信息。在這個背景下，推薦系統成為了一種可選擇的挖掘方法，從LBSN到Twitter等傳統網絡越來越頻繁地使用位置推薦功能。

社交網絡出現后，越來越多的推薦算法利用社交網絡提供的豐富信息來改進傳統推薦算法的性能，特別是解決傳統協同過濾方法中的冷啟動問題。文獻[1]提出基于信任關系的推薦方法CoSRA+T(CoSRA Trust)，該方法是對基于用戶相似性的推薦方法CoSRA 的改進，將用戶的信任關系融入推薦系統中，能提高推薦的精度。文獻[2]提出基于用戶偏好和背景嵌入的深度神經網絡架構，學習用戶和興趣點相關的各種背景環境來預測用戶對候選興趣點的喜好程度。雖然現有的推薦方法結合了信任關系，但并沒有針對用戶社會地位進行有效的分類，因此在推薦系統中，針對不同的領域，考慮用戶在不同領域的社會地位可以更加準確地反映實際的推薦過程，從而有效地改進推薦算法的性能。

綜上所述，本文提出了一種融合用戶相似性、地理位置和信任關系UGT(User-Geography-Trust)的混合推薦算法，綜合考慮了多種情境因素。本文的貢獻主要為：(1)對用戶簽到信息添加時間權重，充分利用用戶的簽到信息，提升推薦精度；(2)提出了一種基于朋友的鄰居選擇策略，篩選出目標用戶的鄰居用戶，以此來提高對目標用戶的偏好預測精度；(3)分析了用戶的屬性，給出了社會地位和信任度的計算方法。將信任關系融合到推薦系統中，有助于提升推薦精度，避免不良用戶的惡意推薦。實驗結果表明，本文算法在推薦精度上相較傳統的基于用戶相似性的協同過濾算法有很大的提高，并且保證了推薦結果的可信度，能夠有效地抵御惡意推薦。

2 相關工作

本節主要介紹3類興趣點推薦算法，包括基于協同過濾的推薦、基于地理位置的推薦和基于信任關系的推薦。

(1) 基于協同過濾的推薦。協同過濾推薦算法是由Goldberg等人[3]在1992年提出的，該算法是利用用戶的歷史活動記錄(一般為用戶-簽到矩陣)來進行推薦，不需要分析用戶概要信息和興趣點描述信息，是目前應用最廣泛的推薦技術，可分為基于模型的推薦和基于記憶的推薦。Lee等人[4]認為用戶簽到受個人喜好、好友影響和興趣點遠近距離3個方面影響，綜合用戶偏好、好友和地理信息提出混合推薦算法，明顯提高了推薦結果的精度。隨著云計算時代的到來，朱夏等人[5]提出了一種適用于云計算分布式處理環境的基于協同過濾的個性化推薦機制RAC。Wu等人[6]使用馬爾科夫鏈的局部隨機游走算法，提出了一種融合時間、空間和社會關系的朋友推薦模型。上述方法均需要用到用戶的歷史活動記錄，由于用戶-興趣點簽到矩陣數據極度稀疏，導致協同過濾算法的推薦精度并不高。

(2) 基于地理位置的推薦。基于地理位置的推薦是利用用戶大量簽到位置軌跡數據和社交活動數據進行推薦，現有的大多數關于位置推薦的研究都基于協同過濾和用戶地理位置偏好兩者之間進行組合。Pham等人[7]考慮興趣點之間的空間影響，提出了一種外地區域推薦算法來衡量一個區域的吸引力。考慮到用戶簽到的空間影響，可以縮小搜索空間，提高推薦系統的性能。Lian等人[8]提出一種加權矩陣分解模型，利用用戶的活動區域向量和興趣點的影響區域向量來對模型中用戶和興趣點的潛在因素進行增廣；Kurashima等人[9]提出了一種基于地理主題模型的假設，即如果一個興趣點離用戶當前簽到的地點或其訪問的地點更近，那么用戶訪問該興趣點的可能性更大；為了模擬不同用戶的LBSN簽到的中心數量，Ye等人[10]利用簡單的線性組合，將基于鄰居的協同過濾與基于冪率的模型相結合，來實現用戶的地理位置建模。這些方法的缺點是都無法很好地處理用戶冷啟動問題。

(3)基于信任關系的推薦。基于信任關系的推薦是由Massa首次提出的，之后有很多基于信任關系的推薦算法問世，這些算法可大致分為2類：一類是基于隱性信任的算法，另一類是基于顯性信任的算法。Chen等人[11]認為用戶對項目的偏好會隨著時間的推移發生變化，提出了一種基于矩陣分解的TTSMF(Trust and Time Social Matrix Factorization)算法，將時間序列信息、用戶信任關系和分數矩陣相結合，推薦精度高于現有的協同過濾推薦，特別是當目標用戶的項目得分較低時，甚至是沒有得分時，該算法也能取得較好的推薦效果。Cho等人[12]提出了一種基于概率矩陣分解的SoReg算法，通過分解信任關系矩陣和評分矩陣，生成了低維的潛在用戶向量、特征向量和項目向量；然后利用這3個向量進行評分預測；最后結合用戶評分和用戶之間的信任關系來進行推薦。

總體來說，現有的研究工作對用戶的偏好捕獲考慮不夠充分，同時忽略了信任關系和簽到頻次及簽到時間對興趣點推薦的影響，導致算法推薦精度較低。因此，本文提出了一種融合用戶相似性、地理位置和信任關系的混合推薦算法，線性組合后得到推薦結果，能更好地提高推薦精度。

3 問題的描述

典型的LBSN包含了用戶集和興趣點集2種實體集合，如圖1所示。為了便于研究，令U=(u1,u2,…,un)表示用戶集，L=(l1,l2,…，lm)表示興趣點集，其中n和m分別表示用戶數和興趣點數。除了以上2種實體集合，用戶歷史簽到信息對興趣點推薦尤為重要，用戶的簽到記錄組成用戶-興趣點簽到頻次矩陣F=[fu,l]n×m，簽到頻次矩陣中的元素fu,l表示用戶u在興趣點l上的簽到頻次。相較于使用二值來表示用戶是否訪問一個興趣點，用戶的簽到頻次直觀地反映了用戶對興趣點的偏好程度，在一個興趣點簽到的次數越多，用戶可能更加偏好該興趣點。

Figure 1 Structure of LBSN圖1 LBSN結構

4 用戶偏好建模

4.1 簽到矩陣處理

考慮到用戶簽到數據的時效性，采用可控變量的指數函數作為歷史簽到時間權重。與用戶所有時間的簽到信息相比，最近的數據更能準確地反映當前用戶的簽到頻次，而時間間隔較近的簽到數據對于推薦貢獻更大。為降低時間復雜性，設置一個時間間隔閾值H，當用戶的簽到間隔大于或等于閾值H時，對簽到數據進行處理。則更新后的用戶簽到矩陣FT為：

(1)

其中,ftu,l為用戶u在興趣點l上簽到的頻次，|tnow-tu,l|表示用戶u對興趣點l簽到時間與當前時間的間隔。λ為訓練得出的權重。

4.2 基于用戶的協同過濾推薦

傳統構建推薦系統的方法有基于內容CB(Content-Based)的推薦方法和協同過濾CF(Collaborative Filtering)推薦方法。CB是指每個用戶在給定的一組環境下表現出來特定的行為，而這種行為在類似的環境下會重復出現；而CF是在特定的群體中，人們在相似的環境下表現也類似。在CB中，用戶的行為是通過用戶過去的行為來進行預測的；而在CF中，用戶的行為是通過其他志同道合的人的行為來預測的。本文采用的是基于用戶的協同過濾推薦。為了能在CF方法中獲得推薦，需要求出目標用戶在候選興趣點上簽到的概率。經典的基于用戶的協同過濾模型如式(2)所示：

(2)

為了在預測時正確區分鄰居的選擇和他們意見的權重，對式(2)進行了如下修正，則可得出用戶u在興趣點l上簽到的概率P(u,l)為：

(3)

(4)

首先要做的是篩選出目標用戶的鄰居集合；而鄰居的選擇需要確定其他用戶與目標用戶的相似度。該過程涉及到這個數據集中的所有用戶，因為任何與目標用戶相似的用戶都可能參與偏好評估，然而鄰居的選擇會受到LBSN中的幾個因素影響。

在此背景下，本文采用一種基于朋友的鄰居選擇策略，如圖2所示。在這個策略中，使用系統中用戶自己創建的社交網絡信息，可以對目標用戶的簽到頻次做出估計的鄰居僅限于與目標用戶有社交關系的用戶，這些關系可以是直接朋友關系和間接朋友關系；根據給定的策略選擇鄰居集后，再用式(3)評估目標用戶在候選興趣點上的簽到概率。該策略通過探索以目標用戶為中心的社交網絡，搜索k個用戶，預測目標用戶的偏好。

Figure 2 Neighbor selection strategy圖2 鄰居選擇策略

4.3 基于地理位置的推薦

一些研究人員利用LBSN的簽到數據作為理解人類移動模式的有用信息來源[12,13]，從中得出2個結論：(1)用戶與簽到地點之間的距離分布類似于一個Power-Law分布，即指定用戶已簽到的大多數位置彼此接近；(2)用戶傾向于去自己感興趣的地點簽到，例如他們的家或工作場所，即使有些地點可能會離家偏遠。且由拖布勒第一定律[14]可知，一切事物都與其他事物相關，但近距離的事物比遠距離的事物更相關，這表明距離相近的興趣點更可能具有相似的特征。本文采用樸素貝葉斯算法來計算地理位置在推薦中的影響。用戶ui簽到過的興趣點集合用Li表示,則該用戶在任意一對興趣點簽到的概率為：

(5)

其中，d(lm,ln)為2個興趣點之間的距離；lm,ln為Li中任意一對興趣點。則由貝葉斯算法可得用戶ui在候選興趣點lj簽到的概率為：

(6)

其中,lj為候選興趣點；li為簽到集合Li中任意興趣點；d(lj,li)為興趣點li到候選興趣點lj的距離。PT[d(lj,li)]為用戶在2個興趣點都簽到的概率，PT(ljLi)表示用戶同時在lj和li簽到的概率。

4.4 基于信任關系的推薦

為了將信任融入到興趣點推薦中，本文考慮了幾個不同角度的重要因素，包括用戶在社交網絡中的聲譽，即社會地位以及用戶與用戶之間的互動。

在社交網絡中用戶總傾向于選擇他們所相信的朋友們或是專家為其推薦的興趣點，且用戶之間的信任關系越強，其受到的影響越大；用有向圖G(U,E)表示社交網絡的信任關系圖，其中U表示社交網絡中的用戶節點集；E表示這些用戶之間關系的一組邊；每條邊被賦予一個值，表示用戶之間的信任度。如圖3所示，展示了用戶u1～u5之間的信任度；u1～u5表示5個用戶。社交網絡和信任網絡是不同的，社交網絡的好友關系是相互的，而信任網絡中的信任關系是單向的，即用戶u1信任u2，并不代表用戶u2也信任用戶u1；而這些用戶與用戶之間的鏈接，是由同一網絡中的其他用戶對某個特定用戶進行全面評估產生的。

Figure 3 Trust network圖3 信任網絡

根據社交網絡的交互行為，用戶的屬性反映了用戶的特征，本文將用戶的屬性分為3個，并對這些屬性進行分析。

(1)用戶活動力：其反映的是用戶是否發表過動態，社交網絡中的用戶活動力通常是通過用戶的交互來衡量的，其定義如下所示：

(7)

其中,Nr(ui)表示用戶ui更新動態的次數；t表示時間周期。

(2)用戶關注度：在社交網絡中，關注度高的用戶將獲得更多的關注和認同，這種良性現象將增強用戶與用戶之間的信任關系。根據這種現象，可以使用改進了的個人主頁的 PageRank 值來衡量用戶的關注度，其定義如下所示：

(8)

其中,C(ui)表示ui關注了的用戶；N表示所有用戶數；δ是調節因子；Act(ui)為用戶活動力。

(3)社會地位值：在社交網絡中，每個用戶的影響力不同，由式(8)可得用戶的關注度，對N個用戶按關注度進行排序，設用戶ui的排名為ri∈[1,N]，則用戶ui的社會地位值定義為：

(9)

由式(9)可知用戶排名第1時，其si=1；且隨著排名的下降，其社會地位值也隨之下降，即用戶的關注度越低，與之對應的社會地位值越低。

一般來說，在系統中如果一個用戶被很多用戶信任，那么這個用戶在信任關系網絡中的影響力應該大于那些只被少數用戶信任的用戶。這種觀點同樣能應用到對用戶偏好的影響上，即被很多用戶信任的用戶具有較大的影響力，其個人的意見及言論往往會影響其他人的選擇?；谠撍枷?，認為在信任關系網絡中被很多用戶信任的用戶在社交網絡中的影響也會更大。因而，可以利用式(10)對用戶之間的信任關系進行重構：

(10)

其中，Tuv表示用戶u對用戶v的信任度；Tu代表用戶u信任集合，|Tu|表示集合中元素的個數；Nk和Nv分別表示信任用戶k和用戶v的用戶個數。

綜上所述，在信賴其他用戶的情況下，用戶ui去候選興趣點lj簽到的概率為：

(11)

其中，Di表示用戶ui信任的用戶集合；Tuiuk表示用戶ui對用戶uk的信任度；ftkj表示用戶uk在興趣點lj上的簽到頻次。

5 混合推薦系統

5.1 混合框架

在第3節中詳細介紹了基于用戶的協同過濾、基于地理位置和基于信任關系3種推薦方法，這3種推薦方法雖然能夠為用戶推薦興趣點，但推薦效果并不是很好。人們更傾向于接納信賴的朋友的推薦，因此接著分析用戶的屬性和信任關系計算方法。在LBSN中，用戶根據其所信任朋友的簽到歷史考慮去一個新地點的可能性，更符合實際。因此，本文將用戶的用戶相似性、地理位置和信任關系這3種影響進行線性組合，確定用戶ui在候選興趣點lj上簽到的概率為:

0≤λ,α,β≤1;λ+α+β= 1

(12)

在該系統中對于偽造簽到頻次的惡意用戶，即使他們與目標用戶相似度很高，也不能對目標用戶的興趣點推薦產生決定性的影響。惡意用戶不管是通過直接朋友還是間接朋友關系都不能獲得目標用戶的足夠信任，最終也無法對目標用戶進行惡意推薦。

5.2 規范統一模型

本文將利用min-max標準化來處理原始數據，將基于用戶的推薦、基于地理位置的推薦和基于信任的推薦規范化如下：

(13)

其中,maxuser,maxgeo,maxtru分別表示P(u,i),P(lj/Li),P(ui,lj)的最大值；minuser,mingeo,mintru分別表示P(u,i),P(lj/Li),P(ui,lj)的最小值。

5.3 參數推導

對于參數的推導，本文采用的方法是梯度下降法，首先將式(12)進行多元線性回歸處理，則有：

f(x)=fc(x)=c1x1+c2x2+c3x3

(14)

其中，

f(x)=Puilj

(15)

損失函數為：

(16)

最后得出最優化參數為：

(17)

(18)

(19)

6 實驗結果及分析

6.1 實驗數據集和參數的選取

本文實驗使用了2個真實簽到數據集Foursquare和Gowalla。為了保證實驗的有效性，從中剔除了簽到次數少于10且好友人數少于5的用戶，剔除被簽到次數少于5 的興趣點。最終得到的Foursquare數據集包含3 067個用戶的180 544條簽到記錄，其中興趣點數量為27 564個。Gowalla數據集包含6 304個用戶的808 172條簽到數據，興趣點數量為53 827個。對Foursquare和Gowalla這2個數據集中的每位用戶隨機選取其80%的簽到數據作為訓練集，余下20%的簽到數據作為測試集。根據5.3節所敘述的參數推導方法,選取最優參數作為本文的實驗值。這些參數的值如表1所示。

Table 1 Experimental parameter value表1 實驗參數值

6.2 評價指標

本文采用2個在推薦算法中應用較為廣泛的評價指標：準確率precision@N和召回率recall@N。TOP-N代表最終的推薦數量，準確率表示算法推薦結果與用戶反饋的契合程度，能夠反映推薦的準確性。召回率則被用來評估算法的執行效率，體現的是用戶偏好的推薦對象能被推薦的概率，反映推薦的全面性。計算方法為：

(20)

(21)

其中，R(u)表示推薦算法在執行訓練集后得到的興趣點推薦列表，T(u)則表示用戶在測試集上的實際簽到過的興趣點列表。

6.3 對比實驗

為了驗證本文提出的融合用戶相似性、地理相似性和信任關系的混合興趣點推薦算法(UGT)的推薦效果，本文將其與以下幾種推薦算法進行實驗對比，各對比算法介紹如表2所示。

Table 2 Recommendation algorithms used in experiment表2 實驗中使用的推薦算法

(1)各算法在不同時間閾值H下的結果對比。

本實驗主要觀察各算法在不同時間閾值下的結果。圖4中橫軸H表示時間閾值，其大小決定了用戶簽到數據的貢獻度，進而影響推薦算法的推薦結果?？v軸precision@N和recall@N分別表示在不同時間閾值下各推薦算法對應的準確率和召回率，實驗中分別設置閾值范圍為0≤H≤5，單位為年，實驗結果如圖4所示。

Figure 4 Influence of check-in frequency in recommendation圖4 簽到頻次在推薦中的影響

通過實驗1結果可以看出，隨著時間閾值H的增加，各算法的準確率和召回率均有所下降，因為隨著時間閾值H的增加，用戶的興趣可能會發生變化，對應時間間隔越大的簽到信息對推薦結果的貢獻越大，而用戶最近的簽到數據更能反映用戶的偏好，因此控制好時間間隔對于推薦結果有著重要的意義。

(2)各算法在不同推薦數量下的結果對比。

本實驗主要觀察各算法在不同興趣點推薦數量(TOP-N)下的結果。圖5所示為在Foursquare數據集和Gowalla數據集上各算法的性能比較，圖5中的橫軸TOP-N代表了所推薦的興趣點個數，縱軸precision@N和recall@N分別代表在不同推薦興趣點數量時各推薦算法對應的準確率和召回率。實驗中分別設置N=5,10,15,20，算法中的其余參數均設為滿足算法性能最優化時的參數值。圖5給出了各類算法在不同興趣點推薦數量下準確率和召回率的比較結果。

Figure 5 Performance comparison of each algorithm under different recommended quantities圖5 各算法在不同推薦數量下的性能比較

從圖5中可以得出：

①隨著TOP-N值的增加，各類算法的準確率均有所下降，但召回率均有所提升，但本文提出的UGT算法在各種情況下都表現出了較好的推薦性能。

②UGT、ULR、PACE、USG與UBCF相比在性能上均有了較為明顯的提升，這說明考慮多個因素比單因素能得到更好的推薦效果，且UGT算法提升最為明顯。

③相比較ULR，本文的UGT算法推薦效果更優，表明融合信任關系可提高準確率和召回率，也避免了惡意推薦。

實驗結果表明，相對于另外4種推薦算法，無論是在準確率還是召回率上，本文UGT算法的性能明顯更好。

7 結束語

本文利用用戶在LBSN中的歷史簽到信息、興趣點的位置屬性和用戶信任關系，提出了一種混合興趣點推薦算法。對簽到信息添加時間權重，充分利用了用戶簽到信息；提出了一種基于朋友的鄰居選擇策略，篩選出目標用戶的鄰居用戶，以此來提高對目標用戶的偏好預測精度；分析了用戶的屬性，給出了社會地位和信任度的計算方法。將用戶信任關系融合到推薦系統中，可以有效地改善推薦系統的性能，使得推薦的準確率和召回率更高，用戶滿意度更好。下一步的研究工作是深入挖掘用戶行為的時空模式，以此來提高推薦性能。