Đại Học Quốc Gia TP. Hồ Chí Minh

TRƯỜNG ĐẠI HỌC BÁCH KHOA
-------------oOo-------------

NGÔ XUÂN TIẾN
LUẬN VĂN THẠC SĨ
Chuyên Ngành: Khoa học máy tính

XÂY DỰNG CHỈ MỤC CĨ NGỮ NGHĨA
TRONG HỆ THỐNG TRUY HỒI THƠNG TIN

TP. Hồ Chí Minh, Tháng 12 – 2008


LỜI CẢM ƠN
Tôi xin chân thành cảm ơn PGS. TS. Phan Thị Tươi định hướng và tận tình
hướng dẫn tơi hồn thành luận văn này.
Xin cảm ơn q thầy, cơ trong Khoa Công nghệ thông tin trường Đại học
Bách khoa thành phố Hồ Chí Minh và Th.S Nguyễn Chánh Thành – NCS ngành
Khoa học máy tính trường Đại học Bách khoa thành phố Hồ Chí Minh đã dạy dỗ
và hướng dẫn tôi trong suốt thời gian học tập và thực hiện luận văn.
Tôi xin gửi lời cảm ơn đến gia đình, bạn bè và đồng nghiệp, những người
ln sát cánh động viên và tạo mọi điều kiện tốt nhất để tơi có thể học tập và hồn
tất được luận văn tốt nghiệp này.


TÓM TẮT
Khi đối mặt với kho dữ liệu lớn, phương pháp truy hồi thơng tin dựa vào từ
khố đã khơng cho được kết quả tìm kiếm chính xác cao như mong muốn. Đã có
nhiều nghiên cứu được đưa ra nhằm nâng cao độ chính xác tìm kiếm, nhưng các

nghiên cứu này chủ yếu tập trung vào môi trường web với việc khai thác thông tin
về mối liên kết giữa các tài liệu web với nhau. Cũng với mong muốn tăng được độ
chính xác tìm kiếm, nhưng trong luận văn của mình chúng tơi tập trung vào các
kho dữ liệu nhỏ hơn mang tính chất đặc thù riêng, từ đó xây dựng một hệ thống
chỉ mục cho phép tích hợp các nét ngữ nghĩa thu được từ kho dữ liệu này. Kho dữ
liệu mà chúng tôi chọn để thực nghiệm là các bài báo khoa học được cung bởi tạp
chí ACL.


ABSTRACT
When faces with large data storage, the information retrieval system based
on keywords has turned out not to give such an accurate result as it is expected.
There have been many studies carried out to improve the accuracy of searching,
but these researches have only focused on web environment to exploit the
information about the hyperlinks between web pages. What we do here, in this
thesis, is also with the aim of increasing searching accuracy, however we primarily
develop it in the context of the smaller domain but having specific characteristics,
and from that build an index system allowing the integration of the semantic
contents derived from this data storage. The data storage that we choose to work is
the scientific articles provided by ACL journal.


MỤC LỤC
CHƯƠNG 1 TỔNG QUAN ................................................................1
1.1.

LÝ DO CHỌN ĐỀ TÀI ................................................................. 1

1.2.


MỤC TIÊU ĐỀ TÀI....................................................................... 2

1.3.

ĐÓNG GÓP CỦA ĐỀ TÀI............................................................ 3

1.4.

Ý NGHĨA THỰC TIỄN CỦA ĐỀ TÀI ......................................... 3

1.5.

CẤU TRÚC LUẬN VĂN .............................................................. 4

CHƯƠNG 2 CƠ SỞ LÝ THUYẾT....................................................5
2.1.

Mơ hình khơng gian vector ............................................................ 5

2.2.

Tiêu chí đánh giá chất lượng hệ thống truy hồi thông tin [3] ........ 6

2.3.

Giới thiệu hệ thống truy hồi thông tin dựa theo chiến lược Term

Weighting (Trọng số từ) [4] ................................................................................. 9

CHƯƠNG 3 CÁC NGHIÊN CỨU LIÊN QUAN ĐẾN ĐỀ TÀI...17

3.1.

Kỹ thuật PageRank của Google ................................................... 17

3.2.

Cải tiến phương pháp PageRank bằng cách phân tích liên kết ở

cấp độ Block 20
3.3.

Máy tìm kiếm thơng tin web ngữ nghĩa và metadata - Swoogle . 26

CHƯƠNG 4 CƠ SỞ LÝ LUẬN CỦA ĐỀ TÀI...............................31
4.1.

Mục tiêu đề tài.............................................................................. 31

4.2.

Đặc điểm của kho dữ liệu thư viện online.................................... 32

4.3.

Kho dữ liệu ACL.......................................................................... 33

4.4.

Cấu trúc của một bài viết trên ACL ............................................. 33


4.5.

Hướng nghiên cứu của đề tài........................................................ 34

4.6.

Phương pháp xác định trọng số dựa vào nội dung tài liệu ........... 36

4.7.

Phương pháp xây dựng trọng số ngữ nghĩa dựa vào các mối quan

hệ giữa các tài liệu .............................................................................................. 41
4.8.

Trọng số tài liệu thống nhất sử dụng cho việc sắp thứ tự ............ 46


CHƯƠNG 5 CÀI ĐẶT HỆ THỐNG ...............................................48
5.1.
PDFBox

Chuyển đổi file từ định dạng pdf sang dạng text sử dụng thư viện
50

5.2.

Rút trích đặc trưng của tài liệu ACL (ACL Feature Extraction).. 50

5.3.


Lập chỉ mục tài liệu sử dụng Lucene Indexer .............................. 51

5.4.

Chuyển Lucene index sang cơ sở dữ liệu (Index Converter)....... 52

5.5.

Rút trích mối quan hệ tài liệu (ACL Relation Extraction) ........... 53

5.6.

Tính tần suất đặc trưng (fF Calculator)......................................... 53

5.7.

Tính trọng số mức độ phổ biến tài liệu (PRref Calculator) .......... 54

5.8.

Tính trọng số tài liệu sử dụng cho việc sắp thứ tự ....................... 54

5.9.

Giao diện chương trình................................................................. 55

CHƯƠNG 6 THỰC NGHIỆM ........................................................57
6.1.


Kết quả rút trích thơng tin tài liệu ACL ....................................... 57

6.2.

So sánh kết quả tìm kiếm của hệ thống với các hệ thống khác.... 58

KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN .......................................66
TÀI LIỆU THAM KHẢO ................................................................68


DANH MỤC CÁC BẢNG
Bảng 2-1: Các công thức xác định trọng số cục bộ .................................... 11
Bảng 2-2: Các công thức xác định trọng số tồn cục.................................. 12
Bảng 2-3: Cơng thức xác định thành phần chuẩn hoá ................................ 13
Bảng 2-4: Kết quả thu được khi chỉ sử dụng trọng số cục bộ..................... 14
Bảng 2-5: Kết quả thu được khi kết hợp trọng số cục bộ LOGN với từng
trọng số toàn cục .................................................................................................... 14
Bảng 2-6: Kết quả thu được khi kết hợp thêm thành phần chuẩn hoá........ 14
Bảng 2-7: Kết quả thu được khi sử dụng kết hợp trọng số cho cả tài liệu và
từ khoá truy vấn...................................................................................................... 15
Bảng 5-1: Tập giá trị trọng số của từng đặc trưng nội dung tài liệu........... 53
Bảng 6-1: Kết quả rút trích thơng tin tài liệu ACL ..................................... 57
Bảng 6-2: Độ dài từ khoá truy vấn.............................................................. 58
Bảng 6-3: Độ chính xác trung bình của các hệ thống ................................. 60
Bảng 6-4: Độ lệch tập tài liệu trả về giữa hệ thống LuceneSimC với các hệ
thống khác .............................................................................................................. 61
Bảng 6-5: Kết quả trả về của hai hệ thống đối với từ khoá “phrasal word
alignment” .............................................................................................................. 62
Bảng 6-6: Kết quả trả về đối với từ khoá “Traditional search engine” ...... 63
Bảng 6-7: Kết quả trả về đối với từ khoá “information extraction” ........... 64



DANH MỤC CÁC HÌNH
Hình 3-1: Độ chính xác trung bình theo tham số alpha cho PR-Combination
và BLPR-Combination, thực nghiệm với TREC2003 ........................................... 25
Hình 3-2: Độ chính xác theo điểm cắt P@10 theo alpha cho PRCombination và BLPR-Combination, thực nghiệm với TREC2003 ..................... 25
Hình 3-3: Kiến trúc của hệ thống Swoogle................................................. 27
Hình 3-4: Lược đồ lướt trang của Swoogle ................................................ 29
Hình 5-1: Mơ hình hoạt động của hệ thống S_Engine................................ 49
Hình 5-2: Giao diện người dùng nhập thông tin truy vấn........................... 55
Hình 5-3: Giao diện trả kết quả tìm kiếm cho người dùng ......................... 56
Hình 5-4: Giao diện xem nội dung tài liệu.................................................. 56


CHƯƠNG 1
TỔNG QUAN

1.1.

LÝ DO CHỌN ĐỀ TÀI
Trong thời đại bùng nổ thông tin như hiện nay, khi mà các kho dữ liệu

thường rất lớn, thì thách thức mà nó mang lại cho con người là làm thế nào để có
thể quản lý và truy xuất thông tin một cách nhanh chóng và chính xác. Điều này
địi hỏi các hệ thống truy hồi thơng tin phải duy trì hoặc tăng được độ chính xác
tìm kiếm. Đối với các hệ thống truy hồi thơng tin truyền thống chỉ dựa vào từ khố
thì việc duy trì này là khơng thể. Vì vậy, nhiều nghiên cứu đã ra đời với mục đích
tích hợp thêm các nét ngữ nghĩa đặc thù của từng loại tài liệu nhằm nâng cao độ
chính xác của hệ thống.
Trong những năm gần đây, sự ra đời của hệ thống tìm kiếm Google đã đánh

