TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
KHOA CÔNG NGHỆ THÔNG TIN
──────── * ───────
ĐỒ ÁN
TỐT NGHIỆP ĐẠI HỌC
NGÀNH CÔNG NGHỆ THÔNG TIN
XÂY DỰNG THỬ NGHIỆM TẬP MẪU VÀ
PHẦN MỀM PHÂN TỰ ĐỘNG PHÂN LOẠI
VĂN BẢN TIẾNG VIỆT
Sinh viên thực hiện : Trần Quý Giáp
Lớp CNPM
Giáo viên hướng dẫn: TS Huỳnh Quyết Thắng
Hà nội 5-2007
1
2
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
PHIẾU GIAO NHIỆM VỤ ĐỒ ÁN TỐT NGHIỆP
1. Định hướng đề tài tốt nghiệp
Nghiên cứu tập mẫu, công thức phân loại văn bản. Xây dựng thử nghiệm tập
mẫu tiếng việt và xây dựng phần mềm phân loại văn bản theo công thức cải tiến.
2. Các nhiệm vụ cụ thể của ĐATN
 Xây dựng tập mẫu tiếng việt với số lượng lớn về văn bản mẫu và nhiều về
phân lớp văn bản.
 Cài đặt chương trình tự động phân loại văn bản theo công thức cải tiến có tốc
độ xử lý nhanh.
 Đề xuất các giải pháp để tăng độ chính xác của chương trình.
3. Lời cám đoan của sinh viên:
Tôi – Trần Quý Giáp - cam kết ĐATN là công trình nghiên cứu của bản thân tôi
dưới sự hướng dẫn của TS. Huỳnh Quyết Thắng
Các kết quả nêu trong ĐATN là trung thực, không phải là sao chép toàn văn của bất
kỳ công trình nào khác.

Hà Nội, ngày tháng năm
Tác giả ĐATN
Trần Quý Giáp

4. Xác nhận của giáo viên hướng dẫn về mức độ hoàn thành của ĐATN và cho
phép bảo vệ
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
3
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
TÓM TẮT NỘI DUNG ĐỒ ÁN TỐT NGHIỆP
Nội dung đồ án có những phần sau :
 Xây dựng thử nghiệm tập mẫu tiếng việt với số lượng lớn văn bản mẫu và nhiều
phân lớp.
 Nâng cao chất lượng của tập mẫu.
 Xây dựng phần mềm phân loại văn bản tiếng việt dựa trên công thức cải tiến. Yêu
cầu phần mềm là tốc độ xử lý cao để mang lại tính ứng dụng lớn.
 Nghiên cứu tìm ra các giải pháp nâng cao chất lượng của chương trình, các giải
pháp bao gồm các vấn đề về tập mẫu, từ điển và công thức tính.
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
4
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
ABSTRACT OF THESIS
With the rapid gowth of outline information, text categorization has become
one of the key techniques for handling and organizing text data. Text categorization
techniques are used to classify new stories, to find interesting information on the
www, and to guide a user’s search through hypertext…
The objective be of the thesis is the construction vietnamese text collection to
assay be with the number of the texts and many the subclassings. Construct a
automatic vietnamese text categorization software based on an innovation formula
with the high precison and the the quick procesing time. To map out the solution

about text collection, the dictionary and the formula to improve more the precision
of result in procesing.
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
5
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
Lời mở đầu 8
Danh mục hình : 10
2 10
Danh mục bảng : 11
Danh mục từ viết tắt 12
3 Chương 1. Tổng quan về bài toán xử lý văn bản 13
3.1 Khai phá dữ liệu và phát hiện tri thức 13
3.1.1 Dữ liệu, thông tin và tri thức 13
3.1.2 Khai phá dữ liệu và phát hiện tri thức 14
3.2 Các Khái niệm trong xử lý văn bản 15
3.2.1 Từ khoá, Thuật ngữ, và Khái niệm 15
3.2.2 Từ dừng ( Stop word ) 16
3.2.3 Trọng số của thuật ngữ 16
3.2.4 Độ Liên quan giữa các văn bản 17
3.3 Các bài toán cơ bản trong xử lý văn bản 17
3.3.1 Tìm kiếm văn bản (Text Retrieval) 17
3.3.2 Phân lớp văn bản (Text Categorization, Text Classification) 18
3.3.3 Phân nhóm văn bản (Text Clustering) 18
3.3.4 Tóm tắt văn bản (Text Summarization) 18
3.3.5 Dẫn đường văn bản (Text Routing) 19
3.4 Kết chương 19
4 Chương 2. Bài toán phân loại văn bản 20
4.1 Giới thiệu bài toán phân lớp văn bản 20
4.2 Các thuật toán được sử dụng trong bài toán phân lớp văn bản 20
4.2.1 Các phương pháp phân chia (Partitionning Algorithms) 21

