Bài giảng Nhập môn Học máy và Khai phá dữ liệu: Chương 9 - Nguyễn Nhật Quang

Bài giảng Nhập môn Học máy và Khai phá dữ liệu: Chương 9, chương này cung cấp cho học viên những nội dung về: phân lớp; máy vectơ hỗ trợ (Support vector machine); mặt siêu phẳng phân tách; mặt siêu phẳng có lề cực đại; dữ liệu phân tách được tuyến tính (SVM); tính toán mức lề;... Mời các bạn cùng tham khảo chi tiết nội dung bài giảng!
Nội dung trích xuất từ tài liệu:
Bài giảng Nhập môn Học máy và Khai phá dữ liệu: Chương 9 - Nguyễn Nhật Quang Nhập môn Học máy và Khai phá dữ liệu (IT3190) Nguyễn Nhật Quang quang.nguyennhat@hust.edu.vn Trường Đại học Bách Khoa Hà Nội Viện Công nghệ thông tin và truyền thông Năm học 2020-2021 Nội dung môn học: Giới thiệu về Học máy và Khai phá dữ liệu Tiền xử lý dữ liệu Đánh giá hiệu năng của hệ thống Hồi quy Phân lớp Máy vectơ hỗ trợ (Support vector machine) Phân cụm Phát hiện luật kết hợp Nhập môn Học máy và Khai phá dữ liệu – Introduction to Machine learning and Data mining 2 Máy vectơ hỗ trợ - Giới thiệu (1) ◼ Máy vectơ hỗ trợ (Support vector machine - SVM) được đề cử bởi V. Vapnik và các đồng nghiệp của ông vào những năm 1970s ở Nga, và sau đó đã trở nên nổi tiếng và phổ biến vào những năm 1990s ◼ SVM là một phương pháp phân lớp tuyến tính (linear classifier), với mục đích xác định một siêu phẳng (hyperplane) để phân tách hai lớp của dữ liệu – ví dụ: lớp các ví dụ có nhãn dương (positive) và lớp các ví dụ có nhãn âm (negative) ◼ Các hàm nhân (kernel functions), cũng được gọi là các hàm biến đổi (transformation functions), được dùng cho các trường hợp phân lớp phi tuyến Nhập môn Học máy và Khai phá dữ liệu – Introduction to Machine learning and Data mining 3 Máy vectơ hỗ trợ - Giới thiệu (2) ◼ SVM có một nền tảng lý thuyết chặt chẽ – dựa trên nhiều định lý toán học ◼ SVM là một phương pháp tốt (phù hợp) đối với những bài toán phân lớp có không gian biểu diễn thuộc tính lớn – các đối tượng cần phân lớp được biểu diễn bởi một tập rất lớn các thuộc tính ◼ SVM đã được biết đến là một trong số các phương pháp phân lớp tốt nhất đối với các bài toán phân lớp văn bản (text/document classification) Nhập môn Học máy và Khai phá dữ liệu – Introduction to Machine learning and Data mining 4 Máy vectơ hỗ trợ - Giới thiệu (3) ◼ Các vectơ được ký hiệu bởi các chữ đậm nét! ◼ Biểu diễn tập r các ví dụ huấn luyện (training examples) {(x1, y1), (x2, y2), …, (xr, yr)}, ❑ xi là một vectơ đầu vào được biểu diễn trong không gian X  Rn ❑ yi là một nhãn lớp (giá trị đầu ra), yi  {1,-1} ❑ yi=1: lớp dương (positive); yi=-1: lớp âm (negative)  1 nêu  w  x i  + b  0 [Eq.1] ◼ Đối với một ví dụ xi: yi =  − 1 nêu  w  x i  + b  0 ◼ SVM xác định một hàm phân tách tuyến tính f(x) = w  x + b [Eq.2] ❑ w là vectơ trọng số các thuộc tính; b là một giá trị số thực Nhập môn Học máy và Khai phá dữ liệu – Introduction to Machine learning and Data mining 5 Mặt siêu phẳng phân tách ◼ Mặt siêu phẳng phân tách các ví dụ huấn luyện lớp dương và các ví dụ huấn luyện lớp âm: w  x + b = 0 ◼ Còn được gọi là ranh giới (bề mặt) quyết định ◼ Tồn tại nhiều mặt siêu phẳng phân tách. Chọn cái nào? [Liu, 2006] Nhập môn Học máy và Khai phá dữ liệu – Introduction to Machine learning and Data mining 6 Mặt siêu phẳng có lề cực đại ◼ SVM lựa chọn mặt siêu phẳng phân tách có lề (margin) lớn nhất ◼ Lý thuyết học máy đã chỉ ra rằng một mặt siêu phẳng phân tách như thế sẽ tối thiểu hóa giới hạn lỗi (phân lớp) mắc phải [Liu, 2006] Nhập môn Học máy và Khai phá dữ liệu – Introduction to Machine learning and Data mining 7 SVM – Dữ liệu phân tách được tuyến tính ◼ Giả sử rằng tập dữ liệu (tập các ví dụ huấn luyện) có thể phân tách được một cách tuyến tính ◼ Xét một ví dụ của lớp dương (x+,1) và một ví dụ của lớp âm (x-,-1) gần nhất đối với siêu phẳng phân tách H0 (+b=0) ◼ Định nghĩa 2 siêu phẳng lề song song với nhau ❑ H+ đi qua x+, và song song với H0 ❑ H- đi qua x-, và song song với H0 H+: +b = 1 [Eq.3] H-: +b = -1 sao cho: +b ≥ 1, nếu yi = 1 +b ≤ -1, nếu yi = -1 Nhập môn Học máy và Khai phá dữ liệu – Introduction to Machine learning and Data mining 8 Tính toán mức lề (1) ◼ Mức lề (margin) là khoảng cách giữa 2 siêu phẳng lề H+ và H-. Trong hình vẽ nêu trên: ❑ d+ là khoảng cách giữa H+ và H0 ❑ d- là khoảng cách giữa H- và H0 ❑ (d+ + d−) là mức lề ◼ Theo lý thuyết đại số vectơ, khoảng cách (trực giao) từ một điểm xi đến mặt siêu phẳng (w  x + b = 0) là: | w  xi  + b | [Eq.4] trong đó ||w|| là độ dài của w: || w || || w || =  w  w  = w1 + w2 + ... + wn 2 2 2 [Eq.5] Nhập môn Học máy và Khai phá dữ liệu – Introduction to Machine learning and Data mining 9 Tính toán mức lề (2) ◼ Tính toán d+ – khoảng cách từ x+ đến (w  x + b = 0) ❑ Áp dụng các biểu thức [Eq.3-4]: | w  x+  + b | |1| 1 d+ = = = [Eq.6] || w || || w || || w || ◼ Tính toán d- – khoảng cách từ x- đến (w  x + b = 0) ❑ Áp dụng các biểu thức [Eq.3-4]: |  w  x −  + b | | −1 | 1 d− = = = [Eq.7] || w || || w || || w || ◼ Tính toán mức lề 2 ...