Luận án tiến sĩ: Nâng cao hiệu năng phân lớp dữ liệu bằng thuật toán SVM cải tiến - ĐH Huế 2023

ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THẾ CƯỜNG NÂNG CAO HIỆU NĂNG PHÂN LỚP DỮ LIỆU TRÊN CƠ SỞ CẢI TIẾN THUẬT TOÁN SVM LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH HUẾ - NĂM 2023 ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KHOA HỌC NGUYỄN THẾ CƯỜNG NÂNG CAO HIỆU NĂNG PHÂN LỚP DỮ LIỆU TRÊN CƠ SỞ CẢI TIẾN THUẬT TOÁN SVM NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ: 9.01 Người hướng dẫn khoa học: PGS. Huỳnh Thế Phùng HUẾ - NĂM 2023 Nâng cao hiệu năng phân lớp dữ liệu trên cơ sở cải tiến thuật toán SVM LỜI CAM ĐOAN Tôi xin cam đoan đề tài: "Nâng cao hiệu năng phân lớp dữ liệu trên cơ sở cải tiến thuật toán SVM " là một công trình nghiên cứu của riêng tôi, dưới sự hướng dẫn của PGS. Huỳnh Thế Phùng. Các số liệu sử dụng trong luận án là trung thực.

Các thuật toán được đề xuất là hoàn toàn mới, các kết quả thực nghiệm được thực hiện trên những bộ dữ liệu khách quan. Những kết quả của luận án chỉ được công bố trong các công trình liên quan đến luận án. Nghiên cứu sinh Nguyễn Thế Cường i Nâng cao hiệu năng phân lớp dữ liệu trên cơ sở cải tiến thuật toán SVM LỜI CẢM ƠN Luận án này sẽ không thể trở thành hiện thực nếu không có sự ủng hộ và giúp đỡ cả về tri thức lẫn tinh thần của rất nhiều người quan trọng trong cuộc đời tôi. Tôi xin bày tỏ lòng biết ơn sâu sắc đến quý Thầy, Cô khoa Công nghệ Thông tin và khoa Toán trường Đại học Khoa học, Đại học Huế, trường Đại học Sư phạm, Đại học Huế, những người đã dạy tôi không chỉ kiến thức mà còn là thái độ sống từ khi tôi tới Huế, đến bây giờ và mai sau nữa.

Xin chân thành cảm ơn phòng đào tạo sau Đại học trường Đại học Khoa học, Đại học Huế đã hướng dẫn tận tình thủ tục cần thiết để tôi hoàn thành hồ sơ Khoa học. Xin cảm ơn thành phố Huế, một nơi đặc biệt đối với tôi trên hành trình học làm người. Xin cảm ơn tất cả các anh, em và bạn bè sống tại Huế. Xin cảm ơn khoa Cơ bản trường Sĩ quan Thông tin đã tạo điều kiện về mặt thời gian để tôi hoàn thành quá trình học tập và nghiên cứu.

Nhân dịp này, tôi xin chân thành cảm ơn tất cả mọi người trong gia đình tôi, đã luôn ủng hộ cả về vật chất lẫn tinh thần và luôn động viên tôi lúc khó khăn. Đặc biệt, tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy Huỳnh Thế Phùng, người trực tiếp hướng dẫn tôi từ dấu chấm câu đến tổng thể, giúp tôi có một góc nhìn đúng đắn về khoa học và làm khoa học. Tôi cũng xin chân thành cảm ơn gia đình thầy đã luôn hỗ trợ về mọi mặt để tôi có điều kiện tốt nhất làm việc với thầy. Làm luận án này là cả một cuộc hành trình dài với rất nhiều cung bậc cảm xúc, quá trình này khiến tôi trở nên khiêm nhường, biết ơn những gì mình đang có và những người mình đã gặp.

