一种轨迹相似性的度量方法。技术前沿
正是基于大规模的轨迹数据，针对易感人群难以发现的问题，开发并提供了相关的人群查询功能。通过对轨迹的匹配和挖掘，可以快速找出在时间和空间上与被诊断者的轨迹有过“接触”的人。其中，实现这一功能最重要的任务之一就是如何度量两个轨迹的相似性。下面将简单介绍一些常见的轨迹相似性度量方法。
轨迹，作为一种时空数据[1]，是指物体在空间中的移动路径，通常表示为GPS点的序列，如tr=，其中点pi=(lat，lng，t)表示物体在t时刻位于地理坐标位置(lat，lng)，lat和lng分别表示纬度和经度。
大数据时代，随着车载导航系统的普及，大量的轨迹数据正在不断产生，这些轨迹蕴含着巨大的价值[2]，比如可以对交通流量进行分析预测，为政府的城市规划提供建议；还可以进行轨迹聚类，寻找多条轨迹穿越的道路，用于指导自行车道的规划；还可以检测驻点，找到轨迹经常停留的区域。
轨迹数据的分析和处理极具挑战性，主要包括三个方面:1)轨迹数据量大；2)轨迹数据有噪声；3)获取轨迹数据的方式多种多样。其中，轨迹相似度作为一个基础的算法服务，度量两个轨迹之间的距离，可以支持其上层应用，也是当前研究的热点之一。
与点到点或点到轨迹的距离测量相比，轨迹间的距离测量更加复杂，需要考虑的因素很多，比如轨迹的采样率、考虑轨迹的时间信息、轨迹本身的噪声等。常见的轨迹相似性度量方法大致分类如下图所示。
我们分别定义以下两个长度为n和m的轨迹，然后:
欧几里德距离欧几里德距离要求两条轨迹长度相等，一一对应，它的数学定义是:
欧氏距离的定义简单明了，即两条轨迹对应点的空间距离的平均值，但缺点也很明显，即不同长度轨迹的相似性无法度量，且对噪声点敏感。
动态时间扭曲(DTW)
如上所述，欧几里德距离的一个明显的限制是要求两条轨迹长度相等，这在实际情况下是不太可能的。理想情况下，轨道长度应该有一定的灵活性。
动态时间扭曲DTW[3]的思想是自动扭曲两个序列，在时间轴上进行局部缩放和对齐，使它们的形状尽可能一致，从而得到尽可能大的相似度。DTW将两个轨迹的点映射为多对多，从而有效地解决了数据不均匀的问题。其动态规划算法如下:
其中，head(tr)= 1
动态时间归一化算法灵活、轨迹长度不受限制且有效，但不处理噪声点，离群点也会对结果产生很大影响。
最长公共子序列(LCSS)
有一个经典的算法问题:求解两个序列的最长公共子序列，不要求两个连续的公共子序列相连，例如BDCABA和ABCBDAB的最大公共子序列是BCBA。在此基础上，很自然地提出了一种基于最长公共* * *子序列的轨迹相似性度量方法，即LCSS，其值代表最多可视为同一点的点数，即两条轨迹中满足最小距离阈值限制的轨迹点的对数。基于动态规划的算法如下:
其中，参数为最小距离阈值，当两点之间的距离小于该值时，将被认为是同一点。此外，该算法对轨迹长度没有限制。
最长公共子串距离处理噪声点，即由于噪声点的偏差没有靠近它的跟踪点，所以不会计入最终结果。这一步对噪音很有效。但同时算法的最小距离阈值很难定义，有可能返回不相似的轨迹。
编辑真实序列的距离(EDR)
给定两条长度分别为n和m的轨迹tr1和tr2，以及最小距离的匹配阈值，两条轨迹之间的EDR距离[4]就是需要插入、删除或替换tr1并使之为tr2的操作次数。基于动态规划的算法如下。
其中，
轨迹的编辑距离为新的轨迹相似性度量提供了新思路，其缺陷也很明显，即对噪声点敏感。
豪斯多夫距离
简单来说，Hausdorff距离[5]就是两条轨迹最近点之间的最大距离。
其中h(tr1，tr2)称为从tr1到tr2的单向Hausdorff距离，其定义如下:
弗雷歇距离(弗雷歇距离)
直观地说，弗雷歇距离[6]就是狗绳距离，即主人分别走路径A和狗走路径B所需的最短狗绳长度。
基于动态规划思想的弗雷歇距离算法如下:
其中d(p，q)是两个GPS点之间的欧氏距离，tr(n-1)=是长度为n-1的轨迹tr的子轨迹。
弗雷歇距离为我们提供了一种简单直观的度量相似性的方法，也能取得很好的效果；但是，很遗憾，它没有处理噪声点。例如，如果狗的跟踪点因为噪声而偏离很远，弗雷歇距离也会增加，这显然是不合理的。
单程距离(OWD)
单向距离OWD[7]定义如下:
其中|tr1|表示轨迹tr1的长度，d(p，tr2)表示GPS点p到tr2的距离。为了对称，只需修改上面的公式:
图11:单向距离示意图，是多边形面积之和与折线长度之比。
OWD距离的基本概念是基于两条轨道所包围的区域。面积大，说明轨迹间距离远，相似度低。相反，如果封闭区域为0，则表示两条轨迹重叠，相似度最高。
折线之间的位置(LIP)
多线位置距离LIP[8]定义如下:
其中Ii表示两个轨迹的第I个交点，权重wi定义如下:
LIP法很好理解，当某个区域的周长占总长度的比例大时，权重自然大；面积为0时，表示两条轨迹之间没有间隙，唇距为0；当面积的加权和较大时，意味着两个轨迹之间的间隙较大，唇距也较大。另外，权重由区域周长占总长度的比例决定，这也在一定程度上抵抗了噪声点的干扰。
目前，JD.COM市开发的时空数据引擎JUST (JD城市时空数据引擎)已经实现了动态时间扭曲、豪斯多夫距离、弗雷歇距离等多种轨迹相似度计算方法。用户只需要一条SQL就可以实现，不需要编码，只是还提供了一个轨迹可视化功能，供用户观察。欢迎参观/体验。请发邮件给just@jd.com寻求合作。
参考资料:
[1]郑，y，等。城市计算:概念、方法和应用。ACM。
[2]郑宇。轨迹数据挖掘:综述。美国计算机学会智能系统与技术汇刊。2015第6卷第3期。
[3] Yi B K，Jagadish H V，Faloutsos C .时间弯曲下相似时间序列的高效检索[C]//Proceedings 14第四届国际数据工程会议。IEEE，1998: 201-208。
[4]陈升，？移动物体轨迹的鲁棒快速相似性搜索[C]//2005年ACM SIGMOD数据管理国际会议录。2005: 491-502.
[5] Alt H .比较形状的计算几何[M]//高效算法。施普林格，柏林，海德堡，2009: 235-248。
[6] Eiter T，Mannila H .计算离散弗雷歇距离[R].技术报告CD-TR 94/64，克里斯琴·多普勒专家系统实验室，奥地利维也纳大学，邮编:1994。
[7]论文:林B，苏J .单向距离:用于基于形状的运动物体伪影相似性搜索[J].地理信息，2008，12(2):117-142。
[8] LIP论文:Pelekis N，Kopanakis I，Marketos G，等.轨迹数据库中的相似性搜索[C]//14第四届国际时态表征与推理研讨会(TIME'07).IEEE，2007: 129-140。