Machine Learning Pruning Techniques: Minimum Error Pruning

This blog explains what minimum error pruning is and how it can reduce the error rate of a decision tree. It also provides an example and discusses the benefits and limitations of this pruning technique.

Table of Contents

1. Introduction

Decision trees are one of the most popular and widely used machine learning algorithms for classification and regression tasks. They are easy to understand, interpret, and implement, and can handle both numerical and categorical data. However, decision trees also have some drawbacks, such as overfitting, high variance, and instability.

Overfitting is a common problem in machine learning, where a model learns the training data too well and fails to generalize to new and unseen data. Overfitting can result in high error rates on the test data, which is the data that we want to make accurate predictions on. One way to reduce overfitting and improve the performance of decision trees is to use pruning techniques.

Pruning is a process of reducing the size and complexity of a decision tree by removing some of its branches or nodes. Pruning can help to avoid overfitting, reduce the variance and noise, and improve the interpretability and efficiency of the decision tree. There are different types of pruning techniques, such as pre-pruning, post-pruning, reduced error pruning, cost complexity pruning, and minimum error pruning.

In this blog, we will focus on one of the simplest and most effective pruning techniques: minimum error pruning. We will explain what minimum error pruning is, how it works, and how to apply it to a decision tree. We will also provide an example of minimum error pruning using Python and scikit-learn, and discuss the benefits and limitations of this technique.

By the end of this blog, you will be able to use minimum error pruning to reduce the error rate of your decision tree and improve its performance. Let’s get started!

2. Decision Trees and Error Rate

In this section, we will review some basic concepts of decision trees and error rate, which are essential for understanding minimum error pruning. We will explain how to build a decision tree from a given dataset, how to measure the error rate of a decision tree, and what factors can affect the error rate.

A decision tree is a graphical representation of a series of decisions and their outcomes. It consists of nodes and branches, where each node represents a test or a condition on a feature, and each branch represents an outcome or a decision. The root node is the first node in the tree, and the leaf nodes are the final nodes that contain the predicted class or value.

To build a decision tree, we need to have a dataset with features and labels. The features are the attributes or variables that describe the data, and the labels are the classes or values that we want to predict. For example, if we want to build a decision tree to classify whether a person has diabetes or not, the features could be age, gender, blood pressure, blood sugar, etc., and the label could be diabetes (yes or no).

There are different algorithms for building a decision tree, such as ID3, C4.5, CART, etc. The general idea is to start with the root node and split the data based on the feature that best separates the classes or minimizes the error. This process is repeated recursively for each subset of the data until a stopping criterion is met, such as reaching a maximum depth, a minimum number of samples, or a minimum error.

One of the most important aspects of a decision tree is its error rate, which is the proportion of incorrect predictions made by the tree. The error rate can be measured on different sets of data, such as the training set, the validation set, or the test set. The training set is the data that is used to build the tree, the validation set is the data that is used to tune the parameters of the tree, and the test set is the data that is used to evaluate the performance of the tree.

The error rate of a decision tree can be affected by various factors, such as the size and complexity of the tree, the quality and quantity of the data, the noise and variance in the data, the choice of the splitting criterion, the pruning technique, etc. Generally speaking, a larger and more complex tree tends to have a lower error rate on the training set, but a higher error rate on the test set, due to overfitting. A smaller and simpler tree tends to have a higher error rate on the training set, but a lower error rate on the test set, due to underfitting.

The goal of building a decision tree is to find the optimal balance between the error rate on the training set and the error rate on the test set, which is also known as the bias-variance trade-off. This is where pruning techniques come in handy, as they can help to reduce the size and complexity of the tree and improve its generalization ability.

Now that we have a basic understanding of decision trees and error rate, let’s move on to the next section and learn about minimum error pruning, one of the simplest and most effective pruning techniques.

2.1. How to Build a Decision Tree

