NGHIÊN CỨU BỘ LỌC THƯ SPAM TRÊN CƠ SỞ MẠNG BAYES

Chia sẻ: Le Dang Son | Ngày: | Loại File: PPT | Số trang:35

Thêm vào BST

Báo xấu

189
lượt xem 25
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 bộ lọc thư spam trên cơ sở luật và dấu hiệu  Các 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ỹ • 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ị N1 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ị N2 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ừ so 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ể) xác suất có thể P( “thư là spam” | “các từ  Tính 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) Các token có được từ thư đến.  2a:  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 ) trước một tập huấn luyện S, chia S thành các  Cho 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ớix 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 ) thực tế, có thể sự phụ thuộc giữa hai biến  Trong đượ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).