Thạc Sĩ Phân loại văn bản với máy học Vector hỗ trợ và cây quyết định

52
PHÂN LOẠI VĂN BẢN VỚI MÁY HỌC VECTOR HỖ TRỢ
VÀ CÂY QUYẾT ĐỊNH
Trần Cao Đệ và Phạm Nguyên Khang 1
ABSTRACT
Text document classification, basically, can be considered as a classification problem.
Automatic text document classification is to assign a label to a new document based on
the similarity of the document with labeled documents in the training set. Many machine
learning and data mining methods have been applied in text document classification such
as: Naive Bayes, decision tree, k – Nearest neighbor, neural network,
Support vector machine (SVM) is an efficient classification algorithm. It has been applied
to machine learning and recognition field. However, it is still not efficient in applying to
text document classification because, by the nature, this problem often deals with a large
feature space. This paper focuses on applying SVM to text document classification and
compares the efficiency of the method with the one of decision tree, a traditional
classification algorithm. The research illustrates that SVM along with the feature
selection based on the singular value decomposition (SVD) is much better than decision
tree method.
Keywords: Decision tree, Support vector machine (SVM), text document classification,
single value decomposition (SVD)
Title: Text document classification with support vector machine and decision tree
TÓM TẮT
Bài toán phân loại văn bản, thực chất, có thể xem là bài toán phân lớp. Phân loại văn
bản tự động là việc gán các nhãn phân loại lên một văn bản mới dựa trên mức độ tương
tự của văn bản đó so với các văn bản đã được gán nhãn trong tập huấn luyện. Nhiều kỹ
thuật máy học và khai phá dữ liệu đã được áp dụng vào bài toán phân loại văn bản,
chẳng hạn: phương pháp quyết định dựa vào Bayes ngây thơ (Naive Bayes), cây quyết
định (decision tree), k–láng giềng gần nhất (KNN), mạng nơron (neural network),
Máy học vectơ hỗ trợ (SVM) là một giải thuật phân lớp có hiệu quả cao và đã được áp
dụng nhiều trong lĩnh vực khai phá dữ liệu và nhận dạng. Tuy nhiên SVM chưa được áp
dụng một cách có hiệu quả vào phân loại văn bản vì đặc điểm của bài toán phân loại văn
bản là không gian đặc trưng thường rất lớn. Bài viết này nghiên cứu máy học vector hỗ
trợ (SVM), áp dụng nó vào bài toán phân loại văn bản và so sánh hiệu quả của nó với
hiệu quả của giải thuật phân lớp cổ điển, rất phổ biến đó là cây quyết định. Nghiên cứu
chỉ ra rằng SVM với cách lựa chọn đặc trưng bằng phương pháp tách giá trị đơn (SVD)
cho kết quả tốt hơn so với cây quyết định.
Từ khóa: Cây quyết định, máy học vector hỗ trợ, phân loại văn bản, tách giá trị đơn
1 GIỚI THIỆU BÀI TOÁN PHÂN LOẠI VĂN BẢN
Phân loại văn bản là một bài toán xử lí văn bản cổ điển, đó là ánh xạ một văn bản
vào một chủ đề đã biết trong một tập hữu hạn các chủ đề dựa trên ngữ nghĩa của
văn bản. Ví dụ một bài viết trong một tờ báo có thể thuộc một (hoặc một vài) chủ

