Bài giảng Thư viện số - Chương 4: Tìm kiếm thông tin - Đỗ Quang Vinh

Nội dung text: Bài giảng Thư viện số - Chương 4: Tìm kiếm thông tin - Đỗ Quang Vinh

1. BÀI GIẢNG THƯ VIỆN SỐ CHƯƠNG 4: TÌM KIẾM THÔNG TIN TS. ĐỖ QUANG VINH HÀ NỘI - 2013
2. NỘI DUNG I. TỔNG QUAN VỀ THƯ VIỆN SỐ DL II. MÔ HÌNH HÌNH THỨC CHO THƯ VIỆN SỐ DL III. CHỈ MỤC TÀI LIỆU IV. TÌM KIẾM THÔNG TIN V. CÁC CHUẨN SỬ DỤNG TRONG THƯ VIỆN SỐ VI. THỰC HÀNH HỆ PHẦN MỀM THƯ VIỆN SỐ GREENSTONE 2
3. IV. TÌM KIẾM THÔNG TIN 4.1 MÔ HÌNH TÌM KIẾM THÔNG TIN ▪ Tìm kiếm thông tin IR đề cập đến tổ chức, lưu trữ, tìm kiếm và đánh giá thông tin có liên quan tới nhu cầu thông tin của NSD. ▪ Mô hình IR tổng quát là một cặp bao gồm các đối tượng và một ánh xạ liên kết (“tìm kiếm”) một số đối tượng với một đối tượng đại diện cho một truy vấn. Cho D = {d1, d2, , dM}, M 2 (4.1) là một tập hữu hạn không rỗng đối tượng. ✓ Chú ý: trường hợp M = 1 có thể được xem xét nhưng nó là tầm thường. Các đối tượng tiêu biểu là đại diện. 3
4. Cho  là một ánh xạ tìm kiếm từ D vào trong lực lượng của nó (D), nghĩa là,  : D → (D) (4.2) Bằng cách kết hợp tập đối tượng D và ánh xạ tìm kiếm , chúng tôi định nghĩa cấu trúc tìm kiếm thông tin như sau: ▪ Định nghĩa 4.1 (cấu trúc tìm kiếm thông tin): Cấu trúc tìm kiếm thông tin SIR là một bộ 2 S = (4.3) Định nghĩa 4.1 là một định nghĩa tổng quát: nó không đề cập đến về các dạng riêng biệt của ánh xạ tìm kiếm  và đối tượng D. Từ đó, các mô hình IR riêng biệt khác nhau có thể nhận được bằng cách đặc tả D và . 4
5. ▪ Định nghĩa 4.2 (mô hình tìm kiếm thông tin MIR): Mô hình tìm kiếm thông tin MIR là một SIR S = với 2 thuộc tính sau đây: i. q =  ãi(q, ) = 1 i, q,  (tính phản xạ); (4.4) i ii.  (q) = { D| ãi(q, ) = max ãk(q, k)} a i, i cố định tùy ý. trong đó: + T = {t1, t2, , tN} là một tập hữu hạn thuật ngữ chỉ mục, N 1; + O = {o1, o2, , oU} là một tập hữu hạn đối tượng, U 2; + (Dj)j J = {1, 2, , M} là một họ cluster đối tượng, Dj (O), M 2; 5
6. + D = {j| j J} là một tập tài liệu, trong đó tập mờ đã chuẩn hóa j = {(tk , j(tk))| tk T, k = 1, , N}, j = 1, , M, j : T → S  [0, 1]  R là đại diện cluster của cluster đối tượng Dj. + A = {ã1, , ãC} là một tập hữu hạn tiêu chuẩn, C 1, trong đó ãi = {((q, j), ãi(q, j)) | j D, j =1, , M}, i = 1, , C là một quan hệ mờ chuẩn hóa, ãi : D x D → [0, 1]  R, q D cố định tùy ý. ✓ Theo truyền thống, IR kinh điển có thuộc tính phân đôi (lưỡng cực) trong đó có 2 tiêu chuẩn rõ ràng: i. có mặt và không có mặt; ii. tìm kiếm được thực hiện dựa vào (i). 6
7. + a i = { D| ãi(q, ) > i}, i = 1, , C là một i-lát cắt tiêu chuẩn mạnh ãi, i 0, q D cố định tùy ý; +  : D → (D) là một ánh xạ tìm kiếm. Về mặt hình thức, tìm kiếm nghĩa là liên kết một tập con tài liệu với một truy vấn nếu chúng liên quan với nhau – tuân theo một tiêu chuẩn lựa chọn - đủ mạnh. Từ đó, chúng ta bắt buộc phải xem truy vấn là một tài liệu và tìm kiếm được định nghĩa dùng -lát cắt. 7
8. ▪ Định nghĩa 4.3: R.B. Yates và B.R. Neto Một mô hình tìm kiếm thông tin là một bộ bốn [D, Q, F, R(qi, dj)] trong đó: + D là một tập các tài liệu; + Q là một tập hợp các truy vấn của NSD; + F là một khung mô hình hóa các biểu diễn tài liệu, truy vấn và các quan hệ giữa chúng; + R(qi, dj) là một hàm sắp xếp liên kết một số thực với một truy vấn qi Q và một biểu diễn tài liệu dj D. Hàm sắp xếp xác định thứ tự giữa các tài liệu đối với truy vấn qi. 8
9. Khảo sát 3 kiểu truy vấn: ▪ Truy vấn Boole BQ truyền thống; ▪ Truy vấn xếp hạng RQ; ▪ Mô hình tìm kiếm thông tin xác suất. 4.2 TRUY VẤN BOOLE BQ 4.2.1 Truy vấn BQ hội Dạng t1 AND t2 AND AND tr 4.2.2 Truy vấn BQ không hội Dạng phổ biến khác là một phép hội của các phép tuyển: (text OR data OR information) AND (search OR seek) AND (retrieval OR indexing) 9
10. 4.3 TRUY VẤN XẾP HẠNG RQ 4.3.1 So khớp toạ độ Đếm số thuật ngữ truy vấn xuất hiện trong mỗi một tài liệu 4.3.2 Tích trong độ tương tự Quá trình được hình thức hoá bằng một tích trong của một vectơ truy vấn với một tập vectơ tài liệu Độ tương tự của truy vấn Q với tài liệu Dd được biểu diễn như sau: . S(Q, Dd) = Q Dd (4.5) trong đó: phép toán . là phép tích trong Tích trong của hai n-vectơ X = và Y = được định nghĩa: n X.Y =  xiyi i=1 (4.6) 10
11. Bảng 4.1 – Các vectơ đối với tính toán tích trong (a) Vectơ tài liệu, (b) Vectơ truy vấn. Vectơ tài liệu Wd,t D inf ret sea indexing bui index inv file (a) 1 1 1 1 1 0 0 0 0 2 0 0 0 1 1 1 0 0 3 0 0 0 0 0 1 1 1 4 0 0 0 1 1 0 1 1 searching 0 0 1 0 0 0 0 0 (b) indexing 0 0 0 1 0 0 0 0 11
12. Ví dụ: . S(indexing, D1) = (0, 0, 0, 1, 0, 0, 0, 0) (1, 1, 1, 1, 0, 0, 0, 0) = 1 ✓ Cách tiếp cận so khớp toạ độ có 3 hạn chế: 1. Không tính đến tần suất thuật ngữ 2. Không tính đến sự khó tìm thuật ngữ 3. Các tài liệu dài với nhiều thuật ngữ ▪ Bài toán 1 có thể được giải quyết bằng cách thay thế đánh giá “có” hoặc “không” nhị phân bằng một số nguyên chỉ thị thuật ngữ xuất hiện bao nhiêu lần trong tài liệu. 12
13. − Định nghĩa tần suất bên trong tài liệu của thuật ngữ fd,t : Số đếm chỉ thị số lần thuật ngữ xuất hiện trong tài liệu Ví dụ: Tính độ tương tự đối với truy vấn mẫu trở thành S(information retrieval, D1) = (1, 1, 0, 0, 0, 0, 0, 0,) . (1, 1, 1, 1, 0, 0, 0, 0) = 2 vì tài liệu D1 chứa information 1 lần và retrieval 1 lần. − Tổng quát hơn, thuật ngữ t trong tài liệu d có thể được gán một trọng số tài liệu - thuật ngữ, ký hiệu là wd,t và trọng số khác wq,t trong vectơ truy vấn 13
14. − Độ tương tự là tích trong của hai trọng số wd,t và wq,t – lấy tổng của tích các trọng số của các thuật ngữ truy vấn và thuật ngữ tài liệu tương ứng: n S(Q, D ) = Q . D =  w q,t  w d,t (4.7) d d t=1 Nếu wq,t = 0 thì (nếu t không xuất hiện trong Q) độ tương tự như ∑ wq,t  wd,t sau: S(Q, Dd) = t∈Q (4.8) ▪ Bài toán 2 không tính đến các thuật ngữ khó tìm. Một tài liệu với đủ lần xuất hiện của một thuật ngữ phổ biến luôn được xếp hạng đầu tiên nếu truy vấn chứa thuật ngữ đó, khổng kể các từ khác, bằng cách lấy trọng số thuật ngữ tuân theo tần suất tài liệu đảo IDF. 14
15. − Zipf quan sát tần suất của một mục tin có xu hướng là tỉ lệ nghịch với hạng của nó. Tức là, nếu hạng được coi là một độ đo tầm quan trọng thì trọng số wt của một thuật ngữ t được tính như sau: 1 wt = (4.9) ft trong đó: ft là số tài liệu chứa thuật ngữ t. − Trọng số thuật ngữ wt được sử dụng theo 3 cách khác nhau: 1. Có thể được nhân với một giá trị tần suất thuật ngữ tương đối rd,t để sinh ra trọng số tài liệu-thuật ngữ wd,t , trong đó rd,t có thể được tính theo một số cách khác nhau. 2. Trọng số thuật ngữ có thể được tổ hợp bằng cách nhân với rq,t sinh ra một trọng số truy vấn-thuật ngữ wq,t 3. Có thể được dùng trong cả hai tính toán wd,t và wq,t , tức là, áp dụng hai lần. Không công thức nào ở trên là khả năng duy nhất được dùng đối với wt , thành phần IDF. 15
16. ▪ Luật TFxIDF: tần suất thuật ngữ nhân tần suất tài liệu đảo. Các vectơ tài liệu được tính như sau: wd,t = rd,t (4.12) hoặc wd,t = rd,t . wt (TF x IDF) ✓ Chú ý: + Các thành phần TF và IDF không nên hiểu theo nghĩa đen là các hàm đưa ra tên của chúng. Một heuristic độ tương tự được gọi là “TF x IDF” bất kỳ khi dùng tần suất thuật ngữ fd,t tăng đều và tần suất tài liệu của thuật ngữ ft giảm đều. + Các trọng số truy vấn-thuật ngữ wq,t được tính tương tự 16
17. − Nhân tử chuẩn hoá để không kể đến phần đóng góp của các tài liệu dài. Do đó, luật tích trong đánh giá độ tương tự bằng  t Q wq,t  wd,t S(Q,Dd ) = (4.14) Dd trong đó Dd =  i fd,i là độ dài của tài liệu Dd 17
18. 4.3.3 Mô hình không gian vectơ Độ tương tự đối với một cặp vectơ là khoảng cách Euclide: n 2 S(Q,Dd ) =  w q,t − w d,t (4.15) t=1 Hướng chỉ thị bởi 2 vectơ n x y X  Y  i i i=1 (4.18) cos  = = n n X Y 2 2  x i  yi i=1 i=1 Công thức có 2 hàm ý: 1. Chứng minh sự chuẩn hoá: Nhân tử chuẩn hoá là độ dài Euclide của tài liệu 2. Cung cấp một sự trực quan rõ ràng của luật xếp hạng 18
19. Luật cosin đối với xếp hạng: 1 n Q Dd cos(Q,D ) = = ∑w q,t w d,t d t =1 Wq Wd Q Dd (4.19) n trong đó 2 Wd =  w d,t t=1 (4.20) là độ dài Euclide – trọng số – của tài liệu d và n 2 (4.21) Wq = ∑wq,t t=1 là trọng số của truy vấn q. Độ tương tự: 1 N cos(Q,Dd ) =  (1+ log e f d,t ) log e 1+ t QD Wd Wq d f t (4.22) 19
20. 4.4 ĐỘ ĐO COSIN 4.4.1 Tần suất bên trong tài liệu 4.4.2 Tính độ đo cosin Xét lại công thức (4.22) đối với độ đo cosin: 1 N cos(Q,Dd ) =  (1+ loge fd,t )loge 1+ WdWq t QDd ft 4.4.3. Bộ nhớ dành cho trọng số tài liệu 4.4.4. Sắp xếp 20
21. Giải thuật 4.2 Tìm kiếm r tài liệu dùng độ đo cosin, 1. Đặt A  { }. A là tập thanh tích luỹ. 2. Đối với mỗi một thuật ngữ truy vấn t Q, (a) Truy gốc từ t. (b) Tìm kiếm từ vựng. (c) Ghi ft và địa chỉ của It , mục vào IF đối với t. (d) Đặt wt  1 + loge(N / ft). (e) Đọc mục vào IF It. (f) Đối với mỗi một cặp (d, fd,t) thuộc It , i> Nếu Ad A thì Đặt Ad  0 , Đặt A  A + {Ad}. ii> Đặt Ad  Ad + loge(1 + fd,t) * wt. 21
22. 3. Đối với mỗi một Ad A, Đặt Ad  Ad / Wd. Bây giờ Ad tỉ lệ với giá trị cos(Q, Dd). 4. Đối với 1 i r, (a) Lựa chọn d sao cho Ad = max{A}. (b) Dò tìm địa chỉ của tài liệu d. (c) Tìm kiếm tài liệu d và trình bày với NSD. (d) Đặt A  A - {Ad}. Giải thuật nêu lên 3 điểm như sau: 1. Wq bị bỏ qua vì Wq là một hằng số 2. lượng lớn bộ nhớ được sử dụng 3. chỉ r << N tài liệu có mặt 22
23. 4.5 MÔ HÌNH TÌM KIẾM THÔNG TIN XÁC SUẤT ▪ Nguyên lý xếp hạng theo xác suất do Robertson đưa ra (probability ranking principle): Nếu đáp ứng của một hệ tìm kiếm thông tin với mỗi một yêu cầu của NSD là một dãy các tài liệu sắp xếp theo thứ tự giảm dần của các xác suất liên quan, các xác suất ở đây được đánh giá là độ chính xác có thể trên CSDL có sẵn thì toàn bộ hiệu quả của hê đối với NSD sẽ là tốt nhất trên CSDL đó. ▪ Mô hình tìm kiếm thông tin xác suất như sau: Định nghĩa 4.4 (PIR): Mô hình tìm kiếm thông tin xác suất PIR là một MIR S = thỏa mãn điều kiện sau đây: C = 2 (4.29) Chúng ta lấy C = 2 là vì ở mô hình IR xác suất truyền thống có 2 tiêu chuẩn: có liên quan và không liên quan. 23
24. ▪ Định nghĩa 4.5 (PIR): định nghĩa 4.4 có thể được định nghĩa lại như sau: Mô hình tìm kiếm thông tin xác suất PIR là một MIR S = trong đó: C = 2 và (q) = {|ãi(q,) ãj(q, )}, j = i + (-1)i+1, ãi(q, ) > i}. (4.30) ▪ Định nghĩa 4.6 (mô hình tìm kiếm thông tin xác suất kinh điển) Cho D là một tập tài liệu, q D một truy vấn và P(R|(q, d)) xác suất tài liệu d D là có liên quan /không liên quan với truy vấn q tương ứng. Cho R(q) là tập tài liệu tìm kiếm đáp ứng truy vấn q. Một tài liệu d được lựa chọn đáp ứng một truy vấn q nếu P(R|(q, d)) P(I|(q, d)) (Luật quyết định Bayes) (4.31) 24
25. nghĩa là, R(q) = {d| P(R|(q, d)) P(I|(q, d))} (4.32) − Chính xác hơn, P(R|(q, d)) và P(I|(q, d)) là xác suất liên đới tới d khi nó được xét có liên quan và không liên quan tới q tương ứng. − Đánh giá P(R|(q, d)) và P(I|(q, d)) dựa vào công thức Bayes. Cho D là một tập đối tượng, một đối tượng cố định bất kỳ q D và hai tiêu chuẩn ã1 và ã2 là liên quan và không liên quan tương ứng. Cho ãi(q, ), i = 1, 2 là mức độ mà một đối tượng bất kỳ d D thỏa mãn tiêu chuẩn ãi liên quan tới q. ▪ Định nghĩa 4.7 (PIR): Mô hình tìm kiếm thông tin xác suất PIR là một MIR S = trong đó: (q) = {|ã1(q,) ã2(q, )}, ã1(q, ) > 1} (4.33) 25
26. − PIR là một trường hợp đặc biệt của MIR (ở định nghĩa 4.5, lấy i =1). − S. Dominich đã chứng minh PIR ở định nghĩa 4.7 và mô hình tìm kiếm thông tin xác suất kinh điển ở định nghĩa 4.6 là tương đương. Bảng 4.4 – Các xác suất có điều kiện. Số tài liệu Có liên Không Tổng quan liên quan Thuật ngữ t có mặt Rt ft - Rt ft Thuật ngữ t R - Rt N - ft - (R - Rt) N - ft vắng mặt Tổng R N – R N 26
27. − Các xác suất có điều kiện có thể được đánh giá từ bảng 4.4. P [có liên quan | thuật ngữ t có mặt] = Rt / ft (4.34) và P [không liên quan | thuật ngữ t có mặt] = (ft – Rt) / ft Tương tự, P [thuật ngữ t có mặt | có liên quan] = Rt / R (4.35) và P [thuật ngữ t có mặt | không liên quan] = (ft – Rt) / (N – R)  trọng số wt đối với thuật ngữ t nhận được dùng công thức Bayes: R t /(R − R t ) w t = (ft − R t ) /(N − ft − (R − R t )) 27 (4.36)
28. ▪ SỰ PHẢN HỒI LIÊN QUAN − Là quá trình sửa đổi truy vấn để nâng cao hiệu suất tìm kiếm − Salton, Buckley và Harman đề xuất phương pháp lặp lại truy vấn. Tất cả sử dụng biểu diễn vectơ, trong đó tài liệu Dd và truy vấn Q đều được coi là n-vectơ trọng số, trong đó n là số thuật ngữ truy vấn riêng biệt. Chiến lược đơn giản nhất như sau: Qi+1 = Qi − Dn +  Dd d R (4.39) trong đó: + Dn là tài liệu xếp hạng cao nhất không liên quan; + R là tập tài liệu có liên quan. 28
29. ▪ Các biểu thức phản hồi tổng quát hơn cho phép một số lớn hơn trong những tài liệu không liên quan ảnh hưởng đến truy vấn mới và bao hàm dự trữ sẵn cho truy vấn ban đầu nhằm ảnh hưởng đến tất cả truy vấn tiếp theo: Qi+1 = Q0 + Qi + Dd + Dd d R d I (4.40) trong đó: , ,  và  là các hằng trọng số (với  0); R là tập con tài liệu có liên quan; I là một tập con tài liệu không liên quan bởi vì đáp ứng của NSD với các phép lặp truy vấn. 29
30. 4.6 ĐÁNH GIÁ HIỆU SUẤT TÌM KIẾM 4.6.1 Độ chính xác và độ phục hồi Độ chính xác P của một phương pháp xếp hạng đối với điểm cắt nào đó r là một phần trong số tài liệu xếp hạng cao nhất r có liên quan đến truy vấn: so tai lieu tim kiem co lien quan P = (4.41) tong so tai lieu tim kiem Độ phục hồi R của một phương pháp tại giá trị r nào đó là tỷ lệ của tổng số tài liệu có liên quan được tìm kiếm trong r cao nhất: so tai lieu co lien quan duoc tim kiem R = tong so tai lieu co lien quan (4.42) 30
31. ▪ Độ chính xác P: N P = R  (4.41’) ▪ Độ phục hồi R: N R = R NT (4.42’) trong đó: NT là tổng số tài liệu có liên quan tới một truy vấn q, NT 0; | (q) | =  là số tài liệu tìm kiếm được đáp ứng q,  0; NR là số tài liệu có liên quan tìm kiếm được. ▪ Định đề: Tỉ số giữa độ phục hồi và độ chính xác R / P thay đổi tuyến tính đối với . Chứng minh: NR = R NT = P  R / P =  / NT (4.43) 31
32. 4.6.2 Đường cong độ phục hồi-độ chính xác Hình 4.1 – Đường cong P-R đối với hạng của bảng 3.2 Đuong cong P-R doi voi hang 120 100 80 R (%) P 60 P (%) 40 20 0 R Do thi hieu suat tinh toan 200 150 do chinh xac P 100 do phuc hoi 50 0 R 32
33. ❑ TÀI LIỆU THAM KHẢO 1. Đỗ Quang Vinh (2009), Thư viện số - Chỉ mục và Tìm kiếm, Nxb Đại học Quốc gia Hà Nội. 2. Lourdes T.D. (2006), Thư viện số và truy cập mở tài liệu lưu trữ, Nguyễn Xuân Bình và nnk biên dịch, UNESCO, Hà Nội. 3. The 10th International Conference on Digital Libraries (2007), Asian Digital Libraries: Looking Back 10 years and Forging New Frontiers, Ha Noi 4. Tài liệu hướng dẫn cài đặt, sử dụng và phát triển của hệ phần mềm thư viện số Greenstone 5. Arms W.Y. (2003), Digital Libraries, MIT Press, Cambridge. 6. Fox E.A. (2000), Advanced Digital Libraries, Virginia Polytechnic Institue and State University. 7. Lesk M. (2005), Understanding Digital Libraries, 2nd Edition, Morgan Kaufmann, San Francisco. 8. Witten I.H., Bainbridge D. (2003), How to Build a Digital Library, Morgan Kaufmann, San Francisco. 33
34. KẾT THÚC ! TRÂN TRỌNG CÁM ƠN ! 34