20

1

[9] Nguyen Van Truong, Pham Dinh Lam, Vu Duc Quang.
Some impovements of selection algorithms fo spam email filtering.
[10] Johan Hovold (). Naïve Bayes Spam filtering using WordPosition-Based attributes. Department of Computer Science Lund
University

MỤC LỤC
MỤC LỤC .......................................................................................... 1
MỞ ĐẦU ............................................................................................ 3
Chương 1. THƯ RÁC VÀ CÁC PHƯƠNG PHÁP LỌC THƯ RÁC 4
1.1. Một số khái niệm cơ bản........................................................ 4
1.1.1. Định nghĩa thư rác.......................................................... 4
1.1.2. Phân loại thư rác ............................................................ 4
1.2. Các phương pháp lọc thư rác ................................................. 4
1.2.1. Lọc thư rác thông qua việc đưa ra luật lệ nhằm hạn chế,
ngăn chặn việc gửi thư rác. ........................................................ 4
1.2.2. Lọc thư rác dựa trên địa chỉ IP ....................................... 5
1.2.3. Lọc dựa trên chuỗi hỏi/ đáp ........................................... 5
1.2.4. Phương pháp lọc dựa trên mạng xã hội.......................... 5
1.2.5. Phương pháp lọc nội dung ............................................. 5
Chương 2. TỔNG QUAN CÁC THUẬT TOÁN NSA, PSA, PNSA
TRONG LỌC THƯ RÁC ................................................................... 5
2.1. Cơ sở lý thuyết về hệ miễn dịch nhân tạo............................... 5
2.1.1. Khái niệm về hệ miễn dịch nhân tạo ................................ 5
2.1.2. Phạm vi ứng dụng của hệ miễn dịch nhân tạo ................. 6
2.1.3. Cấu trúc cơ bản của hệ miễn dịch nhân tạo ..................... 6
2.2. Cơ sở lý thuyết về thuật toán chọn lọc tiêu cực (Negative
Selection Algorithms - NSA) ........................................................ 7

2.3. Cơ sở lý thuyết về thuật toán chọn lọc tích cực (Positive
Selection Algorithms – PSA) ........................................................ 7
2.4. Cơ sở lý thuyết thuật toán cải tiến chọn lọc thư rác (Positive
and Negative Selection Algorithms – PNSA) ............................... 8
2.4.1. Một số định nghĩa ............................................................ 9
2.4.2. Thuật toán sinh tập bộ dò r-chunk ................................... 9
2.4.3. Thuật toán sinh tập bộ dò dạng r – contiguous ................ 9


2

19

2.5. Các nghiên cứu gần đây ......................................................... 9
Chương 3. KẾT QUẢ CÀI ĐẶT CÁC THUẬT TOÁN. ................... 9
3.1 Tổng quan ứng dụng CNTT tại tỉnh Bắc Kạn ......................... 9
3.2 Mô hình tổng quát ................................................................... 9
3.3 Mô hình thực tế ứng dụng lọc email Spam tại hệ thống email
nội bộ của Viễn tông tỉnh Bắc Kạn ............................................. 10
3.4 Ứng dụng hệ miễn dịch nhân tạo trong lọc thư rác .............. 10
3.4.1 Phát biểu bài toán ............................................................ 10
3.4.2 Cơ sở dữ liệu TREC'07 ................................................... 11
3.4.3 Phân tích thuật toán........................................................ 12
3.1.5. Đánh giá ......................................................................... 13
3.5 So sánh với các thuật toán trên WEKA ................................. 13
3.5.1 Phát biểu bài toán ............................................................ 13
3.5.2 Cơ sở dữ liệu SpamBase ................................................. 13
3.5.3 Phần mềm WEKA .......................................................... 13
3.2.4. Thiết kế phần mềm ........................................................ 14
3.2.5 Phân tích thuật toán kết hợp chọn lọc tích cực và chọn lọc

tiêu cực PNSA ......................................................................... 14
3.2.6 Giao diện chương trình và kết quả .................................. 15
KẾT LUẬN ...................................................................................... 17
TÀI LIỆU THAM KHẢO ................................................................ 19

TÀI LIỆU THAM KHẢO
Tài liệu tiếng Việt
[1]. Bùi Ngọc Lan (2006). Lọc thư rác dựa trên tính chất của
mạng xã hội. Khóa luận tốt nghiệp. Trường Đại học Công nghệ, Đại
học Quố c gia Hà Nộ i.
[2] .Từ Minh Phương, Phạm Văn Cường, Nguyễn Duy
Phương, Hoàng Trọng Huy (2006). Báo cáo đề tài “Nghiên cứu xây
dựng hệ thống lọc thư rác có khả năng lọc thư rác tiếng Anh và tiếng
Việt”. Học viện Bưu chính Viễn thông, 2006.
Tài liệu tiếng Anh
[3]. Dipak R. Kawade, and Kavita S. Oza, SMS Spam
Classification using WEKA, International journal of Electronics
Communication and Computer Technology, 5 (2015), 43-47.
[4] Fernando Esponda, Stephanie Forrest, and Paul Helman, A
Formal Framework for Positive and Negative Detection Schemes,
IEEE transactions on systems, man, and cybernetics, 34 (2004), 357 372.
[5] Forrest, S., Hofmeyr, S. and Somayaji, A., Computer
Immunology, Communications of the ACM, 40 (1997), 88 - 96.
[6] Fuyong Zhang, Deyu Qi, A Positive Selection Algorithm
for classification, Journal of Computational Information Systems, 8
(2012), 207 - 215.
[7] Sin-Eon Kim, Jung-Tae Jo, and Sang-Hyun Choi, 2015,
SMS Spam Filterinig Using Keyword Frequency Ratio, International
Journal of Security and Its Applications, 9(1), 329-336.
[8] Van Truong Nguyen, Xuan Hoai Nguyen and Chi Mai

Luong, A Novel Combination of Negative and Positive Selection in
Artificial Immune Systems, Vietnam National University, Hanoi
Journal of Science: Comp. Science & Com. Eng. 31(1), 22-31, 2015.


18

3

- Kết hợp với các thuật toán học máy khác để có thể cải thiện
được hiệu suất và độ chính xác.
- Xây dựng hệ thống Webmail cho một cơ quan hoặc tổ chức
và tích hợp bộ lọc vào hệ thống.
- Xây dựng bộ lọc theo mức độ phù hợp cho một số nhóm đối
tượng cụ thể như: cùng chung sở thích, cùng nơi làm việc, cùng lĩnh
vực nghiên cứu…

MỞ ĐẦU
Mạng Internet ra đời đã mang lại cho con người những tiên ích
hết sức to lớn và quan trọng, một trong những tiện ích đó là dịch vụ
thư điện tử. Vì, đó là phương tiện giao tiếp đơn giản, tiện lợi, rẻ và
hiệu quả giúp mọi người gắn kết và liên lạc với nhau thường xuyên
hơn. Tuy nhiên, lợi dụng tính mở của công nghệ và cơ chế trao đổi
thư mà hàng ngày người dùng nhận được một số thư ngoài mong đợi
đó là thư rác (Spam). Thư rác thường được gửi với số lượng rất lớn
thường vì mục đích quảng cáo, thậm trí là đính kèm mã độc dưới
dạng Virus gây phiền toài cho người dùng, làm giảm tốc độ xử lý của
máy chủ mail server.
Thư rác (spam) là thư điện tử được gửi hàng loạt với nội dung
mà người nhận không mong đợi, không muốn xem, hay chứa những

nội dung không liên quan đến người nhận và thường được sử dụng để
gửi thông tin quảng cáo. Do có giá thành tương đối thấp so với các
phương pháp quảng cáo khác, thư rác hiện chiếm một tỷ lệ lớn và
ngày càng tăng trong tổng số thư điện tử được gửi qua Internet. Sự
xuất hiện và gia tăng thư rác không những gây khó chịu và làm mất
thời gian của người nhận mà còn ảnh hưởng tới đường truyền
Internet và làm chậm tốc độ xử lý của máy chủ thư điện tử, gây thiệt
hại lớn về kinh tế.
Xuất phát từ lý do đó, đề tài đặt vấn đề nghiên cứu một số
thuật toán LỌC THƯ RÁC, một trong những thuật toán mới được
công bố gần đây để đề xuất một mô hình thực nghiệm trên một dịch
vụ email thực tế. Qua đó hướng tới xây dựng ứng dụng bằng cách
tích hợp thêm một số Module trong hỗ trợ sử dụng dịch vụ sử dụng
email.