4.2.2 Phương pháp phân nhóm dựa trên hàm mật độ (Density-Based) 21
4.2.3 Phương pháp phân nhóm dựa trên lưới (Grid-Based Method) 22
4.2.4 Phân nhóm dựa trên thuật ngữ xuất hiện thường xuyên (Frequen Itemset) 22
4.2.4.1 Phân nhóm dựa trên thuật ngữ xuất hiện thường xuyên ( Frequen Item set)
23
4.2.4.1.1 Giải thuật Apriori 23
4.2.4.1.2 Giải thuật FP Growth 24
4.3 Các phương pháp biểu diễn văn bản 26
4.3.1 Mô hình không gian vector 26
4.3.1.1 Mô hình Boolean 27
4.3.1.2 Mô hình tần số 27
4.3.1.3 Phương pháp xử lý vector thưa 29
4.3.2 Phương pháp biểu diễn văn bản dựa trên khái niệm mờ 30
4.4 Kết chương 31
5 Chương 3. Tổng quan về tập mẫu 33
5.1 Khái niệm về tập mẫu 33
5.2 Đặc điểm của tập mẫu 34
5.2.1 Nguồn gốc 34
5.2.2 Tính đầy đủ 34
5.2.3 Tính hiệu quả 34
5.3 Các tập mẫu xử lý văn bản tiếng anh 35
5.3.1 Tập mẫu Reuter 21578 35
5.3.1.1 Lịch sử phát triển của tập mẫu Reuter 21578 35
5.3.1.2 Quá trình nâng cấp từ Reuter 22173 đến Reuter 21578 36
5.3.1.3 Khuôn dạng dữ liệu tập mẫu Reuters-21578 36
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
6
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
5.3.1.4 Hệ thống phần lớp trong Reuter 21578 41
5.3.1.5 Sử dụng của tập mẫu Reuter 21578 trong phân lớp văn bản 42

5.3.1.6 Tổng kết về Reuter 21578 44
5.3.2 Tập mẫu RCV1 44
5.3.2.1 Tổng quan về tập mẫu RCV1 và RCV2 44
5.3.2.2 Mã hoá dữ liệu tập mẫu RCV1 44
5.3.2.3 Quá trình xây dựng RCV1 45
5.3.2.4 Cấu trúc của tập mẫu RCV1 47
5.3.2.5 Kết luận về RCV1 50
5.4 Kết chương 50
6 Chương 4. Bài toán phân loại văn bản tiếng việt và giải pháp 51
6.1 Tổng quan về xử lý ngôn ngữ tự nhiên 51
6.2 Đặc điểm chung của ngôn ngữ tiếng việt 51
6.2.1 Tính âm tiết 52
6.2.2 Từ trong tiếng việt 52
6.2.3 Ngũ pháp tiếng việt 54
6.2.3.1 Phó từ 55
6.2.3.2 Giới từ 55
6.2.3.3 Liên từ 56
6.2.4 Font được sử dụng trong tiếng việt 56
6.3 Bài toán phân lớp văn bản tiếng việt 57
6.4 Giải thuật phân loại văn bản – công thức cải tiến 57
6.4.1 Mô hình tiếp cận bài toán 57
6.4.1.1 Từ điển 58
6.4.1.2 Tách term và loại bỏ Stopword 59
6.4.1.3 Biểu diễn văn bản 60
6.4.1.4 Các công thức tính toán sử dụng trong thuật giải 61
6.4.1.5 Công thức cải tiến 63
6.4.1.6 Sử dụng thuật toán KNN để xác định thể loại của văn bản 64
6.5 Kết chương 67
7 Chương 5. Tập mẫu tiếng việt và giải pháp 68
7.1 Ý tưởng từ tập mẫu tiếng việt 68

7.2 Những vấn đề về tập mẫu tiếng việt 68
7.3 Quá trình xây dựng tập mẫu tiếng việt 69
7.4 Quá trình nâng cao độ chính xác của tập mẫu tiếng việt 70
7.5 Định dạng của tập mẫu : 70
7.6 Kết chương 74
8 Chương 6. Xây dựng hệ thống thử nghiệm và kết quả 75
8.1 Xác định yêu cầu của đồ án 75
8.2 Phân tích và thiết kế hệ thống 75
8.2.1 Chức năng phân loại văn bản 76
8.2.2 Chức năng quản lý hệ thống 79
8.2.2.1 Quản lý tập mẫu : 79
8.2.2.2 Chức năng quản lý tập mẫu : 80
8.2.3 Chức năng cập nhật hệ thống 81
8.2.3.1 Cập nhật tập mẫu : 81
8.2.3.2 Chức năng cập nhật từ điển : 82
8.3 Thử nghiệm và đánh giá 82
8.4 Đánh giá hiệu suất phân lớp văn bản 88
Kết Luận 91
Tài liệu tham khảo: 94
Phần phụ lục : Một số từ điển cập nhật thêm 95
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
7
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
1
Lời mở đầu
Trên thế giới bài toán phân lớp văn bản- text categorization đã xuất hiện khá
lâu, và đã được tiến hành trên rất nhiều ngôn ngữ khác nhau. Ở Việt Nam những
năm gần đây, với sự quan trọng và sự phát tiển rất mạnh của Internet, thông tin
được lưu trữ dưới dạng văn bản ngày càng nhiều, thực tế này yêu cầu chúng ta
phải có một phương tiện để xử lý tự động các văn bản, phân loại và sắp xếp

quản lý chúng. Chương trình phân loại văn bản là chương trình đáp ứng được
yêu cầu đó. Thông qua phân loại văn bản chúng ta có thể phân loại, xắp xếp
chúng phù hợp với chủ đề tương ứng với độ chính xác cao. Phân loại văn bản
được ứng dụng trong rất nhiều lĩnh vực, đặc biệt trong lĩnh vực báo điện tử, hay
ở những cơ quan lưu trữ tài liệu…
Đã có nhiều nghiên cứu và các đề tài khoa học về vấn đề này, và chúng ta đã
đạt tới nhiều thành công. Nhưng dù vậy chúng ta vẫn chưa có một tập mẫu tiếng
việt chuẩn của chúng ta để kiểm nghiệm độ chính xác của các phần mềm phân
loại tiếng việt.
Trong đồ án này em đã tạo ra một tập mẫu tiếng việt thử nghiệm và được sử
dụng ngay trong chương trình phân loại phân bản tự đông, thực nghiệm cho thấy
nó cho kết quả tốt. Tuy nhiên vì kiến thức còn hạn chế và thời gian có hạn nên
chắc hẳn chương trình và tập mẫu của em còn nhiều sai sót, kính mong các thầy
cô góp ý để em có thể hoàn thiện đồ án của mình.
Và cuối cùng em xin chân thành gửi lời cảm ơn thầy Huỳnh Quyết Thắng đã
tận tình hướng dẫn làm đề tài và chị Đinh Thị Phương Thu đã cung cấp cho em
nhiều kiến thức và kinh nghiệm để em có thể hoàn thành đồ án của mình.
Hà nội, ngày 22 tháng 5 năm 2007

Sinh viên
Trần Quý Giáp
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
8
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
Lời cảm ơn !
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
9
Trước hết, em xin được chân thành gửi lời cảm ơn sâu sắc tới các
thầy cô giáo trong trường Đại học Bách Khoa Hà Nội nói chung và các
thầy cô trong khoa Công nghệ Thông tin, bộ môn Công nghệ phần mềm

nói riêng đã tận tình giảng dạy, truyền đạt cho em những kiến thức và
những kinh nghiệm quý báu trong suốt 5 năm học tập và rèn luyện tại
trường Đại học Bách Khoa Hà Nội.
Em xin được gửi lời cảm ơn đến Ts Huỳnh Quyết Thắng - Giảng viên
bộ môn Công nghệ phần mềm, khoa Công nghệ Thông tin, trường Đại học
Bách Khoa Hà Nội đã hết lòng giúp đỡ, hướng dẫn và chỉ dạy tận tình
trong quá trình em làm đồ án tốt nghiệp.
Cuối cùng, em xin được gửi lời cảm ơn chân thành tới gia đình, bạn
bè đã quan tâm, động viên, đóng góp ý kiến và giúp đỡ trong quá trình
học tập, nghiên cứu và hoàn thành đồ án tốt nghiệp.
Hà Nội, ngày 22 tháng 05 năm 2007
Trần Quý Giáp
Lớp CNPM – K47
Khoa CNTT – ĐH Bách Khoa HN
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
Danh mục hình :
2
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
10
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
Danh mục bảng :
Bảng 2.1. Ví dụ về tần số xuất hiện của từ khoá 27
Bảng 2.2.Ví dụ biểu diễn vector thưa 30
Bảng 3.3. Hệ thống phân lớp trong Reuter 21578 41
Bảng 4.4 Ví dụ 1 về độ tương tự 66
Bảng 4.5 Ví dụ 2 về độ tương tự 66
Bảng 6.6. Kết quả phân lớp của các văn bản 88
Bảng 6.7 Kết quả tính precision và recall 90

Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang

11
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.

Danh mục từ viết tắt
STT Từ Giải nghĩa
01 KNN K_Nearest Neighbor_ thuật toán k lớp văn bản láng giềng gần nhất
02 NNTN Ngôn ngữ tự nhiên
03 SGML Standard Generalized Markup Language
04 IRL
Information Retrieval Laboratory- thư viện lưu trữ thông tin
05 RCV
Reuters Corpus Volume – tập mẫu RCV
06 IDF
Inverse Document Frequency _ nghịch đảo tần suất văn bản.
07 IF Item Frequency- tần suất từ khoá
08 STING
Statistical Information Grid
09 W Weigh – trọng số
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
12
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
3 Chương 1. Tổng quan về bài toán xử lý văn bản
3.1 Khai phá dữ liệu và phát hiện tri thức
3.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 chiến
sự tại Iraq, 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 chiến sự tại Iraq, các nhà
quân sự có thể phân tích và nắm được động thái về quân sự cũng như chính trị của
các bên có liên quan.
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, chứ không
thể có đủ 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.
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
13
Nội Dung :
1. Khai phá dữ liệu, phát hiện tri thức trong dữ liệu văn bản
2. Các Khái niệm trong xử lý văn bản.
3. Các bài toán cở bản trong xử lý văn bản.
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
3.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.
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
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)
.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
Descovery in Database (KDD). 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 khai phá dữ liệu và phát hiện tri thức (KDD) nói chung bao gồm
7 quá trình cơ bản sau đây:
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.
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.
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
14
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
Hình 1.1. Tiến trình khai phá dữ liệu và phát hiện tri thức
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ý khác nhau 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), phân lớp

