Tài liệu Một số phương pháp rút gọn thuộc tính trong bảng quyết định

ð I H C THÁI NGUYÊN TRƯ NG ð I H C CNTT VÀ TRUY N THÔNG HOÀNG TH NG C MAI M TS PHƯƠNG PHÁP RÚT G N THU C TÍNH TRONG B NG QUY T ð NH LU N VĂN TH C SĨ CÔNG NGH THÔNG TIN Thái Nguyên - Năm 2013 ð I H C THÁI NGUYÊN TRƯ NG ð I H C CNTT VÀ TRUY N THÔNG HOÀNG TH NG C MAI M TS PHƯƠNG PHÁP RÚT G N THU C TÍNH TRONG B NG QUY T ð NH LU N VĂN TH C SĨ CÔNG NGH THÔNG TIN Chuyên ngành: Khoa h c máy tính Mã s : 60.48.01 NGƯ I HƯ NG D N KHOA H C: GS.TS Vũ ð c Thi Thái Nguyên - Năm 2013 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn M CL C L I C M ƠN ......................................................................................................... I L I CAM ðOAN ................................................................................................... II DANH M C CÁC THU T NG ........................................................................ III B NG CÁC KÝ HI U .........................................................................................IV DANH SÁCH B NG............................................................................................VI L I M ð U ......................................................................................................... 1 Chương 1. KHÁI QUÁT V T P THÔ VÀ RÚT G N THU C TÍNH ................. 5 1.1. H thông tin .................................................................................................... 5 1.2. T p thô ........................................................................................................... 7 1.3. B ng quy t ñ nh.............................................................................................. 9 1.4. T p rút g n và lõi ........................................................................................... 9 1.5. Ma tr n phân bi t và hàm phân bi t .............................................................. 10 1.6. M i liên h gi a các t p rút g n c a các phương pháp rút g n thu c tính. .... 11 1.6.1. Entropy trong h thông tin và các tính ch t. ............................................... 12 1.6.2. T p rút g n d a trên entropy thông tin ....................................................... 14 1.6.3. M i liên h c a t p rút g n d a trên Shannon entropy ............................... 15 1.6.4. M i liên h c a t p rút g n d a trên ñ khác bi t gi a các tri th c............. 19 1.7. S thay ñ i các ñ ño ñánh giá hi u năng b ng quy t ñ nh khi rút g n thu c tính. ..................................................................................................................... 22 1.7.1. Lu t quy t ñ nh và các ñ ño c ñi n ......................................................... 23 1.7.2. ð ño hi u năng c i ti n c a b ng quy t ñ nh ............................................ 24 1.7.3. ð! xu t ñ ño hi u năng m"i c a b ng quy t ñ nh ..................................... 25 1.7.4. S thay ñ i các ñ ño khi th c hi n các phương pháp rút g n thu c tính ... 29 1.8. K t lu n Chương 1 ....................................................................................... 31 Chương 2. M T S# PHƯƠNG PHÁP RÚT G N THU C TÍNH TRONG B NG QUY%T ð&NH. ..................................................................................................... 32 2.1. M' ñ(u ......................................................................................................... 32 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 2.2. Thu t toán tìm t p rút g n s) d*ng Liang entropy......................................... 39 2.2.1. T p rút g n d a trên Liang entropy v"i phân ho+ch c i ti n..................... 40 2.2.2. Thu t toán tìm t p rút g n s) d*ng Liang entropy.................................... 43 2.3. Thu t toán tìm t p rút g n s) d*ng metric .................................................. 48 2.3.1. Kho ng cách Jaccard gi a hai t p h,p h u h+n ........................................ 49 2.3.2. Metric trên h thông tin ........................................................................... 50 2.3.3. T p rút g n d a trên metric ..................................................................... 51 2.3.4. Thu t toán tìm t p rút g n s) d*ng metric ............................................... 54 2.3.5. Thu t toán tìm t p rút g n theo ngư-ng ch.c ch.n c a b ng quy t ñ nh ........ 59 2.4. K t lu n Chương 2 ..................................................................................... 61 Chương 3: CHƯƠNG TRÌNH TH/ NGHI M ..................................................... 62 3.1. Bài toán ..................................................................................................... 62 3.2. Phương pháp .............................................................................................. 62 3.3. Xây d ng chương trình th) nghi m ............................................................ 63 3.4. K t qu th) nghi m ................................................................................... 64 3.5. K t lu n chương 3 ..................................................................................... 65 K%T LU N ........................................................................................................... 66 TÀI LI U THAM KH O ..................................................................................... 67 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn I L I C M ƠN Tôi xin chân thành c m ơn ñ n: - Trư0ng ð+i h c Công ngh thông tin và Truy!n thông, ð+i h c Thái Nguyên - Vi n Công ngh Thông tin và các th(y cô giáo ñã tr c ti p gi ng d+y, hư"ng d1n tôi trong quá trình h c t p và ñ nh hư"ng quan tr ng trong vi c hình thành ý tư'ng nghiên c u. Tôi xin chân thành c m ơn Chi b , BGH, BCH Công ñoàn, T Khoa h c t nhiên và cán b giáo viên, nhân viên Trư0ng THPT Bình ð ñã ñ ng viên, giúp ñ-, t+o ñi!u ki n thu n l,i cho tôi trong quá trình h c t p và nghiên c u. ð2c bi t, tôi xin bày t3 lòng bi t ơn sâu s.c ñ n GS.TS Vũ ð c Thi, ngư0i th(y ñã tr c ti p hư"ng d1n và giúp ñ- tôi hoàn thành lu n văn t t nghi p. Cu i cùng xin chân thành c m ơn nh ng ngư0i thân và gia ñình ñã luôn chia s5 m i khó khăn và là ch6 d a v ng ch.c v! v t ch t, tinh th(n ñ tôi hoàn thành chương trình khóa h c cũng như trong su t th0i gian hoàn thành lu n văn. M2c dù ñã có nhi!u c g.ng, nhưng do th0i gian có h+n và b n thân còn nh ng h+n ch nh t ñ nh nên lu n văn không tránh kh3i thi u sót. Mong nh n ñư,c các ý ki n phê bình, góp ý c a H i ñ7ng ch m lu n văn, các th(y cô giáo và ñ7ng nghi p ñ công trình nghiên c u ñư,c hoàn ch8nh hơn. Thái Nguyên, tháng 01 năm 2013 Tác gi Hoàng Th Ng c Mai Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn II L I CAM ðOAN Tôi xin cam ñoan lu n văn này là công trình do tôi t ng h,p và nghiên c u. Trong lu n văn có s) d*ng m t s tài li u tham kh o như ñã nêu trong ph(n tài li u tham kh o. Tác gi Lu n văn Hoàng Th Ng c Mai Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn III DANH M C CÁC THU T NG T p thô Rough Set H thông tin Information System H thông tin ñ(y ñ Complete Information System B ng quy t ñ nh Decision Table B ng quy t ñ nh ñ(y ñ Comple Decision Table B ng quy t ñ nh không nh t quán Inconsistent Decision Table Quan h không phân bi t ñư,c Indiscernibility Relation Rút g n thu c tính Attribute Reduction T p rút g n Reduct T p lõi Core Shannon entropy Entropy Liang entropy Entropy m"i c a Jiye Liang trong [28] Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn IV B NG CÁC KÝ HI U IS = (U , A,V , f ) DS = (U , C ∪ D, V , f ) H thông tin Cho b ng quy t ñ nh U S ñ i tư,ng C S thu c tính ñi!u ki n trong b ng quy t ñ nh u (a) Giá tr ñ i tư,ng c a u c a thu c tính a [ u ]B L"p tương ñương ch a u c a quan h IND ( B ) SB ( u ) L"p dung sai c a ñ i tư,ng u trên quan h SIM ( B ) U/B Phân ho+ch U sinh b'i t p thu c tính B BX B - x p x8 dư"i c a X BX B - x p x8 trên c a X BN B ( X ) B - mi!n biên c a X POS B ( D ) B - mi!n dương c a D PRED ( C ) T p t t c các rút g n d a trên mi!n dương HRED ( C ) T p t t c các rút g n d a trên Shannon entropy SRED ( C ) T p t t c các rút g n c a phương pháp ma tr n phân bi t ERED ( C ) T p t t c các rút g n d a trên Liang entropy NERED ( C ) T p t t c các rút g n d a trên Liang entropy v"i phân ho+ch c i ti n. MRED ( C ) T p t t c các rút g n d a trên metric KRED ( C ) T p t t c các rút g n d a trên ñ ño lư,ng tri th c khác nhau. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn V COREP ( C ) T p lõi d a trên mi!n dương COREH ( C ) T p lõi d a trên Shannon entropy CORES ( C ) T p lõi c a phương pháp ma tr n phân bi t. COREE ( C ) T p lõi d a trên Liang entropy. COREM ( C ) T p lõi d a trên metric COREK ( C ) T p lõi d a trên ñ ño lư,ng tri th c khác nhau. H ( P) Shannon entropy c a t p thu c tính P H (Q \ P ) Shannon entropy có ñi!u ki n c a Q khi ñã bi t P E ( P) Liang entropy c a t p thu c tính P E (Q \ P ) Liang entropy có ñi!u ki n c a Q khi ñã bi t P K ( P) Tri th c sinh b'i t p thu c tính P d ( K ( P ) , K (Q)) Metric gi a hai tri th c K ( P ) và K ( Q ) trên h thông tin ñ(y ñ s) d*ng kho ng cách Jaccard gi a hai t p h,p. DQP ( K ( P ) , K ( Q ) ) Lư,ng tri th c khác nhau gi a K ( P ) và K ( Q ) Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn VI DANH SÁCH B NG B ng 1.1. B ng thông tin v b nh cúm ........................................................... 6 B ng 1.3. B ng quy t ñ nh minh h a Ví d 1.3 ............................................ 18 B ng 1.4. B ng quy t ñ nh minh h a Ví d 1.4 ............................................ 46 B ng 2.1. B ng quy t ñ nh minh h a Ví d 2.1. ........................................... 46 B ng 2.2. B ng quy t ñ nh v b nh c m cúm ............................................... 53 B ng 2.3. B ng quy t ñ nh minh h a Ví d 2.5 ............................................ 57 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 1 L IM ð U 1. Tính c p thi t c!a ñ# tài Hi n nay, trên th gi"i có r t nhi!u thu t toán khai phá tri th c b9ng cách phân l"p và r0i r+c d li u như: S) d*ng cây quy t ñ nh, phương pháp th ng kê, các m+ng nơ ron, thu t toán di truy!n,...Trong m t vài năm g(n ñây, lý thuy t tâp thô ñư,c nhi!u nhóm nghiên c u ho+t ñ ng trong lĩnh v c tin h c nói chung và khai phá tri th c nói riêng nghiên c u và áp d*ng trong th c t . Lý thuy t t p thô ñư,c xây d ng trên n!n t ng toán h c v ng ch.c giúp cung c p nh ng công c* h u ích ñ gi i quy t nh ng bài toán phân l"p d li u và khai phá lu t,...Lý thuy t t p thô do Zdzisaw Pawlak ñ! xu t vào nh ng năm ñ(u th p niên tám mươi c a th k8 hai mươi - ñư,c xem là công c* h u hi u ñ gi i quy t các bài toán phân l"p, phát hi n lu t… ch a d li u mơ h7, không ch.c ch.n. T; khi xu t hi n, lý thuy t t p thô ñã ñư,c s) d*ng hi u qu trong các bư"c c a quá trình khai phá d li u và khám phá tri th c, bao g7m r0i r+c hóa d li u, rút g n thu c tính, trích l c các tri th c ti!m và sôi ñ ng c a các nghiên c u v! rút g n thu c tính. Ph(n l"n các nghiên c u này ñ!u t p trung vào ba phương pháp: phương pháp d a trên mi!n dương; phương pháp s) d*ng các ñ ño không ch.c ch.n và phương pháp s) d*ng ma tr n phân bi t. Lĩnh v c nghiên c u ñ ño không ch.c ch.n c a tri th c trong m y năm g(n ñây t p trung vào hai hư"ng ti p c n chính là entropy thông tin và h+t tri th c. M t l"p ñ2c bi t c a các h thông tin ñóng vai trò quan tr ng trong nhi!u ng d*ng là b ng quy t ñ nh. B ng quy t ñ nh DS là m t h th ng thông tin v"i t p thu c tính A ñư,c chia thành hai t p con khác r6ng r0i nhau C và D . Nói cách khác, DS = (U , C ∪ D ) v"i C ∩ D = ∅ . B ng quy t ñ nh là nh t quán khi ph* thu c hàm C → D là ñúng. ð i v"i b ng quy t ñ nh nh t quán, t p con các thu c tính ñi!u ki n R ⊆ C ñư,c g i là m t t p rút g n c a b ng quy t ñ nh n u R là t p t i thi u th3a mãn ph* thu c hàm R → D . N u xem b ng quy t ñ nh là quan h r trên t p thu c tính C ∪ D và D ch8 ch a m t thu c tính duy nh t {d } thì khái ni m t p rút g n trong b ng quy t ñ nh tương ñương v"i khái ni m t p t i thi u c a thu c tính {d } trên quan h . Khi ñó, các bài toán liên quan ñ n t p rút g n trong b ng quy t ñ nh có th gi i quy t b9ng các k t qu liên quan ñ n t p t i thi u c a m t thu c tính trên quan h trong lý thuy t cơ s' d li u quan h . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 3 Xu t phát t; nh ng lý do trên, tôi ch n và nghiên c u ñ! tài lu n văn: “M t s phương pháp rút g n thu c tính trong b ng quy t ñ nh”. 2. M$c tiêu c!a lu n văn M*c tiêu c a lu n văn là tìm hi u m t s v n ñ! liên quan ñ n phương pháp rút g n thu c tính trong h thông tin và xây d ng chương trình th) nghi m m t s thu t toán liên quan ñ n t p rút g n trong b ng quy t ñ nh. 3. Các ñóng góp c!a lu n văn Lu n văn ñã có hai ñóng góp chính sau: Th nh t là nghiên c u m i liên h gi a các t p rút g n c a các phương pháp rút g n thu c tính, tìm hi u các ñ ño c i ti n ñánh giá hi u năng b ng quy t ñ nh và nghiên c u s thay ñ i c a các ñ ño này khi th c hi n các phương pháp rút g n thu c tính. Th hai là xây d ng toán heuristic tìm t p rút g n c a b ng quy t ñ nh ñ(y ñ s) d*ng Liang entropy và metric. 4. B c$c lu n văn Lu n văn ñư,c vi t trong ba chương, g7m 66 trang Chương m t khái quát v! t p thô và rút g n thu c tính. Chương hai trình bày k t qu nghiên c u v! ba v n ñ!. Th nh t nghiên c u m i liên h gi a các t p rút g n c a các phương pháp rút g n thu c tính, bao g7m phương pháp d a trên mi!n dương, phương pháp s) d*ng các ñ ño không ch.c ch.n (entropy thông tin, h+t tri th c) và phương pháp s) d*ng ma tr n phân bi t. Th hai là tìm hi u các ñ ño c i ti n ñánh gia hi u năng c a b ng quy t ñ nh và nghiên c u s thay ñ i c a các ñ ño này khi th c hi n các phương pháp rút g n thu c tính. Th ba là ñ! xây d ng chương trình th) nghi m thu t toán heuristic (Thu t toán 2.2, Thu t toán 2.4 và Thu t toán 2.5). Thu t toán 2.5 tìm t p rút g n Pawlak s) d*ng Liang entropy, Thu t toán 2.4 tìm t p rút g n trong b ng quy t ñ nh s) d*ng metric, Thu t toán 2.5 là Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 4 c i ti n c a Thu t toán 2.4 tìm t p rút g n theo tham s là ngư-ng ch.c ch.n c a b ng quy t ñ nh. Các thu t toán trên ñ!u có ñ ph c t+p tính toán trong th0i gian ña th c và hi u qu hơn các thu t toán khác ñã công b . Chương 3 Chương trình th) nghi m xây d ng b ng quy t ñ nh d a trên Thu t toán 2.4 tìm t p rút g n s) d*ng metric ñã trình bày trong Chương 2. K t qu th) nghi m c a chương trình th c hi n trên công c* mã ngu7n m' NetBeans IDE 7.1.2 Cu i cùng, ph(n k t lu n nêu nh ng ñóng góp c a lu n văn, hư"ng phát tri n và nh ng v n ñ! quan tâm c a tác gi . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 5 Chương 1. KHÁI QUÁT V T P THÔ VÀ RÚT G N THU C TÍNH 1.1. H' thông tin H thông tin là công c* bi u di=n tri th c dư"i d+ng m t b ng d li u g7m P c t ng v"i P thu c tính và n hàng ng v"i n ñ i tư,ng. M t cách hình th c, nó ñư,c ñ nh nghĩa như sau: ð nh nghĩa 1.1. H th ng thông tin là m t b t IS = (U , A,V , f ) trong ñó U là t p h u h+n, khác r6ng các ñ i tư,ng; A là t p h u h+n, khác r6ng các thu c tính; V = ∏ Va v"i Va là t p giá tr c a thu c tính a ∈ A ; f là hàm thông tin, a∈ A v"i m i a ∈ A và u ∈ U hàm f cho giá tr f ( u , a ) ∈ Va . V"i m6i u ∈U , a ∈ A , ta kí hi u giá tr c a ñ i tư,ng u t+i thu c tính a là u ( a ) thay vì f ( u , a ) . 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> vi t u ( B ) = v ( B ) n u u ( bi ) = v ( bi ) v"i m i i = 1,..., k . Cho h thông tin IS = (U , A,V , f ) . V"i m6i t p con các thu c tính p ⊆ A , t7n t+i m t quan h hai ngôi trên U , ký hi u là IND ( P ) , xác ñ nh b'i IND ( P ) = {( u, v ) ∈U × U | ∀a ∈ P, f ( u, a ) = f ( v, a )} . IND ( P ) ñư,c g i là quan h B - không phân bi t ñư,c. D= th y r9ng ñây là m t quan h tương ñương trên U . N u ( v, u ) ∈ IND ( B ) thì hai ñ i tư,ng u và v không phân bi t b'i các thu c tính trong B . Ký hi u phân ho+ch c a U sinh b'i quan h tương ñương IND ( P ) là U / IND ( P ) , vi t t.t là U / P . M6i ph(n t) trong U / P là m t l"p tương ñương hay m t kh i. Ký hi u l"p tương ñương U / P ch a ñ i tư,ng u là [u ]P , khi ñó, [u ]P = {v ∈U | ( u, v ) ∈ IND ( P )} . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 6 ð nh nghĩa 1.2. [11, 12] Cho h th ng thông tin IS = (U , A,V , f ) v"i P, Q ⊆ A . Ta nói: 1) U / P = U / Q khi và ch8 khi ∀u ∈ U , [u ]P = [u ]Q 2) U / P ≤ U / Q khi và ch8 khi ∀u ∈ U , [u ]P ⊆ [u ]Q ; 3) U / P < U / Q khi và ch8 khi ∀u ∈ U , [u ]P ⊆ [u ]Q và t7n t+i v sao cho [ v ]P ⊆ [ v ]Q Tính ch t 1.1. [11, 12] Xét h th ng thông tin S = (U , A,V , f ) và P, Q ⊆ A . N u P ⊆ Q thì U / Q ≤ U / P . Tính ch t 1.2. [11, 12] Xét h thông tin IS = (U, A, V, ƒ) và P, Q ⊆ A . V i m i u ∈ U ta có [u ]P ∪Q = [u ]P ∩ [u ]Q . Ví d$ 1.1. Xét h thông tin IS = (U , A,V , f ) bi u di=n các tri u ch ng cúm c a b nh nhân cho ' B ng 1.1 v"i U = ( u1 , u2 , u3 , u4 , u5 , u6 , u7 , u8 ) , C = ( a1 , a2 , a3 ) v"i a1 (ðau ñ(u), a2 (Thân nhi t), a3 (C m cúm). ðau ñ)u U Thân nhi't C m cúm u1 Có Bình thư0ng Không u2 Có Cao Có u3 Có R t cao Có u4 Không Bình thư0ng 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.1. B ng thông tin v b nh cúm Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 7 Ta có U / {a1} = {{u1 , u2 , u3} , {u4 , u5 , u6 , u7 , u8 }} , U / {a2 } = {{u1 , u4 } , {u2 , u5 , u7 } , {u3 , u6 , u8 }} , U / {a3 } = {{u1 , u4 , u5 , u8 } , {u2 , u3 , u6u7 }} , U / {a1 , a2 } = {{u1} , {u2 } , {u3 } , {u4 }{u5 , u7 } , {u6 , u8 }} Như v y, các b nh nhân u2 , u3 không phân bi t nhau v! ñau ñ(u ( a1 ) và c m cúm ( a3 ) , nhưng phân bi t ñư,c v! thân nhi t ( a2 ) . 1.2. T p thô Cho h thông tin IS = (U , A,V , f ) và t p ñ i tư,ng X ⊆ U . V"i m t t p thu c tính B ⊆ A cho trư"c, chúng ta có các l"p tương ñương c a phân ho+ch U / B , th thì m t t p ñ i tư,ng X có th bi u di=n 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 X thông qua các l"p tương ñương c a U / B (còn g i là bi u di=n X b9ng tri th c s?n có B ), ngư0i ta x p x8 X b'i h,p c a m t s h u h+n các l"p tương ñương c a U / B . Có hai cách x p x8 t p ñ i tư,ng X thông qua thu c tính B , ñư,c g i là B -x p x dư i và B x p x trên c a X , ký hi u l(n lư,t là BX và BX ñư,c xác ñ nh như sau: BX = {u ∈ U | [u ]B ⊆ X } , BX = {u ∈ U | [u ]B ∩ X ≠ ∅} . T p BX bao g7m t t c các ph(n t) c a U ch.c ch.n thu c vào X , còn t p BX bao g7m các ph(n t) c a U có kh năng ñư,c phân lo+i vào X d a vào t p thu c tính B . T; hai t p x p x8 nêu trên, ta ñ nh nghĩa các t p BN B ( X ) = BX − BX : B - mi n biên c a X . U − BX : B -mi n ngoài c a X D= th y B - mi n biên c a X là t p ch a các ñ i tư,ng có th thu c X , còn mi!n B - mi n ngoài c a X ch a các ñ i tư,ng ch.c ch.n không thu c Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 8 X . S) d*ng các l"p c a phân ho+ch U / B , các x p x8 dư"i và trên c a X có th vi t l+i. BX = {Y ∈U / B | Y ⊆ X } . BX = {Y ∈U / B | Y ∩ X = ∅} . Trong trư0ng h,p BN B ( X ) = ∅ , X ñư,c g i là t p rõ, ngư,c l+i X ñư,c g i là t p thô. V"i B, D ⊆ A , ta g i B - mi n dương c a D là t p ñư,c xác ñ nh như sau POS B ( D ) = BX X ∈U / D Rõ ràng POS B ( D ) là t p t t c ñ i tư,ng u sao cho v"i m i v ∈U mà ta u ( B) = v ( B) ñ!u có u ( D) = v ( D) . Nói cách khác, POS B ( D ) = {u ∈ U | [u ]B ⊆ [u ]D } . Ví d$ 1.2. Xét h thông tin IS = (U , A,V , f ) ' Ví d* 1.1. V"i B = {a1 , a2 } và X = {u2 , u3 , u6 , u7 } ta có U / B = {{u1} , {u2 } , {u3 } , {u4 } , {u5 , u7 } , {u6 , u8 }} . Do ñó, BX = {u2 , u3 } và BX = {u2 , u3 , u5 , u6 , u7 , u8 } . Như v y, B -mi n biên c a X là t p h,p BN B ( X ) = {u5 , u6 , u7 , u8 } . N u ñ2t D = {a3 } thì U / D = { X 1 = {u1 , u4 , u5 , u8 } , X 2 = {u2 , u3 , u6 , u7 }} . BX 1 = {u1 , u4 } , BX 2 = {u2 , u3 } . Do ñó, POSB ( D ) = ( BX ) = {u1 , u2 , u3 , u4 } . X ∈U / D V"i các khái ni m c a t p x p x8 ñ i v"i phân ho+ch U / B , các t p thô ñư,c chia thành b n lo+i như sau: 1) T p X là B - xác ñ nh thô n u BX ≠ ∅ và BX ≠ U 2) T p X là B - không xác ñ nh trong n u BX = ∅ và BX ≠ U 3) T p X là B - không xác ñ nh ngoài n u BX ≠ ∅ và BX = U 4) T p X là B - không xác ñ nh hoàn toàn n u BX ≠ ∅ và BX = U . Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 9 1.3. B ng quy t ñ nh M t l"p ñ2c 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 d+ng ñ2c bi t c a h thông tin, trong ñó t p các thu c tính A bao g7m hai t p con r0i nhau: t p các thu c tính ñi!u ki n C và t p các thu c tính quy t ñ nh D . Như v y, b ng quy t ñ nh là m t h th ng thông tin DS = (U , C ∪ D,V , f ) trong ñó C ∩ D = ∅ . B ng quy t ñ nh DS ñư,c g i là nh t quán khi và ch8 khi ph* thu c hàm C → D nghi m ñúng, nghĩa là v"i m i u , v ∈ U , u (C ) = v(C ) kéo theo u ( D) = v( D) . Ngư,c l+i, DS là không nh t quán. D= th y b ng quy t ñ nh DS là nh t quán khi và ch8 khi POSC ( D) = U . Trong trư0ng h,p b ng không nh t quán thì POSC ( D ) chính là t p con c c ñ+i c a U sao cho ph* thu c hàm C → D ñúng. 1.4. T p rút g n và lõi Trong b ng quy t ñ nh, các thu c tính ñi!u ki n ñư,c chia thành ba nhóm: thu c tính lõi, thu c tính cơ b n (hay thu c tính rút g n) và thu c tính dư th;a (hay thu c tính không c(n thi t). - Thu c tính lõi là thu c tính c(n thi t và c t y u, không th thi u trong vi c phân l"p chính xác t p d li u. - Thu c tính dư th;a là nh ng thu c tính không c(n thi t, nghĩa là có th lo+i b3 các thu c tính như v y mà không nh hư'ng ñ n vi c phân l"p d li u. - Thu c tính cơ b n là thu c tính n9m trong m t t p rút g n nào ñó. Ta s> ñưa ra các ñ nh nghĩa chính xác như sau: Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn 10 ð nh nghĩa 1.3. Cho b ng quy t ñ nh DS = (U , C ∪ D,V , f ) , thu c tính a ∈ C ñư,c g i là c(n thi t n u POSC ( D ) ≠ POS(C −{a}) ( D) . T p t t c các thu c tính c(n thi t trong DS ñư,c g i là t p lõi và kí hi u là COREP (C ) . ð nh nghĩa 1.4. Cho b ng quy t ñ nh DS = (U , C ∪ D,V , f ) . N u R ⊆ C th3a mãn: 1) POS R ( D) = POSC ( D) 2) POS R ( D) ≠ POSC ( D ) v"i ∀R ' ⊂ R thì R là m t rút g n c a C ' T p rút g n ñ nh nghĩa như trên g i là m t t p rút g n d a trên mi!n dương theo Pawlak. ð nh nghĩa 1.4 cho th y, R là t p rút g n n u nó là t p t i thi u th3a mãn POSR ( D) = POSC ( D) . Có th t7n t+i nhi!u t p rút g n c a C . Ta kí hi u PREDP ( C ) là t p t t c các rút g n theo Pawlak c a C . Khi ñó, R. COREP (C ) = R∈PRED ( C ) T; ñ nh nghĩa v! t p lõi và t p rút g n, ta ñ nh nghĩa thu c tính dư th;a và thu c tính cơ b n trong b ng quy t ñ nh như sau: ð nh nghĩa 1.5. Cho b ng quy t ñ nh DS = (U , C ∪ D, V , f ) và a ∈ C . Ta nói r9ng a là thu c tính cơ b n c a C n u t7n t+i m t rút g n R ∈ PRED(C ) sao cho a∈R . ð nh nghĩa 1.6. Cho b ng quy t ñ nh DS = (U , C ∪ D, V , f ) và a ∈ C . Ta nói r9ng a là thu c tính dư th;a c a C n u a ∈ C − R. R∈PRED ( C ) 1.5. Ma tr n phân bi't và hàm phân bi't Ngư0i ñ(u tiên xây d ng phương pháp rút g n thu c tính trong b ng quy t ñ nh là Skowron. Ông ñã ñưa ra khái ni m ma tr n phân bi t và hàm phân bi t, t; ñó ñưa ra phương pháp tìm t p rút g n s) d*ng hàm phân bi t. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn