基于蚁群算法和特征融合的空间目标分类
2009-06-01
作者：方 建1, 曹占辉1,2, 李言
摘 要: 针对支持向量机核参数和误差惩罚因子较难选择以及采用单一特征分类效果较差的问题，提出了一种基于蚁群算法与特征融合的空间目标分类算法，克服了以往反复试验以确定其参数的缺点，优化了特征。该方法分类正确率达90%左右，与采用单一特征分类的结果相比，效果较好。验证了方法的有效性。
关键词: 空间目标； 支持向量机； 蚁群算法
随着开发太空步伐的加快，人类航天活动越来越频繁，由此产生的空间碎片日益增多，导致了空间环境逐步恶化，这对人类航天活动构成了严重的威胁，使卫星的发射和监测面临越来越严峻的挑战[1]。为了确保航天活动的安全可靠，保卫本国太空安全，促进人类航天事业的发展，对空间目标（卫星、碎片等）进行有效监视、识别和编目将具有重要意义。
由于保密的原因，不可能获得大量的相关数据，即分类的样本较少，这样导致普通的分类器无能为力。而在统计学习理论基础上发展起来的支持向量机(SVM)[2]在解决小样本学习方面表现出许多特有的优势。作为一门新兴的学科，SVM存在一些尚未完善的地方，其参数选取就是亟待解决的问题之一。参数选取的好坏直接影响分类器泛化性能的好坏，因此，如何选取参数常被认为是SVM从理论走向实际应用的一个“瓶颈”问题。传统的参数选取方法多是采用反复试验的方法确定，这需要很大的工作量。
由于空间环境复杂多变，影响空间目标的因素较多。抽取单一种类的特征进行目标识别，误识率较难降低，且抗干扰性不易提高。
本文提出了一种基于蚁群算法和特征融合的空间目标分类方法，用蚁群算法优选SVM参数，同时，采用特征融合技术将多种互补的特征结合以获取优化特征，并将其在空间目标分类中运用。
1 支持向量机参数范围的确定
支持向量机在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势，已经在模式识别、函数逼近和概率密度估计等方面取得了良好的效果。对于核函数的选择，目前尚无成熟理论。经过分析和比较，本文采用径向基函数作为核函数：
Vapnik等人在研究中发现，核函数的参数和误差惩罚因子C是影响支持向量机性能的关键因素。
C：用于控制模型复杂度和逼近误差的折中，C越大则对数据的逼近误差越小，但模型也越复杂，学习机器的推广能力也越差。
σ：用于控制回归逼近误差的大小，从而控制支持向量的个数和泛化能力，其值越大，则支持向量数越少，但精度不高，否则，支持向量数越多，精度越高。
由于没有理论上的指导，传统的参数选取都是通过反复的试验，人工选取出令人满意的解。这种方法需要人的经验做指导，并且它的选取需要付出较高的时间代价，因此,传统的参数选取方法并不能适应支持向量机的发展。
Keerthi的研究表明[3]，对于某一确定的足够大的C，当σ2→0时，会发生严重的“过学习”现象，此时径向基函数支持向量机能把训练样本正确分开，但对测试样本不具有任何推广能力；而当σ2→∞时，会发生严重的“欠学习”现象，此时径向基函数支持向量机把所有训练样本都划分到样本数较大的一类。从核函数K(xi,xj)=
exp(-||xi-xj||2/σ2）可以看出，σ2的大小完全是针对||xi-xj||2而言的。因此，在实际应用中，只要σ2的取值比训练样本之间的最小距离小得多，就能达到σ2→0的效果；当σ2比训练样本之间的最大间隔大得多时，就可以达到σ2→∞的效果。基于这一考虑，实验中，本文确定σ2的搜索空间为
。
在构造分类面方程时惩罚因子C的作用是对拉格朗日因子α的取值加以限制。当C超过一定值时就丧失了其对?琢取值的约束作用，相应的支持向量机的复杂度也达到了数据子空间所允许的最大值，此时，经验风险和推广能力几乎不再发生变化。为此采取了如下的启发式思维确定C值(例如10 000)，用其训练支持向量机求解出一组αi(i=1,2,…，L)，其中L为训练样本总数，令C*作为C的取值上限。否则说明C仍对α的取值构成约束，换一个更大的C训练支持向量机，直至等到的C*远小于C为止。这样就得到了C的搜索空间(0,C*)。
期望在分类精度接近条件下获得结构尽可能简单的分类面，所以在设计目标函数时，附加了两个复杂度控制项C1N1/n1和C2N2/n2，此时，目的函数为：
式中，E是支持向量机在训练样本集上的错分率，N1、N2、n1、n2分别对应两类的支持向量数和训练样本数。C1和C2值可取得较小，从而弱化分类面复杂度在适值函数中的比重；当对结构的简单性要求较高、对精度要求一般时，可相应地增加C1和C2。
2 基于蚁群算法的参数优化
蚁群算法ACO(Ant Colony Optimization)是意大利学者DORIGO M等人[4-5]于20世纪90年代通过模拟蚁群的觅食行为提出的一种新型模拟进化算法，它运用了正反馈、分布式计算和贪婪启发式搜索。该算法适应性强，无需计算目标函数的偏导数，搜索效率高，寻优能力突出，克服了其他算法容易陷入局部最优的缺点。鉴于蚁群算法以上的优点，本文采用该算法来实现对核函数参数和误差惩罚因子的优化搜索。
参考文献[6]指出，单独调整核函数g和惩罚因子C都可以使模型的推广能力得到提高，但如要同时获得小的经验风险就必须两个参数综合调整。因此本文设定g为横坐标，C为纵坐标，g-C在平面上寻优。
在取值范围内将g-C平面平均等分成M×N个子块(以下称区域)，区域大小为m×n，其中m=L/M,n=L/N，(为了保证各区域内目标函数值相差不会太大，避免陷入局部最优，区域的形状应尽量保证是正方形，即m=n)。
每个区域分配一只蚂蚁，则共有M×N只蚂蚁。初始时刻，蚂蚁在各区域的中心点或最靠近中心的某一点。蚂蚁的转移概率定义为：
式中，i2∈{1,2,…,M},j2∈{1,2,…,N}，τij称为区域(i,j)的吸引强度，即信息素的浓度，在初始时刻，每个区域信息素的量都是相等的，设τij(0)=C（C为一定常数）。令target(s,t)是以(s,t)计算得到的目标值，η(i1j1)(i2j2)(定义为max{target(s,t),(s,t)∈tabuk(i2,j2)}-max{target(s,t),(s,t)∈tabuk(i1,j1)}，即以两个区域中的向量计算得到的最大目标值之间的差值，表示区域(i1,j1)中的蚂蚁向区域(i2,j2)转移的期望程度。当η(i1j1)(i2j2)≥0时，区域(i1,j1)的蚂蚁按概率pij移动至区域(i2,j2)；当η(i1j1)(i2j2)<0时，区域中的蚂蚁在本区域（i1,j1)中搜索，即蚂蚁要么移动至其他区域，要么在本区域中搜索，tabuk(i,j)表示区域(i,j)中已经计算过的向量。α为信息启发式因子，反映了各区域信息素浓度即τij在蚂蚁运动过程中所起的作用，其值越大，蚂蚁之间的协作性越强。β为期望启发式因子，反映了启发信息即η(i1j1)(i2j2)在蚂蚁移动过程中受重视的程度，其值越大，则转移概率越接近于贪婪规则。α,β∈[1,5]。则强度更新方程为:
式中，Δτij反映区域(i,j)蚂蚁在某次移动完后吸引强度即信息素浓度的增加；Q表示信息素调节因子，调节信息素增加的速度，它在一定程度上影响算法的收敛速度，0
可见，当区域足够小，蚂蚁数量足够大，即在g-C平面中每个点对应一只蚂蚁时，就变成了穷尽搜索。因此，最佳目标值的寻找是借助M×N只蚂蚁的不断移动来进行的。
为了避免重复计算，提高计算效率，对于已经计算过的目标值向量不再计算，同时，记录各个区域的最优值。
基于蚁群算法的最优值选取步骤如下：
(1)将迭代次数count置0；对所有τij和τij初始化。
(2)将M×N只蚂蚁置于各区域中，每个蚂蚁按概率pij移动至其他区域或在本区域内搜索。
(3)以每只蚂蚁对应向量计算目标值，并记录各区域的最优解。
(4)计算Δτij，按更新方程(4)更新各区域的吸引强度。
(5)count←count+1，若count小于预定的迭代次数，则返回到(2)。
(6)输出目前的最优解。
3 空间目标分类
本文采用实测数据对空间目标进行分类，由于篇幅和保密的原因，本文只列出以下具有代表性的四组两种目标类型的RCS序列，如图1所示。
本文基于非线性理论提取空间目标RCS序列的特征。为了便于分类，选择能够定量描述的特征，如关联维数[7]、Kolmogorov熵[8]、最大Lyapunov指数[9]、功率谱指数[10]、盒维数[11]、Hurst指数[12-13]等，舍弃只能定性描述而不能够定量描述的特征，本文选择的相关特征及所列出的空间目标RCS序列的特征值如表1所示，计算过程详见相应参考文献。
为了提高识别的正确率，对于每种目标，应努力获取尽可能多的空间目标RCS序列作为训练样本。考虑到保密的原因，本文只能获得30组空间目标RCS序列。任意抽取20组作为训练样本，其余10组为测试样本。采用传统的径向基函数作为核函数进行训练。最后分类的结果为90%，也就是说，10个测试样本中只有一个样本被误分。表2是核参数、惩罚因子和分类正确率随迭代次数的变化表。图2是运用蚁群算法在优选参数过程中分类正确率的变化曲线图。表3是采用单一特征所得的惩罚因子、核函数参数和分类正确率。由表3可以看出，无论采用哪一类特征，其分类的正确率都要低于基于特征融合的分类正确率，也就是说，采用特征融合的分类效果要好于采用单一特征。
本文将蚁群算法与特征融合相结合，提出了一种优选支持向量机参数的方法，克服了以往反复试验以确定其参数的缺点，节省了工作量。同时，采用特征融合来替代单一特征，克服了抽取单一种类的特征进行目标识别误识率较难降低且抗干扰性不易提高的问题。利用实测的空间目标RCS序列进行实验，分类正确率达90%，说明基于蚁群算法和特征融合的方法是有效的，具有一定的实际应用价值。
参考文献
[1] 何远航，王 萍. 空间碎片环境的研究与控制方法[J].中国航天，2003(7)：27-31.
[2] VAPNIK V N.The nature of statictical learning theory[M].
2th ed, New York: USA Springer,1999.
[3] KEERTHI S S, LIN C J. Asymptotic behaviors of support vector machines with gaussian kernel[J]. Neural Computation,2003,15(7):1667-1689.
[4] DORIGO M， MANIEZZO V， COLORNI A. Ant system:optimization by a colony of coorperating agents. IEEE Transactions on Systems,Man ,and Cybernetics-Part B，1996，26(1):29-41.
[5] 段海滨. 蚁群算法原理及其应用[M].北京：科学出版社,2005.
[6] 王春林，周昊，周樟华,等. 基于支持向量机的大型电厂锅炉飞灰含碳量建模[J]. 中国电机工程学报，2005，25(20):72-76.
[7] GRASSBERGER P，PROCACCIA I. Characterization of strange attractors[J]. Phys Rev Lett，1983，50:346-355.
[8] BENETTIN G G, SGRELCYN J M. Kolmogorov entropy and numerical experiments. Phys Rev, A, 1976，14：2338-2345.
[9] ROSENSTEIN M T，COLLINS J J. A practical method for calculating largest lyapunov exponents from small data sets[J]. Physica D，1993(65):117-134.
[10] SHAW R. Strange attractors, chaotic behavior,and information flow. Z. Naturf. 1981,36a:80-112.
[11] MANDELBROT B B. The fractal geometry of nature[M]. San Francisco:Freeman,1982.
[12] MANDELBROT B B，WALLIS J R. Some long-run properties of geographysical records[J]. Water Resource Research，1969，5(2):321-340.
[13] MANDELBROT B B，Wallis J R. Robustness of the rescaled ranged R/S in the measurement of noncyclic long-run statistical dependence[J]. Water Resource Research，1969，5(5):967-988.