4

17

Nội dung luận văn gồm có 3 chương:
Dự kiến nội dung báo cáo của luận văn gồm: Phần mở đầu, 3
chương chính, phần kết luận, tài liệu tham khảo, phụ lục. Bố cục
được trình bày như sau:
Phần mở đầu: Nêu lý do chọn đề tài và hướng nghiên cứu chính
Chương 1: THƯ RÁC VÀ CÁC PHƯƠNG PHÁP LỌC THƯ RÁC
Chương 2: TỔNG QUAN CÁC THUẬT TOÁN NSA, PSA,
PNSA TRONG LỌC THƯ RÁC.
Chương 3: KẾT QUẢ CÀI ĐẶT CÁC THUẬT TOÁN.
Phần kết luận: Tóm tắt các kết quả đã đạt được và hướng phát

triển tiếp theo của đề tài.

KẾT LUẬN
Đề tài đã đạt được những kết quả sau đây:
- Tìm hiểu tổng quan về thư rác, các phương pháp phân loại
thư rác hiện đang sử dụng như: lọc thư giác thông quan việc đưa ra
luật lệ nhằm hạn chế, ngăn chặn việc gửi thư giác, lọc dựa trên địa
chỉ IP, lọc dựa trên chuỗi hỏi/đáp, lọc dựa trên mạng xã hội, lọc dựa
trên lọc nội dung... Đồng thời đánh giá ưu nhược điểm của các
phương pháp.
- Tìm hiểu về thuật toán chọn lọc tiêu cực, thuật toán chọn lọc
tích cực, các khái niệm cơ bản như: Self, Nonself, bộ dò…một số
thuật toán trong hệ miễn dịch nhân tạo.
- Nghiên cứu thuật toán chọn lọc tiêu cực dạng r-chunk và rcontiguous và đưa ra phương pháp ứng dụng các thuật toán trên cho
quá trình phân loại thư rác.
- Xây dựng chương trình mô phỏng sử dụng thuật toán kết hợp
chọn lọc tiêu cực và chọn lọc tích cực PNSA trong hệ miễn dịch nhân
tạo và áp dụng vào quá trình huấn luyện cũng như phân loại thư rác,
đồng thời đánh giá chương trình bằng thông số như: TP, TN, FP, FN
và các độ đo như: DR, FPR và Acc.
- Thử nghiệm phương pháp sinh tập bộ dò dạng r-chunk với
các bộ dữ liệu chuẩn TREC'07, SpamBase và so sánh kết quả với một
số phương pháp học máy khác.

Chương 1.
THƯ RÁC VÀ CÁC PHƯƠNG PHÁP LỌC THƯ RÁC
1.1. Một số khái niệm cơ bản
1.1.1. Định nghĩa thư rác
Thư rác (spam mail) là những bức thư điện tử không yêu cầu,
không mong muốn và được gửi hàng loạt tới người nhận.


Hinh 1.1: Tất cả các thư điện tử
1.1.2. Phân loại thư rác
1.2. Các phương pháp lọc thư rác
1.2.1. Lọc thư rác thông qua việc đưa ra luật lệ nhằm hạn chế,
ngăn chặn việc gửi thư rác.

Hướng phát triển
- Cần nghiên cứu khâu tiền xử lý văn bản, xây dựng các mẫu
huấn luyện tiêu chuẩn cũng như lựa chọn tham số hợp lý cho ℓ và r
để có thể nâng cao độ chính xác phân loại của giải thuật hơn nữa.
- Nâng khả năng lọc thư rác với các loại email chứa nội dung
là hình ảnh, ký tự lạ,…và có đính kèm tệp tin.


16
lazy.TB1
misc.HyperPipes
rules.ComnunctiveRule
trees.RandomTree
PNSA

1592
163
1276
1621
1499

