一種改進的數(shù)據(jù)場和決策圖聯(lián)合聚類算法

陳濤，高鵬成

哈爾濱工程大學 信息與通信工程學院，黑龍江 哈爾濱 150001

在不斷改變的戰(zhàn)爭形式中，信息化戰(zhàn)爭已取代傳統(tǒng)戰(zhàn)爭形式成為當今戰(zhàn)爭的主流形式[1]。雷達信號分選是電子偵察的一個重要的環(huán)節(jié)，信號分選的成功與否成為電子戰(zhàn)發(fā)揮作用的標志，甚至會影響戰(zhàn)爭的最終格局[2]。但是伴隨科學技術(shù)水平的發(fā)展和提高，雷達信號分選面臨的電磁環(huán)境越來越復雜多變，雷達數(shù)量和類型層出不窮，雷達信號錯綜復雜交疊，雜波干擾等問題。因此，如何對復雜多變的電磁環(huán)境中的錯綜交疊的脈沖信號進行精確和快速的分選，是當今雷達信號分選的重點和難點。

為了處理復雜電磁環(huán)境的雷達信號分選，趙貴喜等[3]將數(shù)據(jù)場引入雷達信號分選的領(lǐng)域，將數(shù)據(jù)場和K-means 進行聯(lián)合實現(xiàn)聚類，為雷達信號分選提供新的思路；徐賽等[4]將樣本熵作為特征參數(shù)進行分選，也取得了不錯的成果；Brendan J. Frey 等[5]基于仿射思想提出了一種新的聚類算法，沙作金[6]將數(shù)據(jù)場結(jié)合平面變換技術(shù)實現(xiàn)了復雜電磁環(huán)境下的雷達信號分選。

現(xiàn)代電子偵察設(shè)備每秒能夠接收到百萬個脈沖信號，這些脈沖信號互相錯雜、密集分布，直接應用于雷達信號分選會導致信號處理工作量大，浪費大量的時間，降低時效性。故而，需要對脈沖信號進行預分選處理，降低脈沖信號的密度。聚類是利用數(shù)據(jù)對象之間的相關(guān)性，可以作為預處理步驟，達到降低信號密度的目的。但是傳統(tǒng)的如K-means 聚類算法，需要人為預先設(shè)置具體的參數(shù)信息[7]，且對噪聲點敏感，聚類的質(zhì)量受到初始人為設(shè)置參數(shù)信息的影響。為此，本文提出一種基于數(shù)據(jù)場和決策圖的聚類算法。數(shù)據(jù)場主要通過計算數(shù)據(jù)對象的場強函數(shù)值累加形成勢值，利用勢值可以清楚快捷地識別孤立的噪聲點。數(shù)據(jù)場聚類是利用勢值的極值確定聚類中心和聚類數(shù)目，決策圖是依據(jù)數(shù)據(jù)對象的局部密度參數(shù)值和到最近大密度點的距離值來確定聚類中心和聚類數(shù)目。由于數(shù)據(jù)場尋極值的步驟繁瑣以及決策圖對噪聲點敏感，故將數(shù)據(jù)場和決策圖做了不同程度的改進，并將兩者進行聯(lián)合聚類，按照數(shù)據(jù)對象的勢值和到最近大密度點的距離實現(xiàn)聚類。

1 數(shù)據(jù)場

“場”的概念最初是用來描述物質(zhì)對象之間的作用力，受到場論思想的啟發(fā)，李德毅院士將物理作用力引入到數(shù)據(jù)處理領(lǐng)域，創(chuàng)造性地提出數(shù)據(jù)場的概念。數(shù)據(jù)場理論認為每一個數(shù)據(jù)對象的狀態(tài)值都是場中其他所有數(shù)據(jù)對象作用力的累積。類同庫倫定律，數(shù)據(jù)對象的作用力與距離成反比，距離越遠，作用力越小；距離越近，作用力越大。所有數(shù)據(jù)對象之間的作用力和作用范圍構(gòu)建了數(shù)據(jù)場[8]。

1.1 場強函數(shù)

