Tài liệu Bui phuoc trung

BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KHOA HỌC BÙI PHƯỚC TRUNG TÌM HIỂU MỘT SỐ PHƯƠNG PHÁP PHÂN LỚP DỮ LIỆU KHÔNG PHÂN CẤP LUẬN VĂN THẠC SĨ KHOA HỌC CÔNG NGHỆ THÔNG TIN Thừa Thiên Huế, 2016 BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC HUẾ TRƯỜNG ĐẠI HỌC KHOA HỌC BÙI PHƯỚC TRUNG TÌM HIỂU MỘT SỐ PHƯƠNG PHÁP PHÂN LỚP DỮ LIỆU KHÔNG PHÂN CẤP CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH MÃ SỐ: 60.48.01.01 LUẬN VĂN THẠC SĨ KHOA HỌC ĐỊNH HƯỚNG NGHIÊN CỨU NGƯỜI HƯỚNG DẪN KHOA HỌC TS. HOÀNG THỊ LAN GIAO Thừa Thiên Huế, 2016 LỜI CAM ĐOAN Tôi xin cam đoan những kết quả đươ ̣c trình bày trong luận văn này là của riêng tôi, không sao chép từ bất kỳ một công trình nào khác. Nếu có điều gì không trung thực, tôi xin chịu hoàn toàn trách nhiệm. Ho ̣c viên Bùi Phước Trung LỜI CẢM ƠN Đầu tiên, tôi xin chân thành cảm ơn cô Hoàng Thị Lan Giao, mặc dù rất bận rộn trong công việc nhưng cô luôn quan tâm giúp đỡ, chỉ bảo kịp thời và đã tận tình hướng dẫn tôi hoàn thành luận văn này. Tôi xin gởi lời cảm ơn Quý thầy cô trong Khoa Công nghệ thông tin Trường Đại học Khoa học Huế, đã cung cấp, truyền đạt kiến thức cho tôi trong suốt quá trình học tập tại trường. Xin chân thành cảm ơn các anh chị em lớp cao học Khoa học máy tính khóa 2014 – 2016 và các bạn bè đã luôn bên cạnh, động viên, khuyến khích trong suốt thời gian học tập và thực hiện đề tài. Cuối cùng, tôi đặc biệt gửi lời cảm ơn đến gia đình, gia đình là điểm tựa vật chất và tinh thần lớn nhất giúp tôi yên tâm học tập tốt. Xin chân thà nh cả m ơn! Huế , ngà y 27 thá ng 6 năm 2016 Ho ̣c viên Bùi Phước Trung MỤC LỤC Lờ i cam đoan ............................................................................................................... Lờ i cả m ơn ................................................................................................................... Mục lục ......................................................................................................................... Danh mu ̣c các thuật ngữ............................................................................................. Danh mu ̣c ký hiêu........................................................................................................ ̣ Danh sá ch cá c hı̀nh vẽ................................................................................................. MỞ ĐẦU .................................................................................................................... 1 Chương 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ PHÂN CỤM DỮ LIỆU ........................................................................................................................... 4 1.1. TỔNG QUAN KHAI PHÁ DỮ LIỆU............................................................. 4 1.1.1. Khái niệm về khai phá dữ liệu ............................................................... 4 1.1.2. Các loại dữ liệu có thể khai phá ............................................................. 7 1.1.3. Quá trı̀nh khá m phá tri thứ c ................................................................... 7 1.2. CÁC KỸ THUẬT TRONG KHAI PHÁ DỮ LIỆU........................................ 9 1.3. CÁC MÔ HÌNH PHÂN CỤM/PHÂN LỚP DỮ LIỆU ................................. 10 1.3.1. Khái niệm về phân cụm/phân lớp dữ liệu ............................................ 10 1.3.2. Mục tiêu của phân cụm/lớp dữ liệu...................................................... 11 1.3.3. Các mô hình phân lớp .......................................................................... 13 1.4. YÊU CẦU VÀ NHỮNG VẤN ĐỀ CÒN TỒN TẠI TRONG PHÂN CỤM DỮ LIỆU .............................................................................................................. 19 1.4.1. Các yêu cầu của phân cụm dữ liệu....................................................... 19 1.4.2. Những vấn đề còn tồn tại trong phân cụm dữ liệu ............................... 21 1.5. CÁC ỨNG DỤNG CỦA PHÂN CỤM DỮ LIỆU ........................................ 22 1.6. TIỂU KẾT CHƯƠNG 1 ................................................................................ 22 Chương 2. MỘT SỐ THUẬT TOÁN PHÂN LỚP DỮ LIỆU TRÊN HỆ THỐNG THÔNG TIN............................................................................................ 23 2.1. THUẬT TOÁN K-MEANS: ......................................................................... 23 2.2. THUẬT TOÁN BISECTING-KMEANS: .................................................... 29 2.3. THUẬT TOÁN DỰA TRÊN MẬT ĐỘ DBSCAN ...................................... 38 2.3.1. Giới thiệu thuật toán:............................................................................ 38 2.3.2. Các định nghĩa và bổ đề ....................................................................... 38 2.4. THUẬT TOÁN OPTICS ............................................................................... 43 2.5. TIỂU KẾT CHƯƠNG 2 ................................................................................ 45 Chương 3. CÀ I ĐẶT MÔ PHỎNG VÀ ĐÁNH GIÁ KẾT QUẢ ........................ 46 3.1. MỘT SỐ LƯỢC ĐỒ LỚP ............................................................................. 46 3.1.1. LƯỢC ĐỒ LỚP CỦA KMEANS. ....................................................... 46 3.1.2. LƯỢC ĐỒ LỚP CỦA BISECTINGKMEANS. .................................. 47 3.1.3. LƯỢC ĐỒ LỚP CỦA DBSCAN......................................................... 48 3.1.4. LƯỢC ĐỒ LỚP CỦA OPTICS. .......................................................... 48 3.2. CÀI ĐẶT THỬ NGHIỆM............................................................................. 49 3.2.1. CÀI ĐẶT THUẬT TOÁN DBSCAN.................................................. 49 3.2.2. CÀI ĐẶT THUẬT TOÁN DBSCAN OPTICS ................................... 50 3.2.3. CÀI ĐẶT THUẬT TOÁN KMEANS ................................................. 51 3.2.4. CÀI ĐẶT THUẬT TOÁN BITSEC KMEANS .................................. 52 3.3. ĐÁNH GIÁ KẾT QUẢ ................................................................................. 53 3.3.1. Đánh giá 2 thuật toán Kmeans và BisectingKmeans ........................... 53 3.3.2. So sánh thời gian thực hiện của 4 thuật toán: DBSCAN, OPTICS, KMEANS và BISECTING-KMEANS .......................................................... 53 3.3. TIỂU KẾT CHƯƠNG 3 ................................................................................ 54 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ............................................................. 55 DANH MỤC TÀI LIỆU THAM KHẢO............................................................... 56 DANH MỤC CÁC THUẬT NGỮ Thuâ ̣t ngữ tiế ng Anh Thuâ ̣t ngữ tiế ng Việt Association rule Luật kết hợp Classification Phân lớp Clustering Phân cụm Data clustering Phân cụm dữ liệu Datamining Khai phá dữ liệu Density connected Mật độ liên thông Density reachable Mật độ đến được Directly density reachable Mật độ đến được trực tiếp Greedy Chiến lược tham lam Knowledge discovery Phát hiện tri thức Regression Hồi quy Similar Độ tương tự Summarization Tổng hợp Visualization Trực quan hóa DANH MỤC KÝ HIỆU Boder Point Đối tượng biên Core Distance Khoảng cách nhân Core Point Đối tượng nòng cốt CSDL Cơ sở dữ liệu Eps Bán kính lớn nhất của vùng lân cận Iter Số lần dựa vào thuật toán Kmeans chia 1 cụm thành 2 cụm nhỏ KDD Khám phá tri thức KPDL Khai phá dữ liệu KPTT Khai phá tri thức MinPts Số lượng tối thiểu các đối tượng trong cụm Neps(P) Lân cận của điểm p Noise Point Đối tượng nhiễu Reachability Distance Khoảng cách liên lạc SSE Bình phương sai số SSE Bình phương sai số DANH MỤC CÁC BẢNG Trang Bảng 1.1: Bảng hệ thống thông tin về bệnh nhân. ....................................................16 Bảng 2.1: Bảng so sánh giữa BisectingKmeans và Kmeans.....................................37 DANH SÁCH CÁC HÌ NH VẼ Trang Hình 1.1. Quá trình khám phá tri thức ........................................................................5 Hình 1.2. Quá trình khai phá dữ liệu...........................................................................8 Hình 1.3. Ví dụ về phân cụm/phân lớp dữ liệu .........................................................11 Hình 1.4. Phân cụm/lớp các đối tượng dựa trên khoảng cách ..................................12 Hình 1.5. Phân cụm/lớp các đối tượng dựa trên kích cỡ...........................................13 Hình 1. 6. Các chiến lược về phương pháp phân cấp ...............................................16 Hình 1. 7. Cây quyết định của ví dụ thông tin bệnh nhân.........................................17 Hình 1. 8. Ví dụ về phương pháp kết nối đơn...........................................................17 Hình 1. 9. Ví dụ về phương pháp kết nối đầy đủ ......................................................18 Hình 1.10. Ví dụ về phương pháp trọng tâm ............................................................18 Hình 2.1. Các thiết lập để xác định danh giới các cụm ban đầu ................................... 23 Hình 2.2. Tính toán trọng tâm của các cụm mới.......................................................25 Hình 2.3. Lân cận của P với ngưỡng Eps..................................................................38 Hình 2.4. Mật độ - đến được trực tiếp.......................................................................39 Hình 2. 5. Mật độ đến được ......................................................................................40 Hình 2.6. Mật độ liên thông ......................................................................................40 Hình 2.7. Cụm và nhiễu ............................................................................................41 Hình 2.8. Sắp xếp cụm trong OPTICS phụ thuộc vào ...........................................44 Hình 3.1. Sơ đồ lớp của hàm thuật toán KMEANS..................................................46 Hình 3.2. Sơ đồ lớp của hàm thuật toán BISECTINGKMEANS. ............................47 Hình 3.3. Sơ đồ lớp của hàm thuật toán DBSCAN...................................................48 Hình 3.4. Sơ đồ lớp của hàm thuật toán OPTICS. ....................................................48 Hình 3.5. Giao diện thực thi thuật toán DBSCAN....................................................49 Hình 3.6. Kết quả thực thi thuật toán DBSCAN.......................................................49 Hình 3.7. Giao diện thực thi thuật toán DBSCAN OPTICS.....................................50 Hình 3.8. Kết quả thực thi thuật toán DBSCAN-OPTICS........................................50 Hình 3.9. Giao diện thực thi thuật toán KMEANS. ..................................................51 Hình 3.10. Kết quả thực thi thuật toán KMEANS. ...................................................51 Hình 3.11. Giao diện thực thi thuật toán BISECTING - KMEANS.........................52 Hình 3.12. Kết quả thực thi thuật toán BISECTING-KMEANS..............................52 Hình 3.13. So sánh độ tương đồng giữa Kmeans và BisectingKmeans ...................53 Hình 3.14. So sánh độ thời gian thực hiện giữa DBSCAN, OPTICS, Kmeans và BisectingKmeans.......................................................................................................53 MỞ ĐẦU Cùng với sự phát triển của công nghệ thông tin và ứng dụng của nó trong đời sống – kinh tế – xã hội, lượng dữ liệu thu thập được ngày càng nhiều theo thời gian, tốc độ tăng dữ liệu rất lớn dẫn đến đã có những bộ dữ liệu có kích thước lên tới mức tera – byte. Trong tình hình hiện nay, khi thông tin đang trở thành yếu tố quyết định trong nhiều lĩnh vực của đời sống xã hội thì vấn đề tìm ra các thông tin hữu ích – tri thức trong khối dữ liệu lớn ngày càng trở thành mục tiêu quan trọng của nhiều ngành, nhiều doanh nghiệp. Một hướng tiếp cận có khả năng giúp các công ty khai thác các thông tin có nhiều ý nghĩa từ khối dữ liệu lớn được thu thập đó là khai phá dữ liệu (KPDL). KPDL đã và đang được sử dụng rộng rãi trong nhiều lĩnh vực khác nhau: marketing, tài chính, ngân hàng và bảo hiểm, khoa học, y tế, an ninh, internet… Quá trình KPDL là quá trình phát hiện ra mẫu thông tin có ích, tiềm ẩn trong khối dữ liệu lớn. Trong đó, giải thuật khai phá tìm kiếm các mẫu đáng quan tâm như các luật, phân lớp, hồi quy, cây quyết định,... Một trong những kỹ thuật chính của KPDL đó là phân lớp dữ liệu, Các kĩ thuật khai phá này đã, đang và sẽ phát triển mạnh mẽ trước những khát khao khám phá tri thức của con người. Phân lớp dữ liệu là việc xác định ánh xạ từ một mẫu dữ liệu vào một trong số các lớp đã biết trước, Mục tiêu của thuật toán phân lớp là tìm ra mối quan hệ giữa thuộc tính dự báo và thuộc tính phân lớp. Do đó quá trình phân lớp có thể sử dụng mối quan hệ này để dự báo cho các đối tượng mới, nhằm giải quyết hai bài toán trong KPDL là mô tả và dự đoán. Trong đó, phân lớp dữ liệu không phân cấp nhằm giải quyết bài toán mô tả dữ liệu. Trong các mô hình phân lớp, thuật toán phân lớp là nhân tố chủ đạo. Do vậy cần xây dựng những thuật toán có độ chính xác cao, thực thi nhanh, đi kèm với khả năng mở rộng được để có thể thao tác với những tập dữ liệu ngày càng lớn. Luận văn thực hiện việc nghiên cứu tổng quan về công nghệ phân lớp dữ liệu cụ thể là phân lớp dữ liệu không phân cấp. Các thuật toán phân lớp đều có độ phức tạp tính toán không phải là đa thức. Hơn nữa, việc đánh giá mô hình hay sự phân 1 lớp nào tối ưu là một bài toán khó và vẫn đang thu hút nhiều nhà nghiên cứu quan tâm. Với những lý do trên tôi chọn đề tài: “TÌM HIỂU MỘT SỐ PHƯƠNG PHÁP PHÂN LỚP DỮ LIỆU KHÔNG PHÂN CẤP” làm đề tài luận văn tốt nghiệp 1. Mu ̣c đı́ch nghiên cứu: - Tìm hiểu về phân lớp dữ liệu. - Tìm hiểu về các thuật toán DBScan, K-means và các cải tiến. - Mô phỏng các thuật toán đã tìm hiểu. 2. Đố i tươ ̣ng nghiên cứu: - Các thuật toán phân lớp trên các hệ thống thông tin. 3. Phương phá p nghiên cứu: - Lý thuyết: tìm hiểu về lý thuyết dựa vào các công trình đăng tải trên các tạp chí có uy tín trong và ngoài nước, các giáo trình, sách tham khảo được xuất bản bởi những nhà xuất bản đáng tin cậy. - Thực nghiệm: mô phỏng các thuật toán đã tìm hiểu. 4. Nội dung: Luận văn tập trung nghiên cứu các nội dung sau: - Tìm hiểu về các thuật toán DBScan, K-means và các cải tiến. Ngoà i phầ n mở đầ u, kế t luâ ̣n và tà i liê ̣u tham khả o luâ ̣n văn đươ ̣c chia là m 3 chương vớ i cấ u trú c như sau: Chương 1: Trı̀nh bà y tổ ng quan về khai phá tri thứ c, các kĩ thuật khai phá tri thức và các phương pháp phân lớp dữ liệu. Chương 2: Trình bày các thuật toán DBSCAN, DBSCAN – OPTICS, KMEANS, BISECTING - KMEANS. 2 Chương 3: Cà i đă ̣t thuâ ̣t toá n DBSCAN, DBSCAN OPTICS, KMEANS, BISECTING KMEANS trên mô ̣t số bô ̣ dữ liê ̣u sử du ̣ng ngôn ngữ lâ ̣p trı̀nh Java. Do thờ i gian có ha ̣n, bả n thân chı̉ bướ c đầ u thực hiê ̣n cá c đề tà i nghiên cứ u nên không trá nh khỏ i thiế u só t, mong thầ y cô và ba ̣n bè giú p đỡ gó p ý thêm để chất lượng luâ ̣n văn tốt hơn. 3 Chương 1. TỔNG QUAN VỀ KHAI PHÁ DỮ LIỆU VÀ PHÂN CỤM DỮ LIỆU Ngà y nay, Công nghê ̣ thông tin đó ng vai trò quan tro ̣ng trong đờ i số ng xã hô ̣i, nó len lỏ i và o hầ u hế t mo ̣i lı̃nh vực củ a đờ i số ng xã hô ̣i. Cù ng vớ i đó là sự phá t triể n củ a cá c công cu ̣ thu thâ ̣p, lưu trữ dữ liê ̣u như camera hà nh trı̀nh, camera giá m sá t và các ứng dụng web. Do đó lươ ̣ng thông tin đươ ̣c lưu trữ rấ t lớ n. Tuy nhiên, cá c thông tin dư thừ a và hữ u ı́ch – tri thứ c chı̉ chiế m mô ̣t phầ n rấ t nhỏ , đề u đươ ̣c lưu trữ trong khố i dữ liê ̣u lớ n nà y. Do đó vấ n đề trı́ch xuấ t cá c dữ liê ̣u có ı́ch – tri thứ c để phu ̣c vu ̣ cho đờ i số ng xã hô ̣i là vấ n đề thá ch thứ c đố i vớ i cá c phương phá p phân tı́ch dữ liê ̣u truyề n thố ng. KPDL chı́nh là quá trı̀nh chắ t lo ̣c cá c thông tin hữ u ı́ch tiề m ẩ n, chưa đươ ̣c biế t đế n trong khố i lươ ̣ng dữ liê ̣u lớ n để phu ̣c vu ̣ cho nhiề u ngà nh, nhiề u lı̃nh vực khá c nhau như: thố ng kê, trı́ tuê ̣ nhân ta ̣o, marketing, y ho ̣c, thi ̣ trườ ng chứ ng khoá n… KPDL có thể dù ng để cung cấ p cá c tri thứ c, hỗ trơ ̣ quyế t đinh, ̣ dự bá o. 1.1. TỔNG QUAN KHAI PHÁ DỮ LIỆU 1.1.1. Khái niệm về khai phá dữ liệu Khai phá dữ liệu [2] là quá trình khai thác (rút trích) những thông tin tiềm ẩn có tính dự đoán, những thông tin có nhiều ý nghĩa, hữu ích từ những cơ sở dữ liệu lớn, nó được coi như là một bước trong quá trình khám phá tri thức (KDD). Khai phá dữ liệu là giai đoạn quan trọng nhất trong tiến trình KDD từ cơ sở dữ liệu. Quá trình KDD tiến hành qua 6 giai đoạn như Hình 1.1: 4 Hình 1.1. Quá trình khám phá tri thức Bắt đầu của quá trình là kho dữ liệu thô và kết thúc với tri thức được chiết xuất ra. Về lý thuyết thì có vẻ rất đơn giản nhưng thực sự đây là một quá trình rất khó khăn, gặp phải rất nhiều vướng mắc như: quản lý các tập dữ liệu, phải lặp đi lặp lại toàn bộ quá trình, v.v... - Thu gom dữ liệu Tập hợp dữ liệu là bước đầu tiên trong quá trình KPDL. Đây là bước được khai thác trong một CSDL, một kho dữ liệu hay nguồn dữ liệu từ các ứng dụng web hoă ̣c cá c thiế t bi ̣thu nhâ ̣n dữ liê ̣u. - Trích lọc dữ liệu Ở giai đoạn này lựa chọn những dữ liệu phù hợp với nhiệm vụ phân tích trích rút từ CSDL. - Làm sạch, tiền xử lý và chuẩn bị trước dữ liệu Giai đoạn thứ ba này là giai đoạn hay bị sao nhãng, nhưng thực tế nó là một bước rất quan trọng trong quá trình khai phá dữ liệu. Một số lỗi thường mắc phải 5 trong khi gom dữ liệu là tính không đủ chặt chẽ và logic. Vì vậy, dữ liệu thường chứa các giá trị vô nghĩa và không có khả năng kết nối, chẳ ng ha ̣n như thu thâ ̣p dữ liê ̣u điểm là số âm. Giai đoạn này sẽ tiến hành xử lý những dạng dữ liệu không chặt chẽ nói trên. Những dữ liệu dạng này được xem như thông tin dư thừa, không có giá trị. Bởi vậy, đây là một quá trình rất quan trọng vì dữ liệu này nếu không được “làm sạch” sẽ gây nên những kết quả sai lệch nghiêm trọng. - Chuyển đổi dữ liệu Tiếp theo là giai đoạn chuyển đổi dữ liệu, dữ liệu được chuyển đổi hay được hợp nhất về dạng thích hợp cho việc khai phá. - Khai phá dữ liệu Đây là một tiến trình cốt yếu. Ở giai đoạn này nhiều thuật toán khác nhau đã được sử dụng một cách phù hợp để trích xuất thông tin có ích hoặc các mẫu điển hình trong dữ liệu. - Đánh giá kết quả mẫu Đây là giai đoạn cuối trong quá trình KPDL. Ở giai đoạn này, các mẫu dữ liệu được chiết xuất, không phải bất cứ mẫu dữ liệu nào cũng đều hữu ích, đôi khi còn bị sai lệch. Vì vậy, cần phải ưu tiên những tiêu chuẩn đánh giá để chiết xuất ra các tri thức cần thiết. Từ quá trình KPTT trên chúng ta thấy được sự khác biệt giữa KPTT và KPDL. Trong khi KPTT là nói đến quá trình tổng thể phát hiện tri thức hữu ích từ dữ liệu. Còn KPDL chỉ là một bước trong quá trình KPTT, các công việc chủ yếu là xác định được bài toán khai phá, tiến hành lựa chọn phương pháp KPDL phù hợp với dữ liệu có được và tách ra các tri thức cần thiết. 6 1.1.2. Các loại dữ liệu có thể khai phá Các loại dữ liệu có thể được khai phá như sau: - CSDL quan hệ. - CSDL đa chiều. - CSDL giao tác. - CSDL quan hệ - hướng đối tượng. - CSDL không gian và thời gian. - CSDL đa phương tiện. Trong 6 giai đoạn trên của quá trình khám phá tri thức, trong đó giai đoạn 5 khai phá dữ liệu (hay còn gọi đó là Data Mining) là giai đoạn được quan tâm nhiều nhất. KPDL không thuộc một ngành công nghiệp nào. Nó sử dụng các kỹ thuật thông minh để khai phá các tri thức tiềm ẩn trong dữ liệu. Có thể coi KPDL ngày nay đang ở trạng thái giống như việc quản trị dữ liệu vào những năm 60, khi mà các ứng dụng quản trị dữ liệu đều không tuân theo một nguyên tắc chung nào cho đến khi mô hình dữ liệu quan hệ ra đời cùng với sức mạnh của ngôn ngữ truy vấn đã thúc đẩy việc phát triển các ứng dụng quản trị dữ liệu một cách nhanh chóng. Tuy vậy, hiện nay trên thế giới đã có rất nhiều ngành công nghiệp sử dụng kỹ thuật KPDL để phục vụ cho hoạt động kinh doanh của mình và đã bước đầu thành công như ngành tài chính, y học, hóa học, bảo hiểm, sản xuất, giao thông, hàng không,… Các kết quả đạt được cho thấy mặc dù kỹ thuật KPDL hiện nay vẫn còn nhiều vấn đề nổi cộm, nhưng với những tri thức mà chuyên gia cũng chưa cung cấp được thì KPDL có một tiềm năng to lớn trong việc tạo ra những lợi nhuận đáng kể trong nền kinh tế. 1.1.3. Quá trı̀nh khá m phá tri thức Quá trình KPTT từ CSDL là một quá trình có sử dụng nhiều phương pháp và công cụ tin học nhưng vẫn là một quá trình mà trong đó con người là trung tâm. Do 7 đó, nó không phải là một hệ thống phân tích tự động mà là một hệ thống bao gồm nhiều hoạt động tương tác thường xuyên giữa con người và CSDL, tất nhiên với sự hỗ trợ của các công cụ tin học. Người sử dụng hệ thống ở đây phải là người có kiến thức cơ bản về lĩnh vực cần phát hiện tri thức để có thể chọn được đúng các tập con dữ liệu, các lớp mẫu phù hợp và đạt tiêu chuẩn. Tri thức mà ta nói ở đây là các tri thức rút ra từ các CSDL, thường để phục vụ cho việc giải quyết một loạt nhiệm vụ nhất định trong một lĩnh vực nhất định. Do đó, quá trình phát hiện tri thức cũng mang tính chất hướng nhiệm vụ, không phải là phát hiện mọi tri thức bất kỳ mà là phát hiện tri thức nhằm giải quyết tốt nhiệm vụ đề ra. Khai phá dữ liệu [2] là một giai đoạn quan trọng trong quá trình khám phá tri thức. Về bản chất là giai đoạn duy nhất tìm ra được thông tin mới, thông tin tiềm ẩn có trong cơ sở dữ liệu chủ yếu phục vụ cho mô tả và dự đoán. Mô tả dữ liệu là tổng kết hoặc diễn tả những đặc điểm chung của những thuộc tính dữ liệu trong kho dữ liệu mà con người có thể hiểu được. Dự đoán là dựa trên những dữ liệu hiện thời để dự đoán những quy luật được phát hiện từ các mối liên hệ giữa các thuộc tính của dữ liệu trên cơ sở đó chiết xuất ra các mẫu, dự đoán được những giá trị chưa biết hoặc những giá trị tương lai của các biến quan tâm. Hình 1.2. Quá trình khai phá dữ liệu - Xác định nhiệm vụ: Xác định chính xác các vấn đề cần giải quyết. - Xác định các dữ liệu liên quan: Dùng để xây dựng giải pháp. 8