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ể - Nguyễn Đạo Thái

ĐẠ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 5.0 = 0.791 và F 2.0 = 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 1Mở đầ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 2ngườ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. 3Chươ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 sẽ nhận được kết quả như sau: 5Hì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] 6Hì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 7cá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 8Hì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 9Hình 1.6 – 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ể A B C A D E A D E B C P2P1 Hình 6 - Tổng hợp thông tin về người A từ 2 trang P1 và P2 10 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) 11 Độ 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. 12 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. 13 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: 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: 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”, Oliver “Biff” Kelly John Parry Massachusetts Golf Association Kelly John Parry Weston Golf Club Massachusetts Golf Association Woment’s Golf Association He Perry 14 ”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: 1S và 2S là 2 vector cho 2 bản tóm tắt được trích xuất từ các bài báo 1D và 2D , độ tương đồng của chúng được tính như sau: Sim( 1S , 2S ) = j t j ww j 21 * (2.1) Trong đó jt là thành phần chung của 2 vector 1S , 2S . jw1 là trọng số của jt trong 1S và jw2 là trọng số của jt trong 2S . Trọng số jt của vector Si được tính như sau: ijw = 22 2 2 1 .. log* inii sss df N tf  (2.2) Trong đó tf là tần số của jt trong 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 15 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 1 , t 2 ,… t N củ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: 16 (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 a là 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: D(p||q) =  Xx xq xp xp )( )( log)( (2.4) 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) C-value(a) = log 2 |a|*f(a) nếu a nằm trong “term” khác log|a|(f(a) -   aTba bf TP )( )( 1 ) trường hợp ngược lại 17 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): sim(p,q) = exp(- 2 1 (S (p,q) + S (q,p)) (2.6) Trong phần cài đặt hệ thống lấy 100 “snippets” từ Google và  = 0.9 Bước 4: Tính toán độ tương đồng (Calculate similarity) Lấy T(A) = {a 1 , a 2 , a 3 ,…, a n } là mô hình “term” cho văn bản A và T(B) = { b1 , b 2 , b 3 ,…, b m } là mô hình “term” cho văn bản B. Ở đây a 1 , a 2 , a 3 ,…, a n là các term trích xuất từ văn bản A, và b1 , b 2 , b 3 ,…, b m là 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: DocSim(A,B) = mn 1 ),( ; j ba i basim ji  (2.7) 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 18 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 và 1976 bằng . 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. 19 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 20 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) I(w;c) = )( )|( wp cwp (2.9) 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. 21 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: “” 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. 22 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: 23 Đặ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 24 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 Trong 2 bài báo trên, tên người “Nguyễn Hữu Đức” xuất hiện cùng 2 tên người khác là “Ngô Quang Thạch” và “Nguyễn Thị Tuyết”, và trong thực tế thì 2 bài báo này cùng nói về một người. 3.2. Cơ sở lý thuyết 3.2.1. Mô hình không gian vector Mô hình biểu diễn vector [1] là một mô hình truyền thống cho việc đo độ tương đồng giữa hai văn bản. Theo mô hình này, mỗi văn bản được biểu diễn bởi một không gian nhiều chiều, trong đó mỗi chiều tương ứng với một từ trong văn bản. Một từ với độ quan trọng được xác định bằng một phương pháp đánh chỉ số trong văn bản, và giá trị được chuẩn khóa trong khoảng [0,1]. Ví dụ hình mô tả hai văn bản d 1 và d 2 được biểu diễn bởi các vector v 1 và v 2 gồm ba chiều T 1 , T 2 , T 3 25 Một số phương pháp đánh trọng số cho từ trong văn bản: - Phương pháp dựa trên tần số từ khóa Giá trị của một từ khóa được tính dựa trên số lần xuất hiện của từ khóa (TF – Term Frequency) trong văn bản. Gọi tf ij là tần số xuất hiện của từ khóa t i trong văn bản d j khi đó có thể tính trọng số w ij theo một trong các công thức dưới đây: w ij = ijtf (3.1) w ij = 1 + log(tf ij ) (3.2) w ij = tf ij (3.3) - Phương pháp dựa trên nghịch đảo tần số văn bản (IDF – Inverse Document Frequency ) Gọi df i là số lượng văn bản có chứa từ khóa t i trong tập m văn bản đang xét, thì giá trị của tần số từ được tính bởi công thức: w ij = log ( idf m ) = log(m) – log(df i ) (3.4) Phương pháp này được giải thích dựa trên lập luận rằng một từ xuất hiện trong nhiều văn bản thuộc tập văn bản D thì không quan trọng bằng một từ xuất hiện trong ít văn bản thuộc tập D, nghĩa là một từ quá thông dụng sẽ có độ quan trọng kém hơn một từ chỉ xuất hiện trong một văn bản hoặc một tập nhỏ các văn bản. - Phương pháp TFIDF T2 T3 T1 v1 v2  Hình 12 - Biểu diễn văn bản trong không gian vector. 26 Phương pháp này là tổng hợp của hai phương pháp TF và IDF, giá trị của ma trận trọng số được tính như sau: (3.5) 3.2.2. Thuật toán phân cụm HAC Khái niệm về bài toán phân cụm: Phân cụm dữ liệu là một kỹ thuật trong khai phá dữ liệu, nhằm đưa ra các cụm mà các phần tử trong cùng một cụm có độ tương đồng cao và các phần tử thuộc các cụm khác nhau lại có độ tương đồng thấp. Bài toán phân cụm thường được thực hiện khi chúng ta không biết được nội dung thông tin của các thành phần thuộc cụm để định nghĩa trước các lớp. Vì lý do này mà công việc phân cụm thường được truyền thống nhìn nhận dưới con mắt của học máy không giám sát, phương pháp học mà khi ta cho trước một mẫu chỉ gồm các đối tượng cần tìm một cấu trúc đáng quan tâm của dữ liệu và nhóm lại các dữ liệu giống nhau. . Hình 13 - Quy trình phân cụm Một số phương pháp phân cụm cơ bản:  Phân cụm phân hoạch (phân cụm phẳng): Phương pháp này chia tập gồm n phần tử thành tập k tập con rời nhau, trong đó k cho trước. Với phương pháp này, ban đầu người ta khởi tạo một phân hoạch ban đầu cho tập dữ liệu theo một phép gán ngẫu nhiên hoặc dựa trên một phương pháp kinh nghiệm (hueristic), sau đó tinh chỉnh lại các cụm cho đến khi thu được một phân hoạch mong muốn thỏa mãn một ràng buộc cho trước . Tại mỗi bước thuật toán phân cụm cố w ij = [1 + log(tf ij )] log( ijtf m ) nếu tf ij > 0 0 nếu tf ij = 0 27 gắng cải tiến chất lượng phân cụm bằng cách tính độ đo tương tự giữa các đối tượng dữ liệu và sắp xếp các giá trị này, sau đó thuật toán lựa chọn một giá trị trong dãy sắp xếp sao cho hàm tiêu chuẩn đạt giá trị tối thiểu. Thuật toán tiêu biểu cho phương pháp này là K-Means. Ví dụ về thuật toán K-means: Hình 14 - Ví dụ về thuật toán K-means  Phân cụm dữ liệu dựa trên mật độ: Phương pháp này dựa vào mật độ của các đối tượng để xác định các cụm dữ liệu và có thể tìm ra các cụm dữ liệu với hình thù bất kỳ. Trong phương pháp phân cụm này, khi một cụm dữ liệu đã được xác định thì nó tiếp tục phát triển thêm các đối tượng mới miễn là các đối tượng lân cận của đối tượng này phải lớn hơn một ngưỡng về mật độ cho trước. Tuy nhiên việc xác định trước các tham số mật độ của thuật toán là rất khó khăn, trong khi các tham số này có ảnh hưởng quan trọng đến chất lượng phân cụm. Thuật toán tiêu biểu cho phương pháp phân cụm này là DB-Scan. Hình dưới đây là một số hình ảnh ví dụ về phân cụm dựa trên mật độ. Hình 15 - Hình vẽ minh họa cho phân cụm dữ liệu dựa trên mật độ.  Phân cụm phân cấp Phương pháp phân cụm cây phân cấp xây dựng một cấu trúc cây phân cấp cho các tài liệu, và có hai phương pháp chính là xây dựng cây theo hướng từ trên xuống (top-down) và xây dựng theo hướng từ dưới lên (bottom-up). Với phương pháp 28 bottom-up, đầu tiên mỗi phần tử được coi như một cụm phân biệt và sau đó tiến hành ghép lần lượt 2 cụm giống nhau nhiều nhất hay khác nhau ít nhất làm một đến khi tất cả các cụm được ghép vào một cụm duy nhất chứa tất cả các phần tử. Phân cụm phân cấp bottom-up được gọi là hierachical agglomerative clustering (HAC). Hình vẽ minh họa cho thuật toán HAC: Hình 16 - Sơ đồ các phân tử trước khi phân cụm Hình 17 - Sơ đồ các phần tử sau khi phân cụm phân cấp Còn với phân cụm phân cấp top-down, trạng thái ban đầu là tất cả các đối tượng thuộc vào cùng một cụm. Tại mỗi vòng lặp thành công, một cụm được tách thành các cụm nhỏ hơn theo giá trị của một phép đo độ tương tự nào đó cho đến khi mỗi đối tượng là một cụm, hoặc cho đến khi điều kiện dừng thỏa mãn. Cách tiếp cận này sử dụng chiến lược chia để trị trong quá trình phân cụm. Chi tiết về HAC Thuật toán HAC cho phân cụm Web[2] Tham số: 29 G là tập hợp các cụm. S là tập các phân hợp các trang Web cần phân cụm. k là tham số để dừng thuật tóan khi số lượng cụm mong muốn đã được tạo ra. q là tham số ngưỡng dừng thuật toán khi độ tương tự giữa 2 cụm nhỏ hơn một ngưỡng nào đó. 1. G <- {{d} | d thuộc S } (Khởi tạo G là tập các cụm chỉ gồm một trang Web trong tập S) 2. Nếu |G| < k thì dừng thuật toán ( Đã được số lượng cụm mong muốn ). 3. Tìm 2 cụm Si và Sj thuộc G sao cho (i,j) = arg max(i,j) sim (Si,Sj) ( Tìm 2 cụm có độ tương tự lớn nhất ). 4. Nếu sim(Si,Sj) < q thì dừng thuật tóan ( độ tương tự của 2 cụm nhở hơn ngưỡng cho phép ) 5. Loại bỏ Si,Sj khỏi G 6. G = G hợp { Si , Sj } (ghép 2 cụm Si,Sj và đưa vào trong tập G ) 7. Nhảy đến bước 2 Một số độ đo khoảng cách trong thuật toán HAC: - Single link hay Single-linkage: Với phương pháp này, khoảng cách giữa các cụm được định nghĩa là khoảng cách giữa những đối tượng giống nhau nhất giữa 2 cụm: D(r,s) = min(d(i,j)) (3.6) Trong đó: r,s là 2 cụm. i,j là 2 đối tượng bất kỳ thuộc 2 cụm r,s. Với 2 cụm, ta tính tất cả các khoảng cách giữa 2 phần tử bất kỳ thuộc 2 cụm đó và khoảng cách nhỏ nhất tìm được chính là khoảng cách giữa 2 cụm đó. Tại mỗi bước, 2 cụm gần nhau nhất sẽ được chọn để ghép lại với nhau. 30 Hình 18 - Phân cụm với Single-linkage - Complete-link: Với 2 cụm, ta tính tất cả các khoảng cách giữa 2 phần tử bất kỳ thuộc 2 cụm đó và khoảng cách lớn nhất tìm được chính là khoảng cách giữa 2 cụm đó. Tại mỗi bước, 2 cụm gần nhau nhất sẽ được chọn để ghép lại với nhau. D(r,s) = max(d(i,j)) (3.7) Trong đó: r,s là 2 cụm. i,j là 2 đối tượng bất kỳ thuộc 2 cụm r,s. Hình 19 - Phân cụm với Complete-linkage - Group average agglomerative Phương pháp phân cụm GAAC tính độ tương tự trung bình SIM-GA của tất cả các cặp văn bản khi ghép tất cả các văn bản của hai cụm vào làm một, trong đó bao gồm cả những cặp thuộc cùng một cụm. 31 Hình 20 - Trung bình các khoảng cách trong GAAC (3.8) Trong đó N i là số văn bản của cụm i , N j là số văn bản của cụm j ,  d là vector đã được chuẩn hóa của văn bản d. 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 Đầu vào: Tập các tên người. Đầu ra: Tập các trang Web tin tức chứa tên người đó được phân cụm, sao cho những trang Web thuộc cùng một cụm cùng đề cập tới một người, và các trang Web thuộc các cụm khác nhau đề cập tới những người khác nhau. Phương pháp giải quyết và mô hình ` Hình 3.12 – Bước 1 : Thu thập dữ liệu Tên người Thu thập dữ liệu Tập các trang Web chứa tên người Tiền xử lý Văn bản qua xử lý Trích chọn đặc trưng Ngữ cảnh cho tên người Tính độ tương đồng ngữ cảnh Ma trận tương đồng Phân cụm ngữ cảnh Tập các văn bản phân cụm theo người Hình 21 - Mô hình giải quyết bài toán phân biệt nhập nhằng trên tập văn bản 32 Với mỗi tên người, chúng tôi thu thập các trang tin tức chứa chúng từ ba Website tin tức: vnexpress.net, dantri.com.vn và vietnamnet.vn thông qua máy tìm kiếm Google. Truy vấn “tên người”+site:domain được đưa vào máy tìm kiếm Google để lấy ra các kết quả phù hợp cho mỗi domain. Ví dụ: Thu thập các bài báo liên quan tới tên “Nguyễn Hữu Đức” trong website vnexpress.net ta sử dụng truy vấn “Nguyễn Hữu Đức” + site:vnexpress.net Với các kết quả có được, chúng tôi lọc lấy những trang văn bản dạng html, bỏ qua các văn bản đính kèm đuôi .doc hay .xls. Bước 2: Tiền xử lý  Loại bỏ thẻ HMTL, lấy nội dung chính của từng trang Web.  Tách câu, tách từ trên dữ liệu thu được. Bước 3: Trích chọn đặc trưng  Chọn lấy những câu chứa tên người đó trong văn bản.  Trích ra đặc trưng mạng xã hội: Xác định các thực thể tên người khác cũng xuất hiện trong văn bản đó. Bước 4:Tính độ tương đồng ngữ cảnh Thử nghiệm 2 phương pháp: Phương pháp 1: Coi toàn bộ các câu chứa tên người là một văn bản, loại bỏ từ dừng và biểu diễn dưới dạng mô hình vector. Với một tên người, để thu được các câu chứa tên người đó, ta biến đổi tên bằng cách loại bỏ các từ trong tên từ trái sang phải và tìm các câu chứa các tên đã bị cắt. Ví dụ với tên “Nguyễn Ngọc Minh” , ta sẽ tìm những câu chứa các từ “Nguyễn Ngọc Minh”, “Ngọc Minh” và “Minh”. Độ tương đồng ngữ cảnh được tính bằng độ đo cosin giữa 2 vector, đánh trọng số của từ theo phương pháp tf. Phương pháp 2: Với mỗi sự xuất hiện của các tên riêng, chúng tôi lấy độ rộng xung quanh cửa sổ là 10 làm ngữ cảnh cho tên, gọi là một đoạn, chỉ lấy những đoạn chứa đầy đủ tên. Thực hiện so khớp từng đoạn chứa tên người của văn bản này với các đoạn chứa tên người của văn bản kia để tìm ra các từ, cụm từ chung. Hai đoạn của hai văn bản có nhiều cụm từ chung nhất được đại diện cho tên người đó trong mỗi văn bản, và các cụm từ chung trong 2 đoạn đó được tính điểm như sau: Nếu có 2 cụm từ a 1 và a 2 ,trong đó a 1 chứa a 2 thì chỉ lấy a 1 . 33 Với mỗi từ đơn chung đứng riêng ta tính 1 điểm cho độ tương đồng, nếu có một cụm n từ đơn liên tiếp nhau thì độ tương đồng tính bằng công thức Point( n-word ) = n + log 2 (n)/2 (3.9) Trong đó n-word là một cụm gồm n từ liên tiếp. Trong cả 2 phương pháp ta đều bổ sung thêm đặc trưng mạng xã hội có từ việc xác định các thực thể tên người trong văn bản ở bước trên như sau:  Nếu 2 văn bản có từ 2 thực thể người chung trở lên thì ta coi chúng là tương đồng hoàn toàn.  Nếu 2 văn bản có 1 thực thể người chung, ở phương pháp 1 ta nhân độ tương đồng với hệ số k = 1.5, ở phương pháp 2 ta coi tên đó cũng là 1 từ chung bình thường và tính điểm tương tự như các từ chung khác. Đầu ra của bước này chính là ma trận độ tương đồng [w ij ] trong đó w ij là độ tương đồng của văn bản i với văn bản j. Bước 5: Phân cụm ngữ cảnh  Sử dụng thuật toán phân cụm HAC với khoảng cách single-linkage dựa trên ma trận độ tương đồng ngữ cảnh.  Sử dụng ngưỡng  để cắt cây phân cấp HAC tìm ra được số cụm, tương ứng là số người phân biệt có cùng tên. 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 Tập tên người Module thu thập văn bản và phân biệt nhập nhằng tên người trên tập văn bản Tập trang Web ứng với từng người Trích xuất các đặc trưng cho mỗi người CSDL về người 34 Hệ thống gồm 2 bước chính: Bước 1: Tập tên người sẽ được cho qua “Module thu thập văn bản và phân biệt nhập nhằng tên người trên tập văn bản” để thu được một tập trang Web tương ứng với từng người riêng biệt. Bước này đã được trình bày chi tiết ở hệ thống phân biệt nhập nhằng tên người trên tập văn bản ở phần trước. Bước 2: Trích xuất đặc trưng cho mỗi người. Trong bước 1, với mỗi tên người và tập các trang Web tương ứng với người đó khóa luận đã trích xuất đặc trưng là tập các thực thể người có liên quan đến người đó và các cụm từ chung đại diện cho người. Các đặc trưng này sẽ được lưu vào trong cơ sở dữ liệu để phục vụ cho quá trình tìm kiếm sau này. Tóm tắt chương ba Trong chương ba, 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. Trong chương tiếp theo, khóa luận tiến hành thực nghiệm trên mô hình đã xây dựng và đánh giá những kết quả đạt được của mô hình đề xuất. 35 Chương 4. Thực nghiệm và đánh giá Dựa vào cơ sở lý thuyết và mô hình đề xuất ở chương 3, khóa luận tiến thành thực nghiệm 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ử. 4.1. Môi trường và các công cụ sử dụng thực nghiệm. Cấu hình phần cứng Thành phần Chỉ số CPU 2.2 GHz Core Duo Intel RAM 2 GB OS WindowsXP Service Pack 2 Bộ nhớ ngoài 160GB Các phần mềm sử dụng STT Tên phần mềm Tác giả Nguồn 1 Eclipse-SDK- 3.4.1-win32 oads 2 vnTokenzier Lê Hồng Phương, Nguyễn Thị Minh Huyền ols/vnTokenizer.php Ngoài ra các công cụ trên, chúng tôi tiến hành cài đặt các module xử lý dựa trên ngôn ngữ Java, bao gồm các package chính như sau: Thuật toán phân cụm HAC: Chỉnh sửa và tùy biến một số chức năng trong chương trình của tác giả Roberto Perdisci [19] (chương trình thực hiện thuật toán HAC với các khoảng cách single-link 36 và complete-link cho phần mềm Weka3). Chương trình ban đầu của Perdisi có đầu vào là một tập văn bản biểu diễn dưới dạng vector, sau khi chỉnh sửa chương trình thao tác trên ma trận tương đồng ngữ cảnh. Chương trình gồm các package: Cluster.alogrithm : Cài đặt thuật toán HAC cho các khoảng cách “single-link” và “complete-link” Cluster.data: Bao gồm các cấu trúc dữ liệu tạo thuận lợi cho việc cài đặt thuật toán HAC (DistanceMatrix.java, Hcluster.java, IndexPair.java, Dendrogram.java, ClusterIndexPair.java ) 4.2. Xây dựng tập dữ liệu Do chưa có một bộ dữ liệu test chuẩn cho bài toán này, nên chúng tôi đã đưa ra 15 tên người có độ nhập nhằng cao trên môi trường Web để đánh giá phương pháp. Tập dữ liệu mà trên đó chúng tôi thực hiện công việc phân biệt nhập nhằng tên người là miền dữ liệu báo chí điện tử lấy từ 3 trang Web: vnexpress.net, dantri.com, vietnamnet.vn. Bảng tập tên người thực nghiệm mô hình Tên người Số thực thể người Số tài liệu Nguyễn Hữu Đức 5 30 Nguyễn Văn Tuấn 6 30 Nguyễn Văn Sơn 10 30 Nguyễn Văn Thành 7 30 Nguyễn Ngọc Minh 6 30 Nguyễn Minh Tuấn 8 30 Trần Văn Tuấn 5 30 Nguyễn Văn Hải 7 30 Nguyễn Văn Hùng 5 30 Trần Văn Phương 6 30 Nguyễn Văn Đức 7 30 Nguyễn Minh Hà 7 30 Nguyễn Trung Hiếu 7 30 Nguyễn Thu Thủy 6 30 Nguyễn Thị Hạnh 5 30 3 37 Đối với tập dữ liệu thu được từ máy tìm kiếm Google, chúng tôi chỉ giữ lại những trang có tên người nằm ở phần nội dung chính của trang, và loại bỏ những trang có tên nằm ở phần bình luận hoặc tác giả bài viết. 4.3. Thực nghiệm Thực nghiệm phân biệt nhập nhằng tên người trên tập văn bản. Quá trình tiền xử lý:  Tiến hành loại bỏ thẻ HTML, lấy nội dung chính của trang.  Tiến hành tách câu, tách từ bằng phần mềm vnTokenizer [20].  Loại bỏ từ dừng (tập từ dừng có trong file stoplist.txt) . Trích chọn đặc trưng:  Lọc lấy những câu chứa tên người.  Xác định thực thể tên người có trong văn bản:  Xác định tập tên riêng sử dụng phần mềm vnTokenizer [20].  Sử dụng tập luật để xác định tên riêng nào là tên người, sử dụng 2 bộ từ điển các từ tiền tố trước tên người và tiền tố không tên người oBộ từ điển từ tiền tố trước tên người: “ông” , “bà” , “chị” , “cô” , “dì” , “chú” , “bác”, “cụ” , “anh” , “em” , “hắn” , “tên” … oBộ từ điển từ tiền tố không đứng trước tên người: “chợ” , “đường” , “phố” , “quận” , “huyện” , “xã” , “thôn” , “tỉnh” , “bệnh viện” …. Thuật toán phân cụm HAC: Đối với phương pháp 1, qua quá trình khảo sát thực nghiệm chúng tôi chọn  = 0.1 làm ngưỡng để cắt cây phân cụm, còn phương pháp 2 giá trị ngưỡng là  = 3.5 Bảng kết quả thực nghiệm. Đặc trưng Purity Inverse Purity F 5.0 F 2.0 PP1 0.707 0.673 0.689 0.679 PP1 + đặc trưng mạng xã hội 0.731 0.708 0.719 0.712 PP2 0.792 0.722 0.755 0.735 PP2 + đặc trưng mạng xã hội 0.825 0.761 0.791 0.773 38 Bảng kết quả từ khóa, và thực thể người liên quan với tên “Nguyễn Hữu Đức” Từ khóa Tên người Hiệu trưởng, GS, TS, ĐHCN Nguyễn Ngọc Bình, Nguyễn Văn Hiệu, Phạm Bảo Sơn… Tiến sỹ, đại học, y dược, TPHCM Đạo diễn, miền đồi ấm áp, con chung, mùa báo bão, gia đình thợ mỏ Đàm Hằng Trưởng phòng, đầu tư, xây dựng Ngô Quang Thạch, Nguyễn Thị Tuyết, Lê Hoài Chương… Tổ chức, đánh bạc, BLHS Võ Thị Kim Hương, Trương Văn Cam, Nguyễn Văn Thọ… Nhận xét: Phương pháp 1: Trong tính toán độ tương đồng có một số trường hợp sau ảnh hưởng đến kết quả tính toán. Việc tách câu của phần mềm Vntokenizer trong một số trường hợp chưa chính xác, dẫn đến việc xây dựng vector đặc trưng chưa thật chính xác. Khi cùng một người tham gia các hoạt động thuộc lĩnh vực khác nhau thì độ lặp nội dung trong các câu là thấp dẫn đến độ tương đồng thấp, trong những trường hợp dưới ngưỡng dẫn đến kết quả sai vì coi đó là 2 người khác nhau. Ngược lại, 2 người khác nhau tham gia hoạt động trong cùng một lĩnh vực, trong trường hợp độ tương đồng vượt ngưỡng cũng dẫn đến kết quả sai vì coi đó là cùng một người. Phương pháp 2: Phương pháp 2 sử dụng có độ chính xác cao hơn phương pháp 1, điều này phù hợp với đặc trưng đầu tiên đã nêu trong phần cơ sở thực tiễn rằng: các thông tin định danh mạnh cho người thường tập trung ở xung quanh phần tên đầy đủ, phương pháp 2 lấy cửa sổ với độ rộng 10 xung quanh tên đầy đủ, còn phương pháp 1 lấy tất cả các câu chứa cả tên đầy đủ hoặc chỉ tên không. 39 Với những người tương nổi tiếng trong âm nhạc thể thao, bài báo thường không kèm theo thông tin định danh mạnh về người đó nên với việc sử dụng phương pháp 2 không thực sự hiệu quả. Ví dụ trong trường hợp của tên “Nguyễn Ngọc Minh” có một ca sỹ tương đối nổi tiếng thì kết quả của Purity và Inverse Prity tương ứng chỉ là 0.72 và 0.69 Việc sử dụng viết tắt khác nhau cho cùng một tên cũng làm tỉ lệ trùng lặp giảm xuống, làm sai lệch kết quả. Ví dụ cùng một tên “Đại học Quốc Gia Hà Nội” có một số cách viết tắt Đại học QGHN” , “ ĐHQGHN”…hoặc chức danh ví dụ như “tiến sỹ” có viết tắt là “ts” , “giáo sư” là “gs”….. Trong rất nhiều trường hợp, một người tham gia các lĩnh vực khác nhau và những đặc trưng ở mỗi trang để giúp nhận ra đó chỉ là một người là quá ít. Rõ ràng điều này khó có thể khắc phục được bằng các thuật toán không giám sát vì không có một tri thức đầy đủ và toàn diện về người đó để phân biệt và ghép nối các thông tin. Ví như như trong hai bài báo dưới đây cùng nói về giáo sư tiến sỹ Nguyễn Hữu Đức, với những thông tin trong bài báo thì chưa đủ để biết được đó làm một người, chúng ta phải có một tri thức về người đó thì mới vượt qua được vấn đề này. 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 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 Việc bổ sung thêm đặc trưng về mạng xã hội (các thực thể người khác xuất hiện trong ngữ cảnh) làm tăng độ các chỉ số cho các kết quả, nó khắc phục được một số trường hợp việc lấy ngữ cảnh quanh tên ở phương pháp 1 và 2 thiếu sót. Điều này 40 cũng hoàn toàn dễ hiểu, như đã trình bày ở phần cơ sở thực tiễn, việc trích chọn ra các tên người khác thể hiện cho ngữ cảnh là những đặc trưng tiêu biểu cho mối quan hệ xã hội của một người. 41 Kết luận Kết quả đạt được của khóa luận Trong khóa luận này, chúng tôi đã khảo sát miền dữ liệu báo điện tử tiếng Việt để đề xuất phương pháp phân biệt tên người trên tập văn bản sử dụng hai độ đo dựa trên đặc trưng về vùng trọng tâm thông tin và mạng xã hội. Những phương pháp này có ưu điểm là không cần sử dụng quá nhiều các tài nguyên về xử lý ngôn ngữ tự nhiên và dễ cài đặt. Tuy nhiên vấp phải hạn chế là chưa tận dụng được hết các đặc trưng tốt khác xuất hiện trong toàn bộ văn bản, và việc so khớp từ vẫn còn nhiều vấn đề như: từ viết tắt, các từ nghề nghiệp nên có trọng số cao hơn… Chúng tôi cũng đã cài đặt, thử nghiệm ban đầu trên một tập nhỏ tên người có độ nhập nhằng cao và cho kết quả khá tốt Dựa trên kết quả của 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 tôi đề xuất mô hình hệ thống tìm kiếm thực thể người dựa trên bài toán phân biệt nhập nhằng tên. Tuy nhiên hệ thống tìm kiếm là một bài toán lớn gồm nhiều thành phần phức tạp, do thời gian có hạn nên khóa luận chưa thực hiện được một hệ thống hoàn chỉnh. Định hướng tương lai Thử nghiệm bổ sung các từ điển về từ viết tắt và danh từ nghề nghiệp để tăng chất lượng cho việc phân biệt nhập nhằng. Kết hợp thêm một số đặc trưng về thực thể định danh ,siêu liên kết và các độ đo tương đồng cho ngữ cảnh tên người. Xây dựng được một hệ thống tìm kiếm thực thể với quy mô nhỏ. 42 Tài liệu tham khảo Tiếng Việt [1] Hà Quang Thụy, Phan Xuân Hiếu, Đoàn Sơn, Nguyễn Trí Thành, Nguyễn Thu Trang, Nguyễn Cẩm Tú. Giáo trình khai phá dữ liệu Web, Nhà xuất bản giáo dục Việt Nam, 2009, tr. 124-125. [2] Hà Quang Thụy, Phan Xuân Hiếu, Đoàn Sơn, Nguyễn Trí Thành, Nguyễn Thu Trang, Nguyễn Cẩm Tú. Giáo trình khai phá dữ liệu Web, Nhà xuất bản giáo dục Việt Nam, 2009, tr. 197-200. [3] Trần Nam Khánh. Some studies on a probabilistic framework for finding object-oriented information in unstructured data, undergraduate thesis, College of Technology, VietNam National Univeristiy, Hanoi,2009 [3] [4] [5] Tiếng Anh [6] A. Bagga, and B. Baldwin. 1998. Entity-Based Cross-Document Coreferencing Using the Vector Space Model. COLING-ACL'98. [7] Breck Baldwin, Mike Collins, Jason Eisner, Adwait Ratnaparkhi, Joseph Rosenzweig, Anoop Sarkar: University of Pennsylvania: description of the University of Pennsylvania system used for MUC-6. MUC 1995: 177-191 [8] Bekkerman, R., McCallum, A. (2005), "Disambiguating web appearances of people in a social network", Proceedings of the 14th Conference on World Wide Web, Chiba, Japan, May 10-14, ACM Publications, New York, NY, pp.463-70. [9] Bollegala, D., Matsuo, Y., Ishizuka, M. (2006), "Disambiguating personal names on the web using automatically extracted key phrases", Proceedings of the 17th European Conference on Artificial Intelligence, Riva del Garda, Italy, 28 August-1 September, IOS Press, Amsterdam. [10] Brin S., Page L. (1998), "The anatomy of a large-scale hypertextual web search engine", Proceedings of the 7th World Wide Web Conference, Brisbane, Australia, pp.107-17. [11] D. Ravichandran and E. Hovy. 2002. Learning surface text patterns 43 for a question answering system. In Proceedings of the40th Annual Meeting of the Association for ComputationalLinguisti. [12] E. Elmacioglu, Y. F. Tan, S. Yan, M.-Y. Kan, and D. Lee. PSNUS: Web people name disambiguation by simple clustering with rich features. In Proceedings of the Fourth International Workshop on Semantic Evaluations (SemEval-2007), pages 268--271, 2007. [13] Gideon S. Mann and David Yarowsky. Unsupervised personal name disambiguation. In Proceedings of CoNLL-7, pages 33–40, 2003. [14] K.T. Frantzi and S. Ananiadou, Extracting nested collocations, in 16th Conference on Computational Lingustics, pp. 41–46, (1996). [15] K.T. Frantzi and S. Ananiadou, The c-value/nc-value domain independent method for multi-word term extraction, Journal of Natural LanguageProcessing, 6(3), 145–179, (1999). [16] Malin, B. (2005), "Unsupervised Name Disambiguation via Social Network Similarity," in Proceedings of the 2005 SIAM Workshop on Link Analysis, Counterterrorism, and Security, Newport Beach, CA, pp. 93-102. Min-Yen Kan and Hoang Oanh Nguyen Thi. 2005. Fast webpage classification using URL features. In CIKM, pages 325–326, October/November. [17] Reema Al-Kamha and David W. Embley, 2004. Grouping search-engine returned citations for person-name queries. In Proceedings of the 6th annual ACM international workshop on Web information and data management, pages 96–103. [18] Tao Cheng, Xifeng Yan, Kevin Chen-Chuan Chang. EntityRank: Searching Entities Directly and Holistically. In VLDB 2007: Proceedings of the 33rd international conference on very large data bases. Công cụ sử dụng [19] Roberto Perdisci, Implementation of single and complete-linkage hierarchical clustering. [20] Lê Hồng Phương (2009), “vnTokenizer, an automatic tokenizer for tokenization of Vietnamese texts”