ðại Học Quốc Gia Tp. Hồ Chí Minh
TRƯỜNG ðẠI HỌC BÁCH KHOA
--------------------

NGÔ THI

PHÁT TRIỂN MỘT GIẢI THUẬT XẾP HẠNG CÁC
THÔNG TIN TRUY HỒI TRÊN MÔI TRƯỜNG WEB DỰA
TRÊN CÁC THỰC THỂ CĨ TÊN
Chun ngành: Khoa học máy tính
Mã số ngành: 60.48.01

LUẬN VĂN THẠC SĨ

TP. HỒ CHÍ MINH, tháng 6 năm 2008


ii

CƠNG TRÌNH ðƯỢC HỒN THÀNH TẠI
TRƯỜNG ðẠI HỌC BÁCH KHOA
ðẠI HỌC QUỐC GIA TP HỒ CHÍ MINH

Cán bộ hướng dẫn khoa học : TS. Quản Thành Thơ.........................................

Cán bộ chấm nhận xét 1 : PGS. TS. Cao Hoàng Trụ.......................................

Cán bộ chấm nhận xét 2 : TS. Nguyễn ðức Cường ..........................................

Luận văn thạc sĩ ñược bảo vệ tại
HỘI ðỒNG CHẤM BẢO VỆ LUẬN VĂN THẠC SĨ

TRƯỜNG ðẠI HỌC BÁCH KHOA, ngày 5 tháng 9 năm 2008.


ðẠI HỌC QUỐC GIA TP. HCM
TRƯỜNG ðẠI HỌC BÁCH KHOA
----------------

CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM
ðộc Lập - Tự Do - Hạnh Phúc
---oOo--Tp. HCM, ngày . .20. . tháng . .6. . năm .2008.

NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ và tên học viên : Ngơ Thi......................................Giới tính : Nam / Nữ
Ngày, tháng, năm sinh : 9/7/1983 ...............................Nơi sinh : Khánh Hồ ...........
Chun ngành : Khoa học máy tính...........................................................................
Khố : 2006..............................................................................................................
1- TÊN ðỀ TÀI : .....................................................................................................
PHÁT TRIỂN MỘT GIẢI THUẬT XẾP HẠNG CÁC THÔNG TIN TRUY
HỒI TRÊN MÔI TRƯỜNG WEB DỰA TRÊN CÁC THỰC THỂ CÓ TÊN
................................................................................................................................
2- NHIỆM VỤ LUẬN VĂN : ...................................................................................
................................................................................................................................
................................................................................................................................
................................................................................................................................
................................................................................................................................
3- NGÀY GIAO NHIỆM VỤ : 21/1/2008 ...............................................................
4- NGÀY HOÀN THÀNH NHIỆM VỤ : 30/6/2008 ..............................................
5- HỌ VÀ TÊN CÁN BỘ HƯỚNG DẪN : TS. Quản Thành Thơ ..........................
Nội dung và ñề cương Luận văn thạc sĩ ñã ñược Hội ðồng Chuyên Ngành thông qua.
CÁN BỘ HƯỚNG DẪN

(Họ tên và chữ ký)

CHỦ NHIỆM BỘ MÔN
QUẢN LÝ CHUYÊN NGÀNH
(Họ tên và chữ ký)

TS. Quản Thành Thơ

TS. ðinh ðức Anh Vũ


LỜI CAM ðOAN
Tơi cam đoan rằng, ngoại trừ các kết quả tham khảo từ các cơng trình khác
như đã ghi rõ trong luận văn, các cơng việc trình bày trong luận văn này là do chính
tơi thực hiện và chưa có phần nội dung nào của luận văn này được nộp ñể lấy một
bằng cấp ở trường này hoặc trường khác.
Ngày 20 tháng 6 năm 2008
Ngô Thi


5

LỜI CẢM ƠN

ðầu tiên, xin ñược gởi lời cảm ơn sâu sắc nhất ñến Thầy TS. Quản Thành
Thơ, người Thầy đã tận tình hướng dẫn tơi bắt đầu từ mơn chun đề cho đến khi
hồn thành luận văn, xin cảm ơn Thầy vì đề tài thật hay này.
Em xin cảm ơn Thầy PGS.TS Cao Hồng Trụ, chủ nhiệm đề tài VN-KIM, đã
tạo mọi điều kiện thuận lợi để em có thể hoàn thành luận văn.
Xin cảm ơn thạc sĩ Huỳnh Tấn ðạt, kỹ sư Nguyễn Minh Luân, kỹ sư Hồng

Trung Dũng, kỹ sư Hồng Minh Sơn trong nhóm dự án VN-KIM đã tận tình giúp
đỡ để luận văn được hồn thành như hôm nay.
Cuối cùng, con cảm ơn Ba, Má và những người thân đã khích lệ, động viên
con trong thời gian học tập, nghiên cứu để có được thành quả như ngày nay.
Tháng 6 năm 2008
Học viên
Ngô Thi


6

TĨM TẮT
Ngày nay thơng tin đóng vai trị hết sức quan trọng trong mọi lĩnh vực ñời
sống, kinh tế, xã hội. Cùng với sự bùng nổ dữ liệu web, vai trị của cơng cụ truy hồi
và sắp hạng thơng tin ñã ñược khẳng ñịnh.
Giải thuật xếp hạng thông tin truy hồi theo từ khóa PageRank là giải thuật
cho chất lượng xếp hạng khá tốt. Mặt khác việc chú thích ngữ nghĩa cho tài liệu
web truyền thống ñã ñạt ñược những kết quả rất khả quan. Việc kết hợp giải thuật
PageRank và ngữ nghĩa của các thực thể có tên được nhận diện trên các trang web
ñể cải thiện chất lượng xếp hạng là một hướng ñi hợp lý.
Trong luận văn này, chúng tơi đã đề ra hướng áp dụng giải thuật PageRank
để xây dựng 4 vector PageRank cho các khơng gian name, class, name+class và id
của thực thể có tên cho mỗi trang web (NE PageRank). Kết quả ñạt ñược là cơ sở
cho hai phương pháp sắp hạng dựa trên việc kết hợp hai ñộ ño NE PageRank và
Sim (ñộ tương tự giữa truy vấn với trang web).
Kết quả ñạt ñược cho thấy, các kết quả trên cùng theo sắp hạng của giải thuật
NE PageRank có chất lượng rất tốt. Hai phương pháp sắp hạng dựa trên sự kết hợp
hai ñộ ño NE PageRank và Sim kế thừa ñược ưu ñiểm của cả hai hệ thống. ðộ
chính xác của các kết quả ñược truy hồi tốt hơn các hệ thống dựa trên từ khóa
truyền thống nhờ dựa trên thực thể có tên.

Kết luận, web ngữ nghĩa là hướng phát triển tất yếu của thế hệ web kế tiếp.
Tiếp tục phát triển các giải thuật xếp hạng cho thông tin truy hồi trên mơi trường
web nói chung và web có ngữ nghĩa nói riêng là một hướng đi đúng, sẽ đem lại
nhiều lợi ích to lớn và cần được duy trì.


Mục lục

LỜI CAM ðOAN ..................................................................................................................4
LỜI CẢM ƠN ........................................................................................................................5
TÓM TẮT ...............................................................................................................................6
Danh mục các hình................................................................................................................9
Danh mục các bảng .............................................................................................................11
Chương 1 Phát biểu vấn đề ..............................................................................................12
1.1 Thực thể có tên ............................................................................................................12
1.2 Bộ máy tìm kiếm.........................................................................................................13
1.3 Kết hợp giải thuật PageRank và NE .........................................................................15
Chương 2 Tổng thuật về các cơng trình liên quan đến ñề tài ..................................16
2.1 Giải thuật HITS ...........................................................................................................16
2.2 Giải thuật PageRank ...................................................................................................17
2.3 Giải thuật Topic-Sensitive PageRank ......................................................................18
2.4 Truy hồi thông tin theo thực thể có tên ....................................................................18
Chương 3 Cơ sở lý thuyết .................................................................................................21
3.1 Hệ thống chú thích thực thể có tên của VN-KIM ...................................................21
3.1.1 Tổng quan .............................................................................................................21
3.1.2 VN-KIM Ontology (VN-KIMO) .......................................................................23
3.1.3 Cơ sở tri thức của VN-KIM ..............................................................................26
3.1.4 Sự rút trích thơng tin của VN-KIM ...................................................................26
3.1.5 Ứng dụng chú thích các NE trên các trang web với plug-in cho trình duyệt
Internet Explorer............................................................................................................28

3.2 Chi tiết giải thuật PageRank ......................................................................................29
3.2.1 Tổng quan .............................................................................................................29
3.2.2 Giải thuật PageRank ............................................................................................30
3.2.2.1 Một minh họa ñơn giản cho giải thuật PageRank ................................ 31
3.2.2.2 Giải thuật PageRank tổng quát ............................................................. 32
3.2.2.3 Mã giả giải thuật PageRank.................................................................. 36
3.3 Mơ hình khơng gian vector và độ tương tự Sim .....................................................37


8

3.3.1 Mơ hình khơng gian vector (VSM) cho truy hồi thơng tin theo từ khóa ......37
3.3.2 ðộ tương tự giữa tài liệu và truy vấn Sim ........................................................37
3.3.3 Mơ hình áp dụng cho NE....................................................................................38
Chương 4 Các giải thuật sắp hạng thông tin truy hồi trên môi trường web dựa
trên thực thể có tên .............................................................................................................39
4.1 Giải thuật NE PageRank ............................................................................................39
4.2 Kết hợp giá trị NE PageRank và ñộ tương tự giữa truy vấn và tài liệu Sim .......44
4.2.1 Giải thuật sắp hạng theo Sim có hỗ trợ của NE PageRank ............................44
4.2.2 Giải thuật sắp hạng theo NE PageRank có hỗ trợ của Sim ............................45
Chương 5 Hiện thực và các kết quả thực nghiệm.......................................................47
5.1 Hiện thực ......................................................................................................................47
5.2 Thời gian tính tốn NE PageRank và kích thước dữ liệu lưu trữ .........................50
5.3 Các kết quả thực nghiệm............................................................................................52
5.3.1 Khác biệt giữa sắp hạng theo NE PageRank và theo Sim ..............................52
5.3.2 Chất lượng sắp hạng theo Sim có hỗ trợ của NE PageRank tốt hơn so với
chỉ dựa trên Sim.............................................................................................................58
5.3.3 Sắp hạng theo NE PageRank có hỗ trợ của Sim tốt hơn chỉ dựa trên NE
PageRank ........................................................................................................................61
5.3.4 Ưu điểm về độ chính xác nhờ sắp hạng dựa trên thực thể có tên ..................66

5.3.5 So sánh giữa sắp hạng theo Sim có hỗ trợ của NE PageRank với Google
Desktop ...........................................................................................................................70
5.3.6 So sánh giữa sắp hạng theo NE PageRank có hỗ trợ của Sim với Google
Desktop ...........................................................................................................................74
5.3.7 So sánh truy vấn theo class và sắp hạng theo NE PageRank có hỗ trợ của
Sim với Google Desktop ..............................................................................................77
5.3.8 So sánh truy vấn theo class và sắp hạng theo Sim có hỗ trợ của NE
PageRank với Google Desktop....................................................................................80
Chương 6 Kết luận và hướng mở rộng .........................................................................83
6.1 Các đóng góp mới của cơng trình .............................................................................83
6.2 Kiến nghị những nghiên cứu tiếp theo .....................................................................83
Tài liệu tham khảo ..............................................................................................................85


Danh mục các hình
Hình 2-1 Sơ đồ mơ hình truy hồi thơng tin dựa trên thực thể có tên .......................20
Hình 3-1 Ontology và cơ sở tri thức.........................................................................22
Hình 3-2 Kiến trúc của VN-KIM .............................................................................23
Hình 3-3 Ontology của VN-KIM [26] .....................................................................25
Hình 3-4 Thành phần rút trích thơng tin của VN-KIM [10] ....................................27
Hình 3-5 Plug-in cho Internet Explorer....................................................................29
Hình 3-6 Các liên kết giữa các site được dùng cho sự tính tốn của PageRank [24]
...........................................................................................................................30
Hình 3-7 Vùng sink ..................................................................................................33
Hình 4-1 Tính giá trị PageRank cho thành phần thứ nhất của các vector PRN ........40
Hình 4-2 Mơ hình đề nghị ........................................................................................43
Hình 4-3 Sắp hạng trong nội bộ khoảng Sim bị thay ñổi dựa trên NE PageRank ...45
Hình 4-4 Sắp hạng trong nội bộ khoảng NE PageRank bị thay đổi dựa trên Sim ...46
Hình 5-1 Kiến trúc hệ thống truy hồi thơng tin hiện thời.........................................47
Hình 5-2 Kiến trúc hệ thống truy hồi thơng tin........................................................49

Hình 5-3 Truy vấn về Nha Trang và sắp hạng theo NE PageRank..........................54
Hình 5-4 Truy vấn về Nha Trang và sắp hạng theo Sim (trang 1)...........................55
Hình 5-5 Truy vấn về Nha Trang và sắp hạng theo Sim (trang 2)...........................56
Hình 5-6 Kết quả sắp hạng bởi Google Desktop khi truy vấn từ khóa "Nha Trang"
...........................................................................................................................57
Hình 5-7 Truy vấn về Nha Trang và sắp hạng theo Sim với hỗ trợ của NE
PageRank (trang 1) ............................................................................................59
Hình 5-8 Truy vấn về Nha Trang và sắp hạng theo Sim với hỗ trợ của NE
PageRank (trang 2). ...........................................................................................60
Hình 5-9 Truy vấn về Bình Nhưỡng và sắp hạng theo NE PageRank (trang 1) ......62
Hình 5-10 Truy vấn về Bình Nhưỡng và sắp hạng theo NE PageRank (trang 2) ....63


10

Hình 5-11 Truy vấn về Bình Nhưỡng và sắp hạng theo NE PageRank có hỗ trợ của
Sim (trang 1) ......................................................................................................64
Hình 5-12 Truy vấn về Bình Nhưỡng và sắp hạng theo NE PageRank có hỗ trợ của
Sim (trang 2) ......................................................................................................65
Hình 5-13 Truy vấn về con người tên Thế Anh và sắp hạng theo NE PageRank có
hỗ trợ của Sim....................................................................................................67
Hình 5-14 Truy vấn về con người tên Thế Anh và sắp hạng theo Sim có hỗ trợ của
NE PageRank.....................................................................................................68
Hình 5-15 Truy vấn về Thế Anh và sắp hạng bởi Google Desktop.........................69
Hình 5-16 Truy vấn về sân vận ñộng Vinh và sắp hạng theo Sim có hỗ trợ của NE
PageRank (trang 1) ............................................................................................71
Hình 5-17 Truy vấn về sân vận ñộng Vinh và sắp hạng theo Sim có hỗ trợ của NE
PageRank (trang 2) ............................................................................................72
Hình 5-18 Truy vấn "sân vận động" Vinh và sắp hạng bởi Google Desktop ..........73
Hình 5-19 Các đường dẫn có liên quan đến Mai Phương Th ..............................74

Hình 5-20 Truy vấn về Mai Phương Thuý và sắp hạng bởi NE PageRank có hỗ trợ
của Sim ..............................................................................................................75
Hình 5-21 Truy vấn về Mai Phương Thuý và sắp hạng bởi Google Desktop .........76
Hình 5-22 Truy vấn class “Câu lạc bộ thể thao” và sắp hạng theo NE có hỗ trợ của
Sim .....................................................................................................................78
Hình 5-23 Truy vấn “câu lạc bộ thể thao” và sắp hạng theo Google Desktop ........79
Hình 5-24 Truy vấn về “Tổ chức thể thao” và sắp hạng theo Sim có hỗ trợ của NE
PageRank ...........................................................................................................81
Hình 5-25 Truy vấn về “tổ chức thể thao” và sắp hạng bởi Google Desktop..........82


11

Danh mục các bảng
Bảng 5-1 Thời gian tính tốn và khối lượng lưu trữ NE PageRank .........................51


12

Chương 1
Phát biểu vấn đề

Vấn đề xếp hạng các thơng tin truy hồi sao cho hợp lý, nêu bật các kết quả
tìm kiếm quan trọng và có ý nghĩa là một vấn ñề quan trọng trên các hệ thống truy
hồi thơng tin. ðối với các thơng tin được truy hồi trên môi trường Web, giải thuật
PageRank và các cải tiến của nó đã được ứng dụng hiệu quả khi tìm kiếm thơng tin
dựa trên từ khóa, đặc biệt trên máy tìm kiếm Google. Trong đề tài này, dựa trên các
kết quả nghiên cứu đã có dựa trên từ khóa, sinh viên sẽ nghiên cứu và phát triển một
giải thuật xếp hạng các thông tin truy hồi trên môi trường web dựa trên thực thể có
tên (Named Entity).


1.1 Thực thể có tên
Khái niệm “Named Entity” (NE) hiện nay ñược dùng rộng rãi trong rút trích
thơng tin (Information Extraction hay IE), hỏi ñáp (Question Answering hay QA)
và các ứng dụng xử lý ngôn ngữ tự nhiên khác (Natural Language Processing hay
NLP), ra ñời từ Message Understanding Conferences (MUC-6) 1995 [31]. Trong xử
lý ngôn ngữ tự nhiên và IE truyền thống, thực thể có tên gồm: con người, tổ chức,
địa danh, và những ñối tượng khác ñược tham khảo bằng tên. Một cách rộng hơn
thực thể có tên cũng có thể bao gồm các giá trị vô hướng như (số lượng, ngày, số
lượng tiền), địa chỉ…(ban đầu thực thể có tên được định nghĩa với bảy loại: person,
organization, location, date, time, money và percent [31]). Cũng qua hệ thống phân
loại, ta có thể thấy NE đóng vai trị quan trọng trong việc hình thành nên ngữ nghĩa
của tài liệu.
Sự phát triển các hệ thống hỏi ñáp ñã tạo sự thúc ñẩy mạnh mẽ ñối với việc
mở rộng hệ thống phân loại cho NE, chẳng hạn trong ngữ cảnh tổng quát thì hệ


13

