Luận văn: Nghiên cứu giải thuật Naïve Bayes trong bài toán phân loại văn bản

Luận văn nghiên cứu sâu giải thuật Naïve Bayes cho bài toán phân loại văn bản. Phân tích, cài đặt và so sánh hiệu quả với thuật toán SVM.

• Tác giả: Tran Hoang Hiep
• Người hướng dẫn: GS. Nguyễn Thanh Thủy
• Trường học: Trường Đại học Bách Khoa Hà Nội
• Chuyên ngành: Công nghệ thông tin
• Đề tài: Giải thuật Naive Bayes trong bài toán phân loại văn bản
• Loại tài liệu: Luận văn Thạc sĩ
• Năm xuất bản: 2012
• Địa điểm: Hà Nội

Tóm tắt

I. Tổng quan về bài toán phân loại văn bản

Phân loại văn bản (Text Categorization) là một bài toán quan trọng trong lĩnh vực xử lý ngôn ngữ tự nhiên và khai phá dữ liệu. Với sự phát triển mạnh mẽ của internet và các dịch vụ truyền thông điện tử, lượng văn bản số hoá tăng exponentially hàng ngày. Việc tự động phân loại văn bản thành các danh mục khác nhau trở nên cần thiết để giúp người dùng quản lý và tìm kiếm thông tin hiệu quả hơn. Ứng dụng phân loại văn bản rất đa dạng như lọc email spam, phân loại tài liệu, phân tích tâm luận, và các hệ thống đề xuất nội dung. Bài toán này đòi hỏi các thuật toán máy học tiên tiến để đạt độ chính xác cao.

1.1. Nhu cầu và ý nghĩa của phân loại văn bản

Sự phát triển của mạng truyền thông và dịch vụ email tạo ra khối lượng lớn thư rác (spam) và tin nhắn không mong muốn. Người dùng cần công cụ tự động để phân loại và lọc nội dung. Các phương pháp truyền thống dùng từ khoá hoặc blacklist có hiệu quả hạn chế. Do đó, phân loại dựa trên nội dung văn bản sử dụng thuật toán máy học như Naive Bayes và SVM là giải pháp hiệu quả và cần thiết.

1.2. Các thách thức trong phân loại văn bản

Phân loại văn bản gặp nhiều thách thức như đặc trưng dữ liệu cao chiều, độ thưa của ma trận từ, và sự đa nghĩa của ngôn ngữ tự nhiên. Cần tiền xử lý dữ liệu và kỹ thuật trích chọn đặc trưng tốt. Cải tiến thuật toán là chìa khóa để nâng cao độ chính xác phân loại.

II. Giải thuật Naive Bayes trong phân loại văn bản

Naive Bayes là một thuật toán học máy dựa trên định lý Bayes và giả định độc lập có điều kiện giữa các đặc trưng. Đây là phương pháp phổ biến và hiệu quả cho bài toán phân loại văn bản vì tính đơn giản, nhanh chóng và dễ cài đặt. Công thức xác suất Bayes cơ bản là: P(C|X) = P(X|C)P(C)/P(X), trong đó C là lớp văn bản và X là các từ. Luận văn tập trung nghiên cứu Multinomial Naive Bayes và các cải tiến như Weight-normalized Complement Naive Bayes (WCNB) và Transformed Weight-normalized Complement Naive Bayes (TWCNB) để cải thiện hiệu quả phân loại so với phương pháp chuẩn.

2.1. Định lý Bayes và phân bố Multinomial

Định lý Bayes là nền tảng toán học của Naive Bayes classifier. Phân bố Multinomial được sử dụng để mô hình hoá tần suất xuất hiện của các từ trong văn bản. Công thức Bayes tính xác suất một lớp C cho trước quan sát X dựa vào xác suất có điều kiện. Giả định độc lập Naive giúp giảm độ phức tạp tính toán và làm cho mô hình dễ hiểu.

2.2. Các cải tiến Naive Bayes