2585
2777

2437
2563
2668

5
221
1650
537
192
314

203
11
351
225
120

87.81
8.99
70.38
89.41
82.67

7.28
0.39
12.59
8.07
4.31

90.78

63.90
80.70
90.94
90.56

Bảng 3.4. So sánh PNSA với một số phương pháp cho kết quả tốt
hơn
Phương pháp
TP
TN
FN
FP
DR
FPR
Acc
bayes.DMNBtext
1617 2662 196 126 89.19 4.52 93.00
functions.logistic
1607 2645 206 143 88.64 5.13 92.41
functions.Spegasos 1544 2661 269 127 85.16 4.56 91.39
lazy.TB1
1592 2585 221 203 87.81 7.28 90.78
trees.RandomTree 1621 2563 192 225 89.41 8.07 90.94
PNSA
1499 2668 314 120 82.67 4.31 90.56

Bảng 3.5. So sánh PNSA với một số phương pháp cho kết quả
thấp hơn
Phương pháp
TP

BayessianLogisticRegression 1758
NaiveBayesUpdateable
1725
functions.RBFNetwork
1568
misc.HyperPipes
163
rules.ComnunctiveRule
1276
PNSA
1499

TN
1986
1923
2143
2777
2437
2668

FN
55
88
245
1650
537
314

FP
802

865
645
11
351
120

DR
96.97
95.15
86.49
8.99
70.38
82.67

FPR
28.77
31.03
23.13
0.39
12.59
4.31

1.2.2. Lọc thư rác dựa trên địa chỉ IP
Danh sách đen (Blacklist)
Danh sách trắng (Whitelist)
1.2.3. Lọc dựa trên chuỗi hỏi/ đáp
1.2.4. Phương pháp lọc dựa trên mạng xã hội
1.2.5. Phương pháp lọc nội dung
Phương pháp lọc nội dung để phân loại thư rác đã và đang
được quan tâm, nghiên cứu và ứng dụng nhiều nhất. Phương pháp

này dựa vào nội dung và chủ đề bức thư để phân biệt thư rác và thư
hợp lệ. Phương pháp này có ưu điểm đó là chúng ta có thể dễ dàng
thay đổi bộ lọc để nó có thể lọc các loại thư rác cho phù hợp. Nhược
điểm của phương pháp này là: do biết được cách thức lọc nội dung
nên các spammer luôn luôn thay đổi hình thức nội dung của thư rác.

Acc
81.37
79.29
80.66
63.90
80.70
90.56

3.2.7. Đánh giá
Test áp dụng thuật toán để lọc các nội dung cụ thể

Hinh 1.2 : Mô tả tổng quan quá trình hoạt động của honeyd
Chương 2.
TỔNG QUAN CÁC THUẬT TOÁN NSA, PSA, PNSA
TRONG LỌC THƯ RÁC
2.1. Cơ sở lý thuyết về hệ miễn dịch nhân tạo.
2.1.1. Khái niệm về hệ miễn dịch nhân tạo


6

15

“HMD nhân tạo là một hệ thống thích nghi lấy ý tưởng của

học thuyết miễn dịch và những chức năng, nguyên tắc, mô hình miễn
dịch quan sát được, áp dụng giải các bài toán thực tế.” (Castro &
Timmis - 2002)

Output: Các số liệu: Acc, DR, FPR.
*) Kiểm tra khả năng phát hiện email SPAM
*) Sau 2 quá trình kiểm tra trên, tính toán 3 thông số: DR,
FPR, Acc.

2.1.2. Phạm vi ứng dụng của hệ miễn dịch nhân tạo
HMD nhân tạo có phạm vi ứng dụng rất rất rộng rãi, các ứng
dụng của nó phải kể đến là:
- Nhận dạng mẫu
- Kiểm tra lỗi và những dấu hiệu bất thường của hệ thống
- Phân tích dữ liệu
- Lập lịch
- Học máy
- Điều khiển tự động
- Tìm kiếm và tối ưu
- An toàn thông minh

3.2.6 Giao diện chương trình và kết quả

