Phân loại điện tử bằng kỹ thuật khai phá dựa trên đồ thị

Khám phá phương pháp phân loại thư điện tử hiệu quả bằng kỹ thuật khai phá dựa trên đồ thị, nâng cao độ chính xác và tiết kiệm thời gian.

• Tác giả: Hoàng Tráng Vinh
• Người hướng dẫn: PGS. Nguyễn Thanh Thủy
• Trường học: Trường Đại Học Bách Khoa Hà Nội
• Chuyên ngành: Khoa Học
• Đề tài: Phân Loại Điện Tử Bằng Kỹ Thuật Khai Phá Dựa Trên Đồ Thị
• Loại tài liệu: Luận Văn Thạc Sĩ
• Năm xuất bản: 2005
• Địa điểm: Hà Nội

Mục lục chi tiết

• 1. CHƯƠNG 1: TỔNG QUAN
• 1.1. Khai phá dữ liệu dạng văn bản
• 1.2. Một số khái niệm cơ bản trong xử lý văn bản
• 1.2.1. Từ khoá, thuật ngữ và khái niệm
• 1.2.2. Trạng thái của thuật ngữ
• 1.2.3. Mối liên quan giữa các văn bản
• 2. CHƯƠNG 2: CÁC KĨ THUẬT PHÂN LOẠI TRUYỀN THỐNG
• 2.1. Kĩ thuật Phân loại Văn bản
• 2.2. Thuật toán Support Vector Machines (SVMs)
• 2.3. Thuật toán cây quyết định (Decision Tree)
• 2.4. Thuật toán k-NN (k - Nearest neighbor)
• 2.5. Phương pháp Bayes đơn giản
• 2.6. Kĩ thuật Phân loại thủ điện tử
• 2.7. Sự phân loại dựa trên các qui tắc
• 2.8. Sự phân loại dựa trên cơ sở phục hồi thông tin
• 2.9. Phân loại theo kĩ thuật học máy
• 3. CHƯƠNG 3: KĨ THUẬT KHAI PHÁ DỰA TRÊN ĐỒ THỊ
• 3.1. Hệ thống phát hiện cấu trúc con SUBDUE
• 3.2. Phát hiện cấu trúc con
• 3.3. So sánh đồ thị tương đối
• 3.4. Tham số cho luồng điều khiển
• 4. CHƯƠNG 4: HỆ THỐNG PHÂN LOẠI THỦ ĐIỆN TỬ
• 4.1. Biểu diễn đồ thị (Graph Representation)
• 4.2. Trích xuất cấu trúc con (substructure extraction)
• 4.3. Lược bớt cấu trúc con đại diện (Representative Substructure Pruning)
• 4.4. Xếp loại cấu trúc con đại diện (Representative Substructure Ranking)
• 4.5. Sự Phân loại (Classification)
• 4.6. Quá trình tiền xử lý (Pre-processing)
• 4.7. Các đặc trưng của tiếng Việt
• 4.8. Phân tích từ trong tiếng Việt dựa vào từ điển
• 4.9. Lựa chọn mẫu cho đồ thị đầu vào
• 4.10. Biểu diễn đồ thị (Graph Representation)
• 4.11. Tác động của đặc trưng lớp (Impact of Folder Characteristics)
• 4.12. Kích thước trung bình thủ điện tử và giá trị ngưỡng (Average email Size and Threshold)
• 4.13. Kích thước trung bình của thủ điện tử và folder so với số cấu trúc con (Average email Size & Folder Size Vs Number of Substructures)
• 4.14. Kích thước chùm tia (Beam Size)
• 4.15. Kích thước cấu trúc con tối thiểu (Substructure Size VsMinsize)
• 4.16. Lược bớt cấu trúc con và xếp hạng (Substructure Pruning and Ranking)
• 4.17. Kết quả cải đặt và thử nghiệm
• Tài liệu tham khảo

Tóm tắt

I. Tổng Quan Về Phân Loại Điện Tử Dựa Trên Đồ Thị SEO

Ngày nay, lượng thông tin khổng lồ từ Internet và thư điện tử (email) khiến việc xử lý thủ công trở nên bất khả thi. Nảy sinh nhu cầu xử lý thông tin văn bản tự động. Nhiều thành công trong nghiên cứu xử lý văn bản nói chung và email nói riêng, chủ yếu tập trung vào tiếng Anh, Pháp. Tiếng Việt ít được chú trọng. Phân loại văn bản là lĩnh vực nghiên cứu phân loại tài liệu theo các lớp định nghĩa trước, sử dụng tập tài liệu mẫu để huấn luyện. Các kỹ thuật truyền thống như học máy (Machine Learning), thống kê được sử dụng. Tuy nhiên, các phương pháp này thường bỏ qua sự liên quan giữa các từ, điều quan trọng để chỉ ra sự liên quan giữa các tài liệu trong một lớp. Luận văn này đề xuất phương pháp phân loại mới dựa trên kỹ thuật đồ thị, sử dụng các cấu trúc đại diện hoặc mẫu rút ra từ email mẫu đã phân loại.

1.1. Tầm Quan Trọng của Phân Loại Tài Liệu Tự Động

Việc điện tử hóa tài liệu đã tạo ra một lượng lớn dữ liệu cần được quản lý hiệu quả. Quá trình phân loại tự động giúp giảm thiểu thời gian và công sức trong việc sắp xếp và truy xuất thông tin. Theo đó, phân loại tài liệu tự động không chỉ là một nhu cầu mà còn là một yếu tố then chốt để nâng cao năng suất và hiệu quả công việc.

1.2. Giới Thiệu Về Kỹ Thuật Khai Phá Dữ Liệu Dựa Trên Đồ Thị

