Tài liệu 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

ĐẠ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 loan, tác giả thƣ viện LIBSVM về nhƣng góp ý trong việc sử dụng LIBSVM cũng nhƣ việc tối ƣu các tham số. Xin đƣợc gửi lời cảm ơn đến các đồng nghiệp và bạn bè về những trợ giúp trong việc xây dựng tập ngữ liệu tiếng Việt cũng nhƣ trong các thực nghiệm tƣơng ứng. Cuối cùng tôi xin gửi lời cảm ơn đến những ngƣời thân trong gia đình mình, nhƣng ngƣời đã dành cho tôi những ủng hộ và động viên đặc biệt trong quá trình học tập cũng nhƣ trong thời gian làm luận văn. Hà nội, tháng 3 năm 2008 Tác giả Lƣu Trƣờng Huy MỤC LỤC Danh sách các hình ............................................................................................ 6 Danh sách bảng .................................................................................................. 8 Danh sách từ viết tắt........................................................................................... 9 Bảng thuật ngữ Anh-Việt ................................................................................. 10 MỞ ĐẦU .......................................................... Error! Bookmark not defined. 1. Cơ sở khoa học và tính thực tiễn của đề tài.Error! Bookmark not defined. 2. Phạm vi và mục đính nghiên cứu của để tàiError! Bookmark not defined. 3. Bố cục và cấu trúc của luận văn ............... Error! Bookmark not defined. CHƢƠNG 1 - TỔNG QUAN VỀ BÀI TOÁN PHÂN LOẠI VĂN BẢNError! Bookmark not defined. 1.1. Tổng quan .............................................. Error! Bookmark not defined. 1.2. Các bƣớc chính trong bài toán phân loại văn bản Error! Bookmark not defined. CHƢƠNG 2 - BIỂU DIỄN VĂN BẢN TRONG PHÂN LOẠI VĂN BẢNError! 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. 3.9. Tổng kết chƣơng.................................... Error! Bookmark not defined. CHƢƠNG 4 - PHÂN LOẠI VĂN BẢN TIẾNG VIỆT . Error! Bookmark not defined. 4.1. Tiếng Việt và một số đặc điểm của tiếng Việt ..... Error! Bookmark not defined. 4.1.1. Cấu trúc từ trong tiếng Việt ............ Error! Bookmark not defined. 4.1.2. So sánh tiếng Việt và tiếng Anh ..... Error! Bookmark not defined. 4.2. Bài toán phân loại văn bản tiếng Việt ... Error! Bookmark not defined. 4.3. Vấn đề tách từ trong văn bản tiếng Việt Error! Bookmark not defined. 4.3.1. Tách từ trong văn bản tiếng Việt dựa trên từ Error! Bookmark not defined. 4.3.2. Tách từ trong văn bản tiếng Việt dựa trên ký tựError! Bookmark not defined. 4.3.3. Một số phƣơng pháp tách từ trong văn bản tiếng ViệtError! Bookmark not defined. 4.4. Thực nghiệm và kết quả ........................ Error! Bookmark not defined. 4.5. Tổng kết chƣơng.................................... Error! Bookmark not defined. CHƢƠNG 5 - ỨNG DỤNG PHÂN CỤM TRONG CẢI TIẾN PHÂN LOẠI VĂN BẢN ................................................................. Error! Bookmark not defined. 5.1. Giới thiệu ............................................... Error! Bookmark not defined. 5.2. Phân cụm dữ liệu ................................... Error! Bookmark not defined. 5.3. Một số phƣơng pháp phân loại văn bản sử dụng phân cụm........... Error! Bookmark not defined. 5.3.1. Phƣơng pháp 1 ................................ Error! Bookmark not defined. 5.3.2. Phƣơng pháp 2 ................................ Error! Bookmark not defined. 5.3.3. Phƣơng pháp 3 ................................ Error! Bookmark not defined. 5.4. Nhận xét ................................................ Error! Bookmark not defined. 5.5. Thực nghiệm và kết quả thực nghiệm ... 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. KẾT LUẬN ...................................................... Error! Bookmark not defined. 1. Nhận xét chung......................................... Error! Bookmark not defined. 2. Hƣớng phát triển....................................... Error! Bookmark not defined. Tài liệu tham khảo............................................................................................ 11 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. ....................... Error! Bookmark not defined. 1. Yêu cầu của chƣơng trình ........................ Error! Bookmark not defined. 2. Phân tích .................................................. Error! Bookmark not defined. 2.1. Mô hình ca sử dụng. .......................... Error! Bookmark not defined. 2.2. Biểu đồ tuần tự hệ thống và mô hình khái niệmError! Bookmark not defined. 3. Thiết kế ..................................................... Error! Bookmark not defined. 3.1. Thao tác trên tập ngữ liệu .................. Error! Bookmark not defined. 3.2. Xử lý thuộc tính xâu con chính. ........ Error! Bookmark not defined. 3.3. Phân loại văn bản bằng phƣơng pháp SVM ..... Error! Bookmark not defined. 4. Cài đặt chƣơng trình ................................. Error! Bookmark not defined. PHỤ LỤC B: Cấu trúc đĩa CD đi kèm............. Error! Bookmark not defined. PHỤ LỤC C: Chia sẽ dữ liệu, các công cụ và chƣơng trình liên quan .... Error! Bookmark not defined. Chỉ mục từ ........................................................ Error! Bookmark not defined. 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ảnError! Bookmark not defined. Hình 1-2: Mô hình trong học máy ................... Error! Bookmark not defined. Hình 2-1: Biểu diễn văn bản bằng vector thuộc tính ...... Error! Bookmark not defined. Hình 3-1: SVM với siêu phẳng phân chia hai nhóm dữ liệu mẫuError! Bookmark 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. Hình A-8: Biểu đồ lớp SVM ............................ Error! Bookmark not defined. Hình A-9: Biểu đồ tuần tự SVM ...................... Error! Bookmark not defined. Danh sách bảng 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 ReutersError! Bookmark not defined. Bảng 4-1: Cấu trúc âm tiết trong tiếng Việt..... Error! Bookmark not defined. Bảng 4-2: So sánh tiếng Việt và Tiếng anh ..... Error! Bookmark not defined. Bảng 4-3: Thống kế nguồn gốc dữ liệu trong corpus ..... Error! Bookmark not defined. Bảng 4-4: Thống kê dữ liệu trong corpus cho từng nhóm văn bản .......... Error! Bookmark not defined. 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 Error! Bookmark not defined. Bảng 5-1: Kết quả thực nghiệm phân lọai sử dụng phân cụmError! Bookmark not defined. Bảng 6-1: Sự phụ thuộc của số thuộc tính KSG với các tham số đầu vàoError! Bookmark not defined. Bảng 6-2: Kết quả sử dụng hàm nhân tuyến tính và hàm nhân RBF ....... Error! Bookmark not defined. Bảng 6-3: So sánh phƣơng pháp SVM và SVM+KSG .. Error! Bookmark not defined. Bảng A-1: Danh sách ca sử dụng ..................... Error! Bookmark not defined. Bảng A-2: Ánh xạ giữa lớp thiết kế và các file cài đặt ... Error! Bookmark not defined. 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 Finite State Machine GA Genetics Algorithm HMM Hiden Markov Model IDF Inverse Document Frequency IG Information Gain kNN k- Nearest Neighbour KSG Key SubString Group LLSP Linear Least Square Fit LRMM Left Right Maximum Matching MI 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 TC Text Categorization TF Term Frequency TM2 Second Moment of Term TS Term Strength TSVM Transductive Support Vector Machine WFST Weight Finite State Transducer 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 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 Học phân biệt Empirical risk minimization Tối thiểu hóa rủi ro thực nghiệm Fard clustering Phân cụm cứng Feature Thuộc tính Feature selection Lựa chọn thuộc tính Generative learning Học suy diễn Incremental clustering Phân cụm bổ sung Incremental supervised learning Học có giám sát bổ sung 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 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 Tài liệu tham khảo 1. Nguyễn Thị Minh Khuê, Nguyễn Ngọc Bình (2006),”Phân loại văn bản sử dụng phương pháp máy vector hỗ trợ (SVMs)”, Kỷ yếu hội Hội thảo khoa học 30 năm thành lập Viện CNTT. Tr.361-371, Hà Nội, tháng 12-2006. 2. Đinh Thị Phƣơng Thu, Huỳnh Quyết Thắng (2006), “Sử dụng luật cấu tạo âm tiết tiếng Việt, hai thành phần trong bài toán kiểm tra chính tả tiếng Việt”, Tạp chí 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, In proceedings of 22nd Annual International SIGIR. 13. Han, E.H., Karypis, G. (1999), Centroid based document classificatino analysis and experimental results, Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery. 14. Joachims, T. (1997), Text categorization with Support Vector Machine: Learning with many relevant features, Proceedings of ECML-98, 10th European Conference on Machine Learning. 15. Nigam, K., Lafferty, J., McCallum, A. (1999), Using Maximum Entropy for Text Classification, In IJCAI-99 Workshop on Machine Learning for Information Filtering, pages 61-67. 16. He, J.; Tan, A.H., Tan, C.L. (2000), A Comparative Study on Chinese Text Categorization Methods, In Proceedings of PRICAI'2000 International Workshop on Text and Web Mining, p24-35. 17. Yang, Y. (1997), An evaluation of statistical approaches to text categorization, Technical Report CMU-CS-97-127, Carnegie Mellon University. 18. Nguyen, T.V., Tran, H.K., Nguyen, T.T.T., Nguyen, H. (2006), Word segmentation for Vietnamese text categorization: an online corpus approach, Research, Innovation and Vision for the Future, The 4th International Conference on Computer Sciences, RIVF 2006, Cantho, Vietnam. 19. Dinh, D., Kiem, H., Toan, N.V. (2001), Vietnamese Word Segmentation, The 6th Natural Language Processing Pacific Rim Symposium, Tokyo, 2001, pages: 749-756. 20. Ha, L.A. (2003), A method for word segmentation in Vietnamese, Proceedings Of Corpus Linguistics 2003, Lancaster, UK. 21. Phan, X.H., Nguyen, C.T. (2006), Vietnamese Word Segmentation with CRFs and SVMs: An investigation, The Pacific Asia Conference on Language, Information and Computation(PACLIC) 2006, China. 22. Peng, F., Feng, F., McCallum, A. (2004). Chinese Segmentation and New Word Detection using Conditional Random Fields, The 20th International Conference on Computational Linguistics. 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, http://chasen.org/~taku/software/TinySVM/ 34. A tool for extracting key sub-string group feature, Open source http://www.dcs.bbk.ac.uk/~dell/publications/ 35. LibSVM a Library for Support Vector Machines, Open source, www.csie.ntu.edu.tw/~cjlin/libsvm/ 36. SVM Light, an implementation of Support Vector Machines (SVMs) in C, Open source, www.svmlight.joachims.org 37. JVNSegmentor, Tool for vietnamese segmentation- Open source, http://jvnsegmenter.sourceforge.net/ 38. CLUTO, Family of Data Clustering Software Tools, http://glaros.dtc.umn.edu/gkhome/views/cluto/