ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ GIẢI PHÁP PHÂN BIỆT TÊN NGƢỜI TRÊN WEB
DỰA TRÊN MÔ HÌNH THÔNG TIN NGƢỜI VÀ
THỬ NGHIỆM VÀO HỆ THỐNG TÌM KIẾM NGƢỜI
TIẾNG VIỆT KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin Cán bộ hƣớng dẫn: ThS. Nguyễn Cẩm Tú

HÀ NỘI - 2011 i

LỜI CẢM ƠN
Lời đầu 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 PGS.TS. Hà
Quang Thụy, ThS. Nguyễn Cẩm Tú và CN. Nguyễn Đạo Thái đã tận tình 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 cũng xin gửi lời cảm ơn tới các anh chị và các bạn sinh viên trong phòng thí
nghiệm KT-Sislab đã 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.

= 83.1 %.
Điều này khẳng định mô hình là khả quan và có khả năng ứng dụng vào thực tế. iii

Lời cam đoan

Tôi xin cam đoan mô hình phân biệt tên người dựa trên mô hình thông tin Người
và thực nghiệm được trình bày trong khóa luận này là do tôi thực hiện sự hướng dẫn của
ThS. Nguyễn Cẩm Tú và CN. Nguyễn Đạo Thái. Các số liệu và kết quả có được trong
luận văn là trung thực và chưa từng được công bố ở bất kỳ một công trình nào khác.
Tôi cũng nêu rõ nguồn gốc của những tham khảo từ các nghiên cứu liên quan trong
danh mục tài liệu tham khảo của khóa luận. Trong khóa luận, không có việc sao chép tài
liệu, công trình nghiên cứu của người khác mà không chỉ rõ về tài liệu tham khảo.

Sinh viên
Nguyễn Thị Thanh Na
iv

MỤC LỤC
LỜI CẢM ƠN i
Tóm tắt ii
Lời cam đoan iii
MỤC LỤC iv
Danh mục các bảng vii
Danh mục hình vẽ viii

3.2.1. Mô hình không gian vector 35
3.2.2. Độ tương đồng Cosin 37
3.2.3. Thuyết chắc chắn Stanford 37
3.2.4. Phân cụm phân cấp HAC (Hierachical agglomerative clustering) 38
3.3. Mô hình giải quyết bài toán 42
3.4. Áp dụng bài toán phân biệt tên người vào hệ thống tìm kiếm thực thể 49
Tóm tắt chương 3 50
Chương 4: Thực nghiệm và đánh giá 51
4.1. Môi trường và công cụ sử dụng thực nghiệm. 51
4.2. Quá trình thực nghiệm: 53
4.2.1. Xây dựng tập dữ liệu thực nghiệm 53
4.2.2. Trích chọn đặc trưng 55
4.2.3. Biểu diễn mô hình thông tin Người: 56
4.2.4. Phân cụm 56
4.4. Đánh giá 59
4.4.1. Phương pháp đánh giá. 59
4.4.2. Kết quả kiểm thử 60 vi

4.5. Nhận xét 60
Kết luận 62
PHỤ LỤC 64
TÀI LIỆU THAM KHẢO 65
Hình 7. Mô hình đoán nhận và giải quyết nhập nhằng thực thể tiếng Việt 16
Hình 8. Hệ thống phân biệt thực thể người sử dụng không gian vector 19
Hình 9. Trích từ tài liệu doc.36 20
Hình 10. Trích từ tài liệu doc.38 20
Hình 11. Chuỗi kết quả của đoạn trích trong tài liệu doc.36 21
Hình 12. Chuỗi kết quả của đoạn trích trong tài liệu doc.36 21
Hình 13. Các bước trong bài toán phân biệt tên người 27
Hình 14. Các bước trích chọn thuộc tính người. 29
Hình 15 : Đoạn tóm tắt của bài báo “Nữ cán bộ Agribank bị bắt vì nghi tham ô 6 tỷ
đồng.” 34
Hình 16: Tên người các tên người khác cùng xuất hiện với tên người “Trương Hồng
Nhung” 35
Hình 17. Biểu diễn văn bản trong khôn gian vector 36
Hình 18. Sơ đồ thuật toán phân cụm HAC 39
Hình 19: Phân cụm với độ đo single-link 41
Hình 20: Phân cụm với độ đo complete-link 41
Hình 21. Mô hình giải quyết bài toán phân biệt tên người dựa trên mô hình thông tin
Người 43 ix

