基于網(wǎng)格密度峰值聚類的實時雷達分選系統(tǒng)

顧軍華 田 喆 蘇 鳴 張亞娟

(河北工業(yè)大學人工智能與數(shù)據(jù)科學學院 天津 300401)(河北省大數(shù)據(jù)計算重點實驗室 天津 300401)

0 引 言

雷達分選是雷達信號處理中的重要一環(huán)，只有從交疊的雷達數(shù)據(jù)中分解出每個雷達的數(shù)據(jù)，才能對雷達數(shù)據(jù)進行準確分析，因此雷達分選的準確性直接影響了雷達的性能。隨著雷達的廣泛應(yīng)用，雷達所處的電磁環(huán)境日益復雜[1]，單純依靠脈沖重復周期(PRI)的分選系統(tǒng)已經(jīng)無法滿足人們對雷達分選準確度的需求。近年來，有學者提出基于聚類的雷達分選系統(tǒng)[2]，這類方法無須先驗信息，可以處理嚴重重疊的雷達數(shù)據(jù)。針對雷達分選系統(tǒng)的實時性要求，實際應(yīng)用中常采用數(shù)據(jù)流聚類算法進行分選。

CluStream算法是最早出現(xiàn)的數(shù)據(jù)流聚類算法，該算法包含在線和離線兩個階段，這種高效的框架成為了數(shù)據(jù)流聚類的主流框架。CluStream算法存在只能發(fā)掘球狀類、不能識別噪聲點等問題，為了解決上述問題，提出基于網(wǎng)格的數(shù)據(jù)流聚類算法(D-Stream算法)，該算法通過將數(shù)據(jù)點映射到網(wǎng)格，提升了算法效率。此后，出現(xiàn)了大量對D-Stream算法的改進[3]，其中ExCC算法[4]按照每個維度的特性分配各個維度的粒度來劃分網(wǎng)格，并且在線階段考慮了數(shù)據(jù)流流速，具有很好的效率。但是上述基于網(wǎng)格的數(shù)據(jù)流聚類算法，存在著容易丟失聚類的邊界和容易將距離較近類合并的問題。

針對上述兩個問題，本文提出了基于網(wǎng)格密度峰值的數(shù)據(jù)流聚類算法(GDP-Stream)。該算法首先于在線階段采用一種新的雙重網(wǎng)格劃分方式來建立概要數(shù)據(jù)結(jié)構(gòu)，極大地減少了聚類邊界丟失的概率。其次，鑒于密度峰聚類算法(DPC)[5]可以很好地區(qū)分距離較近的類，因此本文算法通過在離線階段融入改進的DPC算法，來避免傳統(tǒng)網(wǎng)格合并方法容易將距離較近的類合并的問題。為了證明GDP-Stream算法可以有效地進行雷達分選，本文將GDP-Stream算法、ExCC算法和DP-Stream算法[6]在仿真雷達數(shù)據(jù)集上進行對比實驗。其中，DP-Stream算法是一種基于DPC的數(shù)據(jù)流聚類算法。結(jié)果表明，GDP-Stream算法相比于ExCC算法和DP-Stream算法有著更高的準確度和抗干擾能力。

1 GDP-Stream算法

GDP-Stream算法的框架如圖1所示。

圖1 GDP-Stream算法框架圖

在線階段，不斷接收數(shù)據(jù)流，采用雙重網(wǎng)格劃分生成并維護概要數(shù)據(jù)結(jié)構(gòu)。當收到用戶發(fā)來的聚類請求時，算法進入離線階段，執(zhí)行基于改進DPC算法的網(wǎng)格合并，生成聚類結(jié)果。

1.1 在線階段

數(shù)據(jù)流樣本集X={X1,X2，…，Xn}是由n個有d維屬性的數(shù)據(jù)樣本點Xi={Xi1,Xi2，…，Xij，…Xid}組成的，Xij為X中第i個樣本點的第j維屬性。數(shù)據(jù)空間的上界M={M1,M2，…，Md}，下界m={m1,m2，…，md}，其中Mi=max(X1i,X2i，…，Xni)，mi=min(X1i,X2i，…，Xni)。