dấu sự thành công cho hướng nghiên cứu tích hợp ngữ nghĩa này. Bằng cách khai
thác thơng tin về mối liên kết giữa các tài liệu trong môi trường web để xác định
mức độ phổ biến của từng tài liệu, Google đã tạo nên nét ngữ nghĩa mới cho tài
liệu tích hợp thêm vào hệ thống. Sự tích hợp này đã giúp Google phần nào đáp
ứng được như cầu tìm kiếm thơng tin của người dùng trong mơi trường web và trở
thành hệ thống tìm kiếm thơng tin trong môi trường web phổ biến tại thời điểm
hiện nay.
Tuy nhiên, với việc giữ kín mơ hình hoạt động và hầu như chỉ tập trung vào
môi trường web nên Google khơng thể đáp ứng tốt nhu cầu tìm kiếm đối với các
hệ thống dữ liệu cục bộ của người dùng cũng như các hệ thống dữ liệu mà các tài
liệu không phải là tài liệu web, do không thể rút trích được thơng tin về mối liên
kết giữa các tài liệu này.
Ngược lại với việc giữ kín mơ hình hoạt động của Google, Lucene được
biết đến như một thư viện mã nguồn mở để hỗ trợ người dùng xây dựng hệ thống
-1-


truy hồi thơng tin cho phép tìm kiếm thơng tin trong toàn bộ nội dung tài liệu. Tuy
nhiên Lucene được thiết kế để có thể hỗ trợ tất cả các dạng tài liệu mà không quan
tâm đến ngữ nghĩa của nội dung, do đó Lucene khơng thể khai thác và tích hợp các
nét ngữ nghĩa đối với các dạng dữ liệu đặc thù.
Với các kho dữ liệu cụ thể, khi mà các tài liệu trong đó tồn tại một số đặc
trưng chung có thể truy xuất được, thì việc khai thác các đặc trưng này khi xây
dựng hệ thống truy hồi thông tin sẽ là tiền đề cho phép ta có thể gia tăng được độ
chính xác. Với mong muốn có thể gia tăng được độ chính xác truy hồi thông tin
trong một kho dữ liệu cụ thể, chúng tôi giới hạn kho dữ liệu của mình là tập các
tài liệu được trích đăng trên tạp chí ACL (The Association for Computational
Linguistics) [15]. ACL là một tạp chí chuyên ngành về ngơn ngữ học tính tốn,
nên các tài liệu trích đăng thường có chủ đề về máy tính và được viết theo một
đinh dạng chuẩn. Việc giới hạn này cho phép chúng tơi rút trích được các đặc

trưng của tài liệu như tên tài liệu, tên tác giả, thông tin tóm tắt, các tài liệu tham
khảo … và sử dụng các đặc trưng này kết hợp với mơ hình truy hồi thơng tin dựa
vào từ khố để xây dựng một hệ thống chỉ mục tích hợp ngữ nghĩa, cho phép việc
truy hồi thơng tin có độ chính xác tốt hơn.

1.2.

MỤC TIÊU ĐỀ TÀI
Mục tiêu của đề tài là xây dựng một chỉ mục cho phép tích hợp thêm các

nét ngữ nghĩa khác ngoài nội dung tài liệu nhằm làm tăng độ chính xác tìm kiếm.
Trong phạm vi đề tài chúng tơi thực hiện tích hợp hai nét ngữ nghĩa sau:
Nét ngữ nghĩa về vị trí xuất hiện từ khố trong các đặc trưng nội dung của
tài liệu (trình bài trong phần 4.6): các hệ thống truy hồi thông tin thường khơng
xác định đặc trưng nội dung tài liệu, do đó khơng quan tâm đến vị trí xuất hiện của
từ khố trong tài liệu. Tuy nhiên, khi xác định được đặc trưng nội dung của tài
liệu, ta nhận thấy rằng các tài liệu có từ khố xuất hiện trong các đặc trưng quan
trọng như tên tài liệu, phần tóm tắt … sẽ có xác suất phù hợp với từ khố đó cao
hơn. Vì vậy, bằng cách xác định được vị trí xuất hiện của từ khoá trong đặc trưng
-2-


nào của tài liệu để làm nét ngữ nghĩa sẽ là cơ sở để ta có thể năng cao độ chính xác
của hệ thống.
Nét ngữ nghĩa về mối quan hệ tài liệu (trình bài trong phần 4.7): từ việc xác
định được tác giả và tập tài liệu tham khảo của một tài liệu, ta có thể xác định
được hai mối quan hệ là quan hệ tham khảo và quan hệ cùng tác giả. Ta thấy rằng
một tài liệu được tham khảo bởi nhiều tài liệu khác thì thường là tài liệu có nội
dung tốt vì vậy nó nên được trả về cho người dùng. Tương tự, một tài liệu có cùng
tác giả với nhiều tài liệu khác về cùng một chủ đề thì nó có xác suất cao là thuộc