2.1.3. Cấu trúc cơ bản của hệ miễn dịch nhân tạo
Mô hình chung cho các hệ thống phỏng tiến hoá sinh học
Mô hình cho hệ miễn dịch nhân tạo

Giao diện chương trình
Chức năng của các đối tượng trong giao diện:
- Hộp Select a value r: Đặt giá trị cho r.

- Nút Test:
+ Tạo tập bộ dò từ các file email HAM.
+ Cho file email HAM còn lại (không sử dụng để tạo bộ dò)
và file email SPAM qua tập bộ dò thực hiện so khớp.
+ Tính toán và kết luận về khả năng phát hiện của tập bộ dò,
hiển thị kết quả tại vùng Results.
- Nút Exit: Thoát khỏi chương trình.
Bảng 3.3. Kết quả thử nghiệm trên WEKA và PNSA

Hình 2.3: Cấu trúc phân tầng của HMD nhân tạo
Các mô hình trừu tượng của hệ miễn dịch và tương tác giữa
chúng

Phương pháp
BayessianLogisticRegression
NaiveBayesUpdateable
bayes.DMNBtext
functions.logistic
functions.RBFNetwork
funtions.Spegasos

TP
1758
1725
1617
1607
1568
1544

TN

1986
1923
2662
2645
2143
2661

FN
55
88
196
206
245
269

FP
802
865
126
143
645
127

DR
96.97
95.15
89.19
88.64
86.49
85.16


FPR
28.77
31.03
4.52
5.13
23.13
4.56

Acc
81.37
79.29
93.00
92.41
80.66
91.39


14

3.2.4. Thiết kế phần mềm
- Bước 1: Chia các email thường trong file nguồn (HAM.txt)
ngẫu nhiên thành 10 phần và các email SPAM trong file nguồn
(SPAM.txt) thành
10 phần tương ứng được 10 file email HAM và 10 file email
SPAM.
- Bước 2: Đọc số liệu trong 9 file email thường để huấn luyện.
- Bước 3: Tiến hành kiểm tra (testing), thực hiện với 1 file
email thường còn lại và tất cả các email SPAM. Số lượng các email
HAM và email SPAM mà chương trình phát hiện được sẽ được tính

toán quy đổi ra 3 số liệu:
DR = TP/(TP + FN) FPR = FP/(TN + FP)
Acc = (TP + TN) /(TP + TN + FP + FN)
Chương trình thực hiện lặp bước hai và ba mười lần, mỗi lần
sẽ tính toán và cho ra 3 số liệu trên. Sau đó lấy giá trị trung bình
mười lần tính toán.
3.2.5 Phân tích thuật toán kết hợp chọn lọc tích cực và chọn lọc
tiêu cực PNSA
3.2.5.1 Quá trình chia file nguồn (Split file)
Input: file chứa số liệu thống kê 58 thuộc tính của email
HAM - HAM.txt Output: 10 file email HAM: HSub 1.txt, HSub 2.txt,
…, HSub 10.txt
3.2.5.2 Quá trình huấn luyện – Tạo tập bộ dò (Training)
Input: Chọn 9 trong 10 file: HSub i.txt (i=1,…,10).
Output: Tập bộ dò lưu trong bảng băm kích thước: 2r.(ℓ-r+1).
3.2.5.3 Quá trình kiểm tra – phân biệt HAM/SPAM (testing)
Input: Bảng băm đã tạo; File email HAM còn lại và file
emailSPAM.txt

7

Hình 2.4: Kháng thể nhận diện kháng nguyên dựa vào phần bù
2.2. Cơ sở lý thuyết về thuật toán chọn lọc tiêu cực (Negative
Selection Algorithms - NSA)
Bước 1. Khởi tạo: Sản sinh một quần thể tiềm năng P những Tcell chưa trưởng thành. Giả thiết tất cả các phần tử (các cơ quan thụ
cảm và các self-peptide) được biểu diễn bằng một xâu nhị phân ℓ bit.
Bước 2. Đánh giá độ thích hợp: Xác định độ thích hợp của tất
cả T-cell trong P với mọi phần tử của tập Self S.
Bước 3. Tạo một quần thể có giá trị: Nếu độ thích hợp của một
T-cell chưa trưởng thành với ít nhất một phần tử self-peptide lớn hơn