Dành cho những ai biết đến đề tài này và đã từng động viên cho tôi, xin cảm ơn! TÁC GIẢ LUẬN ÁN Nghiên cứu sinh Nguyễn Thế Cường ii MỤC LỤC Lời cam đoan i Lời cảm ơn ii Danh mục các ký hiệu v Danh mục bảng biểu vii Danh mục hình vẽ viii Mở đầu 1 Chương 1. Cơ sở toán học của SVM 7 1.1 Hàm toàn phương .2 Bài toán quy hoạch toàn phương (QP) .3 Điều kiện tối ưu của bài toán QP .4 Bài toán đối ngẫu .5 Bài toán phân lớp dữ liệu .6 Hàm phân lớp tuyến tính .7 Siêu phẳng lề mềm .8 Hàm phân lớp phi tuyến .9 Hàm phân lớp có trọng số .10 Tiểu kết chương. Các biến thể của SVM 22 2.1 SVM xấp xỉ (PSVM) .2 PSVM thông qua các trị riêng suy rộng (GEPSVM) .3 SVM song sinh (TSVM) .1 Trường hợp tuyến tính .2 Trường hợp phi tuyến .4 TSVM dùng bình phương tối thiểu (LSTSVM) .5 SVM song sinh có cấu trúc (S-TSVM) .6 Tiểu kết chương. Phương pháp lớp đối cụm 41 3.1 SVM có cấu trúc có trọng số (WS-SVM).

41 iii Nâng cao hiệu năng phân lớp dữ liệu trên cơ sở cải tiến thuật toán SVM 3.1 Trường hợp tuyến tính .2 Trường hợp phi tuyến .1 Tập dữ liệu giả 2 chiều .2 Các tập dữ liệu của UCI .2 Cải tiến SVM dùng bình phương tối thiểu (ILS-SVM) .1 Trường hợp tuyến tính .2 Trường hợp phi tuyến .1 Tập dữ liệu giả 2 chiều .2 Các tập dữ liệu UCI .3 Tiểu kết chương. Phương pháp cụm đối lớp 70 4.1 Biến đổi của S-TSVM .2 SVM dùng bình phương tối thiểu có trọng số (WLS-SVM) .1 Trường hợp tuyến tính .2 Trường hợp phi tuyến .1 Tập dữ liệu giả 2 chiều .2 Các tập dữ liệu UCI .4 Tiểu kết chương. 87 Kết luận 88 Danh mục các công trình khoa học của tác giả liên quan đến luận án 90 Tài liệu tham khảo 91 Phụ lục 96 iv Nâng cao hiệu năng phân lớp dữ liệu trên cơ sở cải tiến thuật toán SVM DANH MỤC CÁC KÝ HIỆU Ký hiệu Diễn giải ý nghĩa SVM Support Vector Machine PSVM SVM xấp xỉ (Proximal Support Vector Machine) GEPSVM SVM xấp xỉ thông qua các trị riêng suy rộng (Proximal Support Vector Machine via Generalized Eigenvalues) TSVM SVM song sinh (Twin Support Vector Machine) LSTSVM SVM song sinh dùng bình phương tối thiểu (Least Square Twin Support Vector Machine) S-TSVM SVM song sinh có cấu trúc (Structural Twin Support Vector Ma- chine) WS-SVM SVM có cấu trúc có trọng số (Weighted Structural - Support Vector Machine) ILS-SVM Cải tiến của SVM dùng bình phương tối thiểu (Improvement Least Square - Suport Vector Machine) WLS-SVM SVM dùng bình phương tối thiểu có trọng số (Weighted Least Square - Support Vector Machine) CV Đánh giá chéo (Cross validation) SMW Công thức giảm chiều ma trận nghịch đảo của Sherman-Morison- Woodbury SLEs Hệ phương trình tuyến tính (Systems of Linear Equations) KKT Hệ điều kiện Karush - Kuhn - Tucker QP Quy hoạch toàn phương (Quadratic programming) ∥x∥ Chuẩn Euclide của véc-tơ x v Nâng cao hiệu năng phân lớp dữ liệu trên cơ sở cải tiến thuật toán SVM Ký hiệu Diễn giải ý nghĩa a, b,. Chữ cái thường biểu diễn số w, x,.