thống phân loại gồm bảy loại ở trên có thể là đủ, tuy nhiên khi ngữ cảnh là “dịch
bệnh”, “phóng tên lửa” chúng ta cần biết “tên của dịch bệnh”, “tên của tên lửa”. Tác
vụ IE càng rộng thì hệ thống NE càng cần ñược mở rộng. Việc mở rộng trên cũng
cho thấy, khơng có một định nghĩa hay hệ thống phân loại tuyệt ñối cho NE, mà tùy
vào ứng dụng.
Các tài liệu đã được chú thích NE có thể được tìm kiếm chính xác hơn văn
bản thơ, chưa được chú thích. Chẳng hạn, sự chú thích cho phép chúng ta tìm tất cả
tài liệu đề cập đến thành phố “Sài Gịn”, bỏ qua các tài liệu khơng liên quan nhưng
cùng có chữ “Sài Gịn” như sơng “Sài Gịn”, nhà máy bia “Sài Gòn”…
Trong một báo cáo của Microsoft [32] dựa trên thống kê về cơng cụ tìm kiếm
SIS, là cơng cụ giúp người dùng tìm kiếm thơng tin đã thấy trước đó, cho thấy, các

loại truy vấn phổ biến nhất đó là các truy vấn về Người/ðịa điểm/Vật
(People/Places/Things), Máy tính/Internet (Computers/Internet) và Sức khoẻ /Khoa
học (Health/Science). Trong danh mục People/Places, thì các truy vấn về tên
(names) đặc biệt phổ biến. Nổi bật với 25% của các truy vấn có bao gồm tên người.
Ngược lại, các truy vấn về thông tin chung ít phổ biến hơn. Thống kê trên phần nào
khẳng định thêm tầm quan trọng của thực thể có tên trong các truy vấn.
Một NE được biểu diễn thơng qua bộ ba [tên, kiểu, id]. Trong đó id là danh
hiệu dùng ñể phân biệt giữa các NE với nhau. Cùng một tên có thể thuộc về vài kiểu
khác nhau, do đó cũng có thể có các id khác nhau. Một kiểu có thể có nhiều tên
khác nhau. Việc rút trích thực thể có tên đã đạt độ hiệu quả chung về chú thích ngữ
nghĩa tự động vào khoảng 80% so với con người chú thích bằng tay [10].

1.2 Bộ máy tìm kiếm
Nhờ khả năng chứa đựng dữ liệu ngày càng lớn của phần cứng, sự hỗ trợ của
các hệ cơ sở dữ liệu quan hệ, việc xây dựng web site ngày càng dễ dàng. Dữ liệu từ
báo chí điện tử, công ty, tổ chức, mạng xã hội, cá nhân …là nguồn cung cấp thông
tin vô cùng lớn, nhưng cũng đặt ra những thách thức khơng nhỏ để có thể khai thác


14

hiệu quả nguồn thơng tin giá trị này. ðó là, làm sao để truy xuất được thơng tin
quan tâm từ một nguồn dữ liệu vô cùng lớn và gần như khơng hề được tổ chức như
vậy, hơn nữa q trình truy xuất địi hỏi phải nhanh và chính xác. Từ những u cầu
bức thiết đó đã dẫn đến sự ra ñời của mảng truy hồi thông tin cho web mà nổi bật
với các tên tuổi như Google, Yahoo, Live Search (MSN Search).
Yahoo Search khởi đầu chỉ là một cơng ty thực hiện xây dựng hệ thống phân
loại các trang web (directory), hệ thống được xây dựng thủ cơng do con người thực
hiện. Tuy nhiên những năm gần ñây sự phát triển nhanh chóng của các trang web
mới đã buộc Yahoo phải xây dựng cơng cụ tìm kiếm tự động. Ban đầu Yahoo sử

dụng cơng nghệ tìm kiếm của Inktomi, rồi cơng nghệ của Google, sau đó quay lại
với Inktomi.
MSN Search (Live Search) là dịch vụ tìm kiếm của cơng ty Microsoft. Mặc
dù chậm chân trong thị trường tìm kiếm, chỉ mới ñược tập trung phát triển từ năm
2005, nhưng MSN Search cũng đã chiếm được thị phần tìm kiếm khá lớn. Kết quả
sắp hạng của MSN Search một phần lớn dựa vào cơng nghệ của Inktomi.
Google là cơng cụ tìm kiếm ñược nhiều người sử dụng nhất hiện nay. Năm
2000 Google thay thế Inktomi cung cấp dịch vụ tìm kiếm cho Yahoo, tiếp đó là
AOL, Netscape, Freeserve…giúp Google khẳng định là một trong những cơng cụ
tìm kiếm đáng tin cậy và chính xác nhất. Người dùng thực hiện tìm kiếm thơng tin
mong muốn thơng qua từ khóa và các phép tốn. Tại thời điểm tháng 8/2007, thị
phần tìm kiếm của Google là 53.6%, của Yahoo là 19.9% và của MSN Search là
12.9% [24]. Giải thuật xếp hạng ñược Google sử dụng, và ñược khẳng ñịnh trên
web site của hãng rằng cho ñến tận bây giờ vẫn là trái tim của Google đó là giải
thuật PageRank.
Chất lượng xếp hạng các kết quả truy vấn chính là ngun nhân trọng yếu
dẫn đến thành cơng của các cơng cụ tìm kiếm này, mà cơ sở chính là một giải thuật
xếp hạng tốt. Giải thuật xếp hạng tốt giúp cho người dùng nhanh chóng xác ñịnh


