Thuật toán phân lớp Naive Bayes

This post hasn't been updated for 5 years

Bộ phân lớp Bayes là một giải thuật thuộc lớp giải thuật thống kê, nó có thể dự đoán xác suất của một phần tử dữ liệu thuộc vào một lớp là bao nhiêu. Phân lớp Bayes được dựa trên định lý Bayes (định lý được đặt theo tên tác giả của nó là Thomas Bayes)

1. Định lý Bayes

Gọi A, B là hai biến cố

Công thức Bayes tổng quát

    Trong đó ta gọi A là một chứng cứ (evidence) (trong bài toán phân lớp A sẽ là một phần tử dữ liệu), B là một giả thiết nào để cho A thuộc về một lớp C nào đó. Trong bài toán phân lớp chúng ta muốn xác định giá trị P(B/A) là xác suất để giả thiết B là đúng với chứng cứ A thuộc vào lớp C với điều kiện ra đã biết các thông tin mô tả A. P(B|A) là một xác suất hậu nghiệm (posterior probability hay posteriori probability) của B với điều kiện A.
    Giả sử tập dữ liệu liệu khách hàng của chúng ta được mô tả bởi các thuộc tính tuổi và thu nhập, và một khách hàng X có tuổi là 25 và thu nhập là 2000$. Giả sử H là giả thiết khách hàng đõ sẽ mua máy tính, thì P(H|X) phản ánh xác xuất người dùng X sẽ mua máy tính với điều kiện ta biết tuổi và thu nhập của người đó.
    Ngược lại P(H) là xác suất tiền nghiệm (prior probability hay priori probability) của H. Trong ví dụ trên, nó là xác suất một khách hàng sẽ mua máy tính mà không cần biết các thông tin về tuổi hay thu nhập của họ. Hay nói cách khác, xác suất này không phụ thuộc vào yếu tố X. Tương tự, P(X|H) là xác suất của X với điều kiện H (likelihood), nó là một xác suất hậu nghiệm. VÍ dụ, nó là xác suất người dùng X (có tuổi là 25 và thu nhập là $200) sẽ mua máy tính với điều kiện ta đã biết người đó sẽ mua máy tính. Cuối cùng P(X) là xác suất tiền nghiệm của X. Trong ví dụ trên, nó se là xác xuất một người trong tập dữ liệu sẽ có tuổi 25 và thu nhập $2000.
Posterior = Likelihood * Prior / Evidence

2. Phân lớp Naive Bayes

Bộ phân lớp Naive bayes hay bộ phân lớp Bayes (simple byes classifier) hoạt động như sau:

Gọi D là tập dữ liệu huấn luyện, trong đó mỗi phần tử dữ liệu X được biểu diễn bằng một vector chứa n giá trị thuộc tính A₁, A₂,...,A_n = {x₁,x₂,...,x_n}
Giả sử có m lớp C₁, C₂,..,C_m. Cho một phần tử dữ liệu X, bộ phân lớp sẽ gán nhãn cho X là lớp có xác suất hậu nghiệm lớn nhất. Cụ thể, bộ phân lớp Bayes sẽ dự đoán X thuộc vào lớp C_i nếu và chỉ nếu:
P(C_i|X) > P(C_j|X) (1<= i, j <=m, i != j)
Giá trị này sẽ tính dựa trên định lý Bayes.
Để tìm xác suất lớn nhất, ta nhận thấy các giá trị P(X) là giống nhau với mọi lớp nên không cần tính. Do đó ta chỉ cần tìm giá trị lớn nhất của P(X|C_i) * P(C_i). Chú ý rằng P(C_i) được ước lượng bằng |D_i|/|D|, trong đó D_i là tập các phần tử dữ liệu thuộc lớp C_i. Nếu xác suất tiền nghiệm P(C_i) cũng không xác định được thì ta coi chúng bằng nhau P(C₁) = P(C₂) = ... = P(C_m), khi đó ta chỉ cần tìm giá trị P(X|C_i) lớn nhất.
Khi số lượng các thuộc tính mô tả dữ liệu là lớn thì chi phí tính toàn P(X|C_i) là rất lớn, dó đó có thể giảm độ phức tạp của thuật toán Naive Bayes giả thiết các thuộc tính độc lập nhau. Khi đó ta có thể tính:
P(X|C_i) = P(x₁|C_i)...P(x_n|C_i)

Ví dụ 1:

