基于面積劃分的軌跡相似性度量方法

呂一可，徐 凱，黃振強

（1.上海海事大學交通運輸學院，上海201306；2.上海海事大學上海國際航運研究中心，上海200082；3.上海海事大學信息工程學院，上海201306）

0 引言

隨著大數據時代的來臨，時空軌跡數據挖掘在越來越多的場景中被運用，包括動物的遷徙、行人的流線、運輸載具行駛的軌跡，甚至是氣象領域的氣旋路徑。這類的時空軌跡數據蘊含著大量的信息，而相關領域的分析研究也就顯得尤為重要。在時空軌跡數據中，軌跡的相似性度量作為軌跡挖掘工作的關鍵步驟，在軌跡聚類、軌跡修復和預測等工作中起著重要作用。

時空軌跡的相似性對于移動對象分析來說是一個重要的指標，而這些工作大多面臨著龐大而雜亂的數據，軌跡相似度量為相關數據的挖掘工作提供了保障。但對于不同的應用場景和實際需求，涌現(xiàn)出了一系列不同的相似度量方法，而各種軌跡相似度量方法對于軌跡相似及其程度有著各自不同的劃定。

本文提出一種基于面積劃分的空間軌跡相似的全局匹配度量的三角分割（Triangle Division，TD）方法，該方法適用于無路網結構軌跡，有著高效且在軌跡點缺失下有著更佳的魯棒性的特點。本文的主要工作如下：

1）對面積劃分的軌跡度量方法明確了相似屬性的定義：兩條軌跡間擁有著類似的運行趨勢、位置與形狀，且在非關鍵軌跡點數量缺失或者分布不均勻等特殊情況下仍然可判斷軌跡相似。這一充要條件是很多軌跡相似方法中所未提及且容易遺漏的，而在實際應用中有著重要意義。

2）不同于基于軌跡點或段的度量方法，采用了面積劃分的全新思路來度量軌跡的相似度。相較于傳統(tǒng)根據軌跡點的相似度量算法，該方法將時間復雜度從T(n)=Ο(n×m)降低到了T(n)=Ο(n+m)，且對于軌跡中非關鍵軌跡點缺失的情形有著更佳的魯棒性。

3）提出了TD 的軌跡相似度量方法，建立了三角形面積分割規(guī)則，以計算軌跡間的面積。通過設置“指針”，有規(guī)則地將兩條軌跡間的面積分割成若干不重疊三角形，并累加這些三角形的面積獲得軌跡面積。再由此面積得到單位長度的軌跡間面積定義為軌跡距離，可與設定的閾值對比來確認此兩條軌跡的相似性。

4）與傳統(tǒng)方法提出的軌跡距離不同，本文方法是基于軌跡長度的相似度，使軌跡相似程度與軌跡的長度掛鉤。該數值越大表明軌跡越相似，同時可設置對應于軌跡長度閾值的軌跡相似度下限。引入軌跡長度來得到軌跡相似度，而不是使用傳統(tǒng)的軌跡點，該數值越大表明軌跡越相似。通過相似度，可設置對應于不同應用場景下的軌跡相似度下限來判斷軌跡是否相似。

1 相關工作

軌跡相似度量的方法在實際的運用中，不同的相似性度量方法會對后續(xù)的軌跡挖掘工作產生較大的影響。因此，要具體根據所應用場景特點來選擇合適的度量方法。

對于時空軌跡的相似度量方法，由度量對象的不同可分為基于軌跡點的相似度量方法和基于軌跡段的相似度量方法［1］。而對于軌跡點的度量方法，又可分為軌跡的全局匹配方法和局部匹配方法。

1）基于軌跡點的軌跡相似度量的全局匹配方法。歐氏距離（Euclid）［2］是較早提出的對于空間軌跡相似度量的方法，通過兩條軌跡的軌跡點距離的累加來作為度量值。針對歐氏距離的不足，動態(tài)時間扭曲（Dynamic Time Warping，DTW）法［3］應運而生，該方法能將軌跡進行壓縮，以找到兩條軌跡間的最小距離。Chen 等［4］又提出了基于代價的編輯距離（Edit Distance on Real Penalty，ERP）的度量方法通過確定懲罰值來度量軌跡相似。而后劉坤等［5］對基于編輯距離的軌跡相似度量方法進行了運動物體的行為分析優(yōu)化，使之更適用于空間移動軌跡。全局匹配的度量方法將空間軌跡整體考慮，以度量完整軌跡的相似性，此類方法對于軌跡點分布均勻軌跡有著較高的準確度，但缺點是時間復雜度過高。

