ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
NGUYỄN THỊ HỒNG HẬU
TÌM HIỂU PHƯƠNG PHÁP HỌC TÍCH CỰC VÀ
ỨNG DỤNG CHO BÀI TOÁN LỌC THƯ RÁC

LUẬN VĂN THẠC SĨ
Hà Nội - 2011
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN THỊ HỒNG HẬU

TÌM HIỂU PHƯƠNG PHÁP HỌC TÍCH CỰC VÀ
ỨNG DỤNG CHO BÀI TOÁN LỌC THƯ RÁC
Ngành: Công nghệ thông tin
Chuyên ngành: H
ệ thống thông tin
Mã s
ố: 60 48 05
LUẬN VĂN THẠC SĨ
NGƯỜI HƯỚ
NG DẪN KHOA HỌC: TS. NGUYỄN TRÍ THÀNH
Hà N
ội - 2011
1

MỤC LỤC
DANH SÁCH HÌNH VẼ 3
DANH SÁCH CÁC BẢNG BIỂU 4
CHƯƠNG I: GIỚI THIỆU 5

3.2.3 Version space 30
3.2.4 Học tích cực với SVM 33
3.3 Kết luận 39
CHƯƠNG 4. ỨNG DỤNG HỌC TÍCH CỰC CHO BÀI TOÁN LỌC
THƯ RÁC 40
4.1 Giới thiệu 40
4.2 Học tích cực trong bài toán lọc thư rác 41
4.3 Thử nghiệm và kết quả 43
4.3.1. Cài đặt chương trình thử nghiệm 43
4.3.2. Thu thập và biểu diễn dữ liệu 45
4.3.3. Xây dựng chương trình biểu diễn và tiền xừ lý dữ liệu 48
4.3.4. Kết quả thử nghiệm 51
4.4 Kết luận 57
KẾT LUẬN 58
TÀI LIỆU THAM KHẢO 60 3
DANH SÁCH HÌNH VẼ
Hình 2.1 Lược đồ chung cho bộ học thụ động
Hình 2.2 Lược đồ chung cho bộ học tích cực
Hình 2.3 Lược đồ tổng thể của học tích cực
Hình 3.1 Thuật toán perceptron chuẩn
Hình 3.2 Thuật toán cải tiến percepron chuẩn
Hình 3.3 Quy tắc học tích cực là truy vấn các nhãn cho các điểm x trong L
Hình 3.4. Phiên bản tích cực của Perceptron đã chỉnh sửa.
Hình 3.5 (a) Máy hỗ trợ vector tuyến tính đơn giản.

Bảng 4.2 Từ điển và chỉ số cho dữ liệu trong bảng 4.1
Bảng 4.3 Biểu diễn vector cho dữ liệu trong bảng 4.1
Bảng 4.4 Kết quả chạy qua 20 lần truy vấn của các thuật toán
5
CHƯƠNG I: GIỚI THIỆU
1.1 Giới thiệu đề tài
1.1.1 Lý do chọn đề tài
Ngày nay thư điện tử (email) đã trở thành một công cụ đắc lực phục vụ
cho nhu cầu trao đổi thông tin của các cơ quan tổ chức, doanh nghiệp cũng
như mỗi cá nhân. Email giúp con người có thể kết nối mọi nơi, mọi lúc với
công việc và cuộc sống cá nhân. Tuy nhiện thư điển tử cũng đang bị lợi dụng
để phát tán thư rác (spam) lây lan virus máy tính và lừa đảo trực tuyến, gây
thiệt hại lớn cho người sử dụng.
Thư rác 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ế.
Thư rác là một trong những thách thức lớn nhất hiện nay mà khách
hàng và các nhà cung cấp dịch vụ phải đối phó. Spam đã trở thành một hình

học thư rác dựa vào các phương pháp học tích cực (bộ lọc tích cực). Nội dung
nghiên cứu bao gồm cả thử nghiệm trên dữ liệu thực làm rõ khả năng lọc thư
của các bộ lọc tích cực, so sánh hiệu quả của các phương pháp được áp dụng
trong bộ lọc.
1.1.2 Mục tiêu của đề tài
Để loại bỏ thư rác, các nhà cung cấp dịch vụ thư điện tử đã tích hợp
nhiều chương trình lọc thư rác vào dịch vụ thư điện tử. Các chương trình lọc
thư rác chủ yếu dựa vào các phương pháp học máy thông qua một bộ học.
Tuy nhiên dựa vào thực tế: thư điện tử là một dịch vụ online, các thư điện tử
được cập nhật thay đổi theo thời gian và có sự tương tác của người sử dụng
hòm thư với hệ thống vì vậy đề tài đã tập trung vào nghiên cứu bộ học tích
cực và áp dụng cho bài toán lọc thư rác.
7
Trên cơ sở xác định loại hình nghiên cứu của đề tài là nghiên cứu lý
thuyết và ứng dụng thực nghiệm, mục tiêu của đề tài là tìm hiểu về phương
pháp học tích cực và tìm giải giải pháp cho bài toán lọc thư rác, chọn mô hình
thích hợp để áp dụng vào bài toán lọc thư rác với các tiêu chí:
- Lọc thư rác nhanh, phát hiện chính xác thư rác (spam mail).
- Tận dụng được khả năng tương tác với người sử dụng dịch vụ
mail, sự phân loại mail của người dùng để tăng thêm lượng mail đã gán nhãn
cũng như chất lượng của dữ liệu gán nhãn.
- Có khả năng thích nghi với các biến thể của thư rác, chủ động lọc
loại ra các thư rác ngày một hoạt động tinh vi hơn.
Giống như trong lĩnh vực phòng chống virus máy tính, hacker luôn tìm
cách để chống lại các chương trình diệt virus, thì trong chương trình lọc thư
rác, những người gửi thư rác luôn tìm cách để tránh được bộ lọc thư rác một
cách hữu hiệu. Vì vậy mà thư rác luôn luôn được biến đổi, cải tiến hơn do

dữ liệu và chạy thực nghiệm dữ liệu trên các công cụ đã cài đặt được. Phân
tích đánh giá và nhận xét kết quả thực nghiệm
Giai đoạn 3 – Tổng kết: Khái quát hóa và rút ra kết luận chung cho đề
tài. Viết báo cáo, công bố kết quả nghiên cứu trong đề tài.
1.2 Cấu trúc của luận văn
Luận văn gồm bốn chương: Chương 1 dẫn nhập và giới thiệu chung về
luận văn, lý do chọn đề tài, mục tiêu của đề tài và ý nghĩa của đề tài. Chương
này cũng trình bày các giai đoạn thực hiện luận văn và cấu trúc của luận văn.
Chương 2: trình bày các cơ sở lý thuyết phục vụ cho bài toán lọc mai.
Cụ thể chương 2 sẽ giới thiệu về phương pháp học tích cực. Đưa ra mô hình
học tích cực, so sánh giữa hai mô hình học thụ động và học tích cực. Từ đó
nêu ra được ưu điểm của học tích cực và các miền ứng dụng.
Chương 3: sẽ trình bày về các mô hình học tích cực. Đầu tiên, Chương
3 trình bày cơ sở lý thuyết của phương pháp học tích cực dựa vào perceptron
sử dụng cải tiến bước cập nhật. Cuối Chương 3 trình bày về học tích cực với
SVM, giới thiệu ba phương pháp truy vấn trong bộ học SVM: Simple Margin,
MaxMin Margin và Ratio Margin.
Chương 4: Giới thiệu bài toán lọc thư rác, phương pháp học tích cực
trong bài toán lọc thư rác. Chương 4 sử dụng phương pháp học tích cực dựa
vào Perceptron và SVM active vào xây dựng mô hình cho bài toán lọc thư rác.
9
Phần cuối chương 4: Cài đặt các tool thực nghiệm và xây dựng chương
trình xử lý dữ liệu thu thập được về dạng dữ liệu đầu vào cho các tool thực
nghiệm. Phân tích, đánh giá và nhận xét kết quả thực nghiệm.
Phần Kết luận: tổng kết lại những kết quả đã thực hiện được trong luận
văn và đưa ra phương hướng phát triển luận văn trong tương lai.


