Decision Trees

Decision trees are versatile machine learning algorithms that can perform both classification and regression tasks, and even multioutput tasks. They are powerful algorithms, capable of fitting complex datasets.

Note. > Graphviz is an open source graph visualization software package. It also includes a dot command-line tool to convert .dot files to a variety of formats, such as PDF or PNG.

One of the many qualities of decision trees is that they require very little data preparation. In fact, they don’t require feature scaling or centering at all.

• Node - a point in a Decision Tree where the data is either split based on a condition or assigned a final prediction.
• Root Node - the first node of a decision tree. It contains all training instances before any split happens.
• Split Node - node that divides the data into smaller groups based on a feature condition, such as petal length <= 2.45.
• Leaf Node - a final node in the tree where no further splitting occurs. This node gives the model's predicted class.
• Samples - the number of training instances that reach a specific node. For example, samples = 100 means 100 training instances satisfy the conditions needed to reach that node.
• Value - the number of training instances from each class that reach a node. For example, value = [0, 49, 5] means the node contains 0 Iris setosa, 49 Iris versicolor, and 5 Iris virginica instances.
• Class - the predicted class of a node. It is usually the class with the highest count in the node's value.
• Gini Impurity - a measure of how mixed the classes are in a node. A node is considered pure when all training instances in that node belong to the same class.

The Gini impurity of the ith node is computed as:

$$G_i = 1 - \sum_{k=1}^{n} p_{i,k}^2$$

where p_{i,k} is the ratio of class k instances among the training instances in node i.

For a node with value = [0, 49, 5], the Gini impurity is:

$$G_i = 1 - (0/54)^2 - (49/54)^2 - (5/54)^2 \approx 0.168$$

This means the node is mostly pure because most samples belong to one class, Iris versicolor, but it still contains a few Iris virginica samples.

• White Box Model
  A Machine Learning model whose decision-making process is easy to understand, inspect, and explain. Example: Decision Trees.

• Black Box Model
  A Machine Learning model that can make accurate predictions, but whose internal reasoning is difficult to interpret or explain clearly. Examples: Random Forests and Neural Networks.

CART Training Algorithm

The CART Algorithm stands for Classification and Regression Tree. It is the algorithm used by Scikit-Learn to train or “grow” Decision Trees. CART works by splitting the training set into two subsets using one feature k and one threshold t_k. It chooses the split that produces the purest subsets, weighted by their size.

The CART cost function for classification is:

$$J(k, t_k) = \frac{m_{left}}{m}G_{left} + \frac{m_{right}}{m}G_{right}$$

where G_left/right is the impurity of the left or right subset, and m_left/right is the number of instances in each subset.

After the first split, CART repeats the same process recursively on each subset. It stops when it reaches max_depth, or when no split can reduce impurity further.

Important stopping hyperparameters include max_depth, min_samples_split, min_samples_leaf, min_weight_fraction_leaf, and max_leaf_nodes.

CART is a greedy algorithm because it chooses the best split at each level without checking whether that split will lead to the best overall tree. This usually gives a reasonably good tree, but not always the optimal one. Finding the optimal decision tree is an NP-complete problem, so CART settles for a good practical solution instead of searching all possible trees.

Definition. Complexity Classes: P, NP, NP-Hard, and NP-Complete P is the set of problems that can be solved in polynomial time.

$$P = \{L \mid L \text{ can be solved in polynomial time}\}$$

NP is the set of problems whose solutions can be verified in polynomial time.

$$NP = \{L \mid L \text{ can be verified in polynomial time}\}$$

A problem is NP-hard if every problem in NP can be reduced to it in polynomial time.

$$\forall L \in NP,\quad L \leq_p H$$

A problem is NP-complete if it is both in NP and NP-hard.

$$C \in NP\text{-Complete} \iff C \in NP \text{ and } C \in NP\text{-Hard}$$

The P versus NP question asks whether every problem whose solution can be verified quickly can also be solved quickly.

$$P \stackrel{?}{=} NP$$

Gini Impurity vs Entropy

Definition. Entropy Entropy is an impurity measure used in Decision Trees. A node has entropy 0 when all instances belong to the same class. Higher entropy means the node contains a more mixed set of classes.

$$H_i = - \sum_{\substack{k=1 \ p_{i,k} \neq 0}}^{n} p_{i,k}\log_2(p_{i,k})$$

where $p_{i,k}$ is the ratio of class $k$ instances among the training instances in node $i$.

By default, DecisionTreeClassifier uses Gini Impurity, but entropy can be selected by setting:

criterion="entropy"

