Tài liệu Tóm tắt văn bản tiếng việt theo chủ đề

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI ----------------------------------------------- NGUYỄN HỒNG THÁI TÓM TẮT VĂN BẢN TIẾNG VIỆT THEO CHỦ ĐỀ LUẬN VĂN THẠC SĨ KHOA HỌC CHUYÊN NGÀNH: CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Lê Thanh Hương Hà Nội - 2008 ĐỒ ÁN TỐT NGHIỆP CAO HỌC ĐỀ TÀI: “TÓM TẮT VĂN BẢN TIẾNG VIỆT THEO CHỦ ĐỀ” LỜI CẢM ƠN Em xin gửi lời cảm ơn chân thành và sâu sắc nhất tới cô giáo TS. Lê Thanh Hương đã tận tình hướng dẫn và giúp đỡ trong quá trình làm đồ án. Mặc dù em đã cố gắng hoàn thành luận văn này trong phạm vi khả năng cho phép nhưng chắc chắn không không thể tránh được những thiếu sót. Chúng em kính mong được nhận được sự thông cảm và sự chỉ bảo tận tình của các thầy cô và các bạn. Sinh viên: Nguyễn Hồng Thái Lớp: Cao học CNTT 2006-2008 Hà Nội 10/2008 Nguyễn Hồng Thái – Lớp cao học CNTT 2006-2008 0 ĐỒ ÁN TỐT NGHIỆP CAO HỌC ĐỀ TÀI: “TÓM TẮT VĂN BẢN TIẾNG VIỆT THEO CHỦ ĐỀ” LỜI NÓI ĐẦU Trong thời đại bùng nổ thông tin ngày nay, sự phát triển vượt bậc của công nghệ thông tin đã làm tăng đáng kể số lượng giao dịch trên mạng Internet đặc biệt là thư viện điện tử, sách báo điện tử…, mà thời gian luôn có hạn mà với mỗi người, ngày càng nhiều việc phải làm hơn. Và thế là vấn đề làm sao để khai thác thông tin một cách hiệu quả trong các hoạt động xử lý thông tin đã được nhiều người dùng tin quan tâm. Dĩ nhiên là đã xuất hiện hàng loạt các công cụ tìm kiếm tương đối thông minh như Google, Altavista, Yahoo…Song một vấn đề đặt ra là chúng ta không thể đọc hết tất cả các thông tin trên sách báo điện tử hay những gì mà các công cụ tìm kiếm đó đem lại. Để giải quyết vấn đề đó, người viết luận văn xin đề xuất giải pháp “Tóm tắt văn bản tiếng Việt theo chủ đề”. Mục đích của đề tài là trích rút nội dung chính của các văn bản tiếng Việt lại, hiển thị cho người đọc từ đó người sử dụng xem xét nội dung đó có cần đọc không? Nếu có người sử dụng tiến hành đọc chi tiết văn bản gốc, nếu không người sử dụng dừng lại, không cần phải đọc nữa. Hướng tiếp cận của người viết luận văn hướng đến các lĩnh vực trong nội dung văn bản cần tóm tắt. Các lĩnh vực này chính là cấu trúc về nội dung của các tờ báo điện tử, thư viện điện tử,… Người viết luận văn sử dụng các thành quả đạt về xử lý văn bản tiếng Việt như bài toán phân tách từ, bài toán phân nhóm, phân lớp văn bản, bài toán tóm tắt văn bản. Nội dung của luận văn gồm có 4 chương trong đó: Chương 1. Trình bầy về các cơ sở lý thuyết của lĩnh vực khai phá dữ liệu văn bản và xử lý ngôn ngữ tự nhiên. Đó là các lý thuyết chung về khai phá dữ liệu văn bản, mối liên quan giữa xử lý ngôn ngữ tự nhiên với khai phá dữ liệu văn bản. Đặc biệt người viết luận văn có đi sâu phân tích đặc điểm ngôn ngữ tiếng Việt. Chương 2. Trình bầy về thành tựu đạt được về các bài toán liên quan tới hướng tiếp cận tóm tắt văn bản tiếng Việt theo chủ đề. Đó là các bài toán tách từ, phân nhóm văn bản, phân lớp văn bản và tóm tắt văn bản. Chương 3. Trình bầy về mô hình, giải pháp cho bài toán tóm tắt văn bản theo chủ đề mà người viết luận văn đề xuất. Đó là mô hình xây dựng các lĩnh vực trước tạo Nguyễn Hồng Thái – Lớp cao học CNTT 2006-2008 1 ĐỒ ÁN TỐT NGHIỆP CAO HỌC ĐỀ TÀI: “TÓM TẮT VĂN BẢN TIẾNG VIỆT THEO CHỦ ĐỀ” lên các chủ đề. Từ đó một văn bản đầu vào sẽ được trích rút ra chủ đề nội dung, chủ đề văn bản, chủ đề khái niệm…Dựa vào độ trích rút mà tiến hành đưa ra kết quả đầu ra. Chương 4. Trình bầy về phân tích thiết kế hệ thống, cài đặc và kiểm thử cho giải pháp mà người viết luận văn đề xuất. Đó là quá trình phân tách từ vựng của văn bản. Đó là quá trình tìm nội chính của chủ đề, đó là kết quả trích rút. Nguyễn Hồng Thái – Lớp cao học CNTT 2006-2008 2 ĐỒ ÁN TỐT NGHIỆP CAO HỌC ĐỀ TÀI: “TÓM TẮT VĂN BẢN TIẾNG VIỆT THEO CHỦ ĐỀ” DANH MỤC TỪ VIẾT TẮT STT Từ viết tắt Giải nghĩa 1. KDD Phát hiện tri thức trong cơ sở dữ liệu 2. TFxIDF Term Frequency times Inverse Document Frequency 3 IR 4. NLP 5. NLG 6. SVM 7. CFG Văn phạm phi ngữ cảnh 8. CSDL Cơ sở dữ liệu 9. POS 10. RST 11. HMM 12 LRMM Knowledge Discovery in Databases Hệ thu thập thông tin Information Retrieval Natural Language Processing Xử lý ngôn ngữ tự nhiên Natural Language Generating Sinh ngôn ngữ tự nhiên Support Vector Machine Mô hình máy vector hỗ trợ Context Free Grammar Part of Speech Từ loại Rhetorical Structure Theory Lý thuyết cấu trúc tu từ Hidden Markov Model Mô hình Markov ẩn Left Right Maximum Matching Tách từ dài nhất từ trái qua phải Nguyễn Hồng Thái – Lớp cao học CNTT 2006-2008 3 ĐỒ ÁN TỐT NGHIỆP CAO HỌC ĐỀ TÀI: “TÓM TẮT VĂN BẢN TIẾNG VIỆT THEO CHỦ ĐỀ” DANH MỤC HÌNH VẼ Hình 1-1:Tiến trình khai phá dữ liệu và phát hiện tri thức (KDD) ......................................... 10 Hình 1-2: Quan hệ Dữ liệu – Thông tin – Tri thức ................................................................. 11 Hình 1-3: Chức năng dẫn đường văn bản trong VNExpress .................................................. 17 Hình 1-4: Các vector văn bản trong không gian có 3 thuật ngữ ............................................. 18 Hình 1-5: Phân tích cú pháp ................................................................................................... 27 Hình 2-1: Các phương pháp tách từ ........................................................................................ 36 Hình 2-2: Sơ đồ hệ thống WFST ............................................................................................ 42 Hình 2-3: Mô hình hệ thống IGATEC .................................................................................... 45 Hình 2-4: Ví dụ mô tả giải thuật k-means ............................................................................. 48 Hình 2-5: Tóm tắt trang tin ..................................................................................................... 58 Hình 2-6: Tóm tắt hoạt động để hiển thị trên thiết bị cầm tay ................................................ 58 Hình 2-7: Tóm tắt danh sách tìm kiếm từ Google và gợi ý đọc tiếp ...................................... 59 Hình 2-8: Tóm tắt tài liệu khoa học ........................................................................................ 59 Hình 2-9: Mô hình hệ Tóm tắt văn bản tổng quát .................................................................. 60 Hình 2-10: Mô hình một hệ Trích rút văn bản ........................................................................ 61 Hình 2-11: Quan hệ lẫn nhau giữa các đoạn trong văn bản .................................................... 63 Hình 3-1: Tập mẫu của chủ đề ................................................................................................ 77 Hình 3-2: Tính chủ đề trong cơ cấu đào tạo trường Cao đẳng công nghiệp Hà Nội .............. 78 Hình 3-3: Cây chủ đề trong báo điện tử www.vnexpress.net ................................................. 79 Hình 3-4: Tính chủ đề của mô hình tóm tắt văn bản theo chủ đề ........................................... 85 Hình 3-5: Mô hình tóm tắt văn bản theo chủ đề ..................................................................... 87 Hình 3-6: Tính chủ đề trong tòa soạn báo www.vnexpress.net .............................................. 90 Hình 3-7: Biểu thị việc tìm ra k khái niệm trong tập mẫu của chủ đề .................................... 92 Hình 3-8: Thuật toán Tách từ sử dụng phương pháp LRMM ................................................ 95 Hình 3-9: Thuật toán K-Mean ................................................................................................ 97 Hình 3-10: Minh họa việc khoanh vùng k văn bản gần nhất với k = 5 .................................. 97 Hình 4-1: Các chức năng hệ thống ....................................................................................... 103 Hình 4-2: Sơ đồ hệ thống ...................................................................................................... 104 Hình 4-3: Biểu đồ tập mẫu trên vnexpress.net và trên vietnamnet.vn .................................. 107 Hình 4–4: Biểu đồ kết quả đánh giá trích rút về nội dung .................................................... 111 Hình 4-5: Biểu đồ kết quả đánh giá trích rút về độ trơn ....................................................... 113 Nguyễn Hồng Thái – Lớp cao học CNTT 2006-2008 4 ĐỒ ÁN TỐT NGHIỆP CAO HỌC ĐỀ TÀI: “TÓM TẮT VĂN BẢN TIẾNG VIỆT THEO CHỦ ĐỀ” DANH MỤC BẢNG Bảng 1-1: Ví dụ về biểu diễn văn bản theo mô hình vector tần suất ...................................... 18 Bảng 1-2: So sánh đặc điểm tiếng Việt với đặc điểm tiếng Anh ............................................ 22 Bảng 2-1: Phương pháp đánh giá............................................................................................ 72 Bảng 2–2: Đánh giá nội dung văn bản trích rút ...................................................................... 75 Bảng 2-3: Đánh giá theo độ trơn của văn bản ........................................................................ 75 Bảng 3-1: Gán nhãn theo số đông ........................................................................................... 98 Bảng 3-2: Thí dụ cụ thể .......................................................................................................... 98 Bảng 4-1: Cơ sở dữ liệu cho tập phân tách từ....................................................................... 107 Bảng 4-2: Cơ sở dữ liệu cho tập trích rút văn bản ................................................................ 108 Bảng 4-3: Bảng chi tiết tập huấn luyện và tập kiểm thử....................................................... 109 Bảng 4-4: Kết quả đánh giá nội dung của trích rút theo người sử dụng ............................... 111 Bảng 4-5: Kết quả đánh giá nội dung của trích rút theo pp BLEU....................................... 112 Bảng 4-6: Kết quả đánh giá nội dung của trích rút ............................................................... 113 Nguyễn Hồng Thái – Lớp cao học CNTT 2006-2008 5 ĐỒ ÁN TỐT NGHIỆP CAO HỌC ĐỀ TÀI: “TÓM TẮT VĂN BẢN TIẾNG VIỆT THEO CHỦ ĐỀ” MỤC LỤC LỜI CẢM ƠN.......................................................................................................................... 0 LỜI NÓI ĐẦU ......................................................................................................................... 1 DANH MỤC TỪ VIẾT TẮT ................................................................................................. 3 DANH MỤC HÌNH VẼ .......................................................................................................... 4 DANH MỤC BẢNG................................................................................................................ 5 MỤC LỤC ............................................................................................................................... 6 CHƯƠNG 1: CƠ SỞ LÝ THUYẾT ...................................................................................... 9 1.1. NHIỆM VỤ CỦA ĐỒ ÁN ....................................................................................... 9 1.2. KHAI PHÁ DỮ LIỆU VĂN BẢN .......................................................................... 9 1.2.1. Khái niệm khai phá dữ liệu văn bản ............................................................... 11 1.2.2.1. Thuật ngữ - Từ khóa – Khái niệm .............................................................. 12 1.2.2.2. Từ dừng ....................................................................................................... 13 1.2.2.3. Trọng số thuật ngữ ...................................................................................... 14 1.2.3. Các bài toán cơ bản trong xử lý văn bản ........................................................ 14 1.2.3.1. Tìm kiếm văn bản (Text Retrieval)............................................................. 14 1.2.3.2. Phân lớp văn bản (Text categorization, Text classification)....................... 15 1.2.3.3. Phân nhóm văn bản (Text clustering) ......................................................... 15 1.2.3.4. Tóm tắt văn bản (Text summarization)....................................................... 15 1.2.3.5. Dẫn đường văn bản (Text rounting) ........................................................... 16 1.2.4. Các phương pháp biểu diễn văn bản .............................................................. 17 1.2.5. Mô hình độ đo trong xử lý văn bản ................................................................. 20 1.3. XỬ LÝ VĂN BẢN GẮN LIỀN VỚI XỬ LÝ NGÔN NGỮ TỰ NHIÊN ............ 21 1.3.1. Tại sao xử lý văn bản lại gắn liền với xử lý ngôn ngữ tự nhiên? .................. 21 1.3.2. Một số khái niệm, thuật ngữ cơ bản trong ngôn ngữ .................................... 23 1.3.2.1. Thuật ngữ cơ bàn về ngôn ngữ ................................................................... 23 1.3.2.2. Từ loại ......................................................................................................... 24 1.3.2.3. Ngữ loại ...................................................................................................... 24 1.3.2.4. Các thành phần trong câu............................................................................ 24 1.3.3. Các bài toán trong ngôn ngữ tự nhiên ............................................................ 25 1.3.3.1. Bài toán phân tách từ vựng ......................................................................... 25 1.3.3.2. Bài toán gán nhãn từ loại ............................................................................ 26 1.3.3.3. Bài toán phân tích cú pháp .......................................................................... 27 1.3.3.4. Bài toán phân tích ngữ nghĩa ...................................................................... 28 1.3.4. Các đặc trưng của ngôn ngữ tiếng Việt .......................................................... 29 1.3.4.1. Một số đơn vị đặc trưng của tiếng việt ....................................................... 30 1.3.4.2. Các đặc điểm chính tả tiếng Việt ................................................................ 30 1.3.4.3. Từ tiếng Việt ............................................................................................... 31 1.3.4.4. Đánh giá về phương pháp xử lý tiếng Việt ................................................. 32 1.3.4.5. Các chuẩn font tiếng Việt được sử dụng..................................................... 32 Kết luận về xử lý ngôn ngữ tự nhiên ........................................................................... 33 KẾT CHƯƠNG ................................................................................................................. 34 CHƯƠNG 2: CÁC BÀI TOÁN SỬ DỤNG TRONG ĐỀ TÀI .......................................... 35 2.1. BÀI TOÁN TÁCH TỪ TIẾNG VIỆT .................................................................. 35 2.1.1. Những khó khăn trong tách từ tiếng Việt ....................................................... 35 2.1.2. Các phương pháp tách từ hiện nay ................................................................ 35 2.1.3. Các phương pháp tách từ tiếng Việt ............................................................... 40 2.1.4. So sánh các phương pháp tách từ tiếng Việt hiện nay................................... 46 2.2. BÀI TOÁN PHÂN NHÓM VĂN BẢN ................................................................ 47 Nguyễn Hồng Thái – Lớp cao học CNTT 2006-2008 6 ĐỒ ÁN TỐT NGHIỆP CAO HỌC ĐỀ TÀI: “TÓM TẮT VĂN BẢN TIẾNG VIỆT THEO CHỦ ĐỀ” 2.2.1. Khái niệm........................................................................................................... 47 2.2.2. Các giải thuật cơ bản ........................................................................................ 47 2.2.3. Kết luận về bài toán phân nhóm...................................................................... 49 2.3. BÀI TOÁN PHÂN LỚP VĂN BẢN ..................................................................... 49 2.3.1. Các phương pháp phân loại văn bản hiện nay. .............................................. 49 2.3.2. Các phương pháp phân loại văn bản tiếng Anh hiện hành. ......................... 50 2.3.3. Kết luận .............................................................................................................. 54 2.4. BÀI TOÁN TÓM TẮT VĂN BẢN ....................................................................... 55 2.4.1. Giới thiệu bài toán tóm tắt văn bản. ............................................................... 55 2.4.2. Khái niệm về Tóm tắt văn bản? ...................................................................... 57 2.4.3. Mô hình bài toán tóm tắt văn bản ................................................................... 59 2.4.4. Các phương pháp tóm tắt văn bản .................................................................. 61 2.4.5. Các phương pháp đánh giá .............................................................................. 70 2.4.6. Đánh giá ............................................................................................................. 71 2.4.7. Kết luận .............................................................................................................. 75 KẾT CHƯƠNG ................................................................................................................. 76 CHƯƠNG 3: GIẢI PHÁP TÓM TẮT VĂN BẢN THEO CHỦ ĐỀ ................................ 77 3.1. GIỚI THIỆU VỀ BÀI TOÁN TÓM TẮT VĂN BẢN THEO CHỦ ĐỀ .......... 77 3.1.1. Giới thiệu về tính chủ đề trong bài toán ......................................................... 77 3.1.2. Các khái niệm trong tóm tắt văn bản theo chủ đề ......................................... 80 3.1.3. Các đặc trưng trong tóm tắt văn bản theo chủ đề chủ đề ............................. 81 3.1.3.1. Đặc trưng ngôn ngữ của văn bản ................................................................ 81 3.1.3.2. Đặc trưng trong hệ thống tóm tắt tóm tắt văn bản theo chủ đề................... 84 3.1.4. Bài toán tóm tắt văn bản theo chủ đề.............................................................. 85 3.2. MÔ HÌNH TÓM TẮT VĂN BẢN THEO CHỦ ĐỀ .......................................... 85 3.2.1. Mô hình tổng thể ............................................................................................... 85 3.2.2. Phương pháp xây dựng chủ đề ........................................................................ 89 3.2.3. Xây dựng đặc trưng từ các phương pháp học trong các chủ đề................... 90 3.2.3.1. Học không giám sát – Phương pháp tìm khái niệm cho cho chủ đề ........... 91 3.2.3.2. Học có giám sát – Phương pháp tìm chủ đề cho văn bản cần tóm tăt. ....... 92 3.2.4. Các thuật toán sử dụng .................................................................................... 93 3.2.4.1. Thuật toán tách từ ....................................................................................... 93 3.2.4.2. Thuật toán phân nhóm K - Mean ................................................................ 95 3.2.4.3. Thuật toán phân lớp KNN........................................................................... 97 3.2.4.4. Thuật toán tóm tắt, trích rút ........................................................................ 99 KẾT CHƯƠNG ............................................................................................................... 101 CHƯƠNG 4: THIẾT KẾ, CÀI ĐẶT VÀ THỬ NGHIỆP PHẦN MỀM ....................... 103 4.1. XÁC ĐỊNH YÊU CẦU ....................................................................................... 103 4.2. PHÂN TÍCH THIẾT KẾ HỆ THỐNG .............................................................. 103 4.2.1. Thiết kế tổng thể ............................................................................................. 103 4.2.2. Chức năng hệ thống ........................................................................................ 104 4.3. CƠ SỞ DỮ LIỆU THỬ NGHIỆP....................................................................... 107 4.3.1. Tập 7 văn bản đã gán nhãn sẵn ..................................................................... 107 4.3.2. Tập kiểm thử trên vnexpress.net và vietnamnet.vn .................................... 107 4.4. KẾT QUẢ THỬ NGHIỆP .................................................................................. 109 4.4.1. Phương pháp đánh giá kết quả thử nghiệm ................................................... 109 4.4.2. Tóm tắt văn bản tiếng Việt theo chủ đề ........................................................ 110 4.5. ĐÁNH GIÁ THỬ NGHIỆM ............................................................................... 113 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ......................................................................... 114 TÀI LIỆU THAM KHẢO .................................................................................................. 116 Nguyễn Hồng Thái – Lớp cao học CNTT 2006-2008 7 ĐỒ ÁN TỐT NGHIỆP CAO HỌC ĐỀ TÀI: “TÓM TẮT VĂN BẢN TIẾNG VIỆT THEO CHỦ ĐỀ” Nguyễn Hồng Thái – Lớp cao học CNTT 2006-2008 8 ĐỒ ÁN TỐT NGHIỆP CAO HỌC ĐỀ TÀI: “TÓM TẮT VĂN BẢN TIẾNG VIỆT THEO CHỦ ĐỀ” CHƯƠNG 1: CƠ SỞ LÝ THUYẾT 1.1. Nhiệm vụ của đồ án Hiện nay, lĩnh vực khai phá dữ liệu văn bản đối với tiếng Việt vẫn là một điều mới mẻ với người Việt. Gần đây bài toán tóm tắt văn bản phục vụ cho công việc tóm tắt tin tức (tóm tắt trang tin) được nhiều nhà nghiên cứu quan tâm. Dựa trên cơ sở nền tảng vốn có về bài toán tách từ trong lĩnh vực ngôn ngữ tự nhiên, bài toán phân nhóm, phân lớp, tóm tắt văn bản trong lĩnh vực khai phá dữ liệu văn bản, người viết luận văn quyết định thử nghiệm bài toán tóm tắt văn bản tiếng Việt theo chủ đề. Đó là sự kết hợp của bài toán tóm tắt văn bản với bài toán phân nhóm, phân lớp và bài toán tách từ. Đây là một cách tiếp cận với cho bài toán tóm tắt văn bản tiếng Việt. Chính vì lí do đó nên gặp rất nhiều khó khăn như:  Khả năng liên kết giữa bài toán tách từ, phân nhóm, phân lớp với bài toán tóm tắt văn bản.  Tập mẫu cho bài toán tóm tắt văn bản  Khả năng đáp ứng tốc độ cũng như nội dung cho bài toán tóm tắt trang tin. Phần nhiệm vụ tách từ, phân nhóm, phân lớp của bài toán toán tóm tắt văn bản dựa trên kết quả của luận văn tác giả Hoàng Đức Đông [4]. 1.2. Khai phá dữ liệu văn bản Khai phá dữ liệu văn bản (Text Mining) là khái niệm ra đời từ những năm 90 của thế kỷ trước. Đến nay, khai phá dữ liệu văn bản đã có một nền tảng lý thuyết vững chắc. Khai phá dữ liệu văn bản bắt nguồn từ khái niệm rộng hơn là Khai phá dữ liệu (Data Mining), một khái niệm đề cập đến quá trình phát hiện, trích rút ra những thông tin hữu dụng từ một lượng lớn dữ liệu lưu trữ trong các loại cơ sở dữ liệu khác nhau [13]. Để hiểu rõ hơn về khái niệm khai phá dữ liệu văn bản chúng ta tìm hiểu khái niệm về khai phá dữ liệu và phát hiện tri thức trong cơ sở dữ liệu. Khái niệm phát hiện tri thức trong cơ sở dữ liệu (Knowledge Discovery in Databases - KDD) mong muốn tìm ra những thông tin hữu ích ẩn chứa trong cơ sở dữ liệu. Trong đó, quá trình phát hiện tri thức gồm 7 giai đoạn là [13]: Nguyễn Hồng Thái – Lớp cao học CNTT 2006-2008 9 ĐỒ ÁN TỐT NGHIỆP CAO HỌC ĐỀ TÀI: “TÓM TẮT VĂN BẢN TIẾNG VIỆT THEO CHỦ ĐỀ” 1. Làm sạch dữ liệu trước khi thu thập (Data Cleaning) 2. Tích hợp dữ liệu từ các nguồn khác nhau (Data Integration) 3. Chọn lựa dữ liệu ứng viên (Data Selection) 4. Biến đổi dữ liệu thành dạng chuẩn để xử lý (Data Transformation) 5. Khai phá dữ liệu (Data Mining) 6. Đánh giá kết quả (Evaluation) 7. Biểu diễn tri thức (Knowledge Presentation) Quá trình Phát hiện tri thức trong cơ sở dữ liệu được biểu diễn dưới hình vẽ sau [13]: Hình 1-1:Tiến trình khai phá dữ liệu và phát hiện tri thức (KDD) Quá trình Phát hiện tri thức tuân theo các giai đoạn phát triển: Dữ liệu - Thông tin Tri thức. Khi lưu trữ thông tin chúng ta có được dữ liệu. Dữ liệu thông thường không được sử dụng hết theo thời gian trở thành kho dữ liệu lớn. Trong quá trình phân tích, thống kê,… kho dữ liệu lớn này chúng ta thu được Thông tin. Thông tin được tổng hợp, khái quá hóa thành các quy luật, quy tắc chúng ta có được Tri thức. Quá trình Khai phá dữ liệu không chỉ dừng ở mức độ phát hiện mà nó thực hiện việc phân tích dữ liệu, để tìm ra những tri thức chưa từng được biết đến trước đó. Nguyễn Hồng Thái – Lớp cao học CNTT 2006-2008 10 ĐỒ ÁN TỐT NGHIỆP CAO HỌC ĐỀ TÀI: “TÓM TẮT VĂN BẢN TIẾNG VIỆT THEO CHỦ ĐỀ” Hình 1-2: Quan hệ Dữ liệu – Thông tin – Tri thức Các ứng dụng Khai phá dữ liệu có xu hướng phát triển trong tương lai tạo ra các sản phẩn gần gũi và thân thiện hơn với con người. Điều này giúp cho con người thuận tiện khi tiếp xúc, nắm bắt thông tin về sản phẩn, qua đó đẩy mạnh quá trình phát triển thương mại. Oracle, IBM, Yahoo, Microsoft,… đã tích hợp những nghiên cứu Khai phá dữ liệu hết sức nghiêm túc và thành công của mình vào các họ sản phẩm, các nền tảng (platform) dành cho các doanh nghiệp cỡ lớn cũng như các ứng dụng phổ biến cho cá nhân người dùng. Các kỹ thuật của Khai phá dữ liệu cũng được áp dụng rộng rãi trong lĩnh vực Data warehousing (quá trình lưu trữ và quản lý tập trung các cơ sở dữ liệu khác nhau bằng các công cụ quản lý tiên tiến trong việc lưu trữ, truyền tải, phân tích và khai thác dữ liệu với dung lượng lưu trữ cực lớn và tốc độ xử lý cực mạnh) Như vậy trong quá trình Khai phá dữ liệu, khi dữ liệu là văn bản chúng ta có lĩnh vực Khai phá dữ liệu văn bản. Khai phá dữ liệu là một trong bảy giai đoạn của quá trình Phát hiện tri thức trong cơ sở dữ liệu. Là một quá trình phát triển trải qua các giai đọan Dữ liệu – Thông tin – Tri thức. 1.2.1. Khái niệm khai phá dữ liệu văn bản Chúng ta xem xét một số định nghĩa về văn bản. Văn bản: Là các tài liệu được thể hiện dưới dạng phi cấu trúc hoặc bán cấu trúc. Thông thường văn bản có định dạng là các file có đuôi ".txt". Văn bản được phân loại như sau [4]:  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 Nguyễn Hồng Thái – Lớp cao học CNTT 2006-2008 11 ĐỒ ÁN TỐT NGHIỆP CAO HỌC ĐỀ TÀI: “TÓM TẮT VĂN BẢN TIẾNG VIỆT THEO CHỦ ĐỀ” có một cấu trúc định dạng cụ thể nào. Ví dụ, các 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 loại 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, WordPad, DOC… Trong luận văn này người viết luận văn quan tâm đến những văn bản lưu trữ theo mã Unicode, có nội dung của văn bản là ngôn ngữ tiếng Việt. Khai phá dữ liệu văn bản là thực hiện công việc:  Trích ra, lấy ra các thông tin có ích, chưa được biết đến còn tiềm ẩn trong các kho dữ liệu văn bản lớn. Thu thập và phân tích dữ liệu bằng các công cụ tự động hoặc bán tự động từ các nguồn tài liệu đã có khác nhau để có được các tri thức mới, chưa được biết đến trước đó.  Phát hiện ra các mô tả chung của các lớp đối tượng, các từ khoá, các mối liên quan về mặt nội dung, sự phân loại của các đối tượng văn bản, v.v... Như vậy, Khai phá dữ liệu văn bản là công việc trích rút ra thông tin tiềm ẩn bằng các công cụ tự động hoặc bán tự động qua việc tìm các đặc trưng về đối tượng, từ khóa, các mối liên hệ ngữ nghĩa, thống kê, tổng hợp,… 1.2.2. Các khái niệm cơ bản trong xử lý văn bản Sau đây chúng ta tiến hành định nghĩa một số khái niệm thường xuất hiện trong lĩnh vực xử lý văn bản. đó là các khái niệm: Thuật ngữ (Term), Từ khóa (Keyword), khái niệm (Concept), từ dừng (Stopword), trọng số thuật ngữ (Centroid),… Các khái niệm này là thành phần nền tảng, xây dựng lên các mô hình, phương pháp xử lý văn bản. 1.2.2.1. Thuật ngữ - Từ khóa – Khái niệm Thuật ngữ (Term) Là các từ quan trọng xuất hiện trong một văn bản ở dạng nguyên thể, có nghĩa trong từ điển. Ví dụ với văn bản: “Sinh viên Đại Học Bách Khoa quyết tâm học tập, Nguyễn Hồng Thái – Lớp cao học CNTT 2006-2008 12 ĐỒ ÁN TỐT NGHIỆP CAO HỌC ĐỀ TÀI: “TÓM TẮT VĂN BẢN TIẾNG VIỆT THEO CHỦ ĐỀ” nghiên cứu khoa học đạt thành tích cao chào mừng 50 năm thành lập trường”. các từ khóa có thể được tách ra là: “Sinh viên”, “quyết tâm”, “học tập”, “nghiên cứu”, “ khoa học”, “đạt ”, “thành tích”, “cao”, “chào mừng”, “thành lập”, “trường”. Từ khóa (Keyword) Là các thuật ngữ có nghĩa liên quan đến một lĩnh vực nào đó, ví dụ: “tin học”, “toán học”, “văn học” “xã hội học”. Là các từ thường hay được nhắc tới trong lĩnh vực đó, đồng thời các từ khóa này còn có ý nghĩa đặc trưng trong lĩnh vực đó. Số lượng từ khóa thường ít. Khái niệm (Concept) Xét trên góc độ ngôn ngữ khái niệm là các thuật ngữ nhưng nó là sự khái quát hóa, tổng quát hóa của nhiều thuật ngữ khác. Ví dụ khái niệm “máy tính” có thể chứa đựng các thuật ngữ khác như “bàn phím”, “chuột”, “phần cứng”, “phần mềm”, “CPU”, “ổ cứng”, “Internet”, “màn hình”, “số hóa”,… các từ này có một phần liên quan đến khái niệm “máy tính”. Xét về mặt mô hình toán học, chúng ta trừu tượng hóa khái niệm để định lượng hóa đượng khái niệm trong chủ đề. Chúng ta có khái niệm là hàm của các thuật ngữ. Trong đó trọng số của thuật ngữ thể hiện mức quan trọng của thuật ngữ đối với khái niệm. Cùng một số lượng thuật ngữ nhưng trọng số khác nhau chúng ta có các khái niệm khác nhau [12]. Đây là một định nghĩa mang tính chất định lượng thể hiện được công thức độ đo giúp chúng ta có thể tính toán, định lượng được khái niệm. 1.2.2.2. Từ dừng Từ dừng (Stopwords) Trong ngôn ngữ tự nhiên, rất nhiều từ trong câu hầu như không mang ý nghĩa về mặt nội dung trong tổng thể văn bản. Các từ này chỉ mang ý nghĩa về mặt cấu trúc câu. Về mặt Ngôn ngữ học đó thường là các loại từ như: 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 mang một lượng thông tin rất nhỏ về nội dung hay chủ đề của văn bản. Việc loại bỏ các từ như vậy cũng đồng nghĩa với việc trích rút những từ quan trọng trong văn bản (thuật ngữ) đồng thời nó còn làm giảm số chiều trong mô hình biểu diễn văn bản, những từ đó được gọi là từ dừng (stopwords). Nguyễn Hồng Thái – Lớp cao học CNTT 2006-2008 13 ĐỒ ÁN TỐT NGHIỆP CAO HỌC ĐỀ TÀI: “TÓM TẮT VĂN BẢN TIẾNG VIỆT THEO CHỦ ĐỀ” Từ dừng là các từ mang ít ý nghĩa trong việc xử lý văn bản vì nó thường xuất hiện trong hầu hết các văn bản. Một vài ví dụ về từ dừng: Thì, là, mà, rằng, Có thể, nếu, vì vậy, sau khi, thì, một số, với lại, quả thật, hầu như ... 1.2.2.3. Trọng số thuật ngữ Là độ quan trọng hay hàm lượng thông tin mà thuật ngữ đó mang lại cho văn bản. Trọng số của thuật ngữ là đại lượng dùng để đo sự khác biệt giữa văn bản chứa cùng thuật ngữ đó. Đại lượng này thường được xác định bằng tay hoặc đánh giá bằng số lần xuất hiện của thuật ngữ trong văn bản và số lần xuất hiện của thuật ngữ đó trong các văn bản khác. Trọng số của thuật ngữ tỉ lệ thuận với độ quan trọng của thuật ngữ với văn bản. Khi số lần xuất hiện của thuật ngữ trong văn bản càng nhiều thì thông tin mà nó mang lại càng lớn. Khi số lần xuất hiện của nó trong các văn bản khác càng ít thì thông tin mà nó mang lại càng ít. 1.2.3. Các bài toán cơ bản trong xử lý văn bản Các bài toán trong xử lý văn bản bao gồm: bài toán tìm kiếm văn bản (Text Retrieval), bài toán phân lớp văn bản (Text Categorization), bài toán phân nhóm văn bản (Text Clustering), bài toán tóm tắt văn bản (Text Summarization), bài toán định tuyến văn bản (Text Rounting). 1.2.3.1. Tìm kiếm văn bản (Text Retrieval) Tìm kiếm văn bản (hay còn gọi là truy hồi văn bản): Là quá trình tìm các văn bản trong một kho lưu trữ theo các yêu cầu của người dùng. Ở đây, các yêu cầu là các truy vấn và thường được biểu diễn dưới dạng thuật ngữ hay biểu thức logic giữa các thuật ngữ. Ví dụ: truy vấn “Text Mining” AND (“Categorization” OR “Summurization”). Ứng với truy vấn này search engine của hệ thống sẽ tìm tất cả các tài liệu về “Text Mining” có liên quan đến “Categorization” hoặc “Summarization”. Trên thực tế thì hầu hết các hệ thống chỉ được thiết kế để hiểu các truy vấn tương tự như “Text Mining” OR “Categorization” OR “Summarization”. Với câu truy vấn này hệ thống sẽ tìm kiếm các tài liệu theo mức phù hợp với cả ba thuật ngữ “Text Mining”, “Categorization”, và “Summarization”. Nguyễn Hồng Thái – Lớp cao học CNTT 2006-2008 14 ĐỒ ÁN TỐT NGHIỆP CAO HỌC ĐỀ TÀI: “TÓM TẮT VĂN BẢN TIẾNG VIỆT THEO CHỦ ĐỀ” Kết quả đầu ra của một phép truy vấn là danh sách các tài liệu được sắp xếp giảm dần theo mức độ phù hợp với câu truy vấn đầu vào. 1.2.3.2. Phân lớp văn bản (Text categorization, Text classification) Phân lớp văn bản được định nghĩa: Là quá trình gán các văn bản vào một hay nhiều lớp văn bản đã được xác định trước dựa trên nội dung của văn bản đó [4]. Người ta có thể phân lớp các văn bản một cách thủ công, tức là đọc từng văn bản và gán nó vào một lớp nào đó, cách này sẽ tốn rất nhiều thời gian và công sức khi số lượng văn bản lớn nên không khả thi. Do vậy cần phải có các phương pháp phân lớp tự động. Để phân lớp tự động người ta sử dụng các phương pháp học máy trong trí tuệ nhân tạo. Khi phân lớp, văn bản được gán vào một lớp theo một giá trị ngưỡng nào đó. Ngưỡng đặt ra tùy thuộc vào thuật toán và yêu cầu người dùng. 1.2.3.3. Phân nhóm văn bản (Text clustering) Phân nhóm văn bản (Hay còn gọi là lập cụm văn bản): Là việc tự động sinh ra các lớp văn bản dựa vào sự tương tự về nội dung của các văn bản. Số lượng các nhóm văn bản ở đây là chưa biết trước, chẳng hạn số nhóm có thể là 2,3 5,... Người dùng có thể chỉ ra số lượng các nhóm cần phân nhóm hoặc hệ thống sẽ tự phân nhóm. Đối với bài toán này, không bao giờ có một kết quả thỏa mãn hoàn toàn theo ý người dùng. Một lý do đơn giản để giải thích là máy không được học trước. Chúng ta phải thừa nhận rằng ngay cả con người cũng giải quyết bài toán này không giống nhau. Ví dụ, lập nhóm các từ “cầu thủ”, “cha cố”, “nến”, “trái bóng”; một người sẽ lập thành 2 nhóm là: con người (“cầu thủ” , “cha cố”) và sự vật (“nến”, “trái bóng”), trong khi đó người khác lại phân chúng thành 2 nhóm khác: nhà thờ (“cha cố”, “nến”) và bóng đá (“cầu thủ”, “trái bóng”). Do đó, việc đòi hỏi hệ thống tự động lập nhóm làm việc đúng tuyệt đối là điều không tưởng. 1.2.3.4. Tóm tắt văn bản (Text summarization) Tóm tắt văn bản là: bài toán tìm ra thể hiện nội dung của một văn bản thông qua một vài đoạn văn. Ứng dụng điển hình của bài toán này là trong tìm kiếm văn bản. Các kho lưu trữ bao gồm rất nhiều tài liệu và kích thước mỗi tài liệu có thể lên đến vài trăm trang. Nguyễn Hồng Thái – Lớp cao học CNTT 2006-2008 15 ĐỒ ÁN TỐT NGHIỆP CAO HỌC ĐỀ TÀI: “TÓM TẮT VĂN BẢN TIẾNG VIỆT THEO CHỦ ĐỀ” Giả sử khi bạn đọc muốn tìm một tài liệu về “Text Mining” và nhờ hệ thống tìm kiếm văn bản tìm giúp, hệ thống tìm kiếm sẽ đưa ra một danh sách các tài liệu với nội dung tương đối phù hợp với “Text Mining”. Nhưng để biết thực sự tài liệu đó có phù hợp với mình hay không, bạn đọc đành phải đọc toàn bộ hoặc đọc một phần trong tài liệu. Hệ thống tóm tắt văn bản sẽ làm cho việc tìm kiếm giảm nhẹ đi rất nhiều bằng cách tự động tóm lược nội dung của toàn bộ văn bản bởi một vài đoạn văn bản. Sau khi đọc qua đoạn tóm lược này, bạn đọc có thể biết được đây có phải là tài liệu chứa thông tin mà họ đang cần hay không. Người viết luận văn sẽ trình bầy kỹ hơn bài toán tóm tắt văn bản ở phần 1.3.3 trong chương này của đồ án. 1.2.3.5. Dẫn đường văn bản (Text rounting) Dẫn đường văn bản là sự tổ hợp giữa bài toán tìm kiếm văn bản và phân lớp, nhóm văn bản. Giống như phân lớp, nhóm văn bản, bài toán dẫn đường cũng đưa các văn bản về các lớp, nhóm khác nhau và việc xử lý này yêu cầu trong thời gian thực. Tuy nhiên, nó cũng giống như bài toán tìm kiếm, mỗi lớp, nhóm văn bản được gán với các thông tin cần thiết của một hay nhiều nhóm người dùng. Mỗi người dùng có thể thay đổi thêm bớt các yêu cầu của mình. Quá trình phản hồi có thể được sử dụng để nâng cao chất lượng tìm kiếm văn bản. Một ứng dụng điểu hình của bài toán dẫn đường văn bản là trong các trang tin điện tử. Khi đọc một tin mới, hệ thống sẽ tìm cách đưa ra danh sách các tin khác có liên quan đến đoạn tin đang đọc. Ứng dụng của bài toán này được sử dụng hết sức rộng rãi trên báo điện tử. Khi đọc một bài báo, phía dưới mỗi trang web sẽ có các liên kết đến các bài báo khác có liên quan về mặt nội dung (hình 1.3.). Bạn đọc có thể theo các thông tin dẫn đường này để theo dõi toàn bộ diễn biến của sự kiện. Nguyễn Hồng Thái – Lớp cao học CNTT 2006-2008 16 ĐỒ ÁN TỐT NGHIỆP CAO HỌC ĐỀ TÀI: “TÓM TẮT VĂN BẢN TIẾNG VIỆT THEO CHỦ ĐỀ” Hình 1-3: Chức năng dẫn đường văn bản trong VNExpress 1.2.4. Các phương pháp biểu diễn văn bản Công việc biểu diễn văn bản là tiền đề giúp chúng xử lý được văn bản. Có rất nhiều phương pháp biểu diễn văn bản, song trong phạm vi đồ án người viết luận văn chỉ đi sâu vào phương pháp biểu diễn văn bản theo mô hình không gian vector. Cụ thể hơn là mô hình tần suất. Đây là phương pháp phổ biến được sử dụng trên Thế Giới Mô hình không gian vector coi mỗi văn bản được biểu diễn như một vector, thành phần của vector là các thuật ngữ riêng biệt trong văn bản gốc và được gán một giá trị trọng số xác định bởi hàm f. Có nhiều phương pháp để xác định trọng số của thuật ngữ trong văn bản như phương pháp dựa trên tần số xuất hiện của thuật ngữ, phương pháp dựa trên nghịch đảo tần số văn bản. Hình 1.4 là biểu diễn các vector văn bản trong không gian chỉ có 3 thuật ngữ. Nguyễn Hồng Thái – Lớp cao học CNTT 2006-2008 17 ĐỒ ÁN TỐT NGHIỆP CAO HỌC ĐỀ TÀI: “TÓM TẮT VĂN BẢN TIẾNG VIỆT THEO CHỦ ĐỀ” văn bản 1 Thuật ngữ 2 văn bản 2 văn bản 3 Thuật ngữ 1 Thuật ngữ 3 Hình 1-4: Các vector văn bản trong không gian có 3 thuật ngữ Các thuật ngữ được sử dụng trong mô hình vector có thể là một từ hoặc một cụm từ và không phải là những từ dừng. Việc tách các thuật ngữ trong văn bản là một bài toán khó và phụ thuộc vào đặc trưng của từng ngôn ngữ. Ta xem xét ví dụ sau: có 2 văn bản Văn bản 1: Máy tính đã trở thành một công cụ không thể thiếu trong cuộc sống. Văn bản 2: Máy tính xuất hiện trong mọi lĩnh vực hoạt động của cuộc sống. Biểu diễn của 2 văn bản với trọng số của các thuật ngữ là tần số xuất hiện của chúng được cho trong bảng 1. STT Thuật ngữ Văn bản 1 Văn bản 2 1 Máy tính 1 1 2 trở thành 1 0 3 công cụ 1 0 5 Cuộc sống 1 1 6 Xuất hiện 0 1 7 lĩnh vực 0 1 8 không thể thiếu 1 0 9 Hoạt động 0 1 Bảng 1-1: Ví dụ về biểu diễn văn bản theo mô hình vector tần suất Trong mô hình tần suất, ma trận W = {wij} được xác định dựa trên tần số xuất hiện của thuật ngữ ti trong văn bản dj hoặc tần số xuất hiện của thuật ngữ ti trong toàn bộ cơ sở dữ liệu. Tùy theo các phương pháp khác nhau mà trọng số này được tính khác nhau. Chúng ta đi vào một số phương pháp cụ thể. Nguyễn Hồng Thái – Lớp cao học CNTT 2006-2008 18