The random subspace method for constructing decision forests
IEEE Transactions on Pattern Analysis and Machine IntelligencePublished 1 January 1998
Tin Kam Ho
Citations6,737
SJR quartileQ1
SJR score3.91
SNIP5.99
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A method to construct a decision tree based classifier is proposed that maintains highest accuracy on training data and improves on generalization accuracy as it grows in complexity.
Abstract
Much of previous attention on decision trees focuses on the splitting criteria and optimization of tree sizes. The dilemma between overfitting and achieving maximum accuracy is seldom resolved. A method to construct a decision tree based classifier is proposed that maintains highest accuracy on training data and improves on generalization accuracy as it grows in complexity. The classifier consists of multiple trees constructed systematically by pseudorandomly selecting subsets of components of the feature vector, that is, trees constructed in randomly chosen subspaces. The subspace method is compared to single-tree classifiers and other forest construction methods by experiments on publicly available datasets, where the method's superiority is demonstrated. We also discuss independence between trees in a forest and relate that to the combined classification accuracy.
Keywords
Computer Science
The Nature of Statistical Learning Theory
39,279 Citations1995Vladimir Vapnik
BiometricsClassification and Regression Trees.
23,841 Citations1984Alexander Gordon, Leo Breiman +3 more
C4.5: Programs for Machine Learning
23,665 Citations1992J. R. Quinlan
A complete guide to the C4.5 system as implemented in C for the UNIX environment, which starts from simple core learning methods and shows how they can be elaborated and extended to deal with typical problems such as missing data and over hitting.
Machine LearningBagging predictors
16,377 Citations1996Leo Breiman
Tests on real and simulated data sets using classification and regression trees and subset selection in linear regression show that bagging can give substantial gains in accuracy.
Machine LearningInduction of Decision Trees
14,815 Citations1986J. R. Quinlan
This paper summarizes an approach to synthesizing decision trees that has been used in a variety of systems, and it describes one such system, ID3, in detail, which is described in detail.
Machine LearningInduction of decision trees
12,383 Citations1986J. R. Quinlan
This paper summarizes an approach to synthesizing decision trees that has been used in a variety of systems, and it describes one such system, ID3, in detail, which is described in detail.
Experiments with a new boosting algorithm
7,585 Citations1996Yoav Freund, Robert E. Schapire
Random decision forests
4,947 Citations2002Tin Kam Ho
IEEE Transactions on Pattern Analysis and Machine IntelligenceDecision combination in multiple classifier systems
1,511 Citations1994Tin Kam Ho, J.J. Hull +1 more
This work proposes three methods based on the highest rank, the Borda count, and logistic regression for class set reranking that have been tested in applications of degraded machine-printed characters and works from large lexicons, resulting in substantial improvement in overall correctness.
National Conference on Artificial IntelligenceBagging, boosting, and C4.S
1,262 Citations1996J. R. Quinlan
Journal of Artificial Intelligence ResearchA System for Induction of Oblique Decision Trees
583 Citations1994Sreerama K. Murthy, Simon Kasif +1 more
This system, OC1, combines deterministic hill-climbing with two forms of randomization to find a good oblique split (in the form of a hyperplane) at each node of a decision tree.
Machine LearningAn Empirical Comparison of Selection Measures for Decision-Tree Induction
464 Citations1989John Mingers
The paper considers a number of different measures and experimentally examines their behavior in four domains and shows that the choice of measure affects the size of a tree but not its accuracy, which remains the same even when attributes are selected randomly.
Machine LearningAn empirical comparison of selection measures for decision-tree induction
312 Citations1989John Mingers
The paper considers a number of different measures and experimentally examines their behavior in four domains and shows that the choice of measure affects the size of a tree but not its accuracy, which remains the same even when attributes are selected randomly.
IEEE Transactions on Pattern Analysis and Machine IntelligenceJoint induction of shape features and tree classifiers
197 Citations1997Yali Amit, Donald Geman +1 more
A very large family of binary features for two-dimensional shapes determined by inductive learning during the construction of classification trees is introduced, which makes it possible to narrow the search for informative ones at each node of the tree.
IEEE Transactions on Pattern Analysis and Machine IntelligenceHierarchical Classifier Design Using Mutual Information
183 Citations1982Ishwar K. Sethi, G. P. R. Sarvarayudu
A nonparametric algorithm is presented for the hierarchical partitioning of the feature space that generates an efficient partitioning tree for specified probability of error by maximizing the amount of average mutual information gain at each partitioning step.
Induction of Oblique Decision Trees.
161 Citations1993David G. Heath, Simon Kasif +1 more
A randomized technique for partitioning examples using oblique hyperplanes to create smaller but equally accurate decision trees than those created by other methods, and is found to produce surprisingly small trees without losing predic-tive accuracy.
Journal of the Operational Research SocietyExpert Systems—Rule Induction with Statistical Data
154 Citations1987John Mingers
Rule induction has been proposed as a way of speeding up the acquisition of knowledge for expert systems but can only deal with determinate data and extensions to deal with statistical data are explored.
Annals of Mathematics and Artificial IntelligenceStochastic discrimination
144 Citations1990E. M. Kleinberg
A general method is introduced for separating points in multidimensional spaces through the use of stochastic processes, called Stochastic discrimination.
Machine intelligence and pattern recognitionMultiple decision trees
139 Citations1990Suk Wah Kwok, Chris Carter
This paper describes experiments, on two domains, to investigate the effect of averaging over predictions of multiple decision trees, instead of using a single tree, finding that it is best to average across sets of trees with different structure; this usually gives better performance than any of the constituent trees, including the ID3 tree.
The Annals of StatisticsAn overtraining-resistant stochastic modeling method for pattern recognition
135 Citations1996E. M. Kleinberg
A generic approach for solving problems in pattern recognition based on the synthesis of accurate multiclass discriminators from large numbers of very inaccurate weak models through the use of discrete stochastic processes is introduced.
Machine LearningTechnical note: Bias and the quantification of stability
120 Citations1995Peter D. Turney
This paper introduces a method for quantifying stability, based on a measure of the agreement between concepts, and discusses the relationships among stability, predictive accuracy, and bias.
Building projectable classifiers of arbitrary complexity
97 Citations1996Tin Kam Ho, E. M. Kleinberg
This work presents a method that constructs a classifier up to arbitrary complexity while presenting generalization accuracy, and reveals that the conflict is resolvable by building classifiers based on projectable elements, which are weak discriminators that perform equally well for both training and testing data.
Pattern RecognitionMultiple binary decision tree classifiers
66 Citations1990Seymour Shlien
This paper demonstrates that higher classification accuracies can be obtained from the same training set by using a combination of decision trees and by reaching a consensus using Dempster and Shafer's theory of evidence.
Computer Vision and Image UnderstandingPattern Classification with Compact Distribution Maps
46 Citations1998Tin Kam Ho, Henry S. Baird
For applications to arbitrary domains, this work presents a method to automatically construct feature transformations that are suitable for such mappings and illustrates the method by an application in a challenging character recognition problem with thousands of classes.
Journal of ClassificationAutomated design of multiple-class piecewise linear classifiers
45 Citations1989Young-Tae Park, Jack Sklansky
Experiments on multiple-class data obtained from ship images show that classifiers designed by this method yield approximately the same error rate as the bestk-nearest neighbor rule, while providing faster decisions.
C4.5 decision forests
29 Citations2002Tin Kam Ho
This work proposes a method to construct a decision tree based classifier that maintains highest accuracy on training data and improves on generalization accuracy as it grows in complexity.
Pattern RecognitionStructure-driven induction of decision tree classifiers through neural learning
26 Citations1997Ishwar K. Sethi, Jae Hung Yoo
A structure-driven approach for induction of decision trees, SDIDT, is proposed, which generates compact trees that have multifeature splits at each internal node which are determined on global rather than local basis; consequently it produces decision trees yielding better classification and interpretation of the underlying relationships in the data.
Recognition of handwritten digits by combining independent learning vector quantizations
21 Citations2002T.K. Ho
In an application of this LVQ method to the recognition of handwritten digits, it is shown that the classifier can be improved almost monotonically without suffering from over-adaptation to the training data.
An alternative method of stochastic discrimination with applications to pattern recognition
20 Citations1995Roger Steven Berlind
This dissertation introduces an alternative method of performing stochastic discrimination in pattern recognition which differs in several aspects from the original method introduced by Kleinberg, and discusses four variations of the method, each of which uses different variations of Ho's discriminant functions.
Pattern Recognition LettersNonparametric classification using matched binary decision trees
20 Citations1992Seymour Shlien
A new technique for designing binary decision tree classifiers that is chosen at each node in such a way that the classifier formed by combining the decision trees behaves in an optimal fashion is described.
Perfect metrics
17 Citations2002Tuyen Ho Thi Thanh, Henry S. Baird
In a test on over three million images, the perfect-metric classifier achieved better than 99% top-choice accuracy and it is shown that it is superior to a conventional parametric classifier.
Advances in psychologyChapter 18 Committees of decision trees
15 Citations1996David Heath, Simon Kasif +1 more
This paper has developed a randomized decision tree induction algorithm, which generates different decision trees every time it is run, and combines these trees using a majority voting scheme in order to overcome small errors that appear in individual trees.