基于社交信任和標簽偏好的景點推薦方法①

陳燁天,米傳民,肖 琳

(南京航空航天大學 經濟與管理學院,南京 211106)

隨著國民生活水平的提高和互聯網的快速發展,我國在線旅游發展迅猛,2016年中國在線旅游市場交易規模已達6026億,同比增長34%[1].人們可以在各種在線旅游平臺上挑選自己喜歡的旅游產品并制定相應的出行計劃.然而嚴重的信息過載問題,使得用戶很難便捷地從海量的檢索結果中獲取自己真正需要的旅游信息[2].此外,目前國內的在線旅游電商平臺提供的服務項目單一,旅游路線、景點介紹幾乎都是固定內容,推薦系統的搜索和推薦結果多以產品熱度排序,無法滿足用戶個性化的需求[3].尤其是在旅游景點的推薦上,景點熱度和時間因素會對用戶造成極大地干擾.用戶缺乏旅游經驗,面對過于廣泛和缺乏人性化的推薦信息,難以獲取較高的滿意度[4].

為解決上述問題,學者們針對個性化旅游推薦技術做了廣泛的研究,主要集中在基于社交媒體的推薦上[5–7].但區別于圖書、音樂等物品的推薦[8],由于旅游景點眾多,用戶購買頻次低,導致數據稀疏性極大,傳統的推薦方法難以解決冷啟動和“新城市”等問題[9].本文通過引入用戶信任關系來緩解數據稀疏性和冷啟動問題,根據用戶社交行為和影響力衡量顯性信任,利用上下文信息挖掘隱性信任,并通過信任傳遞計算用戶間接信任,構建完整的信任網絡.在信任推薦的基礎上,進一步融入用戶-標簽興趣信息,提出一種結合社交信任和地理標簽的STGT推薦算法(recommended algorithm combined with Social Trust and Geo-Tags ).實驗結果表明,本文提出的算法能在一定程度上提高推薦精度,同時緩解新用戶和新城市等問題.

1 相關工作

個性化旅游推薦系統通過挖掘用戶數據,獲得用戶的潛在需求和未來喜好,從而主動為用戶推薦滿足需求或感興趣的信息,不僅有效解決了信息過載問題,而且滿足了用戶的個性化需求[10].不同于其他個性化推薦,個性化旅游推薦面臨的挑戰更大[11]:(1)旅游數據更復雜;(2)用戶更難準確表達自己的需求;(3)大多數用戶的歷史旅游記錄和偏好信息都很少;(4)旅游數據更稀疏.傳統的推薦方法如協同過濾推薦等效果不佳,數據稀疏性、冷啟動問題嚴峻,還有新城市推薦問題[5].

為解決上述問題,學者們在傳統的推薦方法上做了不少改進.從獲取用戶個性化信息方式角度可分為兩類:(1)用戶交互方式.如 Ahas 等人[12]通過邀請用戶填寫問卷的方式獲取用戶偏好;麻風梅[13]以會話的方式在線獲取用戶偏好和需求,結合用戶瀏覽行為得到綜合興趣度進行推薦.這類基于知識、會話式的推薦方法不需要用戶歷史數據,故不存在冷啟動問題,對非注冊用戶也能做出個性化推薦,但數據稀疏性問題依舊無法解決.另一方面,這種方式無法得到大量用戶的數據,時間和操作成本高,能使用的用戶訓練樣本小,無法滿足日益龐大的數據量處理需求.(2)用戶產生的社交媒體數據.這些社交媒體數據包括簽到數據(check-in)[14],GPS 軌跡信息[15]、旅游博客[6]等.這類方法能獲得大量的用戶歷史數據和消費行為數據,覆蓋面廣,得到的結果更具有普適性.近年來,隨著互聯網技術的不斷提高,帶有地理信息的圖片數據越來越受到研究者的關注[7].以Flickr、Panoramio為代表的圖片分享網站的興起,為研究者提供了海量的用戶旅游照片.這些照片附帶地理位置、拍攝時間、標簽等重要信息,本身就體現了用戶的旅游興趣偏好,為個性化推薦帶了極大地便利[16].

隨著用戶個性化需求的不斷提高,學者們利用地理圖片社交媒體這一數據時,分析用戶偏好的方法主要分成兩類:(1)利用上下文信息分析用戶偏好,包括用戶年齡等個人信息、消費成本、天氣、時間和季節等時空信息[17].如Memon等人[18]綜合考慮用戶偏好和時間因素,根據用戶過去時間內在舊城市的旅游偏好推薦新城市的旅游產品.Yin等人[15]進一步區分了游客偏好和當地居民偏好,利用當地居民偏好緩解數據稀疏性和新城市問題.這些研究在傳統用戶相似性度量假設用戶未評分項為0的基礎上,通過添加附加約束條件緩解數據稀疏性問題,但沒有從根本上解決這個問題.因此有研究者提出在計算用戶相似性時,先用相似性度量方法計算未評分稀疏項和其他項目的直接相似性,增加共同評分項來緩解稀疏性.但這類研究集中在電影、音樂數據,在旅游景點推薦方面的效果有待檢驗.(2)利用標簽信息.之前的研究大多使用用戶評分數據,但相同的評分不能代表興趣真正相同.標簽信息可以進一步直觀地揭示用戶對景點本身的興趣點.如Lu等人[7]結合地理手冊從地理信息圖片中得到目的地后,引入目的地風格標簽,結果比只用流行游覽時間等上下文信息更精確.雖然這些研究通過標簽細化了用戶興趣偏好,但大多簡單地考慮了標簽-景點關系,進行景點預過濾篩選處理,忽視了標簽-標簽關系、用戶-標簽關系.

此外,部分學者還引入了社交信任關系來緩解傳統協同過濾算法的弊端,通過綜合信任度和相似度,提高推薦精度[19].如史一帆[20]提出的基于用戶社交關系和物品標簽的協同過濾推薦,把與目標用戶相似度大于0或信任度大于0的用戶當做相鄰用戶.但這些研究大多聚焦在圖書、音樂、電影等推薦領域,涉及旅游照片、游記等類型數據的旅游推薦研究極少.劉艷等人[3]通過用戶景點照片矩陣計算用戶偏好,結合好友親密信任關系計算相似度,但只是簡單判斷了好友間是否有關注關系,忽視了用戶交互行為和信任的傳遞問題.在現實推薦中,社交用戶間的直接信用值獲取也是一個難題.

因此,本文基于圖片數據,根據用戶社交行為、社交影響力和上下文信息獲取用戶直接信任和隱性信任關系,在考慮信任傳遞的基礎上挖掘用戶間接信任,最后綜合相似度和信任度得到推薦結果.為緩解用戶信任好友稀缺時推薦效果不佳的問題,引入用戶標簽偏好,提出一個混合社交信任和標簽興趣的STGT景點推薦算法.實驗結果表明,該算法能夠有效利用多維信息,提高推薦精度.

2 基于社交信任的景點推薦模型

2.1 構建信任網絡

利用圖片媒體數據挖掘用戶信任關系的關鍵是構建信任網絡:給定一個用戶-景點評分模型,如何表示用戶集合中用戶間的直接信任關系.直接信任指直接相連的用戶間的信任關系,可進一步分為顯性信任和隱性信任.

(1)顯性信任

顯性信任可通過用戶社交互動行為和社交影響力獲取.在本文中,當用戶i和用戶j存在好友關系,且用戶i對用戶j有點贊等互動行為,則認為兩個用戶間存在顯性信任關系,用trustie,xj表示,計算公式為:

其中,R=(r1,r2,···,rn),rj表示用戶i對用戶j發布的照片等狀態的點贊數;F=(f1,f2,···,fn),fj表示用戶j在社交網絡中的被關注數.α1取0.75,將較大權重分配給用戶社交互動行為.

(2)隱性信任

