張榆薪 王欣

摘 要：隨著航空事業(yè)的發(fā)展，對航跡進行聚類分析，存在許多應(yīng)用價值。在分析歷史飛行航跡特征的基礎(chǔ)上，將航跡看作時間序列，采用近鄰傳播聚類算法，對航跡進行聚類分析，得到聚類結(jié)果并進行優(yōu)化分析。近鄰傳播算法（AP）是建立在相似度矩陣基礎(chǔ)上進行的聚類，為了得到相似度矩陣，結(jié)合航跡不等長的特征，選擇使用DTW距離作為航跡間相似性的度量；同時，使用DCT對航跡時序列進行降噪，以求得到更好的聚類效果。實驗結(jié)果表明：該方法在393條航跡的數(shù)據(jù)集中，劃分出11個聚類，提高了航跡聚類的準確性。

關(guān)鍵詞：飛行航跡；近鄰傳播算法；DTW距離；DCT

DOI：10.11907/rjdk.172682

中圖分類號：TP312

文獻標識碼：A 文章編號：1672-7800（2018）004-0089-02

Abstract：With the development of aviation industry， clustering analysis of trajectories has much application value. Based on the analysis of the characteristics of historical flight trajectories， this paper regards the trajectory as time series， and uses AP（Affinity Propagation） clustering algorithm to cluster the trajectories and get clustered results for optimization analysis. The AP algorithm is based on the similarity matrix. In order to get the similarity matrix， the DTW（Dynamic time warping） distance is selected as the measure of the similarity between trajectories， for which are of unequal length. Besides， we use DCT（Discrete Cosine Transform） to denoise the track time series to get a better clustering effect. The experimental results show that the method is divided into 11 clusters in the data set of 393 tracks， which improves the accuracy of track clustering.

Key Words：flight trajectories； Affinity Propagation； DTW distance； DCT

0 引言

將物理或抽象對象的集合分組成為由類似對象組成多個類的過程稱為聚類[1]。聚類分析已經(jīng)在多個領(lǐng)域廣泛應(yīng)用，如圖像識別、圖像檢索等。在民航領(lǐng)域，對飛行航跡數(shù)據(jù)的聚類分析，也有著良好應(yīng)用前景，如：在飛行程序分析和評價方面，計算出歷史航跡簇中的平均飛行航跡，然后與標準航線進行對比，可以分析飛行程序的適用性和改進方法等[2]。

飛行航跡是由檢測雷達周期掃描而得到的空中位置離散點列，可看作是時間序列。由于雷達的掃描周期往往是固定的，所以每條航跡實際上是一條等間隔時間序列。當(dāng)航跡被看成時間序列時，許多對時間序列的聚類算法也就可以被運用，如基于密度的時間序列聚類算法[1]、基于相似性的時間序列聚類算法。

目前，已有不少對飛行航跡的聚類研究，如基于密度的航跡聚類[1]、基于分層的航跡聚類[2]、自動化粒子群算法的航跡聚類[3]、基于C_Means的航跡聚類[4]等。

本文針對某機場終端區(qū)的實際飛行航跡數(shù)據(jù)，首先采用離散余弦變換（DCT）對航跡進行平滑處理，然后用動態(tài)時間彎曲（DTW）計算不等長航跡之間的相似性度量，在此基礎(chǔ)之上應(yīng)用近鄰傳播算法（Affinity Propagation，AP）對航跡進行聚類分析。最后進行實驗結(jié)果分析，該方法在航跡聚類分析方面有效。

1 AP聚類算法

AP算法是由Frey等[5]在《Science》一篇文章中提出的，通過消息傳遞實現(xiàn)聚類。

當(dāng)?shù)螖?shù)超過設(shè)定值或者多次聚類結(jié)果相同時，迭代終止。為了避免震蕩發(fā)生，AP算法在信息更新時引入一個阻尼因子λ∈[0，1）。

AP算法的基本流程如下：

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

（2）按照式（1）-式（3）更新矩陣r（i，k）和a（i，k）。

（3）判斷聚類結(jié)果是否滿足要求，如果沒有，則重復(fù)步驟（2），直到滿足要求，輸出結(jié)果。

2 相似度測量與軌跡表示

2.1 基于DTW距離的相似度測量

常用于AP算法的相似度指標為歐式距離，不過歐式距離只適用于等長序列，考慮到航跡時序列的不等長特性，歐式距離不再適合作為其相似性的指標。當(dāng)然有的文章，如文獻[3]提出了處理數(shù)據(jù)集的方法，使歐式距離也能使用在航跡聚類上，不過其本質(zhì)是等長序列?？紤]到航跡數(shù)據(jù)不等長特性本身固有的意義，這里采用不等長也可以使用的DTW距離作為相似度測量指標。

DTW距離的算法思想可以歸結(jié)為：運用動態(tài)規(guī)劃思想尋找一條具有最小彎曲代價的最佳路徑[6]。