động. Học không giám sát bao gồm bài toán phân cụm (Ở đây chúng ta sẽ cố
tìm nhóm dữ liệu tương tự nhau) và xây dựng mô hình (chúng ta cố gắng xây
dựng một mô hình miền từ một tập dữ liệu).
Tất cả các bài toán học giám sát và không giám sát, đầu tiên là thu thập
11
đầy đủ lượng dữ liệu sao cho được đánh mẫu tự động từ sự phân bố mật độ cơ
bản và sau đó chúng ta quy vào một lớp hay một mô hình. Phương pháp này
được gọi là học thụ động. Bộ học thụ động nhận dữ liệu một cách ngẫu nhiên
từ thế giới (hình 2.1) và sau đó đưa ra mô hình để phân lớp.
Thông thường những bài toán mất nhiều thời gian và chi phí trong các
ứng dụng là thu thập dữ liệu. Trong một số trường hợp, chúng ta có giới hạn
các tài nguyên cho việc thu thập dữ liệu. Do đó, rất là quan trọng khi xác định
cách để chúng ta có thể sử dụng những tài nguyên này càng nhiều càng tốt.
Hầu như trong tất cả các trường hợp chúng ta đều cho rằng thu thập các thể
hiện dữ liệu một cách ngẫu nhiên là độc lập và phân bố tương tự nhau. Tuy
nhiên, trong một số trường hợp chúng ta có thể có cách hướng dẫn quá trình
lấy mẫu. Ví dụ, trong bài toán phân lớp tài liệu, thường rất dễ thu thập một
lượng lớn các tài liệu chưa gán nhãn. Thay vì lựa chọn tài liệu một cách ngẫu
nhiên để gán nhãn cho tập huấn luyện, chúng ta có quyền lựa chọn (yêu cầu)
cẩn thận một số tài liệu để gán nhãn. Trong bài toán ước lượng tham số và
phát hiện cấu trúc, giả sử chúng ta nghiên cứu bệnh ung thư phổi trong ngành
y:
 Chúng ta có một danh sách sơ bộ ban đầu về tuổi và sở thích hút thuốc
của những người có khả năng mắc bệnh để chúng ta có quyền lựa chọn
hướng kiểm tra thêm.
 Chúng ta có khả năng đưa ra chỉ với một số người bản kiểm tra chi tiết.
Thay vì chọn ngẫu nhiên một số người để kiểm tra thì ta đặt ra yêu cầu với

người sử dụng hay chuyên gia gán nhãn. Bằng cách này, bộ học tích cực
hướng đến việc đạt được độ chính xác cao trong việc sử dụng dữ liệu gán
nhãn càng ít càng tốt, do đó sẽ giảm thiểu được chí phí trong việc thu thập dữ
liệu có nhãn. Học tích cực được coi là một hướng tiếp cận có mục đích tốt
trong các bài toán học máy hiện đại mà dữ liệu có thể bị dư thừa nhưng các
nhãn thì khan hiếm hoặc là tốn chi phí mới có được.
Học tích cực là một trong những phương pháp học giám sát [7] tạo ra
những dữ liệu được gán nhãn với sự giúp đỡ của con người trong những vòng
lặp có phản hồi [5]. Bộ học tập trung vào việc huấn luyện sử dụng một lượng
nhỏ dữ liệu đã gán nhãn và làm giảm số các nhãn mà người sử dụng có để
Thế giới
Bộ học thụ
động
Mô hình hoặc
bộ phân lớp
Dữ liệu Dữ liệu ra
Thế giới
Bộ học tích
cực
Mô hình /Bộ
phân lớp
Dữ liệu đã gán
nhãn/chưa gán
nhãn
Truy vấn
Phản hồi
Dữ liệu
ra
13


câu trả lời cho câu truy vấn đó:
14








 (2.1)
Nếu sử dụng định nghĩa này trong thuật toán học tích cực thì có thể
chọn các câu truy vấn sao cho độ tổn thất kỳ vọng của mô hình là thấp nhất.
Dựa vào nhưng phân tích ở trên Tong [36] đã đưa ra lược đồ tổng thể của học
tích cực như trong hình 2.3
For i:=1 to totalQueries
ForEach q in potentialQueries
Evaluate
Loss(q)

EndForEach
Ask truy vấn q sao cho Loss(q) là thất nhất
Update cập nhật mô hình M với truy vấn q và phản hồi x
EndFor
Return mô hình

Hình 2.3 Lược đồ tổng thể của học tích cực [36]

