ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
-------------------

LÊ HỮU DŨNG

PHÁT HIỆN BẤT THƯỜNG CỦA MẠNG
THEO CÁCH TIẾP CẬN HỌC MÁY

LUẬN VĂN THẠC SĨ KHOA HỌC

Hà Nội – Năm 2014


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN
-------------------

LÊ HỮU DŨNG

PHÁT HIỆN BẤT THƯỜNG CỦA MẠNG
THEO CÁCH TIẾP CẬN HỌC MÁY
Chuyên ngành: Cơ sở Toán học cho Tin học
Mã số:

60460110

LUẬN VĂN THẠC SĨ KHOA HỌC
NGƯỜI HƯỚNG DẪN KHOA HỌC:
PGS.TS. Lê Trọng Vĩnh

Hà Nội – Năm 2014


MỤC LỤC
Danh mục hình vẽ .......................................................................................................3
Danh mục bảng biểu....................................................................................................4
LỜI CẢM ƠN .............................................................................................................5
LỜI CAM ĐOAN .......................................................................................................6
LỜI NÓI ĐẦU ............................................................................................................7
CHƯƠNG 1: TỔNG QUAN .......................................................................................8
1

Sự phát triển của mạng máy tính ..........................................................................8

2

Nguy cơ bị tấn công của mạng .............................................................................9

3

Các phương pháp phát hiện xâm nhập mạng hiện có.........................................12

3.1

Nhận diện dấu hiệu .........................................................................................12

3.2

Phát hiện bất thường .......................................................................................13


3.2.1

Bằng số liệu thống kê ..................................................................................13

3.2.2

Theo cách tiếp cận học máy ........................................................................13

CHƯƠNG 2: THUẬT TOÁN HỌC MÁY SUPPORT VECTOR MACHINE
(SVM)........................................................................................................................15
2.1.

Giới thiệu .....................................................................................................15

2.2.

Ý tưởng của SVM ........................................................................................15

2.3.

Nội dung của SVM ......................................................................................16

2.3.1.

Cơ sở lý thuyết .........................................................................................16

2.3.2.

Bài toán phân 2 lớp với SVM ..................................................................18


2.3.3.

Phân nhiều lớp với SVM ..........................................................................22

2.3.4.

Các bước chính của thuật toán SVM .......................................................23

2.3.5.

Thuật toán SVM trong trường hợp dữ liệu được phân tách tuyến tính. ...24

2.3.6. Thuật tốn SVM trong trường hợp dữ liệu không phân tách tuyến tính
trong khơng gian đặc trưng ....................................................................................36
2.3.6.1.

Nhận xét ................................................................................................36

2.3.6.2.

Dạng 1 của thuật toán SVM, bài toán C – SVC ...................................36

2.3.6.3.

Dạng 2 của thuật toán SVM, bài toán v-SVC .......................................41

2.3.7.

SVM nhiều lớp .........................................................................................42
1



2.3.8.

Lựa chọn hàm nhân cho các ứng dụng .....................................................43

2.3.9.

Lựa chọn các tham số cho hàm nhân RBF ...............................................44

2.4.

Các thư viện, phần mềm hỗ trợ phân lớp dữ liệu theo thuật tốn SVM ......44

CHƯƠNG 3: MƠ HÌNH PHÁT HIỆN BẤT THƯỜNG MẠNG SỬ DỤNG
THUẬT TOÁN HỌC MÁY SVM............................................................................46
3.1.

Thu thập dữ liệu ...........................................................................................47

3.2.

Bóc tách Header các gói tin .........................................................................50

3.3.

Tạo dữ liệu đầu vào cho q trình huấn luyện ............................................59

3.4.


Dựng mơ hình phân lớp ...............................................................................59

3.5.

Kiểm tra chéo và điều chỉnh tham số ..........................................................59

3.6.

Ghi nhận mơ hình ........................................................................................59

CHƯƠNG 4: THỰC NGHIỆM VÀ KẾT QUẢ .......................................................60
4.1.

Định dạng dữ liệu đầu vào ...........................................................................61

4.2.

Huấn luyện, tạo mô hình..............................................................................63

4.3.

Kiểm tra mơ hình và điều chỉnh tham số .....................................................65

CHƯƠNG 5: KẾT LUẬN ........................................................................................67
5.1.

Kết quả đạt được ..........................................................................................67

5.2.


Hướng nghiên cứu tương lai ........................................................................67

TÀI LIỆU THAM KHẢO .........................................................................................68

2


Danh mục hình vẽ
Hình 2.1 Siêu phẳng f phân chia dữ liệu học thành 2 lớp + và – với khoảng cách
biên lớn nhất. Các điểm gần f nhất (điểm được khoanh trịn) là các Support Vector.
...................................................................................................................................16
Hình 2.2. Minh họa cho bài tốn phân hai lớp ..........................................................18
Hình 2.3. Minh họa bài tốn phân hai lớp với Thuật tốn SVM ..............................21
Hình 2.4. Bài toán SVM trong trường hợp dữ liệu mẫu khơng phân tách tuyến tính
...................................................................................................................................21
Hình 2.5. Minh họa về sự phân tách dữ liệu trong khơng gian đặc trưng.................24
Hình 2.7. Dữ liệu phân tách tuyến tính trong khơng gian đặc trưng qua phép ánh xạ
 ...............................................................................................................................27
