Tài liệu Phân loại văn bản với phương pháp mạng nurual kết hợp phương pháp cây quyết định

ii PHÂN LOẠI VĂN BẢN VỚI PHƯƠNG PHÁP MẠNG NERUAL KẾT HỢP PHƯƠNG PHÁP CÂY QUYẾT ĐỊNH Học viên: Huỳnh Thị Hiền Thắm Chuyên ngành: Khoa học máy tính Mã số: 60.48.01 Trường Đại học Bách khoa-ĐHĐN Khóa: 31 Tóm tắt - Bài toán phân loại văn bản, thực chất, có thể xem là bài toán phân lớp. Phân loại văn bản tự động là việc gán các nhãn phân loại 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. Nhiều kỹ thuật máy học và khai phá dữ liệu đã được áp dụng vào bài toán phân loại văn bản, chẳng hạn: phương pháp quyết định dựa vào Bayes ngây thơ (Naive Bayes), cây quyết định (decision tree), k–láng giềng gần nhất (KNN), mạng nơron (neural network),… Phương pháp mạng nerual kết hợp phương pháp cây quyết định là chuyển đổi cây quyết định thành các mạng neural. Nhiệm vụ phân loại văn bản của phương pháp này là xây dựng các mạng lưới bằng cách trực tiếp lập bản đồ các nút quyết định hoặc quy định cho các đơn vị neural và nén lại mạng bằng cách loại bỏ các đơn vị và các kết nối không quan trọng và không cần thiết. Từ khóa – Cây quyết định, phân loại văn bản, mạng Nơ-ron. CLASSIFICATION CATEGORY WITH NEURAL NETWORK METHODS COMPLETED BY DECISION METHODOLOGY Abstract - Text document classification, basically, can be considered as a classification problem. Automatic text document classification is to assign a label to a new document based onthe similarity of the document with labeled documents in the training set. Many machinelearning and data mining methods have been applied in text document classification suchas: Naive Bayes, decision tree, k – Nearest neighbor, neural network,… The nerual networking method combines the decision tree method of converting decision trees into neural networks. The textual task of this method is to build networks by directly mapping decision nodes or rules to neural units and compressing networks by removing units and connections. Not important and unnecessary. Key words - Decision tree, text document calssification, Nerual Network. iii MỤC LỤC LỜI CAM ĐOAN ...........................................................................................................i MỤC LỤC .................................................................................................................... iii DANH MỤC CÁC CHỮ VIẾT TẮT ........................................................................... v DANH MỤC CÁC BẢNG............................................................................................vi DANH MỤC CÁC HÌNH VẼ .................................................................................... vii MỞ ĐẦU ......................................................................................................................... 1 1. Tính cấp thiết của đề tài .......................................................................................... 1 2. Mục tiêu và nhiệm vụ ............................................................................................. 1 3. Đối tượng và phạm vi nghiên cứu .......................................................................... 1 4. Phương pháp nghiên cứu ........................................................................................ 2 5. Bố cục đề tài ........................................................................................................... 2 6. Tổng quan tài liệu tham khảo ................................................................................. 2 Chương 1 - CƠ SỞ LÝ THUYẾT .............................................................................. 3 1.1. Phân loại văn bản ................................................................................................. 3 1.1.1. Khái niệm văn bản ...................................................................................... 3 1.1.2. Phân loại văn bản ........................................................................................ 3 1.1.3. Mô hình tổng quát ....................................................................................... 4 1.2. So sánh đặc điểm tiếng Anh và tiếng Việt........................................................... 5 1.2.1. Đặc điểm tiếng Anh và tiếng Việt ............................................................... 5 1.2.2. Nhận xét ...................................................................................................... 5 1.3. Các phương pháp phân loại văn bản.................................................................... 6 1.3.1. Phương pháp Naïve Bayes .......................................................................... 6 1.3.2. Phương pháp k Nearest Neighbor ............................................................... 7 1.3.3. Phương pháp Support Vector Machine ....................................................... 8 1.3.4. Phương pháp Linear Least Square Fit ......................................................... 9 1.3.5. Phương pháp Centroid – based vector ...................................................... 10 1.3.6. Nhận xét .................................................................................................... 10 1.4. Các phương pháp tách từ tiếng Việt .................................................................. 11 1.4.1. Phương pháp Conditional Random Field .................................................. 11 1.4.2. Phương pháp Transformation – based Learning ....................................... 15 1.4.3. Phương pháp Weighted Finite-State Transducer ...................................... 15 1.4.4. Nhận xét .................................................................................................... 16 Chương 2 - ĐỀ XUẤT GIẢI PHÁP ........................................................................... 17 2.1. Giới thiệu bài toán .............................................................................................. 17 2.2. Mô hình đề xuất ................................................................................................. 19 2.3.1. Phương pháp tách từ tiếng Việt .................................................................. 20 2.3.2. Loại bỏ từ dừng ........................................................................................... 22 iv 2.3.3. Mô hình biểu diễn văn bản ......................................................................... 23 2.4. Phương pháp cây quyết định .............................................................................. 28 2.4.1. Cây quyết định ............................................................................................ 28 2.4.2. Thuật toán phân lớp cây quyết định C4.5 ................................................... 32 2.4.3. Chuyển đổi từ cây quyết định sang luật ..................................................... 35 2.5. Phương pháp mạng Neural ................................................................................. 35 2.5.1. Giới thiệu mạng nơron ................................................................................ 35 2.5.2. Luật học của mạng nơron ........................................................................... 38 2.5.3. Thuật toán lan truyền ngược (back-propagation) ....................................... 39 2.6. Phương pháp mạng Nerual khởi tạo với cây quyết định .................................... 41 2.6.1. Thuật toán xây dựng cây quyết định ........................................................... 41 2.6.2. Đào tạo mạng Nerual đa lớp .................................................................... 42 2.6.3. Mạng Nerual khởi tạo với cây quyết định .................................................. 43 Chương 3 - XÂY DỰNG ỨNG DỤNG VÀ THỰC NGHIỆM ................................ 45 3.1. Mô hình đề xuất ................................................................................................. 45 3.1.1. Quá trình tiền xử lý ................................................................................... 45 3.1.2. Biểu diễn văn bản ...................................................................................... 47 3.2. Ứng dụng phương pháp mạng nerual kết hợp cây quyết định trong phân lớp văn bản tiếng Việt................................................................................................................. 51 3.2.1. Huấn luyện ................................................................................................ 51 3.2.2. Phân loại .................................................................................................... 52 3.3. Xây dựng chương trình thử nghiệm ................................................................... 53 3.3.1. Yêu cầu bài toán ......................................................................................... 53 3.3.2. Danh sách các chức năng ............................................................................ 53 3.3.3. Giao diện chương trình ............................................................................... 53 3.3.4. Kết quả thử nghiệm..................................................................................... 55 KẾT LUẬN .................................................................................................................. 57 TÀI LIỆU THAM KHẢO QUYẾT ĐỊNH GIAO ĐỀ TÀI LUẬN VĂN (Bản sao) v DANH MỤC CÁC CHỮ VIẾT TẮT Tiếng Việt VB VB1 VB2 Văn bản Văn bản 1 Văn bản 2 Tiếng Anh ANN IDF kNN LLSF MLP NB Nnet SVM TBL TF WFTS Artificial Neural Network Inverse Document Frequency k Nearest Neighbor Linear Least Square Fit Multilayer Perceptron Naïve Bayes Nerual Network Support Vector Machine Transformation – Based Learning Term Frequency Weighted Finite-State Transducer vi DANH MỤC CÁC BẢNG Số hiệu bảng 2.1. 2.2. 2.3. 2.4. 2.5. 2.6. 2.7. 2.8. 3.1. 3.2. 3.3. 3.4. 3.5. 3.6. Tên bảng Một số từ dừng trong văn bản tiếng Việt Biểu diễn văn bản theo mô hình Logic Biểu diễn văn bản theo mô hình không gian vector Biểu diễn văn bản theo không gian vector Boolean Bảng Trainning Data Bảng Testing Data Kết quả phân lớp bằng cây quyết định Huấn luyện với thuộc tính phân lớp là buys computer. Danh sách chức năng của chương trình thử nghiệm 4 chủ đề và số lượng mẫu dùng trong tập thử nghiệm Kết quả thử nghiệm công văn Đoàn thanh niên Kết quả thử nghiệm công văn Tư pháp Kết quả thử nghiệm công văn Đảng Kết quả thử nghiệm công văn Công đoàn Trang 22 23 25 26 29 30 31 34 53 55 55 56 56 56 vii DANH MỤC CÁC HÌNH VẼ Số hiệu hình 1.1. 1.2. 1.3. 2.1. 2.2. 2.3. 2.4. 2.5. 3.1. 3.2. 3.3. 3.4. Tên hình Giai đoạn huấn luyện Giai đoạn phân lớp Đồ thị vô hướng mô tả CRF Mô hình đề xuất Cây quyết định Mô hình một nơron nhân tạo Mô hình một nơron nhân tạo với giá trị bias Sơ đồ khối mô tả luật học giám sát Mô hình đề xuất Giao diện chính chương trình Giao diện form huấn luyện Giao diện form phân loại Trang 4 4 12 19 29 36 37 39 45 54 54 55 1 MỞ ĐẦU 1. Tính cấp thiết của đề tài Trong thời đại bùng nổ Công nghệ thông tin hiện nay, phương thức sử dụng giấy tờ trong công việc đã dần được số hoá chuyển sang các dạng công văn lưu trữ trên máy tính. Bởi nhiều tính năng ưu việt của tài liệu số như: cách lưu trữ gọn nhẹ, thời gian lưu trữ lâu dài, tiện dụng trong trao đổi đặc biệt là qua Internet, dễ dàng sửa đổi… nên ngày nay, số lượng công văn số tăng lên một cách chóng mặt. Cùng với sự gia tăng về số lượng công văn, nhu cầu tìm kiếm công văn cũng tăng theo. Với số lượng công văn đồ sộ thì việc có một công cụ phân loại công văn là một nhu cầu thực sự cần thiết. Hằng năm, tại Ủy ban nhân dân xã Hòa Phú tiếp nhận và chuyển đi số lượng lớn các loại công văn, khi tra cứu, sử dụng lại mất rất nhiều thời gian, công sức. Chính vì vậy, để hỗ trợ văn thư có được một công cụ quản lý công văn một cách thuận tiện, chính xác, tiết kiệm thời gian cũng như ứng dụng công nghệ thông tin vào công tác quản lý Văn thư – Lưu trữ, tôi thực hiện đề tài: "Xây dựng ứng dụng phân loại công văn tại Ủy ban nhân dân xã Hòa Phú”. 2. Mục tiêu và nhiệm vụ 2.1. Mục tiêu Mục tiêu chính của đề tài này là xây dựng ứng dụng tự động phân loại công văn theo các bộ phận tại Ủy ban nhân dân xã Hòa Phú. Ứng dụng này sẽ giúp Văn thư có thể chuyển số lượng lớn công văn đến các bộ phận để kịp thời giải quyết công việc khi chưa đọc văn bản và giúp lập hồ sơ công việc theo các bộ phận vào cuối năm, giúp tiết kiệm thời gian, nhằm tin học hóa bộ phận Văn thư. 2.2. Nhiệm vụ Để hoàn thành mục tiêu trên, nhiệm vụ nghiên cứu của đề tài gồm: - Nghiên cứu các phương pháp phân loại văn bản tiếng Anh. - Nghiên cứu các phương pháp phân loại văn bản tiếng Việt. - Xây dựng ứng dụng phân loại công văn dựa trên phương pháp mạng neural kết hợp phương pháp cây quyết định. Thử nghiệm chương trình và đánh giá kết quả. 3. Đối tượng và phạm vi nghiên cứu 3.1. Đối tượng Đối tượng nghiên cứu của luận văn gồm: - Hệ thống công văn Ủy ban nhân dân xã Hòa Phú. - Các phương pháp phân loại văn bản tiếng Anh. - Các phương pháp phân loại văn bản tiếng Việt. - Phân loại văn bản tiếng Anh sử dụng phương pháp mạng neural kết hợp phương pháp cây quyết định. 2 - Phân loại văn bản tiếng Việt sử dụng phương pháp mạng neural kết hợp phương pháp cây quyết định 3.2. Phạm vi nghiên cứu Trong khuôn khổ của luận văn, tôi nghiên cứu và xây dựng ứng dụng phân loại công văn theo các bộ phận như: công văn Đoàn thanh niên, công văn Tư pháp, công văn Đảng, công văn Công đoàn. Ứng dụng phân loại các công văn bằng file word và được xây dựng trên môi trường máy tính đơn. 4. Phương pháp nghiên cứu Đối với phương pháp nghiên cứu, tôi sử dụng hai phương pháp đó là nghiên cứu tài liệu và nghiên cứu thực nghiệm. Đối với phương pháp nghiên cứu tài liệu, tôi tập trung nghiên cứu cơ sở lý thuyết về phân loại văn bản, các phương pháp phân loại văn bản tiếng Anh, các phương pháp phân loại văn bản tiếng Việt, nghiên cứu tài liệu phân loại văn bản tiếng Anh sử dụng phương pháp mạng nerual kết hợp phương pháp cây quyết định, nghiên cứu ngôn ngữ lập trình Java. Đối với phương pháp nghiên cứu thực nghiệm, tôi sử dụng ngôn ngữ lập trình Java xây dựng ứng dụng phân loại công văn tiếng Việt. 5. Bố cục đề tài Luận văn được tổ chức thành ba chương với nội dung chính của các chương được giới thiệu như dưới đây: CHƯƠNG 1: Cơ sở lý thuyết trình bày khái niệm chung về phân loại văn bản; đặc điểm của tiếng Anh, tiếng Việt; các phương phân pháp phân loại văn bản tiếng Anh và tiếng Việt. CHƯƠNG 2: Đề xuất giải pháp trình bày cách phân loại văn bản loại văn bản bằng cách sử dụng phương pháp mạng nerual kết hợp phương pháp cây quyết định. CHƯƠNG 3: Xây dựng ứng dụng và thực nghiệm trình bày việc thực hiện demo và triển khai trên thực tế chương trình Xây dựng ứng dụng phân loại công văn tại Ủy ban nhân dân xã Hòa Phú bằng phương pháp mạng nerual kết hợp phương pháp cây quyết định. 6. Tổng quan tài liệu tham khảo Tài liệu tham khảo được sử dụng trong luận văn gồm có các bài báo, giáo trình, các luận văn của các học viên các lớp cao học ở các trường. Một số tài liệu tham khảo về các phương pháp phân loại văn bản [11] [12] [15][17][18]. Tài liệu tham khảo về xử lý ngôn ngữ tự nhiên [4]. 3 Chương 1 CƠ SỞ LÝ THUYẾT Phân loại văn bản là một trong nhiều lĩnh vực được chú ý và đã được nghiên cứu trong những năm gần đây. Trong chương này, tôi sẽ giới thiệu về phân loại văn bản, các phương pháp phân loại văn bản tiếng Anh, các phương pháp phân loại văn bản tiếng Việt. 1.1. Phân loại văn bản 1.1.1. Khái niệm văn bản Theo nghĩa rộng, văn bản được hiểu là vật mang tin được ghi bằng ký hiệu hay bằng ngôn ngữ, nghĩa là bất cứ phương tiện nào dùng để ghi nhận và truyền đạt thông tin từ chủ thể này đến chủ thể khác. Theo nghĩa hẹp, văn bản được hiểu là các tài liệu, giấy tờ, hồ sơ được hình thành trong quá trình hoạt động của các cơ quan, tổ chức. Theo nghĩa này, các loại giấy tờ dùng để quản lý và điều hành các hoạt động của cơ quan, tổ chức như chỉ thị, thông tư, nghị quyết, quyết định, đề án công tác, báo cáo… đều được gọi là văn bản. Ngày nay, khái niệm được dùng một cách rộng rãi trong hoạt động của các cơ quan, tổ chức. Khái niệm văn bản dùng trong tài liệu này cũng được hiểu theo nghĩa hẹp nóitrên. Dữ liệu văn bản chia thành hai loại: dạng phi cấu trúc và dạng bán cấu trúc. Dạng phi cấu trúc: là dạng văn bản chúng ta sử dụng hằng ngày được thể hiện dưới dạng ngôn ngữ tự nhiên của con người và không có một cấu trúc định dạng cụ thểnào. Ví dụ: các văn bản lưu dưới dạng tệp tin .TXT, .DOC. Dạng bán cấu trúc là các loại văn bản không được lưu trữ dưới dạng các bản ghi chặt chẽ mà được tổ chức qua các thẻ đánh dấu để thể hiện nội dung chính của vănbản. Ví dụ: dạng tệp tin HTML, email, … Trong luận văn này quan tâm xử lý dữ liệu các văn bản ở dạng phi cấu trúc biểu diễn dưới dạng tệp tin .TXT. 1.1.2. Phân loại văn bản Phân loại văn bản là một trong những phần quan trọng của việc khai phá dữ liệu văn bản, khá nhiều các hệ thống phân loại văn bản sử dụng kỹ thuật dựa trên tri thức (knowledge based) hoặc dựa trên các luật được xây dựng sẵn để tạo thành một tập hợp các quy tắc logic để hiểu và phân loại văn bản. Mỗi loại (hay còn gọi là lớp –class) tương đương với một chủ đề ví dụ “thể thao”, “chính trị” hay “nghệ thuật”. Nhiệm vụ phân loại được bắt đầu xây dựng từ một tập các văn bản D = {d1,d2,..,dn} được gọi là tập huấn luyện và trong đó các tài liệu di được gán nhãn cj với cjthuộc tập các chủ đề C={c1,c2,...,cm}. Nhiệm vụ tiếp theo đó là xác định được mô hình phân loại 4 mà có thể gán đúng lớp để một tài liệu dk bất kỳ có thể phân loại chính xác vào một trong những chủ đề của tập chủ đề C. Khái niệm [Phân loại văn bản]: Phân loại văn bản là nhiệm vụ gán một văn bản dj vào một chủ đề ck thích hợp thuộc tập chủ đề C = {c1,c2,...,cm}theo đúng nội dung của văn bản đó Để giải bài toán này đã có rất nhiều phương pháp được đưa ra như: thuật toán Naive Bayes, KNN (K-Nearest-Neighbor), cây quyết định (Decision Tree), mạng Neuron nhân tạo (Artificial Neural Network) và SVM (Support Vector Machine)… 1.1.3. Mô hình tổng quát Có rất nhiều hướng tiếp cận bài toán phân loại văn bản đã được nghiên cứu như: tiếp cận bài toán phân loại dựa trên lý thuyết đồ thị, cách tiếp cận sử dụng lý thuyết tập thô, cách tiếp cận thống kê…Tuy nhiên, tất cả các phương pháp trên đều dựa vào các phương pháp chung là máy học đó là: học có giám sát, học không giám sát và học tăng cường. Vấn đề phân loại văn bản theo phương pháp thống kê dựa trên kiểu học có giám sát được đặc tả bao gồm 2 giai đoạn: giai đoạn huấn luyện và giai đoạn phân lớp. a. Giai đoạn huấn luyện Hình 1.1. Giai đoạn huấn luyện b. Giai đoạn phân lớp Hình 1.2. Giai đoạn phân lớp 5 1.2. So sánh đặc điểm tiếng Anh và tiếng Việt 1.2.1. Đặc điểm tiếng Anh và tiếng Việt a. Đối với tiếng Anh Trong tiếng Anh có những đặc điểm cơ bản như sau: - Là ngôn ngữ không đơn lập – loại hình biến cách hay còn gọi là loại hình chiết khuất. - Từ có biến đổi hình thái, ý nghĩa ngữ pháp nằm ở trong từ. - Phương thức ngữ pháp chủ yếu là phụ tố. - Kết hợp giữa các hình vị là chặt chẽ, khó xác định, được nhận diện bằng khoảng trắng hoặc dấu câu. - Hiện tượng cấu tạo bằng từ ghép thêm phụ tố vào từ gốc là rất phổ biến. b. Đối với tiếng Việt Trong tiếng Việt có những đặc điểm cơ bản như sau: - Là ngôn ngữ đơn lập hay còn gọi là loại phi hình thái, không biến hình, đơn âm tiết. - Từ không biến đổi hình thái, ý nghĩa ngữ pháp nằm ngoài từ. - Phương thức ngữ pháp chủ yếu: trật tự từ và hư từ. - Ranh giới từ không được xác định mặc nhiên bằng khoảng trắng - Tồn tại loại từ đặc biệt “từ chỉ loại” hay còn gọi là phó danh từ chỉ loại kèm theo với danh từ. - Có hiện tượng nói láy và nói lái trong tiếng Việt. 1.2.2. Nhận xét Từ những đặc điểm của tiếng Anh và đặc điểm của tiếng Việt, ta có những nhận xét như sau: - Tiếng Việt là loại hình phi hình thái nên việc phân loại từ (danh từ, động từ, tính từ,…) và ý nghĩa từ rất khó khăn, cho dù có sử dụng từ điển. - Việc tiền xử lý văn bản sẽ thêm phức tạp với phần xử lý các hư từ, phụ từ, từ láy, … - Phương thức ngữ pháp chủ yếu là trật tự từ nên nếu áp dụng phương pháp tính xác suất xuất hiện của từ có thể không chính xác như mong đợi. - Ranh giới từ không được xác định mặc định bằng khoảng trắng. Điều này khiến cho việc phân tích hình thái (tách từ) tiếng Việt trở nên khó khăn. Việc nhận diện giới từ là quan trọng và làm tiền đề cho các xử lý tiếp theo sau đó như: kiểm tra lỗi chính tả, gán nhãn từ loại, thống kê tần suất từ. - Vì tiếng Anh và tiếng Việt có những đặc điểm khác biệt nên chúng ta không thể áp dụng y nguyên các thuật toán của tiếng Anh cho tiếng Việt. 6 1.3. Các phương pháp phân loại văn bản “Việc phân loại văn bản tự động là việc gán nhãn phân loại 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”.[19] Từ trước đến nay, phân loại văn bản trong tiếng Anh đã có rât nhiều công trình nghiên cứu và đạt được kết quả đáng khích lệ. Có nhiều phương pháp phân loại văn bản. Mỗi phương pháp phân loại văn bản đều có cách tính toán khác nhau, tuy nhiên, nhìn một cách tổng quan thì các phương pháp sẽ dựa trên thông tin về sự xuất hiện của từ trong văn bản để biểu diễn văn bản thành dạng vector; sau đó, tùy từng phương pháp mà ta sẽ áp dụng công thức và phương thức tính toán khác nhau để thực hiện phân loại. 1.3.1. Phương pháp Naïve Bayes Naïve Bayes (NB) là phương pháp phân loại dựa vào xác suất được sử dụng rộng rãi trong lĩnh vực máy học và nhiều lĩnh vực khác như trong các công cụ tìm kiếm, các bộ lọc mail, … [15] Ý tưởng cơ bản của cách tiếp cận này là sử dụng xác suất có điều kiện giữa từ hoặc cụm từ và chủ đề để dự đoán xác suất chủ đề của một văn bản cần phân loại. Điểm quan trọng của phương pháp này chính là ở chỗ giả định rằng sự xuất hiện của tất cả các từ trong văn bản đều độc lập với nhau. Như thế NB không tận dụng được sự phụ thuộc của nhiều từ vào một chủ đề cụ thể. Chính giả định đó làm cho việc tính toán NB hiệu quả và nhanh chóng hơn các phương pháp khác với độ phức tạp theo số mũ vì nó không sử dụng cách kết hợp các từ để đưa ra phán đoán chủ đề. Mục đích chính là làm sao tính được xác suất Pr(Cj , d’), xác suất để văn bản d’nằm trong lớp Cj . Theo luật Bayes, văn bản d’ sẽ được gán vào lớp Cj nào có xác suất Pr(Cj , d’) cao nhất. Công thức để tính Pr(Cj , d’) như sau: Với: - TF(wi , d’) là số lần xuất hiện của từ wi trong văn bản d’. - |d’| là số lượng các từ trong văn bản d’. - Wi là một từ trong không gian đặc trưng F với số chiều là |F|. - Pr(Cj) được tính dựa trên tỷ lệ phần trăm của số văn bản mỗi lớp tương ứng. 7 Ngoài ra còn có các phương pháp Naïve Bayes khác có thể kể ra như ML Naïve Bayes, MAP Naïve Bayes, Expected Naïve Bayes. Nói chung Naïve Bayes là một công cụ rất hiệu quả trong một số trường hợp. Kết quả có thể rất xấu nếu dữ liệu huấn luyện nghèo nàn và các tham số dự đoán (như không gian đặc trưng) có chất lượng kém. Nhìn chung, đây là một thuật toán phân loại tuyến tính thích hợp trong phân loại văn bản nhiều chủ đề. NB có ưu điểm là cài đặt đơn giản, tốc độ thực hiện thuật toán nhanh, dễ dàng cập nhật dữ liệu huấn luyện mới và có tính độc lập cao với tập huấn luyện. 1.3.2. Phương pháp k Nearest Neighbor K-Nearest Neighbor là phương pháp truyền thống khá nổi tiếng theo hướng tiếp cận thống kê đã được nghiên cứu trong nhiều năm qua. KNN được đánh giá là một trong những phương pháp tốt nhất được sử dụng từ những thời kỳ đầu trong nghiên cứu về phân loại văn bản. Ý tưởng của phương pháp này đó là khi cần phân loại một văn bản mới,thuật toán sẽ xác định khoảng cách (có thể áp dụng các công thức về khoảngcách như Euclide, Cosine, Manhattan, …) của tất cả các văn bản trong tập huấnluyện đến văn bản này để tìm ra K văn bản gần nhất, gọi là K Nearest Neighbor– K láng giềng gần nhất, sau đó dùng các khoảng cách này đánh trọng số cho tấtcả các chủ đề. Khi đó, trọng số của một chủ đề chính là tổng tất cả cá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 giá trị trọng số giảm dần và các chủ đề có trọng số cao sẽ được chọn làm chủ đề của văn bản cần phân loại.[18] Trọng số của chủ đề cj đối với văn bản x được tính như sau: 8 Trong đó: y(di, c) thuộc {0,1}, với: - y = 0: văn bản di không thuộc chủ đề cj. - y = 1: văn bản di thuộc chủ đề cj. sim(x, d): độ giống nhau giữa văn bản cần phân loại x và văn bản d. Chúng ta có thể sử dụng độ đo Cosine để tính khoảng cách. -bj là ngưỡng phân loại chủ đề cj được tự động học sử dụng một tập văn bản hợp lệ được chọn ra từ tập huấn luyện. Để chọn được tham số k tốt nhất cho thao tác phân loại, thuật toán cần được chạy thử nghiệm trên nhiều giá trị K khác nhau, giá trị K càng lớn thì thuật toán càng ổn định và sai sót càng thấp. 1.3.3. Phương pháp Support Vector Machine Máy học vector hỗ trợ (SVM) là một giải thuật máy học dựa trên lý thuyết học thống kê do Vapnik và Chervonenkis xây dựng. [11] Ý tưởng chính của thuật toán này là cho trước một tập huấn luyện được biểu diễn trong không gian vector 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 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 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 lớp đế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. Mục đích thuật toán SVM tìm ra được khoảng cách biên lớn nhất để tạo kết quả phân lớp tốt. [2] Bài toán cơ bản của SVM là bài toán phân loại hai lớp: Cho trước n điểm trong không gian d chiều, mỗi điểm thuộc vào một lớp ký hiệu là +1 hoặc -1, mục đích của giải thuật SVM là tìm một siêu phẳng (hyperplane) phân hoạch tối ưu cho phép chia các điểm này thành hai phần sao cho các điểm cùng một lớp nằm về một phía với siêu phẳng này. Có thể nói 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 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ố khi phân loại là thấp nhất, nghĩa là kết qủa phân loại sẽ cho kết quả tốt nhất. Phương trình siêu phẳng chứa vector di trong không gian như sau: 9 Như thế vector h(di) biểu diễn sự phân lớp của vector di vào hai lớp. Gọi Yi mang giá trị +1 hoặc -1, khi đó Yi = +1 văn bản tương ứng với vector di thuộc lớp (+) và ngược lại nó sẽ thuộc vào lớp (-). Khi này để có siêu mặt phẳng h, ta sẽ giải bài toán sau: Để có siêu phẳng h ta sẽ phải giải bài toán sau: Chúng ta thấy rằng SVM là mặt phẳng quyết định chỉ phụ thuộc vào các vector hỗ trợ có khoảng cách đến mặt phẳng quyết định là 1/wi. Khi các điểm khác bị xóa đi thì thuật toán vẫn cho kết quả giống như ban đầu. Chính đặc điểm này làm cho SVM khác với các thuật toán khác như KNN, LLSF, Nnet, NB vì tất cả dữ liệu trong tập huấn luyện đều được dùng để tối ưu hóa kết quả. 1.3.4. Phương pháp Linear Least Square Fit Linear Least Square Fit (LLSF) là một các tiếp cận ánh xạ được phát triển bởi Yang và Chute vào năm 1992. Đầ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. Ý tưởng của LLSF là 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 vector đầu vào và đầu ra như sau: - Vector đầu vào là một văn bản bao gồm các từ và trọng số. -Vector đầ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 vector đầu vào. Giải phương trình các cặp vector đầu vào, đầu ra chúng ta sẽ thu được ma trận đồng hiện của hệ số hồi quy của từ và chủ đề. Phương pháp này sử dụng công thức: 10 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 vector đầ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 vector 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. Nhờ đặ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. 1.3.5. Phương pháp Centroid – based vector Là một phương pháp phân loại đơn giản, dễ cài đặt và tốc độ nhanh do có độ phức tạp tuyến tính O(n). Ý tưởng của cách tiếp cận này là mỗi lớp trong dữ liệu huấn luyện sẽ đượcbiểu diễn bằng một vector trọng tâm. Việc xác định lớp của một văn bản bất kỳsẽ thông qua việc tìm vector trọng tâm nào gần với vector biểu diễn văn bản thứ nhất. Lớp của văn bản chính là lớp mà vector trọng tâm đại diện và khoảng cách được xác định theo độ đo Cosine. Chúng ta có công thức tính vector trọng tâm của lớp i: Độ đo khoảng cách giữa vector x và vector Ci: Trong đó: - x là vector văn bản cần phân loại. - {i} là tập hợp các văn bản thuộc chủ đề Ci. Chủ đề của vector x là Cx thỏa mãn cox (x, Cx) = arg max (cos(x,Ci)). 1.3.6. Nhận xét Các thuật toán phân loại trên từ thuật toán phân loại hai lớp (SVM) đến cácthuật toán phân loại đa lớp (KNN) đều có điểm chung là yêu cầu văn bản phải được biểu diễn dưới dạng vector đặc trưng. Ngoài ra các thuật toán như KNN,NB, LLSF đều phải sử dụng các ước lượng tham số và ngưỡng tối ưu khi phân loại văn bản, trong khi 11 thuật toán SVM có thể tự xác định các tham số tối ưu nàytrong quá trình thực hiện thuật toán. Xét về mặt thời gian, các phương pháp có thời gian huấn luyện khác nhau, các phương pháp KNN, NB, LLSF có thời gian huấn luyện và phân loại văn bản nhanh hơn so với các thuật toán còn lại, đồngthời dễ dàng cài đặt hơn. 1.4. Các phương pháp tách từ tiếng Việt Từ các đặc điểm của tiếng Việt, ta thấy việc xác định ranh giới từ trong văn bản tiếng Việt là một thách thức trong xử lý ngôn ngữ tự nhiên nói chung và phân loại văn bản nói riêng. 1.4.1. Phương pháp Conditional Random Field CRFs là mô hình trạng thái tuyến tính vô hướng (máy trạng thái hữu hạn đượ huấn luyện có điều kiện) và tuân theo tính chất Markov thứ nhất. CRFs đã được chứng minh thành công cho các bài toán gán nhãn như tách từ, gán nhãn cụm từ, xác định thực thể, gán nhãn cụm danh từ, etc. Định nghĩa CRF: Kí hiệu X là biến ngẫu nhiên có tương ứng với chuỗi dữ liệu cần gán nhãn và Y là biến ngẫu nhiên tương ứng với chuỗi nhãn. Mỗi thành phần Yi của Y là một biến ngẫu nhiên nhận trá trị trong tập hữu hạn các trạng thái S. Ví dụ trong bài toán phân đoạn từ, X nhận giá trị là các câu trong ngôn ngữ tự nhiên, còn Y là chuỗi nhãn tương ứng với các câu này. Mỗi thành phần Yi của Y là một nhãn xác định phạm vi của một từ trong câu (bắt đầu một từ, ở trong một từ và kết thúc một từ). Cho một đồ thị vô hướng không có chu trình G = (V, E), trong đó E là tập các cạnh vô hướng của đồ thị, V là tập các đỉnh của đồ thị sao cho Y = { Yv | v∈V}. Nói cách khác là tồn tại ánh xạ một – một giữa một đỉnh đồ thị và một thành phần Yv của Y. Nếu mỗi biến ngẫu nhiên Yv tuân theo tính chất Markov đối với đồ thị G – tức là xác suất của biến ngẫu nhiên Yv cho bởi X và tất cả các biến ngẫu nhiên khác Y {u | u ≠ v, {u, v} ∈V}. bằng xác suất của biến ngẫu nhiên Yv cho bởi X và các biến ngẫu nhiên khác tương ứng với các đỉnh kề với đỉnh v trong đồ thị: Như vậy, một CRF là một trường ngẫu nhiên phụ thuộc toàn cục vào chuỗi quan sát X. Trong bài toán tách từ nói riêng và các bài toán xử lý dữ liệu dạng chuỗi nói chung, thì đồ thì G đơn giản chỉ là dạng chuỗi, V= {1, 2,… m}, E = {(i, i+1)} Kí hiệu X= (X1, X2, ..., Xn) và Y = (Y1, Y2,…, Yn) thì mô hình đồ thị G có dạng nhưhình: 12 Hình 1.3. Đồ thị vô hướng mô tả CRF Gọi C là tập các đồ thị con đầy đủ của G. Vì G có dạng chuỗi nên đồ thị con đầy đủ thực ra chỉ là một đỉnh hoặc một cạnh của đồ thị G. Áp dụng kết quả của Hammerley - Clifford [13] cho các trường ngẫu nhiên Markov thì phân phối của chuỗi nhãn Y với chuỗi quan sát X cho trước có dạng: Trong đó ΨA gọi là hàm tiềm năng, nhận giá trị thực - dương. Lafferty xác định hàm tiềm năng này dựa trên nguyên lý cực đại entropy. Việc xác định một phân phối theo nguyên lý cực đại entropy có thể hiểu là ta phải xác định một phân phối sao cho phân phối đó tuân theo mọi giải thiết suy ra từ thực nghiệm, ngoài ra không đưa thêm bất kì giả thiết nào khác” và gần nhất với phân phối đều. Entropy là độ đo thể hiện tính không chắc chắn, hay độ không đồng đều của phân phối xác suất. Một phân phối xác suất có Entropy càng cao thì phân phối của nó càng đều. Độ đo entropy điều kiện H(Y|X) được cho bởi công thức: Với p(x,y) là phân phối thực nghiệm của dữ liệu. Theo cách trên, Lafferty đã chỉ ra hàm tiềm năng của mô hình CRFs có dạng: Trong đó λk là thừa số lagrangian ứng với thuộc tính fk. Ta cũng có thể xem như λk là trọng số xác định độ quan trọng của thuộc tính fk trong chuỗi dữ liệu. Có hai loại thuộc tính là thuộc tính chuyển (ký hiệu là f) và thuộc tính trạng thái (ký hiệu là g) tùy thuộc vào A là một đỉnh hay một cạnh của đồ thị. Thay công thức hàm tiềm năng vào công thức (3.1) và thêm thừa số chuẩn hóa để đảm bảo thỏa mãn điều kiện xác suất ta được: 13 Ở đây, x là chuỗi dữ liệu, y là chuỗi trạng thái tương ứng. f k(yi-1,yi,x) là thuộc tính của chuỗi quan sát và các trạng thái tương ứng với vị trí thứ i và i-1 trong chuỗi trạng thái. gk(yi,x) là thuộc tính của chuỗi quan sát và trạng thái ứng với trí thứ i trong chuỗi trạng thái. Các thuộc tính này được rút ra từ tập dữ liệu và có giá trị cố định. Ví dụ: Vấn đề của ta bây giờ là phải ước lượng được các tham số (λ1, λ2,…; µ1, µ2,…) từ tập dữ liệu huấn luyện. Huấn luyện CRF Việc huấn luyện mô hình CRF thực chất là đi tìm tập tham số của mô hình. Kỹ thuật được sử dụng là làm cực đại độ đo likelihood giữa phân phối mô hình và phân phối thực nghiệm. Vì thế việc huấn luyện mô hình CRFs trở thành bài toán tìm cực đại của hàm logarit của hàm likelihood. Giả sử dữ liệu huấn luyện gồm một tập N cặp, mỗi cặp gồm một chuỗi quan sát và một chuỗi trạng thái tương ứng, D = {(x(1), y(1))}∀i = 1…N. Hàm log-likelihood có dạng sau: Ở đây θ(λ1, λ2,…, µ1, µ2,…) là các tham số của mô hìnhvà p(x|y)là phân phối thực nghiệm đồng thời của x,y trong tập huấnluyện. Thay p(y|x) của CRFs trong công thức (3.4) vào trên ta được Ở đây, (λ1, λ2, λ3,…, λn) và (µ1, µ2, µ3,…, µm) là các vector tham số của mô hình, f là vector các thuộc tính chuyển, g là vector các thuộc tính trạng thái. Người ta đã chứng minh được hàm log-likelihood là một hàm lõm và liên tục trong toàn bộ không gian của tham số. Vì vậy ta có thể tìm cực đại hàm log-likelihood 14 bằng phương pháp vector gradient. Mỗi thành phần trong vector gradient sẽ được gán bằng0: Việc thiết lập phương trình trên bằng 0 tương đương với việc đưa ra ràng buộc với mô hình là: giá trị kỳ vọng của thuộc tính fk đối với phân phối mô hình phải bằng giá trị kỳ vọng của thuộc tính fk đối với phân phối thực nghiệm. Sau khi tìm được mô hình CRF từ tập dữ liệu huấn luyện, nhiệm vụ của ta lúc này là làm sao dựa vào mô hình đó để gán nhãn cho chuỗi dữ liệu quan sát, điều này tương đương với việc làm cực đại phân phối xác suất giữa chuỗi trạng thái y và dữ liệu quan sát x. Chuỗi trạng thái y* mô tả tốt nhất chuỗi dữ liệu quan sát x sẽ là nghiệm của phương trình y* = argmax{p(x|y)}. Chuỗi y* có thể xác định được bằng thuật toán Viterbi. Gọi S là tập tất cả trạng thái có thể, ta có |S| =s m. X t một tập hợp các ma trận c m×m kí hiệu { Mi(x) | i= 0,2…n-1} được định nghĩa trên từng cặp trạng thái y, y' ∈S , như sau: Bằng việc đưa thêm hai trạng thái y-1 và yn vào trước và sau chuỗi trạng thái. Coi như chúng ứng với trạng thái ‘start” và “end”, phân phối xác suất có thể viết là: Ở đây Z(x) là thừa số chuẩn hóa được đưa thêm vào và có thể tính được dựa vào các Mi, nhưng vấn đề ta quan tâm là cực đại hóa p(y|x) nên không cần thiết phải tínhZ(x). Như vậy ta chỉ cần cực đại hóa tích n+1 phần tử trên. Tư tưởng chính của thuật toán Viterbi là tăng dần chuỗi trạng thái tối ưu bằng việc quét các ma trận từ vị trí 0 cho đến vị trí n. Tại mỗi bước i ghi lại tất cả các chuỗi tối ưu kết thúc bởi trạng thái y với y∈S (ta kí hiệu là y* (y)) (*y yi) và tích tương ứngPi(y):