Khai phá và làm sạch dữ liệu

1BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG -------o0o------- Khai phá và làm sạch dữ liệu ĐỒ ÁN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY NGÀNH CÔNG NGHỆ THÔNG TIN Giáo viên hướng dẫn: PGS. TS. Đỗ Trung Tuấn Sinh viên: Nguyễn Hoài Nam Lớp: CT701 Hải Phòng, 2007 2Nội dung báo cáo  Chương 1. Mở đầu.  Chương 2. CSDL và nhu cầu về dữ liệu meta.  Chương 3. Khai phá dữ liệu.  Chương 4. Luật kết hợp và các tiếp cận.  Chương 5. Thử nghiệm việc khai phá dữ liệu.  Chương 6. Kết luận 3Chương 2. CSDL và nhu cầu về dữ liệu meta  Mô hình dữ liệu quan hệ  Nhu cầu về dữ liệu meta  Trong vài thập niên với những tác động mạnh mẽ của các tiến bộ trong công nghệ công nghệ thông tin và truyền thông nhu cầu về dữ liệu ngày càng nhiều  Yêu cầu về các thông tin trong các lĩnh vực hoạt động đó đòi hỏi cao hơn, người quyết định không những cần dữ liệu mà còn cần có thêm nhiều hiểu biết, nhiều tri thức để hỗ trợ cho việc ra quyết định của mình. 4Chương 3. Khai phá dữ liệu  Giới thiệu chung  Về khai phá dữ liệu  Quá trình phát hiện tri thức trong CSDL  Nhiệm vụ chính trong khai phá dữ liệu  Các kĩ thuật khai phá dữ liệu  Ứng dụng của khai phá dữ liệu  Khai phá luật kết hợp và ứng dụng 5Giới thiệu chung  Những năm 60 của thế kỷ trước, người ta bắt đầu sử dụng các công cụ tin học để tổ chức và khai thác các CSDL  Người ta nói “Chúng ta đang chìm ngập trong dữ liệu mà vẫn đói tri thức”  Khai phá dữ liệu là một lĩnh vực mới, nhằm tự động khai thác những thông tin, những tri thức có tính tiềm ẩn, hữu ích từ những CSDL lớn 6Về khai phá dữ liệu  Khai phá dữ liệu là một khái niệm ra đời vào những năm cuối của thập kỉ 80  Khai phá dữ liệu sử dụng các giải thuật đặc biệt để chiết xuất ra các mẫu hay các mô hình từ dữ liệu  Định nghĩa: Data Mining là một quá trình tìm kiếm, phát hiện tri thức mới, tiềm ẩn, hữu dụng trong CSDL lớn 7Quá trình phát hiện tri thức trong CSDL 8Nhiệm vụ chính trong khai phá dữ liệu  Phân lớp, phân loại  Hồi quy  Phân nhóm  Tóm tắt  Mô hình hoá phụ thuộc 9Các kĩ thuật khai phá dữ liệu  Các kĩ thuật tiếp cận  Dạng dữ liệu có thể khai phá 10 Các kĩ thuật tiếp cận  Trên quan điểm của học máy, các kĩ thuật trong Data Mining gồm:  Học có giám sát  Học không có giám sát  Học nửa giám sat  Căn cứ vào lớp các bài toán cần giải quyết, khai phá dữ liệu có các kỹ thuật áp dụng sau:  Phân lớp và dự đoán  Luật kết hợp  Phân tích chuỗi theo thời gian  Phân cụm  Mô tả khái niệm 11 Dạng dữ liệu có thể khai phá  CSDL quan hệ  CSDL đa chiều  CSDL dạng giao dịch  CSDL quan hệ-hướng đối tượng  Dữ liệu không gian và thời gian  Dữ liệu chuỗi thời gian  CSDL đa phương tiện  Dữ liệu Text và Web… 12 Ứng dụng của khai phá dữ liệu  Kinh doanh  Ngân hàng  Bảo hiểm sức khoẻ  Y tế… 13 Khai phá luật kết hợp và ứng dụng  Luật kết hợp là một biểu thức có dạng: X- >Y, trong đó X và Y là tập các trường gọi là item  Ứng dụng trực tiếp của các luật này trong các bài toán kinh doanh 14 Thuật toán về khai phá dữ liệu thuật toán Apriori  Ý tưởng thuật toán  Thuật toán Apriori  Ví dụ minh hoạ 15 Ý tưởng thuật toán  Đề xuất lần đầu vào năm 1993  Thuật toán tìm giao dịch t có độ hỗ trợ và độ tin cậy thoả mãn lớn hơn một giá trị ngưỡng nào đó  Thuật toán được tỉa bớt những tập ứng cử viên có tập con không phổ biến trước khi tính độ hỗ trợ  Thuật toán Apriori tính tất cả các tập ứng cử của tập k trong một lần duyệt CSDL 16 Thuật toán Apriori Gồm 2 bước:  Tạo tập item phổ biến: tạo tất cả các tập item dự kiến, tính toán độ hỗ trợ, loại bỏ các tập dự kiến không đạt minsupp.  Kiểm tra tập 1 item có là phổ biến không.  Lần duyệt thứ k: Sử dụng các tập Lk-1 của tập k-1 item phổ biến để tạo tập dự kiến Ck (dùng hàm apriori_gen). Duyệt CSDL và tính support cho Ck.  Lk: là tập hợp của các tập k_item phổ biến, mỗi phần tử là một tập có 2 trường itemset, support.  Ck: tập hợp của tập k_item dự kiến 17 Thuật toán Apriori 18 Thuật toán Apriori  Tạo luật kết hợp: Từ các tập con của tập phổ biến xây dựng luật kết hợp và tính độ tin cậy của luật.  Từ tập item phổ biến L, tìm tất cả các tập con không rỗng f  L rồi tạo ra luật f  L – f thoả mãn minconf. VD: Nếu {A,B,C,D} là tập item phổ biến thì có các luật dự kiến: ABC D, ABD C, ACD B, BCD A, A BCD, B ACD, C ABD, D ABC AB CD, AC  BD, AD  BC, BC AD, BD AC, CD AB,  Nếu L có k item thì có thể tạo ra 2k-2 luật kết hợp dự kiến(bỏ qua luật L   và   L)  Dựa vào tính chất của độ tin cậy để tạo ra luật có conf >= minconf.  Độ tin cậy không có tính chất c(ABC D) có thể lớn hơn hay nhỏ hơn c(AB D)  Nhưng nếu luật được sinh ra từ cùng một tập item phổ biến thì có thuộc tính đó: VD: L = {A,B,C,D} c(ABC  D)  c(AB  CD)  c(A  BCD) 19 Thuật toán Apriori 20 Ví dụ minh hoạ 21 Ví dụ minh hoạ 22 Chương 4. Luật kết hợp và các tiếp cận  Khai phá luật kết hợp  Cho trước tỉ lệ hỗ trợ  và độ tin cậy .. Đánh số tất cả các luật trong D có các giá trị tỉ lệ hỗ trợ và tin cậy lớn hơn  và  tương ứng.  Lý thuyết về luật kết hợp 23 Chương 5. Thử nghiệm 24 Chương 5. Thử nghiệm 25 Chương 5. Thử nghiệm 26 Chương 5. Thử nghiệm 27 Chương 5. Thử nghiệm 28 Chương 6. Kết luận  Trong quá trình nghiên cứu viết luận văn em đã: tìm hiểu tổng quan về lí thuyết khai phá dữ liệu, thuật toán Apriori và luật kết hợp.  Do thời gian và kinh nghiệm thực tế chưa nhiều nên luận văn còn nhiều thiếu sót mong các thầy cô bỏ qua và góp ý. Em xin chân thành cảm ơn!