Week 6: Decision Trees - Interactive Demonstrations

MPS311/439 Machine Learning - Dr. Wei Xing

This notebook contains interactive demonstrations for the Week 6 lecture on Decision Trees.

Instructions: Run all cells sequentially. Interact with sliders and buttons to explore concepts.

# Install required packages (only needed once in Colab)
!pip install ipywidgets -q

# Import all required libraries
import numpy as np
import matplotlib.pyplot as plt
from matplotlib.colors import ListedColormap
import seaborn as sns
from sklearn.datasets import load_iris, load_wine, make_moons, make_classification
from sklearn.tree import DecisionTreeClassifier, plot_tree
from sklearn.linear_model import LogisticRegression
from sklearn.discriminant_analysis import QuadraticDiscriminantAnalysis
from sklearn.model_selection import train_test_split, GridSearchCV
from sklearn.metrics import accuracy_score
from ipywidgets import interact, interactive, fixed, IntSlider, FloatSlider, Dropdown
import ipywidgets as widgets
from IPython.display import display, clear_output

# Set random seed for reproducibility
np.random.seed(42)

# Set style
plt.style.use('seaborn-v0_8-darkgrid')
sns.set_palette("husl")

print("โœ… All libraries imported successfully!")
โœ… All libraries imported successfully!

Demo 1: XOR Problem - When Linear Methods Fail

Purpose: Show students a concrete example where linear methods completely fail.

Key Learning: No straight line can separate the XOR pattern, motivating the need for decision trees.

def plot_xor_problem(noise_level=0.1, n_samples=100):
    """
    Generate and visualize XOR problem with linear classifier failure.
    """
    # Generate XOR dataset
    np.random.seed(42)
    n_per_cluster = n_samples // 4
    
    # Four clusters arranged in XOR pattern
    cluster1 = np.random.randn(n_per_cluster, 2) * noise_level + [0, 0]  # Class 0
    cluster2 = np.random.randn(n_per_cluster, 2) * noise_level + [1, 1]  # Class 0
    cluster3 = np.random.randn(n_per_cluster, 2) * noise_level + [0, 1]  # Class 1
    cluster4 = np.random.randn(n_per_cluster, 2) * noise_level + [1, 0]  # Class 1
    
    X = np.vstack([cluster1, cluster2, cluster3, cluster4])
    y = np.array([0]*n_per_cluster*2 + [1]*n_per_cluster*2)
    
    # Train logistic regression
    lr = LogisticRegression(random_state=42)
    lr.fit(X, y)
    lr_acc = lr.score(X, y)
    
    # Train decision tree
    dt = DecisionTreeClassifier(max_depth=3, random_state=42)
    dt.fit(X, y)
    dt_acc = dt.score(X, y)
    
    # Create mesh for decision boundary
    h = 0.02
    x_min, x_max = X[:, 0].min() - 0.5, X[:, 0].max() + 0.5
    y_min, y_max = X[:, 1].min() - 0.5, X[:, 1].max() + 0.5
    xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
                         np.arange(y_min, y_max, h))
    
    # Plot
    fig, axes = plt.subplots(1, 2, figsize=(14, 5))
    
    # Logistic Regression
    Z_lr = lr.predict(np.c_[xx.ravel(), yy.ravel()])
    Z_lr = Z_lr.reshape(xx.shape)
    axes[0].contourf(xx, yy, Z_lr, alpha=0.3, cmap='RdYlBu')
    axes[0].scatter(X[y==0, 0], X[y==0, 1], c='blue', s=50, edgecolors='black', label='Class 0')
    axes[0].scatter(X[y==1, 0], X[y==1, 1], c='red', s=50, edgecolors='black', label='Class 1')
    axes[0].set_title(f'Logistic Regression FAILS\nAccuracy: {lr_acc:.1%}', fontsize=14, fontweight='bold')
    axes[0].set_xlabel('Feature 1', fontsize=12)
    axes[0].set_ylabel('Feature 2', fontsize=12)
    axes[0].legend()
    axes[0].grid(True, alpha=0.3)
    
    # Decision Tree
    Z_dt = dt.predict(np.c_[xx.ravel(), yy.ravel()])
    Z_dt = Z_dt.reshape(xx.shape)
    axes[1].contourf(xx, yy, Z_dt, alpha=0.3, cmap='RdYlBu')
    axes[1].scatter(X[y==0, 0], X[y==0, 1], c='blue', s=50, edgecolors='black', label='Class 0')
    axes[1].scatter(X[y==1, 0], X[y==1, 1], c='red', s=50, edgecolors='black', label='Class 1')
    axes[1].set_title(f'Decision Tree SUCCEEDS\nAccuracy: {dt_acc:.1%}', fontsize=14, fontweight='bold', color='green')
    axes[1].set_xlabel('Feature 1', fontsize=12)
    axes[1].set_ylabel('Feature 2', fontsize=12)
    axes[1].legend()
    axes[1].grid(True, alpha=0.3)
    
    plt.tight_layout()
    plt.show()
    
    print(f"\n๐Ÿ”ด Logistic Regression: {lr_acc:.1%} (barely better than random guessing!)")
    print(f"๐ŸŸข Decision Tree: {dt_acc:.1%} (captures the XOR pattern!)\n")
    print("๐Ÿ’ก Key Insight: No straight line can separate XOR pattern. Trees use axis-aligned splits to solve it!")

