基于动态转移图的时间敏感的旅游路线推荐方法

孙焕良， 崔 晨， 刘俊岭

(沈阳建筑大学 信息与控制工程学院 辽宁 沈阳 110015)

基于动态转移图的时间敏感的旅游路线推荐方法

孙焕良， 崔 晨， 刘俊岭

(沈阳建筑大学 信息与控制工程学院 辽宁 沈阳 110015)

提出了基于动态转移图的时间敏感的旅游路线推荐方法，构建一种基于层次聚类的动态转移图的模式方法，设计了流行序列异常的去除方法，建立稳定的模式规律.模式规律为用户准确地推荐适合其出行时间的最佳旅游线路.通过真实数据的实验验证，与现有工作相比，用户的收益提高了10%以上，验证了提出方法的有效性.

路线推荐； 时间敏感； 转移图模型； 签到数据

0 引言

随着互联网和移动设备的快速发展，越来越多的用户将旅行信息分享到在线社交平台上，如Foursquare或Gowalla.它们收集了大量反映用户位置与停留信息的数据.利用历史用户的偏好和习惯进行旅游路线推荐，成为目前旅游路线推荐的研究热点.基于签到数据的路线推荐主要包括：基于地点流行度的路线推荐[1]、结合用户偏好的路线搜索与推荐[2-4]、条件受限的路线推荐[4]等.

利用签到数据进行路线推荐的做法是将用户的签到数据生成路线转移图.图中结点表示景点，边表示景点之间的转移关系，景点的签到次数表示景点流行度，边上的权重表示边的流行度.现有方法将所有的数据生成一个路线转移图，在图中进行满足条件的路线查询[4-5].此类处理方法忽略了季节变化、节假日变化对景点流行度及转移关系的影响.

现有的时间敏感路线推荐考虑各景点一天中最佳访问时间，进行路线推荐[6-7]，而本文的研究是按全年范围内以星期为最小单位的时间敏感路线推荐.方法如图1所示.由图1可知，本文采用层次聚类算法进行概化处理对签到数据中记录少的景点进行聚合.根据景点流行度序列得出景点流行规律和转移规律，对规律的学习和划分以获取稳定合理的转移图模式集.结合转移图模式集的时间范围属性进行路线推荐实现了时间敏感的旅游路线推荐，有效解决了出行时间不同但路线唯一的路线推荐问题.

1 相关工作

依据所用的数据类型可以将路线的推荐分为3类：基于GPS轨迹数据的旅游路线推荐[2,8]、基于签到记录的旅游路线的推荐[4,8-10]和基于用户分享的带有地理位置信息的照片的旅游路线推荐[11-14].

文献[15]利用景点集合、用户访问景点的先后次序集合以及照片数据，建立用户的旅行转移序列，进而进行路线推荐.文献[16]从不确定轨迹中构建多条有序轨迹并通过对指定地点集的挖掘得出最流行的路线.文献[17]运用多样化的排序算法将推荐的路线进行排序，目的是使推荐的路线包含更多的景点，使推荐的路线之间差异性更大.以上工作根据现有的数据挖掘流行度最高的路线对用户进行推荐，未考虑路线是否符合用户偏好这一重要因素.

文献[18-20]虽然将用户对于不同类别景点的偏好考虑在路线推荐过程中，但其中并没有考虑景点流行度的变化，现实生活中景点的流行度是随着时间的推移而变化的.本文利用签到数据实时性和包含地点类别信息的特点，依据景点在一年中流行度的变化建立动态转移图模式集，为用户推荐适合其出行时间的最佳路线.

2 问题定义

图2左侧是根据一年提取出的转移图的示例，右侧为转移图中景点的类别和流行度的集合.

定义1 时间段T的景点模式. 给定时间段T，景点模式定义为P(T)=〈v1, v2, …, vi, …, vn〉.n代表结点总数.景点流行度计算方法为

