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

Luận văn phân loại thư điện tử hiệu quả sử dụng kỹ thuật khai phá dựa trên đồ thị. Tìm hiểu phương pháp mới, ưu điểm và ứng dụng thực tế.

• Tác giả: Hoang Trong 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: Công Nghệ Thông Tin
• Đề tài: Phân Loại Thư Đ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

Tóm tắt

I. Tổng Quan Luận Văn Phân Loại Thư Điện Tử Hiện Đại

Sự phát triển của Internet tạo ra lượng lớn thư điện tử, đòi hỏi xử lý tự động. Các phương pháp truyền thống tập trung vào từ khóa mà bỏ qua sự liên quan giữa chúng. Luận văn này giới thiệu phương pháp phân loại thư điện tử mới dựa trên kỹ thuật khai phá dữ liệu dựa trên đồ thị. Cách tiếp cận này sử dụng các cấu trúc đại diện, hay các mẫu, được rút ra từ các thư điện tử mẫu đã được phân loại. Các mẫu này sau đó được dùng để phân loại các thư điện tử mới. 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ử. Khai phá dữ liệu trở nên quan trọng để xử lý khối lượng thông tin khổng lồ này. Quản lý thông tin hiệu quả có ý nghĩa to lớn. Một cơ chế lọc thông tin đơn giản là dựa vào sự hiện diện của một số từ khóa. Tuy nhiên, cách này có thể cho ra kết quả không thích hợp. Sự phân loại cho phép phân loại thông tin thành các phạm trù khác nhau.

1.1. Bài toán Phân loại Văn bản và Phân loại Thư điện tử

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.

1.2. Khó khăn và Thách thức trong Phân loại Thư Việt

Các thành công chủ yếu tập trung vào việc 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ý. Rất ít công cụ được xây dựng thành công trong lĩnh vực xử lý văn bản, thư điện tử tiếng Việt. 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 coi trọng.

II. Cách Kỹ Thuật Phân Loại Thư Điện Tử Truyền Thống Hoạt Động

Các kỹ thuật phân loại truyền thống như Support Vector Machines (SVMs), cây quyết định, k-NN (k - Nearest neighbor), và phương pháp Bayes đơn giản hoá được sử dụng rộng rãi. Phân loại dựa trên các quy tắc và sự phục hồi thông tin cũng là các phương pháp tiếp cận phổ biến. Các phương pháp này thường tập trung vào trích xuất các từ khóa mà không chú trọng đến mối liên hệ giữa chúng. Sự liên quan giữa các từ 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. Sự khác biệt giữa các mẫu thường không hoàn toàn giống nhau, do đó cần có khả năng phân loại dựa trên sự tương tự.

2.1. Phân Loại Dựa trên Các Quy Tắc và Phục Hồi Thông Tin

Sự phân loại dựa trên các quy tắc sử dụng các luật được định nghĩa trước để gán nhãn cho các thư điện tử. Sự phân loại dựa trên cơ sở sự phục hồi thông tin tìm kiếm các tài liệu tương tự trong cơ sở dữ liệu đã được phân loại.

2.2. Ứng Dụng Học Máy trong Phân Loại Thư Điện Tử

Các thuật toán học máy như SVMs, Cây quyết định, k-NN, và Bayes được sử dụng để huấn luyện mô hình từ dữ liệu mẫu. Mô hình này sau đó được sử dụng để phân loại các thư điện tử mới.

2.3. Hạn Chế Của Phương Pháp Tiếp Cận Truyền Thống

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.

III. Kỹ Thuật Khai Phá Dữ Liệu Dựa Trên Đồ Thị Cách Tiếp Cận

Luận văn này đề xuất một phương pháp phân loại mới dựa trên kỹ thuật khai phá dữ liệu dựa trên đồ thị. Phương pháp này sử dụng hệ thống phát hiện cấu trúc con SUBDUE. Cách tiếp cận này dựa trên cơ sở các cấu trúc đại điệ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. 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ử.

3.1. Tổng Quan về Hệ Thống Phát Hiện Cấu Trúc Con SUBDUE

Hệ thống SUBDUE là một thuật toán khai phá dữ liệu dựa trên đồ thị. Nó được sử dụng để phát hiện các cấu trúc con phổ biến trong một tập dữ liệu đồ thị.

3.2. Đối sánh Đồ thị Tương đối Tìm Mẫu Đặc Trưng

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.

IV. Xây Dựng Hệ Thống Phân Loại Thư Điện Tử Dựa Trên Đồ Thị

