ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Ngô Thương Huyền PHÂN LỚP THƯ ĐIỆN TỬ SỬ DỤNG MÁY VECTOR HỖ TRỢ LUẬN VĂN THẠC SĨ HÀ NỘI – 2007 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Ngô Thương Huyền MỤC LỤC PHÂN LỚP THƯ ĐIỆN TỬ SỬ DỤNG MÁY VECTOR HỖ TRỢ Ngành: Công nghệ thông tin Mã số: 1.10 LUẬN VĂN THẠC SĨ Người hướng dẫn khoa học: PGS. TS Hà Quang Thụy HÀ NỘI – 2007 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com MỤC LỤC Lời cảm ơn . ii Danh mục hình vẽ . iv Danh mục bảng biểu . vi MỞ ĐẦU . KHÁI QUÁT VỀ KHAI PHÁ DỮ LIỆU VĂN BẢN . Một số kiến thức về khai phá dữ liệu .1 Khái niệm khai phá dữ liệu .2 Các hướng tiếp cận và các dạng dữ liệu trong khai phá dữ liệu . Các bài toán trong khai phá dữ liệu văn bản .2 Phân lớp văn bản .3 Một số bài toán khác . Khai phá dữ liệu Web .3 Các hướng tiếp cận . PHÂN LỚP VĂN BẢN . Bài toán phân lớp .1 Nhu cầu, ý tưởng .2 Quá trình phân lớp . Các giải pháp phân lớp điển hình .1 Thuật toán phân lớp Bayes .2 Thuật toán k-người láng giềng gần nhất.3 Phân lớp dựa vào cây quyết định .4 Chiết lọc thông tin theo mô hình Markov ẩn . BỘ PHÂN LỚP SỬ DỤNG MÁY VECTOR HỖ TRỢ . 30 ii LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Biểu diễn văn bản dựa trên mô hình không quan vector.2 Mô hình Boolean .3 Mô hình tần số . Bộ phân lớp sử dụng vector hỗ trợ .1 Vector hỗ trợ.2 Thuật toán tạo siêu phẳng phân cách . ỨNG DỤNG VÀ THỰC NGHIỆM . Giới thiệu bài toán thực nghiệm . Dữ liệu và chương trình . Môi trường thực nghiệm . Kết quả thực nghiệm và đánh giá .1 Độ chính xác của bộ phân lớp khi thử nghiệm với tập kiểm tra 51 4.2 Độ chính xác của bộ phân lớp khi tăng dần tập dữ liệu học. 59 TÀI LIỆU THAM KHẢO . 57 iii LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Danh mục hình vẽ Hình 1. Lượng dữ liệu được tích lũy tăng mạnh theo thời gian Hình 2. Các bước trong quá trình khám phá tri thức Hình 3. Các nội dung trong khai phá Web Hình 4. Mô hình của bài toán phân lớp Hình 5. Mô hình học- phân tích một tập dữ liệu huấn luyện Hình 6. Mô hình phân lớp-đánh giá độ chính xác của mô hình Hình 7. Mối quan hệ giữa các siêu phẳng phân cách Hình 8. Biên giới của siêu phẳng phân cách Hình 9. Mô phỏng một điểm dữ liệu nhiễu Hình 10. Minh họa cho trường hợp tập dữ liệu không thể phân tách tuyến tính Hình 11. Một minh họa khác bằng ảnh khi ánh xạ sang không gian mới ta có thể phân tách tuyến tính tập dữ liệu Hình 12. Thực nghiệm với kiểu hàm nhân tuyến tính của người dùng Beck-s Hình 13. Đồ thị biểu diễn độ chính xác của bộ phân lớp SVM khi áp dụng các hàm nhân khác nhau Hình 14. Sử dụng svm-train để huấn luyện trên tập dữ liệu huấn luyện train_scale. Độ chính xác khi thử nghiệm trên tập kiểm tra của người dùng Becks Hình 16. Độ chính xác khi thử nghiệm trên tập kiểm tra của người dùng William-w3 Hình 17. Đồ thị biểu diễn độ chính xác của bộ phân lớp SVM khi thử nghiệm với tập kiểm tra. Quá trình học sử dụng svm-train Hình 19. Kết quả thực nghiệm khi tỉ lệ dữ liệu là 2:1 của người dùng Farmer iv LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Kết quả thực nghiệm khi tỉ lệ dữ liệu là 3:1 của người dùng Farmer Hình 21. Kết quả thực nghiệm khi tỉ lệ dữ liệu là 4:1 của người dùng Farmer Hình 22. Đồ thị biểu diễn độ chính xác của bộ phân lớp SVM với tỉ lệ dữ liệu Học/Kiểm tra tăng dần v LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Danh mục bảng biểu Bảng 1. Thống kê tập dữ liệu sử dụng Bảng 2. Thống kê tập dữ liệu thử nghiệm Bảng 3. Cấu hình máy tính Bảng 4. Độ chính xác của bộ phân lớp ứng với từng hàm nhân Bảng 5. Độ chính xác của bộ phân lớp khi thử nghiệm trên tập kiểm tra Bảng 6. Thống kê tập dữ liệu theo tỉ lệ phân chia dữ liệu học/dữ liệu kiểm tra Bảng 7. Độ chính xác của bộ phân lớp ứng với tỉ lệ phân chia dữ liệu vi LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com MỞ ĐẦU Ngày nay với sự phát triển như vũ bão của các ngành khoa học kỹ thuật, đặc biệt là sự phát triển nhanh chóng của mạng máy tính toàn cầu, một khối lượng dữ liệu khổng lồ vẫn hàng ngày được cập nhật liên tục, thường xuyên, nhằm đáp ứng một trong những nhu cầu không thể thiếu được của con người, đó là thông tin. Và vì thế chúng ta đang được sống trong một xã hội bùng nổ thông tin, khi các ứng dụng công nghệ thông tin đã đi vào tới từng lĩnh vực của đời sống xã hội. Trong đó Internet ngày càng khẳng định một sức mạnh vượt trội và đóng một vai trò quan trọng trong đời sống xã hội, kinh tế, chính trị, văn hoá, giáo dục… của con người. Cùng với sự phát triển không ngừng đó, Internet đã và đang trở thành một kho thông tin khổng lồ về cả số lượng cũng như sự biến đổi nhanh chóng của nó, theo ước đoán thì cứ sau hai năm lượng thông tin lại tăng thêm gấp đôi. Thư điện tử là một dịch vụ phổ biến nhất trên Internet, nó giúp cho mọi người sử dụng máy tính kết nối Internet đều có thể trao đổi thông tin với nhau. Ngày nay, khi mà Internet đã có mặt ở khắp mọi nơi thì việc sử dụng dịch vụ thư điện tử là việc hàng ngày đối với rất nhiều người trên khắp thế giới. Ta biết rằng khi mạng Internet ra đời, những người sử dụng đầu tiên là các chuyên gia máy tính, họ cùng gửi nhiều email đến các nhóm người dùng khác nhau, sau đó mới có tình trạng không thể kiểm soát được các email gửi đến. Vì vậy cần phải có các chương trình phân lớp các email theo thư mục người dùng hoặc lọc hay ngăn chặn những email mà người dùng không muốn nhận nhằm tăng chất lượng sử dụng. Trong lĩnh vực thư điện tử cá nhân, các kỹ thuật phân lớp văn bản cũng được áp dụng rất rộng rãi vào bài toán lọc thư rác. Một số vấn đề khác liên 1 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com quan đến thư điện tử như lọc các luồng thư điện tử, tự động tạo các thư mục mới cũng được nghiên cứu và giải quyết. Hiện nay, bài toán phân lớp thư điện tử vào các thư mục cũng đang được nhiều nhà nghiên cứu quan tâm. Trong luận văn này, chúng tôi ứng dụng phân lớp văn bản vào lĩnh vực thư điện tử nhằm giải quyết bài toán phân lớp tự động thư điện tử vào các lớp do người dùng định nghĩa. Lựa chọn thuật toán máy vector hỗ trợ (SVMs) với những ưu điểm và hiệu quả đã được chứng minh qua nhiều thực nghiệm về phân lớp văn bản, chúng tôi hy vọng SVMs có thể giải quyết các khó khăn của bài toán phân lớp email và đem lại kết quả khả quan. Luận văn được tổ chức thành 4 chương như sau: Chương 1 trình bày khái quát về khai phá dữ liệu, các kỹ thuật và hướng tiếp cận chính trong khai phá dữ liệu và phân loại các hệ thống khai phá theo nhiều tiêu chí khác nhau. Chương này cũng giới thiệu về các bài toán trong khai phá dữ liệu văn bản và khai phá dữ liệu Web. Chương 2 trình bày bài toán và quá trình phân lớp văn bản, đồng thời giới thiệu một số giải pháp phân lớp điển hình. Chương 3 giới thiệu phương pháp biểu diễn văn bản dựa trên mô hình không quan vector và tập trung nghiên cứu, khảo sát phương pháp máy vector hỗ trợ, đây là tiền đề để thực hiện việc thực nghiệm cho luận văn này. Chương 4 trình bày về mô hình phân lớp thư điện tử và áp dụng đối với một bộ dữ liệu đã được công bố. Từ các kết quả thực nghiệm, đưa ra đánh giá hệ thống phân lớp nói trên. 2 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com CHƢƠNG 1. KHÁI QUÁT VỀ KHAI PHÁ DỮ LIỆU VĂN BẢN 1. Một số kiến thức về khai phá dữ liệu 1.1 Khái niệm khai phá dữ liệu Trong những thập kỷ gần đây, lượng thông tin được lưu trữ trên các thiết bị điện tử (đĩa cứng, CD-ROM, băng từ, .) không ngừng tăng lên. Sự tích lũy dữ liệu này xảy ra với một tốc độ bùng nổ. Người ta ước đoán rằng, lượng thông tin trên toàn cầu tăng gấp đôi sau khoảng hai năm và theo đó số lượng cũng như kích cỡ của các cơ sở dữ liệu cũng tăng lên một cách nhanh chóng [5]. Hình 1 - Lượng dữ liệu được tích lũy tăng mạnh theo thời gian Chúng ta quả thực đang sở hữu một khối lượng dữ liệu khổng lồ, nhưng lại luôn cảm thấy thiếu những thông tin hữu ích. Lượng dữ liệu khổng lồ này thực sự là một nguồn “tài nguyên” rất giá trị bởi thông tin là yếu tố then chốt trong mọi hoạt động trước khi ra quyết định. Khai phá dữ liệu – khai thác những thông tin tiềm ẩn có tính dự đoán từ những cơ sở dữ liệu lớn – là một hướng tiếp cận mới với khả năng giúp các công ty chú trọng vào những thông tin có nhiều ý nghĩa từ những tập dữ liệu lớn (databases, data warehouses, data repositories) mang tính lịch sử. Những công cụ khai phá dữ liệu có thể dự đoán những xu hướng trong tương lai và do đó cho phép doanh nghiệp ra những quyết định kịp thời được định hướng bởi tri thức mà khai phá dữ liệu 3 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com đem lại. Sự phân tích dữ liệu một cách tự động và mang tính dự báo của khai phá dữ liệu có ưu thế hơn hẳn so với sự phân tích thông thường dựa trên những sự kiện trong quá khứ của các hệ hỗ trợ ra quyết định (Decision Support Systems - DSSs) truyền thống trước đây. Công cụ khai phá dữ liệu cũng có thể trả lời những câu hỏi trong lĩnh vực kinh doanh mà trước đây được xem là tốn nhiều thời gian để xử lý. Với tất cả những ưu thế trên, khai phá dữ liệu đã chứng tỏ được tính hữu dụng của nó trong môi trường kinh doanh đầy tính cạnh tranh ngày nay. Giờ đây, khai phá dữ liệu đã và đang trở thành một trong những hướng nghiên cứu chính của lĩnh vực khoa học máy tính và công nghệ tri thức.
Nghiên cứu phân lớp thư điện tử sử dụng máy vector hỗ trợ
Luận văn thạc sĩ VNU UET nghiên cứu phân lớp thư điện tử bằng máy vector hỗ trợ, mang lại giải pháp hiệu quả cho việc quản lý thông tin.
Trường đại học
Trường Đại học Công nghệ - Đại học Quốc gia Hà NộiChuyên ngành
Công nghệ thông tinNgười đăng
Ẩn danhThể loại
Luận văn thạc sĩPhí lưu trữ
30 PointMục lục chi tiết
THÔNG TIN CHI TIẾT
Tác giả: Ngô Thương Huyền
Người hướng dẫn: PGS. TS Hà Quang Thụy
Trường học: Trường Đại học Công nghệ - Đại học Quốc gia Hà Nội
Chuyên ngành: Công nghệ thông tin
Đề tài: Phân lớp thư điện tử sử dụng máy vector hỗ trợ
Loại tài liệu: Luận văn thạc sĩ
Năm xuất bản: 2007
Địa điểm: Hà Nội
Trích đoạn nội dung tài liệu
Nội dung được bảo vệ bản quyền — Tải xuống đầy đủ