ĐẠI HỌC QUỐC GIA TP.HCM
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
BÀI THU HOẠCH
TOÁN
NGUYỄN HẢI TOÀN CH1301110
HUỲNH THANH VIỆT CH1301114
TRỊNH NAM VIỆT CH1301115
TP HCM, tháng 10 năm 2014
NHẬN XÉT CỦA GVHD
LÝ THUYẾT TẬP THÔ
&
ỨNG DỤNG
Lý thuyết tập thô và ứng dụng

NIỆM

CƠ

BẢN
1.1 Hệ thống thông tin và tập thô
1.1.1

Hệ

thống

thông

tin
Một

tập

dữ

liệu

có

thể

biểu

diễn

đối

tượng,

mỗi

cột

biểu

diễn

một

thuộc

tính

có

thể

đo

được
của

mỗi

đối

là

một

hệ

thống

thông

tin.

Hình

thức

hơn,

hệ

thống

thông

tin

là

một



là

tập

vũ

trụ

hay

là

tập
phổ

dụng,

A

là

một

tập

hữu

hạn



trị

của

đối

tượng

u

tại

thuộc

tính

a.

Nếu

gọi

I
a

là

tập tất


giờ,

nếu

B

=

{b
1
,

b
2
,

,b
k
}

⊆

A,
ta

ký

hiệu

bộ


đối

tượng,

thì

ta
sẽ

viết

u(B)

=

v(B)

nếu

u(b
i
)

=

v(b
i
),


thống

thông

tin

S

=

(U,

A),

với

mỗi

tập

thuộc

tính

B

⊆

A


u(a)

=

v(a),∀a ∈ B}
IND(B) được gọi là quan hệ B_không phân biệt được. Dễ kiểm chứng đây là một
quan hệ tương đương trên U. Với mọi đối tượng u U, lớp tương đương của u
trong quan hệ IND(B) được kí hiệu bởi [u]B. Tập thương xác định bởi quan hệ
IND(B) được ký hiệu U/IND(B) hay U/B, tức là U/IND(B) = U/B = {[u]B |
u U}
6
Lý thuyết tập thô và ứng dụng
Ví

dụ

1.1

Xét

hệ

thống

thông

tin

cho



thường Không
x
5
Có Không Cao Không
x
6
Không Có Rất

cao Có
Bảng

1.1

Bảng

dữ

liệu

bệnh

cúm
Trong

đó:

U

=

đầu,

Đau

cơ,

Nhiệt

độ,

Cúm}.
Trong

bảng,

các

bệnh

nhân

x
2
,

x
3

và



x
6

không

phân

biệt

được

đối

với

thuộc

tính

Đau

cơ,
Cúm

và
b
ệnh

nhân


và

Nhiệt

độ.
Do

đó:
IND({Đau

đầu})

=

{{x
1
,

x
4
,

x
6
},{x
2
,

x

,

x
5
}},
IND({Nhiệt

độ})

=

{{x
1
,

x
2
,

x
5
},

{x
3
,

x
6
},

x
5
}},
IND({Đau

đầu,

Đau

cơ})

=

