Bài giảng Tìm kiếm và trình diễn thông tin: Bài 15 - TS.Nguyễn Bá Ngọc

Tiếp tục đến với "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" sẽ giới thiệu tới các bạn tính chất của K-means; K-means luôn hội tụ; RSS giảm khi xác định lại tâm cụm; tính tối ưu của K-means; hội tụ, cận tối ưu;...
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 15 - TS.Nguyễn Bá Ngọc (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: http://is.hust.edu.vn/~ngocnb 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 ????∈????????  ???????????????? ???? = ???????? − ???????? 2 ????∈???????? ????=1..???? ???????????????????? (????)  = ????∈???????? 2(???????? − ???????? ) ???????????? 1  ???????? = ????∈???????? ???????? ???????? RSS đạt cực tiểu tại ???? là tâm cụm 5 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 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 Ví dụ, tính Rand Index FP = 40 − 20 = 20, FN và TN được xác định tương tự. 16 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 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 Kết quả đánh giá 19 20