Multivariate Decision Tree Core Formulas

Unlike a univariate decision tree, each internal node of a multivariate decision tree uses a linear combination of multiple features for splitting, and can produce decision boundaries in any direction.

① Linear Discriminant Function

A node maps the input vector \(\mathbf{x}\) to a real number through a linear function, which is defined by the weight vector \(\mathbf{w}\) and the bias \(b\).

Parameters:
\(\mathbf{x} = (x_1, x_2, \dots, x_n)\) — input feature vector
\(\mathbf{w} = (w_1, w_2, \dots, w_n)\) — weight vector
\(b\) — bias term
\(f(\mathbf{x})\) — linear discriminant value

② Split Rule

Samples are assigned to the left or right subtree according to the sign of the linear discriminant value. When \(f(\mathbf{x}) > 0\), the sample goes to the right subtree; otherwise it goes to the left subtree.

Parameters:
\(f(\mathbf{x})\) — output of the linear discriminant function
The decision boundary is the hyperplane: \(\mathbf{w} \cdot \mathbf{x} + b = 0\)

③ Weighted Impurity (Gini Index)

Multivariate splits also use impurity measures to evaluate split quality, commonly the Gini index or information entropy. The lower the weighted impurity, the purer the split.

Parameters:
\(D\) — current dataset
\(D_L, D_R\) — left and right subsets
\(Gini(D)\) — Gini index
\(|D|\) — number of samples

Multivariate Split Interactive Simulation

Drag the sliders to adjust the weights and bias of the linear discriminant function, and observe how the decision boundary rotates and shifts, as well as how the classification impurity changes.

Linear Discriminant Parameters

Current w₁ = 2.00
Current w₂ = 1.00
Current b = -3.00
The larger the value, the greater the noise and the more mixed the data
Root Node Gini Index
--
Weighted Gini Index
--
Information Gain
--
Classification Accuracy
--
Data Distribution and Linear Decision Boundary
Current Decision Tree Structure

Standard Introduction

A multivariate decision tree is an extension of the decision tree in which internal nodes no longer test based only on the threshold of a single feature, but instead use a linear combination of multiple features (or a more complex function) to partition the data. This allows the decision boundary to be a hyperplane in any direction, giving it stronger expressive power when handling problems in which features are correlated.

For example, a two-dimensional multivariate node can be expressed as \(w_1 x_1 + w_2 x_2 + b > 0\), and the corresponding decision boundary is a straight line with an arbitrary slope. Compared with the axis-parallel boundaries of univariate decision trees, multivariate trees can usually achieve similar accuracy with a shallower tree.

Plain-Language Introduction

An ordinary decision tree is like a robot that can only ask simple "yes/no" questions, and each question can only be about a single feature, such as "is x₁ greater than 5?". Such questions can only draw horizontal or vertical lines, and the partitioned regions look like a bunch of rectangles pieced together.

A multivariate decision tree is smarter: it can consider multiple features at the same time and ask questions such as "is \(2x₁ + 3x₂ - 5\) greater than 0?". Such questions can draw slanted lines, making the partitioned regions more flexible, and often fewer questions are needed to separate the data.

What Problem Does It Solve

  • Axis-parallel limitation: univariate trees can only produce axis-parallel piecewise-constant boundaries, and are inefficient for data with diagonal distributions.
  • Feature interactions: they can directly model linear combination relationships between features, without the need to construct cross features afterward.
  • Model compactness: when achieving similar accuracy, multivariate trees usually have smaller tree depth and fewer nodes.
  • Representational power: they can approximate any linear decision boundary, whereas univariate trees require a large number of piecewise approximations.

Why It Matters

Multivariate decision trees extend the capabilities of traditional decision trees and hold an important position in pattern recognition and data mining. They retain the advantage of strong interpretability of decision trees while introducing stronger expressive power for classification boundaries. Their ideas have also inspired many ensemble methods, such as Oblique Random Forest. In addition, before the emergence of neural networks, multivariate splits were one of the important methods for building linear classifiers.

Application Scenarios

  • Image recognition: pixel features are highly correlated, and oblique boundaries can partition them more efficiently.
  • Medical diagnosis: combinations of multiple biological indicators are often more discriminative than a single indicator.
  • Financial risk control: linear combinations of multiple financial indicators in credit scoring models.
  • Industrial process control: sensor data fusion, determining states through combinations of multiple variables.
  • Text classification: linear combinations of word vector features for document topic classification.

Limitations and Drawbacks

  • High computational complexity: finding the optimal linear combination usually requires solving an optimization problem (such as linear discriminant analysis or a perceptron), which is slower than univariate threshold search.
  • Risk of overfitting: there are more parameters, and without constraints it may be more prone to overfitting.
  • Reduced interpretability: although it is still a tree structure, the node tests are linear combinations and are less intuitive than a single threshold.
  • Local optima: greedy construction may lead to linear splits that are not globally optimal.
  • Sensitive to data scaling: differences in the scales of different features may affect weight learning, so standardization is needed in advance.