ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGHIÊN CỨU CẢI TIẾN MỘT SỐ PHƯƠNG PHÁP
PHÂN LOẠI VĂN BẢN TỰ ĐỘNG VÀ ÁP DỤNG
TRONG XỬ LÝ VĂN BẢN TIẾNG VIỆT Ngành: Công nghệ thông tin
Chuyên ngành: Công nghệ phần mềm
Mã số: 60 48 10
2.3.3. Thông tin tƣơng hỗ (MI) 19
2.3.4. Thống kê Chi bình phƣơng
2
20
2.3.5. Cƣờng độ của từ (TS) 21
2.3.6. Một số phƣơng pháp khác 22
2.4. Tổng kết chƣơng 22
CHƢƠNG 3 - CÁC PHƢƠNG PHÁP PHÂN LOẠI VĂN BẢN TRUYỀN
THỐNG 24
3.1. Phƣơng pháp Rocchio 24
3.2. Phƣơng pháp k- Nearest Neighbour 24
3.3. Phƣơng pháp Naïve Bayes (NB) 25
3.4. Phƣơng pháp Linear Least Square Fit- LLSF 27
2 3.5. Phƣơng pháp Centroid- based vector 28
3.6. Phƣơng pháp SVM- Support Vector Machine 28
3.7. Một số phƣơng pháp khác 32
3.8. Phƣơng pháp đánh giá 32
3.9. Tổng kết chƣơng 33
CHƢƠNG 4 - PHÂN LOẠI VĂN BẢN TIẾNG VIỆT 35
4.1. Tiếng Việt và một số đặc điểm của tiếng Việt 35
4.1.1. Cấu trúc từ trong tiếng Việt 35
4.1.2. So sánh tiếng Việt và tiếng Anh 37
4.2. Bài toán phân loại văn bản tiếng Việt 38
4.3. Vấn đề tách từ trong văn bản tiếng Việt 39
4.3.1. Tách từ trong văn bản tiếng Việt dựa trên từ 40
4.3.2. Tách từ trong văn bản tiếng Việt dựa trên ký tự 41
7.1. Công cụ chiết xuất nội dung từ các web-site báo điện tử 85
7.2. Chƣơng trình phân đoạn từ tiếng Việt và tạo các ma trận thuộc tính 88
7.3. Công cụ chiết xuất thuộc tính KSG và đƣa ra ma trân thuộc tính 91
7.4. Công cụ mở rộng tập dữ liệu kết hợp phân cụm 93
7.5. Phân lọai văn bản sử dụng thƣ viện LibSVM 93
7.6. Công cụ phân loại theo phƣơng pháp kNN và Centroid based vector 94
KẾT LUẬN 96
1. Nhận xét chung 96
2. Hƣớng phát triển 98
Tài liệu tham khảo 100
PHỤ LỤC A: Phân tích thiết kế chƣơng trình phân loại văn bản tự động sử
dụng thuộc tính nhóm xâu con chính. 103
1. Yêu cầu của chƣơng trình 103
2. Phân tích 103
2.1. Mô hình ca sử dụng. 103
2.2. Biểu đồ tuần tự hệ thống và mô hình khái niệm 104
3. Thiết kế 106
3.1. Thao tác trên tập ngữ liệu 106
3.2. Xử lý thuộc tính xâu con chính. 108
3.3. Phân loại văn bản bằng phƣơng pháp SVM 110
4. Cài đặt chƣơng trình 111
PHỤ LỤC B: Cấu trúc đĩa CD đi kèm 113
PHỤ LỤC C: Chia sẽ dữ liệu, các công cụ và chƣơng trình liên quan 114
Chỉ mục từ 116
4
Danh sách các hình
Hình 1-1: Các bƣớc chính trong phân loại văn bản 13
Bảng 3-1: Kết quả thực nghiệm của T. Joachims, so sánh phƣơng pháp SVM
với một số phƣơng pháp khác trên Corpus Reuters 31
Bảng 4-1: Cấu trúc âm tiết trong tiếng Việt 35
Bảng 4-2: So sánh tiếng Việt và Tiếng anh 37
Bảng 4-3: Thống kế nguồn gốc dữ liệu trong corpus 49
Bảng 4-4: Thống kê dữ liệu trong corpus cho từng nhóm văn bản 50
Bảng 4-5: Kết quả phân loại sử dụng một số phƣơng pháp truyền thống 51
Bảng 5-1: Kết quả thực nghiệm phân lọai sử dụng phân cụm 67
Bảng 6-1: Sự phụ thuộc của số thuộc tính KSG với các tham số đầu vào 81
Bảng 6-2: Kết quả sử dụng hàm nhân tuyến tính và hàm nhân RBF 82
Bảng 6-3: So sánh phƣơng pháp SVM và SVM+KSG 83
Bảng A-1: Danh sách ca sử dụng 104
Bảng A-2: Ánh xạ giữa lớp thiết kế và các file cài đặt 111
6 Danh sách từ viết tắt
Từ viết tắt
Từ gốc
ARAM
Adaptive Resonance Associative Map
CBC
Clustering Based Text Classification
Conf
Confidence Weight
CSDL
Cơ sở dữ liệu
DF
Document Frequency
FSM
Support Vector Machine
TBL
Transformation based learning
TC
Text Categorization
TF
Term Frequency
TM2
Second Moment of Term
TS
Term Strength
TSVM
Transductive Support Vector Machine
WFST
Weight Finite State Transducer 7 Bảng thuật ngữ Anh-Việt
Tiếng Anh
Tiếng Việt
Bioinfomatics
Tin sinh học
Centroid
Trọng tâm
Context predicate
Thành phần ngữ cảnh
Machine Learning
Học máy
Mutual information
Thông tin tƣơng hỗ
Pattern regconition
Nhận dạng mẫu
Reinforcement Learning
Học củng cố
Stop word
Từ dừng
Suffix tree
Cây hậu tố
Syllable
Âm tiết
Unseen new document
Văn bản mới cần đoán nhận
Word clustering
Phân cụm theo từ
Word stemming
Xác định từ gốc
8 MỞ ĐẦU
1. Cơ sở khoa học và tính thực tiễn của đề tài.
Từ khi Internet ra đời, chúng ta đã chứng kiến sự phát triển không ngừng
về số lƣợng thông tin trực tuyến trên Internet. Nếu chúng ta xem World Wide
Web nhƣ một Cơ sở dữ liệu-CSDL, thì CSDL này là khổng lồ, rất hỗn tạp và
đa phƣơng tiện, tuy nhiên trong số đó có hơn 80% lƣợng thông tin là dƣới
dạng văn bản. Với CSDL lớn nhƣ thế, việc tìm kiếm thông tin nào đó của
Machine), kNN (k- Nearest Neighbor), Naïve Bayes…
- Tìm hiểu về bài toán phân loại văn bản tiếng Việt, với các vấn đề sau:
+ Thuận lợi và khó khăn.
+ Đặc điểm của tiếng Việt, cấu trúc từ trong tiếng Việt.
+ Vấn đề phân đoạn từ trong tiếng Việt, Vietnamese word segmentation,
vấn đề tập ngữ liệu tiếng Việt (Vietnamese corpus) …
+ Áp dụng một số thuật toán vào bài toán phân loại văn bản tiếng Việt.
+ Cài đặt các công cụ và thuật toán liên quan.
+ Thực nghiệm và kết quả thực nghiệm phân loại văn bản tiếng Việt sử
dụng một số thuật toán tiêu biểu.
- Nghiên cứu một số hƣớng cải tiến của phân loại văn bản phù hợp với bối
cảnh Việt Nam và tiếng Việt.
+ Sử dụng phân cụm trong phân loại văn bản.
+ Sử dụng thuộc tính nhóm xâu con chính trong phân loại văn bản.
+ Cài đặt các công cụ và thuật toán liên quan.
+ Thực nghiệm và kết quả thực nghiệm.
3. Bố cục và cấu trúc của luận văn
Luận văn đƣợc cấu trúc nhƣ sau.
- Chƣơng 1: Trình bày tổng quan về phân loại văn bản.
- Chƣơng 2: Trình bày vấn đề biểu diễn văn bản trong phân loại văn bản
dƣới dạng vector thuộc tính, và một số phƣơng pháp giảm kích thƣớc
của không gian thuộc tính nhƣ sử dụng danh sách từ dừng, tìm gốc của
từ, vấn đề trọng số và các phƣơng pháp lựa chọn thuộc tính.
- Chƣơng 3: Trình bày các phƣơng pháp phân loại văn bản truyền thống.
- Chƣơng 4: Áp dụng trong phân loại văn bản tiếng Việt, đặc điểm của
tiếng Việt, so sánh với các ngôn ngữ khác, thực nghiệm và kết quả thực
nghiệm cho bài toán phân loại tiếng Việt.
10
m
}
D là tập các văn bản: D={d
1
,d
2
,…, d
n
}
Phân loại văn bản là một hàm
fTC
đƣợc định nghĩa trong (1-1):
: {0,1}fTC C D
(1-1)
Với:
( , ) 0
ij
fTC c d
, nếu d
j
không thuộc nhóm c
i
.
( , ) 1
ij
fTC c d
, nếu d
j
thuộc nhóm c
mà văn bản có thể thuộc vào. Tập văn bản đƣợc phân thành các chủ đề khác
nhau.
Ví dụ: Giáo dục, Thể thao, Du lịch
- Phân loại văn bản theo ngữ nghĩa: đây là cách phân loại dựa vào ngữ
nghĩa trong văn bản đề phân loại chúng.
Ví dụ: Spam hay không spam, đƣợc đề nghị hay không đƣợc đề nghị
Nhận dạng mẫu và học máy đƣợc áp dụng vào phân loại văn bản, một số
phƣơng pháp đã đƣợc giới thiệu và sử dụng nhƣ Mạng Neutral, Cây quyết
định, kNN, Naïve Bayes, LLFS, SVM… các phƣơng pháp thu đƣợc các kết
quả khả quan. Gần đây, hƣớng nghiên cứu tập trung vào tăng độ chính xác và
hiệu năng của phân loại nhƣ giảm kích thƣớc không gian thuộc tính, sử dụng
tập dữ liệu gán nhãn nhỏ hay kết hợp học không giám sát. Hầu hết các
phƣơng pháp phân loại ban đầu đƣợc xây dựng và thí nghiêm cho văn bản
tiếng Anh sau đó dƣợc áp dụng cho văn bản trên các ngôn ngữ khác. Tuy
nhiên trong nhiều trƣờng hợp các ngôn ngữ khác nhau có những đặc điểm
khác nhau, nên các bƣớc trong phân loại cho các ngôn ngữ khác nhau có thể
sẽ có các biến đổi và mực độ chính xác do đó cũng khó đồng nhất cho mọi
ngôn ngữ.
13 1.2. Các bƣớc chính trong bài toán phân loại văn bản
Mô hình phân loại văn bản tổng quát gồm các bƣớc, mô tả trong hình 1-1:
- Tiền xử lý.
- Tạo chỉ mục.
- Chọn thuộc tính.
- Áp dụng thuật toán phân loại.
Tập văn bản
Đánh giá kết quả
Hình 1-1: Các bƣớc chính trong phân loại văn bản
14 Tạo chỉ mục là việc tính toán trọng số cho các thuộc tính bằng cách áp
dụng các phƣơng pháp tính trọng số nhƣ tần xuất từ TF, tần xuất từ kết hợp
tần xuất văn bản ngƣợc TFIDF…
Chọn thuộc tính là căn cứ vào trọng số, sử dụng một số phƣơng pháp chọn
thuộc tính nhƣ Tần xuất văn bản, Lợi ích thông tin, Thông tin tƣơng hỗ để
loại đi các thuộc tính không có ý nghĩa thông tin và không ảnh hƣởng đến kết
quả phân loại. Việc lựa chọn thuộc tính giúp giảm kích thƣớc không gian
thuộc tính, giảm thời gian tính toán, tránh overfitting, và tăng hiểu năng của
thuật toán sử dụng.
Áp dụng thuật toán phân loại là việc sử dụng một thuật toán phân loại hợp
lý để tiến hành huấn luyện và kiểm thử hiệu quả phân loại.
Việc đánh giá kết quả bao gồm xem xét và đánh giá thời gian huấn luyện,
thời gian kiểm thử, độ chính xác của phân loại. Các Tiêu chí thông thƣờng là
thời gian tính toán hiệu quả và độ chính xác cao.
Trong học máy, bài toán phân loại văn bản đƣợc minh họa nhƣ trong Hình
1-2.
Hình 1-2: Mô hình trong học máy
thể và khả quan nào về vấn đề này. Tuy nhiên, đã có những bằng chứng cho
thấy đối với những văn bản dài, việc xem xét các thông tin bổ sung ngoài tập
hợp các từ là không có nhiều ý nghĩa.
Hiện nay, các phƣơng pháp thể hiện văn bản hoặc sử dụng các thuộc tính
boolean để cho biết nếu một từ nào đó đã xuất hiện trong một văn bản không,
hoặc sử dụng tần số xuất hiện của một từ trong một văn bản cho trƣớc. Cho dù
là phƣơng pháp nào đƣợc sử dụng đi chăng nữa, vần đề ở đây là, số lƣợng
thuộc tính sẽ là rất lớn, đặc biệt khi mà văn bản rất dài. Để giải quyết vấn đề
này ta phải loại bỏ đi một số thuộc tính và giảm kích thƣớc của không gian
thuộc tính.
2.2. Việc lựa chọn thuộc tính
Quá trình lựa chọn sẽ chọn những thuộc tính để sử dụng trong việc phân
loại. Các thuộc tính không có (hoặc ít) ý nghĩa thông tin cũng nhƣ không ảnh
hƣởng đến kết quả phân loại có thể bị lƣợc bỏ, nhƣ thế việc phân loại sẽ đƣợc
thực hiện trong một không gian thuộc tính nhỏ hơn. Bằng cách thu nhỏ lại
kích cỡ của không gian thuộc tính, không những việc huấn luyện và kiểm thử
sẽ trở nên hiệu quả hơn, mà những ảnh hƣởng của overfitting đƣợc hạn chế đi.
Quá trình lựa chọn bao gồm các bƣớc sau: loại bỏ các từ dừng, xác định gốc
của từ, và lựa chọn thuộc tính.
2.2.1. Loại bỏ các từ dừng
Các từ có tần xuất xuất hiện lớn, có nội dung thông tin thấp, hoặc không có
tác dụng phân biệt đƣợc gọi là các từ dừng.
Ví dụ trong tiếng Anh các mạo từ “a, the, an, that, so…”, là các từ dừng
vì chúng chứa đựng ít thông tin cũng nhƣ nội dung thông tin thấp. Việc loại bỏ
các từ dừng đƣợc thực hiện bằng cách, một danh sách các từ dừng đƣợc cung
cấp từ trƣớc, trong quá trình xử lý văn bản, nếu một từ thuộc danh sách này thì
sẽ bị loại bỏ và không đƣợc đƣa vào không gian thuộc tính.
17
18 Giới hạn Tần xuất văn bản là phƣơng pháp đơn giản nhất cho việc giảm bớt
từ vựng. Nó có thể thực hiện việc giới hạn đối với mọi tập văn bản lớn, với độ
phức tạp tính toán tỉ lệ thuận với số lƣợng các văn bản có trong tập huấn
luyện. Tuy nhiên, phƣơng pháp này đƣợc đánh giá là không ổn định trong việc
nâng cao hiệu quả, và không phải là một nguyên lí tiêu chuẩn cho việc lựa
chon thuộc tính. Bên cạnh đó, Tần xuất văn bản cũng không đƣợc sử dụng cho
quá trình loại bỏ từ mang ý nghĩa đặc biệt bởi sự giả định trong quá trình lấy
lại thông tin. Tức là, một số từ có tần xuất văn bản thấp nhƣng có nhiều ý
nghĩa thông tin thì không nên bị bỏ đi.
Một số biến thể của phƣơng pháp này là sử dụng tần xuất văn bản ngƣợc
(IDF) hay kết hợp với tần xuất của từ TF-IDF. Tần xuất của một từ t trong văn
bản d đƣợc định nghĩa là số lần xuất hiện của từ đó trong d.IDF đƣợc tính theo
công thức:
r
i
ri
T
IDF(t )=log
#T (t )
(2-1)
Trong (2-1),
r
2.3.2. Lợi ích thông tin (IG)
Phƣơng pháp này đƣợc sử dụng thƣờng xuyên nhƣ một tiêu chuẩn trong
lĩnh vực học máy. Phƣơng pháp này xác định số lƣợng thông tin thu đƣợc cho
quá trình dự đoán bằng cách xác định liệu một từ nào đó có xuất hiện hay
không trong một văn bản. Nếu ta coi {c
i
}
m
i=1
biểu thị cho tập các lớp. Lợi ích
thông tin từ t sẽ đƣợc xác định nhƣ (2-3):
19
11
( ) ( )log ( ) ( ) ( | )log ( | )
mm
r i r i r r i r i
ii
G t P c P c P t P c t P c t
1
( ) ( | )log ( | )
m
r r i r i
i
rr
P t c
I t c
P t P c
(2-4)
Và đƣợc ƣớc lƣợng theo (2-5):
.
( , ) log
( ).( )
AN
I t c
A C A B
(2-5)
20 I(t,c) sẽ có giá trị bằng 0 nếu t và c không phụ thuộc lẫn nhau. Để xác định
giá trị của một từ trong quá trình lựa chọn thuộc tính toàn cục, Ta kết hợp các
điểm số của môt nhóm với một từ theo hai cách:
1
( ) ( ). ( , )
m
Phƣơng pháp này tính sự phụ thuộc giữa t và c và có thể đƣợc so sánh với
phân phối
2
. Sử dụng bảng ngẫu nhiên 2 chiều của một từ t và một lớp c, A
là số lần t và c cùng xuất hiện, B là số lần t xuất hiện không có c, C là số lần c
xuất hiện không có t, D là số lần t và c đều không xuất hiện, và N là tổng số
văn bản , trọng số của từ đƣợc xác định theo (2-9):
2
2
.( )
( , )
( ).( ).( ).( )
N AD CB
tc
A C B D A B C D
(2-9)
Số liệu
2
sẽ có giá trị bằng 0 nếu t và c không phụ thuộc lẫn nhau. Ta
tính, với mỗi nhóm, thông kê
(2-11)
Quá trình tính toán giá trị CHI có độ phức tạp bậc hai, tƣơng tự nhƣ đối
nhƣ với IG và MI. Điểm khác biệt chính giữa CHI và MI là
2
là một giá trị
đã đƣợc chuẩn hóa, vì vậy các giá trị
2
có thể đƣợc dùng để so sánh giữa các
từ trong cùng một nhóm văn bản. Bởi vậy, phƣơng pháp này không thích hợp
với những từ có tần số thấp.
2.3.5. Cƣờng độ của từ (TS)
Phƣơng pháp này đƣợc đề xuất và đánh giá bởi Wilbur và Sirotkin [6] cho
việc làm giảm bớt từ vựng trong quá trình thu thập dữ liệu văn bản, và sau này
đƣợc ứng dụng bởi Yang và Wilbur cho việc phân loại văn bản. Phƣơng pháp
này ƣớc lƣợng mức quan trọng của từ dựa trên việc mức độ xuất hiện của từ
đó trong những tài liệu có nội dụng liên quan chặt chẽ với nhau. Nó sử dụng
một tập hợp các văn bản huấn luyện để sinh ra những cặp văn bản có độ tƣơng
tự (đƣợc tính toán dựa trên giá trị cosine của 2 vectors đại diện cho 2 văn bản
đó) lớn hơn một ngƣỡng. “Cƣờng độ từ” sau đó đƣợc tính toán dựa trên xác
suất có điều kiện của một từ sẽ xuất hiện trong nửa thứ hai của một cặp văn
bản, với điều kiện cho trƣớc là từ đó xuất hiện ở nửa thử nhất của cặp văn bản.
Nếu ta coi x và y là một cặp văn bản bất kì có nội dung liên quan, và t là một
từ, vậy thì giá trị trọng số của từ đó đƣợc xác định nhƣ (2-12):
s(t) = Pr(t
y |t
phối từ cố định [9], thực nghiệm của H. Xu cho thấy phƣơng pháp này cho
kết quả tốt hơn Conf, IDF và IG.
2.4. Tổng kết chƣơng
Nhƣ vậy, trong phân loại văn bản, văn bản đƣợc biểu diễn dƣới dạng
vector thuộc tính. Tuy nhiên khi đó ta sẽ có không gian thuộc tính với số chiều
lớn, và các vector thƣa. Để giảm độ phức tạp tính toán, tăng hiệu năng của
thuật toán phân loại, và giảm không gian bộ nhớ cần thiết để lƣu trữ dữ liệu.
Ta sử dụng các phƣơng pháp làm giảm khích thƣớc không gian thuộc tính nhƣ
loại bỏ các từ dừng bằng các xây dựng danh sách các từ dừng, xác định gốc
của từ và sử dụng các phƣơng pháp lựa chon thuộc tính nhƣ ngƣỡng tần xuất
văn bản (DF), thông tin thu đƣợc (IG), thông tin tƣơng hỗ (MI), thống kê Chi
bình phƣơng (
2
), hay cƣờng độ từ (TS). Thực nghiệm của Y. Yang [5] cho
thấy có mối quan hệ chặc chẽ giữa các phƣơng pháp DF, IG va CHI. Điều này
chứng tỏ DF không chỉ là một phƣơng pháp đơn giản mà có thể sử dụng để
thay thế IG va CHI, khi mức độ tính toán của các phƣơng này là quá phức tạp
và mất nhiều thời gian. Yang cho rằng IG va CHI tỏ ra hiệu quả nhất mặc dù
23 loại bỏ đi một số lƣợng lớn các thuộc tính mà không ảnh hƣởng đến độ chính
xác của kết quả phân loại (bỏ đi 98% các từ duy nhất), DF có kết quả tƣơng
đƣơng với CH khi 90% từ đƣợc loại và TS có kết quả tƣơng đƣơng với
khoảng 50% từ đƣợc loại.
Nhƣ vây có thể thấy DF, IG và CHI là hiệu quả và có thể áp dụng vào bài
toán phân loại văn bản trong thực tế. Lựa chọn thuộc tính tiếp tục đƣợc nghiên
cứu với nhiều công trình và kết quả cho tới nay. Tuy nhiên hiện chƣa có các
thực nghiệm và đánh giá so sánh tính hiệu quả của các phƣơng pháp lựa chọn
hình, văn bản kiểm thử sẽ đƣợc gép vào nhóm có độ tƣơng tự cao nhất.
Nhận xét:
Ƣu điểm:
- Dễ cài đặt.
- Thời gian học rất nhanh.
Nhƣợc điểm:
- Tính chính xác thấp
- Các kết hợp tuyến tính quá đơn giản đề phân loại.
- Các tham số α và β trong (3-1) đƣợc xác định bằng thực nghiệm.
3.2. Phƣơng pháp k- Nearest Neighbour
kNN hay k – láng giềng gần nhất là phƣơng pháp phân loại văn bản 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. kNN đƣợc đánh giá là một trong những phƣơng pháp phân
loại văn bản tốt nhất đƣợc sử dụng từ thời kỳ đầu trong những 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 (ở đây có thể áp dụng các công thức về khoảng
cách nhƣ Euclide, Cosine, Manhattan,…) của tất cả các văn bản trong tập
huấn luyện đến văn bản cần phân loại để tìm ra k văn bản gần nhất, gọi là k-
Nearest Neighbour (k láng giềng gần nhất), 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à
Copyright: Tài liệu đại học ©