支持向量机与纠错编码相结合的多类分类算法

《支持向量机与纠错编码相结合的多类分类算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2003年8月西北工业大学学报Aug．2003第21卷第4期JournalofNorthwesternPolytechnicalUniversityVo1．21No．4支持向量机与纠错编码相结合的多类分类算法夏建涛，何明一(西北工业大学陕西省信息获取与处理重点实验室．陕西西安710072)摘要：提出了一种基于纠错编码的支持向量机多类分类算法(ECC—SVM)，并在理论上研究了该算法的推广性与编码长度、码间汉明距离、编码顺序以及每个SVM推广性之间的关系，给出了这种关系的数学表达，为提高该算法的推广能力指明了方向。把目前广泛使用的1一v—RSVM多类分类算法

2、作为该算法的一个特例，分析了它的推广性。计算机仿真数据和多光谱遥感图像分类实验结果表明，ECC—SVM具有更快的分类速度和更高的分类精度，同时验证了本文理论分析的正确性。关键词：支持向量机(SVM)，纠错编码(ECC)．多类分类，推广性，1一v—RSVM中图分类号：TP391．4，TN911．7文献标识码：A文章编号：1000—2758(2003)04—0443—06支持向量机(SVM)是近几年发展起来的一种一种把多类分类问题转化为多个两类分类问题的方学习机器口]，它以强的推广能力受到越来越多人的法B]。K类数据分类问题，对每个类进行长度为L青睐。但SVM

3、是针对两类分类问题设计的，不能直的二进制编码，就把类分类问题转化为L个两类接用于多类分类问题。而实际的模式识别问题绝大分类问题。由于每个码位上的分类器只需要做两类多数都是多类分类问题，所以目前SVM难以用来分类，所以可以采用SVM作为码位分类器。对于一解决实际的模式分类问题。为了克服这个缺陷，人们个新样本，L个SVM的分类结果构成一个码字s，K对SVM多类分类方面进行了大量的研究．提出了个编码中与s汉明距离最小的码字所代表的类别就一些有效的SVM多类分类算法[2]。但这些算法中是这个新样本所属类别。把对数据进行ECC编码大部分的推广性都没有得到分析，使得人

4、们无法有后，采用SVM作为码位分类器的多类分类方法称效地使用这些算法获取更好的分类结果。本文提出为ECC—SVM多类分类算法。有效的ECC编码必须了一种基于纠错编码[5的SVM多类分类算法满足两个条件：①编码矩阵的行之间不相关；②编(ECC—SVM)码矩阵的列之间不相关且不互补。因此对于K类分类问题，编码长度L必须满足log。K

5、问题的ECC—SVM类别类⋯别．码字———_一收稿日期：2002—06—17基金项目：国家973计划和教育部博士点基金作者简介：夏建涛(1975一)，西北工业大学博士生，主要从事遥感图像处理、机器学习等的研究。·444·西北工业大学学报第21卷ECC—SVM算法中，第i个SVM训练样本的组12(2m)·M·N·K!]g2—————一j成是把编码矩阵中第列取值为0的所有类别的样本归为第1类，把取值为1的所有类别的样本归为式中，D一∑1，M—IL一生l。N是码长i=1lL一第2类。为L、码间汉明距离为d的编码组数，每一组中有K个码字，R是包含m个样本的最小球半

6、径。2推广性分析定理2的证明见附录。从定理2可以看出，ECC—SVM的推广能力不是由推广性最差的SVM采用VC理论和fat—shattering维概念对的分类精度决定，而是由前M个推广性好的SVMECC—SVM推广性进行分析，可以得到它与编码长的分类精度决定。编码长度和码间最小汉明距离会度、码间汉明距离、编码顺序以及SVM分类间隙之影响M，从而影响推广能力。编码顺序对分类间隙间的关系。这为人们研究如何提高ECC—SVM的分有一定的影响，因此也会影响推广能力。类能力提供了理论指导。目前被广泛使用的1一v—RSVM多类分类算法对于ECC—SVM的推广性，可以有

7、下面的结可以看作采用表2中编码的ECC—SVM。它是ECC—论：SVM的一个特例，编码长度为K(与类别数相同)，定理1对于K个类别的分类问题，ECC的码码间汉明距离为2，所以1一v—RSVM采用的编码不长为L．码间最小汉明距离为d。依据未知概率分布具有纠错功能。P产生的m个样本(记为)的最小包容球半径为表2l—v．RSVM采用的编码R。如果ECC—SVM能够把m个样本完全正确分类，L个SVM的分类间隙由大到小排列，分别记为，r。，⋯，，令k。一fat(／8)，i一1，2，⋯，L。那么对于由P新产生的m个样本(记为y)，有Pz”‘fy：一ECC—SVM：把⋯

8、正确⋯分⋯类，1}<，I则把y错分的比例>e(，L，d，)J式中1