Tổng Quan Về Thuật Toán Phân Lớp Naive Bayes Classification (NBC)

Naive Bayes Classification (NBC) là một thuật toán dựa trên định lý Bayes về lý thuyết xác suất để đưa ra các phán đoán cũng như phân loại dữ liệu dựa trên các dữ liệu được quan sát và thống kê. Naive Bayes Classification là một trong những thuật toán được ứng dụng rất nhiều trong các lĩnh vực Machine learning dùng để đưa các dự đoán chính xác nhất dự trên một tập dữ liệu đã được thu thập, vì nó khá dễ hiểu và độ chính xác cao. Nó thuộc vào nhóm Supervised Machine Learning Algorithms (thuật toán học có hướng dẫn), tức là máy học từ các ví dụ từ các mẫu dữ liệu đã có.

Ví dụ như ta có thể ứng dụng vào việc thiết kế một ứng dụng nghe nhạc có thể phán đoán được sở thích của nghe nhạc của người dùng dựa trên các hành vi như nhấn nút “thích” bài hát, “nghe đi nghe” lại nhiều lần các bài hát, “bỏ qua” các bài hát không thích …. Dựa trên tập dữ liệu đó ta có thể áp dụng NBC để tính toán ra các phong cách nhạc mà người dùng thích nhất, từ đó chúng ta có thể đưa ra các “gợi ý” nghe nhạc gần đúng nhất cho người dùng từ việc học hỏi từ những thói quen đó.

Phần 1 Định luật Bayes

Định luật Bayes được phát biểu như sau:

Định lý Bayes cho phép tính xác suất xảy ra của một sự kiện ngẫu nhiên A khi biết sự kiện liên quan B đã xảy ra. Xác suất này được ký hiệu là P(A|B), và đọc là “xác suất của A nếu có B”. Đại lượng này được gọi xác suất có điều kiện hay xác suất hậu nghiệm vì nó được rút ra từ giá trị được cho của B hoặc phụ thuộc vào giá trị đó.

Theo định lí Bayes, xác suất xảy ra A khi biết B sẽ phụ thuộc vào 3 yếu tố:

* Xác suất xảy ra A của riêng nó, không quan tâm đến B. Kí hiệu là P(A) và đọc là xác suất của A. Đây được gọi là xác suất biên duyên hay xác suất tiên nghiệm, nó là “tiên nghiệm” theo nghĩa rằng nó không quan tâm đến bất kỳ thông tin nào về B.

* Xác suất xảy ra B của riêng nó, không quan tâm đến A. Kí hiệu là P(B) và đọc là “xác suất của B”. Đại lượng này còn gọi là hằng số chuẩn hóa (normalising constant), vì nó luôn giống nhau, không phụ thuộc vào sự kiện A đang muốn biết.

* Xác suất xảy ra B khi biết A xảy ra. Kí hiệu là P(B|A) và đọc là “xác suất của B nếu có A”. Đại lượng này gọi là khả năng (likelihood) xảy ra B khi biết A đã xảy ra. Chú ý không nhầm lẫn giữa khả năng xảy ra B khi biết A và xác suất xảy ra A khi biết B.

Tóm lại định lý Bayes sẽ giúp ta tính ra xác suất xảy ra của một giả thuyết bằng cách thu thập các bằng chứng nhất quán hoặc không nhất quán với một giả thuyết nào đó. Khi các bằng chứng tích lũy, mức độ tin tưởng vào một giả thuyết thay đổi. Khi có đủ bằng chứng, mức độ tin tưởng này thường trở nên rất cao hoặc rất thấp, tức là xác xuất sảy ra giả thuyết sẽ thay đổi thì các bằng chứng liên quan đến nó thay đổi.

Công thức của định luật Bayes được phát biểu như sau:

Trong đó – P(A|B) là xác suất xảy ra của một sự kiện ngẫu nhiên A khi biết sự kiện liên quan B đã xảy ra. – P(B|A) là xác suất xảy ra B khi biết A xảy ra – P(A) là xác suất sảy ra của riêng A mà không quan tâm đến B. – P(B) là xác suất xảy ra của riêng B mà không quan tâm đến A.

