基于签到数据的群体局部分散式旅游路线搜索*

宋晓宇，韦海燕，孙焕良，许鸿斐



基于签到数据的群体局部分散式旅游路线搜索*

宋晓宇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网络优先出版: 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.

摘要：基于位置的社交网络产生了大量反映用户喜好及路线流行规律的数据，为旅游路线搜索提供了新的模式。现有的群体旅游路线搜索通过将多个用户的偏好进行聚合，之后利用个体推荐算法进行搜索。现实生活中存在群体整体上浏览一条线路时，个体用户可以根据需要选择局部不同景点进行访问的需求。基于此需求，提出了群体用户局部分散式旅游路线搜索问题。该问题结合群体用户的个人偏好，发现一条带有局部分散POI（point of interest）的且群体收益最大的访问路线。采用签到数据，通过用户在POI间的转移情况生成POI转移关系图，在关系图上进行路线搜索。为了提高搜索效率，根据POI的流行度与转移关系设计了双层转移关系图，对POI进行了概化，实现了分级查询。设计了基于分支限界搜索策略的优化算法，利用结点间的控制关系进行剪枝，进一步提高了算法的搜索效率。利用Gowalla和Foursquare社交网站真实的签到数据集进行了充分实验，对搜索出的路线收益及算法的运行效率进行了对比，验证了所提出方法的有效性。

关键词：路线搜索；群体推荐；签到数据；基于位置的社交网络

1 引言

基于位置的社交网络（location-based social networks, LBSNs）的快速发展，越来越多的用户在Foursquare[1]、Gowalla[2]等在线社交平台上分享其位置信息，并对特定地点进行评论。通过对这些分享的数据进行分析，可以挖掘出用户的个人偏好及流行地点（point of interest，POI）和路线，为人们的出行提供路线推荐和搜索服务[3]。

现有的路线推荐大多针对个体用户需求，研究基于地点和路线流行程度的路线推荐[2,4-5]，结合用户偏好的路线推荐与搜索[6-7]及考虑查询的位置、时间及天气的路线搜索等[8-9]。针对群体用户的推荐，现有研究通常将群体用户的偏好进行聚合，再采用个体路线推荐方法加以解决[10-12]。

现实生活中，当结伴出行的群体用户偏好差异较大，难以找到一条满足全部用户偏好的同行路线时，希望找到一条整体同行局部分散式的最优出行路线，即在POI之间转移时结伴同行，在访问具体POI时，个体用户可以根据自己的偏好选择该点周边且使其收益最大的POI进行访问。收益即用户对POI的满意度，通过路线中地点类别满足用户偏好程度来度量。

针对此需求，本文提出了群体用户局部分散式旅游路线搜索。该路线搜索结合群体用户的查询位置、个体用户偏好及用户可以分散访问的POI周边区域范围，为群体用户搜索到一条带有局部分散POI且群体收益最大的访问路线。本文用局部分散度来限定用户可以分散访问POI周边区域，其具体定义将在第3章给出。每个用户的最优出行路线，可能包含不同的POI，但均在最优路线所包含的POI内，达到了共同转移、分散访问的目的。

该路线搜索有效解决了群体偏好差异较大时，推荐路线中的公平性问题，避免了群体整体满意度高，个体收益差异较大的情况，兼顾了群体与个体的收益，增强了群体用户的旅游体验效果，是对群体旅游路线推荐问题的有效补充。

考虑用户全局同行局部分散的情况，在大量的POI中搜索一条最优路线是本文的挑战。直接方法是通过遍历满足群体用户约束的所有可行路线，根据分散访问区域大小以及个体用户的偏好，最终确定使得群体收益最大的访问路线。随着POI个数与POI之间边数的增加，可行路线数会呈指数增长，使得该方法伸缩性较差。