2）基于軌跡點的軌跡相似度量的局部匹配方法。最長公共子序列（Longest Common SubSequence，LCSS）［6］是最早提出的軌跡相似度量方法，累加軌跡點間的判斷值以度量相似。Chen 等［7］根據編輯距離又提出了實序列編輯距離（Edit Distance on Real Sequence，EDR）關注不相似的軌跡點距離。k-最佳連接路徑（k Best Connected Trajectories，k-BCT）法［8］通過建立一些關鍵軌跡點來獲取經過這些關鍵軌跡點附近的軌跡，適用于如旅游之類的模糊軌跡應用場景。弗雷歇距離（Fréchet distance）度量方法［9］，即狗繩距離，走完兩條路徑過程中所需要的最短狗繩長度。朱進等［10］提出了多重運動特征編輯距離方法，以加權編輯距離作為相似性度量。局部匹配雖然解決了全局匹配方法無法度量軌跡部分相似的問題，但帶來了時間復雜度的進一步增加，而同樣通過軌跡點判斷相似的做法，對于軌跡點的分布也有了較高的要求。

3）基于軌跡段的軌跡相似度量方法。最小邊界矩形（Minimum Bounding Rectangle，MBR）法［11］則利用規(guī)則將軌跡分段并簡化，再進行相似判斷。豪斯多夫（Hausdorff）距離法［12］將軌跡分段并將軌跡的三種屬性納入考慮。結構相似距離法［13-14］在此基礎上進行了長軌跡片段劃分。而后，王培等［15］基于Hausdorff 距離又提出一種基于單位時間平均值的時空軌跡相似性度量方法。單向距離（One Way Distance，OWD）方法［16］通過判斷兩條軌跡匹配的軌跡段的距離積分作為軌跡的相似性。王飛等［17］提出了一種面向相似查詢的軌跡索 引 方 法 GeoSAX （Geohash Symbolic Aggregate approXimation），依據數據量的大小對空間動態(tài)劃分后做相似度量工作；室內空間的軌跡相似性度量方法［18］有效地減小了序列誤差。先對軌跡段進行壓縮的方法也有著很好的效果［19］，梯形帶相似聚類算法［20］的做法也是先壓縮軌跡，并以梯形作判定區(qū)域。基于軌跡點的度量方法因為需要考慮每個軌跡點間關系，有著較高的時間復雜度。而基于軌跡段的相似度量方法將度量工作聚焦在了軌跡段上，多適用于有路網軌跡情形，雖提升了度量效率，但卻增加了軌跡劃分或是壓縮等流程，增加了軌跡分析的工作步驟。

由于基于軌跡點的各種相似性度量方法的應用場景和對相似性的定義不同，也伴隨著不同的性能［21］。針對上述方法，對于無路網軌跡，基于軌跡點的相似度量有著較高的時間復雜度，并且對于度量的對象通常為符合條件的軌跡點數的占比，極大地影響了方法的可行性。而基于軌跡段的方法的應用場景為以軌跡段為主要單位的軌跡曲線，如汽車的行駛軌跡的有路網結構的軌跡線路，此類的行駛軌跡多有著固定的軌跡段輪廓。所以，軌跡段的相似度量方法既增加了對軌跡段的劃分或是壓縮等預處理步驟，又只對以段為單位的軌跡作出判斷，針對無路網軌跡網絡的相似度量工作無法匹配。

本文聚焦于針對點軌跡的無路網結構的相似度量方法，提出了全新的基于面積劃分的時空軌跡度量方法，該方法既解決了此類方法時間復雜度高的問題，同時增加了在缺失部分非關鍵軌跡點或軌跡點分布不均勻時的魯棒性，這一點在現(xiàn)有方法中很少被提及并研究。

2 基于面積劃分的軌跡相似度量算法

2.1 TD方法

2.1.1 TD方法的思路

本文基于軌跡間面積劃分原理，提出了針對無路網軌跡全新的空間軌跡相似度量方法，該方法通過對軌跡間的二維空間進行劃分的方式，透過一定的規(guī)則，連接兩條軌跡點的線段形成互不重疊的三角形區(qū)域并累計作軌跡面積。同時，確定單位軌跡長度的面積閾值，通過軌跡面積和該閾值的對比來確定兩條軌跡是否相似。

