點擊藍字關注我們

軌跡相似性度量的介紹

數(shù)據(jù)相似性一般使用距離來度量，這些距離包括歐氏距離(Euclidean Distance)，曼哈頓距離(Manhattan Distance)，切比雪夫距離 ( Chebyshev Distance )，閔可夫斯基距離(Minkowski Distance)，標準化歐氏距離 (Standardized Euclidean distance )，馬氏距離(Mahalanobis Distance)，夾角余弦(Cosine)，皮爾遜相關系數(shù)（Pearson correlation），漢明距離(Hamming distance)，杰卡德相似系數(shù)(Jaccard similarity coefficient)，布雷柯蒂斯距離(Bray Curtis Distance)等等。

軌跡相似性對于移動對象分析來說是一個重要的指標，如何度量軌跡相似性，則是中心問題。與一般數(shù)據(jù)類似的是，兩個軌跡之間的相似性通常是由軌跡點之間距離的某種集合來衡量的，沿著這個方向，不同應用程序的幾個典型的相似函數(shù)包括Closest-Pair Distance、Sum-of-Pairs Distance、DTW、LCSS和ERP、EDR。值得注意的是，其中一些相似性函數(shù)最初是針對時間序列數(shù)據(jù)提出的。但由于軌跡是多維空間中一類特殊的時間序列，這些相似函數(shù)同樣適用于軌跡數(shù)據(jù)。

（1）Closest-Pair Distance

測量兩條軌跡相似度的一個簡單方法是使用它們的最小距離。為了做到這一點，我們從兩條軌跡中找到最近的一對點，并計算它們之間的距離。更正式地，給定兩條軌跡A和B，其最近鄰距離可以計算如下:

（2）Sum-of-Pairs Distance

Agrawal等人提出了兩個軌跡之間的另一個相似函數(shù)，他們簡單地使用對應點對之間距離的和來度量相似度。設A,B為點數(shù)相同的兩條軌跡，其距離定義如下:

（3）Dynamic Time Warping Distance（DTW）

正如我們所看到的，歐幾里得距離的一個明顯的限制是，它要求兩條軌跡長度相同，這在現(xiàn)實生活中是不太可能的。更理想的相似度度量應該在兩條軌跡的長度上具有一定的靈活性。動態(tài)時間規(guī)整(DTW)距離是第一個基于這種動機的方法。DTW的基本思想是允許“重復”某些點，以便獲得最佳對齊。

給定軌跡a = {a1，…，an}，令Head(A)表示a1, Rest(A)表示{a2，…，an}。定義長度為n和m的兩條軌跡A和B之間的時間彎曲距離為

其中d(，)可以是在點上定義的任意距離函數(shù)。

（4）Longest Common Subsequence

前兩個相似函數(shù)的一個共同缺點是它們對噪聲比較敏感，因為包括噪聲在內(nèi)的所有點都需要匹配。因此，僅僅由于一個噪聲點，就可能積累一個過大的距離。為了解決這一問題，提出了用最長公共子序列(lcs)來更魯棒地測量兩條軌跡的距離。它的基本思想是允許跳過一些點，而不是重新排列它們。因此，遠點將被忽略，使其對噪聲具有魯棒性。LCSS方法的優(yōu)點有兩個:1)有些點是不匹配的，而在歐幾里得距離和DTW距離中，所有的點都必須匹配，即使它們是離群點。2) LCSS距離允許更有效的近似計算。

設A和B分別為長度為n和m的兩條軌跡。鑒于整數(shù)δ和距離閾值ε,a和B之間LCSS定義如下:

參數(shù)δ是用來控制在時間,我們能走多遠為了匹配一個給定的點從一個軌道到另一個點的軌跡。ε是一個匹配的閾值來確定是否考慮到這一點。基于LCSS的概念，有作者提出了兩個相似函數(shù)S1和S2（ Zheng, Y., Zhang, L., Xie, X., Ma, W.Y.: Mining interesting locations and travel sequences from gps trajectories. WWW(2009)）

（5）EDR Distance

雖然LCSS可以處理帶有噪聲的軌跡，但它是一種非常粗糙的度量方法，因為它不區(qū)分具有相似公共子序列的軌跡，而是關注于不同大小的軌跡之間的間隙。這促使我們提出了一個新的距離函數(shù)的建議，稱為Edit Distance on Real Sequence。

定義：給定兩個長度分別為n和m的軌跡A、B，匹配閾值ε, A和B之間的EDR距離是需要對S進行插入、刪除或替換使其變成B的操作次數(shù)。

與歐幾里得距離、DTW和LCSS相比，EDR具有以下優(yōu)點:

①在EDR中，匹配閾值通過量化一對元素到兩個值(0和1)之間的距離來減少噪聲的影響(LCSS也執(zhí)行相同的量化)。因此，在EDR中，異常值對測量距離的影響要比在歐幾里得距離和DTW中小得多。

②與LCSS不同的是，EDR會根據(jù)兩個匹配子軌跡之間的間隙長度對其進行懲罰，這使得EDR比LCSS更精確。

（6）ERP Distance

前面討論的所有相似函數(shù)可以分為兩類。第一個是歐幾里得距離，它是一個度量，但不能支持局部時移。第二類包括DTW、LCSS和EDR，它們能夠處理本地時移，但是非公制的。為了解決這個問題，我們提出了帶實際懲罰的ERP，它代表了L1-norm和ERP的結合。

通過仔細分析DTW的距離可以看出，DTW不是度量標準的原因是，當需要添加一個gap時，它會重復前面的點。因此，點與gap之間的差值取決于前一個點。相反，ERP在兩個匹配點之間使用真實的懲罰值，而在計算不匹配點的距離時使用一個恒定值。因此，ERP可以支持本地時移，并且是一種度量。