當兩個用戶為非好友時,即trustie,xj=0,但不代表他們是非信任關系,因此需要判斷計算他們之間是否有隱性信任關系.本文通過計算用戶共同游玩景點的上下文情景信息相似度,來推導用戶隱性信任,計算如下:

其中,simtime(i,j)表示用戶i和j的游玩時間相似度,L(i)表示用戶i游玩過的景點集合,L(j)表示用戶j游玩過的景點集合,k∈L(i)∩L(j)表示用戶i和j共同游玩過的景點,tik表示用戶i游玩景點k的時間,tjk表示用戶j游玩景點k的時間.

其中,simweather(i,j)表示用戶i和j的游玩天氣相似度,上下文天氣信息用CI=(Temperature,Condition)表示,包含氣溫Temperature={hot,warm,cold},天氣狀況Condition={rainy,sunny,cloudy}.

綜合前面的顯性信任和隱性信任關系,得到用戶直接信任值trustdi,ijr計算方式如下:

得到trustid,ijr就能構建信任網絡,過程如下:遍歷每個用戶和其他用戶間的直接信任值,與全局信任閾值tthreldall比較,若trustid,ijr大于tthreldall,說明用戶間直接相連,反之則說明沒有直接相連,由此檢查每個用戶的連接情況.網絡中的每個節點分別代表一個用戶,連接節點每條邊代表用戶間相互連接,邊上的權值代表直接信任度,邊的方向代表信任方向.

2.2 計算間接信任

信任具有傳遞性,即當用戶a信任b,用戶b信任c時,認為用戶a對c也存在著信任關系[21].因此僅僅考慮用戶直接信任值構建的信任網絡并不能完全反應用戶的信任關系,還需要考慮信任在網絡中傳播時的間接信任值.關于信任傳播比較經典的算法是TidalTrust[22]和 MoleTrust[23]算法.本研究借鑒TidalTrust算法思想,做出了改進.通過考慮隱性信任解決了用戶顯性信任難以獲取時無法進行信任度計算的問題,并引入信任最長傳播距離解決了TidalTrust算法中舍棄高信任值的長距離路徑問題.

首先需要為每個節點用戶設置一個路徑信任閾值,將目標用戶對所有鄰居用戶的信任值的平均值作為路徑信任閾值pthrelds:

其中,TF(s)表示用戶s的所有直接信任好友,trustds,irf表示用戶s對直接信任好友f的直接信任值.在信任傳遞過程中,這個路徑信任閾值將過濾所有信任值低于此閾值的路徑.

TidalTrust算法中取目標節點到源節點的最短路徑d作為信任最長傳播距離,這有可能舍棄路徑長但信任度高的路徑.因此,文獻[24]中信任傳播距離的研究:

其中,n表示信任網絡中的用戶總數,m表示網絡中用戶的鄰居用戶的平均數,即平均度數.本文在信任最長傳遞距離的選擇上取MD=max(L,d).如果用戶A不能到達用戶B,則B對A就沒有信任價值.但如果A能在最大傳遞距離內達到B,則意味著B對A來說具有一定的信任價值[25].

選擇完信任路徑和傳遞距離后,通過加權源節點與直接信任節點間的信任值,得到源節點對目標節點的間接信任值,公式如下:

其中,加權因子是通過比較直接信任節點到目標節點的最大路徑信任值確定的,如公式(9)所示.route(i,e)表示用戶i到用戶e的所有路徑集合,(x,y)∈r指路徑r上的任意兩個用戶x和y,表示單條路徑r上的兩個用戶間信任值的最小值.

綜合上述計算,信任網絡中任意兩個用戶間的傳遞距離在信任最長傳播距離內時,他們之間存在信任關系:當距離為 1 時,兩用戶直接相連,取直接信任值作為信任度;當距離大于1且不超過最長傳播距離時,取間接信任值作為用戶間信任度.當用戶間距離大于最長傳播距離時,信任度為0.

2.3 結合相似度和信任度的推薦策略

在傳統的協同過濾推薦算法中,目標用戶對目標項目的評分可以通過加權計算目標用戶的相鄰用戶打出的評分來進行預測.但隨著系統中用戶和項目數量的增加,數據稀疏性越來越高,以及新用戶和新項目帶來的冷啟動問題大大降低了傳統協同過濾算法的推薦精度[26].研究證實在推薦過程中引入信任關系能緩解上述協同過濾推薦算法中的主要問題,有效地提高推薦結果的準確度.Massa[23]提出的MoleTrust模型則采取通過信任關系過濾相鄰用戶,信任度替代用戶相似度的策略.經典的TidalTrust算法則利用信任關系過濾相鄰用戶,再通過信任權重加權評分的方式進行評分預測.

這些基于社交信任關系的推薦算法雖然提高了推薦結果的準確度,但推薦結果的覆蓋率卻比不上經典的協同過濾推薦計算方式.因此本文采用綜合協同過濾推薦和信任推薦的推薦策略:

其中,Ptrust(a,i)表示目標用戶a對景點i的預測評分,N+表示和目標用戶a相似度高的相鄰用戶集,ta,u表示用戶a和用戶u間的信任度,NT表示對目標項目i有過評分且信任度ta,u超過閾值的用戶集合,NT+=NT∩N+.ru,i表示用戶u對項目i的評分,是用戶u的項目平均評分,是用戶a的項目平均評分.sima,u表示用戶a和用戶u間的用戶相似度,通過Pearson相關系數計算得到.

當目標用戶和其他用戶之間有直接或間接的信任關系時,則使用信任度代替相似度作為加權計算的權重,通過優先考慮信任用戶的方式來保留信任推薦的優勢.另一方面,覆蓋率可以通過考慮無法獲取信任信息的那部分相似用戶保證.

3 考慮信任關系和標簽偏好的STGT景點推薦算法

雖然基于信任的推薦往往能獲得較高的滿意度和覆蓋率,但現實中信任關系一般比較稀疏,好友數量不足,導致推薦效果不理想.因此本文在考慮信任關系的基礎上,融入用戶偏好,通過計算用戶對標簽的偏好來分析用戶興趣,進一步挖掘了用戶的個性化需求.

3.1 基于標簽的用戶偏好建模

傳統的協同過濾通過用戶評分來表現用戶興趣偏好,受到數據稀疏性影響推薦結果不佳.標簽信息的引入可以很好地細分用戶興趣點,通過計算用戶對標簽的偏好度能很好地表示用戶的興趣點分布,緩解數據稀疏問題,同時在面對新用戶時也能通過獲取標簽偏好來緩解冷啟動問題.

(1)計算景點-標簽關聯度

首先我們定義用戶集合U={u1,u2,···,un},景點集合L={l1,l2,···,lm},標簽集合T={t1,t2,···,tk},Lu表示用戶u瀏覽過的景點集合,Tu表示用戶u使用過的標簽集.一個景點會被很多用戶標記標簽,在得到用戶的標簽偏好前需要在景點和標簽之間建立聯系,評價一個標簽在景點資源中的重要性.文獻[27]表明,sigmoid函數能最好地表示標簽的權重,用W(l,t)表示景點-標簽關聯度,即:

其中,tag_quality(l,t)可用TF算法算得,表示標簽t在景點l的標簽集中出現的比重.

(2)計算用戶-標簽關系

本文從用戶標簽行為和用戶評分行為兩方面衡量用戶標簽喜好度:一方面考慮了用戶標記標簽時間,另一方面當標簽在評分越高的景點出現,表示用戶對標簽的興趣越高.用tag_prefini表示用戶u對標簽t喜好度,計算如下:

timeperiod表示到用戶標記標簽的時間到現在的時間間隔,.

(3)計算標簽-標簽關系

當用戶標簽行為和評分較少時,標簽稀疏性較高,為解決這個問題,本文采取了拓展標簽的方法,為每個用戶的標簽集增加相關度高的相關標簽.首先計算標簽相關度:

