宋曉宇，韋海燕，孫煥良，許鴻斐

?

基于簽到數(shù)據(jù)的群體局部分散式旅游路線搜索*

宋曉宇1+，韋海燕1，孫煥良1，許鴻斐2

1.沈陽建筑大學信息與控制工程學院，沈陽110168
2.東北大學信息科學與工程學院，沈陽110004

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(05)-0646-11

E-mail: fcst@vip.163.com http:

//www.ceaj.org Tel:

+86-10-89056056

* The National Natural Science Foundation of China under Grant Nos. 61070024, 61272179 (國家自然科學基金). Received 2015-07,Accepted 2015-09.

CNKI網(wǎng)絡優(yōu)先出版: 2015-10-09, http://www.cnki.net/kcms/detail/11.5602.TP.20151009.1556.008.htm l

SONG Xiaoyu, WEI Haiyan, SUN Huanliang, et al. Local distributed group travel route search based on check-in data. Journal of Frontiersof Com puter Scienceand Technology, 2016, 10(5): 635-645.

摘要：基于位置的社交網(wǎng)絡產(chǎn)生了大量反映用戶喜好及路線流行規(guī)律的數(shù)據(jù)，為旅游路線搜索提供了新的模式?，F(xiàn)有的群體旅游路線搜索通過將多個用戶的偏好進行聚合，之后利用個體推薦算法進行搜索?，F(xiàn)實生活中存在群體整體上瀏覽一條線路時，個體用戶可以根據(jù)需要選擇局部不同景點進行訪問的需求?；诖诵枨螅岢隽巳后w用戶局部分散式旅游路線搜索問題。該問題結(jié)合群體用戶的個人偏好，發(fā)現(xiàn)一條帶有局部分散POI（point of interest）的且群體收益最大的訪問路線。采用簽到數(shù)據(jù)，通過用戶在POI間的轉(zhuǎn)移情況生成POI轉(zhuǎn)移關(guān)系圖，在關(guān)系圖上進行路線搜索。為了提高搜索效率，根據(jù)POI的流行度與轉(zhuǎn)移關(guān)系設計了雙層轉(zhuǎn)移關(guān)系圖，對POI進行了概化，實現(xiàn)了分級查詢。設計了基于分支限界搜索策略的優(yōu)化算法，利用結(jié)點間的控制關(guān)系進行剪枝，進一步提高了算法的搜索效率。利用Gowalla和Foursquare社交網(wǎng)站真實的簽到數(shù)據(jù)集進行了充分實驗，對搜索出的路線收益及算法的運行效率進行了對比，驗證了所提出方法的有效性。

關(guān)鍵詞：路線搜索；群體推薦；簽到數(shù)據(jù)；基于位置的社交網(wǎng)絡

1 引言

基于位置的社交網(wǎng)絡（location-based social networks, LBSNs）的快速發(fā)展，越來越多的用戶在Foursquare[1]、Gowalla[2]等在線社交平臺上分享其位置信息，并對特定地點進行評論。通過對這些分享的數(shù)據(jù)進行分析，可以挖掘出用戶的個人偏好及流行地點（point of interest，POI）和路線，為人們的出行提供路線推薦和搜索服務[3]。

現(xiàn)有的路線推薦大多針對個體用戶需求，研究基于地點和路線流行程度的路線推薦[2,4-5]，結(jié)合用戶偏好的路線推薦與搜索[6-7]及考慮查詢的位置、時間及天氣的路線搜索等[8-9]。針對群體用戶的推薦，現(xiàn)有研究通常將群體用戶的偏好進行聚合，再采用個體路線推薦方法加以解決[10-12]。

現(xiàn)實生活中，當結(jié)伴出行的群體用戶偏好差異較大，難以找到一條滿足全部用戶偏好的同行路線時，希望找到一條整體同行局部分散式的最優(yōu)出行路線，即在POI之間轉(zhuǎn)移時結(jié)伴同行，在訪問具體POI時，個體用戶可以根據(jù)自己的偏好選擇該點周邊且使其收益最大的POI進行訪問。收益即用戶對POI的滿意度，通過路線中地點類別滿足用戶偏好程度來度量。

針對此需求，本文提出了群體用戶局部分散式旅游路線搜索。該路線搜索結(jié)合群體用戶的查詢位置、個體用戶偏好及用戶可以分散訪問的POI周邊區(qū)域范圍，為群體用戶搜索到一條帶有局部分散POI且群體收益最大的訪問路線。本文用局部分散度來限定用戶可以分散訪問POI周邊區(qū)域，其具體定義將在第3章給出。每個用戶的最優(yōu)出行路線，可能包含不同的POI，但均在最優(yōu)路線所包含的POI內(nèi)，達到了共同轉(zhuǎn)移、分散訪問的目的。

該路線搜索有效解決了群體偏好差異較大時，推薦路線中的公平性問題，避免了群體整體滿意度高，個體收益差異較大的情況，兼顧了群體與個體的收益，增強了群體用戶的旅游體驗效果，是對群體旅游路線推薦問題的有效補充。

