HỌC VIỆN NGÂN HÀNG

KHOA HỆ THỐNG THÔNG TIN QUẢN LÝ KHOÁ LUẬN
TỐT NGHIỆP ĐẠI HỌC

Đề tài: Phân loại văn bản tiếng Việt sử
dụng phƣơng pháp Máy Hỗ Trợ Vector
(Support Vector Machine – SVMs) Giảng viên hƣớng dẫn : ThS. GIANG THỊ THU HUYỀN
Sinh viên thực hiện : HOÀNG THỊ NHUNG
Lớp : HTTTA


Giảng viên hƣớng dẫn : ThS. GIANG THỊ THU HUYỀN
Sinh viên thực hiện : HOÀNG THỊ NHUNG
Lớp : HTTTA
Khoá : 11 (2008-2012)
Hệ : CHÍNH QUY
Hà Nội, tháng 6/2012

i

HỌC VIỆN NGÂN HÀNG
CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM


3/ Ngày nộp khoá luận : 06/06/2012

GIÁO VIÊN HƢỚNG DẪN
CHỦ NHIỆM KHOA
(Ký, ghi rõ họ tên)
(Ký, ghi rõ họ tên)
ii

MỞ ĐẦU

Sự phát triển trong lĩnh vực Công nghệ thông tin hiện nay là vô cùng lớn lao, đi
đôi với nó là rất nhiều ưu điểm áp dụng trong cuộc sống của loài người chúng ta.
Trong kỷ nguyên công nghệ, mọi thông tin, dữ liệu trao đổi của con người (như dữ liệu
văn bản, âm thanh, hình ảnh, dữ liệu multimedia, …) đều có thể số hoá, lưu trữ và khai
thác trên các thiết bị điện tử, trên máy tính và mạng Internet. Sự phát triển mạnh mẽ
này đã dẫn đến việc mất khả năng kiểm soát thông tin của con người trong các phương
pháp truyền thống.
Nhu cầu về việc khai thác thông tin nhằm lấy ra những tri thức có ích cho con
người là một trong những vấn đề được nêu ra. Đó chính là mảng đề tài về Khai phá dữ
liệu (Data Mining) với các bài toán: Khai phá dữ liệu văn bản (Text Mining), Khai phá
dữ liệu Web (Web Mining), Khai phá dữ liệu đa phương tiện (Multimedia Mining).
Bài toán Khai phá dữ liệu văn bản đóng một vai trò quan trọng trong việc xử lý
thông tin của con người, nó đang được rất nhiều nơi trên thế giới nghiên cứu và phát
triển, áp dụng trên nhiều ngôn ngữ khác nhau. Phân loại văn bản là một trong những
bài toán quan trọng thuộc lĩnh vực khai phá dữ liệu văn bản, nó đã được nghiên cứu và
triển khai thông qua rất nhiều giải thuật khác nhau như: k láng giềng gần nhất (k-NN),

Hoàng Thị Nhung iv

NHẬN XÉT
(Của nơi thực tập)

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

.…………………………………………………………………………………………………
.…………………………………………………………………………………………………
.…………………………………………………………………………………………………
.…………………………………………………………………………………………………
.…………………………………………………………………………………………………
.…………………………………………………………………………………………………
.…………………………………………………………………………………………………
.…………………………………………………………………………………………………
.…………………………………………………………………………………………………
.…………………………………………………………………………………………………
.…………………………………………………………………………………………………
.…………………………………………………………………………………………………
.…………………………………………………………………………………………………
.…………………………………………………………………………………………………
.…………………………………………………………………………………………………
.…………………………………………………………………………………………………
.…………………………………………………………………………………………………
.…………………………………………………………………………………………………
.…………………………………………………………………………………………………
.…………………………………………………………………………………………………
.…………………………………………………………………………………………………
.…………………………………………………………………………………………………
.…………………………………………………………………………………………………
.…………………………………………………………………………………………………
.………………………………………………………………………………………………… vi

MỤC LỤC

2.2.3 SVMs trường hợp không thể phân chia tuyến tính 25
2.3 Thuật toán tìm siêu phẳng phân tách tối ƣu 27
2.3.1 Tìm tham số α* theo thuật toán 2v-SVM 27
2.3.2 Thuật toán khởi tạo các biến α
0
29
2.3.3 Đánh giá độ phức tạp của thuật toán 2v-SVM 30
2.4 Nhận xét về phƣơng pháp SVMs 31
2.5 Kết chƣơng 31
CHƢƠNG 3. THIẾT KẾ VÀ XÂY DỰNG CHƢƠNG TRÌNH 32
3.1 Lựa chọn công cụ xây dựng giải pháp 32
3.1.1 Lựa chọn môi trường 32
3.1.2 Lựa chọn ngôn ngữ lập trình 32
3.2 Phân tích và thiết kế chức năng 32
3.2.1 Xác định yêu cầu 32
3.2.2 Thiết kế chức năng 33
3.2.2.1 Chức năng phân loại văn bản 34
3.2.2.2 Chức năng tiền xử lý văn bản 35

vii

3.3 Xây dựng các chức năng 36
3.3.1 Xây dựng chức năng tiền xử lý văn bản 36
3.3.1.1 Tiền xử lý ký tự 36
3.3.1.2 Tách từ khoá, loại bỏ từ dừng trong văn bản 36
3.3.1.3 Trích chọn tập từ đặc trưng 39
3.3.1.4 Lựa chọn mô hình biểu diễn văn bản 40
3.3.1.5 Cài đặt module tiền xử lý văn bản 40
3.3.2 Xây dựng chức năng phân loại SVMs 42
3.3.2.1 Module huấn luyện SVMs 42

DANH MỤC CÁC HÌNH

Hình 1-1: Quy trình Khai phá tri thức – KDD Process. 1
Hình 1-2: Mô hình chung bài toán Khai phá văn bản. 3
Hình 1-3: Ví dụ quá trình phân loại văn bản. 4
Hình 1-4: Biểu diễn các vector văn bản trong không gian chỉ có 2 thuật ngữ. 9
Hình 1-5: Mô hình phân loại văn bản tổng quát. 11
Hình 1-6: Cấu trúc phương pháp phân loại văn bản. 12
Hình 1-7: Minh hoạ cách tính độ chính xác (precision) và độ bao (recall). 14
Hình 2-1: Minh hoạ chiều VC trong không gian 2 chiều với 3 điểm dữ liệu. 16
Hình 2-2: Minh hoạ các hàm {f(x)} trong không gian 2 chiều với 4 điểm dữ liệu. 17
Hình 2-3: Phân tách tuyến tính được xác định bằng mặt hình học H (w•x + b = 0). 19
Hình 2-4: Siêu phẳng phân tách tối ưu H trường hợp tuyến tính. 21
Hình 2-5: Trường hợp dữ liệu huấn luyện có nhiễu. 24
Hình 2-6: Thực hiện ánh xạ sang không gian đặc trưng kích thước 25
lớn thông qua hàm nhân. 26
Hình 3-1: Sơ đồ chức năng hệ thống xử lý văn bản. 33
Hình 3-2: Sơ đồ minh hoạ chức năng Phân loại văn bản. 34
Hình 3-4: Mô hình bộ tiền xử lý văn bản. 35
Hình 3-5: Lược đồ tiền xử lý tập dữ liệu và trích chọn tập đặc trưng. 41
Hình 3-7: Lược đồ thực hiện module huấn luyện. 43
Hình 4-1: Giao diện chính của chương trình Phân loại văn bản SVMs. 48
Hình 4-2: Giao diện chức năng huấn luyện SVMs. 49
Hình 4-3: Giao diện chức năng kiểm tra hiệu năng SVMs. 49
Hình 4-4: Biểu đồ biến thiên thời gian phân tách từ trên tập dữ liệu báo Vietnamnet. 51
Hình 4-5: Biểu đồ biến thiên thời gian phân tách từ trên tập dữ liệu báo VnExpress. . 52


Bảng 4-8: Tổng hợp kết quả phân loại đa lớp trên các bộ dữ liệu (báo Vietnamnet,
VnExpress, Hanoimoi, Laodong) 58

x

KÍ HIỆU CÁC CỤM TỪ VIẾT TẮT CSDL: Database
Cơ sở dữ liệu.
DM: Data Mining
ML: Machine Learning
IDF: Inverse Document Frequency
KDD: Knowledge Discovery in Database
k-NN: k-Nearest Neighbor
OSH: Optimum Separation Hyperplance
SVMs: Support Vector Machines
TF: Term Frequency.
TM: Text Mining
Khai phá dữ liệu.
Học máy.
Mô hình nghịch đảo tần số văn bản.
Phát hiện tri thức trong Cơ sở dữ liệu.
Thuật toán k láng giềng gần nhất.
Siêu phẳng phân tách tối ưu.
Phương pháp máy vector hỗ trợ.
Mô hình tần số thuật ngữ.

