徐 濤，李永祥，呂宗平

（1.中國民航大學計算機科學與技術學院，天津300300；2.中國民航大學中國民航信息技術科研基地，天津300300）

基于航跡點法向距離的航跡聚類研究

徐 濤1，2，李永祥1，呂宗平2

（1.中國民航大學計算機科學與技術學院，天津300300；2.中國民航大學中國民航信息技術科研基地，天津300300）

隨著民航業(yè)的飛速發(fā)展，機場噪聲污染問題越來越嚴重，研究航跡聚類對機場噪聲預防治理工作具有重要意義。現(xiàn)有航跡聚類算法所采用的航跡點對選取方式，無法實現(xiàn)所選航跡點對在空間上的對應，嚴重影響聚類效果。針對這一問題，提出一種基于航跡點法向距離的航跡聚類模型。該模型采用航跡點法向距離作為航跡相似性度量方法，有效地解決了因飛機速度差異引起的航跡點對選取不匹配問題。通過K-medoids聚類算法對航跡進行二維和三維聚類，使用Davies Bouldin（DB）指標、Dunn指標對聚類結果進行評價。實驗表明，提出的模型能夠更好地度量航跡之間的相似性，航跡聚類效果更好，從而驗證了該模型的合理性和有效性。

航跡相似性；航跡聚類；K-medoids；聚類有效性評價；噪聲預測

0 引 言

隨著民用航空成為更加高效和快捷的出行方式，越來越多的人將飛機作為出行選擇，從而促進了中國民航業(yè)迅猛發(fā)展。新建、擴建機場帶來了日益嚴重的機場周邊噪聲問題。機場噪聲預測是開展機場噪聲評價及其環(huán)境影響評估的重要基礎，因此，科學合理地對機場周邊的噪聲進行預測尤為重要。

飛行航跡決定機場周圍噪聲的分布模式，民用機場的運行每天都會產(chǎn)生大量航跡數(shù)據(jù)，每年積累海量的歷史航跡數(shù)據(jù)。直接利用海量航跡進行噪聲預測、噪聲評估、航跡優(yōu)化等研究，易導致研究方法的復雜以及研究結果的不理想。因此，本文基于航跡聚類思想針對具有代表性的航跡進行研究。同時根據(jù)噪聲監(jiān)測點數(shù)據(jù)、雷達數(shù)據(jù)，結合具體地理位置研究每一簇航跡的噪聲分布模式。

目前，關于航跡聚類的研究主要有兩大類方法：一類為文獻［1］提出的基于航跡點比對的航跡聚類方法，該方法僅建立了一個初步的航跡聚類過程框架，沒有考慮因航空器飛行速度差異所帶來的空間航跡點不匹配所導致的相似度偏差；另一類是文獻［2］提出的基于最長公共子序列的相似性度量算法，并把聚類結果應用到異常航跡預警，該方法根據(jù)航跡轉折點進行聚類，用轉折點落入同一簇的數(shù)目來度量航跡相似性。通常，實際數(shù)據(jù)中航跡轉折點數(shù)目較少，故其航跡相似性度量誤差較大。此外，文獻［3］研究了基于軌跡的異常檢測；文獻［4］分析了常用軌跡相似性度量方法在聚類有效性和時間成本上的優(yōu)劣。

文獻［5］改進了文獻［1］的算法，提出根據(jù)前后附近點最短距離來度量航跡相似性，將聚類結果應用到終端區(qū)的進場程序管制，改進并優(yōu)化現(xiàn)有進離場飛行程序。文獻［6］提出了基于時空分布的航跡聚類分析，并在空管進近管制指揮中得到了應用。

上述提出的兩種航跡聚類方法同樣沒有解決因飛行速度不同引起的航跡點對選取不匹配的問題，故航跡聚類效果并不理想，聚類結果也沒有使用聚類有效性指標進行評價。根據(jù)“環(huán)境影響評價技術導則：聲環(huán)境”［7］，深入研究航跡的噪聲影響范圍和大小需要更加精細的航跡相似性度量方法對航跡數(shù)據(jù)聚類，并使用航跡聚類結果和機場噪聲數(shù)據(jù)進行結合研究。

1 基本概念及理論

1.1 航跡的特征與表示

