龙源期刊网 http://www.qikan.com.cn
一种计算地理轨迹相似度的动态规划算法
作者：吴友凯 叶永舜
来源：《经营管理者·上旬刊》2017年第06期
摘 要：本文提出了一种利用动态规划算法解决轨迹相似度计算的方案。首先，根据空间相似性的定义以及距离相似度的运算原则，提出了一种可能的顺序相关的轨迹相似度计算模型，并以轨迹中的所有点到参考轨迹中的所有对应线段的相似度的平均数作为评估轨迹相似度的依据；然后，通过动态规划的方法寻找最佳的点到线段的匹配组合，从而得到轨迹之间的包括方向和形状两个方面的相似度。结果表明，本文提出的解决方案具有相当的可靠性，可以解决生活中的轨迹相似度计算要求。
关键词：动态规划算法 轨迹相似度计算 一、引言
1.选题背景及意义。轨迹的相似度度量有重大的意义。随着跟踪监测、卫星定位、传感器和无线通信等技术的快速发展，大量的轨迹数据产生了，其范围包括天文气象、动物迁徙路线、物流、交通、社交网络以及人类行为、市场营销等方面。为了从这些轨迹数据中发掘更多价值，聚类分类、轮廓提取、轨迹预测、隐私保护、行为预测等多种应用技术应运而出。这些技术都依赖于轨迹的相似性度量。因此，轨迹相似性度量的意义重大。
2.理论综述与文献回顾。理论综述。动态规划法 动态规划是针对求最优解问题的算法，其思想是：把一个问题的求解过程拆分为对多个不同阶段的子问题的求解 ，然后分别对这些子问题求解 ，最后根据不同阶段的子问题的解求出整个问题的解。空间相似度 地理学第一定律对相似性有定性的描述。本文综合文献，利用集合学的知识对相似性做以下定义： 设有2个地理空间的目标A1和A2，其特征的集合为C1、C2（C1、 C2均非空）。若C1∩C2=C≠Ф，称相似特征集C为目标A1、A2的空间相似关系。2个空间目标之间的空间相似关系强弱可用空间相似度衡量，其值域为[0，1]。相似度的大小具有模糊性。 文献回顾。由于轨迹相似度概念较新，对此的研究较少。最早在1993年，国外的AGRAWAL.R等人提出了基于欧氏距离的轨迹间相似度的表示方法，该方法要求参与计算的轨迹采样点一一对应，采用间隔相同、轨迹长度一致。轨迹间的距离由轨迹上对应各点间的距离求和、取最大或最小值得到。此方法与本文思想基本一致，本文在此方法的基础上进行了改变和改善。
中国科学院电子研究所的郭岩等学者提出了基于DTW改进的轨迹相似度算法，与本文从不同的角度对欧氏距离的轨迹相似度计算法进行改进。兰州交通大学的刘涛、闫浩文学者提出
一种计算地理轨迹相似度的动态规划算法
