论文部分内容阅读
新乡职业技术学院 河南新乡 473000
摘要：支持向量机是一种新的机器学习方法，由于其出色的学习性能，该技术已成为当前国际机器学习界的研究热点。对SVM训练算法的最新研究成果进行了综述，着重说明了各种的算法的思路和优缺点。总结了支持向量机理论及其应用的现状，对支持向量机的未来发展方向进行了展望。
关键词：支持向量机；训练算法；分类
Abstract：Support Vector Machines are a kind of novel machine learning methods，which have become the hotspot of machine learning because of their excellent learning performance.This paper made a summarize of the new pro gress in the SVM training of algorithm，focused on the ideas of various algorithms，pointed out the advantages and disadvantages of them.The status quo of SVM theory and its applications are summarized and the future development direction of SVM theory is expected.
Keywords：Support vector machine；raining algrithm；categorizing；
支持向量机（Support Vector Machine，SVM）是Vapnik等1995年提出的一种基于统计学习理论[1]的模式识别方法。它在解决小样本、非线性和高维模式识别问题中具有特有的优势，且在某种程度上克服了维数灾难和过度学习等传统难题，另其具有坚实的理论基础、简明的数学模型，使得支持向量机自提出以来受到广泛的关注，并取得了长足的发展。
1 支持向量机的训练算法
（1）块算法与分解算法
块算法（chunking algorithm）[2]最早是由Boser等人提出来的。它的出发点是删除矩阵中对应于Lagrange乘子为零的行和列不会对最终结果产生影响。对于给定的样本，块算法的目标就是通过某种迭代方式逐步排除非支持向量。块算法将矩阵的规模从训练样本数的平方减少到具有非零Lagrange乘子的样本数的平方，从而降低了训练过程对存储容量的要求。这种方法只要支持向量远远小于训练样本。但是，随着算法迭代次数的增多，训练样本集规模也会越来越大，算法依旧会变得十分复杂。
Osuna等人提出的分解算法（decomposition a1.gorithm）[3]，是目前有效解决大规模问题的主要方法。主要思想是将训练样本分成工作集 B 和非工作集 N，并保持大小不变。该算法的关键是如何最优的选取工作集B。Joachims利用SVMlight提高算法收敛速度，是目前设计SVM分类器的重要软件。
除了分解算法，还有Huber近似算法、多拉格朗日乘子协同优化算法|、剪枝算法等SVM的求解方法。
（2）序贯最小优化算法
由Platt提出的序列最小优化（sequential mini—real optimization，SMO）[4]算法是分解算法是针对工作集的个数为2的特殊情形，即SMO把一个大的优化问题分解成一系列只含两个变量的优化问题。两个变量的最优化问题可以解析求解，因而不需要迭代地求解二次规划问题。对分类SMO算法，Keerthi等人修正了优化条件，并针对经验方法提出两个改进措施，以保证算法收敛和减少迭代次数。随后Keerthi等人引提出了广义SMO（generalized SMO，GSMO）算法，利用违反对的概念确定工作集，指出前面两种改进都是GSMO的特例，并证明，对任意的t﹥0以τ违反对为工作集，则GSMO算法有限终止，得到优化问题的τ近似优化解.Lin对SMO算法的渐进收敛性进行了证明。
（3）模糊支持向量机
模糊支持向量机（Fuzzy SVM，FSVM）算法将模糊逻辑的方法与支持向量机的学习方法相结合，该算法给每个训练样本都赋与相应的模糊隶属度，这样不同的樣本对决策函数的学习有不同的贡献，可以降低噪声对最优超平面的影响。
（4）粒度支持向量机[ 5]
粒度支持向量机是Y.C.Tang提出的一种新的训练算法，其主要思想是通过粒划分来构建粒空间获得一系列信息粒，然后在每个信息粒上进行学习，最后通过聚合信息粒上的信息（如数据、规则、知识、属性等）获得最终的SVM 决策函数。如何进行粒度划分是粒度支持向量机研究的主要问题。目前，主要有基于关联规则的粒度支持向量机，利用聚类方法对训练样本集进行粒度划分的基于聚类的粒度支持向量机，基于商空间的粒度支持向量机的基本思想是首先对训练样本集进行粗粒度的选择SV，去除一部分对构造最优分类超平面无用的样本点，然后再对粗选后的样本进行细粒度的 SV 训练。此外还有基于树形层次结构的粒度支持向量机等。
（5）多分类支持向量机
SVM起初主要是针对两类问题的分类，为了满足现实生活应用中多分类问题，需要构造多类 SVM 分类器，目前多分类支持向量机算法的思路主要有两种：
（1）在经典 SVM 的基础上对其目标函数进行优化，构造多分类模型，进而实现多分类问题。这种方法为一次性求解法，由于其计算复杂度比较高，在实际应用中效率低，所以并不常用。
（2）将多分类问题归结为多个两分类问题，常用的算法主要有一对多[6-7]、一对一[8-9]、导向无环图[10]、二叉树[11]四种。文献[12]对这四种算法分别进行了详细的描述，在训练复杂度、测试复杂度和分类准确率方面作了理论分析，并利用数据对分析结果进行了验证。分析得出，导向无环图的分类性能最优，一对一的分类性能次之，二叉树的分类性能较差，一对多的分类性能最差；在训练和测试耗时方面，二叉树耗时最短，导向无环图次之，一对一和一对多的耗时相对较长。
2 支持向量机的应用及发展方向
支持向量机理论自提出以来，在各种应用领域得到了广泛应用，并在模式识别领域已经得到成功应用。在模式识别领域，SVM 方法主要应用于手写数字识别、语音识别、人脸检测与识别、文本分类等方面。
支持向量机在生物信息领域，如蛋白质的分类和 DNA 分析等，取得了较好结果。此外，支持向量机还应用于时间序列分析、回归分析、聚类分析、动态图像的人脸跟踪、信号处理、语音识别、图像分类和控制系统等诸多领域。
尽管国内外学者对支持向量机的理论与算法开展了许多有效的研究工作，但是其算法研究中还有很多尚未解决的问题。
（1）如何彻底解决大样本时训练算法速度慢、算法复杂、运算量大等缺点；
（2）SVM 自选参数目前尚缺乏结构化方法来实现参数的最优选择，
（3）训练样本中数据含有不确定性以及噪声时的 SVM 理论性能，即 SVM 理论的鲁棒性问题是值得研究的重点课题。
结束语
本文主要介绍了现有的SVM 训练算法，着重说明了各种的算法的思路和优缺点.当前对SVM的研究方兴未艾，训练算法的研究方向主要是确定不同的优化目标，根据KKT 约束优化条件寻找大规模训练样本下的实用算法；应用方向主要是为模式识别时的多类问题寻找好的算法和解决训练样本规模和训练速度之间的矛盾、解决支持向量树木和分类速度之间的矛盾。在此基础上进行进一步的机理分析和试验分析，探索和拓宽SVM新的应用领域，使其成为更有发展前途的新技术。
参考文献：
[1] Vapnik V N.统计学习理论[ M ].许建华，张学工，译.北京：电子工业出版社，2009.
[2] 吴德会.基于多分类支持向量机的智能辅助质量诊断研究[J].系统仿真学报，2009，21（6）：1689-1693.
摘要：支持向量机是一种新的机器学习方法，由于其出色的学习性能，该技术已成为当前国际机器学习界的研究热点。对SVM训练算法的最新研究成果进行了综述，着重说明了各种的算法的思路和优缺点。总结了支持向量机理论及其应用的现状，对支持向量机的未来发展方向进行了展望。
关键词：支持向量机；训练算法；分类
Abstract：Support Vector Machines are a kind of novel machine learning methods，which have become the hotspot of machine learning because of their excellent learning performance.This paper made a summarize of the new pro gress in the SVM training of algorithm，focused on the ideas of various algorithms，pointed out the advantages and disadvantages of them.The status quo of SVM theory and its applications are summarized and the future development direction of SVM theory is expected.
Keywords：Support vector machine；raining algrithm；categorizing；
支持向量机（Support Vector Machine，SVM）是Vapnik等1995年提出的一种基于统计学习理论[1]的模式识别方法。它在解决小样本、非线性和高维模式识别问题中具有特有的优势，且在某种程度上克服了维数灾难和过度学习等传统难题，另其具有坚实的理论基础、简明的数学模型，使得支持向量机自提出以来受到广泛的关注，并取得了长足的发展。
1 支持向量机的训练算法
（1）块算法与分解算法
块算法（chunking algorithm）[2]最早是由Boser等人提出来的。它的出发点是删除矩阵中对应于Lagrange乘子为零的行和列不会对最终结果产生影响。对于给定的样本，块算法的目标就是通过某种迭代方式逐步排除非支持向量。块算法将矩阵的规模从训练样本数的平方减少到具有非零Lagrange乘子的样本数的平方，从而降低了训练过程对存储容量的要求。这种方法只要支持向量远远小于训练样本。但是，随着算法迭代次数的增多，训练样本集规模也会越来越大，算法依旧会变得十分复杂。
Osuna等人提出的分解算法（decomposition a1.gorithm）[3]，是目前有效解决大规模问题的主要方法。主要思想是将训练样本分成工作集 B 和非工作集 N，并保持大小不变。该算法的关键是如何最优的选取工作集B。Joachims利用SVMlight提高算法收敛速度，是目前设计SVM分类器的重要软件。
除了分解算法，还有Huber近似算法、多拉格朗日乘子协同优化算法|、剪枝算法等SVM的求解方法。
（2）序贯最小优化算法
由Platt提出的序列最小优化（sequential mini—real optimization，SMO）[4]算法是分解算法是针对工作集的个数为2的特殊情形，即SMO把一个大的优化问题分解成一系列只含两个变量的优化问题。两个变量的最优化问题可以解析求解，因而不需要迭代地求解二次规划问题。对分类SMO算法，Keerthi等人修正了优化条件，并针对经验方法提出两个改进措施，以保证算法收敛和减少迭代次数。随后Keerthi等人引提出了广义SMO（generalized SMO，GSMO）算法，利用违反对的概念确定工作集，指出前面两种改进都是GSMO的特例，并证明，对任意的t﹥0以τ违反对为工作集，则GSMO算法有限终止，得到优化问题的τ近似优化解.Lin对SMO算法的渐进收敛性进行了证明。
（3）模糊支持向量机
模糊支持向量机（Fuzzy SVM，FSVM）算法将模糊逻辑的方法与支持向量机的学习方法相结合，该算法给每个训练样本都赋与相应的模糊隶属度，这样不同的樣本对决策函数的学习有不同的贡献，可以降低噪声对最优超平面的影响。
（4）粒度支持向量机[ 5]
粒度支持向量机是Y.C.Tang提出的一种新的训练算法，其主要思想是通过粒划分来构建粒空间获得一系列信息粒，然后在每个信息粒上进行学习，最后通过聚合信息粒上的信息（如数据、规则、知识、属性等）获得最终的SVM 决策函数。如何进行粒度划分是粒度支持向量机研究的主要问题。目前，主要有基于关联规则的粒度支持向量机，利用聚类方法对训练样本集进行粒度划分的基于聚类的粒度支持向量机，基于商空间的粒度支持向量机的基本思想是首先对训练样本集进行粗粒度的选择SV，去除一部分对构造最优分类超平面无用的样本点，然后再对粗选后的样本进行细粒度的 SV 训练。此外还有基于树形层次结构的粒度支持向量机等。
（5）多分类支持向量机
SVM起初主要是针对两类问题的分类，为了满足现实生活应用中多分类问题，需要构造多类 SVM 分类器，目前多分类支持向量机算法的思路主要有两种：
（1）在经典 SVM 的基础上对其目标函数进行优化，构造多分类模型，进而实现多分类问题。这种方法为一次性求解法，由于其计算复杂度比较高，在实际应用中效率低，所以并不常用。
（2）将多分类问题归结为多个两分类问题，常用的算法主要有一对多[6-7]、一对一[8-9]、导向无环图[10]、二叉树[11]四种。文献[12]对这四种算法分别进行了详细的描述，在训练复杂度、测试复杂度和分类准确率方面作了理论分析，并利用数据对分析结果进行了验证。分析得出，导向无环图的分类性能最优，一对一的分类性能次之，二叉树的分类性能较差，一对多的分类性能最差；在训练和测试耗时方面，二叉树耗时最短，导向无环图次之，一对一和一对多的耗时相对较长。
2 支持向量机的应用及发展方向
支持向量机理论自提出以来，在各种应用领域得到了广泛应用，并在模式识别领域已经得到成功应用。在模式识别领域，SVM 方法主要应用于手写数字识别、语音识别、人脸检测与识别、文本分类等方面。
支持向量机在生物信息领域，如蛋白质的分类和 DNA 分析等，取得了较好结果。此外，支持向量机还应用于时间序列分析、回归分析、聚类分析、动态图像的人脸跟踪、信号处理、语音识别、图像分类和控制系统等诸多领域。
尽管国内外学者对支持向量机的理论与算法开展了许多有效的研究工作，但是其算法研究中还有很多尚未解决的问题。
（1）如何彻底解决大样本时训练算法速度慢、算法复杂、运算量大等缺点；
（2）SVM 自选参数目前尚缺乏结构化方法来实现参数的最优选择，
（3）训练样本中数据含有不确定性以及噪声时的 SVM 理论性能，即 SVM 理论的鲁棒性问题是值得研究的重点课题。
结束语
本文主要介绍了现有的SVM 训练算法，着重说明了各种的算法的思路和优缺点.当前对SVM的研究方兴未艾，训练算法的研究方向主要是确定不同的优化目标，根据KKT 约束优化条件寻找大规模训练样本下的实用算法；应用方向主要是为模式识别时的多类问题寻找好的算法和解决训练样本规模和训练速度之间的矛盾、解决支持向量树木和分类速度之间的矛盾。在此基础上进行进一步的机理分析和试验分析，探索和拓宽SVM新的应用领域，使其成为更有发展前途的新技术。
参考文献：
[1] Vapnik V N.统计学习理论[ M ].许建华，张学工，译.北京：电子工业出版社，2009.
[2] 吴德会.基于多分类支持向量机的智能辅助质量诊断研究[J].系统仿真学报，2009，21（6）：1689-1693.