考慮用戶全局同行局部分散的情況，在大量的POI中搜索一條最優(yōu)路線是本文的挑戰(zhàn)。直接方法是通過遍歷滿足群體用戶約束的所有可行路線，根據(jù)分散訪問區(qū)域大小以及個體用戶的偏好，最終確定使得群體收益最大的訪問路線。隨著POI個數(shù)與POI之間邊數(shù)的增加，可行路線數(shù)會呈指數(shù)增長，使得該方法伸縮性較差。

然而，現(xiàn)實生活中流行度較高的POI周圍通常伴有其他流行度較低的POI，這些POI往往不被包含在最優(yōu)推薦路線之中，對這些POI的計算，消耗了大量時間。本文提出了一種分層處理POI的方法（hierarchical processing POI，HPP），該方法將流行度較高的POI稱為SPOI，其他POI根據(jù)與SPOI的距離與轉(zhuǎn)移關(guān)系分配到SPOI中，之后構(gòu)建雙層轉(zhuǎn)移關(guān)系圖（doublehierarchy transfer graph，DTG），在上層轉(zhuǎn)移圖中查詢可行路線，局部分散的因素在下層中進行查詢。SPOI能夠保證群體具有較高收益，因此得到的近似最優(yōu)路線與最優(yōu)解之間收益相差較小。但該方法減少了對可行路線的判別，較大程度提高了搜索效率。并且設計了相應的分支限界搜索算法，利用結(jié)點之間存在的相互控制關(guān)系進行剪枝，剪掉得不到最優(yōu)解的子樹，進一步加速對最優(yōu)路線的求解。

在數(shù)據(jù)選擇方面，現(xiàn)有針對旅游路線搜索的研究主要基于3種數(shù)據(jù)：GPS軌跡數(shù)據(jù)[5,7]、帶地理位置標簽的照片數(shù)據(jù)[6,9]和簽到數(shù)據(jù)[2,8,12]。其中簽到數(shù)據(jù)包含用戶確切的空間位置信息。通過分析用戶的簽到記錄，可以得出用戶位置轉(zhuǎn)移信息、用戶的個人偏好以及連續(xù)訪問兩地的時間花費；分析某地的簽到記錄，可以得到該地區(qū)的流行地點以及地點的流行程度；簽到數(shù)據(jù)不僅包含了POI的空間信息，還包含了POI具有的類別特點?；谝陨咸攸c，簽到數(shù)據(jù)較適用于本文所提出的群體用戶分散式旅游路線搜索問題。本文將簽到數(shù)據(jù)映射為圖，簽到的POI生成圖的結(jié)點，兩個結(jié)點如果有相同用戶連續(xù)簽到則生成一條邊。

綜上所述，本文的主要貢獻如下：

（1）提出了一種新的路線搜索——群體用戶局部分散式旅游路線搜索，有效解決了群體旅游路線推薦中的個體偏好差異較大問題，并給出了該問題的形式化定義。

（2）提出了一種分層處理POI的方法HPP，減少了對無效POI的計算，并且設計了分支限界搜索方法，提高了搜索效率。

（3）運用Gowalla和Foursquare兩個社交網(wǎng)站真實的簽到數(shù)據(jù)集，對文中所提出算法進行了充分實驗研究，從路線收益及效率方面進行對比，驗證了算法在不同參數(shù)設置下的有效性。

本文組織結(jié)構(gòu)如下：第2章綜述相關(guān)研究工作；第3章定義群體用戶分散式旅游路線搜索問題；第4章給出解決問題的有效算法；第5章給出實驗結(jié)果及分析；第6章總結(jié)全文。

2 相關(guān)工作

近年來，針對旅游路線搜索開展了大量相關(guān)研究，根據(jù)推薦對象不同，分為針對個體用戶的路線搜索與推薦[5-7]以及針對群體用戶的路線搜索與推薦[10-12]。以下分別對兩個研究領(lǐng)域的現(xiàn)有工作進行詳述。

2.1個體用戶路線搜索與推薦

針對個體用戶的路線搜索與推薦的相關(guān)研究，根據(jù)所使用的數(shù)據(jù)不同，通常有以下3種：通過分析社交網(wǎng)站上用戶分享的旅游照片來推薦旅游路線[6,9,13]；通過GPS軌跡來挖掘流行的旅游地點和線路[5,7]；運用人們?nèi)粘Ｉ钪蟹窒淼暮灥接涗?，為用戶提供基于位置的路線搜索[2,8]。

文獻[13]充分利用照片數(shù)據(jù)中的Tags和Titles，在此基礎上得到了不同旅游主題類別的頻繁訪問模式。文獻[14]提出了KOR（keyword-aware optimal route search）問題，即在滿足用戶提出的關(guān)鍵字與消耗約束的基礎上搜索一條最流行的路線，運用了近似算法OSScaling、BucketBound以及貪心算法來解決此問題。文獻[15]中，基于GPS軌跡數(shù)據(jù)，運用Coherence Expanding算法構(gòu)建中間轉(zhuǎn)移網(wǎng)絡，運用Absorbing Markov Chain模型與Maximum Probability Product算法在轉(zhuǎn)移網(wǎng)絡中尋找概率最大的路徑。文獻[16]從連續(xù)的簽到地點構(gòu)成的路線中挖掘出頻繁的訪問模式，根據(jù)用戶需求推薦分數(shù)最高的訪問路線。

