基于極值特征的雷達(dá)偵察數(shù)據(jù)BIRCH聚類方法

張 宇

（中國(guó)西南電子技術(shù)研究所 四川 成都　610036）

基于極值特征的雷達(dá)偵察數(shù)據(jù)BIRCH聚類方法

張 宇

（中國(guó)西南電子技術(shù)研究所 四川 成都610036）

為解決傳統(tǒng)BIRCH算法對(duì)數(shù)據(jù)對(duì)象輸入順序敏感、聚類結(jié)果不穩(wěn)定的問(wèn)題，提出了一種改進(jìn)的BIRCH算法。該算法將雷達(dá)信號(hào)偵察數(shù)據(jù)的脈沖載頻、脈沖重復(fù)間隔和脈沖寬度分別進(jìn)行聚類，根據(jù)工程應(yīng)用中各參數(shù)量測(cè)誤差和系統(tǒng)誤差設(shè)定不同閾值。并且引入聚類簇的極大極小值作為聚類特征，使用層次樹的方法來(lái)構(gòu)建聚類特征模型，實(shí)現(xiàn)了雷達(dá)偵察數(shù)據(jù)的快速向下搜索及聚類。實(shí)驗(yàn)結(jié)果表明，該方法是可行、有效的。

雷達(dá)偵察數(shù)據(jù)；脈沖描述字；BIRCH；極值特征；層次聚類

雷達(dá)信號(hào)偵察數(shù)據(jù)處理的參數(shù)包含：脈沖前沿到達(dá)時(shí)間（TOA）、脈沖到達(dá)角（DOA）、脈沖載頻（RF）、脈沖重復(fù)間隔（PRI）、脈沖寬度（PW）、脈沖幅度（PA），統(tǒng)稱為脈沖描述字（PDW）。對(duì)脈沖載頻（RF）、脈沖重復(fù)間隔（PRI）和脈沖寬度（PW）分別進(jìn)行聚類，并在到達(dá)時(shí)間（TOA）和到達(dá)角（DOA）上做進(jìn)一步時(shí)序分析，能夠識(shí)別雷達(dá)輻射源和還原雷達(dá)輻射源的工作模式。在雷達(dá)信號(hào)偵察數(shù)據(jù)累積數(shù)月或數(shù)年的前提下，數(shù)據(jù)量高達(dá)TB級(jí)，同時(shí)雷達(dá)信號(hào)偵察數(shù)據(jù)是按時(shí)序到達(dá)的數(shù)據(jù)流，不僅需要離線數(shù)據(jù)聚類，同時(shí)也要對(duì)實(shí)時(shí)數(shù)據(jù)流進(jìn)行聚類。許多傳統(tǒng)的聚類算法［1-2］如平均誤差聚類算法［3］、K-均值聚類算法［4］、最近鄰算法［5］、PAM算法在時(shí)效性和計(jì)算資源上已經(jīng)無(wú)法滿足需求。傳統(tǒng)BIRCH算法［6-8］通過(guò)構(gòu)建聚類特征（Clustering feature）CF樹，通過(guò)對(duì)數(shù)據(jù)集一次掃描的基礎(chǔ)上，增量地對(duì)多維數(shù)據(jù)完成聚類。傳統(tǒng)BIRCH算法適用于大規(guī)模數(shù)據(jù)集的聚類，聚類效率高，應(yīng)用于各個(gè)領(lǐng)域。李磊［9］、李曉嫻［10］將該方法應(yīng)用于大規(guī)模微博實(shí)時(shí)抓取數(shù)據(jù)，通過(guò)BIRCH層次聚類的方法得到微博熱點(diǎn)列表，結(jié)合微博本身特征信息評(píng)價(jià)微博的熱度。王旭［11］首次提出了基于注冊(cè)信息的學(xué)習(xí)分組算法，實(shí)現(xiàn)了針對(duì)學(xué)習(xí)者學(xué)習(xí)需求和學(xué)習(xí)能力等要素的個(gè)性化分組。吳春瓊［12］則是將BIRCH方法應(yīng)用于入侵檢測(cè)。

