影视推荐与参观相关地点路径规划算法研究

李建硕

（天津工业大学，天津 300000）

1 引言

根据互联网搜索到的数据显示，我国电影业和旅游业增长迅速，从2011 年全国总票房100 亿，到2018 年全国总票房609 亿，6 年的时间，总票房翻了5 倍，2017 年全年国内游客达到50.01 亿人次，比上年增长12.8%，这表明人们生活越来越多元化，对于精神层面的需求越来越高。一部电影的成功与否，不仅在于主演、题材等主要因素，更取决于电影场景的选取。根据世界各国影视旅游情况，结合一些经典电影景点，指出虽然电影的经济效益是一时的，但是一些电影中的场景随着影片的热映而闻名，吸引到大批游客，带动当地经济发展。因此影视旅游的概念近几年在国内兴起[1]。

然而，大多数游客想要到这些旅游景点进行游览时，需要自己发掘电影拍摄景点信息并查找大量旅游攻略制定路线图，这一过程费时费力。因此，通过基于用户喜好的协同过滤算法，实现电影经典的个性化推荐以及智能路线规划功能符合市场需求。本文针对现有的一些智能推荐和路线规划方案进行了算法上的优化，以获得更为高效、实用的影视旅游系统。

2 相关文献综述

传统的相似度计算忽略了用户共同评分项目数与用户平均评分的影响，以至于在数据稀疏时不能很好地度量用户间的相似度。提出了两个修正因子来改进传统相似度，同时改进了协同过滤算法，将其应用于电影推荐。

2016 年，李昂等人[2]针对跨系统协同过滤推荐中用户信息安全问题，提出一个安全计算模型。模型基于安全多方计算理论，使用轻量级分组密码算法LBlock 加密第三方提供的数据,并用RSA 密码系统管理密钥。

2018 年,张丽等人[3]发布Slope One 视频推荐算法的研究与实现，该算法基于Slope One 算法上，把时间衰减引起的评分权重函数作为一个权值参与到评分预测的公式中。而对于推荐的误差较大问题，本文对皮尔逊相关系数法做了改进，并将改进后的项目相似度作为权值参与到评分预测公式计算中。

2020 年，陈浩铨等人[4]发布热度和用户爱好程度的关联推荐算法研究，于景点热度和用户爱好程度的个性化旅游推荐算法，分析用户所到过的旅游景点，根据旅游时长推算出用户的兴趣程度，基于该景点的热度和用户的爱好设计出适合的最佳旅游路线。

2020 年，余洋等人[5]对Slope one 算法进行了进一步改进与研究，应用到基于辅助项的多权重slop one 算法。

2020 年，刘荣权等人[6]发布属性聚类与矩阵填充的景点推荐算法，将二分k－means 聚类算法应用到用户属性聚类中，因为同一类用户的特征越相似，则它们的相似度越高，这使得目标用户的相近邻用户集越准确。

3 偏好推荐

本文以Jaccard 相似系数作为协同过滤算法的基础，通过倒排法解决不同用户相似喜好过少导致的无意义计算，获得相似度矩阵。之后利用相似度矩阵计算出用户对物品的兴趣度。最后采用借助“堆”实现的TOP-N 分析法，得到为用户推荐的物品，并对热门物品的影响进行了削减。

3.1 Jaccard 相似系数

为了判断用户喜好偏好，为其进行个性化推荐，常使用相似系数将目标用户过去的行为轨迹与其他用户进行对比，计算出相似度（见图1）。

图1 Jaccard 相似系数推荐逻辑

目前有很多相关的相似度算法：

闵可夫斯基距离：

一般来说Jaccard 算法不适合协同过滤，因为在协同过滤中，评分是一个很关键的参考因素，Jaccard 算法忽略了其中的评分环节。而本系统中针对目标用户所喜好的物品只有电影和旅游地两类，不需要考虑评分偏好，因此选择较为简单的Jaccard 算法来简单计算两用户之间兴趣相似度：

3.2 倒排法优化用户兴趣度

为了解决如上问题，本系统将根据用户的喜好偏好，将用户-物品表转变为物品-用户表。根据每一个物品下的用户，得到用户的相似度矩阵（如图2）。每一个物品下相同喜好的用户会为矩阵中对应项的值加1。

图2 用户-物品表到相似度矩阵的转化过程

在得到了用户的相似度矩阵后，便很容易得到用户u 对某未知物品i 的兴趣度公式：

其中，p(u,i)表示用户u 对物品i 的感兴趣程度，Auv是用户相似度矩阵中用户u 和用户v 所对应的值，Wvi是用户v 对于物品i的感兴趣度。此处由于喜欢与否只根据用户选择来决定，因此这个值非0 即1。

3.3 堆优化的TOP-N 分析法推荐

得到用户对物品的兴趣度后，使用TOP-N 算法进行推荐，此处含义为推荐用户最感兴趣的N 个物品。由于N 的值可以在系统中动态更改，后续可能会对喜好进行更新。如果简单使用排序求前N 大的物品，只能满足一次系统调用的需求，若每次都需要重新计算该用户感兴趣度，则每次都需要花费O(nlog2n)的时间复杂度用于排序，大大降低了系统运行效率。

