-i -
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG
---------
---------
NGUYỄN THỊ THÙY DƢƠNG
NGHIÊN CỨU LÝ THUYẾT NAIVE BAYES VÀ
ỨNG DỤNG TRONG PHÂN LOẠI VĂN BẢN TIẾNG VIỆT
Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số: 60.48.0101
LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH
Ngƣời hƣớng dẫn khoa học:
TS. NGUYỄN THỊ THU HÀ
THÁI NGUYÊN, NĂM 2015
Số hóa bởi Trung tâm Học liệu - ĐHTN
http://www.lrc-tnu.edu.vn/
-ii -
LỜI CAM ĐOAN
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
văn.
Xin chân thành cảm ơn!
Thái Nguyên, ngày 20 tháng 08 năm 2015
Số hóa bởi Trung tâm Học liệu - ĐHTN
http://www.lrc-tnu.edu.vn/
-iv -
MỤC LỤC
LỜI CAM ĐOAN......................................................................................i
LỜI CẢM ƠN..........................................................................................iii
DANH SÁCH CÁC BẢNG.....................................................................vi
Chƣơng 1: TỔNG QUAN VỀ PHÂN LOẠI VĂN BẢN........................3
1.1. Giới thiệu bài toán phân loại văn bản tiếng Việt........................................................ 3
1.1.1. Tổng quan bài toán phân loại văn bản................................................................. 3
1.1.2. Mô hình hệ thống phân loại văn bản....................................................................4
1.1.3. Các khái niệm cơ bản trong phân loại văn bản....................................................5
1.2. Các nghiên cứu liên quan............................................................................................9
1.2.1. Đánh giá phân loại văn bản................................................................................11
1.2.2. Lý thuyết Naive Bayes.......................................................................................11
1.2.3. Khái niệm...........................................................................................................12
1.3. Kết luận chƣơng 1.................................................................................................... 17
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.................................................................18
TÀI LIỆU THAM KHẢO.......................................................................60
Số hóa bởi Trung tâm Học liệu - ĐHTN
http://www.lrc-tnu.edu.vn/
-vi -
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
Bảng 3.2. Danh sách một số từ trong tập từ chủ đề................................49
Bảng 3.3. Độ triệu hồi khi thực hiện các truy vấn.................................. 57
Số hóa bởi Trung tâm Học liệu - ĐHTN
http://www.lrc-tnu.edu.vn/
-vii -
DANH SÁCH HÌNH VẼ
Hình 1.1. Quá trình học phân loại văn bản............................................... 4
Hình 1.2. Mô hình SVM........................................................................... 8
Hình 2.1. Mô tả bƣớc xây dựng bộ phân lớp..........................................21
Hình 2.2. Trực quan hóa dữ liệu giảm chiều...........................................26
Hình 2.3. Danh sách một số từ dừng.......................................................27
http://www.lrc-tnu.edu.vn/
-ix -
DANH SÁCH CÁC CHỮ VIẾT TẮT
Viết tắt
Tiếng Anh
Tiếng Việt
k- NN
SVM
k- Nearest Neighbor
Support Vector Machine
k-Láng giềng gần nhất
Máy véc tơ hỗ trợ
RSS
Really Simple Syndication
Định dạng tập tin
ML
Machine Languages
Đề tài “Nghiên cứu lý thuyết Naive Bayes và ứng dụng trong phân loại
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.
Số hóa bởi Trung tâm Học liệu - ĐHTN
http://www.lrc-tnu.edu.vn/
-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
1.1. Giới thiệu bài toán phân loại văn bản tiếng Việt
1.1.1. Tổng quan bài toán phân loại văn bản
Các nghiên cứu về khai phá dữ liệu dạng văn bản đang đƣợc quan tâm
hơn trong thời gian gần đây vì số lƣợng các tài liệu điện tử tăng nhanh chóng
từ nhiều nguồn khác nhau. Không kể tới những văn bản có cấu trúc, số lƣợng
các văn bản không cấu trúc và cấu trúc cũng tăng lên quá lớn. Mục đích chính
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 = {d 1,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].
Số hóa bởi Trung tâm Học liệu - ĐHTN
http://www.lrc-tnu.edu.vn/
-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
Phân loại
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.
- Pha phân loại: Văn bản đầu vào đƣợc trích rút thành các đặc trƣng và
dựa trên mô hình chuẩn đã đƣợc học để phân theo đúng nhãn.
Đối với những bài toán xử lý phân loại các đối tƣợng, việc quan trọng
Số hóa bởi Trung tâm Học liệu - ĐHTN
http://www.lrc-tnu.edu.vn/
-5 -
là xác định đặc trƣng bởi hầu hết trong những bài toán này, số chiều đặc
trƣng dƣờng nhƣ là khá lớn, bởi thế, các đề xuất trƣớc đây [5] sẽ gặp phải
những khó khăn sau:
- Thời gian tính toán lớn (do số chiều đặc trƣng cao)
- Độ chính xác cũng nhƣ hiệu năng của hệ thống bị hạn chế.
1.1.3. Các khái niệm cơ bản trong phân loại văn bản
1.1.3.1. Tập văn bản huấn luyện (Training documents set)
Tập văn bản huấn luyện là một tập hợp các dữ liệu đƣợc sử dụng trong
các quá trình tìm kiếm những quan hệ, các luật để dùng cho dự đoán hoặc dự
báo sau này.
1.1.3.2. Tiền xử lý (Preprocessing)
Tiền xử lý là một bƣớc quan trọng trƣớc khi nhận diện văn bản hoặc
T2
w11 w21
...
wt1 c1
D2
w12 w22
...
wt2 c2
Dn
w1n w2n
...
wtn cn
T1
Trong đó mỗi một phần tử biểu diễn tần suất xuất hiện của tử trong văn
bản và wtn là trọng số của từ i trong văn bản n. Có rất nhiều cách để xác định
các trọng số w trong ma trận trên, có thể sử dụng phƣơng pháp trọng số
Boolean, trọng số tần xuất từ, mô hình tf-idf, entropy,...[3]
1.1.3.4 Trích chọn đặc trưng (Feature selection)
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( ,
-
,
Trong đó: y (di, c) thuộc {0,1}, với:
+ y = 0 : văn bản di không thuộc về chủ đề cj
+
y = 1 : văn bản d i thuộc về chủ đề cj sim (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 Cô sin
để tính khoảng cách:
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
+
-
- -
-
-
+ 1, khi ( . + ) > 0
− 1, khi ( . + ) < 0
→
→
Từ đó h ( d ) biểu diễn sự phân lớp của di
vào 2 lớp nói trên
i
Có yi
→
→
= { ±1} thì với yi= +1, văn bản di ∈ “+”;với yi= -1, văn bản di ∈
“-”.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
, trong đó wi
đƣợ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
Số hóa bởi Trung tâm Học liệu - ĐHTN
http://www.lrc-tnu.edu.vn/
-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
(1999); Yang and Liu (1999). Trong mô hình nhiều lớp này có thể thể hiện
đƣợc sự tƣơng tác giữa các thuật ngữ và có khả năng học tốt hơn [9].
Các nghiên cứu về tiếng Việt mới đƣợc phát triển từ những năm 2004 2005, do đó các công bố về phân loại văn bản tiếng Việt còn ít so với tiếng
Anh. Mặt khác, các kho dữ liệu và các công cụ phục vụ cho nghiên cứu tiếng
Việt còn thiếu hoặc hiệu quả chƣa cao, một số các nghiên cứu đều dừng lại ở
mức tìm hiểu, đề xuất phƣơng pháp mà chƣa xây dựng hệ thống hoàn chỉnh.
Các kho dữ liệu chƣa thống nhất và tự do các nhóm nghiên cứu tự xây dựng
phục vụ cho nghiên cứu của mình. Chƣa thành lập đƣợc các chuẩn đánh giá
hiệu năng cho các hệ thống phân loại văn bản.
Một số các nghiên cứu phân loại tiếng Việt tập trung vào ứng dụng các
phƣơng pháp máy học hoặc áp dụng các phƣơng pháp đã đƣợc đề xuất hiệu
π=
||
=1
| |
+
||
ρ=
||
=1
| |
||
=
=1 +
||
=1
Độ hồi tƣởng (ρ)
TNi, FPi và FNitham 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
Số hóa bởi Trung tâm Học liệu - ĐHTN
http://www.lrc-tnu.edu.vn/
-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
- P(B): Xác suất của sự kiện B xảy ra.
- P(B|A): Xác suất (có điều kiện) của sự kiện B xảy ra,nếu biết rằng sự
kiện A đã xảy ra.
- P(A|B): Xác suất (có điều kiện) của sự kiện A xảy ra, nếu biết rằng sự
kiện B đã xảy ra.
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 ρ(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:
ρ(C|F1, . ., Fn) =
ρ C ρ(F1,..,Fn |C)
ρ(F1
,..,Fn |C)
Một cách mô tả đơn giản cho công thức trên nhƣ sau:
Hậu nghiệm =
ệ
ƣớ × ả ă ằ ứ
Trên thực tế, chỉ cần quan tâm tới số các phân mảnh (fraction), bởi có
một số đặc trƣng không phụ thuộc vào C và các giá trị Fi đã cho, mô hình
2
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à:
ρ(C|F1,. . ., Fn) = ρ(C)
1
ρ( | )
=1
Với Z = ρ(F1,. . ., Fn) đƣợc gọi là nhân tố độc lập trên F 1,. . ., 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:
( , … , ) ==
1
( = | C=c)
=1
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.
Số hóa bởi Trung tâm Học liệu - ĐHTN
5.855
Female 5.4175
3.5033e-02 176.25
9.7225e-02 132.5
variance
mean
(foot
size)
1.2292e+02
5.5833e+02
11.25
7.5
variance
(foot size)
9.1667e-01
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:
Số hóa bởi Trung tâm Học liệu - ĐHTN
Copyright: Tài liệu đại học ©