基于证据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