基于平衡核函數(shù)聚類(lèi)的飛行航跡數(shù)據(jù)分析方法

唐 靜，王 婧，李冬梅

（92830部隊(duì)，?？?71122）

關(guān)于航跡的研究，國(guó)內(nèi)外學(xué)者已經(jīng)開(kāi)始進(jìn)行并取得了一定的成果，例如基于密度的航跡聚類(lèi)方法[1]、基于粒子群的航跡聚類(lèi)[2]、面向目標(biāo)航跡融合的坐標(biāo)變換運(yùn)用技術(shù)[3]、對(duì)航跡進(jìn)行加權(quán)融合的權(quán)值動(dòng)態(tài)分配算法[4]、基于C均值的航跡聚類(lèi)[5]。但是對(duì)大量航跡進(jìn)行識(shí)別和分類(lèi)的應(yīng)用研究仍然還處于開(kāi)始階段。比如，Noyes[6]提出的模糊邏輯的航跡分類(lèi)算法，可以區(qū)分氣象雜波和航跡；文獻(xiàn)[7]實(shí)現(xiàn)了多航路目標(biāo)和非航路目標(biāo)的分類(lèi)；文獻(xiàn)[8]利用基于密集的聚類(lèi)思想，通過(guò)多維目標(biāo)航跡的聚類(lèi)，實(shí)現(xiàn)對(duì)目標(biāo)行為規(guī)律的挖掘分析；文獻(xiàn)[9]基于一致性預(yù)測(cè)原理，通過(guò)設(shè)計(jì)一致性多類(lèi)分類(lèi)器，實(shí)現(xiàn)對(duì)目標(biāo)行為模式的在線學(xué)習(xí)與分類(lèi)識(shí)別；文獻(xiàn)[10]對(duì)不確定性航跡的自適應(yīng)預(yù)測(cè)進(jìn)行了研究；文獻(xiàn)[11]對(duì)航跡點(diǎn)在坐標(biāo)轉(zhuǎn)換方面進(jìn)行了討論；文獻(xiàn)[12]分析了誤差對(duì)航跡點(diǎn)的干擾；文獻(xiàn)[13]基于綜合隸屬度提出航跡起始關(guān)聯(lián)的窮舉法；文獻(xiàn)[14]對(duì)航跡初值進(jìn)行修正來(lái)提高多尺度聚類(lèi)濾波的準(zhǔn)確性；文獻(xiàn)[15]提出來(lái)基于假設(shè)檢驗(yàn)的航跡-航路相關(guān)方法。但是現(xiàn)有的研究方法大多按照全局最優(yōu)來(lái)進(jìn)行參數(shù)調(diào)節(jié)，對(duì)航跡數(shù)據(jù)量大、交連多、非線性特征等特點(diǎn)，要做到盡可能精確的聚類(lèi)分類(lèi)十分困難。

支持向量機(jī)理論[16]自20 世紀(jì)90 年代創(chuàng)立并開(kāi)始發(fā)展，由于具有結(jié)構(gòu)簡(jiǎn)單、強(qiáng)大的泛化能力和容易實(shí)現(xiàn)全局最優(yōu)結(jié)果等優(yōu)點(diǎn)，被快速應(yīng)用到模式識(shí)別和數(shù)據(jù)挖掘的領(lǐng)域。支持向量機(jī)的核函數(shù)是構(gòu)建適合系統(tǒng)的關(guān)鍵，通過(guò)核函數(shù)的非線性映射方法，可以將輸入的數(shù)據(jù)映射到高維的特征空間，變化成線性問(wèn)題進(jìn)行討論。這種處理思路使得支持向量機(jī)方法在特征提取、主成分分析和分類(lèi)識(shí)別等領(lǐng)域得到廣泛應(yīng)用。因此，研究核函數(shù)的構(gòu)造和設(shè)計(jì)變得至關(guān)重要，其要求是對(duì)待分析的數(shù)據(jù)變化敏感，表現(xiàn)形式具有一定的意義。

本文立足提高飛行航跡數(shù)據(jù)聚類(lèi)分析的準(zhǔn)確性，基本思路為：在航跡特征數(shù)據(jù)的預(yù)處理階段，加入一種平衡核函數(shù)用于K-均值聚類(lèi)的處理過(guò)程，可以解決高維特征數(shù)據(jù)帶來(lái)的奇異性，還能提高交疊樣本的聚類(lèi)性能；設(shè)計(jì)了一種模糊支持向量機(jī)實(shí)現(xiàn)航跡的分類(lèi)。通過(guò)實(shí)際航跡數(shù)據(jù)，測(cè)試了本文設(shè)計(jì)的基于平衡核函數(shù)航跡聚類(lèi)和模糊支持向量機(jī)分類(lèi)器有效性。

