栗大鵬, 梁偉

(1.北京理工大學(xué) 機(jī)電學(xué)院， 北京 100081; 2.北京遙感設(shè)備研究所， 北京 100854)

針對(duì)非合作目標(biāo)的自適應(yīng)網(wǎng)格聚類算法

栗大鵬1,2, 梁偉2

(1.北京理工大學(xué) 機(jī)電學(xué)院， 北京 100081; 2.北京遙感設(shè)備研究所， 北京 100854)

武器系統(tǒng)的探測(cè)設(shè)備通常面對(duì)的是非合作目標(biāo)，觀測(cè)樣本在特征空間中的分布形式難以預(yù)期，噪聲、不規(guī)則的類簇形狀以及差異化的類簇密度給聚類分析帶來(lái)極大挑戰(zhàn)。提出了一種自適應(yīng)的網(wǎng)格聚類算法，該算法包括基于k-近鄰方法的空間分辨率自適應(yīng)網(wǎng)格化處理方法，以及基于自適應(yīng)分水嶺變換的類簇結(jié)構(gòu)檢測(cè)與劃分方法。實(shí)現(xiàn)了對(duì)噪聲以及密度差異極大類簇的自適應(yīng)處理，同時(shí)保留了網(wǎng)格聚類方法對(duì)類簇形狀不敏感、不需要類個(gè)數(shù)作為先驗(yàn)參數(shù)等優(yōu)點(diǎn)。通過(guò)雷達(dá)、電子偵察以及復(fù)雜人造數(shù)據(jù)集的仿真，證明了該算法的有效性。

人工智能； 網(wǎng)格聚類； 可塑性面積單元問(wèn)題； 分水嶺變換

0 引言

聚類分析是一種無(wú)監(jiān)督的模式識(shí)別技術(shù)，在雷達(dá)、引信、電子偵察、激光紅外等武器系統(tǒng)的目標(biāo)探測(cè)設(shè)備中有廣泛的應(yīng)用。該技術(shù)試圖解決如下問(wèn)題[1]：對(duì)于包含n個(gè)對(duì)象的集合，根據(jù)相似性將其劃分為若干個(gè)組，使得同組對(duì)象之間的相似性較高，而不同組對(duì)象之間的相似性較低。圖1仿真了電子偵察系統(tǒng)收集的對(duì)象在方位角、俯仰角二維空間上的分布，其中存在4個(gè)類簇。

圖1 電子偵察仿真數(shù)據(jù)集Fig.1 ELINT simulation dataset

武器探測(cè)系統(tǒng)主要面對(duì)非合作目標(biāo)，目標(biāo)的信息(如位置、速度、頻譜、能量等)通常是不完整的，因此不能實(shí)現(xiàn)完全匹配處理，導(dǎo)致目標(biāo)探測(cè)樣本在特征空間中的聚合性較差，分布形式難以預(yù)期，某些情況下甚至非常不規(guī)則，給聚類分析帶來(lái)諸多困難，包括：

1)類的個(gè)數(shù)未知。對(duì)于武器系統(tǒng)，類的數(shù)量(通常對(duì)應(yīng)目標(biāo)個(gè)數(shù))在很多時(shí)候是未知的，而一些聚類算法需要類的個(gè)數(shù)作為先驗(yàn)參數(shù)，制約了其在這些場(chǎng)合下的實(shí)用性。

2)類的形狀不規(guī)則。因?yàn)榻邮障到y(tǒng)與目標(biāo)信號(hào)形式的非匹配性，觀測(cè)對(duì)象在特征空間中聚集性較差，類簇的形狀可能會(huì)發(fā)生畸變，形成非凸殼類簇，如圖1左上的類簇。這些類簇很難確定類中心的位置，從而影響某些聚類算法的效果。

3)類簇間對(duì)象密度的差異。對(duì)象的相似性通常用特征空間中的距離或密度進(jìn)行衡量。而在某些情況下不同類簇的對(duì)象密度差異較大，如圖1所示，右側(cè)兩個(gè)類簇的類間距離與左下類簇的類內(nèi)對(duì)象間距可以比擬。這種情況下很難確定統(tǒng)一的相似度門(mén)限。

4)噪聲對(duì)象的影響?，F(xiàn)代戰(zhàn)場(chǎng)上存在大量有意干擾和無(wú)意干擾，而且很多情況下信噪比水平是時(shí)變的。因此聚類算法需要考慮對(duì)噪聲對(duì)象進(jìn)行自適應(yīng)的抑制。