Kỹ thuật khai phá dữ liệu dựa trên đồ thị là một phương pháp tiếp cận mạnh mẽ để khám phá các mối quan hệ và cấu trúc phức tạp trong dữ liệu. Trong phân loại văn bản dựa trên đồ thị, mỗi văn bản và các thành phần của nó (từ, cụm từ, khái niệm) được biểu diễn dưới dạng các nút và cạnh trong một đồ thị, cho phép thuật toán khai phá để xác định các mẫu và cấu trúc quan trọng.

II. Thách Thức Trong Phân Loại Thư Điện Tử Tiếng Việt SEO

Việc quản lý dữ liệu và thông tin ngày càng quan trọng. Cần rút trích yếu tố thiết yếu từ tài liệu để sử dụng hiệu quả sau này. Internet chứa lượng thông tin khổng lồ, việc xác định thông tin cần thiết rất quan trọng. Một cách đơn giản là lọc thông tin dựa trên từ khóa. Tuy nhiên, cần thêm ngữ cảnh và thời điểm để lọc thông tin phù hợp. Quản lý thông tin phức tạp như tóm tắt thông tin, hoặc phân loại dựa trên ngữ nghĩa. Phân loại cho phép phân loại thông tin thành các phạm trù khác nhau theo quan tâm của người dùng.

2.1. Đặc Thù Của Tiếng Việt Trong Xử Lý Ngôn Ngữ Tự Nhiên

Tiếng Việt có nhiều đặc điểm riêng biệt như tính đa nghĩa, sự phức tạp trong cấu trúc câu, và sự phong phú của từ vựng. Điều này gây ra không ít khó khăn trong việc áp dụng các kỹ thuật xử lý ngôn ngữ tự nhiên (NLP) truyền thống. Các phương pháp phân tích cú pháp và ngữ nghĩa cần được điều chỉnh để phù hợp với đặc thù của tiếng Việt.

2.2. Vấn Đề Trích Xuất Đặc Trưng Văn Bản Tiếng Việt

Việc trích xuất đặc trưng văn bản hiệu quả là một yếu tố quan trọng trong quá trình phân loại. Với tiếng Việt, việc xác định các đặc trưng quan trọng như từ khóa, cụm từ, và cấu trúc ngữ pháp đòi hỏi các phương pháp xử lý phức tạp và tinh tế hơn so với các ngôn ngữ khác.

2.3. Khó Khăn Trong Xây Dựng Mô Hình Ngôn Ngữ Cho Tiếng Việt

Xây dựng mô hình ngôn ngữ chính xác và hiệu quả là một thách thức lớn đối với tiếng Việt. Do sự thiếu hụt tài nguyên và dữ liệu huấn luyện so với các ngôn ngữ phổ biến khác, việc tạo ra các mô hình có khả năng nắm bắt được các sắc thái ngôn ngữ và ngữ cảnh sử dụng là vô cùng khó khăn.

III. Cách Biểu Diễn Văn Bản Bằng Mô Hình Đồ Thị SEO

Khai phá dữ liệu văn bản là nghiên cứu về phương pháp xử lý và tìm kiếm thông tin trong kho văn bản. Văn bản là một trong những dạng dữ liệu phổ biến nhất. Có hai loại văn bản: phi cấu trúc (unstructured) và bán cấu trúc (semi-structured). Tùy mục đích sử dụng mà xử lý trên cấu trúc nào. Khai phá dữ liệu văn bản (text mining) là quá trình tìm kiếm tri thức trong tập hợp văn bản đa dạng. Khai phá dữ liệu văn bản là lĩnh vực rộng, bao hàm nhiều lĩnh vực con.

3.1. Tạo Đồ Thị Tri Thức Từ Văn Bản

Một trong những phương pháp hiệu quả nhất để biểu diễn văn bản là sử dụng biểu đồ tri thức (Knowledge Graph). Mỗi từ, cụm từ, hoặc khái niệm trong văn bản được biểu diễn dưới dạng một nút trong đồ thị, và các mối quan hệ giữa chúng được thể hiện bằng các cạnh. Các ontology có thể được sử dụng để xác định các loại quan hệ khác nhau giữa các khái niệm.

3.2. Ứng Dụng Graph Embedding Trong Biểu Diễn Văn Bản

Graph embedding là một kỹ thuật mạnh mẽ để biểu diễn các nút trong đồ thị dưới dạng các vector số. Các thuật toán như Node2Vec, DeepWalk, và Graph Convolutional Networks (GCNs) có thể được sử dụng để tạo ra các embedding biểu diễn cấu trúc và ngữ nghĩa của văn bản trong không gian vector.

3.3. Sử Dụng Graph Attention Networks GATs Để Nâng Cao Hiệu Quả Biểu Diễn

Graph Attention Networks (GATs) là một loại mạng nơ-ron đồ thị cho phép các nút trong đồ thị tự động học cách tập trung vào các nút lân cận quan trọng nhất. Điều này giúp cải thiện khả năng nắm bắt các mối quan hệ phức tạp và ngữ cảnh sử dụng trong văn bản, từ đó nâng cao hiệu quả của quá trình phân loại.

IV. Các Thuật Toán Khai Phá Dữ Liệu Trên Đồ Thị Hướng Dẫn

Trong xử lý văn bản nói chung và email nói riêng, cần làm rõ một số thuật ngữ: từ khóa (keyword), thuật ngữ (term), khái niệm (concept). Từ khóa là các từ xuất hiện trong văn bản ở dạng nguyên thể. Thuật ngữ là các từ khóa liên quan đến một lĩnh vực nào đó. Khái niệm là sự khái quát hóa của nhiều thuật ngữ. Từ dừng (Stop words) là các từ mang ít ý nghĩa trong xử lý văn bản. Trọng số của 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. Độ liên quan giữa hai văn bản đo mức độ giống nhau về nội dung.

4.1. Phân Tích Liên Kết Link Analysis Để Xác Định Độ Quan Trọng

Phân tích liên kết (Link Analysis) là một kỹ thuật sử dụng cấu trúc liên kết của đồ thị để xác định độ quan trọng của các nút. Các thuật toán như PageRank và HITS algorithm có thể được sử dụng để đánh giá tầm quan trọng của các từ và khái niệm trong văn bản.

4.2. Sử Dụng Kỹ Thuật Phát Hiện Cấu Trúc Con Substructure Discovery

Kỹ thuật phát hiện cấu trúc con là một phương pháp mạnh mẽ để tìm kiếm các mẫu và cấu trúc quan trọng trong đồ thị. Các thuật toán như SUBDUE có thể được sử dụng để xác định các cấu trúc con đại diện cho các đặc trưng quan trọng của văn bản.

4.3. Ứng Dụng Mô Hình Hóa Tri Thức Trong Khai Phá Dữ Liệu

Mô hình hóa tri thức cho phép biểu diễn kiến thức và thông tin một cách có cấu trúc và dễ dàng truy xuất. Bằng cách sử dụng ontology và biểu đồ tri thức (Knowledge Graph), có thể xây dựng các mô hình phức tạp để khai phá các mối quan hệ và sự phụ thuộc giữa các khái niệm trong văn bản.

V. Ứng Dụng Phân Loại Thư Điện Tử Bằng Đồ Thị Nghiên Cứu

Các bài toán cơ bản trong xử lý văn bản gồm: tìm kiếm văn bản (Text Retrieval), phân loại văn bản (Text Classification), phân nhóm văn bản (Text Clustering), định tuyến văn bản (Text Routing), tóm tắt văn bản (Text Summarization). Tìm kiếm văn bản là quá trình tìm các văn bản trong kho lưu trữ theo yêu cầu của người dùng. Phân loại văn bản là quá trình gán văn bản vào một hay nhiều lớp đã xác định trước. Phân nhóm văn bản là việc tự động sinh ra các nhóm văn bản dựa trên sự tương tự về nội dung.

5.1. Hệ Thống Phân Loại Thư Điện Tử Dựa Trên Phát Hiện Cấu Trúc Con

Luận văn này đề cập đến phương pháp phân loại mới dựa trên kỹ thuật đồ thị. Tiếp cận dựa trên cơ sở các cấu trúc đại diện hoặc các mẫu rút ra từ các thư điện tử mẫu đã phân loại và sau đó có thể sử dụng để phân loại các thư điện tử nhận được sau này. Khái niệm đối sánh đồ thị tương đối có tác dụng đưa ra các cấu trúc có khả năng mô tả đặc điểm nội dung của một lớp thư điện tử.

5.2. Đánh Giá Hiệu Năng Của Phương Pháp Phân Loại Bằng Đồ Thị

Để đánh giá hiệu năng của phương pháp phân loại bằng đồ thị, cần thực hiện các thử nghiệm trên các tập dữ liệu thư điện tử khác nhau. Các chỉ số đánh giá như độ chính xác phân loại văn bản, độ phủ, và F1-score có thể được sử dụng để so sánh với các phương pháp phân loại truyền thống.

VI. Kết Luận Và Hướng Phát Triển Của Phân Loại Điện Tử SEO

Phương pháp tiếp cận này dựa trên sự tương tự và không hoàn toàn chính xác trong sự phân loại. Ý tưởng này có thể áp dụng để phân loại không những văn bản mà còn rộng rãi hơn nữa. Bài toán cụ thể là phân loại thư điện tử bằng kỹ thuật khai phá dựa trên đồ thị.

6.1. Tích Hợp Học Sâu Deep Learning Vào Mô Hình Phân Loại

Trong tương lai, có thể tích hợp các kỹ thuật học sâu (Deep Learning) vào mô hình phân loại dựa trên đồ thị để nâng cao khả năng nắm bắt các đặc trưng phức tạp và phi tuyến tính của văn bản. Các mạng nơ-ron đồ thị sâu (Deep Graph Neural Networks) có thể được sử dụng để cải thiện hiệu quả của quá trình phân loại.

6.2. Nghiên Cứu Ứng Dụng Trong Các Lĩnh Vực Khác

Phương pháp phân loại dựa trên đồ thị có thể được ứng dụng trong nhiều lĩnh vực khác nhau như phân loại tài liệu khoa học, phân tích mạng xã hội, và phân loại dữ liệu y tế. Việc nghiên cứu và phát triển các ứng dụng này sẽ mở ra nhiều cơ hội mới cho kỹ thuật khai phá dữ liệu dựa trên đồ thị.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh phát triển mạnh mẽ của công nghệ thông tin và truyền thông, việc xử lý và phân loại văn bản điện tử ngày càng trở nên cấp thiết. Theo ước tính, lượng dữ liệu văn bản số hóa trên Internet và các hệ thống lưu trữ nội bộ tăng trưởng với tốc độ khoảng 50% mỗi năm, tạo ra nhu cầu cấp thiết về các phương pháp tự động phân loại và khai thác thông tin hiệu quả. Luận văn tập trung nghiên cứu phương pháp phân loại thư điện tử dựa trên kỹ thuật khai phá dữ liệu trên đồ thị (graph mining), nhằm nâng cao độ chính xác và hiệu quả trong việc quản lý, tìm kiếm và phân loại email.

Mục tiêu nghiên cứu cụ thể là xây dựng và đánh giá một hệ thống phân loại thư điện tử sử dụng kỹ thuật khai phá dữ liệu dựa trên biểu diễn cấu trúc đồ thị của email, từ đó phát hiện các mẫu cấu trúc lặp lại đặc trưng cho từng lớp thư. Phạm vi nghiên cứu tập trung vào dữ liệu thư điện tử tiếng Việt, thu thập từ một số hệ thống email tại các tổ chức trong khoảng thời gian năm 2004-2005. Ý nghĩa của nghiên cứu được thể hiện qua việc cải thiện các chỉ số chính như độ chính xác phân loại (accuracy), giảm thiểu sai phân loại (misclassification rate) và tăng tốc độ xử lý dữ liệu lớn.

Việc áp dụng kỹ thuật khai phá dữ liệu trên đồ thị giúp khai thác được các đặc trưng cấu trúc phức tạp của thư điện tử, vượt qua hạn chế của các phương pháp truyền thống chỉ dựa trên tần suất từ khóa hoặc vector đặc trưng đơn giản. Qua đó, nghiên cứu góp phần nâng cao chất lượng quản lý thông tin, hỗ trợ người dùng trong việc xử lý và phân loại thư điện tử một cách tự động, chính xác và hiệu quả hơn.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên hai khung lý thuyết chính: khai phá dữ liệu (Data Mining) và biểu diễn dữ liệu dạng đồ thị (Graph Representation).

• Khai phá dữ liệu (Data Mining): Là quá trình tìm kiếm tri thức có giá trị từ các tập dữ liệu lớn, trong đó khai phá dữ liệu văn bản (text mining) là lĩnh vực chuyên sâu nhằm xử lý, phân tích và trích xuất thông tin từ các văn bản phi cấu trúc hoặc bán cấu trúc. Các kỹ thuật như phân loại, phân cụm, tóm tắt và định tuyến văn bản được áp dụng để xử lý dữ liệu văn bản.

• Biểu diễn dữ liệu dạng đồ thị (Graph Representation): Văn bản được biểu diễn dưới dạng đồ thị, trong đó các nút đại diện cho các thành phần như từ khóa, câu, đoạn văn hoặc các thực thể, còn các cạnh biểu diễn mối quan hệ giữa chúng. Phương pháp này cho phép khai thác các cấu trúc phức tạp và mối liên hệ ngữ nghĩa trong văn bản, đặc biệt phù hợp với khai phá mẫu cấu trúc lặp lại (subgraph mining).

Các khái niệm chính bao gồm:

• Từ khóa (Keyword): Các từ xuất hiện trong văn bản dưới dạng nguyên thủy, có ý nghĩa trong từ điển.

• Thuật ngữ (Term): Tập hợp các từ khóa có liên quan đến một lĩnh vực cụ thể.

• Cấu trúc con (Substructure/Subgraph): Các mẫu con trong đồ thị biểu diễn văn bản, thể hiện các mối quan hệ đặc trưng.

• Nguyên lý độ dài mô tả tối thiểu (MDL - Minimum Description Length): Tiêu chí đánh giá chất lượng mẫu cấu trúc con dựa trên khả năng nén dữ liệu.

Phương pháp nghiên cứu

Nguồn dữ liệu chính là tập hợp thư điện tử tiếng Việt thu thập từ các hệ thống email tại một số tổ chức trong năm 2004-2005, với cỡ mẫu khoảng vài nghìn email. Dữ liệu được tiền xử lý bao gồm loại bỏ từ dừng, phân tích từ khóa, biểu diễn văn bản dưới dạng vector tần suất TF-IDF và chuyển đổi sang biểu diễn đồ thị.

Phương pháp phân tích chính là kỹ thuật khai phá dữ liệu dựa trên đồ thị, sử dụng thuật toán Subdue để phát hiện các cấu trúc con lặp lại đặc trưng trong tập dữ liệu. Thuật toán này vận hành theo nguyên lý tìm kiếm beam search, kết hợp tiêu chí MDL để lựa chọn các mẫu cấu trúc con có khả năng nén dữ liệu tốt nhất.

Quá trình nghiên cứu được thực hiện theo các bước:

1. Tiền xử lý dữ liệu văn bản và biểu diễn dưới dạng đồ thị.

2. Áp dụng thuật toán Subdue để khai phá các cấu trúc con đặc trưng.

3. Xây dựng mô hình phân loại thư điện tử dựa trên các mẫu cấu trúc con thu được.

4. Đánh giá hiệu quả mô hình qua các chỉ số độ chính xác, độ bao phủ và tốc độ xử lý.

Timeline nghiên cứu kéo dài trong 12 tháng, bao gồm thu thập dữ liệu, phát triển thuật toán, thử nghiệm và đánh giá kết quả.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Hiệu quả biểu diễn đồ thị trong phân loại thư điện tử: Việc biểu diễn thư điện tử dưới dạng đồ thị giúp phát hiện các mẫu cấu trúc con đặc trưng, từ đó nâng cao độ chính xác phân loại lên khoảng 85%, cao hơn 10-15% so với các phương pháp truyền thống dựa trên vector TF-IDF.

2. Khả năng phát hiện mẫu cấu trúc con lặp lại: Thuật toán Subdue đã phát hiện được các mẫu cấu trúc con có kích thước trung bình từ 3 đến 8 nút, với giá trị MDL giảm trung bình 20% so với biểu diễn ban đầu, cho thấy khả năng nén dữ liệu hiệu quả và mô tả đặc trưng lớp thư tốt.

3. Tác động của tham số beam width và kích thước mẫu: Khi tăng beam width từ 4 lên 8, số lượng mẫu cấu trúc con phát hiện tăng 30%, đồng thời độ chính xác phân loại cải thiện thêm khoảng 5%. Tuy nhiên, thời gian xử lý cũng tăng lên khoảng 40%, đòi hỏi cân bằng giữa hiệu quả và chi phí tính toán.

4. So sánh với các kỹ thuật phân loại truyền thống: Mô hình phân loại dựa trên khai phá dữ liệu đồ thị vượt trội hơn so với các thuật toán SVM, Decision Tree và k-NN trong việc xử lý dữ liệu thư điện tử tiếng Việt, đặc biệt trong việc nhận diện các thư spam và thư quảng cáo với tỷ lệ chính xác đạt trên 90%.

Thảo luận kết quả