上述的旅游路線搜索與推薦研究主要針對個體用戶，根據(jù)個體用戶的偏好或查詢需求進行推薦。本文的研究對象為群體用戶，推薦的路線需要滿足群體用戶整體偏好，針對個體用戶的路線推薦方法難以解決該問題。

2.2群體用戶路線搜索與推薦

現(xiàn)有針對群體用戶進行旅游路線搜索與推薦的常用方法通常將群體用戶的偏好進行聚合，之后再采用個體路線推薦方法加以解決[10-12]。文獻[10]采用最小痛苦聚合偏好算法（Least M isery），將群體中成員偏好的最小值作為群體偏好，并通過交互反饋過程建立群體偏好模型，推薦的路線中不存在收益較低的用戶。文獻[11]采用平均數(shù)聚合偏好算法（Average）對群體用戶的偏好進行聚合，將群體內(nèi)每名用戶的偏好取平均數(shù)作為群體整體的偏好，目標是能夠最大化群體整體收益。在此基礎上，文獻[12]提出了動態(tài)聚合偏好算法（dynam ic aggregation preference），根據(jù)當前個體用戶不同收益狀態(tài)，動態(tài)調(diào)整用戶偏好的優(yōu)先級，使路線中后續(xù)的地點選擇更偏向于當前滿意度低的用戶，推薦的路線個體收益差異較小。

雖然上述針對群體用戶的旅游路線搜索與推薦方法對于傳統(tǒng)的群體旅游路線搜索均能取得良好的結(jié)果，但推薦結(jié)果均為一條由若干POI組成的路線，不能解決群體用戶整體上瀏覽一條路線時在局部選擇景點的需求。

與上述工作相比，本文提出了群體用戶局部分散式旅游路線搜索，為群體用戶搜索到一條帶有局部分散POI的且群體收益最大的訪問路線，群體中每個用戶可以訪問不同的POI?，F(xiàn)有方法均不適于解決該問題。

3 問題定義

其中，CheckinNum(vi)代表vi的簽到次數(shù)；argc∈Cmax(CheckinNum(vj):vj.c=vi.c)代表與vi同類的POI中最大的簽到次數(shù)。

本文采用基于位置服務的在線網(wǎng)站Foursquare的位置分類方法，描述POI具有的類別。通常分為8類，記為：

A={arts_entertainment(c1),shops(c2),food(c3), nightlife(c4),travel(c5),education(c6), parks_outdoors(c7),building(c8)}

有向邊(vi,vj)代表兩個POI之間的一條可行路線，邊的數(shù)目為|E|，邊上的權(quán)值代表兩個POI之間的歐式空間距離，用d(vi,vj)表示。一條POI訪問路線可表示為R=(v0,v1,…,vn)。任一結(jié)點v∈V的鄰接點的集合為nb(v)={u|(v,u)∈E}，表示與該POI存在可行路線的其他POI。結(jié)點v的出度數(shù)為d(v)=|nb(v)|。

定義1（個體偏好向量）個體偏好向量是用戶u對不同類型地點的喜愛程度，表示為PV(u)=，其中p(u,ci)代表用戶u對地點類型ci的偏好程度。本文采用文獻[7]提出的方法對用戶偏好進行學習。

定義2（局部分散度）局部分散度用來限定用戶可以分散訪問POI周邊的區(qū)域，表示為α。與POI的空間距離小于α且滿足轉(zhuǎn)移關(guān)系的其他POI屬于可分散訪問的地點。例如圖1中，若當前訪問點為v5，α為1.6，則在該點能夠分散訪問的其他POI為v4、v8。

定義3（局部分散式路線）一條局部分散路線表示為RLD={v1(v1-1,v1-2,…,v1-j),v2(v2-1,v2-2,…,v2-k),…,vn(vn-1, vn-2,…,vn-m)}，其中(v1-1,v1-2,…,v1-j)為v1根據(jù)局部分散度求出的可分散訪問POI。

定義4（個體收益）個體收益代表單個用戶對一條旅游路線的滿意程度。計算方法如式（2）所示：

其中，M代表R中地點個數(shù)。例如圖1所示，PV(u1)代表用戶u1對c1、c2、c3這3類地點的偏好向量，若一條路線R=(v5,v1),則得出用戶u1在旅游路線R中的收益為Profit(u1)=0.10+0.03=0.13。

定義5（群體收益）群體收益代表群體U對局部分散路線的滿意程度，是每名用戶在各自最優(yōu)出行路線中的收益總和，表示為Profit(U)，計算方法如式（3）所示：

其中，|U|表示群體用戶的數(shù)量。

Fig.1 An example of searching圖1 一個搜索例子

定義6（群體用戶局部分散式旅游路線查詢）Q= ，s代表查詢點，n是用戶設定的訪問地點個數(shù)，α為局部分散度。

問題1（群體用戶局部分散式旅游路線搜索）依據(jù)圖G，結(jié)合Q=，以及群體用戶偏好PV，為群體U找到一條帶有局部分散POI的且群體收益最大的訪問路線，記為：

RLD-max=arg max(Profit(U))

