ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

LƯU TRƯỜNG HUY

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

LUẬN VĂN THẠC SĨ

HƢỚNG DẪN KHOA HỌC:
PSG.TS. NGUYỄN NGỌC BÌNH

Hà Nội - 2008


LỜI CẢM ƠN
Tôi xin đƣợc bầy tỏ sự biết ơn sâu sắc đến ngƣời hƣớng dẫn khoa học của
mình, PGS. TS. Nguyễn Ngọc Bình, Trƣờng Đại học Công nghệ, Đại học
Quốc gia Hà nội, vì những nhận xét, hỗ trợ và chỉ bảo trong quá trình làm đồ
án.
Xin đƣợc gửi lời cảm ơn đến TS. Dell Zhang, Đại học tổng hợp London,
với những giúp đỡ và góp ý trong quá trình tìm hiểu, cải tiến, cài đặt và thực
nghiệm cho phƣơng pháp phân loại văn bản sử dụng thuộc tính nhóm xâu con
chính.
Xin đƣợc gửi lời cảm ơn đến GS.TS. Chil Jen Lin, Đại học Quốc gia Đài

Bookmark not defined.
2.1. Các vector thuộc tính............................. Error! Bookmark not defined.
2.2. Việc lựa chọn thuộc tính ....................... Error! Bookmark not defined.
2.2.1. Loại bỏ các từ dừng ........................ Error! Bookmark not defined.
2.2.2. Xác định gốc của từ ........................ Error! Bookmark not defined.
2.2.3. Lựa chọn thuộc tính ........................ Error! Bookmark not defined.
2.3. Một số phƣơng pháp lựa chọn thuộc tính trong phân loại văn bảnError!
Bookmark not defined.
2.3.1. Ngƣỡng tần xuất văn bản (DF) ....... Error! Bookmark not defined.
2.3.2. Lợi ích thông tin (IG) ..................... Error! Bookmark not defined.
2.3.3. Thông tin tƣơng hỗ (MI) ................ Error! Bookmark not defined.
2.3.4. Thống kê Chi bình phƣơng  ........ Error! Bookmark not defined.
2.3.5. Cƣờng độ của từ (TS) ..................... Error! Bookmark not defined.
2.3.6. Một số phƣơng pháp khác .............. Error! Bookmark not defined.
2.4. Tổng kết chƣơng.................................... Error! Bookmark not defined.
2


CHƢƠNG 3 - CÁC PHƢƠNG PHÁP PHÂN LOẠI VĂN BẢN TRUYỀN
THỐNG ............................................................ Error! Bookmark not defined.
3.1. Phƣơng pháp Rocchio ........................... Error! Bookmark not defined.
3.2. Phƣơng pháp k- Nearest Neighbour ...... Error! Bookmark not defined.
3.3. Phƣơng pháp Naïve Bayes (NB) ........... Error! Bookmark not defined.
3.4. Phƣơng pháp Linear Least Square Fit- LLSF ...... Error! Bookmark not
defined.
3.5. Phƣơng pháp Centroid- based vector .... Error! Bookmark not defined.
3.6. Phƣơng pháp SVM- Support Vector Machine ..... Error! Bookmark not
defined.
3.7. Một số phƣơng pháp khác ..................... Error! Bookmark not defined.
3.8. Phƣơng pháp đánh giá ........................... Error! Bookmark not defined.

