igure
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Nguyễn Thị Thu Chung
NGHIÊN CỨU, PHÁT TRIỂN PHƯƠNG PHÁP
TÍNH ĐỘ TƯƠNG TỰ CÂU TRUY VẤN TRONG HỆ
TÌM KIẾM VÀ ỨNG DỤNG THỬ NGHIỆM VÀO MỘT
HỆ TÌM KIẾM THỰC THỂ TIẾNG VIỆT
LUẬN VĂN THẠC SĨ

Hà Nội - 2011 ĐẠI HỌC QUỐC GIA HÀ NỘI

Danh sách các hình 6
MỞ ĐẦU 7
Chương 1. Bài toán tính độ tương tự câu truy vấn trong máy tìm kiếm 8
1.1 Đặc trưng của truy vấn 9
1.2 Bài toán tính độ tương tự truy vấn 9
1.2.1. Bài toán tính độ tương tự truy vấn 9
1.2.2. Các vấn đề cần quan tâm khi tính độ tương tự câu truy vấn 10
1.3 Tóm tắt chương 1 13
Chương 2. Các phương pháp tính độ tương tự 14
2.1 Phương pháp thống kê 14
2.1.1 Phát biểu bài toán 14
2.1.2 Tính toán độ tương tự dựa trên từ vựng 14
2.2 Phương pháp sử dụng xử lý ngôn ngữ tự nhiên 16
2.2.1. Phương pháp tính độ tương tự câu sử dụng Wordnet corpus 16
2.2.2. Phương pháp tính độ tương tự câu sử dụng chủ đề ẩn 21
2.3. Phương pháp sử dụng lưu vết truy vấn của máy tìm kiếm 26
2.4 Tóm tắt chương 2 28
Chương 3. Mô hình đề xuất và thực nghiệm 30
3.1 Cơ sở thực tiễn 30
3.2 Mô hình đề xuất 30
3.3. Thực nghiệm 33
3.3.1. Môi trường thực nghiệm 33
3.3.2. Quá trình thực nghiệm 33
3.3.3. Đánh giá 35
KẾT LUẬN 40
TÀI LIỆU THAM KHẢO 41
PHỤ LỤC 43
Kết quả trả về từ máy tìm kiếm sau khi truy vấn 43
4
Bảng ký hiệu các chữ viết tắt


7

MỞ ĐẦU
Tìm kiếm thông tin trên web là nhu cầu không thể thiếu trên thế giới cũng như
ở Việt Nam. Với tốc độ phát triển internet rất nhanh chóng và mạnh mẽ tại Việt Nam,
theo báo cáo mới đây – tháng 4/2011 của Netcitizens [20], Việt Nam là quốc gia có tỷ
lệ tăng trưởng Internet nhanh nhất trong khu vực và nằm trong số các quốc gia có tỷ lệ
tăng trưởng cao nhất thế giới. Từ năm 2000 đến nay số người sử dụng Internet đã nhân
lên khoảng 120 lần. Việc sử dụng trang web tìm kiếm chiếm 92% trên tổng các hoạt
động trực tuyến [20]. Trong bối cảnh, lượng thông tin trên Internet ngày càng lớn và
cập nhật kịp thời như hiện tại thì người dùng càng cần một công cụ để tìm kiếm những
thông tin họ cần một cách hiệu quả nhất.
Trong các hệ thống tìm kiếm, hầu hết các truy vấn đặt ra là từ khóa, cụm từ
khóa hoặc là một đoạn văn bản ngắn. Biểu diễn lại, làm truy vấn phù hợp hơn là một
bài toán đặc trưng trong các hệ tìm kiếm, trong đó mở rộng truy vấn (query expansion)
và biểu diễn truy vấn có tính tương tự (query similarity) là hai giải pháp điển hình
nhất. Nhiều công trình nghiên cứu về tính tương tự truy vấn cũng như tính tương tự
của các văn bản ngắn đã được công bố, chẳng hạn như [18][7][1][8]. Tính tương tự
văn bản không chỉ hỗ trợ việc biểu diễn lại truy vấn mà còn được sử dụng trong nhiều
bài toán khác, chẳng hạn như bài toán phân cụm truy vấn.
Luận văn với đề tài “Nghiên cứu, phát triển phương pháp tính độ tương tự truy
vấn trong hệ tìm kiếm và ứng dụng thử nghiệm vào một hệ tìm kiếm thực thể tiếng
Việt” thực hiện khảo sát, nghiên cứu các phương pháp tính độ tương tự truy vấn trong
hệ tìm kiếm. Từ đó đưa ra hướng phát triển cho phương pháp tính độ tương tự truy vấn
phù hợp để áp dụng thử nghiệm vào một hệ tìm kiếm tiếng Việt. Đồng thời, luận văn
cũng tiến hành đánh giá ở bước cuối cùng để đưa ra so sánh giữa việc tìm kiếm thông
thường trên máy tìm kiếm tiếng Việt với việc sử dụng tính độ tương tự truy vấn để đưa
ra câu trả lời. Trong thời gian tiếp theo, luận văn sẽ nghiên cứu để áp dụng tính độ
tương tự câu hỏi và áp dụng vào hệ tìm kiếm thực thể Tiếng Việt.

khác trong lĩnh vực khai phá dữ liệu như phân cụm [2][3], tóm tắt văn bản [10], ….
Việc tính toán độ tương tự giữa văn bản thường dựa vào nội dung, ngữ cảnh của văn
[4]. Các thuật toán thông thường được sử dụng là: độ đo cosin, độ đo TF-IDF, Dice, …
[8] . Với văn bản, thường có khối lượng từ ngữ nhiều, có khả năng thể hiện được đầy
đủ nội dung và ngữ cảnh thì việc sử dụng các phương pháp truyền thống thường tỏ ra
hiệu quả, tuy nhiên, do đặc trưng của câu truy vấn thường ngắn và mang ít ngữ cảnh so
với văn bản ví dụ câu truy vấn: apple có thể biểu thị một loại hoa quả, đồng thời nó
cũng là tên của một công ty máy tính. Ngoài ra, câu truy vấn của người dùng thường
rất đa dạng mà không phải bao giờ cũng đúng mẫu hay được biểu diễn đúng với nội
dung mà người dùng muốn tìm kiếm. Truy vấn có những đặc trưng riêng mà ta cần
nắm bắt đề có thể lựa chọn áp dụng phương pháp phù hợp nhất cho việc tính độ tương
tự giữa các truy vấn. Dưới đây luận văn sẽ trình bày về các đặc trưng của truy vấn.
9

1.1 Đặc trưng của truy vấn
Truy vấn là một dạng biểu diễn đặc biệt của văn bản. Truy vấn có những đặc
điểm riêng, đặc trưng cho những truy vấn mà người dùng đưa vào máy tìm kiếm.
Truy vấn được đưa vào máy tìm kiếm thường mang tính chủ quan của người
dùng. Nó không phải lúc nào cũng biểu diễn đúng những điều mà người dùng mong
muốn thể hiện. Do trình độ của người dùng mỗi người là khác nhau, nên các câu truy
vấn đưa vào cũng có những định dạng khác nhau, đôi khi còn xuất hiện lỗi chính tả,
Ngoài ra, không giống với văn bản với lượng lớn câu chữ, thường thể hiện bối
cảnh, nội dung rõ ràng, các câu truy vấn thường ngắn, nó không thể hiện được đầy đủ
nội dung mà người dùng mong muốn. Ví dụ: Khi người dùng đưa vào câu truy vấn
apple – quả táo. Khi đọc câu truy vấn này, máy tìm kiếm sẽ khó để hiểu được người
dùng đang muốn ám chỉ một loại hoa quả hay ám chỉ một hãng máy tính nổi tiếng.
Để đáp ứng được các đặc trưng riêng này của truy vấn, người ta thường áp dụng
phương pháp biểu diễn truy vấn bằng chính những từ ngữ nội tại của nó. Tức là không
thêm bớt từ khóa nào trong truy vấn. Ngoài ra, để tăng thêm ngữ nghĩa cho truy vấn,
người ta cũng sử dụng phương pháp mở rộng câu truy vấn, giúp máy tìm kiếm xác

