HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG TRẦN VŨ LINH

NGHIÊN CỨU KẾT HỢP CÁC BỘ PHÂN LOẠI
CHO CÁC BÀI TOÁN NHẬN DẠNG VÀ
DỰ ĐOÁN CHUYÊN NGÀNH : TRUYỀN DỮ LIỆU VÀ MẠNG MÁY TÍNH
MÃ SỐ : 60.48.15

Người hướng dẫn khoa học: PGS.TS TỪ MINH PHƯƠNG TÓM TẮT LUẬN VĂN THẠC SĨ

HÀ NỘI - 2011

2

thuộc tính của các đối tượng chứa trong lớp đó.
Các thuật toán phân loại tiêu biểu bao gồm như mạng neural,
cây quyết định, suy luận quy nạp, mạng Beyesian, Support Vector
Machine…. Tất cả các cách tiếp cập này xây dựng những mô hình
đều có khả năng phân loại cho một mẫu mới chưa biết dựa vào
những mẫu tương tự đã được học. Bài toán phân loại có thể xử lý
thông tin được thu thập từ mọi lĩnh vực hoạt động của con người và
thế giới tự nhiên được biểu diễn dưới dạng các bảng. Bảng này bao
gồm các đối tượng và các thuộc tính. Các phần tử trong bảng là các
giá trị xác định các thuộc tính (attributes hay features) của các đối
tượng. Trong đó số cột chính là số thuộc tính của các đối tượng, mỗi
cột là một thuộc tính và số dòng chính là số đối tượng chứa trong dữ
liệu này. Mọi dữ liệu được biểu diễn dưới các dạng khác có thể được
chuyển thành dạng bảng như trên để thực hiện quá trình phân loại.
1.2. BÀI TOÁN PHÂN LOẠI
Một bài toán phân loại bao gồm 2 bước sau:
Bước 1: Huấn luyện
Mục đích của bước này là xây dựng một mô hình xác định
một tập các lớp dữ liệu. Mô hình này được xây dựng bằng cách phân
tích các bộ dữ liệu của một cơ sở dữ liệu, mỗi bộ dữ liệu được xác
định bởi giá trị của các thuộc tính. Giả sử mỗi bộ dữ liệu đã thuộc về
một trong các lớp đã đựơc định nghĩa trước, điều này được xác định
bởi một trong các thuộc tính, gọi là thuộc tính phân loại. Trong ngữ
cảnh của bài toán phân loại, mỗi bộ dữ liệu được xem như là một
mẫu, một ví dụ, hay một đối tượng. Những bộ dữ liệu được phân tích
để xây dựng mô hình phân loại được lấy từ trong tập dữ liệu học hay

4
dữ liệu huấn luyện (training data set). Những bộ dữ liệu riêng lẻ tạo
thành tập dữ liệu huấn luyện còn gọi là những mẫu huấn luyện

1.3.2.Mạng Bayes
Bayesian là phương pháp phân lớp dựa vào thống kê. Ta có
thể dự đoán xác suất của các lớp trong tập dữ liệu, dựa vào xác suất
này có thể xếp các mẫu vào các lớp riêng biệt. Thuật toán phân lớp
Bayesian giả thiết rằng giá trị các thuộc tính của một lớp độc lập với
giá trị của các thuộc tính khác, giả thiết này còn được gọi là lớp độc
lập có điều kiện, nó làm đơn giản các tính toán sau này. Mạng
Bayesian là một đồ thị, trên đồ thị cho phép biểu diễn mối quan hệ
giữa các thuộc tính.

1.3.3. Support Vector Machine
SVM là một phương pháp mới để phân lớp dữ liệu. Nó dễ sử
dụng hơn mạng neural, tuy nhiên nếu không sử dụng nó chính xác thì
dễ bị bỏ qua một số bước đơn giản nhưng cần thiết, dẫn đến kết quả
không được thỏa mãn. Mục đích của phương pháp SVM là phát sinh
ra một mô hình từ tập mẫu học, mô hình này có khả năng dự đoán
lớp cho các mẫu thử. SVM tìm ra một hàm quyết định phi tưyến
trong tập mẫu học bằng cách ánh xạ hoàn toàn các mẫu học vào một
không gian đặc trưng kích thước lớn có thể phân lớp tuyến tính và
phân lớp dữ liệu trong không gian này bằng cách cực đại khoảng
cách lề (geometric margin) và cực tiểu lỗi học cùng một lúc. Vấn đề
tối ưu chủ yếu là

