Bài giảng Nhập môn Học máy và Khai phá dữ liệu: Chương 10 - 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 10, chương này cung cấp cho học viên những nội dung về: phân cụm; bài toán phân cụm; phân cụm dựa trên phân tách - k-Means; phân cụm phân cấp - HAC; học có giám sát (Supervised learning); học không có giám sát (Unsupervised learning);... 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 10 - 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 Phân cụm Bài toán phân cụm Phân cụm dựa trên phân tách: k-Means Phân cụm phân cấp: HAC 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 Học có vs. không có giám sát ◼ Học có giám sát (Supervised learning) ❑ Tập dữ liệu (dataset) bao gồm các ví dụ, mà mỗi ví dụ được gắn kèm với một nhãn lớp/giá trị đầu ra mong muốn ❑ Mục đích là học (xấp xỉ) một giả thiết/hàm mục tiêu (vd: phân lớp, hồi quy) phù hợp với tập dữ liệu hiện có ❑ Hàm mục tiêu học được (learned target function) sau đó sẽ được dùng để phân lớp/dự đoán đối với các ví dụ mới ◼ Học không có giám sát (Unsupervised learning) ❑ Tập dữ liệu (dataset) bao gồm các ví dụ, mà mỗi ví dụ không có thông tin về nhãn lớp/giá trị đầu ra mong muốn ❑ Mục đích là tìm ra (xác định) các cụm/các cấu trúc/các quan hệ tồn tại trong tập dữ liệu hiện có Nhập môn Học máy và Khai phá dữ liệu – Introduction to Machine learning and Data mining 3 Phân cụm ◼ Phân cụm/nhóm (Clustering) là phương pháp học không có giám sát được sử dụng phổ biến nhất ❑ Tồn tại các phương pháp học không có giám sát khác, ví dụ: Lọc cộng tác (Collaborative filtering), Khai phá luật kết hợp (Association rule mining), ... ◼ Bài toán Phân cụm: ❑ Đầu vào: Một tập dữ liệu không có nhãn (các ví dụ không có nhãn lớp/giá trị đầu ra mong muốn) ❑ Đầu ra: Các cụm (nhóm) của các ví dụ ◼ Một cụm (cluster) là một tập các ví dụ: ❑ Tương tự với nhau (theo một ý nghĩa, đánh giá nào đó) ❑ Khác biệt với các ví dụ thuộc các cụm khác Nhập môn Học máy và Khai phá dữ liệu – Introduction to Machine learning and Data mining 4 Phân cụm – Ví dụ minh họa Các ví dụ được phân chia thành 3 cụm [Liu, 2006] Nhập môn Học máy và Khai phá dữ liệu – Introduction to Machine learning and Data mining 5 Phân cụm – Các thành phần ◼ Hàm tính khoảng cách (độ tương tự, độ khác biệt) ◼ Giải thuật phân cụm • Dựa trên phân tách (Partition-based clustering) • Dựa trên tích tụ phân cấp (Hierarchical clustering) • Bản đồ tự tổ thức (Self-organizing map – SOM) • Các mô hình hỗn hợp (Mixture models) • … ◼ Đánh giá chất lượng phân cụm (Clustering quality) • Khoảng cách/sự khác biệt giữa các cụm → Cần được cực đại hóa • Khoảng cách/sự khác biệt bên trong một cụm → Cần được cực tiểu hóa Nhập môn Học máy và Khai phá dữ liệu – Introduction to Machine learning and Data mining 6 Bài toán phân cụm: Đánh giá hiệu năng ◼ Làm sao để đánh giá hiệu quả phân cụm? ◼ External evaluation: Sử dụng thêm thông tin bên ngoài (ví dụ: nhãn lớp của mỗi ví dụ) ◼ Ví dụ: Accuracy, Precision,… ◼ Internal evaluation: Chỉ dựa trên các ví dụ được phân cụm (mà không có thêm thông tin bên ngoài) ◼ Rất thách thức! ◼ Là trọng tâm được trình bày tiếp theo Nhập môn Học máy và Khai phá dữ liệu – Introduction to Machine learning and Data mining 7 Internal evaluation: Nguyên tắc ◼ Sự gắn kết (compactness/coherence) ◼ Khoảng cách giữa các ví dụ trong cùng cụm (intra-cluster distance) ◼ Sự tách biệt (separation) ◼ Khoảng cách giữa các ví dụ thuộc 2 cụm khác nhau (inter-cluster distance) Khoảng cách giữa Khoảng cách giữa các ví dụ trong các ví dụ thuộc 2 cụm cùng cụm (intra- khác nhau (inter- cluster distance) cluster distance) Nhập môn Học máy và Khai phá dữ liệu – Introduction to Machine learning and Data mining 8 Internal evaluation: Các độ đo (1) ◼ RMSSTD (Root-mean-square standard deviation) ◼ Đánh giá sự gắn kết (compactness) của các cụm thu được ◼ Mong muốn giá trị RMSSTD càng nhỏ càng tốt! ◼ k: Số lượng các cụm ◼ Ci: Cụm thứ i ◼ mi: Điểm trung tâm (center/centroid) của cụm Ci ◼ P: Tổng số chiều (số lượng thuộc tính) biểu diễn ví dụ ◼ ni: Tổng số các ví dụ thuộc cụm Ci Nhập môn Học máy và Khai phá dữ liệu – Introduction to Machine learning and Data mining 9 Internal evaluation: Các độ đo (2) ◼ R-squared ◼ Đánh giá sự phân tách (separation) giữa các cụm thu được ◼ Mong muốn giá trị R-squared càng lớn càng tốt! ◼ k: Số lượng các cụm ◼ Ci: Cụm thứ i ◼ mi: Điểm trung tâm (center/centroid) của cụm Ci ◼ D: Tập toàn bộ các ví dụ ◼ g: Điểm trung tâm (center/centroid) của toàn bộ các ví dụ Nhập môn Học máy và Khai phá dữ liệu – Introduction to Machine learning and Data mining 10 Internal evaluation: Các độ đo (3) ◼ Dunn index ◼ ~ (Separation/Compactness): Tỷ lệ giữa khoảng cách nhỏ nhất giữa các cụm (minimum inter-cluster distance ...