核向量机与支持向量机相结合的二阶段快速学习方法

doi:10.3724/SP.J.1087.2012.00419

计算机应用 ›› 2012, Vol. 32 ›› Issue (02): 419-424.DOI: 10.3724/SP.J.1087.2012.00419

核向量机与支持向量机相结合的二阶段快速学习方法

蒲骏逸,雷秀仁

华南理工大学理学院，广州 510640

收稿日期:2011-07-12 修回日期:2011-09-13 发布日期:2012-02-23 出版日期:2012-02-01
通讯作者: 蒲骏逸
作者简介:蒲骏逸(1986-)，男，广东广州人，硕士研究生，主要研究方向：支持向量机、核向量机、并行算法；
雷秀仁(1964-)，男，湖南常宁人，副教授，博士，主要研究方向：矩阵计算、并行算法。

Two-stage fast training method based on core vector machine and support vector machine

PU Jun-yi,LEI Xiu-ren

School of Sciences, South China University of Technology, Guangzhou Guangdong 510640，China

Received:2011-07-12 Revised:2011-09-13 Online:2012-02-23 Published:2012-02-01
Contact: PU Jun-yi

摘要/Abstract

摘要： 支持向量机(SVM)作为一种有效的模式分类方法，当数据集规模较大时，学习时间长、泛化能力下降；而核向量机(CVM)分类算法的时间复杂度与样本规模无关，但随着支持向量的增加，CVM的学习时间会快速增长。针对以上问题，提出一种CVM与SVM相结合的二阶段快速学习算法(CCS)，首先使用CVM初步训练样本，基于最小包围球(MEB)筛选出潜在核向量，构建新的最有可能影响问题解的训练样本，以此降低样本规模，并使用标记方法快速提取新样本;然后对得到的新训练样本使用SVM进行训练。通过在6个数据集上与SVM和CVM进行比较，实验结果表明，CCS在保持分类精度的同时训练时间平均减少了30%以上，是一种有效的大规模分类学习算法。

关键词: 支持向量机, 分类, 大规模数据集, 核向量机, 最小包围球

Abstract: Support Vector Machine (SVM) is a widely used classification technique. But the scalability of SVM to handle large data sets still needs much of exploration. Core Vector Machine (CVM) is a technique for scaling up a two class SVM to handle large data sets. However, it is computationally infeasible to use CVM to deal with the data set with mass Support Vectors (SV), as its training time is related to the number of SV. In this paper, a two-stage training algorithm combining CVM with SVM (CCS) was proposed. It first employed Minimum Enclosing Ball (MEB) based CVM algorithm to determine the potential core vectors, and then used labeling method to rapidly reconstruct training set, which aim is to reduce the scale of training set. After obtaining new training samples, SVM was adopted to deal with them. The experimental results indicate that the proposed approach can reduce the training time by 30% without losing the classification accuracy, and it is an efficient method for handling large-scale classification.

Key words: Support Vector Machine (SVM), classification, large data set, Core Vector Machine (CVM), Minimum Enclosing Ball (MEB)

中图分类号:

TP181

蒲骏逸雷秀仁. 核向量机与支持向量机相结合的二阶段快速学习方法[J]. 计算机应用, 2012, 32(02): 419-424.

PU Jun-yi LEI Xiu-ren. Two-stage fast training method based on core vector machine and support vector machine[J]. Journal of Computer Applications, 2012, 32(02): 419-424.

参考文献