15

được các trang web có nội dung quan trọng, phù hợp với mong ñợi khi thực hiện
truy vấn.

1.3 Kết hợp giải thuật PageRank và NE
Mặc dù giải thuật PageRank ñã ñược Google sử dụng rất thành công, nhưng
bản chất của Google vẫn là dựa trên từ khóa (keyword) để tìm kiếm và sắp hạng. Do
đó, nếu có thể kết hợp ñược giải thuật PageRank với những ưu ñiểm của các NE đã
được nhận diện, nhiều khả năng sẽ có được các kết quả tìm kiếm và xếp hạng tốt

hơn.
Thấy được tầm quan trọng của một giải thuật sắp hạng, dựa trên các kết quả
đã đạt được trong việc chú thích ngữ nghĩa cho các tài liệu web, giải thuật tính ñộ
quan trọng tương quan PageRank cùng với việc lập chỉ mục, ñề tài hướng ñến việc
xây dựng một giải thuật sắp hạng có chất lượng cao cho thơng tin truy hồi trên mơi
trường web dựa trên các thực thể có tên.


16

Chương 2
Tổng thuật về các cơng trình liên quan đến đề
tài

Các kỹ thuật truy hồi thơng tin truyền thống có thể cho một kết quả khơng
tốt, khơng ổn định về chất lượng trên môi trường web. Tuy nhiên, những năm gần
đây, kết quả tìm kiếm từ mơi trường web đã ñược cải thiện rất nhiều bằng cách sử
dụng thông tin ẩn chứa trong cấu trúc liên kết giữa các trang, với hai giải thuật nổi
tiếng là giải thuật HITS (Hypertext Induced Topic Search) và PageRank. Giải thuật
PageRank ñã ñược dùng rất thành cơng với máy tìm kiếm Google.

2.1 Giải thuật HITS
Giải thuật HITS [16] ñược phát triển vào năm 1997 bởi Jon Kleinberg. Với
một truy vấn, HITS dùng một công cụ tìm kiếm truyền thống để có tập các trang
phù hợp, mở rộng tập này thông qua các liên kết vào (inlinks) và ra (outlinks), sau
đó thực hiện xác định hai loại trang, hub (trang trỏ đến nhiều trang có chất lượng
cao) và authority (trang có chất lượng cao, có nhiều liên kết trỏ tới), đây là các định
nghĩa có tính đệ qui.
Một cách tương ứng HITS dùng hai điểm số cho mỗi trang, ñiểm authority
và ñiểm hub. Các ñiểm số được tính một cách đệ qui và thơng qua các lần lặp cho

ñến khi hội tụ. ðiểm số authority ñược tính bằng tổng ñiểm hub của các trang trỏ
ñến trang này, và ñiểm số hub của trang bằng tổng ñiểm authority của các trang mà
trang này trỏ tới.


17

Bởi vì q trình tính tốn này được thực hiện tại thời điểm truy vấn, nên
khơng khả thi cho các máy tìm kiếm ngày nay, là những hệ thống phải ñáp ứng
lượng truy vấn rất lớn mỗi ngày và thời gian ñáp ứng nhanh. Việc sử dụng các liên
kết ra (outlinks) khiến giải thuật dễ bị làm cho sai lệch (spam) bởi những nhà quản
trị web, bằng cách chủ ñộng thêm liên kết trên trang web của mình.

2.2 Giải thuật PageRank
PageRank [30] ñược phát triển tại ñại học Stanford bởi Larry Page và sau đó
bởi Sergey Brin như một phần của dự án nghiên cứu về một loại máy tìm kiếm mới.
Dự án ñã bắt ñầu từ 1995 và cho kết quả là một nguyên mẫu chức năng, gọi là
Google vào năm 1998. Khơng lâu sau đó, Page và Brin thành lập công ty Google.
Trọng số PageRank của mỗi trang web được xác định thơng qua phiếu bầu
dưới hình thức một liên kết từ một trang khác trên web. Ý tưởng là những phiếu bầu
(liên kết) từ những trang web quan trọng sẽ có trọng lớn hơn từ những trang ít quan
trọng, và khi một trang web thực hiện bầu (có liên kết đến) nhiều trang web khác,
thì trọng số của mỗi phiếu bầu sẽ bị chia nhỏ. ðây là một định nghĩa đệ qui, nên
việc tính tốn cần q trình lặp.
PageRank thực hiện việc tính tốn tại thời điểm lập chỉ mục, ñây là ưu ñiểm
nổi bật của PageRank, giúp hệ thống có thể đáp ứng nhanh với số lượng truy vấn
lớn, ñồng thời chỉ sử dụng liên kết vào (inlinks) để phân tích nên hạn chế được
nhược điểm của HITS, bởi việc thêm liên kết từ các trang quan trọng khó hơn rất
nhiều.
Nhưng nhược điểm chung của hai giải thuật trên (HITS và PageRank) đó là

khơng quan tâm ñến nội dung, chủ ñề của truy vấn cũng như các trang web, bởi vì
mỗi trang được gán một trọng số duy nhất chỉ dựa vào cấu trúc của liên kết (không
hề dựa trên nội dung). Một trang nếu nằm trong kết quả trả về của các truy vấn khác
nhau sẽ ln có trọng số giống nhau.


18

2.3 Giải thuật Topic-Sensitive PageRank
ðể khắc phục nhược điểm khơng quan tâm ñến nội dung, chủ ñề của truy vấn
cũng như của các trang web ở các giải thuật Hit và PageRank, tác giả Haveliwala ñã
ñề xuất giải thuật PageRank nhạy cảm với chủ ñề TSPR (Topic-Sensitive
PageRank) [33]. Dựa vào hệ thống phân loại gồm 16 chủ ñề (là mức phân loại trên
cùng của Open Directory Project), TSPR thực hiện tính 16 giá trị PageRank khác
nhau cho mỗi trang web (mỗi giá trị tương ứng với một chủ ñề). Khi tính giá trị
PageRank theo từng chủ đề, giải thuật PageRank gốc ñược sử dụng và chỉ xem xét
các liên kết từ các trang thuộc chủ ñề ñang xem xét. Tại thời ñiểm truy vấn, 16 giá
trị PageRank này ñược kết hợp dựa trên chủ ñề (mức ñộ thuộc về từng chủ đề) của
truy vấn để hình thành giá trị PageRank tổng hợp cho mỗi trang.
Nhược ñiểm của phương pháp này là phụ thuộc vào hệ thống phân loại chủ
ñề, hệ thống phân loại càng chi tiết tác dụng của phương pháp càng ñược thể hiện.
Tác giả cũng ñề xuất hướng nghiên cứu mở rộng hệ thống phân loại chủ ñề bằng
cách sử dụng tần thứ hai hoặc thứ ba của Open Directory Project thay cho việc
dùng tần thứ nhất (với 16 chủ ñề), tuy nhiên tác giả cũng nhận ñịnh việc gia tăng số
lượng chủ ñề sẽ gặp phải trở ngại về chi phí tính tốn.

2.4 Truy hồi thơng tin theo thực thể có tên
Cơng trình được thực hiện bởi tác giả Ngô Minh Vương, trong luận văn thạc
sĩ của mình, hồn thành vào tháng 7 năm 2007, tại đại học Bách Khoa, TP.HCM.
Luận văn hướng ñến việc xây dựng các mơ hình truy hồi thơng tin dựa trên thực thể

có tên.
Trong cơng trình của mình [23], tác giả đã đề xuất mơ hình biểu diễn tài liệu
và đánh chỉ mục trên bốn không gian thuật ngữ (Tên, Kiểu, Tên-Kiểu, Danh hiệu)
hay (Name, Class, Name-Class, ID) (ký hiệu tương ứng (N, C, N-C, ID)) cho các


19

thực thể có tên, đồng thời mở rộng mơ hình VSM (Vector Space Model) và SSM
(Semantic Similarity Model) truyền thống thành NE-VSM (Named Entity-VSM) và
NE-SSM áp dụng cho việc truy hồi thơng tin dựa trên thực thể có tên (xác ñịnh ñộ
tương tự giữa truy vấn và tài liệu Sim).
Hình 2-1 thể hiện mơ hình truy hồi thơng tin theo thực thể có tên. Q trình
nhận diện các thực thể có tên (q trình chú thích) được đề cập cụ thể ở mục 3.1.
Các vector biểu diễn cho tài liệu và truy vấn ñược ñề cập ở mục 3.3. Việc lập chỉ
mục cho các vector và truy hồi danh sách các tài liệu thỏa mãn truy vấn ñược thực
hiện nhờ hỗ trợ của chương trình Lucene.
Trong mơ hình trên, tác giả cũng ñề nghị sự mở rộng vector biểu diễn tài liệu
và truy vấn theo quan hệ alias và kiểu cha giúp tăng lượng thông tin biểu diễn
nhưng không làm thay ñổi nghĩa gốc của tài liệu hoặc truy vấn, cũng như phân bổ
lại trọng số của vector biểu diễn truy vấn ñể nhấn mạnh vào vùng quan tâm ñặc biệt
của truy vấn dựa vào ñộ tương ñồng ngữ nghĩa giữa các NE trong truy vấn. Mơ hình
NE-SSM có sự bổ sung việc sử dụng ngữ nghĩa ñộ tương tự giữa hai thuật ngữ so
với mơ hình NE-VSM.
Dữ liệu dùng ñể thực nghiệm là 2.402 trang web ñã ñược chú thích, gồm
1.505 trang của Reuters, 805 trang của CNN, 92 trang của KIM. Các thống kê, so
sánh của tác giả cho thấy mơ hình có những ưu điểm về độ triệu hồi và độ chính xác
so với các mơ hình dựa trên từ khóa truyền thống.
Nhược điểm của cơng trình là chưa sử dụng được thơng tin ẩn chứa trong cấu
trúc liên kết giữa các trang trong việc xếp hạng các trang kết quả.



