轨迹相似性度量

哈士奇的罪恶

轨迹相似性对于移动对象分析来说是一个重要的指标，如何度量轨迹相似性，则是中心问题。轨迹相似性通常用一个距离函数来计算，现行比较常用的轨迹相似性度量指标有多种，而且分别有各自的优势，如何选择不同的轨迹相似性度量是进行轨迹聚类的关键。

在介绍轨迹相似性之前，先考虑如何定义点与轨迹之间的相似性[1]。假设有查询点q与轨迹A,q与A之间的相似性通常定义如下：


p'为轨迹A上按照d(.)计算距离最小的点。因此，点到轨迹的距离本质上还是计算点到点的距离，核心部分在于d(.)的定义，计算两个点距离时，可以选择L-P范数，可以选择欧氏距离，切式距离，曼哈顿距离等各种距离计算方法。对于经纬度数据，计算大圆距离显然比直接计算经纬度欧氏距离更准确。

轨迹与轨迹之间的相似度有多种经典度量指标。

Closest-Pair Distance(CPD)
Sum-of-Pairs Distance (SPD)
DTW
LCSS
EDR   

CPD距离即找出两条轨迹之间两点距离最近的两个点，以该点对的距离作为轨迹距离。计算公式如下所示：

CPD距离定义简单，但是容易受到局部极端情况的影响，考虑两条轨迹在某点相交，然而整体情况差异很大，这种情况用CPD距离显然不合适。总体来说，这种方法不是很好。

SPD[2]距离对两条轨迹对应序号的点对计算距离并求和，以该求和距离作为轨迹相似性分数。计算公式如下：

观察SPD距离发现，SPD距离要求轨迹A和轨迹B具有相同的轨迹点个数。在此基础上可以做出一些改进[3]，以便可以适应轨迹长度不同的情况，同时考虑轨迹方向的影响，参考Hausdorff distance algorithm ,类似于对称SPD距离。

总体距离分数为score = (d(A,B) + d(B,A)) / 2。对于d(A,B),按照轨迹点index顺序，找出轨迹A上每个点到轨迹B的最短距离，求和并除以总点数。

DTW距离的计算不受到轨迹点数是否相同的限制，计算公式为：

给定轨迹A<a1,a2,...an>和轨迹B<b1,b2,...bm>,Head(A)表示a1,Rest(A)表示<a2,a3...an>。

在噪声点存在的情况下，之前的计算方法会受到很大影响，而LCSS方法[4]在解决噪声点影响时很有效。LCSS全称为最大公共子串，假定A和B是点数分别为n和m,给定整数δ 和距离阈值ε 。LSSS的定义如下：

与DTW一样，计算方法用一种动态规划的形式定义。

虽然LCSS距离考虑到噪声的影响，但是LCSS无法区分具有相同公共子序列的轨迹，因此提出EDR[5]距离。

n,m为轨迹A,B的长度。subcost定义为：

轨迹相似性度量在轨迹聚类，移动目标分析中是个关键的问题，考虑到数据量，计算复杂度，噪声等影响因素，不同情况下需要选择不同度量。

参考资料：

《Computing with Spatial Trajectories》 郑宇

Agrawal, R., Faloutsos, C., Swami, A.N.: Efficient similarity search in sequence databases.

FODO pp. 69–84 (1993)

Chen, L., Ozsu, M.T., Oria, V.: Robust and fast similarity search for moving object trajectories.

SIGMOD (2005)

Chen, Z., Shen, H.T., Zhou, X., Zheng, Y., Xie, X.: Searching trajectories by locations - an

efficiency study. SIGMOD (2010)

Jon Froehlich John Krumm: Route Prediction from Trip Observations(2008)