基于深度表示模型的旅游路线推荐算法研究

梁栋屹+陶宏曜+刘兴旺

摘要：针对现有旅游路线推荐算法在实际应用中景点标签缺失、依赖用户评分等缺陷，提出一种基于深度表示模型的旅游路线推荐算法。根据时空轨迹隐含的位置顺序和时间中的用户移动模式，建立深度表示模型对每个用户的时空间序列训练特征向量，并用Kmeans算法对训练结果进行聚类。为验证实验结果，将用户的移动模式应用到旅游路线推荐上，选择使用Gowalla上的签到数据集进行检测。实验结果表明，包含诸如“购物”，“夜生活”等标签的移动轨迹具备推荐价值。

关键词：社交网络；深度表示模型；Kmeans聚类；用户移动模式；训练特征向量

DOIDOI：10.11907/rjdk.171932

中图分类号：TP319

文献标识码：A 文章编号：1672-7800（2017）012-0158-04

Abstract：In currently， there are some weakness like lacking of feature spot label and the large distance between different places for the travel route recommendation algorithm. In this paper， we analyze the sequence of locations and time which hide the user moving model and create a depth representation model to train the feature vector about the space-time list. At last， we select the Kmeans algorithm to cluster the value of feature. To test the result of experiment and apply it in the recommendation of travel route， I select to use the check-in data list Gowalla as the resource。According to the result， some moving route including shopping or night life label have the value of recommendation.

Key Words：social network； depth representation model； Kmeans clustering； user moving model； training feature vector

0 引言

随着移动设备和基于位置的服务广泛应用，用户签到数据的获取更加方便且成本大大降低，人们在通过微信朋友圈、QQ空间等社交网络平台分享图片、感想的同时，也产生了时空签到数据。这些数据至少具备3种属性：用户ID、签到时间与经纬度，这促使了基于地理位置的移动社交网络（LBSN）迅猛发展，这些个体行为轨迹数据为研究用户移动模式以及探究其内在规律提供了机会。例如收集一个用户在一定时间内的时空数据连线就可得到一条时空轨迹，而时空轨迹在城市智能化发展中扮演着越来越重要的角色，2012年，Science就发现了这个现象[1]。

在LBSN网站中，可由用户的一系列签到点绘制出轨迹，这些轨迹同时具有地理信息和社交信息属性，是许多分析用户移动轨迹研究的基础。Tang[3]等提出根据海量用户的 GPS历史轨迹来挖掘旅途中目标一致的同伴。Backstrom[4]等通过分析 Facebook上用户间的社会关系来预测好友的地理位置信息。Wang[6]等提出基于朋友关系向用户推荐其可能感兴趣的地点算法FBCA，该算法将朋友关系应用于轨迹聚类，很好地利用了社交网络中的社交属性。Zheng[7]提出一个基于社交网络位置推荐系统，但实际生活中，人们的活动通常会受到与用户关系密切或其他人言行的影响，因此在研究社交轨迹聚类时必须考虑其他用户对轨迹的评价，这里引入用户爱好相似度评估矩阵。

随着旅游业的蓬勃发展，出现了许多旅游推荐算法，而大多数算法都是依靠用户对于景点与旅游路线的评分信息来匹配“相似用户”，实现旅游推荐的。例如AhasR[8]等以爱沙尼亚为例，对旅客的旅游活动进行了问卷调查，并分析了其偏好的旅游目的地信息；麻风梅[9]等通过在线访谈的方式获取用户旅游需求，以计算游客相似兴趣度的方法推荐景点；王显飞[11]等通过会话的方式了解用户需求，以筛选旅游知识库的方式产生景点和酒店的推荐。基于用户调查与评分的方法虽然能有效地为用户推荐旅游信息，但在繁忙的网络社会中，显式评分信息只会越来越少，而签到操作和历史记录中包含的隐式路线流行度将成为重要的推荐依据。

为解决用户评分信息的缺失，不同于传统的基于用户评分推荐，本文提出基于Gowalla签到数据集建立位置时间序列，通过一种新的深度表示模型训练特征向量，从结果中探讨用户隐含的移动模式价值。通过kmeans聚类算法和KNN分类算法对位置时间序列特征向量进行处理，提取流行移动模式帮助旅客选择路线。

1 数据预处理

首先介绍本文所用的签到数据集属性，并进行预处理操作。

1.1 数据属性

Gowalla是一个基于位置的社交网络，网站用户可以分享签到数据。这里收录了共6 442 890条用戶签到数据，时间为2009年2月到2010年10月。每条签到数据包含5种属性，分别是用户编号、经度、纬度、时间和地点编号。具体数据记录见表1。

3 实验分析

利用Gowalla数据集进行测评，通过深度表示模型探索用户的移动模式，并用模拟游客数据验证用户移动模式对旅游路线推荐的效果。endprint

3.1 用户移动模式

由于训练所得的位置时间序列向量很难直观显示出用户隐含的移动模式，因此选择使用Kmeans聚类算法对数据特征进行归纳。Kmeans算法作为最基础的聚类算法之一，不需要从外部确定类，完全根据训练数据的特征进行聚类，属于无监督学习，非常适合对实验所得的无标签、杂乱的数据进行处理。但其缺陷是需要人为确定簇的数量，所以选择两份不同的向量集分别测试簇总数为5、10、15三种情况，见表2，这里选取簇总数为10的情况介绍。

要将向量特征聚类，需要计算向量间的相似度，即数学上的距离。一般有基于余弦距离和欧几里得距离公式两种方法选择，这里使用计算余弦值的公式：