定義1(靜態(tài)網(wǎng)格) 由數(shù)據(jù)空間對每一維k等分得到。網(wǎng)格邊長l={l1,l2，…，ld}。靜態(tài)網(wǎng)格Gi的密度DGi為靜態(tài)網(wǎng)格中包含的數(shù)據(jù)點數(shù)量。當靜態(tài)網(wǎng)格密度大于用戶設(shè)置的密度閾值DT時，稱該靜態(tài)網(wǎng)格為高密度靜態(tài)網(wǎng)格，否則稱低密度靜態(tài)網(wǎng)格。

定義2(數(shù)據(jù)樣本點之間的距離) PDW中不同屬性的量綱差別很大[7]，為避免影響聚類準確性，本文對歐式距離進行min-max歸一化改進，數(shù)據(jù)樣本點Xi和Xj的距離如下所示：

(1)

傳統(tǒng)網(wǎng)格聚類算法多采用靜態(tài)網(wǎng)格劃分。網(wǎng)格數(shù)量隨數(shù)據(jù)維數(shù)增長而激增，降低了算法的效率。并且這種劃分直接丟棄低密度網(wǎng)格中的點，容易丟失聚類的邊界。本文基于文獻[2]進行改進，提出雙重網(wǎng)格劃分，該方法有效濾除了噪聲點，并在下文的網(wǎng)格合并過程中只對動態(tài)網(wǎng)格進行操作，由于動態(tài)網(wǎng)格數(shù)量不隨維度一起增長，提高了效率。

定義3(動態(tài)網(wǎng)格) 以Xi點為網(wǎng)格中心，定義1中的網(wǎng)格邊長l為邊長創(chuàng)建的網(wǎng)格稱為動態(tài)網(wǎng)格。以Xi點為中心的動態(tài)網(wǎng)格的密度DXi為動態(tài)網(wǎng)格中數(shù)據(jù)點的個數(shù)。

當有數(shù)據(jù)點屬于兩個動態(tài)網(wǎng)格，則稱這兩個動態(tài)網(wǎng)格相交。如圖2所示，求一個動態(tài)網(wǎng)格的相交動態(tài)網(wǎng)格時，只需搜索與該動態(tài)網(wǎng)格中心點所在靜態(tài)網(wǎng)格相鄰的靜態(tài)網(wǎng)格即可。

圖2 相交動態(tài)網(wǎng)格

對數(shù)據(jù)流X={X1,X2,…,Xn}執(zhí)行雙重網(wǎng)格劃分，生成并維護概要數(shù)據(jù)結(jié)構(gòu)的具體步驟如下：

(1) 設(shè)置參數(shù)：噪聲過濾閾值DT、靜態(tài)網(wǎng)格劃分份數(shù)k、數(shù)據(jù)點最大數(shù)量max_X。

(2) 積累一定的數(shù)據(jù)點，計算X的上界M和下界m，根據(jù)靜態(tài)網(wǎng)格劃分份數(shù)k，計算網(wǎng)格邊長l。

(3) 進行靜態(tài)網(wǎng)格劃分，將數(shù)據(jù)空間k等分。

(4) 從數(shù)據(jù)流X接收一點Xi，存入X_list。

(5) 若X_list中數(shù)據(jù)點總量達到max_X，則刪除最早到達的數(shù)據(jù)點，如果該數(shù)據(jù)點所處的靜態(tài)網(wǎng)格退化為低密度靜態(tài)網(wǎng)格，則刪除該靜態(tài)網(wǎng)格中包含的動態(tài)網(wǎng)格。

(6) 求Xi所屬靜態(tài)網(wǎng)格Gi，更新DGj。

(7) 如果DGj由低密度靜態(tài)網(wǎng)格轉(zhuǎn)變?yōu)楦呙芏褥o態(tài)網(wǎng)格，則執(zhí)行(8)，否則執(zhí)行(10)。

(8) 對Gj中每一個數(shù)據(jù)點，判斷該點能否落入某個已存在的動態(tài)網(wǎng)格中。若能，則將該點存入該動態(tài)網(wǎng)格中；若不能，則以該點為中心，根據(jù)網(wǎng)格邊長創(chuàng)建一個新的動態(tài)網(wǎng)格。

(9) 判斷與Gj相鄰的低密度靜態(tài)網(wǎng)格中的每個點能否落入(8)中新創(chuàng)建的動態(tài)網(wǎng)格，若能則存入。

