Tìm kiếm và trình diễn thông tin - Cài đặt mô hình không gian vec-Tơ

(IT4853) Tìm kiếm và trình diễn thông tin Cài đặt mô hình không gian vec-tơ 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  Các bước cơ bản  Tăng tốc thực hiện truy vấn  Lọc theo từ truy vấn  Phân cấp chỉ mục  Sắp xếp theo trọng số  Phân cụm ngẫu nhiên  Tổng quan hệ thống tìm kiếm 3 Tính độ tương đồng cosine Sec. 6.3.3 4 Lựa chọn top K theo cosine  Sử dụng cấu trúc Heap nhị phân cực đại:  Cây nhị phân, trong đó giá trị của nút gốc luôn lớn hơn hoặc bằng nút con  Nhanh hơn sắp xếp Sec. 7.1 1 .9 .3 .8.3 .1 .1 5 Nội dung chính  Các bước cơ bản  Tăng tốc thực hiện truy vấn  Lọc theo từ truy vấn  Phân cấp chỉ mục  Sắp xếp theo trọng số  Phân cụm ngẫu nhiên  Tổng quan hệ thống tìm kiếm 6 Giản lược quá trình tính cosine: Đặt vấn đề  Chiếm khối lượng tính toán lớn nhất trong xếp hạng  Cần phải xác định chính xác top K?  Độ tương đồng cosine chỉ thể hiện khả năng phù hợp.  Một văn bản không nằm trong top K vẫn có khả năng là văn bản phù hợp.  Có thể giảm khối lượng tính toán nếu chấp nhận tập gần với K văn bản có cosine cao nhất. Sec. 7.1.1 7 Giản lược quá trình tính cosine: Giải pháp  Xác định tập A thỏa mãn:  K < |A| << N;  A chứa nhiều văn bản trong top K, không cần tất cả;  Trả về top K văn bản trong A. Sec. 7.1.1 8 Nội dung chính  Các bước cơ bản  Tăng tốc thực hiện truy vấn  Lọc theo từ truy vấn  Phân cấp chỉ mục  Sắp xếp theo trọng số  Phân cụm ngẫu nhiên  Tổng quan hệ thống tìm kiếm 9 Lọc theo từ truy vấn  Các phương pháp lọc cơ bản:  Chỉ xét từ truy vấn có idf cao;  Chỉ xét các văn bản chứa ít nhất một từ truy vấn;  Chỉ xét các văn bản có chứa nhiều từ truy vấn. Sec. 7.1.2 10 Từ truy vấn với idf cao  Ví dụ, với truy vấn catcher in the rye  Chỉ sử dụng catcher và rye  Giả thuyết: in và the có idf thấp và không ảnh hưởng nhiều tới xếp hạng theo VSM.  Lợi ích:  Các từ có idf thấp có danh sách thẻ định vị dài  giúp giảm thiều đáng kể khối lượng tính toán. Sec. 7.1.2 11 Chứa nhiều từ truy vấn  Văn bản bất kỳ với ít nhất một từ truy vấn đều có khả năng nằm trong danh sách top K.  Với truy vấn đa từ chỉ xếp hạng những văn bản chứa nhiều từ truy vấn  Có hiệu ứng gần với điều kiện AND trong mô hình Boolean. Sec. 7.1.2 12 Ví dụ, nếu chỉ xét văn bản có tối thiểu 3 từ truy vấn T2 T3 T4 1 2 3 5 8 13 21 34 2 4 8 16 32 64 128 13 16 T1 3 4 8 16 32 64 128 32 Chỉ xếp hạng các văn bản 8, 16 và 32. Sec. 7.1.2 13 Nội dung chính  Các bước cơ bản  Tăng tốc thực hiện truy vấn  Lọc theo từ truy vấn  Phân cấp chỉ mục  Sắp xếp theo trọng số  Phân cụm ngẫu nhiên  Tổng quan hệ thống tìm kiếm 14 Danh sách hợp t  Xác định trước các danh sách r văn bản có trọng số cao nhất từ các thẻ định vị của t  Gọi đây là danh sách hợp t.  champion list, top docs for t.  Cần lựa chọn r ở thời điểm xây dựng chỉ mục  Như vậy có khả năng r < K  Khi thực hiện truy vấn ưu tiên lựa chọn top-K từ những văn bản này. Sec. 7.1.3 15 Đại lượng độc lập truy vấn  Độ tin cậy, sẽ ký hiệu là g(d)  Những tín hiệu tin cậy cơ bản:  Được công bố ở một địa chỉ có uy tín  Được trích dẫn bởi nhiều trang khác  Pagerank  v.v. Sec. 7.1.4 16 Tích hợp với VSM  Xếp hạng văn bản theo tổng các giá trị:  net-score(q, d) = g(d) + cosine(q, d)  Có thể sử dụng các phương pháp tổng hợp khác  Xác định các danh sách hợp t theo tổng trọng số g(d) + tf-idft, d Sec. 7.1.4 17 Ứng dụng trong xác định top K  Có thể sắp xếp thẻ định vị theo g(d) thay vì mã văn bản:  Thứ tự thống nhất cho tất cả các danh sách.  Nếu sắp xếp theo g(d), thì các văn bản có xếp hạng cao sẽ có xu hướng xuất hiện sớm trong quá trình duyệt danh sách Sec. 7.1.4 18 Phân cấp danh sách thẻ định vị  Chia mỗi danh sách thẻ định vị thành hai danh sách high và low:  high là danh sách được ưu tiên cao, v.d., trọng số cao  Khi thực hiện truy vấn, duyệt danh sách high trước  Nếu có nhiều hơn K văn bản, lựa chọn top K và dừng.  Ngược lại, xử lý văn bản từ danh sách low.  Tiêu trí phân cấp  tf-idf,  hoặc trọng số kết hợp: g(d) + tf-idft,d Sec. 7.1.4 19 Nội dung chính  Các bước cơ bản  Tăng tốc thực hiện truy vấn  Lọc theo từ truy vấn  Phân cấp chỉ mục  Sắp xếp theo trọng số  Phân cụm ngẫu nhiên  Tổng quan hệ thống tìm kiếm 20 Sắp xếp theo trọng số  Chúng ta chỉ mong muốn xếp hạng những văn bản có wft,d đủ lớn.  Sắp xếp thẻ định vị theo wft,d  Các danh sách khác nhau có thể có thứ tự khác nhau!  Tính điểm để lấy top K bằng cách nào? Sec. 7.1.5 21 Xác định top K 1. Duyệt danh sách thẻ định vị:  Với mỗi danh sách thẻ định vị của t lấy ra  r văn bản,  hoặc những văn bản có wft,d cao hơn ngưỡng  Chỉ xếp hạng các văn bản trong số được lấy ra từ các danh sách thẻ định vị của từ truy vấn. 2. Xử lý từ truy vấn  Theo thứ tự giảm dần idf,  Dừng nếu điểm có xu hướng không đổi, v.d, idf quá nhỏ. Sec. 7.1.5 22 Nội dung chính  Các bước cơ bản  Tăng tốc thực hiện truy vấn  Lọc theo từ truy vấn  Phân cấp chỉ mục  Sắp xếp theo trọng số  Phân cụm ngẫu nhiên  Tổng quan hệ thống tìm kiếm 23 Phân cụm ngẫu nhiên 1. Tiền xử lý:  Chọn ngẫu nhiên N văn bản: gọi là leaders  Tính trước leader gần nhất đối với mỗi văn bản  Các văn bản gắn với leader: followers;  Có thể: Mỗi leader có khoảng ~ N followers. 2. Thực hiện truy vấn:  Tìm leader L gần q nhất.  Tìm top K trong số followers của L. Sec. 7.1.6 24 Trực quan hóa Query Leader Follower Sec. 7.1.6 25 Giải pháp tổng quát  Sử dụng các tham số b1 và b2:  b1 là số leader của mỗi follower.  b2 là số cụm sẽ sử dụng trong thực hiện truy vấn.  Có thể có chu trình khi xác định leader và follower Sec. 7.1.6 26 Nội dung chính  Các bước cơ bản  Tăng tốc thực hiện truy vấn  Lọc theo từ truy vấn  Phân cấp chỉ mục  Sắp xếp theo trọng số  Phân cụm ngẫu nhiên  Tổng quan hệ thống tìm kiếm 27 Chỉ mục siêu dữ liệu  Trong thực tế mỗi văn bản có nhiều thuộc tính khác nhau:  Tác giả  Tiêu đề  Ngày xuất bản  Ngôn ngữ  Định dạng  v.v.  Tập hợp các thuộc tính của văn bản gọi là siêu dữ liệu, có vai trò mô tả văn bản. Sec. 6.1 28 Tìm kiếm trên siêu dữ liệu  Để hỗ trợ tìm kiếm trên siêu dữ liệu:  Chia nhỏ chỉ mục siêu dữ liệu theo thuộc tính;  Tổ chức các danh sách thẻ định vị tương ứng cho mỗi thuộc tính.  Thực hiện truy vấn trên siêu dữ liệu:  Tìm kiếm theo từng thuộc tính riêng lẻ;  Kết quả thực hiện truy vấn trên các thuộc tính thường được kết hợp như điều kiện AND. Sec. 6.1 29 Chia miền  Một miền là một phần văn bản, có thể có độ dài tùy ý:  Tiêu đề  Tóm tắt  Tài liệu tham khảo  Tổ chức chỉ mục ngược trên miền sẽ rất hữu ích trong tìm kiếm  v.d., “tìm văn bản có merchant trong tiêu đề và phù hợp với gentle rain” Sec. 6.1 30 Ví dụ chỉ mục chia miền Mã hóa miền trong từ điển vs. danh sách Sec. 6.1 31 Chỉ mục phân cấp  Chia danh sách thẻ định vị theo nhiều cấp độ  Có thể sử dụng g(d) hoặc các tham số khác  Khi thực hiện truy vấn, tìm top K tuân tự theo cấp độ ưu tiên Sec. 7.2.1 32 Ví dụ chỉ mục phân cấp Sec. 7.2.1 33 Nhận diện kiểu truy vấn  Một chuỗi từ có thể được hiểu theo nhiều cách khác nhau:  Một truy vấn dạng câu;  Nhiều câu nhỏ hơn;  Hoặc vec-tơ trên từ.  Người dùng thường ưa thích văn bản có từ truy vấn xuất hiện gần nhau  Nhận diện kiểu truy vấn là quá trình xác định sơ đồ truy vấn tối ưu. Sec. 7.2.3 34 Tổng hợp tiêu trí xếp hạng  Điểm xếp hạng có thể được tổng hợp từ độ tương đồng cosine, đại lượng độc lập truy vấn, khoảng cách giữa từ truy vấn, v.v. Sec. 7.2.3 35 Phương pháp tổng hợp nào là hiệu quả nhất? Sơ đồ khái quát Sec. 7.2.4 36 37