Nội dung

ĐẠ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 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.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 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 ............................................................................................................... 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.3 1.4 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 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 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 v 1.5 Kết luận chương ...................................................................................................... 31 CHƯƠNG 2. KỸ THUẬT LỰA CHỌN ĐẶC TRƯNG TRONG BÀI TOÁN CHO ĐIỂM TÍN DỤNG ............................................................................................... 32 2.1 Bài toán cho điểm tín dụng ..................................................................................... 32 2.2 Các nghiên cứu liên quan ........................................................................................ 35 2.3 Phương pháp đề xuất ............................................................................................... 37 2.4 2.5 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 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 Kết luận chương ...................................................................................................... 66 CHƯƠNG 3. KỸ THUẬT TRÍCH XUẤT ĐẶC TRƯNG TRONG BÀI TOÁN PHÂN TÍCH DỮ LIỆU UNG THƯ .................................................................. 67 3.1 Bài toán phân tích dữ liệu ung thư .......................................................................... 67 3.2 Các nghiên cứu liên quan ........................................................................................ 69 3.3 Phương pháp giải quyết ........................................................................................... 71 3.4 3.5 3.3.1 Sơ đồ hệ thống trích xuất đặc trưng .............................................................. 71 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 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 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 vi DANH MỤC TỪ VIẾT TẮT Từ viết tắt ACO AUC BG CFS DL DT FCFS FRFE GA ICA IG KDD k-NN LDA LR MLP mRMR OLTP PCA PSO RF RG SA SBE SBG SBS SFG Từ gốc Giải nghĩa 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 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 Sequential Backward Generation Sequential Sackward Search Sequential Forward Generation Tối ưu đàn kiến Diện tích dưới đường cong Sinh tập con từ hai hướng Lựa chọn đặc trưng dựa trên tương quan Học sâu Cây quyết định Lựa chọn đặc trưng dựa trên tương quan nhanh Loại bỏ đặc trưng đệ quy nhanh Thuật toán di truyền Phân tích thành phần độc lập Độ lợi thông tin Khám phá tri thức vii k-láng giềng gần nhất Phân tích biệt thức tuyến tính Hồi qui logistic Perceptron nhiều tầng Phù hợp nhiều nhất-dư thừa ít 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 Loại bỏ lùi tuần tự 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 Sequential forward search Singular Value Decomposition Support Vector Machine viii Tìm kiếm tiến tuần tự Phân tích giá trị riêng Máy véc tơ hỗ trợ