về chủ để đó. Từ những nhận xét này chúng tơi đã sử dụng hai mối quan hệ trên
làm nét ngữ nghĩa tích hợp vào hệ thống.

1.3.

ĐĨNG GĨP CỦA ĐỀ TÀI
Đề tài đã đề ra phương pháp cho phép xác định trọng số dựa vào các đặc

trưng về nội dung tài liệu, sử dụng để cải tiến mơ hình tìm kiếm dựa vào từ khoá
truyền thống.
Đề tài đề xuất phương pháp kết hợp các nét ngữ nghĩa khác nội dung (các
mối quan hệ) của tài liệu với thông tin nội dung để xác định một giá trị chung của
từng tài liệu, phục vụ cho việc sắp thứ tự tài liệu.

1.4.

Ý NGHĨA THỰC TIỄN CỦA ĐỀ TÀI
Đề tài có thể được phát triển để phục vụ việc lập chỉ mục cho các kho dữ

liệu đặc thù như thư viện số, cho phép người dùng cấu hình tích hợp các nét ngữ
nghĩa như nhà xuất bản, tác giả, chủ đề, lượt truy cập … để nâng cao độ chính xác
tìm kiếm.

-3-


1.5.

CẤU TRÚC LUẬN VĂN
Luận văn bao gồm 6 chương: Tổng quan, Cơ sở lý thuyết, Các nghiên cứu


liên quan đến đề tài, Cơ sở lý luận của đề tài, Cài đặt hệ thống, Thực nghiệm.
Trong phần mở đầu chúng tôi nêu lý do chọn đề tài, mục tiêu đề tài, đóng
góp của đề tài cũng như ý nghĩa thực tiễn của đề tài.
Phần cơ sở lý thuyết chúng tơi trình bày một số cơ sở lý thuyết nền tảng để
có được cái nhìn tổng quan về hệ thống truy hồi thơng tin như: Mơ hình khơng
gian vector, Tiêu chí đánh giá chất lượng hệ thống truy hồi thông tin, và giới thiệu
mơ hình hệ thống truy hồi thơng tin sử dựng cơ chế trọng số từ.
Phần các nghiên cứu liên quan đến đề tài, chúng tôi giới thiệu các hướng
nghiên cứu đã ảnh hướng đến cơ sở lý luận của đề tài. Các nghiên cứu này chủ yếu
tập trung vào việc nâng cao tính chính xác của hệ thống truy hồi thơng tin bằng
cách tích hợp thêm các đặc trưng ngữ nghĩa khác của tài liệu vào mơ hình truy hồi
thơng tin dựa từ khố, bao gồm: Kỹ thuật PageRank của Google, Cải tiến phương
pháp PageRank bằng cách phân tích liên kết ở cấp độ block, Máy tìm kiếm thơng
tin web ngữ nghĩa và metadata Swoogle.
Trong phần cơ sở lý luận của đề, tài chúng tơi trình bày những lý luận cần
thiết để xây dựng hệ thống chỉ mục hỗ trợ ngữ nghĩa. Phần này chủ yếu tập trung
vào việc xây dựng phương pháp xác định trọng số dựa vào nội dung tài liệu và
phương pháp xác định trọng số dựa vào mối quan hệ giữa các tài liệu.
Trong phần cài đặt hệ thống, chúng tơi đưa ra mơ hình hoạt động của hệ
thống cũng như giải thích chi tiết hoạt động từng module của mơ hình.
Cuối cùng chúng tơi trình bày các kết quả thực nghiệm thu được, từ đó đưa
đến kết luận, cũng như đưa ra định hướng về các hướng phát triển của đề tài.

-4-


CHƯƠNG 2
CƠ SỞ LÝ THUYẾT
Để nâng cao chất lượng tìm kiếm, các hệ thống truy hồi thông tin thường

được phát triển bằng cách tích hợp thêm một số đặc trưng vào một mơ hình truy
hồi thơng tin cổ điển dựa vào từ khố. Vì vậy trong chương này chúng tơi trình
bày một số cơ sở lý thuyết cho phép ta có cái nhìn tổng quan về hệ thống truy hồi
thơng tin cổ điển, phương pháp đánh giá chất lượng, cũng như các kết quả thực
nghiệm về chất lượng đạt được của các hệ thống truy hồi thơng tin này.

2.1.

Mơ hình không gian vector

