ĐẠI HỌC QUỐC GIA TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TÌM HIỂU MỘT SỐ LỚP TOÁN TỬ KÉO THEO VÀ ỨNG DỤNG MỘT VÀI BÀI TOÁN CỦA CƠ SỞ DỮ LIỆU MỜ NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TSKH BÙI CÔNG CƯỜNG HỌC VIÊN THỰC HIỆN: NGUYỄN THỊ HUYỀN 1 TIEU LUAN MOI download : skknchat@gmail.com 2 MỤC LỤC LỜI CẢM ƠN. 5 PHÉP KÉO THEO. Tập mờ và quan hệ mờ. Các phép toán đại số trên tập mờ.
Các phép toán cơ bản của logic mờ. Phép phủ định. Luật De Morgan. Quan hệ mờ.
Quan hệ mờ và phép hợp thành. Phép hợp thành. Phép kéo theo. Định nghĩa phép kéo theo :.
Các loại phép kéo theo mờ. Sự phân lớp các phép kéo theo mờ. Suy luận mờ với phép kéo theo. Các liên kết logic .2 Phủ định trong các mệnh đề mờ.1 Biểu biễn của luật mờ.
Sự kết hợp giữa các luật mờ. Suy luận mờ. Luật hợp thành suy diễn. Sự suy rộng modus ponens và modus tollens.
Tiêu chuẩn để suy rộng modus ponens. Suy diễn một luật dựa trên T-implication. 30 T-CHUẨN CÓ NGƯỠNG VÀ PHÉP KÉO THEO CÓ NGƯỠNG. T- chuẩn có ngưỡng.
T-chuẩn và hàm sinh. t-chuẩn có ngưỡng. t-conorm có ngưỡng. Bộ ba De Morgan.
t-chuẩn có ngưỡng và các hàm sinh. Các phương pháp suy diễn mờ sử dụng t-chuẩn có ngưỡng. Phép kéo theo có ngưỡng. 40 TIEU LUAN MOI download : skknchat@gmail.com 3 CƠ SỞ DỮ LIỆU MỜ VÀ LUẬT KẾT HỢP MỜ .Cơ sở dữ liệu mờ.
Đại số gia tử và lập luận xấp xỉ. Lập luận xấp xỉ dựa trên đại số gia tử. Tính mờ của một giá trị ngôn ngữ .Xây dựng hàm định lượng ngữ nghĩa trên cơ sở độ đo tính mờ của gia tử. Xây dựng quan hệ đối sánh trong miền trị của thuộc tính.
Phân hoạch dựa trên độ đo mờ của các giá trị ngôn ngữ trong đại số gia tử. Xấp xỉ các giá trị ngôn ngữ trong phân hoạch. Một số cách tiếp cận mô hình cơ sở dữ liệu mờ. Luật kết hợp mờ.
Luật kết hợp. Ý nghĩa của luật kết hợp .2 Một số hướng tiếp cận trong khai thác luật kết hợp. Khai thác luật kết hợp. Thuật toán Apriori nhị phân để tìm kiếm các tập thường xuyên.
Luật kết hợp có thuộc tính số và thuộc tính hạng mục .6 Phương pháp rời rạc hoá dữ liệu. Luật kết hợp mờ. Mô tả bài toán. Không gian tìm kiếm.
72 BƯỚC ĐẦU ỨNG DỤNG PHÉP KÉO THEO VÀO TÍNH TOÁN LUẬT KẾT HỢP MỜ. t-chuẩn có ngưỡng và độ ủng hộ. Cài đặt thuật toán F-Apriori. 78 Những vấn đề đã được giải quyết trong luận văn.
78 Công việc nghiên cứu trong tương lai. 78 TÀI LIỆU THAM KHẢO. 82 TIEU LUAN MOI download : skknchat@gmail.com 5 CHƢƠNG 1 PHÉP KÉO THEO 1. Tập mờ và quan hệ mờ.
Tập mờ (Fuzzy set) A là tập mờ trên không gian nền U nếu A được xác định bởi hàm: A là hàm thuộc(membership function), A(x) xác định mức độ thuộc của x vào tập mờ A Ví dụ 1: Xét một tập à bao gồm những người TRẺ, như vậy ở đây sẽ không có ranh giới rõ ràng để khẳng định một người có là phần tử của à hay không, ranh giới đó là mờ. Ta chỉ có thể nói một người sẽ thuộc tập hợp à ở một mức độ nào đó. Chẳng hạn chúng ta đồng ý với nhau một người 35 tuổi thuộc về tập hợp à với độ thuộc là 60% hay 0. Ta có hình vẽ sau: Young Old 25 50 Chúng ta cũng sẽ ký hiệu : A = {(A(x) / x) : x U}; Ví dụ 2: A0 = một vài quả cam = {(0/0),(0/1) (0.
Số mờ Tập mờ M trên đường thẳng số thực R1 là một số mờ nếu: a. M chuẩn hoá, tức là có điểm x‟ sao cho M(x‟) = 1 b. Ứng với mỗi R1 , tập mức {x: M(x) } là đoạn đóng trên R1 Số mờ có 3 dạng phổ biến: 1/ Dạng tam giác. 0 Nếu z < a 1 z – a Nếu a z b b–a M(z) = 1 Nếu z = b 0 z – a Nếu b z c a b c c–b 0 Nếu z > c TIEU LUAN MOI download : skknchat@gmail.com 6 2/ Dạng hình thang 0 Nếu z < a z – a Nếu a z b 1 b–a M(z) = 1 Nếu b z c d – z Nếu c z d 0 d–c a b c d 0 Nếu z > d 3/ Dạng hàm Gauss 1 (z – zo)2 /2 Nếu z-z0 d0 e M(z) = 0 0 Nếu z-z0 > d0 Z0 Hình 1 1.
Các phép toán đại số trên tập mờ Cho A và B là hai tập mờ trên không gian nền U Phép hợp: Phép hợp của hai tập mờ A và B, kí hiệu là A B là một tập mờ có hàm thuộc: AB(x) = max{A(x), B(x)} Phép giao: Phép giao của hai tập mờ A và B, kí hiệu là A B là một tập mờ có hàm thuộc: AB(x) = min{A(x), B(x)} Phép lấy phần bù của tập mờ A ký hiệu là Ac là tập mờ có hàm thuộc: Ac (x) = 1- A(x) 1. Các phép toán cơ bản của logic mờ Như các toán tử được định nghĩa trong tập hợp cổ điển, các toán tử tương tự như thế cũng được định nghĩa trên tập hợp mờ. Đó là phép hội, phép tuyển của hai tập hợp mờ và phép phủ định của một tập hợp mờ, các phép toán này được suy ra từ định lý của tập hợp cổ điển. Giá trị chân lý của phép hội, phép tuyển, phép phủ định được định nghĩa duy nhất trong tập hợp cổ điển như sau: TIEU LUAN MOI download : skknchat@gmail.com 7 A B AB AB A 0 0 0 0 1 0 1 0 1 1 1 0 0 1 0 1 1 1 1 0 Bảng 1 Ở trong lý thuyết tập mờ giá trị chân lý của các phép toán này không chỉ lấy hai giá trị 0 và 1 mà nó là tập hợp các giá trị trong khoảng [0,1].
Các toán tử này không được định nghĩa duy nhất. Trong phần này trình bày chi tiết các định nghĩa về phép tuyển, phép hội của các tập mờ và phép lấy phủ định của một tập mờ. Phép phủ định (negation) Phủ định là một trong những phép toán logic cơ bản, để suy rộng cần tới toán tử v(NOT P) xác định giá trị chân lý của NOT P đối với mỗi mệnh đề NOT P. Ta sẽ xét tới một số tiên đề diễn đạt những tính chất quen thuộc trong logic cổ điển: 1/ v(NOT P) chỉ phụ thuộc vào v(P) 2/ Nếu v(P) = 1 thì v(NOT P) = 0 3/ Nếu v(P) = 0 thì v(NOT P) = 1 4/ Nếu v(P1) v(P2) thì v(NOT P1) v(NOT P2) Định nghĩa 1.1 [4] Hàm n: [0,1] [0,1] không tăng thoả mãn các điều kiện n(0) = 1, n(1) = 0 gọi là hàm phủ định hay phép phủ định.2 [4] 1/ Hàm phủ định n là chặt nếu nó là hàm liên tục và giảm chặt.
2/ Hàm phủ định n là mạnh nếu n giảm chặt và n(n(x)) = x với mỗi x 1. Phép hội (conjunction) Phép hội (vẫn quen gọi là phép AND) cũng là một trong những phép toán logic cơ bản. Nó là cơ sở để định nghĩa phép giao của hai tập mờ. Ở đây ta cũng xét các tiên đề từ logic cổ điển.
TIEU LUAN MOI download : skknchat@gmail.com 8 1/ v(P1 AND P2) chỉ phụ thuộc vào các giá trị v(P1), v(P2) 2/ Nếu v(P1) = 1 thì v(P1 AND P2) = v(P2), với mọi mệnh đề P2 3/ Giao hoán: v(P1 AND P2) = v(P2 AND P1) 4/ Nếu v(P1) v(P2) thì v(P1 AND P3) v(P2 AND P3) với mọi mệnh đề P3 5/ Kết hợp: v(P1 AND (P2 AND P3)) = v((P1 AND P2 ) AND P3) Nếu diễn đạt phép hội mờ (fuzzy conjunction) như một hàm T: [0,1] x [0,1] [0,1] thì ta có định nghĩa [4] như sau: Hàm T: [0,1] x [0,1] [0,1] là phép hội hay là t-chuẩn (t-norm) nếu thoả mãn các điều kiện sau: 1/ T(1,x) = x với mọi 0 x 1 2/ T có tính giao hoán, tức là T(x,y) = T(y,x) với mọi 0 x,y 1 3/ T không giảm theo nghĩa T(x,y) T(u,v) với mọi x u, y v 4/ T có tính kết hợp : T(x, T(y,z)) = T(T(x,y),z) với mọi 0 x,y,z 1 Từ những tiên đề trên ta suy ra T(0,x), hơn nữa tiên đề 4/ đảm bảo tính thác triển duy nhất cho hàm nhiều biến. Một số ví dụ về t-chuẩn: 1/ Min (Zadeh 1965) T(x,y) = min(x,y) 2/ Dạng tích: T(x,y) = x.y 3/ t-chuẩn Lukasiewiez T(x,y) = max{x+y-1, 0} min(x,y) nếu x+y > 1 4/ min nipotent (Fodor 1993) T(x,y) = 0 nếu x+y 1 min(x,y) nếu max(x,y) = 1 5/ T-chuẩn yếu nhất Z(x,y) = 0 nếu max(x,y) <1 Ta thấy rằng Z(x,y) T(x,y) min(x,y) với mọi 0 x,y 1 TIEU LUAN MOI download : skknchat@gmail. Phép tuyển (disjunction) Giống như phép hội, phép tuyển hay toán tử logic OR thông thường cần thoả mãn các tiên đề sau: 1/ v(P1 OR P2) chỉ phụ thuộc vào các giá trị v(P1), v(P2) 2/ Nếu v(P1) = 0 thì v(P1 OR P2) = v(P2), với mọi mệnh đề P2 3/ Giao hoán: v(P1 OR P2) = v(P2 OR P1) 4/ Nếu v(P1) v(P2) thì v(P1 OR P3) v(P2 OR P3) với mọi mệnh đề P3 5/ Kết hợp: v(P1 OR (P2 OR P3)) = v((P1 OR P2 ) OR P3) Định nghĩa [4] Hàm S: [0,1] x [0,1] [0,1] gọi là phép tuyển hay là t-đối chuẩn (t- conorm) nếu thoả mãn các tiên đề sau: 1/ S(0,x) = x với mọi 0 x 1 2/ S có tính giao hoán, tức là S(x,y) = S(y,x) với mọi 0 x,y 1 3/ S không giảm S(x,y) S(u,v) với mọi x u, y v 4/ S có tính kết hợp : S(x, S(y,z)) = S(S(x,y),z) với mọi 0 x,y,z 1 1. Luật De Morgan Cho A và B là hai tập con của U, khi đó (A B)C = AC BC (A B)C = AC BC Định nghĩa 1.
Cho T là t-chuẩn, S là t-đối chuẩn, n là phép phủ định chặt. Chúng ta nói bộ ba (T,S,n) là một bộ ba De Morgan nếu: n(S(x,y) = T(nx,ny) 1. Quan hệ mờ. Quan hệ mờ và phép hợp thành.
Cho X, Y là hai không gian nền.