Luận văn 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 1Mục lụ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 21.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 33.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 4Chươ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ỉ 5Chươ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 ). BV : 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 6tí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. ωVB(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. ωVB(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 6→ Y : Y không phụ thuộc hàm vào X trên U . 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 . 7Danh 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 1.4 Bảng rút gọn thứ nhất của hệ thống bệnh cúm (R1). . . . . . . . . . 19 1.5 Bảng rút gọn thứ hai của hệ thống bệnh cúm (R2). . . . . . . . . . . 19 1.6 Dữ liệu bảng quyết định. . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.7 Ma trận phân biệt được M. . . . . . . . . . . . . . . . . . . . . . . . 21 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 83.4 Quan hệ tương tự trên Ib . . . . . . . . . . . . . . . . . . . . . . . . . 80 3.5 Quan hệ tương tự trên Ic . . . . . . . . . . . . . . . . . . . . . . . . . 80 3.6 Dữ liệu của hệ thống. . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 3.7 Các quan hệ tương tự trên IX , IY và IZ . . . . . . . . . . . . . . . . . 83 3.8 Bảng dữ liệu. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 3.9 Các quan hệ tương tự trên IY và IZ . . . . . . . . . . . . . . . . . . . 86 9Chươ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 Vừa Vuông u4 Đỏ Vừa 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 Vừa 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à BV và BV , cụ thể các tập xấp xỉ này được xác định như sau BV = {u ∈ U | [u]B ⊆ V }, BV = {u ∈ U | [u]B ∩ V 6= ∅}. 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 \ BV 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: BV = ∪{W ∈ U/B | W ⊆ V }, BV = ∪{W ∈ U/B | W ∩ V 6= ∅}. 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) = ⋃ V ∈U/D (BV ). 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