Hình 3.1. Cấu trúc tổng thể mơ hình phát hiện bất thường trong giai đoạn huấn
luyện ..........................................................................................................................46
Hình 3.2 Phát hiện gói tin bất thường trong thời gian thực ......................................47
Hình 3.3: Cấu trúc gói tin [8] ....................................................................................52
Hình 3.4: Quá trình thêm header cho dữ liệu truyền qua các tầng của mạng ...........53
Hình 3.5: Thuật tốn bóc tách header từ một gói tin ................................................58
Hình 3.6: Một phần tệp dữ liệu theo khn dạng đầu vào LibSVM.........................59
Hình 4.1: Giao diện chương trình thực nghiệm ........................................................60
Hình 4.2: Một phần nội dung tệp header của dữ liệu ngày thứ 2, tuần thứ 1 (xem ở
dạng Hexa) ................................................................................................................61
Hình 4.3: Tệp dữ liệu phục vụ huấn luyện ................................................................61
Hình 4.4: Giao diện chương trình khi tiến hành huấn luyện .....................................63

Hình 4.5: Giao diện chương trình khi đang chạy bước dự đốn (prediction) với dữ
liệu kiểm tra...............................................................................................................65

3


Danh mục bảng biểu
Bảng 3.1: Các bộ dữ liệu năm 1999 của dự án DARPA intrusion detection
evaluation..................................................................................................................48
Bảng 3.2: Bảng mô tả các kiểu tấn công đã được triển khai trong tuần 2 của bộ dữ
liệu năm 1999 trong dự án DARPA intrusion detection evaluation ........................48
Bảng 3.3: Ý nghĩa các thành phần trong một gói tin ................................................52
Bảng 3.4: IP Header ..................................................................................................53
Bảng 3.5: TCP Header ..............................................................................................55
Bảng 3.6: Các đặc trưng dùng để phân lớp các gói tin .............................................56
Bảng 4.1: Kết quả dự đoán trên tệp dữ liệu kiểm tra ................................................66

4


LỜI CẢM ƠN
Trước tiên, em xin được gửi lời cảm ơn chân thành nhất của mình tới PGS.
TS Lê Trọng Vĩnh - giảng viên khoa Toán - Cơ - Tin học, Trường Đại học Khoa
học Tự nhiên, Đại học Quốc gia Hà Nội đã dành nhiều công sức hướng dẫn em thực
hiện luận văn này!
Em cũng xin chân thành cảm ơn các thầy cơ trong khoa Tốn – Cơ – Tin
học, trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội đã nhiệt tình
truyền đạt kiến thức, kinh nghiệm, phương pháp nghiên cứu và cả sự say mê khoa
học tới nhiều lứa học viên cao học – trong đó có em!
Với sự tận tình chỉ bảo của các thầy, các cô, em đã rất cố gắng để hồn thành

luận văn này. Tuy nhiên, do em cịn nhiều điểm hạn chế nên chắc hẳn luận văn này
vẫn còn tồn tại các thiếu sót. Em kính mong tiếp tục nhận được những ý kiến góp ý,
chỉ bảo của các thầy, các cô cũng như các bạn học viên để em tiếp tục hồn thiện
chun mơn của bản thân.
Em xin trân trọng cảm ơn!
Học viên

Lê Hữu Dũng

5


LỜI CAM ĐOAN
Tôi xin cam đoan luận văn là công trình nghiên cứu của bản thân. Các số liệu,
kết quả được trình bày trong luận văn này là trung thực và chưa từng được
công bố trong bất kỳ luận văn nào trước đây.
Học viên

Lê Hữu Dũng

6


LỜI NÓI ĐẦU
Các hoạt động kinh tế, xã hội của con người ngày càng sử dụng nhiều đến
máy tính và các thiết bị công nghệ. Cùng với điều này, nhu cầu sử dụng mạng máy
tính để trao đổi thơng tin, chia sẻ tài nguyên cũng ngày càng tăng cao. Bên cạnh đó,
vấn đề đảm bảo cho sự an tồn của thơng tin cũng như của mạng máy tính ngày
càng trở nên bức thiết. Để đảm bảo an tồn cho thơng tin và hoạt động của mạng
máy tính thì cần triển khai nhiều giải pháp đồng bộ. Trong đó, phát hiện sớm các

