基于時間序列的多維距離聚類異常檢測方法

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

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

0 引 言

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

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

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

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

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

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

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

1.2 軌跡相似度

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

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

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

圖1 相似軌跡

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

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

圖2 運動軌跡

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

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

2.1 算法描述

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

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

2.2 基于時間序列的多維Hausdorff距離算法

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

(1)位置特征

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

(2)速度特征

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

(3)方向特征

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

即綜合上述公式

(1)

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

(2)

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

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

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

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

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

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

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

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

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

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

3 實驗分析

3.1 實驗數(shù)據(jù)集

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

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

圖3 航跡聚類

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

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

3.2 實驗評價標準

在進行異常檢測時，針對于位置、速度、航向等特征分別隨機選取北京至上海的5條航跡，修改航跡點使其偏離正常飛行航跡閾值，飛行速度為正常速度的1.5倍，修改航向為正常航向的相反方向。該實驗結(jié)果通過計算正確率(Accuracy)、精確率(Precision)、召回率(Recall)、F1值(F1-score)來評價基于多維Hausdorff距離的層次聚類算法。以上評價指標計算公式

(3)

(4)

(5)

(6)

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

3.3 實驗結(jié)果

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

圖5 異常檢測聚類

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

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

4 結(jié)束語

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