LỜI CẢM ƠN
Để hoàn thành đề tài này, em xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo
Ths. Nguyễn Văn Trường – Giảng viên Tin học, khoa Toán, Trường Đại học Sư
Phạm – Đại học Thái Nguyên, đã định hướng ý tưởng, tận tình giúp đỡ, chỉ bảo
em trong suốt quá trình thực hiện đề tài.
Em xin chân thành cảm ơn Ban giám hiệu nhà trường, Ban chủ nhiệm khoa
Toán cùng toàn thể các thầy, cô giáo trong khoa đã tận tình hướng dẫn, giúp đỡ
em thực hiện đề tài.
Bên cạnh đó, em xin gửi lời cảm ơn đến gia đình, bạn bè và những người
thân đã động viên giúp đỡ em trong suốt quá trình làm đề tài.
Trong quá trình tiến hành làm đề tài do chưa có nhiều kinh nghiệm nên
không tránh khỏi những thiếu sót và hạn chế. Vì vậy em rất mong nhận được sự
góp ý của các thầy cô và các bạn sinh viên để đề tài được hoàn thiện hơn.
Em xin chân thành cảm ơn!
Thái Nguyên, tháng 3 năm 2013
Sinh viên
Vũ Thị Nguyệt Thu
1
MỤC LỤC
2
DANH SÁCH KÍ HIỆU, TỪ VIẾT TĂT
Viết tắt Viết đầy đủ
HMD Hệ miễn dịch
NSA Negative Selfection Algorithm-Thuật toán chọn lọc tiêu cực
MHC Major Histocompatibility Complex
|X| Lực lượng của tập X
CNTT Công nghệ thông tin
TTNT Trí tuệ nhân tạo
Dpn Tập bộ dò kết hợp cây self và nonself
Dne Tập bộ dò sinh bởi cây nonself
Dp Tập bộ dò sinh bởi cây self

Biểu đồ 1. So sánh thời gian so khớp trên bộ dữ liệu “data20.inp” của 2 tập bộ
dò tương ứng với các giá trị r biến thiên.
Hình 4.11. File dữ liệu gốc
Hình 4.12. Tập bộ dò Dpn với r = 15
Hình 4.13. Tập bộ dò Dne với r = 15
Bảng 5. Tổng hợp kết quả với r biến thiên
Biểu đồ 2. So sánh thời gian so khớp trên bộ dữ liệu “data30.inp” của 2 tập bộ
dò tương ứng với các giá trị r biến thiên.
Hình 4.14. File dữ liệu gốc
Hình 4.15. Tập bộ dò Dpn với r = 15
Hình 4.16. Tập bộ dò Dne với r = 15
Bảng 6. Tổng hợp kết quả với r biến thiên
Biểu đồ 3. So sánh thời gian so khớp trên bộ dữ liệu “data40.inp” của 2 tập bộ
dò tương ứng với các giá trị r biến thiên.
Hình 4.17. File dữ liệu gốc
Hình 4.18. Tập bộ dò Dpn với r = 15
Hình 4.19. Tập bộ dò Dne với r = 15
Bảng 7. Tổng hợp kết quả với r biến thiên
Biểu đồ 4. So sánh thời gian so khớp trên bộ dữ liệu “data4goc.inp” của 2 tập
bộ dò tương ứng với các giá trị r biến thiên.
Biểu đồ 5. Mối quan hệ giữa tỉ lệ số node giảm và r
Biểu đồ 6. Trung bình tỉ lệ số node giảm
4
MỞ ĐẦU
 Lý do chọn đề tài
Một trong số những mối quan tâm của người sử dụng máy tính là sự phát
tán và xâm nhập của virus vào các hệ thống CNTT về cả chiều rộng và chiều
sâu. Virus máy tính thực sự trở thành hiểm họa, là mối đe dọa thường xuyên và
cấp bách đối với các hệ thống CNTT. Các hệ thống CNTT phần lớn sử dụng các
phần mềm chống virus (anti-virus (AV)) như là biện pháp phòng chống. Nhưng

giữa chọn lọc âm tính và chọn lọc dương tính
• Cài đặt chương trình.
 Phương pháp nghiên cứu
• Nghiên cứu lý thuyết: tìm đọc các tài liệu về lĩnh vực nghiên cứu
• Tham khảo ý kiến: tham khảo ý kiến cũng như cách thức nghiên cứu lý
thuyết về HMD nhân tạo của các thầy cô trong trường, các chuyên gia về
bảo mật.
• Thực nghiệm: cài đặt thuật toán đề xuất; so sánh, đánh giá độ phức tạp thời
gian với kết quả của các thuật toán chọn lọc âm tính gần đây.
 Cấu trúc đề tài
• Chương 1: Trình bày tổng quan về hệ miễn dịch sinh học và hệ miễn dịch
nhân tạo.
• Chương 2: Một số phương pháp sinh tập bộ dò
• Chương 3: Phương pháp sinh tập dò bằng cây nhị phân kết hợp chọn lọc âm
tính và chọn lọc dương tính
• Chương 4: Thực nghiệm cài đặt thuật toán ở chương 3.
6
Chương 1
TỔNG QUAN VỀ HỆ MIỄN DỊCH SINH HỌC VÀ HỆ MIỄN
DỊCH NHÂN TẠO NHÂN TẠO
1.1. Tổng quan về hệ miễn dịch sinh học
1.1.1. Khái niệm
Hệ miễn dịch (HMD) sinh học là tập hợp tất cả các cơ chế sinh học giúp
cho một cơ thể đa bào giữ được sự liên kết giữa các tế bào và các mô, đảm bảo sự
toàn vẹn của cơ thể bằng cách loại bỏ những thành phần bị hư hỏng cũng như các
chất và sinh vật xâm hại. Chức năng bảo vệ cơ thể bao gồm hai loại cơ chế miễn
dịch, lần lượt xuất hiện trong quá trình tiến hóa của các loài và liên hệ chặt chẽ với
nhau ở các động vật bậc cao.
1.1.2. Hệ miễn dịch thích nghi và hệ miễn dịch bẩm sinh
Hệ miễn dịch thích nghi và hệ miễn dịch bẩm sinh nằm ở tầng trong cùng,

cơ quan thụ cảm của chúng không có khả năng nhận diện được kháng nguyên. Kết
quả cuối cùng là những Lymphô bào có khả năng nhận diện được kháng nguyên.
+ Phép chọn lọc tiêu cực
Phép chọn lọc tiêu cực của các lymphô bào nhằm mục đích loại bỏ những
lymphô bào mà cơ quan thụ cảm của nó nhận diện được các tế bào do cơ thể tạo ra
và nó có thể tiêu diệt những tế bào này.
1.2. Tổng quan về hệ miễn dịch nhân tạo
8



!
"#$
"%&'()
1.2.1. Khái niệm về hệ miễn dịch nhân tạo
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ế.
1.2.2. Mô hình hệ miễn dịch nhân tạo

Hình 1.1. Cấu trúc phân tầng của HMD nhân tạo
- Tầng lĩnh vực ứng dụng: lĩnh vực ứng dụng khác nhau sẽ quyết định những
thành phần và cách thức biểu diễn khác nhau và dẫn tới các thao tác trên các thành
phần cũng khác nhau.
- Tầng biểu diễn các thành phần: Trong HMD nhân tạo phải biểu diễn được
hai thành phần quan trọng là kháng thể và kháng nguyên.
- Tầng các phương pháp đánh giá độ thích hợp: sử dụng nhiều phương pháp
khác nhau như khoảng cách Hamming, khoảng cách Euclid, hoặc khoảng cách
Mahattan.
9

&456
!7
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ỏ.
Hình 1.2. Sơ đồ khối thuật toán chọn lọc tích cực
+ Thuật toán chọn lọc tiêu cực (Negative Selfection Algorithms-NSA)
NSA của Forrest và các đồng nghiệp khá đơn giản [5]: Giả sử đã có một tập
Self-Peptide để tạo thành phức chất MHC-Self peptide, các cơ quan thụ cảm T-cell
nếu nhận diện được một self-peptide thì sẽ bị loại bỏ, trái lại nó sẽ được chọn như
một tế bào có khả năng miễn dịch và bổ sung vào quần thể có giá trị A. Thuật toán
chọn lọc tiêu cực được minh họa trong hình 1.5 có thể được tóm tắt như sau:
11
!
",
/0123
∈
&456
!7
*+
Bước 1. Khởi tạo: Sản sinh một quần thể tiềm năng P những T-cell 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.

ℓ
. Nó khớp được với một xâu khác
s
∈
Σ
ℓ
nếu có một i
∈
{1,…,ℓ – r + 1} với d[i,…,i + r – 1] = s[i,…,i+r–1].
2.1.2. Tập bộ dò ChunkD(S, r)
Cho một tập xâu kí tự S
⊆
Σ
ℓ
và một số nguyên r
∈
{1,…,ℓ}, kí hiệu (S, r) là
tập hợp các bộ dò r-chunk không khớp được với bất kỳ xâu nào trong S.
2.1.3. Khả năng phát hiện của tập bộ dò
Khả năng phát hiện của tập một tập bộ dò là số lượng nonself mà tập bộ dò
đó khớp được.
13
Một tập bộ dò được gọi là đầy đủ và không dư thừa nếu nó là tập bộ dò bé
nhất có khả năng phát hiện bằng khả năng phát hiện của mọi tập bộ dò đầy đủ.
2.1.4. Hole
Một xâu h
⊆
Σ
ℓ
được gọi là hole hay còn gọi là “lỗ hổng” nếu nó không

, mô hình tiền tố cho phần bù của S ký hiệu là minprefix(
S
)
là tập nhỏ nhất của mô hình tiền tố mô tả chính xác các xâu trong
S
.
14
2.2.2.3. Thuật toán
Thuật toán 1: Sinh mô hình tiền tố.
Input: Một tập S
⊆
Σ
r
không rỗng.
Output: Tập minprefix(
S
).
Procedure minprefix(
S
)
Begin
D
←
Ø
for mỗi s
∈
S do
begin
for i = 1 to r do
begin

ℓ
không rỗng, r
∈
{1 ℓ}, một xâu s
∈
Σ
ℓ
Output: - Tập D = ChunkD(S,r)
- Kết luận s là self hoặc nonself
Procedure Efficient-Chunk-Negative-Selfection;
Begin
D
←
Ø
for i = 1 to ℓ-r+1 do
begin
S
i
← {s[i… i + r-1] | s
∈
S};
D
i
← {(
π
,i)|
π
∈
minprefix(
S


1xxx = {1xxx},
kí hiệu x để chỉ kí tự tùy ý là 0 hoặc 1
+) i = 2
P
2
= s1[1]
]2[s1
= 00
P
2
là tiền tố của s2 nên loại p2
+) i = 3
P
3
= s1[1]s1[2]
]3[s1
= 011
P
3
không là tiền tố của bất kỳ s
∈
S nên
D = D

011x = {1xxx, 011x}
+) i = 4
P
4
= s1[1]s1[2]s1[3]

vào tập bộ dò. Nếu tập bộ dò đã đủ số lượng phần tử
N
R
thì sang bước 5. Nếu không quay lại bước 2.
• B5: Kết thúc.
Bạn đọc muốn tìm hiểu rõ hơn về thuật toán sinh bộ dò r-contiguous đơn giản có
thể đọc thêm tài liệu [4]
2.3.2. Thuật toán sinh tập bộ dò dựa vào bảng băm
Việc so khớp hai xâu bất kì thực chất là so khớp lần lượt r vị trí liên tiếp (r
≤
ℓ). Do vậy, chắc chắn trong quá trình so khớp ta phải nhiều lần so khớp các
đoạn có độ dài r giống nhau. Công việc này làm tốn nhiều thời gian tính toán. Để
khắc phục nhược điểm đó, trong tập các xâu lưu trong S, ta có thể loại những xâu
trùng nhau để tăng hiệu suất sử dụng bộ nhớ. Tuy nhiên công việc này lại đòi hỏi
mất thêm thời gian tính toán.
Phương pháp tốt hơn cho công việc này là sử dụng mô hình bảng băm.
2.3.2.1. Phương pháp bảng băm
Tư tưởng: Ta sử dụng bảng A kiểu boolean có n hàng và m cột với:
n = 2
r
và m = ℓ – r + 1
Trong đó:
18
+ A[i, j] = 1: đoạn bit từ bit j đến bit thứ j + r – 1 của các s
∈
S có giá trị là i
trong hệ cơ số 10.
+ A[i, j] = 0: trong trường hợp ngược lại.
- Bảng A được xây dựng bằng cách đọc lần lượt các đoạn r bit liên tiếp của
các xâu trong S rồi tính giá trị thập phân của đoạn bit đó và gán A[i, j] tương ứng

= (5)
10
Vậy A[5, 2] = 1
+ Với j = 3: ta có đoạn bit 011
(011)
2
= (3)
10
Vậy A[3, 3] = 1
* Xét xâu 2: s2 = 11001
+ Với j = 1: ta được đoạn bit 110
(110)
2
= (6)
10
Vậy A[6, 1] = 1
+ Với j = 2: ta được đoạn bit 100
(100)
2
= (4)
10
Vậy A[4, 2] = 1
+Với j = 3: ta có đoạn bit 001
(001)
2
= (1)
10
Vậy A[1, 3] = 1
* Xét xâu 3: s3 = 01010
+ Với j = 1: ta có đoạn bit 010

Vì A là bảng hai chiều, được lưu trữ trên bộ nhớ trong nên việc truy cập đến
phần tử A[i, j] chỉ mất thời gian là O(1). Dù dữ liệu bảo vệ có thay đổi, rất lớn đi
nữa thì ta vẫn chỉ cần một bảng A kích thước cố định 2
r
dòng,
(ℓ - r + 1) cột.
Bạn đọc muốn tìm hiểu chi tiết về thuật toán sinh tập bộ dò bằng bảng băm
có thể đọc thêm [4].
2.4. Phương pháp sinh tập bộ dò bằng cây nhị phân
Với việc sinh tập bộ dò theo phương pháp tiền tố như mô tả ở trên thì mỗi
lần sinh được một xâu ta lại phải kiểm tra xem xâu đó có khớp với s không, do đó
sẽ rất tốn chi phí tính toán lại.
Để khắc phục nhược điểm đó, sử dụng cấu trúc dữ liệu cây nhị phân.
21
2.4.1. Ý tưởng
Đầu tiên ta tạo một rừng cây với số lượng ℓ-r+1 cây là với các gốc được lưu
bởi mảng root[1…ℓ-r+1]. Mỗi cây có gốc là root[i] sẽ được tạo ra trực tiếp từ S
chính là phần bù của D
i
, là {0,1}
r
\D
i
, i = 1,…, (ℓ - r + 1). Sau đó chúng ta thực
hiện điều chỉnh cây đó để nó tương đương với D
i
. Việc khớp r đoạn bít tương
đương với việc duyệt trên cây. Trong các hình vẽ minh họa cây, để đơn giản chúng
ta mặc định con trái được gán nhãn là 0 và con phải được gán với nhãn là 1.
2.4.2. Thuật toán sinh tập bộ dò r-Chunk bằng cây nhị phân

Ví dụ 3.1. Cho S = {s
1
= 01111; s
2
= 00111; s
3
= 10000; s
4
= 10001;
s
5
= 10010} ⊂ {0,1}
5
.
Bước 1 : Chọn ℓ = 5 và r = 3
Bước 2 :
Với s
1
= 01111 ta sẽ có (011, 1), (111, 2), (111, 3)
root[1] root[2] root[3]
Hình 2.1. Một phần của các cây nhị phân sinh ra bởi s
1
= 01111
Với s
2
= 00111 ta sẽ có (001, 1); (011, 2); (111, 3)
root[1] root[2] root[3]
23
Hình 2.2. Một phần của cây nhị phân khi thêm s
2