基于簽到數(shù)據(jù)的群體局部分散式旅游路線搜索*
2016-06-07 02:35:07宋曉宇韋海燕孫煥良許鴻斐
計(jì)算機(jī)與生活 2016年5期
宋曉宇，韋海燕，孫煥良，許鴻斐
?
基于簽到數(shù)據(jù)的群體局部分散式旅游路線搜索*
宋曉宇1+，韋海燕1，孫煥良1，許鴻斐2
1.沈陽(yáng)建筑大學(xué)信息與控制工程學(xué)院，沈陽(yáng)110168
2.東北大學(xué)信息科學(xué)與工程學(xué)院，沈陽(yáng)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 (國(guó)家自然科學(xué)基金). Received 2015-07,Accepted 2015-09.
CNKI網(wǎng)絡(luò)優(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)絡(luò)產(chǎn)生了大量反映用戶喜好及路線流行規(guī)律的數(shù)據(jù)，為旅游路線搜索提供了新的模式。現(xiàn)有的群體旅游路線搜索通過(guò)將多個(gè)用戶的偏好進(jìn)行聚合，之后利用個(gè)體推薦算法進(jìn)行搜索。現(xiàn)實(shí)生活中存在群體整體上瀏覽一條線路時(shí)，個(gè)體用戶可以根據(jù)需要選擇局部不同景點(diǎn)進(jìn)行訪問(wèn)的需求。基于此需求，提出了群體用戶局部分散式旅游路線搜索問(wèn)題。該問(wèn)題結(jié)合群體用戶的個(gè)人偏好，發(fā)現(xiàn)一條帶有局部分散POI（point of interest）的且群體收益最大的訪問(wèn)路線。采用簽到數(shù)據(jù)，通過(guò)用戶在POI間的轉(zhuǎn)移情況生成POI轉(zhuǎn)移關(guān)系圖，在關(guān)系圖上進(jìn)行路線搜索。為了提高搜索效率，根據(jù)POI的流行度與轉(zhuǎn)移關(guān)系設(shè)計(jì)了雙層轉(zhuǎn)移關(guān)系圖，對(duì)POI進(jìn)行了概化，實(shí)現(xiàn)了分級(jí)查詢。設(shè)計(jì)了基于分支限界搜索策略的優(yōu)化算法，利用結(jié)點(diǎn)間的控制關(guān)系進(jìn)行剪枝，進(jìn)一步提高了算法的搜索效率。利用Gowalla和Foursquare社交網(wǎng)站真實(shí)的簽到數(shù)據(jù)集進(jìn)行了充分實(shí)驗(yàn)，對(duì)搜索出的路線收益及算法的運(yùn)行效率進(jìn)行了對(duì)比，驗(yàn)證了所提出方法的有效性。
關(guān)鍵詞：路線搜索；群體推薦；簽到數(shù)據(jù)；基于位置的社交網(wǎng)絡(luò)
1 引言
基于位置的社交網(wǎng)絡(luò)（location-based social networks, LBSNs）的快速發(fā)展，越來(lái)越多的用戶在Foursquare[1]、Gowalla[2]等在線社交平臺(tái)上分享其位置信息，并對(duì)特定地點(diǎn)進(jìn)行評(píng)論。通過(guò)對(duì)這些分享的數(shù)據(jù)進(jìn)行分析，可以挖掘出用戶的個(gè)人偏好及流行地點(diǎn)（point of interest，POI）和路線，為人們的出行提供路線推薦和搜索服務(wù)[3]。
現(xiàn)有的路線推薦大多針對(duì)個(gè)體用戶需求，研究基于地點(diǎn)和路線流行程度的路線推薦[2,4-5]，結(jié)合用戶偏好的路線推薦與搜索[6-7]及考慮查詢的位置、時(shí)間及天氣的路線搜索等[8-9]。針對(duì)群體用戶的推薦，現(xiàn)有研究通常將群體用戶的偏好進(jìn)行聚合，再采用個(gè)體路線推薦方法加以解決[10-12]。
現(xiàn)實(shí)生活中，當(dāng)結(jié)伴出行的群體用戶偏好差異較大，難以找到一條滿足全部用戶偏好的同行路線時(shí)，希望找到一條整體同行局部分散式的最優(yōu)出行路線，即在POI之間轉(zhuǎn)移時(shí)結(jié)伴同行，在訪問(wèn)具體POI時(shí)，個(gè)體用戶可以根據(jù)自己的偏好選擇該點(diǎn)周邊且使其收益最大的POI進(jìn)行訪問(wèn)。收益即用戶對(duì)POI的滿意度，通過(guò)路線中地點(diǎn)類別滿足用戶偏好程度來(lái)度量。
針對(duì)此需求，本文提出了群體用戶局部分散式旅游路線搜索。該路線搜索結(jié)合群體用戶的查詢位置、個(gè)體用戶偏好及用戶可以分散訪問(wèn)的POI周邊區(qū)域范圍，為群體用戶搜索到一條帶有局部分散POI且群體收益最大的訪問(wèn)路線。本文用局部分散度來(lái)限定用戶可以分散訪問(wèn)POI周邊區(qū)域，其具體定義將在第3章給出。每個(gè)用戶的最優(yōu)出行路線，可能包含不同的POI，但均在最優(yōu)路線所包含的POI內(nèi)，達(dá)到了共同轉(zhuǎn)移、分散訪問(wèn)的目的。
該路線搜索有效解決了群體偏好差異較大時(shí)，推薦路線中的公平性問(wèn)題，避免了群體整體滿意度高，個(gè)體收益差異較大的情況，兼顧了群體與個(gè)體的收益，增強(qiáng)了群體用戶的旅游體驗(yàn)效果，是對(duì)群體旅游路線推薦問(wèn)題的有效補(bǔ)充。
考慮用戶全局同行局部分散的情況，在大量的POI中搜索一條最優(yōu)路線是本文的挑戰(zhàn)。直接方法是通過(guò)遍歷滿足群體用戶約束的所有可行路線，根據(jù)分散訪問(wèn)區(qū)域大小以及個(gè)體用戶的偏好，最終確定使得群體收益最大的訪問(wèn)路線。隨著POI個(gè)數(shù)與POI之間邊數(shù)的增加，可行路線數(shù)會(huì)呈指數(shù)增長(zhǎng)，使得該方法伸縮性較差。
然而，現(xiàn)實(shí)生活中流行度較高的POI周圍通常伴有其他流行度較低的POI，這些POI往往不被包含在最優(yōu)推薦路線之中，對(duì)這些POI的計(jì)算，消耗了大量時(shí)間。本文提出了一種分層處理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)移圖中查詢可行路線，局部分散的因素在下層中進(jìn)行查詢。SPOI能夠保證群體具有較高收益，因此得到的近似最優(yōu)路線與最優(yōu)解之間收益相差較小。但該方法減少了對(duì)可行路線的判別，較大程度提高了搜索效率。并且設(shè)計(jì)了相應(yīng)的分支限界搜索算法，利用結(jié)點(diǎn)之間存在的相互控制關(guān)系進(jìn)行剪枝，剪掉得不到最優(yōu)解的子樹，進(jìn)一步加速對(duì)最優(yōu)路線的求解。
在數(shù)據(jù)選擇方面，現(xiàn)有針對(duì)旅游路線搜索的研究主要基于3種數(shù)據(jù)：GPS軌跡數(shù)據(jù)[5,7]、帶地理位置標(biāo)簽的照片數(shù)據(jù)[6,9]和簽到數(shù)據(jù)[2,8,12]。其中簽到數(shù)據(jù)包含用戶確切的空間位置信息。通過(guò)分析用戶的簽到記錄，可以得出用戶位置轉(zhuǎn)移信息、用戶的個(gè)人偏好以及連續(xù)訪問(wèn)兩地的時(shí)間花費(fèi)；分析某地的簽到記錄，可以得到該地區(qū)的流行地點(diǎn)以及地點(diǎn)的流行程度；簽到數(shù)據(jù)不僅包含了POI的空間信息，還包含了POI具有的類別特點(diǎn)。基于以上特點(diǎn)，簽到數(shù)據(jù)較適用于本文所提出的群體用戶分散式旅游路線搜索問(wèn)題。本文將簽到數(shù)據(jù)映射為圖，簽到的POI生成圖的結(jié)點(diǎn)，兩個(gè)結(jié)點(diǎn)如果有相同用戶連續(xù)簽到則生成一條邊。
綜上所述，本文的主要貢獻(xiàn)如下：
（1）提出了一種新的路線搜索——群體用戶局部分散式旅游路線搜索，有效解決了群體旅游路線推薦中的個(gè)體偏好差異較大問(wèn)題，并給出了該問(wèn)題的形式化定義。
（2）提出了一種分層處理POI的方法HPP，減少了對(duì)無(wú)效POI的計(jì)算，并且設(shè)計(jì)了分支限界搜索方法，提高了搜索效率。
（3）運(yùn)用Gowalla和Foursquare兩個(gè)社交網(wǎng)站真實(shí)的簽到數(shù)據(jù)集，對(duì)文中所提出算法進(jìn)行了充分實(shí)驗(yàn)研究，從路線收益及效率方面進(jìn)行對(duì)比，驗(yàn)證了算法在不同參數(shù)設(shè)置下的有效性。
本文組織結(jié)構(gòu)如下：第2章綜述相關(guān)研究工作；第3章定義群體用戶分散式旅游路線搜索問(wèn)題；第4章給出解決問(wèn)題的有效算法；第5章給出實(shí)驗(yàn)結(jié)果及分析；第6章總結(jié)全文。
2 相關(guān)工作
近年來(lái)，針對(duì)旅游路線搜索開(kāi)展了大量相關(guān)研究，根據(jù)推薦對(duì)象不同，分為針對(duì)個(gè)體用戶的路線搜索與推薦[5-7]以及針對(duì)群體用戶的路線搜索與推薦[10-12]。以下分別對(duì)兩個(gè)研究領(lǐng)域的現(xiàn)有工作進(jìn)行詳述。
2.1個(gè)體用戶路線搜索與推薦
針對(duì)個(gè)體用戶的路線搜索與推薦的相關(guān)研究，根據(jù)所使用的數(shù)據(jù)不同，通常有以下3種：通過(guò)分析社交網(wǎng)站上用戶分享的旅游照片來(lái)推薦旅游路線[6,9,13]；通過(guò)GPS軌跡來(lái)挖掘流行的旅游地點(diǎn)和線路[5,7]；運(yùn)用人們?nèi)粘Ｉ钪蟹窒淼暮灥接涗洠瑸橛脩籼峁┗谖恢玫穆肪€搜索[2,8]。
文獻(xiàn)[13]充分利用照片數(shù)據(jù)中的Tags和Titles，在此基礎(chǔ)上得到了不同旅游主題類別的頻繁訪問(wèn)模式。文獻(xiàn)[14]提出了KOR（keyword-aware optimal route search）問(wèn)題，即在滿足用戶提出的關(guān)鍵字與消耗約束的基礎(chǔ)上搜索一條最流行的路線，運(yùn)用了近似算法OSScaling、BucketBound以及貪心算法來(lái)解決此問(wèn)題。文獻(xiàn)[15]中，基于GPS軌跡數(shù)據(jù)，運(yùn)用Coherence Expanding算法構(gòu)建中間轉(zhuǎn)移網(wǎng)絡(luò)，運(yùn)用Absorbing Markov Chain模型與Maximum Probability Product算法在轉(zhuǎn)移網(wǎng)絡(luò)中尋找概率最大的路徑。文獻(xiàn)[16]從連續(xù)的簽到地點(diǎn)構(gòu)成的路線中挖掘出頻繁的訪問(wèn)模式，根據(jù)用戶需求推薦分?jǐn)?shù)最高的訪問(wèn)路線。
上述的旅游路線搜索與推薦研究主要針對(duì)個(gè)體用戶，根據(jù)個(gè)體用戶的偏好或查詢需求進(jìn)行推薦。本文的研究對(duì)象為群體用戶，推薦的路線需要滿足群體用戶整體偏好，針對(duì)個(gè)體用戶的路線推薦方法難以解決該問(wèn)題。
2.2群體用戶路線搜索與推薦
現(xiàn)有針對(duì)群體用戶進(jìn)行旅游路線搜索與推薦的常用方法通常將群體用戶的偏好進(jìn)行聚合，之后再采用個(gè)體路線推薦方法加以解決[10-12]。文獻(xiàn)[10]采用最小痛苦聚合偏好算法（Least M isery），將群體中成員偏好的最小值作為群體偏好，并通過(guò)交互反饋過(guò)程建立群體偏好模型，推薦的路線中不存在收益較低的用戶。文獻(xiàn)[11]采用平均數(shù)聚合偏好算法（Average）對(duì)群體用戶的偏好進(jìn)行聚合，將群體內(nèi)每名用戶的偏好取平均數(shù)作為群體整體的偏好，目標(biāo)是能夠最大化群體整體收益。在此基礎(chǔ)上，文獻(xiàn)[12]提出了動(dòng)態(tài)聚合偏好算法（dynam ic aggregation preference），根據(jù)當(dāng)前個(gè)體用戶不同收益狀態(tài)，動(dòng)態(tài)調(diào)整用戶偏好的優(yōu)先級(jí)，使路線中后續(xù)的地點(diǎn)選擇更偏向于當(dāng)前滿意度低的用戶，推薦的路線個(gè)體收益差異較小。
雖然上述針對(duì)群體用戶的旅游路線搜索與推薦方法對(duì)于傳統(tǒng)的群體旅游路線搜索均能取得良好的結(jié)果，但推薦結(jié)果均為一條由若干POI組成的路線，不能解決群體用戶整體上瀏覽一條路線時(shí)在局部選擇景點(diǎn)的需求。
與上述工作相比，本文提出了群體用戶局部分散式旅游路線搜索，為群體用戶搜索到一條帶有局部分散POI的且群體收益最大的訪問(wèn)路線，群體中每個(gè)用戶可以訪問(wèn)不同的POI。現(xiàn)有方法均不適于解決該問(wèn)題。
3 問(wèn)題定義
其中，CheckinNum(vi)代表vi的簽到次數(shù)；argc∈Cmax(CheckinNum(vj):vj.c=vi.c)代表與vi同類的POI中最大的簽到次數(shù)。
本文采用基于位置服務(wù)的在線網(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)代表兩個(gè)POI之間的一條可行路線，邊的數(shù)目為|E|，邊上的權(quán)值代表兩個(gè)POI之間的歐式空間距離，用d(vi,vj)表示。一條POI訪問(wèn)路線可表示為R=(v0,v1,…,vn)。任一結(jié)點(diǎn)v∈V的鄰接點(diǎn)的集合為nb(v)={u|(v,u)∈E}，表示與該P(yáng)OI存在可行路線的其他POI。結(jié)點(diǎn)v的出度數(shù)為d(v)=|nb(v)|。
定義1（個(gè)體偏好向量）個(gè)體偏好向量是用戶u對(duì)不同類型地點(diǎn)的喜愛(ài)程度，表示為PV(u)=
定義2（局部分散度）局部分散度用來(lái)限定用戶可以分散訪問(wèn)POI周邊的區(qū)域，表示為α。與POI的空間距離小于α且滿足轉(zhuǎn)移關(guān)系的其他POI屬于可分散訪問(wèn)的地點(diǎn)。例如圖1中，若當(dāng)前訪問(wèn)點(diǎn)為v5，α為1.6，則在該點(diǎn)能夠分散訪問(wèn)的其他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ù)局部分散度求出的可分散訪問(wèn)POI。
定義4（個(gè)體收益）個(gè)體收益代表單個(gè)用戶對(duì)一條旅游路線的滿意程度。計(jì)算方法如式（2）所示：
其中，M代表R中地點(diǎn)個(gè)數(shù)。例如圖1所示，PV(u1)代表用戶u1對(duì)c1、c2、c3這3類地點(diǎn)的偏好向量，若一條路線R=(v5,v1),則得出用戶u1在旅游路線R中的收益為Profit(u1)=0.10+0.03=0.13。
定義5（群體收益）群體收益代表群體U對(duì)局部分散路線的滿意程度，是每名用戶在各自最優(yōu)出行路線中的收益總和，表示為Profit(U)，計(jì)算方法如式（3）所示：
其中，|U|表示群體用戶的數(shù)量。
Fig.1 An example of searching圖1 一個(gè)搜索例子
定義6（群體用戶局部分散式旅游路線查詢）Q=
問(wèn)題1（群體用戶局部分散式旅游路線搜索）依據(jù)圖G，結(jié)合Q=
RLD-max=arg max(Profit(U))
RLD-max.q表示最大收益值；RLD-max-ui表示每名用戶的最優(yōu)出行路線。例如圖1中，群體用戶u1、u2發(fā)出查詢Q=
4 搜索方法
下面研究路線搜索算法。4.1節(jié)介紹處理該問(wèn)題的基本算法，4.2節(jié)介紹HPP處理方法和DTG的構(gòu)建，4.3節(jié)介紹基于分支限界搜索策略的優(yōu)化算法。
4.1基本算法BSL
一個(gè)基本的解決群體局部分散式旅游路線搜索問(wèn)題的方法為：在圖G中，根據(jù)給定起點(diǎn)，采用深度優(yōu)先搜索策略，找到所有滿足地點(diǎn)數(shù)目約束的可行路線，根據(jù)用戶的個(gè)人偏好以及局部分散度確定每條路線的收益值，最終將收益最大的局部分散式路線返回給群體。同時(shí)為每名用戶返回最優(yōu)出行路線。
算法1描述了基本算法BSL的細(xì)節(jié)。步驟5中，當(dāng)路線長(zhǎng)度m'=m時(shí)，計(jì)算路線的收益，否則將該結(jié)點(diǎn)放入棧U中，遞歸調(diào)用BSL，直到遍歷完nb(vs)為止。最終輸出最大收益可行路線RLD-max、最大收益RLD-max.q以及每名用戶最大收益路線RLD-max-ui。步驟11中，根據(jù)式（3）計(jì)算群體在當(dāng)前路線中的收益。步驟12～15中，如果當(dāng)前群體收益大于已有最優(yōu)收益，對(duì)當(dāng)前群體及個(gè)體最優(yōu)路線進(jìn)行更新。
算法1 BSL(G,Q)
輸入：G,Q=
輸出：Umax中存儲(chǔ)的最大收益路線RLD-max及qmax中存儲(chǔ)的最大收益值RLD-max.q;umax[|U|]中存儲(chǔ)的每名用戶各自最優(yōu)路線RLD-max-ui。
1.初始化棧U,Umax,棧數(shù)組u[|U|],umax[|U|];
2.當(dāng)前可行路線長(zhǎng)度m'=0,qmax=0;
3. For nb(vs)中的每一個(gè)結(jié)點(diǎn)vjdo
4. m'=m'+1;
5. If m'=m
6. For U中所有結(jié)點(diǎn)vido
7.For群體中所有用戶uido
8.根據(jù)式（2），找出vi分散區(qū)域內(nèi)個(gè)體收益最大的結(jié)點(diǎn)vk;
9.Profit(ui)=vk.c×p(ui,c);
10.u[ui].push(vk);
11.Profit(U)=Profit(U)+Profit(ui); //根據(jù)式（3）計(jì)算群體收益
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)镼=
4.2 HPP方法和DTG關(guān)系圖的構(gòu)建
為解決基本算法的不足，本文提出了一種分層處理POI的方法HPP，通過(guò)該方法構(gòu)建雙層轉(zhuǎn)移關(guān)系圖DTG，減少候選路線的數(shù)量，實(shí)現(xiàn)了分級(jí)查詢，有效提高了查詢效率。
如圖2（a）所示，HPP方法首先從原始POI中選取流行度大于閾值β的POI，將其稱作SPOI點(diǎn)。本文通過(guò)基于密度的聚類方法DBSCAN（density-based spatial clustering of applications w ith noise），對(duì)原始POI在空間進(jìn)行聚類，將所有聚簇中最大流行度的平均值作為流行度閾值β。然后依據(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)系圖中進(jìn)行查詢。
圖3依據(jù)圖1中原始POI，設(shè)定流行度閾值為0.4，通過(guò)HPP處理，形成的DTG。圖3（a）中，v5、v2、v9和v10構(gòu)成上層轉(zhuǎn)移關(guān)系圖。圖3（b）下層轉(zhuǎn)移關(guān)系圖中，v5包含的分散地點(diǎn)有v8、v4、v1；v2包含的分散地點(diǎn)有v6、v7；v9包含的分散地點(diǎn)有v3；v10包含的分散地點(diǎn)有v11。 4.3基于分支限界搜索策略的近似優(yōu)化算法DTG-BB
基于DTG，本文采用分支限界搜索策略獲取最優(yōu)路線，提出了DTG-BB搜索算法。該算法的基本思想是：在搜索過(guò)程中，從起點(diǎn)vs和空優(yōu)先隊(duì)列開(kāi)始，vs被擴(kuò)展后，其兒子結(jié)點(diǎn)被依次插入堆中，之后算法從堆中取出具有最大當(dāng)前收益的結(jié)點(diǎn)作為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并依次檢查與當(dāng)前擴(kuò)展結(jié)點(diǎn)相鄰的所有結(jié)點(diǎn)。該過(guò)程一直持續(xù)到優(yōu)先隊(duì)列為空時(shí)為止。
在搜索過(guò)程中，利用結(jié)點(diǎn)間的控制關(guān)系進(jìn)行剪枝。在一般情況下，如果解空間樹中以結(jié)點(diǎn)vi為根的子樹中所含的解優(yōu)于以結(jié)點(diǎn)vj為根的子樹中所含的解，則結(jié)點(diǎn)vi控制了結(jié)點(diǎn)vj，以被控制的結(jié)點(diǎn)vj為根的子樹可以減去。圖4為圖3（a）的解空間樹，從起點(diǎn)v5出發(fā)，經(jīng)過(guò)結(jié)點(diǎn)v2和經(jīng)過(guò)結(jié)點(diǎn)v9的兩條路徑到達(dá)圖3中的同一結(jié)點(diǎn)v10。如圖4，在該問(wèn)題的解空間樹中，這兩條路徑對(duì)應(yīng)于解空間樹中兩個(gè)不同的結(jié)點(diǎn)4和5。如果結(jié)點(diǎn)4所對(duì)應(yīng)的收益大于結(jié)點(diǎn)5所對(duì)應(yīng)的收益，此時(shí)以結(jié)點(diǎn)4為根的子樹中所包含的從v5到終點(diǎn)的路線收益大于以結(jié)點(diǎn)5為根的子樹中所包含的收益。這時(shí)，結(jié)點(diǎn)4控制了結(jié)點(diǎn)5。因此，可以將以5為根的子樹剪去。優(yōu)先隊(duì)列分支限界法的具體執(zhí)行過(guò)程如算法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=
輸出：Umax中存儲(chǔ)的最大收益路線RLD-max及qmax中存儲(chǔ)的最大收益值RLD-max.q;umax[|U|]中存儲(chǔ)的每名用戶各自最優(yōu)路線RLD-max-ui。
1.初始化最大堆H，數(shù)組p，棧U，Umax，棧數(shù)組u[|U|]，umax[|U|]，定義H中元素E和N
2.當(dāng)前可行路線長(zhǎng)度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)中的每一個(gè)結(jié)點(diǎn)vjdo
7. If E.profit +群體在vj的收益>p[vj] //滿足控制約束
8.p[vj]=E.profit +群體在vj的收益
9.U.push(vj);
10.N.v=vj//加入活結(jié)點(diǎn)隊(duì)列
11.N.profit=p[vj]
12.H.push(N)
13. If m′=m
14.For U中所有結(jié)點(diǎn)vido
15.For群體中所有用戶uido
16.根據(jù)式（2），找出vi分散區(qū)域內(nèi)個(gè)體收益最大的結(jié)點(diǎn)vk；
17.Profit(ui)=vk.c×p(ui,c);
18.u[ui].push(vk);
19.Profit(U)=Profit(U)+Profit(ui); //根據(jù)式（3）計(jì)算群體收益
20.If Profit(U)>qmax
21.qmax=Profit(U);
22.Umax=U;
23.umax=u;
算法中，H為最大堆，表示活結(jié)點(diǎn)優(yōu)先隊(duì)列，堆中元素類型包含屬性v，用于記錄該活結(jié)點(diǎn)所表示的雙層轉(zhuǎn)移關(guān)系圖G′中相對(duì)應(yīng)的結(jié)點(diǎn)編號(hào)；屬性profit表示從起始點(diǎn)到v所記錄的結(jié)點(diǎn)的收益值。用數(shù)組p記錄從起始點(diǎn)到各結(jié)點(diǎn)的收益。步驟1中，將起點(diǎn)作為初始擴(kuò)展結(jié)點(diǎn)。步驟4中，while循環(huán)體完成對(duì)解空間內(nèi)部結(jié)點(diǎn)的擴(kuò)展，一直持續(xù)到活結(jié)點(diǎn)優(yōu)先隊(duì)列為空時(shí)為止。步驟6中，依次檢查與當(dāng)前擴(kuò)展結(jié)點(diǎn)相鄰的所有頂點(diǎn)。步驟7中，利用結(jié)點(diǎn)間的控制關(guān)系進(jìn)行剪枝，如果該結(jié)點(diǎn)滿足控制約束，則將該結(jié)點(diǎn)作為活結(jié)點(diǎn)插入到優(yōu)先隊(duì)列中。
例如圖3中，群體用戶u1、u2發(fā)出查詢?yōu)镼= 該優(yōu)化算法基于DTG，減少了對(duì)無(wú)效POI的計(jì)算，并且運(yùn)用剪枝操作，剪掉了不能生成最優(yōu)解的子樹，進(jìn)一步提高了搜索效率。 實(shí)驗(yàn)首先對(duì)比所提出的兩種搜索算法與常用的偏好聚合算法，在為群體推薦路線時(shí)，群體用戶的整體收益和個(gè)體收益差異性。然后對(duì)BSL算法和DTG-BB算法在搜索效率上進(jìn)行對(duì)比。 Fig.4 A solution space tree of Fig.3（a）圖4 圖3（a）的解空間樹 實(shí)驗(yàn)對(duì)比3種常用的偏好聚合算法：平均數(shù)聚合偏好算法（Average）中，群體對(duì)某類地點(diǎn)的偏好為群體內(nèi)用戶對(duì)該類地點(diǎn)偏好的平均數(shù)；乘法聚合偏好算法（Multiply）中，群體的偏好為群體內(nèi)用戶對(duì)該類地點(diǎn)偏好的累乘；最小痛苦聚合偏好算法（Least M isery）中，群體的偏好為群體內(nèi)用戶對(duì)該類地點(diǎn)偏好的最小值。因?yàn)闊o(wú)痛苦聚合偏好算法有很大幾率無(wú)法得到解，所以實(shí)驗(yàn)不采用此算法。 5.1實(shí)驗(yàn)數(shù)據(jù) 本文實(shí)驗(yàn)采用Gowalla和Foursquare社交網(wǎng)站真實(shí)的簽到數(shù)據(jù)集。實(shí)驗(yàn)選取Gowalla數(shù)據(jù)集中美國(guó)舊金山市北部從2009年3月到2010年10月的64 358條簽到記錄，過(guò)濾掉簽到次數(shù)低于3次的簽到地點(diǎn)，得到5 706個(gè)地點(diǎn)，如果一天中兩個(gè)地點(diǎn)間有相同的用戶連續(xù)簽到，并且平均時(shí)間間隔大于1小時(shí)小于5小時(shí)，兩點(diǎn)間生成一條有向邊。本文利用Foursquare簽到數(shù)據(jù)集中對(duì)地點(diǎn)類別的描述以及文獻(xiàn)[9]中計(jì)算地點(diǎn)流行程度的方法，來(lái)確定每個(gè)地點(diǎn)的類別和流行度。在用戶的個(gè)人偏好學(xué)習(xí)中，采用Foursquare的tips數(shù)據(jù)集，該數(shù)據(jù)集由文獻(xiàn)[7]獲得，實(shí)驗(yàn)隨機(jī)選取美國(guó)紐約市tips數(shù)目大于30次的50名用戶，一共有1 606條tips記錄。 5.2實(shí)驗(yàn)設(shè)置 實(shí)驗(yàn)分為兩組：第一組實(shí)驗(yàn)中，路線包含的地點(diǎn)數(shù)目M=5，群體內(nèi)用戶數(shù)目N由2變化到6，研究群體內(nèi)用戶數(shù)目的變化對(duì)算法效果以及搜索效率的影響。N取不同數(shù)值時(shí)，進(jìn)行500次實(shí)驗(yàn)，每次實(shí)驗(yàn)隨機(jī)選取一個(gè)起始點(diǎn)，在50名用戶中隨機(jī)選取相應(yīng)數(shù)目的用戶，求得500次實(shí)驗(yàn)各項(xiàng)度量值的平均數(shù)。第二組實(shí)驗(yàn)中，群體內(nèi)用戶數(shù)目N=5，路線包含的地點(diǎn)數(shù)目M從2變化到6，研究地點(diǎn)數(shù)目的變化對(duì)算法效果以及搜索效率的影響。M取不同數(shù)值時(shí)，分別進(jìn)行500次實(shí)驗(yàn)，每次實(shí)驗(yàn)隨機(jī)選取一個(gè)起始點(diǎn)，在50名用戶中隨機(jī)選取5名用戶，求得500次實(shí)驗(yàn)各項(xiàng)度量值的平均數(shù)。 5.3效果對(duì)比實(shí)驗(yàn) 本節(jié)通過(guò)群體用戶整體的收益和個(gè)體收益差異性來(lái)評(píng)價(jià)BSL算法、DTG-BB算法、Average算法、Multiply算法和Least M isery算法的有效性。 5.3.1群體整體收益對(duì)比 圖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)隨路線中地點(diǎn)個(gè)數(shù)M變化的趨勢(shì)。隨著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均能為群體帶來(lái)較高的整體收益。 5.3.2個(gè)體收益差異性對(duì)比 Fig.5 Variation trend of Profit(U)圖5 Profit(U)的變化趨勢(shì) 個(gè)體收益差異性是對(duì)路線公平性的評(píng)價(jià)。本文采用均方根誤差RMSE(U)表示個(gè)體收益差異性，計(jì)算方法如式（4）所示。Profit(u)′為個(gè)體u在群體最優(yōu)路線中的平均每個(gè)地點(diǎn)的收益，Profit(u)″表示僅根據(jù)用戶u的個(gè)人偏好，得到的個(gè)人最優(yōu)路線中平均每個(gè)地點(diǎn)的收益，N表示群體人數(shù)。實(shí)驗(yàn)比較個(gè)體在群體最優(yōu)路線中與個(gè)人最優(yōu)路線中收益的RMSE(U)值。RMSE(U)值越小，代表用戶在群體最優(yōu)路線中的收益與個(gè)人最優(yōu)路線中的收益差異越小，表示個(gè)體收益差異性越小，推薦的路線越公平。 圖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)隨路線中地點(diǎn)數(shù)目M的變化情況，隨著M的增加，RMSE(U)值逐漸增高，與圖6（a）類似，其中BSL和DTG-BB算法比Average算法分別降低了約36%和34%。綜上可知，兩種局部分散式算法BSL和DTG-BB，使群體對(duì)局部提供的景點(diǎn)進(jìn)行訪問(wèn)，均能使個(gè)體收益差異較小，推薦的路線較公平。 5.4效率對(duì)比實(shí)驗(yàn) Fig.6 Variation trend of RMSE(U)圖6 RMSE(U)的變化趨勢(shì) Fig.7 Variation trend of efficiency圖7 效率的變化趨勢(shì) 圖7（a）顯示了算法訪問(wèn)結(jié)點(diǎn)數(shù)隨著群體內(nèi)用戶數(shù)目N的變化情況，N越大，算法訪問(wèn)的結(jié)點(diǎn)數(shù)越多，其中DTG-BB算法比BSL算法的訪問(wèn)結(jié)點(diǎn)數(shù)減少了約65%。圖7（b）中顯示了算法的運(yùn)行時(shí)間，與圖7 （a）中訪問(wèn)結(jié)點(diǎn)數(shù)的趨勢(shì)基本一致。圖7（c）中顯示了算法訪問(wèn)結(jié)點(diǎn)數(shù)隨著路線中地點(diǎn)數(shù)目M的變化情況，隨著M增加，算法訪問(wèn)的結(jié)點(diǎn)數(shù)呈指數(shù)次冪增長(zhǎng)。圖7（d）中顯示了算法的運(yùn)行時(shí)間，與圖7（c）中訪問(wèn)結(jié)點(diǎn)數(shù)的趨勢(shì)基本相同，與4.1節(jié)中的分析一致。綜合可知：DTG-BB算法在各種參數(shù)設(shè)置下運(yùn)行效率均高于BSL算法，DTG-BB算法具有較高的運(yùn)行效率。 本文提出了一種新的路線搜索方法——群體用戶局部分散式旅游路線搜索。該路線搜索方法可為群體用戶搜索一條帶有局部分散POI的且群體收益最大的訪問(wèn)路線。為了解決可行路線數(shù)目過(guò)多的問(wèn)題，本文提出了一種分層處理POI的方法HPP，通過(guò)HPP構(gòu)建DTG。本文方法減少了對(duì)可行路線的判別，實(shí)現(xiàn)了分級(jí)查詢，從而提高了搜索最優(yōu)路線的效率。實(shí)驗(yàn)用真實(shí)的數(shù)據(jù)集進(jìn)行路線收益和搜索效率對(duì)比，驗(yàn)證了本文方法的有效性。實(shí)驗(yàn)表明，局部分散式策略能使群體用戶獲得較高整體收益，個(gè)體收益差異性較小，同時(shí)所提出的近似優(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. 附中文參考文獻(xiàn): [12]宋曉宇,閆玉奇,孫煥良,等.基于簽到數(shù)據(jù)的群體旅游路線推薦[J].計(jì)算機(jī)科學(xué)與探索, 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—），男，遼寧沈陽(yáng)人，2007年于中國(guó)科學(xué)院大學(xué)獲得博士學(xué)位，現(xiàn)為沈陽(yáng)建筑大學(xué)教授，主要研究領(lǐng)域?yàn)槟Ｊ阶R(shí)別與圖像處理，計(jì)算智能及數(shù)據(jù)挖掘等。發(fā)表學(xué)術(shù)論文120余篇，主持國(guó)家科技支撐計(jì)劃、國(guó)家科技推廣計(jì)劃等多項(xiàng)科研項(xiàng)目。 WEI Haiyan was born in 1990. He is an M.S. candidate at Shenyang Jianzhu University. His research interest is data m ining. 韋海燕（1990—），男，廣西柳州人，沈陽(yáng)建筑大學(xué)碩士研究生，主要研究領(lǐng)域?yàn)閿?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年于東北大學(xué)獲得博士學(xué)位，現(xiàn)為沈陽(yáng)建筑大學(xué)教授，CCF高級(jí)會(huì)員，主要研究領(lǐng)域?yàn)榭臻g數(shù)據(jù)庫(kù)，數(shù)據(jù)挖掘等。發(fā)表學(xué)術(shù)論文50余篇，主持國(guó)家自然科學(xué)基金、國(guó)家科技支撐計(jì)劃等多項(xiàng)科研項(xiàng)目。 XU Hongfei was born in 1987. He is a Ph.D. candidate at Northeastern University. His research interest is spatial database. 許鴻斐（1987—），男，山西太原人，東北大學(xué)博士研究生，主要研究領(lǐng)域?yàn)榭臻g數(shù)據(jù)庫(kù)。 Local Distributed Group Travel Route Search Based on Check-in Data? SONG Xiaoyu1+, WEI Haiyan1, SUN Huanliang1, XU Hongfei2 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 文獻(xiàn)標(biāo)志碼：A 中圖分類號(hào)：TP311.135 實(shí)驗(yàn)結(jié)果與分析
6 結(jié)束語(yǔ)
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
