Decision Tree

1 What is a Decision Tree?

A Decision Tree is a supervised machine learning algorithm used for:

✅ Classification → Output is a category (Yes/No, 0/1, Pass/Fail)

✅ Regression → Output is a continuous value (price, marks, salary)

It works like a flowchart, where:

 Each question is a decision

 Each branch is an outcome
 Each leaf node is the final prediction

2 Simple Real-Life Idea

Think of how humans take decisions

“Should I approve a loan?”

You don’t decide randomly.

You check:
  Age
 Income
 Job stability

Decision Tree does exactly the same, but mathematically.

3 Structure of a Decision Tree

Term Meaning
Root Node First decision (main question)
Internal Node Intermediate decision
Branch Result of a decision
Leaf Node Final output (prediction)

4 Example 1: Loan Approval (Classification)

Problem

Will the bank approve the loan?

Output: Approve or Reject

Features (Inputs)

 Age
 Income
 Credit Score

Decision Flow

Is Age > 30?

├── Yes → Is Income > 50k?
│ ├── Yes → Loan Approved
│ └── No → Loan Rejected
└── No → Loan Rejected
Why this works?

 Each question splits the data

 At each step, data becomes more pure

5 Example 2: Disease Prediction (Classification)

Problem

Does the patient have diabetes?

Features

 Glucose level
 BMI
 Age

Flow

Is Glucose > 140?

├── Yes → Is BMI > 30?
│ ├── Yes → Diabetes
│ └── No → No Diabetes
└── No → No Diabetes

✔ Final output is class label → Yes / No

6 Example 3: House Price Prediction (Regression)

Here output is a number, not a class.

Features

 Area ([Link])
 Location
 Number of rooms
Flow

Is Area > 1200?

├── Yes → Price = ₹80 Lakhs
└── No → Price = ₹50 Lakhs

✔ Leaf node gives a numerical value

7 How Does a Decision Tree Decide the Best Split?

This is where important concepts come in 👇

A. Entropy (Classification)

Entropy measures impurity / randomness

Formula

Entropy(S) = − Σ pᵢ log₂(pᵢ)

Where:

pᵢ = proportion of class i in dataset S

Special cases:

Entropy = 0 → Pure node

Entropy = 1 → Impure node (binary classification)

 Entropy = 0 → Pure data

 Entropy = 1 → Mixed data

Example

If all loans are approved, entropy = 0

If 50% approved, 50% rejected → entropy is high
B. Information Gain (Classification)

Information Gain tells:

“Which question gives the best split?”

Formula

Information Gain(S, A) =
Entropy(S) − Σ ( |Sᵥ| / |S| ) × Entropy(Sᵥ)

Where:

S = parent dataset
A = attribute used for split
Sᵥ = subset after split
|S| = total samples

✔ Decision Tree chooses the split with highest information gain

C. Gini Index (Classification – CART)

Used instead of entropy in many libraries.

Formula

Gini(S) = 1 − Σ (pᵢ)²

Where:

pᵢ = probability of class i

Special cases:

Gini = 0 → Pure node

Higher Gini → More impurity
  Gini = 0 → Pure
 Lower Gini → Better split

Gini Index for Split

Gini_split = Σ ( |Sᵢ| / |S| ) × Gini(Sᵢ)

Decision rule:

Choose split with MINIMUM Gini_split

CART algorithm uses Gini Index

D. Variance Reduction (Regression)

Used in Decision Tree Regression

Goal:

Reduce variance in output values after split

The best split minimizes:

Variance (Regression Tree)

Variance = (1 / n) × Σ (yᵢ − ȳ)²

Where:

yᵢ = actual output value

ȳ = mean of output values
n = number of samples

Variance Reduction

Variance Reduction =
Variance(parent) − Σ ( |Sᵢ| / |S| ) × Variance(Sᵢ)
Decision rule:

Choose split with MAXIMUM Variance Reduction

8 Important Types of Decision Trees

1 Classification Tree

 Output → Class
 Uses → Entropy / Gini

Examples:

 Spam vs Not Spam

 Disease Yes/No

2 Regression Tree

 Output → Continuous value

 Uses → Variance reduction