2.1.1. Khái niệm
VSM (Vector Space Model) [1] là một mơ hình cho phép mơ tả tài liệu text
dưới dạng vector nhằm hỗ trợ việc tính tốn. VSM được sử dụng trong các ứng
dụng lọc thông tin, truy hồi thông tin, lập chỉ mục và sắp thứ tự tài liệu dựa theo
mức độ tương tự giữa nội dung tài liệu với từ khố truy vấn.
Trong mơ hình VSM, một tài liệu được mô tả bởi một vector. Mỗi phần tử
của vector tương ứng với một term (thông thường là một từ). Nếu term xuất hiện
trong tài liệu thì giá trị của nó trong vector là khác 0, ngược lại sẽ bằng 0. Để
VSM có thể hoạt động được, cần phải có thêm thuật tốn xác định giá trị của các
phần tử của vector. Có nhiều giải pháp khác nhau đã được đề xuất, trong đó giải
pháp được biết đến nhiều nhất là giải pháp đánh trọng số tf-idf [2]. Giải pháp này
xác định các giá trị trọng số dựa vào tần suất xuất hiện từ (term frequency) và
nghịch đảo tần suất tài liệu (inverse document frequency).
Việc xác định một term phụ thuộc vào từng ứng dụng. Thường thì term là
một từ đơn, một từ khoá hoặc một cụm từ dài hơn. Nếu từ đơn được chọn làm

-5-


term thì số chiều của vector sẽ là số lượng từ (khơng trùng nhau) trong tồn tập từ

vựng.
2.1.2. Ứng dụng của VSM
Trong các hệ thống truy hồi thông tin, VMS được sử dụng để tính tốn mức
độ tương tự của tài liệu với từ khoá truy vấn. Để xác định mức độ tương tự của tài
liệu với từ khoá, cả tài liệu và từ khố sẽ được mơ tả dưới dạng vector. Khi đó,
mức độ tự được xác định bằng độ lớn của góc lệch giữa hai vector này. Cụ thể
mức độ tương tự tỉ lệ thuận với giá trị cosin của góc lệch giữa hai vector.
Gọi v1, v2 lần lượt là vector mô tả tài liệu và câu truy vấn, ta có độ tương tự
giữa tài liệu và từ khoá truy vấn là:
cos θ =

v1 .v 2
v1 . v 2

Nếu cosθ bằng 0 nghĩa là từ khoá truy vấn và tài liệu khơng có thơng tin
nào trùng với nhau hay tài liệu và từ khố hồn tồn khác nhau. Ngược lại, giá trị
cosθ càng lớn thì tài liệu và từ khoá sẽ càng giống với nhau. Bằng cách so sánh giá
trị về độ tương tự này của các tài liệu với nhau, hệ thống có thể sắp thứ tự các tài
liệu để trả về cho người dùng.

2.2.

Tiêu chí đánh giá chất lượng hệ thống truy hồi thông tin [3]
Các hệ thống truy hồi thơng tin thực hiện việc tính toán và trả về cho người

dùng một danh sách tài liệu tương ứng với mỗi câu truy vấn nhận được. Danh sách
này sẽ có một số tài liệu là tốt (theo ý nghĩa là tài liệu phù hợp với mong muốn của
người dùng), tuy nhiên cũng có một số tài liệu khơng tốt. Chất lượng của hệ thống
tìm kiếm được đánh giá theo các tiêu chí sau:
•


Số các tài liệu tốt trong danh sách trả về

•

Số các tài liệu tốt khơng trả về được trong danh sách

•

Vị trí của các tài liệu tốt trong danh sách

-6-


Từ các tiêu chí này, hai độ đo được đề xuất dùng để đánh giá chất lượng hệ
thống truy hồi thơng tin là độ chính xác và độ truy hồi. Độ chính xác là số đo về
tính hữu ích của danh sách tài liệu trả về, trong khi độ truy hồi là số đo về tính đầy
đủ của danh sách đó. Trong trường hợp lý tưởng, hệ thống truy hồi thông tin sẽ trả
về tất cả các tài liệu tốt và không trả về bất kỳ tài liệu xấu nào. Khi đó hệ thống
được gọi là có độ chính xác và độ truy hồi tuyệt đối. Tuy nhiên thực tế cho thấy
các hệ thống thường trả về tập hợp có cả tài liệu phù hợp và tài liệu không phù
hợp với mong muốn của người dùng.
2.2.1. Độ truy hồi
Độ truy hồi (recall) được tính bằng số lượng tài liệu phù hợp trong danh
sách trả về chia cho số lượng tài liệu phù hợp trong tồn bộ hệ thống. Cơng thức
xác định độ truy hồi như sau:
recall =

{relevantDocument}∩ {retrievedDocument}
{relevantDocument}


Trong đó:
•

{RelevantDocument}: là tập các tài liệu phù hợp với từ khoá truy
vấn trong tồn bộ hệ thống

•

{RetrievedDocument}: là tập các tài liệu mà hệ thống trả về khi
nhận được từ khoá truy vấn