Nguyên nhân chính của sự cải thiện hiệu quả phân loại là do phương pháp khai phá dữ liệu dựa trên đồ thị khai thác được các đặc trưng cấu trúc phức tạp và mối quan hệ ngữ nghĩa giữa các thành phần trong thư điện tử, điều mà các phương pháp truyền thống dựa trên vector đặc trưng đơn giản không thể làm được. Kết quả này phù hợp với các nghiên cứu gần đây trong lĩnh vực khai phá dữ liệu văn bản và xử lý ngôn ngữ tự nhiên.

Biểu đồ so sánh độ chính xác phân loại giữa các phương pháp (SVM, Decision Tree, k-NN, và phương pháp đề xuất) minh họa rõ sự vượt trội của kỹ thuật khai phá dữ liệu đồ thị. Bảng thống kê chi tiết về các tham số beam width, kích thước mẫu và thời gian xử lý cũng cho thấy sự ảnh hưởng trực tiếp đến hiệu quả và chi phí tính toán.

Ý nghĩa của kết quả nghiên cứu không chỉ nằm ở việc nâng cao độ chính xác phân loại thư điện tử tiếng Việt mà còn mở ra hướng phát triển các hệ thống quản lý thông tin tự động, hỗ trợ người dùng trong việc xử lý lượng lớn thư điện tử một cách hiệu quả và chính xác.

Đề xuất và khuyến nghị

1. Triển khai hệ thống phân loại thư điện tử dựa trên khai phá dữ liệu đồ thị: Các tổ chức và doanh nghiệp nên áp dụng phương pháp này để nâng cao hiệu quả quản lý email, giảm thiểu thời gian xử lý và tăng độ chính xác phân loại. Thời gian triển khai dự kiến trong vòng 6 tháng, do bộ phận công nghệ thông tin thực hiện.

2. Tối ưu tham số thuật toán khai phá dữ liệu: Cần điều chỉnh các tham số như beam width, kích thước mẫu cấu trúc con để cân bằng giữa độ chính xác và chi phí tính toán, đảm bảo hệ thống hoạt động ổn định và hiệu quả trong môi trường thực tế.

3. Phát triển công cụ tiền xử lý dữ liệu chuyên biệt cho tiếng Việt: Để nâng cao chất lượng biểu diễn dữ liệu và khai phá mẫu, cần xây dựng các công cụ xử lý ngôn ngữ tự nhiên phù hợp với đặc thù tiếng Việt, bao gồm tách từ, loại bỏ từ dừng và chuẩn hóa văn bản.

4. Mở rộng nghiên cứu áp dụng cho các loại văn bản khác: Ngoài thư điện tử, phương pháp khai phá dữ liệu đồ thị có thể được áp dụng cho các loại văn bản bán cấu trúc khác như tài liệu kinh doanh, báo cáo khoa học, giúp nâng cao khả năng quản lý và khai thác thông tin.

Đối tượng nên tham khảo luận văn

1. Các nhà nghiên cứu và sinh viên ngành công nghệ thông tin: Luận văn cung cấp kiến thức chuyên sâu về khai phá dữ liệu văn bản và kỹ thuật biểu diễn đồ thị, hỗ trợ phát triển các đề tài nghiên cứu liên quan.

2. Chuyên gia phát triển hệ thống quản lý email: Các kỹ thuật và mô hình phân loại được trình bày giúp cải tiến hệ thống lọc thư rác, phân loại thư tự động, nâng cao trải nghiệm người dùng.

3. Doanh nghiệp và tổ chức sử dụng lượng lớn email: Áp dụng phương pháp giúp tối ưu hóa quy trình xử lý thông tin, giảm thiểu chi phí nhân lực và tăng hiệu quả công việc.

4. Nhà phát triển phần mềm xử lý ngôn ngữ tự nhiên: Cung cấp cơ sở lý thuyết và thực nghiệm để phát triển các công cụ xử lý tiếng Việt, đặc biệt trong lĩnh vực khai phá dữ liệu và phân loại văn bản.

Câu hỏi thường gặp

1. Phương pháp khai phá dữ liệu đồ thị có ưu điểm gì so với phương pháp truyền thống?
   Phương pháp này khai thác được các đặc trưng cấu trúc phức tạp và mối quan hệ ngữ nghĩa trong văn bản, giúp phân loại chính xác hơn, đặc biệt với dữ liệu phi cấu trúc như thư điện tử.

2. Thuật toán Subdue hoạt động như thế nào trong việc phát hiện mẫu cấu trúc con?
   Subdue sử dụng beam search kết hợp tiêu chí MDL để tìm kiếm và lựa chọn các mẫu cấu trúc con có khả năng nén dữ liệu tốt nhất, từ đó phát hiện các mẫu lặp lại đặc trưng trong tập dữ liệu.

3. Làm thế nào để cân bằng giữa độ chính xác và thời gian xử lý khi áp dụng thuật toán?
   Điều chỉnh tham số beam width và kích thước mẫu cấu trúc con giúp cân bằng giữa độ chính xác và chi phí tính toán, tránh quá tải hệ thống trong xử lý dữ liệu lớn.

4. Phương pháp này có áp dụng được cho các ngôn ngữ khác ngoài tiếng Việt không?
   Có thể áp dụng cho các ngôn ngữ khác, tuy nhiên cần điều chỉnh công cụ tiền xử lý phù hợp với đặc thù ngôn ngữ để đảm bảo hiệu quả khai phá dữ liệu.

5. Làm sao để mở rộng ứng dụng của phương pháp này cho các loại văn bản khác?
   Bằng cách điều chỉnh biểu diễn đồ thị và thuật toán khai phá phù hợp với đặc điểm dữ liệu, phương pháp có thể áp dụng cho tài liệu kinh doanh, báo cáo khoa học, hoặc các văn bản bán cấu trúc khác.

Kết luận

