基于证据聚类的水声目标识别算法研究
张扬1, 杨建华1, 侯宏2     
1. 西北工业大学 自动化学院, 陕西 西安 710129;
2. 西北工业大学 航海学院, 陕西 西安 710072
摘要: 针对水声目标信号复杂、样本获取难度大且富含不确定信息的问题,研究了一种证据聚类识别算法。首先在水声目标的各类训练样本中,根据特征距离大小选取待识别目标的K近邻,并采用证据近邻分类优化算法为各目标数据构造一组合理的初始基本置信指派。然后对算法的目标函数进行循环迭代优化,计算出目标数据最终的全局基本置信指派。最后根据融合结果和所设立的分类规则即可判断目标的类别属性。通过水声目标实测数据的实验,将新算法与其他几种常用的水声目标识别算法进行了对比分析,结果表明其能有效提高识别准确率。
关键词: 水声目标     证据聚类     证据K近邻     组合规则     模式识别    

水声目标识别在诸多方面都有着重要的应用背景[1-2]。快速准确地识别是克敌致胜的关键, 因此其相关研究一直深受关注[3-4]。但水声目标信号复杂且类别众多, 同时又富含噪声和不确定数据, 这都为识别工作带来了极大挑战。

水声目标识别系统受传感器探测精度和环境噪声影响, 所获取的目标数据会包含大量的不精确、不确定信息, 此外在应用中很难构建一个完备的样本库, 使得目标数据也具有一定的不完备性。传统的水声目标识别算法诸如:支持向量机优化算法(Support vector machine algorithms, SVM)[1, 3]和近邻改进算法(Improved K nearest neighbor algorithms, IKNN)[5-6]受其理论框架限制, 不能很好处理这部分信息, 在识别决策时易造成结果的误判。而证据分聚类算法[7-13]在不确定、不完备信息的量测和处理上具有显著的优势, 为问题的解决提供了全新思路。在证据分聚类算法中, 证据K近邻分类[7]和证据C均值聚类算法(Evidence c-means clustering algorithm, ECM)[8, 9]计算简单、易于实现, 也最具代表。但证据K近邻分类算法具有易受噪声数据影响的局限。因此, 基于以上的算法基础并针对水声目标信号富含噪声和不确定信息的特定问题, 文章首先对证据K近邻算法进行优化, 然后结合ECM算法中目标函数和相关参数的设定, 研究了一种基于证据聚类的水声目标识别算法(The evidence clustering recognition algorithm, TECRA)。通过水声目标实测数据的对比实验, 对新算法的良好性能进行了验证分析。

1 证据理论及其聚类算法 1.1 证据理论及组合规则

证据理论也称Dempster-Shafer(D-S)理论[14], 可有效处理不确定和不精确信息。D-S是基于辨识框架Θ的, 对于问题域中的任何命题A都应包含于幂集2Θ中。其基本置信指派函数m:2Θ→ [0, 1], m满足:m(ø)=0, 以及∀A ⊆ 2Θ

(1)

·D-S规则

假定辨识框架上独立的2个证据BC, 其焦元分别为BiCj, 基本置信指派函数为m1m2, 按照D-S规则组合如下:

(2)

矛盾因子:

(3)

D-S满足交换律和结合律, 可推广到多证据融合中且能够快速收敛。

·PCR5规则

D-S对“高冲突”证据进行合成时会出现不合理结果。许多学者都提出了相应的改进方法[15-16]。其最具代表的就是Dezert和Smarandache所提出的redistribute conflicting mass proportionally rule5(PCR5)规则[15], 对2个证据合成时如下所示:

(4)

式中,x, y分别为证据BC的2个存在冲突信息的焦元。PCR5可根据矛盾双方基本置信的大小, 将冲突信息按比例进行精确分配。适用于“高冲突”证据的组合, 但不利于焦元置信值的快速收敛。

1.2 证据C均值聚类算法

ECM给出了不确定和噪声类别, 能准确处理分类中的不确定信息并抑制噪声数据干扰。ECM中样本xi={xi1, xi2, …, xip}(i=1, 2, …, n)的类别属性, 可通过辨识框架Ω={ω1, …, ωc}下的基本置信指派mi(·)进行表征。其mi(·)可表示xi从完全未知到全部确定的所有情况。xi对于命题Aj的置信值mi(Aj)可简单表示为mij, 其取值是根据xivj间的距离dij大小所确定的, 其中vj为命题Aj的类别中心, 定义如下:

(5)
(6)

式中, vk为单个类别ωc的类别中心, Ej=|Aj|表示命题A的势, dij为样本xi与类别中心vj间的欧式距离。

