HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
KHOA CÔNG NGHÊ THÔNG TIN I
BÁO CÁO THỰC TẬP
Giảng viên hướng dẫn : TS. Hoàng Xuân Dậu
Sinh viên : Đào Thanh Tùng
Lớp : D08CNPM1
HÀ NỘI, 7/2012
I.Giới thiệu
Thiết kế và cái đặt hệ thống phát hiện đột nhập là một vấn đề nghiên cứu quan trọng
trong an toàn mạng. Các hệ thống phát hiện đột nhâp được học và đề xuất gặp phải các thách
thức trong môi trường internet. Không phải là sự thổi phòng trạng thái mà một hệ thống phát
hiện đột nhập phải là một hệ thống hiện đại. Kĩ thuật phát hiện đột nhập có thể chia thành 2
nhóm : phát hiện sai và phát hiện dị thường.
Phát hiện sai nhận ra các các hành động đột nhập dựa trên các hành vi đã biết từ quá
trình phát triển. Phát hiện sai tương tự các phần mềm diệt vi rút. Chúng so sánh dữ liệu với
cơ sở dữ liệu virus có sẵn. Phát hiện sai là tập hợp các hành vi tấn công từ cơ sở dữ liệu thuộc
tính. Do đó chúng có hạn chế không thể phát hiện đột nhập mới xảy ra ví dụ các sự kiện chưa
xảy ra bao giờ. Phát hiện di thường khác biệt so với phát hiện sai.
Phát hiện dị thường dựa trên phân tích dữ liệu các sự kiện và nhận ra các mẫu của các
hành động xuất hiện một cách bình thường. Nếu một sự kiện xảy ra ngoài mẫu, chúng được
báo cáo như một xâm nhập. Có thể xem phương pháp này là phương pháp tiếp cận nửa học
máy.
Có nhiều kĩ thuật học máy được sử dụng phát hiện đột nhập dị thường. Qiao giới thiệu
một phương pháp phát hiện đột nhập dựa vào mô hình ẩn của Markov để phân tích tập dữ liệu
UNM. Lee thiết lập mô hình phất hiện đột nhập kết hợp luật kết hợp và logic mờ điều chế
mãu cho phất hiện dột nhâp. Mohajeran phát triển hệ thống phát hiện đôt nhập kết hợp mạng
nơron và logic mờ phân tích tập dữ liệu KDD, Wang áp dụng thuật toán di truyền dánh giá
hàm thành viên cho khai phái mờ luật kết hợp.
SVM (SVM) là một kĩ thuật phổ biến cho phát hiện đột nhâp dị thường. SVM huấn
luyện vector vào không gian đặc trưng có số chiều lớn hơn, gán nhãn mỗi vector vào các lớp.
SVM phân loại dữ liệu bởi giới hạn một tập vector hỗ trợ chúng là thành viên của tập dữ liệu

trình (1) được viết như sau:
(3)
Với là biến biểu diễn tọa độ thứ i của vector x.
Bản chất SVM tìm các siêu phẳng:
(4)
để chia các mẫu huấn luyện thành dương và âm. Siêu phẳng này được gọi là đường biên quyết
định hoặc bề mặt quyết định.
Về mặt hình học, siêu phẳng <w.x> + b=0 phân chia không gian đầu và othành hai nửa
không gian: một nửa cho các mẫu dương và một nửa khác cho các mẫu âm. Nhớ lại rằng siêu
phẳng thường được gọi là một đường trong một không gian 2-chiều và một plane trong một
không gian 3 chiều.
Hình 1 cho thấy một ví dụ trong một không gian 2 chiều. Mẫu dương được biểu diễn bởi hình
chữ nhật đặc nhỏ, và mẫu âm được biểu diễn bởi hình tròn rỗng nhỏ. Đường dày ở giữa là các
siêu phẳng biên quyết định (một đường trong trường hợp này), nó chia các điểm dữ liệu
dương (phía trên đường) và âm (phía dưới đường). Phương trình (1), gọi là quy tắc quyết định
của phân lớp SVM, được sử dụng để tạo quyết định phân lớp trên các trường hợp thử
nghiệm.
Hình 1 (A) A là một đường thẳng chia tập dữ liệu và (B) các biên quyết dịnh có thể
1.SVM tuyến tính : trường hợp có thể chia
Phần này nghiên cứu trường hợp đơn giản của SVM tuyến tính. Nó giả thiết rằng các dữ liệu
dương và âm là có thể chia tuyến tính.
Theo đại số tuyến tính, chúng ta biết rằng trong <w.x> + b = 0, w định nghĩa một đường pháp
tuyến với siêu phẳng (xem hình 2). Không thay đổi vector chuẩn w, biến b di chuyển siêu
phẳng song song với chính nó. Cũng lưu ý rằng <w.x> + b = 0 có một mức độ tự do vốn có.
Chúng ta có thể thay đổi tỉ lệ các siêu phẳng thành
mà không thay đổi hàm/ siêu phẳng.
Hình 2 Siêu phẳng phân chia và lề của của SVM : Vector hỗ trợ khoanh tròn
Khi SVM đạt cực đại lề giữa các điểm dữ liệu dương và âm, hãy tìm lề đó. Gọi d+ là khoảng
cách ngắn nhất từ siêu phẳng để chia tới các điểm dữ liệu dương gần nhất, d- là khoảng cách
ngắn nhất từ siêu phẳng để chia tới các điểm dữ liệu âm gần nhất. Khi đó lề của siêu phẳng