如萬有引力和庫侖定律，將數(shù)據(jù)場中描述數(shù)據(jù)對象之間的作用力用場強函數(shù)來表征，根據(jù)數(shù)據(jù)對象與距離的關(guān)系可以清楚地知曉，數(shù)據(jù)對象密集的地方場強函數(shù)值大，數(shù)據(jù)對象稀疏的地方場強函數(shù)值小。一般用高斯函數(shù)來描述數(shù)據(jù)對象的作用力，場強函數(shù)描述數(shù)據(jù)對象x與y點的作用力為

式中: ρ為數(shù)據(jù)點的影響能力，鑒于數(shù)據(jù)對象具備獨立性和完整性，設(shè)參數(shù)值為1；d(x,y)是數(shù)據(jù)對象x與y點之間的歐式距離[9]； σ是衡量數(shù)據(jù)對象的作用能力的輻射因子變量。

1.2 勢函數(shù)

勢函數(shù)是描述數(shù)據(jù)對象受到的場強函數(shù)的標量累加和，假設(shè)存在n個數(shù)據(jù)對象(x1,x2,···,xn)，則數(shù)據(jù)對象y受到的場強函數(shù)累加和表示為

1.3 輻射因子

輻射因子 σ是表征數(shù)據(jù)點的作用能力，由式(1)可知，場強函數(shù)值與輻射因子 σ成正比。假設(shè)只存在一個孤立的數(shù)據(jù)點，在不同輻射因子 σ的基礎(chǔ)上，勢值隨距離的關(guān)系圖如圖1 所示。

圖1 勢值隨距離關(guān)系曲線

從圖1 中可以看出，勢值隨距離呈衰減趨勢，且輻射因子 σ越小，衰減的程度越快。輻射因子σ的取值對于勢值非常關(guān)鍵，因而，如何選取最合適的輻射因子 σ成為數(shù)據(jù)場聚類的一個非常重要環(huán)節(jié)。

為了獲取最優(yōu)的輻射因子 σ，利用描述數(shù)據(jù)間分布不確定性的熵的概念。一般將在數(shù)據(jù)場表述數(shù)據(jù)對象之間的不確定性的熵用勢熵來表述。可以利用勢熵對輻射因子 σ進行優(yōu)化選擇。假設(shè)存在n個數(shù)據(jù)對象D={x1,x2,···,xn}，其相對應每個數(shù)據(jù)對象的勢值為Ψ1,Ψ2,···,Ψn，則相應的勢熵的計算公式為

由式(2)可得，0 ≤HΨ≤log(n)。當輻射因子σ參數(shù)值變得非常大時，數(shù)據(jù)場中的每個數(shù)據(jù)對象的勢值都不斷趨近相等，每個數(shù)據(jù)對象之間的分布規(guī)律混雜無序，數(shù)據(jù)對象之間不確定性達到最大，勢熵的函數(shù)值最大；當輻射因子 σ參數(shù)值變得非常小時，數(shù)據(jù)對象的分布基本有序排布，數(shù)據(jù)對象之間的不確定性達到最小，勢熵的函數(shù)值最小。當且僅當輻射因子參數(shù)值小到一定時，數(shù)據(jù)場中的每個數(shù)據(jù)對象之間可以到達動態(tài)平衡，即每個數(shù)據(jù)對象的勢值參數(shù)值都趨近相等，即Ψ1=Ψ2=···Ψn,HΨ=log(n)。

數(shù)據(jù)對象的勢熵與輻射因子的關(guān)系如圖2 所示。由圖可知勢熵與輻射因子的變化規(guī)律為，輻射因子 σ不斷增大，勢熵值先減小后增大。所以，選取最優(yōu)的輻射因子就是選擇勢熵的最小值，即

圖2 勢值與輻射因子關(guān)系

1.4 數(shù)據(jù)場的改進

對數(shù)據(jù)場進行改進就是需要對場強函數(shù)進行改進，但是基于式(1)可知，只要改進輻射因子σ和距離d(x,y)即可。在1.3 節(jié)中采用了勢熵的概念將尋找輻射因子 σ轉(zhuǎn)變?yōu)閷ふ易钚蒽兀⒗渺巢瞧醴梢缘玫阶钚蒽兀吹玫捷椛湟蜃?σ。故剩下的只需要對距離進行修改。由圖1可知數(shù)據(jù)場不同的輻射因子的作用范圍。場強函數(shù)的公式滿足高斯函數(shù)，根據(jù)高斯函數(shù)具有的“ 3σ”原則，即在±3σ區(qū)間內(nèi)包含99.73%的數(shù)據(jù)對象，標記的地方就是 3σ位置。因此，每個數(shù)據(jù)對象的輻射范圍是以自身為中心，最大輻射范圍是3σ，即數(shù)據(jù)對象只對處于半徑值 3σ內(nèi)的其他數(shù)據(jù)對象產(chǎn)生影響，對于距離處于 3σ外的數(shù)據(jù)對象之間產(chǎn)生的影響力基本忽略不計。因此，可以將場強函數(shù)的公式改進為

