Top-down induction of decision trees classifiers - a survey
---
paper_title: Induction of decision trees

paper_content:

The technology for building knowledge-based systems by inductive inference from examples has been demonstrated successfully in several practical applications. 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. Results from recent studies show ways in which the methodology can be modified to deal with information that is noisy and/or incomplete. A reported shortcoming of the basic algorithm is discussed and two means of overcoming it are compared. The paper concludes with illustrations of current research directions.
---
paper_title: Lower bounds on learning decision lists and trees

paper_content:

k-decision lists and decision trees play important roles in learning theory as well as in practical learning systems, k-decision lists generalize classes such as monomials, k-DNF, and k-CNF and like these subclasses is polynomially PAC-learnable [19]. This leaves open the question of whether k-decision lists can be learned as efficiently as k-DNF. We answer this question negatively in a certain sense, thus disproving a claim in a popular textbook [2]. Decision trees, on the other hand, are not even known to be polynomially PAC-learnable, despite their widespread practical application. We will show that decision trees are not likely to be efficiently PAC-learnable. We summarize our specific results.
---
paper_title: Finding small equivalent decision trees is hard

paper_content:

Two decision trees are called decision equivalent if they represent the same function, i.e., they yield the same result for every possible input. We prove that given a decision tree and a number, to decide if there is a decision equivalent decision tree of size at most that number is NP-complete. As a consequence, finding a decision tree of minimal size that is decision equivalent to a given decision tree is an NP-hard problem. This result differs from the well-known result of NP-hardness of finding a decision tree of minimal size that is consistent with a given training set. Instead our result is a basic result for decision trees, apart from the setting of inductive inference. On the other hand, this result differs from similar results for BDDs and OBDDs: since in decision trees no sharing is allowed, the notion of decision tree size is essentially different from BDD size.
---
paper_title: Trading Accuracy for Simplicity in Decision Trees

paper_content:

When communicating concepts, it is often convenient or even necessary to define a concept approximately. A simple, although only approximately accurate concept definition may be more useful than a completely accurate definition which involves a lot of detail. This paper addresses the problem: given a completely accurate, but complex, definition of a concept, simplify the definition, possibly at the expense of accuracy, so that the simplified definition still corresponds to the concept “sufficiently” well. Concepts are represented by decision trees, and the method of simplification is tree pruning. Given a decision tree that accurately specifies a concept, the problem is to find a smallest pruned tree that still represents the concept within some specified accuracy. A pruning algorithm is presented that finds an optimal solution by generating a dense sequence of pruned trees, decreasing in size, such that each tree has the highest accuracy among all the possible pruned trees of the same size. An efficient implementation of the algorithm, based on dynamic programming, is presented and empirically compared with three progressive pruning algorithms using both artificial and real-world data. An interesting empirical finding is that the real-world data generally allow significantly greater simplification at equal loss of accuracy.
---
paper_title: An iterative growing and pruning algorithm for classification tree design

paper_content:

An efficient iterative method is proposed to grow and prune classification trees. This method divides the data sample into two subsets and iteratively grows a tree with one subset and prunes it with the other subset, successively interchanging the roles of the two subsets. The convergence and other properties of the algorithm are established. Theoretical and practical considerations suggest that the iterative tree growing and pruning algorithm should perform better and require less computation than other widely used tree growing and pruning algorithms. Numerical results on a waveform recognition problem are presented to support this view. >
---
paper_title: Induction of decision trees

paper_content:

The technology for building knowledge-based systems by inductive inference from examples has been demonstrated successfully in several practical applications. 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. Results from recent studies show ways in which the methodology can be modified to deal with information that is noisy and/or incomplete. A reported shortcoming of the basic algorithm is discussed and two means of overcoming it are compared. The paper concludes with illustrations of current research directions.
---
paper_title: Finding small equivalent decision trees is hard

paper_content:

Two decision trees are called decision equivalent if they represent the same function, i.e., they yield the same result for every possible input. We prove that given a decision tree and a number, to decide if there is a decision equivalent decision tree of size at most that number is NP-complete. As a consequence, finding a decision tree of minimal size that is decision equivalent to a given decision tree is an NP-hard problem. This result differs from the well-known result of NP-hardness of finding a decision tree of minimal size that is consistent with a given training set. Instead our result is a basic result for decision trees, apart from the setting of inductive inference. On the other hand, this result differs from similar results for BDDs and OBDDs: since in decision trees no sharing is allowed, the notion of decision tree size is essentially different from BDD size.
---
paper_title: A Distance-Based Attribute Selection Measure for Decision Tree Induction

paper_content:

This note introduces a new attribute selection measure for ID3-like inductive algorithms. This measure is based on a distance between partitions such that the selected attribute in a node induces the partition which is closest to the correct partition of the subset of training examples corresponding to this node. The relationship of this measure with Quinlan's information gain is also established. It is also formally proved that our distance is not biased towards attributes with large numbers of values. Experimental studies with this distance confirm previously reported results showing that the predictive accuracy of induced decision trees is not sensitive to the goodness of the attribute selection measure. However, this distance produces smaller trees than the gain ratio measure of Quinlan, especially in the case of data whose attributes have significantly different numbers of values.
---
paper_title: The attribute selection problem in decision tree generation

paper_content:

We address the problem of selecting an attribute and some of its values for branching during the top-down generation of decision trees. We study the class of impurity measures, members of which are typically used in the literature for selecting attributes during decision tree generation (e.g. entropy in ID3, GID3*, and CART; Gini Index in CART). We argue that this class of measures is not particularly suitable for use in classification learning. We define a new class of measures, called C-SEP, that we argue is better suited for the purposes of class separation. A new measure from C-SEP is formulated and some of its desirable properties are shown. Finally, we demonstrate empirically that the new algorithm, O-BTree, that uses this measure indeed produces better decision trees than algorithms that use impurity measures.
---
paper_title: An iterative growing and pruning algorithm for classification tree design

paper_content:

An efficient iterative method is proposed to grow and prune classification trees. This method divides the data sample into two subsets and iteratively grows a tree with one subset and prunes it with the other subset, successively interchanging the roles of the two subsets. The convergence and other properties of the algorithm are established. Theoretical and practical considerations suggest that the iterative tree growing and pruning algorithm should perform better and require less computation than other widely used tree growing and pruning algorithms. Numerical results on a waveform recognition problem are presented to support this view. >
---
paper_title: A Kolmogorov-Smirnoff Metric for Decision Tree Induction

paper_content:

In 1977, Friedman demonstrated that Kolmogorov-Smirnoff distance could be employed effectively as a test selection metric for decision tree induction. We revisit this metric and modify it to handle multiple classes within a single tree, and to be sensitive to missing data values. Empirical results for a large sample of learning tasks, comparing this metric to the gain ratio metric, show a highly significant reduction in tree size and expected number of tests for classification, without a significant change in classification accuracy.
---
paper_title: A combined nonparametric approach to feature selection and binary decision tree design

paper_content:

Abstract An efficient procedure which integrates feature selection and binary decision tree construction is presented. The nonparametric approach is based on the Kolmogorov-Smirnov criterion which yields an optimal classification decision at each node. By combining the feature selection with the design of the classifier, only the most informative features are retained for classification.
---
paper_title: Block diagrams and splitting criteria for classification trees

paper_content:

Various aspects of the classification tree methodology of Breiman et al., (1984) are discussed. A method of displaying classification trees, called block diagrams, is developed. Block diagrams give a clear presentation of the classification, and are useful both to point out features of the particular data set under consideration and also to highlight deficiencies in the classification method being used. Various splitting criteria are discussed; the usual Gini-Simpson criterion presents difficulties when there is a relatively large number of classes and improved splitting criteria are obtained. One particular improvement is the introduction of ‘adaptive anti-end-cut factors’ that take advantage of highly asymmetrical splits where appropriate. They use the number and mix of classes in the current node of the tree to identify whether or not it is likely to be advantageous to create a very small offspring node. A number of data sets are used as examples.
---
paper_title: Tree classifier design with a permutation statistic

paper_content:

Abstract This paper proposes a permutation statistic as a basis for designing binary tree classifiers of d -dimensional patterns. The statistic permits an objective and easily interpreted evaluation of a (feature, threshold) pair that is the core of the design paradigm. It has a known distribution that is independent of the number of training patterns. After defining the permutation statistic and explaining its properties, the paper proposes the design procedure whereby each non-terminal node is assigned a feature and a threshold on that feature. The design procedure is demonstrated on six test sets and compared to designs based on mutual information.
---
paper_title: An Exact Probability Metric for Decision Tree Splitting and Stopping

paper_content:

ID3‘s information gain heuristic is well-known to be biased towards multi-valued attributes. This bias is only partially compensated for by C4.5‘s gain ratio. Several alternatives have been proposed and are examined here (distance, orthogonality, a Beta function, and two chi-squared tests). All of these metrics are biased towards splits with smaller branches, where low-entropy splits are likely to occur by chance. Both classical and Bayesian statistics lead to the multiple hypergeometric distribution as the exact posterior probability of the null hypothesis that the class distribution is independent of the split. Both gain and the chi-squared tests arise in asymptotic approximations to the hypergeometric, with similar criteria for their admissibility. Previous failures of pre-pruning are traced in large part to coupling these biased approximations with one another or with arbitrary thresholds; problems which are overcome by the hypergeometric. The choice of split-selection metric typically has little effect on accuracy, but can profoundly affect complexity and the effectiveness and efficiency of pruning. Empirical results show that hypergeometric pre-pruning should be done in most cases, as trees pruned in this way are simpler and more efficient, and typically no less accurate than unpruned or post-pruned trees.
---
paper_title: The attribute selection problem in decision tree generation

paper_content:

We address the problem of selecting an attribute and some of its values for branching during the top-down generation of decision trees. We study the class of impurity measures, members of which are typically used in the literature for selecting attributes during decision tree generation (e.g. entropy in ID3, GID3*, and CART; Gini Index in CART). We argue that this class of measures is not particularly suitable for use in classification learning. We define a new class of measures, called C-SEP, that we argue is better suited for the purposes of class separation. A new measure from C-SEP is formulated and some of its desirable properties are shown. Finally, we demonstrate empirically that the new algorithm, O-BTree, that uses this measure indeed produces better decision trees than algorithms that use impurity measures.
---
paper_title: Split Selection Methods for Classification Trees

paper_content:

Classification trees based on exhaustive search algorithms tend to be bi- ased towards selecting variables that afford more splits. As a result, such trees should be interpreted with caution. This article presents an algorithm called QUEST that has negligible bias. Its split selection strategy shares similarities with the FACT method, but it yields binary splits and the final tree can be selected by a direct stopping rule or by pruning. Real and simulated data are used to compare QUEST with the exhaustive search approach. QUEST is shown to be substantially faster and the size and classification accuracy of its trees are typically comparable to those of exhaustive search. A classification tree is a rule for predicting the class of an object from the values of its predictor variables. The tree is constructed by recursively parti- tioning a learning sample of data in which the class label and the values of the predictor variables for each case are known. Each partition is represented by a node in the tree. Two approaches to split selection have been proposed in the statistical liter- ature. The first and more popular approach examines all possible binary splits of the data along each predictor variable to select the split that most reduces some measure of node impurity. It is used, for example, by the THAID (Morgan and Sonquist (1963), Morgan and Messenger (1973)) and CART (Breiman, Friedman, Olshen and Stone (1984)) algorithms. If X is an ordered variable, this approach searches over all possible values c for splits of the form X ≤ c. (1)
---
paper_title: Families of splitting criteria for classification trees

paper_content:

Several splitting criteria for binary classification trees are shown to be written as weighted sums of two values of divergence measures. This weighted sum approach is then used to form two families of splitting criteria. One of them contains the chi-squared and entropy criterion, the other contains the mean posterior improvement criterion. Both family members are shown to have the property of exclusive preference. Furthermore, the optimal splits based on the proposed families are studied. We find that the best splits depend on the parameters in the families. The results reveal interesting differences among various criteria. Examples are given to demonstrate the usefulness of both families.
---
paper_title: Selecting the best splits for classification trees with categorical variables

paper_content:

Based on a family of splitting criteria for classification trees, methods of selecting the best categorical splits are studied. They are shown to be very useful in reducing the computational complexity of the exhaustive search method.
---
paper_title: Design of multicategory multifeature split decision trees using perceptron learning

paper_content:

Abstract The decision tree methodology is an important nonparametric technique for building classifiers from a set of training examples. Most of the existing top-down decision tree design methods make use of single feature splits at successive stages of the tree design. While computationally attractive, single feature splits generally lead to large trees and inferior performance. This paper presents a new top-down decision tree design method that generates compact trees of superior performance by using multifeature splits in place of single feature splits at successive stages of the tree development. The multifeature splits in the proposed method are obtained by combining the concept of information measure of a partition with perceptron learning. Several decision tree induction results for a broad range of classification problems are presented to demonstrate the strengths of the proposed decision tree design methods.
---
paper_title: Multicategory Discrimination via Linear Programming

paper_content:

A single linear program is proposed for discriminating between the elements of κ disjoint point sets in the n-dimensional real space Rn . When the conical hulls of the κ sets are (κ−1)-point disjoint in Rn +1, a κ-piece piecewise-linear surface generated by the linear program completely separates the κ sets. This improves on a previous linear programming approach which required that each set be linearly separable from the remaining κ−1 sets. When the conical hulls of the κ sets are not (κ;−1)-point disjoint, the proposed linear program generates an error-minimizing piecewise-linear separator for the κ Sets. For this case it is shown that the null solution is never a unique solver of the linear program and occurs only under the rather rare condition when the mean of each point set equals the mean of the means of the other κ−l sets. This makes the proposed linear computational programming formulation useful for approximately discriminating between κ sets that are not piecewise-linear separable. Computationa...
---
paper_title: Pattern Classification And Scene Analysis

paper_content:

Provides a unified, comprehensive and up-to-date treatment of both statistical and descriptive methods for pattern recognition. The topics treated include Bayesian decision theory, supervised and unsupervised learning, nonparametric techniques, discriminant analysis, clustering, preprosessing of pictorial data, spatial filtering, shape description techniques, perspective transformations, projective invariants, linguistic procedures, and artificial intelligence techniques for scene analysis.
---
paper_title: Robust Linear Discriminant Trees

paper_content:

We present a new method for the induction of classification trees with linear discriminants as the partitioning function at each internal node. This paper presents two main contributions: first, a novel objective function called soft entropy which is used to identify optimal coefficients for the linear discriminants, and second, a novel method for removing outliers called iterative re-faltering which boosts performance on many datasets. These two ideas are presented in the context of a single learning algorithm called DT-SEPIR, which is compared with the CART and OC1 algorithms.
---
paper_title: A System for Induction of Oblique Decision Trees

paper_content:

This article describes a new system for induction of oblique decision trees. 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. Oblique decision tree methods are tuned especially for domains in which the attributes are numeric, although they can be adapted to symbolic or mixed symbolic/numeric attributes. We present extensive empirical studies, using both real and artificial data, that analyze OC1's ability to construct oblique trees that are smaller and more accurate than their axis-parallel counterparts. We also examine the benefits of randomization for the construction of oblique decision trees.
---
paper_title: A Distance-Based Attribute Selection Measure for Decision Tree Induction

paper_content:

