Bài giảng Tìm kiếm và trình diễn thông tin - Bài 15: Chia cụm và ứng dụng trong tìm kiếm - Nguyễn Bá Ngọc

Nội dung text: Bài giảng Tìm kiếm và trình diễn thông tin - Bài 15: Chia cụm và ứng dụng trong tìm kiếm - Nguyễn Bá Ngọc

1. (IT4853) Tìm kiếm và trình diễn thông tin Chia cụm và ứng dụng trong tìm kiếm
2. Giảng viên  TS. Nguyễn Bá Ngọc  Địa chỉ: Viện CNTT & TT/BM HTTT/B1-603  Email: ngocnb@soict.hust.edu.vn  Website: 2
3. Nội dung chính  Tính chất của K-means;  Đánh giá phương pháp chia cụm. 3
4. K-means luôn hội tụ  RSS: Residual Sum of Squares;  RSS tổng bình phương khoảng cách giữa các văn bản và trọng tâm gần nhất;  RSS giảm dần sau mỗi bước chia cụm  Vì mỗi văn bản được gán với trọng tâm gần nhất;  RSS giảm sau mỗi bước xác định lại tâm cụm  Xem slides tiếp theo  Số cách chia cụm là hữu hạn; 4
5. RSS giảm khi xác định lại tâm cụm  푅푆푆 = =1 퐾 푅푆푆 2  푅푆푆 푣 = 푣 − ∈휔 2  푅푆푆 푣 = 푣 − ∈휔 =1 휕푅푆푆 (푣)  = ∈휔 2(푣 − ) 휕푣 1  푣 = ∈휔 휔 RSS đạt cực tiểu tại 푣 là tâm cụm 5
6. Tính tối ưu của K-means  Hội tụ không đồng nhất với cách chia cụm tối ưu;  Nếu lựa chọn tâm cụm ban đầu không tốt, chất lượng chia cụm có thể rất thấp. 6
7. Hội tụ, cận tối ưu  Kết quả chia cụm tối ưu cho K = 2?  Luôn hội tụ với các tập mầm {di, dj} bất kỳ? 7
8. Khởi tạo K-means  Nhược điểm của khởi tạo ngẫu nhiên là không ổn định: kết quả chia cụm có thể khong tối ưu  Hiệu chỉnh:  Lựa chọn tập mầm tốt;  V.D., thực hiện nhiều lượt sinh ngẫu nhiên rồi chọn kết quả tốt nhất. 8
9. Độ phức tạp giải thuật K-means  Tính khoảng cách giữa hai vec-tơ O(M)  Gắn văn bản với trọng tâm: O(KNM)  Xác định lại trọng tâm: O(NM)  Giả sử giải thuật hội tụ sau I bước  Độ phức tạp tổng quát: O(IKNM) 9
10. Nội dung chính  Tính chất của K-means;  Đánh giá phương pháp chia cụm. 10
11. Tiêu trí chất lượng chia cụm  Tiêu trí nội biên  Ví dụ, RSS trong K-means  Tiêu trí ngoại biên  Chiếu theo kết quả phân lớp của chuyên gia 11
12. Đánh giá bằng đối chiếu với phân lớp mẫu  Mục tiêu: Mô phỏng cách chia lớp mẫu.  Các độ đo:  Purity  Rand Index 12
13. Đánh giá dựa trên kết quả mẫu, Purity  Ω= {ω1, ω2, . . . , ωK} là các cụm,  C = {c1, c2, . . . , cJ} là các lớp.  Trong mỗi cụm ωk tìm lớp cj với nhiều văn bản nhất, ký hiệu số văn bản là nki;  Tính tổng nki và chia cho số lượng văn bản. 13
14. Ví dụ, tính Purity  Để tính purity:  5 = maxj |ω1 ∩ cj |; 4 = maxj |ω2 ∩ cj |;  và 3 = maxj |ω3 ∩ cj |  Purity = (1/17) × (5 + 4 + 3) ≈ 0.71. 14
15. Đánh giá dựa trên kết quả mẫu, Rand Index Cùng cụm Khác cụm Cùng lớp TP FP Khác lớp FN TN  TP+ FN + FP + TN = N là tổng số cặp văn bản. 15
16. Ví dụ, tính Rand Index FP = 40 − 20 = 20, FN và TN được xác định tương tự. 16
17. Ví dụ, tính Rand Index Cùng cụm Khác cụm Cùng lớp TP = 20 FP = 24 Khác lớp FN = 20 TN = 72 RI = 17
18. Các độ khác  Chuẩn hóa hàm lượng thông tin (NMI)  Cụm có NMI cực đại  entropy của các lớp và các cụm  Độ đo F  Trung bình có trọng số của độ chính xác và độ đầy đủ 18
19. Kết quả đánh giá 19