维普资讯 http://www.cqvip.com 第３８卷第３期 航空计算技术 Ｖ０１．３８ Ｎｏ．３ ２００８年５月 Ａｅｒｏｎａｕｔｉｃａｌ Ｃｏｍｐｕｔｉｎｇ Ｔｅｃｈｎｉｑｕｅ Ｍａｖ．２００８ 基于支持向量机和蚁群算法的空间目标分类 （西北工业大学航天学院，陕西西安７１００７２）盛 曹占辉，李言俊 摘要：研究了基于支持向量机的空间目标分类中核参数和误差惩罚因子的选择问题。将蚁群算 法与支持向量机相结合，提出了一种自动优选支持向量机模型参数的方法，克服了以往反复试验以 确定其参数的缺点。采用所提出的方法，分类正确率达９０％左右，验证了该方法的有效性。 关键词：空间目标；支持向量机；蚁群算法 中图分类号：ＴＰ３９１．４１ 文献标识码：Ａ 文章编号：１６７１・６５４Ｘ（２００８）０３・００１５・０４ 引言 个“瓶颈”问题。传统的参数选取方法多是采用反复 随着人类航天活动越来越频繁，１３益增长的空间 试验的方法确定，这需要很大的工作量。 碎片对人类航天活动构成了严重的威胁，逐步恶化的 本文提出了一种基于蚁群算法优选ＳＶＭ参数的 空间环境使卫星的发射和监测面临越来越严峻的挑 方法，并将其在空间目标分类中运用。在实验中，参数 战＿１ Ｊ，因此，为了确保航天活动的安全可靠，保护本国 选取所花费的工作量大大减少，识别率达９０％，实验 太空安全，如何有效对空间目标（卫星、碎片等）进行 结果证明了该方法的有效性。 监视、识别和编目，对于维护国家安全和促进人类的航 天活动都具有重要意义。 １支持向量机 由于空间环境复杂多变，影响空间目标的因素较 支持向量机在解决小样本、非线性及高维模式识 多，导致所得的空间目标的数据在特征空间中的距离 别问题中表现出许多特有的优势，已经在模式识别、函 变小，普通距离分类器的推广能力变弱。另外，由于保 数逼近和概率密度估计等方面取得了良好的效果。支 密的原因，不可能获得大量的相关数据，即分类的样本 持向量机从本质上讲是一种前向神经网络，根据结构 较少，这样导致普通的分类器无能为力。因此，如何提 风险最小化准则，在使训练样本分类误差极小化的前 高分类器的泛化和推广能力，就成为空间目标识别研 提下，尽量提高分类器的泛化推广能力。 究的关键问题之一。 在分类问题中，如果输入空间数据可以用一个空 由Ｖａｐｎｉｋ等 人提出的统计学习理论是一种专 间曲面进行划分，则称这个曲面为输入数据空间的一 门的小样本统计理论，着重研究在有限样本情况下的 个分离曲面。当一个分离曲面不但能将输入数据空间 统计规律及学习方法。２０世纪９０年代，在统计学习 的两类数据正确分开，而且使两类间的间隔最大，则称 理论的基础上发展出了支持向量机（Ｓｕｐｐｏｒｔ Ｖｅｃｔｏｒ 这一曲面为最优分离曲面。如果输入数据空间是非线 Ｍａｃｈｉｎｅｓ，简称ＳＶＭ），它表现出很多优于已有方法的 性不可分的，则需要找到一个超曲面实现以下目标：一 分类性能，在解决小样本学习、非线性及高维模式识别 是使两类数据间的间隔尽可能大；二是希望错划程度 的问题中表现出许多特有的优势。 尽可能小。能实现这两个目标的超曲面称为广义最优 作为一门新兴的学科，ＳＶＭ存在一些尚未完善的 分界曲面。支持向量机提供了寻找这样一个最优分离 地方，其参数选取就是亟待解决的问题之一。参数选 曲面的一种方法，其基本思想是作非线性映射 （ ）， 取的好坏直接地影响分类器泛化性能好坏，因此，如何 将输入的数据空间尺 映射到一个高维的内积空间Ｆ， 选取参数常被认为是ＳＶＭ从理论走向实际应用的一 然后在Ｆ中实现线性划分。而在空间Ｆ中的内积通 收稿日期：２００８．０３－０３ 修订日期－２００８—０４．２３ 基金项目：国家自然科学基金（６０５７５１０３） 作者简介：曹占辉（１９７７一），男，河北枣强人，博士研究生，研究方向为图像和雷达信号处理。 维普资讯 http://www.cqvip.com 航空计算技术 第３８卷 第３期 过一个核函数Ｋ（ｘ， ’）实现，即 （ ‘）・ （ ）＝Ｋ（ｘ ， ｆ） 多，就能达到 的效果；当 比训练样本之间的 。。的效果。基于 最大间隔大得多时，就可以达到 选择满足Ｍｅｒｃｅｒ条件的不同内积核函数，就构造 了不同的支持向量机，这样也就形成了不同的算法。 目前研究最多的核函数主要有三类： １）多项式核函数 这一考虑，实验中，本文确定 的搜索空间为： ［ｍｉｎ（１ — ，ｌｌ ）×１ｌ０一 ，ｍａｘ（１ — ，ｌｌｌ ）×１０ ］ 在构造分类面方程时惩罚因子ｃ的作用是对拉格 朗日因子 的取值加以限制。当ｃ超过一定值时就 （１） 丧失了其对 取值的约束作用，相应的支持向量机的 复杂度也达到了数据子空间所允许的最大值，此时，经 Ｋ（ｘ， ）＝［（ ・ ｉ）＋１］ 其中ｇ是多项式的阶次，所得到的是ｇ阶多项式分类 器。 ２）径向基函数（又称为高斯核函数） （ ）：ｅｘｐ（一 ） （２） ３）形核函数 Ｋ（ｘ， ）＝ｔａｎｈ［ｖ（ｘ・ ）＋ｃ］ （３） ２参数范围的确定 由于有多种核函数，设计支持向量机的一个重要 步骤就是选择核函数和核参数。Ｖａｐｎｉｋ等人在研究 中发现，不同的核函数对支持向量机性能的影响不大， 反而核函数的参数和误差惩罚因子ｃ是影响支持向 量机性能的关键因素。就函数拟合而言，径向基函数 的函数拟合性能要优于多项式核函数，能使支持向量 机以任意精度逼近非线性函数曲线。因此，目前使用 最广泛的是径向基函数，下文讨论的核参数是指径向 基函数的参数 。 ｃ用于控制模型复杂度和逼近误差的折中，ｃ越 大则对数据的逼近误差越小，但模型也越复杂，学习机 器的推广能力越也越差。 用于控制回归逼近误差的大小，从而控制支持 向量的个数和泛化能力，其值越大，则支持向量数越 少，但精度不高，否则，支持向量数越多，精度越高。 由于没有理论做指导，传统的参数选取都是通过 反复的试验，人工选取出令人满意的解。这种方法需 要人的经验做指导，并且它的选取需要付出较高的时 间代价，因此传统的参数选取方法并不能适应支持向 量机的发展。 Ｋｅｅｒｔｈｉ的研究表明 ］，对于某一确定的足够大的 ｃ，当 时，会发生严重的“过学习”现象，此时径 向基函数支持向量机能把训练样本正确分开，但对测 试样本不具有任何推广能力；当 。。时，会发生严 重的“欠学习”现象，此时径向基函数支持向量机把所 有训练样本都划分到样本数较大的一类。从核函数 Ｋ（ｘ ， ）＝ｅｘｐ（～ｌ ｌ￡一 『ｌ ｌ／ ）可以看出， 的大 小完全是针对『Ｉ — 『ｆＩ 而言的。因此，在实际应用 中，只要 的取值比训练样本之间的最小距离小得 验风险和推广能力几乎不再发生变化。为此采取了如 下的启发式思维确定ｃ值（例如１００００），用其训练支 持向量机求解出一组 （ｉ＝１，２，…，￡），其中￡为训练 样本总数，令ｃ 作为ｃ的取值上限。否则说明ｃ仍 对 的取值构成约束，换一个更大的ｃ训练支持向量 机，直至等到的ｃ 远小于ｃ为止。这样就得到了ｃ 的搜索空间（０，Ｃ ）。 期望在分类精度接近条件下获得结构尽可能简单 的分类面，所以在设计目标函数的时候，附加了两个复 杂度控制项Ｃ。Ⅳｌ／ｎ。和 Ⅳ２／ ，此时，目的函数为： ｍ，２ ｎ、 １ ，．、 Ｌ ，Ｌ Ｌ珥 式中，Ｅ是支持向量机在训练样本集上的错分率，Ⅳｌ， Ⅳ２，ｎ ，ｎ 分别对应两类的支持向量数和训练样本数。 ｃ 和ｃ 值可取得较小，从而弱化分类面复杂度在适 值函数中的比重；当对结构的简单性要求较高、对精度 要求一般时，可相应地增加ｃ 和ｃ 。 ３基于蚁群算法的参数优化 蚁群算法（Ａｎｔ Ｃｏｌｏｎｙ Ｏｐｔｉｍｉｚａｔｉｏｎ，简称ＡＣＯ）是 意大利学者Ｍ．Ｄｏｒｉｇｏ等人 于２０世纪９０年代通过 模拟蚁群的觅食行为提出的一种新型模拟进化算法， 它运用了正反馈、分布式计算和贪婪式启发式搜索。 该算法适应性强，不用计算目标函数偏导数，搜索效率 高，寻优能力突出，克服了其他算法容易陷入局部最优 的缺点。签于以上优点，本文采用蚁群算法来实现对 核函数参数 和误差惩罚因子ｃ的优化搜索。 文献［６］指出，单独调整核函数ｇ和惩罚因子Ｃ 都可以使模型的推广能力得到提高，但如要同时获得 小的经验风险就必须两个参数综合调整。因此本文设 定ｇ为横坐标，ｃ为纵坐标，在ｇ—Ｃ平面上寻优。 在取值范围内将ｇ—Ｃ平面平分等分成Ｍ×Ｎ子 块（以下称区域），区域大小为ｍ×ｎ，其中ｍ＝￡／ ， ｎ＝Ｌ／Ｎ（为了保证各区域内目标函数值相差不会太 大，避免陷入局部最优，区域的形状应尽量保证是正方 形，即ｍ＝ｎ）。 每个区域分配一只蚂蚁，则共有Ｍ×Ｎ只蚂蚁，初 维普资讯 http://www.cqvip.com ２００８年５月 曹占辉等：基于支持向量机和蚁群算法的空间目标分类 始时刻，蚂蚁在各区域的中心点或最靠近中心的某一 点。蚂蚁的转移概率定义为： （ｒｆ ） （ （￡ ））卢 域的最好解； ４）计算Ａｒ¨按更新方程（６）更新各区域的吸引 强度； ∑（ｒ ） （ （ｉｔｉｌ ） ｉ：∈｛１，２，…， ｝， ∈｛１，２，…，Ⅳ｝ （５） ５）ｃｏｕｎｔ＋－－ｃｏｕｎｔ＋１，若ｃｏｕｎｔ＜预定的迭代次数，则 返回到２）； ６）输出目前的最优解。 ｒ 称区域（ｉ， ）的吸引强度，即信息素的浓度，在 初始时刻，每个区域信息素的量都是相等的，设ｒ （０） ＝４空间目标分类 雷达散射截面（Ｒａｄａｒ Ｃｒｏｓｓ Ｓｅｃｔｉｏｎ，简称 Ｃ（Ｃ为一定常数）。令ｔａｒｇｅｔ（ｓ，ｔ）是以（ｓ，ｔ）计算得 到的目标值， （ ）（ ）定义为ｍａｘ｛ｔａｒｇｅｔ（ｓ， ），（ｓ， ）∈ ｔａｂｕｋ（ｉ２，Ｊ。２）｝一，ｍａｘ｛ｔａｒｇｅｔ（ｓ，ｔ），（ｓ，ｔ）∈ｔａｂｕｋ（ｉｌ， ＾）｝即以两个区域中的向量为计算得到的最大目标值 之间的差值，表示区域（ｉ ，＾）中的蚂蚁向区域（ｉ：， ） 转移的期望程度。当 （ 『１）（ｉ ｂ）≥０时，区域（ 。， 。）的 蚂蚁按概率Ｐ 移动至区域（ｉ２，Ｊ２）；当＂ｑ（ｉｌＪ１）（ｉ２／２）＜０时， 区域（ｉ。， 。）中的蚂蚁在本区域中搜索，即蚂蚁要么移 动至其他区域，要么在本区域中搜索，ｔａｂｕｋ（ｉ，Ｊ）表示 区域（ｉ， ）中已经计算过的向量。Ｏ／为信息启发式因 子，反映了各区域信息素浓度即ｒ 在蚂蚁运动过程中 所起的作用，其值越大，蚂蚁之间的协作性越强。 为 期望启发式因子，反映了启发信息即Ｔ￣（ｉｌＪ１）（ｉ２ｊ２ 在蚂蚁 移动过程中受重视的程度，其值越大，则转移概率越接 近于贪婪规则。 ， ∈［１，５］。 强度更新方程为 ｒｆｔ“＝ｆ（１－ｐ）ｒ ＋Ａｒ （６） Ａｒ ＝Ｑ×Ｌ （７） 其中Ａｒ 反映区域（ｉ，Ｊ）蚂蚁在某次移动完后吸引强 度即信息素浓度的增加，Ｑ表示信息素调节因子，调节 信息素增加的速度，它在一定程度上影响算法的收敛 速度，０＜Ｑ＜１００００。 表示某次移动完成后区域（ ， ）中蚂蚁的数量。为了避免残留信息素过多引起残留 信息淹没启发信息，我们引入信息素挥发系数Ｐ，０≤ｐ ＜１，根据经验，取０．７为最佳。 可见，当区域足够小，蚂蚁数量足够大，即在ｇ—Ｃ 平面中每个点对应一只蚂蚁时，就变成了穷尽搜索。 因此，最佳目标值的寻找是借助Ｍ×Ｎ只蚂蚁的不断 移动来进行的。 为了避免重复计算，提高计算效率，对于已经计算 过的目标值向量不再计算，同时，记录各个区域的最优 值。 基于蚁群算法的最优值选取步骤为： １）将迭代次ｃｏｕｎｔ数置０；各ｒ 和Ａｒ 初始化； ２）将Ｍ×Ｎ只蚂蚁置于各区域中，每个蚂蚁按概 率ｐ ，移动至其他区域或在本区域内搜索； ３）以每只蚂蚁对应向量计算目标值，并记录各区 ＲＣＳ） ］，是表征雷达目标对于照射电磁波散射能力的 一个物理量，是雷达目标特性中最基本最重要的一个 参数。 本文采用实测数据对空间目标进行分类，由于篇 幅和保密的原因，本文只列出以下具有代表性的四组 两种目标类型的ＲＣＳ序列，如图１所示。 （ａ）旋转目标ｌ （ｂ）旋转目标２ ｆｃ）ｓ－轴稳定目标ｌ ｆｄ）Ｓ－轴稳定目标２ 图ｌ空间目标ＲＣＳ序列图 本文基于非线性理论提取空间目标ＲＣＳ序列的特 征。为了便于分类，应该选择能够定量描述的特征，如 关联维数、最大Ｌｙａｐｕｎｏｖ指数等，舍弃只能定性描述而 不能够定量描述的特征，本文选择以下特征对空间目标 维普资讯 http://www.cqvip.com 航空计算技术 第３８卷 第３期 进行分类，相关特征及相应的特征值如表１所示。 表１标定结果统计表 考虑到保密的原因，本文只能获得３０组空间目标ＲＣＳ 序列。任意抽取２０组作为训练样本，１０组为测试样 本。采用传统的径向基函数作为核函数进行训练。最 后分类的结果为９０％，也就是说，１０个测试样本中只 有一个样本被误分。表２是核参数、惩罚因子和识别 率随迭代次数的变化表。图２是运用蚁群算法在优选 参数过程中识别率的变化曲线图。 ５ 结论 本文将蚁群算法与支持向量机相结合，提出了一 表２支持向量机参数变化表 种优选支持向量机参数的方法，克服了以往反复试验 以确定其参数的缺点，节省了工作量。利用实测的空 间目标ＲＣＳ序列进行实验，分类正确率达９０％，说明 基于蚁群算法的支持向量机优选方法是有效的，具有 一２ 定的实际应用价值。 ３ １Ｊ １Ｊ ｒＬ ｒＬ ｒＬ ｒＬ ｒＬ ｒ１Ｊ４ ５ １Ｊ ６ １Ｊ ７１参考文献： ［１］ 何远航，王萍．空间碎片环境的研究与控制方法［Ｊ］．中国 航天，２００３（７）：２７—３１． Ｖａｐｎｉｋ ＶＮ．Ｔｈｅ ｎａｔｕｒｅ ｏｆ ｓｔａｔｉｃｔｉｃａｌ ｌｅａｒｎｉｎｇ ｔｈｅｏｒｙ（Ｓｅｃｏｎｄ Ｅｄｉｔｉｏｎ）［Ｍ］．Ｓｐｒｉｎｇｅｒ，Ｎｅｗ Ｙｏｒｋ，ＵＳＡ，１９９９． Ｋｅｅｒｔｈｉ Ｓ Ｓ，Ｌｉｎ Ｃ Ｊ．Ａｓｙｍｐｔｏｔｉｃ ｂｅｈａｖｉｏｒｓ ｏｆ ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅｓ ｗｉｔｈ Ｇａｕｓｓｉａｎ ｋｅｒｎｅｌ［Ｊ］．Ｎｅｕｒａｌ Ｃｏｍｐｕｔａｔｉｏｎ， ２００３，１５（７）：１６６７—１６８９． 、 Ｄｏｒｉｇｏ Ｍ，Ｍａｎｉｅｚｚｏ Ｖ，Ｃｏｌｏｒｎｉ Ａ．Ａｎｔ Ｓｙｓｔｅｍ：Ｏｐｔｉｍｉｚａｔｉｏｎ ｂｙ ａ Ｃｏｌｏｎｙ ｏｆ Ｃｏｏｒｐｅｒａｔｉｎｇ Ａｇｅｎｔｓ，ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｓｙｓｔｅｍｓ，Ｍａｎ．ａｎｄ Ｃｙｂｅｒｎｅｔｉｃｓ—Ｐａｒｔ Ｂ，１９９６，２６（１）：２９— ４１． 迭代次数 段海滨．蚁群算法原理及其应用［Ｍ］．北京：科学出版社， ２０ｏ５． 图２识别率变化曲线 王春林，周昊，周樟华等．基于支持向量机的大型电厂锅 炉飞灰含碳量建模［Ｊ］．中国电机工程学报，２００５，２５ 为了提高识别的正确率，对于每种目标，应尽可能 的获取尽可能多的空间目标ＲＣＳ序列作为训练样本。 （２０）：７２—７６． 黄培康，殷红成，许小剑．雷达目标特性［Ｍ］．北京：电子 工业出版社．２００５． Ｓｐａｃｅ Ｏｂｊｅｃｔ Ｃｌａｓｓｉｉｆｃａｔｉｏｎ Ｂａｓｅｄ ｏｎ ＳＶＭ ａｎｄ ＡＣＯ ＣＡＯ Ｚｈａｎ—ｈｕｉ，ＬＩ Ｙａｎ—ｊｕｎ （Ｓｃｈｏｏｌ ｏｆＡｓｔｒｏｎａｕｔｉｃ，Ｎｏｒｔｈｗｅｓｔｅｒｎ Ｐｏｌｙｔｅｃｈｎｉｃａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉ ａｎ ７１００７２，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｓｅｌｅｃｔｉｏｎ ｐｒｏｂｌｅｍ ｏｆ ｋｅｒｎｅ１．ｐａｒａｍｅｔｅｒ ａｎｄ ｅｒｒｏｒ ｐｕｎｉｓｈ ｉｎｄｅｘ ｉｓ ａｎａｌｙｚｅｄ．Ａｎ ｏｐｔｉｍｉｚａｔｉｏｎ ｍｅｔｈｏｄ ｂａｓｅｄ ｏｎ ｔｈｅ ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ ｉｓ ｕｓｅｄ ｔｏ ｓｅｌｅｃｔ ｔｈｅ ｔｗｏ ｐａｒａｍｅｔｅｒｓ．Ｉｔ ａｖｏｉｄｓ ｒｅｐｅａｔｉｎｇ ｅｘｐｅｒｉｍｅｎｔｓ ｔｏ ｄｅｔｅｒｍｉｎｅ ｔｈｅ ｔｗｏ ｐａｒａｍｅｔｅｒｓ．Ｗｉｔｈ ｔｈｅ ｎｅｗ ｄｅｓｉｇｎｅｄ ＳＶＭ，ｔｈｅ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｏｆ ｓｐａｃｅ ｔａｒｇｅｔｓ ｉｓ ｅｆｆｅｃｔｉｖｅ． Ｋｅｙ ｗｏｒｄｓ：ｓｐａｃｅ ｏｂｊｅｃｔ；ｓｕｐｐｏｒｔ ｖｅｃｔｏｒ ｍａｃｈｉｎｅ（ＳＶＭ）；ａｎｔ ｃｏｌｏｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ（ＡＣＯ） ．
