A System for Induction of Oblique Decision Trees

By Sreerama K. Murthy, Simon Kasif, Steven L. Salzberg. 1994

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.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Making Tree Ensembles Interpretable (2016, methodology): “These modifications can also be extended to oblique decision trees (Murthy et al., 1994).”
The Random Subspace Method for Constructing Decision Forests (1998, background): “…and Sarvarayudu's average mutual information [28], the Gini index proposed by Breiman et al. [3], Quinlan's information gain ratio [25], or Mingers's G statistic [20], [21], etc. Oblique hyperplanes can be obtained by Tomek links [23], simulated annealing [7], [8], or perceptron training [11].”
Optimal randomized classification trees (2021, methodology): “There are different algorithms that implement oblique cuts, such as OC1 [38] and oblique.tree [39].”
Budding Trees (2014, background): “The multivariate tree [4], [5] is a generalization where we define gm(x) = w Tx hence defining arbitrary oblique splits.”
Interpretable Rule Discovery Through Bilevel Optimization of Split-Rules of Nonlinear Decision Trees for Classification Problems (2020, background): “The work done in the past to generate non-axis-parallel trees can be found in [5], [6], [7], where the researchers rely on randomized algorithms to search for multi-variate hyperplanes.”
What are decision trees? (2008, background): “It is also possible to use more complex questions, taking either linear or logical combinations of many features at onc”
Top-down induction of decision trees classifiers - a survey (2005, background): “Finding the best linear combination can be performed using a greedy search [5], [29] linear programming [30], [31], linear discriminant analysis [18], [30], [32]–[35] and others [36]–[38].”
Drug Design by Machine Learning: Support Vector Machines for Pharmaceutical Data Analysis (2001, methodology): “These methods, e.g. OC1 (Murthy et al., 1994), are more powerful but require extensive model selection.”
Optimal classification trees (2017, background): “2016), and perturbation of existing univariate trees (Breiman et al. 1984; Murthy et al. 1994).”
NBDT: Neural-Backed Decision Trees (2020, background): “ancestor’s representative vector. In this ﬁgure, the ancestor is the root, so its representative vector is the average of all leaves w 1;w 2;w 3;w 4. For simplicity, consider an oblique decision tree [32] with non-axis-aligned hyperplanes for each binary decision: Each node in the decision tree is a”
Weighted Oblique Decision Trees (2019, methodology): “While training oblique decision trees is always followed with high running-time cost, as well as the initialization with best axis-parallel splits (Murthy, Kasif, and Salzberg 1994; Norouzi et al. 2015).”
Tree based hierarchical reinforcement learning (2002, background): “Other ways of dividing the region have also been investigated, for example linear divisions of the region are not uncommon (Utgoff and Brodley, 1991; Murthy et al., 1994).”