truy vấn của người dùng, tiến hành tìm kiếm và đưa ra được kết quả tốt hơn. Đấy là
nội dung của bài toán tính độ tương tự câu truy vấn.
Ví dụ: Người dùng đưa vào truy vấn: Lê Hồng Phong thì người ta cũng muốn
có những kết quả liên quan đến Lê Huy Doãn hoặc Tổng bí thư giai đoạn 1935-1936.
Như vậy, máy tìm kiếm cần viết lại truy vấn Lê Hồng Phong thành Tổng bí thư Lê
Hồng Phong, Lê Huy Doãn.
1.2.2. Các vấn đề cần quan tâm khi tính độ tương tự câu truy vấn
a. Biểu diễn truy vấn
Do đặc trưng riêng của truy vấn, để tính toán độ tương tự giữa các truy vấn, ta
cần có cách biểu diễn truy vấn phù hợp.
Truy vấn có thể được biểu diễn theo các phương pháp: Biểu diễn nguyên thể,
Biểu diễn rút gọn, Biểu diễn mở rộng [7]. Các phương pháp biểu diễn câu truy vấn sẽ
được trình bày dưới đây:
 Biểu diễn không thay đổi từ ngữ - Surface representation
Biểu diễn truy vấn bằng chính từ ngữ nội tại của nó là phương pháp biểu diễn
văn bản ngắn đơn giản nhất.
Việc biểu diễn truy vấn bằng phương pháp này có thể đưa lại dữ liệu rời rạc, tuy
nhiên nó có chất lượng khá cao vì không có sự thay đổi nào (tự động hoặc thủ công)
tác động để thay đổi nó. Phương pháp này có thể gây nhiều nhiễu khi xử lý tính độ
tương tự truy vấn tuy nhiên ta lại không tốn công sức để xử lý nó.
Ví dụ: Nếu người dùng đưa vào truy vấn

11

 Biểu diễn rút gọn - Stemmed representation
Lược giản từ đã được biết đến rộng rãi như một công nghệ cơ bản trong khai
phá dữ liệu đặc biệt là máy tìm kiếm, khai phá văn bản và phân tích tâm lý (sentiment
analysis) như là bước tiền xử lý dữ liệu. Do đây là phương pháp lược bỏ bớt một phần
của từ về dạng đơn giản hơn nên dung lượng từ sẽ được giảm bớt.
Ví dụ: Từ clustering trong tiếng Anh (phâm cụm trong tiếng Việt) sẽ được

- Phương pháp thủ công
- Phương pháp tự động
- Phương pháp kết hợp (kết hợp giữa thủ công và tự động)
 Phương pháp thủ công
Đây là phương pháp mở rộng truy vấn cơ bản nhất, nó chủ yếu kết hợp việc tìm kiếm
Boolean. Có rất nhiều mô hình tìm kiếm trực tuyến đã được phát triển dựa trên mô hình
Boolean và các phương pháp tương tác giữa người dùng và hệ thống truy hồi. Theo Có nhiều
phương pháp được công bố, như: xây dựng khối (building block), tìm kiếm đơn giản (brief
search), successive fraction,…
 Phương pháp tự động
Phương pháp này tận dụng các khái niệm có sẵn trong tập tài liệu và các mối
quan hệ giữa chúng để thực hiện mở rộng truy vấn.
Mối quan hệ giữa các khái niệm (khái niệm ở đây có thể là một từ hoặc một
cụm danh từ) được biểu diễn dưới dạng cấu trúc phân cấp. Dựa vào những đặc trưng
và đặc tính ngữ nghĩa, ta có thể phân thành nhiều loại mối quan hệ khác nhau.
 Phương pháp kết hợp
Khác với các phương pháp đã trình bày ở trên, việc mở rộng truy vấn sử dụng
phương pháp này được thực hiện kết hợp giữa hệ thống và người sử dụng. Hệ thống sẽ
thực hiện liệt kê và xếp hạng tập các từ có liên quan và người sử dụng phải quyết định
lựa chọn các khái niệm theo quan điểm tìm kiếm để tự thêm vào câu truy vấn. Vì vậy,
người dùng là người quyết định cuối cùng việc mở rộng của một từ. Nó phản ảnh tầm
quan trọng tương đối và tính hữu dụng của các khái niệm dựa vào quan điểm của
người sử dụng, do đó tăng sự hài lòng của người sử dụng. Có nhiều cách kết hợp để
mở rộng truy vấn, ví dụ một phương pháp mở rộng câu truy vấn phổ biến hiện nay là
phương pháp sử dụng lưu vết truy vấn của máy tìm kiếm. Từ bộ userlog mà máy chủ
tìm kiếm ghi lại được lịch sử truy vấn và lịch sử lựa chọn tài liệu mở của người dùng,
người ta tiến hành mở rộng để đưa câu truy vấn về dạng giàu ngữ nghĩa hơn.
b. Tìm ra ngưỡng phù hợp để định nghĩa tính tương tự
Như ta đã biết, hai câu truy vấn có độ tương tự càng cao thì chúng càng giống
nhau, hai câu truy vấn có độ tương tự càng thấp thì chúng càng ở xa nhau hơn. Vì vậy,

bản là dựa trên từ ngữ của văn bản [7] . Tùy thuộc vào cách biểu diễn, phương pháp
này chỉ dựa trên số từ chung giữa hai truy vấn.
2.1.1 Phát biểu bài toán
Cho hai câu truy vấn q và s. Đặt Q, S tương ứng là tập hợp các từ thuộc q và s
 
 
n
n
sssS
qqqQ
, ,,
, ,,
21
21


( 1)
Trong đó:
 n là số từ thuộc q
 m là số từ thuộc s
Xác định độ tương tự giữa hai truy vấn q, s bằng cách xác định số từ chung thuộc
cả hai câu truy vấn. Việc tính toán độ tương tự giữa hai câu truy vấn q và s được xác
định bằng một số công thức như liệt kê dưới đây.
2.1.2 Tính toán độ tương tự dựa trên từ vựng
Để tính độ tương tự giữa hai truy vấn dựa trên từ vựng, người ta sử dụng
phương pháp biểu diễn truy vấn đơn giản nhất là dựa trên chính những từ ngữ nội tại
của truy vấn – “surface representation”.
Chúng ta xác định một số tiêu chuẩn sau để tính toán tính phù hợp giữa các truy
vấn [7] :
15

( 3)
 Độ đo Jaccard
