- PHÂN LOẠI VĂN BẢN: MÔ HÌNH TÚI TỪ VÀ TẬP HỢP MÔ HÌNH MÁY HỌC TỰ ĐỘNG Đỗ Thanh Nghị 1 và Phạm Nguyên Khang 1. - Phân loại văn bản, Mô hình túi từ, Phương pháp tập hợp mô hình máy học, Phân loại có giám sát. - Trong bài này, chúng tôi giới thiệu tiếp cận phân lớp văn bản với độ chính xác cao. - Nghiên cứu của chúng tôi dựa trên sự kết hợp giữa phương pháp biểu diễn văn bản bằng mô hình túi từ và các giải thuật xây dựng tập hợp các mô hình học tự động như Bayes thơ ngây ngẫu nhiên (random multinomial naive Bayes (rMNB. - Bước tiền xử lý, bao gồm phân tích từ vựng, xây dựng mô hình túi từ để biểu diễn văn bản dưới dạng véc tơ tần số xuất hiện của từ trong văn bản, số chiều rất lớn. - Chúng tôi đề xuất các giải thuật boosting mới dựa trên mô hình cơ bản như cây ngẫu nhiên xiên phân đơn giản (rODS), Bayes thơ ngây ngẫu nhiên (rMNB), cho phép phân lớp hiệu quả tập dữ liệu này. - Kết quả thực nghiệm với tập dữ liệu thực cho thấy rằng phương pháp của chúng tôi đề xuất phân lớp rất hiệu quả khi so sánh với các giải thuật hiện có, đạt được chính xác 94.8%.. - Trong kỷ nguyên công nghệ thông tin, chúng ta nhận ngày càng nhiều nguồn thông tin dưới dạng văn bản. - 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. - Phân lớp tự động văn bản có thể được mô tả ngắn gọn như sau. - Phân lớp văn bản thường được dựa trên mô hình ngữ nghĩa hoặc máy học. - Hầu hết các phương pháp phân loại văn bản dựa trên mô hình thống kê từ và các giải thuật học tự động Theo (Sebastiani, 99). - Theo mô hình túi từ, dữ liệu văn bản không có cấu trúc (độ dài khác nhau) được biểu diễn dưới dạng véc tơ tần số xuất hiện của từ trong văn bản. - Tập các dữ liệu văn bản được chuyển về dạng một bảng có số cột (chiều, từ vựng) rất lớn. - Bước tiếp theo là huấn luyện mô hình học tự động từ bảng dữ liệu này. - Các mô hình máy học thường sử dụng như giải thuật k láng giềng (kNN (Fix &. - giải thuật tập hợp mô hình bao gồm Boosting (Freund &. - Do dữ liệu có số chiều lớn, chỉ có máy học SVM và phương pháp tập hợp mô hình xử lý hiệu quả.. - Trong bài báo này, chúng tôi đề xuất giải thuật học boosting của Bayes thơ ngây ngẫu nhiên (rMNB) và cây xiên phân ngẫu nhiên đơn giản (rODS) cho phân lớp hiệu quả dữ liệu có số chiều lớn thu được từ biểu diễn văn bản với mô hình túi từ. - Giải thuật boosting để xây dựng tuần tự k mô hình cơ sở rMNB hay rODS, mỗi mô hình tập trung hầu hết các lỗi được tạo ra bởi các mô hình trước đó. - Vì vậy, giải thuật boosting của chúng tôi có thể xử lý hiệu quả tập dữ liệu với số chiều lớn. - Chúng tôi làm thực nghiệm trên tập dữ liệu văn bản thu thập bởi (Trần &. - Phạm, 12), gồm 10 chủ đề văn bản của trang báo điện tử vnexpress.net.. - Kết quả cho thấy rằng phương pháp của chúng tôi đề xuất phân lớp rất hiệu quả khi so sánh với các giải thuật hiện có, đạt được chính xác 94.8%.. - Phần tiếp theo của bài viết được trình bày như sau: phần 2 trình bày ngắn gọn về biểu diễn văn bản bằng mô hình túi từ. - phần 3 trình bày giải thuật boosting của rMNB, rODS. - 2 BIỂU DIỄN VĂN BẢN BẰNG MÔ HÌNH TÚI TỪ. - Theo tiếp cận phân lớp tự động văn bản bằng mô hình máy học (Sebastiani, 99), việc phân loại văn bản bao gồm hai bước chính: biểu diễn dữ liệu văn bản, huấn luyện mô hình phân lớp. - Do dữ liệu văn bản ở đầu vào ở dạng không cấu trúc, trong khi các giải thuật máy học ở giai đoạn tiếp theo sau thường chỉ có thể xử lý được dữ liệu dạng cấu trúc bảng (mỗi dòng là một phần tử dữ liệu, cột là chiều hay thuộc tính). - Để giải quyết vấn đề này, mô hình túi từ cho phép chúng ta biểu diễn tập dữ liệu văn bản về cấu trúc bảng.. - Bước tiền xử lý này bao gồm việc phân tích từ vựng và tách các từ trong nội dung của tập văn bản, sau đó chọn tập hợp các từ có ý nghĩa quan trọng dùng để phân loại, biểu diễn dữ liệu văn bản về dạng bảng để từ đó các giải thuật máy học có thể học để phân loại. - Một văn bản được biểu diễn dạng véc tơ (có n thành phần, chiều) mà giá trị thành phần thứ j là tần số xuất hiện từ thứ j trong văn bản. - Bảng 1: Ví dụ về tập dữ liệu văn bản. - Pháp luật Bảng 2: Biểu diễn tập dữ liệu văn bản bằng mô. - Trong khi các mô hình máy học như k láng giềng (kNN), Bayes thơ ngây (NB) hay cây quyết định xử lý kém hiệu quả. - Tuy nhiên, nếu không thực hiện bước rút gọn chiều, chúng ta cần xây dựng giải thuật máy có thể xử lý được bảng có số chiều lớn. - Thường thì các mô hình máy học SVM và phương pháp tập hợp mô hình xử lý hiệu quả trên dữ liệu có số chiều lớn.. - Chúng tôi đề xuất giải thuật học boosting của Bayes thơ ngây ngẫu nhiên (rMNB) và cây xiên phân ngẫu nhiên đơn giản (rODS) cho phân lớp hiệu quả dữ liệu có số chiều lớn thu được từ biểu diễn văn bản với mô hình túi từ.. - 3 GIẢI THUẬT BOOSTING CỦA RMNB VÀ RODS. - Tập dữ liệu văn bản được biểu diễn theo mô hình túi từ. - Thay vì giải thuật MNB và ODS sử dụng toàn bộ tập các thuộc tính (chiều) để huấn luyện mô hình phân lớp thì rMNB và rODS chỉ sử dụng tập con các thuộc tính được lấy ngẫu nhiên từ tập thuộc tính ban đầu.. - 3.1 Giải thuật Bayes thơ ngây ngẫu nhiên (rMNB). - Phương pháp ước lượng xác suất khi phân lớp một văn bản của mô hình MNB (Lewis &. - Giả sử C là tập hợp các lớp của văn bản. - Tập các từ vựng của văn bản có kích thước là N. - Khi có một văn bản mới đến là ti thì mô hình MNB gán lớp cho ti sao cho ước lượng xác suất để ti thuộc vào một lớp ci là lớn nhất hay là tìm giá trị lớn nhất của Pr(c|ti). - 3.2 Giải thuật cây xiên phân ngẫu nhiên (rODS). - Mô hình cây quyết định có cấu trúc dạng cây mà ở đó nút lá được gán nhãn tương ứng với lớp của dữ liệu và nút trong được tích hợp với điều kiện kiểm tra để rẽ nhánh. - Có hai giải thuật học tự động là CART (Breiman et al., 84) và C4.5 (Quinlan, 93).. - Mô hình cây quyết định đơn giản (decision stump) được đề xuất trong (Freund &. - định đơn giản của giải thuật học chỉ chọn một thuộc tính tốt nhất cho việc phân hoạch dữ liệu tại nút gốc tạo thành 2 nút lá (mỗi nút tương ứng một lớp).. - Do đó, độ chính xác của mô hình cây quyết định đơn giản bị giảm khi làm việc với các tập dữ liệu có số chiều lớn, mỗi chiều cung cấp ít thông tin cho phân lớp và các. - chiều còn phụ thuộc lẫn nhau, chẳng hạn như dữ liệu văn bản thu được mà chúng ta xử lý ở đây.. - Hình 1: Phân hoạch đơn thuộc tính (trái), phân hoạch đa thuộc tính (phải) Để khắc phục nhược điểm trên, nhiều giải thuật. - Nghiên cứu tiên phong của Murthy và các cộng sự trong (Murthy et al., 93) đã đưa ra giải thuật OC1, một hệ thống dùng để xây dựng các cây quyết định xiên trong đó dùng thuật toán leo đồi để tìm một phân hoạch xiên tốt dưới dạng một siêu phẳng. - Giải thuật rODS xây dựng cây như mô tả trong Hình 2 cho vấn đề phân lớp nhị phân (2 lớp dương và âm).. - So với mô hình MNB, ODS với tập đầy đủ các thuộc tính thì giải thuật rMNB, rODS đơn giản, nhanh hơn, hiệu quả phân lớp tốt hơn do khả năng chịu đựng nhiễu cao hơn. - Mặc dù mô hình đơn của rMNB và rODS thì không mạnh do quá đơn giản, nhưng khi áp dụng kỹ thuật boosting (Freund &. - Schapire, 95), (Breiman, 98) để xây dựng tập hợp các mô hình rMNB, rODS thì hiệu quả của giải thuật được cải thiện rất nhiều.. - 3.3 Giải thuật boosting của rMNB, rODS Breiman đã nghiên cứu phân tích hiệu quả giải thuật học dựa trên cơ sở của hai thành phần lỗi là bias và variance mà ở đó, thành phần lỗi bias là lỗi của mô hình học và variance là lỗi do tính biến thiên của mô hình so với tính ngẫu nhiên của các mẫu dữ liệu học (Breiman, 01). - Trong nghiên cứu kết hợp nhiều mô hình phân loại yếu thành tập hợp các mô hình phân loại để cho tính chính xác cao hơn so với chỉ một mô hình đơn.. - Giải thuật ArcX4 cho kết quả tương tự như AdaBoost nhưng đơn giản và dễ cài đặt.. - Ý tưởng chính của giải thuật ArcX4 (như mô tả. - trong giải thuật 1) lặp lại quá trình học của một bộ phân lớp yếu nhiều lần. - Ở bước thứ i, ta lấy tập mẫu S i trên tập dữ liệu và xây dựng mô hình h i từ tập mẫu S i . - Lặp lại quá trình này sau T bước, ta sẽ được T mô hình cơ sở, kết hợp các mô hình cơ sở này lại ta sẽ có được một bộ phân lớp mạnh.. - Giải thuật 1: ArcX4 của rMNB, rODS. - Để đánh giá hiệu quả của phương pháp đề xuất (mô hình túi từ và giải thuật boosting của rMNB, rODS) cho phân loại văn bản, chúng tôi đã tiến hành cài đặt giải thuật boosting của rMNB, rODS bằng C/C. - Chúng tôi muốn so sánh hiệu quả của giải thuật boosting của rMNB, rODS với các giải thuật học khác, bao gồm k láng giềng (kNN), Bayes thơ ngây (NB), máy học SVM, cây quyết định C4.5 và rừng ngẫu nhiên xiên (RF-ODT).. - Chúng tôi tiến hành cài đặt giải 2 giải thuật NB và kNN bằng ngôn ngữ lập trình C/C. - Giải thuật SVM chuẩn đã có trong các thư viện phần mềm miễn phí LibSVM (Chang &. - Đây là tập dữ liệu văn bản thu thập từ trang báo điện tử vnexpress.net, gồm có 10 chủ đề như công nghệ thông tin (cntt), giải trí, giáo dục, kinh doanh, ẩm thực, pháp luật, y tế, thế giới, thể thao, tình yêu. - Mỗi chủ đề có 200 văn bản khác nhau tạo thành tập dữ liệu văn bản có 2000 bản tin.. - Tập dữ liệu học dùng để huấn luyện mô hình phân lớp, bao gồm cả việc điều chỉnh các tham số cho các giải thuật học. - Với các mô hình đơn, giải thuật Bayes thơ ngây (NB) và cây quyết định C4.5 không cần điều chỉnh tham số. - Với các phương pháp tập hợp mô hình như Boosting và ngẫu nhiên xiên (RF-ODT), chúng tôi đều xây dựng 50 mô hình cơ sở (rMNB, rODS, ODT sử dụng 1000 chiều ngẫu nhiên từ 12182 chiều).. - Hình 3: Kết quả phân lớp trên tập dữ liệu. - văn bản 10 chủ đề. - Kết quả thu được từ các giải thuật được trình bày trong Hình 3. - Quan sát kết quả thu được, không có gì ngạc nhiên khi các mô hình học kNN, NB, C4.5 cho kết quả thấp khi so sánh với các các giải thuật khác. - Điều này hoàn toàn phù hợp do dữ liệu có số chiều lớn, các mô hình đơn giản không còn phân lớp hiệu quả. - Trong khi đó, giải thuật máy học SVM cho kết quả tốt hơn nhóm giải thuật đơn giản trước. - Nhóm tập hợp mô hình, gồm 2 giải thuật boosting của rMNB, rODS và rừng ngẫu nhiên xiên RF-ODT cho kết quả phân lớp chính xác nhất.. - Nếu quan sát thời gian cần thiết để huấn luyện mô hình học, mặc dù giải thuật kNN không có huấn luyện nhưng lại mất thời gian khi phân lớp lâu nhất. - Kế đến là RF-ODT mặc dù nhanh hơn kNN đến 4 lần nhưng vẫn chậm hơn các giải thuật khác đến 4 hoặc 10 lần. - Giải thuật SVM có thời gian huấn luyện nhanh, cho kết quả cũng rất khả quan. - Hai giải thuật chúng tôi đề xuất là boosting của rMNB, rODS có thời gian huấn luyện nhanh và cho kết quả chính xác nhất.. - Hình 4: Thời gian huấn luyện mô hình Kết quả thu được từ thực nghiệm này cho phép chúng tôi tin rằng giải thuật đề xuất rMNB, rODS phân loại tốt dữ liệu văn bản, được biểu diễn theo mô hình túi từ (rất đơn giản, nhanh, không cần xử lý phức tạp nào).. - 5 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN Chúng tôi vừa trình bày một tiếp cận phân lớp văn bản với độ chính xác cao. - Nghiên cứu của chúng tôi dựa trên sự kết hợp giữa phương pháp biểu diễn văn bản bằng mô hình túi từ và các giải thuật boosting, xây dựng tập hợp các mô hình học tự động như rMNB, rODS. - Mô hình túi từ được xây dựng đơn giản, nhanh, để biểu diễn văn bản dưới dạng véc tơ tần số xuất hiện của từ trong văn bản, số chiều rất lớn. - Thay vì cần các xử lý đặc thù để rút gọn chiều, chúng tôi đề xuất các giải thuật. - boosting mới dựa trên mô hình cơ bản ngẫu nhiên rMNB, rODS cho phép phân lớp hiệu quả tập dữ liệu này. - Trong tương lai, chúng tôi dự định mở rộng giải thuật để xử lý vấn đề tương tự như phân lớp ảnh, video, sử dụng mô hình biểu diễn túi từ. - Bên cạnh đó, chúng tôi cũng muốn tăng tốc quá trình xây dựng mô hình học của rMNB, rODS bằng việc xây dựng giải thuật song song.. - Thời gian huấn luyện mô hình (giây). - và Poulet F.: Phân loại văn bản với BPSVM. - Trần, C.Đ và Phạm N.K.: Phân loại văn bản với máy học véc tơ hỗ trợ và cây quyết định