支持向量机SMO算法的改进研究

发布时间：2019-03-20 08:52

【摘要】：支持向量机是近几十年来在机器学习方向最重要的进展之一。它从一开始出现就因其十分优秀的分类能力得到了众多国内外研究学者的关注。现今为止已经被应用到许许多多的领域发挥着巨大的作用。因此各类支持向量机的求解算法也成为了广大学者的研究重点。特别是顺序最小优化算法更是受到广泛的关注。顺序最小优化算法具有优美的二次规划表达,从而避免了对空间过大的需求,使实现支持向量机的过程变得简单而高效。但是即便如此,顺序最小优化算法本身的效率提升问题也是现今研究的重点。本文在传统的顺序最小优化算法的基础上,分别通过大量实验借助目标函数值和间隔值的变化对支持向量机以及顺序最小优化算法的求解过程进行了深入地分析,并且根据分析结果对算法求解过程中的停止条件进行了改进。改进过程中对目标函数值和间隔值变化曲线进行了平滑处理,统计数据来对两种改进后的顺序最小优化算法的效果进行衡量,且进一步采用交叉验证的方法验证改进算法的结果。本文的研究工作主要包括:(1)依据传统的顺序最小优化算法推导出目标函数值及间隔值的表达式,并编写相应代码,能够分别输出目标函数值以及间隔值随迭代次数变化的数据。对代码改进后的传统的顺序最小优化算法过程进行大量实验研究,借助目标函数值和间隔值观察过程中的每一个量的变化情况。(2)实验过程中对目标函数值和间隔值的变化曲线分别进行平滑处理,并用更具形象曲线变化的方式表现其变化过程。发现目标函数值和间隔值随迭代次数变化的规律:目标函数值及间隔值随迭代次数的变化类似均呈铰链函数形态,有一个明显的拐点,在一定的迭代次数后(即拐点后)目标函数值在很长的一段时间里变化甚微,在目标函数值的变化过程中甚至出现微小的升降波动现象。(3)对传统的顺序最小优化算法进行过程改进。分别进行了目标函数值辅助的顺序最小优化算法改进以及间隔值辅助的顺序最小优化算法改进。根据目标函数值以及间隔值的曲线形态,找到一个可以提前终止训练避免后期无效率训练同时又对训练的正确率影响不大的停止标准,完成改进代码的编写。(4)分别对两个改进后的顺序最小优化算法进行实验,统计数据,并从训练效率以及测试的正确率方面对改进算法和传统算法的实验结果进行比较将。同时采用比较权威的交叉验证的方法进行训练效率和模型预测能力的进一步比较,综合分析改进后算法的训练效果。通过大量的实验分析验证,本文所采取的新改进的间隔值和目标函数值辅助的顺序最小优化改进算法在训练效率和模型预测能力比教优越,同时本文两种改进算法比较来看,间隔值辅助的顺序最小优化算法对训练效率的提升更显著。
[Abstract]:Support vector machine (SVM) is one of the most important advances in machine learning in recent decades. From the beginning, it has attracted the attention of many scholars at home and abroad because of its excellent classification ability. Up to now, it has been applied to many fields to play a great role. Therefore, all kinds of support vector machine algorithms have also become the focus of the majority of scholars. In particular, the sequential minimum optimization algorithm has attracted more and more attention. The sequential minimum optimization algorithm has a beautiful quadratic programming representation, which avoids the need for too much space and makes the process of implementing support vector machine simple and efficient. But even so, the efficiency improvement of sequential minimum optimization algorithm itself is the focus of current research. In this paper, on the basis of traditional sequential minimum optimization algorithm, the solving process of support vector machine and sequential minimum optimization algorithm are deeply analyzed by means of a large number of experiments with the help of the change of objective function value and interval value, respectively. According to the analysis results, the stopping condition of the algorithm is improved. In the process of improvement, the change curves of objective function value and interval value are smoothed, and the statistical data are used to measure the effect of the two improved sequential minimum optimization algorithms. Furthermore, cross-validation is used to verify the results of the improved algorithm. The main work of this paper is as follows: (1) according to the traditional sequential minimum optimization algorithm, the expressions of objective function value and interval value are deduced, and the corresponding code is written. Can output the object function values and interval values with the number of iterations data. A large number of experiments have been carried out on the traditional sequential minimum optimization algorithm process after code improvement. With the help of objective function value and interval value, the variation of each quantity in the process is observed. (2) the variation curves of objective function value and interval value are smoothed respectively during the experiment. And use more vivid curve change way to show its change process. It is found that the value of objective function and interval value vary with the number of iterations: the change of value of objective function and interval value with the number of iterations is similar to that of hinge function, and there is an obvious inflection point. After a certain number of iterations (that is, after the inflection point), the value of the objective function varies little over a long period of time. There are even slight fluctuation phenomena in the course of the change of objective function value. (3) the traditional sequential minimum optimization algorithm is improved. The sequential minimum optimization algorithm assisted by objective function value and the sequential minimum optimization algorithm assisted by interval value are improved respectively. According to the curve form of objective function value and interval value, a stopping criterion is found, which can stop training early and avoid inefficiency training in later period, but has little influence on the correct rate of training. The improved code is written. (4) two improved sequential minimum optimization algorithms are tested and compared with the traditional algorithm in terms of the training efficiency and the test accuracy. (4) the experimental results of the improved algorithm are compared with those of the traditional algorithm in terms of the training efficiency and the accuracy of testing. (4) two improved sequential minimum optimization algorithms are tested and statistically analyzed. At the same time, a more authoritative cross-validation method is used to compare the training efficiency and the prediction ability of the model, and the training effect of the improved algorithm is comprehensively analyzed. Through a large number of experiments, it is proved that the improved sequential minimum optimization algorithm based on improved interval value and objective function value is superior to teaching in training efficiency and model prediction ability. At the same time, the comparison of the two improved algorithms in this paper shows that the improved algorithm is superior to the teaching method in training efficiency and model prediction ability. The sequential minimum optimization algorithm assisted by interval value can improve the training efficiency more significantly.
【学位授予单位】：山东师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP181

【参考文献】