(7)

ECM中所定义的目标函数为:

(8)

满足约束条件:

(9)

ECM通过以下两交替步骤来实现算法的各步更新。

1) 基本置信指派的更新

(10)
(11)

式中, 参数α为势集权重因子, β为置信值的权重系数, 一般选取为2, δ为给定的噪声阈值。

2) 聚类中心的更新

矩阵Vc×p的的每一行对应着每一类别的聚类中心, 可通过求解以下线性系统方程得出:

(12)

其矩阵BH中各元素的具体定义为:

(13)
(14)
2 本文方法

证据K近邻分类算法所采用的D-S规则对“高冲突”近邻证据进行组合时会存在一定的局限。而在水声目标识别当中, 同类别间的近邻证据其置信不是分派给此类别就是分派给未知, 因此不存在“高冲突”, 融合时可采用D-S规则以增强融合的时效性。不同类别间的证据由于置信分派所属类别不同, 会存在一定的冲突, 融合时可采用PCR5规则以减少融合的错误。因此, 文章首先研究了证据K近邻优化算法(improved evidence K nearest neighbor, IEKNN), 然后进一步结合ECM算法中目标函数和相关参数的设定, 提出了一种基于证据聚类的水声目标识别算法(TECRA)。

2.1 证据K近邻优化算法

IEKNN综合D-S与PCR5规则的各自优势, 对同类别近邻证据组合时使用D-S提高计算速率, 对异类证据组合时使用PCR5减少识别误差。算法主要包括各类别下近邻证据的构造和组合、类别间证据的融合2个步骤。

1) 各类别下近邻证据的构造和组合

对于M类水声目标{C1, …, CM}, 首先建立各类目标的训练样本库, 对于待识别水声目标xs, 在类别Ci(i=1, 2, …, M)的训练样本中根据特征距离大小选取xsK近邻。可得近邻样本集合:Φi={(x1, d1), …, (xk, dk)}。

距离目标越近的样本类别属性也与其越接近, 所构造的近邻证据权重越大。确定距离xs最近样本所构造的近邻证据为关键证据, 其权重为:

(15)

则相应的各近邻证据“权重系数”为:

(16)

特征距离dj(j=1, 2, …, K)到基本置信指派(basic belief assignments, bba′s)的转换可通过负指数函数进行描述, 所构造的K近邻证据为:

(17)

式中, mj表示j近邻所对应的bba′s, 在类别Ci下, 各近邻证据的bba′s不是分给类别Ci就是分派给未知, 使得近邻证据间不存在“高冲突”, 可直接采用D-S规则组合, 从而得到类别Ci下总的bba′s:

(18)

M类水声目标, 经此步的计算可得各类别下bba′s集合:Φ={m1, …, mM}。

2) 类别间证据的融合

集合Φ中各元素mi(i=1, 2, …, M)的置信度主要分派给了各自的类别Ci, 由于不同类别的bba′s指派不同, 这就导致证据存在一定的冲突。需采用PCR5规则对冲突信息进行精确分配。对于M类水声目标的bba′s, 应用PCR5规则组合, 可得最终的bba′s ms:

(19)
2.2 新的证据聚类识别算法

在证据聚类中, 一组合适的初始bba′s不仅可以极大缩短迭算法的代优化时间, 而且还可以有效抑制噪声数据影响并提高分类正确率。因此, TECRA中首先采用IEKNN为各目标数据构造一组合理的初始bba′s, 然后结合ECM中目标函数和相关参数的设定, 并对目标数据的bba′s进行循环优化, 最后根据全局bba′s进行识别。算法主要包括特征提取、证据的构造与融合及分类决策。

2.2.1 特征提取

水声目标信号为非平稳信号, 小波变换是非平稳信号的良好分析工具[17-18]。因此提取水声目标的小波分析特征作为识别特征, 具体过程为:

1) 对水声目标y进行N级小波分解, 并提取每级分解后的高频分量yj(j=1, …, N)。

2) 统计各高频分量yj中过零点波的波长分布密度:

(20)

(20)式中, S(αi)表示yj中波长为αi的过零点波个数, l为过零点波的波长类型总数。

3) 计算yj中过零点波的波长分布密度所对应的信息熵值:

(21)

Hj(α)即为目标的小波分析特征。

2.2.2 证据的构造与融合

将训练样本和识别目标的特征信息转换为可进行组合的证据是应用证据分类算法的关键, TECRA中证据构造与融合的具体步骤为:

1) 输入n个待识别水声目标{x1, …, xn}。

2) 设定IEKNN算法中的近邻参数K, 首先在水声目标的模板库中, 选取各目标数据的近邻样本, 然后使用IEKNN算法为各目标数据构造一组初始的基本置信指派bba′s (即目标属于各类别的一组初始隶属度)。

(22)

3) 根据各目标数据的初始bba′s, 设定参数c, α, β, δ, ε的取值, 1<cn; α>0;β>1;δ>0。根据公式(13)、(14), 计算初始转换矩阵B0H0的各元素。

(23)

4) 设定循环的终止阈值ε, 并对目标函数进行如下循环优化过程。

循环过程(t为循环次数):

(1) 根据公式(5)、(6)、(10)、(11)和Vt-1, 更新Mt

(2) 根据公式(13)、(14)和Mt, 更新BtHt

(3) 根据公式(12)以及BtHt的取值, 更新Vt

(4) 根据公式(8)计算目标函数值, 当与前一次循环中目标函数的差值小于设定阈值ε时, 停止循环运算, 否则继续执行循环过程。

5) 输出聚类中心Vt, 以及各目标数据的类别隶属度mij

6) 再次重新设定IEKNN算法中的近邻参数K′, 并重复步骤2~5, 获得另一组目标数据的bba′s mij

7) 使用PCR5规则对2组bba′s进行组合, 可得各目标数据的全局bba′s ms

(24)
2.2.3 分类决策

根据各目标数据的全局bba′s ms(s=1, 2, …, n), 计算待识别目标xs属于各个模式类别的pignistic概率BetP{Ci} (i=1, 2, …, M)。

(25)

然后, 确定如下分类规则:

规则1  目标所属类别应具有最大的pignistic概率, 表示具有最大信任值的类别就是目标类别;

规则2  目标所属类别与其他类别的pignistic概率差值须大于某一阈值T, 表示证据对不同类别的支持程度应保持足够大的差异;

最后, 计算符合以上分类规则的BetP{Ci}, i为所得的1到M的某一特定取值。那么类别Ci即被判定为待识别水声目标xs(s=1, 2, …, n)的所属类别。

3 实验及结果分析 3.1 实验数据及参数设置

分类实验所选取的对象是一些实测水声目标的声信号, 采样频率为22 kHz。实验中选取4 096个点为一个样本, 对每个样本提取10维的小波分析特征。水声目标主要分为3个类别, 共16 500个样本, 其中Type1有7 500个、Type2有4 400个、Type3有6 000个。各类别下训练和测试样本的具体设定如表 1所示:

表 1 训练样本和测试样本的数目
样本用途 各类水声目标样本个数 样本总和
Type1 Type2 Type3
训练 4 500 3 000 3 600 11 100
测试 3 000 1 800 2 400 5 400

为对水声目标特性进行直观展示, 提取了一些各类别典型样本的小波分析特征, 如图 1所示:

图 1 各类别中典型样本的小波分析特征示图

使用TECRA进行识别时, 其算法参数NT可根据具体应用进行设定。T越小目标区分的就约为精确, 在识别应用中一般选取为0.2。N越大所包含的目标信息越丰富, 而计算就会越复杂。对于此水声目标实测数据分类实验, 经过多次实验求证在N的取值大于10后, 对算法识别准确度的影响己经很小。因此参数NT的设定如表 2所示:

表 2 NECNE算法的参数设定
参数符号 参数含义 参数的实验取值
N 小波分析特征维数 10
T 不同类别pignistic概率的差值阈值 0.2
3.2 实验结果及分析

根据表 1中的样本设定, 分别采用传统的SVM和IKNN、以及IEKNN和TECRA新算法对测试样本进行分类验证, 其中IKNN、IEKNN和TECRA的近邻数目K都选取为6, 具体结果如表 3所示:

表 3 各分类算法的实验结果
测试样本 识别正确率/(%)
SVM IKNN IEKNN TECRA
Type1 88.07 88.73 90.47 97.47
Type2 88.85 89.15 89.46 96.55
Type3 89.08 88.75 90.08 96.65
总和 88.66 88.88 90.00 96.89

表 3显示, SVM与IKNN的识别正确率比较接近, 基本维持在0.89。IEKNN相对于SVM与IKNN识别正确率有了一定提高但不是很显著, 只能达到0.91。而相比之下, TECRA识别率则有了极大的提升, 基本可以保持在0.96以上。

改变IKNN、IEKNN和TECRA的近邻样本数目K, 并对比各算法识别率的变化, 结果如图 2所示:

图 2 不同K值时各算法的正确识别率

