Decision Trees Explained

Learn all about Decision Tree and its Visualization

⬅️ Previous: [Support Vector Machine(SVM)]

Types of Tree based ML models:

1. Base Model: Decision Tree

The foundational building block [2, 13]. It splits data into subsets using simple if-else rules based on features like age or income [1, 18].

• CART (Classification and Regression Trees): The industry standard that handles both labels and numerical values [2, 30]. It uses Binary Tree i.e. two nodes at every level. Sklearn always uses CART means there will two child at max at each node.
• Variants: Includes ID3 and C4.5, which use different math (Entropy vs. Gini) to decide where to split [14, 30]. It have more than two nodes at every level.

2. Parallel Ensembles (Bagging)

Instead of one tree, these models train many trees independently and average their results to reduce errors [2, 26].

• Random Forest: The most popular bagging model [15]. It trains each tree on a random sample of data and a random subset of features to ensure diversity [2, 40].
• Extra Trees: An even more randomized version that picks split points entirely at random to further lower variance [8, 19].

3. Sequential Ensembles (Boosting)

These models build trees one after another. Each new tree focuses specifically on correcting the mistakes made by the previous ones [1, 25].

• AdaBoost: The pioneer boosting method that gives more weight to misclassified data points [1, 15].
• Gradient Boosting (GBM): Uses gradient descent to minimize errors [1, 25].
• Modern Powerhouses: Optimized versions of GBM used in competitions and production:
• XGBoost: Known for extreme speed and performance [17, 37].
• LightGBM: Optimized for large datasets using “leaf-wise” growth [2, 37].
• CatBoost: Specialized for handling categorical data (like “City” or “Color”) without complex prep [2, 37].

Decision Trees

Tree based Algorithms are different branch of ML model like Regression. It is non-parametric model means don’t make any assumption about the data and can work on non-linear data. It is a white-box model means pridiction is explainable thus vary useful on critical places like bank loan approval. It works with both Classification and Regression. It is a giant nested if else structure.

Example: If we have to recomment which app a person will use the more given gender and occupation of the person. then we can see that if occupation is Student then the person will use PUBG, if the person is Programmer and Gender is M then he will use Whatsapp else will use Github.

Example: In the second example it is very difficult to mannually find the if and else condition. That is why Decision Tree is used.

Impurity Function, H

It decide the column and its value for a node. Example: Gini Impurity and Entropy for Classification and MSE and MAE for Regression.

Gini Impurity

The Gini impurity is a measure of how often a randomly chosen element from the set would be incorrectly labelled if it was randomly labelled according to the distribution of labels in the subset.

The geometric intuition of a decision tree is based on recursive partitioning of the feature space, which breaks the data into smaller, non-overlapping, and more homogeneous rectangles (in 2D) or hyper-rectangles (in higher dimensions). Each split in the tree corresponds to a straight line (decision boundary) that is perpendicular to one of the feature axes.

Gini Impurity = 0 means Pure Node (One branch contain one value and other contain rest of the values). This is the leaf Node.

CART (Classification AND Regression Trees) Algorithm

It is an algorithm to grow decision tree.

The CART Algorithm — Classification

At a given node, Divide data set into two parts for a column and one of the column’s value. Then calculate the Overall Weighted Impurity (G value) and set the node to the lowest value and move to next sub node untill we reach the leaf node (no rows left to divide).

Splitting Categorical Features

Dataset with Binary, Multi Class and Numerical Column

• Binary Class Categorical Feature: Splitting value is only one i.e. if Field is Science or not. Then calculate gini impurity and G value. Calculating probability of Job_Outcome in both newly created sub-datasets.
• Multi Class Categorical Feature: We will calculate G value 3 time (Undergraduate or not, PhD or not, Postgraduate or not)

Splitting Numerical Features: Order in ascending order. split between each two rows and take the average (average of 85 and 86 is 85.5). for each of these value, Calculate G vlaue like Grade > 85.5 or not. Compare the G value for the column and select the smallest one.

from sklearn.tree import DecisionTreeClassifier, plot_tree, DecisionTreeRegressor
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score
from sklearn.datasets import load_iris
from sklearn.tree import export_text
import matplotlib.pyplot as plt
import numpy as np

iris = load_iris()
X = iris.data[:, :2]  # we only take the first two features.
y = iris.target

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

clf = DecisionTreeClassifier(max_depth=3, min_samples_split=40)
clf.fit(X_train, y_train)

y_pred = clf.predict(X_test)
print(f"Accuracy: {accuracy_score(y_test, y_pred)}") # Accuracy: 0.8

# Plot the decision tree
plt.figure(figsize=(12, 8))
plot_tree(clf, filled=True, feature_names=iris.feature_names[:2], class_names=iris.target_names)
plt.show()

# Plot the decision boundary
plt.figure(figsize=(8, 6))
x_min, x_max = X[:, 0].min() - 1, X[:, 0].max() + 1
y_min, y_max = X[:, 1].min() - 1, X[:, 1].max() + 1
xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.01), np.arange(y_min, y_max, 0.01))

Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
Z = Z.reshape(xx.shape)

plt.contourf(xx, yy, Z, alpha=0.8)
plt.scatter(X[:, 0], X[:, 1], c=y, edgecolor='k')
plt.xlabel('Sepal length')
plt.ylabel('Sepal width')
plt.show()

print(export_text(clf, feature_names=['sepal_length','sepal_width']))

print(clf.feature_importances_) # array([0.83569313, 0.16430687])
# feature importance of sepal_length and sepal_width are 0.83 and 0.16 

Here, for each region majority of class will be the class for the entire region like if value = [1, 5, 1] then output will be versicolor and its probability will be 5/7.

The CART Algorithm — Regression

Here, MSE(Variance) as Impurity Function.

• Binary Class Categorical Feature: Split into sub-node like (Math or not) then calculate the MSE for the Test_Score column for both sub-nodes.
• Multi Class Categorical Feature: Split into sub-node like (Junior or not), (Sophomore or not) and (Freshman or not) then calculate the MSE for the Test_Score column for both sub-nodes for each Class in Grade_Level. The Class with minimum variance is G.
• Numerical Feature: Sort the column in ascending order, then split between two different number and calculate the mean like (2 between 1 and 3), (3.5 between 3 and 4), (5 between 4 and 6) and (7.5 between 6 and 9). create sub-node on (hours > 2), (hours > 3.5), (hours > 5) and (hours > 7.5). for each sub-node, calculate MSE and select the lowest as G.

# Generate a non-linear dataset based on the sine function
np.random.seed(0)
X = np.sort(5 * np.random.rand(80, 1), axis=0)
y = np.sin(X).ravel()
y[::5] += 3 * (0.5 - np.random.rand(16))  # add some noise to the data

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)

regressor = DecisionTreeRegressor(max_depth=2)
regressor.fit(X_train, y_train)

# To plot the regression curve, we'll sort the X values and predict Y values for the sorted X
X_grid = np.arange(np.min(X), np.max(X), 0.01)[:, np.newaxis]
y_grid = regressor.predict(X_grid)

# Plot the training data and the regression curve
plt.scatter(X_train, y_train, color='red', label='data')
plt.plot(X_grid, y_grid, color='blue', label='prediction')
plt.title('Decision Tree Regression')
plt.xlabel('X')
plt.ylabel('Y')
plt.legend()
plt.show()

Regression Curve || piecewise constant approximation

# Plot the decision tree
plt.figure(figsize=(12, 8))
plot_tree(regressor, filled=True)
plt.show()

Regression Tree for max_depth=2

There are 4 reason and 0.676, 0.059, -0.674 and -0.903 are prediction value for each reason. Each value reprsent mean of all data points in the reason.

Advantages and Disadvantages

Advantages

• Simple to understand and to interpret. Trees can be visualized.
• Requires little data preparation. Other techniques often require data
  normalization, dummy variables need to be created and blank values to
  be removed. Note however that this module does not support missing
  values.
• The cost of using the tree (i.e., predicting data) is logarithmic in the
  number of data points used to train the tree. Much faster than KNN.
• Able to handle both numerical and categorical data.
• Can work on non-linear datasets
• Can give you feature importance

Disadvantages

