作者：李丹阳, 蔡金燕, 杜敏杰, 朱赛, 张峻宾

作者单位：军械工程学院光学与电子工程系, 河北 石家庄 050003

关键词：序贯最小优化算法;快速训练;KKT条件;工作集选择;支持向量数据描述

摘要：

针对传统支持向量数据描述(support vector data description,SVDD)训练中存在的训练速度慢、存储核矩阵需要的空间开销大、计算量大、算法效率低等问题,提出一种基于改进序贯最小优化(SMO)算法的SVDD快速训练方法。该算法针对原有SMO算法仅能处理单类样本的缺陷,提出一种可以处理负样本的改进方法,给出详细的计算推导过程,并针对KKT判定条件、工作集选择等关键问题进行改进。试验证明:与传统的SVDD训练算法相比,基于改进SMO算法的SVDD快速训练方法训练时间短,计算量小,分类准确度高,空间开销小,更适合于大规模数据的快速训练,具有较高的工程应用价值。

SVDD fast training algorithm based on improved SMO

LI Danyang, CAI Jinyan, DU Minjie, ZHU Sai, ZHANG Junbin

Department of Optical and Electronic Engineering, Ordnance Engineering College, Shijiazhuang 050003, China

Abstract: A fast training algorithm is presented based on the improved SMO to solve the problems such as low training speed, high cost in large storage space needed for kernel matrix, large amounts of calculation and low efficiency in traditional training algorithms. As the original SMO can only deal with the samples of the same class, an improved SMO which can deal with negative samples is presented. Its calculation and derivation processes have been presented in details and the important problems like KKT judge condition and working set selection have been improved. Experiments show that the improved SMO used in SVDD fast training takes less time, needs smaller calculation and smaller space, and has higher classification accuracy. It is more suitable for large-scale data fast training and has high value in engineering application.

Keywords: SMO;fast training;KKT conditions;working set selection;SVDD

2015, 41(11): 101-105  收稿日期: 2015-01-03;收到修改稿日期: 2015-02-25

基金项目: 

作者简介: 李丹阳(1987-),男,河南濮阳市人,博士研究生,专业方向为电子系统性能检测与故障诊断。

参考文献

[1] Tax D M J, Duin R P W. Support vector data description[J]. Machine Learning,2004,54(1):45-65.
[2] Platt J. Fast training of support vector machines using sequential minimal optimization[M]. Cambridge,MA:MIT Press,1999:185-208.
[3] 罗瑜,徐图,何大可,等. 基于函数逼近的改进SMO算法研究[J]. 山西大学学报:自然科学版,2007,30(3):329-334.
[4] Coleman T F, Li Y. A reflective newton method for minimizing a quadratic function subject to bounds on some of the variables[J]. SIAM Journal on Optimization,1996,6(3):1040-1058.
[5] 周晓剑,马义中,朱嘉钢. SMO算法的简化及其在非正定核条件下的应用[J]. 计算机研究与发展,2010,47(11):1962-1969.
[6] 朱齐丹,张智,邢卓异. 支持向量机改进序列最小优化学习算法[J]. 哈尔滨工程大学学报,2007,28(2):183-188.
[7] 曾志强,吴群,廖备水,等. 改进工作集选择策略的序贯最小优化算法[J]. 计算机研究与发展,2009,46(11):1925-1933.
[8] 徐图,罗瑜,何大可. 超球体单类支持向量机的SMO训练算法[J]. 计算机科学,2008,35(6):178-180.
[9] 徐磊,赵光宙,顾弘. 基于作用集的一类支持向量机递推式训练算法[J]. 浙江大学学报:工学版,2009,43(1):42-46.