張勇，張建偉，韓云祥

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

0 引言

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

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

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

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

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

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

相關(guān)符號及含義：

T：航跡集合nT：航跡總數(shù)量，即ti：某一條進(jìn)場軌跡，

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

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

C： 聚 類 后 得 到 的 軌 跡簇

k：航跡聚類得到聚類簇的個數(shù)

Ci：第個聚類簇第個聚類簇內(nèi)包含的航跡數(shù)目，每一條航跡的航跡簇

Cout：離群航跡構(gòu)成的軌跡簇

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

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

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

ndrop：離 群 航 跡 簇 的 判 定 閾 值 ，當(dāng)

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

1.1 聚類參數(shù)選取

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

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

Dstop，Dnearest。

1.2 航跡間距離/相似性

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

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

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

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

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

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

1.3 航跡簇之間的距離

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

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

2 航跡聚類算法

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

2.1 改進(jìn)的層次聚類

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

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

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

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

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

（4）重復(fù)（2）和（3）直到簇的個數(shù)達(dá)到預(yù)期設(shè)定值k。

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

改進(jìn)算法具體如圖2 所示。

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

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

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

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

圖1 經(jīng)典層次聚類算法流程

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

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

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

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

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

圖2 基于平均距離的改進(jìn)層次聚類算法

圖3

2.2 算法復(fù)雜度分析

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

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

3 實驗結(jié)果分析

3.1 實驗環(huán)境及數(shù)據(jù)來源

本文數(shù)據(jù)處理與算法實現(xiàn)過程采用Python 語言實現(xiàn)，其硬件平臺為Windows10×64 位系統(tǒng)，內(nèi)存為32.0GB，處理器為Intel Core i7-7700@3.6GHz CPU。

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

3.2 聚類性能評價指標(biāo)

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

（1）緊湊度，用來衡量簇內(nèi)樣本點之間相似程度的指標(biāo)。

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

上述兩種度量標(biāo)準(zhǔn)在實際的聚類度量指標(biāo)中，有很多量化指標(biāo)對其進(jìn)行有效性評價。如下兩種度量：

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

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

3.3 實驗結(jié)果分析

實驗對改進(jìn)聚類算法的參數(shù)設(shè)置以及聚類最佳簇數(shù)進(jìn)行了分析，對不同聚類參數(shù)的選取進(jìn)行了調(diào)優(yōu)，得出最佳聚類結(jié)果。對比測試了DTW 算法、快速DTW算法、傳統(tǒng)層次聚類（HC）、改進(jìn)層次聚類算法（IHC）的聚類結(jié)果，并從算法時間開銷、聚類性能兩個指標(biāo)進(jìn)行評價。

（1）不同算法運(yùn)行時間對比

以下實驗結(jié)果在上述硬件環(huán)境下進(jìn)行測試，測試數(shù)據(jù)集為雙流機(jī)場航班進(jìn)場航跡，測試航跡數(shù)據(jù)數(shù)目：nT，航跡點數(shù)目：npoint，聚類結(jié)果可視圖如圖5 所示。

表1 算法時間對比

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

圖4

圖5 不同進(jìn)場航路航跡聚類二維平面圖

（2）參數(shù)選取對聚類結(jié)果的影響

如圖6 所示，當(dāng)增大離群航跡數(shù)判定閾值ndrop，將會減少最終航跡聚類簇數(shù)目，增大離群航跡簇Cout內(nèi)航跡數(shù)目；同理增大聚類終止閾值Dstop，亦會減少最終航跡聚類簇數(shù)目。

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

（3）各類聚類算法性能指標(biāo)

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

圖6

表2 算法性能指標(biāo)比較

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

4 結(jié)語

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