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. 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com “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. 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, .), 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, .), 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,.
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,. Đồ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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Hình 2 - Các bước trong quá trình khám phá tri thức (KDD) 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),. 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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,. 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 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),.
Dữ liệu Text và Web (text database & www) 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Các bài toán trong khai phá dữ liệu văn bản 1. 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.