ECOC多类分类研究综述

doi:10.3969/j.issn.0372-2112.2014.09.020

电子学报 ›› 2014, Vol. 42 ›› Issue (9): 1794-1800.DOI: 10.3969/j.issn.0372-2112.2014.09.020

ECOC多类分类研究综述

雷蕾¹, 王晓丹¹, 罗玺², 周进登³, 陈琴⁴

1. 空军工程大学防空反导学院, 陕西西安 710051;
2. 空军工程大学信息与导航学院, 陕西西安 710077;
3. 空军装备软件测评中心, 北京 100076;
4. 93704部队, 北京 101149

收稿日期:2013-05-11 修回日期:2013-09-07 出版日期:2014-09-25
- 作者简介:
- 雷蕾 女，1988年生于四川南充，博士生，研究方向为智能信息处理和目标识别. E-mail：wendyandpaopao@163.com；王晓丹 女，1966年生于陕西汉中，教授，博士，研究方向为模式识别，机器学习等. E-mail：afeu_w@163.com；周进登 男1984年生于江西鹰潭，博士，研究方向为模式识别，智能信息处理和多传感器数据融合 E-mail：zhoujin198417@163.com
- 基金资助:
- 国家自然科学基金 (No.61273275，No.60975026）

An Overview of Multi-Classification Based on Error-Correcting Output Codes

LEI Lei¹, WANG Xiao-dan¹, LUO Xi², ZHOU Jin-deng³, CHEN Qin⁴

1. The Air and Missile Defense Institute, Air Force Engineering University, Xi'an, Shaanxi 710051, China;
2. The Information and Navigation Institute, Air Force Engineering University, Xi'an, Shaanxi 710077, China;
3. Air Force Equipment Software Testing Center, Beijing 10076, China;
4. Air Force 93704, Beijing 101149, China

Received:2013-05-11 Revised:2013-09-07 Online:2014-09-25 Published:2014-09-25
- Supported by:
- National Natural Science Foundation of China (No.61273275, No.60975026)

摘要/Abstract

摘要：

纠错输出编码能有效地将多类问题转化为二类问题进行求解，已受到国内外从事机器学习的研究者们的重视，并使其成为多类分类领域的研究热点.本文首先分析了ECOC多类分类的原理和框架，指出解决ECOC多类分类问题的关键在于解码策略和编码策略的确定；然后从这两个关键点出发综述了ECOC多类分类的最新进展和应用领域；最后指出了目前存在的问题以及下一步研究方向.论文研究成果将为基于ECOC多类分类方法在实际应用过程中起借鉴和参考作用.

关键词: 多类分类, 纠错输出编码, 机器学习

Abstract:

Multi-classification has been one of the research hotspot in pattern recognition,and there are many solutions to it.As a common way to model multi-classification to design a set of binary classifiers and fuse them,Error-correcting output codes(ECOC) represents a successful framework to deal with this type of problems and is attracting more and more attention of researchers.In this paper,the framework of ECOC is concluded at first.Then the two keys of multi-classification based on ECOC,i.e.,the coding strategies and decoding strategies are proposed.The main part focuses on the research of the two keys and the application of ECOC.Finally,the still existing problems of ECOC are pointed out and the promising research fields are given.The analysis of the paper will provide reference and advice in the practical application of multi-classification based on ECOC.

Key words: multi-classification, error-correcting output codes, machine learning

中图分类号:

TP391

雷蕾, 王晓丹, 罗玺, 等. ECOC多类分类研究综述[J]. 电子学报, 2014, 42(9): 1794-1800.

LEI Lei, WANG Xiao-dan, LUO Xi, et al. An Overview of Multi-Classification Based on Error-Correcting Output Codes[J]. Acta Electronica Sinica, 2014, 42(9): 1794-1800.

参考文献

[1] T G Dietterich, G Bakiri.Solving.Multi-class learning problems via error-correcting output codes[J].Journal of Artificial Intelligence Research, 1995, 34(2):263-286.
[2] T G Dietterich, G Bakiri, Error-correcting output codes:A general method for improving multiclass inductive learning programs[A].Proceedings of the Ninth National Conference on Artificial Intelligence[C].Menlo Park, San Francisco:AAAI, 1991.572-577.
[3] T G Dietterich, E Kong.Error correcting output codes corrects bias and variance[A].Proceedings of the 21th International Conference on Machine Learning[C].San Francisco:AAAI, 1995.313-321.
[4] F Masulli G Valentini.Effectiveness of error correcting output coding methods in ensemble and monolithic learning machines[J].Pattern Anal Applic, 2003, 65(6):285-300.
[5] 李健武, 魏海周, 宋玉龙.ECOC多分类器实现的最小封闭球模型[J].计算机研究与发展, 2011, 48(Suppl):22-30. Li Jianwu, Wei Haizhou, Song Yulong.Theminimum closed sphere model for multi-class classifiers using error-correcting output codes[J].Journal of Computer Research and Development, 2011, 48(Suppl):22-30.(in Chinese)
[6] Crammer K, Singer Y.On the learnability and design of output codes for multiclass problems[A].Proceedings of the Thirteenth Annual Conference on Computational Learning Theory[C].Boston:Kluwer Academic Publishers, 2000.896-909.
[7] T Windeatt, R Ghaderi.Binary labelling and decision level fusion[J].Information Fusion, 2001, 2(1):103-112.
[8] E Tapia, P Bulacio, L Angelone.Recursive ECOC classification[J].Pattern Recognition letters, 2010, 31(3):210-215.
[9] Paolo Simeon, David M J Tax, Robert P W Duin, Francesco Tortorella.A fast approach to improve classification performance of ECOC classification systems[J].Computer Science Trans Structural, Syntactic, and Statistical Pattern Recognition, 2008, 43(3):459-468.
[10] Robett E.Schapire.Using output codes to boost multi-class learning problems[A].Machine Learning:Proceedings of the Fourteenth International Conference[C].Nashville TN:IEEE, 1997.313-321.
[11] Terry Windeatt, G Ardeshir.Tree pruning for output coded ensembles[A].Proceedings 16th International Conference on Pattern Recognition[C].Quebec City, Canada:IEEE Computer Soclos Alamitos, 2002.92-96.
[12] Sergio Escalera, Oriol Pujol, Petia Radeva.Separability ofternary error-correcting output codes[A].Proceedings 19th International Conference on Pattern Recognition[C].Tampa, FL, United States:IEEE, 2008.1-4.
[13] John Langford, Alina Beygelzimer.Sensitive error correcting output codes[J].Lecture Notes in Computer Science, 2005, 2459(3):21-49.
[14] Matthew Prior, Terry Windeatt.Over-fitting in ensembles of neural network classifiers within ECOC frameworks[J].Lecture Notes in Computer Science, 2005, 3541(4):286-295.
[15] 尹安容, 谢湘, 匡镜明.Hadamard纠错码结合支持向量机在多分类问题中的应用[J].电子学报, 2008, 36(1):122-126. Yi Anrong, Xie Xiang, Kuang Jingming.Application of Hadamard ECOC inmulti-class problems based on SVM[J].Acta Electronica Sinica, 2008, 36(1):122-126.(in Chinese)
[16] E Alpaydin, E Mayoraz.Learning error-correcting output codes from data[A].Proceedings of International Conference on Artificial Neural Networks (ICANN'99) (Volume:2)[C].Edinbuergh:IEEE, 1999.743-748.
[17] W Utschick, W Weichselberger.Stochastic organization of output codes in multiclass learning problems[J].Neural Comput, 2001, 13(5):1065-1102.
[18] O Pujol, P Radeva, J Vitria.Discriminate ECOC:A heuristic method for application dependent design of error correcting output codes[J].IEEE Trans on Pattern Analysis and Machine Intelligence, 2006, 28(6):1001-1007.
[19] S Escalera, David M J Tax, O Pujol, P Radeva, Robert P W Duin.Subclass problem-dependent design for error-correcting output codes[J].IEEE Trans on Pattern Analysis and Machine Intelligence, 2008, 30(6):1041-1054.
[20] O Pujol, Escalera S., Radeva P. An incremental node embedding technique for error correcting output codes[J].Pattern Recognition, 2008, 41(2):713-725.
[21] Dimitrios Bouzas, Nikolaos Arvanitopoulos, Anastasios Tefas.Optimizing linear discriminant error correcting output codes using particle swarm optimization[J].Lecture Notes in Computer Science, 2011, 6792(4):79-86.
[22] Guoqiang Zhong, et al.Joint learning of error-correcting output codes and dichotomizers from data[J].Neural Comput & Applic, 2012, 21(4):715-724.
[23] Guoqiang Zhong, Kaizhu Huang, Cheng-Lin Liu.Learning ECOC and dichotomizers Jointly from data[J].Lecture Notes in Computer Science, 2010, 6443(3):494-502.
[24] M A Bagheri, GA Montazer.A subspace approach to error correcting output codes[J].Pattern Recognition Letters, 2013, 34(1):176-184.
[25] Sergio Escalera, O Pujol.Re-coding ECOCs without re-training[J].Pattern Recognition Letters, 2013, 31(5):555-562.
[26] Yunyun Wang, Songcan Chen, Hui Xue.Can under-exploited structure of original-classes help ECOC-based multi-class classification[J].Eeurocomputing, 2012, 89(15):158-167.
[27] 周进登, 王晓丹.基于最小k近邻错分率编码确定方法及其在多类分类中的应用[J].控制与决策, 2010, 26(9):1296-1302. Zhou Jindeng, Wang Xiaodan.Designing of output codes based on minimal k nearest neighbor classifying error and its application in multi-class classification[J].Control and Decision, 2010, 26(9):1296-1302.(in Chinese)
[28] 周进登, 王晓丹.基于混淆矩阵的自适应纠错输出编码多类分类方法[J].系统工程与电子技术, 2012, 34(7):220-226. Zhou Jindeng, Wang Xiaodan.Multiclass classification of adaptive error-correcting output codes based on confusion matrix[J].Systems Engineering and Electronics, 2012, 34(7):220-226.(in Chinese)
[29] S Escaler, David Masip, et al.Online error correcting output codes[J].Pattern Recognition Letters, 2011, 32(3):458-467.
[30] Miguel Angel Bautista, Sergio Escalera, et al.Minimal design of error-correcting output codes[J].Pattern Recognition Letters, 2012, 33(10):693-702.
[31] Nima Hatami.Thinned-ECOC ensemble based on sequential code shrinking[J].Expert Systems with Application, 2012, 39(1):936-947.
[32] 蒋艳凰, 赵强利, 杨学军.一种搜索编码法及其在监督分类中的应用[J].软件学报, 2005, 45(6):1081-1088. Jiang Yan-Huang, Zhao Qiang-Li, Yang Xue-Jun.A search coding method and its application in supervised classification[J].Journal of Software, 2005, 45(6):1081-1088.(in Chinese)
[33] Ludmila I, Kuncheva.Using diversity measures for generating error-correcting output codes in classibler ensembles[J].Pattern Recognition Letters, 2005, 26(5):83-90.
[34] T Windeatt, R Ghaderi.Coding and decoding strategies for multi-class learning problems[J].Information Fusion, 2003, 43(4):11-21.
[35] James G.Majority Vote Classifiers:Theory and Applications[D].CA:Stanford University, 1998.
[36] Erin LAllwein, Robert E Schapire, Yoram Singer.Reducing multiclass to binary:A unifying approach for margin classifiers[A].Machine Learning:Proceedings of the Seventeenth International Conference[C].Palo Alto:Stanford University, 2000.1545-1550.
[37] S Escalera, O Pujol, P Radeva.On the decoding process in ternary error-correcting output codes[J].IEEE Trans Pattern Analysis and Machine Intelligence, 2010, 32(1):120-134.
[38] E B Kong, T G Diettrich.Probability estimation via error correcting output coding[A].International Conference of Artificial Intelligence and Soft Computing[C].Banff, Canada:IEEE, 1997.
[39] Reza Ghaderi, Terry Windeatt.Least squares and estimation measures via error correcting output code[A].2nd International Workshop on Multiple Classifier Systems[C].Cambridge, UK:Springer-Verlag, 2001.148-157.
[40] A Passerini, M Pontil, P Frasconi.New results on error correcting output codes of Kernel machines[J].IEEE Trans Neural Networks, 2004, 15(1):45-54.
[41] Kittler J, Ghaderi R, Windeatt T, Matas J.Face identification and verification via ECOC[A].Third Int Conf Audio and Video Based Biometric Person Authentication[C].Halmstad, Sweden:IEEE, 2001.1-13.
[42] Zhou Jindeng, Wang Xiaodan, et al.Decoding design based on conditional probabilities in ternary error-correcting output codes[J].Pattern Recognition, 2012, 45(4):1342-1351.
[43] Guoqiang Zhong, Cheng-Lin Liu.Error-correcting output codes based ensemble feature extraction[J].Pattern Recogniton, 2013, 46(4):1091-1100.
[44] P Simeon, C Marrocco, F Tortorella.Design of reject rules for ECOC classification systems[J].Pattern Recognition, 2012, 45(2):863-875.
[45] Mikhail Petrovskiy.Probabilityestimation in error correcting output coding framework using game theory[J].Lecture Notes in Computer Science, 2005, 3809(5):186-196.
[46] Omid Dehzangi, Bin Ma, et, al.Discriminative feature extraction for speech recognition using continuous output codes[J].Pattern Recognition Letters, 2012, 33(13):1703-1709.
[47] Sergio Escalera, Oriol Pujol, Josepa Mauri.IVUS tissue characterization with subclass error-correcting output codes[J].Computer Vision and Pattern Recognition, 2008, 34(5):1-8.
[48] T Windeatt, G Ardeshir.Boosted ECOC ensembles for face recognition[J].Pattern Recognition, 2003, 35(4):165-168.
[49] Hongming Zhang, Wen Gao.Robustmulti-view face detection using error correcting output codes[J].Lecture Notes in Computer Science, 2006, 3954(11):1-12.
[50] Elif Deryableyli.ECG beats classification using multiclass support vector machines with error correcting output codes[J].Digital Signal Processing, 2007, 45(17):675-684.
[51] 陶晓燕, 姬红兵.一种基于SOM解码的多类支持向量机[J].系统工程与电子技术, 2006, 24(4):1147-1151. Tao Xiao-yan, Ji Hong-bing.Multi-class SVM based on SOM decoding[J].Systems Engineering and Electronics, 2006, 24(4):1147-1151.(in Chinese)
[52] 胡莹岑, 王友仁, 崔江.模拟电路的一种纠错码SVM诊断方法[J].计算机辅助设计与图形学学报, 2011, 23(11):1931-1937. Hu Yingcen, Wang Youren, Cui Jiang.Method ofanalog circuit diagnosis based on ECOC and SVM[J].Journal of Computer-Aided Design & Computer Graphics, 2011, 23(11):1931-1937.(in Chinese) [LL]
[53] 辛轶, 郭躬德, 陈黎飞.半监督层次纠错输出编码算法[J].小型微型计算机系统, 2010, 31(8):1660-1664. Xin Yi, Guo Gongde, Chen Lifei.Semi-supervised Basedhierarchical ECOC algorithm[J].Journal of Chinese Computer Systems, 2010, 31(8):1660-1664.(in Chinese)
[54] 郭巍, 张平, 朱良.基于AdaBoost.ECOC的合成孔径雷达图像目标识别研究[J].哈尔滨工程大学学报, 2010, 31(2):232-236. Guo Wei, Zhang Ping, Zhu Liang.Research onsynthetic aperture radar image target recognition based on AdaBoostECOC[J].Journal of Harbin Engineering University, 2010, 31(2):232-236.(in Chinese)
[55] 周进登, 王晓丹.加权解码在解决纠错输出编码consistent-diverse平衡问题的应用[J].电子学报, 2011, 39(7):1514-1522. Zhou Jindeng, Wang Xiaodan, et al.Application of weighted decoding for the consistent-diverse balance problem of error correcting output codes[J].Acta Electronica Sinica, 2011, 39(7):1514-1522.(in Chinese)

ECOC多类分类研究综述

An Overview of Multi-Classification Based on Error-Correcting Output Codes

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	吴军君, 王涛, 王英楷, 王星辉. 基于迁移学习的LiPON制备工艺模拟优化[J]. 电子学报, 2023, 51(3): 687-693.
[2]	李雪莹, 王田路, 梁鹏, 王翀. 基于系统模型的用户评论中非功能需求的自动分类[J]. 电子学报, 2022, 50(9): 2079-2089.
[3]	黄璐, 蔚保国, 李宏生, 李隽, 贾浩男, 程建强, 李雅宁. GNSS拒止环境下的伪卫星指纹定位方法[J]. 电子学报, 2022, 50(4): 811-822.
[4]	崔亚奇, 何友, 唐田田, 熊伟. 一种深度学习航迹关联方法[J]. 电子学报, 2022, 50(3): 759-763.
[5]	蒋华伟, 郭陶, 杨震. 车辆路径问题研究进展[J]. 电子学报, 2022, 50(2): 480-492.
[6]	张笑宇, 沈超, 蔺琛皓, 李前, 王骞, 李琦, 管晓宏. 面向机器学习模型安全的测试与修复[J]. 电子学报, 2022, 50(12): 2884-2918.
[7]	郑锐, 汪秋云, 林卓庞, 靖蓉琦, 姜政伟, 傅建明, 汪姝玮. 一种基于威胁情报层次特征集成的挖矿恶意软件检测方法[J]. 电子学报, 2022, 50(11): 2707-2715.
[8]	张梦, 郑建宏, 刘香燕, 何云. 基于集成学习的全双工中继系统安全中继选择方案研究[J]. 电子学报, 2021, 49(9): 1852-1856.
[9]	郑海颖, 王峰, 姜维, 王志强, 姚西文. 神经网络训练策略对高分辨率遥感图像场景分类性能影响的评估[J]. 电子学报, 2021, 49(8): 1599-1614.
[10]	周东明, 张灿龙, 李志欣, 王智文. 基于多层级视觉融合的图像描述模型[J]. 电子学报, 2021, 49(7): 1286-1290.
[11]	侯秀聪, 赖晓平, 曹九稳. 正则化超限学习机的最大分划广义交替方向乘子法[J]. 电子学报, 2021, 49(4): 625-630.
[12]	陈长青, 郭春, 崔允贺, 申国伟, 蒋朝惠. 基于API短序列的勒索软件早期检测方法[J]. 电子学报, 2021, 49(3): 586-595.
[13]	刘润滋, 吴伟华, 张文柱, 周笛, 张琰. 基于图学习的密集空间网络传输资源调度方法[J]. 电子学报, 2021, 49(11): 2133-2137.
[14]	仇祝令, 查宇飞, 吴敏, 王青. 基于注意力学习的正则化相关滤波跟踪算法[J]. 电子学报, 2020, 48(9): 1762-1768.
[15]	宋宇琦, 高旻, 李骏东, 荣文戈, 熊庆宇. 网络欺凌检测综述[J]. 电子学报, 2020, 48(6): 1220-1229.