多分类问题代价敏感AdaBoost算法

付忠良

doi:10.3724/SP.J.1004.2011.00973

多分类问题代价敏感AdaBoost算法

doi: 10.3724/SP.J.1004.2011.00973

付忠良

1.
中国科学院成都计算机应用研究所成都 610041

计量
- 文章访问数: 2602
- HTML全文浏览量: 92
- PDF下载量: 2081
- 被引次数: 0
出版历程
- 收稿日期: 2010-09-02
- 修回日期: 2011-03-24
- 刊出日期: 2011-08-20

Cost-sensitive AdaBoost Algorithm for Multi-class Classification Problems

FU Zhong-Liang

1.
Chengdu Computer Applications Institute, Chinese Academy of Sciences, Chengdu 610041

摘要

摘要: 针对目前多分类代价敏感分类问题在转换成二分类代价敏感分类问题存在的代价合并问题, 研究并构造出了可直接应用于多分类问题的代价敏感AdaBoost算法.算法具有与连续AdaBoost算法类似的流程和误差估计. 当代价完全相等时, 该算法就变成了一种新的多分类的连续AdaBoost算法, 算法能够确保训练错误率随着训练的分类器的个数增加而降低, 但不直接要求各个分类器相互独立条件, 或者说独立性条件可以通过算法规则来保证, 但现有多分类连续AdaBoost算法的推导必须要求各个分类器相互独立. 实验数据表明, 算法可以真正实现分类结果偏向错分代价较小的类, 特别当每一类被错分成其他类的代价不平衡但平均代价相等时, 目前已有的多分类代价敏感学习算法会失效, 但新方法仍然能实现最小的错分代价. 研究方法为进一步研究集成学习算法提供了一种新的思路, 得到了一种易操作并近似满足分类错误率最小的多标签分类问题的AdaBoost算法.
- 代价敏感学习 /
- 多分类问题 /
- 多标签分类问题 /
- 连续AdaBoost /
- 代价敏感分类
Abstract: To solve the cost merging problem when multi-class cost-sensitive classification is transferred to two-class cost-sensitive classification, a cost-sensitive AdaBoost algorithm which can be applied directly to multi-class classification is constructed. The proposed algorithm is similar to real AdaBoost algorithm in algorithm flow and error estimation formula. When the costs are equal, this algorithm becomes a new real AdaBoost algorithm for multi-class classification, guaranteeing that the training error of the combination classifier could be reduced while the number of trained classifiers increased. The new real AdaBoost algorithm does not need to meet the condition that every classifier must be independent, that is to say, the independent condition of classifiers can be derived from the new algorithm, instead of being the must for current real AdaBoost algorithm for multi-class classification. The experimental results show that this new algorithm always ensures the classification result trends to the class with the smallest cost, while the existing multi-class cost-sensitive learning algorithm may fail if the costs of being erroneously classified to other classes are imbalanced and the average cost of every class is equal. The research method above provides a new idea to construct new ensemble learning algorithms, and an AdaBoost algorithm for multi-label classification is given, which is easy to operate and approximately meets the smallest error classification rate.
- Cost-sensitive learning /
- multi-class classification problem /
- multi-label classification problem /
- real AdaBoost /
- cost-sensitive classification

HTML全文

参考文献(1)

[1]