Độ truy hồi phản ánh chất lượng của hệ thống trong việc tìm kiếm tài liệu.
Độ truy hồi bằng 100% khi tất cả các tài liệu phù hợp đều được trả về. Về mặt lý
thuyết ta có thể dễ dàng nhận được độ truy hồi tốt, đơn giản bằng cách trả về tất cả
các tài liệu trong kho dữ liệu cho mọi từ khố truy vấn nhận được. Do đó, chỉ với
độ truy hồi thì khơng thể làm số đo để đánh giá chất lượng của hệ thống truy hồi
thông tin.

-7-


2.2.2. Độ chính xác
Độ chính xác (Precision) được tính bằng số tài liệu phù hợp trong danh
sách trả về chia cho số lượng tài liệu mà hệ thống trả về cho người dùng. Cơng
thức như sau:
precision =

{relevantDocument}∩ {retrievedDocument}
{retrievedDocument}


Độ chính xác phản ánh chất lượng của hệ thống trong việc loại bỏ các tài
liệu không phù hợp ra khỏi danh sách trả về. Độ chính xác là 100% nếu tất cả các
tài liệu trả về đều phù hợp với câu truy vấn.
Để xây dựng được một hệ thống truy hồi thông tin tốt cần phải làm tăng độ
chính xác mà khơng làm mất độ truy hồi của hệ thống. Tuy nhiên hầu hết các hệ
thống tìm kiếm hiện tại thường được xây dựng với độ truy hồi tốt nhưng độ chính
xác lại thấp, nghĩa là nó trả về một số tài liệu phù hợp cùng với nhiều tài liệu
không phù hợp với ý muốn của người dùng. Đây là các hệ thống khơng tốt vì khi
sử dụng các hệ thống này người dùng sẽ phải mất nhiều thời gian để tìm được tài
liệu phù hợp với nhu cầu của mình trong tập tài liệu trả về.
2.2.3. Độ chính xác theo điểm cắt
Độ truy hồi và độ chính xác được tính trong tồn bộ tập tài liệu trả về. Vì
vậy nó khơng hỗ trợ việc đánh giá các hệ thống có sắp thứ tự các tài liệu trả về cho
người dùng. Thông thường người dùng muốn các tài liệu trả về được sắp xếp thứ
tự dựa vào mức độ tương tự của nó với câu truy vấn, sao cho các tài liệu phù hợp
nhất sẽ được trả về đầu tiên. Chất lượng của hệ thống có sắp thứ tự tài liệu trả về
được đo bằng cách xác định độ chính xác tại các điểm cắt khác nhau. Cách tính độ
chính xác tại điểm cắt i (gọi là precision[i] hay P@i) như sau:

∑
precision[i ] = P @ i =
•

i
k =1

rel[k ]
i


Với: rel[k] bằng 1 nếu tài liệu thứ k trong danh sách là phù hợp;
bằng 0 nếu ngược lại.
-8-


Ví dụ: nếu 10 tài liệu trả về đầu tiên đều phù hợp và 10 tài liệu tiếp theo
không phù hợp thì độ chính xác tại điểm cắt 10 tài liệu là P@10 = 100%, và độ
chính xác tại điểm cắt 20 tài liệu là P@20 = 50%.
2.2.4. Độ chính xác trung bình
Ta thấy độ chính xác theo điểm cắt khơng quan tâm đến độ truy hồi. Vì vậy
một phép đo mới được đề xuất gọi là độ chính xác trung bình kết hợp độ chính xác
của tập sắp thứ tự và độ truy hồi. Độ chính xác trung bình được tính bằng tổng số
độ chính xác tại các điểm cắt trong danh sách tài liệu trả về chia cho tổng số tài
liệu phù hợp trong toàn kho dữ liệu. Công thức cụ thể như sau:

∑
Averageprecision =

n

i =1

( precision[i ] * rel[i ])
R

Trong đó:
•

rel[i] bằng 1 nếu tài liệu thứ i trong danh sách là phù hợp, bằng 0
nếu ngược lại.


•

n là số lượng tài liệu trong tập danh sách trả về

•

R là số lượng tài liệu phù hợp trong tồn kho dữ liệu

Độ chính xác trung bình được xem như số đo đánh giá chất lượng của của
hệ thống truy hồi thông tin. Ta nhận thấy rằng, để đạt được độ chính xác trung
bình bằng 1 thì hệ thống phải trả về tất cả các tài liệu phù hợp (recall = 1) và phải
sắp thứ tự một cách tối ưu (nghĩa là độ chính xác tại điểm cắt R = 1).

2.3.

Giới thiệu hệ thống truy hồi thông tin dựa theo chiến lược Term

Weighting (Trọng số từ) [4]
Các hệ thống truy hồi thông tin cổ điển thường được xây dựng dựa trên mơ
hình VSM, trong đó thành phần cấu thành các vector của mơ hình này được xác
định theo chiến lược trọng số từ. Theo chiến lược này thì các giá trị này được tính
tốn dựa vào tần suất xuất hiện của các từ trong nội dung tài liệu hoặc trong từ
khoá truy vấn và số lượng tài liệu chứa từ đó trong tồn kho dữ liệu.
-9-


