ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Hà Văn Sang

NGHIÊN CỨU CẢI TIẾN CÁC KỸ THUẬT RÚT GỌN
ĐẶC TRƯNG CHO PHÂN LỚP DỮ LIỆU

LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN

HÀ NỘI – 2018


ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Hà Văn Sang

NGHIÊN CỨU CẢI TIẾN CÁC KỸ THUẬT RÚT
GỌN ĐẶC TRƯNG CHO PHÂN LỚP DỮ LIỆU

Chuyên ngành: Hệ thống thông tin
Mã số: 62.48.01.04
LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN

NGƯỜI HƯỚNG DẪN KHOA HỌC:
1. PGS. TS. NGUYỄN HÀ NAM
2. PGS. TS. NGUYỄN HẢI CHÂU

Hà Nội – 2018


trình tôi làm nghiên cứu sinh.
Tôi cũng gửi lời cảm ơn tất cả bạn bè, những người đã giúp đỡ và hỗ trợ tôi
trong suốt quá trình nghiên cứu.
Cuối cùng, tôi vô cùng biết ơn gia đình, bố mẹ tôi, anh chị em, đặc biệt là vợ
của tôi, những người đã động viên, tạo mọi điều kiện thuận lợi để tôi có thể hoàn
thành chương trình nghiên cứu sinh của mình.
Hà Văn Sang

Hà Nội, 1-12-2017

ii


TÓM TẮT
Rút gọn đặc trưng ngày càng được sử dụng rộng rãi nhằm tăng hiệu năng cũng
như giảm chi phí trong quá trình phân tích dữ liệu. Mục tiêu của việc rút gọn đặc
trưng là xác định và giảm bớt đặc trưng của dữ liệu gốc dựa trên việc biến đổi không
gian đặc trưng hoặc lựa chọn những đặc trưng quan trọng, loại bỏ các đặc trưng không
liên quan, dư thừa nhằm giảm kích thước dữ liệu, từ đó cải thiện hiệu quả, độ chính
xác của các mô hình phân tích dữ liệu. Các kỹ thuật rút gọn đặc trưng đã được áp
dụng rộng rãi trong nhiều ứng dụng khác nhau như: cho điểm tín dụng, phân tích dữ
liệu ung thư, tìm kiếm thông tin, phân lớp văn bản. Tuy nhiên, không tồn tại một kỹ
thuật rút gọn đặc trưng mà hiệu quả trên mọi miền dữ liệu. Trong luận án này, chúng
tôi tập trung vào việc tìm hiểu, phân tích và cải tiến một số kỹ thuật rút gọn đặc trưng
nhằm tăng hiệu năng của kỹ thuật phân tích dữ liệu hiện có theo hai hướng tiếp cận
là lựa chọn đặc trưng và trích xuất đặc trưng.
Có nhiều cách tiếp cận rút gọn đặc trưng khác nhau đã được giới thiệu, tuy
nhiên các cách tiếp cận này vẫn tồn tại một số hạn chế khi áp dụng với các miền dữ
liệu khác nhau. Chúng tôi đã đề xuất phương pháp lựa chọn đặc trưng có tên FRFE
(Fast Recursive Feature Elimination) dựa trên hướng tiếp cận đóng gói (wrapper) với

DANH MỤC TỪ VIẾT TẮT ....................................................................................... VII
DANH MỤC HÌNH ẢNH............................................................................................... IX
DANH MỤC BẢNG BIỂU ............................................................................................. XI
MỞ ĐẦU ............................................................................................................................ 1
Tính cấp thiết của luận án ................................................................................................... 1
Mục tiêu của luận án ........................................................................................................... 3
Đối tượng và phạm vi nghiên cứu ...................................................................................... 4
Phương pháp nghiên cứu .................................................................................................... 4
Đóng góp của luận án ......................................................................................................... 4
Bố cục của luận án .............................................................................................................. 5
CHƯƠNG 1.

