Decision Tree in Machine Learning -ID3 Algorithm

 

🌳 Decision Tree in Machine Learning

A Decision Tree is a supervised learning algorithm used for classification and regression. It works like a flowchart:

  • Each internal node → a test on a feature (e.g., “Is age > 30?”)
  • Each branch → outcome of the test
  • Each leaf node → final prediction (class label or value)



Example:


Pic courtesy: geeksforgeeks

🔹 Simple Intuition

Think of it like asking questions:

“Is it raining?”
→ Yes → “Carry umbrella”
→ No → “No umbrella”

The model keeps splitting data based on questions until it reaches a decision.

🔹 Key Terms

  • Root Node: Topmost node (entire dataset)
  • Splitting: Dividing data into subsets
  • Decision Node: A node where a split happens
  • Leaf Node: Final output
  • Depth: Length of the longest path from root to leaf

🔹 How Decision Trees Work

  1. Start with the full dataset
  2. Choose the best feature to split the data
  3. Divide dataset into subsets
  4. Repeat recursively for each subset
  5. Stop when:
    • All data in a node belongs to one class, OR
    • No features remain, OR
    • Stopping condition is met (like max depth)

📊 Entropy (Measure of Impurity)

Decision trees need a way to measure how “mixed” the data is.

H(S)=−∑i=1cpilog⁡2piH(S) = - \sum_{i=1}^{c} p_i \log_2 p_i

Interpretation:

  • Entropy = 0 → Pure (all same class)
  • High entropy → Mixed classes

Given Dataset

X={a,a,a,b,b,b,b,b}X = \{a, a, a, b, b, b, b, b\}
  • Total instances = 8
  • Instances of aa = 3
  • Instances of bb = 5

Step 1: Compute Probabilities

P(a)=38=0.375P(a) = \frac{3}{8} = 0.375P(b)=58=0.625P(b) = \frac{5}{8} = 0.625

Step 2: Entropy Formula

H(X)=−[(38)log⁡2(38)+(58)log⁡2(58)]H(X) = - \left[ \left(\frac{3}{8}\right) \log_2 \left(\frac{3}{8}\right) + \left(\frac{5}{8}\right) \log_2 \left(\frac{5}{8}\right) \right]

Step 3: Substitute Values

H(X)=−[0.375⋅log⁡2(0.375)+0.625⋅log⁡2(0.625)]=0.954H(X) = - \left[ 0.375 \cdot \log_2(0.375) + 0.625 \cdot \log_2(0.625) \right]

📈 Information Gain

This tells us how good a split is.

Information Gain=Entropy before split−Entropy after split\text{Information Gain} = \text{Entropy before split} - \text{Entropy after split}
  • Higher gain → Better split
  • Goal → Reduce uncertainty


🌲 ID3 Algorithm (Iterative Dichotomiser 3)

The ID3 algorithm is one of the earliest methods to build decision trees. It uses Information Gain to decide splits.

🔹 Steps of ID3

1. Start with Dataset SS

Treat the entire dataset as the root node.

2. Compute Entropy of SS

Use entropy formula to measure impurity.

3. For Each Attribute AA

  • Split dataset based on values of AA
  • Compute weighted entropy
Remainder(S,A)=∑v∈Values(A)∣Sv∣∣S∣⋅H(Sv)\text{Remainder}(S, A) = \sum_{v \in \text{Values}(A)} \frac{|S_v|}{|S|} \cdot H(S_v)

4. Compute Information Gain

Gain(S,A)=H(S)−Remainder(S,A)\text{Gain}(S, A) = H(S) - \text{Remainder}(S, A)

5. Choose Best Attribute

  • Select attribute with maximum Information Gain
  • Make it the decision node

6. Split the Dataset

Create branches for each value of the chosen attribute.

7. Repeat Recursively

Apply the same process to each subset.

8. Stopping Conditions

Stop when:

  • All examples belong to same class
  • No attributes left
  • Dataset is empty

🔍 Example (Simple)

🌳 Dataset

We want to predict Play (Yes/No) using two features:

Outlook    Wind    Play
Sunny    Weak    No
Sunny    Strong    No
Overcast    Weak    Yes
Rain    Weak    Yes
Rain    Strong    No

