Thạc Sĩ Nghiên cứu và cải tiến phương pháp phân đa lớp văn bản bằng SVM (Support Vector Machines)

i

MỞ ĐẦU
Ngày này, đi cùng sự phát triển của các công nghệ hiện đại thì máy tính nói
chung và các thiết bị lưu trữ nói riêng ngày càng được cải tiến không ngừng với
dung lượng tăng dần lên tới một con số khổng lồ và chưa có dấu hiệu dừng lại. Bên
cạnh đó, sự bùng nổ của internet làm các nguồn thông tin được kết nối với nhau
càng làm khối lượng thông tin đó đã lớn lại càng trở nên lớn hơn. Chính vì vậy mà
nhu cầu tổ chức, phân loại thông tin ngày càng trở nên tối cần thiết. Thử tưởng
tượng khi chúng ta đứng trước một thư viện lớn với khoảng 1000 đầu sách để lẫn
lộn vào nhau, công việc tìm một cuốn sách đáp ứng được ý muốn của chúng ta sẽ
trở nên thực sự khó khăn khi phải xem xét tất cả những đầu sách ở đó. Nếu như
1000 đầu sách đó được chia làm các lĩnh vực, khu vực cụ thể thì công việc của
chúng ta sẽ trở nên đơn giản hơn nhiều. Chúng ta chỉ cần đi với khu vực chứa lĩnh
vực chúng ta cần và lướt qua 1 số lượng nhỏ các cuốn sách, như thế là đã chọn được
cuốn sách chúng ta cần. Do vậy, hầu hết bất cứ thư viện hay nhà sách nào cũng đã
phân loại cách đầu sách để cho người đọc dễ chọn lựa.
Chúng ta có thể thấy, ví dụ trên chỉ đưa ra khối lượng thông tin là 1000 đầu
sách trong thư viện đã đủ gây ra nhiều khó khăn, huống hồ dữ liệu trên internet hiện
nay lại vô cùng lớn, gấp hàng trăm hàng triệu lần ví dụ ở trên. Giải pháp được đưa
ra là phân loại thông tin. Nhưng một vấn đề gặp phải ở đây nữa là 1000 đầu sách thì
có thể phân loại bằng tay nhưng với một khối lượng khổng lồ thông tin thì làm cách
nào chúng ta có thể phân loại được? Nếu như chúng ta vẫn phân loại bằng tay thì sẽ
tiêu tốn rất nhiều thời gian, nhân lực, vật lực, và liệu chăng phương pháp này có khả
thi?
May thay, chúng ta đang sống trong thời đại của công nghệ. Tốc độ xử lý của
máy tính càng ngày càng lớn và thực sự trở thành một công cụ đắc lực của con
người, hỗ trợ con người trong nhiều lĩnh vực, trong đó có phân loại thông tin. Máy
tính trở thành một công cụ hữu hiệu cho việc phân loại tự động thông tin bằng cách

ii

học, đó được gọi là chiến lược máy học được áp dụng để giải bài toán phân lớp văn
bản.
Để giải quyết phần nào bài toán nói trên, chúng em thử nghiệm một công cụ
tự động huấn luyện, phân lớp và tổ chức thông tin theo các chủ đề trên máy tính. Và
từ những thuật toán đã có từ trước, chúng em xin được đưa ra một mô hình phân đa
lớp văn bản dựa trên các mô hình phân đa lớp đã có của thuật toán vector hỗ trợ
(Support Vector Machines). Hi vọng khóa luận của chúng em có thể đóng góp phần
nào cho giải quyết bài toán tổ chức và phân loại thông tin tự động.
Khóa luận bao gồm 4 chương, nội dung chính của các chương như sau:
Chương 1: Định nghĩa bài toán phân loại văn bản, các khái niệm cơ bản, quá
trình tiền xử lý văn bản và các phương pháp phổ biến, đã được công bố dùng để
phân loại văn bản hiện nay. Từ đó đưa ra sự so sánh giữa các phương pháp này với
nhau để có thể thấy được ưu điểm, khuyết điểm của từng phương pháp.
Chương 2: Đề cập đến cơ sở lý thuyết của phương pháp phân lớp Support
Vector Machines (SVMs). Trong phần này chúng em đi sâu về các vấn đề chính của
SVMs cùng với giải thuật huấn luyện SMO. Trong phần sau của chương, chúng em
giới thiệu một số phương pháp phân đa lớp sử dụng SVMs nhị phân và các nhận
xét, đánh giá.
Chương 3: Đây là phần chính của khóa luận. Phần này sẽ trình bày về
phương án được đề xuất để giải quyết vấn đề phân đa lớp. Để giải quyết bài toán đa
lớp, chúng em sử dụng SVMs kết hợp cây nhị phân để đưa ra mô hình cây tổng
quát. Bên cạnh đó chúng em cũng đưa ra tiêu chuẩn để đánh giá cây tổng quát là
xác suất lỗi của cây. Cuối cùng độ khái niệm độ tách rời của hai lớp cùng với giải
thuật thử nghiệm để phát sinh cây tổng quát được đưa ra để thử nghiệm trên cây
tổng quát.
Chương 4: Trong phần đầu của chương sẽ đề cập đến phần cài đặt của
SVMs Framework – một framework dành cho việc tiền xử lý, huấn luyện và phân
lớp văn bản. Phần sau sẽ thống kê dữ liệu của các bộ huấn luyện cùng với kết quả

