Luận án TS: Kỹ thuật rút gọn đặc trưng cho phân lớp dữ liệu - ĐH Công nghệ

ĐẠ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.04 LUẬN ÁN TIẾN SĨ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. NGUYỄN HÀ NAM 2. 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. Nguyễn Hà Nam và PGS.

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 i 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. Nguyễn Hà Nam và PGS.

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. Nguyễn Hà Nam và PGS. 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 ii TÓM TẮT Rút gọn đặc trưng ngày càng được sử dụng rộng rãi nhằm tăng hiệu năng cũng như giảm chi phí trong quá trình phân tích dữ liệu.

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

Có nhiều cách tiếp cận rút gọn đặc trưng khác nhau đã được giới thiệu, tuy nhiên các cách tiếp cận này vẫn tồn tại một số hạn chế khi áp dụng với các miền dữ liệu khác nhau. Chúng tôi đã đề xuất phương pháp lựa chọn đặc trưng có tên FRFE (Fast Recursive Feature Elimination) dựa trên hướng tiếp cận đóng gói (wrapper) với 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 đặ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 iii 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 iv MỤC LỤC LỜI CAM ĐOAN.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. TỔNG QUAN VỀ RÚT GỌN ĐẶC TRƯNG.1 Rút gọn đặc trưng.2 Lựa chọn đặc trưng.1 Mục tiêu của lựa chọn đặc trưng.2 Phân loại các kỹ thuật lựa chọn đặc trưng .3 Các thành phần chính của lựa chọn đặc trưng .4 Thủ tục lựa chọn đặc trưng .5 Các mô hình lựa chọn đặc trưng .3 Trích xuất đặc trưng .1 Mục tiêu của trích xuất đặc trưng .2 Phân loại các kỹ thuật trích xuất đặc trưng.4 Một số nghiên cứu về rút gọn đặc trưng .1 Hướng nghiên cứu về lựa chọn đặc trưng.2 Hướng nghiên cứu về trích xuất đặc trưng.3 Phân tích và đánh giá .5 Kết luận chương. KỸ THUẬT LỰA CHỌN ĐẶC TRƯNG TRONG BÀI TOÁN CHO ĐIỂM TÍN DỤNG.1 Bài toán cho điểm tín dụng .2 Các nghiên cứu liên quan.3 Phương pháp đề xuất.1 Sơ đồ hệ thống lựa chọn đặc trưng.2 Đề xuất hàm đánh giá và chiến lược tìm kiếm đặc trưng phù hợp .3 Cải tiến tốc độ xử lý bằng thư viện H20 .4 Thực nghiệm và kết quả.1 Thiết lập thực nghiệm .2 Dữ liệu thực nghiệm.3 Đánh giá hiệu năng phân lớp.4 Kết quả thực nghiệm .5 Kết luận chương. KỸ THUẬT TRÍCH XUẤT ĐẶC TRƯNG TRONG BÀI TOÁN PHÂN TÍCH DỮ LIỆU UNG THƯ .1 Bài toán phân tích dữ liệu ung thư .2 Các nghiên cứu liên quan.3 Phương pháp giải quyết.1 Sơ đồ hệ thống trích xuất đặc trưng .2 Hàm nhân tùy chọn cho PCA.3 Xây dựng hàm nhân tùy chọn .4 Thực nghiệm và kết quả.1 Thiết lập thực nghiệm .2 Dữ liệu thực nghiệm.3 Kết quả thực nghiệm .5 Kết luận chương.

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 vi DANH MỤC TỪ VIẾT TẮT Từ viết tắt Từ gốc Giải nghĩa ACO Ant Colony Optimization Tối ưu đàn kiến AUC Area under curve Diện tích dưới đường cong BG Bidirectional Generation Sinh tập con từ hai hướng CFS Correlation-based Feature Lựa chọn đặc trưng dựa trên Selection tương quan DL Deep Learning Học sâu DT Decision Tree Cây quyết định FCFS Fast Correlation-based Feature Lựa chọn đặc trưng dựa trên Selection tương quan nhanh FRFE Fast Recursive Feature Elimination Loại bỏ đặc trưng đệ quy nhanh GA Genetic Algorithm Thuật toán di truyền ICA Independent component analysis Phân tích thành phần độc lập IG Information Gain Độ lợi thông tin KDD Knowledge Discovery in Khám phá tri thức Databases k-NN k-Nearest Neighbors k-láng giềng gần nhất LDA Linear discriminant analysis Phân tích biệt thức tuyến tính LR Logistic Regression Hồi qui logistic MLP Multi-layer Perceptron Perceptron nhiều tầng mRMR minimum Redundancy Maximum Phù hợp nhiều nhất-dư thừa ít Relevance nhất OLTP Online transaction processing Xử lý giao dịch trực tuyến PCA Principal Component Analysis Phân tích thành phần chính PSO Particle Swarm Optimization Tối ưu hóa bầy đàn RF Random Forest Rừng ngẫu nhiên RG Random Generation Sinh tập con ngẫu nhiên SA Simulated Annealing Thuật toán mô phỏng tôi luyện SBE Sequential Backward Elimination Loại bỏ lùi tuần tự SBG Sequential Backward Generation Sinh tập con lùi tuần tự SBS Sequential Sackward Search Tìm kiếm lùi tuần tự SFG Sequential Forward Generation Sinh tập con tiến tuần tự vii SFS Sequential forward search Tìm kiếm tiến tuần tự SVD Singular Value Decomposition Phân tích giá trị riêng SVM Support Vector Machine Máy véc tơ hỗ trợ viii DANH MỤC HÌNH ẢNH Hình 1.1 Lựa chọn đặc trưng.2 Ba thành phần chính của lựa chọn đặc trưng[59] .3 Thủ tục lựa chọn đặc trưng[86] .4 Mô hình chọn lựa đặc trưng Lọc.5 Mô hình chọn lựa đặc trưng đóng gói.6 Trích xuất đặc trưng.1 Quy trình lựa chọn đặc trưng của bài toán cho điểm tín dụng.2 Sơ đồ khối của thuật toán lựa chọn đặc trưng theo hướng tiến .3 Sơ đồ khối của lựa chọn đặc trưng theo hướng lui .4 Chiến lược lựa chọn đặc trưng FRFE .5 Kiến trúc của thư viện H20.6 Phân lớp Random forest.7 Ví dụ về đường cong AUC [27] .8 Kiểm chứng chéo 5 lần .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.10 Danh sách các đặc trưng được sắp xếp theo độ đo Relief-F giảm dần.11 Danh sách các đặc trưng được sắp xếp theo độ tương quan giảm dần .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 .13 Độ chính xác phân lớp với bộ dữ liệu Đức.14 Độ chính xác phân lớp trên bộ dữ liệu Đức theo hướng quay lui.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 .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.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.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.