HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG

LÊ THANH TRÀ
ĐỀ TÀI:
NGHIÊN CỨU CÁC PHƯƠNG PHÁP
PHÂN LOẠI VĂN BẢN VÀ ỨNG DỤNG VÀO
PHÂN LOẠI THƯ ĐIỆN TỬ
Chuyên ngành: Khoa học máy tính
Mã số: 60.48.01
TÓM TẮT LUẬN VĂN THẠC SĨ
HÀ NỘI - 2013
Luận văn được hoàn thành tại:
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
Người hướng dẫn khoa học: PGS.TS. NGUYỄN BÁ TƯỜNG
Phản biện 1: ……………………………………
Phản biện 2: ……………………………………
Luận văn sẽ được bảo vệ trước Hội đồng chấm luận
văn thạc sĩ tại Học viện Công nghệ Bưu chính Viễn
thông
Vào lúc: giờ ngày tháng năm…
Có thể tìm hiểu luận văn tại:
- Thư viện của Học viện Công nghệ Bưu chính Viễn thông
MỞ ĐẦU
Phân loại văn bản là một vấn đề quan trọng trong lĩnh
vực xử lý ngôn ngữ. Nhiệm vụ của bài toán này là gán các tài
liệu văn bản vào nhóm các chủ đề cho trước. Đây là một bài
toán rất thường gặp trong thực tế.
Ngày nay, Internet mở ra nhiều kênh liên lạc, nhiều dịch
vụ mới cho người sử dụng, một trong những dịch vụ mà
Internet mang lại đó là dịch vụ thư điện tử(email), đó là
phương tiện giao tiếp rất đơn giản, tiện lợi, rẻ và hiệu quả.

