Classification Part II

• Decision Trees with Information Gain
• Course: Databases and Data Mining
• Instructor: Jamolbek Mattiev

Learning Objectives

• • Understand decision tree structure
• • Learn entropy concept
• • Understand information gain
• • Apply splitting criteria mathematically

What is a Decision Tree?

• • Supervised classification method
• • Tree-like structure
• • Internal nodes = feature tests
• • Leaves = class labels

Entropy Concept

• Entropy measures impurity
• H(S) = − Σ pi log2(pi)
• Range: 0 (pure) to 1 (max impurity)

Interpretation of Entropy

• • H = 0 → Pure node
• • H = 1 → Maximum uncertainty (binary case)
• • Higher entropy → more disorder

Information Gain

• IG(S, A) = H(S) − Σ (|Sv|/|S|) H(Sv)
• Measures reduction in entropy
• Select attribute with highest IG

Step-by-Step Algorithm

• 1. Compute entropy of dataset
• 2. For each attribute compute IG
• 3. Choose attribute with max IG
• 4. Split dataset
• 5. Repeat recursively

Example Dataset (Binary Class)

• Total samples: 14
• 9 Positive, 5 Negative
• Compute H(S)
• Test split on attribute Outlook

Tree Construction Process

• • Recursive partitioning
• • Stop when entropy = 0
• • Or no features left
• • Or stopping criteria reached

Advantages

• • Easy to interpret
• • Handles categorical data
• • No normalization required
• • Fast training

Limitations

• • Can overfit
• • Sensitive to noise
• • Bias toward multi-valued attributes

Overfitting Control

• • Pre-pruning
• • Post-pruning
• • Limit maximum depth
• • Minimum samples per leaf

Entropy vs Gini

• Entropy → used in ID3/C4.5
• Gini → used in CART
• Both measure impurity
• Different mathematical properties

Mathematical Insight

• Information gain = Mutual Information
• Based on Information Theory
• Maximizes reduction in uncertainty

Summary

• • Entropy measures impurity
• • Information gain selects best split
• • Tree built recursively
• • Pruning improves generalization

Entropy Curve Visualization