(10) 若X中有數(shù)據(jù)點未處理，則執(zhí)行(4)，否則在線階段結(jié)束。在線階段，得到一組靜態(tài)網(wǎng)格和動態(tài)網(wǎng)格，作為概要數(shù)據(jù)結(jié)構(gòu)。

如圖3所示，雙重網(wǎng)格劃分可以很好地處理靜態(tài)網(wǎng)格劃分存在的聚類邊界丟失問題。

圖3 網(wǎng)格劃分對比

1.2 離線階段

離線階段對在線階段生成的概要數(shù)據(jù)結(jié)構(gòu)(靜態(tài)網(wǎng)格和動態(tài)網(wǎng)格)執(zhí)行網(wǎng)格合并。

按照傳統(tǒng)的網(wǎng)格合并思路，直接合并相交的動態(tài)網(wǎng)格，可以高效地處理復雜形狀類，如圖4所示。

圖4 傳統(tǒng)網(wǎng)格合并

但是這種合并方式只考慮了局部信息，缺乏對數(shù)據(jù)空間的整體考量，如果兩個類距離較近，很可能被合并為一類，如圖5所示。

文獻[5]提出DPC算法，該算法的思想是首先求出密度峰作為聚類中心，密度峰為本身局部密度大并且與其他局部密度更大數(shù)據(jù)點的距離較大的點；然后將其他數(shù)據(jù)點歸類到相應(yīng)的密度峰。DPC算法對聚類中心的挖掘，考慮了數(shù)據(jù)空間的整體特性，可以很好地區(qū)分距離較近的類[8-10]。參考DPC算法中密度峰的定義，密度峰動態(tài)網(wǎng)格的定義如下：

定義4(密度峰動態(tài)網(wǎng)格) 當動態(tài)網(wǎng)格擁有較高密度，且與其他密度更大的動態(tài)網(wǎng)格之間的距離較大，稱其為密度峰動態(tài)網(wǎng)格。本算法采用文獻[11]中的密度峰指標ZXi如下：

(2)

式中：dmXi為以Xi為中心的動態(tài)網(wǎng)格與更高密度動態(tài)網(wǎng)格之間的最小距離：

ZXi=DXi×dmXi

(3)

首先計算所有動態(tài)網(wǎng)格的ZXi，排除ZXi最大的動態(tài)網(wǎng)格，對于剩下動態(tài)網(wǎng)格排序后的序列為Z={Z1,Z2，…，Zm}，其中m為ZXi值不為最大值的點的動態(tài)網(wǎng)格數(shù)量。

I=argmaxi((Zi-1-Zi)-(Zi-Zi+1))

(4)

稱{Z1,Z2，…，ZI}所對應(yīng)的動態(tài)網(wǎng)格為密度峰動態(tài)網(wǎng)格。

但是DPC算法有著效率低的缺點，并且容易把復雜形狀的類劃分為多個類。不能將DPC算法中的方法直接用于本文對動態(tài)網(wǎng)格的合并，因此本文對DPC算法思想提出如下改進。

改進1：降低挖掘密度峰動態(tài)網(wǎng)格的時間消耗。

定義5(密度極大動態(tài)網(wǎng)格) 當動態(tài)網(wǎng)格密度不小于它的任意一個相交動態(tài)網(wǎng)格密度，且大于所有動態(tài)網(wǎng)格平均密度，稱該動態(tài)網(wǎng)格為密度極大動態(tài)網(wǎng)格。

密度極大動態(tài)網(wǎng)格的ZXi較大，密度峰動態(tài)網(wǎng)格大多存在于密度極大動態(tài)網(wǎng)格中。求得密度峰動態(tài)網(wǎng)格的時間復雜度為O(m2)。為了提高效率，本算法首先用O(m)的復雜度求得密度極大動態(tài)網(wǎng)格，再從所有密度極大動態(tài)網(wǎng)格中求得密度峰動態(tài)網(wǎng)格。

改進2：降低非密度峰動態(tài)網(wǎng)格歸類時間消耗。

定義6(動態(tài)網(wǎng)格集) 對于以Xi點為中心的密度峰動態(tài)網(wǎng)格，稱以它為基礎(chǔ)歸類得到的動態(tài)網(wǎng)格集為CXi。