1 飛行航跡數(shù)據(jù)的選擇和處理

本文分析使用ADS-B 系統(tǒng)的航跡數(shù)據(jù)進(jìn)行研究。ADS-B 系統(tǒng)的航跡數(shù)據(jù)是按照一定時(shí)序發(fā)送的位置數(shù)據(jù)的序列，這是一種多維度的數(shù)據(jù)集[17]。飛行器的航跡自民用空管軟件上獲取，其軟件界面如圖1所示，軟件中可得到航班飛行航跡點(diǎn)的時(shí)間、航班號(hào)、經(jīng)緯度、高度、速度和航向。

航跡的原始數(shù)據(jù)為：

式（1）中：T為航跡集，i∈[1,2,…,n] 是航跡點(diǎn)編號(hào)，n為航跡總數(shù)；TRi為第i個(gè)航跡點(diǎn)序列。

式（2）中：Pij為第i條航跡中第j個(gè)多維特征點(diǎn)；j∈[1,2,…,m] ，m為航跡點(diǎn)的總數(shù)。

當(dāng)采用時(shí)間、經(jīng)度、緯度、高度、速度、航向這6 個(gè)特征時(shí)，得到：

即第i條航跡中第j個(gè)多維特征點(diǎn)的特征。然后，對(duì)數(shù)據(jù)進(jìn)行坐標(biāo)轉(zhuǎn)換，由于航跡數(shù)據(jù)是經(jīng)緯度數(shù)據(jù)，為便于分析和計(jì)算，將數(shù)據(jù)從大地坐標(biāo)系轉(zhuǎn)換到直角坐標(biāo)系，采用墨卡托投影轉(zhuǎn)換，得到航跡數(shù)據(jù)樣本集。

圖1 民用空管軟件的航跡圖Fig.1 Track chart of civil air traffic control software

2 平衡核函數(shù)K-均值聚類(lèi)方法

假設(shè)對(duì)2 個(gè)數(shù)據(jù)樣本進(jìn)行非線性變換?()，得到映射的內(nèi)積為核函數(shù)k(x,z)，即k(x,z)=?(x),?(z) 。其中，特征變換?:x→?(x)為核函數(shù)導(dǎo)出的，X和?(x)為輸入空間及特征空間。

核算法的主要特點(diǎn)有：

1）可以將非線性問(wèn)題線性化；

2）核函數(shù)可以方便地與不同的算法結(jié)合使用；

3）核函數(shù)的使用避免了計(jì)算特征空間的內(nèi)積，與維數(shù)無(wú)關(guān)，不會(huì)造成“維數(shù)災(zāi)難”；

4）核函數(shù)的引入，適用于高維度問(wèn)題的分析。

傳統(tǒng)的K-均值方法是基于最小距離原則來(lái)進(jìn)行聚類(lèi)的[18]，是一種非監(jiān)督學(xué)習(xí)方法。容易導(dǎo)致聚類(lèi)內(nèi)外的樣本數(shù)量相差過(guò)大，形成聚類(lèi)結(jié)果失衡，從而影響聚類(lèi)產(chǎn)生的結(jié)果。能不能有一種兼顧內(nèi)外樣本數(shù)量的核函數(shù)構(gòu)造方法呢？本文提出了一種新的聚類(lèi)方法——平衡核函數(shù)K-均值法，即合理的構(gòu)造核函數(shù)，在數(shù)據(jù)被映射到高維的非線性空間之后，進(jìn)行K-均值聚類(lèi)同時(shí)兼顧聚類(lèi)之間的樣本數(shù)的方法。

本文對(duì)航跡特征數(shù)據(jù)進(jìn)行聚類(lèi)的步驟如下：

1）獲取航跡數(shù)據(jù)集，對(duì)其中的經(jīng)緯度數(shù)據(jù)進(jìn)行墨卡托坐標(biāo)變換，形成數(shù)據(jù)樣本集；

2）對(duì)數(shù)據(jù)樣本集的數(shù)據(jù)進(jìn)行高斯核變換，映射到特征空間；

