Ứng Dụng Học Tích Cực Cho Bài Toán Lọc Thư Rác‌

CHƯƠNG 4. ỨNG DỤNG HỌC TÍCH CỰC CHO BÀI TOÁN LỌC THƯ RÁC‌

4.1 Giới thiệu‌

Trong số các phương pháp lọc và ngăn chặn thư rác thông dụng, phương pháp lọc theo nội dung có một số ưu điểm quan trọng và hiện đang được sử dụng trong nhiều hệ thống lọc thư thương phẩm. Lọc theo nội dung hoạt động theo nguyên tắc phân loại thư điện tử thành hai nhóm “thư rác” và “thư thường” bằng cách phân tích phần nội dung của thư. Trong nghiên cứu này, chúng tôi giới hạn việc phân loại thư cho trường hợp thư có chứa văn bản. Như vậy, nội dung thư ở đây là phần văn bản trong thư. Chúng tôi cũng không xem xét tới cách định dạng trong thư khi phân loại, chẳng hạn thư có được trình bày dưới dạng HTML hay không, mặc dù thông tin về định dạng có thể đóng vai trò quan trọng trong việc phát hiện thư rác.

Lọc thư rác theo nội dung là trường hợp riêng của bài toán phân loại văn bản. Tuỳ theo nội dung, thư được phân thành hai loại: thư rác và thư bình thường. Việc phân loại tiến hành như sau. Trước tiên, nội dung thư được biểu diễn dưới dạng vector các đặc trưng hay các thuộc tính, mỗi đặc trưng thường là một từ hoặc cụm từ xuất hiện trong thư. Tiếp theo, trong giai đoạn huấn luyện, tập thư đã được gán nhãn {rác, bình thường} - gọi là dữ liệu huấn luyện hay dữ liệu mẫu - được sử dụng để huấn luyện một bộ phân lớp. Sau khi huấn luyện xong, bộ phân loại được sử dụng để xác định thư mới (thư chưa biết nhãn) thuộc vào loại nào trong hai loại nói trên. Trong cả giai đoạn huấn luyện và phân loại, thuật toán phân loại chỉ làm việc với nội dung thư đã được biểu diễn dưới dạng vector.

Có nhiều phương pháp phân loại có thể sử dụng để phân loại thư điện tử, luận văn này nghiên cứu phân loại dựa vào phương pháp học tích cực với hai thuật toán xây dựng bộ học tích cực là thuật toán Perceptron [17] và Acitve Support Vector Machines (Acitve SVM) [35].

4.2 Học tích cực trong bài toán lọc thư rác‌

Nhiệm vụ của lọc thư rác là tự động tìm ra các thư điện tử không mong muốn, độc hại trước khi chúng được chuyển đến người sử dụng. Nhiệm vụ của lọc thư rác là một phạm vi ứng dụng quan trọng và có qui mô lớn trong lĩnh vực học máy.

Phương pháp học tích cực đã được phát triển mạnh mẽ trong học máy để làm giảm đi chi phí gán nhãn bằng cách xác định các dữ liệu chứa thông tin mà có yêu cầu nhãn. Điều này được thể hiện trong thực tế rằng chỉ có một phần nhỏ của tập dữ liệu chưa có nhãn là cần phải được gán nhãn để huấn luyện bộ học tích cực sao cho đạt đến một hiệu suất đủ để ứng dụng trong việc phân loại. Với tốc độ học cao và yêu cầu ít các email đã gán nhãn để huấn luyện, chúng ta sẽ áp dụng phương pháp học tích cực ở trên vào bài toán lọc thư rác. Phương pháp học tích cực cho phép chọn các mẫu huấn luyện một cách tự động. Sử dụng tri thức hiện tại, bộ học tích cực không thụ động nhận các mẫu huấn luyện mà lại tích cực lựa chọn các mẫu sao cho có thể huấn luyện được một mô hình tối ưu hơn.

Kịch bản ý tưởng của học tích cực trong bài toán lọc thư rác được thể hiện qua hình 4.1. Các thư điện tử được giả sử là đến theo luồng, nghĩa là tại một thời điểm chỉ có một thư điện tử đến. Với mỗi một thư đến, bộ học sẽ đưa ra truy vấn để nhận được nhãn của thư bằng cách dự đoán đó là thư thường hay thư rác. Người dùng sẽ quan sát thư và nhãn của thư được bộ học dự đoán trước đó và thực hiện phản hồi đến bộ học tích cực, cung cấp nhãn thực sự của thư, thư đó thực sự là thư rác hay thư thường. Bộ lọc thư tích cực nhận phản hồi của người dùng sẽ xác định được sự dự đoán của mình về nhãn của thư là đúng hay sai. Nó học sẽ sử dụng nhãn thực sự của thư do người dùng phản hồi để cập nhật thêm vào tập huấn luyện, huấn luyện (cập nhật) lại mô hình để cải thiện hiệu suất lọc thư hay cải thiện dự đoán nhãn cho các thư sau.

Hình 4.1 Bộ lọc thư rác áp dụng phương pháp học tích cực

Có nhiều thuật toán được sử dụng để xây dựng bộ học tích cực, điển

hình như thuật toán truy vấn dựa vào hội động (Query by Committee), lấy

mẫu không chắc chắn, truy vấn dựa vào tập dữ liệu ban đầu… Các thuật toán này đều đạt hiệu quả trong bài toán lọc thư rác. Tuy nhiên trong luận văn này, chỉ áp dụng 2 thuật toán học tích cực là Perceptron và active SVM để xây dựng bộ học tích cực cho bài toán lọc thư rác.

Trong mô hình bài toán lọc thư rác bộ học tích cực được xây dựng dưa vào thuật toán perceptron hoặc thuật toán học tích cực dựa vào SVM đã trình bày ở chương 3. Với bộ họctích cực được xây dựng trên thuật toán perceptron sẽ cho ta bộ lọc thư rác tích cực perceptron. Bộ học tích tích cực được xây dựng dựa trên active SVM sẽ thu được bộ lọc thư SVM tích cực. Các bộ lọc thư rác tích cực này được thể hiện trong hình 4.2. Thư điện tử khi đến sẽ được vector hóa và được trích chọn các thuộc tính đặc trưng đại diện cho thư, sau đó được đưa vào bộ học tích cực (perceptron hoặc SVM active). Quá trình học của bộ lọc thư điện tử sẽ được lặp đi lặp lại nhằm mục đích thu được một bộ lọc đạt hiệu quả cao.

Hình 4.2 Bộ lọc thư rác tích cực dựa trên Perceptron/SVM active

4.3 Thử nghiệm và kết quả‌

Luận văn định hướng khai thác phần mềm mã nguồn mở để tiến hành thử nghiệm phân loại thư điện tử trên tập dữ liệu là các thư điện tử bao gồm cả thư thườngvà thưc rác. Phần đầu của mục 4.3 sẽ giới thiệu hai tool thực nghiệm mã nguồn mở cài đặt hai thuật toán học tích cực đã trình bày trong chương ba là chương trình Snow do Dan Roth xây dựng [46] và chương trình ActiveExperimenter do Ran EL-Yaniv xây dựng [47]. Các phần tiếp theo sẽ thu thập dữ liệu và xây dựng chương trình tiền xử lý dữ liệu và biểu diễn dữ liệu về dạng dữ liệu đầu vào cho các công cụ thực nghiệm. Và cuối cùng là phân tích, đánh giá và nhận xét thực nghiệm.

4.3.1. Cài đặt chương trình thử nghiệm‌

4.3.1.1. Chương trình snow

1. Giới thiệu chương trình

Chương trình Snow được Ran Roth cài đặt phiên bản đầu tiên năm 1999, và các phiên bản sau cũng được phát triển trong nững năm tiếp theo. Snow là chương trình học kiến trúc, là bộ học được cài đặt trên các thuật toán winnow, percepptron, naïve Bayer…

2. Down load

Chương trình được download trên trang web mã nguồn mở: http://l2r.cs.uiuc.edu/~cogcomp/asoftware.php?skey=SNOW

3. Cài đặt

Chương trình được cài đặt trên máy tính có cài hệ điều hành Linux, Trước tiên, cần giải nén file cài đặt bằng các lệnh sau:

>tar –xvzf SNoW_v3.1.8.tar

Sau đó nó sẽ tạo ra một thư mục có tên là Snow_v3.1 chứa Makefile và các file nguồn. Chuyển đường dẫn vào thư mục vừađược tạo ra (Snow_v3.1) bằng lệnh

> cd Snow_v3.1

Gõ lệnh:

>makefile

Chương trình sẽ tạo ra file thực thi

Snow

Quá trình thực thi này được sử dụng để huấn luyện, kiểm tra và đánh giá quá trình thực hiện.

4.3.1.2. Chương trình ActiveExperimenter

1. Giới thiệu chương trình

ActiveExperiment là chương trình được cài đặt dựa trên bốn thuật toán học tích cực dựa vào SVM, đó là thuật toán Simple, Self-Conf, KFF và balanced. Chương trình được Ran EL-Yaniv xây dựng bằng ngôn ngữ java, cài đặt một số thuật toán học tích cực.

2. Down load

Người dùng có thể download công cụ trên trang web: http://www.cs.technion.ac.il/~rani/code/active/code_index.html

3. Cài đặt

Chương trình có thể cài đặt trên máy tình cáo cài hệ điều hành Window hoặc Linux. Để chạy chương trình trước tiên phải cài java

1.4.2 hoặc phiên bản cao hơn. Có thể download java trên trang web.

Sau khi đã cài đặt môi trường, giải nén file cài đặt AcitveExperimenter.zip, ta được thư mục AcitveExperimenter. Trong

thư mục có chưa file experimenter.bat chính là file chạy của chương trình.

4.3.2. Thu thập và biểu diễn dữ liệu‌

1. Dữ liệu thử nghiệm

Một khó khăn khi thử nghiệm lọc thư là hiện nay chưa có những bộ dữ liệu mẫu chuẩn. Do vậy tác giả sẽ tự tiến hành xây dựng bộ dữ liệu thư để dùng trong thử nghiệm của mình. Thư rác được thu thập từ hai nguồn: nguồn thứ nhất là những thư rác mà các tác giả nhận được qua địa chỉ thư của mình tại Việt nam. Nguồn thứ hai là những thư rác do quản trị phát hiện tại mail server của công ty FPT (mail.fpt.com.vn). Thư bình thường là những thư mà các tác giả nhận được thông qua hòm thư mail.gdt.gov.vn.

Đối với các thư bình thường nhận được, trong trường hợp thư nhận từ cùng một nguồn qua nhiều phiên gửi và reply thì đối với những thư gửi sau sẽ được xoá phần đã gửi từ trước, chỉ giữ lại nội dung thư nhận được cuối cùng. Đối với những thư bao gồm cả văn bản và hình ảnh, chỉ có phần văn bản được sử dụng, phần hình ảnh bị bỏ qua không xem xét. Các thông số chính về bộ dữ liệu được thống kê:

Tổng thư: 700

Thư rác: 236

Thư thường: 464

2. Biểu diễn nội dung thư dưới dạng mô hình boolean

Để có thể sử dụng kỹ thuật học máy và xác suất thống kê, nội dung thư cần được biểu diễn dưới dạng thuận tiện cho việc áp dụng thuật toán học máy. Các phương pháp lọc thư bằng cách tự động phân loại theo nội dung đều sử dụng cách biểu diễn thư dưới dạng véctơ. Mặc dù có nhiều cách xây dựng véctơ nhưng cách đơn giản nhất là mô hình boolean. Nguyên tắc cơ bản của phương pháp này là không quan tâm tới vị trí xuất hiện các từ hay cụm từ

trong thư mà coi thư như một tập hợp không có thứ tự các từ. Mỗi thư khi đó được biểu diễn bởi một véctơ. Số phần tử của véctơ bằng số lượng từ khác nhau trên toàn bộ tập dữ liệu huấn luyện.

Có nhiều cách tính giá trị các phần tử của vectơ. Cách đơn giản nhất là sử dụng giá trị nhị phân: mỗi phần tử của véctơ bằng 1 hay 0 tuỳ thuộc vào từ tương ứng có xuất hiện trong thư tương ứng với véctơ hay không.

Giả sử có một tập gồm m văn bản D = {d1, d2, … , dn}. Mỗi văn bản gòm n từ khóa T = {t1, t2, … , tn}. Gọi W = (wij) là ma trận trọng số, trong đó wij là trọng số của từ khóa ti trong văn bản dj.

Mô hình Boolean là mô hình đơn giản nhất, trong đó trọng số các từ trong văn bản là 0 hoặc 1. Khi đó, mỗi văn bản sẽ được biểu diễn dưới dạng tập hợp như sau:

di={tij}, trong đó tij là từ ti có trọng số wij trong văn bản dj là 1.[1]

Các phương pháp phức tạp hơn thường dựa vào tần suất xuất hiện của từ trong thư. Từ xuất hiện càng nhiều thì phần tử tương ứng của vectơ có giá trị càng lớn và ngược lại.

Trên các tập dữ liệu mẫu thực, số lượng từ khác nhau có thể lên tới hàng chục nghìn tương ứng với số lượng phần tử trong mỗi véctơ. Trong các phần sau sẽ đề cập tới kỹ thuật giảm bớt số lượng từ dùng để biểu diễn thư.

Phương pháp biểu diễn thư sử dụng boolean trình bày ở trên bỏ qua thông tin về vị trí xuất hiện và thứ tự các từ trong thư. Những thông tin này có thể có giá trị quan trọng trong việc phát hiện thư rác. Tuy nhiên, do đơn giản, phương pháp boolean vẫn là phương pháp biểu diễn nội dung thư thông dụng nhất, mặc dù có nhược điểm vừa nêu. Trong nghiên cứu này, luận văn cũng sử dụng phương pháp boolean và các mở rộng của phương pháp này để biểu diễn nội dung thư điện tử:

Tập các từ trong tất cả tài liệu sẽ được sắp xếp thành từ điển và được đánh chỉ số theo thứ tự tăng dần. Thư sẽ được biểu diễn dưới dạng vector, biểu diễn thứ tự tăng dần các chỉ số của các từ có trong thư đó.

Dưới đây là một ví dụ đơn giản minh hoạ cho cách biểu diễn nội dung nói trên. Dữ liệu huấn luyện bao gồm bốn thư, trong đó hai thư là thư rác và hai là thư bình thường. Nội dung các thư được cho trong bảng 4.1. Trên bảng

4.3. là biểu diễn véctơ cho các thư trong bảng 4.1.

Số TT