Tài liệu 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 WWW World Wide Web 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ị WebPS1, 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/ 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 Cazoodle2 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/ 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 A D E A P1 D P2 E A B Hình 1.6 – C 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 (semisupervised 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) Trong đó: Độ chính xác ứng với cụm C i với mỗi mục L j được định nghĩa như sau: Precision (C i , L j ) = | C i  L j | / | C i | (1.3) Độ đo F được tính theo công thức: (1.4) Hệ thống thường sử dụng  = 0.5 và  = 0.2. Tóm tắt chương một 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: Weston Golf Club John Parry 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: Oliver “Biff” Kelly John Parry Massachusetts Golf Association 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