Ở trên ta có thể thấy xác suất sảy ra của giả thuyết A phụ thuộc và xác suất của giả thuyết B, nhưng trong thực tế xác suất A có thể phụ thuộc vào xác suất của nhiều các giác thuyết khác có thể là B1, B2, B3 … Bn. Vậy định luật Bayes có thể được mở rộng bằng công thức sau:

Ví dụ 1 ta có một thống kê như sau:

Quốc hội Mỹ có 200 thượng nghị sĩ trong đó có: + 120 thượng nghị sĩ thuộc đảng Dân Chủ. + 80 thượng nghĩ sĩ thuộc đảng Cộng Hòa. + Số lượng Nữ giới trong đám thượng nghị sĩ là 60 người + Còn lại 140 người còn lại là Nam giới (giả dụ chả có ông thượng nghị sĩ nào mới đi Thái về cả). + Và số lượng Nữ giới trong đám Dân Dủ là 30 người.

Vậy nếu tôi chọn ngẫu nhiên một người trong đám thượng nghị sĩ thì tỷ lệ thượng nghị sĩ là Nữ giới và thuộc đảng Dân Chủ thì tỷ lệ là bao nhiêu?

Áp dụng công thức Bayes ta có thể tính toán được bằng công thức sau:

• P(Female|Democrat): Chính là tỷ lệ nữ giới thuộc đảng dân chủ trong cả đám thượng nghị sĩ cần tính toán
• P(Demorate|Female): Chính là tỷ lệ nữ giới trong đảng dân chủ
• P(Female): Chính là tỷ lệ nữ giới trong cả đám thượng nghị sĩ
• P(Democrat): Chính là tổng cả đám thượng nghị sĩ.

Ở đây với dữ liệu cho bên trên ta có thể tính toán được P(Democrat|Female) = Số nữ giới trong đám dân chủ / Tổng đám thượng nghị đảng dân chủ P(Democrat|Female) = 30/ 120 = 0.25

P(Female) = Số nữ giới trong cả đám thượng nghị sĩ / Tổng đám thượng nghị sĩ P(Female) = 60/200 = 0.3

P(Democrat) = Tổng đám thượng nghĩ sĩ P(Democrat) = 1

Vậy ta có thể tín ra P(Female|Democrat) theo công thức Bayes như sau:

P(Female|Democrat) = (0.25 * 0.3) / 1 = 0.075 Có nghĩa là nếu tôi chọn chọn ngẫu nhiên một người trong đám thượng nghị sĩ thì tỷ lệ thượng nghị sĩ là Nữ giới và thuộc đảng Dân Chủ thì tỷ lệ sẽ là “7,5%”.

Trên đây là một ví dụ rất đơn giản được tính toán bằng định lý Bayes mà thật ra nếu bạn nào giỏi có thể tự tính nhẩm ra mà ko cần sử dụng định lý trên.

Vậy tôi sẽ xét tiếp một ví dụ phức tạp hơn với nhiều dữ liệu và giả thuyết hơn hơn để minh họa định lý “Bayes mở rộng” bên trên.

Ví dụ 2: Trong một vụ thu hoạch ở một đồn điền trang trại các người làm đã thu hoạch được hơn 1000 trái cây các loại được phân loại thành 3 nhóm trái cây chính là “Chuối (banana)”, “Cam (orange)” và “các loại trái cây khác (other fruit)” và được phân l oại thành các kiểu như loại trái cây “dài (long), “không dài (not long), “ngọt (sweet)”, “không ngọt (not sweet)”, “màu vàng (yellow)”, “không phải màu vàng (not yellow)”

1 2 3 4 5 6 7 8

Type Long | Not Long || Sweet | Not Sweet || Yellow |Not Yellow|Total ___________________________________________________________________ Banana | 400 | 100 || 350 | 150 || 450 | 50 | 500 Orange | 0 | 300 || 150 | 150 || 300 | 0 | 300 Other Fruit | 100 | 100 || 150 | 50 || 50 | 150 | 200 ____________________________________________________________________ Total | 500 | 500 || 650 | 350 || 800 | 200 | 1000 ___________________________________________________________________

Bây giờ bài toàn đặt ra là tính ra tỷ lệ một quả chuối có thuộc tính là “màu vàng, dài, và ngọt” với tỷ lệ quả cảm và các loại hoa quả khác có cũng có thuộc tính là “màu vàng, dài, và ngọt”.

Áp dụng định lý Bayes ta sẽ có 3 công thức tính cho 3 loại trái cây như sau:

1. Tỷ lệ quả chuối với thuộc tính “vàng, dài và ngọt”

P(Long|Banana) = 400/500 = 0.8 P(Sweet|Banana) = 350/500= 0.7 P(Yellow|Banana) =450/500= 0.9 P(Banana) = 500/1000 = 0.5 P(Long) = 500/1000 = 0.5 P(Sweet) = 650/1000 = 0.65 P(Yellow) = 800/1000= 0.8 P(Banana|Long,Sweet,Yellow) = (0.8 * 0.7 * 0.9 * 0.5) / (0.5 * 0.65 * 0.8) = 0.97 Tức là tỷ lệ chuối với thuộc tính “vàng, dài và ngọt” là 97%

2. Tương tự ta cũng có thể tính ra tỷ lệ quả cam với thuộc tính “vàng dài và ngọt” với công thức sau:

Do tỷ lệ P(Long|Orange) = 0/500 = 0 cho nên P(Orange|Long, Sweet, Yellow) = 0 tức là tỷ lệ quả cam với thuộc tính “vàng dài và ngọt” là 0%.

3. Cũng thế ta ốp công thức Bayes để tính các trái cây còn lại với thuộc tính “vàng dài và ngọt” với công thức sau:

P(Long|Other Fruit) = 100/200= 0.5 P(Sweet|Other Fruit) = 150/200 = 0.75 P(Yellow|Other Fruit) =50/200= 0.25 P(Other Fruit) = 200/1000 = 0.2 P(Banana|Long,Sweet,Yellow) = 0.5 * 0.75 * 0.25 * 0.2 / (0.5 * 0.65 * 0.8) = 0.072 Tức là tỷ lệ các trái cây khác có thuộc tính “vàng dài và ngọt” chỉ là khoảng 7,2%

Vậy suy ra với trái cây với ba thuộc tính là “Vàng, dài và ngọt” thì có khả năng cao nhất đó là quả chuối.

Chúng ta có thể ứng dụng Naive Bayes Classification để tính tỷ lệ xác suất với rất nhiều các dạng bài toán khác nhau, với dữ liệu càng nhiều thì độ chính xác của thuật toán sẽ càng cao, và khi dữ liệu thay đổi thì kết quả cũng thay đổi theo.

Thuật toán Naive Bayes Classification được áp dụng vào các loại ứng dụng sau:

1. Real time Prediction: NBC chạy khá nhanh nên nó thích hợp áp dụng ứng dụng nhiều vào các ứng dụng chạy thời gian thực, như hệ thống cảnh báo, các hệ thống trading …

2. Multi class Prediction: Nhờ vào định lý Bayes mở rộng ta có thể ứng dụng vào các loại ứng dụng đa dự đoán, tức là ứng dụng có thể dự đoán nhiều giả thuyết mục tiêu.

3. Text classification/ Spam Filtering/ Sentiment Analysis: NBC cũng rất thích hợp cho các hệ thống phân loại văn bản hay ngôn ngữ tự nhiên vì tính chính xác của nó lớn hơn các thuật toán khác. Ngoài ra các hệ thống chống thư rác cũng rất ưu chuộng thuật toán này. Và các hệ thống phân tích tâm lý thị trường cũng áp dụng NBC để tiến hành phân tích tâm lý người dùng ưu chuộng hay không ưu chuộng các loại sản phẩm nào từ việc phân tích các thói quen và hành động của khách hàng.

4. Recommendation System: Naive Bayes Classifier và Collaborative Filtering được sử dụng rất nhiều để xây dựng cả hệ thống gợi ý, ví dụ như xuất hiện các quảng cáo mà người dùng đang quan tâm nhiều nhất từ việc học hỏi thói quen sử dụng internet của người dùng, hoặc như ví dụ đầu bài viết đưa ra gợi ý các bài hát tiếp theo mà có vẻ người dùng sẽ thích trong một ứng dụng nghe nhạc …

(Nguồn Thành Nam)

Hits: 0