鑒于現(xiàn)實電磁環(huán)境中不只存在脈沖信號，還存在大量的噪聲干擾等因素，聚類的效果還會受到信號噪聲等干擾因素影響。但是噪聲點不是真實的脈沖信號，距離會超過聚類中心點的輻射范圍，即距離值大于 3σ，孤立噪聲點的勢值參數(shù)值非常接近0，改進的數(shù)據(jù)場可以使得孤立的噪聲點更加容易被識別出，從而剔除。

2 決策圖

按照目前存在的聚類算法，大多數(shù)都是基于數(shù)據(jù)對象之間的距離信息進行數(shù)據(jù)的簇類劃分處理，但是這些算法處理數(shù)據(jù)會需要大量的工作量，消耗大量的時間。2014 年，Rodriguez 等[10]在基于密度聚類算法的基礎(chǔ)上進行改進優(yōu)化，提出了一種快速簡捷的搜索聚類中心的聚類算法，并將該算法命名為密度峰值聚類算法。該算法主要是利用數(shù)據(jù)對象的局部密度值和到最近大密度點的距離形成決策圖，再在決策圖中處理參數(shù)信息得到聚類中心和聚類數(shù)目，所以該算法也被稱為決策圖聚類算法。決策圖聚類算法可以實現(xiàn)自動選擇聚類中心和聚類數(shù)目，且相較于其他聚類算法，決策圖聚類算法需要處理的步驟少，能夠快捷地得到聚類簇組，節(jié)省大量數(shù)據(jù)處理時間。

2.1 決策圖基礎(chǔ)

決策圖聚類算法可以實現(xiàn)數(shù)據(jù)對象的快速聚類，核心思想是對聚類中心或密度峰值點進行相關(guān)的理論假設(shè):1)每個數(shù)據(jù)聚類簇組中的聚類中心擁有最大的局部密度參數(shù)值，聚類簇組中其他相鄰數(shù)據(jù)點的局部密度值低于聚類中心的局部密度值[11]；2)不同數(shù)據(jù)聚類簇組的聚類中心之間有著比較遠的距離，即高局部密度的數(shù)據(jù)點分布比較遠。基于決策圖聚類算法的2 個理論假設(shè)，決策圖聚類算法引入了2 個重要的參數(shù)變量，局部密度 ρi以及數(shù)據(jù)對象到最近大密度點的距離 δi。

假設(shè)待聚類的數(shù)據(jù)對象為D={x1,x2,···,xN}，將不同數(shù)據(jù)對象xi和xj之間的歐式距離參數(shù)值設(shè)置為dij=distance(xi,xj)，則局部密度 ρi以及數(shù)據(jù)對象到最近大密度點的距離 δi對應的公式如下:

1)局部密度 ρi被定義為

式中參數(shù)dc＞0被稱為截斷距離，是衡量決策圖聚類算法的一個非常重要的參數(shù)變量，利用其參數(shù)閾值處理數(shù)據(jù)對象來得到聚類中心和聚類數(shù)目值。但是參數(shù)dc是人為選取，一般選擇原則是讓所有數(shù)據(jù)對象的局部密度值總和滿足待聚類數(shù)據(jù)對象總數(shù)N的2%:

2)最近大密度點的距離 δi被定義為

與K-modes 聚類算法類似，峰值密度聚類算法首先需要得到待聚類數(shù)據(jù)對象的聚類中心，該算法是利用 ρ和δ作為橫縱坐標形成決策圖，選擇圖中 ρ和δ都比較大的數(shù)據(jù)點對應的數(shù)據(jù)對象作為聚類中心，就是人為選擇決策圖右上方對應的數(shù)據(jù)對象為聚類中心，利用局部密度值的靠近原則將其他數(shù)據(jù)對象點劃分到不同的聚類簇組中，從而完成整個數(shù)據(jù)對象的聚類。