然而，现实生活中流行度较高的POI周围通常伴有其他流行度较低的POI，这些POI往往不被包含在最优推荐路线之中，对这些POI的计算，消耗了大量时间。本文提出了一种分层处理POI的方法（hierarchical processing POI，HPP），该方法将流行度较高的POI称为SPOI，其他POI根据与SPOI的距离与转移关系分配到SPOI中，之后构建双层转移关系图（doublehierarchy transfer graph，DTG），在上层转移图中查询可行路线，局部分散的因素在下层中进行查询。SPOI能够保证群体具有较高收益，因此得到的近似最优路线与最优解之间收益相差较小。但该方法减少了对可行路线的判别，较大程度提高了搜索效率。并且设计了相应的分支限界搜索算法，利用结点之间存在的相互控制关系进行剪枝，剪掉得不到最优解的子树，进一步加速对最优路线的求解。

在数据选择方面，现有针对旅游路线搜索的研究主要基于3种数据：GPS轨迹数据[5,7]、带地理位置标签的照片数据[6,9]和签到数据[2,8,12]。其中签到数据包含用户确切的空间位置信息。通过分析用户的签到记录，可以得出用户位置转移信息、用户的个人偏好以及连续访问两地的时间花费；分析某地的签到记录，可以得到该地区的流行地点以及地点的流行程度；签到数据不仅包含了POI的空间信息，还包含了POI具有的类别特点。基于以上特点，签到数据较适用于本文所提出的群体用户分散式旅游路线搜索问题。本文将签到数据映射为图，签到的POI生成图的结点，两个结点如果有相同用户连续签到则生成一条边。

综上所述，本文的主要贡献如下：

（1）提出了一种新的路线搜索——群体用户局部分散式旅游路线搜索，有效解决了群体旅游路线推荐中的个体偏好差异较大问题，并给出了该问题的形式化定义。

（2）提出了一种分层处理POI的方法HPP，减少了对无效POI的计算，并且设计了分支限界搜索方法，提高了搜索效率。

（3）运用Gowalla和Foursquare两个社交网站真实的签到数据集，对文中所提出算法进行了充分实验研究，从路线收益及效率方面进行对比，验证了算法在不同参数设置下的有效性。

本文组织结构如下：第2章综述相关研究工作；第3章定义群体用户分散式旅游路线搜索问题；第4章给出解决问题的有效算法；第5章给出实验结果及分析；第6章总结全文。

2 相关工作

近年来，针对旅游路线搜索开展了大量相关研究，根据推荐对象不同，分为针对个体用户的路线搜索与推荐[5-7]以及针对群体用户的路线搜索与推荐[10-12]。以下分别对两个研究领域的现有工作进行详述。

2.1个体用户路线搜索与推荐

针对个体用户的路线搜索与推荐的相关研究，根据所使用的数据不同，通常有以下3种：通过分析社交网站上用户分享的旅游照片来推荐旅游路线[6,9,13]；通过GPS轨迹来挖掘流行的旅游地点和线路[5,7]；运用人们日常生活中分享的签到记录，为用户提供基于位置的路线搜索[2,8]。

文献[13]充分利用照片数据中的Tags和Titles，在此基础上得到了不同旅游主题类别的频繁访问模式。文献[14]提出了KOR（keyword-aware optimal route search）问题，即在满足用户提出的关键字与消耗约束的基础上搜索一条最流行的路线，运用了近似算法OSScaling、BucketBound以及贪心算法来解决此问题。文献[15]中，基于GPS轨迹数据，运用Coherence Expanding算法构建中间转移网络，运用Absorbing Markov Chain模型与Maximum Probability Product算法在转移网络中寻找概率最大的路径。文献[16]从连续的签到地点构成的路线中挖掘出频繁的访问模式，根据用户需求推荐分数最高的访问路线。

上述的旅游路线搜索与推荐研究主要针对个体用户，根据个体用户的偏好或查询需求进行推荐。本文的研究对象为群体用户，推荐的路线需要满足群体用户整体偏好，针对个体用户的路线推荐方法难以解决该问题。

2.2群体用户路线搜索与推荐

