BÀI GIẢNG THƯ VIỆN SỐ 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 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 đánh giá thông tin có liên quan tới nhu cầu thông tin NSD  Mô hình IR tổng quát cặp bao gồm đối tượng ánh xạ liên kết (“tìm kiếm”) số đối tượng với đối tượng đại diện cho truy vấn Cho D = {d1, d2, , dM}, M ≥ (4.1) tập hữu hạn không rỗng đối tượng  Chú ý: trường hợp M = xem xét tầm thường Các đối tượng tiêu biểu đại diện Cho ℜ ánh xạ tìm kiếm từ D vào lực lượng ρ(D), nghĩa là, ℜ : D → ρ(D) (4.2) Bằng cách kết hợp tập đối tượng D ánh xạ tìm kiếm ℜ, định nghĩa cấu trúc tìm kiếm thông tin 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 S = (4.3) Định nghĩa 4.1 định nghĩa tổng quát: không đề cập đến dạng riêng biệt ánh xạ tìm kiếm ℜ đối tượng D Từ đó, mô hình IR riêng biệt khác nhận cách đặc tả D ℜ  Đị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 SIR S = với thuộc tính sau đây: i q = δ ⇒ µãi(q, δ) = ∀i, q, δ (tính phản xạ); (4.4) ii ℜi (q) = {δ ∈ D| µãi(q, δ) = max µãk(q, δk)}∩ aαi, i cố định tùy ý đó: + T = {t1, t2, , tN} tập hữu hạn thuật ngữ mục, N ≥ 1; + O = {o1, o2, , oU} tập hữu hạn đối tượng, U ≥ 2; + (Dj)j ∈ J = {1, 2, , M} họ cluster đối tượng, Dj ∈ ρ(O), M ≥ 2; + D = {δj| j ∈ J} tập tài liệu, 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 đại diện cluster cluster đối tượng Dj + A = {ã1, , ãC} tập hữu hạn tiêu chuẩn, C ≥ 1, ãi = {((q, δj), µãi(q, δj)) | δj∈ D, j =1, , M}, i = 1, , C 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) có tiêu chuẩn rõ ràng: i có mặt mặt; ii tìm kiếm thực dựa vào (i) + aαi = {δ ∈ D| µãi(q, δ) > αi}, i = 1, , C αi-lát cắt tiêu chuẩn mạnh ãi, αi ≥ 0, q ∈ D cố định tùy ý; + ℜ : D → ρ(D) ánh xạ tìm kiếm Về mặt hình thức, tìm kiếm nghĩa liên kết tập tài liệu với truy vấn chúng liên quan với – tuân theo tiêu chuẩn lựa chọn đủ mạnh Từ đó, bắt buộc phải xem truy vấn tài liệu tìm kiếm định nghĩa dùng α-lát cắt  Định nghĩa 4.3: R.B Yates B.R Neto Một mô hình tìm kiếm thông tin bốn [D, Q, F, R(qi, dj)] đó: + D tập tài liệu; + Q tập hợp truy vấn NSD; + F khung mô hình hóa biểu diễn tài liệu, truy vấn quan hệ chúng; + R(qi, dj) hàm xếp liên kết số thực với truy vấn qi ∈ Q biểu diễn tài liệu dj ∈ D Hàm xếp xác định thứ tự tài liệu truy vấn qi Khảo sát 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 phép hội phép tuyển: (text OR data OR information) AND (search OR seek) AND (retrieval OR indexing) 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 tài liệu 4.3.2 Tích độ tương tự Quá trình hình thức hoá tích vectơ truy vấn với tập vectơ tài liệu Độ tương tự truy vấn Q với tài liệu Dd biểu diễn sau: S(Q, Dd) = Q Dd (4.5) đó: phép toán phép tích n = Y = định Tích hai n-vectơ X i X.Y = ∑ x i yi i i =1 nghĩa: 10 4.4 ĐỘ ĐO COSIN 4.4.1 Tần suất bên tài liệu 4.4.2 Tính độ đo cosin Xét lại công thức (4.22) độ đo cosin:  N cos(Q, Dd ) = ∑ (1 + log e f d, t ) ⋅ log e  +  Wd Wq 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 Giải thuật 4.2 Tìm kiếm r tài liệu dùng độ đo cosin, Đặt A ← { } A tập tích luỹ Đối với 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 địa It , mục vào IF t (d) Đặt wt ← + loge(N / ft) (e) Đọc mục vào IF It (f) Đối với cặp (d, fd,t) thuộc It , i> Nếu Ad ∈ A Đặt Ad ← , Đặt A ← A + {Ad} ii> Đặt Ad ← Ad + loge(1 + fd,t) * wt 21 Đối với Ad ∈ A, Đặt Ad ← Ad / Wd Bây Ad tỉ lệ với giá trị cos(Q, Dd) Đối với ≤ i ≤ r, (a) Lựa chọn d cho Ad = max{A} (b) Dò tìm địa tài liệu d (c) Tìm kiếm tài liệu d trình bày với NSD (d) Đặt A ← A - {Ad} Giải thuật nêu lên điểm sau: Wq bị bỏ qua Wq số lượng lớn nhớ sử dụng r α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 tập tài liệu, q ∈ D truy vấn P(R|(q, d)) xác suất tài liệu d ∈ D có liên quan /không liên quan với truy vấn q tương ứng Cho R(q) tập tài liệu tìm kiếm đáp ứng truy vấn q Một tài liệu d lựa chọn đáp ứng truy vấn q P(R|(q, d)) ≥ P(I|(q, d)) (Luật định Bayes) (4.31) 24 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)) P(I|(q, d)) xác suất liên đới tới d xét có liên quan không liên quan tới q tương ứng − Đánh giá P(R|(q, d)) P(I|(q, d)) dựa vào công thức Bayes Cho D tập đối tượng, đối tượng cố định q ∈ D hai tiêu chuẩn ã1 ã2 liên quan không liên quan tương ứng Cho µãi(q, δ), i = 1, mức độ mà đối tượng 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 MIR S = đó: ℜ(q) = {δ|µã1(q,δ) ≥ µã2(q, δ)}, µã1(q, δ) > α1} (4.33) 25 − PIR trường hợp đặc biệt MIR (ở định nghĩa 4.5, lấy i =1) − S Dominich chứng minh PIR định nghĩa 4.7 mô hình tìm kiếm thông tin xác suất kinh điển định nghĩa 4.6 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 quan Không liên quan Tổng Thuật ngữ t có mặt Rt ft - R t ft Thuật ngữ t vắng mặt R - Rt N - ft - (R - Rt) N - ft Tổng R N–R N 26 − Các xác suất có điều kiện đánh giá từ bảng 4.4 P [có liên quan | thuật ngữ t có mặt] = Rt / ft (4.34) 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) P [thuật ngữ t có mặt | không liên quan] = (ft – Rt) / (N – R)  trọng số wt thuật ngữ t nhận dùng công thức R t /(R − R t ) Bayes: wt = (f t − R t ) /( N − f t − (R − R t )) 27  SỰ PHẢN HỒI LIÊN QUAN − Là trình sửa đổi truy vấn để nâng cao hiệu suất tìm kiếm − Salton, Buckley Harman đề xuất phương pháp lặp lại truy vấn Tất sử dụng biểu diễn vectơ, tài liệu Dd truy vấn Q coi n-vectơ trọng số, n số thuật ngữ truy vấn riêng biệt Chiến lược đơn giản sau: Qi +1 = Qi − Dn + ∑ Dd d∈ R (4.39) đó: + Dn tài liệu xếp hạng cao không liên quan; + R tập tài liệu có liên quan 28  Các biểu thức phản hồi tổng quát cho phép số lớn tài liệu không liên quan ảnh hưởng đến truy vấn bao hàm dự trữ sẵn cho truy vấn ban đầu nhằm ảnh hưởng đến tất truy vấn tiếp theo: Q i +1 = π Q + ω Q i + λ ∑ D d + η ∑ D d d∈ R d∈ I (4.40) đó: π, ω, λ η trọng số (với η ≤ 0); R tập tài liệu có liên quan; I tập tài liệu không liên quan đáp ứng NSD với phép lặp truy vấn 29 4.6 ĐÁNH GIÁ HIỆU SUẤT TÌM KIẾM 4.6.1 Độ xác độ phục hồi Độ xác P phương pháp xếp hạng điểm cắt r phần số tài liệu xếp hạng cao r có liên quan đến truy vấn: so tai lieu tim kiem co lien quan P = tong so tai lieu tim kiem (4.41) Độ phục hồi R phương pháp giá trị r tỷ lệ tổng số tài liệu có liên quan tìm kiếm r cao nhất: so tai lieu co lien quan duoc tim kiem R = tong so tai lieu co lien quan (4.42) 30  Độ xác P:  Độ phục hồi R: NR P= κ (4.41’) NR R= NT (4.42’) đó: NT tổng số tài liệu có liên quan tới truy vấn q, NT ≠ 0; | ℜ(q) | = κ số tài liệu tìm kiếm đáp ứng q, κ ≠ 0; NR số tài liệu có liên quan tìm kiếm  Định đề: Tỉ số độ phục hồi độ xác R / P thay đổi tuyến tính κ Chứng minh: NR = R N T = P κ ⇒ R / P = κ / N T (4.43) 31 4.6.2 Đường cong độ phục hồi-độ xác Hình 4.1 – Đường cong P-R hạng bảng 3.2 Đuong cong P-R doi voi hang 120 100 P 80 R (%) P (%) 60 40 20 R Do thi hieu suat tinh toan 200 P 150 chinh xac 100 phuc hoi 50 R 32  TÀI LIỆU THAM KHẢO Đỗ Quang Vinh (2009), Thư viện số - Chỉ mục Tìm kiếm, Nxb Đại học Quốc gia Hà Nội Lourdes T.D (2006), Thư viện số truy cập mở tài liệu lưu trữ, Nguyễn Xuân Bình nnk biên dịch, UNESCO, Hà Nội The 10th International Conference on Digital Libraries (2007), Asian Digital Libraries: Looking Back 10 years and Forging New Frontiers, Ha Noi Tài liệu hướng dẫn cài đặt, sử dụng phát triển hệ phần mềm thư viện số Greenstone Arms W.Y (2003), Digital Libraries, MIT Press, Cambridge Fox E.A (2000), Advanced Digital Libraries, Virginia Polytechnic Institue and State University Lesk M (2005), Understanding Digital Libraries, 2nd Edition, Morgan Kaufmann, San Francisco Witten I.H., Bainbridge D (2003), How to Build a Digital Library, Morgan Kaufmann, San Francisco 33 KẾT THÚC ! TRÂN TRỌNG CÁM ƠN ! 34 ... 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... nhiều thuật ngữ  Bài toán giải cách thay đánh giá “có” “không” nhị phân số nguyên thị thuật ngữ xuất lần tài liệu 12 − Định nghĩa tần suất bên tài liệu thuật ngữ fd,t : Số đếm thị số lần thuật ngữ... ngữ t tài liệu d gán trọng số tài liệu - thuật ngữ, ký hiệu wd,t trọng số khác wq,t vectơ truy vấn 13 − Độ tương tự tích hai trọng số wd,t wq,t – lấy tổng tích trọng số thuật ngữ truy vấn thuật