2.2 決策圖改進

對決策圖的改進主要就是要解決人為選擇ρmin和δmin的問題，使其能夠?qū)崿F(xiàn)自動確定所需要的聚類數(shù)目。鑒于決策圖的聚類思想是聚類中心點擁有較大的局部密度 ρ和最近大密度點的距離 δ參數(shù)值，故而可以設(shè)置變量 γ，具體的表示為

這樣可以將變量 γ作為判斷聚類中心的變量參數(shù)，且變量 γ參數(shù)值大的數(shù)據(jù)點就可以作為聚類中心點，可以通過設(shè)置閾值來獲取聚類所需要的聚類數(shù)目。具體操作是先按照每個數(shù)據(jù)對象的變量 γ值進行降序排列，再利用相鄰數(shù)據(jù)對象變量γ的比值差來判斷，當比值差小于設(shè)定的閾值時結(jié)束算法。其具體的數(shù)學表達式為

式中變量 ε作為閾值判斷值，具體參數(shù)值根據(jù)實驗需要設(shè)置。

3 數(shù)據(jù)場聯(lián)合決策圖聚類

數(shù)據(jù)場聚類所需要的步驟冗雜，需要利用勢值參數(shù)進行極值判斷來確定聚類中心和聚類數(shù)目，再來處理脈沖歸屬問題。孤立噪聲點在數(shù)據(jù)場聚類中能夠輕易地被識別剔除，決策圖聚類只需要得到變量 γ，利用排序和閾值就能夠快捷地確定聚類中心和聚類數(shù)目。但對于存在脈沖丟失和噪聲干擾的情況下，決策圖聚類的效果很差。所以，本文將數(shù)據(jù)場聯(lián)合決策圖進行數(shù)據(jù)聚類，具體的步驟如下:

1)對輸入的待聚類的雷達數(shù)據(jù)的脈寬(pulse width, PW)、射頻(radio frequency, RF)、波達方向(direction of arrival, DOA)進行歸一化處理；

2)根據(jù)DOA 參數(shù)值對待分選的脈沖信號進行排序，并計算兩兩脈沖信號之間的歐式距離形成距離矩陣；

3)利用斐波那契法計算得出最佳的輻射因子 σ；

4)利用距離矩陣和最佳的輻射因子 σ計算出勢值 φ和最近大密度點的距離δ；

5)對勢值 φ和最近大密度點的距離 δ重新進行歸一化處理，消除不同計算方式得到數(shù)據(jù)對象參數(shù)的權(quán)重問題，同時可以根據(jù)勢值的大小消除孤立的噪聲點；

6)設(shè)置變量τ=φ×δ作為判斷聚類中心的變量參數(shù)，變量 τ參數(shù)值大的數(shù)據(jù)點就是聚類中心點，并利用相鄰數(shù)據(jù)對象的變量 τ的比值差和設(shè)定的閾值來確定聚類數(shù)目；

7)對剩余的脈沖信號按照靠近原則劃分到最近的聚類中。

4 聚類算法仿真

4.1 仿真條件

本文選擇了12 部雷達輻射源信號，其中包括常規(guī)雷達信號、參差雷達信號、抖動雷達信號、脈組捷變和脈間捷變雷達信號，具體的參數(shù)信息如表1 所示，圖3 是待聚類的雷達信號。其中，設(shè)置脈寬的精度為1 μs，載頻的精度為1 MHz，方位角的精度為1°[12]。為了統(tǒng)一待聚類的數(shù)據(jù)對象之間各個參數(shù)的維度量綱，采用min-max 標準將數(shù)據(jù)對象進行歸一化處理，結(jié)果為

4.2 實驗結(jié)果與分析

實驗1為了驗證數(shù)據(jù)場聚類算法的正確性，對算法進行仿真驗證。用Matlab 模擬實際環(huán)境中的雷達信號，根據(jù)表1 的參數(shù)信息生成對應的雷達信號并進行數(shù)據(jù)場聚類，得到的聚類中心如表2 所示。

表1 雷達參數(shù)設(shè)置表

圖3 待聚類的雷達信號

表2 聚類中心參數(shù)表

