梁復(fù)臺，李宏權(quán)，孟慶文，蔡莉

(1.空軍預(yù)警學(xué)院 預(yù)警情報系，湖北 武漢 430019；2.中國人民解放軍31121部隊，江西 南昌 330000)

0 引言

為挖掘歷史航跡價值、揭示空中目標活動規(guī)律，可對航跡進行聚類，得出聚類簇中心航跡，然后將中心航跡作為參考與實時空情比對，以幫助雷達操作員準確判定空中目標屬性，輔助指揮員及時對空情作出決策。

傳統(tǒng)的航跡聚類方法主要有基于航跡點的聚類、基于部分特征相似子航跡的聚類及面向航跡整體的聚類[1]。這些航跡聚類算法的關(guān)鍵點有2處：一是相似度度量模型的構(gòu)建；二是高效聚類算法的設(shè)計[2]。其中，文獻[3]提出的航跡點逐點比對的航跡聚類方法，形成了一個航跡聚類框架。文獻[4]對文獻[3]的算法進行了改進，根據(jù)前后附近點最短距離來對航跡相似性度量，然后將聚類結(jié)果應(yīng)用于終端區(qū)的進場程序管制。文獻[5]提出基于最長公共子序列相似性度量的聚類算法，根據(jù)航跡轉(zhuǎn)折點進行聚類，得到的聚類結(jié)果用于異常航跡預(yù)測。文獻[6]采用最小描繪長度(minimun description length,MDL)理論劃分得出航跡關(guān)鍵點，對關(guān)鍵點聚類采用改進的模糊k-means算法。文獻[7]提出了基于軌跡聚類的軌跡整體運動趨勢提取方法，聚類部分采取了分割再聚類的思路實現(xiàn)。

但這些傳統(tǒng)方法均存在著較多不足，基于航跡點的聚類運算量大，耗時長，占用大量資源，且對交叉航線航跡點較難處理；基于部分相似子航跡聚類算法復(fù)雜；面向航跡整體的聚類不能太多地兼顧航跡細節(jié)特征。針這些不足，本文提出一種空中目標航跡聚類算法，首先對空中目標歷史航跡進行曲線擬合，將其由點跡映射為曲線，然后對于曲線的特征點及參量運用k-means算法進行聚類，明顯克服了上述算法缺陷。

1 航跡特征提取

對于數(shù)據(jù)挖掘而言，提取有效的特征是前提，如果提取的特征對事物沒有好的區(qū)分度，方法再好也無濟于事。能將事物很好地區(qū)分開的屬性特征就是有效的特征，其有弱、中、強之分。能否找到強特征，很大程度上決定著數(shù)據(jù)挖掘的效率高低甚至數(shù)據(jù)挖掘的成功與否。

數(shù)據(jù)挖掘輸入的是樣本屬性。傳統(tǒng)關(guān)于航跡的數(shù)據(jù)挖掘方法，樣本的屬性多選擇為移動對象航跡的點跡[3-4]，或者基于復(fù)雜運算得到的特征點[5-6]，聚類模型往往都是建立于其上，算法運算量大，影響挖掘速度，算法時效性不高。本文通過航跡擬合得到航跡特征點及對應(yīng)曲線參數(shù)，以此來表征目標活動規(guī)律的樣本屬性，帶來了一系列的優(yōu)勢。

航跡是由大量點跡組成的，由于目標的運動軌跡是連續(xù)變化的，在一段連續(xù)的航跡上，點跡變化平緩，航跡曲線光滑，因此可利用曲線對航跡進行擬合。通過擬合曲線參數(shù)來代替大量點跡來進行聚類，得到航跡的參數(shù)化特征，減少了樣本屬性數(shù)量，使得算法可以適用于大的樣本集。同時還使得運算可以分階段進行，在傳輸及存儲階段進行擬合運算，在聚類階段只對擬合參數(shù)聚類，優(yōu)化了存儲和運算資源，減小了數(shù)據(jù)傳輸壓力，提高了運算效率。

1.1 改進的航跡擬合算法

1.1.1 航跡擬合的基本方法

