Phân lớp tài liệu Web độc lập ngôn ngữ

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Nguyễn Thị Thuỳ Linh PHÂN LỚP TÀI LIỆU WEB ĐỘC LẬP NGÔN NGỮ KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY Ngành: Công nghệ thông tin Cán bộ hướng dẫn: NCS. Phan Xuân Hiếu Cán bộ đồng hướng dẫn: TS. Hà Quang Thuỵ HÀ NỘI – 2006 LỜI CẢM ƠN Em xin gửi lời cảm ơn chân thành và biết ơn sâu sắc tới Tiến sĩ Hà Quang Thuỵ (Trường Đại học Công Nghệ) và Nghiên cứu sinh Phan Xuân Hiếu (Japan Advanced Institute of Science and Technology) đã chỉ bảo và hướng dẫn tận tình cho tôi trong suốt quá trình nghiên cứu Khoa học và quá trình thực hiện khoá luận này. Em xin gửi lời cảm ơn và biết ơn sâu sắc tới các thày, cô đã dạy dỗ em trong suốt quá trình học tập tại trường Đại học Công Nghệ. Những kiến thức các thày, cô dạy tôi là hành trang để tôi vững bước vào đời. Em cũng xin chân thành cảm ơn các thày, cô, anh, chị trong Bộ môn Các hệ thống thông tin đã tạo điều kiện, giúp đỡ và động viên tinh thần cho em trong quá trình làm khoá luận. Tôi xin gửi lời cảm ơn tới các bạn sinh viên trong nhóm seminar “Khai phá dữ liệu và khám phá tri thức” đã ủng hộ và khuyến khích tôi trong quá trình nghiên cứu và làm khoá luận này. Và cuối cùng, con xin gửi lời cảm ơn và biết ơn vô hạn tới bố, mẹ, cảm ơn em trai tôi, những người thân yêu của tôi, đã nuôi nấng, dạy dỗ và luôn động viên, làm chỗ dựa tinh thần cho tôi trong cuộc sống cũng như trong học tập và làm việc. Xin chân thành cảm ơn! Hà Nội, ngày 25 tháng 05 năm 2006 Sinh viên Nguyễn Thị Thuỳ Linh i TÓM TẮT NỘI DUNG Phân lớp văn bản là một trong những bài toán cơ bản và quan trọng nhất của lĩnh vực xử lý ngôn ngữ tự nhiên. Nó có ứng dụng rất nhiều trong các bài toán thực tế ví dụ như: ứng dụng lọc nội dung văn bản (lọc thư rác, lọc trang web có nội dung phản động, trang web có nội dung không lành mạnh,…), bài toán phân lớp văn bản sau tìm kiếm,… Hiện nay có rất nhiều bộ phân lớp đạt được độ chính xác cao (đều xấp xỉ 90%), tuy nhiên các bộ phân lớp này hầu hết chỉ áp dụng cho một ngôn ngữ cụ thể. Thực tế cho thấy, đối với bài toán lọc nội dung trang Web thì một vấn đề đặt ra là phải xử lý trên nhiều ngôn ngữ khác nhau. Một trong hướng nghiên cứu phân lớp văn bản được quan tâm gần đây là phân lớp đa ngôn ngữ [7]. Khoá luận này nghiên cứu và đề xuất một phương pháp phân lớp nội dung Web độc lập ngôn ngữ. Phương pháp này cho phép tích hợp thêm các ngôn ngữ mới vào bộ phân lớp và giải quyết vấn đề bùng nổ đặc trưng thông qua hướng tiếp cận entropy cực đại và sử dụng chiến lược tối ưu hoá hàm nhiều biến rất hiệu quả. Các kết quả thực nghiệm cho thấy hướng tiếp cận của khoá luận rất khả quan, cụ thể, khi huấn luyện riêng biệt trên từng ngôn ngữ đều nhận được kết quả rất cao (Anh trên 98%, Việt trên 91%), còn khi có sự kết hợp của hai ngôn ngữ kết quả đạt được cũng rất khả quan (Anh-Việt xấp xỉ 95%). Đặc biệt khi cho mô hình kiểm tra trên một tập dữ liệu hoàn toàn mới kết quả cũng rất khả quan (độ chính xác Anh-Việt xấp xỉ 84%). Bên cạnh đó, khoá luận cũng đã phân tích các vấn đề cơ bản của bài toán phân lớp văn bản độc lập ngôn ngữ đó là sự nhập nhằng ngôn ngữ và sự bùng nổ đặc trưng, sau đó đã đưa ra các phương pháp khắc phục khá hiệu quả. Một đề xuất mới mà khoá luận đưa ra là mô hình dựa trên cây phân lớp thông minh. Đề xuất này có nhiều triển vọng cho các ứng dụng nhỏ cần phân loại văn bản và nhận diện được ngôn ngữ. ii MỤC LỤC LỜI CẢM ƠN.................................................................................................................. i TÓM TẮT NỘI DUNG................................................................................................... i MỤC LỤC ...................................................................................................................... ii BẢNG KÍ HIỆU VIẾT TẮT ......................................................................................... iv DANH MỤC BẢNG SỐ LIỆU.......................................................................................v DANH MỤC HÌNH ẢNH............................................................................................. vi MỞ ĐẦU .........................................................................................................................1 CHƯƠNG 1. KHÁI QUÁT VỀ PHÂN LỚP VĂN BẢN ĐỘC LẬP NGÔN NGỮ ......3 1.1. Bài toán phân lớp văn bản ...................................................................................3 1.1.1. Tổng quan......................................................................................................3 1.2. Phân lớp văn bản độc lập ngôn ngữ .....................................................................4 1.2.1. Đặt vấn đề......................................................................................................4 1.2.2. Phân lớp văn bản độc lập ngôn ngữ ..............................................................5 1.2.3. Ý nghĩa và ứng dụng .....................................................................................5 CHƯƠNG 2. CÁC MÔ HÌNH VÀ THUẬT TOÁN PHÂN LỚP VĂN BẢN...............7 2.1. Giới thiệu.............................................................................................................7 2.2. Mô hình Maximum Entropy................................................................................7 2.2.1. Giới thiệu.......................................................................................................7 2.2.2. Xây dựng mô hình .........................................................................................9 2.3. Tổng kết chương.................................................................................................16 CHƯƠNG 3. PHÂN LỚP TÀI LIỆU WEB ĐỘC LẬP NGÔN NGỮ VỚI MÔ HÌNH ENTROPY CỰC ĐẠI ...................................................................................................17 3.1 Giới thiệu............................................................................................................17 3.2. Bài toán phân lớp văn bản độc lập ngôn ngữ ....................................................17 3.2.1. Vấn đề nhập nhằng ngôn ngữ ......................................................................17 3.2.2. Vấn đề bùng nổ đặc trưng ...........................................................................18 3.3. Quy trình xây dựng bộ phân lớp........................................................................19 3.3.1. Tiền xử lý dữ liệu ........................................................................................19 3.3.2. Xây dựng đặc trưng .....................................................................................20 3.3.3. Lựa chọn đặc trưng......................................................................................21 3.3.4. Huấn luyện mô hình ....................................................................................23 3.3.5. Phân lớp văn bản mới ..................................................................................23 3.4. Đánh giá độ chính xác của bộ phân lớp ............................................................24 iii 3.4.1. Các độ đo.....................................................................................................24 3.4.2. Áp dụng phương pháp ước lượng chéo trên k tập con ................................25 3.5. Xây dựng bộ phân lớp trên cây phân lớp thông minh .......................................25 3.5.1. Bản chất bài toán .........................................................................................26 3.5.2. Phân lớp cho văn bản mới ...........................................................................26 3.5.3. Thảo luận .....................................................................................................27 3.6. Tổng kết chương................................................................................................27 CHƯƠNG 4. KẾT QUẢ THỬ NGHIỆM VÀ ĐÁNH GIÁ .........................................28 4.1. Môi trường thử nghiệm ......................................................................................28 4.1.1. Môi trường phần cứng.................................................................................28 4.1.2. Công cụ phần mềm......................................................................................28 4.2. Dữ liệu kiểm thử.................................................................................................29 4.2.1. Tiền xử lý dữ liệu ........................................................................................29 4.2.2. Cây phân lớp................................................................................................30 4.3. Kết quả thử nghiệm ............................................................................................31 4.3.1. Quá trình huấn luyện ...................................................................................31 4.3.2. Lần lặp cho độ chính xác cao nhất ..............................................................34 4.3.3. Kết quả kiểm tra trên dữ liệu mới ...............................................................35 4.4. Tổng kết chương.................................................................................................36 KẾT LUẬN ...................................................................................................................37 PHỤ LỤC. DANH SÁCH STOP-WORD ....................................................................38 TÀI LIỆU THAM KHẢO .............................................................................................41 iv BẢNG KÍ HIỆU VIẾT TẮT Kí hiệu Diễn giải GIS Generalized Interative Scaling HTML Hyper Text Markup Language IDF Inverse Document Frequency IIS Improved Iterative Scaling kNN K Nearest Neighbours L-BFGS Limited-memory Broyden-Fletcher-Goldfarb-Shannon MaxEnt Maximum Entropy NCR Numeric Character References TF Term Frequency UTF Unicode Transformation Formats v DANH MỤC BẢNG SỐ LIỆU Bảng 1. Cây phân lớp thông minh tổng quát.................................................................26 Bảng 2. Bảng ví dụ cho cây phân lớp thông minh ........................................................26 Bảng 3. Cấu hình hệ thống chạy thử nghiệm ................................................................28 Bảng 4. Danh sách phần mềm sử dụng để thử nghiệm .................................................28 Bảng 5. Danh sách công cụ sử dụng để thử nghiệm .....................................................29 Bảng 6. Cây phân lớp thông tin.....................................................................................31 Bảng 7. Tập dữ liệu huấn luyện của cả 3 mô hình ........................................................31 Bảng 8. Độ chính xác 10 lần huấn luyện của tiếng Anh ...............................................32 Bảng 9. Độ chính xác 10 lần huấn luyện của tiếng Việt ...............................................32 Bảng 10. Độ chính xác 10 lần huấn luyện kết hợp Anh-Việt........................................32 vi DANH MỤC HÌNH ẢNH Hình 1. Tập ràng buộc C ...............................................................................................12 Hình 2. Mô tả các bước xây dựng bộ phân lớp .............................................................19 Hình 3. Trang tin tức tiếng Việt VnExpress.net............................................................29 Hình 4. Trang tin tức tiếng Anh BBC News .................................................................30 Hình 5. Độ chính xác của 3 bộ phân lớp trong 10 lần huấn luyện ................................33 Hình 6. Sự phụ thuộc độ chính xác theo bước lặp của cả 3 mô hình ............................34 Hình 7. Kết quả kiểm tra bộ dữ liệu độc lập Anh-Việt .................................................35 1 MỞ ĐẦU Hiện nay, nhờ khả năng cho phép mã hoá được phần lớn các ngôn ngữ thông dụng trên toàn thế giới của bảng mã Unicode, khoảng cách giữa các quốc gia, dân tộc do hạn chế về ngôn ngữ gây ra đang dần được xoá đi. Theo thống kê [20] hiện nay đã có 141 ngôn ngữ được sử dụng trên Internet và xu hướng tất yếu là sẽ ngày càng xuất hiện thêm nhiều ngôn ngữ trên Internet. Bộ phân lớp văn bản đã có hiện nay mới chỉ dừng ở mức phân lớp cho các văn bản cùng trên một ngôn ngữ. Nếu với 141 ngôn ngữ chúng ta xây dựng 141 bộ phân lớp thì quả thật tốn kém. Hơn thế nữa các trang web thương mại, web có nội dung không lành mạnh hiện nay thể hiện và ẩn náu dưới nhiều hình thức đa dạng (nhiều ngôn ngữ cùng xuất hiện trong một trang web) với mục đích đi qua bộ lọc trong máy tìm kiếm, chúng gây rất nhiều phiền toái cho người dùng. Vì vậy, bài toán phân lớp văn bản độc lập ngôn ngữ được đặt ra nhằm mục đích xây dựng một bộ phân lớp duy nhất cho nhiều ngôn ngữ. Ý thức được vấn đề đó, khóa luận này tập trung xây dựng một bộ phân lớp tài liệu web độc lập ngôn ngữ dựa trên việc áp dụng nguyên lý entropy cực đại. Đây là phương pháp có khả năng tích hợp mạnh hàng nghìn hàng triệu đặc trưng quan trọng. Qua kết quả thực nghiệm, với tập dữ liệu lên tới 12.000 trang Web bao gồm hai ngôn ngữ Anh và Việt, kết quả cho thấy rất khả quan. Mục tiêu mà khoá luận hướng tới: 9 Xây dựng bộ phân lớp duy nhất cho nhiều ngôn ngữ dựa trên mô hình entropy cực đại. 9 Không cần sử dụng một bộ phân nhận dạng ngôn ngữ nào khác. 9 Thử nghiệm và đánh giá, và vạch ra hướng phát triển tiếp theo. Cấu trúc của luận văn được tổ chức như sau: 9 Chương 1: Giới thiệu tóm tắt bài toán phân lớp văn bản, đặt vấn đề và phát biểu bài toán phân lớp văn bản độc lập ngôn ngữ. 9 Chương 2: Trình bày cụ thể hơn về bài toán phân lớp, đề cập đến các vấn đề cơ bản của nguyên lý entropy cực đại theo hướng áp dụng vào bài toán phân lớp văn bản. 9 Chương 3: Phát biểu bài toán phân lớp văn bản độc lập ngôn ngữ, phân tích các vấn đề cần giải quyết đối với bài toán và các bước xây dựng bộ 2 phân lớp trên cơ sở áp dụng mô hình entropy cực đại. Đưa ra một đề xuất mới có thể áp dụng và các ứng dụng vừa và nhỏ. 9 Chương 4: Trình bày những kết quả đánh giá thử nghiệm của khoá luận áp dụng cho bài toán cây phân lớp tin tức với hai ngôn ngữ Anh và Việt. Cuối cùng là kết luận lại những điểm chính, những đóng góp chính của luận văn, đồng thời chỉ ra những điểm cần khắc phục và vạch ra hướng cải tiến nhằm hướng tới xây dựng một hệ ứng dụng thực trên môi trường Internet. 3 Chương 1 KHÁI QUÁT VỀ PHÂN LỚP VĂN BẢN ĐỘC LẬP NGÔN NGỮ Bài toán phân lớp độc lập ngôn ngữ là một bài toán con, phát triển trên nền của bài toán phân lớp văn bản. Trước khi trình bày về bài toán chính, chương này trình bày một cách sơ lược lịch sử cũng như ứng dụng của bài toán phân lớp văn bản. 1.1. Bài toán phân lớp văn bản 1.1.1. Tổng quan Phân lớp văn bản được coi là quá trình phân loại một văn bản bất kì vào một hay nhiều lớp cho trước. Theo phương pháp học máy (machine learning), quá trình này gồm hai bước. Ở bước thứ nhất, một mô hình phân lớp (classfication model) được xây dựng dựa trên tri thức kinh nghiệm. Ở đây, tri thức kinh nghiệm chính là một tập dữ liệu huấn luyện (training dataset) được cung cấp bởi con người bao gồm một tập văn bản và phân lớp tương ứng của chúng. Bước này còn gọi là bước xây dựng huấn luyện (training process) hay ước lượng mô hình phân lớp. Ở bước thứ hai, mô hình phân lớp xây dựng ở bước đầu sẽ được sử dụng để phân lớp cho những văn bản (chưa được phân loại) trong tương lai. Bước đầu tiên được xem như là việc học có giám sát mà chúng ta có thể sử dụng rất nhiều các kĩ thuật học máy đã có như: Naïve Bayes, k láng giếng gần nhất (kNN), cây quyết định (Decision Tree),… Mục tiêu của bài toán phân lớp là nhằm xây dựng mô hình có khả năng gán nhãn cho một văn bản bất kì với độ chính xác cao nhất có thể. Nhu cầu có một bộ phân lớp hiệu quả đã xuất hiện ngay từ thủa ban đầu của thời kì bùng nổ thông tin trên Internet. Vì thế bài toán phân lớp văn bản không phải là một khái niệm mới mẻ. Tuy nhiên, hiện nay càng ngày hệ thống máy tính có khả năng xử lý càng mạnh, lượng thông tin trên Internet biến đổi không ngừng cả về chất lượng và số lượng. Nên bài toán phân lớp văn bản vẫn luôn là một vấn đề thời sự [7]. Đồng hành với lịch sử đó cho đến nay đã có rất nhiều các công cụ, bộ phân lớp ra đời, có thể là bộ phân lớp với từng ứng dụng cụ thể, hay bộ phân lớp cho một bài toán nhưng áp dụng những kĩ thuật học máy khác nhau. Ứng dụng lớn nhất của bài toán phân lớp văn bản là áp dụng vào bài toán phân loại hay lọc nội dung. Trong bài toán lọc nội dung: một văn bản được phân loại vào 4 nhóm: có ích hoặc không có ích. Sau đó lấy tất cả những văn bản thuộc nhóm có ích, nhóm còn lại bị loại bỏ. Các ứng dụng cụ thể như: lọc thư rác, lọc trang web phản động,… Một ứng dụng khác của bài toán phân lớp là xây dựng bộ phân lớp sau tìm kiếm, ứng dụng này rất hữu ích vì nó định vị nội dung thông tin cần tìm kiếm nhanh và dễ dàng hơn. Tóm lại, với tất cả ý nghĩa thực tế trên, một lần nữa có thể khẳng định rằng trong thời đại Internet được coi là một phần không thể thiếu trong cuộc sống, phân lớp văn bản luôn là vấn đề đáng được quan tâm để có thể phát triển và xây dựng được những công cụ ngày càng hữu dụng hơn. 1.2. Phân lớp văn bản độc lập ngôn ngữ 1.2.1. Đặt vấn đề Nếu thường xuyên theo dõi các trang tin của các hãng tin lớn, chúng ta dễ dàng nhận thấy chúng được thể hiện trên nhiều ngôn ngữ. Trên BBC hiện nay có tới 33 ngôn ngữ, CNN có 5 ngôn ngữ,… Hoặc khi chúng ta nhập câu truy vấn trong một hệ thống tìm kiếm trực tuyến (Google, Yahoo) để tìm kiếm thông tin mà ta quan tâm, kết quả trả về là một danh sách các địa chỉ trang web chứa từ khoá cần tìm và chúng hiển thị dưới nhiều ngôn ngữ khác nhau. Như vậy có thể thấy rằng khá nhiều ngôn ngữ đã được đưa lên Internet. Hiện nay theo thống kê [20] đã có tới 141 ngôn ngữ được mã hoá và được sử dụng trên Internet, và theo xu thế này thì sẽ còn có nhiều hơn nữa các ngôn ngữ được mã hoá và đưa vào sử dụng. Trong giai đoạn nền kinh tế hội nhập này, không chỉ các hãng tin lớn mà cả các tập đoàn xuyên quốc gia cũng xây dựng trang web của mình trên nhiều ngôn ngữ khác nhau. Bên cạnh đó còn có các quốc gia muốn giới thiệu về nền văn hoá, lịch sử nước mình bằng việc xây dựng các trang web trên Internet nhằm giao lưu văn hoá và thu hút khách du lịch. Hơn thế nữa, hiện nay thư rác, các trang web thương mại, trang web phản động, trang web có nội dung không lành mạnh,… ngày càng xuất hiện dưới nhiều hình thức phong phú hơn. Chúng không chỉ được biểu diến một ngôn ngữ mà còn bởi đồng thời nhiều ngôn ngữ nhằm đi qua bộ lọc thư rác, hay các bộ lọc nội dung của máy tìm kiếm. Vì thế, việc xây dựng bộ phân lớp văn bản tự động cho nhiều ngôn ngữ là rất cần thiết. 5 Chúng ta có thể xây dựng một bộ phân lớp như vậy bằng cách sử dụng một bộ nhận dạng ngôn ngữ cho văn bản rồi mới tiến hành phân lớp. Đây là một phương pháp hay, tuy nhiên khó khăn gặp khi phân lớp các tài liệu có nhiều ngôn ngữ xuất hiện đồng thời. Hướng đến việc xây dựng công cụ áp dụng cho các ứng dụng vừa và nhỏ, trong khoá luận này, chúng tôi đề xuất tiếp cận cho bài toán phân lớp văn bản trên nhiều ngôn ngữ theo hướng không phụ thuộc ngôn ngữ (độc lập) sử dụng mô hình entropy cực đại. 1.2.2. Phân lớp văn bản độc lập ngôn ngữ Phân lớp văn bản độc lập ngôn ngữ là một bài toán phân lớp văn bản, cho phép sắp xếp một văn bản vào một lớp bất kì mà không cần quan tâm đến ngôn ngữ trên văn bản đó. Điều đó cũng có nghĩa là các văn bản trên những ngôn ngữ khác nhau được coi là bình đẳng. Ý nghĩa của chữ “độc lập” là như vậy. Trong [7], Fuchen đề xuất ý tưởng sử dụng mô hình ngôn ngữ N-gram giải quyết các bài toán xử lý ngôn ngữ tự nhiên độc lập