3）按照需要聚合的類(lèi)別數(shù)，設(shè)定初始中心，分別求得與中心的差值，在特征空間中完成平衡核函數(shù)K-均值聚類(lèi)；

4）滿足條件的xi：當(dāng)D達(dá)到最小的xi所屬的聚類(lèi)就是xi應(yīng)該屬于的聚類(lèi)；

5）完成樣本數(shù)據(jù)集的聚類(lèi)。

假設(shè)經(jīng)過(guò)歸一化變換后的飛行器的航跡數(shù)據(jù)為{(x1,z1),(x2,z2),…,(xN,zN)}，其中zi（i=1,2,…,N）是類(lèi)別標(biāo)志，zi∈{1,2,…,c} ，xi∈?（i=1,2,…,N）是第i個(gè)樣本，c是類(lèi)別總數(shù)。

特征空間F是Φ( )xi，則平衡核函數(shù)K-均值聚類(lèi)在特征空間F的目標(biāo)函數(shù)定義為：

可以看到，在式（4）中，第1 部分類(lèi)似一般用到的核K-均值方法，當(dāng)?shù)? 部分最小化時(shí)，聚類(lèi)是收斂的。聚類(lèi)個(gè)數(shù)用L表示，Li是第i個(gè)樣本所屬聚類(lèi)的類(lèi)標(biāo)，是F特征空間中屬于第Li個(gè)聚類(lèi)類(lèi)型中的樣本平均值，NLi為第Li個(gè)聚類(lèi)中的樣本總數(shù)，K(?,?)是核函數(shù)。

式（4）中，第2部分設(shè)計(jì)可反映出類(lèi)與類(lèi)之間及聚類(lèi)之內(nèi)樣本數(shù)是否平衡，ξ和β是加權(quán)系數(shù)，Nl為第l個(gè)聚類(lèi)之內(nèi)的樣本總數(shù)，Nˉ為平均值，用來(lái)表示屬于第c類(lèi)的第l個(gè)聚類(lèi)中的樣本數(shù)，第l個(gè)聚類(lèi)之內(nèi)的各類(lèi)樣本數(shù)的平均值用表示。即當(dāng)D達(dá)到最小的xi所屬的聚類(lèi)就是xi應(yīng)該屬于的聚類(lèi)。第2 部分的設(shè)計(jì)是平衡核函數(shù)K-均值聚類(lèi)的核心。與傳統(tǒng)的K-均值聚類(lèi)相比，在聚類(lèi)時(shí)，式（4）中第1 部分也會(huì)引起第2 部分的變化，這樣就在全局動(dòng)態(tài)聚類(lèi)的過(guò)程中使D最小化。

這樣聚類(lèi)處理之后得到的數(shù)據(jù)在特征空間中分布會(huì)滿足距離相近的樣本聚集在同一類(lèi)中，距離遠(yuǎn)的樣本不會(huì)出現(xiàn)在同一類(lèi)中，有效避免了樣本交疊嚴(yán)重的情況。

3 模糊支持向量機(jī)的多分類(lèi)器設(shè)計(jì)

在數(shù)據(jù)完成特征提取和歸一化的標(biāo)準(zhǔn)處理后，本文設(shè)計(jì)了一種基于模糊支持向量機(jī)的多分類(lèi)器進(jìn)行分類(lèi)，用模糊隸屬度來(lái)去除數(shù)據(jù)中偏差較大的點(diǎn)對(duì)分類(lèi)器的影響。

基于模糊支持向量機(jī)的飛行航跡分類(lèi)基本構(gòu)想如圖2所示。

圖2 基于模糊支持向量機(jī)的飛行航跡分類(lèi)步驟Fig.2 Flight track classification steps based on fuzzy SVM

假設(shè)訓(xùn)練樣本集為：

(x1,y1,μ(x1)),(x2,y2,μ(x2)),…,(xn,yn,μ(xn)) ，xi∈?N，yi∈{- 1,1}，0 ＜μ(xi)≤1。設(shè)原始空間?N到高維特征空間Z的映射關(guān)系為z=?(x)。該樣本隸屬于某類(lèi)的可靠程度用模糊隸屬度μ(xi)來(lái)表示，支持向量機(jī)中設(shè)置的目標(biāo)函數(shù)中的分類(lèi)誤差項(xiàng)用ξi來(lái)表示，加權(quán)誤差項(xiàng)是μ(xi)ξi。如下目標(biāo)函數(shù)的最優(yōu)解即是需要找到的最優(yōu)超分類(lèi)平面。

