计算机工程与应用 ›› 2017, Vol. 53 ›› Issue (4): 64-69.DOI: 10.3778/j.issn.1002-8331.1607-0111

• 理论与研发 • 上一篇    下一篇

间隔值辅助的SMO算法改进研究

郑  奇1,2,段会川1,2,孙海涛3   

  1. 1.山东师范大学 信息科学与工程学院,济南 250014
    2.山东师范大学 山东省分布式计算机软件新技术重点实验室,济南 250014
    3.山东师范大学 实验室与设备管理处,济南 250014
  • 出版日期:2017-02-15 发布日期:2017-05-11

Margin value assisted sequential minimal optimization improvement

ZHEGN Qi1,2, DUAN Huichuan1,2, SUN Haitao3   

  1. 1.School of Information Science & Engineering, Shandong Normal University, Jinan 250014, China
    2.Shandong Provincial Key Laboratory for Novel Distributed Computer Software Technology, Shandong Normal University, Jinan 250014, China
    3.The Laboratory and Equipment Management Sector, Shandong Normal University, Jinan 250014, China
  • Online:2017-02-15 Published:2017-05-11

摘要: 顺序最小优化(SMO)算法是现今求解支持向量机(SVM)的最优秀算法之一,其效率直接影响到SVM的训练效率。为提高SVM的训练效率,提出了一种间隔值辅助的SMO改进算法。通过一定量的经验性实验,统计总结出了间隔值随迭代次数变化的规律,即该变化呈铰链函数形态,起始阶段下降很快,经过一小段缓慢变化期后进入间隔值几乎无变化的水平区域。由此,提出并实现了SMO改进算法,通过跟踪间隔值随迭代次数的变化率,待越过拐点一小段时间后终止算法以缩短SVM训练时间。对比实验以及k分类的交叉验证(k-CV)证明,改进后的SMO算法在保持原有算法的模型预测能力的基础上,能够产生至少45%的效率提升。

关键词: 支持向量机, 顺序最小优化, 间隔, 交叉验证

Abstract: Sequential Minimal Optimization algorithm is one of the best method to solve Support Vector Machine now. Its efficiency directly affects the training efficiency of SVM. For this reason, the paper summarizes the law of margin value changing with the number of iterations by a certain amount of empirical test. This law shows that the changes is in hinge function form. It has a start of a rapid descent and a horizon field which has no changes on margin value after a short period of slowly changing period. Therefore, the paper provides and realizes the algorithm which tracks the rate of margin?value’s changing along with the number of iterations and stops the training when entering the horizontal region. Contrast experiment and k-CV shows that this improved algorithm can improve efficiency by 45% at least and keep the predictive ability at the same time.

Key words: support vector machine, sequential minimal optimization, margin, cross-validation