• Decision-tree learners can create over-complex trees that do not generalize the data well. This is called overfitting. Mechanisms such as pruning, setting the minimum number of samples required at a leaf node or setting the maximum depth of the tree are necessary to avoid this problem.
• Decision trees can be unstable because small variations in the data might result in a completely different tree being generated. This problem is mitigated by using decision trees within an ensemble.
• Predictions of decision trees are neither smooth nor continuous, but piecewise constant approximations as seen in the above figure. Therefore, they are not good at extrapolation. We can use Decision Tree only on marks not on profit because mark’s value are fixed between 0 and 100 while profit is not fixed. Because there is no equation like in linear regression. thus we can make prediction in range of values on which the model is trained. This limitation is inherent to the structure of decision tree models. They are very useful for interpretability and for handling non-linear relationships within the range of the training data, but they aren’t designed for extrapolation. If extrapolation is important for your task, you might need to consider other types of models.
• Decision tree learners create biased trees if some classes dominate. It is therefore recommended to balance the dataset prior to fitting with the decision tree.

Node Importance (ni) : measures the weighted decrease in impurity resulting from a split at that node. Essentially, a node is considered important if it splits a large portion of the data (Nj/N) and significantly reduces the impurity of the resulting groups. It cannot be calculated for leaf node.

Feature Importance

The importance of a feature is computed as the (normalized) total reduction of the criterion brought by that feature. It is also known as the Gini importance for classification. It gives feature importance during the training of the data. Feature importance is the fraction of the total impurity reduction in the tree that can be attributed to that specific feature.

Feature Importance (fik) || Total Importance of a specific feature k

The Problem of Overfitting

Overfitting in Classification and Regression

The chances of overfitting is highest is in Decision Tree and will don’t perform well on test data as it has learnt too much the training data point.

Get Mr. Vivek Kumar’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Q. Why Overfitting happens?

Answer. The overfitting in Decision Tree is due to the work of Decision Tree which don’t have Stopping Criteria. For classification, It work untill all points of a region has be correctly classified as one class. For regression, It work untill all the point have smallest MSE(Variance) i.e. 0 means all point lie at same position.

we have to change the stopping criteria and reduce the length of the tree by reducing the number of nodes. But, a lots of nodes are not necessaryly usefull. This is achived by removing the unnecessary nodes to reduce the tree size and reducing the overfitting.

Pruning

Pruning is to cut branches or parts of branches off a tree or bush in order to make it a better shape.

Pruning is a technique used in machine learning to reduce the size of decision trees and to avoid overfitting. Overfitting happens when a model learns the training data too well, including its noise and outliers, which results in poor performance on unseen or test data.

Decision trees are susceptible to overfitting because they can potentially create very complex trees that perfectly classify the training data but fail to generalize to new data. Pruning helps to solve this issue by reducing the complexity of the decision tree, thereby improving its predictive power on unseen data.

There are two main types of pruning:

1. Pre-pruning (Early stopping): This method halts the tree construction early. It can be done in various ways: by setting a limit on the maximum depth of the tree, setting a limit on the minimum number of instances that must be in a node to allow a split, or stopping when a split results in the improvement of the model’s accuracy below a certain threshold.
2. Post-pruning (Cost Complexity Pruning): This method allows the tree to grow to its full size, then prunes it. Nodes are removed from the tree based on the error complexity trade-off. The basic idea is to replace a whole subtree by a leaf node, and assign the most common class in that subtree to the leaf node.

Pre-pruning

Pre-pruning is a technique where the decision tree is pruned during the learning process as soon as it’s clear that further splits will not add significant value. There are several strategies for pre-pruning:

1. Maximum Depth: One of the simplest forms of pre-pruning is to set a limit on the maximum depth of the tree. Once the tree reaches the specified depth during training, no new nodes are created. This strategy is simple to implement and can effectively prevent overfitting, but if the maximum depth is set too low, the tree might be overly simplified and underfit the data. It start from 1 and default is None.
2. Minimum Samples Split: This is a condition where a node will only be split if the number of samples in that node is above a certain threshold. If the number of samples is too small, then the node is not split and becomes a leaf node instead. This can prevent overfitting by not allowing the model to learn noise in the data. High value cause underfitting and low value cause overfitting at Parent level.
3. Minimum Samples Leaf: This condition requires that a split at a node must leave at least a minimum number of training examples in each of the leaf nodes. Like the minimum samples split, this strategy can prevent overfitting by not allowing the model to learn from noise in the
   data. High value cause underfitting and low value cause overfitting at Child level.
