基于K－Means算法的雷達(dá)信號預(yù)分選方法

聶曉偉

(西安電子科技大學(xué) 電子信息攻防對抗與仿真技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，陜西 西安710071)

隨著現(xiàn)代高科技的發(fā)展，空間中的電磁信號越發(fā)復(fù)雜多變，密集程度也逐漸增高，其主要表現(xiàn)為空間輻射源的數(shù)量多、密度大、信號調(diào)制復(fù)雜，且分布較廣泛，同時(shí)信號交錯(cuò)嚴(yán)重，這使得雷達(dá)輻射源的分選工作變得困難，而雷達(dá)輻射源分選在電子戰(zhàn)中扮演著非常重要的角色［1］，傳統(tǒng)的分選方法面對日益復(fù)雜的電磁環(huán)境顯得束手無策，因此對高密集復(fù)雜雷達(dá)信號實(shí)時(shí)有效的分選是當(dāng)前雷達(dá)偵查系統(tǒng)需要解決的關(guān)鍵問題。

通常雷達(dá)信號分選由信號預(yù)分選、主分選和綜合分析處理3部分組成［2］，雷達(dá)信號預(yù)分選的主要目的是降低處理信號的密度，以便于主分選處理。文獻(xiàn)［3～4］提出了K－Means(K－均值)聚類算法，該算法簡單有效，但對聚類個(gè)數(shù)以及聚類中心的初始設(shè)定依賴性過大，且對噪聲和孤立點(diǎn)較敏感。文中首先分析了傳統(tǒng)K－Means算法的局限性，針對傳統(tǒng)算法在雷達(dá)信號預(yù)分選中的不足，提出了一種在雷達(dá)信號預(yù)分選前對數(shù)據(jù)進(jìn)行噪聲和孤立點(diǎn)的去除，再用改進(jìn)的K－Means進(jìn)行聚類的方法，通過仿真實(shí)驗(yàn)證明該方法的可行性和有效性。

1 傳統(tǒng)K－Means聚類方法及其局限性

聚類分析［5］將數(shù)據(jù)劃分成有意義或有用的簇，將數(shù)據(jù)對象分組，其目標(biāo)是組內(nèi)對象且相互之間是相似的，而不同組中的對象則不同，其是根據(jù)最大化類內(nèi)的相似性、最小化類間的相似性原則對數(shù)據(jù)對象進(jìn)行分組。其結(jié)果是，每個(gè)由數(shù)據(jù)對象組成的簇，各簇內(nèi)對象之間具有較高的相似性，而簇間的對象則不相似或低相似性。組內(nèi)的相似性越大，組間差別越大，而聚類越好。將聚類的思想引入到雷達(dá)信號分選中，即將接收機(jī)所接收到的雷達(dá)信號參數(shù)作為待分選的數(shù)據(jù)，利用脈沖信號的各維參數(shù)，將不同輻射源的信號聚集為不同的類，盡可能地將同一輻射源的PDW(脈沖描述字)聚集為一類，從而達(dá)到分選的目的。

J.B.MacQueen在1967年提出的K－Means算法到目前為止是用于科學(xué)和工業(yè)應(yīng)用中諸多聚類算法的一種極具影響的技術(shù)。其有快速收斂、計(jì)算簡單、分類迅速及占用計(jì)算機(jī)內(nèi)存小的優(yōu)點(diǎn)，傳統(tǒng)K－Means算法以誤差平方和準(zhǔn)則函數(shù)作為聚類的結(jié)果函數(shù)，誤差平方和準(zhǔn)則函數(shù)定義為

式(1)中的JC表示誤差平方和，式(2)中mj，j=1，2，…，c，是聚類類型xj中所含樣本的平均值，表示c個(gè)聚類的中心。在樣本集x給定的情況下，JC的大小取決于c個(gè)聚類中心的值。當(dāng)n個(gè)樣本聚類為c類時(shí)，JC表示聚類時(shí)總的本樣誤差平方和。JC的大小，表明誤差的大小，誤差越大，說明聚類的結(jié)果越差，因此應(yīng)尋求使JC最小的聚類結(jié)果，即在誤差平方和準(zhǔn)則下的最優(yōu)結(jié)果。

