Tìm kiếm và truy xuất thông
tin(Information Retrieval)

1


Nội dung








Đặt bài toán IR ?
Các quá trình xử lý trong IR?
Lập chỉ mục (Indexing)
Thu thập và tìm kiếm (Retrieval)
Đánh giá hệ thống (System evaluation)
Một số hướng nghiên cứu hiện nay?
Báo cáo môn học?
2


1. Bài toán IR


Mục tiêu = tìm tập tài liệu phù hợp từ tập rất lớn
các tài liệu để có được thông tin thích hợp.
Info.

- Khó khăn trong khi phát triển hệ thống.
2. Sử dụng kỹ thuật Indexing: (*)
- Thực hiện nhanh vì tài liệu được tìm thông
qua index.
- Mềm dẻo và dễ dàng cải tiến
5


Indexing-based IR
Document

Query

indexing

indexing
(Query analysis)

Representation
(keywords)

Query
evaluation

Representation
(keywords)

6



diễn trong của tài liệu.
Các nhân tố xem xét:







Độ chính xác của phương pháp biểu diễn ngữ nghĩa(semantics)
Tính toàn diện (Exhaustiveness) hay mức độ bao phủ(cover)
đến tất cả nội dung
Khả năng thực thi trên máy tính

Phương pháp nào biểu diễn tốt nhất nội dung tài liệu





Coverage
(Recall)

Char. string (char trigrams): không đủ độ chính xác
Word: độ bao phủ tốt, độ chính xác thấp
Phrase: độ bao phủ thấp, độ chính xác cao
Concept: độ bao phủ thấp, độ chính xác cao
String

Word

9


Lược đồ ước lượng trọng số tf*idf


tf (term frequency): tần xuất xuất hiện từ




df (document frequency): tần xuất tài liệu





Tần xuất xuất hiện của từ bằng thương giữa số lần xuất hiện từ và
tổng số từ trong một tài liệu. Giá trị tf cao phản ánh từ đó quan trọng.
Số lượng tài liệu chứa đựng từ
Phân bố của từ trên toàn bộ tài liệu

idf (inverse document frequency): tần xuất nghịch đảo



Sự thay đổi phân bố của từ trên toàn bộ tài liệu
Sự riêng biệt của từ đối với mỗi tài liệu

The more the term is distributed evenly, the less it is specific to a document



Từ dừng (Stopwords /
Stoplist)




Một số từ không đem theo thông tin ví dụ
of, in, about, with, I, although, …
Stoplist: contain stopwords, not to be used as index









Giới từ (Prepositions)
Mạo từ (Articles)
Đại từ (Pronouns)
Một số phó từ và tính từ (Some adverbs and adjectives)
Một số từ thông dụng (e.g. document)

Lược bỏ stopwords thường nâng cao hiệu quả cho IR.
Một số ít stoplists được sử dụng (e.g compare,
however…).
12

Porter algorithm
(Porter, M.F., 1980, An algorithm for suffix stripping,
Program, 14(3) :130-137)


Step 1: Gặp số nhiều hoặc động tính từ quá khứ:







(m>0) ICATE -> IC

triplicate -> triplic

Step 4:





(m>0) OUSNESS -> OUS callousness -> callous
(m>0) ATIONAL -> ATE
relational -> relate

Step 3:



controll -> control
14


Kết quả của indexing


Mỗi văn bản được biểu diễn bởi tập trọng số các từ
khóa keywords (terms):
D1  {(t1, w1), (t2,w2), …}
e.g. D1  {(comput, 0.2), (architect, 0.3), …}
D2  {(comput, 0.1), (network, 0.5), …}



Đảo ngược lại biểu diễn file:
comput  {(D1,0.2), (D2,0.1), …}
Đây chính là dữ liệu đầu vào được sử dụng trong tìm kiếm
và thu thập thông tin một cách hiệu quả.
15


4. Retrieval


Những vấn đề cơ bản của retrieval


Mô hình tìm kiếm và thu thập


Kết hợp với một số danh sách từ?
Làm thể nào để ước lượng trọng số?
17


Các mô hình IR


Mô hình đối sánh điểm (Matching score)






Tài liệu D = tập các từ khóa đã được đánh
trọng số.
Câu hỏi Q = tập các từ khóa chưa được
đánh trọng số.
Kết quả tìm kiếm: R(D, Q) = i w(ti , D)
trong đó ti là từ khóa trong Q.

18


Mô hình logic







D là thành viên của lớp ti với mức độ wi.
Trong tập mờ: ti(D) = wi

Một số đánh giá có thể dùng:
R(D,
R(D,
R(D,
R(D,

ti) = ti(D);
Q1  Q2) = min(R(D, Q1), R(D, Q2));
Q1  Q2) = max(R(D, Q1), R(D, Q2));
Q1) = 1 - R(D, Q1).
20


Mô hình không gian Vector








Vector space = tập tất cả các từ khóa có được
<t1, t2, t3, …, tn> //rất lớn
Tài liệu:


tn
a1n
a2n
a3n

am1 am2 am3 …
b1 b2 b3 …

amn
bn

Term vector
space

22


Một số cách đo độ tương tự
Dot product

Sim( D, Q)   (ai * bi )

t1

 (a * b )
i

Cosine


D

i

2

i

 (a * b )
Sim( D, Q) 
 a   b   (a * b )
i

i

i

2

2

i

i

i

i

i

( t i  xi )D

x

  P(ti  1 | R ) xi P(ti  0 | R) (1 xi )   pi i (1  pi ) (1 xi )
ti

ti
x

P ( D | NR )   P(ti  1 | NR) xi P(ti  0 | NR) (1 xi )   qi i (1  qi ) (1 xi )
ti

ti

24


Prob. model
Xếp hạng tài liệu
x

P( D | R)
Odd ( D)  log
 log
P( D | NR)

(1 xi )
i
p

pi (1  qi )
  xi log
qi (1  pi )
ti
25