Phân các bệnh nhân thành 2 lớp ung thư và không ung thư. Giả sử xác suất để một người bị ung thư là 0.008 tức là P(cancer) = 0.008; và P(nocancer) = 0.992. Xác suất để bệnh nhân ung thư có kết quả xét nghiệm dương tính là 0.98 và xác suất để bệnh nhân không ung thư có kết quả dương tính là 0.03 tức là P(+/cancer) = 0.98, P(+/nocancer) = 0.03. Bây giờ giả sử một bệnh nhân có kết quả xét nghiệm dương tính. Ta có:
P(+/canncer)P(cancer) = 0.98 * 0.008 = 0.0078
P(+/nocancer)P(nocancer) = 0.03 * 0.992 = 0.0298
Như vậy, P(+/nocancer)P(nocancer) >> P(+/cancer)P(cancer).
Do đó ta xét đoán rằng, bệnh nhân là không ung thư.

Ví dụ 2:

Cơ sở dữ liệu khách hàng:

ID	Tuổi	Thu nhập	Sính viên	Đánh giá tín dụng	Mua máy tính
1	youth	high	no	fair	no
2	youth	high	no	excellent	no
3	middle	high	no	fair	yes
4	senior	medium	no	fair	yes
5	senior	low	yes	fair	yes
6	senior	low	yes	excellent	no
7	middle	low	yes	excellent	yes
8	youth	medum	no	fair	yes
9	youth	low	yes	fair	yes
10	senior	medium	yes	fair	yes
11	youth	medium	yes	excellent	yes
12	middle	medium	no	excellent	yes
13	middle	high	yes	fair	yes
14	senior	medium	no	excellent	no

Giả sử ta có một khách hàng mới X có các thuộc tính
X = (age = youth, income = medium, student = yes, credit_rating = fair)
Bây giớ cần xác định xem khách hàng X có thuộc lớp C_yes (mua máy tính) hay không, ta tính toán như sau:
P(C_yes) = 9/14 = 0.357
Các xác suất thành phần:
P(age = youth|C_yes) = 2/9 = 0.222
P(age = youth|C_no) = 3/5 = 0.6
P(income = medium|C_yes) = 4/9 = 0.444
P(income = medium|C_no) = 2/5 = 0.4
P(student = yes|C_yes) = 6/9 = 0.667
P(student = yes|C_no) = 1/5 = 0.2
P(credit_rating = fair|C_yes) = 6/9 = 0.667
P(credit_rating = fair|C_no) = 2/5 = 0.2
Cuối cùng:
P(X|C_yes) = 0.222 * 0.444 * 0.667 * 0.667 = 0.044
P(X|C_no) = 0.60.4 * 0.2 * 0.4 = 0.019
P(X|C_yes)*P(C_yes) = 0.044 * 0.643
P(X|C_no)*P(C_no) =0.019 * 0.357 = 0.007

Từ kết quả này ta thấy P(X |C_yes)P(C_yes) có giá trị lớn nhất, do đó thuật toán Bayes sẽ kết luận là khách hàng X sẽ mua máy tính.

3. Khắc phục vấn đề xác suất điều kiện bằng zero

Nếu trong dữ liệu huấn luyện không có đối tượng X nào có thuộc tính lớp C_k có thuộc tính F_i nhận một giá trị cụ thể vⁱ_j, xác suất điều kiện P(F_i = xⁱ_j | C_k) sẽ bằng 0.
Khi phân lớp, nếu có một đối tượng nào mang thuộc tính này thì xác suất phân vào lớp Ck luôn bằng 0.
Khắc phục bằng cách ước lượng theo công thức sau:

4. Ưu điểm

Giả định độc lập: hoạt động tốt cho nhiều bài toán/miền sữ liệu và ứng dụng.
Đơn giản nhưng đủ tốt để giải quyết nhiều bài toán như phân lớp văn bản, lọc spam,..
Cho phép kết hợp tri thức tiền nghiệm (prior knowledge) và dữ liệu quan sát được (obserwed data).
Tốt khi có sự chệnh lệch số lượng giữa các lớp phân loại.
Huấn luyện mô hình (ước lượng tham số) dễ và nhanh.

5. Nhược điểm

Giả định độc lập (ưu điểm cũng chính là nhược điểm)
hầu hết các trường hợp thực tế trong đó có các thuộc tính trong các đối tượng thường phụ thuộc lẫn nhau.
Vấn đề zero (đã nêu cách giải quyết ở phía trên)
Mô hình không được huẩn luyện bằng phượng pháp tối ưu mạnh và chặt chẽ.
Tham số mủa mô hình là các ước lượng xác suất điều kiện đơn lẻ.
Không tính đến sự tương tác giữa các ước lượng này.

6. Ứng dụng cụ thể

6.1. Phân lớp văn bản (document classification)

Tham khảo cuốn sách sau:
Christopher Manning, Prabhakar Raghavan, and Hinrich Schutze, Introduction to Information Retrieval, Cambridge University Press, 2008. (Free)
Chương 13. Text classification and Naïve Bayes
Tham khảo thêm:
http://en.wikipedia.org/wiki/Document_classification
http://en.wikipedia.org/wiki/Naive_Bayes_classifier