TRƢỜNG ĐẠI HỌC LẠC HỒNG
KHOA CÔNG NGHỆ THÔNG TIN


BÁO CÁO
NGHIÊN CỨU KHOA HỌC

ĐỀ TÀI:

XÂY DỰNG HỆ THỐNG PHÂN LOẠI TÀI
LIỆU TIẾNG VIỆT TRẦN THỊ THU THẢO
VŨ THỊ CHINH BIÊN HÒA, THÁNG 11/2012

TRƢỜNG ĐẠI HỌC LẠC HỒNG
KHOA CÔNG NGHỆ THÔNG TIN
 ĐỀ TÀI:

XÂY DỰNG HỆ THỐNG PHÂN
LOẠI TÀI LIỆU TIẾNG VIỆT

tức, bài viết, bài báo hay các tài liệu để rồi phân loại chúng theo đúng mục đích của mình
bởi vì số tài liệu lớn, nếu để đọc hết đƣợc tất cả thì sẽ mất rất nhiều thời gian. Đó là lý do
cần có một hệ thống phân loại tài liệu tiếng Việt.
Chúng em đã chọn thực hiện đề tài “Xây dựng hệ thống phân loại tài liệu tiếng Việt”
nhằm tìm hiểu và thử nghiệm các phƣơng pháp phân loại văn bản áp dụng trên tiếng Việt.
Trong luận văn này, chúng em cũng tìm hiểu một số cách phân loại tài liệu và thử nghiệm
một phƣơng pháp phân loại áp dụng thuật toán Naïve Bayes để xây dựng chƣơng trình dựa
trên tập dữ liệu huấn luyện từ đó hƣớng đến việc phân loại các bài báo khoa học trong lĩnh
vực Công nghệ thông tin nhằm tiết kiệm thời gian và công sức cho các nhà tổ chức trong
các hội thảo chuyên đề.
Việc thực hiện đề tài phân loại tài liệu tiếng Việt của chúng em hy vọng sẽ đem đến
một cách phân loại mới, nhanh chóng và hiệu quả hơn việc phân loại bằng thủ công nhƣ
hiện nay.

LỜI CẢM ƠN
Chúng em xin bày tỏ lòng biết ơn sâu sắc nhất tới Thầy Tạ Nguyễn đã tận tụy hƣớng
dẫn, động viên, giúp đỡ em trong suốt thời gian thực hiện đề tài.
Chúng em xin chân thành cảm ơn quý Thầy Cô trong khoa Công nghệ thông tin đã
truyền đạt những kiến thức quý báu và những kinh nghiệm quý báu cho chúng em trong
những năm học vừa qua.
Chúng con xin nói lên lòng biết ơn đối với Ông Bà, Cha Mẹ luôn là nguồn động viên,
chăm sóc trên bƣớc đƣờng học vấn của chúng con.
Xin chân thành cảm ơn các anh chị và bạn bè đã ủng hộ, giúp đỡ và động viên chúng
em trong thời gian học tập và nghiên cứu.
Mặc dù chúng em đã cố gắng hoàn thành luận văn trong phạm vi và khả năng cho phép
nhƣng chắc chắn chúng em sẽ không tránh khỏi những thiếu sót trong quá trình thực hiện đề
tài. Chúng em kính mong nhận đƣợc sự cảm thông và các ý kiến đóng góp của quý Thầy Cô
và các bạn.
Một lần nữa, xin chân thành cảm ơn.