🔹 Step 1: Compute Parent Entropy H(S)

  • Total = 5
  • Yes = 2
  • No = 3
P(Yes)=25=0.4,P(No)=35=0.6P(Yes)=\frac{2}{5}=0.4,\quad P(No)=\frac{3}{5}=0.6

H(S)=−[0.4log⁡2(0.4)+0.6log⁡2(0.6)]H(S) = -[0.4\log_2(0.4) + 0.6\log_2(0.6)]

H(S)≈0.971H(S) \approx 0.971

🔹 Step 2: Try Split on Outlook

Subsets:

🌞 Sunny → (No, No)

Entropy = 0 (pure)

☁️ Overcast → (Yes)

Entropy = 0 (pure)

🌧️ Rain → (Yes, No)

H(Rain)=−[0.5log⁡2(0.5)+0.5log⁡2(0.5)]=1H(Rain) = -[0.5\log_2(0.5) + 0.5\log_2(0.5)] = 1

🔹 Weighted Entropy (Outlook)

Remainder=25(0)+15(0)+25(1)=0.4\text{Remainder} = \frac{2}{5}(0) + \frac{1}{5}(0) + \frac{2}{5}(1) = 0.4

🔹 Information Gain (Outlook)

Gain(Outlook)=0.971−0.4=0.571Gain(Outlook) = 0.971 - 0.4 = 0.571

🔹 Step 3: Try Split on Wind

Subsets:

Weak → (No, Yes, Yes)

  • Yes = 2, No = 1
H(Weak)=−[1/3log⁡2(1/3)+2/3log⁡2(2/3)]H(Weak) = -[1/3\log_2(1/3) + 2/3\log_2(2/3)] 
H(Weak)≈0.918H(Weak) \approx 0.918

Strong → (No, No)

Entropy = 0

🔹 Weighted Entropy (Wind)

Remainder=35(0.918)+25(0)=0.551\text{Remainder} = \frac{3}{5}(0.918) + \frac{2}{5}(0) = 0.551

🔹 Information Gain (Wind)

Gain(Wind)=0.971−0.551=0.420Gain(Wind) = 0.971 - 0.551 = 0.420

✅ Step 4: Choose Best Attribute

Attribute        Gain
Outlook        0.571 ✅
Wind        0.420

👉 Choose Outlook as root node

🌳 Step 5: Split Tree on Outlook

        Outlook
       /   |    \
   Sunny Rain Overcast
     |      |      |
    No     ?      Yes
  • Sunny → No (pure)
  • Overcast → Yes (pure)
  • Rain → needs further split

🔹 Step 6: Split Rain Subset using Wind

Rain subset:

Wind    Play
Weak    Yes
Strong    No

Perfect split:

  • Weak → Yes
  • Strong → No

🌳 Final Decision Tree

        Outlook
       /   |    \
   Sunny Rain Overcast
     |      |      |
    No     Wind    Yes
           /   \
        Weak  Strong
         |       |
        Yes      No

🎯 Final Rules

  • If Outlook = Sunny → No
  • If Outlook = Overcast → Yes
  • If Outlook = Rain AND Wind = Weak → Yes
  • If Outlook = Rain AND Wind = Strong → No

🧠 Key Takeaways

  • ID3 always picks highest Information Gain
  • First split may not fully classify → recursive splitting
  • Tree grows until all nodes are pure

⚖️ Advantages of Decision Trees

  • Easy to understand and visualize
  • No need for data normalization
  • Works with both categorical & numerical data

⚠️ Limitations

  • Can overfit easily
  • Sensitive to small data changes
  • ID3 handles only categorical features

🔄 ID3 vs Other Algorithms

AlgorithmKey Idea
ID3        Uses Information Gain
C4.5        Handles continuous data, pruning
CART        Uses Gini Index

🧠 Key Insight

Decision Trees (and ID3) work by:

👉 Asking the best question at each step to reduce uncertainty as quickly as possible



Appendix

🌳 What is the Gini Index?

The Gini Index (or Gini Impurity) is a measure of how impure or mixed a dataset is. It is commonly used to decide the best split in decision trees.

📌 Formula