TỔNG QUAN VỀ RÚT GỌN ĐẶC TRƯNG ................................... 7

1.1

Rút gọn đặc trưng ...................................................................................................... 7

1.2

Lựa chọn đặc trưng.................................................................................................... 7

1.3

1.4

1.2.1

Mục tiêu của lựa chọn đặc trưng ..................................................................... 8


1.4.2

Hướng nghiên cứu về trích xuất đặc trưng.................................................... 27

1.4.3

Phân tích và đánh giá .................................................................................... 30
v


1.5

Kết luận chương ...................................................................................................... 31

CHƯƠNG 2.

KỸ THUẬT LỰA CHỌN ĐẶC TRƯNG TRONG BÀI TOÁN CHO

ĐIỂM TÍN DỤNG ............................................................................................... 32
2.1

Bài toán cho điểm tín dụng ..................................................................................... 32

2.2

Các nghiên cứu liên quan ........................................................................................ 35

2.3

Phương pháp đề xuất ............................................................................................... 37

2.4.4

Kết quả thực nghiệm ..................................................................................... 53

Kết luận chương ...................................................................................................... 66

CHƯƠNG 3.

KỸ THUẬT TRÍCH XUẤT ĐẶC TRƯNG TRONG BÀI TOÁN

PHÂN TÍCH DỮ LIỆU UNG THƯ .................................................................. 67
3.1

Bài toán phân tích dữ liệu ung thư .......................................................................... 67

3.2

Các nghiên cứu liên quan ........................................................................................ 69

3.3

Phương pháp giải quyết ........................................................................................... 71

3.4

3.5

3.3.1

Sơ đồ hệ thống trích xuất đặc trưng .............................................................. 71


DANH MỤC TỪ VIẾT TẮT

Từ viết tắt
ACO
AUC
BG
CFS
DL
DT
FCFS
FRFE
GA
ICA
IG
KDD
k-NN
LDA
LR
MLP
mRMR
OLTP
PCA
PSO
RF
RG
SA
SBE
SBG
SBS

Random Forest
Random Generation
Simulated Annealing
Sequential Backward Elimination
Sequential Backward Generation
Sequential Sackward Search
Sequential Forward Generation

Tối ưu đàn kiến
Diện tích dưới đường cong
Sinh tập con từ hai hướng
Lựa chọn đặc trưng dựa trên
tương quan
Học sâu
Cây quyết định
Lựa chọn đặc trưng dựa trên
tương quan nhanh
Loại bỏ đặc trưng đệ quy nhanh
Thuật toán di truyền
Phân tích thành phần độc lập
Độ lợi thông tin
Khám phá tri thức

vii

k-láng giềng gần nhất
Phân tích biệt thức tuyến tính
Hồi qui logistic
Perceptron nhiều tầng
Phù hợp nhiều nhất-dư thừa ít