RLD-max.q表示最大收益值；RLD-max-ui表示每名用戶的最優(yōu)出行路線。例如圖1中，群體用戶u1、u2發(fā)出查詢Q=，通過計算得到RLD-max={v5(v4),v2,v10(v11)}，RLD-max.q=1.15，RLD-max-u1=(v4,v2,v11)，RLD-max-u2=(v5,v2,v10)。

4 搜索方法

下面研究路線搜索算法。4.1節(jié)介紹處理該問題的基本算法，4.2節(jié)介紹HPP處理方法和DTG的構(gòu)建，4.3節(jié)介紹基于分支限界搜索策略的優(yōu)化算法。

4.1基本算法BSL

一個基本的解決群體局部分散式旅游路線搜索問題的方法為：在圖G中，根據(jù)給定起點，采用深度優(yōu)先搜索策略，找到所有滿足地點數(shù)目約束的可行路線，根據(jù)用戶的個人偏好以及局部分散度確定每條路線的收益值，最終將收益最大的局部分散式路線返回給群體。同時為每名用戶返回最優(yōu)出行路線。

算法1描述了基本算法BSL的細節(jié)。步驟5中，當路線長度m'=m時，計算路線的收益，否則將該結(jié)點放入棧U中，遞歸調(diào)用BSL，直到遍歷完nb(vs)為止。最終輸出最大收益可行路線RLD-max、最大收益RLD-max.q以及每名用戶最大收益路線RLD-max-ui。步驟11中，根據(jù)式（3）計算群體在當前路線中的收益。步驟12～15中，如果當前群體收益大于已有最優(yōu)收益，對當前群體及個體最優(yōu)路線進行更新。

算法1 BSL(G,Q)

輸入：G,Q=，每名用戶的偏好向量PV。

輸出：Umax中存儲的最大收益路線RLD-max及qmax中存儲的最大收益值RLD-max.q;umax[|U|]中存儲的每名用戶各自最優(yōu)路線RLD-max-ui。

1.初始化棧U,Umax,棧數(shù)組u[|U|],umax[|U|];

2.當前可行路線長度m'=0,qmax=0;

3. For nb(vs)中的每一個結(jié)點vjdo

4. m'=m'+1;

5. If m'=m

6. For U中所有結(jié)點vido

7.For群體中所有用戶uido

8.根據(jù)式（2），找出vi分散區(qū)域內(nèi)個體收益最大的結(jié)點vk;

9.Profit(ui)=vk.c×p(ui,c);

10.u[ui].push(vk);

11.Profit(U)=Profit(U)+Profit(ui); //根據(jù)式（3）計算群體收益

12.If Profit(U)>qmax

13.qmax=Profit(U);

14.Umax=U;

15.umax=u;

16. Else

17. U.push(vj);

18. BSL(G,Q=)

例如在圖1中，群體用戶u1、u2發(fā)出查詢?yōu)镼=。存在6條可行路線：R1=(v5,v9,v3)，R2=(v5,v9, v10)，R3=(v5,v2,v10)，R4=(v5,v2,v7)，R5=(v5,v2,v6)，R6=(v5,v1, v2)。根據(jù)Q可知，α=1.9，群體在v5可局部分散訪問的POI有v4和v8，在v2可局部分散訪問的POI有v7和v6，在v10可局部分散訪問的POI有v11。群體用戶根據(jù)個人偏好選擇其收益最高的POI進行訪問。經(jīng)過計算，最終為群體返回的最優(yōu)路線為RLD-max={v5(v4),v2,v10(v11)}，RLD-max.q=1.15，RLD-max-u1=(v4,v2,v11)，RLD-max-u2=(v5,v2,v10)。

4.2 HPP方法和DTG關(guān)系圖的構(gòu)建

為解決基本算法的不足，本文提出了一種分層處理POI的方法HPP，通過該方法構(gòu)建雙層轉(zhuǎn)移關(guān)系圖DTG，減少候選路線的數(shù)量，實現(xiàn)了分級查詢，有效提高了查詢效率。

如圖2（a）所示，HPP方法首先從原始POI中選取流行度大于閾值β的POI，將其稱作SPOI點。本文通過基于密度的聚類方法DBSCAN（density-based spatial clustering of applications w ith noise），對原始POI在空間進行聚類，將所有聚簇中最大流行度的平均值作為流行度閾值β。然后依據(jù)轉(zhuǎn)移關(guān)系與局部分散度獲取其附屬POI。圖2（b）中，SPOI依據(jù)其原始POI的轉(zhuǎn)移關(guān)系構(gòu)建上層關(guān)系轉(zhuǎn)移圖，其附屬POI依據(jù)轉(zhuǎn)移與距離關(guān)系形成下層關(guān)系轉(zhuǎn)移圖。在上層轉(zhuǎn)移關(guān)系圖中查詢到可行路線，局部分散的影響在下層轉(zhuǎn)移關(guān)系圖中進行查詢。

圖3依據(jù)圖1中原始POI，設定流行度閾值為0.4，通過HPP處理，形成的DTG。圖3（a）中，v5、v2、v9和v10構(gòu)成上層轉(zhuǎn)移關(guān)系圖。圖3（b）下層轉(zhuǎn)移關(guān)系圖中，v5包含的分散地點有v8、v4、v1；v2包含的分散地點有v6、v7；v9包含的分散地點有v3；v10包含的分散地點有v11。 4.3基于分支限界搜索策略的近似優(yōu)化算法DTG-BB