現(xiàn)有的聚類算法一般被分為5類，分別是劃分式算法、層次化算法、基于密度的算法、基于網(wǎng)格的算法以及基于模型的算法[1]。從算法的實(shí)時(shí)性角度來(lái)看，劃分式算法以及基于網(wǎng)格的算法相對(duì)其他算法有明顯優(yōu)勢(shì)。然而，以K-means、C-means為代表的劃分式算法需要類的個(gè)數(shù)作為先驗(yàn)參數(shù)，而且對(duì)非凸殼類簇的聚類效果不太理想[2-3]?；诰W(wǎng)格的聚類方法首先對(duì)特征空間進(jìn)行網(wǎng)格劃分，將其量化為包含不同對(duì)象數(shù)目的單元格，并定義網(wǎng)格的密度函數(shù)，此后的聚類分析只針對(duì)單元格進(jìn)行操作，與對(duì)象數(shù)量無(wú)關(guān)，從而能夠獲得較高的運(yùn)算效率，很適用于大數(shù)據(jù)的聚類分析[4]。另外網(wǎng)格類聚類算法還具有不需要預(yù)知類個(gè)數(shù)，對(duì)樣本輸入順序不敏感，對(duì)類的形狀不敏感等優(yōu)點(diǎn)。經(jīng)典的網(wǎng)格聚類算法包括GDCA[5]、CLIQUE[6]、GGCA[7]、改進(jìn)的分水嶺聚類[8]等。然而，正如文獻(xiàn)[7]指出，所有的網(wǎng)格聚類算法都要面對(duì)以下兩方面的共性問(wèn)題：1)網(wǎng)格顆粒度的選擇問(wèn)題，即可塑性面積單元問(wèn)題(MAUP)[9]，當(dāng)類簇密度差異過(guò)大時(shí)這一問(wèn)題尤為突出，即前述第3點(diǎn)困難；2)類的檢測(cè)與劃分的問(wèn)題，特別是在前述第3點(diǎn)、第4點(diǎn)困難的情況下，如何進(jìn)行類的檢測(cè)與劃分。如此可見(jiàn)，基于網(wǎng)格的聚類算法用于武器系統(tǒng)非合作目標(biāo)聚類分析主要需要解決前述第3點(diǎn)、第4點(diǎn)困難。因此，本文提出一種自適應(yīng)的網(wǎng)格聚類方法，以應(yīng)對(duì)上述挑戰(zhàn)。

1 問(wèn)題描述以及相關(guān)的研究

1.1 對(duì)MAUP的研究

MAUP最早由Openshawn在1977年提出[9]。在網(wǎng)格聚類算法中，網(wǎng)格密度通常被定義為單元格內(nèi)包含的對(duì)象數(shù)量，這樣，在不同顆粒度的網(wǎng)格劃分下，空間中就會(huì)呈現(xiàn)出不同的類簇結(jié)構(gòu)。以圖2、圖3為例：對(duì)同一組數(shù)據(jù)集，當(dāng)采用如圖2(a)所示的大顆粒度劃分時(shí)，得到的密度地形圖如圖2(b)所示，在網(wǎng)格空間中能夠正確區(qū)分左下角的類，但無(wú)法分辨右上角的4個(gè)類，出現(xiàn)了空間模糊；而當(dāng)采用如圖3(a)所示的小顆粒度劃分時(shí)，右上角的4個(gè)類能被正確區(qū)分，而左下角的類則被過(guò)度分割。

圖2 大顆粒度網(wǎng)格化效果Fig.2 Gridding effect under gross granularity

圖3 小顆粒度網(wǎng)格化效果Fig.3 Gridding effect under fine granularity

一些網(wǎng)格聚類算法對(duì)這一問(wèn)題專門(mén)進(jìn)行了研究。文獻(xiàn)[7-8]的方法基于這樣一種假設(shè)：在最合適的顆粒度下，類簇在地形圖上形成局部尖峰，這樣在對(duì)網(wǎng)格密度進(jìn)行直方圖統(tǒng)計(jì)后，將呈現(xiàn)出多峰值的特征。通過(guò)遍歷不同顆粒度的網(wǎng)格或?yàn)V波模板，能夠讓這種多峰值特征最大化(或密度值統(tǒng)計(jì)方差最大化)的即為最佳顆粒度。然而，上述的方法只能適用于不同類簇內(nèi)的對(duì)象密度相差不大的情況，當(dāng)這個(gè)密度差異非常大的時(shí)候，是無(wú)法獲取一個(gè)適中的顆粒度兼顧所有類簇的。為此文獻(xiàn)[10-12]采用了一種非均勻的網(wǎng)格劃分方法：首先采用較粗的顆粒度進(jìn)行均勻網(wǎng)格化，然后選取那些密度值大于門(mén)限t的網(wǎng)格，將其等分成兩個(gè)網(wǎng)格，這樣不斷循環(huán)，特征空間就被分成大小不同、但密度值均小于t的網(wǎng)格。這種方法能夠根據(jù)局部密度調(diào)整網(wǎng)格尺寸，但非均勻的劃分也為后續(xù)處理帶來(lái)了很多困難，另外門(mén)限值t的選擇顯然非常關(guān)鍵，這也涉及到下面要討論的類的檢測(cè)與劃分問(wèn)題。

1.2 類簇檢測(cè)與劃分問(wèn)題的研究

大部分的網(wǎng)格聚類算法都會(huì)用到“有效網(wǎng)格”的概念，即那些密度較高，可能存在類簇的網(wǎng)格。通常采用門(mén)限比較的方法將高密度的網(wǎng)格與背景網(wǎng)格區(qū)分開(kāi)來(lái)，超過(guò)門(mén)限的網(wǎng)格形成若干個(gè)互連區(qū)域，然后再將這些區(qū)域進(jìn)一步合并或分割，形成類簇。顯然，確定合適的門(mén)限是這類算法的關(guān)鍵。然而對(duì)于如圖4(a)所示的一維網(wǎng)格密度地形圖，不同的門(mén)限將形成不同的聚類效果，無(wú)法用統(tǒng)一的門(mén)限檢測(cè)出所有的類。

圖4 不同密度類的檢測(cè)與劃分Fig.4 Detection and partition of clusters with diverse densities

為此，文獻(xiàn)[8]采用圖像形態(tài)學(xué)的分水嶺變換進(jìn)行類簇的分割，這種算法起源于地形學(xué)的概念：灰度圖像被看作地形圖，包括山峰和山谷，一滴水從平面上任意一點(diǎn)落下，最終穩(wěn)定于一個(gè)局部最低點(diǎn)。水在各個(gè)山谷內(nèi)累積形成聚水盆，當(dāng)兩個(gè)聚水盆將要融合的時(shí)候，認(rèn)為構(gòu)建分水嶺保持其隔離狀態(tài)，這樣直到水漫過(guò)最高的山峰，分水嶺就形成了對(duì)圖像的分割。網(wǎng)格化的空間可看作多維圖像，網(wǎng)格密度對(duì)應(yīng)灰度值。原始分水嶺算法采用自底向上填平峽谷的方式，將其逆轉(zhuǎn)，采用自頂向下削平山峰的方式，即可用于網(wǎng)格聚類。這種方法能夠發(fā)現(xiàn)并利用局部區(qū)域密度的相對(duì)差異，找到相對(duì)集中的類簇，并在峽谷上形成分水嶺，作為類的分割線。其聚類效果如圖4(b)所示。

通過(guò)上述分析可知，分水嶺聚類相較于固定門(mén)限方法有明顯優(yōu)勢(shì)。但是，直接采用原始分水嶺方法存在噪聲敏感的缺點(diǎn)。受噪聲的影響，不僅在背景中會(huì)檢測(cè)出虛假的類，還會(huì)造成同屬一個(gè)類簇區(qū)域的過(guò)度分割。文獻(xiàn)[8]提出的改進(jìn)分水嶺聚類算法采樣中值濾波方法，只選取密度大于全局極大值一半的峰值點(diǎn)作為有效類中心，但這種方法損失了對(duì)類簇密度差異的適應(yīng)性，圖4中低密度的類簇顯然會(huì)被漏檢。因此，本文提出一種自適應(yīng)的基于分水嶺變換的類簇檢測(cè)與劃分方法，以降低噪聲的影響并抑制過(guò)度分割效應(yīng)，進(jìn)一步提高算法的適應(yīng)性。

2 算法

2.1 空間分辨率自適應(yīng)的網(wǎng)格化方法

理想的網(wǎng)格劃分應(yīng)該針對(duì)不同密度的類簇采用不同顆粒度的網(wǎng)格，然而悖論是，在未進(jìn)行聚類分析之前，類簇的分布和密度又是未知的。因此，本文提出了另外一種思路，采用較小顆粒度的網(wǎng)格保證空間分辨力，利用類內(nèi)對(duì)象具有內(nèi)聚性的特點(diǎn)，用k-近鄰方法定義新的密度函數(shù)，以適應(yīng)不同分布密度，下面進(jìn)行具體討論。

1) 確定網(wǎng)格尺度。對(duì)于N維特征空間，在各個(gè)維度上分別進(jìn)行均勻網(wǎng)格劃分，某一維度上劃分的顆粒度與該維度上期望得到的分辨率匹配，例如在距離維上需要能夠分離兩個(gè)間隔1 cm以上的類簇，那就可以將距離維的顆粒度定為0.5 cm或1 mm，從而獲得足夠精細(xì)的空間區(qū)分度。

