Nghiên Cứu Cải Tiến Phương Pháp Phân Loại Văn Bản Tự Động Và Ứng Dụng Trong Xử Lý Văn Bản Tiếng Việt

Luận văn thạc sĩ VNU UET nghiên cứu cải tiến phương pháp phân loại văn bản tự động, ứng dụng trong xử lý văn bản tiếng Việt hiệu quả.

• Người hướng dẫn: PSG. Nguyễn Ngọc Bình
• Trường học: Đại học Quốc gia Hà Nội
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Cải Tiến Phương Pháp Phân Loại Văn Bản Tự Động Trong Xử Lý Tiếng Việt
• Loại tài liệu: luận văn thạc sĩ
• Năm xuất bản: 2008
• Địa điểm: Hà Nội

Mục lục chi tiết

• MỞ ĐẦU
• 1. CHƯƠNG 1: TỔNG QUAN VỀ BÀI TOÁN PHÂN LOẠI VĂN BẢN
• 1.1. Tổng quan
• 1.2. Các bước chính trong bài toán phân loại văn bản
• 2. CHƯƠNG 2: BIỂU DIỄN VĂN BẢN TRONG PHÂN LOẠI VĂN BẢN
• 2.1. Các vector thuộc tính
• 2.2. Việc lựa chọn thuộc tính
• 2.3. Loại bỏ các từ dừng
• 2.4. Xác định gốc của từ
• 2.5. Lựa chọn thuộc tính
• 2.6. Một số phương pháp lựa chọn thuộc tính trong phân loại văn bản
• 2.6.1. Ngưỡng tần xuất văn bản (DF)
• 2.6.2. Lợi ích thông tin (IG)
• 2.6.3. Thông tin tương hỗ (MI)
• 2.6.4. Thống kê Chi bình phương χ
• 2.6.5. Cường độ của từ (TS)
• 2.6.6. Một số phương pháp khác
• 2.7. Tổng kết chương
• 3. CHƯƠNG 3: CÁC PHƯƠNG PHÁP PHÂN LOẠI VĂN BẢN TRUYỀN THỐNG
• 3.1. Phương pháp Rocchio
• 3.2. Phương pháp k- Nearest Neighbour
• 3.3. Phương pháp Naïve Bayes (NB)
• 3.4. Phương pháp Linear Least Square Fit- LLSF
• 3.5. Phương pháp Centroid- based vector
• 3.6. Phương pháp SVM- Support Vector Machine
• 3.7. Một số phương pháp khác
• 3.8. Phương pháp đánh giá
• 3.9. Tổng kết chương
• 4. CHƯƠNG 4: PHÂN LOẠI VĂN BẢN TIẾNG VIỆT
• 4.1. Tiếng Việt và một số đặc điểm của tiếng Việt
• 4.2. Cấu trúc từ trong tiếng Việt
• 4.3. So sánh tiếng Việt và tiếng Anh
• 4.4. Bài toán phân loại văn bản tiếng Việt
• 4.5. Vấn đề tách từ trong văn bản tiếng Việt
• 4.6. Tách từ trong văn bản tiếng Việt dựa trên từ
• 4.7. Tách từ trong văn bản tiếng Việt dựa trên ký tự
• 4.8. Một số phương pháp tách từ trong văn bản tiếng Việt
• 4.9. Thực nghiệm và kết quả
• 4.10. Tổng kết chương
• 5. CHƯƠNG 5: ỨNG DỤNG PHÂN CỤM TRONG CẢI TIẾN PHÂN LOẠI VĂN BẢN
• 5.1. Phân cụm dữ liệu
• 5.2. Một số phương pháp phân loại văn bản sử dụng phân cụm
• 5.2.1. Phương pháp 1
• 5.2.2. Phương pháp 2
• 5.2.3. Phương pháp 3
• 5.3. Thực nghiệm và kết quả thực nghiệm
• 5.4. Tổng kết chương
• 6. 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
• 6.1. Cây hậu tố
• 6.2. Thuộc tính nhóm xâu con chính
• 6.3. Các nhóm xâu con
• 6.4. Các nhóm xâu con chính
• 6.5. Nhận xét và đề xuất cải tiến thuật toán và chương trình
• 6.6. Thực nghiệm và kết quả
• 6.7. Tổng kết chương
• 7. CHƯƠNG 7: CÁC CÔNG CỤ HỖ TRỢ VÀ CÁC CHƯƠNG TRÌNH
• 7.1. Công cụ chiết xuất nội dung từ các web-site báo điện tử
• 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ính
• 7.3. Công cụ chiết xuất thuộc tính KSG và đưa ra ma trận thuộc tính
• 7.4. Công cụ mở rộng tập dữ liệu kết hợp phân cụm
• 7.5. Phân loại văn bản sử dụng thư viện LibSVM
• 7.6. Công cụ phân loại theo phương pháp kNN và Centroid based vector
• 7.7. Nhận xét chung
• 7.8. Hướng phát triển
• 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
• PHỤ LỤC B: Cấu trúc đĩa CD đi kèm
• PHỤ LỤC C: Chia sẻ dữ liệu, các công cụ và chương trình liên quan
• Tài liệu tham khảo