bất thường của mạng được coi là một khâu quan trọng giúp đảm bảo an toàn cho
một mạng máy tính. Có nhiều cách hiện đang được nghiên cứu, triển để phát hiện
bất thường trong mạng như sử dụng phương pháp nhận diện dấu hiệu, phương pháp
thống kê và phương pháp sử dụng các thuật tốn học máy. Trong đó, các phương
pháp học máy cho phép đưa ra những kết quả phát hiện bất thường có độ chính xác
cao và đặc biệt là ln có thể cải tiến để cho kết quả cao hơn.
Luận văn này với tên gọi “Phát hiện bất thường của mạng theo cách tiếp
cận học máy” tập trung tìm hiểu việc phát hiện các gói tin trong mạng là bình
thường hay bất thường bằng cách áp dụng thuật tốn học máy để phân lớp các gói
tin.
Luận văn bao gồm 5 chương với nội dung như sau:
Chương 1: Tổng quan
Chương 2: Thuật toán học máy Support Vector Machines (SVM)
Chương 3: Mơ hình phát hiện bất thường trong mạng sử dụng thuật toán học máy
SVM
Chương 4: Thực nghiệm và kết quả
Chương 5: Kết luận

7


CHƯƠNG 1: TỔNG QUAN
1

Sự phát triển của mạng máy tính

Với sự phát triển như vũ bão của các mạng máy tính trong kỉ ngun thơng tin
truyền thơng, khoảng cách vật lý đã dần trở nên vô nghĩa. Chúng ta đang được
chứng kiến rất nhiều lợi ích mà mạng máy tính mang lại cho sự phát triển của đời
sống, công nghệ, kinh tế và xã hội.

Trong lĩnh vực thông tin, thương mại điện tử: email đã gần như thay thế hoàn tồn
thư truyền thống; Các dịch vụ viễn thơng truyền thống cũng đang bị cạnh tranh
mạnh mẽ bởi các dịch vụ Over-The-Top (OTT) trên nền Internet; Báo điện tử đang
là đối thủ cạnh tranh trực tiếp, gây nên rất nhiều “sự ra đi” của báo giấy; Các cửa
hàng trực tuyến đang ngày càng phát triển, mang đến những lợi ích to lớn cho cả
người mua và người bán.
Trong lĩnh vực chính phủ điện tử: Hạ tầng mạng máy tính, cơng nghệ thông tin –
truyền thông phát triển cùng với khả năng tiếp cận các sản phẩm công nghệ của
người dân đã tạo ra những điều kiện thuận lợi để nhiều nước triển khai chính phủ
điện tử và thành cơng. Ngay ở nước ta, nhiều dịch vụ hành chính cơng đã được triển
khai trực tuyến, mang lại nhiều lợi ích cho người dân như: tờ khai Hải quan điện tử,
khai thuế trực tuyến, đăng ký cấp Hộ chiếu trực tuyến tại Công an TP Hà Nội, …
Các dịch vụ trên nền “Đám mây”: Trong vài năm qua, Công nghệ thông tin (IT) đã
bắt đầu một mẫu hình mới - điện tốn đám mây. Mặc dù điện toán đám mây chỉ là
một cách khác để cung cấp các tài nguyên máy tính, chứ khơng phải là một cơng
nghệ mới, nhưng nó đã châm ngịi một cuộc cách mạng trong cách cung cấp thơng
tin và dịch vụ của các tổ chức. Điện toán đám mây là một giải pháp tồn diện cung
cấp cơng nghệ thơng tin như một dịch vụ. Nó là một giải pháp điện tốn dựa trên
Internet ở đó cung cấp tài nguyên chia sẻ giống như dòng điện được phân phối trên
lưới điện. Các máy tính trong các đám mây được cấu hình để làm việc cùng nhau và
các ứng dụng khác nhau sử dụng sức mạnh điện toán tập hợp cứ như thể là chúng

8


đang chạy trên một hệ thống duy nhất. Những lợi ích mà điện toán đám mây mang
lại gồm:
-

Chi phí giảm: Điện tốn đám mây có thể làm giảm cả chi phí vốn lẫn chi phí

vận hành vì các tài ngun chỉ được mua khi cần và chỉ phải trả tiền khi sử
dụng.

-

Cách sử dụng nhân viên được tinh giản: Việc sử dụng điện tốn đám mây
giải phóng đội ngũ nhân viên quý giá cho phép họ tập trung vào việc cung
cấp giá trị hơn là duy trì phần cứng và phần mềm.

-

Khả năng mở rộng vững mạnh: Điện toán đám mây cho phép khả năng điều
chỉnh quy mô ngay lập tức hoặc tăng lên hoặc giảm xuống, bất cứ lúc nào mà
không cần giao kết dài hạn.

Chỉ đơn cử một tiện ích đối với người dùng cuối là có thể thực hiện cơng việc với
dữ liệu của mình mọi lúc, mọi nơi, mọi thiết bị, mọi nền tảng (mà chỉ cần có kết nối
mạng) là ta có thể hình dung ra những lợi ích to lớn khác đối với mức độ tổ chức
hoặc lớn hơn.
Xử lý nghiệp vụ theo hướng cộng tác: Với kết nối mạng và những thiết lập chia sẻ
thích hợp, những người dùng ở bất kì đâu, bất kì lúc nào có thể cùng cộng tác để tạo
ra những sản phẩm mà trước đây thường phải gặp trực tiếp hoặc tiến hành tuần tự,
mất rất nhiều thời gian. Đó chính là xử lý nghiệp vụ theo hướng cộng tác.