20

Hình 2-1 Sơ đồ mơ hình truy hồi thơng tin dựa trên thực thể có tên


21

Chương 3
Cơ sở lý thuyết

3.1 Hệ thống chú thích thực thể có tên của VN-KIM
3.1.1 Tổng quan
VN-KIM là hệ thống chú thích ngữ nghĩa cho các thực thể có tên tiếng Việt,
ñược phát triển từ ñề tài trọng ñiểm của quốc gia về công nghệ thông tin và truyền
thông cho web có ngữ nghĩa, do PGS.TS. Cao Hồng Trụ chủ nhiệm. VN-KIM
cung cấp một cơ sở hạ tầng và dịch vụ cho việc chú thích ngữ nghĩa tự động, lập chỉ
mục, truy hồi các nội dung không cấu trúc hoặc bán cấu trúc.
VN-KIM phân tích văn bản và nhận diện các thực thể (người, tổ chức, nơi
chốn, ngày), và cố gắng liên kết các thực thể nhận diện ñược với phân loại (class)
chi tiết nhất trong ontology, và liên kết với một thực thể đã biết (có các mơ tả của
mình) trong cơ sở tri thức được xác định thơng qua URI duy nhất. Quá trình này
(cũng như kết quả) ñược gọi là chú thích ngữ nghĩa (semantic annotation) hay chú
thích thực thể có tên (NE annotation).


22

Hình 3-1 Ontology và cơ sở tri thức


Kiến trúc của VN-KIM được thể hiện ở Hình 3-2, bao gồm VN-KIM
Ontology (VN-KIMO), cơ sở tri thức, KIM Server (với các API cho việc truy xuất
từ xa), và các chương trình đầu cuối như plug-in cho trình duyệt Internet Explorer,
chương trình duyệt cơ sở tri thức.


23

Ứng dụng

Trình Duyệt

Các Ứng Dụng

Plugin vào

Xây Dựng Cơ

Web

Khai Thác VN-KIM

Trình Duyệt

Sở Tri Thức

Ứng Dụng

Ứng Dụng


Ứng Dụng

Truy Vấn

Truy Vấn

Thu Thập

Cơ Sở Tri

Tài Liệu

Tài Liệu

Ứng Dụng
Sinh Chú
Thích Cho

Thức

Tài Liệu

Khối Quản Lý
và Truy Vấn Cơ Sở Tri
Thức

Khối ðánh Chỉ Mục, Lưu Trữ,

Khối Chú Thích Ngữ Nghĩa


Truy Vấn Tài Liệu

Cho Tài Liệu

Các tài liệu Web
đã chú thích

Seasame
A

B

Thành phần A sử dụng thành phần B

VN-KIM Ontology
và Cơ Sở Tri Thức

Hình 3-2 Kiến trúc của VN-KIM

3.1.2 VN-KIM Ontology (VN-KIMO)
Ontology là một tập các khái niệm và quan hệ giữa các khái niệm ñược ñịnh
nghĩa cho một lĩnh vực nào đó nhằm vào việc biểu diễn và trao đổi thơng tin.
Ontology của VN-KIM được thiết kế sao cho chứa ñựng ñược các thực thể ở cả
Việt Nam và trên thế giới [10].


24



25

Hình 3-3 Ontology của VN-KIM [26]
Hình 3-3 thể hiện cấu trúc phân cấp Ontology của VN-KIM. Ontology của
VN-KIM ñược tổ chức với ba lớp trên cùng là Thực_thể, Nguồn_thông_tin,
Ngữ_liệu. Lớp Thực_thể lại ñược chia làm ba lớp nhỏ hơn là Trừu_tượng, Biến_cố,
và ðối_tượng. Lớp Object chứa các thực thể như ñịa danh, nhân vật ñang tồn tại.
Lớp Biến_cố chứa các sự kiện và trạng thái. Lớp Trừu_tượng chứa những thực thể
không thuộc lớp Biến_cố cũng như ðối_tượng. Và các lớp trên lại tiếp tục ñược
chia nhỏ cho ñến khi ñạt yêu cầu của hệ thống. Với cách tổ chức như trên, ontology