Decision Trees in Machine Learning: From Intuition to Gini Impurity
Introduction — A Model That Thinks Like a Human
Imagine deciding whether to play cricket on a particular day. You might start by asking, “Is it raining?” If not, you may check whether the weather is suitable. Based on these answers, you make your final decision. We follow a similar process when making many everyday decisions.
A Decision Tree is a supervised machine learning algorithm that follows a sequence of questions to make predictions. It learns patterns from data by dividing it into smaller groups based on different conditions. Each decision leads to another question or a final prediction.
Decision Trees can be used for both classification and regression. They can predict categories, such as whether an email is spam or not, as well as numerical values, such as the price of a house.
What makes Decision Trees interesting is their simplicity. Their decision-making process can be represented visually, making it easier to understand how a model arrives at a prediction. But how does a machine decide which question to ask first? That is where the real learning begins.
What Is a Decision Tree?
A Decision Tree is a supervised machine learning algorithm that makes predictions by following a sequence of conditions. It represents these decisions in a tree-like structure, where each question divides the data into smaller groups until a final prediction is reached.
Think of it as a flowchart made up of questions and answers. Each question examines a feature of the data, and the answer determines which direction to follow. This process continues until the model reaches an outcome.
A Decision Tree consists of four main components: the root node, decision nodes, branches, and leaf nodes. Each component plays a specific role in moving from the initial dataset to the final prediction.
The Four Main Components of a Decision Tree
- Root Node: The starting point of the tree. It represents the entire dataset before any splitting takes place.
- Decision Node (Internal Node): A node that checks a condition or feature and divides the data based on the result.
- Branch: A connection between nodes that represents the outcome of a decision, such as Yes or No.
- Leaf Node (Terminal Node): The final node that provides the prediction. It does not split into further nodes.
These components form a hierarchical structure. A prediction starts at the root, follows the appropriate branches through decision nodes, and ends at a leaf node.
Let’s use this simple tree to understand the prediction process:
Imagine the following situation:
- We start at the root node: “Is it raining?”
- If the answer is No, the tree predicts “Play cricket.”
- If the answer is Yes, we move to another decision node: “Is the ground wet?”
- If the ground is wet, the prediction is “Stay indoors.” Otherwise, the prediction is “Play cricket.”
Notice that every possible path leads to a final outcome. This is how a Decision Tree converts a sequence of conditions into a prediction
How Does a Decision Tree Work?
A Decision Tree learns by repeatedly dividing the dataset into smaller groups based on the features that help make better predictions. At each step, it looks for a condition that separates the data into groups with more similar outcomes. This process is called recursive splitting.
The algorithm evaluates different features and possible splitting conditions using a measure such as Gini Impurity or Entropy. It selects the split that provides the best separation between classes. The same process is then repeated for each resulting group.
For example, when predicting whether a person will play cricket, the tree might first consider the weather, then check whether the ground is wet. Each decision narrows down the possibilities until a prediction can be made.
The splitting process continues until a stopping condition is reached, such as a node containing only one class, reaching the maximum tree depth, or having too few samples to split further. The final nodes become leaf nodes, where the model produces its predictions.
In simple terms, a Decision Tree follows a divide-and-conquer approach: it breaks a complex prediction problem into smaller, simpler decisions.
A Decision Tree generally follows these steps:
- Start with the entire dataset at the root node.
- Evaluate features and possible splits to find the most effective condition.
- Split the dataset into smaller groups based on that condition.
- Repeat the process recursively for each group.
- Stop splitting when a stopping condition is satisfied.
- Assign predictions to the final leaf nodes.
The key idea is that the tree does not randomly divide the data. It chooses splits based on how well they help the model distinguish between outcomes.
This leads to an important question: How does a Decision Tree measure whether one split is better than another? We will explore this through impurity and Gini Impurity in the next sections.
Understanding Impurity
Before a Decision Tree can decide how to split the data, it needs a way to measure how well the data is grouped. This is where impurity comes into the picture. Impurity measures how mixed the different classes are within a node.
Imagine a node containing 10 samples: 10 Purple samples and 0 Yellow samples. Since all samples belong to the same class, the node is considered pure. Now, imagine another node containing 5 Purple and 5 Yellow samples. Both classes are equally represented, making the node more impure.
A Decision Tree tries to create groups where samples belonging to the same class are together. These groups make predictions easier and more reliable. Therefore, during splitting, the algorithm aims to reduce impurity as much as possible.
In simple terms, the purer the groups, the easier it becomes for a Decision Tree to make a prediction. But how do we measure this impurity mathematically? One of the most commonly used methods is Gini Impurity.
Gini Impurity — Measuring How Mixed a Node Is
Once we understand impurity, the next question is: How can a Decision Tree measure it?
One commonly used method is Gini Impurity. It measures how likely a randomly selected sample would be incorrectly classified if its label were assigned based on the class distribution within that node.
In simple terms, Gini Impurity tells us how mixed the classes are. A node containing samples from only one class has zero impurity, while a node containing a mixture of classes has a higher impurity.
The Gini Impurity Formula
The formula for Gini Impurity is:
Gini = 1 — ∑ pᵢ²
Where:
- n = The total number of classes
- pᵢ = The proportion of samples belonging to class i
For a binary classification problem (for example, a dataset containing only Purple and Yellow samples), the formula expands like this:
Gini = 1 — ( p_Purple² + p_Yellow² )
To find the Gini Impurity, you simply calculate the proportion of each class, square those individual proportions, add them together, and then subtract that final total from 1.
Understanding Gini Impurity with an Example
Imagine a node containing 10 samples, divided into Purple and Yellow classes.
Case 1: A Pure Node
Suppose all 10 samples belong to the Purple class.
- Gini = 1 — ( ¹² + ⁰² )
- Gini = 0
Since every sample belongs to the exact same class, there is absolutely no impurity.
Case 2: A Completely Mixed Node
Suppose there are 5 Purple and 5 Yellow samples.
- Gini = 1 — ( 0.⁵² + 0.⁵² )
- Gini = 1–0.5
- Gini = 0.5
This represents the highest possible Gini Impurity for a binary classification problem.
Case 3: A Mostly Pure Node
Suppose there are 8 Purple and 2 Yellow samples.
- Gini = 1 — ( 0.⁸² + 0.²² )
- Gini = 1 — ( 0.64 + 0.04 )
- Gini = 0.32
The node is noticeably less impure than the balanced node because the vast majority of samples belong to the Purple class.
What Do These Values Tell Us?
- Gini Impurity = 0 : Completely pure node
- Gini Impurity = 0.32 : Mostly one class
- Gini Impurity = 0.50 : Maximum impurity for two classes
How Does Gini Impurity Help in Splitting?
A Decision Tree evaluates different possible splits and calculates the weighted Gini Impurity of the resulting child nodes.
The split that produces the lowest weighted impurity is generally preferred. This helps the algorithm create groups where samples belonging to the same class are more concentrated.
However, calculating Gini Impurity for a single node is only the beginning. To understand how a Decision Tree actually chooses the best split, let’s solve a complete example step by step.
Solving a Decision Tree Problem Step by Step
We have understood what Gini Impurity is and how it measures the mixture of classes within a node. Now, let’s see how a Decision Tree uses it to choose the best split.
Imagine we have a dataset containing 10 samples, divided into two classes: Purple and Yellow. Our goal is to separate these samples into groups that are as pure as possible.
Step 1: Calculate the Gini Impurity Before Splitting
Initially, all 10 samples belong to a single root node.
Using the Gini Impurity formula:
Gini = 1 — ( p_Purple² + p_Yellow² )
- Gini = 1 — ( 0.⁵² + 0.⁵² )
- Gini = 1 — ( 0.25 + 0.25 )
- Gini = 0.5
The root node has a Gini Impurity of 0.5, which represents the maximum possible impurity for a two-class system.
Now, let’s see whether splitting the data can reduce this impurity.
Step 2: Perform the First Split
Suppose we split the dataset into two distinct groups:
- Group 1: 4 Purple, 0 Yellow
- Group 2: 1 Purple, 5 Yellow
Notice that Group 1 is completely pure, while Group 2 contains a mixture of both classes.
Calculate Gini Impurity of Group 1
• Gini_1 = 1–(1² + 0² )
• Gini_1 = 0
All samples belong entirely to the Purple class, meaning this child node is perfectly pure.
Calculate Gini Impurity of Group 2
Group 2 contains 1 Purple and 5 Yellow samples, making a total of 6 samples.
• Gini_2 = 1 — ( 1/6 )² — ( 5/6 )²
• Gini_2 = 1 — ( 1/36 + 25/36 )
• Gini_2 = 1 — ( 26/36 )
• Gini_2 ≈ 0.2778
While Group 2 is not completely pure, it is still significantly less impure than our original root node.
Step 3: Calculate the Weighted Gini Impurity
We cannot simply take a standard average of the two Gini values because the two child nodes contain a different number of samples.
Instead, we calculate a weighted Gini Impurity, where each group’s impurity is multiplied by its overall proportion of the total dataset.
The formula is:
Gini_split = ∑ ( Nⱼ / N ) × Giniⱼ
Where:
• Nⱼ = Number of samples in child node j
• N = Total number of samples in the parent node
• Giniⱼ = Gini Impurity of child node j
For our specific split:
• Gini_split = ( 4 / 10 ) × ( 0 ) + ( 6 / 10 ) × ( 0.2778 )
• Gini_split = 0 + 0.1667
• Gini_split = 0.1667
Our dataset’s impurity has dropped dramatically from 0.5 down to 0.1667! This proves our split successfully created groups that are far more organized by class.
But is this the absolute best path? To confirm, we must compare it to alternative splitting configurations.
Step 4: Compare Another Possible Split
Suppose an alternative splitting condition produces these two groups instead:
• Group 1: 3 Purple, 2 Yellow (5 samples total)
• Group 2: 2 Purple, 3 Yellow (5 samples total)
Gini Impurity of Group 1
• Gini_1 = 1 — ( 0.6² + 0.4² )
• Gini_1 = 1 — ( 0.36 + 0.16 )
• Gini_1 = 0.48
Gini Impurity of Group 2
• Gini_2 = 1 — ( 0.4² + 0.6² )
• Gini_2 = 0.48
Calculate the Weighted Gini
• Gini_split = ( 5 / 10 ) × ( 0.48 ) + ( 5 / 10 ) × ( 0.48 )
• Gini_split = 0.24 + 0.24
• Gini_split = 0.48
This alternative split leaves us with a much higher remaining impurity than our first option.
Step 5: Select the Best Split
Let’s look at the final comparison:
• Split Option 1 (Weighted Gini): 0.1667 🏆 (Winner)
• Split Option 2 (Weighted Gini): 0.4800
The first split is decisively better because it yields the lower weighted Gini Impurity.
Get V V Srimannarayana Reddy Tetali’s stories in your inbox
Join Medium for free to get updates from this writer.
This is exactly how a Decision Tree operates under the hood. It thoroughly evaluates all available splitting thresholds and locks in the specific condition that achieves the greatest overall reduction in impurity.
Entropy and Information Gain
Gini Impurity is not the only method used by Decision Trees to measure the quality of a split. Another commonly used method is Entropy, which measures the uncertainty or disorder within a dataset.
Imagine a node containing 5 Purple and 5 Yellow samples. Since both classes are equally represented, there is greater uncertainty in predicting the class. However, if all samples belong to the same class, the uncertainty becomes zero.
Entropy helps measure this uncertainty and identify splits that make the resulting groups more certain.
Understanding Entropy
Entropy is calculated using the following formula:
Entropy = −∑ pᵢ × log₂(pᵢ)
Where:
- pᵢ = proportion of samples belonging to class i.
For a binary classification problem:
Entropy = −[pₚ × log₂(pₚ) + pᵧ × log₂(pᵧ)]
Entropy is 0 for a pure node and reaches its maximum value of 1 when two classes are equally represented.
What Is Information Gain?
Information Gain measures how much uncertainty is reduced after a split.
It is calculated by subtracting the weighted Entropy of the child nodes from the Entropy of the parent node.
Information Gain = Entropy_parent − Entropy_split
The weighted Entropy is calculated as:
Entropy_split = ∑ (Nⱼ / N) × Entropyⱼ
Let’s use our previous example:
- Parent node: 5 Purple, 5 Yellow
- Group 1: 4 Purple, 0 Yellow
- Group 2: 1 Purple, 5 Yellow
The parent Entropy is 1. Group 1 has an Entropy of 0, while Group 2 has an Entropy of approximately 0.6500.
Entropy_split = (4 / 10) × 0 + (6 / 10) × 0.6500
Entropy_split ≈ 0.3900
Therefore:
Information Gain = 1 − 0.3900 = 0.6100
This means the split reduces uncertainty by approximately 0.61 bits. A Decision Tree using Entropy prefers the split with the highest Information Gain.
Gini Impurity vs Entropy
Both methods help Decision Trees identify better splits, but they measure impurity differently.
Both methods often produce similar results. The key idea is that Gini Impurity aims to reduce class mixture, while Entropy aims to reduce uncertainty.
Why Is a Decision Tree a Greedy Algorithm?
A Decision Tree is called a greedy algorithm because it selects the best possible split at each step based on the current node. It chooses the feature and condition that provide the greatest impurity reduction, without evaluating every possible combination of future splits.
For example, imagine predicting whether a person will play cricket using features such as Weather, Temperature, and Wind. The tree evaluates these features and selects the one that produces the lowest weighted Gini Impurity for the current split. It then repeats this process for the resulting child nodes.
This approach makes the algorithm efficient. However, the best split at the current step may not lead to the best overall tree. A locally optimal decision does not always produce a globally optimal solution.
In simple terms, a Decision Tree focuses on making the best decision at the present step rather than planning the entire tree in advance.
Classification vs Regression Trees
Decision Trees can solve two types of supervised learning problems: classification and regression. The main difference is the type of output they predict. Classification predicts a category, while regression predicts a numerical value.
Classification Trees
A Classification Tree predicts discrete categories or class labels. It splits the data based on features that help separate different classes.
For example, a Decision Tree can predict whether an email is Spam or Not Spam, or whether a patient has a particular disease. To select the best split, classification trees commonly use Gini Impurity or Entropy.
At the leaf node, the tree generally predicts the majority class among the training samples that reach that node.
Regression Trees
A Regression Tree predicts continuous numerical values. Instead of separating samples into classes, it divides the data into groups with similar target values.
For example, a Regression Tree can predict house prices based on features such as area, location, and number of bedrooms. It commonly uses Mean Squared Error (MSE) or variance reduction to select splits that make the target values within each group more similar.
The prediction at a leaf node is typically the average target value of the training samples that reach it.
Classification vs Regression
Although their outputs differ, both types follow the same basic process: split the data into smaller groups, evaluate the quality of each split, and continue until a stopping condition is reached.
Overfitting in Decision Trees
A Decision Tree can become too complex when it continues splitting the data into very small groups. Instead of learning general patterns, it may start memorizing individual examples and even the noise in the training dataset.
This is called overfitting.
For example, a tree predicting whether a student passes an exam may initially use meaningful features such as study hours and attendance. But an overfitted tree might create many extra rules based on small differences in the training data.
An overfitted tree often shows:
- High training accuracy: It performs very well on the data used to train it.
- Low test accuracy: It performs poorly on new, unseen data.
- Complex structure: It may have too many branches and leaves.
The main goal of a Decision Tree is not to memorize the training data, but to learn patterns that can make reliable predictions on new data.
Preventing Overfitting — Pruning and Tree Constraints
To prevent overfitting, we need to control how complex a Decision Tree can become. This can be done by limiting its growth or removing unnecessary branches.
1. Tree Depth (max_depth)
Tree depth controls the maximum number of levels a tree can grow.
A shallow tree is simpler and easier to understand, while a very deep tree can create detailed rules and may overfit.
For example:
max_depth = 3: The tree can grow only up to 3 levels.max_depth = 10: The tree can learn more detailed patterns but may become more complex.
2. Minimum Samples per Split (min_samples_split)
This parameter specifies the minimum number of samples a node must contain before it can be split.
If the value is set higher, fewer nodes are eligible for splitting, which helps keep the tree simpler.
For example, if min_samples_split = 10, a node must contain at least 10 samples to be split.
3. Minimum Samples per Leaf (min_samples_leaf)
This parameter specifies the minimum number of samples that must remain in each leaf node.
It prevents the tree from creating leaves that contain only one or a few samples.
For example, if min_samples_leaf = 5, every leaf must contain at least 5 samples. This can reduce the effect of individual training examples and improve generalization.
Pre-Pruning and Post-Pruning
Pruning is a technique used to reduce the complexity of a Decision Tree.
Pre-pruning (Early Stopping)
Pre-pruning stops the tree from growing too much during training. Parameters such as max_depth, min_samples_split, and min_samples_leaf are used to control its growth.
Post-pruning
Post-pruning allows the tree to grow first and then removes branches that do not contribute enough to its predictive performance. This helps simplify an already-trained tree.
Both techniques aim to create a tree that is simple enough to avoid memorizing the training data, but complex enough to learn useful patterns.
Key takeaway: A deeper tree is not always a better tree. Controlling tree complexity helps balance training performance and the ability to generalize to unseen data.
Advantages of Decision Trees
1. Easy to Understand and Interpret
Decision Trees make predictions using clear rules. We can follow the path from the root node to the leaf node and understand how the model reached its prediction.
2. Minimal Data Preprocessing
Unlike many algorithms, Decision Trees generally do not require feature scaling or normalization. They can work with numerical and categorical features, although categorical data may need encoding depending on the implementation.
3. Capture Nonlinear Relationships
Decision Trees can learn complex patterns and nonlinear relationships between features and the target variable. They do not require the relationship to follow a straight line.
4. Useful for Classification and Regression
A Decision Tree can predict categories, such as spam or not spam, as well as continuous values, such as house prices.
5. Handle Different Types of Features
Decision Trees can work with both numerical and categorical features, making them useful for many real-world datasets.
Disadvantages of Decision Trees
1. Prone to Overfitting
A tree can grow too deep and memorize the training data. This may result in high training accuracy but poor performance on unseen data.
2. Sensitive to Small Changes in Data
A small change in the training dataset can sometimes lead to a completely different tree structure. This makes individual Decision Trees less stable.
3. Can Be Biased Toward Majority Classes
When the dataset is imbalanced, a Decision Tree may favor the majority class and perform poorly on the minority class. Techniques such as class weights or resampling can help address this issue.
4. Greedy Approach
A Decision Tree selects the best split at each step based on the current data. It does not evaluate every possible tree structure, so a locally good split may not lead to the globally best tree.
5. May Become Complex and Less Interpretable
Although small trees are easy to understand, very deep trees with many branches can become difficult to interpret.
When to Use Decision Trees and Their Real-World Applications
Decision Trees are useful when we need a model that is easy to understand, can capture nonlinear patterns, and makes predictions using a sequence of rules.
They are especially suitable for structured or tabular data, where features describe records such as customers, patients, loans, or crops.
When Are Decision Trees a Good Choice?
Decision Trees are a good choice when:
- Interpretability is important and we need to explain how a prediction was made.
- The dataset contains nonlinear relationships.
- We want a model that requires relatively little preprocessing.
- The problem involves classification or regression.
- We need a simple baseline model before trying more complex algorithms.
However, another algorithm may be more suitable in some situations:
- Linear Regression or Logistic Regression: When the relationship is relatively simple and a more stable, interpretable model is preferred.
- Random Forest or Gradient Boosting: When predictive performance is more important and a single tree is not accurate or stable enough.
- Neural Networks: When working with complex data such as images, audio, or large-scale unstructured data.
The best algorithm depends on the dataset, the problem, and the evaluation metric.
Real-World Applications of Decision Trees
1. Healthcare Diagnosis
Decision Trees can help classify patients based on symptoms, test results, and medical history. For example, a model may predict whether a patient is at a higher risk of a particular disease.
They can support clinical decision-making, but should not replace professional medical judgment.
2. Loan Approval
Banks and financial institutions can use Decision Trees to assess loan applications using features such as income, credit score, existing debt, and repayment history.
The tree can learn rules that help classify applications as lower or higher risk. Real loan decisions must also consider fairness and regulatory requirements.
3. Customer Churn Prediction
Businesses use Decision Trees to predict whether a customer is likely to stop using a service.
Features may include customer tenure, monthly charges, complaints, and usage patterns. The results can help businesses identify customers who may need additional support or retention offers.
4. Fraud Detection
Decision Trees can identify potentially fraudulent transactions using features such as transaction amount, location, frequency, and unusual activity.
Since fraud datasets are often imbalanced, the model should be evaluated using suitable metrics such as precision, recall, and F1-score — not accuracy alone.
5. Agriculture
Decision Trees can support agricultural decisions using features such as soil type, rainfall, temperature, humidity, and nutrient levels.
Applications include crop recommendation, disease classification, and predicting whether conditions are suitable for a particular crop.
Beyond a Single Decision Tree: Ensemble Algorithms
A single Decision Tree is easy to interpret, but it may be unstable or less accurate. Ensemble learning combines multiple models to improve prediction.
Two popular tree-based ensemble algorithms are:
- Random Forest
Random Forest builds many Decision Trees using different samples of the training data and different subsets of features. Their predictions are combined — through voting for classification or averaging for regression.
This usually makes the model more stable and reduces overfitting compared with a single tree.
2. Gradient Boosting
Gradient Boosting builds trees sequentially. Each new tree focuses on correcting errors made by the previous trees. The combined model gradually improves its predictions.
Popular implementations include XGBoost, LightGBM, and CatBoost.
Conclusion
Every Decision Begins with the Right Question
Decision Trees learn by recursively splitting data into smaller groups based on features. They use impurity measures such as Gini Impurity and Entropy to identify better splits and make predictions.
Their greedy approach selects the best split at each step, making learning efficient. However, growing a tree too deep can lead to overfitting, where the model memorizes training data instead of learning general patterns. Pruning and tree constraints help control this complexity.
Ultimately, a good Decision Tree is not the deepest or the one with perfect training accuracy. It is the one that balances simplicity, interpretability, and predictive performance.
Every decision begins with the right question — but a good model knows when to stop asking.
