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

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

1. (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
2. 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
3. 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
4. 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
5. Vấn đề chia cụm, minh họa Làm cách nào để chia cụm như trong hình vẽ? 5
6. 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
7. 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
8. 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
9. Ứng dụng chia cụm trong tìm kiếm Ứng dụng Tập văn bản chia Lợi ích cụm? 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 Bộ văn bản Giao diện duyệt tập văn (Scatter-Gather) 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 9
10. Chia cụm kết quả tìm kiếm 10
11. Chia cụm-Gom nhóm 11
12. Chia cụm để duyệt 12
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
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
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. K-Means là phương pháp chia cụm phẳng, đường biên cứng. 16
16. 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
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
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
19. Giải thuật K-means 20
20. Ví dụ chia cụm theo K-means 21
21. Ví dụ, xác định ngẫu nhiên trọng tâm 22
22. Ví dụ, xác định trọng tâm gần nhất cho mỗi văn bản 23
23. Ví dụ, kết quả chia cụm đầu tiên 24
24. Ví dụ, xác định lại trọng tâm 25
25. Ví dụ, lặp quá trình chia cụm 26
26. Ví dụ chia cụm theo K-means 27
27. Ví dụ chia cụm theo K-means 28
28. Ví dụ chia cụm theo K-means 29
29. Ví dụ chia cụm theo K-means 30
30. Ví dụ chia cụm theo K-means 31
31. Ví dụ chia cụm theo K-means 32
32. Ví dụ chia cụm theo K-means 33
33. Ví dụ chia cụm theo K-means 34
34. Ví dụ chia cụm theo K-means 35
35. Ví dụ chia cụm theo K-means 36
36. Ví dụ chia cụm theo K-means 37
37. Ví dụ chia cụm theo K-means 38
38. Ví dụ chia cụm theo K-means 39
39. Ví dụ chia cụm theo K-means 40
40. Ví dụ chia cụm theo K-means 41
41. Ví dụ chia cụm theo K-means 42
42. Ví dụ chia cụm theo K-means 43
43. Ví dụ chia cụm theo K-means 44