曲線擬合是指選擇適當?shù)那€類型來擬合觀測數(shù)據(jù)，并用擬合的曲線方程分析變量間的關(guān)系。常見的擬合函數(shù)有：指數(shù)函數(shù)、對數(shù)函數(shù)、冪函數(shù)，及多項式。對于空中目標航跡的擬合，考慮到多項式簡單易用，擬合計算速度快，擬合效果好，而成為空中目標航跡擬合的首選[8]。對大多數(shù)空中目標來說，為了得到較好的燃油經(jīng)濟性并追求最大航程，都會盡快爬升到一定高度采取水平勻速巡航(巡航飛行)，盡量避免改變速度和高度，故航跡信息中高度值的變化較小，在一個很長的時間間隔內(nèi)保留一個高度值即能反應(yīng)高度的變化[9]。因此，可在經(jīng)緯度構(gòu)成的二維平面上采取用三次多項式y(tǒng)=ax3+bx2+cx+d曲線進行擬合[10]，擬合方法采用最小二乘法。目標函數(shù)為使航跡擬合值與點航跡實際值離差平方和(或稱殘差平方和)最?。?/p>

(1)

1.1.2 最優(yōu)擬合區(qū)間的選擇

由于航跡軌跡復(fù)雜，用一條曲線難以描述其全部特征，故自適應(yīng)的擬合區(qū)間選擇成為問題的關(guān)鍵[11]，且擬合區(qū)間應(yīng)該精心選擇以達最優(yōu)效果，過長或過短都會弱化重要特征點的區(qū)分作用，導(dǎo)致聚類誤差加大，況且，過小還影響壓縮效果，占用存儲空間。擬合前，首先將原始航跡極坐標轉(zhuǎn)換為直角坐標。然后采用回溯法對巡航階段航跡選擇最優(yōu)擬合區(qū)間，回溯法的實現(xiàn)采用迭代逼近的方式：對于一段長度為L的航跡，假如誤差小于所設(shè)閾值，再向外延伸1/2距離，如果前后誤差相等，則終止循環(huán)并退出；如果誤差大于所設(shè)閾值，則從此判斷處往回縮減1/2距離，如此循環(huán)迭代，直至前后2次誤差相等，擬合誤差為

(2)

1.1.3 最優(yōu)擬合區(qū)間段航跡擬合

采用上述擬合方法得出整條航跡的全部自適應(yīng)擬合區(qū)間段，航跡段經(jīng)度值記為序列Xm=(xm1,xm2,xm3,…,xmnm)，航跡段緯度值記為序列Ym=(ym1,ym2,ym3,…,ymnm)，其中，m為段落數(shù)，nm為第m段航跡點跡數(shù)目。然后對所有擬合區(qū)間段航跡附加如下限制條件重新擬合。

為保持航跡的連續(xù)性，對于第1段航跡需要添加這樣的限制條件，即該段首尾點值與擬合值一致：

(3)

對后面的最優(yōu)擬合段(m≥2)擬合的過程中不但要考慮各段落之間的連續(xù)性，還需保證光滑性，即上一段的航跡末點為下一段的首點。

(4)

通過矩陣運算，將目標函數(shù)及其限制條件轉(zhuǎn)化為二次規(guī)劃問題[12]，通過在Python環(huán)境中調(diào)用函數(shù)計算，得到各段擬合曲線參數(shù)。擬合后的航跡信息用航跡擬合特征點與其所對應(yīng)擬合區(qū)間的擬合曲線參數(shù)來表示：[(經(jīng)度，緯度)，(a,b,c,d)]。

1.2 算法仿真實驗

按照上節(jié)所述思路，用python語言編程實現(xiàn)算法，然后對一條航跡采用該擬合算法進行仿真，得出航跡位置信息擬合前后效果對比示意圖。此段航跡共包含373點跡(圖1藍色點跡所示)，航跡地理位置信息變化明顯，比較真實地反映了各類空中目標航跡特征，具有一定的代表性。

圖1 固定劃分航跡擬合圖

文獻[8]的軌跡擬合算法對航跡段落進行了固定劃分，雖然一定程度上解決了擬合效果不好的問題，但在段落劃分較少時還是存在著與真實航跡偏差太大的問題，如果劃分過密，又達不到壓縮數(shù)據(jù)量的目的。圖1中分段數(shù)達到35，擬合曲線才較好地吻合原航跡。

圖2 自適應(yīng)的航跡擬合圖

對于自適應(yīng)的航跡擬合方法，在不附加限制條件的情況下，擬合誤差σ=0.000 01時，紅色圓圈表示擬合特征點，紅色曲線為與擬合特征點對應(yīng)的擬合曲線。從圖2可以看出，航跡在自適應(yīng)擬合段的連接處出現(xiàn)斷續(xù)，且每段之間連接不光滑，模擬真實航跡存在著一定的失真。

采用本文中所示方法，在擬合誤差σ=0.000 01時，自適應(yīng)航跡段數(shù)目為8，原始航跡曲線與擬合后的曲線吻合很好，連續(xù)性及光滑性都得到了很好的體現(xiàn)，見圖3。很好地保留了航跡信息特征，實現(xiàn)了航跡信息存儲與挖掘分析以及可視化各方性能的兼顧。

圖3 改進自適應(yīng)擬合航跡圖

2 基于k-means的航跡聚類

聚類是一種無監(jiān)督學(xué)習(xí)，將對象劃分為不同的簇，同一個簇中的對象“相似”，不同簇之間對象“互異”[13]。聚類方法有基于原型的方法、基于層次的方法、基于密度的方法、基于網(wǎng)格的方法和基于模型的方法。基于原型的聚類方法中，對象的相似性通常通過距離函數(shù)來度量，這個特點適用于對于航跡信息的聚類。基于原型的聚類方法常用的有k均值，k-means++是它的改進型，解決了k-means方法因初始中心選擇不當導(dǎo)致簇效果不佳或收斂慢的問題[14]。本文采用k-means++算法實現(xiàn)聚類，簡記為k-means算法。

2.1 航跡特征點聚類

k-means算法的基本思想是：首先從特征集中隨機選擇k個特征點作為初始簇中心；然后將n個數(shù)據(jù)對象劃分為k個簇以便使其距離滿足：同一簇中的對象相似度較高；不同簇間的對象相似度較小。k-means++在初始點的選擇上作了優(yōu)化。給定樣本集D={x1,x2,…,xm}，聚類所得簇C={c1,c2,…,ck}最小化平方誤差：

(5)

通常對“相似度度量”都是基于某種形式的距離來定義，距離大小與相似度大小成反比。最常用的距離是閔可夫斯基距離，對于給定樣本xi=(xi1，xi2，…，xin)與xj=(xj1，xj2，…，xjn),有

(6)

當p=2時閔可夫斯基距離就是歐式距離,當p=1時為曼哈頓距離[15]。在本文中，采用了歐式距離作為相似度的度量。

對整段航跡通過選取自適應(yīng)擬合段落，得到各段航跡特征點及擬合曲線系數(shù)，建立起關(guān)于整段航跡的新的特征集。對某空域中所有航跡擬合時選取統(tǒng)一的誤差閾值，得到的新的航跡特征集則能夠代表原航跡，解決了傳統(tǒng)以所有航跡點作為航跡特征來聚類，所帶來的運算量大、準確率不高的問題。對1.1節(jié)所述航跡采用自適應(yīng)航跡擬合算法，將原航跡373點跡壓縮為8個特征點，數(shù)據(jù)量減少了98%,除去擬合環(huán)節(jié)的開銷，在聚類環(huán)節(jié)，運算量相應(yīng)減少了98%，這在實時航跡匹配中可以提高運算速度。

k-means算法的缺點是必須事先指定先驗的簇數(shù)量[16]。對于航跡數(shù)據(jù)聚類中心數(shù)目的確定，可以事先根據(jù)擬合特征點的分布，經(jīng)可視化處理最終確定，也可以通過二分k-means或通過肘部法和輪廓系數(shù)圖對聚類效果進行評定，幫助選出最優(yōu)k值。本文采取肘部法評估、可視化輔助的方法選定最優(yōu)k值。

2.2 航跡曲線系數(shù)聚類

對最優(yōu)航跡擬合段特征點進行聚類，還存在準確率不高的問題，在此基礎(chǔ)上，結(jié)合航跡最優(yōu)擬合段曲線系數(shù)聚類，可以形成印證互補，提高正確率。

多項式系數(shù)決定著多項式曲線的形狀，從系數(shù)上能夠區(qū)分擬合曲線所表示的航跡?？蓪τ谌味囗検綌M合所產(chǎn)生的4個系數(shù)，較難在其上確定“序”的關(guān)系，屬于無序?qū)傩?，不能直接用閔可夫斯基距離來度量[17]。

對本文中航跡擬合所采取的三次多項式求導(dǎo)可得y′=3ax2+2bx+c，取Δ=4b2-12ac，Δ=0是其是否單調(diào)的臨界點，再通過a值的大小，完全可以確定目標航跡的運動特征。通過觀察三次函數(shù)圖像(如圖4所示)，不難發(fā)現(xiàn)a與Δ決定著曲線的形狀及性質(zhì)。a的大小決定函數(shù)曲線遞增與遞減性，Δ的大小決定著函數(shù)曲線的單調(diào)性。故本文中將系數(shù)(a,b,c,d)轉(zhuǎn)化為(a,Δ)2個屬性來表述擬合航跡段。