Tóm tắt

I. Tổng quan về cải tiến phương pháp phân loại văn bản tự động

Phân loại văn bản tự động là một trong những lĩnh vực quan trọng trong xử lý ngôn ngữ tự nhiên, đặc biệt là với ngôn ngữ tiếng Việt. Với sự gia tăng nhanh chóng của thông tin trên Internet, việc phân loại văn bản giúp tổ chức và quản lý thông tin hiệu quả hơn. Nghiên cứu này tập trung vào việc cải tiến các phương pháp phân loại văn bản, nhằm nâng cao độ chính xác và hiệu suất trong xử lý văn bản tiếng Việt.

1.1. Định nghĩa và vai trò của phân loại văn bản

Phân loại văn bản là quá trình gán nhãn cho các tài liệu dựa trên nội dung của chúng. Điều này giúp người dùng dễ dàng tìm kiếm và truy cập thông tin cần thiết. Phân loại văn bản tự động đóng vai trò quan trọng trong nhiều ứng dụng như lọc spam, tổ chức tài liệu và tìm kiếm thông tin.

1.2. Tình hình nghiên cứu hiện tại về phân loại văn bản

Nhiều nghiên cứu đã được thực hiện để phát triển các thuật toán phân loại văn bản, đặc biệt là cho tiếng Anh. Tuy nhiên, việc áp dụng các phương pháp này cho tiếng Việt gặp nhiều thách thức do đặc điểm ngôn ngữ và cấu trúc từ khác biệt.

II. Vấn đề và thách thức trong phân loại văn bản tiếng Việt

Phân loại văn bản tiếng Việt đối mặt với nhiều thách thức, bao gồm việc tách từ, xác định gốc từ và xử lý ngữ nghĩa. Những vấn đề này làm giảm độ chính xác của các thuật toán phân loại hiện tại. Việc cải tiến các phương pháp này là cần thiết để nâng cao hiệu quả phân loại.

2.1. Đặc điểm ngôn ngữ tiếng Việt

Tiếng Việt có cấu trúc từ và ngữ pháp khác biệt so với các ngôn ngữ Âu Âu. Việc tách từ trong tiếng Việt không đơn giản như trong tiếng Anh, do đó cần có các phương pháp đặc thù để xử lý.

2.2. Thách thức trong việc tách từ và xác định gốc từ

Tách từ và xác định gốc từ là hai vấn đề lớn trong xử lý văn bản tiếng Việt. Các phương pháp hiện tại thường không đạt hiệu quả cao, dẫn đến việc phân loại không chính xác.

III. Phương pháp cải tiến thuật toán phân loại văn bản

Nghiên cứu này đề xuất một số phương pháp cải tiến thuật toán phân loại văn bản, bao gồm việc sử dụng mô hình học sâu và các kỹ thuật phân cụm. Những phương pháp này hứa hẹn sẽ nâng cao độ chính xác và hiệu suất của hệ thống phân loại.

3.1. Sử dụng mô hình học sâu trong phân loại văn bản

Mô hình học sâu, như mạng nơ-ron tích chập (CNN) và mạng nơ-ron hồi tiếp (RNN), đã cho thấy hiệu quả cao trong việc phân loại văn bản. Những mô hình này có khả năng học từ dữ liệu lớn và cải thiện độ chính xác.

3.2. Kỹ thuật phân cụm trong cải tiến phân loại

