Tóm tắt : Khai phá và phát hiện tri thức trong dữ liệu,các bài toán cơ bản trong xử lý văn bản phân nhóm phương pháp học không giám sát,phân nhóm dựa trên thuật ngữ xuất hiện thường xuyên(Frequenitemset)phân lớp,phương pháp học có giám sát bài toán phân lớp văn bản tiếng việt đề xuất hai hướng tiếp cận bài toá n theo phương pháp học không giám sát trong học cơ giám sát theo đề xuất theo cải tiến công thức đánh giá độ liên quan giữa hai văn bản trong mô hình véctơ thiết kế xây dựng hệ thống thử nghiệm cài đặt mô hình và kết quả thử nghiệm
Mô tả: Luận văn thạc sỹ Chuyên ngành Công nghệ thông tin
®inh thÞ ph¬ng thu
Bé gi¸o dôc vµ ®µo t¹o
Trêng ®¹i häc b¸ch khoa Hµ Néi
-------***-------
§inh ThÞ Ph¬ng Thu
tiÕp cËn häc kh«ng gi¸m s¸t trong häc cã gi¸m s¸t
ngµnh c«ng nghÖ th«ng tin
víi bµi to¸n ph©n líp v¨n b¶n tiÕng viÖt &
®Ò xuÊt c¶i tiÕn c«ng thøc tÝnh ®é liªn quan gi÷a hai
v¨n b¶n trong m« h×nh vector
luËn v¨n th¹c sÜ c«ng nghÖ th«ng tin
kho¸ 2002 - 2004
Hµ néi - N¨m 2004
bé gi¸o dôc vµ ®µo t¹o
trêng ®¹i häc b¸ch khoa hµ néi
----------***--------§inh ThÞ Ph¬ng Thu
tiÕp cËn häc kh«ng gi¸m s¸t trong häc cã gi¸m s¸t víi bµi
to¸n ph©n líp v¨n b¶n tiÕng viÖt &
®Ò xuÊt c¶i tiÕn c«ng thøc tÝnh ®é liªn quan gi÷a hai v¨n
b¶n trong m« h×nh vector
Chuyªn ngµnh: C«ng nghÖ th«ng tin
luËn v¨n th¹c sÜ c«ng nghÖ th«ng tin
ngêi híng dÉn khoa häc
TS. Huúnh QuyÕt Th¾ng
Hµ néi - 11/2004
- Trang 1 -
MỤC LỤC
MỤC LỤC .......................................................................................................... 1
Danh mục các thuật ngữ và ký hiệu viết tắt trong Luận văn ...................... 6
Danh mục các bảng trong Luận văn .............................................................. 8
Danh mục các hình vẽ trong Luận văn .......................................................... 9
MỞ ĐẦU .......................................................................................................... 10
phÇn i c¬ së lý thuyÕt ................................................................................... 13
CHƯƠNG 1 - TỔNG QUAN VỀ XỬ LÝ VĂN BẢN...................................... 14
1.1. Khai phá và phát hiện tri thức trong dữ liệu ................................................ 15
1.1.1. Dữ liệu, Thông tin và Tri thức...........................................................................15
1.1.2. Khai phá dữ liệu và phát hiện tri thức ..............................................................15
1.2. Text Mining - Góc nhìn nhận quan trọng trong Data Mining .................... 18
1.3. Các khái niệm cơ bản trong xử lý văn bản .................................................... 19
1.3.1. Từ khóa, Thuật ngữ và Khái niệm ....................................................................19
1.3.2. Từ dừng (StopW ords ).......................................................................................20
1.3.3. Trọng số của thuật ngữ ....................................................................................20
1.3.4. Độ liên quan giữa các văn bản .........................................................................21
1.4. Các bài toán cơ bản trong xử lý văn bản ....................................................... 21
1.4.1. Tìm kiếm văn bản (Tex t Retrieval ) ...................................................................21
1.4.2. Phân lớp văn bản (Tex t Categorization, Tex t Classification ) ...........................22
1.4.3. Phân nhóm văn bản (Tex t Clustering ) ............................................................22
1.4.4. Tóm tắt văn bản (Tex t Sum m arization ) ...........................................................23
1.4.5. Dẫn đường văn bản (Tex t Routing ) ..................................................................23
1.5. Các phương pháp biểu diễn văn bản ............................................................. 24
1.5.1. Mô hình không gian vector (Vector Space M odel - VSM ) .................................24
1.5.1.1. Mô hình Boolean ............................................................................................ 25
§inh ThÞ Ph¬ng Thu -
LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi
11/2004
- Trang 2 1.5.1.2. Mô hình tần số ............................................................................................... 26
1.5.1.3. Phương pháp xử lý véc tơ thưa ...................................................................... 27
1.5.2. Phương pháp biểu diễn văn bản dựa trên các khái niệm mờ ...........................29
1.6. Kết chương ....................................................................................................... 30
CHƯƠNG 2 PHÂN NHÓM - PHƯƠNG PHÁP HỌC KHÔNG GIÁM SÁT .. 31
2.1. Giới thiệu bài toán phân nhóm ....................................................................... 32
2.1.1. Phân nhóm dữ liệu ...........................................................................................32
2.1.2. Bài toán “Phân nhóm văn bản” ........................................................................32
2.2. Các yêu cầu của kĩ thuật phân nhóm ............................................................. 32
2.3. Các thuật toán Phân nhóm cơ bản hiện nay ................................................. 33
2.3.1. Các phương pháp phân chia (P artitionning Algorithm s )..................................34
2.3.2. Phương pháp phân nhóm dựa trên hàm mật độ (Density-Based ) ...................34
2.3.3. Phương pháp phân nhóm dựa trên lưới (Grid-Based M ethod ) ........................35
2.3.4. Phân nhóm dựa trên thuật ngữ xuất hiện thường xuyên (Frequent I tem set ) 36
2.3.4.1. Các giải thuật xác định tập các thuật ngữ xuất hiện thường xuyên .............. 36
2.3.4.2. Các giải thuật phân nhóm dựa trên thuật ngữ xuất hiện thường xuyên ........ 39
2.4. Đánh giá hiệu suất phân nhóm ....................................................................... 45
2.5. Kết chương ....................................................................................................... 45
CHƯƠNG 3 PHÂN LỚP - PHƯƠNG PHÁP HỌC CÓ GIÁM SÁT ............. 46
3.1. Giới thiệu bài toán ........................................................................................... 47
3.2. Các thuật toán Phân lớp văn bản cơ bản ...................................................... 47
3.2.1. Thuật toán cây quyết định (Decision Tree ) ......................................................48
3.2.1.1. Mô tả cây quyết định ...................................................................................... 48
3.2.1.2. Ví dụ minh họa cây quyết định....................................................................... 48
3.2.1.3. Xây dựng cây quyết định ................................................................................ 51
3.2.2. Thuật toán k-NN (k-Nearest Neighbor ) ...........................................................54
3.3. Đánh giá hiệu suất phân lớp văn bản............................................................. 57
3.4. Kết chương ....................................................................................................... 58
§inh ThÞ Ph¬ng Thu -
LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi
11/2004
- Trang 3 -
CHƯƠNG 4 VẤN ĐỀ NGHIÊN CỨU CỦA LUẬN VĂN - BÀI TOÁN PHÂN
LỚP VĂN BẢN TIẾNG VIỆT ........................................................................... 59
4.1. Khai phá dữ liệu văn bản tiếng Việt .............................................................. 60
4.2. Các đặc trưng của tiếng Việt .......................................................................... 60
4.2.1. Các đơn vị tiếng Việt .........................................................................................61
4.2.2. Các đặc điểm chính tả văn bản tiếng Việt ........................................................61
4.2.3. Từ tiếng Việt .....................................................................................................62
4.2.4. Các chuẩn Font tiếng Việt được sử dụng ..........................................................63
4.3. Bài toán phân lớp văn bản tiếng Việt............................................................. 64
4.4. Kết chương ....................................................................................................... 65
phÇn iI thiÕt kÕ híng tiÕp cËn .................................................................... 66
CHƯƠNG 5 - ĐỀ XUẤT VÀ LỰA CHỌN GIẢI PHÁP TIẾP CẬN BÀI
TOÁN PHÂN LỚP VĂN BẢN TIẾNG VIỆT .................................................... 67
5.1. Đề xuất hai hướng tiếp cận bài toán .............................................................. 68
5.1.1. Hướng tiếp cận theo phương pháp học không giám sát trong học có giám
sát ...............................................................................................................................68
5.1.2. Hướng tiếp cận theo đề xuất cải tiến công thức đánh giá độ liên quan giữa
hai văn bản trong mô hình vector ..............................................................................69
5.2. Lựa chọn giải pháp tiếp cận ............................................................................ 71
5.2.1. Tiếp cận theo phương pháp học không giám sát trong học có giám sát ..........71
5.2.1.1. Tiền xử lý văn bản .......................................................................................... 72
5.2.1.2. Biểu diễn văn bản trong mô hình vector ........................................................ 74
5.2.1.3. Phân nhóm các lớp văn bản mẫu ................................................................... 77
5.2.1.4. Phân lớp văn bản dựa trên tiếp cận phân nhóm ............................................ 78
5.2.2. Tiếp cận theo đề xuất cải tiến công thức đánh giá độ liên quan giữa hai văn
bản trong mô hình vector ...........................................................................................80
5.2.2.1. Mô hình tiếp cận ............................................................................................ 80
5.2.2.2. Tiền xử lý và vector hóa văn bản ................................................................... 81
5.2.2.3. Quản lý độ liên quan giữa các term và văn bản mẫu .................................... 81
5.2.2.4. Phân lớp văn bản với công thức cải tiến đề xuất........................................... 82
5.3. Kết chương ....................................................................................................... 83
§inh ThÞ Ph¬ng Thu -
LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi
11/2004
- Trang 4 -
CHƯƠNG 6 - THIẾT KẾ XÂY DỰNG HỆ THỐNG THỬ NGHIỆM .............. 84
6.1. Xác định yêu cầu .............................................................................................. 85
6.2. Thiết kế xây dựng hệ thống thử nghiệm ........................................................ 85
6.2.1. Thiết kế tổng thể ..............................................................................................85
6.2.2. Chức năng phân lớp văn bản ............................................................................86
6.2.2.1. Hướng tiếp cận học không giám sát .............................................................. 86
6.2.2.2. Hướng tiếp cận theo đề xuất cải tiến công thức ............................................ 88
6.2.3. Chức năng vector hóa văn bản .........................................................................89
6.2.4. Chức năng phân nhóm các lớp văn bản mẫu....................................................91
6.2.5. Chức năng xác định trước độ liên quan của các term trong từ điển với tập
văn bản mẫu ...............................................................................................................93
6.2.6. Chức năng Quản lý tập mẫu .............................................................................94
6.2.7. Chức năng quản lý từ điển/ StopW ords ...........................................................95
6.3. Kết chương ....................................................................................................... 95
phÇn iii cµi ®Æt m« h×nh vµ kiÓm thö kÕt qu¶ ............................................. 96
CHƯƠNG 7 – CÀI ĐẶT MÔ HÌNH VÀ KIỂM THỬ KẾT QUẢ ..................... 97
7.1. Cài đặt chương trình ....................................................................................... 98
7.1.1. Lựa chọn công nghệ và môi trường cài đặt ......................................................98
7.1.2. Giao diện chương trình Demo ..........................................................................98
7.1.2.1. Giao diện hướng tiếp cận học không giám sát trong học có giám sát .......... 98
7.1.2.2. Giao diện hướng tiếp cận theo công thức cải tiến ....................................... 100
7.2. Cơ sở dữ liệu thử nghiệm .............................................................................. 102
7.3. Kết quả thử nghiệm ....................................................................................... 102
7.3.1. Kết quả phân tách các thuật ngữ .................................................................. 103
7.3.1.1. Đánh giá tốc độ phân tách các thuật ngữ .................................................... 103
7.3.1.2. Đánh giá hiệu quả phân tách các thuật ngữ ................................................ 104
7.3.2. Kết quả phân lớp văn bản .............................................................................. 105
7.3.2.1. Kết quả thử nghiệm phân lớp trên tập mẫu VnExpress ............................... 105
7.3.2.2. Kết quả thử nghiệm phân lớp trên tập mẫu VietNamNet............................. 107
§inh ThÞ Ph¬ng Thu -
LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi
11/2004
- Trang 5 7.4. Đánh giá thử nghiệm ..................................................................................... 109
7.5. Kết chương ..................................................................................................... 109
KẾT LUẬN VÀ ĐỊNH HƯỚNG PHÁT TRIỂN ............................................ 110
TÀI LIỆU THAM KHẢO ................................................................................. 112
phÇn phô lôc ................................................................................................... 115
PHỤ LỤC 1 - Tập các từ dừng (Stopwords) tiếng Việt ............................ 116
PHỤ LỤC 2 - Kết quả thử nghiệm phân lớp trên tập dữ liệu VnExpress121
PHỤ LỤC 3 - Hướng dẫn cài đặt và sử dụng chương trình ................... 129
PHỤ LỤC 4 - Mô tả nội dung đĩa CD kèm theo ......................................... 130
§inh ThÞ Ph¬ng Thu -
LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi
11/2004
- Trang 6 -
Danh mục các thuật ngữ và ký hiệu viết tắt trong Luận văn
STT
Từ
Nghĩa
1.
Ca
Một nhóm văn bản
2.
Cluster
Nhóm (nhóm dữ liệu, nhóm văn bản)
3.
concept
khái niệm
4.
d
Một văn bản
5.
D
Tập văn bản
6.
Decision Tree
Cây quyết định
7.
Document vector
Vector văn bản
8.
Feature vector
Vector thuộc tính đặc trưng
9.
FIHC
Hierarchical Frequent Item Based Clustering - Phân
nhóm có phân cấp dựa trên thuật ngữ xuất hiện thường
xuyên
10.
Frequent itemset
Tập thuật ngữ xuất hiện thường xuyên trong văn bản
11.
GFI
Global frequent item - Một thuật ngữ thường xuyên toàn
cục
12.
GFS
Global frequent itemset -Tập thuật ngữ thường xuyên
toàn cục
13.
GS
Global support - Phần trăm tài liệu chứa tập thuật ngữ.
14.
hash-table
bảng băm
15.
HTML
HyperText Markup Language - Ngôn ngữ đánh dấu siêu
văn bản
16.
ICS
inter-cluster similarity - Độ tương tự trong của nhóm
17.
KDD
Knowledge Discovery in Database - Tiến trình khai phá
dữ liệu và phát hiện tri thức
18.
keyword
từ khóa
19.
k-itemset
tập thuật ngữ gồm k phần tử
20.
k-NN
k-Nearest Neighbor - Thuật toán k láng giềng gần nhất
§inh ThÞ Ph¬ng Thu -
LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi
11/2004
- Trang 7 21.
Machine Learning
học máy
22.
membership
hàm thuộc
function μA(x)
23.
postpruning
Tỉa cây sau
24.
precision
Độ chính xác phân lớp
25.
prepruning
Tỉa cây trước
26.
recall
Độ hồi tưởng (trong phân lớp)
27.
Semi-structured
Dạng bán cấu trúc
28.
Sim(Ca←Cb),
Similarity- Độ tương tự giữa hai nhóm văn bản Ca và Cb
29.
Stop word
Từ dừng
30.
supervised learning Học có giám sát
method
31.
term
thuật ngữ
32.
Test set
Tập dữ liệu kiểm thử
33.
Text Catergorization Phân lớp văn bản
34.
Text Classification
Phân lớp văn bản
35.
Text Clustering
Phân nhóm văn bản
36.
Text Mining
Khai phá dữ liệu văn bản
37.
TF × IDF
Phương pháp biểu diễn văn bản dựa trên tần số thuật ngữ
TF và nghịch đảo tần số văn bản IDF
38.
Training set
Tập dữ liệu huấn luyện
39.
unstructured
Dạng phi cấu trúc
40.
unsupervised
Học không giám sát
learning method
41.
VSM
§inh ThÞ Ph¬ng Thu -
Vector Space Model - Mô hình không gian vector
LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi
11/2004
- Trang 8 -
Danh mục các bảng trong Luận văn
Bảng 1.1. Ví dụ về văn bản biểu diễn theo từ khóa và tần số xuất hiện ______________ 25
Bảng 1.2. Ví dụ biểu diễn vector thưa. _______________________________________ 28
Bảng 2.1. Dữ liệu đầu vào để xây dựng cây FP ________________________________ 38
Bảng 3.1. Các mẫu huấn luyện dùng cho cây quyết định class LÚA ________________ 49
Bảng 3.2. Ví dụ 1 về gán nhãn theo số đông ___________________________________ 56
Bảng 3.3. Ví dụ 2 về gán nhãn theo số đông ___________________________________ 57
Bảng 7.1. Thông tin mô tả một số thông số của các tập dữ liệu huấn luyện __________ 102
Bảng 7.2. Kết quả thử nghiệm phân lớp 80 văn bản trên tập mẫu VnExpress ________ 105
Bảng 7.3. Kết quả thử nghiệm phân lớp 35 văn bản trên tập mẫu VietNamNet _______ 107
§inh ThÞ Ph¬ng Thu -
LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi
11/2004
- Trang 9 -
Danh mục các hình vẽ trong Luận văn
Hình 1.1. Tiến trình khai phá dữ liệu và phát hiện tri thức (KDD) __________________ 17
Hình 1.2. Chức năng dẫn đường văn bản trong VNExpress _______________________ 24
Hình 1.3. Ví dụ biểu diễn văn bản dựa trên khái niệm mờ ________________________ 29
Hình 2.1. Ví dụ mô tả giải thuật k-means _____________________________________ 34
Hình 2.2. Mô tả một giải thuật phân nhóm dựa trên lưới _________________________ 35
Hình 2.3. Ví dụ về thuật toán Apriori ________________________________________ 37
Hình 2.4. Ví dụ về xây dựng cây FP _________________________________________ 38
Hình 3.1. Một ví dụ về cây quyết định cho phân lớp LÚA _________________________ 49
Hình 3.2. Ví dụ tìm kiếm lời giải trên cây quyết định phân lớp chủ đề “LÚA” ________ 50
Hình 3.3. Đồ thị phân bố đại lượng Entropy ___________________________________ 52
Hình 3.4. Minh họa việc khoanh vùng k văn bản gần nhất với k = 5 ________________ 55
Hình 3.5. Minh họa cách tính precision và recall _______________________________ 57
Hình 5.1. Mô hình tiếp cận theo phương pháp học không giám sát _________________ 71
Hình 5.2. Thuật toán tách term tiếng Việt _____________________________________ 74
Hình 5.3. Phân nhóm các lớp văn bản mẫu với thuật toán FIHC ___________________ 78
Hình 5.4. Mô hình tiếp cận theo công thức cải tiến đề xuất _______________________ 80
Hình 6.1. Sơ đồ chức năng tổng thể của hệ thống _______________________________ 85
Hình 6.2. Chức năng phân lớp văn bản theo hướng tiếp cận học không giám sát ______ 86
Hình 6.3. Chức năng phân lớp văn bản theo hướng tiếp cận cải tiến công thức _______ 88
Hình 6.4. Mô hình bộ vector hóa văn bản _____________________________________ 90
Hình 6.5. Chức năng phân nhóm các lớp văn bản mẫu __________________________ 91
Hình 6.6. Chức năng xác định độ liên quan của các term trong từ điển với tập mẫu ____ 93
Hình 6.7. Chức năng Quản lý tập văn bản mẫu ________________________________ 94
Hình 6.8. Chức năng quản lý Từ điển/StopWords _______________________________ 95
Hình 7.1. Các giao diện chương trình cài đặt hướng tiếp cận học không giám sát ____ 100
Hình 7.2. Các giao diện chương trình cài đặt hướng tiếp cận theo công thức cải tiến _ 101
Hình 7.3. Tốc độ tách thuật ngữ ___________________________________________ 103
§inh ThÞ Ph¬ng Thu -
LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi
11/2004
- Trang 10 -
MỞ ĐẦU
Sự phát triển vượt bậc của khoa học và công nghệ trong một vài thập kỷ gần
đây đã mang lại cho con người nhiều tri thức hơn. Thông tin, tri thức giờ đây không
chỉ còn được lưu giữ trên giấy tờ nữa mà còn được số hóa và cất giữ như các tài liệu
điện tử. Thế kỷ 20 đánh dấu sự ra đời và phát triển mạnh mẽ của công nghệ thông
tin và công nghệ điện tử cùng với máy tính, mạng máy tính và mạng thông tin toàn
cầu có khả năng chia sẻ thông tin, an toàn, tốc độ trao đổi, khả năng xử lý thông tin
nhanh chóng, chính xác,… Con người không còn đáp ứng được với việc xử lý các
thông tin lưu trữ dạng văn bản điện tử theo các cách thủ công truyền thống. Từ đó
nảy sinh các nhu cầu về xử lý thông tin văn bản tự động.
MỤC ĐÍCH VÀ LÝ DO LỰA CHỌN ĐỀ TÀI
Trên thế giới đã có rất nhiều thành công trong lĩnh vực nghiên cứu xử lý văn
bản như của hãng IBM, trong các phòng thí nghiệm ở MIT [12], hay trong các viện
nghiên cứu của các trường đại học ở Mỹ, Pháp, Nhật bản, Canada,... Tuy nhiên, các
thành công đó chủ yếu tập trung vào vấn đề nghiên cứu văn bản tiếng Anh, tiếng
Pháp, những ngôn ngữ tương đối đơn giản khi xử lý. Trong khi đó, rất ít công cụ đã
được xây dựng thực sự thành công trong lĩnh vực xử lý văn bản tiếng Việt. Do nhu
cầu hội nhập, nhu cầu phát triển về kinh tế, văn hóa, xã hội ngày càng tăng, các
thông tin được lưu trữ qua văn bản điện tử, qua web, qua email phát triển với tốc độ
§inh ThÞ Ph¬ng Thu -
LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi
11/2004
- Trang 11 không ngừng, nhu cầu nghiên cứu và xây dựng các công cụ khai phá văn bản tiếng
Việt đang được hết sức coi trọng.
Luận văn tốt nghiệp này được thực hiện với mục đích nghiên cứu tìm hiểu
các lý thuyết xử lý văn bản đã được nghiên cứu phát triển trong nước và trên thế
giới để từ đó xây dựng giải pháp cho các bài toán xử lý văn bản tiếng Việt. Bài toán
xử lý cụ thể đặt ra trong luận văn này là Bài toán phân lớp văn bản tiếng Việt.
NỘI DUNG VÀ PHẠM VI NGHIÊN CỨU CỦA ĐỀ TÀI
Trong luận văn nghiên cứu về bài toán phân lớp văn bản tiếng Việt, với
mục đích tăng độ chính xác cho kết quả phân lớp văn bản tiếng Việt, dựa trên cơ sở
lý thuyết đã nghiên cứu, tác giả đề xuất hai hướng tiếp cận bài toán và trình bày các
kết quả nghiên cứu thử nghiệm theo cả hai hướng tiếp cận này đã tiến hành trong
khoảng thời gian vừa qua.
• Hướng tiếp cận thứ nhất: xuất phát từ ý tưởng rằng mặc dù kĩ thuật phân nhóm
là một phương pháp học không giám sát và kĩ thuật phân lớp là một phương
pháp học có giám sát nhưng chúng ta vẫn có thể sử dụng cách tiếp cận phân
nhóm để tăng hiệu quả cho bài toán phân lớp văn bản. Với cách tiếp cận này
chúng ta sẽ giảm được kích thước, số chiều trong không gian vector đặc trưng và
mang lại hiệu quả rõ rệt.
• Hướng tiếp cận thứ hai: tác giả đề xuất một sự cải tiến công thức tính độ liên
quan giữa các văn bản trong mô hình vector, công thức này được phát triển dựa
trên những nghiên cứu đã được chứng minh trong [6]. Việc sử dụng công thức
cải tiến này kết hợp với các cấu trúc dữ liệu phù hợp nhằm mục đích tối ưu kiến
trúc cho mô hình thực hiện đã giảm được chi phí thời gian đáng kể trong quá
trình tiến hành phân lớp và cho một kết quả thực nghiệm tương đối tốt.
Trong cả hai hướng tiếp cận tác giả đều sử dụng mô hình không gian vector để biểu
diễn văn bản.
§inh ThÞ Ph¬ng Thu -
LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi
11/2004
- Trang 12 -
BỐ CỤC TRÌNH BÀY CỦA LUẬN VĂN
Bố cục trình bày của luận văn bao gồm 3 phần, 7 chương.
Phần I: Cơ sở lý thuyết
Chương I: Giới thiệu một khung nhìn tổng quan về lĩnh vực xử lý văn bản.
Chương II: Đề cập đến kỹ thuật phân nhóm văn bản là một kỹ thuật học
không giám sát trong xử lý văn bản.
Chương III: Tìm hiểu về phương pháp phân lớp văn bản là một kỹ thuật học
có giám sát trong xử lý văn bản.
Chương IV: Mô tả bài toán nghiên cứu chính của Luận văn: Bài toán phân
lớp trên các văn bản tiếng Việt.
Phần II: Thiết kế hướng tiếp cận
Chương V: Tác giả đề xuất hai hướng tiếp cận và lựa chọn giải pháp cho các
mô hình tiếp cận theo hai hướng đó.
Chương VI: Thiết kế mô hình phần mềm cho chương trình kiểm thử.
Phần III: Cài đặt mô hình và kiểm thử kết quả
Chương VII: Trình bày quá trình tiến hành thực nghiệm và các kết quả thực
nghiệm của cả hai hướng tiếp cận.
Cuối cùng, trong phần kết luận và định hướng phát triển, tác giả nêu ra các
nhận xét về kết quả đạt được và một số định hướng phát triển tiếp theo của đề tài ■.
§inh ThÞ Ph¬ng Thu -
LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi
11/2004
- Trang 13 -
phÇn i
c¬ së lý thuyÕt
Néi dung
*
Nội dung phần I mô tả tổng quan cơ sở lý thuyết liên
quan đến vấn đề nghiên cứu trong luận văn:
Chương I: Tổng quan về xử lý văn bản
Chương II: Phân nhóm – phương pháp học
không giám sát
Chương III: Phân lớp – phương pháp học có
giám sát
Chương IV: Vấn đề nghiên cứu chính của luận
văn – bài toán phân lớp văn bản tiếng Việt.
§inh ThÞ Ph¬ng Thu -
LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi
11/2004
- Trang 14 -
PhÇn
1
C HƯƠNG 1 - TỔNG QUAN VỀ XỬ LÝ VĂN BẢN
Néi dung:
1.1. Khai ph¸ vµ ph¸t hiÖn tri thøc trong d÷ liÖu
1.2. Text Mining – gãc nh×n nhËn quan träng trong Data mining
1.3. C¸c kh¸i niÖm c¬ b¶n trong xö lý v¨n b¶n
1.4. C¸c bµi to¸n c¬ b¶n trong xö lý v¨n b¶n
1.5. C¸c ph¬ng ph¸p biÓu diÔn v¨n b¶n
1.6. KÕt ch¬ng
§inh ThÞ Ph¬ng Thu -
LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi
11/2004
- Trang 15 -
1.1. Khai phá và phát hiện tri thức trong dữ liệu
1.1.1. Dữ liệu, Thông tin và Tri thức
Dữ liệu được hiểu là một chuỗi các bit, các con số hoặc các đối tượng mà
chúng ta thu thập được hàng ngày. Ví dụ: dữ liệu là các file trong máy tính, dữ liệu
là các văn bản giấy tờ mà chúng ta phải xử lý hàng ngày, các tín hiệu,...
Thông tin là dữ liệu đã được loại bỏ đi nhiễu, sự dư thừa và đã được biểu
diễn dưới dạng mà con người có thể nhận thức được. Ví dụ: thông tin về tình hình
giá cổ phiếu, thông tin về nhiệt độ trong tháng,...
Tri thức được hiểu là các thông tin đã được tích hợp lại, đã được nhận thức,
kiểm nghiệm, hay được đúc rút ra thành các quy luật có ý nghĩa đối với con người.
Ví dụ: từ thông tin về nhiệt độ trong tháng, con người có thể đưa ra được những dự
báo thời tiết quan trọng, hoặc từ các thông tin về tình hình giá cổ phiếu, các nhà
kinh doanh có thể phân tích và nắm được diễn biến của thị trường để có các quyết
định đầu tư đúng đắn,...
Tri thức chính là các dữ liệu, thông tin ở mức trừu tượng và khái quát cao
hơn. So với dữ liệu và thông tin thì tri thức ở dạng cô đọng và dễ hiểu nhất đối với
con người. Rõ ràng trong kỷ nguyên công nghệ thông tin này thì con người chỉ
muốn tìm kiếm và lĩnh hội các tri thức, đó là cách nhanh nhất và hợp lý nhất, so với
chi phí thời gian và khả năng để hiểu được các dữ liệu ở một dạng thô sơ nào đó.
Điều đó cũng cho thấy vai trò quan trọng của lớp các bài toán khai phá dữ liệu và
phát hiện tri thức.
1.1.2. Khai phá dữ liệu và phát hiện tri thức
Khai phá dữ liệu, hay Data Mining, được định nghĩa như quá trình phát
hiện các tri thức từ các dữ liệu lớn được lưu trữ trong cơ sở dữ liệu, data warehouse
hay các kho chứa thông tin khác [1, 12, 17].
Thuật ngữ khai phá dữ liệu (data mining) chỉ việc tìm kiếm một tập hợp nhỏ
có giá trị từ một số lượng lớn các dữ liệu thô. Một ví dụ hay được nhắc tới là việc
§inh ThÞ Ph¬ng Thu -
LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi
11/2004
- Trang 16 khai thác vàng từ đá và cát, khai phá dữ liệu được ví như công việc “đãi cát tìm
vàng” trong một tập hợp lớn các dữ liệu cho trước.
Có nhiều thuật ngữ hiện được dùng cũng có nghĩa tương tự với từ data
mining như knowledge mining (khai phá tri thức), knowledge extraction (chắt lọc tri
thức), data/patern analysis (phân tích dữ liệu/mẫu), data archaeology (khảo cổ dữ
liệu), data dredging (nạo vét dữ liệu) [12]. Hiện nay, thuật ngữ khai phá dữ liệu
được dùng quen thuộc và thường đồng nhất với một thuật ngữ khác là phát hiện tri
thức trong cơ sở dữ liệu – Knowledge Discovery in Database (KDD) [1, 2]. Thực
ra, khai phá dữ liệu chỉ là một bước trong các quá trình của KDD.
Tiến trình phát hiện tri thức KDD nói chung bao gồm 7 quá trình cơ bản
sau đây [1, 2, 4, 12, 17]:
1. Làm sạch dữ liệu: Loại bỏ nhiễu và các dữ liệu không cần thiết.
2. Tích hợp dữ liệu: Tích hợp các nguồn dữ liệu khác nhau.
3. Lựa chọn dữ liệu: Chọn lựa các dữ liệu liên quan tới quá trình phân tích.
4. Chuyển đổi dữ liệu: Các dữ liệu được chuyển đổi sang các dạng phù hợp
cho việc xử lý.
5. Khai phá dữ liệu: Là một trong những bước quan trọng nhất, ở đây sử
dụng những phương pháp thông minh để chắt lọc ra những mẫu dữ liệu
có giá trị.
6. Ước lượng mẫu: Quá trình này nhằm đánh giá các kết quả tìm được thông
qua các độ đo nào đó.
7. Biểu diễn tri thức: Sử dụng các kỹ thuật biểu diễn và thể hiện trực quan
các tri thức cho người dùng.
Hình 1.1 mô tả bảy quá trình trên trong tiến trình KDD.
§inh ThÞ Ph¬ng Thu -
LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi
11/2004
- Trang 17 -
Hình 1.1. Tiến trình khai phá dữ liệu và phát hiện tri thức (KDD)
Việc áp dụng tiến trình KDD có thể thực hiện trên nhiểu kiểu, loại dữ liệu
khác nhau với các hình thức tổ chức lưu trữ khác nhau. Hiện nay, có rất nhiều cách
tổ chức dữ liệu khác nhau: cơ sở dữ liệu văn bản, cơ sở dữ liệu quan hệ, cơ sở dữ
liệu hướng đối tượng, cơ sở dữ liệu không gian, cơ sở dữ liệu hướng thời gian,…
Đối với mỗi dạng cơ sở dữ liệu lại có các phương pháp xử lý và mục đích khai phá
dữ liệu khác nhau tùy theo tính chất và đặc thù của dữ liệu.
Các kỹ thuật được sử dụng có thể là các phương pháp truyền thống như
học máy (Machine Learning), nhận dạng (Recognition), thống kê (Statistics),… và
các kỹ thuật được phát triển bởi ngành nghiên cứu trí tuệ nhân tạo như mạng nơ-ron
nhân tạo (Neural Network), thuật toán di truyền (Genetic Algorithm), quy nạp luật
(Rule Reduction),…
§inh ThÞ Ph¬ng Thu -
LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi
11/2004
- Trang 18 -
1.2. Text Mining - Góc nhìn nhận quan trọng trong
Data Mining
Trong các dạng dữ liệu thường xuyên được sử dụng thì văn bản là một trong
những dạng được dùng phổ biến nhất. Văn bản có mặt ở mọi nơi và thường xuyên
bắt gặp hàng ngày. Văn bản có thể là các bài báo, các tài liệu kinh doanh, các thông
tin kinh tế, các bài nghiên cứu khoa học,... Dù việc áp dụng CSDL vào hoạt động
quản lý của các tổ chức là rất phổ biến và đem lại nhiều lợi ích trong lưu trữ cũng
như xử lý, nhưng trên thực tế còn rất nhiều thông tin khác được lưu trữ dưới dạng
văn bản. Do đó, các bài toán xử lý văn bản đã được đặt ra từ khá lâu và cho đến nay
vẫn là một bài toán quan trọng trong khai thác dữ liệu văn bản.
Xử lý văn bản được hiểu đơn giản là các thao tác tác động lên văn bản để
làm cho chúng dễ sử dụng hơn, thông tin trong chúng hữu ích hơn hoặc làm cho
chúng được lưu trữ tốt hơn.
Dữ liệu văn bản thường được chia thành hai loại [1, 9]:
• 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à không có
một cấu trúc định dạng cụ thể nào. Ví dụ: các văn bản lưu dưới dạng tệp tin
TXT,...
• Dạng bán cấu trúc (semi-structured): là các loại 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 thẻ đánh dấu để thể
hiện nội dung chính của văn bản. Ví dụ: dạng tệp tin HTML, e-Mail,…
Tùy từng mục đích sử dụng cụ thể mà việc xử lý văn bản được thực hiện trên dạng
cấu trúc nào. Ví dụ, với bài toán phân lớp nội dung trang web thì dạng văn bản cần
xử lý là HTML. Trong luận văn này, tác giả chỉ quan tâm xử lý các dữ liệu văn bản
ở dạng phi cấu trúc (biểu diễn dưới dạng tệp tin TXT), bài toán được giải quyết
theo hướng dữ liệu mở để tương lai có thể đáp ứng với các mục đích sử dụng khác
nhau.
§inh ThÞ Ph¬ng Thu -
LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi
11/2004
- Xem thêm -