This note introduces a new attribute selection measure for ID3-like inductive algorithms. This measure is based on a distance between partitions such that the selected attribute in a node induces the partition which is closest to the correct partition of the subset of training examples corresponding to this node. The relationship of this measure with Quinlan's information gain is also established. It is also formally proved that our distance is not biased towards attributes with large numbers of values. Experimental studies with this distance confirm previously reported results showing that the predictive accuracy of induced decision trees is not sensitive to the goodness of the attribute selection measure. However, this distance produces smaller trees than the gain ratio measure of Quinlan, especially in the case of data whose attributes have significantly different numbers of values.
---
paper_title: The attribute selection problem in decision tree generation

paper_content:

We address the problem of selecting an attribute and some of its values for branching during the top-down generation of decision trees. We study the class of impurity measures, members of which are typically used in the literature for selecting attributes during decision tree generation (e.g. entropy in ID3, GID3*, and CART; Gini Index in CART). We argue that this class of measures is not particularly suitable for use in classification learning. We define a new class of measures, called C-SEP, that we argue is better suited for the purposes of class separation. A new measure from C-SEP is formulated and some of its desirable properties are shown. Finally, we demonstrate empirically that the new algorithm, O-BTree, that uses this measure indeed produces better decision trees than algorithms that use impurity measures.
---
paper_title: Block diagrams and splitting criteria for classification trees

paper_content:

Various aspects of the classification tree methodology of Breiman et al., (1984) are discussed. A method of displaying classification trees, called block diagrams, is developed. Block diagrams give a clear presentation of the classification, and are useful both to point out features of the particular data set under consideration and also to highlight deficiencies in the classification method being used. Various splitting criteria are discussed; the usual Gini-Simpson criterion presents difficulties when there is a relatively large number of classes and improved splitting criteria are obtained. One particular improvement is the introduction of ‘adaptive anti-end-cut factors’ that take advantage of highly asymmetrical splits where appropriate. They use the number and mix of classes in the current node of the tree to identify whether or not it is likely to be advantageous to create a very small offspring node. A number of data sets are used as examples.
---
paper_title: A combined nonparametric approach to feature selection and binary decision tree design

paper_content:

Abstract An efficient procedure which integrates feature selection and binary decision tree construction is presented. The nonparametric approach is based on the Kolmogorov-Smirnov criterion which yields an optimal classification decision at each node. By combining the feature selection with the design of the classifier, only the most informative features are retained for classification.
---
paper_title: An efficient algorithm for optimal pruning of decision trees

paper_content:

Abstract Pruning decision trees is a useful technique for improving the generalization performance in decision tree induction, and for trading accuracy for simplicity in other applications. In this paper, a new algorithm called OPT-2 for optimal pruning of decision trees is introduced. The algorithm is based on dynamic programming. In its most basic form, the time and space complexities of OPT-2 are both Θ (nC), where n is the number of test nodes in the initial decision tree, and C is the number of leaves in the target (pruned) decision tree. This is an improvement over the recently published OPT algorithm of Bohanec and Bratko (which is the only known algorithm for optimal decision tree pruning) especially in the case of heavy pruning and when the tests of the given decision tree have many outcomes. If so desired, the space required by OPT-2 can further be reduced by a factor of r at the cost of increasing the execution time by a factor that is bounded above by (r + 1) 2 (this is a considerable overestimate, however). From a practical point of view, OPT-2 enjoys considerable flexibility in various aspects, and is easy to implement.
---
paper_title: Trading Accuracy for Simplicity in Decision Trees

paper_content:

When communicating concepts, it is often convenient or even necessary to define a concept approximately. A simple, although only approximately accurate concept definition may be more useful than a completely accurate definition which involves a lot of detail. This paper addresses the problem: given a completely accurate, but complex, definition of a concept, simplify the definition, possibly at the expense of accuracy, so that the simplified definition still corresponds to the concept “sufficiently” well. Concepts are represented by decision trees, and the method of simplification is tree pruning. Given a decision tree that accurately specifies a concept, the problem is to find a smallest pruned tree that still represents the concept within some specified accuracy. A pruning algorithm is presented that finds an optimal solution by generating a dense sequence of pruned trees, decreasing in size, such that each tree has the highest accuracy among all the possible pruned trees of the same size. An efficient implementation of the algorithm, based on dynamic programming, is presented and empirically compared with three progressive pruning algorithms using both artificial and real-world data. An interesting empirical finding is that the real-world data generally allow significantly greater simplification at equal loss of accuracy.
---
paper_title: Inferring Decision Trees Using the Minimum Description Length Principle *

paper_content:

Abstract We explore the use of Rissanen's minimum description length principle for the construction of decision trees. Empirical results comparing this approach to other methods are given.
---
paper_title: An Exact Probability Metric for Decision Tree Splitting and Stopping

paper_content:

ID3‘s information gain heuristic is well-known to be biased towards multi-valued attributes. This bias is only partially compensated for by C4.5‘s gain ratio. Several alternatives have been proposed and are examined here (distance, orthogonality, a Beta function, and two chi-squared tests). All of these metrics are biased towards splits with smaller branches, where low-entropy splits are likely to occur by chance. Both classical and Bayesian statistics lead to the multiple hypergeometric distribution as the exact posterior probability of the null hypothesis that the class distribution is independent of the split. Both gain and the chi-squared tests arise in asymptotic approximations to the hypergeometric, with similar criteria for their admissibility. Previous failures of pre-pruning are traced in large part to coupling these biased approximations with one another or with arbitrary thresholds; problems which are overcome by the hypergeometric. The choice of split-selection metric typically has little effect on accuracy, but can profoundly affect complexity and the effectiveness and efficiency of pruning. Empirical results show that hypergeometric pre-pruning should be done in most cases, as trees pruned in this way are simpler and more efficient, and typically no less accurate than unpruned or post-pruned trees.
---
paper_title: Coding Decision Trees