基于DTG，本文采用分支限界搜索策略獲取最優(yōu)路線，提出了DTG-BB搜索算法。該算法的基本思想是：在搜索過程中，從起點vs和空優(yōu)先隊列開始，vs被擴展后，其兒子結(jié)點被依次插入堆中，之后算法從堆中取出具有最大當前收益的結(jié)點作為當前擴展結(jié)點，并依次檢查與當前擴展結(jié)點相鄰的所有結(jié)點。該過程一直持續(xù)到優(yōu)先隊列為空時為止。

在搜索過程中，利用結(jié)點間的控制關(guān)系進行剪枝。在一般情況下，如果解空間樹中以結(jié)點vi為根的子樹中所含的解優(yōu)于以結(jié)點vj為根的子樹中所含的解，則結(jié)點vi控制了結(jié)點vj，以被控制的結(jié)點vj為根的子樹可以減去。圖4為圖3（a）的解空間樹，從起點v5出發(fā)，經(jīng)過結(jié)點v2和經(jīng)過結(jié)點v9的兩條路徑到達圖3中的同一結(jié)點v10。如圖4，在該問題的解空間樹中，這兩條路徑對應于解空間樹中兩個不同的結(jié)點4和5。如果結(jié)點4所對應的收益大于結(jié)點5所對應的收益，此時以結(jié)點4為根的子樹中所包含的從v5到終點的路線收益大于以結(jié)點5為根的子樹中所包含的收益。這時，結(jié)點4控制了結(jié)點5。因此，可以將以5為根的子樹剪去。優(yōu)先隊列分支限界法的具體執(zhí)行過程如算法2所示。

Fig.2 HPP and DTG圖2 HPP方法和DTG關(guān)系圖

Fig.3 DTG of Fig.1圖3 依據(jù)圖1構(gòu)建的DTG

算法2 DTG-BB(G′,Q)

輸入：G′，Q=，每名用戶的偏好向量PV。

輸出：Umax中存儲的最大收益路線RLD-max及qmax中存儲的最大收益值RLD-max.q;umax[|U|]中存儲的每名用戶各自最優(yōu)路線RLD-max-ui。

1.初始化最大堆H，數(shù)組p，棧U，Umax，棧數(shù)組u[|U|]，umax[|U|]，定義H中元素E和N

2.當前可行路線長度m′=0，qmax=0;E.v=vs，E.profit=p[vs]

3. H.push(E);

4. While H!=NULL //搜索解空間

5. H.pop(E);

6. For nb(E.v)中的每一個結(jié)點vjdo

7. If E.profit +群體在vj的收益>p[vj] //滿足控制約束

8.p[vj]=E.profit +群體在vj的收益

9.U.push(vj);

10.N.v=vj//加入活結(jié)點隊列

11.N.profit=p[vj]

12.H.push(N)

13. If m′=m

14.For U中所有結(jié)點vido

15.For群體中所有用戶uido

16.根據(jù)式（2），找出vi分散區(qū)域內(nèi)個體收益最大的結(jié)點vk；

17.Profit(ui)=vk.c×p(ui,c);

18.u[ui].push(vk);

19.Profit(U)=Profit(U)+Profit(ui); //根據(jù)式（3）計算群體收益

20.If Profit(U)>qmax

21.qmax=Profit(U);

22.Umax=U;

23.umax=u;

算法中，H為最大堆，表示活結(jié)點優(yōu)先隊列，堆中元素類型包含屬性v，用于記錄該活結(jié)點所表示的雙層轉(zhuǎn)移關(guān)系圖G′中相對應的結(jié)點編號；屬性profit表示從起始點到v所記錄的結(jié)點的收益值。用數(shù)組p記錄從起始點到各結(jié)點的收益。步驟1中，將起點作為初始擴展結(jié)點。步驟4中，while循環(huán)體完成對解空間內(nèi)部結(jié)點的擴展，一直持續(xù)到活結(jié)點優(yōu)先隊列為空時為止。步驟6中，依次檢查與當前擴展結(jié)點相鄰的所有頂點。步驟7中，利用結(jié)點間的控制關(guān)系進行剪枝，如果該結(jié)點滿足控制約束，則將該結(jié)點作為活結(jié)點插入到優(yōu)先隊列中。

例如圖3中，群體用戶u1、u2發(fā)出查詢?yōu)镼=。在圖1基礎上，當流行度閾值為0.4時構(gòu)建DTG，圖3（a）中有兩條可行路線：R1=(v5,v9,v10)，R2=(v5, v2,v10)。與基本算法相同，α=1.9。此時，從v5開始擴展，p[v5]=0.4；E.profit=0.4；結(jié)點v5被擴展后，將其鄰接點加入優(yōu)先隊列，由于p[v2]=0.8高于p[v9]=0.72，算法先擴展v2，此時可以得到Profit(U)=1.15。同樣，擴展v9可得到Profit(U)=1.0。最終得到與基本算法相同的旅游路線，RLD-max={v5(v4),v2,v10(v11)}，qmax=1.15，RLD-max-u1= (v4,v2,v11)，RLD-max-u2=(v5,v2,v10)。假設地點個數(shù)大于2，并且經(jīng)過v10的路線滿足地點個數(shù)要求，當算法擴展到v9時，由于p[v9]+0.32

該優(yōu)化算法基于DTG，減少了對無效POI的計算，并且運用剪枝操作，剪掉了不能生成最優(yōu)解的子樹，進一步提高了搜索效率。

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

實驗首先對比所提出的兩種搜索算法與常用的偏好聚合算法，在為群體推薦路線時，群體用戶的整體收益和個體收益差異性。然后對BSL算法和DTG-BB算法在搜索效率上進行對比。

Fig.4 A solution space tree of Fig.3（a）圖4 圖3（a）的解空間樹

實驗對比3種常用的偏好聚合算法：平均數(shù)聚合偏好算法（Average）中，群體對某類地點的偏好為群體內(nèi)用戶對該類地點偏好的平均數(shù)；乘法聚合偏好算法（Multiply）中，群體的偏好為群體內(nèi)用戶對該類地點偏好的累乘；最小痛苦聚合偏好算法（Least M isery）中，群體的偏好為群體內(nèi)用戶對該類地點偏好的最小值。因為無痛苦聚合偏好算法有很大幾率無法得到解，所以實驗不采用此算法。

5.1實驗數(shù)據(jù)

本文實驗采用Gowalla和Foursquare社交網(wǎng)站真實的簽到數(shù)據(jù)集。實驗選取Gowalla數(shù)據(jù)集中美國舊金山市北部從2009年3月到2010年10月的64 358條簽到記錄，過濾掉簽到次數(shù)低于3次的簽到地點，得到5 706個地點，如果一天中兩個地點間有相同的用戶連續(xù)簽到，并且平均時間間隔大于1小時小于5小時，兩點間生成一條有向邊。本文利用Foursquare簽到數(shù)據(jù)集中對地點類別的描述以及文獻[9]中計算地點流行程度的方法，來確定每個地點的類別和流行度。在用戶的個人偏好學習中，采用Foursquare的tips數(shù)據(jù)集，該數(shù)據(jù)集由文獻[7]獲得，實驗隨機選取美國紐約市tips數(shù)目大于30次的50名用戶，一共有1 606條tips記錄。

5.2實驗設置

實驗分為兩組：第一組實驗中，路線包含的地點數(shù)目M=5，群體內(nèi)用戶數(shù)目N由2變化到6，研究群體內(nèi)用戶數(shù)目的變化對算法效果以及搜索效率的影響。N取不同數(shù)值時，進行500次實驗，每次實驗隨機選取一個起始點，在50名用戶中隨機選取相應數(shù)目的用戶，求得500次實驗各項度量值的平均數(shù)。第二組實驗中，群體內(nèi)用戶數(shù)目N=5，路線包含的地點數(shù)目M從2變化到6，研究地點數(shù)目的變化對算法效果以及搜索效率的影響。M取不同數(shù)值時，分別進行500次實驗，每次實驗隨機選取一個起始點，在50名用戶中隨機選取5名用戶，求得500次實驗各項度量值的平均數(shù)。

5.3效果對比實驗

本節(jié)通過群體用戶整體的收益和個體收益差異性來評價BSL算法、DTG-BB算法、Average算法、Multiply算法和Least M isery算法的有效性。

5.3.1群體整體收益對比

圖5（a）顯示了Profit(U)隨群體中用戶數(shù)目的變化情況。隨著群體內(nèi)用戶數(shù)目N的增加，每種算法的Profit(U)值增加，表明N增大，群體收益提高。其中，Multiply和Least M isery算法的效果較差，Average、BSL和DTG-BB算法的效果均較好，其中BSL比Average算法增多了約43%，DTG-BB比Average算法增多了約40%。圖5（b）顯示了Profit(U)隨路線中地點個數(shù)M變化的趨勢。隨著M的增加，每種算法的Profit(U)值增加，表明M增加，群體整體收益提高。與圖5（a）類似，Multiply和Least M isery算法表現(xiàn)出較差的效果，Average、BSL和DTG-BB算法的效果均較好，其中BSL和DTG-BB算法效果最好，分別比Average算法增多了約46%和45%。綜上可知，兩種局部分散式算法BSL和DTG-BB均能為群體帶來較高的整體收益。

5.3.2個體收益差異性對比

Fig.5 Variation trend of Profit(U)圖5 Profit(U)的變化趨勢

個體收益差異性是對路線公平性的評價。本文采用均方根誤差RMSE(U)表示個體收益差異性，計算方法如式（4）所示。Profit(u)′為個體u在群體最優(yōu)路線中的平均每個地點的收益，Profit(u)″表示僅根據(jù)用戶u的個人偏好，得到的個人最優(yōu)路線中平均每個地點的收益，N表示群體人數(shù)。實驗比較個體在群體最優(yōu)路線中與個人最優(yōu)路線中收益的RMSE(U)值。RMSE(U)值越小，代表用戶在群體最優(yōu)路線中的收益與個人最優(yōu)路線中的收益差異越小，表示個體收益差異性越小，推薦的路線越公平。

