一種改進的數據場和決策圖聯合聚類算法

陳濤，高鵬成

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

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

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

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

1 數據場

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

1.1 場強函數

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

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

1.2 勢函數

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

1.3 輻射因子

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

圖1 勢值隨距離關系曲線

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

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

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

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

圖2 勢值與輻射因子關系

1.4 數據場的改進

對數據場進行改進就是需要對場強函數進行改進，但是基于式(1)可知，只要改進輻射因子σ和距離d(x,y)即可。在1.3 節中采用了勢熵的概念將尋找輻射因子 σ轉變為尋找最小勢熵，并利用斐波那契法可以得到最小勢熵，即得到輻射因子 σ。故剩下的只需要對距離進行修改。由圖1可知數據場不同的輻射因子的作用范圍。場強函數的公式滿足高斯函數，根據高斯函數具有的“ 3σ”原則，即在±3σ區間內包含99.73%的數據對象，標記的地方就是 3σ位置。因此，每個數據對象的輻射范圍是以自身為中心，最大輻射范圍是3σ，即數據對象只對處于半徑值 3σ內的其他數據對象產生影響，對于距離處于 3σ外的數據對象之間產生的影響力基本忽略不計。因此，可以將場強函數的公式改進為

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

2 決策圖

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

2.1 決策圖基礎

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

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

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

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

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

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

2.2 決策圖改進

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

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

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

3 數據場聯合決策圖聚類

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

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

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

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

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

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

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

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

4 聚類算法仿真

4.1 仿真條件

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

4.2 實驗結果與分析

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

表1 雷達參數設置表

圖3 待聚類的雷達信號

表2 聚類中心參數表

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

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

圖4 數據場改進前后平均誤差對比

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

圖5 基于γ-n 的數據對象聚類決策

圖6 基于γ-n 數據對象聚類局部放大決策

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

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

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

5 結論

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

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

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

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

經過仿真實驗表明，本文提出的聚類算法在復雜的電磁環境下能夠實現聚類功能，且有很好的聚類效果。但是聯合聚類算法需要的時間復雜性更高些，聚類的時間會比數據場略多，后續需要對時間復雜性作進一步的研究，以縮短聚類的時間。