基于聚類(lèi)算法的飛行航跡分析

李琳丹，許雅璽，張榆薪，劉坤

（1.中國(guó)民用航空飛行學(xué)院機(jī)場(chǎng)學(xué)院，廣漢 618300；2.中國(guó)民用航空飛行學(xué)院計(jì)算機(jī)學(xué)院，廣漢 618300；3.中國(guó)民用航空飛行學(xué)院航空工程學(xué)院，廣漢 618300）

0 引言

信息爆炸的新時(shí)代，大數(shù)據(jù)已成為當(dāng)下流行詞匯之一。數(shù)據(jù)內(nèi)部隱藏著大量有用信息，對(duì)數(shù)據(jù)隱藏信息進(jìn)行挖掘，已成為當(dāng)下各行業(yè)競(jìng)爭(zhēng)的重要手段之一，這種信息分析技術(shù)，稱(chēng)為數(shù)據(jù)挖掘。聚類(lèi)分析是數(shù)據(jù)挖掘中應(yīng)用范圍較廣的方法。聚類(lèi)分析已在生物、工程、語(yǔ)言、醫(yī)藥、人類(lèi)學(xué)、心理學(xué)和市場(chǎng)學(xué)等方面得到廣泛應(yīng)用，如地質(zhì)勘探、古生物研究、大壩監(jiān)控、圖像識(shí)別、圖像檢索等。在航空領(lǐng)域，聚類(lèi)分析也有較為廣泛的應(yīng)用，在空中交通流量管理和分析層面，聚類(lèi)分析從錯(cuò)綜復(fù)雜的航跡中提取出主要流（Major Traffic Flow）信息，識(shí)別出扇區(qū)中流量的主要模式和特征；在扇區(qū)規(guī)劃方面，對(duì)歷史航跡進(jìn)行聚類(lèi)得到航跡簇，根據(jù)航跡簇建立扇區(qū)邊界；在實(shí)際飛行程序設(shè)計(jì)分析方面[1]，聚類(lèi)計(jì)算航跡簇平均飛行航跡，對(duì)比理想航跡分析實(shí)際飛行程序存在的不足及改進(jìn)。

國(guó)內(nèi)航跡聚類(lèi)方法及應(yīng)用也較多，王超[2]等人的基于改進(jìn)的模糊C-means航跡聚類(lèi)方法研究，在C-means算法聚類(lèi)的基礎(chǔ)上結(jié)合了模擬退火和遺傳算法進(jìn)行改進(jìn)，一定程度上增強(qiáng)了新算法的有效性；肖宇[3]等人的基于近鄰傳播算法的半監(jiān)督聚類(lèi)方法，利用已有的標(biāo)簽數(shù)據(jù)或者成對(duì)點(diǎn)約束對(duì)數(shù)據(jù)產(chǎn)生的相似度矩陣進(jìn)行調(diào)整，提高了近鄰傳播算法的聚類(lèi)性能；徐濤[4]等人的基于航跡點(diǎn)法向距離的航跡聚類(lèi)研究，解決了因飛機(jī)速度差異引起的航跡點(diǎn)對(duì)選取不匹配問(wèn)題；鄭樂(lè)[5]等人的基于轉(zhuǎn)彎點(diǎn)聚類(lèi)的航空器飛行軌跡分析，實(shí)現(xiàn)了盛行交通流的識(shí)別。

國(guó)外存在的主流聚類(lèi)分析方法，一是Gaffney S[6]等人對(duì)移動(dòng)對(duì)象軌道聚類(lèi)進(jìn)行的研究，將單條軌跡視為整體處理，但一般軌跡路徑較復(fù)雜，在小段上相似在整體上不相似。二是Lee Jaegil[7]等人將單條軌跡分為系列短線(xiàn)段進(jìn)行聚類(lèi)，缺乏軌跡整體性。

