PHÂN BIỆT NHẬP NHẰNG TÊN NGƯỜI TRONG HỆ THỐNG TÌM KIẾM THỰC THỂ

Mục lục

Chương 1. Bài toán phân biệt nhập nhằng tên người trong hệ thống tìm kiếm
thực thể. 3
1.1. Hệ thống tìm kiếm thực thể 3
1.1.1. Những thuận lợi và khó khăn trong việc khai thác thông tin trên WWW 3
1.1.2. Hệ thống tìm kiếm thực thể 4
1.1.3. Vấn đề giải quyết nhập nhằng tên trong hệ thống tìm kiếm thực thể người 7
1.2. Bài toán phân biệt nh
ập nhằng tên người trên tập văn bản. 9
1.2.1. Phát biểu bài toán 9
1.2.3. Mối quan hệ với bài toán phân biệt nhập nhằng nghĩa của từ. 9
1.2.3. Phương pháp đánh giá 10
Tóm tắt chương một 11
Chương 2. Phương pháp giải quyết bài toán nhập nhằng tên người trên tập văn
bản 12
2.1. Tiếp cận dựa trên thực th
ể định danh 12
2.2. Tiếp cận dựa trên từ khóa 14
2.3. Tiếp cận dựa trên kỹ thuật trích xuất thông tin 18
2.4. Một số cách tiếp cận khác 20
Tóm tắt chương hai 21
Chương 3: Mô hình hệ thống phân biệt nhập nhằng tên người 22
3.1. Cơ sở thực tiễn 22
3.2. Cơ
sở lý thuyết 24
3.2.1. Mô hình không gian vector 24
3.2.2. Thuật toán phân cụm HAC 26
3.3. Mô hình hệ thống phân biệt nhập nhằng tên người trên tập văn bản 31
3.4. Áp dụng bài toán phân biệt nhập nhằng tên người trong hệ thống tìm kiếm thực
thể người 33
Tóm tắt chương ba 34
Chương 4. Thực nghiệm và đánh giá 35

4.1. Môi trường và các công cụ sử dụng thực nghiệm. 35
4.2. Xây dựng tập dữ liệu 36
4.3. Thực nghiệm 37
Thực nghiệm phân biệt nhập nhằng tên người trên tập văn bản. 37
Kết luận 41
Tài liệu tham khảo 42


Danh sách hình vẽ
Hình 1 - Kết quả tìm kiếm từ Google với truy vấn “nokia 6030” 5
Hình 2 - Đồ thị giữa các trang Web dưới góc nhìn thực thể 5
Hình 3 - 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. 6
Hình 4 - Hệ thống tìm kiếm nơi nghỉ mát của Cazoodle 7
Hình 5 - Danh sách top 10 từ khóa được tìm kiếm trong Google, Bing và Yahoo năm
2009 8
Hình 7 - Các mẫu trích xuất sinh tự động cho ngày sinh 19
Hình 8 - Đoạn trích từ bài báo “Năm 2010: ĐH Quốc gia Hà Nội tuyển sinh 5.500 chỉ
tiêu” 22
Hình 9 - Đoạn trích từ bài báo “Cá ngừ độc là do chứa histamin tự do” 23
Hình 10 - Trích từ bài báo “11 giám đốc bưu điện đồng loạt hầu tòa” từ trang
vnexpress.net 23
Hình 11 - Trích từ bài báo “Siêu lừa Nguyễn Lâm Thái có dấu hiệu tâm thần” từ trang
vnexpress.net 24
Hình 13 - Quy trình phân cụm 26
Hình 14 - Ví dụ về thuật toán K-means 27
Hình 15 - Hình vẽ minh họa cho phân cụm dữ liệu dựa trên mật độ. 27
Hình 16 - Sơ đồ các phân tử trước khi phân cụm 28
Hình 17 - Sơ đồ các phần tử sau khi phân cụm phân cấp 28
Hình 18 - Phân cụm với Single-linkage 30
Hình 19 - Phân cụm với Complete-linkage 30
Hình 20 - Trung bình các khoảng cách trong GAAC 31
Hình 22 - Trích từ bài viết “Lê Thị Thanh Nhàn – nữ PGS toán học trẻ nhất VN” -báo
dantri.com.vn 39
Hình 23 - Trích từ bài viết “Kịch tính vòng chung khảo Nhân tài đất Việt CNTT
2008!” – báo dantri.com.vn 39


Danh sách các từ viết tắt

HAC Hierarchical agglomerative clustering
GAAC
Group-average agglomerative clustering
WSD Word Sense Disambiguation
WWW World Wide Web


1

Mở đầu


Sự ra đời của các máy tìm kiếm đã giúp ích cho con người rất nhiều trong các
hoạt động khai thác thông tin. Tuy nhiên, chất lượng tìm kiếm thông tin vẫn còn nhiều
hạn chế, đặc biệt là tìm kiếm thông tin về người, một trong những lĩnh vực có truy vấn
lớn nhất trong các máy tìm kiếm. Mặt khác, thực thể người là một trong những loại
thực thể có độ nhập nhằng cao nhất, vì vậy mà các kết quả trả v
ề bởi máy tìm kiếm sẽ
bao gồm tất cả những người có tên giống nhau và người dùng cần phải đọc lần lượt để
tìm ra kết quả mong muốn. Vì vậy mà cần thiết phải có 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 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 cốt lõi cho vấn đề này là bài toán gi
ải quyết nhập nhằng tên người trên
tập văn bản. Bài toán này đã nhận được sự quan tâm từ các nhà nghiên cứu trong các
hội nghị lớn trong những năm gần đây như Colling, ACL, Senseval…Đặc biệt là hội
nghị WebPS
1
, hội nghị dành riêng cho các vấn đề giải quyết nhập nhằng tên người
trong kết quả tìm kiếm Web. Trong những năm gần đây, có rất nhiều nghiên cứu và ý
tưởng được đề xuất trên thế giới để giải quyết bài toán này,
Tuy nhiên, đối với tiếng Việt thi các nghiên cứu về bài toán này vẫn còn rất hạn
chế. Các nghiên cứu tập trung chủ yếu vào việc thể hiện tốt nhất các ngữ c
ảnh riêng
biệt cho từng người, tìm các độ đo tương đồng ngữ cảnh phù hợp và phân cụm ngữ
cảnh, hay phân cụm văn bản chứa ngữ cảnh. Và các phương pháp thường chỉ thao tác
trên một miền dữ liệu tương đối đặc thù, chứ không có một phương pháp khả thi trên
nhiều miền dữ liệu. Việc tìm ra một phương pháp tốt cho tiếng Việt vẫn là một vấn đề
khó kh
ăn, mặc dù tiếng Việt đã giải quyết được một số bài toán cơ sở (thuộc đề tài KC
01.01/06-10), tuy nhiên so với nhu cầu của bài toán giải quyết nhập nhằng tên người
thì vẫn chưa đủ.
Mục tiêu của khóa luận là khảo sát, nghiên cứu để đưa ra một phương pháp đủ
tốt giải quyết bài toán phân biệt nhập nhằng tên người trên miền dữ liệu báo điện tử
ti
ếng Việt. Để đạt được mục tiêu này, khóa luận khảo sát một số phương pháp tiêu
biểu nhất giải quyết bài toán này trên thế giới. Từ đó, khóa luận đưa ra phương pháp
giải quyết bài toán phân biệt nhập nhằng tên người trên tập văn bản tiếng Việt. Đầu
tiên, khảo sát miền dữ liệu báo điện tử để tìm ra những đặc trưng tốt (dựa trên từ vựng
và đặc điểm mạng xã hội) thể hiện riêng biệt cho một người, phân biệt người đó với
những người khác cùng tên. Tiếp đó, thực hiện việc gom cụm các văn bản chứa tên

1
http://nlp.uned.es/weps/

2

người này bằng thuật toán HAC. Khóa luận đã thực nghiệm với kết quả độ đo F đạt
mức tốt so với kết quả của thế giới (F
5.0
= 0.791 và F
2.0
= 0.773); đồng thời, đề xuất
một mô hình hệ thống tìm kiếm thực thể người dựa trên kết quả bài toán này.
Nội dung của khóa luận được chia thành các chương như sau:
Chương 1: Khóa luận giới thiệu khái quát về hệ thống tìm kiếm thực thể và bài
toán giải quyết nhập nhằng tên người trên tập tài liệu, vai trò của bài toán đối với hệ
thống tìm kiếm thực thể người. Khóa luậ
n cũng trình bày mối liên hệ của bài toán với
bài toán phân biệt nhập nhằng nghĩa của từ, và phương pháp đánh giá cho bài toán
phân biệt nhập nhằng tên người trên tập văn bản.
Chương 2: Khóa luận giới thiệu chi tiết các phương pháp tiêu biểu để giải
quyết vấn đề phân biệt nhập nhằng tên người trên tập văn bản.
Chương 3: Khoá luận đã giới thiệu các đặc trư
ng của miền dữ liệu báo điện tử
để từ đó đề xuất ra mô hình giải quyết bài toán nhập nhằng tên người trên tập văn bản
và ứng dụng bài toán đó trong việc đề xuất mô hình hệ thống tìm kiếm thực thể người.
Chương 4: Thực nghiệm, kết quả và đánh giá. Tiến hành thực nghiệm việc việc
phân biệt nhập nhằng trên miền dữ
liệu báo điện tử tiếng Việt với tập dữ liệu kiểm thử
là những tên người có độ nhập nhằng cao.
Phần kết luận: Tóm lược kết quả đạt được của khóa luận và định hướng phát
triển tương lai.


3

Chương 1. Bài toán phân biệt nhập nhằng tên người trong hệ
thống tìm kiếm thực thể.
Tìm kiếm thông tin là nhu cầu thiết yếu trong cuộc sống con người. Con người
có được thông tin mong muốn từ rất nhiều các nguồn tài liệu khác nhau như sách vở,
tạp chí, và đặc biệt là Internet. Internet là một kho dữ liệu đồ sộ, tuy nhiên khai thá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. Con
người mong muốn có những thông tin ở dạng thực thể, bản ghi (thông tin có cấu trúc)
hơn là việc phải đọc lần lượ
t từng trang Web để tìm ra thông tin mình mong muốn.
Một trong những đối tượng tìm kiếm được quan tâm nhất là tìm kiếm người. Tuy
nhiên, khi thực hiện thu thập thông tin về một người, chúng ta vấp phải thách thức là
những người khác nhau có cùng tên nhưng người chúng ta mong muốn tìm kiếm chỉ là
một trong số họ. Vì vậy đối với các hệ thống tìm kiếm thực thể người, giải quyết bài
toán nhập nhằng tên có một ý nghĩa rất quan trọ
ng. Chương này sẽ giới thiệu một số
khái niệm và các vấn đề liên quan đến bài toán phân biệt nhập nhằng tên người trong
máy tìm kiếm thực thể.
1.1. Hệ thống tìm kiếm thực thể
1.1.1. Những thuận lợi và khó khăn trong việc khai thác thông tin trên WWW
Khối lượng dữ liệu khổng lồ trên WWW là nguồn tài quyên quý giá cho người
dùng trong việc khai thác và tìm kiếm thông tin phục vụ cho nhu cầu hiểu biết của
mình. Người dùng có thể truy cập nguồn tài nguyên này mọi lúc, mọi nơi một cách
thuận tiện; họ 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. Tuy nhiên, khai khác nguồn tri thức này thế nào cho hiệu quả là một vấn đề lớn.
Đặc biệt là khi lượng thông tin trên WWW ngày càng nhiều, và luôn thay đổi hàng
ngày hàng giờ tiêu biểu là các tờ báo điện tử tin tức cập nhật trang tin, các website về
thị trường chứng khoán. Hình thức thông tin ngày càng đa dạng từ văn bản đến âm
thanh, hình ảnh làm cho con người cảm giác ngập trong tri thức, khó khăn trong việc
tìm ra tri thức mình cần. Do đó, cần phải có một cách thức tổ chức, quản lý, điều hành,
cập nhật thông tin từ WWW phù hợ
p để thuận lợi cho việc khai thác
Máy tìm kiếm ra đời như một công cụ hữu ích trợ giúp trong việc khai thác thông
tin trên WWW, và phần nào đáp ứng được nhu cầu người dùng. Máy tìm kiếm có một
cách tổ chức tương đối phức tạp nhằm mục tiêu cải thiện chất lượng khai thác thông
tin, bao gồm các thành phần chính [10]:

4

• Crawler: Thành phần này chịu trách nhiệm đi dọc theo các siêu liên kết trên
WWW để thu thập các trang web để đảm bảo tính đầy đủ, và tươi mới của của
thông tin.
• Indexer: Thành phần này thực hiện việc lưu trữ nội dung các trang Web theo
cấu trúc chỉ mục ngược đảm bảo việc truy suất nhanh thông tin.
• Query Engine: Thành phần này thực hiện xử lý với các truy vấn của người dùng
rồi chuyển về dạng phù h
ợp thực hiện cho việc tìm kiếm.
• Ranking: Thành phần này thực hiện việc xếp hạng lại kết quả các trang theo độ
phù hợp với câu truy vấn trước đi khi trình bày tới người dùng.
Mặc dù đã có rất nhiều cải tiến đối với các thuật toán xếp hạng máy tìm kiếm để
thông tin trình bày tới người dùng là phù hợp nhất, nhưng kết quả trả về vẫn là những
trang web bao gồm c
ả vùng thông tin người dùng quan tâm và các thông tin khác họ
không quan tâm. Do đó, người dùng mất thời gian để duyệt từng trang web tìm ra nội
dung mà họ mong muốn.
Một bất lợi nữa là người dùng rất khó mô tả được trực tiếp những điều họ truy
vấn ngay từ những truy vấn đầu tiên. Vì vậy mà họ cần bổ sung, thay đổi truy vấn theo
một cách nào đó có thể dựa trên các kết quả tìm kiếm lần trước để
có được những
thông tin phù hợp với nhu cầu.
Các hệ thống tìm kiếm hiện tại vẫn chủ yếu dựa trên mức từ vựng, chưa có nhiều
đặc trưng về tính hiểu ngữ nghĩa của ngôn ngữ, kết quả tìm kiếm không giống như
người dùng kì vọng đặc biệt là trong các trường hợp từ đồng nghĩa và từ đa nghĩa.
Tìm kiếm hướng thực thể là m
ột trong những hướng đi được quan tâm gần đây
để giải quyết những hạn chế của các hệ thống tìm kiếm thông tin hiện tại, nhằm đem
lại chất lượng khai thác thông tin tốt hơn tới người dùng. Xu hướng này sẽ được trình
bày ở phần tiếp theo của khóa luận.
1.1.2. Hệ thống tìm kiếm thực thể
Rõ ràng với đối tượng trả về là trang Web, mức độ chọn lọc thông tin phù hợp
với yêu cầu người dùng của các máy tìm kiếm vẫn còn ở mức độ chưa cao, và điều
người dùng cần là thông tin về các thực thể chứ không phải là các trang Web.
Ví dụ: bạn Cá muốn tìm kiếm giá, thuộc tính và hình ảnh của điện thoại Nokia
6030, khi đưa truy vấn “Nokia 6030” vào http://google.com
sẽ nhận được kết quả như
sau:

5


Hình 1
-
Kết quả tìm kiếm từ Google với truy vấn “nokia 6030”