3.1 Hiện trạng 24
3.2 Quy trình xử lý phân loại bài báo 25
3.2.1 Tách từ trong văn bản 26
3.2.2 Loại bỏ các từ tầm thƣờng 28
3.3 Trích chọn đặc trƣng văn bản 28
3.3.1 Các ý tƣởng cơ bản 28
3.3.2 Phƣơng pháp rút trích đặc trƣng 29
3.3.3 Phƣơng pháp đặc trƣng đề nghị sử dụng 30
3.4 Sử dụng thuật toán Naïve Bayes để phân loại văn bản 32
3.4.1 Lý do chọn Naïve Bayes 32
3.4.2 Ý tƣởng và công thức Naïve Bayes 32
3.4.3 Ƣớc lƣợng P(X|Y) 33
3.4.4 Ƣớc lƣợng P(Y) 34
3.4.5 Ƣớc lƣợng P(Y|X) 34
3.5 Ứng dụng Naïve Bayes vào bài toán phân loại 34
3.5.1 Ý tƣởng 34
3.5.1 Hƣớng dẫn cài đặt 35
CHƢƠNG 4: XÂY DỰNG CHƢƠNG TRÌNH 39
4.1 Xây dựng cơ sở dữ liệu 39
4.1.1 Từ điển tiếng việt 39
4.1.2 Mô tả thực thể 40
4.1 Xây dựng giao diện phân loại văn bản 47
4.1.1 Lƣu đồ phân loại văn bản 47
4.1.2 Thiết kế giao diện 48
4.1.3 Xây dựng các chức năng 49
CHƢƠNG 5: THỬ NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ 54
5.1 Ví dụ về chƣơng trình phân loại văn bản 54
5.2 Đánh giá kết quả 58
5.2.1 Dữ liệu đầu vào 58
5.2.2 Kết quả thực nghiệm 59

Bảng 4.2 Bảng Chuyên ngành 40
Bảng 4.3 Bảng tài khoản 41
Bảng 4.4 Bảng từ điển 41
Bảng 4.5 Bảng từ phổ thông 42
Bảng 4.6 Bảng từ đƣợc tách 42
Bảng 4.7 Bảng từ chuyên ngành 43
Bảng 4.8 Bảng bài báo 43
Bảng 4.9 Bảng bài báo sau khi phân loại 44
Bảng 4.10 Bảng biến tạm 44
Bảng 4.11 Bảng mối quan hệ thực thể 46
Bảng 4.12 Bảng mối kết hợp của thực thể 46
Bảng 5.1 Bảng số liệu xử lý theo con ngƣời 58
Bảng 5.2 Bảng kết quả chƣơng trình phân loại văn bản tiếng Việt 59
Bảng 5.3 Tỷ lệ(%) phân loại văn bản 60

1

CHƢƠNG 1: TỔNG QUAN
1.1 Đặt vấn đề
Trong thời đại bùng nổ công nghệ thông tin hiện nay, phƣơng thức sử dụng giấy tờ
trong giao dịch đã dần đƣợc số hoá chuyển sang các dạng văn bản lƣu trữ trên máy tính
hoặc truyền tải trên mạng. Bởi nhiều tính năng ƣu việt của tài liệu số nhƣ: cách lƣu trữ
gọn nhẹ, thời gian lƣu trữ lâu dài, tiện dụng trong trao đổi đặc biệt là qua Internet, dễ dàng
sửa đổi… nên ngày nay, số lƣợng văn bản số tăng lên một cách chóng mặt đặc biệt là trên
world-wide-web. Cùng với sự gia tăng về số lƣợng văn bản, nhu cầu tìm kiếm văn bản
cũng tăng theo. Với số lƣợng văn bản đồ sộ thì việc phân loại văn bản tự động là một nhu
cầu bức thiết.
Tại sao phải phân loại văn bản tự động? Việc phân loại văn bản sẽ giúp chúng ta
tìm kiếm thông tin dễ dàng và nhanh chóng hơn rất nhiều so với việc phải bới tung mọi
thứ trong ổ đĩa lƣu trữ để tìm kiếm thông tin. Mặt khác, lƣợng thông tin ngày một tăng lên

cách thức tính toán khác nhau để thực hiện việc phân loại.
Đối với tiếng Anh, các kết quả trong lĩnh vực này rất khả quan, còn đối với tiếng
Việt, các công trình nghiên cứu về phân loại văn bản gần đây đã có một số kết quả ban
đầu nhƣng vẫn còn nhiều hạn chế. Nguyên nhân là ngay ở bƣớc đầu tiên, chúng ta đã
gặp khó khăn trong việc xử lý văn bản để rút ra tần số xuất hiện của từ. Trong khi đó, để
phân loại văn bản thì có thể nói bƣớc đầu tiên là quan trọng nhất bởi vì nếu ở bƣớc tách
từ đã sai thì việc phân loại hầu nhƣ không thể thành công đƣợc. Phần trình bày tiếp theo
sẽ cho chúng ta biết những thách thức đặt ra trong việc tách từ tiếng Việt, cũng nhƣ
những ứng dụng thú vị của nó.
1.2.2 Tổng quan trong nƣớc
Vấn đề phân loại văn bản tiếng Việt đƣợc nhiều cơ sở nghiên cứu trong cả nƣớc
quan tâm trong những năm gần đây. Một số công trình nghiên cứu cũng đạt đƣợc những
kết quả khả quan. Các hƣớng tiếp cận bài toán phân loại văn bản đã đƣợc nghiên cứu bao
gồm: hƣớng tiếp cận bài toán phân loại bằng lý thuyết đồ thị[10], cách tiếp cận sử dụng
3

lý thuyết tập thô [9], cách tiếp cận thống kê [12], 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[14, 15]. Nhìn chung, những cách tiếp cận này đều cho
kết quả tốt.Tuy vậy để đi đến những triển khai khả thi thì vẫn cần đẩy mạnh nghiên cứu
nhƣng vẫn dựa trên hƣớng nghiên cứu trên. Một trong những khó khăn trong việc áp
dụng những thuật toán phân loại văn bản vào tiếng Việt là xây dựng đƣợc tập hợp từ
vựng của văn bản. Vấn đề này liên quan tới việc phân tách một câu thành các từ một cách
chính xác. Có thể kể đến công trình nghiên cứu của GS.TSKH Hoàng Kiếm và TS. Đỗ
Phúc[13]
Đối với tiếng Anh, “từ là một nhóm các ký tự có nghĩa đƣợc tách biệt với nhau
bởi khoảng trắng trong câu” (Webster Dictionary), do vậy việc tách từ trở nên rất đơn
giản. Trong khi đối với tiếng Việt, ranh giới từ không đƣợc xác định mặc định là
khoảng trắng mà tùy thuộc vào ngữ cảnh dùng câu tiếng Việt. Ví dụ các từ trong tiếng
Anh là “book”, “cat”, “stadium” thì trong tiếng Việt là “quyển sách”, “con mèo”, “sân
vận động”. Vấn đề trên thực sự đƣa ra một thách thức đối với chúng ta - những ngƣời

 Bƣớc 1:
- Tìm tập dữ liệu bao gồm tập kiểm thử chƣơng trình và tập máy học bao
gồm các bài báo, luận văn thuộc chuyên ngành công nghệ thông tin trong
đó:
o Tập máy học bao gồm các bài báo đƣợc phân loại theo tri thức, phân
loại thủ công hay dựa vào đề tài để phân loại làm dữ liệu
o Tập dùng để kiểm thử là tập hợp các bài báo đã đƣợc phân loại sẵn
dùng để kiểm thử chƣơng trình lấy kết quả thống kê khi hoàn thành
chƣơng trình
 Bƣớc 2:
- Tìm hiểu các phƣơng pháp tách từ hiện nay để chọn ra phƣơng pháp phù
hợp nhất
- Tách từ, xóa những stop word dựa trên phƣơng pháp đã chọn trên tập dữ
liệu tìm đƣợc
5

 Bƣớc 3:
- Tìm hiểu các phƣơng pháp tính trọng số của từ, chọn lựa phƣơng pháp phù
hợp.Xây dựng bộ từ điển các từ trong lĩnh vực Công nghệ thông tin kèm
theo trọng số.
 Bƣớc 4:
- Rút trích đặc trƣng ƣớc lƣợng xác suất theo phƣơng pháp Naïve Bayes vào
chƣơng trình phân loại văn bản tiếng Việt
 Bƣớc 5:
- Thử nghiệm và thống kê kết quả xử lý khi hoàn thành chƣơng trình dựa trên
tập dữ liệu kiểm thử đã đƣợc phân loại sẵn.
- Nhận xét và đánh giá 6

Vì vậy, nhiệm vụ đầu tiên cần phải làm là biểu diễn văn bản dƣới dạng các từ, cụm
từ và các câu có chọn lọc. Lọc bỏ những từ, cụm từ và câu không có nghĩa hay không có tác
động tích cực tới việc phân loại.
Bƣớc tiếp theo là xác định các ràng buộc cho bài toán phân loại. Các ràng buộc
này sẽ đƣợc lấy ra từ tập dữ liệu huấn luyện. Mỗi ràng buộc thể hiện một đặc trƣng của dữ
liệu huấn luyện. Khi ta có đƣợc 1 bài báo, khi đó ta dựa vào một số đặc điểm hay thuộc
tính nào đó của bài báo để tăng khả năng phân loại . Các đặc điểm của bài báo nhƣ: tiêu
đề, nội dung… Càng nhiều những thông tin nhƣ vậy xác suất phân loại đúng càng lớn, tất
nhiên còn phụ thuộc vào kích thƣớc của tập mẫu huấn luyện.
Việc tính toán xác suất sẽ dựa vào công thức Naïve Bayes, từ xác suất thu đƣợc ta
đem so sánh với một giá trị ngƣỡng t nào đó mà ta xem là ngƣỡng để phân loại bài báo thuộc
thể loại nào.
2.3 Các phƣơng pháp phân loại văn bản tiếng Anh
2.3.1 Support vector Machine (SVM)
SVM - viết tắt tên tiếng Anh support vector machine là phƣơng pháp đƣợc Vapnik
giới thiệu vào năm 1995 [3] nhằm giải quyết vấn đề nhận dạng mẫu 2 lớp sử dụng nguyên lý
cực tiểu hóa rủi ro có cấu trúc.
 Ý tƣởng
Cho trƣớc tập huấn luyện đƣợc biểu diễn trong không gian vector trong đó mỗi văn
bản là một điểm, phƣơng pháp tìm ra một siêu mặt phẳng h quyết định tốt nhất có thể chia
các điểm trên không gian này thành 2 lớp riêng biệt tƣơng ứng lớp + và lớp Hiệu quả xác
định siêu mặt phẳng này đƣợc quyết định bởi khoảng cách của điểm gần mặt phẳng nhất của
mỗi lớp. Khoảng cách càng lớn thì mặt phẳng quyết định càng tốt đồng nghĩa với việc phân
loại càng chính xác và ngƣợc lại. Mục đích cuối cùng của phƣơng pháp là tìm đƣợc khoảng
cách biên lớn nhất.

8 Hình 2.1 Phân chia dữ liệu huấn huyện

) biểu diễn sự phân lớp của
i
d

vào 2 lớp + và lớp Gọi y
i
= {±1}, y
i
= +1
văn bản
i
d

thuộc lớp +, y
i
= -1 văn bản
i
d
thuộc lớp Để có siêu mặt phẳng h ta đi giải bài
toán:
Tính Min||
w
|| với
w
và b thoản mãn điều kiện:

1)).((:,1  bwdsignyni
i
i


j
, d’) cao nhất .
Công thức để tính Pr (C
j
, d’) nhƣ sau:
 
   
   























j
d
'
H
BAYES

Với:
- TF(w
i
, d’) là số lần xuất hiện của từ w
i
trong văn bản d’
- |d’| là số lƣợng các từ trong văn bản d’
- w
i
là một từ trong không gian đặc trƣng F với số chiều là |F|
- Pr(Cj) đƣợc tính dựa trên tỷ lệ phần trăm của số văn bản mỗi lớp tƣơng
ứng trong tập dữ liệu huấn luyện
10
 



C
C
'
C

,
w
i
TF1
C
j
|
w
i
Pr Ngoài ra còn có các phƣơng pháp NB khác có thể kể ra nhƣ ML Naïve Bayes,
MAP Naïve Bayes, Expected Naïve Bayes. Nói chung Naïve Bayes là một công cụ rất
hiệu qủa trong một số trƣờng hợp. Kết qủa có thể rất xấu nếu dữ liệu huấn luyện nghèo
nàn và các tham số dự đoán (nhƣ không gian đặc trƣng) có chất lƣợng kém. Nhìn chung
đây là một thuật toán phân loại tuyến tính thích hợp trong phân loại văn bản nhiều chủ đề.
NB có ƣu điểm là cài đặt đơn giản, tốc độ thực hiện thuật toán nhanh, dễ dàng cập nhật dữ
liệu huấn luyện mới và có tính độc lập cao với tập huấn luyện.
2.3.3 Biểu diễn văn bản
Bƣớc đầu tiên của các phƣơng pháp phân loại văn bản là chuyển việc mô tả văn bản
dùng chuỗi ký tự thành dạng mô tả khác phù hợp với các thuật toán. Hầu hết các thuật toán
đều sử dụng cách biểu diễn theo vector đặc trƣng, khác nhau chủ yếu ở việc lựa chọn không
gian đặc trƣng. Cụ thể với mô hình cực đại entropy [11], thuật toán IIS chỉ có thể tính toán
đƣợc các tham số dựa trên các vector đặc trƣng. Vậy vector đặc trƣng là gì?
Mỗi vector đặc trƣng
id
đại diện cho một văn bản tƣơng ứng trong không gian các
từ w:
id

id
Hình 2.2 Biểu diễn văn bản
Trong thực tế để cải thiện tốc độ và kết quả ngƣời ta sử dụng IDF(w
i
) hay
TFIDF(w
i
) thay cho TF(w
i
) (trong luận văn sử dụng TFIDF):
)
)(
log()(
i
i
wDF
m
wIDF 

)().()(
iii
wIDFwTFwTFIDF 

Trong đó:
- m chính là số văn bản huấn luyện
- DF(w
i

 Công thức
Trọng số của chủ đề c
j
đối với văn bản x đƣợc tính nhƣ sau:

b
j
c
j
,
d
i
y.
{kNN}
d
i
d
i
,
x
sim
c
j
x,
W 






-
y = 0: văn bản d
i
không thuộc về chủ đề c
j
13

- y = 1: văn bản di thuộc về chủ đề cjsim (x, d): độ giống nhau giữa văn bản
cần phân loại x và văn bản d. Chúng ta có thể sử dụng độ đo cosine để tính
khoảng cách:
d
i
x
d
i
.
x
d
i
,
x
cos
d
i
,
x
sim




2.3.5 Linear Least Square Fit (LLSF)
LLSF là một cách tiếp cận ánh xạ đƣợc phát triển bởi Yang và Chute vào năm
1992. Ban đầu LLSF đƣợc thử nghiệm trong lĩnh vực xác định từ đồng nghĩa sau đó sử
dụng trong phân loại vào năm 1994. Các thử nghiệm cho thấy hiệu suất phân loại của
LLSF có thể ngang bằng với phƣơng pháp kNN kinh điển.
 Ý tƣởng
LLSF sử dụng phƣơng pháp hồi quy để học từ tập huấn luyện và các chủ đề có sẵn
[Yang & Chute, 1994]. Tập huấn luyện đƣợc biểu diễn dƣới dạng một cặp vector đầu vào
và đầu ra nhƣ sau:
o Vector đầu vào một văn bản bao gồm các từ và trọng số
o Vector đầu ra gồm các chủ đề cùng với trọng số nhị phân của văn bản ứng
với vector đầu vào
Giải phƣơng trình các cặp vector đầu vào/ đầu ra, ta sẽ đƣợc ma trận đồng hiện
của hệ số hồi quy của từ và chủ đề (matrix of word-category regression coefficients)
 Công thức
14

BFA
2
min
arg
F
F
LS


Trong đó ¾ A, B là ma trận đại diện tập dữ liệu huấn luyện (các cột trong ma trận
tƣơng ứng là các vector đầu vào và đầu ra) ¾ FLS là ma trận kết quả chỉ ra một ánh xạ từ
một văn bản bất kỳ vào vector của chủ đề đã gán trọng số
Nhờ vào việc sắp xếp trọng số của các chủ đề, ta đƣợc một danh sách chủ đề có

liên quan từ đặc trƣng đầu vào cho đến kết quả gán chủ đề tƣơng ứng đƣợc học từ 17 tập
dữ liệu. Do vậy, để phân tích một cách tuyến tính, tác giả dùng hàm sigmoid sau làm hàm
truyền trong mạng neural:


  


Trong đó, T xη β= là sự kết hợp của những đặc trƣng đầu vào và p phải thỏa điều
kiện p  (0,1)
2.3.7 Centroid- based vector
Là một phƣơng pháp phân loại đơn giản, dễ cài đặt và tốc độ nhanh do có độ phức
tạp tuyến tính O(n).
 Ý tƣởng
Ý tƣởng của cách tiếp cận này là mỗi lớp trong dữ liệu huấn luyện sẽ đƣợc biểu
diễn bằng một vector trọng tâm.Việc xác định lớp của một văn bản bất kỳ sẽ thông qua
việc tìm vector trọng tâm nào gần với vector biểu diễn văn bản thứ nhất.Lớp của văn bản
chính là lớp mà vector trọng tâm đại diện và khoảng cách đƣợc xác định theo độ đo
cosine.
16

 Công thức
Công thức tính vector trọng tâm của lớp i:





{i}
d












Trong đó:
 x là vector văn bản cần phân loại
 {i} là tập hợp các văn bản thuộc chủ đề C
i

 Chủ đề của vector x là C
x
thỏa mãn cos(x, C
x
) = arg max
(cos(x, C
i
)).
2.4 Kết luận chung về các phƣơng pháp phân loại văn bản tiếng Anh
Các thuật toán phân loại trên từ thuật toán phân loại hai lớp (SVM) đến các thuật
toán phân loại đa lớp (kNN) đều có điểm chung là yêu cầu văn bản phải đƣợc biểu diễn
dƣới dạng vector đặc trƣng. Ngoài ra các thuật toán nhƣ kNN, NB, LLSF đều phải sử
dụng các ƣớc lƣợng tham số và ngƣỡng tối ƣu khi phân loại văn bản, trong khi thuật toán
SVM có thể tự xác định các tham số tối ƣu này trong qúa trình thực hiện thuật toán. Xét

tiền bạc.
Trong luận văn này, chúng em cố gắng tìm hiểu, cài đặt, thử nghiệm phƣơng pháp
tách từ dựa trên mô hình N-gram. Bởi vì trong tiếng Việt, hình vị nhỏ nhất là “tiếng” đƣợc
hình thành bởi nhiều ký tự trong bảng chữ cái. Phƣơng pháp này đơn thuần rút trích ra một
số lƣợng nhất định các tiếng trong văn bản nhƣ rút trích từ 1 ký tự (unigram) hay nhiều ký
tự (n-gram) đƣợc minh chứng thông qua một số công trình nghiên cứu đã đƣợc công bố,
nhƣ của tác giả Lê An Hà [2003] xây dựng tập ngữ liệu thô 10MB bằng cách sử dụng

Trích đoạn Hiện trạng Ứng dụng Naïve Bayes vào bài toán phân loại

---