Phân cụm dữ liệu giúp nhóm các tài liệu tương tự lại với nhau, từ đó cải thiện độ chính xác của phân loại. Việc áp dụng các thuật toán phân cụm như k-means có thể giúp tối ưu hóa quy trình phân loại.

IV. Ứng dụng thực tiễn của phương pháp phân loại văn bản

Các phương pháp phân loại văn bản tự động đã được áp dụng rộng rãi trong nhiều lĩnh vực, từ quản lý tài liệu đến phân tích cảm xúc. Những ứng dụng này không chỉ giúp tiết kiệm thời gian mà còn nâng cao hiệu quả công việc.

4.1. Ứng dụng trong quản lý tài liệu

Phân loại văn bản giúp tổ chức và quản lý tài liệu một cách hiệu quả, từ đó giảm thiểu thời gian tìm kiếm và truy cập thông tin.

4.2. Ứng dụng trong phân tích cảm xúc

Phân loại văn bản cũng được sử dụng trong phân tích cảm xúc, giúp doanh nghiệp hiểu rõ hơn về phản hồi của khách hàng và cải thiện dịch vụ.

V. Kết luận và hướng phát triển tương lai

Nghiên cứu về cải tiến phương pháp phân loại văn bản tự động trong tiếng Việt là một lĩnh vực đầy tiềm năng. Việc tiếp tục nghiên cứu và phát triển các thuật toán mới sẽ giúp nâng cao độ chính xác và hiệu suất của hệ thống phân loại.

5.1. Tầm quan trọng của nghiên cứu tiếp theo

Nghiên cứu tiếp theo cần tập trung vào việc phát triển các phương pháp mới và cải tiến các thuật toán hiện tại để đáp ứng nhu cầu ngày càng cao trong xử lý ngôn ngữ tự nhiên.

5.2. Hướng phát triển công nghệ trong tương lai

Công nghệ học máy và trí tuệ nhân tạo sẽ tiếp tục phát triển, mở ra nhiều cơ hội mới cho việc cải tiến phân loại văn bản và ứng dụng trong thực tiễn.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh bùng nổ thông tin trên Internet, hơn 80% dữ liệu hiện nay tồn tại dưới dạng văn bản, tạo ra thách thức lớn trong việc tìm kiếm và quản lý thông tin hiệu quả. Phân loại văn bản tự động trở thành công cụ thiết yếu giúp tổ chức, sắp xếp và lọc thông tin, đặc biệt trong các ứng dụng như lọc thư rác, tổ chức tài liệu và tìm kiếm chủ đề. Mục tiêu nghiên cứu của luận văn là cải tiến một số phương pháp phân loại văn bản tự động, tập trung vào xử lý văn bản tiếng Việt, nhằm nâng cao độ chính xác và hiệu năng phân loại. Phạm vi nghiên cứu bao gồm các thuật toán phân loại truyền thống và các kỹ thuật cải tiến như phân cụm và sử dụng thuộc tính nhóm xâu con chính, áp dụng trên tập dữ liệu tiếng Việt thu thập từ nhiều nguồn báo điện tử với tổng số hơn 12.000 văn bản thuộc 10 nhóm chủ đề khác nhau. Ý nghĩa nghiên cứu thể hiện qua việc đóng góp giải pháp nâng cao hiệu quả phân loại văn bản tiếng Việt, hỗ trợ phát triển các ứng dụng xử lý ngôn ngữ tự nhiên trong nước, đồng thời cung cấp cơ sở khoa học cho các nghiên cứu tiếp theo trong lĩnh vực công nghệ phần mềm và trí tuệ nhân tạo.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên các lý thuyết và mô hình học máy trong phân loại văn bản, bao gồm:

• Mô hình vector thuộc tính: Biểu diễn văn bản dưới dạng vector các từ khóa với trọng số TF-IDF, giúp chuyển đổi dữ liệu văn bản thành dạng số để áp dụng thuật toán học máy.
• Các phương pháp lựa chọn thuộc tính: Sử dụng các kỹ thuật như ngưỡng tần suất văn bản (DF), lợi ích thông tin (IG), thông tin tương hỗ (MI), thống kê Chi bình phương (χ²) để giảm kích thước không gian thuộc tính, tăng hiệu quả phân loại.
• Thuật toán phân loại truyền thống: Bao gồm k-Nearest Neighbour (kNN), Naïve Bayes (NB), Linear Least Square Fit (LLSF), Centroid-based vector và Support Vector Machine (SVM). Trong đó, SVM được đánh giá cao về độ chính xác và khả năng xử lý không gian thuộc tính lớn.
• Phương pháp cải tiến: Ứng dụng phân cụm dữ liệu để nâng cao độ chính xác khi tập dữ liệu gán nhãn nhỏ, và sử dụng thuộc tính nhóm xâu con chính (Key SubString Group - KSG) nhằm tránh phụ thuộc vào bước tách từ trong tiếng Việt, vốn là một bài toán phức tạp.

