CART-ELC: Oblique Decision Tree Induction via Exhaustive Search

Andrew D. Laack [email protected] · 2025

Read CART-ELC: Oblique Decision Tree Induction via Exhaustive Search by Andrew D. Laack [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-05402.txt.

Introduction

Andrew Laack introduces a decision tree algorithm in a 2025 paper that splits data along slanted lines. Standard trees split on one feature at a time, which can force deep, tangled trees. Slanted splits can fit patterns better, but searching all options is costly, so the idea has seen little use.

His method searches a limited set of slanted splits in full at each node. Laack studies the cost of the search and tests accuracy on small data sets. The method matched or beat known tree builders, often with clear gains, while growing shallower and simpler trees. Such trees are easier for people to read, which matters in fields that must explain each call.

Catalog record

CREATORAndrew D. Laack [email protected]
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE37 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-05402

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

CART-ELC: Oblique Decision Tree Induction via Exhaustive Search Andrew D. Laack [email protected] Abstract Oblique decision trees have attracted attention due to their potential for improved classification performance over traditional axis-aligned decision trees. However, methods that rely on exhaustive search to find oblique splits face computational challenges. As a result, they have not been widely explored. We introduce a novel algorithm, Classification and Regression Tree - Exhaustive Linear Combinations (CART-ELC), for inducing oblique decision trees that performs an exhaustive search on a restricted set of hyperplanes. We then investigate the algorithm’s computational complexity and its predictive capabilities. Our results demonstrate that CART-ELC consistently achieves competitive performance on small datasets, often yielding statistically significant improvements in classification accuracy relative to existing decision tree induction algorithms, while frequently producing shallower, simpler, and thus more interpretable trees. 1 Introduction Decision tree induction algorithms are among the most widely used algorithms for training interpretable machine learning models. This interpretability is one of the reasons they are often preferred over other models with better predictive capabilities ( Mienye & Jere, 2024 ; Drucker & Cortes, 1995 ) . While there has been much research on axis-aligned decision trees ( Kotsiantis, 2011 ; Breiman et al., 1984 ; Mienye & Jere, 2024 ) , research on oblique decision trees has been less extensive ( Wickramarachchi et al., 2016 ; Murthy et al., 1994 ; Breiman et al., 1984 ) . Where traditional decision trees use axis-aligned splits to partition the feature space, oblique decision trees use linear combinations of features that are not restricted to axis-alignment. This allows oblique decision trees to be stronger learners with shallower trees while still being fairly interpretable ( Murthy et al., 1994 ) . However, this increased flexibility results in a larger search space as the number of hyperplanes that uniquely partition a dataset when considering the relative positions of samples with respect to the hyperplane is at most 2^{m}\cdot\binom{n}{m} , where m is the dimensionality of the feature space and n is the number of samples ( Murthy et al., 1994 ) . 1.1 Related Works 1.1.1 CART The Classification and Regression Tree (CART) algorithm ( Breiman et al., 1984 ) induces axis-aligned decision trees by recursively partitioning the dataset. At each step, it evaluates a set of candidate axis-aligned splits, selects the best one, and partitions the dataset using this split. These steps are then performed recursively for each partition until a stopping criterion is met. 1.1.2 CART-LC The Classification and Regression Tree - Linear Combinations (CART-LC) algorithm ( Breiman et al., 1984 ) is a deterministic hill climbing algorithm for inducing oblique decision trees. The algorithm starts by median-centering the features and dividing them by their interquartile range. It then identifies the best axis-aligned split and iteratively adjusts the coefficients of the corresponding hyperplane to improve the split. Once improvements fall below a threshold, the algorithm converts the refined split from the transformed feature space to the original feature space, and uses this split to partition the dataset. This process is then applied recursively for each partition until a stopping criterion is met. 1.1.3 OC1 The Oblique Classifier 1 (OC1) algorithm ( Murthy et al., 1994 ) is a stochastic hill climbing algorithm for inducing oblique decision trees. It begins by initializing a random hyperplane and deterministically perturbs the hyperplane’s coefficients to improve its splitting score. If no improvements can be made, a new hyperplane is created by adding random values to the coefficients in an attempt to escape the local optimum. The new hyperplane is then evaluated against the previous one. If the new score is better, the process repeats, starting with this new hyperplane as the initial hyperplane. If it is not better, another random hyperplane is initialized, and the entire procedure starts again. This process of applying perturbations and then attempting to escape local optima is applied z times, where z is a hyperparameter of the algorithm. After z iterations, the split with the best splitting score is then used to partition the dataset. The algorithm then recursively applies the above procedure to each partition until a stopping criterion is met. 1.1.4 HHCART The Householder Classification and Regression Tree (HHCART) algorithm ( Wickramarachchi et al., 2016 ) induces oblique decision trees by leveraging class-specific orientation. HHCART(D), a variant of the algorithm, computes the dominant eigenvector of the covariance matrix for each class. Each of these dominant eigenvectors is then individually used to perform a Householder transformation to align the corresponding class orientation with a coordinate axis. In the resulting feature space, the algorithm searches for the best axis-aligned split, which is then mapped back to the original feature space as an oblique split. The best oblique split found after evaluating each dominant eigenvector is used to partition the dataset. This process is then applied to each of the resulting partitions until a stopping criterion is met. Wickramarachchi et al. (2016) defined two variants of HHCART: HHCART(D), which only uses the dominant eigenvector for each class, and HHCART(A), which uses all eigenvectors for each class. 1.2 Limitations A limitation of the CART algorithm is that it only considers axis-aligned splits. These splits can be suboptimal when the data is linearly separable, as described by Breiman et al. (1984) . Algorithms like CART-LC and OC1 are not constrained to axis-aligned splits, but they often converge to local optima due to their hill climbing nature. While OC1 attempts to escape local optima by adding random values to the coefficients of the splitting hyperplane after its improvements have stagnated, this strategy does not guarantee escaping local optima. HHCART is not limited in either of these regards, but it does only test splits that are axis-aligned in specific transformed feature spaces. This subset of oblique splits can be overly limited in cases where it is computationally feasible to evaluate more oblique splits. Additionally, while CART-LC, OC1, and HHCART can generate shallower trees relative to CART ( Murthy et al., 1994 ) , the resulting trees often use splits that are linear combinations of many features. This results in oblique trees that can be difficult to interpret, and more costly to perform predictions with. 2 CART-ELC 2.1 Description We introduce CART-ELC to address the limitations described in subsection 1.2 . CART-ELC has one hyperparameter, r , defining both the minimum number of samples each candidate hyperplane must pass through and the maximum number of non-zero coefficients the hyperplane’s normal vector can have. We define m as the dimensionality of the feature space. With these definitions, we now discuss the two cases for the algorithm. Case 1: \mathbf{r=m} In the general case for r=m , CART-ELC performs an exhaustive search of all unique hyperplanes that pass through at least r samples. This is done by evaluating each hyperplane according to a splitting criterion, tracking the best splitting hyperplane, and after all hyperplanes have been evaluated, the algorithm partitions the dataset using the best split. This process is then recursively applied to both partitions, stopping when a stopping criterion is met. The general case for r=m is when each selection of r samples uniquely identifies a hyperplane. In such cases, this process guarantees the greedily optimal hyperplane passing through at least r samples

Read the complete text