基于小波聚類的終端區(qū)進場軌跡模式識別

王 超 鄭旭芳 卜 寧

(中國民航大學(xué)空中交通管理學(xué)院 天津 300300)

?

基于小波聚類的終端區(qū)進場軌跡模式識別

王 超 鄭旭芳 卜 寧

(中國民航大學(xué)空中交通管理學(xué)院 天津 300300)

為改善終端區(qū)航空器軌跡聚類方法中存在的自動化程度低、無法精確識別異常軌跡的不足，提出基于小波聚類的進場軌跡模式識別方法。首先，建立基于3D空間網(wǎng)格的軌跡相似性矩陣，推導(dǎo)得到軌跡間相似特征子空間，進一步構(gòu)建軌跡相似特征2D圖模型。通過特征圖模型的數(shù)字化、小波變換與聚類，實現(xiàn)對盛行交通流模式以及異常交通流軌跡的識別。實例分析在無人工指導(dǎo)情況下，從352條進場軌跡中識別出4個類的331條盛行交通流軌跡，以及 21條異常軌跡。實驗結(jié)果證明，該算法克服了目前航空器軌跡聚類領(lǐng)域需要人工確定類數(shù)以及難以識別異常軌跡的不足。

模式識別 小波聚類 航空器軌跡聚類 異常軌跡識別

0 引 言

空中交通運行中產(chǎn)生的海量歷史軌跡數(shù)據(jù)是大量航班飛行與空中交通管制決策交互作用的結(jié)果，隱含著豐富的交通模式信息，其中包括盛行交通流和異常軌跡。盛行交通流反映了航空器軌跡在空間分布的頻繁模式。異常軌跡是與盛行交通流偏差顯著的少數(shù)軌跡，是交通擁塞、危險天氣和飛行沖突解脫等異常交通控制行為的反映。因此，基于軌跡聚類的交通模式識別可以用來量化分析空中交通系統(tǒng)性能，發(fā)現(xiàn)現(xiàn)有空域結(jié)構(gòu)的不足。根據(jù)盛行交通流的分布來改進終端空域的設(shè)計可以提高容納動態(tài)交通流能力，同時降低空中交通管制難度，從而提高終端區(qū)空中交通運行效率。

近年來，許多學(xué)者在軌跡聚類領(lǐng)域開展了研究，主要方法有：基于離散特征點的聚類方法、基于子軌跡的聚類方法、基于完整軌跡的聚類方法和基于時間區(qū)間的聚類方法。

針對航空器的飛行軌跡聚類，Rehm[1]提出了一種基于離散航跡點對之間的歐式距離構(gòu)建相似度的層次聚類方法。但當(dāng)不同的軌跡所包含的航跡點數(shù)量差異顯著時，該相似度模型不能準(zhǔn)確表達(dá)軌跡的空間接近程度。Gariel等[2]提取轉(zhuǎn)彎點作為聚類對象，然后采用K-means和DBSCAN相結(jié)合的方法實現(xiàn)聚類，但依然需要人工確認(rèn)聚類數(shù)目。Enrgquze等[3]提出了基于譜聚類的軌跡聚類方法，該方法首先建立相似鄰接矩陣，并采用譜聚類方法分割鄰接圖，聚類效果良好。但需要對航空器位置信息進行線性預(yù)處理，導(dǎo)致長度差異顯著的軌跡的相似度失真，也存在自動化程度不高的問題。

綜上，現(xiàn)有航空器軌跡聚類方法普遍存在兩個不足：一是需要根據(jù)經(jīng)驗人工確定聚類的簇數(shù)，使得聚類的結(jié)果受到人為干預(yù)的影響；二是無法在大量軌跡數(shù)據(jù)中精確識別異常軌跡，從而影響聚類質(zhì)量。

針對以上問題，本文提出一種基于小波聚類的進場軌跡模式識別方法。首先，分析了航空器軌跡數(shù)據(jù)結(jié)構(gòu)，建立了軌跡相似性矩陣，推導(dǎo)出相似矩陣的特征子空間，構(gòu)造了2D相似特征圖模型。然后，通過對相似特征圖模型的數(shù)字化、小波變換、空間映射和聚類等過程，識別出盛行交通流軌跡和異常軌跡。最后，通過實際進場軌跡樣本對模型和方法進行驗證和分析。

1 航空器軌跡數(shù)據(jù)集相似性

1.1 航空器軌跡的數(shù)據(jù)結(jié)構(gòu)

圖1 航空器進場軌跡的結(jié)構(gòu)

(1)

(2)

1.2 航空器軌跡的相似性

