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)
x1
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:
aA
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
x1
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
x1
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, AD=
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=CD, CD=
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
x1
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
- Xem thêm -