(Classification),… 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), cây quyết định (Decision Tree),…
3.2 Các Khái niệm trong xử lý văn bản
Để hiểu rõ hơn về tư tưởng cũng như thuật toán được sử dụng trong bài toán
phân loại văn bản tiếng việt, chúng ta sẽ tìm hiểu trước một số khái niệm được sử
dụng trong luận văn : từ khóa (keyword), thuật ngữ (term), khái niệm (concept),
trọng số thuật ngữ, độ liên quan, từ dừng
3.2.1 Từ khoá, Thuật ngữ, và Khái niệm.
 Từ khoá ( Term ) : Là các từ xuất hiện trong văn bản ở dạng nguyên thể và có
mặt trong từ điển. Chúng ta sẽ xét một đoạn văn bản sau : “Từ cuối thế kỷ hai
mươi, công nghệ thông tin và truyền thông đã phát triển nhanh chóng, mạnh
mẽ, xuất hiện thêm rất nhiều phương tiện truyền thông mới.”, các term có thể
tách ra như sau : “thế kỷ”,” hai mươi”,” công nghệ”,” thông tin”, “truyền
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
15
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
thông”,” phát triển”,” mạnh mẽ”,” xuất hiện”, “phương tiện”,” truyền
thông”.
 Thuật ngữ : là các từ khoá liên quan đến một lĩnh vực nào đó. Ta sẽ có các
thuật ngữ trong tin học chẳng hạn :”công nghệ phần mềm”, “công nghệ thông
tin”, “vi xử lý” … Trong lĩnh vực luật có các thuật ngữ như : “quyền sử dụng
đất”, “quyền trẻ em”…
 Khái niệm : là các thuật ngữ nhưng nó là sự khái quát hóa, tổng quát hóa của
nhiều thuật ngữ khác. Ví dụ khái niệm “máy tính” có thể chứa đựng các thuật
ngữ khác như “bàn phím”, “chuột”, “phần cứng”, “phần mềm”, “CPU”, “ổ
cứng”, “Internet”, “màn hình”, “số hóa”,… các từ này có một phần liên quan
đến khái niệm “máy tính”.
Một khái niệm thường liên quan đến một dãy các thuật ngữ với mức độ khác
nhau. Ví dụ thuật ngữ “phần mềm” có mức độ liên quan đến khái niệm “tin học”

nhiều hơn so với thuật ngữ “số hóa”. Một tiêu chuẩn để xem xét mức độ liên quan
là xác xuất đồng xuất hiện của cặp khái niệm – thuật ngữ trong các văn bản. Khi
thuật ngữ “máy tính” xuất hiện nhiều trong các văn bản chứa thuật ngữ “tin học”
thì có nghĩa là độ liên quan (hay độ phụ thuộc) giữa cặp “tin học”-“máy tính” càng
cao. Một lý do để giải thích suy luận này là mức độ thay thế.
3.2.2 Từ dừng ( Stop word )
Có thể quan sát thấy rằng trong các ngôn ngữ tự nhiên, rất nhiều từ được dùng
để biểu diễn cấu trúc câu nhưng hầu như không mang ý nghĩa về mặt nội dung,
chẳng hạn các loại từ: giới từ, liên từ,… Các loại từ này xuất hiện thường xuyên
trong các văn bản nhưng không hề mang bất cứ một thông tin nào về nội dung hay
chủ đề của văn bản. Việc loại bỏ các từ như vậy cũng đồng nghĩa với việc giảm số
chiều của văn bản, những từ đó được gọi là từ dừng (stop words).
Từ dừng (Stop Words): là các từ mang ít ý nghĩa trong xử lý văn bản vì nó
xuất hiện trong hầu hết các văn bản. Ví dụ: “Có thể”, “nếu”, “vì vậy”, “sau khi”,
“thì”, “một số”, “với lại”, “quả thật”, “hầu như”
Có một số phương pháp để xác định các từ dừng.
Xây dựng một thuật toán phát hiện các từ dừng. Trong thuật toán này cần đưa
ra một ngưỡng để phát hiện từ dừng, ví dụ nếu phát hiện thấy một từ xuất hiện trong
quá 50% số văn bản thì có thể coi đó là từ dừng.
Sử dụng so sánh với một từ điển từ dừng. Từ điển từ dùng là một từ điển đã
được nghiên cứu và xây dựng sẵn từ trước.
3.2.3 Trọng số của thuật ngữ
Trọng số của thuật ngữ là độ quan trọng hay hàm lượng thông tin mà thuật
ngữ đó mang lại cho văn bản. Nó là đại lượng dùng để đo sự khác biệt giữa văn bản
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
16
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
chứa nó với các văn bản khác. Đại lượng này thường được xác định bằng tay hoặc
đánh giá bằng số lần xuất hiện của thuật ngữ trong văn bản và số lần xuất hiện của
thuật ngữ đó trong các văn bản khác. Khi số lần xuất hiện của thuật ngữ trong văn

bản càng nhiều thì thông tin mà nó mang lại càng lớn. Khi số lần xuất hiện của nó
trong các văn bản khác càng nhiều thì thông tin mà nó mang lại càng ít.
Như vậy một cách tổng quát ta có thể dễ dàng nhận thấy rằng trọng số của các
thuật ngữ như “công nghệ thông tin”, “hệ điều hành” trong lĩnh vực vi tính và các
khái niệm “thị trường tự do”, “thị trường”
trong lĩnh vực kinh doanh chứng khoán sẽ có trọng số lớn vì nó không xuất
hiện nhiều trong toàn bộ các văn bản mà chỉ xuất hiện trong một số các văn bản
thuộc thể loại tương ứng là vi tính và kinh doanh chứng khoán. Ngược lại những từ
mà có trọng số nhỏ và không đáng kể ( sau này sẽ bị loại trong giải thuật tìm term
của văn bản ) chính là các StopWord như : “ấy vậy mà”,”ấy mà”, “bất chấp”…vì nó
xuất hiện ở hầu như tất cả các văn bản.
3.2.4 Độ Liên quan giữa các văn bản
Độ liên quan giữa hai văn bản là một đại lượng đo mức độ giống nhau về mặt
nội dung giữa hai văn bản đó. Các phương pháp đánh giá độ liên quan được chia
thành 2 loại: đánh giá theo tần suất xuất hiện thuật ngữ và đánh giá theo ngữ nghĩa.
• Cách đánh giá độ liên quan theo tần suất xuất hiện thuật ngữ: không quan
tâm đến thứ tự sắp xếp của các thuật ngữ trong văn bản mà chỉ quan tâm đến
số lần nó xuất hiện trong văn bản đó. Ví dụ: phương pháp sử dụng hệ số
Dice, hệ số Jaccard, hệ số consine,
• Cách đánh giá theo ngữ nghĩa : không chỉ chú ý đến số lần xuất hiện thuật
ngữ trong văn bản mà còn chú ý cả đến sự kết cấu giữa các từ trong từng
câu văn. Phương pháp đánh giá thuộc loại này thường phức tạp hơn, yêu cầu
có các giải thuật phù hợp với từng ngôn ngữ cụ thể.
Trong luận văn này thì chúng ta quan tâm đến phương pháp đánh giá độ liên
quan theo tần suất.
3.3 Các bài toán cơ bản trong xử lý văn bản
Một số bài toán cơ bản trong xử lý văn bản, bao gồm: bài toán tìm kiếm văn
bản (Text Retrieval), bài toán phân lớp văn bản (Text Catergorization), bài toán
phân nhóm văn bản (Text Clustering), bài toán định tuyến văn bản (Text Routing),
bài toán tóm tắt văn bản (Text Summarization)

3.3.1 Tìm kiếm văn bản (Text Retrieval)
Tìm kiếm văn bản (Text Retrieval) là quá trình tìm các văn bản trong một kho
lưu trữ theo các yêu cầu của người dùng. Ở đây, các yêu cầu là các truy vấn và
thường được biểu diễn dưới dạng thuật ngữ hay biểu thức logic giữa các thuật ngữ.
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
17
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
Ví dụ: truy vấn “Text Mining” AND (“Categorization” OR “Classification”).
Ứng với truy vấn này search engine của hệ thống sẽ tìm tất cả các tài liệu về “Text
Mining” có liên quan đến “Categorization” hoặc “Classification”. Trên thực tế thì
hầu hết các hệ thống chỉ được thiết kế để hiểu các truy vấn tương tự như “Text
Mining” OR “Categorization” OR “Classification”. Với câu truy vấn này hệ thống
sẽ tìm kiếm các tài liệu theo mức phù hợp với cả ba thuật ngữ “Text Mining”,
“Categorization”, và “Classification”.
Kết quả đầu ra của một phép truy vấn là danh sách các tài liệu được sắp xếp
giảm dần theo mức độ phù hợp với câu truy vấn đầu vào.
3.3.2 Phân lớp văn bản (Text Categorization, Text Classification)
Phân lớp văn bản được định nghĩa như quá trình gán các văn bản vào một hay
nhiều lớp văn bản đã được xác định trước dựa trên nội dung của văn bản đó.
Người ta có thể phân lớp các văn bản một cách thủ công, tức là đọc từng văn
bản và gán nó vào một lớp nào đó, cách này sẽ tốn rất nhiều thời gian và công sức
khi số lượng văn bản lớn nên không khả thi. Do vậy cần phải có các phương pháp
phân lớp tự động. Để phân lớp tự động người ta sử dụng các phương pháp học máy
trong trí tuệ nhân tạo. Khi phân lớp, văn bản được gán vào một lớp theo một giá trị
ngưỡng nào đó. Ngưỡng đặt ra tùy thuộc vào thuật toán và yêu cầu người dùng.
3.3.3 Phân nhóm văn bản (Text Clustering)
Phân nhóm văn bản là việc tự động sinh ra các lớp văn bản dựa vào sự tương tự về
nội dung của các văn bản. Số lượng các nhóm văn bản ở đây là chưa biết trước, chẳng hạn
số nhóm có thể là 2,3 5, Người dùng có thể chỉ ra số lượng các nhóm cần phân nhóm
hoặc hệ thống sẽ tự phân nhóm.

Đối với bài toán này, không bao giờ có một kết quả thỏa mãn hoàn toàn theo ý
người dùng. Một lý do đơn giản để giải thích là máy không được học trước. Chúng
ta phải thừa nhận rằng ngay cả con người cũng giải quyết bài toán này không giống
nhau. Ví dụ, lập nhóm các từ “cầu thủ”, “cha cố”, “nến”, “trái bóng”; một người
sẽ lập thành 2 nhóm là: con người (“cầu thủ” , “cha cố”) và sự vật (“nến”, “trái
bóng”), trong khi đó người khác lại phân chúng thành 2 nhóm khác: nhà thờ (“cha
cố”, “nến”) và bóng đá (“cầu thủ”, “trái bóng”). Do đó, việc đòi hỏi hệ thống tự
động lập nhóm làm việc đúng tuyệt đối là điều không tưởng.
3.3.4 Tóm tắt văn bản (Text Summarization)
Tóm tắt văn bản là bài toán tìm ra thể hiện nội dung của một văn bản thông qua
một vài đoạn văn.
Ứng dụng điển hình của bài toán này là trong tìm kiếm văn bản. Các kho lưu
trữ bao gồm rất nhiều tài liệu và kích thước mỗi tài liệu có thể lên đến vài trăm
trang. Giả sử khi bạn đọc muốn tìm một tài liệu về “Text Mining” và nhờ hệ thống
tìm kiếm văn bản tìm giúp, hệ thống tìm kiếm sẽ đưa ra một danh sách các tài liệu
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
18
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
với nội dung tương đối phù hợp với “Text Mining”. Nhưng để biết thực sự tài liệu đó
có phù hợp với mình hay không, bạn đọc đành phải đọc toàn bộ hoặc đọc một phần
trong tài liệu. Hệ thống tóm tắt văn bản sẽ làm cho việc tìm kiếm giảm nhẹ đi rất
nhiều bằng cách tự động tóm lược nội dung của toàn bộ văn bản bởi một vài đoạn
văn bản. Sau khi đọc qua đoạn tóm lược này, bạn đọc có thể biết được đây có phải
là tài liệu chứa thông tin mà họ đang cần hay không.
Bài toàn tóm tắt văn bản có thể được sử dụng trong bài toán phân loại văn bản
( text categorization ) khi mà văn bản cần phân loại liên quan một lúc đến nhiều thể
loại với tỉ lệ độ liên quan là tương đối gần giống nhau. Khi ấy để biết được văn bản
đó thuộc thể loại nào với độ chính xác cao nhất thì chúng ta dựa vào nội dung chính
của văn bản đó.
3.3.5 Dẫn đường văn bản (Text Routing)

Dẫn đường văn bản là sự tổ hợp giữa bài toán tìm kiếm văn bản và phân lớp,
nhóm văn bản. Giống như phân lớp, nhóm văn bản, bài toán dẫn đường cũng đưa
các văn bản về các lớp, nhóm khác nhau và việc xử lý này yêu cầu trong thời gian
thực. Tuy nhiên, nó cũng giống như bài toán tìm kiếm, mỗi lớp, nhóm văn bản được
gán với các thông tin cần thiết của một hay nhiều nhóm người dùng. Mỗi người
dùng có thể thay đổi thêm bớt các yêu cầu của mình. Quá trình phản hồi có thể
được sử dụng để nâng cao chất lượng tìm kiếm văn bản.
Một ứng dụng điểu hình của bài toán dẫn đường văn bản là trong các trang tin
điện tử. Khi đọc một tin mới, hệ thống sẽ tìm cách đưa ra danh sách các tin khác có
liên quan đến đoạn tin đang đọc. Ứng dụng của bài toán này được sử dụng hết sức
rộng rãi trên báo điện tử. Khi đọc một bài báo, phía dưới mỗi trang web sẽ có các
liên kết đến các bài báo khác có liên quan về mặt nội dung Bạn đọc có thể theo các
thông tin dẫn đường này để theo dõi toàn bộ diễn biến của sự kiện
3.4 Kết chương
Trong chương này chúng ta đã tìm hiểu về các bài toán xử lý văn bản và các
khái niệm trong bài toán phân loại văn bản. Những khái niệm trong bài toán phân
loại văn bản là những khái niệm thường xuyên sử dụng giúp chúng ta hiểu rõ hơn
về chương trình đồ án sẽ được tác giả trình bày ở các chương sau.
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
19
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.

4 Chương 2. Bài toán phân loại văn bản.
4.1 Giới thiệu bài toán phân lớp văn bản
Bài toán phân lớp văn bản là việc gán các chủ đề có trước cho các văn bản dựa
trên nội dung của chúng. Người ta có thể phân lớp văn bản một cách thủ công, hoặc
sử dụng các phương pháp phân lớp tự động.
Để phân lớp được văn bản tự động thường sử dụng các kỹ thuật học máy có
giám sát (supervised learning). Trong kỹ thuật này, dữ liệu được chia ra thành
hai phần: tập huấn luyện hay tập mẫu (training set) và tập kiểm thử (test set).

