-i-

LỜI CAM ĐOAN
Tôi xin cam đoan:
1. Những nội dung trong luận văn này là do tôi thực hiện dưới sự trực
tiếp hướng dẫn của cô giáo TS. Nguyễn Thị Thu Hà.
2. Mọi tham khảo dùng trong luận văn đều được trích dẫn rõ ràng tên tác
giả, tên công trình, thời gian, địa điểm công bố.
3. Mọi sao chép không hợp lệ, vi phạm quy chế đào tạo, hay gian trá, tôi
xin chịu hoàn toàn trách nhiệm.
Tác giả luận văn

Nguyễn Thị Thùy Dương


- ii -

LỜI CẢM ƠN
Lời đầu tiên tôi xin được bày tỏ lòng biết ơn chân thành đến Ban Giám
Hiệu, các thầy giáo, cô giáo phòng Sau đại học trường Đại học Công Nghệ
Thông Tin & Truyền Thông, các thầy giáo ở Viện Công Nghệ Thông Tin đã
giảng dạy và tạo mọi điều kiện cho tôi học tập, nghiên cứu và hoàn thành luận
văn này.
Đặc biệt, tôi xin bày tỏ sự kính trọng và lòng biết ơn sâu sắc đến TS.
Nguyễn Thị Thu Hà, người đã tận tình hướng dẫn và giúp đỡ tôi trong suốt
quá trình học tập, nghiên cứu và hoàn thành luận văn.
Tôi chân thành cảm ơn các thầy cô Khoa Công nghệ thông tin, Trường
Trung cấp nghề Phát Thanh Truyền Hình Thanh Hóa nơi tôi công tác đã tạo
điều kiện và hỗ trợ tôi trong suốt thời gian qua.
Tôi cũng xin chân thành cảm ơn người thân, bạn bè đã giúp đỡ và động
viên tôi trong suốt thời gian học tập cũng như trong thời gian thực hiện luận


Chương 3: PHÁT TRIỂN HỆ THỐNG PHÂN LOẠI VĂN BẢN TIẾNG
VIỆT DỰA TRÊN NAIVE BAYES............................................................. 43
3.1. Mô hình tổng quát của hệ thống ............................................................................ 43
3.2. Xây dựng tập ngữ liệu ........................................................................................... 44
3.2.1. Xây dựng tập dữ liệu ...................................................................................... 44
3.2.2. Tiền xử lý và chuẩn hóa dữ liệu ..................................................................... 47
3.2.3. Xây dựng bộ từ điển danh từ .......................................................................... 48
3.3. Môi trường cài đặt ................................................................................................ 50
3.3.1. Môi trường cài đặt của hệ thống ..................................................................... 50


- iv -

3.3.2. Cấu trúc của chương trình .............................................................................. 50
3.3.3. Giao diện chương trình................................................................................... 51
3.4. Kết quả thực nghiệm ............................................................................................. 56
3.5. Kết luận chương 3................................................................................................. 57

KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ............................................ 59
TÀI LIỆU THAM KHẢO .................................................................... 60


-v-

DANH SÁCH CÁC BẢNG
Bảng1.2. Đánh giá phân loại văn bản ................................................... 11
Bảng 2.1. Các từ chủ đề trong tập mô tả của Andrews năm 2009. ........ 30
Bảng 2.2. Danh sách một số chủ đề đã được xây dựng ......................... 41
Bảng 3.1. Các chức năng của chương trình........................................... 45



- vii -

Hình 3.10. Giao diện danh sách tin tức ................................................. 55
Hình 3.11. Giao diện người dùng ......................................................... 56


- viii -

DANH SÁCH CÁC CHỮ VIẾT TẮT
Viết tắt
k- NN

Tiếng Anh
k- Nearest Neighbor

Tiếng Việt
k-Láng giềng gần nhất

SVM

Support Vector Machine

Máy véc tơ hỗ trợ

RSS

Really Simple Syndication


văn bản 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. Phân loại văn bản (Text classification) là một
trong những công cụ khai phá dữ liệu dạng văn bản một cách hữu hiệu, làm
nhiệm vụ đưa những văn bản có cùng nội dung chủ đề giống nhau về cùng
một lớp có sẵn. Phân loại văn bản giúp người dùng dễ dàng hơn trong việc
tìm kiếm thông tin cần thiết đồng thời có thể lưu trữ các thông tin theo đúng
chủ đề (topic) hay lớp (class) dựa trên các thuật toán phân loại.
2. Đối tượng và phạm vi nghiên cứu: Tìm hiểu lý thuyết Naive Bayes và
ứng dụng trong phân loại văn bản tiếng Việt.
3. Những nội dung nghiên cứu chính
 Chương 1: Tổng quan về phân loại văn bản
Tổng quan về phân loại văn bản và khái niệm cơ bản về lý thuyết Naive
Bayes, bộ phân loại Naive Bayes trên mô hình xác suất.
 Chương 2: Phân loại văn bản tiếng Việt dựa trên phương pháp Naive
Bayes
Trình bày phương pháp phân loại văn bản tiếng Việt dựa trên phân loại
Naive Bayes và cách giảm chiều đặc trưng nhằm tăng tốc trong quá trình tính
toán xử lý bằng cách sử dụng mô hình chủ đề dùng cho tiếng Việt.


-2-

 Chương 3: Phát triển hệ thống phân loại văn bản Tiếng Việt
Trình bày chi tiết từ phân tích thiết kế của hệ thống và các giao diện
của hệ thống.
4. Phương pháp nghiên cứu
- Tổng hợp các thông tin liên quan, lựa chọn các cách tiếp cận đã được
áp dụng
thành công, tiến hành cài đặt thử nghiệm, đánh giá kết quả.
- Các tư liệu và thông tin liên quan chủ yếu được thu thập, tổng hợp từ

của việc khai phá dữ liệu văn bản là cho phép người dùng trích xuất thông tin
của các nguồn văn bản và sử dụng chúng thông qua các công cụ như: tra cứu,
hỏi đáp, phân loại và tóm tắt sử dụng ngôn ngữ tự nhiên.
Phân loại văn bản là một trong những phần quan trọng của việc khai
phá dữ liệu văn bản, khá nhiều các hệ thống phân loại văn bản sử dụng kỹ
thuật dựa trên tri thức (knowledge based) hoặc dựa trên các luật được xây
dựng sẵn để tạo thành một tập hợp các quy tắc logic để hiểu và phân loại văn
bản. Mỗi loại (hay còn gọi là lớp –class) tương đương với một chủ đề ví dụ
“thể thao”, “chính trị” hay “nghệ thuật”. Nhiệm vụ phân loại được bắt đầu
xây dựng từ một tập các văn bản D = {d1,d2,..,dn} được gọi là tập huấn luyện
và trong đó các tài liệu di được gán nhãn cj với cjthuộc tập các chủ đề
C={c1,c2,...,cm}. Nhiệm vụ tiếp theo đó là xác định được mô hình phân loại
mà có thể gán đúng lớp để một tài liệu dk bất kỳ có thể phân loại chính xác
vào một trong những chủ đề của tập chủ đề C [4].


-4-

Khái niệm [Phân loại văn bản]: Phân loại văn bản là nhiệm vụ gán một
văn bản dj vào một chủ đề ck thích hợp thuộc tập chủ đề C = {c1,c2,...,cm}theo
đúng nội dung của văn bản đó.
1.1.2. Mô hình hệ thống phân loại văn bản
Mô hình bài toán phân loại văn bản được mô tả như hình sau:

Hình 1.1. Quá trình học phân loại văn bản.
Một quy trình xử lý phân loại văn bản bao gồm 2 pha chính: Pha huấn
luyện và pha phân loại.
- Pha huấn luyện: Các văn bản đầu vào được gán nhãn và được trích
chọn đặc trưng để nhận dạng và sử dụng thuật toán học để lưu trữ lại các giá
trị của đặc trưng theo một mô hình chuẩn.

Biểu diễn văn bản là một trong những kỹ thuật tiền xử lý, nó được sử
dụng để giảm độ phức tạp của văn bản và dễ dàng trong lưu trữ và xử lý, văn
bản có thể biến đổi từ dạng chữ đầy đủ thành một véc tơ văn bản. Thông


-6-

thường nhất sử dụng mô hình véc tơ không gian. Các văn bản được biểu diễn
bằng các véc tơ từ. Ví dụ như ma trận trọng số sau:
T1

T2

...

Tαt ci

D1

w11 w21

...

wt1 c1

D2

w12 w22

...



-7-

Phương pháp k-NN [6] là phương pháp truyền thống khá nổi tiếng theo
hướng tiếp cận thống kê đã được nghiên cứu trong nhiều năm qua. k - NN
được đánh giá là một trong những phương pháp tốt nhất được sử dụng từ
những thời kỳ đầu trong nghiên cứu về phân loại văn bản.
Ý tưởng của phương pháp này đó là khi cần phân loại một văn bản mới,
thuật toán sẽ xác định khoảng cách (có thể áp dụng các công thức về khoảng
cách như Ơclit, Cô sin, Manhattan, …) của tất cả các văn bản trong tập huấn
luyện đến văn bản này để tìm ra k văn bản gần nhất, gọi là k – NN, sau đó
dùng các khoảng cách này đánh trọng số cho tất cả các chủ đề. Khi đó, trọng
số của một chủ đề chính là tổng tất cả các khoảng cách ở trên của các văn bản
trong k láng giềng có cùng chủ đề, chủ đề nào không xuất hiện trong k láng
giềng sẽ có trọng số bằng 0. Sau đó các chủ đề sẽ được sắp xếp theo giá trị
trọng số giảm dần và các chủ đề có trọng số cao sẽ được chọn làm chủ đề của
văn bản cần phân loại.
Trọng số của chủ đề cj đối với văn bản x được tính như sau:
( , )=∑

∈{

}

sin( ,

,

).

thiệu năm 1995, là phương pháp tiếp cận phân lớp hiệu quả để 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
(Structural Risk Minimization).
Trong không gian véc tơ cho trước một tập huấn luyện được biểu diễn
trong đó mỗi tài liệu là một điểm, thuật toán SVM sẽ 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
hai lớp riêng biệt tương ứng lớp “+” và lớp “–“. Chất lượng của siêu mặt
phẳng phân cách này được quyết định bởi khoảng cách (gọi là biên) của điểm
dữ liệu gần nhất của mỗi lớp đến mặt phẳng này. Khoảng cách biên càng lớn
thì mặt phẳng quyết định càng tốt và việc phân lớp càng chính xác. Mục đích
thuật toán SVM là tìm được khoảng cách biên lớn nhất.
Hình sau minh họa cho thuật toán này:
+
+
+
+
+

+
+

+

+

h

+

-

.

+ b) =

+ 1, khi (

.

+ ) >0

1, khi (

.

+ ) < 0





Từ đó h(di ) biểu diễn sự phân lớp của d i vào 2 lớp nói trên




Có yi  {1} thì với yi= +1, văn bản d i  “+”; với yi= -1, văn bản d i 
“-”. Lúc này muốn có siêu mặt phẳng h, ta sẽ giải bài toán sau:
min‖ ‖,

Tìm

nó là:

1


. Khi các điểm khác bị xóa đi thì vẫn không ảnh hưởng đến kết

|| w ||

quả ban đầu.

1.2. Các nghiên cứu liên quan
Các nghiên cứu về phân loại văn bản tập trung vào việc áp dụng các
phương pháp học giám sát, sử dụng các kho dữ liệu lớn là tập các văn bản
được phân loại theo các chủ đề khác nhau như phương pháp Naive Bayes
(McCalum, 1998; Ko, 2000), Phương pháp k - NN (Yang, 2002), và Rocchio
(Lewis, 1996).
Đối với phân loại bằng mạng nơ ron, mô hình đơn giản nhất được đề
xuất bởi Dagan và các cộng sự (1997) và Ng (1997) là perceptron. Một mô
hình đơn giản khác là mạng nơ ron tuyến tính bổ sung một kiểu hồi quy logic


- 10 -

được đề xuất bởi Schutze và các cộng sự vào năm 1995 mang lại hiệu quả
tương đối cao.
Một mô hình nơ ron không tuyến tính nhiều lớp sử dụng trong phân
loại văn bản được đề xuất bởi Lam và Lee vào năm 1999 thay thế cho mô
hình một nơ ron tuyến tính đơn giản, tiếp theo đó một loạt các mô hình mạng
nơ ron nhiều lớp được đề xuất như Ruiz và Srinivasan (1999), Weigend


Macroaveraging

| |

Độ đo chính xác (p)

p=
r=

Độ hồi tưởng (r)

∑

p=

| |

∑

∑

| |

| |

∑

r=


Bảng1.2. Đánh giá phân loại văn bản
Trong đó:
Trung bình hóa có độ chính xác và thu hồi trên các loại khác nhau; TPi,
TNi, FPi và FNi tham khảo các bộ tích cực đúng, âm đúng, sai tích cực, sai tiêu
cực và wrt ci, tương ứng
1.2.2. Lý thuyết Naive Bayes
Trong học máy, phân loại Naive Bayes là một thành viên trong nhóm
các phân loại có xác suất dựa trên việc áp dụng định lý Bayes khai thác mạnh
giả định độc lập giữa các hàm, hay đặc trưng.
Mô hình Naive Bayes cũng được biết đến với nhiều tên khác nhau ví
dụ: Simple Bayes hay independence Bayes hay phân loại Bayes.
Naive Bayes đã được nghiên cứu rộng rãi từ những năm 1950. Nó được
giới thiệu vào đầu những năm 1960 đầu tiên ứng dụng trong phân loại văn
bản, các vấn đề của việc đánh giá các tài liệu thuộc về một thể loại hay khác
(chẳng hạn như thư rác hoặc hợp pháp, thể thao, chính trị, v.v..) với tần số từ
như các đặc trưng. Với tiền xử lý thích hợp, đó là cạnh tranh trong lĩnh vực