Hình 22. Mô hình hệ thống tìm kiếm thực thể người 49
Hình 23. Chương trình thu thập dữ liệu. 54
Hình 24: Định dạng văn bản lưu các đặc trưng trích chọn được 55
Hình 25: Mô tả kết quả phân cụm 58


Mở đầu
Tên người là một trong những từ khóa được tìm kiếm nhiều nhất trên Web thông
qua máy tìm kiếm. Tuy nhiên, thực thể người là một trong những thực thể có độ nhập
nhằng cao nhất - một tên người có thể ứng với nhiều thực thể người khác nhau, nhiều tên
người cũng có thể là của cùng một thực thể người. Vì vậy, với một truy vấn tên người, kết
quả trả về từ máy tìm kiếm thường bao gồm những người khác nhau cùng tên. Để tìm
được thông tin quan tâm, người dùng phải đọc lần lượt nội dung các trang web trả về,
điều này gây mất thời gian và công sức của người dùng. Bài toán phân biệt tên người
nhằm giải quyết vấn đề trên bằng cách gom cụm kết quả trả về từ máy tìm kiếm sao cho
những trang Web thuộc cùng một cụm nói về một người và những trang Web thuộc các
cụm khác nhau nói về những người khác nhau. Bài toán này nhận được sự quan tâm rất
lớn từ các nhà nghiên cứu và các hội nghị lớn trên thế giới trong những năm gần đây như
Coling/ACL, Senseval, … Đặc biệt, dãy các hội nghị WePS-1,2,3
1
là hội nghị dành riêng
cho bài toán phân biệt tên người và tìm kiếm người trên Web.
Tại Việt Nam, bài toán phân biệt tên người vẫn đặt ra nhiều thách thức do tính
phức tạp của ngôn ngữ tiếp Việt và số lượng nghiên cứu về bài toán phân biệt tên người
vẫn còn hạn chế. Các nghiên cứu chủ yếu tiếp cận theo phương pháp tìm thể hiện tốt nhất
cho ngữ cảnh của người, tính độ tương đồng ngữ cảnh, từ đó phân cụm văn bản theo độ
tương đồng ngữ cảnh. Mặt khác, các phương pháp chỉ áp dụng trên các miền dữ liệu
tương đối đặc thù, không áp dụng được cho nhiều miền dữ liệu. Trên cơ sở hiểu và phân
tích các phương pháp mới giải quyết bài toán phân biệt tên người trên thế giới, khóa luận
đề nghị một mô hình giải quyết bài toán phân biệt tên người dựa trên mô hình thông tin
Người trên miền dữ liệu các trang tin điện tử tiếng Việt. Kết quả thực nghiệm cho thấy mô
hình là khả quan và có khả năng ứng dụng tốt vào thực tế.
Nội dung của khóa luận được bố cục gồm 4 chương:
Chƣơng 1. Giới thiệu khái quát về bài toán phân biệt tên người, các khái niệm và
vấn đề liên quan đến bài toán phân biệt tên người.
Chƣơng 2. Giới thiệu các phương pháp tiếp cận giải quyết bài toán phân biệt tên

từ Internet. Trong các nguồn đó, thông tin từ Internet là nguồn tri thức khổng lồ đang
được quan tâm khai thác nhiều. Tìm kiếm thông tin người là một hoạt động phổ biến trên
WWW. Tuy nhiên, tên người rất mơ hồ, một tên người được sử dụng chung bởi nhiều
người khác nhau, nên việc tìm kiếm thông tin của một người trong số họ rất khó khăn.
Chương này tập trung giới thiệu khái quát về bài toán phân biệt tên người.
1.1. Giới thiệu về vấn đề phân biệt tên ngƣời
Vấn đề phân biệt tên người có vai trò quan trọng trong lĩnh vực khai thác dữ liệu
web. Số truy vấn tên người trong máy tìm kiếm trên Web chiếm tỉ lệ cao, tuy nhiên, kết
quả trả về cho tên người thường bị nhập nhằng (nhiều người khác nhau chia sẻ cùng tên).
Theo thống kê năm 2007 [8], 30% truy vấn trong máy tìm kiếm chứa một tên người, 4%
truy vấn Web là một tên người và tên người có độ nhập nhằng cao: Theo thống kê điều tra
dân số Mỹ, 90.000 tên khác nhau được chia sẻ cho hơn 100 triệu người. Trong hầu hết
trường hợp, kết quả trả về từ máy tìm kiếm là một hỗn hợp của các trang về những người
khác nhau cùng chia một tên. Vì vậy, vấn đề phân biệt nhập nhằng tên người trên Web
mang một ý nghĩa rất quan trọng đối với các hệ thống tìm kiếm thực thể người.
1.1.1. Hệ thống tìm kiếm thực thể
 Vấn đề khai thác thông tin trên Web
Ngày nay, World Wide Web (WWW) đã trở thành một kho tài nguyên dữ liệu
khổng lồ về mọi lĩnh vực và đang ngày càng tăng trưởng với tốc độ cao. Kho tài nguyên
dữ liệu Web chứa nhiều thông tin quý giá phục vụ nhu cầu tìm kiếm thông tin của tất cả
mọi người trên thế giới. Với mục đích phục vụ nhu cầu khai thác thông tin của con người,
WWW hiện đang giữ một vai trò ngày càng quan trọng nhờ chứa những ưu điểm riêng
của nó.
Thông tin trên WWW rất phong phú. Nguồn thông tin trên Web luôn được cập
nhật từng ngày từng giờ bởi tất cả cá nhân, tổ chức trên thế giới, từ đó góp phần làm giàu
thêm kho tài nguyên khổng lồ WWW và giúp cho người dùng có nhiều cơ hội tìm kiếm,
tổng hợp các tri thức để tạo ra những giá trị mới. 4

Hình 1: Cấu trúc chung của một máy tìm kiếm [16]
Máy tìm kiếm bao gồm các thành phần chính sau:
- Thành phần crawling (Crawler): Thành phần này có chức năng thu thập các trang
Web bằng cách duyệt không gian Web, đi dọc theo các siêu liên kết trên các trang Web.
Sau đó, gửi lưu tập các trang web thu thập được vào Reposotory để lưu trữ.
- Thành phần chỉ mục (Indexer): Thực hiện việc lưu trữ nội dung các trang web
theo cấu trúc chỉ mục thuận và chỉ mục ngược.
- Thành phần phân tích truy vấn (Query engine): Thành phần có nhiệm vụ xử lý
truy vấn của người dùng. Nó thực hiện đọc truy vấn, phân tích và chuyển các truy vấn
dang định dạng thích hơp.
- Thành phần xếp hạng (Ranking): Thực hiện xếp hạng các trang Web theo độ
tương đồng giữa câu truy vấn và tài liệu Web trước khi hiển thị cho người dùng. 6

