..

BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

……………………………………..

LUẬN VĂN THẠC SĨ KHOA HỌC
NGÀNH: CÔNG NGHỆ THÔNG TIN

PHÂN LOẠI VĂN BẢN CHO
HỆ THỐNG THU THẬP TIN TỨC TIẾNG VIỆT
BÙI MẠNH HOÀNG

Người hướng dẫn khoa học: TS. LÊ THANH HƯƠNG

HÀ NỘI 2009


BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
……………………………………..

BÙI MẠNH HOÀNG

LUẬN VĂN THẠC SĨ KHOA HỌC

PHÂN LOẠI VĂN BẢN CHO
HỆ THỐNG THU THẬP TIN TỨC TIẾNG VIỆT

NGÀNH CÔNG NGHỆ THÔNG TIN

MÃ SỐ:

Người hướng dẫn khoa học: TS. LÊ THANH HƯƠNG

HÀ NỘI - 2009


Phân loại văn bản cho hệ thống thu thập tin tức tiếng Việt

MỤC LỤC
MỤC LỤC ............................................................................................................. 1
DANH MỤC BẢNG ............................................................................................. 4
DANH MỤC HÌNH .............................................................................................. 5
MỞ ĐẦU ............................................................................................................... 6
CHƯƠNG I ........................................................................................................... 8
TỔNG QUAN VỀ KHAI PHÁ VĂN BẢN.......................................................... 8
1.1. Khai phá dữ liệu văn bản (Text mining) .................................................... 8
1.2. Các bước khai phá dữ liệu văn bản .......................................................... 10
1.2.1 Tiền xử lý văn bản .............................................................................. 10
1.2.2 Khai phá văn bản/dữ liệu ....................................................................... 10
1.2.3 Ứng dụng kết quả khai phá dữ liệu văn bản trong thực tiễn .............. 11
1.3. Bài toán phân loại văn bản (Text categorization) .................................... 11
1.3.1 Bài toán phân loại văn bản ................................................................. 11
Hình 1.1: Các cơng việc trong phân loại văn bản ............................................... 14
1.3.2 Một số phương pháp phân loại văn bản ............................................. 16
1.4. Kết chương ............................................................................................... 18
CHƯƠNG II ........................................................................................................ 19
TÁCH TỪ VÀ BIỂU DIỄN VĂN BẢN TIẾNG VIỆT ..................................... 19
2.1. Một số phương pháp tách từ trong văn bản tiếng Việt ............................ 19
2.1.1 Các đặc trưng của văn bản ................................................................. 19

2.1.2 Một số đặc trưng của tiếng Việt ......................................................... 20
2.1.3 Một số phương pháp tách từ .............................................................. 26
Hình 2.2. Phương pháp xây dựng ơtơmát âm tiết ........................................... 28
Hình 2.4: Một tình huống nhập nhằng ............................................................ 30
Hình 2.6: Một ví dụ về đồ thị của mơ hình HMM bậc 2 ................................ 36
2.2. Phương pháp biểu diễn văn bản ............................................................... 40
2.2.1 Các kỹ thuật trích chọn đặc trưng của văn bản .................................. 41
2.2.2 Một số phương pháp biểu diễn văn bản bằng mơ hình khơng gian
vector ........................................................................................................... 46
Bùi Mạnh Hoàng

1

Luận văn Thạc sĩ


Phân loại văn bản cho hệ thống thu thập tin tức tiếng Việt
2.3. Kết chương ............................................................................................... 50
CHƯƠNG III....................................................................................................... 51
MỘT SỐ PHƯƠNG PHÁP ................................................................................. 51
PHÂN LOẠI VĂN BẢN TRUYỀN THỐNG .................................................... 51
3.1 Cây quyết định .......................................................................................... 51
3.1.1 Thuật toán ID3 ................................................................................... 54
3.1.2 Cách lựa chọn thuộc tính tốt nhất ...................................................... 55
3.1.3 Hiện tượng vượt ngưỡng .................................................................... 57
3.2 K-láng giềng gần nhất (K-Nearest Neighbor) ........................................... 58
3.2.1 Gán nhãn văn bản gần nhất ................................................................ 59
3.2.2 Gán nhãn theo số đông ....................................................................... 60
3.2.3 Gán nhãn theo độ phù hợp của chủ đề ............................................... 61
3.3 Kết chương ................................................................................................ 62

CHƯƠNG IV ...................................................................................................... 64
PHƯƠNG PHÁP PHÂN LOẠI VĂN BẢN ....................................................... 64
SUPPORT VECTOR MACHINES .................................................................... 64
4.1 Lý thuyết học thống kê .............................................................................. 64
4.1.1 Chiều VC (Vapnik Chervonenkis dimension) .................................. 64
4.1.2 Rủi ro của bài toán học phân loại có giám sát ................................... 65
4.1.3 Rủi ro thực nghiệm............................................................................ 66
4.1.4 Nguyên tắc tối thiểu rủi ro cấu trúc.................................................... 67
4.1.5 Định lý 4.1 .......................................................................................... 68
4.2 Support Vector Machines .......................................................................... 68
4.3 Phương pháp giải bài toán QP.................................................................. 78
4.3.1 Thuật toán tối ưu ................................................................................ 78
4.3.2 Thuật toán khởi tạo các biến α i0 ......................................................... 81
4.4 Đánh giá : .................................................................................................. 82
4.5 Kết chương ............................................................................................... 84
CHƯƠNG V ........................................................................................................ 85
CHƯƠNG TRÌNH VÀ KẾT QUẢ THỰC NGHIỆM ........................................ 85
5.1 Xây dựng hệ thống tống hợp tin tức tự động ............................................ 85
5.1.1 Đặt vấn đề........................................................................................... 85
Bùi Mạnh Hoàng

2

Luận văn Thạc sĩ


Phân loại văn bản cho hệ thống thu thập tin tức tiếng Việt
5.1.2 Mơ hình hệ thống: .............................................................................. 86
5.2 Xây dựng hệ thống .................................................................................... 86
5.2.1 Ngôn ngữ cài đặt chương trình .......................................................... 86

5.2.2 Thu thập tin tức từ các site: ................................................................ 86
5.2.3 Xây dựng bộ lọc trích rút thơng tin: ................................................... 88
5.2.4 Chương trình hiển thị ......................................................................... 92
5.2.5 Kết quả xây dựng ............................................................................... 92
5.3. Kết quả thực nghiệm việc phân loại văn bản ........................................... 94
5.4 Kết luận ..................................................................................................... 99
KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN CỦA LUẬN VĂN ......................... 100
6.1 Kết luận ................................................................................................... 100
6.2 Hướng phát triển của luận văn ................................................................ 101
TÀI LIỆU THAM KHẢO ................................................................................. 103

Bùi Mạnh Hoàng

3

Luận văn Thạc sĩ


Phân loại văn bản cho hệ thống thu thập tin tức tiếng Việt

DANH MỤC BẢNG
Bảng 2.1

Thông tin về tập huấn luyện của mơ hình ………………………… 38

Bảng 2.2

Kết quả đánh giá độ chính xác của mơ hình Markov ẩn ………… 38

Bảng 2.3


Một số từ dừng trong văn bản tiếng Việt …………………………… 42

Bảng 2.4

Một số hàm tính tốn giá trị thơng tin của từ trong phân loại ……46

Bảng 3.1

Biểu diễn văn bản bằng vector nhị phân ……………………………. 54

Bảng 3.2

Ví dụ 1 về độ tương tự giữa văn bản và chủ đề …………………….. 62

Bảng 3.3

Ví dụ 2 về độ tương tự giữa văn bản và chủ đề ……………………. 63

Bảng 3.4

Ví dụ 3 về độ tương tự giữa văn bản và chủ đề …………………….. 63

Bảng 3.5

Ví dụ 4 về độ tương tự giữa văn bản và chủ đề …………………….. 64

Bùi Mạnh Hoàng

4


Luận văn Thạc sĩ


Phân loại văn bản cho hệ thống thu thập tin tức tiếng Việt

DANH MỤC HÌNH
Hình 2.1

Sơ đồ chuyển trạng thái giữa các ký tự …………………….............. 29

Hình 2.2

Phương pháp xây dựng ôtômát âm tiết …………………………….. 29

Hình 2.3

Phương pháp xây dựng ôtômát từ ………………………………….. 30

Hình 2.4

Một tình huống nhập nhằng ………………………………………... 31

Hình 2.5

Một ví dụ về đồ thị của HMM bậc 1 ………...………………………. 36

Hình 2.6

Một ví dụ về đồ thị của HMM bặc 2 ………...………………………. 37


Hình 3.1

Xây dựng cây quyết định cho tập mẫu dùng để huấn luyện …….... 55

Hình 3.2

Quá trình tìm kiếm lời giải trên cây quyết định ……...……………. 56

Hình 4.1

Minh họa chiều VC của tập hàm {f(x)} trong không gian 2 chiều ... 67

Hình 4.2

Siêu phẳng phân chia tập mẫu huấn luyện ………...……………… 71

Hình 4.3

Siêu phẳng phân chia dữ liệu và các ràng buộc ………………….. 72

Hình 4.4

Trường hợp dữ liệu có nhiễu ………..……………………………….. 76

Bùi Mạnh Hồng

5

Luận văn Thạc sĩ



Phân loại văn bản cho hệ thống thu thập tin tức tiếng Việt

MỞ ĐẦU
Trong những năm gần đây phân loại văn bản đã trở thành một kỹ thuật
then chốt để tổ chức thơng tin trực tuyến. Nó có thể được sử dụng để tổ chức cơ
sở dữ liệu văn bản, lọc thư điện tử, tìm kiếm thơng tin quan tâm trên Web, hoặc
để chỉ dẫn người dùng tìm kiếm thơng tin qua các siêu văn bản (hypertext). Mà
ở đó, việc phân loại văn bản bằng tay là không thể thực hiện được, hoặc thực
hiện với chi phí tốn kém nhất. Do đó, cùng với sự phát triển của thơng tin trực
tuyến, một yêu cầu cấp thiết đặt ra là cần phải xây dựng hệ thống phân loại văn
bản tự động.
Cho đến nay, đã có nhiều đề xuất xây dựng bài toán phân loại văn bản tự
động như Neive Bayes, Bayes net, k-láng giềng gần nhất, cây quyết định, mạng
nơron, Support Vector Machines, … Các phương pháp phân loại này, đạt được
những thành công đáng kể đối với các văn bản tiếng Anh, Pháp, Nhật, Trung
Quốc, và đã được ứng dụng trong thực tế như trong các hệ tìm tin của Yahoo,
Altavista, Google, … Trong đó, Support Vector Machines là một cách tiếp cận
mới và cho độ chính xác của phân loại văn bản cao hơn hẳn các phương pháp
phân loại khác.
Ở Việt Nam, cũng đã có nhiều nghiên cứu về lĩnh vực xử lý văn bản tiếng
Việt, như đề tài nghiên cứu về Máy dịch tự động Anh – Việt (EVTRan) của viện
nghiên cứu ứng dụng công nghệ; đề tài nhận dạng, xử lý tiếng Việt VnDoc của
Viện Công nghệ thông tin, và nhiều luận văn tốt nghiệp cao học và đại học khác.
Nhưng các nghiên cứu về phân loại văn bản tiếng Việt chưa nhiều, và kết quả
còn hạn chế. Bởi vậy, trong luận văn này chúng tôi sẽ tập trung nghiên cứu bài
toán phân loại văn bản tiếng Việt dựa trên cách tiếp cận Support Vector
Machines.


Bùi Mạnh Hoàng

6

Luận văn Thạc sĩ


