Đồ Án Phân Loại Văn Bản

MỤC LỤC

1. Tóm tắt đồ án . 1

2. Bài toán phân loại văn bản . 2

2.1 Giới thiệu . 2

2.2 Phát biểu bài toán 2

2.3 Mô hình tổng quát 3

2.3.1 Giai đoạn huấn luyện . 4

2.3.2 Giai đoạn phân lớp 5

2.4 Tiền xử lý văn bản . 6

2.5 Phương pháp biểu diễn văn bản 7

2.5.1 Mô hình không gian vector 7

2.5.2 Khái niệm trọng số . 7

2.6 Đánh giá bộ phân lớp . 9

2.6.1 Macro-Averaging . 11

2.6.2 Micro-Averaging 11

3. Các phương pháp phân loại văn bản . 12

3.1 Thuật toán Naïve Bayes . 12

3.1.1 Định lý . 12

3.1.2 Thuật toán . 13

3.1.3 Áp dụng trong phân loại văn bản . 15

3.2 Cây quyết định (Decision Tree) 18

3.2.1 Khái niệm 18

3.2.2 Thuật toán xây dựng cây . 19

3.2.2.1 Thuật toán ID3 19

3.2.2.2 Các độ đo trong thuật toán : 20

3.2.2.3 Ví dụ . 20

3.2.3 Áp dụng vào phân loại văn bản . 23

3.2.3.1 Biểu diễn văn bản . 23

3.2.3.2 Giai đoạn huấn luyện 24

3.2.3.3 Cross-validation 28

3.2.3.4 Giai đoạn phân lớp . 29

3.3 Mô hình xác xuất Entropy tối đại (Maximum Entropy Modeling) 29

3.3.1 Entropy 29

3.3.1.1 Khái niệm 29

3.3.1.2 Entropy của biến ngẫu nhiên 30

3.3.2 Áp dụng vào phân loại văn bản . 30

3.3.2.1 Biểu diễn văn bản . 30

3.3.2.2 Hàm đặc trưng và ràng buộc 31

3.3.2.3 Một số kí hiệu : 31

3.3.2.4 Mô hình . 31

3.3.2.5 Thủ tục huấn luyện Generalized iterative scaling 32

3.3.2.6 Giai đoạn phân lớp . 34

5. Tài liệu tham khảo 35











1





1. Tóm tắt đồ án

Phần này trình bày sơ lược về bài toán “Phân loại văn bản” được đề

cập đến trong cuốn sách “Foundations Of Statistical Natural

Language Processing” và các phương pháp để thực thi bài toán phân

loại văn bản theo phương pháp thống kê.



Phân loại văn bản là một vấn đề quan trọng trong lĩnh vực xử lý ngôn ngữ.

Nhiệm vụ của bài toán này là gán các tài liệu văn bản vào nhóm các chủ đề cho

trước. Đây là một bài toán rất thường gặp trong thực tế điển hình như : một nhà

chuyên phân tích thị thường chứng khoán, anh ta cần phải tổng hợp rất nhiều tài

liệu, bài viết về thị trường chứng khoán để đọc và đưa ra phán đoán của mình.

Tuy nhiên, anh ta không thể đọc tất cả các bài viết, bài báo hay các tài liệu để rồi

phân loại chúng đâu là tài liệu chứng khoán sau đó anh ta mới đọc kỹ chúng cho

mục đích của anh ta. Lý do của vấn đề này là bởi ví số lượng bào viết, bài báo

hiện nay rất nhiều, đặc biệt là trên internet, nếu để đọc hết được tất cả tài liệu đó

thì sẽ mất rất nhiều thời gian. Một ví dụ khác trong thực tế là việc phân loại spam

mail. Khi một mail được gửi đến hộp thư, nếu để người dùng phải đọc tất cả các

mail thì sẽ tốn rất nhiều thời gian vì spam mail rất nhiều. Vì vậy, cần có một hệ

thống phân loại đâu là spam mail và đâu là mail tốt.

Để giải bài toán này đã có rất nhiều phương pháp được đưa ra như : thuật

toán Naïve Bayes, K-NN (K-Nearest-Neighbor), Cây quyết định (Decision Tree),

Mạng Neuron nhân tạo (Artificial Neural Network) và SVM (Support Vector

Machine). Mỗi phương pháp đều cho kết quả khá tốt cho bài toán này, tuy nhiên

để có được sự so sánh đầy đủ, ở các phân sau chúng ta sẽ đi vào chi tiết từng

phương pháp.

Đồ án nêu ra chi tiết các bước thực hiện bài toán “Phân Loại Văn Bản” trong

lĩnh vực xử lý ngôn ngữ tự nhiên và một số cách tiếp cận để giải quyết bài toán

cũng những kết quả đã đạt được dựa trên một số những ví dụ thử nghiệm của tác

giả trong cuốn sách này.











2





2. Bài toán phân loại văn bản

Phần này trình bày về chi tiết các bước thực hiện bài toán phân loại

văn bản như mô hình biểu diễn, các độ đo cũng như các phương pháp

đánh giá kết quả thực hiện bài toán phân loại văn bản.

2.1 Giới thiệu

Như đã trình bày ở trên, bài toán phân loại văn bản là một bài toán quan trọng

trong xử lý ngôn ngữ. Có khá nhiều bài toán phân loại trong lĩnh vực xử lý ngôn

ngữ tự nhiên như : gán nhãn từ loại (POS tagging), khử nhập nhằng nghĩa từ

vựng (Word Sense Disambiguation) và gán nhãn ngữ tính từ (Prepositional

Phrase Attachment)

Mỗi bài toán phân loại đều có các đối tượng thao tác khác nhau và mục tiêu

phân loại khác nhau. Trong bài toán gán nhãn từ loại (POS tagging) và khử nhập

nhằng nghĩa từ vựng (Word Sense Disambiguation), thì từ được xem là đối tượng

nội dung cần thao tác (mức độ từ). Trong gán nhãn ngữ tính từ (Prepositional

Phrase Attachment) thì một ngữ là đối tượng nội dung cần thao tác. Còn trong bài

toán phân loại văn bản thì một văn bản (document hay text) là đối tượng nội dung

cần thao tác.



Hình 2.1: Các bài toán phân loại trong xử lý ngôn ngữ tự nhiên



2.2 Phát biểu bài toán

Bài toán phân loại văn bản có thể được phát biểu như sau : Cho trước một tập

văn bản D={d1,d2, ,dn} và tập chủ đề được định nghĩa C={c1,c2, ,cn}.

Nhiệm vụ của bài toán là gán lớp di thuộc về cj đã được định nghĩa. Hay nói

cách khác, mục tiêu của bài toán là đi tìm hàm  :