Multinomial Naive Bayes (MNB) là phiên bản chuẩn nhưng có độ lệch cao. Complement Naive Bayes (CNB) sử dụng bù ngược để cải thiện hiệu quả. WCNB và TWCNB là các cải tiến heuristic tiếp theo, sử dụng chuẩn hoá trọng số và biến đổi để nâng cao độ chính xác phân loại với tập dữ liệu không cân bằng.

III. Giải thuật Support Vector Machine SVM

Support Vector Machine (SVM) là một thuật toán học máy mạnh mẽ sử dụng phân tách tuyến tính trong không gian đặc trưng để phân loại dữ liệu. Lý thuyết SVM dựa vào việc tìm siêu phẳng tối ưu có khoảng lề (margin) cực đại. Các khái niệm quan trọng bao gồm điều kiện Karush-Kuhn-Tucker (KKT) và lý thuyết đối ngẫu (Duality). SVM phi tuyến sử dụng hàm nhân (kernel function) để ánh xạ dữ liệu lên không gian chiều cao, giúp giải quyết các bài toán không tách được tuyến tính. Luận văn so sánh hiệu quả của SVM với Naive Bayes trong phân loại văn bản trên các tập dữ liệu mẫu.

3.1. Nguyên lý và tối ưu hoá SVM

SVM tìm siêu phẳng tối ưu bằng cách cực tiểu hoá hàm lỗi với ràng buộc khoảng lề cực đại. Bài toán đối ngẫu (Duality) được giải quyết bằng phương pháp giảm đạo hàm. Điều kiện KKT đảm bảo nghiệm tối ưu. Soft margin cho phép lỗi phân loại tùy chỉnh để tránh overfitting.

3.2. SVM phi tuyến và hàm nhân

Hàm nhân (kernel function) như RBF kernel hoặc polynomial kernel giúp SVM xử lý dữ liệu phi tuyến. Thuật toán Sequential Minimal Optimization (SMO) được sử dụng để tối ưu hoá SVM hiệu quả. SVM đa lớp được triển khai bằng cách kết hợp SVM nhị phân.

IV. Kết quả thực nghiệm và đánh giá

Luận văn tiến hành thử nghiệm cả hai giải thuật Naive Bayes và SVM trên ba bộ dữ liệu mẫu bao gồm 20 Newsgroups, WebKB, và Reuters-21578. Phương pháp đánh giá sử dụng các chỉ số hiệu suất như độ chính xác (Accuracy), Precision, Recall, và F-measure. Kết quả cho thấy cải tiến TWCNB đạt hiệu quả gần tương đương với SVM nhưng có thời gian huấn luyện nhanh hơn đáng kể. Thực hiện kiểm chứng trên các tập dữ liệu đa dạng để đánh giá tính khái quát của mô hình.

4.1. Bộ dữ liệu và cài đặt thực nghiệm

20 Newsgroups chứa 18,846 tin nhắn từ 20 nhóm tin tức khác nhau. WebKB gồm 8,282 trang web từ 4 loại. Reuters-21578 là tập dữ liệu văn bản tin tức lớn với hàng chục danh mục. Cài đặt sử dụng Python hoặc Java với các thư viện máy học như scikit-learn.

4.2. Phân tích kết quả và kết luận

Kết quả thử nghiệm cho thấy TWCNB đạt F-measure cao trên tất cả các bộ dữ liệu. SVM vẫn là lựa chọn tốt nhất nhưng chi phí tính toán cao hơn. Naive Bayes cải tiến là giải pháp cân bằng giữa hiệu quả và tốc độ, thích hợp cho ứng dụng thực tế.

Trích đoạn nội dung tài liệu

CHƯƠNG 1. TỎNG QUAN VỀ BÀI TOÁN PHAN LOAI VAN BAN 1. SU CAN THIET CUA VIEC PHÂN LOẠI VĂN BẢN 1. Phân loại văn bản cùng với các ứng dụng Quả trình phân loại văn bản nhằm mục đích xác định một văn bản (document) cho trước thuộc lớp ngữ nghĩa được xác định trước.