sim（si，sj）=cosθ=v（si）*v（sj）‖v（si）‖‖v（sj）‖（5）

通过聚类算法，具备相似特征的向量聚集在一个簇中，易于发现用户隐患的移动模式。首先观察周末和工作日人们移动模式的变化，发现差异较大，见图3。为减小误差，按工作日和周末分类后进行训练。

根据文献[14]对地点进行分类，见表3，完成后抽取距离簇中心最近的几个用户轨迹，根据地点ID和经纬度数据，选择具备清晰标签的轨迹，且忽略掉簇中心为 “公路-公路”，“家-上班”的簇，最后得到含有娱乐标签的记录，见表4、表5。

观察对比表4和表5，可以发现休息的用户移动模式明显包含更多娱乐标签，工作日的移动模式在经过筛选后仍包含大量与旅游路线推荐无关的移动模式，例如：“公路—公路”。所以选择基于休息日的聚类结果作为旅游路线推荐的依据。

根据表4，可以直观展现用户移动模式的类型，如簇二，最流行的5种移动模式都包含了夜生活的标签，可以证明这类移动轨迹的目的都是享受夜生活服务，类似于这种具备明显特征属性的轨迹，可以为旅游路线推荐提供有价值的信息。

3.2 推荐效果测试

通过聚类将具备相似特征的向量聚集在一起，且通过少量位置标签对用户移动轨迹进行分类，有利于KNN（最近邻居）分类算法的实现，这需要人为设定类别并指定k个邻近点作为分类依据，但不需要前期训练，时间复杂度为O（n），反馈速度较块。

假设有一名旅客在某地进行签到，并想获得下一步行动指引，这种行为类似于一条用户轨迹数据缺乏第二个位置点，可以直接为旅客确定下一个目的地的属性，从而得到对应的移动轨迹向量，然后从对应的用户轨迹特征向量簇中选择斜率相似的向量。例如，旅客的第一次签到在带有娱乐标签的位置点，将游客可能感兴趣的类型分别设置为下一个目标并训练特征向量，最后将结果与聚类集合比较，通过KNN算法对位置时间序列向量进行分类，会发现下一个目标含有饭店标签属性的例子可能性最高。由此发现旅客潜在的移动轨迹，将当地人流行的休闲移动轨迹推荐给游客。实验结果表明，推荐路线目标间距离较近，且景点标签描述准确率高，对旅游路线推荐有一定价值。

表6列出了当地签到人数最多的三簇休闲娱乐移动模式。表7是针对旅客在不同类型地点进行第一次签到后，根据表6的移动模式为下一个目的地的出现概率进行的预测。

4 结语

本文尝试用一种新的深度表示模型对用户签到轨迹进行特征值训练，并利用训练所得的移动模式特征值聚类作为旅游路线推荐的依据。聚类结果显示：同种类型的用户移动轨迹如包含夜生活标签的轨迹，向量间相似度极高，显示了具备该标签的地点在当地的流行度，并且挖掘出了原本没有标记的同类景点。此外在用户路线推荐时，很容易发现与当地流行轨迹向量斜率相似的新的轨迹，基于当地实际情况的路线推荐在效率与可行性上也有所提升。

参考文献：

[1] COOK D， GRADY M， HARE G. How smart is your home？[J].Science，2012，335（6076）：1579-1581.

[2] 余凯，贾磊，陈雨强，等.深度学习的昨天、今天和明天[J].计算机研究与发展，2013，50（9）：1799-1804.

[3] TANG LUAN，ZHENG YU，YUAN JING，et al.On discovery of traveling companions from streaming trajectories[C].Proceedings of the 28th IEEE International Conference on Data Engineering，2012：186-197.

[4] BACKSTROM L，SUN E，MARLOW C.Find me if you can：improving geographical prediction with social and spatial proximity[C].Proceedings of the Conference on WWW，2010：61-70.

[5] 陈勐，禹晓辉，刘洋.基于深度表示模型的移动模式挖掘[J].计算机应用，2016（1）：33-38.

[6] WANG HAO，TERROVITIS M，MAMOULIS N.Location recommendation in location-based social networks using user check-in data[C].Proceedings of the 21st ACM SIGSPATIAL International Conference on Advances in GIS，2013：364-373.

[7] ZHENG Y，XIE X.Learning travel recommendations from user-generated GPS traces[J].ACM TIST，2011，2（1）：2-3.

[8] AHAS R，ASAS A，ROOSE A，et al.Evaluating Passive Mobile Positioning data for tourism surveys：an estonianease study[J].Tourism Management，2007，3（4）：l-18

[9] 麻風梅.基于游客综合兴趣度的旅游景点推荐[J].测绘与空间地理信息，2014（3）：56-58.

[10] 方潇，刘晓寒，柴永平，等.一种基于协同过滤的旅游行程推荐算法[J].地理空间信息，2016（7）：53-56.

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

[12] 胡振，傅昆，张长水.基于深度学习的作曲家分类问题[J].计算机研究与发展，2014，51（9）：1945-1954.

[13] 王瑞琴，蒋云良，李一啸，等.一种基于多元社交信任的协同过滤推荐算法[J].计算机研究与发展，2016（6）：1389-1399.

[14] YUAN J， ZHENG Y， XIE X. Discovering regions of different functions in a city using human mobility and POIs[C].SIGKDD 2012：Proceeding of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York：ACM，2012：186-194.

（责任编辑：杜能钢）endprint