K－Means算法的工作原理［6］:根據(jù)輸入的參數(shù)k，將數(shù)據(jù)集劃分為k個(gè)簇，首先在樣本數(shù)據(jù)集中隨機(jī)選取k個(gè)數(shù)據(jù)點(diǎn)作為初始聚類的中心，再將各樣本點(diǎn)到每個(gè)聚類中心的歐式距離算出，并選擇距離最近的某一聚類中心，將樣本歸并到該聚類中心所在的類。最終在新形成的所有聚類中，計(jì)算各自所含數(shù)據(jù)對象的平均值，即為新聚類的中心。若在相鄰的兩次聚類中，發(fā)現(xiàn)各聚類中心均無任何變化，則說明樣本調(diào)整結(jié)束，聚類準(zhǔn)則函數(shù)JC已收斂。

K－Means算法屬于動(dòng)態(tài)聚類算法，其迭代過程采用按批修改的方法，在每次迭代的過程中，均要考察所有樣本分類的正確性，若調(diào)整不正確，當(dāng)一次迭代完畢，即全部樣本點(diǎn)均調(diào)整完后，再修改各自聚類的中心，進(jìn)行下次迭代，若在某一次迭代中，所有的樣本點(diǎn)均能被正確分類，則無需調(diào)整樣本，聚類中心也不會出現(xiàn)任何變化，此時(shí)意味著JC已收斂［7］，算法結(jié)束。

K－Means算法的缺點(diǎn)［8］從以下幾方面給出:(1)KMeans算法中聚類結(jié)果依賴于聚類個(gè)數(shù)k的初始設(shè)定，但k值的選定通常是需經(jīng)過多次試驗(yàn)才能得到的最佳結(jié)果。(2)K－Means算法初始聚類中心是隨機(jī)選取的，由于初始選取點(diǎn)的不同，可能會出現(xiàn)不同的聚類結(jié)果，而導(dǎo)致聚類結(jié)果的不穩(wěn)定性，且容易陷入局部最優(yōu)聚類。(3)K－Means算法中聚類結(jié)果對噪聲點(diǎn)和孤立點(diǎn)過于敏感，因采用同一個(gè)聚類中所有對象的平均值作為聚類中心，所以算法的效果受到噪聲和孤立點(diǎn)的影響較大。(4)K－Means算法通常采用基于歐式距離以衡量其之間的相似度，而大值的屬性時(shí)常會左右樣本間的距離，因此該算法有可能出現(xiàn)將大的聚類進(jìn)一步分割的現(xiàn)象，不適用于有大值屬性存在的數(shù)據(jù)集。

2 距離法移除及改進(jìn)K－Means算法

針對K－Means算法效果對噪聲和孤立點(diǎn)依賴性過大的特點(diǎn)，文中在進(jìn)行K－Means算法前，先進(jìn)行孤立點(diǎn)的去除。孤立點(diǎn)是指在數(shù)據(jù)集合中與過多數(shù)數(shù)據(jù)相比，有顯著差異或特征不一致的數(shù)據(jù)。而其的產(chǎn)生，可能不是由隨機(jī)偏差造成的，而是因測量、執(zhí)行的錯(cuò)誤以及固有數(shù)據(jù)的變異等其他原因。總之其與數(shù)據(jù)集中的多數(shù)數(shù)據(jù)不一致，由于孤立點(diǎn)或噪聲點(diǎn)對K－Means聚類算法的結(jié)果影響過大，所以需減少孤立點(diǎn)或噪聲點(diǎn)，從而有效提高K－Means算法聚類的準(zhǔn)確性和結(jié)果的質(zhì)量，使用距離法對孤立點(diǎn)或噪聲點(diǎn)進(jìn)行排除，基于距離法［9］移除孤立點(diǎn)的過程為:

首先掃描待分選數(shù)據(jù)集中的所有數(shù)據(jù)，計(jì)算數(shù)據(jù)集中所有對象Xi與Xj之間的距離di，j，在此使用歐式距離

分析式(4)比較每個(gè)數(shù)據(jù)與其他所有對象的累加距離和，假設(shè)某個(gè)數(shù)據(jù)與其他所有對象的累加距離和pi比距離和均值h大，則將該點(diǎn)視為孤立點(diǎn)，并將該對象點(diǎn)從數(shù)據(jù)對象集中移除至孤立點(diǎn)集合中，重復(fù)以上做法直到所有孤立點(diǎn)均被找到并從原數(shù)據(jù)集中移除，最后得到新的數(shù)據(jù)集便是聚類的初始數(shù)據(jù)集合。

