Đăng ký Đăng nhập
Trang chủ Công nghệ thông tin Thiết kế - Đồ họa Tiếp cận học không giám sát trong học có giám sát với bài toán phân lớp văn bản ...

Tài liệu Tiếp cận học không giám sát trong học có giám sát với bài toán phân lớp văn bản tiếng việt và đề xuất cải tiến công thức tính độ liên quan giữa hai văn bản trong mô hình véctơ

.PDF
132
416
129

Mô tả:

Tóm tắt : Khai phá và phát hiện tri thức trong dữ liệu,các bài toán cơ bản trong xử lý văn bản phân nhóm phương pháp học không giám sát,phân nhóm dựa trên thuật ngữ xuất hiện thường xuyên(Frequenitemset)phân lớp,phương pháp học có giám sát bài toán phân lớp văn bản tiếng việt đề xuất hai hướng tiếp cận bài toá n theo phương pháp học không giám sát trong học cơ giám sát theo đề xuất theo cải tiến công thức đánh giá độ liên quan giữa hai văn bản trong mô hình véctơ thiết kế xây dựng hệ thống thử nghiệm cài đặt mô hình và kết quả thử nghiệm Mô tả: Luận văn thạc sỹ Chuyên ngành Công nghệ thông tin
®inh thÞ ph­¬ng thu Bé gi¸o dôc vµ ®µo t¹o Tr­êng ®¹i häc b¸ch khoa Hµ Néi -------***------- §inh ThÞ Ph­¬ng Thu tiÕp cËn häc kh«ng gi¸m s¸t trong häc cã gi¸m s¸t ngµnh c«ng nghÖ th«ng tin víi bµi to¸n ph©n líp v¨n b¶n tiÕng viÖt & ®Ò xuÊt c¶i tiÕn c«ng thøc tÝnh ®é liªn quan gi÷a hai v¨n b¶n trong m« h×nh vector luËn v¨n th¹c sÜ c«ng nghÖ th«ng tin kho¸ 2002 - 2004 Hµ néi - N¨m 2004 bé gi¸o dôc vµ ®µo t¹o tr­êng ®¹i häc b¸ch khoa hµ néi ----------***--------§inh ThÞ Ph­¬ng Thu tiÕp cËn häc kh«ng gi¸m s¸t trong häc cã gi¸m s¸t víi bµi to¸n ph©n líp v¨n b¶n tiÕng viÖt & ®Ò xuÊt c¶i tiÕn c«ng thøc tÝnh ®é liªn quan gi÷a hai v¨n b¶n trong m« h×nh vector Chuyªn ngµnh: C«ng nghÖ th«ng tin luËn v¨n th¹c sÜ c«ng nghÖ th«ng tin ng­êi h­íng dÉn khoa häc TS. Huúnh QuyÕt Th¾ng Hµ néi - 11/2004 - Trang 1 - MỤC LỤC MỤC LỤC .......................................................................................................... 1 Danh mục các thuật ngữ và ký hiệu viết tắt trong Luận văn ...................... 6 Danh mục các bảng trong Luận văn .............................................................. 8 Danh mục các hình vẽ trong Luận văn .......................................................... 9 MỞ ĐẦU .......................................................................................................... 10 phÇn i c¬ së lý thuyÕt ................................................................................... 13 CHƯƠNG 1 - TỔNG QUAN VỀ XỬ LÝ VĂN BẢN...................................... 14 1.1. Khai phá và phát hiện tri thức trong dữ liệu ................................................ 15 1.1.1. Dữ liệu, Thông tin và Tri thức...........................................................................15 1.1.2. Khai phá dữ liệu và phát hiện tri thức ..............................................................15 1.2. Text Mining - Góc nhìn nhận quan trọng trong Data Mining .................... 18 1.3. Các khái niệm cơ bản trong xử lý văn bản .................................................... 19 1.3.1. Từ khóa, Thuật ngữ và Khái niệm ....................................................................19 1.3.2. Từ dừng (StopW ords ).......................................................................................20 1.3.3. Trọng số của thuật ngữ ....................................................................................20 1.3.4. Độ liên quan giữa các văn bản .........................................................................21 1.4. Các bài toán cơ bản trong xử lý văn bản ....................................................... 21 1.4.1. Tìm kiếm văn bản (Tex t Retrieval ) ...................................................................21 1.4.2. Phân lớp văn bản (Tex t Categorization, Tex t Classification ) ...........................22 1.4.3. Phân nhóm văn bản (Tex t Clustering ) ............................................................22 1.4.4. Tóm tắt văn bản (Tex t Sum m arization ) ...........................................................23 1.4.5. Dẫn đường văn bản (Tex t Routing ) ..................................................................23 1.5. Các phương pháp biểu diễn văn bản ............................................................. 24 1.5.1. Mô hình không gian vector (Vector Space M odel - VSM ) .................................24 1.5.1.1. Mô hình Boolean ............................................................................................ 25 §inh ThÞ Ph­¬ng Thu -  LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi 11/2004 - Trang 2 1.5.1.2. Mô hình tần số ............................................................................................... 26 1.5.1.3. Phương pháp xử lý véc tơ thưa ...................................................................... 27 1.5.2. Phương pháp biểu diễn văn bản dựa trên các khái niệm mờ ...........................29 1.6. Kết chương ....................................................................................................... 30 CHƯƠNG 2 PHÂN NHÓM - PHƯƠNG PHÁP HỌC KHÔNG GIÁM SÁT .. 31 2.1. Giới thiệu bài toán phân nhóm ....................................................................... 32 2.1.1. Phân nhóm dữ liệu ...........................................................................................32 2.1.2. Bài toán “Phân nhóm văn bản” ........................................................................32 2.2. Các yêu cầu của kĩ thuật phân nhóm ............................................................. 32 2.3. Các thuật toán Phân nhóm cơ bản hiện nay ................................................. 33 2.3.1. Các phương pháp phân chia (P artitionning Algorithm s )..................................34 2.3.2. Phương pháp phân nhóm dựa trên hàm mật độ (Density-Based ) ...................34 2.3.3. Phương pháp phân nhóm dựa trên lưới (Grid-Based M ethod ) ........................35 2.3.4. Phân nhóm dựa trên thuật ngữ xuất hiện thường xuyên (Frequent I tem set ) 36 2.3.4.1. Các giải thuật xác định tập các thuật ngữ xuất hiện thường xuyên .............. 36 2.3.4.2. Các giải thuật phân nhóm dựa trên thuật ngữ xuất hiện thường xuyên ........ 39 2.4. Đánh giá hiệu suất phân nhóm ....................................................................... 45 2.5. Kết chương ....................................................................................................... 45 CHƯƠNG 3 PHÂN LỚP - PHƯƠNG PHÁP HỌC CÓ GIÁM SÁT ............. 46 3.1. Giới thiệu bài toán ........................................................................................... 47 3.2. Các thuật toán Phân lớp văn bản cơ bản ...................................................... 47 3.2.1. Thuật toán cây quyết định (Decision Tree ) ......................................................48 3.2.1.1. Mô tả cây quyết định ...................................................................................... 48 3.2.1.2. Ví dụ minh họa cây quyết định....................................................................... 48 3.2.1.3. Xây dựng cây quyết định ................................................................................ 51 3.2.2. Thuật toán k-NN (k-Nearest Neighbor ) ...........................................................54 3.3. Đánh giá hiệu suất phân lớp văn bản............................................................. 57 3.4. Kết chương ....................................................................................................... 58 §inh ThÞ Ph­¬ng Thu -  LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi 11/2004 - Trang 3 - CHƯƠNG 4 VẤN ĐỀ NGHIÊN CỨU CỦA LUẬN VĂN - BÀI TOÁN PHÂN LỚP VĂN BẢN TIẾNG VIỆT ........................................................................... 59 4.1. Khai phá dữ liệu văn bản tiếng Việt .............................................................. 60 4.2. Các đặc trưng của tiếng Việt .......................................................................... 60 4.2.1. Các đơn vị tiếng Việt .........................................................................................61 4.2.2. Các đặc điểm chính tả văn bản tiếng Việt ........................................................61 4.2.3. Từ tiếng Việt .....................................................................................................62 4.2.4. Các chuẩn Font tiếng Việt được sử dụng ..........................................................63 4.3. Bài toán phân lớp văn bản tiếng Việt............................................................. 64 4.4. Kết chương ....................................................................................................... 65 phÇn iI thiÕt kÕ h­íng tiÕp cËn .................................................................... 66 CHƯƠNG 5 - ĐỀ XUẤT VÀ LỰA CHỌN GIẢI PHÁP TIẾP CẬN BÀI TOÁN PHÂN LỚP VĂN BẢN TIẾNG VIỆT .................................................... 67 5.1. Đề xuất hai hướng tiếp cận bài toán .............................................................. 68 5.1.1. Hướng tiếp cận theo phương pháp học không giám sát trong học có giám sát ...............................................................................................................................68 5.1.2. Hướng tiếp cận theo đề xuất cải tiến công thức đánh giá độ liên quan giữa hai văn bản trong mô hình vector ..............................................................................69 5.2. Lựa chọn giải pháp tiếp cận ............................................................................ 71 5.2.1. Tiếp cận theo phương pháp học không giám sát trong học có giám sát ..........71 5.2.1.1. Tiền xử lý văn bản .......................................................................................... 72 5.2.1.2. Biểu diễn văn bản trong mô hình vector ........................................................ 74 5.2.1.3. Phân nhóm các lớp văn bản mẫu ................................................................... 77 5.2.1.4. Phân lớp văn bản dựa trên tiếp cận phân nhóm ............................................ 78 5.2.2. Tiếp cận theo đề xuất cải tiến công thức đánh giá độ liên quan giữa hai văn bản trong mô hình vector ...........................................................................................80 5.2.2.1. Mô hình tiếp cận ............................................................................................ 80 5.2.2.2. Tiền xử lý và vector hóa văn bản ................................................................... 81 5.2.2.3. Quản lý độ liên quan giữa các term và văn bản mẫu .................................... 81 5.2.2.4. Phân lớp văn bản với công thức cải tiến đề xuất........................................... 82 5.3. Kết chương ....................................................................................................... 83 §inh ThÞ Ph­¬ng Thu -  LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi 11/2004 - Trang 4 - CHƯƠNG 6 - THIẾT KẾ XÂY DỰNG HỆ THỐNG THỬ NGHIỆM .............. 84 6.1. Xác định yêu cầu .............................................................................................. 85 6.2. Thiết kế xây dựng hệ thống thử nghiệm ........................................................ 85 6.2.1. Thiết kế tổng thể ..............................................................................................85 6.2.2. Chức năng phân lớp văn bản ............................................................................86 6.2.2.1. Hướng tiếp cận học không giám sát .............................................................. 86 6.2.2.2. Hướng tiếp cận theo đề xuất cải tiến công thức ............................................ 88 6.2.3. Chức năng vector hóa văn bản .........................................................................89 6.2.4. Chức năng phân nhóm các lớp văn bản mẫu....................................................91 6.2.5. Chức năng xác định trước độ liên quan của các term trong từ điển với tập văn bản mẫu ...............................................................................................................93 6.2.6. Chức năng Quản lý tập mẫu .............................................................................94 6.2.7. Chức năng quản lý từ điển/ StopW ords ...........................................................95 6.3. Kết chương ....................................................................................................... 95 phÇn iii cµi ®Æt m« h×nh vµ kiÓm thö kÕt qu¶ ............................................. 96 CHƯƠNG 7 – CÀI ĐẶT MÔ HÌNH VÀ KIỂM THỬ KẾT QUẢ ..................... 97 7.1. Cài đặt chương trình ....................................................................................... 98 7.1.1. Lựa chọn công nghệ và môi trường cài đặt ......................................................98 7.1.2. Giao diện chương trình Demo ..........................................................................98 7.1.2.1. Giao diện hướng tiếp cận học không giám sát trong học có giám sát .......... 98 7.1.2.2. Giao diện hướng tiếp cận theo công thức cải tiến ....................................... 100 7.2. Cơ sở dữ liệu thử nghiệm .............................................................................. 102 7.3. Kết quả thử nghiệm ....................................................................................... 102 7.3.1. Kết quả phân tách các thuật ngữ .................................................................. 103 7.3.1.1. Đánh giá tốc độ phân tách các thuật ngữ .................................................... 103 7.3.1.2. Đánh giá hiệu quả phân tách các thuật ngữ ................................................ 104 7.3.2. Kết quả phân lớp văn bản .............................................................................. 105 7.3.2.1. Kết quả thử nghiệm phân lớp trên tập mẫu VnExpress ............................... 105 7.3.2.2. Kết quả thử nghiệm phân lớp trên tập mẫu VietNamNet............................. 107 §inh ThÞ Ph­¬ng Thu -  LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi 11/2004 - Trang 5 7.4. Đánh giá thử nghiệm ..................................................................................... 109 7.5. Kết chương ..................................................................................................... 109 KẾT LUẬN VÀ ĐỊNH HƯỚNG PHÁT TRIỂN ............................................ 110 TÀI LIỆU THAM KHẢO ................................................................................. 112 phÇn phô lôc ................................................................................................... 115 PHỤ LỤC 1 - Tập các từ dừng (Stopwords) tiếng Việt ............................ 116 PHỤ LỤC 2 - Kết quả thử nghiệm phân lớp trên tập dữ liệu VnExpress121 PHỤ LỤC 3 - Hướng dẫn cài đặt và sử dụng chương trình ................... 129 PHỤ LỤC 4 - Mô tả nội dung đĩa CD kèm theo ......................................... 130 §inh ThÞ Ph­¬ng Thu -  LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi 11/2004 - Trang 6 - Danh mục các thuật ngữ và ký hiệu viết tắt trong Luận văn STT Từ Nghĩa 1. Ca Một nhóm văn bản 2. Cluster Nhóm (nhóm dữ liệu, nhóm văn bản) 3. concept khái niệm 4. d Một văn bản 5. D Tập văn bản 6. Decision Tree Cây quyết định 7. Document vector Vector văn bản 8. Feature vector Vector thuộc tính đặc trưng 9. FIHC Hierarchical Frequent Item Based Clustering - Phân nhóm có phân cấp dựa trên thuật ngữ xuất hiện thường xuyên 10. Frequent itemset Tập thuật ngữ xuất hiện thường xuyên trong văn bản 11. GFI Global frequent item - Một thuật ngữ thường xuyên toàn cục 12. GFS Global frequent itemset -Tập thuật ngữ thường xuyên toàn cục 13. GS Global support - Phần trăm tài liệu chứa tập thuật ngữ. 14. hash-table bảng băm 15. HTML HyperText Markup Language - Ngôn ngữ đánh dấu siêu văn bản 16. ICS inter-cluster similarity - Độ tương tự trong của nhóm 17. KDD Knowledge Discovery in Database - Tiến trình khai phá dữ liệu và phát hiện tri thức 18. keyword từ khóa 19. k-itemset tập thuật ngữ gồm k phần tử 20. k-NN k-Nearest Neighbor - Thuật toán k láng giềng gần nhất §inh ThÞ Ph­¬ng Thu -  LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi 11/2004 - Trang 7 21. Machine Learning học máy 22. membership hàm thuộc function μA(x) 23. postpruning Tỉa cây sau 24. precision Độ chính xác phân lớp 25. prepruning Tỉa cây trước 26. recall Độ hồi tưởng (trong phân lớp) 27. Semi-structured Dạng bán cấu trúc 28. Sim(Ca←Cb), Similarity- Độ tương tự giữa hai nhóm văn bản Ca và Cb 29. Stop word Từ dừng 30. supervised learning Học có giám sát method 31. term thuật ngữ 32. Test set Tập dữ liệu kiểm thử 33. Text Catergorization Phân lớp văn bản 34. Text Classification Phân lớp văn bản 35. Text Clustering Phân nhóm văn bản 36. Text Mining Khai phá dữ liệu văn bản 37. TF × IDF Phương pháp biểu diễn văn bản dựa trên tần số thuật ngữ TF và nghịch đảo tần số văn bản IDF 38. Training set Tập dữ liệu huấn luyện 39. unstructured Dạng phi cấu trúc 40. unsupervised Học không giám sát learning method 41. VSM §inh ThÞ Ph­¬ng Thu - Vector Space Model - Mô hình không gian vector  LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi 11/2004 - Trang 8 - Danh mục các bảng trong Luận văn Bảng 1.1. Ví dụ về văn bản biểu diễn theo từ khóa và tần số xuất hiện ______________ 25 Bảng 1.2. Ví dụ biểu diễn vector thưa. _______________________________________ 28 Bảng 2.1. Dữ liệu đầu vào để xây dựng cây FP ________________________________ 38 Bảng 3.1. Các mẫu huấn luyện dùng cho cây quyết định class LÚA ________________ 49 Bảng 3.2. Ví dụ 1 về gán nhãn theo số đông ___________________________________ 56 Bảng 3.3. Ví dụ 2 về gán nhãn theo số đông ___________________________________ 57 Bảng 7.1. Thông tin mô tả một số thông số của các tập dữ liệu huấn luyện __________ 102 Bảng 7.2. Kết quả thử nghiệm phân lớp 80 văn bản trên tập mẫu VnExpress ________ 105 Bảng 7.3. Kết quả thử nghiệm phân lớp 35 văn bản trên tập mẫu VietNamNet _______ 107 §inh ThÞ Ph­¬ng Thu -  LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi 11/2004 - Trang 9 - Danh mục các hình vẽ trong Luận văn Hình 1.1. Tiến trình khai phá dữ liệu và phát hiện tri thức (KDD) __________________ 17 Hình 1.2. Chức năng dẫn đường văn bản trong VNExpress _______________________ 24 Hình 1.3. Ví dụ biểu diễn văn bản dựa trên khái niệm mờ ________________________ 29 Hình 2.1. Ví dụ mô tả giải thuật k-means _____________________________________ 34 Hình 2.2. Mô tả một giải thuật phân nhóm dựa trên lưới _________________________ 35 Hình 2.3. Ví dụ về thuật toán Apriori ________________________________________ 37 Hình 2.4. Ví dụ về xây dựng cây FP _________________________________________ 38 Hình 3.1. Một ví dụ về cây quyết định cho phân lớp LÚA _________________________ 49 Hình 3.2. Ví dụ tìm kiếm lời giải trên cây quyết định phân lớp chủ đề “LÚA” ________ 50 Hình 3.3. Đồ thị phân bố đại lượng Entropy ___________________________________ 52 Hình 3.4. Minh họa việc khoanh vùng k văn bản gần nhất với k = 5 ________________ 55 Hình 3.5. Minh họa cách tính precision và recall _______________________________ 57 Hình 5.1. Mô hình tiếp cận theo phương pháp học không giám sát _________________ 71 Hình 5.2. Thuật toán tách term tiếng Việt _____________________________________ 74 Hình 5.3. Phân nhóm các lớp văn bản mẫu với thuật toán FIHC ___________________ 78 Hình 5.4. Mô hình tiếp cận theo công thức cải tiến đề xuất _______________________ 80 Hình 6.1. Sơ đồ chức năng tổng thể của hệ thống _______________________________ 85 Hình 6.2. Chức năng phân lớp văn bản theo hướng tiếp cận học không giám sát ______ 86 Hình 6.3. Chức năng phân lớp văn bản theo hướng tiếp cận cải tiến công thức _______ 88 Hình 6.4. Mô hình bộ vector hóa văn bản _____________________________________ 90 Hình 6.5. Chức năng phân nhóm các lớp văn bản mẫu __________________________ 91 Hình 6.6. Chức năng xác định độ liên quan của các term trong từ điển với tập mẫu ____ 93 Hình 6.7. Chức năng Quản lý tập văn bản mẫu ________________________________ 94 Hình 6.8. Chức năng quản lý Từ điển/StopWords _______________________________ 95 Hình 7.1. Các giao diện chương trình cài đặt hướng tiếp cận học không giám sát ____ 100 Hình 7.2. Các giao diện chương trình cài đặt hướng tiếp cận theo công thức cải tiến _ 101 Hình 7.3. Tốc độ tách thuật ngữ ___________________________________________ 103 §inh ThÞ Ph­¬ng Thu -  LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi 11/2004 - Trang 10 - MỞ ĐẦU Sự phát triển vượt bậc của khoa học và công nghệ trong một vài thập kỷ gần đây đã mang lại cho con người nhiều tri thức hơn. Thông tin, tri thức giờ đây không chỉ còn được lưu giữ trên giấy tờ nữa mà còn được số hóa và cất giữ như các tài liệu điện tử. Thế kỷ 20 đánh dấu sự ra đời và phát triển mạnh mẽ của công nghệ thông tin và công nghệ điện tử cùng với máy tính, mạng máy tính và mạng thông tin toàn cầu có khả năng chia sẻ thông tin, an toàn, tốc độ trao đổi, khả năng xử lý thông tin nhanh chóng, chính xác,… Con người không còn đáp ứng được với việc xử lý các thông tin lưu trữ dạng văn bản điện tử theo các cách thủ công truyền thống. Từ đó nảy sinh các nhu cầu về xử lý thông tin văn bản tự động. MỤC ĐÍCH VÀ LÝ DO LỰA CHỌN ĐỀ TÀI Trên thế giới đã có rất nhiều thành công trong lĩnh vực nghiên cứu xử lý văn bản như của hãng IBM, trong các phòng thí nghiệm ở MIT [12], hay trong các viện nghiên cứu của các trường đại học ở Mỹ, Pháp, Nhật bản, Canada,... Tuy nhiên, các thành công đó chủ yếu tập trung vào vấn đề nghiên cứu văn bản tiếng Anh, tiếng Pháp, những ngôn ngữ tương đối đơn giản khi xử lý. Trong khi đó, rất ít công cụ đã được xây dựng thực sự thành công trong lĩnh vực xử lý văn bản tiếng Việt. Do nhu cầu hội nhập, nhu cầu phát triển về kinh tế, văn hóa, xã hội ngày càng tăng, các thông tin được lưu trữ qua văn bản điện tử, qua web, qua email phát triển với tốc độ §inh ThÞ Ph­¬ng Thu -  LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi 11/2004 - Trang 11 không ngừng, nhu cầu nghiên cứu và xây dựng các công cụ khai phá văn bản tiếng Việt đang được hết sức coi trọng. Luận văn tốt nghiệp này được thực hiện với mục đích nghiên cứu tìm hiểu các lý thuyết xử lý văn bản đã được nghiên cứu phát triển trong nước và trên thế giới để từ đó xây dựng giải pháp cho các bài toán xử lý văn bản tiếng Việt. Bài toán xử lý cụ thể đặt ra trong luận văn này là Bài toán phân lớp văn bản tiếng Việt. NỘI DUNG VÀ PHẠM VI NGHIÊN CỨU CỦA ĐỀ TÀI Trong luận văn nghiên cứu về bài toán phân lớp văn bản tiếng Việt, với mục đích tăng độ chính xác cho kết quả phân lớp văn bản tiếng Việt, dựa trên cơ sở lý thuyết đã nghiên cứu, tác giả đề xuất hai hướng tiếp cận bài toán và trình bày các kết quả nghiên cứu thử nghiệm theo cả hai hướng tiếp cận này đã tiến hành trong khoảng thời gian vừa qua. • Hướng tiếp cận thứ nhất: xuất phát từ ý tưởng rằng mặc dù kĩ thuật phân nhóm là một phương pháp học không giám sát và kĩ thuật phân lớp là một phương pháp học có giám sát nhưng chúng ta vẫn có thể sử dụng cách tiếp cận phân nhóm để tăng hiệu quả cho bài toán phân lớp văn bản. Với cách tiếp cận này chúng ta sẽ giảm được kích thước, số chiều trong không gian vector đặc trưng và mang lại hiệu quả rõ rệt. • Hướng tiếp cận thứ hai: tác giả đề xuất một sự cải tiến công thức tính độ liên quan giữa các văn bản trong mô hình vector, công thức này được phát triển dựa trên những nghiên cứu đã được chứng minh trong [6]. Việc sử dụng công thức cải tiến này kết hợp với các cấu trúc dữ liệu phù hợp nhằm mục đích tối ưu kiến trúc cho mô hình thực hiện đã giảm được chi phí thời gian đáng kể trong quá trình tiến hành phân lớp và cho một kết quả thực nghiệm tương đối tốt. Trong cả hai hướng tiếp cận tác giả đều sử dụng mô hình không gian vector để biểu diễn văn bản. §inh ThÞ Ph­¬ng Thu -  LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi 11/2004 - Trang 12 - BỐ CỤC TRÌNH BÀY CỦA LUẬN VĂN Bố cục trình bày của luận văn bao gồm 3 phần, 7 chương. Phần I: Cơ sở lý thuyết  Chương I: Giới thiệu một khung nhìn tổng quan về lĩnh vực xử lý văn bản.  Chương II: Đề cập đến kỹ thuật phân nhóm văn bản là một kỹ thuật học không giám sát trong xử lý văn bản.  Chương III: Tìm hiểu về phương pháp phân lớp văn bản là một kỹ thuật học có giám sát trong xử lý văn bản.  Chương IV: Mô tả bài toán nghiên cứu chính của Luận văn: Bài toán phân lớp trên các văn bản tiếng Việt. Phần II: Thiết kế hướng tiếp cận  Chương V: Tác giả đề xuất hai hướng tiếp cận và lựa chọn giải pháp cho các mô hình tiếp cận theo hai hướng đó.  Chương VI: Thiết kế mô hình phần mềm cho chương trình kiểm thử. Phần III: Cài đặt mô hình và kiểm thử kết quả  Chương VII: Trình bày quá trình tiến hành thực nghiệm và các kết quả thực nghiệm của cả hai hướng tiếp cận. Cuối cùng, trong phần kết luận và định hướng phát triển, tác giả nêu ra các nhận xét về kết quả đạt được và một số định hướng phát triển tiếp theo của đề tài ■. §inh ThÞ Ph­¬ng Thu -  LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi 11/2004 - Trang 13 - phÇn i c¬ së lý thuyÕt Néi dung * Nội dung phần I mô tả tổng quan cơ sở lý thuyết liên quan đến vấn đề nghiên cứu trong luận văn:  Chương I: Tổng quan về xử lý văn bản  Chương II: Phân nhóm – phương pháp học không giám sát  Chương III: Phân lớp – phương pháp học có giám sát  Chương IV: Vấn đề nghiên cứu chính của luận văn – bài toán phân lớp văn bản tiếng Việt. §inh ThÞ Ph­¬ng Thu -  LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi 11/2004 - Trang 14 - PhÇn 1 C HƯƠNG 1 - TỔNG QUAN VỀ XỬ LÝ VĂN BẢN Néi dung: 1.1. Khai ph¸ vµ ph¸t hiÖn tri thøc trong d÷ liÖu 1.2. Text Mining – gãc nh×n nhËn quan träng trong Data mining 1.3. C¸c kh¸i niÖm c¬ b¶n trong xö lý v¨n b¶n 1.4. C¸c bµi to¸n c¬ b¶n trong xö lý v¨n b¶n 1.5. C¸c ph­¬ng ph¸p biÓu diÔn v¨n b¶n 1.6. KÕt ch­¬ng §inh ThÞ Ph­¬ng Thu -  LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi 11/2004 - Trang 15 - 1.1. Khai phá và phát hiện tri thức trong dữ liệu 1.1.1. Dữ liệu, Thông tin và Tri thức Dữ liệu được hiểu là một chuỗi các bit, các con số hoặc các đối tượng mà chúng ta thu thập được hàng ngày. Ví dụ: dữ liệu là các file trong máy tính, dữ liệu là các văn bản giấy tờ mà chúng ta phải xử lý hàng ngày, các tín hiệu,... Thông tin là dữ liệu đã được loại bỏ đi nhiễu, sự dư thừa và đã được biểu diễn dưới dạng mà con người có thể nhận thức được. Ví dụ: thông tin về tình hình giá cổ phiếu, thông tin về nhiệt độ trong tháng,... Tri thức được hiểu là các thông tin đã được tích hợp lại, đã được nhận thức, kiểm nghiệm, hay được đúc rút ra thành các quy luật có ý nghĩa đối với con người. Ví dụ: từ thông tin về nhiệt độ trong tháng, con người có thể đưa ra được những dự báo thời tiết quan trọng, hoặc từ các thông tin về tình hình giá cổ phiếu, các nhà kinh doanh có thể phân tích và nắm được diễn biến của thị trường để có các quyết định đầu tư đúng đắn,... Tri thức chính là các dữ liệu, thông tin ở mức trừu tượng và khái quát cao hơn. So với dữ liệu và thông tin thì tri thức ở dạng cô đọng và dễ hiểu nhất đối với con người. Rõ ràng trong kỷ nguyên công nghệ thông tin này thì con người chỉ muốn tìm kiếm và lĩnh hội các tri thức, đó là cách nhanh nhất và hợp lý nhất, so với chi phí thời gian và khả năng để hiểu được các dữ liệu ở một dạng thô sơ nào đó. Điều đó cũng cho thấy vai trò quan trọng của lớp các bài toán khai phá dữ liệu và phát hiện tri thức. 1.1.2. Khai phá dữ liệu và phát hiện tri thức Khai phá dữ liệu, hay Data Mining, được định nghĩa như quá trình phát hiện các tri thức từ các dữ liệu lớn được lưu trữ trong cơ sở dữ liệu, data warehouse hay các kho chứa thông tin khác [1, 12, 17]. Thuật ngữ khai phá dữ liệu (data mining) chỉ việc tìm kiếm một tập hợp nhỏ có giá trị từ một số lượng lớn các dữ liệu thô. Một ví dụ hay được nhắc tới là việc §inh ThÞ Ph­¬ng Thu -  LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi 11/2004 - Trang 16 khai thác vàng từ đá và cát, khai phá dữ liệu được ví như công việc “đãi cát tìm vàng” trong một tập hợp lớn các dữ liệu cho trước. Có nhiều thuật ngữ hiện được dùng cũng có nghĩa tương tự với từ data mining như knowledge mining (khai phá tri thức), knowledge extraction (chắt lọc tri thức), data/patern analysis (phân tích dữ liệu/mẫu), data archaeology (khảo cổ dữ liệu), data dredging (nạo vét dữ liệu) [12]. Hiện nay, thuật ngữ khai phá dữ liệu được dùng quen thuộc và thường đồng nhất với một thuật ngữ khác là phát hiện tri thức trong cơ sở dữ liệu – Knowledge Discovery in Database (KDD) [1, 2]. Thực ra, khai phá dữ liệu chỉ là một bước trong các quá trình của KDD. Tiến trình phát hiện tri thức KDD nói chung bao gồm 7 quá trình cơ bản sau đây [1, 2, 4, 12, 17]: 1. Làm sạch dữ liệu: Loại bỏ nhiễu và các dữ liệu không cần thiết. 2. Tích hợp dữ liệu: Tích hợp các nguồn dữ liệu khác nhau. 3. Lựa chọn dữ liệu: Chọn lựa các dữ liệu liên quan tới quá trình phân tích. 4. Chuyển đổi dữ liệu: Các dữ liệu được chuyển đổi sang các dạng phù hợp cho việc xử lý. 5. Khai phá dữ liệu: Là một trong những bước quan trọng nhất, ở đây sử dụng những phương pháp thông minh để chắt lọc ra những mẫu dữ liệu có giá trị. 6. Ước lượng mẫu: Quá trình này nhằm đánh giá các kết quả tìm được thông qua các độ đo nào đó. 7. Biểu diễn tri thức: Sử dụng các kỹ thuật biểu diễn và thể hiện trực quan các tri thức cho người dùng. Hình 1.1 mô tả bảy quá trình trên trong tiến trình KDD. §inh ThÞ Ph­¬ng Thu -  LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi 11/2004 - Trang 17 - Hình 1.1. Tiến trình khai phá dữ liệu và phát hiện tri thức (KDD) Việc áp dụng tiến trình KDD có thể thực hiện trên nhiểu kiểu, loại dữ liệu khác nhau với các hình thức tổ chức lưu trữ khác nhau. Hiện nay, có rất nhiều cách tổ chức dữ liệu khác nhau: cơ sở dữ liệu văn bản, cơ sở dữ liệu quan hệ, cơ sở dữ liệu hướng đối tượng, cơ sở dữ liệu không gian, cơ sở dữ liệu hướng thời gian,… Đối với mỗi dạng cơ sở dữ liệu lại có các phương pháp xử lý và mục đích khai phá dữ liệu khác nhau tùy theo tính chất và đặc thù của dữ liệu. Các kỹ thuật được sử dụng có thể là các phương pháp truyền thống như học máy (Machine Learning), nhận dạng (Recognition), thống kê (Statistics),… và 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 (Genetic Algorithm), quy nạp luật (Rule Reduction),… §inh ThÞ Ph­¬ng Thu -  LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi 11/2004 - Trang 18 - 1.2. Text Mining - Góc nhìn nhận quan trọng trong Data Mining Trong các dạng dữ liệu thường xuyên được sử dụng thì văn bản là một trong những dạng được dùng phổ biến nhất. Văn bản có mặt ở mọi nơi và thường xuyên bắt gặp hàng ngày. Văn bản có thể là các bài báo, các tài liệu kinh doanh, các thông tin kinh tế, các bài nghiên cứu khoa học,... Dù việc áp dụng CSDL vào hoạt động quản lý của các tổ chức là rất phổ biến và đem lại nhiều lợi ích trong lưu trữ cũng như xử lý, nhưng trên thực tế còn rất nhiều thông tin khác được lưu trữ dưới dạng văn bản. Do đó, các bài toán xử lý văn bản đã được đặt ra từ khá lâu và cho đến nay vẫn là một bài toán quan trọng trong khai thác dữ liệu văn bản. Xử lý văn bản được hiểu đơn giản là các thao tác tác động lên văn bản để làm cho chúng dễ sử dụng hơn, thông tin trong chúng hữu ích hơn hoặc làm cho chúng được lưu trữ tốt hơn. Dữ liệu văn bản thường được chia thành hai loại [1, 9]: • 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à không 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): 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 thẻ đánh dấu để thể hiện nội dung chính của văn bản. Ví dụ: dạng tệp tin HTML, e-Mail,… Tùy từng mục đích sử dụng cụ thể mà việc xử lý văn bản được thực hiện trên dạng cấu trúc nào. Ví dụ, với bài toán phân lớp nội dung trang web thì dạng văn bản cần xử lý là HTML. Trong luận văn này, tác giả chỉ quan tâm xử lý các dữ liệu văn bản ở dạng phi cấu trúc (biểu diễn dưới dạng tệp tin TXT), bài toán được giải quyết theo hướng dữ liệu mở để tương lai có thể đáp ứng với các mục đích sử dụng khác nhau. §inh ThÞ Ph­¬ng Thu -  LuËn v¨n Th¹c sÜ CNTT - §¹i häc B¸ch Khoa Hµ Néi 11/2004
- Xem thêm -

Tài liệu liên quan