基于频繁序列挖掘的后续行程序列推荐

温彦 马立健 陈明

摘 要：个性化旅游发展迅速，已有方法主要集中在单个旅游产品推荐上，而旅游行程存在明显的序列性，并受到当前已有行程轨迹影响。因此，提出一种旅行中后续行程序列的推荐方法SeqRem，基于所有用户的行程序列挖掘频繁序列模式，并以此为依据利用最大点权独立集方法对用户的历史行程序列进行分割，以发现最优序列推荐内容。实验证明，SeqRem在单点推荐和序列推荐准确率与召回率均具有较好效果。

关键词：推荐系统;频繁序列挖掘;兴趣点;后续行程序列;数据挖掘

DOI：10. 11907/rjdk. 182099

中图分类号：TP301文献标识码：A文章编号：1672-7800（2019）003-0053-04

0 引言

随着人们生活水平提高，越来越多家庭注重旅游投入，追求优质的旅行体验，“主题旅游”、“定制旅游”等新型旅游模式应运而生。而当前旅游市场对游客的个性化需求满足远未达到用户预期。旅游产品推荐是当前个性化旅游服务的热门话题，根据推荐内容可分为旅游景点、旅游包、旅游线路推荐等，能够根据用户历史旅游记录分析用户特征和偏好，并推荐其可能感兴趣的产品。人们在旅游过程中往往存在如下需求：根据用户当前旅行状态实时推荐后续一系列行程，这在不同粒度的旅游过程中均存在，例如用户到达天安门后，需要有序浏览故宫博物院、国家博物馆、人民大会堂等景点，进入故宫后需要有序浏览故宫内相关景点。事实上，旅游行程存在明显的序列性，人们往往按照某种有序路线访问景点，但这一序列性又受到用户当前状态如已有行程、位置、时间以及用户对景点偏好的影响。用户已经访问的景点代表了其行程轨迹，也可以反映其当前所处位置，对后续景点访问会产生重要影响，因此本文主要关注如何推荐后续旅游行程序列并提出方法SeqRem。

1 相关工作

旅游点推荐根据产品内容不同可分为：①单个旅游产品推荐，主要包含与旅游的食、住、行、游、娱、购相关的单个产品，如文献[1]、文献[2]都是利用用户在旅游网站上传照片的标签信息挖掘其偏好相似性，并推荐其可能感兴趣的景点，文献[3]、文献[4]是基于旅游知识库的推荐系统;②旅行包推荐是对多种旅游产品打包后形成的包价产品进行推荐，如文献[5]、文献[6]利用改造的主题模型对游客与旅行包之间的关系建模并进行推荐，文献[7]采用隐语义分析模型（Latent Factor Model，LFM）和矩阵分解方法进行旅行包推荐;③旅游线路推荐主要为用户规划出一条或多条合理并符合用户兴趣与期望的旅游线路，主要采用图搜索方式满足预设成本、时间等需求[8-9]。

旅行推荐可以看作基于位置的兴趣点（Point of Interest，POI）推荐的一类特殊工作，根据用户历史轨迹推荐可能感兴趣的地理位置。由于位置推荐受到物理距离影响，因此大部分工作均将位置间的距离作为推荐的重要依据之一，此外，受到社会化推荐系统影响，也有不少工作考虑社会关系对推荐内容的作用[10- 11]。后续兴趣点推荐是近年来提出的对传统POI推荐的扩展，表示根据用户当前所在位置推荐后续可能位置，如文献[12]利用马尔科夫链建模后续关系，文献[13]利用一体化张量分解方法对访问时间和位置间的前后关系建模。在旅行系统中，基于当前位置推荐后续位置是常见需求，而且旅游行程体现出显著的序列性特点，即用户基于当前位置，更倾向于访问后续的n个地点。序列推荐能够有效规避用户因访问顺序不当带来的额外时间代价，提高旅游体验。当前已有工作主要集中在单点推荐上，缺乏对行程序列的考虑，本文旨在提供一定模型和方法实现后续序列的推荐。

2 问题定义

首先给出相关概念和问题定义。

证明：根据定义3及频繁项集的先验原理可知，若一个项集是频繁的，则其所有子集一定是频繁的，因此一个序列出现的概率必定小于等于其子序列出现的概率[14-15]。

根据性质1可知，序列S子序列的概率必定不小于其自身，会限制有意义的长序列出现，因此需根据序列长度对后续行程序列S的概率进行补偿，提高长序列的优先级。

定义4 长度补偿函数[c（F）]。对于序列S，其长度为[|S|]，其长度补偿函数[c（|S|）]需满足如下条件：

3 基于历史序列的后续序列概率模型

本文对来自国内多个大型旅游网站的游客签到数据进行分析，通过观察发现，绝大多数游客对同一景点的签到记录只有一次，且从照片时间关系来看，也都集中在同一时间段，这种现象也符合人们对旅行行为的一般认知，即相同景点只访问一次。这是本文的基本假设之一。

假设1：对于用户u，他访问过的所有地点在其行程中只出现一次。

对于目标函数式（1），首先应给出[P（S|H）]的计算方法。其中H是用户已有的所有行程序列，一方面，行程序列可能很长，带来相当程度的计算复杂性;另一方面，行程序列可以由多个行程片段组合，每个片段可以看作是一个关系较为紧密的景点群，而这些片段分别对后续行程产生相对独立的影响。因此有如下假设：

假设2：用户的历史行程序列H可以分割为多组频繁序列，而各个频繁序列之间是互相独立的。

根据該假设，可以对H进行重写。

式（2）计算需要解决3个问题：①如何根据所有用户的历史行程计算频繁序列;②如何将历史序列H重写为[{f1，f2，？，fm}]的形式，即如何对H进行分割;③对于所有可能访问的地点，其构成的序列数量呈指数级增长，如何对可能的序列数进行有效约减。

4 后续序列概率模型计算与序列推荐

4.1 频繁序列生成

生成频繁历史序列可采用序列模式挖掘（Sequential Pattern Mining，SPM）的方法，用于发现高于给定支持度且能保障频繁序列在历史记录中出现次序的序列。GSP是其中的经典算法[15]。本文频繁序列的定义是传统序列模式挖掘的特例：由于旅游过程中不同景点耗时不一致，很难给定一个固定的事件区间T，因此本文频繁序列挖掘中不考虑长短行程序列的差别，每一个用户的历史行程就是一个事件。为了消除长程频繁序列的影响，在频繁序列发现后引入序列间距指标，用于描述不同频繁序列中各项的平均位置间隔。

給定平均间距的阈值后，就可将长程频繁序列删去。

4.2 基于频繁序列的历史行程Top-K最优划分

考虑如何划分用户的历史行程，使其成为互相独立的频繁序列集合。根据式（2），应为每一个可能推荐的序列[S]构建其历史序列划分，但一方面[S]的数量呈指数级，另一方面对每一个[S]求划分也是指数级代价，因此实际上不可行。为此，引入频繁序列关联图概念，利用历史序列在所有频繁序列上的统计规律，对其进行最优划分。

频繁序列关联图的所有节点包括含用户u历史行程的所有行程节点[V1]和频繁序列[V2]。节点权值综合了频繁序列的支持度以及该序列在历史行程中的位置。寻找历史行程的最优划分，即对频繁序列关联图寻找满足如下条件的子节点集合：①有边连接的两个顶点不能同时选择，保障所有历史行程中的景点只访问一次;②节点的权值和最大，保障划分结果最频繁。

该问题可直接建模为最大点权独立集问题。对于某一个用户u，应当推荐使得P（S | H）最大的K个序列S，而该K个序列S可能分布在对H的多个不同划分中。因此，需要计算Top-K个最大点权独立集。该问题等价于求序列H的所有极大独立集，然后对各个独立集求权重和并排序。该问题是NP难问题，采用两种手段使其可计算：①缩小历史序列的窗口大小，越远的历史序列对后续影响越小，因此控制窗口大小可使计算量可控;②采用近似算法[16]。

4.3 推荐序列生成

5 实验

数据集来自国内多个大型旅游网站的游客签到数据，游客在网站上传旅行照片，照片中记录了旅行时间，从中可以抽取出游客的旅游行程。选择某热门旅游城市所有行程记录，去除其中只签到一次的用户，得到数据集，包括5 677个用户和33 231条签到记录。