Trong 10 kết quả đầu trả về bởi máy tìm kiếm Google, thậm chí có trang không
chứa thông tin về các thuộc tính của điện thoại “Nokia 6030”, điều này thật sự không
đáp ứng được kì vọng người dùng.
Các thực thể rất đa dạng từ các tổ chức, người, các sản phẩm, trường học, công
ty và chúng cũng được phân tán ở nhiều loại trang Web khác nhau như trang tin tức,
trang bán hàng, trang cá nhân, blog….
Khác với các hệ thống tìm ki
ếm thông thường có đối tượng tìm kiếm là các trang
Web, các hệ thống tìm kiếm thực thể có đối tượng tìm kiếm là các thực thể được trích
chọn ra từ nội dung của một hay nhiều trang Web liên quan. Hệ thống tìm kiếm thực
thể sẽ cung cấp cho người dùng một mức lọc thông tin ở mức cao hơn. Và khi đó đồ
thị Web được nhìn nhận lại dưới dạng đồ thị các thực thể [18]:

Hình 2 - Đồ thị giữa các trang Web dưới góc nhìn thực thể

Sau đâ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]


6


Hình 3 - 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.
Mô hình hệ thống tìm kiếm thực thể bao gồm các bộ phận chính sau:
• Trích xuất thông tin về thực thể
: Công việc của bộ phận này là trích xuất ra 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ể.
Ví dụ với thực thể điện thoại thì cần phải trích xuất được giá, nhà sản xuất, hình
ảnh, bản mô tả… của chiếc điện thoại đó. Đây là bài toán không đơn giản vì các
miêu tả theo ngôn ngữ tự nhiên không theo một mẫu nhất định đối vớ
i dữ liệu
phi cấu trúc, và bố cục trang Web cũng không giống nhau đối với dữ liệu bán
cấu trúc. Một giải pháp đặt ra là xây dựng bộ phận trích xuât thông tin cho từng
loại trang Web cho dữ liệu bán cấu trúc. Tuy nhiên điều này là rất khó khăn khi
thực hiện bóc tách thông tin trên một số lượng lớn các trang Web.
• Tổng hợp thông tin về thực thể
: Sau khi có thông tin về từng thực thể, bộ phận
này phải chịu trách nhiệm tổng hợp lại các thông tin thu thập được ở những lần
khác nhau về cùng thực thể đó. Ví dụ: Với cùng một sản phẩm, trong một trang
Web có giá của nó và trong các trang Web có các chức năng, nếu ta có thể tổng
hợp thông tin về thực thể thì ta sẽ có cái nhìn đầy đủ thông tin về thực thể . Tuy
nhiên điều này gặp phải mộ
t số khó khăn như: vấn đề những thực thể khác nhau
dùng cùng một tên và những tên khác nhau cùng trỏ về một thực thể, đặc biệt là
trong vấn đề tìm kiếm người. Phần tiếp theo của khóa luận sẽ trình bày chi tiết

7

các vấn đề liên quan đến bài toán phân biệt nhập nhằng tên người trong tìm
kiếm thực thể người.
Một số hệ thống tìm kiếm thực thể tiêu biểu:

Hệ thống Cazoodle
2
do nhóm nghiên cứu của Kevin Chen-Chuan Chang (thuộc
phòng thí nghiệm Cơ sở dữ liệu và Hệ thống thông tin DAIS thuộc trường đại học
Illinois) là một hệ thống tìm kiếm thực thể điển hình, bao gồm các lĩnh vực tìm kiếm
nơi nghỉ mát (Vacation Rental), tìm kiếm căn hộ (Apartment Rentals), và giá cả sản
phẩm (Electronics Shopping)

Hình 4 - Hệ thống tìm kiếm nơi nghỉ mát của Cazoodle

1.1.3. Vấn đề giải quyết nhập nhằng tên trong hệ thống tìm kiếm thực thể
người
Các truy vấn tìm kiếm người chiếm một tỉ lệ cao ( khoảng 10%) trong tìm kiếm
thông tin trên Internet. Theo thống kê những từ khóa được tìm kiếm nhiều nhất năm
2009, thì ở cả 3 máy tìm kiếm là Google, Bing và Yahoo đứng đầu đều là “Michael
JackSon”, và trong top 10 có rất nhiều từ khóa tìm kiếm tên người.

2
http://www.cazoodle.com/

Xem chi tiết: PHÂN BIỆT NHẬP NHẰNG TÊN NGƯỜI TRONG HỆ THỐNG TÌM KIẾM THỰC THỂ