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  Vấn đề chia cụm  Ứng dụng chia cụm trong tìm kiếm  Giải thuật K-means 3 Vấn đề chia cụm  Chia cụm là chia một tập văn bản lớn thành nhiều tập nhỏ với nội dung tương tự, gọi là cụm;  Các văn bản trong một cụm phải tương tự;  Các văn bản khác cụm phải khác nhau;  Chia cụm là một phương pháp học không giám sát (unsupervised);  Không yêu cầu dữ liệu luyện. 4 Vấn đề chia cụm, minh họa 5 Làm cách nào để chia cụm như trong hình vẽ? Phân lớp vs. Chia cụm  Phân lớp: Học có giám sát  Các lớp được định nghĩa bởi con người  Chia cụm: Học không giám sát  Cụm được suy diễn trực tiếp từ dữ liệu  Con người giám sát các tham số: số cụm, phương pháp tính độ tương đồng, biểu diễn văn bản v.v. 6 Nội dung chính  Vấn đề chia cụm  Ứng dụng chia cụm trong tìm kiếm  Giải thuật K-means 7 Giả thuyết chia cụm  Giả thuyết: Các văn bản trong cùng một cụm có cùng đặc tính phù hợp với nhu cầu thông tin.  Theo Van Rijbergen: “Closely associated documents tend to be relevant to the same requests”. 8 Ứng dụng chia cụm trong tìm kiếm 9 Ứng dụng Tập văn bản chia cụm? Lợi ích Chia cụm kết quả Tập kết quả Dễ tìm kết quả phù hợp hơn Chia cụm – gom nhóm (Scatter-Gather) Bộ văn bản Giao diện duyệt tập văn bản (search without typing) Chia cụm để duyệt Bộ văn bản Hỗ trợ tìm kiếm bằng phương pháp duyệt Lọc văn bản theo cụm Bộ văn bản Xử lý truy vấn nhanh hơn Chia cụm kết quả tìm kiếm 10 Chia cụm-Gom nhóm 11 Chia cụm để duyệt 12 13 13 Tăng độ đầy đủ  Để cải thiện tính đầy đủ của kết quả tìm kiếm:  Chia cụm văn bản trong bộ dữ liệu;  Đồng thời trả về các văn bản trong cùng cụm chứa văn bản d phù hợp với q.  Kết quả mong đợi: Trả về các văn bản chứa từ đồng nghĩa (car – automobile). 14 Cụm phẳng vs. cụm phân cấp  Giải thuật chia cụm phẳng:  Thường bắt đầu với cách chia ngẫu nhiên;  Sau đó lặp quá trình xác định lại cụm;  Giải thuật tiêu biểu: K-means  Chia cụm phân cấp:  Tổ chức cụm theo cấu trúc cây;  Bottom-up, agglomerative  Top-down, divise 15 Giới hạn cứng vs. mềm  Chia cụm cứng: Mỗi văn bản chỉ thuộc một cụm duy nhất.  Đơn giản hơn so với chia cụm mềm;  Chia cụm mềm: Mỗi văn bản có thể thuộc nhiều cụm. 16 K-Means là phương pháp chia cụm phẳng, đường biên cứng. Nội dung chính  Phát biểu bài toán  Ứng dụng chia cụm trong tìm kiếm  Giải thuật K-means 17 Mô hình hóa văn bản trong chia cụm  Tương tự như trong mô hình không gian vec-tơ  Mức độ khác biệt giữa các văn bản được thể hiện bằng khoảng cách Euclide  Không chuẩn hóa vec-tơ trọng tâm. 18 K-means  Mỗi cụm theo K-means được xác định bởi một trọng tâm (centroid).  Mục tiêu: Cực tiểu tổng bình phương khoảng cách từ các điểm mô hình văn bản đến trọng tậm 𝜇(𝜔) = 1 |𝜔| 𝑥∈𝜔 𝑥, trong đó ω là một cụm;  Cực tiểu hóa bằng cách:  Gắn mỗi vec-tơ với trọng tâm gần nhất;  Xác định lại trọng tâm sau mỗi lần chia cụm. 19 Giải thuật K-means 20 Ví dụ chia cụm theo K-means 21 Ví dụ, xác định ngẫu nhiên trọng tâm 22 Ví dụ, xác định trọng tâm gần nhất cho mỗi văn bản 23 Ví dụ, kết quả chia cụm đầu tiên 24 Ví dụ, xác định lại trọng tâm 25 Ví dụ, lặp quá trình chia cụm 26 Ví dụ chia cụm theo K-means 27 Ví dụ chia cụm theo K-means 28 Ví dụ chia cụm theo K-means 29 Ví dụ chia cụm theo K-means 30 Ví dụ chia cụm theo K-means 31 Ví dụ chia cụm theo K-means 32 Ví dụ chia cụm theo K-means 33 Ví dụ chia cụm theo K-means 34 Ví dụ chia cụm theo K-means 35 Ví dụ chia cụm theo K-means 36 Ví dụ chia cụm theo K-means 37 Ví dụ chia cụm theo K-means 38 Ví dụ chia cụm theo K-means 39 Ví dụ chia cụm theo K-means 40 Ví dụ chia cụm theo K-means 41 Ví dụ chia cụm theo K-means 42 Ví dụ chia cụm theo K-means 43 Ví dụ chia cụm theo K-means 44 45