Hệ thống phân loại thư điện tử dựa trên đồ thị bao gồm các bước chính: biểu diễn thư điện tử bằng đồ thị, trích xuất cấu trúc con, lược bỏ cấu trúc con đại diện, xếp loại cấu trúc con đại diện, xử lý thư điện tử đầu vào, và sự phân loại. Quá trình tiền xử lý bao gồm phân tách từ trong tiếng Việt. Các đặc trưng của tiếng Việt cần được xem xét để đảm bảo hiệu quả của hệ thống. Lựa chọn mẫu cho đồ thị đầu vào là một bước quan trọng.

4.1. Biểu diễn Thư Điện Tử thành Đồ thị

Mỗi thư điện tử được biểu diễn dưới dạng một đồ thị, trong đó các đỉnh đại diện cho các từ và các cạnh đại diện cho mối quan hệ giữa các từ.

4.2. Trích xuất Cấu Trúc Con và Lược Bỏ Cấu Trúc Không Quan Trọng

Hệ thống trích xuất các cấu trúc con từ đồ thị biểu diễn thư điện tử. Sau đó, các cấu trúc con không quan trọng sẽ được lược bỏ để giảm độ phức tạp của mô hình.

4.3. Xử Lý Tiền Xử Lý Cho Ngôn Ngữ Tiếng Việt

Các đặc trưng của tiếng Việt (ví dụ, sự phức tạp của việc phân tách từ) cần được xem xét để đảm bảo hiệu quả của hệ thống.

V. Thử Nghiệm và Đánh Giá Hệ Thống Phân Loại Thư Điện Tử

Luận văn trình bày kết quả cài đặt và thử nghiệm hệ thống phân loại thư điện tử. Các yếu tố như kích thước trung bình thư điện tử và giá trị ngưỡng, kích thước trung bình của thư điện tử và folder so với số cấu trúc con, kích thước chùm tia, kích thước cấu trúc con, và lược bỏ cấu trúc con và xếp hạng đều ảnh hưởng đến hiệu suất của hệ thống. Đánh giá mô hình sử dụng các bộ dữ liệu thư điện tử chuẩn để đo lường độ chính xác phân loại, hiệu suất phân loại và các chỉ số liên quan khác. Việc lựa chọn tính năng trích xuất phù hợp là rất quan trọng để cải thiện hiệu suất.

5.1. Ảnh Hưởng của Đặc Trưng Lớp và Kích Thước Thư Điện Tử

Kích thước trung bình thư điện tử và giá trị ngưỡng có ảnh hưởng đến hiệu suất của hệ thống. Tương tự, kích thước trung bình của thư điện tử và folder so với số cấu trúc con cũng ảnh hưởng đến hiệu suất.

5.2. Kết Quả Thực Nghiệm và Đánh Giá Hiệu Năng Hệ Thống

Luận văn trình bày kết quả cài đặt và thử nghiệm hệ thống phân loại thư điện tử. Các kết quả này được sử dụng để đánh giá hiệu năng của hệ thống.

VI. Kết Luận Hướng Phát Triển Kỹ Thuật Phân Loại Thư Điện Tử

Luận văn đã trình bày một phương pháp mới để phân loại thư điện tử sử dụng kỹ thuật khai phá dữ liệu dựa trên đồ thị. Hướng phát triển của luận văn bao gồm cải tiến phương pháp biểu diễn đồ thị, tối ưu hóa thuật toán khai phá dữ liệu, và thử nghiệm hệ thống trên các bộ dữ liệu thư điện tử lớn hơn. Các nghiên cứu tiếp theo có thể tập trung vào việc sử dụng các thuật toán học sâu (deep learning) và mạng nơ-ron (neural network) để cải thiện độ chính xác phân loại và hiệu suất phân loại. Phân tích cảm xúc thư điện tử (sentiment analysis email) cũng là một hướng nghiên cứu tiềm năng.

6.1. Tổng Kết Đóng Góp và Hạn Chế của Nghiên Cứu

Luận văn đã đóng góp một phương pháp mới để phân loại thư điện tử. Tuy nhiên, nghiên cứu vẫn còn một số hạn chế, chẳng hạn như yêu cầu về tài nguyên tính toán.

6.2. Các Hướng Nghiên Cứu và Phát Triển Tiềm Năng

