Show
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). 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$. $$ 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) $$
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 BayesMộ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 Bernoullia. 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àiTa có training data gồm 10 email, đánh 2 nhãn: Spam (S) và Not Spam (N). $$ 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ó: 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 sklearnTa 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: naive_bayes_bernoulli.py
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: S2. Mô hình Multinomiala. 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. $$ 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 SmoothingCô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$. Để 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àiVẫ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ảiTa có: 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-learnTa 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 naive_bayes_multinomial.py
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: NKết luậnNaive 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. © 2022 Nam Doan. Privacy Policy
|