Vol.35 No.21 Computer Engineering · 博士论文 ·
文章编号：1000—3428(2009)21—0007—03
文献标识码：A
2009年11月
November 2009
中图分类号：TP311.5
改进核最近特征分类器与雷达目标识别
刘华林，阳 光
(中国兵器装备集团公司火控技术中心，成都 611731)
摘 要：为了解决核最近特征线与特征平面分类器在计算大数据样本量与高维数时工作量较大的问题，根据局部最近邻准则，提出针对这2种分类器的改进策略，使其不仅能够降低失效的可能性，而且在保证相近识别率的条件下，提高算法的实时性能，利用3类不同飞机实测距离像回波数据对其进行测试，实验结果表明，该改进策略是有效可行的。 关键词：雷达目标识别；核最近特征分类器；局部最近邻准则；距离像
Improved Kernel Nearest Feature Classifier
and Radar Target Recognition
LIU Hua-lin, YANG Guang
(Fire Control Technology Center, China Ordnance Equipment Group Corporation, Chengdu 611731)
【Abstract】In order to solve larger workload problems when Kernel Nearest Feature Line(KNFL) and Kernel Nearest Feature Plane(KNFP) classifiers compute large data size and high dimensionality, an improved strategy for these two classifiers is proposed according to locally nearest neighbor rule, which reduces the disabled possibility, and promotes the algorithms real-time performances under condition of similar recognition rate. It is tested by using the real range profiles of three types of aircrafts. Experimental results show this strategy is effective and feasible. 【Key words】radar target recognition; kernel nearest feature classifier; locally nearest neighbor rule; range profile
1 概述 在模式识别任务中，模式分类与特征提取一样也是需要解决的关键问题。目前，业界已有多种模式分类方法，其中，最近邻(Nearest Neighbor, NN)分类器[1]应用最广泛，但NN分类器的性能较依赖于样本特征的表征能力和样本个数，对训练样本数较少的情况，其表征目标变化的能力有限，分类性能较弱。针对该问题，研究者将基于点(样本的投影子像看作是特征空间中的一个点)的NN分类器推广到线和面的情况。文献[2]提出最近特征线(Nearest Feature Line, NFL)分类器。文献[3]在NFL的基础上，提出最近特征平面(Nearest Feature Plane, NFP)分类器。此外，文献[4]将核技巧与NFL, NFP结合，进一步得到核最近特征线(Kernel Nearest Feature Line, KNFL)与核最近特征平面(Kernel Nearest Feature Plane, KNFP)分类器。研究表明，基于线和面的分类器扩展了对目标变化的表征能力，有利于提高分类器的性能。特别是KNFL和KNFP，两者无需特征提取过程，即可直接对原始目标样本进行分类，但KNFL和KNFP仍存在以下不足： (1)在样本数据量大与高维情况下，算法的计算量大，分类实时性能差；(2)可能存在失效问题。 针对上述情况，本文依据局部最近邻准则对KNFL和KNFP进行改进，提出k近邻KNFL(k-KNFL)和k近邻KNFP(k-KNFP)，其中，k表示选定的最近邻样本个数。 2.1 k近邻核最近特征线分类器 KNFL是NFL的一种核非线性版本。依据核机器学习理[5-6]论，首先通过一个非线性映射Φ:x→Φ(x)将原始距离像样本x映射到特征空间F中。如图1所示，Φ(x)表示某个待识别样本；Φ(xli)和Φ(xlj)为第l类(1≤l≤g)目标的任意 2个训练样本，记过点Φ(xli)和Φ(xlj)的直线Φ(xli)Φ(xlj)为该类的一条特征线。 Φ(x)Φ(xli)pΦΦ(xlj)
图1 KNFL分类器几何关系 从点Φ(x)到特征线Φ(xli)Φ(xlj)引垂线，设垂足为pΦ，则点Φ(x)到pΦ的距离为 d(Φ(x),pΦ)=||Φ(x)−pΦ|| (1) 其中，pΦ=Φ(xli)+δΦ(Φ(xlj)−Φ(xli))。由直线Φ(xli)Φ(xlj)与Φ(x)pΦ垂直，满足<Φ(x)−pΦ,Φ(xlj)−Φ(xli)>=0，可推出系数δΦ： 基金项目：国家自然科学基金资助项目(60702070)
作者简介：刘华林(1977－)，男，博士，主研方向：雷达信号处理，雷达目标识别；阳 光，高级工程师
收稿日期：2009-06-02 E-mail：hualinl2004@126.com
2 核最近特征分类器的改进 设xij表示第i类目标、第j个姿态角的距离像(1≤i≤g, 1≤j≤Ni,N=N1+N2+\"+Ng)，其中，g表示目标的类别数；Ni表示第i类目标的训练样本数；N为训练样本总数。
—7—
δΦ=
<Φ(x)−Φ(xli),Φ(xlj)−Φ(xli)><Φ(xlj)−Φ(xli),Φ(xlj)−Φ(x=
li)>
k(x,xk(x lj)−k(x,xli)−k(xli,xlj)>+li,xli)
k(x (2)lj,xlj)−2k(xli,xlj)+k(xli,xli)
其中， k(x,x)−2k(x,pΦ)+k(pΦ,pΦ) (3) 其中， k(x,pΦ)=δΦk(x,xΦlj)+(1−δ)k(x,xli) (4) k(pΦ,pΦ)=(δΦ−1)2k(xli,xli)+ 2δΦ(1−δΦ)k(xli,xlj)+(δΦ)2k(xlj,xlj) (5) 对未知待测样本x，若满足式(6)定义的约束，KNFL将判定其属于第h类： d(Φ(x),Φ(xhi)Φ(xhj))= 1min d(≤Φ(x),Φ(xli)Φ(xlj))(6) l≤g;i≠1≤j i,j≤Nl由上述分析可知，KNFL无需特征提取过程，即可直接对原始距离像样本进行分类，但同时也可以看到，该分类器每次任务都需建立MgKNFL=∑i=1N i(Ni−1)/2条特征线，因此，当样本数据量大、样本维数高时，计算量也是相当可观的。同时，KNFL继承了NFL的特点，也存在可能失效问题，如图2所示。 ΦΦ(x12)Φ(x11)p1Φ(x)pΦ2Φ(x21)Φ(x22) 图2 KNFL可能失效的情况 在图2中，待识别样本Φ(x)与第1类训练样本点Φ(x11), Φ(x12)较近，但与特征线Φ(x11)Φ(x12)却较远；相反地，Φ(x) 与训练样本Φ(x21), Φ(x22)较远，但与特征线Φ(x21)Φ(x22)却较近。依据式(6)的判决准则，Φ(x)将被判予第2类，而事实上Φ(x)属于第1类的可能性更大些。 受局部线性嵌入(Locally Linear Embedding, LLE)思想[7]的启发，本文提出一种基于局部最近邻准则的k近邻KNFL(k-KNFL)分类方法，具体步骤是：对第l类训练目标，先计算待识别样本Φ(x)与该类所有训练样本点的Euclidean距离，并按距离从小到大的顺序对这些点进行排列，然后选取前k≥2个最近邻的训练样本点组成第l类目标的训练样本子集(其他各类依此类推)。最后，在选出的g类训练样本子集基础上，用KNFL分类方法对Φ(x)进行分类。此时，分类规则变为 d(Φ(x),Φ(xhi)Φ(xhj))= 1min d(≤Φ(x),Φ(xli)Φ(xlj)) (7) l≤g;i≠1≤j i,j≤k改进后的k-KNFL计算特征线的数量大大减少，即Mk−KNFL=g×k×(k−1)/2，从而有效提高了实时性能。另一方面，对上述可能失效的问题，由于每幅待识别样本从各类训练样本集中均抽取与之最近邻的k个样本组成新训练集，因—8— 此算法分类失效的可能性将大大降低。 2.2 k近邻核最近特征平面分类器 对比KNFL，KNFP则是NFP的一种核非线性扩展，其几何关系如图3所示。 Φ(x)Φ(xli)ElpΦΦ(xlj)Φ(xlm) 图3 KNFP分类器几何关系 同样地，设Φ(x)表示某个待识别样本，Φ(xli), Φ(xlj)和Φ(xlm)为第l类(1≤l≤g)目标的任意3个训练样本，则记过点Φ(xli), Φ(xlj)以及Φ(xlm)的平面El为该类的一个特征平面。 从点Φ(x)到特征平面El引垂线，设垂足为pΦ，则点Φ(x)到平面El的距离为 d(Φ(x),El)=||Φ(x)−pΦ|| (8)其中，pΦ可以利用垂线Φ(x)pΦ与平面El垂直的特性求得：pΦ=YΦ((YΦ)TYΦ)−1(YΦ)TΦ(x)=YΦK−1lKlx (9)其中，YΦ=[Φ(xli),Φ(xlj),Φ(xlm)]，Kl和Klx分别表示为 ⎡k(xli,xli)k(xli,xlj)k(xli,xlm)⎤ Kl=(YΦ)T Y Φ=⎢⎢k(xx⎥ lj,xli)k(xlj,lj)k(xlj,xlm)⎥ (10)⎢⎣k(xlm,xli)k(xlm,xlj)k(xlm,xlm)⎥⎦ ⎡Φ(xli )T⎤⎡k(xli,x)⎤KYΦ)TΦ(x)=⎢⎢⎢Φ(xT ⎥⎥lx=(lj)⎥Φ(x)=⎢⎢k(xlj,x)⎥ (11)⎢⎣Φ(x)T⎥lm⎥⎦ ⎢⎣k(xlm,x)⎥⎦由此可以计算获得Φ(x)到特征平面El的距离： d(Φ(x),EΦl)=||Φ(x)−pΦ|| = k(x,x)−2k(x,pΦ)+k(pΦ,pΦ) (12)其中， k(x,pΦ)=Φ(x)TYΦK−1T lKlx=K−1lxKlKlx (13)k(pΦ,pΦ)=(YΦK−1−1T−1lKlx)TYΦKlKlx=KlxKlKlx (14)由于Kl为对称矩阵，因此依据式(13)、式(14)，式(12)可进一步简化为 d(Φ(x),El)=||Φ(x)−pΦ||=k(x,x)−KT−1lxKlKlx (15)对未知测试样本x，KNFP判定其属于第h类，当且仅当满足约束： d(Φ(x),Eh)= 1≤l≤g;min1d(El)≤i,j,m≤NΦ(x), (16) i≠j≠m lKNFP与KNFL一样存在相同的问题，因此，本文依据局部最近邻准则也提出k近邻KNFP(k-KNFP)分类方法。其具体步骤与k-KNFL相仿，但从每类目标中抽取的最近邻样本数必须满足k≥3，同时，分类规则相应变为 d(Φ(x),Eh)= 1≤l≤gmin;1≤i,j,m≤d(Φ(x),El) (17) i≠j≠m k可见，改进后k-KNFP分类器的实时性能将大大提高，所需计算的特征平面数将由原来的∑gi=1Ni(Ni−1)(Ni−2)/6减少为g×k(k−1)(k−2)/6，而分类失效的可能性则大大降低。 3 实验结果与分析 3.1 实验数据 本文实测数据采用C波段ISAR雷达对空中3种飞机(An-26, Jiang和Yark-42)所成的距离像，根据飞行轨迹的不同，每种飞机各记录了7段数据。雷达及目标的部分参数分别如表1、表2所示。 表1 ISAR雷达的部分参数 MHz Radar parameters value Center frequency 5 520 Bandwidth 400 表2 3类飞机目标的部分参数 m parameters Length Width Height An-26 23.80 29.20 8.58 Jiang 14.39 15.90 4.57 Yark-42 36.38 34.88 9.83 Aircraft 从表3、表4可以看出，对比与KNFL, k-KNFL在k值取2~10时均取得较高的识别率，尤其当k取10时平均识别率最为接近。但是KNFL在4种不同样本数情况下，分类所用的时间分别为1.607 7 s, 13.050 4 s, 44.327 5 s以及 105.593 0 s(实验在P2.0 GHz、2.0 GB内存的PC机上完成，编程环境Matlab R2007a，取重复10次实验的平均结果)，而与之相比，10-KNFL分类所用的时间仅为0.726 3 s, 1.343 4 s, 2.025 6 s和2.736 4 s。基于局部最近邻准则改进后的k-KNFL，不仅分类的实时性能明显提高，而且平均识别率可与KNFL相比拟。同样的情况，对于KNFP和k-KNFP而言，也可以得出相似的结论。 4 结束语 本文研究2种核最近特征分类器KNFL和KNFP的分类机理，并基于局部最近邻准则对它们进行改进，得到k-KNFL和k-KNFP。这些分类器的优点在于无需经过特征提取，即可直接对原始目标样本进行分类。对3种不同类型飞机的实测距离像回波数据进行分类实验，实验结果表明改进后的k-KNFL和k-KNFP在实时性能上明显优于原KNFL和KNFP，而识别性能仍保持了较高水平。 参考文献 [1] Cover T M, Hart P E. Nearest Neighbor Pattern Classification[J]. IEEE Transactions on Information Theory, 1967, 13(1): 21-27. [2] Stan Z L, Lu Juwei. Face Recognition Using the Nearest Feature Line Method[J]. IEEE Transactions on Neural Networks, 1999, 10(2): 439-443. [3] Chien J T. Discriminant Waveletfaces and Nearest Feature Classifiers for Face Recognition[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(12): 1644-1649. [4] 贺云辉, 赵 力, 邹采荣. 核最近特征分类器及人脸识别应用[J]. 应用科学学报, 2006, 24(3): 227-231. [5] Schökopf B, Smola A, Müller K. Nonlinear Component Analysis as a Kernel Eigenvalue Problem[J]. Neural Computation, 1998, 10(5): 1299-1319. [6] Vapnik N. The Nature of Statistical Learning Theory[M]. New York, USA: Springer Verlag, 1995. [7] Roweis S T, Saul L K. Nonlinear Dimensionality Reduction by Locally Linear Embedding[J]. Science, 2000, 290(1): 2323-2326. 3.2 实验结果 实验选定An-26的第4段、Jiang的第4段和Yark-42的第2段距离像数据，并从各段分别抽取30幅、60幅、90幅和120幅距离像组成3组不同大小的实验样本集，然后对样本集进行能量归一、Fourier变换对准等预处理，并按“隔一取一”的方式，将各样本集的奇数幅像作为训练样本，余下的作为测试样本。此外，核最近特征分类器采用径向基核函2 数[6]k(x,y)=exp(−||x−y||/σ)，其中，参数σ取值为0.5。 表3、表4分别给出了当最近邻样本数k取不同值时，KNFL和k-KNFL、KNFP和k-KNFP的分类性能对比。 表3 KNFL和k-KNFL的平均识别率比较 (％) Number of training samples per class Method 15 30 45 60 KNFL 100.00 98.89 97.04 96.67 2-KNFL 97.78 96.67 92.59 90.56 3-KNFL 97.78 96.37 94.07 94.44 4-KNFL 97.78 97.78 95.56 95.00 5-KNFL 97.78 98.89 95.56 95.00 6-KNFL 100.00 98.89 95.56 95.00 7-KNFL 100.00 98.89 95.56 95.56 8-KNFL 100.00 98.89 95.56 95.56 9-KNFL 100.00 98.89 95.56 95.56 10-KNFL 100.00 98.89 97.04 95.56 表4 KNFP和k-KNFP的平均识别率比较 (％) Number of training samples per class Method 15 30 45 60 KNFP 100.00 98.89 97.78 97.22 3-KNFP 97.78 98.89 95.56 94.44 4-KNFP 97.78 98.89 97.04 96.11 5-KNFP 97.78 97.78 97.04 96.11 6-KNFP 97.78 97.78 96.30 96.11 7-KNFP 100.00 97.78 97.04 96.11 8-KNFP 100.00 98.89 97.04 96.11 9-KNFP 100.00 98.89 97.04 96.11 10-KNFP 100.00 98.89 97.78 96.11 编辑 陈 文 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ （上接第6页） 参考文献 [1] Yang D L, Chern M S. Two-machine Flowshop Sequencing Problem with Limited Waiting Time Constraints[J]. Computers & Industrial Engineering, 1995, 28(1): 63-70. [2] 王 凌. 车间调度及其遗传算法[M]. 北京: 清华大学出版社, 2003. [3] Sally C, Ford B, Potts C N, et al. Constraint Satisfaction Problems: Algorithm and Applications[J]. European Journal of Operational Research, 1999, 119(3): 557-581. [4] Deris S, Omatu S, Ohta H, et al. Incorporating Constraint Propagation in Genetic Algorithm for University Timetable Planning[J]. Engineering Applications of Artificial Intelligence, 1999, 12(3): 241-253. [5] Hansen P, Mladenovic N. Variable Neighborhood Search[J]. Computers in Operations Research, 1997, 24(11): 1097-1100. 编辑 任吉慧 —9— 因篇幅问题不能全部显示，请点此查看更多更全内容