ADA442

Trees, Forests & Ensembles

Decision Trees for Classification

Parameter Tuning for Decision Trees in Classification

Parameter tuning, also known as hyperparameter optimization, is the process of selecting the best set of hyperparameters for a machine learning model. In the context of Decision Trees for Classification, tuning these parameters can significantly improve the model's performance by balancing bias and variance, preventing overfitting, and enhancing generalization to unseen data.

Why Parameter Tuning Matters

Improves Model Performance: Properly tuned parameters can lead to higher accuracy, precision, recall, and other performance metrics.
Prevents Overfitting and Underfitting: Balancing model complexity ensures that the tree generalizes well to new data.
Enhances Model Interpretability: Simpler trees are easier to interpret without sacrificing performance.

Key Hyperparameters in Decision Trees for Classification

criterion
- Description: Determines the function to measure the quality of a split.
- Options:
  - "gini": Gini impurity.
  - "entropy": Information gain.
- Impact: Affects how splits are evaluated; different criteria can lead to different tree structures.
max_depth
- Description: The maximum depth of the tree.
- Default: None (nodes are expanded until all leaves are pure or contain fewer than min_samples_split samples).
- Impact: Controls the complexity of the tree. Lower values prevent overfitting but might underfit; higher values can capture more details but risk overfitting.
min_samples_split
- Description: The minimum number of samples required to split an internal node.
- Default: 2
- Impact: Higher values prevent the tree from creating splits that capture noise in the data, thus reducing overfitting.
min_samples_leaf
- Description: The minimum number of samples required to be at a leaf node.
- Default: 1
- Impact: Ensures that leaf nodes have a minimum number of samples, which can smooth the model and prevent overfitting.
max_features
- Description: The number of features to consider when looking for the best split.
- Options:
  - "auto": All features.
  - "sqrt": Square root of the number of features.
  - "log2": Logarithm base 2 of the number of features.
  - None: Same as "auto".
- Impact: Controls the randomness of the splits, which can help in reducing overfitting.
splitter
- Description: The strategy used to choose the split at each node.
- Options:
  - "best": Best split.
  - "random": Random split.
- Impact: Affects how the splits are made, potentially impacting tree structure and performance.
class_weight
- Description: Weights associated with classes.
- Options:
  - None: All classes have weight 1.
  - "balanced": Weights inversely proportional to class frequencies.
- Impact: Useful for handling imbalanced datasets by giving more importance to minority classes.

Techniques for Parameter Tuning

Grid Search
- Description: Exhaustively searches through a specified subset of hyperparameters.
- Pros: Simple to implement; explores all possible combinations.
- Cons: Computationally expensive, especially with many hyperparameters.
Random Search
- Description: Randomly samples hyperparameter combinations.
- Pros: More efficient than grid search; can find good solutions faster.
- Cons: Might miss the optimal combination.
Bayesian Optimization
- Description: Uses probabilistic models to predict promising hyperparameter regions.
- Pros: More efficient and can converge to optimal solutions with fewer evaluations.
- Cons: More complex to implement; requires additional libraries.
Automated Hyperparameter Tuning Libraries
- Examples:
  - Optuna
  - Hyperopt
  - Scikit-learn’s HalvingGridSearchCV and HalvingRandomSearchCV
- Pros: Streamlines the tuning process; often more efficient.
- Cons: May require learning new libraries or interfaces.

Extrapolation: refers to the process of making predictions or estimates for data points that lie outside the range of the training data. In contrast, interpolation involves predicting values within the range of the observed data.
Use Ensemble Methods: Ensemble techniques like Random Forests or Gradient Boosting combine multiple trees and average their predictions, reducing the sensitivity to individual splits.
min_samples_split parameter in a Decision Tree specifies the minimum number of samples required to split an internal node. It is a critical hyperparameter for controlling the complexity of the tree and preventing overfitting or underfitting.
Effect:
- Higher Values:
- Forces the tree to consider larger subsets of data for splitting.
- Leads to fewer splits, reducing the depth of the tree.
- Helps prevent overfitting by creating a simpler, more generalized tree.
- Lower Values:
- Allows more splits, increasing the depth of the tree.
- Can lead to overfitting, especially if small sample sizes are noisy.

Decision Trees for Classification

Decision Trees are widely used for classification tasks. The algorithm splits the dataset into subsets based on feature values to form a tree structure. The goal is to divide the data into pure subsets (where all data points belong to a single class) or subsets with minimal impurity.

Key Components in Classification

Impurity Measures: Used to decide the best feature and value for splitting the data.
- Gini Index: Gini= $^{'} 1 - \sum i = 1 C p i 2 G i n i = 1 - \sum_{i = 1}^{C} p_{i}^{2}$ where pip_i is the proportion of data points in class ii.
- Entropy: Entropy=−∑i=1Cpilog⁡2(pi)Entropy = -\sum_{i=1}^{C} p_i \log_2(p_i)
- Information Gain: Information Gain=Entropy(parent)−∑childrenNchildNparent×Entropy(child)Information\ Gain = Entropy(parent) - \sum_{children} \frac{N_{child}}{N_{parent}} \times Entropy(child)
- Gain Ratio: Adjusts Information Gain by considering the intrinsic information of a split.
Splitting Criterion: Based on impurity measures, the algorithm chooses the feature and threshold that result in the greatest reduction in impurity.
Stopping Criteria: To avoid overfitting, splitting stops when:
- A maximum tree depth is reached.
- The minimum number of samples in a node is below a threshold.
- A node is "pure" (contains data points from only one class).

Steps to Build a Classification Decision Tree

Start with the root node containing the entire dataset.
Evaluate possible splits on all features to maximize information gain or minimize impurity.
Split the data and create child nodes.
Repeat recursively until stopping criteria are met.
Assign a class label to each leaf node (the majority class in that node).

Advantages

Simple to interpret.
Handles both categorical and numerical features.
Works well for small to medium-sized datasets.

Disadvantages

Prone to overfitting, especially for complex datasets.
Can become biased toward features with more levels (e.g., numeric features).

Python Example: Decision Tree for Classification

Using scikit-learn:

from sklearn.datasets import load_iris
from sklearn.tree import DecisionTreeClassifier, plot_tree
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score

# Load dataset
data = load_iris()
X, y = data.data, data.target

# Split into training and testing sets
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)

# Create and train the decision tree
clf = DecisionTreeClassifier(criterion="gini", max_depth=3, random_state=42)
clf.fit(X_train, y_train)

# Predict and evaluate
y_pred = clf.predict(X_test)
accuracy = accuracy_score(y_test, y_pred)
print("Accuracy:", accuracy)

# Visualize the tree
import matplotlib.pyplot as plt
plt.figure(figsize=(12,8))
plot_tree(clf, feature_names=data.feature_names, class_names=data.target_names, filled=True)
plt.show()

Real-World Applications

Email Spam Detection: Classifying emails as spam or not.
Customer Churn Prediction: Identifying customers likely to leave a service.
Medical Diagnosis: Categorizing diseases based on symptoms.

Let me know if you'd like more examples, explanations, or help implementing this!

Categorical Data

Can split on categorical data directly

Intuitive way to split: split in two subsets

2 ^ n_values many possibilities

Possible to do in linear time exactly for gini index and binary

classi

Heuristics done in practice for multi-class.

(

Not in sklearn :

KMeans

centers.

Classic, simple. Only convex cluster shapes, determined by cluster

Agglomerative

Can take input topology into account, can produce hierarchy.

DBSCA

Arbitrary cluster shapes, can detect outliers, often very different sized

clusters.

Gaussian Mixture Models

Can model covariance, soft clustering, can be hard to