Top 5 Machine Learning Interview Problems

Implementing a Naive Bayes Classifier from Scratch

Introduction

The Naive Bayes classifier is one of the simplest and most efficient probabilistic classifiers, based on Bayes' Theorem. It is particularly well-suited for classification tasks involving text data, such as spam email detection or sentiment analysis, but it can also be applied to other types of data. The "naive" part of the name refers to the assumption that all features are independent of one another, which is often an unrealistic assumption, but one that simplifies computation and can still perform surprisingly well in many cases.

In this tutorial, we will implement a Naive Bayes Classifier from scratch using Python. We will explore both the Gaussian Naive Bayes (for continuous data) and Multinomial Naive Bayes (commonly used for text classification). We will also implement Laplace Smoothing to handle cases where certain feature combinations are missing from the training data.

By the end of this tutorial, you will have a solid understanding of the Naive Bayes algorithm and how to implement it from scratch using Python.

1. Understanding Naive Bayes Classifier

Bayes' Theorem

The Naive Bayes classifier is based on Bayes' Theorem, which states that the probability of a class CCC given a set of features X=( x₁ , x₂ ,….,  x_n ) is given by:

Where:

• P(C∣X) is the posterior probability of class C given the features X
• P(X∣C) is the likelihood, or the probability of observing X given the class C
• P(C) is the prior probability of the class C
• P(X) is the probability of observing the features X, which is constant for all classes.

The Naive Bayes classifier assumes that the features are independent given the class, which simplifies the likelihood calculation as follows:

Thus, we only need to calculate the likelihood of each individual feature, making the model computationally efficient even for large datasets.

2. Gaussian Naive Bayes

For continuous features, Gaussian Naive Bayes assumes that the features follow a Gaussian (normal) distribution. The probability of a feature xix_ixi​ given a class CCC is then modeled as:

Where:

• μC​ is the mean of the feature x_i in class C.
• 2σ²_c​ is the variance of the feature x_i​ in class C.

3. Multinomial Naive Bayes

For discrete data, such as text classification, Multinomial Naive Bayes is used. The probability of a feature xix_ixi​ given a class CCC is computed using the Multinomial distribution:

Where:

• count(xi​,C) is the number of times feature x_i appears in class C.
• count(C) is the total number of features in class C.
• α is a smoothing parameter, often set to 1 (Laplace smoothing).
• ∣V∣ is the size of the vocabulary.

4. Laplace Smoothing

One of the limitations of Naive Bayes is that it assigns a probability of 0 to features that never appear in the training data. Laplace Smoothing is used to handle this issue by adding a small constant (typically 1) to the count of each feature. This ensures that the probabilities never reach 0 and allows the model to handle unseen features.

5. Building the Naive Bayes Classifier

Now, let’s implement the Naive Bayes classifier from scratch. We will create two versions: Gaussian Naive Bayes for continuous data and Multinomial Naive Bayes for discrete data (such as word counts in text classification).

5.1 Gaussian Naive Bayes Implementation

We’ll implement the Gaussian Naive Bayes algorithm to classify continuous data. First, we need to calculate the mean and variance for each feature in each class.

Code Sample for Gaussian Naive Bayes:

import numpy as np

class GaussianNaiveBayes:

    def __init__(self):

        self.mean = {}

        self.variance = {}

        self.prior = {}

    def fit(self, X, y):

        classes = np.unique(y)

        for c in classes:

            X_c = X[y == c]

            self.mean[c] = np.mean(X_c, axis=0)

            self.variance[c] = np.var(X_c, axis=0)

            self.prior[c] = X_c.shape[0] / float(X.shape[0])

    def predict(self, X):

        predictions = [self._predict(x) for x in X]

        return np.array(predictions)

    def _predict(self, x):

        posteriors = []

        for c in self.prior:

            prior = np.log(self.prior[c])

            likelihood = np.sum(np.log(self._gaussian_likelihood(x, c)))

            posteriors.append(prior + likelihood)

        return np.argmax(posteriors)

    def _gaussian_likelihood(self, x, c):

        mean = self.mean[c]

        variance = self.variance[c]

        return (1 / np.sqrt(2 * np.pi * variance)) * np.exp(-((x - mean) ** 2) / (2 * variance))

Explanation:

• fit() computes the mean and variance for each class and stores the prior probabilities.
• _predict() computes the posterior probability for each class and returns the class with the highest probability.
• _gaussian_likelihood() computes the Gaussian likelihood for each feature given the class.

