Luận văn 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

ĐẠ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 4 DANH SÁCH CÁC BẢNG BIỂU Bảng 4.1 Ví dụ nội dung của bốn thư 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 thức quảng cáo chuyên nghiệp, phát tán virus, ăn cắp thông tin... với nhiều thủ đoạn và mánh khóe cực kỳ tinh vi. Người dùng sẽ phải mất khá nhiều thời gian để xóa những thư điện tử “không mời mà đến”, nếu vô ý còn có thể bị nhiễm virus, trojan, spyware ... và nặng nề hơn là mất thông tin như thẻ tín dụng, tài khoản ngân hàng qua các email dạng thư lừa người dùng tưởng đó là thư hợp lệ (phishing). Để loại bỏ hoặc giảm thiểu ảnh hưởng của thư rác, nhiều cách tiếp cận khác nhau đã được nghiên cứu và sử dụng. Giải pháp đấu tranh với thư rác rất đa dạng, bao gồm từ các cố gắng về pháp lý trong việc xây dựng luật ngăn chặn phát tán thư rác cho tới những giải pháp kỹ thuật nhằm phát hiện và 6 ngăn chặn thư rác trong những giai đoạn khác nhau của quá trình tạo và phát tán thư. Tất nhiên, những kẻ gửi thư rác sẽ liên tục cải thiện chiến thuật/cách thức của chúng, do đó, điều quan trọng là biện pháp ngăn chặn thư rác phải “học” cách thức thay đổi của thư rác theo thời gian để giúp việc ngăn chặn có hiệu quả. Và việc ngăn chặn thư rác phải được thực hiện nhanh nhất có thể để không làm ảnh hưởng đến hệ thống, công việc khác. Từ những đặc điểm của hệ thống thư điện tử như có sự tương tác với người sử dụng và sự biến đổi của thư rác, luận văn nghiên cứu về học tích cực và xác định được sự phù hợp cho bài toán lọc thư rác. Đề tài “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” được tiến hành nhằm đưa ra được phương pháp xây dựng bộ lọc thư rác có thể “học” được cách thức thay đổi của thư rác và tận dụng được sự tương tác với người dùng để đưa ra các truy vấn phân loại cho thư điện tử giúp cho việc phân loại thư rác đạt hiệu quả và chính xác cao. Trong phạm vi đề tài, luận văn tiến hành nghiên cứu một số giải pháp 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 những người gửi thư rác. Sử dụng phương pháp học tích cực cho bài toán lọc thư rác làm phong phú thêm tập lời giải cho bài toán nhận dạng các đối tượng biến đổi. Bộ lọc thư rác tích cực giảm chi phí và thời gian thu thập dữ liệu, bởi vì nó được xây dựng dựa trên sự tương tác giữa bộ học và người dùng là nhận dạng thư rác hay thư thường. Với mục tiêu đã nêu ở trên luận văn chủ yếu tập trung nghiên cứu vào phương pháp học tích cực, áp dụng được các bộ học để tìm ra lời giải cho bài toán lọc thư rác. Để kiểm tra và đánh giá kết quả, luận văn sử dụng các chương trình thực nghiệm đã cài đặt sẵn các bộ học mà luận văn nghiên cứu, thu thập dữ liệu thực tế, xây dựng chương trình xử lý dữ liệu thành các tri thức để huấn luyện các bộ học thực nghiệm nhằm phát hiện ra các thư rác một cách chính xác và đạt hiệu quả cao. 1.1.3 Các giai đoạn thực hiện đề tài Quá trình nghiên cứu của luận văn được thực hiện qua các giai đoạn sau: 8 Giai đoạn 1 – Nghiên cứu lý thuyết: Thu thập tài liệu, các bài viết liên quan đến học tích cực và phương pháp lọc mail. Nghiên cứu tài liệu, tìm hiểu phương pháp học học máy nói chung và phương pháp học tích cực nói riêng. Tìm hiểu cụ thể vào pương pháp học tích cực dựa vào perceptron và học tích cực với SVM. Tìm hiểu một số phương pháp lọc mail, tham khảo một số mô hình lọc mail đã được xây dựng. Trên cơ sở khoa học và lý thuyết đã tìm hiểu lựa chọn phương pháp và áp dụng trong thực tế. Giai đoạn 2 – Xây dựng chương trình tiền xử lý dữ liệu để làm dữ liệu cho bài toán lọc mail. Tìm hiểu và cài đặt các công cụ có ứng dụng cho bài toán lọc mail. Thu thập dữ liệu từ thực tế, sử dụng chương trình có sẵn, xử lý 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. 10 CHƯƠNG II - TỔNG QUAN VỀ HỌC TÍCH CỰC 2.1 Giới thiệu học tích cực Mục đích chính của học máy là thu được những mẫu chung từ một lượng dữ liệu hữu hạn [36]. Học máy được chia thành 2 loại: học có giám sát và học không giám sát. Nhiệm vụ của học giám sát là dự đoán thêm những các đặc trưng của một đối tượng đầu vào [36]. Ví dụ: đơn giản là bài toán dự doán cân nặng của một người khi biết chiều cao của họ, còn những bài toán phức tạp hơn có thể là dự đoán chủ đề của hình ảnh khi biết các giá trị của điểm ảnh. Một lĩnh vực trọng tâm của học giám sát là bài toán phân lớp. Phân lớp là bài toán học có giám sát mà ở đó đặc trưng nữa của một đối tượng mà chúng ta mong muốn dự đoán là các giá trị rời rạc. Ta gọi đặc trưng này là nhãn. Mục đích của phân lớp là tạo ra một ánh xạ các đối tượng đầu vào tới các nhãn.Ví dụ, phân loại các tài liệu trong đó chúng ta mong muốn gán nhãn tự động cho một tài liệu mới với một vài chủ để đã xác định trước (ví dụ thể thao, chính trị, kinh doanh…). Hướng tiếp cận của học máy để giải quyết được vấn đề này là chúng ta phải thu thập được tập huấn luyện (trainning set) bằng cách gán nhãn tự động một số các tài liệu. Tiếp theo chúng sử dụng một bộ học (learner) thực hiện trên tập huấn luyện đã được gán nhãn để sinh ra một ánh xạ từ các tài liệu đến chủ đề. Chúng ta gọi ánh xạ này là bộ phân lớp (classifier). Chúng ta có thể dùng bộ phân lớp (classifier) để gán nhãn cho các tài liệu mới. Một lĩnh vực lớn nữa của học máy là học không giám sát. Khoảng cách giữa học giám sát và học không giám sát cũng không hoàn toàn rõ ràng. Tuy nhiên bản chất của học không giám sát là chúng ta sẽ không nhận được thông tin cụ thể về cách thức thực hiện như thế nào. Nói cách khác, trong bài toán phân lớp chúng ta nhận được tập dữ liệu huấn luyện đã được gán nhãn tự độ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: v 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. v 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 những người phù hợp với các đặc điểm nào đó. Ví dụ Chúng ta muốn kiểm tra những người hút thuốc và trên 50 tuổi. v Hơn nữa, chúng ta không cần phải đưa ra các danh sách câu hỏi trước. Chúng ta có thể chọn câu hỏi tiếp theo dựa trên các câu trả lời của các câu hỏi trước. Quá trình hướng dẫn các bước lấy mẫu bằng câu hỏi cho một số trường hợp nào đó căn cứ vào dữ liệu mà chúng ta đã được cung cấp gọi là học tích cực. 12 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ọc tích cực (đôi khi còn được gọi là học truy vấn hay thiết kế thực nghiệm tối ưu trong các bài toán thống kê) là một lĩnh vực nhỏ của học máy nói riêng và trong trí tuệ nhân tạo nói chung. Giả thiết chính là nếu thuật toán học được phép chọn dữ liệu từ những gì nó học thì nó sẽ thực hiện tốt hơn ngay cả khi được huấn luyện ít hơn. Hệ thống học tích cực cố gắng vượt qua những hạn chế trong việc gán nhãn bằng cách đưa ra các truy vấn để các dữ liệu chưa gán nhãn sẽ được 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