Tài liệu Phân loại văn bản tiếng việt sử dụng phương pháp máy hỗ trợ vector (support vector machine – svms)

HỌC VIỆN NGÂN HÀNG KHOA HỆ THỐNG THÔNG TIN QUẢN LÝ KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC Đề tài: Phân loại văn bản tiếng Việt sử dụng phƣơng pháp Máy Hỗ Trợ Vector (Support Vector Machine – SVMs) Giảng viên hƣớng dẫn : ThS. GIANG THỊ THU HUYỀN Sinh viên thực hiện : Lớp : Khoá : Hệ : HOÀNG THỊ NHUNG HTTTA 11 (2008-2012) CHÍNH QUY Hà Nội, tháng 6/2012 HỌC VIỆN NGÂN HÀNG KHOA HỆ THỐNG THÔNG TIN QUẢN LÝ KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC Đề tài: Phân loại văn bản tiếng Việt sử dụng phƣơng pháp Máy Hỗ Trợ Vector (Support Vector Machine – SVMs) Giảng viên hƣớng dẫn : ThS. GIANG THỊ THU HUYỀN Sinh viên thực hiện : Lớp : Khoá : Hệ : HOÀNG THỊ NHUNG HTTTA 11 (2008-2012) CHÍNH QUY Hà Nội, tháng 6/2012 HỌC VIỆN NGÂN HÀNG CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM KHOA HỆ THỐNG THÔNG TIN QUẢN LÝ Độc lập - Tự do – Hạnh phúc TÓM TẮT ĐỀ TÀI KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC Họ và tên sinh viên: HOÀNG THỊ NHUNG Lớp: HTTTA Khoá: 11 (2008-2012) Ngành đào tạo: Hệ thống thông tin quản lý Hệ đào tạo: Chính quy 1/ Tên khoá luận tốt nghiệp: Phân loại văn bản tiếng Việt sử dụng phương pháp Máy Hỗ Trợ Vector (SVMs – Support Vector Machine). 2/ Nội dung chính của khoá luận:  Chương 1: Trình bày những vấn đề cơ bản là nền tảng của các bài toán xử lý văn bản nói chung và bài toán phân loại nói riêng, các vấn đề liên quan tới việc tiền xử lý văn bản tiếng Việt, các kỹ thuật khai phá dữ liệu văn bản. Cuối cùng, trình bày về bài toán phân loại văn bản và các kỹ thuật đã được áp dụng trong bài toán này, cũng như giới thiệu qua về phương pháp phân loại văn bản SVMs.  Chương 2: Trình bày chi tiết về phương pháp phân loại văn bản SVMs.  Chương 3: Trình bày nội dung phân tích, thiết kế áp dụng phương pháp phân loại SVMs vào bài toán phân loại văn bản tiếng Việt.  Chương 4: Mô tả về chương trình xây dựng và các kết quả thực nghiệm nhằm kiểm thử chất lượng phân loại của phương pháp SVMs cho văn bản tiếng Việt. 3/ Ngày nộp khoá luận : 06/06/2012 GIÁO VIÊN HƢỚNG DẪN CHỦ NHIỆM KHOA (Ký, ghi rõ họ tên) (Ký, ghi rõ họ tên) i MỞ ĐẦU Sự phát triển trong lĩnh vực Công nghệ thông tin hiện nay là vô cùng lớn lao, đi đôi với nó là rất nhiều ưu điểm áp dụng trong cuộc sống của loài người chúng ta. Trong kỷ nguyên công nghệ, mọi thông tin, dữ liệu trao đổi của con người (như dữ liệu văn bản, âm thanh, hình ảnh, dữ liệu multimedia, …) đều có thể số hoá, lưu trữ và khai thác trên các thiết bị điện tử, trên máy tính và mạng Internet. Sự phát triển mạnh mẽ này đã dẫn đến việc mất khả năng kiểm soát thông tin của con người trong các phương pháp truyền thống. Nhu cầu về việc khai thác thông tin nhằm lấy ra những tri thức có ích cho con người là một trong những vấn đề được nêu ra. Đó chính là mảng đề tài về Khai phá dữ liệu (Data Mining) với các bài toán: Khai phá dữ liệu văn bản (Text Mining), Khai phá dữ liệu Web (Web Mining), Khai phá dữ liệu đa phương tiện (Multimedia Mining). Bài toán Khai phá dữ liệu văn bản đóng một vai trò quan trọng trong việc xử lý thông tin của con người, nó đang được rất nhiều nơi trên thế giới nghiên cứu và phát triển, áp dụng trên nhiều ngôn ngữ khác nhau. Phân loại văn bản là một trong những bài toán quan trọng thuộc lĩnh vực khai phá dữ liệu văn bản, nó đã được nghiên cứu và triển khai thông qua rất nhiều giải thuật khác nhau như: k láng giềng gần nhất (k-NN), mạng nơron, cây quyết định, … . Kết quả thu được với các phương pháp này cũng đã đạt được nhiều thành công trên nhiều ngôn ngữ khác nhau. Ngoài các phương pháp trên, hiện nay có nhiều phương pháp khác được nghiên cứu và hứa hẹn cho những ưu điểm tối ưu hơn, trong đó có phương pháp Máy vector hỗ trợ (Support Vector Machines - SVMs). SVMs được đánh giá là phương pháp có hiệu năng phân loại rất cao trong bài toán Phân loại văn bản. Nó đã được thực nghiệm áp dụng trên các văn bản tiếng Anh, Pháp, … và thu được kết quả khá tốt. Tuy nhiên, đối với ngôn ngữ Tiếng Việt thì đây là một phương pháp hoàn toàn mới mẻ, và đang được triển khai nghiên cứu. Chính vì lý do đó, em đã lựa chọn đề tài liên quan tới bài toán này. Với việc lựa chọn bài toán Phân loại văn bản sử dụng phương pháp SVMs, em mong muốn có những đóng góp nhất định trong lĩnh vực Khai phá dữ liệu văn bản Tiếng Việt, trên cơ sở đó xây dựng một ứng dụng có thể triển khai được rộng rãi các vấn đề liên quan tới phân loại dữ liệu văn bản. ii LỜI CẢM ƠN Để hoàn thành khóa luận tốt nghiệp đại học, trước hết em xin chân thành cảm ơn Ths Giang Thị Thu Huyền đã trực tiếp giảng dậy và tận tình giúp đỡ em trong quá trình nghiên cứu. Mặc dù có nhiều cố gắng nhưng do thời thời gian và kiến thức còn hạn chế nên chắc chắn khóa luận này vẫn còn có nhiều thiếu sót. Em rất mong nhận được những ý kiến đóng góp quý báu từ thầy cô giáo và các bạn. Hà Nội, ngày 01 tháng 06 năm 2012. Sinh viên thực hiện: Hoàng Thị Nhung iii NHẬN XÉT (Của nơi thực tập) .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. iv NHẬN XÉT (Của giảng viên hƣớng dẫn) .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. .………………………………………………………………………………………………….. v MỤC LỤC CHƢƠNG 1: TỔNG QUAN LÝ THUYẾT .........................................................................1 1.1 Tổng quan về khai phá tri thức................................................................................1 1.1.1 Khai phá dữ liệu .................................................................................................1 1.1.2 Khai phá dữ liệu văn bản ....................................................................................2 1.1.3 Bài toán phân loại văn bản .................................................................................4 1.1.4 Các khó khăn trong khai phá dữ liệu văn bản .....................................................4 1.2 Tiền xử lý và biểu diễn văn bản tiếng việt. ..............................................................5 1.2.1 Tiền xử lý văn bản tiếng Việt .............................................................................5 1.2.2 Tách thuật ngữ trong văn bản Tiếng Việt ............................................................5 1.2.3 Các kỹ thuật giảm chiều văn bản ........................................................................7 1.2.4 Các mô hình biểu diễn văn bản ...........................................................................8 1.2.4.1 Mô hình không gian vector (Vector Space Model) .....................................9 1.2.4.2 Áp dụng phương pháp vector thưa trong biểu diễn văn bản ...................... 10 1.3 Bài toán phân loại văn bản..................................................................................... 11 1.3.1 Tổng quan phân loại văn bản................................................................................ 11 1.3.2 Nền tảng học máy trong bài toán phân loại ........................................................... 12 1.3.3 Phương pháp máy vector hỗ trợ (Support Vector Machines) ................................ 13 1.3.2 Công thức xác định hiệu năng phân loại văn bản .................................................. 14 1.4 Kết chƣơng ............................................................................................................. 15 CHƢƠNG 2 . PHƢƠNG PHÁP PHÂN LOẠI MÁY VECTOR HỖ TRỢ SVMs ............ 16 2.1 Lý thuyết học thống kê ........................................................................................... 16 2.1.1 Chiều VC (Vapnik Chervonenkis Dimension) .................................................. 16 2.1.2 Rủi ro trong phương pháp học máy có giám sát ................................................ 17 2.1.3 Nguyên tắc tối thiểu hoá rủi ro cấu trúc ............................................................ 18 2.1.4 Bổ đề Vapnik ................................................................................................... 18 2.1.5 Nguyên lý nhận dạng mẫu (Pattern Recognition) .............................................. 19 2.2 Phƣơng pháp máy vector hỗ trợ SVMs ................................................................. 20 2.2.1 SVMs trường hợp dữ liệu tuyến tính ................................................................ 21 2.2.2 SVMs trường hợp tuyến tính nhưng có nhiễu ................................................... 23 2.2.3 SVMs trường hợp không thể phân chia tuyến tính ............................................ 25 2.3 Thuật toán tìm siêu phẳng phân tách tối ƣu ......................................................... 27 2.3.1 Tìm tham số α* theo thuật toán 2v-SVM .......................................................... 27 2.3.2 Thuật toán khởi tạo các biến α0 ........................................................................ 29 2.3.3 Đánh giá độ phức tạp của thuật toán 2v-SVM................................................... 30 2.4 Nhận xét về phƣơng pháp SVMs ........................................................................... 31 2.5 Kết chƣơng ............................................................................................................. 31 CHƢƠNG 3. THIẾT KẾ VÀ XÂY DỰNG CHƢƠNG TRÌNH ........................................ 32 3.1 Lựa chọn công cụ xây dựng giải pháp ................................................................... 32 3.1.1 Lựa chọn môi trường ........................................................................................ 32 3.1.2 Lựa chọn ngôn ngữ lập trình ............................................................................ 32 3.2 Phân tích và thiết kế chức năng ............................................................................. 32 3.2.1 Xác định yêu cầu .............................................................................................. 32 3.2.2 Thiết kế chức năng ........................................................................................... 33 3.2.2.1 Chức năng phân loại văn bản ................................................................... 34 3.2.2.2 Chức năng tiền xử lý văn bản ................................................................... 35 vi 3.3 Xây dựng các chức năng ........................................................................................ 36 3.3.1 Xây dựng chức năng tiền xử lý văn bản ............................................................ 36 3.3.1.1 Tiền xử lý ký tự ....................................................................................... 36 3.3.1.2 Tách từ khoá, loại bỏ từ dừng trong văn bản ............................................ 36 3.3.1.3 Trích chọn tập từ đặc trưng ...................................................................... 39 3.3.1.4 Lựa chọn mô hình biểu diễn văn bản ........................................................ 40 3.3.1.5 Cài đặt module tiền xử lý văn bản ............................................................ 40 3.3.2 Xây dựng chức năng phân loại SVMs .............................................................. 42 3.3.2.1 Module huấn luyện SVMs ....................................................................... 42 3.3.2.2 Module Kiểm tra SVMs ........................................................................... 45 3.4 Kết chƣơng ............................................................................................................. 47 CHƢƠNG 4. MÔ TẢ CHƢƠNG TRÌNH VÀ KẾT QUẢ THỬ NGHIỆM ...................... 48 4.1 Mô tả chƣơng trình ................................................................................................ 48 4.1.1 Giao diện chính của chương trình ..................................................................... 48 4.2 Kết quả thực nghiệm .............................................................................................. 50 4.2.1 Cơ sở dữ liệu thử nghiệm ................................................................................. 50 4.2.2 Cấu hình máy tính ............................................................................................ 50 4.2.3 Thực nghiệm phân tách từ khoá........................................................................ 50 4.2.3.1 Thực nghiệm về tốc độ tách từ ...................................................................... 51 4.2.3.2 Thực nghiệm về hiệu quả tách từ................................................................... 52 4.3.2.3 Đánh giá về chức năng tách từ ..................................................................... 54 4.2.4 Thực nghiệm phân loại văn bản với SVMs ....................................................... 54 4.2.4.1 Thực nghiệm quá trình trích chọn tập đặc trưng ............................................ 55 4.2.4.2 Thực nghiệm đánh giá hiệu năng phân loại đa lớp ......................................... 56 4.2.5 Nhận xét kết quả thực nghiệm .......................................................................... 59 4.3 Kết chƣơng ............................................................................................................. 59 CHƢƠNG 5. KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN .................................................... 60 PHỤ LỤC 1: Mô tả mã nguồn của chƣơng trình ............................................................... 62 PHỤ LỤC 2: Hƣớng dẫn sử dụng và cài đặt chƣơng trình. .............................................. 64 PHỤ LỤC 3: Mô tả nội dung đĩa CD kèm theo ................................................................. 65 DANH MỤC TÀI LIỆU THAM KHẢO ............................................................................ 66 vii DANH MỤC CÁC HÌNH Hình 1-1: Quy trình Khai phá tri thức – KDD Process. ................................................ 1 Hình 1-2: Mô hình chung bài toán Khai phá văn bản. ................................................. 3 Hình 1-3: Ví dụ quá trình phân loại văn bản. ............................................................... 4 Hình 1-4: Biểu diễn các vector văn bản trong không gian chỉ có 2 thuật ngữ. .............. 9 Hình 1-5: Mô hình phân loại văn bản tổng quát. ........................................................ 11 Hình 1-6: Cấu trúc phương pháp phân loại văn bản. .................................................. 12 Hình 1-7: Minh hoạ cách tính độ chính xác (precision) và độ bao (recall). ................. 14 Hình 2-1: Minh hoạ chiều VC trong không gian 2 chiều với 3 điểm dữ liệu. .............. 16 Hình 2-2: Minh hoạ các hàm {f(x)} trong không gian 2 chiều với 4 điểm dữ liệu. ...... 17 Hình 2-3: Phân tách tuyến tính được xác định bằng mặt hình học H (w•x + b = 0). .... 19 Hình 2-4: Siêu phẳng phân tách tối ưu H trường hợp tuyến tính. ................................ 21 Hình 2-5: Trường hợp dữ liệu huấn luyện có nhiễu. ................................................... 24 Hình 2-6: Thực hiện ánh xạ sang không gian đặc trưng kích thước ............................ 25 lớn thông qua hàm nhân. ............................................................................................ 26 Hình 3-1: Sơ đồ chức năng hệ thống xử lý văn bản. ................................................... 33 Hình 3-2: Sơ đồ minh hoạ chức năng Phân loại văn bản. ........................................... 34 Hình 3-4: Mô hình bộ tiền xử lý văn bản. .................................................................. 35 Hình 3-5: Lược đồ tiền xử lý tập dữ liệu và trích chọn tập đặc trưng. ......................... 41 Hình 3-7: Lược đồ thực hiện module huấn luyện. ...................................................... 43 Hình 4-1: Giao diện chính của chương trình Phân loại văn bản SVMs. ...................... 48 Hình 4-2: Giao diện chức năng huấn luyện SVMs. .................................................... 49 Hình 4-3: Giao diện chức năng kiểm tra hiệu năng SVMs. ......................................... 49 Hình 4-4: Biểu đồ biến thiên thời gian phân tách từ trên tập dữ liệu báo Vietnamnet. 51 Hình 4-5: Biểu đồ biến thiên thời gian phân tách từ trên tập dữ liệu báo VnExpress. . 52 viii DANH MỤC CÁC BẢNG Bảng 1-1: Một số hàm tính giá trị ước lượng thông tin của thuật ngữ. .......................... 8 Bảng 1-2: Ví dụ biểu diễn vector thưa........................................................................ 11 Bảng 4-1: Kết quả thực nghiệm phân tách trên bộ dữ liệu Vietnamnet ....................... 51 Bảng 4-2: Kết quả thực nghiệm trên bộ dữ liệu VnExpress ........................................ 52 Bảng 4-3: Kết quả thực nghiệm trích chọn tập đặc trưng trên báoVietnamnet. ........... 55 Bảng 4-4: Kết quả thực nghiệm phân loại đa lớp trên bộ dữ liệu báo Vietnamnet ...... 57 Bảng 4-5: Kết quả thực nghiệm phân loại đa lớp trên bộ dữ liệu báo VnExpress ...... 57 Bảng 4-6: Kết quả thực nghiệm phân loại đa lớp trên bộ dữ liệu báo Hanoimoi ......... 58 Bảng 4-7: Kết quả thực nghiệm phân loại đa lớp trên bộ dữ liệu báo Laodong ........... 58 Bảng 4-8: Tổng hợp kết quả phân loại đa lớp trên các bộ dữ liệu (báo Vietnamnet, VnExpress, Hanoimoi, Laodong) ............................................................................... 58 ix KÍ HIỆU CÁC CỤM TỪ VIẾT TẮT CSDL: Database Cơ sở dữ liệu. DM: Data Mining ML: Machine Learning Khai phá dữ liệu. Học máy. IDF: Inverse Document Frequency KDD: Knowledge Discovery in Database Mô hình nghịch đảo tần số văn bản. Phát hiện tri thức trong Cơ sở dữ liệu. k-NN: k-Nearest Neighbor OSH: Optimum Separation Hyperplance Thuật toán k láng giềng gần nhất. Siêu phẳng phân tách tối ưu. SVMs: Support Vector Machines Phương pháp máy vector hỗ trợ. TF: Term Frequency. Mô hình tần số thuật ngữ. TM: Text Mining Khai phá văn bản x Khoá luận tốt nghiệp Phân loại văn bản tiếng Việt sử dụng phương pháp SVMs CHƢƠNG 1: TỔNG QUAN LÝ THUYẾT Nội dung chương này sẽ trình bày những vấn đề lý thuyết về: lĩnh vực khai phá tri thức, khai phá dữ liệu văn bản, đặc biệt là bài toán phân loại văn bản. Đây là những nền tảng cơ bản của các bài toán xử lý văn bản nói chung và bài toán phân loại văn bản nói riêng. Tiếp theo, chương này sẽ đi sâu về bước tiền xử lý dữ liệu và các mô hình biểu diễn văn bản. Đây là một bước không thể thiếu trong quy trình khai phá dữ liệu văn bản, nó làm tiền đề cho các kỹ thuật xử lý các bài toán khai phá dữ liệu văn bản đã nêu. Cuối cùng, là đề cập đến các phương pháp tối ưu được áp dụng cho bài toán phân loại văn bản. 1.1 Tổng quan về khai phá tri thức 1.1.1 Khai phá dữ liệu Khai phá dữ liệu (Data Mining) được định nghĩa là quá trình phát hiện và trích chọn thông tin hữu ích ẩn chứa trong các cơ sở dữ liệu lớn hay các kho chứa thông tin khác [1]. Hiện nay, thuật ngữ khai phá dữ liệu luôn gắn liền với thuật ngữ phát hiện tri thức trong cơ sở dữ liệu (KDD – Knowledge Discovery in Database). Nó là một bước trong quy trình tổng quan KDD, nhưng được xem là bước quan trọng nhất. Sau đây là sơ đồ biểu diễn quy trình KDD [1]: Ước lượng và Trình diễn Tri thức Các mẫu dữ liệu Khai phá dữ liệu Lựa chọn và Chuyển đổi Kho chứa dữ liệu Làm sạch và Tích hợp Cơ sở dữ liệu Các tệp phẳng Hình 1-1: Quy trình Khai phá tri thức – KDD Process. Sinh viên thực hiện: Hoàng Thị Nhung – Lớp HTTTA-K11 Trang 1/67 Khoá luận tốt nghiệp Phân loại văn bản tiếng Việt sử dụng phương pháp SVMs  Làm sạch dữ liệu: Nhằm loại bỏ nhiễu và dữ liệu không cần thiết. Các dữ liệu cần loại bỏ ở đây có thể là dấu hiệu, ký hiệu, ký tự không mang nhiều ý nghĩa.  Tích hợp dữ liệu: Là quá trình tích hợp dữ liệu từ nhiều nguồn khác nhau.  Lựa chọn dữ liệu: Ở bước này, các dữ liệu liên quan tới quá trình phân tích sẽ được lựa chọn từ cơ sở dữ liệu.  Chuyển đổi dữ liệu: Các dữ liệu được biến đổi hoặc kết hợp thành các mẫu phù hợp với quá trình khai thác.  Khai thác dữ liệu: Đây là bước quan trọng nhất, ở giai đoạn này lựa chọn các phương thức thông minh (theo thứ tự nhất định) để trích chọn ra các mẫu dữ liệu.  Ƣớc lƣợng mẫu: Đánh giá tính chân thực của các mẫu liên quan về tri thức dựa trên các phương pháp chuẩn nhất định.  Biểu diễn tri thức: Là quá trình sử dụng các kĩ thuật biểu diễn và thể hiện trực quan các tri thức khai thác cho người dùng. Hình 1-1 thể hiện 7 quá trình của KDD, trong đó khai thác dữ liệu là một trong các bước của quy trình KDD. Khai phá dữ liệu có hai nhiệm vụ chính, đó là: Mô tả và dự đoán [2].  Nhiệm vụ mô tả (Description Task): Nhằm tìm ra các mẫu thông tin để mô tả dữ liệu mà con người có thể hiểu được. Tương ứng với nhiệm vụ này có một số bài toán liên quan như: lập nhóm, phát hiện luật kết hợp, … .  Nhiệm vụ dự đoán (Prediction Task): Sử dụng một số biến để dự đoán những giá trị chưa biết hay giá trị trong tương lai của biến khác. Tương ứng với nhiệm này có một số bài toán liên quan như: phân loại, hồi quy, phát hiện độ lệch. Việc tổ chức dữ liệu áp dụng trong bước khai phá dữ liệu là rất quan trọng. Có rất nhiều cách tổ chức dữ liệu khác nhau, cách phổ biến hiện nay là cơ sở dữ liệu quan hệ, ngoài ra còn có: Cơ sở dữ liệu hướng đối tượng, cơ sở dữ liệu không qian, cơ sở dữ liệu hướng thời gian thực, và cơ sở dữ liệu fulltext, … . Đối với mỗi dạng cơ sở dữ liệu lại có các phương pháp xử lý khác nhau và mục đích khai thác dữ liệu khác nhau tùy theo tính chất và đặc thù của dữ liệu. Hiện nay người ta biết đến nhiều kỹ thuật được sử dụng trong khai phá dữ liệu bao gồm: các kỹ thuật truyền thống như học máy (machine learning), nhận dạng (recognition), thống kê (statistics), phân loại (classification), …,các kỹ thuật được phát triển bởi ngành nghiên cứu trí tuệ nhân tạo như mạng nơ-ron nhân tạo (neural network), thuật toán di truyền (generic algorithm), quy nạp luật (rule reduction), cây quyết định (decision tree), … . 1.1.2 Khai phá dữ liệu văn bản Trong các loại dữ liệu thì văn bản là loại dữ liệu chiếm đa số trong CSDL. Văn bản có những đặc điểm chung của dữ liệu và cũng có những đặc điểm khác biệt với các loại dữ liệu khác như âm thanh, hình ảnh,… . Về mặt lưu trữ, dữ liệu văn bản được chia thành hai loại [25]: Sinh viên thực hiện: Hoàng Thị Nhung – Lớp HTTTA-K11 Trang 2/67 Khoá luận tốt nghiệp Phân loại văn bản tiếng Việt sử dụng phương pháp SVMs  Dạng phi cấu trúc (unstructured): là dạng văn bản chúng ta sử dụng hằng ngày được thể hiện dưới dạng ngôn ngữ tự nhiên của con người và chúng không có một cấu trúc cụ thể nào. Ví dụ, văn bản lưu dưới dạng tệp tin TXT.  Dạng bán cấu trúc (semi-structured): đây là các dạng văn bản không được lưu trữ dưới dạng các bản ghi chặt chẽ mà được tổ chức qua các đánh dấu để thể hiện nội dung chính của văn bản. Ví dụ, các văn bản lưu dưới dạng tệp tin HTML, e-Mail, Doc, … . Do thiếu tính cấu trúc nên để khai phá dữ liệu trước tiên ta phải đưa các văn bản về dạng có cấu trúc. Khai phá dữ liệu văn bản (Text mining) là một lĩnh vực nhỏ trong Khai phá dữ liệu. Khai phá dữ liệu văn bản được định nghĩa là quá trình tìm kiếm tri thức trong những tập hợp bao gồm rất nhiều văn bản có nội dung đa dạng và được thu thập từ nhiều nguồn khác nhau. Kỹ thuật khai phá dữ liệu văn bản được mô tả theo [4]: Text Mining = Data Mining + Language Engineering. Trong đó:  Data mining: Sử dụng các kỹ thuật trong quy trình khai thác dữ liệu áp dụng riêng đối với dữ liệu văn bản.  Language Engineering: Kỹ thuật ngôn ngữ, nhằm xử lý riêng ngôn ngữ thể hiện nội dung dữ liệu văn bản. Nói chung, khai phá dữ liệu văn bản bao gồm các bước: Thu thập dữ liệu ở dạng văn bản, làm sạch chúng, phân tích biến đổi, lấy thông tin và hiển thị. Hiển thị văn bản Xử lý văn bản Tiền xử lý làm sạch Thu thập văn bản Nguồn dữ liệu Hình 1-2: Mô hình chung bài toán Khai phá văn bản. Sinh viên thực hiện: Hoàng Thị Nhung – Lớp HTTTA-K11 Trang 3/67 Khoá luận tốt nghiệp Phân loại văn bản tiếng Việt sử dụng phương pháp SVMs 1.1.3 Bài toán phân loại văn bản Phân loại văn bản là quy trình gán một tài liệu văn bản vào một hoặc nhiều lớp văn bản thích hợp dựa vào nội dung của văn bản. d1 C1 d2 d3 C2 d4 C3 dn C4 C5 ... Ck Hình 1-3: Ví dụ quá trình phân loại văn bản. Bài toán phân loại văn bản được ứng dụng trong rất nhiều lĩnh vực khác nhau, một trong những ứng dụng quan trọng nhất của bài toán này là ứng dụng tìm kiếm văn bản. Từ tập dữ liệu đã được phân loại, các văn bản sẽ được đánh chỉ số đối với từng lớp tương ứng. Người dùng có thể xác định chủ đề mà mình muốn tìm thông qua các truy vấn. 1.1.4 Các khó khăn trong khai phá dữ liệu văn bản Mặc dù có nhiều cách tiếp cận đã được đề xuất nhưng hầu hết các giải pháp đều chưa giải quyết hoàn toàn một số vấn đề trong khai phá dữ liệu:  Tính đa chiều (high dimensionality): Số thuật ngữ trong một văn bản có thể lên đến hàng nghìn, thậm chí hàng chục nghìn. Nếu mỗi thuật ngữ trong một ngôn ngữ nào đó được biểu diễn bằng một chiều trong không gian vector thì số chiều không gian vector sẽ rất lớn. Điều này dẫn đến rất nhiều khó khăn chẳng hạn như chi phí tính toán cao.  Tính khả cỡ (scability): Các cơ sở dữ liệu lớn thường chứa hàng trăm nghìn văn bản. Nhiều thuật toán khai phá dữ liệu có thể làm việc tốt với tập dữ liệu nhỏ nhưng khi xử lý trên tập dữ liệu lớn thì không hiệu quả.  Tính chính xác (accuracy): Trong các ngôn ngữ khác nhau đều có sự nhập nhằng chẳng hạn như: từ đồng nghĩa, từ đồng âm khác nghĩa. Trong những trường hợp này, phải dựa vào ngữ cảnh mới xác định được chúng.  Biểu diễn kết quả một cách dễ hiểu: Kết quả sau khi khai phá dữ liệu cần được biểu diễn ở cấu trúc được mô tả một cách dễ hiểu để người sử dụng có thể truy cập một cách dễ dàng.  Tri thức tiên nghiệm: Trong nhiều bài toán chẳng hạn như bài toán lập nhóm văn bản, thì người sử dụng phải xác định trước một số tham số đầu vào (như số nhóm văn bản cần lập). Tuy nhiên, trong nhiều trường hợp người sử dụng lại không hiểu những gì mình cần. Sinh viên thực hiện: Hoàng Thị Nhung – Lớp HTTTA-K11 Trang 4/67 Khoá luận tốt nghiệp Phân loại văn bản tiếng Việt sử dụng phương pháp SVMs Chính vì những lý do trên hiện nay khai phá dữ liệu văn bản là một trong những lĩnh vực đang đặt ra nhiều thách thức thu hút nhiều nhóm nghiên cứu nhằm tìm ra giải pháp thích hợp để giải quyết khó khăn trên. 1.2 Tiền xử lý và biểu diễn văn bản tiếng việt. 1.2.1 Tiền xử lý văn bản tiếng Việt Tiền xử lý trong văn bản chính là bước nhằm biến đổi văn bản về dạng tài liệu chuẩn có cấu trúc xác định. Các ngôn ngữ trên thế giới có những đặc điểm khác nhau do đó việc tiền xử lý để loại bỏ các từ ngữ không cần thiết, tách các thuật ngữ, … cho các văn bản là không giống nhau. Nhìn chung một quy trình tiền xử văn bản bao gồm các bước như sau:  Tiền xử lý ký tự Mục đích nhằm làm giảm sự nhập nhằng trong việc biểu diễn ký tự. Ví dụ như trong xử lý văn bản Tiếng Việt, loại bỏ sự khác nhau giữa chữ hoa và chữ thường bằng cách chuyển tất cả các ký tự chữ hoa thành chữ thường; hoặc chuyển các ký tự không có trong bộ chữ cái Tiếng Việt thành dấu chấm “.”.  Tách các từ khoá trong văn bản Là thao tác tách văn bản thành danh sách các từ khoá (thuật ngữ) với một sai số chấp nhận được để chuẩn bị cho việc biểu diễn văn bản dưới dạng cấu trúc. Đối với các ngôn ngữ khác nhau thì việc tách từ cũng có những đặc điểm khác nhau.  Loại bỏ từ dừng trong văn bản Từ dừng (stopword) là những từ mang ít ý nghĩa trong xử lý văn bản mà nó lại xuất hiện trong hầu hết các văn bản, chẳng hạn như: các liên từ, giới từ … (như trong Tiếng Việt: nếu, thì, vì thế, hơn nữa, tuy nhiên, …). Việc loại bỏ các từ dừng đồng nghĩa với việc giảm số chiều của văn bản.  Biểu diễn văn bản về dạng cấu trúc Là quá trình sử dụng các mô hình biểu diễn văn bản để đưa văn bản về dạng dễ giải quyết, phù hợp với ứng dụng trong bài toán Khai thác dữ liệu. Một số mô hình biểu diễn thường được sử dụng để biểu diễn gồm: mô hình không gian vector, mô hình dựa trên tập mờ (Fuzzy Set), mô hình dựa trên tập thô (Rough Set), … . . 1.2.2 Tách thuật ngữ trong văn bản Tiếng Việt Tiếng Việt là ngôn ngữ đơn âm tiết khác với các ngôn ngữ đa âm tiết như nhóm ngôn ngữ Ấn-Âu. Khác với các ngôn ngữ đơn âm tiết khác như tiếng Trung Quốc hay tiếng Thái Lan, tiếng Việt được viết bằng các ký tự Latinh mở rộng. Vì vậy cách xử lý các ngôn ngữ này cũng không thể áp dụng hoàn toàn cho tiếng Việt. Về mặt đơn vị ngôn ngữ, tiếng Việt có hai đơn vị ngôn ngữ nhỏ nhất là tiếng và từ [24]: Sinh viên thực hiện: Hoàng Thị Nhung – Lớp HTTTA-K11 Trang 5/67 Khoá luận tốt nghiệp Phân loại văn bản tiếng Việt sử dụng phương pháp SVMs  Tiếng: Mỗi tiếng trong tiếng Việt được viết thành một chữ, ngược lại mỗi chữ đọc thành một tiếng, mỗi chữ nằm giữa hai dấu phân cách trong câu. Tiếng dùng để tạo thành từ, tiếng có thể có nghĩa rõ ràng hoặc không có nghĩa rõ ràng. Ví dụ: - Từ tạo bởi một tiếng: “tôi”, “tớ”. - Từ tạo bởi nhiều tiếng có nghĩa rõ ràng: “hoa hồng” = “hoa” + “hồng”.  Từ: Hiện nay đang tồn tại nhiều định nghĩa khác nhau về từ trong tiếng Việt, nhưng tất cả những nghiên cứu ngôn ngữ đều đồng ý “từ” trong tiếng Việt có những đặc điểm sau: - Từ phải đầy đủ về phương diện hình thức, ngữ nghĩa và độc lập về mặt ngữ pháp - Từ được xây dựng từ tiếng. - Từ có thể là các từ đơn (1 tiếng) hoặc từ phức (gồm nhiều tiếng) Ghi chú: Trong tiếng Việt, một từ có độ dài không quá 5 tiếng ghép thành.  Đặc điểm về chính tả: Mặc dù chính tả tiếng Việt đã có một hệ thống các quy tắc chuẩn mực, nhưng vẫn có một số từ mà tồn tại nhiều cách viết khác nhau: - Những từ đồng âm: y/i (vật lý/ vật lí, tốc ký/ tốc kí, bác sỹ/ bác sĩ); d/gi (dông bão/ giông bão). - Phương ngữ: chính đáng/ chánh đáng, con tru/ con trâu, … . - Vị trí dấu trong một âm: khai hoả/ khai hỏa, … . - Cách viết hoa tuỳ tiện đối với các danh từ riêng: tồn tại nhiều cách viết khác nhau. Ví dụ: Bộ Khoa học công nghệ và môi trường/ Bộ Khoa học công nghệ & Môi trường, Việt Nam/ Việt nam, … . - Phiên âm tiếng nước ngoài: phiên âm là hình thức biến chữ ngoại quốc thành chữ địa phương. Nhưng hiện nay vẫn tồn tại cả hai cách viết phiên âm và không phiên âm, chẳng hạn: Singapo/ Xing-ga-po, America/ Hoa Kỳ, Trung Quốc/ Trung Hoa, … . - Dấu gạch nối: thường xuất hiện khi các từ đa âm nước ngoài du nhập vào Việt Nam. Để chỉ rõ đây là chữ chứ không phải là một cụm chữ, người ta dùng dấu gạch nối. Tuy nhiên vẫn tồn tại hai cách viết, ví dụ Portugal được dịch thành Bồ Đào Nha/ Bồ-Đào-Nha. Do đặc điểm của tiếng Việt không thể sử dụng các ký tự trắng để phân tách các thuật ngữ nên có một cách phổ biến là sử dụng một từ điển thuật ngữ để phát hiện từ. Sau đây, em sẽ giới thiệu một số phương pháp tách thuật ngữ áp dụng đối với văn bản tiếng Việt [15][16].  Tách thuật ngữ theo độ dài từ dài nhất Đây là phương pháp tách thuật ngữ đơn giản và dễ cài đặt, và hiệu quả thu được tương đối tốt (giải thuật này sẽ được áp dụng triển khai trong chương Sinh viên thực hiện: Hoàng Thị Nhung – Lớp HTTTA-K11 Trang 6/67 Khoá luận tốt nghiệp Phân loại văn bản tiếng Việt sử dụng phương pháp SVMs trình demo). Phương pháp này sử dụng một từ điển từ vựng để làm cơ sở phân tách thuật ngữ.  Thuật ngữ theo phƣơng pháp đồ thị Phương pháp tách thuật ngữ bằng đồ thị quy việc phân tách câu về việc tìm đường đi trên một đồ thị có hướng, không có trọng số. 1.2.3 Các kỹ thuật giảm chiều văn bản Quá trình tiền xử lý tách từ cho văn bản đưa lại một danh sách rất lớn các từ khoá. Khi tập từ khoá này càng lớn thì không gian để lưu trữ văn bản cũng càng lớn, và việc xử lý càng tốn nhiều thời gian. Do đó, cần loại bớt những từ không có, hoặc ít có giá trị trong quá trình xử lý văn bản. Các bước áp dụng giúp giảm kích thước chiều của văn bản, bao gồm:  Loại bỏ từ dừng (Stopwords) Trong các ngôn ngữ tự nhiên có rất nhiều từ dùng biểu diễn cấu trúc câu nhưng lại không mang nhiều ý nghĩa về mặt nội dung, chẳng hạn các từ loại thuộc: giới từ, liên từ, … . Các loại từ này xuất hiện thường xuyên trong các văn bản nhưng không hề mang bất cứ một thông tin nào về nội dung hay chủ đề bài viết. Hơn nữa, việc xuất hiện của các từ dừng có thể làm chi phối, làm giảm chất lượng kết quả của việc xử lý văn bản. Việc loại bỏ từ dừng đồng nghĩa với việc giảm số chiều văn bản, nhưng lại mang lại làm tăng chất lượng xử lý văn bản. Ngoài ra, trong xử lý văn bản thường các động từ không đóng vai trò quan trọng, do đó để làm giảm số chiều văn bản ta cũng có thể loại đi các động từ. Để thực hiện được việc này, ta có thể áp dụng phương pháp phân tích cú pháp câu để tìm các động từ, đây là phương pháp hay nhưng lại có độ phức tạp cao, tốn thời gian xử lý. Trong ngôn ngữ tiếng Việt, những từ đứng sau các từ “đã”, “đang”, và “sẽ” luôn là các động từ, do đó ta có thể áp dụng điều này để có thể loại bỏ một phần những từ không quan trọng trong danh sách biểu diễn.  Lựa chọn tập đặc trƣng cho không gian văn bản Sau khi đã loại bỏ các từ trong danh sách thuật ngữ phân tách, tập các từ khoá T của văn bản mặc dù đã giảm đi đáng kể, nhưng vẫn có kích thước rất lớn (nếu đầu vào là một tập văn bản lớn). Kỹ thuật lựa chọn tập thuật ngữ đặc trưng (hay giảm không gian thuật ngữ - Term Space Reduction -TSR) [25] sẽ giúp làm giảm số chiều của văn bản, tức sẽ chọn ra tập thuật ngữ T’ từ tập thuật ngữ T (với |T’| << |T|), sao cho khi sử dụng nó để biểu diễn tài liệu nó cho ta hiệu quả cao nhất. Giảm số chiều có khuynh hướng làm giảm hiện tượng tràn lỗi (overfitting). Một trong những phương pháp lựa trọn tập đặc trưng cho kết quả cao đó là sử dụng phương pháp lựa chọn thuật ngữ đặc trưng dựa trên lý thuyết thông tin. Theo phương pháp này, để lựa chọn tập thuật ngữ đặc trưng, ta sử dụng các hàm để tính giá trị thông tin của thuật ngữ. Sau đây là một số hàm ước lượng thông tin hay dùng: Sinh viên thực hiện: Hoàng Thị Nhung – Lớp HTTTA-K11 Trang 7/67 Khoá luận tốt nghiệp Phân loại văn bản tiếng Việt sử dụng phương pháp SVMs Bảng 1-1: Một số hàm tính giá trị ước lượng thông tin của thuật ngữ. Tên hàm Kí hiệu DIA association factor z(tk,ci) Information Gain IG(tk,ci) Mutual Information MI(tk,ci) Chi-square χ2(tk,ci) Correlation Coefficient CC(tk,ci) Relevancy score RS(tk,ci) Odds Ratio OR(tk,ci) Công thức toán học P(ci|tk)   P(t , c). log c{ci ,ci } t{tk ,t k } log P(t , c) P(t ).P(c) P(t k , ci ) P(t k ).P(ci ) | Tr | .[ P(t k , ci ).P(t k , c i )  P(t k , c i ).P(t k , ci )] P(t k ).P(t k ).P(ci ).P(c i ) | Tr |.[ P(t k , ci ).P(t k , c i )  P(t k , c i ).P(t k , ci )] P(t k ).P(t k ).P(ci ).P(c i ) log P(t k | ci )  d P(t k | c i )  d P(t k | ci ).[1  P(t k | c i )] [1  P(t k | ci )].P(t k | c i ) Trong đó: - P( t k , ci ): là xác suất lựa chọn ngẫu nhiên một văn bản x trong tập văn bản huấn luyện, thì x không chứa thuật ngữ tk và x  ci, xác suất này bằng số lần xảy ra trong tập huấn luyện - P(tk,ci): xác suất chọn ngẫu nhiên một văn bản x, mà x chứa tk và x ci. - P(ci): xác suất chọn ngẫu nhiên một văn bản x, mà x  ci. - P(tk): xác suất ngẫu nhiên một văn bản x, mà x chứa thuật ngữ tk. Với hàm ước lượng thông tin nêu trên, ta sẽ tiến hành tính toán giá trị hàm ước lượng thông tin của thuật ngữ tk đối với lớp ci để quyết định xem có nên lựa chọn tk làm đặc trưng của văn bản hay không. Chúng ta sẽ chỉ giữ lại những thuật ngữ có giá trị ước lượng thông tin không thấp hơn ngưỡng cho trước, nếu hàm ước lượng thông tin của tk thấp hơn ngưỡng thì nó sẽ bị loại bỏ. Nhiều kết quả thực nghiệm trên các tập mẫu khác nhau đã chỉ ra rằng, các kỹ thuật như: IG hoặc χ2 có thể giảm không gian thuật ngữ tới 100 lần mà không ảnh hưởng (hoặc giảm rất ít) hiệu quả phân loại. 1.2.4 Các mô hình biểu diễn văn bản Như ta đã biết, để có thể xử lý được văn bản ta phải chuyển chúng về dạng dữ liệu có cấu trúc. Để có thể thực hiện được công việc này, người ta đưa ra các mô hình biểu diễn văn bản. Mô hình biểu diễn văn bản có ảnh hưởng rất nhiều đến hiệu quả và hiệu suất xử lý các văn bản. Tuỳ mục đích, yêu cầu đặt ra của ứng dụng mà ta sẽ lựa chọn mô hình biểu diễn và phương pháp xử lý phù hợp. Dưới đây là một số mô hình dùng để biểu diễn văn bản: Sinh viên thực hiện: Hoàng Thị Nhung – Lớp HTTTA-K11 Trang 8/67