Luận án 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

ĐẠ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.48.01.01 Người hướng dẫn khoa học: PGS.TS. 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.TS. 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Bài toán quy hoạch toàn phương (QP) . . . . . . . . . . . . . . . . . . 7 1.3 Điều kiện tối ưu của bài toán QP . . . . . . . . . . . . . . . . . . . . . 8 1.4 Bài toán đối ngẫu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.5 Bài toán phân lớp dữ liệu . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.6 Hàm phân lớp tuyến tính . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.7 Siêu phẳng lề mềm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.8 Hàm phân lớp phi tuyến . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.9 Hàm phân lớp có trọng số . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.10 Tiểu kết chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Chương 2. Các biến thể của SVM 22 2.1 SVM xấp xỉ (PSVM) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.2 PSVM thông qua các trị riêng suy rộng (GEPSVM) . . . . . . . . . . . 26 2.3 SVM song sinh (TSVM) . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.3.1 Trường hợp tuyến tính . . . . . . . . . . . . . . . . . . . . . . . 28 2.3.2 Trường hợp phi tuyến . . . . . . . . . . . . . . . . . . . . . . . 31 2.4 TSVM dùng bình phương tối thiểu (LSTSVM) . . . . . . . . . . . . . . 32 2.5 SVM song sinh có cấu trúc (S-TSVM) . . . . . . . . . . . . . . . . . . 34 2.6 Tiểu kết chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 Chương 3. 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.1 Trường hợp tuyến tính . . . . . . . . . . . . . . . . . . . . . . . 44 3.1.2 Trường hợp phi tuyến . . . . . . . . . . . . . . . . . . . . . . . 47 3.1.3 Thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.1.3.1 Tập dữ liệu giả 2 chiều . . . . . . . . . . . . . . . . . . 50 3.1.3.2 Các tập dữ liệu của UCI . . . . . . . . . . . . . . . . . 52 3.2 Cải tiến SVM dùng bình phương tối thiểu (ILS-SVM) . . . . . . . . . . 57 3.2.1 Trường hợp tuyến tính . . . . . . . . . . . . . . . . . . . . . . . 58 3.2.2 Trường hợp phi tuyến . . . . . . . . . . . . . . . . . . . . . . . 60 3.2.3 Thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.2.3.1 Tập dữ liệu giả 2 chiều . . . . . . . . . . . . . . . . . . 63 3.2.3.2 Các tập dữ liệu UCI . . . . . . . . . . . . . . . . . . . 64 3.3 Tiểu kết chương . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 Chương 4. Phương pháp cụm đối lớp 70 4.1 Biến đổi của S-TSVM . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.2 SVM dùng bình phương tối thiểu có trọng số (WLS-SVM) . . . . . . . 72 4.2.1 Trường hợp tuyến tính . . . . . . . . . . . . . . . . . . . . . . . 75 4.2.2 Trường hợp phi tuyến . . . . . . . . . . . . . . . . . . . . . . . 77 4.3 Thực nghiệm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 4.3.1 Tập dữ liệu giả 2 chiều . . . . . . . . . . . . . . . . . . . . . . . 81 4.3.2 Các tập dữ liệu UCI . . . . . . . . . . . . . . . . . . . . . . . . 82 4.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) ∇2Q(x) Hessian của hàm Q(x) T Chuyển vị của một ma trận hay véc-tơ∑ A Ma trận hiệp phương sai của ma trận A wTx 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 . . . . . . . . 52 3.2 Thời gian huấn luyện của WS-SVM với kernel phi tuyến . . . . . . . . 52 3.3 WS-SVM tuyến tính đối với dữ liệu nhỏ của UCI . . . . . . . . . . . . 54 3.4 WS-SVM tuyến tính đối với dữ liệu lớn của UCI . . . . . . . . . . . . . 55 3.5 WS-SVM phi tuyến đối với dữ liệu của UCI . . . . . . . . . . . . . . . 56 3.6 Thời gian huấn luyện của ILS-SVM với kernel tuyến tính . . . . . . . . 63 3.7 Thời gian huấn luyện của ILS-SVM với kernel phi tuyến . . . . . . . . 64 3.8 ILS-SVM tuyến tính đối với dữ liệu nhỏ của UCI . . . . . . . . . . . . 66 3.9 ILS-SVM tuyến tính đối với dữ liệu lớn của UCI . . . . . . . . . . . . . 67 3.10 ILS-SVM phi tuyến đối với dữ liệu của UCI . . . . . . . . . . . . . . . 68 4.1 Thời gian huấn luyện của WLS-SVM với kernel tuyến tính . . . . . . . 81 4.2 Thời gian huấn luyện của WLS-SVM với kernel phi tuyến . . . . . . . . 82 4.3 WLS-SVM tuyến tính đối với dữ liệu nhỏ của UCI . . . . . . . . . . . . 84 4.4 WLS-SVM tuyến tính đối với dữ liệu lớn của UCI . . . . . . . . . . . . 85 4.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 . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.2 Mặt quyết định tuyến tính . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.3 Mặt quyết định chính tắc . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.4 Siêu phẳng lề mềm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.5 Dữ liệu phi tuyến . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.6 Dữ liệu phi tuyến trên không gian mới . . . . . . . . . . . . . . . . . . 18 2.1 SVM lề mềm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.2 SVM xấp xỉ (PSVM) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.3 PSVM thông qua các trị riêng suy rộng (GEPSVM) . . . . . . . . . . . 27 2.4 SVM song sinh (TSVM) . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.5 LSTSVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.6 Độ chi tiết cấu trúc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.7 TSVM có cấu trúc (S-TSVM) . . . . . . . . . . . . . . . . . . . . . . . 37 3.1 S-TSVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 3.2 WS-SVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.3 Dữ liệu giả 2 chiều . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.4 ILS-SVM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.1 S-TSVM trường hợp dữ liệu có cấu trúc đơn giản . . . . . . . . . . . . 72 4.2 S-TSVM trường hợp dữ liệu có cấu trúc phức tạp . . . . . . . . . . . . 73 4.3 WLS-SVM trường hợp dữ liệu có cấu trúc đơn giản . . . . . . . . . . . 74 4.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. 2. Động lực nghiên cứu Trong quá trình nghiên cứu SVM và các hướng phát triển, có thể kể đến một vài biến thể tiêu biểu của SVM như: SVM xấp xỉ (PSVM) [16, 18, 30], SVM xấp xỉ thông qua trị riêng suy rộng (GEPSVM) [32, 33, 15, 21], SVM song sinh (TSVM) [20, 22, 37, 57], SVM song sinh có cấu trúc (S-TSVM) [43, 55, 56], SVM song sinh dùng bình phương tối thiểu (LSTSVM) [27, 28, 44, 58, 35, 42]. 1 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 PSVM [16] có cách tiếp cận tương tự như SVM tiêu thuẩn bằng cách tìm siêu phẳng tách với lề lớn nhất, nhưng PSVM chú trọng tới việc tìm hai siêu phẳng song song tương ứng với hai lớp dữ liệu sao cho các điểm trên mỗi lớp dữ liệu tụ tập quanh nó và hai siêu phẳng này tạo ra lề lớn nhất có thể. Ưu điểm của PSVM là giải bài toán quy hoạch toàn phương (QP) lồi chặt với ràng buộc đẳng thức, điều này tăng tính ổn định của thuật toán. Tuy nhiên việc tìm hai siêu phẳng song song dẫn tới khả năng mở rộng của PSVM bị hạn chế. Tiếp cận bài toán phân loại hai lớp dữ liệu dưới một góc nhìn khác, GEPSVM [33] đã tìm hai siêu phẳng không nhất thiết song song sao cho, mỗi siêu phẳng là gần với một lớp dữ liệu và xa lớp còn lại nhất có thể. Hai siêu phẳng này được tạo bởi các véc-tơ riêng của các trị riêng nhỏ nhất trong hai bài toán tìm trị riêng suy rộng. Vì GEPSVM giải hai bài toán tối ưu không có ràng buộc nên độ chính xác và khả năng mở rộng chưa thực sự tốt. TSVM [20] cũng có cách tiếp cận tương tự GEPSVM, với mục đích là tìm hai siêu phẳng không nhất thiết song song để tách hai lớp dữ liệu. Tuy nhiên công thức toán học của TSVM là hoàn toàn khác với GEPSVM. TSVM được giải dựa vào hai bài toán đối ngẫu Lagrange và dùng hai siêu phẳng để tách hai lớp dữ liệu, TSVM đã tỏ ra hiệu quả hơn SVM, PSVM, GEPSVM cả về thời gian tính toán và khả năng mở rộng. Tương tự như các thuật toán trên, LSTSVM [27] cũng tiếp cận bài toán phân loại nhị phân bằng cách tìm hai siêu phẳng không nhất thiết song song, sao cho mỗi siêu phẳng là gần với một lớp và cách xa lớp còn lại nhất có thể. Tuy nhiên, LSTSVM không giải hai bài toán đối ngẫu như cách mà TSVM thực hiện. Thay vào đó, bằng cách thay thế các ràng buộc bất đẳng thức trong TSVM bởi các ràng buộc đẳng thức, LSTSVM giải hai hệ phương trình tuyến tính (SLEs) để tìm ra hai siêu phẳng. Nhờ chiến lược đó, thời gian huấn luyện trong tất cả các trường hợp của LSTSVM tỏ ra nhanh vượt trội so với thời gian huấn luyện của các thuật toán ở trên. S-TSVM [43] có chiến lược tìm hai siêu phẳng tương tự như TSVM. Bên cạnh đó, S-TSVM khai thác đầy đủ thông tin cấu trúc của từng cụm trong các lớp vào huấn luyện mô hình nhằm xây dựng bộ phân loại. Cách tiếp cận này khá 2 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 hợp lí, bởi vì dữ liệu hai lớp trong thực tế thường có xu hướng phân phối khác nhau. Thậm chí trong cùng một lớp dữ liệu cũng có thể bao gồm nhiều cụm mà mỗi cụm có một phân phối riêng biệt. Chẳng hạn như, chúng ta xét bài toán phân loại hoa quả thuộc lớp "da trơn" hay "da xù xì" với tập dữ liệu bao gồm 5 cụm: Xoài, Mít, Dứa, Táo, Nho. Dĩ nhiên rằng, dữ liệu trong lớp "da trơn" sẽ gồm 3 cụm là Xoài, Táo, Nho, trong khi dữ liệu trong lớp "da xù xì" gồm 2 cụm là Mít, Dứa. Trong trường hợp dữ liệu có cấu trúc đơn giản, khi mỗi lớp chỉ bao gồm một cụm dữ liệu, hay khi mỗi lớp bao gồm nhiều cụm có xu hướng phân phối tương tự nhau, SVM và các biến thể tỏ ra khá hiệu quả. Tuy nhiên, trong trường hợp dữ liệu có cấu trúc phức tạp, nơi mà mỗi lớp chứa nhiều cụm, mỗi cụm có xu hướng phân phối riêng biệt thì SVM và các biến thể chưa khai thác đầy đủ thông tin về cấu trúc của từng cụm, thông tin về số lượng điểm dữ liệu trong mỗi cụm. Điều này có thể làm ảnh hưởng đến hiệu năng (độ chính xác, thời gian huấn luyện) phân lớp dữ liệu. Những vấn đề nêu trên chính là động lực để luận án tập trung nghiên cứu, cải tiến và đề xuất mới các giải pháp nâng cao hiệu năng phân lớp dữ liệu đối với dữ liệu có cấu trúc phức tạp. 3. Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu là các thuật toán học máy, bài toán phân lớp dữ liệu. Phạm vi nghiên cứu của đề tài tập trung vào học máy có giám sát, cụ thể là nghiên cứu và đề xuất các cải tiến của thuật toán SVM đối với loại dữ liệu có cấu trúc phức tạp, mỗi lớp bao gồm nhiều cụm, mỗi cụm có xu hướng phân phối khác nhau và có số lượng điểm dữ liệu khác nhau. 4. Mục tiêu của luận án Như đã nói, đối với bài toán phân loại nhị phân trong thực tế, hai lớp dữ liệu thường có xu hướng phân phối khác nhau. Phức tạp hơn, mỗi lớp dữ liệu gồm nhiều cụm có phân phối khác nhau. Cách tiếp cận dùng một siêu phẳng hay dùng hai siêu phẳng để phân loại còn nhiều hạn chế. Xuất phát từ đó, mục tiêu chính của luận án là đề xuất các phương pháp mới nhằm nâng cao hiệu năng 3 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 phân lớp dữ liệu (độ chính xác trong phân lớp, thời gian huấn luyện) đối với dữ liệu có cấu trúc phức tạp, trên cơ sở cải tiến thuật toán SVM. Cụ thể, cần khai thác được thông tin về cấu trúc của từng cụm dữ liệu và thông tin về số lượng điểm dữ liệu của mỗi cụm trong các lớp. 5. Phương pháp nghiên cứu và giải quyết Chúng tôi tập trung tiếp cận trên một số phương pháp chính như sau: ˆ Phương pháp tổng hợp và phân tích: Tổng hợp các công bố liên quan đến SVM. Phân tích, đánh giá ưu và khuyết điểm của một số mô hình đã công bố để làm cơ sở cho việc cải tiến hoặc đề xuất mới. ˆ Các phương pháp toán học Phương pháp nhân tử Lagrange, hệ KKT (Karush - Kuhn - Tucker): tìm nghiệm của bài toán QP lồi với các ràng buộc bất đẳng thức thông qua nghiệm của bài toán đối ngẫu của nó. Phương pháp dùng bình phương tối thiểu: tìm nghiệm của bài toán QP lồi với hàm mục tiêu toàn phương và các ràng buộc đẳng thức, bằng cách thay trực tiếp các ràng buộc vào hàm mục tiêu và giải hệ các phương trình tuyến tính. ˆ Các phương pháp xử lý với dữ liệu có nhiều cụm Khai thác lớp-đối-cụm: tìm (l+k) siêu phẳng, ở đó mỗi siêu phẳng là gần với một lớp và cách xa một cụm của lớp còn lại. Khai thác cụm-đối-lớp: tìm (k+ l) siêu phẳng, ở đó mỗi siêu phẳng là gần với một cụm của lớp này và cách xa lớp khác. ˆ Phương pháp thực nghiệm khoa học: sử dụng ngôn ngữ lập trình Python để cài đặt các thuật toán đề xuất và các thuật toán đã công bố. Thực hiện trên các tập dữ liệu giả để mô phỏng, trên các tập dữ liệu mở của UCI [14] để so sánh kết quả về thời gian thực hiện và độ chính xác phân loại giữa các thuật toán. Các chương trình nguồn được đưa lên nguồn lưu trữ mở GitHub và đã được thử nghiệm nhiều lần (có đường dẫn theo từng thuật toán). 4 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 6. Ý nghĩa khoa học và thực tiễn Ý nghĩa khoa học Những đóng góp chính của luận án về khoa học: ˆ Đề xuất các thuật toán phân lớp nhị phân với dữ liệu có cấu trúc phức tạp, sử dụng chiến lược lớp-đối-cụm, tìm nghiệm toàn cục bằng phương pháp đối ngẫu hoặc phương pháp bình phương tối thiểu. Việc giải các bài toán QP cỡ lớn được thay thế bởi các bài toán QP có cỡ nhỏ hơn. ˆ Đề xuất các thuật toán phân lớp nhị phân với dữ liệu có cấu trúc phức tạp, sử dụng chiến lược cụm-đối-lớp, khai thác thông tin cấu trúc của từng cụm trong mỗi lớp và thông tin về số lư