Decision Tree

Classification Algorithms - Decision Tree

Introduction to Decision Trees

Decision Trees are versatile supervised learning algorithms used for both classification and regression tasks. They work by recursively partitioning the data based on feature values, creating a tree-like structure where:

• Internal Nodes: Represent tests on specific features (e.g., ‘Is glucose level > 120?’).
• Branches: Represent the outcome of a test (e.g., ‘Yes’ or ‘No’).
• Leaf Nodes (Terminal Nodes): Represent the final prediction (a class label in classification, or a continuous value in regression).

They are popular because they are relatively easy to understand and interpret, mimicking human decision-making processes.

Conceptually, imagine a flowchart for classifying fruits. A node might ask ‘Is the color Red?’. If yes, a branch leads to another node ‘Is the size < 5cm?’. If yes, a leaf node might predict ‘Cherry’. If no, another leaf might predict ‘Apple’.

Building a Decision Tree: Key Concepts

The core challenge is to determine the best feature and split point at each node to partition the data effectively. This is typically done by maximizing information gain or minimizing impurity.

Impurity Measures

Impurity measures quantify the ‘mixed-up-ness’ of class labels within a node. A node with only one class has zero impurity (it’s pure).

• Gini Impurity: Measures the probability of incorrectly classifying a randomly chosen element if it were randomly labeled according to the distribution of labels in the node. Ranges from 0 (pure) to 0.5 (maximum impurity for 2 classes). Formula: Gini = 1 - Σ(pᵢ)², where pᵢ is the proportion of instances of class i at the node.
• Entropy: Measures the uncertainty or randomness in the node. Ranges from 0 (pure) to log₂(num_classes). Formula: Entropy = - Σ(pᵢ * log₂(pᵢ)).

Common algorithms like CART (Classification and Regression Trees) often use Gini impurity, while ID3 and C4.5 use Entropy/Information Gain.

Splitting Criteria

At each node, the algorithm considers potential splits for all features. For a given feature, it might test various split points (for continuous features) or categories (for categorical features).

The best split is the one that results in the largest reduction in impurity (or highest Information Gain, which is based on entropy reduction). The gain is calculated as the impurity of the parent node minus the weighted average impurity of the child nodes resulting from the split.

Stopping Criteria & Pruning

If allowed to grow indefinitely, a decision tree can perfectly fit the training data, leading to overfitting. To prevent this, we need stopping criteria or pruning:

• Maximum Depth (max_depth): Limit the maximum number of levels in the tree.
• Minimum Samples per Split (min_samples_split): Require a minimum number of data points at a node before it can be split.
• Minimum Samples per Leaf (min_samples_leaf): Require a minimum number of data points in each leaf node.
• Maximum Leaf Nodes (max_leaf_nodes): Limit the total number of leaf nodes.
• Minimum Impurity Decrease (min_impurity_decrease): Only split if the impurity reduction exceeds a threshold.
• Pruning: Build a full tree first, then remove branches that provide little predictive power (e.g., Cost Complexity Pruning).

These are hyperparameters that need to be tuned (e.g., using GridSearchCV).

Implementation in Python (Scikit-learn)

Let’s implement a DecisionTreeClassifier using Scikit-learn on the Pima Indians Diabetes dataset.

Example

import pandas as pd
from sklearn.tree import DecisionTreeClassifier, plot_tree # Updated import for visualization
from sklearn.model_selection import train_test_split
from sklearn.metrics import classification_report, confusion_matrix, accuracy_score
from sklearn.datasets import fetch_openml
import matplotlib.pyplot as plt

# 1. Load Pima Indians Diabetes dataset
pima = fetch_openml(name='diabetes', version=1, as_frame=True, parser='pandas')
df = pima.frame
df.columns = ['num_pregnancies', 'glucose', 'bp', 'skin', 'insulin', 'bmi', 'pedigree', 'age', 'class']
# Ensure class is numeric
df['class'] = pd.to_numeric(df['class'])

# Define features and target
feature_cols = ['num_pregnancies', 'insulin', 'bmi', 'age', 'glucose', 'bp', 'pedigree']
X = df[feature_cols]
y = df['class']

