Bài giảng Học máy - L9: Các phương pháp học có giám sát Giới thiệu về phân cụm „Phân cụm dựa trên phân tách: K-Measn

Nội dung text: Bài giảng Học máy - L9: Các phương pháp học có giám sát Giới thiệu về phân cụm „Phân cụm dựa trên phân tách: K-Measn

1. Nội dung môn học: „ Giới thiệu chung „ Đánh giá hiệunăng hệ thống họcmáy „ Các phương pháp họccd dựatrênxácsua trên xác suất „ Các phương pháp học có giám sát „ Cácphương pháp học không giámsát „ Giớithiệuvề phân cụm „ Phân cụm dựa ttêrên ppâhân tách: k-Mean s „ Lọccộng tác „ Học tăng cường Học Máy (IT 4862) 2
2. 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ồntạ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ậtkếthợp (Association rule mining), „ Học 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) ‰ Đầura: cáccụm (nhóm) củacácvídụ „ Một cụm(cluster)là mộttậ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 ọ H c Máy (IT 4862) 4
3. 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ảithuậ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ỗnhợ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ữacáccụm → Cần được cực đại hóa • Khoảng cách/sự khác biệt bên trong mộtcụm → Cần được cựctiểu hóa ọ H c Máy (IT 4862) 6
4. k-Means – Các bước chính Vớimộtgiátrị k đượcxácđịnh trước • Bước 1. Chọnngẫunhiên k ví dụ (đượcgọi là các hạt nhân – seeds) để sử dụng làm các điểm trung tâm ban đầu (initial centroids) của k cụm • Bước2. Đốivớimỗivídụ, gán nó vào cụm (trong số k cụm) có điểm trung tâm (centroid) gầnvídụđónhất • Bước3. Đốivớimỗicụm, tính toán lại điểm trung tâm (centroid) củanódựatrêntấtcả các ví dụ thuộcvào cụm đó • Bước4. Dừng lạinếu điềukiệnhộitụ (convergence criterion) được thỏa mãn; nếu không, quay lại Bước 2 ọ H c Máy (IT 4862) 8
5. Điều kiện hội tụ Quá trình phân cụm kết thúc, nếu: • Không có (hoặc có không đáng kể) việc gán lại các ví dụ vào các cụm khác, hoặc • Không có (hoặc có không đáng kể) thay đổivề các điểm trung tâm (centidtroids) củacáccụm, hoặc • Giảm không đáng kể về tổng lỗi phân cụm: k 2 Error = ∑ ∑ d(x,mi ) iC=∈1 x i ƒ Ci: Cụm thứ i ƒ mi: Điểm trung tâm (centroid) củacụm Ci ƒ d(x, mi): Khoảng cách (khác biệt) giữavídụ x và điểm trung tâm mi ọ H c Máy (IT 4862) 10
6. k-Means – Minh họa (()2) [Liu, 2006] ọ H c Máy (IT 4862) 12
7. k-Means – Các ưu điểm „ Đơngiản • Rất dễ cài đặt • Rấtdễ hiểu „ Hiệuquả • Độ phứctạpvề thờigian~ O(r.k.t) ƒ r: Tổng số các ví dụ (kích thước của tập dữ liệu) ƒ k: Tổng số cụm thu được ƒ t: Tổng số bướclặp(của quá trình phân cụm) • Nếucả 2 giá trị k và t đềunhỏ, thì giảithuật k-means đượcxem như là có độ phứctạp ở mứctuyến tính „ k-means là giải thuật phân cụm được dùng phổ biến nhất ọ H c Máy (IT 4862) 14
8. k-Means – Các ví dụ ngoại lai [Liu, 2006] ọ H c Máy (IT 4862) 16
9. k-Means – Các nhược điểm (2) „ Giải thuật k-means phụ thuộc vào việc chọn các điểm trung tâm ban đầu (initial centroids) 1st centroid 2nd centidtroid [Liu, 2006] ọ H c Máy (IT 4862) 18
10. k-Means – Các hạt nhân ban đầu(2) „ Lựa chọn ngẫu nhiên hạt nhân thứ 1 (m1) „ Lựa chọn hạt nhân thứ 2 (m2) càng xa càng tốt so với hạt nhân thứ 1 „ „ Lựa chọn hạt nhân thứ i (mi) càng xa càng tốt so với hạt nhân gầnnnh nhất trong số {m1, m2, , mi-1} „ ọ H c Máy (IT 4862) 20
11. k-Means – Tổng kết „ Mặcdùcónhững nhược điểmnhư trên, k-means vẫnlà giải thuật phổ biến nhất được dùng để giải quyết các bài toán phân cụm – do tính đơngiảnvàhiệuquả • Các giảithuật phân cụm khác cũng có các nhược điểm riêng „ Về tổng quát, không có lý thuyết nào chứng minh rằng mộtgiảithuật phân cụm khác hiệuquả hơn k-means • Mộtsố giảithuật phân cụm có thể phù hợphơnmộtsố giảithuật khác đốivớimộtsố kiểutậpdữ liệunhất định, hoặc đốivớimột số bài toán ứng dụng nhất định „ So sánh hiệunăng của các giảithuật phân cụm là một nhiệmvụ khó khăn(tháchthức) • Làm sao để biết được các cụm kết quả thu được là chính xác? ọ H c Máy (IT 4862) 22