ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
BÀI TẬP LỚN
HỌC PHẦN: XỬ LÍ NGÔN NGỮ TỰ NHIÊN
1. ĐỀ 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
Giáo viên hướng dẫn: PGS. TS. Lê Thanh Hương
Sinh viên thực hiện
1. Nguyễn Đình Dũng 20086079
2. Nguyễn Thành Lâm 20081487
3. Vũ Đông Lâm 20081496
4. Đoàn Ngọc Sơn 20082211
5. Trần Huy Hưng 20081307
Lời nói đầu
Ngày nay sự phát triển không ngừng của công nghệ thông tin, đặc biệt
là sự ra đời của Internet đã đưa con người lên một tầm cao mới. Sự ra đời
của các dịch vụ trên Internet làm cho nhu cầu trao đổi thông tin, tìm kiếm
thông tin của con người được đáp ứng một cách tốt nhất và nhanh nhất. Có
rất nhiều dịch vụ mới phát triển cùng công nghệ thông tin nhằm giúp công
nghệ thông tin thân thiết với người dùng hơn. Một trong những dịch vụ góp
phần không nhỏ vào việc giúp con người trao đổi thông tin một cách nhanh
chóng đó là dịch vụ thư điện tử (electronic mail).
Tốc độ phát triển của các dịch vụ thư điện tử ngày nay và những lợi ích
mà nó mang lại cho chúng ta là rất lớn. Qua thư điện tử người dùng không
chỉ nhận được thông tin mong muốn mà còn có thể nhận được âm thanh hình
ảnh, đồ họa và cả những kho dữ liệu khổng lồ mà trước đây việc trao đổi thư
từ qua tay không bao giờ có được. Tuy nhiên, thư điện tử không chỉ mang
đến cho con người nhiều lợi ích mà còn rất nhiều tác hại vô bổ khác, có thể
gây ra những thiệt hại to lớn nếu không biết cách loại bỏ và phòng chống nó.
Một trong những vấn đề nghiêm trọng cần giải quyết hiện nay trong các thư
điện tử đó là nạn thư rác hay còn gọi là “spam”. Đó là những thư từ quảng

