Định nghĩa

Naive Bayes Classification (NBC) là một thuật toán phân loại dựa trên tính toán xác suất áp dụng định lý Bayes mà ta đã tìm hiểu ở bài trước (xem bài trước tại đây).
Thuật toán này thuộc nhóm Supervised Learning (Học có giám sát).

Theo định lý Bayes, ta có công thức tính xác suất ngẫu nhiên của sự kiện $y$ khi biết $x$ như sau:

$$ P(y|x) = \dfrac{P(x|y)P(y)}{P(x)} ~~~~~ (1) $$

Giả sử ta phân chia 1 sự kiện $x$ thành $n$ thành phần khác nhau $x_1, x_2, \dots, x_n$.
Naive Bayes theo đúng như tên gọi dựa vào một giả thiết ngây thơ rằng $x_1, x_2, \dots x_n$ là các thành phần độc lập với nhau. Từ đó ta có thể tính được:

$$ P(x|y) = P(x_1 \cap x_2 \cap \dots \cap x_n |y) = P(x_1|y) P(x_2|y) \dots P(x_n|y) ~~~~~ (2) $$

Do đó ta có:

$$ P(y|x) \propto P(y) \prod\limits_{i=1}^n P(x_i|y) ~~~~~ (3) $$

$\propto$ là phép tỉ lệ thuận.

Trên thực tế thì ít khi tìm được dữ liệu mà các thành phần là hoàn toàn độc lập với nhau. Tuy nhiên giả thiết này giúp cách tính toán trở nên đơn giản, training data nhanh, đem lại hiệu quả bất ngờ với các lớp bài toán nhất định.

Cách xác định các thành phần (class) của dữ liệu dựa trên giả thiết này có tên là Naive Bayes Classifier.

Các mô hình thuật toán Naive Bayes

Một trong các bài toán nổi tiếng hiệu quả khi sử dụng NBC là bài toán phân loại text, trong đó phổ biến nhất là bài toán phân loại thư rác.

Trong bài toán này, mỗi văn bản được thể hiện thành dạng bag of words, hiểu nôm na là thể hiện xem có bao nhiêu từ xuất hiện và tần suất xuất hiện trong văn bản, nhưng bỏ qua thứ tự các từ.

Các từ và tần suất xuất hiện được coi là các feature vector, và theo giả thiết Naive Bayes coi là các thành phần độc lập mà không ảnh hưởng đến nhau.

Có 2 mô hình thuật toán Naive Bayes thường sử dụng là: mô hình Bernoulli và mô hình Multinomial.

1. Mô hình Bernoulli

a. Công thức

Ở mô hình này, các feature vector là các giá trị nhị phân 0, 1. Trong đó 1 thể hiện từ có xuất hiện trong văn bản, 0 thể hiện từ đó không xuất hiện trong văn bản.

Xác suất $P(x_i | y)$ được tính bằng

$$ P(x_i | y) = P(i | y) \times {x_i} + (1 - P(i | y)) \times (1 - x_i) ~~~~~ (4) $$

với $P(i|y)$ là tỉ lệ số lần từ $x_i$ xuất hiện trong toàn bộ tập training data có nhãn $y$.

Nhiều tài liệu biểu diễn công thức dưới dạng khác là:

$$ P(x_i | y) = P(i | y)^{x_i} \times (1 - P(i | y))^{1 - x_i} ~~~~~ (5) $$

Công thức (4) và (5) về giá trị toán học là giống nhau.

b. Ví dụ

Đề bài

Ta có training data gồm 10 email, đánh 2 nhãn: Spam (S) và Not Spam (N).
Ta định nghĩa bảng từ vựng gồm 8 từ như sau:

$$ V = \left [ w_1, w_2, w_3, w_4, w_5 \right ] $$

Cần phân loại email E11 thuộc loại nào

Lời giải

Để dễ phân biệt, ra xếp tập training data riêng thành 2 bảng như sau:

class = Spam (S)

class = Not Spam (N)

Ta có:
$P(S) = \dfrac{6}{10}$, $P(N) = \dfrac{4}{10}$

Số lần xuất hiện của từng từ tương ứng với 2 nhãn S và N như sau:

$$ \begin{aligned} n_s(w_1) = 4 \quad n_s(w_2) = 4 \cr n_s(w_3) = 3 \quad n_s(w_4) = 3 \cr n_s(w_5) = 2 \cr \cr n_n(w_1) = 1 \quad n_n(w_2) = 2 \cr n_n(w_3) = 2 \quad n_n(w_4) = 3 \cr \cr n_n(w_5) = 2 \cr \end{aligned} $$