2) 定義密度函數(shù)。設(shè)X={xξ∈RD,ξ=1,…,n}代表D維空間中的對(duì)象集，取單元格i的中心點(diǎn)ci，在X中找到K個(gè)與中心點(diǎn)最近鄰的對(duì)象{xi,1,xi,2,…，xi,K}，d(ci,xi,j)代表兩個(gè)對(duì)象之間的距離，則單元格i的密度為

(1)

從(1)式可以看出單元格i的密度與中心點(diǎn)ci的位置、K值以及周?chē)鷮?duì)象分布的疏密程度相關(guān)，而與網(wǎng)格劃分的顆粒度無(wú)關(guān)。

(1)式中K值決定密度函數(shù)在類簇內(nèi)的波動(dòng)率和類簇邊緣的衰減率。直觀上，K越大，平滑效果越明顯，類簇內(nèi)部密度的起伏越小，有利于抑制類簇內(nèi)部的過(guò)度分割，但同時(shí)類簇邊緣的密度衰減越緩慢，不利于類簇間的分割；反之亦然。因此需要對(duì)這兩個(gè)指標(biāo)進(jìn)行權(quán)衡取舍確定最佳的K值。這里以均勻分布的對(duì)象集為標(biāo)準(zhǔn)，不失一般性，對(duì)象在各維度上的分布間隔均為l，網(wǎng)格在各維度上的尺寸為g，并令g?l. 定義類簇內(nèi)的波動(dòng)率β為類簇區(qū)域內(nèi)網(wǎng)格密度最高值DenInmax與類簇區(qū)域內(nèi)網(wǎng)格密度最低值DenInmin之比。定義類簇邊緣處的衰減率α為所有密度值小于0.1DenInmax的網(wǎng)格與類簇內(nèi)任意對(duì)象間的最短距離。β、α與K的關(guān)系不容易用解析式表達(dá)，本文采用數(shù)值仿真的方法計(jì)算。以二維空間為例，取歐式距離，在不同K值下的β與α如表1所示。由表1可知，β并非隨K值嚴(yán)格單調(diào)遞減，在K=5時(shí)波動(dòng)率β較小，同時(shí)也能兼顧到較好的衰減率α，故而將5設(shè)為最佳K值。

表1 指標(biāo)水平表

采用上述方法對(duì)圖2和圖3中的對(duì)象進(jìn)行網(wǎng)格化處理，網(wǎng)格邊長(zhǎng)為0.1，K值取5，得到如圖5所示的密度地形圖。由圖5可知，5個(gè)密度差異很大的類簇都被凸顯出來(lái)，并且由于網(wǎng)格顆粒度很小，距離較近的類簇都能被清晰的區(qū)分，這樣就可以采用較小的網(wǎng)格得到理想的空間分辨率，同時(shí)又不會(huì)因?yàn)榫W(wǎng)格過(guò)小產(chǎn)生過(guò)度分割的現(xiàn)象，從而規(guī)避了MAUP問(wèn)題。

圖5 自適應(yīng)網(wǎng)格化方法的效果Fig.5 Griding effect of adaptive gridding method

2.2 基于自適應(yīng)分水嶺變換的類簇檢測(cè)與劃分

原始的分水嶺方法能夠自動(dòng)發(fā)現(xiàn)相對(duì)集中的類簇，對(duì)密度差異較大的類簇有很好的適應(yīng)性，但其缺點(diǎn)在于易受噪聲影響，產(chǎn)生過(guò)度分割，網(wǎng)格密度的局部不規(guī)則性也會(huì)加劇這一趨勢(shì)。故而，成功應(yīng)用分水嶺聚類的關(guān)鍵在于對(duì)背景噪聲和過(guò)度分割效應(yīng)的抑制，下面詳細(xì)介紹本文的方法。

2.2.1 自適應(yīng)背景噪聲抑制

背景噪聲分布在整個(gè)特征空間內(nèi)，首先估計(jì)噪聲網(wǎng)格的密度值范圍。數(shù)據(jù)集如圖6(a)所示，按2.1節(jié)方法生成密度地形圖6(b)。統(tǒng)計(jì)其密度直方圖如圖6(c)所示，其橫坐標(biāo)為密度值DH(i)，縱坐標(biāo)為地形圖上落入密度值區(qū)間內(nèi)的像素點(diǎn)數(shù)PN(i)，其中i為對(duì)橫坐標(biāo)區(qū)間量化的序號(hào)。密度值區(qū)間的劃分與噪聲網(wǎng)格的密度分布范圍、噪聲與對(duì)象之間密度值的差異等因素相關(guān)，同樣存在MAUP問(wèn)題。若間隔較大，噪聲與對(duì)象之間不容易區(qū)分；若間隔較小，落入每個(gè)區(qū)間的點(diǎn)數(shù)較少，出現(xiàn)過(guò)度分割。故而，這里采用一維的自適應(yīng)網(wǎng)格化方法，即采用較小的密度間隔，同時(shí)用(1)式對(duì)PN(i)進(jìn)行等價(jià)計(jì)算。

