Tài liệu Tìm hiểu về phân loại văn bản và xây dựng chương trình ứng dụng

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC KỸ THUẬT CÔNG NGHỆ KHOA CÔNG NGHỆ THÔNG TIN H BỘ MÔN CÔNG NGHỆ PHẦN MỀM C LUẬN VĂN TỐT NGHIỆP U TE TÌM HIỂU VỀ PHÂN LOẠI VĂN BẢN VÀ XÂY DỰNG CHƯƠNG TRÌNH ỨNG DỤNG H Sinh viên thực hiện: 1. 2. Họ tên: PHAN THANH BÌNH MSSV: 10102019 Họ tên: LÊ BẠCH VŨ MSSV: 10102218 TP. HỒ CHÍ MINH NĂM HỌC: 2005-2006 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC KỸ THUẬT CÔNG NGHỆ KHOA CÔNG NGHỆ THÔNG TIN H BỘ MÔN CÔNG NGHỆ PHẦN MỀM C LUẬN VĂN TỐT NGHIỆP U TE TÌM HIỂU VỀ PHÂN LOẠI VĂN BẢN VÀ XÂY DỰNG CHƯƠNG TRÌNH ỨNG DỤNG H Sinh viên thực hiện: 1. 2. Họ tên: PHAN THANH BÌNH MSSV: 10102019 Họ tên: LÊ BẠCH VŨ MSSV: 10102218 Giảng viên hướng dẫn: Ths. NGUYỄN CHÁNH THÀNH TP.HCM, THÁNG 1 NĂM 2006 Luận văn tốt nghiệp GVHD: Th.s Nguyễn Chánh Thành LỜI NÓI ĐẦU Ngày nay, với sự phát triển của công nghệ thông tin, thì số lượng thông tin cũng bùng nổ nhanh chóng. Các thông tin tồn tại dưới nhiều hình thức khác nhau như: các trang web, thư điện tử, cơ sở dữ liệu… Do đó công việc tìm kiếm thông tin theo nội dung nào đó cũng trở nên khó khăn. Từ thực tiễn này nhu cầu phân loại các thông tin đã xuất hiện từ rất sớm. Nhưng nếu dùng con người để phân loại các thông tin thì sẽ mất rất nhiều công sức và tiền bạc. Cho H U TE C gánh nặng cho con người. H nên người ta đã tìm ra nhiều phương pháp phân loại văn bản tự động giúp giảm SVTH: Phan Thanh Bình & Lê Bạch Vũ Trang 1 Luận văn tốt nghiệp GVHD: Th.s Nguyễn Chánh Thành TÓM TẮT NỘI DUNG Trong luận văn này chúng tôi sẽ trình bày về các phương pháp phân loại văn bản và hiện thực giải thuật K-Nearest Neightbour (K-NN). Đây là giải thuật không quá phức tạp nhưng có độ chính xác khá cao. Các phần trong luận văn sẽ được trình bày như sau: Chương 1: Chương này sẽ trình bày về nhu cầu thực tiễn của việc phân loại văn bản và các ứng dụng thực tế của các ph ương pháp phân loại văn bản tự động trong thời đại ngày nay. H động. Chương này sẽ cho ta thấy sự cần thiết của việc phân loại văn bản tự C Chương 2: Chương này trình bày về các cơ sở lý thuyết liên quan đến quá trình TE phân loại văn bản tự động. Cung cấp các kiến thức rất quan trọng dùng để cài đặt và kiểm tra hiệu quả của các phương pháp phân loại tự động. Chương 3: Chương này trình bày tổng quan một số ph ương pháp phân loại văn bản tự động như: Giải thuật Rocchio, Giải thuật K-Nearest Neighbour, Naïve U Bayes, Giải thuật cây quyết định, Giải thuật mạng neuron, Giải thuật Support H Vector Machine. Chương 4: Chương này sẽ trình bày bảng thiết kế và cài đặt chương trình phân loại văn bản tự động theo phương pháp K-Nearest Neighbour. Sau đó chúng tôi sẽ trình bày các kết quả đạt được sau khi chạy thử nghiệm chương trình như độ chính xác, tốc độ của chương trình. Để minh họa cho việc ứng dụng phương pháp phân loại văn bản tự động, chúng tôi có cài đặt các module crawler dùng để rút trích văn bản trên mạng máy tính, module index dùng để lập chỉ mục các văn bản đã phân loại và một trang web tìm kiếm. Chương 5: Chương này sẽ trình bày các thảo luận và rút ra các kết luận và kết quả đối chiếu với mục tiêu đề ra. Cuối cùng là định hướng phát triển của đề tài. SVTH: Phan Thanh Bình & Lê Bạch Vũ Trang 2 Luận văn tốt nghiệp GVHD: Th.s Nguyễn Chánh Thành LỜI CẢM ƠN Lời cám ơn đầu tiên chúng tôi xin gởi đến Thạc sĩ Nguyễn Chánh Thành. Thầy đã tận tình hướng dẫn và định hướng cho chúng tôi từ đồ án cơ sở, đồ án chuyên ngành và nay là luận văn tốt nghiệp. Chúng tôi xin chúc thầy luôn vui vẻ hạnh phúc và luôn nhiệt tình chỉ bảo cho các sinh viên. Tiếp theo chúng tôi xin cám ơn các anh chị trong công ty Thương mại cổ phần HPT chi nhánh thương mại TP-HCM đã nhiệt tình giúp đỡ và tạo điều kiện cho chúng tôi tìm H kiếm văn bản và dữ liệu kiểm chứng chương trình. Cuối cùng xin cám ơn đến H U TE quá trình thực hiện đề tài này. C các bạn thân học cùng khóa 01- ĐTH đã quan tâm động viên c húng tôi trong SVTH: Phan Thanh Bình & Lê Bạch Vũ Trang 3 Luận văn tốt nghiệp GVHD: Th.s Nguyễn Chánh Thành MỤC LỤC LỜI NÓI ĐẦU ............................................................................................................... 1 TÓM TẮT NỘI DUNG ................................................................................................. 2 LỜI CẢM ƠN ................................................................................................................ 3 MỤC LỤC ..................................................................................................................... 4 DANH MỤC HÌNH ....................................................................................................... 9 DANH MỤC BẢNG.................................................................................................... 11 Chương 1...................................................................................................................... 12 PHÁT BIỂU VẤN ĐỀ ................................................................................................. 12 H 1.1. Giới thiệu ................................................................................................ 12 1.1.1. Động cơ thúc đẩy việc phân loại văn bản tự động .......................... 13 C 1.1.2. Một số ứng dụng của việc phân loại văn bản theo chủ đề .............. 14 TE 1.2. Nội dung đề tài ....................................................................................... 15 1.3. Ứng dụng mở rộng - Lập chỉ mục và tìm kiếm của Lucene .................. 16 1.3.1. Giới thiệu Lucene ............................................................................ 16 U 1.3.2. Cơ sở nền tảng của Lucene.............................................................. 18 1.3.3. Mục đích, chức năng, công dụng .................................................... 18 H 1.3.4. Tạo chỉ mục và tìm kiếm ................................................................. 19 Chương 2...................................................................................................................... 20 CƠ SỞ LÝ THUYẾT PHẦN LOẠI VĂN BẢN ......................................................... 20 2.1. Biểu diễn văn bản ................................................................................... 20 2.1.1. Phương pháp Boolean ..................................................................... 23 2.1.2. Phương pháp tần suất từ (work frequency) ..................................... 24 2.1.3. Phương pháp tf-idf (frequency x inverse document frequency) ..... 24 2.1.4. Phương pháp tfc (Term Frequency Component) ............................ 25 2.1.5. Phương pháp ltc (Log Term Component) ....................................... 25 2.1.6. Phương pháp Entropy ...................................................................... 26 SVTH: Phan Thanh Bình & Lê Bạch Vũ Trang 4 Luận văn tốt nghiệp GVHD: Th.s Nguyễn Chánh Thành 2.2. Rút gọn danh sách từ .............................................................................. 26 2.2.1. Phương pháp ngưỡng tần xuất của văn bản. ................................... 27 2.2.2. Phương pháp độ lợi thông tin .......................................................... 27 2.2.3. Phương pháp thông tin tương hỗ ..................................................... 28 2.2.4. Phương pháp độ mạnh của từ .......................................................... 28 2 2.2.5. Phương pháp thống kê χ ............................................................... 29 2.3. Tập văn bản dùng để phân loại ............................................................... 30 2.3.1. Giới thiệu ......................................................................................... 30 2.3.2. Tập Reuters ...................................................................................... 30 H 2.3.3. Tập 20-newsgroup ........................................................................... 33 C 2.4. Đánh giá độ chính của việc phân loại văn bản ....................................... 34 2.4.1. Thông số precision. ......................................................................... 35 TE 2.4.2. Thông số recall ................................................................................ 35 2.4.3. Thông số f (f-score) ......................................................................... 35 2.4.4. Thông số accuracy ........................................................................... 36 U 2.4.5. Thông số error ................................................................................. 36 Chương 3...................................................................................................................... 37 H CÁC GIẢI THUẬT PHÂN LOẠI VĂN BẢN ............................................................ 37 3.1. Giải thuật Rocchio .................................................................................. 37 3.1.1. Giới thiệu ......................................................................................... 37 3.1.2. Giai đoạn huấn luyện ....................................................................... 38 3.1.3. Giai đoạn phân loại.......................................................................... 39 3.1.4. Đánh giá giải thuật .......................................................................... 40 3.2. Giải thuật K-Nearest Neighbour............................................................ 41 3.2.1. Giới thiệu ......................................................................................... 41 3.2.2. Giai đoạn huấn luyện ....................................................................... 42 3.2.3. Giai đoạn phân loại.......................................................................... 43 SVTH: Phan Thanh Bình & Lê Bạch Vũ Trang 5 Luận văn tốt nghiệp GVHD: Th.s Nguyễn Chánh Thành 3.2.4. Đánh giá giải thuật .......................................................................... 44 3.3. Giải thuật Naïve Bayes ........................................................................... 45 3.3.1. Giới thiệu ......................................................................................... 45 3.3.2. Giai đoạn huấn luyện ....................................................................... 46 3.3.3 Giai đoạn phân loại........................................................................... 46 3.3.4. Đánh giá giải thuật .......................................................................... 47 3.4. Giải thuật cây quyết định....................................................................... 47 3.4.1. Cây quyết định ................................................................................. 47 3.4.2. Entropy và độ lợi thông tin. ............................................................ 49 H 3.4.3. Cắt nhánh cây quyết định. ............................................................... 49 3.4.4. Nhận xét.......................................................................................... 50 C 3.5. Giải thuật mạng Neuron (Neural Network) ............................................ 50 TE 3.5.1. Giải thuật ......................................................................................... 50 3.5.2. Đánh giá giải thuật .......................................................................... 53 3.6. Giải thuật Support Vector Machine........................................................ 54 U 3.6.1. Các mặt phân cách (Hyperplanes) ................................................... 54 3.6.2. Giải thuật Support Vector Machine................................................. 55 H 3.6.3. Nhân xét........................................................................................... 56 3.7. Chọn giải thuật ....................................................................................... 57 Chương 4...................................................................................................................... 58 THIẾT KẾ VÀ HIỆN THỰC CHƯƠNG TRÌNH PHÂN LOẠI VĂN BẢN ............ 58 4.1. Quá trình xây dựng giải thuật K-Nearest Neighbour ............................. 58 4.1.1. Xây dựng từ điển (danh sách từ khóa) ............................................ 58 4.1.2. Giai đoạn huấn luyện ....................................................................... 58 4.1.3. Giai đoạn phân loại.......................................................................... 59 4.2. Sơ đồ usecase.......................................................................................... 60 4.3. Sơ đồ tuần tự của vài nghiệp vụ chính ................................................... 61 SVTH: Phan Thanh Bình & Lê Bạch Vũ Trang 6 Luận văn tốt nghiệp GVHD: Th.s Nguyễn Chánh Thành 4.3.1. Huấn luyện văn bản ......................................................................... 61 4.3.2. Phân loại văn bản ............................................................................ 62 4.3.3. Đánh giá kết quả phân loại .............................................................. 63 4.3.4. Trích rút dữ liệu trên mạng .............................................................. 65 4.3.5. Lập chỉ mục ..................................................................................... 66 4.3.6. Tìm kiếm ......................................................................................... 67 4.4. Sơ đồ lớp................................................................................................. 68 4.4.1. Pakage textcategory.reader .............................................................. 68 4.4.2. Package textcategory.analysis ......................................................... 69 H 4.4.3. Package textcategory.training ......................................................... 70 C 4.4.4. Package textcategory.category ........................................................ 72 4.4.5. Package store. .................................................................................. 72 TE 4.4.6. Package crawler ............................................................................... 73 4.4.7. Package index .................................................................................. 74 4.4.8. Package util ..................................................................................... 74 U 4.5. Thiết kế cơ sở dữ liệu ............................................................................. 75 4.6. Thiết kế giao diện ................................................................................... 76 H 4.6.1. Màn hình chính của chương trình ................................................... 76 4.6.2. Màn hình tạo loại văn bản ............................................................... 76 4.6.3. Màn hình huấn luyện chương trình ................................................. 77 4.6.4. Màn hình phân loại dữ liệu .............................................................. 77 4.6.5. Màn hình kết quả phân loại ............................................................. 78 4.6.6. Màn hình tạo chỉ mục (reverted index) ........................................... 78 4.6.7. Màn hình trích rút dữ liệu trên mạng .............................................. 79 4.6.8. Trang chủ tìm kiếm theo chủ đề ..................................................... 79 4.6.9. Trang tìm kiếm theo chủ đề ............................................................. 80 4.7. Kết quả đạt được..................................................................................... 80 SVTH: Phan Thanh Bình & Lê Bạch Vũ Trang 7 Luận văn tốt nghiệp GVHD: Th.s Nguyễn Chánh Thành Chương 5...................................................................................................................... 83 ĐÁNH GIÁ VÀ HƯỚNG PHÁT TRIỂN ................................................................... 83 5.1. Đánh giá.................................................................................................. 83 5.1.1. Kết quả đạt được.............................................................................. 83 5.1.2. Các hạn chế của đề tài ..................................................................... 84 5.2. Hướng phát triển của đề tài .................................................................... 84 PHỤ LỤC..................................................................................................................... 86 1. Từ điển giải thích các thuật ngữ ................................................................ 86 2. Các mã nguồn mở được sử dụng trong luận văn ....................................... 87 H U TE C H 3. Tài liệu tham khảo ..................................................................................... 87 SVTH: Phan Thanh Bình & Lê Bạch Vũ Trang 8 Luận văn tốt nghiệp GVHD: Th.s Nguyễn Chánh Thành DANH MỤC HÌNH Hình 1. Mô hình kiến trúc của Lucene ........................................................................ 17 Hình 2. Mô hình không gian vector 3 chiều. ............................................................... 22 Hình 3. Ảnh minh họa cho giải thuật phân loại văn bản Rocchio ............................... 39 Hình 4. Mình họa xác định vector Q giống D1 hay D2 theo giải thuật KNN ............. 44 Hình 5. Cây quyết định cho chủ đề “earning” ............................................................. 48 Hình 6. Biểu đồ thể hiện hiệu quả của việc cắt nhánh ................................................. 50 Hình 7. Mô hình một Perceptron ................................................................................. 51 Hình 8. Mô hình mạng neuron ..................................................................................... 53 H Hình 9. Mô hình lan truyền dữ liệu .............................................................................. 53 Hình 10. Đường phân cách .......................................................................................... 54 C Hình 11. Các trường hợp của đường phân cách........................................................... 55 Hình 12. Biểu diễn nhiều chủ đề khác nhau trong phương pháp SVM ....................... 55 TE Hình 13. Mô tả phương pháp SVM ............................................................................. 56 Hình 14. Ví dụ cần phân loại văn bản x với K = 3 ...................................................... 59 Hình 15. Sơ đồ use case mô tả các nghiệp vụ chủ ứng dụng ....................................... 60 U Hình 16. Sơ đồ tuần tự của quá trình huấn luyện chương trình ................................... 61 Hình 17. Sơ đồ tuần tự của quá trình phân loại văn bản .............................................. 62 H Hình 18. Sơ đồ tuần tự của quá trình đánh giá kết quả phân loại ................................ 64 Hình 19. Sơ đồ tuần tự của quá trình đánh giá kết quả phân loại ................................ 65 Hình 20. Sơ đồ tuần tự của quá trình lập chỉ mục ....................................................... 66 Hình 21. Sơ đồ tuần tự của quá trình tìm kiếm ............................................................ 67 Hình 22. Package reader .............................................................................................. 68 Hình 23. Pakage analysis ............................................................................................. 69 Hình 24. Pakage training.............................................................................................. 70 Hình 25. Pakage category ............................................................................................ 72 Hình 26. Package store ................................................................................................ 72 Hình 27. Package crawler ............................................................................................ 73 SVTH: Phan Thanh Bình & Lê Bạch Vũ Trang 9 Luận văn tốt nghiệp GVHD: Th.s Nguyễn Chánh Thành Hình 28. Package index ............................................................................................... 74 Hình 29. Package util ................................................................................................... 75 H U TE C H Hình 30. Cơ sở dữ liệu ................................................................................................. 75 SVTH: Phan Thanh Bình & Lê Bạch Vũ Trang 10 Luận văn tốt nghiệp GVHD: Th.s Nguyễn Chánh Thành DANH MỤC BẢNG Bảng 1. Ví dụ một từ điển ............................................................................................ 21 Bảng 2. Các version của tuyển tập Reuter. ................................................................. 31 Bảng 3 . Thống kê một số chủ đề trong tập Reuters .................................................... 33 Bảng 4. Thống kê một số chủ đề trong tập 20-newsgroup .......................................... 34 Bảng 5. Các trường hợp phân loại ............................................................................... 35 Bảng 6. Tóm tắt hiệu quả của các giải thuật ( bởi Yang & Liu) .................................. 57 H U TE C H Bảng 7. Kết quả đạt được của chương trình demo....................................................... 82 SVTH: Phan Thanh Bình & Lê Bạch Vũ Trang 11 Luận văn tốt nghiệp GVHD: Th.s Nguyễn Chánh Thành Chương 1 PHÁT BIỂU VẤN ĐỀ 1.1. Giới thiệu Luận văn này trình bày về vấn đề phân loại văn bản tự động theo các chủ đề cho trước. Đề tài này đã được nghiên cứu từ đầu thập niên 1960. Kể từ đó, đề tài này đã liên tục được nghiên cứu và phát triển thông qua các thư viện điện tử, báo chí và các văn bản trực tuyến. Khái niệm phân loại văn bản được định nghĩa như sau: “Phân loại văn bản (Text Categorization) là việc quyết định xem một mẫu văn H bản thuộc về một chủ đề nào đó trong tập chủ đề cho trước. Đây là chức năng C xử lý văn bản tổng quát có ích cho việc lập chỉ mục và truy xuất thông tin sau này, là một công đoạn trong hệ thống xử lý ngôn ngữ tự nhiên để phân tích nội TE dung và trong nhiều vai trò khác.” Xử lý ngôn ngữ tự nhiên (NLP: Natural Language Processing) làĩnh l vực thuộc ngành trí tuệ nhân tạo và ngôn ngữ học. Nó có những phương pháp giúp U cho việc xử lý, thao tác và hiểu ngôn ngữ tự nhiên một cách dể dàng và làm cho các câu lệnh trong máy tính hiểu được các ngôn ngữ của nhân loại. Do đó, H nó thu hút rất nhiều nhà khoa học nghiên cứu và đã đạt được những thành tựu đáng kể. Sau đây là một vài thành tựu có thể kể đến như:  Đọc văn bản (Text to Speech)  Nhân dạng tiếng nói (Speech Recognition)  Sinh ra ngôn ngữ tự nhiên (Natural Language Generation)  Máy dịch thuật (Machine Translation)  Trả lời câu hỏi (Question Answering)  Tìm kiếm thông tin (Information Retrieval)  Trích rút thông tin (Information Extraction)  Kiểm chứng văn bản (Text-Proofing) SVTH: Phan Thanh Bình & Lê Bạch Vũ Trang 12 Luận văn tốt nghiệp GVHD: Th.s Nguyễn Chánh Thành  Tóm tắc tự động (Automatic Summarization)  Mơ hồ về ngữ nghĩa (Syntactic ambiguity)  Xử lý ngôn ngữ bằng thống kê (Statistical Natural Language Processing) Trong luận văn này chúng tôi ình tr bày là phân lo ại văn bản tự động - một hướng nghiên cứu trong lĩnh vực xử lý ngôn ngữ tự nhiên bằng thống kê. Mục tiêu của việc phân loại văn bản tự động là phải viết một chương trình có khả năng phân loại chính xác một văn bản bất kỳ (bằng tiếng Anh). 1.1.1. Động cơ thúc đẩy việc phân loại văn bản tự động Phân loại văn bản tự động đem lại rất nhiều lợi ích trong đời sống hiện nay. H Thật vậy, sự phát triển vượt bậc của Internet dẫn đến sự bùng nổ của các văn bản trực tuyến, cho nên cần phải phân loại các văn bản nhận được vào các chủ C đề khác nhau. Nếu việc phân loại văn bản cổ điển được thực hiện thủ công, nghĩa là thông TE qua con người (các chuyên gia của từng lĩnh vực), thì số lượng chuyên gia tham gia vào việc phân loại là rất lớn và thời gian phân loại cũng lớn hơn, điều này rất tốn kém và gây nhàm chán cho các chuyên gia này. Tuy nhiên việc U phân loại thủ công cũng không tránh khỏi những ý kiến chủ quan của những chuyên gia, vì vậy độ chính xác cũng không cao. H Khi đó các công cụ ph ân loại văn bản tự động rất hữu ích cho người đọc trong việc tổ chức dữ liệu. Do đó việc phân loại tiến hành bằng máy có ưu điểm là hiệu suất cao, có thể hoạt động bất kỳ lúc nào.Tuy nhiên vấn đề ta cần quan tâm là độ chính xác của hệ thống. Thật vậy, nếu thực hiện theo cách tự động sẽ tận dụng được khả năng quét các văn bản và khả năng xử lý nhanh của máy tính. Do đó hiệu suất sẽ lớn hơn và độ chính xác sẽ cao hơn nếu như máy tính được huấn luyện tốt. SVTH: Phan Thanh Bình & Lê Bạch Vũ Trang 13 Luận văn tốt nghiệp GVHD: Th.s Nguyễn Chánh Thành 1.1.2. Một số ứng dụng của việc phân loại văn bản theo chủ đề a. Phân loại văn bản theo ngôn ngữ Ở một số trung tâm kiểm duyệt văn bản, số lượng văn bản nhận được rất lớn. Các văn bản này có thể được biểu diễn từ các ngôn ngữ khác nhau. Ta có thể dùng các hệ thống phân loại văn bản theo ngôn ngữ để gán các văn bản này vào từng ngôn ngữ cụ thể. Các chuyên gia ngôn ngữ sẽ kiểm duyệt các văn bản này theo ngôn ngữ chuyên môn của họ. b. Phân loại thông tin theo chủ đề Cũng giống như việc phân loại văn bản theo ngôn ngữ, việc phân loại thông tin H theo chủ đề sẽ phân c hia các thông tin nhận được vào các chủ đề khác nhau. Nếu việc phân loại này được thực hiện thủ công, nghĩa là thông qua con người, C thì số lượng chuyên gia tham gia vào việc phân loại là rất lớn và thời gian phân loại cũng lớn hơn. Việc phân loại thủ công cũng không tránh khỏi ý kiến chủ TE quan của những chuyên gia, vì vậy độ chính xác cũng không cao. Trong khi đó, nếu thực hiện theo cách tự động sẽ tận dụng được khả năng quét các văn bản và khả năng xử lý nhanh của máy tính. Do đó hiệu suất sẽ lớn hơn và độ chính xác U sẽ cao hơn nếu như máy tính được huấn luyện tốt. c. Tìm kiếm thông tin H Việc phân loại văn bản có thể áp dụng trong các hệ thống tìm kiếm thông tin nhằm tăng hiệu suất cũng như tăng độ chính xác của việc tìm kiếm. Do sự phát triển của Internet, số lượng thông tin trực tuyến ngày càng tăng. Một thao tác phổ biến trên Internet là tìm kiếm. Tuy nhiên, do khối lượng thông tin rất lớn nên các cỗ máy tìm kiếm (search engine) thường tổ chức dữ liệu vào các chủ đề giúp không gian tìm kiếm giảm đi, qua đó tăng hiệu suất của hệ thống. Ngoài ra việc tìm kiếm theo từ khoá thường không đạt được độ chính xác cao nên các search engine thường kết hợp với tìm kiếm theo chủ đề nhằm cải thiện độ chính xác của việc tìm kiếm. SVTH: Phan Thanh Bình & Lê Bạch Vũ Trang 14 Luận văn tốt nghiệp GVHD: Th.s Nguyễn Chánh Thành d. Phân loại email Chức năng của một hệ thống phân loại email tự động là: - Từ chối mail theo luật. - Phân phối mail vào các folder định trước. - Chuyển mail đến địa chỉ khác. 1.2. Nội dung đề tài Trong luận văn chúng tôi tìm hiểu và áp dụng phương pháp k – Nearest Neighbour để phân loại văn bản tiếng Anh. Đối với ngôn ngữ tiếng Anh hiện nay có rất nhiều công trình liên quan như: Google, Yahoo, … H Các văn bản cần phân loại trong luận văn chúng tôi gói gọn trong 5 chủ đề: Trí tuệ nhân tạo (artificial intelligence), Cấu trúc dữ liệu + giải thuật (structure and C algorithm), mạng máy tính (network), sinh học (biology), bóng đá (football). Các chủ đề trên được thu thập từ các trang web được Google phân loại sẵn do TE đó mỗi thể loại rất đa dạng về nội dung. Trong đó hai chủ đề cấu trúc dữ liệu + giải thuật và trí tuệ nhân tạo được xem là tiêu biểu nhất cho việc phân loại vì chúng giao nhau rất lớn, thêm vào đó là chủ đề mạng máy tính cũng rất gần vì U chúng điều thuộc cùng một lĩnh vực khoa học máy tính. Ngoài ra, các chủ đề còn lại đại diện cho các văn bản hoàn toàn khác nhau nên việc phân loại văn H bản sẽ dễ dàng hơn và đạt độ chính xác cao hơn. Do đó một văn bản có thể thuộc cùng lúc cả hai hoặc nhiều chủ đề thì việc phân loại sẽ khó khăn hơn và mức độ chính xác cũng thấp hơn. Nếu giải quyết được tình huống khó khăn trên thì việc phân loại văn bản cho các chủ đề khác sẽ đạt độ chính xác cao hơn. Tóm lại, sau khi xây dựng thành công giải thuật phân loại văn bản cho các chủ đề trên, thì việc mở rộng phân loại văn bản cho nhiều chủ đề khác là điều hoàn toàn có thể t hực hiện được một cách dể dàng. Mỗi chủ đề cần phân loại phải trên vài trăm văn bản mẫu và phải có các chuyên gia riêng tạo lập thì mới có thể đạt được độ chính xác cao. SVTH: Phan Thanh Bình & Lê Bạch Vũ Trang 15 Luận văn tốt nghiệp GVHD: Th.s Nguyễn Chánh Thành 1.3. Ứng dụng mở rộng - Lập chỉ mục và tìm kiếm của Lucene 1.3.1. Giới thiệu Lucene Lucene là bộ công cụ mã nguồn mở viết bằng Java hỗ trợ việc tạo chỉ mục (indexing) và tìm kiếm (searching) văn bản. Đây là bộ công cụ dễ sử dụng, linh hoạt và khá mạnh với mô hình kiến trúc hướng đối tượng. Lucene là một thành viên rất được ưa chuộng trong các dự án của Apache Jakarta. Trong vài năm gần đây, hầu hết các thư viện tìm kiếm thông tin (IR: Information Retrieval) bằng Java đều hoàn toàn miễn phí. Lucene có thể tạo chỉ mục cho bất kì thông tin dạng text nào bạn muốn, sau đó thực hiện tìm kiếm theo nhiều tiêu chuẩn khác nhau. Mặc dù chỉ làm việc với H text, nhưng có nhiều tính năng khác được cung cấp để bạn có thể tạo index cho C văn bản Word, file PDF, XML, hay các trang HTML. Lucene không quá ph ức tạp. Nó cung cấp một khung làm việc cơ bản, hỗ trợ bạn xây dựng một công cụ TE tìm kiếm đầy đủ chức năng cho website của mình. Ta có thể xem Lucene là một tầng phía dưới, giúp xử lí thao tác index và search H U cho các chương trình bên trên, như trong hình sau: SVTH: Phan Thanh Bình & Lê Bạch Vũ Trang 16 Luận văn tốt nghiệp TE C H GVHD: Th.s Nguyễn Chánh Thành Hình 1. Mô hình kiến trúc của Lucene U Một số chương trình tìm kiếm có đầy đủ chức năng được xây dựng dựa trên cơ sở Lucene. Nếu bạn đang tìm một số thứ cần thiết đã được xây dựng sẵn hay H một khung làm việc dùng cho việc crawling, xử lí văn bản, và tìm kiếm, bạn có thể xem tại trang Lucene Wiki (http://wiki.apache.org/jakarta- lucene/PoweredBy) với nhiều chương trình: Zilverline, SearchBlox, Nutch, LARM, và jSearch. Với sự phong phú của thông tin, và thời gian là một trong những thứ quý giá của hầu hết mọi người, chúng ta cần làm cho những câu truy vấn trở nên linh hoạt, độc lập, đặc biệt để nhanh chóng cắt ngang rào cản phân loại cứng nhắc và tìm kiếm chính xác sau đó đưa ra kết quả hợp lý nhất theo yêu cầu. SVTH: Phan Thanh Bình & Lê Bạch Vũ Trang 17 Luận văn tốt nghiệp GVHD: Th.s Nguyễn Chánh Thành 1.3.2. Cơ sở nền tảng của Lucene Lucene là sản phẩm sáng tạo của Doug Cutting và sẵn có trên SourceForge, cho phép mọi người download. Nó gia nhập dòng sản phẩm phần mềm Apache Software Foundation's Jakarta mã nguồn mở bằng Java vào tháng 9 năm 2001. Từ khi được phổ biến rộng rãi, Lucene ngày càng được nhiều người dùng và các nhà phát triển ủng hộ. Tháng 11 năm 2002, phiên bản Lucene 1.2 được phát hành, rồi đến 1.3. Ngoài những tổ chức được đề cập đến ở trang "Powered by Lucene", còn có cácạpt chí như FedEx, Overture, Mayo Clinic, Hewlett Packard, New Scientist magazine, Epiphany, và một số khác. H 1.3.3. Mục đích, chức năng, công dụng Doug Cutting, một nhà phát triển đầy kinh nghiệm trong lĩnh vực text-search C (tìm kiếm văn bản) và công cụ phục hồi đã sáng tạo ra Lucene. Cutting là tác giả chính của cỗ máy tìm kiếm V-Twin và hiện nay là kiến trúc sư thâm niên TE tại Excite. Ông đã thiết kế Lucene nhằm giúp việc tạo index và khả năng tìm kiếm có thể phát triển trên nhiều ứng dụng, bao gồm:  Searchable email : Một ứng dụng email cho phép người dùng tìm kiếm U các thông điệp đã được lưu trữ và thêm vào những thông điệp mới để tạo index khi chúng đến. H  Online documentation search: một documentation reader -- CD, Web hay được nhúng vào một ứng dụng - cho phép người dùng tìm kiếm các văn bản hướng dẫn trực tuyến.  Searchable Webpages: Một trình duyệt Web hay máy chủ proxy có thể xây dựng một công cụ tìm kiếm riêng để tạo index cho mỗi trang Web mà người dùng đã vào, cho phép người dùng dễ dàng vào lại các trang Web đó.  Website search: Một chương trình CGI giúp người dùng tìm được Website của bạn. SVTH: Phan Thanh Bình & Lê Bạch Vũ Trang 18