6
1.4. MỘT SỐ VẤN ĐỀ VỚI BÀI TOÁN PHÂN LOẠI
Có 2 vấn đề xảy ra với kết quả dự đoán của các bộ phân loại
đó là kết quả dự đoán bị lệch (bias), tức là kết quả có thiên hướng sai
giống nhau và kết quả dự đoán quá khác biệt nhau (variance). Tưởng
tượng rằng chúng ta có các tập dữ liệu huấn luyện khác nhau, và tốt
như nhau. Một thuật toán được coi là dự đoán lệch (bias) với một dữ

là lựa chọn một thuật toán học máy có bias thấp, sau đó sử dụng
phương pháp biểu quyết để làm giảm variance của nó. Chương sau sẽ
mô tả chi tiết hơn về cách thức để tạo ra và biểu quyết kết quả của
các bộ phân loại đơn lẻ đó.
1.5. KẾT LUẬN CHƯƠNG
Chương 1 đã giới thiệu chung về bài toán phân loại tự động,
và trình bày nội dung của một số thuật toán phân loại phổ biến: thuật
toán cây quyết đinh, mạng Bayes, Support Vector Machine. Các bộ
phân loại được xây dựng bởi các thuật toán này lại thường cho kết
quả chính xác không cao với những bộ dữ liệu lớn, hoặc quá phức
tạp. Dẫn đến việc cần thiết tìm ra phương pháp mới để giải quyết các
bài toán phân loại tự động.

8
CHƯƠNG 2 – TRÌNH BÀY PHƯƠNG PHÁP
KẾT HỢP CÁC BỘ PHÂN LOẠI

2.1. KẾT HỢP CÁC BỘ PHÂN LOẠI
2.1.1. Khái niệm kết hợp các bộ phân loại
Bộ kết hợp các bộ phân loại (Ensemble) là tập hợp của các
bộ phân loại cơ bản, trong đó mỗi bộ phân loại cơ bản có thể là một
một bộ phân loại cổ điển như: cây quyết định, naives bayes, mạng
nơ-ron, Khi một ví dụ mới được phân loại, nó được xử lý bởi các
bộ phân loại cơ bản của bộ kết hợp mà kết quả của chúng được kết
hợp theo một cách nào đó để đưa ra dự đoán cuối cùng của bộ kết
hợp đối với ví dụ đó. Chúng ta muốn có các bộ phân loại cơ bản
phân loại tốt và kết quả của các bộ phân loại cơ bản không có độ
tương quan cao với nhau.
2.1.2. Các cách tiếp cận phương pháp kết hợp các bộ phân loại
Có hai cách tiếp cận bộ kết hợp:

m
. Khi có một ví dụ phân loại mới, kết quả
của bộ kết hợp sẽ là kết quả nhận được nhiều nhất khi chạy M bộ
phân loại cơ bản.

Hình 2.3: Mô hình hoạt động của Bagging
10

Trong hình 2.3, bộ 3 mũi tên bên trái mô tả việc lấy mẫu 3 lần
có lặp. Bộ 3 mũi tên tiếp theo mô tả việc gọi thuật toán học mô hình
trên 3 ví dụ để tạo ra 3 mô hình cơ bản.
Bagging trả lại hàm h(x) được biểu quyết lớn nhất trong các
h
1
,h
2
,….,h
M
. phân lớp các ví dụ mới bằng việc trả lại lớp y trong tập
các lớp có thể Y. Trong hình 2.3, có 3 bộ phân loại cơ bản để biểu
quyết ra đáp án cuối cùng. Trong bagging, các tập huấn luyện M
được tạo ra khác nhau. Nếu sự khác nhau này đủ để dẫn đến sự khác
nhau của M mô hình cơ bản trong khi hiệu năng của các mô hình đủ
tốt thì thì bộ kết hợp có hiệu năng tốt hơn các mô hình cơ bản.