2

Nguy cơ bị tấn công của mạng

Song song với những lợi ích mà mạng máy tính mang lại thì mạng máy tính cũng là
mơi trường lí tưởng để kẻ xấu lợi dụng thực hiện những hành vi tấn công đến thơng

tin trong máy tính hay mạng máy tính của người dùng.
Tấn công (attack), hay đột nhập (intrusion) lên một hệ thống là sự vi phạm chính
sách an tồn bảo mật của hệ thống đó. Mặc dù các vụ tấn công, đột nhập ngày càng
trở nên phức tạp, tinh vi nhưng chúng ta cũng có thể chia chúng thành một số
dạng tấn công và đột nhập thường gặp như:

9


-

Các cuộc tấn công do 1 người dùng xâm nhập vào 1 hệ thống với các quyền hạn
lớn hơn là được phép bởi chính sách bảo mật hệ thống.

-

Các cuộc tấn công từ chối người khác truy cập vào 1 số dịch vụ mà hệ thống
cung cấp.

-

Hoặc là nỗ lực thăm dị 1 hệ thống để tìm kiếm lỗ hổng.

Sau đây là một vài ví dụ về rất nhiều cách mà kẻ tấn cơng có thể truy cập bất hợp
pháp hoặc ngăn cản người khác truy cập vào một mạng
Kĩ nghệ xã hội: kẻ tấn cơng có thể truy cập vào hệ thống bằng cách lừa một người
sử dụng cung cấp thơng tin có thể sử dụng được để đột nhập vào hệ thống. Ví dụ: kẻ
tấn cơng có thể gọi cho một cá nhân với tư cách của một người quản trị mạng lưới
trên điện thoại mạo danh với nỗ lực thuyết phục cá nhân tiết lộ thông tin bí mật
(như mật khẩu, tên tập tin, các chính sách bảo mật ). Hoặc kẻ tấn cơng có thể cung

cấp một phần mềm cho người sử dụng hệ thống dưới dạng phần mềm hay bản tin
hấp dẫn trên mạng nhưng có chứa mã độc hại để cung cấp những thơng tin cần thiết
hay mở cửa hậu (backdoor) cho kẻ tấn công truy cập hệ thống.
Thực hiện lỗi: Những lỗi trong những chương trình đáng tin cậy có thể bị khai thác
bởi kẻ tấn công để lấy được cách truy cập trái phép đến 1 hệ thống máy tính. Ví dụ
như lỗi tràn bộ đệm hay xử lý sai các tập tin tạm thời.
Lạm dụng tính năng: Có những hành động hợp pháp người ta có thể thực hiện
bình thường nhưng khi đưa đến cực độ có thể dẫn đến lỗi của hệ thống. Ví dụ khi
mở hàng trăm kết nối Telnet để máy tính có thể điền vào bẳng tiến trình của nó
hoặc làm cho máy tính rơi vào trạng thái chờ đợi vô hạn hoặc làm ngập lụt hệ thống
bằng các email rác.
Cấu hình sai: kẻ tấn cơng có thể truy cập bởi một lỗi trong cấu hình của hệ thống.
Ví dụ: cấu hình mặc định của một số hệ thống bao gồm tài khoản “khách” (guest)
hay “quản trị viên” (Administrator) mà không được bảo vệ bởi mật khẩu đủ mạnh.
Giả mạo: Trong một số trường hợp, kẻ tấn cơng có thể đánh lừa 1 hệ thống cho
phép truy cập bằng cách giả mạo một hệ thống khác. Một ví dụ là về việc gửi 1 gói
10


tin TCP có 1 địa chỉ nguồn được cài đặt làm như gói tin đó xuất hiện đến từ nguồn
đáng tin cậy.
Những dạng tấn công gây ra sự bất thường cho mạng (như làm tê liệt, khai thác lỗ
hổng, sử dụng vượt quyền hạn, ….) về cơ bản đều dựa trên những cơ chế bình
thường của mạng nhưng lại phục vụ cho mục đích bất thường.
Ví dụ như kiểu tấn công Ping Of Death (PoD): lệnh Ping được thiết kế để kiểm tra
tính liên thơng giữa 2 nút mạng bằng cách gửi một gói tin tới địa chỉ của một nút
mạng và chờ tín hiệu phản hồi. Tuy nhiên, bằng cách sử dụng thêm tham số [-l size]
và [-n count], kẻ tấn cơng có thể lạm dụng để làm ngập lụt địa chỉ đích bằng cách
thực hiện ping bằng gói tin với dung lượng (size) lớn và gửi với số lượng (count)
lớn. Như vậy, tại địa chỉ đích, nếu chỉ nhận một gói tin ping từ một địa chỉ nguồn