Gini(S)=1−∑i=1cpi2Gini(S) = 1 - \sum_{i=1}^{c} p_i^2

  • pip_i: Probability of class ii
  • cc: Number of classes

🔍 Intuition

  • Gini = 0 → Perfectly pure (all samples belong to one class)
  • Higher Gini → More mixed classes

👉 It tells: “How likely are we to misclassify a random sample?”

📊 Example

If a dataset has:

  • P(Yes)=0.5P(Yes) = 0.5
  • P(No)=0.5P(No) = 0.5
Gini=1−(0.52+0.52)=1−(0.25+0.25)=0.5Gini = 1 - (0.5^2 + 0.5^2) = 1 - (0.25 + 0.25) = 0.5

⚖️ Gini vs Entropy

Measure    Formula StyleRange    Used In
Entropy    Uses log        0 to 1        ID3
Gini Index    No log (faster)        0 to 0.5 (binary)    CART

❗ Is Gini Index used in ID3?

👉 No — Gini Index is NOT used in ID3.

  • ID3 uses → Entropy + Information Gain
  • Gini Index is used in → CART (Classification and Regression Trees)

🧠 Key Difference

  • ID3: Chooses split that maximizes Information Gain
  • CART: Chooses split that minimizes Gini Index


Big Example:

Compute the Gain and find the best attribute for splitting( root node )




So the root node is outlook

Learn the complete example : visit https://iq.opengenus.org/id3-algorithm/

Comments

Post a Comment

Popular posts from this blog

Machine Learning PCCST503 Semester5 KTU CS 2024 Scheme - Dr Binu V P

About Me  - Dr Binu V P Syllabus Machine Learning PCCST503 KTU 2024 Scheme Model Question Paper Machine Learning PCCST503 Semester 5 KTU CS 2024 Scheme Do the programs to better understand the concept. Machine Learning Lab PCCSL508 Module -I Introduction to Machine Learning Introduction to ML Distinguishing Machine Learning from Traditional Programming Machine Learning Paradigms Supervised UnSupervised Semi-Supervised Reinforcement Stages of Machine Learning: From Data Collection to Deployment Parameter Estimation Introduction to Parameter Estimation in Machine Learning Maximum Likelyhood Estimation.(MLE) Maximum A Posteriori Estimation.(MAP) Numerical Problems MLE and MAP Supervised Learning Feature Representation and Problem Formulation Role of loss functions and optimization  Regression Introduction to Regression   Linear regression with one variable  (  lab experiment ) Example Problems- simple linear regression - University Questions Evaluation Metri...
Read more

Introduction to Machine Learning (ML)

  📘 Introduction to Machine Learning (ML) 🔹 What is Machine Learning? Machine Learning is a subfield of Artificial Intelligence that focuses on developing algorithms that allow computers to learn patterns from data and make decisions or predictions without explicit programming . It focuses on developing algorithms and models that allow machines to: Identify patterns in data Make decisions with minimal human intervention Predict future outcomes based on past experiences By continuously learning from new data, machine learning systems become more accurate and efficient over time. 📌 Formal Definition  A computer program is said to learn from experience E with respect to some task T and performance measure P if its performance at task T , as measured by P , improves with experience E . 🔹 Why Machine Learning? Traditional programming: Input + Program → Output Machine Learning paradigm: Input + Output → Model (learned program) 👉 Instead of writing...
Read more

Distinguishing Machine Learning from Traditional Programming

Image
  📘 Distinguishing Machine Learning from Traditional Programming 🔹 1. Fundamental Idea 🧾 Traditional Programming In conventional programming, developers write explicit instructions for the system to follow. The programmer explicitly writes rules/logic System follows deterministic instructions Input data is processed using predefined rules The output is based strictly on those rules 👉 Flow: Input + Program → Output 🤖 Machine Learning In machine learning, the system learns patterns from data instead of being explicitly programmed. Programmer provides  data + learning algorithm The model is trained using data The system  learns rules automatically from data It makes predictions or decisions based on learned patterns 👉 Flow: Input + Output → Learning Algorithm → Model Model + New Input → Predicted Output 🔹 2. Key Difference in Approach Aspect      Traditional Programming Machine Learning Input method Logic creation   ...
Read more