航跡數(shù)據(jù)是由空管部門使用雷達監(jiān)測設備獲取飛機的實時經(jīng)緯度、海拔高度等數(shù)據(jù)。雷達獲取的航跡數(shù)據(jù)由一系列離散的航跡點組成，離散化程度由雷達的掃描周期（通常為3～5 s）決定。若將每條航跡所有航跡點按時間順序連接，則形成一條由多個離散航跡點構成的航跡線。飛機進離場時，發(fā)動機引擎推力大小不一，飛行的速度隨之改變，導致在相同的時間間隔內(nèi)，雷達獲取的航跡數(shù)據(jù)所表征的實際空間間隔分布不均勻。

不失一般性，航跡可表示為

式中，Ti為第i條航跡；i∈［1，n］為航跡編號；n為航跡總條數(shù)。且Ti可用航跡點的數(shù)據(jù)集表示為式中，Pij表示第i條航跡中第j個航跡點的信息；j∈［1，m］為航跡點編號；m為航跡點總數(shù)。

每一個航跡點Pij定義為一個4維向量，即

式中，x、y、z、t分別表示第i條航跡中第j個航跡點的橫坐標緯度、縱坐標經(jīng)度、海拔高度和航跡點記錄時間，分別用pij（x）、pij（y）、pij（z）、pij（t）表示。

1.2 航跡相似性度量方法

飛機的離港航跡初始段，由于低空飛行，雷達無法監(jiān)測，現(xiàn)有的離港航跡數(shù)據(jù)都是從海拔250～350 m才開始被雷達監(jiān)測到。正由于航跡的這種特殊性，雷達監(jiān)測到的每條航跡的起始海拔高度通?；ゲ幌嗤?，如果直接使用基于航跡點對之間的距離來度量兩條航跡之間的相似性，會引起很大的誤差。因此，當兩條離港航跡數(shù)據(jù)起始海拔高度不一致時，需對航跡進行對準截取，即

設Ti＝｛Pi1，Pi2，…，Piu｝和Tj＝｛Pj1，Pj2，…，Pjv｝是任意兩條航跡。其中，u，v∈［1，m］分別表示第i條和第j條航跡的航跡點數(shù)目。分別以航跡Ti、Tj中第一個航跡點Pi1、Pj1海拔高度最高的點作為起始航跡點。不失一般性，假設pi1（z）＞pj1（z），則以Pi1作為起始航跡點，然后根據(jù)式（4），以Ti為基準航跡確定航跡Tj中與Pi1最近的航跡點Pjw，對航跡進行對準截取。

圖1給出了現(xiàn)有兩種基于航跡點比對的航跡相似性度量方法，圖1（a）表示文獻［1］方法的航跡點選取方式，該方法直接使用對準后的兩條航跡點對之間的距離和除以比對的點數(shù)，其航跡相似性度量r1（Ti，Tj）定義為

圖1 航跡相似性度量方法

圖1（b）表示文獻［5］方法的航跡點選取方式，該方法在圖1（a）基礎上進行改進，在計算每一對航跡點（如Pi2和Pj（w+1））間距離時，同時選取各航跡點前后最相近的兩個航跡點進行計算，以獲取在此位置附近的兩個航跡點之間的最短距離。其航跡相似性度量r2（Ti，Tj）定義為在5條距離中選取最短的距離作為當前航跡點對的距離，即

但是，這兩種方法都沒有解決因飛行速度不同引起的航跡點對選取不匹配的問題，故使用圖1中的方法進行航跡聚類效果不好。

1.3 初始簇中心算法

傳統(tǒng)聚類算法隨機選擇初始簇中心，易于導致聚類結果陷入局部最優(yōu)。為合理選取初始簇中心，航跡聚類初始簇中心的計算考慮采用最大距離積法［8］。

簇中心集合可表示為

式中，k表示簇中心的個數(shù)；ck表示第k個簇中心。

簇集合定義為

式中，C1，C2，…，Ck分別表示以c1，c2，…，ck為簇中心的航跡簇數(shù)據(jù)。

