Thạc Sĩ Hệ thống nhận dạng và phân loại văn bản

CHƯƠNG I. MỞ ĐẦU . 8
I.1. Giới thiệu: . 8
I.2. Tổng quan về phân loại văn bản và các nghiên cứu đã thực hiện . 9
I.3. Mục tiêu của luận văn . 10
I.4. Nội dung nghiên cứu 11
I.5. Kết quả đạt được 12
CHƯƠNG II. CƠ SỞ LÝ THUYẾT 14
II.1. Một số định nghĩa trong vấn đề văn bản và ngôn ngữ: . 14
II.1.1. Các cấp độ trong ngôn ngữ: . 14
II.1.2. Các quan hệ trong ngôn ngữ 14
II.2. Phân loại ngôn ngữ . 15
II.2.1. Phân theo cội nguồn . 15
II.2.2. Phân theo loại hình . 15
II.2.3. Phân theo trật tự từ của ngôn ngữ 16
II.3. Các đặc điểm của tiếng Anh 17
II.4. Tóm tắt các phương pháp phân loại văn bản bằng tiếng Anh . 17
II.4.1. Naïve Bayes (NB) . 17
II.4.2. Phương pháp K–Nearest Neighbor (kNN) 19
II.4.3. Support vector Machine (SVM) . 21
II.4.4. Neural Network (NNet) 23
II.4.5. Linear Least Square Fit (LLSF) . 25
II.4.6. Centroid- based vector 26
II.5. Các đặc điểm cơ bản về tiếng Việt 27
II.6. So sánh đối chiếu tiếng Anh-Việt . 28
II.7. Tóm tắt các phương pháp phân loại văn bản bằng tiếng Việt . 28
II.7.1. Phương pháp khớp tối đa Maximum Matching: forward/backward. 28
* Ưu điểm 29
* Hạn chế 30
II.7.2. Phương pháp giải thuật học cải biến (Transformation-based
Learning, TBL) 30
* Nội dung . 30
* Ưu điểm 30
* Hạn chế 31
II.7.3. Mô hình tách từ bằng WFST và mạng Neural . 31
* Nội dung . 31
* Ưu điểm 34
* Hạn chế 35
II.7.4. Phương pháp quy hoạch động (dynamic programming) . 35
* Nội dung . 35
* Ưu điểm 36
* Hạn chế 36
II.8. Mô tả phương pháp sử dụng trong đề cương . 36
II.8.1. Chọn phương án thực hiện luận văn 36
II.8.2. Hạt nhân cho các chuỗi Text . 37
II.8.3. Cơ sở lý thuyết của Support vector Machine (SVM): 43
II.8.4. Huấn luyện SVM . 48
II.8.5. Phân loại văn bản . 49
CHƯƠNG III. MÔ TẢ BÀI TOÁN và XỬ LÝ BÀI TOÁN 50
III.1. Các yêu cầu đối với việc phân loại văn bản . 50
III.2. Cấu trúc chương trình 51
III.2.1. Bước 1: Tiền xử lý số liệu 51
III.2.2. Bước 2: Tách câu: . 52
III.2.3. Bước 3: Tách từ: 52
III.2.4. Bước 4: Gán nhãn từ loại – Đánh trọng số 52
III.2.5. Bước 5: Sử dụng thuật toán để phân loại văn bản cần đọc . 52
III.3. Các bước thực hiện trong chương trình . 52
III.3.1. Tiền xử lý số liệu: . 52
III.3.2. Tách câu 55
III.3.3. Tách từ 57
III.3.4. Gán nhãn – đánh trọng số . 60
III.3.5. Huấn luyện . 64
III.3.6. Phân loại văn bản 66
CHƯƠNG IV. CHƯƠNG TRÌNH THỬ NGHIỆM .69
IV.1.1. Chuẩn bị số liệu . 69
IV.1.2. Mô tả chương trình: . 71
IV.1.1. Cài đặt . 71
IV.1.2. Một số giao diện của chương trình 72
IV.1.3. Cài đặt . 77
IV.1.4. Các lưu ý khi chuẩn bị số liệu 78
IV.1.5. Kết quả thử nghiệm . 86
CHƯƠNG V. KẾT LUẬN .89
CHƯƠNG VI. TÀI LIỆU THAM KHẢO 91
CHƯƠNG VII. PHỤ LỤC .94
VII.1. Cấu trúc CSDL của chương trình 94
VII.2. Kết quả nhận dạng văn bản 94
VII.3. Các đặc trưng của mẫu phân loại văn bản (trích) . 95
CHƯƠNG I. MỞ ĐẦU
I.1.Giới thiệu:
Chúng ta hãy cùng nhau xem xét các trường hợp thường hay xảy
ra trong thực tế sau:
Trong thời đại bùng nổ công nghệ thông tin hiện nay, hệ thống dữ
liệu số hoá trở nên khổng lồ để phục vụ cho việc lưu trữ trao đổi thông
tin, Dữ liệu số hoá này rất đa dạng - nó có thể là các dữ liệu dưới dạng
tập tin văn bản text, tập tin văn bản MS Word, tập tin văn bản PDF, mail,
HTML .v.v. Các tập tin văn bản cũng được lưu trữ trên máy tính cục bộ
hoặc đươc truyền tải trên intenet, cùng với thời gian và/hoặc số lượng
người dùng tăng nhanh thì các tập tin này ngày càng nhiều và đến một
thời điểm nào đó thì số lượng tập tin này sẽ vượt quá tầm kiểm soát, do
đó khi muốn tìm kiếm lại 1 văn bản nào đó việc tìm kiếm sẽ rất khó khăn
và phức tạp, đặc biệt là trong trường hợp người cần tìm kiếm không nhớ
rõ các câu cần tìm chính xác trong văn bản
Các thông tin trên internet có rất nhiều và phong phú gần như đáp
ứng được hầu hết các nhu cầu thông tin của con người khi cần tra cứu
thông tin. Các thông tin này thường xuyên được cập nhật và thay đổi liên
tục, do vậy khi người cần tìm kiếm muốn tìm kiếm thông tin thì lượng
thông tin thỏa mãn nhu cầu tìm kiếm sẽ rất nhiều nhưng chưa đủ để trở
thành tài liệu phục vụ cho người tìm kiếm; do đó khi người sử dụng muốn
sắp xếp các thông tin tìm được theo thể loại (nhóm văn bản) thì thời gian
thực hiện sẽ mất rất nhiều (thời gian) và công sức bỏ ra cũng không phải
nhỏ
Từ các nhu cầu trên mà yêu cầu về một Hệ thống nhận dạng và
phân loại văn bản để đáp ứng yêu cầu phân loại văn bản sau đó mới
thực hiện tìm kiếm được ra đời nhằm đáp ứng yêu cầu thực tế của người
dùng. Đã có rất nhiều công trình nghiên cứu và ứng dụng thực tế dùng
để thực hiện việc phân loại văn bản, tuy nhiên các ứng dụng đó cũng
chưa thể đáp ứng hoàn toàn nhu cầu của người sử dụng, do vậy mà việc
tìm kiếm, nghiên cứu các giải thuật, các phương pháp phân loại văn bản
vẫn được tiếp tục nghiên cứu và hoàn thiện
Với mục tiêu góp phần vào lĩnh vực nghiên cứu và ứng dụng phân
loại văn bản vào cuộc sống, luận văn này sẽ thực hiện các công việc sau:
- Nghiên cứu và tổng hợp một số phương pháp phân loại văn bản
(tiếng Anh và tiếng Việt) đã làm và sau đó đưa ra 1 số nhận xét
đánh giá
- Nghiên cứu và đưa vào ứng dụng trong việc phân loại văn bản
tiếng Việt bằng lý thuyết khá mới hiện nay là lý thuyết phân loại văn
bản bằng hạt nhân chuỗi (string kernels) và phương pháp hỗ trợ
vecto (Support vector Machine - SVM)
- Đưa ra một chương trình máy tính để thử nghiệm và có kết quả
đánh giá về phương pháp phân loại văn bản sử dụng Hạt nhân
chuỗi (string kernels) kết hợp với Máy hỗ trợ vecto (Support vector
Machine - SVM)
I.2. Tổng quan về phân loại văn bản và các nghiên cứu đã thực
hiện
Bài toán nhận dạng và phân loại văn bản là một trong những bài
toán kinh điển trong lĩnh vực xử lý dữ liệu văn bản. Xử lý dữ liệu văn bản
bao gồm:
- Kiểm tra lỗi chính tả (spelling-checker)
- Kiểm tra lỗi văn phạm (grammar checker)
- Từđiển đồng nghĩa (thesaurus)
- Phân tích văn bản (text analyzer)
- Phân loại văn bản (text classification)
- Tóm tắt văn bản (text summarization)
- Tổng hợp tiếng nói (voice synthesis)
- Nhận dạng giọng nói (voice recognization)
- Dịch tự động (automatic translation)
- .
Phân loại văn bản là công việc phân tích nội dung của văn bản và
sau đó ra quyết định văn bản này thuộc nhóm nào trong các nhóm văn
bản đã cho trước. Do đó để công việc phân loại văn bản chính xác cần
phải đáp ứng được các yêu cầu sau:
- Các văn bản trong nhóm đã được phân loại phải có những tiêu
chuẩn chung nào đó
- Các văn bản khi phân tích thì phải “hiểu” được nội dung để xác
định được các tiêu chuẩn trong văn bản
- Việc xác định loại của văn bản khi so sánh với các nhóm văn bản
yêu cầu phải có những định lượng xác định để xác định chính xác
văn bản cần phân tích thuộc nhóm văn bản nào
Do đó rõ ràng việc phân loại văn bản chính là công việc khai phá
dữ liệu văn bản (text data mining). Trong lĩnh vực khai phá dữ liệu, các
phương pháp phân loại văn bản đã dựa trên những phương pháp quyết
định như quyết định Bayes, cây quyết định, láng giềng gần nhất, mạng
nơron, . Những phương pháp này đã cho kết quả chấp nhận được và
được sử dụng trong thực tế, tuy nhiên việc nghiên cứu việc phân loại văn
bản tiếng Việt vẫn chưa được lâu năm và chưa được sâu rộng, nguyên
nhân là do tiếng Việt có những đặc trưng khác với tiếng Anh như từ
không biến đổi hình thái, ý nghĩa ngữ pháp nằm ở ngoài từ, ranh giới từ
không xác định mặc nhiên bằng khoảng trắng .v.v. (xin xem thêm ở phần
II.3. Các đặc điểm cơ bản về tiếng Việt), ở đây có thể kể tên khá nhiều
nghiên cứu về vấn đề này ở phần tham khảo
I.3.Mục tiêu của luận văn
Do phạm vi bài toán khá lớn và thời gian làm đề tài cũng hạn hẹp nên
mục tiêu nghiên cứu của luận văn này sẽ được tập trung ở các điểm sau:
- Nghiên cứu kỹ thuật phân loại văn bản và một số phương pháp phân
loại văn bản, mô tả các yêu cầu chính yếu nhất của từng phương pháp
và rút ra các ưu/khuyết điểm của từng phương pháp, các phương pháp
được nghiên cứu ở đây là các phương pháp được đánh giá tương đối
mới, đã được các đề tài nghiên cứu trong nước ứng dụng
- Nghiên cứu và ứng dụng cách xử lý ngôn ngữ tiếng Việt:
o Phương pháp tách từ ứng dụng trong tiếng Việt (trong luận văn
này sử dụng phương pháp Maximum Matching: forward/backward
nhưng sẽ có một số cải biến để tăng độ chính xác)
o Phương pháp phân tích để định dạng văn bản tiếng Việt (trong
luận văn sử dụng phương pháp phân tích Support vector machine
(SVM) dựa trên lý thuyết về String kernels)
- Xây dựng thử nghiệm phương pháp nhận dạng và phân loại văn bản
tiếng Việt dựa trên các nghiên cứu về tách từ, string kernels và SVM đã
nêu ở trên
- Đưa ra các kết luận và có thể dùng để so sánh với các phương pháp
khác đã được sử dụng, đồng thời cũng sẽ nêu ra phương hướng để giải
quyết các vấn đề còn tồn tại
I.4.Nội dung nghiên cứu
Dựa trên các mục tiêu của luận văn việc nghiên cứu trong luận văn này
sẽ tiến hành bám sát yêu cầu mục tiêu đòi hỏi:
- Nghiên cứu các phương pháp phân tích văn bản mới được đưa ra hoặc
có tính phổ biến được sử dụng nhiều trong thực tế
- Dựa trên các kết quả đã nghiên cứu về phân loại văn bản ở trên thì luận
văn sẽ chọn lựa một phương pháp mới trong việc phân loại văn bản đó
là phương pháp Hạt nhân chuỗi (String Kernels) kết hợp với Máy Hỗ trợ
Vecto (Support vector machine – SVM)
- Luận văn cũng sẽ nghiên cứu các phương pháp phân tích và tách câutừ
trong tiếng Việt, với mỗi phương pháp sẽ đưa ra được các ưu nhược
điểm của từng phương pháp