Chữ thường đậm chỉ véc-tơ cột C, A,. Chữ hoa đậm chỉ ma trận P(X, f ) Bài toán tối ưu tổng quát với hàm mục tiêu f và tập ràng buộc X B(x̄, ϵ) Hình cầu mở tâm x̄ bán kính ϵ sgn Hàm xác định dấu ∇Q(x) Gradient của hàm Q(x) ∇2 Q(x) Hessian của hàm Q(x) T Chuyển vị của một ma trận hay véc-tơ P A Ma trận hiệp phương sai của ma trận A wT x Tích vô hướng của véc-tơ w và véc-tơ x f(w,b) (x) Hàm phân lớp S(w,b) Mặt quyết định vi Nâng cao hiệu năng phân lớp dữ liệu trên cơ sở cải tiến thuật toán SVM DANH MỤC BẢNG BIỂU 3.1 Thời gian huấn luyện của WS-SVM với kernel tuyến tính .2 Thời gian huấn luyện của WS-SVM với kernel phi tuyến .3 WS-SVM tuyến tính đối với dữ liệu nhỏ của UCI .4 WS-SVM tuyến tính đối với dữ liệu lớn của UCI .5 WS-SVM phi tuyến đối với dữ liệu của UCI .6 Thời gian huấn luyện của ILS-SVM với kernel tuyến tính .7 Thời gian huấn luyện của ILS-SVM với kernel phi tuyến .8 ILS-SVM tuyến tính đối với dữ liệu nhỏ của UCI .9 ILS-SVM tuyến tính đối với dữ liệu lớn của UCI .10 ILS-SVM phi tuyến đối với dữ liệu của UCI .1 Thời gian huấn luyện của WLS-SVM với kernel tuyến tính .2 Thời gian huấn luyện của WLS-SVM với kernel phi tuyến .3 WLS-SVM tuyến tính đối với dữ liệu nhỏ của UCI .4 WLS-SVM tuyến tính đối với dữ liệu lớn của UCI .5 WLS-SVM phi tuyến đối với dữ liệu của UCI. 86 vii Nâng cao hiệu năng phân lớp dữ liệu trên cơ sở cải tiến thuật toán SVM DANH MỤC HÌNH VẼ 1.1 Mặt quyết định phi tuyến .2 Mặt quyết định tuyến tính .3 Mặt quyết định chính tắc .4 Siêu phẳng lề mềm .5 Dữ liệu phi tuyến .6 Dữ liệu phi tuyến trên không gian mới .1 SVM lề mềm .2 SVM xấp xỉ (PSVM) .3 PSVM thông qua các trị riêng suy rộng (GEPSVM) .4 SVM song sinh (TSVM) .6 Độ chi tiết cấu trúc .7 TSVM có cấu trúc (S-TSVM) .3 Dữ liệu giả 2 chiều .1 S-TSVM trường hợp dữ liệu có cấu trúc đơn giản .2 S-TSVM trường hợp dữ liệu có cấu trúc phức tạp .3 WLS-SVM trường hợp dữ liệu có cấu trúc đơn giản .4 WLS-SVM trường hợp dữ liệu có cấu trúc phức tạp. 75 viii Nâng cao hiệu năng phân lớp dữ liệu trên cơ sở cải tiến thuật toán SVM MỞ ĐẦU 1.

Lý do chọn đề tài Mục tiêu của phân loại mẫu là tìm ra một quy tắc, dựa trên quan sát bên ngoài, để gán một đối tượng vào chính xác một lớp nào đó. Nhiều thuật toán đã được xây dựng để nhận diện các mẫu khác nhau trên cơ sở các mẫu đã được huấn luyện. Một kỹ thuật phân loại có giám sát nổi tiếng là thuật toán Support Vector Machine (SVM) [52]. Đối với nhiều ứng dụng, phương pháp SVM, độc lập hoặc kết hợp với những phương pháp khác, mang lại hiệu suất vượt trội so với các lựa chọn học máy khác.

Nói chung, SVM hoạt động rất tốt trong thực tế và cho ra lời giải toàn cục. Đầu tiên, SVM giải quyết bài toán với tập dữ liệu tách được tuyến tính, sau đó đến trường hợp tập dữ liệu có chồng lấn hoặc phức tạp hơn khi dữ liệu các lớp trộn lẫn vào nhau. Trong tất cả các trường hợp, phương pháp nhân tử Lagrange [41] vẫn tỏ ra hiệu quả để đưa bài toán về dạng tường minh nhất mà từ đó có thể đưa ra thuật toán giải. Sở dĩ thuật toán SVM được quan tâm nghiên cứu và cải tiến không ngừng là bởi những ứng dụng rộng rãi của nó trong các bài toán thực tế [38, 1, 49, 51, 6, 34].

Chẳng hạn các bài toán về nhận dạng hình ảnh, chữ viết, âm thanh, sắc thái giọng nói. mà có thể có ích trong việc xây dựng các ứng dụng cho các thiết bị thông minh. Nhận thấy SVM vẫn đang là một vấn đề thời sự của cộng đồng nghiên cứu học thuật vì vậy chúng tôi chọn đề tài “Nâng cao hiệu năng phân lớp dữ liệu trên cơ sở cải tiến thuật toán SVM” để nghiên cứu.