为了解决这种无意义的系统运行开销，同时保证在更新用户信息时能更加快速有效，本系统采用“小顶堆”这种数据结构对传统影视旅游所采用的简单TOP-N 分析法进行优化。将为每位用户所推荐的最感兴趣的N 个物品存入堆中，当需要更新时，只需要将新物品插入堆中，并执行“up 操作”[7]，最后将堆顶元素删除，并保证堆大小为N。这样即可用O(logn)的时间复杂度完成用户喜好的更新。

而此方法的缺点在于，需要为用户额外分配n 个物品大小的空间内存，属于以空间效率换取时间效率的做法。考虑到推荐物品数量不多，即占用的系统空间可以接收，因此此方法具有可行性。

4 路线规划

根据通过偏好推荐算法所获得的推荐地点，为用户进行路径规划。由于需要为用户推荐的是N 个景点的规划线路，而非单源汇最短路问题，因此不适宜使用简单的最短路算法进行处理。以往影视旅游研究中所采用弧面距离与实际道路距离相拟合的方式（图3），虽然能得到可行解，但当目标地点在起始点左右分布较为分散时，这种做法会产生极大的不稳定性。

图3 弧面距离与实际道路距离相拟合算法流程图

举例来说，假设A 地在起始点东方向1 千米，B 地在起始点西方向2 千米，C 地在起始点东方向3 千米，根据此算法得到的路线结果为：A->C->B。这显然有一段重复的路线导致推荐的路线并不是最优方案。

本文采用基于迭代思想（动态规划）的Bellman-Ford 算法[8]来求得推荐地点的最优旅游路线。首先将起始位置抽象成点0，推荐的N 个点抽象成点1 至点n，构成一张图。将0号点设置为超级源点，向所有其他点连一条边，作为该点的初始距离。对于图中的任意一条边(x,y,z)若满足：

dist[y]≤dist[x]+z(6)

成立，则该边满足三角形不等式。其中dist[x]表示第x 号点到0 号点的距离，dist[y]表示第y 号点到0 号点的距离，z表示这两点间的实际道路距离。当图中所有边均满足三角形不等式时，dist 数组中所存的即为最短路线。

Bellman-Ford 算法的算法流程如下：

遍历所有边(x,y,z)，用dist[x]+z更新所有dist[y]>dist[x]+z的边。

重复操作，直到没有更新产生，dist 数组中的最大值即为所求最短路长度。

由于对每个点均遍历了所有边的情况，因此该算法时间复杂度为O(mm)。m 为图中总边数。

由于实际景点路线错综复杂，因此针对Bellman-Ford 算法可以使用队列进行优化，将时间复杂度降低到O (km)级别，k 是一个很小的常数。本系统中采用的就是这种优化后的算法，本文中不再详细描述。

所获得的dist 数组与实际距离进行比对，可以得到清晰的最短路径，将其作为结果展示给用户即可。

5 实验与分析

本文使用网络爬虫所获得的地点数据集与用户喜好数据集，并对其中的数据进行整理，构建原始数据集与期望结果数据集，得到可用于进行计算的数据集，见表1。

表1 原始数据集

由于喜好推荐其本身的主观性，且数据集数量有限，缺少高数量用户的样本，缺少了推荐结果与用户个人信息的吻合，故而对于推荐结果的准确性评估仅停留在理论层面，本文无法对其给出量化评估。

本文对以往影视旅游研究中所采用弧面距离与实际道路距离相拟合的方式进行了改进，故本文将使用原始数据集中的最优路线规划数据集与计算所得的最优路线规划数据集进行比较。

本文最后得到如下实验结果，见表2-3。

表2 本文算法实验结果

表3 实验结果对比

6 总结与展望

本文针对影视旅游中经常出现的协同过滤推荐，以及最佳路径规划两类算法进行了理论性的优化，同时实现了以用户个性化推荐和路径规划为主要功能点的影视旅游系统。

在协同过滤算法中，首先，考虑到电影资源以及旅游地点的多样性，针对Jaccard 相似系数，采用倒排法进行优化，避免过多无效物品对于用户偏好计算过程效率的影响。其次，针对用户对于某一物品的兴趣度公式，进行了简化，可以更容易在程序和系统中实现相应算法。最后，为了降低重复计算用户感兴趣物品所带来的时间损耗，本文采用“堆”这类数据结构对TOP-N 分析法进行了改进优化，加快系统运行效率。

在路径规划算法中，证明出传统的以球面距离与实际道路距离相映射这种方法的局限性。同时提出了一种基于Bellman-Ford 算法，针对全局的路径规划方案，提高了路径推荐算法的可靠性。

在系统实际运行测试中，数据集数量有限，均来自管理员手动输入。虽能够保证在用户数量较低的情况下系统的正确运行，但缺少高数量用户的样本，同时缺少了推荐结果与用户个人信息的吻合，对于推荐结果的准确性仅停留在理论层面。为了解决这些问题，接下来将重点提高用户数据量，并考虑添加用户对于推荐结果满意度的反馈功能，帮助改进推荐算法，实现系统功能的完善。