Các tệp phẳng
Khai phá dữ liệu
Làm sạch và
Tích hợp
Lựa chọn và
Chuyển đổi
Ước lượng và
Trình diễn
Tri thức
Các mẫu dữ liệu

Hình 1-1: Quy trình Khai phá tri thức – KDD Process.
Khoá luận tốt nghiệp Phân loại văn bản tiếng Việt sử dụng phương pháp SVMs
Sinh viên thực hiện: Hoàng Thị Nhung – Lớp HTTTA-K11 Trang 2/67

 Làm sạch dữ liệu: Nhằm loại bỏ nhiễu và dữ liệu không cần thiết. Các dữ
liệu cần loại bỏ ở đây có thể là dấu hiệu, ký hiệu, ký tự không mang nhiều ý
nghĩa.
 Tích hợp dữ liệu: Là quá trình tích hợp dữ liệu từ nhiều nguồn khác nhau.
 Lựa chọn dữ liệu: Ở bước này, các dữ liệu liên quan tới quá trình phân tích
sẽ được lựa chọn từ cơ sở dữ liệu.
 Chuyển đổi dữ liệu: Các dữ liệu được biến đổi hoặc kết hợp thành các mẫu
phù hợp với quá trình khai thác.
 Khai thác dữ liệu: Đây là bước quan trọng nhất, ở giai đoạn này lựa chọn
các phương thức thông minh (theo thứ tự nhất định) để trích chọn ra các
mẫu dữ liệu.
 Ƣớc lƣợng mẫu: Đánh giá tính chân thực của các mẫu liên quan về tri thức
dựa trên các phương pháp chuẩn nhất định.
 Biểu diễn tri thức: Là quá trình sử dụng các kĩ thuật biểu diễn và thể hiện
trực quan các tri thức khai thác cho người dùng.

 Dạng phi cấu trúc (unstructured): là dạng văn bản chúng ta sử dụng hằng
ngày được thể hiện dưới dạng ngôn ngữ tự nhiên của con người và chúng
không có một cấu trúc cụ thể nào. Ví dụ, văn bản lưu dưới dạng tệp tin
TXT.
 Dạng bán cấu trúc (semi-structured): đây là các dạng văn bản không
được lưu trữ dưới dạng các bản ghi chặt chẽ mà được tổ chức qua các đánh
dấu để thể hiện nội dung chính của văn bản. Ví dụ, các văn bản lưu dưới
dạng tệp tin HTML, e-Mail, Doc, … .
Do thiếu tính cấu trúc nên để khai phá dữ liệu trước tiên ta phải đưa các văn bản
về dạng có cấu trúc.
Khai phá dữ liệu văn bản (Text mining) là một lĩnh vực nhỏ trong Khai phá dữ
liệu. Khai phá dữ liệu văn bản được định nghĩa là quá trình tìm kiếm tri thức trong
những tập hợp bao gồm rất nhiều văn bản có nội dung đa dạng và được thu thập từ
nhiều nguồn khác nhau. Kỹ thuật khai phá dữ liệu văn bản được mô tả theo [4]:
Text Mining = Data Mining + Language Engineering.
Trong đó:
 Data mining: Sử dụng các kỹ thuật trong quy trình khai thác dữ liệu áp
dụng riêng đối với dữ liệu văn bản.
 Language Engineering: Kỹ thuật ngôn ngữ, nhằm xử lý riêng ngôn ngữ thể
hiện nội dung dữ liệu văn bản.
Nói chung, khai phá dữ liệu văn bản bao gồm các bước: Thu thập dữ liệu ở
dạng văn bản, làm sạch chúng, phân tích biến đổi, lấy thông tin và hiển thị.
Thu thập văn bản
Tiền xử lý làm sạch
Xử lý văn bản
Hiển thị văn bản
Nguồn dữ liệu

Hình 1-2: Mô hình chung bài toán Khai phá văn bản.



Hình 1-3: Ví dụ quá trình phân loại văn bản.
Bài toán phân loại văn bản được ứng dụng trong rất nhiều lĩnh vực khác nhau,
một trong những ứng dụng quan trọng nhất của bài toán này là ứng dụng tìm kiếm văn
bản. Từ tập dữ liệu đã được phân loại, các văn bản sẽ được đánh chỉ số đối với từng
lớp tương ứng. Người dùng có thể xác định chủ đề mà mình muốn tìm thông qua các
truy vấn.
1.1.4 Các khó khăn trong khai phá dữ liệu văn bản
Mặc dù có nhiều cách tiếp cận đã được đề xuất nhưng hầu hết các giải pháp đều
chưa giải quyết hoàn toàn một số vấn đề trong khai phá dữ liệu:
 Tính đa chiều (high dimensionality): Số thuật ngữ trong một văn bản có
thể lên đến hàng nghìn, thậm chí hàng chục nghìn. Nếu mỗi thuật ngữ trong
một ngôn ngữ nào đó được biểu diễn bằng một chiều trong không gian
vector thì số chiều không gian vector sẽ rất lớn. Điều này dẫn đến rất nhiều
khó khăn chẳng hạn như chi phí tính toán cao.
 Tính khả cỡ (scability): Các cơ sở dữ liệu lớn thường chứa hàng trăm
nghìn văn bản. Nhiều thuật toán khai phá dữ liệu có thể làm việc tốt với tập
dữ liệu nhỏ nhưng khi xử lý trên tập dữ liệu lớn thì không hiệu quả.
 Tính chính xác (accuracy): Trong các ngôn ngữ khác nhau đều có sự nhập
nhằng chẳng hạn như: từ đồng nghĩa, từ đồng âm khác nghĩa. Trong những
trường hợp này, phải dựa vào ngữ cảnh mới xác định được chúng.
 Biểu diễn kết quả một cách dễ hiểu: Kết quả sau khi khai phá dữ liệu cần
được biểu diễn ở cấu trúc được mô tả một cách dễ hiểu để người sử dụng có
thể truy cập một cách dễ dàng.
 Tri thức tiên nghiệm: Trong nhiều bài toán chẳng hạn như bài toán lập
nhóm văn bản, thì người sử dụng phải xác định trước một số tham số đầu
vào (như số nhóm văn bản cần lập). Tuy nhiên, trong nhiều trường hợp
người sử dụng lại không hiểu những gì mình cần.
Khoá luận tốt nghiệp Phân loại văn bản tiếng Việt sử dụng phương pháp SVMs
Sinh viên thực hiện: Hoàng Thị Nhung – Lớp HTTTA-K11 Trang 5/67

số mô hình biểu diễn thường được sử dụng để biểu diễn gồm: mô hình
không gian vector, mô hình dựa trên tập mờ (Fuzzy Set), mô hình dựa trên
tập thô (Rough Set), … .
.
1.2.2 Tách thuật ngữ trong văn bản Tiếng Việt
Tiếng Việt là ngôn ngữ đơn âm tiết khác với các ngôn ngữ đa âm tiết như nhóm
ngôn ngữ Ấn-Âu. Khác với các ngôn ngữ đơn âm tiết khác như tiếng Trung Quốc hay
tiếng Thái Lan, tiếng Việt được viết bằng các ký tự Latinh mở rộng. Vì vậy cách xử lý
các ngôn ngữ này cũng không thể áp dụng hoàn toàn cho tiếng Việt. Về mặt đơn vị
ngôn ngữ, tiếng Việt có hai đơn vị ngôn ngữ nhỏ nhất là tiếng và từ [24]: Khoá luận tốt nghiệp Phân loại văn bản tiếng Việt sử dụng phương pháp SVMs
Sinh viên thực hiện: Hoàng Thị Nhung – Lớp HTTTA-K11 Trang 6/67

 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 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ừ tạo bởi một tiếng: “tôi”, “tớ”.
- Từ tạo bởi nhiều tiếng có nghĩa rõ ràng: “hoa hồng” = “hoa” +
“hồng”.
 Từ:
Hiện nay đang tồn tại nhiều định nghĩa khác nhau về từ trong tiếng Việt,
nhưng tất cả những nghiên cứu ngôn ngữ đều đồng ý “từ” trong tiếng Việt có
những đặc điểm sau:
- 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
- Từ được xây dựng từ tiếng.
- Từ có thể là các từ đơn (1 tiếng) hoặc từ phức (gồm nhiều tiếng)