(1)

式中：argc∈cmax(vj.w:vj.c=vi.c)为取出vi所属类别景点集中最大频度的计算，此计算方法与文献[12]提出的方法一致，优势在于更真实准确地反馈出带有类别的景点流行度.

定义2 时间段T的转移图模式.给定时间段T，转移图模式定义为GT=〈VT,ET〉.

定义3 时间敏感的转移图模式集. 时间敏感的转移图模式集定义为G=〈G1,G2,…,Gn〉，如图3所示.图3的模式集是将一年的数据通过相似度的计算和层次聚类的聚合生成的转移图模式集合.

图2 转移图示例

(a)转移图模式P1(b)转移图模式P2

定义4 景点流行度序列.给定景点v，景点流行度序列定义为

定义5 景点相似性度量.给定时段T和时段T′，景点模式P(T)和景点模式P(T′)的相似度计算方法为

(2)

由于景点模式与词频向量相似，具有稀疏性，度量的要求为关注两个模式相同的景点，以及相同景点出现的频度，所以采用文本相似度中的余弦相似度为适宜.

本文采用社交网站Foursquare的位置分类方法对景点的类别进行描述，共分为8个类别，分别为：C={娱乐中心(c1),商场(c2),美食(c3),夜店(c4),旅行(c5),教育(c6),公园(c7),建筑(c8)}.

定义7 用户的旅游路线查询. 旅游路线查询表示为Q=〈N,T,PV(u)〉,N代表用户设定的访问景点的个数，T为用户出行的时间.

定义8 用户收益. 给定用户u、路线景点总数N和偏好集合，用户收益定义为Profit(u).计算方法为

(3)

用户收益代表用户u对路线的满意度,i表示路线中的第i个景点.

问题1 时间敏感的路线搜索.给定查询Q=〈N,T,PV(u)〉，转移图的模式集G，用户的偏好PV(u)，利用时间敏感的路线推荐方法推荐一条适合在时间T出行且收益最大的旅游路线R.

现设用户的初始查询是Q=〈3,T,PV(u)=〈0.3, 0.5, 0.2〉〉，在生成的转移图模式集中，T所在的模式为图3中的模式P1.通过计算发现用户的最大收益值中包含两条路线，分别是(v1,v2,v6)和(v6,v5,v4)，但前者边的流行度更高，所以模式P1的最佳路线RP1.road为(v1,v2,v6)，最佳路线的收益值RP1.value为0.54.

3 转移图模式构建

3.1 构建模型

模型构建的流程如图4所示，模型分为数据预处理、景点模式建立、转移图模式建立和路线的推荐4部分.本文首先将基于地理信息的对象活动的相关数据采用规范的概化处理，得到符合现实生活的数据信息，如步骤①所示，为数据的预处理部分.

步骤②根据处理后的数据依据景点的数目，采用等深分箱技术进行划分，统计每箱中景点出现的频度，根据现实生活中主观认为时间以星期为单位进行划分，构建景点模式集合和景点流行度序列集合.由于每个星期都包含工作日和休息日，故排除了二者对于模式集生成的干扰.步骤③依据景点模式统计所有景点的流行度的变化情况，建立景点流行序列.步骤④将景点流行序列进行异常点的处理操作，得到稳定、均化的流行序列，依据相似性检验及层次聚类算法得到最终的景点模式.其中去除异常是为了让景点流行序列均匀平滑，相似性检验是为了去除相邻模式之间相似性过大带来的相似问题.步骤⑤由景点模式与其时间范围的转移关系得到转移图模式.最后，步骤⑥通过转移图模式进行路线的评分与推荐.

由于区域对象流动的随机性造成了景点流行度的异常，如何生成合理稳定的序列、异常点的处理和模式之间相似度的计算，成为本文研究如何生成高精度的转移图模式的重点.

图4 动态转移图的时间敏感推荐模型图

3.2 景点模式的处理

景点模式根据自然星期划分建立，但模式集中景点的流行度并不稳定，规律性不强，这使景点模式的处理成为必然.本文首先定位异常点，其次主要采用景点流行度序列局部去除异常点和均值替代法对异常的流行点进行处理.结合文本相似度的层次聚类算法，对景点模式集中相似的两个连续模式聚合，目的是使景点模式集中所有连续的景点模式之间互不相似.

景点模式集中包含所有景点各星期的流行度，所以景点流行序列的构建和处理成为去除景点模式集中异常流行点的关键.未经处理的流行度序列如图5所示.

图5 初始流行序列

由图5可知，初始模式生成的景点流行序列大多是难以发现其中规律的，但可以隐约看出在春季和冬季是不流行的，序列大体保持在一年中最低水平.流行序列中的异常点影响着稳定景点序列的生成，这使得去除异常点成为稳定景点序列生成的关键.

3.2.1 定位异常点 本文景点流行序列中的异常点是指在稳定的景点流行度区间夹杂着流行度变化过大的一个时间段，此处的流行度超出稳定序列设定的范围，由于它的存在导致了稳定流行度区间出现了较大的波动，因此设定为异常点.本文提出一种依据流行度波动情况有效定位局部异常点的方法，如算法1所示.

算法1 定位异常点

Input:所有景点的流行度序列集合Sn；景点集合V；

Output:景点异常点标记集合Result，景点稳定聚簇集合Cluster；

1) For V中的景点viDo

2) For S(vi)的时间段TjDo

3) Find(vi, tj)//找到Si.max、Si.min中流行度的最大值max，最小值min

4) 计算最大值与最小值的差Si.len=max-min

6) For S(vi)的时间段TkDo

7) Result[i][k]=FindOutlier(j, flu(Si), Si, cluster[i]);//确定异常点位置

8) Cluster[i]=FindCluster(i, flu(Si), Si);//稳定聚簇

9) Delete(Si. k)//删除j的流行程度

3.2.2 异常点的处理 异常点的流行度经过算法1的处理已被删除，但异常点留下的空缺使得各景点的流行序列曲线出现断裂之处，所以要对此进行处理.本文采用现有数据挖掘知识中数据清洗技术的均值替代法对空缺之处进行填补.如算法2所示，

算法2 异常点的处理

Input: Result为存储异常点的链表；Cluster为存储景点稳定序列的链表；景点的流行度序列集合Sn；景点集合V；

Output:处理后的景点流行度的序列集合Sn；

1) For V中的景点viDo //遍历所有景点

2) For Sn中Series(vi)的时间段TjDo

3) IF(Result[i][j] == 1) THEN //找寻异常标记

4) clusternum = cluster[j]

5) For Sn中Series(vi)的时间段TkDo

6) IF(cluster[k] == clusternum&&Result[i][k]!=1) THEN

7) sum = sum+Si.k.w//计算相同聚簇里的流行度总和

8) Update(Si.k, avg(sum));//得到稳定序列内的流行程度的平均值,更新S

9) Else continue.

算法2的步骤1)～4)是对所有景点的流行序列进行异常点处理的操作.检验景点在当前时间是否为异常点标记，如果是,则将所属稳定聚簇记录在clusternum中.步骤5)～9)首先是在该景点的所有时间点中发现与clusternum相同的稳定聚簇的值，即属于同一稳定聚簇，其次对所有该聚簇的流行度进行求平均值的操作，求和及求平均值时都不考虑异常点的影响.用均值代替异常点，并更新景点流行度序列集合Sn.启用异常处理之后的流动序列曲线与处理之前的对比如图6所示.

图6 异常处理的流行序列

图6中的散点为异常点，反映异常点处理前后的对比.本文采用聚簇均值替代的方法，将景点的稳定流行聚簇内包含的时间段的流行度的值，用聚簇内流行度的均值进行替换，使得每个聚簇都能成为绝对稳定的聚簇，流行序列曲线成为阶梯状的变化，反映景点在各个时间段内流行度的变化，最终的景点流行序列如图7所示.