5.6.Tổng kết chƣơng..................................... Error! Bookmark not defined.
CHƢƠNG 6 - CẢI TIẾN GIẢI THUẬT CHIẾT XUẤT THUỘC TÍNH NHÓM
XÂU CON CHÍNH VÀ ÁP DỤNG TRONG PHÂN LOẠI VĂN BẢN TIẾNG
VIỆT ................................................................. Error! Bookmark not defined.
6.1. Giới thiệu ............................................... Error! Bookmark not defined.
6.2. Cây hậu tố.............................................. Error! Bookmark not defined.
6.3. Thuộc tính nhóm xâu con chính ............ Error! Bookmark not defined.
6.3.1. Các nhóm xâu con .......................... Error! Bookmark not defined.
6.3.2. Các nhóm xâu con chính ................ Error! Bookmark not defined.
6.4. Thuật toán .............................................. Error! Bookmark not defined.
6.5. Nhận xét và đề xuất cải tiến thuật toán và chƣơng trìnhError! Bookmark
not defined.
6.6. Thực nghiệm và kết quả ........................ Error! Bookmark not defined.
6.7. Tổng kết chƣơng.................................... Error! Bookmark not defined.
CHƢƠNG 7 - CÁC CỘNG CỤ HỖ TRỢ VÀ CÁC CHƢƠNG TRÌNH Error!
Bookmark not defined.
7.1. Công cụ chiết xuất nội dung từ các web-site báo điện tửError! Bookmark
not defined.
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ínhError!
Bookmark not defined.
7.3. Công cụ chiết xuất thuộc tính KSG và đƣa ra ma trân thuộc tính . Error!
Bookmark not defined.


7.4. Công cụ mở rộng tập dữ liệu kết hợp phân cụm .. Error! Bookmark not
defined.
7.5. Phân lọai văn bản sử dụng thƣ viện LibSVM ..... Error! Bookmark not
defined.
7.6. Công cụ phân loại theo phƣơng pháp kNN và Centroid based vectorError!
Bookmark not defined.

not defined.
Hình 4-1: Tình hình hiện tại của bài toán tách từ tiếng ViệtError! Bookmark not
defined.
Hình 5-1: Phân loại kết hợp phân cụm ............ Error! Bookmark not defined.
Hình 5-2: Thuật toán phân loại văn bản sử dụng phân cụm của Zeng, H.JError!
Bookmark not defined.
Hình 5-3: Thuật toán của phân loại văn bản sử dụng phân cụm của Kyriakopoulou,
A. ...................................................................... Error! Bookmark not defined.
Hình 5-4: Biểu đồ so sánh độ chính xác theo tỷ lệ tập huấn luyên .......... Error!
Bookmark not defined.
Hình 6-1: Cây hậu tố ........................................ Error! Bookmark not defined.
Hình 6-2: Thuật toán chiết xuất thuộc tính nhóm xâu con chínhError! Bookmark
not defined.
Hình 7-1: Minh họa nội dung chính của bài báo trên trang webError! Bookmark
not defined.
Hình 7-2: Giao diện công cụ chiết xuất nội dungError! Bookmark not defined.
Hình 7-3: Minh họa kết quả phân chia dữ liệu cho k-fold cross validationError!
Bookmark not defined.
Hình 7-4: Minh họa cấu trúc thƣ mục đầu vào 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 ........................... Error! Bookmark not defined.
Hình A-1: Biểu đồ ca sử dụng ......................... Error! Bookmark not defined.
Hình A-2: Biểu đồ tuần tự hệ thống................. Error! Bookmark not defined.
Hình A-3: Mô hình khái niệm hệ thống ........... Error! Bookmark not defined.
Hình A-4: Biểu đồ lớp ca sử dụng thao tác corpusError! Bookmark not defined.
Hình A-5: Biểu đồ tuần tự ca sử dụng thao tác corpus ... Error! Bookmark not
defined.
Hình A-6: Biểu đồ lớp KSG ............................ Error! Bookmark not defined.


Hình A-7: Biểu đồ tuần tự KSG ...................... Error! Bookmark not defined.


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

Finite State Machine

GA

Genetics Algorithm


Mutual Information

MM

Maximum Matching

MM

Maximum Entropy

NB

Naïve Bayes

NLP

Natual Language Processing

POS

Part Of Speed

SVM

Support Vector Machine

TBL

Transformation based learning


Bioinfomatics

Tin sinh học

Centroid

Trọng tâm

Context predicate

Thành phần ngữ cảnh

Corpus

Tập ngữ liệu

Co-training

Đồng huấn luyện

Data clustering

Phân cụm dữ liệu

Data mining

Khai phá dữ liệu

Discriminative learning


Inductive learning

Học quy nạp