# Interactive widget
interact(plot_xor_problem, 
         noise_level=FloatSlider(value=0.1, min=0.05, max=0.3, step=0.05, description='Noise Level:'),
         n_samples=IntSlider(value=100, min=40, max=200, step=20, description='Samples:'));

Demo 2: Decision Tree Structure on Iris Dataset

Purpose: Show students how to visualize and interpret a real decision tree.

Key Learning: Understanding tree structure, node information, and prediction paths.

def visualize_iris_tree(max_depth=3, min_samples_split=2, min_samples_leaf=1):
    """
    Train and visualize decision tree on Iris dataset.
    """
    # Load Iris dataset
    iris = load_iris()
    X, y = iris.data, iris.target
    
    # Split data
    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
    
    # Train tree
    clf = DecisionTreeClassifier(
        max_depth=max_depth,
        min_samples_split=min_samples_split,
        min_samples_leaf=min_samples_leaf,
        random_state=42
    )
    clf.fit(X_train, y_train)
    
    # Calculate accuracies
    train_acc = clf.score(X_train, y_train)
    test_acc = clf.score(X_test, y_test)
    
    # Visualize tree
    fig, ax = plt.subplots(figsize=(20, 10))
    plot_tree(clf, 
              filled=True, 
              rounded=True,
              feature_names=iris.feature_names,
              class_names=iris.target_names,
              fontsize=10,
              ax=ax)
    plt.title(f'Decision Tree (depth={max_depth})\nTrain Acc: {train_acc:.3f} | Test Acc: {test_acc:.3f}', 
              fontsize=16, fontweight='bold', pad=20)
    plt.tight_layout()
    plt.show()
    
    # Feature importance
    importances = clf.feature_importances_
    feature_names = iris.feature_names
    
    print("\n๐Ÿ“Š Feature Importance:")
    print("โ”€" * 50)
    for name, importance in sorted(zip(feature_names, importances), key=lambda x: x[1], reverse=True):
        if importance > 0:
            print(f"{name:30s}: {importance:.3f} {'โ–ˆ' * int(importance * 50)}")
        else:
            print(f"{name:30s}: {importance:.3f} (not used)")
    
    print(f"\n๐Ÿ“ˆ Number of leaves: {clf.get_n_leaves()}")
    print(f"๐Ÿ“ Actual depth: {clf.get_depth()}")
    
    # Show prediction example
    sample_idx = 0
    sample = X_test[sample_idx].reshape(1, -1)
    pred = clf.predict(sample)[0]
    true_label = y_test[sample_idx]
    
    print(f"\n๐Ÿ” Example Prediction:")
    print(f"Sample features: {sample[0]}")
    print(f"Predicted: {iris.target_names[pred]}")
    print(f"True label: {iris.target_names[true_label]}")
    print(f"Correct: {'โœ…' if pred == true_label else 'โŒ'}")

# Interactive widget
interact(visualize_iris_tree,
         max_depth=IntSlider(value=3, min=1, max=8, step=1, description='Max Depth:'),
         min_samples_split=IntSlider(value=2, min=2, max=20, step=2, description='Min Split:'),
         min_samples_leaf=IntSlider(value=1, min=1, max=10, step=1, description='Min Leaf:'));

Demo 3: Decision Boundaries in 2D

Purpose: Visualize how decision trees create axis-aligned rectangular regions.

Key Learning: Trees split along axes, creating rectangular decision regions.

