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

Lời cảm ơn 3

Tóm tắt nội dung 4

Bảng từ viết tắt 1

Mở đầu 2

CHƯƠNG 1. SƠ LƯỢC BÀI TOÁN TRÍCH CHỌN THỰC THỂ TÊN TỔ CHỨC 3

1.1. Tổng quan về trích chọn thông tin 3

1.2. Bài toán rút trích thực thể tên tổ chức 4

1.3. Ý nghĩa của bài toán rút trích thực thể tên tổ chức 5

CHƯƠNG 2. HƯỚNG TIẾP CẬN BÀI TOÁN TRÍCH CHỌN THỰC THỂ 6

2.1. Rút trích cặp quan hệ (title, author) của cuốn sách trong tài liệu web 6

2.1.1. Occurrences của sách 6

2.1.2. Patterns của sách 7

2.1.3. Quy trình rút trích 7

2.1.4. Thuật toán sinh Patterns 8

2.2. Thu thập tên và miền tương ứng từ tập tài liệu web 9

2.3. Hệ thống Snowball 13

2.3.1. Sinh patterns 13

2.3.2. Sinh cặp quan hệ 15

2.4. Tổng kết chương 16

CHƯƠNG 3. 17

3.1. Mô hình tổng quát 17

3.2. Mô hình chi tiết 19

3.2.1. Find_IndexsOfPrefixPattern 20

3.2.2. Extract_CandidateStrings 21

3.2.3. Trim 22

3.2.4. Filter_Entities 22

3.2.5. Find_PrefixStrings 23

3.2.6. Generate_NewPrefixPattern 23

3.3. Biểu diễn PrefixString và quy tắc cho PrefixPattern 24

3.3.1. Biểu diễn PrefixString 24

3.3.2. Thuật toán sinh PrefixPattern 25

3.4. Quy tắc cắt tỉa 27

3.4.1. Extract_By_Capitalize_Rule 29

3.4.2. Extract_By_Left_Rule 29

3.4.3. Extract_Standard_Name 30

3.4.4. Compare_Discard_Name 30

3.4.5. Các trường hợp cắt tỉa khác 30

CHƯƠNG 4. THỰC NGHIỆM 31

4.1. Chuẩn bị đầu vào 31

4.1.1. Thu thập dữ liệu 31

4.1.2. Xây dựng PrefixPattern (Initial) 31

4.1.3. Xây dựng các Luật (Rule) 31

4.2. Môi trường thực nghiệm 32

4.2.1. Phần cứng 32

4.2.2. Phần mềm 33

4.3. Kết quả thực nghiệm 33

4.4. Nhận xét 35

Kết Luận 35

Tài liệu tham khảo: 37

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.