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

Bài giảng Tìm kiếm và trình diễn thông tin: Bài 14 - TS.Nguyễn Bá Ngọc hướng đến trình bày chia cụm và ứng dụng trong tìm kiếm; vấn đề chia cụm; vấn đề chia cụm, minh họa; phân lớp vs. Chia cụm; ứng dụng chia cụm trong tìm kiếm;...
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 - 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 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. 4Vấn đề chia cụm, minh họa Làm cách nào để chia cụm như trong hình vẽ? 5 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Ứ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ơnChia 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ệtLọc văn bản theo cụm Bộ văn bản Xử lý truy vấn nhanh hơn 9Chia cụm kết quả tìm kiếm 10Chia cụm-Gom nhóm 11Chia cụm để duyệthttp://news.google.com 1213 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.K-Means là phương pháp chia cụm phẳng, đườngbiên cứng. 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 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. 19Giải thuật K-means 20 ...