[原创新思] SVM改进算法的研究现状与趋势

改进算法, 现状, 趋势, 支持向量机 赵勇. SVM改进算法的研究现状与趋势. 人工智能研讨论坛, SVM版.

由于SVM有着良好的统计学习理论基础，优良的泛化能力，在模式识别（人脸识别、文本识别、手写体识别等）、函数拟合、建模和控制领域得到了应用，取得了 良好的评价。但同时，在目前SVM的应用中还存在一些问题，如对不同的应用问题核函数参数的选择比较困难，对较复杂问题其分类精度不是很高，以及对大规模 分类问题训练时间长等。由此，促生了对SVM算法进行改进的研究热潮，并在从中孕育出了许多具有实用价值的优良改进算法。

目前针对SVM应用中出现的问题，主要针对SVM的一些不足之处进行如下方面的改进和完善：

1. 对学习训练速度的改进：SVM的训练速度与支持向量的数量有关，支持向量个数越大，训练的计算量就越大，识别的计算量也同样很大。于是，就需要提高SVM 的计算速度，以便于处理大规模问题。因此，降低支持向量数目、简化支持向量成为一项非常有意义的工作。

在国外，Burges[8]通过在给定精度损失下生成支持向量缩减集合的方式得到简化支持向量机，它的计算量很大且在简化的同时牺牲了识别精度。Lee 等[9]提出RSVM (Reduced Support Vector Machine)，Lin 等[10]对这种方法作了进一步的研究，该方法人为地将支持向量限制在一个训练样本子集中,它只有在训练样本很多且支持向量所占比例极高的情况下能减少支 持向量，在一般情况下支持向量个数反而可能会增加。Scholkopf 等人[11, 12]提出了所谓的υ-SVM,证明了参数υ与支持向量数目及误差之间的关系，但这种方法在参数υ过小时将降低机器泛化能力。

在国内，刘向东和陈兆乾[13]提出了一种快速支持向量机分类算法FCSVM，实验表明在几乎不损失识别精度的情况下识别速度有不同程度的提高。 该方法通过变换，用少量的支持向量代替全部支持向量进行分类计算，但在求解变换矩阵时需要求解复杂优化问题。李红莲[14]等提出了一种大规模样本集的支 持向量机学习策略：首先用小规模的样本集训练得到初始分类器，然后用这个分类器对大规模训练集进行修剪，得到一个规模很小的约减集，再用这个约减集进行训 练得到最终的分类器。实验表明这种方法既减少了训练时间，也减少了识别速度，且在最优阈值时识别率还可能有所提高，但在计算时需对阈值进行选择.

2. 对SVM多分类算法的研究：经典SVM算法在二分类问题上得到了很好的研究和应用，但是现实中，大多情况是多分类问题。如何将SVM良好的二分类处理能力 有效地延伸到多分类问题上，是扩大SVM应用领域实际所要求，是目前研究的一个重要方面。
相关资料：
目前，将二分类方法转化为多分类方法常用的思路有两种：一是间接构造，通过多个2 类分类器组合起来完成多类分类,如DAGSVM 等方法[5] ；二是利用Weston等人提出的方法直接构造多类SVM分类器,如k-SVM[6] 。
（1）间接构造多分类器：这一方法根据训练样本组成的不同可以分为“one against one”和“one against all”两种类型。对于构造k类的分类器：前者的每一个SVM的训练样本是由两个不同类别的样本组成，需要构造(k(k-1)/2)个SVM完成整个分类 任务；后者的每个SVM训练样本由全部样本组成，分为属于该类和不属于该类两部分，需要构造k个SVM完成k分类。

3. 对过学习问题的优化：当训练样本两类样本混杂较严重时，SVM也可能会出现过学习现象，使得决策面过于复杂而降低了泛化能力。因此，对过学习问题的研究和 寻找避免方法也是研究之一。
相关论文：
文献[1]的做法是：先对训练样本进行裁剪，首先找出每一个点的最近邻,然后对每一个点,如果该点与其最近邻属于同类,则保留此点;如果该点与其最近邻属 于异类,将该点删除，由此使的不同类样本的掺杂程度降低；然后在使用SVM对裁剪后的样本进行学习。由此，改进得到了作者所命名的NN-SVM，在试验中 表现出较好的效果。

4. 对SVM样本孤立点和噪点处理的改进：改进对训练样本中噪点的处理提高其泛化能力，因为SVM在构造最优分类面时所有的样本具有相同的作用,因此,存在对 噪声或野值敏感的问题。于是，如何消除噪点影响也是改进SVM的研究方向之一。提出了很多模糊支持向量机的方法，如F-SVM[7]等。
相关论文：
文献[2]从“出错样本点都在分界面附近”考虑，认为要提高SVM的分类性能应尽量利用分界面附近的样本提供的信息。同时，经过推导得出SVM可以看成 “每类只有一个代表点的最近邻（Nearest Neighbour, NN）分类器”。由此分析，作者将SVM和NN结合起来，对样本在空间的不同分布使用不同的分类法：当样本和SVM最优分类面的距离大于一个给定的阈值 时，使用SVM分类，反之则用KNN分类（以每类的所有的支持向量机作为代表点组）。以此构造出SVM-KNN分类器，以提高SVM的预测精度。

5. 对SVM在线学习算法的研究：

6. 对SVM回归预测算法的改进：
相关论文：
文献[3]观察到支持向量回归算法建立的预测模型, 通常把待预测样本输入, 只能获得一个点输出, 至于这个预测值到底可信与否并不知道。于是，根据局部预测的思想, 对每个待预测样本都找到它的一个邻近集（距离待预测样本距离小于某个阈值的点的集合）, 然后以这个邻近集作为训练集, 并且根据这个邻近集中回归预测的正确率（预测结果误差在允许范围内的点的个数与临近集样本数的比值）来定义该待预测样本的预测信任度, 从而对每个待预测样本都能提供一个预测信任度。

参考文献：
[1] 李红莲, 王春花, 袁保宗. 一种改进的支持向量机NN-SVM[J]. 计算机学报, 2003, 26(8): 1015-1020.
[2] 李蓉, 叶世伟, 史忠植. SVM-KNN分类器——一种提高SVM分类精度的新方法[J]. 电子学报, 2002, 30(5): 745-748.
[3] 孙德山, 吴今培. 支持向量回归中的预测信任度[J]. 计算机科学, 2003, 30(8): 126-127.
[4] Platt J . Fast training of support vector machines using sequential minimal optimization [A]. Advances in Kernel Methods-Support Vector Learning [C]. Cambridge: MIT Press, 1999. 185-208.
[5] Platt J C , Cristianini N , Shawe-Taylor J . Large margin DAG’s for multiclass classification. Advances in Neural Information Processing Systems. Cambridge , MA : MIT Press , 2000 , 12 : 547-553.
[6] Weston J , Watkins C. Multi-class support vector machines : [Technical Report SD2 TR298204]. Department of Computer Science , Royal Holloway University of London ,1998
[7] Inoue T , Abe S. Fuzzy Support Vector Machines for Pattern Classification. In : Proceedings of International Joint Conference on Neural Networks , 2001. 1449～1454.
[8] C J C Burges . Simplified support vector decision rule[A ] . Proc 13th Int Conf Machine Learning[ C ] . San Mateo , CA ,1996. 71 - 77.
[9] Y J Lee , O L Mangasarian. RSVM : Reduced support vector machines [A ] . Proc of the First SIAM International Conference on Data Mining[ C] . Chicago ,2001.
[10] K M Lin ,C J Lin. A study on reduced support vector machines[J ] . IEEE Transactions on Neural Networks ,2003 ,14 (6) :1449 - 1559.
[11] B Scholkopf , et al . New support vector algorithms [J ] . Neural Computation ;2000 ,12 (5) :1207 - 1245.
[12] P H Chen ,C J Lin ,B Schǒlkopf . A tutorial onυ2support vector machines [J ] . Applied Stochastic Models in Business and Industry ,2005 ,21 (2) :111 - 136.
[13] 刘向东, 陈兆乾. 一种快速支持向量机分类算法的研究[J ] . 计算机研究与发展,2004 ,41 (8) :1327 - 1332.
    Xiang dong Liu , Zhao2qian Chen. A fast classification algorithm of support vector machines [J ] . J ournal of Computer Research and Development ,2004 ,41 (8) :132721332. (in Chinese)
[14] 李红莲,等. 针对大规模训练集的支持向量机的学习策略[J ] . 计算机学报,2004 ,27 (5) :716 - 719.
   Hong lian Li , et al . A learning strategy of SVM used to large training set [ J ] . Chinese J ournal of Computers , 2004 , 27 (5) : 716 - 719. (in Chinese)