Phân loại văn bản cho hệ thống thu thập tin tức tiếng Việt
Một vấn đề liên quan mật thiết đến tốc độ xử lý cũng như độ chính xác
của quá trình phân loại là số chiều của các vector biểu diễn văn bản. Nếu dùng
toàn bộ các từ trong từ điển làm đặc trưng để biểu diễn văn bản thì mỗi văn bản
tiếng Việt được biểu diễn bằng một vector có hơn 70 nghìn chiều (tương đương
với số từ trong từ điển tiếng Việt). 70 nghìn là con số quá lớn khi mà có tới hàng
triệu văn bản cần xử lý trong quá trình phân loại. Để tăng tốc độ xử lý và độ
chính xác của kết quả phân loại văn bản, trong luận văn này chúng tơi trình bày
một phương pháp lựa chọn các từ đặc trưng để biểu diễn văn bản tiếng Việt.
Cuối cùng, chúng tôi xây dựng một chương trình thực nghiệm nhằm đánh giá
hiệu quả của phương pháp Support Vector Machines đối với bài toán phân loại
văn bản tiếng Việt.
Nội dung luận văn bao gồm 6 chương:
- Chương I: Trình bày tổng quan về khai phá dữ liệu văn bản và bài toán
phân loại văn bản.
- Chương II: Trình bày các vấn đề của qúa trình tiền xử lý văn bản tiếng
Việt (tách từ, lựa chọn đặc trưng, biểu diễn văn bản). Và đề xuất một
phương pháp lựa chọn từ đặc trưng của chúng tôi.
- Chương III: Một số phương pháp phân loại văn bản truyền thống.
- Chương IV: Phương pháp phân loại văn bản dựa trên cách tiếp cận
Support Vector Machines.
- Chương V: Chương trình và kết quả thực nghiệm.
- Chương VI: Kết luận và hướng phát triển của luận văn.


Bùi Mạnh Hoàng

7

Luận văn Thạc sĩ


Phân loại văn bản cho hệ thống thu thập tin tức tiếng Việt

CHƯƠNG I
TỔNG QUAN VỀ KHAI PHÁ VĂN BẢN
Mục đích của chương này là giới thiệu một cách tóm tắt về vấn đề khai
phá dữ liệu văn bản, bài toán phân loại văn bản.
 Khai phá dữ liệu văn bản là gì?
 Các bước để xây dựng bài tốn khai phá dữ liệu văn bản.
 Bài toán phân loại văn bản
1.1. Khai phá dữ liệu văn bản (Text mining)
Văn bản là một trong những dạng dữ liệu phổ biến nhất, hiện nay, nó có
mặt ở khắp mọi nơi và chúng ta thường xuyên bắt gặp hàng ngày. Do đó, các bài
toán xử lý văn bản đã được đặt ra từ khá lâu và cho đến nay vẫn là một trong
những vấn đề hay trong khai phá dữ liệu văn bản (text), trong đó có những bài
tốn đáng chú ý như tìm kiếm văn bản, phân loại văn bản, phân cụm văn bản,
hoặc dẫn đường văn bản, ...
Các văn bản được tập hợp trong cơ sở dữ liệu văn bản và có thể chia làm
hai loại:
- Dạng khơng có cấu trúc (unstructured): Những văn bản thông thường mà
chúng ta thường đọc hàng ngày được thể hiện dưới dạng ngôn ngữ tự
nhiên của con người và nó khơng có một cấu trúc định dạng nào.
- Dạng bán cấu trúc (semi-structured): Những văn bản được tổ chức dưới

dạng cấu trúc không chặt chẽ thành bản ghi mà dùng các kí hiệu đánh dấu
văn bản và vẫn thể hiện được nội dung chính của văn bản, ví dụ như các
dạng HTML, email,...
Trong luận văn này, chúng tôi chỉ quan tâm xử lý dữ liệu văn bản ở dạng
phi cấu trúc (biểu diễn dưới dạng tập tin TXT), bài toán được giải quyết theo
Bùi Mạnh Hoàng

8

Luận văn Thạc sĩ


Phân loại văn bản cho hệ thống thu thập tin tức tiếng Việt
hướng dữ liệu mở để tương lai có thể áp dụng với các mục đích sử dụng khác
nhau.
Có nhiều cách phân lớp các lĩnh vực trong xử lý văn bản, Lewis đã chia
thành hai nhóm lĩnh vực chính là Phân lớp văn bản (Text Classification) gồm
các công việc xác định văn bản hoặc một phần của văn bản vào một hay nhiều
lớp xác định trước và Hiểu nghĩa văn bản (Text Understanding) bao gồm các
công việc phức tạp hơn để xử lý nội dung của văn bản như tóm tắt văn bản (Text
Summarization hoặc Abstraction), trích chọn thơng tin (Text Extraction), ... Tuy
nhiên, việc phân làm hai lớp cũng không thật rõ ràng, trong các hệ phần mềm,
người ta thường kết hợp hai lớp bài toán trên để thành một hệ như trong các hệ
tìm kiếm (Search Engine), hoặc trong bài tốn tìm kiếm văn bản (Text
Retrieval), một trong những lĩnh vực được quan tâm nhất hiện nay. Chẳng hạn
trong hệ tìm kiếm như Yahoo, Altavista, Google... đều tổ chức dữ liệu theo các
nhóm và thư mục, mỗi nhóm lại có thể có nhiều nhóm con nằm trong nó. Hệ
phần mềm tìm kiếm của Altavista cịn tích hợp thêm chương trình dịch tự động
có thể dịch chuyển đổi sang nhiều thứ tiếng khác nhau và cho kết quả khá tốt.
Khai phá văn bản (Text mining) là một nhánh của khai phá dữ liệu (Data

mining), có mục đích là phát hiện và trích rút thơng tin từ các tài liệu văn bản
(text documents). Khai phá văn bản liên quan tới các vấn đề như: xử lý ngôn
ngữ tự nhiên, trích rút thơng tin, tìm kiếm thơng tin, khai phá Web, ...
Text Mining = Data Mining (applied to text data)
+ Language Engineering

Bùi Mạnh Hoàng

9

Luận văn Thạc sĩ


Phân loại văn bản cho hệ thống thu thập tin tức tiếng Việt
1.2. Các bước khai phá dữ liệu văn bản
1.2.1 Tiền xử lý văn bản
Mục đích của q trình tiền xử lý văn bản là để đưa ra cách biểu diễn văn
bản thích hợp nhất. Các bước của quá trình tiền xử lý văn bản bao gồm:
- Phân tích ngữ pháp/ngữ nghĩa của văn bản: tìm từ loại, loại bỏ sự nhập nhằng
về ngữ nghĩa, phân tích ngữ pháp.
- Sinh ra các tập các từ (còn gọi là túi từ - bag of words): Biểu diễn văn bản bởi
các từ xuất hiện trong văn bản đó, nhận dạng từ, loại bỏ các từ dừng (stop
words, là những từ không có ích cho khai phá văn bản). Ví dụ, một số từ dừng
trong các văn bản tiếng Việt là: và, vì vậy, tóm lại, nếu, chẳng hạn, …
- Lựa chọn các từ: Sau khi đã loại bỏ các từ dừng, quá trình giảm số chiều của
việc biểu diễn văn bản được thực hiện bằng cách loại bỏ những đặc trưng khơng
thích hợp. Việc lựa chọn các đặc trưng của văn bản liên quan đến trọng số của
từ xuất hiện trong văn bản đó. Trọng số của từ là độ quan trọng, hay hàm lượng
thơng tin mà từ đó mang lại cho văn bản. Nó là đại lượng dùng để đo sự khác
biệt giữa văn bản chứa nó với các văn bản khác. Đại lượng này có thể được xác

định bằng tay hoặc đánh giá bằng số lần xuất hiện của từ đó trong văn bản và số
lần xuất hiện của từ đó trong các văn bản khác. Số lần xuất hiện của từ trong văn
bản càng nhiều thì độ quan trọng của nó trong văn bản càng lớn và ngược lại.
1.2.2 Khai phá văn bản/dữ liệu
Một số bài toán của khai phá dữ liệu văn bản là:
- Phân loại văn bản (Text Categorization): Cho một số lớp văn bản đã được
xác định trước, nhiệm vụ của phân loại văn bản là: gán các văn bản vào một
(hay một số) lớp văn bản thích hợp dựa vào nội dung của văn bản.
- Lập nhóm văn bản (Text Clustering): Cho một số văn bản, nhiệm vụ của lập
nhóm văn bản là chia các văn bản này thành các nhóm thích hợp căn cứ vào
sự tương tự về mặt nội dung giữa các văn bản.
Bùi Mạnh Hoàng

10

Luận văn Thạc sĩ


Phân loại văn bản cho hệ thống thu thập tin tức tiếng Việt
- Tóm tắt văn bản (Text Summarization): Tóm tắt, chắt lọc thông tin từ một
(hay nhiều) nguồn để đưa ra một mô tả ngắn gọn, cô đọng thông tin từ nguồn
tài liệu đó.
- Phát hiện xu hướng nổi bật (Emerging Trend Detection): Phát hiện các chủ
đề sẽ được quan tâm và có ích trong tương lai.
- Trả lời câu hỏi: Đưa ra câu trả lời thích hợp cho câu hỏi (tìm tài liệu thích
hợp cho câu hỏi).
- ...
1.2.3 Ứng dụng kết quả khai phá dữ liệu văn bản trong thực tiễn
Ứng dụng các kết quả khai phá dữ liệu văn bản là sử dụng các kết quả
khai thác văn bản cho những mục đích cụ thể. Kết quả của q trình khai phá dữ

liệu văn bản có thể sử dụng cho việc trích lọc thơng tin, tóm tắt thơng tin, dịch
tự động văn bản, dự đốn các xu hướng trong tương lai, tìm kiếm thơng tin,
phân loại thơng tin, ... Và các ứng dụng này lại được sử dụng như một công cụ
hỗ trợ trong các hệ thống thơng tin khác. Ví dụ, chương trình dịch tự động văn
bản được sử dụng trong hệ phần mềm tìm kiếm của Altavista để có thể dịch
chuyển đổi văn bản sang nhiều thứ tiếng khác nhau. Các kết quả của quá trình
phân loại thơng tin, trích chọn thơng tin, tìm kiếm văn bản có thể được trong
việc tổ chức, phân loại thơng tin trong các hệ tìm kiếm để mang lại hiệu quả cao
trong việc tìm kiếm thơng tin ...
1.3. Bài toán phân loại văn bản (Text categorization)
1.3.1 Bài toán phân loại văn bản
Phân loại văn bản là quá trình gán nhãn văn bản vào một (hay một số)
chủ đề cho trước, dựa trên nội dung của văn bản.
Trong những thập kỷ 80 hầu hết các cách tiếp cận (ít nhất là trong việc
thiết đặt thao tác) để phân loại văn bản tự động gồm các kỹ thuật điều khiển
Bùi Mạnh Hoàng

11

Luận văn Thạc sĩ


Phân loại văn bản cho hệ thống thu thập tin tức tiếng Việt
bằng tay bởi chuyên gia tri thức (Knowledge Engineering - KE), một hệ thống
chuyên gia có khả năng đưa ra quyết định phân loại. Hệ chuyên gia bao gồm
một tập các luật logic định nghĩa bằng tay, cho mỗi loại, có dạng:
If(DNF formula) then (category).
Một cơng thức DNF (“Disjunctive Normal Form”) là hợp của các mệnh
đề liên kết, tài liệu được phân loại vào category nếu nó thỏa mãn cơng thức,
nghĩa là, nếu nó thỏa mãn ít nhất một mệnh đề trong cơng thức. Một ví dụ nổi

tiếng cho cách tiếp cận này là hệ thống CONSTRUE [Hayes et al. 1990], xây
dựng bởi Carnegie Group cho tập tin tức Reuters. Sau đây, là một ví dụ về luật
được sử dụng trong CONSTRUE:
If

((wheat & farm) or (wheat & commodity)
or (bushels & export) or (wheat & tonnes)
or (wheat & winter & ¬ soft))

then WHEAT
else ¬ WHEAT
Điều trở ngại của cách tiếp cận này là hạn chế trong quá trình thu nhận tri
thức từ tài liệu của các hệ thống chuyên gia. Nghĩa là, các luật phải được định
nghĩa bằng tay bởi kỹ sư tri thức với sự giúp đỡ của chuyên gia về lĩnh vực được
nêu trong tài liệu: nếu tập hợp của các loại được cập nhật, thì hai nhà chuyên
nghiệp phải can thiệp lại, và nếu phân loại được chuyển hoàn toàn sang một
phạm vi khác, một chuyên gia về lĩnh vực này cần thiết phải can thiệp vào và
công việc phải được bắt đầu lại từ tập tài liệu hỗn tạp ban đầu.
Đầu thập kỷ 90, cách tiếp cận học máy (Machine Learning) để phân loại
văn bản được coi là nổi tiếng và trở thành thống trị, ít nhất là trong cộng đồng
người nghiên cứu (Mitchell, 1996), Theo cách tiếp cận này, một quá trình xử lý
quy nạp chung (cũng được gọi là quá trình học) xây dựng tự động một phân lớp
cho một loại ci bằng quan sát các đặc trưng của tập hợp các tài liệu đã được phân
Bùi Mạnh Hoàng

