Decision Trees Deep Dive

Entropy(S) = -SUM[p_i * log2(p_i)] for each class i

Examples:
  - All same class:    Entropy = 0     (pure, no disorder)
  - 50/50 split:       Entropy = 1.0   (maximum disorder)
  - 90/10 split:       Entropy = 0.47  (mostly ordered)

Where p_i = proportion of class i in the set

Information_Gain(S, feature) = Entropy(S) - SUM[(|S_v|/|S|) * Entropy(S_v)]

Where:
  S = parent dataset
  S_v = subset of S after splitting on feature value v
  |S_v|/|S| = proportion of samples in each child

The tree greedily picks the feature and threshold that
maximizes Information Gain at each step.

Gini(S) = 1 - SUM[p_i^2] for each class i

Examples:
  - All same class:    Gini = 0       (pure)
  - 50/50 split:       Gini = 0.5     (maximum impurity)
  - 90/10 split:       Gini = 0.18    (mostly pure)

Gini vs Entropy:
  - Gini is faster to compute (no log)
  - Results are very similar in practice
  - Gini tends to isolate the most frequent class
  - Entropy tends to produce more balanced trees

# For regression trees, CART minimizes MSE instead:
# At each split, it minimizes:
#   SUM[(y_i - mean(y_left))^2] + SUM[(y_j - mean(y_right))^2]
# The prediction at each leaf is the mean of the target values

# Cost-complexity pruning in sklearn
# Uses the ccp_alpha parameter
# Higher alpha = more pruning = simpler tree

# Find optimal alpha using cross-validation
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import cross_val_score

tree = DecisionTreeClassifier(random_state=42)
path = tree.cost_complexity_pruning_path(X_train, y_train)
ccp_alphas = path.ccp_alphas

# Test each alpha value
scores = []
for alpha in ccp_alphas:
    clf = DecisionTreeClassifier(ccp_alpha=alpha, random_state=42)
    score = cross_val_score(clf, X_train, y_train, cv=5)
    scores.append(score.mean())

# Pick alpha with highest cross-validation score
best_alpha = ccp_alphas[np.argmax(scores)]

import numpy as np
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeClassifier, plot_tree, export_text
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score, classification_report

# Load the Iris dataset
data = load_iris()
X, y = data.data, data.target
feature_names = data.feature_names
class_names = data.target_names

# Train/test split
X_train, X_test, y_train, y_test = train_test_split(
    X, y, test_size=0.2, random_state=42, stratify=y
)

# Train Decision Tree (with pruning)
tree = DecisionTreeClassifier(
    criterion='gini',        # or 'entropy'
    max_depth=4,             # prevent overfitting
    min_samples_split=5,     # minimum samples to split
    min_samples_leaf=2,      # minimum samples in leaf
    random_state=42
)
tree.fit(X_train, y_train)

# Evaluate
y_pred = tree.predict(X_test)
print(f"Accuracy: {accuracy_score(y_test, y_pred):.4f}")
print(f"\n{classification_report(y_test, y_pred, target_names=class_names)}")

# --- Visualize the Tree ---
plt.figure(figsize=(20, 10))
plot_tree(
    tree,
    feature_names=feature_names,
    class_names=class_names,
    filled=True,           # color by class
    rounded=True,          # rounded boxes
    fontsize=10,
    proportion=True        # show proportions
)
plt.title("Decision Tree - Iris Classification")
plt.tight_layout()
plt.show()

# --- Text representation ---
print("\nTree Rules:")
print(export_text(tree, feature_names=feature_names))

# --- Feature Importance ---
importances = tree.feature_importances_
indices = np.argsort(importances)[::-1]

print("\nFeature Importance:")
for i, idx in enumerate(indices):
    print(f"  {i+1}. {feature_names[idx]:<25} {importances[idx]:.4f}")

plt.figure(figsize=(8, 5))
plt.bar(range(len(importances)), importances[indices])
plt.xticks(range(len(importances)),
           [feature_names[i] for i in indices], rotation=45, ha='right')
plt.title("Feature Importance - Decision Tree")
plt.ylabel("Importance (Gini)")
plt.tight_layout()
plt.show()

# --- Compare: Pruned vs Unpruned ---
tree_full = DecisionTreeClassifier(random_state=42)  # no constraints
tree_full.fit(X_train, y_train)

print(f"\nUnpruned tree depth: {tree_full.get_depth()}, leaves: {tree_full.get_n_leaves()}")
print(f"Pruned tree depth:   {tree.get_depth()}, leaves: {tree.get_n_leaves()}")
print(f"Unpruned accuracy:   {accuracy_score(y_test, tree_full.predict(X_test)):.4f}")
print(f"Pruned accuracy:     {accuracy_score(y_test, y_pred):.4f}")