Vector Space Model là gì

ĐẠI HỌC GIAO THÔNG VẬN TẢI HCMC
BỘ MÔN CÔNG NGHỆ THÔNG TIN

BÁO CÁO
Môn học: chuyên đề công nghệ thông tin
Đề tài: Tìm hiểu về Information Retrieval

Nhóm sinh viên thực hiện:

Mã sinh viên:

1. Bùi Văn Hiệp [nhóm trưởng]

5451074036

2. Nguyễn Thị Kim Chi

5451074001

3. Nguyễn Tuấn Tiến

5451074016

4. Nguyễn Thảo Nhi

5451074058

5. Đinh Xuân Bằng

5451074022

Tp.HCM, Tháng 11 năm 2016


Trường đại học giao thông vận tải - HCMC

Mục lục
Mục lục .......................................................................................................................1
Chương 1. Giới thiệu về Information Retrieval .......................................................2
1.1. Khái niệm Information Retrieval [truy hồi thông tin]: .....................................2
1.2. Khái niệm Documents .....................................................................................2
1.3. Khái niệm Query.............................................................................................2
1.4. Best-Match Retrieval ......................................................................................3
Chương 2. Lịch sử hình thành và phát triển của IR ................................................4
2.1. Trước năm 1900: ............................................................................................4
2.2. Năm 1920 năm 1930 ..................................................................................4
2.3. Năm 1940 năm 1950 ..................................................................................4
2.4. Giữa những năm 1960 :...................................................................................7
2.5. Những năm 1970 ............................................................................................7
2.6. Những năm 1980 ............................................................................................8
2.7. Những năm 1990 ............................................................................................8
Chương 3. Cấu trúc hệ thống IR ..............................................................................9
3.1. Các thành phần trong hệ thống IR: ..................................................................9
3.2. Mô tả chi tiết một số thành phần trong hệ thống IR .........................................9
Chương 4. Phân loại hệ thống truy hồi thông tin................................................... 13
4.1. Phân loại hệ thống tìm kiếm thông tin ........................................................... 13
4.2. Hệ thống tìm kiếm dựa trên khái niệm [sematic search] ................................ 15
Chương 5. Một số kỹ thuật tìm kiếm ...................................................................... 19
5.1. Mô hình Boolean .......................................................................................... 19
5.2. Mô hình Boolean mở rộng [lập chỉ mục ngược] ............................................ 21
5.3. Mô hình không gian vector ........................................................................... 23


Information Retrieval

1


Chương 1: Giới thiệu về Information Retrieval

Chương 1. Giới thiệu về Information Retrieval
1.1. Khái niệm Information Retrieval [truy hồi thông tin]:
- Là tìm kiếm thông tin [thường là các tài liệu] ở một dạng phi cấu trúc [thông
thường là văn bản] thỏa mãn nhu cầu tìm kiếm thông tin từ trong những nguồn
thông tin lớn [được lưu trữ trên máy tính].
1.2. Khái niệm Documents

Văn bản, chuỗi các kí tự

Document

Hình ảnh

Bài báo, tạp chí

Âm thanh
Video
Hình 1.1. Các loại của document
1.3. Khái niệm Query
- Là thông tin cần thiết do người dùng nhập vào hệ thống

Information Retrieval


2


Chương 1: Giới thiệu về Information Retrieval

Dạng truy vấn logic
có giá trị đúng hoặc sai
EX: She is beautiful,
It is sunny and warm

Query

Bao gồm 2, 3 từ thậm
chí là nhiều các từ khóa
EX: dress, computer,
telephone

Cụm từ truy vấn
EX: information technology,
social organization, proffessional
environment.
Hình 1.2. Phân loại query
1.4. Best-Match Retrieval
- So sánh thuật ngữ trong một document và query.
- Tính độ tương quan giữa mỗi document trong kho tài liệu và query dựa trên thuật
ngữ mà chúng có điểm chung.
- Sắp xếp các documents theo thứ tự giảm dần độ tương quan với query.
- Kết quả đầu ra là một danh sách sắp xếp các documents và hiển thị đến người
dùng mà các documents có độ liên quan cao được đánh giá bởi hệ thống.


Hình 1.3. Information retrieval process

Information Retrieval

3


Chương 2: Lịch sử hình thành và phát triển của IR

Chương 2. Lịch sử hình thành và phát triển của IR
2.1. Trước năm 1900:
- 1801 : Joseph Marie Jacquard phát minh ra máy dệt Jacquard , máy đầu tiên sử
dụng thẻ đục lỗ để kiểm soát một chuỗi các hoạt động.
- Năm 1880 : Herman Hollerith phát minh ra một lập bảng dữ liệu cơ điện sử dụng
thẻ đục lỗ như một phương tiện có thể đọc được máy.
- 1890 Hollerith thẻ , keypunches và tabulators dùng để xử lý 1.890 US Census dữ
liệu.
2.2. Năm 1920 năm 1930
- Emanuel Goldberg nộp bằng sáng chế cho "Máy thống kê" của mình một công
cụ tìm kiếm tài liệu được sử dụng tế bào quang điện và nhận dạng mẫu để tìm
kiếm siêu dữ liệu trên cuộn văn bản microfilmed.
2.3. Năm 1940 năm 1950
- Cuối những năm 40 : Quân đội Mỹ phải đối mặt các vấn đề về lập chỉ mục và
tìm kiếm các tài liệu nghiên cứu khoa học trong chiến tranh bị bắt từ Đức.
- 1945 : As We May Think của Vannevar Bush xuất hiện trong Atlantic Monthly .
- 1947 : Hans Peter Luhn [kỹ sư nghiên cứu tại IBM kể từ năm 1941] bắt đầu làm
việc trên một hệ thống đấm thẻ dựa trên cơ cho việc tìm kiếm các hợp chất hóa
học.
- Năm 1950 : Trồng quan tâm tại Hoa Kỳ trong một "khoảng cách khoa học" với

Liên Xô thúc đẩy, khuyến khích tài trợ và cung cấp một bối cảnh cho các hệ
thống tìm kiếm tài liệu cơ [ Allen Kent] Và việc phát minh ra dẫn lập chỉ mục
[ Eugene Garfield].
- 1950 : Thuật ngữ "thu hồi thông tin" được đặt ra bởi Calvin Mooers..
- 1951 : Philip Bagley tiến hành các thí nghiệm đầu tiên trong thu hồi tài liệu trên
máy vi tính trong một luận án thạc sĩ tại MIT.
- 1955 : Allen Kent gia nhập Case Western Reserve University , và cuối cùng trở
thành phó giám đốc của Trung tâm Tư liệu và Nghiên cứu Truyền thông. Cùng
năm đó, Kent và các đồng nghiệp công bố một bài báo trong tài liệu của Mỹ mô
tả các biện pháp chính xác và thu hồi cũng như chi tiết một đề nghị "khủng" để

Information Retrieval

4


Chương 2: Lịch sử hình thành và phát triển của IR
đánh giá một hệ thống IR bao gồm các phương pháp lấy mẫu thống kê để xác
định số lượng các tài liệu liên quan không được lấy.
- 1958 : Hội nghị quốc tế về Thông tin Khoa học Washington DC bao gồm việc
xem xét các hệ thống hồng ngoại như một giải pháp cho vấn đề xác định. Xem: Kỷ
yếu của Hội nghị quốc tế về thông tin khoa học, 1958 [National Academy of
Sciences, Washington, DC, 1959]
- 1959 : Hans Peter Luhn xuất bản "Tự động-mã hóa dữ liệu để tìm kiếm thông
tin."
- Năm 1960: Melvin Earl Maron và John Lary Kuhns xuất bản On relevance,
probabilistic indexing, and information retrieval " trong Tạp chí của ACM 7 [3]:
216-244, tháng 7 năm 1960.
- 1962 :
- Cyril W. Cleverdon công bố những phát hiện ban đầu của nghiên cứu Cranfield,

phát triển một mô hình để đánh giá hệ thống IR. Xem: Cyril W. Cleverdon,
"Report on the Testing and Analysis of an Investigation into the Comparative
Efficiency of Indexing Systems" . Cranfield Collection Hàng không, Cranfield,
Anh, năm 1962.
- Kent xuất bản Information Analysis và Retrieval .
- 1963 :
- Báo cáo Weinberg "Khoa học, Chính phủ và Thông tin" đã đưa ra một phát âm
đầy đủ các ý tưởng về một "cuộc khủng hoảng thông tin khoa học." Báo cáo này
được đặt theo tên của Tiến sĩ Alvin Weinberg .
- Joseph Becker và Robert M. Hayes công bố văn bản về thông tin. Becker,
Joseph; . Hayes, Robert Mayo: Thông tin lưu trữ và truy xuất: công cụ, các yếu
tố, các lý thuyết . New York, Wiley [1963].
- 1964 :
- Karen Spärck Jones hoàn thành luận án của mình tại Cambridge, đồng nghĩa và
phân loại ngữ nghĩa, và tiếp tục công việc về ngôn ngữ học tính toán khi áp dụng
cho IR.
- Các Cục Tiêu chuẩn Quốc gia tài trợ cho một hội thảo mang tên "Hiệp hội thống
kê Phương pháp Tài liệu cơ giới." Một số bài báo rất quan trọng, bao gồm cả tài

Information Retrieval

5


Chương 2: Lịch sử hình thành và phát triển của IR
liệu tham khảo được xuất bản đầu tiên của G. Salton [we believe] cho hệ thống
thông minh.

Information Retrieval


6


Chương 2: Lịch sử hình thành và phát triển của IR
2.4. Giữa những năm 1960 :
- Thư viện Y khoa Quốc gia phát triển: MEDLARS y tế Phân tích Văn học và hệ
thống Retrieval, cơ sở dữ liệu máy tính có thể đọc được và truy hồi hệ thống lớn
đầu tiên.
- Dự án Intrex tại MIT.
- 1965 : JCR Licklider xuất bản Libraries of the Future.
- 1966 : Don Swanson đã tham gia vào nghiên cứu tại Đại học Chicago về yêu cầu
cho Catalogs tương lai.
- Cuối những năm 60 : F. Wilfrid Lancaster hoàn thành nghiên cứu đánh giá hệ
thống MEDLARS và xuất bản các ấn bản đầu tiên của văn bản của mình về thông
tin.
- 1968 :


Gerard Salton công bố Automatic Information Organization and
Retrieval .



John W. Sammon, báo cáo RADC Tech Jr. "Một số Toán học của thông
tin lưu trữ và Retrieval ..." phác thảo mô hình vector.

- 1969 : " A nonlinear mapping for data structure analysis " của Sammon [IEEE
giao dịch trên máy tính] đã đề nghị đầu tiên cho giao diện trực quan để một hệ
thống IR.
2.5. Những năm 1970

- Năm 1970 :


Trực tuyến đầu tiên hệ thống-NLM AIM-TWX, MEDLINE; Dialog của
Lockheed; ORBIT của SDC.



Theodor Nelson thúc đẩy khái niệm siêu văn bản , được công bố Computer
Lib/Dream Machines.

- 1971 : Nicholas Jardine và Cornelis J. van Rijsbergen xuất bản "The use of
hierarchic clustering in information retrieval", trong đó có kết nối "giả thuyết
cluster."
- 1975 : Ba ấn phẩm có ảnh hưởng lớn bởi Salton hoàn toàn khớp khuôn khổ và
phân biệt đối xử hạn mô hình xử lý vector của mình:


A Theory of Indexing [Society for Industrial and Applied Mathematics]

Information Retrieval

7


Chương 2: Lịch sử hình thành và phát triển của IR


A Theory of Term Importance in Automatic Text Analysis




A Vector Space Model for Automatic Indexing

- 1978 : Hội nghị ACM SIGIR đầu tiên
- 1979 : CJ Van Rijsbergen xuất bản Information Retrieval [Butterworths]. Nhấn
mạnh vào mô hình xác suất.
- 1979 : Tamas Doszkocs thực hiện các CITE giao diện người dùng ngôn ngữ tự
nhiên cho MEDLINE tại Thư viện Y khoa Quốc gia. Hệ thống CITE hỗ trợ đầu
vào truy vấn hình thức miễn phí, sản lượng xếp và thông tin phản hồi liên quan.
2.6. Những năm 1980
- 1980 : quốc tế đầu tiên hội nghị ACM SIGIR, liên doanh với tập đoàn British
Computer Society IR ở Cambridge.
- 1982 : Nicholas J. Belkin , Robert N. Oddy, và Helen M. Brooks đề xuất ASK
[Anomalous State of Knowledge] quan điểm cho thông tin. Đây là một khái niệm
quan trọng, dù công cụ phân tích tự động của họ đã chứng minh cuối cùng thất
vọng.
- 1983 : Salton [và Michael J. McGill] xuất bản Introduction to Modern
Information Retrieval [McGraw-Hill], với nhấn mạnh vào mô hình vector.
- 1985 : David Blair và Bill Maron xuất bản:

An Evaluation of Retrieval

Effectiveness for a Full-Text Document-Retrieval System
- Giữa những năm 1980 : Nỗ lực để phát triển các phiên bản của người dùng cuối
của hệ thống IR thương mại.
2.7. Những năm 1990
- 1992 : Hội nghị TREC diễn ra đầu tiên.
- 1997 : Công bố của Korfhage Information Storage and Retrieval với sự nhấn
mạnh vào hệ thống trực quan và đa điểm tham khảo.

- Cuối những năm 1990 : Công cụ tìm kiếm web thực hiện nhiều tính năng trước
đây chỉ được tìm thấy trong các hệ thống IR nghiệm. Công cụ tìm kiếm trở thành
instantiation phổ biến nhất và có lẽ tốt nhất của các mô hình IR.

Information Retrieval

8


Chương 3: Cấu trúc hệ thống IR

Chương 3. Cấu trúc hệ thống IR

Hình 3.1. Cấu trúc hệ thống IR
3.1. Các thành phần trong hệ thống IR:
- User interface: là giao diện người dùng nhằm mục đích giúp cho người dùng tìm
kiếm thông tin và nhận kết quả tìm kiếm thông tin
- Text operations: Là nơi tiếp nhận thông tin tìm kiếm của người dùng, sau đó xử
lý thông tin đó nhằm giúp cho hệ thống hiểu được thông tin mà người dùng hướng
tới.
- Query operation: các thao tác truy vấn dữ liệu nhằm tạo ra câu truy vấn sau đó
truy xuất thông tin trong hệ thống
- Searching: Sau khi truy vấn được xử lý thì hệ thống sẽ bắt đầu tìm kiếm thông
tin có trong hệ thống
- Ranking: Xếp hạng các tài liệu theo mức độ liên quan của thông tin, tài liệu nào
có mức độ liên quan càng cao thì sẽ nằm ở top.
- Indexing: Xây dựng chỉ mục cho tài liệu nhằm tăng tốc độ truy xuất thông tin,
giúp hệ thống trả về kết quả nào tốt nhất cho người dùng
- Database manager: Là nơi chứa dữ liệu các tài liệu trong hệ thống, khi người
dùng truy vấn đến hệ thống thì sẽ truy xuất thông tin từ đây để trả về kết quả hiển

thị cho người dùng.
3.2. Mô tả chi tiết một số thành phần trong hệ thống IR

Information Retrieval

9


Chương 3: Cấu trúc hệ thống IR
3.2.1. Giai đoạn tiền xử lý
Loại bỏ từ dừng
Ví dụ: Ta có đoạn tài liệu sau

Kết quả sau khi dùng phương pháp loại bỏ từ dừng:

Việc loại bỏ từ dừng có ý nghĩa làm giảm kích cỡ của tài liệu, đồng thời loại bỏ
những từ có tần xuất xuất hiện cao trong hầu hết các tài liệu mà những từ này lại
không mang nội dung có nghĩa. Một số từ dừng thông dụng như: a, the, it, of
Lấy gốc từ
Lấy gốc từ là quá trình thu gọn một từ về dạng ngữ pháp gốc của nó
Ví dụ:
Computes, computting, computer có gốc từ là compute.
Việc lấy gốc từ trước khi xây dựng chỉ mục có ưu điểm là làm giảm kích thước
chỉ mục và cho phép truy vấn tài liệu một cách dễ dàng hơn
Indexing [lập chỉ mục]
Sử dụng phương pháp inverted file.
Sẽ giúp hệ thống đọc được tài liệu, sau đó phân tích các từ trong tài liệu và gán chỉ
mục cho tài liệu đó, tài liệu nào có số chỉ mục càng cao thì tầm quan trọng của tài liệu
đó càng lớn.
Ví dụ: Ta có 2 tài liệu cần được phân tích như sau:


Information Retrieval

10


Chương 3: Cấu trúc hệ thống IR

Đầu tiên hệ thống sẽ phân tích từng từ trong tài liệu bằng cách lấy từ gốc, sau đó
đếm số lần xuất hiện của từng từ trong tài liệu

Bước tiếp theo là sắp xếp các từ ngữ vừa phân tích được theo bảng chữ cái
alphabet
Kết quả cuối cùng của việc lập chỉ mục cho tài liệu, tần số xuất hiện của từ chính
là chỉ mục của tài liệu:

Information Retrieval

11


Chương 3: Cấu trúc hệ thống IR

3.1.2. Giai đoạn thu thập thông tin
Query operation: Nhu cầu truy xuất thông tin của người dùng thường được phát
biểu ở dạng ngôn ngữ tự nhiên, tập các từ khóa, đây là bước quan trọng vì nó giúp cho
hệ thống hiểu được cái mà người dùng đang cần là gì, từ đó đáp ứng được nhu cầu đó.
Để hiểu được yêu cầu của người dùng, thì hệ thống sẽ phân tích yêu cầu của người
dùng tương tự như trong quá trình tiền xử lý
Searching: Tìm kiếm là quá trình tìm kiếm các từ trong tài liệu và các từ trong

truy vấn để đánh giá độ liên quan giữa tài liệu với nhu cầu của người dùng. Kết quả
của quá trình tìm kiếm có thể phù hợp tuyệt đối hoặc một phần.
Ranking: Các tài liệu thu thập được sẽ được đánh giá theo độ liên quan tương đối
của truy vấn, tài liệu nào có độ liên quan cao thì có số ranking càng bé, nhờ vậy mà
người dùng có thể xem được các tài liệu có liên quan nhất ở phần trên trong thứ tự sắp
xếp.

Information Retrieval

12


Chương 4: Phân loại hệ thống truy hồi thông tin

Chương 4. Phân loại hệ thống truy hồi thông tin
4.1. Phân loại hệ thống tìm kiếm thông tin
- Phân loại theo cách xây dựng từ chỉ mục: có 2 cách:


Cách thứ nhất: là dùng tập chỉ mục được xây dựng từ tập từ hay cụm từ
được rút trích từ chính nội dung của tài liệu, cách lập chỉ mục này gọi là
lập chỉ mục free-text. Các mô hình như Boolean, mô hình không gian
vector[Vector Space Model], các mô hình xác suất đều lập chỉ mục theo
cách này.



Cách thứ hai: là dựa vào một cấu trúc phân lớp có sẵn, phân loại tài liệu
theo một danh mục tiêu đề đề mục có sẵn. Tập chỉ mục trong cách làm
này là tồn tại trước và độc lập với tài liệu, cách lập chỉ mục này gọi là

controlled vocabulary.

- Phân loại theo đơn vị thông tin: có 2 cách:


Hệ thống tìm kiếm thông tin dựa trên từ khóa: sử dụng từ khóa biểu diễn
tài liệu và câu truy vấn. Đây là cách làm phổ biến của các hệ thống tìm
kiếm trước đây. Tiêu biểu là mô hình Boolean, mô hình không gian vector,
mô hình xác xuất và LSI.



Hệ thống tìm kiếm thông tin dựa trên khái niệm [sematic search]: sử dụng
khái niệm biểu diễn tài liệu và câu truy vấn.

Information Retrieval

13


Chương 4: Phân loại hệ thống truy hồi thông tin
4.1 Hệ thống tìm kiếm thông tin dựa trên từ khóa:

- Một hệ thống tìm kiếm trên web có 3 thành phần chính: bộ thu nhập thông tin,
bộ lập chỉ mục và bộ truy vấn.
4.1.1. Bộ thu nhập thông tin Robot
- Robot là một chương trình tự động duyệt qua các cấu trúc siêu liên kết để thu
thập tài liệu và nó nhận về tất cả các tài liệu có liên lết với tài liệu này. Về bản
chất robot chỉ là một chương trình duyệt và thu thập thông tin từ các site theo
đúng giao thức web. Những trình duyệt thông thường không được xem là robot

do thiếu tính chủ động, chúng chỉ duyệt web khi có sự tác động của con người.
4.1.2. Bộ lập chỉ mục Index
- Hệ thống lập chỉ mục hay còn gọi là hệ thống phân tích và xử lý dữ liệu, thực
hiện việc phân tích, trích chọn những thông tin cần thiết [thường là các từ đơn,
từ ghép, cụm từ quang trọng] từ những dữ liệu mà robot thu thập được và tổ chức
thành cơ sở dữ liệu riêng để có thể tìm kiếm trên đó một cách nhanh chóng, hiệu
quả. Hệ thống chỉ mục là danh sách các từ khóa, chỉ rõ các từ khóa nào xuất hiện
ở trnag nào, địa chỉ nào.
4.1.3. Bộ truy vấn [bộ tìm kiếm]

Information Retrieval

14


Chương 4: Phân loại hệ thống truy hồi thông tin
- Bộ phận tìm kiếm có nhiệm vụ so khớp câu truy vấn của người dùng với tập chỉ
mục đã lập của các tài liệu để đánh giá độ liên quan của các tài liệu với câu truy
vấn và trả về các tài liệu liên quan, được sắp xếp theo độ liên quan của nó với
câu truy vấn.
- Đối với những động cơ tìm kiếm theo từ khóa, tìm kiếm từ là tìm kiếm các trang
mà những từ trong câu truy vấn [query] xuất hiện nhiều nhất, ngoại từ stopword
[ như các mạo từ, giới từ]. Một từ các xuất hiện nhiều trong một trang thì trang
đó càng được chọn để trả về cho người dùng. Và một trang chứa tất cả các từ
trong câu truy vấn thì tốt hơn là một trang không chứa hoặc chứa một số từ. Ngày
nay, hầu hết các động cơ tìm kiếm đều hỗ trợ chức năng tìm cơ bản và nâng cao,
tìm từ đơn, từ ghép, cụm từ, danh từ riêng, hay giới hạn phạm vi tìm kiếm như
trên đề mục, tiêu đề, đoạn văn bản giới thiệu về trang web,
4.2. Hệ thống tìm kiếm dựa trên khái niệm [sematic search]
- Trong mô hình tìm kiếm thông tin dựa trên khái niệm, nội dung của một đối

tượng thông tin được mô tả bởi một tập các khái niệm. Hệ thống tìm kiếm dựa
trên khái niệm cũng có chức năng, nguyên lý hoạt động và các bộ phận cấu thành
như hệ thống tìm kiếm tổng quát. Tuy nhiên, khác biệt lớn nhất giữa hệ tìm kiếm
dựa trên khái niệm và hệ tìm kiếm dựa trên từ khóa ở hai điểm sau:


Hệ tìm kiếm dựa trên từ khóa sẽ sử dụng từ khóa để lập chỉ mục, trong khi
hệ tìm kiếm dựa trên khái niệm sử dụng khái niệm để lập chỉ mục.



Để rút trích khái niệm, hệ tìm kiếm dựa trên khái niệm cần sử dụng đến
nguồn tri thức về lĩnh vực nhất định nào đó.

Information Retrieval

15


Chương 4: Phân loại hệ thống truy hồi thông tin

Hình: Hệ thống tìm kiếm dựa trên khái niệm
- Kiến trúc hệ thống tìm kiếm dựa trên khái niệm được cấu thành từ 3 bộ phận
chính đó là bộ thu thập thông tin, bộ lập chỉ mục khái niệm và bộ truy vấn.
4.2.1. Bộ thu thập thông tin
- Giống bộ thu thập thông tin trong một hệ thống tìm kiếm dựa trên từ khóa. Nó có
chức năng thu thập các trang web trên Internet và lưu trữ lại trong cơ sở dữ liệu.
Chức năng này được thực hiện lặp đi lặp lại thường xuyên để cập nhật những
trang Web mới vào trong bộ cơ sở dữ liệu.
4.2.2. Bộ lập chỉ mục khái niệm


Information Retrieval

16


Chương 4: Phân loại hệ thống truy hồi thông tin
- Điều khác biệt cơ bản nhất giữa một động cơ tìm kiếm theo khái niệm và động
cơ tìm kiếm theo từ khóa nằm ở bộ phận lập chỉ mục. Đây cũng là bộ phận quan
trọng nhất trong toàn bộ hệ thống. Với những động cơ tìm kiếm dựa trên từ khóa,
hệ thống sẽ lập chỉ mục theo từ khóa, với những động cơ tìm kiếm dựa trên khái
niệm, hệ thống sẽ lập chỉ mục theo khái niệm.
- Để có bộ khái niệm, hệ thống cần thực hiện công việc rút trích toàn bộ các khái
niệm trong cơ sở dữ liệu để phục vụ cho quá trình lập chỉ mục.Như vậy, trong bộ
lập chỉ mục sẽ có 2 nhiệm vụ rất quan trọng là rút trích các khái niệm từ tập cơ
sở dữ liệu và lập chỉ mục cho các tài liệu dựa trên các khái niệm đó.
- Quy trình chung của rút trích khái niệm:


Rút trích khái niệm là nhiệm vụ khó khăn nhất của một hệ thống tìm kiếm
dựa trên khái niệm. Quá trình này gồm hai giai đoạn chính là: rút trích các
từ chỉ mục trong tài liệu và so khớp các cụm từ này với nguồn tri thức.



Giai đoạn rút trích các cụm từ trong tài liệu:
Đầu tiên, một tài liệu sẽ được đưa vào để tách thành các thành phần khác

o


nhau như danh từ, cụm danh từ, động từ, cụm động từ, tính từ, cụm tính từ,
....
Tiếp theo, hệ thống bắt đầu tạo ra các biến thể từ các thành phần đó.

o


o

Giai đoạn so khớp các cụm từ này với nguồn tri thức:
Sau khi đã có tập các biến thể, hệ thống sẽ xem xét xem những biến thể
nào có trong cơ sở tri thức chứa các khái niệm thì sẽ đưa vào thành tập ứng
viên.

o

Sau đó, tập ứng viên này sẽ được đánh giá và cho điểm theo những tiêu chí
nhất định nào đó và sắp xếp lại theo điểm số.

o

Cuối cùng là việc chọn lựa các ứng viên để đưa vào tập khái niệm.Hệ thống
sẽ tìm ra những ứng viên phù họrp nhất để tạo thành khái niệm, gọi là tập
các khái niệm được rút trích từ tài liệu.

4.2.3. Bộ truy vấn
- Cũng giống như bộ truy vấn của hệ tìm kiểm dựa trên từ khóa. Bộ truy vấn của
hệ thống dựa trên khái niệm có chức năng lấy nội dung câu truy vấn do người

Information Retrieval


17


Chương 4: Phân loại hệ thống truy hồi thông tin
dùng nhập vào, sau đó so trùng với tập chỉ mục đã được lập của các tài liệu để
tìm ra các tài liệu liên quan đển câu truy vấn.
- Để so trùng với tập chỉ mục đã được lập của các tài liệu, trước tiên hệ thống cần
phải rút trích khái niệm từ câu truy vấn. Việc rút trích các khái niệm từ câu truy
vấn tương tự như quá trình rút trích khái niệm của các tài liệu.
- Tùy thuộc vào cách lập chỉ mục cho tập khái niệm như thế nào mà sẽ có những
cách so trùng câu truy vấn với tập chỉ mục của tài liệu khác nhau. Nếu như bộ
lập chỉ mục sử dụng các mô hình truyền thống, cách bộ truy vấn thông tin so
trùng các khái niệm cũng giống như trong hệ thống tìm kiếm dựa trên từ khóa
truyền thống. Nếu một cấu trúc khái niệm biểu diễn tập khái niệm của các tài liệu
đã được xây dựng trong quá trình lập chỉ mục, thì cần xây dựng thêm một cấu
trúc khái niệm để biểu diễn tập khái niệm của câu truy vấn. Sau đó, việc tìm kiếm
mới có thể được thực hiện dựa trên việc so trùng hai cấu trúc khái niệm.