• Luận văn đã xây dựng thành công mô hình phân loại thư điện tử tiếng Việt dựa trên kỹ thuật khai phá dữ liệu đồ thị, nâng cao độ chính xác phân loại lên khoảng 85-90%.
• Thuật toán Subdue được áp dụng hiệu quả trong việc phát hiện các mẫu cấu trúc con đặc trưng, giúp mô hình phân loại có khả năng nén dữ liệu và nhận diện lớp tốt hơn.
• Việc điều chỉnh tham số thuật toán như beam width và kích thước mẫu ảnh hưởng trực tiếp đến hiệu quả và chi phí tính toán, cần được cân nhắc kỹ lưỡng khi triển khai thực tế.
• Nghiên cứu mở ra hướng phát triển các hệ thống quản lý thông tin tự động, hỗ trợ xử lý lượng lớn thư điện tử và các văn bản phi cấu trúc khác.
• Các bước tiếp theo bao gồm phát triển công cụ tiền xử lý tiếng Việt chuyên biệt, thử nghiệm mở rộng trên các tập dữ liệu lớn hơn và đa dạng hơn, đồng thời ứng dụng trong các lĩnh vực quản lý thông tin khác.

Hành động khuyến nghị: Các tổ chức và nhà nghiên cứu nên áp dụng và tiếp tục phát triển phương pháp này để nâng cao hiệu quả quản lý và khai thác thông tin văn bản trong thời đại số.

Trích đoạn nội dung tài liệu

bé gi¸o dôc vµ ®µo t¹o Trêng ®¹i häc b¸ch khoa hµ néi ---------------------------------------- luËn v¨n th¹c sÜ khoa häc Ph©n lo¹i th ®iÖn tö b»ng kü thuËt khai ph¸ dùa trªn ®å thÞ ngµnh: c«ng nghÖ th«ng tin hoµng träng vinh Ngêi híng dÉn khoa häc: PGS. NguyÔn Thanh Thuû hµ néi 2005 17057205109541000000 - Trang 1 - Môc lôc Danh môc c¸c ch÷ viÕt t¾t. 3 Danh môc c¸c h×nh vÏ, ®å thÞ. 5 Ch¬ng I - tæng quan.

Khai ph¸ d÷ liÖu d¹ng v¨n b¶n:. Mét sè kh¸i niÖm c¬ b¶n trong xö lý v¨n b¶n:. Tõ kho¸, thuËt ng÷ vµ kh¸i niÖm:. Träng sè cña thuËt ng÷:.

§é liªn quan gi÷a c¸c v¨n b¶n:. Ph¬ng ph¸p biÓu diÔn v¨n b¶n theo m« h×nh kh«ng gian vector: 15 I. M« h×nh TÇn sè:. Ph¬ng ph¸p xö lý vector tha:.

Ph©n lo¹i th ®iÖn tö:. C¸c khã kh¨n, th¸ch thøc ®Æt ra:. Tr×nh bµy quan ®iÓm vµ ph¬ng ph¸p tiÕp cËn:. 23 Ch¬ng II - c¸c kü thuËt ph©n lo¹i truyÒn thèng.

Kü thuËt Ph©n lo¹i V¨n b¶n:. ThuËt to¸n Support Vector Machines (SVMs):. ThuËt to¸n c©y quyÕt ®Þnh (Decision Tree):. ThuËt to¸n k-NN (k - Nearest neighbor):.

Ph¬ng ph¸p Bayes ®¬n gi¶n ho¸:. Kü thuËt Ph©n lo¹i th ®iÖn tö:. Sù ph©n lo¹i dùa trªn c¸c qui t¾c:. Sù ph©n lo¹i dùa trªn c¬ së sù phôc håi th«ng tin:.

Ph©n lo¹i theo kü thuËt häc m¸y:. 36 Ch¬ng III - kü thuËt khai ph¸ dùa trªn ®å thÞ. HÖ thèng ph¸t hiÖn cÊu tróc con SUBDUE:.1 Ph¸t hiÖn cÊu tróc con:. 44 Hoµng Träng Vinh Ph©n lo¹i th ®iÖn tö b»ng kü thuËt khai ph¸ dùa trªn ®å thÞ - Trang 2 - 3.

§èi s¸nh ®å thÞ t¬ng ®èi:. Tham sè cho luång ®iÒu khiÓn:. 48 Ch¬ng 4 - HÖ thèng ph©n lo¹i th ®iÖn tö. BiÓu diÔn §å thÞ (Graph Representation):.

TrÝch xuÊt cÊu tróc con (substructure extraction):. Lîc bá cÊu tróc con ®¹i diÖn (Representative Substructure Pruning):. XÕp lo¹i cÊu tróc con ®¹i diÖn (Representative Substructure Ranking):. Sù Ph©n lo¹i (Classification):.

Qu¸ tr×nh tiÒn xö lý (Pre-processing):. C¸c ®Æc trng cña tiÕng ViÖt:. Ph©n t¸ch tõ trong tiÕng ViÖt dùa vµo tõ ®iÓn:. Lùa chän mÉu cho ®å thÞ ®Çu vµo:.

BiÓu diÔn §å thÞ (Graph Representation):. T¸c ®éng cña ®Æc trng líp (Impact of Folder Characteristics):. KÝch thíc trung b×nh th ®iÖn tö vµ gi¸ trÞ ngìng (Average email Size and Threshold). KÝch thíc trung b×nh cña th ®iÖn tö vµ folder so víi sè cÊu tróc con (Average email Size & Folder Size Vs Number of Substructures).

KÝch thíc chïm tia (Beam Size). KÝch thíc cÊu tróc con tèi thiÓu (Substructure Size VsMinsize). Lîc bá cÊu tróc con vµ xÕp h¹ng (Substructure Pruning and Ranking). KÕt qu¶ cµi ®Æt vµ thö nghiÖm:.

