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

張榆薪 王欣

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

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

DOI：10.11907/rjdk.172682

中圖分類(lèi)號(hào)：TP312

文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引言

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

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

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

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

1 AP聚類(lèi)算法

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

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

AP算法的基本流程如下：

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

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

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

2 相似度測(cè)量與軌跡表示

2.1 基于DTW距離的相似度測(cè)量

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

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

2.2 航跡表示

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

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

3 實(shí)驗(yàn)與分析

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

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

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

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

實(shí)驗(yàn)基本流程如下：

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

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

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

（4）進(jìn)行AP聚類(lèi)。

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

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

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

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

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

5 結(jié)語(yǔ)

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

參考文獻(xiàn)：

[1] 趙恩來(lái)，郝文寧，趙飛，等.改進(jìn)的基于密度的航跡聚類(lèi)算法[J].計(jì)算機(jī)工程， 2011（9）：270-272.

[2] 王超，徐肖豪，王飛.基于航跡聚類(lèi)的終端區(qū)進(jìn)場(chǎng)程序管制適用性分析[J].南京航空航天大學(xué)學(xué)報(bào)，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] 王超，王明明，王飛.基于改進(jìn)的模糊C-Means航跡聚類(lèi)方法研究[J].中國(guó)民航大學(xué)報(bào)，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距離的時(shí)間序列相似性度量[J].微計(jì)算機(jī)信息，2007（27）：204-206.

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

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

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

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