Tìm kiếm và trình diễn thông tin - Chia cụm và ứng dụng trong tìm kiếm

(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 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 Nội dung chính  Tính chất của K-means;  Đánh giá phương pháp chia cụm. 3 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 RSS giảm khi xác định lại tâm cụm  𝑅𝑆𝑆 = 𝑘=1..𝐾 𝑅𝑆𝑆𝑘  𝑅𝑆𝑆𝑘 𝑣 = 𝑥∈𝜔𝑘 𝑣 − 𝑥 2  𝑅𝑆𝑆𝑘 𝑣 = 𝑥∈𝜔𝑘 𝑚=1..𝑀 𝑣𝑚 − 𝑥𝑚 2  𝜕𝑅𝑆𝑆𝑘(𝑣) 𝜕𝑣𝑚 = 𝑥∈𝜔𝑘 2(𝑣𝑚 − 𝑥𝑚)  𝑣𝑚 = 1 𝜔𝑘 𝑥∈𝜔𝑘 𝑥𝑚 5 RSS đạt cực tiểu tại 𝑣 là tâm cụm 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 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 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 Độ 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 Nội dung chính  Tính chất của K-means;  Đánh giá phương pháp chia cụm. 10 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 Đá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 Đá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 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 Đánh giá dựa trên kết quả mẫu, Rand Index  TP+ FN + FP + TN = N là tổng số cặp văn bản. 15 Cùng cụm Khác cụm Cùng lớp TP FP Khác lớp FN TN Ví dụ, tính Rand Index 16 FP = 40 − 20 = 20, FN và TN được xác định tương tự. Ví dụ, tính Rand Index 17 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 =.. Các độ khác 18  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 đủ Kết quả đánh giá 19 20