Decision Tree Algorithm in Machine Learning

Understand how Decision Trees make predictions using conditions and decision rules, along with Gini Impurity, Entropy, Information Gain, and practical concepts.

Introduction

A Decision Tree is a supervised Machine Learning algorithm used for both classification and regression problems.
It makes predictions by asking a series of questions about the input data. Each answer leads to another question or a final prediction.
A Decision Tree works like a flowchart, where each decision helps the model move towards the final result.

Simple Example

Imagine deciding whether to play cricket based on the weather:

• Is it raining?
• Yes: Don’t play.
• No: Check whether it is sunny.
• Yes: Play cricket.
• No: Consider other conditions.

Similarly, a Decision Tree uses conditions and rules to make predictions from data.

Applications of Decision Trees

• Classification: Predicting whether an email is Spam or Not Spam.
• Regression: Predicting numerical values such as house prices or salaries.

Important Components of a Decision Tree

A Decision Tree consists of different components that work together to make predictions.

1. Root Node

The Root Node is the first and topmost node of a Decision Tree. It represents the entire dataset and contains the first decision or split.

2. Decision Node

A Decision Node represents a condition or question based on a feature. It divides the data into smaller groups based on the answers.
Example: Is the study time greater than 5 hours?

3. Leaf Node

A Leaf Node is the final node of a Decision Tree. It gives the final prediction, which can be a class label or a numerical value.

4. Branch

A Branch is the connection between two nodes. It represents the outcome of a decision, such as Yes or No.

Simple Decision Tree Structure

• Root Node: Starting point of the tree.
• Decision Node: Represents a condition.
• Branch: Connects nodes and represents outcomes.
• Leaf Node: Provides the final prediction.

Step 4: How Does a Decision Tree Work?

A Decision Tree follows a Greedy Algorithm to split the dataset and create decision rules.
The main goal is to divide the data into smaller groups so that each group contains similar data points (maximum homogeneity).

Working Steps

1. Start with the Dataset
The algorithm takes the training dataset containing input features (X) and the target variable (Y).

2. Identify the Best Feature
It examines the available features and selects the best feature for the first split. Measures such as Gini Impurity and Entropy help identify the best split.

3. Create the Root Node
The feature selected for the first split becomes the Root Node.

4. Split the Dataset
The dataset is divided into smaller groups based on the selected feature and its conditions.

5. Repeat the Process
The algorithm repeats the splitting process for each child node until a stopping condition is reached.

6. Generate the Final Prediction
The process ends at the Leaf Nodes, which provide the final predicted class or numerical value.

What Is a Greedy Algorithm?

A Greedy Algorithm makes the best possible choice at each step without considering all future possibilities.
In a Decision Tree, it selects the best split at the current node to improve the separation of data.

Gini Impurity in Decision Trees

Gini Impurity is a measure used in Decision Trees to identify how mixed or impure the classes are in a dataset.

It helps the algorithm select the best feature for splitting the data.

• Low Gini Impurity: The node contains mostly one class (high purity).
• High Gini Impurity: The node contains a mixture of different classes.

Gini Impurity Formula

Where:

• Pᵢ: Probability of each class.
• n: Number of classes.

Example: Calculate Gini Impurity

Suppose a dataset contains 10 fruits:

• Yellow fruits = 5
• Purple fruits = 5

Step 1: Calculate the probability of each class.
[P(Yellow)={5}{10}=0.5]

[P(Purple)={5}{10}=0.5]

Step 2: Apply the Gini Impurity formula.

[Gini=1-(0.5)²-(0.5)²]

[=1–0.25–0.25]

[Gini=0.5]

The Gini Impurity is 0.5, which indicates that the dataset contains an equal mixture of both classes.

How Does Gini Impurity Help in Splitting?

A Decision Tree calculates Gini Impurity before and after splitting the dataset.
The Gini Impurity after splitting is calculated using the weighted average of the child nodes

Entropy in Decision Trees

Entropy is a measure used in Decision Trees to calculate the impurity or uncertainty present in a dataset.

It helps the algorithm understand how mixed the classes are before and after splitting the data.

• Low Entropy: The dataset contains mostly one class (high purity).
• High Entropy: The dataset contains a mixture of different classes (high impurity).

Entropy Formula

Example: Calculate Entropy

Suppose a dataset contains 10 fruits:

• Yellow fruits = 5
• Purple fruits = 5

Step 1: Calculate the probability of each class.

[P(Yellow)={5}{10}=0.5]

[P(Purple)={5}{10}=0.5]

Step 2: Apply the Entropy formula.

[Entropy=-[0.5\log_2(0.5)+0.5\log_2(0.5)]]

Since: [\log_2(0.5)=-1]

Therefore:

[Entropy=-[0.5(-1)+0.5(-1)]]

[Entropy=1]

The Entropy is 1, indicating maximum uncertainty for this two-class dataset.

Entropy Values

Information Gain in Decision Trees

Information Gain (IG) is used in Decision Trees to identify the best feature for splitting a dataset.
It measures how much uncertainty (Entropy) is reduced after splitting the data.
The Decision Tree selects the feature with the highest Information Gain because it creates better-separated groups.

Information Gain Formula

IG = Entropy_before — Entropy_after

Get Gollapalli Sai Teja’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Where:

• Entropy Before: Uncertainty in the dataset before splitting.
• Entropy After: Weighted average uncertainty of the child nodes after splitting.

How Does Information Gain Work?

1. Calculate the Entropy of the original dataset.
2. Split the dataset using a feature.
3. Calculate the Entropy of each resulting group.
4. Calculate the weighted average Entropy after splitting.
5. Subtract it from the original Entropy to get Information Gain.
6. Select the feature with the highest Information Gain.

Decision Tree Algorithms — ID3, C4.5, and C5.0

There are different algorithms used to build Decision Trees. Three commonly discussed algorithms are ID3, C4.5, and C5.0.
Each algorithm uses a different approach to select the best feature for splitting the dataset.

1. ID3 (Iterative Dichotomiser 3)

ID3 is one of the basic Decision Tree algorithms used for classification.

• Uses Entropy to measure impurity.
• Uses Information Gain to select the best feature.
• Selects the feature with the highest Information Gain as the splitting feature.

Example: If we have features such as Age, Salary, and Experience, ID3 calculates Information Gain for each feature and selects the one with the highest value.

2. C4.5

C4.5 is an improved version of the ID3 algorithm.

• Uses Entropy and Gain Ratio.
• Gain Ratio helps address the bias of Information Gain toward features with many distinct values.
• It improves the feature-selection process.

3. C5.0

C5.0 is an improved version of C4.5.

• It is generally faster and more efficient.
• It can handle larger datasets more effectively.
• It provides improvements over the C4.5 algorithm.

Overfitting and Underfitting in Decision Trees

Overfitting and underfitting are two common problems in Machine Learning. They occur when a Decision Tree is not built with the right level of complexity.

1. Overfitting

Overfitting occurs when a Decision Tree becomes too complex and learns the training data too closely, including noise and unnecessary details.

• The tree has too many levels or a very high depth.
• It performs very well on training data.
• It may perform poorly on unseen or test data.
• It has low bias and high variance.

Example: Imagine a Decision Tree that creates too many conditions to classify whether a student will pass or fail. It may correctly classify almost every training example but struggle with new students.

2. Underfitting

Underfitting occurs when a Decision Tree is too simple to learn the important patterns in the dataset.

• The tree has very few levels or low depth.
• It cannot capture important relationships in the data.
• It performs poorly on both training and test data.
• It has high bias and low variance.

Example: If a Decision Tree uses only one simple condition to predict whether a student will pass or fail, it may not consider other important factors such as study hours and attendance.

Pruning in Decision Trees

Pruning is a technique used to reduce the complexity of a Decision Tree by removing unnecessary branches or splits.
A Decision Tree may grow too deep and learn unnecessary patterns from the training data. This can lead to overfitting.
Pruning helps control the tree’s growth and improves its ability to make predictions on unseen data.

Why Is Pruning Important?