paper_content:

Quinlan and Rivest have suggested a decision-tree inference method using the Minimum Description Length idea. We show that there is an error in their derivation of message lengths, which fortunately has no effect on the final inference. We further suggest two improvements to their coding techniques, one removing an inefficiency in the description of non-binary trees, and one improving the coding of leaves. We argue that these improvements are superior to similarly motivated proposals in the original paper. ::: ::: Empirical tests confirm the good results reported by Quinlan and Rivest, and show our coding proposals to lead to useful improvements in the performance of the method.
---
paper_title: An Empirical Comparison of Pruning Methods for Decision Tree Induction

paper_content:

This paper compares five methods for pruning decision trees, developed from sets of examples. When used with uncertain rather than deterministic data, decision-tree induction involves three main stages—creating a complete tree able to classify all the training examples, pruning this tree to give statistical reliability, and processing the pruned tree to improve understandability. This paper concerns the second stage—pruning. It presents empirical comparisons of the five methods across several domains. The results show that three methods—critical value, error complexity and reduced error—perform well, while the other two may cause problems. They also show that there is no significant interaction between the creation and pruning methods.
---
paper_title: An Empirical Comparison of Pruning Methods for Decision Tree Induction

paper_content:

This paper compares five methods for pruning decision trees, developed from sets of examples. When used with uncertain rather than deterministic data, decision-tree induction involves three main stages—creating a complete tree able to classify all the training examples, pruning this tree to give statistical reliability, and processing the pruned tree to improve understandability. This paper concerns the second stage—pruning. It presents empirical comparisons of the five methods across several domains. The results show that three methods—critical value, error complexity and reduced error—perform well, while the other two may cause problems. They also show that there is no significant interaction between the creation and pruning methods.
---
paper_title: Unknown Attribute Values In Induction

paper_content:

Simple techniques for the development and use of decision tree classifiers assume that all attribute values of all cases are available. Numerous approaches have been proposed with the aim of extending these techniques to cover real-world situations in which unknown attribute values are not uncommon. This paper compares the effectiveness of several approaches as measured by their performance on a collection of datasets.
---
paper_title: Split Selection Methods for Classification Trees

paper_content:

Classification trees based on exhaustive search algorithms tend to be bi- ased towards selecting variables that afford more splits. As a result, such trees should be interpreted with caution. This article presents an algorithm called QUEST that has negligible bias. Its split selection strategy shares similarities with the FACT method, but it yields binary splits and the final tree can be selected by a direct stopping rule or by pruning. Real and simulated data are used to compare QUEST with the exhaustive search approach. QUEST is shown to be substantially faster and the size and classification accuracy of its trees are typically comparable to those of exhaustive search. A classification tree is a rule for predicting the class of an object from the values of its predictor variables. The tree is constructed by recursively parti- tioning a learning sample of data in which the class label and the values of the predictor variables for each case are known. Each partition is represented by a node in the tree. Two approaches to split selection have been proposed in the statistical liter- ature. The first and more popular approach examines all possible binary splits of the data along each predictor variable to select the split that most reduces some measure of node impurity. It is used, for example, by the THAID (Morgan and Sonquist (1963), Morgan and Messenger (1973)) and CART (Breiman, Friedman, Olshen and Stone (1984)) algorithms. If X is an ordered variable, this approach searches over all possible values c for splits of the form X ≤ c. (1)
---
paper_title: Induction of decision trees

paper_content:

The technology for building knowledge-based systems by inductive inference from examples has been demonstrated successfully in several practical applications. 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. Results from recent studies show ways in which the methodology can be modified to deal with information that is noisy and/or incomplete. A reported shortcoming of the basic algorithm is discussed and two means of overcoming it are compared. The paper concludes with illustrations of current research directions.
---
paper_title: An Exploratory Technique for Investigating Large Quantities of Categorical Data

paper_content:

SUMMARY The technique set out in the paper, CHAID, is an offshoot of AID (Automatic Interaction Detection) designed for a categorized dependent variable. Some important modifications which are relevant to standard AID include: built-in significance testing with the consequence of using the most significant predictor (rather than the most explanatory), multi-way splits (in contrast to binary) and a new type of predictor which is especially useful in handling missing information.
---
paper_title: Boolean feature discovery in empirical learning

paper_content:

We investigate the problem of learning Boolean functions with a short DNF representation using decision trees as a concept description language. Unfortunately, Boolean concepts with a short description may not have a small decision tree representation when the tests at the nodes are limited to the primitive attributes. This representational shortcoming may be overcome by using Boolean features at the decision nodes. We present two new methods that adaptively introduce relevant features while learning a decision tree from examples. We show empirically that these methods outperform a standard decision tree algorithm for learning small random DNF functions when the examples are drawn at random from the uniform distribution.
---
paper_title: A Comparison of Prediction Accuracy, Complexity, and Training Time of Thirty-Three Old and New Classification Algorithms

paper_content:

