朱瑜亮

(中國電科集團第十研究所，四川 成都 610036)

0 引言

航跡聚類是航跡數(shù)據(jù)分析中的一個重點，通過對記錄或?qū)崟r的航跡數(shù)據(jù)的聚類分析，可以獲得不同空中目標(biāo)的飛行路徑、飛行范圍、飛行特征等信息，幫助指揮人員了解空中目標(biāo)態(tài)勢，對空情進行指揮或事后研究分析。

以往傳統(tǒng)航跡聚類方法，有可以對空間中K 個點為中心進行聚類，對最靠近中心點的對象歸類，并迭代中心點位置的K-means 算法。K-means 算法可對圓形或球狀的聚類數(shù)據(jù)進行處理，但無法處理任意形狀的數(shù)據(jù)簇聚類，且需要事先人工設(shè)置聚類類別數(shù)K，聚類結(jié)果也受起始中心點設(shè)置的影響。

也有基于網(wǎng)格的移動對象處理算法，將時空域劃分為網(wǎng)格，把航跡數(shù)據(jù)點劃分到不同網(wǎng)格內(nèi)可解決航跡點本身的定位誤差，再將鄰域密度高于門限的網(wǎng)格連接成簇進行聚類。但對密度不均勻、密度差異大的數(shù)據(jù)集聚類效果不好，門限參數(shù)不好選取，且不能處理空域數(shù)據(jù)的聚類。

還有基于空間密度的聚類算法DBSCAN，通過統(tǒng)計點跡數(shù)據(jù)集內(nèi)任意點鄰域內(nèi)鄰近點的數(shù)量，不斷向鄰域擴張聚合為簇，直到遍歷所有點完成聚類。同樣可發(fā)現(xiàn)任意形狀的數(shù)據(jù)聚類，但對密度不均勻、密度差異大的數(shù)據(jù)集聚類效果不好，且不能處理時空域數(shù)據(jù)的聚類。

本文使用基于ST DBSCAN 的航跡聚類，既符合DBSCAN 聚類算法的特點和優(yōu)點又增加了從時間域?qū)δ繕?biāo)數(shù)據(jù)集的掃描。

1 ST DBSCAN 算法

ST DBSCAN 算法的航跡提取實現(xiàn)是在時間域和空間域上對目標(biāo)點跡進行掃描，以目標(biāo)航跡點的密度為依據(jù)進行聚類。通過此種聚類方式可對任意形狀的飛行航跡進行聚類。

1.1 DBSCAN 算法

(1)把所有數(shù)據(jù)集D 的數(shù)據(jù)點都標(biāo)記為無分類標(biāo)簽點；

(2)從任意無標(biāo)簽點開始選取某點p 為掃描的核心點，以核心點p 為圓心，距離鄰域Eps 為半徑的圓區(qū)域Eps(p)為掃描鄰域，掃描滿足鄰近距離門限的鄰域點數(shù)量；

(3)如果該核心點的鄰域點數(shù)量小于設(shè)定閾值MinPts，則標(biāo)記該點為噪聲點；

(4)如果鄰域點數(shù)量大于等于設(shè)定閾值MinPts，則標(biāo)記該點p 為核心點，產(chǎn)生聚類編號為簇C1，并將p 在鄰域Eps(p)內(nèi)的點都加入待掃描的簇C1 中；

(5)對簇C1 內(nèi)的尚未被標(biāo)記的點重復(fù)步驟(2)～步驟(4)的過程，直到簇C1 內(nèi)的點全部被標(biāo)記處理；

(6)繼續(xù)從數(shù)據(jù)集D 內(nèi)選取其他未標(biāo)記過的點，重復(fù)步驟(2)～步驟(5)的過程，聚類為另一個新類簇C2、C3等，直到D 內(nèi)沒有未標(biāo)記過的點。

1.2 ST DBSCAN 算法的改進

ST DBSCAN 算法的改進在于將DBSCAN 算法中的第(2)步加入了對掃描鄰域的時間連續(xù)性約束，從而可以從時間域維度提高飛機航跡聚類的準(zhǔn)確性。具體方法如下：

(1)把所有飛行航跡數(shù)據(jù)集D 的數(shù)據(jù)點都標(biāo)記為無分類標(biāo)簽點；

(2)從任意無標(biāo)簽點開始選取某點p 為掃描的核心點，核心點p 時間鄰域ΔT 內(nèi)為掃描鄰域，掃描時間鄰域ΔT 內(nèi)滿足以核心點p 為圓心，距離鄰域Eps 為半徑的圓球區(qū)域Eps(p)中滿足距離門限的鄰域點數(shù)量；