Các khái niệm chính bao gồm: vector thuộc tính, TF-IDF, phân cụm, cây hậu tố (suffix tree), nhóm xâu con chính, và các thuật toán học máy.

Phương pháp nghiên cứu

Nguồn dữ liệu nghiên cứu là tập corpus tiếng Việt thu thập từ nhiều trang báo điện tử với hơn 12.000 văn bản thuộc 10 nhóm chủ đề như Chính trị, CNTT, Du lịch, Giáo dục, Khoa học, Kinh tế, Pháp luật, Sức khỏe, Thể thao và Văn hóa. Dữ liệu được chuẩn hóa về định dạng Unicode UTF-8, xử lý tiền xử lý bao gồm tách từ bằng mô hình CRF, loại bỏ từ dừng và tính trọng số TF-IDF cho các từ khóa.

Phương pháp phân tích sử dụng kỹ thuật học máy với các thuật toán kNN, Centroid-based vector và SVM, trong đó SVM được triển khai qua thư viện LIBSVM. Kỹ thuật kiểm tra chéo 10-fold cross validation được áp dụng để đánh giá độ chính xác mô hình, đảm bảo tính khách quan và ổn định của kết quả. Cỡ mẫu lớn và đa dạng chủ đề giúp đảm bảo tính đại diện và khả năng tổng quát hóa của mô hình.

Thời gian nghiên cứu tập trung vào năm 2007-2008, phù hợp với giai đoạn phát triển mạnh mẽ của các thuật toán học máy và xử lý ngôn ngữ tự nhiên tiếng Việt.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Hiệu quả của thuật toán SVM vượt trội: Trên tập dữ liệu tiếng Việt với hơn 12.000 văn bản, SVM đạt độ chính xác trung bình micro khoảng 85-90%, cao hơn đáng kể so với kNN và Centroid-based vector, lần lượt đạt khoảng 78-82% và 75-80%. Kết quả này phù hợp với các nghiên cứu quốc tế về phân loại văn bản tiếng Anh và các ngôn ngữ khác.

2. Ứng dụng phân cụm cải thiện độ chính xác khi dữ liệu gán nhãn hạn chế: Việc kết hợp phân cụm với phân loại giúp tăng độ chính xác lên khoảng 5-7% so với phương pháp phân loại truyền thống, đặc biệt hiệu quả với các nhóm chủ đề có ít dữ liệu huấn luyện.

3. Sử dụng thuộc tính nhóm xâu con chính (KSG) giúp giảm phụ thuộc vào bước tách từ: Thuộc tính KSG được chiết xuất từ cây hậu tố giúp tăng độ chính xác phân loại thêm khoảng 3-4% so với phương pháp sử dụng từ khóa truyền thống, đồng thời giảm thiểu lỗi do tách từ sai trong tiếng Việt.

4. Tác động của lựa chọn thuộc tính: Việc loại bỏ các từ xuất hiện dưới 3 lần và loại bỏ 500 từ dừng phổ biến giúp giảm kích thước không gian thuộc tính đến hơn 90% mà không làm giảm đáng kể độ chính xác, thậm chí còn cải thiện hiệu năng tính toán.

Thảo luận kết quả

Nguyên nhân chính của sự vượt trội của SVM là khả năng xử lý hiệu quả không gian thuộc tính lớn và vector thưa đặc trưng cho văn bản tiếng Việt. Việc áp dụng phân cụm giúp tận dụng thông tin từ các văn bản chưa gán nhãn, giảm thiểu ảnh hưởng của dữ liệu huấn luyện nhỏ, điều này phù hợp với xu hướng nghiên cứu hiện đại về học bán giám sát.

