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

（1.中國民用航空飛行學院機場學院，廣漢 618300；2.中國民用航空飛行學院計算機學院，廣漢 618300；3.中國民用航空飛行學院航空工程學院，廣漢 618300）

0 引言

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

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

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

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

1 基本概念

1.1 近鄰傳播（AAPP）算法

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

1.2 飛行航跡

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

1.3 離散余弦變換（DDCT）

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

1.4 動態(tài)時間規(guī)整（DTW）

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

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

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

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

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

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

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

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

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

若n=m，可直接計算兩個序列的距離；

若n≠m，則需要線性縮放，即把短的航跡時序列線性放大到和長序列一樣的長度，或者把長的線性縮短到和短序列一樣的長度，再進行比較。具體如下：

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

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

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

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

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

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

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

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

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

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

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

3 算例分析

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

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

3.2 實驗參數(shù)設(shè)定

AP聚類算法需要預先設(shè)置偏向參數(shù)p以得到不同類別個數(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ù)點數(shù)在100-400之間的航跡數(shù)據(jù)集，篩選過濾其中的意外突發(fā)事件造成的非正常航跡數(shù)據(jù)點。

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

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

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

3.4 實驗結(jié)果分析

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

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

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

4 結(jié)語

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