def plot_2d_decision_boundary(max_depth=3, dataset='moons'):
    """
    Visualize decision boundaries for 2D data.
    """
    # Generate dataset
    if dataset == 'moons':
        X, y = make_moons(n_samples=300, noise=0.25, random_state=42)
        title_dataset = "Moons Dataset"
    elif dataset == 'circles':
        from sklearn.datasets import make_circles
        X, y = make_circles(n_samples=300, noise=0.15, factor=0.5, random_state=42)
        title_dataset = "Circles Dataset"
    else:  # blobs
        from sklearn.datasets import make_blobs
        X, y = make_blobs(n_samples=300, centers=2, random_state=42, cluster_std=1.5)
        title_dataset = "Blobs Dataset"
    
    # Train models
    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
    
    dt = DecisionTreeClassifier(max_depth=max_depth, random_state=42)
    dt.fit(X_train, y_train)
    dt_acc = dt.score(X_test, y_test)
    
    lr = LogisticRegression(random_state=42)
    lr.fit(X_train, y_train)
    lr_acc = lr.score(X_test, y_test)
    
    # Create mesh
    h = 0.02
    x_min, x_max = X[:, 0].min() - 0.5, X[:, 0].max() + 0.5
    y_min, y_max = X[:, 1].min() - 0.5, X[:, 1].max() + 0.5
    xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
                         np.arange(y_min, y_max, h))
    
    # Plot
    fig, axes = plt.subplots(1, 2, figsize=(14, 5))
    
    # Logistic Regression
    Z_lr = lr.predict(np.c_[xx.ravel(), yy.ravel()])
    Z_lr = Z_lr.reshape(xx.shape)
    axes[0].contourf(xx, yy, Z_lr, alpha=0.4, cmap='RdYlBu')
    axes[0].scatter(X_train[y_train==0, 0], X_train[y_train==0, 1], 
                   c='blue', s=50, edgecolors='black', label='Class 0 (train)', alpha=0.7)
    axes[0].scatter(X_train[y_train==1, 0], X_train[y_train==1, 1], 
                   c='red', s=50, edgecolors='black', label='Class 1 (train)', alpha=0.7)
    axes[0].scatter(X_test[y_test==0, 0], X_test[y_test==0, 1], 
                   c='blue', s=100, marker='s', edgecolors='black', label='Class 0 (test)', alpha=0.9)
    axes[0].scatter(X_test[y_test==1, 0], X_test[y_test==1, 1], 
                   c='red', s=100, marker='s', edgecolors='black', label='Class 1 (test)', alpha=0.9)
    axes[0].set_title(f'Logistic Regression\nTest Acc: {lr_acc:.3f}', fontsize=14, fontweight='bold')
    axes[0].set_xlabel('Feature 1', fontsize=12)
    axes[0].set_ylabel('Feature 2', fontsize=12)
    axes[0].legend(loc='best', fontsize=8)
    axes[0].grid(True, alpha=0.3)
    
    # Decision Tree
    Z_dt = dt.predict(np.c_[xx.ravel(), yy.ravel()])
    Z_dt = Z_dt.reshape(xx.shape)
    axes[1].contourf(xx, yy, Z_dt, alpha=0.4, cmap='RdYlBu')
    axes[1].scatter(X_train[y_train==0, 0], X_train[y_train==0, 1], 
                   c='blue', s=50, edgecolors='black', label='Class 0 (train)', alpha=0.7)
    axes[1].scatter(X_train[y_train==1, 0], X_train[y_train==1, 1], 
                   c='red', s=50, edgecolors='black', label='Class 1 (train)', alpha=0.7)
    axes[1].scatter(X_test[y_test==0, 0], X_test[y_test==0, 1], 
                   c='blue', s=100, marker='s', edgecolors='black', label='Class 0 (test)', alpha=0.9)
    axes[1].scatter(X_test[y_test==1, 0], X_test[y_test==1, 1], 
                   c='red', s=100, marker='s', edgecolors='black', label='Class 1 (test)', alpha=0.9)
    axes[1].set_title(f'Decision Tree (depth={max_depth})\nTest Acc: {dt_acc:.3f}', 
                     fontsize=14, fontweight='bold')
    axes[1].set_xlabel('Feature 1', fontsize=12)
    axes[1].set_ylabel('Feature 2', fontsize=12)
    axes[1].legend(loc='best', fontsize=8)
    axes[1].grid(True, alpha=0.3)
    
    plt.suptitle(f'{title_dataset}', fontsize=16, fontweight='bold', y=1.02)
    plt.tight_layout()
    plt.show()
    
    print(f"\n๐Ÿ“Š Results on {title_dataset}:")
    print(f"Logistic Regression Test Accuracy: {lr_acc:.3f}")
    print(f"Decision Tree Test Accuracy: {dt_acc:.3f}")
    print(f"\n๐Ÿ’ก Notice: Tree boundary is made of horizontal/vertical lines (axis-aligned splits)!")

# Interactive widget
interact(plot_2d_decision_boundary,
         max_depth=IntSlider(value=3, min=1, max=10, step=1, description='Max Depth:'),
         dataset=Dropdown(options=['moons', 'circles', 'blobs'], value='moons', description='Dataset:'));

Demo 4: The Overfitting Problem (MOST IMPORTANT!)

Purpose: Demonstrate how tree depth affects overfitting - the critical concept!

Key Learning: Deep trees memorize training data, leading to poor generalization.

