一種改進的航跡聚類方法

張勇，張建偉，韓云祥

（1.四川大學空天科學與工程學院，成都610065；2.四川大學計算機學院，成都610065；3.四川大學視覺合成圖形圖像技術國家級重點實驗室，成都610065）

0 引言

隨著移動設備的廣泛使用，大量的移動軌跡數據被存儲記錄，急劇增加的數據量迫切需要高效的軌跡處理算法，分析軌跡數據特征，用于監測和管理熱點地區交通狀況。在空中交通運輸管理領域，研究航空器的運動軌跡，可用于改進現有進場飛行程序結構[1]；同時便于管制員理解機場空域交通結構，協助其對進場航班進行排序，分析離群航跡產生原因降低潛在安全風險[2]；分析航班進場時間的相關特征，分離不同進場飛行路徑，預測航班到達時間[3]。航跡分析中的重要一步是對航空器通過不同進場路徑產生的航跡簇進行合理分離，航跡聚類算法被廣泛用于分析進場航班的交通流量特征[4]。

近年來有許多研究者提出了不同的航跡聚類方法[5-7]，文獻[8]提出采用主成份分析（PCA）的方法降低數據維度，并用基于模型和密度的聚類方法得到聚類航跡，主要考慮雷達覆蓋區的入口點航跡的聚類。文獻

[9]提出了一種處理時間序列的改進聚類算法，該算法能夠降低傳統聚類算法的時間復雜度，但是該算法聚類過程是依據第一次計算的序列距離，聚類簇之間使用最小距離衡量，無法準確刻畫聚類簇之間的距離關系，抗噪聲能力有待提高。文獻[1]提出一種基于對應雷達軌跡點逆向比對方法的航跡間相似性測度模型，應用層次聚類法對航跡數據集進行聚類分析，改進了航跡間相似度的計算方法，處理小規模航跡數據效果較好，但是聚類過程復雜度較高不適用大規模數據。文獻[10]利用CURA 算法實現航跡聚類，通過比較聚類集平均航跡和代表航跡分別與標準飛行程序的關系，建立了飛行程序軌跡表示模型。文獻[11]等提出的基于航跡點法向距離的相似性度量算法，但該方法均未解決因飛行速度不同而引起的航跡點采樣間隔不相同的問題。文獻[12]提出了一種融合匈牙利算法的無監督層次聚類算法并將該算法與譜聚類算法進行比較得出該算法在時間復雜度表現上優于傳統譜聚類算法。

通過以上相關算法的研究發現，其主要問題體現在兩個方面：航跡間相似度的計算不夠準確且時間復雜度較高；算法合并簇與更新距離矩陣都為單步進行，聚類過程中算法收斂速度慢，抗噪聲能力差，航跡中離群航跡重復計算浪費了較多計算資源。本文提出采用快速DTW（Fast Dynamic Time Warping）算法[13]計算航跡距離，每次迭代后舍棄離群航跡，合并航跡簇采用并行計算的方式，相較于目前常用的航跡聚類算法，改進聚類算法效率提高了20%，加快了現有航跡數據的處理速度。

1 軌跡距離/相似度計算方法

航跡分類中的關鍵問題是如何選擇航跡間的相似性度量方法，不同航跡之間航跡點數量不同，傳統的歐氏距離計算方法對于采樣點數不一樣的兩條航跡之間的衡量效果較差，需要通過插值等方法將軌跡點一一匹配，這樣對于大規模航跡處理來說效率較低。本文采用快速DTW 算法取代歐氏距離計算方法和DTW 算法來對航跡距離進行計算，在計算航跡簇之間的距離上應用平均距離以取代最大最小距離，使其在時間復雜度與相似度衡量效果上表現更好。

相關符號及含義：

T：航跡集合nT：航跡總數量，即ti：某一條進場軌跡，

ni：編號為i的航空器飛行軌跡中軌跡點的總數

p(i,j)：組 成 一 條 航 跡 的 單 個 航 跡點，

