基于證據K-NN改進算法的水聲目標識別

楊　蕊　王曉燕

(西安建筑科技大學機電工程學院　陜西 西安 710055)

?

基于證據K-NN改進算法的水聲目標識別

楊蕊王曉燕

(西安建筑科技大學機電工程學院陜西 西安 710055)

證據分類算法已廣泛應用于目標識別當中。針對傳統證據K近鄰算法在近鄰證據組合規則上的局限，研究一種新的基于PCR5規則的證據K近鄰改進算法(IEK-NN)。首先在總樣本集中隨機重復采樣來構造多個訓練子集；然后在各訓練子集中，利用目標數據與其近鄰的特征距離來構造基本置信指派；最后利用證據推理中的PCR5規則對近鄰證據進行融合，并根據融合結果以及所建立的分類規則判斷目標的類別屬性。通過水聲目標實測數據實驗，將IEK-NN與傳統的證據近鄰分類算法進行對比分析，結果表明新算法能有效提高識別的準確率。

模式識別水聲目標證據推理近鄰組合規則

0　引　言

在現代海洋戰中，水聲目標的準確識別是致勝的關鍵[1,2]。目前水聲目標識別面臨兩個主要問題：一方面水聲目標類別眾多，如潛艇、水面艦艇、魚雷、商船以及各種海洋生物等[3,4]。另一方面異類水聲目標間的特征存在相似性，使得識別任務面臨很大干擾[5,6]。因此，利用智能多域信息融合理論來設計水聲目標識別系統模型，并構建可應用于不同識別任務的智能目標識別系統，是預防水下目標突襲和當代戰爭的急需。

水聲目標識別應用中，受到系統中傳感器測量精度、戰場環境噪聲等因素影響，系統會存在一定的不確定性信息[7]。而證據理論[8]可有效處理具有不確定性的信息和數據[9,10]。因此諸多學者將證據理論與一些傳統模式分類算法相結合，研究了一系列基于證據理論框架的分類算法。其最具代表的就是由Denoeux學者所提出并逐漸發展起來的證據K-NN(EK-NN)分類算法[11,12]，EK-NN算法簡單直觀、誤差率低，在目標識別應用當中備受關注。算法首先在總的訓練樣本集中根據特征距離大小選擇目標的K近鄰，并構造各近鄰的基本置信指派(bba’s)。然后使用Dempster(D-S)規則對K個近鄰的bba’s進行組合，最后根據組合結果對目標進行分類決策。EK-NN在對近鄰證據進行組合時所采用的是D-S組合規則，但D-S規則在證據“高沖突”時會出現有悖常理的結果[13]。而不同近鄰樣本由于所屬類別不盡相同，使得所構造的bba’s也會存在較大的差異，因此在近鄰證據組合時會存在一定的“高沖突”，這時融合決策就容易造成目標的誤判。

針對D-S規則在“高沖突”證據融合所存在的局限，很多學者都提出新的融合規則，其中Dezert等所研究的PCR5規則[14]對于沖突部分信息的分配最為準確。另外在模式識別中對訓練樣本集重復采樣可有效抑制噪聲影響、并提高分類的精度。因此，針對傳統EK-NN算法的局限，本文采用重復采樣的方式來構造多個訓練樣本子集，并將近鄰分類與PCR5規則相結合，研究了一種新的證據K-NN改進算法(IEK-NN)。最后通過水聲目標實測數據實驗，驗證了新算法在識別應用中的有效性。

1　PCR5組合規則

在水聲目標識別研究中，目標信號復雜、樣本獲取難度大且富含不確定信息。傳統的D-S理論可以有效處理這些不確定信息，但D-S規則在證據“高沖突”時會出現不合理的結果。而Dezert等學者所提出的五種成比例的沖突重新分配規則[14](PCR1-PCR5)，是對傳統D-S規則的擴展和完善，在對包含高沖突，高不確定性信息的證據進行融合時，有著不錯效果[14,15]。其中，PCR5組合規則對于沖突部分信息的分配最為準確，規則如下：

