More Web Proxy on the site http://driver.im/

research-article

An Instance-Weighting Method to Induce Cost-Sensitive Trees

Author:

K. M. TingAuthors Info & Claims

IEEE Transactions on Knowledge and Data Engineering, Volume 14, Issue 3

Pages 659 - 665

https://doi.org/10.1109/TKDE.2002.1000348

Published: 01 May 2002 Publication History

Abstract

We introduce an instance-weighting method to induce cost-sensitive trees. It is a generalization of the standard tree induction process where only the initial instance weights determine the type of tree to be induced minimum error trees or minimum high cost error trees. We demonstrate that it can be easily adapted to an existing tree learning algorithm. Previous research provides insufficient evidence to support the idea that the greedy divide-and-conquer algorithm can effectively induce a truly cost-sensitive tree directly from the training data. We provide this empirical evidence in this paper. The algorithm incorporating the instance-weighting method is found to be better than the original algorithm in terms of total misclassification costs, the number of high cost errors, and tree size in two-class data sets. The instance-weighting method is simpler and more effective in implementation than a previous method based on altered priors.

References

[1]

C. Blake E. Keogh and C.J. Merz, “UCI Repository of Machine Learning Databases,” Univ. of California, Dept. Information and Computer Science, http://www.ics.uci.edu/~mlearn/MLRepository.html, 1998.]]

[2]

J.P. Bradford C. Kunz R. Kohavi C. Brunk and C.E. Brodley, “Pruning Decision Trees with Misclassification Costs,” Proc. 10th European Conf. Machine Learning, pp. 131-136, 1998.]]

Digital Library

[3]

L. Breiman J.H. Friedman R.A. Olshen and C.J. Stone, Classification and Regression Trees. Belmont, Cailf.: Wadsworth, 1984.]]

[4]

U. Knoll G. Nakhaeizadeh and B. Tausend, “Cost-Sensitive Pruning of Decision Trees,” Proc. Eighth European Conf. Machine Learning, pp. 383-386, 1994.]]

Digital Library

[5]

D. Michie D.J. Spiegelhalter and C.C. Taylor, Machine Learning, Neural and Statistical Classification. Ellis Horwood Limited, 1994.]]

Digital Library

[6]

S.W. Norton, “Generating Better Decision Trees,” Proc. 11th Int'l Joint Conf. Artificial Intelligence, pp. 800-805, 1989.]]

[7]

M. Núñez, “The Use of Background Knowledge in Decision Tree Induction,” Machine Learning, vol. 6, pp. 231-250, 1991.]]

Digital Library

[8]

M. Pazzani C. Merz P. Murphy K. Ali T. Hume and C. Brunk, “Reducing Misclassification Costs,” Proc. 11th Int'l Conf. Machine Learning, pp. 217-225, 1994.]]

[9]

J.R. Quinlan, C4.5: Program for Machine Learning. Morgan Kaufmann, 1993.]]

Digital Library

[10]

J.R. Quinlan, “Boosting, Bagging, and C4.5,” Proc. 13th Nat'l Conf. Artificial Intelligence, pp. 725-730, 1996.]]

[11]

J.R. Quinlan, “C5,” http://rulequest.com, 1997.]]

[12]

R.E. Schapire Y. Freund P. Bartlett and W.S. Lee, “Boosting the Margin: A New Explanation for the Effectiveness of Voting Methods,” Proc. 14th Int'l Conf. Machine Learning, pp. 322-330, 1997.]]

Digital Library

[13]

M. Tan, “Cost-Sensitive Learning of Classification Knowledge and Its Applications in Robotics,” Machine Learning, vol. 13, pp. 7-33, 1993.]]

Digital Library

[14]

K.M. Ting, “A Comparative Study of Cost-Sensitive Boosting Algorithms,” Proc. 17th Int'l Conf. Machine Learning, pp. 983-990, 2000.]]

Digital Library

[15]

K.M. Ting and Z. Zheng, “Boosting Cost-Sensitive Trees,” Proc. First Int'l Conf. Discovery Science, pp. 244-255, 1998.]]

Digital Library

[16]

P.D. Turney, “Cost-Sensitive Classification: Empirical Evaluation of a Hybrid Genetic Decision Tree Induction Algorithm,” J. Artificial Intelligence Research, vol. 2, pp. 369-409, 1995.]]

Digital Library

[17]

G.I. Webb, “Cost-Sensitive Specialization,” Proc. 1996 Pacific Rim Int'l Conf. Artificial Intelligence, pp. 23-34, 1996.]]

Digital Library

Cited By