图 2中各算法识别率曲线显示, 在近邻数目K相同时, TECRA的正确识别率一直远远高于IKNN和IEKNN。当K值为9时, 新算法识别率可以进一步达到0.98。而这时IKNN和IEKNN的识别率也都不到0.90。这也表明在近邻数目相同即算法复杂度相近的情况下, 新算法能够有着更好的识别效果。

接下来通过目标的正确识别率和分类算法耗时2个指标, 对新算法TECRA的识别性能和计算复杂度进行分析, 结果如图 3表 4所示。

图 3 TECRA的算法性能分析图
表 4 TECRA算法识别时间与正确率的数据分析
近邻数目 分类时间/s 正确识别率
K=2 0.030 0.886
K=4 0.091 0.927
K=6 0.545 0.969
K=8 3.896 0.981

图 3中的算法识别率和计算耗时曲线显示, 随近邻样本参数K的增大, TECRA的正确识别率会得到提升, 同时计算耗时也会有所增加。但在近邻数目较少时(K<6), 随K值增加, 计算时间增加不是很大却可以极大地提高识别正确率。而近邻数目较大时(K> 6), 随K值增加, 识别正确率增加很微小但计算耗时却呈指数上升。此外表 4的实验结果也显示, K为4比K为2时的计算时间只多了0.061 s, 而识别率却可以提高4个百分点之多。但K为8比K为6时的识别正确率只提高了0.01, 但计算的耗时却增加了7倍之多, 会极大影响算法的时效性。所以, 针对此水声目标识别实验而言, K为6时为比较合理的选择。因此TECRA的推广应用中, 并非近邻数目越多越好, 而是要根据具体识别任务对时效性和识别精度的综合要求来进行合理设定。此外针对具体识别任务实现K值的自适应选择, 也将是新算法随后研究中的一个关键问题。

4 结论

文章研究了一种基于证据聚类的水声目标识别算法, 在构造目标数据的初始基本置信指派时采用了所提出的证据近邻优化算法, 其综合了D-S和PCR5规则的各自优势, 能有效的抑制噪声数据影响和提高分类正确率, 同时也极大缩短了后续迭代优化算法的时间。实测水声目标数据集的对比实验也很好的展示了新算法的良好性能。文章最后也对算法各项性能参数进行了详尽的实验分析, 便于在其他领域研究中的推广和应用。