# 2. Split dataset into training set and test set
# 70% training and 30% test
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.3, random_state=42)

# 3. Create Decision Tree Classifier object
# We can set hyperparameters here, e.g., max_depth=5 to prevent overfitting
clf = DecisionTreeClassifier(max_depth=5, random_state=42)

# 4. Train Decision Tree Classifier
clf = clf.fit(X_train, y_train)

# 5. Predict the response for test dataset
y_pred = clf.predict(X_test)

# 6. Evaluate Model
print("--- Model Evaluation ---")
conf_mat = confusion_matrix(y_test, y_pred)
print("Confusion Matrix:")
print(conf_mat)

class_rep = classification_report(y_test, y_pred)
print("\nClassification Report:")
print(class_rep)

acc_score = accuracy_score(y_test, y_pred)
print(f"\nAccuracy: {acc_score:.4f}")

# 7. Visualize the Decision Tree (optional, requires matplotlib)
plt.figure(figsize=(20,10))
plot_tree(clf,
          filled=True,
          rounded=True,
          class_names=['No Diabetes (0)', 'Diabetes (1)'], # Use string names for clarity
          feature_names=feature_cols,
          fontsize=10)
plt.title("Decision Tree Visualization (max_depth=5)")
# plt.savefig('pima_diabetes_tree.png') # Optional: save the figure
plt.show()

Output (Illustrative)

--- Model Evaluation ---
Confusion Matrix:
[[122  29]
 [ 37  43]]

Classification Report:
              precision    recall  f1-score   support

           0       0.77      0.81      0.79       151
           1       0.60      0.54      0.57        80

    accuracy                           0.71       231
   macro avg       0.68      0.67      0.68       231
weighted avg       0.71      0.71      0.71       231


Accuracy: 0.7143

The output shows the performance metrics for the decision tree with a maximum depth of 5. The accuracy is around 71.4%. The confusion matrix and classification report give more detail on performance per class. The code also generates a plot of the decision tree structure. (The plot would show a tree diagram with nodes showing the splitting criteria, impurity, samples, and predicted class).

Feature Importance

Decision trees (and tree-based ensembles) can provide estimates of feature importance, indicating which features were most useful for splitting the data. This is often based on the total reduction in impurity contributed by that feature across all splits in the tree.

# --- Feature Importance ---
importances = clf.feature_importances_
feature_importance_df = pd.DataFrame({'feature': feature_cols, 'importance': importances})
feature_importance_df = feature_importance_df.sort_values('importance', ascending=False)

print("\n--- Feature Importances ---")
print(feature_importance_df)

Output (Illustrative)

--- Feature Importances ---
         feature  importance
4        glucose       0.385
2            bmi       0.188
3            age       0.140
6       pedigree       0.111
0  num_pregnancies       0.077
5             bp       0.065
1        insulin       0.034

In this example run, ‘glucose’, ‘bmi’, and ‘age’ appear to be the most important features according to this specific tree.

Advantages and Disadvantages

Advantages

• Interpretability: Easy to understand and visualize the decision process.
• Minimal Data Prep: Often requires less data preparation (e.g., no need for feature scaling). Can handle both numerical and categorical data (though Scikit-learn requires numerical input).
• Non-linear Relationships: Can capture complex non-linear patterns in the data.
• Feature Importance: Implicitly performs feature selection and provides importance scores.

Disadvantages

• Overfitting: Prone to creating overly complex trees that don’t generalize well. Requires careful tuning (e.g., max_depth) or pruning.
• Instability: Small changes in the data can lead to a completely different tree structure.
• Bias: Can create biased trees if some classes dominate.
• Optimality: Finding the globally optimal decision tree is computationally infeasible (NP-hard), so algorithms use greedy approaches (locally optimal splits), which might not yield the best overall tree.

Due to the overfitting and instability issues, single decision trees are often replaced by ensemble methods like Random Forests or Gradient Boosting Trees in practice, which build upon the concepts of decision trees.

Further Resources

• Scikit-learn Decision Trees: https://scikit-learn.org/stable/modules/tree.html
• StatQuest: Decision Trees Explained: https://statquest.org/video-index/ (Search for Decision Trees)