và lồi và các ràng buộc là tuyến tính trong các thông số w và b, chúng ta có thể sử dụng
phương pháp hệ số nhân Lagrange chuẩn để giải quyết nó.
Thay vì đánh giá hàm mục tiêu, ta cần đánh giá Lagrangian của vấn đề,nó xem xét các ràng
buộc cùng một lúc. Cần quan tâm đến các ràng buộc là rõ ràng bởi vì chúng giảm bớt các giải
pháp khả thi. Khi ràng buộc bất đẳng thức được biểu diễn sử dụng “ ”, các Lagrange được
xây dựng bằng cách các ràng buộc được nhân với các hệ số nhân dương và được trừ vào hàm
mục tiêu, cụ thể là:
(12)
trong đó 0 là các hệ số nhân lagrange.
Lí thuyết đánh giá nói rằng một giải pháp đánh giá cho biểu thức phải thỏa mãn các điều kiện
nhất định, được gọi là các điều kiện Kunhn- Tucker, nó giữ vai trò quan trọng trong đánh giá
ràng buộc. Ở đây, ta giới thiệu tóm tắt các điều kiện này. Các vấn để tổng quá hóa là :
(13)
Trong đó f là hàm mục tiêu và la hàm ràng buộc. Lagrangian của (13) là,
(14)
Một giải pháp đánh giá vấn đề trong (13) phải thỏa mãn các điều kiện cần thiết (nhưng chưa
đủ) sau : (15)
(16)

(17)
(18)
Các điều kiện này được gọi là các điều kiện Kuhn-Tucker, chú ý rằng (16) là tập các ràng
buộc bản đầu có trong (13). Điều kiện (18) được gọi là điều kiện bổ sung, nó ngụ ý rằng tại
điểm giải quyết :
Để cực tiểu vấn đề (11), các
điều kiện Kuhn-Tucker là :


Để SVM là hữu dụng, nó phải cho phép nhiễu trong các dữ liệu huấn luyện. Tuy nhiên, với dữ
liệu nhiễu thì SVM chia tuyến tính sẽ không tìm ra một hướng giải pháp nào bởi vì các ràng
buộc không thể đạt được. Chẳng hạn, trong hình 3, có một điểm âm trong miền dương, và có
một điểm dương trong miền âm. Một cách rõ ràng hơn, không có giải pháp có thể được tìm
thấy cho vấn đề này.
Nhớ lại rằng nền tảng cho trường hợp chia tuyến tính là:
(27)
Để cho phép lỗi trong dữ liệu, chúng ta có thể nới lỏng các rằng buộc lề dc bẳng cách đưa ra
các biến slack, () như sau:
Do đó chúng ta có các rằng buộc mới :
Biểu diễn hình học được minh họa trong hình 3, ở đây có hai điểm dữ liệu lỗi , (được khoanh
tròn) trong miền không chính xác.
Hình 3 Trường hợp không phân chia đúng
Chúng ta cũng cần để ý các lỗi trong hàm mục tiêu. Một cách thông thường là gán một giá trị
mở rộng cho các lỗi để thay đổi hàm mục tiêu để:
(28)
Với C là một tham số được quy định bởi người dùng. K=1 được sử dụng phổ biến, nó có tiến
bộ là không phải mà cũng không phải hệ số nhân Lagrangian của nó xuất hiện trong biểu
thức đối ngẫu. Ta chỉ quan tâm thảo luận trường hợp k=1 ở phía dưới đây.
Vấn đề đánh giá mới trở thành:
(29)
Công thức này được gọi là lề mềm SVM. Lagrangian cơ bản (biểu diễn bởi ) của biểu thức
này như sau:
(30)
Trong đó, , là các hệ số nhân Lagrange. Điều kiện Kuhn-Tucker tốt nhất là những điều kiện
sau :
(31)
(32)
(33)
(34)

