Khóa luận Phương pháp học gần không giám sát để trích chọn thực thể tên tổ chức - Vũ Quốc Đạt

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Vũ Quốc Đạt PHƯƠNG PHÁP HỌC GẦN KHÔNG GIÁM SÁT ĐỂ TRÍCH CHỌN THỰC THỂ TÊN TỔ CHỨC 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 - 2009 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Vũ Quốc Đạt PHƯƠNG PHÁP HỌC GẦN KHÔNG GIÁM SÁT ĐỂ TRÍCH CHỌN THỰC THỂ TÊN TỔ CHỨC 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: TS. Nguyễn Trí Thành HÀ NỘI – 2009 Lời cảm ơn Trước tiên em muốn gửi lời cảm ơn sâu sắc nhất đến thầy giáo, TS. Nguyễn Trí Thành, người đã giúp em chọn đề tài, đưa ra những nhận xét quý giá và trực tiếp hướng dẫn giúp em hoàn thành luận văn tốt nghiệp. Em xin chân thành cảm ơn các thầy cô giáo trong khoa CNTT- Trường Đại học Công Nghệ - ĐHQG Hà Nội đã truyền đạt kiến thức cho em trong suốt thời gian học tập tại trường. Trong suốt thời gian làm khóa luận, em đã nhận được nhiều sự giúp đỡ, động viên từ gia đình, thầy cô và bạn bè. Em xin gửi lời cảm ơn tới những người bạn của em, luôn bên cạnh em để chia sẽ những kiến thức, kinh nghiệm học tập cũng như trong cuộc sống. Cuối cùng, em xin gửi lời cảm ơn sâu sắc nhất tới gia đình của mình, nguồn động viên và cổ vũ lớn lao, và là động lực giúp em thành công trong công việc và trong cuộc sống. Sinh viên Vũ Quốc Đạt Tóm tắt nội dung Trích chọn thông tin là lĩnh vực quan trọng trong khai phá dữ liệu, trong đó trích chọn thực thể là một bài toán con, cơ bản nhưng đóng vai trò hết sức quan trọng. Nó có thể được sử dụng để hỗ trợ cho phương pháp tìm kiếm mới – tìm kiếm hướng thực thể, và góp phần quan trọng cho việc xây dựng web ngữ nghĩa. Có nhiều phương pháp tiếp cận khác nhau cho bài toán trích chọn thực thể như phương pháp học máy HMM, … Trong khóa luận này em trình bày một phương pháp để trích chọn thực thể tên tổ chức tiếng Việt trong văn bản tiếng Việt trên môi trường Web. Phương pháp này dựa trên ý tưởng của Sergey Brin mà cụ thể hơn là thuật toán DIPRE trong việc trích chọn cặp quan hệ tên sách và tác giả của những cuốn sách tiếng Anh trên môi trường Web. Ưu điểm của phương pháp này là cần ít sự can thiệp của con người, không cần sự hỗ trợ của các ứng dụng phụ như xác định từ loại (POS – tag). Kết quả thực nghiệm trên các văn bản tiếng Việt cho thấy phương pháp này tương đối khả quan. Mục lục Bảng từ viết tắt Từ hoặc cụm từ Viết tắt Dual Iterative Pattern Relation Expansion DIPRE Mô hình Markov ẩn HMM Mở đầu Trích chọn thực thể là bài toán đơn giản nhất trong các bài toán trích chọn thông tin. Tuy cơ bản nhưng lại đóng vai trò khá quan trọng, như hỗ trợ các hệ thống tóm tắt văn bản tự động, ứng dụng cho máy tìm kiếm hướng thực thể … Bài toán trích chọn thực thể tên tiếng Việt đã được nghiên cứu vài năm gần đây, có nhiều phương pháp giải quyết được đưa ra với những kết quả thu được tương đối khả quan. Trong khóa luận này, em đưa ra một phương pháp mới “học gần không giám sát” để áp dụng cho bài toán trên. Tuy nhiên, trong phạm vi của khóa luận này em chỉ thực hiện rút trích một loại thực thể đó là thực thể tên tổ chức. Luận văn được chia thành 4 chương: Chương 1 Giới thiệu qua về trích chọn thông tin và bài toán trích chọn thực thể tên tổ chức cũng như ý nghĩa của nó. Chương 2 trình bày hướng tiếp cận để giải quyết bài toán. Chương đưa ra 3 bài toán rút trích các cặp quan hệ hệ khác nhau trên tập tài liệu (quan hệ , , ). Ý tưởng chính của các bài toàn này là dựa vào thông tin ngữ cảnh của đối tượng cần rút trích để biểu diễn chúng dưới dạng mẫu (pattern), từ mẫu này rút trích ra đối tượng. Bài toán cơ bản nhất là của Brin – rút trích cặp quan hệ . Kỹ thuật quay vòng được áp dụng để rút trích thực thể, dựa vào thuật toán DIPRE. Vòng lặp sau sử dụng kết quả của vòng lặp trước làm đầu vào. Các thực thể lần lượt được rút trích ở mỗi vòng, kết thúc vòng lặp khi thỏa mãn điều kiện dừng đã cho. Mỗi bài toán đưa ra đều có cách biểu diễn mẫu riêng, phù hợp với ngữ cảnh của từng quan hệ cần rút trích.Từ bài toán của Pasca nãy ra ý nghĩ về một phương pháp học gần không giám sát để áp dụng cho bài toán trong khóa luận này. Hệ thống Snowball độc đáo với cách biểu diễn pattern và phương thức đánh giá chất lượng của thực thể thu được. Chương 3 trình bày mô hình tổng quát và các bước chi tiết của bài toán rút trích thực thể tên tổ chức. Mô hình tổng quát dựa trên bài toán của Brin về rút trích cặp quan hệ , đặc biệt là kỹ thuật DIPRE. Tuy nhiên, điểm xuất phát ban đầu giống với bài toán của Pasca – xuất phát là patterns. Với cách xuất phát này thì có thể giảm được số vòng lặp thực hiện. Chi tiết các bước thực hiện là: Ban đầu cho một mẫu (pattern) để đoán nhận tiền tố tên tổ chức; ước lượng một xâu (được kỳ vọng là có chứa tên thực thể) ngay sau tiền tố đó; cắt tỉa xâu trên thu được tên thực thể; chọn lọc những thực thể đại diện từ tập thực thể thu được; ánh xạ ngược thực thể đại diện vào dữ liệu để tìm xâu tiền tố; sinh ra các pattern mới từ tập xâu tiền tố đó; tiếp tục vòng lặp mới… Chương cũng trình bày thuật toán sinh pattern từ cho tiền tố của thực thể; cuối cùng là đưa một số nhập nhằng trong cách biểu diễn tên, từ đó xây dựng chiến lược cắt tỉa để thu được tên hợp lý. Chương 4 là phần thực nghiệm. Dữ liệu chuẩn bị, môi trường thực nghiệm và kết quả thực nghiệm. Chỉ đưa ra một số kết quả thực nghiệm đại diện để thể hiện tính chất của bài toán. CHƯƠNG 1. SƠ LƯỢC BÀI TOÁN TRÍCH CHỌN THỰC THỂ TÊN TỔ CHỨC Tổng quan về trích chọn thông tin Với sự bùng nổ của Internet và các phương tiện lưu trữ đã tạo ra một lượng thông tin khổng lồ. Bên cạnh đó nhu cầu về tốc độ xử lý thông tin, cũng như tính chính xác ngày càng tăng. Do đó bài toán đặt ra đối với các nhà nghiên cứu là tìm ra những phương pháp mới, hiệu quả cho việc xử lý thông tin đáp ứng nhu cầu sử dụng. Hiện nay, các máy tìm kiếm (search engine) thực hiện việc tìm những trang web phù hợp với yêu cầu câu hỏi người dùng. Tuy nhiên bởi vì đối tượng tác động của nó là trang Web trong hệ thống tài liệu, nên miền tri thức nó thu được đôi khi không đủ để đáp ứng yêu cầu tìm kiếm của người dùng. Vẫn còn tiềm ẩn những giá trị trong các câu, bộ phận của trang Web. Do đó khai thác được những tri thức đó sẽ mang lại nhiều thông tin bổ ích. Đó là lĩnh vực mà “trích chọn thông tin” nghiên cứu. Trích chọn thông tin là một lĩnh vực quan trọng trong khai phá dữ liệu, thực hiện việc rút trích ra thông tin có cấu trúc từ tập tài liệu thô – không có cấu trúc. Không giống như hiểu toàn bộ văn bản, các hệ thống trích chọn thông tin chỉ cố gắng nhận biết một số thông tin đáng quan tâm ở một lĩnh vực nào đó. Hay nói một cách khác, cho một mẫu (template) bao gồm các trường thực thể, quan hệ thực thể …., hệ thống trích chọn thông tin có nhiệm vụ phân tích tài liệu thô để tìm ra thông tin thích hợp điền vào các trường tương ứng trong mẫu đó. Ví dụ về hệ thống trích chọn thông tin : Hình 1 : Hệ thống trích chọn thông tin Hệ thống trên thực hiện rút trích ra bộ ba quan hệ từ tập tài liệu web và bổ sung các bản ghi 3 trường đó vào cơ sở dữ liệu. Bài toán rút trích thực thể tên tổ chức Tổ chức là một trong những đối tượng cơ bản xuất hiện trong văn bản, đặc biệt là trong các website về kinh tế, xã hội, thế giới… Cùng với sự phát triển của thương mại điện tử, sự toàn cầu hóa …nên nhu cầu tìm hiểu về các tổ chức Việt Nam cũng như thế giới là vấn đề đáng được quan tâm. Rút trích tên tổ chức là liệt kê ra danh sách tên các tổ chức xuất hiện trong văn bản. Bài toán rút trích tên thực thể (mà cụ thể ở khóa luận này là bài toán trích chọn thực thể tên các tổ chức) là bài toán cơ bản trong các bài toán trích chọn thông tin. Bởi vì trước khi khai phá được các tri thức về thuộc tính, tính chất của các thực thể, thì đầu tiên chúng ta phải rút trích ra được chính xác tên của thực thể đó. Tuy nó là bài toán cơ bản, nhưng tồn tại rất nhiều vấn đề nhập nhằng làm cho việc rút trích gặp khó khăn. Đặc biệt với ngôn ngữ tiếng Việt, đa dạng trong cách viết, đôi khi nhập nhằng về ngữ pháp, và chưa có một chuẩn nào cụ thể về chữ hoa, chữ thường cho tên tiếng Việt cũng như xuất hiện nhiều từ “thừa” chỉ mang tính chất liệt kê, bổ nghĩa ... Có nhiều phương pháp được áp dụng cho bài toán rút trích tên thực thể như phương pháp học máy HMM [4] … Trong khóa luận này, em sử dụng phương pháp “học gần không giám sát“ dựa trên thuật toán DIPRE và ý tưởng rút trích cặp quan hệ (author, title) của Brin [7], kết hợp các luật hỗ trợ để rút trích thực thể tên tổ chức. Tuy nhiên, có một hạn chế là thuật toán DIPRE thường áp dụng cho bài toán rút trích cặp quan hệ như (tên sách, tên tác giả), (tổ chức, trụ sở chính của tổ chức) …., còn nội dung khóa luận này chỉ là trích chọn thực thể đơn – tên tổ chức. Nhưng lợi thế của DIPRE là tính tự động (automatic), cần ít thao tác thủ công của con người, có thể áp dụng trong miền dữ liệu lớn. Hơn thế nữa tên các tổ chức thường có “quan hệ” nào đó với các “tiền tố” đứng liền nó. Đấy là những tiền đề để áp dụng kỹ thuật DIPRE vào bài toán trong khóa luận này. Các chương tiếp theo sẽ đề cập chi tiết hơn. Ý nghĩa của bài toán rút trích thực thể tên tổ chức Một hệ thống rút trích các loại thực thể hiểu quả có thể có nhiều ứng dụng trong thực tế: Hỗ trợ xây dưng Web ngữ nghĩa. Xây dựng các máy tìm kiếm hướng thực thể. Ví dụ với từ khóa “Washington“ có thể trả về những trang web nói về vị tổng thống đầu tiên nước Mỹ, hoặc về thành Phố Washington – thủ đô nước Mỹ, hoặc về một công ty nào đó… Do đó thời gian tiềm kiếm sẽ giảm đi khi có sự trợ giúp của hệ thống trích chọn thực thể. Hỗ trợ hệ thống tóm tắt văn bản tự động. ….. Bài toán rút trích thực thể tên tổ chức trong khóa luận này đưa ra chỉ là bài toán cơ bản, chưa có ứng nhiều trong thực tế. Mới chỉ dừng lại ở mức là làm giàu thông tin cho dữ liệu. Tuy nhiên nó là cơ sở để phát triển bài toán phức tạp hơn, hữu ích hơn. CHƯƠNG 2. HƯỚNG TIẾP CẬN BÀI TOÁN TRÍCH CHỌN THỰC THỂ Học máy là hướng tiếp cận phổ biến nhất cho bài toán trích chọn thực thể. Bài toán trong khóa luận sẽ tiếp cận theo một cách khác. Chương này sẽ giới thiệu một số bài toán điển hình đã được thực nghiệm để rút trích cặp quan hệ, từ đó có thể rút ra ý tưởng áp dụng cho bài toán rút trích thực thể tên tổ chức. Rút trích cặp quan hệ (title, author) của cuốn sách trong tài liệu web Nhận thấy rằng thông tin trên WWW không phải chỉ ở dạng thô, mà chúng còn tiềm ẩn những quan hệ, cấu trúc nào đó. Nếu khai phá được những đặc tính đó thì sẽ rất hữu ích cho việc xử lý thông tin. Segrey Brin đã đưa ra một ý tưởng là rút trích ra các cặp “title, ” và “author” của cuốn sách. Đặc điểm của cặp được rút trích này là chúng có quan hệ với nhau – tên sách và tên tác giả viết cuốn sách. Điểm nổi bật trong nghiên cứu này là thuật toán DIPRE sẽ được trình bày dưới đây. Đầu tiên giới thiệu một số khái niệm có trong bài toán, sau đó sẽ đưa ra quy trình rút trích tổng quát và chi tiết các thuật toán sử dụng trong bài. Occurrences của sách Occurrences của cuốn sách được hiểu là thông tin về sự “xuất hiện” của cuốn sách (gồm title và author) trên tập dữ liệu. Để thuận tiện cho việc xử lý, Brin biểu diễn occurrences của cuốn sách là một bộ gồm 7 trường: (author,title,order,url,prefix,middle,suffix) order : Thứ tự xuất hiện của author và title. url : Địa chỉ trang web mà nội dung có chứa author, title . prefix : Xâu ký tự đứng trước author hay title (tùy theo thứ tự của author, title) middle : Xâu nằm giữa author và title. suffix : Xâu đứng sau author hay title. Patterns của sách Patterns sẽ được “ánh xạ” ngược vào tập tài liệu để rút trích ra tập quan hệ mới (ở đây là “title” và “author”). Patterns được “sinh ra” từ tập các Occurrences ở trên theo một tiêu chí, quy tắc nào đó (sẽ được trình bày ở dưới). Patterns có ý nghĩa quan trọng trong việc rút trích. Patterns tốt sẽ tăng số lượng cũng như chất lượng tìm kiếm, rút trích. Patterns cho những cuốn sách sách là một bộ gồm 5 trường (order,urlprefix,prefix,middle,suffix) order : Giống ở Occurrences Một cặp (author, title) được rút trích nếu có một URL trên web hợp (matchs) với urlprefix* và nội dung của nó có chứa đoạn hợp với biểu thức chính quy “*prefix, author, middle, title, suffix*” , đồng thời khi đó biến order = true. Biểu thức chinh quy cho author và title lần lượt là: [A-Z][A-Za-z .,&]5;30[A-Za-z.] [A-Z0-9][A-Za-z0-9 .,:'#!?;&]4;45[A-Za-z0-9?!] Quy trình rút trích Quy trình rút trích dựa theo thuật toán DIPRE. Ý tưởng là: Bắt đầu bằng mẫu nhỏ R’ – tập 5 cuốn sách và tên tác giả tương ứng. Mẫu này được thao tác trực tiếp bằng tay. OßFindOccurrences(R’;D) Tìm tất cả “sự xuất hiện của các bộ (author, title) của R’ trong D. Ứng với mỗi bộ tìm thấy, ghi nhớ lại url và text xung quanh (ở giữa, 2 bên) “author” và “title”. PßGenPatterns(O)Dựa vào tập xuất hiện của cặp (author,title) để sinh ra mẫu (pattern). Mẫu sinh ra phải không được quá riêng biệt, hay quá chung chung thì mới là mẫu tốt. R’ßMD(P)Từ những pattern xây dựng được, tìm kiếm trên CSDL những bộ (tuples) mà hợp với mẫu đó. Nếu R’ đủ lớn thì kết thúc. Ngược lại nhảy về bước 2 Kỹ thuật trên có thể được mô tả như hình dưới đây : Hình 2: Quy trình rút trích Thuật toán sinh Patterns Như đã trình bày trong mục trên, thủ tục GenPatterns có nhiệm vụ sinh ra các patterns dựa vào các occurrences. Nó là một quy trình quan trọng trong DIPRE. Giả sử chúng ta có một bộ occurrences , và sẽ “thử” dựng nên một pattern từ bộ đó. Khi đã có thủ tục sinh ra 1 pattern, thì thủ tục sinh tất cả các patterns có thể cũng sẽ tương tự, như được trình bày dưới đây : Sinh một Pattern Các bước cho thủ tục GenOnePattern(O) – sinh 1 pattern như sau: Cần phải chắc chắn rằng order và middle của tất cả sự xuất hiện (occurrences) phải giống nhau. Nếu không thì không thế sinh ra được pattern để match với tất cả occurrences. Đặt outpattern.order và outpattern.middle tương ứng với order và middle. Tìm đoạn prefix dài nhất của các urls mà chúng giống nhau. Đặt outpattern.urlprefix = prefix Đặt outpattern.prefix là xâu dài nhất của các prefixs mà chúng giống nhau tính từ cuối (suffix) của các tiền tố (prefixs) đó. Đặt outpattern.suffix là xâu dài nhất của các suffix mà chúng giống nhau tính từ đầu (prefix) của các hậu tố (suffixs) đó. Kết quả thu được một pattern. Sinh tập Patterns Thuật toán cho GenPatterns(O) dựa vào thuật toán GenOnePattern(O) đã được giới thiệu ở trên : Nhóm tất cả sự xuất hiện (occurrences) o trong O theo order và middle. Được kết quả các nhóm O1 , …, Ok. Với mỗi Oi , p ß GenOnePattern( Oi). Nếu p thoả mãn điều kiện về độ “riêng biệt” thì nhận p đưa ra ngoài. Nếu không: Nếu tất cả occurrences o trong Oi có chung url thì bỏ Oi. Ngược lại : Tách các occurrences o trong Oi thành những nhóm con dựa vào đặc điểm urls của chúng – qua p.urlprefix. Lặp lại thủ tục ở bước 2 cho những nhóm con này. Ý tưởng của thủ tục sinh patterns như trên là chia nhỏ urls khi patterns sinh ra không đủ “riêng biệt”. Như thế thì cũng có thể sử dụng kỹ thuật chia nhỏ theo prefix hay suffix. Tất cả trên chỉ là những giải pháp cơ bản, để có được 1 kỹ thuật tốt hơn thì cần phải nghiên cứu thêm. Tuy nhiên kết quả mà kỹ thuật vừa đưa ra cũng có một kết quả thực nghiệm chấp nhận được. Thu thập tên và miền tương ứng từ tập tài liệu web Con người, thời gian, địa điểm…là những thực thể cơ bản trong văn bản dù ở bất cứ ngôn ngữ nào. Nhưng với từng “chuyên ngành” hay lĩnh vực riêng thì vẫn tồn tại rất nhiều thực thể và miền của thực thể đó. Ví dụ như miền “Universities” có các thực thể “Harvard”, “Cambridge” …., hay miền “Programming” có “C++, Java …”. Nếu rút trích được các cặp tên miền và thực thể (C, N) rồi tích hợp vào các hệ thống như WordNet [1] thì sẽ tạo ra cơ sở tri thức hữu ích. Dựa trên DIPRE, Marius Pasca đưa ra một mô hình để thu được cặp (C,N) từ tài tập liệu web [6]. C và N tương ứng viết tắt cho Category và named Entity ( miền và tên thực thể). Pattern được sử dụng có dạng : [StartOfSent] X [such as|including] N [and|,|.] Ở đây X là một “categorical fact” tạm hiểu nó là một xâu mà được coi là có chứa miền C. N là “potential instance name” tạm hiểu là thực thể cần tìm thuộc miền C. Một đặc điểm để nhận dạng N đó là nó là một danh từ riêng nên thường được viết hoa. Ánh xạ pattern này vào tài liệu sẽ thu được cặp (X,N). Ví dụ như câu sau : “That is because software firewalls, including Zone Alarm, offer some semblance of this feature”. Cặp (X,N ) thu được là (That is because software firewalls, Zone Alarm). Cuối cùng, từ X rút trích ra cụm danh từ thỏa mãn là miền C của N. Nó được ước lượng là cụm danh từ không đệ quy phải nhất, sao cho thành phần cuối cùng của nó là một danh từ số nhiều. Như ví dụ câu trên, sẽ rút trích được cụm danh từ “software firewalls” nó chính miền C . Chiến lược ước lượng này tuân theo một số quy tắc : Nếu không có cụm danh từ dạng số nhiều nằm gần cuối của “categorical fact”, thì cặp (X, N) bị loại bỏ. Một cụm danh từ dạng số nhiều nằm gần cuối của “categorical fact” nhưng ngay trước nó cũng là một cụm danh từ số nhiều, thì cặp (X, N) bị loại bỏ. Trường hợp còn lại thì (X, N) là phù hợp và thu được cặp (C,N). Bảng dưới đây mô tả kết quả áp dụng các quy tắc nói trên: Bảng 1: Sự lựa chọn cateogries từ cateogrical facts Categorical fact and instance name Selection Anti-GMO food movements sprouted up Discard in European nations in the 1990s, including Germany Discard Our customers’ chipsets compete with Discard products from other vendors of standardsbased and ADSL chipsets, including Alcatel Discard The venture is supported by a number of academics, including Noam Chomsky Retain (academics, Noam Chomsky) API Adapter can be written in other programming languages such as C++ Retain (programming languages,C++) Để tăng số lượng cặp (C, N) rút trích được, mô hình đưa ra phương thức để “tự động” sinh ra những patterns mới. Bằng cách “ánh xạ” những cặp (C, N) đã được rút trích ở vòng lặp trước vào dữ liệu. Ý tưởng được mô tả như trong hình dưới : Hình 3: Rút trích Patterns mới Mỗi pattern có dạng: LeftContext, InnerPattern và RightContext là dãy những phần tử liên tiếp trong câu. Pattern chỉ đoán nhận các xâu trong từng câu riêng biệt hay nói cách khác mỗi pattern “nằm” hoàn toàn trong 1 câu. Trong thực nghiệm này LeftContext, RightContext được biểu diễn theo dạng từ loại (POS –tag ) bởi Penn Treebank [5]. Kết quả xếp hạng top 15 patterns được liệt kê như bảng bên dưới: Bảng 2 : Phân hạng các Pattern rút trích được LeftContext (POS tags) InnerPattern (words) RightContext (POS tags) StartOfSent Such asb , NNP NNP , NNP , NNP , NNP , and othera . EndOfSent IN NNP , NNP , and othera . EndOfSent StartOfSent such asb . EndOfSent StartOfSent such asb , NNP , NNP , StartOfSent , includingb , NNP , NNP , NNP StartOfSent IN such asb , NNP NNP , NNP StartOfSent DT includeb , NNP , NNP , StartOfSent , includingb CC NNP NNP NNP NNP NNP , NNP NNP , and othera . EndOfSent StartOfSent JJ , includingb CC NNP NNP , VBP StartOfSent JJ , includingb , NNP NNP CC NNP StartOfSent DT areb , NNP , NNP , Nhìn vào bảng trên ta thấy, ngoài việc tìm lại được” các InnerPaterns mồi là “such as” và “including” thủ tục trên còn “khám phá” ra những InnerPatterns hữu ích khác như “and other”, “include” và “are”. Những patterns mới này lại được sử dụng để rút trích thực thể cho vòng lặp tiếp theo. Hệ thống Snowball Cũng dựa trên tư tưởng của DIPRE, Eugene Agichtein và Luis Gravano đã xây dựng hệ thống Snowball [3] để rút trích cặp quan hệ (organization, location) – tổ chức và địa điểm. Biểu diễn mối quan hệ một tổ chức organization có trục sở đặt tại địa điểm location. Snowball đã đưa ra một kỹ thuật mới để sinh patterns và rút trích cặp quan hệ từ tài liệu. Snowball cũng có thêm chiến lược đánh giá chất lượng của mỗi patterns và cặp quan hệ, nếu cái nào đủ tin cậy thì mới được sử dụng cho các vòng lặp tiếp theo. Tuy nhiên Snowball cần đến sự hỗ trợ của NER (Named Entity Recognition). Mô hình của Snowball được biểu diễn như dưới : Hình 4: Hệ thống Snowball Sinh patterns Với mỗi cặp organization-location Snowball xác định nó trong tập tài liệu và phân tích các thành phần trái (left), giữa (middle) và phải (right) để sinh pattern. Pattern của Snowball là một bộ 5 thành phần : Trong đó tag1, tag2 là các thẻ tên thực thể (cụ thể ở đây là và ) và left, middle, right là các vector liên kết “terms” và “weights”. (terms là xâu tùy ý hoặc kí tự trống, weights – trọng số biểu thị độ quan trọng của terms). Mỗi vector các terms có trọng số weights nằm trong khoảng từ 0 đến 1. Trọng số càng lớn thì độ ưu tiên của term đó càng cao. Ví dụ : }, LOCATION, { , }, ORGANIZATION, {}> Để sinh pattern, đầu tiên Snowball tìm tất cả sự xuất hiện (occurrences) của các bộ , biểu diễn dưới dạng giống như dạng của các pattern. Mỗi thành phần left, middle, right có một giới hạn m terms. Trọng số của mỗi term xác định dựa theo tần số của các terms trong ngữ cảnh tương ứng. Từ tập các occurrences, sử dụng thuật toán phân cụm đơn giản [8] để phân thành các cụm . Với mỗi cụm, các vector left được biểu diễn bằng vector trung tâm l’s , tương tự biểu diễn các vector middle, right bằng các vector trung tâm m’s, r’s . Ví dụ từ tập các occurrences : Sẽ được phân thành 2 cụm : Tính toán vector trung tâm của mỗi cụm, thu được các patterns : Sinh cặp quan hệ Trước hết định nghĩa độ phù hợp của hai bộ tP = (t1, t2 là các thẻ) tS = (t’1, t’2 là các thẻ) theo công thức : Sau khi sinh được các patterns, Snowball quét tập tài liệu để tìm ra những cặp (o, l) mới. Dùng MITRE Corporation’s Alembic Workbench [2] để nhận dạng những câu có chứa một organization và location. Phân tích nội dung xung quanh nó và sinh ra 1 bộ 5 trường t = theo quy tắc giống ở trên. Gọi cặp là cặp “ứng cử viên” nếu có một pattern tp thỏa mãn Match(t, tp) >= tsim (tsim là ngưỡng). Mỗi một cặp “ứng cử viên” được sinh bởi các patterns ứng với từng “độ phù hợp” (như giá trị Match(t , tp) trên ). Và mỗi một pattern cũng có một độ đo tính “chọn lọc” của nó. Snowball sẽ sử dụng hai thông số này để quyết định cặp “ứng cử viên” nào là thích hợp. Tổng kết chương Chương đã đưa ra 3 bài toán để rút trích các cặp quan hệ khác nhau. Rút trích cặp quan hệ (title, author) là bài toán cơ bản nhất, kỹ thuật biểu diễn pattern và occurrence đơn giản, thuật toán để sinh pattern từ occurrence cũng không phức tạp. Độc đáo nhất ở bài toán là thuật toán DIPRE. Bài toán của Pasca xuất phát là một pattern “mồi”, với cách thực hiện này hệ thống có thể rút trích được một lượng lớn cặp quan hệ ở vòng lặp đầu tiên, do đó sẽ có nhiều patterns mới được sinh ra cho vòng lặp tiếp theo. Với cách thực hiện này, thuật toán có thể sẽ phải thực hiện số vòng lặp ít hơn. Tuy nhiên nó cần sự hỗ trợ của POS - tag ( thẻ từ loại ) để biểu diễn pattern, đối với tiếng Việt thì vẫn chưa xây dựng được POS –tagger (gán nhãn từ loại ) hoàn chỉnh. Hệ thống Snowball độc đáo với cách biểu diễn pattern mềm dẻo , cộng với sự hỗ trợ của thẻ tên thực thể (NER) nên có kết quả thu được tốt nhất. Tuy nhiên chỉ “học “ được ở Snowball chiến lược đánh giá pattern và cặp thực thể thu được để áp dụng vào khóa luận, còn để biểu diễn được pattern thì cần sự hỗ trợ của NER – trong khi bài toán trong khóa luận này bản chất chính là xây dựng NER. CHƯƠNG 3. TRÍCH CHỌN TÊN CÁC TỔ CHỨC Chương này sẽ luần lượt trình bày từ mô hình tổng quát đến các bước chi tiết của bài toán trích chọn. Dựa trên các bài toán ở chương 2, em sử dụng phương pháp “học gần không giám sát” kết hợp sự hỗ trợ của các luật để giải quyết bài toán của mình. Các bài toán đã trình bày ở chương 2 là rút trích các cặp quan hệ, còn mục tiêu của khóa luận này là rút trích tên các tổ chức – đơn, nên khi áp dụng tư tưởng của các bài toán đó vào bài toán trích chọn tên các tổ chức, cần có sự thay đổi về dạng biểu diễn pattern và cách thức rút trích tên thực thể từ các pattern đó… Mô hình tổng quát Bài toán dựa trên bài toán của Sergey Brin về việc tìm ra cặp quan hệ (tên sách, tên tác giả) của cuốn sách, đặc biệt là kỹ thuật DIPRE. Cứ sau mỗi vòng lặp lại sinh ra những cặp thực thể mới và mẫu (patterns) mới. Các vòng lặp tiếp theo sử dụng kết quả của vòng lặp trước đó để thu được kết quả mới. Quá trình đó cứ tiếp tục quay vòng cho đến khi đạt được một yêu cầu đưa ra. Sergey Brin cho xuất phát bằng 5 cặp thực thể (tên sách, tên tác giả), từ cặp thực thể đó tìm ra sự xuất hiện (occurrences ) của chúng trên tài liệu Web và từ đó đưa ra quy tắc để sinh mẫu (pattern). Mỗi tập mẫu thu được lại tiếp tục tìm ra cặp thực thể (title, author) mới… Với bài toán của chúng ta, ở mức tổng quát gồm các bước: Xuất phát là một mẫu được xây dựng thủ công; Rút trích ra các thực thể tên tổ chức trong tập tài liệu web dựa vào mẫu đó “Ánh xạ” lại các thực thể vừa rút trích được vào tập tài liệu web để xác định sự xuất hiện (Occurrences) của chúng trên tài liệu. Sinh mẫu mới từ Occurrences đó. Quay lại bước thứ nhất với mẫu vừa được sinh ra Do xuất phát không phải là tập các thực thể “mồi” mà là một mẫu, nên có thể rút trích được số lượng lớn các thực thể ngay ở vòng lặp đầu tiên, số lượng mẫu mới sinh ra cho vòng lặp tiếp theo cũng lớn… Điều đó giúp cho chương trình giảm được số lần thực hiện vòng lặp. Chương trình dừng lại khi độ chính xác của các thực thể rút trích được thấp dưới một ngưỡng cho phép. Quy trình rút trích được mô tả như hình dưới đây : Hình 5: Mô hình tổng quát Có một điểm khác biệt giữa thực thể mà Brin rút trích với kiểu thực thể của chúng ta. Đó là Brin rút trích theo cặp thực thể quan hệ, cụ thể ở đây là cặp (tên sách, tên tác giả) của cuốn sách. Chúng có quan hệ là với mỗi cuốn sách sẽ có tên sách và tác giả viết ra cuốn sách đó. Do vậy cách biểu diễn nó trên tài liệu sẽ có một quy luật nào đó. Còn bài toán của chúng ta chỉ là rút trích ra tên thực thể đơn – tên tổ chức. Tuy nhiên, thường thì “tiền tố” của tên các tổ chức ở một dạng nhất định, trên một miền nhất định. Và có một đặc điểm thuận lợi nữa là tên tổ chức thường ở dạng kí tự đầu tiên của mỗi từ là viết hoa hoặc không thì từ cuối cùng của tên thường có ký tự đầu viết hoa ... Chính vì vậy, mấu chốt của bài toán là tìm ra đặc điểm của xâu ký tự bên trái (“ tiền tố “) của mỗi tên thực thể để sinh ra pattern hợp lý, và đưa ra những quy tắc cắt tỉa thích hợp, loại bỏ những trường hợp ngoại lệ thu để được tên hợp lý. Trong mô hình Snowball, mỗi một cặp quan hệ được đánh giá dựa theo số lượng các pattern sinh ra nó, cũng như “tính chọn lọc” của mỗi pattern. Chỉ những cặp nào có độ đánh giá phù hợp thì mới được sử dụng như kết quả của qúa trình rút trích. Bài toán trong khóa luận này áp dụng ý tưởng đó cho việc sinh ra các patterns thích hợp dựa vào tập các thực thể liên quan. Chi tiết sẽ được trình bày ở mục tiếp theo. Mô hình chi tiết Tổng quát cho ý tưởng bài toán được mô tả như hình trên, trong mục này sẽ biểu diễn chi tiết hơn về các bước hoạt động của chương tình. Do sự khác nhau về kiểu đối tượng cần rút trích, nên cách biểu diễn pattern và cách thức rút trích thực thể dựa vào pattern cũng thay đổi. Các bước thực hiện được mô tả như hình bên dưới :  Hình 6. Mô hình bài toán Các thủ tục trên được diễn giải như sau : Input: PrefixPattern (Initial) – Xuất phát là một mẫu được xây dựng thủ công IndexsOfPrefixPattern ß Find_IndexsOfPrefixPattern (PrefixPattern) Ánh xạ PrefixPattern vào tập tài liệu để xác định các xâu mà mẫu này đoán nhận (PrefixStrings) và các vị trí tương ứng của chúng (IndexsOfPrefixPattern) trong mỗi file tài liệu. CandidateStrings ß Extract_CandidateStrings (IndexsOfPrefixPattern, PrefixStrings, CandidateRegularExpression) Biểu thức chính quy CandidateRegularExpression đoán nhận các xâu trong tập tài liệu từ các vị trí xuất phát trong mỗi file là (IndexsOfPrefixPattern + chiều dài của PrefixStrings tương ứng). Entities ß Trim (CandidateStrings) Thực hiện “cắt tỉa” CandidateStrings để thu được các thực thể (Entities) thích hợp. RepresentativeEntities ß Filter_Entities ( Entities ) Từ Entities chọn ra những thực thể đại diện. PrefixStrings ß Find_PrefixStrings(RepresentativeEntities, PrefixRegularExpression) Sử dung biểu thức chính quy PrefixRegularExpression kết hợp với RepresentativeEntities để đoán nhận “tiền tố” của các RepresentativeEntities (PrefixStrings). NewPrefixPattern ß Generate_NewPrefixPattern ( PrefixStrings ) Từ PrefixStrings sinh ra các mẫu mới. Quy lại bước 1 (vòng lặp mới ) với NewPrefixPattern vừa được sinh ra. Các mục dưới đây sẽ giải thích rõ ràng hơn. Find_IndexsOfPrefixPattern Để rút trích được một thực thể, cần phải biết được ngữ cảnh xung quanh nó. Ở bài toán này chỉ quan tâm đến “tiền tố” (prefix) của nó. Bởi vì đứng trước mỗi một thực thể tên tổ chức thường là các “tiền tố” có dạng đặc biệt, hoặc nằm trong miền giá trị cụ thể. Ví dụ như thường là : “Tổ chức, công ty, tập đoàn, phòng ….”. Còn đứng sau mỗi tên tổ chức thường không có một quy tắc nào xác định. PrefixPattern là biểu thức chính quy được dùng để đoán nhận các “tiền tố” đó. Đầu vào ban đầu của chương trình là PrefixPattern (Initial) được xây dựng bằng tay. PrefixPattern có dạng : PrefixPattern = (A1|A2|A3 …An) Nghĩa là PrefixPattern có thể là A1 hoặc là A2 … hoặc An. Trong đó A1, A2 … An là một từ, cụm từ tiếng Việt nào đó thể hiện tiền tố của tên tổ chức được xác định ban đầu (nằm trong file cấu hình). Ví dụ : PrefixPattern = (tổ chức|công ty|phòng). Thủ tục Find_IndexsOfPrefixPattern với tham số đầu vào PrefixPattern sẽ tìm các xâu khớp (match) với PrefixPattern ,kết quả thu được là các xâu “tiền tố” PrefixStrings và các vị trí của chúng IndexsOfPrefixPattern. Ví dụ nếu trong văn bản có đoạn “Thông tin Tổng công ty Hàng không Việt Nam thua kiện ở châu Âu … “, với PrefixPattern như trên (tổ chức|công ty|phòng) thì ánh xạ vào văn bản thu được PrefixString là “công ty” còn IndexOfPrefixPattern nhận giá trị là vị trí của xâu “công ty” (tức vị trí ký tự “c”) trong văn bản tính từ đầu file – nếu đoạn trên nằm ở đầu file thì IndexOfPrefixPattern là 15. Extract_CandidateStrings Ứng với mỗi xâu “tiền tố” xác định được ở bước trên, thì xâu con đứng ngay sau nó “được mong đợi” sẽ là một tên thực thể nào đó. Nhưng không có một quy tắc chính nào cho tên của các tổ chức, cũng như không xác định được độ dài số từ (word) của nó là bao nhiêu. Hướng tiếp cận để giải quyết vấn đề này là ước lượng xâu con đứng ngay sau mỗi “tiền tố” (số lượng từ tùy chọn), từ xâu đó đưa ra các quy tắc “cắt tỉa” để thu được tên mong đợi. CandidateRegularExpression là biểu thức chính quy được dùng để đoán nhận xâu con đó. Nó có dạng : ([ |: ][\\-&a-zA-Z0-9à-ỵÀ-Ỵ]+){n,m} Nghĩa là đoán nhận xâu gồm tối thiếu n, tối đa m từ tiếng Việt hay các số nguyên. Bất đầu xâu là dấu cách hoặc dấu hai chấm. Trong thực nghiệm n = 1, m = 8. Với 3 tham số đầu vào IndexsOfPrefixPattern, PrefixStrings và CandidateRegularExpression thủ tục Extract_CandidateStrings sẽ thực đoán nhận các xâu con như nói ở trên, kết quả gọi là CandidateStrings. Tiếp tục ví dụ trên với đoạn: “Thông tin Tổng công ty Hàng không Việt Nam thua kiện ở châu Âu … “. PrefixString là “công ty”, IndexOfPrefixPattern là vị trí của “công ty”. Nếu CandidateRegularExpression là ([ |: ][\\-&a-zA-Z0-9à-ỵÀ-Ỵ]+){1,8} thì CandidateString thu được là “ Hàng không Việt Nam thua kiện ở châu”. Trim Tập CandidateStrings được đoán nhận ở bước trên chỉ mới được “kỳ vọng” là có chứa các thực thể thích hợp. Cần “cắt tỉa” để hoặc thu được tên thực thể mong muốn hoặc loại bỏ nếu không chứa tên thích hợp. Thủ tục Trim thực hiện công việc đó trên CandidateStrings thu được tập thực thể Entities – tập thực thể được rút trích ở mỗi vòng lặp. Chi tiết về các quy tắc cắt tỉa sẽ được trình bày ở mục 3.4. Filter_Entities Tập thực thể sau khi được rút trích sẽ được ánh xạ ngược vào tập dữ liệu ở vòng lặp tiếp theo để tìm sự xuất hiện (Occurrences). Nhưng không phải tất cả các thực thể được dùng để ánh xạ. Bởi có 2 lý do. Thứ nhất nếu như sử dụng tất cả các thực thể, thì thời gian để tìm Occurrences là rất lâu. Thứ hai, không phải tất cả các thực thể được rút trích ra đều chính xác, và không phải tất cả đều “hiện diện” nhiều lần trong tập tài liệu, dẫn đến kết quả “sai lệch” đi. Những thực thể có số lần được rút trích ở mỗi vòng lặp càng lớn, thì xác suất nó là một thực thể hợp lý càng cao, và cũng có nghĩa nó có “độ ưu tiên cao” nên sẽ có nhiều cách để “biểu diễn” nó trên các tài liệu, dẫn đến tạo ra nhiều pattern mới hợp lý. Do đó, chỉ chọn lọc những thực thể mà có số lần được tìm thấy ở mỗi vòng lặp lớn hơn một ngưỡng nào đó. Sự lựa chọn một ngưỡng phù hợp cho việc lấy thực thể “đại diện” là tương đối khó, bởi không có một quy tắc nào đó để quy định miền giá trị cho ngưỡng này. Kết quả chọn lọc ảnh hưởng đến số lượng, chất lượng của những patterns mới cũng như đối với những thực thể ở các vòng lặp tiếp theo. Để có thể tìm ra một ngưỡng hợp lý nhất thì nên tiến hành nhiều thử nghiệm với những ngưỡng khác nhau. Thủ tục Filter_Entities thực hiện chọn các thực thể đại diện RepresentativeEntities từ Entities. Find_PrefixStrings Tập thực thể đại diện RepresentativeEntities đã được chọn lọc ở bước trên, cái cần quan tâm tiếp theo là “xâu tiền tố” (PrefixString) của những thực thể này. Biểu thức chính quy PrefixRegularExpression kết hợp với RepresentativeEntities để đoán nhận “sự xuất hiện” (Occurrences) của các thực thể cũng như “tiền tố” của chúng. PrefixRegularExpression có dạng: ([a-zA-Z0-9à-ỵÀ-Ỵ]+[ |\\:]){n,m} Có nghĩa là đoán nhận xâu gồm tối thiểu n, tối đa m từ (mỗi từ cấu tạo bởi các ký tự tiếng Việt hay chữ số). Kết thúc của xâu là dấu cách hoặc dấu hai chấm. Trong thực nghiệm n=1,m=3. Bởi vì chúng ta chỉ cần quan tâm tới xâu từ 1 đến 3 từ đứng liền trước tên thực thể, hay nói cách khác “tiền tố” chỉ là xâu dài từ 1 đến 3 từ. Thủ tục Find_PrefixStrings dùng 2 tham số đầu vào PrefixRegularExpression và RepresentativeEntities để ánh xạ vào tài liệu tìm ra sự xuất hiện của các thực thể và rút trích ra các tiền tố. Kết quả các tiền tố trả về là PrefixStrings. Giả sử trong văn bản có đoạn “Có phải Tập đoàn Điện lực Việt Nam đặt quyền lợi của mình lên trên tất cả”, thì với RepresentativeEntity là “Điện lực Việt Nam” và PrefixRegularExpression là ([a-zA-Z0-9à-ỵÀ-Ỵ]+[ |\\:]){1,3}, PrefixString nhận được là “phải Tập đoàn ”. Generate_NewPrefixPattern Thủ tục Generate_NewPrefixPattern thực hiện việc sinh ra NewPrefixPattern từ tập PrefixStrings đã được rút trích ở bước trước. Thuật toán sinh NewPrefixPattern cũng như cách biểu diễn của PrefixString để thuận tiện cho cài đặt thuật toán sẽ được trình bày kỹ ở mục 3.3. . NewPrefixPattern có “định dạng” giống như PrefixPattern (Initial), chúng tiếp tục được dùng để rút trích những thực thể mới. Quy trình cứ tiếp tục thực hiện các vòng lặp như vậy cho đến khi đạt đến một điều kiện dừng. Có thể đưa ra nhiều điều kiện dừng như : Dừng khi không sinh ra được pattern mới, hoặc dừng khi độ chính xác của các thực thể rút trích được thấp… Trong bài toán này, chạy đến vòng thứ 3 thì kết quả thu được đã không như ý muốn do đó chỉ sử dụng kết quả của 2 vòng đầu như là những thực thể rút trích được. Biểu diễn PrefixString và quy tắc cho PrefixPattern Dựa vào quy trình thực hiện trong các bài toán của Brin, Pasca hay hệ thống Snowball, có thể thấy các thực thể được rút trích và patterns sinh ra có quan hệ tương hỗ với nhau. Nghĩa là “chất lượng” của cái này ảnh hưởng đến chất lượng của cái kia. Không những thế còn ảnh hưởng đến chất lượng của các vòng lặp tiếp theo. Bài toán rút trích thực thể tên tổ chức cũng như vậy, cụ thể ở đây là giữa PrefixPattern và thực thể tên tổ chức. Do đó, sinh ra một PrefixPattern tốt là điều quan trọng, nó ảnh hưởng đến chất lượng của toàn bộ quy trình. PrefixString là dữ liệu vào cho thuật toán sinh PrefixPatern, nên nó cần có cách biểu diễn hợp lý để thuận tiện cho thuật toán sinh. Chi tiết về PrefixString và PrefixPattern được đề cập ở dưới đây. Biểu diễn PrefixString PrefixString là xâu “tiền tố” của tên thực thể, được đoán nhận bởi biểu thức chính quy PrefixRegularExpression. Trong văn bản, mỗi một thực thể có nhiều PrefixString và một xâu PrefixString có thể là “tiền tố” cho nhiều thực thể. Ứng với một thực thể, khi ánh xạ ngược nó vào tập dữ liệu ta thu được tập các PrefixString. Mỗi PrefixString đó được biểu diễn theo dạng : S : Xâu nội dung của PrefixString – Tức xâu tiền tố của thực thể N: Tên thực thể C: Count – Số lần S là “tiền tố” của N Biểu diễn theo cách này để thuận tiện cho thủ tục sinh PrefixPattern. Bởi vì PrefixPattern coi như là “đại diện” cho tập các PrefixString để rút trích các thực thể mới nên pattern đó phải có quan hệ với các PrefixPattern. Mỗi PrefixString cũng có “độ ưu tiên” khác nhau trong việc lựa chọn tham gia sinh pattern. Độ ưu tiên đó dựa theo số lượng thực thể nhận nó làm tiền tố. Chi tiết hơn được trình bày ở mục dưới. Thuật toán sinh PrefixPattern PrefixPattern có dạng tổng quát là A1|A2|….|An Vấn đề là từ tập các PrefixStrings, tìm ra quy tắc hợp lý để sinh ra các thành phần A1, A2, … An đó. Một PrefixPattern được coi là tốt nếu mỗi thành phần A1, A2,…., An của nó được sinh ra từ nhiều PrefixStrings, và phải là các PrefixStrings của nhiều thực thể khác nhau để đảm bảo PrefixPattern đó không riêng biệt và không chung chung. Thủ tục sinh ra các thành phần Ai được mô tả như sau: procedure GeneratePattern ( D ) Đầu vào: tập các PrefixString D Đầu ra: danh sách các {Ai} Begin L={}; Chia D thành các miền D1, D2, … Dk sao cho: Di ∩ Dj = Ө ( i≠j) Các PrefixString trong mỗi miền Di có thành phần S khớp với nhau “phải nhất” (tính từ cuối mỗi xâu) ít nhất một từ (word) – gọi là xâu Si . For each Di Do Gọi CNi là tổng số thực thể khác nhau trong Di.; Gọi CCi = Ci0 + Ci1 + … + Cik (k = | Di | ) If (CNi > m) AND (CCi > n) Then L=L+{Si}; End If End For Return L; End Xét ví dụ minh họa cho thủ tục trên: D ban đầu gồm các PrefixStrings như sau : { ; ; ; }. Sau bước thứ nhất sẽ chia làm 2 miền D1, D2 là: D1 ={ ; } D2 = { ; } Và S1 = “công ty”, S2 = “Hiệp hội”; Bước thứ 2 thu được: CN1 = 1, CN2 = 2; CC1 = 17, CC2 = 11; Giả sử m = 1 và n = 10 thì kết quả trả về là L = { “Hiệp hội” }. Và PrefixPattern sinh ra là : PrefixPattern = (Hiệp hội) Thủ tục trên tương đối đơn giản, các thành phần Ai chỉ là phần khớp nhau phải nhất ( Si ) trong mỗi miền Di . Do đó cần chọn lọc các Si tin cậy để gán cho Ai . Xác định độ tin cậy của mỗi Si theo biểu thức: CNi > m AND CCi > n (như trong thủ tục trên) m, n là “ngưỡng” tùy chọn – dựa vào thực nghiệm để tìm ra giá trị phù hợp nhất. Thỏa mãn thỏa mãn điều kiện CNi > m nghĩa là thành phần Ai được “sinh ra” bởi nhiều hơn m thực thể, tức là nó không riêng biệt cho một thực thể nào cả. Điều này rất cần thiết, bởi nó phải là sự “đóng góp” của nhiều thực thể thì mới thể hiện là “đại diện” cho tiền tố của các tên . Thỏa mãn CCi > n nghĩa là nó đại diện cho hơn n tiền tố của các thực thể. Do đó CCi càng lớn thì độ tin cậy càng cao. Xác định ngưỡng m, n là không dễ dàng. Bằng nhiều thực nghiệm khác nhau với những cặp giá trị (m, n) thay đổi khác nhau và quan sát kết quả đạt được tương ứng để chọn ra giá trị m,n hợp lý nhất. Vẫn có những trường hợp Ai đã được chọn lọc ở bước trên nhưng chúng là những từ “nghèo” giá trị hay chỉ là những từ với tính chất liệt kê, liên kết …. Do đó, tìm ra các quy tắc để chọn lọc tiếp sẽ thu được PrefixPattern tốt hơn. Liệt kê tất cả các trường hợp là điều khó khăn, trong khóa luận này em chỉ hạn chế theo một giới hạn nào đó. Cụ thể, nếu Ai của PrefixPattern chỉ là một xâu gồm một từ, mà từ đó chỉ gồm 2 ký tự sẽ bị loại bỏ. Ví dụ như các từ : “và, do, là …” sẽ bị loại bỏ. Kết quả thu được PrefixPattern hợp lý để sử dụng cho vòng lặp tiếp theo. Quy tắc cắt tỉa Như mục 3.3.2. đã trình bày, CandidateString là xâu được “kỳ vọng” là có chứa tên thực thể thích hợp. Ban đầu nó chỉ là một xâu bất kỳ được đoán nhận bởi biểu thức chính quy CandidateRegularExpression (như trên mỗi CandidateString có độ dài từ 1 đến 8 từ) nên cần phải cắt tỉa và chuẩn hóa để thu được tên chính xác. Chính vì sự đa dạng trong cách viết của tiếng Việt, cũng như đôi khi những thông tin viết trên Web không thật sự theo chuẩn – chuẩn ngữ pháp, chuẩn chữ hoa chữ thường… khiến cho việc việc cắt tỉa gặp nhiều khó khăn, nên cần xét kỹ nhiều trường hợp để cắt tỉa một cách hợp lý nhất. Các bước cắt tỉa một CandidateString được mô tả như hình dưới đây: Hình 7: Quy tắc cắt tỉa Các thủ tục trên được diễn giải như sau: Input : CandidateString – Xâu ban đầu cần cắt tỉa EndIsCapitalizedWord ß Extract_By_Capitalize_Rule (CandidateString) Rút trích từ CandidateString ra xâu dài nhất thỏa mãn từ cuối cùng có ký tự đầu viết hoa. Standard_Left ß Extract_By_Left_Rule (EndIsCapitalizedWord, LeftRule) Từ EndIsCapitalizedWord rút trích ra xâu con trái nhất, dài nhất thỏa mãn không chứa phần tử nào của tập LeftRule. Standard_Name ß Extract_By_Right_Rule (StandardLeft, RightRule) Từ StandardLeft rút trích ra xâu con phải nhất, dài nhất thỏa mãn không chứa phần tử nào của tập RightRule. ExactName ß Compare_Discard_Name (StandardName, DiscardName) So sánh Standard_Name với các tên trong tập DiscardName. Nếu khác hoàn toàn thì trả về chính nó – StandardName. Ngược lại trả về xâu rỗng (tên không hợp lệ). Output : ExactName – tên được rút trích Các mục dưới đây sẽ giải thích rõ hơn. Extract_By_Capitalize_Rule Đặc điểm của tên các tổ chức là các từ cấu tạo nên nó thường viết hoa ở ký tự đầu. Hoặc tất cả các từ đều viết hoa hoặc chỉ một số từ viết hoa. Tuy nhiên kết thúc của tên phải là một từ mà ký tự đầu viết hoa. Đó là dấu hiệu đầu tiên cho việc cắt tỉa. Thủ tục Extract_By_Capitalize_Rule có nhiệm vụ cắt tỉa xâu CandidateStrings để trả về kết quả là xâu EndIsCapitalizedWord có tính chất trên. Ví dụ nếu CandidateString là : “Hàng không Việt Nam liên tiếp gặp nhiều” thì EndIsCapitalizedWord sẽ là : “Hàng không Việt Nam”. Extract_By_Left_Rule Những từ như : “tại, ở, đến …” ( tạm gọi là từ “thừa” ) thường được đi sau bởi một địa điểm nào đó. Do vậy nếu trong EndIsCapitalizedWord có chứa những từ như vậy thì sẽ “cắt” đi phần đằng sau đó, chỉ lấy phần bên trái. Tập những từ “thừa” đó được gọi là LeftRule. Thủ tục Extract_By_Left_Rule nhận 2 tham số đầu vào là EndIsCapitalizedWord và LeftRule thực hiện công việc đó, kết quả trả về là StandardLeft . Ví dụ nếu EndIsCapitalizedWord là : “Du lịch Việt Nam tại Hà Nội” thì từ “thừa” là “tại” và StandardLeft sẽ là : “Du lịch Việt Nam”. Extract_Standard_Name Những từ như : ”như, là, …” (từ “liệt kê”) thường dùng để liệt kê. Đằng sau nó rất có thể sẽ là chính xác một, nhiều tên tổ chức nào đó. Do vậy nếu StandardLeft có chứa những từ “liệt kê” như vậy, thì sẽ cắt đi phần bên trái và chỉ lấy phần bên phải của từ “liệt kê” đó. Tập các từ liệt kê gọi là RightRule. Thủ tục Extract_Standard_Name với 2 tham số đầu vào là StandardLeft và RightRule thực hiện công việc trên, thu được StandardName. Ví dụ nếu StandardLeft là : “kinh doanh gas như Vinagas” thì StandardName là: “Vinagas”. Compare_Discard_Name Giả sử có đoạn text:” Nhiều công ty Việt Nam đang tiến hành nhập khẩu …” với PrefixPattern là “công ty”, thì khi rút trích như ở các bước trên sẽ thu được StandardName là “Việt Nam”. Tuy nhiên, tên này không chính xác cần loại bỏ. Đấy là một trong các trường hợp ngoại lệ mà tên thu được tuy rất “phổ biến” nhưng thực chất lại không chính xác… Tập các tên ngoại lệ đó gọi là DiscardName. Thực hiện thủ tục Compare_Discard_Name(StandardName, DiscardName) kết quả thu được là ExactName . ExtractName nhận giá trị là StandardName nếu không có phần tử nào trong DiscardName trùng với StandardName, ngược lại ExtractName nhận ra trị là một xâu rỗng. Các trường hợp cắt tỉa khác Ngoài ra với đặc điểm của sự đoán nhận và cắt tỉa tên như trên, có những trường hợp sau các bước cắt tỉa ở trên, xâu thu được chỉ là một từ - có thể là tiếng Việt hoặc tiếng Anh hoặc là từ viết tắt … Do không có một tên tổ chức nào lại có tên chỉ là một từ tiếng Việt (từ mà các ký tự có dấu ), nên nếu gặp trường hợp đó thì sẽ loại bỏ. Thêm một trường hợp nữa, vì trong thực nghiệm “quy ước” tên tổ chức là một xâu dài tối đa 8 từ, nên đối với những tổ chức có tên dài từ 9 từ trở lên sẽ không được đoán nhận. Ví dụ với văn bản có chứa đoạn ”Công ty TNHH Quy hoạch và Phát triển nhà Việt Nam - Hàn Quốc” thì với PrefixPattern là “công ty” thì chỉ rút trích được đoạn text là “TNHH Quy hoạch và Phát triển nhà Việt” (dài 8 từ) rõ ràng tên này không đúng mà chính xác phải là “TNHH Quy hoạch và Phát triển nhà Việt Nam - Hàn Quốc” nên phải loại bỏ. Đặc điểm của xâu (8 từ) trên là chỉ chỉ có 1 từ “phải nhất” viết hoa và là một từ tiếng Việt. Nên với những xâu nào được rút trích sau 5 bước trên mà có dạng như vậy cũng sẽ bị hũy bỏ… Đấy là một số quy tắc em quan sát được và áp dụng vào thực nghiệm, còn nhiều trường hợp nữa có thể đưa ra để tăng độ chính xác cho thực thể. Tuy nhiên trong phạm vi của khóa luận này em chỉ thử với những trường hợp như vậy. CHƯƠNG 4. THỰC NGHIỆM Chuẩn bị đầu vào Thu thập dữ liệu Dữ liệu cho thực nghiệm gồm trên 3500 file được lấy từ website www.vietnamnet.vn/ trong các mục “kinhte”, “thegioi” bởi vì những mục này sẽ có nhiều bài viết về các tổ chức. Chương trình chỉ quan tâm tới dữ liệu text bên trong mỗi file, do đó trước khi thực hiện rút trích tên thực thể, file dữ liệu được lọc tách hết các thẻ html cũng như javascript. Xây dựng PrefixPattern (Initial) Phương pháp trích chọn ở đây chỉ là học gần không giám sát, nó dựa vào đặc điểm của thực thể cần rút trích là được biểu diễn theo một định dạng nhất định. Sinh được một PrefixPattern tốt cũng đồng nghĩa với việc rút trích được nhiều thực thể chính xác. Ngược lại, từ tập thực thể chính xác sẽ sinh ra được những PrefixPattern mới tốt. Do đó xây dựng PrefixPattern khởi tạo là hết sức quan trọng, nó có ý nghĩa lớn đối với chất lượng, độ chính xác của thực nghiệm. Thực nghiệm sẽ thay đưa ra những PrefixPattern khác nhau, từ kết quả thu được sẽ rút ra được mẫu nào là tốt nhất. Qua khảo sát, nhận thấy PrefixPattern ban đầu: “phòng|cục|công ty|cty|tập đoàn” là tốt nhất. Mẫu này được lưu trong file “prefixPattern0.txt”. Số 0 thể hiện mẫu ở vòng lặp đầu tiên, với mỗi vòng lặp tiếp theo giá trị sẽ lần lượt là 1, 2… Xây dựng các Luật (Rule) Các Rules được dùng trong quá trình “cắt tỉa” tên thực thể như đã được trình bày ở trên. LeftRule Là tập hợp các “từ, cụm từ” mà nếu chúng xuất hiện trong tên thực thể thì tên thực thể sẽ được “cắt tỉa” và lấy phần ký tự từ đầu đến trước “từ, cụm từ” đó. Tập hợp các “từ, cụm từ” này được lưu trong file “rule\\leftRule.txt”. Có thể liệt kê một số các từ như : “tại, ở, sang, …”. RightRule Tập các từ, cụm từ “liên kết”. Tên thực thể sẽ được rút trích từ vị trí các từ, cụm từ này đến hết xâu của tên thực thể ban đầu. File “rule\rightRule.txt” dùng để lưu trữ tập các từ, cụm từ “liên kết”. Ví dụ như các từ : “như, là, gồm …”. DiscardName File “rule\discardName.txt” chứa tập các tên không thích hợp đối với tên tổ chức. Nếu chương trình đoán nhận được tên nào trùng với một trong các tên trong “rule\discardName.txt” thì xem như không hợp lệ. Ví dụ liệt kê một số tên Quốc gia hoặc những từ thường đi kèm (bổ sung thông tin) cho tổ chức: ”Việt Nam, Trung Quốc …, TNHH, CP, …”. Môi trường thực nghiệm Phần cứng Bảng 3 : Môi trường phần cứng Thành phần Chỉ số CPU Intel Pentium Dual E2180 2.0GHz RAM 1 GB Bộ nhớ ngoài 160GB Phần mềm Bảng 4: Môi trường phần mềm Thành phần Chỉ số OS WindowsXP Service Pack 2 IDE eclipse-SDK-3.4.1-win32 Kết quả thực nghiệm Kết quả thực nghiệm phụ thuộc rất nhiều vào PreifxPattern ban đầu đưa vào và các luật để cắt tỉa tên. Nếu như lựa chọn được một PrefixPattern ban đầu tốt, thì số lượng cũng như “chất lượng” của các thực thể rút trích được sẽ rất tốt ngay ở vòng lặp đầu tiên . Dẫn đến những kết quả khả quan ở các vòng lặp tiếp theo. Cũng như càng đưa ra nhiều luật cắt tỉa, thì độ chính xác sẽ càng cao, nhưng cũng đồng nghĩa với số lượng các thực thể rút trích được sẽ giảm đi. Và ngược lại, một PrefixPattern không tốt, hay lượng luật cắt tỉa đưa ra không chính xác, số lượng thực thể rút trích được sẽ lớn, nhưng chất lượng càng xấu ở các vòng lặp tiêp theo … Trong thực nghiệm này, do không biết được chính xác tập R = { tất cả các thực thể tên tổ chức }, do đó không thể tính được giá trị “độ hồi tưởng” (recall). Chỉ dùng một chỉ số duy nhất là độ chính xác (precision) để đánh giá chất lượng của thực nghiệm. Độ chính xác được xác định theo : Độ chính xác : R = {tất cả các rút trích được ở mỗi vòng} R’ = {chọn ngẫu nhiên một số lượng các thực thể từ R – trong thực nghiệm |R’| = 100} R’’ = {các thực thể trong R’ được kiểm định là chính xác} |R| = số lượng các phần tử trong R. Để lấy kết quả đưa vào bảng, với mỗi lần kiểm tra độ chính xác, em thực hiện lấy 3 lần. Lấy giá trị trung bình của 3 lần đó làm số liệu cuối cùng. Em đã thực hiện thực nghiệm nhiều lần, với những thay đổi khác nhau về PrefixPattern ban đầu, quy tắc cắt tỉa, ….và kết quả thu được tương đối khác nhau. Dưới đây em chỉ liệt kê một số thực nghiệm đại diện để mô tả tính chất của bài toán: Với lần thực nghiệm đầu tiên cho PrefixPattern là : “công ty|cty|tập đoàn” . Kết quả được cho như bảng bên dưới: Bảng 5: Kết quả lần 1 Kếtquả Vòng lặp Số thực thể được rút trích Độ chính xác 1 2064 84.67% 2 299 84.33% Lần thực nghiệm thứ 2 giống như lần thứ 1, tuy nhiên đã “hạn chế” các luật cắt tỉa, cụ thể là loại đi bước cuối cùng trong quy trình cắt tỉa trình bày ở mục 3.4. Kết quả thu được là : Bảng 6: Kết quả lần 2 Kết quả Vòng lặp Số thực thể được rút trích Độ chính xác 1 2632 71.33% 2 13775 34.33% Lần thực nghiệm 3 PrefixPattern là “phòng|cục|công ty|cty|tập đoàn”, chọn ngưỡng là 10 kết quả: Bảng 7: Kết quả lần 3 Kết quả Vòng lặp Số thực thể được rút trích Độ chính xác 1 2333 81.33% 2 299 84.33% Nhận xét Theo kết quả lần 1 và lần 3 cho thấy, khi tăng số phần tử trong PrefixPattern ban đầu thì số lượng các thực thể rút trích được ở vòng đầu cũng tăng. Tuy nhiên, độ chính xác cũng giảm đi một chút, kết quả đó có thể chấp nhận được. Đến vòng lặp thử 2 thì kết quả thu được giống nhau, là do PrefixPattern ở vòng 2 của 2 lần thực nghiệm giống nhau. Mặc dù thực nghiệm 3 có số thực thể ở vòng 1 nhiều hơn ở thực nghiệm 1, nhưng không “sinh” ra nhiều PrefixPattern mới hơn thực nghiệm 1. Như vậy có thể suy ra thực nghiệm chỉ có kết quả tốt ở 2 vòng đầu. Kết quả lần 1 và lần 2 cho thấy vai trò của quy tắc cắt tỉa đối với chất lượng toàn bộ kết quả các vòng lặp. Cùng tham số đầu vào với lần thực nghiệm 1, chỉ giảm bớt quy tắc cắt tỉa, nhưng độ chính xác ở vòng 1 của thực nghiệm 2 đã giảm đi đáng kể. Kết quả kém ngay ở vòng thứ nhất càng kéo theo sự sai lệch ở các vòng tiếp theo … dẫn đến độ chính xác của toàn bộ quy trình sẽ rất thấp. Kết Luận Những vấn đề đã đề cập trong khóa luận Khóa luận đã khái quát hóa một số vấn đề lý thuyết về trích chọn thông tin, bài toán trích chọn thực thể tên tổ chức, đồng thời đưa ra các bài toán nền tảng để áp dụng vào cho khóa luận này. Một số vấn đề và giải pháp cho bài toán đã được đưa ra, điểm đặc biệt chú ý nhất là kỹ thuật DIPRE. Thực nghiệm đã đưa ra một số trường hợp tiêu biểu để thể hiện đặc điểm, bản chất của bài toán. Tuy nhiên kết quả của thực nghiệm mới chỉ ở mức tạm chấp nhận được. Khái quát lại nội dung mà luận văn đã đưa ra. Chương 1 đưa ra một cái nhìn khái quát về trích chọn thông tin, bài toán trích họn thực thể tên tổ chức, cũng như ý nghĩa thực tế mà bài toán mang lại. Chương 2 trình bày các bài toán liên quan, nó là cơ sở để áp dụng cho bài toán trong khóa luận này. Vấn đề mấu chốt nhất trong chương là kỹ thuật DIPRE. Đó là một kỹ thuật chính sử dụng cho bài toán trong khóa luận, với một đặc điểm nổi bật là có thể áp dụng cho tập dữ liệu lớn mà cần ít sự can thiệp của con người. Sử dụng kết quả của vòng lặp hiện tại để làm dữ liệu vào cho vòng lặp tiếp theo …. Ngoài ra những kỹ thuật rút trích thực thể từ tập các patterns của hệ thống Snowball hay kỹ thuật rút trích tên thực thể, tên miền mà Pasca đưa ra cũng là ý tưởng quan trọng để em áp dụng vào khóa luận của mình. Chương 3 đưa ra mô hình tổng quát cũng như chi tiết cho bài toán trích chọn thực thể tên tổ chức. Chương đã đưa ra từng bước cụ thể của bài toán. Và cũng nhấn mạnh đến vai trò của việc lựa chọn pattern ban đầu cho chương trình, cũng như vai trò của các quy tắc cắt tỉa tên đối với chất lượng của kết quả thu được. Chương này cũng đưa ra khái niệm “ngưỡng”; một ngưỡng cho việc lựa chọn thực thể để sử dụng ở vòng lặp tiếp theo; một ngưỡng để lựa chọn ra pattern phù hợp. Đấy cũng là yếu tố quyết định không nhỏ đến kết quả đạt được. Chương 4 trình bày môi trường tiến hành thực nghiệm, chuẩn bị dữ liệu … và kết quả thực nghiệm. Chỉ đưa ra một số kết quả đại diện, tiêu biểu để phản ánh bản chất, đặc điểm của thuật toán. Những mặt hạn chế và hướng giải quyết Như đã nói, kỹ thuật DIPRE chỉ thường áp dụng cho bài toán rút trích cặp quan hệ còn khóa luận này áp dụng để rút trích thực thể đơn (thực thể tên công ty). Do đó gặp phải khó khăn trong việc xây dựng pattern để rút trích. Kết quả thu được chưa thật sự cao, và độ chính xác phụ thuộc nhiều vào quy tắc cắt tỉa. Một điểm hạn chế nữa là số lượng thực thể tên tổ chức rút trích được chưa nhiều. Chỉ có 2 vòng đầu là cho kết quả chấp nhận được. Miền của các tổ chức rút trích được cũng chưa rộng, mới chỉ rút trích được các loại tổ chức như “công ty”, “tập đoàn”, “hiệp hội” … Bởi vì trên thực tế có rất nhiều loại tổ chức, với cách biểu diễn khác nhau nên khó có thể tìm ra mối liên hệ để xây dựng mẫu. Nếu như có nhiều thời gian hơn nữa để nghiên cứu về bài toán này thì có thể đưa ra nhiều quy tắc cắt tỉa cũng như kỹ thuật xây dựng pattern hợp lý hơn. Hoặc có thể phân tích thêm về xâu ký tự đứng trước mỗi PrefixSring, bởi nó cũng mang lại nhiều thông tin bổ ích. Từ đó độ chính xác sẽ cao hơn. Tuy kết quả mà khóa luận mang lại chưa có ứng dụng vào các hệ thống thực, nhưng nó là bài toán cơ bản cho các bài toán rút trích thực thể, đặc biệt là tên tiếng Việt – vấn đề đang được quan tâm nhiều. Có thể phát triển nhiều bài toán khác liên quan đến tổ chức, vẫn dựa vào DIPRE, như bài toán rút trích cặp quan hệ … Tài liệu tham khảo: [1] C.Fellbaum. WordNet: An Electronic Lexical Database and Some of its Applications.M IT Press, 1998. [2] David Day, John Aberdeen, Lynette Hirschman, Robyn Kozierok, Patricia Robinson, and Marc Vilain. Mixedinitiative development of language processing systems. In Proceedings of the Fifth ACL Conference on Applied Natural Language Processing, April 1997. [3] Eugene Agichtein and Luis Gravano: “Snowball: Extracting Relations from Large Plain-Text Collections”. Proc. 5th ACM International Conference on Digital Libraries, San Antonio, 2000 [4] GuoDong Zhou. “Named Entity Recognition using an HMM-based Chunk Tagger”. Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics Philadelphia, July 2002, [5] Marcus, B.S antorini, and M. Marcinkiewicz. Building a large annotated corpus of English: The Penn Treebank. Computational Linguistics, 313–330, June 1993. [6] Marius Pasca, “Acquisition of Categorized Named Entities for Web Search”. Proc. 13th ACM Conference on Information and Knowledge Management, Washington, 2004. [7]. S.Brin. Extracting patterns and relations from the World Wide Web.In Proceedings of the 6th International Conference on Extending Database Technology (EDBT- 98), Workshop on the Web and Databases, Valencia, Spain, 1998. [8] William B. Frakes and Ricardo Baeza-Yates, editors. Information Retrieval: Data Structures and Algorithms. Prentice-Hall, 1992.