In this section, we will show you how to build a decision tree from a given dataset using Python and scikit-learn. We will use the diabetes dataset from the UCI Machine Learning Repository, which contains 768 instances of female patients with 8 features and 1 binary label (diabetes or not).

The first step is to import the necessary libraries and load the dataset. We will use pandas to read the data from a CSV file and store it in a dataframe. We will also use numpy to perform some numerical operations and matplotlib to visualize the data.

# Import libraries
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt

# Load the dataset
url = "https://archive.ics.uci.edu/ml/machine-learning-databases/pima-indians-diabetes/pima-indians-diabetes.data"
columns = ["pregnancies", "glucose", "blood_pressure", "skin_thickness", "insulin", "bmi", "diabetes_pedigree", "age", "diabetes"]
df = pd.read_csv(url, header=None, names=columns)

The next step is to explore the data and check for any missing or invalid values. We can use the info() and describe() methods to get some basic information and statistics about the data. We can also use the isnull() and sum() methods to count the number of missing values in each column.

# Explore the data
df.info()
df.describe()
df.isnull().sum()

We can see that the data has 768 rows and 9 columns, and there are no missing values. However, we can also notice that some columns have zero values that are not valid, such as glucose, blood pressure, skin thickness, insulin, and bmi. These values need to be replaced or removed, as they can affect the performance of the decision tree. For simplicity, we will replace them with the mean value of each column.

# Replace zero values with mean values
zero_columns = ["glucose", "blood_pressure", "skin_thickness", "insulin", "bmi"]
for col in zero_columns:
    df[col] = df[col].replace(0, df[col].mean())

The final step before building the decision tree is to split the data into features and labels, and then into training and test sets. We will use the values attribute to convert the dataframe into a numpy array, and then use the iloc method to select the columns. We will use the train_test_split function from scikit-learn to split the data randomly with a 80/20 ratio.

# Split the data into features and labels
X = df.values[:, :-1] # all columns except the last one
y = df.values[:, -1] # the last column

# 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)

Now we are ready to build the decision tree using the DecisionTreeClassifier class from scikit-learn. We will use the default parameters, which include the gini criterion for splitting, the best strategy for choosing the split, and no limit on the depth, number of samples, or number of features. We will fit the model on the training set and then make predictions on the test set.

# Build the decision tree
from sklearn.tree import DecisionTreeClassifier
dt = DecisionTreeClassifier()
dt.fit(X_train, y_train)

# Make predictions on the test set
y_pred = dt.predict(X_test)

To evaluate the performance of the decision tree, we will use the accuracy_score function from scikit-learn to compute the proportion of correct predictions on the test set. We will also use the plot_tree function from scikit-learn to visualize the decision tree and see its structure and rules.

# Evaluate the performance of the decision tree
from sklearn.metrics import accuracy_score
accuracy = accuracy_score(y_test, y_pred)
print(f"Accuracy: {accuracy}")

# Visualize the decision tree
from sklearn.tree import plot_tree
plt.figure(figsize=(12, 8))
plot_tree(dt, feature_names=columns[:-1], class_names=["No", "Yes"], filled=True)
plt.show()

The output of the code is as follows:

Accuracy: 0.7337662337662337

We can see that the decision tree has an accuracy of 0.7338 on the test set, which means that it correctly predicts the diabetes status of about 73% of the patients. We can also see that the decision tree has 31 nodes and 16 leaves, and that it uses different features and thresholds to split the data. For example, the root node splits the data based on the glucose level, and the leftmost leaf node predicts that a patient has diabetes if they have more than 6.5 pregnancies, a glucose level higher than 127.5, and a bmi higher than 29.95.

This is how we can build a decision tree from a given dataset using Python and scikit-learn. However, this decision tree may not be optimal, as it may suffer from overfitting, high variance, and instability. To improve the performance of the decision tree, we can use pruning techniques, such as minimum error pruning, which we will discuss in the next section.

2.2. How to Measure the Error Rate of a Decision Tree

In this section, we will explain how to measure the error rate of a decision tree and how it can vary depending on the data set and the pruning technique. We will also introduce the concept of a hold-out set, which is a subset of the data that is used to evaluate the effect of pruning on the error rate.

The error rate of a decision tree is the proportion of incorrect predictions made by the tree on a given data set. For example, if a decision tree makes 20 wrong predictions out of 100, its error rate is 0.2 or 20%. The error rate can be computed using the accuracy_score function from scikit-learn, as we did in the previous section.

However, the error rate of a decision tree is not a fixed value, as it can change depending on the data set and the pruning technique. For instance, the error rate on the training set is usually lower than the error rate on the test set, because the decision tree is built to fit the training data as well as possible. However, this may lead to overfitting, which means that the decision tree is too complex and does not generalize well to new and unseen data. Therefore, the error rate on the test set is a better indicator of the performance of the decision tree.

Moreover, the error rate of a decision tree can also change depending on the pruning technique. Pruning is a process of reducing the size and complexity of a decision tree by removing some of its branches or nodes. Pruning can help to avoid overfitting, reduce the variance and noise, and improve the interpretability and efficiency of the decision tree. However, pruning can also affect the error rate of the decision tree, as it may remove some useful information or introduce some bias.

To measure the effect of pruning on the error rate of a decision tree, we need to use a hold-out set, which is a subset of the data that is not used for building or testing the decision tree, but only for evaluating the pruning technique. The hold-out set is usually a part of the training set that is separated before building the decision tree. The hold-out set is also known as the validation set or the pruning set.

The idea of using a hold-out set is to compare the error rate of the decision tree before and after pruning on the same data set. If the error rate of the pruned tree is lower than the error rate of the original tree, then the pruning technique is effective and improves the performance of the decision tree. If the error rate of the pruned tree is higher than the error rate of the original tree, then the pruning technique is not effective and worsens the performance of the decision tree.

In the next section, we will introduce one of the simplest and most effective pruning techniques: minimum error pruning. We will explain what minimum error pruning is, how it works, and how to apply it to a decision tree using a hold-out set.

3. Minimum Error Pruning

Minimum error pruning is one of the simplest and most effective pruning techniques for decision trees. It is a post-pruning technique, which means that it is applied after the decision tree is fully grown. The goal of minimum error pruning is to find the smallest subtree of the original tree that has the lowest error rate on the hold-out set.

The idea of minimum error pruning is to start from the bottom of the tree and prune each node that does not increase the error rate on the hold-out set. To prune a node, we replace it with a leaf node that has the most common class or the average value of the subtree. We then compare the error rate of the pruned tree with the error rate of the original tree on the hold-out set. If the error rate of the pruned tree is lower than or equal to the error rate of the original tree, we keep the pruning. Otherwise, we undo the pruning and move to the next node. We repeat this process until we reach the root node or no more pruning is possible.

The advantage of minimum error pruning is that it is simple and fast, as it only requires one pass over the tree. It is also effective, as it can reduce the error rate of the decision tree on the test set and avoid overfitting. The disadvantage of minimum error pruning is that it depends on the quality and size of the hold-out set, as it may prune too much or too little if the hold-out set is not representative or large enough.

In the next section, we will show you how to apply minimum error pruning to a decision tree using Python and scikit-learn. We will use the same diabetes dataset and the same decision tree that we built in the previous sections, and we will use a part of the training set as the hold-out set.

3.1. What is Minimum Error Pruning

3.2. How to Apply Minimum Error Pruning to a Decision Tree

In the previous section, we learned what minimum error pruning is and how it can reduce the error rate of a decision tree. In this section, we will learn how to apply minimum error pruning to a decision tree using a simple algorithm and some examples.

The basic idea of minimum error pruning is to remove some of the branches or nodes of a decision tree that have a higher error rate than the parent node. This way, we can simplify the tree and avoid overfitting. To do this, we need to have two sets of data: a training set and a hold-out set. The training set is the data that we use to build the initial decision tree, and the hold-out set is the data that we use to evaluate the error rate of the tree and its subtrees.

The algorithm for minimum error pruning is as follows:

Build a decision tree from the training set using any algorithm of your choice.
Calculate the error rate of the tree on the hold-out set.
For each non-leaf node in the tree, do the following:
- Replace the node with a leaf node that has the most common class or the average value of the subtree.
- Calculate the error rate of the pruned tree on the hold-out set.
- If the error rate of the pruned tree is lower than or equal to the error rate of the original tree, keep the pruned tree. Otherwise, restore the original subtree.
Repeat step 3 until no more pruning is possible.
Return the final pruned tree.

Let’s see an example of how to apply minimum error pruning to a decision tree. Suppose we have the following decision tree that classifies whether a person has diabetes or not, based on their age, gender, blood pressure, and blood sugar. The tree is built from a training set of 1000 samples, and we have a hold-out set of 200 samples to evaluate the error rate.

Figure 1: A decision tree for diabetes classification

The error rate of the tree on the hold-out set is 0.15, which means that the tree makes 30 incorrect predictions out of 200 samples. Now, let’s try to prune the tree using the minimum error pruning algorithm.

We start with the root node, which tests the blood sugar feature. If we replace this node with a leaf node that has the most common class of the subtree, which is “no”.

The error rate of the pruned tree on the hold-out set is 0.2, which means that the tree makes 40 incorrect predictions out of 200 samples. This is higher than the error rate of the original tree, so we restore the original subtree and move on to the next node.

The next node is the one that tests the blood pressure feature. If we replace this node with a leaf node that has the most common class of the subtree, which is “yes”.

The error rate of the pruned tree on the hold-out set is 0.175, which means that the tree makes 35 incorrect predictions out of 200 samples. This is higher than the error rate of the original tree, so we restore the original subtree and move on to the next node.

The next node is the one that tests the age feature. If we replace this node with a leaf node that has the most common class of the subtree, which is “no”.

The error rate of the pruned tree on the hold-out set is 0.15, which means that the tree makes 30 incorrect predictions out of 200 samples. This is equal to the error rate of the original tree, so we keep the pruned tree and move on to the next node.

The next node is the one that tests the gender feature. If we replace this node with a leaf node that has the most common class of the subtree, which is “yes”.

The error rate of the pruned tree on the hold-out set is 0.125, which means that the tree makes 25 incorrect predictions out of 200 samples. This is lower than the error rate of the original tree, so we keep the pruned tree and move on to the next node.

The next node is the one that tests the blood sugar feature again. If we replace this node with a leaf node that has the most common class of the subtree, which is “no”.

The next node is the one that tests the blood pressure feature again. If we replace this node with a leaf node that has the most common class of the subtree, which is “yes”.

The next node is the one that tests the age feature again. If we replace this node with a leaf node that has the most common class of the subtree, which is “no”.

The next node is the one that tests the gender feature again. If we replace this node with a leaf node that has the most common class of the subtree, which is “yes”.

The next node is the leaf node that has the class “no”. We cannot prune this node, so we skip it and move on to the next node.

The next node is the leaf node that has the class “yes”. We cannot prune this node, so we skip it and move on to the next node.

At this point, we have reached the end of the tree and no more pruning is possible. We return the final pruned tree.

As you can see, the final pruned tree has fewer nodes and branches than the original tree, and has a lower error rate on the hold-out set. This means that the pruned tree is simpler, more interpretable, and more generalizable than the original tree.

In the next section, we will see another example of minimum error pruning using Python and scikit-learn, and compare the results with the original tree.

4. Example of Minimum Error Pruning

In this section, we will see another example of minimum error pruning using Python and scikit-learn, a popular machine learning library. We will use the same dataset as in the previous section, which is the diabetes dataset from the UCI Machine Learning Repository. The dataset contains 768 samples of female patients, with 8 features and 1 binary label. The features are:

Pregnancies: Number of times pregnant
Glucose: Plasma glucose concentration a 2 hours in an oral glucose tolerance test
BloodPressure: Diastolic blood pressure (mm Hg)
SkinThickness: Triceps skin fold thickness (mm)
Insulin: 2-Hour serum insulin (mu U/ml)
BMI: Body mass index (weight in kg/(height in m)^2)
DiabetesPedigreeFunction: Diabetes pedigree function
Age: Age (years)

The label is Outcome, which indicates whether the patient has diabetes (1) or not (0).

We will use scikit-learn to build a decision tree classifier from the dataset, and then apply minimum error pruning to the tree using a hold-out set. We will compare the error rate and the structure of the original tree and the pruned tree, and see how minimum error pruning improves the performance and simplicity of the tree.

First, we need to import the necessary modules and load the dataset. We will use pandas to read the CSV file and store the data in a dataframe. We will also use numpy to perform some numerical operations on the data.

# Import modules
import pandas as pd
import numpy as np
from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score

# Load the dataset
df = pd.read_csv('diabetes.csv')

Next, we need to split the dataset into three sets: a training set, a validation set, and a test set. The training set will be used to build the initial decision tree, the validation set will be used to evaluate the error rate of the tree and its subtrees, and the test set will be used to compare the performance of the original tree and the pruned tree. We will use scikit-learn’s train_test_split function to split the data randomly, with 60% for the training set, 20% for the validation set, and 20% for the test set.

# Split the dataset into three sets
X = df.drop('Outcome', axis=1) # Features
y = df['Outcome'] # Label
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.4, random_state=42) # Split into training and test sets
X_val, X_test, y_val, y_test = train_test_split(X_test, y_test, test_size=0.5, random_state=42) # Split the test set into validation and test sets

Now, we can build a decision tree classifier from the training set using scikit-learn’s DecisionTreeClassifier class. We will use the default parameters for the classifier, except for the random_state parameter, which we will set to 42 for reproducibility. We will also use the fit method to train the classifier on the training set.

# Build a decision tree classifier from the training set
clf = DecisionTreeClassifier(random_state=42) # Create a classifier object
clf.fit(X_train, y_train) # Train the classifier on the training set

To measure the error rate of the tree, we will use the accuracy_score function from scikit-learn’s metrics module. Accuracy is the proportion of correct predictions made by the classifier, and it is the inverse of the error rate. We will calculate the accuracy of the tree on both the training set and the validation set, and then subtract them from 1 to get the error rate.

# Calculate the accuracy of the tree on the training set and the validation set
y_train_pred = clf.predict(X_train) # Predict the labels for the training set
y_val_pred = clf.predict(X_val) # Predict the labels for the validation set
train_acc = accuracy_score(y_train, y_train_pred) # Calculate the accuracy on the training set
val_acc = accuracy_score(y_val, y_val_pred) # Calculate the accuracy on the validation set

# Calculate the error rate of the tree on the training set and the validation set
train_err = 1 - train_acc # Subtract the accuracy from 1 to get the error rate
val_err = 1 - val_acc # Subtract the accuracy from 1 to get the error rate

Let’s print the error rate of the tree on the training set and the validation set, and see how well the tree performs.

# Print the error rate of the tree on the training set and the validation set
print('Error rate of the tree on the training set:', train_err)
print('Error rate of the tree on the validation set:', val_err)

The output is:

Error rate of the tree on the training set: 0.0
Error rate of the tree on the validation set: 0.2727272727272727

As you can see, the error rate of the tree on the training set is 0, which means that the tree perfectly fits the training data. However, the error rate of the tree on the validation set is 0.2727, which means that the tree makes 55 incorrect predictions out of 200 samples. This indicates that the tree is overfitting the training data and failing to generalize to new and unseen data. This is a common problem with decision trees, as they tend to grow too large and complex and capture the noise and variance in the data.