如图7，景点的流行度是随时间变化的序列，每条水平的线段都代表稳定的流行聚簇.由于单周的流行程度不具有代表性，故稳定流行序列的长度至少为2.

3.3 转移图模式的构建

图7 处理后的流行序列

构建转移图模式的前提是相似的景点模式.由于异常点处理后的景点模式之间存在相似的可能，相似且相邻的模式可能推荐相同或相似的路线，所以本文通过文本相似度的计算方法进行模式之间相似度的计算.文本相似度的计算方法如本文定义5所示.结合文本相似度采用层次聚类的方法将相似度矩阵中满足聚合要求且相邻的模式进行聚合，利用景点模式中景点的转移关系建立转移图模式.具体的转移图生成原则会在4.1节的转移图生成过程中详细说明.模式的生成如算法3所示.

算法3 转移图模式生成

Input: 根据Sn得到的景点模式P;

Output:转移图模式集G；

1) While(Sim Rt.max()≥thr) Do//相似度矩阵中相似度的最大值不小于阈值

2) For景点模式P中的景点模式PkDo

3) Sim Rt= Sim(Pk, P(k+1), k, k+1);//生成相似度矩阵，不相邻的模式相似度为0

4) max= Sim Rt.max;//得到相似度矩阵的最大值

5) location= Sim Rt.location;//确定最大值位置

6) Cluster(location);

7) Update(P);//更新P景点模式集合

8) For景点模式P中的景点模式PiDo

9) Gi=creategraph(Pi);//每个景点模式生成转移图

算法3的步骤1)设定条件，景点模式中相似度矩阵的最大值超过阈值则聚合条件满足，景点模式发生聚合.步骤2)～7)为提取景点模式，计算景点模式之间的相似度生成相似度矩阵，并依据层次聚类算法进行聚合.步骤8)～9)是利用聚合后的景点模式，依据转移图生成规则，分别建立转移图.

3.4 基于动态转移图的时间敏感的旅游路线推荐

基于动态转移图的时间敏感的旅游路线推荐方法是根据用户给定的出行时间和预计访问的景点数目，将最佳收益的路线为用户推荐.具体过程如算法4所示.

算法4 基于动态转移图的时间敏感的旅游路线推荐方法

Input:出行用户的偏好PV，用户预计的出行时间t，用户预计访问景点总数N；转移图模式集合G，景点集合V；

Output:对象R，存储最大收益路线R.road以及R.profit用户最大收益值；

1) 初始化栈W，路线存储R，路线数组A[N]，收益存储Profit，存储邻接表list

4) list.i.add(j); //建立邻接表

5) For景点集合V中所有景点viDo

6) A[N]=TRDG(vi,N, t, list); //得到vi为起点的最佳路线

7) W.push(A)

8) For(k = 0;k

9) Profit = Profit + A[k].c*p(ui,c)

10) IF(Profit>R.profit)

11) R.profit =Profit

12) R.road=A

13) ELSE W.pop(A)

算法4描述了基于动态转移图的时间敏感的旅游路线推荐算法的流程.步骤1)初始化路线搜索.步骤2)～4)建立邻接表，提升路线查询速度.步骤5)～13)根据邻接表进行基于动态转移图的时间敏感的旅游路线推荐算法的路线搜索，将起始结点vi的最佳路线分别入栈，计算路线的收益，并与当前最大收益路线进行比较，如果比当前的收益大，便将R进行替换，否则将路线出栈，继续执行基于动态转移图的时间敏感的旅游路线推荐算法，直到邻接表中的所有结点都已查询完毕.基于动态转移图的时间敏感的旅游路线推荐方法是按照模式的规模搜索最佳路线，并非全年数据，因此效率大大提高.