2.2 航跡表示

為了提高航跡時序列的相似性檢索性能，用離散余弦變換（DCT）對時間進行處理，以降低時序列的噪聲，使時序列更加平滑。

作為一種經(jīng)典的時域-頻域轉(zhuǎn)換方法，離散余弦變換目前已經(jīng)得到了廣泛應(yīng)用。將此方法用于時序列的相似性檢索上，也被證明了相對以前方法，性能有很大提升[7]。

3 實驗與分析

3.1 實驗數(shù)據(jù)集及預(yù)處理

本文使用的實驗數(shù)據(jù)集來自于文獻[3]里提到的航跡數(shù)據(jù)集，該數(shù)據(jù)集中包含了許多舊金山國際機場的航班軌跡及每條航跡的描述信息。每條航跡都包含x、y、z坐標，其中z坐標就是航班的實際飛行高度。本文提取2006年1月1日航跡數(shù)據(jù)點在150～400之間的航跡數(shù)據(jù)集，并進行DCT預(yù)處理。

3.2 實驗參數(shù)設(shè)定及基本流程

AP 算法中有兩個重要參數(shù)：參數(shù)p的大小會影響聚類數(shù)目，而參數(shù)λ的大小會影響聚類過程的震蕩程度。本文實驗設(shè)定p初值為相似度中值，λ=0.9。其次，迭代停止的限制條件為：最大迭代次數(shù)為500，聚類中心保持不變，迭代次數(shù)50。

實驗基本流程如下：

（1）篩選數(shù)據(jù)。排除占小部分的突發(fā)飛行航跡數(shù)據(jù)，并取數(shù)據(jù)點數(shù)在150～400之間的航跡數(shù)據(jù)集。

（2）對航跡進行DCT處理，首先進行DCT變換，然后保留大于2 500的DCT系數(shù)，再進行DCT逆變換重構(gòu)飛行航跡。

（3）計算基于DTW的相似度矩陣s。

（4）進行AP聚類。

3.3 實驗結(jié)果與分析

初次聚類分析將航跡劃分為10個聚類，如圖1、圖2所示。不過第7類結(jié)果并不理想，它至少能分成兩類。該問題是偏向參數(shù)p難以確定其值而得到最優(yōu)聚類結(jié)果引起的。文獻[8]和[9]各自提出了一種可行的優(yōu)化方案。本文結(jié)合數(shù)據(jù)科學(xué)中的簡單算法，用數(shù)據(jù)解決具體問題的思想，用如下基本流程進行優(yōu)化：

（1）搜索偏值空間（這里即簡單的向小或向大）。

（2）將新的偏值用來對第7類進行再次聚類，直到得到不少于兩類的聚類結(jié)果為止。

再次聚類的結(jié)果如圖3所示，第7類被成功地分成了兩類。

5 結(jié)語

使用基于DTW距離相似性測量的AP算法對飛行航跡進行了聚類分析，實驗證實了在圖像識別、圖像檢索等領(lǐng)域有出色表現(xiàn)的AP聚類算法，對航跡聚類也是可行與出色的。在聚類前，使用DCT對航跡數(shù)據(jù)進行降噪優(yōu)化。對由于偏向參數(shù)p難以確定其值以獲得最優(yōu)解的問題，提出了一種解決辦法，實驗也證明了其可行性。

參考文獻：

[1] 趙恩來，郝文寧，趙飛，等.改進的基于密度的航跡聚類算法[J].計算機工程， 2011（9）：270-272.

[2] 王超，徐肖豪，王飛.基于航跡聚類的終端區(qū)進場程序管制適用性分析[J].南京航空航天大學(xué)學(xué)報，2013（1）：130-139.

[3] ZAHEDEH I， MOHAMMAD S M， AJITH A. Automated clustering of trajectory data using a particle swarm optimization[J]. Computers，Environment and Urban Systems，2016，55（1）：55-65.

[4] 王超，王明明，王飛.基于改進的模糊C-Means航跡聚類方法研究[J].中國民航大學(xué)報，2013（3）：14-18.

[5] FREY B J， DUECK D. Clustering by passing messages between data points[J].Science，2007，315：972-976.

[6] 陸薛妹，胡軼，方建安.基于分段極值DTW距離的時間序列相似性度量[J].微計算機信息，2007（27）：204-206.

[7] 劉端陽，張瑞強.基于離散余弦變換的時間序列相似性檢索[J].計算機系統(tǒng)應(yīng)用， 2012（9）：195-197+186.

[8] 唐東明，朱清新，楊凡，等.一種有效的蛋白質(zhì)序列聚類分析方法[J].軟件學(xué)報， 2011（8）：1827-1837.

[9] 王開軍，張軍英，李丹，等.自適應(yīng)仿射傳播聚類[J].自動化學(xué)報，2007（12）：1242-1246.

（責(zé)任編輯：何 麗）