HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
NGUYỄN THỊ BÍCH PHƯƠNG

NGHIÊN CỨU PHƯƠNG PHÁP MỞ RỘNG TRUY VẤN TRONG
TRUY XUẤT THÔNG TIN (INFORMATION RETRIEVAL)

Chuyên ngành : Truyền dữ liệu và mạng máy tính
Mã số : 60.48.15 TÓM TẮT LUẬN VĂN THẠC SỸ

……………………………………………………………………………………………
Luận văn sẽ được bảo vệ trước Hội đồng chấm luận văn thạc sĩ tại Học viện Công nghệ Bưu
chính Viễn thông
Vào lúc: giờ ngày tháng năm 2010

Có thể tìm hiểu luận văn tại:
- Thư viện của Học viện Công nghệ Bưu chính Viễn thông
TÓM TẮT LUẬN VĂN
Chương I. Tổng quan về mở rộng truy vấn trong truy xuất thông tin
1.1 Giới thiệu tổng quan về mở rộng truy vấn trong truy xuất thông tin
1.1.1 Hệ thống truy xuất thông tin (Information Retrieval-IR)
Hệ thống Truy xuất thông tin (Information Retrieval) là hệ thống thực hiện tìm
kiếm tài liệu (thường là các tài liệu văn bản) từ một tập các tài liệu (được lưu trữ
trên máy tính) thường có tính chất phi cấu trúc (văn bản ngôn ngữ tự nhiên) thỏa
mãn một nhu cầu thông tin của con người
Mục đích của hệ thống Truy xuất thông tin là hiển thị cho người dùng một tập
các thông tin thỏa mãn nhu cầu thông tin. Định nghĩa chính xác cho nhu cầu thông
tin là “câu truy vấn” (query), và các thông tin được chọn là “tài liệu” (documents).
Một hệ thống tìm kiếm thông tin có hai chức năng chính, đó là lập chỉ mục
(indexing) và tìm kiếm (interrogation).
Hệ thống truy xuất thông tin được chia làm 2 loại như sau:

để khai thác mối quan hệ về ngữ pháp hoặc sự phụ thuộc ngữ pháp.
Từ điển được tạo ra gồm danh sách các từ có mối quan hệ ngữ pháp
tương tự nhau.
Chương II. Các phương pháp mở rộng truy vấn trong truy xuất thông tin
2.1 Phương pháp mở rộng truy vấn trong truy xuất thông tin dựa trên phân
tích tổng thể (Global analysis)
Phân tích tổng thể chiết xuất sự đồng xuất hiện của các thuật ngữ liên quan và
các kết quả trong một ma trận tương tự bằng cách phân tích toàn bộ tập tài liệu.
Phương pháp bao gồm các kỹ thuật: phân cụm thuật ngữ (term clustering), kỹ thuật
tìm cụm từ (phrasefinder) và kỹ thuật tạo từ điển tương tự (similar thesaurus).
Trong đó, kỹ thuật Phrasefinder là một trong các kỹ thuật thành công nhất của phân
tích tổng thể.
Kỹ thuật Phrasefinder sử dụng giả thuyết: “mọi khái niệm được kết hợp với một
tài liệu giả”. Nội dung của tài liệu giả cho một khái niệm là các từ xuất hiện trong
mọi cửa sổ cho khái niệm đó trong tài liệu. Kích cỡ của một cửa sổ thường là từ 1

đến 3 câu. Cơ sở dữ liệu INQUERY được xây dựng từ những tài liệu giả này, nó tạo
một cơ sở dữ liệu khái niệm. Các khái niệm c là tập {
1 1
,
t a
 
,
2 2
,
t a
 
,… } trong
đó
i

thông tin liên quan, thì người dùng có 1 lựa chọn để dán nó vào câu truy vấn, vì vậy
làm tăng cơ hội tìm kiếm thành công
2.3 Phương pháp mở rộng truy vấn trong truy xuất thông tin dựa trên phân
cụm (cluster-based)

Phương pháp thu hồi thông tin dựa trên cụm phân chia tập các tài liệu khác
nhau thành các cụm có ý nghĩa (chủ đề) khác nhau. Do đó những tài liệu trong cùng
một cụm mô tả cùng một chủ đề và thêm nữa là trả về một danh sách xếp hạng các
văn bản dựa trên các cụm mà đến từ đến người dùng.
Có 2 phương pháp tiếp cận thu hồi thông tin dựa trên phân cụm:
- Phương pháp xếp hạng cụm truy vấn tương tự.
- Phương pháp sử dụng phân cụm để làm mịn tài liệu.
Kỹ thuật phân cụm mờ (fuzzy clustering). Kỹ thuật mở rộng truy vấn dựa trên phân
cụm mờ bao gồm 2 tiến trình: Tiến trình xây dựng từ điển (thesauri) và tiến trình
mở rộng truy vấn:

Hình 1. Kỹ thuật mở rộng truy vấn dựa trên phân cụm mờ
2.4 Phương pháp mở rộng truy vấn trong truy xuất thông tin dựa trên bản
thể học (Ontology based Query expansion)
2.4.1 Tổng quan về Ontology Khái niệm về Ontology
Ontology là một kho dữ liệu biểu diễn một tập các khái niệm và các quan hệ, dùng
để mô tả, định nghĩa các tính chất của miền (domain).
Các yếu tố cấu thành ontology
- Ontology được cấu tạo bởi các class và các quan hệ (relation) tồn tại giữa các
đối tượng của class.
- Lược đồ thuật ngữ ontology dùng để tham chiếu tới toàn bộ các class và các
quan hệ. Cơ sở tri thức thuật ngữ (thuộc ontology) tham chiếu đến một lược

IR
OB P
QEM
 

)
- Mô hình mở rộng truy vấn dựa trên ontology và kết hợp với hệ thống truy
xuất thông tin (Query Expansion Model with Ontology-Based with
Information Retrieval,
+IR
OB
QEM

)
- Mô hình mở rộng truy vấn dựa trên ontolgy kết hợp xác xuất và tích hợp hệ
thống truy xuất thông tin (Query Expansion Model with Ontology-Based and
Probability with Information Retrieval,
+IR
OB P
QEM
 
)
2.4.2.2 Các bước thực hiện mở rộng truy vấn dựa trên Ontology
Phương pháp mở rộng truy vấn dựa trên ontology cần thực hiện theo 2 bước như
sau:
- Đầu tiên, các thuật ngữ của câu truy vấn phải được khử nhập nhằng để chúng
ánh xạ vào một khái niệm ontology duy nhất.
- Sau đó, các thuật ngữ có liên quan đến những khái niệm đã khử nhập nhằng
trong ontology được thêm vào câu truy vấn.
+ Khử nhập nhằng:

3.1.2 Trình bày giải pháp
Có 2 phương pháp phổ biến trong mở rộng truy vấn dựa trên Ontology được nghiên
cứu trên thế giới đó là:
- Phương pháp mở rộng truy vấn thông qua việc sử dụng WordNet (một
ontology tổng quát được xây dựng sẵn). Phương pháp này khai thác thác trực
tiếp dữ liệu từ WordNet để thực hiện mở rộng truy vấn.
- Phương pháp mở rộng truy vấn thông qua xây dựng ontology chuyên biệt kết
hợp khai thác dữ liệu ngữ nghĩa và quan hệ ngữ nghĩa từ WordNet. Phương
pháp này gồm 2 phần:

o 1 - Xây dựng một ontology chuyên biệt tối ưu dựa trên việc khai thác
các quan hệ ngữ nghĩa đã được định nghĩa sẵn trong WordNet.
o 2 - Thực hiện mở rộng truy vấn dựa trên Ontology vừa được xây
dựng.
Phương pháp đầu tiên là phương pháp đơn giản, dễ thực hiện nhưng hiệu quả thu
hồi thông tin không cao. Ngược lại, phương pháp thứ 2 khá phức tạp và tốn nhiều
thời gian, chi phí để xây dựng.
3.1.2.1 Giới thiệu WordNet
WordNet [ là một ontology tổng quát phổ dụng
được xây dựng để phục vụ nhiều ứng dụng khác nhau trong xử lý ngôn ngữ tự
nhiên, truy xuất thông tin, làm việc với dữ liệu văn bản nói chung. Đây là một hệ
ontology dùng cho từ vựng tiếng Anh. Các từ vựng trong WordNet được phân loại
và tổ chức thành các tập đồng nghĩa gọi là synsets. Mỗi tập synset biểu diễn một
nghĩa. Các quan hệ của WordNet được mô tả như sau:
- Quan hệ Hypernymy (tên khác là Superordinate, Thượng danh) là quan hệ
giữa hai khái niệm A và B mà nghĩa của khái niệm A luôn bao hàm khái
niệm B(nhưng không ngược lại). Một dạng của quan hệ này là Instance
Hypernymy (hay Instance) là quan hệ giữa khái niệm A và đối tượng B mà B
là một dạng của A tương ứng cho đối tượng.
- Quan hệ Hyponymy (hay Subordinate, Hạ danh hoặc IS-A) là quan hệ giữa

* Khử nhập nhằng dùng WordNet (Word sense Disambiguation-WSD)
Pavlidis [37] đã nghiên cứu một thuật toán khử nhập nhằng để tạo độ chính
xác cao, nhưng có thể độ truy hồi thấp. Thuật toán này thuộc lớp phương pháp nhận
dạng mẫu có cấu trúc. Ở đây, Pavlidis sử dụng một đồ thị để mô tả những trường
hợp (ngữ nghĩa của từ). Thuật toán như sau:
Đặt Q = {
1
w
,
2
w
, …,
w
n
} là truy vấn khởi tạo
Đặt:


Word
(w ) | s (w ), w
k k
k j j Net k k
S S S Syn et Q
  

là tập đồng nghĩa WordNet của
w
k
, k=1,…,n.
Ta có:

C m Sc e C


- Tạo mạng ngữ nghĩa:
Với mỗi w
k
Q

và mỗi synset
k
j
S
của
w
k
(
k
j
S
là ngữ nghĩa thứ j của
w
k

trong WordNet), tạo một mạng ngữ nghĩa.
Mạng ngữ nghĩa được tạo tự động sử dụng quan hệ ngữ nghĩa sau: hypernym

(vd: xe ô tô là một phương tiện xe cộ; ký hiệu:
@

), hyponym (ngược lại của

Hình 3.3 Mạng ngữ nghĩa cho nghĩa số 1 của từ “bus”
Phân cắt mạng ngữ nghĩa và gán điểm số cho cấu hình
Đặt SN(
k
j
S
) là mạng ngữ nghĩa cho ngữ nghĩa j của từ
w
k
. Xét một cấu hình
ngữ nghĩa
x
C
tương ứng với mỗi truy vấn Q, các mạng ngữ nghĩa được phân thành
các cặp giao nhau và số node chung được đếm. Đặt
1
( ) ( )
k m
j
SN S SN S
 là một điểm
giao. Gọi điểm giao là node chung S. Ví dụ
* * 1
k
j m
S S S
 
trong đó
*


C m Sc e C


* Mở rộng truy vấn với WordNet
Để mở rộng truy vấn, người ta sử dụng 5 phương thức mở rộng và 2 chiến lược lựa
chọn từ mở rộng
+ Phương thức mở rộng truy vấn:
i. Mở rộng Synset: synset liên quan thay thế thuật ngữ truy vấn ban đầu (từ có
thể được mở rộng nằm trong truy vấn ban đầu).
ii. Mở rộng Hypernym (thượng danh): Các từ (word) có khả năng mở rộng
được bổ sung thêm các hypernyms trực tiếp của nó vào câu truy vấn.
iii. Mở rộng gloss synset: Các từ (word) có khả năng mở rộng được bổ sung
thêm các synset của gloss của từ đó.
iv. Mở rộng gloss word: Các từ (word) có khả năng mở rộng được bổ sung thêm
các từ trong glosses của chúng (glosses - là định nghĩa khái niệm của từ
trong WordNet. Ở đây là lấy các từ nằm trong định nghĩa tương ứng với ngữ
nghĩa của từ đó sau khi đã khử nhập nhằng)
v. Mở rộng các node chung: Các từ mở có khả năng mở rộng được bổ sung
thêm các từ (word) mà tập đồng nghĩa của nó thuộc
[S ]
x
j
- Danh sách các
node chung thuộc
x
C
.
+ Chiến lược lựa chọn từ có khả năng mở rộng:
- Chiến lược 1: Chỉ mở rộng các từ monosemous. Đây là các từ có nghĩa rõ
ràng (có duy nhất 1 nghĩa).

- Chiến lược thứ 1: Tìm kiếm tài liệu với câu truy vấn ban đầu là “bike”. Trong
đó, hệ thống tìm kiếm sẽ thực hiện tìm tất cả các tài liệu trong kho tài liệu có
chứa từ “bike” và thu được kết quả là 11/17 tài liệu

- Chiến lược thứ 2: Tìm kiếm mở rộng truy vấn dựa trên ontology WordNet.
Động cơ tìm kiếm thông tin cục bộ thực hiện mở rộng câu truy vấn “bike”
bằng cách tìm các từ đồng nghĩa với từ “bike” trong WordNet và thu được
những cặp từ đồng nghĩa như sau:
1) motorcycle, bike.
2) bicycle, bike, wheel, cycle.
3) bicycle, cycle, bike, pedal, wheel.
Động cơ tìm kiếm thông tin tiếp tục tìm các tài liệu trong kho tài liệu ban đầu
mà chứa những từ đồng nghĩa với bike (như trên) và thu được kết quả là 15/17
tài liệu.
3.3 Đánh giá ưu khuyết điểm của giải pháp mở rộng truy vấn dựa trên
Ontology
a. Ưu điểm:
- Chất lượng mô hình tri thức tốt: Đặc trưng của ontology là độ gắn kết, tính
ổn định, tính đối kháng và sự đồng nhất, sự nhập nhằng nên chất lượng về
mô hình tri thức rất tốt. Bởi chất lượng của việc diễn dịch văn bản tự do phụ
thuộc rất nhiều vào chất lượng mô hình tri thức. Theo nghiên cứu của Jones
[16] chất lượng mô hình tri thức hay từ điển chuyên đề là quan trọng nhất.
Mô hình này phải chính xác, ổn định và bao hàm toàn diện. Nếu một mô
hình dữ liệu không bao phủ các chủ đề trong hướng toàn diện thì các truy
vấn (liên quan đến một chủ đề nào đó) sẽ không thu hồi được bất kỳ kết quả
nào.
- Am hiểu mô hình tri thức: Theo nghiên cứu của Suomela và Kekalainen
[17], quá trình tìm kiếm thông tin có cơ hội thành công nhiều hơn nếu người
dùng hiểu rõ mô hình tri thức.
- Khả năng định hướng của mô hình tri thức: Các phương pháp thực