• Reduces the complexity of the Decision Tree.
• Helps prevent overfitting.
• Removes unnecessary branches.
• Makes the tree easier to understand.
• Helps the model generalize better to new data.

How Does Pruning Work?

Pruning controls how much a Decision Tree can grow.
For example:

• If a node does not provide a useful split, we can stop splitting it.
• We can control the maximum depth of the tree.
• Unnecessary branches can be removed to make the tree simpler.

Example

Imagine a Decision Tree created to predict whether a student will pass or fail.
If the tree creates too many conditions based on small differences in the training data, it may become unnecessarily complex.
By applying pruning, we can remove less useful branches and create a simpler tree that makes better predictions on new student data.

Decision Tree for Regression

Decision Trees are not limited to classification problems. They can also be used for regression problems, where the goal is to predict a continuous numerical value.

What Is Decision Tree Regression?

Decision Tree Regression is a supervised Machine Learning technique used to predict numerical values by dividing the dataset into smaller groups based on feature conditions.

Instead of predicting categories such as Yes or No, it predicts values such as:

• House prices
• Employee salaries
• Temperature
• Sales revenue

Example: Imagine predicting house prices based on features such as area, number of bedrooms, and location. A Decision Tree asks a series of questions about these features and predicts the house price.

How Does Decision Tree Regression Work?

1. Start with the dataset containing input features (X) and a numerical target (Y).
2. Select the best feature and splitting condition.
3. Divide the dataset into smaller groups.
4. Calculate the prediction for each group.
5. Continue splitting until the stopping condition is reached.
6. Predict the numerical value for a new input.

Mean Squared Error (MSE)

In Decision Tree Regression, Mean Squared Error (MSE) is commonly used to evaluate how well the values within a group are represented by their mean.

The formula is:

Where:

• n = Number of observation
• yi = Actual value
• bar {y} = Mean of actual values

A lower MSE indicates that the predicted values are closer to the actual values.
When selecting a split, the algorithm compares the weighted MSE of the resulting groups and prefers the split with the lower error.
Advantages and Disadvantages of Decision Trees
Decision Trees are widely used in Machine Learning because they are simple to understand and can solve both classification and regression problems. However, they also have some limitations.

Advantages of Decision Trees

1. Easy to Understand: Decision Trees are simple to interpret because they work like a flowchart with conditions and decisions.
2. Handles Classification and Regression: They can predict both categorical values and continuous numerical values.
3. No Feature Scaling Required: Decision Trees do not require standardization or normalization because they split data based on feature conditions.
4. Handles Non-Linear Relationships: They can identify complex patterns and non-linear relationships in datasets.
5. Easy to Visualize: The tree structure makes it easier to understand how the model makes predictions.

Disadvantages of Decision Trees

1. Overfitting: A Decision Tree can become too complex and learn unnecessary patterns from training data.
2. Sensitive to Data Changes: Small changes in the training dataset can sometimes produce a very different tree structure.
3. Prone to Underfitting: If the tree is too shallow, it may fail to capture important patterns.
4. Greedy Approach: It selects the best split at each step without considering all possible future splits.
5. May Require Pruning: Pruning or depth control may be needed to reduce complexity and improve generalization.

Key Takeaway

Decision Trees are easy to understand, visualize, and use for classification and regression. However, controlling their depth and avoiding overfitting are important for building a reliable model.

Conclusion

Decision Trees are one of the important supervised Machine Learning algorithms used for both classification and regression.
In this article, we explored how Decision Trees work, their important components, and how they select the best features using Gini Impurity, Entropy, and Information Gain.
We also covered ID3, C4.5, and C5.0 algorithms, overfitting and underfitting, pruning, and Decision Tree Regression using Mean Squared Error.

Key Takeaways:

• Decision Trees make predictions using a series of conditions.
• Gini Impurity and Entropy measure impurity in classification.
• Information Gain helps select the best feature for splitting.
• ID3 uses Information Gain, while C4.5 uses Gain Ratio.
• Pruning helps control overfitting.
• Decision Tree Regression predicts continuous numerical values using criteria such as MSE.