ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ
PHẠM THỊ THU UYÊN
NGHIÊN CỨU, CẢI TIẾN PHƢƠNG PHÁP MỞ RỘNG
CÂU HỎI VÀ TÍCH HỢP VÀO HỆ THỐNG TÌM KIẾM
THỰC THỂ TIẾNG VIỆT Ngành: Công nghệ thông tin
Chuyên ngành: Hệ thống thông tin
Mã số: 60.48.05 LUẬN VĂN THẠC SĨ
Ngƣời hƣớng dẫn khoa học: PGS.TS Hà Quang Thụy
Hà Nội - 2011
3
Mục lục
Chương 1. Bài toán Mở rộng truy vấn trong hệ thống tìm kiếm 9
Danh sách hình vẽ
Hình 1. Mô hình hệ thống tìm kiếm 9
Hình 2. Các câu truy vẫn hỗ trợ khi nhập câu truy vấn “Hồ Chí Minh” 12
Hình 3. Mô hình của phương pháp xây dựng khối (building block) 15
Hình 4. Mối liên hệ giữa từ “car” với các từ khác thông qua các mối quan hệ 16
Hình 5. Giới thiệu về YAGO 18
Hình 6. Đồ thị mô tả mối quan hệ cho câu truy vấn “jaguar” 22
Hình 7. Mô hình Mở rộng truy vấn sử dụng đồ thị khái niệm Wikipedia 24
Hình 8. Mô hình Mở rộng truy vấn 28
Hình 9. Mô hình chung của hệ thống tìm kiếm 33
Hình 10. Đồ thị mối quan hệ giữa các câu truy vấn chứa từ “máy tính” 42 5
Danh sách bảng
Bảng 1. Mối quan hệ ngữ nghĩa trong WordNet 17
Bảng 2. Tập câu truy vấn và session 30
Bảng 3. Cấu hình phần cứng sử dụng trong thực nghiệm 35
Bảng 4. Một số phần mềm sử dụng 35
Bảng 5. Tập 10 câu truy vấn đầu tiên trong một phiên giao dịch của người dùng 37
Bảng 6. Một số câu truy vấn và link kết quả các phiên giao dịch của người dùng 39
Bảng 7. Thống kê số truy vấn, phiên giao dịch và tập luật liên kết dựa vào tập query
log ngày 11/04/2009 40
Bảng 8. Tập 20 câu truy vấn đầu tiên chứa từ “máy tính” 40
Bảng 9. Một số luật liên kết giữa các câu truy vấn có chứa từ “máy tính” 41
Bảng 10. Thống kê số câu truy vấn chứa từ “máy tính” và tập luật liên kết 41
Bảng 11. Tập 20 khái niệm liên quan câu truy vấn “máy tính” trọng số cao nhất 43
Bảng 12. Một số các câu truy vấn mở rộng cho truy vấn “máy tính” 44
quan tâm đặc biệt từ các nhà nghiên cứu. Đây là nền tảng cho việc xây dựng và phát
triển các bài toán ứng dụng khác. Mở rộng truy vấn là một trong số đó, bài toán này
được đã được nhiều nhà nghiên cứu quan tâm tới từ lâu [8, 12, 15, 13] và hiện nay vẫn
được nghiên cứu và cải tiến. Bài toán mở rộng tập truy vấn với mục đích xác định cụ
thể mục đích, ngữ cảnh tìm kiếm của người sử dụng thông qua việc bổ sung thêm một
số từ, khái niệm liên quan nhằm đưa ra những kết quả chính xác đáp ứng nhu cầu của
người dùng. Đồng thời, mở rộng truy vấn được ứng dụng trong nhiều bài toán khác
như: Hệ thống tìm kiếm [14, 21], Hệ thống hỏi đáp [14],…Vì vậy, bài toán Mở rộng
truy vấn đã nhận được sự quan tâm từ các nhà nghiên cứu tại các hội nghị lớn trên thế
giới trong những năm gần đây như: ACM
1
, WWW
2
, Text Retrieval Conference
(TREC)
3
….
Trong thời gian gần đây, mặc dù đã có nhiều phương pháp mới đưa ra nhằm cải
tiến việc mở rộng truy vấn nhưng đây vẫn là bài toán nhận được nhiều sự quan tâm từ
các nhà nghiên cứu cho các ngôn ngữ nói chung và tiếng Việt nói riêng. Tương tự như
tiếng Anh, mở rộng truy vấn cũng là một bài toán được đề cập nhiều từ xưa tới nay
nhằm cải tiến việc tìm kiếm để đưa ra kết quả chính xác trong các hệ thống như Hệ
thống tìm kiếm, Hệ thống hỏi đáp, Việc đưa ra một phương pháp tốt nhất cho tiếng
Việt hiện nay vẫn đang là một vấn đề còn gặp nhiều khó khăn do hiện tại tài nguyên
ngôn ngữ học cũng như các kĩ thuật xử lý còn đang dần được hoàn thiện. Vì thế, nhiều
bài toán xử lý cho ngôn ngữ tiếng Việt còn gặp nhiều hạn chế.
Mục tiêu của luận văn này là tìm ra phương pháp nhằm nâng cao chất lượng kết
quả tìm kiếm của hệ thống tìm kiếm tiếng Việt. Để thực hiện công việc trên, luận văn
thực hiện khảo sát, nghiên cứu để đề xuất một phương pháp Mở rộng truy vấn tối ưu
cho ngôn ngữ Tiếng Việt. Để tiếp cận mục tiêu này, luận văn nghiên cứu và giới thiệu
trên vào hệ thống tìm kiếm tiếng Việt, từ đó đưa ra một số đánh giá, nhận xét
các kết quả đạt được.
9 Chƣơng 1. Bài toán Mở rộng truy vấn trong hệ thống tìm kiếm
Tìm kiếm thông tin là nhu cầu cần thiết trong cuộc sống, con người có được thông tin
từ rất nhiều nguồn tài liệu khác nhau như sách vở, tạp chí,… Hiện nay, việc tin học
hóa vào cuộc sống ngày càng cao và thời đại thông tin bùng nổ thì Internet là một
trong những nguồn tài liệu mà con người thường sử dụng nhất. Internet là một kho dữ
liệu đồ sộ, tuy nhiên để khai thác được nó là một thách thức lớn vì dữ liệu trên Internet
quá đa dạng và không có cấu trúc. Vì thế, để tìm được thông tin cần thiết và chính xác
với mong muốn của người sử dụng là một bài toán khó. Chương này sẽ giới thiệu tổng
quát về hệ thống tìm kiếm và trình bày bài toán Mở rộng truy vấn để giải quyết vấn đề
trên.
1. 1. Giới thiệu hệ thống tìm kiếm
Thông tin trên World Wide Web rất đa dạng và là kho dữ liệu lớn. Tuy nhiên,
để khai thác nguồn tri thức này một cách hiệu quả là một vấn đề lớn. Đặc biệt khi
lượng thông tin ngày càng nhiều và luôn thay đổi. Ngoài ra, hình thức thông tin cũng
ngày càng đa dạng, từ văn bản tới âm thanh, hình ảnh,… Vì vậy sẽ gây khó khăn cho
người dùng trong việc tìm kiếm thông tin. Do đó, cần phải tổ chức, quản lý thông tin
từ www cho phù hợp nhằm thuận lợi cho việc khai thác. Máy tìm kiếm ra đời là một
công cụ hữu ích cho việc khai thác thông tin. Kiến trúc chung của một hệ thống tìm
kiếm được mô tả theo như hình 1 bên dưới
Hình 1. Mô hình hệ thống tìm kiếm
10
đồng nghĩa
Ví dụ: nhập từ khóa “cafe”, kết quả trả về có thể có những tài liệu có thông tin
liên quan tới từ khóa “café”. Tuy nhiên, cũng có những tài liệu có nội dung liên
quan tới khái niệm “restaurant”. Vì vậy, dựa vào tập tài liệu trả về bao gồm
11 thông tin của cả 2 khái niệm trên, người dùng có thể tìm được thông tin đúng
với yêu cầu.
- Trường hợp khác, hệ thống cũng có thể trả về những tập tài liệu chứa câu truy
vấn nhưng có thông tin khác nhau.
Ví dụ: Nhập từ “apple”, hệ thống có thể trả về các tập tài liệu chứa từ khóa và
các từ khóa liên quan như “company” và “fruit”
Từ “apple”, có nghĩa là quả táo. Có thể liên tưởng tới việc người dùng muốn
tìm thông tin liên quan tới một loại trái cây. Tuy nhiên, “apple” cũng là thương
hiệu của một công ty sản xuất máy tính nổi tiếng. Vì vậy, để tìm được đúng tài
liệu mong muốn, người dùng phải thực hiện tìm kiếm trong tập tài liệu trả về.
Điều này gây bất tiện cho người sử dụng.
Nhận xét: Khi người dùng nhập vào các từ khóa không “tốt”, tức các từ khóa
đa nghĩa, không có ý nghĩa hoặc từ khóa thiếu thông tin về miền tri thức tìm kiếm.
Thông qua máy tìm kiếm, kết quả trả về sẽ bao gồm nhiều thông tin và người dùng sẽ
mất thêm thời gian cho việc tìm kiếm để có được thông tin mà mình mong muốn. Để
giải quyết vấn đề trên, bài toán “Mở rộng truy vấn” được đặt ra nhằm bổ sung thêm
thông tin và xác định ngữ cảnh giúp hệ thống tìm kiếm đưa ra kết quả chính xác nhất.
Định nghĩa: Mở rộng truy vấn là quá trình bổ sung một số từ vào truy vấn của
người dùng nhằm tạo ra các truy vấn mới tương đồng ngữ nghĩa, để từ đó giúp hệ
thống có thêm thông tin theo ngữ cảnh nhằm cải tiến các kết quả truy vấn [19].
Ví dụ: Câu truy vấn của người dùng: “car”
Sau khi mở rộng truy vấn, câu truy vấn mở rộng sẽ bao gồm: car, cars, automobile,
auto,
ban đầu. Vì vậy, ta cần quan tâm tới nguồn dữ liệu phục vụ cho việc mở rộng truy vấn
phải đảm bảo có đầy đủ thông tin về câu truy vấn.
13 Độ đo đƣợc sử dụng cho việc đánh trọng số các khái niệm
Để có thể đưa ra những câu truy vấn mở rộng nhằm làm rõ ý nghĩa cũng như
ngữ cảnh cho câu truy vấn thì cần phải có một cách thức đánh giá thứ tự ưu tiên cho
các khái niệm có liên quan, hay cần phải có một phương thức hay độ đo để đánh trọng
số cho các khái niệm.
1. 3. Tóm tắt chƣơng 1
Trong chương này, luận văn giới thiệu khái quát về kiến trúc chung của hệ thống tìm
kiếm, một số bài toán được đặt ra nhằm cải thiện độ chính xác cho hệ thống. Đồng
thời, đề cập tới bài toán Mở rộng truy vấn – một phương pháp xử lý truy vấn đầu vào
cho hệ thống tìm kiếm. Trong chương tiếp theo, luận văn trình bày một số phương
pháp Mở rộng truy vấn đã được nghiên cứu và công bố.
14 Chƣơng 2. Một số phƣơng pháp mở rộng truy vấn
Mở rộng truy vấn được nhiều nhà khoa học trên thế giới quan tâm vào có nhiều công
trình nghiên cứu về bài toán này [13, 15, 18]. Đã có rất nhiều nhóm giải pháp và
hướng tiếp cận khác nhau, mỗi phương pháp có những ưu nhược điểm riêng. Chương
này thực hiện trình bày các phương pháp đã được nghiên cứu và áp dụng vào Hệ thống
tìm kiếm, Hệ thống hỏi đáp, mỗi phương pháp trình bày một hướng xử lý cụ thể.
Bài toán mở rộng truy vấn được đặt ra trong việc xây dựng truy vấn ban đầu
cho việc tìm kiếm trực tuyến. Theo Efthimiadis [8], các phương pháp chính được sử
dụng để mở rộng truy vấn như sau:
- Phương pháp thủ công
A B C
Term A
1
Term B
1
Term C
1
Term A
2
Term B
2
Term C
2
Term A
3
Term B
3
Term C
3
….
Term A
3
Term B
3
Term C
3 Giới thiệu về WordNet
WordNet
4
là một từ điển trực tuyến trong Tiếng Anh, được phát triển bởi các
nhà từ điển học trường đại học Princeton. WordNet bao gồm khoảng 100.000 khái
niệm bao gồm danh từ, động từ, tính từ, phó từ liên kết với nhau thông qua 17 mối
quan hệ (được mô tả trong bảng 1) [11]. Thông thường, người ta thường hay sử dụng
WordNet cho việc tìm kiếm các mối quan hệ ngữ nghĩa. Đồng thời, dựa vào các mối
quan hệ này, một từ trong WordNet có thể tìm được các mối liên hệ với các khái niệm
khác.
Ví dụ: Từ “car” trong WordNet có thể tìm được mối liên hệ với các từ như:
Vehicle, Owner, Wheels, high,… thông qua các mối quan hệ như: is-a, has part,
hasOwner, hasSpeed,… (như hình 4)
Hình 4. Mối liên hệ giữa từ “car” với các từ khác thông qua các mối quan hệ
417 Bảng 1. Mối quan hệ ngữ nghĩa trong WordNet
Mối quan hệ
Các khái niệm đƣợc liên kết
với nhau bởi mối quan hệ
Coal has-stuff carbon
Cause-to
Động từ - Động từ
To develop cause-to to grow
Entail
Động từ - Động từ
To snore entail to sleep
Atribute
Tính từ - Danh từ
Hot attribute temperature
Synonymy
(synset)
Danh từ - Danh từ
Động từ - Động từ
Tính từ - Tính từ
Phó từ - Phó từ
Car synonym automobile
To notice synonym to observe
Happy synonym content
Mainly synonym primarily
Antonymy
Danh từ - Danh từ
Động từ - Động từ
Tính từ - Tính từ
Phó từ - Phó từ
Happines antonymy unhappiness
To inhale antonymy to exhale
Sincere antonymy insincere
Always antonymy never
Similarity
truy vấn ngắn có thể gặp khó khăn trong bước khử nhặp nhằng khi tìm kiếm thông tin,
vì quan hệ phân cấp is-a không đủ mạnh cho việc chọn các nghĩa chính xác của từ. Từ
đó, trong vấn đề về giải pháp mở rộng truy vấn sử dụng tự động các synsset được tạo
hoặc vấn đề giải quyết các ngữ nghĩa không chính xác, việc so trùng chính xác các
thiếu sót có hiệu suất truy hồi thông tin thấp hơn so với các giải pháp so trùng không
chính xác.
Năm 1994, Voorhees, đã sử dụng WordNet để tiến hành thực nghiệm trên các
tập TREC trong miền chuyên biệt. Các kết quả cho thấy việc mở rộng truy vấn có thể
cải tiến những vấn đề từ vựng không trùng khớp, đặc biệt trong trường hợp các từ
được mở rộng có liên quan về từ vựng với các từ trong truy vấn. Ngược lại, việc mở
rộng truy vấn cho các truy vấn dài chỉ cải thiện rất nhỏ tính hiệu quả của truy vấn
thông tin, vì bản thân truy vấn nguyên thủy đã mô tả đầy đủ yêu cầu thông tin.
Năm 1998, theo phân tích của nhóm Mandala [17] WordNet có nhược điểm là
các danh từ riêng không đầy đủ và không có khả năng để hình thức hóa các quan hệ
giữa các từ thuộc các phần khác nhau của từ loại. Ngoài ra, quan hệ bộ phận
(meronymy) bị hạn chế trong sự diễn dịch của nó. Để giải quyết vấn đề này, năm 2006
Grootjen và Van De Weider [10] dùng giải pháp kết hợp bao gồm một từ điển chuyên
đề toàn cục và từ điển chuyên đề cục bộ được tạo tự động. Điều này đã bổ sung những
khiếm khuyết về từ vựng trong quá trình khai thác WordNet.
Năm 2005, nhóm Nilsson [12] đã sử dụng một ontology miền đặc trưng dựa
trên hệ thống SuiS (Stockholm University Information System) để thực hiện mở rộng
truy vấn SuiS chỉ cho phép các kiểu câu hỏi gồm Who, What, When, Where và chỉ có
các từ đồng nghĩa và trái nghĩa được sử dụng để tăng độ chính xác. Thực nghiệm cho
thấy sự cải tiến mang lại kết quả tốt. Tuy nhiên, phương pháp này giới hạn đối với câu
hỏi WHO, chưa thực hiện được với các truy vấn tự do
Năm 2011, tận dụng các mối quan hệ cũng như các sự kiện đã được định nghĩa
trong ontology YAGO được mô tả ở trên, nhóm tác giả Abdullah và Rehab [1] đã sử
dung YAGO để thực hiện mở rộng truy vấn. Ngoài ra, nhóm tác giả đã sử dụng kết
quả của việc mở rộng truy vấn vào Hệ thống hỏi đáp QASYO.
20
Để tìm được các mối quan hệ giữa các truy vấn có trong tập log, ông cùng các cộng sự
đưa ra phương pháp dựa vào tập luật kết hợp, với phương pháp này tác giả đề cập tới 6
luật kết hợp
21 Ví dụ:
Ta có log của 3 người SS1, SS2, SS3 và có log của 3 giao dịch đó theo như bảng dưới:
Query log
SS1
Qa
Qb
Qc
SS2
Qa
Qb
Qd
SS3
Qa
Qb
Qe
Tương ứng với mỗi sesstion của một người, ta có T
1
= {Q
a
, Q
b
, Q
c
thường xuyên
xuất hiện cùng Q
b.
Ta sẽ có luật: Q
b
Q
a
nếu Q
b
có liên quan tới Q
a
hay Q
a
được mở
rộng truy vấn nhờ vào Q
b
- Bƣớc 2: Xây dựng đồ thị thể hiện mối quan hệ các khái niệm
Sử dụng tập querylog và tập các luật kết hợp đã được tìm thấy từ bước 1, chúng
ta có thể tìm thấy các câu truy vấn đã được thực hiện trước đó có liên quan tới câu truy
vấn hiện tại của người dùng. Cụ thể là: Chúng ta sẽ thực hiện tìm kiếm một câu truy
vấn có trong log mà có ý nghĩa tương đồng với câu truy vấn hiện tại, hay nó bao gồm
các khái niệm có trong câu truy vấn hiện tại.
Chúng ta có câu truy vấn Q
a
, sau đó sẽ tìm kiếm các câu truy vấn khác có liên
quan tới Q
a
thông qua luật kết hợp mà chúng ta đã xác định. Nếu như Q
c
j
• Xây dựng được đồ thị quan hệ G
a
cho câu truy vấn Q
a
. Trong đó:
22 – Q
i
, Q
j
là các đỉnh kề trong đồ thị G
a
– Mối quan hệ Q
i
Q
j
là cạnh của đồ thị trong G
aHình 6. Đồ thị mô tả mối quan hệ cho câu truy vấn “jaguar”.
- Bƣớc 3: Dựa vào đồ thị, chỉ ra các khái niệm có liên quan để mở rộng câu truy
vấn người dùng
Dựa vào hình 6 thì ta có thể thấy các khái niệm có liên quan tới như sau:
Concept
Đối với module Xử lý truy vấn (Query Generator), Sarmento thực hiện bằng
phương pháp mở rộng câu hỏi nhờ tập từ đồng nghĩa, cách thức thực hiện như sau:
- Bƣớc 1: Dựa vào cấu trúc ngữ pháp, xác định được cách biểu diễn của từ
đưa từ về hình thức cơ bản của từ
- Bƣớc 2: Sử dụng từ điển đồng nghĩa Lựa chọn ra n từ liên quan đầu tiên
- Bƣớc 3: Xác định các hình thức biểu diễn khác của tập từ đó. Tập hợp tất cả
các từ đồng nghĩa được biểu diễn dưới dạng mọi hình thức là tập truy vấn mở
rộng cho câu truy vấn ban đầu.
Ví dụ: Câu hỏi: “Quantas vezes ganhou Portugal a Taca Davis"
- Động từ trong câu: “ganhou”, đưa về dạng cơ bản của từ là: “ganhar”
- Thực hiện lựa chọn 5 từ đồng nghĩa nhất với từ “ganhar” là: “poupar”,
“vencer”, “conquistar”, “perder”, “ter” (“angariar”, “dar”, “disputar”)
- Lựa chọn những hình thức biểu diễn khác của các từ được mở rộng, như:
“ganh*”, “poup*”, “venc*”, “conquist*”, “perd*”, “ter”
- Sau đó sẽ thực hiện lấy tập từ mở rộng này để tìm kiếm tiếp.
2.3.4 Mở rộng truy vấn sử dụng đồ thị khái niệm wikipedia
Đồ thị khái niệm là một trong những phương pháp được sử dụng trong trí tuệ
nhân tạo nhằm đại diện cho kiến thức tiềm ẩn trong các văn bản. Dựa vào đồ thị khái
niệm, ta có thể biết được mối quan hệ giữa các khái niệm. Năm 2008, Hadi và
Abolfazl dựa trên tập dữ liệu wikipedia đã xây dựng đồ thị khái niệm [13]. Mô hình
của phương pháp theo như hình 7 bên dưới:
24
Hình 7. Mô hình Mở rộng truy vấn sử dụng đồ thị khái niệm Wikipedia
- Bƣớc 1: Thu thập dữ liệu
Dựa vào câu query q và tập tài liệu từ Wikipedia, hệ thống sử dụng máy tìm
kiếm Lemur Toolkit để thu thập dữ liệu.
chủ đề ẩn [3].
- Năm 2001, Weining Qianvà cộng sự cũng đã thực hiện mở rộng truy vấn
dựa vào cấu trúc, phương pháp này đã được áp dụng vào máy tìm kiếm
XMLS [21]
- Tháng 01/2010, máy tìm kiếm được sử dụng riêng cho Mobile được xây
dựng bởi Huy-Nguyen. Việc xây dựng máy tìm kiếm dựa trên bài toán
Phân cụm và Mở rộng truy vấn [14].
- Năm 2010, Sérgio và cộng sự giới thiệu một phương pháp mở rộng truy
vấn dựa vào các mối quan hệ giữa các gens trong lĩnh vực y tế [20].
26 2.4 Tóm tắt chƣơng 2
Trong chương hai, luận văn giới thiệu chi tiết một số phương pháp đã được
sử dụng cho việc mở rộng truy vấn. Đồng thời, cũng giới thiệu về một số hệ thống
tìm kiếm hay hệ thống hỏi đáp sử dụng một số phương pháp mở rộng truy vấn.
Trong chương tiếp theo, luận văn thực hiện đánh giá các phương pháp đã tìm hiểu
được, từ đó đề xuất một mô hình mở rộng truy vấn phù hợp với ngôn ngữ tiếng
Việt. Tiếp theo đó, áp dụng kết quả của bài toán mở rộng truy vấn vào hệ thống tìm
kiếm tiếng Việt.
Copyright: Tài liệu đại học ©