HÀ NỘI - 2011 Cán bộ hướng dẫn: ThS.Nguyễn Cm Tú

HÀ NỘI - 2011

i

Lời cảm ơn Trước tiên, tôi xin gửi lời cảm ơn và lòng biết ơn sâu sắc nhất tới Phó Giáo
sư Tiến sĩ Hà Quang Thụy và Thạc sĩ Nguyễn CNm Tú, những người đã tận tình chỉ
bảo và hướng dẫn tôi trong suốt quá trình thực hiện khoá luận tốt nghiệp.
Tôi chân thành cảm ơn các thầy, cô đã tạo những điều kiện thuận lợi cho tôi
học tập và nghiên cứu tại trường Đại học Công nghệ.
Tôi cũng xin gửi lời cảm ơn tới các anh chị, các bạn và các em sinh viên
trong phòng nghiên cứu SIS-KTLab đã giúp tôi rất nhiều trong việc hỗ trợ kiến thức
chuyên môn để hoàn thành tốt khoá luận. Khóa luận này nhận được sự hỗ trợ từ đề
tài QG.10.38.
Cuối cùng, tôi muốn gửi lời cảm vô hạn tới gia đình và bạn bè, những người

cụm ở mức 0.86 và xếp hạng thực thể ở mức 0.8. Kết quả này cho thấy mô hình tìm
kiếm người theo tên tiếng Việt trên Web dược đề xuất và triển khai là có tính khả
quan.

iii

Lời cam đoan

Tôi cam đoan giải pháp tìm kiếm người trên Web dựa trên thuật toán phân
cụm phân cấp và xếp hạng cặp thứ tự và thực nghiệm được trình bày trong khóa
luận là do tôi thực hiện dưới sự hướng dẫn của PGS.TS Hà Quang Thụy và ThS.
Nguyễn CNm Tú.
Trong toàn bộ nội dung của khóa luận, những điều được trình bày hoặc là của
cá nhân hoặc là được tổng hợp từ nhiều nguồn tài liệu. Tất cả các tài liệu tham khảo
đều có xuất xứ rõ ràng và được trích dẫn hợp pháp.

2.1.2.1. Hướng tiếp cận dựa trên phân cụm bán giám sát 14
2.1.2.2. Các tiếp cận dựa trên kỹ thuật phân cụm hai trạng thái 17
2.1.2.3. Các hướng tiếp cận khác 19
2.4. Một số hướng tiếp cận giải quyết vấn đề xếp hạng thực thể 20
2.4.1. Phát biểu bài toán xếp hạng thực thể 20
2.4.2. Một số hướng tiếp cận giải quyết bài toán xếp hạng thực thể 21
2.4.2.1. Hướng tiếp cận dựa trên điểm số tương đồng và liên kết 21
2.4.2.2. Hướng tiếp cận dựa trên Mô hình Impression 23
Chương 3. Mô hình giải quyết bài toán tìm kiếm người trên Web 28
3.1. Cơ sở lý thuyết 28
3.1.1. Thuật toán phân cụm HAC 28
3.1.2. Độ tương đồng cosin 31

v

3.1.3. Phương pháp PageRank 31
3.1.4. Phương pháp xếp hạng cặp thứ tự (Pairwise) 32
3.2. Mô hình giải quyết bài toán tìm kiếm người trên Web 32
3.3. Áp dụng bài toán tìm kiếm người theo tên trên Web vào hệ thống tìm kiếm thực
thể người 38
Chương 4. Thực Nghiệm và đánh giá 39
4.1. Mô tả thực nghiệm 39
4.2. Môi trường và công cụ sử dụng thực nghiệm 39
4.3. Xây dựng tập dữ liệu thực nghiệm 40
4.5. Thực nghiệm và Kết quả 41
Kết luận 48


vii
Danh Sách hình vẽ