In practice, Gini Impurity and Entropy usually produce similar Decision Trees. Gini impurity is slightly faster to compute, so it is a good default. When they differ, Gini tends to isolate the most frequent class in its own branch, while entropy tends to create slightly more balanced trees.

Regularization Hyperparameters

Decision Trees make very few assumptions about the training data. If left unconstrained, the tree can grow until it fits the training data very closely, which can lead to Overfitting.

Definition. Nonparametric Model A nonparametric model does not have a fixed number of parameters before training. Its structure can adapt freely to the training data.

Decision Trees are nonparametric models because they can keep growing depending on the data.

Definition. Parametric Model A parametric model has a fixed number of parameters before training.

Example: Linear Regression has a predetermined form, so its flexibility is limited.

To reduce overfitting, the freedom of a Decision Tree must be restricted during training. This is called Regularization.

The main regularization hyperparameter is max_depth, which controls the maximum depth of the tree. The default value is None, meaning the tree can grow without a depth limit. Reducing max_depth makes the model simpler and lowers the risk of overfitting.

Other important DecisionTreeClassifier regularization hyperparameters include:

• max_features: maximum number of features evaluated when splitting each node.
• max_leaf_nodes: maximum number of leaf nodes allowed in the tree.
• min_samples_split: minimum number of samples a node must have before it can be split.
• min_samples_leaf: minimum number of samples required for a leaf node to be created.
• min_weight_fraction_leaf: similar to min_samples_leaf, but expressed as a fraction of the total weighted instances.

Increasing min_* hyperparameters or reducing max_* hyperparameters regularizes the model and helps reduce overfitting.

Pruning removes decision tree branches that do not provide a statistically meaningful improvement.

Decision Tree Regression

Decision Trees can also be used for Regression tasks using Scikit-Learn’s DecisionTreeRegressor.

import numpy as np
from sklearn.tree import DecisionTreeRegressor

np.random.seed(42)
X_quad = np.random.rand(200, 1) - 0.5  # a single random input feature
y_quad = X_quad ** 2 + 0.025 * np.random.randn(200, 1)

tree_reg = DecisionTreeRegressor(max_depth=2, random_state=42)
tree_reg.fit(X_quad, y_quad)

Unlike classification trees, which predict a class, regression trees predict a numerical value. The prediction for each region is the average target value of the training instances in that region.

For example, if a new instance has $x_1 = 0.2$, the tree follows the decision rules until it reaches a leaf node. The predicted value is the value stored in that leaf, such as:

$$\hat{y} = 0.111$$

This value is the average target value of the training samples assigned to that leaf.

Definition. Regression Tree Prediction A Regression Tree predicts the average target value of the training instances that fall into the same leaf node.

The CART Algorithm for regression works similarly to classification, but instead of minimizing impurity such as Gini Impurity or Entropy, it minimizes Mean Squared Error.

$$J(k, t_k) = \frac{m_{\text{left}}}{m}\text{MSE}_{\text{left}} + \frac{m_{\text{right}}}{m}\text{MSE}_{\text{right}}$$

where:

$$\text{MSE}_{\text{node}} = \frac{\sum_{i \in \text{node}}(\hat{y}_{\text{node}} - y^{(i)})^2}{m_{\text{node}}}$$

and:

$$\hat{y}_{\text{node}} = \frac{\sum_{i \in \text{node}} y^{(i)}}{m_{\text{node}}}$$

The model splits the data into regions so that the target values inside each region are as close as possible to the predicted average value.

Regression trees are also prone to Overfitting. Without regularization, the tree may fit the training data too closely and create very unstable predictions. Setting hyperparameters such as max_depth or min_samples_leaf helps regularize the model.

For example:

DecisionTreeRegressor(min_samples_leaf=10)

This forces each leaf to contain at least 10 samples, resulting in a smoother and more reasonable regression tree.

Principal Component Analysis rotates the data in a way that reduces the correlation between features, which often (not always) makes things easier for trees.

Decision Trees Have High Variance

Decision Trees have high variance, meaning small changes in the training data or hyperparameters can produce very different trees.

This happens because the training algorithm is partly stochastic. In Scikit-Learn, the algorithm randomly selects the set of features to evaluate at each node, so retraining the same model on the same data may still produce a different tree unless random_state is fixed.

random_state=42

Setting random_state makes the results reproducible.

Definition. High Variance A model has high variance when it is highly sensitive to small changes in the training data or training process. This can make the model unstable and prone to Overfitting.

A common way to reduce variance is to average predictions over many different trees. An ensemble of decision trees is called a Random Forest.

Definition. Random Forest A Random Forest is an ensemble model made of many Decision Trees. By averaging their predictions, it reduces variance and usually produces more stable and accurate results.