- PHÂN LOẠI VĂN BẢN VỚI MÁY HỌC VECTOR HỖ TRỢ VÀ CÂY QUYẾT ĐỊNH. - 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),…. - 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 vì đặc điểm của bài toán phân loại văn bản là không gian đặc trưng thường rất lớn. - Bài viết này nghiên cứu máy học vector hỗ trợ (SVM), áp dụng nó vào bài toán phân loại văn bản và so sánh hiệu quả của nó với hiệu quả của giải thuật phân lớp cổ điển, rất phổ biến đó là cây quyết định. - Từ khóa: Cây quyết định, máy học vector hỗ trợ, phân loại văn bản, tách giá trị đơn. - Phân loại văn bản là một bài toán xử lí văn bản cổ đ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. - 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. - 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. - Ở đâ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ợ [1], cách tiếp cận sử dụng lý thuyết tập thô [2], cách tiếp cận thống kê hình vị [3], 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 [4], cách tiếp cận theo luật kết hợp [5]. - Bài viết này so sánh hiệu quả của hai cách tiếp cận phân loại văn bản: phân loại với giải thuật cây quyết định và phân loại với máy học vector hỗ trợ kết hợp với phân tích giá trị đơn (SVD).. - Theo cả hai cách tiếp cận này, trước hết, văn bản được coi như là một tập hợp các từ. - Phần tiếp theo sẽ trình bày cụ thể mô hình hóa văn bản trước khi áp dụng phân lớp theo giải thuật cây quyết định và phân lớp theo SVM.. - Trên thực tế, để có thể áp dụng một giải thuật tách từ, văn bản cần qua bước tiền xử lí cơ bản: chuẩn hóa dấu, chuẩn hóa “i” và “y”, chuẩn hóa font,… Tuy nhiên các bước này sẽ không được đề cập ở đây do giới hạn trang bài viết. - Có thể xem văn bản là tập hợp các từ. - chẳng hạn trong tiếng Việt cứ lấy hai tiếng liên tiếp đứng cạnh nhau trong văn bản làm “2-gram”. - Tuy nhiên, trong nghiên cứu của chúng tôi, MMSEG có thể áp dụng vào bài toán phân loại văn bản vì: MMSEG tách từ với độ chính xác khá cao trên 95%. - tỷ lệ sai sót trong tách từ khoảng 5% không ảnh hưởng lớn đến kết quả phân loại.. - Sau khi tách từ, văn bản được xem như là một tập hợp các “từ”. - Hình 1 cho ví dụ về một đoạn văn bản được tách theo giải thuật MMSEG.. - Rõ ràng rằng, các từ trong văn bản có mức độ quan trọng khác nhau đối với văn bản và cả trong phân loại văn bản. - không mang tính phân biệt trong khi phân loại. - Ngoài ra, còn có rất nhiều từ khác cũng không có giá trị phân loại ví dụ như từ xuất hiện hầu khắp các văn bản hay dùng không phổ biến trong văn bản, những từ gọi là stopword này cần được loại bỏ. - Sau khi loại bỏ các stopword, 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. - Tuy nhiên, có thể thấy rằng, số đặc trưng của một văn bản là lớn và không gian các đặc trưng (tất cả đặc trưng) của tất cả các văn bản đang xem xét là rất lớn, về nguyên tắc, nó bao gồm tất cả các từ trong một ngôn ngữ. - Chính vì vậy, phân loại dựa trên các đặc trưng này cần phải có cách xử lí, lựa chọn đặc trưng nhằm rút ngắn số chiều của không gian đặc trưng. - Kế đến, mỗi văn bản d i trong tập ngữ liệu đang xét sẽ được mô hình hóa như là một vector trọng số của các đặc trưng, d i (w i1 ,…,w im. - Trong bài viết này, trọng số của một từ được tính theo tần suất xuất hiện của từ trong văn bản (TF) và tần suất nghịch đảo của từ trong tập ngữ liệu (IDF).. - TF ij là số lần xuất hiện của từ thứ j trong văn bản thứ i.. - DF j là tổng số văn bản có chứa từ thứ j trong tập ngữ liệu.. - N là tổng số văn bản trong tập ngữ liệu.. - 3 PHÂN LOẠI VĂN BẢN THEO PHƯƠNG PHÁP CÂY QUYẾT ĐỊNH Phương pháp cây quyết định [8] có thể áp dụng vào bài toán phân loại văn bản.. - Dựa vào tập các văn bản huấn luyện (sau này gọi tắt là tập huấn luyện), xây dựng một cây quyết định. - Cây quyết định có dạng là cây nhị phân, mỗi nút trong tương ứng với việc phân hoạch tập văn bản dựa trên một thuộc tính nào đó (một từ). - Giả sử tập huấn luyện S chứa các văn bản thuộc k chủ đề, thì độ hỗn loạn thông tin của tập S là:. - p i chính là tần suất xuất hiện một văn bản thuộc chủ đề thứ i trong tập S.. - 3.1 Giải thuật xây dựng cây quyết định Đầu vào. - Tập M chứa tất cả các văn bản huấn luyện đã mô hình hóa thành các vector d i (w i1 ,…,w im. - Đầu ra : Cây quyết định dạng nhị phân cho việc phân loại theo tập chủ đề C.. - Giải thuật (tham khảo [9]):. - Bắt đầu: nút gốc chứa tất cả văn bản huấn luyện.. - M1 chứa các văn bản chứa a nhưng giá trị thuộc tính nhỏ hơn y, M2 chứa các văn bản chứa a và giá trị thuộc tính lớn hơn bằng y.. - 3.2 Đánh giá một giải thuật máy học. - Một số chỉ số thông dụng được dùng để đánh giá một giải thuật máy học, hay cụ thể là để đánh giá một bộ phân loại hai lớp tạm gọi là dương và âm:. - Số đúng dương (TP- True positive): số phần tử dương được phân loại dương - Số sai âm (FN - False negative): số phần tử dương được phân loại âm - Số đúng âm (TN- True negative): số phần tử âm được phân loại âm - Số sai dương (FP - False positive): số phần tử âm được phân loại dương - Độ chính xác (Precision. - Các chỉ số này sẽ được dùng để đánh giá hiệu quả cây quyết định và máy học SVM về sau, trong phần thực nghiệm.. - 3.3 Xén tỉa cây quyết định. - 3.4 Thực hiện phân loại 1 văn bản mới. - Các cây quyết định giờ đã được xây dựng xong và sẵn sàng để dùng cho phân loại văn bản. - Văn bản mới (cần được phân loại) được coi như là một tập hợp các đặc. - Ta sẽ tiến hành duyệt cây quyết định để gán nhãn phân loại chủ đề cho văn bản đó. - Nếu từ thuộc văn bản và giá trị của từ nhỏ hơn giá trị phân tách tại nút, hoặc từ không thuộc văn bản thì ta sẽ duyệt tiếp cây con trái của cây quyết định.. - Nếu từ thuộc văn bản và giá trị của từ lớn hơn giá trị phân tách tại nút thì ta sẽ duyệt cây con phải của cây quyết định.. - Quá trình này dừng khi gặp nút hiện tại là nút lá, gán nhãn cho văn bản là nhãn của nút lá đó.. - 4 PHÂN LOẠI VĂN BẢN VỚI MÁY HỌC VECTOR HỖ TRỢ. - Gần đây phương pháp máy học vector hỗ trợ đã được áp dụng vào bài toán phân loại văn bản và đã cho thấy kết quả khả quan [1,12]. - Tuy nhiên, như đã nói, bài toán phân loại văn bản có các đặc trưng là từ nên không gian đặc trưng là rất lớn, bao gồm mọi từ của ngôn ngữ hoặc trong tập ngữ liệu. - Số chiều của không gian đặc trưng lớn làm gia tăng nhiễu, đó là một trở ngại chính trong việc áp dụng SVM vào phân loại văn bản. - Trong nghiên cứu này chúng tôi dùng kỹ thuật tích giá trị đơn (SVD) để rút ngắn số chiều không gian đặc trưng.. - Phân tích giá trị đơn là phân tích toán học nền tảng trong kỹ thuật chỉ mục ngữ nghĩa tiềm ẩn (LSI-Latent Semantic Indexing) đã được dùng rộng rãi trong tìm kiếm và thu hồi thông tin dạng văn bản. - Về mặt thực hành việc cắt ma trận A về số chiều k còn loại bỏ nhiễu và tăng cường các mối liên kết ngữ nghĩa tiềm ẩn giữa các từ trong tập văn bản. - Khởi đầu, mỗi văn bản được mô hình hóa thành một vectơ cột trong không gian xác định bởi A mxn . - 4.2 Máy học véctơ hỗ trợ. - Máy học véctơ hỗ trợ (SVM) là một giải thuật máy học dựa trên lý thuyết học thống kê do Vapnik và Chervonenkis xây dựng [13]. - Bài toán cơ bản của SVM là bài toán phân loại hai lớp: Cho trước n điểm trong không gian d chiều (mỗi điểm thuộc vào một lớp kí hiệu là +1 hoặc –1, mục đích của giải thuật SVM là tìm một siêu phẳng (hyperplane) phân hoạch tối ưu cho phép chia các điểm này thành hai phần sao cho các điểm cùng một lớp nằm về một phía với siêu phẳng này. - Về sau, việc phân loại một mẫu mới chỉ là việc kiểm tra hàm dấu sign(wx +b).. - Trong thực nghiệm, có 7842 văn bản thuộc 10 chủ đề khác nhau đã được tập hợp dùng để xây dựng máy học và kiểm chứng hiệu quả. - Các văn bản được sưu tập từ các trang báo điện tử phổ biến bằng tiếng việt như vnexpress.net, vietnamnet.vn, dantri.com.vn. - Sau khi mô hình hóa, mỗi văn bản là một vector trọng số các từ, trong đó các trọng số là chỉ số TF*IDF như đã trình bày. - Bảng 2 cho số liệu thống kê số văn bản thuộc mỗi chủ đề. - Trong mỗi chủ đề, 500 văn bản được chọn một cách ngẫu nhiên để huấn luyện, tức là xây dựng cây quyết định hoặc huấn luyện máy học SVM. - Số văn bản còn lại để kiểm chứng độc lập.. - Kết quả kiểm chứng các cây quyết định với tập kiểm chứng độc lập được cho trong bảng 3. - Các chỉ số kiểm chứng nói trên được cho trong bảng 5 và so sánh với kết quả kiểm chứng với máy học SVM.. - Bảng 3: Kết quả kiểm chứng bộ phân lớp bằng cây quyết định Tên lớp Mã. - Để huấn luyện máy học SVM, tập ngữ liệu đang xét (đã được mô hình hóa như ma trận A 14275x7842 ) sẽ được phân tích giá trị đơn và rút ngắn số chiều về k=200. - Tất cả các vector tương ứng với 7842 văn bản đều được chiếu lên không gian A 200 bằng công thức (4). - Máy học SVM được huấn luyện bằng tập huấn luyện đã được dùng để xây dựng cây quyết định. - Tập kiểm chứng độc lập một lần nữa được dùng để kiểm chứng hiệu quả máy học SVM. - Bảng 4: Kết quả kiểm chứng bộ phân lớp bằng máy học SVM Tên lớp Mã. - Bảng 5: So sánh hiệu quả phân loại văn bản với cây quyết định và với máy học SVM. - Tên lớp Cây quyết định Máy học SVM. - Như vậy với máy học SVM kết hợp với phân tích giá trị đơn để rút ngắn số chiều của không gian đặc trưng sẽ cho kết quả phân loại văn bản tốt hơn là phương pháp cây quyết định. - Trong bài viết này chúng tôi đã trình bày phương pháp phân loại văn bản dựa trên máy học SVM. - trị đơn (SVD) để rút ngắn số chiều của không gian đặc trưng. - Các kiểm chứng thực nghiệm dựa trên tập hợp các mẫu độc lập với các mẫu dùng để xây dựng máy học cho thấy rằng hiệu quả của máy học SVM trong bài toán phân loại văn bản là ổn định, không phải là học vẹt. - Việc phân tích giá trị đơn để rút gọn số chiều của không gian đặc trưng là hoàn toàn thích hợp cho bài toán phân loại văn bản, một bài toán mà không gian đặc trưng lớn, có nhiều nhiễu.. - Các bài toán này về bản chất không khác so với bài toán phân loại văn bản vì qui trình xử lí, phương pháp xử lí là tương tự nhau: rút trích đặc trưng, lựa chọn đặc trưng, máy học và phân lớp. - Nguyễn Linh Giang, Nguyễn Mạnh Hiển, Phân loại văn bản tiếng Việt với bộ phân loại vectơ hỗ trợ SVM. - Nguyễn Ngọc Bình, “Dùng lý thuyết tập thô và các kỹ thuật khác để phân loại, phân cụm văn bản tiếng Việt”, Kỷ yếu hội thảo ICT.rda’04. - sát trong học có giám sát với bài toán phân lớp văn bản tiếng Việt và đề xuất cải tiến công thức tính độ liên quan giữa hai văn bản trong mô hình vectơ”, Kỷ yếu Hội thảo ICT.rda’04, trang 251-261, Hà Nội 2005.. - Đỗ Phúc, Nghiên cứu ứng dụng tập phổ biến và luật kết hợp vào bài toán phân loại văn bản tiếng Việt có xem xét ngữ nghĩa, Tạp chí phát triển KH&CN, tập 9, số 2, pp.