軌跡相似度構(gòu)建方法的優(yōu)劣直接影響著聚類質(zhì)量的高低。軌跡的相似度構(gòu)建有基于歐氏距離的模型，簡單直觀但對噪聲數(shù)據(jù)較為敏感；基于最小外包矩形距離的模型，容易遺漏不在對應(yīng)時刻的相似軌跡的劃分；基于全區(qū)間變換封裝距離的模型，對噪聲數(shù)據(jù)較為敏感；基于子軌跡相似性的模型，受子軌跡時間區(qū)間影響較大[4]。

(3)

(4)

2 航空器軌跡的相似特征提取

在數(shù)據(jù)挖掘領(lǐng)域中，有很多數(shù)據(jù)由于類型特殊、維度過高、規(guī)模龐大等原因?qū)е潞茈y直接對其使用挖掘算法。但通過數(shù)據(jù)集進行特征提取，可以在保證所提取的特征完整以及準(zhǔn)確表達(dá)原始數(shù)據(jù)集特點的前提下，達(dá)到提高數(shù)據(jù)類型的適用性、降低維度和減小數(shù)據(jù)規(guī)模的目的?；谙嗨贫葘娇掌鬈壽E進行特征提取，可以解決數(shù)據(jù)維度過高的問題。

2.1 軌跡的特征提取原理

Jenssen[7]等人對Renyi熵進行估計，發(fā)現(xiàn)該熵的最大化與相似矩陣相關(guān)，并通過推導(dǎo)確認(rèn)相似矩陣前k個最大特征值對應(yīng)的特征向量即為Renyi熵最大化的近似解。根據(jù)這一思想，用軌跡數(shù)據(jù)集的相似矩陣的前k個最大特征值對應(yīng)的特征向量來構(gòu)造特征空間，并用特征空間來代表原始軌跡數(shù)據(jù)。

2.2 軌跡的特征提取方法

(1) 構(gòu)造原始特征空間V

(5)

(2) 提取特征子空間B

依據(jù)Jenssen關(guān)于Renyi熵的思想，越大的特征值所對應(yīng)的特征向量對原始數(shù)據(jù)的表征能力更強。將軌跡相似特征矩陣W的特征值λ由大到小排序，并選取前k個最大λ對應(yīng)的特征向量組成n×k維的子空間，可以進一步減小空間維度[8]。選擇k值時，需要考慮具體數(shù)據(jù)的結(jié)構(gòu)特征、類型和應(yīng)用環(huán)境。

由于構(gòu)建的軌跡相似度涵蓋了所有軌跡的空間位置、速度、航向等因素的影響，所以每一個特征向量都能在一定程度上表達(dá)所有軌跡的特征信息。當(dāng)k=1時，由于維度和信息量過小，無法有效實施聚類，所以將k值初步設(shè)定為2。經(jīng)實驗驗證，當(dāng)k值由2開始增大時，聚類質(zhì)量和效果并無明顯提升，但維度的增加會導(dǎo)致計算復(fù)雜度大幅增高。綜合考慮算法的質(zhì)量和效率，最終將k值設(shè)定為2。由此得到的二維特征子空間如下：

(6)

(3) 構(gòu)造軌跡的相似特征圖

為了實現(xiàn)軌跡的小波聚類，在特征提取的基礎(chǔ)上提出了一種新的圖模型，稱為軌跡的相似特征圖。以特征子空間B中的值為數(shù)據(jù)源，以di1和di2兩個維度設(shè)置x、y坐標(biāo)系，將[di1,di2]表示為圖中的點，稱為軌跡特征點，如圖2所示。

圖2 航空器軌跡的相似特征圖模型

3 基于小波聚類的進場軌跡模式識別

小波聚類是一種基于網(wǎng)格和密度相結(jié)合的多分辨率算法，目前多用在圖像處理、網(wǎng)絡(luò)入侵檢測、信號去噪和多目標(biāo)定位等領(lǐng)域。將小波聚類應(yīng)用到航空器軌跡聚類領(lǐng)域，利用其特性可以實現(xiàn)無指導(dǎo)聚類和異常軌跡檢測，從而完成航空器軌跡模式的識別。基于小波聚類的航空器軌跡模式識別，是以相似特征圖為基礎(chǔ)展開的，其總體工作流程如圖3所示。

圖3 基于小波聚類的進場軌跡模式識別流程

對航空器軌跡的特征數(shù)據(jù)實施小波變換后，得到的低頻信息表征著特征數(shù)據(jù)穩(wěn)定集中的區(qū)域，最終將這些特征數(shù)據(jù)所對應(yīng)的軌跡識別為盛行交通流；高頻信息表征著高速變化的特征數(shù)據(jù)，對應(yīng)軌跡識別為異常軌跡。