本文基于近鄰傳播（AP）算法對(duì)飛行器航跡進(jìn)行聚類(lèi)分析，采集中國(guó)民航飛行學(xué)院歷史飛行訓(xùn)練數(shù)據(jù)，將雷達(dá)監(jiān)測(cè)航跡點(diǎn)視為時(shí)間序列，采用與傳統(tǒng)歐氏距離區(qū)別的DTW距離作為AP算法的相似度測(cè)量指標(biāo)，增強(qiáng)了航跡距離的適用性，同時(shí)采用離散余弦變換（DCT）對(duì)航跡時(shí)序列做平滑處理，有效地降低航跡時(shí)序列的噪聲數(shù)據(jù)，實(shí)驗(yàn)結(jié)果顯示該聚類(lèi)方法在航跡聚類(lèi)分析方面效果更佳。

1 基本概念

1.1 近鄰傳播（AAPP）算法

近鄰傳播算法是近年來(lái)出現(xiàn)在數(shù)據(jù)挖掘領(lǐng)域的基于代表點(diǎn)的聚類(lèi)方法，在數(shù)據(jù)挖掘中起著至關(guān)重要的作用。近鄰傳播算法是在數(shù)據(jù)點(diǎn)的相似度矩陣的基礎(chǔ)上進(jìn)行聚類(lèi)[8]，所有數(shù)據(jù)點(diǎn)都會(huì)被考慮為潛在的類(lèi)代表點(diǎn)，將每個(gè)類(lèi)代表點(diǎn)視為聚類(lèi)網(wǎng)絡(luò)中的節(jié)點(diǎn)，同時(shí)由結(jié)點(diǎn)之間的信息傳遞，使得類(lèi)代表點(diǎn)的相似度信息最大，最后得到最佳的類(lèi)代表點(diǎn)集合。近鄰傳播算法信息的傳遞更新基于max-product、sum-product原則，該信息幅度代表近鄰的程度，即將一個(gè)數(shù)據(jù)點(diǎn)選為類(lèi)代表點(diǎn)的相似度。此外，近鄰傳播算法相較于傳統(tǒng)聚類(lèi)方法，針對(duì)大規(guī)模數(shù)據(jù)聚類(lèi)能更快更優(yōu)的處理，針對(duì)非歐空間問(wèn)題也有較好表現(xiàn)。

1.2 飛行航跡

飛行航跡是指連接一系列點(diǎn)構(gòu)成一條預(yù)計(jì)的或經(jīng)過(guò)的路線(xiàn)，通常用來(lái)表示飛行器在空間上形成或遵循的航行路線(xiàn)。這一系列點(diǎn)是由檢測(cè)雷達(dá)固定周期掃描得到的一系列離散點(diǎn)列，因此可以將其視為等間隔時(shí)間序列。

1.3 離散余弦變換（DDCT）

DCT是一種針對(duì)實(shí)信號(hào)的與傅里葉變換相關(guān)的可分離變換，由于傅里葉變換的共軛對(duì)稱(chēng)性，實(shí)際處理實(shí)信號(hào)時(shí)，導(dǎo)致頻域中數(shù)據(jù)冗余。利用DCT對(duì)實(shí)信號(hào)變換，DCT變換其核心為余弦函數(shù)，變換后依舊為實(shí)信號(hào)，同時(shí)簡(jiǎn)化了實(shí)際計(jì)算。如圖像、聲音等實(shí)信號(hào)，其能量主要存在于DCT變換的低頻部分，因此其在圖像語(yǔ)音信號(hào)處理中運(yùn)用甚廣。

1.4 動(dòng)態(tài)時(shí)間規(guī)整（DTW）

DTW算法，即動(dòng)態(tài)時(shí)間規(guī)整算法，又名動(dòng)態(tài)時(shí)間規(guī)劃算法，是一種衡量?jī)蓚€(gè)時(shí)間序列之間的相似度的方法，其特點(diǎn)在于能衡量長(zhǎng)短不一樣的信息數(shù)據(jù)的相似度，一般用以解決發(fā)音長(zhǎng)短不一的模板匹配問(wèn)題。

2 基于近鄰傳播的航跡聚類(lèi)算法

2.1 基于DCT的航跡數(shù)據(jù)降噪處理

本文利用AP算法對(duì)航跡時(shí)序列進(jìn)行聚類(lèi)，由于實(shí)際雷達(dá)監(jiān)測(cè)中存在噪聲數(shù)據(jù)對(duì)真實(shí)數(shù)據(jù)的影響，為了增強(qiáng)算法初始數(shù)據(jù)的有效性，降低噪聲數(shù)據(jù)對(duì)后續(xù)的航跡相似性度量的不利影響，利用離散余弦變換（DCT）對(duì)航跡數(shù)據(jù)進(jìn)行預(yù)處理。首先將時(shí)域序列變換到頻域序列，接著通過(guò)觀察頻域序列，去掉噪聲頻域分量，然后再進(jìn)行逆變換，將頻域序列返回到時(shí)域序列，從而實(shí)現(xiàn)時(shí)間序列的平滑。

對(duì)一條航跡時(shí)序列AM×N其DCT變換公式如下：

以此類(lèi)推，將本文采集實(shí)際數(shù)據(jù)按照上述方法對(duì)航跡時(shí)序列做平滑降噪處理，通過(guò)DCT離散余弦變化預(yù)處理后的數(shù)據(jù)剔除了影響航跡點(diǎn)的噪聲數(shù)據(jù)，比較傳統(tǒng)聚類(lèi)，在數(shù)據(jù)輸入的起始段就增強(qiáng)了航跡初始數(shù)據(jù)的準(zhǔn)確性，進(jìn)而以達(dá)到更為真實(shí)準(zhǔn)確的聚類(lèi)效果，最后得到的數(shù)據(jù)作為DTW距離的輸入。

2.2 基于DDTTWW距離的航跡相似性度量

假設(shè)需要對(duì)n條航跡構(gòu)成的樣本空間實(shí)現(xiàn)航跡聚類(lèi)，軌跡的相似性度量方法的優(yōu)劣直接影響聚類(lèi)質(zhì)量的高低。傳統(tǒng)方法一般采用歐氏距離來(lái)計(jì)算航跡之間的相似性。但是歐氏距離的計(jì)算要求航跡必須是于等長(zhǎng)序列，這就使得算法具有很大的局限性。在本文采集的數(shù)據(jù)集中，航跡具有非等長(zhǎng)的特點(diǎn)，因此本文采用DTW距離作為相似性度量的指標(biāo)。

動(dòng)態(tài)時(shí)間規(guī)整是60年代，由日本學(xué)者Itakura提出將未知量伸長(zhǎng)或縮短到與參考模板長(zhǎng)度一致[9]，使得特征量與標(biāo)準(zhǔn)模式相互對(duì)應(yīng)。其本質(zhì)可簡(jiǎn)述為尋找一條彎曲代價(jià)最小的最優(yōu)路徑。給定兩個(gè)航跡時(shí)序列Q和C，他們的長(zhǎng)度分別是n和m：

若n=m，可直接計(jì)算兩個(gè)序列的距離；

若n≠m，則需要線(xiàn)性縮放，即把短的航跡時(shí)序列線(xiàn)性放大到和長(zhǎng)序列一樣的長(zhǎng)度，或者把長(zhǎng)的線(xiàn)性縮短到和短序列一樣的長(zhǎng)度，再進(jìn)行比較。具體如下：

構(gòu)造一個(gè)n×m的矩陣網(wǎng)格，矩陣(i,j)處的元素為qi和cj兩個(gè)點(diǎn)的距d(qi,cj)=運(yùn)用運(yùn)籌學(xué)中動(dòng)態(tài)規(guī)劃的思想，尋找一條使得點(diǎn)與點(diǎn)之間距離最小，相似度最高的路徑。并將該路徑定義為warping path規(guī)整路徑，用W表示，第k個(gè)元素為Wk=(i,j)k，

但這條路徑不是任意選擇的，需要滿(mǎn)足邊界條件，連續(xù)性，單調(diào)性幾個(gè)約束條件，找到使得DTW規(guī)整代價(jià)最小的路徑，使得最后總距離最小。將上述降噪后航跡數(shù)據(jù)輸入，找出最佳路徑，將DTW距離作為非等長(zhǎng)航跡聚類(lèi)相似性度量指標(biāo)。

2.3 基于近鄰傳播算法的航跡聚類(lèi)

聚類(lèi)分析是將物理或抽象對(duì)象的集合分組成為類(lèi)似的對(duì)象組成的多個(gè)類(lèi)的分析過(guò)程[10]，在DCT航跡時(shí)序列降噪處理和DTW相似度量基礎(chǔ)上，用兩類(lèi)矩陣：代表矩陣a(i,k)和適選矩陣r(i,k)來(lái)分別表示歸屬度和吸引度信息。a(i,k)由候選聚類(lèi)中心xk指向數(shù)據(jù)樣本點(diǎn)xi，以此描述數(shù)據(jù)點(diǎn)作為其類(lèi)代表點(diǎn)的合適程度。r(i,k)由數(shù)據(jù)樣本點(diǎn)xi指向候選聚類(lèi)中心xk，為數(shù)據(jù)點(diǎn)搜尋相關(guān)信息決定其作為類(lèi)代表點(diǎn)的代表程度。代表矩陣和適選矩陣的大小決定數(shù)據(jù)點(diǎn)成為聚類(lèi)中心可能性大小。通過(guò)各個(gè)數(shù)據(jù)樣本點(diǎn)的迭代更新后，使得r(i,k)和a(i,k)最大的點(diǎn)即為我們尋求的聚類(lèi)中心。其對(duì)應(yīng)迭代更新公式如下：

近鄰傳播在各個(gè)數(shù)據(jù)樣本點(diǎn)之間反復(fù)迭代結(jié)束時(shí)，xk為xi的類(lèi)代表點(diǎn)，其中k滿(mǎn)足：

argkmin(a(i,k)+r(i,k)) （8）

實(shí)際迭代更新過(guò)程中近鄰傳播算法引入阻尼因子λ∈[0 ,1)來(lái)預(yù)防震蕩出現(xiàn)。當(dāng)最終迭代次數(shù)超過(guò)設(shè)定閾值或迭代結(jié)果相同時(shí)，則停止迭代。

近鄰傳播算法相關(guān)步驟：

代表矩陣初始化，令a（i,k）=0,設(shè)置實(shí)驗(yàn)參考值p并計(jì)算相似矩陣s。

根據(jù)上述公式（1）～（3）更新代表矩陣及適選矩陣。

最終得到聚類(lèi)結(jié)果，結(jié)合實(shí)際情況判斷該聚類(lèi)結(jié)果是否符合要求，符合，迭代終止；反之重復(fù)上述步驟（2），直至達(dá)到實(shí)際聚類(lèi)要求，迭代終止，輸出結(jié)果。

3 算例分析

3.1 數(shù)據(jù)采集

本文實(shí)際數(shù)據(jù)采集自中國(guó)民航飛行學(xué)院飛行訓(xùn)練飛機(jī)的 ADS-B數(shù)據(jù)。ADS-B（Automatic Dependent Surveillance-Broadcast）即廣播式自動(dòng)相關(guān)監(jiān)視，其實(shí)際原理是利用航空器將機(jī)載導(dǎo)航設(shè)備確定的航空器識(shí)別信息、位置、速度、高度、方向和爬升率等相關(guān)信息按照標(biāo)準(zhǔn)組成ADS-B報(bào)文，通過(guò)數(shù)據(jù)鏈路，按照一定的時(shí)間間隔進(jìn)行廣播式發(fā)送。飛行器的運(yùn)行軌跡是連續(xù)平滑的，航跡數(shù)據(jù)就是飛行器在運(yùn)動(dòng)過(guò)程中根據(jù)ADSB報(bào)文采樣得到的數(shù)據(jù)。每個(gè)航跡點(diǎn)包含經(jīng)度、緯度、高度的三維坐標(biāo)信息。本文選取100-400的航跡數(shù)據(jù)點(diǎn)，利用離散余弦變化對(duì)航跡數(shù)據(jù)集做預(yù)處理[11]。

3.2 實(shí)驗(yàn)參數(shù)設(shè)定

AP聚類(lèi)算法需要預(yù)先設(shè)置偏向參數(shù)p以得到不同類(lèi)別個(gè)數(shù)的缺陷[12]，偏向參數(shù)p和阻尼因子λ分別對(duì)聚類(lèi)數(shù)量大小和聚類(lèi)震蕩程度造成相關(guān)影響。因此設(shè)定適宜的偏向參數(shù)p和阻尼因子對(duì)聚類(lèi)結(jié)果也有較大影響，本文設(shè)定阻尼因子λ=0.9，偏向參數(shù)初值為相似度中值。設(shè)置上限迭代次數(shù)為500次，聚類(lèi)中心迭代次數(shù)50次為迭代終止條件[11]。