TD 軌跡相似度量方法的原理如圖1 所示。軌跡PA和軌跡PB兩條軌跡間的部分，由虛線分割面積，形成S1～S8到的8個互不重疊的三角形，累加此8 個三角形的面積得到軌跡面積用以相似度量。

圖1 面積劃分示意圖Fig.1 Schematic diagram of area division

2.1.2 TD方法的劃分和累加規(guī)則

TD 方法通過構建規(guī)則分步確認三角形的三邊，避免出現(xiàn)三角形面積重復累加。

劃分和累加的循環(huán)思路如下：

步驟1 得到三角形邊L1。連接a 與b 點得到三角形邊L1。且在循環(huán)開始時，a與b分別為軌跡PA和PB的第一個點。

步驟2 確認三角形邊L2。對比軌跡點a 與b+1 連線和軌跡點b 與a+1 連線的長度，即圖中帶箭頭直線i 與j 的長度。并取較短者連接，得到此線段為L2。

圖2 “指針”法示意圖一Fig.2 Schematic diagram 1 of“pointer”method

步驟3 得到L3和三角形面積的計算。由L1和L2確認的三角形，可以得到第三條邊L3。計算該三角形面積，累加進軌跡間總面積sum。

步驟4 循環(huán)和終止。步驟2中連接較短直線后，對應的a 或b 將進入下一個軌跡點a+1 或b+1，并回到步驟1 繼續(xù)計算。當a或b進入軌跡末點時，結束循環(huán)。

圖3 “指針”法示意圖二Fig.3 Schematic diagram 2 of“pointer”method

2.2 模型的構建

TD 方法使用的是軌跡間單位長度的面積作為軌跡距離。從兩條軌跡的第一個點a1和b1開始，得到兩條軌跡的面積SA（Sum Area）為：

其中，area(ak，ag，ak+1)表示ak、bg和ak+1三點所圍成三角形的面積。

得到兩條軌跡的平均長度為：

最后得到該方法下單位長度面積（Area Per Length，APL），即軌跡距離：

當使用APL 度量軌跡相似度時，需要設置軌跡距離的度量閾值γ，對比距離值是否超過閾值。

為了更好地與其他軌跡相似度量方法作對比，該方法引入了相似度（Similarity）的定義。同時，該相似度很好地去除了軌跡距離的單位，也能使不同長度范圍的軌跡有著不同的度量敏感度，如長度量值大的軌跡間在軌跡距離相對較大的情況下也可判斷它們?yōu)橄嗨啤Ｏ嗨贫鹊挠嬎愎綖椋?/p>

該相似度代表的是考慮軌跡總長的情況下考慮的軌跡相似程度，該數值越大表示軌跡越相似，而不同的應用場景和閾值設置下，應根據軌跡距離的閾值來設置相似度的閾值。

軌跡相似度量的TD方法的偽碼描述如下：

算法 軌跡相似度量的TD方法。

輸入 兩 條 軌 跡 的 軌 跡 數 據PA={a1，a2，…，an}和PB={b1，b2，…，bm}；軌跡間單位長度面積閾值γ；

輸出 輸出兩條軌跡的單位長度面積APL 和相似度Similarity；輸出兩條軌跡的相似性，即是否相似。

1） for each ak∈PAdo //對點ak在軌跡集合PA中

2） if each akis the first point then

3） a ←0 //由元素a記錄軌跡A的索引

4） b ←0； //由元素b記錄軌跡B的索引

6） L1←distance(a，b) //計算a與b對應直線長度

7） L2_AtoB ←distance(a，b+1) //設置了“指針”

8） L2_BtoA ←distance(b，a+1) //設置了“指針”

9） if L2_AtoB ≤L2_BtoA then

10） L2←L2_AtoB //得到L2長度

11） b ←b+1 //元素b的索引進入B下一個點

12） L3←distance(b，b+1) //計算L3長度

13） SA ←SA+area(L1，L2，L3)//L1、L2和L3形成的三角形面積累加入sum

14） else //如果L2_AtoB更長

15） L2←L2_BtoA //使L2得到L2_BtoA的數值

16） a ←a+1 //元素a的索引進入軌跡A下一個點

17） L3←distance(a，a+1) //計算L3長度

