Luận án Tiến sĩ Công nghệ thông tin: 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 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

LỜI CAM ĐOAN

Tôi xin cam đoan đây là công trình nghiên cứu do tôi thực hiện dưới sự hướng

dẫn của PGS.TS. Nguyễn Hà Nam và PGS.TS. Nguyễn Hải Châu tại Bộ môn các Hệ

thống Thông tin, Khoa Công nghệ Thông tin, Trường Đại học Công nghệ, Đại học

Quốc gia Hà nội. Các số liệu và kết quả trình bày trong luận án là trung thực và chưa

được công bố trong bất cứ các công trình nào khác trước đây.

Tác giả

Hà Văn Sang

LỜI CẢM ƠN

Luận án được thực hiện tại Bộ môn Hệ thống Thông tin-Khoa CNTT, Trường

Đại học Công nghệ, Đại học Quốc gia Hà Nội, dưới sự hướng dẫn của PGS.TS.

Nguyễn Hà Nam và PGS.TS. Nguyễn Hải Châu.

Trước tiên, tôi xin bày tỏ lòng biết ơn sâu sắc tới PGS.TS. Nguyễn Hà Nam

và PGS.TS. Nguyễn Hải Châu. Hai Thầy đã tận tụy chỉ dạy, giúp đỡ tôi từ định hướng

nghiên cứu đến việc giải quyết những vấn đề khó khăn nhất trong quá trình nghiên

cứu. Không chỉ về lĩnh vực nghiên cứu khoa học, các Thầy còn chỉ bảo cho tôi nhiều

điều trong cuộc sống. Đó là những bài học vô cùng quý giá và hữu ích cho chính bản

thân tôi trong thời gian tới.

Tôi cũng xin gửi lời cảm ơn tới tập thể các Thầy, Cô giáo, các nhà khoa học

trong khoa CNTT đã truyền đạt cho tôi những kiến thức quý báu và đã tạo điều kiện

thuận lợi cho tôi trong quá trình học tập và nghiên cứu.

Tôi xin gửi lời cảm ơn tới các Thầy, Cô giáo ở Bộ môn Tin học Tài chính kế

toán, khoa Hệ thống Thông tin kinh tế, Học viện Tài chính, những người đồng nghiệp

đã tạo điều kiện giúp đỡ tôi về mặt thời gian cũng như sắp xếp công việc trong quá

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

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

lõi là một thủ tục loại bỏ đặc trưng đệ quy. Để tăng hiệu quả của việc lựa chọn đặc

trưng, chúng tôi đã đề xuất một hàm đánh giá (ranking) đặc trưng và thủ tục lựa chọn

đặc trưng tương ứng. Hơn nữa, do đặc điểm của phương pháp lựa chọn đặc trưng

đóng gói là chi phí tính toán cao, vì vậy chúng tôi đã áp dụng các thư viện xử lý phân

tán để cải thiện hiệu năng của thuật toán đề xuất. Kết quả thực nghiệm thuật toán

FRFE (được viết bằng ngôn ngữ R) trên hai bộ dữ liệu tín dụng Đức và Úc cho thấy

thuật toán đề xuất đã cải thiện được thời gian chạy so với thuật toán cơ sở và đạt kết

quả khả quan so với các kỹ thuật hiện có.

Theo hướng tiếp cận trích xuất đặc trưng, chúng tôi đã đề xuất phương pháp

trích xuất đặc trưng có tên C-KPCA (Custom-Kernel PCA) nhằm làm giảm số lượng

iii

đặc trưng dựa trên kỹ thuật hàm nhân PCA. Đóng góp chính của phương pháp đề xuất

là xây dựng một hàm nhân mới dựa trên việc kết hợp có định hướng một số hàm nhân

cơ bản [67]. Kết quả thực nghiệm thuật toán C-KPCA trên bốn bộ dữ liệu ung thư

cho thấy thuật toán đề xuất cho kết quả ổn định và tốt hơn so với các phương pháp

khác trong nhiều trường hợp.

Từ khóa: khai phá dữ liệu, học máy, lựa chọn đặc trưng, trích xuất đặc trưng,

rút gọn đặc trưng, KPCA

MỤC LỤC

LỜI CAM ĐOAN ............................................................................................................... I

LỜI CẢM ƠN ................................................................................................................... II

TÓM TẮT ........................................................................................................................ III

MỤC LỤC ........................................................................................................................ V

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.2.1 Mục tiêu của lựa chọn đặc trưng ..................................................................... 8

1.2.2 Phân loại các kỹ thuật lựa chọn đặc trưng ...................................................... 8

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

1.2.4 Thủ tục lựa chọn đặc trưng ........................................................................... 12

1.2.5 Các mô hình lựa chọn đặc trưng ................................................................... 13

1.3 Trích xuất đặc trưng ................................................................................................ 16

1.3.1 Mục tiêu của trích xuất đặc trưng ................................................................. 17

1.3.2 Phân loại các kỹ thuật trích xuất đặc trưng ................................................... 17

1.4 Một số nghiên cứu về rút gọn đặc trưng ................................................................. 19

1.4.1 Hướng nghiên cứu về lựa chọn đặc trưng ..................................................... 19

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

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.3.1 Sơ đồ hệ thống lựa chọn đặc trưng ................................................................ 37

2.3.2 Đề xuất hàm đánh giá và chiến lược tìm kiếm đặc trưng phù hợp ............... 38

2.3.3 Cải tiến tốc độ xử lý bằng thư viện H20 ....................................................... 45

2.4 Thực nghiệm và kết quả .......................................................................................... 48

2.4.1 Thiết lập thực nghiệm ................................................................................... 48

2.4.2 Dữ liệu thực nghiệm ...................................................................................... 49

2.4.3 Đánh giá hiệu năng phân lớp......................................................................... 49

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

2.5 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.3.1 Sơ đồ hệ thống trích xuất đặc trưng .............................................................. 71

3.3.2 Hàm nhân tùy chọn cho PCA ........................................................................ 73

3.3.3 Xây dựng hàm nhân tùy chọn ....................................................................... 77

3.4 Thực nghiệm và kết quả .......................................................................................... 82

3.4.1 Thiết lập thực nghiệm ................................................................................... 82

3.4.2 Dữ liệu thực nghiệm ...................................................................................... 82

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

3.5 Kết luận chương ...................................................................................................... 96

KẾT LUẬN ...................................................................................................................... 97

DANH MỤC CÔNG TRÌNH KHOA HỌC LIÊN QUAN ĐẾN LUẬN ÁN .............. 99

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

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

Từ viết tắt Từ gốc Giải nghĩa

ACO AUC BG CFS

DL DT FCFS

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

FRFE GA ICA IG KDD 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

k-NN LDA LR MLP mRMR

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 nhất Xử lý giao dịch trực tuyến Phân tích thành phần chính Tối ưu hóa bầy đàn Rừng ngẫu nhiên Sinh tập con ngẫu nhiên Thuật toán mô phỏng tôi luyện

vii

OLTP PCA PSO RF RG SA SBE SBG SBS SFG Ant Colony Optimization Area under curve Bidirectional Generation Correlation-based Feature Selection Deep Learning Decision Tree Fast Correlation-based Feature Selection Fast Recursive Feature Elimination Loại bỏ đặc trưng đệ quy nhanh Genetic Algorithm Independent component analysis Information Gain Knowledge Discovery in Databases k-Nearest Neighbors Linear discriminant analysis Logistic Regression Multi-layer Perceptron minimum Redundancy Maximum Relevance Online transaction processing Principal Component Analysis Particle Swarm Optimization Random Forest Random Generation Simulated Annealing Sequential Backward Elimination Loại bỏ lùi tuần tự Sequential Backward Generation Sequential Sackward Search Sequential Forward Generation Sinh tập con lùi tuần tự Tìm kiếm lùi tuần tự Sinh tập con tiến tuần tự

SFS SVD SVM Tìm kiếm tiến tuần tự Phân tích giá trị riêng Máy véc tơ hỗ trợ

viii

Sequential forward search Singular Value Decomposition Support Vector Machine

DANH MỤC HÌNH ẢNH

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

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

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

Hình 2.21 Độ chính xác dự đoán trên bộ dữ liệu tín dụng Úc ............................................. 65

Hình 2.22 Độ chính xác dự đoán sử dụng đặc trưng được lựa chọn trên bộ dữ liệu Úc ..... 65

Hình 3.1 Phân tích dữ liệu ung thư ...................................................................................... 68

Hình 3.2 Quy trình trích xuất đặc trưng cho bài toán phân tích dữ liệu ung thư ................. 71

Hình 3.3 Chuyển dữ liệu sang không gian có chiều lớn hơn[21] ........................................ 74

Hình 3.4 Độ chính xác phân lớp với bộ dữ liệu ung thư ruột kết ........................................ 85

Hình 3.5 Độ chính xác phân lớp với bộ dữ liệu ung thư bạch cầu ...................................... 87

Hình 3.6 Độ chính xác phân lớp với bộ dữ liệu lymphoma ................................................. 89

Hình 3.7 So sánh độ chính xác phân lớp với bộ dữ liệu ung thư tuyến tiền liệt .................. 91

Hình 3.8 So sánh hiệu năng phân lớp trên bốn bộ dữ liệu ung thư...................................... 93

DANH MỤC BẢNG BIỂU

Bảng 1.1 Chiến lược tìm kiếm và hướng tìm kiếm[59] ....................................................... 11

Bảng 1.2 Ưu nhược điểm của mô hình Lọc[8] .................................................................... 14

Bảng 1.3 Ưu nhược điểm của mô hình Đóng gói [8] .......................................................... 15

Bảng 1.4 So sánh ba mô hình[33] ........................................................................................ 16

Bảng 2.1 Ý nghĩa của diện tích dưới đường cong AUC ...................................................... 51

Bảng 2.2 So sánh hiệu năng của các bộ phân lớp [55] trên bộ dữ liệu tín dụng của Đức ... 57

Bảng 2.3. Hiệu năng của các bộ phân lớp khác nhau [55] với bộ dữ liệu tín dụng Đức ... 59

Bảng 2.4 So sánh hiệu năng của các bộ phân lớp trên bộ dữ liệu tín dụng của Úc ............. 64

Bảng 2.5 Hiệu năng của các bộ phân lớp khác nhau trên bộ dữ liệu tín dụng của Úc ........ 66

Bảng 3.1 Cấu trúc bảng dữ liệu ung thư ruột kết ................................................................. 72

Bảng 3.2 Các hàm nhân được sử dụng ................................................................................ 82

Bảng 3.3 Tổng hợp các bộ dữ liệu ung thư được sử dụng trong thực nghiệm .................... 83

Bảng 3.4 Kết quả huấn luyện lựa chọn hàm nhân với bộ ung thư ruột kết ......................... 84

Bảng 3.5 So sánh hàm nhân mới với hàm nhân cơ sở trên dữ liệu ung thư ruột kết ........... 85

Bảng 3.6 So sánh kết quả phân lớp dự đoán trên bộ dữ liệu ung thư ruột kết ..................... 86

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

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

dữ liệu. Tuy nhiên, các kỹ thuật phân tích dữ liệu như phân lớp, dự báo có thể dẫn

đến kết quả thấp hoặc không chính xác do không phải lúc nào dữ liệu cũng được xử

lý đầy đủ, vẫn có nhiều dữ liệu dư thừa, không liên quan, hay nhiễu. Ngoài ra, các

thuật toán phân lớp chạy mất nhiều thời gian, thậm chí có thể không thể thực hiện

được nếu dữ liệu chưa được tiền xử lý một cách thích hợp.

Rút gọn đặc trưng là kỹ thuật giải quyết vấn đề thu gọn chiều dữ liệu nhằm

giải quyết các vấn đề nêu trên. Rút gọn đặc trưng được phân loại thành “lựa chọn đặc

trưng” và “trích xuất đặc trưng”. Trong đó, lựa chọn đặc trưng có thể chọn ra một

nhóm con các đặc trưng phù hợp, liên quan từ tập dữ liệu gốc bằng cách loại bỏ các

đặc trưng nhiễu, dư thừa không liên quan trong khi đó trích xuất đặc trưng sẽ trích rút

ra các đặc trưng mới bằng một phép chuyển đổi. Rút gọn đặc trưng tạo điều kiện cho

các kỹ thuật phân tích xử lý dữ liệu cải tiến hiệu năng theo nghĩa nâng cao hiệu suất

mà vẫn giữ nguyên hoặc nâng cao được hiệu quả.

Nhiều kỹ thuật rút gọn đặc trưng đã được cộng đồng nghiên cứu trên thế giới

công bố [9][12][69][99]. Theo thống kê từ năm 2010 tới năm 2017 trên cơ sở dữ liệu

của Google scholar (https://scholar.google.com) thì có tới 88.500 tài liệu liên quan

tới chủ đề lựa chọn đặc trưng (tìm kiếm từ khóa “Feature Selection”), và có tới

159.000 tài liệu liên quan tới chủ đề trích xuất đặc trưng (tìm kiếm từ khóa “Feature

Extraction”). Cũng trong khoảng thời gian từ 2010-2017 trên cơ sở dữ liệu của trang

Sciencedirect1 thì chủ đề lựa chọn đặc trưng có trên 11.880 bài báo khoa học, trong

khi chủ đề trích chọn đặc trưng có hơn 32.980 bài báo liên quan.

Trong những năm gần đây, nhiều nghiên cứu đã tập trung vào cải tiến hiệu

năng của kỹ thuật rút gọn đặc trưng bằng cách lựa chọn tập con đặc trưng có ích, hoặc

trích xuất đặc trưng. Điển hình như luận án của Hall [34] đề xuất phương pháp lựa

chọn đặc trưng dựa trên tương quan cho học máy; Diao và cộng sự [23] sử dụng tìm

kiếm hài hòa (Harmony Search) cho việc xây dựng phương pháp lựa chọn đặc trưng.

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ề

1 http://www.sciencedirect.com

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

đặ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

Hương [3] nghiên cứu và rút gọn thuộc tính trong bảng quyết định động theo hướng

tiếp cận tập thô. Các luận án này đã đề xuất việc áp dụng một kỹ thuật lựa chọn hoặc

trích xuất đặc trưng vào bài toán của mình, tập trung chủ yếu tới bài toán xử lí ảnh.

Như vậy, có thể nhận thấy rằng rút gọn đặc trưng hiện vẫn là chủ đề để các

nhà nghiên cứu trong và ngoài nước tiếp tục nghiên cứu và phát triển.

Mục tiêu của luận án

Mục tiêu của luận án là nghiên cứu cải tiến một số kỹ thuật rút gọn đặc trưng

tiên tiến trong phân lớp dữ liệu đối với một số miền ứng dụng.

Hướng tiếp cận lựa chọn đặc trưng xác định một tập con đặc trưng tốt nhất có

thể từ tập đặc trưng ban đầu mà không làm giảm kết quả phân lớp. Để giải quyết mục

tiêu này, luận án tập trung giải quyết một số vấn đề sau:

- Xây dựng một hàm đánh giá đặc trưng phù hợp với dữ liệu cần phân tích.

- Áp dụng chiến lược tìm kiếm theo kinh nghiệm nhằm làm giảm không gian tìm

2 https://scholar.google.com.vn/

kiếm.

Hướng tiếp cận trích xuất đặc trưng xác định một phép biến đổi đặc trưng hiệu

quả để thu được tập đặc trưng mới phù hợp với bộ phân lớp tương ứng. Để giải quyết

mục tiêu này, luận án tập trung giải quyết một số vấn đề sau:

- 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:

Lựa chọn đặc trưng: chúng tôi đã đề xuất phương pháp lựa chọn đặc trưng (FRFE)

dựa trên hướng tiếp cận đóng gói. Nội dung chính của phương pháp đề xuất là việc

loại bỏ đặc trưng đệ quy và việc cải tiến hàm đánh giá đặc trưng. Hàm đánh giá đặc

trưng đề xuất có ưu điểm là giúp tăng hiệu quả phân lớp và giúp cho kết quả này

được ổn định hơn. Phương pháp đề xuất giúp tự động tìm ra tập con đặc trưng tối

ưu cho mỗi bộ dữ liệu. Một vấn đề khác mà các phương pháp lựa chọn đặc trưng

phải đối mặt đó là các phương pháp lựa chọn đặc trưng đóng gói (wrapper) có chi

phí tính toán lớn. Để giải quyết vấn đề này chúng tôi sử dụng bộ phân lớp rừng ngẫu

nhiên (random forest) với khả năng xử lý song song nhằm làm giảm thời gian thực

hiện của phương pháp đề xuất. Thực nghiệm trên bộ dữ liệu tín dụng cho thấy

phương pháp lựa chọn đặc trưng đề xuất này có khả năng đạt được mục tiêu mà luận

án đặt ra. Những đóng góp dựa trên hướng tiếp cận lựa chọn đặc trưng cho bài toán

cho điểm tín dụng được báo cáo trong các công bố [SANGHV1, SANGHV2,

SANGHV3, SANGHV5].

Trích xuất đặc trưng: Ngoài cách tiếp cận lựa chọn đặc trưng, một hướng tiếp cận

khác là trích xuất đặc trưng đã và đang được nhiều nhóm nghiên cứu quan tâm phát

triển khi các kỹ thuật lựa chọn đặc trưng trở nên ít hiệu quả. Chúng tôi đã đề xuất kỹ

thuật trích xuất đặc trưng có tên C-KPCA (Custom-Kernel PCA) nhằm làm giảm số

lượng đặc trưng dựa trên kỹ thuật hàm nhân PCA. Cải tiến chính trong đề xuất của

chúng tôi là xây dựng một hàm nhân mới dựa trên việc kết hợp một số hàm nhân cơ

bản[40]. Chúng tôi đã tiến hành thực nghiệm trên 04 bộ dữ liệu ung thư và so sánh

kết quả khi sử dụng hàm nhân đề xuất với hàm nhân cơ bản cũng như so sánh với

một số phương pháp lựa chọn đặc trưng phổ biến khác. Thực nghiệm cho thấy C-

KPCA cho kết quả ổn định và tốt hơn so với các phương pháp khác trong nhiều

trường hợp. Hướng tiếp cận trích xuất đặc trưng cho bài toán phân tích dữ liệu ung

thư được công bố trong [SANGHV4].

Các kết quả nghiên cứu trình bày trong luận án được công bố trong 05 cô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:

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.

Chương 1.

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

Hầu hết các lĩnh vực khoa học và công nghệ ngày nay đều đòi hỏi phân tích

dữ liệu nhằm bóc tách các tri thức hữu ích giúp cải tiến hay nâng cao hiệu quả của

các lĩnh vực này. Dữ liệu quan sát và thu thập được từ những ứng dụng trong thực tế

thường chứa nhiều thông tin nhiễu, dư thừa, đặc biệt với tập dữ liệu có số lượng thuộc

tính lớn có thể dẫn tới việc tốn kém tài nguyên khi áp dụng kỹ thuật phân tích dữ liệu,

và nhiều trường hợp không thể thực hiện được. Xuất phát từ nhu cầu thực tiễn đó, các

kỹ thuật rút gọn đặc trưng được nghiên cứu và phát triển để giải quyết những vấn đề

trên. Nội dung chương này nhằm giới thiệu tổng quan về vấn đề rút gọn đặc trưng và

điểm lại một số hướng nghiên cứu về rút gọn đặc trưng tiêu biểu hiện nay. Phần cuối

của chương sẽ đưa ra một số phân tích, đánh giá một số kỹ thuật rút gọn đặc trưng

thường được áp dụng hiện nay.

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

Rút gọn đặc trưng được hiểu là quá trình thu gọn hoặc biến đổi không gian

biểu diễn dữ liệu ban đầu thành một không gian con hoặc một không gian mới có số

đặc trưng nhỏ hơn không gian ban đầu mà vẫn giữ được các đặc tính của dữ liệu gốc.

Trong nhiều trường hợp, tập dữ liệu ban đầu có chứa nhiều đặc trưng không liên quan

cho sự mô tả bản chất của hiện tượng mà ta quan tâm, khi đó có thể loại bỏ các đặc

trưng không liên quan này và chỉ giữ lại các đặc trưng quan trọng. Có hai phương

pháp để rút gọn đặc trưng gồm lựa chọn đặc trưng và trích xuất đặc trưng.

1.2 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

[

𝑙ự𝑎 𝑐ℎọ𝑛 đặ𝑐 𝑡𝑟ư𝑛𝑔 → [

]

] (𝑀 < 𝑁)

x1 x2 ⋮ xN

x𝑖1 x𝑖2 ⋮ x𝑖M

từ các đặc trưng ban đầu mà không có sự thay đổi về giá trị của đặc trưng.

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

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à

loại bỏ các đặc trưng không liên quan hoặc không phù hợp. Các thuật toán lựa chọn

đặc trưng khác nhau sẽ có thể có các mục tiêu khác nhau. Một số mục tiêu thường

được sử dụng:

- Tìm ra tập con các đặc trưng có kích cỡ nhỏ nhất có thể, mà nó là cần và đủ

cho việc phân tích dữ liệu (cụ thể ở đây là phân lớp)

- Chọn một tập con có M đặc trưng từ một tập gồm N đặc trưng ban đầu (M

trong đó giá trị của hàm mục tiêu được tối ưu trên tập con kích cỡ M.

- Chọn một tập con các đặc trưng nhằm cải tiến độ chính xác dự đoán hoặc làm

giảm kích cỡ của tập dữ liệu mà không làm giảm độ chính xác dự đoán của bộ

phân lớp.

1.2.2 Phân loại các kỹ thuật lựa chọn đặc trưng

Dựa vào tính sẵn có của thông tin nhãn lớp (label), kỹ thuật lựa chọn đặc trưng

có thể được chia thành ba loại: phương pháp có giám sát, bán giám sát, và không

giám sát. Thông tin nhãn có sẵn của lớp giúp cho các thuật toán lựa chọn đặc trưng

có giám sát lựa chọn được các đặc trưng phù hợp. Khi chỉ có một số ít dữ liệu đã

được gán nhãn, có thể sử dụng lựa chọn đặc trưng bán giám sát, trong đó có thể tận

dụng được lợi thế của cả dữ liệu được gán nhãn và dữ liệu không được gán nhãn. Hầu

hết các thuật toán lựa chọn đặc trưng bán giám sát đều dựa trên việc xây dựng ma

trận tương tự và lựa chọn các đặc trưng phù hợp nhất với ma trận tương tự đó.

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

Không xác định

Cơ bản

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

Do số tập con là 2N nên không gian tìm kiếm sẽ tăng theo hàm mũ khi N tăng

lên. Không gian tìm kiếm sẽ là tương đối nhỏ khi số lượng đặc trưng N là nhỏ. Khi

không gian tìm kiếm lớn thì chiến lược tìm kiếm được sử dụng sẽ ảnh hưởng lớn tới

hiệu năng của nó. Kết quả tìm kiếm phụ thuộc vào việc lựa chọn chiến lược tìm kiếm.

Mục tiêu là tìm được một tập con các đặc trưng tối ưu trong thời gian ít nhất có thể

theo các tiêu chí cho trước. Các chiến lược tìm kiếm có thể được chia thành 3 nhóm

dưới đây.

Tìm kiếm toàn bộ (chiến lược vét cạn): trong chiến lược này, tất cả các khả

năng có thể của các tập con sẽ được kiểm tra. Kết quả cuối cùng một tập con tốt nhất

theo tiêu chí tìm kiếm. Độ phức tạp không gian của chiến lược này trong trường hợp

tổng quát nhất là 𝛰(2𝑁). Khi biết trước được hướng tìm kiếm, thì không gian tìm

0) + (𝑁

𝑀) Trong đó, M là số lượng đặc trưng tối thiểu của một

1) + ⋯ + (𝑁 tập con thỏa mãn một số tiêu chí đánh giá nào đó.

kiếm sẽ là (𝑁

Tìm kiếm theo kinh nghiệm: là quá trình tìm kiếm sử dụng hàm đánh giá để

hướng dẫn sự tìm kiếm. Mục tiêu của hàm đánh giá nhằm xác định theo kinh nghiệm

định hướng để tìm được tập con tối ưu. Chiến lược tìm kiếm theo kinh nghiệm chỉ

thực hiện theo một lộ trình cụ thể và tìm ra một tập con gần tối ưu nên nó cho kết quả

nhanh hơn so với chiến lược tìm kiếm vét cạn.

Tìm kiếm không xác định: chiến lược này khác với hai chiến lược kể trên ở

chỗ nó tìm kiếm tập con kế tiếp một cách ngẫu nhiên. Chiến lược này thường được

áp dụng trong không gian tìm kiếm khá lớn và tồn tại nhiều giá trị tối ưu cục bộ. Ưu

điểm chính là của chiến lược này là tránh được các tối ưu cục bộ và tương đối dễ cài

đặt.

(2)Hướng 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ị

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,

ngược lại nếu M lớn hơn N/2 khi đó SBG chạy nhanh hơn. Thường thì giá trị của M

là không biết trước nên ta không thể biết chiến lược nào chạy nhanh hơn. Khi đó BG

có ý nghĩa.

Tìm kiếm ngẫu nhiên (Random Generation-RG): việc tìm kiếm được bắt đầu

theo một hướng ngẫu nhiên. Trong khi tìm kiếm việc thêm hay loại bỏ bớt một đặc

trưng cũng được thực hiện một cách ngẫu nhiên. Do chiến lược tìm kiếm không đi

theo một chiều cố định nào đó trong việc tạo ra tập đặc trưng tối ưu nên phương pháp

này tránh được các tối ưu địa phương. Mối quan hệ giữa hướng tìm kiếm và chiến

lược tìm kiếm được mô tả trong Bảng 1.1. Ký hiệu × thể hiện sự kết hợp giữa chiến

lược tìm kiếm và hướng tìm kiếm là không khả thi.

Bảng 1.1 Chiến lược tìm kiếm và hướng tìm kiếm[59]

Hướng tìm kiếm Chiến lược tìm kiếm Toàn bộ Kinh nghiệm Không xác định

√ √ √ × √ √ √ √ × × × √

Tìm kiếm tiến tuần tự Tìm kiếm lùi tuần tự Tìm kiếm theo hai hướng Tìm kiếm ngẫu nhiên

(3)Tiêu chí đánh giá

Sau khi xem xét về chiến lược và hướng tìm kiếm, vấn đề tiếp theo cần xem

xét là đánh giá một đặc trưng là có ích hay xác định tập con đặc trưng được lựa chọn

là tốt hay không tốt. Cần phải phân biệt giữa tập con tốt nhất và tập con tối ưu đối với

các kỹ thuật lựa chọn đặc trưng. Việc đánh giá này thường là phức tạp và có nhiều

tiêu chí đánh giá khác nhau. Chẳng hạn việc đánh giá có thể xem xét xem các đặc

trưng được chọn lựa có làm tăng độ chính xác của bộ phân lớp hay không? Các đặc

trưng được chọn lựa có giúp làm giảm chi phí tính toán hay không? Một số độ đo

thường được sử dụng trong lựa chọn đặc trưng gồm có độ đo chính xác, độ lợi thông

tin (Information Gain), độ đo khoảng cách, độ đo phụ thuộc, độ đo nhất quán.

1.2.4 Thủ tục lựa chọn đặc trưng

Mặc dù lựa chọn đặc trưng có thể được áp dụng với nhiều mô hình học, tuy

nhiên trong khuôn khổ luận án này chúng tôi chỉ tập trung vào việc nghiên cứu kỹ

thuật lựa chọn đặc trưng để tăng hiệu năng của các bộ phân lớp. Dash và Liu [86]

chia tiến trình lựa chọn đặc trưng thành bốn khối chính: Sinh tập con, đánh giá, điều

Tập con

Tập đặc trưng ban đầu

Sinh tập con

Đánh giá

Đúng

Sai

Kiểm chứng kết quả

Điều kiện dừng

kiện dừng và kiểm chứng kết quả (Hình 1.3).

Hình 1.3 Thủ tục lựa chọn đặc trưng[86]

Sinh tập con: là việc tìm kiếm trong không gian của các đặc trưng để có được

các tập con có khả năng phân lớp và dự đoán tốt nhất. Với N là số các đặc trưng thì

tổng số tập con có thể có là 2N, nên việc duyệt qua tất cả các tập con của các đặc trưng

là tốn kém.

Đánh giá: sau khi sinh tập con các đặc trưng, người ta sử dụng một hàm hoặc

một bộ tiêu chí để đánh giá mức độ phù hợp (độ tốt) của tập con được chọn lựa. Kết

quả trả về của hàm đánh giá sau đó được sử dụng để xác định thứ hạng của các tập

con đặc trưng được đánh giá.

Điều kiện dừng: được sử dụng để đảm bảo tiến trình rút gọn tập đặc trưng kết

thúc khi không thể tìm thấy tập con đặc trưng tốt hơn.

Kiểm chứng kết quả: kiểm tra kết quả với các thuật toán học được chọn nhằm

xác nhận hiệu năng của kỹ thuật lựa chọn đặc trưng.

1.2.5 Các mô hình lựa chọn đặc trưng

Tất cả đặc trưng

Filter

Tập con đặc trưng tốt nhất

Phân lớp

Tính toán xếp hạng theo các độ đo tương ứng

Mô hình Lọc (Filter)

Hình 1.4 Mô hình chọn lựa đặc trưng Lọc

Mô hình Lọc (Filter) là phương pháp lựa chọn đặc trưng đơn giản nhất (Hình

1.4). Đầu vào của mô hình là toàn bộ các đặc trưng của tập dữ liệu, sau khi thực hiện

việc đánh giá các đặc trưng sử dụng các độ đo hoặc các tiêu chí nhất định cho trước

thì đầu ra của mô hình là danh sách các đặc trưng với điểm số của từng đặc trưng.

Việc lựa chọn M đặc trưng có điểm số cao nhất (hoặc thấp nhất) sẽ cho tập con đặc

trưng tốt nhất theo một tiêu chí nhất định. Ưu nhược điểm của một số phương pháp

lọc được liệt kê trong Bảng 1.2

Bảng 1.2 Ưu nhược điểm của mô hình Lọc[8]

Ví dụ

Ưu điểm Đơn biến Đơn giản Nhanh, dễ mở rộng Không phụ thuộc vào bộ phân lớp

Nhược điểm Loại bỏ các đặc trưng có liên quan Kết quả phân lớp cuối cùng có độ chính xác không cao. X2 Khoảng cách Ơ clit t-test Độ lợi thông tin (IG) Gain ratio

Đa biến Độc lập với bộ phân lớp Độ phức tạp tính toán thấp Sử dụng cho bộ dữ liệu kích cỡ lớn Chậm hơn các kỹ thuật đơn biến Có thể không loại bỏ được các đặc trưng dư thừa

Lựa chọn đặc trưng dựa trên tương quan (CFS) Lựa chọn đặc trưng dựa trên tương quan nhanh (FCFS)

Mô hình Đóng gói (Wrapper)

Mô hình đóng gói tìm kiếm tập con các đặc trưng tốt bằng cách đánh giá chất

lượng của các tập đặc trưng. Việc đánh giá chất lượng thường sử dụng hiệu năng (độ

Wrapper

Tất cả đặc trưng

Tập con đặc trưng tốt nhất

Bộ sinh tập con

Tập con đặc trưng

Kết quả đánh giá

Thuật toán học

chính xác dự đoán hoặc phân lớp) của thuật toán học (Hình 1.5).

Hình 1.5 Mô hình chọn lựa đặc trưng đóng gói

Để đánh giá chất lượng của tập đặc trưng, chúng sử dụng phản hồi (feedback)

từ mô hình dự đoán. Sở dĩ mô hình này được gọi là đóng gói bởi nó luôn ‘bao quanh’

bộ phân lớp. Mô hình đóng gói có thể sử dụng các chiến lược tìm kiếm khác nhau

chẳng hạn như tìm kiếm tuần tự, hoặc ngẫu nhiên. Ưu nhược điểm của mô hình đóng

gói được mô tả trong Bảng 1.3

Bảng 1.3 Ưu nhược điểm của mô hình Đóng gói [8]

Ưu điểm Nhược điểm Ví dụ

Thuật toán lựa chọn tuần tự

Dễ bị quá khớp

Có tương tác với bộ phân lớp Lựa chọn tiến tuần tự (SFS) Thực hiện dễ dàng

Chi phí tính toán thấp Loại bỏ lùi tuần tự (SBE) Dễ gặp tối ưu địa phương

Beam Search

Thuật toán lựa chọn tiến hóa

Tìm được tập con tối ưu Tính toán phức tạp SA

Tương tác với bộ phân lớp Dễ bị quá khớp hơn GA

PSO

Hiệu năng cao hơn mô hình lọc ACO

Mô hình nhúng (Embedded)

Mô hình nhúng giúp cải tiến hiệu năng phân lớp và tăng tốc độ của quá trình

lựa chọn. Mô hình nhúng là sự tích hợp, nhúng kỹ thuật lựa chọn đặc trưng vào mô

hình học. Mô hình này kết hợp ưu điểm của mô hình Lọc và Đóng gói bằng cách sử

dụng đồng thời tiêu chí đánh giá độc lập và các thuật toán học để đánh giá tập con

các đặc trưng. Mô hình Lọc có thể cung cấp một chỉ dẫn thông minh cho mô hình

Đóng gói, chẳng hạn như: giảm không gian tìm kiếm, một điểm khởi đầu tốt, đường

tìm kiếm ngắn và thông minh hơn. Để thực hiện được mô hình Nhúng người phát

triển cần tìm hiểu cấu trúc của thuật toán học, xác định các tham số có thể sử dụng

cho việc đánh giá mức độ quan trọng của đặc trưng. Nói cách khác, các đặc trưng

được xếp hạng ngay trong quá trình thực thi của việc học, không phải sau khi việc

học hoàn thành như trong mô hình Đóng gói. Bảng 1.4 dưới đây so sánh ba mô hình

lựa chọn đặc trưng dựa theo ba hướng tiếp cận:

Bảng 1.4 So sánh ba mô hình[33]

Tiêu chuẩn

Mô hình Lọc Đo lường độ phù hợp đặc trưng/ tập con đặc trưng Thường là thứ tự của các đặc trưng Chiến lược tìm kiếm

kiểm kiểm Đánh giá

Ưu điểm

Đo lường tính có ích của tập con đặc trưng Tìm kiếm được hướng dẫn bởi quá trình học Sử dụng chứng chéo Chi phí tính toán thấp Sử dụng các kiểm định thống kê Nhanh, không phụ thuộc mô hình học

Mô hình Đóng gói Mô hình Nhúng Đo lường tính có ích của tập con đặc trưng Tìm kiếm không gian toàn bộ đặc trưng Sử dụng chứng chéo Có thể lựa chọn được các đặc trưng “tối ưu” nhất Dễ bị “quá khớp” Ít bị “quá khớp” Nhược điểm

Có thể không lựa chọn được các đặc trưng “hữu ích” nhất

1.3 Trích xuất đặc trưng

- Trích xuất đặc trưng (Feature extraction): biến đổi không gian đặc trưng ban

đầu sang một không gian khác mà có thể dễ dàng phân tích hơn. Hay nói cách

khác là nó xây dựng một tập đặc trưng mới từ tập đặc trưng ban đầu với số đặc

[

𝑡𝑟í𝑐ℎ 𝑥𝑢ấ𝑡 đặ𝑐 𝑡𝑟ư𝑛𝑔 → [

]

] = 𝑓 ([

])

trưng nhỏ hơn.

x1 x2 ⋮ xN

y1 y2 ⋮ yM

Hình 1.6 Trích xuất đặc trưng.

Trích xuất đặc trưng liên quan tới việc tạo ra tập đặc trưng “mới” từ tập đặc

trưng ban đầu, thông qua việc áp dụng một hàm hoặc một quá trình chuyển đổi. Trích

xuất đặc trưng thực hiện một số phép biến đổi từ đặc trưng ban đầu để tạo ra các đặc

trưng mới (tập đặc trưng đích) để có thể dễ dàng phân tích hơn.

1.3.1 Mục tiêu của trích xuất đặc trưng

- Tăng hiệu năng của thuật toán học do dữ liệu sau khi trích xuất có thể dễ dàng

phân tích hơn so với dữ liệu ban đầu.

- Trực quan hóa dữ liệu được thực hiện dễ dàng hơn do dữ liệu sau phép biến đổi

có thể dễ dàng biểu diễn hơn so với dữ liệu gốc

- Giảm nhiễu và dư thừa.

1.3.2 Phân loại các kỹ thuật trích xuất đặc trưng

Cách thức phân loại của các kỹ thuật trích xuất đặc trưng thường khác so với

cách phân loại của các kỹ thuật lựa chọn đặc trưng. Có nhiều cách phân loại dựa trên

các đặc điểm của kỹ thuật trích xuất. Trong khuôn khổ luận án này, chúng tôi tập

trung phân loại các kỹ thuật trích xuất đặc trưng thành hai loại là các phương pháp có

giám sát và các phương pháp không có giám sát. Ngoài ra, còn có thể phân loại theo

các mô hình tuyến tính và mô hình phi tuyến.

Các phương pháp không giám sát gồm: Phân tích thành phần chính (PCA),

Phân tích giá trị riêng (SVD), Phân tích yếu tố (FA)…

Các phương pháp có giám sát gồm: Phân tích biệt thức tuyến tính (LDA), Phân

tích thành phần độc lập (ICA)…

Các kỹ thuật không có giám sát

Phân tích thành phần chính

Phân tích thành phần chính (Principal Component Analysis-PCA) là kỹ thuật

rút gọn chiều được sử dụng rộng rãi trong các lĩnh vực như học máy, nén dữ liệu,

phân tích hình ảnh, nhận dạng mẫu, dự đoán thời gian thực và trực quan hóa dữ liệu.

Giả sử các phần tử dữ liệu được biểu diễn bằng vector n chiều, phương pháp phân

tích thành phần chính sẽ tìm k vector trực giao n chiều có thể dùng để biểu diễn dữ

liệu, với k ≤ n. Khi đó, phép chiếu trên không gian k chiều cho phép biểu diễn dữ liệu

ban đầu bằng một không gian nhỏ hơn. Phương pháp phân tích thành phần chính sẽ

kết hợp các đặc trưng ban đầu với nhau để tạo ra các đặc trưng mới. Các đặc trưng

mới được gọi là thành phần chính và chúng có số lượng ít hơn hoặc bằng các đặc

trưng ban đầu. PCA là một trong các kỹ thuật không có giám sát bởi dữ liệu ban đầu

không có sẵn thông tin về tin nhãn. PCA có thể sử dụng để trích xuất các thông tin

liên quan nhiều nhất từ một tập dữ liệu có chứa thông tin dư thừa hoặc nhiễu.

Phân tích giá trị riêng (SVD)

Phân tích giá trị riêng [6] của một ma trận X cỡ n×d được thực hiện bằng tích

của ba ma trận

𝐗 = 𝐔𝐒𝐕𝐓

(1.1)

Trong đó: 𝐔 là ma trận trực giao cỡ n×n

𝐒 là ma trận cỡ n×d

𝐕𝐓 là ma trận nghịch đảo của 𝐕

SVD thường được dùng để giảm chiều của ma trận bằng cách loại bỏ các cột

không tiêu biểu hoặc không quan trọng.

Phân tích yếu tố

Phân tích yếu tố (Factor Analysis-FA) cũng là một mô hình tuyến tính, nhưng

là mô hình xác suất chứa biến ẩn. FA được đề xuất lần đầu tiên bởi các nhà tâm lý.

FA giả sử rằng các biến được đo phụ thuộc vào một số yếu tố chung, không rõ và

thường không đo đạc được. Ví dụ điểm thi của sinh viên thường liên quan, phụ thuộc

vào yếu tố “thông minh” của mỗi sinh viên. Mục tiêu của FA là khai thác các mối

quan hệ như thế và có thể được sử dụng để giảm chiều của tập dữ liệu theo một mô

hình yếu tố. Phân tích yếu tố là mô hình dữ liệu có nhiều ưu điểm, cụ thể trong trường

hợp tập dữ liệu ban đầu có chiều cao, thì phân tích yếu tố cho phép mô hình hóa dữ

liệu trực tiếp bởi phân phối Gauss với ít tham biến hơn.

Các kỹ thuật có giám sát

Phân tích biệt thức tuyến tính

Phân tích biệt thức tuyến tính (Linear Discriminant Analysis-LDA) là một kỹ

thuật có giám sát; trong đó LDA tối đa hóa độ tin cậy tuyến tính giữa dữ liệu của các

lớp khác nhau. Tương tự như PCA, LDA tìm kiếm một kết hợp tuyến tính của các

đặc trưng để dựng hàm phân lớp của các đối tượng. LDA mô hình hóa sự khác biệt

giữa các lớp trong khi PCA không quan tâm tới những khác biệt này. LDA thường

được sử dụng với dạng dữ liệu có kiểu số.

Phân tích thành phần độc lập

Phân tích thành phần độc lập (Independent Component Analysis-ICA) là một

phương pháp biến đổi tuyến tính, trong đó các đại diện mong muốn là một trong các

thành phần phụ thuộc ít nhất vào các thành phần đại diện. Việc sử dụng các đặc trưng

trích xuất được phát triển theo lý thuyết về giảm sự dư thừa. Các thuật toán ICA được

chia thành hai loại: một là các thuật toán được phát triển từ việc giảm thiểu thông tin

tương hỗ; và loại thứ hai những thuật toán khác được phát triển từ việc tối đa hóa

phân phối chuẩn.

1.4 Một số nghiên cứu về rút gọn đặc trưng

1.4.1 Hướng nghiên cứu về lựa chọn đặc trưng

Trong nghiên cứu [53], các tác giả phân chia các hướng nghiên cứu thành bốn

nhóm là hướng nghiên cứu dựa trên sự tương quan, hướng nghiên cứu dựa trên thống

kê, hướng nghiên cứu dựa trên lý thuyết thông tin và hướng nghiên cứu dựa trên học

1.4.1.1 Hướng nghiên cứu dựa trên sự tương quan

thưa.

Các thuật toán lựa chọn đặc trưng khác nhau sử dụng các tiêu chí khác nhau

để xác định các đặc trưng liên quan. Một số độ đo được sử dụng để đánh giá mức độ

quan trọng của đặc trưng là điểm số Laplace (Laplacian Score), điểm số Fisher,

Relief-F…

Thuật toán cứu trợ (Relief-F) là một trong những thuật toán lựa chọn đặc trưng

phổ biến nhất do nó đơn giản và hoạt động hiệu quả. Tính chất của dữ liệu ảnh hưởng

tới việc thực hiện thuật toán cứu trợ. Cụ thể, nếu dữ liệu có nhiều nhiễu thì Relief-F

có thể cho kết quả kém chính xác. Nếu trong tập dữ liệu có giá trị ngoại lai (outlier)

thì độ chính xác sẽ giảm nhiều hơn nữa. Vì vậy, cần phải hết sức cẩn thận khi chọn

mẫu cho tập dữ liệu. Ngoài ra, Relief-F chỉ xếp hạng các đặc trưng dựa trên mức độ

quan trọng của từng đặc trưng. Do đó, trong nghiên cứu [102], các tác giả đã lai ghép

Relief-F với một thuật toán di truyền nhằm lựa chọn các đặc trưng tối ưu. Các tham

số của thuật toán di truyền được xác định một cách phù hợp dựa vào số đặc trưng

được lựa chọn từ Relief-F.

Nhận xét: Ưu điểm của các phương pháp lựa chọn đặc trưng dựa trên sự tương

quan là tương đối đơn giản và dễ hiểu bởi công việc tính toán chỉ tập trung vào xây

dựng ma trận tương quan sau đó tính điểm số cho từng đặc trưng. Do có hiệu suất cao

nên chúng thường được sử dụng cho các bài toán phân lớp. Các phương pháp này

cũng độc lớp với các thuật toán học khi lựa chọn các đặc trưng. Tuy nhiên, nhược

điểm của các phương pháp này là không thể xác định được các đặc trưng dư thừa bởi

chúng có thể lặp lại việc tìm kiếm các đặc trưng có độ tương quan cao trong suốt quá

1.4.1.2 Hướng nghiên cứu dựa trên thống kê

trình lựa chọn.

Các độ đo thống kê cũng được sử dụng để làm tiêu chuẩn lựa chọn đặc trưng.

Các phương pháp lựa chọn đặc trưng sử dụng độ đo thống kê được xếp vào nhóm các

phương pháp lọc do chúng không phụ thuộc vào thuật toán học mà chỉ đánh giá đặc

trưng dựa trên các độ đo thống kê. Các phương pháp này có thể không loại bỏ được

các đặc trưng dư thừa trong pha lựa chọn do chúng chỉ đánh giá các đặc trưng một

cách độc lập. Một số độ đo hay được sử dụng là: phương sai thấp (Low Variance),

điểm số T (T-score), điểm số F (F-score), X2, chỉ số Gini.

Nhận xét: Các phương pháp lựa chọn đặc trưng dựa trên thống kê sử dụng các

độ đo để loại bỏ các đặc trưng không mong muốn. Với ưu điểm đơn giản, dễ hiểu và

chi phí tính toán thấp, chúng thường được sử dụng trong bước tiền xử lý sau đó mới

áp dụng cho các phương pháp lựa chọn đặc trưng phức tạp khác. Giống như các

phương pháp lựa chọn đặc trưng dựa trên sự tương quan, các phương pháp này đánh

giá độ quan trọng của các đặc trưng một cách độc lập nên không thể loại bỏ được các

đặc trưng dư thừa. Một nhược điểm khác của các phương pháp này là chúng chỉ có

thể làm việc với dữ liệu rời rạc. Các biến kiểu số hay liên tục cần phải xử lý rời rạc

hóa trước khi được áp dụng.

1.4.1.3 Hướng nghiên cứu trên lý thuyết thông tin

Phần lớn các thuật toán lựa chọn đặc trưng hiện có là dựa trên lý thuyết thông

tin. Các thuật toán này sử dụng điều kiện lọc theo kinh nghiệm để đánh giá độ quan

trọng của đặc trưng. Hầu hết các thuật toán dựa trên khái niệm entropy để đo sự không

chắc chắn của một biến ngẫu nhiên rời rạc. Độ lợi thông tin (Information Gain) giữa

hai biến X và Y được sử dụng để đo lượng thông tin dùng chung của X và Y. Một số

thuật toán lựa chọn đặc trưng dựa trên lý thuyết thông tin:

- Độ lợi thông tin (Information Gain): đo sự quan trọng của đặc trưng bằng mối

tương quan của nó với nhãn lớp. Giả sử rằng một đặc trưng có độ tương quan

cao với nhãn lớp thì nó có thể giúp đạt hiệu suất phân lớp tốt. Công việc đánh

giá độ quan trọng của từng đặc trưng được thực hiện riêng biệt, do đó nó có thể

bỏ qua các đặc trưng dư thừa. Sau khi có được điểm số của các đặc trưng, có

thể lựa chọn ra các đặc trưng có điểm số cao nhất.

- Lựa chọn đặc trưng dựa trên thông tin tương hỗ (Mutual Information): nhược

điểm của phương pháp độ lợi thông tin là việc giả thiết các đặc trưng là độc lập

với nhau. Trong thực tế, một đặc trưng được gọi là tốt nếu nó liên quan cao với

nhãn lớp và không liên quan tới các đặc trưng khác. Nói cách khác cần làm

giảm mối liên quan giữa các đặc trưng. Phương pháp này xem xét cả các đặc

trưng liên quan và các đặc trưng dư thừa trong pha lựa chọn đặc trưng.

- Liên quan nhiều nhất-dư thừa ít nhất (Minimum Redundancy Maximum

Relevance-mRMR): Peng và cộng sự [76] đề xuất điều kiện liên quan nhiều

nhất- dư thừa ít nhất để lựa chọn số đặc trưng cần chọn. Thuật toán giúp cho

việc lựa chọn càng nhiều đặc trưng, ảnh hưởng của các đặc trưng dư thừa càng

giảm.

- Thông tin tương hỗ chung (Joint Mutual Information): Meyer và cộng sự [64]

đề xuất điều kiện thông tin tương hỗ chung nhằm tăng cường thông tin bổ sung

được chia sẻ giữa các đặc trưng chưa được chọn và đặc trưng đã được chọn.

Nhận xét: khác với các phương pháp lựa chọn đặc trưng dựa trên sự tương

quan, hầu hết các phương pháp lựa chọn đặc trưng dựa trên lý thuyết thông tin có thể

xác định được các đặc trưng liên quan và các đặc trưng dư thừa. Cũng giống như các

phương pháp dựa trên sự tương quan, các phương pháp dựa trên lý thuyết thông tin

là độc lập với thuật toán học. Do đó, các phương pháp này thường chỉ phù hợp với

bài toán phân lớp. Do không có sự hướng dẫn của nhãn lớp nên không thể xác định

rõ ràng việc đánh giá mức quan trọng của các đặc trưng. Ngoài ra, các phương pháp

này chỉ có thể áp dụng cho dữ liệu rời rạc do đó các biến số liên tục cần phải được xử

1.4.1.4 Hướng nghiên cứu dựa trên học thưa (Sparse learning)

lý rời rạc hóa.

Trong những năm gần đây, các phương pháp lựa chọn đặc trưng dựa trên học

thưa đã được nhiều nhà nghiên cứu quan tâm do hiệu suất tốt và dễ hiểu. Hướng

nghiên cứu dựa trên học thưa có mục tiêu là giảm thiểu lỗi với một số qui tắc thưa.

Các qui tắc thưa làm cho các hệ số của đặc trưng thu nhỏ dần (hoặc chính xác bằng

0) và sau đó các đặc trưng tương ứng có thể được loại bỏ một cách dễ dàng. Một số

phương pháp lựa chọn đặc trưng dựa trên học thưa:

Lựa chọn đặc trưng với qui tắc chuẩn ℓ𝑝: phương pháp này được áp dụng cho

bài toán phân lớp nhị phân hoặc hồi qui đa biến. Để lựa chọn đặc trưng điều kiện giới

hạn thưa ℓ𝑝𝑛𝑜𝑟𝑚 được đưa vào mô hình, trong đó 0 ≤ 𝑝 ≤ 1. Có thể lựa chọn đặc

trưng bằng cách lựa chọn các đặc trưng có trọng số lớn. Thông thường trọng số càng

cao thì độ quan trọng của đặc trưng càng lớn. Các phương pháp lựa chọn đặc trưng

theo ℓ1-norm gồm có [98][96][36].

Lựa chọn đặc trưng với qui tắc chuẩn ℓ𝑝,𝑞 : phương pháp này được áp dụng

cho bài toán phân lớp đa nhãn hoặc hồi qui đa biến. Các bài toán này tương đối khó

hơn do có đa nhãn và đa mục tiêu và pha lựa chọn đặc trưng phải là nhất quán trên

nhiều mục tiêu. Việc lựa chọn đặc trưng liên quan được chuyển thành việc giải bài

toán tối ưu. Đề giải bài toán này một số tác giả đã tìm kiếm giải pháp tối ưu địa

phương[16].

Ngoài ra, nhiều tác giả đã nghiên cứu và đề xuất các phương pháp lựa chọn

đặc trưng hiệu quả dựa trên học thưa [24][43][74][75].

Nhận xét: Các phương pháp lựa chọn đặc trưng dựa trên học thưa có thể được

nhúng vào một thuật toán học bất kỳ (chẳng hạn hồi qui tuyến tính, SVM, Random

Forest..). Do đó, có thể cải thiện hiệu năng của các thuật toán học. Ngoài ra, với đặc

tính thưa của trọng số của đặc trưng, mô hình trở nên dễ hiểu, dễ giải thích. Tuy nhiên,

các phương pháp này vẫn còn gặp phải một số hạn chế. Thứ nhất, nó tối ưu hóa trực

tiếp một thuật toán học bằng việc lựa chọn đặc trưng, do đó các đặc trưng được lựa

chọn chỉ phù hợp với thuật toán học này mà không phù hợp với thuật toán học khác.

Có nghĩa là không tổng quát. Thứ hai, các phương pháp này liên quan tới việc giải

bài toán tối ưu với các phép toán phức tạp trên ma trận (nhân, đảo ngược,..) trong hầu

hết các trường hợp. Do đó, chi phí tính toán cao là một trong những hạn chế của các

1.4.1.5 Một số hướng nghiên cứu khác:

phương pháp này.

Ngoài các phương pháp lựa chọn đặc trưng thuộc bốn nhóm đã trình bày ở

trên, các nhà nghiên cứu còn tập trung vào phát triển các phương pháp lựa chọn đặc

trưng theo chiến lược tìm kiếm và tiêu chí đánh giá.

Tìm kiếm kinh nghiệm và tham lam

Nakariyakul và Casasent [66] cải tiến thuật toán lựa chọn đặc trưng tuần tự

tiến nhằm chọn một tập hợp con của các đặc trưng. Các tác giả đã đề xuất cải tiến các

thuật toán lựa chọn đặc trưng gốc bằng cách thêm một bước tìm kiếm bổ sung được

gọi là "thay thế đặc trưng yếu". Bước tìm kiếm bổ sung này sẽ thực hiện việc loại bỏ

một đặc trưng bất kỳ trong tập các đặc trưng con hiện đang được chọn. Sau đó thêm

tuần tự từng đặc trưng mới nhằm cải thiện các tập con đặc trưng hiện thời.

Yusta [101] trình bày ba chiến lược tìm kiếm theo kinh nghiệm để giải quyết

các bài toán lựa chọn đặc trưng (GRASP, tìm kiếm Tabu và thuật toán Memetic). Ba

chiến lược tìm kiếm này được so sánh với giải thuật di truyền và với các phương pháp

lựa chọn đặc trưng điển hình khác như SFFS và SBFS. Kết quả cho thấy GRASP và

tìm kiếm Tabu có được kết quả tốt hơn so với các phương pháp còn lại.

Tìm kiếm dựa trên tối ưu

Khi bài toán lựa chọn đặc trưng có thể được coi là một bài toán tối ưu hóa tổ

hợp, các nhà nghiên cứu đã sử dụng các thuật toán di truyền, tối ưu đàn kiến, phương

pháp tập thô và tối ưu hóa bầy đàn (Particle Swarm Optimization) để giải quyết.

Một thủ tục tìm kiếm khác dựa trên các thuật toán di truyền (GA), đó là một

kỹ thuật tìm kiếm tổ hợp dựa trên cả hai độ đo ngẫu nhiên và xác suất. Các tập con

đặc trưng được đánh giá bằng cách sử dụng hàm phù hợp và sau đó qua kết hợp trao

đổi chéo và đột biến để tạo ra thế hệ tiếp theo của các tập con.

Othman Soufan và các cộng sự [82] đề xuất một phương pháp lựa chọn đặc

trưng hiệu quả theo mô hình đóng gói trong đó sử dụng chiến lược tìm kiếm dựa trên

thuật toán di truyền. Việc kiểm tra và đánh giá số lượng lớn các đặc trưng được triển

khai song. Trong bước tiền xử lý các tác giả cũng tích hợp các phương pháp lọc khác

nhau. Một ưu điểm nổi bật của phương pháp này là trọng số và các tham số khác của

GA có thể điểu chỉnh đề phù hợp các ứng dụng khác nhau.

Các phương pháp lựa chọn đặc trưng sử dụng thuật toán di truyền thường gặp

khó khăn khi số lượng đặc trưng lớn.

Tối ưu hóa bầy đàn (Particle Swarm Optimization-PSO) là một kỹ thuật tối ưu

hóa ngẫu nhiên dựa vào dân số được phát triển bởi Kennedy và Eberhart [48]. PSO

mô hình hóa việc đàn chim bay đi tìm kiếm thức ăn cho nên nó thường được xếp vào

các loại thuật toán có sử dụng trí tuệ bầy đàn. Bae và cộng sự [9] đề xuất một thuật

toán tiến hóa được gọi là bầy đàn thông minh động dựa trên biến đổi của thuật toán

PSO. Một phương pháp lựa chọn đặc trưng lai giữa GA và PSO được Pedram Ghamisi

và cộng sự [30] đề xuất nhằm phán đoán điểm ảnh trong quá trình xử lý ảnh. Thuật

toán lai này tự động dừng khi giá trị trung bình của cá thể nhỏ hơn một giá trị ngưỡng

cho trước. Ưu điểm của phương pháp này là không cần phải thiết lập số lượng đặc

trưng cần thiết trước khi bắt đầu các vòng lặp.

Trong nghiên cứu của Martin Jung và Zscheischler Jakob [46], các tác giả giới

thiệu một thuật toán di truyền lai cho việc lựa chọn đặc trưng. Thuật toán di truyền

được chỉ dẫn bởi Rừng ngẫu nhiên (RF) giúp làm giảm chi phí tính toán của hàm mục

tiêu. Hướng dẫn này gợi ý những đặc trưng sẽ bị loại bỏ và giữ lại những đặc trưng

phù hợp nhất.

Gần đây, Ghaemi Manizheh và cộng sự đề xuất một phương pháp lựa chọn

đặc trưng sử dụng thuật toán tối ưu rừng (FOA)[29]. Đầu tiên, thuật toán tối ưu rừng

được áp dụng cho bài toán có không gian liên tục, sau đó nó được áp dụng cho bài

toán có không gian đặc trưng rời rạc bằng cách thiết lập lại bậc của cây tốt nhất về

giá trị không.

Maldonado và Weber [63] giới thiệu một thuật toán đóng gói để lựa chọn đặc

trưng, trong đó sử dụng SVM với các hàm nhân. Phương pháp của họ được dựa trên

sự lựa chọn tuần tự ngược, bằng cách sử dụng số lỗi đánh giá trên một tập con làm

độ đo để quyết định đặc trưng nào bị loại bỏ trong mỗi lần lặp.

Kỹ thuật lai

Các kỹ thuật lai là một dạng của các phương pháp dựa trên kết hợp mô hình

(ensemble) với mục đích tạo ra một nhóm các tập con đặc trưng từ các thuật toán lựa

chọn đặc trưng khác nhau và sau đó tổng hợp lấy ra kết quả cuối cùng tốt nhất. Kỹ

thuật này có thể làm giảm thiểu vấn đề không ổn định, nhiễu của từng phương pháp

lựa chọn đặc trưng, và do đó các công việc học tiếp sau được cải thiện đáng kể. Tương

tự như các phương pháp học kết hợp thông thường, các phương pháp lựa chọn đặc

trưng lai gồm hai bước: (1) Xây dựng một tập các kết quả lựa chọn đặc trưng khác

nhau, (2) Kết hợp các kết quả này để có được kết quả cuối cùng. Việc thực hiện các

bước khác nhau sẽ cho ra các phương pháp lựa chọn đặc trưng khác nhau.

Unler và cộng sự [89] trình bày một thuật toán lựa chọn tập con đặc trưng lai

giữa lọc và đóng gói dựa trên tối ưu hóa hạt bầy đàn (PSO) cho bộ phân lớp SVM.

Mô hình lọc dựa trên các thông tin tương hỗ (MI), MI là một độ đo tổng hợp của đặc

trưng liên quan và dư thừa đối với các tập con đặc trưng được lựa chọn. Mô hình

đóng gói là một thuật toán cải tiến dựa trên PSO.

Cách tiếp cận của Peng và cộng sự [77] gồm hai phần: (1) thêm một bước tiền

lựa chọn để nâng cao hiệu quả trong việc tìm kiếm các tập con đặc trưng với hiệu

năng phân lớp được cải tiến, (2) sử dụng đường cong (ROC) để mô tả hiệu suất của

đặc trưng riêng lẻ và tập con đặc trưng trong việc phân lớp.

Lee và Leu [50] đề xuất một phương pháp lai mới để lựa chọn đặc trưng trong

việc phân tích dữ liệu microarray. Phương pháp này lần đầu tiên sử dụng thuật toán

di truyền với cài đặt tham số động (GADP) để tạo ra một số tập hợp gen và để xếp

hạng các gen theo tần số xuất hiện của chúng trong các tập con gen. Sau đó, sử dụng

phương pháp X2 để chọn một số gen thích hợp trong số các gen được xếp hạng cao

nhất.

Xie và Wang [97] đề xuất một phương pháp lựa chọn đặc trưng lai, cải tiến F-

score và tìm kiếm kế tiếp tuần tự (IFSFS). Họ cải tiến F-score gốc bằng cách đo độ

phân biệt giữa hai bộ số thực sau đó đo sự phân biệt giữa nhiều hơn hai bộ số thực.

Các cải tiến F-score và tìm kiếm kế tiếp tuần tự (SFS) được kết hợp để tìm tập con

tối ưu trong quá trình lựa chọn đặc trưng, trong đó, cải tiến F-score được dùng như là

một tiêu chí đánh giá của phương pháp lọc còn SFS là một hệ thống đánh giá dựa trên

phương pháp đóng gói.

Các phương pháp tập thô

Lý thuyết tập thô (Rough Set) đã được giới thiệu bởi Pawlak [73] để giải quyết

với các khái niệm không chính xác hoặc mơ hồ. Swiniarski và Skowron [85] giới

thiệu các ứng dụng cho phép sử dụng phương pháp tập thô để lựa chọn đặc trưng.

Chen và cộng sự [18] đề xuất một phương pháp lựa chọn đặc trưng dựa trên

bit để tìm tập đặc trưng nhỏ nhất đại diện cho các chỉ số của một tập dữ liệu cho trước.

Cách tiếp cận này bắt nguồn từ việc lập chỉ mục bitmap và kỹ thuật tập thô. Nó bao

gồm hai giai đoạn. Trong giai đoạn đầu, tập dữ liệu đã cho được biến đổi thành một

ma trận bitmap được lập chỉ mục với một số thông tin dữ liệu bổ sung. Trong giai

đoạn thứ hai, một tập hợp các đặc trưng phù hợp được lựa chọn và sử dụng đại diện

cho các chỉ số phân lớp của tập dữ liệu cho trước. Sau khi các đặc trưng phù hợp được

lựa chọn, chúng có thể được đánh giá bởi các chuyên gia trước khi tập các đặc trưng

cuối cùng của dữ liệu được đề xuất.

Lựa chọn đặc trưng là một chủ đề khá quan trọng trong nghiên cứu ứng dụng

lý thuyết tập thô. Tuy nhiên, nhiều phương pháp lựa chọn đặc trưng dựa trên lý thuyết

tập thô không có khả năng xử lý dữ liệu quy mô lớn. Trong [44], Jiao và cộng sự giới

hai phương pháp lựa chọn đặc trưng dựa trên các nguyên tắc phân rã và tích hợp. Ý

tưởng chính là phân rã một bảng phức tạp thành một số bảng phụ đơn giản, dễ quản

lý và nhiều khả năng giải quyết hơn bằng cách sử dụng phương pháp qui nạp, sau đó

tích hợp chúng lại với nhau để giải quyết các bảng gốc.

Học sâu (Deep learning) so với lựa chọn đặc trưng

Gần đây, các kỹ thuật học sâu ngày càng phổ biến và thành công trong nhiều

ứng dụng trong thế giới thực. Học sâu tương đối khác so với lựa chọn đặc trưng bởi

sức mạnh của học sâu là ở việc tập trung vào các kiến trúc mạng nơ-ron sâu nhằm

học các đặc trưng đại diện mới trong khi đó lựa chọn đặc trưng trực tiếp tìm ra các

đặc trưng liên quan từ những đặc trưng ban đầu. Từ cách nhìn này có thể thấy kết quả

của lựa chọn đặc trưng là dễ đọc và dễ hiểu hơn. Mặc dù học sâu được sử dụng chủ

yếu cho việc học đặc trưng, tuy nhiên cũng có nhiều nhà nghiên cứu sử dụng học sâu

cho bài toán lựa chọn đặc trưng. Li và cộng sự [54] đề xuất một phương pháp lựa

chọn đặc trưng sâu (DFS), trong đó việc lựa chọn các đặc trưng được thực hiện ở mức

đầu vào của một mạng nơ-ron sâu. Để có thể lựa chọn đặc trưng, DFS áp đặt qui tắc

thưa và lựa chọn các đặc trưng có trọng số là lớn hơn 0. Tương tự, Roy và cộng sự

[79] cũng đề xuất một thuật toán lựa chọn đặc trưng ở mức đầu vào của mạng nơ-ron

sâu, chỉ khác ở chỗ các tác giả đề xuất một khái niệm mới để đánh giá các đặc trưng

ở pha phân lớp. Zhao và cộng sự [104] đề xuất việc kết hợp một mạng nơ-ron sâu với

đại diện thưa cho việc lựa chọn đặc trưng. Đầu tiên, phương pháp này trích xuất một

đại diện mới từ từng nhóm các đặc trưng bằng cách sử dụng mạng nơ-ron đa mô hình.

Sau đó, độ quan trọng của đặc trưng được học bởi một phương pháp học thưa.

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

Hướng nghiên cứu dựa trên lý thuyết thống kê

Phương pháp dựa trên lý thuyết phân tích thống kê là phương pháp thường

được sử dụng trong trích xuất đặc trưng. Các phương pháp thống kê có thể phân tích

và xử lý dữ liệu một cách hiệu quả. Chẳng hạn, một số phương pháp cổ điển như phân

tích thành phần chính (PCA), phân tích biệt thức tuyến tính (LDA), phân tích yếu tố

(FA).

Phương pháp trích xuất đặc trưng phổ biến nhất và sử dụng rộng rãi là phân

tích thành phần chính (PCA) được giới thiệu bởi Karl. PCA là một biến đổi tuyến tính

của dữ liệu nhằm giảm thiểu sự dư thừa (đo lường thông qua hiệp phương sai) và tối

đa hóa thông tin (được đo thông qua các phương sai). Zhang và cộng sự [103] đề xuất

một thuật toán cho phân lớp đa nhãn, trong đó tích hợp quá trình trích xuất đặc trưng

dựa trên PCA. Đầu tiên, quá trình trích xuất đặc trưng được thực thi dựa trên phân

tích thành phần chính để loại bỏ các đặc trưng không liên quan. Tiếp đó, tiến hành

quá trình lựa chọn đặc trưng dựa trên thuật toán sinh để lựa chọn những tập con các

đặc trưng có ích nhất theo nghĩa làm tối ưu hàm rủi ro khoảng cách và rủi ro xếp

hạng.

Phân tích thành phần độc lập (ICA) [81] là một phương pháp thống kê dùng

để chuyển đổi một véc tơ đa chiều sang các thành phần độc lập. Bằng cách đó, nó cho

phép loại bỏ dư thừa từ dữ liệu. Karhunen cùng cộng sự [47] đã sử dụng nguyên lý

của ICA để trích xuất đặc trưng mẫu.

Park và Lee [72] mở rộng phân tích biệt thức tuyến tính (LDA) được sử dụng

trong phân lớp đơn nhãn nhằm giảm chiều trong phân lớp đa nhãn.

Wang và cộng sự đề xuất kỹ thuật trích xuất đặc trưng – phân tích biệt thức

tuyến tính cân bằng. Ý tưởng của mô hình là định nghĩa một ma trận phân bố trong

lớp và một ma trận phân bố đa lớp cho học đa nhãn. Vì mỗi thể hiện có thể quan hệ

với nhiều lớp nên ma trận phân bố trong lớp và đa lớp được biến đổi cho phù hợp.

Mô hình đề xuất LDA cân bằng lớp này tương đương với LDA truyền thống thực thi

trên tập dữ liệu sau khi biến đổi bản sao.

Ngoài ra, phương pháp trích xuất đặc trưng dựa trên phân tích ma trận giá trị

đơn (Matrix Singular Value Decomposition), phương pháp phân tích biệt thức không

tương quan thống kê (Statistical Uncorrelated Discriminant Analysis) là các phương

pháp toán học cổ điển.

Hướng nghiên cứu dựa trên hàm nhân

Hàm nhân được sử dụng để chuyển đổi dữ liệu từ không gian phi tuyến ban

đầu sang không gian đặc trưng tuyến tính. Các phương pháp sử dụng hàm nhân nhằm

phát triển một hướng tiếp cận mới để giải quyết các bài toán phi tuyến, và từ đó có

thể áp dụng các thuật toán phân tích dữ liệu tuyến tính. Các hàm nhân được dùng phổ

biến hiện nay là hàm đa thức, hàm đa thức thứ tự p, hàm Gaussian Radial Basis

Function (RBF).

Phân tích thành phần chính dựa trên hàm nhân (KPCA) [99] với ý tưởng chính

là ánh xạ từ dữ liệu đầu vào sang một không gian đặc trưng thông qua một ánh xạ phi

tuyến. Zhou [105] chỉ ra một cách tiếp cận để phân tích thành phần chính dựa trên

hàm nhân theo phương pháp xác suất gọi là phân tích thành phần chính dựa trên hàm

nhân xác suất (PKPCA); nhằm kết hợp một cách tự nhiên giữa PPCA và KPCA để

khắc phục những hạn chế của PCA.

Phân tích khác biệt Fisher dựa trên hàm nhân(Kernel FDA)[80], phân tích khác

biệt tương quan tiêu chuẩn (KCCDA) cũng là các phương pháp điển hình dựa trên

hàm nhân.

Hướng nghiên cứu dựa trên kiến trúc mạng nơ-ron

Các phương pháp mạng nơ-ron và gần đây là học sâu (Deep learning) là các

phương pháp phi tuyến phổ biến. Năm 2006 Hilton và cộng sự áp dụng thành công

mạng nơ-ron trong việc giảm chiều dữ liệu và đưa ra khái niệm học sâu “deep

learning”.

Hiện nay, các kỹ thuật học sâu đang được áp dụng cho nhiều ứng dụng trong

thực tế do có hiệu quả cao. Nghiên cứu về mạng nơ-ron đã được thực hiện từ nhiều

thâp năm trước đây và đạt được nhiều thành công. Mặc dù các thuật toán học sâu đạt

được nhiều thành tựu đáng kể nhưng, nó chỉ phù hợp với một số bài toán cụ thể, mà

không thể thay thế được quá rút gọn đặc trưng trong mọi trường hợp. Rút gọn đặc

trưng vẫn là chủ đề được quan tâm trong nhiều lĩnh vực.

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

Cho một tập hợp các đặc trưng đầu vào, việc rút gọn đặc trưng có thể được

thực hiện theo hai hướng tiếp cận khác nhau. Hướng tiếp cận đầu tiên là lựa chọn ra

một tập con các đặc trưng tốt nhất từ tập đặc trưng đầu vào. Quá trình này được gọi

là lựa chọn đặc trưng. Hướng tiếp cận thứ hai là tạo ra các đặc trưng mới dựa trên

việc chuyển đổi các đặc trưng ban đầu sang một không gian có chiều thấp hơn và quá

trình này được gọi là trích xuất đặc trưng. Sự chuyển đổi này có thể là một sự kết hợp

tuyến tính hoặc phi tuyến của các đặc trưng ban đầu. Việc sử dụng kỹ thuật lựa chọn

đặc trưng hay trích xuất đặc trưng phụ thuộc vào miền ứng dụng và dữ liệu hiện có.

Về thủ tục tìm kiếm đặc trưng, số lượng các tập con có thể được tạo ra từ tập

đặc trưng ban đầu là cấp số mũ. Trong hầu hết các trường hợp, khó có thể để kiểm

tra tất cả các tập con có thể được tạo ra này, ngay cả khi việc ước lượng hay tính toán

các tiêu chí đánh giá là đơn giản.

Độ đo khoảng cách là một độ đo cơ bản và được sử dụng rộng rãi. Các độ đo

phụ thuộc, cũng được gọi là độ đo tương quan, chủ yếu được sử dụng để tìm ra mối

tương quan giữa hai đặc trưng hoặc một đặc trưng và một lớp. Các độ đo nhất quán

chủ yếu dựa trên tập dữ liệu huấn luyện và được dùng để lựa chọn đặc trưng. Các độ

đo đều nhạy cảm với các giá trị cụ thể của dữ liệu huấn luyện. Vì vậy, dữ liệu nhiễu

hoặc ngoại lai có thể gây tác động tới các độ đo này. Trong khi đó, các độ đo thông

tin xác định số lượng thông tin hoặc sự không chắc chắn của một đặc trưng để phân

lớp. Quá trình phân lớp dữ liệu nhằm mục đích làm giảm số lượng thông tin không

chắc chắn hoặc thu thập thông tin về sự phân lớp.

Các nghiên cứu trong [41] so sánh một số phương pháp lựa chọn đặc trưng cơ

bản trong các bộ dữ liệu có đến hàng ngàn đặc trưng, sử dụng cả dữ liệu tổng hợp dựa

trên mô hình và dữ liệu thực tế. Trong quy trình này, họ đánh giá hiệu năng của các

thuật toán lựa chọn đặc trưng cho các mô hình và bộ phân lớp khác nhau. Mặc dù kết

quả cho thấy rõ ràng rằng không phương pháp nào trong số các phương pháp đặc

trưng lựa chọn được coi là thực hiện tốt nhất trong tất cả các tình huống. Các phương

pháp lọc có hiệu năng tốt hơn hoặc tương tự với phương pháp đóng gói cho một số

bài toán có số mẫu nhỏ. Các phương pháp đóng gói có hiệu năng tốt hơn khi số lượng

mẫu huấn luyện đủ lớn. Phương pháp rút gọn đặc trưng cũng có thể làm mất thông

tin của tập đặc trưng ban đầu. Do đó, không có phương pháp rút gọn đặc trưng nào là

tốt nhất cho mọi bài toán.

Lựa chọn đặc trưng có ưu điểm là tiết kiệm chi phí tính toán. Kết quả của quá

trình là một số đặc trưng không phù hợp được loại bỏ trong khi các đặc trưng được

lựa chọn có khả năng giữ lại đặc tính của dữ liệu gốc. Trích xuất đặc trưng có thể

cung cấp một khả năng phân tích hoặc trực quan hóa dữ liệu tốt hơn do dữ liệu gốc

được chuyển đổi sang không gian đặc trưng mới. Tuy nhiên tập đặc trưng được sinh

ra sẽ không giữ được tính chất nguyên gốc của dữ liệu ban đầu.

1.5 Kết luận chương

Chương này của luận án tập trung vào giới thiệu tổng quan về lĩnh vực rút gọn

đặc trưng. Phần đầu tập trung vào trình bày các kiến thức cơ sở về bài toán lựa chọn

đặc trưng và trích xuất đặc trưng. Phần còn lại của chương giới thiệu một số hướng

nghiên cứu về rút gọn đặc trưng tiêu biểu hiện nay. Đây là những cơ sở lý thuyết giúp

ích cho định hướng nghiên cứu và xây dựng các mô hình sẽ được trình bày ở chương

tiếp theo. Tùy thuộc vào bài toán và dữ liệu của bài toán, có thể lựa chọn kỹ thuật rút

gọn đặc trưng phù hợp để đạt được mục tiêu cải tiến hiệu năng của các thuật toán

phân lớp. Các kiến thức giới thiệu trong chương này sẽ được áp dụng để giải quyết

các bài toán với miền dữ liệu cụ thể trong các chương tiếp theo của luận án.

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

Trong chương này, chúng tôi đề xuất phương pháp lựa chọn đặc trưng dựa vào

hướng tìm kiếm tiến và tìm kiếm lùi được trình bày trong chương 1, chúng tôi đề xuất

hai hướng tiếp cận, cụ thể như sau:

Hướng thứ nhất là lựa chọn đặc trưng theo hướng tìm kiếm tiến, trong đó việc

thêm đặc trưng tốt nhất được thực hiện bằng cách sử dụng các luật lựa chọn đặc trưng

có tiêu chí xếp hạng cao nhất. Các kết quả nghiên cứu này đã được công bố tại tạp

chí khoa học công nghệ quốc tế (Công trình khoa học SANGHV1).

Hướng thứ hai là lựa chọn đặc trưng theo hướng tìm kiếm quay lui có tên là

FRFE (Fast Recursive Feature Elimination) dựa trên việc loại bỏ đặc trưng đệ quy

kết hợp với rừng ngẫu nhiên. Tập các đặc trưng được thu gọn dựa vào tiêu chí xếp

hạng đặc trưng đề xuất. Tiêu chí này được kết hợp từ độ quan trọng của từng đặc

trưng, mối liên quan giữa độ chính xác huấn luyện, kiểm tra và độ đo AUC. Kết quả

thực nghiệm của phương pháp đề xuất trên các bộ dữ liệu tín dụng đã cho kết quả tốt

hơn so với một số phương pháp truyền thống. Các kết quả nghiên cứu này đã được

công bố tại kỉ yếu của hội thảo quốc tế (Công trình SANGHV5).

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

Các ngân hàng thương mại thường sử dụng hệ thống cho điểm tín dụng (xếp

hạng khách hàng) để đánh giá xem một khách hàng có khả năng trả nợ hay không.

Đánh giá rủi ro tín dụng dựa trên việc xác định khả năng trả lãi và gốc khi đến hạn.

Mức độ rủi ro tín dụng phụ thuộc vào từng khách hàng, doanh nghiệp, trong đó mức

độ rủi ro thường được đánh giá bằng các thang điểm dựa vào thông tin tài chính, phi

tài chính đã có. Dựa trên nhóm khách hàng, mô hình cho điểm tín dụng thường được

chia thành hai loại. Với nhóm khách hàng là doanh nghiệp, thì áp dụng mô hình xếp

hạng tín dụng (credit rate). Mô hình này thường đánh giá mức độ tín dụng bằng các

thang điểm như AAA, AA, BBB,…CC của Moody hay Standard & Poor. Với nhóm

khách hàng là cá nhân và hộ gia đình thì áp dụng mô hình cho điểm tín dụng (credit

scoring); mô hình này thường đơn giản hơn bởi nó chỉ cần dựa vào các thông tin của

khách hàng trong quá khứ và hiện tại để đưa ra quyết định có cho vay không. Hai mô

hình này, hỗ trợ cán bộ tín dụng nhanh chóng ra quyết định đồng thời giám sát và

đánh giá mức tín dụng của khách hàng. Chúng còn cho phép dự đoán, dự báo những

khoản vay có chất lượng không tốt (nợ xấu).

Cho điểm tín dụng là phương pháp đo lường rủi ro gắn với một khách hàng

bằng cách phân tích dữ liệu của họ để dự báo khả năng trả nợ [4]. Các mô hình cho

điểm tín dụng được xây dựng dựa trên việc sử dụng dữ liệu đã có của khách hàng.

Chúng có khả năng thể hiện được mối quan hệ giữa các thông tin đã có để dự đoán

khả năng tín dụng trong tương lai. Mối quan hệ này có thể được mô tả bởi hàm f như

(2.1)

𝑓(𝑥1, 𝑥2, . . , 𝑥𝑛) = 𝑦

Trong đó, 𝑥1, 𝑥2, . . , 𝑥𝑛 là các đặc trưng thông tin đầu vào của mỗi khách hàng.

y là mức độ tín dụng của khách hàng, với hai mức tín dụng là tốt hoặc xấu. Nhiệm vụ

của mô hình cho điểm tín dụng là dự đoán giá trị mức độ tín dụng y từ tập thông tin

đầu vào thông qua hàm f.

Lý do lựa chọn đặc trưng cho bài toán cho điểm tín dụng

Trong những năm gần đây các tổ chức tín dụng cũng như các ngân hàng bán

lẻ rơi vào tình trạng nguy hiểm do đã không quan tâm sát đáng tới quản trị rủi ro tài

chính. Trong các loại của rủi ro tài chính thì rủi ro tín dụng là hết sức quan trọng.

Việc quyết định cấp tín dụng là một chủ đề nóng và đã được nghiên cứu rộng rãi trong

lĩnh vực tài chính-ngân hàng. Tập hợp các mô hình, phương pháp hỗ trợ cho việc cấp

tín dụng được gọi là cho điểm tín dụng (Credit scoring).

Việc đánh giá mức độ tín nhiệm của khách hàng theo cách truyền thống gây

tốn kém về cả thời gian và nguồn lực. Ngoài ra, các phương pháp này thường dựa vào

ý chủ quan của các nhân viên tín dụng ngân hàng. Đó là lý do tại sao việc xây dựng

và áp dụng các mô hình tính toán có sự hỗ trợ của máy tính được đưa vào lĩnh vực

cho điểm tín dụng. Các mô hình này có thể loại bỏ các nhân tố chủ quan trong quá

trình cho điểm, đồng thời khuyến nghị cho ngân hàng có cho vay hay không hoặc khả

năng liên quan tới việc hoàn trả tiền vay trong trường hợp đã thực hiện giao dịch vay

tiền.

Chiến lược chung trong việc cho điểm tín dụng là sử dụng lịch sử tín dụng của

khách hàng trước đây để tính toán rủi ro của những người nộp đơn vay mới [88]. Các

thông tin lịch sử được thu thập để xây dựng mô hình cho điểm tín dụng. Mô hình này

có thể được sử dụng để xác định mối liên quan giữa đặc điểm của người nộp đơn và

độ tốt xấu. Nói chung, dữ liệu tài chính được sử dụng cho việc cho điểm tín dụng là

khá lớn. Dữ liệu này có đặc điểm chứa nhiều nhiễu, nhiều giá trị bị thiếu (trong quá

trình thu thập) gây ra bởi các đặc trưng dư thừa hoặc không liên quan và phân bố hết

sức phức tạp [78]. Số lượng các đặc trưng và số mẫu được gọi là kích thước của dữ

liệu. Dữ liệu của bài toán cho điểm tín dụng có số đặc trưng không thực sự nhiều

nhưng nó có số lượng mẫu tương đối lớn (khoảng vài nghìn tới vài chục nghìn). Trong

thực tế, mỗi ngày số lượng các đặc trưng không tăng đáng kể nhưng số mẫu tăng lên

khá nhiều. Điều này đòi hỏi phải tính toán nhiều hơn, độ chính xác và tính dễ hiểu

của mô hình giảm xuống [61]. Giải pháp để giải quyết vấn đề này là lựa chọn đặc

trưng trên bộ dữ liệu ban đầu.

Về phương diện phân tích dữ liệu, việc phát hiện ra các mối liên hệ giữa các

thuộc tính với kết quả đầu ra là vấn đề quan trọng trong việc khảo sát và cho điểm tín

dụng. Tất cả các thông tin của khách hàng vay vốn đều có ý nghĩa và quan trọng. Tuy

nhiên, mức độ quan trọng của các thuộc tính là không giống nhau. Mục tiêu của luận

án là dựa vào kỹ thuật lựa chọn đặc trưng nhằm tìm mức độ quan trọng của các thuộc

tính từ đó giúp cho việc phân lớp dữ liệu tín dụng một cách hiệu quả. Trong quá trình

thu thập dữ liệu của khách hàng đến vay vốn, có nhiều thông tin bị thiếu. Những giá

trị thiếu này của các thuộc tính ảnh hưởng tới quá trình phân tích dữ liệu tín dụng.

Trong các thuộc tính thu thập được có những thuộc tính quan trọng như thu nhập,

nghề nghiệp, học vấn. Nếu các giá trị bị thiếu này nằm trong các thuộc tính quan

trọng, cần phải xử lý hoặc thu thập lại. Tuy nhiên, cũng có một số thuộc tính ít quan

trọng hơn chẳng hạn như tuổi, nơi cư trú, tình trạng hôn nhân. Những thuộc tính với

mức độ quan trọng thấp được loại bỏ sẽ làm giảm chiều dữ liệu và làm cho việc phân

tích được hiệu quả và nhanh hơn.

2.2 Các nghiên cứu liên quan

Trong những năm gần đây đã có nhiều mô hình cho điểm tín dụng được xây

dựng, tuy nhiên độ chính xác dự đoán và mức độ tin cậy để hỗ trợ quyết định cho vay

là chưa cao. Do tiềm năng ứng dụng lớn, lĩnh vực cho điểm tín dụng đã trở thành một

chủ đề được nghiên cứu rộng rãi bởi nhiều nhà nghiên cứu [57], với nhiều mô hình

được đề xuất và phát triển sử dụng các phương pháp thống kê chẳng hạn như hồi qui

logistic (Logistic Regression-LR) [93], phân tích biệt thức tuyến tính (LDA) [65].

Gần đây, các nghiên cứu cũng đã áp dụng trí tuệ nhân tạo và tính toán mềm để thay

thế hoặc bổ sung cho các phương pháp thống kê truyền thống trong việc xây dựng

mô hình cho điểm tín dụng [11]. Trong đó, mạng nơ-ron nhân tạo vào máy véc tơ hỗ

trợ (SVM) là hai phương pháp phổ biến được dùng trong bài toán cho điểm tín dụng.

Tuy nhiên, dữ liệu tài chính nói chung và dữ liệu tín dụng nói riêng thường chứa

những thông tin không liên quan và dư thừa. Chúng có thể làm giảm độ chính xác

phân lớp và dẫn tới việc đưa ra những quyết định không chính xác [32][59]. Bởi vậy,

lựa chọn đặc trưng là một trong những hướng tiếp cận tốt nhằm loại bỏ các thông tin

dư thừa với một tập con các đặc trưng được lựa chọn đảm bảo giữ được đặc tính của

dữ liệu. Ngoài ra việc lựa chọn đặc trưng cũng cho phép rút ngắn thời gian phân tích

dữ liệu do các đặc trưng dư thừa và ít liên quan đã được loại bỏ.

Việc áp dụng khai phá dữ liệu cũng như lựa chọn đặc trưng cho bài toán cho

điểm tín dụng đã được áp dụng từ nhiều năm trước đây. Liu và Schumann [61] nghiên

cứu bốn phương pháp lựa chọn đặc trưng là: phương pháp Relief-F, phương pháp dựa

trên độ tương quan, phương pháp dựa trên sự đồng nhất và phương pháp đóng gói.

Các phương pháp này giúp cải tiến hiệu suất của mô hình: làm đơn giản hóa mô hình,

tăng tốc độ và độ chính xác. Thực nghiệm được thực hiện trên các bộ dữ liệu tín dụng

sử dụng một số bộ phân lớp như cây quyết định, mạng nơ-ron, k-NN.

Trong nghiên cứu [100], Yao thực hiện việc so sánh 07 phương pháp lựa chọn

đặc trưng được dùng phổ biến như t-test, PCA, tập thô…Thực nghiệm cho thấy việc

áp dụng các phương pháp lựa chọn đặc trưng cùng với bộ phân lớp SVM cho kết quả

tốt.

Wang và cộng sự [94] đề xuất một hướng tiếp cận mới có tên FSRT nhằm lựa

chọn đặc trưng dựa trên lý thuyết tập thô và tìm kiếm tabu. Trong cách tiếp cận này,

độ đo entropy được xem như là kinh nghiệm để tìm kiếm các giải pháp tối ưu. Thực

nghiệm trên các bộ dữ liệu tín dụng cho thấy FSRT cho hiệu suất cao do giảm chi phí

tính toán và nâng cao độ chính xác phân lớp. Sau đó, các tác giả đã cải tiến thuật toán

và trình bày trong nghiên cứu [95].

Nhiều nhà nghiên cứu chỉ xem lựa chọn đặc trưng như là một bước tiền xử lý

trước khi xây dựng mô hình. Các nghiên cứu tập trung vào việc áp dụng một phương

pháp lựa chọn đặc trưng cụ thể cho bài toán dự báo phá sản và cho điểm tín dụng.

Trong [55], Liang và cộng sự tiến hành nghiên cứu một cách tổng thể về hiệu quả của

các phương pháp lựa chọn đặc trưng trong việc dự báo suy thoái kinh tế. Kết quả thực

nghiệm cho thấy không có sự kết hợp nào là tốt nhất giữa các phương pháp lựa chọn

đặc trưng với bộ phân lớp. Ngoài ra, tùy thuộc vào các kỹ thuật được lựa chọn thì

việc lựa chọn đặc trưng không phải lúc nào cũng có thể cải tiến hiệu suất dự đoán.

Koutanaei và cộng sự [49] đề xuất một phương pháp lựa chọn đặc trưng lai

dựa trên ba giai đoạn. Giai đoạn đầu tiên là thu thập và tiền xử lý dữ liệu; giai đoạn

hai bốn thuật toán lựa chọn đặc trưng được sử dụng bao gồm: phân tích thành phần

chính (PCA), thuật toán di truyền (GA), độ lợi thông tin (IG), và Relief-F. Việc thiết

lập các tham số của các phương pháp lựa chọn đặc trưng được thực hiện dựa trên độ

chính xác phân lớp của SVM. Trong bước này, PCA là thuật toán lựa chọn đặc trưng

tốt nhất. Các tác giả đã đề xuất và chứng minh rằng phương pháp lựa chọn đặc trưng

lai hoạt động tốt trong bài toán cho điểm tín dụng.

Thuật toán lai giữa GA và mạng nơ-ron (HGA-NN) được đề xuất trong [70]

nhằm hỗ trợ việc đánh giá rủi ro tín dụng. Trong nghiên cứu này, các tác giả chia quá

trình lựa chọn đặc trưng thành hai pha. Trong pha đầu tiên không gian đặc trưng được

giảm chiều nhờ các phương pháp lọc như: chỉ số Gini, độ lợi thông tin, độ tương

quan. Các đặc trưng được lựa chọn bởi phương pháp lọc được sử dụng như là đầu

vào cho GA. Trước mỗi vòng lặp của GA, các tham số cũng được thay đổi và kiểm

soát cho phù hợp với yêu cầu.

Phương pháp SVM-RFE [37] áp dụng chiến lược loại bỏ đệ quy dựa trên máy

véc tơ nhằm lọc ra các đặc trưng liên quan và loại bỏ những đặc trưng dư thừa. Ngoài

ra, phương pháp tìm kiếm sử dụng các thuật toán tiến hóa [70], thuật toán tối ưu hóa

bầy đàn kết hợp với SVM [58] cũng đã cải thiện được độ chính xác của bài toán phân

lớp. Tuy nhiên SVM-RFE chỉ phân tích tốt với các dữ liệu kiểu số, trong khi đó dữ

liệu tín dụng có đặc điểm chứa nhiều thông tin dạng phân loại hoặc kiểu văn bản.

Việc chuyển đổi đặc trưng dạng phân loại hoặc văn bản sang đặc trưng số sẽ làm thay

đổi tính chất dữ liệu dẫn tới có thể giảm độ chính xác phân lớp. Rừng ngẫu nhiên

(Random Forest-RF) là một bộ phân lớp hiệu quả để giải quyết vấn đề này do nó có

thể phân tích cả dữ liệu số lẫn dữ liệu kiểu phân loại và văn bản.

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

2.3.1 Sơ đồ hệ thống lựa chọn đặc trưng

Với mục tiêu của luận án là xây dựng một hàm đánh giá đặc trưng phù hợp

với dữ liệu tín dụng nhằm cải tiến độ chính xác của kỹ thuật phân lớp và giảm thời

gian thực hiện từ đó giúp cho ngân hàng đưa ra những quyết định phù hợp. Quy trình

Tập đặc trưng

Tập con đặc trưng

Phân lớp

Tiền xử lý dữ liệu

Độ chính xác dự báo

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

Dữ liệu tín dụng

lựa chọn đặc trưng với bài toán cho điểm tín dụng như được trình bày Hình 2.1

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

Tiền xử lý dữ liệu: Trong các bộ dữ liệu tín dụng sử dụng thực nghiệm được

tiền xử lý để loại bỏ các giá trị thiếu, rời rạc hóa các thuộc tính số. Vì lý do bảo mật

đối với lĩnh vực ngân hàng, bộ dữ liệu của Úc đã được mã hóa và chuyển đổi.

Lựa chọn đặc trưng: Để có thể tìm ra tập con đặc trưng tối ưu, chúng tôi đã

đề xuất phương pháp lựa chọn đặc trưng dựa trên phương pháp đóng gói. Cải tiến

trong phương pháp đề xuất này là xây dựng hàm đánh giá đặc trưng và thủ tục loại

bỏ đặc trưng có tên FRFE.

Phân lớp: Phương pháp đề xuất có thể sử dụng các bộ phân lớp độc lập như

K-NN, cây quyết định, mạng nơ-ron nhân tạo…Tuy nhiên, bộ dữ liệu tín dụng chứa

nhiều kiểu dữ liệu như kiểu số, xâu, phân loại. Chúng tôi đã lựa chọn bộ phân lớp

rừng ngẫu nhiên đối với dữ liệu thực nghiệm bởi bộ phân lớp tính hiệu quả của nó.

2.3.2 Đề xuất hàm đánh giá và chiến lược tìm kiếm đặc trưng phù hợp

Vì bộ dữ liệu tín dụng có số lượng đặc trưng không lớn nên chúng tôi đề xuất

lựa chọn phương pháp đóng gói sử dụng chiến lược tìm kiếm toàn bộ với hai hướng

tìm kiếm là tiến và lùi. Các phương pháp đóng gói thường sử dụng độ chính xác dự

đoán làm tiêu chí đánh giá đặc trưng do đó trong nhiều trường hợp phương pháp này

sẽ bị “quá khớp”. Để khắc phục vấn đề này chúng tôi đã cải tiến hàm đánh giá đặc

2.3.2.1 Chiến lược lựa chọn đặc trưng tiến

trưng sử dụng kiểm chứng chéo n lần trong các phương pháp đề xuất.

Trong hướng tiếp cận này chúng tôi sử dụng chiến lược tìm kiếm tiến, từ một

tập rỗng, lần lượt thêm vào tập đó từng đặc trưng tốt nhất. Thuật toán lựa chọn đặc

trưng dựa trên phương pháp đóng gói được mô tả như sau:

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

Các bước thực hiện của thuật toán được đặc tả dưới dạng giả mã như sau:

Thuật toán 2.1: Lựa chọn đặc trưng theo hướng tiến

Đầu vào: S là tập các mẫu (xi, yi) trong đó xi có chiều là p

Đầu ra: danh sách xếp hạng của p đặc trưng

Chương trình:

1. F ← Ø //tập rỗng các đặc trưng

2. R ← Ø //tập kết quả đã sắp thứ tự của các đặc trưng

3. for i:=1 to n do

4. for l:=1 to 20 do //thuc hien 20 lan

5. for j:=1 to p do //

score

6. Tính Fj,l

theo công thức 2.2

7. endfor

8. endfor

9. locbest ← findLocBest() //tìm vị trí tốt nhất

10. fbest ← fj[locbest] //đặc trưng fj có vị trí tốt nhất

11. F = F ᴗ {fbest}

12. R = R ᴗ F // thêm đặc trưng tốt nhất vào R

13. endfor

14. return R

Ý tưởng của thuật toán là cải tiến việc xây dựng hàm đánh giá đặc trưng tốt

nhất sau đó tìm vị trí và đưa vào tập đặc trưng tối ưu. Điểm số của đặc trưng thứ j

(j=1..p) được tính bởi công thức (2.2) do chúng tôi xây dựng:

(2.2)

𝑙𝑒𝑎𝑟𝑛 là độ chính xác huấn luyện trong lần kiểm chứng chéo thứ k

Trong đó: 𝐹𝑗𝑘 là độ quan trọng của đặc trưng

𝑣𝑎𝑙𝑖𝑑𝑎𝑡𝑖𝑜𝑛

là độ chính xác kiểm thử trong lần kiểm chứng chéo thứ k

𝐴𝑘

𝐴𝑘 Giá trị 𝐹𝑗𝑘 xác định độ quan trọng của từng đặc trưng khi huấn luyện dữ liệu

bởi bộ phân lớp Random forest. Giá trị của 𝐹𝑗𝑘 càng cao, độ quan trọng của đặc trưng càng lớn. Mục tiêu của công thức (2.2) là tìm các đặc trưng làm tăng độ chính xác

trong quá trình huấn luyện. Độ chính xác huấn luyện và độ chính xác kiểm thử càng

cao cho độ tốt của đặc trưng càng cao. Tuy nhiên, độ chính xác huấn luyện và độ

𝑠𝑐𝑜𝑟𝑒 n lần và xác định đặc trưng để cho ra điểm số

chính xác kiểm thử chưa đủ để đảm bảo tính ổn định của thuật toán, do đó chúng tôi

𝑠𝑐𝑜𝑟𝑒 tốt nhất. Việc tìm ra vị trí của đặc trưng tốt nhất được thực hiện trong hàm

thực hiện tính toán điểm số 𝐹𝑗

𝐹𝑗

𝑠𝑐𝑜𝑟𝑒 cao nhất

findBestLoc() sử dụng các luật lựa chọn có thứ tự ưu tiên như sau:

𝑠𝑐𝑜𝑟𝑒 cao nhất

Luật 1: lựa chọn các đặc trưng có điểm số trung vị của 𝐹𝑗

𝑠𝑐𝑜𝑟𝑒 thấp nhất

Luật 2: lựa chọn các đặc trưng có điểm số trung bình 𝐹𝑗

Luật 3: lựa chọn các đặc trưng có độ lệch chuẩn 𝐹𝑗

Luật 1 tìm ra vị trí của các đặc trưng có điểm số trung vị cao nhất. Nếu chỉ có

1 điểm số trung vị cao nhất thì đây chính là vị trí của đặc trưng cần tìm. Nếu có từ 2

vị trí trở lên thì tiếp tục sử dụng luật 2 để tìm ra vị trí có điểm số trung bình của trung

vị cao nhất. Trong trường hợp này nếu chỉ có một vị trí thì đây là vị trí cần tìm. Ngược

𝑠𝑐𝑜𝑟𝑒 cao nhất và độ lệch chuẩn thấp nhất.

lại sẽ dùng luật 3 để tìm ra vị trí của đặc trưng có độ lệch chuẩn thấp nhất. Kết quả

trả về là vị trí của đặc trưng có điểm số 𝐹𝑗

Hướng tiếp cận tiến có khả năng tính toán nhanh vì: ở vòng lặp đầu tiên nó

xây dựng p mô hình dự đoán cho một đặc trưng và ở lần lặp cuối cùng nó xây dựng

01 mô hình dự đoán của p đặc trưng. Tuy nhiên, hướng tiếp cận này có thể bỏ sót

2.3.2.2 Chiến lược lựa chọn đặc trưng lùi

nhiều đặc trưng quan trọng.

Một hướng tiếp cận khác sử dụng chiến lược lựa chọn đặc trưng lùi được mô

tả bởi sơ đồ khối sau:

Hình 2.3 Sơ đồ khối của lựa chọn đặc trưng theo hướng lui

Các bước của thuật toán được mô tả dưới dạng mã giả như sau:

Thuật toán 2.2: Lựa chọn đặc trưng theo hướng lùi

Đầu vào: S là tập các mẫu (xi, yi) trong đó xi có chiều là p

Đầu ra: danh sách xếp hạng của p đặc trưng

Chương trình:

1. F ← tập tất cả p đặc trưng trong S

2. R ← tập rỗng các đặc trưng // tập sắp thứ tự của các đặc trưng

3. while F is not empty do

4. for fj ∈ F do

𝑟𝑎𝑛𝑘 theo công thức (2.3) //sử dụng các đặc trưng

5. Tính 𝐹𝑗

// trong tập F \ {fj}

6. end

7. ftoRemove ← FRFE()

8. F = F \ {ftoRemove}

9. R = concatenate(ftoRemove,R) // thêm đặc trưng bị loại

10. end

11. return R

Đối với chiến lược lựa chọn theo thuật toán 2.2, tất cả các đặc trưng ban đầu

được coi là tập đặc trưng tốt nhất. Thuật toán sẽ loại bỏ lần lượt các đặc trưng

theo hàm đánh giá để có tập đặc trưng tối ưu. Chúng tôi đã cải tiến việc loại bỏ các

đặc trưng bằng hàm FRFE(), trong đó áp dụng chiến lược tìm kiếm theo kinh nghiệm

để có kết quả tốt hơn.

𝑠𝑐𝑜𝑟𝑒, độ đo AUC (𝐴𝑈𝐶𝑘

𝑙𝑒𝑎𝑟𝑛, độ chính xác kiểm thử 𝐹𝑗

Ở bước kiểm chứng chéo thứ k, chúng tôi có được đặc trưng quan trọng 𝐹𝑗𝑘, 𝑙𝑒𝑎𝑟𝑛). độ chính xác học 𝐴𝑘

Những giá trị này sẽ được sử dụng để tính toán tiêu chí xếp hạng.

Tiêu chí xếp hạng cho đặc trưng thứ j được tính toán như sau:

(2.3)

Trong đó k=1,.., n là số lần kiểm chứng chéo; ε là một số thực đủ nhỏ.

Giá trị 𝐹𝑗𝑘 xác định độ quan trọng của đặc trưng khi huấn luyện dữ liệu bởi

thuật toán. Giá trị của 𝐹𝑗𝑘càng cao, độ quan trọng của đặc trưng càng lớn. Mục tiêu của công thức (2.3) là giữ lại các đặc trưng làm tăng độ chính xác huấn luyện (train)

và độ chính xác đánh giá (validate). Sự khác biệt giữa độ chính xác huấn luyện (train)

và độ chính xác đánh giá (validate) càng nhỏ cho thấy thuật toán càng ổn định. Giá

trị nhỏ ε được thêm vào để tránh trường hợp phân số chia cho 0 khi độ chính xác huấn

luyện bằng với độ chính xác kiểm tra.

Độ đo AUC thường được sử dụng để đánh giá trong các bài toán phân lớp nhị

phân như dự đoán Tốt/ Xấu hay Mua/Bán. Một mô hình hoàn hảo sẽ cho giá trị AUC

bằng 1, giá trị AUC lớn hơn 0,8 cho mô hình tốt, trong khi đó nếu giá trị AUC trong

khoảng nhỏ hơn 0,6 thì mô hình không tốt. Trong thực tế, AUC thường dự đoán chính

xác hơn đối với bài toán phân lớp nhị phân có tập dữ liệu không cân bằng, đó là lý do

tại sao chúng tôi sử dụng độ đo này trong công thức.

Chiến lược loại bỏ đệ quy (FRFE) sử dụng cả tiêu chí xếp hạng và độ chính

xác kiểm thử (test) để loại bỏ các đặc trưng. Tiêu chuẩn xếp hạng được sử dụng để

tạo ra danh sách các đặc trưng sẽ được loại bỏ và độ chính xác kiểm tra sẽ được dùng

để xác định đặc trưng nào sẽ bị loại bỏ vĩnh viễn từ danh sách các đặc trưng sẽ được

loại bỏ. Hàm FRFE() được mô tả như sau:

Giả sử ta có một tập dữ liệu với 3 đặc trưng (F1, F2, F3). Một mảng nhị phân

gồm các thành phần được thiết lập là 1 nếu đặc trưng được chọn, 0 nếu đặc trưng bị

loại bỏ. Nếu mảng có giá trị (1, 1, 1) có nghĩa là cả 3 đặc trưng được chọn và (1, 1,

0) có nghĩa là chỉ đặc trưng F3 bị loại. Trong trường hợp này có 3 đặc trưng nên sẽ

có tất cả 8 trạng thái (tập con). Một tập con đặc trưng tối ưu thường nằm đâu đó giữa

điểm đầu và điểm cuối cây.

Tập đặc trưng đầy đủ

N0,0

N1,1 N1,2 N1,3

Tập đặc trưng rỗng

N2,1 N2,2 N2,3

N3,0

Hình 2.4 Chiến lược lựa chọn đặc trưng FRFE

Các nút trong cây được gán nhãn Ni,j trong đó i là mức của cây, còn j là chỉ số

của đặc trưng bị loại bỏ trong từng mức.

Bước đầu tiên: tính toán và lưu lại hạng của từng đặc trưng trong nút N0,0, xác

định đây là hạng tốt nhất của tập tất các đặc trưng Rbest=R0,0

Bước tiếp theo: loại bỏ từng đặc trưng trong tập đặc trưng ban đầu và tính hạng

của các tập con đặc trưng có thể {N1,1, N1,2,N1,3}. Tập các giá trị xếp hạng của ba nút

này là {R1,1, R1,2, R1,3}. Giả sử R1,1

nút có tập con đặc trưng có giá trị hạng cao nhất và gán Rbest=R1,2. Các khả năng có

thể từ nút N1,2 là tập {N2,3,N2,1}. Tiếp tục tính hạng cho các tập con này và giả sử có

kết quả R2,1<(Rbest=R1,2)

nút N2,3 với Rbest=R2,3. Lúc này tập đặc trưng chỉ còn một đặc trưng và không có giá

trị xếp hạng mới nào cao hơn Rbest. Lúc này hàm sẽ quay lại nút trước đó và chọn nút

tốt nhất thứ hai là nút N1,3. Lúc này có hai tập con đặc trưng ứng viên là N2,1 và N2,2.

Tiếp tục lặp lại quá trình tính toán giá trị xếp hạng và so sánh chúng với giá trị tốt

nhất hiện tại.

Có thể nhận thấy giá trị xếp hạng thu được tốt hơn giá trị xếp hạng tốt nhất

hiện tại thì hàm tiếp tục thực hiện loại bỏ và tập con đặc trưng sẽ thu nhỏ lại. Nếu

không có giá trị xếp hạng nào tốt hơn thì sẽ quay lại nút trước đó như trình bày ở trên.

Quá trình sẽ dừng lại khi chỉ còn lại 1 đặc trưng hoặc không còn đường nào để đi.

Thủ tục FRFE loại bỏ đệ qui sử dụng chiến lược tìm kiếm theo kinh nghiệm

như đã được trình bày trong chương một nhằm giảm bớt không gian tìm kiếm. Trong

trường hợp xấu nhất sẽ là tìm kiếm vét cạn và độ phức tạp tính toán là 𝛰(2𝑁). Còn

trong trường hợp tốt thì nó tìm ra tập con đặc trưng nằm trên một đường thẳng.

2.3.3.1 Kiến trúc H20

2.3.3 Cải tiến tốc độ xử lý bằng thư viện H20

Kiến trúc H2O sử dụng cho thống kê, học máy và toán học trên dữ liệu lớn.

H2O sử dụng giao diện quen thuộc như Excel, JSON, R, Python và Scala, cho phép

người dùng có thể khám phá, mô hình hóa bộ dữ liệu sử dụng các thuật toán phân

lớp có khả năng xử lý song song và phân tán. Nó cũng cho phép bổ sung thuật toán

và chuyển đổi dữ liệu một cách linh hoạt. Hình 2.5 thể hiện kiến trúc H2O:

Hình 2.5 Kiến trúc của thư viện H203

Kiến trúc H2O được chia thành hai phần, liên kết với nhau qua một mạng đám

mây. Ở phần trên các máy trạm sử dụng hàm API có sẵn để giao tiếp với nhau và giao

tiếp với H20 trông qua kết nối mạng. Mỗi nút trong mạng đám mây là một tiến trình

Java duy nhất. Nó được chia thành ba lớp: ngôn ngữ, thuật toán, và cơ sở hạ tầng lõi.

Phần dưới bao gồm các thành phần khác nhau chạy trong một tiến trình Java.

Gói rừng ngẫu nhiên (RF) trong thư viện H20

Rừng ngẫu nhiên (Random Forest-RF) là thuật toán dựa trên kỹ thuật kết hợp

mô hình (ensemble), được phát triển bởi Leo Breiman[15]. Thuật toán phân lớp

CART sử dụng kỹ thuật bagging chính là nền tảng cho việc xây dựng thuật toán rừng

ngẫu nhiên. Trong kỹ thuật này, một nhóm nhỏ các thuộc tính được lựa chọn tại mỗi

nút của cây nhằm phân chia cho các mức tiếp theo của cây phân lớp. Tuy không gian

tìm kiếm là tương đối lớn nhưng thuật toán phân lớp lại thực hiện nhanh do không

gian tìm kiếm được chia nhỏ thành các cây nhở hơn. Cách thức phân lớp của RF được

3 http://docs.h2o.ai/h2o/latest-stable/h2o-docs/architecture.html

thể hiện như Hình 2.6

Hình 2.6 Phân lớp Random forest

Thuật toán có hai tham số chính là số cây ntree và số thuộc tính được chọn ở

mỗi lần phân chia (mtry). Để tính toán việc phân chia cây tại mỗi nút, thuật toán RF

cũng sử dụng công thức GINI giống như của thuật toán CART. Ý tưởng chính của

giải thuật RF như sau:

Một tập ngẫu nhiên gồm m thuộc tính được chọn ra ở mỗi lần phân chia cây

và chỉ m thuộc tính này tham gia vào việc phân chia cây. Thông thường 𝑚 = √𝑛 hoặc

n/3 trong đó n là tổng số các thuộc tính.

Đối với mỗi cây phát triển dựa trên một mẫu boostrap, tỷ lệ lỗi của các phần

tử không thuộc vào bootstrap sẽ được kiểm soát. Tỷ lệ lỗi này được gọi là tỷ lệ lỗi

“out-of-bag” (OOB).

Mô tả thuật toán RF

1. Chọn tham số T là số lượng các cây thành phần sẽ được xây dựng.

2. Chọn tham số m là số lượng các thuộc tính sẽ được dùng để phân chia tại

mỗi nút của cây, m thường nhỏ hơn n khá nhiều (n là tổng số các thuộc tính). Trong

suốt quá trình dựng cây, giá trị m sẽ không thay đổi.

3. Xây dựng T cây quyết định theo các bước sau:

- Xây dựng một tập gồm k mẫu ban đầu (bootstrap) bằng cách hoán vị tập các

mẫu ban đầu. Mỗi cây sẽ được dựng từ tập ban đầu này.

- Tại mỗi nút sẽ chọn ra m thuộc tính, sau đó sử dụng chúng để tìm ra cách phân

chia tốt nhất.

- Mỗi cây được phát triển và không bị cắt xén.

4. Rừng ngẫu nhiên sau khi được xây dựng sẽ dùng để phân lớp cho đối tượng

T, thu thập kết quả phân lớp đối tượng này trên tất cả các cây quyết định và sử dụng

kết quả được chọn nhiều nhất làm kết quả cuối cùng của thuật toán. Tỉ lệ lỗi của cây

tổng thể phụ thuộc vào độ mạnh của từng cây quyết định thành phần và mối quan hệ

qua lại giữa các cây đó.

Ưu điểm: là thuật toán phân lớp cho độ chính xác tương đối cao và thường

được dùng trong các bài toán phân lớp phức tạp. Mô hình được tạo ra một cách dễ

dàng, tránh được hiện tượng quá khớp. Có thể dễ dàng thực hiện song song hóa.

Nhược điểm: số lượng cây lớn sẽ làm tốc độ của thuật toán chậm với bài toán

dự đoán thời gian thực.

H2O Random forest là một công cụ phân lớp mạnh được cung cấp sẵn trong

kiến trúc H2O. Quá trình tạo cây được H2O song song hóa và chạy trên các cluster

nhờ đó thời gian thực hiện được giảm xuống đáng kể.

2.4 Thực nghiệm và kết quả

2.4.1 Thiết lập thực nghiệm

Phương pháp đề xuất được thực hiện trên ngôn ngữ R (http://www.r-

project.org) và sử dụng thư viện H20 để cải thiện hiệu năng dựa trên kiến trúc song

song. Thực nghiệm được xây dựng để kiểm tra tính đúng đắn của thuật toán đề xuất

với một số bộ dữ liệu bao gồm hai tập dữ liệu được công bố trên UCI

(https://archive.ics.uci.edu/ml/datasets.html). Đó là bộ dữ liệu tín dụng của nước Đức

và bộ dữ liệu tín dụng của nước Úc.

2.4.2 Dữ liệu thực nghiệm

Dữ liệu sử dụng trong thực nghiệm là hồ sơ tín dụng của khách hàng cá nhân

vay tiền của ngân hàng. Bộ dữ liệu tín dụng tuy có số lượng đặc trưng không nhiều

2.4.2.1 Bộ dữ liệu tín dụng của Đức

nhưng nó gồm các dữ liệu kiểu số, văn bản, phân loại.

Bộ dữ liệu tín dụng của Đức bao gồm 1.000 đơn xin vay vốn, trong đó có 700

trường hợp của ứng viên có mức tín dụng tốt và 300 trường hợp người nộp đơn bị từ

chối. Đối với mỗi ứng viên, 20 đặc trưng mô tả lịch sử tín dụng, số dư, thông tin vay

vốn và thông tin cá nhân của tài khoản. Bộ dữ liệu tín dụng của Đức có tỷ lệ phân

phối mẫu thuộc lớp tốt (Good) là 70% và 30% thuộc lớp xấu (Bad), do đó bộ dữ liệu

2.4.2.2 Bộ dữ liệu tín dụng của Úc

này có thể xem như là không cân bằng.

Bộ dữ liệu tín dụng của Úc bao gồm 690 ứng viên, với 383 trường hợp tín

dụng tốt và 307 trường hợp tín dụng xấu. Mỗi mẫu có chứa cả đặc trưng số, đặc trưng

phân loại, và văn bản. Bộ dữ liệu tín dụng của Úc có tỷ lệ phân phối mẫu thuộc lớp

bị từ chối (Rejected) là 56% và được chấp nhận (Accepted) là 44%.

2.4.3 Đánh giá hiệu năng phân lớp

Trong bài toán phân lớp, cần quan tâm tới khả năng tổng quát hóa của bộ phân

lớp khi đánh giá hiệu năng của một mô hình. Do đó, cần phải đo lường hiệu năng một

cách cẩn thận khi dự đoán trên dữ liệu kiểm thử. Sau đây là một số phương pháp dùng

2.4.3.1 Ma trận nhầm lẫn (Confusion matrix)

để đánh giá hiệu năng cho bài toán phân lớp.

Một ma trận nhầm lẫn là một bảng chứa các thông tin về phân lớp thực tế và

dự đoán cho các thuật toán phân lớp.

Lớp được dự đoán Lớp thực tế

+ - - FN TN + TP FP

Ma trận nhầm lẫn có các thông tin sau:

TP (true positive) – mẫu mang nhãn dương được phân lớp đúng vào lớp dương.

TN (true negative) – mẫu mang nhãn âm được phân lớp đúng vào lớp âm.

FN (false negative) – mẫu mang nhãn dương bị phân lớp sai vào lớp âm.

FP (false positive) – mẫu mang nhãn âm bị phân lớp sai vào lớp dương.

Độ chính xác được tính như sau:

(2.4)

𝐴𝑐𝑐𝑢𝑟𝑎𝑐𝑦 = 𝑇𝑃 + 𝑇𝑁 𝑇𝑃 + 𝑇𝑁 + 𝐹𝑃 + 𝐹𝑁

Với từng lớp có thể sử dụng thêm 2 độ đo đánh giá sau:

Độ chính xác (precision):

(2.5)

𝑃𝑟𝑒𝑐𝑖𝑠𝑖𝑜𝑛 = 𝑇𝑃 𝑇𝑃 + 𝐹𝑃

Độ phủ/độ nhạy (recall):

(2.6)

2.4.3.2 Diện tích dưới đường cong

𝑅𝑒𝑐𝑎𝑙𝑙 = 𝑇𝑃 𝑇𝑃 + 𝐹𝑁

AUC (Area Under Curve) được xác định như là một độ đo có thể đánh giá

chính xác khả năng phân lớp của mô hình được chọn. Nó là một độ đo mới và tốt hơn

so với độ chính xác phân lớp truyền thống, đặc biệt là cho dữ liệu không cân bằng.

Phương pháp này cho phép dễ dàng so sánh các đường ROC [27] khác nhau trong

khi phân tích.

Công thức tính AUC được tính như sau:

(2.7)

𝑅1 − 𝐴𝑈𝐶1 = 𝑛1(𝑛1 + 1) 2 𝑛1𝑛2

Trong đó n1 là kích cỡ của mẫu 1, n2 là kích cỡ của mẫu 2, và R1 là tổng của

các xếp hạng trong mẫu. Khi đó hiệu suất của các bộ phân lớp được so sánh như ví

dụ ở Hình 2.7

Hình 2.7 Ví dụ về đường cong AUC [27]

Giá trị của AUC được sử dụng để đánh giá độ tốt của mô hình, một mô hình

có ích phải có diện tích AUC trên 0.5. Các ngưỡng và ý nghĩa của AUC được thể hiện

trong Bảng 2.1

Bảng 2.1 Ý nghĩa của diện tích dưới đường cong AUC

AUC Ý nghĩa

>0.9 Rất tốt

0.8 đến 0.9 Tốt

0.7 đến 0.8 Trung bình

0.6 đến 0.7 Không tốt

0.5 đến 0.6 Vô dụng

Trong quá trình thực nghiệm, AUC thường được sử dụng để so sánh hiệu năng

của các mô hình. Mô hình nào có AUC cao hơn có nghĩa là mô hình đó có độ chính

xác cao hơn.

2.4.3.3 Kiểm chứng chéo

Kiểm chứng chéo n-lần này chia tách các tập dữ liệu thành n tập mẫu con bằng

nhau. Một phần mẫu con được giữ cho việc chứng thực dữ liệu, trong khi n - 1 phần

còn lại được sử dụng để huấn luyện. Ví dụ, áp dụng một kiểm chứng chéo 5 lần trên

một tập hợp dữ liệu với 100 bản ghi, bộ dữ liệu sẽ được phân chia thành 5 phần bằng

nhau. Trong vòng đầu tiên, phần đầu tiên của dữ liệu (20 bản ghi) được giữ lại để thử

nghiệm và 4 phần (80 bản ghi) khác được sử dụng để huấn luyện. Ở vòng tiếp theo,

phần thứ hai được dành riêng để thử nghiệm và 80 bản ghi còn lại được sử dụng để

huấn luyện. Quá trình này tiếp tục cho đến khi tất cả các phần được sử dụng. Kết quả

cuối cùng được tính trung bình cộng để có một kết quả duy nhất. Hình minh họa một

Kiểm tra

Huấn luyện

Kiểm tra

tra

Kiểm tra

Dữ liệu

tra

Kiểm tra

ểm tra

Kiểm tra

m tra

kiểm chứng chéo 5 lần.

Hình 2.8 Kiểm chứng chéo 5 lần

Từ việc đánh giá hiệu năng phân lớp chúng tôi lựa chọn, cải tiến mô hình để

đạt được hiệu quả cao nhất.

2.4.4.1 Bộ dữ liệu tín dụng Đức

2.4.4 Kết quả thực nghiệm

Trước khi thực hiện chạy thực nghiệm trên các phương pháp đề xuất, chúng

tôi sử dụng phương pháp lọc với các độ đo khác nhau bao gồm: Độ lợi thông tin (IG)

[51], lựa chọn đặc trưng dựa trên sự tương quan (CFS)[35], và Relief-F[84].

Kết quả thực nghiệm lựa chọn đặc trưng theo phương pháp lọc

Kết quả chạy thực nghiệm với độ đo Độ lợi thông tin được thể hiện trong Hình

)

I ( n i t g n ô h t i ợ l ộ Đ

Đặc trưng

2.9

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

Với tập danh sách các đặc trưng đã được xếp hạng, chúng tôi có thể lựa chọn

nhóm gồm 50% các đặc trưng cao nhất hoặc lựa chọn các đặc trưng có giá trị IG >

50% giá trị của số cực đại IG. Mười đặc trưng được lựa chọn theo tiêu chí độ lợi

thông tin có số thứ tự là: 1, 20, 3, 2, 5, 6, 13, 15, 14, 4. Kết quả cho thấy đặc trưng

trạng thái hiện tại (ca_status) có độ lợi thông tin cao nhất, nó sẽ được chọn là đặc

trưng quyết định để phân lớp khách hàng. Tiếp đến là các đặc trưng liên quan tới

khách hàng người nước ngoài, thời gian, lịch sử và số tiền vay.

Cũng thực hiện với bộ dữ liệu trên bằng phương pháp lựa chọn đặc trưng

F - f e i l e R o đ ộ Đ

Đặc trưng

Relief-F có kết quả như trong Hình 2.10:

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

Kết quả của thực nghiệm lựa chọn các đặc trưng có số thứ tự : 1, 3, 4, 6, 7, 9,

12, 8, 19, 2, 14, 10, 13, 18, 17, 11, 5, 16, 15, 20. Cũng giống như phương pháp độ lợi

thông tin, kết quả cho thấy đặc trưng trạng thái hiện tại (ca_status) có giá trị độ đo

cao nhất, nó sẽ là đặc trưng quyết định để phân lớp khách hàng. Tuy nhiên, các đặc

trưng tiếp theo của khách hàng có sự khác biệt và gồm có thông tin về lịch sử và mục

đích vay. Kết quả thực nghiệm sử dụng phương pháp lựa chọn đặc trưng dựa trên độ

n a u q g n ơ ư t ộ Đ

Đặc trưng

tương quan được thể hiện trong Hình 2.11

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

Theo kết quả ở Hình 2.11, với mỗi một độ đo khác nhau cho ra các tập đặc

trương được lựa chọn có các chỉ số khác nhau. Kết quả phân lớp dữ liệu sử dụng 5,

10, 15, và 20 đặc trưng có thứ hạng cao nhất theo ba phương pháp được thể hiện trong

Hình 2.12

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

Do các phương pháp lựa chọn đặc trưng này dựa vào tính chất của bộ dữ liệu

và độc lập với bộ phân lớp. Để giải quyết vấn đề trên, chúng tôi tiến hành áp dụng

Phương pháp đóng gói đề xuất theo hướng tìm kiếm tiến và sử dụng bộ phân lớp rừng

ngẫu nhiên (random forest) trong các thực nghiệm. Giá trị của tham số mtry được

mặc định và tham số ntree đã thử với giá trị 100. Hình 2.13 cho thấy kết quả thực

nghiệm được tính trung bình trên 20 thử nghiệm độc lập.

c á x h n í h c ộ Đ

Số lượng đặc trưng

Kết quả thực nghiệm lựa chọn đặc trưng theo hướng lựa chọn tiến

Hình 2.13 Độ chính xác phân lớp với bộ dữ liệu Đức

Hiệu năng của một số bộ phân lớp khác nhau [55] được so sánh và thể hiện

trong Bảng 2.2 . Cơ sở dùng để so sánh là kết quả phân lớp mà không lựa chọn đặc

trưng. Một số bộ phân lớp được sử dụng trong thực nghiệm của chúng tôi bao gồm:

SVM, CART, k-NN, Naive Bayes, MLP. Các phương pháp lựa chọn đặc trưng khác

nhau cũng được sử dụng để so sánh bao gồm cả phương pháp Lọc và phương pháp

Đóng gói. Phương pháp lọc bao gồm: t-test, phân tích biệt thức tuyến tính (LDA), hồi

quy Logistic (LR). Phương pháp Đóng gói sử dụng các kỹ thuật tối ưu bao gồm: thuật

toán di truyền (GA) và tối ưu hóa bầy đàn (PSO).

Bảng 2.2 So sánh hiệu năng của các bộ phân lớp [55] trên bộ dữ liệu tín dụng của Đức

Bộ phân lớp

cơ sở Phương pháp Lọc Phương pháp Đóng gói Phương pháp t-test LDA LR PSO GA

SVM 76,74 75,72 75,10 76,54 73,76 77,18

CART 74,28 73,52 73,66 75,72 74,16 74,30

k-NN 71,82 71,86 72,62 72,24 71,60 70,86

Naïve Bayes 72,40 70,88 71,44 71,56 74,16 70,52

MLP 73,28 73,44 73,42 74,03 72,54 71,76

75,3

RandomForest Lựa chọn tiến 76,20

Qua kết quả so sánh hiệu năng của các phương pháp khác nhau như thể hiện

trong Bảng 2.2, chúng tôi thấy rằng độ chính xác của RF trên tập hợp con các đặc

trưng mới được chọn đã được tăng lên từ 73.4% ban đầu thành 76,20%. Và số lượng

các đặc trưng được lựa chọn chỉ còn lại 65% so với số lượng đặc trưng ban đầu.

Hơn nữa, phương pháp của chúng tôi dựa trên kỹ thuật xử lý song song của

kiến trúc H20 cho phép thời gian để chạy nhanh hơn 9,5 lần so với bộ phân lớp rừng

ngẫu nhiên gốc.

Kết quả thực nghiệm theo hướng lùi sử dụng FRFE

Áp dụng phương pháp lựa chọn đặc trưng FRFE theo hướng lùi, chúng tôi có

kết quả như Hình 2.14

0.90

Pred

0.85

0.80

0.75

n á o đ ự d c á x

h n

0.70

h c

ộ Đ

0.65

0.60

10 11 12 13 14 15 16 17 18 19

7 Số đặc trưng được chọn

Hình 2.14 Độ chính xác phân lớp trên bộ dữ liệu Đức theo hướng quay lui

Pha huấn luyện cho kết quả bộ tập con các đặc trưng tốt nhất bao gồm 13 đặc

trưng và độ chính xác phân lớp dự đoán là 77,3%. Độ chính xác dự đoán tăng lên

78,95%, trong khi độ chính xác trung bình trên dữ liệu ban đầu là 76,60%.

Kết quả thực nghiệm trên bộ dữ liệu sử dụng đặc trưng thu được từ phương

pháp lọc, tiến và FRFE được thể hiện trong Hình 2.15, trong đó cột cuối là kết quả

phân lớp dự đoán bằng Random forest trên tập dữ liệu ban đầu.

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

Chúng tôi cũng thực hiện so sánh hiệu năng phân lớp của phương pháp đề xuất

với các phương pháp khác như trong Bảng 2.3

Bảng 2.3. Hiệu năng của các bộ phân lớp khác nhau [55] với bộ dữ liệu tín dụng Đức

Phương pháp Lọc Phương pháp Đóng gói

Bộ phân lớp t-test LDA LR GA PSO

76,74 75,72 75,10 74,28 73,52 73,66 71,82 71,86 72,62 72,40 70,88 71,44 73,28 73,44 73,42 76,54 75,72 72,24 71,56 74,03 73,76 74,16 71,60 74,16 72,54

Phương pháp cơ sở 77,18 74,30 70,86 70,52 71,76 76,60

SVM CART k-NN Naïve Bayes MLP Random Forest FRFE 78,95

Kết quả cho thấy thời gian thực hiện việc lựa chọn đặc trưng sử dụng bộ phân

lớp Random forest của gói H20 nhanh gấp khoảng 10 lần so với thời gian thực hiện

việc lựa chọn đặc trưng sử dụng bộ phân lớp Random forest gốc. Thời gian thực hiện

phân lớp bằng random forest của gói H20 nhanh hơn bởi nó có cơ chế xử lý song

song. Thời gian thực thi nhanh hơn giúp cho phương pháp FRFE đề xuất có khả năng

2.4.4.2 Bộ dữ liệu tín dụng Úc

lựa chọn các đặc trưng một cách hiệu quả.

Tương tự như bộ dữ liệu tín dụng của Đức, phương pháp Lọc đầu tiên chúng

tôi sử dụng là độ lợi thông tin (IG), kết quả chạy thực nghiệm khi sử dụng toàn bộ

tập dữ liệu như sau:

)

I ( n i t g n ô h t i ợ l ộ Đ

Đặc trưng

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

Các đặc trưng được lựa chọn bằng phương pháp độ lợi thông tin có thứ tự như

trên Hình 2.16. Các đặc trưng X8, X10, X9, X14, X7 có thứ hạng cao nhất theo độ

lợi thông tin. Đây chính là các đặc trưng sẽ được lựa chọn theo tiêu chí độ lợi thông

tin. Các đặc trưng X1, X11, X12 có độ lợi thông tin tương đối thấp, nó không có đóng

góp nhiều thông tin do đó có thể loại bỏ.

Cũng thực hiện với bộ dữ liệu sử dụng phương pháp Relief-F có kết quả như

trong Hình 2.17

F - f e i l e R o đ ộ Đ

Đặc trưng

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

Các đặc trưng được lựa chọn theo thứ tự là: X8, X5, X11, X4, X1. Giống như

phương pháp độ lợi thông tin, đặc trưng X8 có độ đo cao nhất so với các đặc trưng

khác. Đặc trưng X8 có thể được sử dụng làm tiêu chí đầu tiên để phân lớp dữ liệu.

Trong phương pháp này các đặc trưng như X14, X13, X10, X7 có thể loại bỏ do

chúng có giá trị xếp hạng tương đối thấp.

Phương pháp lựa chọn đặc trưng dựa trên độ tương quan được thực hiện và

cho kết quả được sắp xếp theo thứ tự giảm dần như sau:

n a u q g n ơ ư t ộ Đ

Đặc trưng

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

Các đặc trưng được xếp hạng theo độ tương quan so với các độ đo IG và Relief-

F được thể hiện trong Hình 2.18. Nhìn vào kết quả có thể thấy đặc trưng X8 có độ

quan trọng nhất trong việc phân loại khách hàng.

Cũng như bộ dữ liệu tín dụng Đức, theo kết quả ở Hình 2.18 thì với mỗi một

độ đo khác nhau cho ra những kết quả lựa chọn đặc trưng khác nhau. Từ đó có thể

thấy rằng các phương pháp lọc có thời gian thực hiện nhanh cho chỉ cần tính toán các

độ đo một lần. Tuy nhiên, một đặc trưng tốt được lựa chọn theo độ đo này có thể lại

không tốt với độ đo khác. Điều quan trọng hơn là các phương pháp lọc hoàn toàn

không phụ thuộc vào các bộ phân lớp, do đó ít có khả năng cải tiến độ chính xác của

các bộ phân lớp.

Kết quả phân lớp sử dụng 5, 7 và 10 đặc trưng có thứ hạng cao nhất theo ba

phương pháp được thể hiện trong Hình 2.19.

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

Chúng tôi tiến hành áp dụng phương pháp Đóng gói đề xuất theo hướng tìm

kiếm tiến. Trong thực nghiệm của chúng tôi, giá trị mặc định cho tham số mtry đã

được sử dụng và tham số ntree đã thử với giá trị 100. Tiến hành thực nghiệm trên

c á x h n í h c ộ Đ

Số lượng đặc trưng

hướng tiếp cận lựa chọn đặc trưng tiến, chúng tôi có kết quả:

Hình 2.20 Độ chính xác phân lớp với bộ dữ liệu Úc

Bảng 2.4 cho thấy các hiệu năng của các bộ phân lớp khác nhau và các phương

pháp lựa chọn đặc trưng khác nhau. Các kết quả thu được cho thấy rằng độ chính xác

phân lớp của RF trên tập hợp con gồm 9 đặc trưng được chọn đã được cải thiện rõ

rệt. Độ chính xác trung bình là 87,82% trên bộ dữ liệu ban đầu, trong khi độ chính

xác trung bình tăng tới 89,40% sau khi áp dụng phương pháp lựa chọn đặc trưng của

chúng tôi.

Bảng 2.4 So sánh hiệu năng của các bộ phân lớp trên bộ dữ liệu tín dụng của Úc

Bộ phân lớp Phương pháp Lọc Phương pháp Đóng gói Phương

t-test LDA LR GA PSO

85,52 85,52 85,52 85,25 85,46 85,11 86,06 85,31 84,81 68,52 67,09 66,74 85,60 86,00 85,89 85,52 84,85 84,69 86,09 85,57 85,52 84,82 84,64 85,86 85,49

pháp cơ sở 85,52 85,20 84,58 68,55 84,15 86,81

SVM CART k-NN Naïve Bayes MLP Random forest Lựa chọn tiến 89,40

Dựa trên xử lý song song, thời gian để huấn luyện với kiểm chứng chéo bằng

phương pháp của chúng trong 20 lần thử nghiệm chỉ còn 2.974 giây (~ 50 phút). Kết

quả so sánh thời gian trong một lần thực nghiệm giữa bộ phân lớp H2O Random

forest và bộ phân lớp Random forest gốc.

Chiến lược lựa chọn đặc trưng FRFE

Sau khi tiến hành chạy thủ tục FRFE, tập con tốt nhất thu được bao gồm 07

đặc trưng được lựa chọn và phương pháp đề xuất đạt độ chính xác là 87.5% trong

trường hợp của bộ dữ liệu tín dụng Úc.

Pred

0.95

0.9

c á x

0.85

h n í h c

0.8

ộ Đ

0.75

0.7

1 0

1 1

1 2

1 3

5 7 9 Số đặc trưng được chọn

Hình 2.21 Độ chính xác dự đoán trên bộ dữ liệu tín dụng Úc

Kết quả so sánh độ chính xác dự đoán sử dụng các đặc trưng được lựa chọn

bởi các phương pháp được thể hiện trong Hình 2.22. Trong đó cột cuối là kết quả

89.4

89.16

)

86.81

86.37

( c á x

84.5

83.9

h n

h c

ộ Đ

90 89 88 87 86 85 84 83 82 81 80

Phương pháp lựa chọn đặc trưng

phân lớp dự đoán bằng Random forest trên tập dữ liệu ban đầu.

Hình 2.22 Độ chính xác dự đoán sử dụng đặc trưng được lựa chọn trên bộ dữ liệu Úc

Cũng so sánh với các bộ phân lớp khác trong [55] gồm: SVM, CART, k-NN,

Naïve Bayes, MLP. Các phương pháp Lọc gồm: t-test, phân tích biệt thức tuyến tính,

hồi qui logistic. Các phương pháp Đóng gói: thuật toán di truyền (GA) và tối ưu hóa

bầy đàn (PSO). Như ta thấy độ chính xác của phương pháp đề xuất cao hơn nhiều so

với các phương pháp khác hiện có. Sau khi áp dụng phương pháp đề xuất, độ chính

xác tăng lên 89.16%, trong khi độ chính xác trung bình trên dữ liệu gốc là 87.25%.

Bảng 2.5 Hiệu năng của các bộ phân lớp khác nhau trên bộ dữ liệu tín dụng của Úc

Phương pháp Lọc Phương pháp Đóng gói

Bộ phân lớp

t-test LDA LR GA PSO

85,52 85,52 85,52 85,25 85,46 85,11 86,06 85,31 84,81 68,52 67,09 66,74 85,60 86,00 85,89 85,52 84,85 84,69 86,09 85,57 85,52 84,82 84,64 85,86 85,49

Phương pháp cơ sở 85,52 85,20 84,58 68,55 84,15 86,81

89,16 SVM CART k-NN Naïve Bayes MLP Random forest FRFE

Bằng việc sử dụng kỹ thuật song song của kiến trúc H2O, thời gian chạy huấn

luyện với kiểm chứng chéo 5-lần chỉ mất 09 phút với bộ dữ liệu tín dụng Úc.

So sánh hai phương pháp tìm kiếm:

Như đã trình bày và phân tích ở chương một, chiến lược lựa chọn đặc trưng

FRFE theo hướng lùi cho kết quả cao hơn so với chiến lược tìm kiếm tiến. Tuy nhiên,

thời gian thực hiện thì lại lâu hơn do phải quay lui thực hiện tính toán nhiều lần.

2.5 Kết luận chương

Trong chương này, chúng tôi đề xuất hai phương pháp lựa chọn đặc trưng để

cải tiến hiệu năng của bài toán cho điểm tín dụng dựa trên hướng tìm kiếm tiến và

tìm kiếm lùi đã được trình bày trong chương 1. Hướng thứ nhất là lựa chọn đặc trưng

theo hướng tìm kiếm tiến, trong đó việc thêm đặc trưng tốt nhất được thực hiện bằng

cách sử dụng các luật lựa chọn đặc trưng có tiêu chí xếp hạng cao nhất. Phương pháp

thứ hai là lựa chọn đặc trưng theo tìm kiếm lùi có tên là FRFE dựa trên việc loại bỏ

đặc trưng đệ quy dựa trên công thức tính hạng do chúng tôi đề xuất kết hợp với rừng

ngẫu nhiên. Kết quả thực nghiệm của phương pháp đề xuất trên các bộ dữ liệu tín

dụng đã cho kết quả tốt hơn so với một số phương pháp truyền thống.

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Ư

Trong chương này chúng tôi áp dụng hướng tiếp cận trích xuất đặc trưng với

mục tiêu tìm ra một phép biến đổi phù hợp để có thể tăng hiệu quả của việc phân tích

dữ liệu. Chúng tôi đề xuất phương pháp trích xuất đặc trưng dựa trên việc kết hợp các

hàm nhân cơ bản cho KPCA được sử dụng nhằm cải thiện hiệu năng phân lớp.

Phương pháp được chúng tôi đề xuất được thực nghiệm trên các bộ dữ liệu ung thư

như ung thư ruột kết, bệnh bạch cầu, bệnh ung thư máu và tuyến tiền liệt. Phương

pháp C-KPCA cho một độ chính xác phân loại tốt hơn so với KPCA và trong một số

trường hợp kết quả cao hơn so với một số thuật toán lựa chọn đặc trưng khác. Kết

quả nghiên cứu đã được công bố tại kỷ yếu của hội thảo quốc tế lần thứ 12 về học

máy và khai phá dữ liệu MLDM-2016 (Công trình SANGHV4).

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

Hiện nay tỷ lệ tử vong do chẩn đoán muộn bệnh ung thư là tương đối cao;

chiếm tới 2/3 số lượng bệnh nhân được phát hiện ung thư. Các bác sĩ chỉ tập trung

vào một số các triệu chứng chính trong khi chẩn đoán mà bỏ qua các yếu tố nguy cơ

tiềm ẩn. Ứng dụng khai phá dữ liệu trong chẩn đoán bệnh ung thư là một hướng tiếp

cận mới nhằm tăng tỷ lệ phát hiện ung thư sớm nhờ việc phân tích các dữ liệu lâm

sàng với mục tiêu giảm tỷ lệ tử vong ở các bệnh nhân mắc các căn bệnh ung thư. Các

nhà nghiên cứu cho biết việc nhận biết sớm các biểu hiện ung thư có thể giúp cứu

sống trên 5000 người mỗi năm. Quy trình phân tích dữ liệu ung thư được thể hiện ở

Hình 3.1.

Dữ liệu microarray biểu hiện gen

Hình 3.1 Phân tích dữ liệu ung thư

Lý do trích xuất đặc trưng cho bài toán phân tích dữ liệu ung thư

Trong lĩnh vực khai phá dữ liệu, xử lý dữ liệu có số chiều cao là một nhiệm

vụ hết sức quan trọng. Hầu hết các thuật toán phân lớp hiện tại chỉ có thể xử lý một

số lượng dữ liệu hữu hạn và dữ liệu này có số chiều thấp. Công nghệ microarray đã

tạo ra hàng terabyte dữ liệu sinh học trong đó dữ liệu microarray thường chứa một

lượng nhỏ các mẫu với một số lượng lớn (hàng ngàn tới hàng chục ngàn) biểu hiện

gen dưới dạng các đặc trưng. Sự gia tăng của các đặc trưng dẫn tới vấn đề bùng nổ tổ

hợp (curse of dimensionality). Thêm vào đó, các dữ liệu biểu hiện gen chứa các đặc

trưng không liên quan, dư thừa và nhiễu đòi hỏi độ phức tạp tính toán cao làm cho

việc phát hiện các gen có liên quan hết sức khó khăn. Dữ liệu dư thừa và nhiễu có thể

làm giảm độ chính xác phân lớp và dẫn đến những quyết định sai lầm. Để giải quyết

những vấn đề này, lựa chọn đặc trưng và trích xuất đặc trưng là hai kỹ thuật phổ biến

được sử dụng trong việc rút gọn đặc trưng. Nhiều nhà nghiên cứu đã áp dụng thành

công phương pháp lựa chọn đặc trưng cho bài toán phân tích dữ liệu ung thư. Tuy

nhiên, đặc điểm của bộ dữ liệu ung thư là có số mẫu nhỏ và số đặc trưng lớn. Các bộ

dữ liệu này có thể coi là dữ liệu chiều cao và thưa, phân bổ dữ liệu hết sức phức tạp.

Mức độ quan trọng của các thuộc tính trong bộ dữ liệu ung thư là khó xác định do đó

không thể chắc chắn là nên loại bỏ thuộc tính nào. Bộ dữ liệu ung thư được phân bố

rời rạc và có thể nó là thưa. Nhận thấy việc loại bỏ các thuộc tính có thể gây mất mát

thông tin có ích nên luận án đã tập trung tìm hiểu việc dựa vào kỹ thuật trích xuất đặc

trưng nhằm tìm ra một phép biến đổi phù hợp để có thể chuyển đổi dữ liệu ban đầu

sang một không gian mới. Trong không gian mới này việc phân tích dữ liệu hiệu quả

hơn.

3.2 Các nghiên cứu liên quan

Các phương pháp học máy được áp dụng cho dữ liệu microarray sớm nhất là

các phương pháp phân cụm và trong số đó phổ biến nhất là phương pháp phân cụm

theo thứ bậc. Các phương pháp phân cụm được sử dụng phổ biến do chúng hết sức

linh hoạt. Tuy nhiên, dữ liệu ngày càng gia tăng với số lượng lớn làm cho các phương

pháp này trở nên kém hiệu quả. Nhiều phương pháp đã được phát triển nhằm trích

xuất các thông tin quan trọng từ dữ liệu ung thư. Có thể chia các phương pháp trích

xuất này thành hai nhóm là nhóm các phương pháp tuyến tính và nhóm các phương

pháp phi tuyến.

- Các phương pháp tuyến tính

Như đã trình bày ở trên thuật toán rút gọn đặc trưng phổ biến nhất chính là

PCA. Sử dụng ma trận hiệp phương sai và giá trị riêng, vector riêng, PCA tìm ra các

thành phần chính trong dữ liệu ung thư. PCA và các biến thể của nó được áp dụng

như là các cách để giảm chiều dữ liệu ung thư [45][17][19]. Các tác giả trong nghiên

cứu [10] cho rằng khi tính toán các thành phần chính của một tập dữ liệu thì không

có cơ sở nào đảm bảo rằng các thành phần này có liên quan tới lớp. Do đó, phương

pháp phân tích thành phần chính có giám sát (SPCA) đã được đề xuất để lựa chọn

các thành phần chính có liên quan tới lớp. Mặc dù, phương pháp này hoạt động tốt

hơn phương pháp PCA truyền thống nhưng nó vẫn tồn tại một điểm yếu là không thể

tìm được các mối quan hệ phi tuyến trong dữ liệu, đặc biệt là trong các hệ thống sinh

học phức tạp.

Một phương pháp tương tự là phương pháp phân tích toạ độ chính (Principal

Coordinates Analysis)[14] để tính toán ma trận không tương quan với bất cứ ma trận

đầu vào nào. Phương pháp này được sử dụng với các bộ dữ liệu gen lớn bởi tính hiệu

quả của nó.

- Các phương pháp phi tuyến:

Các phương pháp giảm chiều phi tuyến làm việc theo một cách khác so với

các phương pháp tuyến tính. Cụ thể dữ liệu có chiều thấp có thể được ánh xạ sang

một không gian có chiều cao trong đó mối quan hệ phi tuyến của các đặc trưng có thể

được tìm thấy. Trong lý thuyết một hàm f có thể được sử dụng để ánh xạ các đặc

trưng sang một không gian có chiều cao hơn. Trong không gian này, mối quan hệ

giữa các đặc trưng có thể xem như là tuyến tính và có thể dễ dàng phát hiện ra. Sau

đó được ánh xạ ngược trở lại không gian có chiều thấp hơn và mối quan hệ được xem

như là phi tuyến. Trong thực tế, các hàm nhân được sử dụng để làm việc này một

cách hiệu quả. Cách tiếp cận khác là sử dụng đa tạp (manifold). Cách tiếp cận này

dựa trên giả định rằng dữ liệu nằm trên một không gian phi tuyến có chiều thấp hơn

không gian dữ liệu ban đầu. Một số thuật toán làm việc trong không gian đa tạp và

ứng dụng cho dữ liệu ung thư. Isomap [87] là phương pháp được sử dụng phổ biến

để tìm ra một không gian đa tạp phù hợp. Isomap được áp dụng với dữ liệu ung thư

với những kết quả tốt [22], tuy nhiên Orsenigo và Vercellis [71] chỉ ra điểm yếu của

Isomap là do ảnh hưởng dữ liệu nhiễu và ngoại lai. So với PCA, Isomap có khả năng

trích xuất nhiều thông tin có cấu trúc hơn. Các thuật toán khác hay được sử dụng

trong dữ liệu ung thư gồm Locally Linear Embedding (LLE) [60] và Laplacian

Eigenmaps [62] [25]. PCA và các phương pháp học đa tạp thường được sử dụng cho

việc trực quan hóa dữ liệu ung thư. Các cụm có thể được tách biệt một cách dễ dàng

với phương pháp LLE đa tạp và Isomap, tuy nhiên PCA thực hiện nhanh hơn hai

phương pháp trên.

Phương pháp phi tuyến khác là Phân tích thành phần chính dựa trên hàm nhân

(KPCA). Phương pháp này có nhiều ưu điểm bởi trong bài toán phân tích dữ liệu ung

thư, số lượng lớn thuộc tính làm cho quá trình học chậm và việc phân tích trở nên

khó khăn. Trong chương này chúng tôi sẽ áp dụng kỹ thuật trích xuất đặc trưng để

giảm chiều dữ liệu ung thư.

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

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

Nội dung của phương pháp đề xuất là sử dụng phân tích giá trị riêng (SVD) và

phân tích thành phần chính dựa trên hàm nhân (KPCA) với bộ dữ liệu ung thư để

chẩn đoán khả năng bị bệnh. Quy trình cơ bản của hệ thống bao gồm các bước: tiền

Tập đặc trưng mới

Phân lớp

Tiền xử lý dữ liệu

Độ chính xác dự báo

Dữ liệu ung thư

KPCA hàm nhân tùy chọn (C-KPCA)

xử lý dữ liệu, giảm chiều và phân lớp dữ liệu (Hình 3.2).

Hình 3.2 Quy trình trích xuất đặc trưng cho bài toán phân tích dữ liệu ung thư

Dữ liệu ung thư: bộ dữ liệu ung thư được thu thập từ các số liệu lâm sàng của

các bệnh nhân khác nhau. Dữ liệu thô chưa được định dạng được thu thập và lưu dưới

dạng tệp tin văn bản gồm hai tệp: tệp dữ liệu của gen và tệp tên của gen. Ví dụ về mã

gen và mô tả của các gen trong bộ dữ liệu ung thư ruột kết (Colon tumor)

Dữ liệu sau khi được định dạng được lưu trữ trong ba tệp:

- Tệp dữ liệu biểu hiện gen: expression_profiles.csv

- Tệp dữ liệu chứa tên các gen: genes.txt

- Tệp dữ liệu chữa nhãn của các gen bệnh: classification.txt

Kết hợp các tệp dữ liệu có được bảng dữ liệu dưới dạng:

Bảng 3.1 Cấu trúc bảng dữ liệu ung thư ruột kết

T49647 28.70125 16.77375 15.15625 16.085 31.8125

H55933 R39465 R39465 4263.408 5468.241 8589.416 4883.449 6719.53 9164.254 5369.969 6970.361 3825.705 5955.835 7823.534 6246.449 3230.329 3400.74 3694.45 .. .. .. .. .. .. .. ..

7472.01

.. 39.63125 Lớp - + - + - .. - .. 3653.934 .. 2728.216

STT 1 2 3 4 5 .. 62

Tiền xử lý dữ liệu: dữ liệu đầu vào được tiền xử lý trước bằng hàm chuẩn hóa,

chuyển đổi để đưa các giá trị về khoảng 0-1. Việc chuẩn hóa dữ liệu ung thư có ảnh

hưởng tới hiệu quả của việc phân tích và phân lớp dự báo. Kỹ thuật SVD [6] được sử

dụng để giảm chiều của dữ liệu ung thư thông qua việc phân rã ma trận dữ liệu đầu

vào thành các giá trị duy nhất.

Trích xuất đặc trưng: Chúng tôi đề xuất hàm nhân mới cho KPCA để biến

đổi không gian dữ liệu ban đầu vào không gian đặc trưng mới. Trong không gian này

dữ liệu có thể được phân lớp dễ hơn.

Phân lớp: Sau khi đã trích xuất được các thành phần chính, bộ phân lớp được

lựa chọn thực hiện việc phân lớp ung thư. Trong chương này chúng tôi sử dụng hai

bộ phân lớp là rừng ngẫu nhiên (đã được giới thiệu ở chương 2) và máy vector hỗ trợ

để tiến hành phân lớp trên bộ dữ liệu thực nghiệm.

Máy vector hỗ trợ (Support Vector Machines - SVM) được Vladimir Vapnik

và Corinna Cortes giới thiệu [20], là thuật toán học thuộc lớp giải thuật phân lớp

thống kê. SVM có khả năng xử lý dữ liệu tuyến tính và dữ liệu phi tuyến. Ý tưởng

chính của thuật toán này là việc xây dựng một siêu phẳng để phân chia dữ liệu thành

hai nửa. Trong trường hợp nếu không thể phân chia các lớp dữ liệu một cách tuyến

tính thì cần phải sử dụng một hàm nhân (kernel function) để chuyển đổi tập dữ liệu

ban đầu sang một không gian mới có số chiều lớn hơn để xử lý.

3.3.2.1 Phương pháp hàm nhân

3.3.2 Hàm nhân tùy chọn cho PCA

Trong thực tế, dữ liệu miền ứng dụng D được biểu diễn trong không gian 𝑅𝑛

theo phân tích ban đầu là không “khả tách tuyến tính” (linear separability), có nghĩa

là không tồn tại một siêu phẳng trong 𝑅𝑛 tách D thành hai lớp riêng biệt. Trong tình

huống đó, hiệu năng của mô hình phân lớp theo thuật toán phân lớp SVM đối với tập

dữ liệu D tương đối thấp, vì vậy, không thể áp dụng trực tiếp thuật toán phân lớp

SVM đối với tập dữ liệu D như biểu diễn ban đầu được. Trong trường hợp này, cần

phải tìm một biểu diễn dữ liệu thuộc D vào một không gian 𝑅𝑚 (nm, mà trong trường

hợp chung thì n

tục chuyển dạng dữ liệu trong trường hợp này bao gồm hai bước:

- Bước 1: Sử dụng một ánh xạ phi tuyến  (trường hợp đặc biệt là hàm tuyến tính

kiểu hàm phạt) chuyển biểu diễn dữ liệu thuộc D từ không gian 𝑅𝑛 sang không

gian 𝑅𝑚 mà theo biểu diễn đó tập dữ liệu D là khả tách tuyến tính.

- Bước 2: Thực hiện thuật toán phân lớp SVM trên tập dữ liệu D theo biểu diễn

dữ liệu mới trong không gian 𝑅𝑚. Khi đó, một thuật toán rút gọn đặc trưng phù

hợp (chẳng hạn PCA) cũng sẽ được áp dụng..

Hình 3.3 [21] mô tả việc chuyển dạng dữ liệu đối với tập dữ liệu D để nó không

khả tách tuyến tính khi biểu diễn trong không gian 𝑅𝑛 thành khả tách tuyến tính khi

biểu diễn trong không gian 𝑅𝑚.

Hình 3.3 Chuyển dữ liệu sang không gian có chiều lớn hơn[21]

Khi áp dụng mô hình phân lớp SVM, dữ liệu đầu vào được chuyển dạng theo

ánh xạ  đã chọn và giải pháp rút gọn đặc trưng (chẳng hạn PCA) được tiến hành trên

dữ liệu sau khi chuyển dạng.

Theo phương pháp hàm nhân, hàm chuyển dạng biểu diễn dữ liệu được tiến

3.3.2.2 Một số hàm nhân phổ biến

hành dựa trên các hàm nhân như được giới thiệu sơ bộ sau đây.

Các hàm nhân thường được dùng là hàm nhân tuyến tính, hàm nhân đa thức,

hàm nhân RBF và Sigmoid

𝑇𝑥𝑗) + 𝑐

Hàm nhân tuyến tính [40] được mô tả như sau:

𝑘(𝑥𝑖, 𝑥𝑗) = (𝑥𝑖

(3.1)

Nhân tuyến tính chỉ có một tham số là c. Hàm nhân này thực hiện tương đối

tốt và nhanh trên bộ dữ liệu có thể phân tách tuyến tính, tuy nhiên hầu hết dữ liệu

trong các bài toán thực tế là khó phân tách tuyến tính.

𝑑

Hàm nhân đa thức [40] được mô tả như sau:

, 𝛾 > 0

(3.2)

𝑇𝑥𝑗 + 𝑟)

𝑘(𝑥𝑖, 𝑥𝑗) = (𝛾𝑥𝑖

Trong số các hàm nhân thì hàm nhân đa thức có số lượng tham số nhiều hơn

cả. Ngoài tham số C và γ còn có hai tham số quan trọng khác là bậc d và r. Tham số

d cần phải được lựa chọn cẩn thận vì nếu d quá lớn thì giá trị của kernel sẽ là vô hạn

hoặc bằng 0.

Hàm nhân RBF [40] còn gọi là Gaussian hay RBF có dạng:

(3.3)

𝑘(𝑥𝑖, 𝑥𝑗) = 𝑒𝑥𝑝 (− 1 2𝛼2 ‖𝑥𝑖 − 𝑥𝑗‖)

Hoặc có thể thay bằng dạng:

)

(3.4)

2 𝑘(𝑥𝑖, 𝑥𝑗) = exp (−𝛾‖𝑥𝑖 − 𝑥𝑗‖

RBF được sử dụng phổ biến bởi nó có khả năng phân lớp dữ liệu phi tuyến.

Số lượng tham số ít hơn so với các hàm nhân khác, tham số 𝛾 ảnh hưởng nhiều tới

hiệu năng của nhân.

𝑇𝑥𝑗 + 𝑐), 𝛾 > 0

Hàm nhân Sigmoid [40] được mô tả như sau:

𝑘(𝑥𝑖, 𝑥𝑗) = 𝑡𝑎𝑛ℎ(𝛾𝑥𝑖

(3.5)

3.3.2.3 Kernel PCA[80]

Hai tham số cần lựa chọn của hàm nhân này là γ và c.

Phân tích thành phần chính dựa trên hàm nhân (KPCA) là một cách tiếp cận

hiệu quả nhờ việc xây dựng một không gian đặc trưng mới có số chiều cao hơn bằng

cách sử dụng hàm phi tuyến 𝜇(𝑥𝑡), 𝑧 = 𝜇(𝑥𝑡) và phân tích thành phần chính (PCA)

thực hiện tương tự như áp dụng PCA phi tuyến trong không gian ban đầu.

Cho trước một tập các dữ liệu 𝑥𝑖 ∈ 𝑅𝑝, 𝑖 = 1, … , 𝑛, không gian dữ liệu phi tuyến ban đầu được ánh xạ sang không gian đặc trưng mới F bởi ánh xạ ∅: 𝑅𝑝 → 𝐹

Khi thực hiện ánh xạ, giả sử xảy ra vấn đề dữ liệu bị tập trung trong không gian mới

𝑛 là ∑ ∅(𝑥𝑖) 𝑖−1

= 0. Trong F ma trận hiệp phương sai có dạng:

(3.6)

𝑛 ∅(𝑥𝑗)∅𝑇(𝑥𝑗) 𝑗−1

𝐶 = 1 𝑛

𝑛

Cần tìm kiếm một giá trị riêng 𝜆 ≥ 0 và véc tơ riêng khác không 𝑣 ∈ 𝐹\{0}

𝑖−1

. thỏa mãn 𝐶𝑣 = 𝜆𝑣 trong khoảng {∅(𝑥𝑗)}

Thứ nhất, xét tập các phương trình:

〈∅(𝑥𝑗), 𝐂v〉 = λ〈∅(𝑥𝑗), v〉

(3.7)

Với tất cả j=1,…,n, trong đó 〈. , . 〉 là tích vô hướng được xác định trong F.

𝑛

Thứ hai, tồn tại hệ số αi, i=1,…,n, sao cho:

(3.8)

𝑖−1

𝑣 = 𝛼𝑖∅(𝑥𝑖)

Kết hợp công thức (3.7) và (3.8), từ đó có được hai kết quả của bài toán giá trị

riêng cho các giá trị riêng khác không:

Kα=n λ α

(3.9)

Trong đó 𝑲 = (𝐾(𝑥𝑖, 𝑥𝑗)) 𝑖, 𝑗 = 1, . . , 𝑛 là tập ma trận hàm nhân; 𝑲 là một

hàm nhân mà tích vô hướng trong F thoả mãn 〈∅(𝑥𝑖), ∅(𝑥𝑗)〉 = 𝐾(𝑥𝑖, 𝑥𝑗) với 𝜆1 ≥ 𝜆12 ≥. . ≥ 𝜆𝑛là giá trị riêng của 𝑲 và α1, … , α𝑛 là tập các véc tơ riêng được chuẩn hóa tương ứng, với 𝜆𝑟 là giá trị riêng cuối cùng khác 0. Để trích xuất thành phần chính, cần tính toán phép chiếu lên véc tơ riêng v𝑗 trong F, j=1,…,r. Nếu x là điểm kiểm

𝑛

tra, với một ảnh ∅(x) trong F tương ứng thì:

(3.10)

𝑗 〈v𝑗, ∅(𝑥)〉 = ∝𝑖

𝑖−1

𝐾(𝑥𝑖, 𝑥)

Trong đó thành phần chính phi tuyến thứ j tương ứng với ∅

3.3.3 Xây dựng hàm nhân tùy chọn

Một số ký hiệu và định nghĩa:

Ma trận nửa xác định dương[39]: (positive semi-definite matrix): Một ma trận 𝐾𝑀×𝑀 được gọi là nửa xác định dương nếu bất cứ dạng toàn phương 𝒓𝑇𝐾𝒓 nào trên K đều không âm, nghĩa là với mọi 𝑟𝑖 ∈ ℝ, 𝑖 = 1, . . , 𝑀 ta có

≥ 0

(3.11)

𝑀 𝑟𝑖𝑟𝑗𝐾𝑖𝑗 𝑖,𝑗=1

𝑐

Hàm nửa xác định dương[39]: Một hàm kernel 𝐾: X ×→ ℝ được gọi là nửa xác định

dương nếu nó thoả mãn

- Đối xứng

- Với mọi tập {𝑥1, . . , 𝑥𝑀 ∈ X}, ma trận K được tạo thành với 𝐾𝑖𝑗 = 𝑘(𝑥𝑖, 𝑥𝑗) là

nửa xác định dương.

Định lý Mercer [39]: Một hàm 𝐾(𝑥, 𝑦) là một hàm nhân hợp lệ nếu nó thỏa mãn hai

điều kiện sau:

- Đối xứng: 𝐾(𝑥, 𝑦) = 𝐾(𝑦, 𝑥)

- Nửa xác định dương: 𝐾(𝑥, 𝑥) ≥ 0

Nello Cristianini và John Shawe-Taylor [21] chỉ ra một số cách để xây dựng một hàm

nhân mới. Cách xây dựng hàm nhân mới được trình bày trong bổ đề dưới đây.

Bổ đề 3.1 Giả sử K1 và K2 là các hàm nhân trên 𝑋 ∗ 𝑋, 𝑋 ⊆ 𝑅𝑛, 𝑎 ∈ 𝑅+, 𝑓(∙) là một

hàm tính toán giá trị thực trên X

𝜙: 𝑋 → ℝ𝑚

Với K3 là một hàm nhân trên ℝ𝑚 × ℝ𝑚 và B là một ma trận nửa xác định dương

(positive semi-definite) n*n . Khi đó hàm trên X là các hàm nhân:

Trong luận án này chúng tôi sử dụng bổ đề 3.1 để xây dựng hàm nhân mới.

Bổ đề này đã được chứng minh trong tài liệu [21]. Cách xây dựng hàm nhân phức tạp

hơn dựa trên các hàm nhân khác được dựa trên nguyên lý của bổ đề này. Cụ thể, một

hàm nhân mới được tạo ra bằng cách kết hợp các hàm nhân khác sử dụng các toán tử

như sau:

(3.12)

𝐾𝑐 = 𝛼1(𝐾1) ∘ 𝛼2(𝐾2) ∘ ⋯ ∘ 𝛼𝑚(𝐾𝑚), 𝛼𝑖 ≥ 0

Trong đó:

{𝐾𝑖 | i =1, …, m} là tập các hàm nhân dùng để kết hợp.

𝛼𝑖 : là các hệ số của mỗi hàm nhân.

và ◦ biểu diễn một toán tử giữa hai hàm nhân (cộng và nhân).

Chứng minh 𝑲𝒄 là một hàm nhân hợp lệ

Theo mệnh đề Mercer 𝐾𝑐 là một hàm nhân hợp lệ nếu thỏa mãn:

- 𝐾𝑐 đối xứng

- 𝐾𝑐 nửa xác định dương

Thật vậy:

Trường hợp 1: ◦ biểu diễn toán tử cộng (+) giữa hai hàm nhân

Khi đó hàm nhân 𝐾𝑐 có dạng:

(3.13)

𝐾𝑐 = 𝛼1(𝐾1) + 𝛼2(𝐾2) + ⋯ +𝛼𝑚(𝐾𝑚), 𝛼𝑖 ≥ 0

Chứng minh:

a. 𝑲𝒄 là đối xứng Với mọi hàm nhân 𝐾𝒊(𝑥, 𝑦) hợp lệ có

𝐾𝒊(𝑥, 𝑦) = 𝐾𝒊(𝑦, 𝑥), 𝑖 = 1 … 𝑚

(3.14)

Có

(3.15)

𝒎 𝐾𝒄(𝑥, 𝑦) = 𝛼𝑖𝐾𝒊(𝑥, 𝑦) 𝒊=𝟏

Do (3.14) ta có

(3.16)

𝒎 𝐾𝒄(𝑥, 𝑦) = 𝛼𝑖𝐾𝒊(𝑦, 𝑥) 𝒊=𝟏

(3.17)

𝒎 𝛼𝑖𝐾𝒊(𝑦, 𝑥) = 𝐾𝒄(𝑦, 𝑥) 𝒊=𝟏

𝐾𝒄(𝑥, 𝑦) = 𝐾𝒄(𝑦, 𝑥)

(3.18)

Nên 𝑲𝒄 là đối xứng.

b. 𝑲𝒄 ≥ 𝟎 Với mọi x, x’: 𝐾𝑖(𝑥, 𝑥′) ≥ 0 ∀ 𝑖 = 1. . 𝑚

Do giả thiết 𝛼𝑖 ≥ 0, ∀𝑖 nên

𝛼𝑖(𝐾𝑖) ≥ 0, 𝑖 = 1 … 𝑚

(3.19)

Từ (3.18) và (3.19) và ta có

𝐾𝑐 = 𝛼1(𝐾1) + 𝛼2(𝐾2) + ⋯ +𝛼𝑚(𝐾𝑚) ≥ 0, 𝑖 = 1 … 𝑚

(3.20)

thỏa mãn tính chất đối xứng và bán định dương nên 𝐾𝑐 là một hàm nhân hợp

lệ.

Trường hợp 2: ◦ biểu diễn toán tử nhân (*) giữa hai hàm nhân

Khi đó hàm nhân 𝐾𝑐 có dạng:

𝐾𝑐 = 𝛼1(𝐾1) ∗ 𝛼2(𝐾2) ∗ ⋯ ∗ 𝛼𝑚(𝐾𝑚), 𝛼𝑖 ≥ 0

(3.21)

𝐾𝑐 là một hàm nhân hợp lệ

Chứng minh:

a. 𝑲𝒄 là đối xứng Với mọi hàm nhân 𝐾𝒊(𝑥, 𝑦) hợp lệ có

𝐾𝒊(𝑥, 𝑦) = 𝐾𝒊(𝑦, 𝑥), 𝑖 = 1 … 𝑚

(3.22)

Có

(3.23)

𝒎 𝐾𝒄(𝑥, 𝑦) = ∏ 𝛼𝑖𝐾𝒊(𝑥, 𝑦) 𝒊=𝟏

Do (3.13) ta có

(3.24)

𝒎 𝐾𝒄(𝑥, 𝑦) = ∏ 𝛼𝑖𝐾𝒊(𝑦, 𝑥) 𝒊=𝟏

(3.25)

𝒎 ∏ 𝛼𝑖𝐾𝒊(𝑦, 𝑥) 𝒊=𝟏

= 𝐾𝒄(𝑦, 𝑥)

𝐾𝒄(𝑥, 𝑦) = 𝐾𝒄(𝑦, 𝑥)

(3.26)

Nên 𝑲𝒄 là đối xứng.

b. 𝑲𝒄 ≥ 𝟎 Với mọi x, x’: 𝐾𝑖(𝑥, 𝑥′) ≥ 0 ∀ 𝑖 = 1. . 𝑚

Do giả thiết 𝛼𝑖 ≥ 0, ∀𝑖 nên

𝛼𝑖(𝐾𝑖) ≥ 0, 𝑖 = 1 … 𝑚

(3.27)

Từ (3.26) và (3.27) và ta có

𝐾𝑐 = 𝛼1(𝐾1) ∗ 𝛼2(𝐾2) ∗ ⋯ ∗ 𝛼𝑚(𝐾𝑚) ≥ 0, 𝑖 = 1 … 𝑚

(3.28)

thỏa mãn tính chất đối xứng và bán định dương nên 𝐾𝑐 là một hàm nhân hợp

lệ.

Trường hợp 3: ◦ biểu diễn toán tử cộng (+) hoặc toán tử nhân (*) giữa hai

hàm nhân.

Khi đó hàm nhân 𝐾𝑐 có dạng:

𝐾𝑐 = 𝛼1(𝐾1) + 𝛼2(𝐾2) ∗ ⋯ +𝛼𝑚(𝐾𝑚), 𝛼𝑖 ≥ 0

(3.29)

𝐾𝑐 cũng là một hàm nhân hợp lệ.

Chứng minh:

Giả sử K1, K2 là các hàm nhân hợp lệ được kết hợp bằng toán tử cộng (+) hoặc

nhân (*)

Trường hợp 3.1: Nếu trong 𝐾𝑐 tồn tại ít nhất 01 toán tử nhân (*) và các toán

tử còn lại là toán tử cộng (+)

Ta xây dựng các hàm nhân mới có dạng:

𝐾∗ = 𝛼1𝐾1 ∗ 𝛼2𝐾2

Khi đó 𝐾𝑐 có dạng

𝐾𝑐 = 𝛼1(𝐾1) + 𝛼∗(𝐾∗) + ⋯ +𝛼𝑚(𝐾𝑚) ≥ 0, 𝑖 = 1 … 𝑚

(3.30)

Chứng minh tương tự trường hợp 1: ta có 𝐾𝑐là một hàm nhân hợp lệ.

Trường hợp 3.2: Nếu trong 𝐾𝑐 tồn tại ít nhất 01 toán tử cộng (+) và các toán

tử còn lại là toán tử cộng (*)

Ta xây dựng các hàm nhân mới có dạng:

𝐾+ = 𝛼1𝐾1 + 𝛼2𝐾2

Khi đó 𝐾𝑐 có dạng

𝐾𝑐 = 𝛼1(𝐾1) ∗ 𝛼+(𝐾+) ∗ ⋯ ∗ 𝛼𝑚(𝐾𝑚) ≥ 0, 𝑖 = 1 … 𝑚

(3.31)

Chứng minh tương tự trường hợp 2: ta có 𝐾𝑐 là một hàm nhân hợp lệ.

Trường hợp 3.3: Nếu trong 𝐾𝑐 tồn tại ít nhất 01 toán tử chia (/) và các toán tử

còn lại là toán tử cộng (+) hoặc toán tử (*)

⁄ là đối xứng với mọi hàm nhân K Ta cần chứng minh: 1 𝐾(𝑥, 𝑦)

Thật vậy:

(3.32)

𝐾(𝑥, 𝑦) = = = 𝐾(𝑦, 𝑥) 1 𝐾′(𝑥, 𝑦) 1 𝐾′(𝑦, 𝑥)

Mặt khác 𝐾𝑖 ≥ 0 ∀ 𝑖 = 1. . 𝑚

Chứng minh tương tự trường hợp 1 và 2: ta có 𝐾𝑐 là một hàm nhân hợp lệ.

Độ phức tạp tính toán của kỹ thuật trích xuất đặc trưng đề xuất là độ phức tạp

tính toán của phương pháp KPCA và độ phức tạp khi kết hợp các hàm nhân. Theo

nghiên cứu [31], trong pha kiểm tra để đánh giá hàm nhân mất thời gian tính toán là

𝛰(𝑛𝑑). Do đó, độ phức tạp tính toán về thời gian là của kỹ thuật đề xuất 𝛰(𝑛2 + 𝑛𝑑)

3.4 Thực nghiệm và kết quả

3.4.1 Thiết lập thực nghiệm

Phương pháp đề xuất của chúng tôi được thực hiện trên ngôn ngữ

R(http://www.r-project.org) và thực nghiệm trên hiện trên máy tính laptop (bộ vi xử

lý core i7 2.7GHz và 8G Ram) với một số bộ dữ liệu ung thư bao gồm: ung thư ruột

kết (colon tumor), ung thư bạch cầu (leukemia), máu trắng (lymphoma) và ung thư

tuyến tiền liệt (prostate). Chúng tôi sử dụng kết quả phân lớp bằng phương pháp

KPCA làm cơ sở để so sánh với kết quả của phương pháp đề xuất trên cùng một bộ

dữ liệu ung thư. Chúng tôi sử dụng ba loại hàm nhân như trong Bảng 3.2 để thực hiện

kết hợp bằng các toán tử cộng và nhân.

Bảng 3.2 Các hàm nhân được sử dụng

Hàm nhân Công thức Ký hiệu

2 exp (−𝛾‖𝑥𝑖 − 𝑥𝑗‖

𝑑

Radial(RBF) K1 )

𝑇𝑥𝑗 + 𝑟)

Polynomial K2 , 𝛾 > 0 (𝛾𝑥𝑖

𝑇𝑥𝑗 + 𝑐), 𝛾 > 0

Sigmoid K3 𝑡𝑎𝑛ℎ(𝛾𝑥𝑖

Bộ phân lớp: trong quá trình thực nghiệm chúng tôi thực hiện phân lớp dữ liệu

ung thư sử dụng hai bộ phân lớp là Random forest và SVM với kiểm chứng chéo 10

lần. Các tham số của bộ phân lớp SVM được thiết lập với C=1 và các tham số khác

có giá trị mặc định. Còn các tham số của bộ phân lớp Random forest được thiết lập

với số cây ntree=100, các tham số khác để mặc định. Các độ đo được sử dụng để

đánh giá hiệu năng là AUC, độ chính xác, độ phủ như đã trình bày ở chương 1.

3.4.2 Dữ liệu thực nghiệm

Hiện nay có một số bộ dữ liệu được công bố trong các nghiên cứu về phân tích

dữ liệu ung thư. Trong số các bộ dữ liệu đó, chúng tôi đã lựa chọn ra bốn bộ dữ liệu

ung thư để sử dụng thực nghiệm là: bộ dữ liệu ung thư ruột kết (Colon Tumor), bộ

dữ liệu bạch cầu (Leukemia), bộ dữ liệu máu trắng (Lymphoma) và bộ dữ liệu ung

thư tuyến tiền liệt (Prostate) như trong Bảng 3.3

Bảng 3.3 Tổng hợp các bộ dữ liệu ung thư được sử dụng trong thực nghiệm

Số lớp Bài toán cần giải quyết Tên bộ dữ liệu Số mẫu

Colon Leukemia Lymphoma Prostate Số thuộc tính 2000 7129 2647 2135 62 72 77 102 2 2 2 2 Phát hiện ung thư ruột kết Phát hiện bệnh bạch cầu cấp tính Phát hiện máu trắng Phát hiện khối u tiền liệt tuyến

Bộ dữ liệu ung thư ruột kết (Colon Tumor) được tạo thành từ 2000 đặc trưng

trong đó có 40 mẫu bị bệnh và 22 mẫu bình thường. Bộ dữ liệu này có sẵn trên trang

web:http://www.molbio.princeton.edu/colondata. Chúng tôi thực hiện việc tiền xử lý

dữ liệu ung thư và tạo ra một bộ dữ liệu được chuẩn hóa.

Bộ dữ liệu bạch cầu (Leukemia) được tạo thành bởi 7129 đặc trưng, trong đó

các mẫu thuộc hai lớp bạch cầu: 47 trường hợp thuộc loại (ALL), 25 trường hợp thuộc

loại (AML). Dữ liệu có thể được tải về từ trang web http://www.genome.wi.mit.edu.

Dữ liệu được tiền xử lý trước khi phân tích.

Bộ dữ liệu máu trắng (Lymphoma) có được từ việc nghiên cứu biểu hiện gen

của ba khối máu trắng: B-cell (B-CLL), nang lymphoma (FL) và u khuếch tán lớn B-

cell lymphoma (DLCL). Trong số 96 mẫu, chúng tôi chọn ra 77 mẫu chứa 2647 đặc

trưng thuộc hai lớp: 19 mẫu FL và 58 mẫu thuộc loại DLCL. Bộ dữ liệu này có thể

lấy về tại http://genome-www.stanford.edu/lymphoma. Sau khi tiền xử lý dữ liệu, bộ

dữ liệu được biến đổi và chuẩn hóa cho quá trình phân tích.

Bộ dữ liệu ung thư tuyến tiền liệt (Prostate) có 2135 đặc trưng với 102 mẫu.

Trong số đó có 52 mẫu bệnh chiếm tỉ lệ 51%. Các trường hợp bình thường là 49%

với 50 mẫu. Dữ liệu có thể được tải về từ trang http://www-

genome.wi.mit.edu/mpr/prostate.

3.4.3 Kết quả thực nghiệm

Trong quá trình thực nghiệm chúng tôi kết hợp và lựa chọn hàm nhân tốt nhất

cho KPCA sau đó tiến hành phân lớp dữ liệu được trích xuất, việc so sánh hiệu năng

phân lớp được chia làm ba mục:

(1)Sử dụng tất cả các đặc trưng

(2) Sử dụng các đặc trưng được trích xuất bởi KPCA (hàm nhân RBF)

(3) Sử dụng các đặc trưng được trích xuất bởi C-KPCA (hàm nhân kết hợp).

3.4.3.1 Bộ dữ liệu ung thư ruột kết

Kết quả thực nghiệm trên từng bộ dữ liệu ung thư như sau:

Trong quá trình thực nghiệm để trích xuất ra các đặc trưng bằng KPCA, chúng

tôi lựa chọn và kết hợp ba hàm nhân như mô tả trong Bảng 3.2. Kết quả độ chính xác

phân lớp trong quá trình huấn luyện và đánh giá để chọn ra hàm nhân tốt nhất được

thể hiện trong Bảng 3.4.

Bảng 3.4 Kết quả huấn luyện lựa chọn hàm nhân với bộ ung thư ruột kết

Hàm nhân

Số đặc trưng

K1+K2+K3

1/(K1+K2+K3)

K1K2K3

K1+K2*K3

81,53

87,58

74,81

89,27

87,66

88,31

88,87

84,74

90,48

91,94

84,72

92,34

91,94

92,18

87,15

93,55

92,82

91,94

86,83

94,52

90,08

86,85

88,06

86,50

89,03

81,61

86,53

86,39

100

82,34

85,10

89,49

200

85,24

82,26

82,42

83,50

88,71

500

Kết quả cho thấy việc kết hợp các hàm nhân sử dụng toán tử + cho kết quả cao

hơn so với các cách kết hợp khác trong nhiều trường hợp. So sánh hàm nhân tùy chọn

với các hàm nhân cơ bản có kết quả như trong Bảng 3.5:

Bảng 3.5 So sánh hàm nhân mới với hàm nhân cơ sở trên dữ liệu ung thư ruột kết

Hàm nhân

Số đặc trưng

K1(Rbf) K2 (Poly) K3(Sigmoid)

3 5 10 15 20 50 100 200 500

87,10 87,42 91,94 91,94 92,26 86,85 83,23 84,03 81,21

88,15 88,87 92,10 93,55 93,63 92,26 81,69 85,48 82,90

90,81 88,87 92,10 93,23 93,32 86,85 85,48 82,74 84,19

Combined 89,27 88,87 92,34 93,55 94,52 88,06 86,53 85,24 83,50

Với số lượng đặc trưng được trích xuất bằng phương pháp C-KPCA (sử dụng

hàm nhân tùy chọn K1+K2+K3) là 3 thì độ chính xác cao hơn phương pháp KPCA

sử dụng hàm nhân Rbf và hàm nhân đa thức. Với số lượng đặc trưng được trích xuất

là 5, 10, 15, 20 thì phương pháp C-KPCA luôn cho độ chính xác cao hơn so với việc

sử dụng từng hàm nhân. Kết quả thực nghiệm so sánh độ chính xác phân lớp sử dụng

các đặc trưng được trích xuất bởi C-KPCA với số đặc trưng 3, 5, 10, 15, 20, 50, 100,

200 được thể hiện dưới Hình 3.4

Hình 3.4 Độ chính xác phân lớp với bộ dữ liệu ung thư ruột kết

Kết quả Hình 3.4 cho thấy trong quá trình huấn luyện (train) và đánh giá

(validate) với số đặc trưng trong khoảng từ 10-20 đặc trưng thì phương pháp C-KPCA

sử dụng hàm nhân tùy chọn cho độ chính xác cao hơn so với việc sử dụng các hàm

nhân cơ bản. Độ chính xác phân lớp khi kiểm tra (test) bằng bộ phân lớp rừng ngẫu

nhiên và máy vector hỗ trợ sử dụng tất cả các đặc trưng được so sánh với việc sử

dụng 20 đặc trưng trích xuất bởi KPCA và C-KPCA thể hiện trong Bảng 3.6

Bảng 3.6 So sánh kết quả phân lớp dự đoán trên bộ dữ liệu ung thư ruột kết

20 đặc trưng (KPCA)

20 đặc trưng (C-KPCA)

Độ đo

AUC Accuracy Precision Recall

Tất cả đặc trưng SVM 83,6 85,5 85,4 85,5

RF 84,5 82,3 82,0 82,3

RF 85,5 82,3 82,0 82,3

SVM 82,6 85,5 85,4 85,5

RF 86,6 79,0 79,2 79,0

SVM 88,2 88,7 88,9 88,7

Độ chính xác phân lớp sử dụng 20 đặc trưng được trích xuất bằng phương

pháp C-KPCA cho kết quả cao hơn và ổn định hơn so với việc phân lớp sử dụng toàn

bộ các đặc trưng. Ngoài ra phương pháp đề xuất cũng cho kết quả phân lớp SVM cao

3.4.3.2 Bộ dữ liệu bạch cầu

hơn phương pháp KPCA sử dụng hàm nhân cơ sở.

Chúng tôi lựa chọn, kết hợp ba hàm nhân và áp dụng trên bộ dữ liệu ung thư

bạch cầu. Kết quả độ chính xác phân lớp trong quá trình huấn luyện và đánh giá để

chọn ra hàm nhân tốt nhất được thể hiện trong Bảng 3.6.

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

Hàm nhân

Số đặc trưng

K1+K2+K3

1/(K1+K2+K3)

K1K2K3

K1+K2*K3

73,82 75,56 81,94 87,50 89,10 90,28 86,04 82,50 82,71

75,21 81,88 89,44 90,00 90,14 88,33 84,38 83,96 87,08

84,91 84,46 78,67 80,62 82,90 83,00 83,28 84,47 86,08

78,13 81,81 92,71 90,28 90,76 91,94 93,82 92,85 92,78

3 5 10 15 20 50 100 200 500

Kết quả cũng cho thấy việc kết hợp các hàm nhân sử dụng toán tử + cho kết

quả cao hơn so với các cách kết hợp khác trong nhiều trường hợp. So sánh hàm nhân

tùy chọn với các hàm nhân cơ bản có kết quả như trong Bảng 3.8 và Hình 3.5

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

Hàm nhân

Số đặc trưng

K1(Rbf) K2(Poly) K3(Sigmoid)

3 5 10 15 20 50 100 200 500

78,96 76,39 82,92 83,06 84,58 83,47 86,94 81,53 82,36

85,56 89,86 90,21 89,10 90,21 88,19 80,23 81,04 82,99

81,81 88,61 88,89 90,14 88,33 86,25 86,67 89,72 90,56

Combined 78,13 81,81 92,71 90,28 90,76 91,94 93,82 92,85 92,78

Hình 3.5 Độ chính xác phân lớp với bộ dữ liệu ung thư bạch cầu

Kết quả cho thấy, với số đặc trưng là 3 và 5 được trích xuất từ phương pháp

KPCA gốc cho độ chính xác cao hơn các đặc trưng trích xuất bởi phương pháp C-

KPCA trong một số trường hợp. Với số đặc trưng từ 10 trở lên thì phương pháp C-

KPCA của chúng tôi cho kết quả cao hơn hẳn. Tiến hành kiểm tra (test) hiệu năng

phân lớp sử dụng tất cả các đặc trưng so với việc sử dụng 20 đặc trưng trích xuất bởi

KPCA và C-KPCA được thể hiện trong Bảng 3.9

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

20 đặc trưng (KPCA) 20 đặc trưng (C-KPCA)

Độ đo

AUC Accuracy Precision Recall

Tất cả đặc trưng SVM RF 77,77 81,8 81,94 77,8 81,8 80,8 81,94 77,8

RF 74,6 72,2 71,1 72,2

SVM 75,9 81,9 82,8 81,9

RF 76,8 76,4 75,9 76,4

SVM 67,5 72,2 71,4 72,2

Bảng cho thấy phương pháp đề xuất C-KPCA trích xuất ra 20 đặc trưng cho

kết quả không cao hơn so với việc sử dụng toàn bộ các đặc trưng. Lý do là bộ dữ liệu

này có hơn 7000 đặc trưng, việc trích xuất 20 đặc trưng chưa đủ thông tin để phân

lớp cho độ chính xác cao. Ngoài ra phương pháp đề xuất cũng cho kết quả phân lớp

3.4.3.3 Bộ dữ liệu máu trắng

Random forest cao hơn phương pháp KPCA sử dụng hàm nhân mặc định.

Chúng tôi tiếp tục tiến hành việc lựa chọn, kết hợp ba hàm nhân và áp dụng

trên bộ dữ liệu lymphoma. Kết quả độ chính xác phân lớp trong quá trình huấn luyện

và đánh giá để chọn ra hàm nhân tốt nhất được thể hiện trong bảng.

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

Hàm nhân

Số đặc trưng

1/(K1+K2+K3) 77,50 76,00 82,84 87,90 90,62 93,27 93,76 96,91 87,31

K1K2K3 89,48 98,57 97,40 97,40 100,00 97,21 86,36 88,25 84,48

K1+K2*K3 89,68 98,44 97,40 97,79 100,00 97,34 80,06 84,22 83,31

K1+K2+K3 87,27 98,70 98,64 98,57 100,00 99,81 81,56 88,12 87,40

3 5 10 15 20 50 100 200 500

Tương tự như hai bộ dữ liệu trước, kết quả cho thấy việc kết hợp các hàm nhân

sử dụng toán tử + cho kết quả cao hơn so với các cách kết hợp khác trong nhiều

trường hợp. So sánh hàm nhân tùy chọn với các hàm nhân cơ bản có kết quả như sau:

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

Hàm nhân

Số đặc trưng

K1(Rbf) K2(Poly) K3(Sigmoid)

3 5 10 15 20 50 100 200 500

87,79 98,70 98,25 99,94 100,00 96,88 77,01 85,06 83,90

86,75 98,70 97,92 99,42 100,00 96,30 76,75 85,58 83,25

87,27 98,70 98,70 100,00 100,00 98,70 82,73 89,87 94,68

Combined 87,27 98,70 98,64 98,57 100,00 99,81 81,56 88,12 87,40

Hình 3.6 Độ chính xác phân lớp với bộ dữ liệu lymphoma

Kết quả trong Hình 3.6 cho thấy trong quá trình huấn luyện (train) và đánh giá

(validation) với số đặc trưng trong khoảng từ 10-50 đặc trưng thì phương pháp C-

KPCA sử dụng hàm nhân tùy chọn cho độ chính xác cao hơn so với việc sử dụng các

hàm nhân cơ bản.

Độ chính xác phân lớp khi kiểm tra (test) bằng bộ phân lớp rừng ngẫu nhiên

(RF) và máy vector hỗ trợ (SVM) sử dụng tất cả các đặc trưng được so sánh với việc

sử dụng 20 đặc trưng trích xuất bởi KPCA và C-KPCA thể hiện trong Bảng 3.12

Bảng 3.12 So sánh kết quả phân lớp dự đoán trên bộ dữ liệu lymphoma

Độ đo

20 đặc trưng (KPCA) 20 đặc trưng (C-KPCA)

AUC Accuracy Precision Recall

Tất cả đặc trưng SVM RF 88 97,2 93,5 88,3 93,5 89,9 93,5 88,3

RF 98,5 93,5 93,5 93,5

SVM 96,5 97,4 97,4 97,4

RF 99,6 93,5 94 93,5

SVM 96,5 97,4 97,4 97,4

3.4.3.4 Bộ dữ liệu ung thư tuyến tiền liệt

Cuối cùng, chúng tôi tiến hành lựa chọn, kết hợp ba hàm nhân và áp dụng trên

bộ dữ liệu ung thư tuyến tiền liệt. Kết quả độ chính xác phân lớp trong quá trình huấn

luyện và đánh giá để chọn ra hàm nhân tốt nhất được thể hiện trong bảng.

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

Hàm nhân

Số đặc trưng

K1+K2+K3

1/(K1+K2+K3)

K1K2K3

K1+K2*K3

82,89 88,28 95,00 94,31 97,11 99,10 100,00 100,00 98,48

68,73 86,03 94,12 94,12 94,41 95,88 96,13 100,00 100,00

65,88 89,17 94,41 94,12 96,08 99,80 99,02 95,44 98,48

84,25 84,30 84,81 84,81 87,34 87,34 86,52 88,58 86,90

3 5 10 15 20 50 100 200 500

Tương tự như các bộ dữ liệu trước, kết quả cho thấy việc kết hợp các hàm nhân

sử dụng toán tử + cho kết quả cao hơn so với các cách kết hợp khác trong nhiều

trường hợp. So sánh hàm nhân tùy chọn với các hàm nhân cơ bản có kết quả như sau:

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

Hàm nhân

Số đặc trưng

3 5 10 15 20 50 100 200 500

K1(Rbf) K2(Poly) K3(Sigmoid) 0.8755 0.9123 0.9412 0.9451 0.9426 0.9755 0.9593 1.0000 1.0000

0.8745 0.9299 0.9515 0.9623 0.9804 0.9902 1.0000 0.9377 0.9078

0.8745 0.9275 0.9510 0.9637 0.9745 0.9902 1.0000 0.9686 0.9245

Combined 0.8289 0.8828 0.9520 0.9641 0.9711 0.9910 1.0000 1.0000 0.9848

Hình 3.7 So sánh độ chính xác phân lớp với bộ dữ liệu ung thư tuyến tiền liệt

Với bộ ung thư tuyến tiền liệt, việc sử dụng các đặc trưng trích xuất bởi C-

KPCA cho độ chính xác phân lớp ngang bằng hoặc cao hơn trong một số trường hợp

so với việc sử dụng các hàm nhân cơ bản.

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

Độ đo

20 đặc trưng (KPCA) 20 đặc trưng (C-KPCA)

Tất cả đặc trưng SVM RF 90,2 92,8 90,2 90,2 90,3 90,3 90,2 90,2

RF 93,8 83,3 83,5 83,3

SVM 91,2 91,2 91,3 91,2

RF 91 86,3 86,3 86,3

SVM 91,3 91,2 91,2 91,2

AUC Accuracy Precision Recall

Tiến hành so sánh hiệu năng phân lớp với bốn bộ dữ liệu ung thư cho kết quả

như Hình 3.8

Hình 3.8 So sánh hiệu năng phân lớp trên bốn bộ dữ liệu ung thư

Trong các thực nghiệm thực hiện trên bốn bộ dữ liệu ung thư nói trên, phương

pháp C-KPCA với hàm nhân được đề xuất thường xuyên cho độ chính xác dự đoán

cao hơn so với phương pháp KPCA truyền thống sử dụng hàm nhân cơ sở. Có thể

thấy phương pháp C-KPCA cho kết quả ổn định hơn.

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

Colon Tumor

Phương pháp

Số đặc trưng 20 8

Độ chính xác 83,5 91,2

Leukemia Độ Số chính đặc xác trưng 97,1 20 91,5 3

Lymphoma Độ Số chính đặc xác trưng 93,0 20 93,3 5

Prostate Số đặc trưng 20

Độ chính xác 91,7 -

5,2

6,4

97,1

5,6

91,1

10 4 15

90,0 75 90,3

13 6 20

91,18 82,4 72,2

93,33 92,9 96,1

113 3 15

85,29 97,1 92,2

11 3 5

PLSDR [52] GEM [38] IWSS3-MB-NB [92] DRF0-CFS [13] BDE-SVMRankf [7] C-KPCA

Bảng 3.16 thể hiện độ chính xác phân lớp của phương pháp đề xuất và các

phương pháp lựa chọn đặc trưng phổ biến hiện nay. Với bộ dữ liệu ung thư ruột kết,

việc phân lớp sử dụng 15 đặc trưng được trích xuất bằng phương pháp C-KPCA của

chúng tôi cho độ chính xác cao hơn bốn phương pháp khác là: PLSDR [52], IWSS3-

MB-NB [92], DRF0-CFS [13] và BDE-SVMRankf [7]. Trong khi đó, với bộ dữ liệu

bạch cầu thì kết quả không được cao bằng các phương pháp khác do bộ dữ liệu này

không phù hợp với phương pháp trích xuất đặc trưng của chúng tôi.

So sánh trên bộ dữ liệu máu trắng và ung thư tiền liệt tuyến, cho thấy chỉ với

5 và 15 đặc trưng được trích xuất thì độ chính xác của phương pháp đề xuất luôn cao

hơn phương pháp khác.

Chúng tôi cũng so sánh kết quả của phương pháp C-KPCA với kết quả của

các mô hình trích chọn đặc trưng dựa trên học thưa như Lasso, SRC-LatLRR [28],

HLR [42]. Kết quả được thể hiện trong Bảng 3.17 và Bảng 3.18.

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

Phương pháp Colon Tumor Prostate

SVM

85,48

91,18

LASSO

85.48

91.91

SRC

85.48

94,85

SRC-LatLRR

90.32

94,12

C-KPCA

90,3

92,2

Kết quả trong Bảng 3.17 cho thấy với bộ dữ liệu Colon tumor, phương pháp

C-KPCA cho độ chính xác tương đương phương pháp SRC-LatLRR và cao hơn ba

phương pháp SVM, LASSO và SRC. Còn với bộ dữ liệu Prostate, phương pháp C-

KPCA cho kết quả cao hơn hai phương pháp SVM và LASSO.

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

Phương pháp Lymphoma Prostate

LASSO

91,11

92,40

91,2

92.18

L1/2

92,99

91,33

SCAD-L2

HLR

94,23

93,68

C-KPCA

96,1

92,2

Phương pháp C-KPCA cho kết quả cao hơn các phương pháp khác khi so sánh

với bộ dữ liệu Lymphoma. Từ các kết quả trên có thể thấy phương pháp C-KPCA

thực hiện trích xuất đặc trưng và cho kết quả phân tốt với nhiều bộ dữ liệu ung thư.

3.5 Kết luận chương

Trong chương này, chúng tôi tập trung vào việc tìm hiểu cách tiếp cận hàm

nhân và đề xuất phương pháp C-KPCA sử dụng hàm nhân mới được kết hợp từ các

hàm nhân cơ bản khác. Hiệu quả và độ tin cậy của hàm nhân mới này được xác định

thông qua thực nghiệm. Cụ thể, phương pháp đề xuất được thực nghiệm trên bốn bộ

dữ liệu ung thư đang được dùng phổ biến hiện nay. So sánh kết quả phân lớp sử dụng

hàm nhân tùy chọn và ba hàm nhân cơ sở khác cho thấy hàm nhân của chúng tôi

thường xuyên cho độ chính xác cao hơn

Kết quả cho thấy độ chính xác phân lớp sử dụng các đặc trưng được trích xuất

bởi C-KPCA được cải thiện so với phương pháp KPCA sử dụng các hàm nhân cơ bản

và một số phương pháp lựa chọn đặc trưng đã được đề xuất trước đây.

KẾT LUẬN

Với miền ứng dụng rủi ro tín dụng, số lượng đặc trưng là không quá nhiều

nhưng số lượng bản ghi là tương đối lớn so với số đặc trưng. Nhiệm vụ là phải loại

bỏ các đặc trưng không liên quan, dư thừa và tìm ra các đặc trưng tốt cho quá trình

phân lớp. Chúng tôi đã sử dụng phương pháp lựa chọn đặc trưng FRFE và bộ phân

lớp rừng ngẫu dựa trên cơ chế phân tán và song song để xây dựng mô hình đánh giá

tín dụng. Các kết quả thực nghiệm cho thấy độ chính xác phân lớp sử dụng các đặc

trưng lựa chọn bởi phương pháp đề xuất được cải thiện tương đối khả quan. Tiêu chí

xếp hạng các đặc trưng được đề xuất nhằm giúp cải tiến độ chính xác cũng như làm

giảm thời gian thực hiện của các kỹ thuật phân lớp. Ngoài ra, thời gian chạy đã được

giảm xuống đáng kể do áp dụng các thủ tục xử lý song song.

Với việc phân tích dữ liệu ung thư có số lượng đặc trưng lớn hơn so với số bản

ghi, chúng tôi đã đề xuất kỹ thuật trích xuất đặc trưng có tên C-KPCA nhằm làm giảm

số lượng đặc trưng dựa trên kỹ thuật hàm nhân PCA. Cải tiến chính trong đề xuất của

chúng tôi là xây dựng một hàm nhân mới dựa trên việc kết hợp một số hàm nhân cơ

bản. Chúng tôi đã tiến hành thực nghiệm trên 04 bộ dữ liệu ung thư và so sánh kết

quả khi sử dụng hàm nhân đề xuất với hàm nhân cơ bản cũng như so sánh với một số

phương pháp lựa chọn đặc trưng phổ biến khác. Thực nghiệm cho thấy C-KPCA cho

kết quả ổn định và tốt hơn so với các phương pháp khác trong một số trường hợp.

Hướng nghiên cứu tiếp theo

Các kết quả nghiên cứu về lựa chọn đặc trưng mới tập trung xây dựng hàm

đánh giá chủ yếu dựa trên độ chính xác của các bộ phân lớp. Trong một số nghiên

cứu gần đây cho thấy việc sử độ đo AUC là tốt hơn so với độ chính xác khi phân tích

trên bộ dữ liệu đa lớp hoặc không cân bằng, mặc dù trong hàm đánh giá chúng tôi

cũng đã sử dụng độ đo này tuy nhiên mức độ ảnh hưởng của nó chưa được đánh giá

một cách độc lập. Do đó, trong các nghiên cứu tiếp theo, chúng tôi dự kiến sẽ tiến

hành khảo sát kỹ sự ảnh hưởng của độ đo AUC nhằm tăng hiệu năng của hàm đánh

giá.

Các kết quả nghiên cứu về trích xuất đặc trưng mới chỉ dừng lại ở việc kết hợp

thủ công các hàm nhân cơ bản để có được hàm nhân mới cho KPCA trong phân tích

dữ liệu ung thư. Chúng tôi sẽ khảo sát và nghiên cứu tìm hiểu việc ứng dụng kỹ thuật

học máy nhằm tự động xây dựng hàm nhân mới dựa trên việc kết hợp các hàm nhân

cơ bản phù hợp với từng loại dữ liệu cần phân tích.

DANH MỤC CÔNG TRÌNH KHOA HỌC LIÊN QUAN ĐẾN

LUẬN ÁN

Tạp chí quốc tế: [SANGHV1]. Ha Van Sang, Nguyen Ha Nam, Nguyen Duc Nhan. (2016). “A Novel Credit Scoring Prediction Model based on Feature Selection Approach and Parallel Random Forest” Indian Journal of Science and Technology, Vol 9(S20), May 2016. (Scopus4)

[SANGHV2]. Ha Van Sang, Nguyen Ha Nam, & Bao, H. N. T. (2017). A hybrid feature selection method for credit scoring. EAI Endorsed Trans. Context- Aware Syst. & Appl., 4(11), e2. (DBLP5)

Hội thảo quốc tế: [SANGHV3]. Van-Sang Ha and Ha-Nam Nguyen (2016). “Credit scoring with a feature selection approach based deep learning”, in MATEC Web of Conferences, vol. 54, p. 05004.(Scopus)

[SANGHV4]. Van-Sang Ha and Ha-Nam Nguyen. (2016). “C-KPCA: Custom Kernel PCA for Cancer Classification”, in Machine Learning and Data Mining in Pattern Recognition: 12th International Conference, MLDM 2016, Springer International Publishing, pp. 459–467(Scopus; DBLP)

4 https://www.scopus.com/authid/detail.uri?authorId=57190294285

5 http://dblp.uni-trier.de/pers/hd/h/Ha:Van=Sang

[SANGHV5]. Van-Sang Ha and Ha-Nam Nguyen (2016), “FRFE: Fast Recursive Feature Elimination for Credit Scoring”, in Nature of Computation and Communication: Second International Conference, ICTCC 2016, Springer International Publishing, pp. 133–142.(Scopus; DBLP)

TÀI LIỆU THAM KHẢO

[1]. • Định, V. V. (2016). Rút gọn thuộc tính trong bảng quyết định không đầy đủ theo tiếp

cận tập thô dung sai. Luận án tiến sĩ, Học viện Khoa học và Công nghệ.

[2]. • Dương, H. Đ. (2015). Một số phương pháp trích chọn đặc trưng và phát hiện đám cháy

qua dữ liệu ảnh. Luận án tiến sĩ, Học viện Kỹ thuật Quân sự.

[3]. • Hương, N. T. L. (2016). Rút gọn thuộc tính trong bảng quyết định động theo tiếp cận

tập thô. Luận án tiến sĩ, Học viện Khoa học và Công nghệ.

Tiếng Việt

Tiếng Anh [4]. Abdou, H., & Pointon, J. (2011). Credit scoring, statistical techniques and evaluation criteria : a review of the literature. Intelligent Systems in Accounting, Finance and Management, 18(2–3), 59–88.

[5]. Agarwal, B., & Namita, M. (2016). Prominent Feature Extraction for Sentiment

Analysis. Springer International.

[6]. Alter, O., Brown, P. O., & Botstein, D. (2000). Singular value decomposition for genome-wide expression data processing and modeling. Proceedings of the National Academy of Sciences of the United States of America, 97(18), 10101–6.

[7]. Apolloni, J., Leguizamón, G., & Alba, E. (2016). Two hybrid wrapper-filter feature selection algorithms applied to high-dimensional microarray experiments. Applied Soft Computing Journal, 38, 922–932.

[8]. Aziz, R., Verma, C. K., & Srivastava, N. (2017). Dimension reduction methods for

microarray data: a review. AIMS Bioengineering, 4(2), 179–197.

[9]. Bae, C., Yeh, W. C., Chung, Y. Y., & Liu, S. L. (2010). Feature selection with Intelligent Dynamic Swarm and rough set. Expert Systems with Applications, 37(10), 7026–7032. [10]. Bair, E., Hastie, T., Paul, D., & Tibshirani, R. (2006). Prediction by supervised principal components. Journal of the American Statistical Association, 101(473), 119– 137.

[11]. Bellotti, T., & Crook, J. (2009). Support vector machines for credit scoring and discovery of significant features. Expert Systems with Applications, 36(2 PART 2), 3302–3308.

[12]. Benabdeslem, K., & Hindawi, M. (2014). Efficient semi-supervised feature selection: Constraint, relevance, and redundancy. IEEE Transactions on Knowledge and Data Engineering, 26(5), 1131–1143.

[13]. Bolón-Canedo, V., Sánchez-Maroño, N., & Alonso-Betanzos, a. (2015). Distributed feature selection: An application to microarray data classification. Applied Soft Computing, 30, 136–150.

[14]. Borg, I., & Groenen, P. (2005). Modern Multidimensional Scaling: Theory and

Applications. In Chapter 10 (pp. 100–131).

[15]. Breiman, L. (2001). Random Forests. Machine Learning, 45(1), 5–32. [16]. Cai, X., Nie, F., & Huang, H. (2007). Exact Top- k Feature Selection via l2,0-Norm

Constraint. Ijcai, 1240–1246.

[17]. Cangelosi, R., & Goriely, A. (2007). Component retention in principal component

analysis with application to cDNA microarray data. Biology Direct, 2.

[18]. Chen, W. C., Tseng, S. S., & Hong, T. P. (2008). An efficient bit-based feature selection

method. Expert Systems with Applications, 34(4), 2858–2869.

[19]. Chen, X., Wang, L., Smith, J. D., & Zhang, B. (2008). Supervised principal component analysis for gene set enrichment of microarray data with continuous or survival outcomes. Bioinformatics, 24(21), 2474–2481.

[20]. Cortes, C., & Vapnik, V. (1995). Support-vector networks. Machine Learning, 20(3),

273–297.

[21]. Cristianini, N., & Shawe-Taylor, J. (2000). An Introduction to Support Vector

Machines and other kernel based learning methods. Ai Magazine.

[22]. Dawson, K., Rodriguez, R. L., & Malyj, W. (2005). Samle phenotype clusters in high- density oligonucleotide microarray data sets are revealed using Isomap, a nonlinear algorithm. BMC Bioinformatics, 6.

[23]. Diao, R., & Parthaláin, N. S. Mac. (2014). Feature Selection with Harmony Search and

its Applications. PhD Thesis, Aberystwyth University.

[24]. Du, L., & Shen, Y. (2015). Unsupervised Feature Selection with Adaptive Structure Learning. International Conference on Knowledge Discovery and Data Mining, 209– 218.

[25]. Ehler, M., Rajapakse, V. N., Zeeberg, B. R., Brooks, B. P., Brown, J., Czaja, W., & Bonner, R. F. (2011). Nonlinear gene cluster analysis with labeling for microarray gene expression data in organ development. In BMC Proceedings (Vol. 5).

[26]. Eyben, F. (2016). Real-time Speech and Music Classification by Large Audio Feature

Space Extraction. Springer International.

[27]. Fawcett, T. (2006). An introduction to ROC analysis. Pattern Recognition Letters,

27(8), 861–874.

[28]. Gan, B., Zheng, C.-H., Zhang, J., & Wang, H.-Q. (2014). Sparse Representation for Tumor Classification Based on Feature Extraction Using Latent Low-Rank Representation. BioMed Research International, 2014, 1–7.

[29]. Ghaemi, M., & Feizi-Derakhshi, M.-R. (2016). Feature selection using Forest

Optimization Algorithm. Pattern Recognition, 60, 121–129.

[30]. Ghamisi, P., & Benediktsson, J. A. (2015). Feature selection based on hybridization of genetic algorithm and particle swarm optimization. IEEE Geoscience and Remote Sensing Letters, 12(2), 309–313.

[31]. Ghashami, M., & Perry, D. J. (2016). Streaming Kernel Principal Component Analysis,

41, 1365–1374.

[32]. Guyon, I., & Elisseeff, A. (2003). An introduction to variable and feature selection.

Journal of Machine Learning Research, 3, 1157–1182.

[33]. Guyon, I., & Elisseeff, A. (2006). An Introduction to Feature Extraction. Feature

Extraction - Foundations and Applications, 207(10), 740.

[34]. Hall, M. a. (1999). Correlation-based Feature Selection for Machine Learning.

Methodology. PhD Thesis, University of Waikato.

[35]. Hall, M., & Smith, L. a. (1999). Feature Selection for Machine Learning : Comparing a Correlation-based Filter Approach to the Wrapper CFS : Correlation-based Feature. International FLAIRS Conference, 5.

[36]. Hara, S., & Maehara, T. (2017). Enumerate Lasso Solutions for Feature Selection.

Aaai, 1985–1991.

[37]. Harikrishna, S., Farquad, M. A. H., & Shabana. (2012). Credit Scoring Using Support Vector Machine: A Comparative Analysis. Advanced Materials Research, 433–440, 6527–6533.

101

[38]. Hernandez Hernandez, J., Duval, B., & Hao, J.-K. (2007). A Genetic Embedded Approach for Gene Selection and Classification of Microarray Data. In Evolutionary Computation,Machine Learning and Data Mining in Bioinformatics (Vol. 4447, pp. 90–101).

[39]. Hochstadt, H. (1989). Integral equations. New York: A Wiley-Interscience

Publication.

[40]. Hofmann, T., Schölkopf, B., & Smola, A. J. (2008). Kernel methods in machine

learning. The Annals of Statistics, 36(3), 1171–1220.

[41]. Hua, J., Tembe, W. D., & Dougherty, E. R. (2009). Performance of feature-selection methods in the classification of high-dimension data. Pattern Recognition, 42(3), 409– 424.

[42]. Huang, H. H., Liu, X. Y., & Liang, Y. (2016). Feature selection and cancer classification via sparse logistic regression with the hybrid L1/2 +2regularization. PLoS ONE, 11(5), 1–15.

[43]. Jian, L., Li, J., Shu, K., & Liu, H. (2016). Multi-label informed feature selection. In IJCAI International Joint Conference on Artificial Intelligence (Vol. 2016–Janua, pp. 1627–1633).

[44]. Jiao, N., Miao, D., & Zhou, J. (2010). Two novel feature selection methods based on decomposition and composition. Expert Systems with Applications, 37(12), 7419–7426. [45]. Jonnalagadda, S., & Srinivasan, R. (2008). Principal components analysis based methodology to identify differentially expressed genes in time-course microarray data. BMC Bioinformatics, 9.

[46]. Jung, M., & Zscheischler, J. (2013). A guided hybrid genetic algorithm for feature selection with expensive cost functions. In Procedia Computer Science (Vol. 18, pp. 2337–2346).

[47]. Karhunen, J., Hyvarinen, A., Vigario, R., Hurri, J., & Oja, E. (1997). Applications of neural blind separation to signal and image processing. In 1997 IEEE International Conference on Acoustics, Speech, and Signal Processing (Vol. 1, pp. 131–134). [48]. Kennedy, J., & Eberhart, R. (1995). Particle swarm optimization. Neural Networks,

1995. Proceedings., IEEE International Conference on, 4, 1942–1948 vol.4.

[49]. Koutanaei, F. N., Sajedi, H., & Khanbabaei, M. (2015). A hybrid data mining model of feature selection algorithms and ensemble learning classifiers for credit scoring. Journal of Retailing and Consumer Services, 27, 11–23.

[50]. Lee, C.-P., & Leu, Y. (2011). A novel hybrid feature selection method for microarray

data analysis. Applied Soft Computing, 11(4), 208–213.

[51]. Lee, C., & Lee, G. G. (2006). Information gain and divergence-based feature selection text categorization. Information Processing and

learning-based

for machine Management.

[52]. Li, G. Z., Zeng, X. Q., Yang, J. Y., & Yang, M. Q. (2007). Partial Least Squares Based Dimension Reduction with Gene Selection for Tumor Classification. 2007 IEEE 7th International Symposium on BioInformatics and BioEngineering.

[53]. Li, J., Cheng, K., Wang, S., Morstatter, F., Trevino, R. P., Tang, J., & Liu, H. (2016).

Feature Selection: A Data Perspective, 1–73.

[54]. Li, Y., Chen, C. Y., & Wasserman, W. W. (2015). Deep feature selection: Theory and application to identify enhancers and promoters. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 9029, pp. 205–217).

102

[55]. Liang, D., Tsai, C.-F., & Wu, H.-T. (2015). The effect of feature selection on financial

distress prediction. Knowledge-Based Systems, 73, 289–297.

[56]. Liang Sun, Shuiwang Ji, J. Y. (2013). Multi-Label Dimensionality Reduction. Chapman

and Hall/CRC.

[57]. Lin, W. Y., Hu, Y. H., & Tsai, C. F. (2012). Machine learning in financial crisis prediction: A survey. IEEE Transactions on Systems, Man and Cybernetics Part C: Applications and Reviews.

[58]. Ling, Y., Cao, Q. Y., & Zhang, H. (2011). Application of the PSO-SVM model for credit scoring. Proceedings - 2011 7th International Conference on Computational Intelligence and Security, CIS 2011, 47–51.

[59]. Liu, H., & Motoda, H. (1998). Feature Selection for Knowledge Discovery and Data

Mining. Springer US.

[60]. Liu, X., Tosun, D., Weiner, M. W., & Schuff, N. (2013). Locally linear embedding

(LLE) for MRI based Alzheimer’s disease classification. NeuroImage, 83, 148–157.

[61]. Liu, Y., & Schumann, M. (2005). Data mining feature selection for credit scoring

models. Journal of the Operational Research Society, 56(9), 1099–1108.

[62]. M., K., A., S., & S., O. (2002). Analysis of DNA microarray data using self-organizing map and kernel based clustering. {ICONIP}’02. Proceedings of the 9th International Conference on Neural Information Processing. Computational Intelligence for the {E}- Age, 2, 755–759.

[63]. Maldonado, S., & Weber, R. (2009). A wrapper method for feature selection using

Support Vector Machines. Information Sciences, 179(13), 2208–2217.

[64]. Meyer, P. E., Schretter, C., & Bontempi, G. (2008). Information-Theoretic Feature Selection in Microarray Data Using Variable Complementarity. IEEE Journal of Selected Topics in Signal Processing, 2(3), 261–274.

[65]. Mylonakis, J., & Diacogiannis, G. (2010). Evaluating the likelihood of using linear discriminant analysis as a commercial bank card owners credit scoring model. International Business Research, 3(2), 9–21.

[66]. Nakariyakul, S., & Casasent, D. P. (2009). An improvement on floating search algorithms for feature subset selection. Pattern Recognition, 42(9), 1932–1940. [67]. Nello Cristianini, J. S.-T. (2000). An Introduction to Support Vector Machines and

Other Kernel-based Learning Methods. Cambridge University Press.

[68]. Nixon, M., & Aguado, A. (2012). Feature Extraction and Image Processing for Computer Vision. Feature Extraction & Image Processing for Computer Vision, Second Edition.

[69]. Nziga, J. (2015). Incremental Sparse-PCA Feature Extraction For Data Streams. PhD

Thesis, Nova Southeastern University.

[70]. Oreski, S., & Oreski, G. (2014). Genetic algorithm-based heuristic for feature selection

in credit risk assessment. Expert Systems with Applications, 41(4), 2052–2064.

[71]. Orsenigo, C., & Vercellis, C. (2012). An effective double-bounded tree-connected Isomap algorithm for microarray data classification. Pattern Recognition Letters, 33(1), 9–16.

[72]. Park, C. H., & Lee, M. (2008). On applying linear discriminant analysis for multi-

labeled problems. Pattern Recognition Letters, 29(7), 878–887.

[73]. Pawlak, Z. (1996). Rough sets: Theoretical aspects of reasoning about data. Control

Engineering Practice.

[74]. Peng, H., & Fan, Y. (2016). Direct Sparsity Optimization Based Feature Selection for

103

Multi-Class Classification. Ijcai, 1918–1924.

[75]. Peng, H., & Fan, Y. (2017). A General Framework for Sparsity Regularized Feature Selection via Iteratively Reweighted Least Square Minimization. Proceedings of the 31th Conference on Artificial Intelligence (AAAI 2017), 2471–2477.

[76]. Peng, H., Long, F., & Ding, C. (2005). Feature selection based on mutual information: Criteria of Max-Dependency, Max-Relevance, and Min-Redundancy. IEEE Trans. on Pattern Analysis and Machine Intelligence, 27(8), 1226–1238.

[77]. Peng, Y., Wu, Z., & Jiang, J. (2010). A novel feature selection approach for biomedical

data classification. Journal of Biomedical Informatics, 43(1), 15–23.

[78]. Piramuthu, S. (2006). On preprocessing data for financial credit risk evaluation. Expert

Systems with Applications.

[79]. Roy, D., Murty, K. S. R., & Mohan, C. K. (2015). Feature selection using Deep Neural Networks. In 2015 International Joint Conference on Neural Networks (IJCNN) (pp. 1–6).

[80]. Schölkopf, B., Smola, A., & Müller, K.-R. (1998). Nonlinear Component Analysis as

a Kernel Eigenvalue Problem. Neural Computation, 10(5), 1299–1319.

[81]. Soliz, P., Russell, S. R., Abramoff, M. D., Murillo, S., Pattichis, M., & Davis, H. (2008). Independent Component Analysis for Vision-inspired Classification of Retinal Images with Age-related Macular Degeneration. 2008 IEEE Southwest Symposium on Image Analysis and Interpretation, 65–68.

[82]. Soufan, O., Kleftogiannis, D., Kalnis, P., & Bajic, V. B. (2015). DWFS: A wrapper feature selection tool based on a parallel Genetic Algorithm. PLoS ONE, 10(2). [83]. Stańczyk, U., & Jain, L. C. (2015). Feature Selection for Data and Pattern Recognition.

Studies in Computational Intelligence (Vol. 584).

[84]. Sun, Y. (2007). Iterative RELIEF for feature weighting: Algorithms, theories, and applications. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(6), 1035–1051.

[85]. Swiniarski, R. W., & Skowron, A. (2003). Rough set methods in feature selection and

recognition. Pattern Recognition Letters, 24(6), 833–849.

[86]. Tang, J., Alelyani, S., & Liu, H. (2014). Feature Selection for Classification: A Review.

Data Classification: Algorithms and Applications, 37–64.

[87]. Tenenbaum, J. B., de Silva, V., & Langford, J. C. (2000). A global geometric framework for nonlinear dimensionality reduction. Science (New York, N.Y.), 290(5500), 2319–23.

[88]. Thomas, L. C. (2009). Consumer credit models: Pricing, profit and portfolios.

Consumer Credit Models: Pricing, Profit and Portfolios.

[89]. Unler, A., Murat, A., & Chinnam, R. B. (2011). Mr2PSO: A maximum relevance minimum redundancy feature selection method based on swarm intelligence for support vector machine classification. Information Sciences, 181(20), 4625–4641.

[90]. Verónica Bolón-Canedo, Noelia Sánchez-Maroño, A. A.-B. (2015). Feature Selection

for High-Dimensional Data. Springer International.

[91]. Villacampa, O. (2015). Feature Selection and Classification Methods for Decision Making: A Comparative Analysis. Nova Southeastern University. PhD Thesis, Nova Southeastern University.

[92]. Wang, A., An, N., Chen, G., Yang, J., Li, L., & Alterovitz, G. (2014). Incremental wrapper based gene selection with Markov blanket. 2014 IEEE International Conference on Bioinformatics and Biomedicine (BIBM).

104

[93]. Wang, H., Xu, Q., & Zhou, L. (2015). Large unbalanced credit scoring using lasso-

logistic regression ensemble. PLoS ONE, 10(2).

[94]. Wang, J., Guo, K., & Wang, S. (2010). Rough set and Tabu search based feature

selection for credit scoring. Procedia Computer Science, 1(1), 2425–2432.

[95]. Wang, J., Hedar, A.-R., Wang, S., & Ma, J. (2012). Rough set and scatter search metaheuristic based feature selection for credit scoring. Expert Systems with Applications, 39(6), 6123–6128.

[96]. Wei, X., & Yu, P. S. (2016). Unsupervised Feature Selection by Preserving Stochastic

Neighbors, 51(6), 995–1003.

[97]. Xie, J., & Wang, C. (2011). Using support vector machines with a novel hybrid feature selection method for diagnosis of erythemato-squamous diseases. Expert Systems with Applications, 38(5), 5809–5815.

[98]. Xu, Z., Huang, G., Weinberger, K. Q., & Zheng, A. X. (2014). Gradient boosted feature selection. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining - KDD ’14, 522–531.

[99]. Yang, J., Frangi, A. F., Yang, J. Y., Zhang, D., & Jin, Z. (2005). KPCA plus LDA: A complete kernel fisher discriminant framework for feature extraction and recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(2), 230–244. [100]. Yao, P. Y. P. (2009). Feature Selection Based on SVM for Credit Scoring. 2009 International Conference on Computational Intelligence and Natural Computing, 2, 44–47.

[101]. Yusta, S. C. (2009). Different metaheuristic strategies to solve the feature selection

problem. Pattern Recognition Letters, 30(5), 525–534.

[102]. Zainudin, M., Sulaiman, M., Mustapha, N., Perumal, T., Nazri, A., Mohamed, R., & Manaf, S. (2017). Feature Selection Optimization using Hybrid Relief-f with Self- adaptive Differential Evolution. International Journal of Intelligent Engineering and Systems, 10(3), 21–29.

[103]. Zhang, M. L., Peña, J. M., & Robles, V. (2009). Feature selection for multi-label naive

Bayes classification. Information Sciences, 179(19), 3218–3229.

[104]. Zhao, L., Hu, Q., & Wang, W. (2015). Heterogeneous Feature Selection with Multi- Modal Deep Neural Networks and Sparse Group LASSO. IEEE Transactions on Multimedia, 17(11), 1936–1948.

[105]. Zhou, S. (2003). Probabilistic analysis of kernel principal components: mixture

modeling and classification. IEEE Transactions on Pattern Analysis, (i), 1–26.

105