轨迹相似性度量
轨迹相似性对于移动对象分析来说是一个重要的指标，如何度量轨迹相似性，则是中心问题。轨迹相似性通常用一个距离函数来计算，现行比较常用的轨迹相似性度量指标有多种，而且分别有各自的优势，如何选择不同的轨迹相似性度量是进行轨迹聚类的关键。在介绍轨迹相似性之前，先考虑如何定义点与轨迹之间的相似性。假设有查询点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距离对两条轨迹对应序号的点对计算距离并求和，以该求和距离作为轨迹相似性分数。计算公式如下：
观察SPD距离发现，SPD距离要求轨迹A和轨迹B具有相同的轨迹点个数。在此基础上可以做出一些改进，以便可以适应轨迹长度不同的情况，同时考虑轨迹方向的影响，参考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方法在解决噪声点影响时很有效。LCSS全称为最大公共子串，假定A和B是点数分别为n和m,给定整数δ 和距离阈值ε 。LSSS的定义如下：
与DTW一样，计算方法用一种动态规划的形式定义。虽然LCSS距离考虑到噪声的影响，但是LCSS无法区分具有相同公共子序列的轨迹，因此提出EDR距离。
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 - anefficiency study. SIGMOD (2010) Jon Froehlich John Krumm: Route Prediction from Trip Observations(2008)
页:
[1]