thì có thể coi là bình thường nhưng nếu nhận được một số lượng lớn, các gói tin
ping có dung lượng lớn, từ cùng một hoặc một số địa chỉ nguồn thì có thể coi đó là
điều bất thường. Ta có thể kiểm tra điều này bằng cách sử dụng chương trình có
tính năng đọc thơng tin từ header của các gói tin và đưa ra các phản ứng thích hợp.
Các dấu hiệu cụ thể của PoD, Denies Of Services (DoS) cũng như các kiểu tấn công
phổ biến khác đã được tác giả Kristopher Kendall trình bày trong nghiên cứu có tên
“A Database of Computer Attacks for the Evaluation of Intrusion Detection
Systems” [5]. Bằng cách đánh giá các thông tin trong header của các gói tin truyền
trong mạng, ta có thể phát hiện được rất nhiều kiểu tấn công mạng mà K. Kendall
đã nêu trong nghiên cứu của mình. Vấn đề là cần phải thực hiện bằng một phương
pháp đủ hiệu quả để có thể triển khai trong thời gian thực.
Mỗi hệ thống mạng như vậy phải đương đầu với rất nhiều nguy cơ. Chỉ một sự xâm
nhập của kẻ tấn cơng từ một vị trí trong mạng cũng có thể gây thiệt hại nghiêm
trọng cho cả phạm vi rộng lớn. An ninh mạng trở thành một vấn đề quan trọng và
đặc biệt trong đó, người ta cần phát triển các cơ chế bảo vệ chống lại sự xâm nhập.

11


3

Các phương pháp phát hiện xâm nhập mạng hiện có

Một hệ thống phát hiện xâm nhập sẽ thu thập thông tin từ một máy tính hoặc mạng
máy tính và cố gắng phát hiện kẻ xâm nhập hay lạm dụng hệ thống. Thông thường,
một hệ thống phát hiện xâm nhập sẽ cảnh báo con người về truy cập khả nghi và
không thực hiện gì thêm nhưng một số hệ thống mới như Real Secure 2.5 hay Mc
Afee Virus Scan Enterprise Edition có thể chủ động ngăn chặn kẻ xâm nhập ngay
khi phát hiện ra
Các phương pháp xâm nhập hiện có được xếp vào hai loại chính: nhận diện dấu

hiệu và phát hiện bất thường.

3.1

Nhận diện dấu hiệu

Trong kĩ thuật phát hiện bất thường dựa trên nhận diện dấu hiệu, những đặc điểm
bình thường của hệ thống được định nghĩa trước. Thêm vào đó, những đặc điểm của
những kiểu tấn cơng phổ biến cũng được ghi nhận để phục vụ mục đích so sánh,
phát hiện bất thường sau này. Sự bất thường có thể do một hoạt động đã được định
nghĩa là bình thường nhưng lại diễn ra ở thời điểm khơng bình thường ví dụ như sự
truy cập của một người dùng vào hệ thống mạng của một tổ chức vào 3 giờ sáng –
giờ mà ở tổ chức đó khơng có ai làm việc thì có thể coi là một dấu hiệu bất thường.
Hoặc cũng có thể là sự gia tăng của dữ liệu bình thường trên hệ thống ví dụ như sự
gia tăng kích thước của tệp tin ghi nhật kí (log) của hệ thống khác với dung lượng
đã ghi nhận trong cùng thời điểm ở những khoảng thời gian khác có thể là căn cứ để
nghi ngờ hệ thống đang bị làm cho quá tải hay những gói tin được gửi liên tiếp từ
cùng một địa chỉ nguồn tới nhiều cổng khác nhau của một hệ thống có thể là căn cứ
để nghi ngờ hệ thống đang bị tấn cơng theo kiểu dị cổng (Scan port).
Kĩ thuật phát hiện bất thường dựa trên dấu hiệu khá hiệu quả với những kiểu tấn
cơng đã biết hay với những chính sách kiểm soát truy cập đã biết nhưng một hạn
chế rõ ràng của kỹ thuật này là không thể phát hiện các cuộc tấn công mới với
những dấu hiệu chưa được biết.

12


Phát hiện bất thường

3.2


3.2.1 Bằng số liệu thống kê
Tư tưởng của phương pháp này là thực hiện thu thập, lưu trữ và thống kê cả dữ liệu
bình thường và bất thường. Sau đó, ta định kì tính tốn ngưỡng bất thường, nếu
vượt ngưỡng thì đưa ra cảnh báo.
Ưu điểm của phương pháp này là không cần dấu hiệu biết trước của một dạng tấn
cơng mới mà có thể chỉ cần dựa trên số lượng dữ liệu bất thường thu thập được vượt
quá một ngưỡng nào đó để đưa ra cảnh báo. Tuy vậy, ngưỡng bình thường/bất
thường là khó xác định.
3.2.2 Theo cách tiếp cận học máy
Phương pháp này ban đầu dựa vào những dữ liệu huấn luyện đã được gán nhãn là
bình thường/bất thường để tạo ra mơ hình phân lớp dữ liệu bằng các phương pháp
học máy. Sau đó, với những dữ liệu mới, ta sẽ kiểm tra xem chúng phù hợp với lớp
bình thường hay bất thường để đưa ra cảnh báo.
Phương pháp này có những ưu điểm như:
•

