Decision Trees for Classification

Introduction

• Welcome to Normalized Nerd
• Topic: Decision Trees, specifically for classification
• Content focus: Intuition, math, and visualizations
• Encouragement to subscribe and join the Discord server

Data Setup

• Data features: x0 (horizontal axis) and x1 (vertical axis)
• Classes: Green and Red
• Note: Classes are not linearly separable

What is a Decision Tree?

• Definition: A binary tree that splits datasets until pure leaf nodes are created
• Leaf nodes contain only one type of class
• Types of nodes:
  • Decision Nodes: Conditions to split data
  • Leaf Nodes: Classifies new data points

Example of Trained Decision Tree

1. Root Node: Contains whole dataset
   • Condition: Is x0 <= -12?
   • Splits data into left (meets condition) and right (does not meet condition)
2. Left Child: Pure node (only Red points)
3. Right Child: Further split with condition x0 <= 9
4. Left Child of Right: Further split x1 <= 9
   • Result: Both child nodes are pure

Classifying New Data Points

• Example data point: (x0 = 15, x1 = 7)
• Follow conditions at each node:
  • Root: 15 > -12 (right child)
  • Right Child: 15 > 9 (right child)
  • Leaf node reached: All points are Red
• If nodes are not pure, use majority voting for classification

Understanding Decision Trees as Machine Learning

• Similar to nested if statements, but requires learning optimal conditions
• Model determines the best features and threshold values to split data

Optimal Splitting Criterion

• Goal: Achieve pure leaf nodes through optimal splits
• Use information theory for decision-making
• Entropy: Measure of uncertainty in a given state
  • Higher entropy = more uncertainty
  • Example: Equal number of Red and Green points = highest entropy
• Information Gain: Measure to evaluate splits
  • Calculate by subtracting child nodes' entropy from parent node's entropy
  • Weights for child nodes are relative sizes compared to the parent

Greedy Algorithm in Decision Trees

• Decision trees use a greedy algorithm: selects the best immediate split
• No backtracking or changing previous splits
• Fast training despite simplicity

Conclusion

• Final model shows reduced impurity at each level after training
• Upcoming content: Coding a decision tree from scratch and introduction to Gini index
• Encourage subscriptions and notifications for future updates
• Thank you for watching!