def demonstrate_overfitting(max_depth=5, dataset_size=300, noise_level=0.3):
    """
    Interactive demonstration of overfitting with tree depth.
    Shows both decision boundaries and accuracy curves.
    """
    # Generate dataset
    X, y = make_moons(n_samples=dataset_size, noise=noise_level, random_state=42)
    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
    
    # Train tree with specified depth
    clf = DecisionTreeClassifier(max_depth=max_depth, random_state=42)
    clf.fit(X_train, y_train)
    train_acc = clf.score(X_train, y_train)
    test_acc = clf.score(X_test, y_test)
    
    # Train trees with different depths for comparison
    depths = range(1, 16)
    train_accs = []
    test_accs = []
    
    for d in depths:
        clf_temp = DecisionTreeClassifier(max_depth=d, random_state=42)
        clf_temp.fit(X_train, y_train)
        train_accs.append(clf_temp.score(X_train, y_train))
        test_accs.append(clf_temp.score(X_test, y_test))
    
    # Create mesh for decision boundary
    h = 0.02
    x_min, x_max = X[:, 0].min() - 0.5, X[:, 0].max() + 0.5
    y_min, y_max = X[:, 1].min() - 0.5, X[:, 1].max() + 0.5
    xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
                         np.arange(y_min, y_max, h))
    
    Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)
    
    # Create figure with 2 subplots
    fig = plt.figure(figsize=(16, 6))
    
    # Left: Decision boundary
    ax1 = plt.subplot(1, 2, 1)
    ax1.contourf(xx, yy, Z, alpha=0.4, cmap='RdYlBu')
    ax1.scatter(X_train[y_train==0, 0], X_train[y_train==0, 1], 
               c='blue', s=50, edgecolors='black', label='Class 0', alpha=0.7)
    ax1.scatter(X_train[y_train==1, 0], X_train[y_train==1, 1], 
               c='red', s=50, edgecolors='black', label='Class 1', alpha=0.7)
    ax1.set_xlabel('Feature 1', fontsize=12)
    ax1.set_ylabel('Feature 2', fontsize=12)
    ax1.legend()
    ax1.grid(True, alpha=0.3)
    
    # Determine if overfitting
    gap = train_acc - test_acc
    if gap < 0.05:
        status = "Good Balance โœ…"
        color = 'green'
    elif gap < 0.15:
        status = "Slight Overfitting โš ๏ธ"
        color = 'orange'
    else:
        status = "Severe Overfitting โŒ"
        color = 'red'
    
    ax1.set_title(f'Decision Boundary (depth={max_depth})\nTrain: {train_acc:.3f} | Test: {test_acc:.3f}\n{status}', 
                 fontsize=13, fontweight='bold', color=color)
    
    # Right: Accuracy vs depth
    ax2 = plt.subplot(1, 2, 2)
    ax2.plot(depths, train_accs, 'b-o', linewidth=2, markersize=8, label='Training Accuracy')
    ax2.plot(depths, test_accs, 'r--s', linewidth=2, markersize=8, label='Test Accuracy')
    ax2.axvline(x=max_depth, color='green', linestyle=':', linewidth=2, label=f'Current Depth ({max_depth})')
    
    # Mark optimal depth
    optimal_depth = depths[np.argmax(test_accs)]
    ax2.axvline(x=optimal_depth, color='purple', linestyle='--', linewidth=2, label=f'Optimal Depth ({optimal_depth})')
    
    # Shade regions
    ax2.axvspan(1, 3, alpha=0.1, color='yellow', label='Underfitting')
    ax2.axvspan(optimal_depth-1, optimal_depth+1, alpha=0.1, color='green', label='Sweet Spot')
    ax2.axvspan(10, 15, alpha=0.1, color='red', label='Overfitting')
    
    ax2.set_xlabel('Tree Depth', fontsize=12)
    ax2.set_ylabel('Accuracy', fontsize=12)
    ax2.set_title('Accuracy vs Tree Depth\n(Watch the Gap!)', fontsize=13, fontweight='bold')
    ax2.legend(loc='best', fontsize=9)
    ax2.grid(True, alpha=0.3)
    ax2.set_ylim([0.5, 1.05])
    ax2.set_xticks(depths)
    
    plt.tight_layout()
    plt.show()
    
    print(f"\n๐Ÿ“Š Current Configuration:")
    print(f"  Tree Depth: {max_depth}")
    print(f"  Training Accuracy: {train_acc:.3f}")
    print(f"  Test Accuracy: {test_acc:.3f}")
    print(f"  Train-Test Gap: {gap:.3f}")
    print(f"  Status: {status}")
    print(f"\n๐ŸŽฏ Optimal Depth (best test acc): {optimal_depth}")
    print(f"\n๐Ÿ’ก Key Insights:")
    if max_depth <= 3:
        print("   - Tree is too shallow (underfitting)")
        print("   - Both train and test accuracy are suboptimal")
        print("   - Try increasing max_depth!")
    elif max_depth > 10:
        print("   - Tree is too deep (overfitting)")
        print("   - Perfect training but poor test accuracy")
        print("   - The model memorized noise in training data")
        print("   - Try decreasing max_depth!")
    else:
        print("   - Tree depth is in reasonable range")
        print("   - Monitor the train-test gap")
        print("   - Adjust based on the gap size")

# Interactive widget
interact(demonstrate_overfitting,
         max_depth=IntSlider(value=5, min=1, max=15, step=1, description='Max Depth:'),
         dataset_size=IntSlider(value=300, min=100, max=500, step=50, description='Dataset Size:'),
         noise_level=FloatSlider(value=0.3, min=0.1, max=0.5, step=0.05, description='Noise Level:'));

Demo 5: Feature Importance Analysis