由于本文推荐的是序列而非单个景点，而目前还未能查到推荐旅行行程序列的论文。因此进行如下两项实验：①针对单个后续景点的推荐实验，并与推荐后续POI的方法LORE进行比较[12];②后续行程序列的推荐实验，与单个地点推荐进行比较。采取的指标为推荐准确性和召回率，实验中的参数值为：频繁序列的支持度阈值为3，长度补偿函数为|S|。针对不同TOP-K的K值，实验结果如图1和图2所示。可以看出，对于后续单景点推荐，本文准确率和召回率与其它方法基本持平，对于序列推荐而言，准确率和召回率略低于单点推荐。

6 结语

本文提出一种在旅游过程中基于历史行程序列推荐后续行程序列的方法SeqRem，基于所有用户的行程序列挖掘频繁序列模式，并以此为依据利用最大点权独立集的方法对用户历史行程序列进行分割，同时发现最优序列推荐内容。实验证明，基于SeqRem的后续行程序列推荐方法具有较好效果。

参考文献：

[1] KOFLER C， CABALLERO L， MENENDEZ M， et al. Near2me： an authentic and personalized social media-based recommender for travel destinations[C]. The 3rd ACM SIGMM International Workshop on Social Media， 2011： 47-52.

[2] CAO L L， LUO J B， GALLAGHER A， et al. A worldwide tourism recommendation system based on geotagged web photos[C].The 35th International Conference on Acoustics， Speech and Signal Processing， 2010：2274-2277.

[3] 王显飞，陈梅，李小天. 基于约束的旅游推荐系统的研究与设计[J]. 计算机技术与发展，2012，22（2）：141-145.

[4] CLEMENTS M，SERDUKOV P， VRIES A D， et al. Using Flickr geotags to predict user travel behavior[C]. ACM Transactions on Information Systems， 2010：851-852.

[5] TAN C，LIU Q，CHEN E， et al. Object-oriented travel package recommendation[J]. ACM Transactions on Intelligent Systems & Technology （TIST）， 2014， 5（3）： 1-26.

[6] HE J， LIU H， XIONG H. Socotraveler： travel-package recommendations leveraging social influence of different relationship types[J]. Information & Management， 2016， 53（8）： 934-950.

[7] LIU Q， GE Y， LI Z M， et al. Personalized travel package recommendation[C]. The IEEE International Conference on Data Mining， 2011：407-416.

[8] KURASHIMA T， IWATA T， LRIE G， et al. Travel route recommendation using geotags in photo sharing sites[C]. The International Conference on Information and Knowledge Management， 2010：579-588.

[9] CHAKRABORTY B. Integrating awareness in user oriented route recommendation system[C]. The International Joint Conference on Neural Networks， 2012：1-5.

[10] YE M，YIN P，LEE W C， et al. Exploiting geographical influence for collaborative point-of-interest recommendation[C]. Proceedings of the 34th International ACM SIGIR Conference on Research and Development in Information Retrieval， 2011： 325-334.

[11] CHENG C，YANG H，KING I，et al. Fused matrix factorization with geographical and social influence in location-based social networks[C]. 26th AAAI Conference on Artificial Intelligence，2012，12： 17-23.

[12] ZHANG J D，CHOW C Y，LI Y. Lore： exploiting sequential influence for location recommendations[C]. Proceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems，2014：103-112.

[13] ZHAO S， ZHAO T， YANG H， et al. Stellar： spatial-temporal latent ranking for successive point-of-interest recommendation[C]. 30th AAAI Conference on Artificial Intelligence， 2016：315-322.

[14] SRIKANT R，AGRAWAL R. Mining sequential patterns： generalizations and performance improvements[C]. 5th International Conference on Extending Database Technology， 1996：3-17.

[15] TAN P N， MICHAEL S， VIPIN K. 數据挖掘导论[M]. 范明，范宏建，译. 北京：人民邮电出版社，2011.

[16] LAWLER E L， LENSTRA J K， RINNOOY KAN A H G. Generating all maximal independent sets： NP-hardness and polynomial-time algorithms[J]. SIAM Journal on Computing， 1980， 9（3）： 558-565.

（责任编辑：何 丽）