A Beginner‘s Guide to Decision Tree Classification using Python

Decision trees are a popular machine learning algorithm used for both classification and regression tasks. They offer a powerful yet intuitive way to model complex decision-making processes. In this guide, we‘ll dive deep into decision trees for classification, covering the core concepts, implementation in Python, and advanced techniques.

What is a Decision Tree?

A decision tree is a flowchart-like structure that models a series of decisions and their possible outcomes. It consists of:

• Nodes: where a decision needs to be made based on an attribute
• Edges: the outcomes of a decision that connect to the next node
• Leaf nodes: terminal nodes that represent a final classification

Here‘s a simple example of a decision tree that classifies whether to play tennis based on the weather:

Decision trees learn by recursively splitting the training data into subsets based on the feature that best separates the classes. The goal is to create a tree where each leaf node contains samples from only one class.

How Decision Trees Make Splitting Decisions

At each node, the decision tree must decide which feature to split on and what threshold to use. There are several common criteria for evaluating the quality of a split:

Entropy and Information Gain

Entropy measures the impurity or randomness of a set of examples. The higher the entropy, the more mixed the classes are. The formula for entropy is:

$H(X) = -\sum_{i=1}^{n} P(x_i) \log_2 P(x_i)$

Where $X$ is a set of examples, $x_i$ is a class label, and $P(x_i)$ is the probability of an example having label $x_i$.

Information gain measures the reduction in entropy after splitting the data on a particular feature. The feature with the highest information gain is chosen for splitting.

The formula for information gain is:

$IG(X,F) = H(X) – \sum_{v \in Values(F)} \frac{|X_v|}{|X|} H(X_v)$

Where $F$ is a feature, $Values(F)$ is the set of possible values for $F$, $X_v$ is the subset of examples where feature $F$ has value $v$, and $|X|$ is the number of examples in set $X$.

Gini Impurity

Gini impurity is another common criterion that measures the probability of misclassifying a randomly chosen example if it were labeled randomly according to the class distribution. The formula is:

$Gini(X) = 1 – \sum_{i=1}^{n} P(x_i)^2$

Where the terms have the same meaning as in the entropy formula.

The feature that minimizes the weighted sum of the Gini impurity of the subsets is selected for splitting.

Other Splitting Criteria

Some other splitting criteria include:

• Classification error: $1 – \max_i P(x_i)$
• Variance reduction: used for regression trees
• Chi-square: for categorical features

The scikit-learn implementation of decision trees supports entropy, Gini impurity, and variance reduction.

Complexity of Decision Trees

The training time complexity of building a decision tree is $O(n{features}n{samples}\log n{samples})$ in the worst case. Predictions take $O(\log n{samples})$ time.

In practice, the actual training time is often much lower since the splits are chosen greedily and the algorithm terminates early due to stopping criteria like maximum depth.

The space complexity is $O(n_{samples})$ since the tree needs to store a constant amount of information for each sample.

Implementing a Decision Tree in Python

We‘ll use the popular scikit-learn library to build a decision tree classifier in Python. First, let‘s load the famous Iris dataset:

from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

iris = load_iris()
X = iris.data
y = iris.target

X_train, X_test, y_train, y_test = train_test_split(X, y, random_state=42)

Now we can create the decision tree classifier and train it:

from sklearn.tree import DecisionTreeClassifier

clf = DecisionTreeClassifier(criterion=‘entropy‘, max_depth=3, random_state=42)
clf.fit(X_train, y_train)

Here we‘ve set a few important hyperparameters:

• criterion=‘entropy‘ means to use entropy as the splitting criteria
• max_depth=3 limits the tree depth to prevent overfitting
• random_state=42 sets the random seed for reproducibility

We can evaluate the performance on the test set:

from sklearn.metrics import accuracy_score

y_pred = clf.predict(X_test)
accuracy = accuracy_score(y_test, y_pred)
print(f"Test Accuracy: {accuracy:.3f}")

Test Accuracy: 0.974

Over 97% accuracy, not bad! Let‘s visualize the learned decision tree:

from sklearn.tree import plot_tree

plt.figure(figsize=(12,8))
plot_tree(clf, filled=True, feature_names=iris.feature_names, class_names=iris.target_names)
plt.show()

We can see that the tree first splits on petal length, then petal width to separate the three Iris species. The numbers in the leaf nodes represent the distribution of classes.

Real-World Applications of Decision Trees

Decision trees are used across many domains for both classification and regression tasks. Some common applications include:

• Medical diagnosis: Decision trees can model the diagnostic process of diseases based on symptoms and test results. For example, the Wisconsin Breast Cancer dataset has been used to predict whether a tumor is malignant or benign based on cell measurements.

• Credit risk assessment: Banks and financial institutions use decision trees to determine the creditworthiness of loan applicants based on factors like income, debt, and credit history. The Give Me Some Credit dataset on Kaggle contains data on 150,000 borrowers for this task.

• Customer churn prediction: Businesses can use decision trees to identify customers at risk of churning based on their usage patterns and interactions. The Telco Customer Churn dataset is a popular benchmark for this problem.

• Fraud detection: Decision trees can learn patterns that indicate fraudulent activities in online transactions, insurance claims, etc. Kaggle‘s Credit Card Fraud Detection dataset is an example where the goal is to identify fraudulent transactions.

Advanced Techniques for Decision Trees

There are several strategies to optimize and enhance decision trees:

Ensemble Methods

Ensemble methods combine multiple individual models to make a more robust final prediction. The two main ensemble approaches for decision trees are:

1. Bagging (Bootstrap Aggregating): Trains many decision trees on random subsets of the data and combines their predictions through averaging or voting. Random forests are a popular implementation of bagging.

2. Boosting: Trains a sequence of weak decision trees where each tree learns to correct the mistakes of the previous ones. Examples include AdaBoost, Gradient Boosting Machines (GBM), and XGBoost.

Ensemble methods often outperform individual decision trees, as can be seen in these benchmark results on the Give Me Some Credit dataset:

Model	Accuracy	AUC
Decision Tree	0.859	0.71
Random Forest	0.862	0.75
Gradient Boosted Trees	0.867	0.79

Handling Missing Data

Decision trees can naturally handle missing data by treating it as a separate branch. Common strategies are to:

• Route missing values to the most common branch
• Assign the most common label of examples with missing values
• Assign a probability score based on the proportion of different labels

The scikit-learn implementation automatically learns which strategy to use based on the data.

Cost-Complexity Pruning

Pruning reduces the size of a decision tree by removing branches that provide little predictive power. Cost-complexity pruning balances the tradeoff between the size of the tree and its accuracy on the training set.

The algorithm starts with the full tree and recursively collapses internal nodes that lead to the smallest increase in error. The hyperparameter $\alpha$ controls the tradeoff.

Oblique Decision Trees

Traditional decision trees make axis-parallel splits, meaning they split on a single feature at a time. Oblique decision trees allow for multivariate splits that combine multiple features.

Oblique trees are more flexible and can model interactions between features, but are also more prone to overfitting. Some popular oblique tree algorithms are OC1 (Oblique Classifier 1) and CART-LC (CART with Linear Combinations).

Interpreting Decision Trees

One of the main advantages of decision trees is their interpretability. We can extract knowledge about the most informative features and decision rules from a trained tree.

Feature Importance

Feature importance measures how useful each feature was in constructing the tree. It is calculated by the total reduction in impurity brought by splits on that feature, averaged over all trees in an ensemble.

In scikit-learn, we can access feature importances through the .feature_importances_ attribute:

importances = clf.feature_importances_
indices = np.argsort(importances)[::-1]

plt.figure(figsize=(8,5))
plt.title("Feature Importances")
plt.bar(range(X.shape[1]), importances[indices])
plt.xticks(range(X.shape[1]), iris.feature_names[indices], rotation=20)
plt.show()

We can see that petal length and width were the most informative features for classifying Iris species.

Decision Rules

We can also extract the decision rules that the tree learned. Each path from the root to a leaf forms an IF-THEN rule:

from sklearn.tree import export_text

rules = export_text(clf, feature_names=iris.feature_names)
print(rules)

|--- petal length (cm) <= 2.45
|   |--- class: 0
|--- petal length (cm) >  2.45
|   |--- petal width (cm) <= 1.75
|   |   |--- petal length (cm) <= 4.95
|   |   |   |--- class: 1
|   |   |--- petal length (cm) >  4.95
|   |   |   |--- class: 2
|   |--- petal width (cm) >  1.75
|   |   |--- class: 2

These rules provide a clear explanation of how the tree makes its predictions.

The Future of Decision Trees

Despite the recent surge in popularity of deep learning, decision trees remain a vital tool in the machine learning practitioner‘s toolkit. Some recent developments and future directions for decision trees include:

• Gradient Boosted Decision Trees (GBDT): GBDTs have achieved state-of-the-art results on structured data and are widely used in industry. Frameworks like XGBoost, LightGBM, and CatBoost have made them more scalable and efficient.

• Automatic Feature Interaction Discovery: Decision trees can naturally model interactions between features, which is important for datasets with many categorical variables. Techniques like Fast Interaction Tests (FIT) and RuleFit use decision trees to automatically discover important feature interactions.

• Hybrid Models: There has been increasing interest in combining decision trees with deep learning models, e.g. using a GBDT to extract features for a neural network. This approach has shown promising results on tabular datasets.

• Interpretable AI: As machine learning is increasingly applied to high-stakes domains like healthcare and finance, there is a growing need for interpretable models. Decision trees are a key component of many interpretable AI systems due to their transparency and explicit decision rules.

Conclusion

Decision trees are a powerful yet intuitive algorithm for classification and regression tasks. They offer several advantages:

• Simple to understand and interpret
• Can handle categorical and numerical features
• Automatically discover feature interactions
• Robust to outliers and missing data

However, they also have some limitations:

• Prone to overfitting without proper regularization
• May create complex trees that don‘t generalize well
• Sensitive to small changes in the data
• Biased towards features with many levels

By using ensemble methods, pruning, and other optimization techniques, many of these issues can be mitigated. Decision trees are widely used across industries for applications like fraud detection, medical diagnosis, and customer churn prediction.

As machine learning continues to evolve, decision trees will undoubtedly remain an essential part of the toolkit. Exciting developments in GBDTs, hybrid models, and interpretable AI will make them even more powerful and applicable to real-world problems.

I encourage you to experiment with decision trees on your own datasets and see their impressive results firsthand. You can find plenty of resources to dive deeper, such as:

• The scikit-learn documentation on decision trees
• This excellent course on machine learning by Andrew Ng
• The seminal book Classification and Regression Trees by Breiman, Friedman, Stone, and Olshen

Decision trees embody the core principles of machine learning: to learn meaningful patterns from data in a transparent and interpretable way. By mastering this essential technique, you‘ll be well-equipped to tackle a wide range of real-world problems and drive valuable insights. Happy learning!