多分类孪生支持向量机研究进展
作者:
基金项目:

国家自然科学基金(61672522,61379101);国家重点基础研究发展计划(973)(2013CB329502)


Survey on Multi Class Twin Support Vector Machines
Author:
Fund Project:

National Natural Science Foundation of China (61672522, 61379101); National Key Basic Research Program of China (973) (2013CB329502)

  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [68]
  • |
  • 相似文献 [20]
  • |
  • 引证文献
  • | |
  • 文章评论
    摘要:

    孪生支持向量机因其简单的模型、快速的训练速度和优秀的性能而受到广泛关注.该算法最初是为解决二分类问题而提出的,不能直接用于解决现实生活中普遍存在的多分类问题.近年来,学者们致力于将二分类孪生支持向量机扩展为多分类方法,并提出了多种多分类孪生支持向量机.多分类孪生支持向量机的研究已经取得了一定的进展.主要工作是回顾多分类孪生支持向量机的发展,对多分类孪生支持向量机进行合理归类,分析各个类型的多分类孪生支持向量机的理论和几何意义.以多分类孪生支持向量机的子分类器组织结构为依据,将多分类孪生支持向量机分为:基于"一对多"策略的多分类孪生支持向量机、基于"一对一"策略的多分类孪生支持向量机、基于"一对一对余"策略的多分类孪生支持向量机、基于二叉树结构的多分类孪生支持向量机和基于"多对一"策略的多分类孪生支持向量机.基于有向无环图的多分类孪生支持向量机训练过程与基于"一对一"策略的多分类孪生支持向量机类似,但其决策方式有其特殊的优缺点,因此将其也独立为一类.分析和总结了这6种类型的多分类孪生支持向量机的算法思想、理论基础.此外,还通过实验对比了分类性能.为各种多分类孪生支持向量机之间建立了联系比较,使得初学者能够快速理解不同多分类孪生支持向量机之间的本质区别,也对实际应用中选取合适的多分类孪生支持向量机起到一定的指导作用.

    Abstract:

    Twin support vector machines have drawn extensive attention for their simple model, high training speed and good performance. The initial twin support vector machine is designed for binary classification. However, multi class classification problems are also common in practice. In recent years, researchers have devoted themselves to the study of multi class twin support vector machines. Various mulit class twin support vector machines have been proposed. The study of multi class twin support vector machines has made great progress. This paper aims to review the development of multi class twin support vector machines, classify and analyze them with the respect to the basic theories and geometric meanings. According to the structures, the paper divides the machines into the following groups:"one-versus-all" strategy based multi class twin support vector machines, "one-versus-one" strategy based multi class twin support vector machines, binary tree based multi class twin support vector machines, "one-versus-one-versus-rest" strategy based multi class twin support vector machines, and "all-versus-one" strategy based multi class twin support vector machines. Although the training processes of direct acyclic graph based multi class twin support vector machines are much similar with that of "one-versus-one" based approachs, the decision processes have their own characteristics and disadvantages, and therefore they are divided into a separate group. This paper analyzes and summarizes the ideas and theories of different multi class twin support vector machines, and presents experimental results to compare the performances. This review can make it easy for novices to understand the essential differences and help to choose the suitable multi class twin support vector machine for a practical problem.

    参考文献
    [1] Cortes C, Vapnik VN. Support vector networks. Machines Learning, 1995,20(2):273-297.[doi:10.1023/A:1022627411411]
    [2] Vapnik VN. The Nature of Statistical Learning Theory. New York:Springer-Verlag, 1998.[doi:10.1007/978-1-4757-3264-1]
    [3] Khemchandni R, Chandra S. Twin support vector machines for pattern classification. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2007,29(5):905-910.[doi:10.1109/TPAMI.2007.1068]
    [4] Ding SF, Yu JZ, Qi BJ, Huang HJ. An overview on twin support vector machines. Artificial Intelligence Review, 2014,42(2):245-252.[doi:10.1007/s10462-012-9336-0]
    [5] Kumar MA, Gopal M. Least squares twin support vector machines for pattern classification. Expert Systems with Applications, 2009,36(4):7535-7543.[doi:10.1016/j.eswa.2008.09.066]
    [6] Peng XJ, Xu D. Twin Mahalanobis distance based support vector machines for pattern recognition. Information Sciences, 2012,200:22-37.[doi:10.1016/j.ins.2012.02.047]
    [7] Shao YH, Chen WJ, Zhang JJ, Wang Z, Deng NY. An efficient weighted Lagrangian twin support vector machine for imbalanced data classification. Pattern Recognition, 2014,47(9):3158-3167.[doi:10.1016/j.patcog.2014.03.008]
    [8] Ding SF, Zhang XK, Yu JZ. Twin support vector machines based on fruit fly optimization algorithm. Int'l Journal of Machine Learning and Cybernetics, 2016,7(2):193-203.[doi:10.1007/s13042-015-0424-8]
    [9] Kumar MA, Gopal M. Application of smoothing technique on twin support vector machines. Pattern Recognition Letters, 2008, 29(13):1842-1848.[doi:10.1016/j.patrec.2008.05.016]
    [10] Huang HJ, Ding SF, Shi ZZ. Smooth CHKS twin support vector regression. Journal of Computer Research & Development, 2015, 52(3):561-568(in Chinese with English abstract).[doi:10.7544/issn1000-1239.2015.20131444]
    [11] Ding SF, Huang HJ, Shi ZZ. Weighted smooth CHKS twin support vector machines. Ruan Jian Xue Bao/Journal of Software, 2014, 24(11):2548-2557(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4475.htm[doi:10.3724/SP.J.1001.2013. 04475]
    [12] Ding SF, Huang HJ, Xu XZ, Wang J. Polynomial smooth twin support vector machines. Applied Mathematics and Information Sciences, 2014,8(4):2063-2071.[doi:10.12785/amis/080465]
    [13] Peng XJ, Kong LY, Chen DJ. Improvements on twin parametric margin support vector machine. Neurocomputing, 2015,151(2):857-863.[doi:10.1016/j.neucom.2014.10.010]
    [14] Xie XJ, Sun SL. Multitask centroid twin support vector machines. Neurocomputing, 2015,149(2):1085-1091.[doi:10.1016/j. neucom.2014.07.025]
    [15] Gu B, Sheng VS, Wang ZJ, Ho D, Osman S, Li S. Incremental learning for ν support vector regression. Neural Networks, 2015,67:140-150.[doi:10.1016/j.neunet.2015.03.013]
    [16] Peng X, Xu D. A twin hypersphere support vector machine classifier and the fast learning algorithm. Information Sciences, 2013, 221:12-27.[doi:10.1016/j.ins.2012.09.009]
    [17] Mehrkanoon S, Huang XL, Johan S. Non parallel support vector classifiers with different loss functions. Neurocomputing, 2014, 143:294-301.[doi:10.1016/j.neucom.2014.05.063]
    [18] Hua XP, Ding SF. Weighted least squares projection twin support vector machines with local information. Neurocomputing, 2015, 160:228-237.[doi:10.1016/j.neucom.2015.02.021]
    [19] Gu B, Sheng VS. A robust regularization path algorithm for ν support vector classification. IEEE Trans. on Neural Networks and Learning Systems, 2016.[doi:10.1109/TNNLS.2016.2527796]
    [20] Tanveer M, Shubham K, Aldhaifallah M, Ho SS. An efficient regularized K nearest neighbor based weighted twin support vector regression. Knowledge Based Systems, 2016,94:70-87.[doi:10.1016/j.knosys.2015.11.011]
    [21] Shao YH, Wang Z, Chen WJ, Deng NY. A regularization for the projection twin support vector machine. Knowledge Based System, 2013,37:203-210.[doi:10.1016/j.knosys.2012.08.001]
    [22] Nasiri JA, Charkari NM, Mozafari K. Energy based model of least squares twin support vector machines for human action recognition. Signal Processing, 2014,104(6):248-257.[doi:10.1016/j.sigpro.2014.04.010]
    [23] Yuan CS, Sun XM, Lü R. Fingerprint liveness detection based on multi scale LPQ and PCA. China Communications, 2016,13(7):60-65.[doi:10.1109/CC.2016.7559076]
    [24] Khemchandani R, Sharma S. Robust least squares twin support vector machine for human activity recognition. Applied Soft Computing, 2016,47:33-46.[doi:10.1016/j.asoc.2016.05.025]
    [25] Al Dhaifallah M. Twin support vector machine method for identification of wiener models. Mathematical Problems in Engineering, 2015,2015(2):1-7.[doi:10.1155/2015/125868]
    [26] Tomar D, Agarwal S. A comparison on multi class classification methods based on least squares twin support vector machine. Knowledge Based Systems, 2015,81:131-147.[doi:10.1016/j.knosys.2015.02.009]
    [27] Tomar D, Agarwal S. Twin support vector machine:A review from 2007 to 2014. Egyptian Informatics Journal, 2015,20(1):55-69.[doi:10.1016/j.eij.2014.12.003]
    [28] Xie JY, Hone K, Xie WX, Gao XB, Shi Y, Liu XH. Extending twin support vector machine classifier for multi category classification problems. Intelligent Data Analysis, 2013,17(4):649-664.[doi:10.3233/IDA-130598]
    [29] Wang Z, Chen J, Qin M. Non parallel planes support vector machine for multi class classification. In:Proc. of the 2010 Int'l Conf. on Logistics Systems and Intelligent Management. 2010. 581-585.[doi:10.1109/ICLSIM.2010.5461354]
    [30] Cong HH, Yang CF, Pu XR. Efficient speaker recognition based on multi class twin support vector machines and GMMs. In:Proc. of the IEEE Conf. on Robotics, Automation and Mechatronics (RAM). Chengdu, 2008. 348-352.[doi:10.1109/RAMECH.2008. 4681433]
    [31] Chen SG, Xu J. Least squares twin support vector machine for multi class classification. Int'l Journal of Database Theory & Application, 2015,8(5):65-76.[doi:10.14257/ijdta.2015.8.5.06]
    [32] Tomar D, Agarwal S. Multiclass least squares twin support vector machine for pattern classification. Int'l Journal of Database Theory and Application, 2015,8(6):285-302.[doi:10.14257/ijdta.2015.8.6.26]
    [33] Li CN, Huang YF, Wu HJ, Shao YH, Yang ZM. Multiple recursive projection twin support vector machine for multi class classification. Int'l Journal of Machine Learning and Cybernetics, 2016,7(5):729-740.[doi:10.1007/s13042-014-0289-2]
    [34] Yang ZM, Wu HJ, Li CN, Shao YH. Least squares recursive projection twin support vector machine for multi class classification. Int'l Journal of Machine Learning & Cybernetics, 2016,7(3):411-426.[doi:10.1007/s13042-015-0394-x]
    [35] Tomar D, Agarwal S. An effective weighted multi class least squares twin support vector machine for imbalanced data classification. Int'l Journal of Computational Intelligence Systems, 2015,8(4):761-778.[doi:10.1080/18756891.2015.1061395]
    [36] Shao YH, Chen WJ, Wang Z, Li CN, Deng NY. Weighted linear loss twin support vector machine for large scale classification. Knowledge Based Systems, 2015,73:276-288.[doi:10.1016/j.knosys.2014.10.011]
    [37] Tomar D, Agarwal S. Multi class twin support vector machine for pattern classification. In:Proc. of the 3rd Int'l Conf. on Advanced Computing, Networking and Informatics, Vol.43. Springer-Verlag, 2016. 97-110.[doi:10.1007/978-81-322-2538-6_11]
    [38] Platt JC, Cristianini N, Shawe Taylor J. Large margin dags for multiclass classification. Advances in Neural Information Processing Systems, 2000,12(3):547-553.
    [39] Gu HB, Niu B, Gao ZX. A directed acyclic graph algorithm for multi class classification based on twin support vector machine. Journal of Information & Computational Science, 2014,11(18):6529-6536.[doi:10.12733/jics20105038]
    [40] Tomar D, Agarwal S. Direct acyclic graph based multi class twin support vector machine for pattern classification. In:Proc. of the ACM Ikdd Conf. 2015. 80-85.[doi:10.1145/2732587.2732598]
    [41] Chen J, Ji GR. Multi class LSTSVM classifier based on optimal directed acyclic graph. In:Proc. of the Int'l Conf. on Computer and Automation Engineering. IEEE, 2010. 100-104.[doi:10.1109/ICCAE.2010.5452037]
    [42] Zhang XK, Ding SF, Sun TF. Multi class LSTMSVM based on optimal directed acyclic graph and shuffled frog leaping algorithm. Int'l Journal of Machine Learning and Cybernetics, 2016,7(2):241-251.[doi:10.1007/s13042-015-0435-5]
    [43] Li K, Huang WX, Huang ZH. Multi sensor detected object classification method based on support vector machine. Journal of Zhejiang University (Engineering Science Edition), 2013,47(1):15-22(in Chinese with English abstract).[doi:10.3785/j.issn.1008-973X.2013.01.003]
    [44] Xu YT, Guo R, Wang LS. A twin multi class classification support vector machine. Cognitive Computation, 2013,5(4):580-588.[doi:10.1007/s12559-012-9179-7]
    [45] Nasiri JA, Charkari NM, Jalili S. Least squares twin multi class classification support vector machine. Pattern Recognition, 2015, 48(3):984-992.[doi:10.1016/j.patcog.2014.09.020]
    [46] Khemchandani R, Pal A. Multi category Laplacian least squares twin support vector machine. Applied Intelligence, 2016.[doi:10.1007/s10489-016-0770-6]
    [47] Chu MX, Gong RF, Wang AN. Strip steel surface defect classification method based on enhanced twin support vector machine. Trans. of the Iron & Steel Institute of Japan, 2014,54(1):119-124.[doi:10.2355/isijinternational.54.119]
    [48] Chu M, Wang A, Gong R, Sha M. Multi class classification methods of enhanced LS TWSVM for strip steel surface defects. Int'l Journal of Iron and Steel Research, 2014,21(2):174-180.[doi:10.1016/S1006-706X(14)60027-3]
    [49] Khemchandani R, Saigal P. Color image classification and retrieval through ternary decision structure based multi category TWSVM. Neurocomputing, 2015,165:444-455.[doi:10.1016/j.neucom.2015.03.074]
    [50] Nie PP, Li Z, Liu LL. Application of multi class classification algorithm based on twin support vector machine in intrusion detection. Journal of Computer Applications, 2013,33(2):426-429(in Chinese with English abstract).[doi:10.3724/SP.J.1087. 2013.00426]
    [51] Khemchandani R, Pal A. Tree based multi category Laplacian TWSVM for content based image retrieval. Int'l Journal of Machine Learning & Cybernetics, 2016.[doi:10.1007/s13042-016-0493-3]
    [52] Xie JY, Zhang BQ, Wang WZ. A partial binary tree algorithm for multiclass classification based on twin support vector machines. Journal of Nanjing University (Natural Sciences), 2011,47(4):354-363(in Chinese with English abstract).
    [53] Li QL, Wang JJ, Gao BB. Multi classification algorithm for twin binary tree support vector machine. Journal of Southwest University (National Science Edition), 2014,36(7):162-168(in Chinese with English abstract).[doi:10.13718/j.cnki.xdzk.2014.07. 026]
    [54] Shao YH, Chen WJ, Huang WB, Yang ZM, Deng NY. The best separating decision tree twin support vector machine for multi class classification. Procedia Computer Science, 2013,17:1032-1038.[doi:10.1016/j.procs.2013.05.131]
    [55] Yang ZX, Shao YH, Zhang XS. Multiple birth support vector machine for multi class classification. Neural Computing and Applications, 2013,22(Suppl 1):S153-S161.[doi:10.1007/s00521-012-1108-x]
    [56] Ju XC, Tian YJ, Liu DL, Qi ZQ. Nonparallel hyperplanes support vector machine for multi class classification. Procedia Computer Science, 2015,51(1):1574-1582.[doi:10.1016/j.procs.2015.05.287]
    [57] Xu YT, Guo R. A twin hyper sphere multi class classification support vector machine. Journal of Intelligent and Fuzzy Systems, 2014,27(4):1783-1790.[doi:10.3233/IFS-141145]
    [58] Li DW, Tian YJ. Twin support vector machine in linear programs. Procedia Computer Science, 2014,29:1770-1778.[doi:10.1016/j. procs.2014.05.162]
    [59] Zhang XK, Ding SF, Xue Y. An improved multiple birth support vector machine for pattern classification. Neurocomputing, 2017, 225:119-128.[doi:10.1016/j.neucom.2016.11.006]
    [60] Ding SF. Twin Support Vector Machine:Algorithm, Theory and Extension. Beijing:Science Press, 2017(in Chinese).
    附中文参考文献:
    [10] 黄华娟,丁世飞,史忠植.光滑CHKS孪生支持向量回归机.计算机研究与发展,2015,52(3):561-568.[doi:10.7544/issn1000-1239. 2015.20131444]
    [11] 丁世飞,黄华娟,史忠植.加权光滑CHKS孪生支持向量机.软件学报,2013,24(11):2548-2557. http://www.jos.org.cn/1000-9825/4475.htm[doi:10.3724/SP.J.1001.2013.04475]
    [43] 李侃,黄文雄,黄忠华.基于支持向量机的多传感器探测目标分类方法.浙江大学学报(工学版),2013,47(1):15-22.[doi:10.3785/j. issn.1008-973X.2013.01.003]
    [50] 聂盼盼,臧洌,刘雷雷.基于对支持向量机的多类分类算法在入侵检测中的应用.计算机应用,2013,33(2):426-429.[doi:10.3724/SP.J.1087.2013.00426]
    [52] 谢娟英,张兵权,汪万紫.基于双支持向量机的偏二叉树多类分类算法.南京大学学报(自然科学),2011,47(4):354-363.
    [53] 李秋林,王建军,高斌斌.孪生二叉树支持向量多分类机算法.西南大学学报(自然科学版),2014,36(7):162-168.[doi:10.13718/j. cnki.xdzk.2014.07.026]
    [60] 丁世飞.孪生支持向量机:理论、算法及其拓展.北京:科学出版社,2017.
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

丁世飞,张健,张谢锴,安悦瑄.多分类孪生支持向量机研究进展.软件学报,2018,29(1):89-108

复制
分享
文章指标
  • 点击次数:5541
  • 下载次数: 8850
  • HTML阅读次数: 4526
  • 引用次数: 0
历史
  • 收稿日期:2017-01-19
  • 最后修改日期:2017-02-25
  • 在线发布日期: 2017-07-20
文章二维码
您是第19698494位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号