Purpose: Show which features drive the treeโ€™s decisions.

Key Learning: Trees automatically rank features by importance.

def analyze_feature_importance(max_depth=5, dataset='iris'):
    """
    Visualize feature importance for different datasets.
    """
    # Load dataset
    if dataset == 'iris':
        data = load_iris()
        title = "Iris Dataset"
    else:  # wine
        data = load_wine()
        title = "Wine Dataset"
    
    X, y = data.data, data.target
    feature_names = data.feature_names
    
    # Split and train
    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
    
    clf = DecisionTreeClassifier(max_depth=max_depth, random_state=42)
    clf.fit(X_train, y_train)
    
    train_acc = clf.score(X_train, y_train)
    test_acc = clf.score(X_test, y_test)
    
    # Get feature importances
    importances = clf.feature_importances_
    indices = np.argsort(importances)[::-1]
    
    # Create figure
    fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(16, 6))
    
    # Left: Bar chart
    colors = ['green' if imp > 0 else 'lightgray' for imp in importances[indices]]
    bars = ax1.barh(range(len(importances)), importances[indices], color=colors, edgecolor='black')
    ax1.set_yticks(range(len(importances)))
    ax1.set_yticklabels([feature_names[i] for i in indices], fontsize=10)
    ax1.set_xlabel('Importance', fontsize=12)
    ax1.set_title(f'Feature Importance\n{title} (depth={max_depth})', fontsize=13, fontweight='bold')
    ax1.invert_yaxis()
    ax1.grid(True, alpha=0.3, axis='x')
    
    # Add value labels
    for i, (imp, bar) in enumerate(zip(importances[indices], bars)):
        if imp > 0:
            ax1.text(imp + 0.01, i, f'{imp:.3f}', va='center', fontsize=9, fontweight='bold')
    
    # Right: Pie chart (only non-zero importances)
    non_zero_indices = [i for i in indices if importances[i] > 0]
    if len(non_zero_indices) > 0:
        non_zero_importances = [importances[i] for i in non_zero_indices]
        non_zero_names = [feature_names[i] for i in non_zero_indices]
        
        # Wrap long feature names
        wrapped_names = [name[:20] + '...' if len(name) > 20 else name for name in non_zero_names]
        
        wedges, texts, autotexts = ax2.pie(non_zero_importances, 
                                            labels=wrapped_names,
                                            autopct='%1.1f%%',
                                            startangle=90,
                                            textprops={'fontsize': 10})
        ax2.set_title(f'Feature Importance Distribution\n(Only features used in splits)', 
                     fontsize=13, fontweight='bold')
        
        # Make percentage text bold
        for autotext in autotexts:
            autotext.set_color('white')
            autotext.set_fontweight('bold')
    else:
        ax2.text(0.5, 0.5, 'No features used\n(tree too shallow)', 
                ha='center', va='center', fontsize=14, transform=ax2.transAxes)
        ax2.set_xlim(0, 1)
        ax2.set_ylim(0, 1)
    
    plt.tight_layout()
    plt.show()
    
    # Print detailed statistics
    print(f"\n๐Ÿ“Š {title} Results:")
    print(f"  Training Accuracy: {train_acc:.3f}")
    print(f"  Test Accuracy: {test_acc:.3f}")
    print(f"\n๐Ÿ† Feature Importance Ranking:")
    print("  " + "โ”€" * 60)
    for rank, idx in enumerate(indices, 1):
        imp = importances[idx]
        name = feature_names[idx]
        if imp > 0:
            bar = 'โ–ˆ' * int(imp * 50)
            print(f"  {rank:2d}. {name:35s}: {imp:.4f} {bar}")
        else:
            print(f"  {rank:2d}. {name:35s}: {imp:.4f} (not used)")
    
    print(f"\n๐Ÿ’ก Interpretation:")
    top_feature = feature_names[indices[0]]
    top_importance = importances[indices[0]]
    if top_importance > 0:
        print(f"   - '{top_feature}' is the most important feature ({top_importance:.1%})")
        print(f"   - It contributes most to reducing impurity across all splits")
    
    n_used = sum(1 for imp in importances if imp > 0)
    n_total = len(importances)
    print(f"   - {n_used}/{n_total} features are actually used in this tree")
    print(f"   - {n_total - n_used} features have zero importance (ignored)")

# Interactive widget
interact(analyze_feature_importance,
         max_depth=IntSlider(value=5, min=1, max=10, step=1, description='Max Depth:'),
         dataset=Dropdown(options=['iris', 'wine'], value='iris', description='Dataset:'));

Demo 7: Comparing Trees with Logistic Regression and QDA

Purpose: Direct comparison with previous methods to solidify understanding.

Key Learning: When to use which method - trees excel at non-linear patterns.