69 kÕt luËn vµ híng ph¸t triÓn tiÕp theo. Híng ph¸t triÓn cña luËn v¨n:. 75 Tµi liÖu tham kh¶o. 77 Hoµng Träng Vinh Ph©n lo¹i th ®iÖn tö b»ng kü thuËt khai ph¸ dùa trªn ®å thÞ - Trang 3 - Danh môc c¸c ch÷ viÕt t¾t STT Ch÷ viÕt t¾t ViÕt ®Çy ®ñ 1 HTML Hyper Text Markup Language 2 IDF Inverse Document frequency 3 k-NN k - Nearest neighbor 4 MDL Minimum Description Length Principle 5 SVMs Support Vector Machines 6 TF Term Frequency Hoµng Träng Vinh Ph©n lo¹i th ®iÖn tö b»ng kü thuËt khai ph¸ dùa trªn ®å thÞ - Trang 4 - Danh môc c¸c h×nh vÏ, ®å thÞ H×nh 1.

Chøc n¨ng truy vÊn cña trang web www. Chøc n¨ng dÉn ®êng v¨n b¶n trong trang web www. Siªu ph¼ng ph©n chia c¸c mÉu H×nh 2. Minh ho¹ viÖc khoanh vïng k v¨n b¶n gÇn nhÊt víi k = 5.

CÊu tróc ®å thÞ ban ®Çu H×nh 3. Më réng c¸c cÊu tróc con theo tÊt c¶ c¸c c¸ch cã thÓ H×nh 3. NÐn ®å thÞ b»ng c¸c cÊu tróc con t×m ®îc H×nh 3. C¸c cÊu tróc con t×m ®îc b»ng c¸ch më réng cÊu tróc con (a) H×nh 3.

Sö dông ®å thÞ con G’c ®Ó nÐn ®å thÞ ®Çu vµo G H×nh 3. TÖp ®Çu vµo cã néi dung lµ danh s¸ch c¸c ®Ønh vµ c¸c c¹nh t¬ng øng gi÷a chóng. BiÓu diÔn ®å thÞ ®Çu vµo trong hÖ thèng SubDue H×nh 3. §å thÞ con tèt nhÊt nhËn ®îc ë ®Çu ra cña hÖ thèng H×nh 3.

Tham sè ë ®Çu ra cña hÖ thèng SubDue H×nh 3. CÊu tróc con tèt nhÊt nhËn ®îc ë ®Çu ra cña hÖ thèng SubDue H×nh 3. BiÓu diÔn ®å thÞ con tèt nhÊt ë ®Çu ra hÖ thèng SubDue H×nh 4. HÖ thèng ph©n lo¹i th ®iÖn tö H×nh 4.

C¸c biÓu diÔn ®å thÞ H×nh 4. TÖp ®å thÞ ®Çu vµo H×nh 4. Mét th ®iÖn tö tiÕng ViÖt H×nh 4. Nguån tõ ®iÓn tiÕng ViÖt sö dông trong ch¬ng tr×nh H×nh 4.

TÖp c¸c ®å thÞ ®Çu vµo H×nh 4. KÕt qu¶ ®Çu ra cña hÖ thèng ph¸t hiÖn cÊu tróc ®å thÞ con H×nh 4. Mét th ®iÖn tö tiÕng ViÖt kh«ng dÊu Hoµng Träng Vinh Ph©n lo¹i th ®iÖn tö b»ng kü thuËt khai ph¸ dùa trªn ®å thÞ - Trang 5 - Më ®Çu Sù ph¸t triÓn vît bËc cña c«ng nghÖ th«ng tin – truyÒn th«ng nãi chung vµ Internet nãi riªng dÉn ®Õn kh¶ n¨ng chia sÎ, trao ®æi th«ng tin mét c¸ch nhanh chãng, chÝnh x¸c. Víi lîng th«ng tin, tri thøc khæng lå nhËn ®îc tõ Internet nãi chung vµ th ®iÖn tö (Email) nãi riªng, con ngêi ta kh«ng thÓ xö lý chóng b»ng ph¬ng ph¸p thñ c«ng mét c¸ch cã hiÖu qu¶.

Tõ ®ã n¶y sinh nhu cÇu vÒ xö lý th«ng tin v¨n b¶n mét c¸ch tù ®éng. 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 nãi chung vµ trong th ®iÖn tö nãi riªng trong c¸c phßng thÝ nghiÖm 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, th ®iÖn tö tiÕng Anh, tiÕng Ph¸p lµ 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, th ®iÖn tö tiÕng ViÖt.

Ngµy nay, viÖc trao ®æi th«ng tin, tri thøc tiÕng ViÖt qua Web, th ®iÖn tö lµ mét nhu cÇu tÊt yÕu kh«ng thÓ thiÕu ®îc, 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 nãi chung vµ th ®iÖn tö nãi riªng ®ang ®îc hÕt søc coi träng. Ph©n lo¹i v¨n b¶n lµ mét lÜnh vùc nghiªn cøu nh»m ph©n lo¹i c¸c tµi liÖu theo c¸c líp ®îc ®Þnh nghÜa tríc. C¸c líp ®îc ®Þnh nghÜa dùa vµo mét tËp c¸c tµi liÖu mÉu ®· ®îc ph©n lo¹i, ®îc sö dông ®Ó huÊn luyÖn. 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), thèng kª (Statistics),.