Với cách tổ chức và thực thi của mình, máy tìm kiếm chỉ đáp ứng phần nào nhu
cầu cải thiện khả năng khai thác thông tin do những tồn tại sau:
- Người dùng phải thay đổi câu truy vấn nhiều lần để xác định được câu lệnh truy
vấn phù hợp thông tin mà người dùng muốn tìm kiếm. Câu truy vấn sau thường phải dựa
vào kết quả trả về của hệ thống tìm kiếm khi người dùng nhập vào các các câu truy vấn
trước.
- Nhờ thành phần ranking, hệ thống tìm kiếm sẽ đưa về các trang web phù hợp
nhất với từ khóa mà người dùng nhập vào, tuy nhiên, các trang web trả về vẫn bao gồm cả
những thông tin người dùng quan tâm lẫn những thông tin người dùng không quan tâm, vì
vậy người dùng vẫn phải duyệt từng trang web để tìm thông tin mình đang tìm kiếm.
- Các hệ thống tìm kiếm vẫn chủ yếu dựa vào mức từ, các đặc trưng liên quan đến
ngữ nghĩa của ngôn ngữ còn ít. Vì vậy, kết quả trả về nhiều khi không đúng với mong
muốn của người dùng.
 Hệ thống tìm kiếm thực thể


Với đối tượng trả về là các thực thể, hệ thống tìm kiếm thực thể cung cấp cho
người dùng một mức chọn lọc thông tin cao hơn và hệ thống sẽ được nhìn nhận dưới
dạng đồ thị các thực thể thay cho đồ thị Web trong máy tìm kiếm thông thường. Nhờ đặc
tính này, người dùng tìm kiếm thông tin mình quan tâm nhanh và dễ dàng hơn nhiều (xem
hình 5).
Tùy theo kỹ thuật sử dụng khác nhau, các hệ thống tìm kiếm thực thể được tổ chức
khác nhau. Sử dụng kỹ thuật trích xuất thông tin, hệ thống sẽ được tổ chức như
hình 4.

Hình 4. Kiến trúc 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 [17]
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 hai
bộ phận chính là trích xuất thông tin về thực thể và tổng hợp thông tin về thực thể. 9

Thành phần trích xuất thông tin về thực thể làm nhiệm vụ trích xuất ra các thông
tin liên quan đến đến một thực thể xác đinh từ tất cả các trang Web chứa loại thực thể.
Việc này không đơn giản vì các dữ liệu trên trên Web thường là dữ liệu phi cấu trúc hoặc
bán cấu trúc.
Sau khi có thông tin về từng thực thể, thành phần tổng hợp thông tin về thực thể sẽ
tổng hợp lại các thông tin thu thập những lần khác nhau cho mỗi thực thể. Điều này là khó
khăn khi gặp các thực thể khác nhau nhưng dùng cùng tên và những tên khác nhau cùng
trỏ đến một thực thể, đặc biệt trong vấn đề tìm kiếm người.
Một số hệ thống tìm kiếm thực thể điển hình:
Một hệ thống tìm kiếm thực thể điển hình là hệ thống Cazoodle
2
do nhóm nghiên

Google
Yahoo
Bing
1
Michael Jackson
Michael Jackson
Michael Jackson
2
Facebook
Twitter
Twilight
3
Tuenti
Swine Flu
WWE
4
Twitter
Stock Market
Megan Fox
5
Sanalika
Farrah Fawcett
Britney Spears
6
New Moon
Patrick Swayze
Naruto
7
Lady Gaga
Cash for Clunkers

Tiger Woods
4
nicki minaj
Kim Kardashian
Lady Gaga
5
Friv
Lady Gaga
Barack Obama 12

6
Myxer
iPhone
Hairstyles
7
katy perry
Megan Fox
Kate Gosselin
8
Twitter
Justin Biebe
Walmart
9
Gamezer
American Idol
Justin Bieber
10
13
d1 d2
Hình 6. Tổng hợp thông tin của người P từ 2 trang d
1
và d
2

Người dùng nhập vào các từ khóa A, B, D, E mong muốn tìm được người P.
Trường hợp hệ thống tìm kiếm thực thể người không kết hợp giải quyết bài toán
phân biệt tên người, khi người dùng nhập vào các từ khóa như trên, nếu không có bài viết
d
i
nào khác nói về người P và chứa 4 đặc trưng A, B, D, E. Hệ thống tìm kiếm thực thể