在航跡數(shù)據(jù)集F中取最高密度區(qū)域內(nèi)的航跡c1作為第1個聚類簇中心；取距離c1最遠的另一個航跡c2作為第2個聚類簇中心，計算F中其余每條航跡數(shù)據(jù)Ti與αk中的數(shù)據(jù)之間的距離d（Ti，c1）和d（Ti，c2）；推而論之，ck為滿足max（d（Ti，c1）×d（Ti，c2）×…×d（Ti，ck－1））的航跡數(shù)據(jù)Ti，Ti∈F，以此可得到k個初始聚類中心。

1.4 聚類評價指標

為了更好地評價聚類結果并選取理想的航跡聚類簇數(shù)目，選用Davies Bouldin（DB）指標［9］和Dunn指標［10］對航跡聚類結果進行評價。

DB指標定義為

式中，

Dunn指標定義為

式中，Ci表示第i個航跡簇內(nèi)的航跡數(shù)據(jù)；｜Ci｜表示第i簇內(nèi)的航跡條數(shù)，ci表示第i類的簇中心；Si表示第i簇內(nèi)各航跡數(shù)據(jù)與簇中心ci的距離和，即第i簇內(nèi)航跡數(shù)據(jù)的分散程度；d（ci，cj）表示第i簇中心到第j簇中心的距離；

理想的聚類結果是同一類間的各數(shù)據(jù)對象間相似度大，而不同類之間的相似度小。DB指標越小，Dunn指標越大聚類結果越好。使用這兩種評價指標可以確定理想的航跡聚類簇的個數(shù)。

2 基本航跡點法向距離的航跡聚類

2.1 基于航跡點法相距離的相似性度量方法

在分析航跡數(shù)據(jù)特征與圖1兩種航跡相似性度量方法基礎上，提出了一種基于航跡點法向距離的航跡相似性度量方法。該方法在圖1（b）基礎上，計算當前計算航跡點對的前后航跡點的法向距離，這樣就能很好地解決因飛行速度不同引起的航跡點對選取不匹配的問題，如圖2所示。

圖2 基于航跡點法向距離的相似性度量方法

根據(jù)航跡相似性度量方法r（Ti，Tj）的定義，從以下幾個方面對其合理性證明：

證明當i＝j時，Pie關于點Pi（e－1），Pie的對稱點是其本身，即Pie＝P′ie，根據(jù)兩點距離公式知d（Pie，P′ie）＝0，得出r（Ti，Ti）＝0成立。

證畢

證明由于d（Pie，P′ie）+d（Pjq，P′jq）計算的是兩點之間的歐式距離，即r（Ti，Tj）≥0成立。

證畢

（3）r（Ti，Tj）＝r（Tj，Ti）

證明

定義航跡相似性度量方法r（Ti，Tj）表示為

由d（Pjq，P′jq）+d（Pie，P′ie）＝d（Pie，P′ie）+d（Pjq，P′jq）可知，即r（Ti，Tj）＝r（Tj，Ti）成立。

證畢

（4）r（Ti，Ta）+r（Ta，Tj）≥r（Ti，Tj）

證明

證畢

由以上證明可知，基于航跡點法相距離的航跡相似性度量方法滿足距離公式的基本性質(zhì)，使用該度量方法結合航跡數(shù)據(jù)可以構造出計算航跡間的相似性矩陣R，且

2.2 K-medoids航跡聚類算法

考慮到每一條航跡數(shù)據(jù)都是由一系列的航跡點組成，航跡點數(shù)目可能都不相同，不具備典型的數(shù)據(jù)與屬性之間的對應關系特征，因此，本文選用基于劃分的聚類算法［11-12］對滿足指定條件的航跡數(shù)據(jù)集進行航跡相似度的聚類分析。由于航跡的離散性，K-medoids算法在航跡簇中選取真實的航跡作為簇中心，能很好地采用該方法結合航跡數(shù)據(jù)進行聚類。表1給出結合航跡數(shù)據(jù)的K-medoids算法。

表1 K-medoids航跡聚類算法

2.3 基于航跡點法向距離的航跡聚類模型

針對海量歷史航跡數(shù)據(jù)，使用航跡相似性度量方法第1.3節(jié)中初始簇中心算法、聚類評價指標構建適合機場噪聲預測的基于航跡點法向距離的航跡聚類模型。