5.2 Multinomial Naive Bayes Implementation

Next, let’s implement the Multinomial Naive Bayes classifier. For simplicity, we’ll assume the dataset consists of word counts, such as in text classification tasks.

Code Sample for Multinomial Naive Bayes:

class MultinomialNaiveBayes:

    def __init__(self, alpha=1):

        self.alpha = alpha

        self.class_probs = {}

        self.feature_probs = {}

    def fit(self, X, y):

        classes = np.unique(y)

        for c in classes:

            X_c = X[y == c]

            class_count = X_c.shape[0]

            feature_count = np.sum(X_c, axis=0)

            total_feature_count = np.sum(feature_count)

            self.class_probs[c] = class_count / float(X.shape[0])

            self.feature_probs[c] = (feature_count + self.alpha) / (total_feature_count + self.alpha * X.shape[1])

    def predict(self, X):

        predictions = [self._predict(x) for x in X]

        return np.array(predictions)

    def _predict(self, x):

        posteriors = []

        for c in self.class_probs:

            prior = np.log(self.class_probs[c])

            likelihood = np.sum(np.log(self.feature_probs[c] ** x))

            posteriors.append(prior + likelihood)

        return np.argmax(posteriors)

Explanation:

• fit() computes the feature probabilities (with Laplace smoothing) and class priors.
• _predict() computes the posterior probability for each class using the log of the prior and the feature probabilities.
• This implementation assumes the input data X contains word counts, where each row corresponds to a sample and each column corresponds to a feature (a word in the vocabulary).

6. Training the Naive Bayes Model

Let’s train both classifiers on a dataset. We will use the Iris dataset for the Gaussian Naive Bayes classifier and a synthetic text dataset for the Multinomial Naive Bayes classifier.

6.1 Training Gaussian Naive Bayes

Code Sample:

from sklearn.datasets import load_iris

from sklearn.model_selection import train_test_split

from sklearn.metrics import accuracy_score

# Load the Iris dataset

iris = load_iris()

X = iris.data

y = iris.target

# Split into training and testing data

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

# Train Gaussian Naive Bayes

gnb = GaussianNaiveBayes()

gnb.fit(X_train, y_train)

# Make predictions

y_pred = gnb.predict(X_test)

# Evaluate accuracy

print(f"Gaussian Naive Bayes Accuracy: {accuracy_score(y_test, y_pred) * 100:.2f}%")

6.2 Training Multinomial Naive Bayes

Code Sample for Multinomial Naive Bayes:

# Synthetic text dataset

X_text = np.array([[1, 2, 1], [2, 1, 1], [1, 1, 2], [2, 2, 1], [1, 2, 2]])  # Feature matrix (word counts)

y_text = np.array([0, 0, 1, 1, 1])  # Labels

# Split into training and testing data

X_train_text, X_test_text, y_train_text, y_test_text = train_test_split(X_text, y_text, test_size=0.3, random_state=42)

# Train Multinomial Naive Bayes

mnb = MultinomialNaiveBayes(alpha=1)

mnb.fit(X_train_text, y_train_text)

# Make predictions

y_pred_text = mnb.predict(X_test_text)

# Evaluate accuracy

print(f"Multinomial Naive Bayes Accuracy: {accuracy_score(y_test_text, y_pred_text) * 100:.2f}%")

7. Evaluating the Naive Bayes Model

After training the model, we evaluate its performance using accuracy for classification tasks, which is computed as:

Accuracy=Number of correct predictionsTotal number of predictions\text{Accuracy} = \frac{\text{Number of correct predictions}}{\text{Total number of predictions}}Accuracy=Total number of predictionsNumber of correct predictions​

8. Conclusion

In this tutorial, we implemented the Naive Bayes Classifier from scratch for both continuous and discrete data. We:

1. Built a Gaussian Naive Bayes model for continuous features using Gaussian distributions.
2. Built a Multinomial Naive Bayes model for discrete features (such as word counts) using Multinomial distributions.
3. Implemented Laplace smoothing to handle missing feature combinations.
4. Trained and evaluated the models on real datasets like Iris and synthetic text data.

This tutorial demonstrated the power of Naive Bayes for both simple and more complex classification problems. Despite its simplicity, Naive Bayes is a highly effective algorithm, especially when the assumptions hold true (i.e., feature independence).