SEMINAR: CƠ SỞ DỮ LIỆU NÂNG CAO
NGHIÊN CỨU BỘ LỌC THƯ SPAM
TRÊN CƠ SỞ MẠNG BAYES
Học viên: Nguyễn Viết Linh
MS: CH0601038

GIỚI THIỆU

Các bộ lọc thư spam trên cơ sở luật và dấu hiệu
không có khả năng tự tạo ra quyết định và lọc
các spam mới.

Các bộ lọc thư trên cơ sở mạng Bayes cho phép
bộ lọc có thể ‘học’ và có khả năng tự ra quyết
định với các spam mới.

Các bộ phân lớp trên cơ sở máy học cho ta hiệu
quả lọc và phán đoán các thư spam hiệu quả
cao. Với các bộ lọc trên cơ sở mạng Bayes
được huấn luyện tốt, độ chính xác có thể đạt tới
99 %.

GIỚI THIỆU
Trong seminar này chúng ta sẽ đề cập đến các
vấn các đề sau để xây dựng bộ lọc spam kỹ
thuật Bayes:
•
Bộ lọc spam trên cơ sở mạng Bayes đơn giản
•
Bộ lọc spam trên cơ sở mạng Bayes đầy đủ

•
Các phương thức huấn luyện cho các bộ lọc spa
m kỹ thuật Bayes
•
Phân lớp Email và sự phân lớp sai
•
Hiện thực bộ phân lớp spam Bayes

I. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐƠN GIẢN
(Tổng quan về mạng Bayes)

Mạng Bayes là một dạng mô hình đồ thị
theo xác suất không có cung trực tiếp.
Các nút biểu diễn các biến ngẫu nhiên,
các cung biểu diễn mối quan hệ phụ thuộc
giữa các biến.

Nếu các biến là X1, , Xn và “parents(A)”
là các cha của nút A, thì phân bố kết nối
cho X1 tới Xn được biểu diễn dưới dạng
kết quả của phân bố theo xác suất:
P(X1, , Xn) = ∏P(Xi | parents(Xi)) for i = 1 to n.

I. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐƠN GIẢN
(Mô hình mạng Bayes đơn giản)

Một mạng Bayes đơn giản nhất gồm một nút cha
và tất cả các biến khác là con của nút cha. Nếu
biến cha là “Xp”, thì công thức phân bố kết nối
như sau: P(Xp, X1, , Xn) = P(Xp) ∏P(Xi|Xp) for

i = 1 to n.

Bộ phân lớp Naive Bayes là một bộ phân lớp
theo xác suất đơn giản. Lợi ích chính của bộ
phân lớp Naive Bayes là có thể huấn luyện rất
hiệu quả bằng việc học có giám sát.

I. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐƠN GIẢN
(Giải pháp cụ thể cho cho bộ lọc spam Bayes)
Bộ lọc spam trên cơ sở mạng Bayes dựa vào nội
dung của email để phân lớp. Cơ chế hoạt động
của bộ lọc này như sau:
•
Đầu tiên cần token hoá nội dung của email cần
phân lớp. Các token này có thể là các cụm từ,
các cặp từ, nhưng thường sử dụng các từ đơn
để định nghĩa các token.
•
Bước tiếp theo, sử dụng các giá trị trong một từ
điển để tính toán giá trị của mỗi token của
email. Từ điển này chứa các token xuất hiện
trong các thư spam và thư hợp lệ đã được phân
lớp từ trước cùng các giá trị tương ứng.

I. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐƠN GIẢN
(Giải pháp cụ thể cho cho bộ lọc spam Bayes)
•
Sau khi có giá trị của các token trong thư
cần phân lớp, ta sử dụng 15 đến 27 token
có giá trị tốt nhất để tính xác suất cho một

email là thư spam hay hợp lệ.
•
Bước cuối cùng là sửa đổi các giá trị của
các token trong từ điển, điều này đưa ra
khả năng học liên tục với thông tin phản
hồi (feedback) và kết quả phân loại cuối
cùng được tạo ra.

I. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐƠN GIẢN
(Giải pháp cụ thể cho cho bộ lọc spam Bayes)
Một số tính toán cho giải pháp này:
•
N1 là số thư spam mà một từ xuất hiện, N2 là số
thư hợp lệ mà một từ xuất hiện.
•
ALL (tổng số tất cả các e-mail) = SPAM + HAM
(số thư hợp lệ + số thư spam).
•
Gọi một từ là “từ so trùng”, nếu tồn tại cả trong
thư và trong từ điển token.
•
P ( “các từ so trùng” | “thư là spam” ) = ∏cho tất cả từ
được so trùng (giá trị N1 của từ hiện tại / SPAM ).

I. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐƠN GIẢN
(Giải pháp cụ thể cho cho bộ lọc spam Bayes)
•
P ( “các từ so trùng” | “thư là hợp lệ” ) = ∏cho tất cả
từ được so trùng(giá trị N2 của từ hiện tại / HAM ).
•

P ( “thư là spam” ) = SPAM / ALL
•
P ( “thư là hợp lệ” ) = HAM / ALL
•
P ( “thư là spam” | “các từ so trùng” ) = P ( “thư
là spam” ) * P (“các từ so trùng” | “thư là spam” )
•
P ( “thư là hợp lệ” | “các từ so trùng” ) = P ( “thư
là hợp lệ” ) * P (“các từ so trùng” | “thư là hợp
lệ”)
•
Kết quả cuối cùng: P ( “thư là spam” | “các từ
so trùng” ) / P ( “thư là hợp lệ” | “các từ so trùng”
)

I. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐƠN GIẢN
(Giải pháp cụ thể cho cho bộ lọc spam Bayes)
Cấu trúc từ điển token:
•
N1 là số thư spam mà một từ xuất hiện.
•
N2 là số thư hợp lệ mà một từ xuất hiện.
•
W/S (word has existed/spam) là số thư
spam có từ so trùng hiện tại chia cho số
tất cả các thư spam.
•
W/H (word has existed/ham) là số thư hợp
lệ có từ so trùng hiện tại chia cho số tất cả
các thư hợp lệ.


I. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐƠN GIẢN
(Một ví dụ cụ thể)

Giả sử cơ sở dữ liệu có 240 spam và 814
thư hợp lệ được lưu (tổng cộng là 1054
thư). Như vậy tỷ lệ thư spam là 23%, thư
hợp lệ là 77%.

Thư nhận được cần phân lớp như sau:

Date: 19.05.1908 11:14
From: KathrineWitt <>
Subject: All products for your health!
/>Suffering from pain, depression or heartburn?We'll help you!
All verified dr@gs collected at one LICENSED online store! Great choice of wonderful meds to give
you long-awaited relief! Operative support, fast shipping, secure p@yment processing and complete
confidentiality!
The store is VERIFIED BY BBB and APPROVED BY VISA!
/>

I. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐƠN GIẢN
(Một ví dụ cụ thể)

Bộ lọc chia thư thành các token, các giá trị của
các token có trong cơ sở dữ liệu như sau:

I. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐƠN GIẢN
(Một ví dụ cụ thể)


Tính xác suất có thể P( “thư là spam” | “các từ
so trùng” ) = P ( “thư là spam” ) * P (“các từ
so trùng” | “thư spam” ) = 23% * ∏tất cả các từ so
trùng(W/S).

Tính xác suất có thể P ( “thư hợp lệ” | “các từ
so trùng” ) = P ( “thư là hợp lệ” ) * P (“các từ
so trùng” | “thư là hợp lệ” ) = 77% * ∏tất cả các từ so
trùng(W/H).

Kết quả cuối cùng là thương số của hai xác suất
có thể được tính toán ở trên.Nếu kết quả sẽ lớn
hơn 1 thì thư giống spam hơn và kết quả nằm
giữa zero và 1 thì thư hợp lệ hơn.

I. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐƠN GIẢN
(Biểu đồ bộ lọc)

1a: Thư nhận được.

1b: Thư này được sử dụng như một văn bản thuần tuý
(bao gồm thân và header).

1c: Thư được phân đoạn thành các token (token hoá).

