Xem mẫu
- 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
mr,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
Scoree= 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.
Spame= (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 ; i0...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
nguon tai.lieu . vn