3.3 具體步驟

（1）數(shù)據(jù)過(guò)濾：初選航跡數(shù)據(jù)點(diǎn)數(shù)在100-400之間的航跡數(shù)據(jù)集，篩選過(guò)濾其中的意外突發(fā)事件造成的非正常航跡數(shù)據(jù)點(diǎn)。

（2）降噪處理：利用離散余弦變換對(duì)航跡數(shù)據(jù)進(jìn)行預(yù)處理，利用離散余弦變換保留大于300的DCT系數(shù)，再對(duì)保留數(shù)據(jù)進(jìn)行離散余弦逆變換重新構(gòu)建飛行器航跡。

（3）DTW處理：基于上述處理計(jì)算DTW相似度矩陣s。

（4）聚類(lèi)分析：利用AP算法對(duì)上述航跡進(jìn)行聚類(lèi)。

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

其最后聚類(lèi)結(jié)果顯示，291條飛行航跡數(shù)據(jù)集，共劃分出7個(gè)聚類(lèi)。如圖1和2所示。圖中我們可以看出前面6類(lèi)的聚類(lèi)的效果比較好，但第七類(lèi)結(jié)果表現(xiàn)并不令人滿(mǎn)意，分析其原因是該類(lèi)里的航跡與其他類(lèi)里的航跡相似度低，同時(shí)由于偏向參數(shù)p對(duì)聚類(lèi)結(jié)果影響很大卻又難以確定其具體某一個(gè)值來(lái)得到最佳聚類(lèi)結(jié)果，使得該類(lèi)里看上去不相似的航跡也聚類(lèi)到一個(gè)類(lèi)里。針對(duì)上述問(wèn)題，如何進(jìn)行進(jìn)一步的聚類(lèi)優(yōu)化，文獻(xiàn)[13]和[14]提出了解決方案，除此之外以進(jìn)一步搜索偏向參數(shù)也可以達(dá)到更佳的聚類(lèi)效果。

圖1 聚類(lèi)結(jié)果前三類(lèi)

圖2 聚類(lèi)結(jié)果后四類(lèi)

4 結(jié)語(yǔ)

由于我國(guó)民航事業(yè)的快速發(fā)展，空中運(yùn)輸需求與空域資源不足的矛盾日益加大，解決矛盾的根本途徑就是要對(duì)空中交通管理實(shí)施更加精準(zhǔn)化的管理，對(duì)飛行器航跡進(jìn)行分析和規(guī)劃，對(duì)實(shí)現(xiàn)智慧化空中交通管理有著重大意義。本文利用AP算法對(duì)飛行器航跡進(jìn)行聚類(lèi)，AP算法相對(duì)于傳統(tǒng)聚類(lèi)算法具有更高效更快速更精準(zhǔn)更便捷的優(yōu)點(diǎn)，其在其他領(lǐng)域也有著十分出色的表現(xiàn)。航跡聚類(lèi)分析是依據(jù)數(shù)據(jù)挖掘（Data Min?ing）中聚類(lèi)分析的方法，通過(guò)引入相關(guān)學(xué)科的知識(shí)來(lái)不斷改善聚類(lèi)的效果。本文結(jié)合中國(guó)民航飛行學(xué)院飛行訓(xùn)練飛機(jī)的ADS-B飛行數(shù)據(jù)，根據(jù)檢測(cè)雷達(dá)固定掃描周期特性，確立航跡時(shí)序列，針對(duì)航跡不等長(zhǎng)的特性，采用與傳統(tǒng)歐氏距離相區(qū)別的DTW距離來(lái)作為AP算法的相似性度量指標(biāo)。同時(shí)為了降低航跡噪聲數(shù)據(jù)，使用了經(jīng)典的離散余弦變換DCT方法來(lái)對(duì)航跡數(shù)據(jù)進(jìn)行降噪優(yōu)化，其最后得到的航跡聚類(lèi)效果良好，同時(shí)也對(duì)該方法中偏向參數(shù)p造成的某些聚類(lèi)效果不佳的情況進(jìn)行了分析，并提出了解決方法。