BIRCH算法在實(shí)際聚類中也存在缺陷：對(duì)數(shù)據(jù)對(duì)象插入順序敏感；不善于劃分體積差別較大的類別；類別劃分會(huì)陷入局部最優(yōu)；節(jié)點(diǎn)分裂方式容易將一個(gè)中心簇分類為兩個(gè)對(duì)等簇。仰孝富［13］提出基于BIRCH和KNN的改進(jìn)聚類算法，在構(gòu)建KNN連接圖基礎(chǔ)上利用圖劃分方法得到聚類簇后，再利用BIRCH進(jìn)行聚類，改善對(duì)數(shù)據(jù)輸入順序的敏感問(wèn)題，保持聚類的穩(wěn)定性。周迎春、路嘉偉［14］將CF中數(shù)據(jù)對(duì)象的平方和改進(jìn)為離差平方和，適應(yīng)體積差別較大的類別。楊敏煜［15］則是基于密度來(lái)劃分類別，減少對(duì)閾值T的依賴，以及發(fā)現(xiàn)任意形狀的簇。本文結(jié)合工程實(shí)際，提出了一種基于極值特征的雷達(dá)偵察數(shù)據(jù)BIRCH聚類方法，該算法將雷達(dá)信號(hào)偵察數(shù)據(jù)的脈沖載頻、脈沖重復(fù)間隔和脈沖寬度分別進(jìn)行聚類，根據(jù)工程應(yīng)用中各參數(shù)量測(cè)誤差和系統(tǒng)誤差設(shè)定閾值T。算法選取類別中最大最小值作為類特征，運(yùn)用閾值T來(lái)控制類的數(shù)據(jù)大小范圍，并使用層次樹的方法來(lái)形成聚類特征模型。仿真結(jié)果表明本方法能有效克服BIRCH算法順序敏感性，提高聚類質(zhì)量。

1　BIRCH聚類方法

BIRCH算法是一個(gè)增量式的層次聚類算法，該算法的主要結(jié)構(gòu)是一棵CF樹，聚類的過(guò)程都是在這棵樹上完成的。而CF樹上每個(gè)節(jié)點(diǎn)又用聚類特征來(lái)進(jìn)行描述。

對(duì)于具有N個(gè)d維數(shù)據(jù)點(diǎn)的簇｛xi｝（i=1，2，…，N），它的聚類特征向量定義為：

對(duì)于聚類特征有如下定理：

假設(shè)CF1=（N1，LS1，SS1）與CF2=（N2，LS2，SS2）分別為兩個(gè)類的聚類特征，合并后的新類特征為

CF樹是一棵平衡樹，樹的寬度由分支節(jié)點(diǎn)中最大子節(jié)點(diǎn)數(shù)決定，每個(gè)子節(jié)點(diǎn)都有與之相應(yīng)的一個(gè)三元組（聚類特征向量）。各子節(jié)點(diǎn)的三元組都被包含在父節(jié)點(diǎn)中，每個(gè)葉節(jié)點(diǎn)也都表示一個(gè)簇，為了控制樹的規(guī)模大小，每個(gè)葉節(jié)點(diǎn)每個(gè)葉節(jié)點(diǎn)對(duì)應(yīng)一個(gè)閾值T，閾值代表允許的最大直徑。也就是簇中任意兩節(jié)點(diǎn)間距離的均方根。葉節(jié)點(diǎn)所代表的簇都不能超過(guò)給定的閾值。

在聚類的過(guò)程中BIRCH算法自上而下掃描CF樹，掃描過(guò)程中，所有子節(jié)點(diǎn)簇的三元組信息都保存在父節(jié)點(diǎn)中。在每個(gè)節(jié)點(diǎn)逐個(gè)被插入到CF樹中的過(guò)程中，逐漸構(gòu)造出CF樹。為了控制樹的規(guī)模，如果葉節(jié)點(diǎn)超過(guò)閾值，則把新節(jié)點(diǎn)作為單獨(dú)的簇來(lái)處理。控制樹的規(guī)模最主要的目的是使其適應(yīng)主存的規(guī)模，為的就是在執(zhí)行整個(gè)聚類過(guò)程中數(shù)據(jù)不用二次讀入。具體算法核心骨架如下：

BIRCH算法

輸入：閾值T，數(shù)據(jù)集（x1，…，xn）

輸出：類別n for i=1，i從1到n

將xi插入與其最近的一個(gè)葉節(jié)點(diǎn)中；if插入后的簇小于或等于閾值

將xi插入到該葉節(jié)點(diǎn)，并且重新調(diào)整從根到此葉節(jié)點(diǎn)路徑上的所有三元組；elseif插入后節(jié)點(diǎn)中有剩余空間

把xi作為一個(gè)單獨(dú)的簇插入并且重新調(diào)整從根到此葉節(jié)點(diǎn)路徑上的所有三元組；else