12

Luận văn Thạc sĩ



Phân loại văn bản cho hệ thống thu thập tin tức tiếng Việt
bằng tay vào ci hay ci bởi chuyên gia về lĩnh vực này; từ đó, q trình qui nạp
thu lượm các đặc trưng để phân loại một tài liệu mới (khơng nhìn thấy) vào ci.
Trong kỹ thuật học máy, bài tốn phân lớp là hoạt động học có giám sát, quá
trình học được “giám sát” bởi tri thức của các phân loại và của các mẫu huấn
luyện thuộc chúng.
Với phương pháp học máy, sự cố gắng về phương diện công việc của kỹ
sư theo hướng không phải xây dựng một phân lớp mà xây dựng một phân lớp tự
động (học) từ một tập hợp các tài liệu đã được phân loại bằng tay. Trong các
tiếp cận học máy, các tài liệu đã được phân lớp trở thành nguồn. Trường hợp
thuận lợi nhất, chúng đã có sẵn, khi đó quá trình phân loại bắt đầu bằng việc học
từ tập dữ liệu này, sau đó sẽ thực hiện phân loại tự động với các tài liệu khác.
Trường hợp ít thuận lợi, khơng có sẵn tài liệu đã phân loại bằng tay; khi đó q
trình phân loại bắt đầu một hành động phân loại và chọn một phương pháp tự
động ngay lập tức. Do đó, cách tiếp cận học máy là thuận lợi hơn cách tiếp cận
kỹ sư tri thức.
Các phân lớp xây dựng theo nghĩa của kỹ thuật học máy ngày nay gây
được ấn tượng sâu sắc về mức độ hiệu quả, khiến cho phân lớp tự động trở thành
một lựa chọn tốt để thay thế phân loại bằng tay (khơng chỉ về phương diện kinh
tế). Chúng ta có thể hình dung các cơng việc của bài tốn phân loại văn bản dựa
trên kỹ thuật học máy như sau:

Bùi Mạnh Hoàng

13

Luận văn Thạc sĩ


Phân loại văn bản cho hệ thống thu thập tin tức tiếng Việt


BIỂU DIỄN BAN ĐẦU

DỮ LIỆU
VĂN BẢN

Biểu diễn ban đầu
của văn bản

TRI THỨC THÊM

GIẢM SỐ CHIỀU
HOẶC

VÀO

LỰA CHỌN THUỘC TÍNH

QUẾT ĐỊNH
HỌC QUY NẠP

PHÂN LOẠI

Biểu diễn cuối cùng

Hình 1.1: Các cơng việc trong phân loại văn bản

Cách tiếp cận học máy dựa trên một tập dữ liệu có sẵn từ đầu Ω={d1, …, d|Ω|} ⊂
D, trong đó D tập tất cả các tài liệu đã được phân lớp trước, dj là văn bản thứ j,



Tập các lớp C={c1, …, c|C|}, ci là kí hiệu của lớp thứ i. Hàm Φ : D × C → {T , F } với


mọi d j , ci ∈ Ω × C . Một tài liệu dj là mẫu dương của ci nếu Φ(d j , ci ) = T , là một


mẫu âm nếu Φ(d j , ci ) = F .
Với mỗi cách phân loại được đưa ra, người ta mong muốn đánh giá được
hiệu quả phân loại của chúng. Bởi vậy, trước khi xây dựng phân loại người ta
chia tập dữ liệu ban đầu thành 2 tập hợp.
-

Tập huấn luyện (training (-and-validation) set) Tr={d1, …, d|TV|}. Phân
lớp Φ cho các phân loại C={c1, …, c|C|} được xây dựng quy nạp dựa trên sự
quan sát các đặc trưng của các tài liệu trong Tr.

Bùi Mạnh Hoàng

14

Luận văn Thạc sĩ


Phân loại văn bản cho hệ thống thu thập tin tức tiếng Việt
Tập kiểm tra (test set) Te={d|TV+1|, …d|Ω|}, được sử dụng để kiểm tra hiệu

-

quả của phân lớp. Mỗi dj ∈Te được đưa vào hệ thống phân lớp để xác định



giá trị Φ(d j , ci ) , và so sánh giá trị này với quyết định Φ(d j , ci ) của chuyên


gia. Hiệu quả của phân lớp dựa trên sự phù hợp giữa Φ(d j , ci ) và Φ(d j , ci ) .
Số tài liệu trong tập luyện và tập kiểm tra thường được chọn theo tỷ lệ tương
ứng là 70% và 30%. Trong đó, Tr∩Te =∅ , nếu điều kiện này bị vi phạm thì kết
quả đánh giá hiệu quả của mơ hình mất đi yếu tố khách quan, khoa học.
Phân loại văn bản chủ yếu dựa trên cơ chế trích rút thơng tin. Kỹ thuật
trích rút thơng tin được sử dụng trong 3 giai đoạn của quá trình phân loại văn
bản:
1) Đánh chỉ số: các văn bản ở dạng thô cần được chuyển sang một dạng biểu
diễn nào đó để xử lý. Quá trình này được gọi là quá trình biểu diễn văn bản,
dạng biểu diễn của văn bản phải có cấu trúc và dễ dàng xử lý. Chi tiết về việc
biểu diễn văn bản sẽ được trình bày trong chương 2.
2) Kỹ thuật: kỹ thuật ở đây là phương pháp học để phân loại văn bản, nó thường
được sử dụng trong quá trình xây dựng quy nạp của các phân loại.
3) Đánh giá: đánh giá hiệu quả của các phân lớp được thực hiện.
Sự khác nhau trong các cách tiếp cận trước đây phần lớn là để giải quyết (2)
mặc dù trong một số ít đề xuất cũng sử dụng (1) và (3).
Hầu hết các phương pháp phân loại văn bản dựa trên kỹ thuật học máy hiện
nay đều dựa vào tần xuất xuất hiện (số lần xuất hiện) của từ hoặc cụm từ trong
văn bản, hoặc dựa vào tần xuất xuất hiện của từ trong văn bản và tần xuất văn
bản (số các văn bản trong tập dữ liệu huấn luyện có chứa từ đó). Độ chính xác
của kết quả tách từ có ảnh hưởng rất lớn đến kết quả của phân loại, khơng thể có
một kết quả phân loại tốt nếu như không tách được đúng các từ trong văn bản.
Bởi vậy, một vấn đề quan trọng đối với phân loại văn bản là phải tách được
Bùi Mạnh Hoàng


