Bài giảng "Học máy - Các phương pháp học không giám sát: Phân cụm dựa trên tích phân tụ phân cấp" trình bày khoảng cách giữa hai cụm, liên kết đơn, liên kết hoàn toàn, độ phức tạp, các hàm khoảng cách,. . | Bài giảng Học máy: Các phương pháp học không giám sát - Nguyễn Nhật Quang (P2) Học Máy (IT 4862) Nguyễn ễ Nhật hậ Quang quangnn-fit@ 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 2011-2012 Nội dung d môn ô học: h Giới thiệu chung g Đánh giá hiệu năng hệ thống học máy Các phương pháp học dựa trên xác suất Các phương pháp học có giám sát Cá phương Các h pháp há học h không khô giám iá sát át Phân cụm dựa trên tích tụ phân cấp: HAC (Hierarchical agglomerative clustering) Lọc cộng tác Học tăng cường Học Máy (IT 4862) 2 HAC (1) Sinh ra một chuỗi lồng nhau của các cụm, được gọi là dendrogram g • Cũng được gọi là một phân loại (taxonomy)/phân cấp (hierarchy)/cây (tree) của các ví dụ [Liu, 2006] Học Máy (IT 4862) 3 HAC (2) Phân cụm dựa trên tích tụ phân cấp (Hierarchical Agglomerative Clustering – HAC) sẽ xây dựng dendrogram từ mức đáy (cuối) dần lên (bottom-up) Giải thuật HAC • Bắt đầu, mỗi ví dụ chính là một cụm (là một nút trong dendrogram) • Hợp ợp nhất 2 cụm ụ có mức độ ộ tương g tự ự (g (gần)) nhau nhất Cặp gồm 2 cụm có khoảng cách nhỏ nhất trong số các cặp cụm • Tiếp tục quá trình hợp nhất • Giải thuật kết thúc khi tất cả các ví dụ được hợp nhất thành một cụm duy nhất (là nút gốc trong dendrogram) Học Máy (IT 4862) 4 HAC – Ví dụ ụ (Venn diagram) [Liu, 2006] Học Máy (IT 4862) 5 Khoảng g cách g giữa 2 cụm ụ Giải thuật HAC cần định nghĩa việc tính toán khoảng cách giữa 2 cụm • Trước khi hợp nhất, cần tính khoảng cách giữa mỗi cặp 2 cụm có thể Có nhiều phương pháp để đánh giá khoảng cách giữa 2 cụm – đưa đến các biến thể khác nhau của giải thuật HAC • Liên kết đơn (Single link) • Liên kết hoàn toàn (Complete link) • Liên kết trung bình (Average link) • Liên kết trung tâm (Centroid link) • Học Máy (IT 4862) 6 HAC – Liên kết đơn HAC liên kết đơn (Single link): C1 + .
