A Complete Tutorial on Tree Based Modeling from Scratch in Python

Tree based modeling algorithms are some of the most widely used supervised machine learning methods today. Tree based models offer several advantages including high predictive accuracy, ability to capture non-linear relationships, fast training times on large datasets, and ease of interpretation compared to other black-box models.

In this in-depth tutorial, we‘ll dive into the details of how tree based algorithms work, the different types of tree based models, and how to implement them from scratch using Python. By the end, you‘ll have a solid understanding of tree based modeling and be equipped to apply these powerful techniques to real-world problems.

Introduction to Tree Based Models

Tree based models belong to the family of supervised machine learning algorithms. They can be used to solve both regression and classification problems. As the name suggests, tree based methods involve segmenting the predictor space into a number of simple regions using decision trees.

The core idea is to split the data into subsets containing the most similar data points, and then fit a simple model (like a constant) to each subset. By repeating this recursive partitioning process, very complex relationships can be learned.

Some key advantages of tree based models include:

• Ability to capture non-linear relationships between features and target
• Handle categorical and numerical features without scaling/normalization
• Automatically perform feature selection
• Robust to outliers and missing data
• Outputs are easy to visualize and interpret
• Computationally efficient to train and predict on large datasets

Now that we have an intuitive understanding of tree based modeling, let‘s examine the key types of tree based algorithms in more detail.

Decision Trees

Decision trees are the fundamental building block that more sophisticated tree based models are composed of. A decision tree works by recursively partitioning the data into subsets, and then fitting a simple model to each subset.

The partitioning is done through a greedy algorithm that selects the best split point at each node based on some criteria. For classification trees, metrics like Gini impurity or information gain are used to evaluate splits. For regression trees, a metric like mean squared error (MSE) is used.

Here‘s a simplified algorithm for building a decision tree:

1. Start at the root node containing all training data
2. Find the feature and split point that produces the largest reduction in impurity/error if split on
3. Split the data into child nodes based on the selected split
4. Repeat steps 2-3 recursively on the child nodes until a stopping criteria is reached (e.g. maximum depth, minimum samples per leaf)
5. Assign each leaf node a predicted class (classification) or value (regression) based on majority class or mean of training samples in that leaf

To make a prediction for a new data point, we start at the root and follow the decision rules at each node based on the feature values until reaching a leaf node. The leaf node contains the predicted output.

Some advantages of decision trees are that they require little data preprocessing, can handle both numerical and categorical data, and are easy to interpret and visualize. They are also quite robust to outliers and irrelevant features.

However, decision trees tend to overfit the training data if grown too deep. They also suffer from high variance, as small changes in the training data can lead to very different trees. Techniques like setting maximum depth, minimum samples per leaf, and pruning can help limit overfitting. We‘ll see that ensemble methods can reduce variance.

Random Forests

Random forests are an ensemble learning method that combines the predictions of many individual decision trees to produce a more accurate and stable prediction. The key idea is that a large number of uncorrelated trees operating as a committee will outperform any of the individual trees.

Here‘s how the random forest algorithm works:

1. Create a bootstrapped dataset by sampling N instances with replacement from the original training set
2. Train a decision tree on the bootstrapped dataset, but at each node:
   • Randomly select m features (typically m = sqrt(total features))
   • Only allow splits on one of the m selected features
3. Repeat steps 1-2 to create a "forest" of trees
4. To make a prediction, take the majority vote (classification) or average (regression) of all trees

The random sampling of instances (aka bootstrapping) and random feature selection serve to decorrelate the individual trees. This leads to more diversity and lower variance in the final model.

Random forests have several compelling advantages:

• Reduce overfitting and variance compared to decision trees
• Handle high dimensional data well
• Provide a built-in estimate of feature importance
• Require little hyperparameter tuning
• Embarrassingly parallel training

The main drawbacks are reduced interpretability and slower prediction times compared to a single tree due to the large number of trees.

Gradient Boosting Machines (GBM)

Gradient boosting is another ensemble method that combines many weak learners (typically decision trees) into a strong learner in an iterative fashion.

