(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
2
TS. Nguyễn Bá Ngọc Địa chỉ: ViệnCNTT & TT/BM HTTT/B1-603 Email: ngocnb@soict.hust.edu.vn Website: http://is.hust.edu.vn/~ngocnb
Nội dung chính
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
Các bước cơ bản Tăng tốc thực hiện truy vấn
Sec. 6.3.3
Tính độ tương đồng cosine
4
Sec. 7.1
Lựa chọn top K theo cosine
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
Sử dụng cấu trúc Heap nhị phân cực đại:
1
.9
.3
.8
.3
.1
.1
5
Nội dung chính
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
Các bước cơ bản Tăng tốc thực hiện truy vấn
Sec. 7.1.1
Giản lược quá trình tính cosine: Đặt vấn đề
lượng tính toán lớn nhất trong xếp
hạng
Chiếm khối
Độ 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.
7
Cần phải xác định chính xác top K?
Sec. 7.1.1
Giản lược quá trình tính cosine: Giải pháp
Xác định tập Athỏa mãn:
K < |A| << N; Achứ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.
8
Nội dung chính
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
Các bước cơ bản Tăng tốc thực hiện truy vấn
Sec. 7.1.2
Lọc theo từ truy vấn
10
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
Từ truy vấn với idf cao
hưởng nhiều tới xếp hạng theo VSM.
Ví dụ, với truy vấn catcher in the rye Chỉ sử dụng catcher và rye Giả thuyết: invà thecó idf thấp và không ảnh
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.
11
Lợi ích:
Sec. 7.1.2
Chứa nhiều từ truy vấn
có khả năng nằm trong danh sách top K.
Văn bản bất kỳ với ít nhất một từ truy vấn đều
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.
12
Với truy vấn đa từ chỉ xếp hạng những văn bản
Sec. 7.1.2
Ví dụ, nếu chỉ xét văn bản có tối thiểu 3 từ truy vấn
T1
3
4
8
16 32 64 128
T2
2
4
8
16 32 64 128
T3
1
2
3
5
8
13 21 34
T4
13 16
32
Chỉ xếp hạng các văn bản 8, 16 và 32.
13
Nội dung chính
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
Các bước cơ bản Tăng tốc thực hiện truy vấn
Sec. 7.1.3
Danh sách hợp t
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.
Xác định trước các danh sách r văn bản có trọng
Như vậy có khả năng r< K
Cần lựa chọn r ở thời điểm xây dựng chỉ mục
những văn bản này.
15
Khi thực hiện truy vấn ưu tiên lựa chọn top-K từ
Sec. 7.1.4
Đại lượng độc lập truy vấ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.
16
Độ tin cậy, sẽ ký hiệu là g(d) Những tín hiệu tin cậy cơ bản:
Sec. 7.1.4
Tích hợp với VSM
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
17
Xếp hạng văn bản theo tổng các giá trị: net-score(q, d) = g(d) + cosine(q, d)
Sec. 7.1.4
Ứng dụng trong xác định top K
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
18
Có thể sắp xếp thẻ định vị theo g(d) thay vì mã
Sec. 7.1.4
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.
tf-idf, hoặc trọng số kết hợp: g(d) + tf-idft,d
19
Tiêu trí phân cấp
Nội dung chính
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
Các bước cơ bản Tăng tốc thực hiện truy vấn
Sec. 7.1.5
Sắp xếp theo trọng số
bản có wft,d đủ lớn.
Chúng ta chỉ mong muốn xếp hạng những văn
nhau!
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
21
Tính điểm để lấy top K bằng cách nào?
Sec. 7.1.5
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
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
22
quá nhỏ.
Chỉ xếp hạng các văn bản trong số được lấy ra từ
Nội dung chính
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
Các bước cơ bản Tăng tốc thực hiện truy vấn
Sec. 7.1.6
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 ~ Nfollowers.
2. Thực hiện truy vấn: Tìm leader Lgần qnhất. Tìm top Ktrong số followers của L.
24
Sec. 7.1.6
Trực quan hóa
Query
Leader
Follower
25
Sec. 7.1.6
Giải pháp tổng quát
follower
26
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à
Nội dung chính
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
Các bước cơ bản Tăng tốc thực hiện truy vấn
Sec. 6.1
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.
dữ liệu, có vai trò mô tả văn bản.
28
Tập hợp các thuộc tính của văn bản gọi là siêu
Sec. 6.1
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.
Để hỗ trợ tìm kiếm trên siêu dữ liệu:
được kết hợp như điều kiện AND.
29
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
Sec. 6.1
Chia miền
tùy ý: Tiêu đề Tóm tắt Tài liệu tham khảo …
Một miền là một phần văn bản, có thể có độ dài
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”
30
Tổ chức chỉ mục ngược trên miền sẽ rất hữu ích
Sec. 6.1
Ví dụ chỉ mục chia miền
Mã hóa miền trong từ điển vs. danh sách
31
Sec. 7.2.1
Chỉ mục phân cấp
Có thể sử dụng g(d)hoặc các tham số khác
Chia danh sách thẻ định vị theo nhiều cấp độ
cấp độ ưu tiên
32
Khi thực hiện truy vấn, tìm top K tuân tự theo
Sec. 7.2.1
Ví dụ chỉ mục phân cấp
33
Sec. 7.2.3
Nhận diện kiểu truy vấn
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ừ.
Một chuỗi từ có thể được hiểu theo nhiều cách
vấn xuất hiện gần nhau
Người dùng thường ưa thích văn bản có từ truy
đồ truy vấn tối ưu.
34
Nhận diện kiểu truy vấn là quá trình xác định sơ
Sec. 7.2.3
Tổng hợp tiêu trí xếp hạng
tương đồng cosine, đại khoảng cách giữa từ truy vấn, v.v.
Phương pháp tổng hợp nào là hiệu quả nhất?
35
Điểm xếp hạng có thể được tổng hợp từ độ lượng độc lập truy vấn,
Sec. 7.2.4
Sơ đồ khái quát
36
37