2.3.1. Chiến lược trọng số từ
Một chiến lược xác định trọng số là sự kết hợp của 3 thành phần khác nhau
là:

•

Trọng số cục bộ (local)

•

Trọng số tồn cục (global)

•

Thành phần chuẩn hoá (normalization)

Trọng số cục bộ là hàm số xác định số lần xuất hiện của mỗi từ trong nội
dung của tài liệu hoặc trong từ khoá truy vấn. Trọng số toàn cục là hàm số xác
định số tài liệu có chứa từ trong tồn kho dữ liệu. Thành phần chuẩn hố có ý
nghĩa để bù trừ ảnh hưởng của độ dài tài liệu. Trọng số chung của một từ i trong
tài liệu j, Wij được xác định bởi cơng thức:
Wij = Lij * Gi * Nj
Trong đó:
•

Lij là trọng số cục bộ của từ i trong tài liệu j

•

Gi là trọng số tồn cục của từ i

•

Nj là thành phần chuẩn hoá cho tài liệu j


2.3.2. Trọng số cục bộ
Trọng số cục bộ được xây dựng dựa trên quan niệm rằng một từ xuất hiện
trong tài liệu với tần suất cao hơn thì càng có ý nghĩa với tài liệu đó, vì vậy trọng
số cục bộ của từ đó đối với tài liệu sẽ có giá trị cao nhằm làm tăng giá trị trọng số
chung của tài liệu. Bảng 2-1 liệt kê một số công thức được sử dụng để tính trọng
số cục bộ:

- 10 -


Bảng 2-1: Các công thức xác định trọng số cục bộ

Trong đó:
•

fij là tần suất xuất hiện của từ i trong tài liệu j

•

aj là tần suất xuất hiện trung bình của các từ trong tài liệu j

•

xj là tần suất xuất hiện lớn nhất của các từ trong tài liệu j

- 11 -


2.3.3. Trọng số tồn cục

Trọng số tồn cục có ý nghĩa xác định mức độ quan trọng giữa các từ với
nhau. Với ý tưởng là một từ có số lượng tài liệu chứa nó càng ít thì mức độ quan
trọng của nó càng cao. Như vậy một từ xuất hiện trong càng ít tài liệu thì trọng số
tồn cục của nó sẽ càng lớn để làm tăng tác động của từ đó vào trọng số chung của
tài liệu. Bảng 2-2 liệt kê các cơng thức được sử dụng để tính trọng số tồn cục:

Bảng 2-2: Các cơng thức xác định trọng số tồn cục

Trong đó:
•

N là số lượng tài liệu trong tồn kho dữ liệu

•

ni là số tài liệu có chứa từ i

•

Fi là tần suất xuất hiện của từ i trong toàn tập dữ liệu

- 12 -


2.3.4. Thành phần chuẩn hoá
Thành phần chuẩn hoá được dùng để chuẩn hoá vector tài liệu nhằm giúp
việc xác định trọng số chung của tài không phụ thuộc vào độ dài của tài liệu. Các
cơng thức sử dụng để tính thành phần chuẩn hoá được liệt kê trong bảng 2-3:

Bảng 2-3: Cơng thức xác định thành phần chuẩn hố


Trong đó:
•

lj là số lượng các từ không trùng nhau trong tài liệu j

•

slope có giá trị 0.2

•

pivot là giá trị trung bình của số lượng từ khơng trùng nhau của mỗi
tài liệu, xét chung cho toàn kho dữ liệu

2.3.5. Kết quả thực nghiệm về độ chính xác thu được khi kết hợp các cơng
thức với nhau
Trong phần này chúng tơi trình bày các kết quả thực nghiệm mà bài báo [4]
ghi nhận được về độ chính xác của hệ thống truy hồi thông tin khi thực hiện việc
kết hợp các công thức lại với nhau. Các kết quả thực nghiệm được thực hiện nhằm
xác định hiệu quả của từng công thức cũng như hiệu quả của việc kết hợp giữa các
loại trọng số. Kết quả thực nghiệm xây dựng dựa trên hai tiêu chí thường được sử
dụng để đánh giá chất lượng của các hệ thống truy hồi thông tin là độ chính xác và
độ truy hồi.
Các bảng 2-4, 2-5, 2-6, 2-7 dưới đây là các kết quả bài báo ghi nhận trong
các trường hợp sử dụng riêng, hay kết hợp giữa các thành phần trọng số với nhau.

- 13 -



Bảng 2-4: Kết quả thu được khi chỉ sử dụng trọng số cục bộ

Bảng 2-5: Kết quả thu được khi kết hợp trọng số cục bộ LOGN với từng trọng số
toàn cục