Twenty-two decision tree, nine statistical, and two neural network algorithms are compared on thirty-two datasets in terms of classification accuracy, training time, and (in the case of trees) number of leaves. Classification accuracy is measured by mean error rate and mean rank of error rate. Both criteria place a statistical, spline-based, algorithm called POLYCLSSS at the top, although it is not statistically significantly different from twenty other algorithms. Another statistical algorithm, logistic regression, is second with respect to the two accuracy criteria. The most accurate decision tree algorithm is QUEST with linear splits, which ranks fourth and fifth, respectively. Although spline-based statistical algorithms tend to have good accuracy, they also require relatively long training times. POLYCLASS, for example, is third last in terms of median training time. It often requires hours of training compared to seconds for other algorithms. The QUEST and logistic regression algorithms are substantially faster. Among decision tree algorithms with univariate splits, C4.5, IND-CART, and QUEST have the best combinations of error rate and speed. But C4.5 tends to produce trees with twice as many leaves as those from IND-CART and QUEST.
---
paper_title: Split Selection Methods for Classification Trees

paper_content:

Classification trees based on exhaustive search algorithms tend to be bi- ased towards selecting variables that afford more splits. As a result, such trees should be interpreted with caution. This article presents an algorithm called QUEST that has negligible bias. Its split selection strategy shares similarities with the FACT method, but it yields binary splits and the final tree can be selected by a direct stopping rule or by pruning. Real and simulated data are used to compare QUEST with the exhaustive search approach. QUEST is shown to be substantially faster and the size and classification accuracy of its trees are typically comparable to those of exhaustive search. A classification tree is a rule for predicting the class of an object from the values of its predictor variables. The tree is constructed by recursively parti- tioning a learning sample of data in which the class label and the values of the predictor variables for each case are known. Each partition is represented by a node in the tree. Two approaches to split selection have been proposed in the statistical liter- ature. The first and more popular approach examines all possible binary splits of the data along each predictor variable to select the split that most reduces some measure of node impurity. It is used, for example, by the THAID (Morgan and Sonquist (1963), Morgan and Messenger (1973)) and CART (Breiman, Friedman, Olshen and Stone (1984)) algorithms. If X is an ordered variable, this approach searches over all possible values c for splits of the form X ≤ c. (1)
---
paper_title: Oblivious Decision Trees and Abstract Cases

paper_content:

Abstract : In this paper, we address the problem of case-based learning in the presence of irrelevant features. We review previous work on attribute selection and present a new algorithm, OBLIVION, that carries out greedy pruning of oblivious decision trees, which effectively store a set of abstract cases in memory. We hypothesize that this approach will efficiently identify relevant features even when they interact, as in parity concepts. We report experimental results on artificial domains that support this hypothesis, and experiments with natural domains that show improvement in some cases but not others. In closing, we discuss the implications of our experiments, consider additional work on irrelevant features, and outline some directions for future research.
---
paper_title: Learning Boolean Concepts in the Presence of Many Irrelevant Features

paper_content:

Abstract In many domains, an appropriate inductive bias is the MIN-FEATURES bias, which prefers consistent hypotheses definable over as few features as possible. This paper defines and studies this bias in Boolean domains. First, it is shown that any learning algorithm implementing the MIN-FEATURES bias requires ⊖(( ln ( l δ ) + [2 p + p ln n])/e) training examples to guarantee PAC-learning a concept having p relevant features out of n available features. This bound is only logarithmic in the number of irrelevant features. For implementing the MIN-FEATURES bias, the paper presents five algorithms that identify a subset of features sufficient to construct a hypothesis consistent with the training examples. FOCUS-1 is a straightforward algorithm that returns a minimal and sufficient subset of features in quasi-polynomial time. FOCUS-2 does the same task as FOCUS-1 but is empirically shown to be substantially faster than FOCUS-1. Finally, the Simple-Greedy, Mutual-Information-Greedy and Weighted-Greedy algorithms are three greedy heuristics that trade optimality for computational efficiency. Experimental studies are presented that compare these exact and approximate algorithms to two well-known algorithms, ID3 and FRINGE, in learning situations where many irrelevant features are present. These experiments show that—contrary to expectations—the ID3 and FRINGE algorithms do not implement good approximations of MIN-FEATURES. The sample complexity and generalization performance of the FOCUS algorithms is substantially better than either ID3 or FRINGE on learning problems where the MIN-FEATURES bias is appropriate. These experiments also show that, among our three heuristics, the Weighted-Greedy algorithm provides an excellent approximation to the FOCUS algorithms.
---
paper_title: Efficiently Inducing Determinations: A Complete and Systematic Search Algorithm that Uses Optimal Pruning

paper_content:

Determinations are a useful type of functional knowledge representation. Applications include knowledge-based systems, analogical reasoning, database design, and robotic sensing systems. This paper presents an efficient, batch algorithm for inducing all minimal determinations from observed data. The algorithm is based on breadth-first search and runs in polynomial time and space given a user-supplied parameter limiting the maximum size of a determination. The algorithm uses probabilistic measures to induce determinations despite noisy data. One key contribution is the identification of an enumeration order in the space of possible determinations that affords a complete and systematic search. Another contribution lists axioms that relate neighboring states and allow the construction of pruning rules. A third contribution formulates a perfect hash function for states in this space and facilitates optimal use of the pruning rules. This paper also sketches an algorithm that can incrementally revise a set of determinations given additional data.
---
paper_title: Targeting Business Users with Decision Table Classifiers