Đầu tiên hệ thống sẽ được huấn luyện(học) thông qua tập mẫu, sau đó đánh giá
hiệu quả của hệ thống thông qua các dữ liệu kiểm thử.
Các hệ thống phân loại văn bản như vậy có thể ứng dụng trong việc phân loại tài
liệu của các thư viện điện tử, phân loại bài viết trên các trang tin điện tử, hay phân
loại giấy tờ công văn trong các công sở Một hệ thống phân loại văn bản tốt không
những có thể thay thế hoàn toàn con người trong lĩnh vực này mà thậm chí còn cho
ra các kết quả tốt hơn rất nhiều so với con người.
4.2 Các thuật toán được sử dụng trong bài toán phân lớp văn
bản
Các thuật toán Phân nhóm dữ liệu cơ bản hiện nay:
• Các giải thuật dựa trên tập thuật ngữ xuất hiện thường xuyên (Document
Clustering Using Frequent Itemsets)
• Các giải thuật phân vùng (Partitionning Algorithms)
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
20
Nội dung :
2.1.Giới thiệu bài toán phân lớp văn bản.
2.2.Các thuật toán được sử dụng trong bài toán phân lớp văn bản.
2.3.Các phương pháp biểu diễn văn bản.
2.3.Khái niệm tập mẫu
2.4.Các tập mẫu xử lý văn bản tiếng Anh
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
• Các giải thuật dựa trên mật độ (Densit-based Algorithms)
• Các giải thuật dựa trên các lưới dữ liệu (Grid-based Algorithms)
• Các giải thuật dựa trên mô hình dữ liệu (Model-based Algorithms),
Phần dưới đây sẽ cung cấp một cái nhìn tổng quan về các giải thuật phân nhóm này
và tập trung đi sâu vào một giải thuật chính sẽ được sử dụng trong luận văn
4.2.1 Các phương pháp phân chia (Partitionning Algorithms)
Các phương pháp phân chia thực hiện chia một tập dữ liệu thành các nhóm
riêng rẽ. Ví dụ: để phân một tập các đối tượng dữ liệu thành k nhóm, thuật toán tiến

hành chia chúng ngay từ đầu thành k nhóm. Sau đó, liên tục cải tiến, xác định lại
các nhóm bằng cách di chuyển các đối tượng dữ liệu ở nhóm này sang nhóm khác
cho đến khi thỏa mãn một số điều kiện.
Thuật toán k-means do J.MacQueen đưa ra vào năm 1967 và các biến thể của
nó (k-means chia đôi -bisecting K-Means, ) được biết đến như là các thuật toán
phân chia nổi tiếng. Chúng thường khác nhau trong việc xác định k trọng tâm ban
đầu, tính toán độ tương tự và phương pháp tính toán trọng tâm để giảm thời gian
tính toán.

Hình 2.2. Ví dụ mô tả giải thuật k-means
4.2.2 Phương pháp phân nhóm dựa trên hàm mật độ (Density-Based)
Phương pháp phân nhóm dựa trên mật độ là các phương pháp dựa trên một
ý tưởng: các nhóm ban đầu là các vùng dầy đặc trong không gian dữ liệu sẽ được
tách ra bằng các vùng có mật độ đối tượng thấp hơn. Tiếp tục phát triển đối với các
nhóm mới tách ra cho đến khi mật độ vùng lân cận vượt qua giá trị ngưỡng. Nói
cách khác, với mỗi điểm bất kì trong một nhóm, mật độ điểm địa phương xung
quanh điểm đó phải không vượt quá ngưỡng. Một nhóm sẽ được xác định dựa trên
3 tiêu chí: mật độ (density), các kết nối với những điểm khác (connectivity) và
đường biên (boundary).
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
21
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
Có hai cách tiếp cận đối với các phương pháp phân nhóm dựa trên mật độ :
• Density-Based Connectivity: bao gồm các giải thuật được biết đến như
DBSCAN, GDBSCAN, OPTICS, và DBCLASD. Hướng tiếp cận này dựa
trên giá trị mật độ và các kết nối giữa các điểm dữ liệu.
• Density Functions: ví dụ giải thuật DENCLUE, tiếp cận theo hàm mật độ.
4.2.3 Phương pháp phân nhóm dựa trên lưới (Grid-Based Method)
Các phương pháp phân nhóm dựa trên lưới thực hiện lượng tử hóa không
gian thành số lượng hữu hạn các ô (cell) để tạo thành cấu trúc lưới. Sau đó tất cả

các thao tác phân nhóm được thực hiện trên cấu trúc lưới. Độ phức tạp tính toán
không phụ thuộc vào số các đối tượng dữ liệu mà chỉ phụ thuộc vào số các cell
trong mỗi chiều trong không gian đã được lượng tử hoá.

