Thảo
Quốc
Gia2015
2015về
vềĐiện
Điện Tử,
Tử,Truyền
Truyền Thơng
Thơng và
Thơng
TinTin
(ECIT
2015)
HộiHội
Thảo
Quốc
Gia
vàCơng
CơngNghệ
Nghệ
Thơng
(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

2

: Đại học Hà Nội. Email: {nxthang, ngoctb}@hanu.edu.vn
: Học Viện Cơng Nghệ Bưu Chính Viễn Thơng. Email: ;

Abstract— Một vấn đề còn tồn tại trong các hệ thống phân loại tự
động thư rác dựa trên nội dung là làm sao để cân bằng giữa độ
chính xác phân loại thư rác và tỉ lệ chặn nhầm thư hợp lệ khi
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
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.

Hiện tại quy trình thiết kế bộ lọc thư rác theo phương pháp
học máy gồm các bước như sau:
- Sử dụng các tập mẫu để huấn luyện bộ phân loại tự động.
- Chọn một ngưỡng T dùng để xác định xem một thư mới có
phải là thư rác hay khơng. Thư mới được tách thành các
đặc trưng và so sánh với các đặc trưng đã được ghi nhận
bởi bộ huấn luyện. Nếu tổng trọng số của các đặc trưng
này lớn hơn giá trị T thì thư mới sẽ được phân loại là thư
rác.
- Tính tốn các tham số SDR và FAR để đánh giá hiệu quả
của bộ lọc.
Theo quy trình trên giá trị của SDR và FAR phụ thuộc vào
ngưỡng T và trọng số của các đặc trưng. Để tìm ra bộ lọc có
SDR và FAR phù hợp người dùng phải thử các giá trị T và

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
lớn. Hơn nữa, quy trình chưa hỗ trợ việc đánh giá “sự thỏa
hiệp” giữa SDR và FAR.
Nhóm tác giả đề xuất giải pháp cho vấn đề trên bằng cách
coi yêu cầu thiết kế bộ lọc thư rác là một bài tốn tối ưu hóa đa
mục tiêu trong đó ta cần tìm giá trị ngưỡng T và các trọng số
của mỗi đặc trưng sao cho tham số SDR và FAR của bộ lọc 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 trên nền tảng phần mềm SpamAssassin [1] với các đặc
trưng được trích chọn là các luật và trọng số của mỗi đặc trưng
là điểm của luật tương ứng. Do đặc thù của bài tốn tối ưu đa
mục tiêu được mơ tả trong bài báo là có khơng gian tìm kiếm
lớn và nhiều chiều nên nhóm tác giả đề xuất sử dụng giải thuật
tiến hóa đa mục tiêu (multi-objective evolutionary algorithm –
MOEA) [9], cụ thể là giải thuật SPEA-II [10,11], để giải bài
tốn này. Tuy SPEA-II khơng cho ra lời giải chính xác nhất,
nhưng giải thuật này cho kết quả là tập các phương án thỏa
hiệp (hay còn gọi là tập phương án tối ưu Pareto) [12]. Từ đó,
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
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
nhóm tác giả đề xuất có hai ưu điểm như sau:
- Tìm được các bộ giá trị khác nhau của ngưỡng T và điểm
của mỗi luật để xây dựng bộ lọc thư rác có tham số SDR
và FAR phù hợp với yêu cầu của người dùng mà không
tốn thời gian huấn luyện lại bộ phân loại tự động.
- Đưa ra tập nghiệm “thỏa hiệp” giữa các hai mục tiêu đem
lại sự lựa chọn dễ dàng hơn cho người dùng khi phải cân
nhắc giữa SDR và FAR.
Phần còn lại của bài báo được tổ chức như sau: phần II

trình bày về hệ thống lọc thư rác SpamAssassin. Phần III phát

Keywords- Lọc thư rác, tối ưu hóa đa mục tiêu, giải thuật di
truyền, SpamAssassin.

I.

GIỚI THIỆU

Ngày nay, thư điện tử đã trở thành một công cụ đắc lực
phục vụ cho nhu cầu trao đổi thông tin của các cơ quan, tổ
chức, doanh nghiệp cũng như mỗi cá nhân. Tuy nhiên, thư điện
tử cũng đang bị lợi dụng để phát tán thư rác, lây lan virus máy
tính và lừa đảo trực tuyến, gây thiệt hại lớn cho người sử dụng.
Nhiều giải pháp đã được đưa ra để đối phó với vấn nạn thư rác,
trong đó đáng kể nhất là các giải pháp tự động phân loại thư
rác dựa trên nội dung thông qua học máy. Phương pháp này
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ệ
đã được phân loại chính xác từ trước. Từ các tập mẫu này, một
thuật toán học máy được sử dụng để trích chọn các đặc trưng
nội dung (thường là từ hoặc cụm từ) của thư rác, đánh trọng số
cho các đặc trưng và huấn luyện bộ phân loại tự động cho phép
phân loại các thư mới chưa xuất hiện trong hai tập mẫu. Ưu
điểm của các giải pháp này là có tính linh hoạt và có hiệu quả
cao.
Để đá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ư
rác (Spam Detection Rate – SDR) và tỉ lệ chặn nhầm thư hợp lệ
(False Alarm Rate – FAR). Trong đó, SDR là tỉ số giữa số thư
rác mà bộ lọc phân loại được và tổng số thư rác đầu vào còn

FAR là tỉ lệ giữa số thư hợp lệ bị bộ lọc phân loại nhầm là thư
rác và tổng số thư hợp lệ đầu vào. Một bộ lọc thư rác lý tưởng
sẽ có tỉ lệ SDR và FAR lần lượt là 100% và 0%. Tuy nhiên các
quan sát thực tế trong quá trình xây dựng các bộ lọc thư rác cho
thấy các điều chỉnh để tăng tỉ lệ SDR cũng đồng thời làm tăng
tỉ lệ FAR và ngược lại việc giảm tỉ lệ FAR sẽ kéo theo giảm tỉ
lệ SDR. Do đó vấn đề đặt ra khi thiết kế các bộ lọc thư rác là
cân nhắc “sự thỏa hiệp” (tradeoff) giữa hai tham số SDR và
FAR để tìm ra giải pháp phù hợp cho mỗi tình huống cụ thể.

ISBN: 978-604-67-0635-9

30
30


Thảo
Quốc
Gia2015
2015về
vềĐiện
Điện Tử,
Tử,Truyền
Truyền Thông
Thông và
Thông
TinTin
(ECIT
2015)
HộiHội

Thảo
Quốc
Gia
vàCông
CôngNghệ
Nghệ
Thông
(ECIT
2015)

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 thư trong tập huấn luyện.
Đối chiếu với các bước của giải pháp tự động phân loại thư
rác dựa trên nội dung thông qua học máy đã mơ tả ở phần I thì
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
xác định trọng số của các đặc trưng này thể hiện ở điểm số của
mỗi luật. Dễ thấy khi xây dựng bộ lọc thư rác trên nền tảng
SpamAssassin, điểm số của các luật có ảnh hướng lớn đến hiệu
quả của bộ lọc vì điểm số của luật thể hiện độ quan trọng của
luật đó trong quá trình phân loại thư. Xác định điểm số cho các
luật càng chính xác thì hiệu quả của bộ lọc thư rác càng cao và
ngược lại.
Gọi SDR0 và FAR0 là các giá trị mong muốn của hai tham
số SDR và FAR của bộ lọc thư rác cần thiết kế (với ý nghĩa bộ
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
ngưỡng T, điểm số của mỗi luật sẽ được tính tốn để cho tham
số SDR của bộ lọc thu được là lớn nhất. Tuy nhiên các khả
năng sau có thể xảy ra sau khi thực thi xong thuật tốn tính

điểm số:
(1) Giá trị SDR của bộ lọc thu được không đạt yêu cầu
(2) Giá trị FAR của bộ lọc thu được không đạt yêu cầu
(3) Giá trị SDR và FAR đạt yêu cầu nhưng chưa phải là tối ưu
Để giải quyết vấn đề trên người dùng phải thử chọn các giá trị
ngưỡng T khác, thực hiện lại thuật tốn tính điểm và tiếp tục
kiểm tra xem các tham số SDR và FAR của bộ lọc đã đạt u
cầu chưa. Quy trình này khơng chỉ gây tốn thời gian, tốn tài
nguyên hệ thống mà còn chưa giải quyết triệt để vấn đề (3) do
chưa xem xét đến giá trị của FAR trong quá trình tính điểm.
Từ những phân tích nêu trên, nhóm tác giả đề xuất giải pháp
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
toán tối ưu hóa đa mục tiêu trong đó ta cần tìm giá trị ngưỡng
T và các giá trị điểm số của mỗi luật sao cho giá trị tham số
SDR và FAR của bộ lọc thu được là tối ưu. Lưu ý rằng do mối
quan hệ “thỏa hiệp” giữa SDR và FAR như đã nêu trong phần I
nên sẽ rất khó tìm được một bộ giá trị của T và các điểm số sao
cho SDR và FAR thực sự tối ưu (SDR=100% và FAR=0%),
thay vào đó nhóm tác giả hướng tới việc tìm ra tập các phương
án thỏa hiệp (hay còn gọi là tập phương án tối ưu Pareto) [12].
Từ đó, 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 cho bài toán.

biểu bài toán và đề xuất phương pháp giải. Phần IV trình bày
các kết quả thí nghiệm và đánh giá hiệu quả của giải pháp.
Phần V tóm tắt các kết quả nghiên cứu liên quan đến chủ đề
trình bày trong bài báo. Cuối cùng, các kết luận được trình bày
trong phần VI.
II.


BỘ LỌC SPAMASSASSIN

SpamAssassin là một hệ thống lọc thư rác được sử dụng
khá phổ biến do Apache Foundation phát triển. SpamAssassin
phân loại thư rác dựa trên một tập các luật đã được định nghĩa
sẵn. Mỗi luật được gán một điểm số cho trước. Trong quá trình
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
mỗi thư cần phân loại để chấm điểm. Khi tổng số điểm của một
thư vượt quá ngưỡng cho trước thì thư này sẽ bị phân loại là
thư rác. Một ví dụ về luật dùng trong Spamassassin được mô tả
trong danh sách (1):
Body DEAR_FRIEND /^\s*Dear Friend\b/i
Describe DEAR_FRIEND Dear Friend? That’s not very dear
Score DEAR_FRIEND 0.542
Danh sách 1: Ví dụ một luật trong SpamAssassin

Ví dụ trên định nghĩa một luật có tên DEAR_FRIEND, khi
SpamAssassin áp dụng luật này trên một thư cần phân loại,
phần mềm sẽ kiểm tra xem thư có chứa mẫu chuỗi ký tự được
quy định trong biểu thức chính quy /^\s*Dear Friend\b/i hay
khơng. Nếu thư có chứa chuỗi này thì số điểm 0.542 sẽ được
cộng vào tổng điểm số dùng để phân loại thư. Cấu trúc cụ thể
của luật dùng trong SpamAssassin được trình bày cụ thể trong
[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ẽ
tạo thành một bộ lọc thư rác trên nền SpamAssassin.
Quá trình xây dựng một bộ lọc thư rác cho SpamAssassin
được chia thành hai giai đoạn: xác định nội dung của các luật
(các mẫu chuỗi ký tự dùng trong biểu thức chính quy) và gán
điểm số cho mỗi luật. Ở giai đoạn thứ nhất căn cứ vào hai tập
mẫu cho trước các đặc trưng của thư rác (từ hoặc cụm từ) được

trích chọn để hình thành nên nội dung của các luật của bộ lọc.
Mỗi luật tương ứng với một từ hoặc cụm từ đặc trưng của thư
rác. Dễ thấy nội dung của các luật sẽ phụ thuộc vào loại ngôn
ngữ sử dụng trong các thư ở tập mẫu, do đó sẽ có các luật khác
nhau dành riêng cho lọc thư rác tiếng Anh và lọc thư rác tiếng
Việt. Trong các nghiên cứu trước đây[2,5,6], nhóm tác giả đã
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ả
tập luật lọc thư rác thu được từ các nghiên cứu đó.
Ở giai đoạn thứ hai điểm số được gán cho mỗi luật, q
trình này có ý nghĩa tương tương với việc gán trọng số cho mỗi
đặc trưng đã được trích chọn. Hiện tại SpamAssassin sử dụng
một thuật toán học máy trên nền tảng mạng neural một
lớp[2,3]. Trong đó mỗi nút mạng mô tả một luật, mỗi đầu vào
của mỗi nút thể hiện luật đó có xuất hiện trong một thư rác,
trọng số của mỗi nút là điểm của luật. Sau khi kết thúc q
trình huấn luyện tồn bộ tập luật sẽ được gán một điểm số
tương ứng. Về cơ bản q trình này có thể mơ hình hóa dưới
dạng một bài tốn tối ưu hóa đơn mục tiêu, với một ngưỡng T
cho trước quá trình huấn luyện sẽ gán điểm cho mỗi luật sao

III.

PHÁT BIỂU BÀI TOÁN VÀ PHƯƠNG PHÁP GIẢI

A. PHÁT BIỂU BÀI TOÁN
Giả sử tập mẫu ban đầu bao gồm tập thư rác S=(s1, s2, …,
sK) và tập thư hợp lệ H=(h1, h2, …, hL). Giả sử bộ lọc thư rác
cần xây dựng bao gồm tập luật R=(r1, r2, …, rN), mỗi luật cần
được xác định điểm tương ứng là một phần tử trong tập điểm

X=(x1, x2, …, xN). Với mỗi luật r và mỗi thư điện tử e ta có thể
xác định hàm so khớp m(r,e) như sau:
1 nếu đặc trưng r xuất hiện trong e
mr,e= 
0 ngược lại

(1)

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


Thảo
Quốc
Gia
2015về
vềĐiện
ĐiệnTử,
Tử,Truyền
TruyềnThông
Thông và
TinTin
(ECIT
2015)
HộiHội
Thảo
Quốc

Gia
2015
và Công
CôngNghệ
NghệThông
Thông
(ECIT
2015)
N

Scoree=  m(ri ,e)xi

thể của tập tối ưu Pareto, một tập các phương án như vậy được
gọi là tập Pareto được biết tốt nhất (Best-known Pareto set).
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:
- Là một tập con của tập tối ưu Pareto.
- 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
không gian mục tiêu.
- Các giá trị của hàm mục tiêu tương ứng phải biểu thị toàn
cảnh của đường biên Pareto.

(2)

i=1

Với mỗi giá trị ngưỡng T xác định, bộ lọc SpamAssassin sẽ kết
luận e là thư rác hay thư hợp lệ dựa trên cơng thức:
1 nếu Score(e) ≥ T

Spame= 
0 ngược lại

(3)

Từ đó các tham số SDR và FAR của bộ lọc thư rác được tính
theo các cơng thức:

C. CÁC GIẢI THUẬT TIẾN HĨA ĐA MỤC TIÊU
Với cách tiếp cận nói trên, việc giải bài tốn tối ưu hóa đa
mục tiêu được thực hiện thơng qua q trình tìm kiếm tập
Pareto được biết tốt nhất. Do đó các giải thuật tìm kiếm metaheuristic mà cụ thể là các giải thuật tiến hóa sẽ là các công cụ
đặc biệt phù hợp để giải quyết lớp bài tốn này. Thực tế các
giải thuật tiến hóa đa mục tiêu như NSGA hay SPEA có thể
thực hiện tìm kiếm tập Pareto được biết tốt nhất chỉ trong một
lượt chạy. Theo thống kê trong [13], các giải thuật tiến hóa
chiếm 70% trong tổng số các phương pháp tối ưu hóa đa mục
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
cơng bố, trong [14] các tác giả trình bày tổng quan về các giải
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
đ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à
phương pháp để đa dạng hóa quần thể.
Xếp hạng Pareto (Pareto ranking) là một phương pháp
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
trội trong quần thể và loại chúng ra khỏi danh sách xếp hạng,
rồi tìm các cá thể không bị vượt trội mới để gán thứ hạng 2 và
tiếp tục như vậy cho đến khi tồn bộ quần thể được xếp hạng.

Duy trì quần thể ưu tú là một vấn đề quan trọng trong tối ưu
hóa đa mục tiêu sử dụng MOEA. Trong ngữ cảnh của giải thuật
MOEA, tất cả những cá thể không bị vượt trội được phát hiện
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ì
quần thể ưu tú: (i) lưu trữ các cá thể ưu tú trong chính quần thể
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ể.
Phương pháp chia sẻ độ thích nghi (Fitness sharing) được
dùng để đa dạng hóa quần thể. Phương pháp này khuyến khích
tìm kiếm trên những vùng chưa biết của đường biên Pareto
bằng cách giảm bớt độ thích nghi của các cá thể ở những vùng
có mật độ cao. Các kỹ thuật khác nhau thường được dùng để
ước lượng mật độ các cá thể xung quanh một cá thể đang xét
như kỹ thuật đếm số vùng lân cận (niche count) hay kỹ thuật
tính khoảng cách mật độ trong đó ước tính giá trị khoảng cách
Euclide trung bình trong khơng gian mục tiêu của cá thể đang
xét tới các láng giềng gần nhất thứ k (k-th nearest neighbor)
của nó. Khoảng cách mật độ cũng được dùng trong cơ chế
chọn cha mẹ như sau: lấy ngẫu nhiên hai cá thể x và y; nếu
chúng có cùng thứ tự (non-domination rank) thì cá thể nào có

K

SDR=

1
 Spam(si )
K


(4)

i=1
L

1
FAR=  Spam(hi )
L

(5)

i=1

Do bản thân giá trị ngưỡng T cũng là một biến số nên ta sử
dụng x0 để ký hiệu thay cho T. Cuối cùng bài toán tối ưu hóa
đa mục tiêu được phát biểu như sau:
z1 = SDR(X)  Max
z2 = FAR(X)  Min, X=(xo, x1, …, xN) ∈ RN+1
với các ràng buộc: ximin ≤xi ≤ximax ;i0...N



(6)

Trong đó các giá trị SDR(X) và FAR(X) được tính theo các
công thức (4) và (5). Các giá trị ximin và ximax thể hiện khoảng
giá trị cho phép của biến xi.

B. TỐI ƯU HÓA PARETO
Thực tế hai mục tiêu của bài tốn tối ưu hóa (6) khơng thể

đạt được đồng thời, do đó phương pháp tối ưu hóa Pareto [12]
được áp dụng để giải bài toán. Ta xem xét bài toán tối ưu hóa
đ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
P hàm mục tiêu – các mục tiêu loại tối đa hóa có thể được
chuyển thành loại tối thiểu hóa bằng cách nhân với -1:
zi = fi(X)  Min, X=(x1, x2, …, xN) ∈ RN , i=1, 2, … P (P≥2)
với các ràng buộc: g j X ;j=1...m

Một phương án khả thi X được gọi là vượt trội so với phương
án khả thi Y (ký hiệu X ≽ Y), nếu và chỉ nếu, zi(X) ≤ zi(Y)
(i=1, ... , P) và zj(X) < zj(Y) ở ít nhất một mục tiêu j. Một
phương án được gọi là phương án tối ưu Pareto nếu nó khơng
bị vượt trội bởi bất cứ phương án nào khác trong không gian
phương án {X}. Các giá trị hàm mục tiêu tương ứng của các
phần tử trong tập các phương án tối ưu Pareto nói trên tạo
thành đương biên Pareto (Pareto Front) trong khơng gian mục
tiêu.
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
cả các phương án trong tập tối ưu Pareto. Tuy nhiên việc chứng
minh một tập hợp các phương án tìm được là tập tối ưu Pareto
thường khơng khả thi. Do đó một cách tiếp cận thực tế thường
đượ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


Thảo
QuốcGia
Gia2015

2015về
về Điện
Điện Tử,
Truyền Thông
Thông
Tin Tin
(ECIT
2015)
HộiHội
Thảo
Quốc
Tử, Truyền
ThôngvàvàCông
CôngNghệ
Nghệ
Thông
(ECIT
2015)

khoảng cách mật độ cao hơn sẽ được chọn; ngược lại cá thể có
mức thứ tự thấp hơn sẽ được chọn.

tập kiểm tra. Tập mẫu được dùng trong q trình tìm kiếm bộ
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à
tập kiểm tra đều chứa các thư rác và các thư hợp lệ. Bảng 1 mô
tả số lượng thư cụ thể dùng trong mỗi kịch bản.

D. SỬ DỤNG MOEA ĐỂ GIẢI BÀI TỐN
Nhóm tác giả lựa chọn giải thuật tiến hóa đa mục tiêu SPEA-II

để giải bài tốn. Trong phần tiếp theo chúng tơi mơ tả một số
điểm chính trong q trình sử dụng SPEA-II để giải bài toán.
Biểu diễn nhiễm sắc thể: Bài toán yêu cầu tìm kiếm giá trị
ngưỡng T và điểm cho từng luật có trong bộ lọc thư rác
SpamAssassin sao cho các tham số SDR và FAR của bộ lọc
thu được là tốt nhất. Do đó mỗi nhiễm sắc thể sẽ biểu diễn một
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
N+1 số thực (các gen) tương ứng với một phương án X=(xo, x1,
…, xN) ∈ RN+1 trong không gian phương án. Giá trị của mỗi xi
phải nằm trong ngưỡng cho phép ximin ≤xi ≤ximax đã xác định
trước. Phương pháp mã hóa số thực (real-coded method) [14]
được chúng tôi sử dụng để biểu diễn mỗi nhiễm sắc thể.
Tính tốn giá trị hàm mục tiêu: Giá trị hàm mục tiêu của mỗi
nhiễm sắc thể được tính tốn thơng qua phần mềm
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
gồm tập thư rác S và tập thư hợp lệ H. Từ kết quả kiểm tra ta
có thể tính được các tham số SDR và FAR của bộ lọc và từ đó
xác định được các giá trị hàm mục tiêu của nhiễm sắc thể. Lưu
ý để cho đơn giản ta chọn giá trị hàm mục tiêu 1-SDR thay vì
SDR, như thế mục tiêu của bài tốn sẽ là tối tiểu hóa hai hàm
mục tiêu FAR và 1-SDR.
Cơ chế chọn lọc: Được được dùng để chọn các nhiễm sắc thể
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
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
thích nghi tốt hơn sẽ là người chiến thắng.
Phép toán lai tạo (Crossover operator): Hai nhiễm sắc thể cha

mẹ được chọn sẽ tạo ra hai nhiễm sắc thể con mới cho quần
thể. Chúng tôi sử dụng phép toán lai tạo giả nhị phân
(Simulated Binary Crossover) để thực hiện q trình này.
Phép tốn đột biến (Mutation operator): Chúng tôi chọn phép
đột biến đa thức (polynomial mutation operator) để biến đổi
nhiễm sắc thể nhằm tăng tính đa dạng của quần thể.
Gán độ thích nghi: Phương pháp xếp hạng Pareto được dùng
để gán độ thích nghi cho mỗi nhiễm sắc thể có trong quần thể.
Duy trình quần thể ưu tú: SPEA-II sử dụng một danh sách thứ
cấp để lưu trữ các nhiễm sắc thể ưu tú (là các phương án không
bị vượt trội như mô tả trong phương pháp tối ưu Pareto) của
quần thể. Danh sách này sẽ được đưa lại vào quần thể trong
quá trình chọn lọc.
Chia sẻ độ thích nghi: Sử dụng kỹ thuật tính khoảng cách mật
độ đã trình bày ở phần trên.
IV.

Kịch bản 1 (300 thư)
Mẫu
Kiểm tra
120
60
80
40

Thư rác
Thư hợp lệ

Kịch bản 2 (750 thư)
Mẫu

Kiểm tra
300
150
200
100

Bảng 1: Số lượng thư điện tử dùng trong các kịch bản

Trong mỗi kịch bản thử nghiệm chúng tôi thực hiện thiết kế
bộ lọc gồm 30 luật và 100 luật để đảm bảo các thực nghiệm
được thực hiện với số lượng thư và số lượng luật ở quy mô nhỏ
và quy mô lớn. Dải giá trị hợp lệ được chọn cho ngưỡng T là
[0,5]; cho điểm của mỗi luật là [0,2]. Thuật tốn SPEA-II được
cài đặt để tính điểm cho mỗi luật có trong bộ lọc, các tham số
của SPEA-II được mơ tả trong bảng 2 (N có giá trị lần lượt là
30 và 100).
Tham số
Kích thước quần thể

Giá trị
100

Số lượng thế hệ

1000

Số mục tiêu
Số biến thực
Cận dưới của biến 1
Cận trên của biến 1


2
N+1
0
5

Tham số
Cận dưới của
biến N+1
Cận trên của
biến N+1
Xác suất lai tạo
Xác suất đột biến

Giá trị
0
2
0,9
1/(N+1)

Bảng 2: Các tham số của thuật toán SPEA-II

Các thử nghiệm được chạy trên máy tính có cấu hình Intel
Core i3-3120M 2.5GHz, RAM 4GB, OS Ubuntu 14.04. Để
đảm bảo tính khách quan mỗi thử nghiệm được chạy 20 lần với
các nhân ngẫu nhiên khác nhau, các số liệu trình bày trong bài
báo là giá trị trung bình của kết quả thu được sau mỗi lần chạy.
Kết quả thử nghiệm được so sánh với phương pháp tính điểm
tối ưu hóa đơn mục tiêu (SOOA) [2] của SpamAssassin trên
cùng mẫu dữ liệu thư điện tử. Để thực hiện so sánh, chúng tôi

chọn 10 giá trị ngưỡng T phân bố đều trong khoảng [0,5], với
mỗi giá trị ngưỡng phương pháp tính điểm hiện tại sẽ tính tốn
điểm của các luật để tối ưu hóa tham số SDR, giá trị của tham
số FAR của bộ lọc cũng được tính tốn và so sánh với phương
pháp đề xuất trong bài báo.
Các kết quả thử nghiệm theo kịch bản thứ nhất (với tập
chứa 300 thư) được trình bày trong hình 1 (bộ lọc có 30 luật)
và hình 2 (bộ lọc có 100 luật). Các kết quả thu được khi thiết
kế bộ lọc bằng phương pháp SOOA cũng được trình bày trong
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
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%,
thì kết quả tốt nhất mà phương pháp SOOA tìm được là
(SDR=40,8%, FAR=0%). Trong khi đó sử dụng SPEA-II ta thu
được bộ lọc có (SDR=60%, FAR=0%). Tương tự nếu ta chỉ
quan tâm đến những bộ lọc có FAR ≤ 10% thì các kết quả tốt

KẾT QUẢ

Nhóm tác giả thử nghiệm xây dựng bộ lọc thư rác
SpamAssassin với hai kịch bản sử dụng hai cơ sở dữ liệu thư
điện tử khác nhau chứa 300 thư và 750 thư do nhóm tác giả thu
thập từ nhiều nguồn khác nhau. Trong mỗi kịch bản, tập thư
đ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
Gia
2015
và Cơng
CơngNghệ
NghệThơng
Thơng
(ECIT
2015)
Thảo
Quốc
Gia
2015về
vềĐiện
ĐiệnTử,
Tử,Truyền
TruyềnThơng
Thơng và
TinTin
(ECIT
2015)
nhất mà SOOA tìm được là (67,7%, 10%) và (55,8%, 1,25%)
trong khi SPEA-II tìm ra những kết quả tốt hơn như (60%,
0%), (64,2%, 1,3%) và (68,3%, 5%).

tích kỹ hơn số liệu trình bày trong bảng 3 ta thấy khi bộ lọc
chứa nhiều luật hơn thì SPEA-II cũng tìm được những kết quả
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).

1
2
3

1
2
3

Hình 1. Kết quả kịch bản thử nghiệm 1 với bộ lọc 30 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
67,7 10,0 65,0 12,5 81,3 15
81,7 17,5
55,8 1,25 56,7 2,5
78,3 12,5 78,3 12,5
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
72,5 12,5 71,7 12,5 82,5 13,8 83,3 15,0
71,0 10,0 71,7 10,0 80,8 12,5 80,0 12,5
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 q 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 tố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.
TÀI LIỆU THAM KHẢO

Hình 4. Kết quả kịch bản thử nghiệm 2 với bộ lọc 100 luật

1
2
3

1
2
3

[1]

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
79,0 15,5 78,7 15,0 75,7 4,0
75,0 5,0
81,3 19,0 81,3 19,0 84,3 20,0 84,5 21,0
74,7 8,5
74,7 9,0
78,3 14,0 78,5 14,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
79,3 11,0 79,3 11,0 83,3 10,0 83,3 10,0
77,3 9,0
77,3 9,0
78,3 6,0
78,7 6,0
76,3 7,5
76,7 8,0
81,7 13,5 82,0 14,0


[2]
[3]
[4]
[5]

[6]

[7]

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 2

V.

[8]

CÁC NGHIÊN CỨU LIÊN QUAN

Cho tới nay đã có nhiều cơng trình nghiên cứu liên quan
đến vấn đề lọc thư rác như sử dụng các bộ lọc địa chỉ thư, các
bộ lọc nội dung sử dụng Bayesian hoặc SVM, sử dụng phương
pháp học máy [3], sử dụng mạng phức hợp [4]. Trong vấn đề
phân loại thư rác dựa trên nội dung, ngơn ngữ sử dụng trong
thư điện tử có vai trị rất quan trọng. Nhóm tác giả đã xuất bản
một số cơng trình nghiên cứu liên quan đến việc xây dựng các
bộ lọc thư rác cho từng loại ngôn ngữ (tiếng Trung [2], tiếng
Việt [6]) cũng như thiết kế các luật lọc thư đa ngôn ngữ [5].
Trong phần lớn các nghiên cứu hiện tại, việc tính điểm cho
các luật dùng trong bộ lọc SpamAssassin được thực hiện thông
qua việc giải bài tốn tối ưu hóa đơn mục tiêu sử dụng giải

thuật di truyền hoặc mạng neural [2]. Phương pháp tính điềm
do nhóm tác giả đề xuất trong bài báo thực hiện giải bài tốn
tối ưu hóa đa mục tiêu nên có nhiều ưu điểm hơn so với
phương pháp cũ.
Các giải thuật tiến hóa đa mục tiêu cũng được đã sử dụng
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].

[9]
[10]
[11]

[12]
[13]
[14]

35
35

The Apache SpamAssassin Project. SpamAssassin: The Powerful #1
Open-Source Spam Filter. [Online] 2015. [Cited: 16 July 2015]
/>Tran, Q. A., Duan, H. X. Li, X., “Real-time statistical rules for spam
detection”, IJCSNS International Journal of Computer Science and
Network Security, VOL.6 No.2B, pp 178–184, 2006.
Schwartz A. SpamAssassin. O’Reilly, 2004.
Joseph S. Kong, Behnam Attaran Rezaei, Nima Sarshar, Vwani P.
Roychowdhury, P. Oscar Boykin, “Collaborative Spam Filtering Using
E-Mail Networks”. IEEE Computer 39(8): 67-73, 2006.
Minh Tuan Vu and F. Jiang V.Q. Tran Tran, Quang Anh, “Multilingual

rules for spam detection”. Proceedings of IB2COM 2012, pages 106–
110, 2012.
Nguyen T.A., Tran Q.A., Nguyen N.B., “Vietnamese spam detection
based on language classification”, HUT-ICCE 2008 - 2nd International
Conference on Communications and Electronics, 2008.
V. Fernandes, I. Yevseyeva, R. Frantz, C. Grilo, N. Díaz, M. Emmerich,
“An Automatic Generation of Textual Pattern Rules for Digital Content
Filters Proposal, Using Grammatical Evolution Genetic Programming”,
Procedia Technology, Volume 16, Pages 806-812, 2014.
I. Yevseyeva, V. Fernandes, D. Ord´as, J. M´endez “Optimising antispam filters with evolutionary algorithms”. Expert Systems with
Applications, 2013.
C. A. C. Coello, “Evolutionary multi-objective optimization: A
historical view of the field”. IEEE Computational Intelligence
Magazine, 1(1):28–36, 2006.
E. Zitzler, L. Thiele, and K. Deb, “Comparision of multiobjective
evolutionary algorithms: Emprical results”. Evolutionary Computation,
8(1):173–195, 2000.
E. Zitzler, M. Laumanns, and L. Thiele, “SPEA2: Improving the
strength pareto evolutionary algorithm for multiobjective optimization”.
In Evolutionary Methods for Design Optimization and Control with
Applications to Industrial Problems, pp. 95–100, 2001.
Marler, R.T. and J.S. Arora, “Survey of multi-objective optimization
methods for engineering”. Structural and Multidisciplinary
Optimization, 26(6): pp. 369-395, 2004.
A. Konak, D. W. Coit, A. E. Smith, “Multi-objective optimization using
genetic algorithms: A tutorial” J. Reliability Engineering and System
Safety, No. 91, pp. 992-1007, 2006.
V. Lücken, Christian, B. Barán, C. Brizuela, "A survey on multiobjective evolutionary algorithms for many-objective problems."
Computational Optimization and Applications pp. 707-756, 2014.