Information Retrieval

18


Chương 5: Một số kỹ thuật tìm kiếm

Chương 5. Một số kỹ thuật tìm kiếm
5.1. Mô hình Boolean
5.1.1. Tổng quan
- Mô hình Boolean dựa trên lý thuyết tập hợp và đại số logic

- Câu truy vấn được phân tích thành các từ khóa truy vấn Các tài liệu được đánh
giá bởi việc có chứa hoặc không chứa các từ khóa truy vấn
- V = { T1, T2, , Tn } là tập tất cả các từ khóa [kho từ khóa hoặc kho từ điển]
- D = { D1, D2, , Dn } là tập tất cả các tài liệu [kho tài liệu]


Trong đó: D1 = { d1, d2, , di } là một tài liệu chứa di là một từ khóa

- Q = [W1 OR W2] AND AND [Wm OR Wn OR Wp] là câu truy vấn [dữ liệu
vào]


Trong đó: W1 = Ti hoặc W1 = NOT Ti

- Những tài liệu cần tìm là các tài liệu có chứa hoặc không chứa Wi
𝐒𝐢𝐣 = {

𝟎 𝐧ế𝐮 𝐖𝐢 𝐃𝐣
𝟏 𝐧ế𝐮 𝐖𝐢 𝐃𝐣

Ma trận từ khóa tài liệu:
D1

D2

Dj

W1

S11


S12

S1j

W2

S21

S22

S2j

Wj

Si1

Si2

Sij

Si = { Sij | Sij = 1 }
Giả sử Q = [W1 OR W2] AND W3
S1 = { Dj | S1j = 1 }
S2 = { Dj | S2j = 1}
Si = { Dj | Sij = 1 }
S = S1 S2 Si

Information Retrieval


19


Chương 5: Một số kỹ thuật tìm kiếm
5.1.2. Ví dụ
- O = { O1, O2, O3 } là kho tài liệu gốc


Trong đó:

O1 = Bayes' Principle: The principle that, in estimating a parameter, one
should initially assume that each possible value has equal probability [a uniform
prior distribution].
O2 = Bayesian Decision Theory: A mathematical theory of decision-making
which presumes utility and probability functions, and according to which the act to
be chosen is the Bayes act, i.e. the one with highest subjective expected utility. If
one had unlimited time and calculating power with which to make every decision,
this procedure would be the best way to make any decision.
O3 = Bayesian Epistemology: A philosophical theory which holds that the
epistemic status of a proposition [i.e. how well proven or well established it is] is
best measured by a probability and that the proper way to revise this probability is
given by Bayesian conditionalisation or similar procedures. A Bayesian
epistemologist would use probability to define, and explore the relationship
between, concepts such as epistemic status, support or explanatory power.
- V = { Bayes' Principle, probability, decision-making, Bayesian Epistemology }
- D = { D 1 , D2 , D3 }


Trong đó:


D1 = { Bayes' Principle, probability }
D2 = { probability, decision-making }
D3 = { probability, Bayesian Epistemology }
- Q = probability AND decision-making
Ma trận từ khóa tài liệu:
probability
decision-making

D1
1
0

D2
1
1

Dj
1
0

S1 = { D1, D2, D3 }
S2 = { D2 }
S = S1 S2 = { D2 }

Information Retrieval

20


Chương 5: Một số kỹ thuật tìm kiếm

- Hạn chế:


Không áp dụng được với từ khóa dạng cụm từ [cụm 2 từ trở lên]

Mô hình Boolean mở rộng [lập chỉ mục ngược]
5.2. Mô hình Boolean mở rộng [lập chỉ mục ngược]
- Các toán tử logic:


Not: Lấy bù



And: Lấy giao



Or: Lấy hợp

- Lập chỉ mục ngược:


Bước 1:



Bước 2:

Information Retrieval


21


Chương 5: Một số kỹ thuật tìm kiếm


Bước 3:



Bước 4:



Bước 5:

Information Retrieval

22


Chương 5: Một số kỹ thuật tìm kiếm
5.3. Mô hình không gian vector
5.3.1. Giới thiệu
- Mô hình không gian vector được phát triển bởi Gerard Salton, trong đó tài liệu
và câu truy vấn được biểu diễn dưới dạng các vector. Mỗi chiều của vector tương
ứng với một mục từ [term]. Term viết tắt của terminology nghĩa là thuật ngữ,
là một từ hay cụm từ biểu thị một khái niệm khoa học. Nếu term này xuất hiện
trong tài liệu thì giá trị của nó trong vector đặc trưng là khác 0. Một văn bản d

được biểu diễn như một vector của các từ chỉ mục 𝑑 = [𝑤𝑡1 , 𝑤𝑡2 , , 𝑤𝑡𝑛 ]. Tương
tự,

câu

truy

vấn

cũng

được

biểu

diễn

như

một

vector

𝑞=

[𝑤𝑡1 , 𝑤𝑡2 , , 𝑤𝑡𝑛 ].Trong đó 𝑤𝑡1,.. 𝑤𝑡𝑛 là các trọng số [term - weight] của từ t1
tn [Cách tính 𝑤𝑡 sẽ được giới thiệu ở phần dưới]. Sau khi biểu diễn tập văn bản
và câu truy vấn thành các vector trong không gian vector, sử dụng độ đo cosine
để tính độ tương tự giữa các vector văn bản và vector truy vấn. Kết quả sau khi
tính toán được dùng để xếp hạng độ liên quan giữa văn bản và câu truy vấn.

5.3.2. Số hóa tập văn bản
- Cách tổ chức dữ liệu Ma trận chỉ mục:


Trong mô hình không gian vector, một tập văn bản có n văn bản được biểu
diễn bởi m từ chỉ mục được vector hóa thành ma trận A ma trận này
được gọi là ma trận từ chỉ mục [term document]. Trong đó n văn bản trong
tập văn bản được biểu diễn thành n vector cột, m từ chỉ mục được biểu
diễn thành m dòng. Do đó phần tử 𝑑𝑖𝑗 của ma trận A chính là trọng số của
từ chỉ mục i xuất hiện trong văn bản j.

- Công thức tính trọng số của từ chỉ mục:


Dựa vào số lần xuất hiện của thuật ngữ của tài liệu [term count], tính ra
tần số xuất hiện của thuật ngữ [term frequency] với kí hiệu là 𝑡𝑓𝑡 .



Giá trị 𝑑𝑓𝑡 [term frequency] tương ứng với số lượng tài liệu chứa thuật
ngữ t.



Tần số nghịch đảo của tài liệu [inverse document frequency], được tính
bằng công thức : 𝑖𝑑𝑓𝑡 = log

𝑁
𝑑𝑓𝑡


. Trong đó, N là tổng tài liệu, 𝑑𝑓𝑡 là số

tài liệu chứa thuật ngữ t.

Information Retrieval

23


Chương 5: Một số kỹ thuật tìm kiếm


Dựa trên các giá trị tf và idf, giá trị trọng số [term - weight] của một thuật
ngữ trong một tài liệu được xác định bằng công thức : 𝑤𝑡,𝑑 = 𝑡𝑓𝑡,𝑑
𝑖𝑑𝑓𝑡 .



Giá trị trọng số này được sử dụng trong ma trận từ chỉ mục, các giá trị
khác 0 trong ma trận thể hiện trọng số của thuật ngữ trong tài liệu.

- Truy vấn trong mô hình không gian vector


Trong mô hình không gian vector, một câu truy vấn được xem như tập các
từ chỉ mục và được biểu diễn như các văn bản trong tập văn bản. Số lượng
từ chỉ mục của câu truy vấn là ít so với số lượng từ chỉ mục trong tập văn
bản. Nên có rất nhiều các từ chỉ mục trong tập văn bản không xuất hiện
trong câu truy vấn. Do thế nên từ chỉ mục nào trong câu truy vấn không
xuất hiện trong tập văn bản thì thành phần đó trong vector truy vấn được

gán bằng 0. Thủ tục truy vấn chính là tìm các văn bản trong tập văn bản
liên quan với câu truy vấn hay một cách khác là các văn bản có độ đo
tương tự cao với câu truy vấn. Theo cách biểu diễn hình học, các văn
bản được chọn là các văn bản gần với câu truy vấn nhất theo độ đo
[measure] nào đó. Độ đo thường được sử dụng nhất là độ đo cosine của
góc giữa vector truy vấn và vector văn bản được tính theo công thức:
𝑑

𝑓 𝑤𝑓 𝑖 . 𝑤𝑓𝑞
𝑑𝑖 . 𝑞
𝑖 , 𝑞 ] =
𝑆𝑖𝑚[𝑑𝑖 , 𝑞 ] = 𝑐𝑜𝑠𝑖𝑛𝑒[𝑑
=
𝑖 ||𝑞 |
𝑖 . ||𝑞 . |
|𝑑
|𝑑



Trong đó:

Information Retrieval

24