Các hướng nghiên cứu và phát triển tiềm năng bao gồm cải tiến phương pháp biểu diễn đồ thị, sử dụng các thuật toán học sâu, và mở rộng hệ thống để hỗ trợ các ngôn ngữ khác.

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

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à Intemet 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, trí 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ý thong tin van bản một cách tự dộ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 Tĩ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, trí thức tiếng Việt qua Web, thư diện tử là một nhu cẩu tất yếu không thể thiếu dược, nhu cầu nghiên cửu và xây dựng các công cụ khai phá văn bản liếng Việt nói chung và thư điện tử nói riêng đang được hếi sức coi trong 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 Leaming}, 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ệ Hoang Trong Vink hân loại thư điện tử bằng kỹ thuật khai phá dựa trên đồ thị - Trang 7- CHUONG I- TONG QUAN Việc quản lý đữ liệu và thông tin đã được quan tâm với nhủ 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é su 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 đễ đằng xác định được mục ta cần. Intemet 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 ra là rất quan trọng, nó giúp ta quản lý các thông tin một cách có hiện quả và hm 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 xnạng trong dữ liệu và trí thức là chia sẻ thông tin giữa mọi người trên phạm ví 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. Can e6 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 them 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ả dưa ra cô nhiều thông tin không thích hợp. Vấn dễ là ta phải tìm cách cũng 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 lồ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 !a 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. Hoang Trong Vink hân loại thư điện tử bằng kỹ thuật khai phá dựa trên đồ thị ~ Trang 4 - : CAC HINH VE, DO THI Hinh 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.

l, 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'‹ để 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ệ thong SubDue Hình 3.10, 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 Phan loại thự điện tử bằng kỹ thuật khai phá dựa trên đồ thị - Trang 7- CHUONG I- TONG QUAN Việc quản lý đữ liệu và thông tin đã được quan tâm với nhủ 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é su 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 đễ đằng xác định được mục ta cần. Intemet 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 ra là rất quan trọng, nó giúp ta quản lý các thông tin một cách có hiện quả và hm 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 xnạng trong dữ liệu và trí thức là chia sẻ thông tin giữa mọi người trên phạm ví 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. Can e6 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 them 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ả dưa ra cô nhiều thông tin không thích hợp. Vấn dễ là ta phải tìm cách cũng 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 lồ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 !a 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. Hoang Trong Vink hân loại thư điện tử bằng kỹ thuật khai phá dựa trên đồ thị - Trang 9- 12. MỘT SỐ KHÁI NIỆM CƠ BẢN TRONG XỬ LÝ VĂN BẢN: "Trong xứ lý van bản nói chung và thư điện tử nói riêng có sử dụng một số thuật ngữ cần được làm rõ để tiện cho việc sử dụng sau này. Từ khuá, thuật ngữ và khái niệm: * Từ khoá (keyword): là các từ xuất hiện trong một văn bản ở dạng nguyên thể, có nghĩa trong từ điển.

Ví dụ với câu sau: “Chương trình khuyến mại tăng miễn phi modem ADSL tổ chức song song đồng thời với chương trình khuyến mại tặng 30% cước hoà mạng + 20% giá thiết bị modem đầu cuối”, các từ khoá có thể được tách ra là “Chương trinh”, “khuyển mại”, “miễn phỉ” “modem”, “ADSL”, “tổ chức”, “song song”, “đẳng thời”, “309”, “cước hoả mang”, “20%”, “pia”, “thiét bi”, “dầu cuối”. * Thuật ngữ (term): là các từ khoá có nghĩa liên quan đến 1uột lĩnh vực nào đó, ví dụ: "chuyển tiển nhanh", "tem thư", "điện thoại". Các thuật ngữ này thuộc về lĩnh vực "Bưu điện".4 cdc thuật ngữ nhưng nó là sự khái quát hoá, tổng, quát hoá của nhiều thuật ngữ khác. Ví dụ: khái niệm "máy tính" có thể chứa đựng các thuật ngữ khác "bàn phím", "chuột", "phần cứng", "phẩn mềm", "CPU", "ổ cứng", Internet", "màn hình”, "số hoá”,.

các từ này có một phần liên quan đến khái niệm "máy tính". Một khái niệm thường liên quan đến một dãy các thuật ngữ với mức độ khác nhau. Ví đụ: thuật ngữ "phần mềm" có mức độ liên quan đến khái niệm “tin học" nhiều hơn so với thuật ngữ số hod". Một tiêu chuẩn để xem xét mức độ liên quan là xác xuất đổng xuất hiện của cặp khái niệm - thuật ngữ trong các văn bản.

Khi thuật ngữ "ruáy tính" xuất hiện nhiều trong các văn bản chứa thuật ngữ "tin lọc" đủ có nghĩa là độ liên quan gitta cap "tin hoe” - “indy unk" cằng cao Một lý do để giải thích suy luận này là mức độ thay thế, ở dây, không chỉ hiểu đơn thuần giống như sự thay thé | - I giữa hai từ (ví dụ: "loài Hoang Trong Vink hân loại thư điện tử bằng kỹ thuật khai phá dựa trên đồ thị - Trang- 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à Intemet 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.