Examples:

 House price
 Salary prediction

9 Overfitting in Decision Trees 🚨

What is Overfitting?

Tree becomes too deep, memorizes data.

Symptoms:

 Very high training accuracy

 Poor test accuracy
Solution: Pruning

A. Pre-Pruning

 Limit tree depth

 Minimum samples per node

B. Post-Pruning

 Grow full tree

 Remove unnecessary branches

🔟 Advantages of Decision Tree

✔ Easy to understand
✔ Visual & interpretable
✔ No scaling required
✔ Handles non-linear data
✔ Works with numerical + categorical data

11 Disadvantages

❌ Overfitting
❌ Sensitive to small data changes
❌ Less accurate than ensemble models

12 Algorithms Based on Decision Tree

 Algorithm Uses
ID3 Entropy
C4.5 Entropy + pruning
CART Gini + regression
Random Forest Multiple decision trees
Gradient Boosting Sequential trees

Random Forest & XGBoost are built on decision trees.

13 Simple Python Example (Classification)

from [Link] import DecisionTreeClassifier

X = [[25, 30000], [40, 70000], [35, 60000], [22,

20000]]
y = [0, 1, 1, 0] # 0 = Reject, 1 = Approve

model = DecisionTreeClassifier()
[Link](X, y)

print([Link]([[38, 65000]])) # Output: 1

(Approve)
Decision Tree Concepts Explanation :

Entropy — Explained Clearly with Example

1 What is Entropy?

Entropy is a measure of impurity or randomness in a dataset.

In Decision Trees, entropy answers this question:

❓ How mixed are the classes in this node?

 Low entropy → Data is mostly one class (pure)

 High entropy → Data is mixed (impure)

👉 Decision Trees try to reduce entropy at each split.

2 Where is Entropy Used?

✔ Used in ID3 and C4.5 algorithms

✔ Used for classification problems only
✔ Helps compute Information Gain

3 Entropy Formula

Entropy(S) = − Σ ( p_i × log2(p_i) )

Where:

S = dataset or node
p_i = probability of class i

4 Simple Intuition (Real-Life)

Imagine a bag of balls:

Balls in Bag Entropy

All red 0 (pure)

 Balls in Bag Entropy

50% red, 50% blue High

Mostly red, few blue Medium

5 Example 1: Pure Node (Entropy = 0)

Dataset

Approved = 10
Rejected = 0

Calculation

p(Approve) = 1
p(Reject) = 0
Entropy = − [ p(Approve) × log2(p(Approve))
+ p(Reject) × log2(p(Reject)) ]

Substituting values:

Entropy = − [ 1 × log2(1) + 0 × log2(0) ]

Since:

log2(1) = 0
0 × log2(0) = 0
Entropy = − (0 + 0)
Entropy = 0

📝 One-Line Interpretation (Exam Ready)

When all samples belong to one class, entropy is 0,

indicating a perfectly pure node.

📌 Interpretation:
Node is perfectly pure → No need to split further.
6 Example 2: Mixed Node (High Entropy)

Dataset

Approved = 5
Rejected = 5

Calculation

Entropy Calculation (Completely Impure Node)

p(Approve) = 0.5
p(Reject) = 0.5
Entropy = − [ p(Approve) × log2(p(Approve))
+ p(Reject) × log2(p(Reject)) ]

Substituting values:

Entropy = − [ 0.5 × log2(0.5) + 0.5 × log2(0.5) ]

Since:

log2(0.5) = −1
Entropy = − [ 0.5 × (−1) + 0.5 × (−1) ]
Entropy = − ( −0.5 − 0.5 )
Entropy = − ( −1 )
Entropy = 1

📝 One-Line Interpretation (Exam Ready)

When both classes are equally distributed, entropy is

maximum (1), indicating complete uncertainty.

📌 Interpretation:
Maximum uncertainty → Best candidate for splitting.
7 Example 3: Partially Mixed Node

Dataset

Approved = 8
Rejected = 2

Calculation

Entropy Calculation (Partially Impure Node)

p(Approve) = 0.8
p(Reject) = 0.2
Entropy = − [ p(Approve) × log2(p(Approve))
+ p(Reject) × log2(p(Reject)) ]

Substituting values:

Entropy = − [ 0.8 × log2(0.8) + 0.2 × log2(0.2) ]

Using logarithm values:

log2(0.8) ≈ −0.322
log2(0.2) ≈ −2.322

Now calculate:

Entropy = − [ 0.8 × (−0.322) + 0.2 × (−2.322) ]

Entropy = − ( −0.2576 − 0.4644 )
Entropy = − ( −0.722 )
Entropy ≈ 0.72

📝 One-Line Interpretation (Exam Ready)

When most samples belong to one class but some belong

to another, entropy is less than 1, indicating pa

📌 Interpretation:
Some impurity → Tree may still split.
8 Why Decision Tree Uses Entropy?

Decision Tree asks:

Which feature reduces entropy the most?

This reduction is called Information Gain.

Higher Entropy → Split needed

Lower Entropy → Node is pure

9 Entropy in Decision Tree (Flow Example)

Root Node (Entropy = 1)

│
├── Split on Age
│ ├── Low Entropy → Stop
│ └── High Entropy → Split Again

🔟 Simple Python Code Example

import math

def entropy(yes, no):

total = yes + no
p_yes = yes / total
p_no = no / total

ent = 0
if p_yes != 0:
ent -= p_yes * math.log2(p_yes)
if p_no != 0:
ent -= p_no * math.log2(p_no)

return ent

print("Entropy (5 Yes, 5 No):", entropy(5, 5))

print("Entropy (8 Yes, 2 No):", entropy(8, 2))
print("Entropy (10 Yes, 0 No):", entropy(10, 0))
11 SUMMARY

Entropy is a measure of impurity or randomness used in decision tree algorithms

like ID3 and C4.5. It quantifies how mixed the class labels are in a dataset. Lower
entropy indicates a pure node, while higher entropy indicates greater uncertainty.
Decision trees aim to reduce entropy at each split to create accurate classification
models.

ENTROPY – FORMULAS

1 General Entropy Formula

Entropy(S) = − Σ ( p_i × log2(p_i) )

Where:

S = dataset or node
p_i = probability of class i

2 Binary Classification Entropy

Entropy(S) = − [ p(Yes) × log2(p(Yes)) + p(No) ×

log2(p(No)) ]

3 Probability Calculation

p(Class) = Number of samples in that class / Total

samples

4 Special Cases

Pure Node

p = 1 or p = 0
Entropy = 0
Completely Impure Node (Binary)

p = 0.5 , 0.5
Entropy = 1

5 Entropy Range

0 ≤ Entropy ≤ 1

6 Example (Text Calculation)

Approved = 8
Rejected = 2
Total = 10

p(Approved) = 8/10 = 0.8

p(Rejected) = 2/10 = 0.2

Entropy = − (0.8 × log2(0.8) + 0.2 × log2(0.2))

Entropy ≈ 0.72

ONE-LINE

Entropy is a measure of impurity or randomness used in

decision trees to select the best feature for
INFORMATION GAIN – FORMULA

1 Information Gain Formula

Information Gain(S, A) =
Entropy(S) − Σ ( |S_v| / |S| ) × Entropy(S_v)

Where:

S = Parent dataset
A = Attribute used for split
S_v = Subset of S after split on attribute A
|S| = Total number of samples
|S_v| = Number of samples in subset S_v

GINI INDEX – FORMULA (TEXT FORMAT)

2 Gini Index Formula

Gini(S) = 1 − Σ (p_i)²

Where:

p_i = Probability of class i

Gini Index for a Split

Gini_split = Σ ( |S_i| / |S| ) × Gini(S_i)

Decision Rule:

Choose the split with MINIMUM Gini_split

NUMERICAL SOLVED EXAMPLES (STEP-BY-STEP)

✅ Example 1: Information Gain (Loan Approval)

Dataset

Total samples = 10
Approved = 5
Rejected = 5

Step 1: Parent Entropy

p(Approve) = 5/10 = 0.5