Hình 1. Kết quả trả về từ google với truy vấn ” Sony VaiO FZ150F 5
Hình 2. Mô hình tìm kiếm truyền thống và tìm kiếm thực thể 5
Hình 3. Kiến trúc cơ bản hệ thống tìm kiếm thực thể 6
Hình 4. Hệ thống tìm kiếm thực thể dựa trên kỹ thuật trích rút thông tin 7
Hình 5. Hệ thống tìm kiếm người iSearch. 8
Hình 6. Mô hình hệ thống xếp hạng thực thể 21
Hình 7. Mô hình Impression 25
Hình 8. Sơ đồ thuật toán phân cụm HAC 28
Hình 9. Phân cụm với độ đo single-link 30
Hình 10. Phân cụm với độ đo complete-link 30
Hình 11. Mô hình giải quyết bài toán 33
Hình 12. Mô hình đề xuất xây dựng hệ thống tìm kiếm 338
Hình 13. Ví dụ các thuộc tính sau khi trích chọn 42
Sự ra đời của máy tìm kiếm đã giúp cho người dùng khai thác thông tin một
cách thuận tiện hơn. Tuy nhiên, các kết quả trả về từ máy tìm kiếm vẫn còn nhiều
hạn chế, đặc biệt là khi người dùng muốn tìm kiếm thông tin về một đối tượng cụ
thể thì các kết quả trả về chỉ là tập địa chỉ các trang Web chứ không phải là các
bản ghi về đối tượng cần tìm. Một trong những loại tìm kiếm đối tượng phổ biến
nhất là tìm kiếm người nhưng thực thể người lại là một trong những loại thực thể
có độ nhập nhằng cao nhất, các kết quả trả về từ máy tìm kiếm sẽ bao gồm tập địa
chỉ các trang web liên quan tới nhiều người chia sẻ cùng một tên. Hơn thế nữa, các
thực thể người tìm kiếm được không chỉ được lấy ra từ một trang độc lập mà có
thể được tổng hợp từ nhiều trang khác nhau. Vì vậy, cần thiết một hệ thống có khả
năng gom cụm kết quả sao cho những trang Web thuộc cùng một cụm sẽ cùng trỏ
tới một người đồng thời có khả năng xếp hạng các thực thể người được trích rút từ
các cụm.
Vấn đề tìm kiếm người trên Web ngày càng nhận được sự quan tâm nghiên
cứu trên thế giới. Đặc biệt là các hội nghị khoa học về tìm kiếm người trên Web
[16].
Khóa luận tốt nghiệp với đề tài Giải pháp tìm kiếm người theo tên trên
Web dựa trên phân cụm phân cấp và xếp hạng cặp thứ tự và thử nghiệm vào hệ
thống tìm kiếm thực thể người tiếng Việt nhằm khảo sát, phân tích một số phương
pháp phân cụm và xếp hạng thực thể đang được quan tâm hiện nay. Từ đó, đưa ra
mô hình phân cụm và xếp hạng thực thể người trong hệ thống tìm kiếm thực thể
người tiếng Việt.
Khóa luận gồm các nội dung chính cơ bản sau:
Chương 1: Khái quát bài toán tìm kiếm người trên Web trình bày khái
quát nhu cầu tìm kiếm thông tin trên Web, hệ thống tìm kiếm thực thể người.
Đồng thời, khóa luận cũng trình bày khái quát và một số nội dung liên quan chính
tới bài toán tìm kiếm người trên Web, bao gồm phương pháp đánh giá giải pháp
tìm kiếm người trên Web.

2
3

Chương 1. Khái quát bài toán tìm kiếm người trên Web
Nhu cầu tìm kiếm thông tin là một nhu cầu cần thiết và tất yếu trong cuộc
sống con người. Internet là một kho thông tin khổng lồ được coi là không giới hạn.
Tuy nhiên, việc khai thác thông tin trên Internet gặp phải nhiều khó khăn và thách
thức vì tính đa dạng và phi cấu trúc. Với các máy tìm kiếm thông dụng hiện nay như
Google, Yahoo, MSN…., truy vấn người dùng đưa vào là tập các từ khóa và kết quả
trả về chỉ là các địa chỉ tới các trang web trong khi người dùng mong muốn nhận
được các bản ghi về đối tượng cần tìm. Một trong những đối tượng được tìm kiếm
nhiều nhất là thực thể người. Chương này sẽ trình bày một số vấn đề và nội dung
liên quan tới bài tóan tìm kiếm người trên Web.
1.1. Hệ thống tìm kiếm thực thể
1.1.1. Dữ liệu Web và vấn đề tìm kiếm thông tin trên Web
Hiện nay, người dùng có thể truy cập nguồn tài nguyên Web mọi lúc, mọi nơi
và tìm kiếm, tổng hợp các thông tin cần thiết. Cùng với sự thay đổi và phát triển
hàng ngày hàng giờ về nội dung cũng như số lượng của các trang Web trên Internet
thì vấn đề tìm kiếm thông tin đối người dùng ngày càng trở lên khó khăn. Dữ liệu
Web mang một vài đặc điểm sau[1]:
 Web dường như quá lớn để tổ chức thành một kho dữ liệu phục vụ khai
phá dữ liệu.

Độ phức tạp của trang Web lớn hơn rất nhiều so với những tài liệu văn
bản truyền thống khác.

 Web là một nguồn tài nguyên thông tin có độ thay đổi cao.
 Web phục vụ một cộng đồng người dùng rộng lớn và đa dạng.
 Chỉ một phần rất nhỏ của thông tin trên Web là thực sự hữu ích.