C： 聚 類 后 得 到 的 軌 跡簇

k：航跡聚類得到聚類簇的個數

Ci：第個聚類簇第個聚類簇內包含的航跡數目，每一條航跡的航跡簇

Cout：離群航跡構成的軌跡簇

nCout：離群航跡數量：第個聚類簇和第j個聚類簇之間的距離

α：航跡Ci與距離航跡Ci最近航跡之間的DTW距離

Dstop：聚類算法終止判定閾值

ndrop：離 群 航 跡 簇 的 判 定 閾 值 ，當

x表示航跡點p(i,j)的橫坐標；y表示航跡點p(i,j)的縱坐標；z表示航跡點p(i,j)的高度；vh表示航空器在航跡點p(i,j)的水平速度；vv表示航空器在航跡點p(i,j)的垂直速度；φ表示航空器在航跡點p(i,j)的航向角；t表示航空器在航跡點p(i,j)所在位置距離機場所需要的時間。進場航空器的航跡集合為，每架進場航空器對應唯一航跡，航跡點組成完整航跡每條航跡點的數量由其進場路線以及航跡點的采樣頻率相關，對于采樣點數過少，缺乏對航跡特征完整記錄的航跡需要舍棄，本文采用的航跡數據在預處理階段已經剔除殘缺航跡。

1.1 聚類參數選取

由于交通管制或極端天氣等原因航空器在進離場過程中會偏離既定線路產生離群航跡，這一部分航跡所占比例較小，對進離場航跡數據分析缺乏實際意義，需要在聚類過程中舍棄。對于判斷航跡α是否為離群航跡主要參考兩個指標：①航跡α與距離航跡α最近航跡之間的DTW 距離Dnearest( )α>Dstop，②航跡α屬于航跡簇滿足以上條件任何一條即可判斷航跡α屬于離群航跡。

由離群航跡定義可知，最終航跡聚類簇個數k與舍棄的離群航跡數量nCout取決于參數：Dstop、ndrop，減小Dstop，離群航跡數目nCout會增加而聚類簇數目k會減少，增大ndrop同樣會使nCout增加。對于大量數據集的參數設定需要耗費大量的時間測試，才能得到最佳聚類模型。本文擬采用抽樣的方法，在總航跡樣本中隨機選取10%作為測試航跡，將聚類結果可視化展示，通過航跡數據在二維空間中的分布圖可以直觀地獲取航跡包含的聚類數目信息，由測試結果調節參數

Dstop，Dnearest。

1.2 航跡間距離/相似性

動態時間規整（DTW）是處理時間序列的一種常用技術。算法主要思想是改變航跡點對應匹配計算航跡距離的方法，通過扭曲時間來對某一航跡點重復采樣，擴展匹配路徑；通過迭代的方式從所有可能的變換路徑中找出距離最短的匹配規則。

對于給定的兩條航跡t1,t2,對應的DTW 計算公式（1）：

其中DTW(i,j)為航跡t1的前個航跡點組成的航跡路徑與航跡t2的前j個航跡點組成的路徑的DTW距離，d(pi,dj)是指航跡t1的第個航跡點組成的航跡路徑與航跡t2的第j個航跡點之間的歐氏距離。

DTW 相較于歐幾里得距離無需要對數據進行插值去噪以及將航跡點數目匹配相等操作，能夠計算采樣數目不相等的航跡距離，但是有一個較為明顯的缺點是其時間復雜度較高，對于大量數據的處理較為吃力。

為了克服傳統DTW 時間復雜度過高的缺點，許多對DTW 改進方法被相繼提出[13]，其算法主要通過兩種方式加速算法計算：①約束搜索空間范圍，減少搜索次數；②細化搜索步長，確定搜索路徑。本文采用快速DTW 算法計算航跡間距離，加快計算速度。

采用快速DTW 算法構造如下航跡相似度矩陣D表示航跡集合T中所有航跡相互之間的距離，式（2）：

1.3 航跡簇之間的距離

由于合并層次聚類經常被使用，該方法需要度量簇與簇之間的距離，對于給定的聚類簇C1=常用的簇間距離度量方法如下：最小距離：定義簇間距離為兩個簇間最近的兩個點之間的距離，最大距離：定義簇間距離為兩個簇間最遠的兩個航跡間的距離，平均距離：定義簇間距離為取自兩個不同簇的所有點對間距離的平均值，式（3）：

最大、最小距離度量比較極端，對噪聲點和離群航跡較為敏感，平均距離是最大最小的折中，一定程度上可以克服離群點的影響。本文采用平均距離計算航跡簇之間的距離，用以克服離群航跡對聚類簇的影響。

2 航跡聚類算法

聚類就是將一組觀測對象劃分成不同的種類或簇，應用不同的聚類算法將相似的對象劃為同一類，不相似的對象劃為不同類。本文采用快速DTW 算法進行相似性度量后，應用剪枝及時剔除離群航跡，并行聚類加快收斂速度，實現航跡聚類過程的改進。

2.1 改進的層次聚類

在層次聚類算法中，主要分為凝聚的層次聚類和分裂的層次聚類，凝聚層次聚類是一種自底向上的聚類方法，該方法以單個對象為初始簇，逐步聚合與其距離最近的簇，直到某個聚類終止條件被滿足。

假設聚類航跡集T航跡對象個數為nT，則其距離矩陣大小為nT×nT，則基于平均距離的凝聚層次聚類算法的基本過程如圖1 所示：

（1）設每條航跡為單獨為一簇，根據距離函數計算每個簇之間的距離D(Ci,Cj)，得到初始化距離矩陣DT；

（2）查找距離最近的兩個簇，并將它們合并為一個簇，此時簇的個數減1；

（3）根據距離函數重新計算新簇和舊簇之間的距離；

（4）重復（2）和（3）直到簇的個數達到預期設定值k。

由圖1 可知，經典凝聚層次聚類算法在計算完距離矩陣后并沒有對噪點進行處理，不僅浪費計算的時間與空間同時降低了聚類結果的準確度；每合并完一個簇，重新計算合并后的簇對象之間的距離更新距離矩陣，并在新距離矩陣中搜索最小距離，將對應的數據對象合并，單步合并操作，算法收斂速度慢，對于大型數據集的聚類，時間開銷過高。

改進算法具體如圖2 所示。

（1）輸入航跡數據T，將每條航跡初始化為一個航跡簇，采用FastDTW 算法計算兩兩航跡簇之間的距離，得到初始距離矩陣D；

（2）計算每條航跡與其他航跡的最小距離α，由最小距離α及航跡簇內的航跡數量|Ci|判定航跡簇Ci后續操作：①加入隊列Q，繼續與其他簇合并；②該航跡簇為單獨一類航跡，加入最終航跡聚類集合C；③該航跡簇內航跡屬于離群航跡，將簇航跡加入離群航跡簇Cout。

（3）將隊列內Q內航跡簇之間的距離按照升序排列。

（4）對隊列Q內航跡簇按照合并規則進行合并。具體合并規則為：初始化每個航跡簇標志位置為0，flag=1，依次對隊列Q內每個距離元素，判斷其對應的兩個航跡簇是否在此輪迭代中已合并到某個簇中，此時分為3 種情況：①兩個航跡簇都沒有發生過合并操作，即兩個航跡簇標志位都不為0，則將這兩個航跡簇合為一簇，同時將標志位設為flag，合并結束后flag+=1；②兩個航跡簇有一個簇被合并到其他簇中，即其中一個航跡簇的標志位不為0，則將另外一個航跡簇合并到該簇中標志位置為該航跡簇的標志值；③兩個航跡簇分別合并到了不同的簇中，即兩個航跡簇的標志位都不為0，則將這兩個簇合為一個簇，標志位統一。

圖1 經典層次聚類算法流程