def compare_all_methods(dataset_type='nonlinear', noise_level=0.25):
    """
    Compare Decision Tree, Logistic Regression, and QDA on different datasets.
    """
    # Generate dataset based on type
    if dataset_type == 'linear':
        # Linearly separable data
        from sklearn.datasets import make_classification
        X, y = make_classification(n_samples=300, n_features=2, n_redundant=0, 
                                   n_informative=2, n_clusters_per_class=1,
                                   flip_y=noise_level, random_state=42)
        title = "Linear Dataset"
    else:  # nonlinear
        X, y = make_moons(n_samples=300, noise=noise_level, random_state=42)
        title = "Non-linear Dataset (Moons)"
    
    # Split data
    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
    
    # Train all models
    models = {
        'Logistic Regression': LogisticRegression(random_state=42),
        'QDA': QuadraticDiscriminantAnalysis(),
        'Decision Tree (depth=3)': DecisionTreeClassifier(max_depth=3, random_state=42),
        'Decision Tree (depth=8)': DecisionTreeClassifier(max_depth=8, random_state=42)
    }
    
    # Train and evaluate
    results = {}
    for name, model in models.items():
        model.fit(X_train, y_train)
        train_acc = model.score(X_train, y_train)
        test_acc = model.score(X_test, y_test)
        results[name] = {'model': model, 'train_acc': train_acc, 'test_acc': test_acc}
    
    # Create mesh
    h = 0.02
    x_min, x_max = X[:, 0].min() - 0.5, X[:, 0].max() + 0.5
    y_min, y_max = X[:, 1].min() - 0.5, X[:, 1].max() + 0.5
    xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
                         np.arange(y_min, y_max, h))
    
    # Plot all models
    fig, axes = plt.subplots(2, 2, figsize=(14, 12))
    axes = axes.ravel()
    
    for idx, (name, result) in enumerate(results.items()):
        model = result['model']
        train_acc = result['train_acc']
        test_acc = result['test_acc']
        
        # Predict on mesh
        Z = model.predict(np.c_[xx.ravel(), yy.ravel()])
        Z = Z.reshape(xx.shape)
        
        # Plot
        axes[idx].contourf(xx, yy, Z, alpha=0.4, cmap='RdYlBu')
        axes[idx].scatter(X_train[y_train==0, 0], X_train[y_train==0, 1], 
                         c='blue', s=50, edgecolors='black', alpha=0.7, label='Class 0')
        axes[idx].scatter(X_train[y_train==1, 0], X_train[y_train==1, 1], 
                         c='red', s=50, edgecolors='black', alpha=0.7, label='Class 1')
        
        axes[idx].set_xlabel('Feature 1', fontsize=11)
        axes[idx].set_ylabel('Feature 2', fontsize=11)
        axes[idx].set_title(f'{name}\nTrain: {train_acc:.3f} | Test: {test_acc:.3f}', 
                           fontsize=12, fontweight='bold')
        axes[idx].legend(loc='best')
        axes[idx].grid(True, alpha=0.3)
    
    plt.suptitle(f'Method Comparison on {title}', fontsize=16, fontweight='bold', y=0.995)
    plt.tight_layout()
    plt.show()
    
    # Print comparison table
    print(f"\n{'='*80}")
    print(f"๐Ÿ“Š COMPARISON RESULTS - {title}")
    print(f"{'='*80}\n")
    print(f"{'Method':<30} {'Train Acc':<12} {'Test Acc':<12} {'Gap':<10} {'Status'}")
    print("โ”€" * 80)
    
    for name, result in results.items():
        train_acc = result['train_acc']
        test_acc = result['test_acc']
        gap = train_acc - test_acc
        
        if gap < 0.05:
            status = "โœ… Good"
        elif gap < 0.15:
            status = "โš ๏ธ Slight Overfit"
        else:
            status = "โŒ Overfitting"
        
        print(f"{name:<30} {train_acc:<12.3f} {test_acc:<12.3f} {gap:<10.3f} {status}")
    
    # Find best model
    best_name = max(results.items(), key=lambda x: x[1]['test_acc'])[0]
    best_acc = results[best_name]['test_acc']
    
    print("\n" + "โ”€" * 80)
    print(f"๐Ÿ† Best Model: {best_name} (Test Acc: {best_acc:.3f})")
    print("โ”€" * 80)
    
    print("\n๐Ÿ’ก Key Insights:")
    if dataset_type == 'linear':
        print("   - On linear data, all methods perform similarly")
        print("   - Simpler models (LR) are preferred for interpretability")
        print("   - Trees don't add much value here")
    else:
        print("   - On non-linear data, trees excel!")
        print("   - Linear methods struggle with curved boundaries")
        print("   - Deeper trees capture more complexity (but watch for overfitting!)")
        print("   - QDA can handle some non-linearity, but limited to quadratic")

# Interactive widget
interact(compare_all_methods,
         dataset_type=Dropdown(options=['linear', 'nonlinear'], value='nonlinear', description='Dataset Type:'),
         noise_level=FloatSlider(value=0.25, min=0.1, max=0.5, step=0.05, description='Noise Level:'));

Bonus Demo: Interactive Tree Playground

Purpose: Let students freely explore all hyperparameters at once!