dung lượng ổ đĩa, tốc độ…. của dòng máy tính xác tay Sony VaiO FZ150F. Với
máy tìm kiếm thông thường như Google, người dùng nhập từ khóa “Sony VaiO
FZ150F”. Kết quả nhận được như sau: 5 Hình 1. Kết quả trả về từ google với truy vấn ” Sony VaiO FZ150F”.
Khác với máy tìm kiếm thông thường, kết quả trả về của máy tìm kiếm thực
thể là các thực thể của đối tượng cần tìm, mỗi thực thể được xác định không chỉ xét
trên một trang độc lập mà có thể được tổng hợp qua nhiều trang Web. Hệ thống tìm
kiếm thực thể sẽ cung cấp thông tin lọc ở mức cao hơn cho người dùng.
Sau đây là một hình ảnh minh họa hai mô hình tìm kiếm truyền thống và mô
hình tìm kiếm thực thể được đưa ra bởi nhóm tác giả Kevin Chen –Chuan ChangTao
Cheng và Kim Cuong Pham [17]

Hình 2. Mô hình tìm kiếm truyền thống và tìm kiếm thực thể[17]
Từ khóa

Kết quả
Th
ực

th
ể

Kết quả

6

tổng hợp trọng số cho từng bộ thực thể , kết hợp trọng số cục bộ và trọng
số xác định cho thực thể đó trên toàn tập tài liệu để đạt giá trị điểm cuối
cùng cho xếp hạng thực thể.
Dưới đây là kiến trúc một hệ thống tìm kiếm thực thể tiêu biểu dựa trên kỹ
thuật trích xuất thông tin[3].

Hình 4. Hệ thống tìm kiếm thực thể dựa trên kỹ thuật trích rút thông tin [3]
Mô hình hệ thống tìm kiếm thực thể dựa trên kỹ thuật trích xuất thông tin
gồm các phần chính sau[3]:

8

 Trích xuất thông tin về thực thể: thực hiện trích xuất các thông tin liên
quan đến thực thể này từ tất cả các trang Web chứa loại thực thể.
 Tổng hợp thực thể: Mỗi thực thể được trích chọn sẽ được ánh xạ tới một
đối tượng thế giới thực và lưu trữ vào trong kho dữ liệu Web. Việc tổng
hợp thực thể cần hợp nhất các thông tin liên quan tới cùng một thực thể
và phân biệt các thực thể khác nhau.
 Tìm kiếm thực thể: sau khi trích xuất các thông tin về thực thể và tổng
hợp thực thể, hệ thống cung cấp các thông tin cần thiết cho người dùng.
Ngoài ra, để đạt hiệu quả tốt hơn trong kết quả tìm kiếm, hệ thống cần
một mô hình xếp hạng hiệu quả.
Một số hệ thống tìm kiếm thực thể tiêu biểu như hệ thống Hệ thống Cazoodle
tại Việt Nam được sự hỗ trợ phát triển của nhóm nghiên cứu của Kevin Chen-Chuan
Chang

(). Ngoài ra, còn có các hệ thống như iSearch
(Spock.com) và Zoominfor (Zoominfo.com)
trước, cần phải phân biệt những người khác nhau có cùng tên và đưa ra danh sách
đã được xếp hạng các thực thể người cùng tên đó trên tập các trang Web.
Miền dữ liệu của bài toán là tập các trang Web .edu hoặc .edu.vn
1.2.3. Một số nội dung chính
Trong khóa luận này, bài toán tìm kiếm người trên Web gồm hai nội dung
chính
Nội dung chính thứ nhất: Vấn đề phân biệt nhập nhằng tên người.

10