圖4 三次函數(shù)圖像及性質(zhì)

在實際的聚類操作中，這2類屬性具有不同的量綱，這樣會影響到航跡聚類的結(jié)果，為了消除屬性之間的量綱影響，需要進行屬性數(shù)據(jù)歸一化處理，以使航跡之間具有可比性。本文采用min-max normalization的歸一化方法，特征量化的公式為

(7)

考慮到現(xiàn)實中曲線的遞增與遞減較明顯地表示了航跡的走向，而單調(diào)性對航跡的區(qū)分沒有太大的影響，這里采用加權(quán)的閔可夫斯基距離來進行相似度度量：

(8)

根據(jù)多次的嘗試，式(8)中的權(quán)值確定為w1=0.7,w2=0.3較合適。

2.3 實驗分析

2.3.1 航跡特征點聚類效果

(1) 誤差閾值的影響

模擬某空域一段時間航跡軌跡數(shù)據(jù)，有3類23條航跡，共4 051點跡，在對其運用自適應(yīng)擬合方法后，得到航跡特征點集，對其采用k-means方法聚類后效果如下：

誤差閾值取0.000 01時，得到共141個航跡擬合特征點，雖然能夠很精細地體現(xiàn)航跡特點，但對于航跡聚類來說，聚類的效果不理想，只有一類5條航跡完整地分辨了出來，見圖5。誤差閾值取0.000 1時，得到共58個航跡擬合特征點，擬合精細度較上次有所降低，聚類的效果有提高，但還是不夠完美,將一類折返航跡分成了2類航跡，如圖6所示。

誤差閾值取0.001時，得到共33個航跡擬合特征點，由圖7可以看出，聚類結(jié)果將3類航跡完全區(qū)分了出來。由此看來，誤差閾值的取值與擬合精細度成反比，與聚類效果成正比，在不是航跡重現(xiàn)的場合，可以放寬閾值的設(shè)置來達到更好的聚類效果。

(2) 最優(yōu)簇數(shù)目k值的確定

按照肘部法的思路，先用航跡總數(shù)作為k值代入聚類，逐次遞減，監(jiān)控在該過程中所有樣本點到其所屬類簇距離的平方和，在該值明顯出現(xiàn)肘部時所對應(yīng)的k值即為最優(yōu)簇數(shù)。

圖5 誤差閾值取0.000 01時

圖6 誤差閾值取0.000 1時

圖7 誤差閾值取0.001時

由圖8可看出，對2.2節(jié)所述空域航跡聚類，k值最后確定為3，這個和現(xiàn)實中的航跡類別數(shù)目相吻合(參見圖7)。

圖8 肘部法確定最優(yōu)簇數(shù)目k值

2.3.2 航跡曲線參數(shù)聚類效果

對于交叉的航跡，對于航跡點采用聚類方法包括k-means、DBSACND(基于密度的聚類算法)都無能為力。從2.3.1節(jié)實驗可以看出，在擬合誤差閾值取較小時，擬合特征點跡數(shù)量較多，存在不同航跡特征點同在一個簇中，但特征點對應(yīng)的航跡曲線不屬于同一類型的情況，即存在航跡交叉現(xiàn)象，此時難以有效區(qū)分航跡，聚類效果不好。在對自適應(yīng)擬合段特征點聚類的同時，結(jié)合擬合段曲線參數(shù)聚類，可以提高聚類航跡聚類效果。經(jīng)實驗，在結(jié)合特征點曲線系數(shù)聚類后，對航跡的聚類性能提升明顯，誤差閾值取0.000 1時，仍然可以實現(xiàn)航跡正確聚類。

3 結(jié)束語

針對傳統(tǒng)航跡聚類算法計算量大、實時性差等問題，本文首先提出了自適應(yīng)的航跡擬合算法，從原始航跡中提取少量特征點及對應(yīng)的擬合曲線，然后采用k-means方法對特征點進行聚類，從而實現(xiàn)了航跡的聚類區(qū)分。通過實驗仿真可以看到，選取合適的誤差閾值可以實現(xiàn)大量航跡的有效聚類，可以將不同運動特征的航跡區(qū)分開來。在運用到真實航跡聚類時，為使得算法效果更好，可結(jié)合航跡信息所表征的空中目標運動屬性，如飛行高度、速度、加速度、爬升率等，以更精準地實現(xiàn)空中目標航跡聚類。