15

Luận văn Thạc sĩ


Phân loại văn bản cho hệ thống thu thập tin tức tiếng Việt
chính xác các từ trong văn bản. Các văn bản được viết bằng các ngơn ngữ khác
nhau thì có đặc trưng riêng của ngơn ngữ đó, và khơng có một phương pháp
chung nào để tách các từ trong các văn bản được viết bằng các ngôn ngữ khác
nhau. Trong chương sau, chúng tôi sẽ giới thiệu một số phương pháp tách từ
dùng cho các văn bản tiếng Việt, phục vụ cho các bước tiền xử lý của bài tốn
phân loại văn bản.
Tóm lại, một bài tốn phân loại văn bản dựa trên kỹ thuật học máy gồm
các bước sau:
- Chuẩn bị tập dữ liệu huấn luyện (Training Set) và tập dữ liệu kiểm tra
(Test Set).
- Tách từ trong văn bản.
- Biểu diễn văn bản
- Phương pháp học để phân loại văn bản
- Đánh giá hiệu quả của phương pháp học
1.3.2 Một số phương pháp phân loại văn bản
Có nhiều phương pháp phân loại văn bản được đề xuất, sự khác nhau cơ
bản giữa các phương pháp này là ở thuật toán học quy nạp. Nhiều thực nghiệm
cho thấy các phương pháp như: cây quyết định (decision tree), k-láng giềng gần
nhất (k-nearest neighbors), phương pháp sử dụng các vector hỗ trợ (Support
Vector Machines) là những phương pháp có hiệu quả phân loại cao. Ở Việt Nam
cũng đã có một số nghiên cứu sử dụng các phương pháp cây quyết định, k-láng
giềng gần nhất để phân loại các văn bản tiếng Việt.
- Phương pháp cây quyết định: Ý tưởng của phương pháp này là xây dựng một
cây phân quyết định gồm các nút và các cung trọng số liên kết giữa các nút

cụ thể: Các nút trong được gián nhãn bởi các từ, nhãn của các cung tương
ứng với trọng số của từ trong tài liệu mẫu, nhãn của các lá tương ứng với
nhãn của các lớp. Cho một tài liệu dj, ta sẽ thực hiện so sánh các nhãn của
Bùi Mạnh Hoàng

16

Luận văn Thạc sĩ


Phân loại văn bản cho hệ thống thu thập tin tức tiếng Việt
cung xuất phát từ một nút trong (tương ứng với một từ nào đó) với trọng số
của từ này trong dj, để quyết định nút trong nào sẽ được duyệt kế tiếp. Quá
trình này được lặp từ nút gốc của cây, cho tới khi nút được duyệt là một lá
của cây. Kết thúc quá trình này, nhãn của nút lá sẽ là nhãn của lớp được gán
cho văn bản.
- Phương pháp k-láng giềng gần nhất: Tư tưởng chính của phương pháp này
là tính độ phù hợp của văn bản đang xét với từng nhóm chủ đề dựa trên k văn
bản mẫu có độ tương tự gần nhất.
- Phương pháp Support Vector Machines: Phương pháp này xuất phát từ suy
nghĩ, làm thế nào để tối thiểu lỗi trong quá trình kiểm tra (test error
minimization). Bởi vậy, ý tưởng của Support Vector Machines (SVMs) là tìm
một siêu phẳng tối ưu để phân chia tập dữ liệu huấn luyện sao cho các văn
bản thuộc lớp ci thuộc về phía của siêu phẳng, cịn các văn bản khơng thuộc
lớp ci sẽ thuộc về phía bên kia của siêu phẳng. Một siêu phẳng được gọi là tối
ưu nếu khoảng cách từ mẫu gần nhất đến siêu phẳng là lớn nhất.
Các phương pháp như cây quyết định, k-láng giềng gần nhất có ưu điểm là dễ
hiểu, dễ xây dựng về mặt thuật toán, ... nhưng cây quyết định được xây dựng sẽ
phức tạp khi vector dùng để biểu diễn văn bản có số chiều q lớn, cịn với kláng giềng gần chúng ta khơng có một giải pháp tuyệt đối trong việc lựa chọn
phương pháp xác định độ tương tự gữa văn bản và chủ đề. Hiệu quả của các

phương pháp này tăng khi tập dữ liệu huấn luyện có chứa nhiều văn bản.
Phương pháp SVMs tuy phức tạp về mặt xây dựng thuật tốn nhưng hiệu quả
phân loại khơng phụ thuộc vào số chiều của vector biểu diễn văn bản, và có thể
cho kết quả phân loại tốt mà không cần quá nhiều văn bản để huấn luyện. Quan
trọng hơn cả, nhiều kết quả thực nghiệm [16], [14], ... cho thấy so với các
phương pháp phân loại văn bản truyền thống (như cây quyết định, k-láng giềng
gần nhất, ...), SVMs là phương pháp phân loại văn bản đạt hiệu quả cao hơn.
Bùi Mạnh Hoàng

17

Luận văn Thạc sĩ


Phân loại văn bản cho hệ thống thu thập tin tức tiếng Việt
Do đó, trong luận văn này chúng tơi sẽ tập trung vào tìm hiểu phương pháp
SVMs, và áp dụng phương pháp này để phân loại các văn bản tiếng Việt.
1.4. Kết chương
Trong chương này, chúng tơi đã trình bày tóm tắt các bước cần làm của
một bài tốn phân loại văn bản. Trong các chương tiếp theo chúng tơi, sẽ cụ thể
hóa cách làm của từng bước của bài toán phân loại văn bản. Nghiên cứu phương
pháp SVMs và so sánh nó với một số phương pháp phân loại văn bản khác. Cuối
cùng là kết quả thực nghiệm của luận văn, dùng phương pháp Support Vector
Machines để phân loại các văn bản tiếng Việt.

Bùi Mạnh Hoàng

18

Luận văn Thạc sĩ



Phân loại văn bản cho hệ thống thu thập tin tức tiếng Việt