2.3. PHƯƠNG PHÁP BOOSTING
2.3.1. Mô hình hoạt động của Boosting
12

2.4. KẾT LUẬN CHƯƠNG
Chương 2 đã trình bày các khái niệm cơ bản về phương pháp
kết hợp các bộ phân loại. Và bằng cơ sở lý thuyết, cũng chứng minh
được phương pháp kết hợp các bộ phân loại có khả năng đạt độ chính
xác cao hơn việc sử dụng các bộ phân loại đơn lẻ trong các bài toán
nhận dạng và dự đoán. Bagging và Boosting là hai phương pháp tiêu
biểu của họ các phương pháp kết hợp các bộ phân loại. CHƯƠNG 3 – PHÁT HIỆN URL ĐỘC HẠI
BẰNG CÁCH PHÂN LOẠI
3.1. BÀI TOÁN PHÁT HIỆN URL ĐỘC HẠI
Trước tiên, ta tìm hiểu một số khái niệm về URL và các vấn đề
liên quan đến phân loại URL độc hại. WWW là một mạng thông tin
toàn cầu mà người dùng có thể truy cập qua Internet, và mạng bao
gồm một tập các Web sites. Mỗi web site lại là một tập hợp các trang
văn bản, hình ảnh liên quan đến nhau đặt trên máy chủ của web site
đó. Thông thường, người dùng truy cập các web site thông qua trình
duyệt - phần mềm khách lấy về và biểu diễn các dữ liệu văn bản,
hình ảnh và các nội dung khác liên quan tới site (các trình duyệt
thông dụng là Internet Explorer, Firefox, Chrome, Safari). Tuy nhiên,
các trình duyệt phải xác định vị trí các site mong muốn trước khi lấy
nó về, Uniform Resource Locators(URLs) là cách đặt tên vị trí chuẩn
trên Web. Trong phạm vi đề tài, thuật ngữ URL được hiểu tương
đương với trang web mà nó trỏ tới.


là có độc hại hay không là một cách tiếp cận tiềm năng có thể giải
quyết được vấn đề trên.

3.3. ÁP DỤNG PHƯƠNG PHÁP KẾT HỢP CÁC BỘ PHÂN
LOẠI ĐỂ NHẬN BIẾT URL ĐỘC HẠI
Bài toán phân biệt URL độc hại sử dụng phương pháp kết hợp
các bộ phân loại gồm 3 bước:
- Bước 1: Biểu diễn các URL bằng các đặc trưng.
- Bước 2: Sử dụng một bộ các dữ liệu đã được phân loại độc
hại, hay không độc hại để làm dữ liệu huấn luyện.
- Bước 3: Áp dụng phương pháp Kết hợp các bộ phân loại để
xây dựng bộ phân loại và đánh giá kết quả.
3.3.1. Biểu diễn các URL bằng các đặc trưng
Các đặc trưng của URL được chia làm hai loại là đặc trưng
ngữ nghĩa và đặc trưng về host. Bảng 3.1 biểu diễn các đặc trưng
kiểu ngữ nghĩa và đặc trưng về host cùng với số lượng các đặc trưng
sưu tập được của mỗi loại. Trong đó các đặc trưng kiểu ngữ nghĩa
chỉ chiếm 38%, còn lại 62% là các đặc trưng về host. Bây giờ chúng
ta sẽ mô tả chi tiết hơn về các kiểu đặc trưng và mục đích của việc
đưa các kiểu đặc trưng này vào bộ phân loại.
3.3.1.1. Đặc trưng kiểu ngữ nghĩa
Các đặc trưng này cho phép chúng ta bắt các thuộc tính để
phân biệt giữa URL độc hại và URL không độc hại. Để dễ hình
dung, chúng ta cùng xem xét một ví dụ sau: vị trí của cụm từ ‘.com’
trong URL www.ebay.com là hoàn toàn bình thường. Tuy nhiên khi
nhìn vào vị trí của chính cụm từ ‘.com’ đó trong hai URL
‘www.ebay.com.phishy.biz’ và

