Thuật toán phân lớp Naive Bayes
Bộ phân loại Naive Bayes là một thuật toán thuộc lớp thuật toán thống kê, nó có khả năng 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 nào đó. Phân loại Naive Bayes dựa trên Định lý Bayes (được đặt theo tên tác giả của nó là Thomas Bayes).
1. Định lý Bayes
- Giả sử A, B là hai biến cố
- Công thức Bayes tổng quát
Trong đó, A là chứng cứ (evidence) (trong bài toán phân loại, A là một phần tử dữ liệu), B là giả thiết để A thuộc vào một lớp C nào đó. Trong bài toán phân loại, chúng ta muốn xác định giá trị của 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 đã biết các thông tin mô tả A. P(B|A) là xác suất hậu nghiệm (posterior probability) của B với điều kiện A. Giả sử có một tập dữ liệu của khách hàng được mô tả bởi các thuộc tính 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 rằng khách hàng sẽ mua một chiếc máy tính, thì P(H|X) phản ánh xác suất mà người dùng X sẽ mua máy tính với điều kiện đã 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) của H. Trong ví dụ trên, P(H) 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ọ. 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à 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à $2000) 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ó là xác suấ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 loại Naive Bayes
Bộ phân loại Naive Bayes 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 A1, A2, …, An = {x1, x2, …, xn}
- Giả sử có m lớp C1, C2,..,Cm. Cho một phần tử dữ liệu X, bộ phân loại 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 loại Naive Bayes sẽ dự đoán X thuộc vào lớp Ci nếu và chỉ nếu: P(Ci|X) > P(Cj|X) (1<= i, j <= m, i != j) Giá trị này được 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 cho mọi lớp, do đó ta không cần tính. Ta chỉ cần tìm giá trị lớn nhất của P(X|Ci) * P(Ci). Lưu ý rằng P(Ci) được ước lượng bằng |Di|/|D|, trong đó Di là tập các phần tử dữ liệu thuộc lớp Ci. Nếu xác suất tiền nghiệm P(Ci) cũng không xác định được, ta coi chúng bằng nhau P(C1) = P(C2) = … = P(Cm), khi đó ta chỉ cần tìm giá trị P(X|Ci) lớn nhất.
- Khi số lượng các thuộc tính mô tả dữ liệu lớn, việc tính toán P(X|Ci) rất tốn kém, do đó có thể giảm độ phức tạp của thuật toán Naive Bayes bằng cách giả định các thuộc tính là độc lập. Khi đó ta có thể tính: P(X|Ci) = P(x1|Ci)*P(x2|Ci)*…*P(xn|Ci)
Ví dụ 1:
Phân loại 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(+/cancer)*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 kết luận rằng bệnh nhân không ung thư.
Ví dụ 2:
Bảng dữ liệu khách hàng:
| ID | Tuổi | Thu nhập | Sinh viên | Đánh giá tín dụng | Mua máy tính |
|---|---|---|---|---|---|
| 1 | trẻ | cao | không | công bằng | không |
| 2 | trẻ | cao | không | ưu tú | không |
| 3 | trung niên | cao | không | công bằng | có |
| 4 | cao niên | trung bình | không | công bằng | có |
| 5 | cao niên | thấp | có | công bằng | có |
| 6 | cao niên | thấp | có | ưu tú | không |
| 7 | trung niên | thấp | có | ưu tú | có |
| 8 | trẻ | trung bình | không | công bằng | có |
| 9 | trẻ | thấp | có | công bằng | có |
| 10 | cao niên | trung bình | có | công bằng | có |
| 11 | trẻ | trung bình | có | ưu tú | có |
| 12 | trung niên | trung bình | không | ưu tú | có |
| 13 | trung niên | cao | có | công bằng | có |
| 14 | cao niên | trung bình | không | ưu tú | không |
Giả sử ta có một khách hàng mới X với các thuộc tính X = (tuổi = trẻ, thu nhập = trung bình, sinh viên = có, đánh giá tín dụng = công bằng). Bây giờ cần xác định xem khách hàng X có thuộc lớp “mua máy tính” hay không, ta tính toán như sau:
P(Có mua máy tính) = 9/14 = 0.643
Các xác suất thành phần:
- P(tuổi = trẻ|Có mua máy tính) = 2/9 = 0.222
- P(tuổi = trẻ|Không mua máy tính) = 3/5 = 0.6
- P(thu nhập = trung bình|Có mua máy tính) = 4/9 = 0.444
- P(thu nhập = trung bình|Không mua máy tính) = 2/5 = 0.4
- P(sinh viên = có|Có mua máy tính) = 6/9 = 0.667
- P(sinh viên = có|Không mua máy tính) = 1/5 = 0.2
- P(đánh giá tín dụng = công bằng|Có mua máy tính) = 6/9 = 0.667
- P(đánh giá tín dụng = công bằng|Không mua máy tính) = 2/5 = 0.4
Cuối cùng:
P(X|Có mua máy tính) = 0.222 * 0.444 * 0.667 * 0.667 = 0.044
P(X|Không mua máy tính) = 0.6 * 0.4 * 0.2 * 0.4 = 0.019
P(X|Có mua máy tính)*P(Có mua máy tính) = 0.044 * 0.643
P(X|Không mua máy tính)*P(Không mua máy tính) = 0.019 * 0.357 = 0.007
Từ kết quả này, ta thấy P(X|Có mua máy tính)*P(Có mua máy tính) có giá trị lớn nhất, do đó thuật toán Bayes kết luận rằng 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 Ck và thuộc tính Fi nhận một giá trị cụ thể vij, xác suất điều kiện P(Fi = vij | Ck) sẽ bằng 0.
- Khi phân loại, 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 và lĩnh vực dữ liệu. Đơn giản nhưng đủ để giải quyết nhiều bài toán như phân loại văn bản, lọc spam,…
- Cho phép kết hợp tri thức tiền nghiệm và dữ liệu quan sát được. Tốt khi có sự chênh lệch số lượng giữa các lớp phân loại.
- Dễ và nhanh trong việc huấn luyện mô hình (ước lượng tham số).
5. Nhược điểm
- Giả định độc lập (ưu điểm cũng là nhược điểm) không áp dụng cho hầu hết các trường hợp thực tế, trong đó các thuộc tính trong các đối tượng thường phụ thuộc lẫn nhau.
- Vấn đề xác suất zero (đã được đề cập 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ố củ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 loại văn bản (document classification)
Tham khảo sách “Introduction to Information Retrieval” của Christopher Manning, Prabhakar Raghavan, và Hinrich Schutze, Xuất bản Đại học Cambridge, 2008. (Miễn phí) Chương 13. Phân loại văn bản và Naive Bayes. Tham khảo thêm: http://en.wikipedia.org/wiki/Document_classification http://en.wikipedia.org/wiki/Naive_Bayes_classifier
6.2. Lọc spam (Spam filtering)
Tham khảo: Bayesian spam filtering http://en.wikipedia.org/wiki/Bayesian_spam_filtering http://en.wikipedia.org/wiki/Naive_Bayes_classifier http://en.wikipedia.org/wiki/Email_filtering
Bài viết tham khảo từ cuốn “Giáo trình khai phá dữ liệu” của thầy Hà Quang Thụy – Nguyễn Hà Nam – Nguyễn Trí Thành