TRƯNG ĐI HC BCH KHOA H NI
VIỆN CÔNG NGHỆ THÔNG TIN V TRUYỀN THÔNG
ĐỒ N MÔN XỬ LÝ NGÔN NGỮ TỰ NHIÊN
Đề tài: Xây dựng chương trình lọc thư rác sử dụng phương pháp Naïve Bayes
Giảng viên hướng dẫn: PGS TS Lê Thanh Hương
Sinh viên thực hiện:
Họ và tên MSSV Lớp
Đặng Văn Hùng 20071370 HTTT-K52
Nguyễn Bích Ngọc 20072105 HTTT-K52
Trịnh Thị Lan Phượng 20062468 HTTT-K52
Voin sophat 20073936 HTTT-K52
Hà Nội, 01/05/2012
1
LI MỞ ĐẦU
Thư rác (spam) là thư điện tử được gửi hàng loạt với nội dung mà người nhận không
mong đợi, không muốn xem, hay chứa những nội dung không liên quan đến người nhận
và thường được sử dụng để gửi thông tin quảng cáo . Do có giá thành tương đối thấp so
với các phương pháp quảng cáo khác, thư rác hiện chiếm một tỷ lệ lớn và ngày càng tăng
trong tổng số thư điện tử được gửi qua Internet. Sự xuất hiện và gia tăng thư rác không
những gây khó chịu và làm mất thời gian của người nhận mà còn ảnh hưởng tới đường
truyền Internet và làm chậm tốc độ xử lý của máy chủ thư điện tử, gây thiệt hại lớn về
kinh tế.
Để loại bỏ hoặc giảm thiểu ảnh hưởng của thư rác, nhiều cách tiếp cận khác nhau đã
được nghiên cứu và sử dụng. Giải pháp đấu tranh với thư rác rất đa dạng, bao gồm từ các
cố gắng về pháp lý trong việc xây dựng luật ngăn chặn phát tán thư rác cho tới những giải
pháp kỹ thuật nhằm phát hiện và ngăn chặn thư rác trong những giai đoạn khác nhau của
quá trình tạo và phát tán thư. Trong số giải pháp được sử dụng, lọc thư theo nội dung
đang là một trong những giải pháp được sử dụng rộng rãi và có triển vọng nhất. Lọc thư
theo nội dung là phương pháp phân tích nội dung thư để phân biệt thư rác với thư bình
thường, kết quả phân tích sau đó được sử dụng để quyết định chuyển tiếp thư đến người
nhận hay không.

2
I. Tổng quan về thư rác
1. Khái niệm thư rác
Thư điện tử hay email (electronic mail) còn được gọi là điện thư, là một hệ thống
chuyển nhận thư từ qua mạng máy tính
Thư rác (spam) là những bức thư điện tử không yêu cầu, không mong muốn và được
gửi hàng loạt tới nhiều người nhận. “Thư không yêu cầu” ở đây nghĩa là người nhận thư
không yêu cầu người gửi gửi bức thư đó. “Thư được gửi hàng loạt” nghĩa là bức thư mà
người nhận nhận được nằm trong một loạt các thư được gửi đi cho nhiều người khác và
các bức thư này có nội dung tương tự nhau.
Một bức thư được gọi là thư rác chỉ khi nó là thư không yêu cầu và được gửi hàng
loạt. Nếu thư rác chỉ là thư không mong muốn thì nó có thể là những bức thư làm quen,
được gửi lần đầu tiên, còn nến thư rác chỉ là thư được gửi hàng loạt thì nó có thể là những
bức thư gửi cho khách hành của các công ty, các nhà cung cấp dịch vụ.
Như định nghĩa ở trên, thư rác là thư không yêu cầu và được gửi hàng loạt. Nhưng
yếu tố quan trọng nhất để phân biệt thư rác với thư thông thường phải là ở nội dung bức
thư. Khi một người nhận được thư rác, người đó không thể xác định được thư có được
gửi hàng loạt hay không nhưng có thể nói chính xác đó là thư rác sau khi xem nội dung
thư. Đặc điểm này chính là cơ sở cho giải pháp phân loại thư rác bằng cách phân tích nội
dung thư.
Phần lớn thư rác là các thư quảng cáo cho các hàng hóa hoặc dịch vụ. Tuy nhiên có
thể có những thư rác mang nội dung khác, có thể chia thành các nhóm: thư có nội dung
chính trị, thư từ thiện, thư có nội dung tôn giáo, thư có kèm mã độc tấn công máy tính
người sử dụng
3
2. Tác hại của thư rác
- Thư rác gây thiệt hại về kinh tế cho người nhận thư trong trường hợp người nhận thư
phải trả tiền cho lượng thông tin truyền qua mạng.
- Thư rác có thể làm đầy hộp thư người nhận và do vậy làm thất lạc những thư bình
thường đến sau.

- Thư rác làm tốn thời gian do người nhận phải mở thư và xoá thư khỏi hộp thư của
mình.
- Thư rác chiếm một phần đường truyền Internet và làm tốn thời gian xử lý của máy
chủ
- Thư rác có thể chứa các mã độc, các virus tấn công máy tính của người sử dụng, lấy cắp
thông tin cá nhân hoặc phá hoại máy tính, hệ thống máy chủ của công ty ,tổ chức, cá
nhân
4
3. Quá trình phát tán của thư rác
Quá trình phát tán thư rác gồm 2 bước:
- Thu thập các địa chỉ email
o Nhận dạng ký tự email
o Dụ nạn nhân điền thông tin địa chỉ email
o Mua cơ sở dữ liệu các webstite
o Tạo email bằng dictionary attack
- Phát tán thư rác:
o Sử dụng hệ thống máy tính , modem và đường truyền internet
o Spam bằng các máy chủ
o Hệ thống botnet

5
4. Các biện pháp phân loại thư rác hiện nay
Hiện nay tất cả các nhà cung cấp dịch vụ mail đều áp dụng các công nghệ lọc thư rác sau:
 Sử dụng DNS Blacklistb.
 Sử dụng SURBL List
 Chặn IP
6
 Kiểm tra địa chỉ
 Sử dụng bộ lọc Bayesian
7

 Sử dụng danh sách Black/white list
 Sử dụng Challenge/Response
8
 Kiểm tra header
 Report Spam Emai
Trong nội dung nghiên cứu, nhóm xin trình bày về các phân loại thư rác bằng phương
pháp học máy, lọc theo nội dung thư : “Áp dụng giải thuật Naïve Bayes phân loại thư
rác”
9
II. Định lý Bayes và giải thuật Naïve Bayes
1. Định lý Bayes
Đị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 D khi biết
sự kiện liên quan h đã xảy ra. Xác suất này được ký hiệu là P(D|h), và đọc là "xác suất
của D nếu có h". Đạ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 h hoặc phụ thuộc vào giá trị đó.
Công thức:
( | ). ( )
( | )
( )
P D h P h
P h D
P D
=
Trong đó các đại lượng:
P(h) : Xác xuất trước rằng giả thiết h là đúng
P(D) : Xác suất trước rằng tập dữ liệu D được quan sát.
P(D|h) : Xác suất việc quan sát được tập dữ liệu D, với điều kiện giả thiết h đúng
2. Giải thuật Naïve Bayes phân loại văn bản
Phương pháp phân loại văn bản bằng Naïve Bayes coi xác suất xuất hiện của các từ
trong một văn bản là độc lập thống kê.

Cơ sở của phương pháp này :dựa trên định lí Bayes trong xác suất.
Cần tính xác suất để một văn bản rơi vào các lớp văn bản khác nhau.
Tài liệu cần phân loại sẽ được gán cho lớp văn bản nào có xác suất lớn nhất
Một bài toán phân loại có thể biểu diễn gồm có:
Một tập học D_train trong đó mỗi ví dụ học x được biểu diễn bằng 1 vector n chiều:
(x
1,
x
2
,…. ,x
n
)
- Một tập nhãn xác định các lớp : C = {c
1
,c
2
,…,c
m
}
- Một ví dụ mới z sẽ được phân loại vào lớp nào.
10
Để xác định được phân lớp có thể phù hợp nhất đối với ví dụ z, ta xác định bởi:
1 2
arg max ( , , | ). ( )
i
n i i
c C
P z z z c P c
∈
Với giả thiết rằng

1 2
( , , )
n
P z z z
là như nhau đối với các lớp
Phân loại Naïve Bayes tìm phân lớp có thể nhất đối với z:
1
arg max ( ). ( | )
i
n
NB i j i
c C
j
C P c P z c
∈
=
=
∏
Giải thuật phân loại Naïve Bayes:
- Giai đoạn học (Training Phase), sử dụng một tập học. Đối với mỗi phân lớp c
i
∈ c
ta tính giá trị xác suất trước P(c
i
). Đối với mỗi giá trị thuộc tính x
j
ta tính giá trị
xác suất của thuộc tính đó đối với một phân lớp c
i
: P(x

j
|c
i
)
Sau giai đoạn học ta được dữ liệu học.
- Giai đoạn phân lớp đối với một ví dụ mới: Đối với mỗi phân lớp c
i
∈ c ta tính giá
trị của biểu thức:
1
( ). ( | )
n
i j i
j
P c P z c
=
∏
Phân lớp của z là lớp có thể nhất:
*
1
arg max ( ). ( | )
i
n
i j i
c C
j
C P c P z c
∈
=
=

