Decision Tree Algorithm

Decision Tree Algorithm

✅ Steps to Construct a Decision Tree

1. Place the best feature (attribute) of the dataset at the root of the tree.

2. Split the training set into subsets, where each subset contains data with the same value for a feature.

3. Repeat steps 1 and 2 recursively for each subset until:

   • All branches lead to leaf nodes.

   • Leaf nodes contain class labels (decisions).

🧠 Popular Decision Tree Algorithms

• ID3 (Iterative Dichotomiser 3) – Developed by Ross Quinlan

• C4.5 – Successor to ID3, also developed by Ross Quinlan

• CART (Classification and Regression Trees)

• OneR (One Rule Algorithm) – Developed by Robert Holte

📌 The ID3 Algorithm (based on Information Gain)

Used when:

• There are two class labels, "+" (positive) and "−" (negative)

🔤 Notation

🔁 ID3 Algorithm – Steps

1. Create a root node for the tree.

2. If all examples in 𝑆 are positive, → return leaf node labeled "+"

3. If all examples in 𝑆 are negative, → return leaf node labeled "−"

4. If there are no more features, return a leaf node with the most common class in 𝑆.

5. Else:

   • Choose feature A with the highest Information Gain.

   • Assign A to the root node.

   • For each value v in V(A):

     • Create a branch below the root labeled A = v

     • If 𝑆ᵥ is empty, add a leaf node with the most common label in 𝑆.

     • Else, recursively apply the algorithm on 𝑆ᵥ and features F \ {A}

🧪 Training Dataset

🔧 Step 1: Calculate Initial Entropy of the Dataset

• Total = 14

• Yes = 9, No = 5

✅ Entropy($S^{\prime }$) = 0.940

🔍 Step 2: Calculate Information Gain for Each Attribute

Attribute 1: OUTLOOK (Sunny, Overcast, Rain)

$Entrophy(Sunny)$

Sunny: $S$ = [No, No, No, Yes, Yes]

$Entrophy(Overcast)$

Sunny: $S$ = [Yes, Yes, Yes, Yes]

✅ Pure Node

$Entrophy(Rain)$

Sunny: $S$ = [Yes, Yes, Yes, No, No]

$Gain(S^{\prime },OUTLOOK)$

✅ Gain(Outlook) = 0.2464