4 实验评价

本文提出并实现基于动态转移图的时间敏感的旅游路线推荐方法(time-sensitive route recommendation based on dynamic transfer graph,TRDG)的算法，并与以下3种算法进行了比较，分别是基于月份的时间敏感的路线推荐(month time-sensitive route recommendation, MTR)、基于季度的时间敏感的路线推荐(season time-sensitive route recommendation, STR)和文献[18]的原始的结合用户偏好的路线推荐(initial preference route recommendation, IPR).

4.1 实验数据

实验选取Gowalla社交网站的数据集中美国旧金山市北部从2009年11月到2010年10月的签到记录.通过概化处理和统计去除一年中景点平均一个星期出现次数小于5次的景点和相应记录.根据景点模式包含的景点和所属时段，如果同一用户的连续签到记录的时间间隔是大于1小时且小于6小时，则两点之间生成一条有向边，并对边出现的频度进行统计生成转移图.

4.2 推荐路线的评分分析与对比

本节将从访问地点数目N的变化收益效果和出行时间不同的收益效果对TRDG算法、MTR、STR和IPR进行实验对比，验证TRDG算法的有效性和优越性.

4.2.1 访问地点数目变化的收益效果对比 图8(a)是在用户偏好相同，3月1日出行的条件下，profit随着访问地点数目N的变化.每种算法的profit都随着访问地点数目N的增加而增加，表明地点数目越大，用户的收益越高.其中，STR和IPR推荐效果较差，MTR稍好，TRDG的收益比其他3种算法高15%左右.图8b是profit在用户偏好相同，9月1日出行的条件下，随着访问地点数目N的变化.与图8a类似，MTR和STR推荐效果较差， IPR稍好，TRDG的收益比其他3种算法高25%左右.

综上所述，在用户偏好确定出行时间相同的情况下，验证访问地点数目的变化时，在用户收益方面，TRDG比其他3种方法有着很大的优势.

4.2.2 出行时间不同的收益效果对比 图9a是在相同用户访问景点个数为3的条件下，在3月1日、6月1日、9月1日和12月1日，4个不同月份，不同季节的出行时间，采用4种算法进行用户收益的比较.其中，STR和IPR推荐效果依然较差，比MTR收益高10%.

图8 访问地点数目N对profit的影响

图9 出行日期对profit的影响

图9b是在相同用户访问景点个数为4的条件下，在与图9a同样的4个出行时间，采用4种算法进行用户收益的比较.与图9a类似，TRDG的用户收益比其他3种路线推荐算法的收益至少高15%.

综上所述，在用户偏好确定、访问地点数目相同的情况下，验证访问出行时间的变化，在用户收益方面，TRDG算法比其他3种方法有很大优势.

5 结论

本文提出了一种新的路线推荐方法：基于动态转移图的时间敏感的旅游路线推荐.根据自然星期划分法得到了景点模式，结合相似度采用层次聚类方法进行模式的聚合.实验对算法的有效性和用户的收益进行了分析比较，验证了该问题的正确性和算法的优越性.

[1] BAO J, ZHENG Y, WILKIE D, et al. Recommendations in location-based social networks: a survey[J]. Geoinformatica, 2015, 19(3): 525-565.

[2] BAO J, ZHENG Y, 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, 2012: 199-208.

[3] FUNKE S, STORANDT S. Personalized route planning in road networks[C]//Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems. Seattle, 2015: 45.

[4] LU E H C, CHEN C Y, TSENG V S. Personalized trip recommendation with multiple constraints by mining user check-in behaviors[C]//Proceedings of the 20th International Conference on Advances in Geographic Information Systems. Redondo Beach, 2012: 209-218.

[5] WANG S, LIN W, YANG Y, et al. Efficient route planning on public transportation networks: a labelling approach[C]//Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. Melbourne, 2015: 967-982.