圖6 自適應(yīng)背景噪聲抑制方法Fig.6 Adaptive background noise suppression method

顯然，只有當(dāng)類簇密度大于背景噪聲密度的時(shí)候，類簇才能被檢測(cè)出來(lái)，因此只考慮類簇密度值大于噪聲的情況。故而，認(rèn)為圖6(c)的第1個(gè)尖峰屬于噪聲網(wǎng)格區(qū)域，其中峰值點(diǎn)對(duì)應(yīng)的橫坐標(biāo)(網(wǎng)格密度值)為DenNP. 接下來(lái)確定噪聲網(wǎng)格的密度函數(shù)值的分布范圍，假設(shè)噪聲分布區(qū)間關(guān)于峰值點(diǎn)對(duì)稱，首先將圖6(c)上左起第1個(gè)非0網(wǎng)格定為左邊界DenNL，則其右邊界DenNR為2DenNP-DenNL，認(rèn)為DenNR就是噪聲網(wǎng)格密度函數(shù)的最大值，以DenNR作為噪聲抑制門(mén)限，大部分的噪聲網(wǎng)格都將被過(guò)濾掉。圖6(d)所示為圖6(b)的檢測(cè)結(jié)果，紅色區(qū)域?yàn)槌^(guò)門(mén)限的網(wǎng)格，由此可見(jiàn)效果比較理想。

該方法借鑒了恒虛警檢測(cè)的思想，門(mén)限可以根據(jù)噪聲水平自動(dòng)調(diào)整。

2.2.2 分水嶺聚類過(guò)度分割抑制

以圖7(a)的數(shù)據(jù)集為例，實(shí)施上述噪聲門(mén)限抑制處理，然后進(jìn)行分水嶺分割，結(jié)果如圖7(b)所示，可見(jiàn)類簇內(nèi)部還是存在過(guò)度分割，這是局部的地形起伏造成的。常見(jiàn)的方法是加入濾波預(yù)處理，以平滑局部尖峰。然而，濾波模板的尺度又直接關(guān)系到空間分辨力，使前面闡述的MAUP問(wèn)題更加復(fù)雜化，故而本文不考慮此類方法。在聚類的原始定義中，類是一組內(nèi)部相似性較高的對(duì)象，因此在網(wǎng)格空間中，類簇內(nèi)部應(yīng)該具有相近的密度值，類簇之間應(yīng)存在過(guò)渡區(qū)域，其密度明顯小于與其相鄰的類簇，形成峽谷，正確的分水嶺應(yīng)該出現(xiàn)在這些峽谷上。基于這種思想，本文設(shè)計(jì)一組規(guī)則，消除那些多余的分水嶺，保留有價(jià)值的分水嶺。

圖7 分水嶺聚類的過(guò)度分割Fig.7 Over-segmentation of watershed clustering

峽谷所在的低密度區(qū)域是一個(gè)相對(duì)的概念，需要根據(jù)其周?chē)惔氐拿芏茸詣?dòng)調(diào)整，為了實(shí)現(xiàn)這一目的，需要首先確定類簇內(nèi)部網(wǎng)格密度的波動(dòng)水平。對(duì)象在局部分布的不規(guī)則性會(huì)導(dǎo)致類簇內(nèi)部網(wǎng)格密度的波動(dòng)。對(duì)象的分布規(guī)律千差萬(wàn)別，根據(jù)中心極限定理，假設(shè)同一類簇內(nèi)網(wǎng)格密度值統(tǒng)計(jì)規(guī)律服從高斯分布。設(shè)高斯分布均值為μ，方差為σ2，認(rèn)為峰值點(diǎn)±2σ內(nèi)是同屬一個(gè)類簇的網(wǎng)格密度分布范圍，則密度值下限與密度值峰值的比例為

(2)

設(shè)DenCpeak為類簇的峰值密度，以該數(shù)值乘以RDenC以及2.1節(jié)介紹波動(dòng)率β作為判斷類簇邊界的門(mén)限：

TC=βRDenCDenCpeak=0.143 6DenCpeak.

