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

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

0 引言

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

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

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

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

1 基本概念

1.1 近鄰傳播（AAPP）算法

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

1.2 飛行航跡

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

1.3 離散余弦變換（DDCT）

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

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

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

2 基于近鄰傳播的航跡聚類算法

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

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

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

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

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

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

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

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

若n≠m，則需要線性縮放，即把短的航跡時(shí)序列線性放大到和長序列一樣的長度，或者把長的線性縮短到和短序列一樣的長度，再進(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，

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

2.3 基于近鄰傳播算法的航跡聚類

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

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

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

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

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

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

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

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

3 算例分析

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

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

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

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

3.3 具體步驟

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

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

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

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

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

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

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

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

4 結(jié)語

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