實驗2利用式(1)、(4)不同的場強函數(shù)重新計算勢函數(shù)，按照數(shù)據(jù)場聚類得出每個簇組的聚類中心，并與理論值進行比較，得出不同場強函數(shù)下的聚類算法的誤差，并進行500 次蒙特卡洛實驗，對誤差處理得到方差值，圖4 是不同場強函數(shù)對應的聚類誤差圖。

仿真結(jié)果顯示改進的數(shù)據(jù)場聚類的平均誤差要比數(shù)據(jù)場聚類的誤差小，雖然誤差值沒有得到大幅度改進，但是改進的數(shù)據(jù)場聚類算法的方差值小，聚類效果穩(wěn)定，分析圖中出現(xiàn)幾次誤差遠大于平均誤差的原因是聚類數(shù)目比真實聚類數(shù)目多，造成同一組數(shù)據(jù)被分到不同的聚類簇組中，改進的數(shù)據(jù)場明顯減少了這些現(xiàn)象，同時，改進的數(shù)據(jù)場減少了運算步驟，降低時間的復雜性，加快了聚類的效果，所以改進后的數(shù)據(jù)場對數(shù)據(jù)對象聚類的效果會更加好。

圖4 數(shù)據(jù)場改進前后平均誤差對比

實驗3利用改進的決策圖聚類仿真，忽略脈沖丟失和噪聲干擾的情況下，形成圖5 基于 γ-n的數(shù)據(jù)對象聚類決策圖和圖6 基于 γ-n數(shù)據(jù)對象聚類局部放大決策圖，設(shè)置變量ε=1.15，獲得前15個聚類中心。

圖5 基于γ-n 的數(shù)據(jù)對象聚類決策

圖6 基于γ-n 數(shù)據(jù)對象聚類局部放大決策

實驗4利用改進的數(shù)據(jù)場聯(lián)合改進的決策圖進行聚類得到聚類中心，連同原數(shù)據(jù)場聚類得出的每個簇組的聚類中心，分別與理論值進行比較，得出2 種聚類算法的誤差，并進行500 次蒙特卡洛實驗，對誤差處理得到方差值，圖7 是不同聚類方式得到的聚類平均誤差對比圖。

圖7 不同聚類方式的聚類平均誤差對比

從仿真結(jié)果中可以看出，數(shù)據(jù)場聯(lián)合決策圖的聚類平均誤差比改進的數(shù)據(jù)場的聚類平均誤差小，同時對應的方差函數(shù)值也比改進的數(shù)據(jù)場小，說明數(shù)據(jù)場聯(lián)合決策圖的聚類效果更加穩(wěn)定，聚類效果更加好。而圖中改進的數(shù)據(jù)場出現(xiàn)幾次誤差遠大于平均誤差的原因是聚類數(shù)目比真實聚類數(shù)目多，造成同一組數(shù)據(jù)被分到不同的聚類簇組中，數(shù)據(jù)場聯(lián)合決策圖明顯對這種現(xiàn)象做了進一步的改進，基本上解決了這一問題。

5 結(jié)論

本文采取了一種改進的數(shù)據(jù)場和決策圖聯(lián)合聚類算法，主要是根據(jù)數(shù)據(jù)對象的勢值和到最近大密度點的距離實現(xiàn)了聚類，且取得了理想的聚類效果。

1)改進的數(shù)據(jù)場能夠更加快捷地處理孤立的噪聲點，聚類的平均誤差更加小，聚類效果更加穩(wěn)定。

2)決策圖實現(xiàn)了快速獲得聚類中心和聚類數(shù)目的效果，在無噪聲和脈沖丟失的情況下，聚類效果好。

3)數(shù)據(jù)場聯(lián)合決策圖聚類算法在能夠處理孤立噪聲點的基礎(chǔ)上，克服了決策圖對噪聲和脈沖丟失的缺陷，聯(lián)合聚類的效果更加顯著。

經(jīng)過仿真實驗表明，本文提出的聚類算法在復雜的電磁環(huán)境下能夠?qū)崿F(xiàn)聚類功能，且有很好的聚類效果。但是聯(lián)合聚類算法需要的時間復雜性更高些，聚類的時間會比數(shù)據(jù)場略多，后續(xù)需要對時間復雜性作進一步的研究，以縮短聚類的時間。