Bài giảng Học máy - L12: Các phương pháp học có giám sát Phân cụm dựa trên tích tụ phân cấp: HAC (Hierarchical agglomerative clustering)

Nội dung text: Bài giảng Học máy - L12: Các phương pháp học có giám sát Phân cụm dựa trên tích tụ phân cấp: HAC (Hierarchical agglomerative clustering)

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 „ Phân cụm dựatrêntíchtụ phân cấp: HAC (Hierarchical agglomerative clustering) „ Lọccộng tác „ Học tăng cường Học Máy (IT 4862) 2
2. 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ỗivídụ chính là mộtcụm (là một nút trong dendrogram) • Hợp nhất2 cụm có mức độ tương tự (gần) nhau nhất ƒ Cặpgồm2 cụm có khoảng cách nhỏ nhất trong số các cặpcụm • Tiếptục quá trình hợpnhất • Giảithuậtkết thúc khi tấtcả các ví dụđượchợpnhất thành một cụm duy nhất (là nút gốc trong dendrogram) ọ H c Máy (IT 4862) 4
3. Khoảng cách giữa2 cụm „ GiảithuậtHAC cần định nghĩaviệc tính toán khoảng cách giữa 2c2 cụm • Trướckhihợpnhất, cần tính khoảng cách giữamỗicặp2 cụm có thể „ Có nhiềuphương pháp để đánh giá khoảng cách giữa2 cụm – đưa đến các biếnthể khác nhau củagiảithuậtHAC • 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
4. HAC – Liên kết hoàn toàn HAC liên kết hoàn toàn (Complete link): C1 + ƒ Khoảng cách giữa2 cụm là + khoảng cách lớnnhất giữa C các ví dụ (các thành viên) của 2 2 cụm đó ƒ Nhạycảm(gặplỗi phân cụm) đốivới các ngoại lai (outliers) ƒ Có xu hướng sihinh ra cáccụm có dạng “bụi cây” (clumps) [Liu, 2006] ọ H c Máy (IT 4862) 8
5. HAC – Liên kết trung tâm HAC liên kết trung tâm (Centroid link): „ Khoảng cách giữa2 cụm là khoảng cách giữa2 điểm trung tâm (centroids) của2 cụm đó C1 + + C2 ọ H c Máy (IT 4862) 10
6. Các hàm khoảng cách „ Một thành phần quan trọng của các phương pháp phân cụm • Cầnxácđịnh các hàm tính độ khác biệt (dissimilarity/distance functions), hoặc các hàm tính độ tương tự (similarity functions) „ Các hàm tính khoảng cách khác nhau đốivới • Các kiểudữ liệu khác nhau ƒ Dữ liệukiểusố (Numeric data) ƒ Dữ liệukiểu định danh (Nominal data) • Các bài toán ứng dụng cụ thể ọ H c Máy (IT 4862) 12
7. Hàm k/c cho thuộc tính nhị phân „ Sử dụng một ma trận để biểu diễn hàm tính khoảng cách • a: Tổng số thuộc tính có giá trị là 1 trong cả xi và xj ví dụ xj • b: Tổng số các thuộc tính có giá trị là 1 trong x và i 10 có giá trị là 0 trong xj i x • c: Tổng số các thuộc tính có giá trị là 0 trong xi và 1 ab ụ có giá trị là 1 trong xj 0 cd • d: Tổng số các thuộc tính có giá trị là 0 trong cả xi ví d và xj „ Hệ số phù hợp đơn giản (Simple matching coeffi ci en t). Tỷ lệ sai lệcgách giá trị củaacác các thuộc tính giữa 2 ví dụ: b + c d(x ,x ) = i j a + b + c + d ọ H c Máy (IT 4862) 14
8. Tài liệu tham khảo •B. Liu. Web Data Mining: Exploring Hyperlinks, Contents, and Usage Data. Sppgringer, 2006. ọ H c Máy (IT 4862) 16