Như vậy, theo định nghĩa thì các thư rác có thể có hại cho máy
tính (hiểu theo nghĩa vật chất), đôi khi còn làm chúng ta bực
mình khó chịu hoặc làm cho các thư từ khác (nhất là các thư
gửi có nghĩa quan trọng) bị lẫn lộn trong một đống thư mà chủ
yếu là các thư rác. Khiến cho việc tìm kiếm cũng mất thời gian
và cũng có thể khi xoá thư rác lại xoá nhầm thư quan trọng.
1.2. Sự cần thiết phải phân loại thư rác
3
3
Spam đang được coi là một vấn đề “lớn” trên mạng Internet.
Con số các “spam” gia tăng hàng ngày được nghiện cứu và
chiếm tỉ lệ lớn trên tổng số lượng email được gửi đi trên toàn
thế giới
Tốc độ tăng trưởng của Spam được thống kê theo lược đồ sau:
Ngày nay, khi spam mail trở thành một hình thức quảng cáo
chuyên nghiệp, phát tán virus, ăn cắp thông tin … thì một
chương trình anti-spam cho email là rất cần thiết. Chúng ta sẽ
phải mất khá nhiều thời gian để xóa những email “không mời
mà đến”, nếu vô ý còn có thể bị nhiễm virus, trojan, spyware …
và nặng nề hơn là mất thông tin như thẻ tín dụng, tài khoản
ngân hàng qua các email dạng phishing. Đối với người dùng
khi “checkmail” mà gặp phải thư rác sẽ gây ra một cảm giác
khó chịu và làm tốn thời gian để xóa thư đôi khi còn gây ra
những hậu quả nghiệm trọng hơn đối với những người dùng có
4
4
tính tò mò… Vì vậy việc xây dựng một hệ thống lọc thư rác cá
nhân tự động là rất cần thiết
1.3. Phân loại thư rác
Tổ chức hợp tác phát triển kinh tế OECD (Organization for

(spammer) thường xuyên sử dụng các điểm chuyển tiếp mở
này để che dấu tung tích xuất xứ của mình. Trong nhiều
trường hợp, tin tặc tận dụng các lỗ hổng bảo mật để “ra
lệnh” cho các máy chủ chuyển tiếp làm công việc của
spammer.
 Đố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” và ứng dụng phương
pháp này để phân loại các email cá nhân trong một Email
Client.
2. Bài toán phân loại văn bản
2.1. Định nghĩa
Có nhiều cách định nghĩa khác nhau về phân loại văn bản
nhưng nói một cách ngắn gọn dễ hiểu: Phân loại văn bản là sự
phân loại không cấu trúc các tài liệu văn bản dựa trên một tập
hợp của một hay nhiều loại văn bản đã được định nghĩa trước.
Quá trình này thường được thực thi bằng một hệ thống tự
động gán cho các tài liệu văn bản một loại nào đó.
Trong thực tế ứng dụng quan trọng nhất của phân loại văn bản
là giới hạn phạm vi tìm kiếm thông tin (bởi thay cho việc phải
lục soát tất cả các tài liệu họ chỉ tập trung vào một số loại văn
bản có liên quan đến thông tin mà họ cần tìm kiếm). Phân loại
6
6
văn bản góp phần quan trọng trong việc tổ chức thông tin và
quản lí tài liệu. Ứng dụng phổ biến nhất của phân loại văn bản

- Học một bộ phân loại văn bản
- Tiến hành phân loại văn bản
Trong đó, lựa chọn đặc trưng văn bản là quá trình phân
tích văn bản thành các từ hay cụm từ. Biểu diễn văn bản là
cách thể hiện văn bản dưới dạng một vector mà không gian
của nó là tập các đặc trưng đã lựa chọn. Căn cứ vào các đặc
trưng đã chọn có thể học một bộ phân loại văn bản như Naive
Bayes hay kNN… Đầu ra của quá trình này sẽ là một máy dùng
để phân loại các tài liệu cần thiết (tiến hành phân loại văn
bản).
2.3. Phương pháp PLVB – Mô hình xác suất Naïve Bayes
Dựa trên các đặc trưng của văn bản đã xuất hiện nhiều chiến
lược phân loại văn bản đã được đề xuất và áp dụng trong các
tập tài liệu khác nhau. Hiệu quả của các phương pháp đó tuy
chỉ là tương đối nhưng đã hỗ trợ rất nhiều trong truy cập,
quản lí, lọc thông tin. Các phương pháp phân loại văn bản cho
kết quả tốt thường được sử dụng như:
- Nguyên mẫu (prototype)
- Mô hình xác suất Naive Bayes
- Phương pháp SVM (Support Vectors Machines)
- Phương pháp cây quyết định (Decision Trees)
8
8
- Phương pháp mạng neuron (Neuron Network)
Trong phạm vi đề tài, nhóm em chỉ xin trình bày cụ thể về
phương pháp phân loại văn bản sử dụng các mô hình xác
suất Naïve Bayes. Kĩ thuật phân hoạch của Naive Bayes dựa
trên cơ sở định lí Bayes và đặc biệt phù hợp cho các trường
hợp phân loại có kích thước đầu vào là lớn. Mặc dù Naive
Bayes khá đơn giản nhưng nó có khả năng phân loại tốt hơn

bản là độc lập thống kê. Cơ sở của phương pháp phân loại văn bản
Naive Bayes là chủ yếu dựa trên các giả định của Bayes. Giả thuyết
Bayes gán cho mỗi tài liệu văn bản cần phân loại một giá trị xác
suất.
Xác suất P(ck| di) gọi là xác suất mà tài liệu di có khả năng thuộc
vào lớp văn bản ck được tính toán như sau:
tài liệu di sẽ được gán cho loại văn bản nào có xác suất hậu
nghiệm cao nhất nên được biểu diễn bằng công thức:
trong đó N là tổng số tài liệu.
Tóm lại phân loại văn bản sử dụng thuật toán Naive Bayes có
thể diễn đạt một cách ngắn gọn như sau:
Với mỗi văn bản D (document), người ta sẽ tính cho mỗi loại một
xác suất mà tài liệu D có thể thuộc vào lớp tài liệu đó bằng việc sử
dụng luật Bayes:
12
12
Trong đó: D là tài liệu cần phân loại, Ci là một tài liệu bất kì. Theo
giả định của Naive Bayes xác suất của mỗi từ trong tài liệu D là
độc lập với ngữ cảnh xuất hiện các từ đồng thời cũng độc lập với
vị trí của các từ trong tài liệu. Xác suất P(D|Ci) được tính toán từ
tần suất xuất hiện của các từ đơn wj (word) trong tài liệu D
l là tổng số từ w trong tài liệu D:
Như vậy biểu thức (1) có thể được viết lại như sau:
Giá trị lớn nhất của xác suất P(Ci | D) được đưa ra bởi nguời làm
công tác phân loại. Giá trị này được gọi là ngưỡng hay ranh rới
giữa các lớp văn bản mà chúng có thể chứa tài liệu D.
3. Quá trình hoạt động của bộ lọc thư rác Bayes
Bộ lọc thư Bayes dựa trên một cơ sở tất yếu là hầu hết các sự kiện
đều phụ thuộc và đó là xác suất của các sự kiện xuất hiện trong
tương lai, có thể được suy luận ra từ những sự xuất hiện trước đó

đây là cơ sở để phân loại các thư rác. Cũng giống như phân loại
thư hợp lệ khái niệm thư rác cũng tùy thuộc vào người sử dụng
rất nhiều.
3.4. Tính các giá trị xác suất bằng thuật toán Naïve Bayes
Máy lọc thư rác sử dụng thuật toán Naive Bayes cung cấp một
chức năng lọc thư tự rác tự động. Trên cơ sở sử dụng các xác suất
gần đúng để tính toán các khả năng một thư điện tử có thể là thư
rác hay không. Sự tính toán này là quá trình tìm kiếm các từ
thường xuất hiện trong các thư điện tử và so sánh chúng với tập
mẫu. Thuật toán bắt đầu bằng việc học các nội dung của các thư
điện tử hợp lệ và nội dung của những thư rác. Để sau đó khi nhận
vào một thư điện tử mới, các thông tin có sẵn từ tập mẫu, các tiến
trình tiền xử lí trước sẽ được áp dụng trên cơ sở nội dung của các
thư điện tử.
Nguyên tắc tính các xác suất bằng thuật toán Bayes:
- Giả sử nội dung của mỗi thư điện tử là: content
- Lớp thư rác kí hiệu là: spam
- Lớp thư hợp lệ kí hiệu là: ham
- Xác suất để một thư điện tử là thư rác: P(spam|content)
- Word1, word2, word3…wordm là các từ đặc trưng xuất hiện
trong content
Ta có:
15
15
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
Để đơn giản hóa công thức và tính toán chúng ta giả định rằng
xác suất của các từ đó được bao hàm trong một văn bản là độc lập

Folder – là nơi mà người sử dụng email rất ít khi kiểm tra tới. Đối
với hầu hết người dùng, việc “vứt nhầm thư đúng” này có tác hại
nghiêm trọng hơn rất nhiều so với việc họ phải nhận thư rác.
Nếu một người nhận được càng nhiều thư rác thì anh ta càng khó
tìm và nhận ra được những thư thường bị “lạc” trong mục Thư
rác. Và dĩ nhiên, nếu một bộ lọc thư rác càng hiệu quả tức là xác
suất gán mác đúng cho mỗi bức thư càng lớn (cái này thì quá tốt
rồi) nhưng cũng đồng nghĩa với việc anh ta sẽ càng gặp nhiều khó
khăn trong việc lục lọi hòm thư rác để xem là có thư nào quan
trọng bị vứt nhầm ở đấy không!
Sau đây, nhóm em xin được trình bày chi tiết về thuật toán
Naïve Bayes cải tiến theo phương pháp của Paul Graham:
Cũng giống như giải thuật Naïve Bayes cơ bản, thuật toán cải tiến
17
17
này cũng dựa trên nguyên tắc sử dụng giải thuật học máy để làm
cơ sở:
4.1. PHA HUẤN LUYỆN (TRAINING PHRASE)
- Từ tập dữ liệu mẫu là các file text (mỗi file chứa nội dung của một
email) và một file index lưu giữ thông tin về nhãn đúng của từng
email (dùng cho việc tối ưu tham số và tạo báo cáo), ta chia các
file text (email) ra làm 2 tập: tập huấn luyện (Training Set) và tập
kiểm tra (Test Set)
- Đọc nội dung của các email trong Training Set, đọc file index để
tìm nhãn đúng của mỗi email. Nếu một email là SPAM thì ghi thêm
nội dung của mail này (không bao gồm tiêu đề và các thông tin
khác) vào file SPAM.txt, ngược lại nội dung của mail sẽ được ghi
thêm vào file HAM.txt.
- Sau khi tiến hành đọc này, ta thu được 2 file có kích thước tương
đối lớn. Mục đích của bước lưu tất cả nội dung mail của mỗi nhóm

từ trong tập HAM
o 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.
o Cuối cùng, phần quan trọng nhất là công thức tính xác suất của
toàn bộ email. Như đã trình bày ở phần trên, ý 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.
Để hiệu rõ hơn về xác suất kết hợp, ta có thể lấy ví dụ: 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
19
19
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?
Bài toán trên cho ta một cách hiểu dễ dàng nhất về khái niệm xác
suất kết hợp. Trong phạm vi đề tài, nhóm em sẽ chỉ đưa ra công
thức tính xác suất này mà không giải thích về mặt toán học nữa.
Nếu gọi a, b là hai xác suất đơn. Thì xác suất kết hợp của chúng sẽ
được tính bằng:
ab / (ab + (1-a)*(1-b))
Trong ví dụ trên, ta có: a = 0.6, b = 0.8

Xác suất kết hợp = 0.6*0.8/(0.6*0.8 + 0.4*0.2) = 0.857 > hai

kinh nghiệm của nó - những gì mà bộ lọc đã được “học” từ các ví
dụ trong tập huấn luyện - để đánh giá các email mới mà nó “chưa
được học”.
- Cuối cùng là so sánh kết quả nhãn mà bộ lọc trả về với nhãn đúng
của mỗi email được lưu trong file index để đưa ra đánh giá hiệu
quả thuật toán phân loại bằng cách thống kê và viết báo cáo.
III. Ứng dụng Demo bộ lọc thư rác SpamFilterSample
1. Giới thiệu;
SpamFilterSample là một chương trình ứng dụng C# để cài đặt
thuật toán phân loại thư rác Naïve Bayes theo cách của Paul
Graham. Chương trình nguồn được tham khảo trên Internet, phần
thuật toán của pha huấn luyện được nhóm em kế thừa và có thay
đổi chút ít. Về cơ bản, thuật toán được cài đặt trong chương trình
cũng chính là thuật toán cải tiến đã được trình bày ở trên. Tuy
nhiên, phần kiểm thử Testing Phrase còn khá đơn giản: không có
tập kiểm thử, chỉ kiểm tra được từng email nên khó thực hiện
đánh giá vì số lượng test nhỏ. Vì vậy, nhóm em đã thiết kế lại toàn
21
21
bộ phần Test: tìm tập mẫu khác, phân chia tập mẫu thành các tập
Training Set và Test Set có kích thước khác nhau để đánh giá và so
sánh hiệu quả của thuật toán, thiết kế thêm tính năng kiểm tra
hàng loạt Test Batch và tự động so khớp kết quả nhãn thu được để
đưa ra các chỉ số đặc trưng về hiệu năng: Precision và Recall, với
mỗi tập huấn luyện và tập kiểm thử xác định.
2. Chương trình:
Có 3 lớp cần quan tâm:
- Lớp Corpus: đọc file văn bản cần kiểm tra (coi như email chỉ ở
dạng văn bản thuần text), sau đó tiến hành lưu trữ các từ cùng với
tần số xuất hiện của chúng trong file văn bản đó.

Box
Ngoài ra, thay vì nạp dữ liệu và tính toán trực tiếp như trên, có thể
nạp các giá trị xác suất này từ Bảng xác suất bằng cách bấm chọn
nút Load Processed Data, (nếu dữ liệu này đã được lưu trong file
ProbList.txt). Nếu chưa có dữ liệu này thì bấm chọn nút Save
Processed Data để lưu lại (tránh việc nạp dữ liệu từ đầu và tính
toán lại, gây mất thời gian)
23
23
Testing Phrase:
Có hai cách thực hiện kiểm thử: test hàng loạt và test thủ công
- Test hàng loạt: thực hiện bằng cách chọn bấm 1 trong 3 nút “Test
Batch…” để tiến hành test hàng loạt (các file chứa nội dung email)
với các kích thước khác nhau (các file này được chọn lấy từ 2000
thư cuối cùng – khác với các file của tập huấn luyện)
24
24
Các giá trị đánh giá hiệu quả của thuật toán được cài đặt sẽ được
hiện ra trong Text Box:
- Test thủ công: người dùng nhập hoặc dán toàn bộ nội dung thư
cần kiểm tra vào Text Box. Sau đó bấm nút Manual Test để kiểm
tra. Kết quả phân loại sẽ được hiện ra trong bảng thông báo ngay
sau đó.
25
25