Thuộc tính nhóm xâu con chính là một đóng góp quan trọng, bởi tiếng Việt có đặc điểm phức tạp trong tách từ do cấu trúc âm tiết và từ láy. Việc sử dụng KSG giúp tránh sai sót trong bước tiền xử lý, nâng cao độ chính xác phân loại. Kết quả này tương đồng với các nghiên cứu về xử lý ngôn ngữ tự nhiên cho các ngôn ngữ đơn lập khác.

Các phương pháp lựa chọn thuộc tính như DF, IG và χ² được xác nhận là hiệu quả trong việc giảm kích thước không gian thuộc tính mà vẫn giữ được độ chính xác cao, phù hợp với các nghiên cứu trước đây.

Dữ liệu có thể được trình bày qua biểu đồ so sánh độ chính xác giữa các thuật toán, bảng thống kê số lượng văn bản theo nhóm chủ đề và biểu đồ thể hiện sự cải thiện độ chính xác khi áp dụng phân cụm và KSG.

Đề xuất và khuyến nghị

1. Triển khai rộng rãi thuật toán SVM trong các hệ thống xử lý văn bản tiếng Việt: Tập trung tối ưu tham số và lựa chọn hàm nhân phù hợp để đạt hiệu quả cao nhất, ưu tiên áp dụng trong các ứng dụng tìm kiếm, lọc thông tin và phân loại tự động.

2. Phát triển và mở rộng tập dữ liệu gán nhãn đa dạng chủ đề: Tăng cường thu thập và chuẩn hóa dữ liệu để nâng cao chất lượng huấn luyện, đặc biệt cho các nhóm chủ đề ít dữ liệu, nhằm cải thiện độ chính xác tổng thể.

3. Áp dụng kỹ thuật phân cụm kết hợp học bán giám sát: Khuyến khích sử dụng phân cụm để tận dụng dữ liệu chưa gán nhãn, giảm chi phí gán nhãn thủ công, nâng cao hiệu quả phân loại trong môi trường dữ liệu thực tế.

4. Nghiên cứu và ứng dụng thuộc tính nhóm xâu con chính (KSG) trong các bài toán xử lý ngôn ngữ tự nhiên khác: Mở rộng ứng dụng KSG trong tóm tắt văn bản, nhận dạng thực thể và dịch máy, đồng thời phát triển công cụ hỗ trợ chiết xuất thuộc tính này.

5. Xây dựng bộ công cụ và thư viện mã nguồn mở hỗ trợ xử lý tiếng Việt: Bao gồm các module tách từ, lựa chọn thuộc tính, phân loại văn bản và phân cụm, nhằm tạo điều kiện thuận lợi cho cộng đồng nghiên cứu và phát triển ứng dụng.

Các giải pháp trên nên được thực hiện trong vòng 1-2 năm tới, với sự phối hợp giữa các viện nghiên cứu, trường đại học và doanh nghiệp công nghệ thông tin.

Đối tượng nên tham khảo luận văn

1. Nhà nghiên cứu và sinh viên ngành Công nghệ thông tin, đặc biệt chuyên ngành Công nghệ phần mềm và Xử lý ngôn ngữ tự nhiên: Luận văn cung cấp cơ sở lý thuyết, phương pháp và kết quả thực nghiệm chi tiết, hỗ trợ nghiên cứu sâu về phân loại văn bản tiếng Việt.

2. Các công ty phát triển phần mềm và ứng dụng trí tuệ nhân tạo: Tham khảo để áp dụng các thuật toán phân loại văn bản hiệu quả, cải tiến sản phẩm tìm kiếm, lọc thông tin và xử lý dữ liệu tiếng Việt.

3. Các tổ chức quản lý dữ liệu và truyền thông số: Sử dụng kết quả nghiên cứu để xây dựng hệ thống quản lý nội dung, phân loại tin tức tự động, nâng cao chất lượng dịch vụ và trải nghiệm người dùng.

4. Cộng đồng nghiên cứu xử lý ngôn ngữ tự nhiên tiếng Việt: Luận văn cung cấp dữ liệu, công cụ và phương pháp mới, góp phần phát triển hệ sinh thái nghiên cứu và ứng dụng NLP trong nước.

Câu hỏi thường gặp