trình demo). Phương pháp này sử dụng một từ điển từ vựng để làm cơ sở
phân tách thuật ngữ.
 Thuật ngữ theo phƣơng pháp đồ thị
Phương pháp tách thuật ngữ bằng đồ thị quy việc phân tách câu về việc tìm
đường đi trên một đồ thị có hướng, không có trọng số.
1.2.3 Các kỹ thuật giảm chiều văn bản
Quá trình tiền xử lý tách từ cho văn bản đưa lại một danh sách rất lớn các từ
khoá. Khi tập từ khoá này càng lớn thì không gian để lưu trữ văn bản cũng càng lớn,
và việc xử lý càng tốn nhiều thời gian. Do đó, cần loại bớt những từ không có, hoặc ít
có giá trị trong quá trình xử lý văn bản.
Các bước áp dụng giúp giảm kích thước chiều của văn bản, bao gồm:
 Loại bỏ từ dừng (Stopwords)
Trong các ngôn ngữ tự nhiên có rất nhiều từ dùng biểu diễn cấu trúc câu nhưng
lại không mang nhiều ý nghĩa về mặt nội dung, chẳng hạn các từ loại thuộc: giới từ,
liên từ, … . Các loại từ này xuất hiện thường xuyên trong các văn bản nhưng không hề
mang bất cứ một thông tin nào về nội dung hay chủ đề bài viết. Hơn nữa, việc xuất
hiện của các từ dừng có thể làm chi phối, làm giảm chất lượng kết quả của việc xử lý
văn bản. Việc loại bỏ từ dừng đồng nghĩa với việc giảm số chiều văn bản, nhưng lại
mang lại làm tăng chất lượng xử lý văn bản. Ngoài ra, trong xử lý văn bản thường các
động từ không đóng vai trò quan trọng, do đó để làm giảm số chiều văn bản ta cũng có
thể loại đi các động từ. Để thực hiện được việc này, ta có thể áp dụng phương pháp
phân tích cú pháp câu để tìm các động từ, đây là phương pháp hay nhưng lại có độ
phức tạp cao, tốn thời gian xử lý. Trong ngôn ngữ tiếng Việt, những từ đứng sau các từ
“đã”, “đang”, và “sẽ” luôn là các động từ, do đó ta có thể áp dụng điều này để có thể
loại bỏ một phần những từ không quan trọng trong danh sách biểu diễn.
 Lựa chọn tập đặc trƣng cho không gian văn bản
Sau khi đã loại bỏ các từ trong danh sách thuật ngữ phân tách, tập các từ khoá T
của văn bản mặc dù đã giảm đi đáng kể, nhưng vẫn có kích thước rất lớn (nếu đầu vào
là một tập văn bản lớn). Kỹ thuật lựa chọn tập thuật ngữ đặc trưng (hay giảm không
gian thuật ngữ - Term Space Reduction -TSR) [25] sẽ giúp làm giảm số chiều của văn