Key sub-string group

Nhóm xâu con chính

Key-substring group feature

Thuộc tính nhóm xâu con chí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

ngôn ngữ, Viện Ngôn ngữ học, Vienam, http://www.iol.gov.vn .
3. Nguyễn Thanh Hùng (2006), Hướng tiếp cận mới trong việc tách từ tiếng Việt sử
dụng giải thuật di truyền và thống kê Internet, Đại học KHTN tp HCM.

Tiếng Anh
4. Salton, G,; Wong, A., Yang, C., (1975) “A Vector Space Model for automatic
Indexing”, Communications of the ACM, Volume 1, Pages: 613 – 620.
5. Yang, Y. and Pedersen, J. (1997), A comparative study on feature
selection in text categorization, Proceedings of ICML-97, 14th International
Conference on Machine Learning, Nashville, Tennessee, USA .
6. Wilbur, J.W., Sirotkin,K. (1992) “The automatic identification of stop words”,
Journal of Information Science, Volume 18, pages: 45 - 55.
7. Dumais, S. T., Latent Semantic Indexing (LSI) and TREC-2., in The Second Text
REtrieval Conference (TREC2), D. Harman, ed., March 1994, pp. 105-116
8. Soucy, P., Mineau, G.W. (2005), Beyond TFIDF weighting for Text
categorization in the Vector Space Model, International Joint Conferences on
Artificial Intelligence, IJCAI-05, page 1130.
9. Xu, H., Li, Ch. (2007), A Novel Term Weighting Schema for Automatic Text
Categorization, Proceedings of the Seventh International Conference on
Intelligent Systems Design and Applications, Pages 759-764.
10. Li, L.B., Shinwen. Y.; Qin, L. (2003), An improved k-Nearest Neighbor
Algorithm for Text categorization, Proceedings of the 20th International
Conference on
Computer Processing of Oriental Languages, Shenyang, China.
11. Yang, Y.; Chute, C.G. (1994), “An example-based mapping method for text
categorization and retrieval”, ACM Transaction on Information Systems,


Volume 12, pages: 252-277.
12. Yang. Y., Liu, X. (1999), A re-examination of Text Categorization Methods,

23. Berry, M. W. (2004), Survery of Text Mining: Clustering, Classification and


Retrieval, Springer, NY, USA.
24. Takamura, H. (2003), Clustering approaches to Text categorization, Phd’s
thesis.
25. Zeng, H.J.; Wang, X.H.; Chen, Zh.; Ma, W.Y. (2003), CBC: Clustering based
Text Classification requiring minimal labelled data, Third IEEE International
Conference on Data Mining (ICDM'03) p. 443.
26. Li, H., Abe, N. (1998), Word clustering and disambiguation based on
co-occurrence data, In Proceedings of COLING - ACL'98.
27. Joachims, T. (1999), Transductive Inference for Text Classification Using
Support Vector Machine, In Proceedings of ICML-99, 16th International
Conference on Machine Learning, pages 200-209, San Francisco, CA, USA.
28. Kyriakopoulou, A.; Kalamboukis, T. (2006), Text Classification using
clustering, In Proceedings of the ECML-PKDD Discovery Challenge
Workshop, 2006.
29. Kyriakopoulou, A., Kalamboukis, T. (2007), Using clustering to Enhance Text
Classification, Proceedings of the 30th annual international ACM SIGIR
conference, Amsterdam, The Netherlands.
30. Zhang, D; Lee W.S. (2006), Extracting Key Substring Group Features for Text
Classification, Proceedings of The Twelfth Annual SIGKDD International
Conference on Knowledge Discovery and Data Mining, Philadelphia, USA.
31. Dan. G. (1997), Algorithms on Strings, Trees, and Sequences, Computer
Science and Computational Biology, Cambridge University Press.
32. Precup, D. (2002), Applying Machine Learning Algorithms to Text
Categorization, ACM Computing Surveys (CSUR), Volume 34, Pages: 1 - 47 .

Web sites:
33. TinySVM, an implementation of Support Vector Machines, Open source,