Nishtala SRavindran B(2024)Cost-Sensitive Trees for Interpretable Reinforcement LearningProceedings of the 7th Joint International Conference on Data Science & Management of Data (11th ACM IKDD CODS and 29th COMAD)10.1145/3632410.3632443(91-99)Online publication date: 4-Jan-2024
https://dl.acm.org/doi/10.1145/3632410.3632443
Xu YYu ZChen C(2024)Improved Contraction-Expansion Subspace Ensemble for High-Dimensional Imbalanced Data ClassificationIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.338427436:10(5194-5205)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1109/TKDE.2024.3384274
Hou BFu CXue M(2024)An extended belief rule-based system with hybrid sampling strategy for imbalanced rule baseInformation Sciences: an International Journal10.1016/j.ins.2024.121288684:COnline publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1016/j.ins.2024.121288
Show More Cited By

Index Terms

An Instance-Weighting Method to Induce Cost-Sensitive Trees
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies
      1. Discrete space search
      2. Game tree search
  2. Machine learning
    1. Learning settings
    2. Machine learning approaches
      1. Logical and relational learning
        Inductive logic learning
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Machine learning theory
      1. Inductive inference

Recommendations

Cost-Sensitive self-training
Canadian AI'12: Proceedings of the 25th Canadian conference on Advances in Artificial Intelligence

In some real-world applications, it is time-consuming or expensive to collect much labeled data, while unlabeled data is easier to obtain. Many semi-supervised learning methods have been proposed to deal with this problem by utilizing the unlabeled ...
Extremal cost binary trees
Cost-Sensitive Decision Trees with Pre-pruning
CAI '07: Proceedings of the 20th conference of the Canadian Society for Computational Studies of Intelligence on Advances in Artificial Intelligence

This paper explores two simple and efficient pre-pruning strategies for the cost-sensitive decision tree algorithm to avoid overfitting. One is to limit the cost-sensitive decision trees to a depth of two. The other is to prune the trees with a pre-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Knowledge and Data Engineering

IEEE Transactions on Knowledge and Data Engineering Volume 14, Issue 3

May 2002

206 pages

ISSN:1041-4347

Issue’s Table of Contents

Copyright © Copyright © 2002 IEEE. All Rights Reserved.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 May 2002

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

123
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 31 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nishtala SRavindran B(2024)Cost-Sensitive Trees for Interpretable Reinforcement LearningProceedings of the 7th Joint International Conference on Data Science & Management of Data (11th ACM IKDD CODS and 29th COMAD)10.1145/3632410.3632443(91-99)Online publication date: 4-Jan-2024
https://dl.acm.org/doi/10.1145/3632410.3632443
Xu YYu ZChen C(2024)Improved Contraction-Expansion Subspace Ensemble for High-Dimensional Imbalanced Data ClassificationIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.338427436:10(5194-5205)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1109/TKDE.2024.3384274
Hou BFu CXue M(2024)An extended belief rule-based system with hybrid sampling strategy for imbalanced rule baseInformation Sciences: an International Journal10.1016/j.ins.2024.121288684:COnline publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1016/j.ins.2024.121288
Zhang ZRong JQi ZYang YZheng XGao JLi WYuan T(2024)A multi-species pest recognition and counting method based on a density map in the greenhouseComputers and Electronics in Agriculture10.1016/j.compag.2023.108554217:COnline publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1016/j.compag.2023.108554
Lenka SBisoy SPriyadarshini R(2024)Multiple optimized ensemble learning for high-dimensional imbalanced credit scoring datasetsKnowledge and Information Systems10.1007/s10115-024-02129-z66:9(5429-5457)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s10115-024-02129-z
Han XSong XDong XWei YLiu MNie L(2023)DBiased-P: Dual-Biased Predicate Predictor for Unbiased Scene Graph GenerationIEEE Transactions on Multimedia10.1109/TMM.2022.319013525(5319-5329)Online publication date: 1-Jan-2023
https://dl.acm.org/doi/10.1109/TMM.2022.3190135
Chen HCheng Y(2023)Travel Mode Choice Prediction Using Imbalanced Machine LearningIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2023.323768124:4(3795-3808)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1109/TITS.2023.3237681
Pei WXue BZhang MShang LYao XZhang Q(2023)A Survey on Unbalanced Classification: How Can Evolutionary Computation Help?IEEE Transactions on Evolutionary Computation10.1109/TEVC.2023.325723028:2(353-373)Online publication date: 14-Mar-2023
https://dl.acm.org/doi/10.1109/TEVC.2023.3257230
Wei ZZhang LZhao L(2023)Minority-prediction-probability-based oversampling technique for imbalanced learningInformation Sciences: an International Journal10.1016/j.ins.2022.11.148622:C(1273-1295)Online publication date: 9-Mar-2023
https://dl.acm.org/doi/10.1016/j.ins.2022.11.148
Shifman DCohen IHuang KXian XSinger G(2023)An adaptive machine learning algorithm for the resource-constrained classification problemEngineering Applications of Artificial Intelligence10.1016/j.engappai.2022.105741119:COnline publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1016/j.engappai.2022.105741
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents