Tài liệu Nghiên cứu các phương pháp phân lớp văn bản và ứng dụng xây dựng phần mềm phân loại văn bản hành chính tại ;sở thông tin và truyền thông đà nẵng

NGHIÊN CỨU CÁC PHƯƠNG PHÁP PHÂN LỚP VĂN BẢN VÀ ỨNG DỤNG XÂY DỰNG PHẦN MỀM PHÂN LOẠI VĂN BẢN HÀNH CHÍNH TẠI SỞ THÔNG TIN VÀ TRUYỀN THÔNG THÀNH PHỐ ĐÀ NẴNG Học viên: Lê Trung Nhựt Mã số: 60.48.01 Khóa: 31 Chuyên ngành: Khoa học máy tính Trường Đại học Bách khoa-ĐHĐN 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),… Luận văn tập trung nghiên cứu các phương pháp phân loại văn bản tiếng Việt hiệu quả hơn. Bước đầu thử nghiệm trên các văn bản hành chính tại sở Thông tin và Truyền thông thành phố Đà Nẵng đã cho những kết quả có độ chính xác cao so với yêu cầu. Từ khóa – Khai phá văn bản, Phân loại văn bản, SVM, . RESEARCH ON THE METHODS OF CLARIFYING DOCUMENTS, AND THE APPLICATION FOR CONSTRUCTION OF CLARIFICATION SOFTWARE OF ADMINISTRATIVE DOCUMENTS AT DEPARTMENT OF INFORMATION AND COMMUNICATION OF ĐA NANG CITY 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 on the similarity of the document with labeled documents in the training set. Many machine learning and data mining methods have been applied in text document classification such as: Naive Bayes, decision tree, k – Nearest neighbor, neural network,…The thesis focuses on different approaches to Vietnamese text classification problem and methods that help improve the quality of the classification result. These approaches and methods have been implemented and tested against documents gathered from Da Nang Department of Information and Communications, giving promissing result with high accuracy Key words – Text mining, Text classification/Categorization, SVM MỤC LỤC LỜI CAM ĐOAN MỤC LỤC DANH MỤC CÁC BẢNG DANH MỤC CÁC HÌNH MỞ ĐẦU ........................................................................................................................ 1 1. Tính cấp thiết của đề tài ..................................................................................... 1 2. Mục tiêu nghiên cứu .......................................................................................... 2 3. Đối tượng và phạm vi nghiên cứu ..................................................................... 2 4. Phương pháp nghiên cứu ................................................................................... 3 5. Bố cục đề tài ...................................................................................................... 3 6. Tổng quan tài liệu nghiên cứu ........................................................................... 4 CHƯƠNG 1. NGHIÊN CỨU TỔNG QUAN ............................................................. 5 1.1. TỔNG QUAN VỀ PHÂN LỚP DỮ LIỆU ......................................................... 5 1.1.1. Tổng quan về bài toán phân lớp dữ liệu ................................................... 5 1.1.2. Tổng quan về quá trình phân lớp dữ liệu .................................................. 5 1.2. TỔNG QUAN VỀ PHÂN LỚP VĂN BẢN ....................................................... 6 1.2.1. Khái niệm .............................................................................................. 6 1.2.2. Thực trạng của vấn đề ............................................................................. 8 1.2.3. Tổng quan về phương pháp phân lớp văn bản .......................................... 8 1.2.4. Ứng dụng của việc phân lớp văn bản ....................................................... 9 1.2.5. Quá trình phân lớp văn bản ..................................................................... 9 1.2.6. Đánh giá máy phân lớp văn bản ............................................................ 10 1.2.7. Những yếu tố ảnh hưởng đến quá trình phân lớp .................................... 11 1.3. PHÁT BIỂU VỀ BÀI TOÁN PHÂN LOẠI VĂN BẢN ................................... 12 1.3.1. Mô hình tổng quát ................................................................................ 12 1.3.2. Giai đoạn huấn luyện ............................................................................ 13 1.3.3. Giai đoạn phân lớp ............................................................................... 14 1.4. TỔNG QUAN VỀ TÌNH HÌNH NGHIÊN CỨU TRONG VÀ NGOÀI NƯỚC . 15 1.4.1. Tổng quan thế giới................................................................................ 15 1.4.2. Tổng quan trong nước........................................................................... 16 1.4.3. Giới thiệu các công trình nghiên cứu liên quan ...................................... 17 1.5. KẾT LUẬN CHƯƠNG 1 ................................................................................ 22 CHƯƠNG 2. ĐỀ XUẤT CÁC PHƯƠNG PHÁP ÁP DỤNG ................................. 23 2.1. PHÁT BIỂU BÀI TOÁN ................................................................................ 23 2.2. PHÂN TÍCH YÊU CẦU ĐỀ TÀI .................................................................... 24 2.3. MÔ HÌNH ĐỀ XUẤT ..................................................................................... 25 2.4. TIỀN XỬ LÝ VĂN BẢN ............................................................................... 25 2.4.1. Tách từ trong tiếng việt ......................................................................... 26 2.4.2. Một số phương pháp tách từ hiện nay .................................................... 27 2.4.3. So sánh các phương pháp tách từ tiếng Việt ........................................... 30 2.4.4. Loại bỏ từ dừng .................................................................................... 31 2.5. CHUYỂN ĐỔI VĂN BẢN TỪ DẠNG NGÔN NGỮ TỰ NHIÊN SANG MÔ HÌNH KHÔNG GIAN VECTOR ........................................................................... 31 2.5.1. Binary vector ....................................................................................... 32 2.4.2. TF-IDF vector ...................................................................................... 33 2.4.3. Độ tương đồng giữa các vector ............................................................. 34 2.5. CÁC PHƯƠNG PHÁP PHÂN LOẠI VĂN BẢN BẰNG HỌC MÁY............... 35 2.5.1. Thuật toán Support Vector Machine (SVM) .......................................... 35 2.5.2. Thuật toán K-Nearest Neighbor (kNN) .................................................. 38 2.5.3. Thuật toán Naϊve Bayers (NB) .............................................................. 39 2.5.4. Đề xuất áp dụng ................................................................................... 41 2.6. KẾT LUẬN CHƯƠNG 2 ................................................................................ 41 CHƯƠNG 3. XÂY DỰNG CHƯƠNG TRÌNH THỬ NGHIỆM ........................... 43 3.1. PHÁT TRIỂN MOUDLE CHƯƠNG TRÌNH .................................................. 43 3.1.1. Tiền xữ lý văn bản ................................................................................ 43 3.1.2. Vector hóa dữ liệu ................................................................................ 44 3.2. ỨNG DỤNG SVM VÀO BÀI TOÁN PHÂN LOẠI VĂN BẢN HÀNH CHÍNH TIẾNG VIỆT TẠI SỞ THÔNG TIN VÀ TRUYỀN THÔNG ĐÀ NẴNG ................ 45 3.3. XÂY DỰNG CHƯƠNG TRÌNH THỬ NGHIỆM ............................................ 48 3.3.1. Yêu cầu bài toán ................................................................................... 48 3.3.2. Danh sách chức năng ............................................................................ 48 3.3.3. Giao diện chương trình ......................................................................... 49 3.3.4. Kết quả thử nghiệm .............................................................................. 50 3.4. ĐÁNH GIÁ .................................................................................................... 52 3.5. KẾT LUẬN CHƯƠNG 3 ...................................................................................... 52 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ................................................................ 53 DANH MỤC TÀI LIỆU THAM KHẢO QUYẾT ĐỊNH GIAO ĐỀ TÀI LUẬN VĂN (Bản sao) DANH MỤC CÁC CHỮ VIẾT TẮT CRFs IDF kNN LDA LRMM NB SVD TBL TF WFST : Conditional Random Fields : Inverse Document Frequency : K-Nearest Neighbor : Latent Drichlet Allocation : Left Right Maximum Matching : Naϊve Bayers : Singular Value Decomposition : Transformation-Based Learning : Term Frequency : Weighted finite-state Transducer DANH MỤC CÁC BẢNG Số hiệu bảng Tên bảng Trang 1.1. Kết quả phân loại theo phương pháp vector hỗ trợ và cây 19 quyết định của Trần Cao Đệ và Phạm Nguyên Khang 1.2. Kết quả phân loại văn bản theo phương pháp Naïve Bayes 20 của Trần Thị Thu Thảo và Vũ Thị Chinh 1.3. Kết quả phân loại email Spam bằng Matlad của Shahar 22 Yifrah và Guy Lev 3.1. Danh sách chức năng cần có của chương trình thử nghiệm 48 3.2. 4 chủ đề và số lượng mẫu dùng trong tập thử nghiệm 50 3.3. Bảng kết quả kiểm chứng bộ phân lớp bằng máy học S3VM 50 3.4. Bảng kết quả kiểm chứng bộ phân lớp bằng K-Nearest Neighbor 51 3.5. Bảng kết quả kiểm chứng bộ phân lớp bằng Naϊve Bayers 51 3.6. So sánh hiệu quả phân loại văn bản S3VM với kNN và NB 51 DANH MỤC CÁC HÌNH Số hiệu Tên hình hình Trang 1.1. Mô hình tổng quan về bài toán phân lớp 5 1.2. Bài toán phân lớp văn bản 6 1.3. Sơ đồ biểu diễn quá trình phân lớp dữ liệu văn bản 10 1.4. Mô hình tổng quát 13 1.5. Mô hình giai đoạn huấn luyện 13 1.6. Chi tiết giai đoạn huấn luyện 14 1.7. Mô hình giai đoạn phân lớp 14 1.7. Mô hình chi tiết giai đoạn phân lớp 15 1.8. Phân loại văn bản của 18 1.9. Phân loại văn bản của 19 2.1. Mô hình đề xuất 25 2.2. Mô hình tách từ tiếng Việt 27 2.3. Minh họa hình học thuật toán SVM 36 3.1. Giao diện form Huấn luyện 49 3.2. Giao diện chính chương trình 49 1 MỞ ĐẦU 1. Tính cấp thiết của đề tài Cùng với sự phát triển chung của khoa học kỹ thuật và công nghệ thông tin đã đem đến cho con người khả năng tiếp cận với tri thức khoa học một cách nhanh chóng, cụ thể như: thư viện điện tử, cổng thông tin điện tử, báo mạng, các ứng dụng tìm kiếm…, đã giúp con người thuận tiện hơn trong việc trao đổi, cập nhật thông tin trên toàn cầu thông qua mạng Internet. Hệ thống dữ liệu số hoá ngày càng trở nên khổng lồ để phục vụ cho việc lưu trữ trao đổi thông tin, dữ liệu số hoá này rất đa dạng - nó có thể là các dữ liệu dưới dạng tập tin văn bản text, tập tin văn bản MS Word, tập tin văn bản PDF, mail, HTML .v.v. Các tập tin văn bản cũng được lưu trữ trên máy tính cục bộ hoặc được truyền tải trên intenet, cùng với thời gian và số lượng người dùng tăng nhanh thì các tập tin này ngày càng nhiều và đến một thời điểm nào đó số lượng tập tin này sẽ vượt quá tầm kiểm soát, do đó khi muốn tìm kiếm lại một văn bản nào đó, việc tìm kiếm sẽ rất khó khăn và phức tạp, đặc biệt là trong trường hợp người cần tìm kiếm không nhớ rõ các câu cần tìm chính xác trong văn bản. Hiện nay tin học hóa các hoạt động quản lý nhà nước đang ngày càng đặt biệt được chú trọng. Tại Việt Nam phần lớn các cơ quan hành chính nhà nước đang sử dụng các hệ thống phần mềm hỗ trợ văn bản và điều hành để xử lý hồ sơ văn bản, tại sở Thông tin và Truyền thông thành phố Đà Nẵng hằng năm việc nhận và chuyển đi số lượng lớn văn bản hành chính các loại, hệ thống lưu trữ cơ sở dữ liệu cho văn bản khá lớn và mỗi ngày càng phình to, khối lượng dữ liệu lớn khi có việc tìm lại các văn bản cần thiết sẽ mất khá nhiều thời gian công sức, vì nếu thực hện quá trình phân loại bằng thủ công sẽ tốn nhiều thời gian và chi phí. Vì vậy để nâng cao hiệu quả trong việc sử dụng các hệ thống phần mềm này, chúng ta cần phải xây dựng chức năng có khỏa năng phân loại tự động nhằm sắp xếp phân loại văn bản để quá trình tìm kiếm, truy xuất của người dùng được nhanh nhạy và dễ dàng hơn. Phân loại văn bản tự động là 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 Naive Bayes, cây quyết định, k–láng giềng gần nhất, mạng nơron,… những nghiên cứu gần đây, phương pháp phân loại văn bản sử dụng Máy vector hỗ trợ (SVM) được quan tâm và sử dụng nhiều trong những lĩnh vực phân loại. Phương pháp SVM ra đời từ lý thuyết học thống kê do Vapnik và Chervonenkis xây dựng và có nhiều tiềm năng phát triển về mặt lý thuyết cũng như ứng dụng trong thực tiễn. Những năm gần đây vấn đề phân loại văn bản tiếng Việt được nhiều cơ sở 2 nghiên cứu trong cả nước quan tâm. Một số công trình nghiên cứu cũng đạt được những kết quả khả quan. Các hướng tiếp cận bài toán phân loại văn bản đã được nghiên cứu bao gồm: hướng tiếp cận bài toán phân loại bằng 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ê, cách tiếp cận sử dụng phương pháp học không giám sát và đánh chỉ mục. Nhìn chung, những cách tiếp cận này đều cho kết quả chấp nhận được. Tuy nhiên SVM chưa được áp dụng một cách có hiệu quả vào phân loại văn bản tiếng Việt. Vì vậy với mục đích xây dựng mô hình và cải tiến phương pháp máy vector hỗ trợ SVM để nâng cao hiệu quả phân loại văn bản tiếng Việt là một công việc cấp thiết. Chính vì vậy, trong luận văn này, tập trung nghiên cứu các phương pháp nhằm phân loại văn bản tiếng Việt hiệu quả hơn. Nhận thấy đây là lĩnh vực mang tính khoa học cao. Vì vậy tôi đã chọn đề tài “Nghiên cứu các phương pháp phân lớp văn bản và ứng dụng xây dựng phần mềm phân loại văn bản hành chính tại Sở Thông tin và Truyền thong thành phố Đà Nẵng” là một việc làm không chỉ mang tính khoa học mà còn áp dụng vào thực tiễn. Đã có rất nhiều công trình nghiên cứu và ứng dụng thực tế dùng để thực hiện việc phân loại văn bản, tuy nhiên các ứng dụng đó cũng chưa thể đáp ứng hoàn toàn nhu cầu của người sử dụng, do vậy mà việc tìm kiếm, nghiên cứu các giải thuật, các phương pháp phân loại văn bản vẫn được tiếp tục nghiên cứu và hoàn thiện. 2. Mục tiêu nghiên cứu Mục tiêu chung của đề tài là nghiên cứu ứng dụng kỹ thuật học máy vào bài toán phân loại văn bản tiếng Việt. Mục tiêu cụ thể như sau: - Tập trung nghiên cứu một số kỹ thuật và phương pháp phân lớp văn bản, mô tả các yêu cầu chính yếu nhất của từng phương pháp và rút ra các ưu/khuyết điểm của từng phương pháp. - Nắm vững được các vấn đề liên quan đến phân loại văn bản gồm: các mô hình phân loại, quy trình thực hiện. Nghiên cứu các thuật toán xử lý văn bản, cách thức tương tác tài liệu, văn bản. - Ứng dụng các phương pháp trên để xây dựng chương trình phân loại văn bản tiếng Việt bước đầu thử nghiệm trên các văn bản thuộc sở Thông tin và Truyền thông thành phố Đà Nẵng. 3. Đối tượng và phạm vi nghiên cứu 3.1. Đối tượng nghiên cứu của đề tài - Các thuật toán phân loại, phân cụm dữ liệu trong cơ sở dữ liệu có cấu trúc và bán cấu trúc, phương pháp tách từ, tách câu trong các loại văn bản tiếng Việt. 3 - Một số hệ thống phân loại văn bản hiện có. - Hệ thống văn bản hành chính tại Sở Thông tin và Truyền thông Đà Nẵng - Ngôn ngữ lập trình python để xây dựng ứng dụng phân loại văn bản 3.2. Chúng tôi giới hạn phạm vi nghiên cứu trong luận văn này gồm: - Trong khuôn khổ của luận văn, học viên nghiên cứu và xây dựng ứng dụng phân loại văn bản thành các loại theo các bộ phận chức năng như: công nghệ thông tin, báo chí xuất bản, bưu chính viễn thông, an ninh thông tin. - Chỉ tập trung cho hệ thống phân loại văn bản tiếng việt. 4. Phương pháp nghiên cứu - Phương pháp tài liệu: Tập trung nghiên cứu cơ sở lý thuyết về các kỹ thuật phân lớp văn bản các tư liệu và thông tin liên quan chủ yếu được thu thập, tổng hợp từ các nguồn, các tạp chí khoa học. Chuyên ngành trong và ngoài nước, Internet. Các tài liệu có liên quan đến các nội dung nghiên cứu như: học máy, phân loại văn bản, phân loại văn bản tiếng Việt. - Phương pháp thực nghiệm: Nghiên cứu đánh giá thực nghiệm từng mô hình, phương pháp phân loại văn bản, từ đó so sánh, đánh giá với phương pháp được đề xuất. Ứng dụng xây dựng chương trình phân loại văn bản. - Phương pháp chuyên gia: Lấy ý kiến các chuyên gia, các giải pháp đề xuất và khảo sát ý kiến của người sử dụng. 5. Bố cục đề tài Nội dung chính của luận văn được trình bày trong 3 chương gồm: Chương 1: Nghiên cứu tổng quan Chương này trình bày các khái niệm và những nội dung cơ bản về bài toán phân lớp văn bản. Tìm hiểu các kết quả nghiên cứu tổng quan liên quan đến học máy, các phương pháp học máy, phân lớp dữ liệu và phân loại văn bản, tìm hiểu các quy trình phân loại văn bản tiếng Việt. Trên cơ sở nghiên cứu, đánh giá các vấn đề còn tồn tại, đề xuất những nội dung nghiên cứu trình bày trong các chương tiếp theo. Chương 2: Đề xuất phương pháp áp dụng Nội dung chương này tập trung phân tích, trình bày kiến thức nền tảng, cơ sở lý thuyết sử dụng trong luận văn, làm rõ một số giải pháp kỹ thuật liên quan, nêu khái quát đặc điểm các phương pháp được sử dụng tại mỗi bước của quy trình phân loại, qua đó định hướng áp dụng trong việc giải quyết bài toán phân loại văn bản. Kết quả nghiên cứu của chương là cơ sở để giải quyết bài toán phân loại văn bản tiếng Việt ở chương sau. Chương 3: Xây dựng chương trình thử nghiệm Chương này trình bày các áp dụng thuật toán trong việc phân loại văn bản, sử 4 dụng ngôn ngữ lập trình python để viết chương trình phân loại văn bản tại sở Thông tin và Truyền thông TP. Đà Nẵng. Thử nghiệm các kết quả thực nghiệm thu được khi thực hiện ở các phương pháp. Đưa ra một số nhận xét đánh giá kết luận. Trong phần kết luận, luận văn tóm tắt lại những công việc đã thực hiện trong thời gian qua, và kết quả đã đạt được, đồng thời cũng đề cập đến những điểm còn hạn chế của luận văn và đề ra phương hướng nghiên cứu trong thời gian tới. 6. Tổng quan tài liệu nghiên cứu Tài liệu tham khảo được sử dụng trong luận văn gồm 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, các bài báo khoa học công nghệ. 5 CHƯƠNG 1 NGHIÊN CỨU TỔNG QUAN 1.1. TỔNG QUAN VỀ PHÂN LỚP DỮ LIỆU 1.1.1. Tổng quan về bài toán phân lớp dữ liệu Bài toán phân lớp dữ liệu là quá trình phân lớp một đối tượng dữ liệu cụ thể vào một hoặc nhiều lớp dữ liệu, đã xác định trước thông qua một mô hình phân lớp, được xây dựng từ trước dựa trên một tập đối tượng dữ liệu thiết lập nhãn sẵn từ trước hay chúng ta vẫn thường gọi là tập huấn luyện. Quá trình phân lớp dữ liệu còn có thể được gọi với một tên khác là quá trình thiết lập nhãn cho các đối tượng dữ liệu. Nhiệm vụ chính của việc phân lớp dữ liệu là tạo ra mô hình phân lớp để khi có một đối tượng dữ liệu mới được đưa ra thì mô hình phân lớp dữ liệu sẽ xếp đối tượng dữ liệu đó vào lớp nào hay có thể coi là thiết lập nhãn cho đối tượng dữ liệu này. Trong thực tế phân lớp dữ liệu có rất nhiều bài toán khác nhau như bài toán phân lớp nhị phân, bài toán phân lớp đa trị,… Bài toán phân lớp nhị phân còn được hiểu là phân lớp đối tượng dữ liệu vào một trong hai lớp cho trước khác nhau thông qua việc xem xét đối tượng dữ liệu đó có hay không có các đặc tính phân loại được đặt ra theo quy ước của mô hình phân lớp. Bài toán phân lớp đa trị là bài toán phân lớp mà trong đó mỗi đối tượng dữ liệu trong tập dữ liệu được gán nhãn cũng như các đối tượng dữ liệu chưa được gán nhãn sau khi được phân lớp có thể được xếp vào hai lớp trở lên. Tiếp theo đây, nghiên cứu sẽ trình bày tổng quan về quá trình phân lớp dữ liệu và phương pháp phân lớp dữ liệu. 1.1.2. Tổng quan về quá trình phân lớp dữ liệu Hình 1.1. Mô hình tổng quan về bài toán phân lớp 6 Như hình trên thể hiện quá trình phân lớp dữ liệu được thực hiện qua hai bước chính: Bước 1: Thiết lập mô hình phân lớp: Mô hình phân lớp được tạo nên dựa trên việc phân tích các đối tượng dữ liệu trong tập huấn luyện. Các lớp được gán nhãn của tập dữ liệu được gán nhãn này được xác định thủ công từ trước, vì vậy phương pháp học này còn có thể được gọi với tên khác là phương pháp học có giám sát (supervised learning). Tại bước này, độ chính xác của mô hình cần được tính đến. Nếu độ chính xác của mô hình là chấp nhận được mô hình phân lớp sẽ được dùng để xác định nhãn cho các đối tượng chưa được gán nhãn. Trong quá trình đánh giá mô hình phân lớp, độ đo sẽ được sử dụng để đánh giá độ chất lượng của các tập phân lớp. Trong thực tế có nhiều phương pháp phân lớp dữ liệu để giải quyết các bài toán phân lớp tùy thuộc vào cách tạo ra mô hình phân lớp. Có thể kể đến một số phương pháp như Bayes, cây quyết định, SVM, K láng giềng gần nhất, .... Các phương pháp phân lớp phân biệt nhau thông qua bộ phân lớp. Bộ phân lớp còn được gọi với tên gọi khác là thuật toán phân lớp. Bước 2: Tiến hành phân lớp sử dụng mô hình phân lớp tạo ở bước 1: Thuật toán phân lớp có thể coi là ánh xạ từ miền dữ liệu sẵn có sang một miền giá trị cụ thể của nhãn lớp, dựa trên thuộc tính của các đối tượng dữ liệu. 1.2. TỔNG QUAN VỀ PHÂN LỚP VĂN BẢN 1.2.1. Khái niệm Phân lớp văn bản (Text classification) là quá trình gán nhãn (tên lớp/nhãn lớp) các văn bản ngôn ngữ tự nhiên một cách tự động vào một hoặc nhiều lớp cho trước. Hình 1.2. Bài toán phân lớp văn bản Thông thường, các lớp cho trước là các chủ đề nào đó, nhưng cũng có nhiều ứng dụng mà các lớp được thiết lập theo những tiêu chí khác, như phân lớp theo độ ưu tiên, phân lớp theo chủ đề… Hầu hết các bài toán này sẽ 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 7 là đọc từng văn bản và 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 lớp cực kỳ lớn như hiện nay thì việc phân lớp 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 của hai chuyên gia 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 lớp 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 lớp thống kê và kĩ thuật học máy như Naϊve Bayers, máy vector hỗ trợ (Support Vector Machines), K người láng giềng gần nhất, 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 lớp 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 lớp 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 lớp 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. Phân lớp 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 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 lớp văn bản là trong lĩnh vực hiểu văn bản. Phân lớp 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. Định nghĩa phân lớp văn bản : Phân lớp văn bản là nhiệm vụ đặt một giá trị boolean cho mỗi cặp (dj, ci) ∈ D × C , trong đó D là tập các văn bản và C = {c1 , c 2 ,...cc } là tập các lớp cho trước. Giá trị T (true) được gán cho cặp (dj, ci) có nghĩa là tài liệu dj thuộc lớp ci Giá trị F (false) tức là tài liệu dj không thuộc lớp ci 8 Hay nói cách khác phân lớp văn bản là một bài toán tìm hàm Φ : D × C → {T , F } 1 2 trong đó D là tập các văn bản và C = {c , c, ,...cc }là tập các lớp cho trước , hàm Φ : D × C → {T , F }. 1.2.2. Thực trạng của vấn đề Các phương thức giao dịch sử dụng giấy tờ trong thời đại hiện nay thì phương thức số dần đang thay thế các phương thức giao dịch truyền thống. Cụ thể việc số hoá các giấy tờ có thể hiểu như việc chuyển các dữ liệu dạng giấy tờ sang các định dạng số được lưu trữ trên máy tính hoặc truyền tải thông qua môi trường internet. Lượng dữ liệu văn bản được lưu trữ trực tuyến hiện nay đang gia tăng một cách chóng mặt do có nhiều ưu điểm như tiện dụng, gọn nhẹ và sự lưu trữ ổn định lâu dài, dễ dàng hiệu chỉnh cũng như truyền gửi. Song song với sự gia tăng số lượng văn bản thì nhu cầu khai thác tìm kiếm các dữ liệu văn bản cũng đang trở thành một nhu cầu thiết yếu trong thời điểm hiện tại. Trong cuộc sống hàng ngày, việc phân lớp các văn bản đa phần được thực hiện thủ công. Và dễ thấy được cách thức phân loại này tốn kém về mặt thời gian cũng như công sức của con người vì các văn bản rất lớn, để thực hiện phân lớp các văn bản theo cách thức này về lâu dài là một vấn đề không khả thi. Từ đó chúng ta có thể nhận thấy việc phân lớp văn bản tự động là một vấn đề bức thiết cần phải được giải quyết. Câu hỏi được đặt ra ở đây là phân lớp văn bản là gì? Phân lớp văn bản có thể được hiểu là việc phân lớp dữ liệu áp dụng đối với các dữ liệu văn bản, hay phân một văn bản vào một hay nhiều lớp văn bản thông qua một mô hình phân lớp được xây dựng dựa trên một tập hợp các văn bản thiết lập nhãn từ trước. Phân lớp văn bản hiện nay đang là một trong các lĩnh vực được quan tâm hàng đầu và hiện đã và đang được đầu tư nghiên cứu tương đối nhiều trong những năm gần đây trên khắp thế giới. 1.2.3. Tổng quan về phương pháp phân lớp văn bản Hiện nay, có rất nhiều các phương pháp dùng để phân lớp văn bản như phương pháp Bayes, sử dụng cây quyết định, k láng giềng gần nhất hay SVM. Thuật toán học máy thường được sử dụng để xây dựng mô hình phân lớp văn bản một cách tự động. Ngoài ra chúng ta còn có thể kể đến các phương pháp đặc biệt hơn dùng để phân lớp trong một số lĩnh vực. Ví dụ khi mô hình phân loại thấy xuất hiện một cụm từ trong văn bản thì hệ thống sẽ phân văn bản đó vào một lớp nào đó. Trong trường hợp các văn bản có số đặc trưng hơn không nhiều như vậy thì chúng ta đưa ra các phương pháp phân lớp dựa vào nội dung trong văn bản độ phù hợp của văn bản đó với các văn bản trong tập huấn luyện. Trong mô hình học máy được áp dụng, 9 văn bản trong tập huấn luyện đã được gán nhãn trước và mô hình phân loại cần phải tìm cách để trích chọn ra các đặc trưng của các văn bản thuộc mỗi lớp. 1.2.4. Ứng dụng của việc phân lớp văn bản Phân lớp dữ liệu văn bản có vai trò vô cùng quan trọng với công việc tìm kiếm dữ liệu văn bản. Thông qua phân lớp văn bản chúng ta có thể xác định ra được chủ đề phân lớp dữ liệu muốn tìm kiếm. Ngoài ra chúng ta có thể kể đến một ứng dụng nữa của việc phân lớp dữ liệu văn bản là việc ứng dụng để lọc văn bản hoặc một phần văn bản chứa những thông tin cần tìm mà không làm mất hay ảnh hưởng tới tính phức tạp ngôn ngữ tự nhiên. Phân lớp văn bản còn có rất nhiều ứng dụng đa dạng khác trong thực tế, điển hình chúng ta có thể kể đến những ứng dụng trích chọn thông tin trên mạng Internet. Có rất nhiều trang có nội dung không lành mạnh hay phản động hoặc đăng những nội dung sai sự thật nhằm tăng lượng người xem, những nội dung này có khả năng lẫn lộn vào kết quả trả về của các bộ máy tìm kiếm thông tin trên mạng hoặc có thể gây phiền toái cho những người dùng internet bằng các email rác. Từ đó chúng ta ngày càng thấy rõ sự cần thiết của việc ứng dụng việc phân lớp văn bản vào việc xây dựng các mô hình lọc thông tin trên mạng internet. Từ đó có thể thấy rằng phân lớp văn bản đã và đang là một trong các công cụ không thể thiếu trong thời đại hiện nay, vì vậy phân lớp văn bản đang là một trong các vấn đề được quan tâm phát triển hàng đầu với mục đích tạo ra những công cụ hữu ích cho thế giới nói chung và lĩnh vực công nghệ thông tin nói riêng. 1.2.5. Quá trình phân lớp văn bản Phân lớp dữ liệu văn bản có thể chia làm 4 bước cơ bản sau: Bước 1: Tạo chỉ mục (indexing): Văn bản chưa được xử lý cần được chuyển sang một dạng biểu diễn có cấu trúc để có thể xử lý, quá trình này còn được gọi là quá trình biểu diễn văn bản và dạng phổ biến nhất có thể kể đến là vector đặc trưng. Tốc độ thiết lập chỉ mục có vai trò thiết yếu trong quá trình phân lớp dữ liệu văn bản. Bước 2: Xác định độ phân lớp: Đưa ra cách thức xác định lớp cho mỗi văn bản dựa trên cấu trúc biểu diễn của văn bản. Trong khi các câu hỏi mang tính chất nhất thời thì tập phân lớp lại được dùng một cách lâu dài, ổn định cho quá trình phân lớp dữ liệu. Bước 3: So sánh: Trong đa số các tập phân lớp, mỗi đối tượng văn bản đều được yêu cầu thiết lập đúng sai vào một phân lớp nào đó. Bước 4: Phản Hồi: Đây là quá trình có hai vai trò trong mô hình phân lớp dữ liệu văn bản. Vai trò thứ nhất là khi thực hiện phân lớp thì cần một lượng lớn các văn bản trong tập huấn luyện. Các đối tượng văn bản đã được gán nhãn này được dùng làm 10 mẫu huấn luyện để hỗ trợ xây dựng mô hình phân lớp. Vai trò thứ hai là đối với việc phân lớp dữ liệu văn bản chúng ta khó có thể thay đổi các yêu cầu bởi người dùng có thể thông báo với quản trị viên hệ thống về việc cập nhật các lớp văn bản. Sơ đồ dưới đây thể hiện bộ khung cho việc phân lớp dữ liệu văn bản, trong đó có thể kể đến ba công đoạn chính: Hình 1.3. Sơ đồ biểu diễn quá trình phân lớp dữ liệu văn bản Công đoạn 1: Biểu diễn đối tượng văn bản dưới dạng có cấu trúc, xây dựng tập dữ liệu được gán nhãn. Công đoạn 2: Dùng các kỹ thuật học máy để tiến hành huấn luyện trên các mẫu vừa được biểu diễn ở công đoạn 1. Thực chất công đoạn 1 tạo ra các vector đầu vào cho công đoạn 2. Công đoạn 3: Mở rộng các dữ liệu thêm vào được cung cấp bởi người dùng để cải thiện hiệu suất. 1.2.6. Đánh giá máy phân lớp văn bản Trong thực tế không có một phương pháp phân lớp dữ liệu văn bản nào là tuyệt đối trong mọi hoàn cảnh. Bất cứ một phương pháp phân loại nào cũng đều tồn tại độ sai số. Do đó chỉ ra độ đo để có thể đánh giá chính xác được hiệu suất của mô hình phân lớp sẽ giúp xác định được phương pháp nào là tốt hay không tốt. Có thể đưa ra một số công thức chung để đánh giá hiệu suất của các mô hình. Độ hồi tưởng và độ chính xác, độ và độ đo F1 được sử dụng khá phổ biến trong việc đánh giá độ chính xác của các mô hình phân lớp. Precsion = True_positive x 100 % (True_positive) + (False_ positive ) 11 Recall = True_positive x 100 % (True_positive) + (True_ negative ) F1(recall, precision) = 2 x recall x precision recall x precision Để dễ hiểu hơn, chúng ta có công thức: Độ chính xác = Độ bao phủ = Số văn bản được phân vào lớp dương và đúng Tổng số văn bản được phân lớp Số văn bản được phân vào lớp dương và đúng Tổng số văn bản phân vào lớp dương Tiêu chuẩn đánh giá = độ hồi tưởng ∗ độ chính xác độ hồi tưởng + độ chính xác Các chỉ số này cũng là cơ sở để học viên dùng để đánh giá các phương pháp phân loại về sau trong phần thực nghiệm. 1.2.7. Những yếu tố ảnh hưởng đến quá trình phân lớp Phân lớp dữ liệu văn bản hiện đang có vai trò rất quan trọng trong sự phát triển của toàn thế giới, tùy vào độ phức tạp của từng loại văn bản khả năng thực thi của các mô hình phân lớp sẽ khác nhau. Có 3 yếu tố thiết yếu ảnh hưởng đến kết quả của việc phân lớp có thể kể đến: Tập dữ liệu được thiết lập nhãn trước phải đủ lớn để huấn luyện cho mô hình phân lớp. Có được một tập dữ liệu chuẩn và đủ lớn sẽ giúp cho việc học của mô hình được tốt hơn và đem lại kết quả phân lớp sau này chính xác hơn. Phương pháp tách từ khóa trong văn bản ảnh hưởng tới quá trình biểu diễn văn bản bằng vector vì các phương pháp tách đơn giản thường sẽ gặp vấn đề với những ngôn ngữ khác nhau, do đó việc xây dựng phương pháp tách từ khóa là một yếu tố thiết yếu. Phân lớp dữ liệu văn bản phải sử dụng thuật toán hợp lý về thời gian xử lý gồm: thời gian để huấn luyện và thời gian thực hiện phân lớp, thêm nữa thuật toán sẽ không phân lớp lại toàn bộ tập văn bản khi thêm vào đối tượng dữ liệu văn bản mới mà chỉ 12 thực hiện phân lớp cho đối tượng văn bản mới, ngoài ra thuật toán cần có khả năng giảm nhiễu khi phân lớp dữ liệu văn bản. 1.3. PHÁT BIỂU VỀ BÀI TOÁN PHÂN LOẠI VĂN BẢN Trong những năm gần đây, với sự phát triển và ứng dụng của Internet, khối lượng dữ liệu đã tăng trưởng không ngừng theo cả hai phương diện tạo mới và lưu trữ. Sự mở rộng các dữ liệu khoa học về địa lý, địa chất, khí tượng do vệ tinh thu thập, sự giới thiệu quảng bá mã vạch đối với hầu hết các sản phẩm thương mại, việc tin học hoá sâu rộng các thương vụ và giao dịch, sự phát triển việc ứng dụng công nghệ thông tin trong quản lý hành chính nhà nước,... đã tạo ra một khối lượng dữ liệu khổng lồ. Tự động phân lớp văn bản là một nhiệm vụ rất quan trọng có thể giúp ích trong việc tổ chức cũng như tìm kiếm thông tin trên nguồn tài nguyên lớn này. Phân loại văn bản là một bài toán xử lí văn bản kinh điển, đó là ánh xạ một văn bản vào một chủ đề đã biết trong một tập hữu hạn các chủ đề dựa trên ngữ nghĩa của văn bản. Ví dụ một bài viết trong một tờ báo có thể thuộc một (hoặc một vài) chủ đề nào đó (như thể thao, sức khỏe, công nghệ thông tin,…). Việc tự động phân loại văn bản vào một chủ đề nào đó giúp cho việc sắp xếp, lưu trữ và truy vấn tài liệu dễ dàng hơn về sau. Đặc điểm nổi bật của bài toán này là sự đa dạng của chủ đề văn bản và tính đa chủ đề của văn bản. Tính đa chủ đề của văn bản làm cho sự phân loại chỉ mang tính tương đối và có phần chủ quan, nếu do con người thực hiện, và dễ bị nhập nhằng khi phân loại tự động. Rõ ràng một bài viết về giáo dục cũng có thể xếp vào kinh tế nếu như bài viết bàn về tiền nong đầu tư cho giáo dục và tác động của đầu tư này đến kinh tế - xã hội. Về bản chất, một văn bản là một tập hợp từ ngữ có liên quan với nhau tạo nên nội dung ngữ nghĩa của văn bản. Từ ngữ của một văn bản là đa dạng do tính đa dạng của ngôn ngữ (đồng nghĩa, đa nghĩa, từ vay mượn nước ngoài,…) và số lượng từ cần xét là lớn. Ở đây cần lưu ý rằng, một văn bản có thể có số lượng từ ngữ không nhiều, nhưng số lượng từ ngữ cần xét là rất nhiều vì phải bao hàm tất cả các từ của ngôn ngữ đang xét. Trên thế giới đã có nhiều công trình nghiên cứu đạt những kết quả khả quan, nhất là đối với phân loại văn bản tiếng Anh. Tuy vậy, các nghiên cứu và ứng dụng đối với văn bản tiếng Việt còn nhiều hạn chế do khó khăn về tách từ và câu. 1.3.1. 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 văn bản dựa trên đồ 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 của học máy đó là: học có giám sát, học nửa giám sát và học không giám sát. 13 Bộ phân lớp có thể được xây dựng bằng tay dựa vào các kỹ thuật ứng dụng tri thức (thường là xây dựng một tập các tri thức) hoặc có thể xây dựng một cách tự động bằng các kỹ thuật học máy thông qua một tập các dữ liệu huấn luyện được định nghĩa trước phân lớp tương ứng. Vấn đề phân loại văn bản theo phương pháp thống kê dựa trên máy học được đặc tả bao gồm hai giai đoạn: giai đoạn huấn luyện và giai đoạn phân lớp. Hình 1.4. Mô hình tổng quát 1.3.2. Giai đoạn huấn luyện Chúng ta có một tập huấn luyện, mỗi phần tử trong tập huấn luyện được gán vào một hay nhiều lớp mà chúng ta sẽ thể hiện chúng bằng một mô hình mã hóa (sẽ được trình bày chi tiết ở Chương II). Thông thường mỗi phần tử trong tập huấn luyện được thể hiện theo dạng (𝑥⃗ , 𝑐). Trong đó, 𝑥⃗ là vector biểu diễn cho văn bản trong tập huấn luyện. Sau đó, chúng ta sẽ định nghĩa một lớp mô hình và một thủ tục huấn luyện. Lớp mô hình là họ các tham số của bộ phân loại, thủ tục huấn luyện là một giải thuật (hay thuật toán) để chọn ra một họ các tham số tối ưu cho bộ phân loại. Hình 1.5. Mô hình giai đoạn huấn luyện + Đầu vào: dữ liệu huấn luyện và thuật toán huấn luyện