Với mục đích ấy, việc phân loại văn bản được áp dụng rất nhiều trong cuộc sống hiện tại, ứng dụng eu thẻ nhất đó là sắp xép lại tập các văn bản, thành các nhóm để cỏ thể thuận lợi cho việc tra cứu, tìm kiếm. Don giản như khi vào thư viên, người đọc có thể xác định được nhanh chỏng quyền sách mình muốn tìm dựa vào các phân loại sách trong thư viện. Một trang web tin tức với các bải viết được sắp xếp theo nội dung sẽ giúp người đọc thuận tiện cho chuyên mục mình thích, cũng như giúp họ có thể nhanh chỏng tìm đến những bài bảo với nội dung mong muôn Tin nhanh VnExpress - Đọc báo. tin tức online 24h Ø viiexpressneU - Chặn tắt cã các kết quã của vnexprsss net Thông lin nhanh & mới nhất được cắp nhát hàng giờ.

Tin tức Viết Nam & thể giới vễ xã hội, kinh doanh, pháp luật. khoa hoe, công nghã. sức khoẻ, đởi sống, văn. Xem kết quả khác trong 24 qiờ qua Thể thao Ø Văn hóa Ø Tin nhanh video clip hinh ãnh các môn Thông tin vân hóa van nghệ Việt Nam thé thao: bang da quyén.

& quéc t& hoa hau, aghé. Pháp luật Ø - Thông tín nhanh nóng & mới nhất về n giới nhanh nhất - mới pháp luật hình sự, ghỉ chép. nhất - nồng nhất trong ngây. Xã hội Ø Kinh doanh Ø Xem video clip & đọc tin nhanh nhất - Tin tive kinh doanh, câu chuyên mới nhất - nóng nhất vẻ.

doanh nhân & doanh nghiệp. Các kết quả khác từ vnexpress net » Hình 1. Các bài viết trên trang web được sắp xếp theo mục Việc thực biện phân loại ngoài mục đích trên còn có thể giúp những người làm việc nhiều với các hệ thống email, tin nhắn có thẻ phân loại các thông tin mình nhậu được thành các nhôm ruột cách tự động từ đó có thể dể dâng tìm được những thông tin quan trọng. Những mail gửi đến cỏ thể được phân loại thành những mai] Trang 2 Luận văm Lốt righiiỆp Nghiên cứu giải thuật NB trong bai todn TC LOI MO BAU Sự phát triển của khoa học công nghệ, đặc biệt là mạng truyền thông, không chỉ đáp mg như cầu thông tin hàng ngày, mà còn tạo ra những dich vụ trợ giúp cho mọi người.

Việc người dùng trên mạng truyền thông trong đổi thông từì qua những tin nhắn email, điễn đản (forum),. ngày cảng trở nên phế biến Củng với sự phát triển của dịch vụ gửi các thông tin qua các dịch vụ, cũng ngảy càng xuất hiện của những tin nhắn, thư rác với vô vân loại nội đưng khác nhau nhưng đa phần dé phiển nhiễu cho người đừng khi phải nhận dược những thông tin mày. ĐÀ người sử dụng tự động phân loại các tin nhắn, email như vậy, hiện có rất nhiều phân mềm cũng như dịch vụ hỗ trợ, các chương trình hiện tại thường sử dụng những từ khoá, blaoklist để phân loại, nhũng cách làm này có hiệu quả, nhưng không miệt dễ. Vì vậy cần dưa ra giải pháp phân loại các bn nhấn, cmaail như vậy dựa trên nội dung văn bản.

Chính lý do trên, luận văn sẽ tập trung tim hiéu về bài toán phân loại vén ban (Text Categorization). Với Luận văn này, em tập trung nghiên cứu sâu vảo bài toán cũng với 02 phương pháp dễ thực hiện phân loại văn bản dó là Naïve Bayes, va Support Vector Machine (SVM). Thực hiện phân loại trên các tập đũ liệu mẫu, vả đánh giá kết quả thủ được Các nội dụng cơ bản thục hiện Irong quả trình nghiên cứu: # Nghiên cửu giải thuật SVM nói chung và áp dụng cho bải toán phân loại văn bản nỏi riêng. & Tìm hiểu các cải tiến của giấu thuật Naive Bayes, cho kết quả phân loại tốt gần với giải thuật SVM.

