thuật toán bayes và ứng dụng

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

---------<>---------

Nguyễn Văn Huy

THUẬT TOÁN BAYES VÀ ỨNG DỤNG

KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY

Ngành : Công Nghệ Thông Tin

HÀ NỘI – 2009

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

---------<>---------

Nguyễn Văn Huy

THUẬT TOÁN BAYES VÀ ỨNG DỤNG

KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY

Ngành : Công Nghệ Thông Tin

Cán bộ hướng dẫn: ThS. Nguyễn Nam Hải

Cán bộ đồng hướng dẫn: ThS. Đỗ Hoàng Kiên

HÀ NỘI – 2009

Thuật toán Bayes và ứng dụng

ii

Lời cảm ơn

Viết khóa luận khoa học là một trong những việc khó khăn nhất mà em phải

hoàn thành từ trước đến nay. Trong quá trình thực hiện đề tài em đã gặp rất nhiều khó

khăn và bỡ ngỡ. Nếu không có những sự giúp đỡ và lời động viên chân thành của

nhiều thầy cô bạn bè và gia gia đình có lẽ em khó có thể hoàn thành luận văn này.

Đầu tiên em xin gửi lời cảm ơn chân thành đến thày Nguyễn Nam Hải và thày

Đỗ Hoàng Kiên đã trực tiếp hướng dẫn em hoàn thành luận văn này. Nhờ có thày mà

em được tiếp cận với nguồn tài liệu giá trị cũng như những góp ý quý giá sau này. Bên

cạnh sự giúp đỡ đó, em còn được các thày bên Trung tâm máy tính tạo mọi điều kiện

tốt nhất về cơ sở vật chất cũng như hướng dẫn chỉ bảo ân cần để em được tiếp cận với

hệ thống. Em biết ơn những ngày tháng được làm việc bên các thày, em không thể nào

quên những ngày tháng tuyệt vời đó.

Trong quá trình góp nhặt những kiến thức quý báu, các thày, cô, bạn bè là

những người đã cùng em sát cánh trong suốt thời gian em học tập và nghiên cứu dưới

mái trường Đại học Công nghệ.

Trong những nỗ lực đó, không thể không kể đến công lao to lớn không gì có thể

đền đáp của cha mẹ những người đã sinh thành, dưỡng dục con nên người, luôn nhắc

nhở, động viên con hoàn thành tốt nhiệm vụ.

Hà Nội

Tháng 5, 2009

Nguyễn Văn Huy

Thuật toán Bayes và ứng dụng

iii

Tóm tắt nội dung

Thống kê (toán học) là bộ môn toán học rất quan trọng và có nhiều ứng dụng to

lớn trong thực tế, giúp con người rút ra thông tin từ dữ liệu quan sát, nhằm giải quyết

các bài toán thực tế trong cuộc sống.

Trong khóa luận này trình bày về một tiếp cận thống kê trong việc dự đoán sự

kiện dựa vào lý thuyết Bayes. Lý thuyết này nói về việc tính xác suất của sự kiện dựa

vào các kết quả thống kê các sự kiện trong quá khứ. Sau việc tính toán mỗi sự kiện

được gán xác xuất hay điểm (tùy vào mỗi phương pháp đánh giá) ứng với khả năng có

thể xảy ra với sự kiện đó. Và cuối cùng dựa vào ngưỡng để phân loại cho các sự kiện.

Sau phần lý thuyết chúng ta sẽ tìm hiểu về bài toán thực tế trong ngành công

nghệ thông tin. Bài toán về việc lọc thư rác tự động. Giải quyết bài này là sự kết hợp

từ rất nhiều phương án như DNS Blacklist, kiểm tra người nhận, người gửi, dùng bộ

lọc Bayes, chặn địa chỉ IP, Blacklist/Whitelist,.... Dùng bộ lọc Bayes là phương án

thông minh nó gần gũi với người dùng bởi chính người dùng đã huấn luyện nó nhận

biết thư rác. Khóa luận này tập chung vào việc tìm hiểu bộ lọc thư rác Bayesspam –

mã nguồn mở, cài đặt cho hệ thống email có tên là SquirrelMail – mã nguồn mở đang

được dùng cho hệ thống email của trường đại học Công nghệ - Coltech Mail. Kết quả

cho thấy bộ lọc có mức độ hoạt động hiệu quả là khác nhau tùy thuộc việc người dùng

huấn luyện cho bộ lọc thông qua các thư điện tử mà họ cho là thư rác nhưng nói chung

bộ lọc đã đem lại hiệu quả khá tốt.

Thuật toán Bayes và ứng dụng

iv

Mục lục

Chương 1 Giới thiệu.................................................................................. 1

1.1 Tổng quan.......................................................................................................1

1.2 Cấu trúc ..........................................................................................................3

Chương 2 Cơ sở lý thuyết.......................................................................... 4

2.1 Phát biểu định lý Bayes ..................................................................................4

2.2 Cực tiểu hóa rủi ro trong bài toán phân lớp Bayes...........................................5

2.3 Phân lớp Bayes chuẩn tắc .............................................................................13

2.4 Miền quyết định............................................................................................20

Chương 3 Phân lớp Naive Bayes............................................................. 22

3.1 Định nghĩa ....................................................................................................22

3.2 Các mô hình xác suất Naive Bayes ...............................................................23

3.3 Ước lượng tham số .......................................................................................24

3.4 Xây dựng một classifier từ mô hình xác suất.................................................25

3.5 Thuật toán phân loại văn bản Naive Bayes....................................................25

Ví dụ: Phân loại thư điện tử bằng Naive Bayes classifier...................................27

Chương 4 Giải quyết bài toán lọc thư rác .............................................. 30

4.1 Đặt vấn đề ....................................................................................................30

4.2 Bài toán ........................................................................................................31

4.3 Tiền xử lý mỗi lá thư điện tử.........................................................................31

4.4 Dùng luật Bayes tính xác suất.......................................................................32

4.5 Huấn luyện cho bộ lọc Bayes........................................................................33

4.6 Lọc thư đến, có là thư rác không? .................................................................34

4.7 Bộ lọc BayesSpam........................................................................................35

4.8 Một số cải tiến cho bộ lọc BayesSpam..........................................................38

Chương 5 Kết luận .................................................................................. 40