Chương 1 - BÀI TOÁN PHÂN LOẠI VĂN BẢN 1. Phát biểu bài toán phân loại văn bản Phân loại văn bản (hay Text Categorization hoặc Document Classificant) là quá trình gán các văn bản vào một hay nhiều chủ đề đã biết trong một tập hữu hạn các chủ đề đã được xác định từ trước. Ví dụ một bài báo trong một trang web có thể thuộc một hoặc một vài chủ đề nào đó (như thể thao, giáo dục, pháp luật, công nghệ thông tin,…). 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 văn bản và gán nó vào một lớp nào đó.
Tuy nhiên, đối với hệ thống gồm rất nhiều văn bả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ương pháp này giúp cho việc lưu trữ và truy vấn tài liệu dễ dàng hơn. 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: Hình 1.1 Quy trình phân loại văn bản [11] Để tiến hành phân loại văn bản nói chung, chúng ta sẽ thực hiện các bước như sau: Bước 1: Xây dựng bộ dữ liệu huấn luyện dựa vào tài liệu văn bản đã được phân loại sẵn.
Tiến hành học cho bộ dữ liệu, xử lý và thu thập được dữ liệu của quá trình học là các đặc trưng riêng biệt cho từng chủ đề. Bước 2: Dữ liệu cần phân loại được xử lý, rút ra đặc trưng kết hợp với đặc trưng được học trước đó để phân loại và rút ra kết quả. 6 Đặ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 có thể dễ bị nhập nhằng.
Ví dụ có bài báo về tuyển dụng nhân viên bán thuốc tại một công ty dược phẩm, bài báo này có thể xếp vào chủ đề tuyển dụng lĩnh vực Y dược hoặc cũng có thể xếp vào chủ đề lĩnh vực Bán hàng. 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. Có thể liệt kê một số công trình nghiên cứu trong nước với các hướng tiếp cận khác nhau cho bài toán phân loại văn bản, bao gồm: phân loại với máy học vectơ hỗ trợ, cách tiếp cận sử dụng lý thuyết tập thô, cách tiếp cận thống kê hình vị, 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, cách tiếp cận theo luật kết hợp. Theo các kết quả trình bày trong các công trình đó thì những cách tiếp cận nêu trên đều cho kết quả khá tốt.
Tuy nhiên khó có thể so sánh các kết quả ở trên với nhau vì tập dữ liệu thực nghiệm của mỗi phương pháp là khác nhau. Trong những năm gần đây, phương pháp phân loại 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 nhận dạng và phân loại. SVM là một họ các phương pháp dựa trên cơ sở các hàm nhân (kernel) để tối thiểu hóa rủi ro ước lượng. Phương pháp SVM ra đời từ lý thuyết học thống kê 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.
Các thử nghiệm thực tế cho thấy, phương pháp SVM có khả năng phân loại khá tốt đối với bài toán phân loại văn bản cũng như trong nhiều ứng dụng khác (như 7 nhận dạng chữ viết tay, phát hiện mặt người trong các ảnh, ước lượng hồi quy,. So sánh với các phương pháp phân loại khác, khả năng phân loại của SVM là tương đương hoặc tốt hơn đáng kể. Vì những lý do đó mà em đã chọn phương pháp này cho việc phân loại văn bản tiếng Việt, cụ thể thuật toán và ứng dụng sẽ được trình bày trong các chương sau. Một số phương pháp phân loại văn bản Hiện nay trên thế giới đã có rất nhiều công trình nghiên cứu về các phương pháp phân loại văn bản.
Một số phương pháp cần kể đến là: Naïve Bayes, Support Vector Machine, K–Nearest Neighbor, Linear Least Squares Fit, Neural Network… Điểm chung của các phương pháp này đều dựa vào xác suất thống kê hoặc dựa vào trọng số của các từ, cụm từ trong văn bản. Trong mỗi phương pháp đều có cách tính toán khác nhau, tuy nhiên các phương pháp này đều phải thực hiện một số bước chung như: mỗi phương pháp sẽ dựa vào thông tin về sự xuất hiện của các từ trong văn bản (tần số xuất hiện trong tập văn bản…) để biểu diễn thành dạng vector, sau đó tùy từng bài toán cụ thể sẽ quyết định chọn áp dụng phương pháp nào, công thức tính toán nào cho phù hợp để phân loại tập văn bản dựa trên tập các vector đã xây dựng được ở bước trên, nhằm mục đích đạt được kết quả phân loại tốt nhất. Thuật toán K–Nearest Neighbor (kNN) a. Giới thiệu Đây là phương pháp truyền thống khá nổi tiếng về hướng tiếp cận dựa trên thống kê đã được nghiên cứu trong nhận dạng mẫu hơn bốn thập kỷ qua.
kNN được đánh giá là một trong những phương pháp tốt nhất (áp dụng trên tập dữ liệu Reuters), được sử dụng từ những thời kỳ đầu của việc phân loại văn bản. Ý tưởng Khi cần phân loại một văn bản mới, thuật toán sẽ tính khoảng cách (khoảng cách Euclide, Cosine .) của tất cả các văn bản trong tập huấn luyện đến văn bản 8 này để tìm ra k văn bản gần nhất (gọi là k “láng giềng”), sau đó dùng các khoảng cách này đánh trọng số cho tất cả chủ đề. Trọng số của một chủ đề chính là tổng tất cả khoảng cách ở trên của các văn bản trong k láng giềng có cùng chủ đề, chủ đề nào không xuất hiện trong k láng giềng sẽ có trọng số bằng 0. Sau đó các chủ đề sẽ được sắp xếp theo mức độ trọng số giảm dần và các chủ đề có trọng số cao sẽ được chọn là chủ đề của văn bản cần phân loại.
Thuật toán [5] Xác định giá trị tham số K (số láng giềng gần nhất) 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ách Euclidean) 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 Lấy tất cả các lớp của K láng giềng gần nhất đã xác định 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. (Dựa vào k văn bản mẫu này đánh trọng số cho chủ đề. Chủ đề của các văn bản là chủ đề có trọng số lớn nhất) 1. Thuật toán cây quyết định (Decision tree) a.
Giới thiệu Cây quyết định là một cấu trúc cây với: Mỗi nút trong (internal node) ứng với một phép kiểm tra trên một thuộc tính. Mỗi nhánh biểu diễn một kết quả của phép kiểm tra. Các nút lá (leaf node) biểu diễn các lớp hay các phân bố lớp. Nút cao nhất trong cây là nút gốc (root node).
Ý tưởng Cây quyết định được mô tả bằng cách tính toán xác suất có điều kiện. Cây quyết định cũng có thể được mô tả như là một kỹ thuật tính toán và hỗ trợ toán học, kỹ thuật này hỗ trợ việc mô tả, phân loại và khái quát tập dữ liệu đưa vào. Dữ liệu đưa vào có dạng: (x, y) = (x1, x2, … , xk, y ) Biến phụ thuộc y là biến mà chúng ta cố gắng để biết, phân lớp hay tổng quát hóa, còn các biến x1, x2,… là các biến giúp ta thực hiện công việc đó. Để xây dựng được cây quyết định của tập dữ liệu nào đó chúng ta phải hiểu được khái niệm độ đo Entropy và Information Gain (Lợi ích thông tin).
Độ đo Entropy: đặc trưng cho độ hỗn tạp (lộn xộn) của một tập bất kỳ các mẫu thử. c Entropy ( S ) p log i i 1 Lợi ích thông tin: Gain(S, A) là lợi ích thông tin mà thuộc tính A mang lại cho sự phân lớp tập S. A có m giá trị v1, v2, … , vm Ký hiệu: Svi = {x ∈ S | x có giá trị thuộc tính A là vi} |S| là số phần tử của tập S c. Thuật toán [5] Cho tập ví dụ huấn luyện D.
Tìm cây quyết định phù hợp với D Bước 1: Khởi tạo cây một đỉnh gốc Toàn bộ tập ví dụ huấn luyện D đều đi vào đỉnh này. Bước 2: Repeat Chọn một đỉnh lá chưa gán nhãn để phát triển gọi là đỉnh hiện thời 10 Giả sử tập ví dụ huấn luyện đi vào đỉnh này là S If (S = rỗng) Then (gán nhãn chung nhất trong D) Else If (tất cả các ví dụ trong S đều được gán cùng một nhãn c) Then (đỉnh hiện thời được gán nhãn c) Else Đỉnh hiện thời được gán nhãn là thuộc tính A trong đó A = argmax Gain (S, Ai) Ai: ứng viên là nhãn của đỉnh hiện thời và mỗi giá trị v của A được gán nhãn cho nhánh đi từ A tới đỉnh mới. Tập ví dụ huấn luyện đi tới đỉnh mới đó là Sv trong đó Sv = {s ∈ S | s có giá trị của thuộc tính A là v} Until (tất cả các đỉnh của cây đều được gán nhãn) 1. Thuật toán SVM (Support vector machine) a.
Giới thiệu Support vector machine (SVM) – Máy vector hỗ trợ là một phương pháp phân lớp xuất phát từ lý thuyết học thống kê. Ý tưởng Ý tưởng của nó là ánh xạ (tuyến tính hoặc phi tuyến) dữ liệu vào không gian các vector đặc trưng (space of feature vectors) mà ở đó một siêu phẳng tối ưu được tìm ra để tách dữ liệu thuộc hai lớp khác nhau.