給定長度分別為n和m的軌跡A,B，一個隨機點g, ERP距離定義如下:

（7）其它

（方法來自‘一種出租車載客軌跡空間聚類方法’）

如下圖所示，Tr1 和 Tr2 分別為參與距離計算的兩條子軌跡。點 Pi1' 與點 Pi2' 分別是點 Pi1 和點 Pi2 在子軌跡 Tr2 上的投影點，θ 是兩條子軌跡之間的夾角。

子軌跡 Tr1 和 Tr2 之間的軌跡距離為：d(Tr1 ,Tr2)= d水平 + d垂直 + d角度 。其中水平距離、垂直距離、角度距離的定義如下：

①（水平距離） 是指 Pj1 和 Pj2 分別到點 Pi1 和 點 Pi2 在子軌跡 Tr2 上的投影點的距離的平均值。

②（垂直距離） 是指點 Pi1 和點 Pi2 分別到子軌跡 Tr2 的垂直距離的平均值。

③（角度距離） θ 為子軌跡 Tr1 和 Tr2 之間的夾角，|Tr | 1 為子軌跡 Tr1 的長度。當角度大于 0 小于 90° 時，角度距離為較短子軌跡長度乘以夾角的正弦值。當角度大于 90°小于 180°時，角度距離即為較長子軌跡的長度。

軌跡相似性度量的應用

可根據(jù)軌跡相似性進行軌跡聚類，以論文《航空器飛行軌跡相似性度量及聚類分析》為例進行介紹。

基于相似性度量的飛行軌跡聚類能夠為航線優(yōu)化設計、空中交通管理智能化提供技術支持。對飛行軌跡數(shù)據(jù)進行預處理之后，引入歐氏距離和余弦相似度2種度量，分別構建實際軌跡與理想軌跡、實際軌跡之間的相似性矩陣，利用譜聚類方法對終端區(qū)實測飛行軌跡進行聚類，并針對不同相似性度量的特點進行對比分析。結果表明 ，基于實際軌跡與理想軌跡相似性以及基于混合度量計算實際軌跡間相似性的聚類結果均較為理想，能夠有效識別盛行交通流和異常軌跡。

當實際軌跡的整體相似性較差時，需要通過構建軌跡間的相似性矩陣實現(xiàn)聚類，具體相似性度量如下：

1）計算每2條軌跡間對應點的平均距離，得到平均距離矩陣DA

2）計算每2條軌跡間對應點的最大距離，得到最大距離矩陣DM

3）計算每2條軌跡由起點和終點構成向量的余弦相似度 ，得到整體余弦矩陣 Cos

4）計算每 ２ 條軌跡間對應向量的平均余弦 ，得到平均余弦矩陣 COS

5）根據(jù)下式計算每2條軌跡的綜合性度量，得到綜合性度量矩陣 Loc

上式中xloc為軌跡間最大距離點所處位置 ，n 為軌跡點個數(shù) ，則 ζ越小表示最大距離點越靠近起始點 ，即軌跡間的相似性越高 ；d１為軌跡起始點間的距離 ，dm 為最大距離，則 σ越小表示起始點距離相對于最大距離越小 ，即軌跡間的相似性越高 ；ε為基于上述 ２ 種方法的綜合性度量 ，ζ和 σ 乘積越小 ，則 ε越接近于１，軌跡間的相似性越高 。

基于上述5種度量構建5個相似性矩陣 ，并進行歸一化處理 ，使得矩陣中元素值大小對于軌跡相似性判斷的尺度一致。為了分析不同相似性度量的特點 ，將相似性矩陣分配不同的權重后進行聚類 ，權重分配見表1

將相似性矩陣依據(jù)上述不同權重進行加權平均后 ，利用譜聚類方法對飛行軌跡進行聚類。聚類結果如下：

總結以上聚類結果可知，在使用獨立相似性度量時 ，基于軌跡對應點的最大距離（S2）度量得到的聚類效果較好。將不同的相似性度量加權平均得到的混合度量（S6），在一定程度上提高了聚類效果，且增加了魯棒性 ，使聚類結果更加穩(wěn)定。對不同相似性度量的聚類結果對比分析見表 ２ 。

可以改進的方向：（1）相似性度量可以使用以上提到的軌跡數(shù)據(jù)專用的相似性度量（2）除了對軌跡本身進行聚類外，還可以提取軌跡的特征來表征這一條數(shù)據(jù)（3）聚類結果對比分析過于主觀，可以進行量化。（個人想法如有不妥之處請見諒）

參考文獻：

（1）《Computing with Spatial Trajectories》

（2）一種出租車載客軌跡空間聚類方法

鏈接：https://pan.baidu.com/s/1Cyp4G-GXeZ2xdvmA77PNhg

提取碼：a1r0

（3）航空器飛行軌跡相似性度量及聚類分析

鏈接：https://pan.baidu.com/s/1PqbM4Pz4RicNXSu88qHQUQ

提取碼：h6h7

往期精彩回顧適合初學者入門人工智能的路線及資料下載機器學習及深度學習筆記等資料打印機器學習在線手冊深度學習筆記專輯AI基礎下載（pdf更新到25集）機器學習的數(shù)學基礎專輯獲取一折本站知識星球優(yōu)惠券，復制鏈接直接打開：https://t.zsxq.com/yFQV7am本站qq群1003271085，加入微信群請掃碼喜歡文章，點個在看

總結

以上是生活随笔為你收集整理的【交通行业】轨迹相似性度量介绍的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。