Các thành viên:
Nguyễn Đình Dũng 20086079
Nguyễn Thành Lâm 20081487
Vũ Đông Lâm 20081496
Đoàn Ngọc Sơn 20082211
Trần Huy Hưng 20081307
“Đề tài: PHÂN LOẠI THƯ RÁC DÙNG THUẬT TOÁN NAÏVE
BAYES CẢI TIẾN của PAUL GRAHAM”

Thư rác:
- Chứa các quảng cáo sản phẩm, dịch vụ, đăng kí website trả phí,… được gửi với số lượng lớn và có
giá trị thấp
- Gây phiền toái, mất thời gian cho việc sắp xếp, tìm kiếm thư cá nhân
- Mất thông tin cá nhân, thông tin tài khoản, thông tin thẻ tín dụng,… và các hình thức lừa đảo qua
mạng
Thư rác – Tác hại thư rác

Tốc độ tăng trưởng của thư rác: chiếm tỉ lệ lớn trong tổng số thư được gửi đi trên phạm vi
toàn cầu  …
Thư rác – tác hại thư rác

Đối với các email cá nhân thì phương pháp lọc thư rác phổ biến hiện nay là “phân loại qua nội
dung của các email” bằng việc ứng dụng các phương pháp phân loại văn bản.

Phân loại email thực chất là phương pháp “phân loại văn bản hai lớp” dựa vào nội dung của
các email được gửi đến.

Trong đề tài này nhóm em xin trình bày một phương pháp phân loại văn bản khá phổ biến
“Naive Bayes”
Bài toán Phân loại thư rác



Trong đó total được xác định như sau:

Total = P(content | spam)*P(spam) + P(content | ham)*P(ham)

P(spam) = total spam / total messages

P(ham) = total ham / total messages


ĐẾM TẦN SỐ XUẤT

XUẤT HIỆN CỦA TỪ,

ĐẾM SỐ THƯ mỗi loại.
Thuật toán Naïve Bayes trong PLTR

Theo tác giả của bài viết Paul Graham, để giải quyết bài toán thư rác, ta vẫn
có thể sử dụng thuật toán Naïve Bayes với một vài thay đổi so với thuật toán
ban đầu.

Ý tưởng cơ bản của thuật toán cải tiến này là sử dụng xác suất kết hợp của
các từ xuất hiện trong mail.
Thuật toán Naïve Bayes của Paul Graham

Một người có chiều cao trên 1m9 thì xác suất anh ta có chơi bóng rổ là 60%.
Một người đang cầm 1 quả bóng rổ thì xác suất anh ta chơi bóng rổ lên đến
80%. Hỏi một người vừa cao trên 1m9, vừa cầm bóng rổ trên tay thì xác suất
anh ta chơi bóng rổ là bao nhiêu?


suất. Đến đây, ta bắt đầu đếm số lần xuất hiện của một từ trong mỗi nhóm SPAM vs. HAM, từ đó tính
ra xác suất từ đó xuất hiện trong SPAM. Sau đó lưu các giá trị xác suất này vào một danh sách được sắp
xếp theo giá trị xác suất (kiểu SortedList) và gọi danh sách này là Bảng xác suất.
Thuật toán NB cải tiến – Training Phrase

Xác suất một từ xuất hiện trong thư rác được tính bởi công thức:

P (SPAM|w) = P(w|SPAM) / ((P(w|SPAM) + P(w|HAM)

Trong đó:

- P(w|SPAM) = số lần xuất hiện của w trong SPAM / số từ trong tập SPAM

- P(w|HAM) = số lần xuất hiện của w trong HAM / số từ trong tập HAM

Xác suất của toàn bộ email sẽ được tính dựa vào xác suất của 15 từ “đáng quan tâm” nhất trong
thư đó (15 most interesting words) chứ không phải của tất cả các từ trong thư. Trong đó, mức độ
đáng quan tâm của mỗi từ được tính dựa vào độ chênh lệch về xác suất P(SPAM|w) với giá trị
trung lập 0.5, tức là đây là 15 từ đặc trưng cho email này, các giá trị xác suất này rất gần giá trị xác
suất tuyệt đối 0 hoặc 1 và có ảnh hưởng lớn đến việc phân loại email đó. Con số 15 cũng được
Paul Graham lựa chọn, có thể thay đổi để đánh giá hiệu quả theo tham số này.
Thuật toán NB cải tiến – Training Phrase

Sau khi xong xác suất là thư rác của toàn bộ email,cần một giá trị ngưỡng để thực hiện điều này.
Lẽ ra việc chọn ngưỡng sẽ thuộc về pha tối ưu (Cross Validation) dựa vào việc đánh giá hiệu quả
của pha huấn luyện với các giá trị ngưỡng khác nhau (trong bài toán Học máy thì ngưỡng là một
tham số học – learning parameter - cần được xác định trong pha Tối ưu)

bỏ qua



File ProbList.txt lưu trữ Bảng xác suất, sinh ra khi thực hiện nạp dữ liệu huấn luyện.

File Result.txt lưu kết quả gán nhãn do bộ lọc thực hiện khi kiểm tra hàng loạt (Test Batch)
Hướng dẫn sử dụng chương trình:
Cảm ơn mọi người đã lắng nghe 
-The end-