18） SA ←SA+area(L1，L2，L3) //累加面積

20） if b is last point of the trajectory then

21） exit； //若b進入軌跡末端，則結束循環(huán)

23）end for

24）for each ak∈PAdo

25） L ←L+distance(a，a+1)； //計算軌跡A的長度

26）end for

27）for each bk∈PBdo

28） L ←L+distance(a，a+1)； //計算軌跡B的長度

29）end for

30）Length ←(LA+LB)/2 //計算長度平均值

31）APL ←SA/Length //計算軌跡間平均長度的面積

32）Similarity=1-SA/(Length×Length)

3 實驗結果與對比

3.1 對照組設置

3.1.1 對照組的選擇

本文選取了最具代表性的基于軌跡點的軌跡相似度量方法最長公共子序列（LCSS）方法和有著較高魯棒性的弗雷歇距離（Fréchet distance）度量方法進行對比實驗。

而由于基于軌跡段的相似判斷方法主要針對有路網結構的軌跡使用，無法形成對比，所以在本節(jié)的實驗中也不加以討論。

定 義 兩 條 軌 跡 點 集 合 為PA={a1，a2，…，an}和PB={b1，b2，…，bm}，最長公共子序列方法的表達式為：

其中：LCSS(ak，bg)為軌跡PA在軌跡點ak和序列PB在軌跡點bg前的最大公共子序列長度；dist(ak，bg)為PA軌跡中的第ak個點與PB序列中第bg個點間的距離；γ 為設置的距離閾值。可以看出，該方法獲取的是符合點間距離閾值的軌跡點數，用來衡量軌跡的相似。

弗雷歇距離度量方法表達式為：

而弗雷歇距離度量方法將最長公共子序列方法中只關注點與點的距離轉化成點與軌跡的距離，即dist(ak，bg)變?yōu)閐ist(ak，PB)從而增加了該算法的魯棒性。

3.1.2 閾值與度量值

TD 方法中設置了單位長度面積為m km2的閾值；對應于兩種基于軌跡點相似度量方法設置了m km 的軌跡點距離閾值，并使用了相似度來查看相似程度。

在對比實驗中弗雷歇距離度量方法和最長公共子序列方法的度量值最大均為100%，表示相似度最高，度量值表達式為：

3.2 軌跡缺失下的敏感度

本節(jié)的實驗對比數據使用了船舶軌跡應用場景下的AIS數據。選擇了兩條真實的船舶軌跡數據，PA軌跡有660 個軌跡點，PB軌跡有650 個軌跡點。同時，在分別隨機刪除200、300 和400 個軌跡點時的相似情況設置了20 個平行對照組取均值，所得到的各方法的相似度量如表1所示。

在表1和圖4中可以發(fā)現(xiàn)，軌跡缺失后的度量值發(fā)生的變化。首先，LCSS 方法在軌跡點缺失后的度量值明顯地降低了，在缺失后的相似度判斷上有著明顯的誤差。而TD方法和Fréchet distance 度量方法在軌跡點隨機缺失的情況下都有著很好的魯棒性。

表1 軌跡點隨機缺失的軌跡相似度量值Tab.1 Trajectory similarity measurement with randomly missing trajectory points

圖4 軌跡點隨機缺失的軌跡相似度量變化Fig.4 Trajectory similarity measurement change with random missing trajectory points

在表2 中，發(fā)現(xiàn)LCSS 和Fréchet distance 度量方法的耗時遠大于軌跡劃分的方法，且隨著軌跡點數量的增加，時間復雜度T(n)=O(n×m)將呈指數級增長。而同樣的軌跡點數量下，三角分割的軌跡相似度量方法則將時間復雜度大幅度減低。從表2 中可以看到，在此案例給出的軌跡中，TD 方法相對于兩種軌跡點劃分方法的耗時減小了接近90%。

表2 軌跡點隨機缺失的軌跡相似度量耗時 單位：sTab.2 Trajectory similarity measurement time with randomly missing trajectory points unit：s

3.3 不同位置關系的空間軌跡相似判別

此節(jié)設置了4 種特殊的軌跡間關系進行對比，分邊為繞圈、折返、軌跡相交、軌跡交叉且疏密不均的軌跡間關系。

