ĐẠ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
1.1 Giới thiệu đề tài ...................................................................................... 5
1.1.1 Lý do chọn đề tài ................................................................................... 5
1.1.2 Mục tiêu của đề tài ................................................................................ 6
1.1.3 Các giai đoạn thực hiện đề tài ............................................................... 7
1.2 Cấu trúc của luận văn ............................................................................ 8
CHƯƠNG II - TỔNG QUAN VỀ HỌC TÍCH CỰC ................................. 10
2.1 Giới thiệu học tích cực ......................................................................... 10
2.2 Phương pháp học tích cực ................................................................... 13
2.3 Kịch bản học tích cực ........................................................................... 15
2.3.1 Stream_based Sampling ..................................................................... 15
2.3.2 Pool-based Sampling .......................................................................... 15
2.4 Các chiến lược truy vấn trong học tích cực ....................................... 15
2.4.1 Lấy mẫu không chắc chắn................................................................... 16
2.4.2 Truy vấn dựa vào hội đồng ................................................................. 17
2.5 So sánh học tích cực học thụ động ...................................................... 17
2.6 Miền ứng dụng của học tích cực ......................................................... 18
2.7 Kết luận ................................................................................................. 19
CHƯƠNG III - MỘT SỐ THUẬT TOÁN HỌC TÍCH CỰC .................. 20
3.1 Học tích cực dựa trên perceptron ....................................................... 20
3.1.1 Giới thiệu ............................................................................................ 20
3.1.2 Thuật toán perceptron ......................................................................... 20
3.1.3 Cải tiến bước cập nhật perceptron ...................................................... 23
3.1.4 Perceptron chỉnh sửa tích cực ............................................................. 25
3.2 Học tích cực với SVM ......................................................................... 27
2
3.2.1 Giới thiệu ............................................................................................ 27
3.2.2 Máy hỗ trợ vector ................................................................................ 27
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) Máy hỗ trợ vector và máy hỗ trợ vector transaction
Hình 3.6 Máy hỗ trợ vector sử dụng hàm nhân đa thức bậc 5
Hình 3.7 (a) Tính đối ngẫu trong version space
(b) Một bộ phân lớp SVM trên một version space
Hình 3.8 (a) Lề đơn giản truy vấn b (b) Lề đơn giản truy vấn a
Hình 3.9 (a) Lề MaxMin truy vấn b (b) Lề MaxRatio truy vấn e.
Hình 4.1 Bộ lọc thư rác áp dụng phương pháp học tích cực
Hình 4.2 Bộ lọc thư rác tích cực dựa trên Perceptron/SVM active
Hình 4.3 Giao diện chính của chương trình
Hình 4.4 Giao diện lựa chọn thư mục chứ dữ liệu
Hình 4.5 Thông báo quá trình làm sạch dữ liệu thành công
Hình 4.6 Giao diện thông báo kết quả xử lý
Hình 4.7 Kết quả thuật toán perceptron
Hình 4.8 Cấu trúc file cấu hình của chương trình ActiveExperiment
Hình 4.9 Kết quả chạy thuật toán SIMPLE
Hình 4.10 Kết quả chạy thuật toán SELF_CONF
Hình 4.11 Kết quả chạy thuật toán KFF
Hình 4.12. Kết quả chạy thuật toán BALANCE_EE