Hình 1.2 Ba thành phần chính của lựa chọn đặc trưng[59] ................................................... 9
Hình 1.3 Thủ tục lựa chọn đặc trưng[86] ............................................................................ 12
Hình 1.4 Mô hình chọn lựa đặc trưng Lọc........................................................................... 13
Hình 1.5 Mô hình chọn lựa đặc trưng đóng gói ................................................................... 14
Hình 1.6 Trích xuất đặc trưng. ............................................................................................. 16
Hình 2.1 Quy trình lựa chọn đặc trưng của bài toán cho điểm tín dụng .............................. 37
Hình 2.2 Sơ đồ khối của thuật toán lựa chọn đặc trưng theo hướng tiến ............................ 39
Hình 2.3 Sơ đồ khối của lựa chọn đặc trưng theo hướng lui ............................................... 41
Hình 2.4 Chiến lược lựa chọn đặc trưng FRFE ................................................................... 44
Hình 2.5 Kiến trúc của thư viện H20 ................................................................................... 46
Hình 2.6 Phân lớp Random forest........................................................................................ 47
Hình 2.7 Ví dụ về đường cong AUC [27] ........................................................................... 51
Hình 2.8 Kiểm chứng chéo 5 lần ......................................................................................... 52
Hình 2.9 Danh sách các đặc trưng được sắp xếp theo độ lợi thông tin (IG) giảm dần ........ 53
Hình 2.10 Danh sách các đặc trưng được sắp xếp theo độ đo Relief-F giảm dần ............... 54
Hình 2.11 Danh sách các đặc trưng được sắp xếp theo độ tương quan giảm dần ............... 55
Hình 2.12 So sánh kết quả dự đoán sử dụng 5, 10, 15, 20 đặc trưng có thứ hạng cao nhất
trên bộ dữ liệu của Đức ................................................................................................ 56
Hình 2.13 Độ chính xác phân lớp với bộ dữ liệu Đức ......................................................... 56
Hình 2.14 Độ chính xác phân lớp trên bộ dữ liệu Đức theo hướng quay lui ....................... 58
Hình 2.15 So sánh kết quả sử dụng đặc trưng được lựa chọn trên bộ dữ liệu Đức ............. 58
Hình 2.16 Xếp hạng đặc trưng theo độ lợi thông tin (IG) trên bộ dữ liệu tín dụng của Úc. 60
ix


Hình 2.17 Xếp hạng đặc trưng theo độ đo Relief-F trên bộ dữ liệu tín dụng của Úc .......... 61
Hình 2.18 Xếp hạng đặc trưng theo độ tương quan trên bộ dữ liệu tín dụng của Úc .......... 62
Hình 2.19 So sánh kết quả dự đoán sử dụng 5, 7, 10 đặc trưng có thứ hạng cao nhất trên bộ
dữ liệu tín dụng của Úc................................................................................................. 63
Hình 2.20 Độ chính xác phân lớp với bộ dữ liệu Úc ........................................................... 63

Bảng 3.7 Kết quả huấn luyện lựa chọn hàm nhân với bộ ung thư bạch cầu ........................ 86
Bảng 3.8 So sánh với hàm nhân cơ sở trên bộ dữ liệu ung thư bạch cầu ............................ 87
Bảng 3.9 So sánh kết quả phân lớp dự đoán trên bộ dữ liệu ung thư bạch cầu ................... 88
Bảng 3.10 Kết quả huấn luyện lựa chọn hàm nhân với bộ ung thư máu trắng .................... 88
Bảng 3.11 So sánh hàm nhân tùy chọn với hàm nhân cơ sở trên bộ dữ liệu máu trắng ...... 89
Bảng 3.12 So sánh kết quả phân lớp dự đoán trên bộ dữ liệu lymphoma ........................... 90
Bảng 3.13 Kết quả huấn luyện lựa chọn hàm nhân với bộ ung thư tuyến tiền liệt .............. 90
xi


Bảng 3.14 So sánh hàm nhân tùy chọn với hàm nhân cơ sở trên bộ dữ liệu ung thư tiền liệt
tuyến ............................................................................................................................. 91
Bảng 3.15 So sánh kết quả phân lớp dự đoán trên bộ dữ liệu ung thư tuyến tiền liệt ......... 92
Bảng 3.16 So sánh phương pháp đề xuất(C-KPCA) với các phương pháp lựa chọn đặc
trưng khác ..................................................................................................................... 94
Bảng 3.17 So sánh C-KPCA với các phương pháp khác trên hai bộ dữ liệu Colon và
Prostate ......................................................................................................................... 95
Bảng 3.18 So sánh C-KPCA với các phương pháp khác trên hai bộ dữ liệu Lymphoma và
Prostate ......................................................................................................................... 95

xii


MỞ ĐẦU
Tính cấp thiết của luận án
Trong những năm gần đây, dữ liệu trong thực tế đã gia tăng một cách nhanh
chóng cả về dung lượng lẫn về chủng loại. Dữ liệu với số chiều lớn đã trở thành thách
thức đối với các kỹ thuật xử lý, phân tích dữ liệu hiện có. Học máy (machine learning)
và khai phá dữ liệu (data mining) cung cấp các công cụ giúp con người giải quyết vấn
đề quản lý, bóc tách thông tin và tri thức bằng cách tự động phân tích một lượng lớn

Osiris Villacampa [91] nghiên cứu phương pháp lựa chọn đặc trưng và phân lớp cho
việc ra quyết định của công ty; Nziga [69] sử dụng phương pháp trích xuất đặc trưng
PCA thưa cho dòng dữ liệu. Verónica Bolón-Canedo cùng cộng sự [90] giới thiệu về
dữ liệu có số thuộc tính lớn và các phương pháp lựa chọn đặc trưng cho dữ liệu tin
sinh. Basant Agarwal và Namita Mittal [5] nghiên cứu trích xuất đặc trưng nổi bật
trong việc phân tích quan điểm. Urszula và Lakhmi [83] giới thiệu xu hướng nghiên
cứu về lựa chọn đặc trưng trong nhận dạng mẫu. Liang cùng cộng sự [56] nghiên cứu
về rút gọn đặc trưng cho bài toán học đa nhãn. Florian Eyben [26] trích xuất không
gian đặc trưng nhằm phân lớp dữ liệu âm thanh trực tuyến. Mark Nixon [68] sử dụng
các kỹ thuật trích xuất đặc trưng trong việc xử lý ảnh. Tuy nhiên, các phương pháp
rút gọn đặc trưng khác nhau sẽ cho kết quả khác nhau với từng miền ứng dụng tương
ứng.
Cộng đồng nghiên cứu tại Việt Nam đã quan tâm và công bố nhiều công trình
khoa học liên quan tới học máy và khai phá dữ liệu. Tuy nhiên, hướng nghiên cứu về
rút gọn đặc trưng chưa được quan tâm nhiều. Cụ thể, việc tìm kiếm từ khóa “lựa chọn

1



2


đặc trưng”, “lựa chọn thuộc tính”, hay “trích chọn đặc trưng” trên Google Scholar2
cho kết quả chỉ khoảng vài chục tài liệu. Tài liệu liên quan tới lựa chọn đặc trưng,
trích xuất đặc trưng là kết quả nghiên cứu của một số trường đại học. Chẳng hạn gần
đây có một số luận án liên quan tới chủ đề rút gọn thuộc tính như: trong năm 2015,
Hà Đại Dương [2] nghiên cứu một số phương pháp trích chọn đặc trưng nhằm phát
hiện đám cháy qua dữ liệu ảnh; Vũ Văn Định [1] thực hiện việc rút gọn thuộc tính
trong bảng quyết định không đầy đủ theo hướng tiếp cận tập thô; Nguyễn Thị Lan

-

Tìm hiểu kỹ thuật hàm nhân trong việc biến đổi không gian đặc trưng.

-

Xây dựng hàm nhân mới phù hợp với dữ liệu cần phân tích.
Với mục tiêu cải tiến hiệu năng của các kỹ thuật phân tích dữ liệu, chúng tôi

đã lựa chọn đề tài của luận án với tiêu đề: "Nghiên cứu cải tiến các kỹ thuật rút gọn
đặc trưng cho phân lớp dữ liệu”.

Đối tượng và phạm vi nghiên cứu
Đối tượng nghiên cứu của luận án là kỹ thuật rút gọn đặc trưng cho bài toán
phân lớp, theo hai hướng tiếp cận lựa chọn đặc trưng và trích xuất đặc trưng.
Phạm vi áp dụng các kỹ thuật rút gọn đặc trưng vào các miền ứng dụng là
tương đối rộng. Trong luận án này, chúng tôi giới hạn phạm vi với hai miền ứng dụng
là bài toán cho điểm tín dụng và phân tích dữ liệu ung thư.

