Khóa luận Phân biệt nhập nhằng tên người trong hệ thống tìm kiếm thực thể

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Nguyễn Đạo Thái

PHÂN BIỆT NHẬP NHẰNG TÊN NGƯỜI TRONG HỆ

THỐNG TÌM KIẾM THỰC THỂ

KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY

Ngành: Công nghệ thông tin

HÀ NỘI - 2010

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

Nguyễn Đạo Thái

PHÂN BIỆT NHẬP NHẰNG TÊN NGƯỜI TRONG HỆ

THỐNG TÌM KIẾM THỰC THỂ

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: PSG.TS Hà Quang Thụy

Cán bộ đồng hướng dẫn: ThS Trần Mai Vũ

HÀ NỘI - 2010

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ỹ Trần Mai Vũ, 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ị và các bạn sinh viên trong nhóm “Khai

phá dữ liệu” 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.

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 thân

yêu luôn bên cạnh và động viên tôi trong suốt quá trình thực hiện khóa luận tốt nghiệp.

Tôi xin chân thành cảm ơn !

Sinh viên

Nguyễn Đạo Thái

Tóm tắt nội dung

Một trong những lĩnh vực tìm kiếm Internet được người dùng quan tâm nhất đó

chính là tìm kiếm thông tin về thực thể người. Thực thể người là một trong những loại

thực thể có độ nhập nhằng cao nhất, một tên có thể ứng với các thực thể người khác

nhau, và những tên khác nhau có thể ứng với một thực thể người. Tuy nhiên các máy

tìm kiếm hiện nay vẫn thao thác các văn bản chứa tên người giống như các văn bản

bình thường khác dẫn đến các kết quả tìm kiếm không được như người dùng mong

đợi.

Khóa luận tập trung nghiên cứu phương pháp giải quyết nhập nhằng tên người

trên tập văn bản trên miền dữ liệu báo điện tử tiếng Việt dựa trên đặc trưng về từ vựng

và mạng xã hội và đề xuất áp dụng xây dựng một hệ thống tìm kiếm thực thể người.

Thực nghiệm ban đầu với tập tên người có độ nhập nhằng cao cho thấy mô hình

phân biệt nhập nhằng tên người trên tập văn bản có độ chính xác khá cao và đạt độ đo

F ở mức tốt (F_0.5= 0.791 và F_0.2= 0.773). Kết quả trên cho thấy phương pháp phân

biệt nhập nhằng tên người đã đề xuất và triển khai là khả quan cho ngôn ngữ tiếng

Việt.

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

World Wide Web

WWW

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¹, 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

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

1

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_0.5= 0.791 và F_0.2= 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.

2

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]:

3

• 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:

4

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]

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.

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

6

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²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.

²http://www.cazoodle.com/

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

Nhưng tên người lại là một trong những loại thực thể có độ nhập nhằng cao nhất.

Ví dụ: khi tìm kiếm tên “Michael JackSon” trong hàng trăm kết quả trả về bởi máy tìm

kiếm Google, bên cạnh ca sỹ nổi tiếng còn có một chuyên gia về bia và một người

buôn súng. Việc phải duyệt từng trang Web để tìm ra người cần là một quá trình tốn

thời gian. Trong một hệ thống lý tưởng, người dùng chỉ cần đưa vào tên người, và kết

quả sẽ được phân cụm, trong đó mỗi cụm bao gồm các tài liệu về cùng một người kèm

theo những mô tả cho cụm đó, điều này giúp cho người dùng tiết kiệm được rất nhiều

thời gian và công sức. Các hệ thống thực thể tìm kiếm hiện tại đang chủ yếu vào tập

trung vào vấn đề trích xuất thuộc tính thực thể, nhưng với tìm kiếm thực thể người thì

vấn đề phân biệt nhập nhằng có ý nghĩa đặc biệt quan trọng. Nếu ta giải quyết được

bài toán này, ta có khả năng tổng hợp, “hàn gắn” các thông tin khác nhau về cùng một

người trong những lần xuất hiện khác nhau, cho ta một cái nhìn đầy đủ toàn diện về

người đó.

Ví dụ nếu người A tham gia sự kiện B,C ở trang P1, A lại tham gia sự kiên D,E

ở trang P2, ta có thể xây dựng được luồng sự kiện hoàn chỉnh nếu 2 tên A đều trỏ tới

một người

8

B

C

D

E

A

P1

P2

D

E

A

B

C

Hình 1.6 –

Hình 6 - Tổng hợp thông tin về người A từ 2 trang P1 và P2

Từ những phân tích trên ta thấy rằng, bài toán giải quyết nhập nhằng tên người