圖6（a）顯示了RMSE(U)隨著群體內(nèi)用戶數(shù)目N的變化情況，N越大，RMSE(U)越大，代表群體內(nèi)用戶收益差異越低，其中Average算法效果要優(yōu)于Multiply和Least M isery算法，而BSL和DTG-BB算法則比Average算法分別降低了約37%和34%。圖6（b）顯示了RMSE(U)隨路線中地點數(shù)目M的變化情況，隨著M的增加，RMSE(U)值逐漸增高，與圖6（a）類似，其中BSL和DTG-BB算法比Average算法分別降低了約36%和34%。綜上可知，兩種局部分散式算法BSL和DTG-BB，使群體對局部提供的景點進行訪問，均能使個體收益差異較小，推薦的路線較公平。

5.4效率對比實驗

Fig.6 Variation trend of RMSE(U)圖6 RMSE(U)的變化趨勢

Fig.7 Variation trend of efficiency圖7 效率的變化趨勢

圖7（a）顯示了算法訪問結(jié)點數(shù)隨著群體內(nèi)用戶數(shù)目N的變化情況，N越大，算法訪問的結(jié)點數(shù)越多，其中DTG-BB算法比BSL算法的訪問結(jié)點數(shù)減少了約65%。圖7（b）中顯示了算法的運行時間，與圖7 （a）中訪問結(jié)點數(shù)的趨勢基本一致。圖7（c）中顯示了算法訪問結(jié)點數(shù)隨著路線中地點數(shù)目M的變化情況，隨著M增加，算法訪問的結(jié)點數(shù)呈指數(shù)次冪增長。圖7（d）中顯示了算法的運行時間，與圖7（c）中訪問結(jié)點數(shù)的趨勢基本相同，與4.1節(jié)中的分析一致。綜合可知：DTG-BB算法在各種參數(shù)設置下運行效率均高于BSL算法，DTG-BB算法具有較高的運行效率。

6 結(jié)束語

本文提出了一種新的路線搜索方法——群體用戶局部分散式旅游路線搜索。該路線搜索方法可為群體用戶搜索一條帶有局部分散POI的且群體收益最大的訪問路線。為了解決可行路線數(shù)目過多的問題，本文提出了一種分層處理POI的方法HPP，通過HPP構(gòu)建DTG。本文方法減少了對可行路線的判別，實現(xiàn)了分級查詢，從而提高了搜索最優(yōu)路線的效率。實驗用真實的數(shù)據(jù)集進行路線收益和搜索效率對比，驗證了本文方法的有效性。實驗表明，局部分散式策略能使群體用戶獲得較高整體收益，個體收益差異性較小，同時所提出的近似優(yōu)化算法具有較好的收益效果與較高的搜索效率。

References:

[1] Gao Huiji, Liu Huan. Data analysis on location based social networks[M]. New York, USA: Springer, 2014: 165-194.

[2] M cKenzie G, Adams B, Janow icz K. A thematic approach to user similarity built on geosocial check-ins[M]//Geographic Information Science at the Heart of Europe. Basel, Sw itzerland: Springer International Publishing, 2013: 39-53.

[3] Bao Jie, Zheng Yu, Wilkie D, et al. A survey on recommendations in location-based social networks[J]. GeoInformatica, 2014, 19(3): 525-565.

[4] Hsieh H P, Li Chengte. Composing traveling paths from location- based services[C]//Proceedings of the 6th AAAI International Conference on Weblogs and Social Media, Dublin, Ireland, Jun 4-7, 2012. Menlo Park, USA: AAAI, 2012: 618-619.

[5] Yoon H, Zheng Yu, Xie Xing, et al. Social itinerary recommendation from user- generated digital trails[J]. Personal and Ubiquitous Computing, 2012, 16(5): 469-484.

[6] Cheng A J, Chen Y Y, Huang Y T, et al. Personalized travel recommendation by mining people attributes from communitycontributed photos[C]//Proceedings of the 19th ACM International Conference on Multimedia, Scottsdale, USA, Nov 28-Dec 1, 2011. New York, USA:ACM, 2011: 83-92.

[7] Bao Jie, Zheng Yu, Mokbel M F. Location-based and preference-aware recommendation using sparse geo-social networking data[C]//Proceedings of the 20th International Conference on Advances in Geographic Information Systems, Redondo Beach, USA, Nov 6-9, 2012. New York, USA: ACM, 2012: 199-208.

[8] Hsieh H P, Li Chengte, Lin Shoude. Exploiting large-scale check-in data to recommend time-sensitive routes[C]//Proceedings of the 2012 ACM SIGKDD International Workshop on Urban Computing, Beijing, China, Aug 12, 2012. New York, USA:ACM, 2012: 55-62.

[9] Majid A, Chen Ling, M irza H T, et al. M ining contextaware significant travel sequences from geo-tagged social media[C]//Proceedings of the 26th AAAI Conference on Artificial Intelligence, Toronto, Canada, Jul 22-26, 2012. Menlo Park, USA:AAAI, 2012: 2443-2444.