(3)

在峰值周?chē)芏鹊陀赥C的網(wǎng)格被認(rèn)為屬于低密度區(qū)域，屬類簇范圍之外。基于上述準(zhǔn)則，設(shè)計(jì)如下的流程對(duì)分水嶺變換產(chǎn)生的過(guò)度分割區(qū)域進(jìn)行合并：

步驟1在未經(jīng)過(guò)合并處理的分割區(qū)域中選擇最高峰值所在的區(qū)域作為目標(biāo)區(qū)域，將最高峰值設(shè)為DenCpeak，并按(3)式計(jì)算TC；

步驟2尋找一個(gè)與目標(biāo)區(qū)域通過(guò)分水嶺相連的區(qū)域作為備選區(qū)域，若二者間公共分水嶺上的網(wǎng)格密度高于TC，則消除公共分水嶺，將備選區(qū)域合并到目標(biāo)區(qū)域內(nèi)；

步驟3重復(fù)步驟2，這樣逐步向周?chē)鷶U(kuò)大目標(biāo)區(qū)域，直到?jīng)]有備選區(qū)域，或者剩余的分水嶺都無(wú)法消除；

步驟4返回步驟1尋找下一個(gè)目標(biāo)區(qū)域，這樣遍歷整個(gè)特征空間，得到若干目標(biāo)區(qū)域?qū)?yīng)不同的類簇所占據(jù)的范圍。

對(duì)圖7(b)采用上述方法，效果如圖8(a)所示，兩個(gè)類中的過(guò)度分割得到了很好的抑制，得到的聚類結(jié)果如圖8(b)所示。

圖8 過(guò)度分割抑制效果Fig.8 Suppression effect of over-segmentation

3 仿真及分析

本文將算法用于武器探測(cè)系統(tǒng)仿真數(shù)據(jù)集以及人造數(shù)據(jù)集，以進(jìn)一步驗(yàn)證其在戰(zhàn)場(chǎng)仿真場(chǎng)景中及各種極端條件下的聚類效果。由1.2節(jié)的分析可知，分水嶺聚類相較于其他網(wǎng)格聚類方法在類簇密度差異適應(yīng)性上有較大優(yōu)勢(shì)，因此本文的對(duì)比對(duì)象為文獻(xiàn)[8]的改進(jìn)分水嶺聚類算法。

仿真本文算法的關(guān)鍵參數(shù)設(shè)置如下：(1)式中的K=5，類簇邊界門(mén)限采用(3)式中的參數(shù)。

3.1 電子偵察數(shù)據(jù)集

在電子偵察系統(tǒng)中，到達(dá)角是主要的輻射源分選依據(jù)。建立仿真系統(tǒng)，采用和差比幅測(cè)角體制，接收機(jī)帶內(nèi)噪聲為-20 dB，4個(gè)輻射源信號(hào)的信噪比分別為10 dB、-15 dB、-10 dB和-10 dB. 在經(jīng)過(guò)一段時(shí)間的觀測(cè)積累后，信號(hào)樣本到達(dá)角在方位角、俯仰角二維空間上的分布如圖9所示。

圖9 電子偵察數(shù)據(jù)集Fig.9 ELINT dataset

由于來(lái)自不同輻射源的信號(hào)能量不同，噪聲對(duì)其的影響也不盡相同，各輻射源樣本的分布呈現(xiàn)不同規(guī)律。

文獻(xiàn)[8]的改進(jìn)分水嶺聚類算法采用最大化直方圖標(biāo)準(zhǔn)差的方法確定最佳顆粒度，但由于其采用統(tǒng)一的網(wǎng)格尺寸，并將網(wǎng)格內(nèi)對(duì)象數(shù)量作為密度值，不可避免會(huì)在網(wǎng)格化過(guò)程中產(chǎn)生MAUP問(wèn)題。這里人工選定一個(gè)適中的網(wǎng)格尺寸，得到的地形圖如圖10(a)，分水嶺劃分結(jié)果如圖10(c)所示，圖10中不同顏色的區(qū)域?qū)?yīng)不同的類簇?？梢?jiàn)其中出現(xiàn)了明顯的過(guò)度分割，并且由于采用了中值濾波處理，密度最低的類簇被漏檢了。

采用本文方法的地形圖如圖10(b)，分水嶺劃分結(jié)果如圖10(d)所示，4個(gè)類簇的范圍被正確劃分。需要說(shuō)明的是由于采用了本文的自適應(yīng)網(wǎng)格化方法，圖10(d)中類簇的范圍被擴(kuò)大，但不影響最終的聚類結(jié)果，距離較近的類也被正確分離，如圖11所示，可見(jiàn)整體聚類結(jié)果比較理想。