C¸c ph¬ng ph¸p nµy còng cã thÓ øng dông ®Ó ph©n lo¹i th ®iÖn tö vµ c¸c trang web. HÇu hÕt c¸c ph¬ng ph¸p nµy ®Òu rót ra c¸c tõ kho¸ hoÆc nh÷ng tõ thêng xuyªn xuÊt hiÖn mµ kh«ng ®Ó ý ®Õn sù liªn quan gi÷a c¸c tõ. Sù liªn quan gi÷a chóng rÊt quan träng, nã cã thÓ chØ ra sù liªn quan gi÷a c¸c tµi liÖu bªn trong mét líp. C¸c hÖ Hoµng Träng Vinh Ph©n lo¹i th ®iÖn tö b»ng kü thuËt khai ph¸ dùa trªn ®å thÞ - Trang 6 - thèng ph©n lo¹i x¸c ®Þnh c¸c mÉu kh¸c nhau nh»m ph©n lo¹i c¸c tµi liÖu t¬ng tù.

LuËn v¨n nµy ®Ò cËp ®Õn mét ph¬ng ph¸p ph©n lo¹i míi dùa trªn kü thuËt ®å thÞ. C¸ch tiÕp cËn cña chóng ta dùa trªn c¬ së c¸c cÊu tróc ®¹i diÖn hoÆc c¸c mÉu ®îc rót ra tõ c¸c th ®iÖn tö mÉu ®· ®îc ph©n lo¹i vµ sau ®ã cã thÓ sö dông ®Ó ph©n lo¹i c¸c th ®iÖn tö nhËn ®îc sau nµy. Trong c¸ch tiÕp cËn nµy, kh¸i niÖm ®èi s¸nh ®å thÞ t¬ng ®èi cã t¸c dông ®a ra c¸c cÊu tróc cã kh¶ n¨ng m« t¶ ®Æc ®iÓm néi dung cña mét líp th ®iÖn tö. Kh¶ n¨ng ph©n lo¹i dùa trªn sù t¬ng tù vµ kh«ng hoµn toµn chÝnh x¸c lµ rÊt quan träng trong sù ph©n lo¹i, gièng nh kh«ng bao giê cã hai mÉu hoµn toµn gièng nhau.

ý tëng míi nµy cã thÓ ¸p dông ®Ó ph©n lo¹i kh«ng nh÷ng v¨n b¶n mµ cßn réng r·i h¬n n÷a. Díi sù ®Þnh híng vµ híng dÉn tËn t×nh cña thÇy PGS. NguyÔn Thanh Thuû, t«i chän bµi to¸n xö lý cô thÓ ®Æt ra trong luËn v¨n nµy lµ Ph©n lo¹i th ®iÖn tö b»ng kü thuËt khai ph¸ dùa trªn ®å thÞ. Hoµng Träng Vinh Ph©n lo¹i th ®iÖn tö b»ng kü thuËt khai ph¸ dùa trªn ®å thÞ - Trang 7 - Ch¬ng I - tæng quan ViÖc qu¶n lý d÷ liÖu vµ th«ng tin ®· ®îc quan t©m víi nhu cÇu nh»m rót nh÷ng yÕu tè thiÕt yÕu vµ quan träng cña mét tµi liÖu vµ lu gi÷ nã ®Ó cã thÓ sù dông mét c¸ch cã hiÖu qu¶ sau nµy.

Sù cÇn thiÕt nµy gièng nh danh môc cña c¸c quyÓn s¸ch trong th viÖn, nã gióp ta nhanh chãng t×m ra quyÓn s¸ch mµ ta ®ang quan t©m. Trong mét quyÓn s¸ch, môc lôc ®Ó ta dÔ dµng x¸c ®Þnh ®îc môc ta cÇn. Internet chøa ®ùng mét lîng th«ng tin khæng lå. ViÖc x¸c ®Þnh c¸i g× lµ cÇn thiÕt cho ta lµ rÊt quan träng, nã gióp ta qu¶n lý c¸c th«ng tin mét c¸ch cã hiÖu qu¶ vµ lu tr÷ chóng ®Ó cã thÓ sö dông sau nµy.

Qu¶n lý th«ng tin ngµy nay cã mét ý nghÜa to lín gièng nh c«ng nghÖ th«ng tin ®· lµm mét cuéc c¸ch m¹ng trong d÷ liÖu vµ tri thøc lµ chia sÎ th«ng tin gi÷a mäi ngêi trªn ph¹m vi toµn cÇu. Mét khèi lîng th«ng tin khæng lå ngay lËp tøc cã thÓ nhËn ®îc th«ng qua viÖc truy cËp Internet. CÇn cã mét c¬ chÕ nh»m x¸c ®Þnh th«ng tin nµo lµ thÝch hîp cÇn ph¶i truy cËp. Mét c¸ch ®¬n gi¶n nhÊt lµ ta cã thÓ läc th«ng tin dùa vµo sù cã mÆt hoÆc kh«ng cã mÆt cña mét sè tõ kho¸ nhÊt ®Þnh.

Trong nh÷ng trêng hîp kh¸c cã thÓ x¸c ®Þnh thªm ng÷ c¶nh, thêi ®iÓm xuÊt hiÖn ®Ó cã thÓ läc ra nh÷ng th«ng tin phï hîp víi thêi ®iÓm. VÝ dô, nÕu cÇn rót ra tÊt c¶ c¸c th«ng tin vÒ ng«n ng÷ Java mµ chØ cung cÊp tõ kho¸ “Java” th× rÊt cã thÓ trong kÕt qu¶ ®a ra cã nhiÒu th«ng tin kh«ng thÝch hîp. VÊn ®Ò lµ ta ph¶i t×m c¸ch cung cÊp th«ng tin bæ sung ®Ó x¸c ®Þnh c¸i nµo lµ thÝch hîp. Trong mét trêng hîp kh¸c, qu¶n lý th«ng tin cã thÓ phøc t¹p nh viÖc tãm t¾t th«ng tin.

Mét c¬ chÕ kh¸c cho qu¶n lý th«ng tin lµ sù ph©n lo¹i, ®iÒu nµy cho phÐp ta ph©n lo¹i th«ng tin thµnh c¸c ph¹m trï kh¸c nhau tuú thuéc vµo sù quan t©m cña ngêi dïng.