Phương pháp nghiên cứu
Luận án sử dụng các phương pháp phân tích, tổng hợp lý thuyết, phương pháp
mô hình hóa và phương pháp nghiên cứu thực nghiệm. Trong đó, lý thuyết cơ sở được
phân tích và phương pháp đề xuất được mô hình hóa. Cuối cùng phương pháp nghiên
cứu thực nghiệm được dùng để đánh giá, kiểm chứng kết quả của phương pháp đề
xuất.

Đóng góp của luận án
Luận án đề xuất phương pháp rút gọn đặc trưng nhằm tăng hiệu năng của các
kỹ thuật phân lớp theo hai hướng tiếp cận chính là lựa chọn đặc trưng và trích xuất
đặc trưng:

trình. Trong đó có 02 bài báo đăng ở tạp chí nước ngoài [SANGHV1, SANGHV2];
03 bài báo hội thảo quốc tế được công bố có chỉ số Scopus, trong đó 02 bài báo được
Springer xuất bản và đưa vào danh mục LNCS.

Bố cục của luận án
Ngoài phần mở đầu, mục lục, kết luận và tài liệu tham khảo, nội dung chính
của luận án này được chia thành 03 chương, cụ thể như sau:
5


Chương 1: Phần đầu giới thiệu về lý thuyết cơ bản liên quan tới rút gọn đặc
trưng, lựa chọn đặc trưng và trích xuất đặc trưng, đồng thời điểm lại một số nghiên
cứu gần đây. Sau phần phân tích, đánh giá là kết luận của chương.
Chương 2: Đề xuất một hàm đánh giá đặc trưng và áp dụng chiến lược tìm
kiếm theo kinh nghiệm dựa trên hàm đánh giá này nhằm nâng hiệu quả của việc lựa
chọn đặc trưng. Sau khi trình bày về quy trình, giải pháp đề xuất, luận án áp dụng
phương pháp đề xuất cho bộ dữ liệu tín dụng. Phần còn lại của chương thực hiện thực
nghiệm trên các bộ dữ liệu tín dụng và so sánh kết quả với một số phương pháp lựa
chọn đặc trưng khác.
Chương 3: Đề xuất một phương pháp trích xuất đặc trưng dựa trên việc xây
dựng một hàm nhân mới trên cơ sở kết hợp một số hàm nhân cơ bản nhằm biến đổi
không gian đặc trưng phù hợp với miền dữ liệu. Sau khi trình bày về quy trình,
phương pháp đề xuất, phương pháp đề xuất được tiến hành trên bốn bộ dữ liệu ung
thư. Việc thực nghiệm và so sánh với một số kỹ thuật khác được thực hiện ở phần
còn lại của chương.

6


Chương 1.

Lựa chọn đặc trưng

Lựa chọn đặc trưng (Feature Selection): chọn lựa một tập con các đặc trưng
từ các đặc trưng ban đầu mà không có sự thay đổi về giá trị của đặc trưng.
x 𝑖1
x1
x2 𝑙ự𝑎 𝑐ℎọ𝑛 đặ𝑐 𝑡𝑟ư𝑛𝑔 x𝑖2
[ ⋮ ]→
[ ⋮ ]
xN
x 𝑖M

(𝑀 < 𝑁)

Hình 1.1 Lựa chọn đặc trưng.

7


Lựa chọn đặc trưng là một trong những phương pháp hết sức tự nhiên để giải
quyết vấn đề loại bỏ các đặc trưng dư thừa, trùng lặp và không liên quan trong dữ
liệu. Kết quả của lựa chọn đặc trưng là một tập con các đặc trưng từ tập đặc trưng ban
đầu nhưng vẫn đảm bảo các tính chất của dữ liệu gốc. Lựa chọn đặc trưng giúp: (1)
cải tiến hiệu năng (về tốc độ, khả năng dự đoán, và đơn giản hóa mô hình); (2) trực
quan hóa dữ liệu cho việc lựa chọn mô hình; (3) giảm chiều và loại bỏ nhiễu.
1.2.1

Mục tiêu của lựa chọn đặc trưng