paper_content:

Business users and analysts commonly use spreadsheets and 2D plots to analyze and understand their data. On-line Analytical Processing (OLAP) provides these users with added flexibility in pivoting data around different attributes and drilling up and down the multi-dimensional cube of aggregations. Machine learning researchers, however, have concentrated on hypothesis spaces that are foreign to most users: hyper-planes (Perceptrons), neural networks, Bayesian networks, decision trees, nearest neighbors, etc. In this paper we advocate the use of decision table classifiers that are easy for line-of-business users to understand. We describe several variants of algorithms for learning decision tables, compare their performance, and describe a visualization mechanism that we have implemented in MineSet. The performance of decision tables is comparable to other known algorithms, such as C4.5/C5.0, yet the resulting classifiers use fewer attributes and are more comprehensible.
---
paper_title: Improving Stability of Decision Trees

paper_content:

Decision-tree algorithms are known to be unstable: small variations in the training set can result in different trees and different predictions for the same validation examples. Both accuracy and stability can be improved by learning multiple models from bootstrap samples of training data, but the "meta-learner" approach makes the extracted knowledge hardly interpretable. In the following paper, we present the Info-Fuzzy Network (IFN), a novel information-theoretic method for building stable and comprehensible decision-tree models. The stability of the IFN algorithm is ensured by restricting the tree structure to using the same feature for all nodes of the same tree level and by the built-in statistical significance tests. The IFN method is shown empirically to produce more compact and stable models than the "meta-learner" techniques, while preserving a reasonable level of predictive accuracy.
---
paper_title: RainForest—A Framework for Fast Decision Tree Construction of Large Datasets

paper_content:

Classification of large datasets is an important data mining problem. Many classification algorithms have been proposed in the literature, but studies have shown that so far no algorithm uniformly outperforms all other algorithms in terms of quality. In this paper, we present a unifying framework called Rain Forest for classification tree construction that separates the scalability aspects of algorithms for constructing a tree from the central features that determine the quality of the tree. The generic algorithm is easy to instantiate with specific split selection methods from the literature (including C4.5, CART, CHAID, FACT, ID3 and extensions, SLIQ, SPRINT and QUEST). ::: ::: In addition to its generality, in that it yields scalable versions of a wide range of classification algorithms, our approach also offers performance improvements of over a factor of three over the SPRINT algorithm, the fastest scalable classification algorithm proposed previously. In contrast to SPRINT, however, our generic algorithm requires a certain minimum amount of main memory, proportional to the set of distinct values in a column of the input relation. Given current main memory costs, this requirement is readily met in most if not all workloads.
---
paper_title: BOAT—optimistic decision tree construction

paper_content:

Classification is an important data mining problem. Given a training database of records, each tagged with a class label, the goal of classification is to build a concise model that can be used to predict the class label of future, unlabeled records. A very popular class of classifiers are decision trees. All current algorithms to construct decision trees, including all main-memory algorithms, make one scan over the training database per level of the tree. We introduce a new algorithm (BOAT) for decision tree construction that improves upon earlier algorithms in both performance and functionality. BOAT constructs several levels of the tree in only two scans over the training database, resulting in an average performance gain of 300% over previous work. The key to this performance improvement is a novel optimistic approach to tree construction in which we construct an initial tree using a small subset of the data and refine it to arrive at the final tree. We guarantee that any difference with respect to the “real” tree (i.e., the tree that would be constructed by examining all the data in a traditional way) is detected and corrected. The correction step occasionally requires us to make additional scans over subsets of the data; typically, this situation rarely arises, and can be addressed with little added cost. Beyond offering faster tree construction, BOAT is the first scalable algorithm with the ability to incrementally update the tree with respect to both insertions and deletions over the dataset. This property is valuable in dynamic environments such as data warehouses, in which the training dataset changes over time. The BOAT update operation is much cheaper than completely rebuilding the tree, and the resulting tree is guaranteed to be identical to the tree that would be produced by a complete re-build.
---
paper_title: On the Accuracy of Meta-learning for Scalable Data Mining

paper_content:

In this paper, we describe a general approach to scaling data mining applications that we have come to call meta-learning. Meta-Learning refers to a general strategy that seeks to learn how to combine a number of separate learning processes in an intelligent fashion. We desire a meta-learning architecture that exhibits two key behaviors. First, the meta-learning strategy must produce an accurate final classification system. This means that a meta-learning architecture must produce a final outcome that is at least as accurate as a conventional learning algorithm applied to all available data. Second, it must be fast, relative to an individual sequential learning algorithm when applied to massive databases of examples, and operate in a reasonable amount of time. This paper focussed primarily on issues related to the accuracy and efficacy of meta-learning as a general strategy. A number of empirical results are presented demonstrating that meta-learning is technically feasible in wide-area, network computing environments.
---
paper_title: SLIQ: A fast scalable classifier for data mining

paper_content:

Classification is an important problem in the emerging field of data mining. Although classification has been studied extensively in the past, most of the classification algorithms are designed only for memory-resident data, thus limiting their suitability for data mining large data sets. This paper discusses issues in building a scalable classifier and presents the design of SLIQ, a new classifier. SLIQ is a decision tree classifier that can handle both numeric and categorical attributes. It uses a novel pre-sorting technique in the tree-growth phase. This sorting procedure is integrated with a breadth-first tree growing strategy to enable classification of disk-resident datasets. SLIQ also uses a new tree-pruning algorithm that is inexpensive, and results in compact and accurate trees. The combination of these techniques enables SLIQ to scale for large data sets and classify data sets irrespective of the number of classes, attributes, and examples (records), thus making it an attractive tool for data mining.
---
paper_title: SPRINT: A Scalable Parallel Classifier for Data Mining

paper_content:

Classification is an important data mining problem. Although classification is a wellstudied problem, most of the current classification algorithms require that all or a portion of the the entire dataset remain permanently in memory. This limits their suitability for mining over large databases. We present a new decision-tree-based classification algorithm, called SPRINT that removes all of the memory restrictions, and is fast and scalable. The algorithm has also been designed to be easily parallelized, allowing many processors to work together to build a single consistent model. This parallelization, also presented here, exhibits excellent scalability as well. The combination of these characteristics makes the proposed algorithm an ideal tool for data mining.
---
paper_title: CLOUDS: A Decision Tree Classifier for Large Datasets

paper_content:

Classification for very large datasets has many practical applications in data mining. Techniques such as discretization and dataset sampling can be used to scale up decision tree classifiers to large datasets. Unfortunately, both of these techniques can cause a significant loss in accuracy. We present a novel decision tree classifier called CLOUDS, which samples the splitting points for numeric attributes followed by an estimation step to narrow the search space of the best split. CLOUDS reduces computation and I/O complexity substantially compared to state of the art classifiers, while maintaining the quality of the generated trees in terms of accuracy and tree size. We provide experimental results with a number of real and synthetic datasets.
---
paper_title: Extensions to the CART algorithm

paper_content:

Abstract The CART concept induction algorithm recursively partitions the measurement space, displaying the resulting partitions as decision trees. Care, however, must be taken not to overfit the trees to the data, and CART employs cross-validation (cv) as the means by which an appropriately sized tree is selected. Although unbiased, cv estimates exhibit high variance, a troublesome characteristic, particularly for small learning sets. This paper describes Monte Carlo experiments which illustrate the effectiveness of the ·632 bootstrap as an alternative technique for tree selection and error estimation. In addition, a new incremental learning extension to CART is described.
---
paper_title: Decision Tree Induction Based on Efficient Tree Restructuring

paper_content:

The ability to restructure a decision tree efficiently enables a variety of approaches to decision tree induction that would otherwise be prohibitively expensive. Two such approaches are described here, one being incremental tree induction (ITI), and the other being non-incremental tree induction using a measure of tree quality instead of test quality (DMTI). These approaches and several variants offer new computational and classifier characteristics that lend themselves to particular applications.
---

Title: Top-down induction of decision tree classifiers - a survey

Section 1: PRELIMINARIES
Description 1: Describe the basics of supervised learning, the structure of training sets, and the notation used throughout the paper.

Section 2: DECISION TREE REPRESENTATION
Description 2: Explain what decision trees are, how they are structured, and how they function as classifiers, including complexities and their transformation into rule sets.

Section 3: ALGORITHMIC FRAMEWORK FOR DECISION TREES
Description 3: Introduce decision tree algorithms and their goal, focusing on the general approach of top-down inducers and their greedy nature.

Section 4: Impurity Based Criteria
Description 4: Discuss impurity-based criteria for splitting nodes, which include information gain, Gini index, and likelihood ratio chi-squared statistics.

Section 5: Normalized Impurity Based Criteria
Description 5: Explore criteria that address the bias of impurity-based measures towards attributes with many values, such as gain ratio and distance measures.

Section 6: Binary Criteria
Description 6: Delve into criteria used for creating binary decision trees, including twoing criteria, orthogonality criterion, and Kolmogorov-Smirnov criteria.

Section 7: MULTIVARIATE SPLITTING CRITERIA
Description 7: Discuss criteria involving multiple attributes for splitting, the complexity involved, and various methods such as linear programming and linear discriminant analysis.

Section 8: STOPPING CRITERIA
Description 8: Explain the various conditions under which the growing phase of decision tree induction is halted.

Section 9: Pruning Methods
Description 9: Present different methods for pruning decision trees to improve generalization, including cost-complexity pruning, reduced-error pruning, and error-based pruning.

Section 10: OTHER ISSUES IN DECISION TREE INDUCTION
Description 10: Address additional considerations in decision tree induction, such as weighting instances, handling misclassification costs, and dealing with missing values.

Section 11: Overview of Specific Algorithms
Description 11: Provide an overview of several specific decision tree algorithms like ID3, C4.5, CART, and others, enumerating their unique characteristics and differences.

Section 12: Decision Trees Inducers for Large Datasets
Description 12: Discuss algorithms designed to handle large datasets, their methods for reducing computational complexity, and specific strategies to manage large data volumes.

Section 13: Incremental Induction
Description 13: Explore methods for updating decision trees incrementally to reflect new data without rebuilding the entire tree from scratch.

Section 14: CONCLUSION
Description 14: Summarize the survey, encompassing the main points regarding top-down decision tree induction algorithms, their frameworks, and variations.