Báo cáo Nghiên cứu bộ lọc thư spam trên cơ sở mạng Bayes

SEMINAR: CƠ SỞ DỮ LIỆU NÂNG CAO 
NGHIÊN CỨU BỘ LỌC THƯ SPAM TRÊN CƠ SỞ MẠNG BAYES 
Học viên: Nguyễn Viết Linh 
MS: CH0601038 
GIỚI THIỆU 
Các bộ lọc thư spam trên cơ sở luật và dấu hiệu không có khả năng tự tạo ra quyết định và lọc các spam mới. 
Các bộ lọc thư trên cơ sở mạng Bayes cho phép bộ lọc có thể ‘ học’ và có khả năng tự ra quyết định với các spam mới . 
Các bộ phân lớp trên cơ sở máy học cho ta hiệu quả lọc và phán đoán các thư spam hiệu quả cao . Với các bộ lọc trên cơ sở mạng Bayes được huấn luyện tốt , độ chính xác có thể đạt tới 99 %. 
GIỚI THIỆU 
 	 Trong seminar này chúng ta sẽ đề cập đến các vấn các đề sau để xây dựng bộ lọc spam kỹ thuật Bayes: 
Bộ lọc spam trên cơ sở mạng Bayes đơn giản 
Bộ lọc spam trên cơ sở mạng Bayes đầy đủ 
Các phương thức huấn luyện cho các bộ lọc spam kỹ thuật Bayes 
Phân lớp Email và sự phân lớp sai 
Hiện thực bộ phân lớp spam Bayes 
I. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐƠN GIẢN  ( Tổng quan về mạng Bayes ) 
Mạng Bayes là một dạng mô hình đồ thị theo xác suất không có cung trực tiếp . Các nút biểu diễn các biến ngẫu nhiên , các cung biểu diễn mối quan hệ phụ thuộc giữa các biến . 
Nếu các biến là X1, ... , Xn và “parents(A)” là các cha của nút A, thì phân bố kết nối cho X1 tới Xn được biểu diễn dưới dạng kết quả của phân bố theo xác suất : P(X1,..., Xn ) = ∏ P( Xi | parents( Xi )) for i = 1 to n. 
I. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐƠN GIẢN  ( Mô hình mạng Bayes đơn giản ) 
Một mạng Bayes đơn giản nhất g ồm m ột nút cha 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 như sau : P( Xp , X1, ..., Xn ) = P( Xp ) ∏ P( Xi | Xp ) for i = 1 to n. 
Bộ phân lớp Naive Bayes là một bộ phân lớp theo xác suất đơn giản . Lợi ích chính của bộ phân lớp Naive Bayes là có thể huấn luyện rất hiệu quả bằng việc học có giám sát . 
I. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐƠN GIẢN  ( Giải pháp cụ thể cho cho bộ lọc spam 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ơ chế hoạt động của bộ lọc này như sau : 
Đầu tiên cần token hoá nội dung của email cần phân lớp . Các token này có thể là các cụm từ , các cặp từ , nhưng thường s ử dụng các từ đơn để định nghĩa các token. 
Bước tiếp theo , s ử dụng các giá trị trong một từ điển để tính toán giá trị của m ỗ i token c ủa email . T ừ điển này chứa các token xuất hiện trong các thư spam và thư hợp lệ đã được phân lớp từ trước cùng các giá trị tương ứng . 
I. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐƠN GIẢN  ( Giải pháp cụ thể cho cho bộ lọc spam Bayes ) 
Sau khi có giá trị của các token trong thư cần phân lớp , ta sử dụng 15 đến 27 token có giá trị tốt nhất để tính xác suất cho một email là thư spam hay 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ả ph ân loại cuối cùng được tạo ra . 
I. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐƠN GIẢN  ( Giải pháp cụ thể cho cho bộ lọc spam Bayes ) 
Một số tính toán cho giải pháp này : 
N1 là số thư spam mà một từ xuất hiện, N2 là số thư hợp lệ mà một từ xuất hiện. 
ALL ( tổng số tất cả các e-mail) = SPAM + HAM ( số thư hợp lệ + số thư spam ). 
Gọi một từ là “ từ so trùng ”, nếu tồn tại cả trong thư và trong từ điển token. 
P ( “ các từ so trùng ” | “ thư là spam ” ) = ∏ cho tất cả từ được so trùng ( giá trị N 1 của từ hiện tại / SPAM ). 
I. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐƠN GIẢN  ( Giải pháp cụ thể cho cho bộ lọc spam Bayes ) 
P ( “c ác từ so trùng” | “thư là hợp lệ” ) = ∏ cho tất cả từ được so trùng (giá trị N 2 của từ hiện tại / HAM ). 
P ( “ thư là spam ” ) = SPAM / ALL 
P ( “ thư là hợp lệ ” ) = HAM / ALL 
P ( “ thư là spam ” | “ các từ so trùng ” ) = P ( “ thư là spam ” ) * P (“ các từ so trùng ” | “ thư là spam ” ) 
P ( “ thư là hợp lệ ” | “ các từ so trùng ” ) = P ( “ thư là hợp lệ ” ) * P (“ các từ so trùng ” | “ thư là hợp lệ ”) 
Kết quả cuối cùng : P ( “ thư là spam ” | “ các từ so trùng ” ) / P ( “ thư là hợp lệ ” | “ các từ so trùng ” ) 
I. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐƠN GIẢN  ( Giải pháp cụ thể cho cho bộ lọc spam Bayes ) 
Cấu trúc từ điển token: 
N1 là số thư spam mà một từ xuất hiện . 
N2 là số thư hợp lệ mà một từ xuất hiện . 
W/S (word has existed/ spam ) là số thư spam c ó từ s o trùng hiện tại chia cho số tất cả các thư spam . 
W/H (word has existed/ham) là số thư hợp lệ c ó từ so trùng hiện tại chia cho số tất cả các thư hợp lệ . 
I. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐƠN GIẢN  ( Một ví dụ cụ thể ) 
Gi ả sử cơ sở dữ liệu có 240 spam và 814 thư hợp lệ được lưu ( tổng cộng là 1054 thư ). Nh ư vậy tỷ lệ thư spam là 23%, thư hợp lệ là 77%. 
Thư nhận được c ần phân lớp như sau : 
------------------------------------------------------------ 
Date: 19.05.1908 11:14 
From: KathrineWitt 
Subject: All products for your health! 
http:// pcvija . seescum .biz/?70573075 
Suffering from pain, depression or heartburn?We'll help you! 
All verified dr @ gs collected at one LICENSED online store! Great choice of wonderful meds to give 
you long-awaited relief! Operative support, fast shipping, secure p@ yment processing and complete 
confidentiality! 
The store is VERIFIED BY BBB and APPROVED BY VISA! 
http:// pcvija . seescum .biz/?70573075 
------------------------------------------------------------ 
I. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐƠN GIẢN  ( Một ví dụ cụ thể ) 
Bộ lọc chia thư thành các token, các giá trị của các token có trong cơ sở dữ liệu như sau : 
I. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐƠN GIẢN  ( Một ví dụ cụ thể ) 
Tính xác suất có thể P( “ thư là spam ” | “ các từ so trùng ” ) = P ( “ thư là spam ” ) * P (“ các từ so trùng ” | “ thư spam ” ) = 23% * ∏ tất cả các từ so trùng (W/S). 
T ính xác suất có thể P ( “ thư hợp lệ ” | “ các từ so trùng ” ) = P ( “ thư là h ợp lệ ” ) * P (“ các từ so trùng ” | “ thư là h ợp lệ ” ) = 77% * ∏ tất cả các từ so trùng (W/H). 
Kết quả cuối cùng là thương số của hai xác suất có thể được tính toán ở trên .N ếu kết quả sẽ l ớn hơn 1 th ì thư giống spam hơn và kết quả nằm giữa zero và 1 th ì thư hợp lệ hơn . 
I. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐƠN GIẢN  ( Biểu đồ bộ lọc ) 
1a: Thư nhận được . 
1b: Thư này được sử dụng như một văn bản thuần tuý ( bao gồm thân và header). 
1c: Thư được phân đoạn thành các token (token hoá ). 
1d: Giá trị lưu trữ được tìm thấy từ cơ sở dữ liệu 1d. 
1e: Thực hiện tính toán các khả năng có thể . 
1f: Kết quả được thông báo cho người sử dụng , đồng thời các giá trị lưu trữ trong cơ sở dữ liệu được cập nhật (1d). 
1g: Thông tin phản hồi của người sử dụng trong trường hợp phân lớp nhầm , cơ sở dữ liệu được cập nhật. 
Phần tính toán được chi tiết trong Hình 2. 
I. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐƠN GIẢN  ( Biểu đồ bộ lọc ) 
2a: Các token có được từ thư đến. 
2b: Các token nhận được các giá trị tương ứng của chúng lưu trữ trong cơ sở dữ liệu 2d. 
2c: Chỉ có các token thích đáng nhất được sử dụng . 
2e: Tính toán được thực hiện bằng cách sử dụng các giá trị của các token thích đáng nhất và các dữ liệu tĩnh khác . 
2f: quyết định cuối cùng được thực hiện , và cơ sở dữ liệu (2d) được cập nhật theo kết quả phân loại. 
I. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐƠN GIẢN  ( Biểu đồ bộ lọc ) 
II. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐẦY ĐỦ  
Một mạng Bayes đầy đủ là một đa mạng bao gồm một tập hợp các mạng Bayes, mỗi mạng Bayes tương ứng với một giá trị c của biến lớp C. 
Một đa mạng cho một bộ phân lớp Bayes đầy đủ FBC (Full Bayesian Network Classifier) là một tập các FBC tương ứng . 
II. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐẦY ĐỦ  ( Cấu trúc của bộ phân lớp Bayes đầy đủ FBC ) 
Cho trước một tập huấn luyện S, chia S thành các tập con | C |, mỗi Sc của nó tương ứng với giá trị c của lớp, và sau đó xây dựng một FBC cho Sc. 
Nghiên cứu cấu trúc của một mạng Bayes hoàn chỉnh (FBN) có nghĩa là nghiên cứu thứ tự của các biến và sau đó thêm các cung từ một biến tới tất cả các biến khác được xếp sau nó. 
Phương pháp này xếp loại một biến trên cơ sở ảnh hưởng toàn bộ của nó lên các biến khác. Sự ảnh hưởng (sự phụ thuộc) giữa hai biến có thể được đo bởi thông tin có cùng mối quan hệ nào đó với nhau và được định nghĩa như sau: 
II. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐẦY ĐỦ  ( Cấu trúc của bộ phân lớp Bayes đầy đủ FBC ) 
Với x và y là các giá trị của các biến X và Y theo thứ tự. Chú ý rằng, vì chúng ta tính toán thông tin có cùng mối quan hệ với nhau trong mỗi tập con Sc của tập huấn luyện, M(X; Y) thực sự là thông tin có cùng mối quan hệ theo điều kiện M(X; Y |c). 
II. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐẦY ĐỦ  ( Cấu trúc của bộ phân lớp Bayes đầy đủ FBC ) 
Trong thực tế, có thể sự phụ thuộc giữa hai biến được đo bởi phương trình (1) là nguyên nhân do nhiễu do đó sự phụ thuộc không đáng tin cậy và sẽ không được tính đến. Như vậy chúng ta cần một ngưỡng để xem xét sự phụ thuộc giữa hai biến có đáng tin cậy không. 
Một cách để định nghĩa ngưỡng dựa trên cơ sở nguyên tắc độ dài mô tả tối thiểu (Minimum Description Length - MDL). 
II. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐẦY ĐỦ  ( Cấu trúc của bộ phân lớp Bayes đầy đủ FBC ) 
Friedman và Yakhini (1996) chỉ ra rằng lỗi entropy giao nhau trung bình tương ứng một cách tiệm cận với logN/2N, với N là kích thước của dữ liệu huấn luyện. Chúng ta chấp nhận kết quả của họ cho định nghĩa ngưỡng để lọc ra các phụ thuộc không đáng tin cậy như sau: 
II. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐẦY ĐỦ  ( Cấu trúc của bộ phân lớp Bayes đầy đủ FBC ) 
Với T ij = |X i |*|X j |, |X i | là số các giá trị có thể của X i , và |X j | tương ứng với X j . Giả sử chúng ta sử dụng dạng sơ đẳng nhất khi biểu diễn cho các bảng xác suất theo điều kiện (CPT), nếu X i và X j độc lập, thì kích thước toàn bộ của hai CPT cho X i và X j là |X i | + |X j |. Nếu chúng ta biểu diễn sự phụ thuộc giữa Xi và Xj, thì kích thước toàn bộ của hai CPT là |X i | * |X j | + |X i | (giả sử X i là cha của X j ). 
Như vậy, T ij biểu diễn sự tăng của kích thước cho biểu diễn phụ thuộc giữa Xi và Xj. Trong thực thi của chúng ta, sự phụ thuộc giữa Xi và Xj chỉ được tính đến nếu M(X i ;X j ) > φ(X i ;X j ). Ảnh hưởng toàn bộ của một biến X i lên biến khác được biểu thị bởi W(X i ) được định nghĩa như sau: 
II. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐẦY ĐỦ  ( Cấu trúc của bộ phân lớp Bayes đầy đủ FBC ) 
Giải thuật học trên cơ sở W(Xi) như sau: 
Algorithm FBC-Structure(S, X) 
Input : Một tập S các mẫu được gắn nhãn,một tập X các biến. 
Output : Một mạng bayes đầy đủ B . 
1. B = rỗng. 
2. Chia dữ liệu huấn luyện S thành các tập con |C| bởi giá trị c của lớp. 
3. Với mỗi tập dữ liệu huấn luyện Sc: 
	- Tính thông tin có cùng mối quan hệ M(Xi;Xj) và sự bất lợi của cấu trúc φ(Xi;Xj)giữa	 	 mỗi cặp biến Xi và Xj trên cơ sở phương trình 1 và phương trình 2. 
	- Tính W(Xi)cho mỗi biến Xi trên cơ sở phương trình 3. 
	- Với tất cả các biến Xi trong X 
	+ Thêm tất cả các biến Xj với W(Xj) > W(Xi)vào tập cha Π xi của Xi. 
	+ Thêm cung từ tất cả các biến Xj vào Π xi của Xi. 
	- Thêm mạng kết quả Bc vào B. 
4. Trả về B . 
II. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐẦY ĐỦ  (Tính toán bảng xác suất có điều kiện CPT ) 
Tiếp theo, một cây CPT sẽ được xác định cho mỗi biến Xi, giải thuật học dạng cây quyết định truyền thống được áp dụng để xác định các cây CPT, độ phức tạp về thời gian thông thường sẽ là O(n 2 . N). Chú ý rằng cây quyết định sẽ được xác định cho mỗi biến. Như vậy giải thuật học FBC kết quả sẽ có độ phức tạp là O(n 3 . N). 
Ta có giải thuật học dạng cây quyết định nhanh cho CPT. Trong tiến trình tăng trưởng của cây, tất cả các biến X j trong Π Xi được lưu dưới dạng thông tin có cùng mối quan hệ M(Xi;Xj) trên toàn bộ dữ liệu huấn luyện xác định thứ tự cố định của các biến, hãy gỡ bỏ biến Xj với thông tin có cùng mối quan hệ cao nhất khỏi Π Xi và tính toán thông tin có cùng mối quan hệ cục bộ MS(Xi; Xj) trên dữ liệu huấn luyện hiện tại S. 
II. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐẦY ĐỦ  (Tính toán bảng xác suất có điều kiện CPT ) 
Nếu nó lớn hơn ngưỡng cục bộ φ s (Xi;Xj ), thì Xj được sử dụng là gốc, và chia dữ liệu huấn luyện hiện tại S theo các giá trị của Xj và lặp lại tiến trình này cho mỗi nhánh (tập con). Ngoài ra, hãy thử một biến khác. Điểm then chốt ở đây là, với mỗi biến chúng ta tính thông tin có cùng mối quan hệ cục bộ và ngưỡng cục bộ chỉ một lần. 
II. BỘ LỌC SPAM TRÊN CƠ SỞ MẠNG BAYES ĐẦY ĐỦ  (Tính toán bảng xác suất có điều kiện CPT ) 
Algorithm Fast-CPT-Tree(¦Xi , S) 
Input : Π Xi là tập các cha của Xi và S là tập các mẫu được gắn nhãn. 
Output : Một cây quyết định T với Xi là các biến dự đoán. 
1. Tạo cây rỗng T . 
2. If (S thuần tuý hoặc rỗng) hoặc ( Π Xi rỗng) Return T. 
3. qualified = False. 
4. While (qualified == False) and (ΠXi không rỗng) 
- Chọn các biến Xj với M(Xj; Xi)cao nhất. 
- Gỡ bỏ Xj khỏi Π Xi. 
- Tính thông tin có cùng mối quan hệ cục bộ M S (Xi;Xj)trên S trên cơ sở phương trình 1. 
- Tính bất lợi cấu trúc cục bộ φ s (Xi;Xj ), trên S trên cơ sở phương trình 2. 
- If M S (Xj; Xi) > φ s (Xi; Xj) qualified = True 
5. If qualified == True 
- Tạo một gốc Xj cho T. 
- Chia S thành các tập con rời nhau Sx, x là giá trị của Xj. 
- Với tất cả các giá trị x của Xj 
+ Tx=Fast-CPT-Tree(¦Xi ,Sx) 
+ Thêm Tx dưới dạng con của Xj. 
6. Return T. 
III. CÁC PHƯƠNG THỨC HUẤN LUYỆN 
Trong các bộ lọc trên cơ sở mạng Bayes, chúng ta cần phải huấn luyện hệ thống trước khi sử dụng, phương pháp huấn luyện tốt sẽ cải tiến khả năng phân lớp của bộ lọc. 
Các email phân lớp sẵn sẽ được thêm vào đầu vào của hệ thống. Trong quá trình huấn luyện, các giá trị của các token được thay đổi theo thời gian trong từ điển token của bộ lọc để đạt được độ chính xác ngày càng cao hơn. 
III. CÁC PHƯƠNG THỨC HUẤN LUYỆN 
Có một yêu cầu cần chú ý là việc ‘học’ vẫn tiếp tục sau khi kết thúc huấn luyện, Việc huấn luyện sẽ tiếp tục bất cứ khi nào bộ lọc được sử dụng. 
Ngoài ra hiệu quả của bộ lọc còn tăng thêm bằng việc bổ sung thêm các thao tác cá nhân liên quan đến các yêu cầu sử dụng trong quá trình hoạt động của bộ lọc. 
III. CÁC PHƯƠNG THỨC HUẤN LUYỆN Huấn luyện với mọi thứ 
“Huấn luyện với mọi thứ” hay “học không được giám sát” : tất cả các token mới được thêm vào tập dữ liệu, các giá trị của các token được cập nhật sau khi mỗi email được xử lý. 
Giải pháp này cho phép thay đổi nhanh theo các đặc điểm của email, nhưng nó đòi hỏi nhiều tài nguyên để xử lý tất cả các token và các giá trị mỗi khi nhận được email. 
III. CÁC PHƯƠNG THỨC HUẤN LUYỆN Huấn luyện với các lỗi 
“Huấn luyện với các lỗi” : Theo ý tưởng là các giá trị thay đổi nhanh có thể dẫn tới nhiều lỗi hơn. Trong trường hợp này các giá trị của các token trong tập dữ liệu chỉ được sửa đổi khi một lỗi được chỉ ra bởi thông tin phản hồi của người sử dụng. 
Giải pháp này sử dụng đĩa cứng ít hơn đáng kể so với giải pháp “huấn luyện với mọi thứ”. Điểm yếu của phương thức học này là khó thích nghi nhanh với các đặc trưng mới. Ví dụ khi xuất hiện một kiểu spam mới có thể mất một khoảng thời gian cho tới khi nó được xử lý chính xác. 
III. CÁC PHƯƠNG THỨC HUẤN LUYỆN Huấn luyện cho tới khi thành thạo 
“Huấn luyện cho tới khi thành thạo” : giải pháp này kết hợp cả hai giải pháp trên. Nó sẽ “huấn luyện với mọi thứ” và sau khi nhận được đủ chi thức về thói quen của người sử dụng nó sẽ chỉ huấn luyện khi một lỗi xuất hiện như trong huấn “luyện với các lỗi”. 
Phương thức học kết hợp này cho ta lợi ích của cả hai giải pháp học ở trên, vấn đề duy nhất cần giải quyết là định nghĩa bộ lọc khi nào đủ tri thức để thay đổi phương thức học. 
IV. PHÂN LỚP EMAIL VÀ SỰ PHÂN LỚP SAI 
Một thư hợp lệ có thể bị phân lớp nhầm là thư spam và bị bỏ qua bởi người sử dụng. Như vậy, việc phân lớp nhầm một thư hợp lệ là một spam sẽ bất lợi hơn nhiều việc phân lớp nhầm một thư spam là thư hợp lệ, để giải quyết vấn đề này chúng ta cần tìm sự khác nhau trong các xác suất có thể của một thư là spam hay không là spam. 
Ta có công thức sau để tìm độ chính xác: 
	 Differrence = logP(spam = 1/mail)logP(spam = 0/mail) 
IV. PHÂN LỚP EMAIL VÀ SỰ PHÂN LỚP SAI 
Nếu ( Difference > threshold ) thì phân lớp email là spam, nếu không thì phân lớp email là hợp lệ. 
Ta chọn một giá trị threshold thích hợp để tránh việc phân lớp thư hợp lệ sai. Giá trị này có thể được tìm thấy sau nhiều thử nghiệm, ta có thể sử dụng threshold = 2, nghĩa là sự khác nhau giữa các khả năng sẽ lớn hơn 2 lần. 
Sử dụng các luật ở trên ta giảm được việc phân lớp nhầm, như vậy toàn bộ độ chính xác của hệ thống sẽ giảm theo một ý nghĩa nào đó. Do đó, việc cân bằng giữa các yếu tố là vô cùng cần thiết. 
V. HIỆN THỰC BỘ PHÂN LỚP SPAM BAYES 
Xây dựng một tập các thư spam và thư hợp lệ . 
Token hoá các thư spam và thư hợp lệ . 
Xây dựng danh sách tần số các token cùng các giá trị tương ứng. 
Xây dựng danh sách xác suất có khả năng là spam của token. 
Xây dựng lớp c_bayes_spam_filter . 
HẾT