Trong kịch bản ‘pool-based sampling’, đầu tiên bộ học lấy tất cả các
mẫu và xếp hạng chúng tăng dần dựa trên dự đoán của bộ phân lớp. Sau đó,
bộ học sẽ chọn k mẫu đầu tiên của danh sách xếp hạng trong mỗi lần lặp và
đưa chúng cho từng người sử dụng một để ghi nhãn.
Trong kịch bản ‘pool-based sampling’, dữ liệu chưa gán nhãn là cố
định và không thay đổi; trong khi kịch bản ‘stream-based scenario’ là một
phiên bản trực tuyến của kịch bản ‘pool-based sampling’ vì ngay lập tức nó
yêu cầu người sử dụng gán nhãn sau khi nó được phân lớp [44]. Chúng ta có
thể kết luận rằng kịch bản ‘stream-based scenario’ khác biệt với kịch bản
‘pool-based sampling’ về việc liệu trong mô hình các mẫu được chọn có
được hỏi người sử dụng nhãn ngay lập tức không hoặc lúc đầu tất cả các mẫu
được xếp hạng và từ dữ liệu đã xếp hạng này có được lựa chọn để được gán
nhãn.
2.4 Các chiến lược truy vấn trong học tích cực
Các mẫu được chọn phải có rất nhiều thông tin có hiệu quả cho bài
16
toán. Để làm được việc lựa chọn mẫu, có một số phương pháp truy vấn độc
lập với kịch bản học tích cực đã giới thiệu giới thiệu ở trên.
Trong số các phương pháp truy vấn được sử dụng trong các ứng dụng
khác nhau của phương pháp học tích cực, Settles [6][7] đã trình bày việc
phân loại hoàn chỉnh nhất và toàn diện nhất cho các phương pháp truy vấn
này. Trong đó có hai phương pháp được sử dụng rộng rãi nhất đó là lấy mẫu
không chắc chắn và truy vấn dựa trên hội đồng (Query by committee).
2.4.1 Lấy mẫu không chắc chắn
Phương pháp lựa chọn mẫu nổi tiếng nhất và đơn giản là "lấy mẫu
không chắc chắn" (Uncertainty Sampling) được giới thiệu bởi Lewis và Gale
[14]. Trong phương pháp này, bộ học tích cực đưa ra các mẫu tới người sử