CHƯƠNG II
TÁCH TỪ VÀ BIỂU DIỄN VĂN BẢN TIẾNG VIỆT
Để máy tính có thể tự động phân loại văn bản, thì các văn bản được trình
bày dưới dạng chuỗi các ký tự cần phải được biến đổi thành một mơ tả thuận lợi
cho thuật tốn huấn luyện và bài toán phân loại, nghĩa là văn bản được chuyển
từ dạng khơng có cấu trúc (hoặc bán cấu trúc) sang dạng có cấu trúc. Có rất
nhiều cách biểu diễn văn bản, nhưng dù theo cách này hay cách khác thì việc
biểu diễn văn bản đều dựa vào sự xuất hiện của từ trong văn bản. Do đó, cơng
việc đầu tiên và có ảnh hưởng lớn đến chất lượng của quá trình phân loại là kết
quả của việc tách từ trong văn bản. Tiếng Việt có những đặc điểm riêng về cấu
tạo của từ, cấu trúc ngữ pháp. Nên việc tách từ trong văn bản tiếng Việt cũng
địi hỏi có những phương pháp đặc trưng. Trong chương này, chúng tôi sẽ trình
bày chi tiết các bước tiền xử lý chuẩn bị cho việc phân loại văn bản tiếng Việt.
 Một số phương pháp tách từ trong văn bản tiếng Việt.
 Cách trích chọn đặc trưng để biểu diễn văn bản.
 Một số phương pháp biểu diễn văn bản.
2.1. Một số phương pháp tách từ trong văn bản tiếng Việt
2.1.1 Các đặc trưng của văn bản
- Nhiều chiều: Số lượng từ dùng để biểu diễn văn bản là rất lớn (hơn 10000).
- Có tính phụ thuộc: Các từ, các câu trong văn bản khơng hồn tồn độc lập
với nhau, chúng có liên quan với nhau về mặt ngữ nghĩa. Để hiểu chính xác ý
nghĩa diễn đạt của một từ nào đó trong văn bản ta cần phải xem xét nó trong
một ngữ cảnh cụ thể.
- Nhập nhằng: Sự nhập nhằng ở đây là do tính đa nghĩa của từ, một từ có thể
có nhiều nghĩa. Thậm trí một câu cũng có thể diễn đạt nhiều ý khác nhau, mà
Bùi Mạnh Hoàng


19

Luận văn Thạc sĩ


Phân loại văn bản cho hệ thống thu thập tin tức tiếng Việt
để hiểu được câu đó chúng ta phải đặt nó trong một văn cảnh cụ thể. Ví dụ
câu “Ơng già đi nhanh q”, có thể hiểu theo nghĩa một ơng già đi với tốc độ
nhanh, nhưng cũng có thể hiểu theo nghĩa một ơng nào đó nhìn già đi nhiều.
- Dữ liệu nhiễu: Dữ liệu nhiễu có thể là do viết sai chính tả, hoặc do từ trong
văn bản không được cập nhật trong từ điển.
- Cấu trúc của văn bản đa dạng: Mỗi loại văn bản (như viết thư, văn bản hành
chính, văn xi, ...), có những bố cục đặc trưng riêng.
Tóm lại, văn bản có những đặc điểm sau: Cấu trúc văn bản rất đa dạng, có
nhiều văn bản khơng có một cấu trúc cụ thể. Người viết trình độ kém, sai chính
tả, cấu trúc khơng mạch lạc.
2.1.2 Một số đặc trưng của tiếng Việt
Tiếng Việt là ngơn ngữ đơn âm tiết, và thuộc nhóm ngơn ngữ Đơng Nam
Á. Nó có đặc điểm riêng về ký hiệu, ngữ pháp và ngữ nghĩa, khác với các ngôn
ngữ Ấn-Âu. Đây khơng chỉ là khó khăn đối với việc học các ngơn ngữ Châu Âu,
mà cịn là khó khăn trong việc ứng dụng các kỹ thuật phát triển để xử lý ngôn
ngữ tự nhiên. Mặt khác, dù là ngôn ngữ đơn âm tiết nhưng không giống như các
ngôn ngữ đơn âm tiết khác như Trung Quốc, Thái, tiếng Việt được viết bằng các
ký tự Lating mở rộng. Vì vậy, cách thực hiện của các ngôn ngữ này cũng không
thể ứng dụng cho tiếng Việt, và hiện tại một trong số các việc còn chưa được
giải quyết trong xử lý ngơn ngữ tự nhiên của tiếng Việt là bài tốn xác định các
biên giới của từ (word boundaries) trong văn bản tiếng Việt.
1.2.2.1 Đặc điểm từ
Với các ngôn ngữ Ấn-Âu (như tiếng Anh, Pháp, ..), “từ là một nhóm của các

ký tự có nghĩa, phân cách nhau bởi khoảng trống hoặc các dấu câu” (định nghĩa
trong từ điển Webster). Trong khi đó, các ngơn ngữ Châu Á như Trung Quốc,
Thái, Việt Nam, … khoảng trống không được sử dụng để xác định các biên giới
Bùi Mạnh Hoàng

20

Luận văn Thạc sĩ


Phân loại văn bản cho hệ thống thu thập tin tức tiếng Việt
từ. Phần nằm giữa hai dấu phân cách là tiếng, mỗi tiếng có thể được coi là từ
cũng có khi khơng phải là từ. Cụ thể, chúng tơi sẽ trình bày một số đặc điểm của
từ trong tiếng Việt. Các định nghĩa về từ và tiếng của tiếng Việt trong phần này
được trích dẫn từ bộ sách tiếng Việt cấp 2, của nhà xuất bản Giáo Dục.
Tiếng

a)

Ngôn ngữ Việt Nam có một đơn vị đặc biệt gọi là tiếng. Mỗi tiếng trong
tiếng Việt được viết thành một chữ, ngược lại mỗi chữ đọc thành một tiếng, mỗi
chữ nằm giữa hai dấu phân cách trong câu. Tiếng được dùng để tạo thành từ,
tiếng có thể có nghĩa rõ ràng hoặc khơng có nghĩa rõ ràng.Ví dụ:
-

Từ “lạnh lẽo” (có nghĩa): tiếng “lạnh” (có nghĩa), tiếng “lẽo” (nghĩa khơng
rõ).

-


