Decision Trees - Notes

Introduction to Decision Trees

  • Definition: Decision trees are intuitive machine learning algorithms used for both classification and regression tasks. They model decisions through a hierarchical tree structure.

  • Decision Tree Learning: A statistical modeling approach that utilizes decision trees and relies on splitting data based on features using an information metric.

Structure of a Decision Tree

  • Components:

    • Nodes: Comprised of root nodes, internal nodes, and leaf nodes.

    • Root Node: Represents the entire dataset before any splits are made.

    • Internal Nodes: Intermediate decision points based on specific features.

  • Example Structure: An example of a decision tree begins with a root node that asks a question (e.g., "Is the color red?"), followed by branches based on yes/no answers, leading to further internal nodes and ultimately leaf nodes indicating final predictions like fruit types (e.g., Apple or Orange).

Decision Tree Construction

  1. Root Node Selection: The dataset is initially represented at the root node. The first split is determined by the feature providing the most information gain.

    • Example Feature: Weather, chosen for its strong influence on jogging decisions.

  2. Branches: Each decision leads to branches representing the outcomes of the internal nodes.

  3. Leaf Nodes: Terminate the decision process, containing final predictions.

    • Classification Tasks: Leaf nodes hold class labels (e.g., "Jog" or "No Jog").

    • Regression Tasks: Leaf nodes may contain numerical predictions.

Examples of Features

  • Weather: Sunny, Cloudy, or Rainy.

  • Temperature: Hot, Mild, or Cold.

  • Humidity: High or Normal.

  • Wind: Strong or Weak.

Internal Decision Process

Sunny Weather Example

  1. First Internal Node: Checks temperature.

    • Outcomes:

      • Yes: Likely to Jog.

      • No: Further checks humidity.

  2. Cloudy Weather Example: Checks wind conditions.

  3. Rainy Weather Example: Checks humidity but unlikely to jog regardless of other factors.

Scenario Analysis

  • Scenario 1: Sunny Weather, Mild Temperature → Jog.

  • Scenario 2: Rainy Weather, High Humidity, Strong Wind → No Jog.

Splitting Criteria

  • The decision tree splits data at nodes based on criteria like Gini Index or Entropy:

For Classification Tasks

  • Gini Index: Measures impurity; the goal is to minimize it.

    • Formula: Gini Index = 1 - ∑(pi^2) where pi is the proportion of class i.

  • Entropy Comparison: Another measure used alongside Gini Index; aims to minimize impurity to achieve pure splits.

    • Formula: Entropy = -∑(pi log2(pi)).

For Regression Tasks

  • Mean Squared Error (MSE): Splitting criterion in regression trees.

    • Formula: MSE = 1/n ∑(yi - y^)^2 where yi are actual values and y^ is the mean.

Tree Depth and Overfitting

Tree Characteristics

  1. Shallow Trees (Depth = 2): Simpler with fewer decision levels; may generalize better but risk missing nuances.

  2. Deeper Trees (Depth = 4): Capture complex patterns but increase the risk of overfitting.

  • Overfitting: The tree learns training data intricacies that do not generalize to unseen data.

Key Takeaways on Tree Characteristics

  • Shallow Trees: Simpler, less prone to overfitting, but risk missing patterns.

  • Deeper Trees: Capture more complexity but risk overfitting and become harder to interpret.

  • Balancing Depth: Techniques like pruning and setting maximum depth help prevent overfitting.

Advantages and Disadvantages of Decision Trees

Advantages:

  • Interpretable and visualizable.

  • Handle both categorical and numerical data with minimal preprocessing.

Disadvantages:

  • Prone to overfitting.

  • Sensitive to data changes leading to different structures.

  • May struggle with high feature interaction complex datasets.

Implementation in Scikit-learn

  • The default models (DecisionTreeClassifier or DecisionTreeRegressor) utilize a greedy algorithm for root node selection and splitting.

Pruning Techniques

  1. Pre-pruning: Stops growth beyond a certain depth.

  2. Post-pruning: Allows full growth and removes unnecessary branches.

Parameters Influencing Root Node Selection

  1. Criterion: Measures split quality; defaults are "gini" for classification and "mse" for regression.

  2. max_depth: Limits tree depth to manage overfitting.

  3. min_samples_split: Minimum samples to split internal nodes.

  4. min_samples_leaf: Minimum samples at leaf nodes.

  5. max_features: Limits features for splitting.