IG(t
k
,c
i
)
 
 },{ },{
)().(
),(
log).,(
i
i
k
k
ccc ttt
cPtP
ctP
ctP

Mutual Information
MI(t
k
,c
i
)
)().(
),(
log
ik
ik

)
)().().().(
)],().,(),().,(.[||
i
i
k
k
i
ki
k
ik
ik
cPcPtPtP
ctPctPctPctPTr 

Relevancy score
RS(t
k
,c
i
)
dctP
dctP
ik
ik


)|(
)|(
log

i
, xác suất này bằng số lần
xảy ra trong tập huấn luyện
- P(t
k
,c
i
): xác suất chọn ngẫu nhiên một văn bản x, mà x chứa t
k
và x

c
i
.
- P(c
i
): xác suất chọn ngẫu nhiên một văn bản x, mà x

c
i
.
- P(t
k
): xác suất ngẫu nhiên một văn bản x, mà x chứa thuật ngữ t
k
.
Với hàm ước lượng thông tin nêu trên, ta sẽ tiến hành tính toán giá trị hàm ước
lượng thông tin của thuật ngữ t
k
đối với lớp c

bản trong không gian 2 chiều (chỉ có 2 thuật ngữ):
Thuật ngữ 2
Thuật ngữ 1
Văn bản 1
Văn bản 2
Văn bản 3
Văn bản 4

Hình 1-4: Biểu diễn các vector văn bản trong không gian chỉ có 2 thuật ngữ.
Một số mô hình không gian vector thường được áp dụng trong bài toán xử lý
văn bản như: mô hình Boolean, TF, IDF, TFxIDF.
Để biểu diễn tập văn bản theo các mô hình trên, ta giả sử tập gồm m văn bản: D
= {d
1
, d
2
,…, d
m
}. Mỗi văn bản được biểu diễn dưới dạng một vector gồm n thuật ngữ T
= {t
1
, t
2
,…, t
n
}. Gọi W = {w
ij
} là ma trận trọng số, trong đó w
ij
là giá trị của thuật ngữ

ij
được tính dựa trên tần số xuất hiện của thuật ngữ trong văn bản.
Gọi f
ij
là số lần xuất hiện của thuật ngữ t
i
trong văn bản d
j
, khi đó w
ij
được tính bởi
công thức:
w
ij
= f
ij
w
ij
=1+ log(f
ij
), với log(X) – là hàm logarit cơ số 10 đối số X.
Khoá luận tốt nghiệp Phân loại văn bản tiếng Việt sử dụng phương pháp SVMs
Sinh viên thực hiện: Hoàng Thị Nhung – Lớp HTTTA-K11 Trang 10/67

w
ij
=
ij
f
.

j
. Nếu t
i
xuất hiện trong càng ít văn bản, có nghĩa là nếu nó
xuất hiện trong văn bản d
j
thì trọng số của nó đối với văn bản d
j
càng lớn hay hàm
lượng thông tin trong nó càng lớn.


= 




= 







nu 



0 nu 






Trọng số w
ij
được tính bằng tần số xuất hiện của thuật ngữ t
i
trong văn bản d
j
và
độ hiếm của thuật ngữ t
i
trên toàn bộ cơ sở dữ liệu.
1.2.4.2 Áp dụng phƣơng pháp vector thƣa trong biểu diễn văn bản
Khi biểu diễn văn bản theo mô hình vector chuẩn, việc xử lý các phép toán trên
vector sẽ phụ thuộc vào độ lớn của ma trận W
ij
, trong đó i = {1,…,n} với n là số thuật
ngữ hay số chiều của vector; j = {1,…, m} với m là số lượng văn bản trong cơ sở dữ
liệu. Trên thực tế, số lượng thuật ngữ và số văn bản trong cơ sở dữ liệu thường rất lớn,
có thể lên đến hàng nghìn hoặc hơn nữa. Khi đó số lượng phần tử trong ma trận W
ij
sẽ
lên đến con số hàng triệu và việc lưu trữ ma trận W
ij
sẽ tốn quá nhiều tài nguyên bộ
nhớ đồng thời các phép toán trên các vector sẽ rất phức tạp. Để khắc phục vấn đề này
ta sẽ sử dụng kỹ thuật xử lý trên vector thưa thay vì việc lưu trữ và xử lý trên các

(kinh tế)
1
0
7
4
0
0
d
2
(giáo dục)
1
0
0
0
3
5

Trong ví dụ trên, các vector chuẩn có dạng:
d
0
= (2, 3, 0, 0, 0, 0).
d
1
= (1, 0, 7, 4, 0, 0).
d
2
= (1, 0, 0, 0, 3, 5).
Đối với vector thưa:
d
0

hệ thống phân loại tự động được xây dựng không những có thể thay thế hoàn toàn con
người trong lĩnh vực này mà thậm chí còn cho ra các kết quả tốt hơn rất nhiều.
Khoá luận tốt nghiệp Phân loại văn bản tiếng Việt sử dụng phương pháp SVMs
Sinh viên thực hiện: Hoàng Thị Nhung – Lớp HTTTA-K11 Trang 12/67

Để xây dựng công cụ phân loại văn bản tự động người ta thường dùng các thuật
toán học máy (Machine Learning). Tuy nhiên, còn có các thuật toán đặc biệt hơn dùng
cho phân loại trong các lĩnh vực đặc thù. Một ví dụ điển hình là bài toán phân loại
công văn giấy tờ. Hệ thống sẽ tìm ra đặc thù của văn bản một cách tương đối máy
móc, cụ thể là khi tìm thấy ở lề trên bên trái có ký hiệu “NĐ” thì hệ thống sẽ phân văn
bản đó vào nhóm “Nghị định”, tương tự như vậy với các ký hiệu “CV”, “QĐ” thì hệ
thống sẽ phân văn bản này vào nhóm “Công văn”, và “Quyết định”. Thuật toán này
tương đối hiệu quả song lại chỉ phù hợp cho các nhóm dữ liệu tương đối đặc thù. Khi
phải làm việc với các văn bản ít đặc thù hơn thì cần phải xây dựng các thuật toán phân
loại dựa trên nội dung của văn bản và so sánh độ phù hợp của chúng với các văn bản
đã được phân loại bởi con người. Đây là tư tưởng chính của thuật toán học máy. Trong
mô hình này, các văn bản đã được phân loại sẵn và hệ thống của chúng ta phải tìm
cách để tách ra đặc thù của các văn bản thuộc mỗi nhóm riêng biệt. Tập văn bản mẫu
dùng để huấn luyện gọi là tập huấn luyện (train set) hay tập mẫu (pattern set), quá trình
phân loại văn bản bằng tay gọi là quá trình huấn luyện (training), còn quá trình máy tự
tìm đặc thù của các nhóm gọi là quá trình học (learning). Sau khi máy đã học xong,
người dùng sẽ đưa các văn bản mới vào và nhiệm vụ của máy là tìm ra xem văn bản
đó phù hợp nhất với nhóm nào mà con người đã huấn luyện nó.
Một trong những ứng dụng quan trọng nhất của phân loại văn bản là ứng dụng
tìm kiếm văn bản. Từ tập dữ liệu đã được phân loại, các văn bản sẽ được đánh chỉ số
đối với từng lớp tương ứng. Người dùng có thể xác định chủ đề mà mình muốn tìm
thông qua các truy vấn.
1.3.2 Nền tảng học máy trong bài toán phân loại
Quy trình phân loại đối với bài toá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 [1]:

}, trong đó d
i
tương ứng với văn bản thứ i. Tập các lớp C = {c
1
, c
2
, …, c
|C|
}, c
i
là kí
hiệu của lớp thứ i.
 Tập huấn luyện: ký hiệu tập dữ liệu huấn luyện là Tr = {d
1
, d
2
, …, d
n
}.
Hàm phân loại Φ cho các phân loại trong tập C được xây dựng theo quy nạp
dựa trên sự quan sát các đặc trưng của các văn bản trong Tr.
 Tập kiểm tra: ký hiệu tập dữ liệu kiểm tra là Te = {d
n+1
, d
n+2
, …, d
m
}, được
sử dụng để kiểm tra hiệu quả phân lớp. Mỗi d
j

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 sẽ
mất đi yếu tố khách quan, khoa học.
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 suấ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 suất xuất hiện của từ trong văn bản và tần suất văn bản (số văn bản
trong tập dữ liệu huấn luyện 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ả 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
bài toán phân loại văn bản là phải tách được 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á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.
1.3.3 Phƣơng pháp máy vector hỗ trợ (Support Vector Machines)
Support Vector Machines (SVMs) là một phương pháp học máy mới, được giới
thiệu bởi Vladimir Vapnick và các cộng sự vào năm 1970, nhưng lần đăng báo đầu
tiên là vào năm 1995. Từ đó đến nay, nhiều kết quả nghiên cứu và thực nghiệm thấy
rằng SVMs hoàn toàn phù hợp với nhiệm vụ phân loại.
Phương pháp phân loại SVMs dựa trên nền tảng học máy có giám sát, xuất phát
từ lý thuyết học thống kê, và nguyên tắc tối thiểu hoá rủi ro cấu trúc (Structural Risk
Minimisation), nghĩa là SVMs sẽ cố gắng tìm cách phân loại văn bản sao cho lỗi xảy
ra trên tập kiểm tra là nhỏ nhất. Ý tưởng chính của phương pháp SVMs sẽ là: với một
lớp văn bản cho trước, tìm một mặt phẳng phân tách tối ưu (cho sai số nhỏ nhất) chia
tập dữ liệu thành hai phần, một phần thuộc phía dương của siêu phẳng thì thuộc về chủ
đề văn bản đó, phần còn lại (thuộc phía âm của siêu phẳng) thì không thuộc chủ đề đó.
Ta có thể hiểu, siêu phẳng là một mặt hình học f(x) trong không gian N chiều, với x


R