Luận văn tốt nghiệp: Tiếp cận lý thuyết tập thô do Z.Pawlak

Chia sẻ: Bluesky_12 Bluesky_12 | Ngày: | Loại File: PDF | Số trang:102

Thêm vào BST

Báo xấu

317
lượt xem 126
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Lý thuyết tập thô được nhà logoc học Balan Zdzilaw Pawlak đề xuất ra vào đầu những năm 80 của thế kỷ 19 - Nó cung cấp một công cụ để phân tích, suy diễn 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. - Một hướng tiếp cận mới về tính không chắc chắn và không chính xác của dữ liệu

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn tốt nghiệp: Tiếp cận lý thuyết tập thô do Z.Pawlak

  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 ,