（5）判斷合并的航跡簇數量是否大于1，若是，則轉到步驟（6）；若否，則合并后的航跡簇為單獨一類航跡，將其加入最終航跡聚類集合C，返回航跡聚類結果：航跡聚類集合C、離群航跡集合Cout；

（6）將所有標志位相等的航跡簇合并為一簇，完成合并后，根據簇間距離計算公式，計算兩兩航跡簇之間的距離，更新距離矩陣D，回到步驟（2）。

由以上算法描述得出剪枝操作體現如圖3（a）所示：合并操作之前，求得該航跡與其他航跡的最近距離α，若該航跡簇與其他航跡簇距離較遠且該航跡簇內航跡較少（nCindrop∧α

并行操作體現如圖3（b）所示：區別于一般聚類算法，單步合并距離最小的航跡簇，更新距離矩陣D。改進算法提出建立優先隊列Q存儲待聚類的航跡簇，對優先隊列Q所對應的航跡簇同時進行合并簇操作，優先隊列Q內航跡簇全部完成聚類后再依據航跡簇間距離計算公式更新距離矩陣，完成一次迭代。

通過剪枝與并行聚類加快了算法的收斂速度，降低整個聚類過程的時間復雜度。

圖2 基于平均距離的改進層次聚類算法

圖3

2.2 算法復雜度分析

對于經典航跡聚類算法，假設待處理航跡數量為n，初始時航跡簇的個數即為n，由fastDTW 算法計算簇間距離公式，簇間初始距離個數為n×(n-1)/2，第一次查找距離最近的兩個航跡簇Cr,Cs，，從n×(n-1)/2 個距離對象中搜索，需要進行次對比操作，復雜度為O(n2)。每次合并簇得得個數減1，新簇與原簇的距離根據簇間距離計算公式（3）重新計算。第二次合并簇，航跡簇的個數為n-1，需要從（n-1)×(n-2)/2 個距離中查找最小值，復雜度仍然是O(n2)，依次類推，假設簇的個數為k。 合并簇比較大小的次數為通常情況下最終聚類得到的簇的個數k遠遠小于樣本數n，則總比較次數為(n3-n)/6 次，更新距離矩陣時，計算次數總計(n+k-2)[(n-k-1)/2]，總的復雜度為O(N3)。

本文改進的聚類算法，由fastDTW 算法計算航跡間距離，簇間初始距離個數為n×(n-1)/2，每次迭代分別對每個航跡簇求取最小距離，比較次數為n(n-1)，經過剪枝操作后剩余航跡簇數目n'，n'≤n；再對n'個航跡簇進行合并簇計算次數為n'，合并后航跡簇個數為n''，n''≤n'/2，由式（3）更新距離矩陣。每次迭代總計算次數為考慮最差的收斂情況，即n'=n，則首次迭代計算次數為(3n2-n)/2，復雜度為O(n2)。第二次迭代計算次數為，依次類推，總的迭代次數為log2n，所以改進算法總計算次數為3n2-3，復雜度為O(n2)。

3 實驗結果分析

3.1 實驗環境及數據來源

本文數據處理與算法實現過程采用Python 語言實現，其硬件平臺為Windows10×64 位系統，內存為32.0GB，處理器為Intel Core i7-7700@3.6GHz CPU。

使用的是2019.6-2019.10 雙流國際機場航班進港ADS-B 數據，其數據包含進場航空器的時間及經緯度坐標，在數據預處理階段已將其經緯度坐標通過墨卡托公式轉化為以機場為中心的機場坐標系，數據預處理階段已經將采樣點過少的殘缺航跡剔除，每條航跡平均包含100 個采樣點。

3.2 聚類性能評價指標

在聚類研究中，對聚類性能的評價存在大量指標，指標的評價主要是基于簇內及簇間相似度，為保證簇內相似度盡可能高，簇間相似度盡可能低，有以下兩種度量標準：

（1）緊湊度，用來衡量簇內樣本點之間相似程度的指標。

（2）分離度，指不同簇的差異是否足夠大。

上述兩種度量標準在實際的聚類度量指標中，有很多量化指標對其進行有效性評價。如下兩種度量：

戴維森堡丁指數（Davies-Bouldin Index，DB）：計算的是任意兩個類的類內平均距離（即CP 值）之和與兩聚類中心距離的比值，求最大值。DB 越小意味著類內距離越小，同時類間距離越大，其計算為式（4）：

鄧恩指數（Dunn Validity Index，DVI）：通過計算任意兩個簇間的最短距離與任意簇內對象的最大距離。DVI 越大類間距離越大，類內距離越小，其計算為式（5）為：

3.3 實驗結果分析

實驗對改進聚類算法的參數設置以及聚類最佳簇數進行了分析，對不同聚類參數的選取進行了調優，得出最佳聚類結果。對比測試了DTW 算法、快速DTW算法、傳統層次聚類（HC）、改進層次聚類算法（IHC）的聚類結果，并從算法時間開銷、聚類性能兩個指標進行評價。

（1）不同算法運行時間對比

以下實驗結果在上述硬件環境下進行測試，測試數據集為雙流機場航班進場航跡，測試航跡數據數目：nT，航跡點數目：npoint，聚類結果可視圖如圖5 所示。

表1 算法時間對比

通過實際運行數據損耗時間比較可知，由表1 對比以上四種聚類算法，本文提出的FastDTW+IHC 聚類算法明顯縮短了聚類算法運行時間，對于較大的數據集的聚類，顯著提升了聚類效率。

圖4

圖5 不同進場航路航跡聚類二維平面圖

（2）參數選取對聚類結果的影響

如圖6 所示，當增大離群航跡數判定閾值ndrop，將會減少最終航跡聚類簇數目，增大離群航跡簇Cout內航跡數目；同理增大聚類終止閾值Dstop，亦會減少最終航跡聚類簇數目。

由上述結果可知，增大ndrop值時航跡聚類簇數目將會減少，當ndrop的值增大的一定值時，航跡簇的數目會維持在一個固定值，此時所得到的航跡簇數目為較為貼近真實航跡簇數目。對于航跡簇已知的聚類問題，增大ndrop值至航跡聚類簇數和已知條件一致。同理可調節聚類終止閾值Dstop。

（3）各類聚類算法性能指標

為驗證各類算法聚類結果有效性，采用上文所提到的兩種聚類性能評價指標，分別計算上述算法在最佳聚類簇數下得到的DB 指標值和DVI 指標值。表2所示為各算法在最佳聚類簇下得到的評價指標大小。

圖6

表2 算法性能指標比較

由上述指標結果可以看出，本文改進的航跡聚類算法（FastDTW+IHC）DVI 值最大、DB 值最小，DTW+HC 算法得到的DVI 值最小、DB 值最大，表明本文算法取得的聚類效果最佳，DTW+IHC 算法得到的結果次之，DTW+HC 算法聚類效果最差。由以上得出快速DTW 算法相對于普通DTW 算法對于相似性的刻畫更加準確，所以指標反映出來的結果更優；改進層次聚類算法在聚類過程中及時剔除了離群航跡，減少噪聲干擾，所以比經典聚類算法在航跡聚類的準確度上表現更好。

4 結語

本文提出的基于快速DTW 距離度量的并行剪枝層次聚類算法，通過在計算不同軌跡之間的相似度過程中采用快速DTW 算法取代計算效果較差的歐氏距離度量算法；合并簇與更新距離矩陣由單步運算改為批次運算，加快收斂速度；對于遠離聚類中心的離群軌跡及時剪枝，減少不必要的合并簇與更新距離矩陣操作。通過處理大規模實際運行航跡數據，可視化聚類過程，相較于目前常用的層次聚類算法時間降低時間復雜度，該改進算法可應用于多種軌跡數據的聚類研究。