Bài giảng Thư viện số: Chương 4 - TS. Đỗ Quang Vinh

Chia sẻ: Bin Bin | Ngày: | Loại File: PPT | Số trang:34

Thêm vào BST

Báo xấu

142
lượt xem 12
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Chương 4 của Bài giảng Thư viện số giới thiệu đến người học các kiến thức về tìm kiếm thông tin với kết cấu nội dung trình bày mô hình tìm kiếm thông tin, truy vấn BOOLE BQ, truy vấn xếp hạng RQ, độ đo COSIN, mô hình tìm kiếm thông tin xác suất, đánh giá hiệu suất tìm kiếm.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Thư viện số: Chương 4 - TS. Đỗ Quang Vinh

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
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
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
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
 Đị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) ii. ℜi (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
+ 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; 6 ii. tìm kiếm được thực hiện dựa vào (i).
+ 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
 Đị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
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
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 n Tích trong của hai n-vectơ X = và Y = được định X.Y = ∑ x i yi nghĩa: i =1 10
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
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
− Đị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
− Độ 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, Dd) = Q . Dd = ∑w t=1 q, t ⋅ w d,t (4.7) Nếu wq,t = 0 thì (nếuw q , t ⋅ w dxuất hiện trong Q) độ tương tự ∑ t không , t t∈Q như sau: S(Q, Dd) = (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
− 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 15
 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. 16 + Các trọng số truy vấn-thuật ngữ wq,t được tính tương tự
− 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 w q , t ⋅ w d , t S(Q, D d ) = (4.14) Dd trong đó D d = ∑ i f d ,i là độ dài của tài liệu Dd 17
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, D d ) = ∑ w q , t − w d , t (4.15) t =1 Hướng chỉ thị bởi 2 vectơ n X⋅Y ∑ x i yi cos θ = = n i =1 n (4.18) XY ∑ x i2 ∑ y i2 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
Luật cosin đối với xếp hạng: Q ⋅ Dd = 1 ∑ w n w d,t cos(Q, D d ) = Wq Wd t =1 q,t 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à W = ∑w2 n (4.21) q q ,t t =1 là trọng số của truy vấn q. Độ tương tự: 1  N cos(Q, D d ) = ∑ (1 + log e f d , t ) ⋅ log e  1 +   f  Wd Wq t∈Q ∩ D d  t  (4.22) 19
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 + log e f d, t ) ⋅ log e  1 +   f  Wd Wq t∈Q∩ Dd  t 4.4.3. Bộ nhớ dành cho trọng số tài liệu 4.4.4. Sắp xếp 20