Naive Bayes and Laplacian correction

The Naïve Bayes classifier is a statistical classifier based on Bayes' theorem. It predicts the probability that a tuple belongs to each class and assigns the class with the highest posterior probability.

Bayes' theorem

P(C | X) = P(X | C) · P(C) / P(X)

For a tuple X = (x₁, …, xₙ) and classes C₁ … C_m, X is assigned to the class Cᵢ that maximises P(X | Cᵢ)·P(Cᵢ) (P(X) is the same for all classes and is ignored).

• P(Cᵢ) = (number of training tuples of class Cᵢ)/(total tuples).
• For categorical attributes, P(xₖ | Cᵢ) = (tuples of class Cᵢ having value xₖ)/(tuples of class Cᵢ).
• For continuous attributes a Gaussian density with the class mean and standard deviation is used.

Example: buys-computer data (9 yes, 5 no), X = (young, income low, student yes, credit fair): P(X | yes)P(yes) = (2/9)(3/9)(6/9)(6/9)(9/14) = 0.0212; P(X | no)P(no) = (3/5)(1/5)(1/5)(2/5)(5/14) = 0.0034. So class = yes.

Why "naïve"?

It makes the simplifying assumption of class-conditional independence: given the class, the attributes are assumed independent of each other, so P(X | C) = Π P(xₖ | C). This is rarely true in real data (e.g. age and income are related), yet it makes computation easy and often still gives good accuracy.

Laplacian correction (Laplace smoothing)

If some attribute value never occurs with a class in the training data, P(xₖ | C) = 0 and the whole product becomes 0, whatever the other attributes say. To avoid this zero-probability problem, add 1 to each count (assume each value has at least one extra tuple):

P(xₖ | C) = (nₖ + 1) / (n_C + v)

where nₖ is the count of value xₖ in class C, n_C is the number of tuples of class C and v is the number of distinct values of the attribute.

Example: in a class of 1000 tuples, income has low = 0, medium = 990, high = 10. Corrected: low = 1/1003, medium = 991/1003, high = 11/1003. The corrected values are close to the old ones, but are never zero.