[6] HSIEH H P, LI C T, LIN S D. Exploiting large-scale check-in data to recommend time-sensitive routes[C]//Proceedings of the ACM SIGKDD International Workshop on Urban Computing. Beijing, 2012: 55-62.

[7] YUAN Q, CONG G, MA Z, et al. Time-aware point-of-interest recommendation[C]//Proceedings of the 36th international ACM SIGIR Conference on Research and Development in Information Retrieval. Dublin, 2013: 363-372.

[8] ZHENG Y, XIE X. Learning travel recommendations from user-generated GPS traces[J]. ACM transactions on intelligent systems and technology, 2011, 2(1): 389-396.

[9] LIAN D, XIE X. Learning location naming from user check-in histories[C]//Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Chicago, 2011: 112-121.

[10]HSIEH H P, LI C T. Composing traveling paths from location-based services[C]//Proceedings of the 6th International AAAI Conference on Weblogs and Social Media.Dublin, 2012.

[11]LIM K H. Recommending tours and places-of-interest based on user interests from geo-tagged photos[C]//Proceedings of the 2015 ACM SIGMOD on PhD Symposium. Melbourne, 2015: 33-38.

[12]MAJID A, CHEN L, MIRZA H T, et al. Mining context-aware significant travel sequences from geo-tagged social media[C]//Proceedings of the AAAI. Toronto, 2012: 2443-2444.

[13]KURASHIMA T, IWATA T, IRIE G, et al. Travel route recommendation using geotagged photos[J]. Knowledge and information systems, 2013, 37(1): 37-60.

[14]CAO X, CHEN L, CONG G, et al. Keyword-aware optimal route search[J]. Proceedings of the VLDB endowment, 2012, 5(11): 1136-1147.

[15]MASTHOFF J. Group recommender systems: combining individual models[M].New York:Springer,2011: 677-702.

[16]WEI L Y, ZHENG Y, PENG W C. Constructing popular routes from uncertain trajectories[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Beijing, 2012: 195-203.

[17]YIN Z, CAO L, HAN J, et al. Diversified trajectory pattern ranking in geo-tagged social media[C]//IEEE Intermational Conference on Data Mining. Vancouver, 2011: 980-991.

[18]DAI J, YANG B, GUO C, et al. Personalized route recommendation using big trajectory data[C]//Data Engineering (ICDE), IEEE International Conference on Data Engineering. Atlantic, 2015: 543-554.

[19]GARCIA I, PAJARES S, SEBASTIA L, et al. Preference elicitation techniques for group recommender systems[J]. Information sciences, 2012, 189(7): 155-175.

[20]宋晓宇,许鸿斐,孙焕良,等. 基于签到数据的短时间体验式路线搜索[J]. 计算机学报，2013，36(8)：1693-1703.

(责任编辑：王浩毅)

Time-sensitive Travel Route Recommendation Method Based on Dynamic Transfer Graph

SUN Huanliang, CUI Chen, LIU Junling

(SchoolofInformationandControlEngineering,ShenyangJianzhuUniversity,Shenyang110015,China)

The time-sensitive travel route recommendation methods were put forward based on dynamic transfer graph. A pattern-building method of dynamic transfer graphs was proposed based on hierarchy clustering and designs methods to remove outliers with popularity sequence to construct stable pattern rules. The use of pattern rules could accurately recommend the best travel routes that were most suitable for travel time for the user. With the verification of the real data, the profit of users increased by more than 10% compared with the existing work, which indicated the effectiveness of this method.

route recommendation; time-sensitive; transfer graph pattern; check-in data

2016-09-28

国家自然科学基金项目(61070024,61272180).

孙焕良(1969—)，男，黑龙江望奎人，教授，主要从事空间数据库和数据挖掘研究,E-mail:sunhl@sjzu.edu.cn.

TP311

A

1671-6841(2017)01-0050-08

10.13705/j.issn.1671-6841.2016031