Phương pháp thực hiện: & Xây dựng chương trình mô phỏng giái thuật. œ Thực hiện kiểm nghiệm trên các bộ đữ liệu mẫu. ‘Trang1 Luận văn tốt nghiệp Nghiên cứu giải thuật NB trong bài toán TC một lớp nảo đỏ. Vì vậy, việc xây dựng hệ thong phân loại sẽ được xây dựng là một hệ thông học cỏ giám sát (Supervised Leaming) trong lĩnh vực hoc may hay có thể nói là các văn bản sẽ được phân loại dựa trên một lượng các văn bản đã được phân loại sẵn.

Phân loại Với một văn bản bắt kỳ, mỗi khi được phân loại vào các lớp, văn bản sẽ được gán nhãn (label). Việc thực hiện phân loại có thể là đơn nhãn (single-label tức là mỗi văn bản chỉ thuộc vào một lớp nào đỏ) hoặc đa nhãn (multui-label tức là mỗi văn bản đ,cỏ thể thuộc vào một hoặc nhiều lớp khác nhau) Với bài toán TC đơn nhãn ta có thể đưa ra khẳng định mỗi văn bản có duy nhất một lớp é, sao cho ®(đ,,e,)= Trwe , Vị vậy ta cỏ thê viết lai ham ® trở thành hàm cỏ một tham số: ®: Doc © (@,)= c) néavan ban d, thude lope Bai toan TC nhi phan (binary TC) là một bài toán đơn nhãn đặc biệt, ở đây mỗi văn bản #: được phân loại thuộc lớp e hay không. Vì vậy ta có thể viết lại hàm ® trở thành: ® ¡ D—[TusFais ~ Í_ True-nễunh văn bản d,thuộc lớp c {Pelee~ nếu nhĩ văn bản đ, không thuộc lớpc Đối với bải toán TC đa nhãn cỏ thẻ được coi như một tập hợp |C| các bài toản TC nhị phân mỗi hàm sẽ thực hiện phân loại có thuộc lớp ¢ hay khéng: D = {04 Og Decq} Oo + Do feng} oa) = True~ nếu nhĩ văn ban d, thude lop ¢, ws ‘alse - nếu nhữ văn bản d, không thuộc Jo'p ¢ 1. TONG QUAN VE KHAI PHA DU LIEU Khả năng xây dựng một máy cỏ khả năng “học” từ những kinh nghiệm đã là một đề tải tranh luận giữa các nha khoa học.

Nhờ xuất hiện máy tính điện tử, việc xây dựng những cỗ máy có khả năng “học” đã được hỗ trợ rất nhiều vả đem lại nhiều kết quả mới. Những kết quả này đã thể hiện được rằng có thể thiết kế được những máy có thẻ thể hiện một cấp độ nảo đó của kha năng “học”, nhưng những, định nghĩa rõ ràng vẻ danh giới của việc thể hiện này vấn còn đang được lảm rõ. Trang Š Luận văm Lốt righiiỆp Nghiên cứu giải thuật NB trong bai todn TC LOI MO BAU Sự phát triển của khoa học công nghệ, đặc biệt là mạng truyền thông, không chỉ đáp mg như cầu thông tin hàng ngày, mà còn tạo ra những dich vụ trợ giúp cho mọi người. Việc người dùng trên mạng truyền thông trong đổi thông từì qua những tin nhắn email, điễn đản (forum),.

ngày cảng trở nên phế biến Củng với sự phát triển của dịch vụ gửi các thông tin qua các dịch vụ, cũng ngảy càng xuất hiện của những tin nhắn, thư rác với vô vân loại nội đưng khác nhau nhưng đa phần dé phiển nhiễu cho người đừng khi phải nhận dược những thông tin mày. ĐÀ người sử dụng tự động phân loại các tin nhắn, email như vậy, hiện có rất nhiều phân mềm cũng như dịch vụ hỗ trợ, các chương trình hiện tại thường sử dụng những từ khoá, blaoklist để phân loại, nhũng cách làm này có hiệu quả, nhưng không miệt dễ. Vì vậy cần dưa ra giải pháp phân loại các bn nhấn, cmaail như vậy dựa trên nội dung văn bản. Chính lý do trên, luận văn sẽ tập trung tim hiéu về bài toán phân loại vén ban (Text Categorization).

Với Luận văn này, em tập trung nghiên cứu sâu vảo bài toán cũng với 02 phương pháp dễ thực hiện phân loại văn bản dó là Naïve Bayes, va Support Vector Machine (SVM). Thực hiện phân loại trên các tập đũ liệu mẫu, vả đánh giá kết quả thủ được Các nội dụng cơ bản thục hiện Irong quả trình nghiên cứu: # Nghiên cửu giải thuật SVM nói chung và áp dụng cho bải toán phân loại văn bản nỏi riêng. & Tìm hiểu các cải tiến của giấu thuật Naive Bayes, cho kết quả phân loại tốt gần với giải thuật SVM. Phương pháp thực hiện: & Xây dựng chương trình mô phỏng giái thuật.

œ Thực hiện kiểm nghiệm trên các bộ đữ liệu mẫu. ‘Trang1 DANH MỤC CÁC HÌNH VẼ, ĐÒ THỊ "Hình 1. Các bài viet trin trang web được sấp xếp theo mục. Tháp mô tá quả trình đúc rút trí thắc từ dữ liệu - 8 Hình 3.

Phần bố xác xuất văn bản với xuất hiện của fÌ. Phân bê khí đ = 1 Hinh š. Phân bồ xác xuất suất hiện với số lần xuất biện của từ khỉ độ đài ấn bản khác nhau. Lái cắt phần loại được lạo bội siêu phẳng trong không gian phân loại được biểu diễu thông qua vector w và b ¬ sev 29 Bink 7.

Him foo) dat cue dai tat xo © 8. Ý nghĩa hình hạc của diễu kiện KẾT. - - wn BE Minh 9. Lựa chọn đường thẳng cho đlớn.

Hình 10 Tập mẫu gẵn phân tách tuyển tỉnh (khẳng thể phân tách tuyển tính được] - 39 Linh 11. Phan tach phi teyén nhưng chuyên đôi không gian để trẻ về tuyển tính. Thế liện của không gian cũ trong không gian mới. Phân boạch phí tuyển có nhiễu.

Hình 14, Chuyên thành siêu phẳng với hầm Gaussian RBP Hinh 15. One-vs-rest vii 4 lớp Hình !6.ác phẩm loại với SA (1,4) ¬ eevee a Hình 17. One-vs-one với 4 lớp. Quả trình gom cụm dễ xây đụng siêu phẳng.

trường hợp cả thế xảy ra với úị và tụ, - 52 Hình 20. Các trường hạp đạt cực trị của hàm. Cây thư naạc của dữ liệu WebKb, a 56 iv DANH MỤC CÁC KÝ HIỆU, CHỮ VIET TAT Text Classification, Text Categorization — phan loat van bản Information Reiriveal Support Vector Machine Dieu kién Karush-Kuln-Tucker Weight-normalized Complement Naive Bayes ‘Multinomial Naive Bayes Complement Naive Bayes Transformed Weignt-normalized Complement Naive Bayes Luận văn tốt nghiệp. ANghiên cứu giải thuật NB trong bài toán TC 1.

BÀI TOÁN PHÂN LOẠI VĂN BẢN 1. Định nghĩa Phân loại văn bản (Text Classiieation, hay còn có tên khác là Text Categorization hoae Topic spotting 6 day được viết tắt là TC) là hệ thông tự động phân loại và gán cho văn bản một tên lớp (Categorization, Class, hoặc Topic) đã được định nghĩa từ trước Xây dựng một hệ thông phân loại văn bản là sự kết hợp của hệ thống trích rút théng tin (Information Retriveal — viet tit IR) va hệ thống học máy (Machine Learning — viết tắt ML), 1.