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 mining from databases), trích lọc tri thức(knowlegde extraction), phân tích dữ liệu mẫu (data-partent analysis), khảo cứu dữ liệu(data archaeology), đào xới và nạo vét dữ liệu(data dredging).
Với các ngành khoa học, kinh tế - xã hội nơi có những kho dữ liệu khổng lồ thì việc tìm kiếm, truy xuất và đưa ra thông tin cần thiết phù hợp với thời gian và yêu cầu là không dễ dàng và chính vì thế một hế hệ mới các phương pháp tiếp cận, phương pháp nghiên cứu, và các kỹ thuật, công cụ cho phép phân tích, tổng hợp, khai phá tri thức từ dữ liệu một cách thông minh và hiệu quả đã được các nhà khoa học quan tâm và nghiên cứu. Trong những năm gần đây, việc tìm kiếm các thuật toán cho phép khai phá phụ thuộc hàm xấp xỉ đang được quan tâm nghiên cứu, một trong hững thuật toán đó là TANE - một thuật toán tương đối hiệu quả trong khai phá phụ thuộc hàm xấp xỉ. LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 6 CHƢƠNG 1: PHỤ THUỘC HÀM VÀ PHỤ THUỘC HÀM XẤP XỈ Khai phá dữ liệu Phát hiện tri thức và khai phá dữ liệu Phát hiện tri thức trong các cơ sở dữ liệu là một qui trình nhận biết các mẫu hoặc các mô hình trong dữ liệu với các tính năng: hợp thức, mới, khả ích, và có thể hiểu được. Còn khai thác dữ liệu là một bước trong qui trình phát hiện tri thức gồm có các thuật toán khai thác dữ liệu chuyên dùng dưới một số qui định về hiệu quả tính toán chấp nhận được để tìm ra các mẫu hoặc các mô hình trong dữ liệu.
Nói một cách khác, mục đích của phát hiện tri thức và khai phá dữ liệu chính là tìm ra các mẫu và/hoặc các mô hình đang tồn tại trong các cơ sở dữ liệu nhưng vẫn còn bị che khuất bởi hàng núi dữ liệu. Qui trình phát hiện tri thức Qui trình phát hiện tri thức được mô tả tóm tắt : Bảng 1.1 Quy trình phát hiện tri thức - Bước thứ nhất là tìm hiểu lĩnh vực ứng dụng và hình thành bài toán, bước này sẽ quyết định cho việc rút ra được các tri thức hữu ích và cho phép chọn các phương pháp khai phá dữ liệu thích hợp với mục đích ứng dụng và bản chất của dữ liệu. - Bước thứ hai là thu thập và xử lý thô, còn được gọi là tiền xử lý dữ liệu nhằm loại bỏ nhiễu, xử lý việc thiếu dữ liệu, biến đổi dữ liệu và rút gọn dữ liệu nếu cần LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 7 thiết, bước này thường chiếm nhiều thời gian nhất trong toàn bộ qui trình phát hiện tri thức. - Bước thứ ba là khai phá dữ liệu, hay nói cách khác là trích ra các mẫu hoặc/và các mô hình ẩn dưới các dữ liệu.
- Bước thứ tư là hiểu tri thức đã tìm được, đặc biệt là làm sáng tỏ các mô tả và dự đoán. Các bước trên có thể lặp đi lặp lại một số lần, kết quả thu được có thể được lấy trung bình trên tất cả các lần thực hiện. Các phƣơng pháp khai phá dữ liệu Với hai đích chính của khai phá dữ liệu là Dự đoán và Mô tả , người ta thường sử dụng các phương pháp sau cho khai phá dữ liệu: - Phương pháp quy nạp - Phát hiện các luật kết hợp - Sử dụng cây quyết định - Các phương pháp phân lớp và hồi quy phi tuyến: - Phân nhóm và phân đoạn - Các phương pháp dự trên mẫu - Mô hình phụ thuộc dựa trên đồ thị xác suất - Mô hình học quan hệ - Mạng neuron - Thuật giải di truyền 1.2 Phụ thuộc hàm 1.1 Định nghĩa Trong mỗi CSDL luôn tồn tại nhiều mối liên hệ giữa các thuộc tính, giữa các bộ; sự liên hệ này có thể xảy ra trong cùng một quan hệ hoặc trong các quan hệ của một lược đồ CSDL. Các mối liên hệ này là những điều kiện bất biến mà tất cả các bộ của những quan hệ có liên quan trong CSDL đều phải thoả mãn ở mọi thời điểm.
Những điều kiện bất biến đó được gọi là rằng buộc toàn vẹn. Phụ thuộc hàm là 1 công cụ dùng để biểu diễn 1 cách hình thức 1 số rằng buộc toàn vẹn. Các phụ thuộc hàm là các tương quan giữa các thuộc tính của một quan hệ: Một phụ thuộc hàm chỉ ra rằng giá trị của một thuộc tính được xác định duy nhất LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 8 bởi một số các thuộc tính khác. Vấn đề phát hiện các phụ thuộc hàm từ các quan hệ đã nhận được các mối quan tâm đáng kể.
Việc phân tích CSDL tự động, đương nhiên, rất thú vị cho các mục tiêu khai phá tri thức và khai phá dữ liệu , và các phụ thuộc hàm có nhiều ứng dụng trong các lĩnh vực quản lý CSDL, tối ưu hóa truy vấn… Một cách hình thức, một phụ thuộc hàm trên một lược đồ quan hệ R là một biểu diễn XA với X R và A R.Phụ thuộc này đúng trong một quan hệ r trên R cho trước nếu với mọi cặp hàng t,u R, ta có nếu t[B] = u[B] mọi B X thì t[A] = u[A] (ta cũng nói rằng t và u thoả trên X và A). Ví dụ : Mã Sinh viên Họ và tên Số chứng minh Năm Quê quán sinh 00001 Nguyễn Văn A 1247237 198 Hà Nội 7 00002 Nguyễn Văn B 1211445 198 Lạng Sơn 8 Ta có các phụ thuộc hàm sau AB, AC, AD, AE,CB,CD, CE Phụ thuộc hàm X A là tối thiểu trong r nếu A không phụ thuộc hàm vào bất kỳ một tập con thực sự nào của X. Ví dụ nếu Y A không thoả trong r với bất kỳ Y X. Phụ thuộc hàm X A là tầm thường nếu A X.2 Hệ tiên đề Armstrong Gọi F là tập tất cả các phụ thuộc hàm đối với lược đồ quan hệ r(U) và X -> Y là một phụ thuộc hàm với X, Y U, ta nói rằng X -> Y được suy diễn logic từ F nếu quan hệ trên r(U) đều thỏa mãn các phụ thuộc hàm của F thì cũng thỏa X -> Y.
Sau đây là tập quy tắc của hệ tiên đề được Armstrong đề xuất vào năm 1974, được gọi là hệ tiên đề Armstrong. Hệ tiên đề Armstrong LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 9 Gọi R(U) là lược đồ quan hệ với U = (A1, A2,., An) là tập các thuộc tính: giả sử X, Y, Z U, hệ tiên đề Armstrong bao gồm: * Tính phản xạ: Nếu Y X thì X -> Y * Tính tăng trưởng: Nếu Z U, X->Y thì ZX -> ZY. Trong đó ZX=Z U * Tính bắc cầu: Nếu X -> Y và Y -> Zthì X -> Z. Ví dụ: Cho AB -> C, C -> A, chứng minh BC -> ABC (1) C -> A (theo giả thiết) (2) BC -> AB (áp dụng luật tăng trưởng tăng (1) lên B) (3) AB -> C (theo giả thiết) (4) AB -> ABC (tăng (3)AB) (5) BC -> ABC (bắc cầu (1), (2)).
Bổ đề 1: Hệ tiên đề Armstrong là đầy đủ, có nghĩa là nếu F là tập phụ thuộc hàm đúng trên quan hệ r và f : X -> Y là một phụ thuộc hàm được suy dẫn từ F nhờ hệ tiên đề Armstrong thì f đúng trên r Bổ đề 2: Tính hợp : nếu X -> Y và X -> Z thì X -> YZ. Tính tựa bắc cầu : Nếu X -> Y và WY -> Z thì XW -> Z. Tính tách: Nếu X -> Y và Z Y thì X -> Z. Bao đóng của F được kí hiệu là F+, là tập tất cả các phụ thuộc hàm được suy diễn logic nhờ tiên đề Armstrong, 3 bổ đề trên từ F, nếu F = F+ thì F là họ đầy đủ của các phụ thuộc hàm.
Bao đóng của tập thuộc tính (X+) X -> Y là một phụ thuộc hàm suy ra từ F. Khi đó X+ được gọi là bao đóng của tập thuộc tính X nếu X+ là tập tất cả các thuộc tính U được suy dẫn bắt đầu từ tập X. X+F = { A | X -> A F+ } Thuật toán tìm bao đóng của tập thuộc tính: INPUT: X, F,U OUTPUT: X+ LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 10 S:=X WHILE có (Z -> Y) thuộc F với Z S và Y⊄S DO S:= SY ENDWHILE X+ = S Phương pháp: Tính liên tiếp các tập thuộc tính X0, X1, X2,., Xi BC0: Đặt X0 = X BC1: Nếu tồn tại phụ thuộc hàm f: Y->Z F sao cho Y X0, Z U thì X1=X0Z BC2: Tương tư. Until Xi = Xi+1.
Kết luận X+ = Xi. Ví dụ: Cho lược đồ quan hê R(U)=(ABCDEM), với U là tập thuộc tính, tập phụ thuộc hàm F={AB -> C, C ->D, A -> E, BC ->EM} Tính bao đóng của (AB)+ BC0: Đặt X0 = AB BC1: Tồn tại A -> E F, mà A X0, E U vậy X1=X0E = ABE BC2: Tồn tại AB ->C F, mà AB X1, C U vậy X2=X1C = ABCE BC3: Tồn tại C -> D F, mà C X2, D U vậy X3=X2D= ABCDE BC4: Tồn tại BC -> EM F, mà BC X3, EM U vậy X4=X3M = ABCDEM BC5: Xét toàn bộ các phụ thuộc hàm thuộc F, thì X5 =X4 Vậy kết luận (AB)+ = X4 = ABCDEM 1.3 Định nghĩa hai tập phụ thuộc hàm tƣơng đƣơng: Để khám phá ra một tập hợp các FDs, sử dụng phương pháp phân vùng chia bản ghi của trường hợp này thành các nhóm dựa trên các giá trị khác nhau cho mỗi cột (thuộc tính). Đối với mỗi thuộc tính, số lượng các nhóm là bằng với số các giá LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 11 trị khác nhau cho các thuộc tính đó.