基于嵌入表示和加权矩阵分解的线路推荐

Route Recommendation Based on Embedding and Weighted Matrix Factorization

摘要: 为了提升游客体验和增加旅游公司收入，旅游线路推荐成为重要手段。目前已有方法利用了游客与线路的交互历史，提升了推荐性能，但忽略了喜欢相同线路的共现游客对信息、被很多游客喜欢/不喜欢的线路对信息，这些对建模旅客偏好至关重要。因此本文提出了基于嵌入表示和加权矩阵分解旅游线路推荐算法。首先根据游客与线路的交互历史，抽取共现游客对、共现喜欢/不喜欢线路对，建立其词向量模型; 接着利用加权矩阵分解模型对游客与线路的交互历史、共现游客对、喜欢/不喜欢线路对信息进行联合分解完成线路预测；最后在厦航航空公司某旅游公司的真实数据集上评估了算法的有效性。

Abstract: To improve the tourist experience and increase the income of tourism companies, tourism route recommendation has become an important method. Many existing methods train and learn the interaction history between tourists and routes to improve the recommendation performance. However, the user co-occurrence information, codisliked routes and co-liked routes are very important for modeling tourist preference. Therefore, this paper proposes a route recommendation algorithm based on embedding representation and weighted matrix factorization. Firstly, it extracts user’s co-occurrence information, co-disliked routes and co-liked routes based on the interaction history between tourists and routes to establish word vector model by extracting co-occurrence tourists’ likes/dislikes of routes. Then it uses weighted matrix factorization to decompose the interaction history, the co-occurrence traveler information, co-disliked routes and co-liked routes to complete the route recommendation. Finally, the effectiveness of our method is evaluated on a real data set of a travel company of Xiamen Airlines.

1. 引言

随着人们生活水平的提高，人们有越来越多的出门旅游的机会。据统计近几年旅游的人数和收入以10%以上的速度在增长。为了争夺客源及增加收入，旅游公司需了解游客的需求，制定普受欢迎的线路；同时游客需要从大量已有的线路中选择符合自己兴趣的线路。推荐系统能分析用户的历史行为，建模用户的偏好，主动推送符合用户兴趣的个性化产品。将推荐系统应用旅游线路的推荐，不仅能更好地掌握游客的偏好，为其推荐符合其兴趣的线路，提升他们的体验，而且能帮助旅游公司制定更好的线路，增加旅游公司的收入。

目前推荐系统贯穿着整个的旅游过程，比如旅游前的线路推荐 [1]，旅游中景点、个性化服务推荐 [2] 及旅游结束后信息的收集和反馈 [3]。张艳根据游客的地理位置信息，生成游客轨迹，并根据景点实时容量统计，为游客推荐景点 [4]。韩艳等 [5] 引入热门链路概念，以游客满意度最大、景点间行程最短、景点拥挤度最低为目标，利用粒子群优化算法为游客推荐景点。陈雄等 [6] 利用蚂蚁算法在考虑时间关系的基础上为游客推荐其感兴趣的景点。Duan等分析游客的签到行为，利用Convolutional Neural Network (CNN)抽取游客签到地区特征，为游客推荐其感兴趣的景点 [7]。Zhu等 [8] 根据游客的签到数据进行了时间敏感性的个性化线路推荐。这些方法在一定程度上提高了线路推荐的精度，但由于相较于电影、音乐等数据，游客参与过的线路相对更少，因此旅游数据集中“旅客–线路”关联矩阵稀疏度更高。

为了丰富旅游信息，缓解数据稀疏带来的影响，研究者将线路主题 [9] [10]、旅客和线路属性 [11] [12] [13]、社交关系 [14]、评论 [15] [16] 等信息融入到推荐过程，提高了线路推荐准确度。朱桂祥 [9] 等从线路描述中挖掘主题信息来捕捉用户行为模式，从访问序列数据中挖掘频繁序列模式，利用马尔科夫模型完成用户实时点击流与模式库匹配计算进行线路推荐。李雅美等 [11] 用景点特征标签描述旅客的兴趣，并利用基于用户的协同过滤进行推荐。丁恒等 [12] 利用线路属性特征从多个维度计算相似性。孙文平等 [13] 融合多源旅游数据构建知识图谱来丰富旅游数据集。李晓旭等 [14] 采用优化聚类挖掘社交关系中Coterie组模式，并提出基于语义的距离敏感度和基于语义的丛中性两种推荐策略。崔春生等 [15] 根据在线评论信息计算旅客对各景点属性的权重并进行排序。潘禄生 [16] 分析游客对线路评论的情感，结合游客的喜好，为游客推荐喜欢的线路。这些方法利用线路主题、社交关系、属性特征及评论等信息，缓解了旅游数据的高稀疏性，提高了线路推荐性能，但这些额外信息的表示困难。

基于表示学习的推荐算法利用项目/用户的属性信息、游客和线路的交互行为训练、学习用户和项目的向量表示，它们能更好地表示了游客的偏好和项目特征，提高推荐性能。贾中浩等 [17] 使用表示学习得到线路的低维向量表示，利用门控制单元(GRU)建模用户长短期偏好，完成线路推荐，但它们只利用了游客和线路的交互历史。在实际过程中两个游客可能总是喜欢相同的线路，某些线路对出现在很多人喜欢或不喜欢的列表内。这些信息对于为旅客精准推荐符合其兴趣的线路都至关重要。

为了解决上述问题，本文提出了基于嵌入表示和加权矩阵分解的旅游线路推荐算法。首先根据旅客与线路的交互行为，抽取共现游客对、共同喜欢线路对、共同不喜欢线路对。接着利用词向量模型分别学习游客和线路的嵌入向量表示。最后利用加权矩阵分解模型将游客线路交互矩阵，游客共现矩阵，游客喜欢/不喜欢线路共现矩阵联合分解完成评分预测并进行线路推荐。

2. 基于词向量的游客和线路的嵌入表示

假设游客集合 $U=\left\{u_1,u_2,\cdots ,u_m\right\}$，旅游线路的集合 $L=\left\{l_1,l_2,\cdots ,l_n\right\}$，游客与线路的交互历史矩阵为 $M^{m\times n}=\left\{r_{ul}|u\in U,l\in L\right\}$，如果游客u参加了线路l，则 $r_{ul}=1$，否则为0。模型的任务是为目标旅客推荐其可能感兴趣的线路集合。

2.1. 共现线路对和共现游客对集合的抽取

在旅游线路推荐系统，如果一个游客u参与过某条线路l，则认为游客u喜欢线路l。从游客与线路的交互历史矩阵中，可得每位游客可参加多条线路，多名游客可共同选择相同的线路l₁和l₂，l₁和l₂被看作是游客共同喜欢的线路对。当某个游客选择过l₁，还没有选择过l₂时，此时可以将l₂推荐给他。相似地，当游客 $u_i$ 和 $u_j$ 共同参加过很多共同线路时，认为他们具有似的线路偏好，当游客 $u_i$ 参加过某线路 $l_i$，而 $u_j$ 并没有参加过，可以将 $l_i$ 推荐给 $u_j$。游客 $u_i$ 和 $u_j$ 被认为是具有相似偏好的共现游客对。

如果给定交互矩阵中 $M^{m\times n}$，可从中抽取三元组集合 $L_{like-co}=\left\{\left(l_i,l_j,t_{ij}\right)|l_i,l_j\in L,r_{u{l}_i}=1,r_{u{l}_j}=1\right\}$ 和 $U_{co}=\left\{\left(u_m,u_n,t_{mn}\right)|l_k\in L,r_{u_m{l}_k}=1,r_{u_n{l}_k}=1\right\}$，它们分别表示被游客共同喜欢的共现线路对集合、参加过相同线路的具有相似偏好的共现游客对集合及它们出现次数。 $L_{like-co}$ 表示了线路被旅客喜欢的程度，反映线路的受欢迎程度， $t_{ij}$ 越大，表示它们越受欢迎。 $U_{co}$ 表示游客的共同偏好， $t_{mn}$ 越大，表示游客 $u_m$ 和 $u_n$ 的偏好越相似。

2.2. 不喜欢共现线路对集合的抽取

旅游公司为游客推荐线路时，如果能了解游客不喜欢的线路特点，就能避免向游客推荐其根本不可能有兴趣的线路。对于电影等具有评分等显示反馈的推荐系统，抽取喜欢或不喜欢的项目都是相对容易的。游客与线路的交互属于隐式反馈，对于大量 $r_{ul}=\text{0}$ 的线路，游客没有参加，有可能是不喜欢，也可能是不了解此线路造成的。因此对于旅游数据集最大的挑战在于如何推测游客不喜欢的线路。

为了抽取不喜欢共现线路对集合来提高推荐精度，假设游客没有参与过的线路是有很大概率不被游客喜欢的。因此对于所有线路，利用面向游客的EM-like 算法推测游客不喜欢的线路。首先假设在游客的线路排序列表中，被游客喜欢的线路的排序评分要高于具有较高概率不被喜欢的线路。对于游客 $u_i$ 的所有线路排序列表为 $s_{u_i}$，则利用softmax 函数计算游客 $u_i$ 不喜欢线路 $l_k$ 的概率为式(1)

$P_{u_i}^k=\frac{\exp \left(-s_{u_i}\left(k\right)\right)}{{\displaystyle \underset{q=1}{\overset{n}{\sum }}\exp \left(-s_{u_i}\left(q\right)\right)}}$ (1)

其中 $s_{u_i}\left(k\right)$ 表示线路 $l_k$ 在游客 $u_i$ 排序列表中的位置。为了避免游客参加过的线路被选择，将游客旅游过的线路排序设置为＋∞。由于每一个游客旅游过的线路数量不同，因此抽取的不喜欢线路的数目也应不同。设定超参数t控制每个游客抽取不喜欢线路的数量，游客参与过的线路越多，抽取不喜欢的数目也就越大，将该参数称为负采样率。假设某游客旅游过10条线路， $\tau =\text{0}\text{.8}$，则为其抽取8条不喜欢的线路。利用式(1)得到线路的先验概率。为每个游客随机抽取其不喜欢的线路数据，并计算器不喜欢的概率后，进而可得到不喜欢的共现线路对集合，用三元组表示为 $L_{dislike-co}=\left\{\left(l_i,l_j,t_{ij}\right)|l_i,l_j\in L,r_{u{l}_i}=0,r_{u{l}_j}=0\right\}$。

2.3. 基于旅游数据抽取的词向量模型

词向量模型最初应用于文本处理，给定文本序列，它能学习每个词的潜在表示。Word2vector (比如，Skip-gram)是其最流行的模型。采用负采样机制的Skip-gram模型可分解每个词及其上下文组成的词对。因此可以用负采样机制的Skip-gram处理在交互序列对、共现游客对、共现线路对和不喜欢的共现线路对集合，得到共现游客对、共现线路对和不喜欢的共现线路对的潜在表示形式。因此假设D表示旅游过线路和与它们共现的喜欢线路对集合，则线路 $l_i$ 与它的共现线路 $l_j$ 的共现概率为式(2)

$PI\left(i,j\right)=\log \frac{\text{\#}\left(i,j\right)\ast \left|D\right|}{\text{\#}\left(i\right)\ast \text{\#}\left(j\right)}$ (2)

$\left|D\right|$ 表示D中所包含的交互序列对的总数， $\text{\#}\left(i\right)$， $\text{\#}\left(j\right)$ 分别表示 $l_i$ 和 $l_j$ 出现的次数， $\text{\#}\left(i,j\right)$ 表示 $l_i$ 和 $l_j$ 共同出现的次数。通过计算 D 中所有线路及其共现线路对的PI ，可以形成一个 n ´ n的平方矩阵 $M^{PI}$ ,这里的n 是D中独立的线路数。相似地，对于共现游客对集合、不喜欢线路共现对集合都可计算相应的 $M^{PI}$。这样就可以利用词向量模型得到共现用户游客对、共同喜欢线路对和不喜欢的共现线路对的潜在表示。

3. 游客和线路的加权矩阵联合分解模型的建立

综合考虑共现游客对、共现线路对和不喜欢的共现线路对，利用词向量模型得到共现游客对、共现线路对和不喜欢的共现线路对潜在表示，随后将其表示引入加权矩阵分解模型进行联合分解，学习并优化游客和线路的向量表示，从而提高推荐性能。

3.1. 游客与线路交互历史的加权矩阵分解

设有游客与线路的交互历史矩阵为 $M^{m\times n}=\left\{r_{ul}|u\in U,l\in L\right\}$，加权矩阵分解将M分解为2个低阶矩阵 $U^{m\times k}$ 和 $P^{n\times k}$ 分别表示游客和线路的潜在表示，其中k是维数， $U^{\text{T}}=\left({\alpha }_1,{\alpha }_2,\cdots ,{\alpha }_m\right)$， ${\alpha }_u$ 表示游客u的向量表示， $P^{\text{T}}=\left({\beta }_1,{\beta }_2,\cdots ,{\beta }_n\right)$ 表示线路的向量表示， ${\beta }_l$ 表示线路l的表示。M的加权矩阵分解模型为式(3)

$L_{\text{1}}=\frac{1}{2}{\displaystyle \underset{u,l}{\sum }{w}_{ul}}{\left(M_{ul}-{\alpha }_u{\beta }_l\right)}^2+\frac{1}{2}\left({\lambda }_u{\displaystyle \underset{u}{\sum }{\Vert {\alpha }_u\Vert }^2}+{\lambda }_{\beta }{\displaystyle \underset{l}{\sum }{\Vert {\beta }_l\Vert }^2}\right)$ (3)

其中超参数 $w_{ul}$ 用来衡量游客对线路喜欢程度的置信水平和交互矩阵中非零值和零值的数目。 $M_{ul}$ 为游客

与线路的交互历史矩阵。为了避免过拟合，用 ${\lambda }_u$ 和 ${\lambda }_l$ 调整正则项 ${{\displaystyle \underset{u}{\sum }\Vert {\alpha }_u\Vert }}^2$ 和 ${{\displaystyle \underset{l}{\sum }\Vert {\beta }_l\Vert }}^2$。

3.2. 共同喜欢线路的嵌入表示

将游客参加的线路按交互时间升序排序排列即可得到旅游线路序列。因此可以利用词嵌入方法来学习线路的潜在表示。给定每个游客的旅游线路序列，即可得到旅客喜欢的共现线路对集合X。因此学习共同喜欢线路对嵌入表示的目标函数为式(4)

$L_{\text{2}}=\frac{1}{2}{\displaystyle \underset{X_{lm}\ne 0}{\sum }{w}_{lm}^{\left(+p\right)}}{\left(X_{lm}-{\beta }_l{\gamma }_m-b_l-c_m\right)}^2+\frac{1}{2}{\lambda }_m{\displaystyle \underset{m}{\sum }{\Vert {\gamma }_m\Vert }^2}$ (4)

其中 ${\beta }_l$ 表示线路的潜在表示， ${\gamma }_m$ 共同喜欢线路潜在表示向量， $b_l$ 是喜欢线路的偏差， $c_m$ 是共同喜欢线路的偏差， $w_{lm}^{\left(+p\right)}$ 为超参数， ${\lambda }_m$ 为正则项调节系数。

3.3. 共同不喜欢线路嵌入表示

如果许多用户同时不喜欢两条线路时，这两条线路形成不喜欢共现线路对集合。如果推荐系统了解到这种不喜欢的共现模式，就可以避免为游客推荐不喜欢的线路，可降低推荐系统的误报率。因此，与共同喜欢线路嵌入的类似，利用游客共同不喜欢的线路对矩阵Y，学习共同不喜欢线路的表示。不喜欢共现线路嵌入表示的目标函数可以表示为式(5)

$L_3=\frac{1}{2}{\displaystyle \underset{Y_{lm1}\ne 0}{\sum }{w}_{lm1}^{\left(-p\right)}}{\left(X_{lm1}-{\beta }_l{\delta }_{m1}-d_l-e_{m1}\right)}^2+\frac{1}{2}{\lambda }_{m1}{\displaystyle \underset{m1}{\sum }{\Vert {\delta }_{m1}\Vert }^2}$ (5)

其中 ${\beta }_l$ 表示线路的潜在表示， ${\delta }_{m\text{1}}$ 共同不喜欢线路潜在表示向量， $d_l$ 是不喜欢线路的偏差， $e_{m1}$ 是共同不喜欢线路的偏差， $w_{lm1}^{\left(-p\right)}$ 为超参数， ${\lambda }_{m\text{1}}$ 为正则项调节系数。

3.4. 共现游客嵌入表示

当游客 $u_i$ 和 $u_j$ 去过相同的旅游线路时，认为他们有相似的兴趣。因此，如果 $u_i$ 去过某线路但游客 $u_j$ 未去过的线路时，可以向 $u_j$ 推荐该线路。从游客线路交互矩阵M，可以得到由游客-游客共现矩阵Z及概率。共现游客嵌入的目标函数可以表示为式(6)

$L_{\text{4}}=\frac{\text{1}}{\text{2}}{\displaystyle \underset{Z_{ul}\ne 0}{\sum }{w}_{lm1}^{\left(u\right)}}{\left(Z_{ul}-{\alpha }_u{\theta }_l-f_u-g_l\right)}^2+\frac{\text{1}}{\text{2}}{\lambda }_l{\displaystyle \underset{l}{\sum }{\Vert {\theta }_l\Vert }^2}$ (6)

其中 ${\alpha }_u$ 表示游客的潜在表示， ${\theta }_l$ 表示共现游客的潜在表示， $f_u$， $g_l$ 表示游客和共现游客的偏差， $w_{lm1}^{\left(u\right)}$ 为超参数， ${\lambda }_l$ 为正则项调节系数。

3.5. 加权矩阵联合分解模型

综合加权矩阵分解、共同喜欢线路、共同不喜欢线路及共现游客的嵌入表示，得到最后的联合分解目标函数表示为式(7)

$L=L_{\text{1}}+L_{\text{2}}+L_{\text{3}}+L_{\text{4}}$ (7)

其中，令正则化系数 ${\lambda }_u={\lambda }_{\beta }={\lambda }_m={\lambda }_{m1}={\lambda }_l=\lambda$。利用梯度下降法对公式(7)进行优化，学习可得到游客和线路的表示，从而进行线路推荐。

4. 实验结果及分析

4.1. 数据集

旅游数据来源于厦门航空旗下的某旅游公司，包括4737个游客对1436条旅游线路的25717条旅行记录。每名游客至少包含3条参加过的线路，每条记录包括旅游团号、游客姓名、性别、游客身份证号、线路出发时间、线路价格、景点的详细介绍。它是一个隐式反馈数据集，只要游客参加过的某线路，则认为该游客喜欢这条线路，没有游客对线路明确的喜好。对数据集以7:2:1的比例拆分成训练集(train)、验证集(validation)和测试集(test)。训练集用来训练模型，验证集用来参数选取，测试集则用来评估模型。

4.2. 评估指标

本文采用召回率(Recall)、归一化折损累计增益(Normalized Discounted Cumulative Gain, NDCG)和平均精准度(Mean Average Precision, MAP)作为评估标准。Recall描述推荐系统推荐给用户的旅游线路占用户真正感兴趣的线路的比例。NDCG和MAP则表示命中项目在推荐列表中排序位置的情况。

4.3. 参数训练

4.3.1. 负采样率τ的影响

负采样率表示为每个旅客抽取多少个不喜欢的项目。由于每个游客实际参与过的线路数不同，因此在固定的负采样率下，为每个游客抽取的不喜欢线路数是不同的。对同一个游客来说，负采样率τ越大，抽取的不喜欢的线路越多，优化过程中负样本较多。如果负采样率τ的值越小，抽取的不喜欢的线路数越少，负样本会较少。因此在试验中讨论了为每个游客抽取多少个负样本，能使模型性能达到最好。试验中采用网格搜索的方式，根据算法性能来选择负采样率。在固定正则化参数和潜在因子的情况下，τ的搜索范围为{0.1，0.2，0.4，0.6，0.8，1.0}，性能结果如图1所示。

Figure 1. Effect of negative sampling rate

图1. 负采样率对性能的影响

从图1可知，随着τ增大，在Top@5、Top@10和Top@20的三种评估指标都是先增大后减小，之后趋于不变。结果证实了随着负样本数量的增加，模型性能先增加后减少，而负样本数目越大，模型的训练也会越慢，因此为了平衡模型性能和效率，负采样率取为0.2。

4.3.2. 向量维度k的影响

向量维度表示游客和线路潜在表示的长度。向量维度越大，游客和线路的信息表示越丰富，但计算量也越大。向量维度越小，向量表示不够精确，但学习速度快。因此在平衡精度与计算量的情况下，一般通过实验来设定较合适的维度大小。设定向量维度k搜索范围为在{50，100，150，200，250，300}，实验结果如图2所示。从图2可知，随着向量维度的增大，NDCG和MAP指标快速增长，当k达到150以上的时候，增速变缓，算法性能趋于稳定。Recall指标的增长不如NDCG和MAP变化剧烈，但仍然是先增大后减小，到达150之后增速趋缓，因此向量维度取为150。

4.3.3. 正则化系数λ的敏感性分析

正则化系数λ控制模型的参数，避免模型的过拟合。正则化系数的敏感性分析在{0.1，0.5，1，1.5，2}中进行，实验结果如图3所示。随着λ的增大，NDCG和MAP指标均快速增长后减小，之后趋近稳定。Recall虽然也是先增大后减小，但变化幅度比NDCG和MAP小，因此本模型中的正则化参数l 取1。

Figure 2. Effect of dimension size

图2. 向量维度对性能影响

Figure 3. Sensitivity analysis of regularization coefficient

图3. 正则化系数的敏感性分析

4.4. 实验结果与对比分析

为了更好地评估模型的性能，将本文的基于嵌入表示和加权矩阵分解模型(Eebedding Weighted Matrix Factorization，EWMF)与以下方法进行了对比：(1)基本加权矩阵分解模型(Weighted Matrix Factorization，WMF)：它是矩阵分解方法的代表，利用加权矩阵分解模型对用户交互历史矩阵进行分解，得到旅客和线路的向量表示完成线路推荐；(2) 基于标签的协同过滤推荐(Label based Collaborative Filtering, LCF):它是一种利用丰富额外信息的方法，它用地域、时间、主题、类型标签丰富旅游数据，并利用协同过滤进行推荐；(3) 基于知识图谱和长短期偏好的景点推荐(KG-ULSP)：它是表示学习的代表方法，它用网络表示学习的方法学习景点的特征向量表示，利用门控循环单元(GRU)学习旅客长短期偏好。

表1给出了四种模型在Recall@N、NDCG@N、MAP@N线路推荐结果。从表1可以看出，随着N的增大，Recall@N、NDCG@N、MAP@N都增大，其中Recall@N的增长幅度尤为明显。这样的结果验证了现实中这样的一个事实：即为用户提供越多的线路选择，其中满足用户兴趣的线路就会越多。但是推荐的线路多，用户最感兴趣的线路不一定都能排在推荐列表的前面的最前面。基于网络表示学习的两种方法EWMF和KG-ULSP的结果要好于WMF和LCF，这是因为利用网络表示学习的方法学习线路和旅客向量表示，更好地利用了数据信息，得到了好的统一表示，而WMF和LCF融合并充分利用这些信息是困难的。EWMF要好于KG-ULSP说明利用词向量方式加入用户共现、共同喜欢线路对、共同不喜欢线路对的信息，能够得到更好地线路和旅客的向量表示，而KG-ULSP只利用了景点的特征信息来学习向量表示。LCF的性能要优于WMF，是因为LCF很好地利用额外数据信息，而WMF只利用了游客与线路的交互矩阵。

Table 1. Comparison EWMF with other methods

表1. EWMF与其他方法对比

5. 结语

本文提出了基于嵌入表示和加权矩阵分解的旅游线路推荐算法。通过游客与线路的交互历史，抽取共现游客对、共现喜欢/不喜欢线路对信息，并利用词向量模型得到游客和线路的向量表示，在一定程度上缓解了数据稀疏的问题；接着将共现游客对、喜欢/不喜欢线路对及游客与线路的交互历史利用加权矩阵分解模型进行联合分解，最后预测游客对线路的偏好，丰富了可利用信息。通过在厦航航空公司某旅游公司的真实数据集上的实验结果表明提高了推荐算法的性能，推荐的线路更符合游客的偏好。

基金项目

国家自然科学基金资助项目(U1533104)。