Tài liệu Lý thuyết tập thô & ứng dụng

LÝ THUYẾT TẬP THÔ & ỨNG DỤNG Introduction to Rough Set Theory & Application Ts. Nguyễn Đức Thuần BM. Hệ Thống Thông Tin- ĐH Nha Trang NỘI DUNG MÔN HỌC  1: Giới thiệu  2: Một số khái niệm cơ bản về Tập thô  3: Bảng quyết định  4: Cấu trúc Khái niệm Xấp xỉ  5: Lập luận tri thức  6: Một số mở rộng lý thuyết tập thô  7: Các hướng nghiên cứu & ứng dụng Page  2 Tài liệu tham khảo chính [1] Z. Pawlak, Rough Sets - Theoretical Aspect of Reasoning about Data, Kluwer Academic Pubilishers (1991). [2] J.Komorowski, Z.Pawlak, L. Polkowski, A. Skowron, Rough Sets: Tutorial, bioinf.icm.uu.se/kbib/RoughSets-Tutorial.pdf [3] https://webpages.uncc.edu/ras/RS/rs-kdd.PPT [4] Q.Zhang, Q.Xie, G. Wang, A survey on rough set theory and its applications, http://www.journals.elsevier.com/caai-transactions-on-intelligence-technology/ [5] Jaroslaw Stepaniuk, Rough – Granular Computing in Knowledge Discovery and Data Mining, Studies in Computational Intelligence, Springer, ISSN 1860949X, (2008) [6] Transaction on Rough Sets I –XIX Page  3 Giới thiệu Lý thuyết tập thô được đề xuất & phát triển bởi Gs. Zdzislaw Pawlak vào đầu những năm (19)80. Lý thuyết được công bố đầu tiên: Z. Pawlak, “Rough Sets”, International Journal of Computer and Information Sciences, Vol.11, 341356 (1982). Z. Pawlak, Rough Sets - Theoretical Aspect of Reasoning about Data, Kluwer Academic Pubilishers (1991). Zdzislaw I. Pawlak (10-11-1926 – 07-04-2006) Page  4 Giới thiệu  Lý thuyết tập thô cung cấp một công cụ để:  Phân tích, trích chọn dữ liệu từ các dữ liệu không chính xác để phát hiện ra mối quan hệ giữa các đối tượng và những tiềm ẩn trong dữ liệu.  Lựa chọn/ khai thác tính chất đặc trưng  Rút gọn dữ liệu  Tạo quy tắc ra quyết định, và khai thác mẫu (mẫu, luật kết hợp)..  Tiếp cận đến các giá trị null, thiếu dữ liệu, và các kiểu dữ liệu khác  Mô tả, phân tích và thao tác dữ liệu cũng như một cách tiếp cận đối với tính không chắc chắn và không chính xác của dữ liệu Page  5 Giới thiệu  Sự mở rộng gần đây của lý thuyết tập thô nhằm phát triển các phương pháp mới để:  Phân rã bộ dữ liệu lớn  Khai thác dữ liệu trong các hệ thống phân tán và đa tác tử (multi-agent)  Tính toán hạt (granular) Bài trình bày này thể hiện phương pháp tiếp cận thô (cổ điển) cho các bài toán nêu trên, một số chủ đề nâng cao về mở rộng tâp thô và các hướng nghiên cứu mới. Page  6 Một số khái niệm về Tập thô  Hệ thống Thông tin/ Quyết định (Information/Decision Systems) (Tables)  Không phân biệt (Indiscernibility)  Xấp xỉ Tập (Set Approximation)  Rút gọn & Nhân (Reducts and Core)  Thành viên Thô (Rough Membership)  Phụ thuộc của thuộc tính (Dependency of Attributes)  Kiến thức bổ sung: Quan hệ tương đương (Equivalence Relation) Page  7 Một số khái niệm về Tập thô Hệ thống thông tin/Bảng IS Information Systems/Tables  IS là một cặp (U, A) x１ x2 x3 x4 x5 x6 x7 Page  8 Age LEMS 16-30 16-30 31-45 31-45 46-60 16-30 46-60 50 0 1-25 1-25 26-49 26-49 26-49  U là tập hữu hạn khác rỗng các đối tượng U= {x1,x2,x3,x3,x4,x5,x6,x7}  A là tập hữu hạn khác rỗng các thuộc tính A={Age, LEMS} thỏa: aA  a : U  Va Va được gọi tập giá trị của thuộc tính a. Một số khái niệm về Tập thô Hệ quyết định DS Decision Systems/Tables Age x１ x2 x3 x4 x5 x6 x7 16-30 16-30 31-45 31-45 46-60 16-30 46-60 LEMS Walk 50 yes 0 no 1-25 no 1-25 yes 26-49 no 26-49 yes 26-49 no  DS: T  (U , A  {d })  d  A là thuộc tính quyết định (có thể có nhiều thuộc tính quyết định).  Các phần tử của A được gọi là thuộc tính điều kiện (condition attributes)  Các đối tượng tương tự hoặc không phân biệt được có thể được thể hiện nhiều lần.  Một số thuộc tính có thể không cần thiết. Page  9 Một số khái niệm về Tập thô Không phân biệt Indiscernibility  Cho IS = (U, A) là một Hệ thống thông tin, với B A xác định với một quan hệ tương đương: IND ( B)  {( x, x ')  U | a  B, a ( x )  a ( x ')} 2 IS IND ( B ) được gọi là B- quan hệ không phân biệt (B-indiscernibility relation) IS  Nếu ( x, x ')  IND ( B ), thì đối tượng x và x’ là không phân biệt với IS mỗi bộ thuộc tính B  Các lớp tương đương của x ứng với B-quan hệ không phân biệt được ký hiệu [ x]B . Page  10 Một số khái niệm về Tập thô Ví dụ về không phân biệt Age x１ x2 x3 x4 x5 x6 x7 Page  11 16-30 16-30 31-45 31-45 46-60 16-30 46-60 LEMS Walk 50 yes 0 no 1-25 no 1-25 yes 26-49 no 26-49 yes 26-49 no  Các tập con không rỗng của tập điều kiện là {Age}, {LEMS}, {Age, LEMS}.  IND({Age}) = {{x1,x2,x6}, {x3,x4}, {x5,x7}}  IND({LEMS}) = {{x1}, {x2}, {x3,x4}, {x5,x6,x7}}  IND({Age,LEMS}) = {{x1}, {x2}, {x3,x4}, {x5,x7}, {x6}}. Một số khái niệm về Tập thô Chú ý  Quan hệ tương đương tạo ra sự phân hoạch tập vũ trụ.  Các phân vùng có thể được sử dụng để xây dựng các tập con mới của tập vũ trụ.  Trong trường hợp tổng quát, một hệ quyết định có thể có nhiều thuộc tính quyết định DS= T(U,A,D), |D|1, AD=  Có một số tài liệu khi trình bày hệ quyết định, người ta ký hiệu hệ quyết định: DS= T(U,A,C,D), trong đó A: Tập tất cả thuộc tính, C: Tập thuộc tính điều kiện, D: Tập thuộc tính quyết định A=CD, CD=  Các tập con thường được quan tâm là các tập có cùng giá trị với tập thuộc tính quyết định. Page  12 Một số khái niệm về Tập thô Xấp xỉ Tập hợp Set Approximation  Cho một hệ thống thông tin S = (U, A) và R  A , X U.  Chúng ta có thể xấp xỉ X bằng thông tin được chứa trong B, bằng cách xây dựng R-xấp xỉ dưới và R-xấp xỉ trên (B-lower and Bupper ) của X ký hiệu tương ứng: RX và RX Trong đó: RX  {x | [ x]R  X }, RX  {x | [ x]R  X  }.  R-tập biên của X ( R- Boundary set of X) được định nghĩa: BN ( X )  RX  RX Page  13 Một số khái niệm về Tập thô Biểu diễn các phép xấp xỉ R-Miền ngoài của X (B-outside region ): U -RX Nếu BN(X)= thì X là tập rõ (crisp set), ngược lại X là tập thô Page  14 Một số khái niệm về Tập thô Ví dụ về Xấp xỉ tập hợp  Let W = {x | Walk(x) = yes} Age x１ x2 x3 x4 x5 x6 x7 Page  15 16-30 16-30 31-45 31-45 46-60 16-30 46-60 LEMS Walk 50 yes 0 no 1-25 no 1-25 yes 26-49 no 26-49 yes 26-49 no = {x1, x4, x6} AW  {x1, x6}, AW  {x1, x3, x 4, x6}, BN A (W )  {x3, x 4}, U  AW  {x 2, x5, x7}.  W là tập thô vì tập biên khác rỗng Một số khái niệm về Tập thô Ví dụ về Xấp xỉ tập hợp U Headache Temp. Flu u1 yes normal no u2 yes high yes u3 yes very-high yes u4 no normal no u5 no high no u6 no very-high yes u7 no high yes u8 no very-high no Page  16 Các lớp không phân biệt xác định bởi R = {Headache, Temp.} là {u1}, {u2}, {u3}, {u4}, {u5, u7}, {u6, u8}. X1 = {u | Flu(u) = yes} = {u2, u3, u6, u7} RX1 = {u2, u3} RX1= {u2, u3, u6, u7, u8, u5} X2 = {u | Flu(u) = no} = {u1, u4, u5, u8} RX2 = {u1, u4} RX2 = {u1, u4, u5, u8, u7, u6} Một số khái niệm về Tập thô Các tính chất của xấp xỉ Properties of Approximations B( X )  X  B X B( )  B( )   , B(U )  B(U )  U B( X  Y )  B( X )  B(Y ) B( X  Y )  B( X )  B(Y ) X Y Page  17  B( X )  B(Y ) và B( X )  B(Y ) Một số khái niệm về Tập thô Các tính chất của Xấp xỉ Properties of Approximations B ( X  Y )  B ( X )  B (Y ) B ( X  Y )  B ( X )  B (Y ) B( X )   B( X ) B( X )   B( X ) B ( B ( X ))  B ( B ( X ))  B( X ) B ( B ( X ))  B ( B ( X ))  B( X ) ở đây -X ký hiệu U - X. Page  18 Một số khái niệm về Tập thô Bốn lớp cơ bản của Tập thô Four Basic Classes of Rough Sets  X là B-xác định thô (roughly B-definable), nếu và chỉ nếu B ( X )   và B ( X )  U  X là B- không xác định trong (internally B-undefinable), nếu và chỉ nếu B( X )   và B( X )  U  X là B- không xác định ngoài (externally B-undefinable), nếu và chỉ nếu B( X )   và B( X )  U  X là B- không xác định hoàn toàn (totally B-undefinable), nếu và chỉ nếu B(X )   và B( X )  U Page  19 Một số khái niệm về Tập thô Bốn lớp cơ bản của Tập thô Four Basic Classes of Rough Sets  Mệnh đề: a. Tập X là B-xác định thô (roughly B-definable hay B- không xác định hoàn toàn- totally B-undefinable ), nếu và chỉ nếu tập bù –X cũng có tính chất đó. b. Tập X là B-không xác định ngoài (xác định trong) (externally Bundefinale hay internally B-undefinable) nếu và chỉ nếu tập bù –X là B-không xác định trong (xác định ngoài ). Page  20