[10] Garcia I, Pajares S, Sebastia L, et al. Preference elicitation techniques for group recommender systems[J]. Information Sciences, 2012, 189: 155-175.

[11] Masthoff J. Group recommender systems: combining individual models[M]. New York, USA: Springer, 2011: 677-702. [12] Song Xiaoyu, Yan Yuqi, Sun Huanliang, et al. Group trip recommendation based on check-in data[J]. Journal of Frontiers of Computer Science and Technology, 2015, 9(1): 51-62.

[13] Arase Y, Xie Xing, Hara T, et al. M ining people?s trips from large scale geo-tagged photos[C]//Proceedings of the 18th ACM International Conference on Multimedia, Firenze, Italy, Oct 25-29, 2010. New York, USA:ACM, 2010: 133-142.

[14] Cao Xin, Chen Lisi, Cong Gao, et al. Keyword-aware optimal route search[J]. Proceedings of the VLDB Endowment, 2012, 5(11): 1136-1147.

[15] Chen Zaiben, Shen Hengtao, Zhou Xiaofang. Discovering popular routes from trajectories[C]//Proceedings of the 27thIEEE International Conference on Data Engineering, Hannover, Germany, Apr 11- 16, 2011. Piscataway, USA: IEEE, 2011: 900-911.

[16] Chen Zaiben, Shen Hengtao, Zhou Xiaofang, et al. Searching trajectories by locations: an efficiency study[C]//Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, Indianapolis, USA, Jun 6-11, 2010. New York, USA:ACM, 2010: 255-266.

附中文參考文獻:

[12]宋曉宇,閆玉奇,孫煥良,等.基于簽到數(shù)據(jù)的群體旅游路線推薦[J].計算機科學與探索, 2015, 9(1): 51-62.

SONG Xiaoyu was born in 1963. He received the Ph.D. degree from University of Chinese Academy of Sciences in 2007. Now he is a professor at Shenyang Jianzhu University. His research interests include pattern precognition and image processing, computational intelligence and data mining, etc.

宋曉宇（1963—），男，遼寧沈陽人，2007年于中國科學院大學獲得博士學位，現(xiàn)為沈陽建筑大學教授，主要研究領(lǐng)域為模式識別與圖像處理，計算智能及數(shù)據(jù)挖掘等。發(fā)表學術(shù)論文120余篇，主持國家科技支撐計劃、國家科技推廣計劃等多項科研項目。

WEI Haiyan was born in 1990. He is an M.S. candidate at Shenyang Jianzhu University. His research interest is data m ining.

韋海燕（1990—），男，廣西柳州人，沈陽建筑大學碩士研究生，主要研究領(lǐng)域為數(shù)據(jù)挖掘。

SUN Huanliang was born in 1969. He received the Ph.D. degree from Northeastern University in 2005. Now he is a professor at Shenyang Jianzhu University, and the senior member of CCF. His research interests include spatial database and data mining, etc.

孫煥良（1969—），男，黑龍江望奎人，2005年于東北大學獲得博士學位，現(xiàn)為沈陽建筑大學教授，CCF高級會員，主要研究領(lǐng)域為空間數(shù)據(jù)庫，數(shù)據(jù)挖掘等。發(fā)表學術(shù)論文50余篇，主持國家自然科學基金、國家科技支撐計劃等多項科研項目。

XU Hongfei was born in 1987. He is a Ph.D. candidate at Northeastern University. His research interest is spatial database.

許鴻斐（1987—），男，山西太原人，東北大學博士研究生，主要研究領(lǐng)域為空間數(shù)據(jù)庫。

Local Distributed Group Travel Route Search Based on Check-in Data?

SONG Xiaoyu1+, WEI Haiyan1, SUN Huanliang1, XU Hongfei2
1. School of Information and Control Engineering, Shenyang Jianzhu University, Shenyang 110168, China 2. School of Information Science and Engineering, Northeastern University, Shenyang 110004, China
+ Corresponding author: E-mail: sxy@sjzu.edu.cn

Key words:route search; group recommendation; check-in data; location-based social networks

Abstract:Location-based social networks have generated a mass of data that can reflect user’s preference and the regularity of popular routes. These data have provided a new mode in searching travel route. The existing research on group travel route search usually aggregates user’s preference and then performs the search by using individual user route recommendation algorithm. In real life, when group users browse a global route, individual user wants to select different attractions in the local area of attractions in the route. Based on this requirement, this paper proposes the problem of local distributed group travel route search w ith the goal of getting a travel route which has local distributed POI (point of interest) and can make high satisfaction for the overall group. The search finds the optimal route using transfer graph which generated by the check-in data. In order to improve the efficiency, this paper proposes a double-hierarchy transfer graph generated w ith the popularity and metastasis of POI, and achieves hierarchical query. Designing an optimization algorithm based on branch and bound search strategy further improves the searching efficiency by using the controlled relationship between nodes. Using check-in data sets from Gowalla and Foursquare social networking websites, this paper evaluates the proposed algorithms w ith extensive experiments on the route profit and searching effi-ciency, and verifies the effectiveness of the algorithms.

doi:10.3778/j.issn.1673-9418.1507073

文獻標志碼：A

中圖分類號：TP311.13