(3)如果該核心點的鄰域點數(shù)量小于設(shè)定閾值MinPts，則標(biāo)記該點為噪聲點；

(4)如果鄰域點數(shù)量大于等于設(shè)定閾值MinPts，則標(biāo)記該點p 為核心點，產(chǎn)生聚類編號為簇C1，并將p 在鄰域Eps(p)內(nèi)的點都加入待掃描的簇C1 中；

(5)對簇C1 內(nèi)的尚未被標(biāo)記的點，重復(fù)步驟(2)～步驟(4)的過程，直到簇C1 內(nèi)的點全部被標(biāo)記處理；

(6)繼續(xù)從數(shù)據(jù)集D 內(nèi)選取未標(biāo)記過的點，重復(fù)步驟(2)～步驟(5)的過程，聚類為另一個類，直到D 內(nèi)沒有未標(biāo)記過的點。

1.3 參數(shù)選取

1.3.1 Eps 值的選取

Eps 的值可通過計算排序K 最近鄰距離值獲得。

一般情況下，數(shù)據(jù)集中的噪音點與可聚類數(shù)據(jù)應(yīng)該有較大的密度差異才能對不同點跡區(qū)分聚類，在K 最近鄰距離的排序中K 最近鄰距離的值越小說明點跡密度越大，反之說明點跡密度越小。在本文中數(shù)據(jù)集中，當(dāng)K 最近鄰距離值出現(xiàn)由小到大的明顯突變點時，說明點跡的密度從較大的有效航跡區(qū)域進入到了密度較小的噪音區(qū)域，表明存在一個閾值點可以將數(shù)據(jù)集的點區(qū)分開來。具體的計算方法如下：

(1)K 最近鄰距離方法是指對數(shù)據(jù)集D={p(i)；i=0，1，…，n}內(nèi)的點，計算出點p(i)到數(shù)據(jù)集D 內(nèi)其他每個點的距離；

(2)對距離由小到大排序后得到集合Distance={d(1)，d(2)，…，d(k)，…，d(n)}，其中順次為k 的距離d(k)就是p(i)的K 最近鄰距離；

(3)計算D 中所有點的K 最近鄰距離的集合E={e(1)，e(2)，…，e(n)}，對E 中所有距離求均值e′，并計算出各種K 值下e′變化的值，觀察變化值最急劇的部分，對應(yīng)的e′值即為Eps 半徑。

1.3.2 MinPts 的取值

MinPts 用來控制聚類簇中點跡的最小數(shù)目，可根據(jù)聚類簇中點跡的最小可能數(shù)進行設(shè)置，保證一定有點跡可以完成聚類。

1.3.3 △T 的取值

ΔT 用來控制聚類簇中點跡的最小鄰近時間，可根據(jù)點跡數(shù)據(jù)中的最小時間間隔進行設(shè)置，保證一定有點跡可以完成聚類。

2 仿真實現(xiàn)

2.1 生成航跡數(shù)據(jù)

(1)在STK 9 中建立場景產(chǎn)生3 條飛機的航跡；

(2)3 條航跡數(shù)據(jù)分別導(dǎo)出后使用Python 對數(shù)據(jù)預(yù)處理；

(3)提取3 個航跡文件中的時間以及經(jīng)緯高數(shù)據(jù)、添加列名到dataframe 中；

(4)在航跡文件中添加隨機噪音數(shù)據(jù)；

(5)為不同航跡、噪聲數(shù)據(jù)預(yù)先打上標(biāo)簽，用于聚類后的結(jié)果評估。

組合以上4 組數(shù)據(jù)并保存為測試數(shù)據(jù)集。

2.2 航跡數(shù)據(jù)特征

數(shù)據(jù)中包含了航跡數(shù)據(jù)和設(shè)置的噪聲數(shù)據(jù)信息(其中經(jīng)緯高信息使用WGS-84 直角坐標(biāo)系數(shù)值)，并為不同航跡、噪聲數(shù)據(jù)預(yù)先打上了標(biāo)簽：航跡1、航跡2、航跡3、噪聲，用于聚類后的結(jié)果評估，具體如表1 所示。

表1 航跡數(shù)據(jù)內(nèi)容

(1)航跡1 與航跡2 在時域的起止點、時間間隔相同，空間域路徑無交集；

(2)航跡2 與航跡3 在時間域的起止點不同、時間間隔相同，空間域路徑有交集；

(3)航跡1 與航跡3 在時間域的起止點不同、時間間隔相同，空間域路徑無交集。

2.3 聚類參數(shù)選取

(1)Eps 的取值

根據(jù)K 最近鄰距離方法，對數(shù)據(jù)集中航跡點跡的K=2～24 取值時的K 最近鄰距離進行順序排序，可見在K值在3→4、5→6、7→8處的歐式距離值的跳變值都較大，因此以K=3、5、7 時的取值作為Eps 值，分別為5.522、11.251、17.191，具體如表2 所示。

表2 K 最近鄰距離

(2)MinPts 的取值

根據(jù)聚類簇中點跡的最小可能數(shù)設(shè)置為2。

(3)ΔT 的取值

根據(jù)點跡數(shù)據(jù)中的時間間隔設(shè)置為能包含2 個點跡的時間值0.04 s。

2.4 聚類結(jié)果

2.4.1 原始航跡數(shù)據(jù)

原始的航跡測試數(shù)據(jù)的三維圖中所有的點跡未聚類前的視圖，如圖1 所示。

圖1 原始的航跡測試數(shù)據(jù)3 維視圖

2.4.2 聚類后數(shù)據(jù)

當(dāng)選取Eps 值為5.522、11.251、17.191，MinPts 值為2，ΔT 值為0.04 s 時，分別進行聚類處理。得到的聚類結(jié)果如圖2～圖4 所示。

如圖2 所示，當(dāng)取Eps 值為5.522，MinPts 值為2，ΔT值為0.04 s 時，整個航跡點數(shù)據(jù)集被聚類為了5 類(包括4 類航跡和1 類噪聲)，所有點跡的聚類正確率為89.17%。

圖2 Eps 值為5.522 時的聚類結(jié)果

如圖3 所示，當(dāng)取Eps 值為11.251，MinPts 值為2，ΔT 值為0.04 s 時，整個航跡點數(shù)據(jù)集被聚類為了4 類(包括3 類航跡和1 類噪聲)，所有點跡的聚類正確率為100%。

圖3 Eps 值為11.251 時的聚類結(jié)果

如圖4 所示，當(dāng)取Eps 值為17.191，MinPts 值為2，ΔT 值為0.04 s 時，整個航跡點數(shù)據(jù)集被聚類為了4 類(包括3 類航跡和1 類噪聲)，所有點跡的聚類正確率為100%。

圖4 Eps 值為17.191 時的聚類結(jié)果

2.4.3聚類結(jié)果與分析

根據(jù)取Eps 值為5.522、11.251、17.191，MinPts 值為2，ΔT 值為0.04 s 時的3 組參數(shù)的聚類效果分析可知，當(dāng)以距離鄰域Eps=5.522 為半徑的圓球區(qū)域進行掃描時，所有點跡的聚類正確率為89.17%，其中第一類航跡點中有4 484 個由于兩點間歐式距離均超過了5.523 因此被聚類為了噪聲點，第二類航跡點中有69 個由于兩點間歐式距離均超過了5.653 因此被聚類為了噪聲點，其余點均聚類正確。

而當(dāng)以距離鄰域Eps=11.251、17.191 進行聚類時，以上航跡中的點均包含在了相應(yīng)分類的核心點鄰域從Eps 為半徑的圓球區(qū)域內(nèi)，因此都被正確地聚類，聚類正確率為100%。

3 結(jié)論

本文使用一種基于DBSCAN 算法的ST DBSCAN 算法進行了航跡聚類實現(xiàn)，ST DBSCAN 算法既符合DBSCAN 的特點和優(yōu)點又增加了從時間域?qū)δ繕?biāo)數(shù)據(jù)集的掃描?？蓪θ我庑螤畹暮桔E聚類，且不需提前劃分聚類目標(biāo)個數(shù)，并增加了對包含時空域航跡數(shù)據(jù)的聚類。通過增加對掃描鄰域的時間連續(xù)性約束，從而從時間域維度提高了飛機航跡聚類的準(zhǔn)確性。通過本文的仿真實現(xiàn)情況，在參數(shù)選擇合適的條件下可以獲得很好的聚類結(jié)果。但本方法也有和DBSCAN 相同的不足之處，即對時空間域上密度不均勻、密度差異大的點跡數(shù)據(jù)集的聚類效果不穩(wěn)定，且聚類效果依賴對參數(shù)的選擇等。在未來的工作中可以對此方法進行進一步的優(yōu)化和完善。