Classifiability-Based Omnivariate Decision Trees
- 7 November 2005
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Neural Networks
- Vol. 16 (6), 1547-1560
- https://doi.org/10.1109/tnn.2005.852864
Abstract
Top-down induction of decision trees is a simple and powerful method of pattern classification. In a decision tree, each node partitions the available patterns into two or more sets. New nodes are created to handle each of the resulting partitions and the process continues. A node is considered terminal if it satisfies some stopping criteria (for example, purity, i.e., all patterns at the node are from a single class). Decision trees may be univariate, linear multivariate, or nonlinear multivariate depending on whether a single attribute, a linear function of all the attributes, or a nonlinear function of all the attributes is used for the partitioning at each node of the decision tree. Though nonlinear multivariate decision trees are the most powerful, they are more susceptible to the risks of overfitting. In this paper, we propose to perform model selection at each decision node to build omnivariate decision trees. The model selection is done using a novel classifiability measure that captures the possible sources of misclassification with relative ease and is able to accurately reflect the complexity of the subproblem at each node. The proposed approach is fast and does not suffer from as high a computational burden as that incurred by typical model selection algorithms. Empirical results over 26 data sets indicate that our approach is faster and achieves better classification accuracy compared to statistical model select algorithms.Keywords
This publication has 27 references indexed in Scilit:
- SmcHD1, containing a structural-maintenance-of-chromosomes hinge domain, has a critical role in X inactivationNature Genetics, 2008
- A New Information Processing Measure for Adaptive Complex SystemsIEEE Transactions on Neural Networks, 2004
- A compact 3-D VLSI classifier using bagging threshold network ensemblesIEEE Transactions on Neural Networks, 2003
- ANN-DT: an algorithm for extraction of decision trees from artificial neural networksIEEE Transactions on Neural Networks, 1999
- Multivariate decision treesMachine Learning, 1995
- An evaluation of intrinsic dimensionality estimatorsIeee Transactions On Pattern Analysis and Machine Intelligence, 1995
- Neural implementation of tree classifiersIEEE Transactions on Systems, Man, and Cybernetics, 1995
- Growing and pruning neural tree networksIEEE Transactions on Computers, 1993
- Tree-Structured Classification via Generalized Discriminant AnalysisJournal of the American Statistical Association, 1988
- A Theory of Program Size Formally Identical to Information TheoryJournal of the ACM, 1975