丁建立，黃天鏡，徐俊潔，王 靜

(中國(guó)民航大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300300)

0 引 言

在GPS定位、目標(biāo)探測(cè)技術(shù)快速發(fā)展的時(shí)代，為了保障飛機(jī)飛行安全，需要存儲(chǔ)和分析大量的飛行相關(guān)的時(shí)空軌跡數(shù)據(jù)。民航飛行時(shí)空軌跡數(shù)據(jù)包含了經(jīng)緯度坐標(biāo)、記錄時(shí)間、飛行高度、飛行速度、航向等多種屬性[1]。在實(shí)際飛行中，民用飛機(jī)一般按照標(biāo)準(zhǔn)飛行程序，依靠地面空中交通管制人員的指揮來(lái)調(diào)配飛行[2]，但特殊情況會(huì)出現(xiàn)實(shí)際航跡偏離標(biāo)準(zhǔn)程序的情況，通過(guò)對(duì)軌跡數(shù)據(jù)的檢測(cè)可以發(fā)現(xiàn)偏離正常飛行模式的軌跡[3]，保障飛行安全。

已有的軌跡異常檢測(cè)算法主要分為以下4類：基于統(tǒng)計(jì)的方法、基于距離的方法、基于密度的方法和基于聚類的方法[4,5]。以上方法并沒(méi)有充分利用軌跡的類型、位置、速度和方向等多維特征，而傳統(tǒng)的聚類的方法主要采用距離作為相似度的評(píng)價(jià)指標(biāo)，認(rèn)為兩個(gè)對(duì)象的距離越近，其相似度就越大，忽略了飛行軌跡的數(shù)據(jù)點(diǎn)的有序性以及數(shù)據(jù)點(diǎn)本身具有的航向、速度等特征，不能有效挖掘飛行軌跡中的異常行為。

本文針對(duì)傳統(tǒng)聚類異常軌跡檢測(cè)方法中存在的局限性，使用廣播式自動(dòng)相關(guān)監(jiān)視(automatic dependent surveillance-broadcast，ADS-B)，提出了基于時(shí)間序列的多維距離聚類異常檢測(cè)方法。利用改進(jìn)Hausdorff距離計(jì)算不同軌跡數(shù)據(jù)之間的相似距離，并結(jié)合層次聚類算法檢測(cè)異常飛行軌跡。相比只采用軌跡位置的Hausdorff距離函數(shù)進(jìn)行異常檢測(cè)方法，改進(jìn)方法能夠更全面地對(duì)軌跡數(shù)據(jù)進(jìn)行分析，找到軌跡數(shù)據(jù)在位置、速度、方向等特征上的異常，提高飛行軌跡數(shù)據(jù)的異常行為檢測(cè)的精確性。

1 相關(guān)概念描述

1.1 軌跡數(shù)據(jù)

軌跡數(shù)據(jù)是由一系列隨時(shí)間變化的時(shí)空數(shù)據(jù)點(diǎn)組成，即TR={P1,P2,…Pi,…,Pn}。 ADS-B系統(tǒng)可以自動(dòng)地從相關(guān)機(jī)載設(shè)備獲取參數(shù)向其它飛機(jī)或地面站廣播飛機(jī)的位置、高度、速度、航向等信息[5]，針對(duì)于ADS-B數(shù)據(jù)來(lái)說(shuō)，這里第i個(gè)數(shù)據(jù)點(diǎn)可以表示為Pi=(loni,lati,vi,θi,ti)，loni，lati為數(shù)據(jù)點(diǎn)的經(jīng)度和緯度值，vi為數(shù)據(jù)點(diǎn)的速度，θi為數(shù)據(jù)點(diǎn)的航向，ti為該數(shù)據(jù)點(diǎn)的時(shí)間戳信息。

軌跡集合可以表示為n條軌跡數(shù)據(jù)的集合，即T={TR1,TR2,…,TRi,…,TRn}， 其中TRi表示第i條軌跡數(shù)據(jù)。

1.2 軌跡相似度

正常情況下某段航線的飛行軌跡是相似的，但不排除某些突發(fā)情況，如躲避物體或檢測(cè)數(shù)據(jù)丟失等情況，這些情況會(huì)導(dǎo)致軌跡數(shù)據(jù)發(fā)生異常，使得該飛行軌跡偏離正常軌跡，嚴(yán)重時(shí)可能導(dǎo)致軌跡相似度發(fā)生較大差異。僅考慮位置特征的軌跡異常檢測(cè)算法會(huì)忽略掉時(shí)間、速度和方向等運(yùn)動(dòng)狀態(tài)對(duì)飛行軌跡數(shù)據(jù)的影響，不能有效挖掘歷史數(shù)據(jù)[6]，使得正常的軌跡行為被檢測(cè)為異常軌跡，或者真正的異常的軌跡行為不能準(zhǔn)備被發(fā)現(xiàn)。

(1)時(shí)間因素對(duì)軌跡相似度的影響

飛機(jī)飛行的軌跡是隨時(shí)間而逐漸變化的，在已有軌跡異常檢測(cè)算法計(jì)算軌跡相似度時(shí)，僅考慮了軌跡的位置信息，沒(méi)有考慮時(shí)間因素對(duì)飛行軌跡的影響，導(dǎo)致檢測(cè)效果較差。例如在計(jì)算如圖1所示的4條軌跡的相似度時(shí)，如果僅考慮位置信息，很有可能得到4條軌跡相似度歸屬于相同的類，顯然得到的結(jié)果不能完全體現(xiàn)出軌跡的運(yùn)動(dòng)規(guī)律。圖1中4條軌跡的前期運(yùn)動(dòng)形態(tài)趨勢(shì)相似，但軌跡Tr3和Tr4隨著時(shí)間的變化后期的運(yùn)動(dòng)趨勢(shì)同Tr1和Tr2出現(xiàn)了較大的差異。在考慮時(shí)間特征情況下，就可以將Tr3和Tr4軌跡同Tr1和Tr2進(jìn)行區(qū)分。

圖1 相似軌跡

(2)速度和方向因素對(duì)軌跡相似度的影響

為了更好地進(jìn)行軌跡異常檢測(cè)，在考慮位置特征，時(shí)間特征的基礎(chǔ)上，引入軌跡本身具有的速度，方向等運(yùn)動(dòng)特征。如圖2所示，顯而易見，通過(guò)平移轉(zhuǎn)換圖中3條軌跡可以重疊，如果不考慮速度和方向的特征，在計(jì)算相似性時(shí)會(huì)判斷為3條軌跡是相似的。但是在考慮到速度和方向特征前提下，明顯Tr1、Tr2、Tr3軌跡兩兩均不相同。Tr2與Tr1速度相同卻方向不同；Tr3與Tr1方向相同卻速度不同，速度要比Tr1快[7]。

圖2 運(yùn)動(dòng)軌跡

針對(duì)上述問(wèn)題，本文在利用Hausdorff距離計(jì)算軌跡相似性時(shí)，在時(shí)間特征的基礎(chǔ)上結(jié)合了軌跡的速度、方向、位置等多重特征[8,9]，利用基于時(shí)間序列的多維特征對(duì)Hausdorff距離函數(shù)進(jìn)行改進(jìn)，提高了軌跡數(shù)據(jù)相似性計(jì)算的精確性，進(jìn)一步提高軌跡異常檢測(cè)的效果。

2 基于多維距離的層次聚類算法

2.1 算法描述

本文提出的基于多維距離的層次聚類算法由兩部分組成：基于時(shí)間序列的多維Hausdorff距離算法和多維Hausdorff距離的層次聚類算法?；跁r(shí)間序列的多維Hausdorff距離算法首先將方向、速度、位置多維特征融入Hausdorff距離公式中，通過(guò)構(gòu)造的多維Hausdorff距離計(jì)算航跡數(shù)據(jù)集中任意航跡的相似距離[10]，構(gòu)造出航跡間相似性矩陣。多維Hausdorff距離的層次聚類算法基于該相似性矩陣進(jìn)行層次聚類，生成具有層次結(jié)構(gòu)的聚類圖。由于異常與正常航跡之間的相似度值差異較大，可以通過(guò)聚類結(jié)果較為直觀的將異常航跡與正常航跡分類，從而發(fā)現(xiàn)異常航跡。

層次聚類(hierarchical clustering)是一種基于原型的聚類算法，試圖在不同層次對(duì)航跡數(shù)據(jù)集進(jìn)行劃分，從而形成樹形的聚類結(jié)構(gòu)，同時(shí)它不需要事先指定簇的數(shù)量[11]。

2.2 基于時(shí)間序列的多維Hausdorff距離算法

已有的計(jì)算Hausdorff距離算法中僅使用了軌跡數(shù)據(jù)的位置特征，而實(shí)際目標(biāo)軌跡的時(shí)間特征和速度、方向等運(yùn)動(dòng)特征都是描述軌跡的重要信息，本文提出的基于時(shí)間序列的多維Hausdorff距離算法把軌跡數(shù)據(jù)看作是按照時(shí)間序列由有序的數(shù)據(jù)點(diǎn)組成的。假設(shè)軌跡TrA={a1,a2,…,ai,…,an} 和軌跡TrB={b1,b2,…,bi,…,bm}， 其中n,m≥3，ai、bi分別為TrA、TrB在第i時(shí)刻的數(shù)據(jù)點(diǎn)。本算法在考慮時(shí)間序列的基礎(chǔ)上，引入位置、速度、方向等特征來(lái)計(jì)算多維Hausdorff距離，即基于時(shí)間序列的多特征兩點(diǎn)距離(time series multi-feature distance，TMFD)：具體如下所述：

(1)位置特征

posdis(ai,bi)=dist(ai，(bi，bi-1，bi+1)) 表示兩條軌跡上的兩點(diǎn)的經(jīng)緯度距離，本文采用Haversine公式計(jì)算。其中，軌跡A中任意點(diǎn)ai僅與軌跡B中相對(duì)應(yīng)點(diǎn)bi以及前后相鄰兩點(diǎn)比較。

(2)速度特征

spedis(ai,bi)=dist(Vai，(Vbi，Vbi-1，Vbi+1)) 表示兩條軌跡上兩點(diǎn)之間的速度歐式距離，點(diǎn)的速度分解為垂直速度v*sinθ、 水平速度v*cosθ。

(3)方向特征

angdis(ai,bi)=dist(θai,(θbi,θbi-1,θbi+1)) 表示兩條軌跡在內(nèi)部方向改變程度，反應(yīng)了軌跡的波動(dòng)狀況，使用絕對(duì)值距離來(lái)表示。

即綜合上述公式

(1)

TMFD(ai,bi)=ωp×posdis+ωv×spedis+ωθ×angdis

(2)

其中，ωp+ωv+ωθ=1， 且ωp≥0,ωv≥0,ωθ≥0分別表示位置特征、速度特征、方向特征的權(quán)重因子，可根據(jù)應(yīng)用場(chǎng)景的不同，適當(dāng)調(diào)整權(quán)重的選擇。

該算法從3個(gè)方面體現(xiàn)出軌跡數(shù)據(jù)的時(shí)空運(yùn)動(dòng)特征對(duì)異常軌跡行為檢測(cè)的優(yōu)勢(shì)：

(1)軌跡點(diǎn)的運(yùn)行特征具有多維性。改進(jìn)后函數(shù)表達(dá)式中不僅使用點(diǎn)的位置特征，將點(diǎn)的速度特征以及方向特征考慮進(jìn)去，利用Hausdorff距離計(jì)算方法，提高復(fù)雜運(yùn)動(dòng)狀態(tài)下軌跡相似度計(jì)算的準(zhǔn)確性。

(2)軌跡點(diǎn)的運(yùn)動(dòng)是有序的。假設(shè)TrA中的第一個(gè)點(diǎn)a1與TrB中最后一點(diǎn)bn之間距離最大，則按照最初計(jì)算Hausdorff距離原則，則定義h(TrA,TrB)=dist(a1,bn)。 明顯所選取點(diǎn)有一定的時(shí)間差，在計(jì)算相似度時(shí)誤差過(guò)大。且軌跡TrA中任意點(diǎn)與TrB中所有點(diǎn)比較也不能體現(xiàn)出時(shí)間有序性特征。為了避免上述問(wèn)題，令點(diǎn)ai、bi分別為TrA、TrB在同一時(shí)刻i的軌跡點(diǎn)，僅使用軌跡TrA中的每個(gè)點(diǎn)ai與軌跡TrB上的bi點(diǎn)與點(diǎn)bi前后相鄰兩點(diǎn)之間比較，減少計(jì)算量同時(shí)體現(xiàn)出軌跡的有序性。

(3)軌跡點(diǎn)的運(yùn)動(dòng)是連續(xù)性。選取點(diǎn)bi以及bi前后相鄰兩點(diǎn)進(jìn)行比較，最大程度滿足在時(shí)間排序上的一對(duì)一，由于軌跡前后相鄰兩點(diǎn)在速度及方向上變化不會(huì)過(guò)大，同時(shí)采用一對(duì)三保證了點(diǎn)與點(diǎn)之間的連續(xù)性，在計(jì)算軌跡相似度時(shí)提高準(zhǔn)確率。

2.3 多維Hausdorff距離的層次聚類算法

對(duì)軌跡數(shù)據(jù)集使用基于時(shí)間序列的多維特征距離方法計(jì)算得到任意兩條軌跡之間的多維相似距離h(TrA,TrB)，進(jìn)而構(gòu)造出計(jì)算航跡間的相似性矩陣R，即

其中，rij表示第i條軌跡與第j條軌跡之間的相似距離。主對(duì)角線元素0表示軌跡自身與自身比較的相似距離。

表1為結(jié)合軌跡數(shù)據(jù)的多維Hausdorff距離的層次聚類算法。該算法的輸入是軌跡數(shù)據(jù)集T，輸出是聚類圖。在多維Hausdorff距離的層次聚類算法中，步驟1使用基于時(shí)間序列的多維Hausdorff距離計(jì)算T中任意兩條軌跡之間的相似距離；步驟2使用步驟1中的相似距離構(gòu)造相似性度量矩陣R；步驟3根據(jù)n條軌跡數(shù)據(jù)構(gòu)造n個(gè)類，每個(gè)類中只包含一條軌跡，并設(shè)置每一個(gè)類的平臺(tái)高度均為0；步驟4采用自底向上的層次聚類算法合并相似距離最近的兩類為一個(gè)新類(也就是選擇矩陣R中rij的最小值，合并軌跡i和軌跡j對(duì)應(yīng)的兩個(gè)類為新類)，并且以軌跡i和軌跡j的相似距離作為該新類在聚類圖中的平臺(tái)高度；步驟5計(jì)算新類與其它各類的相似距離，若當(dāng)前類的總個(gè)數(shù)已經(jīng)等于1，則輸出聚類圖，否則繼續(xù)步驟4。

表1 多維Hausdorff距離的層次聚類算法

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)數(shù)據(jù)集

本文采用的數(shù)據(jù)集是來(lái)自Flightradar24的ADS-B數(shù)據(jù)，該網(wǎng)站提供實(shí)時(shí)的航班信息數(shù)據(jù)。其中選擇北京到上海的45天以及北京到杭州的20天的部分飛行航跡。實(shí)驗(yàn)場(chǎng)景根據(jù)位置、速度、航向特征的取值差異，按比例確定權(quán)重因子的大小，降低權(quán)值對(duì)構(gòu)造的多維距離的層次聚類算法的影響。

為了更直觀觀察本文方法的聚類結(jié)果，圖3(a)為根據(jù)本文所提出的聚類算法對(duì)北京至上海45條正常航跡以及北京至杭州20條的聚類結(jié)果，杭州與上海在地理位置上的航線差別不明顯，能夠有效驗(yàn)證方向及速度特征對(duì)聚類結(jié)果的影響。橫坐標(biāo)表示航跡數(shù)據(jù)集中的樣本個(gè)數(shù)，坐標(biāo)軸上的數(shù)字為對(duì)應(yīng)的航跡編號(hào)，如圖3(a)左側(cè)聚類為 1～45 編號(hào)的航跡，表示北京至上海的45條航跡，右側(cè)聚類為46～65編號(hào)的航跡，表示北京至杭州的20條航跡；縱坐標(biāo)表示航跡間的相似距離。根據(jù)軌跡相似性距離值，同一航線的航跡屬于同一聚類。如圖所示，北京至上海為一個(gè)聚類、北京至杭州為一個(gè)聚類，符合實(shí)際情況。圖3(b)為北京至上海航線的航跡聚類結(jié)果，圖中聚類線沒(méi)有較大落差，表示該航跡本身之間差距并不大，均在正常范圍內(nèi)(相似度值90)波動(dòng)。

圖3 航跡聚類

圖4為北京至上海的航跡經(jīng)緯度坐標(biāo)的二維顯示，橫坐標(biāo)表示緯度、縱坐標(biāo)表示經(jīng)度，所有的航跡并不是沿著一條直線，而是在一定范圍內(nèi)飛行。

圖4 北京到上海航跡二維圖

3.2 實(shí)驗(yàn)評(píng)價(jià)標(biāo)準(zhǔn)

在進(jìn)行異常檢測(cè)時(shí)，針對(duì)于位置、速度、航向等特征分別隨機(jī)選取北京至上海的5條航跡，修改航跡點(diǎn)使其偏離正常飛行航跡閾值，飛行速度為正常速度的1.5倍，修改航向?yàn)檎：较虻南喾捶较?。該?shí)驗(yàn)結(jié)果通過(guò)計(jì)算正確率(Accuracy)、精確率(Precision)、召回率(Recall)、F1值(F1-score)來(lái)評(píng)價(jià)基于多維Hausdorff距離的層次聚類算法。以上評(píng)價(jià)指標(biāo)計(jì)算公式

(3)

(4)

(5)

(6)

正確率定義為正確預(yù)測(cè)的正反樣本數(shù)占所有樣本的比例。精確率定義為預(yù)測(cè)是異常實(shí)際也是異常的樣本數(shù)占預(yù)測(cè)是異常的樣本數(shù)的比例。召回率定義為測(cè)試集中所有正樣本樣例中，被正確識(shí)別為正樣本的比例。F1值是準(zhǔn)確率和召回率的加權(quán)調(diào)和平均。其中，TP表示正樣本被正確識(shí)別為正樣本，TN表示負(fù)樣本被正確識(shí)別為負(fù)樣本，F(xiàn)P表示負(fù)樣本被錯(cuò)誤識(shí)別為正樣本，F(xiàn)N表示正樣本被錯(cuò)誤識(shí)別為負(fù)樣本。

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