trình này đều có ảnh hưởng quan trọng đến hiệu suất lọc
spam, giới thiệu và triển khai một bộ lọc thư điện tử spam
dựa trên kỹ thuật Naive Bayes.
Chương 1 – MỘT SỐ PHƯƠNG PHÁP PHÂN LOẠI
VĂN BẢN
Phân loại văn bản là một vấn đề quan trọng trong lĩnh
vực xử lý ngôn ngữ. Để giải bài toán này đã có rất nhiều
phương pháp được đưa ra như: thuật toán Naive Bayes, K-
NN (K-Nearest-Neighbor), cây quyết định (Decision Tree),
mạng Neuron nhân tạo (Artificial Neural Network) và SVM
(Support Vector Machine). Mỗi phương pháp đều cho kết
quả khác nhau cho bài toán này, trong chương này chúng ta
sẽ nghiên cứu một số phương pháp nói trên.
1.1 Bài toán phân loại văn bản
1.1.1 Giới thiệu
1.1.2 Phát biểu bài toán
Bài toán phân loại văn bản có thể được phát biểu như sau :
Cho trước một tập văn bản D={d
1
,d
2
,…,d
n
} và tập chủ đề
được định nghĩa C={c
1
,c
2
,…,c
n

lớp, trong đó tập dữ liệu mẫu đưa vào là các thư điện tử gồm
các thư rác(spam) và các thư hợp lệ(Legitimate), các văn bản
cần phân lớp là các Email gửi đến client. Kết quả đầu ra của
quá trình này là hai lớp văn bản: Spam(thư rác) và
Legitimate (thư hợp lệ).
1.6 Kết luận chương
Chương 2 – NHỮNG VẤN ĐỀ VỀ THƯ ĐIỆN TỬ
SPAM
2.1 Định nghĩa spam
Hầu hết các spam đều có thể được xem là các email
không mong muốn, nhưng không phải tất cả các thư
không mong muốn đều là spam. Một thuật ngữ khác để
chỉ spam, đó là các email thương mại không yêu cầu.
Spam cũng có thể được định nghĩa là các thư tạp nham
(junk mail).
2.2 Các kiểu thư spam
2.2.1 Các đặc điểm của thư spam
Spam có các đặc điểm về ngôn ngữ, thời gian
2.2.2 Một số loại thư spam
2.3 Các phương thức đơn giản để loại bỏ thư spam
2.3.1 Sử dụng các từ khóa
2.3.2 So sánh mẫu, danh sách whitelist và danh sách
blacklist
2.3.3 Kỹ thuật lọc cộng tác (Collaborative filtering)
2.3.4 Đo sự giao thoa email (E-mail interferometry)
2.3.5 Lọc ở mức mạng
2.3.6 Kỹ thuật nhân viên giả mạo (Fake worker)
2.3.7 Các bộ lọc trên cơ sở luật
2.3.8 Sử dụng chung danh sách blacklist các dấu hiệu
spam

thức của riêng nó. Mặc dù các spammer luôn nghĩ ra những ý
tưởng mới để vượt qua các bộ lọc, nhưng với bộ lọc Bayes
được huấn luyện tốt, thì sự chính xác của các bộ lọc có thể
đạt tới 99%.
3.1 Mạng Bayes
3.1.1 Tổng quát về mạng Bayes
3.1.2 Mô hình Naive Bayes
Naive Bayes là một mạng Bayes đơn giản nhất trong
đó một nút cha được chứa trong mạng 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 trong trường hợp đó như sau:
P(Xp,X1, ,Xn)=P(Xp)

)|( XpXiP
fori= 1 to n (3.1)
3.2 Bộ lọc spam trên cơ sở mạng 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ác giai đoạn chính của giải pháp
trên cơ sở mạng Bayes như sau:
- Đầu tiên cần token hoá nội dung của email, nghĩa là
tách nó thành các phần nhỏ để sử dụng trong xử lý.
- Bước tiếp theo, giá trị của mỗi token được xác định
bằng cách tìm kiếm trong một bảng cập nhật (từ điểm token).
Các giá trị của các token có liên quan có khoảng cách
lớn nhất từ giá trị trung tính (neutral) và như vậy chúng sẽ
gần với một mặt nạ các thư spam hoặc thư 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ả nhị phân cuối cùng
được tạo ra.

Hình 3.1: Biểu đồ bộ lọc spam trên cơ sở Bayes
3.5 Các phương thức huấn luyện cho bộ lọc dựa trên kỹ
thuật Bayes
3.5.1 Tổng quan
3.5.2 Các phương thức huấn luyện khác nhau
3.6 Bộ lọc spam dựa vào kỹ thuật Bayes của Paul
Graham
3.6.1 Giải thuật
3.6.2 Phân lớp văn bản Bayes
Phân lớp thống kê dựa trên một luật đơn giản như sau:
Nếu có nhiều token tồi trong thư spam hơn trong thư tốt thì
nếu chúng ta tìm thấy thêm các token spam trong một số thư,
thì nó sẽ được xem là thư spam.
3.7 Một số cải tiến cho bộ lọc spam trên cơ sở giải thuật
Bayes
3.7.1 Cải tiến bộ lọc spam Bayes của PaulGraham
Có hai cải tiến được thêm vào:
- Để loại bỏ được việc phân lớp nhầm các thư tốt, tần
số thư tốt được nhân đôi khi ta tính xác suất của thư spam.
- Khi một token chỉ nằm trong tập cơ sở dữ liệu spam
có sẵn, thì chúng ta có thể thiết lập các xác suất tăng lên nếu
có nhiều token ấy. ví dụ: 0.9 cho các tần số nhỏ, 0.99 cho các
tần số lớn hơn 10.
3.7.2 Cải tiến bộ lọc spam Bayes sử dụng khoảng cách
khác biệt giữa hai chuỗi (Giải thuật SEDA)
 Giải thuật khoảng cách khác biệt chuỗi String-
Edit Distance (SEDA)
Giải thuật này cung cấp một tiêu chuẩn về khoảng
cách giữa các chuỗi. Khoảng cách này được định nghĩa là số
các thao tác nhỏ nhất được yêu cầu để đổi chuỗi nguồn thành

Trong chương này chúng ta đã tìm hiểu về mạng Bayes, các
bước xây dựng bộ lọc trên cơ sở mạng Bayes. Đồng thời
cũng tìm hiểu về các cải tiến của PaulGraham, giải thuật
SEDA. Cả hai phương pháp đó đã giúp nâng cao chất lượng
của bộ lọc mạng Bayes, tuy nhiên cả hai giải pháp đó vẫn có
hạn chế nhất định.
Chương 4 – XÂY DỰNG BỘ LỌC CẢI TIẾN VÀ THỬ
NGHIỆM
4.1 Xây dựng bộ lọc cải tiến
- Xây dựng danh sách xác suất là spam của tất cả các
token trong quá trình huấn luyện theo kỹ thuật của
PaulGraham.
- Trong phần phân lớp thư mới, với tất cả các token,
nếu token của thư mới có trong cơ sở tri thức, thì ta đưa
token này cùng xác suất có thể là spam của nó vào danh sách
T.
- Nếu token t không có trong cơ sở tri thức, ta tính
khoảng cách khác biệt chuỗi của nó với tất cả các token của
cơ sở tri thức. Chọn ra một token trong cơ sở tri thức có
khoảng cách khác biệt chuỗi (so với chuỗi t) nhỏ nhất và nhỏ
hơn hoặc bằng ngưỡng α. Nếu tìm thấy token này thì thêm
nó cùng xác suất là spam vào danh sách T, nếu không thì từ
này thực sự là từ mới.
- Ta có thể xây dựng một từ điển các từ chuẩn hoá bắt
nguồn từ các từ trong cơ sở tri thức và bổ sung thêm trong
quá trình từ điển này trong quá trình phân lớp. Như vậy việc
tính toán khoảng cách khác biệt chuỗi sẽ không phải duyệt
trên tòan bộ cơ sở tri thức.
- Chọn ra danh sách 15 token điển hình trong danh
sách T (có khoảng cách tính từ giá trị 0,5). Tính xác suất là

Bayes của
Paulgraham
1478
1522
Giải thuật Bayes –
SEDA
1517
1483
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
Các bộ phân loại thư điện tử ngày nay áp dụng các
giải thuật máy học cho ta hiệu quả lọc cao, đặc biệt là bộ lọc
thư spam áp dụng giải thuật Naive Bayes cho ta hiệu suất lọc
đến 99% và được áp dụng cho những nhà cung cấp dịch vụ
thư điện tử lớn như Yahoo, Hotmail…Các bộ lọc thư spam
trên desktop thương mại ngày nay cũng áp dụng kỹ thuật này
với một số cải tiến và kết hợp nhỏ. Việc áp dụng các giải
thuật máy học vào nhiệm vụ lọc spam làm cho bộ phân lớp
có khả năng thích nghi với các spam thế hệ mới bằng việc
cập nhật tri thức cho cơ sở tri thức của bộ lọc.
Trong khuôn khổ luận văn thạc sỹ CNTT, luận văn đã
nêu bật được các phương pháp phân loại văn bản, các vấn đề
liên quan đến thư spam, các giải pháp lọc thư spam dựa trên
các giải thuật máy học như kỹ thuật Supported Vector
Machines (SVM), k-Nearest-Neighbor (kNN), Neural
Networks (NNet) và Naive Bayesian (NB), các vấn đề liên
quan đến hiệu quả của bộ lọc cũng như việc kết hợp các bộ
lọc nhằm nâng cao hiệu suất lọc. Các bước triển khai bộ lọc
spam trên cơ sở kỹ thuật Bayes được thực hiện bao gồm tiền
xử lý dữ liệu, huấn luyện và các phương thức huấn luyện,
tính toán cho các bộ phân lớp. Một số cải tiến áp dụng cho

người sử dụng có. Bất cứ lúc nào chúng ta nhận được thư từ
một miền địa chỉ trong danh sách đen hoặc địa chỉ trong
danh sách trắng, thì chúng ta biết chắc rằng nó là thư spam
hoặc thư tốt theo độ ưu tiên định sẵn. Do đó chúng ta có thể
trích ra các thông tin tốt để tăng cường cho cơ sở tri thức của
bộ lọc.
- Tổ chức các thư đến theo ba thể loại khác nhau như
Spam, Personal, Business, thay vì chỉ hai. Như vậy mục đích
của bộ lọc thư trở nên phổ biến hơn.
- Xây dựng tập cơ sở dữ liệu thư spam tiếng Việt,
nghiên cứu các từ, cụm từ spam trong thư tiếng Việt.
- Nghiên cứu các bộ lọc spam diện rộng sử dụng cho
các tổ chức xã hội.