||
||
),(
SQ
SQ
sqsim



( 4)
 Độ đo Overlap
|||,min(|
||
),(
SQ
SQ
sqsim


( 5)
16

 Độ đo Cosin
||||
||
),(
SQ
SQ


17

a. Mô hình

Hình 1: Lược đồ tính toán độ tương tự câu

b. Các bước xử lý
Bước 1: Tiền xử lý
 Tách mỗi câu thành một danh sách các từ tố (token): Mỗi câu được tách
ra thành một danh sách các từ và xóa đi các từ dừng. Từ dừng là các từ
xuất hiện thường xuyên, các từ không có ý nghĩa.
 Xác định từ loại (part of speech: từ loại): Sau khi câu được tách thành
danh sách các từ. Bước này sẽ xác định đúng từ loại (POS - như danh từ,
động từ, trạng từ, tính từ, ) của mỗi từ trong câu.
Bước 2: Tính độ tương tự từ
 Sau khi đã có danh sách các từ được gán nhãn, ta xác định được một tập
từ chung cho hai câu. Tập từ chung này bao gồm tất cả những từ phân
biệt có trong hai câu đó.
 Dựa vào tập từ chung đồng thời sử dụng wordnet ta sẽ ước tính được độ
tương tự về ngữ nghĩa cho các từ trong mỗi câu với tập từ chung. Từ đó
đưa ra được vector ngữ nghĩa cho hai câu. 18

Bước 3: Tính độ tương tự ngữ nghĩa cho hai câu
 Khi tính được độ tương tự từ, ta đưa ra được vector ngữ nghĩa s
i
cho mỗi

1
, c
2
, chúng ta cần tính độ tương tự từ cho hai từ đó dựa vào
WordNet. Ta sẽ tìm một lớp nào đó trong cây phân cấp để xác định các từ trong nhóm
lớp đó, rồi tiến hành so sánh. Phương pháp này có thể được thực hiện dựa vào nhiều
độ đo như: độ đo Jiang Conrath (JCN), độ đo Lin, Extended Gloss Overlaps, Hirst-St
Onge, Resnik, Leacock-Chodorow. Theo [16] có bảng sau:
Measure
Nouns Only
All POS
Jiang-Conrath
0.46
N/A
Ex.Gloss Overlaps
0.43
0.34
Lin
0.39
n/a
Vector
0.33
0.29
Hirst-St.Onge
0.33
0.23
Leacock Chodorow
0.28
n/a
Bảng 1: Kết quả so sánh các độ đo

 distance: Khoảng cách của hai từ. Từ đó, đưa ra được mối quan hệ giữa
hai từ c
1
và c
2
như sau:
Relatedness(c
1
, c
2
) = 1 / distance ( 10)
Ví dụ: Xét hai từ boy và teacher. Dựa vào hình 4 ta có lcs(boy, teacher) là
person
e. Độ tương tự về ngữ nghĩa giữa hai câu
Sau khi tính được độ tương tự từ, ta đưa ra được vector ngữ nghĩa s
i
cho mỗi
câu. Giá trị của từng thành phần có trong vector là giá trị về độ tương tự từ của từng từ
trong câu với tập từ chung . Sự giống nhau về ngữ nghĩa giữa hai câu là hệ
số cosin giữa hai vector :
2.
.
1
21
ss
ss
S
s

( 11)

1
và
r
2
tương ứng như sau:
r
1
={1 2 3 4 5 6 7 8 9}
r
2
={1 2 3 9 5 6 7 8 4}
Công thức để tính độ tương tự về thứ tự của từ trong câu như sau:
21
21
1
rr
rr
S
r



( 12)

g. Tính độ tương tự cho toàn bộ câu
Sự giống nhau về toàn bộ câu được định nghĩa là sự kết hơp giữa độ tương tự
về mặt ngữ nghĩa và thứ tự của từ trong câu
( 13)
Với
10 

M
}, trong đó, mỗi
tài liệu m trong corpus bao gồm N
M
từ w
i
rút từ một tập từ vựng (Vocabulary) của các
từ (term) {t
1
, t
2
, , t
v
}, V là số từ. LDA cung cấp một mô hình sinh đầy đủ chỉ ra kết
quả tốt hơn các phương pháp trước. Quá trình sinh ra document như sau:

Hình 3: Mô hình biểu diễn của LDA
Trong đó:
 Các khối vuông trong Hình biểu diễn các quá trình lặp.
 Tham số đầu vào: α và β (corpus-level parameter)
23

o α: Dirichlet prior on
m

(theta)
o β: Dirichlet prior on
k



m,n
được lấy mẫu dựa vào phân phối topic trên.
 Với mỗi topic chỉ mục z
m,n
, dựa vào phân phối từ
k

, W
m,n
, được sinh
ra.

k

được lấy 1 lần cho toàn bộ copus

24

Ở đây, Dir, Poiss and Mult lần lượt là các phân phối Dirichlet, Poisson,
Multinomial. (Lấy mẫu theo phân phối Dirichlet, Poisson, Multinomial).
Ước lượng tham số và Inference thông qua Gibbs Sampling
Cho trước một tập các văn bản, tìm xem topic model nào đã sinh ra tập các văn
bản trên. Bao gồm:
 Tìm phân phối xác suất trên tập từ đối với mỗi topic
k


 Tìm phân phối topic của mỗi tài liệu
m


Trong mỗi lần lấy mẫu lại: các tham số tương ứng với các topic và term cũ
giảm đi 1, các tham số tương ứng với các topic và term mới tăng lên 1.
Check convergence and read out parameters: Quá trình kết thúc, đọc các
tham số đầu ra Φ và Θ
hai phân phối ẩn
k

và
m

được tính như sau:

Trích đoạn Tóm tắt chương 2

---