iii

phân lớp khi áp dụng giải thuật đã đề xuất ở chương 3 trên các bộ dữ liệu này với
các tham số khác nhau.



vii

MỤC LỤC
MỞ ĐẦU . i
LỜI CẢM ƠN iv
NHẬN XÉT CỦA GIẢNG VIÊN HƯỚNG DẪN . v
NHẬN XÉT CỦA GIẢNG VIÊN PHẢN BIỆN . vi
MỤC LỤC vii
CHƯƠNG 1: TỔNG QUAN BÀI TOÁN PHÂN LOẠI VĂN BẢN . 1
1.1. Giới thiệu bài toán phân loại văn bản. 1
1.2. Tiền xử lý văn bản và biểu đặc trưng văn bản trong không gian vector . 5
1.2.1. Tiền xử lý văn bản. . 5
1.2.1.1. Tách từ ( tiếng Việt ) . 6
1.2.1.2. Loại bỏ các ký tự thừa . 8
1.2.1.3. Loại bỏ các từ có chiều dài ngắn . 10
1.2.1.4. Loại bỏ các từ dừng. 10
1.2.1.5. Chỉ giữ lại dạng nguyên mẫu . 10
1.2.2. Biểu diễn đặc trưng văn bản trong không gian vector. 11
1.2.2.1. Chọn lựa đặc trưng. . 11
1.2.2.2. Vector hóa văn bản. 14
1.3. Một số phương pháp phân lớp phổ biến . 17
1.3.1. K láng giềng gần nhất ( K-nearest Neighbor ) . 17
1.3.2. Phương pháp cây quyết định ( decision tree ) . 20
1.3.3. Phương pháp Naïve Bayes 21
1.3.4. Mạng nơron nhân tạo . 22
1.3.5. Phương pháp Centroid-based vector . 25
1.3.6. Phương pháp SVMs . 25
CHƯƠNG 2: PHƯƠNG PHÁP PHÂN LỚP SVMs 27
2.1. Phân lớp SVMs nhị phân . 27
2.1.1. Phân lớp tuyến tính 28
2.1.2. SVMs với siêu phẳng có lề cực đại . 29
2.1.3. Bài toán tối ưu hóa . 32

viii

2.1.4. Trường hợp không thể phân tách tuyến tính - Lề mềm (Soft margin) 33
2.1.5. SVMs phi tuyến - Hàm nhân 35
2.1.6. Giải thuật huấn luyện . 37
2.1.7. Ưu khuyết điểm của SVMs 45
2.2. Phân loại đa lớp . 46
2.2.1. One-versus-All . 46
2.2.2. One-Versus-One (OvO, Pairwise) 49
2.2.3. Các phương pháp dựa trên cây nhị phân . 50
2.2.3.1. Decision Directed Acyclic Graph (DDAG) . 51
2.2.3.2. Half-against-Half (HAH) 52
CHƯƠNG 3: CÂY TỔNG QUÁT VÀ XÁC SUẤT LỖI 54
3.1. Mô hình cây tổng quát . 54
3.2. Xác suất lỗi của cây tổng quát 56
3.2.1. Định nghĩa: 56
3.2.2. Xác định xác suất lỗi của cây . 56
3.3. Giải thuật thử nghiệm 60
3.3.1. Độ tách rời giữa hai nhóm 60
3.3.2. Giải thuật xác định cấu trúc cây 62
CHƯƠNG 4: CHƯƠNG TRÌNH PHÂN LỚP, KẾT QUẢ THỰC NGHIỆM 69
4.1. SVM Framework . 69
4.1.1. Module tiền xử lý văn bản: . 71
4.1.2. Module huấn luyện: 71
4.1.3. Module phân lớp 73
4.2. Kết quả thử nghiệm và kết luận 74
4.2.1. Dữ liệu thử nghiệm 74
4.2.2. Kết quả thử nghiệm 77
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 83
Kết luận và những kết quả đạt được . 83
Hướng phát triển 84
PHỤ LỤC 85
Kết quả phân lớp bộ R8 . 85

ix

Kết quả phân lớp bộ R52 . 87
Kết quả phân lớp bộ 10ng 90
Kết quả phân lớp bộ DTR 93
Kết quả phân lớp bộ r9TTO . 95
TÀI LIỆU THAM KHẢO . 99
Tiếng Việt . 99
Tiếng Anh . 99