p(Reject) = 5/10 = 0.5
Entropy(S) = − (0.5 log2 0.5 + 0.5 log2 0.5)
Entropy(S) = 1

Step 2: Split on "Income"

High Income Group

Approved = 4
Rejected = 1
Total = 5
Entropy(High) =
− (4/5 log2 4/5 + 1/5 log2 1/5)
Entropy(High) ≈ 0.72

Low Income Group

Approved = 1
Rejected = 4
Total = 5
Entropy(Low) =
− (1/5 log2 1/5 + 4/5 log2 4/5)
Entropy(Low) ≈ 0.72

Step 3: Weighted Entropy

Weighted Entropy =
(5/10 × 0.72) + (5/10 × 0.72)
= 0.72

Step 4: Information Gain

Information Gain =
Entropy(parent) − Weighted Entropy
= 1 − 0.72
= 0.28

📝 Conclusion

Information Gain for Income = 0.28

✅ Example 2: Gini Index (Same Dataset)

Step 1: Parent Gini Index

p(Approve) = 0.5
p(Reject) = 0.5
Gini(parent) =
1 − (0.5² + 0.5²)
= 1 − (0.25 + 0.25)
= 0.5

Step 2: Gini for High Income Group

p(Approve) = 4/5 = 0.8

p(Reject) = 1/5 = 0.2
Gini(High) =
1 − (0.8² + 0.2²)
= 1 − (0.64 + 0.04)
= 0.32

Step 3: Gini for Low Income Group

p(Approve) = 1/5 = 0.2
p(Reject) = 4/5 = 0.8
Gini(Low) =
1 − (0.2² + 0.8²)
= 1 − (0.04 + 0.64)
= 0.32

Step 4: Gini Index for Split

Gini_split =
(5/10 × 0.32) + (5/10 × 0.32)
= 0.32

📝 Conclusion

Lower Gini = Better split

🎯 EXAM-READY ONE-LINE SUMMARY

Information Gain measures reduction in entropy,

Gini Index measures impurity,
Decision Trees choose the split with maximum
Information Gain or minimum Gini Index.

NUMERICAL COMPARISON: ENTROPY vs GINI INDEX

📌 Given Dataset (Binary Classification)

Total samples = 10
Approved = 8
Rejected = 2
p(Approve) = 8/10 = 0.8
p(Reject) = 2/10 = 0.2

1ENTROPY CALCULATION

Formula (Text Format)

Entropy(S) = − [ p(Approve) × log2(p(Approve))

+ p(Reject) × log2(p(Reject)) ]

Substituting Values

Entropy(S) = − [ 0.8 × log2(0.8) + 0.2 × log2(0.2) ]

Using logarithm values:

log2(0.8) ≈ −0.322
log2(0.2) ≈ −2.322
Entropy(S) = − [ 0.8 × (−0.322) + 0.2 × (−2.322) ]
Entropy(S) = − ( −0.2576 − 0.4644 )
Entropy(S) ≈ 0.72

2 GINI INDEX CALCULATION

Formula (Text Format)

Gini(S) = 1 − [ p(Approve)² + p(Reject)² ]

Substituting Values

Gini(S) = 1 − (0.8² + 0.2²)

Gini(S) = 1 − (0.64 + 0.04)
Gini(S) = 1 − 0.68
Gini(S) = 0.32

3 SIDE-BY-SIDE NUMERICAL COMPARISON

Metric Formula Used Value

Entropy −Σ p log2(p) ≈ 0.72

Gini Index 1 − Σ p² 0.32

4 SPECIAL CASE COMPARISON (FOR EXAMS)

Pure Node

p = 1 , 0
Entropy = 0
Gini = 0

Completely Impure Node

p = 0.5 , 0.5
Entropy = 1
Gini = 0.5

5 KEY OBSERVATIONS (VERY IMPORTANT)

• Entropy uses logarithms → computationally heavier

• Gini uses squares → faster computation
• Both measure impurity
• Both give similar split decisions

6 WHEN TO USE WHICH?

 Entropy Gini

Used in ID3, C4.5 Used in CART

More sensitive to changes Faster

Theoretically sound Practically preferred

SUMMARY