式（5）中：線性分類(lèi)項(xiàng)，函數(shù)yi的權(quán)系數(shù)用w表示，設(shè)置懲罰因子C為常數(shù)，需要事先指定。

由式（5）可以看出，xi可看作不重要的樣本忽略，因?yàn)棣?xi)會(huì)減小ξi的影響。

這時(shí)得到的是最優(yōu)分類(lèi)面，其判別函數(shù)表示為：

式中：K(xi,x)為核函數(shù)，本文采用常用的高斯核。

本文設(shè)計(jì)的模糊支持向量機(jī)中使用的隸屬度函數(shù)應(yīng)用核密度函數(shù)的估計(jì)方法來(lái)構(gòu)造。

從該函數(shù)的形式可以看出，μ(xi)是無(wú)窮、連續(xù)可微的，c為類(lèi)中心，核密度倒數(shù)用k代表。當(dāng)數(shù)據(jù)距離數(shù)據(jù)中心距離較遠(yuǎn)時(shí)，隸屬度就會(huì)越小，越減小誤分類(lèi)的可能。這時(shí)本分類(lèi)方法的一個(gè)優(yōu)點(diǎn)。

其分類(lèi)的計(jì)算框架如圖3所示。

圖3 分類(lèi)識(shí)別的計(jì)算框架Fig.3 Algorithmic framework of classification and recognition

4 實(shí)際航跡數(shù)據(jù)的應(yīng)用分析

為研究本文所提出方法的有效性和實(shí)用性，做以下2個(gè)方面的驗(yàn)證：

1）驗(yàn)證是否可以用前面所述的平衡核函數(shù)方法來(lái)聚類(lèi)航跡數(shù)據(jù)集合以形成正確的航跡類(lèi)別；

2）在已經(jīng)獲得的類(lèi)別數(shù)據(jù)基礎(chǔ)上，用模糊支持向量機(jī)的方法來(lái)對(duì)不同飛行航跡進(jìn)行分類(lèi)，驗(yàn)證模糊支持向量機(jī)算法框架應(yīng)用的有效性。

以我國(guó)海南島北部的?？诿捞m機(jī)場(chǎng)為中心的附近區(qū)域的飛行器航跡數(shù)據(jù)為研究對(duì)象，只分析以美蘭機(jī)場(chǎng)為到達(dá)機(jī)場(chǎng)的國(guó)內(nèi)和國(guó)際航班的航路區(qū)域周?chē)拿裼煤娇掌鞯暮桔E數(shù)據(jù)，由于沿各種航路飛來(lái)的航班在進(jìn)近區(qū)航跡大致相似，為簡(jiǎn)化問(wèn)題，這里不考慮機(jī)場(chǎng)進(jìn)近區(qū)內(nèi)（這里按美蘭機(jī)場(chǎng)為中心50 km 的圓形范圍）的航跡變化，只考慮進(jìn)近區(qū)域之外的飛行航跡作為參與分析的數(shù)據(jù)。

此外，飛行器在實(shí)際的飛行過(guò)程中，受到天氣、飛行器本身、氣流等因素的影響，實(shí)際飛行航跡要復(fù)雜混亂得多。如果通過(guò)本文提出的聚類(lèi)方法可以應(yīng)用于飛行航跡類(lèi)別的識(shí)別，則為下一步未知類(lèi)別的航跡識(shí)別提供了思路。

在進(jìn)行平衡核函數(shù)聚類(lèi)算法的驗(yàn)證分析時(shí)，為說(shuō)明方法的有效性，除本文使用的方法之外，還和傳統(tǒng)的K-均值聚類(lèi)方法進(jìn)行對(duì)比。本文方法中的參數(shù)設(shè)置 分 別 為：L=2 ，ε=0.001 ，T=100 ，ξ=0.35 ，β=0.2，核函數(shù)選為高斯核函數(shù)。以美蘭機(jī)場(chǎng)為到達(dá)機(jī)場(chǎng)的2條航路，每條航路選擇60條10 min 內(nèi)每隔5 s給出的航跡點(diǎn)形成數(shù)據(jù)集，給出本文方法和傳統(tǒng)的K-均值聚類(lèi)方法在特征空間中的聚類(lèi)分布結(jié)果，圖4 是傳統(tǒng)的K-均值聚類(lèi)方法，圖5是本文方法。圖中橫縱坐標(biāo)的0 點(diǎn)為特征空間中的中心原點(diǎn)，橫坐標(biāo)為與某一類(lèi)數(shù)據(jù)中心與原點(diǎn)在特征空間的距離度量，縱坐標(biāo)的數(shù)字為與該類(lèi)數(shù)據(jù)中心的距離度量。

