Xem mẫu
-
Luận văn tốt nghiệp
Tiếp cận lý thuyết tập thô do Z.Pawlak
- 1
M cl c
Danh m c các thu t ng 2
B ng các ký hi u 3
Danh sách b ng 4
Ph n m đ u 6
Chương 1. Các khái ni m cơ b n 10
1.1. Gi i thi u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2. H th ng thông tin và t p thô . . . . . . . . . . . . . . . . . . . . . . 11
1.2.1. H th ng thông tin . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.2. Quan h không phân bi t đư c . . . . . . . . . . . . . . . . . 12
1.2.3. Các t p x p x . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2.4. Các tính ch t c a x p x . . . . . . . . . . . . . . . . . . . . . 15
1.2.5. Đ chính xác c a x p x . . . . . . . . . . . . . . . . . . . . . 16
1.3. B ng quy t đ nh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3.1. Rút g n và lõi . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.3.2. Ma tr n và hàm phân bi t đư c . . . . . . . . . . . . . . . . . 18
1.3.3. Lu t quy t đ nh . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.4. Ph thu c x p x . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
- 2
1.4.1. Hàm thành viên thô . . . . . . . . . . . . . . . . . . . . . . . 24
1.4.2. Ph thu c hàm x p x . . . . . . . . . . . . . . . . . . . . . . 25
1.4.3. Rút g n x p x . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Chương 2. M t s thu t toán tìm t p rút g n 31
2.1. M đ u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
2.2. Thu t toán s d ng các phép toán đ i s . . . . . . . . . . . . . . . . 32
2.2.1. T p lõi trong b ng quy t đ nh . . . . . . . . . . . . . . . . . . 32
2.2.2. Đ c trưng c a t p rút g n . . . . . . . . . . . . . . . . . . . . 36
2.2.3. Các thu t toán . . . . . . . . . . . . . . . . . . . . . . . . . . 39
2.3. Thu t toán d a vào s c p phân bi t đư c . . . . . . . . . . . . . . . 43
2.3.1. M t s ký hi u . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2.3.2. Cơ s toán h c . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.3.3. Thu t toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
2.4. Thu t toán tìm rút g n x p x . . . . . . . . . . . . . . . . . . . . . . 52
2.4.1. Đ t v n đ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
2.4.2. Sai s c a rút g n x p x . . . . . . . . . . . . . . . . . . . . . 52
2.4.3. Các thu t toán tìm rút g n x p x . . . . . . . . . . . . . . . 54
Chương 3. Khám phá ph thu c đa tr 58
3.1. M đ u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.2. Kh o sát ph thu c b ng Ma tr n ph thu c . . . . . . . . . . . . . . 60
3.2.1. Ph thu c và ph thu c x p x . . . . . . . . . . . . . . . . . 60
3.2.2. Đ c trưng ph thu c b ng ma tr n ph thu c . . . . . . . . . 63
- 3
3.3. Thu t toán ki m đ nh và tìm ki m ph thu c . . . . . . . . . . . . . 69
3.3.1. Thu t toán tính đ d y đ c c a dãy ma tr n . . . . . . . . . . 69
3.3.2. Thu t toán ki m đ nh ph thu c x p x . . . . . . . . . . . . 73
3.3.3. Thu t toán tìm ki m ph thu c t i ti u v ph i . . . . . . . . 75
3.4. M r ng ph thu c hàm và ph thu c đa tr . . . . . . . . . . . . . . 77
3.4.1. Quan h tương t . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.4.2. Ph thu c m r ng và các tính ch t . . . . . . . . . . . . . . . 81
3.4.3. Đ c trưng β −ph thu c b ng ma tr n ph thu c . . . . . . . 84
3.4.4. Thu t toán ki m đ nh β −ph thu c đa tr . . . . . . . . . . . 88
3.5. K t lu n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
Ph n K t lu n 92
Tài li u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
- 4
Chương
DANH M C CÁC THU T NG
H th ng thông tin ()
T p thô (Rough Set)
Quan h không phân bi t đư c
T p x p x dư i
T p x p x trên
B ng quy t đ nh
Rút g n
Lõi
Ma tr n phân bi t đư c
Hàm phân bi t đư c
Lu t quy t đ nh
Ph thu c hàm
Ph thu c đa tr
Ph thu c x p x
- 5
Chương
B NG CÁC KÝ HI U
A = (U, A): H th ng thông tin.
u(a): Giá tr c a đ i tư ng u t i thu c tính a.
IND(B ): Quan h B −không phân bi t đư c.
IND(B |V ): Quan h B −không phân bi t đư c c m sinh trên t p V .
[u]B : L p tương đương ch a u c a quan h IND(B ).
U/B : T p h p thương c a quan h IND(B ).
V /B : T p h p thương c a quan h IND(B |V ).
B V : B −x p x dư i c a V .
BV : B −x p x trên c a V .
POSB (D) : B −mi n kh ng đ nh c a D.
T = (U, C ∪ D): B ng quy t đ nh.
Lower[B ]/[D] : B −x p x dư i tương ng v i D c a U .
Upper[B ]/[D] : B −x p x trên tương ng v i D c a U .
Boundary[B ]/[D] : B −biên tương ng v i D c a U .
k (R, D): Đ ph thu c c a t p thu c tính quy t đ nh D vào t p con các thu c
- 6
tính đi u ki n R.
m(cj , R): Kh năng đóng góp c a thu c tính cj vào R.
V
ωB (cj ): S c p đ i tư ng c a V b ng nhau trên t p thu c tính B nhưng khác
nhau t i thu c tính cj .
V
ωB (D): S c p đ i tư ng c a V b ng nhau trên t p thu c tính B nhưng khác
nhau trên t p thu c tính D.
ω V (cj ): S c p đ i tư ng c a V khác nhau t i thu c tính cj .
ω V (D): S c p đ i tư ng c a V khác nhau trên t p thu c tính D.
ωB (cj ): S c p đ i tư ng c a U b ng nhau trên t p thu c tính B nhưng khác
nhau t i thu c tính cj .
ωB (D): S c p đ i tư ng c a U b ng nhau trên t p thu c tính B nhưng khác
nhau trên t p thu c tính D.
X →: Y không ph thu c hàm vào X trên U .
Y
X → Y : Y không ph thu c đa tr vào X trên U .
→
/
X →V Y : Y ph thu c hàm vào X đúng trên t p con V ⊆ U .
X →→V Y : Y ph thu c đa tr vào X đúng trên t p con V ⊆ U .
α,β
X −→ Y : Y là (α, β )− ph thu c hàm vào X trên U .
α,β
X →→ Y : Y là (α, β )− ph thu c đa tr vào X trên U .
- 7
Danh sách b ng
1.1 B ng d li u các đ chơi. . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2 Các tri u ch ng c a b nh nhân. . . . . . . . . . . . . . . . . . . . . . 14
1.3 B ng quy t đ nh v b nh cúm. . . . . . . . . . . . . . . . . . . . . . 18
B ng rút g n th nh t c a h th ng b nh cúm (R1 ). . . . . . . . . . 19
1.4
B ng rút g n th hai c a h th ng b nh cúm (R2 ). . . . . . . . . . . 19
1.5
1.6 D li u b ng quy t đ nh. . . . . . . . . . . . . . . . . . . . . . . . . . 20
Ma tr n phân bi t đư c M. . . . . . . . . . . . . . . . . . . . . . . . 21
1.7
1.8 B ng ch n ng c viên vào ng ch gi ng d y. . . . . . . . . . . . . . . 24
1.9 B ng d li u. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.1 B ng thông tin v các xe hơi. . . . . . . . . . . . . . . . . . . . . . . 35
2.2 B ng d li u các đ chơi. . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.3 B ng ch n l a giáo viên. . . . . . . . . . . . . . . . . . . . . . . . . . 49
2.4 B ng d li u cho ví d rút g n x p x . . . . . . . . . . . . . . . . . . 54
3.1 B ng d li u sinh viên. . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.2 D li u c a h th ng. . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
3.3 B ng d li u v các l p trình viên . . . . . . . . . . . . . . . . . . . . 80
- 8
Quan h tương t trên Ib . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.4
Quan h tương t trên Ic . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.5
3.6 D li u c a h th ng. . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
Các quan h tương t trên IX , IY và IZ . . . . . . . . . . . . . . . . . 83
3.7
3.8 B ng d li u. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
Các quan h tương t trên IY và IZ . . . . . . . . . . . . . . . . . . . 86
3.9
- 9
Chương
PH N M ĐU
Lý thuy t t p thô do Zdzisaw Pawlak [24] đ xu t vào nh ng năm đ u th p
niên tám mươi c a th k hai mươi đã đư c áp d ng ngày càng r ng rãi trong nhi u
lĩnh v c c a khoa h c máy tính. Lý thuy t t p thô đư c phát tri n trên m t n n
t ng toán h c v ng ch c và cung c p nh ng công c h u ích đ gi i quy t các bài
toán phân l p d li u, phát hi n lu t v.v... đ c bi t thích h p đ i v i nh ng bài
toán ch a d li u mơ h không ch c ch n.
Mư i lăm năm tr l i đây đã đánh d u s phát tri n m nh m c a lĩnh v c
khai phá d li u và phát hi n tri th c trong cơ s d li u. Trong xu th đó, nhi u
nhóm khoa h c trên th gi i đã nghiên c u, phát tri n lý thuy t t p thô vào lĩnh v c
nghiên c u và ng d ng n i b t này. V phương di n nghiên c u phát tri n ng d ng
lý thuy t t p thô vào các lĩnh v c như ngân hàng, tài chính, sinh h c (bi u th gen),
... có th k đ n các công trình nghiên c u [7, 8, 9, 10, 11, 12, 13, 18, 19, 20, 23, 27].
V phương di n nghiên c u phát tri n mô hình và gi i pháp theo ti p c n t p thô
có th k đ n các công trình [14, 26] quan tâm đ n các bài toán tính toán lõi và rút
g n, ho c các công trình [15, 16, 17, 25, 31, 32] nghiên c u tìm ki m các ràng bu c
trong d li u.
Lý thuy t t p thô cho phép trình di n m t mô hình hình th c v tri th c t
b ng d li u đơn thu n. Mô hình này đư c xác đ nh như h các m i quan h "không
- 10
phân bi t đư c", nh đó tri th c đư c đ nh nghĩa m t cách rõ ràng dư i d ng toán
h c và có th đư c phân tích và x lý b ng nh ng công c m nh m và hi u qu
c a toán h c.
Trong lý thuy t t p thô, mô hình bi u di n d li u đư c trình bày thông qua h
thông tin hay b ng quy t đ nh và ý tư ng chính trong vi c phân tích d li u xu t
phát t khái ni m "không phân bi t đư c". V i cách ti p c n như v y, lý thuy t t p
thô cho phép phát hi n tri th c t nh ng b ng d li u l n v i d li u đa d ng, ph c
t p, chưa tinh l c nh m phát hi n ra nh ng quy lu t ti m n t kh i d li u này.
Tri th c đư c bi u di n dư i d ng các m u mô t m i quan h b che d u trong
d li u. Trong lý thuy t t p thô, ch t lư ng c a thông tin đư c đo thông qua các
khái ni m x p x trên và x p x dư i. Nh m thu h p nhi u nh t kích thư c d li u
đ n mi n thông tin chính xác, ý tư ng rút g n đư c s d ng đ cho phép lo i b
nh ng thông tin dư th a, không c n thi t mà v n gi đư c các tính ch t x p x
cơ b n c a h th ng. N u tìm đư c nh ng quy lu t chung nh t bi u di n d li u,
ngư i ta có th tính toán đ m nh c a các thu c tính ho c đ ph thu c gi a chúng
trong h thông tin. Vì vâ v n đ phát hi n lu t theo ti p c n t p thô đư c đ t ra
là hoàn toàn t nhiên.
M c tiêu c a đ tài lu n án là nghiên c u khía c nh đ i s và logic c a bài
toán phát hi n lu t theo ti p c n t p thô. Đây là m t hư ng nghiên c u r t r ng,
bao g m nhi u v n đ đang đư c các nhà khoa h c nghiên c u xem xét. Lu n án
ch t p trung vào hai v n đ , m t là tìm các t p rút g n c a b ng quy t đ nh, hai
là v n đ phát hi n các m i ràng bu c có trong d li u. C hai v n đ này đ u đư c
phân tích và xem xét d a vào các công c c a lý thuy t t p thô mà n n t ng là
quan h "không phân bi t đư c".
V i m c tiêu đó, n i dung lu n án đư c trình bày trong ba chương. Chương
M t trình bày m t cách t ng quan v các khái ni m cơ b n trong lý thuy t t p thô
như là h th ng thông tin, quan h không phân bi t đư c, x p x dư i, x p x trên,
b ng quy t đ nh, rút g n, lõi, ma tr n phân bi t đư c. Các khái ni m liên quan t i
- 11
x p x cũng đư c gi i thi u sơ b trong chương này như hàm thành viên thô, ph
thu c hàm x p x , rút g n x p x .
Chương Hai trình bày các thu t toán tìm t p rút g n c a b ng quy t đ nh.
Các thu t toán này đư c chia làm hai nhóm. Nhóm th nh t bao g m hai thu t
toán (Thu t toán 2.2 và Thu t toán 2.3) d a vào khái ni m đ ph thu c c a t p
thu c tính quy t đ nh vào t p con các thu c tính đi u ki n; và v i khái ni m m i
này, chúng tôi đã đưa ra đánh giá v kh năng đóng góp c a m t thu c tính khi
tham gia đóng vai trò thành viên c a t p rút g n. Nhóm th hai ch bao g m m t
thu t toán (Thu t toán 2.4) tìm t p rút g n d a theo ý tư ng xây d ng ma tr n
phân bi t đư c, tuy nhiên đây, các ph n t c a ma tr n (là các t p h p) không
h đư c tính toán. Thay vào đó, chúng tôi phân tích các đ i tư ng có giá tr quy t
đ nh khác nhau có m i tương quan như th nào đ i v i các giá tr trên t p thu c
tính đi u ki n. Trên cơ s đó, chúng tôi đã đưa ra tiêu chu n c a t p rút g n d a
vào s c p đ i tư ng phân bi t đư c b i m t t p các thu c tính. C ba thu t toán
đư c xây d ng trong chương này đ u là các thu t toán heuristic và có đ ph c t p
tính toán theo th i gian là đa th c, do đó có th áp d ng đư c trên b ng d li u
v i kích thư c l n.
N i dung c a Chương Ba t p trung vào v n đ th hai liên quan t i khái ni m
ph thu c trong lý thuy t cơ s d li u quan h . C th là, trong chương này chúng
tôi kh o sát các ph thu c hàm và ph thu c đa tr ti m n trong b ng d li u có
s n. Đ ki m ch ng ph thu c đa tr đúng trên t p các đ i tư ng, chúng tôi đã mô
t đ c trưng c a ph thu c đa tr b ng m t h các ma tr n ph thu c. Do d li u
trong th c t thư ng r t l n và có th b nhi u, nên các ph thu c đúng ti m n
trong d li u có th khó phát hi n. Vì v y chúng tôi đã nghiên c u các ph thu c đa
tr đúng trên h u h t các đ i tư ng trong b ng, g i là ph thu c x p x , đ ng th i
đưa ra đánh giá v sai s c a ph thu c d a vào khái ni m đ d y đ c c a h các
ma tr n ph thu c. Ph n cu i c a Chương Ba, chúng tôi xây d ng các ph thu c
hàm và ph thu c đa tr m r ng b ng cách thay quan h b ng nhau trên các giá
- 12
tr thu c tính b i quan h tương t . M t đi u khá thú v là các ph thu c m r ng
này cũng đư c đ c trưng b i h các ma tr n ph thu c tương ng.
- Chương Chương 1.
CÁC KHÁI NI M CƠ B N
1.1. Gi i thi u
Ngay t khi xu t hi n, lý thuy t t p thô do Zdzisaw Pawlak [24] kh i xư ng
vào nh ng năm đ u th p niên tám mươi c a th k hai mươi đã ngay l p t c thu
hút s quan tâm c a nhi u nhà nghiên c u và th c nghi m trên toàn th gi i. Kh
năng ng d ng trong nhi u lĩnh v c khác nhau cho th y vai trò quan tr ng c a lý
thuy t này trong vi c nghiên c u và ng d ng công ngh thông tin trong th i đ i
m i.
Lý thuy t t p thô có th đư c xem xét theo hai phương di n là mô hình và th c
hành. Theo phương di n mô hình, lý thuy t t p thô cho m t cách ti p c n m i cho
tính mơ h . Các khái ni m mơ h đư c đ c trưng b i m t "mi n biên" ch a t t c
các ph n t mà không th g p vào mi n các đ i tư ng quan sát ho c ph n bù c a
mi n này. Lý thuy t t p thô đư c nghiên c u và phát tri n nh m hi u t t hơn ý
tư ng c a tính mơ h . Nó cũng xét đ n m t vài ý tư ng c a Gottfried Leibniz (tính
không phân bi t đư c), George Boole (các phương pháp suy lu n), Jan Lukasiewicz
(các logic đa tr ) và Thomas Bayes (suy lu n quy n p). V phương di n th c hành,
lý thuy t t p thô là ý tư ng n n t ng cho trí tu nhân t o và khoa h c nh n th c,
đ c bi t cho h c máy, phát hi n tri th c, phân tích quy t đ nh, suy lu n quy n p
- 14
và nh n d ng m u. Nó là r t quan tr ng cho các nghiên c u v h tr giúp quy t
đ nh và khai phá d li u. Th c t ti p c n lý thuy t t p thô là m t cách ti p c n
m i cho vi c phân tích d li u.
B n ch t toán h c ch t ch làm cho các n i dung cơ s c a lý thuy t t p thô có
th đư c n m b t và ng d ng m t cách d dàng. Các h th ng ph n m m s d ng
lý thuy t t p thô (đi n hình như ROSETTA) đã đư c cài đ t và nhi u ng d ng
quan tr ng trong đ i s ng c a phương pháp lu n này đã đư c xây d ng, ch ng h n
trong y h c, dư c h c, k thu t, ngân hàng, nh n d ng m u, bi u th gien v.v...
B n ch t toán h c ch t ch làm cho lý thuy t này không mâu thu n mà còn
b sung cho các phương pháp đã có và dĩ nhiên cũng có th đư c s d ng đ ng th i
v i các cách ti p c n khác.
M c đích chính c a s phân tích t p thô là đưa ra các t p x p x đ bi u di n
các đ i tư ng không th đư c phân l p m t cách ch c ch n b ng cách dùng tri th c
có s n. Theo cách ti p c n c a lý thuy t t p thô, m i t p thô đư c liên k t v i hai
t p "rõ" là x p x dư i và x p x trên c a nó. X p x dư i bao g m các đ i tư ng
ch c ch n thu c, còn x p x trên ch a t t c các đ i tư ng có kh năng thu c v
t p đó. Các t p x p x là cơ s đ đưa ra các k t lu n t d li u.
1.2. H th ng thông tin và t p thô
1.2.1. H th ng thông tin
H th ng thông tin là m t c p A = (U , A), v i U là t p h u h n, khác r ng,
đư c g i là t p vũ tr các đ i tư ng và A là t p h u h n khác r ng các thu c tính.
V i m i u ∈ U và a ∈ A, ta ký hi u u(a) là giá tr c a đ i tư ng u t i thu c tính a.
N u g i Ia là t p t t c các gía tr c a thu c tính a, thì u(a) ∈ Ia v i m i u ∈ U .
Bây gi , n u B = {b1 , b2 , · · · , bk } ⊆ A là m t t p con các thu c tính thì ta s ký
hi u b các giá tr u(bi ) b i u(B ). Như v y, n u u và v là hai đ i tư ng, thì ta s
- 15
vi t u(B ) = v (B ) n u u(bi ) = v (bi ), v i m i i = 1, · · · , k .
1.2.2. Quan h không phân bi t đư c
Cho h th ng thông tin A = (U, A). V i m i t p con các thu c tính B ⊆ A,
t n t i m t quan h hai ngôi trên U , ký hi u IND(B ), xác đ nh b i:
IND(B ) = {(u, v ) ∈ U × U | u(B ) = v (B )}.
IND(B ) đư c g i là quan h B −không phân bi t đư c. D ki m ch ng đư c r ng
đây là m t quan h tương đương trên U . V i V ⊆ U , ta ký hi u IND(B |V ) là quan
h tương đương trên V , c m sinh b i IND(B ), t c là:
IND(B |V ) = {(u, v ) ∈ V × V | u(B ) = v (B )}.
N u (u, v ) ∈ IND(B ) thì hai đ i tư ng u và v không phân bi t đư c b i các
thu c tính trong B . L p tương đương ch a ph n t u đư c ký hi u [u]B . Khi đó
quan h IND(B ) đư c xác đ nh hoàn toàn b i các l p tương đương [u]B , u ∈ U . T p
h p thương c a quan h IND(B ) đư c ký hi u [IND(B )] hay đơn gi n là U/B , t c
là [IND(B )] = U/B = {[u]B | u ∈ U } và t p h p thương c a quan h IND(B |V ) là
[IND(B |V )] hay V /B .
Ví d 1.1. Xét t p 10 đ chơi v i các thu c tính: Màu s c, Kích thư c, Hình dáng
đư c cho trong B ng 1.1. Lúc đó
U /{Màu s c} = {{u1 , u2 , u6 , u10 }, {u3 , u5 , u9 }, {u4 , u7 , u8 }}
U /{Kích thư c} = {{u1 , u5 , u8 , u9 }, {u3 , u4 , u10 }, {u2 , u6 , u7 }}
U /{Hình dáng} = {{u1 , u2 , u6 , u10 }, {u3 , u4 , u9 }, {u5 , u7 , u8 }}
U /{Màu s c, Hình dáng} = {{u1 , u2 , u6 , u10 }, {u3 , u9 }, {u4 }, {u5 }, {u7 , u8 }}
Như v y các đ chơi u1 , u2 không phân bi t đư c v màu s c và hình dáng,
nhưng phân bi t đư c v kích thư c. Tương t , các đ chơi u3 , u4 không phân bi t
nhau v kích thư c và hình dáng, nhưng phân bi t đư c v màu s c, v.v...
- 16
U Màu s c Kích thư c Hình dáng
u1 Xanh To Tròn
u2 Xanh Nh Tròn
u3 Vàng Va Vuông
u4 Đ Va Vuông
u5 Vàng To Tam giác
u6 Xanh Nh Tròn
u7 Đ Nh Tam giác
u8 Đ To Tam giác
u9 Vàng To Vuông
u10 Xanh Va Tròn
B ng 1.1: B ng d li u các đ chơi.
1.2.3. Các t p x p x
Cho h th ng thông tin A = (U, A), B ⊆ A và V ⊆ U . V i các tri th c đư c
cho b i t p thu c tính B , li u chúng ta có th bi u di n t p đ i tư ng V b ng các
tri th c có s n này hay không? Hay nói cách khác, v i m t t p thu c tính B cho
trư c, chúng ta có các l p tương đương c a quan h IND(B ), th thì m t t p đ i
tư ng V có th di n đ t thông qua các l p tương đương này như th nào? Trong lý
thuy t t p thô, đ bi u di n V b ng tri th c có s n B ngư i ta x p x chúng b i
h p c a m t s h u h n các l p tương đương c a IND(B ). Có hai cách x p x : Cách
th nh t là cho tương ng b i "mi n trong" và cách th hai có th x p x b i "bao
đóng" c a V . Hai giá tr x p x này đư c g i tương ng là B −x p x dư i và B −x p
x trên c a V , ký hi u l n lư t là B V và BV , c th các t p x p x này đư c xác
đ nh như sau
B V = {u ∈ U | [u]B ⊆ V },
BV = {u ∈ U | [u]B ∩ V = ∅}.
- 17
V i các x p x trên, ta g i B −mi n biên c a V là t p BNB (V ) = BV \ B V
và B −mi n ngòai c a V là t p U \ BV . D th y B −mi n biên c a V là t p ch a
các đ i tư ng không ch c ch n thu c hay không thu c V , còn B −mi n ngòai c a V
ch a các đ i tư ng ch c ch n không thu c V . V i ký hi u t p thương c a quan h
tương đương IND(B ) trên U là U/B , các x p x trên và dư i c a V có th vi t l i:
B V = ∪{W ∈ U/B | W ⊆ V },
BV = ∪{W ∈ U/B | W ∩ V = ∅}.
Bây gi n u B, D ⊆ A, ta s g i B −mi n kh ng đ nh c a D là t p đư c xác
đ nh như sau
POSB (D) = (B V ).
V ∈U/D
Rõ ràng POSB (D) là t p t t c đ i tư ng u sao cho v i m i v ∈ U mà u(B ) =
v (B ) ta đ u có u(D) = v (D). Nói cách khác, POSB (D) = {u ∈ U | [u]B ⊆ [u]D }.
Ví d 1.2. Xét h th ng thông tin bi u di n các tri u ch ng cúm c a các b nh
nhân cho B ng 1.2.
U Đau đ u Thân nhi t C m cúm
u1 Có Bình thư ng Không
u2 Có Cao Có
u3 Có R t cao Có
u4 Không Bình thư ng Không
u5 Không Cao Không
u6 Không R t cao Có
u7 Không Cao Có
u8 Không R t cao Không
B ng 1.2: Các tri u ch ng c a b nh nhân.
- 18
Các l p không phân bi t đư c b i B = {Đau đ u, Thân nhi t } là: {u1 }, {u2 }, {u3 },
{u4 }, {u5 , u7 }, {u6 , u8 }. Đ t V = {u | u(C m cúm) = Có} = {u2 , u3 , u6 , u7 }. Lúc
đó,
B V = {u2 , u3 } và BV = {u2 , u3 , u6 , u7 , u5 , u8 }. Như v y, B −mi n biên c a V
là t p h p BNB (V ) = {u5 , u6 , u7 , u8 }. N u đ t D = {C m cúm} thì
U/D = {V1 = {u1 , u4 , u5 , u8 } ; V2 = {u2 , u3 , u6 , u7 }},
B V1 = {u1 , u4 } ; B V2 = {u2 , u3 },
(B V ) = {u1 , u2 , u3 , u4 }.
POSB (D) =
V ∈U/D
1.2.4. Các tính ch t c a x p x
Đ nh lý 1.1. [24] Cho V ⊆ U và B ⊆ A. Khi đó:
a) B V ⊆ V ⊆ BV.
b) B ∅ = B ∅ = ∅, B U = BU = U.
c) B (V ∪ W ) = BV ∪ BW.
d) B (V ∪ W ) ⊇ B V ∪ B W.
e) V ⊆ W ⇒ B V ⊆ B W và BV ⊆ BW.
f) B (V ∩ W ) = B V ∩ B W.
g) B (V ∩ W ) ⊆ BV ∩ BW.
h) B (U \ V ) = U \ BV.
i) B (U \ V ) = U \ B V.
j) B (B V ) = B (B V ) = B V.
k) B (BV ) = B (B (V ) = BV.
- 19
V i các khái ni m c a t p x p x đ i v i phân ho ch IND(B ), các t p thô đư c
chia thành b n l p cơ b n:
1) T p V là B −xác đ nh thô n u B V = ∅ và BV = U.
2) T p V là B −không xác đ nh trong n u B V = ∅ và BV = U.
3) T p V là B −không xác đ nh ngòai n u B V = ∅ và BV = U.
4) T p V là B − không xác đ nh hoàn tòan n u B V = ∅ và BV = U.
1.2.5. Đ chính xác c a x p x
V i m i B ⊆ A và V ⊆ U , đ i lư ng đo lư ng s chính xác c a x p x t p V
đ i v i phân ho ch trên B là giá tr
Card(B V )
αB (V ) =
Card(BV )
Rõ ràng 0 ≤ αB (V ) ≤ 1. N u αB (V ) = 1, ta nói V là chính xác đ i v i B , còn
n u αB (V ) < 1, V đư c g i là thô đ i v i B .
1.3. B ng quy t đ nh
M t l p đ c bi t c a các h th ng thông tin có vai trò quan tr ng trong nhi u
ng d ng là b ng quy t đ nh. B ng quy t đ nh là m t h th ng thông tin T v i t p
thu c tính A đư c chia thành hai t p khác r ng r i nhau C và D, l n lư t đư c g i
là t p thu c tính đi u ki n và t p thu c tính quy t đ nh. T c là T = (U, C ∪ D) v i
C ∩ D = ∅. Trong trư ng h p không s b nh m l n, ngư i ta ký hi u T = (C, D).
B ng quy t đ nh là mô hình thư ng g p trong th c t , khi mà giá tr d li u t i
các thu c tính đi u ki n có th cung c p cho ta thông tin v giá tr c a thu c tính
quy t đ nh. B ng quy t đ nh đư c g i là nh t quán n u D ph thu c hàm vào C ,
nguon tai.lieu . vn