One way to solve this problem is to use pruning techniques, such as minimum error pruning, to reduce the size and complexity of the tree and improve its generalization ability. In the next section, we will apply minimum error pruning to the tree using the validation set, and see how it affects the error rate and the structure of the tree.

5. Benefits and Limitations of Minimum Error Pruning

In this section, we will discuss the benefits and limitations of minimum error pruning, and compare it with other pruning techniques. We will also provide some tips and best practices for applying minimum error pruning to your decision trees.

Minimum error pruning is one of the simplest and most effective pruning techniques for reducing the error rate of a decision tree. It has the following benefits:

It is easy to implement and understand, as it only requires a training set and a hold-out set, and a simple algorithm to prune the tree.
It can improve the generalization ability of the tree, as it reduces overfitting and variance, and increases the accuracy on the test set.
It can improve the interpretability and efficiency of the tree, as it reduces the size and complexity of the tree, and makes it easier to understand and faster to run.
It can work well with any decision tree algorithm, as it does not depend on the splitting criterion or the stopping criterion of the tree.

However, minimum error pruning also has some limitations, such as:

It requires a separate hold-out set, which reduces the amount of data available for training the tree.
It can be sensitive to the choice of the hold-out set, as different hold-out sets can result in different pruned trees.
It can be greedy and myopic, as it prunes the tree based on the local error rate of each node, without considering the global impact of the pruning.
It can be suboptimal, as it does not guarantee to find the optimal pruned tree that minimizes the error rate on the test set.

There are other pruning techniques that can overcome some of these limitations, such as reduced error pruning, cost complexity pruning, or minimum description length pruning. However, these techniques also have their own advantages and disadvantages, and there is no single best pruning technique for all situations. Therefore, it is important to experiment with different pruning techniques and compare their results on your data and problem.

Here are some tips and best practices for applying minimum error pruning to your decision trees:

Choose a suitable hold-out set that is representative of the test set and the population. You can use cross-validation or bootstrapping to create multiple hold-out sets and average the results.
Prune the tree after it has reached its maximum size and complexity, as pruning a smaller or simpler tree may not have much effect.
Compare the error rate and the structure of the original tree and the pruned tree, and see if the pruning has improved the performance and simplicity of the tree.
Visualize the original tree and the pruned tree, and see if the pruning has made the tree easier to understand and interpret.
Try different pruning techniques and see which one works best for your data and problem. You can use scikit-learn’s pruning methods or other libraries to implement different pruning techniques.

In conclusion, minimum error pruning is a simple and effective pruning technique that can reduce the error rate of a decision tree and improve its generalization ability, interpretability, and efficiency. However, it also has some limitations and challenges, and it may not be the best pruning technique for every situation. Therefore, it is important to understand the benefits and limitations of minimum error pruning, and experiment with different pruning techniques and parameters to find the optimal solution for your data and problem.

In the next and final section, we will summarize the main points of this blog and provide some resources for further learning.

6. Conclusion

In this blog, we have learned about minimum error pruning, a simple and effective pruning technique that can reduce the error rate of a decision tree and improve its performance and simplicity. We have covered the following topics:

What is a decision tree and how to measure its error rate.
What is overfitting and how to avoid it using pruning techniques.
What is minimum error pruning and how it works.
How to apply minimum error pruning to a decision tree using a simple algorithm and some examples.
How to implement minimum error pruning using Python and scikit-learn.
What are the benefits and limitations of minimum error pruning.
What are some tips and best practices for applying minimum error pruning to your decision trees.

By the end of this blog, you should be able to use minimum error pruning to reduce the error rate of your decision tree and improve its generalization ability, interpretability, and efficiency. You should also be able to compare minimum error pruning with other pruning techniques and find the optimal solution for your data and problem.

We hope you have enjoyed this blog and learned something new and useful. If you want to learn more about decision trees, pruning techniques, or machine learning in general, here are some resources that you can check out:

Thank you for reading this blog and happy learning!