分裂該節(jié)點(diǎn)并調(diào)整從根到此葉節(jié)點(diǎn)路徑上的所有三元組

2　改進(jìn)的BIRCH聚類方法

本文提出的基于極值特征的雷達(dá)偵察數(shù)據(jù)BIRCH聚類方法，將雷達(dá)信號(hào)偵察數(shù)據(jù)的脈沖載頻、脈沖重復(fù)間隔和脈沖寬度分別進(jìn)行聚類，根據(jù)工程應(yīng)用中各參數(shù)量測(cè)誤差和系統(tǒng)誤差設(shè)定閾值T，并且將離線處理后的聚類特征模型用于實(shí)時(shí)雷達(dá)信號(hào)偵察數(shù)據(jù)聚類。

該方法類似于BIRCH算法，聚類的過(guò)程也是在一棵CF特征樹上完成的，但本方法的CF特征值卻不同于BIRCH算法的CF特征值，其表示如下：

其中N為簇中點(diǎn)的個(gè)數(shù)；LS表示N個(gè)點(diǎn)的線性和；Dmin是簇中數(shù)值最小的元素；Dmax是簇中數(shù)值最大的元素。

類似于 BIRCH算法，假設(shè)：CF1=（N1，LS1，Dmin1，Dmax1）與CF2=（N2，LS2，Dmin2，Dmax2）分別為兩個(gè)類的聚類特征，合并后的新類特征為：

其中 Dmin=min（Dmin1，Dmin2）；Dmax=max（Dmax1，Dmax2）。

基于極值特征的海量數(shù)據(jù)層次聚類方法需要在有限的可用內(nèi)存及計(jì)算機(jī)資源約束條件下，只需一次掃描數(shù)據(jù)集就能動(dòng)態(tài)地、遞增地對(duì)海量雷達(dá)數(shù)據(jù)進(jìn)行聚類，其中CF樹的建立過(guò)程如圖1所示。

圖1　CF樹結(jié)構(gòu)示意圖

1）找到距離最近的簇：從CF樹的根節(jié)點(diǎn)向下遞歸搜索，計(jì)算當(dāng)前節(jié)點(diǎn)實(shí)體與要插入數(shù)據(jù)對(duì)象之間的距離，具體如下：

設(shè)待插入數(shù)據(jù)為Data，當(dāng)前節(jié)點(diǎn)中實(shí)體的CF值為（N，LS，Dmin，Dmax），如果滿足

則數(shù)據(jù)Data沿當(dāng)前節(jié)點(diǎn)繼續(xù)向下搜索，否則計(jì)算Data 與CF的距離

其中abs為取絕對(duì)值操作。如果Data與某一節(jié)點(diǎn)的所有子節(jié)點(diǎn)的CF特征值均不滿足式（5）的條件，則運(yùn)用式（6）分別計(jì)算Data與各個(gè)子節(jié)點(diǎn)之間的距離，然后數(shù)據(jù)沿著最小距離的子節(jié)點(diǎn)繼續(xù)向下搜索，直到搜索到距離數(shù)據(jù)Data最近的簇。

2）計(jì)算當(dāng)前簇與數(shù)據(jù)Data之間的關(guān)系，若Data與簇的聚類特征值CF之間滿足式（5）的關(guān)系，則當(dāng)前簇直接吸收該數(shù)據(jù)；若不滿足式（5），則計(jì)算Data與當(dāng)前簇中心（也叫簇的質(zhì)心）之間的距離，簇的中心表示為：

數(shù)據(jù)與簇中心的距離定義為：

如果距離D小于閾值T，則當(dāng)前簇吸收該數(shù)據(jù)為其新元素，并按照式（4）依次向上更新相關(guān)節(jié)點(diǎn)。若距離D大于閾值T，則需要轉(zhuǎn)到第3步。

閾值T的選擇往往需要根據(jù)數(shù)據(jù)的特點(diǎn)或是經(jīng)驗(yàn)來(lái)決定，由于脈沖載頻、脈沖重復(fù)間隔和脈沖寬度具有不同的精度和置信度，因此在聚類過(guò)程中，結(jié)合工程應(yīng)用分別選用不同的閾值進(jìn)行聚類。