Từ “bồ kết” (có nghĩa): tiếng “bồ” và tiếng “kết” (đều có nghĩa).
Tiếng gồm có ba bộ phận kết hợp lại: âm đầu, vần và thanh. Ví dụ, tiếng

“đà” có âm đầu “đ” vần “a” và thanh “huyền”. Hai bộ phận vần và thanh, tiếng
nào cũng phải có. Âm đầu thì có tiếng có, có tiếng khơng. Ví dụ, tiếng “ở”, chỉ
có vần “ơ” và thanh “hỏi”, khơng có âm đầu. Mỗi bộ phận của tiếng do một âm
hay kết hợp một số âm tạo thành. Bộ phận âm đầu do một âm tạo thành. Âm đầu
là phụ âm. Bộ phận vần có thể do một hoặc 2, 3 âm tạo thành, nhưng bao giờ
cũng phải có một âm chính. Âm chính là nguyên âm. Âm cuối của vần cũng có
thể là phụ âm. Ví dụ, tiếng “nam” có âm đầu là n, âm cuối của vần là phụ âm m,
nguyên âm làm âm chính là a.
Tiếng Việt dùng chữ cái để ghi âm. Mỗi âm được ghi bằng 1 hoặc nhiều
chữ cái ghép lại. Trật tự bảng chữ cái trong tiếng Việt: a, ă, â, b, c, d, đ, e, ê,
g, h, I, k, l, m, n, o, ô, ơ, p, q, r, s, t, u, ư, v, x, y.
b) Từ
Tồn tại nhiều định nghĩa khác nhau về từ trong tiếng Việt, nhưng tất cả các
nghiên cứu ngôn ngữ đều đồng ý từ trong tiếng Việt có những đặc điểm sau
(Đinh Điền, 2001):
Bùi Mạnh Hoàng

21

Luận văn Thạc sĩ


Phân loại văn bản cho hệ thống thu thập tin tức tiếng Việt
1) Từ phải đầy đủ về phương diện hình thức, ngữ nghĩa và độc lập về mặt
ngữ pháp.
2) Từ được xây dựng từ tiếng.
3) Chúng có thể gồm các từ đơn (1-tiếng), hoặc các từ phức (n-tiếng, n<5).

Xét về mặt cấu tạo từ có thể chia thành các loại sau:
-

Từ đơn: do 1 tiếng tạo thành.

-

Từ ghép: do 2, 3 hoặc 4 tiếng tạo thành.

-

Từ láy: là từ do 2 hay nhiều tiếng tiếng lặp lại tạo thành. Các tiếng láy có
thể có một phần hay tồn tồn bộ âm thanh được lặp lại. Ví dụ, lon ton, xinh
xinh, chập chững, nhí nha nhí nhảnh, …
Xét về mặt ngữ loại từ trong tiếng Việt được chia thành một số loại cơ bản

sau:
Danh từ
Là những từ chỉ người hay sự vật. Ví dụ, bàn, ghế, vải vóc, khoa học, kỹ
thuật, Việt Nam, …
Đại từ
Là từ dùng thay thế cho danh từ, hoặc động từ, hoặc tính từ trong câu. Đại từ
chỉ ngôi dùng để xưng hô, thay cho tên gọi khi đối thoại. Ví dụ, tơi, nó, ai, …
Động từ
Là những từ chỉ hoạt động, trạng thái. Nội động từ chỉ hoạt động, trạng thái
của người hay sự vật không tác động hoặc ảnh hưởng đến người hay sự vật
khác. Ngoại động từ chỉ hoạt động của người hay sự vật có tác động, ảnh hưởng
đến người, sự vật khác. Ví dụ: động từ cắt trong câu “Thợ gặt đang cắt lúa” là
ngoại động từ.
Nhận xét:

-

Động từ bị và được chỉ trạng thái tiếp thu.

-

Động từ có chỉ trạng thái tồn tại hoặc sở hữu.

-

Động từ là được dùng trong câu giới thiệu, nhận xét, đánh giá.

Bùi Mạnh Hoàng

22

Luận văn Thạc sĩ


Phân loại văn bản cho hệ thống thu thập tin tức tiếng Việt
Tính từ
Là từ chỉ tính chất (của người, lồi vật, đồ vật, cây cối, …) như: mầu sắc,
hình thể, kích thước, dung lượng, phẩm chất, …
Phụ từ
Là những hư từ chủ yếu đi kèm với động từ, tính từ để biểu thị một số
quan hệ. Phần lớn phụ từ đứng trước động từ, tính từ. Xét về mặt ý nghĩa, phụ
từ không thực hiện được chức năng gọi tên (định danh), mà chỉ làm dấu hiệu cho
một loại ý nghĩa nào đó mà thơi. Phụ từ biểu thị những quan hệ và những ý
nghĩa thường gặp sau đây:
-


Phụ từ (chỉ quan hệ) thời gian

-

Phụ từ (chỉ) thể thức

-

Phụ từ (chỉ ý) khẳng định, phủ định

-

Phụ từ (chỉ ý) mức độ

Ví dụ:
Mai nó mới đi
(phụ từ mới đi kèm với động từ đi chỉ ý khẳng định).
Phụ từ không thể đảm nhiệm vai trị chính của cụm từ, chúng chuyên làm
thành tố phụ trong cụm từ để bổ sung cho thành tố chính một ý nghĩa nào đó. Vì
thế chúng cũng được coi là các từ chứng làm bộc lộ bản chất ngữ pháp của các
từ làm thành tố chính. Đơi khi, nhờ các phụ từ mà ta xác định được từ loại của
từ mà chúng đi kèm. Chẳng hạn:
- Các phụ từ: đã, từng, vừa, mới, đang, sẽ, sắp, …cho ta thấy từ đứng sau
được chúng phụ nghĩa thường là động từ.
- Các phụ từ chỉ mức độ: rất, hơi, …cho ta thấy từ đứng sau được chúng
phụ nghĩa thưưịng là tính từ hoặc động từ chỉ trạng thái tâm lí.
Nhóm từ hãy, chớ, đừng vốn là chứng tố của động từ, khơng xuất hiện được
trước tính từ nói chung. Tuy nhiên cũng có một số trường hợp đặc biệt. Ví dụ:
Có phải dun nhau thì thắm lại

Bùi Mạnh Hoàng

23

Luận văn Thạc sĩ