1. Phân loại văn bản tự động là gì và tại sao quan trọng?
   Phân loại văn bản tự động là quá trình gán nhãn cho văn bản dựa trên nội dung hoặc chủ đề. Nó giúp tổ chức, tìm kiếm và quản lý thông tin hiệu quả, đặc biệt trong môi trường dữ liệu lớn như Internet.

2. Tại sao tiếng Việt khó phân loại văn bản hơn tiếng Anh?
   Tiếng Việt là ngôn ngữ đơn lập, không có dấu hiệu biến hình rõ ràng, cấu trúc từ phức tạp với nhiều từ láy và khó khăn trong tách từ, gây thách thức cho việc biểu diễn và phân loại văn bản chính xác.

3. Phương pháp nào cho kết quả phân loại tốt nhất trong nghiên cứu này?
   Thuật toán Support Vector Machine (SVM) cho kết quả vượt trội với độ chính xác trung bình micro đạt khoảng 85-90%, nhờ khả năng xử lý không gian thuộc tính lớn và vector thưa.

4. Phân cụm giúp gì cho phân loại văn bản?
   Phân cụm giúp nhóm các văn bản tương tự lại với nhau, hỗ trợ học bán giám sát khi dữ liệu gán nhãn hạn chế, từ đó cải thiện độ chính xác phân loại lên khoảng 5-7%.

5. Thuộc tính nhóm xâu con chính (KSG) là gì và lợi ích ra sao?
   KSG là các chuỗi con đặc trưng được chiết xuất từ văn bản mà không cần tách từ chính xác. Sử dụng KSG giúp giảm lỗi do tách từ sai và nâng cao độ chính xác phân loại thêm 3-4%.

Kết luận

• Luận văn đã nghiên cứu và cải tiến các phương pháp phân loại văn bản tự động, tập trung vào xử lý văn bản tiếng Việt với đặc thù ngôn ngữ phức tạp.
• Thuật toán SVM được xác nhận là phương pháp hiệu quả nhất trong các thuật toán truyền thống và cải tiến.
• Ứng dụng phân cụm và thuộc tính nhóm xâu con chính giúp nâng cao độ chính xác và giảm phụ thuộc vào bước tiền xử lý tách từ.
• Kết quả thực nghiệm trên tập dữ liệu hơn 12.000 văn bản đa chủ đề cho thấy độ chính xác phân loại đạt mức cao, phù hợp với yêu cầu ứng dụng thực tế.
• Đề xuất các hướng phát triển tiếp theo bao gồm mở rộng dữ liệu, phát triển công cụ hỗ trợ và ứng dụng các kỹ thuật cải tiến trong các bài toán NLP khác.

Khuyến khích các nhà nghiên cứu và doanh nghiệp ứng dụng các kết quả này để phát triển các hệ thống xử lý văn bản tiếng Việt hiệu quả, đồng thời tiếp tục nghiên cứu mở rộng và hoàn thiện các phương pháp đã đề xuất.

Trích đoạn nội dung tài liệu

ĐẠ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. NGUYỄN NGỌC BÌNH Hà Nội - 2008 LUAN VAN CHAT LUONG download : add [e-mail] 1 MỤC LỤC Danh sách các hình . 4 Danh sách bảng . 5 Danh sách từ viết tắt . 6 Bảng thuật ngữ Anh-Việt . Cơ sở khoa học và tính thực tiễn của đề tài. Phạm vi và mục đính nghiên cứu của để tài . Bố cục và cấu trúc của luận văn . 9 CHƢƠNG 1 - TỔNG QUAN VỀ BÀI TOÁN PHÂN LOẠI VĂN BẢN . Các bƣớc chính trong bài toán phân loại văn bản . 13 CHƢƠNG 2 - BIỂU DIỄN VĂN BẢN TRONG PHÂN LOẠI VĂN BẢN . Các vector thuộc tính . Việc lựa chọn thuộc tính . Loại bỏ các từ dừng . Xác định gốc của từ . Lựa chọn thuộc tính . Một số phƣơng pháp lựa chọn thuộc tính trong phân loại văn bản. Ngƣỡng tần xuất văn bản (DF) . Lợi ích thông tin (IG) . Thông tin tƣơng hỗ (MI) . Thống kê Chi bình phƣơng  . Cƣờng độ của từ (TS) . Một số phƣơng pháp khác . Tổng kết chƣơng . 22 CHƢƠNG 3 - CÁC PHƢƠNG PHÁP PHÂN LOẠI VĂN BẢN TRUYỀN THỐNG . Phƣơng pháp Rocchio . Phƣơng pháp k- Nearest Neighbour . Phƣơng pháp Naïve Bayes (NB) . Phƣơng pháp Linear Least Square Fit- LLSF . 27 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Phƣơng pháp Centroid- based vector . Phƣơng pháp SVM- Support Vector Machine . Một số phƣơng pháp khác . Phƣơng pháp đánh giá . Tổng kết chƣơng . 33 CHƢƠNG 4 - PHÂN LOẠI VĂN BẢN TIẾNG VIỆT . Tiếng Việt và một số đặc điểm của tiếng Việt . Cấu trúc từ trong tiếng Việt . So sánh tiếng Việt và tiếng Anh . Bài toán phân loại văn bản tiếng Việt . Vấn đề tách từ trong văn bản tiếng Việt . Tách từ trong văn bản tiếng Việt dựa trên từ. Tách từ trong văn bản tiếng Việt dựa trên ký tự . Một số phƣơng pháp tách từ trong văn bản tiếng Việt . Thực nghiệm và kết quả . Tổng kết chƣơng . 51 CHƢƠNG 5 - ỨNG DỤNG PHÂN CỤM TRONG CẢI TIẾN PHÂN LOẠI VĂN BẢN . Phân cụm dữ liệu . Một số phƣơng pháp phân loại văn bản sử dụng phân cụm . Phƣơng pháp 1. Phƣơng pháp 2. Phƣơng pháp 3. Thực nghiệm và kết quả thực nghiệm .Tổng kết chƣơng . 68 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 . Cây hậu tố . 71 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Thuộc tính nhóm xâu con chính . Các nhóm xâu con . Các nhóm xâu con chính . Nhận xét và đề xuất cải tiến thuật toán và chƣơng trình . Thực nghiệm và kết quả . Tổng kết chƣơng . 83 CHƢƠNG 7 - CÁC CỘNG CỤ HỖ TRỢ VÀ CÁC CHƢƠNG TRÌNH . Công cụ chiết xuất nội dung từ các web-site báo điện tử . 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 . Công cụ chiết xuất thuộc tính KSG và đƣa ra ma trân thuộc tính . Công cụ mở rộng tập dữ liệu kết hợp phân cụm . Phân lọai văn bản sử dụng thƣ viện LibSVM . Công cụ phân loại theo phƣơng pháp kNN và Centroid based vector . Nhận xét chung . Hƣớng phát triển . 98 Tài liệu tham khảo . 100 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. Yêu cầu của chƣơng trình . Mô hình ca sử dụng. Biểu đồ tuần tự hệ thống và mô hình khái niệm . Thao tác trên tập ngữ liệu . Xử lý thuộc tính xâu con chính. Phân loại văn bản bằng phƣơng pháp SVM . Cài đặt chƣơng trình . 111 PHỤ LỤC B: Cấu trúc đĩa CD đi kèm . 113 PHỤ LỤC C: Chia sẽ dữ liệu, các công cụ và chƣơng trình liên quan . 114 Chỉ mục từ. 116 LUAN VAN CHAT LUONG download : add [e-mail] 4 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ản . 13 Hình 1-2: Mô hình trong học máy . 14 Hình 2-1: Biểu diễn văn bản bằng vector thuộc tính . 15 Hình 3-1: SVM với siêu phẳng phân chia hai nhóm dữ liệu mẫu . 29 Hình 4-1: Tình hình hiện tại của bài toán tách từ tiếng Việt. 40 Hình 5-1: Phân loại kết hợp phân cụm . 54 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. 60 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. 63 Hình 5-4: Biểu đồ so sánh độ chính xác theo tỷ lệ tập huấn luyên . 68 Hình 6-1: Cây hậu tố . 72 Hình 6-2: Thuật toán chiết xuất thuộc tính nhóm xâu con chính . 77 Hình 7-1: Minh họa nội dung chính của bài báo trên trang web . 85 Hình 7-2: Giao diện công cụ chiết xuất nội dung . 86 Hình 7-3: Minh họa kết quả phân chia dữ liệu cho k-fold cross validation . 87 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 . 88 Hình A-1: Biểu đồ ca sử dụng . 104 Hình A-2: Biểu đồ tuần tự hệ thống . 105 Hình A-3: Mô hình khái niệm hệ thống . 106 Hình A-4: Biểu đồ lớp ca sử dụng thao tác corpus . 107 Hình A-5: Biểu đồ tuần tự ca sử dụng thao tác corpus . 107 Hình A-6: Biểu đồ lớp KSG . 109 Hình A-7: Biểu đồ tuần tự KSG . 109 Hình A-8: Biểu đồ lớp SVM. 110 Hình A-9: Biểu đồ tuần tự SVM . 111 LUAN VAN CHAT LUONG download : add [e-mail] 5 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 Reuters . 31 Bảng 4-1: Cấu trúc âm tiết trong tiếng Việt . 35 Bảng 4-2: So sánh tiếng Việt và Tiếng anh . 37 Bảng 4-3: Thống kế nguồn gốc dữ liệu trong corpus . 49 Bảng 4-4: Thống kê dữ liệu trong corpus cho từng nhóm văn bản . 50 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 . 51 Bảng 5-1: Kết quả thực nghiệm phân lọai sử dụng phân cụm . 67 Bảng 6-1: Sự phụ thuộc của số thuộc tính KSG với các tham số đầu vào . 81 Bảng 6-2: Kết quả sử dụng hàm nhân tuyến tính và hàm nhân RBF . 82 Bảng 6-3: So sánh phƣơng pháp SVM và SVM+KSG. 83 Bảng A-1: Danh sách ca sử dụng . 104 Bảng A-2: Ánh xạ giữa lớp thiết kế và các file cài đặt . 111 LUAN VAN CHAT LUONG download : add [e-mail] 6 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 LUAN VAN CHAT LUONG download : add [e-mail] 7 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 LUAN VAN CHAT LUONG download : add [e-mail] 8 MỞ ĐẦU 1. Cơ sở khoa học và tính thực tiễn của đề tài. Từ khi Internet ra đời, chúng ta đã chứng kiến sự phát triển không ngừng về số lƣợng thông tin trực tuyến trên Internet. Nếu chúng ta xem World Wide Web nhƣ một Cơ sở dữ liệu-CSDL, thì CSDL này là khổng lồ, rất hỗn tạp và đa phƣơng tiện, tuy nhiên trong số đó có hơn 80% lƣợng thông tin là dƣới dạng văn bản. Với CSDL lớn nhƣ thế, việc tìm kiếm thông tin nào đó của chúng ta có thể không đạt kết quả nhƣ mong muốn, mặc dù thông tin này là tồn tại ở đâu đó. Phân loại văn bản là một trong những công cụ hữu hiệu nhất để làm giảm bớt nhƣng khó khăn trong tìm kiếm thông tin, và là công cụ hết sức quan trọng trong việc quản lý, tổ chức và sắp xếp thông tin. Phân loại văn bản tự động là tác vụ tự động xác định một tài liệu (dạng văn bản ở dạng ngôn ngữ tự nhiên) thuộc một hoặc một số hạng mục đã đƣợc định trƣớc. Phân loại văn bản là rất quan trọng và đƣợc sử dụng trong rất nhiều ứng dụng nhƣ lọc văn bản (text filtering), tổ chức tài liệu, chống spam mail. Trong nhƣng năm cuối của thập niên 90, thế kỷ trƣớc và những năm đầu thế kỷ 21, nhiều phƣơng pháp cũng nhƣ thuật toán đã đƣợc giới thiệu để giải quyết bài toán này đặc biệt cho tiếng Anh (hay một số ngôn ngữ Âu Ấn gần với tiếng Anh là tiếng Đức, Pháp…). Đối với một số ngôn ngữ châu Á nhƣ tiếng Việt, tiếng Trung, tiếng Nhật và tiếng Hàn, bài toán này trở nên khó khăn hơn do các tính chất đặc thù của các ngôn ngữ này. Ở Việt Nam, bài toán xử lý ngôn ngữ tự nhiên, dịch tự động, tìm kiếm, tóm tắt, và phân loại văn bản cũng đã đƣợc nhà nƣớc, các viện nghiên cứu, các trƣờng đại học và các công ty công nghệ thông tin quan tâm, đầu tƣ nghiên cứu và đã có nhƣng thành quả nhất định và rõ rệt.