Top 5 Machine Learning Interview Problems

Building a Decision Tree Classifier from Scratch

Introduction

Decision Trees are one of the most widely used algorithms in machine learning for both classification and regression tasks. They model data in a tree-like structure where each node represents a decision based on a feature, and the branches represent the outcomes of those decisions. Decision trees are powerful due to their simplicity and interpretability, which makes them suitable for a wide variety of applications.

In this tutorial, we will implement a Decision Tree Classifier from scratch using Python and NumPy. We will build the algorithm step by step, starting from splitting the dataset based on the best feature, calculating the impurity measures (like Gini impurity or Entropy), and recursively growing the tree. By the end of this tutorial, you will have a working Decision Tree implementation and a deeper understanding of how decision trees work.

1. Decision Tree Classifier: Overview

A Decision Tree is a supervised learning algorithm that works by recursively splitting the dataset into subsets based on the feature that best separates the data. The goal is to partition the data into distinct classes such that the data within each partition is as homogeneous as possible.

Key Terminology:

• Root: The topmost node that splits the dataset into two or more subsets.
• Internal Node: A decision node that splits the data based on a feature.
• Leaf Node: A terminal node where the decision is made (i.e., class label is assigned).
• Split: The action of dividing the data based on a feature.

Key Concepts:

1. Entropy: Measures the uncertainty of a dataset. For classification, it is calculated as:

Where p_i​ is the probability of class i in subset SSS.

2. Gini Impurity: Measures the impurity of a dataset. It is calculated as:

Where p_i​ is the probability of class i in subset SSS.

The algorithm chooses the best feature to split on based on the feature that results in the lowest impurity (either highest information gain with entropy or lowest Gini impurity).

2. Data Preprocessing

Before implementing the decision tree, we need to prepare the dataset. For simplicity, we will use a synthetic dataset that includes several features. In real-world scenarios, you would likely use datasets like Iris, Titanic, or Wine.

Let’s first create a simple dataset for classification.

Code Sample:

import numpy as np

from sklearn.datasets import load_iris

from sklearn.model_selection import train_test_split

from sklearn.preprocessing import StandardScaler

# Load the Iris dataset

iris = load_iris()

X = iris.data

y = iris.target

# Split the dataset into training and testing sets

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

# Normalize the feature data

scaler = StandardScaler()

X_train = scaler.fit_transform(X_train)

X_test = scaler.transform(X_test)

Explanation:

• We load the Iris dataset using load_iris() from scikit-learn.
• The dataset is split into training and testing sets using train_test_split().
• StandardScaler is used to normalize the data, which is essential for distance-based algorithms but may not always be necessary for decision trees.

3. Calculating Impurity (Gini and Entropy)

The first step in building a decision tree is to decide how to split the data. We use a measure of impurity to evaluate potential splits. The two most common measures are Gini impurity and Entropy.

3.1 Gini Impurity

The Gini impurity is calculated as follows:

Code Sample for Gini Impurity:

def gini_impurity(y):

    class_probs = [np.sum(y == i) / len(y) for i in np.unique(y)]

    return 1 - sum([p**2 for p in class_probs])

# Example usage

y_train_example = y_train  # Assume y_train is a subset of the training labels

gini = gini_impurity(y_train_example)

print(f"Gini Impurity: {gini}")

Explanation:

• gini_impurity() computes the Gini score by calculating the probabilities of each class in the target variable y and then applying the formula.

3.2 Entropy

Entropy is another measure of impurity that tells us the uncertainty or randomness in the dataset. It is calculated as:

Code Sample for Entropy:

def entropy(y):

    class_probs = [np.sum(y == i) / len(y) for i in np.unique(y)]

    return -sum([p * np.log2(p) for p in class_probs if p > 0])

# Example usage

entropy_value = entropy(y_train_example)

print(f"Entropy: {entropy_value}")

Explanation:

• entropy() calculates the entropy of a dataset based on the proportions of each class.

4. Building the Decision Tree

Now that we understand how to calculate the impurity, we can start building the decision tree. The tree will recursively split the data based on the feature that provides the best (i.e., lowest impurity) partition. We will continue splitting until we reach a stopping criterion, such as a maximum depth or minimum number of samples.