Với truy vấn của người dùng là một tên người, máy tìm kiếm sẽ trả lại danh
sách các trang Web chứa tên người đó. Tuy nhiên, không phải tất cả các trang Web
nhận được cùng trỏ tới một người mà sẽ trỏ tới nhiều người khác nhau chia sẻ
cùng tên đó. Theo thống kê điều tra dân số của Mỹ và được báo cáo tại hội nghị
WebPS-3, 2010 , tên người có độ nhập nhằng cao[7]: với 90.000 tên người khác
nhau đã được chia sẻ cho hơn 100.000.000 người. Ví dụ, với truy vấn là “Nguyễn
Hữu Đức” thì trong hàng trăm kết quả trả về từ máy tìm kiếm Google, bên cạnh
PGS.TS. Nguyễn Hữu Đức-Giám đốc Đại Học Quốc gia còn có một Nguyễn Hữu
Đức, một cố Hiệu trưởng trường Đại Học Đà Lạt hoặc là một du khách hoặc một
trưởng phòng Giáo Dục và Đào Tạo tỉnh An Giang. Vì vậy, vấn đề đặt ra là gom
cụm những người có cùng tên. Mỗi cụm chứa thông tin về một người, các cụm
khác nhau sẽ trỏ tới những người khác nhau.
Nội dung chính thứ hai: Vấn đề xếp hạng kết quả tìm kiếm người cùng
tên.
Kết quả nhận được sau bước phân biệt nhập nhằng tên người là tập các cụm
trang Web chứa tên người cho trước. Mỗi cụm sẽ trỏ tới một người. Với kỹ thuật
trích rút thực thể, thay vì tập các trang Web chứa tên người, kết quả nhận được sẽ
là danh sách các thực thể người cùng tên từ các cụm. Không chỉ tìm được thực thể
người mà vấn đề trong các máy tìm kiếm là những thực thể phù hợp nhất được đưa
lên từ những kết quả đầu tiên trả về cho người dùng. Cũng như máy tìm kiếm

=
i
ji
i
LCprecision
n
C
purity ,max

Trong đó độ chính xác của cụm C
i
ứng với mỗi cụm L
j
được định nghĩa như
sauijiji
CLCLCprecison /),( ∩=

 Công thức độ nghịch đảo tinh khiết

( )
∑
=
i
ji
i
CLprecision
n

K vị trí đầu tiên của xếp hạng Match@K. Độ chính xác mức K được tính như sau:

K
KMatch
KP
@
@ =

 Độ chính xác trung bình MAP
Độ chính xác trung bình là giá trị trung bình của các P@K tại các mức K có
đối tượng đúng.
Độ chính xác trng bình được tính theo công thức:

∑
∑
=
=
×
=
n
j
n
K
jI
KIKP
AP
1
1
)(
)(@

=
1

Tóm tắt chương một
Trong chương một, khóa luận trình bày khái quát về hệ thống tìm kiếm thực
thể người và bài toán tìm kiếm người trên Web. Đồng thời, khóa luận cũng trình

13

bày một số nội dung chính liên quan tới bài toán và phương pháp đánh giá cho bài
toán tìm kiếm người trên Web.
Trong chương tiếp theo, khóa luận nêu ra một số phương pháp giải quyết
được áp dụng thành công đối với các vấn đề chính trong bài toán tìm kiếm người
trên Web.

14

Chương 2. Vấn đề phân biệt nhập nhằng tên người và xếp hạng kết quả
tìm kiếm người cùng tên
Trong chương này, khoá luận trình bày hai vấn đề chính trong bài toán tìm
kiếm người trên Web là vấn đề phân biệt nhập nhằng tên người và vấn đề xếp hạng
kết quả tìm kiếm người cùng tên với một số hướng tiếp cận giải quyết các vấn đề
này. Với mỗi miền dữ liệu khác nhau, các nhóm tác giả đề xuất các phương pháp
giải quyết vấn đề khác nhau. Trên thế giới, vấn đề phân biệt nhập nhằng tên người
đã được quan tâm nghiên cứu từ lâu và đã đạt được những kết quả khá tốt, điển hình
là phương pháp phân cụm dữ liệu. Bên cạnh đó, vấn đề xếp hạng thực thể cũng tồn
tại một số hướng giải quyết được đề xuất bởi một số nhóm tác giả. Trong phần này,
khoá luận sẽ trình bày một số hướng tiếp cận tiêu biểu dựa trên phương pháp phân
cụm dữ liệu để giải quyết vấn đề nhập nhằng tên người và các hướng tiếp cận cũng
như mô hình giải quyết tiêu biểu vấn đề xếp hạng thực thể.

(
)
P
t
p
t
p
t
p
m
ωωωω
, ,,
21
=

Trong đó, m là số lượng các từ khóa duy nhất trong trang Web p

k
t
(k=1,2,….,m) xác định mỗi từ khóa
Mỗi thành phần
pp
t
trong
k
ωω
được tính toán theo công thức sau:

(
)

α
là tần số tài liệu của từ khóa
k
t

N là số lượng các trang Web kết quả.
Ngoài ra, hệ thống xác định vecto trọng tâm của một cụm G

(
)
m
ttt
gggG , ,,
21
=

Với
k
t
g
trọng số của vecto trọng tâm của một cụm.
Bước 3: Áp dụng thuật toán phân cụm bán giám sát
Thuật toán phân cụm bán giám sát được mô tả như sau:
Đầu vào: tập các trang Web kết quả tìm kiếm
(
)
nip
i
, ,2,1=
và một trang seed