15
‘phish.biz/www.ebay.com/index.php’ ta có thể nhận thấy có một nỗ

các trang được đặt tại các các nhà cung cấp chính thức. Vì vậy dựa
vào tốc độ kết nối của máy tính tới một trang thông qua URL chúng
ta có thể dự đoán được trang mà URL đó trỏ tới có phải độc hại
không.
- Danh sách đen: đây là một phương pháp truyền thống, lưu
các URL được nhận biết là độc hại, mỗi URL độc hại trong danh sác
đen có thể được dùng làm một đặc trưng để phân loại.
3.3.2. Dữ liệu huấn luyện thực nghiệm
Bộ dữ liệu URL sử dụng trong Luận văn là bộ dữ liệu URL
được trình bày trong Hội thảo quốc tế về học máy 2009 của nhóm tác
giả Justin Ma, Lawrence Saul, Stefan Savage, Geoff Voelker. Bộ dữ
liệu bao gồm 2 triệu URL được thu thập trong 100 ngày. Trong đó
các URL độc hại được cung cấp bởi một Nhà cung cấp dịch vụ thư
điện tử lớn, họ cung cấp 6000 – 7500 ví dụ về URL rác và URL giả
mạo. Các URL độc hại này được phân tích từ những thư điện tử mà
người dùng đánh dấu là spam, sau đó Nhà cung cấp sử dụng một bộ
lọc để xác định lại URL đó thực sự là độc hại. Các URL không độc
hại được cung cấp bởi kho lưu trữ của Yahoo.
3.3.3. Tiến hành thực nghiệm
Đề tài sử dụng bộ dữ liệu huấn luyện trên để huấn luyện và
kiểm thử phương pháp Boosting và Random Forest. Sau đó so sánh
kết quả phân loại của phương pháp Boosting và Random Forest (là
phương pháp dựa trên ý tưởng của Bagging kết hợp với việc chọn
ngẫu nhiên các đặc trưng để tạo ra một tập các cây quyết định có độ
đa dạng được kiểm soát) với các 2 thuật toán học máy J48 và Naïve
Bayes. Công cụ được sử dụng để huấn luyện và kiểm thử là Weka,
một công cụ phổ biến để đánh giá các bộ phân loại.

17
Các bước tiến hành thực nghiệm như sau:

58.3 91.67 100 83.33
Bộ dữ liệu 10
58.3 91.67 100 83.33
Bộ dữ liệu 11
50 83.33 50 50
Bộ dữ liệu 12
100 66.67 100 83.33
Bộ dữ liệu 13
66.67 66.67 100 83.33
Bộ dữ liệu 14
100 66.67 100 50
Bộ dữ liệu 15
100 100 100 100 18
Nhìn vào bảng kết quả thực nghiệm có thể thấy được trong đa
số các trường hợp thì độ chính xác của bộ kết hợp Boosting cao hơn
so với hai bộ phân loại đơn lẻ và cả bộ phân loại của Random Forest.
Độ chính xác của Radom Forest lớn hơn của J48 trong hầu hết các
trường hợp, nhưng hầu như lại thấp hơn độc chính xác của Naïve
Bayes.
3.4. KẾT LUẬN CHƯƠNG
Chương 3 đã đặt vấn đề cho bài toán “Phát hiện URL độc hại
bằng cách phân loại”. Sau đó trình bày phương thức biểu diễn các
URL bằng các đặc trưng, xây dựng các bộ phân loại dựa vào bộ dữ
liệu huấn luyện và đưa ra kết quả của quá trình thực nghiệm với 2 bộ
phân loại đơn lẻ J48, Naïve Bayes và 2 bộ kết hợp các bộ phân loại
Boosting, Random Forest. Chúng ta đã chứng minh thực nghiệm
rằng so với các bộ phân loại đơn lẻ, thì phương pháp kết hợp các bộ

[2] Jeke S.H.Chan and Nik Kasabov(2005), Fast Neural Network
Ensemble Learning via Negative-Correlation Data Correction,
IEEE Transactions on Neural Networks Vol 16.
[3] Martin Sewell (2008), Ensemble Learning, Department of
Computer Science University Collage London.