Bài giảng Tìm kiếm và trình diễn thông tin - Bài 14: Phân cụm văn bản (2)

Bài giảng Tìm kiếm và trình diễn thông tin - Bài 14: Phân cụm văn bản (2). Bài này cung cấp cho sinh viên những nội dung gồm: tính hội tụ của K-means; tính tối ưu của K-means; đánh giá kết quả chia cụm;... Mời các bạn cùng tham khảo chi tiết nội dung bài giảng!
Nội dung trích xuất từ tài liệu:
Bài giảng Tìm kiếm và trình diễn thông tin - Bài 14: Phân cụm văn bản (2) IT4853 Tìm kiếm và trình diễn thông tinBài 14. Phân cụm văn bản (2)IIR. C16. Flat clustering Bộ môn Hệ thống thông tin Viện CNTT & TT Nội dung chính Tính hội tụ của K-means Đánh giá kết quả chia cụm 2 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; 3RSS giảm khi xác định lại tâmcụm 4 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. 5 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ỳ? 6 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ể không 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. 7 Độ 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) 8 Nội dung chính Tính hội tụ của K-means Đánh giá kết quả chia cụm 9 Đánh giá kết quả chia cụm dựa trên dữ liệu phân lớp Ý tưởng: Coi kết quả phân lớp là phương án chia cụm tối ưu, đáp ứng tốt nhất các tiêu chí chia cụm.  Đánh giá kết quả chia cụm bằng cách so sánh với kết quả phân lớp mẫu. Các độ đo:  Purity  Rand Index 10 Độ đo Purity Ω= {ω1, ω2, . . . , ωK} là tập cụm, C = {c1, c2, . . . , cJ} là tập lớp. 11 Ví dụ Purity Tính purity:  maxj |ω1 ∩ cj | = 5; maxj |ω2 ∩ cj | = 4; maxj |ω3 ∩ cj | = 3  Purity = (1/17) × (5 + 4 + 3) ≈ 0.71. 12 Rand Index Cùng lớp Khác lớp Cùng TP FP cụm Khác FN TN cụm TP+ FN + FP + TN = N là tổng số cặp văn bản. 13 Ví dụ Rand IndexFP = 40 − 20 = 20, FN và TN được xác định tương tự. 14Ví dụ Rand Index Cùng lớp Khác lớpCùng TP = 20 FP = 20cụmKhác FN = 24 TN = 72cụm RI = (20 + 72)/136 15Tổng hợp 16 Bài tập 19.1Hai điều kiện dừng của giải thuận k-means:(i) kết quả phân cụm không thay đổi; (ii) tâmcụm không thay đổi.Từ điều kiện (i) có suy ra được điều kiện (ii)hay không?Từ điều kiện (ii) có suy ra được điều kiện (i)hay không? 17 Bài tập 19.2Thay thế mỗi văn bản trên hình vẽ bằng haivăn bản. Sau đó hãy tính Purity và RI.Thêm các văn bản trùng lặp có làm quá trìnhchia cụm khó hơn không? Đại lượng nào thayđổi/không thay đổi? 18 Bài tập 19.3Hãy tính RSS cho kết quả chia cụm trong cả hai trường hợp. 19 Bài tập 19.5Hãy lấy ví dụ một tập điểm và 3 trọng tâm ban đầusao cho kết quả phân cụm 3-means hội tụ với cụmrỗng. (ii) Kết quả chia cụm với cụm rỗng có thể là kếtquả tối ưu toàn cục theo RSS? 20