(43)
Luật quyết định cho phân lớp (testing) giống như trường hợp có thể chia, cụ thể là
sign(<w.x> +b). Lưu ý rằng cả phương trình (43) và (41) thì không cần được tính toán cụ
thể. Chủ yếu dành cho sử dụng các hàm nhân để xử lí các đường biên quyết định không
tuyến tính.
Cuối cùng, ta vẫn có một vấn đề là xác định tham số C. Giá trị của C thường chọn bởi thử một
dãy các giá trị trên bộ dữ liệu huấn luyện để xây dựng bộ phân loại đa lớp và sau đó test
chúng trên bộ dữ liệu xem xét, trước khi chọn một cái mà đưa ra kết quả phân loại tốt nhất
trên bộ dữ liệu xem xét. Xem xét chéo là được sử dụng phổ biến như vậy.
3.SVM phi tuyến tính : hàm nhân
Ở hai trường hợp các mẫu dương và âm có thể được tách tuyến tính, tức là đường biên quyết
định phải là một siêu phẳng. Tuy nhiên đối với nhiều bộ dữ liệu thực tế, các đường biên
quyết định là không tuyến tính. Để giải quyết với dữ liệu chia không tuyến tính công thức
tương tự và các kĩ thuật giải quyết như đối với trường hợp tuyến tính vẫn được sử dụng. Ta
chỉ chuyển dữ liệu đầu vào từ không gian ban đầu của nó sang không gian khác (thường là
không gian có số chiều nhiều hơn) do đó một đường biên quyết định tuyến tính có thể chia
các mẫu dữ liệu dương và âm trong không gian sau khi chuyển đổi, cái mà được gọi là
không gian đặc trưng. Ý tưởng cơ bản là ánh xạ dữ liệu từ không gian X đầu vào sang không
gian đặc trưng F thông qua một phép ánh xạ không tuyến tính ,
(44)
Sau khi ánh xạ bộ dữ liệu huấn luyện ban đầu {(,), (,), …,(,)} trở thành:
(45)
Phương pháp giải quyết SVM tuyến tính như vậy sau đó được áp dụng vào không gian F.
Hình 4 mô tả xử lí như vậy. Trong không gian đầu vào (hình bên trái), các mẫu dữ liệu huấn
luyện không thể chia tuyến tính. Trong không gian đặc trưng đã thay đổi (hình bên phai),
chúng có thể được chia tuyến tính.
Hình 4 Chuyển đổi từ không gian đầu vào X sang không gian đặc trưng F
Với sự chuyển đổi này, vấn đề đánh giá trong (11) trở thành:
(46)
Biểu thức đối ngẫu tương ứng của nó là:

cách sử dụng hàm nhân (51), số lượng các chiều trong không gian đặc trưng không quan
trọng.
Các dẫn xuất trong (52) là chỉ cho mục đích minh họa. Trong thực tế, ta không cần phải tìm
thấy các hàm ánh xạ. ta chỉ đơn giản là có thể áp dụng các hàm nhân trực tiếp. Đó là, chúng ta
thay thế tất cả các tích vô hướng φ 〈 (x) φ ⋅ (z) 〉 trong (47) và (48) với hàm nhân K (x, z) (ví
dụ, nhân đa thức trong (51). Chiến lược trực tiếp này cách sử dụng một hàm nhân để thay
thế tích vô hướng trong không gian đặc trưng được gọi là nhân trick. Chúng ta không bao
giờ biết rõ ràng φ là gì.Tuy nhiên, câu hỏi là, làm thế nào để chúng ta biết liệu có hay không
một hàm là một KerNel mà không thực hiện phép lấy đạo hàm như thế trong (52)? Đó là,
làm thế nào
chúng ta biết rằng một hàm nhân thực sự là một tích vô hướng trong một số không gian đặc
trưng? Câu hỏi này được trả lời bởi một định lý được gọi là lí thuyết Mercer
Rõ ràng rằng ý tưởng của nhân tổng quát hóa tích vô hướng trong một số không gian đầu
vào. Tích vô hướng cũng là một nhân với phép ánh xạ đặc trưng là xác định
(53)
Thông thường sử dụng các kernel bao gồm
(54)
(55)
4.Cải tiến SVM với trọng số đặc trưng
Các hàm nhân thường được sử dụng là hàm tuyến tính, hàm đa thức, hàm bán kính cơ bản,
hàm xích ma. Tuy nhiên các hàm đó không xem xét sự khác biệt giữa các đặc trưng của dữ
liệu. Từ hàm nhân tổng quát có thể thấy rằng dữ liệu huấn luận và test tương đương.
Xử lý các đặc trưng tương đương là không hiệu quả và làm giảm độ chính xác của SVM. Một
giải pháp được JingTao Yao, Songlun Zhao, and Lisa Fan đề xuất xem xét tầm quan trọng của
các đặc trưng bằng cách them trọng số của hàm nhân. Trọng số được sử dụng để đánh giá tầm
quan trọng của mỗi đặc trưng. Công thức của hàm nhân mới trong đó w là một vector gồm
cố trọng số của đặc trưng của tập dữ liệu. Khi đó hàm biệt thức phi tuyến tính với trọng số đặc
trưng
Nhân cải tiến này là độc lập với hàm nhân đặc biệt. Với các ứng dụng khác nhau, có thể chọn
hàm nhân thích hợp áp dụng trọng số đặc trưng. Chúng ta sử dụng lý thuyết tập thô ddeeer

TP : số lượng phân loại chính xác của những mẫu dương (true positive)
FN: số lượng phân loại không chính xác của những mẫu dương (false negative)
FP: số lượng phân loại không chính xác của những mẫu âm (flase positve)
TN: số lượng phân loại chính xác của những mẫu âm (true negative)
Dựa trên ma trận nhầm lẫn, độ chính xác(p) và độ hồi nhớ (r) của lớp dương được định
nghĩa:
Nói cách, đô chính xác p là số phân loại chính xác mẫu dương chia cho tổng số các mẫu được
phân loại là dương. Độ hồi nhớ r là số phân loại chính xác mẫu dương chia cho tổng số các
mẫu thực tế dương trong các thiết lập thử nghiệm. Các ý nghĩa trực quan của hai biện pháp
này là khá rõ ràng.
Tỉ lệ dương tính thật (TPR) được định nghĩa là một phần trong các trường hợp dương tính
thực được phân loại chính xác :
Tỷ lệ dương tính giả (FPR) được định nghĩa là một phần trong số các trường hợp âm tính thực
tế được phân loại vào lớp tích cực,
TPR cơ bản của nhớ lại của lớp dương tính và cũng được gọi là nhạy cảm trong thống
kê.Ngoài ra còn có một biện pháp khác trong thống kê được gọi là đặc trưng, đó là tỷ lệ đúng
âm tính (TNR), hoặc nhớ lại của lớp tiêu cực. TNR được định nghĩa như sau:
III.Kết luận
SVM là một hệ thống học tuyến tính nhằm tìm đường quyết định mức lền lớn nhất để chia
điểm dương và âm. SVM tương đương với việc giải quyết bài toán tối ưu bậc hai. Ranh giới
quyết định phi tuyến tính được tìm qua việc chuyển đổi dữ liệu ban đầu sang không sang đặc
đặc trưng có số chiều nhiều hơn. Tuy nhiên việc chuyển đổi này không chính xác hoàn toàn.
Do đó hàm nhân được sử dụng để tính toán tích vô hướng cần trong học máy mà không cần
hàm chuyển đổi. Tuy nhiên SVM cũng có một số hạn chế :
- SVM chỉ làm việc với không gian đầu vào là các số thực
→Đối với các thuộc tính định danh (nominal), cần chuyển các giá trị định danh thành
các giá trị số.
- SVM chỉlàm việc (thực hiện phân lớp) với 2 lớp
Đối với các bài toán phân lớp gồm nhiều lớp, cần chuyển thành một tập các bài toán
phân lớp gồm 2 lớp, và sau đó giải quyết riêng rẽ từng bài toán 2 lớp này.