如果按照DPC算法中思想進行歸類，對于每個非密度峰動態(tài)網(wǎng)格，將它按密度降序的順序歸類到密度大于它且距離最近的動態(tài)網(wǎng)格所屬的類中，得到動態(tài)網(wǎng)格集。

本算法改進的歸類方法如下：首先將所有動態(tài)網(wǎng)格按密度降序排序，之后按順序進行歸類。對于非密度極大動態(tài)網(wǎng)格，因為一定存在密度大于它的動態(tài)網(wǎng)格與它相交，相交的動態(tài)網(wǎng)格之間的距離一定小于不相交的，所以只需搜索與它相交的動態(tài)網(wǎng)格，從中找到密度大于它且距離最近的動態(tài)網(wǎng)格，即為所求。上文中提到，求相交動態(tài)網(wǎng)格相比于求距離最近動態(tài)網(wǎng)格只需要很少的時間，所以歸類的效率得到了很大的提高。對于密度極大動態(tài)網(wǎng)格，無法快速求解，因此按照DPC算法的方法求解。但是由于密度極大動態(tài)網(wǎng)格數(shù)量較少，所以時間損耗不大。

改進3：避免復雜形狀類被劃分為多個類。

復雜形狀的類會存在多個密度峰，DPC算法會把非密度峰點歸類到密度峰所屬的類，所以容易導致復雜形狀的類被錯誤的劃分為多個類[8]。

為解決該問題，本文引入了相似度。通過觀察發(fā)現(xiàn)，同一個類中的動態(tài)網(wǎng)格應(yīng)該具有相似的密度；若相鄰動態(tài)網(wǎng)格集屬于同一類，則它們之間相交動態(tài)網(wǎng)格的平均密度不會與它們兩個的平均密度差距很大。則相似度定義如下：

定義7(相似度) 動態(tài)網(wǎng)格集CXi和CXj之間的相似度為：

(5)

(6)

式中：d(CXi)為CXi中動態(tài)網(wǎng)格的平均密度。式(5)為相對密度差，當sim(CXi,CXj)超過一定閾值SIMT后判定兩個動態(tài)網(wǎng)格集相似，合并CXi和CXj。

基于改進DPC算法的網(wǎng)格合并的步驟如下：

(1) 設(shè)置相似度閾值SIMT。

(2) 將所有動態(tài)網(wǎng)格，按照密度從大到小排序。

(3) 找到所有密度極大動態(tài)網(wǎng)格。

(4) 從密度極大動態(tài)網(wǎng)格中找到密度峰動態(tài)網(wǎng)格。

(5) 對所有非密度峰動態(tài)網(wǎng)格進行歸類，生成一組動態(tài)網(wǎng)格集。

(6) 對于每兩個相交動態(tài)網(wǎng)格集CXi和CXj，當sim(CXi,CXj)≥SIMT時，合并CXi和CXj。

(7) 將動態(tài)網(wǎng)格聚類結(jié)果，映射到數(shù)據(jù)點。當數(shù)據(jù)點屬于多個不同類動態(tài)網(wǎng)格時，將其歸屬于距離最近的動態(tài)網(wǎng)格所屬的類。

2 仿真實驗分析

2.1 雷達信號仿真

脈沖描述字(PDW)流的生成流程如下：

(1) 單部雷達PDW流產(chǎn)生：PDW中脈沖載頻(RF)、脈沖寬度(PW)以及脈沖到達角(DOA)三個屬性最為穩(wěn)定，常用來作為雷達分選系統(tǒng)的依據(jù)。脈沖重復周期(PRI)屬性，用來計算每個脈沖的到達時間(TOA)。因此，本文的雷達信號需要對上述四個屬性進行仿真。其中，PW誤差為1%；DOA誤差為2°；RF分為固定、捷變、跳變，誤差為1%。TOA由下式確定:

TOAn=TOAn-1+PRI+ω

(7)

式中：PRI分為固定、抖動、參差和滑變，TOA0為脈沖初始到達時間，誤差ω為PRI的1%。

(2) 干擾脈沖數(shù)據(jù)流產(chǎn)生：在真實的電子偵察活動中，會有噪聲數(shù)據(jù)進入雷達分選系統(tǒng)。本文通過在隨機時刻加入處在數(shù)據(jù)空間值域內(nèi)的偽隨機數(shù)來模擬干擾脈沖。