Có khả năng thay đổi chiến lược để đáp ứng được nhiều trường hợp khác
nhau (cả đã biết và chưa biết)

•

Hiệu quả cao hơn do ln có thể sử dụng các dữ liệu mới để bổ sung vào tập
dữ liệu huấn luyện nhằm cải thiện mơ hình phân lớp ban đầu.

Bên cạnh đó, phương pháp này cũng cịn một số nhược điểm như
•

Chất lượng của mơ hình phân lớp phụ thuộc tập dữ liệu huấn luyện, dữ liệu
kiểm tra và các đặc trưng được lựa chọn


•

Tỉ lệ báo động giả (sai số) cao với phương pháp học máy phi giám sát.

13


Luận văn này lựa chọn nội dung Phát hiện bất thường trong mạng theo cách tiếp
cận học máy làm đề tài nghiên cứu. Chương tiếp theo, chúng ta sẽ tìm hiểu về thuật
toán Support Vector Machine (SVM) – một thuật tốn học máy có nhiều ứng dụng
rộng rãi hiện nay.

14


CHƯƠNG 2: THUẬT TOÁN HỌC MÁY
SUPPORT VECTOR MACHINE (SVM)
2.1. Giới thiệu

Vấn đề phân lớp (Classification) và dự đoán (Prediction) là hai bài tốn
cơ bản và có rất nhiều ứng dụng trong tất cả các lĩnh vực. Có nhiều phương
pháp đã được nghiên cứu và ứng dụng cho các bài toán dạng này như: mạng
rron nhân tạo, phương pháp học thống kê,… Trong chương này, chúng ta sẽ
đi sâu nghiên cứu thuật toán Support Vector Machines (SVM), một thuật toán
học máy rất hiệu quả hiện nay.
Thuật toán SVM được coi là cơng cụ mạnh cho những bài tốn phân
lớp phi tuyến được các tác giả Vapnik và Chervonenkis phát triển mạnh mẽ
năm 1995. Phương pháp này thực hiện phân lớp dựa trên nguyên lý Cực tiểu
hóa Rủi ro có Cấu trúc SRM (Structural Risk Minimization), được xem là một

trong các phương pháp phân lớp tinh vi nhất cho tới nay.
2.2. Ý tưởng của SVM

Cho trước một tập huấn luyện, được biểu diễn trong khơng gian vector,
trong đó mỗi tài liệu là một điểm, thuật tốn này tìm ra một siêu phẳng f
quyết định tốt nhất có thể chia các điểm trên không gian này thành hai lớp
riêng biệt tương ứng là lớp + và lớp –. Chất lượng của siêu phẳng này được
quyết định bởi khoảng cách (gọi là biên) của điểm dữ liệu gần nhất của mỗi
lớp đến mặt phẳng này. Khi đó, khoảng cách biên càng lớn thì mặt phẳng
quyết định càng tốt, đồng thời việc phân loại càng chính xác.
Mục đích của thuật tốn SVM là tìm được khoảng cách biên lớn nhất,
điều này được minh họa trong hình 2.1 dưới đây.

15


Hình 2.1 Siêu phẳng f phân chia dữ liệu học thành 2 lớp + và – với khoảng cách
biên lớn nhất. Các điểm gần f nhất (điểm được khoanh tròn) là các Support Vector.
2.3. Nội dung của SVM
2.3.1. Cơ sở lý thuyết

SVM thực chất là một bài toán tối ưu, mục tiêu của thuật tốn này là
tìm được 1 khơng gian F và siêu phẳng quyết định f trên F sao cho sai số phân
loại là thấp nhất.
Cho tập mẫu ( x1 , y1 ), ( x2 , y2 ), ..., ( xt , yt ) với xi R n thuộc vào hai
lớp nhãn: yi  {1, 1} là nhãn lớp tương ứng của các

( 1 biểu thị lớp I, 1

biểu thị lớp II).

Ta có, phương trình siêu phẳng chứa véc tơ xl trong không gian:
xl . w  b  0


1, xl . w  b  0
Đặt f ( xl )  sign( xl . w  b)  

1, xl . w  b  0

16


Như vậy, f ( xl ) biểu diễn sự phân lớp của xl vào hai lớp như đã nêu.
Ta nói yi   1 nếu xl  lớp I và yi   1 nếu xl  lớp II. Khi đó để có siêu
phẳng f ta sẽ phải giải bài tốn sau:
Tìm min w với w thỏa mãn điều kiện sau:





yi sign( xl .w  b)  1,  i  1, n
Bài tốn SVM có thể giải bằng kỹ thuật sử dụng nhân tử Lagrange để
biến đổi về thành dạng đẳng thức. Một đặc điểm thú vị của SVM là mặt
phẳng quyết định chỉ phụ thuộc vào các Support Vector và nó có khoảng cách
đến mặt phẳng quyết định là

1

. Cho dù các điểm khác bị xóa đi thì thuật


w

toán vẫn cho kết quả giống như ban đầu. Đây chính là điểm nổi bật của thuật
tốn SVM so với các phương pháp khác vì tất cả các dữ liệu trong tập huấn
luyện đều được dùng để tối ưu hóa kết quả.
Tóm lại, trong trường hợp nhị phân phân tách tuyến tính, việc phân lớp
được thực hiện qua hàm quyết định f ( x)  sign  w.x  b  , hàm này thu
được bằng việc thay đổi véc tơ chuẩn w, đây là véc tơ để cực đại hóa miền
đặc trưng y 

1
w

2

Việc mở rộng SVM để phân đa lớp hiện nay vẫn đang được đầu tư
nghiên cứu. Có một phương pháp tiếp cận để giải quyết vấn đề này là xây
dựng và kết hợp nhiều bộ phân lớp nhị phân SVM (Chẳng hạn: trong quá
trình huấn luyện với SVM, bài tốn phân m lớp có thể được biến đổi thành bài
tốn 2 * m lớp, khi đó trong mỗi hai lớp, hàm quyết định sẽ được xác định
cho khả năng tổng quát hóa tối đa).
17


2.3.2. Bài toán phân 2 lớp với SVM
Bài toán đặt ra là: Xác định hàm phân lớp để phân lớp các mẫu trong
tương lai, nghĩa là với một mẫu dữ liệu mới xt thì cần phải xác định xt được
phân vào lớp +1 hay lớp 1 ?
Nếu dữ liệu phân chia tuyến tính, hàm quyết định được xác định:

f ( x)  wt x  b

(2.1)

với w là véc tơ n chiều và b là véc tơ vô hướng.
Siêu phẳng phân tách thỏa mãn:
yi (w t xi  b)  1 với i  1, 2, ..., l

(2.2)

Siêu phẳng phân chia tối ưu là siêu phẳng chia hai lớp với với khoảng
cách giữa hai lớp là lớn nhất.

Hình 2.2. Minh họa cho bài toán phân hai lớp

Siêu phẳng tối ưu có thể xác định được bằng việc giải bài tốn tối ưu
bậc hai sau:
Cực tiểu

1 2
w
2

(2.3)

18


với mọi ràng buộc yi (wxi  b)  1
Nếu số thuộc tính của các mẫu dữ liệu là lớn, chúng ta có thể đơn giản

hóa phép tính bằng cách chuyển bài toán với điều kiện Kuhn-Tucker tương
đương với phương pháp Lagrange cho (2.3) được mô tả như sau:
L( w, b,  ) 

1
( w, w)   i [ yi ( wi .xi  b)  1]
2

(2.4)

với   (1 , ...,  M ) là nhân tử Lagrange.
Phương trình kép trên trở thành: cực đại L(w, b, α)

(2.5)

với ràng buộc i  0, i  1, ..., M
Vi phân từng phần của (2.4) lần lượt với w và b ta được:
M
L
( w, b,  )  w   yi i xi  0
w
i 1

M
L
( w, b,  )  w   yi i  0
b
i 1

(2.6)


Từ (2.4), (2.5), và (2.6) ta có bài tốn tối ưu sau:
M

1 M
Cực đại W(α)   i   i  k yi yk xi xk
2 i ,k  0
i 1

Với ràng buộc

M

 yii  0,
i 1

(2.7)

i  0, i  1,...,M

Số lượng biến trong bài toán tối ưu trên chính là số mẫu trong tập dữ
liệu huấn luyện.

19


Giả sử ta tìm được cặp nghiệm tối ưu là

,


. Theo lý thuyết Karush-

Tucker, điều kiện xảy ra đẳng thức (2.2) tương ứng với mỗi cặp huấn luyện
vào – ra ( ,

) khi và chỉ khi  i* khác 0. Trong trường hợp này, mẫu huấn

luyện chính là một support vector. Giải (2.7) với   (1, ...,  M ) ta có thể
xác định được các support vector của lớp I và lớp II. Do siêu phẳng tối ưu
nằm trong số các support vector vừa tìm được với lớp I và lớp II, nên
được tính bởi:
1 M
b   yk k* ( s1 xk  s2 xk )
2 k 0
*

Với s1 và s2 lần lượt là các support vector của lớp I và lớp II.
Trong trường hợp các mẫu huấn luyện khơng thể phân chia tuyến tính,
chúng ta đưa thêm một biến phụ không âm  i vào (2.2), cộng thêm vào hàm
(2.5) và tổng của các biến phụ được nhân với tham số C. Điều này tương ứng
với việc cộng biên trên của C và  . Trong cả hai trường hợp trên, hàm ra
quyết định là như nhau và được tính bằng:
f ( x) 

M

  k* yi xi x  b*

i 1


Với mỗi một mẫu dữ liệu ban đầu, nó sẽ được phân lớp như sau:
x
Thuật tốn SVM cho bài tốn phân lớp được mơ tả thơng qua ví dụ sau:
Xét trong khơng gian 2 chiều (n = 2), các điểm của tập mẫu được cho như
hình 2.3:

20