Ta tính được xác xuất của từng từ xuất hiện như sau:

$$ \begin{aligned} P(w_1|S) = \dfrac{2}{3} \quad P(w_2|S) = \dfrac{2}{3} \cr P(w_3|S) = \dfrac{1}{2} \quad P(w_4|S) = \dfrac{1}{2} \cr P(w_5|S) = \dfrac{1}{3} \cr \cr P(w_1|N) = \dfrac{1}{4} \quad P(w_2|N) = \dfrac{1}{2} \cr P(w_3|N) = \dfrac{1}{2} \quad P(w_4|N) = \dfrac{3}{4} \cr P(w_5|N) = \dfrac{1}{2} \end{aligned} $$

Với test data $E11 = \{ w_1=1, w_4=1, w_5=1 \}$, ta tính xác suất tương ứng của E11 với mỗi loại như sau:

$$ \begin{aligned} P(S|E11) &\propto& P(S) \prod\limits_{i=1}^5 P(w_i | S) \times {w_i} + (1 - P(w_i | S)) \times (1 - w_i) \cr &\propto& \dfrac{6}{10} \times ( \dfrac{2}{3} \times \dfrac{1}{3} \times \dfrac{1}{2} \times \dfrac{1}{2} \times \dfrac{1}{3} ) \cr &\propto& 0.0111 \end{aligned} $$

$$ \begin{aligned} P(N|E11) &\propto& P(N) \prod\limits_{i=1}^5 P(w_i | N) \times {w_i} + (1 - P(w_i | N)) \times (1 - w_i) \cr &\propto& \dfrac{4}{10} \times ( \dfrac{1}{4} \times \dfrac{1}{2} \times \dfrac{1}{2} \times \dfrac{3}{4} \times \dfrac{1}{2} ) \cr &\propto& 0.0094 \end{aligned} $$

Ta tính được xác suất tương ứng như sau:

$$ \begin{aligned} P(S|E11) &=& \dfrac{0.0111}{0.0111 + 0.0094} \approx 0.54 \cr P(N|E11) &=& \dfrac{0.0094}{0.0111 + 0.0094} \approx 0.46 \end{aligned} $$

Do đó ta phân loại E11 là Spam (S).

Test bằng sklearn

Ta test lại kết quả vừa tính được bằng thư viện sklearn bằng đoạn code bên dưới:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

from sklearn.naive_bayes import BernoulliNB
import numpy as np

# train data

e1 = [1, 1, 0, 1, 0]
e2 = [0, 1, 1, 0, 0]
e3 = [1, 0, 1, 0, 1]
e4 = [1, 1, 1, 1, 0]
e5 = [0, 1, 0, 1, 0]
e6 = [0, 0, 0, 1, 1]
e7 = [0, 1, 0, 0, 0]
e8 = [1, 1, 0, 1, 0]
e9 = [0, 0, 1, 1, 1]
e10 = [1, 0, 1, 0, 1]

train_data = np.array([e1, e2, e3, e4, e5, e6, e7, e8, e9, e10])
label = np.array(['N', 'N', 'S', 'S', 'S', 'N', 'S', 'S', 'N', 'S'])

# test data

e11 = np.array([[1, 0, 0, 1, 1]])

clf1 = BernoulliNB(alpha=1e-10)

# training

clf1.fit(train_data, label)

# test

print('Probability of e11 in each class:', clf1.predict_proba(e11))
print('Predicting class of e11:', str(clf1.predict(e11)[0]))

Chạy đoạn code trên thu được kết quả in ra màn hình trùng khớp với tính toán trước đó:

Probability of e11 in each class: [[0.45762712 0.54237288]]
Predicting class of e11: S

2. Mô hình Multinomial

a. Công thức

Ở mô hình này, các feature vector là các giá trị số tự nhiên mà giá trị thể hiện số lần từ đó xuất hiện trong văn bản.
Ta tính xác suất từ xuất hiện trong văn bản $P(x_i | y)$ như sau:

$$ P(x_i | y) = \dfrac{N_i}{N_c} ~~~~~ (6) $$

Trong đó:
$N_i$ là tổng số lần từ $x_i$ xuất hiện trong văn bản.
$N_c$ là tổng số lần từ của tất cả các từ $x_1, \dots x_n$ xuất hiện trong văn bản.

b. Laplace Smoothing