bộ phân lớp, các mẫu mà có độ bất đồng lớn nhất giữa các bộ phân lớp sẽ
được lựa chọn và đưa ra cho người sử dụng gán nhãn.
2.5 So sánh học tích cực học thụ động
• Bộ học
Một bộ học tích cực thu thập thông tin bằng cách đưa ra các câu truy
vấn và nhận lại các câu trả lời. Sau đó nó đưa ra bộ phân lớp hoặc mô hình có
thể sử dụng được cho bài toán của mình. Bộ học tích cực khác với bộ học thụ
động ở chỗ bộ học thụ động nhận thông tin một cách ngẫu nhiên và sau đó
đưa ra bộ phân lớp và mô hình. Một điểm khác nữa là bộ học thụ động chuẩn
giống như một sinh viên thu thập thông tin bằng cách chỉ ngồi và lắng nghe
giáo viên trong khi bộ học tích cực là người đặt ra câu hỏi cho giáo viên, nghe
câu trả lời và hỏi thêm dựa trên câu trả lời của giáo viên. Rất hợp lý khi đưa ra
câu hỏi dựa trên câu trả lời trước đó sẽ cho phép bộ học tích cực thực hiện tốt
hơn bộ học thụ động.
• Thành phần truy vấn
Điểm khác chủ yếu giữa bộ học tích cực và bộ học thụ động là khả
năng đặt câu hỏi vào câu hỏi và câu trả lời trước. Khái niệm về câu hỏi và câu
trả lời chính xác là gì sẽ phụ thuộc vào các bài toán cụ thể tiếp theo. Khả năng
sử dụng phương pháp học tích cực sẽ được lựa chọn tùy vào từng trường hợp,
từng bài toán cụ thể.
18
2.6 Miền ứng dụng của học tích cực
Học tích cực được áp dụng trong rất nhiều ứng dụng khác nhau, nhưng
đặc biệt gần đây người ta lại chú ý đến phương pháp học tích cực trong lĩnh
vực xử lý ngôn ngữ tự nhiên. Ngoài ra học tích cực cũng được sử dụng trong
nhiều ứng dụng như:
• Nhận dạng giọng nói (Hakkani-Tür et al., 2002), hiểu ngôn ngữ nói (Tur et

Tóm lại, phương pháp học tích cực được tóm tắt lại như sau: Đầu tiên
chúng ta chọn một mô hình và độ tổn thất mô hình thích hợp với bài toán học.
Sau đó chúng ta cũng chọn một phương pháp cho việc tính độ tổn thất mô hình
tiềm năng đưa ra câu truy vấn tiềm năng. Với mỗi câu truy vấn chúng ta đánh
giá độ tổn thất tiềm năng và chúng ta lựa chọn để đưa ra câu truy vấn, câu truy
vấn này sẽ đưa ra được độ tổn thất mô hình tiềm năng thấp nhất.
20
CHƯƠNG III - MỘT SỐ THUẬT TOÁN HỌC TÍCH
CỰC
Chương này sẽ giới thiệu một số thuật toán học tích cực. Cụ thể sẽ đi vào giới
thiệu hai thuật toán phổ biến là perceptron và Active SVM.
3.1 Học tích cực dựa trên perceptron
3.1.1 Giới thiệu
Một trong những phương pháp tiếp cận ra đời sớm nhất cho vấn đề
phân lớp tuyến tính trong học máy là thuật toán Perceptron. Perceptron được
Rosenblatt đề xuất năm 1958 [17], chiếm một vị trí quan trọng trong lịch sử
của các thuật toán nhận dạng mẫu.Perceptron là một bộ phân lớp tuyến tính và
là một phần của học máy kể từ những năm 1958 và đã có nhiều phân tích lý
thuyết về nó. Phần này sẽ trình bày thuật toán học tích perceptron chuẩn và
thuật toán perceptron tích cực có cải tiến bước cập nhật do Dasgupta đề xuất
năm 2005 [32].
3.1.2 Thuật toán perceptron
Cho tập dữ liệu học 


bằng siêu phẳng chia dữ liệu thành vào các lớp thuộc tính. Tập các giả thiết
như vậy ta có:












(3.1)
Trong đó 

và 

 là các hệ số có thể điều chỉnh đóng vai trò
là tham số của mô hình. Hàm phân lớp nhị phân h: R
m
→ {0,1}, có thể thu
được bằng cách xác định dấu của :
21

ế

Khởi tạo các giả thiết ban đầuv
0
For t=0 to n do
Dự đoán: if 



then 





 else 






Bước lọc: quyết định hỏi nhãn y
t
của điểm x
t
Cập nhật:
If 











, u là vector
đơn vị. Do đó thuật toán sẽ lựa chọn các dữ liệu sao cho giảm miền lỗi của giả
thiết càng nhiều càng tốt.
Bước cập nhật
Rosenblatt [17] là người đầu tiên phân tích hoạt động hội tụ của bước
cập nhật perceptron, nó bao gồm qui tắc đơn giản sau đây:
if (x
t
, y
t
) bị phân lớp nhầm (misclassified), then 







.
Vì vậy, thay vì sử dụng một biến của nguyên tắc cập nhật, theo
Motzkin và Schoenberg [40] đã cải tiến bước cập nhật theo quy tắc sau:
if (x
t
, y

≠ SGN (v
t
.
x
t
). Vì vậy Motzkin và Schoenberg [40] đang chia mức độ các bản cập nhật
sau của perceptron chuẩn theo một thừa số 2|v
t
.x
t
| để tránh những dao động
gây ra bởi các điểm gần một nửa không gian đại diện bởi các giả thuyết hiện
thời. Motzkin và Schoenberg đã giới thiệu quy tắc này, trong bối cảnh giải
quyết các bất đẳng thức tuyến tính, và gọi nó là phương pháp "phản xạ"
(Reflexion). Sau đó, Hampson và Kibler [34] áp dụng nó để học tập bộ phân
tách tuyến tính, trong một khuôn khổ phân tích khác với chúng ta. Cùng một
quy tắc, nhưng không có tham số 2, đã được sử dụng trong nhiều nghiên cứu
trước đây [4] nghiên cứu về việc học các bộ phân lớp tuyến tính từ dữ liệu
nhiễu, trong một thiết lập khối. Hai ông có thể chỉ ra rằng công thức của họ có
sự thực hiện tổng quát trong một thiết lập giám sát (không tích cực).
Bước lọc
23
Với giới hạn mà thuật toán đã đưa ra, thì luật lọc tự nhiên là truy vấn
các điểm x
t
khi |v
t

3.1.3 Cải tiến bước cập nhật perceptron
Phần này mô tả một thuật toán Perceptron đã đượcc cải tiến. Không
giống như Perceptron chuẩn, thuật toán Perceptron cải tiến đảm bảo rằng v
t
.u
tăng nghĩa là lỗi của v
t
giảm đơn điệu. Một sự khác biệt nữa của bản cải tiến
chuẩn (so với các bản khác) là độ lớn của các giả thuyết hiện thời luôn luôn là
1. Điều này rất thuận lợi cho việc phân tích.

Perceptron cải tiến
chiều d và số lần cập nhật M






với dữ liệu đầu tiên







For t=1 to M:

