ĐẠ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