trong hệ thống tìm kiếm thực thể quy về vấn đề giải quyết nhập nhằng tên người trên

tập văn bản. Phần tiếp theo của chương này sẽ trình bày chi tiết về bài toán phân biệt

nhập nhằng tên người trên tập văn bản.

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.

1.2.1. Phát biểu bài toán

Theo Bagga [6], bài toán phân biệt nhập nhằng tên người trên tập văn bản có mục

tiêu là với mỗi tên người cho trước cần phải phân chia tập văn bản chứa tên đó thành

các nhóm, sao cho các văn bản trong cùng một nhóm cùng chỉ đến một người và các

văn bản thuộc các nhóm khác nhau thì chỉ đến những người khác nhau.

Miền dữ liệu của bài toán: Tập các trang Web tin tức từ các tờ báo điện tử của

Việt Nam.

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ừ.

Bài toán phân biệt nhập nhằng nghĩa của từ (Word Sense Disambiguation -

WSD) là bài toán có ý nghĩa quan trọng trong lĩnh vực xử lý ngôn ngữ tự nhiên, dành

được sự quan tâm nghiên cứu của các nhà khoa học từ rất lâu. Với hầu hết các ngôn

ngữ, luôn tồn tại một tập các từ có nhiều hơn một nghĩa, mà nghĩa của từ chỉ có thể

9

xác định dựa trên ngữ cảnh xuất hiện của nó. Mục tiêu của bài toán là xác định nghĩa

của một từ trong một văn bản cho trước, kết quả của bài toán này đóng vai trò quan

trọng để thực hiện các bài toán quan trọng tiếp theo trong lĩnh vực xử lý ngôn ngữ tự

nhiên như dịch máy, tóm tắt văn bản…Các hướng nghiên cứu giải quyết vấn đề này rất

đa dạng bao gồm học giám sát (supervised learning), học bán giám sát (semi-

supervised learning) và học không giám sát (unsupervised learning)...

Bài toán phân biệt nhập nhằng tên và nhập nhằng nghĩa đều có mục đích là giải

quyết nhập nhằng trong xử lý ngôn ngữ tự nhiên. Tuy nhiên bài toán WSD giải quyết

với một lớp rộng các từ: danh từ, tính từ, động từ, trạng từ…Khác biệt đầu tiên là sự

khác biệt nghĩa của từ là khá tinh tế, có những nghĩa rất gần nhau nhiều khi với chính

con người điều này rất khó khăn để nhận biết. Trái lại, với vấn đề tên người, sự phân

biệt rất rõ ràng. Khác biệt thứ hai là WSD thường làm việc với từ điển chứa một số

lượng nhỏ các nghĩa ứng với một từ. Nhưng với bài toán phân biệt tên người thì số

lượng người khác nhau lại không được biết trước và số lượng trung bình cho mỗi tên

cao hơn nhiều so với số lượng nghĩa cho mỗi từ ( Có khoảng 90000 tên được chia sẻ

bởi 100 triệu người theo US Census Bureau)

Chính vì số lượng tên người không biết trước nên việc xây dựng tập đặc trưng

cho từng người là một điều vô cùng khó khăn. Do đó hầu hết các các tiếp cận giải

quyết vấn đề này chủ yếu dựa trên phương pháp học không giám sát.

1.2.3. Phương pháp đánh giá

Trong khóa luận này, chúng tôi sử dụng phương pháp đánh giá của hội nghị

WePS-1 2007 (Hội nghị lớn nhất về các vấn đề trong tìm kiếm thực thể người. Đến

thời điểm này hội nghị đã tổ chức đến WebPS-3 tập trung vào hai nhiệm vụ trọng tâm

là trích xuất thuộc tính về người và phân biệt nhập nhằng tên người và tên các tổ chức)

dựa trên độ tinh khiết (purity), độ nghịch đảo tinh khiết (inverse purity) và độ đo F.

Các độ đo được định nghĩa như sau:

Gọi C là tập các cụm cần đánh giá, L là tập hợp các mục (categories) được gán

nhãn bằng tay (các mục ứng với những người khác nhau) và n là số lượng các văn bản

được phân cụm. Độ tinh khiết được tính dựa trên việc lấy trung bình có trọng số độ

chính xác:

(1.1)

10

Độ nghịch đảo tinh khiết tập được tính bởi công thức :

(1.2)

được định nghĩa như sau:

Trong đó:

Độ chính xác ứng với cụm C_ivới mỗi mục L

Precision (C_i, L ) = | C_i| / | C_i|

Độ đo F được tính theo công thức:

j

∩

L

j

(1.3)

(1.4)

Hệ thống thường sử dụng

Tóm tắt chương một

α

= 0.5 và

α

= 0.2.

Trong chương này, 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. 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 trong lĩnh vực này.

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

Trong chương này, khóa luận trình bày một số nghiên cứu trên thế giới về giải

quyết nhập nhằng tên người trên tập văn bản. Vấn đề này được thực hiện trên nhiều

miền lĩnh vực khác nhau từ phân biệt các tác giả trong các công trình khoa học, tên

người được đề cập đến trong các nhật báo, và những người nổi tiếng trên môi trường

WWW…Và mỗi miền ứng dụng khác nhau, các cách tiếp cận khác nhau được đề xuất

nhằm lấy ra những đặc trưng được coi là tiêu biểu nhất cho ngữ cảnh. Ở hầu hết các

công trình đều sử dụng giả thiết rằng, tất cả các tên giống nhau được đề cập trong một

văn bản đều chỉ nói tới một người duy nhất. Vì vậy công việc phân biệt nhập nhằng

tên người chuyển về bài toán phân cụm ngữ cảnh, trong đó những văn bản đề cập tới

một người được nhóm vào một cụm, văn bản đề cập đến những người khác thì thuộc

cụm khác và mỗi văn bản chỉ được thuộc về một cụm duy nhất.

2.1. Tiếp cận dựa trên thực thể định danh

Vào năm 1998, Bagga và Breck Baldwin [6] giới thiệu phương pháp giải quyết

bài toán phân biệt nhập nhằng tên người bằng cách xây dựng ngữ cảnh dựa trên tập

thực thể định danh xuất hiện trong câu chứa tên người bằng mô hình không gian

vector. Phương pháp này được thực nghiệm trên tập dữ liệu gồm 197 bài báo từ năm

1996 đến 1997 của tạp chí New York Times.

Mô tả phương pháp của Bagga như sau:

Bước 1 : Đầu tiên với mỗi bài báo được đưa vào, phần mềm CAMP sẽ xử lý

những bài báo này. Kết quả của quá trình xử lý là một chuỗi các thực thể và các tham

chiếu của nó trong văn bản.(Hệ thống CAMP của trường đại học Pennsylvania giải

quyết bài toán đồng tham chiếu trong một văn bản cho các lớp khác nhau như đại từ,

danh từ riêng [8]. Kết quả của hệ thống CAMP là một chuỗi các thực thể có tên xuất

hiện trong văn bản và các tham chiếu tới nó tương ứng trong văn bản đó)

Ví dụ:

Với văn bản đầu vào:

Văn bản doc.36

John Parry, of Weston Golf Club, announced his regination yesterday. He

was President of Massachusetts Golf Association. During his two years, Perry

guided the MGA into a closer relationship with Woment’s Golf Association of

Massachusetts.

12

Văn bản doc.38

Oliver “Biff” Kelly of Weymonth succeeds John Perry as President of

Massachusetts Golf Association. “We will haved continues growth in the future”

said Kelly, who will serve for two years. “There’s been a lot of changes and there

will be continued change as we head into the year 2000”

Kết quả của bước này đối với văn bản doc.36 là một chuỗi như sau:

John Parry

Weston Golf

Club

Massachusetts

Golf Association

Woment’s

Golf

Association

He

Perry

Hình 2.1 – Kết quả phân tích đồng tham chiếu văn bản doc.36

Kết quả của bước này đối với văn bản doc.38:

John Parry

Massachusetts

Golf

Association

Oliver “Biff”

Kelly

Hình 2.2 – Kết quả phân tích đồng tham chiếu văn bản doc.38

Bước 2 : Với mỗi chuỗi đồng tham chiếu cần được quan tâm ( ví dụ chuỗi đồng

tham chiếu ứng với “Jonh Perry” ) , module “Sentence Extractor” sẽ trích xuất ra tất

cả những câu chứa cụm danh từ trong chuỗi đồng tham chiếu trong văn bản. Hay nói

cách khác, module này sẽ thực hiện công việc tạo ra một bản tóm tắt biểu diễn chuỗi

thực thể của mỗi bài báo hướng về thực thể được quan tâm. Do đó với văn bản doc.36,

vì ít nhất một trong 3 cụm danh từ trong chuỗi đồng tham chiếu ( “John Parry”, ”He”,

13

”Perry” ) đều xuất hiện trong các câu của văn bản , nên phần tóm tắt được sinh bởi

module “Sentence Extractor” chính là phần trích xuất được. Còn với văn bản doc.38

phần tóm tắt chỉ là câu đầu tiên của phần trích xuất được bởi vì chỉ có duy nhất 1

thành phần duy nhất “John Parry” xuất hiện ở câu này.