4. Maximum Leaf Nodes: This strategy limits the total number of leaf nodes in the tree. The tree stops growing when the number of leaf nodes equals the maximum number. High value cause Overfitting and low value cause Underfitting at Child level.
5. Minimum Impurity Decrease: This strategy allows a node to be split if the impurity decrease of the split is above a certain threshold. Impurity measures how mixed the classes within a node are. If the decrease is too small, the node becomes a leaf node.
6. Maximum Features: This strategy considers only a subset of features for deciding a split at each node. The number of features to consider can be defined and this helps in reducing overfitting. Features are selected randomly.

Advantages of Pre-Pruning:

1. Simplicity: Pre-pruning criteria such as maximum depth or minimum number of samples per leaf are easy to understand and implement.
2. Computational Efficiency: By limiting the size of the tree, pre-pruning can substantially reduce the computational cost of training and prediction.

Disadvantages of Pre-Pruning:

1. Risk of Underfitting: If the stopping criteria are too strict, pre-pruning can halt the growth of the tree too early, leading to underfitting. The model may become overly simplified and fail to capture important patterns in the data.
2. Requires Fine-Tuning: The pre-pruning parameters (like maximum depth or minimum samples per leaf) often require careful tuning to find the right balance between underfitting and overfitting.
3. Short Sightedness: Can prune good nodes if they come after a bad node.

Post Pruning

Post-pruning, also known as backward pruning, is a technique used to prune the decision tree after it has been built. There are several strategies for post-pruning:

1. Cost Complexity Pruning (CCP): Also known as Weakness Pruning, this technique introduces a tuning parameter (α) that trades off between tree complexity and its fit to the training data. For each value of α, there is an optimal subtree that minimizes the cost complexity criterion. The subtree that minimizes the cost complexity criterion over all values of α is chosen as the pruned tree.
2. Reduced Error Pruning: In this method, starting at the leaves, each node is replaced with its most popular class. If the accuracy is not affected in the validation set, the change is kept.

Advantages of Post-Pruning:

1. Reduced Overfitting: Post-pruning methods can help to avoid overfitting the training data, which can lead to better model generalization and thus better performance on unseen data.
2. Preserving Complexity: Unlike pre-pruning, post-pruning allows the tree to grow to its full complexity first, which means it can capture complex patterns in the data before any pruning is done.
3. Better Performance: Post-pruned trees often outperform pre-pruned trees, as they are able to better balance the bias-variance trade-off.

Disadvantages of Post-Pruning:

1. Increased Computational Cost: Post-pruning can be more computationally intensive than pre-pruning, as the full tree must be grown first before it can be pruned.
2. Requires Validation Set: Many post-pruning methods require a validation set to assess the impact of pruning. This reduces the amount of data available for training the model.
3. Complexity of Implementation: Post-pruning methods, especially those involving tuning parameters (like cost complexity pruning), can be more complex to implement and understand than pre-pruning methods.
4. Risk of Underfitting: Similar to pre-pruning, if too much pruning is done, it can lead to underfitting where the model becomes overly simplified and fails to capture important patterns in the data.

Piecewise Constant Approximation

A piecewise constant approximation represents a complex signal or function as a series of constant horizontal segments, typically by taking the average value of the function over defined intervals. It reduces functions to rectangular regions, commonly used for signal discretization, lossy data compression, and Haar wavelet analysis.

Visualization of Decision Trees

• Classification

! pip install dtreeviz

from sklearn.tree import DecisionTreeRegressor, plot_tree, DecisionTreeClassifier
from sklearn.model_selection import train_test_split
from IPython.display import Image, display_svg, SVG
from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as plt
from sklearn.datasets import *
import graphviz.backend as be
from dtreeviz.trees import *
import pandas as pd
import dtreeviz

clas = DecisionTreeClassifier()  
iris = load_iris()