3.1 相似特征圖的數(shù)字化

小波聚類屬于網(wǎng)格聚類，應(yīng)首先建立覆蓋整個運算空間的格網(wǎng)。網(wǎng)格邊長的確定主要取決于數(shù)據(jù)范圍大小以及數(shù)據(jù)的密集程度。為確保每個網(wǎng)格中包含的點數(shù)在0～10之間，經(jīng)過分析，本文取網(wǎng)格邊長為0.004。 在圖2所示的相似特征圖上覆蓋一個網(wǎng)格邊長為0.004×0.004的二維格網(wǎng)來匯總軌跡的特征點信息，如圖4所示。

圖4 使用網(wǎng)格對相似特征圖進行數(shù)字化

統(tǒng)計每個網(wǎng)格中所含特征點的數(shù)量，將數(shù)值填入對應(yīng)網(wǎng)格中，構(gòu)成量化特征空間C，如圖5所示。

圖5 量化特征空間C

3.2 小波變換

圖6 空間單元的映射關(guān)系

使用Haar基函數(shù)，對空間C進行2個尺度的二維離散小波變換，得到變換空間D，如圖7所示。

圖7 變換空間D

3.3 尋找連通區(qū)域

在變換空間D中采取基于密度的思想尋找連通區(qū)域。設(shè)定一個密度閾值δ，將包含點數(shù)大于或等于δ的單元定義為“顯著單元”，小于δ的單元定義為“非顯著單元”。

“顯著單元”的相鄰單元中，如果有“顯著單元”，則將兩個單元視為同一連通區(qū)域并繼續(xù)搜索相鄰的“顯著單元”，直到該連通區(qū)域找不到相鄰的“顯著單元”[9]。此時生成的連通區(qū)域，定義為“連通單元簇”。

掃描變換空間D中的所有單元，以“顯著單元”為基礎(chǔ)尋找連通區(qū)域。經(jīng)過多次實驗，設(shè)定密度閾值δ=10，此時單元中數(shù)值的均勻度和單元整體連通性都較好。如圖8所示，當(dāng)δ=10時，灰色背景的單元即為自動生成的連通單元簇。

圖8 連通單元簇

3.4 標(biāo)記簇號及空間映射

經(jīng)過連通區(qū)域的尋找，變換空間D中自動生成了許多連通單元簇，依次標(biāo)記簇號wi。根據(jù)空間C與空間D中單元的映射關(guān)系，為各連通單元簇所對應(yīng)的C中的單元標(biāo)記簇號wi。在空間C中，將ci的簇號wi標(biāo)記給ci所包含的特征點。由于特征點與軌跡一一對應(yīng)，此時軌跡也被標(biāo)記了簇號wi，如圖9所示。

圖9 標(biāo)記簇號及空間映射

最后，算法將標(biāo)有簇號的軌跡識別為盛行交通流，并將有相同簇號的軌跡各自劃分為一個聚類；而將沒有標(biāo)號的軌跡識別為異常軌跡。

4 算例分析

選用西安咸陽機場采用05L/R跑道獨立運行模式時，兩條跑道某1天內(nèi)共計352條進場軌跡作為實驗數(shù)據(jù)，如圖10所示；使用Matlab作為數(shù)據(jù)處理和實驗分析軟件。

圖10 咸陽機場05L/R跑道進場軌跡

實驗數(shù)據(jù)的相似特征圖如圖2所示，以該圖為基礎(chǔ)，按照基于小波聚類的航空器軌跡模式識別方法進行實驗。經(jīng)過無人工指導(dǎo)的實驗后，變換空間D中自動生成了4個連通單元簇w1、w2、w3和w4。將它們映射到軌跡的相似特征圖上，如圖11所示。

圖11 4個連通單元簇

4.1 盛行交通流的識別

算法將4個簇包含的特征點所對應(yīng)的軌跡識別為盛行交通流，共計331條，用不同灰度標(biāo)記，如圖12所示。

圖12 盛行交通流識別結(jié)果

圖12表明，算法識別出了符合標(biāo)稱進場航線的盛行交通流；且有效地區(qū)分出了由西北、東北、西南和東南方向進場的航空器軌跡，將它們各自劃分為一個聚類，實現(xiàn)了無指導(dǎo)聚類。4個簇的軌跡彼此在形態(tài)和空間分布上有著顯著的差異，而同一簇內(nèi)的軌跡進場方向是一致的，有著較高的相似度和形態(tài)特征。

4.2 異常軌跡的識別

將沒有標(biāo)號的軌跡識別為異常軌跡，共計21條，如圖13所示。

圖13 異常軌跡

