intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Luận án Tiến sĩ Khoa học máy tính: 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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:136

Thêm vào BST
Báo xấu
20
lượt xem 4
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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" được hoàn thành với mục tiêu nhằm đề xuất các phương pháp mới nhằm nâng cao hiệu năng 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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án Tiến sĩ Khoa học máy tính: 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

  1. ĐẠ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
  2. ĐẠ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
  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 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
  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 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
  5. 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
  6. 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
  7. 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
  8. 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ơ 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
  9. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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ượng điểm dữ liệu trong mỗi cụm. Các thuật toán 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. Ý nghĩa thực tiễn ˆ Kết quả nghiên cứu nếu được áp dụng trên thực tế có thể giải quyết được các bài toán phân lớp với dữ liệu có cấu trúc phức tạp, hay dữ liệu không cân bằng (một lớp chiếm đa số dữ liệu khoảng 90%, một lớp chiếm thiểu số dữ liệu khoảng 10%). ˆ Luận án có thể được sử dụng làm tài liệu tham khảo cho các sinh viên đại học và học viên cao học ngành công nghệ thông tin thực hiện đề tài về phân lớp dữ liệu. 7. Bố cục của luận án Ngoài phần mở đầu và kết luận, luận án được chia thành 4 chương: ˆ Chương 1: là kiến thức bổ trợ về bài toán Quy hoạch toàn phương (QP) và trình bày chi tiết về nền tảng toán học của thuật toán SVM cho các trường hợp từ đơn giản đến phức tạp. ˆ Chương 2: là các cải tiến tiêu biểu của SVM được trình bày trong luận án một cách ngắn gọn. Chương này tập trung vào các kết quả đã công bố, có cách tiếp cận sử dụng hai siêu phẳng để phân loại hai lớp dữ liệu. ˆ Chương 3: trình bày hai phương pháp mới: SVM có cấu trúc có trọng số 5
  16. 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 (được gọi là WS-SVM) và Cải tiến của SVM dùng bình phương tối thiểu (được gọi là ILS-SVM), sử dụng chiến lược lớp-đối-cụm. ˆ Chương 4: là chiến lược cụm-đối-lớp, cùng với thuật toán mới: SVM dùng bình phương tối thiểu có trọng số (được gọi là WLS-SVM). Bên cạnh đó, các cài đặt của các thuật toán và thu thập dữ liệu được trình bày trong phần phụ lục của luận án. Các kết quả của luận án được công bố trong 5 công trình khoa học được đăng trong các hội nghị và tạp chí chuyên ngành trong và ngoài nước. Trong đó có 01 bài đăng trong chuyên san hội thảo quốc gia, 01 bài đăng ở kỉ yếu hội thảo quốc tế, 01 bài đăng ở tạp chí Khoa học và Công nghệ, Đại học Khoa học, Đại học Huế, 01 bài đăng ở tạp chí Kĩ thuật và Công nghệ, Đại học Huế, 01 bài đăng ở tạp chí Tin học và Điều khiển. 6
  17. 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 CHƯƠNG 1. CƠ SỞ TOÁN HỌC CỦA SVM Trong chương này, trước tiên chúng tôi cung cấp các khái niệm và kết quả cơ bản về toán mà sẽ được dùng xuyên suốt nội dung luận án. Cụ thể đó là hàm toàn phương, bài toán quy hoạch toàn phương (QP), điều kiện tối ưu của bài toán QP, bài toán đối ngẫu của bài toán QP lồi. Tiếp theo là trình bày về cơ sở toán học của SVM cho các trường hợp từ đơn giản đến phức tạp. 1.1. Hàm toàn phương Trong suốt luận án này hàm toàn phương luôn được trình bày dưới dạng chuẩn như sau: 1 Q(x) = xT Gx + gT x + α; x ∈ Rn , (1.1) 2 trong đó, G ∈ Rn×n là một ma trận vuông đối xứng, g, x ∈ Rn là các véc-tơ cột và T α ∈ R là một số thực. Kí hiệu để chỉ chuyển vị của một ma trận hay véc-tơ. Hàm toàn phương (1.1) có gradient và Hessian được tính trực tiếp như sau: ∇Q(x) = Gx + g; ∇2 Q(x) = G. (1.2) Do đó, hàm Q lồi khi và chỉ khi G là ma trận nửa xác định dương. Hơn nữa, khi G xác định dương thì Q là hàm lồi chặt. 1.2. Bài toán quy hoạch toàn phương (QP) Bài toán quy hoạch toàn phương là một dạng đơn giản của bài toán tối ưu. Cụ thể, đó là bài toán với hàm mục tiêu là hàm toàn phương và các ràng buộc tuyến tính. Bài toán quy hoạch toàn phương, kí hiệu (QP), có dạng tổng quát như sau:  Q(x) = 1 xT Gx + gT x + α −→ min,  2     (QP) : aT x ≥ bi , i ∈ I := {1, 2, . . . , m}, (1.3)  i    T cj x = dj , j ∈ J := {1, 2, . . . , k},  7
  18. 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 trong đó G là ma trận vuông đối xứng cấp n; g, ai , cj là các véc-tơ, α, bi , dj là các số thực, còn I và J là tập hợp hữu hạn các chỉ số: I = {1, . . . , m}, J = {1, . . . , k}. Khi G là ma trận nửa xác định dương, tức hàm mục tiêu Q lồi, ta có bài toán quy hoạch toàn phương lồi. Ta có thể biểu diễn bài toán gọn hơn dưới dạng ma trận. Cụ thể, đặt A = [a1 , a2 , . . . , am ]T là ma trận cấp m × n, gồm m véc-tơ hàng aT , C = [c1 , c2 , . . . , ck ]T i là ma trận cấp k × n, gồm k véc-tơ hàng cT , b ∈ Rm và d ∈ Rk là các véc-tơ cột với j các thành phần bi và dj . Lúc đó, bài toán có thể viết lại dưới dạng ma trận như sau:  Q(x) = 1 xT Gx + gT x + α −→ min,  2     (QP) : Ax ≥ b,     Cx = d.  1.3. Điều kiện tối ưu của bài toán QP Định lý 1.1 (Điều kiện tối ưu ([48], tr. 412)). (a) Giả sử x∗ là nghiệm của bài toán QP được cho ở (1.3). Khi đó tồn tại các bộ hệ số λ∗ = (λ∗ , . . . , λ∗ ) ∈ Rm , µ∗ = (µ∗ , . . . , µ∗ ) ∈ Rk thoả mãn: 1 m 1 k  m k λ∗ ai + µ∗ cj ,  ∗ Gx + g =    i j    i=1 j=1    T ∗ ai x ≥ bi , λ∗ ≥ 0, i i ∈ I, (1.4)   ∗ T ∗ λi (ai x − bi ) = 0,   i ∈ I,      T ∗ c x = dj , j j ∈ J. Hệ (1.4) được gọi là hệ KKT (Karush − Kuhn − T ucker) của bài toán quy hoạch toàn phương (1.3), x∗ được gọi là điểm KKT, và các hệ số λ∗ , µ∗ được gọi là các nhân tử Lagrange tương ứng với x∗ . (b) Nếu G là ma trận nửa xác định dương, và nếu x∗ là một điểm KKT cùng với các nhân tử Lagrange λ∗ , µ∗ , thì x∗ cũng là nghiệm của bài toán QP. Như vậy, nếu QP là bài toán quy hoạch toàn phương lồi, thì việc tìm nghiệm của bài toán tương đương với việc tìm điểm KKT của nó. 8
  19. 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 Chú ý rằng, hệ KKT có thể viết lại dưới dạng ma trận như sau:  Gx∗ + g = AT λ∗ + CT µ∗ ,      Ax ≥ b, λ∗ ≥ 0,   ∗ (1.5)  ∗T λ (Ax∗ − b) = 0,       ∗ Cx = d. 1.4. Bài toán đối ngẫu Mục này trình bày cách lập bài toán đối ngẫu của quy hoạch toàn phương lồi. Đối với một số lớp bài toán thực tiễn ta có thể khai thác cấu trúc đặc biệt của bài toán đối ngẫu để giải bài toán ban đầu một cách hiệu quả hơn. Để đơn giản ta xét bài toán QP với α = 0. Với mỗi bài toán quy hoạch toàn phương lồi ta xét bài toán đối ngẫu tương ứng. Giả sử bài toán QP ở (1.3) lồi, tức G là ma trận nửa xác định dương. Ta có hàm Lagrange của bài toán là 1 L(x, λ, µ) = xT Gx + gT x − λT (Ax − b) − µT (Cx − d), (1.6) 2 với các biến (x, λ, µ) ∈ Rn × Rm × Rk . Lúc này, điểm KKT x∗ cùng với các nhân tử + Lagrange λ∗ , µ∗ chính là điểm yên ngựa (x∗ , λ∗ , µ∗ ) của hàm L và thỏa mãn hệ KKT (1.5), hay thỏa mãn điều kiện tối ưu (Định lí 1.1). Thực ra, điều kiện KKT (1.5) chính là: ∇x L = 0, ∇λ L ≥ 0, λ ≥ 0, λ∇λ L = 0, ∇µ L = 0 Bài toán QP lúc đó tương đương với bài toán minimax sau: inf sup L(x, λ, µ). (1.7) x∈Rn (λ,µ)∈Rm ×Rk + Vì vậy, Bài toán đối ngẫu của QP sẽ là sup n inf L(x, λ, µ). (1.8) (λ,µ)∈Rm ×Rk x∈R + Với giả thiết G là nửa xác định dương, với mỗi (λ, µ), ta giải bài toán inf L(x, λ, µ), x∈Rn 9
  20. 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 theo cách sau. Từ phương trình dừng ∇x L(x, λ, µ) = Gx + g − AT λ − CT µ = 0, giải ra ta được nghiệm x (phụ thuộc (λ, µ)) thoả mãn Gx = AT λ + CT µ − g hay g = AT λ + CT µ − Gx. Thay vào hàm Lagrange ta có 1 L(x, λ, µ) = xT Gx + gT x − λT (Ax − b) − µT (Cx − d) 2 1 T = x Gx + (λT A + µT C − xT G)x − λT (Ax − b) − µT (Cx − d) 2 1 = − xT Gx + λT b + µT d. 2 Vì vậy bài toán đối ngẫu chính là:  − x Gx + λT b + µT d −→ max,  1 T  2    m k (1.9) λ ∈ R+ , µ ∈ R ,   Gx = AT λ + CT µ − g.   Nếu G là xác định dương thì từ Gx = AT λ + CT µ − g suy ra x = G−1 (AT λ + CT µ − g), nên hàm mục tiêu của (1.9) là 1 1 − xT Gx + λT b + µT d = − (AT λ + CT µ − g)T G−1 (AT λ + CT µ − g) + λT b + µT d. 2 2 Do đó, bài toán đối ngẫu (1.9) trở thành  − (A λ + CT µ − g)T G−1 (AT λ + CT µ − g) + λT b + µT d −→ max,  1 T 2 λ ∈ Rm ; µ ∈ Rk .  + Đây cũng là một bài toán quy hoạch toàn phương lồi, với dạng đơn giản hơn nhiều bài toán QP ban đầu. Phần sau của chương, luận án trình bày chi tiết về cơ sở toán học của thuật toán SVM cho bài toán phân loại hai lớp dữ liệu. 10
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.11: Bộ Luận Văn Tốt Nghiệp Chuyên Ngành Tài Chính Ngân Hàng
172 tài liệu
843 lượt tải
THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2