3）判讀當(dāng)前簇所在的葉節(jié)點(diǎn)的子女個(gè)數(shù)是否小于等于L，如果是則直接將該數(shù)據(jù)Data作為一個(gè)新簇插入到當(dāng)前葉節(jié)點(diǎn)下，否則需要分裂該葉節(jié)點(diǎn)。設(shè)定葉節(jié)點(diǎn)所能攜帶的最大簇的數(shù)量為L(zhǎng)是為了能夠?qū)π聰?shù)據(jù)進(jìn)行快速的搜索和插入，從而建立起具有層次的CF樹。

分裂的原則是尋找該葉節(jié)點(diǎn)中距離最遠(yuǎn)的兩個(gè)簇，并以這兩個(gè)簇作為分裂后新的兩個(gè)葉節(jié)點(diǎn)的起始簇，其他剩下的簇根據(jù)距離最小原則分配到這兩個(gè)新的葉節(jié)點(diǎn)中，刪除原葉節(jié)點(diǎn)并更新整棵CF樹。節(jié)點(diǎn)分裂的示意圖如圖2所示。

圖2　葉節(jié)點(diǎn)分裂示意圖

在計(jì)算機(jī)資源及處理時(shí)間允許的條件下，可以通過(guò)迭代來(lái)提升聚類的精確程度。

3　數(shù)值分析

為了驗(yàn)證本文方法的有效性，在JAVA環(huán)境下進(jìn)行編程試驗(yàn)并數(shù)值分析，采用真實(shí)雷達(dá)信號(hào)偵察數(shù)據(jù)作為數(shù)據(jù)源，分別運(yùn)用傳統(tǒng)BIRCH算法和本文方法進(jìn)行聚類，并對(duì)結(jié)果進(jìn)行對(duì)比分析。采用SSQ（Sum of Square Distance）來(lái)評(píng)估聚類的效果，它通過(guò)計(jì)算所有數(shù)據(jù)點(diǎn)到各自的聚類中心的距離來(lái)衡量算法所給出的聚類的質(zhì)量。SSQ越小，說(shuō)明聚類質(zhì)量越好。SSQ的計(jì)算方法如下：

其中，M表示聚類產(chǎn)生的簇?cái)?shù)量；Nj表示第j類的數(shù)據(jù)個(gè)數(shù)；cj表示第j類的質(zhì)心；xji表示屬于第j類的第i個(gè)數(shù)據(jù)。

通過(guò)仿真，得到了BIRCH算法與本文方法的對(duì)比結(jié)果如圖3、圖4和表1所示。

從圖3與圖4可以看出，對(duì)雷達(dá)數(shù)據(jù)的脈沖載頻進(jìn)行聚類時(shí)，在BIRCH方法中，相同或接近的數(shù)據(jù)會(huì)因?yàn)樽x取的順序不同而有可能被分為不同的類別，從而導(dǎo)致聚類的錯(cuò)誤發(fā)生，同樣在脈沖重復(fù)間隔和脈沖寬度的聚類中也會(huì)出現(xiàn)類似情況，而本文提出的基于極值特征的雷達(dá)偵察數(shù)據(jù)BIRCH聚類方法，因采用了簇中最大最小值作為聚類特征，有效避免了該類錯(cuò)誤的出現(xiàn)。從表1看出，無(wú)論是雷達(dá)偵察信號(hào)的脈沖載頻、脈沖重復(fù)間隔還是脈沖寬度，本文方法的聚類SSQ均小于BIRCH算法的聚類SSQ值，這說(shuō)明本文方法的聚類質(zhì)量較BIRCH算法更加優(yōu)良，更能反映數(shù)據(jù)的真實(shí)情況，為后續(xù)的數(shù)據(jù)及情報(bào)挖掘提供了真實(shí)可靠的理論依據(jù)。

圖3　BIRCH方法對(duì)脈沖載頻聚類部分結(jié)果

圖4　本文方法對(duì)脈沖載頻聚類部分結(jié)果

表1　聚類結(jié)果SSQ對(duì)比

4　結(jié)束語(yǔ)

本文提出了基于極值特征的雷達(dá)偵察數(shù)據(jù)BIRCH聚類方法，該方法在傳統(tǒng)BIRCH算法基礎(chǔ)上，將簇的最大最小值作為獨(dú)立的聚類特征，并優(yōu)化了距離度量方法和搜索策略。仿真結(jié)果表明，本文方法不但有效改善傳統(tǒng)BIRCH算法因?yàn)閿?shù)據(jù)讀取順序造成的錯(cuò)分問(wèn)題，還提高了雷達(dá)信號(hào)偵察數(shù)據(jù)的聚類質(zhì)量，在雷達(dá)偵察信號(hào)的脈沖載頻、脈沖重復(fù)間隔還是脈沖寬度聚類上SSQ值均小于傳統(tǒng)BIRCH算法。本文方法已在相關(guān)工程設(shè)計(jì)中應(yīng)用，并在時(shí)效性和計(jì)算資源上能夠較好滿足工程需求，具有重要的應(yīng)用價(jià)值。

