论文笔记--Enhancing Personalized Trip Recommendation with Attractive Routes

作者认为现在大部分的兴趣点推荐算法大多只根据POIs本身的受欢迎程度来进行推荐。但事实上POIs之间的一些路线也有吸引力。在这篇论文中作者提出了同时使用POIs和Attractive Route (AR)的方法来个性化旅游路线推荐。论文主要解决了三个问题(1)如何发现有AR? (2) 如何对AR的评分和计算偏好? (3) 如何通过AR来提升个性化的旅行推荐?

Problem Definition

问题提出

如下图，每个大写字母代表一个POI，括号中的数字表示该POI的受欢迎程度。每条路线上的数字表示它的受欢迎程度。在不依赖于POI的情况下，该路线对游客有自己的吸引力(比如商务活动)。传统的旅游推荐只考虑受欢迎程度高的POIs，推荐 路线，但是 路线是有一个高的受欢迎度，最后很可能 路线能带来更好的体验。

系统设置和概念说明

Definition 1: Travel Graph

对于有n个POIs的区域构造一个带权有向图

其中 表示n个POIs，每条 表示POIs之间的路径，边的权值表示路线平均花费时间。

Definition 2: Preference

每个用户u和POI v都有一个z维的偏好 ，表示用户或POI在第i类的偏好。​​​​​​​ 通过访问各类POI的数目比例计算。

Definition 3: Preference Score

用来表示用户u对POI v 之间的匹配度，通过​​​​​​​ 的余弦相似度获得​​​​​​​ 。

Definition 4: Trip

一个trip通常有一个或者多个POI组成，可以表示为 ，更具trip中包含的POIs数目可以叫做s-trip。用户u在POI v呆的时间可以用 表示（通过历史记录计算），道路 上的时间用​​​​​​​ 表示（通过距离和用户平均速度计算）。所以一个trip花费的时间可以通过下面公式计算​​​​​​​ ​​​​​​​ 计算。

Definition 5: Popularity

表示的是一段路或者一个POI的受欢迎程度。对于POI v， 通过来访数量来计算，对于道路 e，​​​​​​​ 通过道路的旅行流量计算。

Definition 6: Attractive Route (AR)

吸引路线AR定义为一个人气很高的POI的传入路线，它的人气占据了该POI大部分的人气，用符号 表示。

对访问AR的用户进行分析，将500个访问AR的用户的偏好​​​​​​​ 投影到3个类别上，可视化如下图左边，这些用户的绝大多数偏好聚在一起。

然后分析用户在这些路线上的出行时间，喜欢AR的用户会花更多的时间在这上面，如下图右边。所以选择有吸引力线路的用户会花费更长的旅行时间，比如在it上参加促销活动。不喜欢AR的用户会将AR视为普通路线，并在AR上快速行驶，因此用户在AR上花费的时间更少。

Definition 7: Preference of AR

所以AR的偏好可以通过喜欢AR的用户的偏好的聚类中心来表示。

问题定义

用户u对POI v的体验可以定义为​​​​​​​ （即u，v的偏好的余弦相似度）其中RS()是从yelp网站获得的评分在0-5之间。用户u对AR道路e的体验定义为​​​​​​​ ，所以最后用户对tp旅游路线的体验定义为

自由当tp中包含 时 ，其他时候均为0。

所以最后问题定义如下：

给定一个旅游图 ，需要给用户u推荐旅游路线，主要的限制条件有（1）用户有确定的起点，（2）路线没有自环，（3）约束时间为 ，（3）最低的用户体验要求​​​​​​​ 。目标就是在四个条件下获得最大的用户体验。用公式表示如下

这样的问题是被证明是np难的问题。

Method

作者提出根据POI和AR的个性化的旅游推荐 (TRAR)

①AR Discovery

为POI j定义一个向量​​​​​​​ ，其中 表示选择道路 进入POI j的受欢迎占比。然后利用 计算Gini系数，公式如下：

基尼系数范围为(0,1);当基尼系数趋近于0时，来港航线的人气比例接近相等；进入道路数越少，基尼系数越低；在相同的新航线数量下，受欢迎度比例越不均衡，基尼系数越高。

当​​​​​​​ ，并且​​​​​​​ 时，将通向 中最受欢迎的道路定义为AR。

②AR Evaluation

利用引力模型来评估每个AR的偏好和评分。首先将历史访问该道路的用户的偏好进行聚类，区分开偏爱AR的和不喜欢AR的，偏爱AR的用户的聚类中心就是AR的偏好。另外在道路上花费的时间长短则可以用来作为区分两类用户的标签，并以此为每个AR训练一个SVM分类器来分类用户，获得与​​​​​​​ 对应的 。最后用引力模型计算出​​​​​​​ 对应的RS。公式如下

③Trip Recommendation

因为上面提到的PEAR是np难的，作者提出一个启发式的方法TRAR。具体过程如下

首先利用存在n个的POI点构建出旅行图 ，这n个点在都是可在时间限制内访问的。将边eij 的用户体验和旅行时间进行初始化​​​​​​​ 。

当一个新的用户出现时，根据用户的偏好 和POI点的偏好​​​​​​​ ，计算出偏好分数。然后通过偏好分数选择top-k 个POIs。利用这些点生产G的子图​​​​​​​ 。

然后将用户的偏好​​​​​​​ 投影到G’中每一个AR的分类空间中，判断该用户是否属于偏爱该AR的用户类型，如果是，这将更新道路对用户的体验及用户在道路花费的时间​​​​​​​ 。具体如下道路体验从初始值0变为 ，花费时间计算如下。

是偏爱 的用户的平均旅行时间减去不偏爱 的用户的平均旅行时间方式计算。最后在更新后获得针对用户u的旅游图​​​​​​​ 。

最后则利用贪心算法在​​​​​​​ 图中根据时间和用户体验进行路径选择。每回都选择邻居中在时间允许情况下最能提升用户体验的作为下一个POI。

Experiments

数据集 一个是自己生成的synthetic dataset。另一个是公共数据集Foursquare dataset。

执行时间

时间限制的影响

作者提出的TRAR方法与MPTR方法之间的差距主要就是加入了对吸引力的路线的考虑。

Performance metrics: Recall, Precision and F1

创新点

作者把吸引力路径用来做个性化旅行推荐工作（论文反复强调是首次）。