基于小波聚類的終端區(qū)進(jìn)場(chǎng)軌跡模式識(shí)別

王 超 鄭旭芳 卜 寧

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

?

基于小波聚類的終端區(qū)進(jìn)場(chǎng)軌跡模式識(shí)別

王 超 鄭旭芳 卜 寧

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

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

模式識(shí)別 小波聚類 航空器軌跡聚類 異常軌跡識(shí)別

0 引 言

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

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

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

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

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

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

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

圖1 航空器進(jìn)場(chǎng)軌跡的結(jié)構(gòu)

(1)

(2)

1.2 航空器軌跡的相似性

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

(3)

(4)

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

在數(shù)據(jù)挖掘領(lǐng)域中，有很多數(shù)據(jù)由于類型特殊、維度過(guò)高、規(guī)模龐大等原因?qū)е潞茈y直接對(duì)其使用挖掘算法。但通過(guò)數(shù)據(jù)集進(jìn)行特征提取，可以在保證所提取的特征完整以及準(zhǔn)確表達(dá)原始數(shù)據(jù)集特點(diǎn)的前提下，達(dá)到提高數(shù)據(jù)類型的適用性、降低維度和減小數(shù)據(jù)規(guī)模的目的。基于相似度對(duì)航空器軌跡進(jìn)行特征提取，可以解決數(shù)據(jù)維度過(guò)高的問(wèn)題。

2.1 軌跡的特征提取原理

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

2.2 軌跡的特征提取方法

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

(5)

(2) 提取特征子空間B

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

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

(6)

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

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

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

3 基于小波聚類的進(jìn)場(chǎng)軌跡模式識(shí)別

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

圖3 基于小波聚類的進(jìn)場(chǎng)軌跡模式識(shí)別流程

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

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

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

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

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

圖5 量化特征空間C

3.2 小波變換

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

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

圖7 變換空間D

3.3 尋找連通區(qū)域

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

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

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

圖8 連通單元簇

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

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

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

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

4 算例分析

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

圖10 咸陽(yáng)機(jī)場(chǎng)05L/R跑道進(jìn)場(chǎng)軌跡

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

圖11 4個(gè)連通單元簇

4.1 盛行交通流的識(shí)別

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

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

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

4.2 異常軌跡的識(shí)別

將沒(méi)有標(biāo)號(hào)的軌跡識(shí)別為異常軌跡，共計(jì)21條，如圖13所示。

圖13 異常軌跡

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

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

5 結(jié) 語(yǔ)

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

[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] 龔璽,裴韜,孫嘉,等.時(shí)空軌跡聚類方法研究進(jìn)展[J].地理科學(xué)進(jìn)展,2011,30(5):522-534.

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

[6] 袁冠.移動(dòng)對(duì)象軌跡數(shù)據(jù)挖掘方法研究[D].徐州:中國(guó)礦業(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。國(guó)家自然科學(xué)基金項(xiàng)目(61039001)。王超，副教授，主研領(lǐng)域：空中交通系統(tǒng)仿真與分析。鄭旭芳，碩士生。卜寧，碩士。

TP301 V355

A

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