4.1 Split the Data

To decide how to split the data, we will:

1. Iterate over all features.
2. For each feature, calculate the impurity of the split based on some threshold.
3. Choose the feature and threshold that results in the lowest impurity.

Code Sample for Splitting:

def best_split(X, y):

    best_gini = float('inf')

    best_split_value = None

    best_feature = None

    # Iterate over each feature

    for feature_index in range(X.shape[1]):

        feature_values = np.unique(X[:, feature_index])  # Unique values in the feature

        for value in feature_values:

            # Split the data based on this value

            left_mask = X[:, feature_index] <= value

            right_mask = ~left_mask

            left_y = y[left_mask]

            right_y = y[right_mask]

            # Calculate Gini impurity for the split

            gini_left = gini_impurity(left_y)

            gini_right = gini_impurity(right_y)

            gini_split = (len(left_y) * gini_left + len(right_y) * gini_right) / len(y)

            if gini_split < best_gini:

                best_gini = gini_split

                best_split_value = value

                best_feature = feature_index

    return best_feature, best_split_value

Explanation:

• We iterate over all features and find the best split that minimizes the Gini impurity.
• For each feature, we test different split values (thresholds) and compute the Gini impurity for the left and right subsets.
• The best feature and threshold are selected based on the lowest Gini impurity.

4.2 Recursive Tree Construction

Now that we have the function to find the best split, we will recursively build the decision tree. At each node, we select the feature that minimizes the impurity and create child nodes for the left and right subsets.

Code Sample for Tree Construction:

class DecisionTree:

    def __init__(self, max_depth=None):

        self.max_depth = max_depth

        self.tree = None

    def fit(self, X, y):

        self.tree = self._build_tree(X, y, depth=0)

    def _build_tree(self, X, y, depth):

        # Stopping criteria: if all labels are the same or max depth reached

        if len(np.unique(y)) == 1 or (self.max_depth and depth == self.max_depth):

            return np.bincount(y).argmax()

        feature, value = best_split(X, y)

        if feature is None:

            return np.bincount(y).argmax()  # Return majority class if no split found

        # Recursively split the data

        left_mask = X[:, feature] <= value

        right_mask = ~left_mask

        left_tree = self._build_tree(X[left_mask], y[left_mask], depth + 1)

        right_tree = self._build_tree(X[right_mask], y[right_mask], depth + 1)

        return (feature, value, left_tree, right_tree)

    def predict(self, X):

        return [self._predict(x, self.tree) for x in X]

    def _predict(self, x, tree):

        if isinstance(tree, int):  # If it's a leaf node, return the class

            return tree

        feature, value, left_tree, right_tree = tree

        if x[feature] <= value:

            return self._predict(x, left_tree)

        else:

            return self._predict(x, right_tree)

Explanation:

• The fit() method builds the decision tree by recursively splitting the data until the stopping criteria are met.
• The _build_tree() method recursively constructs the tree by selecting the best feature and value to split on, creating child nodes for the left and right subsets.
• The predict() method makes predictions for new data points by traversing the tree.

5. Evaluating the Model

Once the model is trained, we can evaluate its performance on the test set. The performance is typically measured using accuracy for classification tasks.

Code Sample for Accuracy:

def accuracy(y_true, y_pred):

    return np.sum(y_true == y_pred) / len(y_true)

# Evaluate the decision tree

y_pred = tree.predict(X_test)

acc = accuracy(y_test, y_pred)

print(f"Accuracy: {acc * 100:.2f}%")

Explanation:

• The accuracy() function calculates the proportion of correctly predicted labels.

6. Conclusion

In this tutorial, we implemented a Decision Tree Classifier from scratch using Python and NumPy. We covered the following steps:

1. Data preprocessing: Normalizing the features using StandardScaler.
2. Impurity measures: Implementing Gini impurity and Entropy to evaluate the splits.
3. Tree construction: Building the tree recursively using the best feature and value to split the data.
4. Model evaluation: Calculating accuracy to assess model performance.