3.2 雷達(dá)探測(cè)數(shù)據(jù)集

雷達(dá)探測(cè)數(shù)據(jù)的特征空間包括方位角、俯仰角、距離、速度4個(gè)維度，屬于高維數(shù)據(jù)集。某仿真作戰(zhàn)場(chǎng)景中，目標(biāo)呈編隊(duì)密集分布，在雷達(dá)天線主波束內(nèi)存在多個(gè)目標(biāo)，并且由于速度、距離接近，一般方法不易分辨。采用聚類分析，記錄距離波門(mén)內(nèi)所有時(shí)刻樣本的上述四維信息，經(jīng)過(guò)100個(gè)脈沖的數(shù)據(jù)積累，形成的數(shù)據(jù)集如圖12(a)所示(這里為了可視化僅繪出三維圖形)，其中還存在均勻分布的噪聲對(duì)象，接收機(jī)帶內(nèi)的信噪比為10 dB. 采用本文方法的聚類結(jié)果如圖12(b)所示，可見(jiàn)整體的聚類結(jié)果比較理想。

圖12 四維雷達(dá)目標(biāo)數(shù)據(jù)集聚類效果Fig.12 Clustering effect of the algorithm for 4-D radar target simulation dataset

3.3 Jain數(shù)據(jù)集

為了更加全面的考驗(yàn)算法性能，采用Jain數(shù)據(jù)集，這一數(shù)據(jù)集是由Jain在文獻(xiàn)[3]中提出的，其中包含不同形狀、密度及大小的類，并散布著均勻分布的噪聲。圖13左側(cè)的兩個(gè)類密度差異很大，無(wú)法為它們找到相同的距離門(mén)限或密度門(mén)限作為相似度標(biāo)準(zhǔn)；右上角兩個(gè)蛇形纏繞的類沒(méi)有明確的類中心；右下角的類在拓?fù)浣Y(jié)構(gòu)上完全包圍。Jain認(rèn)為還沒(méi)有一種聚類算法能夠成功識(shí)別出圖13中所有的類。

圖13 Jain數(shù)據(jù)集Fig.13 Jain dataset

圖14 Jain數(shù)據(jù)集兩種分水嶺聚類效果比較Fig.14 Compareison of two watershed clustering effects for Jain dataset

雖然Jain對(duì)象集是一個(gè)人工設(shè)計(jì)的特例，但是隨著戰(zhàn)場(chǎng)對(duì)抗的不斷升級(jí)，需要處理的目標(biāo)模式越來(lái)越多、差異也越來(lái)越大，難免出現(xiàn)類似Jain對(duì)象集里的某種模式。對(duì)圖13的Jain數(shù)據(jù)集，首先采用文獻(xiàn)[8]的改進(jìn)分水嶺聚類，同樣人工選定其最佳顆粒度。得到圖14(a)的地形圖和14(c)的分水嶺劃分結(jié)果，其效果差強(qiáng)人意。采用本文方法得到的地形圖、分水嶺劃分效果如圖14(b)及14(d)所示。最終聚類結(jié)果如圖15所示。需要說(shuō)明處理結(jié)果存在的兩個(gè)缺陷：1)由于左上角類簇的密度較低，接近背景噪聲的密度，導(dǎo)致部分本來(lái)屬于類簇內(nèi)的對(duì)象被漏檢，該類簇的范圍在邊緣處出現(xiàn)了斷續(xù)的現(xiàn)象；2)右下角被3個(gè)環(huán)形類簇包圍的噪聲對(duì)象因?yàn)榕c外部噪聲對(duì)象隔離，被識(shí)別為3個(gè)新類。但整體來(lái)看，劃分效果比較清晰，各主要類簇均被成功檢測(cè)出。

圖15 自適應(yīng)網(wǎng)格聚類結(jié)果Fig.15 Adaptive grid-based clustering result

4 結(jié)論

本文提出了一種應(yīng)用于武器探測(cè)系統(tǒng)對(duì)非合作目標(biāo)處理的自適應(yīng)網(wǎng)格聚類算法，其核心包括：1)空間分辨率自適應(yīng)的網(wǎng)格化方法，解決了網(wǎng)格劃分的MAUP問(wèn)題；2)自適應(yīng)分水嶺聚類方法，利用自適應(yīng)噪聲門(mén)限以及過(guò)度分割抑制處理實(shí)現(xiàn)了在噪聲環(huán)境下不同密度類簇結(jié)構(gòu)的檢測(cè)與劃分。仿真實(shí)驗(yàn)表明，該算法達(dá)到了預(yù)期效果，能夠處理空間中分布形式差異極大的類簇，具有一定的噪聲抑制能力，并且對(duì)類簇分布形式不敏感。其主要缺點(diǎn)在于背景噪聲抑制算法的效果在類簇與噪聲密度接近的情況下不夠理想，導(dǎo)致對(duì)類邊緣的劃分不夠精確，有待于進(jìn)一步研究改進(jìn)。