Mục tiêu chính của lựa chọn đặc trưng là xác định các đặc trưng quan trọng và


8


1.2.3

Các thành phần chính của lựa chọn đặc trưng

Liu và Motoda [59] chỉ ra ba thành phần chính của lựa chọn đặc trưng là: (1)
Chiến lược tìm kiếm tập con, (2) Hướng tìm kiếm hay nguyên tắc lựa chọn, bổ sung,
loại bỏ hoặc thay đổi đặc trưng trong quá trình tìm kiếm, và (3) Tiêu chí đánh giá các
tập con khác nhau. Hình 1.2 dưới đây thể hiện lựa chọn đặc trưng theo 3 thành phần
nói trên.
Tiêu chí đánh giá
Chính xác
Nhất quán
Toàn bộ Kinh nghiệm
Cơ bản

Không xác định

Chiến lược tìm kiếm
Tiến
Lùi
Ngẫu nhiên
Hướng tìm kiếm

Hình 1.2 Ba thành phần chính của lựa chọn đặc trưng[59]

(1) Chiến lược tìm kiếm

Việc tìm kiếm tập con các đặc trưng tối ưu trong không gian tìm kiếm có thể
bắt đầu từ một tập rỗng sau đó lần lượt thêm từng đặc trưng hoặc bắt đầu từ một tập
đủ các đặc trưng rồi loại bỏ từng đặc trưng. Với việc tìm kiếm như vậy thì thời gian
trung bình để tìm ra tập con tối ưu giữa các hướng tìm kiếm khác nhau không có sự
khác biệt. Việc tạo ra tập con các đặc trưng có mối liên hệ chặt chẽ với hướng tìm
kiếm.
Tìm kiếm tiến tuần tự (Sequential Forward Generation-SFG): Bắt đầu từ một
tập rỗng các đặc trưng Sselect Tại mỗi bước tìm kiếm, dựa trên một số tiêu chí nhất
định, một đặc trưng được thêm vào tập Sselect. Quá trình tìm kiếm này sẽ dừng lại khi
tất cả các đặc trưng trong tập đặc trưng ban đầu được thêm vào Sselect . Kết quả là một
danh sách xếp hạng các đặc trưng được tạo ra theo thứ tự được thêm vào Sselect.
Tìm kiếm lùi tuần tự (Sequential Backward Generation-SBG): Bắt đầu với
một tập đủ các đặc trưng. Tại mỗi bước tìm kiếm dựa vào một số tiêu chí nào đó, một
đặc trưng ít quan trọng nhất sẽ bị loại bỏ. Các đặc trưng trong tập đặc trưng sẽ dần bị

10


loại bỏ cho tới khi trong tập đặc trưng chỉ còn lại một đặc trưng. Kết quả là một danh
sách xếp hạng các đặc trưng theo thứ tự bị loại được tạo ra.
SBG và SFG là hai phương pháp bổ sung cho nhau vì đôi khi tìm ra đặc trưng
quan trọng nhất là dễ dàng hơn so với tìm ra đặc trưng ít quan trọng và ngược lại.
Tìm kiếm theo hai hướng (Birectional Generation-BG): Nếu trong trường hợp
tập đặc trưng tối ưu không nằm trong khu vực giữa của không gian tìm kiếm, thì việc
bắt đầu tìm kiếm từ cả hai phía của không gian tìm kiếm là giải pháp phù hợp. Quá
trình tìm kiếm sẽ được bắt đầu từ hai hướng một cách đồng thời. Khi một trong hai
chiều tìm kiếm tìm được M đặc trưng tốt nhất trước khi đi đến điểm giữa trong không
gian tìm kiếm thì quá trình dừng lại. Nếu cả hai chiều tìm kiếm tiến đến điểm giữa
trong không gian tìm kiếm thì quá trình cũng kết thúc.
Khi số lượng các đặc trưng liên quan M là nhỏ hơn N/2, SFG chạy nhanh hơn,

Hướng tìm kiếm

11