其中,|user(t)∩user(t′)|表示同時使用過標簽t和t′的用戶數,N(t,t′)表示標簽集中同時含有標簽t和t′的景點數.按相關度對標簽排序,選取TopM個相關標簽作為相關標簽,得到新的用戶標簽集Tu′.

用戶對相關標簽的喜好度可通過加權相關標簽喜好度得到:

綜合tag_prefini和tag_prefex可得用戶的標簽喜好度.

3.2 綜合信任關系和用戶偏好的推薦策略

由于基于信任的推薦結果未充分考慮用戶興趣,本文通過對用戶標簽喜好度的分析進一步進行了用戶興趣建模.因此在最終的推薦策略上,本文選擇加權混合推薦的方式融合兩種推薦方法的優勢,通過加權因子λ將兩個預測結果線性組合,λ的取值由實驗結果確定.預測公式如下:

其中,Ptrust(a,i)指基于信任關系的推薦得到的預測評分,計算方法在公式(10)中已給出.Ptag(a,i)指基于標簽興趣的推薦得到的預測評分,計算公式如下:

其中,T(i)表示景點i包含的標簽集.最后根據P(a,i)對推薦景點列表進行降序排序,選取TopK個結果作為推薦結果.

4 實驗驗證和分析

4.1 實驗數據集

Flickr是一個提供免費及付費數位照片存儲、分享服務的圖片網站,重要特點就是基于社會網絡的人際關系的拓展與內容的組織.在當前的景點推薦領域中,很多推薦方法都會把Flickr數據集作為實驗數據集進行研究.本文的數據集就是選用Flickr公開的圖像數據集.城市的天氣信息通過第三方天氣服務網站的API爬取.對得到的數據集進行預處理,刪除那些元數據中的地點信息和實際經緯度不符以及帶有錯誤時間的照片.利用文獻[28]中的P-DBSCAN方法對照片的經緯度進行聚類得到景點,去除游歷景點數少于3個的用戶,去除包含圖片數少于10張的景點,最后的統計結果如表1所示.為檢驗算法在解決“新城市”問題上的效果,選擇至少去過四個城市中兩個城市的用戶,且其在訓練集中的游歷景點數不少于5個.實驗時隨機將數據集的80%作為訓練集,20%作為測試集.

表1 實驗數據集統計信息

4.2 評價指標

本研究采用的評價指標是推薦系統中常用的精確度(Precision)和平均絕對偏差(MAE).MAE用來衡量推薦算法的預測評分和實際評分之間的差異程度,用戶對景點的評分可通過用戶在景點拍攝的照片數量占比表示.MAE的值越小,代表推薦的準確度越高,推薦效果越好,定義如下:

其中預測用戶a對景點i的評分為pi,用戶對景點的實際評分是ri,n為測試集的景點數量.

精確度是Top-n推薦問題的重要衡量指標,用表示根據訓練集預測的推薦列表,T(u)表示用戶在測試集上的實際訪問景點列表,計算公式如下:

4.3 實驗結果分析

實驗一.確定加權因子λ

為了選擇最佳的加權參數使得混合推薦的效果達到最好,我們先固定推薦數量和用戶最近鄰數都為25進行實驗,通過改變 λ的取值觀察MAE指標的變化.λ從0.1取到0.9,依次遞增0.1.實驗結果如圖1所示.

從圖1中可看出,隨著加權因子 λ 的逐漸增大,MAE的值先逐漸減小再逐漸增大.當 λ 的取值為0.6 時,MAE的值達到最小,推薦質量達到最佳.因此我們在后面的實驗中取 λ=0.6,來確定用戶最近鄰數量和不同算法推薦效果的比較.

圖1 λ取值對實驗結果的影響

實驗二.和其他推薦算法的比較

為了驗證本文提出融合信任關系和用戶偏好的STGT推薦算法的準確性和推薦效果,將本文提出的算法和考慮標簽信息和社交關系的UKS算法[20]、基于信任和項目偏好的TIPCF算法[26]以及MFT-Co[29]信任推薦算法進行對比.固定推薦列表長度為15,拓展標簽的數量取20,通過改變最近鄰數量觀測MAE和Precision@15值的變化.實驗結果如圖2、圖3所示,橫坐標為最近鄰數目個數,縱坐標為MAE和Precision@15的值.