Key Learning: Build intuition through hands-on experimentation.

def tree_playground(max_depth=5, min_samples_split=2, min_samples_leaf=1, 
                   dataset='moons', noise=0.25, n_samples=300):
    """
    Complete interactive playground for decision trees.
    Students can adjust all parameters and see results immediately.
    """
    # Generate dataset
    if dataset == 'moons':
        X, y = make_moons(n_samples=n_samples, noise=noise, random_state=42)
    elif dataset == 'circles':
        from sklearn.datasets import make_circles
        X, y = make_circles(n_samples=n_samples, noise=noise, factor=0.5, random_state=42)
    else:  # xor
        np.random.seed(42)
        n_per = n_samples // 4
        X = np.vstack([
            np.random.randn(n_per, 2) * noise + [0, 0],
            np.random.randn(n_per, 2) * noise + [1, 1],
            np.random.randn(n_per, 2) * noise + [0, 1],
            np.random.randn(n_per, 2) * noise + [1, 0]
        ])
        y = np.array([0]*n_per*2 + [1]*n_per*2)
    
    # Split and train
    X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)
    
    clf = DecisionTreeClassifier(
        max_depth=max_depth,
        min_samples_split=min_samples_split,
        min_samples_leaf=min_samples_leaf,
        random_state=42
    )
    clf.fit(X_train, y_train)
    train_acc = clf.score(X_train, y_train)
    test_acc = clf.score(X_test, y_test)
    gap = train_acc - test_acc
    
    # Create mesh
    h = 0.02
    x_min, x_max = X[:, 0].min() - 0.5, X[:, 0].max() + 0.5
    y_min, y_max = X[:, 1].min() - 0.5, X[:, 1].max() + 0.5
    xx, yy = np.meshgrid(np.arange(x_min, x_max, h),
                         np.arange(y_min, y_max, h))
    
    Z = clf.predict(np.c_[xx.ravel(), yy.ravel()])
    Z = Z.reshape(xx.shape)
    
    # Create figure
    fig = plt.figure(figsize=(16, 6))
    
    # Left: Decision boundary
    ax1 = plt.subplot(1, 2, 1)
    ax1.contourf(xx, yy, Z, alpha=0.4, cmap='RdYlBu')
    ax1.scatter(X_train[y_train==0, 0], X_train[y_train==0, 1], 
               c='blue', s=50, edgecolors='black', alpha=0.7, label='Class 0 (train)')
    ax1.scatter(X_train[y_train==1, 0], X_train[y_train==1, 1], 
               c='red', s=50, edgecolors='black', alpha=0.7, label='Class 1 (train)')
    ax1.scatter(X_test[y_test==0, 0], X_test[y_test==0, 1], 
               c='blue', s=120, marker='s', edgecolors='black', linewidth=2, alpha=0.9, label='Class 0 (test)')
    ax1.scatter(X_test[y_test==1, 0], X_test[y_test==1, 1], 
               c='red', s=120, marker='s', edgecolors='black', linewidth=2, alpha=0.9, label='Class 1 (test)')
    
    # Status color
    if gap < 0.05:
        status = "Good Balance โœ…"
        color = 'green'
    elif gap < 0.15:
        status = "Slight Overfitting โš ๏ธ"
        color = 'orange'
    else:
        status = "Severe Overfitting โŒ"
        color = 'red'
    
    ax1.set_xlabel('Feature 1', fontsize=12)
    ax1.set_ylabel('Feature 2', fontsize=12)
    ax1.set_title(f'Decision Boundary\nTrain: {train_acc:.3f} | Test: {test_acc:.3f} | Gap: {gap:.3f}\n{status}', 
                 fontsize=12, fontweight='bold', color=color)
    ax1.legend(loc='best', fontsize=9)
    ax1.grid(True, alpha=0.3)
    
    # Right: Tree structure (simplified)
    ax2 = plt.subplot(1, 2, 2)
    
    # Get tree statistics
    n_nodes = clf.tree_.node_count
    n_leaves = clf.get_n_leaves()
    actual_depth = clf.get_depth()
    
    # Display tree info as text
    info_text = f"""
๐ŸŒณ TREE STATISTICS
{'='*40}

Structure:
  โ€ข Total Nodes: {n_nodes}
  โ€ข Leaf Nodes: {n_leaves}
  โ€ข Actual Depth: {actual_depth}

Hyperparameters:
  โ€ข max_depth: {max_depth}
  โ€ข min_samples_split: {min_samples_split}
  โ€ข min_samples_leaf: {min_samples_leaf}

Performance:
  โ€ข Training Accuracy: {train_acc:.4f}
  โ€ข Test Accuracy: {test_acc:.4f}
  โ€ข Train-Test Gap: {gap:.4f}

Dataset:
  โ€ข Type: {dataset.upper()}
  โ€ข Training Samples: {len(X_train)}
  โ€ข Test Samples: {len(X_test)}
  โ€ข Noise Level: {noise:.2f}

Status: {status}
    """
    
    ax2.text(0.1, 0.5, info_text, transform=ax2.transAxes, 
            fontsize=11, verticalalignment='center',
            fontfamily='monospace',
            bbox=dict(boxstyle='round', facecolor='wheat', alpha=0.5))
    ax2.axis('off')
    
    plt.tight_layout()
    plt.show()
    
    # Recommendations
    print("\n" + "="*80)
    print("๐Ÿ’ก RECOMMENDATIONS")
    print("="*80)
    
    if gap > 0.15:
        print("\nโš ๏ธ High overfitting detected! Try these:")
        print(f"   1. Decrease max_depth (current: {max_depth}) โ†’ try {max(1, max_depth-2)}")
        print(f"   2. Increase min_samples_split (current: {min_samples_split}) โ†’ try {min_samples_split + 10}")
        print(f"   3. Increase min_samples_leaf (current: {min_samples_leaf}) โ†’ try {min_samples_leaf + 5}")
    elif gap < 0.02 and train_acc < 0.85:
        print("\n๐Ÿ“‰ Possible underfitting! Try these:")
        print(f"   1. Increase max_depth (current: {max_depth}) โ†’ try {max_depth + 2}")
        print(f"   2. Decrease min_samples_split (current: {min_samples_split}) โ†’ try {max(2, min_samples_split - 5)}")
        print(f"   3. Decrease min_samples_leaf (current: {min_samples_leaf}) โ†’ try {max(1, min_samples_leaf - 2)}")
    else:
        print("\nโœ… Model looks good! Current hyperparameters are reasonable.")
        print("   You could still fine-tune further if needed.")
    
    print("\n๐Ÿ’ญ General Tips:")
    print("   โ€ข Start with shallow trees (depth 3-5) and increase if needed")
    print("   โ€ข Watch the train-test gap more than absolute accuracy")
    print("   โ€ข Use cross-validation for more reliable estimates")
    print("   โ€ข More data helps reduce overfitting")
    print("="*80)