现有针对群体用户进行旅游路线搜索与推荐的常用方法通常将群体用户的偏好进行聚合，之后再采用个体路线推荐方法加以解决[10-12]。文献[10]采用最小痛苦聚合偏好算法（Least M isery），将群体中成员偏好的最小值作为群体偏好，并通过交互反馈过程建立群体偏好模型，推荐的路线中不存在收益较低的用户。文献[11]采用平均数聚合偏好算法（Average）对群体用户的偏好进行聚合，将群体内每名用户的偏好取平均数作为群体整体的偏好，目标是能够最大化群体整体收益。在此基础上，文献[12]提出了动态聚合偏好算法（dynam ic aggregation preference），根据当前个体用户不同收益状态，动态调整用户偏好的优先级，使路线中后续的地点选择更偏向于当前满意度低的用户，推荐的路线个体收益差异较小。

虽然上述针对群体用户的旅游路线搜索与推荐方法对于传统的群体旅游路线搜索均能取得良好的结果，但推荐结果均为一条由若干POI组成的路线，不能解决群体用户整体上浏览一条路线时在局部选择景点的需求。

与上述工作相比，本文提出了群体用户局部分散式旅游路线搜索，为群体用户搜索到一条带有局部分散POI的且群体收益最大的访问路线，群体中每个用户可以访问不同的POI。现有方法均不适于解决该问题。

3 问题定义

其中，CheckinNum(vi)代表vi的签到次数；argc∈Cmax(CheckinNum(vj):vj.c=vi.c)代表与vi同类的POI中最大的签到次数。

本文采用基于位置服务的在线网站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之间的一条可行路线，边的数目为|E|，边上的权值代表两个POI之间的欧式空间距离，用d(vi,vj)表示。一条POI访问路线可表示为R=(v0,v1,…,vn)。任一结点v∈V的邻接点的集合为nb(v)={u|(v,u)∈E}，表示与该POI存在可行路线的其他POI。结点v的出度数为d(v)=|nb(v)|。

定义1（个体偏好向量）个体偏好向量是用户u对不同类型地点的喜爱程度，表示为PV(u)=，其中p(u,ci)代表用户u对地点类型ci的偏好程度。本文采用文献[7]提出的方法对用户偏好进行学习。

定义2（局部分散度）局部分散度用来限定用户可以分散访问POI周边的区域，表示为α。与POI的空间距离小于α且满足转移关系的其他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根据局部分散度求出的可分散访问POI。

定义4（个体收益）个体收益代表单个用户对一条旅游路线的满意程度。计算方法如式（2）所示：

其中，M代表R中地点个数。例如图1所示，PV(u1)代表用户u1对c1、c2、c3这3类地点的偏好向量，若一条路线R=(v5,v1),则得出用户u1在旅游路线R中的收益为Profit(u1)=0.10+0.03=0.13。

定义5（群体收益）群体收益代表群体U对局部分散路线的满意程度，是每名用户在各自最优出行路线中的收益总和，表示为Profit(U)，计算方法如式（3）所示：

其中，|U|表示群体用户的数量。

Fig.1 An example of searching图1 一个搜索例子

定义6（群体用户局部分散式旅游路线查询）Q= ，s代表查询点，n是用户设定的访问地点个数，α为局部分散度。

问题1（群体用户局部分散式旅游路线搜索）依据图G，结合Q=，以及群体用户偏好PV，为群体U找到一条带有局部分散POI的且群体收益最大的访问路线，记为：

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

RLD-max.q表示最大收益值；RLD-max-ui表示每名用户的最优出行路线。例如图1中，群体用户u1、u2发出查询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节介绍处理该问题的基本算法，4.2节介绍HPP处理方法和DTG的构建，4.3节介绍基于分支限界搜索策略的优化算法。

4.1基本算法BSL

一个基本的解决群体局部分散式旅游路线搜索问题的方法为：在图G中，根据给定起点，采用深度优先搜索策略，找到所有满足地点数目约束的可行路线，根据用户的个人偏好以及局部分散度确定每条路线的收益值，最终将收益最大的局部分散式路线返回给群体。同时为每名用户返回最优出行路线。