Entropy and Gini Index are impurity measures used in decision trees. For a dataset
with probabilities 0.8 and 0.2, entropy is approximately 0.72 while Gini Index is
0.32. Entropy uses logarithmic calculations and is computationally expensive,
whereas Gini Index uses squared probabilities and is faster. Both measures aim to
create purer splits, and often lead to similar decisions.
 Important Types of Decision Trees

1 Classification Tree

What is a Classification Tree?

A Classification Tree is used when the output (target) is a category / class, such
as:

 Yes / No
 0/1
 Spam / Not Spam
 Disease / No Disease

The tree’s leaf node always gives a CLASS LABEL, not a number.

Concepts Used

 Entropy (ID3, C4.5)

 Gini Index (CART – most common)

Purpose:
To create pure nodes where most data belongs to one class.

Example Problem: Spam Detection

Question: Is an email spam or not?

 1 → Spam
 0 → Not Spam
Code Example: Classification Tree (CART – Gini)

from [Link] import DecisionTreeClassifier

from sklearn.model_selection import train_test_split
from [Link] import accuracy_score

# Example dataset
# Features: [email_length, number_of_links]
X = [
[200, 1],
[1200, 10],
[300, 0],
[1500, 15],
[100, 0],
[900, 8]
]

# Target: 1 = Spam, 0 = Not Spam

y = [0, 1, 0, 1, 0, 1]

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

# Create Classification Tree

model = DecisionTreeClassifier(criterion="gini")
[Link](X_train, y_train)

# Prediction
y_pred = [Link](X_test)

print("Predictions:", y_pred)
print("Accuracy:", accuracy_score(y_test, y_pred))

What is Happening Internally?

1. CART checks all features

2. Tries all possible binary splits
3. Calculates Gini Index
 4. Chooses split with minimum Gini
5. Repeats until leaf node is pure

Why Use Classification Tree?

✔ Easy to understand
✔ Works well for Yes/No decisions
✔ Highly interpretable for business

2 Regression Tree

🔹 What is a Regression Tree?

A Regression Tree is used when the output is a continuous numerical value,

such as:

 House price
 Salary
 Marks
 Temperature

👉 The leaf node stores a NUMBER (mean value).

🔹 Concept Used

 Variance
 Variance Reduction

📌 Goal:
Split data so that output values in each node are close to each other.
🔹 Example Problem: House Price Prediction

🔹 Code Example: Regression Tree

from [Link] import DecisionTreeRegressor

from sklearn.model_selection import train_test_split
from [Link] import mean_squared_error

# Feature: House area ([Link])

X = [[800], [1000], [1200], [1500], [1800], [2000]]

# Target: House price (in lakhs)

y = [40, 50, 55, 80, 90, 110]

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

# Create Regression Tree

model = DecisionTreeRegressor()
[Link](X_train, y_train)

# Prediction
y_pred = [Link](X_test)

print("Predicted Prices:", y_pred)

print("MSE:", mean_squared_error(y_test, y_pred))

🔹 What is Happening Internally?

1. CART calculates variance at parent node

2. Tries all splits
3. Calculates variance after split
4. Chooses split with maximum variance reduction
5. Leaf node predicts mean value
🔹 Why Use Regression Tree?

✔ Handles non-linear relationships

✔ No feature scaling needed
✔ Easy to explain predictions

3 Overfitting in Decision Trees 🚨

🔹 What is Overfitting?

Overfitting happens when:

The tree becomes too deep and memorizes training data instead of learning
patterns.

🔹 Symptoms of Overfitting

✔ Very high training accuracy

❌ Very poor test accuracy

🔹 Code Example: Overfitting vs Controlled Tree

❌ Overfitted Tree

model = DecisionTreeClassifier()
[Link](X_train, y_train)

print("Training Accuracy:", [Link](X_train,

y_train))
print("Test Accuracy:", [Link](X_test, y_test))
➡ Often:

Training Accuracy = 1.0 (100%)

Test Accuracy = Low

✅ Controlled Tree (Pruning Applied)

model = DecisionTreeClassifier(
max_depth=3,
min_samples_split=2
)

[Link](X_train, y_train)

print("Training Accuracy:", [Link](X_train,

y_train))
print("Test Accuracy:", [Link](X_test, y_test))

🔹 Why This Works?

 max_depth → stops tree from growing too deep

 min_samples_split → avoids unnecessary splits
 Improves generalization

🔟 Final Comparison (Easy Revision)

Tree Type Output Concept Used Algorithm

Classification Tree Class Entropy / Gini ID3 / CART
Regression Tree Number Variance CART
Overfitting Control — Pruning CART
One-Line Teaching Summary

Classification Trees predict classes using impurity measures, Regression Trees

predict numbers using variance reduction, and overfitting is controlled using
pruning.
What is a Decision Tree?
A Decision Tree is a machine learning algorithm that makes decisions by splitting
data into branches based on questions (conditions).

Think of it as a flowchart that leads you to a final decision.

Each part of the tree has a role:

 Root Node → First question

 Internal Nodes → Middle questions
 Leaf Nodes → Final prediction
 Branches → Outcomes of questions

🎯 Simple Real-Life Example (Very Easy)

Problem:
You want to decide whether to post a new Instagram Reel today.

Decision Tree Logic:

1. Is today a weekend?
o Yes → Post (more people online)
o No → Ask next question
2. Is engagement usually high today?
o Yes → Post
o No → Don't post

This can be shown as:

🌳 Decision Tree Diagram (Simple)

Here is a diagram using text blocks:

[Is Today Weekend?]

/ \
Yes No
 (Leaf) [Is Engagement
High?]
Post Reel / \
Yes No
| |
(Leaf) Post (Leaf)
Don't Post

This is exactly how machine learning decision trees operate — by asking yes/no or
numeric threshold questions.

🤖 ML Example: Predict Instagram Reach Using Decision Tree

Suppose your dataset has:

 likes
 comments
 shares
 saves
 impressions

A decision tree may learn rules like:

Example Splits:

if shares > 50:

predict reach = 30,000
else:
if likes > 800:
predict reach = 15,000
else:
predict reach = 2,000
This becomes a tree structure:
[shares > 50?]
/ \
Yes No
reach = 30000 [likes > 800?]
/ \
Yes No
reach = 15000 reach = 2000

🧠 How Does the Decision Tree Learn?

The algorithm tries to split the data such that each branch contains similar
outcomes.

To do this, it uses criteria like:

For Classification:

 Gini Impurity
 Entropy

For Regression:

 MSE (Mean Squared Error) reduction

The tree keeps splitting until:

 Maximum depth is reached

 No better splits are found
 Data becomes pure (all have similar values)

⭐ Advantages of Decision Trees

✔ Very easy to understand

✔ Looks like human decision-making
✔ Works with numeric + categorical data
✔ Supports both Regression and Classification
✔ No data scaling required
⚠ Limitations

❌ Overfits easily (memorizes data)

❌ Small changes in data can change the structure
❌ Less accurate than Random Forest

This is why Random Forest (many trees combined) is more powerful.

📝 Example Code (Regression Decision Tree)

from [Link] import DecisionTreeRegressor

from sklearn.model_selection import train_test_split
import pandas as pd

df = pd.read_csv("Instagram_data_by_Bhanu.csv")

X =
df[['likes','comments','shares','saves','impressions']]
y = df['reach']

X_train, X_test, y_train, y_test = train_test_split(X,

y, test_size=0.2, random_state=42)

model = DecisionTreeRegressor(max_depth=4)
[Link](X_train, y_train)

print("Prediction for sample:", [Link]([[500,

30, 40, 20, 8000]]))
Diagram (ASCII Visual Representation)

Here is a full regression-style decision tree diagram:

[impressions > 10000?]

/ \
Yes No
[shares > 40?] [likes > 500?]
/ \ / \
Yes No Yes No
[saves > 20?] reach = 12000 reach = 8000 reach = 2000
/ \
Yes No
reach=35000 reach=25000

This shows how the model splits based on conditions to reach a prediction.

🎓 In One Simple Line:

A Decision Tree is a flowchart-like model that predicts outcomes by asking a

series of if–else questions.