Hình 2.3. Minh họa bài tốn phân hai lớp với Thuật toán SVM

Để xác định hàm phân lớp dựa trên thuật tốn SVM, ta sẽ tiến hành
tìm hai siêu phẳng song song (tương ứng với 2 đường nét đứt trong hình 2.3
ở trên) sao cho khoảng cách y giữa chúng là lớn nhất có thể để phân tách
hai lớp này ra làm hai phía. Hàm phân tách tương ứng với phương trình siêu
phẳng nằm giữa hai siêu phẳng tìm được (đường nét đậm trên hình 2.3).
Hình 2.3 thể hiện trường hợp có thể tìm được siêu phẳng phân tách, dữ
liệu trong trường hợp này gọi là phân tách tuyến tính. Bây giờ ta xét trường
hợp dữ liệu không phân tách tuyến tính như trong hình 2.4 như sau:

Hình 2.4. Bài tốn SVM trong trường hợp dữ liệu mẫu khơng phân tách tuyến tính

21


Ta thấy rằng trong hình 2.4 ở trên có những mẫu mặc dù có nhãn +1,
nhưng lại bị “rơi” vào phía các mẫu có nhãn 1 và ngược lại.
Trong trường hợp này, thuật toán SVM sẽ sử dụng một phép ánh xạ dữ
liệu mẫu vào khơng gian mới có số chiều lớn hơn sao cho tập mẫu này sẽ là
phân tách tuyến tính trong khơng gian đó (ta gọi khơng gian mới này là

không gian đặc trưng). Trong không gian đặc trưng này, ta vẫn tiến hành tìm
khoảng cách cực đại giữa hai siêu phẳng song song để phân tách dữ liệu mẫu.
Các điểm mà nằm trên hai siêu phẳng phân tách được gọi là các
Support Vector. Các điểm này sẽ quyết định đến hàm phân tách dữ liệu.
Trong thực tế, để thuận tiện cho q trình tính tốn, dữ liệu mẫu sẽ
được ánh xạ vào không gian đặc trưng bằng cách sử dụng các hàm nhân, cách
làm này sẽ làm tăng tốc độ tính tốn và đảm bảo rằng dữ liệu sẽ phân tách
tuyến tính.
Tùy vào từng trường hợp cụ thể của dữ liệu mẫu ta có các biến thể của
SVM như C-SVC và bài toán SVM nhiều lớp.
2.3.3. Phân nhiều lớp với SVM
Để phân nhiều lớp thì kỹ thuật SVM nguyên thủy sẽ chia không gian
dữ liệu thành 2 phần và quá trình này lại lặp lại nhiều lần. Khi đó hàm quyết
định phân dữ liệu vào lớp thứ I của tập n 2-lớp sẽ là:

fi (x)  wit x  bi
Những phân tử x là support vector sẽ thỏa mãn điều kiện:
(x)

22


Như vậy, bài toán phân nhiều lớp sử dụng phương pháp SVM hồn
tồn có thể thực hiện giống như bài toán hai lớp. Một trong số các phương
pháp là sử dụng chiến lược “một-đối-một” (one-against-one):
Giả sử bài toán cần phân loại có k lớp (k ≥ 2 ), chiến lược “một-đốimột” sẽ tiến hành

k (k  1)
lần phân lớp nhị phân sử dụng thuật toán SVM.
2


Mỗi lớp sẽ tiến hành phân tách với k  1 lớp còn lại để xác định k  1 hàm
phân tách dựa vào bài toán phân hai lớp bằng thuật toán SVM.
2.3.4. Các bước chính của thuật tốn SVM
Thuật tốn SVM u cầu dữ liệu được diễn tả như các véc tơ của các số
thực. Như vậy nếu đầu vào chưa phải là số thì ta cần phải tìm cách chuyển
chúng về dạng số của SVM.
 Tiền xử lý dữ liệu: Thực hiện biến đổi dữ liệu phù hợp cho q trình
tính tốn, tránh các số q lớn mơ tả các thuộc tính. Thường nên co
giãn (scaling) dữ liệu để chuyển về đoạn [-1, 1] hoặc [0, 1]
 Chọn hàm hạt nhân: Lựa chọn hàm hạt nhân phù hợp tương ứng cho
từng bài toán cụ thể để đạt được độ chính xác cao trong quá trình phân
lớp.
 Thực hiện việc kiểm tra chéo để xác định các tham số cho ứng dụng.
Điều này cũng quyết định đến tính chính xác của q trình phân lớp.
 Sử dụng các tham số cho việc huấn luyện với tập mẫu. Trong quá trình
huấn luyện sẽ sử dụng thuật tốn tối ưu hóa khoảng cách giữa các siêu
phẳng trong quá trình phân lớp, xác định hàm phân lớp trong không
gian đặc trưng nhờ việc ánh xạ dữ liệu trong không gian đặc trưng bằng
cách sử dụng hàm nhân, giải quyết cho cả trường hợp dữ liệu là phân
tách và khơng phân tách tuyến tính trong khơng gian đặc trưng.

23