Luận án tiến sĩ 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

ĐẠ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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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ằngngô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 iii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 iv LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com MỤC LỤC LỜI CAM ĐOAN. III MỤC LỤC. V DANH MỤC TỪ VIẾT TẮT. VIII DANH MỤC HÌNH ẢNH.

X DANH MỤC BẢNG BIỂU. XII 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á. 30 v LUAN VAN CHAT LUONG download : add luanvanchat@agmail.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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com vii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 Databases Khám phá tri thức 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ự SFS Sequential forward search Tìm kiếm tiến tuần tự viii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com SVD Singular Value Decomposition Phân tích giá trị riêng SVM Support Vector Machine Máy véc tơ hỗ trợ ix LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 .