- 12 -

này với nhiều phương pháp tiên tiến bao gồm cả máy véc tơ hỗ trợ. Nó cũng
tìm thấy ứng dụng trong chẩn đoán tự động.
Phân loại Naive Bayes được đánh giá cao khả năng mở rộng, đòi hỏi
một số thông số tuyến tính trong số lượng các biến (các tính năng/tố dự báo)
trong nhiều lĩnh vực khác nhau.
1.2.3. Khái niệm
Một phân loại Naive Bayes dựa trên ý tưởng nó là một lớp được dự
đoán bằng các giá trị của đặc trưng cho các thành viên của lớp đó. Các đối
tượng là một nhóm (group) trong các lớp nếu chúng có cùng các đặc trưng
chung. Có thể có nhiều lớp rời rạc hoặc lớp nhị phân.

1.2.3.1. Mô hình xác suất
Một cách trừu tượng, mô hình xác suất cho phân loại là một mô hình
điều kiện r(C|F1, . ., Fn)
Trên một lớp biến C với số lượng nhỏ các đầu ra hoặc các lớp. Điều
kiện trên một vài biến đặc trưng F1 đến F2. Vấn đề chính trong bài toán này là
nếu số đặc trưng n là lớp hoặc một đặc trưng có thể có số lượng lớn các giá
trị, thì một mô hình được tạo ra dựa trên các bảng xác suất là phù hợp trong
điều kiện này. Lý thuyết Bayes có thể viết thành:
r(C|F1, . ., Fn) =

r( )r(
r(

,..,
,..,

| )
| )

Một cách mô tả đơn giản cho công thức trên như sau:
Hậu nghiệm =

ệ

ướ ×
ằ

ả ă

ứ

| )

Có nghĩa rằng dưới giả thiết độc lập trên, phân tán có điều kiện trên các
lớp biến C là:

r(C|F1,. . ., Fn) = r(C)∏

r( | )

Với Z = r(F1,. . ., Fn) được gọi là nhân tố độc lập trên F1,. . ., Fn và là
một hằng nếu các giá trị của các biến đặc trưng là đã biết.
1.2.3.2. Xây dựng phân lớp từ mô hình xác suất

Phân lớp Bayes kết hợp với luật quyết định tạo ra phân loại Naive
Bayes. Một luật thông thường đưa ra giả thuyết về khả năng nhất hay còn
được xem như là cực đại hóa xác suất hậu nghiệm (maximum a posteriori).
Bộ phân loại Bayes là một hàm phân loại được định nghĩa:
( , …,

)=

( = )∏

(

= | C=c)

Ví dụ về phân lớp giới tính nam và nữ dựa trên một số độ đo đặc trưng.
Các đặc trưng bao gồm: chiều cao, cân nặng và cỡ chân.


female

5.42 (5'5")

130

7

female

5.75 (5'9")

150

9

sex

Bộ phân loại được tạo từ tập huấn luyện sử dụng giả thiết phân tán
Gauss tạo ra giá trị cho các đặc trưng như sau:

Sex

Male

mean
(height)
5.855

Female 5.4175


1.6667e+00

Giả sử rằng tạo ra hai lớp tương đương P(male)= P(female) = 0.5. Xác
suất hậu nghiệm phân tán dựa trên những tri thức đã tính toán được thông qua
tần suất trong tổng thể dân số lớn hoặc tần suất trong tập huấn luyện.
Kiểm tra: Sau khi xây dựng xong bộ phân lớp, có thể dễ dàng kiểm tra,
kiểm thử việc phân lớp với một bộ dữ liệu dùng kiểm tra (test) như sau:


- 16 -

Sex

height (feet)

weight (lbs)

6

130

Sample

foot size(inches)
8

Để xác định hậu nghiệm lớn hơn, đối với phân lớp male cho bởi:
Posterior(male) =



|

)

Evidence được tính bởi:
evidence =
(

)r(

(

|

)r(

)r(

|

|

)r(

)r(

|

|

Trong đó:
= 5.85 và

= 3.5033 .10

là các tham số của phân tán đã được xác

định trước đó từ trong tập huấn luyện. Nếu giá trị >1 là chấp nhận được:

r(

|

r(

) = 5.9881 .10
|

) = 1.3112 .10

Posterior numerator (male) = their product = 6.1984 .10
P(female) = 0.5

r(
r(
r(

|
|