hoặc bằng một ngưỡng tương tác chéo nào đó, thì T- cell nhận diện
được self-peptide này và bị loại bỏ, trái lại T- cell được bổ sung vào
quần thể có giá trị A.

Hình 2.5 Sơ đồ khối thuật toán chọn lọc tiêu cực
2.3. Cơ sở lý thuyết về thuật toán chọn lọc tích cực (Positive
Selection Algorithms – PSA)


8

Thuật toán chọn lọc tích cực được minh họa như trong hình 2.6
và có thể tóm tắt như sau:
Bước 1. Khởi tạo: Sản sinh một quần thể tiềm năng P những Tcell chưa trưởng thành. Giả thiết tất cả các phần tử được biểu diễn
như các xâu nhị phân có cùng độ dài ℓ.
Bước 2. Đánh giá độ thích hợp: Xác định độ thích hợp của tất
cả phần tử trong quần thể P với tất cả phần tử trong tập Self S.
Bước 3. Tạo một quần thể có giá trị: Nếu độ thích hợp của một
phần tử trong P với một phần tử trong S lớn hơn hoặc bằng một
ngưỡng tương tác chéo nào đó thì T-cell có khả năng nhận diện
kháng nguyên, sẽ được chọn vào quần thể có giá trị A trái lại T-cell
bị loại bỏ

13

3.1.5. Đánh giá
Bảng 3.2. So sánh kết quả
R

FPR


Acc

Trong [10]

98.09%

0%

98.82%

Apply PNSA for SPAM Filtering

99.45%

0%

99.67%

3.5 So sánh với các thuật toán trên WEKA
3.5.1 Phát biểu bài toán
Input:
-Số nguyên dương r  [7,10], ℓ.
- Cơ sở dữ liệu Spambase Data Set (lưu trong file *.txt)
Output: Kết quả về sự phát hiện email SPAM hay email HAM
thể hiện qua 10 lần thử nghiệm với 3 số liệu thống kê trung bình: DR
(Detection Rate), FPR (False Positive Rate), Acc (Accuracy).
3.5.2 Cơ sở dữ liệu SpamBase
Trong 58 thuộc tính của cơ sở dữ liệu này:
- Có 48 thuộc tính đầu “word_freq_” nói về tỉ lệ phần trăm các

từ trong thư phù hợp với nội dung của thuộc tính nhắc đến.
3.5.3 Phần mềm WEKA
Giao diện của phần mềm WEKA:

Hình 2.6 Sơ đồ khối thuật toán chọn lọc tích cực
2.4. Cơ sở lý thuyết thuật toán cải tiến chọn lọc thư rác (Positive
and Negative Selection Algorithms – PNSA)
S là tập Self hay còn gọi là tập tế bào cần bảo vệ.
A là quần thể có giá trị.
Giao diện phần mềm Weka


12

9

Bước 5: Tiến hành kiểm thử với bộ dữ liệu test là 1.000 email
được lấy ngẫu nhiên từ 10.000 email ban đầu và tính toán các tham
số DR, FPR, Acc.
3.4.3 Phân tích thuật toán
3.4.3.1 Quá trình tiền xử lý dữ liệu
Trước khi huấn luyện các email được đưa qua bước tiền xử lý
như sau:
+ Loại bỏ các thẻ định dạng HTML trong email
+ Loại bỏ các từ nối câu và các từ không có ý nghĩa trong
email.
+ Các ký tự số vì không nói lên được ý nghĩa của email.
+ Chuyển toàn bộ nội dung email sang dạng nhị phân
3.4.3.2 Quá trình huấn luyện
Input: 5.000 email HAM đã được xử lý.

Output: Tập bộ dò r-chunk
3.1.4.3. Quá trình phân biệt self/non-self:
Input: Tập bộ dò r-chunk, tập email test gồm m email HAM và
n email SPAM (m + n = 1000 email)
Output: Các đánh giá DR, FPR và Acc.
Bảng 3.1. Kết quả khi chạy chương trình với 9 bộ test
HAM SPAM
100
900
200
800
300
700
400
600
500
500
600
400
700
300
800
200
900
100
Average

