zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Kỹ Thuật - Công Nghệ

» Kĩ thuật Viễn thông

Ứng dụng tối ưu hóa đa mục tiêu trong bài toán tự động phân loại thư rác

Chia sẻ: Wang Ziyi | Ngày: | Loại File: PDF | Số trang:6

Báo xấu

27
lượt xem 5
download

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

Bài báo trình bày một giải pháp cho vấn đề này dựa trên việc ứng dụng mô hình tối ưu hóa đa mục tiêu trong thiết kế các bộ lọc thư rác. Để đánh giá giải pháp, nhóm tác giả đã thực hiện thí nghiệm thiết kế các luật lọc thư rác cho phần mềm SpamAssassin sử dụng dữ liệu thư điện tử tiếng Việt. Kết quả thí nghiệm cho thấy phương pháp mới không chỉ cho kết quả tốt hơn so với các phương pháp hiện có mà còn cho phép đánh giá “sự thỏa hiệp” (tradeoff) giữa hai tỉ lệ nói trên khi thiết kế bộ lọc thư rác. Mời các bạn cùng tham khảo!

Chủ đề:

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

Lưu

Nội dung Text: Ứng dụng tối ưu hóa đa mục tiêu trong bài toán tự động phân loại thư rác

HộiHội Thảo Thảo Quốc Quốc Gia2015 Gia 2015về vềĐiện Điện Tử, Tử,Truyền Truyền Thông Thông và vàCông CôngNghệ NghệThông TinTin Thông (ECIT 2015) (ECIT 2015) Ứng dụng tối ưu hóa đa mục tiêu trong bài toán tự động phân loại thư rác Nguyễn Xuân Thắng1, Trần Quang Anh2 , Trịnh Bảo Ngọc1 và Nguyễn Thanh Hà2 1 : Đại học Hà Nội. Email: {nxthang, ngoctb}@hanu.edu.vn 2 : Học Viện Công Nghệ Bưu Chính Viễn Thông. Email: tqanh@ptit.edu.vn; thanhha140589@gmail.com Abstract— Một vấn đề còn tồn tại trong các hệ thống phân loại tự Hiện tại quy trình thiết kế bộ lọc thư rác theo phương pháp động thư rác dựa trên nội dung là làm sao để cân bằng giữa độ học máy gồm các bước như sau: chính xác phân loại thư rác và tỉ lệ chặn nhầm thư hợp lệ khi - Sử dụng các tập mẫu để huấn luyện bộ phân loại tự động. thiết kế các bộ lọc thư rác. Bài báo trình bày một giải pháp cho - Chọn một ngưỡng T dùng để xác định xem một thư mới có vấn đề này dựa trên việc ứng dụng mô hình tối ưu hóa đa mục phải là thư rác hay không. Thư mới được tách thành các tiêu trong thiết kế các bộ lọc thư rác. Để đánh giá giải pháp, nhóm tác giả đã thực hiện thí nghiệm thiết kế các luật lọc thư rác đặc trưng và so sánh với các đặc trưng đã được ghi nhận cho phần mềm SpamAssassin sử dụng dữ liệu thư điện tử tiếng bởi bộ huấn luyện. Nếu tổng trọng số của các đặc trưng Việt. Kết quả thí nghiệm cho thấy phương pháp mới không chỉ này lớn hơn giá trị T thì thư mới sẽ được phân loại là thư cho kết quả tốt hơn so với các phương pháp hiện có mà còn cho rác. phép đánh giá “sự thỏa hiệp” (tradeoff) giữa hai tỉ lệ nói trên khi - Tính toán các tham số SDR và FAR để đánh giá hiệu quả thiết kế bộ lọc thư rác. của bộ lọc. Theo quy trình trên giá trị của SDR và FAR phụ thuộc vào Keywords- Lọc thư rác, tối ưu hóa đa mục tiêu, giải thuật di ngưỡng T và trọng số của các đặc trưng. Để tìm ra bộ lọc có truyền, SpamAssassin. SDR và FAR phù hợp người dùng phải thử các giá trị T và I. GIỚI THIỆU trọng số khác nhau rồi lặp lại cả quy trình. Lưu ý là quá trình huấn luyện bộ phân loại thường rất tốn thời gian do tập mẫu Ngày nay, thư điện tử đã trở thành một công cụ đắc lực lớn. Hơn nữa, quy trình chưa hỗ trợ việc đánh giá “sự thỏa phục vụ cho nhu cầu trao đổi thông tin của các cơ quan, tổ hiệp” giữa SDR và FAR. chức, doanh nghiệp cũng như mỗi cá nhân. Tuy nhiên, thư điện Nhóm tác giả đề xuất giải pháp cho vấn đề trên bằng cách tử cũng đang bị lợi dụng để phát tán thư rác, lây lan virus máy coi yêu cầu thiết kế bộ lọc thư rác là một bài toán tối ưu hóa đa tính và lừa đảo trực tuyến, gây thiệt hại lớn cho người sử dụng. mục tiêu trong đó ta cần tìm giá trị ngưỡng T và các trọng số Nhiều giải pháp đã được đưa ra để đối phó với vấn nạn thư rác, của mỗi đặc trưng sao cho tham số SDR và FAR của bộ lọc thư trong đó đáng kể nhất là các giải pháp tự động phân loại thư rác là tối ưu. Giải pháp này được áp dụng để thiết kế bộ lọc thư rác dựa trên nội dung thông qua học máy. Phương pháp này rác trên nền tảng phần mềm SpamAssassin [1] với các đặc cần có hai tập mẫu riêng biệt chứa các thư rác và các thư hợp lệ trưng được trích chọn là các luật và trọng số của mỗi đặc trưng đã được phân loại chính xác từ trước. Từ các tập mẫu này, một là điểm của luật tương ứng. Do đặc thù của bài toán tối ưu đa thuật toán học máy được sử dụng để trích chọn các đặc trưng mục tiêu được mô tả trong bài báo là có không gian tìm kiếm nội dung (thường là từ hoặc cụm từ) của thư rác, đánh trọng số lớn và nhiều chiều nên nhóm tác giả đề xuất sử dụng giải thuật cho các đặc trưng và huấn luyện bộ phân loại tự động cho phép tiến hóa đa mục tiêu (multi-objective evolutionary algorithm – phân loại các thư mới chưa xuất hiện trong hai tập mẫu. Ưu MOEA) [9], cụ thể là giải thuật SPEA-II [10,11], để giải bài điểm của các giải pháp này là có tính linh hoạt và có hiệu quả toán này. Tuy SPEA-II không cho ra lời giải chính xác nhất, cao. nhưng giải thuật này cho kết quả là tập các phương án thỏa Để đánh giá hiệu quả của một bộ lọc thư rác người ta thường sử dụng hai tham số chính là độ chính xác phân loại thư hiệp (hay còn gọi là tập phương án tối ưu Pareto) [12]. Từ đó, rác (Spam Detection Rate – SDR) và tỉ lệ chặn nhầm thư hợp lệ kết hợp thêm các tiêu chí khác, ta chọn được lời giải tốt nhất (False Alarm Rate – FAR). Trong đó, SDR là tỉ số giữa số thư cho bài toán. So sánh với các giải pháp hiện tại, giải pháp do rác mà bộ lọc phân loại được và tổng số thư rác đầu vào còn nhóm tác giả đề xuất có hai ưu điểm như sau: FAR là tỉ lệ giữa số thư hợp lệ bị bộ lọc phân loại nhầm là thư - Tìm được các bộ giá trị khác nhau của ngưỡng T và điểm rác và tổng số thư hợp lệ đầu vào. Một bộ lọc thư rác lý tưởng của mỗi luật để xây dựng bộ lọc thư rác có tham số SDR sẽ có tỉ lệ SDR và FAR lần lượt là 100% và 0%. Tuy nhiên các và FAR phù hợp với yêu cầu của người dùng mà không quan sát thực tế trong quá trình xây dựng các bộ lọc thư rác cho tốn thời gian huấn luyện lại bộ phân loại tự động. thấy các điều chỉnh để tăng tỉ lệ SDR cũng đồng thời làm tăng - Đưa ra tập nghiệm “thỏa hiệp” giữa các hai mục tiêu đem tỉ lệ FAR và ngược lại việc giảm tỉ lệ FAR sẽ kéo theo giảm tỉ lại sự lựa chọn dễ dàng hơn cho người dùng khi phải cân lệ SDR. Do đó vấn đề đặt ra khi thiết kế các bộ lọc thư rác là nhắc giữa SDR và FAR. cân nhắc “sự thỏa hiệp” (tradeoff) giữa hai tham số SDR và Phần còn lại của bài báo được tổ chức như sau: phần II FAR để tìm ra giải pháp phù hợp cho mỗi tình huống cụ thể. trình bày về hệ thống lọc thư rác SpamAssassin. Phần III phát ISBN: 978-604-67-0635-9 30 30
HộiHội Thảo Quốc Thảo Gia Quốc Gia2015 2015về vềĐiện Điện Tử, Tử,Truyền Truyền Thông vàCông Thông và CôngNghệ Nghệ Thông Thông TinTin (ECIT (ECIT 2015) 2015) biểu bài toán và đề xuất phương pháp giải. Phần IV trình bày cho tham số SDR của bộ lọc là lớn nhất khi tiến hành phân loại các kết quả thí nghiệm và đánh giá hiệu quả của giải pháp. các thư trong tập huấn luyện. Phần V tóm tắt các kết quả nghiên cứu liên quan đến chủ đề Đối chiếu với các bước của giải pháp tự động phân loại thư trình bày trong bài báo. Cuối cùng, các kết luận được trình bày rác dựa trên nội dung thông qua học máy đã mô tả ở phần I thì trong phần VI. giai đoạn một thực hiện việc trích trọn đặc trưng của thư rác thể hiện ở mỗi luật trong tập luật, còn giai đoạn hai thực hiện II. BỘ LỌC SPAMASSASSIN xác định trọng số của các đặc trưng này thể hiện ở điểm số của SpamAssassin là một hệ thống lọc thư rác được sử dụng mỗi luật. Dễ thấy khi xây dựng bộ lọc thư rác trên nền tảng khá phổ biến do Apache Foundation phát triển. SpamAssassin SpamAssassin, điểm số của các luật có ảnh hướng lớn đến hiệu phân loại thư rác dựa trên một tập các luật đã được định nghĩa quả của bộ lọc vì điểm số của luật thể hiện độ quan trọng của sẵn. Mỗi luật được gán một điểm số cho trước. Trong quá trình luật đó trong quá trình phân loại thư. Xác định điểm số cho các lọc thư rác, tập luật này sẽ được áp dụng một cách tuần tự trên luật càng chính xác thì hiệu quả của bộ lọc thư rác càng cao và mỗi thư cần phân loại để chấm điểm. Khi tổng số điểm của một ngược lại. thư vượt quá ngưỡng cho trước thì thư này sẽ bị phân loại là Gọi SDR0 và FAR0 là các giá trị mong muốn của hai tham thư rác. Một ví dụ về luật dùng trong Spamassassin được mô tả số SDR và FAR của bộ lọc thư rác cần thiết kế (với ý nghĩa bộ trong danh sách (1): lọc đạt yêu cầu là bộ lọc có SDR ≥ SRD0 và FAR ≤ FAR0). Trong phương pháp xác định điểm số hiện tại, sau khi xác định Body DEAR_FRIEND /^\s*Dear Friend\b/i ngưỡng T, điểm số của mỗi luật sẽ được tính toán để cho tham Describe DEAR_FRIEND Dear Friend? That’s not very dear số SDR của bộ lọc thu được là lớn nhất. Tuy nhiên các khả Score DEAR_FRIEND 0.542 năng sau có thể xảy ra sau khi thực thi xong thuật toán tính Danh sách 1: Ví dụ một luật trong SpamAssassin điểm số: (1) Giá trị SDR của bộ lọc thu được không đạt yêu cầu Ví dụ trên định nghĩa một luật có tên DEAR_FRIEND, khi (2) Giá trị FAR của bộ lọc thu được không đạt yêu cầu SpamAssassin áp dụng luật này trên một thư cần phân loại, (3) Giá trị SDR và FAR đạt yêu cầu nhưng chưa phải là tối ưu phần mềm sẽ kiểm tra xem thư có chứa mẫu chuỗi ký tự được Để giải quyết vấn đề trên người dùng phải thử chọn các giá trị quy định trong biểu thức chính quy /^\s*Dear Friend\b/i hay ngưỡng T khác, thực hiện lại thuật toán tính điểm và tiếp tục không. Nếu thư có chứa chuỗi này thì số điểm 0.542 sẽ được kiểm tra xem các tham số SDR và FAR của bộ lọc đã đạt yêu cộng vào tổng điểm số dùng để phân loại thư. Cấu trúc cụ thể cầu chưa. Quy trình này không chỉ gây tốn thời gian, tốn tài của luật dùng trong SpamAssassin được trình bày cụ thể trong nguyên hệ thống mà còn chưa giải quyết triệt để vấn đề (3) do [1,3]. Một tập các luật như vậy cùng với điểm số của chúng sẽ chưa xem xét đến giá trị của FAR trong quá trình tính điểm. tạo thành một bộ lọc thư rác trên nền SpamAssassin. Từ những phân tích nêu trên, nhóm tác giả đề xuất giải pháp Quá trình xây dựng một bộ lọc thư rác cho SpamAssassin coi bài toán xác định điểm cho các luật lọc thư rác là một bài được chia thành hai giai đoạn: xác định nội dung của các luật toán tối ưu hóa đa mục tiêu trong đó ta cần tìm giá trị ngưỡng (các mẫu chuỗi ký tự dùng trong biểu thức chính quy) và gán T và các giá trị điểm số của mỗi luật sao cho giá trị tham số điểm số cho mỗi luật. Ở giai đoạn thứ nhất căn cứ vào hai tập SDR và FAR của bộ lọc thu được là tối ưu. Lưu ý rằng do mối mẫu cho trước các đặc trưng của thư rác (từ hoặc cụm từ) được quan hệ “thỏa hiệp” giữa SDR và FAR như đã nêu trong phần I trích chọn để hình thành nên nội dung của các luật của bộ lọc. nên sẽ rất khó tìm được một bộ giá trị của T và các điểm số sao Mỗi luật tương ứng với một từ hoặc cụm từ đặc trưng của thư cho SDR và FAR thực sự tối ưu (SDR=100% và FAR=0%), rác. Dễ thấy nội dung của các luật sẽ phụ thuộc vào loại ngôn thay vào đó nhóm tác giả hướng tới việc tìm ra tập các phương ngữ sử dụng trong các thư ở tập mẫu, do đó sẽ có các luật khác án thỏa hiệp (hay còn gọi là tập phương án tối ưu Pareto) [12]. nhau dành riêng cho lọc thư rác tiếng Anh và lọc thư rác tiếng Từ đó, kết hợp thêm các tiêu chí khác, ta chọn được lời giải tốt Việt. Trong các nghiên cứu trước đây[2,5,6], nhóm tác giả đã nhất cho bài toán. trình bày cụ thể về vấn đề xây dựng các luật lọc thư rác tiếng Việt và thư rác đa ngôn ngữ. Bài báo này sử dụng các kết quả III. PHÁT BIỂU BÀI TOÁN VÀ PHƯƠNG PHÁP GIẢI tập luật lọc thư rác thu được từ các nghiên cứu đó. A. PHÁT BIỂU BÀI TOÁN Ở giai đoạn thứ hai điểm số được gán cho mỗi luật, quá Giả sử tập mẫu ban đầu bao gồm tập thư rác S=(s1, s2, …, trình này có ý nghĩa tương tương với việc gán trọng số cho mỗi sK) và tập thư hợp lệ H=(h1, h2, …, hL). Giả sử bộ lọc thư rác đặc trưng đã được trích chọn. Hiện tại SpamAssassin sử dụng cần xây dựng bao gồm tập luật R=(r1, r2, …, rN), mỗi luật cần một thuật toán học máy trên nền tảng mạng neural một được xác định điểm tương ứng là một phần tử trong tập điểm lớp[2,3]. Trong đó mỗi nút mạng mô tả một luật, mỗi đầu vào X=(x1, x2, …, xN). Với mỗi luật r và mỗi thư điện tử e ta có thể của mỗi nút thể hiện luật đó có xuất hiện trong một thư rác, xác định hàm so khớp m(r,e) như sau: trọng số của mỗi nút là điểm của luật. Sau khi kết thúc quá trình huấn luyện toàn bộ tập luật sẽ được gán một điểm số tương ứng. Về cơ bản quá trình này có thể mô hình hóa dưới 1 nếu đặc trưng r xuất hiện trong e mr,e=  (1) dạng một bài toán tối ưu hóa đơn mục tiêu, với một ngưỡng T 0 ngược lại cho trước quá trình huấn luyện sẽ gán điểm cho mỗi luật sao Tiếp theo tổng điểm của thư điện tử e được tính theo công thức sau: 31 31
HộiHội Thảo Quốc Thảo Gia Quốc 2015 Gia 2015về vềĐiện ĐiệnTử, Tử,Truyền TruyềnThông và Công Thông và CôngNghệ NghệThông ThôngTinTin (ECIT (ECIT 2015) 2015) N thể của tập tối ưu Pareto, một tập các phương án như vậy được Scoree=  m(ri ,e)xi (2) gọi là tập Pareto được biết tốt nhất (Best-known Pareto set). i=1 Ba tiêu chí sau đây thường được dùng để đánh giá một tập Pareto được biết tốt nhất: Với mỗi giá trị ngưỡng T xác định, bộ lọc SpamAssassin sẽ kết - Là một tập con của tập tối ưu Pareto. luận e là thư rác hay thư hợp lệ dựa trên công thức: - Các giá trị của hàm mục tiêu tương ứng của các phương án phải phân bố đều và đa dạng trên đường biên Pareto trong 1 nếu Score(e) ≥ T không gian mục tiêu. Spame=  (3) 0 ngược lại - Các giá trị của hàm mục tiêu tương ứng phải biểu thị toàn Từ đó các tham số SDR và FAR của bộ lọc thư rác được tính cảnh của đường biên Pareto. theo các công thức: K C. CÁC GIẢI THUẬT TIẾN HÓA ĐA MỤC TIÊU 1 SDR=  Spam(si ) (4) Với cách tiếp cận nói trên, việc giải bài toán tối ưu hóa đa K mục tiêu được thực hiện thông qua quá trình tìm kiếm tập i=1 Pareto được biết tốt nhất. Do đó các giải thuật tìm kiếm meta- L heuristic mà cụ thể là các giải thuật tiến hóa sẽ là các công cụ 1 FAR=  Spam(hi ) (5) đặc biệt phù hợp để giải quyết lớp bài toán này. Thực tế các L giải thuật tiến hóa đa mục tiêu như NSGA hay SPEA có thể i=1 thực hiện tìm kiếm tập Pareto được biết tốt nhất chỉ trong một Do bản thân giá trị ngưỡng T cũng là một biến số nên ta sử lượt chạy. Theo thống kê trong [13], các giải thuật tiến hóa dụng x0 để ký hiệu thay cho T. Cuối cùng bài toán tối ưu hóa chiếm 70% trong tổng số các phương pháp tối ưu hóa đa mục đa mục tiêu được phát biểu như sau: tiêu dựa trên meta-heuristic. Đã có nhiều giải thuật tiến hóa đa mục tiêu (MOEA) được z1 = SDR(X)  Max công bố, trong [14] các tác giả trình bày tổng quan về các giải z2 = FAR(X)  Min, X=(xo, x1, …, xN) ∈ RN+1 thuật này. Điểm khác biệt chủ yếu giữa các giải thuật tiến hóa với các ràng buộc: ximin ≤xi ≤ximax ; i0...N (6) đa mục tiêu nằm ở cách tính độ thích nghi cho mỗi cá thể (Fitness assignment), cách duy trì quần thể ưu tú (Elitism) và Trong đó các giá trị SDR(X) và FAR(X) được tính theo các phương pháp để đa dạng hóa quần thể. công thức (4) và (5). Các giá trị ximin và ximax thể hiện khoảng Xếp hạng Pareto (Pareto ranking) là một phương pháp giá trị cho phép của biến xi. thường dùng để tính độ thích nghi của cá thể bằng cách gán thứ hạng 1 (độ thích nghi cao nhất) cho các cá thể không bị vượt B. TỐI ƯU HÓA PARETO trội trong quần thể và loại chúng ra khỏi danh sách xếp hạng, Thực tế hai mục tiêu của bài toán tối ưu hóa (6) không thể rồi tìm các cá thể không bị vượt trội mới để gán thứ hạng 2 và đạt được đồng thời, do đó phương pháp tối ưu hóa Pareto [12] tiếp tục như vậy cho đến khi toàn bộ quần thể được xếp hạng. được áp dụng để giải bài toán. Ta xem xét bài toán tối ưu hóa Duy trì quần thể ưu tú là một vấn đề quan trọng trong tối ưu đa mục tiêu tổng quát với yêu cầu phải đồng thời tối thiểu hóa hóa đa mục tiêu sử dụng MOEA. Trong ngữ cảnh của giải thuật P hàm mục tiêu – các mục tiêu loại tối đa hóa có thể được MOEA, tất cả những cá thể không bị vượt trội được phát hiện chuyển thành loại tối thiểu hóa bằng cách nhân với -1: bởi MOEA được coi như là những thành viên của quần thể ưu tú. Có hai chiến lược thường dùng để hiện thực việc duy trì zi = fi(X)  Min, X=(x1, x2, …, xN) ∈ RN , i=1, 2, … P (P≥2) quần thể ưu tú: (i) lưu trữ các cá thể ưu tú trong chính quần thể với các ràng buộc: g j X ; j=1...m và (ii) lưu trữ các cá thể ưu tú trong một danh sách thứ cấp bên ngoài quần thể và đưa chúng trở lại quần thể. Một phương án khả thi X được gọi là vượt trội so với phương Phương pháp chia sẻ độ thích nghi (Fitness sharing) được án khả thi Y (ký hiệu X ≽ Y), nếu và chỉ nếu, zi(X) ≤ zi(Y) dùng để đa dạng hóa quần thể. Phương pháp này khuyến khích (i=1, ... , P) và zj(X) < zj(Y) ở ít nhất một mục tiêu j. Một tìm kiếm trên những vùng chưa biết của đường biên Pareto phương án được gọi là phương án tối ưu Pareto nếu nó không bằng cách giảm bớt độ thích nghi của các cá thể ở những vùng bị vượt trội bởi bất cứ phương án nào khác trong không gian có mật độ cao. Các kỹ thuật khác nhau thường được dùng để phương án {X}. Các giá trị hàm mục tiêu tương ứng của các ước lượng mật độ các cá thể xung quanh một cá thể đang xét phần tử trong tập các phương án tối ưu Pareto nói trên tạo như kỹ thuật đếm số vùng lân cận (niche count) hay kỹ thuật thành đương biên Pareto (Pareto Front) trong không gian mục tính khoảng cách mật độ trong đó ước tính giá trị khoảng cách tiêu. Euclide trung bình trong không gian mục tiêu của cá thể đang Các giải thuật tối ưu hóa đa mục tiêu lý tưởng sẽ tìm ra tất xét tới các láng giềng gần nhất thứ k (k-th nearest neighbor) cả các phương án trong tập tối ưu Pareto. Tuy nhiên việc chứng của nó. Khoảng cách mật độ cũng được dùng trong cơ chế minh một tập hợp các phương án tìm được là tập tối ưu Pareto chọn cha mẹ như sau: lấy ngẫu nhiên hai cá thể x và y; nếu thường không khả thi. Do đó một cách tiếp cận thực tế thường chúng có cùng thứ tự (non-domination rank) thì cá thể nào có được chọn là tìm kiếm tập các phương án là thể hiện tốt nhất có 32 32
HộiHội Thảo Quốc Thảo QuốcGia Gia2015 2015về về Điện Tử, Truyền Điện Tử, ThôngvàvàCông Truyền Thông CôngNghệ Nghệ Thông Thông Tin Tin (ECIT (ECIT 2015) 2015) khoảng cách mật độ cao hơn sẽ được chọn; ngược lại cá thể có tập kiểm tra. Tập mẫu được dùng trong quá trình tìm kiếm bộ mức thứ tự thấp hơn sẽ được chọn. lọc có các tham số SDR và FAR tối ưu, còn tập kiểm tra được dùng để đánh giá bộ lọc khi hoạt động thực tế. Cả tập mẫu và D. SỬ DỤNG MOEA ĐỂ GIẢI BÀI TOÁN tập kiểm tra đều chứa các thư rác và các thư hợp lệ. Bảng 1 mô Nhóm tác giả lựa chọn giải thuật tiến hóa đa mục tiêu SPEA-II tả số lượng thư cụ thể dùng trong mỗi kịch bản. để giải bài toán. Trong phần tiếp theo chúng tôi mô tả một số điểm chính trong quá trình sử dụng SPEA-II để giải bài toán. Kịch bản 1 (300 thư) Kịch bản 2 (750 thư) Biểu diễn nhiễm sắc thể: Bài toán yêu cầu tìm kiếm giá trị Mẫu Kiểm tra Mẫu Kiểm tra ngưỡng T và điểm cho từng luật có trong bộ lọc thư rác Thư rác 120 60 300 150 SpamAssassin sao cho các tham số SDR và FAR của bộ lọc Thư hợp lệ 80 40 200 100 thu được là tốt nhất. Do đó mỗi nhiễm sắc thể sẽ biểu diễn một Bảng 1: Số lượng thư điện tử dùng trong các kịch bản phương án khả thi để gán giá trị cho ngưỡng T và các luật có trong bộ lọc. Cụ thể mỗi nhiễm sắc thể sẽ là một vecto chứa Trong mỗi kịch bản thử nghiệm chúng tôi thực hiện thiết kế N+1 số thực (các gen) tương ứng với một phương án X=(xo, x1, bộ lọc gồm 30 luật và 100 luật để đảm bảo các thực nghiệm …, xN) ∈ RN+1 trong không gian phương án. Giá trị của mỗi xi được thực hiện với số lượng thư và số lượng luật ở quy mô nhỏ phải nằm trong ngưỡng cho phép ximin ≤xi ≤ximax đã xác định và quy mô lớn. Dải giá trị hợp lệ được chọn cho ngưỡng T là trước. Phương pháp mã hóa số thực (real-coded method) [14] [0,5]; cho điểm của mỗi luật là [0,2]. Thuật toán SPEA-II được được chúng tôi sử dụng để biểu diễn mỗi nhiễm sắc thể. cài đặt để tính điểm cho mỗi luật có trong bộ lọc, các tham số Tính toán giá trị hàm mục tiêu: Giá trị hàm mục tiêu của mỗi của SPEA-II được mô tả trong bảng 2 (N có giá trị lần lượt là nhiễm sắc thể được tính toán thông qua phần mềm 30 và 100). SpamAssassin. Bộ lọc SpamAssassin tương ứng với nhiễm sắc thể sẽ được sử dụng để kiểm tra các thư có trong tập mẫu bao Tham số Giá trị Tham số Giá trị gồm tập thư rác S và tập thư hợp lệ H. Từ kết quả kiểm tra ta Kích thước quần thể 100 Cận dưới của 0 có thể tính được các tham số SDR và FAR của bộ lọc và từ đó biến N+1 xác định được các giá trị hàm mục tiêu của nhiễm sắc thể. Lưu Số lượng thế hệ 1000 Cận trên của 2 ý để cho đơn giản ta chọn giá trị hàm mục tiêu 1-SDR thay vì biến N+1 SDR, như thế mục tiêu của bài toán sẽ là tối tiểu hóa hai hàm Số mục tiêu 2 Xác suất lai tạo 0,9 mục tiêu FAR và 1-SDR. Số biến thực N+1 Xác suất đột biến 1/(N+1) Cơ chế chọn lọc: Được được dùng để chọn các nhiễm sắc thể Cận dưới của biến 1 0 cha mẹ cho việc sinh ra thế hệ tiếp theo. Chúng tôi sử dụng cơ chế chọn lọc dựa trên đấu loại trực tiếp (Binary Tournament Cận trên của biến 1 5 Bảng 2: Các tham số của thuật toán SPEA-II Selection) trong đó hai nhiễm sắc thể được chọn ngẫu nhiên từ quần thể để tham gia đấu loại, nhiễm sắc thể nào có giá trị hàm Các thử nghiệm được chạy trên máy tính có cấu hình Intel thích nghi tốt hơn sẽ là người chiến thắng. Core i3-3120M 2.5GHz, RAM 4GB, OS Ubuntu 14.04. Để Phép toán lai tạo (Crossover operator): Hai nhiễm sắc thể cha đảm bảo tính khách quan mỗi thử nghiệm được chạy 20 lần với mẹ được chọn sẽ tạo ra hai nhiễm sắc thể con mới cho quần các nhân ngẫu nhiên khác nhau, các số liệu trình bày trong bài thể. Chúng tôi sử dụng phép toán lai tạo giả nhị phân báo là giá trị trung bình của kết quả thu được sau mỗi lần chạy. (Simulated Binary Crossover) để thực hiện quá trình này. Kết quả thử nghiệm được so sánh với phương pháp tính điểm Phép toán đột biến (Mutation operator): Chúng tôi chọn phép tối ưu hóa đơn mục tiêu (SOOA) [2] của SpamAssassin trên đột biến đa thức (polynomial mutation operator) để biến đổi cùng mẫu dữ liệu thư điện tử. Để thực hiện so sánh, chúng tôi nhiễm sắc thể nhằm tăng tính đa dạng của quần thể. chọn 10 giá trị ngưỡng T phân bố đều trong khoảng [0,5], với Gán độ thích nghi: Phương pháp xếp hạng Pareto được dùng mỗi giá trị ngưỡng phương pháp tính điểm hiện tại sẽ tính toán để gán độ thích nghi cho mỗi nhiễm sắc thể có trong quần thể. điểm của các luật để tối ưu hóa tham số SDR, giá trị của tham Duy trình quần thể ưu tú: SPEA-II sử dụng một danh sách thứ số FAR của bộ lọc cũng được tính toán và so sánh với phương cấp để lưu trữ các nhiễm sắc thể ưu tú (là các phương án không pháp đề xuất trong bài báo. bị vượt trội như mô tả trong phương pháp tối ưu Pareto) của Các kết quả thử nghiệm theo kịch bản thứ nhất (với tập quần thể. Danh sách này sẽ được đưa lại vào quần thể trong chứa 300 thư) được trình bày trong hình 1 (bộ lọc có 30 luật) quá trình chọn lọc. và hình 2 (bộ lọc có 100 luật). Các kết quả thu được khi thiết Chia sẻ độ thích nghi: Sử dụng kỹ thuật tính khoảng cách mật kế bộ lọc bằng phương pháp SOOA cũng được trình bày trong độ đã trình bày ở phần trên. các hình vẽ này để tiện so sánh. Các số liệu cho thấy bộ lọc thiết kế sử dụng SPEA-II có các tham số SDR và FAR tốt hơn IV. KẾT QUẢ so với bộ lọc thiết kế bằng phương pháp SOOA. Cụ thể đối với bộ lọc có 30 luật, giả sử ta muốn thiết kế bộ lọc có FAR = 0%, Nhóm tác giả thử nghiệm xây dựng bộ lọc thư rác thì kết quả tốt nhất mà phương pháp SOOA tìm được là SpamAssassin với hai kịch bản sử dụng hai cơ sở dữ liệu thư (SDR=40,8%, FAR=0%). Trong khi đó sử dụng SPEA-II ta thu điện tử khác nhau chứa 300 thư và 750 thư do nhóm tác giả thu được bộ lọc có (SDR=60%, FAR=0%). Tương tự nếu ta chỉ thập từ nhiều nguồn khác nhau. Trong mỗi kịch bản, tập thư quan tâm đến những bộ lọc có FAR ≤ 10% thì các kết quả tốt điện tử ban đầu được chia thành hai tập con gọi là tập mẫu và 33 33
HộiHội Thảo Quốc Thảo Gia Quốc 2015 Gia 2015về vềĐiện ĐiệnTử, Tử,Truyền TruyềnThông và Công Thông và CôngNghệ NghệThông ThôngTinTin (ECIT (ECIT 2015) 2015) nhất mà SOOA tìm được là (67,7%, 10%) và (55,8%, 1,25%) tích kỹ hơn số liệu trình bày trong bảng 3 ta thấy khi bộ lọc trong khi SPEA-II tìm ra những kết quả tốt hơn như (60%, chứa nhiều luật hơn thì SPEA-II cũng tìm được những kết quả 0%), (64,2%, 1,3%) và (68,3%, 5%). tốt hơn. Điều này thể hiện ở số lượng điểm tìm được trong tập đường biên Pareto (18 điểm và 31 điểm ứng với các trường hợp sử dụng 30 luật và 100 luật) và giá trị trung bình của khoảng cách D (51,3 và 47 ứng với các trường hợp sử dụng 30 luật và 100 luật). Phương pháp SOOA Bộ lọc 30 luật Bộ lọc 100 luật Thiết kế Thực tế Thiết kế Thực tế SDR FAR SDR FAR SDR FAR SDR FAR 1 67,7 10,0 65,0 12,5 81,3 15 81,7 17,5 2 55,8 1,25 56,7 2,5 78,3 12,5 78,3 12,5 3 40,8 0 45,0 2,5 68,3 3,8 66,7 5,0 Phương pháp SPEA-II Bộ lọc 30 luật Bộ lọc 100 luật Thiết kế Thực tế Thiết kế Thực tế SDR FAR SDR FAR SDR FAR SDR FAR 1 72,5 12,5 71,7 12,5 82,5 13,8 83,3 15,0 Hình 1. Kết quả kịch bản thử nghiệm 1 với bộ lọc 30 luật 2 71,0 10,0 71,7 10,0 80,8 12,5 80,0 12,5 3 73,3 16,3 73,3 17,5 80,0 11,3 80,0 10,0 Bảng 3: So sánh kết quả thu được khi sử dụng hai phương pháp SSOA và SPEA-II trong kịch bản 1 Các kết quả thu được khi thử nghiệm theo kịch bản thứ hai với số lượng thư mẫu lớn hơn cũng cho thấy các kết luận tương tự như trong kịch bản thứ nhất: - SPEA-II cho các kết quả tốt hơn so với SOOA trên cả hai phương diện tối ưu hóa FAR hay SDR. - SPEA-II cho phép người dùng lựa chọn các thiết kế phù hợp nhất căn cứ vào đường biên Pareto tìm được. - Với bộ lọc sử dụng nhiều luật hơn thì SPEA-II tìm được các kết quả tốt hơn. Hình 3 và 4 mô tả kết quả thử ngiệm theo kịch bản thứ hai khi sử dụng bộ lọc có 30 luật và 100 luật. Bảng 4 tóm tắt các kết quả tốt nhất do SOOA và SPEA-II tìm ra trong thực nghiệm. Hình 2. Kết quả kịch bản thử nghiệm 1 với bộ lọc 100 luật Khi tăng số luật của bộ lọc lên thành 100 luật ta cũng thu được các kết quả tương tự. Phương pháp SPEA-II cho kết quả tốt hơn SOOA trên cả hai phương diện tối ưu hóa riêng FAR hoặc SDR. Hơn nữa bằng việc khảo sát đường biên Pareto, người dùng có thể cân nhắc việc đánh đổi giữa SDR và FAR để từ đó tìm được giải pháp phù hợp với yêu cầu. Trên mặt phẳng tọa độ Đề-các tạo bởi hai trục SDR và FAR, dễ thấy bộ lọc lý tưởng tương ứng với điểm có tọa độ I(100,0). Gọi D là khoảng cách Euclide từ một điểm trên đường biên Pareto đến điểm I, khi đó giá trị của D sẽ cho ta thông tin ước lượng tương đối về chất lượng của bộ lọc thu được (D càng nhỏ thì chất lượng bộ lọc càng cao). Bảng 3 trình bày 03 bộ lọc tốt nhất do SPEA-II tìm được và so sánh chúng với phương pháp SOOA. Các số liệu về SDR và FAD khi thiết kế (sử dụng tập thư mẫu) và khi hoạt động thực tế (sử dụng tập thư kiểm tra) cũng được trình bày trong bảng 3. Phân Hình 3. Kết quả kịch bản thử nghiệm 2 với bộ lọc 30 luật 34 34
Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015) Hội Thảo Quốc Gia 2015 về Điện Tử, Truyền Thông và Công Nghệ Thông Tin (ECIT 2015) . VI. KẾT LUẬN Trong bài báo này, chúng tôi đề xuất phương pháp mới để tính điểm cho các luật trong quá trình thiết kế bộ lọc thư rác SpamAssassin. Trong đó việc gán điểm cho mỗi luật được thực hiện thông qua giải bài toán tối ưu hóa đa mục tiêu đồng thời tối đa hóa tham số SDR và tối thiểu hóa tham số FAR của bộ lọc. So sánh với phương pháp cũ, phương pháp mới có ưu điểm hơn vì nó không những tìm ra những kết quả tốt hơn mà còn cho phép người dùng lựa chọn những kết quả “thỏa hiệp” theo các tiêu chí cho trước. Các thực nghiệm cũng được tiến hành với các kích thước khác nhau của tập thư điện tử mẫu và tập luật dùng trong bộ lọc. Kết quả thực ngiệm đã minh chứng rõ các kết luận trình bày trong bài báo. Hình 4. Kết quả kịch bản thử nghiệm 2 với bộ lọc 100 luật TÀI LIỆU THAM KHẢO [1] The Apache SpamAssassin Project. SpamAssassin: The Powerful #1 Phương pháp SOOA Open-Source Spam Filter. [Online] 2015. [Cited: 16 July 2015] http://spamassassin.apache.org/index.html Bộ lọc 30 luật Bộ lọc 100 luật [2] Tran, Q. A., Duan, H. X. Li, X., “Real-time statistical rules for spam Thiết kế Thực tế Thiết kế Thực tế detection”, IJCSNS International Journal of Computer Science and SDR FAR SDR FAR SDR FAR SDR FAR Network Security, VOL.6 No.2B, pp 178–184, 2006. 1 79,0 15,5 78,7 15,0 75,7 4,0 75,0 5,0 [3] Schwartz A. SpamAssassin. O’Reilly, 2004. 2 81,3 19,0 81,3 19,0 84,3 20,0 84,5 21,0 [4] Joseph S. Kong, Behnam Attaran Rezaei, Nima Sarshar, Vwani P. Roychowdhury, P. Oscar Boykin, “Collaborative Spam Filtering Using 3 74,7 8,5 74,7 9,0 78,3 14,0 78,5 14,0 E-Mail Networks”. IEEE Computer 39(8): 67-73, 2006. Phương pháp SPEA-II [5] Minh Tuan Vu and F. Jiang V.Q. Tran Tran, Quang Anh, “Multilingual Bộ lọc 30 luật Bộ lọc 100 luật rules for spam detection”. Proceedings of IB2COM 2012, pages 106– Thiết kế Thực tế Thiết kế Thực tế 110, 2012. SDR FAR SDR FAR SDR FAR SDR FAR [6] Nguyen T.A., Tran Q.A., Nguyen N.B., “Vietnamese spam detection 1 79,3 11,0 79,3 11,0 83,3 10,0 83,3 10,0 based on language classification”, HUT-ICCE 2008 - 2nd International 2 77,3 9,0 77,3 9,0 78,3 6,0 78,7 6,0 Conference on Communications and Electronics, 2008. 3 76,3 7,5 76,7 8,0 81,7 13,5 82,0 14,0 [7] V. Fernandes, I. Yevseyeva, R. Frantz, C. Grilo, N. Díaz, M. Emmerich, Bảng 3: So sánh kết quả thu được khi sử dụng hai phương pháp SSOA “An Automatic Generation of Textual Pattern Rules for Digital Content Filters Proposal, Using Grammatical Evolution Genetic Programming”, và SPEA-II trong kịch bản 2 Procedia Technology, Volume 16, Pages 806-812, 2014. V. CÁC NGHIÊN CỨU LIÊN QUAN [8] I. Yevseyeva, V. Fernandes, D. Ord´as, J. M´endez “Optimising anti- spam filters with evolutionary algorithms”. Expert Systems with Cho tới nay đã có nhiều công trình nghiên cứu liên quan Applications, 2013. đến vấn đề lọc thư rác như sử dụng các bộ lọc địa chỉ thư, các [9] C. A. C. Coello, “Evolutionary multi-objective optimization: A bộ lọc nội dung sử dụng Bayesian hoặc SVM, sử dụng phương historical view of the field”. IEEE Computational Intelligence Magazine, 1(1):28–36, 2006. pháp học máy [3], sử dụng mạng phức hợp [4]. Trong vấn đề [10] E. Zitzler, L. Thiele, and K. Deb, “Comparision of multiobjective phân loại thư rác dựa trên nội dung, ngôn ngữ sử dụng trong evolutionary algorithms: Emprical results”. Evolutionary Computation, thư điện tử có vai trò rất quan trọng. Nhóm tác giả đã xuất bản 8(1):173–195, 2000. một số công trình nghiên cứu liên quan đến việc xây dựng các [11] E. Zitzler, M. Laumanns, and L. Thiele, “SPEA2: Improving the bộ lọc thư rác cho từng loại ngôn ngữ (tiếng Trung [2], tiếng strength pareto evolutionary algorithm for multiobjective optimization”. In Evolutionary Methods for Design Optimization and Control with Việt [6]) cũng như thiết kế các luật lọc thư đa ngôn ngữ [5]. Applications to Industrial Problems, pp. 95–100, 2001. Trong phần lớn các nghiên cứu hiện tại, việc tính điểm cho [12] Marler, R.T. and J.S. Arora, “Survey of multi-objective optimization các luật dùng trong bộ lọc SpamAssassin được thực hiện thông methods for engineering”. Structural and Multidisciplinary qua việc giải bài toán tối ưu hóa đơn mục tiêu sử dụng giải Optimization, 26(6): pp. 369-395, 2004. thuật di truyền hoặc mạng neural [2]. Phương pháp tính điềm [13] A. Konak, D. W. Coit, A. E. Smith, “Multi-objective optimization using do nhóm tác giả đề xuất trong bài báo thực hiện giải bài toán genetic algorithms: A tutorial” J. Reliability Engineering and System Safety, No. 91, pp. 992-1007, 2006. tối ưu hóa đa mục tiêu nên có nhiều ưu điểm hơn so với [14] V. Lücken, Christian, B. Barán, C. Brizuela, "A survey on multi- phương pháp cũ. objective evolutionary algorithms for many-objective problems." Các giải thuật tiến hóa đa mục tiêu cũng được đã sử dụng Computational Optimization and Applications pp. 707-756, 2014. hiệu quả trong vấn đề lọc thư rác tiêu biểu là các nghiên cứu ứng dụng MOEA để xác định các đặc trưng của mỗi luật [7] hoặc tạo ra các luật phức hợp từ các luật cơ bản [8]. 35 35

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.15: Bộ Đồ Án Tốt Nghiệp Chuyên Ngành Cơ Khí

65 tài liệu

2428 lượt tải

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.