Overview
Decision trees are a supervised learning algorithm used for both classification and regression tasks. They work by recursively splitting the data based on feature values to create a tree-like structure of decisions.
How It Works
- Start with the entire dataset at the root node
- Find the best feature to split on (using criteria like Gini impurity or entropy)
- Create branches for each possible value of that feature
- Repeat recursively for each branch until a stopping condition is met
- Assign predictions to leaf nodes based on the majority class (classification) or mean value (regression)
Key Concepts
Splitting Criteria
For Classification:
- Gini Impurity: Measures the probability of incorrectly classifying a randomly chosen element
- Entropy (Information Gain): Measures the amount of disorder or uncertainty in the data
For Regression:
- Variance Reduction: Minimize the variance of the target variable in each split
Stopping Conditions
- Maximum depth reached
- Minimum samples per leaf
- Minimum samples required to split
- All data points in a node belong to the same class
- No further information gain
Handling Missing Values
See Decision Tree - Missing And Unknown Values.
Advantages
- Interpretable: Easy to understand and visualize
- No feature scaling needed: Works with features on different scales
- Handles both numerical and categorical data
- Non-parametric: Makes no assumptions about data distribution
- Captures non-linear relationships
- Automatic feature selection: Only uses important features
Disadvantages
- Prone to overfitting: Can create overly complex trees
- Unstable: Small changes in data can lead to very different trees
- Biased towards features with many levels
- Not optimal for regression: Predicts step-wise constant values
- Greedy algorithm: May not find globally optimal tree
Hyperparameters
| Parameter | Description | Effect |
|---|---|---|
| max_depth | Maximum depth of tree | Higher → more complex, prone to overfitting |
| min_samples_split | Minimum samples to split a node | Higher → simpler tree |
| min_samples_leaf | Minimum samples in a leaf | Higher → smoother decision boundaries |
| max_features | Number of features to consider for split | Lower → more randomness, less overfitting |
| criterion | Split quality measure (gini, entropy) | Affects which feature is chosen |
Ensemble Methods
See Decision Tree - Ensemble Methods.
Practical Example
Classification (Majority Vote)
Training data at leaf:
- Class A: 7 samples
- Class B: 3 samples
Prediction: Class A (majority)
Regression (Mean Value)
Training data at leaf:
- Values: [10, 12, 15, 13, 11]
Prediction: 12.2 (mean)
When to Use
Use Decision Trees when:
- Interpretability is crucial
- Data has mix of categorical and numerical features
- You need a quick baseline model
- Non-linear relationships exist
Avoid Decision Trees when:
- You need high accuracy (use ensembles instead)
- Data is high-dimensional and sparse
- Linear relationships dominate (use linear models)
References
- Scikit-learn documentation
- Introduction to Statistical Learning (ISLR)