X_train = iris.data
y_train = iris.target
clas.fit(X_train, y_train)

# Classification
viz = dtreeviz.model(clas, X_train, y_train, feature_names=iris.feature_names, class_names=["setosa", "versicolor", "virginica"])
viz.view(fontname='Liberation Serif')

Classification

• Regression

regr = DecisionTreeRegressor(max_depth=1)

np.random.seed(0)
X = np.sort(5 * np.random.rand(80, 1), axis=0)
y = np.sin(X).ravel()
y[::5] += 3 * (0.5 - np.random.rand(16))

X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)

regressor = DecisionTreeRegressor(max_depth=2)
regressor.fit(X_train, y_train)

X_grid = np.arange(np.min(X), np.max(X), 0.01)[:, np.newaxis]
y_grid = regressor.predict(X_grid)

regr.fit(X_train, y_train)

viz = dtreeviz.model(regr, X_train, y_train, target_name='price')
viz.view(fontname='Liberation Serif', scale=4)

Regression

• Show Prediction Path

clas = DecisionTreeClassifier()  
iris = load_iris()

X_train = iris.data
y_train = iris.target
clas.fit(X_train, y_train)

X = iris.data[np.random.randint(0, len(iris.data)),:]

viz = dtreeviz.model(clas, X_train, y_train, feature_names=iris.feature_names, class_names=["setosa", "versicolor", "virginica"], X=X)
viz.view(x=X, fontname='Liberation Sans')

Show Prediction Path

• Show Node Number

viz = dtreeviz.model(clas, X_train, y_train, target_name='price', feature_names=iris.feature_names, class_names=["setosa", "versicolor", "virginica"])
viz.view(fontname='Liberation Serif', show_node_labels=True, orientation="LR")

Show Node Number

• Without Any Graphs

viz = dtreeviz.model(clas, X_train, y_train, target_name='price', feature_names=iris.feature_names, class_names=["setosa", "versicolor", "virginica"])
viz.view(fontname='Liberation Serif', fancy=False)

Without Any Graphs

• Show Just Prediction Path, Nothing Else

clas = DecisionTreeClassifier()  
iris = load_iris()

X_train = iris.data
y_train = iris.target
clas.fit(X_train, y_train)

X = iris.data[np.random.randint(0, len(iris.data)),:]

viz = dtreeviz.model(clas, X_train, y_train, target_name='price', feature_names=iris.feature_names, class_names=["setosa", "versicolor", "virginica"])
viz.view(fontname='Liberation Sans', show_just_path=True)

Show just prediction path, nothing else

• Prediction Path in Plain English

print(viz.explain_prediction_path(X))

# 4.95 <= petal length (cm)
# 0.8 <= petal width (cm)  < 1.55

• Feature Importance

viz.instance_feature_importance(X, figsize=(3.5, 2), fontname='Liberation Sans')

Feature Importance

• Univariate Regression

df_cars = pd.read_csv("cars.csv")
X, y = df_cars[['WGT']], df_cars['MPG']

dt = DecisionTreeRegressor(max_depth=3, criterion="mae")
dt.fit(X, y)

fig = plt.figure()
ax = fig.gca()
rtreeviz_univar(dt, X, y, 'WGT', 'MPG', ax=ax)
plt.show()

Univariate Regression

• 3-D Regression

X = df_cars[['km_driven','ENG']]
y = df_cars['MPG']

dt = DecisionTreeRegressor(max_depth=3, criterion="absolute_error")
dt.fit(X, y)

viz = dtreeviz.model(dt, X_train=X, y_train=y, feature_names=['km_driven', 'ENG'], target_name='MPG')

figsize = (6, 5)
fig = plt.figure(figsize=figsize)
ax = fig.add_subplot(111, projection='3d')
viz.rtree_feature_space3D(features=['km_driven', 'ENG'], fontsize=14, elev=20, azim=25, dist=8.2, show={'splits','title'}, ax=ax, fontname='Liberation Sans')
plt.show()

3-D Regression

➡️ Next Up: [Ensemble Learning, Bagging and Random Forests]

If you found value in this content, I invite you to stay connected for more insightful posts. Your time and interest are greatly appreciated. Thank you for reading!