圖5為在北京至上海的航跡中采用本文所述方法實(shí)驗(yàn)修改航跡速度、位置、航向的聚類結(jié)果。實(shí)驗(yàn)結(jié)果分析，聚類圖中的橫坐標(biāo)表示航跡條數(shù)，坐標(biāo)軸上的數(shù)字表示對(duì)應(yīng)的航跡編號(hào)，縱坐標(biāo)表示航跡之間的相似度值。圖5(a)為對(duì)速度修改后的5條航跡與正常航跡的聚類結(jié)果，可以明顯區(qū)別出修改后的異常航跡，通過(guò)本文提出多維Hausdorff距離的層次聚類算法，提高了軌跡相似度度量對(duì)速度變化的敏感度，使得修改速度后的軌跡與正常軌跡的相似度值相差較大，將正常與異常航跡聚為兩類；圖5(b)為對(duì)航向角度修改后的5條航跡與正常航跡的聚類結(jié)果，同樣識(shí)別出異常航跡，將正常與異常航跡聚為兩類。圖5(c)為對(duì)軌跡點(diǎn)經(jīng)緯度值修改的5條航跡與正常航跡的聚類結(jié)果，由圖3(b)可看出，正常軌跡的相似度值最高在90左右，在修改航跡位置后，聚類圖中異常航跡與正常航跡相比的相似度值約為120-130左右，遠(yuǎn)超出正常航跡聚類時(shí)的相似度，其中各別航跡區(qū)分不明顯由于本身航跡并不是沿著一條固定線路不變，有一定的飛行范圍，所以修改后的異常航跡的位置對(duì)正常航跡的聚類稍加影響，但不妨礙判斷出異常的航跡，通過(guò)本文方法可以判斷出異常軌跡。為了說(shuō)明本文提出的算法的有效性，使用未改進(jìn)的Hausdorff距離分別進(jìn)行了與本文實(shí)驗(yàn)數(shù)據(jù)相同的5條位置異常航跡、5條速度異常航跡以及5條航向異常的航跡與正常航跡聚類的3組實(shí)驗(yàn)，計(jì)算異常航跡與正常航跡的相似度，由于原始Hausdorff距離在計(jì)算中僅考慮位置特征，所以對(duì)于修改位置的異常航跡可以用該方法判斷出，但計(jì)算中并沒(méi)有考慮速度和航向特征，所以在修改速度和航向的對(duì)比實(shí)驗(yàn)中并沒(méi)有有效檢測(cè)出速度和航向上的異常，表明本文方法在速度與航向上的檢測(cè)提高了準(zhǔn)確率。

圖5 異常檢測(cè)聚類

表2即原始Hausdorff距離算法與本文改進(jìn)算法基于時(shí)間序列的多維距離聚類異常檢測(cè)方法在相同修改條件下檢測(cè)異常軌跡的對(duì)比結(jié)果。

表2 與現(xiàn)有Hausdorff距離進(jìn)行聚類對(duì)比

4 結(jié)束語(yǔ)

本文通過(guò)分析航跡數(shù)據(jù)的特征，針對(duì)現(xiàn)有的軌跡相似度度量方法存在的不足，提出了一種基于時(shí)間序列的多維Hausdorff距離，考慮軌跡本身的運(yùn)動(dòng)有序性以及軌跡點(diǎn)連續(xù)性特征的基礎(chǔ)上，從位置、速度、航向這3個(gè)方面來(lái)計(jì)算軌跡的相似度，同時(shí)針對(duì)于“軌跡點(diǎn)有序”這一特征，使用一對(duì)三的比較方法減少了軌跡點(diǎn)之間的比較次數(shù)，降低了計(jì)算復(fù)雜度。采用ADS-B數(shù)據(jù)集，利用改進(jìn)的多維Hausdorff距離進(jìn)行層次聚類實(shí)驗(yàn)結(jié)果表明，該算法可以有效識(shí)別出異常航跡，驗(yàn)證了改進(jìn)方法的有效性，對(duì)比實(shí)驗(yàn)結(jié)果表明，增加軌跡點(diǎn)的運(yùn)動(dòng)、方向特征提高了飛行軌跡數(shù)據(jù)的異常行為檢測(cè)的精確性。在實(shí)際應(yīng)用中，發(fā)現(xiàn)異常航跡對(duì)于查找民航飛機(jī)出現(xiàn)故障及漏洞有著重要的參考意義。