［1］HAN J，KAMBER M.數(shù)據(jù)挖掘概念與技術(shù)［M］.范明，孟小峰，譯.北京：機(jī)械工業(yè)出版社，2006.

［2］王實(shí)，高文.數(shù)據(jù)挖掘中的聚類方法［J］.計(jì)算機(jī)科學(xué)，2000，27（4）：42-45.

［3］單世民，于紅，張業(yè)嘉誠(chéng)，等.基于最近共享鄰居節(jié)點(diǎn)的K-means聚類算法［J］.計(jì)算機(jī)工程與應(yīng)用，2008，44（6）：178-181.

［4］Krishma K，Murty M N.Genetic k-means algorithm［J］.-IEEE Transon System：Man，and Cybernetics，Part B，1999，9（3）：433-439.

［5］JARVISR A，PATRICK E A.Clustering using a similarity measure based on shared nearest neighbors［J］.IEEE Trans on Computers：1973，22（11）：1025-1034.

［6］Zhang T，Ramakrishnan R，Livny M.BIRCH：An efficient data clustering method for very large databases［C］//In：Proc. ACM SIGMOD Conf.Management of Data.Montreal，1996：103-114.

［7］張蓉，鐘艷.基于BIRCH算法的模糊集數(shù)據(jù)庫(kù)挖掘算法［J］.科技通報(bào)，2014，30（4）：47-49.

［8］丁光華.基于BIRCH和GAD的譜聚類算法研究［D］.廣州：暨南大學(xué)，2010.

［9］李磊.基于新浪微博的熱點(diǎn)話題發(fā)現(xiàn)系統(tǒng)研究與實(shí)現(xiàn)［D］.上海：復(fù)旦大學(xué)，2013.

［10］李曉嫻.微博熱點(diǎn)話題發(fā)現(xiàn)的研究［D］.北京：北京交通大學(xué)，2014.

［11］王旭.漢語(yǔ)學(xué)習(xí)平臺(tái)中基于BIRCH聚類的用戶個(gè)人信息分組算法研究［D］.長(zhǎng)春：吉林大學(xué)，2011.

［12］吳春瓊.基于聚類型BIRCH算法進(jìn)行數(shù)據(jù)挖掘的入侵檢測(cè)模型設(shè)計(jì)與實(shí)現(xiàn)［J］.科技通報(bào)，2013，29（8）：136-138.

［13］仰孝富.基于BIRCH改進(jìn)算法的文本聚類研究［D］.北京：北京林業(yè)大學(xué)，2013.

［14］周迎春，路嘉偉.一種改進(jìn)的BIRCH聚類分析算法及其應(yīng)用研究［J］.湛江師范學(xué)院學(xué)報(bào)，2009，30（3）：83-87.

［15］楊敏煜.基于改進(jìn)聚類算法的數(shù)據(jù)挖掘系統(tǒng)的研究與實(shí)現(xiàn)［D］.成都：電子科技大學(xué)，2012.

An improved BIRCH clustering method for radar reconnaissance data based on extremum features

ZHANG Yu
（Southwest China Institute of Electronic Technology，Chengdu 610036，China）

In order to solve the problem that traditional BIRCH clustering algorithms are sensitive to the data input order with unstable clustering results，an improved BIRCH clustering algorithm is proposed.In this method，the RF，PRI and PW values of radar reconnaissance data are clustered as three separate parameters.In engineering application，different threshold is set according to the parameter measurement error and system error.The maximum and minimum of clusters are used as clustering features to construct the clustering feature model by using hierarchical tree method.The searching and clustering for radar reconnaissance data can be quickly achieved.Experimental results show that the proposed method is feasible and effective.

radar reconnaissance data；PDW；BIRCH；extremum features；hierarchical clustering

TN95

A

1674－6236（2016）09-0015-04

2015-12-28稿件編號(hào)：201512288

973國(guó)家安全重大基礎(chǔ)研究項(xiàng)目（613181）

張 宇（1981—），男，河北魏縣人，碩士，工程師。研究方向：數(shù)據(jù)挖掘與數(shù)據(jù)處理。