参考文献
[1] 杨宏晖, 王芸, 戴健. 水下目标识别中样本选择与SVME融合算法[J]. 西北工业大学学报, 2014, 32(3): 362-366.
Yang Honghui, Wang Yun, Dai Jian. Instance Selection and SVM Ensembles for Underwater Acoustic Target Recognition[J]. Journal of Northwestern Polytechnical University, 2014, 32(3): 362-366. (in Chinese)
[2] 禹亮, 程咏梅, 陈克喆, 等. 基于证据理论的水声多目标优选方法[J]. 西北工业大学学报, 2014, 32(3): 429-433.
Yu Liang, Cheng Yongmei, Chen Kezhe, et al. Underwater Acoustic Target Optimum Seeking Using Evidence Theory[J]. Journal of Northwestern Polytechnical University, 2014, 32(3): 429-433. (in Chinese)
[3] 杜方键, 杨宏晖. 两种半监督多类水下目标识别算法的比较[J]. 声学技术, 2014, 33(2): 10-13.
Du Fangjian, Yang Honghui. Comparison of TWO Semi-Supervised Multiclass Underwater Target Recognition Algorithm[J]. Technical Acoustics, 2014, 33(2): 10-13. (in Chinese)
[4] 王磊, 彭圆, 林正青. 听觉外周计算模型在水中目标分类识别中的应用[J]. 电子学报, 2012, 40(1): 199-203.
Wang Lei, Peng Yuan, Lin Zhengqing. The Application of Computational Auditory Peripheral Model in Underwater Target Classification[J]. Acta Electronica Sinica, 2012, 40(1): 199-203. (in Chinese)
[5] 刘先康, 梁菁, 任杰, 等. 修正最近邻模糊分类算法在舰船目标识别中的应用[J]. 计算机工程与应用, 2010, 46(9): 228-231.
Liu Xiankang, Liang Jing, Ren Jie, et al. Application of Modified Nearest Neighbor Fuzzy Classification Algorithm in Ship Target Recognition[J]. Computer Engineering and Applications, 2010, 46(9): 228-231. (in Chinese)
[6] 纪正飚, 王吉林, 赵力. 基于模糊K近邻的语音情感识别[J]. 微电子学与计算机, 2015, 32(3): 59-62.
Ji Zhengbiao, Wang Jilin, Zhao Li. Speech Emotion Recognition Based on FKNN[J]. Microelectronics & Computer, 2015, 32(3): 59-62. (in Chinese)
[7] Denoeux T, Kanjanatarakul O, Sriboonchitta S. A Clustering Procedure Based on the Evidential K-Nearest Neighbor Rule[J]. Knowledge-Based Systems, 2015, 88: 57-69. DOI:10.1016/j.knosys.2015.08.007
[8] Antoine V, Quost B, Masson M H, et al. Constrained Evidential C-Means algorithm[J]. Computational Statistics and Data Analysis, 2012, 56(4): 894-914. DOI:10.1016/j.csda.2010.09.021
[9] Masson M H, Denoeux T. ECM:an Evidential Version of the Fuzzy C-Means Algorithm[J]. Pattern Recognition, 2008, 41(4): 1384-1397. DOI:10.1016/j.patcog.2007.08.014
[10] Liu Z G, Pan Q, Dezert J. A New Belief-Based K-Nearest Neighbor Classification Method[J]. Pattern Recognition, 2013, 46(3): 834-844. DOI:10.1016/j.patcog.2012.10.001
[11] 韩德强, 杨艺, 韩崇昭. DS证据理论研究进展及相关问题探讨[J]. 控制与决策, 2014, 29(1): 1-11.
Han Deqiang, Yang Yi, Han Chongzhao. Advances in DS Evidence Theory and Related Discussions[J]. Control and Decision, 2014, 29(1): 1-11. (in Chinese)
[12] Smarandache F, Dezert J. Advances and Applications of DSmT for Information Fusion6[M]. Rehoboth: American Research Press, 2009: 34-43.
[13] 陈雁飞, 夏学知, 胡丹桂, 等. 基于试探折扣修正的证据组合方法[J]. 电子学报, 2014, 42(4): 756-765.
Chen Yanfei, Xia Xuezhi, Hu Dangui, et al. Evidence Combination Based on Tentative Discount of Evidences[J]. Acta Electronica Sinica, 2014, 42(4): 756-765. (in Chinese)
[14] 石超雄, 李钢虎, 何会会, 等. 基于提升小波变换的MFCC在目标识别中的应用[J]. 声学技术, 2013, 33(4): 372-375.
Shi Chaoxiong, Li Ganghu, He Huihui, et al. Application of the Lifting Wavelet Transform Based MFCC in Target Identification[J]. Technical Acoustics, 2013, 33(4): 372-375. (in Chinese)
[15] 杨秀芳, 张伟, 杨宇祥. 基于提升小波变换的雷达生命信号去噪技术[J]. 光学学报, 2014, 34(3): 1-6.
Yang Xiufang, Zhang Wei, Yang Yuxiang. Denoising Technology of Radar Life Signal Based on Lifting Wavelet Transform[J]. Acta Opitca Sinica, 2014, 34(3): 1-6. (in Chinese)
The Underwater Acoustic Target Recognition Algorithm Based on Evidence Clustering
Zhang Yang1, Yang Jianhua1, Hou Hong2     
1. School of Automation, Northwestern Polytechnical University, Xi'an 710129, China;
2. School of Marine Engineering, Northwestern Polytechnical University, Xi'an 710072 China
Abstract: In underwater acoustic target recognition, the target signal is usually complex and the samples which are difficult to obtain also have some uncertain information. In order to effectively solve these problems, the evidence clustering recognition algorithm (TECRA) is presented. In this new method, the k-nearest neighbor are first determined by using the feature distance between the object and its neighbors in each class of the training set, and a reasonable initial basic belief assignments (bba's) for each target data are constructed by the improved k-nearest neighbor classification algorithm. Then the final global bba's of the target is obtained by optimizing the objective function of the algorithm. Finally the object can be recognized by the fusion result and the classification rule presented in the paper. Several experiments based on real underwater acoustic data sets are made to test the effectiveness of TECRA in comparison with some other methods. The results indicate that TECRA can effectively improve the recognition accuracy.
Key words: clustering algorithm     computational efficiency     evidence k-nearest neighbor     support vector machines     pattern recognition    
西北工业大学主办。
0

文章信息

张扬, 杨建华, 侯宏
Zhang Yang, Yang Jianhua, Hou Hong
基于证据聚类的水声目标识别算法研究
The Underwater Acoustic Target Recognition Algorithm Based on Evidence Clustering
西北工业大学学报, 2018, 36(1): 96-102.
Journal of Northwestern Polytechnical University, 2018, 36(1): 96-102.

文章历史

收稿日期: 2017-03-28

相关文章

工作空间