由圖4、5 可以得出看出，本文提出的方法是一種可行的方法。從聚類(lèi)性能上看，平衡核函數(shù)聚類(lèi)的算法聚類(lèi)結(jié)果更加緊密，更加集中，聚類(lèi)后的樣本數(shù)據(jù)分布只占到原有傳統(tǒng)K 均值聚類(lèi)的50%。本文提出的平衡核函數(shù)聚類(lèi)方法明顯優(yōu)于傳統(tǒng)的K-均值聚類(lèi)方法。可以判別出不同類(lèi)型航路的飛行航跡。

圖4 傳統(tǒng)K均值聚類(lèi)Fig.4 Traditional K-MEANS clustering

圖5 平衡核函數(shù)聚類(lèi)算法Fig.5 Balanced kernel function clustering algorithm

在聚類(lèi)獲得航路數(shù)據(jù)集基礎(chǔ)上，再使用不同類(lèi)別的飛行航跡數(shù)據(jù)，采用本文設(shè)計(jì)的模糊支持向量機(jī)進(jìn)行識(shí)別分類(lèi)，觀察分類(lèi)的準(zhǔn)確率。同樣，為了驗(yàn)證效果，調(diào)整使用不同的核密度函數(shù)帶寬和錯(cuò)分懲罰參數(shù)，與標(biāo)準(zhǔn)支持向量機(jī)分類(lèi)器的分類(lèi)結(jié)果進(jìn)行比較。

本文選取6條航路，每條航路作為一個(gè)類(lèi)別，在每條航路經(jīng)過(guò)的航跡中選擇280 條航跡，取10 min 內(nèi)每隔5 s 得出的航跡點(diǎn)形成數(shù)據(jù)集進(jìn)行聚類(lèi)，然后選擇這6 條航路上每一類(lèi)航路的其他70 條航跡進(jìn)行識(shí)別驗(yàn)證，如果能得到正確的分類(lèi)結(jié)果記為“1”，錯(cuò)誤記為“0”，用識(shí)別的正確率來(lái)表示識(shí)別率，根據(jù)正確率的定義：

其中：TP為實(shí)際為正例且被分類(lèi)器劃分為正例的實(shí)例數(shù)；TN為實(shí)際為負(fù)例且被分類(lèi)器劃分為負(fù)例的實(shí)例數(shù)；P為正例；N為負(fù)例。得到識(shí)別率：

重復(fù)進(jìn)行10次以上的步驟，得到的平均識(shí)別率如表1所示。

結(jié)果分析可以發(fā)現(xiàn)，本方法的識(shí)別效果要優(yōu)于標(biāo)準(zhǔn)SVM進(jìn)行分類(lèi)的結(jié)果，而且，通過(guò)改變不同的核密度函數(shù)帶寬和懲罰參數(shù)，對(duì)航跡數(shù)據(jù)識(shí)別的結(jié)果也會(huì)發(fā)生變化。

表1 航路數(shù)據(jù)在不同參數(shù)下的平均識(shí)別率Tab.1 Average recognition rate of track data under different parameters

5 結(jié)論

本文立足提高飛行航跡數(shù)據(jù)聚類(lèi)分析的準(zhǔn)確性，在航跡特征數(shù)據(jù)的預(yù)處理階段，使用一種平衡核函數(shù)用于K-均值聚類(lèi)，能有效提高交疊樣本的聚類(lèi)性能；設(shè)計(jì)了一種模糊支持向量機(jī)實(shí)現(xiàn)航跡數(shù)據(jù)的分類(lèi)。通過(guò)實(shí)際航跡數(shù)據(jù)測(cè)試了基于平衡核函數(shù)航跡聚類(lèi)和模糊支持向量機(jī)分類(lèi)器的有效性。下一步可以繼續(xù)研究不同的核密度函數(shù)帶寬和懲罰參數(shù)對(duì)識(shí)別結(jié)果的影響規(guī)律，可以提高飛行航跡數(shù)據(jù)的識(shí)別效果。