A Fast Decision Tree Learning Algorithm

Jiang Su, Harry ZhangAAAI 2006

Introduction

Decision trees are a cornerstone of machine learning, valued for their interpretability, lack of required parameter tuning, and ability to handle heterogeneous data types. However, the standard induction algorithm, C4.5, faces a significant scaling challenge in the era of Big Data. Its time complexity is quadratic relative to the number of attributes ($n$), specifically $O(m \cdot n^2)$ where $m$ is the number of instances. This quadratic scaling creates a massive bottleneck for high-dimensional datasets, such as those found in text classification or genomics.

The Naive Tree (NT) Algorithm

To overcome this limitation, Su and Zhang introduce the Naive Tree (NT) algorithm. The core innovation is a new heuristic called Independent Information Gain (IIG), which leverages a conditional independence assumption to streamline attribute selection.

In a standard decision tree, the algorithm must scan the current subset of data for every candidate attribute at every node to calculate Information Gain (IG). NT changes this by assuming that candidate attributes are independent of the attributes already chosen for the current path, given the class label. This allows for a more efficient two-step process:

  1. Pre-computation: Before tree construction begins, the algorithm calculates the global probability of each attribute value given the class ($P(X|C)$) in a single $O(m \cdot n)$ pass.
  2. Heuristic Estimation: During tree growth, instead of re-scanning the data to find the local distribution of a candidate attribute, NT uses the pre-computed global probabilities to estimate the information gain.

This shift allows the algorithm to evaluate all attributes at a given level by passing through the data only once, resulting in a total time complexity of $O(m \cdot n)$, comparable to the efficiency of Naive Bayes.

Experimental Evaluation

The researchers benchmarked the Naive Tree algorithm against C4.5 and Naive Bayes (NB) using two distinct experimental setups: 33 UCI benchmark datasets for general performance and 19 high-dimensional text classification datasets for stress testing efficiency.

Performance on Standard Benchmarks

On the UCI datasets, NT demonstrated that its efficiency does not come at the cost of accuracy. The algorithm maintained predictive performance nearly identical to the "gold standard" C4.5. As shown in the results below, the mean accuracy for NT across these 33 diverse problems was 83.37%, compared to 83.57% for C4.5.

Table 1: Experimental results on 33 UCI datasets comparing accuracy (%) of NT, C4.5, and NB.

Efficiency in High-Dimensional Tasks

The true power of the NT algorithm is most evident in text classification, where datasets often feature thousands of attributes. In these scenarios, NT achieved a remarkable 30x speedup over C4.5. On average, NT required only 93 seconds to train, while C4.5 took 2,823 seconds. Furthermore, NT actually outperformed C4.5 in terms of accuracy on these tasks (79.88% vs 78.00%).

Table 2: Experimental results on 19 text datasets, showing accuracy (%) and training time (T) in seconds.

Key Insights and Discussion

The success of NT is rooted in several critical observations:

  • Context-Specific Independence: Unlike Naive Bayes, which assumes global independence, NT assumes independence relative to the current path in the tree. This "weaker" and more realistic assumption allows NT to capture more complex relationships than a simple Naive Bayes model.
  • Ranking vs. Accuracy: The authors emphasize that for a decision tree to be effective, the heuristic only needs to correctly rank the attributes. As long as the "best" attribute identified by IIG matches the one identified by standard IG, the resulting tree structure remains optimal.
  • Mitigating Fragmentation: Standard trees often suffer from "fragmentation," where data subsets at deeper nodes become too small for reliable local statistics. By using global statistics ($P(X|C)$) calculated from the entire dataset, NT’s estimates can remain stable even at the lower levels of the tree.

Conclusion and Future Work

The Naive Tree algorithm represents a significant step forward in making decision trees scalable for modern, high-dimensional datasets. By reducing complexity to $O(m \cdot n)$, it offers a practical solution for large-scale learning without sacrificing the interpretability that makes trees so popular. Future research will focus on refining the algorithm's handling of missing values and further optimizing its performance for continuous numeric attributes.

Summary updated

BibTeX
@inproceedings{su2006fast,
  author = {Jiang Su and Harry Zhang},
  title = {{A Fast Decision Tree Learning Algorithm}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure