張勇，張建偉，韓云祥

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

0 引言

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

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

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

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

1 軌跡距離/相似度計(jì)算方法

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

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

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

ni：編號(hào)為i的航空器飛行軌跡中軌跡點(diǎn)的總數(shù)

p(i,j)：組 成 一 條 航 跡 的 單 個(gè) 航 跡點(diǎn)，

C： 聚 類 后 得 到 的 軌 跡簇

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

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

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

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

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

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

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

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

1.1 聚類參數(shù)選取

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

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

Dstop，Dnearest。

1.2 航跡間距離/相似性

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

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

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

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

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

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

1.3 航跡簇之間的距離

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

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

2 航跡聚類算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3

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

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

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

3 實(shí)驗(yàn)結(jié)果分析

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

本文數(shù)據(jù)處理與算法實(shí)現(xiàn)過程采用Python 語言實(shí)現(xiàn)，其硬件平臺(tái)為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)場航空器的時(shí)間及經(jīng)緯度坐標(biāo)，在數(shù)據(jù)預(yù)處理階段已將其經(jīng)緯度坐標(biāo)通過墨卡托公式轉(zhuǎn)化為以機(jī)場為中心的機(jī)場坐標(biāo)系，數(shù)據(jù)預(yù)處理階段已經(jīng)將采樣點(diǎn)過少的殘缺航跡剔除，每條航跡平均包含100 個(gè)采樣點(diǎn)。

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

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

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

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

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

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

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

3.3 實(shí)驗(yàn)結(jié)果分析

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

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

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

表1 算法時(shí)間對比

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

圖4

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

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

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

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

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

為驗(yàn)證各類算法聚類結(jié)果有效性，采用上文所提到的兩種聚類性能評價(jià)指標(biāo)，分別計(jì)算上述算法在最佳聚類簇?cái)?shù)下得到的DB 指標(biāo)值和DVI 指標(biāo)值。表2所示為各算法在最佳聚類簇下得到的評價(jià)指標(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)層次聚類算法在聚類過程中及時(shí)剔除了離群航跡，減少噪聲干擾，所以比經(jīng)典聚類算法在航跡聚類的準(zhǔn)確度上表現(xiàn)更好。

4 結(jié)語

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