Hình 2.3. Mô tả một giải thuật phân nhóm dựa trên lưới
rong số các giải thuật phân nhóm dựa trên lưới thì STING(Statistical
Information Grid) là một phương pháp phân nhóm dựa trên lưới nổi tiếng dùng cho
dữ liệu không gian. Ta không đi sâu vào chi tiết của giải thuật này trong luận văn.
4.2.4 Phân nhóm dựa trên thuật ngữ xuất hiện thường xuyên
(Frequen Itemset)
Phương pháp sử dụng thuật ngữ thường xuyên để phân nhóm được coi là
phương pháp mang lại kết quả tốt hơn cả trong tất cả các giải thuật phân nhóm văn
bản, chính vì vậỵ đây là phương pháp mà được sử dụng trong chương trình. Phương
pháp này nó khắc phục được những nhược điểm mà một số giải thuật phân nhóm
khác gặp phải như:
• Không thực sự giải quyết được vấn đề số chiều quá lớn trong bài toán phân
nhóm. Không đáp ứng được khi số chiều 10000 thuật ngữ/ số chiều.
• Bất lợi khi kích thước của cơ sở dữ liệu quá lớn
Những đặc điểm trên phù hợp với đặc điểm và yêu cầu của bài toán phân loại văn
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
22
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
bản tiếng việt ( với số lượng văn bản tập mẫu đầu vào nhiều và số lượng từ điển lớn
mà hiện nay chúng ta đang có ).
Quá trình phân nhớm dựa trên thuật ngữ xuất hiện thường xuyên bao gồm hai
bước cơ bản:
• Xác định tập các thuật ngữ xuất hiện thường xuyên
• Sử dụng một giải thuật phân nhóm dựa trên tập thuật ngữ thường xuyên đã
xác định
4.2.4.1 Phân nhóm dựa trên thuật ngữ xuất hiện thường xuyên ( Frequen

Item set)
Có nhiều giải thuật xác định tập các thuật ngữ xuất hiện thường xuyên nổi tiếng
như:
 Thuật toán AIS
 Thuật toán STM
 Thuật toán Apriori, AprioriTid
 Thuật toán FP Growth
Chúng ta sẽ x xét hai thuật toán hay được sử dụng Apriori và FP Growth
4.2.4.1.1Giải thuật Apriori
Thuật toán này sử dụng các k-itemset (tập thuật ngữ gồm k item) để thăm dò
(k+1)-itemset và qua đó khai thác được toàn bộ các tập thuật ngữ thường xuyên
(FIs) trong tập dữ liệu.
 Đầu tiên tính 1-itemsets, 2-itemsets và sau đó là 3-itemsets…
 Khi tính toán (k+1)-itemsets, chỉ xét những (k+1)-itemsets mà tất cả các tập con
có độ dài k đã được xác định là thường xuyên ở bước trước.
Mô tả giải thuật Apriori:
Biến C
k
: Các tập thuật ngữ ứng cử có kích thước k.
Biến L
k
: Các tập thuật ngữ thường xuyên kích thước k.
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
23
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
L
1
= {Các thuật ngữ thường xuyên mức 1};
For (k=1; L
k

!=Ø; k++) do
begin
//Bước kết hợp: Kết hợp L
k
với bản thân nó để tạo ra
C
k+1

//Bước cắt tỉa: Loại bỏ (k+1)-itemsets từ C
k+1
chứa
k-itemsets không thường xuyên
C
k+1
= các ứng cử viên được tạo ra từ L
k
For mỗi tài liệu t trong cơ sở dữ liệu do
Tăng số lượng của tất cả các ứng cử viên trong
C
k+1
có chứa trong t
L
k+1
= các ứng cử viên trong C
k+1
có GS > min_support
end
Return

k

L
k
Ví dụ:
Hình 2.4. Ví dụ về thuật toán Apriori
Phương pháp tạo và kiểm tra của giải thuật Apriori làm việc tốt. Tuy nhiên, một
số lượng lớn itemset được tạo ra. Nếu có m tập 1-FIs (m tập 1-item frequent) thì có
đến m*(m-1)/2 tập 2-FIs được tạo ra. Ngoài ra, thuật toán đòi hỏi quét nhiều lần
toàn bộ dữ liệu để kiểm tra thuật ngữ thường xuyên, nó đòi hỏi (n+1) lần quét với n
là số lượng k-FIs lớn nhất. Đây cũng là nhược điểm của giải thuật này.
4.2.4.1.2 Giải thuật FP Growth
Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
24
Xây dựng thử nghiệm tập mẫu và phần mềm tự động phân loại văn bản.
Thuật toán FP-growth thông qua ý tưởng chia để trị (divide & conquer
approach) để cực tiểu số lượng itemset tạo ra. FP-growth giảm bớt số lần quét toàn
bộ cơ sở dữ liệu và khai thác cấu trúc dữ liệu thành cây FP để tìm kiếm tất cả FI.
Ví dụ: Xây dựng cây FP với Min_support = 0.5
Bảng 2.1. Dữ liệu đầu vào để xây dựng cây FP
DocID Items Frequent items
100 {f, a, c, d, g, i, m, p} {f, c, a, m, p}
200 {a, b, c, f, l, m, o} {f, c, a, b, m}
300 {b, f, h, j, o} {f, b}
400 {b, c, k, s, p} {c, b, p}
500 {a, f, c, e, l, p, m, n} {f, c, a, m, p}
Các bước tiến hành:
1. Quét cơ sở dữ liệu, tìm ra các tập thuật ngữ thường xuyên ở mức 1.
2. Sắp xếp các thuật ngữ thường xuyên theo thứ tự giảm dần.
3. Quét cơ sở dữ liệu lại và xây dựng cây FP.

Hình 2.5. Ví dụ về xây dựng cây FP

Sinh viên thực hiện : Trần Quý Giáp K47 Lớp CNPM Trang
25