算法1描述了基本算法BSL的细节。步骤5中，当路线长度m'=m时，计算路线的收益，否则将该结点放入栈U中，递归调用BSL，直到遍历完nb(vs)为止。最终输出最大收益可行路线RLD-max、最大收益RLD-max.q以及每名用户最大收益路线RLD-max-ui。步骤11中，根据式（3）计算群体在当前路线中的收益。步骤12～15中，如果当前群体收益大于已有最优收益，对当前群体及个体最优路线进行更新。

算法1 BSL(G,Q)

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

输出：Umax中存储的最大收益路线RLD-max及qmax中存储的最大收益值RLD-max.q;umax[|U|]中存储的每名用户各自最优路线RLD-max-ui。

1.初始化栈U,Umax,栈数组u[|U|],umax[|U|];

2.当前可行路线长度m'=0,qmax=0;

3. For nb(vs)中的每一个结点vjdo

4. m'=m'+1;

5. If m'=m

6. For U中所有结点vido

7.For群体中所有用户uido

8.根据式（2），找出vi分散区域内个体收益最大的结点vk;

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

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

11.Profit(U)=Profit(U)+Profit(ui); //根据式（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发出查询为Q=。存在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)。根据Q可知，α=1.9，群体在v5可局部分散访问的POI有v4和v8，在v2可局部分散访问的POI有v7和v6，在v10可局部分散访问的POI有v11。群体用户根据个人偏好选择其收益最高的POI进行访问。经过计算，最终为群体返回的最优路线为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关系图的构建

为解决基本算法的不足，本文提出了一种分层处理POI的方法HPP，通过该方法构建双层转移关系图DTG，减少候选路线的数量，实现了分级查询，有效提高了查询效率。

如图2（a）所示，HPP方法首先从原始POI中选取流行度大于阈值β的POI，将其称作SPOI点。本文通过基于密度的聚类方法DBSCAN（density-based spatial clustering of applications w ith noise），对原始POI在空间进行聚类，将所有聚簇中最大流行度的平均值作为流行度阈值β。然后依据转移关系与局部分散度获取其附属POI。图2（b）中，SPOI依据其原始POI的转移关系构建上层关系转移图，其附属POI依据转移与距离关系形成下层关系转移图。在上层转移关系图中查询到可行路线，局部分散的影响在下层转移关系图中进行查询。

图3依据图1中原始POI，设定流行度阈值为0.4，通过HPP处理，形成的DTG。图3（a）中，v5、v2、v9和v10构成上层转移关系图。图3（b）下层转移关系图中，v5包含的分散地点有v8、v4、v1；v2包含的分散地点有v6、v7；v9包含的分散地点有v3；v10包含的分散地点有v11。 4.3基于分支限界搜索策略的近似优化算法DTG-BB

基于DTG，本文采用分支限界搜索策略获取最优路线，提出了DTG-BB搜索算法。该算法的基本思想是：在搜索过程中，从起点vs和空优先队列开始，vs被扩展后，其儿子结点被依次插入堆中，之后算法从堆中取出具有最大当前收益的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有结点。该过程一直持续到优先队列为空时为止。

在搜索过程中，利用结点间的控制关系进行剪枝。在一般情况下，如果解空间树中以结点vi为根的子树中所含的解优于以结点vj为根的子树中所含的解，则结点vi控制了结点vj，以被控制的结点vj为根的子树可以减去。图4为图3（a）的解空间树，从起点v5出发，经过结点v2和经过结点v9的两条路径到达图3中的同一结点v10。如图4，在该问题的解空间树中，这两条路径对应于解空间树中两个不同的结点4和5。如果结点4所对应的收益大于结点5所对应的收益，此时以结点4为根的子树中所包含的从v5到终点的路线收益大于以结点5为根的子树中所包含的收益。这时，结点4控制了结点5。因此，可以将以5为根的子树剪去。优先队列分支限界法的具体执行过程如算法2所示。

Fig.2 HPP and DTG图2 HPP方法和DTG关系图

Fig.3 DTG of Fig.1图3 依据图1构建的DTG

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

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

输出：Umax中存储的最大收益路线RLD-max及qmax中存储的最大收益值RLD-max.q;umax[|U|]中存储的每名用户各自最优路线RLD-max-ui。

1.初始化最大堆H，数组p，栈U，Umax，栈数组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)中的每一个结点vjdo

7. If E.profit +群体在vj的收益>p[vj] //满足控制约束

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

9.U.push(vj);

10.N.v=vj//加入活结点队列

11.N.profit=p[vj]

12.H.push(N)

13. If m′=m

14.For U中所有结点vido

15.For群体中所有用户uido

16.根据式（2），找出vi分散区域内个体收益最大的结点vk；

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

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

19.Profit(U)=Profit(U)+Profit(ui); //根据式（3）计算群体收益

20.If Profit(U)>qmax

21.qmax=Profit(U);

22.Umax=U;

23.umax=u;

算法中，H为最大堆，表示活结点优先队列，堆中元素类型包含属性v，用于记录该活结点所表示的双层转移关系图G′中相对应的结点编号；属性profit表示从起始点到v所记录的结点的收益值。用数组p记录从起始点到各结点的收益。步骤1中，将起点作为初始扩展结点。步骤4中，while循环体完成对解空间内部结点的扩展，一直持续到活结点优先队列为空时为止。步骤6中，依次检查与当前扩展结点相邻的所有顶点。步骤7中，利用结点间的控制关系进行剪枝，如果该结点满足控制约束，则将该结点作为活结点插入到优先队列中。

例如图3中，群体用户u1、u2发出查询为Q=。在图1基础上，当流行度阈值为0.4时构建DTG，图3（a）中有两条可行路线：R1=(v5,v9,v10)，R2=(v5, v2,v10)。与基本算法相同，α=1.9。此时，从v5开始扩展，p[v5]=0.4；E.profit=0.4；结点v5被扩展后，将其邻接点加入优先队列，由于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)。假设地点个数大于2，并且经过v10的路线满足地点个数要求，当算法扩展到v9时，由于p[v9]+0.32

该优化算法基于DTG，减少了对无效POI的计算，并且运用剪枝操作，剪掉了不能生成最优解的子树，进一步提高了搜索效率。

5 实验结果与分析

实验首先对比所提出的两种搜索算法与常用的偏好聚合算法，在为群体推荐路线时，群体用户的整体收益和个体收益差异性。然后对BSL算法和DTG-BB算法在搜索效率上进行对比。

Fig.4 A solution space tree of Fig.3（a）图4 图3（a）的解空间树

实验对比3种常用的偏好聚合算法：平均数聚合偏好算法（Average）中，群体对某类地点的偏好为群体内用户对该类地点偏好的平均数；乘法聚合偏好算法（Multiply）中，群体的偏好为群体内用户对该类地点偏好的累乘；最小痛苦聚合偏好算法（Least M isery）中，群体的偏好为群体内用户对该类地点偏好的最小值。因为无痛苦聚合偏好算法有很大几率无法得到解，所以实验不采用此算法。

5.1实验数据

本文实验采用Gowalla和Foursquare社交网站真实的签到数据集。实验选取Gowalla数据集中美国旧金山市北部从2009年3月到2010年10月的64 358条签到记录，过滤掉签到次数低于3次的签到地点，得到5 706个地点，如果一天中两个地点间有相同的用户连续签到，并且平均时间间隔大于1小时小于5小时，两点间生成一条有向边。本文利用Foursquare签到数据集中对地点类别的描述以及文献[9]中计算地点流行程度的方法，来确定每个地点的类别和流行度。在用户的个人偏好学习中，采用Foursquare的tips数据集，该数据集由文献[7]获得，实验随机选取美国纽约市tips数目大于30次的50名用户，一共有1 606条tips记录。

5.2实验设置

实验分为两组：第一组实验中，路线包含的地点数目M=5，群体内用户数目N由2变化到6，研究群体内用户数目的变化对算法效果以及搜索效率的影响。N取不同数值时，进行500次实验，每次实验随机选取一个起始点，在50名用户中随机选取相应数目的用户，求得500次实验各项度量值的平均数。第二组实验中，群体内用户数目N=5，路线包含的地点数目M从2变化到6，研究地点数目的变化对算法效果以及搜索效率的影响。M取不同数值时，分别进行500次实验，每次实验随机选取一个起始点，在50名用户中随机选取5名用户，求得500次实验各项度量值的平均数。

