Tài liệu Nghiên cứu áp dụng thuật toán multinomial bayes vào phân loại văn bản

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- NGUYỄN MỸ HẢO NGHIÊN CỨU ÁP DỤNG THUẬT TOÁN MULTINOMIAL BAYES VÀO PHÂN LOẠI VĂN BẢN LUẬN VĂN THẠC SĨ KỸ THUẬT (Theo định hướng ứng dụng) HÀ NỘI - 2018 HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG --------------------------------------- NGUYỄN MỸ HẢO NGHIÊN CỨU ÁP DỤNG THUẬT TOÁN MULTINOMIAL BAYES VÀO PHÂN LOẠI VĂN BẢN Chuyên ngành : Hệ thống thông tin Mã số : 8.48.01.04 LUẬN VĂN THẠC SĨ KỸ THUẬT (Theo định hướng ứng dụng) NGƯỜI HƯỚNG DẪN KHOA HỌC : TS. NGUYỄN MẠNH HÙNG HÀ NỘI – 2018 i LỜI CAM ĐOAN Tôi cam đoan luận văn thạc sĩ “Nghiên cứu áp dụng thuật toán Multinomial Bayes vào phân loại văn bản” là công trình nghiên cứu của riêng tôi. Các số liệu, kết quả nêu trong luận văn là trung thực và chưa từng được ai công bố trong bất kỳ công trình nào khác. Tất cả những tham khảo và kế thừa đều được trích dẫn và tham chiếu đầy đủ. Tác giả luận văn Nguyễn Mỹ Hảo ii MỤC LỤC LỜI CAM ĐOAN ....................................................................................................... i MỤC LỤC .................................................................................................................. ii DANH MỤC HÌNH VẼ ............................................................................................ iv MỤC LỤC BẢNG BIỂU ............................................................................................v DANH MỤC TỪ VIẾT TẮT .................................................................................... vi MỞ ĐẦU .....................................................................................................................1 CHƯƠNG 1: GIỚI THIỆU BÀI TOÁN PHÂN LOẠI ..............................................3 VĂN BẢN ...................................................................................................................3 1.1.Giới thiệu bài toán phân loại văn bản ...................................................................3 1.1.1. Mở đầu .......................................................................................................4 1.1.2. Bài toán phân loại văn bản .........................................................................6 1.1.3. Ứng dụng của bài toán phân loại văn bản..................................................8 1.2.Các phương pháp phân loại văn bản ...................................................................10 1.2.1. Phương pháp Navie Bayes .......................................................................10 1.2.2. Phương pháp K – Nearest Neighbor ........................................................12 1.2.3. Phương pháp Multinomial Logistic regression .......................................14 1.3. Kết luận ..............................................................................................................18 CHƯƠNG 2: PHƯƠNG PHÁP MULTINOMIAL BAYES TRONG BÀI TOÁN PHÂN LOẠI VĂN BẢN ..........................................................................................19 2.1 Biểu diễn văn bản ................................................................................................19 2.1.1. Tiền xử lý văn bản ...................................................................................20 2.1.2. Kỹ thuật Bag of word...............................................................................25 2.1.3. Trọng số TF-IDF ......................................................................................26 2.2. Thuật toán Multinomial Bayes ...........................................................................28 2.2.1. Ý tưởng ....................................................................................................28 2.2.2. Nội dung thuật toán..................................................................................28 2.2.3. Ví dụ các bước của phương pháp Multinomial Bayes ............................30 2.3.4. Ưu điểm phương pháp Multinomial Bayes trong phân loại văn bản ......33 iii 2.3. Kết luận ..............................................................................................................33 CHƯƠNG 3 - THỰC NGHIỆM VÀ ĐÁNH GIÁ ...................................................34 3.1. Giới thiệu về bộ dữ liệu sử dụng ........................................................................34 3.2. Sơ đồ chương trình phân loại văn bản ...............................................................35 3.3. Tiền xử lý dữ liệu ...............................................................................................36 3.4. Biểu diễn văn bản thành vector ..........................................................................37 3.5. Các tiêu chuẩn đánh giá .....................................................................................38 3.6. Phương pháp thực nghiệm .................................................................................40 3.6.1. Công cụ dùng để phân lớp .......................................................................40 3.6.2. Xây dựng dữ liệu huấn luyện và kiểm tra ................................................40 3.7. Kết quả thực nghiệm ..........................................................................................41 3.8. So sánh với một số phương pháp khác...............................................................44 3.9. Kết luận ..............................................................................................................45 KẾT LUẬN ...............................................................................................................46 DANH MỤC TÀI LIỆU THAM KHẢO ..................................................................48 iv DANH MỤC HÌNH VẼ Hình 1. 1 Thời gian trung bình sử dụng internet trong 1 ngày của người Việt Nam..4 Hình 1.2 Các hoạt động trực tuyến được người dùng mạng sử dụng .........................5 Hình 1.3 Quy trình bài toán phân loại văn bản ...........................................................7 Hình 1.4 Mô hình giai đoạn huấn luyện ......................................................................8 Hình 1. 5 Mô hình giai đoạn phân lớp ........................................................................8 Hình 1. 6 Ví dụ bài toán phân loại trên báo điện tử VNExpress ................................9 Hình 1.7 Đồ thị hàm sigmoid 𝝈(𝒂) ..........................................................................15 Hình 2.1 Hình ảnh mô tả bước tiền xử lý..................................................................21 Hình 2.2 Các bước tiền xử lý văn bản .......................................................................21 Hình 2.3 Ví dụ cách biểu diễn Bang of word............................................................25 Hình 3.1 Minh họa một văn bản trong thư mục “rec.autos” .....................................34 Hình 3.2 Mô hình phân loại văn bản áp dụng thuật toán Multinomial Bayes ..........36 Hình 3.3 Tập tin “Data” sau khi đã được thực hiện xử lý .........................................37 v MỤC LỤC BẢNG BIỂU Bảng 1.1 Các bài toán phân loại trong ngôn ngữ tự nhiên..........................................3 Bảng 2.1 Các nghiên cứu về biểu diễn văn bản [6] ..................................................19 Bảng 2.2 Bảng dữ liệu bộ tài liệu gồm D1 – D5 .......................................................30 Bảng 2.3 Bảng dữ liệu để cần phân loại gồm D6 – D7.............................................30 Bảng 2.4 Bảng tính toán khả năng đối với loại AUTO .............................................32 Bảng 3.1 Danh sách phân bố dữ liệu trong 20 nhóm ................................................35 Bảng 3.2 Kết quả lần kiểm tra Fold #1 .....................................................................42 Bảng 3.3 Kết quả trung bình của lần chạy Fold #1 ...................................................43 Bảng 3.4 Kết quả thực nghiệm thuật toán Multinomial Bayes với 5 phần Cross validation ...................................................................................................................44 Bảng 3.5 Kết quả thực nghiệm thuật toán Multinomial Logistic Regression với 5 phần cross - validation ..............................................................................................45 vi DANH MỤC TỪ VIẾT TẮT Từ viết Ý nghĩa tiếng Anh Ý nghĩa tiếng Việt FN False Positive Số sai âm FP False Positive Số sai dương KNN K – Nearest Neighbor Thuật toán K – Nearest tắt Neighbor NB Naïve Bayes Thuật toán Naïve Bayes TN True Negative Số đúng âm TP True Positive Số đúng dương 1 MỞ ĐẦU Trong những năm gần đây, với sự phát triển của các siêu phương tiện và các World Wide Web (WWW)…Với số lượng lớn người dùng và thông tin liên tục được cập nhật từ đến mọi vấn đề trong đời sống, xã hội, kinh tế, giải trí… Điều này tạo ra thách thức lớn cho việc truy vấn có hiệu quả của các hệ thống truy vấn thông tin. Một trong những khó khăn mà các hệ thống thông tin thường phải gặp đó là tần suất cập nhật của các thông tin quá lớn. Phương thức sử dụng giấy trong giao dịch đang dần được số hóa, do nhiều tính năng vượt trội mà phương thức này mang lại, như là có thể lưu trữ lâu dài, cập nhật, sửa đổi, tìm kiếm một cách nhanh chóng. Do đó số lượng văn bản số hóa ngày nay đang tăng dần theo cấp số nhân, cùng với sự gia tăng của số lượng văn bản, nhu cầu tìm kiếm văn bản cũng tăng theo, khi đó phân loại văn bản tự động là một yêu cầu cấp thiết được đặt ra. Phân loại văn bản giúp sẽ giúp chúng ta tìm kiếm thông tin một cách nhanh chóng hơn thay vì phải tìm lần lượt trong từng văn bản, hơn nữa khi mà số lượng văn bản đang gia tăng một cách nhanh chóng thì thao tác tìm lần lượt trong từng văn bản sẽ mất rất nhiều thời gian, công sức và là một công việc nhàm chán và không khả thi. Chính vì thế nhu cầu phân loại văn bản tự động là thực sự cần thiết. Xuất phát từ thực trạng đang xảy ra, luận văn sẽ trình bày về phương pháp phân loại văn bản áp dụng thuật toán Multinomial Bayes giúp người dùng có thể dễ dàng hơn trong việc tìm kiếm thông tin cần thiết, đồng thời có thể lưu trữ thông tin theo đúng chủ đề mong muốn. Luận văn sẽ được cấu trúc với các chương như sau: Chương 1 : Giới thiệu bài toán phân loại văn bản - Chương này đã giới thiệu về bài toán phân loại văn bản các ứng dụng thực tế của bài toán trong môi trường công nghiệp. Tiếp theo, trình bày 3 phương pháp được sử dụng trong bài toán phân loại văn bản là: Naive Bayes, K - Nearest Neighbor và Multinomial Logistic Regression gồm các nội dung lịch sử, ý tưởng và cách thuật toán thực hiện. 2 Chương 2 : Phương pháp Multinomial Bayes trong bài toán phân loại văn bản - Chương 2 của luận văn tập trung vào trình bày thuật toán Multinomial Bayes cơ sở lý thuyết và áp dụng trong bài toán phân loại văn bản. Chương 3: Thực nghiệm và đánh giá – Nội dung của chương 3 là cách thức mô tả dữ liệu và chuẩn hóa bộ dữ liệu 20 Newsgroups được sử dụng trong luận văn. Các bước tiền xử lý dữ liệu, chạy thuật toán phân loại Multinomial Bayes với tập dữ liệu 18758 văn bản với công cụ Apache Spark MLLib. 3 CHƯƠNG 1: GIỚI THIỆU BÀI TOÁN PHÂN LOẠI VĂN BẢN 1.1.Giới thiệu bài toán phân loại văn bản Phân loại văn bản là một vấn đề trong lĩnh vực xử lý ngôn ngữ. Đặ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. Nhiệm vụ của bài toán này là gán các tài liệu văn bản vào nhóm các chủ đề cho trước [4]. Mỗi bài toán phân loại đều có đối tượng thao tác và mục tiêu phân loại khác nhau. Trong bài toán phân loại văn bản, một văn bản (Document hay text) là đối tượng nội dung cần thao tác. Bảng 1.1 Các bài toán phân loại trong ngôn ngữ tự nhiên Vấn đề Gán nhãn từ loại (POS tagging) Gán nhãn ngữ tính từ (Prepositional Phrase Attachment) Khử nhập nhằng nghĩa từ vựng (Word Sense Disambiguration) Phân loại văn bản (Text categorization) Đối tượng Phân loại Ngữ cảnh của một từ Nhãn của từ Câu Phân tích câu Ngữ cảnh của một từ Câu Văn bản Chủ đề 4 1.1.1. Mở đầu Ngày nay, số lượng các tài liệu điện tử tăng lên một cách nhanh chóng từ nhiều nguồn khác nhau, nguồn thông tin này đến từ các thư viện điện tử, thư điện tử, trang web. Việc khám phá tri thức tiềm ẩn từ kho dữ liệu văn bản là cần thiết cho việc quản lý, khai thác triệt để nguồn thông tin văn bản khổng lồ này. Các tri thức có thể là mô hình gom cụm hay phân lớp văn bản, mà ở đó mô hình phân lớp được sử dụng phổ biến trong ứng dụng như: gán nhãn tự động một bản tin, phân tích nội dung để phát hiện nhóm khủng bố, nhận dạng thư rác vì thế các nghiên cứu về khai phá dữ liệu dạng văn bản cũng được quan tâm hơn. Người dùng internet thường có thói quen tìm kiếm thông tin thông qua các bài báo, tài liệu kinh doanh, thương mại điện tử, ... Tại Việt Nam, số người dùng internet được xem là ở mức cao trên thế thời. Theo thống kê của We are social – Công ty chuyên thực hiện các thống kê và đánh giá về thông số kỹ thuật số, di động và các lĩnh vực liên quan: Trung bình 1 ngày, người Việt Nam bỏ ra 6 giờ 53 phút để duyệt web nếu xài PC và Tablet, 2 giờ 33 phút nếu xài điện thoại di động. Hình 1. 1 Thời gian trung bình sử dụng internet trong 1 ngày của người Việt Nam (Nguồn: We are social) Nhìn chung, hoạt động thực hiện thường xuyên nhất trên Internet của người dùng là thu thập thông tin, như đọc tin tức hay sử dụng các trang web tìm kiếm. Hơn 90% số lượng người sử dụng Internet đã sử dụng những trang web tìm kiếm, 5 khoảng một nửa trong số họ thậm chí sử dụng hàng ngày. Internet cũng được sử dụng để nghiên cứu cho việc học hay cho công việc bởi một nửa số người sử dụng Internet 1 lần 1 tuần hay thường xuyên hơn. Với các trang web và ứng dụng tương tác trực tuyến mới, người sử dụng không chỉ có cơ hội tìm được thông tin mà cũng đóng góp phần nội dung của riêng họ. Thương mại điện tử hiện nay, số lượng truy cập đạt mức tăng trưởng đáng kể. Hầu hết các trang phổ biến là các trang web đấu giá và mua bán, nơi có 40% người sử dụng đã từng viếng thăm. Ngân hàng trực tuyến vẫn đang ở giai đoạn sơ khai. Mức độ sử dụng các trang web mua hàng trực tuyến và ngân hàng trực tuyến đã phát triển rất mạnh trong vòng vài năm trở lại đây. Hình 1.2 Các hoạt động trực tuyến được người dùng mạng sử dụng (Nguồn: Cimigo NetCitizens) Trong các hoạt động và truy cập internet, việc phân loại, chọn lọc, tìm kiếm thông tin cần thiết, phù hợp với mục đích công việc là cần thiết. Việc phân loại có thể được tiến hành một cách thủ công: đọc nội dung của từng hoạt động và gán nó vào một nhãn nào đó. Tuy nhiên, đối với hệ thống gồm rất bản ghi hoặc với nguồn dữ liệu lớn thì phương pháp này sẽ tốn rất nhiều thời gian và công sức. Do vậy cần phải có phương pháp tự động để phân loại văn bản. 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, chiết lọc thông tin, lọc văn bản hoặc tự động dẫn đường cho các văn 6 bản tới những chủ đề xác định trước. Phân lớp 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. Từ thực tế về nhu cầu tìm kiếm trong kho văn bản điện tử khổng lồ và việc tìm kiếm thủ công là không khả thi, khi đó, bài toán phân loại văn bản đã, đang và sẽ được nghiên cứu, cải tiến và áp dụng vào thực tế ngày một nhiều. 1.1.2. Bài toán phân loại văn bản Phát biểu bài toán phân loại văn bản: Đầu vào: Cho x là một văn bản, biết x thuộc một trong các nhóm(chủ đề) {1, 2 ,..., K}. Đầu ra: Hãy nhóm đúng nhất với x. Ví dụ: Giả sử x là một bài báo của bạn gửi đăng trên trang web điện tử. Biên tập viên cần quyết định xem x thuộc chủ đề nào là tích hợp nhất: “ showbiz”, “ẩm thực”, “thể thao”,... Giả sử x là một văn bản ngắn có mục tiêu điều khiển điều hòa. Mỗi thể loại ứng với một hành động điều khiển: “ tắt”, “bật”, “chuyển chế độ gió”,... Gọi y = ℎ∅ (x) là hàm phân loại của x trong đó ∅ là tham số của hàm. Ta cần tìm ℎ∅ (. ) có khả năng phân loại tốt. Để tìm ℎ∅ , ta sử dụng phương pháp học có hướng dẫn từ dữ liệu mẫu: - Dữ liệu học gồm N mẫu: (𝑥1 , 𝑦1 ), (𝑥2 , 𝑦2 ), ..., (𝑥𝑁 , 𝑦𝑁 ). - Hàm ℎ∅ được xây dựng sao cho phù hợp nhất với dữ liệu huấn luyện. Mỗi văn bản x là một đối tượng cần phân loại, thông thường x được chuyển thành một biểu diễn vector thực D chiều: x = {𝑥1 , 𝑥2 ,.., 𝑥𝐷 } , 𝑥𝑗  𝓡 Các thành phần 𝑥𝑗 , 𝑗 = 1, 2, … , 𝐷 được gọi là đặc trưng hay thuộc tính của x. Dưới đây là hình vẽ mô tả quy trình của bài toán phân loại văn bản: 7 Hình 1.3 Quy trình bài toán phân loại văn bản Để tiến hành phân loại văn bản nói chung, chúng ta sẽ thực hiện theo 2 phần chính là: huấn luyện và phân loại. - Huấn luyện: Các văn bản đầu vào với nhãn đúng được trích chọn đặc trưng và đưa vào thuật toán học để huấn luyện mô hình dự đoán phù hợp. 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 hoặc nhiều lớp mà chúng ta sẽ thể hiện chúng bằng một mô hình mã hóa. 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à vecto biểu diễn cho văn bản trong tập huấn luyện. Sau đó, đị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. 8 Hình 1.4 Mô hình giai đoạn huấn luyện Đầu vào: ngữ liệu huấn luyện và thuật toán huấn luyện Đầu ra: Mô hình phân lớp - Phân loại: Văn bản mới được trích chọn đặc trưng và đưa vào mô hình đã được huấn luyện ở bước trên để dự đoán nhãn phù hợp nhất. Hình 1. 5 Mô hình giai đoạn phân lớp 1.1.3. Ứng dụng của bài toán phân loại văn bản Bài toán phân loại đang được sử dụng phổ biến hiện nay, ta có thể bắt gặp các ứng dụng của bài toán ở một số ví dụ như: - Công cụ phân loại mail rác (spam email) của Google – Gmail. Theo như công bố đạt độ chính xác 99.9% năm 2017 (Theo vtv công nghệ - Báo điện tử thuộc đài truyền hình Việt Nam: https://vtv.vn/cong-nghe/gmail-cap-nhat-co-cau-tu-hocgiup-ngan-chan-thu-rac-va-tin-nhan-lua-dao-20170602062734311.htm). Theo đó, google áp dụng các kỹ thuật phân loại văn bản để kiểm tra nội dung bức thư đến tự động và phát hiện được email đó là có phải là spam email hay không để cho vào mục “Spam” riêng. 9 - Báo vnexpress.net phục vụ 37,5 triệu người đọc thường xuyên và đạt 1,2 tỷ lượt xem mỗi tháng, đăng gần 500 tin bài mỗi ngày (số liệu 2016 http://chungta.vn/tin-tuc/kinh-doanh/vnexpress-dat-12-ty-luot-xem-mot-thang48730.html). VnExpress, đã áp dụng phương pháp phân loại văn bản phân loại tin bài (gợi ý bài viết liên quan, khuyến nghị những bài báo phù hợp với người dùng từ những bài báo trước đó đã đọc, marketing những sản phẩm phù hợp từ những bài báo người dùng quan tâm,…). Dưới hình ta sẽ thấy khi vào đọc một bài báo, VNExpress sẽ giới thiệu cho ta nhưng bài báo có nội dung tương tự với bài ta đang đọc nhờ vào thuật toán phân loại văn bản tự động. Hình 1. 6 Ví dụ bài toán phân loại trên báo điện tử VNExpress 10 1.2.Các phương pháp phân loại văn bản Để giải bài toán phân loại văn bản, đã có nhiều phương pháp được nghiên cứu như: Naive Bayes, Multinomial Logistic regression, K-Nearest Neighbor, Multinomial Bayes... Để tìm hiểu và so sánh rõ hơn sự khác biệt và tối ưu với phương pháp dùng thuật toán Multinomial Bayes, một số thuật toán phân loại văn bản sau sẽ được phân tích sâu hơn: 1.2.1. Phương pháp Navie Bayes Naive Bayes là thuật toán phân loại dựa trên định lý Bayes. Định lý Bayes thường được dùng trong lý thuyết xác suất, cho phép tính xác xuất xảy ra sự kiện A khi biết sự kiện liên qua B đã xảy ra [2]. Xác suất này được ký hiệu là P(A|B), và đọc là “xác suất của A nếu có B”. Xác suất này có công thức như sau: (1.1) 𝑃(𝐴|𝐵) = 𝑃(𝐵|𝐴)𝑃(𝐴) 𝑃(𝐵) Trong đó: - P(A): Xác suất xảy ra sự kiện A. - P(B): Xác suất xảy ra sự kiện B. - P(B|A): Xác suất xảy ra sự kiên B khi biết sự kiện A đã xảy ra. Phương pháp Navie Bayes được sử dụng lần đầu tiên trong lĩnh vực phân loại bởi Maron vào năm 1961, sau đó trở nên phổ biến trong nhiều lĩnh vực như trong các công cụ tìm kiếm, các bộ lọc mail… Ý tưởng Ý tưởng của phương pháp là sử dụng xác suất có điều kiện giữa từ và chủ đề để dự đoán xác suất chủ đề của một văn bản phân loại. Điểm quan trọng của phương pháp này chính là ở chỗ để ứng dụng định lý Bayes cần 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. Giả định đó làm cho việc tính toán Navie Bayes hiệu quả và nhanh chóng hơn các phương pháp khác với độ phức 11 tạp theo số mũ vì nó không sử dụng việc kết hợp các từ để đưa ra phán đoán chủ đề do đó bước training và testing trở nên vô cùng nhanh chóng và đơn giản. Giả định đó làm cho việc tính toán Navie Bayes 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 việc kết hợp các từ để đưa ra phán đoán chủ đề [17]. Công thức chính Mục đích chính là tính 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 sau dùng để tính Pr (Cj, d’) [17]: HBayes (d’) = arg Cj 𝜖 C max( |𝑑′ | Pr(𝐶𝑗 ).∏𝑖=1 Pr(𝑤𝑖 |𝐶𝑗 ) (1.2) ) |𝑑′ | ∑𝐶′ 𝜖𝐶 Pr(𝐶 ′ ).∏𝑖=1 Pr(𝑤𝑖 |𝐶 ′ ) = arg Cj 𝜖 C max(∑ Pr(𝐶𝑗 ).∏𝑤𝜖𝐹 Pr(𝑤 |𝐶𝑗 )𝑇𝐹(𝑤,𝑑′) 𝐶′ 𝜖𝐶 Pr(𝐶 ′ ).∏ ′ 𝑇𝐹(𝑤.𝑑′ ) 𝑤𝜖𝐹 Pr(𝑤𝑖 |𝐶 ) ) Trong đó: - TF(w, d’) là số lần xuất hiện của từ wi trong văn bản d’  |d’| là số lượng 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 trong tập dữ liệu huấn luyện: Pr(Cj) = - ||𝐶𝑗 || ||𝐶|| =∑ ||𝐶𝑗 || ′ 𝐶′ 𝜖 𝐶 ||𝐶 || (1.3) Pr(wi | C) được tính sử dụng phép ước lượng Laplace Pr(𝑤𝑖 |𝐶𝑗 ) = 1 + 𝑇𝐹(𝑤𝑖 , 𝐶𝑗 ) |𝐹 | + ∑𝑤′𝜖 |𝐹| 𝑇𝐹(𝑤 ′ , 𝐶𝑗 ) (1.4) Naive 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 tồi nếu dữ liệu huấn luyện ít, nghèo nàn và các tham số dự đoán (không 12 gian đặc trưng) có chất lượng kém. Nói 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ủ đề. Naive Bayes có ưu điểm là cài đặt đơn giản, tốc độ nhanh, dễ dàng cập nhật dữ liệu huấn luyện, có thể sử dụng kết hợp nhiều tập huấn luyện khác nhau để đưa ra kết quả phân loại văn bản. Nhược điểm của phương pháp Naive Bayes: Do trong thực tế giả định của phương pháp là 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 rất hiếm khi xảy ra do đó độ chính xác của phương pháp so với các phương pháp khác thường không cao [17]. 1.2.2. Phương pháp K – Nearest Neighbor Phương pháp K – Nearest Neighbor dựa trên thuật toán K-Nearest Neighbors (K-NN) được sử dụng rất phổ biến trong lĩnh vực Data Mining (phân tích dữ liệu). K-NN là phương pháp để phân lớp các đối tượng dựa vào khoảng cách gần nhất giữa đối tượng cần xếp lớp (Query point) và tất cả các đối tượng trong Training Data (tập dữ liệu huấn luyện). Một đối tượng được phân lớp dựa vào K láng giềng của nó. K là số nguyên dương được xác định trước khi thực hiện thuật toán. Người ta thường dùng khoảng cách Euclidean để tính khoảng cách giữa các đối tượng. Mô tả thuật toán: 1. Xác định giá trị tham số K (số láng giềng gần nhất) 2. Tính khoảng cách giữa đối tượng cần phân lớp (Query Point) với tất cả các đối tượng trong training data (thường sử dụng khoảng các Euclidean) 3. Sắp xếp khoảng cách theo thứ tự tăng dần và xác định K láng giềng gần nhất với Query Point 4. Lấy tất cả các lớp của K láng giềng gần nhất đã xác định 5. Dựa vào phần lớn lớp của láng giềng gần nhất để xác định lớp cho Query Point