[1]VAPNIK V. Statistical learning theory[M]. New York: John Wiley and Sons, 1998. [2]边肇祺，张学工.模式识别[M]. 北京：清华大学出版社，2000：284-303. [3]GRAF H P, COSATTO E, BOTTOU L, et al. Parallel support vector machines:the cascade SVM [J]. Neural Information Processing Systems, 2005, 17:521-528. [4]LEE Y-J, MANGASARIAN O L. RSVM: Reduced support vector machines [EB/OL]. ［2010-02-20］. http://citeseer.ist.psu.edu/viewdoc/summary?doi=10.1.1.102.3640. [5]朱方, 顾军华, 杨欣伟, 等.一种新的支持向量机大规模训练样本集缩减策略[J]. JOCA, 2009, 29(10): 2736-2741. [6]CHANG F, GUO Y-C, LIN X-R, et al. Tree decomposition for large-scale SVM problems [J]. Journal of Machine Learning Research, 2010, 11: 2935-2972. [7]文贵华,向君,丁月华. 基于商空间粒度理论的大规模SVM分类算法[J]. 计算机应用研究, 2008, 25(8): 2229-2301. [8]PLATT J C. Fast training of support vector machines using sequential minimal optimization [C]// Advances in Kernel Methods—Support Vector Learning. Cambridge: MIT Press, 1999: 185-208. [9]TSANG I W-H, KWOK J T, CHEUNG P M. Core vector machines: Fast SVM training on very large data sets [J]. Journal of Machine Learning Research, 2005, 6: 363-392. [10]SZEDMAK S, SHAWE-TAYLOR J. Multiclass learning at one-class complexity [R]. Southampton: University of Southampton, School of Electronics and Computer Science, 2005. [11]TSANG I W-H, KWOK J T, LAI K T. Core vector regression for very large regression problems [C]// ICML '05: Proceedings of the 22nd International conference on Machine learning. New York: ACM, 2005: 913-920. [12]WANG DI, ZHANG BO, ZHANG PENG, et al. An online core vector machine with adaptive MEB adjustment [J]. Pattern Recognition, 2010, 43(10): 3468-3482. [13]BDOIU M,CLARKSON K L. Optimal core-sets for balls [J]. Computational Geometry: Theory and Applications, 2008, 40(1): 14-22. [14]SMOLA A J, SCHLKOPF B. Sparse greedy matrix approximation for machine learning [C]// ICML '00: Proceedings of the Seventeenth International Conference on Machine Learning. Stanford: Morgan Kaufmann, 2000: 911-918. [15]TSANG I W-H, KWOK J T. LibCVM: The LibCVM Toolkit is a C implementation of the improved core vector machine [CP/OL]. [2010-03-04]. http://c2inet.sce.ntu.edu.sg/ivor/cvm.html. [16]CHANG C-C, LIN C-J. LIBSVM: A Library for support vector machines [EB/OL]. ［2010-01-04］. http://www.csie.ntu.edu.tw/~cjlin/libsvm/. [17]TSANG I W-H, KWOK J T-Y, CHEUNG P M. Generalized core vector machines [J]. IEEE Transactions on Neural Networks, 2006, 17(5): 1126-1140. [18]KUMAR P, MITCHELL J S B, YILDIRIM E A. Approximate minimum enclosing balls in high dimensions using corsets [J]. ACM Journal of Experimental Algorithmic, 2003, 8: 1-29. [19]PANIGRAHY R. Minimum enclosing polytope in high dimensions [C/OL]// Proceedings of CoRR， 2004 [2010-02-12]. http://arxiv.org/abs/cs/0407020. [20]TSANG I W-H,KWOK J T,CHEUNG P-M.Very large SVM training using core vector machines[C]// Proceedings of the Tenth International Workshop on Artificial Intelligence and Statistics.Barbados:The Society for Artificial Intelligence and Statistics,2005:349-356. [21]ASHARAF S, MURTY M N, SHEVADE S K. Multiclass core vector machine [C]// Proceedings of the 24th International Conference on Machine Learning. New York: ACM, 2007: 41-48.

核向量机与支持向量机相结合的二阶段快速学习方法

Two-stage fast training method based on core vector machine and support vector machine

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	宋中山, 梁家锐, 郑禄, 刘振宇, 帖军. 基于双向门控尺度特征融合的遥感场景分类[J]. 计算机应用, 2021, 41(9): 2726-2735.
[2]	毛铭泽, 曹芮浩, 闫春钢. 基于权值多样性的半监督分类算法[J]. 计算机应用, 2021, 41(9): 2473-2480.
[3]	胡天杰, 胡文军, 王士同. 分布熵惩罚的支持向量数据描述[J]. 计算机应用, 2021, 41(8): 2212-2218.
[4]	李蒙蒙, 秦伟, 刘艺, 刁兴春. 结合头脑风暴优化的混合蚁群优化算法[J]. 计算机应用, 2021, 41(8): 2412-2417.
[5]	朱亮, 徐华, 崔鑫. 基于基分类器系数和多样性的改进AdaBoost算法[J]. 计算机应用, 2021, 41(8): 2225-2231.
[6]	张洋, 江铭虎. 基于注意力机制的文本作者识别[J]. 计算机应用, 2021, 41(7): 1897-1901.
[7]	肖振远, 王逸涵, 罗建桥, 熊鹰, 李柏林. 基于部分加权损失函数的RefineDet[J]. 计算机应用, 2021, 41(7): 1928-1932.
[8]	尹春勇, 张帼杰. 面向分布式漂移数据流的集成分类模型[J]. 计算机应用, 2021, 41(7): 1947-1955.
[9]	章惠, 张娜娜, 黄俊. 优化LeNet-5网络的多角度头部姿态估计方法[J]. 计算机应用, 2021, 41(6): 1667-1672.
[10]	史杨潇, 章军, 陈鹏, 王兵. 基于轻量级网络的钢铁表面缺陷分类[J]. 计算机应用, 2021, 41(6): 1836-1841.
[11]	贾鹤鸣, 郎春博, 姜子超. 基于轻量级卷积神经网络的植物叶片病害识别方法[J]. 计算机应用, 2021, 41(6): 1812-1819.
[12]	韦铭燕, 陈彧, 张亮. 针对混合变量优化问题的协同进化蚁群优化算法[J]. 计算机应用, 2021, 41(5): 1412-1418.
[13]	郭帅, 苏旸. 基于数据流的加密流量分类方法[J]. 计算机应用, 2021, 41(5): 1386-1391.
[14]	贾鹤鸣, 姜子超, 李瑶, 孙康健. 基于改进斑点鬣狗优化算法的同步优化特征选择[J]. 计算机应用, 2021, 41(5): 1290-1298.
[15]	陆鑫伟, 余鹏飞, 李海燕, 李红松, 丁文谦. 基于注意力自身线性融合的弱监督细粒度图像分类算法[J]. 计算机应用, 2021, 41(5): 1319-1325.