Đại học Quốc Gia Thành phố Hồ Chí Minh
Đại học Công Nghệ Thông Tin
TIỂU LUẬN CÔNG NGHỆ TRI THỨC VÀ
ỨNG DỤNG
Đề tài:
Phân lớp văn bản với Naïve Bayes và ứng
dụng trong xây dựng bộ lọc mail rác
GVHD: GS. TSKH. Hoàng Văn Kiếm
HVTH: Trần Cảnh Khánh CH1301093 Tháng 10 năm 2014
MỤC LỤC
CHƯƠNG I KHÁI QUÁT VỀ PHÂN LỚP VĂN BẢN 3
1.1 Khái niệm về phân lớp – phân loại văn bản (Document /categorization
classification) 3
1.1.1 Phân lớp văn bản dựa trên cách tiếp cận hệ chuyên gia 3
1.1.2 Phân lớp văn bản dựa trên cách tiếp cận máy học 3
CHƯƠNG II PHÂN LỚP VĂN BẢN VỚI NAÏVE BAYES 5
2.1 Giới thiệu về phân lớp Naïve Bayes 5
2.2 Mô hình xác suất Naïve Bayes 5
2.2.1 Các mô hình tham số ước lượng và sự kiện 7
2.2.2 Điều chỉnh mẫu 8
2.3 Mô hình Naïve Bayes cho phân lớp văn bản 8
CHƯƠNG III XÂY DỰNG BỘ LỌC THƯ RÁC NAÏVE BAYES 10
3.1 Xử lý 10
3.2 Phương thức thực hiện 10
3.3 Chương trình trình lọc thư rác 12
TÀI LIỆU THAM KHẢO 14
CHƯƠNG I KHÁI QUÁT VỀ PHÂN LỚP VĂN BẢN
1.1 Khái niệm về phân lớp – phân loại văn bản (Document /categorization

chúng.
(Học có giám sát là một kĩ thuật của ngành học máy để xây dựng một hàm (function) từ
dữ liệu huấn luyện. Dữ liệu huấn luyện bao gồm các cặp gồm đối tượng đầu vào (thường
dạng vec-tơ), và đầu ra mong muốn. Đầu ra của một hàm có thể là một giá trị liên tục
(gọi là hồi qui), hay có thể là dự đoán một nhãn phân loại cho một đối tượng đầu vào (gọi
là phân loại). Nhiệm vụ của chương trình học có giám sát là dự đoán giá trị của hàm cho
một đối tượng bất kì là đầu vào hợp lệ, sau khi đã xem xét một số ví dụ huấn luyện (nghĩa
là, các cặp đầu vào và đầu ra tương ứng). Để đạt được điều này, chương trình học phải
tổng quát hóa từ các dữ liệu sẵn có để dự đoán được những tình huống chưa gặp phải
theo một cách "hợp lí")
CHƯƠNG II PHÂN LỚP VĂN BẢN VỚI NAÏVE BAYES
2.1 Giới thiệu về phân lớp Naïve Bayes
Phân lớp Naïve Bayes giả định rằng sự hiện diệ hoặc vắng mặt của một đặc tính là độc
lập với sự hiện diện và vắng mặt của các đặc tính khác, mà được quy định bởi các tham
số phân lớp, ví dụ: một loại trái cây được phân lớp là trái táo nếu nó màu đỏ, tròn, có
đường kính 3 decimet. Một phân lớp Naïve Bayes xem xét các đặc tính này tham gia một
cách độc lập để xác định xác suất mà loại trái cây này là quả táo, bất kể sự hiện diện hay
vắng mặt của các đặc tính khác.
Đối với một số mô hình xác suất, phân lớp Naïve Bayes có thể được huân luyện một cách
hiệu quả trong môi trường học có giám sát. Trong nhiều ứng dụng thực tế, ước lượng
thâm số cho mô hình Naïve Bayes sử dụng phương pháp hợp lý cực đại, nghĩa là khi sử
dụng mô hình Naïve Bayes ta phải chấp nhậ xác suất Bayes. Mặc dù sử dụng các giả định
tương đối đơn giản, nhưng phân lơp Naïve Bayes có thể áp dụng rất tốt trong nhiều
trường hợp phức tạp trong thế giới thực.
Một ưu điểm của mô hình Naïve Bayes là chỉ cần sử dụng khối lượng nhỏ dữ liệu huấn
luyện để ước lượng các tham số cần thiết để phân lớp. Bởi vì các biến độc lập được giả
định, chỉ có sự thay đổi các biến cho mỗi lớp cần được xác định chứ không phải trên toàn
bộ hiệp phương sai.
2.2 Mô hình xác suất Naïve Bayes
Mô hình xác suất cho một phân lớp là mô hình có điều kiện: p (C|F

trị của đặc tính F
i
cho trước, do đó mẫu số có giá trị không đổi, tử số tương đương với mô
hình xác suất (1) có thể viêt lại bằng các sử dụng phương pháp lặp của định nghĩa xác
suất có điều kiện như sau:
p(C,F
1
, ,F
n
) = p(C)p(F
1
|C)p(F
2
|C,F
1
),p(F
3
|C,F
1
,F
2
) p(F
n
|C,F
1
,F
2
, ,F
n-1
) (3)

1
1
)|()(
1
), ,,(
(5)
Trong đó Z là một yếu tố tỷ lệ chỉ phụ thuộc vào F
1
,F
2
,…,F
n
, là một hằng số nếu các biến
đặc tính đã xác định giá trị. Sự phân lớp tương ứng với mô hình này là một hàm phân lớp
được định nghĩa như sau:
∏
=
====
n
i
iicn
cCfFpcCPffclassify
1
1
)|()(maxarg), ,(
(6)
2.2.1 Các mô hình tham số ước lượng và sự kiện
Tất cả các tham số của mô hình (như độ ưu tiên của lớp và sự phân phối xác suất của các
đặc tính) có thể xấp xỉ với tần số tương đối của tập huấn luyện. Đây là những ước tính
khả năng tối đa của xác suất. Độ ưu tiên của một lớp có thể được tính bằng các giả sử các

1
)|(
c
c
v
c
ecvxP
σ
µ
πσ
−
−
==
Một kỹ thuật phổ biến khác để xử lý các giá trị liên tục là sử dụng phương pháp chia
khoảng rời rạc hóa các giá trị của đặc tính, để có được một tập mới của các đặc tính được
phân phối theo mô hình Bernoulli. Tóm lại, phương pháp phân phối là lựa chọn tốt nhất
nếu dữ liệu huấn luyện là nhỏ, hoặc nếu xác định được dữ liệu phân phối chính xác.
Phương pháp rời rạc hóa có xu hướng làm tốt hơn nếu dữ liệu huấn luyện lớn bởi vì nó sẽ
được học để phù hợp với việc phân phối dữ liệu lớn.
2.2.2 Điều chỉnh mẫu
Nếu một lớp và giá trị của đặc tính chưa từng xuất hiện cùng nhau trong dữ liệu huấn
luyện thì tần số dựa vào ước lượng xác suất sẽ bằng 0. Đây là một vấn đề bởi vì nó sẽ xóa
sạch tất các thông tin trong các xác suất khác khi được nhân với nó. Do đó, nó thường
được kết hợp với việc điều chỉnh mẫu nhỏ, gọi là Pseudocount, trong tất cả các ước lượng
xác suất như vậy sẽ không có xác suất nào có giá trị là 0.
2.3 Mô hình Naïve Bayes cho phân lớp văn bản
Xét đến vấn đề phân loại văn bản theo nội dung, văn bản được rút từ lớp các văn bản
được mô hình hóa thành tập các từ trong đó xác suất (không phụ thuộc) của từ thứ i của
một văn bản cho trước xuất hiện trong một văn bản thuộc lớp C có thể được viết như sau
p(w

khả năng. Xác suất thực sự của p(S | D) có thể được tính bằng log(p(S| D) / p(¬S | D))
dựa trên cơ sở p(S | D) + p(¬S | D) = 1. Áp dụng cho tất cả các tỷ lệ, ta có
∑
¬¬
=
¬
i
i
i
Swp
Swp
Sp
Sp
DSp
DSp
)|(
)|(
ln
)(
ln
)|(
)|(
ln
Cuối cùng các văn bản có thể được phân loại như sau: nó được phân loại là spam nếu
0
)|(
)|(
ln
>
¬

, x
2
,…x
n
là giá trị các thuộc tính X
1
, X
2
…X
n
trong không gian vector đặc trưng
X. Mỗi thuộc tính được thể hiện bởi một token đơn. Theo phương pháp đơn giản nhất ta
có thể lập ra một từ điển chứa các token. Sau đó với mỗi token trong email nếu nó xuất
hiện trong từ điển thì giá trị thuộc tính sẽ là 1, ngược lại thì là 0. Tuy nhiên trên thực tế,
tập huấn luyện của ta không thường là một bộ từ điển như vậy. Thay vào đó tập huấn
luyện lúc này sẽ gồm có 2 kho ngữ liệu. Kho ngữ liệu Spam sẽ chứa một list các email đã
được xác định là spam trước đó, và tương tự với kho ngữ liệu Non-spam sẽ chứa các
email hợp lệ.
Như vậy nếu ta vẫn để giá trị các thuộc tính là 0 hoặc 1 thì sẽ rất khó đánh giá được 1
email là spam hay không. Đặc biệt nếu email nhận được là dài, khi đó nếu ta vẫn sử dụng
giá trị thuộc tính là 0 hoặc 1 thì sự xuất hiện của 1 token 100 lần cũng tương đương với
việc xuất hiện chỉ 1 lần.
Để khắc phục vấn đề này giá trị thuộc tính bây giờ ta sẽ thay bằng xác suất spam của
token đó. Xác suất này tương đương với xác suất spam của 1 email chỉ chứa token đó và
là email spam. Việc tính xác suất này thì có nhiều phương pháp. Ta có thể tính dựa trên
số lần xuất hiện của token này trong mỗi kho ngữ liệu học ban đầu. Ví dụ một token w có
số lần xuất hiện trong kho ngữ liệu spam là s và non-spam là n, số email tổng cộng ở kho
spam và non-spam tương ứng là Ns và Nn thì xác suất spam của token w này sẽ là :
P(X=w | C=spam) = (s/N
s

)/((n
s
*s)/N
s
+(n
n
*n)/N
n
))
Còn đối với các token chỉ xuất hiện trong kho ngữ liệu này mà không xuất hiện trong kho
ngữ liệu kia thì không thể kết luận một token chỉ xuât hiện ở kho ngữ liệu spam thì không
bao giờ xuất hiện trong kho ngữ liệu non-spam và ngược lại. Cách thích hợp thì ta sẽ gán
cho chúng một giá trị phù hợp. Với những token chỉ xuất hiện trong kho ngữ liệu spam
thì ta gán xác suất spam cho nó là giá trị N gần với 1 ( chẳng hạn 0,9999) và ngược lại thì
gán xác suất spam là giá trị M gần với 0 ( chẳng hạn 0,0001).
Như vậy ta có công thức tính xác suất spam của token dựa trên số lần xuất hiện và số
email chứa nó là :
P = Max ( M, Min ( N, ((n
s
*s)/N
s
)/((n
s
*s)/N
s
+(n
n
*n)/N
n
) ) )

Vol. 17. 2006.
[3] 2000 Mathematics Subject Classification: 60-04, 65C60 Keywords: Naive Bayesian
classifier, document classification, Web Mining