Công thức trên có hạn chế là khi từ $x_i$ không xuất hiện lần nào trong văn bản, ta sẽ có $N_i = 0$. Điều này làm cho $P(x_i | y) = 0$.
Vế phải của công thức (3) bằng 0 nếu bất kì một giá trị nào bằng 0 (mặc dù có thể các giá trị khác rất lớn).

Để khắc phục vấn đề này, người ta sử dụng kỹ thuật gọi là Laplace Smoothing bằng cách cộng thêm vào cả tử và mẫu để giá trị luôn khác 0.

$$ P(x_i | y) = \dfrac{N_i + \alpha}{N_c + d\alpha} ~~~~~~ (7) $$

Trong đó:
$\alpha$ thường là số dương, bằng 1.
$d\alpha$ được cộng vào mẫu để đảm bảo $\sum_{i=1}^d P(x_i | y) = 1$

c. Ví dụ

Đề bài

Vẫn bài toán phân loại mail Spam (S) và Not Spam (N).
Ta có bộ training data gồm E1, E2, E3. Cần phân loại E4.
Bảng từ vựng: $\left [ w_1, w_2, w_3, w_4, w_5, w_6, w_7 \right ]$.

Số lần xuất hiện của từng từ trong từng email tương ứng như bảng dưới.

Lời giải

Ta có:
$P(S) = \dfrac{1}{3}$, $P(N) = \dfrac{2}{3}$

Sử dụng Laplace Smoothing với $\alpha = 1$ ta tính được xác suất xuất hiện của từng từ trong văn bản như sau:

class = Spam (S)

class = Not Spam (N)

Vậy ta tính được:

$$ \begin{aligned} P(S|E4) &\propto& P(S) \prod\limits_{i=1}^7 P(w_i | S) \cr &\propto& \dfrac{1}{3} \times ( \dfrac{2}{12} \times \dfrac{1}{12}) \cr &\propto& 0.0046 \end{aligned} $$

$$ \begin{aligned} P(N|E4) &\propto& P(N) \prod\limits_{i=1}^7 P(w_i | N) \cr &\propto& \dfrac{2}{3} \times ( \dfrac{2}{17} \times \dfrac{2}{17} ) \cr &\propto& 0.0092 \end{aligned} $$

Vậy xác suất tương ứng sẽ là:

$$ \begin{aligned} P(S|E4) &=& \dfrac{0.0046}{0.0046 + 0.0092} \approx 0.334 \cr P(N|E4) &=& \dfrac{0.0092}{0.0046 + 0.0092} \approx 0.666 \end{aligned} $$

Do đó ta phân loại E4 là Not Spam (N).

Test bằng Scikit-learn

Ta test lại kết quả vừa tính được bằng thư viện scikit-learn bằng đoạn code bên dưới.

Nếu chưa có thư viện này trong máy, ta có thể cài đặt đơn giản bằng pip (thay bằng pip3 nếu muốn cài cho Python 3).

pip install scikit-learn

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

from sklearn.naive_bayes import MultinomialNB
import numpy as np

# train data

e1 = [1, 2, 1, 0, 1, 0, 0]
e2 = [0, 2, 0, 0, 1, 1, 1]
e3 = [1, 0, 1, 1, 0, 2, 0]

train_data = np.array([e1, e2, e3])
label = np.array(['N', 'N', 'S'])

# test data

e4 = np.array([[1, 0, 0, 0, 0, 0, 1]])

clf1 = MultinomialNB(alpha=1)

# training

clf1.fit(train_data, label)

# test

print('Probability of e4 in each class:', clf1.predict_proba(e4))
print('Predicting class of e4:', str(clf1.predict(e4)[0]))

Chạy đoạn code trên thu được kết quả in ra màn hình trùng khớp với tính toán trước đó:

Probability of e4 in each class: [[0.66589595 0.33410405]]
Predicting class of e4: N

Kết luận

Naive Bayes Classifiers (NBC) là phương pháp cổ điển nhưng vẫn rất hữu dụng với các bài toán nhất định như phân loại văn bản, email…

NBC với công thức tính toán đơn giản nên dễ cài đặt (hiện nay nếu dùng thư viện sklearn thì chỉ cần gọi vài dòng lệnh như mình làm bên trên), thời gian training và test nhanh, phù hợp với bài toán data lớn.

Cần chú ý sử dụng Smoothing để tránh lỗi xác suất tổng được bằng 0 khi xác suất của một feature thành phần bằng 0.