{{x
1
,

x
4
,

x
6
},

{x
2
,

x


phận

p

xác

định

trên

họ

{U/B|

B
⊆

A}
đ
ược

định

nghĩa:

nếu

và


nói

Q

là

thô hơn

P

hay

P

là

mịn

hơn

Q.
1.1.3

Tập

thô
Lý thuyết tập thô (Rough set) được đề xuất vào năm 1982 bởi Z.Pawlak. Lý
thuyết này xây dựng phương pháp luận liên quan đến sự phân loại và
phân tích không chắc chắn, thông tin và tri thức không đầy đủ và được coi là một
trong những phương pháp tiếp cận đầu tiên không dựa trên thống kê trong phân


một

tập

hợp

bằng

tri

thức

được

cho

xác
định

bởi

một

tập

thuộc

tính,


(U,

A),

với

mỗi

tập

con

X

⊆

U

và

B

⊆

A,

ký

hiệu R
=

ta

định

nghĩa

các

tập:
Ký

hiệu

tập

thương

của

IND(B)

trên

U

là

U/B,

các


≠

∅,

X

được

gọi

là

tập

thô,
ngược

lại

X

được

gọi

là

tập


⊆

A,

ký

hiệu

R

=

IND(B),

người ta
gọi

B-miền

khẳng

định

dương

của

D

là

đối

tượng

u

sao

cho

với

mọi

v∈U
mà u(B)

=

v(B)

ta

đều

có

u(D)

=


tính

chất

của

xấp

xỉ
Định

lý

1.1.

[34]

Cho

một

hệ

thống

thông

tin



đó:
10
Lý thuyết tập thô và ứng dụng
Tính

chất

(3L),

(4L)

và

(8L)

là

những

tính

chất

đặc

trưng

cho



xỉ

dưới

có

thể

suy

dẫn

từ
ba

tính

chất

này.

Tương

tự,

(3H),

(4H)


chính

xác

của

xấp

xỉ
Cho

một

hệ

thống

thông

tin

S

=

(U,

A),

với

đo

sự

chính

xác

của

tập

xấp

xỉ

X

đối

với

phân

hoạch

trên

B


X.

Rõ

ràng

0
≤
α
R

(X )

≤1.

Nếu

α
R

(X )

=1,

ta

nói

X


với

R.
1.1.6

Bảng

quyết

định
Bảng

quyết

định

là

một

hệ

thống

thông

tin

có


thuộc

tính

rời

nhau

C

và

D,

C

được

gọi

là
tập

thuộc

tính

điều

kiện,

C∩D

=

∅.

Trong

trường

hợp

không

sợ

bị

nhầm

lẫn
người

ta

còn

ký

hiệu


diễn

cơ

sở

tri

thức

về

bệnh

cúm
được

thể

hiện

trong

bảng

1.1

là


3
,

x
4
,

x
5
,

x
6
}.
A

=

{Đau

đầu,

Đau

cơ,

Nhiệt

độ,



tính

quyết

định

D

={Cúm}
U
Đau

đầu
Đau

cơ
Nhiệt

độ
Cúm
x
1
Không Có Cao Có
12
Lý thuyết tập thô và ứng dụng
x
2
Có Không Cao Có
x

=

(U,

C∪D),

giả

sử

U/C

=

{X
1
,

X
2
, ,

X
m
}

và

U/D



nếu

u(d)

=

v(d),

∀u,v∈X
i
,
∀d∈D,

lúc

này

cũng

có

thể

viết

u(D)

=



v(a),

∀u,v∈Y,

∀a∈C
Một

bảng

quyết

định

T

=

(U,

C∪D)

là

nhất

quán

nếu



Dễ

thấy

nếu

U/C

U/D

thì

T

=
(U,C∪D)

là

nhất

quán.
Tương

tự,

nếu

U/D U/C,


và

chỉ

khi

POS
C
(D)

=

U.
Trong

trường

hợp

bảng

không

nhất

quán

thì



→

D

đúng.
1.1.7

Rút

gọn

và

nhân
Xét

một

bảng

quyết

định

T

=

(U,

nếu

POS
R
(D)=POS
C
(D).
Nhân

của

tập

thuộc

tính

điều

kiện

C

ký

hiệu

CORE

(C)


của

C.
13
Lý thuyết tập thô và ứng dụng
Ngoài

ra,

người

ta

cũng

định

nghĩa

rút

gọn

C-miền

khẳng

định


{a}
(D)
B

được

gọi

là

rút

gọn

C-miền

khẳng

định

dương

của

D.
1.1.8

Ma

trận

C∪D),

với

U

=

{u
1
,

u
2
,

,

u
n
}.

Ma

trận

phân

biệt
được

đối

xứng,

trong

đó

mỗi

phần

tử
của nó

là

một

tập

thuộc

tính

được

xác

định

từ

ma

trận

phân
biệt

M(
T
)

như

sau
:
trong

đó,

mỗi

thuộc

tính

được

đặt

C∪D)

là

một

bảng

quyết

định,

giả

sử

U/C

=

{X
1
,

X
2
,

,



ký

hiệu

des(X
i
),

des(Y
j
)

lần

lượt

là

các

mô

tả

của

các
lớp


,

Y
j

có

dạng:
14
Lý thuyết tập thô và ứng dụng
Độ

đo

độ

chắc

chắn

và

độ

hỗ

trợ

của


Z
ij

rơi vào đoạn .Để thuận tiện trong trình bày ký hiệu ta
thay bằng .
1.1.10

Phụ

thuộc

độ

k
Cho

hệ

thống

thông

tin

S

=

(U,



k∈[0,1]

vào

tập

thuộc

tính

X,

ký

hiệu

,

với

k

được

xác

định

như


thuộc

hàm

và là
phụ thuộc hàm đã biết trong CSDL quan hệ.
15
Lý thuyết tập thô và ứng dụng
Chương 2
PHỦ TẬP THÔ
Chương

này

nhóm em tìm hiểu

sự

mở

rộng

tập

thô

theo

hướng

toán

học

của

các

phép

xấp

xỉ
ứng

với

ba

loại

phủ

do

W.

Zhu

và

được

tiếp

cận

bằng

công

cụ

toán

học

là

không

gian

topo

của

một

số



xấp

xỉ.

Cuối

chương,

bài thu
hoạch

sẽ trình bày

thuật

toán

rút

gọn

tập

thuộc

tính

dựa


quả

nghiên

cứu

của

mình

[37,

38],

W.

Zhu

và
F.YWang

đã

đưa

ra

hệ

tiên

tìm

tính

chất

đặc

trưng

của

các

phép

xấp

xỉ

phủ

trên

(loại

1,

2,



kiện

để

hai

phủ

sinh

cùng

xác
định

một

phép

xấp

xỉ

phủ

loại

2.



được

khảo

sát

nhằm

có

thể

sử

dụng

các

kết

quả

ứng

dụng

của

ánh


loại

1
a.

Sự

phụ

thuộc

xấp

xỉ

dưới

và

xấp

xỉ

trên

loại

1
W.


dưới

và

xấp

xỉ
phủ

trên

loại

1

thông

qua

các

định

lý
Định

lý

2.1


sinh

ra

cùng

phép
xấp

xỉ

phủ

dưới

(loại

1,

2,

3)

nếu

và

chỉ



là

hai

phủ

của

U,

C
1

và

C
2

sinh

ra

cùng

phép
xấp

xỉ



2.3

[38]

Cho

C
1
,

C
2

là

hai

phủ

của

U,

C
1

và

C


cùng

sinh

ra

xấp

xỉ

phủ

trên

loại

1.
b.

Tiên

đề

cho

phép

xấp



tồn

tại

1

phép

toán

L:
17
Lý thuyết tập thô và ứng dụng

thì

tồn

tại

một

phủ

C

của

U

bốn

tính

chất

trên

của

phép

xấp

xỉ

phủ

dưới

là

độc

lập.

((1L)-(7L)

là



1.1.4).
c.

Tiên

đề

cho

phép

xấp

xỉ

phủ

trên

loại

1
Các

tính

chất

(1L)

dưới,

phép

xấp

xỉ

trên

trong

tập

thô

cổ

điển.

Định

lý

2.4

chỉ

ra



toán

xấp

xỉ

phủ

dưới.
Tuy

nhiên,

các

tính

chất

(1H),

(2H),

(3H)

và

(5H)



thể

thấy

được

qua

ví

dụ
Ví

dụ

2.1

[38,

40]

Một

phép

toán

H
:

tại

một

phủ

C

của

U

mà

H

là

một

phép

xấp

xỉ

phủ trên

loại





P
(U)

như

sau
Hiển

nhiên

H

thỏa

các

tính

chất

(1H),

(2H),

(3H)

và

xỉ

phủ

trên

loại

1

sinh

ra

bởi

C
.

Thật

vậy,

nếu

có

thì

phủ

{a,b}

≠{a,b,c}=
H
({a,b}).

Do

đó

H

không

là

phép

xấp

xỉ

phủ trên

loại

1

sinh


1

vẫn

còn

là

bài

toán

mở.
18
Lý thuyết tập thô và ứng dụng
2.1.2
Xấp

xỉ

phủ

tập

thô

loại

2
Tương


xấp

xỉ

phủ

tập

thô
loại

2

được

công

bố

trong

[37,

38,

40].

Định



phủ

dưới

tập

thô

loại

1,

sự khác

biệt

là

ở

xấp

xỉ

phủ
trên.Mối

quan



niệm

rút

gọn

phủ

tỏ

ra

không

hữu

dụng

trong

mối

quan

hệ

giữa

xấp

loại

3
20
Lý thuyết tập thô và ứng dụng
a.

Sự

phụ

thuộc

xấp

xỉ

phủ

dưới

và

xấp

xỉ

phủ

trên

và

reduct(
C
)

sinh

ra

cùng

các

phép
xấp

xỉ

phủ

dưới

và

xấp

xỉ

phủ

của

U,

nếu

reduct

(
C
1
)

=

reduct(
C
2
),

thì

C
1
và

C
2

sinh

lý

trên

là

không

đúng,

ta

có

phản

ví

dụ
Phản

ví

dụ

2.3

Cho

U

=

{a,

c}, K
4
={a, b,
c},

C
1

=

{K
1
,

K
2
,

K
3
}

and

C
2


ra

bởi

hai

phủ

C
1

và

C
2

đều

là

X
#

=

{a

,b,
c},

[38,

40]

Cho

C
1
,

C
2

là

các

phủ

của

U,

nếu

C
1

và


xỉ

phủ

trên

loại

3.
b.

Tiên

đề

cho

các

phép

xấp

xỉ

phủ

trên

loại

phủ

xấp

xỉ

trên

loại

3

chưa
thể

tiên

đề

hóa

do

nhiều

tính

chất

đặc

phép

toán

thỏa

(1H),

(2H),

(3H),

(4H),

và

(7H)

nhưng
không

là

xấp

xỉ

phủ

trên



P
(U)
như
sau:

H
(∅)

=

∅,

H
({a})

=

{a,

b},

H
({b})

=

{b,



c})

=

U,

H
(U)

=

U.

Hiển

nhiên

H

thỏa

(1H),

(2H),

(3H)
21
Lý thuyết tập thô và ứng dụng
2.2 Mối quan hệ giữa ba loại phủ tập thô


C
2

cùng

xác

định

xấp

xỉ
phủdưới

và

xấp

xỉ

phủ

trên

loại

2

nếu

và

C
2

là

các

phủ

nửa

thu

gọn
Hệ

quả

2.1

Cho

C
1
,

C
2


và
xấp

xỉ

trên

phủ

loại

2,

nếu

chúng

thỏa

các

điều

kiện

sau
1.

reduct(


minh:

Kết

quả

được

suy

dẫn

trực

tiếp

từ

định

lý

2.12

và

2.13.
Mệnh


sinh

ra

cùng

xấp
xỉ

trên

loại

2

(ngay

cả

khi

reduct(
C
)

là

một

phân

ví

dụ

2.5

Cho

U

=

{a,

b,

c},

K
1

=

{a},

K
2

= {b},



Ta

có

reduct(
C
)

=

{K
1
,K
2
,K
3
}.

Nếu

X

=

{c},

thì

X


phép

xấp

xỉ

phủ

trên

ứng

với

phủ

đơn

vị
Mệnh

đề

2.2

Cho

C


C

thỏa

tính

chất:

∀X,Y

⊆

U,

X

⊆

Y

⇒

FH(X)

⊆

FH(Y) (tính

đồng


tổng

kết

2.1,

nếu

C

là

(phủ)

đơn

vị

thì

FH

=

TH.

Do

TH


(phủ)

đơn

vị

FH

thỏa

tính

đơn

điệu

và

TH

thỏa

tính

lũy

đẳng.

Tuy



dụ

2.6

Cho

U

=

{a,

b,

c,

d},

K
1

=

{a,

b},

K
2


C

là

một

phủ

đơn

vị

của

U.

Với

X

=

{c},

chúng

ta

có

≠

SH(SH(X))

=

{a,

b,

c,

d}.
2.4.2
Tính

chất

ánh

xạ

đóng

của

ba

phép



phủ

của

U.

Nếu

C

là

phủ

tựa

điểm

thì

FH

sinh

bởi

C

thỏa


biến)
23
Lý thuyết tập thô và ứng dụng
Chứng

minh

Từ

định

nghĩa

của

phủ

tựa

điểm

và

FH.

Nếu

C



rằng
24
Lý thuyết tập thô và ứng dụng
2.5 Mối quan hệ giữa các phép xấp xỉ phủ dựa vào không gian topo
Nhiều

tác

giả

trên

cơ

sở

lý

thuyết

không

gian

topo

đã

đề

một

số

điều

kiện

để

các

phép
xấp

xỉ

dựa

vào

phủ

do

Y.Yao,

W.

Zhu,

ngôi

và

không

gian

topo
a.

Không

gian

topo

được

xây

dựng

từ

một

quan

hệ

trên

U,

cặp

(U,

R)

được

gọi

là

một

không

gian

xấp

xỉ

xác

định


trái,

phải

của

một

phần

tử

x

thuộc

U

lần

lượt

như

sau
l
R
(x)

=

τ
1

sử

dụng

R-láng

giềng

phải

(tương

tự,

topo

τ
2

sử

dụng

R-
láng

giềng

một

tiền

cơ

sở

của

topo

τ
1

và

ký

hiệu

S
x

=

{G

∈



R.
b.

Không

gian

topo

được

xây

dựng

từ

một

họ

phủ
Một

hệ

thống

thông


tượng,

A

là

một

tập

hữu

hạn

khác

rỗng

các

thuộc

tính.

Với

mỗi

thuộc

∈

U,

u

R
a

v

khi

và

chỉ

khi

u(a)∩v(a)

≠

∅
Với
định

nghĩa

này,


quan

25