Tài liệu Phân lớp thư điện tử sử dụng máy vector hỗ trợ

ĐẠ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 ĐẠ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.01.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 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 ................................................................................................... 1 Chương 1. KHÁI QUÁT VỀ KHAI PHÁ DỮ LIỆU VĂN BẢN ............... 3 1.1. Một số kiến thức về khai phá dữ liệu ............................................... 3 1.1.1 Khái niệm khai phá dữ liệu ........................................................ 3 1.1.2 Các hướng tiếp cận và các dạng dữ liệu trong khai phá dữ liệu .. 6 1.2. Các bài toán trong khai phá dữ liệu văn bản .................................... 8 1.2.1 Tìm kiếm văn bản ...................................................................... 8 1.2.2 Phân lớp văn bản ....................................................................... 9 1.2.3 Một số bài toán khác ................................................................ 11 1.3. Khai phá dữ liệu Web .................................................................... 11 1.3.1 Nhu cầu ................................................................................... 11 1.3.2 Đặc điểm ................................................................................. 13 1.3.3 Các hướng tiếp cận .................................................................. 15 Chương 2. PHÂN LỚP VĂN BẢN .......................................................... 17 2.1. Bài toán phân lớp ........................................................................... 17 2.1.1 Nhu cầu, ý tưởng ..................................................................... 17 2.1.2 Quá trình phân lớp ................................................................... 18 2.2. Các giải pháp phân lớp điển hình ................................................... 20 2.2.1 Thuật toán phân lớp Bayes ....................................................... 20 2.2.2 Thuật toán k-người láng giềng gần nhất. .................................. 22 2.2.3 Phân lớp dựa vào cây quyết định ............................................. 23 2.2.4 Chiết lọc thông tin theo mô hình Markov ẩn ............................ 26 Chương 3. BỘ PHÂN LỚP SỬ DỤNG MÁY VECTOR HỖ TRỢ .......... 30 ii 3.1. Biểu diễn văn bản dựa trên mô hình không quan vector................. 30 3.1.1 Giới thiệu................................................................................. 30 3.1.2 Mô hình Boolean ..................................................................... 32 3.1.3 Mô hình tần số ......................................................................... 33 3.2. Bộ phân lớp sử dụng vector hỗ trợ ................................................. 34 3.2.1 Vector hỗ trợ............................................................................ 34 3.2.2 Thuật toán tạo siêu phẳng phân cách ........................................ 35 Chương 4. ỨNG DỤNG VÀ THỰC NGHIỆM ........................................ 42 4.1. Giới thiệu bài toán thực nghiệm ..................................................... 44 4.2. Dữ liệu và chương trình ................................................................. 44 4.3. Môi trường thực nghiệm ................................................................ 50 4.4. Kết quả thực nghiệm và đánh giá ................................................... 51 4.4.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.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...... 56 KẾT LUẬN .............................................................................................. 59 TÀI LIỆU THAM KHẢO ........................................................................ 57 iii 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.tr Hình 15. Độ 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. Hình 18. 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 Hình 20. 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 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 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 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 CHƢƠNG 1. KHÁI QUÁT VỀ KHAI PHÁ DỮ LIỆU VĂN BẢN 1.1. Một số kiến thức về khai phá dữ liệu 1.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ừ, ...v.v.) 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 đ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. a) Định nghĩa Khai phá dữ liệu Có thể hiểu một cách sơ lược rằng khai phá dữ liệu là quá trình tìm kiếm những thông tin (tri thức) hữu ích, tiềm ẩn và mang tính dự báo trong các tập dữ liệu lớn. Như vậy, các nhà khoa học cho rằng nên gọi quá trình này là khám phá tri thức (Knowledge Discovery in Databases – KDD) thay vì là khai phá dữ liệu. Tuy nhiên các nhà khoa học trong lĩnh vực này đồng ý với nhau rằng hai thuật ngữ trên là tương đương và có thể thay thế cho nhau. Họ lý giải rằng, mục đích chính của quá trình khám phá tri thức là thông tin và tri thức có ích, nhưng đối tượng mà cần phải xử lý rất nhiều trong suốt quá trình đó lại chính là dữ liệu. Mặt khác, khi chia các bước trong quá trình khám phá tri thức, một số nhà nghiên cứu lại cho rằng, khai phá dữ liệu chỉ là một bước trong quá trình khám phá tri thức [21]. Như vậy, khi xét ở mức tổng quan thì hai thuật ngữ này là tương đương nhau, nhưng khi xét cụ thể thì khai phá dữ liệu được xem là một bước trong quá trình khám phá tri thức. 4 “Khai phá dữ liệu được định nghĩa như quá trình chắt lọc hay khám phá tri thức từ một lượng lớn dữ liệu” (J. Han và M. Kamber [10]). b) Các bước chính trong Khám phá tri thức (KDD) Người ta thường chia quá trình khám phá tri thức thành các bước sau [5][10][12]:  Trích chọn dữ liệu (data selection): là bước trích chọn những tập dữ liệu cần được khai phá từ các tập dữ liệu lớn (databases, data warehouses, data repositories) ban đầu theo một số tiêu chí nhất định.  Tiền xử lý dữ liệu (data preprocessing): là bước làm sạch dữ liệu (xử lý với dữ liệu không đầy đủ, dữ liệu nhiễu, dữ liệu không nhất quán, ...v.v.), rút gọn dữ liệu (sử dụng hàm nhóm và tính tổng, các phương pháp nén dữ liệu, sử dụng histograms, lấy mẫu, ...v.v.), rời rạc hóa dữ liệu (rời rạc hóa dựa vào histograms, dựa vào entropy, dựa vào phân khoảng, ...v.v.). Sau bước này, dữ liệu sẽ nhất quán, đầy đủ, được rút gọn, và được rời rạc hóa.  Biến đổi dữ liệu (data transformation): đây là bước chuẩn hóa và làm mịn dữ liệu để đưa dữ liệu về dạng thuận lợi nhất nhằm phục vụ cho các kỹ thuật khai phá ở bước sau.  Khai phá dữ liệu (data mining): đây là bước áp dụng những kỹ thuật khai phá (phần nhiều là các kỹ thuật của machine learning) để khai phá, trích chọn được những mẫu (patterns) thông tin, những mối liên hệ (relationships) đặc biệt trong dữ liệu. Đây được xem là bước quan trọng và tốn nhiều thời gian nhất của toàn quá trình khai phá dữ liệu.  Biểu diễn và đánh giá tri thức (knowledge representation & evaluation): những mẫu thông tin và mối liên hệ trong dữ liệu đã được khai phá ở bước trên được chuyển dạng và biểu diễn ở một dạng gần gũi với người sử dụng như đồ thị, cây, bảng biểu, luật, ...v.v. Đồng thời bước này cũng đánh giá những tri thức khám phá được theo những tiêu chí nhất định. 5 Hình 2 - Các bước trong quá trình khám phá tri thức (KDD) 1.1.2 Các hướng tiếp cận và các dạng dữ liệu trong Khai phá dữ liệu a) Các hướng tiếp cận Khai phá dữ liệu tuy là một hướng tiếp cận mới nhưng thu hút được rất nhiều sự quan tâm của các nhà nghiên cứu và phát triển nhờ vào những ứng dụng thực tiễn của nó. Phạm vi ứng dụng ban đầu của nó chỉ là trong lĩnh vực thương mại (bán lẻ) và tài chính (thị trường chứng khoán). Nhưng ngày nay đã được ứng dụng rộng rãi trong rất nhiều những lĩnh vực khác nhau. Hướng tiếp cận của khai phá dữ liệu có thể được phân chia theo chức năng hay phân chia theo lớp các bài toán khác nhau. Sau đây là một số hướng tiếp cận chính[10]:  Phân lớp và dự đoán (classification & prediction): xếp một đối tượng vào một trong những lớp đã biết trước. Ví dụ: phân lớp vùng địa lý theo dữ liệu thời tiết. Hướng tiếp cận này thường sử dụng một số kỹ thuật của machine learning như cây quyết định (decision tree), mạng nơron nhân tạo (neural network), ...v.v. Phân lớp còn được gọi là học có giám sát (học có thầy – supervised learning). 6  Mô tả khái niệm (concept description): thiên về mô tả, tổng hợp và tóm tắt khái niệm. Ví dụ: tóm tắt văn bản.  Luật kết hợp (association rules): là dạng luật biểu diễn tri thức ở dạng khá đơn giản. Ví dụ: “50% số tội phạm giết người là nhằm mục đích cướp của”. Luật kết hợp được ứng dụng nhiều trong lĩnh vực kinh doanh, y học, tin-sinh, tài chính và thị trường chứng khoán, ...v.v.  Khai phá chuỗi theo thời gian (sequential/temporal patterns): tương tự như khai phá luật kết hợp nhưng có thêm tính thứ tự và tính thời gian. Hướng tiếp cận này được ứng dụng nhiều trong lĩnh vực tài chính và thị trường chứng khoán vì nó có tính dự báo cao.  Phân cụm (clustering/segmentation): xếp các đối tượng theo từng cụm (số lượng cũng như tên của cụm chưa được biết trước). Phân cụm còn được gọi là học không giám sát (học không có thầy – unsupervised learning). b) Các dạng dữ liệu có thể khai phá Do khai phá dữ liệu được ứng dụng rộng rãi nên nó có thể làm việc với rất nhiều kiểu dữ liệu khác nhau[10]. Sau đây là một số kiểu dữ liệu điển hình:  CSDL quan hệ (relational databases)  CSDL đa chiều (multidimensional structures, data warehouses)  CSDL dạng giao dịch (transactional databases)  CSDL quan hệ - hướng đối tượng (object-relational databases)  Dữ liệu không gian và thời gian (spatial and temporal data)  Dữ liệu chuỗi thời gian (time-series data)  CSDL đa phương tiện (multimedia databases) như âm thanh (audio), hình ảnh (image), phim ảnh (video), .v.v.  Dữ liệu Text và Web (text database & www) 7 1.2. Các bài toán trong khai phá dữ liệu văn bản 1.2.1. Tìm kiếm văn bản a. Nội dung Tìm kiếm văn bản là quá trình tìm kiếm văn bản theo yêu cầu của người dùng. Các yêu cầu được thể hiện dưới dạng các câu hỏi (query), dạng câu hỏi đơn giản nhất là các từ khóa. Có thể hình dung hệ tìm kiếm văn bản sắp xếp văn bản thành hai lớp: Một lớp cho ra những các văn bản thỏa mãn với câu hỏi đưa ra và một lớp không hiển thị những văn bản không được thỏa mãn. Các hệ thống thực tế hiện nay không hiển thị như vậy mà đưa ra các danh sách văn bản theo độ quan trọng của văn bản tuỳ theo các câu hỏi đưa vào, ví dụ điển hình là các máy tìm tin như Google, Altavista,… b. Quá trình tìm kiếm Quá trình tìm tin được chia thành bốn quá trình chính : Đánh chỉ số (indexing): Các văn bản ở dạng thô cần được chuyển sang một dạng biểu diễn nào đó để xử lý. Quá trình này còn được gọi là quá trình biểu diễn văn bản, dạng biểu diễn phải có cấu trúc và dễ dàng khi xử lý. Định dạng câu hỏi: Người dùng phải mô tả những yêu cầu về lấy thông tin cần thiết dưới dạng câu hỏi. Các câu hỏi này phải được biểu diễn dưới dạng phổ biến cho các hệ tìm kiếm như nhập vào các từ khóa cần tìm. Ngoài ra còn có các phương pháp định dạng câu hỏi dưới dạng ngôn ngữ tự nhiên hoặc dưới dạng các ví dụ, đối với các dạng này thì cần có các kỹ thuật xử lý phức tạp hơn. Trong các hệ tìm tin hiện nay thì đại đa số là dùng câu hỏi dưới dạng các từ khóa. So sánh: Hệ thống phải có sự so sánh rõ ràng và hoàn toàn câu hỏi các câu hỏi của người dùng với các văn bản được lưu trữ trong cơ sở dữ liệu. Cuối cùng hệ đưa ra một quyết định phân loại các văn bản có độ liên quan 8 gần với câu hỏi đưa vào và thứ tự của nó. Hệ sẽ hiển thị toàn bộ văn bản hoặc chỉ một phần văn bản. Phản hồi: Nhiều khi kết quả được trả về ban đầu không thỏa mãn yêu cầu của người dùng, do đó cần phải có quá trình phản hồi để người dùng có thể thay đổi lại hoặc nhập mới các yêu cầu của mình. Mặt khác, người dùng có thể tương tác với các hệ về các văn bản thỏa mãn yêu cầu của mình và hệ có chức năng cập nhật các văn bản đó. Quá trình này được gọi là quá trình phản hồi liên quan (Relevance feeback). Các công cụ tìm kiếm hiện nay chủ yếu tập trung nhiều vào ba quá trình đầu, còn phần lớn chưa có quá trình phản hồi hay xử lý tương tác người dùng và máy. Quá trình phản hồi hiện nay đang được nghiên cứu rộng rãi và riêng trong quá trình tương tác giao diện người máy đã xuất hiện hướng nghiên cứu là interface agent. 1.2.2. Phân lớp văn bản a. Nội dung Phân lớp văn bản được xem như là quá trình gán các văn bản vào một hay nhiều văn bản đã xác định từ trước. Người ta có thể phân lớp các văn bản một cách thủ công, tức là đọc từng văn bản một và gán nó vào một lớp nào đó. Cách này sẽ tốn rất nhiều thời gian và công sức đối với nhiều văn bản và do đó không khả thi. Do vậy mà phải có các phương pháp phân lớp tự động. Để phân lớp tự động người ta sử dụng các phương pháp học máy trong trí tuệ nhân tạo (Cây quyết định, Bayes, k-người láng giềng gần nhất...). Một trong những ứng dụng quan trọng nhất của phân lớp văn bản là trong tìm kiếm văn bản. Từ một tập dữ liệu đã phân lớp, các văn bản sẽ được đánh chỉ số đối với từng lớp tương ứng. Người dùng có thể xác định chủ đề hoặc phân lớp văn bản mà mình mong muốn tìm kiếm thông qua các câu hỏi. 9 Một ứng dụng khác của phân lớp văn bản là trong lĩnh vực tìm hiểu văn bản. Phân lớp văn bản có thể được sử dụng để lọc các văn bản hoặc một phần các văn bản chứa dữ liệu cần tìm mà không làm mất đi tính phức tạp của ngôn ngữ tự nhiên. Trong phân lớp văn bản, một lớp có thể được gán giá trị đúng, sai (True hay False hoặc văn bản thuộc hay không thuộc lớp) hoặc được tính theo mức độ phụ thuộc (văn bản có một mức độ phụ thuộc vào lớp). Trong trường hợp có nhiều lớp thì phân loại đúng, sai sẽ là việc xem một văn bản có thuộc vào một lớp duy nhất nào đó hay không. b. Quá trình phân lớp Quá trình phân lớp văn bản tuân theo các bước sau: Đánh chỉ số (Indexing): Quá trình đánh chỉ số văn bản cũng giống như trong quá trình đánh chỉ số của tìm kiếm văn bản. Trong phần này thì tốc độ đánh chỉ số đóng vai trò quan trọng vì một số các văn bản mới có thể cần được xử lý trong thời gian thực. Xác định độ phân lớp: Cũng giống như trong tìm kiếm văn bản, phân lớp văn bản yêu cầu quá trình diễn tả việc xác định văn bản đó thuộc lớp nào đó như thế nào, dựa trên cấu trúc biểu diễn của nó. Đối với hệ phân lớp văn bản, quá trình này do bộ phân lớp (classifier) thực hiện. Bộ phân lớp đóng vai trò như hệ trả lời câu hỏi trong hệ tìm kiếm. Nhưng trong khi các hệ trả lời câu hỏi mang tính nhất thời, thì bộ phân lớp được sử dụng một cách ổn định và lâu dài cho quá trình phân lớp. So sánh: Trong hầu hết các bộ phân loại, mỗi văn bản đều được yêu cầu gán đúng, sai vào một lớp nào đó. Sự khác nhau lớn nhất đối với quá trình so sánh trong hệ tìm kiếm văn bản là mỗi văn bản chỉ được so sánh với một số lượng các lớp một lần và việc chọn quyết định phù hợp còn phụ thuộc vào mối quan hệ giữa các lớp văn bản. 10 Phản hồi (Hay thích nghi): Quá trình phản hồi đóng vai trò trong hệ phân lớp văn bản. Thứ nhất là khi phân loại thì phải có một số lượng lớn các văn bản đã được xếp loại bằng tay trước đó, các văn bản này được sử dụng làm mẫu huấn luyện để hỗ trợ xây dựng bộ phân loại. Thứ hai là đối với việc phân loại văn bản này không dễ dàng thay đổi các yêu cầu như trong quá trình phản hồi của tìm kiếm văn bản, người dùng có thể thông tin cho người bảo trì hệ thống về việc xóa bỏ, thêm vào hoặc thay đổi các phân lớp văn bản nào đó mà mình yêu cầu. 1.2.3. Một số bài toán khác Ngoài hai bài toán kể trên, còn có các bài toán sau:  Tóm tắt văn bản  Phân cụm văn bản  Phân cụm các từ mục  Phân lớp các từ mục  Đánh chỉ mục các từ tiềm năng  Dẫn đường văn bản 1.3. Khai phá dữ liệu Web 1.3.1. Nhu cầu Sự phát triển nhanh chóng của mạng Internet và Intranet đã sinh ra một khối lượng khổng lồ các dữ liệu dạng siêu văn bản (dữ liệu Web). Cùng với sự thay đổi và phát triển hàng ngày hàng giờ về nội dung cũng như số lượng của các trang Web trên Internet thì vấn đề tìm kiếm thông tin đối với người sử dụng lại ngày càng khó khăn. Có thể nói nhu cầu tìm kiếm thông tin trên một cơ sở dữ liệu phi cấu trúc đã được phát triển chủ yếu cùng với sự phát triển của Internet. Thực vậy, với Internet con người đã làm quen với các trang Web cùng với vô vàn các thông tin. Trong những năm gần đây Internet đã trở thành một trong những kênh về khoa học, thông tin kinh tế, thương mại 11 và quảng cáo. Một trong những lý do cho sự phát triển này là giá cả tiêu tốn khi công khai một trang Web trên Internet là khá thấp. So sánh với những dịch vụ khác như phát tờ rơi hay quảng cáo trên một tờ báo hay tạp chí, thì một trang Web rẻ hơn rất nhiều và cập nhật nhanh chóng hơn tới hàng triệu người dùng khắp mọi nơi trên thế giới. Có thể nói trang Web như là cuốn từ điển Bách khoa toàn thư. Thông tin trên các trang Web đa dạng về mặt nội dung cũng như hình thức. Có thể nói Internet như một xã hội ảo, nó bao gồm các thông tin về mọi mặt của đời sống kinh tế, xã hội được trình bày dưới dạng văn bản, âm thanh, hình ảnh... Tuy nhiên, cùng với sự đa dạng và số lượng lớn thông tin như vậy đã nảy sinh vấn đề quá tải thông tin. Người ta không thể tìm tự kiếm địa chỉ trang Web chứa thông tin mà mình cần, do vậy đòi hỏi cần phải có một trình tiện ích quản lý nội dung của các trang Web và cho phép tìm thấy các địa chỉ trang Web có nội dung giống với yêu cầu của người tìm kiếm. Các tiện ích này quản lý dữ liệu như các đối tượng phi cấu trúc. Hiện nay, người sử dụng rất quen thuộc với không ít các tiện ích như vậy đó là: Yahoo, Google, Alvista, v.v... Mặt khác, giả sử chúng ta có các trang Web về các vấn đề Tin học, Thể thao, Kinh tế - Xã hội và Xây dựng... Căn cứ vào nội dung của các tài liệu mà khách hàng xem hoặc download về, sau khi phân lớp, chúng ta sẽ biết khách hàng hay tập trung vào nội dung gì trên trang Web của chúng ta, từ đó chúng ta sẽ bổ sung thêm nhiều các tài liệu về các nội dung mà khách hàng quan tâm và ngược lại. Còn về phía khách hàng sau khi phân tích, chúng ta cũng biết được khách hàng hay tập trung về vấn đề gì, để từ đó có thể đưa ra những hỗ trợ thêm cho khách hàng đó. Từ những nhu cầu thực tế trên, phân lớp và khai phá Web vẫn là bài toán hay và cần tiếp tục phát triển, nghiên cứu. 12 1.3.2. Đặc điểm Hệ thống phục vụ World Wide Web như là một hệ thống trung tâm rất lớn, phân bố rộng, cung cấp thông tin trên mọi lĩnh vực khoa học, chính trị, xã hội, thương mại, kinh tế, văn hóa, giáo dục... Web là một nguồn tài nguyên giàu có cho Khai phá dữ liệu. a) Web dường như quá lớn để tổ chức thành một kho dữ liệu phục vụ Datamining Các cơ sở dữ liệu truyền thống thì có kích thước không lớn lắm và thường được lưu trữ ở một nơi. Trong khi đó kích thước Web rất lớn, tới hàng terabytes và thay đổi liên tục, không những thế còn phân tán trên rất nhiều máy tính khắp nơi trên thế giới. Một vài nghiên cứu về kích thước của Web đã đưa ra các số liệu như sau: Hiện nay trên Internet có khoảng hơn một tỷ các trang Web được cung cấp cho người sử dụng, giả sử kích thước trung bình của mỗi trang là 5-10Kb thì tổng kích thước của nó ít nhất là khoảng 10 terabyte. Còn tỷ lệ tăng của các trang Web thì thật sự gây ấn tượng. Hai năm gần đây số các trang Web tăng gấp đôi và còn tiếp tục tăng trong các năm tới. Nhiều tổ chức và xã hội đặt hầu hết những thông tin công cộng của họ lên Web. Như vậy việc xây dựng một kho dữ liệu (datawarehouse) để lưu trữ, sao chép hay tích hợp các dữ liệu trên Web là gần như không thể. b) Độ phức tạp của trang Web lớn hơn rất nhiều so với những tài liệu văn bản truyền thống khác Các dữ liệu trong các cơ sở dữ liệu truyền thống thì thường là loại dữ liệu đồng nhất (về ngôn ngữ, định dạng,…), còn dữ liệu Web thì hoàn toàn không đồng nhất. Ví dụ về ngôn ngữ dữ liệu Web bao gồm rất nhiều loại ngôn ngữ khác nhau (Cả ngôn ngữ diễn tả nội dung lẫn ngôn ngữ lập trình), nhiều loại định dạng khác nhau (Text, HTML, PDF, hình ảnh, âm thanh,…), nhiều 13