(3) 排序處理：多部雷達的PDW流產(chǎn)生后，需要將多個脈沖序列依照TOA排序融合成一個脈沖序列，從而得到整個PDW流。

(4) 重疊處理：當某一脈沖的到達時間小于前一脈沖的結(jié)束時間，就會出現(xiàn)不同雷達脈沖在時域上重疊的現(xiàn)象。當發(fā)生脈沖重疊時，本文按照5%的概率進行了丟失處理。

仿真實驗?zāi)M了4部不同類型雷達的PDW流。同時加入了雷達脈沖總數(shù)10%的干擾脈沖，具體參數(shù)設(shè)置如表1所示。圖6為數(shù)據(jù)點分布圖。

表1 實驗數(shù)據(jù)參數(shù)表

(a) 數(shù)據(jù)點三維分布圖

(b) 含噪聲數(shù)據(jù)點PW-RF分布圖圖6 數(shù)據(jù)點分布圖

由圖6可以看到4部雷達的脈沖載頻RF、PW以及脈沖到達角DOA三個屬性都嚴重重疊在一起，可以用來檢驗雷達分選系統(tǒng)在復雜信號環(huán)境中的有效性。

2.2 實驗結(jié)果分析

為了觀察GDP-Stream算法求得密度峰動態(tài)網(wǎng)格的效果，在T1=7 152.59 μs(第500個數(shù)據(jù)點到達時刻)、T2=10 700.87 μs(第750個數(shù)據(jù)點到達時刻)和T3=14 255.53 μs(第1 000個數(shù)據(jù)點到達時刻)分別求得密度峰動態(tài)網(wǎng)格。如圖7所示，為了方便觀察，將密度峰動態(tài)網(wǎng)格投影到PW-RF平面。可以看出GDP-Stream算法在T1和T2時刻比較準確地求得了每個類的密度峰動態(tài)網(wǎng)格，T3時刻由于類內(nèi)密度的暫時變化，導致該時刻求得的密度峰動態(tài)網(wǎng)格數(shù)量過多，但是由于GDP-Stream算法會合并相似度超過SIMT的相鄰動態(tài)網(wǎng)格集，因此過多的密度峰動態(tài)網(wǎng)格數(shù)量并不會影響聚類質(zhì)量。

圖7 密度峰動態(tài)網(wǎng)格圖

本文采用聚類準確度(CA)作為聚類效果的評價標準，它表示正確聚類的數(shù)據(jù)點數(shù)占總數(shù)據(jù)點數(shù)的比例，計算方法如下：

(8)

式中：n代表總數(shù)據(jù)點數(shù)，|Cj∩Pk|表示屬于第k聚類并且屬于真實分組第j組的記錄數(shù)目。準確度在[0,1]內(nèi)，準確度越大表示聚類效果越好。

為了說明GDP-Stream算法的有效性，本文分別把GDP-Stream算法與ExCC算法以及DP-Stream算法(參數(shù)設(shè)置見文獻[4]、文獻[6])在多個時刻的聚類準確度進行對比。如圖8所示，GDP-Stream算法和DP-Stream算法相比于ExCC算法，有著更好的聚類準確度，這是因為GDP-Stream算法采用動態(tài)網(wǎng)格劃分方式，會產(chǎn)生聚類邊界丟失問題。而DP-Stream算法則由于直接采用DPC算法的思路所以不容易丟失聚類邊界。在大多數(shù)時刻GDP-Stream算法聚類準確度好于DP-Stream算法，這是因為單純使用DPC算法的聚類方法，會導致復雜形狀的類被劃分成多個小類。

圖8 實驗結(jié)果對比圖

3 結(jié) 語

本文針對日益復雜的電磁環(huán)境，提出一種基于網(wǎng)格密度峰值聚類的實時雷達分選系統(tǒng)，該算法將基于網(wǎng)格的數(shù)據(jù)流聚類算法和DPC算法的優(yōu)點融合，并在準確度和效率上加以優(yōu)化。通過仿真實驗證明，本文算法可以在雷達信號嚴重重疊并且存在干擾的電磁環(huán)境中，進行高效、準確的雷達分選。