📝 Decision Trees Pseudocode

ALGORITHM: Decision Tree Construction (Recursive)
─────────────────────────────────────────────────────────────────

INPUT:
    D: Dataset with features X and labels y
    features: Set of available features to split on
    max_depth: Maximum tree depth (stopping criterion)
    min_samples_split: Minimum samples required to split a node
    criterion: Splitting criterion ('gini', 'entropy', or 'mse')

OUTPUT:
    tree: Trained decision tree

FUNCTION build_tree(D, features, depth):
    
    1. // Check stopping conditions
       IF depth ≥ max_depth OR
          |D| < min_samples_split OR
          all labels in D are the same OR
          features is empty:
           
           // Create leaf node
           IF classification:
               RETURN LeafNode(prediction = majority_class(D))
           ELSE:  // regression
               RETURN LeafNode(prediction = mean(D.y))
    
    2. // Find the best split
       best_gain ← -∞
       best_feature ← None
       best_threshold ← None
       
       FOR each feature f in features:
           thresholds ← unique values or candidate splits for f
           
           FOR each threshold t in thresholds:
               // Split data
               D_left ← samples where X[f] ≤ t
               D_right ← samples where X[f] > t
               
               // Skip invalid splits
               IF |D_left| = 0 OR |D_right| = 0:
                   CONTINUE
               
               // Calculate information gain
               gain ← compute_gain(D, D_left, D_right, criterion)
               
               IF gain > best_gain:
                   best_gain ← gain
                   best_feature ← f
                   best_threshold ← t
    
    3. // If no valid split found, create leaf
       IF best_feature is None:
           RETURN LeafNode(prediction = majority_class(D) or mean(D.y))
    
    4. // Create internal node and recurse
       D_left ← samples where X[best_feature] ≤ best_threshold
       D_right ← samples where X[best_feature] > best_threshold
       
       left_child ← build_tree(D_left, features, depth + 1)
       right_child ← build_tree(D_right, features, depth + 1)
       
       RETURN DecisionNode(
           feature = best_feature,
           threshold = best_threshold,
           left = left_child,
           right = right_child
       )

MAIN:
    RETURN build_tree(D, all_features, depth = 0)

FUNCTION: Impurity Measures and Information Gain
─────────────────────────────────────────────────────────────────

GINI IMPURITY (Classification):
    Gini(D) = 1 - Σₖ pₖ²
    
    where pₖ = proportion of class k in D

ENTROPY (Classification):
    Entropy(D) = -Σₖ pₖ log₂(pₖ)
    
    where pₖ = proportion of class k in D

MEAN SQUARED ERROR (Regression):
    MSE(D) = (1/|D|) Σᵢ (yᵢ - ȳ)²
    
    where ȳ = mean of y values in D

INFORMATION GAIN:
    Gain(D, split) = Impurity(D) - weighted_avg(Impurity(D_left), Impurity(D_right))
    
    weighted_avg = (|D_left|/|D|) × Impurity(D_left) + 
                   (|D_right|/|D|) × Impurity(D_right)

ALGORITHM: Decision Tree Prediction
─────────────────────────────────────────────────────────────────

INPUT:
    x: Sample feature vector
    tree: Trained decision tree

OUTPUT:
    prediction: Predicted class or value

FUNCTION predict(x, node):
    
    // Base case: reached a leaf
    IF node is LeafNode:
        RETURN node.prediction
    
    // Recursive case: traverse based on split
    IF x[node.feature] ≤ node.threshold:
        RETURN predict(x, node.left)
    ELSE:
        RETURN predict(x, node.right)

MAIN:
    RETURN predict(x, tree.root)

ALGORITHM: Cost-Complexity Pruning (Minimal Cost-Complexity Pruning)
─────────────────────────────────────────────────────────────────

INPUT:
    tree: Fully grown decision tree
    X_val, y_val: Validation set
    α: Complexity parameter (regularization strength)

PROCEDURE:
    1. // Calculate cost-complexity for each subtree
       FOR each internal node in tree (bottom-up):
           
           // Cost of keeping subtree
           R(subtree) ← misclassification_rate(subtree, X_val, y_val)
           |leaves| ← number of leaves in subtree
           
           // Cost of pruning to single leaf
           R(leaf) ← misclassification_rate(majority_prediction, X_val, y_val)
           
           // Effective alpha for this node
           α_eff ← (R(leaf) - R(subtree)) / (|leaves| - 1)
           
           // Prune if complexity cost exceeds benefit
           IF α_eff ≤ α:
               Replace subtree with leaf node
    
    2. RETURN pruned tree

CATEGORICAL FEATURES:
    Option 1: One split per category value
    Option 2: Binary split (subset vs. complement)
    
MISSING VALUES:
    Option 1: Surrogate splits (use correlated features)
    Option 2: Fractional instances (send fraction down each branch)
    Option 3: Separate category for missing