Bước 3 : Với mỗi bài báo, hệ thống sử dụng mô hình biểu diễn không gian

vector (Vector Space Model) tính độ tương đồng giữa các bài báo này. Với mỗi bản

tóm tắt có được từ bước trước, các từ dừng được lọc bỏ, các từ khác được phân tích

hình thái để đưa về dạng ban đầu, và được biểu diễn bằng mô hình vector. Độ tương

đồng vượt trên một ngưỡng thì 2 bài báo được coi là cùng nói về một người.

Cụ thể như sau:

S₁và S₂là 2 vector cho 2 bản tóm tắt được trích xuất từ các bài báo D₁và D2

độ tương đồng của chúng được tính như sau:

,

w * w

Sim( S₁

,

S₂) =

(2.1)

∑

1 j

2 j

t _j

Trong đó t _jlà thành phần chung của 2 vector S₁

,

S₂

.

w_{1 j}là trọng số của t _jtrong S₁và w_{2 j}là trọng số của t _jtrong S₂

Trọng số t _jcủa vector Si được tính như sau:

.

N

tf * log

df

w _ij

=

(2.2)

s _i²₁+ s _i²₂+ .. + s _i²_n

Trong đó tf là tần số của t _jtrong phần tóm tắt.

N là số lượng văn bản.

2.2. Tiếp cận dựa trên từ khóa

Trong bài báo năm 2006, Danushka Bollengala [9] trình bày một thuật toán học

không giám sát tạo ra những cụm từ khóa duy nhất để phân biệt những người khác

nhau có cùng tên. Thuật toán nhận đầu vào là tên một người và cho ra kết quả là tập

các cụm từ khóa duy nhất thể hiện cho những người khác nhau. Các cụm từ này sau

đó có thể được bổ sung vào truy vấn để làm hẹp miền tìm kiếm do đó tăng độ chính

xác cho các kết quả tìm kiếm. Phương pháp được áp dụng cho miền dữ liệu các tên

nhà khoa học trên dữ liệu Web.

Lược đồ hệ thống được mô tả như sau

14

Hình 2.3 - Lược đồ hệ thống phân biệt nhập nhằng tên người dựa trên từ khóa

Những module chính của hệ thống:

Bước 1: Thu thập web chứa tên cần phân biệt nhập nhằng (Download Web Pages)

Bước này hệ thống sử dụng máy tìm kiếm Google, các truy vấn sẽ được đưa vào

máy tìm kiếm và lấy ra 100 kết quả đầu tiên cho mỗi tên cần phân biệt nhập nhằng.

Bước này có thể bỏ qua nếu như đã có sẵn một tập tài liệu chứa tên nhập nhằng.

Bước 2: Trích xuất các “term” quan trọng (Extract Terms)

Ở bước này mô hình dựa trên giả thuyết là: Nếu sự xuất hiện của các tên nói về

cùng một người thì ngữ cảnh xung quanh chúng là giống nhau. Và điều này dẫn đến là

nếu 2 tên có ngữ cảnh xuất hiện giống nhau thì khả năng cao là chúng đề cập đến cùng

một người. Do đó, hệ thống cần phải chọn được những đặc trưng mang thông tin tốt

nhất cho ngữ cảnh tên người xuất hiện.

Mô hình “Term” (Term Model) được đề xuất cho việc thể hiện ngữ cảnh của mỗi

tên.

Mô hình T(A) = t₁, t₂,… t _Ncủa một tên A được định nghĩa như một tập hợp các

“term” được trích xuất từ ngữ cảnh của tên. Các “term” được trích xuất tự động sử

dụng thuật toán C-Value.

Thuật toán C-Value kết hợp thông tin về ngôn ngữ và thông tin về thống kê.

Thông tin về ngôn ngữ bao gồm việc gán nhãn từ loại, lọc bỏ từ dừng, và sử dụng một

số mẫu về ngôn ngữ để thành lập các cụm danh từ. Ví dụ như: có mẫu một số tính từ

đứng trước danh từ thì chúng và danh từ đó tạo thành cụm danh từ. Các thông tin về

thống kê cho phép loại bỏ các cụm từ ít mang lại thông tin cho ngữ cảnh của tên. Khái

niệm “termhood” (mức độ một cụm danh từ trở thành “term”) được đánh giá dựa trên

C-value[14,15]. Giá trị của C-value được tính như sau:

15

log ₂|a|*f(a)

log|a|(f(a) -

nếu a nằm trong “term” khác

C-value(a) =

1

f (b)

) trường hợp ngược lại

∑

P(T_a) _b∈T

a

(2.3)

Trong đó:

a là ứng viên.

f(a) là tần số của ứng viên trong văn bản.

|a| là độ dài của a.

T _alà tập các cụm từ chứa a.

P(T _a) là số lượng cụm từ T_a.

Bước 3 : Thu thập snippet (Download snippets).

Việc phân biệt nhập nhằng tên dựa vào độ tương đồng ngữ cảnh. Việc tính độ

tương đồng dựa trên so khớp “term” là rất khó, vì các “term” có sự lặp lại rất ít. Ví dụ:

“term” “George Bush” và “term” “The president of the United States” dù gần nhau về

mặt ý nghĩa nhưng lại không có từ nào lặp lại trong nhau. Vì vậy hệ thống tính toán độ

tương đồng giữa 2 “term” sử dụng “snippet” được trả về bởi máy tìm kiếm.( “Snippet”

là một mẩu văn bản nhỏ, chứa 2 hay 3 câu được trích xuất từ văn bản cho câu truy

vấn, và thường đi kèm với các kết quả tìm kiếm của các máy tìm kiếm)

Ví dụ: với trường hợp của “George Bush” và “The president of the United States”,

trong số 5 “snippet” được trả về bởi máy tìm kiếm Google, có nhiều từ chung như

“President”, “White House”, “Official” , “and”, “site”. Đối với mỗi “term” ta xây

dựng phân bố (distribution) của các từ trong các “snippet” của “term”. Tần suất xuất

hiện mỗi từ được chia cho tổng số từ trong các “snippet”. Sau đó hệ thống tính toán độ

phân kỳ (divergence) KullBack-Liebler (KL), như độ đo tương tự giữa 2 “term”.

Với 2 phân bố xác suất p(x) và q(x) của biến xác suất ngẫu nhiên x

∈

X độ phân kỳ

KullBack-Liebler được định nghĩa như sau:

p(x)

D(p||q) =

p(x)log

(2.4)

∑

q(x)

x∈X

Trong đó X là tập từ vựng. KL-divergence sẽ trở nên không xác định khi có

những từ có xác suất bằng 0. “Skew divergence” S_α(p,q)được dùng để giải quyết vấn

đề này

S_α(p,q) = D(q||

α

p + (1 -

α

)q )

(2.5)

16

Trong đó α ⊂ [0,1] là mức độ thiên lệch giữa hai phân bố p và q. Để chuyển từ

“Skew divergence” bất đối xứng sang độ đo đối xứng sim(p,q) ta sẽ lấy giá trị phân tán

trung bình (average diverge):

1

sim(p,q) = exp(- (S_α(p,q) + S_α(q,p))

(2.6)

= 0.9

2

Trong phần cài đặt hệ thống lấy 100 “snippets” từ Google và

Bước 4: Tính toán độ tương đồng (Calculate similarity)

α

Lấy T(A) = {a₁, a ₂, a₃,…, a_n} là mô hình “term” cho văn bản A và T(B) = { b₁,

b₂, b₃,…, b _m} là mô hình “term” cho văn bản B. Ở đây a₁, a ₂, a₃,…, a _nlà các term

trích xuất từ văn bản A, và b₁, b₂, b₃,…, b _mlà các term trích xuất từ văn bản B.

Chúng ta định nghĩa độ tương đồng DocSim(A,B) giữa A và B sử dụng mô hình T(A)

và T(B) như sau:

1

sim (a ,b )

∑

i

j

DocSim(A,B) =

(2.7)

mn

a_i;b _j

a_i

∈

A , b_j

∈

B.

Ở đây sim(a_i, b_j) được tính ở công thức (2.6)

Bước 5 : Phân cụm văn bản :

Hệ thống sử dụng phương pháp phân cụm trung bình nhóm (Group-average

agglomerative clustering (GAAC)) để phân cụm các văn bản chứa tên xuất hiện. Đây

là phương pháp phân cụm phân cấp từ dưới lên. Ban đầu mỗi văn bản được gán là một

cụm riêng rẽ. GAAC tại mỗi vòng lặp trộn 2 cụm mới thỏa mãn cực đại hóa giá trị C

(2.8)

Trong đó |

Γ

| là số văn bản trong cụm và u, v là 2 văn bản trong cụm

Γ

.

Bước 5: Lựa chọn số cụm.

Trong trường hợp tốt nhất, chọn được số cụm bằng chính số người có trùng tên.

Tuy nhiên, số người là không biết trước nên bài toán tìm số cụm chuyển về bài toán tối

ưu hóa:

Cực đại hóa độ tương đồng các văn bản trong cụm.

Cực tiểu hóa độ tương đồng văn bản ở các cụm khác nhau.

Trong bài báo này tác giả cố gắng tìm số cụm để thỏa mãn 2 điều kiện trên bằng

độ đo liên kết trong cụm và độ tương tác ngoài.

Bước 6: Lựa chọn các “term” đại diện cho các cụm.

Thuận toán GAAC tạo ra một tập các cụm đại diện cho những người khác nhau.

Để lựa chọn từ khóa giúp nhận dạng một cách duy nhất cho mỗi người, đầu tiên hệ

thống sẽ lấy ra tất cả những “terms” trong mô hình “term” như là những từ khóa giúp

nhận diện duy nhất một người. Sau đó trong những “term” này lấy ra những “term” có

tính phân biệt cao nhất cho mỗi người. Quá trình được thực hiện qua 2 bước. Bước đầu

17

tiên sẽ giảm bớt số “term” trong môt cụm bằng cách bỏ những “term” mà nó cũng xuất

hiện trong cụm khác. Bước thứ hai, lựa chọn các term trong mỗi cụm dựa vào độ

tương đồng với tên được đưa vào tìm kiếm ban đầu, và lựa chọn những “term” có độ

tương đồng cao nhất.

2.3. Tiếp cận dựa trên kỹ thuật trích xuất thông tin

Năm 2003, S.Mann và David Yarowsky [13] giới thiệu một thuật toán không

giám sát hiệu quả để phân biệt nhập nhằng tên người. Phương pháp này dựa trên kỹ

thuật trích xuất thông tin sử dụng thuật toán không giám sát để sinh tự động mẫu trích

xuất của Ravichan và Hovy [11] và thuật toán phân cụm phân cấp. Việc sử dụng kỹ

thuật trích xuất thông tin giúp làm giàu đặc trưng cho người bằng các thuộc tính cá

nhân như : ngày sinh, nghề nghiệp, nơi làm việc, quốc tịch, nơi ở. Tác giả đã kết hợp

và so sánh kết quả của việc kết hợp các thuộc tính cá nhân và các đặc trưng khác như:

các từ trong văn bản, danh từ riêng, đặc trưng mở rộng.

Mô hình tác giả đưa ra gồm 2 pha chính:

Pha 1: Sử dụng kỹ thuật trích xuất thông tin để trích xuất các thuộc tính đặc

trưng mạnh cho người cần phân biệt.

Trong pha 1 chia làm 2 bước nhỏ:

Bước 1: Sinh mẫu trích xuất đặc trưng.

Hệ thống sử dụng và mở rộng phương pháp của Ravichan và Hovy [11]. Phương

pháp này dựa trên kỹ thuật boot-trapping, tự động sinh mẫu từ tập nhân mồi ban đầu.

Nó có lợi thế là không phụ thuộc vào ngôn ngữ (independent language) , vì vậy mà nó

rất khả chuyển có thể sinh mẫu cho các ngôn ngữ khác nhau với độ chính xác cao.

Ví dụ với tập nhân ban đầu là (‘Mozart’,1756)

Hệ thống sẽ sinh ra một truy vấn đưa vào máy tìm kiếm để tìm ra những câu

chứa cặp nhân trên. Ví dụ với máy tìm kiếm Altavista truy vấn là “Mozart”+ “1976.

Sau đó chỉ giữ lại nhưng câu chứa đủ cả cặp nhân.

Tất các các sâu con chứa cặp nhân này trong mỗi câu được lấy ra. Những sâu con

này được đơn giản hóa bằng cách thay các nhân bằng nhãn của nó. Trong trường hợp

này ta thay ‘Mozart’ bằng <name> và 1976 bằng <birth year>. Tất cả những chữ số

khác được thay bằng dấu #.

Từ tất cả các chuỗi này ta xây dựng nên cây hậu tố (suffix-tree), và chỉ giữ lại

những chuỗi con có tần xuất xuất hiện cao.

Với mỗi chuỗi con có tần số cao này lại lọc ra chỉ chọn những chuối chứa đủ tập

nhân ban đầu là ‘Mozart’ và 1756, khi đó chúng sẽ trở thành những mẫu tiềm năm.

18

Những mẫu tiềm năng được kiểm tra xem nó có thực sự đáng tin cậy hay không,

bằng cách áp dụng nó với các tập nhân khác, nếu kết quả vượt trên một ngưỡng nào đó

thì có thể coi là tin cậy.

Khi áp dụng mô hình trên hệ thống thu được các mẫu với quan hệ tên và ngày

ngày sinh:

Hình 7 - Các mẫu trích xuất sinh tự động cho ngày sinh

Hệ thống sử dụng phương pháp trên cho việc sinh mẫu tự động cho năm sinh và

nghề nghiệp và sinh mẫu bằng tay cho thông tin về nơi sinh, ngày sinh, quốc tịch, gia

đình, đồng nghiệp.

Bước 2: Áp dụng mẫu có được ở bước 1 để trích ra các đặc trưng quan trọng cho

người.

Pha 2: Sử dụng kỹ thuật phân cụm phân cấp dựa trên các đặc trưng có từ pha 1

chia các tài liệu thành các cụm, các tài liệu trong một cụm nói về một người duy

nhất.

Hệ thống sử dụng thuật toán phân cụm phân cấp từ dưới lên. Trong thuật toán

này, mỗi văn bản sẽ được coi như một vector của các đặc trưng trích chọn được từ văn

bản. Tại mỗi giai đoạn của quá trình phân cụm, 2 vector tương đồng nhất sẽ được trộn

19

lại với nhau tạo ra một cụm mới, và vector mới cho cụm đó tương đương với trung

bình của các vector trong cụm. Quá trình này tiếp tục cho đến khi chỉ còn 1 cụm duy

nhất. Vector đặc trưng cho mỗi văn bản được sinh ra theo những phương pháp sau:

• Baseline: Tất cả các từ hoặc chỉ danh từ riêng.

• Most Relevant words : Những từ liên quan nhất.

• Biographical features: Các thông tin đặc trưng hồ sơ người dùng.

• Extend Biographical features: Các thông tin đặc trưng mở rộng hồ sơ

người dùng.

- Với phương pháp Baseline, hệ thống sử dụng tất cả các từ trong văn bản (loại

bỏ từ dừng), hoặc chỉ danh từ riêng. Sau đó biểu diễn dưới dạng mô hình vector và độ

đo cosin để tính độ tương đồng.

- Với phương pháp dùng những từ liên quan nhất, hệ thống thử nghiệm cả việc

đánh trọng số của từ trong mô hình vector theo cả độ đo tf-idf và độ đo tương tác

thông tin (mutual information)

p

(

w

|

c

)

I(w;c) =

(2.9)

p

(

w

)

Trong đó c là tập hơn văn bản và w là từ cần đánh trọng số

Trọng số của từ trong mô hình vector là log(I(w;c))

- Với phương pháp dùng các thông tin đặc trưng hồ sơ người dùng, hệ thống

dùng phương pháp sinh mẫu trích xuất không giám sát để trích ra.

- Với phương pháp dùng thông tin đặc trưng mở rộng hồ sơ người dùng: đối với

những từ thỏa mãn mẫu trích xuất sẽ được gán trọng số cao hơn, ví dụ năm 1756 thỏa

mãn mẫu trích xuất về ngày sinh thì với các sự xuất hiện khác của 1976 sẽ được đánh

trọng số rất cao.

Khi phân cụm, hệ thống sử dụng những thông tin về người dùng như những hạt

giống để chia các cụm thành các nhóm. Tiếp theo dựa trên các đặc trưng còn lại, để

thực hiện phân cụm phân cấp từ dưới lên.

2.4. Một số cách tiếp cận khác

Năm 2005, Malin [16] đưa ra một cách giải quyết bài toán phân biệt nhập nhằng

tên người dựa trên lý thuyết đồ thị. Bài toán này áp dụng với cơ sở dữ liệu phim

Internet (Internet Movie Database – IMDB). Trong đó, tên của diễn viên được biểu

diễn bởi một đỉnh, và cặp nối giữa 2 đỉnh hay giữa 2 diễn viên biểu thị cho mối quan

hệ là họ đóng trong cùng một phim. Sau đó đồ thị này được sử dụng phân biệt các đỉnh

có cùng tên bằng cách phân tích những đỉnh hàng xóm của chúng.

20

Trong các bài báo của tác giả Elmacioglu [12] và Reema [17] các tác giả bổ sung

thêm những đặc trưng về liên kết cho việc tính tương đồng giữa ngữ cảnh nơi tên

người xuất hiện. Reema cho rằng nếu 2 trang Web chứa tên người thuộc cùng về một

domain thì khả năng cao là 2 tên đó cùng chỉ về một người, và loại trừ những trang

web thuộc về mạng xã hội vì chúng nằm ngoài giả định này. Elmacioglu biễu diễn các

liên kết bằng mô hình vector, trong đó mỗi liên kết là một chiều và trọng số được đánh

số theo phương pháp tf-idf. Trong hệ thống PNUS, Elmacioglu còn khai thác thêm

tính giàu thông tin của địa chỉ url theo phương pháp của hệ thống MeURL[17]. Ví dụ

địa chỉ url có dạng: “http://www.cs.ualberta.ca/~lindek/” tự nó gợi ý rằng đây là trang

chủ của tác giả Lindek tại ngành khoa học máy tính, đại học Alberta, Canada.

Tóm tắt chương hai

Trong chương hai, khóa luận giới thiệu chi tiết các phương pháp tiêu biểu trên

thế giới để 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. Các

phương pháp tập trung vào việc thể hiện ngữ cảnh nơi mà tên người và xuất hiện và đo

độ tương đồng giữa các ngữ cảnh này và cuối cùng là phân cụm ngữ cảnh hay phân

cụm văn bản chứa ngữ cảnh. Một điều dễ nhận thấy là các phương pháp này đều phụ

thuộc rất nhiều vào miễn dữ liệu để có được kết quả chính xác. Trong chương tiếp

theo, khóa luận sẽ tập trung vào việc khai thác những đặc trưng của miền dữ liệu khóa

luận thực hiện là các trang Web tin tức của các báo điện tử Việt Nam để xây dựng nên

ngữ cảnh tên người và đề xuất mô hình cho việc giải quyết nhập nhằng tên người trên

tập văn bản, ứng dụng của nó trong hệ thống tìm kiếm thực thể người.

21

Chương 3: Mô hình hệ thống phân biệt nhập nhằng tên người

3.1. Cơ sở thực tiễn

Như đã trình bày ở phần trên, mỗi phương pháp được đưa ra chỉ khả thi trên một

miền dữ liệu nhất định và phần lớn là trong ngôn ngữ tiếng Anh, chưa có một phương

pháp nào áp dụng trên nhiều miền dữ liệu. Vì vậy, việc nghiên cứu miền dữ liệu rất

quan trọng để đưa ra một phương pháp đúng đắn trên miền đó. Khóa luận này thực

hiện công việc phân biệt nhập nhằng tên người trên miền dữ liệu báo điện tử Việt

Nam, nên cần việc phân tích những đặc trưng về ngôn ngữ và hình thức của báo điện

tử là rất cần thiết. Ví dụ một bản tin về giáo sư “Nguyễn Hữu Đức”-Phó giám đốc đại

học Quốc Gia Hà Nội.

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”

Phương pháp của S.Mann và David Yarowsky [13] sử dụng việc sinh mẫu trích

xuất không giám sát để trích ra các thông tin quan trọng liên quan đến thực thể người

như ngày sinh, nơi sinh, nghề nghiệp…Rõ ràng là với miền dữ liệu báo điện tử Việt

Nam những thông tin như vậy là rất hiếm và việc sinh mẫu bắt được thông tin là không

hề đơn giản vì tính đa dạng cấu trúc của tiếng Việt. Phương pháp của Bagga và Breck

Baldwin [6], sử dụng khử đồng tham chiếu và xây dựng vector thực thể biễu diễn ngữ

cảnh của tên người, tuy nhiên có một số vấn đề là khi thực hiện trên miền dữ liệu báo

điện tử Việt Nam: thứ nhất là ngôn ngữ tiếng Việt chưa có một công cụ nguồn mở nào

cho việc thực hiện khử đồng tham chiếu, thứ hai là khi một người tham gia vào những

hoạt động khác nhau thì tập thực định danh thể biểu diễn ngữ cảnh của người đó cũng

rất khác nhau do đó nếu biễu diễn bằng mô hình vector thì vector sẽ bị thưa với nhiều

phần từ bằng 0 và độ tương đồng thấp, gây sai lệch kết quả.

Miền dữ liệu báo điện tử Việt Nam có một số đặc điểm phục vụ cho việc phân

biệt nhập nhằng tên người như sau:

22

Đặc trưng thứ nhất: Trong bài báo,thường có có một câu giới thiệu chi tiết đầy đủ

về thông tin một người ở phần đầu bài báo. Đây là những thông tin mang tính định

danh mạnh nhất cho một người nào đó, chúng rất có ý nghĩa trong việc phân biệt tên

người.

Hình 9 - Đoạn trích từ bài báo “Cá ngừ độc là do chứa histamin tự do”

Như ví dụ ở trên, chức danh và địa chỉ công tác của một người có tên là “Nguyễn

Hữu Đức” xuất hiện đầy đủ trên câu đầu tiên của bài báo.

Qua khảo sát 1000 trang Web, chúng tôi thấy đặc trưng trên xuất hiện rất phổ

biến trên miền dữ liệu báo chí điện tử.

Đặc trưng thứ hai: Một đặc trưng về mạng xã hội. Nếu hai bài báo chứa tên nhập

nhằng, mà có từ 2 tên người chung nhau (khác với tên nhập nhằng) trở lên thì khả

năng rất lớn là hai bài báo đó cùng nói về một người. Nó có thể hiểu như một dạng

quan hệ xã hội.

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