TP FP FN TN
894 0 6 100
793 0 7 200

695 0 5 300
596 0 4 400
496 0 4 500
399 0 1 600
297 0 3 700
200 0 0 800
100 0 0 900

DR
99.33%
99.13%
99.29%
99.33%
99.20%
99.75%
99.00%
100.00%
100.00%
99.45%

FPR
0%
0%
0%
0%
0%
0%
0%
0%
0%

0%

Acc
99.40%
99.30%
99.50%
99.60%
99.60%
99.90%
99.70%
100.00%
100.00%
99.67%

2.4.1. Một số định nghĩa
2.4.1.1. Self
2.4.1.2. NonSelf
2.4.1.3. Bộ dò
Bộ dò r-chunk
Bộ dò r-contiguous
2.4.1.4. Khả năng phát hiện của tập bộ dò
2.4.1.5. Hole
2.4.2. Thuật toán sinh tập bộ dò r-chunk
2.4.2.1. Thuật toán
- Tư tưởng: Ta sử dụng bảng A kiểu Boolean có n hàng và m
cột với:
n = 2r và m = ℓ – r + 1
Input: Tập các xâu S, ℓ, r
Output: ChunkD(S,r)
2.4.2.2. Độ phức tạp thuật toán

2.4.3. Thuật toán sinh tập bộ dò dạng r – contiguous
2.4.3.1. Thuật toán
Input: Tập các xâu S, ℓ, r
Output: ContD(S,r)
2.4.3.2. Độ phức tạp thuật toán
2.5. Các nghiên cứu gần đây
Chương 3.
KẾT QUẢ CÀI ĐẶT CÁC THUẬT TOÁN.
3.1 Tổng quan ứng dụng CNTT tại tỉnh Bắc Kạn
3.2 Mô hình tổng quát


10

Hình 2.1. Mô hình tổng quát của quá trình gửi và nhận thư điện tử
3.3 Mô hình thực tế ứng dụng lọc email Spam tại hệ thống email
nội bộ của Viễn tông tỉnh Bắc Kạn

11

Input: 5.000 email HAM được chọn ngẫu nhiên từ CSDL
TREC'07 để huấn luyện, ℓ và r.
Output: bảng băm A biểu diễn tập bộ dò dạng r-chunk
- Quá trình phân biệt self/nonself (HAM/SPAM)
Input: 9 bộ test với mỗi bộ test gồm 1.000 email ngẫu nhiên
được thay đổi tỷ lệ HAM/SPAM tương ứng từ 10% đến 90%
Output: Các giá trị TP, TN, FP, FN tương ứng với mỗi bộ test
và ba giá trị trung bình DR (Detection Rate), FPR (False Positive
Rate), Acc (Accuracy). Trong đó
+ TP: Số lượng email SPAM kết luận đúng

+ TN: Số lượng email HAM kết luận đúng
+ FP: Số lượng email HAM kết luận sai thành SPAM
+ FN: Số lượng email SPAM kết luận sai thành HAM
và các giá trị trung bình được tính như sau: DR = TP/(TP + FN)
FPR = FP/(TN + FP)
Acc = (TP + TN) / (TP + TN + FP + FN)
3.4.2 Cơ sở dữ liệu TREC'07
Bộ dữ liệu TREC'07 lưu trữ 75,419 thư điện tử trong đó có
50,199
SPAM và 25,220 HAM.

Hình 2.2. Mô hình mạng nội bộ của Viễn Thông Tỉnh Bắc Kạn
3.4 Ứng dụng hệ miễn dịch nhân tạo trong lọc thư rác
3.4.1 Phát biểu bài toán
- Quá trình huấn luyện

Phương pháp
Bước 1: Đọc 5.000 email HAM và 5.000 email SPAM
ngẫu nhiên từ TREC'07.
Bước 2: Tiền xử lý dữ liệu cho tập các email.
Bước 3: Đọc nội dung 5.000 email HAM sau khi xử lý dưới
dạng nhị phân độ dài ℓ.
Bước 4: Áp dụng thuật toán CHUNK_DETECTOR_NSA để
sinh tập bộ dò.