5.3效果对比实验

本节通过群体用户整体的收益和个体收益差异性来评价BSL算法、DTG-BB算法、Average算法、Multiply算法和Least M isery算法的有效性。

5.3.1群体整体收益对比

图5（a）显示了Profit(U)随群体中用户数目的变化情况。随着群体内用户数目N的增加，每种算法的Profit(U)值增加，表明N增大，群体收益提高。其中，Multiply和Least M isery算法的效果较差，Average、BSL和DTG-BB算法的效果均较好，其中BSL比Average算法增多了约43%，DTG-BB比Average算法增多了约40%。图5（b）显示了Profit(U)随路线中地点个数M变化的趋势。随着M的增加，每种算法的Profit(U)值增加，表明M增加，群体整体收益提高。与图5（a）类似，Multiply和Least M isery算法表现出较差的效果，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在群体最优路线中的平均每个地点的收益，Profit(u)″表示仅根据用户u的个人偏好，得到的个人最优路线中平均每个地点的收益，N表示群体人数。实验比较个体在群体最优路线中与个人最优路线中收益的RMSE(U)值。RMSE(U)值越小，代表用户在群体最优路线中的收益与个人最优路线中的收益差异越小，表示个体收益差异性越小，推荐的路线越公平。

图6（a）显示了RMSE(U)随着群体内用户数目N的变化情况，N越大，RMSE(U)越大，代表群体内用户收益差异越低，其中Average算法效果要优于Multiply和Least M isery算法，而BSL和DTG-BB算法则比Average算法分别降低了约37%和34%。图6（b）显示了RMSE(U)随路线中地点数目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）显示了算法访问结点数随着群体内用户数目N的变化情况，N越大，算法访问的结点数越多，其中DTG-BB算法比BSL算法的访问结点数减少了约65%。图7（b）中显示了算法的运行时间，与图7 （a）中访问结点数的趋势基本一致。图7（c）中显示了算法访问结点数随着路线中地点数目M的变化情况，随着M增加，算法访问的结点数呈指数次幂增长。图7（d）中显示了算法的运行时间，与图7（c）中访问结点数的趋势基本相同，与4.1节中的分析一致。综合可知：DTG-BB算法在各种参数设置下运行效率均高于BSL算法，DTG-BB算法具有较高的运行效率。

6 结束语

本文提出了一种新的路线搜索方法——群体用户局部分散式旅游路线搜索。该路线搜索方法可为群体用户搜索一条带有局部分散POI的且群体收益最大的访问路线。为了解决可行路线数目过多的问题，本文提出了一种分层处理POI的方法HPP，通过HPP构建DTG。本文方法减少了对可行路线的判别，实现了分级查询，从而提高了搜索最优路线的效率。实验用真实的数据集进行路线收益和搜索效率对比，验证了本文方法的有效性。实验表明，局部分散式策略能使群体用户获得较高整体收益，个体收益差异性较小，同时所提出的近似优化算法具有较好的收益效果与较高的搜索效率。

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]宋晓宇,闫玉奇,孙焕良,等.基于签到数据的群体旅游路线推荐[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年于中国科学院大学获得博士学位，现为沈阳建筑大学教授，主要研究领域为模式识别与图像处理，计算智能及数据挖掘等。发表学术论文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—），男，广西柳州人，沈阳建筑大学硕士研究生，主要研究领域为数据挖掘。

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年于东北大学获得博士学位，现为沈阳建筑大学教授，CCF高级会员，主要研究领域为空间数据库，数据挖掘等。发表学术论文50余篇，主持国家自然科学基金、国家科技支撑计划等多项科研项目。

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

许鸿斐（1987—），男，山西太原人，东北大学博士研究生，主要研究领域为空间数据库。

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