(1)

根據融合的bba’s：m，可計算出各命題的置信度大小，從而進行最終的決策。

2　EK-NN算法及其局限

2.1EK-NN算法

假設模式類別的集合為：C={C1,C2,…,CM}，訓練樣本集為：{(x1,L1),(x2,L2),…,(xN,LN)}。其樣本xi類別屬性的標號為Li。對于待測試樣本xs，假設Φs為從訓練集中所選擇的k近鄰樣本集合，Φs中訓練樣本xi類別屬性的標號為Li=Cq(q=1,2,…,M)，則(xi,Cq)為一個對xs進行分類的近鄰證據，可用bba’sms,i進行表示：

(2)

Φs中的近鄰樣本xi距離目標數據xs越近，所構造bba’s中的δ就要越大，Denoeux根據特征距離d的大小定義δ的形式為：

δ=αe-rqdβ

(3)

然后，使用D-S規則將Φs中各近鄰樣本的bba’sms,i組合起來，可得總的bba’s為：

(4)

最后，根據總的ms計算xs屬于各模式類別的置信度，并根據置信度大小進行最終的分類識別。

2.2EK-NN算法的局限

EK-NN算法簡單直觀、易于實現，但局限之處在于：算法對近鄰證據進行組合時采用了D-S規則，而D-S規則在證據“高沖突”時會出現有悖常理的結果。不同近鄰證據由于所屬類別不盡相同，使得所構造的bba’s會存在較大的差異，因而在證據組合時不可避免地會存在一定的“高沖突”，這時使用EK-NN算法就容易造成目標的誤判。

例如，使用EK-NN算法對待識別水聲目標xs進行分類決策時，假設ms,i和ms,j為兩個近鄰樣本所分別構造的bba’s，ms,i的置信度主要分派給類別Ci，ms,j的置信度主要分派給類別Cj。若兩近鄰樣本所屬類別不同，即Ci≠Cj，這時兩近鄰樣本所構造的bba’s就會不同，即ms,i(Ci)≠ms,j(Cj)。則導致近鄰證據存在一定的沖突，其沖突信息量的大小為：m(φ)=m(Ci∩Cj)=ms,i(Ci)ms,j(Cj),ms,i(Ci)和ms,j(Cj)的取值如果較大，沖突信息量就會很大，即兩證據ms,i、ms,j存在高沖突。這時算法使用D-S規則就易造成識別結果的誤判。接著通過例1的具體數據實例對問題進行詳盡的分析說明。

例1假設在使用EK-NN算法進行分類識別時，選取了目標數據的兩個近鄰，且所構造的近鄰證據分別如下：

近鄰證據1：m1(C1)=0.9,m1(C3)=0.1

近鄰證據2：m2(C2)=0.9,m2(C3)=0.1

首先采用EK-NN算法中的D-S規則對以上兩近鄰證據進行組合，可得：

mDS(C1)=0mDS(C2)=0mDS(C3)=1

例1中近鄰證據1確認目標屬于類別C1的置信度為0.9、屬于類別C3的置信度為0.1；近鄰證據2確認目標屬于類別C2的置信度為0.9、屬于類別C3的置信度為0.1。使用D-S規則的組合結果卻顯示目標屬于類別C1和C2的置信度都為0，而屬于類別C3的置信度卻增加到了1，即確信目標屬于類別C3。原來的近鄰證據1和2都認為目標屬于類別C3的置信度不大，只有0.1。但融合后的證據卻確信目標屬于類別C3，顯然是不合理的。原因就在于兩個近鄰證據是“高沖突”的，這時計算表征兩近鄰證據沖突量的矛盾因子k，可得：

k=m1(C1)m2(C2)+m1(C1)m2(C3)+m1(C3)m2(C2)

=0.9×0.9+0.9×0.1+0.1×0.9=0.99

D-S規則在“高沖突”近鄰證據融合時存在局限，而 PCR5組合規則對“高沖突”信息則可以進行精確合理的分配。使用PCR5規則對以上兩近鄰證據進行組合，可得：

mPCR5(C1)=0.45mPCR5(C2)=0.45mPCR5(C3)=0.1

PCR5規則的組合結果顯示，目標屬于類別C1和C2的置信度都為0.45，屬于類別C3的置信度為0.1。兩個原始近鄰證據都認為目標屬于類別C3的置信度為0.1，融合后的結果保持一致，也確認目標屬于類別C3的置信度為0.1，這是比較合理的。另外兩個原始證據分別認為目標屬于類別C1和C2的置信度是一樣的，融合結果則對置信度進行了折中，認為目標屬于C1和C2的置信度仍是相同的，而且大于C3的置信度。所以融合結果相對于D-S規則的組合結果更為合理和可信。

通過實例1中數據的具體分析可見，在近鄰證據“高沖突”時，PCR5規則會比EK-NN算中所使用的D-S規則有著更好的組合結果。

3　新的證據K-NN改進算法(IEK-NN)

針對傳統EK-NN方法的不足，在采用重復采樣方式，并結合PCR5規則和近鄰分類的基礎上，研究了一種新的證據K-NN改進算法(IEK-NN)。IEK-NN算法主要包括構造訓練樣本子集和近鄰證據、證據融合和分類決策三個核心步驟。

3.1構造訓練樣本子集和近鄰證據

選取水聲目標總的類別作為識別框架，若有M類水聲目標：C1,C2,…,CM，則識別框架為：Θ={C1,C2,…,CM}。首先建立這M類水聲目標的總樣本庫，即將已獲得的各個水聲目標的語音信號進行離散采樣和特征提取，使得每個目標的一組特征就對應著樣本庫中的一個樣本。這里選取的是由波形結構[16]、小波分析[17]以及聽覺譜[18]所構造的42維多域組合特征。

假設M類水聲目標進過以上特征提取后，得到的總訓練樣本集為：X={(x1,L1),(x2,L2),…,(xN,LN)}。其中Li為訓練樣本xi的類別標號，N為樣本的總數。

每次從總的訓練樣本集中隨機選取Nj個樣本，來構成訓練子集Xj，選取B次，得B個訓練子集：X1,X2,…,XB。

(5)

δj=e-dj

(6)

3.2證據融合

各訓練子集中樣本數目越多，其包含的類別信息越充足，構造的證據就越精確。因此，這里根據各訓練子集所包含樣本數目，來確定其近鄰證據的權重。

訓練子集的集合為Φ={(X1,N1),…,(XB,NB)}，確定擁有最多樣本數目的子集所構造的近鄰證據為關鍵證據，其權重為：

wmax=max(N1,N2,…,NB)

(7)

則各訓練子集所對應近鄰證據的“折扣因子”為：

αj=Nj/wmax

(8)

(9)

最后，應用PCR5組合規則，對以上B個訓練樣本子集對應的修正證據進行融合，可得：

(10)

ms即為最終所得的bba’s，根據其所指派的各類別置信度大小，即可對待識別水聲目標xs進行最終的分類決策。

3.3分類決策

根據最終獲得的基本置信指派ms，計算待識別目標xs屬于各個模式類別的置信度Bel(Cq)和似真度Pl(Cq)。

(11)

(12)

然后，確定如下分類規則：

規則1待識別水聲目標的所屬類別與其他類別的置信度差值必須大于某一閾值T1；

規則2待識別水聲目標所屬類別的不確定度與其置信度差值必須小于某一閾值T2。

最后，計算符合以上的分類規則的模式類別Cq，q為1到M間計算所得的某一特定取值。那么，類別Cq即被判定為待識別水聲目標所屬的類別。

以上為新算法的設計思想，其實現流程如圖1所示。

圖1　IEK-NN算法流程圖

4　實驗及結果分析

4.1實驗數據及參數設置

實驗的對象是實測水聲目標信號，其采樣頻率為48 000 Hz，把采集的每一段水聲目標信號作為一個分類樣本，其包含10 000個采樣點。對每個樣本提取了8維波形結構特征、10維小波分析特征、24維聽覺譜特征。并將以上特征進行組合，使得每個水聲目標樣本可以由42維的多域組合特征來進行表示。水聲目標分為4類，共有5000個樣本。各類別中訓練樣本、測試樣本的具體數目如表1所示。

表1　各類別訓練樣本和測試樣本的數目

本實驗中使用IEK-NN新算法時，訓練子集的參數B、Nj，以及分類決策參數T1和T2的具體設置如表2所示。

表2　IEK-NN的參數設定

其中，訓練子集的個數B和各訓練子集中樣本數Nj越大，分類時所使用的訓練樣本信息就會越充足，不過計算就會越復雜。經多次實驗驗證，在參數B的取值大于5，Nj的取值大于800后，對算法識別結果的準確度影響已經很微小，相反會極大地增加計算時間。T1越小目標的類別屬性就區分的越精確，在模式識別中通常選取為0.2。當目標數據的不確定度大于一半時，該目標是不能準確識別的，故T2選取為0.5。

4.2實驗結果及分析

分別基于波形結構、小波分析、聽覺譜的單一特征以及以上三類組合特征來進行分類實驗。為了便于結果的對比分析，在使用IEK-NN新算法的同時，也采用傳統的EK-NN算法進行相應的分類實驗，具體結果如表3所示。

表3　各算法的分類實驗結果對比

表3的實驗結果表明，不論是基于單一的波形結構特征、小波分析特征、聽覺譜特征，還是基于三類組合特征的分類實驗，新提出的IEK-NN算法在水聲目標的正確識別率上，相對于傳統EK-NN算法都有一定程度的提高。另外新算法能夠很好地對樣本的多域特征進行組合利用，因而可從表格3中看到，多域組合特征的分類正確率相對單一特征的識別也都有了很大的提高，這時新算法的識別正確率可以高達97%，相對于傳統EK-NN算法的92%，可以高出5個百分點之多。結果表明在水聲目標識別應用當中，綜合利用多域組合特征的IEK-NN新算法相對于傳統EK-NN算法更為有效可行。

為便于新算法在其他應用研究中的進一步推廣和發展，可以根據目標的正確識別率和分類時間兩個指標，對新算法中的訓練樣本子集數目B和子集樣本個數Nj等參數進行實驗分析，實驗中所使用的計算機型號為聯想啟天M4300，統計分類時間時，使用的軟件為Windows 7系統下MATLAB 2014a。結果如表4所示。

表4　新算法參數分析

表4的實驗結果顯示，新算法中訓練樣本子集數目B和子集樣本個數Nj越大，所構造的近鄰證據就越精確，那么在分類決策時目標的識別率就越高。但在數目增大時，計算的復雜度就會增加，對水聲目標識別的實時性就會造成一定的負面影響。因此，在IEK-NN新算法的進一步應用中，也要根據具體識別任務對于時間和精度的綜合要求，來進行合理的參數設定。

5　結　語

本文對傳統EK-NN算法及其局限進行了詳細分析，并針對其局限研究了一種新的IEK-NN算法。新算法將近鄰分類與證據推理中的PCR5規則相結合，并采用重復采樣方式來構造多個訓練樣本子集，從而可以更合理地利用樣本的多域組合特征信息，同時也能有效地處理水聲目標識別系統中的不確定信息，因此可以極大地提高目標的正確識別率。其次通過與傳統EK-NN分類算法在水聲目標實測數據上的對比實驗，顯示了新算法的良好識別性能。最后對新算法的參數設置進行了實驗分析，以便于新算法在目標識別領域的進一步推廣應用。

[1] 楊宏暉，王蕓，戴健.水下目標識別中樣本選擇與SVME融合算法[J].西北工業大學學報，2014，32(3):362-366.

[2] 宋波.水下目標識別技術的發展分析[J].艦船電子工程，2014，34(4):168-173.

