Tài liệu Nghiên cứu ứng dụng mạng bayes xây dựng hệ thống tự động phân loại văn bản

MỤC LỤC DANH MỤC CÁC BẢNG - BIỂU LỜI MỞ ĐẦU .................................................................................................. 1 Chương 1. TỔNG QUAN CÁC MÔ HÌNH, PHƯƠNG PHÁP VÀ HỆ THỐNG PHÂN LOẠI VĂN BẢN ................................................................. 5 1.1. TỔNG QUAN VỀ PHÂN LOẠI VĂN BẢN ......................................... 5 1.2. CÁC MÔ HÌNH VÀ PHƯƠNG PHÁP PHÂN LOẠI VĂN BẢN ........ 7 1.2.1. Xử lý văn bản .................................................................................... 7 1.2.2. Phương pháp phân loại văn bản ........................................................ 9 1.2.2.1. Phương pháp K-Nearest Neighbor (KNN) .................................... 9 1.2.2.2. Phương pháp Linear Least Square Fit (LLSF) ............................ 11 1.2.2.3. Phương pháp cây quyết định (Decision tree) ............................... 11 1.2.2.4. Support Vector Machines (SVM) ................................................ 12 1.2.2.5. Neural Network (NNet) ............................................................... 13 1.2.2.6. Centroid - Based Vector............................................................... 15 1.3. KẾT LUẬN CHƯƠNG ........................................................................ 18 Chương 2. HỆ THỐNG PHÂN LOẠI VĂN BẢN .................................. 19 2.1. XÂY DỰNG MÔ HÌNH PHÂN LOẠI VĂN BẢN ............................. 19 2.2. CÁC GIAI ĐOẠN TRONG HỆ THỐNG ............................................ 22 2.2.1. Tiền xử lý văn bản .......................................................................... 22 2.2.2. Tách từ ............................................................................................ 22 2.2.3. Phương pháp phân loại văn bản sử dụng thuật toán Naïve Bayes.. 24 2.2.3.1. Lý thuyết xác suất Bayes ............................................................. 25 2.2.3.2. Phân loại văn bản dựa trên Naïve Bayes ..................................... 29 2.2.4. Phương pháp giảm kích thước tập văn bản huấn luyện .................. 32 2.2.4.1. Phương pháp Latent Semantic Analysis: ..................................... 32 2.2.4.2. Kỹ thuật SVD - LSA áp dụng tối ưu hóa tập văn bản huấn luyện: ......................................................................................................................... 33 2.3. KẾT LUẬN CHƯƠNG ........................................................................ 38 Chương 3. THIẾT KẾ VÀ TRIỂN KHAI THỬ NGHIỆM HỆ THỐNG 39 3.1. PHÁT TRIỂN HỆ THỐNG PHÂN LOẠI VĂN BẢN ........................ 39 3.2. THIẾT KẾ HỆ THỐNG PHÂN LOẠI VĂN BẢN.............................. 40 3.2.1. Biểu đồ use-case ............................................................................. 40 3.2.2. Biểu đồ tuần tự ................................................................................ 41 3.2.3. Thiết kế cơ sở dữ liệu của hệ thống ................................................ 41 3.2.4. Môi trường và công cụ phát triển hệ thống .................................... 43 3.2.5. Các chức năng của chương trình .................................................... 44 3.3. TRIỂN KHAI THỬ NGHIỆM VÀ ĐÁNH GIÁ KẾT QUẢ ............... 48 3.3.1. Xây dựng dữ liệu văn bản huấn luyện ............................................ 48 3.3.2. Triển khai hệ thống ......................................................................... 49 3.3.3. Kết quả thực nghiệm ....................................................................... 50 3.4. KẾT LUẬN CHƯƠNG ........................................................................ 50 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ................................................... 51 DANH MỤC TÀI LIỆU THAM KHẢO NGHIÊN CỨU ỨNG DỤNG MẠNG BAYES XÂY DỰNG HỆ THỐNG TỰ ĐỘNG PHÂN LOẠI VĂN BẢN Học viên: Phạm Vũ Nhật Huy Chuyên ngành: Khoa khọc máy tính Mã số: 60.48.01.01 Khóa: K31 - Trường Đại học Bách khoa - ĐHĐN Tóm tắt - Với sự phát triển vượt bậc của Internet trong thời đại này, thì việc tìm kiếm văn bản rất dễ dàng; tuy nhiên vấn đề đặt ra là làm sao tìm kiếm được văn bản phù hợp với mục đích người dùng trong khi lượng cơ sở dữ liệu văn bản là rất lớn. Trong luận văn này, tác giả đã đề xuất mô hình phân loại văn bản nhằm giúp cho việc tìm kiếm dễ dàng và nhanh chóng hơn. Mô hình phân loại văn bản đề xuất sử dụng lý thuyết Naïve Bayes - phương pháp phân loại dựa vào xác suất. Bên cạnh đó, tác giả sử dụng Latent Semantic Analysis để tối ưu hóa, giảm kích thước tập văn bản huấn luyện. Xây dựng hệ thống tự động phân loại văn bản trên cơ sở mô hình đề xuất. Từ khóa – phân loại văn bản, phân tích ngữ nghĩa tiềm ẩn, mạng Bayes, phân tích tập huấn luyện, xử lý ngôn ngữ tự nhiên. RESEARCH BAYESIAN NETWORK STRUCTURE AND APPLIED TO DOCUMENT CLASSIFICATION SYSTEM Abstract - Nowadays the internet has increasingly developed, and searching documents by Internet is very easy. But, the problem is how to find suitable documents for needs of the user while the databases on the Internet is very large and separate to many different specialties. In this thesis, the author has proposed a documents classification model to make the process of searching is easier and faster. The proposed model uses the Naïve Bayes theory - a popular classification technique based on probability. In addition, the author uses Latent Semantic Analysis to optimize and reduce the size of the training text. Beside that, the author build a document classification system based on the proposed model. Keywords – document classification, Latent semantic analysis, Bayes network, analysis training data, natural language processing. DANH MỤC CÁC TỪ VIẾT TẮT Từ viết tắt PLVB Tiếng Anh Tiếng Việt Phân loại văn bản LSA Latent semantic analysis SVD LLSF Singular Value Decomposition Phân tích giá trị đơn Linear Least Square Fit Bình phương tối thiểu KNN K-Nearest Neighbor K láng giềng gần nhất (phân loại văn bản) SVM Support vector Machine Máy véc-tơ hỗ trợ NNet Neural Network Mạng Nơ-ron NB Naïve Bayes Phân tích ngữ nghĩa tiềm ẩn DANH MỤC CÁC BẢNG BIỂU Số hiệu Tên bảng Trang 1.1 Bảng ví dụ phương pháp KNN 10 1.2 Bảng so sánh ưu, nhược điểm của các phương pháp 16 PLVB 2.1 Ví dụ điển hình thuật toán Naïve Bayes 26 2.2 Xác suất của giai đoạn Huấn luyện 28 2.3 Bảng dữ liệu tập huấn luyện 30 3.1 Thông tin về chủ đề 42 3.2 Thông tin từ được tách 42 3.3 Thông tin từ khóa cho chủ đề huấn luyện 43 3.4 Thông tin văn bản huấn luyện 43 3.5 Thông tin phân loại 43 3.6 Bảng thông tin dữ liệu văn bản huấn luyện 49 3.7 Bảng kết quá phân loại văn bản bằng tay 49 3.8 Bảng so sánh kết quả phân loại văn bản giữa người và 50 máy DANH MỤC CÁC HÌNH ẢNH Số hiệu Tên bảng Trang 1.1 Bài toán phân loại văn bản 5 1.2 Hình minh họa SVM 13 1.3 Kiến trúc mô đun (Modular Architecture). 14 2.1 Mô hình PLVB trên cơ sở thuật toán Naïve Bayes và 20 LSA 2.2 Quy trình tách từ của công cụ vnTokenizer 23 2.3 Mô tả công thức kỹ thuật SVD 33 2.4 Mô tả công thức kỹ thuật SVD áp dụng thực tế 37 3.1 Màn hình Xử Lý Tập Huấn Luyện 45 3.2 Màn hình chức năng Phân Loại Văn Bản 46 3.3 Màn hình Kết Quả Phân Loại Văn Bản 47 3.4 Màn hình Quản Lý 48 DANH MỤC CÁC SƠ ĐỒ Số hiệu Tên sơ đồ Trang 2.1 Sơ đồ hoạt động của LSA 35 3.1 Sơ đồ các chức năng của hệ thống phân loại văn bản 39 3.2 Use-case Xử lý tập huấn luyện 40 3.3 Use-case Phân loại văn bản 40 3.4 Use-case Quản lý chủ đề 40 3.5 Use-case Quản lý văn bản huấn luyện 41 3.6 Biểu đồ tuần tự xử lý phân loại văn bản 41 3.4 Sơ đồ mối quan hệ của các Bảng dữ liệu 42 1 LỜI MỞ ĐẦU 1. Lý do chọn đề tài: Ngày nay con người không ngừng chia sẻ dữ liệu thông tin về tất cả các đề tài trong cuộc sống, điều đó đã làm cho số lượng các tập tin văn bản xuất hiện trên mạng Internet ngày càng một nhiều hơn, dẫn đến khó khăn trong việc tìm kiếm dữ liệu văn bản. Vấn đề đặt ra của các hệ thống truy cập thông tin là phải làm việc và xử lý lượng dữ liệu ban đầu quá nhiều mà lượng truy cập thì rất lớn. Vì vậy việc phân loại văn bản là việc làm cấp thiết nhằm giúp cho việc truy cập dữ liệu một cách nhanh chóng hơn. Với một lượng cơ sở dữ liệu lớn không thể so sánh từng văn bản một, việc này sẽ tạo ra thời gian dư thừa để tổ chức và tìm kiếm các dữ liệu khả quan hơn. Do đó việc phân loại văn bản theo các nhóm dữ liệu là vấn đề quan trọng trọng lĩnh vực xử lý ngôn ngữ. Trong luận văn này, tác giả sẽ tập trung nghiên cứu ứng dụng mạng Bayes và Latent Semantic Analysis để áp dụng xây dựng hệ thống tự động phân loại văn bản. Mô hình phân loại văn bản đề xuất sử dụng lý thuyết Naïve Bayes - phương pháp phân loại dựa vào xác suất nhằm tăng tốc độ phân loại và Latent Semantic Analysis để tối ưu hóa, giảm kích thước tập văn bản huấn luyện hoặc giảm độ lớn của tập huấn luyện. Vì những lý do như trên, tác giả đề xuất chọn đề tài luận văn cao học: “Nghiên cứu ứng dụng mạng Bayes xây dựng hệ thống tự động phân loại văn bản”. 2. Mục đích và ý nghĩa đề tài: a. Mục đích - Nghiên cứu, phân tích các mô hình, phương pháp phân loại văn bản; - Nghiên cứu và ứng dụng mạng Bayes để xây dựng mô hình phân loại văn bản và sử dụng Latent Semantic Analysis để tối ưu hóa kích thước tập văn bản huấn luyện; 2 - Hiện thực hóa hệ thống tự động phân loại văn bản trên cơ sở mô hình đề xuất. b. Ý nghĩa khoa học - Đề xuất mô hình phân loại văn bản dựa trên mạng Bayes và Latent Semantic Analysis; - Kết quả có thể làm tài liệu tham khảo trong lĩnh vực phân loại văn bản. c. Ý nghĩa thực tiễn - Xây dựng được hệ thống tự động phân loại văn bản áp dụng trong thực tế. 3. Mục tiêu và nhiệm vụ: a. Mục tiêu Mục tiêu chính của đề tài là nghiên cứu và áp dụng mạng Bayes để phân loại văn bản và sử dụng Latent Semantic Analysis để tối ưu hóa kích thước tập văn bản huấn luyện, từ đó đề xuất mô hình phân loại văn bản và phát triển hệ thống tự động phân loại văn bản trên cơ sở mô hình đề xuất. Để thỏa mãn mục tiêu này thì cần đạt được những mục tiêu cụ thể sau: - Nghiên cứu, phân tích các mô hình, phương pháp và hệ thống phân loại văn bản hiện nay; - Nghiên cứu & ứng dụng mạng Bayes và Latent Semantic Analysis để xây dựng mô hình phân loại văn bản; - Hiện thực hóa mô hình đề xuất và triển khai trong thực tế. b. Nhiệm vụ Để đạt được những mục tiêu trên thì nhiệm vụ đặt ra của đề tài là: - Phân tích và nắm vững các mô hình, phương pháp phân loại văn bản, đưa ra bài toán cần giải quyết. - Phân tích và đề xuất mô hình giải quyết bài toán; - Hiện thực hóa hệ thống dựa trên mô hình đề xuất và triển khai, đánh giá kết quả đạt được trong thực tế. 3 4. Đối tượng và phạm vi nghiên cứu: Trong khuôn khổ của luận văn thuộc loại nghiên cứu và ứng dụng, tác giả chỉ giới hạn nghiên cứu các vấn đề sau: - Các mô hình phân loại văn bản; - Nghiên cứu mạng Bayes, Latent Semantic Analysis. 5. Phương pháp nghiên cứu: a. Phương pháp lý thuyết Tiến hành thu thập và phân tích các tài liệu có liên quan đến đề tài; Nghiên cứu mạng Bayes, Latent Semantic Analysis; Đánh giá lựa chọn phương hướng giải quyết vấn đề. b. Phương pháp thực nghiệm - Nghiên cứu đề xuất giải pháp, mô hình phân loại văn bản; - Hiện thực hóa hệ thống trên cơ sở mô hình đề xuất; - Cài đặt hệ thống và triển khai thực tế, nhận xét và đánh giá kết quả đạt được. 6. Phương pháp nghiên cứu: - Ngôn ngữ lập trình C# – Microsoft Visual Studio; - Hệ quản trị cơ sở dữ liệu SQL Server 2008. 7. Kết luận a. Kết quả của đề tài - Đề xuất mô hình phân loại văn bản dựa trên mạng Bayes và Latent Semantic Analysis; - Hiện thực hóa hệ thống tự động phân loại văn bản trên cơ sở mô hình đề xuất; - Triển khai hệ thống trong thực tế và đánh giá hiệu quả của mô hình. b. Hướng phát triển của đề tài - Áp dụng xử lý đa luồng nhằm nâng cao hiệu quả; - Tiếp tục nghiên cứu pháp triển để nâng cao tính chính xác của mô hình đề xuất. 4 8. Kết cấu đề tài: Chương 1: Tổng quan các mô hình, phương pháp và hệ thống phân loại văn bản. Chương 2: Nghiên cứu và ứng dụng mạng Bayes xây dựng mô hình phân loại văn bản. Chương 3: Xây dựng hệ thống, triển khai và đánh giá. 5 Chương 1. TỔNG QUAN CÁC MÔ HÌNH, PHƯƠNG PHÁP VÀ HỆ THỐNG PHÂN LOẠI VĂN BẢN 1.1. TỔNG QUAN VỀ PHÂN LOẠI VĂN BẢN Phân loại văn bản là sự phân loại không cấu trúc các tài liệu văn bản dựa trên một tập hợp của một hay nhiều loại văn bản đã được định nghĩa trước. Quá trình này thường được thực thi bằng một hệ thống tự động gán cho các tài liệu văn bản một loại nào đó. Trong thực tế ứng dụng quan trọng nhất của phân loại văn bản là giới hạn phạm vi tìm kiếm thông tin (bởi thay cho việc phải lục soát tất cả các tài liệu họ chỉ tập trung vào một số loại văn bản có liên quan đến thông tin mà họ cần tìm kiếm) [22]. Phân loại văn bản góp phần quan trọng trong việc tổ chức thông tin và quản lí tài liệu. Ứng dụng phổ biến nhất của phân loại văn bản là trợ giúp cho việc tìm kiếm và lọc văn bản do đó tăng tốc độ truy cập thông tin. Phân loại văn bản cũng đóng vai trò quan trọng trong việc đa dạng hóa và chuyên nghiệp hóa các công việc quản lí thông tin như là: việc sắp xếp các loại thư điện tử hoặc các file trong các hệ thống, xác minh chủ đề để trợ giúp cho các tiến trình hoạt động xử lí, tìm kiếm hay duyệt các cấu trúc, hoặc để tìm kiếm các loại tài liệu mà người dùng quan tâm. Loại thứ 1 Dữ liệu đầu vào Thuật toán phân loại văn bản Loại thứ 2 Loại thứ n Hình 1.1: Bài toán phân loại văn bản Việc phân loại văn bản vào các tập hợp hoặc cấu trúc được thiết lập theo những tiêu chí khác nhau, như phân loại theo độ ưu tiên, theo chủ đề, và hầu hết những việc làm này tốn rất nhiều thời gian, công sức và đôi khi không chính xác nếu được phân loại một cách thủ công – tức là đọc từng văn bản và 6 gán vào một lớp nào đó. Đặc biệt với số lượng tài liệu cần phân loại cực kỳ lớn như hiện nay thì việc phân loại văn bản thủ công là một điều không thể. Phân loại những đối tượng mới vào các lớp bằng phương pháp thủ công gặp phải những khó khăn sau: - Đối với các lĩnh vực đặc biệt, phân loại các đối tượng mới (như cơ sở dữ liệu về y tế, pháp luật, tài chính, ngân hàng, …) vào các lớp cho trước cần có hiểu biết về các lĩnh vực đó; - Phân loại bằng tay đôi khi không chính xác vì quyết định phụ thuộc vào sự hiểu biết và động cơ của người thực hiện; - Quyết định (nhận định) của nhiều người khác nhau có thể nảy sinh bất đồng ý kiến. Vì vậy những công cụ để tự động phân loại văn bản vào các lớp sẽ rất hữu ích với công việc này nhất là khi thông tin tràn ngập như ngày nay. Một số phương pháp phân loại thống kê và kĩ thuật học máy như Bayesian, máy vector hỗ trợ (Support Vector Machines), KNearest Neighbor, Mạng Nơron, ... được áp dụng để giải quyết bài toán này. Chính vì những nhược điểm của phương pháp thủ công nên việc xây dựng một bộ phân loại văn bản tự động là một điều rất quan trọng và cần thiết, đặc biệt là khi hầu hết các thông tin được sinh ra và lưu trữ điện tử. Các bài báo khoa học và giải trí là những ví dụ về tập các tài liệu điện tử. Với sự phát triển ngày càng mạnh mẽ của mạng Internet và Intranet đã tạo ra nguồn thông tin vô cùng phong phú. Các kỹ thuật phân loại văn bản sẽ giúp cho nguồn dữ liệu này đã được lưu trữ tự động một cách hiệu quả và được tìm kiếm nhanh chóng. Phân loại văn bản được xuất hiện từ những năm 1960, nhưng chỉ 15 năm sau, nó đã trở thành lĩnh vực nghiên cứu chính trong hệ thống thông tin bởi sự đa dạng của các ứng dụng [22]. Phân loại văn bản là công việc được sử dụng để hỗ trợ trong quá trình tìm kiếm thông tin (Information Retrieval), chiết lọc thông tin (Information Extraction), lọc văn bản hoặc tự động dẫn đường cho 7 các văn bản tới những chủ đề xác định trước. Một ứng dụng khác của phân loại văn bản là trong lĩnh vực hiểu văn bản. Phân loại văn bản có thể được sử dụng để lọc văn bản hoặc một phần văn bản chứa dữ liệu cần tìm mà không làm mất đi tính phức tạp của ngôn ngữ tự nhiên. 1.2. CÁC MÔ HÌNH VÀ PHƯƠNG PHÁP PHÂN LOẠI VĂN BẢN 1.2.1. Xử lý văn bản a) Đặc điểm của từ trong Tiếng Việt Tiếng Việt thuộc ngôn ngữ đơn lập, tức là mỗi một tiếng (âm tiết) được phát âm tách rời nhau và được thể hiện bằng một chữ viết. Đặc điểm này thể hiện rõ rệt ở tất cả các mặt ngữ âm, từ vựng, ngữ pháp [23]. Đặc điểm ngữ âm: Trong tiếng Việt có một loại đơn vị đặc biệt gọi là "tiếng". Về mặt ngữ âm, mỗi tiếng là một âm tiết. Hệ thống âm vị tiếng Việt phong phú và có tính cân đối, tạo ra tiềm năng của ngữ âm tiếng Việt trong việc thể hiện các đơn vị có nghĩa. Nhiều từ tượng hình, tượng thanh có giá trị gợi tả đặc sắc. Khi tạo câu, tạo lời, người Việt rất chú ý đến sự hài hoà về ngữ âm, đến nhạc điệu của câu văn. Đặc điểm từ vựng: Mỗi tiếng, nói chung, là một yếu tố có nghĩa. Tiếng là đơn vị cơ sở của hệ thống các đơn vị có nghĩa của tiếng Việt. Từ tiếng, người ta tạo ra các đơn vị từ vựng khác để định danh sự vật, hiện tượng, ... chủ yếu nhờ phương thức ghép và phương thức láy. Đặc điểm ngữ pháp: Từ của tiếng Việt không biến đổi hình thái. Đặc điểm này sẽ chi phối các đặc điểm ngữ pháp khác. Khi từ kết hợp từ thành các kết cấu như ngữ, câu, tiếng Việt rất coi trọng phương thức trật tự từ. Việc sắp xếp các từ theo một trật tự nhất định là cách chủ yếu để biểu thị các quan hệ cú pháp. Khi các từ cùng loại kết hợp với nhau theo quan hệ chính phụ thì từ đứng trước giữ vai trò chính, từ đứng sau giữ vai trò phụ. Trật tự chủ ngữ đứng trước, vị ngữ đứng sau là trật tự phổ biến của kết cấu câu tiếng Việt. 8 Từ: Có rất nhiều quan niệm về từ trong tiếng Việt, từ nhiều quan niệm về từ tiếng Việt khác nhau đó chúng ta có thể thấy đặc trưng cơ bản của "từ" là sự hoàn chỉnh về mặt nội dung, từ là đơn vị nhỏ nhất để đặt câu. Người ta dùng "từ" kết hợp thành câu chứ không phải dùng "tiếng", do đó quá trình tách câu thành các "từ" cho kết quả tốt hơn là tách câu bằng “tiếng”. b) Đặc trưng văn bản Đối với mỗi một văn bản luôn chứa tập các từ khóa và gọi tập các từ khóa này là tập các thuật ngữ (term). Một phần tử trong tập term thì đơn giản là một từ, mà ngữ nghĩa của từ này giúp tạo thành nên nội dung của văn bản [23]. Giả sử cho một tập term của một văn bản nào đó, chúng ta có thể nhận thấy rằng không phải tất cả các từ trong tập term này đều có mức độ quan trọng như nhau trong việc mô tả nội dung văn bản. Ví dụ, bây giờ chúng ta xét một tập gồm một ngàn văn bản, giả sử có một từ A nào đó xuất hiện trong một ngàn văn bản này thì chúng ta có thể khẳng định rằng từ A này không quan trọng và chúng ta sẽ không quan tâm đến nó, bởi vì chắc chắn là nó sẽ không cho chúng ta biết được về nội dung của các văn bản này. Vì vậy từ A sẽ bị loại ra khỏi tập các term, khi chúng ta xây dựng tập term cho văn bản để miêu tả nội dung ngữ nghĩa của các văn bản này. Kết quả này có được thông qua thao tác xác định trọng số cho mỗi một từ trong tập term của một văn bản. c) Biểu diễn văn bản Để có thể xử lý được các văn bản, thì phải chuyển chúng về dạng dữ liệu có cấu trúc. Để thực hiện được công việc này, người ta đưa ra các mô hình biểu diễn văn bản. Mô hình biểu diễn văn bản có ảnh hưởng rất nhiều đến hiệu quả và hiệu suất xử lý các văn bản. Tùy mục đích, yêu cầu đặt ra của ứng dụng mà chúng ta lựa chọn mô hình biểu diễn và phương pháp xử lý phù hợp [23]. Các mô hình biểu diễn văn bản đã được sử dụng như mô hình logic, mô hình phân tích cú pháp, mô hình không gian véc-tơ. 9 Bản chất của mô hình không gian véc-tơ là mỗi văn bản được biểu diễn thành một véc-tơ. Mỗi thành phần của véc-tơ biểu diễn một thuật ngữ riêng biệt trong tập văn bản gốc và được gán một giá trị là một hàm của từng thuật ngữ trong văn bản. Giá trị này thường là trọng số của từ trong văn bản, được xác định theo nhiều cách khác nhau. 1.2.2. Phương pháp phân loại văn bản Phân loại văn bản tự động là việc gán các nhãn lên một văn bản mới dựa trên mức độ tương tự của văn bản đó so với các văn bản đã được gán nhãn trong tập huấn luyện. Để phân loại văn bản người ta sử dụng các phương pháp như: thuật toán Naïve Bayes (NB), Neural Network (NNet), Decision Tree (cây quyết định) [8], K láng giềng gần nhất (KNN) [9], Support Vector Machines (SVM) [10], Linear Least Square Fit [11]. 1.2.2.1. Phương pháp K láng giềng gần nhất (KNN) Đây là phương pháp truyền thống khá nổi tiếng về hướng tiếp cận dựa trên thống kê đã được nghiên cứu trong nhận dạng mẫu. Phương pháp phân loại văn bản trên cơ sở thuật toán K-láng giềng gần nhất (K-NN) là so sánh độ phù hợp của văn bản d với từng nhóm chủ đề, dựa trên k văn bản mẫu trong tập huấn luyện mà có độ tương tự với văn bản d là lớn nhất [24]. Khi cần phân loại một văn bản mới, thuật toán sẽ tính khoảng cách (khoảng cách Euclide) của tất cả các văn bản trong tập huấn luyện đến văn bản này để tìm ra k văn bản “gần nhất” (gọi là k “láng giềng”), sau đó dùng các khoảng cách này đánh trọng số cho tất cả chủ đề. Trọng số của một chủ đề chính là tổng tất cả khoảng cách ở trên của các văn bản trong k láng giềng có cùng chủ đề, chủ đề nào không xuất hiện trong k láng giềng sẽ có trọng số bằng 0. Sau đó các chủ đề sẽ được sắp xếp theo mức độ trọng số giảm dần và các chủ đề có trọng số cao sẽ được chọn là chủ đề của văn bản cần phân loại. Có 2 vấn đề cần quan tâm khi phân loại văn bản bằng thuật toán K- láng giềng gần nhất là xác định khái niệm gần, công thức để tính mức độ gần; và 10 làm thế nào để tìm được nhóm văn bản phù hợp nhất với văn bản đó (nói cách khác là tìm được chủ đề thích hợp để gán cho văn bản). Khái niệm gần ở đây được hiểu là độ tương tự giữa các văn bản. Có nhiều cách để xác định độ tương tự giữa hai văn bản, trong đó công thức Cosine trọng số được coi là hiệu quả để đánh giá độ tương tự giữa hai văn bản. Khoảng cách giữa 2 văn bản chính là độ tương tự giữa 2 văn bản đó, 2 văn bản có giá trị độ tương tự càng lớn thì khoảng cách càng gần nhau. Dùng công thức Cosine để tính độ tương tự giữa 2 văn bản [9]: Ví dụ: Văn bản A : “Tôi là học sinh” Văn bản B : “Tôi là sinh viên” Văn bản C : “Tôi là giáo viên” Biểu diễn văn bản theo dạng vector : Bảng 1.1: Bảng ví dụ phương pháp KNN tôi là học sinh viên giáo Văn bản A 1 1 1 1 0 0 Văn bản B 1 1 0 1 1 0 Văn bản C 1 1 0 0 1 1 Vector A = (1,1,1,1,0,0) Vector B = (1,1,0,1,1,0) Vector C = (1,1,0,0,1,1) sim(𝐴⃗,⃗⃗⃗⃗ 𝐵)=cos(𝐴⃗,⃗⃗⃗⃗ 𝐵)= sim(𝐴⃗,⃗⃗⃗⃗ 𝐶 )=cos(𝐴⃗,⃗⃗⃗⃗ 𝐶 )= 3 √4∗4 2 √4∗4 =0.75 =0.5 Điều đó cho thấy văn bản A tương tự văn bản B hơn so với C. 11 1.2.2.2. Phương pháp Linear Least Square Fit (LLSF) LLSF là một cách tiếp cận ánh xạ được phát triển bởi Yang và Chute vào năm 1992 [12]. Đầu tiên, LLSF được Yang và Chute thử nghiệm trong lĩnh vực xác định từ đồng nghĩa sau đó sử dụng trong phân loại vào năm 1994. Các thử nghiệm của Yang cho thấy hiệu suất phân loại của LLSF có thể ngang bằng với phương pháp kNN kinh điển. LLSF sử dụng phương pháp hồi quy để học từ tập huấn luyện và các chủ đề có sẵn. Tập huấn luyện được biểu diễn dưới dạng một cặp véc-tơ đầu vào và đầu ra như sau: - Véc-tơ đầu vào một văn bản bao gồm các từ và trọng số; - Véc-tơ đầu ra gồm các chủ đề cùng với trọng số nhị phân của văn bản ứng với véc-tơ đầu vào. Với công thức sau: 𝐹𝐿𝑆 = 𝑎𝑟𝑔𝐹 𝑚𝑖𝑛‖𝐹𝐴 − 𝐵‖2 Trong đó: - A, B là ma trận đại diện tập dữ liệu huấn luyện (các cột trong ma trận tương ứng là các véc-tơ đầu vào và đầu ra); - FLS là ma trận kết quả chỉ ra một ánh xạ từ một văn bản bất kỳ vào véctơ của chủ đề đã gán trọng số. Nhờ vào việc sắp xếp trọng số của các chủ đề, ta được một danh sách chủ đề có thể gán cho văn bản cần phân loại và việc đặt ngưỡng lên trọng số của các chủ đề mà ta tìm được chủ đề thích hợp cho văn bản đầu vào. Hệ thống tự động học các ngưỡng tối ưu cho từng chủ đề, giống với kNN. Mặc dù LLSF và kNN khác nhau về mặt thống kê, nhưng ta vẫn tìm thấy điểm chung ở hoạt động của hai phương pháp là việc học ngưỡng tối ưu [11]. 1.2.2.3. Phương pháp cây quyết định (Decision tree) Đây là phương pháp học xấp xỉ các hàm mục tiêu có giá trị rời rạc. Mặt khác cây quyết định còn có thể chuyển sang dạng biểu diễn tương đương dưới dạng cơ sở tri thức là các luật Nếu – Thì [15]. 12 Bộ phân lớp cây quyết định là một dạng cây mà mỗi nút được gán nhãn là một đặc trưng, mỗi nhánh là giá trị trọng số xuất hiện của đặc trưng trong văn bản cần phân loại, và mỗi lá là nhãn của loại tài liệu. Việc phân loại của một tài liệu dj sẽ được duyệt đệ quy theo trọng số của những đặc trưng có xuất hiện trong văn bản dj. Thuật toán lặp đệ quy đến khi đạt đến nút lá và nhãn của dj chính là nhãn của nút lá tìm được. Thông thường việc phân loại văn bản nhị phân sẽ tương thích với việc dùng cây nhị phân. Cây quyết định này được tổ chức như sau: Các nút trong được gán nhãn bởi các thuật ngữ, nhãn của các cung tương ứng với trọng số của thuật ngữ trong tài liệu mẫu, nhãn của các lá tương ứng với nhãn của các lớp. Cho một tài liệu dj, ta sẽ thực hiện so sánh các nhãn của cung xuất phát từ một nút trong (tương ứng với một thuật ngữ nào đó) với trọng số của thuật ngữ này trong dj, để quyết định nút trong nào sẽ được duyệt tiếp. Quá trình này được lặp từ nút gốc của cây, cho tới khi nút được duyệt là một lá của cây. Kết thúc quá trình này, nhãn của nút lá sẽ là nhãn của lớp được gán cho văn bản. 1.2.2.4. Support Vector Machines (SVM) Support Vector Machines là một phương pháp phân loại dựa trên lý thuyết học thống kê, được đề xuất bởi Vapnik [10]. SVM hoạt động trên nguyên tắc ánh xạ (tuyến tính hoặc phi tuyến) dữ liệu vào không gian các véc-tơ đặc trưng (space of feature vectors) mà ở đó một siêu phẳng tối ưu được tìm ra để tách dữ liệu thuộc hai lớp khác nhau. Cho trước một tập huấn luyện được biểu diễn trong không gian véc-tơ trong đó mỗi tài liệu là một điểm, phương pháp này tìm ra một siêu mặt phẳng h quyết định tốt nhất có thể chia các điểm trên không gian này thành hai lớp riêng biệt tương ứng lớp + và lớp –. Chất lượng của siêu mặt phẳng này được quyết định bởi khoảng cách (gọi là biên) của điểm dữ liệu gần nhất của mỗi loại đến mặt phẳng này. Khoảng cách biên càng lớn thì mặt phẳng quyết định càng tốt đồng thời việc phân loại càng chính xác. 13 Mục đích thuật toán SVM tìm được khoảng cách biên lớn nhất. Cụ thể như hình 1.2 siêu phẳng phân chia dữ liệu học thành 2 lớp + và – với khoảng cách biên lớn nhất. Các điểm gần nhất là các Support Vector [3]: Hình 1.2: Hình minh họa SVM SVM thực chất là một bài toán tối ưu, mục tiêu của thuật toán này là tìm được một không gian H và siêu mặt phẳng quyết định h trên H sao cho sai số phân loại là thấp nhất. 1.2.2.5. Neural Network (NNet) Mạng Neural được nghiên cứu mạnh trong hướng trí tuệ nhân tạo. Wiener là người đã sử dụng mạng Neural để phân loại văn bản, sử dụng 2 hướng tiếp cận: kiến trúc phẳng (không sử dụng lớp ẩn) và mạng nơron 3 lớp (bao gồm một lớp ẩn) [19]. Cả hai hệ thống trên đều sử dụng một mạng nơron riêng rẽ cho từng chủ đề, NNet học cách ánh xạ phi tuyến tính những yếu tố đầu vào như từ, hay mô hình véc-tơ của một văn bản vào một chủ đề cụ thể. Khuyết điểm của phương pháp NNet là tiêu tốn nhiều thời gian dành cho việc huấn luyện mạng nơron.