1d: Giá trị lưu trữ được tìm thấy từ cơ sở dữ liệu 1d.

1e: Thực hiện tính toán các khả năng có thể.

1f: Kết quả được thông báo cho người sử dụng, đồng

thời các giá trị lưu trữ trong cơ sở dữ liệu được cập nhật
(1d).

1g: Thông tin phản hồi của người sử dụng trong trường
hợp phân lớp nhầm, cơ sở dữ liệu được cập nhật.

Phần tính toán được chi tiết trong Hình 2.

I. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐƠN GIẢN
(Biểu đồ bộ lọc)

2a: Các token có được từ thư đến.

2b: Các token nhận được các giá trị tương ứng
của chúng lưu trữ trong cơ sở dữ liệu 2d.

2c: Chỉ có các token thích đáng nhất được sử
dụng.

2e: Tính toán được thực hiện bằng cách sử
dụng các giá trị của các token thích đáng nhất
và các dữ liệu tĩnh khác.

2f: quyết định cuối cùng được thực hiện, và cơ
sở dữ liệu (2d) được cập nhật theo kết quả phân
loại.

I. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐƠN GIẢN
(Biểu đồ bộ lọc)


II. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐẦY ĐỦ

Một mạng Bayes đầy đủ là một đa
mạng bao gồm một tập hợp các
mạng Bayes, mỗi mạng Bayes tương
ứng với một giá trị c của biến lớp C.

Một đa mạng cho một bộ phân lớp
Bayes đầy đủ FBC (Full Bayesian
Network Classifier) là một tập các
FBC tương ứng.

II. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐẦY ĐỦ
(Cấu trúc của bộ phân lớp Bayes đầy đủ FBC )

Cho trước một tập huấn luyện S, chia S thành các
tập con |C|, mỗi Sc của nó tương ứng với giá trị c
của lớp, và sau đó xây dựng một FBC cho Sc.

Nghiên cứu cấu trúc của một mạng Bayes hoàn
chỉnh (FBN) có nghĩa là nghiên cứu thứ tự của các
biến và sau đó thêm các cung từ một biến tới tất cả
các biến khác được xếp sau nó.

Phương pháp này xếp loại một biến trên cơ sở ảnh
hưởng toàn bộ của nó lên các biến khác. Sự ảnh
hưởng (sự phụ thuộc) giữa hai biến có thể được đo
bởi thông tin có cùng mối quan hệ nào đó với nhau
và được định nghĩa như sau:


II. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐẦY ĐỦ
(Cấu trúc của bộ phân lớp Bayes đầy đủ FBC )

Với x và y là các giá trị của các biến X và
Y theo thứ tự. Chú ý rằng, vì chúng ta tính
toán thông tin có cùng mối quan hệ với
nhau trong mỗi tập con Sc của tập huấn
luyện, M(X; Y) thực sự là thông tin có
cùng mối quan hệ theo điều kiện M(X; Y |
c).

II. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐẦY ĐỦ
(Cấu trúc của bộ phân lớp Bayes đầy đủ FBC )

Trong thực tế, có thể sự phụ thuộc giữa hai biến
được đo bởi phương trình (1) là nguyên nhân do
nhiễu do đó sự phụ thuộc không đáng tin cậy và
sẽ không được tính đến. Như vậy chúng ta cần
một ngưỡng để xem xét sự phụ thuộc giữa hai
biến có đáng tin cậy không.

Một cách để định nghĩa ngưỡng dựa trên cơ sở
nguyên tắc độ dài mô tả tối thiểu (Minimum
Description Length - MDL).

II. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐẦY ĐỦ
(Cấu trúc của bộ phân lớp Bayes đầy đủ FBC )

Friedman và Yakhini (1996) chỉ ra rằng lỗi
entropy giao nhau trung bình tương ứng

một cách tiệm cận với logN/2N, với N là
kích thước của dữ liệu huấn luyện. Chúng
ta chấp nhận kết quả của họ cho định
nghĩa ngưỡng để lọc ra các phụ thuộc
không đáng tin cậy như sau:

II. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐẦY ĐỦ
(Cấu trúc của bộ phân lớp Bayes đầy đủ FBC )

Với Tij = |Xi|*|Xj|, |Xi| là số các giá trị có thể của Xi, và |Xj| tương
ứng với Xj. Giả sử chúng ta sử dụng dạng sơ đẳng nhất khi biểu
diễn cho các bảng xác suất theo điều kiện (CPT), nếu Xi và Xj độc
lập, thì kích thước toàn bộ của hai CPT cho Xi và Xj là |Xi| + |Xj|.
Nếu chúng ta biểu diễn sự phụ thuộc giữa Xi và Xj, thì kích thước
toàn bộ của hai CPT là |Xi| * |Xj | + |Xi| (giả sử Xi là cha của Xj).

Như vậy, Tij biểu diễn sự tăng của kích thước cho biểu diễn phụ
thuộc giữa Xi và Xj. Trong thực thi của chúng ta, sự phụ thuộc giữa
Xi và Xj chỉ được tính đến nếu M(Xi;Xj) > φ(Xi;Xj). Ảnh hưởng toàn
bộ của một biến Xi lên biến khác được biểu thị bởi W(Xi) được định
nghĩa như sau:

II. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐẦY ĐỦ
(Cấu trúc của bộ phân lớp Bayes đầy đủ FBC )
Giải thuật học trên cơ sở W(Xi) như sau:
Algorithm FBC-Structure(S, X)
Input : Một tập S các mẫu được gắn nhãn,một tập X các biến.
Output : Một mạng bayes đầy đủ B.
1. B = rỗng.
2. Chia dữ liệu huấn luyện S thành các tập con |C| bởi giá trị c của lớp.

3. Với mỗi tập dữ liệu huấn luyện Sc:
- Tính thông tin có cùng mối quan hệ M(Xi;Xj) và sự bất lợi của cấu trúc φ(Xi;Xj)giữa
mỗi cặp biến Xi và Xj trên cơ sở phương trình 1 và phương trình 2.
- Tính W(Xi)cho mỗi biến Xi trên cơ sở phương trình 3.
- Với tất cả các biến Xi trong X
+ Thêm tất cả các biến Xj với W(Xj) > W(Xi)vào tập cha Πxi của Xi.
+ Thêm cung từ tất cả các biến Xj vào Πxi của Xi.
- Thêm mạng kết quả Bc vào B.
4. Trả về B.

II. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐẦY ĐỦ
(Tính toán bảng xác suất có điều kiện CPT )
o
Tiếp theo, một cây CPT sẽ được xác định cho mỗi biến
Xi, giải thuật học dạng cây quyết định truyền thống được
áp dụng để xác định các cây CPT, độ phức tạp về thời
gian thông thường sẽ là O(n
2
. N). Chú ý rằng cây quyết
định sẽ được xác định cho mỗi biến. Như vậy giải thuật
học FBC kết quả sẽ có độ phức tạp là O(n
3
. N).
o
Ta có giải thuật học dạng cây quyết định nhanh cho
CPT. Trong tiến trình tăng trưởng của cây, tất cả các
biến Xj trong ΠXi được lưu dưới dạng thông tin có cùng
mối quan hệ M(Xi;Xj) trên toàn bộ dữ liệu huấn luyện
xác định thứ tự cố định của các biến, hãy gỡ bỏ biến Xj
với thông tin có cùng mối quan hệ cao nhất khỏi ΠXi và

tính toán thông tin có cùng mối quan hệ cục bộ MS(Xi;
Xj) trên dữ liệu huấn luyện hiện tại S.

II. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐẦY ĐỦ
(Tính toán bảng xác suất có điều kiện CPT )
o
Nếu nó lớn hơn ngưỡng cục bộ φ
s
(Xi;Xj ),
thì Xj được sử dụng là gốc, và chia dữ liệu
huấn luyện hiện tại S theo các giá trị của
Xj và lặp lại tiến trình này cho mỗi nhánh
(tập con). Ngoài ra, hãy thử một biến
khác. Điểm then chốt ở đây là, với mỗi
biến chúng ta tính thông tin có cùng mối
quan hệ cục bộ và ngưỡng cục bộ chỉ một
lần.