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

張 宇

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

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

張 宇

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

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

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

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

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

1　BIRCH聚類方法

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

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

對于聚類特征有如下定理：

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

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

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

BIRCH算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3　數(shù)值分析

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

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

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

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

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

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

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

4　結(jié)束語

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

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

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

［3］單世民，于紅，張業(yè)嘉誠，等.基于最近共享鄰居節(jié)點的K-means聚類算法［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ù)庫挖掘算法［J］.科技通報，2014，30（4）：47-49.

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

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

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

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

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

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

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

［15］楊敏煜.基于改進(jìn)聚類算法的數(shù)據(jù)挖掘系統(tǒng)的研究與實現(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稿件編號：201512288

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

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