# Create interactive widget with all controls
print("\n๐ŸŽฎ INTERACTIVE DECISION TREE PLAYGROUND")
print("Use the sliders below to explore how different hyperparameters affect the tree!\n")

interact(tree_playground,
         max_depth=IntSlider(value=5, min=1, max=15, step=1, 
                            description='Max Depth:', 
                            style={'description_width': '150px'}),
         min_samples_split=IntSlider(value=2, min=2, max=50, step=2, 
                                     description='Min Samples Split:', 
                                     style={'description_width': '150px'}),
         min_samples_leaf=IntSlider(value=1, min=1, max=20, step=1, 
                                    description='Min Samples Leaf:', 
                                    style={'description_width': '150px'}),
         dataset=Dropdown(options=['moons', 'circles', 'xor'], value='moons', 
                         description='Dataset:', 
                         style={'description_width': '150px'}),
         noise=FloatSlider(value=0.25, min=0.1, max=0.5, step=0.05, 
                          description='Noise Level:', 
                          style={'description_width': '150px'}),
         n_samples=IntSlider(value=300, min=100, max=500, step=50, 
                            description='Sample Size:', 
                            style={'description_width': '150px'}));

๐ŸŽฎ INTERACTIVE DECISION TREE PLAYGROUND
Use the sliders below to explore how different hyperparameters affect the tree!

Summary and Key Takeaways

What We Explored:

  1. Demo 1 - XOR Problem: Linear methods fail on non-linear patterns, motivating decision trees

  2. Demo 2 - Tree Structure: How to read and interpret decision tree visualizations

  3. Demo 3 - Decision Boundaries: Trees create axis-aligned rectangular regions

  4. Demo 4 - Overfitting: The critical concept - deep trees memorize training data

  5. Demo 5 - Feature Importance: Understanding which features drive predictions

  6. Demo 6 - Grid Search: Systematic hyperparameter optimization

  7. Demo 7 - Method Comparison: When to use trees vs linear methods

  8. Bonus - Tree Playground: Free exploration of all parameters

Key Insights:

โœ… Trees excel at non-linear patterns where linear methods struggle

โœ… Overfitting is the main challenge - always monitor train-test gap

โœ… Start simple (depth 3-5) and increase complexity only if needed

โœ… Hyperparameters matter - max_depth, min_samples_split, min_samples_leaf

โœ… Interpretability is a superpower - can explain any prediction

Next Steps:

  1. Try these demos on your own datasets
  2. Experiment with different hyperparameter combinations
  3. Compare trees with other methods youโ€™ve learned
  4. Read lecture notes Section 8-9 for ensemble methods (MPS439)
  5. Prepare for Week 8: PCA and unsupervised learning!

Remember: The goal isnโ€™t to memorize formulas, but to build intuition through experimentation! ๐Ÿš€


Additional Exploration (Optional)

Try modifying the code above to: - Test on your own datasets - Add more evaluation metrics (precision, recall, F1-score) - Compare with Random Forests (ensemble method) - Visualize the effect of class imbalance - Implement cost-complexity pruning