LUẬN VĂN: PHỤ THUỘC HÀM XẤP XỈ VÀ ỨNG DỤNG TRONG KHAI PHÁ DỮ LIỆU

Cơ sở dữ liệu (CSDL) là một trong lĩnh vực được tập trung nghiên cứu và phát triển công nghệ thông tin, nhằm giải quyết các bài toán quản lý, tìm kiếm thông tin trong những hệ thống lớn, đa dạng, phức tạp cho nhiều người sử dụng trên máy tính điện tử. Mô hình dữ liệu quan hệ đặt trọng điểm hàng đầu không phải là khác thác các tiềm năng của máy mà sự mô tả trực quan dữ liệu theo quan điểm của người dùng, cung cấp một mô hình dữ liệu đơn giản, trong sáng, chặt...
Nội dung trích xuất từ tài liệu:
LUẬN VĂN: PHỤ THUỘC HÀM XẤP XỈ VÀ ỨNG DỤNG TRONG KHAI PHÁ DỮ LIỆU 1 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN MINH HUY PHỤ THUỘC HÀM XẤP XỈ VÀ ỨNG DỤNG TRONG KHAI PHÁ DỮ LIỆU LUẬN VĂN THẠC SĨ Hà Nội – 2011 2 MỤC LỤC Lời cam đoan Mục lục Danh mục các từ viết tắt Danh mục các bảng biểu Danh mục phụ lục MỞ ĐẦU ................................................................................................ 5 Chương 1 - Phụ thuộc hàm và phụ thuộc hàm xấp xỉ ................................6 1.1 Khai phá dữ liệu.............................................................................6 1.1.1 Phát hiện tri thức và khai phá dữ liệu ......................................6 1.1.2 Các phương pháp khai phá dữ liệu ..........................................7 1.2 Phụ thuộc hàm ...............................................................................7 1.2.1 Định nghĩa...............................................................................7 1.2.2 Hệ tiên đề Armstrong ..............................................................8 1.2.3 Định nghĩa hai tập phụ thuộc hàm tương đương....................10 1.2.4 Định nghĩa phủ tối thiểu ........................................................ 11 1.2.5 Khoá của quan hệ ..................................................................13 1.3 Phụ thuộc hàm xấp xỉ ...................................................................14 1.3.1 Phụ thuộc hàm xấp xỉ loại 1 ..................................................14 1.3.2 Phụ thuộc hàm xấp xỉ loại 2 ..................................................16 1.3.3 Bao đóng xấp xỉ ....................................................................20 1.3.4 Khoá xấp xỉ ...........................................................................21 Chương 2 - Xây dựng cây quyết định ........................................................ 24 3 2.1 Đặt vấn đề ....................................................................................24 2.2 Bảng quyết định ...........................................................................24 2.2.1 Hệ thống thông tin.................................................................24 2.2.2 Bảng quyết định ....................................................................27 2.3 Cây quyết định .............................................................................30 2.4 Ảnh hưởng của phụ thuộc hàm, phụ thuộc hàm xấp xỉ khi xây dựng cây quyết định ..............................................................................36 Chương 3 - Thử nghiệm và đánh giá ......................................................... 37 3.1 Thuật toán TANE.......................................................................37 3.1.1 Mô tả thuật toán ............................................................... 37 3.1.2 Độ phức tạp ......................................................................38 3.2 Thuật toán AFDMCEC ............................................................. 38 3.2.1 Phân tích thử nghiệm........................................................ 39 3.2.2 Những so sánh về độ phức tạp thời gian ........................... 40 KẾT LUẬN .......................................................................................... 41 TÀI LIỆU THAM KHẢO .................................................................... 42 PHỤ LỤC ............................................................................................. 43 a) Giao diện chương trình b) Thủ tục tính phụ thuộc hàm xấp xỉ c) Thủ tục phân hoạch 4 ‘ DANH MỤC CÁC CHỮ VIẾT TẮT CSDL : Cơ sở dữ liệu FDs : Các phụ thuộc hàm AFDs : Các phụ thuộc hàm xấp xỉ AFDMCEC : Khai phá phụ thuộc hàm xấp xỉ sử dụng phủ tối thiểu và lớp tương đương 5 DANH MỤC CÁC BẢNG BIỂU Bảng 1.1 Quy trình phát hiện tri thức Bảng 1.2 Bảng cơ sở dữ liệu quan hệ Bảng 1.3 Cây khai phá các AFDs(ví dụ với 5 thuộc tính) Bảng 1.4 Bảng cơ sở dữ liệu quan hệ số Bảng 1.5 Bảng cơ sở dữ liệu kiểm toán(ví dụ trong 5 tháng) Bảng 2.1 Bảng dữ liệu các đồ chơi Bảng 2.2 Bảng các triệu chứng của bệnh nhân Bảng 2.3 Bảng quyết định về cúm Bảng 2.4 Bảng rút gọn thứ nhất của bảng quyết định về cúm Bảng 2.5 Bảng rút gọn thứ hai của bảng quyết định về cúm Bảng 2.6 Bảng chọn ứng cử viên vào ngạch giảng dạy Bảng 2.7 Bảng dữ liệu điều tra khách hàng mua ôtô Bảng 2.8 Cây quyết định tại bước 1 trên thuộc tính phụ cấp Bảng 2.9 Cây quyết định tại bước 2 6 MỞ ĐẦU Cơ sở dữ liệu (CSDL) là một trong lĩnh vực được tập trung nghiên cứu và phát triển công nghệ thông tin, nhằm giải quyết các bài toán quản lý, tìm kiếm thông tin trong những hệ thống lớn, đa dạng, phức tạp cho nhiều người sử dụng trên máy tính điện tử. Mô hình dữ liệu quan hệ đặt trọng điểm hàng đầu không phải là khác thác các tiềm năng của máy mà sự mô tả trực quan dữ liệu theo quan điểm của người dùng, cung cấp một mô hình dữ liệu đơn giản, trong sáng, chặt chẽ, dễ hiểu và tạo khả năng tự động hoá thiết kế CSDL quan hệ. Có thể nói lý thuyết thiết kế và cài đặt CSDL, nhất là mô hình dữ liệu quan hệ đã phát triển ở mức độ cao và đạt được những kết quả sâu sắc. Ngày nay việc khai phá dữ liệu còn được coi như việc khai phá tri thức từ dữ liệu (knowlegde ...