基于ST DBSCAN 的航跡聚類實(shí)現(xiàn)

朱瑜亮

(中國(guó)電科集團(tuán)第十研究所，四川 成都 610036)

0 引言

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

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

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

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

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

1 ST DBSCAN 算法

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

1.1 DBSCAN 算法

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

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

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

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

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

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

1.2 ST DBSCAN 算法的改進(jìn)

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

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

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

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

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

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

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

1.3 參數(shù)選取

1.3.1 Eps 值的選取

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

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

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

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

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

1.3.2 MinPts 的取值

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

1.3.3 △T 的取值

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

2 仿真實(shí)現(xiàn)

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

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

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

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

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

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

組合以上4 組數(shù)據(jù)并保存為測(cè)試數(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é)果評(píng)估，具體如表1 所示。

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

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

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

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

2.3 聚類參數(shù)選取

(1)Eps 的取值

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

表2 K 最近鄰距離

(2)MinPts 的取值

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

(3)ΔT 的取值

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

2.4 聚類結(jié)果

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)論

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