識別出的異常軌跡偏離標(biāo)準(zhǔn)進場程序的標(biāo)稱航線，在形態(tài)上與盛行交通流差異顯著，這說明了算法識別異常軌跡的準(zhǔn)確性。

異常軌跡中含有環(huán)線的軌跡，稱為等待軌跡。這類異常軌跡是管制員為了調(diào)配飛行沖突，指揮進場航空器進入等待程序而造成的。圖13中有5條等待軌跡，約占總交通流量2%，說明指揮航空器進入等待程序并非在西安終端區(qū)管制實施的主要策略。

5 結(jié) 語

通過對航空器軌跡的相似度矩陣進行相似特征提取，解決了高維數(shù)據(jù)不能適用小波聚類的問題；提出了基于小波聚類的航空器軌跡模式識別方法，并實現(xiàn)了對異常軌跡的識別。實驗結(jié)果表明，在無人工指導(dǎo)的情況下，算法可以有效識別盛行交通流并準(zhǔn)確劃分聚類。同時可以精確識別異常軌跡，并對軌跡的異常模式做進一步的識別。該方法提出了一種嶄新的軌跡模式識別思路，對航空器軌跡聚類方法做出了補充和改進，為終端區(qū)空域扇區(qū)和進離場航線的優(yōu)化設(shè)計奠定了技術(shù)基礎(chǔ)。未來將對異常軌跡的形成原因和軌跡模式識別進行進一步研究。

[1] Rehm F.Clustering of flight tracks[C]//6th AIAA Infotech @ Aerospace 2010.Atlanta:AIAA,2010:AIAA-2010-3412.

[2] Gariel M,Srivastava A N,Feron E.Trajectory clustering and an application to airspace monitoring[J].Intelligent Transportation Systems,IEEE Transactions on,2011,12(4):1511-1524.

[3] Enriquez M,Kurcz C.A simple and robust flow detection algorithm based on spectral clustering[C]//ICRAT Conference,2012:1-6.

[4] 龔璽,裴韜,孫嘉,等.時空軌跡聚類方法研究進展[J].地理科學(xué)進展,2011,30(5):522-534.

[5] 王超,韓邦村,王飛.基于軌跡譜聚類的終端區(qū)盛行交通流識別方法[J].西南交通大學(xué)學(xué)報,2014,49(3):546-552.

[6] 袁冠.移動對象軌跡數(shù)據(jù)挖掘方法研究[D].徐州:中國礦業(yè)大學(xué),2012.

[7] Jenssen R,Hild K E,Erdogmus D,et al.Clustering using Renyi’s entropy [C]//Neural Networks,2003 International Joint Conference on.IEEE,2003,1:523-528.

[8] Kishore D.Character segmentation from multi-oriented video words using Discrete Wavelet Transform and K-Means Clustering[J].IJSEAT,2014,2(12):1033-1039.

[9] Sheikholeslami G,Chatterjee S,Zhang A D.WaveCluster:a wavelet-based clustering approach for spatial data in very large databases[J].The VLDB Journal,2000,8(3-4):289-304.

PATTERN RECOGNITION OF APPROACH LANDING TRAJECTORIES IN TERMINAL AIRSPACE BASED ON WAVELET CLUSTERING

Wang Chao Zheng Xufang Bu Ning

(CollegeofAirTrafficManagement,CivilAviationUniversityofChina,Tianjin300300,China)

In order to ameliorate the deficiencies existed in trajectories clustering methods of aircrafts in terminal airspace such as low automation degree and cannot precisely identify the abnormal trajectories, we proposed a wavelet clustering-based pattern recognition method of approach landing trajectories. First we set up the 3D spatial grid-based similarity matrix of trajectories, and obtained through derivation the similar characteristic subspace between trajectories. Furthermore we built the 2D graph model of trajectories similar characteristic. The identification on prevailing traffic flows pattern and abnormal traffic trajectories is implemented through the digitisation, wavelet transformation and clustering on the characteristic graph model. We made analyses on examples, under the condition of no artificial guidance, we identified 331 prevailing traffic flows trajectories of 4 categories and 21 abnormal trajectories from 352 approach landing trajectories. Experimental result proved that this algorithm overcomes the deficiency of current aircraft trajectories clustering field that it requires artificial confirmation on the number of categories and is difficult to identify abnormal trajectories.

Pattern recognition Wavelet clustering Aircraft trajectories clustering Abnormal trajectory identification

2015-09-06。國家自然科學(xué)基金項目(61039001)。王超，副教授，主研領(lǐng)域：空中交通系統(tǒng)仿真與分析。鄭旭芳，碩士生。卜寧，碩士。

TP301 V355

A

10.3969/j.issn.1000-386x.2016.11.027