由于傳統(tǒng)K－Means算法的聚類個(gè)數(shù)以及初始的聚類中心需提前設(shè)定，且初始的聚類個(gè)數(shù)和聚類中心對其結(jié)果影響過大，傳統(tǒng)算法中需計(jì)算每個(gè)樣本點(diǎn)到聚類中心的距離，還需計(jì)算總誤差和;而改進(jìn)的KMeans聚類算法是利用數(shù)據(jù)點(diǎn)與聚類中心值作比較，以是否在誤差范圍內(nèi)作為判斷標(biāo)準(zhǔn)進(jìn)行分類，不計(jì)算數(shù)據(jù)點(diǎn)到每個(gè)聚類中心的距離，而是將數(shù)據(jù)集中的數(shù)據(jù)與聚類中心值進(jìn)行比較，若在誤差范圍內(nèi)，則將該數(shù)據(jù)分到該聚類中心所在的聚類中，并重新計(jì)算該聚類的聚類中心值(平均值)，若不在誤差范圍內(nèi)，且與其他所有的聚類中心均已比較，仍未找到合適的聚類，則將該數(shù)據(jù)作為新的聚類中心值，建立一個(gè)新的聚類類別。

3 雷達(dá)信號預(yù)分選

將改進(jìn)的K－Means聚類算法應(yīng)用于雷達(dá)脈沖信號的預(yù)分選中，是將所接收到的雷達(dá)信號數(shù)據(jù)作為待分選數(shù)據(jù)集，在雷達(dá)信號參數(shù)中，DOA是最穩(wěn)定的參數(shù)［10］，一般用于預(yù)分選的雷達(dá)信號參數(shù)是DOA(來波方向)、PW(脈沖寬度)、RF(載頻)，因此文中將采用3者的聯(lián)合分選。針對雷達(dá)信號的特點(diǎn)，首先對雷達(dá)信號數(shù)據(jù)集進(jìn)行預(yù)篩選，去除多數(shù)噪聲點(diǎn)和孤立點(diǎn)，然后再使用改進(jìn)的K－means算法進(jìn)行聚類分選，算法具體步驟如下:

(1)為保證雷達(dá)信號聚類的合理性，要使雷達(dá)信號數(shù)據(jù)集的各維參數(shù)值處在同一個(gè)數(shù)量級，即對雷達(dá)信號數(shù)據(jù)集中所有的參數(shù)進(jìn)行歸一化處理，此處將數(shù)據(jù)集內(nèi)的各個(gè)維數(shù)映射到［0，1］區(qū)間內(nèi)，數(shù)據(jù)集中最大值對應(yīng)1，最小值對應(yīng)0。

(2)由于孤立點(diǎn)對K－Means聚類算法的聚類結(jié)果影響較大，所以有必要進(jìn)行數(shù)據(jù)集的預(yù)篩選。在此采用距離和移除法進(jìn)行，并分別對歸一化后的DOA、PW和RF使用這2種方法，盡量踢除各維數(shù)據(jù)集中的孤立點(diǎn)。

(3)針對以上兩步處理之后的數(shù)據(jù)集，使用改進(jìn)的K－Means聚類算法。讀入DOA、PW和RF三維數(shù)據(jù)集。

(4)將DOA、PW和RF三維數(shù)據(jù)集中的第一個(gè)數(shù)據(jù)作為第一聚類的中心值。

(5)讀取數(shù)據(jù)集中的下一個(gè)數(shù)據(jù)，并與第一個(gè)聚類的中心值進(jìn)行比較，并計(jì)算誤差。若超出誤差范圍，則挑轉(zhuǎn)至步驟(6);若在誤差范圍內(nèi)則匹配成功，即將該數(shù)據(jù)歸并到該聚類中心值所在的聚類中，并且要重新計(jì)算該聚類的中心值，因此采用聚類的平均值代替聚類的中心值，計(jì)算得出中心值之后，讀取數(shù)據(jù)集中的下一個(gè)數(shù)據(jù)，繼續(xù)進(jìn)行比較。

(6)假如未匹配成功，則判斷是否已與所有的聚類中心值進(jìn)行了比較，若沒有，則繼續(xù)與下一個(gè)聚類中心值進(jìn)行比較，直到和所有的聚類中心值均比較后仍未匹配上，則將該聚類類別新建增加一類，以此作為新的聚類中心值。

(7)判斷數(shù)據(jù)集中的數(shù)據(jù)是否進(jìn)行了分類，若沒有，則跳轉(zhuǎn)至步驟(5)，否則算法結(jié)束。

4 仿真實(shí)驗(yàn)及分析

