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

Chia sẻ: Codon_02 Codon_02 | Ngày: | Loại File: PDF | Số trang:20

Thêm vào BST

Báo xấu

69
lượt xem 7
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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;...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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