Bảng 2-6: Kết quả thu được khi kết hợp thêm thành phần chuẩn hoá

- 14 -


Bảng 2-7: Kết quả thu được khi sử dụng kết hợp trọng số cho cả tài liệu và từ khoá
truy vấn

2.3.6. Nhận xét về kết quả thực nghiệm của bài báo
Dựa vào kết quả thực nghiệm của bài báo ta nhận thấy:
Theo số liệu bảng 2-4, nếu chỉ sử dụng trọng số cục bộ thì độ chính xác
trung bình thay đổi tùy theo từng công thức, cụ thể giá trị này thay đổi từ giá trị
thấp nhất là 7.15% khi sử dụng công thức Binary (BNRY), đến giá trị cao nhất thu
được là 7.92% khi sử dụng công thức Normalized Log (LOGN)
Theo số liệu bảng 2-5, việc kết hợp hai thành phần trọng số cục bộ và trọng
số toàn cục giúp cải thiện được chất lượng của hệ thống, vì hầu hết các sự kết hợp
đều thu được độ chính xác trung bình cao hơn (lớn hơn 7.92%). Sự kết hợp giữa
Normalized Log (LOGN) và Probabilistic Inverse (IDFP) thu được độ chính xác
trung bình cao nhất là 9.30%
Trong khi đó theo kết quả thu được từ bảng 2-6 cho thấy thành phần chuẩn
hố khi được kết hợp khơng đem lại hiệu quả, do khơng làm tăng thêm độ chính
xác ở tất cả các hình thức kết hợp
Số liệu trong bảng 2-7 thể hiện kết quả thu được khi sự kết hợp giữa trọng
số cục bộ và trọng số toàn cục được áp dụng cho cả tài liệu và từ khoá truy vấn.
Kết quả cho thấy việc kết hợp này làm tăng đáng kể chất lượng hệ thống khi độ

chính xác trung bình đạt giá trị 12.35% (sử dụng LOGN-IDFP).

- 15 -


Như vậy ta thấy việc lựa chọn các công thức cũng như chiến lược kết hợp
các công thức này với nhau sẽ giúp ta thu được các độ chính xác trung bình khác
nhau. Nói cách khác chất lượng của hệ thống truy hồi thông tin sẽ phụ thuộc vào
chiến lược kết hợp các cơng thức này. Tuy nhiên độ chính xác trung bình cao nhất
thu được chỉ đạt mức 12.35% là không cao, dẫn đến chất lượng của hệ thống thu
được khơng cao.
Như vậy có thể thấy, nếu muốn xây dựng các hệ thống truy hồi thơng tin có
độ chính xác cao thì việc chỉ sự dụng cơ chế trọng số từ là chưa đủ, mà địi hỏi cần
phải có sự kết hợp bổ sung với các phương pháp khác.

- 16 -


CHƯƠNG 3
CÁC NGHIÊN CỨU LIÊN QUAN ĐẾN ĐỀ TÀI

Trong chương này chúng tôi xin giới thiệu một số nghiên cứu về hệ thống
truy hồi thông tin. Các nghiên cứu này tập trung chủ yếu vào việc cải thiện độ
chính xác tìm kiếm theo hướng tích hợp vào hệ thống các đặc trưng của các kho
dữ liệu cụ thể. Đây là những nghiên cứu đã định hướng cho ý tưởng của đề tài
chúng tơi.

3.1.

Kỹ thuật PageRank của Google

Như đã trình bày ở phần 2.3, đối với các hệ thống truy hồi thơng tin sử

dụng mơ hình VSM kết hợp với chiến lược trọng số từ, thì độ chính xác thu được
sẽ không cao. Trong khi kho dữ liệu internet ngày càng lớn thì với các hệ thống có
độ chính xác thấp đòi hỏi người dùng phải mất nhiều thời gian để tìm kiếm tài liệu
mà mình mong muốn trong tập kết quả trả về. Để có thể phục vụ tốt hơn cho
người dùng thì điều kiện tiên quyết là phải nâng cao độ chính xác của các hệ thống
tìm kiếm.
Nhằm nâng cao độ chính xác, nhiều nghiên cứu ([6], [7], [8], [9], [10], [11],
[12]) đã được xây dựng, đề cập đến việc khai thác thông tin về các mối quan hệ
giữa các tài liệu với nhau. Trong số các nghiên cứu này thì kỹ thuật PageRank [6]
của Google đã khai thác thông tin liên kết (hyperlink) giữa các tài liệu web và có
thể được xem là phương pháp đã khai thác thành công nhất.
3.1.1. Trật tự sắp xếp cho môi trường web
Mối liên kết giữa các tài liệu trong môi trường web là tài nguyên quan
trọng cho phép xác định mức độ phổ biến của một trang web. Với ý tưởng, một
trang web được liên kết đến bởi một trang web của người dùng khác chứng tỏ nó

- 17 -