1 Khoa Công nghệ Thông tin & Truyền thông, Trường Đại học Cần Thơ Tạp chí Khoa học 2012:21a 52-63 Trường Đại học Cần Thơ
53
đề nào đó (như thể thao, sức khỏe, công nghệ thông tin, ). Việc tự động phân loại
văn bản vào một chủ đề nào đó giúp cho việc sắp xếp, lưu trữ và truy vấn tài liệu
dễ dàng hơn về sau.
Đặc điểm nổi bật của bài toán này là sự đa dạng của chủ đề văn bản và tính đa chủ
đề của văn bản. Tính đa chủ đề của văn bản làm cho sự phân loại chỉ mang tính
tương đối và có phần chủ quan, nếu do con người thực hiện, và dễ bị nhập nhằng
khi phân loại tự động. Rõ ràng một bài viết về Giáo dục cũng có thể xếp vào Kinh
tế nếu như bài viết bàn về tiền nong đầu tư cho giáo dục và tác động của đầu tư
này đến kinh tế - xã hội. Về bản chất, một văn bản là một tập hợp từ ngữ có liên
quan với nhau tạo nên nội dung ngữ nghĩa của văn bản. Từ ngữ của một văn bản là
đa dạng do tính đa dạng của ngôn ngữ (đồng nghĩa, đa nghĩa, từ vay mượn nước
ngoài, ) và số lượng từ cần xét là lớn. Ở đây cần lưu ý rằng, một văn bản có thể
có số lượng từ ngữ không nhiều, nhưng số lượng từ ngữ cần xét là rất nhiều vì phải
bao hàm tất cả các từ của ngôn ngữ đang xét.
Trên thế giới đã có nhiều công trình nghiên cứu đạt những kết quả khả quan, nhất
là đối với phân loại văn bản tiếng Anh. Tuy vậy, các nghiên cứu và ứng dụng đối
với văn bản tiếng Việt còn nhiều hạn chế do khó khăn về tách từ và câu. Có thể liệt
kê một số công trình nghiên cứu trong nước với các hướng tiếp cận khác nhau cho
bài toán phân loại văn bản, bao gồm: phân loại với máy học vectơ hỗ trợ [1], cách
tiếp cận sử dụng lý thuyết tập thô [2], cách tiếp cận thống kê hình vị [3], cách tiếp
cận sử dụng phương pháp học không giám sát và đánh chỉ mục [4], cách tiếp cận
theo luật kết hợp [5]. Theo các kết quả trình bày trong các công trình đó thì những
cách tiếp cận nêu trên đều cho kết quả khá tốt. Tuy nhiên khó có thể so sánh các
kết quả ở trên với nhau vì tập dữ liệu thực nghiệm của mỗi phương pháp là khác
nhau. Bài viết này so sánh hiệu quả của hai cách tiếp cận phân loại văn bản: phân
loại với giải thuật cây quyết định và phân loại với máy học vector hỗ trợ kết hợp
với phân tích giá trị đơn (SVD).
Theo cả hai cách tiếp cận này, trước hết, văn bản được coi như là một tập hợp các
từ. Để thực hiện tách từ chúng tôi đã áp dụng giải thuật MMSEG [6]. Phần tiếp
theo sẽ trình bày cụ thể mô hình hóa văn bản trước khi áp dụng phân lớp theo giải
thuật cây quyết định và phân lớp theo SVM.
2 MÔ HÌNH HÓA VĂN BẢN
Trên thực tế, để có thể áp dụng một giải thuật tách từ, văn bản cần qua bước tiền
xử lí cơ bản: chuẩn hóa dấu, chuẩn hóa “i” và “y”, chuẩn hóa font, Tuy nhiên
các bước này sẽ không được đề cập ở đây do giới hạn trang bài viết. Có thể xem
văn bản là tập hợp các từ. Khái niệm “từ” ở đây theo nghĩa là một chuỗi kí tự liên
tiếp nhau trong văn bản, không nhất thiết phải là một từ có nghĩa trong ngôn ngữ.
Việc xác định “từ” hay tách từ sẽ được thực hiện bằng một giải thuật nào đó. Hiện
nay phương pháp MMSEG [6] và các cải tiến của nó được áp dụng rộng rãi trong
tách từ tiếng Việt. Một số đề xuất tách từ độc lập với ngôn ngữ như phương pháp
n-gram; chẳng hạn trong tiếng Việt cứ lấy hai tiếng liên tiếp đứng cạnh nhau trong
văn bản làm “2-gram”. Như vậy một “2-gram” không nhất thiết phải là một từ
đúng trong tiếng Việt. Trong nghiên cứu này, chúng tôi dùng giải thuật MMSEG
để tách từ tiếng Việt. Giải thuật này có nguồn gốc là để tách tiếng Trung Quốc [7]