文档介绍：多类ＳＶＭ分类算法的研究和改进
　　摘要：介绍分析了SVM基础理论和目前多类SVM分类算法及其优缺点，提出了一种边界向量抽取算法，并基于该算法改进了1ar和1a1两种多类SVM算法。实验结果表明该边界向量抽取算法可以有效的减少训练样本的数量，在保持分类器推广能力的条件下缩短SVM的训练时间，特别是在大样本训练数据时1arΔ可以提供最好的训练性能。
　　关键词：向量机；多类支持向量机；支持向量；边界向量；分类
　　中图分类号：TP391文献标识码：A文章编号：1009-3044(2007)06-11590-04
　　
　　1 引言
　　支持向量机（SVM）最初是作为二类问题分类提出来的，然而在实际应用中，人们所面对的问题更多的则是多类分类问题，为此很多研究者提出了多类SVM分类算法，该算法也是当今SVM算法的研究重点之一。多类SVM算法的实现思想主要有两种：
　　(1)通过某种方式把多类分类问题分解为多个二类分类问题，该方法需要对训练样本进行重新分配，使得样本符合新的多个二类问题分类的需要，同时根据算法的实现采取不同策略决定测试样本所属类别。比较常用且性能较好的此类算法有one-against
-rest、one-against-one、DAG、二叉树算法等，在这些算法的基础上又提出了一些改进的算法，如ACDMSVM[1]、MACM[2]、基于聚类的二叉树[3]、基于超球体或超方体的二叉树[4]等。这些改进的算法有的提高了多类SVM分类器的分类精度和推广能力，有的有效地加快了分类器训练和预测的速度。
　　(2)把多个分类面的求解合并到一个最优化问题中，该方法是二类问题的推广，一次性的求解一个大的二次规划问题，直接将多类问题同时分开[6]。该方法虽然比第一种思想简单，但其算法复杂度大大增加，需要更多的变量，训练时间较长，推广能力也不比第一种方法更优，不适合应用于大规模的数据样本。
　　可以看出，上述多类SVM算法思想都要考虑两个非常重要的问题：
　　(1)尽可能提高多类SVM分类算法的推广能力和分类精度。由于多类SVM分类算法是由二类SVM算法推广而来，其本身就存在如何提高推广能力的问题，推广到多类以后，不同的多类SVM算法实现，分类精度就有不同的扩散影响。
　　(2)尽可能减少多类SVM分类器算法的执行时间，包括训练和预测时间。根据多类SVM分类器的使用场合可能采取不同的策略：有时要有高效的训练速度，另一种情况是对分类器预测的响应速度非常敏感，需要大大减少分类器对测试样本的分类响应时间。
　　对于多类SVM算法，在相同训练样本和测试样本情况下，分类器消耗的训练时间和预测时间与其实现方法有很大关系，不同实现方法需要的时间可能相差很大。前面两个问题需要整体考虑，精度和速度的提高本来就是互相矛盾的，当然同时得到提高是最好的。本文在介绍分析SVM基础理论和各类多类SVM分类算法优缺点的基础上，提出一种边界向量抽取算法，将其应用到一对一和一对多多类SVM分类算法，实验证明该方法可以提高训练速度而不失较高的推广能力，在大样本情况下训练速度提高更明显。
　　
　　2 支持向量机（SVM）简介[9]
　　统计学****理论是支持向量机的理论基础，该理论由Vapnik等人提出，是一种专门研究小样本情况下机器学****规律的理论。支持向量机的实现是保持经验风险值固定，最小化置信范围，取得实际期望风险的最小化，而神经网络是保持置信范围固定，最小化经验风险。神经网络的解可能是局部极小值，但SVM可得全局最优解。随着该理论的不断发展和成熟，同时也因神经网络等学****方法在理论上缺乏实质性进展，SVM开始受到越来越广泛的重视。
　　支持向量机的具体实现思想是通过某种非线性映射把输入向量x映射到高维特征空间Z，在这个新空间中构建最优分类超平面。映射的原因是无法把训练样本在原来的空间中线性可分，但这也带来一个技术问题，这种映射会大大增加向量的特征空间的维数，既
“维数灾难”。
　　根据最优分类超平面的构造原理可知公式(1)，l为样本向量的个数，
　　公式(1)使支持向量机的训练问题变为一个简单的二次规化问题，即在满足约束条件ai≥0,1...,l 和情况下求解a0最大化W(a)，结果可得大部分ai0为0，不为0的样本向量称为支持向量，假设a0=(a10,...,al0)，且ai0≠0,(i=1,...,l)，可得最优超平面的向量，基于最优超平面的分类规则的指示函数是，
　　上面公式讨论中(xi?x)表示向量的内积，如果训练样本线性可分计算内积没有任何困难，但如果线性不可分就需要映射到高维处理，设Z=Φ(x)，定义x→Φ(x)为x到空间的映射，则公式(1)和(2)变为，