References)

[1] 孫吉貴, 劉杰, 趙連宇. 聚類算法研究[J]. 軟件學(xué)報(bào), 2008, 19(1):48-61.

SUN Ji-gui, LIU Jie, ZHAO Lian-yu. Clustering algorithms research[J]. Journal of Software, 2008, 19(1):48-61. (in Chinese)

[2] Mok P Y, Huang H Q, Kwok Y L, et al. A robust adaptive clustering analysis method for automatic identification of clusters[J]. Pattern Recognition, 2012, 45(8):3017-3033.

[3] Jain A K. Data clustering: 50 years beyond K-means[J]. Pattern Recognition Letters, 2010, 31(8): 651-666.

[4] 伍育紅. 聚類算法綜述[J]. 計(jì)算機(jī)科學(xué),2015,42(增刊1):491-499,524.

WU Yu-hong. General overview on clustering algorithms[J]. Computer Science, 2015, 42(S1):491-499,524. (in Chinese)

[5] 陳寧, 陳安, 周龍?bào)J. 基于密度的增量式網(wǎng)格聚類算法[J]. 軟件學(xué)報(bào), 2002, 13(1):1-7.

CHEN Ning, CHEN An, ZHOU Long-xiang. An incremental grid density-based clustering algorithm[J]. Journal of Software, 2002, 13(1):1-7. (in Chinese)

[6] Agrawal R, Gehrke J, Gunopulos D. Automatic subspace clustering of high dimensional data[J]. Data Mining and Knowledge Discovery, 2005, 11(1): 5-33.

[7] Yue S, Wei M, Wang J S, et al. A general grid-clustering approach[J]. Pattern Recognition Letters, 2008, 29(9):1372-1384.

[8] Lolla S V G, Hoberock L L.Improved unsupervised clustering over watershed-based clustering[C]∥Proceedings of the 9th International Conference on Machine Learning and Applications.Washington DC, US: IEEE, 2010:253-259.

[9] Openshaw S. A geographical solution to scale and aggregation problems in region-building, partition and spatial modeling[J]. Transactions of the Institute of British Geographers, 1977, 2(4):1782-1795.

[10] Dou W, Hu J. A half-split grid clustering algorithm by simulating cell division[C]∥Proceedings of International Joint Conference on Neural Networks. Beijing, China: IEEE, 2014:2183-2189.

[11] Micheal S, Maria P.Fast grid-based clustering method for automatic calculation of optimal parameters of skin color classifier for head tracking[C]∥Proceedings of the 2nd International Conference on Cybernetics. Gdynia, Poland: IEEE, 2015: 119-124.

[12] Schikuta E, Fritz F. An execution framework for grid-clustering methods[J]. Procedia Computer Science, 2016: 80:2322-2326.

AnAdaptiveGrid-basedClusteringAlgorithmforNoncooperativeTargets

LI Da-peng1,2， LIANG Wei2

(1.School of Mechatronical Engineering, Beijing Institute of Technology, Beijing 100081, China; 2.Beijing Institute of Remote Sensing & Equipment, Beijing 100854, China)

The detection equipment of weapon systems is usually used to detect the noncooperative targets, causing the distribution patterns of observed samples to be unpredictable in feature spaces. The irregular cluster shapes, diversified cluster densities and noise bring great challenges to clustering algorithms. A novel adaptive grid-based clustering algorithm, which consists of ak-nearest neighbor method-based gridding method with spatial resolution adaptability, and an adaptive watershed transform-based method for cluster detection and segmentation in the gridded space are presented. The proposed algorithm could process the clusters with noises and significantly diverse densities, meanwhile keeps the advantages of gird-based clustering, including robustness for cluster shape and no need for cluster number as priori parameter. The effectiveness of the algorithm is tested with simulation and artificial datasets.

artificial intelligence; grid-based clustering; modifiable areal unit problem; watershed transform

TP301.6

A

1000-1093(2017)11-2166-10

10.3969/j.issn.1000-1093.2017.11.012

2017-02-16

國(guó)防“973”計(jì)劃項(xiàng)目(613196)

栗大鵬(1982—), 男, 博士研究生。E-mail: li_dapeng@foxmail.com

梁偉(1976—), 男, 研究員。E-mail: lwlevil@163.com