圖2 各算法MAE值對比

從圖2實驗結果中可看出,最近鄰數目確實是影響推薦質量的因素,隨著最近鄰數目的增大,各推薦算法的MAE值下降明顯,當數目達到30左右時MAE的值趨于穩定.說明近鄰用戶與目標用戶的相似度和信任度已經接近閾值,此時繼續增大最近鄰數目,增加的近鄰用戶已經不具備較好的推薦參考價值(相似度或信任度低于閾值),導致推薦效果趨于平緩.從整體上看,STGT算法的推薦效果明顯優于其他三種算法,而UKS的推薦質量比MFT-Co和TIPCF好.

從圖3實驗結果可知,本文提出的STGT算法在精確度上有明顯提高,比TIPCF、MFT-Co和UKS算法分別提高了14.01%、10.07%、6.62%.從增長趨勢看,隨著最近鄰數目的增長,精確度的提升趨勢放緩并趨于穩定,繼續加入相似度或信任度低的近鄰用戶無法再提高推薦精確度.

圖3 各算法 Precision@15 值對比

為驗證本文提出的算法在緩解冷啟動問題上的效果,隨機抽取 10 000 名用戶進行實驗,并隨機去除150個景點在訓練集中的用戶訪問信息,模仿冷啟動環境.從圖4的實驗結果可知,STGT算法對于系統中新項目的應對能力和推薦效果明顯優于其他三種算法,隨著最近鄰數目的增加,算法性能趨于穩定,有效地緩解了冷啟動問題.

圖4 冷啟動環境下各算法推薦效果對比

從以上分析可得出以下結論:(1)由于本文提出的STGT算法更準確地衡量了用戶間的信任關系,通過綜合考慮用戶評分行為和興趣品偏好挖掘出用戶隱性信任關系,緩解了數據稀疏性的同時獲得了更準確的近鄰用戶.(2)本文不僅考慮了其他算法使用的標簽-景點關系,還進一步考慮了標簽-標簽關系和用戶-標簽關系,將用戶對景點的興趣偏好分解成用戶對標簽的偏好,有效地解決了在新城市中無法獲取用戶興趣偏好的問題,提高了推薦準確性.(3)當新用戶或新項目進入系統時,通過利用用戶信任關系和標簽偏好,在一定程度上緩解了冷啟動問題.

5 結論與展望

現有的景點推薦算法在考慮用戶間關系時主要利用了社交網絡或好友關系獲取用戶間直接信任,忽視了用戶隱性信任和信任傳遞問題;而在考慮用戶和景點關系時主要從用戶評分和天氣、時間等上下文信息計算用戶相似性進行推薦,當用戶處于新城市時由于缺乏用戶歷史記錄無法做出準確推薦.針對這些問題,本文提出一種綜合信任關系和標簽偏好的景點推薦方法(STGT方法).首先結合用戶評分行為和上下文信息挖掘用戶隱性信任,構建信任網絡,融合相似度和信任度做出推薦.然后通過全面考慮用戶、景點和標簽之間的關系,把用戶的興趣偏好分解成對不同景點標簽的偏好,更準確地獲取了這些代表用戶長期興趣的偏好,有效地緩解了數據稀疏性,在新城市問題中能做出更準確的推薦.通過在Flickr網站上收集的數據,設計了對比實驗.實驗結果表明本文提出的算法有效地提高了推薦準確度,在一定程度上緩解了冷啟動和新城市問題.

未來的工作包括考慮用戶間信任的動態變化,以及用戶標簽存在的同義、多義問題,標簽本身存在的問題可能會影響推薦質量.此外,可以獲取其他類型的旅游信息,如游記等,進一步挖掘用戶興趣,提高用戶最近鄰搜索精度.