Turney P. Types of cost in inductive concept learning. In: Proceedings of the Cost-sensitive Learning Workshop at the 17th ICML Conference. Stanford, USA: NRC, 2000. 15-21[2] Ting K M. An instance-weighting method to induce cost-sensitive trees. IEEE Transactions on Knowledge and Data Engineering, 2002, 14(3): 659-665[3] Domingos P. MetaCost: a general method for making classifiers cost-sensitive. In: Proceedings of the 5th International Conference on Knowledge Discovery and Data Mining. New York, USA: ACM, 1999. 155-164[4] Elkan C. The foundations of cost-sensitive learning. In: Proceedings of the 17th International Joint Conference of Artificial Intelligence. San Francisco, USA: Morgan Kaufmann, 2001. 973-978[5] Bruka I, Kockova S. A support for decision-making: cost-sensitive learning system. Artificial Intelligence in Medicine, 1999, 6(1): 67-82[6] Zadrozny B, Langford J, Abe N. Cost-sensitive learning by cost-proportionate example weighting. In: Proceedings of the 3th IEEE International Conference on Data Mining. Washington D.C., USA: IEEE, 2003. 435-442[7] Ling C X, Sheng V S, Yang Q. Test strategies for cost-sensitive decision trees. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(8): 1055-1067[8] Chai X, Deng L, Yang Q, Ling C X. Test-cost sensitive Naive Bayes classification. In: Proceedings of the 4th IEEE International Conference on Data Mining. Washington D.C., USA: IEEE, 2004. 51-58[9] Ling C X, Sheng V S. A comparative study of cost-sensitive classifiers. Chinese Journal of Computers, 2007, 30(8): 1203-1211[10] Ye Zhi-Fei, Wen Yi-Min, Lv Bao-Liang. A survey of imbalanced pattern classification problem. Caai Transactions on Intelligent Systems, 2009, 4(2): 138-156(叶志飞, 文益民, 吕宝粮. 不平衡分类问题研究综述. 智能系统学报, 2009, 4(2): 138-156)[11] Ting K M, Zheng Z. Boosting cost-sensitive trees. In: Proceedings of the 1st International Conference on Discovery Science. London, UK: Springer, 1998. 244-255[12] Fan W, Stolfo S J, Zhang J, Chan P K. AdaCost: misclassification cost-sensitive boosting. In: Proceedings of the 16th International Conference on Machine Learning. Bled, USA: Morgan Kaufmann, 1999. 97-105[13] Schapire R E, Singer Y. Improved boosting algorithms using confidence-rated predictions. Machine Learning, 1999, 37(3): 297-336[14] Yin Hui, Cao Yong-Feng, Sun Hong. Urban scene classification based multi-dimensional pyramid representation and AdaBoost using high resolution SAR images. Acta Automatica Sinica, 2010, 36(8): 1099-1106(殷慧, 曹永锋, 孙洪. 基于多维金字塔表达和AdaBoost的高分辨率SAR图像城区场景分类算法. 自动化学报, 2010, 36(8): 1099-1106)[15] Ge Jun-Feng, Luo Yu-Pin. A comprehensive study for asymmetric AdaBoost and its application in object detection. Acta Automatica Sinica, 2009, 35(11): 1403-1409[16] Fu Zhong-Liang. The effectiveness analysis of AdaBoost. Journal of Computer Research and Development, 2008, 45(10): 1747-1755(付忠良. 关于AdaBoost有效性的分析. 计算机研究与发展, 2008, 45(10): 1747-1755)[17] Fu Zhong-Liang. Effective property and best combination of classifiers linear combination. Journal of Computer Research and Development, 2009, 46(7): 1206-1216(付忠良. 分类器线性组合的有效性和最佳组合问题的研究. 计算机研究与发展, 2009, 46(7): 1206-1216)[18] Zhu J, Rosset S, Zou H, Hastie T. Multi-class AdaBoost. Statistics and Its Interface, 2009, 2(3): 349-360[19] Boutell M R, Luo J, Shen X, Brown C M. Learning multi-label scene classification. Pattern Recognition, 2004, 37(9): 1757-1771[20] Zhang M L, Zhou Z H. M3MIML: a maximum margin method for multi-instance multi-label learning. In: Proceedings of the 8th IEEE International Conference on Data Mining. Pisa, Italy, 2008. 688-697[21] Zhang M L, Zhou Z H. ML-KNN: a lazy learning approach to multi-label learning. Pattern Recognition, 2007, 40(7): 2038-2048[22] Fu Zhong-Liang, Zhao Xiang-Hui. Dynamic combination method of classifiers and ensemble learning algorithms based on classifiers combination. Journal of Sichuan University (Engineering Science), 2011, 43(2): 58-65(付忠良, 赵向辉. 分类器动态组合及基于分类器组合的集成学习算法. 四川大学学报(工程科学版), 2011, 43(2): 58-65)

施引文献

资源附件(0)

访问统计