4 種軌跡間關系代表了在各種軌跡應用場景下的特殊且不易判斷相似的部分截取軌跡：繞圈是軌跡出現(xiàn)返回的圓周軌跡；折返是軌跡出現(xiàn)原路的折返；軌跡間相交是兩條判斷軌跡間的關系出現(xiàn)相交但仍然是相似軌跡的情況；軌跡間交叉且疏密不均是特殊的情況，指軌跡呈大角度交叉，完全不相似，但兩個軌跡的軌跡點疏密分布非常地不均勻。

四種情況均采用了算法隨機生成30 組數據，設置2 為軌跡距離閾值，如圖5 為各種不同位置關系軌跡的一次隨機生成數據繪制的圖像。

對于相似度的判斷，100%的相似度定義應指兩條軌跡的完全重合。所以，由圖5 可見，繞圈、折返和相交情況的兩軌跡的相似度應趨近于100%，而不到達100%。而對于軌跡間交叉且疏密不均的相似情況，該截取段在如航空和海運中經常出現(xiàn)，這種相似情況下，相似度應較前三種情況低，但不應出現(xiàn)相似度過低的判斷。

各方法下相似度的平均值如表3 所示。其中，TD 方法得到的結果包括相似度和軌跡距離。

圖5 不同軌跡間關系示例Fig.5 Example of relationship between different trajectories

表3 不同軌跡間相對關系的相似度量值 單位：%Tab.3 Similarity measurement of relative relationship between different trajectories unit：%

由表3可知：

1）表中的前三種關系為兩條空間軌跡相似，可以發(fā)現(xiàn)在出現(xiàn)復雜的軌跡間關系時，LCSS 方法在度量情況出現(xiàn)了誤差，F(xiàn)réchet distance 度量方法在繞圈軌跡情況下也出現(xiàn)了部分的段判斷為不相似。

2）Fréchet distance 度量方法對于前三種情況是否相似的判斷雖然準確，但在相似度數值的確定下同樣體現(xiàn)了軌跡點判斷方法的不足，該三種情況的度量值不應出現(xiàn)百分百的相似度。而第四種情況，該方法則出現(xiàn)了較大的誤差，對于交叉卻相似情況的軌跡，單純依照軌跡點的判斷使相似度在疏密不均下過低。所以，F(xiàn)réchet distance 度量方法在后三種情況的判斷上均差于TD方法。

3）軌跡交叉且軌跡點疏密不均勻的第四種情況暴露了基于軌跡點相似度量的通病，以軌跡點相似個數來度量軌跡相似度的可靠性在軌跡點疏密分布不均勻的情況下非常地不可靠。如64.70%的數據會產生兩條軌跡有大部分軌跡段相似的誤判，而這也非全局判斷方法下的通病。而TD方法在此情況下依舊能夠判斷軌跡的相似情況。

3.4 實驗結論

1）TD 方法的空間軌跡相似度量彌補了最大公共子序列方法對于軌跡缺失下判斷誤差的問題，同時也有著弗雷歇距離度量方法的魯棒性。

2）TD 方法的空間軌跡相似度量方法相比基于軌跡點的相似度量方法有著極低的時間復雜度，使算法的執(zhí)行速度得到了極大的提升。

3）對于復雜的軌跡運行情況下，不同的疏密情況對TD方法的空間軌跡相似度量方法影響很小，相比基于軌跡點的相似度量方法有著顯著優(yōu)勢。這樣的差異來源于度量方法的度量思路，基于軌跡點的度量方法對比每一個點的情況，再查看相似點所占比例來度量相似；而本文中提出的TD 方法，對單位長度的軌跡間面積設置閾值，是對軌跡間整體的考量。

4 結語

本文提出了TD 的軌跡相似度量方法用于空間軌跡相似度量，該方法有著相似度量準確、時間復雜度低的特點，在對船舶的AIS 數據進行不同情景下的實驗中也取得了不錯的效果，對比基于軌跡相似度量方法，發(fā)現(xiàn)該方法對于軌跡缺失和軌跡點分布不均勻下有著較好的魯棒性。同時，不同于之前對于軌跡點和軌跡段的相似度量方法，本文提出的空間軌跡度量TD方法有著不錯的適用性，也為軌跡相似度量方法提供了全新的思路，為進一步的軌跡挖掘工作打下了基礎。在后續(xù)的工作中，可對時空軌跡的相似度量進行應用，增加時空維度來更加精確化度量以應用于更多的場景。