Tài liệu Phân loại văn bản tin tức dùng máy vec tơ hỗ trợ

ĐẠI HỌC ĐÀ NẴNG TRƢỜNG ĐẠI HỌC BÁCH KHOA NGÔ HẢI NAM PHÂN LOẠI VĂN BẢN TIN TỨC DÙNG MÁY VEC-TƠ HỖ TRỢ Chuyên ngành: Khoa học máy tính Mã số: 8480101 LUẬN VĂN THẠC SĨ KỸ THUẬT Ngƣời hƣớng dẫn khoa học: TS. NINH KHÁNH DUY Đà Nẵng - Năm 2019 LỜI CAM ĐOAN Tôi xin cam đoan luận án thạc sĩ “Phân loại văn bản tin tức dùng máy vec-tơ hỗ trợ” là do tôi nghiên cứu dưới sự hướng dẫn của TS. Ninh Khánh Duy. Các kết quả trong luận án là hoàn toàn trung thực và chưa được công bố trong bất kỳ nghiên cứu nào. Các nguồn tài liệu tham khảo và kế thừa đều được trích dẫn và tham chiếu đầy đủ, phù hợp với các quy định của bộ Giáo dục và Đào tạo, trường Đại học Bách khoa Đà Nẵng. Ngƣời cam đoan Ngô Hải Nam MỤC LỤC TRANG BÌA LỜI CAM ĐOAN MỤC LỤC TRANG TÓM TẮT LUẬN VĂN DANH MỤC CÁC TỪ VIẾT TẮT DANH MỤC CÁC BẢNG DANH MỤC CÁC HÌNH MỞ ĐẦU .................................................................................................................... 1 1. Lý do chọn đề tài ........................................................................................... 1 2. Mục đích và ý nghĩa đề tài ............................................................................. 1 3. Mục tiêu và nhiệm vụ .................................................................................... 2 4. Đối tƣợng và phạm vi nghiên cứu ................................................................. 2 5. Phƣơng pháp nghiên cứu ............................................................................... 3 6. Kết luận .......................................................................................................... 3 7. Bố cục của luận văn ....................................................................................... 3 CHƯƠNG 1. BÀI TOÁN PHÂN LOẠI VĂN BẢN .............................................. 4 1.1. Phân loại văn bản ........................................................................................ 4 1.1.1. Khái niệm .......................................................................................... 4 1.1.2. Bài toán phân loại văn bản ................................................................ 5 1.2. Mô hình phân loại văn bản dùng tiếp cận học máy .................................... 6 1.2.1. Khái niệm học máy ........................................................................... 6 1.2.2. Phân loại học máy ............................................................................. 6 1.2.3. Dữ liệu huấn luyện trong học máy .................................................... 7 1.2.4. Mô hình phân loại văn bản ................................................................ 7 1.3. Thu thập dữ liệu .......................................................................................... 8 1.4. Tiền xử lý văn bản ...................................................................................... 9 1.4.1. Xử lý ngôn ngữ tự nhiên ................................................................... 9 1.4.2. Biểu diễn văn bản dƣới dạng vec-tơ đặc trƣng ............................... 13 1.4.3. Giảm chiều dữ liệu .......................................................................... 15 CHƯƠNG 2. THUẬT TOÁN MÁY VEC-TƠ HỖ TRỢ TRONG PHÂN LOẠI VĂN BẢN ................................................................................................................ 16 2.1. Thuật toán máy vec-tơ hỗ trợ.................................................................... 16 2.1.1. Lý thuyết máy vec-tơ hỗ trợ ............................................................ 16 2.1.2. Nội dung phƣơng pháp SVM .......................................................... 16 2.1.3. Hàm nhân kernel trong SVM .......................................................... 20 2.2. Ứng dụng trong phân loại văn bản ........................................................... 22 CHƯƠNG 3. KẾT QUẢ VÀ ĐÁNH GIÁ ............................................................ 24 3.1. Dữ liệu thử nghiệm ................................................................................... 24 3.2. Triển khai chƣơng trình ............................................................................ 25 3.2.1. Các công cụ sử dụng ....................................................................... 25 3.2.2. Các bƣớc xây dựng mô hình phân loại văn bản .............................. 26 3.3. Kết quả thử nghiệm với SVM ................................................................... 27 3.4. So sánh với thuật toán Naive Bayes ......................................................... 34 3.4.1. Thuật toán Naive Bayes .................................................................. 34 3.4.2. Kết quả phân loại với Naive Bayes ................................................. 35 3.5. Đánh giá .................................................................................................... 36 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ............................................................ 37 TÀI LIỆU THAM KHẢO...................................................................................... 38 QUYẾT ĐỊNH GIAO ĐỀ TÀI LUẬN VĂN THẠC SĨ (BẢN SAO). BẢN SAO KẾT LUẬN CỦA HỘI ĐỒNG, BẢN SAO NHẬN XÉT CỦA CÁC PHẢN BIỆN. Học viên Hoàng Đại Thọ TRANG TÓM TẮT LUẬN VĂN Tên đề tài: PHÂN LOẠI VĂN BẢN TIN TỨC DÙNG MÁY VEC-TƠ HỖ TRỢ Học viên: Ngô Hải Nam Chuyên ngành: Khoa Học Máy Tính - Mã số: 8480101 Khóa: 34 Trƣờng Đại học Bách khoa – Đại học Đà Nẵng Tóm tắt - Luận văn này thực hiện nghiên cứu, đánh giá việc phân loại văn bản tin tức dựa trên phƣơng pháp máy học Support vector machine (SVM) cùng với sự kết hợp giữa biểu diễn văn bản bằng mô hình túi từ BoW (Bag-of-Words) và thuật toán TF-TDF (Term frequency – Inverse document frequency). Một số phƣơng pháp máy học và khai phá dữ liệu văn bản phổ biến đƣợc áp dụng để huấn luyện tập dữ liệu cho phân loại văn bản nhƣ SVM, Bayes đơn giản (Naïve Bayes), Cây quyết định (Decision tree). Quá trình thực nghiệm phân loại văn bản tin tức với tập dữ liệu hơn 10.000 tin tức trong nhiều chủ đề đƣợc tổng hợp từ các nguồn báo chí trên Internet. Tập dữ liệu huấn luyện đƣợc trích xuất và tóm gọn trong một số chủ đề chính nhƣ: Thế giới, Giáo dục, Sức khỏe, Khoa học-Công nghệ…Kết quả thực nghiệm bƣớc đầu đã khẳng định tính khả thi của mô hình khi kết quả phân loại đạt đƣợc độ chính xác khoảng 87%. Từ khóa- Phân loại văn bản tiếng việt, máy vec-tơ hỗ trợ Abstract: This thesis studies and evaluates the categorization of news text based on the support vector machine (SVM) method together with the combination of text representation by bag-of-Words and TF-TDF (Term frequency - Inverse document frequency) algorithm. A number of popular machine learning and data mining methods are used to train data sets for text classification such as SVM, Naïve Bayes, decision tree ... The empirical process categorizes news texts with more than 10,000 multi-threaded news aggregated from Internet newspaper sources. Training data was extracted and summarized in a number of major topics such as: World, Education, Health, Science-Technology... The experimental results initially confirmed the feasibility of the model classification results are approximately 87% accurate. Keywords - Vietnamese text classification, Support vector machine DANH MỤC CÁC TỪ VIẾT TẮT SVM Support Vector Machines BoW Bag of Words TF-IDF Term frequency – Inverse document frequency URL Uniform Resource Locator HTML HyperText Markup Language ML Machine Learning NLP Natural Language Processing PCA Principle Component Analysis LDA Linear Discriminant Analysis DANH MỤC CÁC BẢNG Bảng 3.1. Tập dữ liệu tin tức đã thu thập theo các chủ đề ............................................24 Bảng 3.2. Tập dữ liệu training và testing ......................................................................24 Bảng 3.3. Kết quả đánh giá độ chính xác (Precision) với hàm nhân và số chiều vec-tơ đặc trƣng thay đổi.........................................................................................27 Bảng 3.4. Kết quả đánh giá SVM với hàm nhân linear .................................................33 Bảng 3.5. So sánh kết quả phân loại Naïve Bayes và SVM Linear ..............................35 DANH MỤC CÁC HÌNH Hình 1.1. Phân loại văn bản tin tức theo chủ đề ..............................................................4 Hình 1.2 Gmail tự động xác định xem email spam hay không .......................................5 Hình 1.3. Mô hình phân loại văn bản ..............................................................................8 Hình 1.4. Quá trình thu thập dữ liệu website ..................................................................9 Hình 1.5. Ví dụ về công đoạn làm sạch văn bản ...........................................................10 Hình 1.6. Minh họa kết quả của giai đoạn tách từ .........................................................11 Hình 1.7. Một số từ stopwords trong tiếng Việt ............................................................12 Hình 1.8. Cách sử dụng Bag of Words ..........................................................................13 Hình 2.1. Siêu phẳng phân chia dữ liệu 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 .........................................16 Hình 2.2. Bài toán phân loại các điểm sử dụng SVM ...................................................17 Hình 2.3. Phƣơng pháp 1-vs-tất cả cho máy học SVM đa lớp ......................................18 Hình 2.4. Phƣơng pháp 1-vs-1 cho máy học SVM đa lớp ............................................19 Hình 2.5. Các điểm trong không gian phi tuyến ...........................................................20 Hình 2.6. Chuyển đổi không gian dữ liệu đầu vào bài toán SVM ................................20 Hình 2.7. Sự khác nhau khi phân loại dữ liệu của các kernel .......................................22 Hình 2.8. Mô hình ứng dụng phân loại văn bản ............................................................23 Hình 3.1. Các công đoạn tiền xử lý văn bản .................................................................26 Hình 3.2. Giao diện chính của chƣơng trình phân loại văn bản ....................................27 Hình 3.3. Tokenize văn bản tin tức ...............................................................................28 Hình 3.4. Giao diện phân loại văn bản tin tức ...............................................................28 Hình 3.5. Văn bản tin tức chủ đề “thể thao” .................................................................29 Hình 3.6. Kết quả phân loại tin tức chủ đề “Thể thao” .................................................29 Hình 3.7. Văn bản tin tức chủ đề “Kinh tế” ..................................................................30 Hình 3.8. Kết quả phân loại tin tức chủ đề “Kinh tế” ...................................................30 Hình 3.9. Mô hình hóa các chỉ số trong ML .................................................................31 Hình 3.10. Cách tính Precision và Recall ......................................................................32 Hình 3.11. Tỷ lệ chính xác dự đoán các chủ đề ............................................................34 1 MỞ ĐẦU 1. Lý do chọn đề tài Nhƣ chúng ta đã biết, hầu hết các thông tin hiện nay đều nằm dƣới dạng văn bản, có thể kể đến nhƣ các bài báo, tài liệu học tập, tài liệu sản xuất kinh doanh, các nghiên cứu khoa học. Với nhu cầu trao đổi thông tin ngày càng lớn hiện nay, thì việc ứng dụng các công cụ quản lý văn bản là một xu thế tất yếu. Tuy nhiên, đó chỉ là cách quản lý luồng dữ liệu văn bản, cung cấp các công cụ kho chứa, chƣa có giải pháp phân loại, trích lọc thông tin nhằm mục đích thống kê, phát hiên tri thức, ra quyết đinh trực tiếp trên các nguồn dữ liệu này. Với thực tế đó, vấn đề đặt ra là làm thế nào để chúng ta có thể khai thác đƣợc những thông tin hữu ích từ các nguồn tài liệu văn bản nói chung. Các nguồn dữ liệu này phải đƣợc xử lý nhƣ thế nào để ngƣời dùng có thể có những công cụ tự động hóa trợ giúp trong việc khai thác thông tin. Rõ ràng, chúng ta phải hiểu rõ bản chất của dữ liệu văn bản, các đặc trƣng của các dữ liệu loại này để có những phƣơng pháp luận cần thiết. Việc khai thác thông tin từ các nguồn dữ liệu văn bản Việt Nam sẽ dựa vào những kết quả nghiên cứu về văn bản nói chung. Tuy nhiên những văn bản tiếng Việt lại có những đặc trƣng riêng của nó: ví dụ sự khác biệt về cú pháp, ngữ pháp so với các ngôn ngữ phổ biến trên thế giới nhƣ tiếng Anh, tiếng Pháp…Để làm rõ vấn đề này, chúng ta sẽ đi vào một chủ đề thƣờng gặp nhất trong việc xử lý văn bản, đó là phân loại văn bản tiếng Việt. Đây cũng chính là nôi dung chính của đề tài “Phân loại văn bản tin tức dùng máy vec-tơ hỗ trợ” 2. Mục đích và ý nghĩa đề tài Mục đích Xây dựng chƣơng trình có khả năng phân loại văn bản tin tức theo chủ đề (các chủ đề nhƣ Giáo dục, Thể thao, Thế giới, Sức khỏe …) dựa trên việc xử lý văn bản, trích rút đặc trƣng và áp dụng máy vec-tơ hỗ trợ để học, phân loại dựa trên các đặc trƣng đó. Để thoả 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 các bƣớc giải quyết bài toán Machine Learning và lý thuyết phân lớp trong Máy vec-tơ hỗ trợ. Nắm vững cách trích chọn đặc trƣng văn bản tin tức tiếng Việt Xây dựng đƣợc phần mềm có thể phân loại văn bản một cách chính xác nhất. Đánh giá hiệu quả của thuật toán máy vec-tơ hỗ trợ qua các dữ liệu kiểm tra và so sánh với thuật toán phân loại khác nhƣ Naïve Bayes 2 Ý nghĩa khoa học thực tiễn của đề tài Đóng góp về mặt phƣơng pháp và thực nghiệm vào lĩnh vực phân loại văn bản, một nhánh nghiên cứu của xử lý ngôn ngữ tự nhiên. Nghiên cứu chuẩn hóa, trích rút đặc trƣng văn bản tin tức tiếng Việt cho bài toán phân loại văn bản. Xây dựng hƣớng tiếp cận cho bài toán phân loại tin tức, ứng dụng phục vụ cho các công tác quản lý thông tin văn bản. 3. Mục tiêu và nhiệm vụ Mục tiêu Mục tiêu chính của đề tài là nghiên cứu phƣơng pháp phân loại văn bản tin tức ứng dụng máy vec-tơ hỗ trợ thông qua ngôn ngữ Python. Để thỏa mãn mục tiêu này, cần đạt đƣợc các mục tiêu cụ thể sau: Thu thập cơ sở dữ liệu văn bản tin tức tiếng Việt. Nắm vững kiến thức lập trình Python nền tảng và thuật toán máy vec-tơ hỗ trợ Đề xuất giải pháp ứng dụng máy vec-tơ hỗ trợ vào việc phân loại văn bản tin tức và so sánh với các phƣơng pháp khác. Nhiệm vụ Để đạt đƣợc những mục tiêu trên thì nhiệm vụ đặt ra của đề tài là: Thu thập dữ liệu văn bản tin tức tiếng Việt. Phát biểu, phân tích và cài đặt giải thuật trên ngôn ngữ Python cho bài toán phân loại văn bản. Đánh giá kết quả theo yêu cầu của đề tài 4. Đối tƣợng và phạm vi nghiên cứu Trong khuôn khổ của luận văn thạc sĩ thuộc loại ứng dụng với thời gian thực hiện là 06 tháng, tôi giới hạn nghiên cứu các vấn đề sau: Thuật toán máy vec-tơ hỗ trợ và sử dụng ngôn ngữ Python. Ứng dụng thuật toán máy vec-tơ hỗ trợ trong việc phân loại văn bản tiếng Việt triển khai trên ngôn ngữ Python Đánh giá giải pháp thực hiện. 3 5. Phƣơng pháp nghiên cứu Phương pháp lý thuyết Tiến hành thu thập và nghiên cứu các tài liệu có liên quan đến đề tài. Nghiên cứu lý thuyết thuật toán máy vec-tơ hỗ trợ. Nghiên cứu việc mô hình hóa văn bản phù hợp với thuật toán 6. Phƣơng pháp thực nghiệm Lập trình chạy thử với các dữ liệu mẫu trên ngôn ngữ Python Kiểm tra, thử nghiệm, nhận xét và đánh giá kết quả. 7. Kết luận Xây dựng đƣợc công cụ phục vụ phân loại văn bản tin tức Tiếng Việt. Đánh giá hiệu quả của thuật toán máy vec-tơ hỗ trợ và so sánh với các phƣơng pháp khác. 8. Bố cục của luận văn Dự kiến luận văn đƣợc trình bày bao gồm các phần chính nhƣ sau : ● MỞ ĐẦU Nêu bối cảnh nghiên cứu, lý do chọn đề tài và mục tiêu nghiên cứu. ● CHƢƠNG 1: BÀI TOÁN PHÂN LOẠI VĂN BẢN + Phân loại văn bản. + Mô hình phân loại văn bản dùng tiếp cận học máy + Thu thập dữ liệu + Tiền xử lý văn bản + Biểu diễn văn bản dƣới dạng vec-tơ đặc trƣng ● CHƢƠNG 2: THUẬT TOÁN MÁY VEC-TƠ HỖ TRỢ TRONG PHÂN LOẠI VĂN BẢN + Thuật toán máy vec-tơ hỗ trợ + Ứng dụng trong phân loại văn bản ● CHƢƠNG 3: KẾT QUẢ VÀ ĐÁNH GIÁ + Dữ liệu thử nghiệm + Triển khai chƣơng trình + Kết quả thử nghiệm với SVM + So sánh với thuật toán Naïve Bayes + Đánh giá ● KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN ● TÀI LIỆU THAM KHẢO 4 CHƢƠNG 1: BÀI TOÁN PHÂN LOẠI VĂN BẢN 1.1. Phân loại văn bản 1.1.1. Khái niệm Phân loại văn bản hay còn gọi là Text Categorization [1] [10] hoặc Text Classification [1]. là một bài toán xử lý văn bản cổ điển thuộc về lĩnh vực Xử lý ngôn ngữ tự nhiên (Natural Language Processing) [1] [11]., đó là ánh xạ một văn bản mới vào một chủ đề (tên lớp/nhãn lớp) đã biết trong một tập các chủ đề dựa trên mức độ tƣơng tự của văn bản đó so với các văn bản trong cùng chủ đề đấy. 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, chiết lọc thông tin, lọc văn bản. Phân loại văn bản có thể thực hiện thủ công hoặc tự động sử dụng các kỹ thuật học máy có giám sát [1]. Hình 1.1. Phân loại văn bản tin tức theo chủ đề Mục tiêu của một hệ thống phân loại văn bản là nó có thể tự động phân loại một văn bản cho trƣớc, để xác định xem văn bản đó thuộc chủ đề nào. Một số ứng dụng của hệ thống phân loại nhƣ: o o o o Hiểu đƣợc ý nghĩa, đánh giá, bình luận của ngƣời dụng từ mạng xã hội. Phân loại email là spam hay không spam Tự động gắn thẻ cho những truy vấn, tìm kiếm của ngƣời dùng Phân loại chủ đề các bài báo điện tử 5 Ví dụ cụ thể về bài toán phân loại văn bản: Giả sử x là một bài báo do phóng viên viết gửi đăng trên trang báo điện tử VnExpress. Biên tập viên cần phải quyết định xem bài báo x đó thuộc chủ đề nào là thích hợp nhất trong các chủ đề: “chính trị- xã hội”, “quốc tế”, “thể thao”, “giải trí”. Một trong những ví dụ nữa cơ bản nhất của phân loại văn bản đó là việc phân loại email, mỗi ngày ta nhận đƣợc hàng tram email, nhƣng số lƣợng email spam không nhỏ. Làm cách nào để viết một chƣơng trình lọc mail, quyết định xem một email gửi tới vào hộp thƣ đến hay spam? Hình 1.2 Gmail tự động xác định xem email spam hay không 1.1.2. Bài toán phân loại văn bản Ta có thể mô hình hóa toán học việc phân loại văn bản nhƣ sau: Cho x là một văn bản, biết x thuộc một trong các loại y {1, 2,3,...K} .Hãy tìm loại văn bản đúng nhất của x Gọi y h ( x) là hàm phân loại của x trong đó là tham số của hàm. Ta cần h (.) có khả năng phân loại tốt nhất. Để tìm h ta sử dụng phƣơng pháp học có hƣớng dẫn từ dữ liệu mẫu : tìm y Dữ liệu học gồm N mẫu : ( x1 , y1 ) , ( x2 , y2 ) ,…. ( xN , yN ) Hàm h đƣợc xây dựng sao cho khớp nhất với dữ liệu huấn luyện này. Các bài toán phân loại văn bản nói chung có thể phân biệt theo hai cách nhƣ sau: 6 Phân loại văn bản nhị phân/ đa lớp: Bài toán phân loại văn bản gọi là nhị phân khi số lớp là 2, gọi là đa lớp nếu số lớp lớn hơn 2 Phân loại văn bản đơn nhãn/ đa nhãn: Bài toán phân loại văn bản đơn nhãn khi mỗi văn bản đƣợc gán vào chính xác một lớp. Ngƣợc lại nếu một văn bản có thể đƣợc gán nhiều nhãn hơn một nhãn thì đó là bài toán phân loại văn bản đa nhãn. Phân loại văn bản là một lĩnh vực đƣợc chú ý nhất và đã đƣợc nghiên cứu trong những năm gần đây. Tuy nhiên các công trình nghiên cứu này phần lớn đều dành cho xử lý ngôn ngữ nƣớc ngoài, mà tiếng Anh là chủ yếu. Để áp dụng cho các văn bản tin tức tiếng Việt thì không có độ chính xác nhƣ mong muốn. 1.2. Mô hình phân loại văn bản dùng tiếp cận học máy 1.2.1. Khái niệm học máy Học máy (Machine Learning) [15] [16]: Là một lĩnh vực của trí tuệ nhân tạo, liên quan đến các kỹ thuật giúp cho máy tính có thể tự học mà không cần phải cài đặt các luật quyết định [2]. Cụ thể, học máy là một phƣơng pháp để tạo ra các chƣơng trình máy tính bằng việc phân tích các tập dữ liệu. Về nguyên lý, học máy dựa trên các thuật toán, tức là tập hợp hữu hạn của các chỉ thị hay phƣơng thức đƣợc định nghĩa rõ ràng và cần thiết, để chúng tự thu thập kiến thức. Và sau mỗi lần hệ thống khởi động dữ liệu mới, các kết quả do nó đƣa ra sẽ trở nên ngày càng chính xác hơn. Theo đó, học máy chủ yếu dựa trên 4 thao tác: Phân loại/liệt kê thông tin; dự đoán những sự kiện nhất định trên cơ sở các mô hình đã đƣợc nhận dạng; phát hiện/nhận dạng các mô hình chƣa đƣợc biết đến và sự phụ thuộc giữa chúng; phát hiện sự bất thƣờng và các sự kiện chƣa đƣợc dự đoán. 1.2.2. Phân loại học máy Các giải thuật học máy đƣợc phân ra làm 2 loại chính là: Học có giám sát (Supervised Learning) [12]: Là phƣơng pháp sử dụng những dữ liệu đã đƣợc gán nhãn từ trƣớc để suy luận ra quan hệ giữa đầu vào và đầu ra [3]. Các dữ liệu này đƣợc gọi là dữ liệu huấn luyện và chúng là cặp các đầu vào- đầu ra. Học có giám sát sẽ xem xét các tập huấn luyện này để từ đó có thể đƣa ra dự đoán đầu ra cho một đầu vào mới chƣa gặp giờ. Ví dụ nhƣ dự đoán giá nhà, phân loại email. Học phi giám sát (Unsupervised Learning) [3] [12]: Khác với học có giám sát, học phi giám sát sử dụng những dữ liệu chƣa đƣợc gán nhãn từ trƣớc để suy luận. Phƣơng pháp này thƣờng đƣợc sử dụng để tìm cấu trúc của tập dữ liệu. Tuy nhiên lại không co phƣơng pháp đánh giá đƣợc cấu trúc tìm ra đƣợc là 7 đúng hay sai. Ví dụ nhƣ phân cụm dữ liệu, triết xuất thành phần chính của một chất nào đó. Học tăng cƣờng (Reinforcement Learning) [12]. Thuật toán học tăng cƣờng sẽ đƣợc áp dụng khi tƣơng tác với một môi trƣờng thay đổi nhằm thực hiện một nhiệm vụ nào đó (ví dụ như lái xe hay chơi cờ) [3]. Các thuật toán học tăng cƣờng cố gắng tìm một chiến lƣợc ánh xạ không gian trạng thái của môi trƣờng tới các hành động mà chƣơng trình nên chọn trong các trạng thái đó để cực đại hóa một khoản thƣởng (reward) nào đó về lâu dài. 1.2.3. Dữ liệu huấn luyện trong học máy Bất cứ một bài toán học máy nào cũng đều cần có dữ liệu để huấn luyện, ta có thể coi nó là điều kiện tiên quyết. Dữ liệu sau khi có đƣợc cần phải: Chuẩn hóa: Tất cả các dữ liệu đầu vào đều cần đƣợc chuẩn hóa để máy tính có thể xử lý đƣợc. Quá trình chuẩn hóa bao gồm số hóa dữ liệu, co giãn thông số cho phù hợp với bài toán. Việc chuẩn hóa này ảnh hƣởng trực tiếp tới tốc độ huấn luyện cũng nhƣ cả hiệu quả huấn luyện. Phân chia: Việc mô hình đƣợc chọn khớp với tập dữ liệu đang có không có nghĩa giả thuyết của ta là đúng mà co thể xảy ra tình huống dữ liệu thật lại không khớp. Vì vậy khi huấn luyện học máy, ta sẽ chia dữ liệu ra thành 3 loại để có thể kiểm chứng đƣợc phần nào mức độ tổng quát của mô hình. Cụ thể 2 loại đó là: o Tập huấn luyện (Training set): chiếm khoảng từ 60%-90% tập dữ liệu dùng để học khi huấn luyện o Tập kiểm tra (Test set): chiếm khoảng từ 40%-10% dùng để kiểm tra xem mô hình đã phù hợp chƣa sau khi huấn luyện 1.2.4. Mô hình phân loại văn bản Để phân lớp văn bản tự động thƣờng sử dụng các kỹ thuật học máy có giám sát, dựa trên tập dữ liệu đầu vào đã đƣợc gán đúng nhãn [4]. Đầu tiên hệ thống đƣợc huấn luyện thông qua tập mẫu, sau đó đánh giá hiệu quả của hệ thống thông qua các dữ liệu kiểm thử. Quá trình đó là huấn luyện và dự đoán dữ liệu và đƣợc mô phỏng nhƣ hình sau: 8 Hình 1.3: Mô hình phân loại văn bản o Quá trình huấn luyện(Training): Văn bản đầu vào có gán nhãn (chủ đề) đƣợc chuyển thành dạng cấu trúc nào đó thông qua trích chọn đặc trƣng. Sau đó chúng ta thực hiện các thuật toán học máy với tập các đặc trƣng đã đƣợc trích chọn. Kết quả của quá trình training là chúng ta đƣợc mô hình phân loại (classifier model) o Quá trình dự đoán (Prediction): Văn bản chƣa rõ nhãn đƣợc trích chọn đặc trƣng thông qua mô hình phân loại sẽ đƣợc dự đoán đúng nhãn. Các thuật toán học máy dùng trong phân loại văn bản đƣợc áp dụng có thể là: Cây quyết định, K làng giếng gần nhất, máy vec-tơ hỗ trợ, cây quyết định. 1.3. Thu thập d iệu Để có đƣợc nguồn dữ liệu văn bản đầu vào đã đƣợc gán nhãn cho bài toán phận loại văn bản tin tức, ta phải tiến hành thu thập dữ liệu thông qua các trang báo điện tử nhƣ vnexpress.net, dantri.com, kenh14.vn…Những tin tức tại đây đã đƣợc xử lý và phân loại theo các chủ đề sẵn có. Với việc cần số lƣợng lớn các bài báo chúng ta không thể lấy nó thủ công đƣợc mà phải sử dụng các web crawler. Trình thu thập web (web crawler) là một chƣơng trình khai thác cấu trúc đồ thị của web di chuyển từ trang này qua trang khác, các tên gọi khác của trình thu thập web là bọ, rô-bốt, nhện web…Chức năng của web crawler là lấy thông tin từ website, trích xuất ra những thông tin ngƣời sử dụng cần, đồng thời cũng tìm những link có trong trang web đó và tự động truy cập vào những link đó. 9 Mô hình crawler web đơn giản gồm các bƣớc nhƣ sau: 1. Chọn URL khởi đầu 2. Sử dụng HTML protocol để lấy trang web 3. Trích xuất ra các link và lƣu lại trong queue 4. Lặp đi lặp lai các bƣớc 2,3 Hình 1.4. Quá trình thu thập dữ liệu website Các trình thu thập thƣờng bắt đầu bằng cách chọn một số các đƣờng dẫn URL ứng với các trang web sẽ ghé thăm đầu tiên. Khi ghé thăm một trang, trình thu thập sẽ đọc nội dung trang web, lọc ra tất cả các siêu liên kết có trong trang web đó và đƣa các URL tƣơng ứng với chúng vào một danh sách. Dựa vào danh sách này, trình thu thập tiếp tục quá trình duyệt đệ quy để ghé thăm tất cả các URL chƣa đƣợc duyệt. Quá trình này chỉ dừng lại khi trình thu thập đã thu thập đủ số trang yêu cầu hoặc danh sách rỗng. 1.4. Tiền xử ý văn bản 1.4.1. Xử lý ngôn ngữ tự nhiên Các phƣơng pháp phân loại văn bản thƣờng không làm việc trực tiếp trên các tài liệu văn bản. Chính vì vậy, ta phải biến đổi các văn bản sang một dạng phù hợp với các giải thuật phân loại. Phép xử lý nhƣ vậy đƣợc gọi là tiền xử lý văn bản (text preprocessing)[19]. Quá trình này là để đƣa tập dữ liệu về dạng có cấu trúc sau đó đƣa vào các kỹ thuật học máy để xử lý phân loại. Trong nội dung luận văn, tôi sẽ đi lần lƣợt các bƣớc để xử lý văn bản thô 10 1.4.1.1. Làm sạch văn bản Đây bƣớc đầu tiên trong tiền xử lý văn bản. Mục đích của bƣớc này là loại bỏ các ký tự thừa trong dữ liệu, trong các văn bản tin tức đó chính là các thẻ HTML, JavaScript, các ký tự đặc biệt, khoảng trắng thừa…Ngoài ra trong văn bản còn có chữ viết hoa, viết thƣờng lẫn lộn tuy nhiên máy tính phân biệt khác nhau giữa chữ in hoa và chữ in thƣờng. Điều này làm tăng độ phức tạp khi xử lý mặc dù về cơ bản ý nghĩa khi viết hoa hay viết thƣờng vẫn không thay đổi. Ta sẽ thực hiện phƣơng pháp đó là biến đổi hết về các chữ cái thƣờng và loại bỏ các khoảng trắng thừa. Ví dụ quá trình làm sạch văn bản nhƣ sau: Hình 1.5 Ví dụ về công đoạn làm sạch văn bản 1.4.1.2. Tách từ trong câu Thuật ngữ “tách từ” trong tiếng Anh là “Word Segmentation” [13]. Tách từ về mặt biểu hiện là gom nhóm các từ đơn liền kề thành một cụm từ có ý nghĩa. Trong ngôn ngữ tiếng Việt, dấu cách không phải là kí tự để phân tách các từ mà chỉ là phân tách các âm tiết với nhau [6]. Lí do của điều này là trong tiếng Việt tồn tại các từ ghép nhƣ là: đất nước, con người…Nếu đi cùng với nhau thì các từ này có nghĩa hoàn toàn khác so với nghĩa độc lập của nó. Ví dụ trong câu: "Bài toán tách từ tiếng Việt" sau khi tách từ thì thành "Bài_toán tách_từ tiếng_Việt". Về hình thức, các từ đơn đƣợc gom nhóm với nhau bằng cách nối với nhau bằng ký tự gạch dƣới "_", trong trƣờng hợp này là các từ Bài_toán, tách_từ, tiếng_Việt. Sau khi thực hiện tách từ thì mỗi từ (token) trong câu đƣợc cách nhau bởi một khoảng trắng. Vì vậy chúng ta cần tách từ để có thể đảm bảo ý nghĩa của từ đƣợc toàn vẹn. Tách từ là một bƣớc quan trọng bậc nhất trong xử lý ngôn ngữ tự nhiên. Việc tách từ trong Tiếng Việt còn đặc biệt quan trọng hơn vì Tiếng việt không đơn giản nhƣ tiếng Anh. Trong tiếng Anh thì các từ phân cách nhau bằng dấu cách (space) nhƣng tiếng Việt dấu cách lại để tách các âm tiết với nhau. 11 Hình 1.6 Minh họa kết quả của giai đoạn tách từ Về mặt ngữ nghĩa, việc tách từ trong văn bản đầu vào trƣớc khi đƣa vào huấn luyện mô hình máy học là để giải quyết các bài toán liên quan đến ngữ nghĩa của văn bản. Tức là kết quả đầu ra mang tính suy luận dựa trên việc hiểu ý nghĩa của văn bản đầu vào. Tách từ chính xác hay không là công việc rất quan trọng, nếu không chính xác rất có thể dẫn đến việc ý nghĩa của câu sai, ảnh hƣởng đến tính chính xác của của việc phân loại. 1.4.1.3. Loại bỏ Stopwords Stopwords [14] là những từ xuất hiện nhiều trong văn bản nhƣng lại không mang nhiều ý nghĩa, nó chỉ là các từ nối. Mỗi ngôn ngữ có những stopwords khác nhau. Trong tiếng Việt các từ stopwords là: thì, là, này, kia…Trong tiếng Anh là những từ: is, this, that…Việc cần làm của việc tiền xử lý văn bản là loại bỏ các từ không có ý nghĩa, chỉ để lại những từ ngữ mang ý nghĩa thực sự. 12 Hình 1.7. Một số từ stopwords trong tiếng Việt Ƣu điểm của phép xử lý này là không chỉ các từ không có ý nghĩa bị loại bỏ và không can thiệp vào quá trình phân loại về sau mà kích thƣớc các tập tin tài liệu sẽ giảm đi khoảng 30 đến 50 phần trăm. Để loại bỏ các từ stopwords [14] trong văn bản có hai cách chính sau: o Dùng từ điển: Sử dụng danh sách các từ stopwords và dùng bộ lọc để loại bỏ các từ đó ra khỏi văn bản. Trong cách này, thì tùy vào lĩnh vực văn bản cần xử lý thì danh sách các từ stopwords sẽ khác nhau. Tức là xử lý tin tức văn bản sẽ có tập danh sách stopwords khác với xử lý các bài báo khoa học. o Dựa theo tần suất xuất hiện của từ: Tiến hành đếm số lần xuất hiện của từng từ trong dữ liệu văn bản sau đó sẽ tiến hành loại bỏ những từ có số lần xuất hiện nhiều nhất, vì những từ xuất hiện nhiều nhất thƣờng là những từ không mang nhiều ý nghĩa. Sau khi xử lý stopwords, văn bản có thể xem nhƣ là một tập hợp các đặc trƣng, đó là tập hợp các từ quan trọng còn lại để biểu diễn văn bản. Việc phân loại văn bản sẽ dựa trên các đặc trƣng này.