將通過試驗(yàn)驗(yàn)證文中所提算法的性能，模擬空間5部常規(guī)雷達(dá)輻射源，模擬接收機(jī)接收空間脈沖信號，并通過編程按到達(dá)時(shí)間順序形成交錯(cuò)的脈沖列，對同時(shí)到達(dá)的信號進(jìn)行脈沖丟失處理，選取時(shí)間約4 ms的脈沖段做仿真，共422個(gè)數(shù)據(jù)，其中有362個(gè)真實(shí)的雷達(dá)脈沖信號，60個(gè)噪聲及孤立點(diǎn)。對5部輻射源的PW和RF做5%的隨機(jī)抖動(dòng)，仿真實(shí)驗(yàn)選取PW、RF和DOA作為聚類分選的參數(shù)，同時(shí)選用的5個(gè)輻射源參數(shù)如表1所示。

表1 輻射源類型及其參數(shù)

由于空間中的雷達(dá)信號較為復(fù)雜，不同參數(shù)的數(shù)據(jù)不在同一數(shù)量級上，為了消除原始數(shù)據(jù)對分選產(chǎn)生的影響，對接收到的數(shù)據(jù)進(jìn)行歸一化處理。以下的仿真圖中對數(shù)據(jù)統(tǒng)一進(jìn)行了歸一化處理。

在實(shí)驗(yàn)中產(chǎn)生的422個(gè)信號用圖1中帶“*”的點(diǎn)表示，每一個(gè)“*”的三維信息對應(yīng)著脈寬、頻率和到達(dá)方向角。圖2表示分選出的第一類輻射源信號，有56個(gè)脈沖信號;圖3表示分選出的第二類輻射源信號，有62個(gè)脈沖信號;圖4表示分選出的第三類輻射源信號，有73個(gè)脈沖信號;圖5表示分選出的第四類輻射源信號，有72個(gè)脈沖信號;圖6表示分選出的第五類輻射源信號，有107個(gè)脈沖信號。圖7表示分選出的各輻射源所包含的脈沖個(gè)數(shù)。

圖1 待分選的雷達(dá)信號

圖2 K－means算法分選出的第一類雷達(dá)信號

圖3 K－means算法分選出的第二類雷達(dá)信號

圖4 K－means算法分選出的第三類雷達(dá)信號

圖5 K－means算法分選出的第四類雷達(dá)信號

圖6 K－means算法分選出的第五類雷達(dá)信號

圖7 分選出各部雷達(dá)的脈沖個(gè)數(shù)

由仿真結(jié)果可見，該算法大幅降低了傳統(tǒng)KMeans算法對噪聲及孤立點(diǎn)的敏感度，其分選效果穩(wěn)定可靠，對常規(guī)雷達(dá)信號有著較高的正確率。即便是在有30%的噪聲及孤立點(diǎn)的環(huán)境下，分選的正確率也同樣較高。但同時(shí)該算法也仍存在不足，當(dāng)噪聲干擾與真實(shí)脈沖信號較近時(shí)，該算法難以去除噪聲干擾。

［1］ 李合生，韓宇，蔡英武，等.雷達(dá)信號分選關(guān)鍵技術(shù)研究綜述［J］.系統(tǒng)工程與電子技術(shù)，2005，27(12):2036－2039.

［2］ 劉連柱，苗秀梅.雷達(dá)信號分選、處理方法研究［J］.電子對抗，2006，107(2):36－39.

［3］JOSHUA Z H，MICHAEL K N，RONG Hongqiang，et al.Automated variable weighting in k－means type clustering［J］.IEEE Transaction on Pattern Analysis and Machine Intelligence，2005，27(5):657－668.

［4］KRISHNA K，MURTY M N.Genetic k－means algoritym systems［J］.IEEE Transactions on Man and Cybernetics:Part B，1999(5):433－439.

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

［6］ASOKAN N，SHOUP V，WAIDNER M.Asynchronous protocols for optimistic fair exchange［C］.1998 IEEE Symposium on Security and Privacy，1998:6－17.

［7］KANUNGO T，MOUNT D M，NETANYAHU N S，et al.An efficient K－Means clustering algorithm:analysis and implementation［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2002，24(7):881－892.

［8］KAUFAN L，ROUSSEEUW P J.Finding groups in data:an introduction to cluster analysis［M］.New York:John Wiley＆Sons，1990.

［9］ 陸聲鏈，林士敏.基于距離的孤立點(diǎn)檢測研究［J］.計(jì)算機(jī)與應(yīng)用，2004，33(6):73－75.

［10］胡來招.雷達(dá)偵察接收機(jī)設(shè)計(jì)［M］.北京:國防工業(yè)出版社，2000.