將空管部門監(jiān)測到的機場原始雷達數(shù)據(jù)導入數(shù)據(jù)庫進行數(shù)據(jù)預處理。原始雷達航跡數(shù)據(jù)中有缺失、錯誤、不規(guī)則等臟數(shù)據(jù)，通過人工方式對數(shù)據(jù)清洗并篩選出完整的航跡數(shù)據(jù)。結合航跡相似性度量方法對選取的航跡數(shù)據(jù)計算相似性矩陣R。采用最大距離積的初始化簇中心算法選取k個初始簇中心。結合航跡相似性矩陣和選取的初始簇中心，使用K-medoids算法對航跡聚類，并用DB指標、Dunn指標對航跡聚類結果進行評價。根據(jù)評價結果，輸出聚類效果最好的航跡聚類中心和各個航跡簇內(nèi)的航跡對象信息。表2中給出了基于航跡點法向距離的航跡聚類模型。

表2 基于航跡點法向距離的航跡聚類模型

3 實驗結果與分析

為了驗證基于航跡點法向距離的航跡聚類模型的合理性，基于航跡的二維、三維聚類及航跡聚類結果導入NoiseMap（美國國防部研發(fā)的機場噪聲預測軟件，根據(jù)飛行航跡繪制噪聲等值線、計算噪聲影響范圍等），根據(jù)“機場周圍飛機噪聲環(huán)境標準”［13］對航跡聚類結果評估，設計了以下3組實驗。

實驗1 基于航跡的二維聚類。實驗采用某大型樞紐機場2013年的航跡數(shù)據(jù)，選取機場單條跑道一天的離港航跡數(shù)據(jù)進行試驗。為了保證航跡長度大致相同，以跑道中心為圓心，截取半徑為65 km內(nèi)的航跡數(shù)據(jù)。通過數(shù)據(jù)預處理，共獲取113條標準離港航跡數(shù)據(jù)。根據(jù)K-medoids聚類算法的特性，聚類數(shù)目小于樣本總數(shù)開平方，因此，聚類數(shù)目在2～≈11之間最好。通過第2.3節(jié)中的基于航跡點法向距離的航跡聚類模型計算可以得出不同聚類數(shù)目下二維航跡聚類評價指標結果，如表3所示。

表3 二維航跡聚類評價指標結果值

DB指標越小，Dunn指標越大，聚類效果越好。由表3可以看出，航跡聚類個數(shù)為5簇時的聚類結果最好。為了比較以上幾種航跡相似性度量方法的聚類效果，圖3給出了文獻［1］方法、文獻［5］方法、本文方法（基于航跡點法向距離）3種度量方法最好聚類結果的對比。

圖3 二維航跡聚類3種相似性度量方法對比

由圖3可以看出，本文方法DB指標比其他方法都小，Dunn指標比其他方法都大，表明其在二維航跡聚類中效果最好，其航跡聚類結果如圖4所示。

圖4 二維航跡聚類結果

圖4（a）是5簇的航跡聚類結果，圖4（b）、圖4（c）、圖4（f）成功地把相似性的航跡聚在一起。圖4（d）、圖4（e）兩種航跡簇比較接近，但圖4（d）的聚類結果有兩個航跡轉折點，圖4（e）的聚類結果有一個航跡轉折點，因此，圖4（d）、圖4（e）符合機場實際標準進離場飛行程序設計。

實驗2 基于航跡的三維聚類。在實驗1的航跡數(shù)據(jù)基礎上，加入航跡海拔高度信息，形成三維航跡數(shù)據(jù)。為保證三維航跡的長度基本相同，以跑道中心為球心，截取空間航跡點到球心距離小于65 km的航跡數(shù)據(jù)。通過第2.3節(jié)中的基于航跡點法向距離的航跡聚類模型計算可以得出不同聚類數(shù)目下基于航跡三維聚類的評價指標結果值，如表4所示。

表4 三維航跡聚類評價指標結果值

從表4可以看出，聚類個數(shù)為5簇時聚類效果最好。分別使用文獻［1］方法、文獻［5］方法代入航跡聚類模型，并選取最好的聚類評價結果值對比在圖5中。

由圖5得出，本文方法DB指標比其他兩種方法小，Dunn指標比其他兩種方法大，表明其在三維航跡聚類中結果最好，其航跡聚類結果如圖6所示。

圖5 三維航跡聚類3種相似性度量方法對比

圖6（a）是5簇的航跡聚類結果，圖6（b）、圖6（c）、圖6（d）、圖6（e）、圖6（f）分別表示單獨的每一簇的結果，每一航跡簇的結果在空間上都是獨立的，能夠很好地對航跡進行劃分。

實驗3 航跡聚類結果導入NoiseMap噪聲預測軟件繪制噪聲等值線。由于航跡簇內(nèi)航跡較多，將每一簇中所有航跡全部導入NoiseMap比較困難，因此，選取航跡簇內(nèi)具有代表性的航跡導入，實驗結果如圖7所示。由圖7可以得出，航跡簇內(nèi)的航跡噪聲等值線非常相似，表明航跡簇內(nèi)的航跡噪聲影響范圍相似。

圖6 三維航跡聚類結果

圖7 航跡聚類結果的噪聲等值線

由實驗1、實驗2得出，基于航跡點法向距離的相似性度量方法效果最好，能夠應用到更加精細的航跡聚類模型中。由實驗3得出每一航跡簇內(nèi)的噪聲影響范圍均具有相似性，由此驗證了基于航跡點法向距離的航跡聚類模型的合理性和有效性。

4 結束語

在分析航跡數(shù)據(jù)特征和航跡點比對方法的基礎上，提出了一種基于航跡點法向距離的航跡間相似性度量方法。通過實驗分析文獻［1］方法、文獻［5］方法、航跡點法向距離3種相似性度量方法在航跡二維和三維的聚類結果。使用聚類評價指標對結果進行評價，對比兩組實驗得出基于航跡點法向距離的方法聚類效果最好，并把聚類結果導入到Noise Map輸出噪聲等值線分析其噪聲影響范圍，每一簇的噪聲等值線基本相似，驗證了模型的合理性和有效性，并能夠很好的研究航跡聚類在機場噪聲預測上的應用。進一步的工作將結合三維航跡相似性矩陣、機場標準進離場程序、機型、飛行速度、天氣等噪聲主要影響因素，使用模糊聚類算法［14］或者模糊加權的聚類算法［15-16］提高航跡聚類的效率，挖掘噪聲分布模式和噪聲值相似的航跡簇，并對航跡聚類結果和機場噪聲監(jiān)測實際數(shù)據(jù)進行關聯(lián)研究。

［1］Frank R.Clustering of flight tracks［C］∥Proc.of the American Institute of Aeronautics and Astronautics，2010：1-9.

［2］Gariel M，Srivastava A N，F(xiàn)eron E.Trajectory clustering and an application to airspace monitoring［J］.IEEE Trans.on Intelligent Transportation Systems，2011，12（4）：1511-1524.

［3］Lee J G，Han J，Li X.Trajectory outlier detection：a partition and detect framework［C］∥Proc.of the 24th IEEE International Conference on Data Engineering，2008：140-149.

［4］Dahlbom A，Niklasson L.Trajectory clustering for coastal surveillance［C］∥Proc.of the 10th IEEE International Conference on Information Fusion，2007：1-8.

［5］Wang C，Xu X H，Wang F.ATC serviceability analysis of terminal arrival procedures using trajectory clustering［J］.Journal of Nanjing University of Aeronautics and Astronautics，2013，45（1）：130-139.（王超，徐肖豪，王飛.基于航跡聚類的終端區(qū)進場程序管制適用性分析［J］.南京航空航天大學學報，2013，45（1）：130-139.）

［6］Wang J N，Sun H，Zhao Y D.Approach trajectory clustering analysis based on time-space［J］.Science Technology and Engineering，2013，13（33）：78-81.（王潔寧，孫禾，趙元棣.基于時間-空間的進場航跡聚類分析［J］.科學技術與工程，2013，13（33）：78-81.）

［7］Ministry of Environment Protection of China.Technical guidelines for noise impact assessment［S］.Beijing：China Environmental Science Press，2009.（國家環(huán)境保護局.環(huán)境影響評價技術導則：聲環(huán)境［S］.北京：中國環(huán)境科學出版社，2009.）

［8］Xu J L，Xu B W，Zhang W F.Stable initialization scheme for K-means clustering［J］.Wuhan University Journal of Natural Sciences，2009，14（1）：24-28.

［9］Lee S S，Lin J C.An Accelerated K-means clustering algorithmusing selection and erasure rules［J］.Journal of Zhejiang University（Computers&Electronics），2012，13（10）：761-768.

［10］Zalik K R，Zalik B.Validity index for clusters of different sizes and densities［J］.Pattern Recognition Letters，2011，32（2）：221-234.

［11］Pardeshi B，Toshniwal D.Improved K-medoids clustering based on cluster validity index and object density［C］∥Proc.of the 2nd IEEE International Advance Computing Conference，2010：379-384.

［12］Gao D Y，Yang B R.An improved K-medoids clustering algorithm［C］∥Proc.of the 2nd International Conference on Computer and Automation Engineering，2010：132-135.

［13］Ministryof Environment Protection of China.GB9660-88 Standard of Aircraft Noise Environment Around Airport［S］.Beijing：China Environmental Science Press，1988.（國家環(huán)境保護局.GB／T9660-1988機場周圍飛機噪聲環(huán)境標準［S］.北京：中國環(huán)境科學出版社，1988.）

［14］Chen N，Xu Z S，Xia M M.Hierarchical hesitant fuzzy K-means clustering algorithm［J］.Applied Mathematics Journal of Chinese Universities（Series B），2014，29（1）：1-17.

［15］Wang L N，Wang J D，Li T.Cluster's feature weighting fuzzy clustering integrating rough sets and shadowed sets［J］.Systems Engineering and Electronics，2013，35（8）：1769-1776.（王麗娜，王建東，李濤.集成粗糙集和陰影集的簇特征加權模糊聚類算法［J］.系統(tǒng)工程與電子技術，2013，35（8）：1769-1776.）

［16］Wang L N，Wang J D.Feature weighting fuzzy clustering integrating rough sets and shadowed sets［J］.International Journal of Pattern Recognition and Artificial Intelligence，2012，26（4）：1-25.

Research on flight tracks clustering based on the vertical distance of track points

XU Tao1，2，LI Yong-xiang1，LüZong-ping2
（1.College of Computer Science and Technology，Civil Aviation University of China，Tianjin 300300，China；2.Information Technology Research Base of Civil Aviation Administration of China，Civil Aviation University of China，Tianjin 300300，China）

With the rapid development of the civil aviation industry，the noise pollution problem of airport is more and more serious.Research on flight tracks clustering is important for prevention and control of airport noise.The flight track point pair chose method which is the existing flight track clustering common method，could not achieve one to one match in the space，and it has a strong influence on the clustering results.In order to solve this problem，a flight track similarity measure model is proposed based on the vertical distance of track points.It can ignore the effects of flight's speed on flight tracks similarity.According to the daily tracks data，flight tracks can be clustered.2D and 3D clustering of the flight tracks can be achieved by the K-medoids clustering algorithm.And Davies Bouldin（DB）index and the Dunn index are used to evaluate the clustering results.Experimental results show that the proposed model can measure the similarity more profitably between the tracks and the results of flight tracks clustering are better.Therefore，the rationality and availability of the model，have been verified.

flight tracks similarity；flight tracks clustering；K-medoids；cluster validity assessment；noise prediction

TP 399 文獻標志碼：A DOI：10.3969／j.issn.1001-506X.2015.09.36

徐 濤（1962-），男，教授，博士研究生導師，主要研究方向為智能信息處理、民航信息系統(tǒng)理論與分析。

E-mail：txu＠cauc.edu.cn

李永祥（1990-），男，碩士研究生，主要研究方向為數(shù)據(jù)挖掘、機器學習。

E-mail：xiangcool5＠qq.com

呂宗平（1964-），男，副教授，主要研究方向為民航信息處理。

E-mail：zplv＠cauc.edu.cn

1001-506X（2015）09-2198-07

2014-10-21；

2015-01-02；網(wǎng)絡優(yōu)先出版日期：2015-03-23。

網(wǎng)絡優(yōu)先出版地址：http：／／www.cnki.net／kcms／detail／11.2422.TN.20150323.1706.005.html

國家自然科學基金重點項目（61139002）；國家高技術研究發(fā)展計劃（863計劃）（2012AA063301）；國家科技支撐計劃（2014BAJ04B02）；中國民用航空局科技項目（MHRD201006，MHRD201101）；中央高校基本科研業(yè)務費專項資金（3122013P013）資助課題