[3] 禹亮，程詠梅，陳克喆，等.基于證據理論的水聲多目標優選方法[J].西北工業大學學報，2014，32(3):429-433.

[4] 戴健，楊宏暉，王蕓，等.用于水聲目標識別的自適應遺傳樣本選擇算法[J].聲學技術，2013，32(4):332-335.

[5] 楊秀芳，張偉，楊宇祥.基于提升小波變換的雷達生命信號去噪技術[J].光學學報，2014，34(3):1-6.

[6] 黃志遠.新規背景下的噪聲控制技術應用[J].船海工程，2014，43(3):95-98.

[7] 劉先康，梁菁，任杰，等.修正最近鄰模糊分類算法在艦船目標識別中的應用[J].計算機工程與應用，2010，46(9):228-231.

[8] 韓德強，楊藝，韓崇昭.DS證據理論研究進展及相關問題探討[J].控制與決策，2014，29(1):1-11.

[9] 劉準釓，程詠梅，潘泉，等.證據沖突下自適應融合目標識別算法[J].航空學報，2010，31(7):1426-1432.

[10] 陳雁飛，夏學知，胡丹桂，等.基于試探折扣修正的證據組合方法[J].電子學報，2014，42(4):756-765.

[11] 張揚，侯俊，劉準釓，等.一種新的證據K-NN數據分類算法[J].火力與指揮控制，2013，38(9):58-60.

[12] Denoeux T.A k-nearest neighbor classification rule based on Dempster-Shafer theory[J].IEEE Trans on Systems,Man and Cybernetics，1995，25(5):804-813.

[13] Smarandache F，Dezert J.Advances and Applications of DSmT for Information Fusion I[M].Rehoboth:American Research Press，2004.

[14] Smarandache F，Dezert J.Advances and Applications of DSmT for Information Fusion II[M].Rehoboth:American Research Press，2006.

[15] Smarandache F，Dezert J.Advances and Applications of DSmT for Information Fusion III[M].Rehoboth:American Research Press，2009.

[16] 杜方鍵，楊宏暉.兩種半監督多類水下目標識別算法的比較[J].聲學技術，2014，33(1):10-13.

[17] 石超雄，李鋼虎，何會會，等.基于提升小波變換的MFCC在目標識別中的應用[J].聲學技術，2014，33(4):372-375.

[18] 王磊，彭圓，林正青.聽覺外周計算模型在水中目標分類識別中的應用[J].電子學報，2012，40(1):199-203.

UNDERWATER ACOUSTIC TARGET RECOGNITION BASED ON IMPROVED EVIDENTIAL K-NN ALGORITHM

Yang RuiWang Xiaoyan

(College of Mechanical and Electrical Engineering,Xi’an University of Architecture and Technology,Xi’an 710055,Shaanxi,China)

The evidence classification algorithm has been widely used in pattern recognition field.In view of the limitation of traditional evidential k-nearest neighbour classification algorithm in combination rule of nearest neighbour evidences,we proposed a PCR5 rule-based improved evidential k-nearest neighbour classification algorithm (IEK-NN).First the new algorithm repeatedly samples from total sample set in random to construct a couple of training subsets.Then in each training subset,it uses the feature distance between target data and its nearest neighbour to determine the basic belief assignments.Finally the algorithm uses PCR5 rule of evidence reasoning to integrate the nearest neighbour evidences and according to the integration result and the classification rule established by it to judge the classification attribute of target.Through the experiment of measured data of underwater acoustic target,we make comparative analysis on IEK-NN and traditional evidential nearest neighbour classification algorithm.Result indicates that IEK-NN can effectively improve the recognition accuracy.

Pattern recognitionUnderwater acoustic targetEvidence reasoningNearest neighbourCombination rule

2015-05-06。陜西省教育廳專項科研計劃項目(14JK1405)。楊蕊，助理工程師，主研領域：信號處理，電工技術。王曉燕，副教授。

TP391.4

A

10.3969/j.issn.1000-386x.2016.09.067