TL;DR
This paper introduces OC1, a novel algorithm for building oblique decision trees. OC1 combines deterministic hill-climbing with randomization to efficiently search for optimal hyperplane splits, resulting in smaller and more accurate trees than traditional axis-parallel methods.
What Problem Does This Paper Address?
Decision trees are a popular machine learning tool for classification. Traditional decision tree algorithms, like ID3 and CART, use "axis-parallel" splits, meaning they test a single feature against a threshold (e.g., "is age > 30?"). While effective, these trees can become very large and complex, especially for datasets where classes are not easily separated by single features.
This paper tackles the challenge of inducing "oblique" decision trees. Oblique trees use linear combinations of features to define their splits, essentially creating "slanted" hyperplanes to partition the data. This allows for more compact and potentially more accurate trees, as they can capture more complex relationships. However, finding the optimal oblique hyperplane is computationally intractable (NP-Complete). Therefore, the paper addresses the need for efficient, yet effective, heuristic methods to induce these oblique trees.
Methods
OC1, the algorithm introduced, builds oblique decision trees by iteratively finding the best hyperplane to split the data at each node. The core of OC1's innovation lies in its hybrid search strategy:
- Deterministic Hill-Climbing: OC1 starts with a randomly chosen initial hyperplane. It then iteratively perturbs the coefficients of this hyperplane, one at a time, to find a split that minimizes an impurity measure (like information gain). This is a greedy, local search approach.
- Randomization for Escaping Local Minima: A key challenge in optimization is getting stuck in "local minima" – good splits, but not the best possible. OC1 addresses this by:
- Random Initial Hyperplanes: The process begins with a random hyperplane, increasing the chance of exploring different parts of the search space.
- Random Direction Perturbation: If the deterministic search reaches a local minimum, OC1 can perturb the entire hyperplane in a random direction. This allows it to "jump" out of local optima.
- Multiple Iterations: The algorithm can be run multiple times with different random initial hyperplanes, saving the best tree found across all runs.
The paper also discusses different strategies for perturbing coefficients (Seq, Best, R-50) and various impurity measures, noting that the choice of impurity measure has less impact than other parameters.
Datasets
The paper evaluates OC1 on four real-world datasets:
- Star/Galaxy Discrimination (Bright and Dim): Astronomical images characterized by 14 real-valued attributes. The "dim" set is noted as being more difficult.
- Iris Dataset: A classic benchmark with 150 examples described by four numerical attributes, belonging to three different categories.
- Breast Cancer Diagnosis: A dataset of 470 patients with nine numeric attributes, used for classifying benign vs. malignant tumors.
The paper compares OC1's performance against existing methods like CSADT (an oblique tree method using simulated annealing), ID3 (a standard axis-parallel tree algorithm), 1-Nearest Neighbor (1-NN), and Back Propagation (BP) networks.
Key Insights and Ideas
- Randomization is Crucial for Oblique Trees: The paper strongly suggests that randomization is not just a way to speed up search but is essential for escaping local minima and finding better oblique splits, leading to improved accuracy and tree size.
- Oblique Trees Offer Significant Advantages: OC1 consistently produces much smaller trees than comparable methods using univariate tests, making them more interpretable. The accuracy of these smaller trees matches or exceeds other advanced methods.
- Hybrid Search is Effective: Combining deterministic hill-climbing with randomized jumps out of local minima provides a powerful and efficient search strategy for oblique hyperplanes.
- Multiple Iterations Pay Off: Running the OC1 algorithm with multiple random initial hyperplanes significantly improves the quality of the resulting tree.
Key Results
- OC1 consistently finds smaller and more accurate decision trees compared to traditional axis-parallel methods.
- On the Star/Galaxy (Bright) dataset, OC1 achieved 99.2% accuracy with a tree size of 15.6, outperforming CSADT (99.1% accuracy, 18.4 size) and ID3 (99.1% accuracy, 44.3 size).
- For the Iris dataset, OC1 achieved 98.0% accuracy with a tree size of 3.0, significantly smaller than CSADT (94.7% accuracy, 4.2 size) and ID3 (94.7% accuracy, 10.0 size).
- The paper demonstrates that using multiple iterations (e.g., 50 or more) leads to better trees, with accuracy increasing up to a certain point and then leveling off.
- The choice of impurity measure had less impact than other parameters, and no specific order of coefficient perturbation was uniformly superior.
Limitations and Future Work
- Parameter Tuning: The authors acknowledge that determining the optimal program parameters (number of iterations, best impurity measure, order of perturbation) for a given dataset is a future research direction. They suggest using the training set to learn these parameters.
- Theoretical Bound vs. Practice: While a theoretical bound for hyperplane perturbation is O(dn² log n), in practice, hyperplanes were rarely perturbed more than a small number of times, suggesting an expected running time closer to O(kn log n) where k is a small constant.
- Further Exploration of Oblique Trees: The paper concludes by advocating for the use of oblique decision trees, suggesting they should be used in conjunction with other methods to enhance classification tools.
Summary updated