原文传递
高效移动序列推荐算法的研究与实现
| 论文题名： | 高效移动序列推荐算法的研究与实现 |
| 关键词： | 移动序列推荐算法;动态规划;最优线路;出租车 |
| 摘要： | 大规模的位置轨迹数据为发现运输系统中有用信息提供了不可预测的机会。一个热点研究领域就是抽取节能高效的运输模式以便节省能源提高效率。本文着重研究节能高效的移动序列推荐问题。该问题的目的就是为空的出租车推荐一条连接一系列载客点的最优线路，使得该出租车能够以最小的巡航开销载到乘客。求解该问题对于节省能源提高效率、增加收益、减小环境污染以及缓解交通都具有非常广泛的实践意义。求解该问题的主要面临的挑战就是它的高计算复杂度。 本文提出了一种基于动态规划的方法来解决该问题。本文提出的的方法主要分为两个部分：线下预处理部分和线上搜索部分。在线下预处理部分，本文发现了比较序列间代价的常用潜在行驶距离函数满足迭代特性并给出了迭代公式，基于该函数的迭代特性，提出了两种新的潜在序列剪枝方法：增量剪枝和批量剪枝。在此基础上，提出了一种后向递增的潜在序列构造算法，并同时进行潜在序列的增量剪枝，使得候选路径的搜索空间大大减小。此外，在生成的特定长度的潜在序列集合中，进一步使用批量剪枝方法对候选序列集进行了大量约简。而为了处理更大规模的数据，本文把提出的两个算法在MapReduce上进行并行实现，使得算法效率有了数量级的提升。通过线下剪枝效率随着序列长度的不断提高，在线上处理部分，本文提出的的方法能够对所得的候选潜在序列集合实时高效地完成最优线路的搜索。另外，本文开发了一个出租车线路推荐的原型系统，以便应用于实际场景中。 通过对比在真实和人工数据集上的实验表明：本文提出的方法能够使得线下搜索时间得到极大降低，能够处理更大规模的载客点线路，同时，线下的剪枝率比已有基准算法的剪枝率大幅提高，使得在线最优路径搜索的时间复杂度显著下降，能够用于处理较多载客点集合上的任意长度的移动序列推荐问题。而通过系统原型的实现，本文研究的问题也具有很大的实用性。 |
| 作者： | 皇甫学军 |
| 专业： | 计算机科学与技术 |
| 导师： | 黄健斌 |
| 授予学位： | 硕士 |
| 授予学位单位： | 西安电子科技大学 |
| 学位年度： | 2014 |
| 正文语种： | 中文 |
检索历史
应用推荐
