Naïve Bayesian Classification Algorithm

Idea

Naïve Bayes is a statistical/probabilistic classifier based on Bayes' theorem:

$$P(C_i \mid X) = \frac{P(X \mid C_i)\, P(C_i)}{P(X)}$$

where $X = (x_1, x_2, \dots, x_n)$ is a tuple described by $n$ attributes and $C_i$ is a class. Since $P(X)$ is the same for every class, the tuple is assigned to the class with the maximum posterior — the maximum a posteriori (MAP) rule:

$$\text{choose } C_i \text{ that maximises } P(X \mid C_i)\, P(C_i)$$

The "naïve" assumption

To make the computation tractable, naïve Bayes assumes conditional independence of the attributes given the class:

$$P(X \mid C_i) = \prod_{k=1}^{n} P(x_k \mid C_i)$$

Each $P(x_k \mid C_i)$ is estimated separately from the training data, so the classifier is simple and very fast.

Algorithm Steps

Input: training set D (labelled), a new tuple X = (x1, ..., xn)
1. For each class Ci:
     a. Prior:  P(Ci) = (number of training tuples of class Ci) / |D|
     b. For each attribute value xk:
          P(xk | Ci) = (count of tuples of class Ci with xk) / (count of Ci tuples)
          (for continuous attributes use the Gaussian density:
           P(xk|Ci) = 1/(sqrt(2π)·σi) · exp(-(xk-μi)²/(2σi²)) )
2. Score(Ci, X) = P(Ci) · Πk P(xk | Ci)
3. Return the class Ci with the highest score.

Laplacian (add-one) correction: if some $P(x_k \mid C_i) = 0$, the whole product becomes 0. To avoid this, use smoothing:

$$P(x_k \mid C_i) = \frac{\text{count}(x_k, C_i) + 1}{\text{count}(C_i) + m}$$

where $m$ is the number of distinct values of attribute $k$.

Worked Example

Outlook	Temp	Class (Play)
Sunny	Hot	No
Sunny	Mild	Yes
Rainy	Cool	Yes
Rainy	Mild	No
Overcast	Cool	Yes

Predict $X = (\text{Outlook=Sunny},\ \text{Temp=Cool})$.

Priors: $P(Yes)=3/5=0.6$, $P(No)=2/5=0.4$.

Likelihoods:

• $P(Sunny \mid Yes) = 1/3$, $P(Cool \mid Yes) = 2/3$
• $P(Sunny \mid No) = 1/2$, $P(Cool \mid No) = 0$

Scores:

• $\text{Score}(Yes) = 0.6 \times (1/3)(2/3) = 0.133$
• $\text{Score}(No) = 0.4 \times (1/2)(0) = 0$

Since $0.133 > 0$, $X$ is classified as Yes (with Laplacian smoothing, the No score would be tiny but non-zero).

Properties

• Advantages: extremely fast, works well on high-dimensional data (e.g., text/spam filtering), robust to irrelevant attributes, needs only one pass over the training data to estimate probabilities.
• Limitations: the independence assumption is usually violated in real data, which can reduce accuracy; however in practice it often performs surprisingly well.

Naïve Bayes is a core classification method in data mining (Han & Kamber, Chapter 9).