The key idea is to train each new tree to predict the residual errors made by the previous trees. Residual errors are the differences between the true target values and the predictions of the current ensemble. By focusing each new tree on the mistakes of its predecessors, the model can progressively improve and eventually fit complex relationships.

Here‘s a high-level sketch of the gradient boosting algorithm:

1. Initialize the model with a single leaf containing the average target value
2. For M iterations:
   • Compute the negative gradients (residual errors) of the current model
   • Train a new tree to predict the negative gradients using the current features
   • Add the new tree to the ensemble model, weighted by a learning rate
3. Output the final ensemble model

The learning rate controls the contribution of each new tree and serves to regularize the model. Smaller learning rates will require more trees but can lead to better generalization.

Some key advantages of GBMs are:

• Consistently outperform other models on structured data
• Highly flexible and can optimize any differentiable loss function
• Provide a feature importance score like random forests
• Built-in regularization with learning rate and early stopping
• Handle missing data and outliers well

The main downsides are that GBMs require careful tuning of the hyperparameters and can be quite sensitive to noisy data and outliers. They are also slower to train than random forests.

XGBoost

XGBoost is an optimized implementation of gradient boosting that has become very popular in recent years, particularly in Kaggle competitions. XGBoost stands for "extreme gradient boosting".

XGBoost builds upon the basic GBM algorithm with several enhancements:

• Regularization: L1 and L2 regularization terms are added to the loss function to reduce overfitting
• Second-order gradients: A Taylor approximation of the loss function is used to incorporate second-order gradient information, leading to faster convergence
• Weighted quantile sketch: An approximate algorithm is used to find candidate split points, improving speed on large datasets
• Sparsity awareness: The algorithm is designed to handle sparse data efficiently
• Parallel processing: Training can be parallelized across multiple CPU cores
• Handling missing values: Default direction for missing values can be learned
• Continued training: New iterations can be appended to an existing model

With its many optimizations and robust performance, XGBoost has become the go-to model for many tabular data problems. It is also available in highly efficient implementations across many languages.

Implementing Tree Based Models in Python

Now that we understand the theory behind the different tree based algorithms, let‘s see how to implement them in Python. We‘ll use the popular scikit-learn library for decision trees, random forests, and GBMs. For XGBoost, we‘ll import its custom library.

First, let‘s generate a synthetic classification dataset to work with:

from sklearn.datasets import make_classification

X, y = make_classification(n_samples=1000, n_features=10, 
                           n_informative=5, n_redundant=0,
                           random_state=42)

This creates a binary classification problem with 1000 samples, 10 features, and 5 informative features. We set a random seed for reproducibility.

Next, let‘s split the data into training and test sets:

from sklearn.model_selection import train_test_split

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

We use a 80/20 train/test split.

Now, let‘s train a decision tree classifier:

from sklearn.tree import DecisionTreeClassifier

dt = DecisionTreeClassifier(max_depth=5, random_state=42)
dt.fit(X_train, y_train)

print(f"Decision tree accuracy: {dt.score(X_test, y_test):.3f}")

We limit the maximum depth to 5 to avoid overfitting. Increasing max_depth will improve training accuracy but likely reduce test accuracy.

Let‘s visualize the learned tree:

from sklearn import tree
import matplotlib.pyplot as plt

fig, ax = plt.subplots(figsize=(15, 10))
tree.plot_tree(dt, filled=True, 
               feature_names=[f"X{i}" for i in range(10)],
               class_names=["0", "1"],
               ax=ax)

This plots the decision tree, showing the split points and predicted class at each node.

Now let‘s train a random forest:

from sklearn.ensemble import RandomForestClassifier

rf = RandomForestClassifier(n_estimators=100, max_depth=5, random_state=42)  
rf.fit(X_train, y_train)

print(f"Random forest accuracy: {rf.score(X_test, y_test):.3f}")

We use 100 trees and the same max_depth as before. See how the accuracy improves over the single decision tree.

We can visualize the feature importances:

def plot_feature_importance(model):
    n_features = X.shape[1]
    plt.figure(figsize=(8,8))
    plt.barh(range(n_features), model.feature_importances_, align=‘center‘)
    plt.yticks(np.arange(n_features), [f"X{i}" for i in range(n_features)])
    plt.xlabel("Feature importance")
    plt.ylabel("Feature")

plot_feature_importance(rf)

The feature importances reflect how useful each feature was in making predictions. Features used at the top of trees are generally more important.

Next, let‘s train a GBM classifier:

from sklearn.ensemble import GradientBoostingClassifier

gbm = GradientBoostingClassifier(n_estimators=100, learning_rate=0.1, 
                                 max_depth=3, random_state=42)
gbm.fit(X_train, y_train)

print(f"GBM accuracy: {gbm.score(X_test, y_test):.3f}")

The key hyperparameters are n_estimators, learning_rate, and max_depth. Increasing n_estimators usually improves performance but takes longer to train. learning_rate controls the contribution of each tree – lower values require more trees but can generalize better. Decreasing max_depth helps regularize the model.

Finally, let‘s train an XGBoost model:

from xgboost import XGBClassifier

xgb = XGBClassifier(n_estimators=100, learning_rate=0.1, max_depth=3,
                    subsample=0.8, colsample_bytree=0.8, 
                    random_state=42)
xgb.fit(X_train, y_train)

print(f"XGBoost accuracy: {xgb.score(X_test, y_test):.3f}")

In addition to the GBM hyperparameters, XGBoost has subsample for row subsampling and colsample_bytree for column subsampling. These serve as additional regularization.

To optimize the hyperparameters, we can use grid search cross validation:

from sklearn.model_selection import GridSearchCV

param_grid = {
    ‘max_depth‘: [3, 5, 7],
    ‘learning_rate‘: [0.1, 0.01, 0.05],
    ‘n_estimators‘: [50, 100, 200],
    ‘subsample‘: [0.8, 1],
    ‘colsample_bytree‘: [0.8, 1]
}

xgb = XGBClassifier(random_state=42) 
grid_search = GridSearchCV(estimator=xgb, param_grid=param_grid, 
                           cv=5, scoring=‘accuracy‘, verbose=1)
grid_search.fit(X_train, y_train)

print(f"Best accuracy: {grid_search.best_score_:.3f}")
print(f"Best parameters: {grid_search.best_params_}")

This exhaustively searches over the specified hyperparameter values using 5-fold cross validation and returns the best combination found.

Some tips for tree based models:

• Tree based models generally require less data preprocessing (scaling, encoding) compared to other models
• They can handle a mix of categorical and numerical features
• They are fairly robust to outliers but can benefit from removing them
• Start with a small number of trees and a high learning rate, then increase trees and reduce learning rate if needed
• Use early stopping to prevent overfitting by monitoring validation error during training
• Ensemble tree methods are almost always preferable to a single decision tree
• Random forests are very robust and great as a first model to try
• Gradient boosting and XGBoost tend to have the highest performance if tuned well

Conclusion

In this tutorial, we explored tree based machine learning algorithms in depth. We started with the basic decision tree and then looked at ensemble methods like random forests and gradient boosting. We discussed the advantages and tradeoffs of each approach.

We then implemented the tree based models in Python using scikit-learn and the XGBoost library. We saw how to train the models, make predictions, evaluate performance, visualize the learned trees and feature importances, and tune the hyperparameters.

Tree based methods are among the most powerful and widely used techniques in machine learning today. Their flexibility, scalability, and robustness make them invaluable tools to have in your modeling arsenal.

Some common use cases for tree based models include:

• Tabular data prediction problems (e.g. predicting customer churn, credit default risk, fraud detection)
• Feature selection and importance ranking
• Handling missing data through surrogate splits
• Multiclass classification

While tree based models have proven very effective, there are some limitations to be aware of:

• Performance can degrade on very high dimensional sparse data (like text)
• They cannot extrapolate to feature values outside the training data range
• Deeper trees are harder to interpret than shallow ones
• Training can be memory intensive for large datasets

Despite these limitations, tree based models remain an essential part of the practitioner‘s toolkit and an area of active research. Recent advances like feature interactions, dropout regularization, and differentiable trees show that there are still gains to be made.

I hope this tutorial has given you a solid foundation in tree based modeling. The best way to deepen your understanding is to practice on real datasets. Kaggle and the UCI Machine Learning Repository are great places to find datasets. Happy modeling!