∏
11
III. Chương trình phân loại thư rác sử dụng giải thuật Naïve Bayes
1. Mô tả bài toán
Bài toán:
- Input: 1 email chưa nhận dạng thư rác hay thư thường
- Output: Kết quả phân loại là thư rác không?
(Giải quyết bài toán phân loại thư rác là thư có nội dung tiếng Anh)
Biểu diễn:
- Tập học D_Train với mỗi email là 1 ví dụ học.
- Tập nhãn xác định lớp: C={c0,c1}. C0: thư rác, c1: thư thường.
Sau quá trình học, dữ liệu học sẽ được lưu trữ dạng cây nhị phân tìm kiếm, mỗi nút của
cây nhị phân gồm có : từ gốc, tần suất xuất hiện trong thư rác, tần suất xuất hiện trong
thư thường
Một ví dụ mới là 1 email sẽ được phân loại vào lớp nào
2. Mô tả bộ dữ liệu
Chương trình sử dụng bộ dữ liệu :CSDMC2010 SPAM là bộ dữ liệu sử dụng cho hệ
thống lọc thư rác. Bộ dữ liệu này gồm 2 phần chính:
Tập các ví dụ học (TRAINING): 4327 email, với 2949 non-spam và 1378 spam.
SPAMTrain.label : nhãn của các email với 1 cho non-spam và 0 cho spam
Tập các ví dụ để kiểm tra(TESTING): 4292 email chưa được phân loại
Để đánh giá được một cách tốt nhất chương trình , ta sẽ sử dụng dữ liệu sử dụng trong
chương trình được lấy từ tậpTraining của CSDMC2010 SPAM. Chia tập TRAINING
thành 2 phần như sau: (Các email lấy ngẫu nhiên)
12
Tập Training: 3000 email với 957 spam và 2043 non-spam
Tập Testing: 1327 email với 421 spam và 906 non-spam
3. Quá trình tiền xử lý
Trong bài toán phân loại thư rác này, ta chỉ phân loại dựa vào nội dung email, do vậy,
mỗi email đầu vào (có định dạng .eml) sẽ trải qua bước tiền xử lý nhằm loại bỏ các

stopword, khoảng trắng, tiêu đề…chỉ lấy nội dung email làm đầu vào cho hệ thống học
và test.
4. Quá trình học
Từ bộ dữ liệu đầu vào, ta tính các xác suất:
Pc0: tần số thư rác trong tập học
Pc1: tần số thư thường trong tập học
Sau quá trình tiền xử lý, mỗi email sẽ được biểu diễn thành tập các từ nguyên gốc
(Với từ có nhiều từ loại sẽ được đưa thống nhất về 1 loại từ)Với mỗi từ trong tập
Training, ta tính tần suất xuất hiện của mỗi từ trong thư thường và thư rác:
;
Kết quả quá trình học, ta được 1 cây học. Cây học là cây nhị phân tìm kiếm, với mỗi
nút dữ liệu chưa 3 trường dữ liệu: từ gốc, tần suất xuất hiện trong thư rác, tần suất xuất
hiện trong thư thường.
Cấu trúc 1 nút trong cây học:
Word: x F
0
(x) F
1
(x)
X
i
F
0
(x
i
) F
1
(x
i
)

F
0
(x
i
) : tần suất xuất hiện của từ x
i
trong thư rác
F
1
(x
i
) : tần suất xuất hiện của từ x
i
trong thư thường
13
5. Quá trình test
Cho đầu vào là 1 email chưa được phân loại. Email này cũng cần được đưa qua quá
trình tiền xử lý. Sau đó email sẽ được biểu diễn là tập các từ gốc. Ta chỉ xét những từ có
trong cả email thử và trong cây học.
Tính xác suất :
m : tổng số từ trong email
Sau khi tính ta được giá trị của p0 và p1. So sánh 2 giá trị này ta có được kết luận: Nếu
p
0
>p
1
: đây là thư rác,ngược lại là thư thường.
IV. Kết quả và đánh giá
1. Kết quả
Qua thử nghiệm việc phân loại từng email, kết quả chương trình là chính xác với tập dữ

liệu mà ta đã sử dụng.
2. Đánh giá
Để đánh giá độ chính xác của chương trình, ta sử dụng bộ TEST với 1327 email với 421
spam và 906 non-spam.
Hiệu suất nhận dạng thư rác:
Hiệu suất nhận dạng thư thường:
14
Kết quả chương trình:
3. Giao diện chương trình.
Chức năng học
15
Chức năng test
16
4. Đánh giá hiệu năng hệ thống:
Ta thấy hệ thống nhận dạng thư thường khá tốt, tuy nhiên kết quả nhận dạng thư rác còn
chưa tốt lắm.
V. Tài liệu tham khảo
- Bài giảng môn Xử lý ngôn ngữ tự nhiên, cô Lê Thanh Hương
- Các khái niệm tham khảo : www.wikipedia.org
17