Tài liệu Nghiên cứu một số phương pháp rút gọn thuộc tính trong bảng quyết định không đầy đủ

LỜI CẢM ƠN Em xin chân thành cảm ơn và biết ơn sâu sắc đến GS.TS Vũ Đức Thi, Viện Công nghệ Thông tin, Viện Khoa học và Công nghệ Việt Nam. Người đã tận tình dày công hướng dẫn và giúp đỡ em hoàn thành luận văn này. Em xin chân thành cảm ơn các Thầy ở Viện Công nghệ Thông tin đã dạy bảo, giúp đỡ và truyền đạt kiến thức cho em trong suốt khóa học, trong suốt cả quá trình em làm luận văn. Em xin chân thành cảm ơn các Thầy, các Cô ở trường Đại học Công nghệ Thông tin và Truyền thông Thái Nguyên đã động viên, giúp đỡ và tạo điều kiện cho em trong suốt thời gian học tập và nghiên cứu. Cuối cùng xin chân thành cảm ơn bàn bè, người thân và gia đình luôn là người đồng hành, động viên, chia sẻ những khó khăn trong suốt thời gian hoàn thành luận văn. Thái Nguyên, tháng 08 năm 2013 Nguyễn Quỳnh Lan LỜI CAM ĐOAN Tôi xin cam đoan luận văn này là sản phẩm tìm hiểu, nghiên cứu của mình. Một số Định nghĩa, Định lý, Tính chất, Mệnh đề và Thuật toán tôi lấy từ nguồn tài liệu chính xác có trích dẫn tên tài liệu và tên tác giả rõ ràng. Tôi xin chịu trách nhiệm về luận văn của mình. Tác Giả Nguyễn Quỳnh Lan i MỤC LỤC MỤC LỤC...............................................................................................................................i Danh mục các thuật ngữ........................................................................................................iii Bảng các ký hiệu, từ viết tắt..................................................................................................iv Danh sách bảng......................................................................................................................v MỞ ĐẦU................................................................................................................................1 Chương 1. TỔNG QUAN VỀ BẢNG QUYẾT ĐỊNH ĐẦY ĐỦ VÀ BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ......................................................................................................3 1.1. Bảng quyết định đầy đủ...................................................................................................3 1.2. Hệ thông tin .......... .........................................................................................................3 1.3. Hệ thông tin đầy đủ và mô hình tập thô truyền thống.....................................................3 1.3.1. Hệ thông tin đầy đủ ............................................................................................3 1.3.2. Mô hình tập thô truyền thống..............................................................................5 1.3.3. Tập rút gọn và tập lõi..........................................................................................7 1.4. Hệ thông tin không đầy đủ và mô hình tập thô dung sai.................................................9 1.4.1. Hệ thông tin không đầy đủ..................................................................................9 1.4.2. Bảng quyết định không đầy đủ.........................................................................11 1.4.3. Tập rút gọn của bảng quyết định không đầy đủ................................................11 1.5.Rút gọn thuộc tính trong bảng quyết định đầy đủ sử dụng metric.................................12 1.5.1. Metric trên họ các tri thức và tính chất.............................................................12 1.5.1.1. Khoảng cách Jaccard giữa hai tập hợp hữu hạn........................................12 1.5.1.2. Metric trên họ các tri thức........................................................................14 1.5.1.3. Một số tính chất của metric trên bảng quyết định....................................15 1.5.2. Rút gọn thuộc tính trong bảng quyết định sử dụng metric..............................18 1.5.2.1.Tập lõi và tập rút gọn của bảng quyết định dựa trên metric……….……..18 1.5.2.2.Thuật toán tìm tập rút gọn của bảng quyết định sử dụng metric................19 ii 1.6 Kết luận chương 1……………………………………………………………...27 Chương 2.RÚT GỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ….28 2.1 Giới thiệu.......................................................................................................................28 2.2. Entropy Liang mở rộng trong hệ thông tin không đầy đủ và các tính chất…...…….. 29 2.2.1. Entropy Liang mở rộng của tập thuộc tính......................................................29 2.2.2. Entropy Liang mở rộng có điều kiện................................................................30 2.2.3. Một số tính chất của entropy Liang mở rộng....................................................32 2.3. Metric trên họ các phủ và các tính chất.........................................................................37 2.3.1. Metric trên họ các phủ......................................................................................37 2.3.2. Một số tính chất chất của metric.......................................................................40 2.4. Rút gọn thuộc tính trong bảng quyết định không đầy đủ sử dụng metric………...…..43 2.4.1 Tập rút gọn của bảng quyết định không đầy đủ dựa trên metric.......................43 2.4.2.Thuật toán tìm tập rút gọn của bảng quyết định không đầy đủ.........................44 2.5. Kết luận chương 2.........................................................................................................52 Chương 3. CHƯƠNG TRÌNH THỬ NGHIỆM...................................................................53 3.1 Mô tả dữ liệu..................................................................................................................53 3.2 Xây dựng chương trình...................................................................................................57 3.3 Kết quả thực nghiệm......................................................................................................59 3.4 Nhận xét.........................................................................................................................60 KẾT LUẬN..........................................................................................................................61 TÀI LIỆU THAMKHẢO………………………………………………………………….62 PHỤ LỤC…………………………………………………………………………..64 iii Danh mục các thuật ngữ Thuật ngữ tiếng việt Thuật ngữ tiếng anh Tập thô Rough set Hệ thông tin Information system Hệ thông tin đầy đủ Complete Information system Hệ thông tin không đầy đủ Incomplete Information system Bảng quyết định Decision Table Bảng quyết định đầy đủ Complete Decision Table Bảng quyết định không đầy đủ Incomplete Decision Table Quan hệ không phân biệt được Indiscernibility Relation Xấp xỉ dưới Lower Approximation Xấp xỉ trên Upper Lower Approximation Rút gọn thuộc tính Attribute Reduction Tập rút gọn Reduct Tập lõi Core Ma trận phân biệt Indiscernibility Matrix Hàm phân biệt Indiscernibility Function iv Bảng các ký hiệu, từ viết tắt Ký hiệu, từ viết tắt Diễn giải IS = (U, A, V, f) Hệ thông tin, hệ thông tin đầy đủ IIS = (U, A, V, f) Hệ thông tin không đầy đủ DS = (U, C∪D, V, f) Bảng quyết định, bảng quyết định đầy đủ IDS = (U, C∪D, V, f) Bảng quyết định không đầy đủ |U| Số đối tượng |C| Số thuộc tính điều kiện trong bảng quyết định |A| Số thuộc tính trong hệ 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 SIM(B) Quan hệ dung sai trên tập thuộc tính B [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 của U sinh bởi tập thuộc tính B U/SIM(B) Phủ của U sinh bởi tập thuộc tính B COVER(U) Họ tất cả các phủ của U B(u) Hàm quyết định suy rộng của đối tượng u đối với B BX B- xấp xỉ dưới của X BX B- xấp xỉ trên của X BNB(X) B- miền biên của X POS B(D) B- miền dương của D PRED(C) Họ tất cả các tập rút gọn Pawlak v SRED(C) Họ tất cả các tập rút gọn sử dụng ma trận phân biệt MRED(C) Họ tất cả các tập rút gọn dựa trên metric PCORE (C) Tập lõi dựa trên miền dương SCORE(C) Tập lõi sử dụng ma trận phân biệt MCORE(C) Tập lõi dựa trên metric H(P) Entropy Shannon của tập thuộc tính P H(Q/P) Entropy Shannon có điều kiện của Q khi đã biết P IE(P) Entropy Liang mở rộng của tập thuộc tính P trong hệ thông tin không đầy đủ IE(Q/P) Entropy Liang mở rộng có điều kiện của Q khi đã biết P trong hệ thông tin không đầy đủ K(P) Trong hệ thông tin đầy đủ:là tri thức sinh bởi tập thuộc tính P. Trong hệ thông tin không đầy đủ là phủ sinh bởi tâp thuộc tính P dj(K(P), K(Q)) Khoảng cánh giữa K(P) và K(Q) trong hệ thông tin đầy đủ dựa trên khoảng cách Jaccard giữa hai tập hợp dE(K(P), K(Q)) Khoảng cánh giữa K(P) và K(Q) trong hệ thông tin không đầy đủ dựa trên entropy Liang mở rộng SIGB(b) Độ quan trọng của thuộc tính b đối với B vi DANH SÁCH BẢNG Bảng 1.1 Bảng thông tin về bệnh cúm...............................................................6 Bảng 1.2. Bảng quyết định về bệnh cúm...........................................................9 Bảng 1.3. Bảng thông tin về các xe hơi............................................................12 Bảng 1.4. Bảng quyết định về bệnh cảm cúm...................................................19 Bảng 1.5. Bảng quyết định minh họa ví dụ 1.5................................................22 Bảng 2.1 Bảng hệ thông tin không đầy đủ về các xe hơi.................................37 Bảng 2.3. Bảng quyết định không đầy đủ minh họa ví dụ 2.3..........................49 Bảng 2.4. Bảng quyết định không đầy đủ về các xe hơi...................................52 Bảng 3.1. Bảng quyết định không đầy đủ về các xe hơi...................................56 Bảng 3.2. Kết quả thực hiện thuật toán Thuật toán 2.2………………………… 65 Bảng 3.3. Tập rút gọn của Thuật toán 2.2……………………………………..65 1 MỞ ĐẦU Mười năm trở lại đây chúng ta đã chứng kiến sự phát triển mạnh mẽ và sôi động của lĩnh vực nghiên cứu về rút gọn thuộc tính sử dụng lý thuyết tập thô. Trong xu thế đó, nhiều nhóm nhà khoa học trên thế giới quan tâm nghiên cứu các phương pháp rút gọn thuộc tính trong bảng quyết định. Các phương pháp chính là: Phương pháp dựa trên miền dương, phương pháp sử dụng các phép toán trong đại số quan hệ, phương pháp sử dụng ma trận phân biệt, phương pháp sử dụng entropy thông tin, phương pháp sử dụng các độ đo trong tính toán hạt... Mục tiêu của rút gọn thuộc tính là loại bỏ các thuộc tính dư thừa để tìm ra các thuộc tính cốt yếu và cần thiết trong cơ sở dữ liệu. Với bảng quyết định không đầy đủ rút gọn thuộc tính là tìm tập con nhỏ nhất của tập thuộc tính điều kiện bảo đảm thông tin phân lớp của bảng quyết định đó. Đối với một bảng quyết định không đầy đủ có thể có nhiều tập rút gọn khác nhau. Tuy nhiên, trong thực hành thường không đòi hỏi tìm tất cả các tập rút gọn mà chỉ cần tìm được một tập rút gọn theo một tiêu chuẩn đánh giá nào đó là đủ. Các kết quả nghiên cứu cho thấy rút gọn thuộc tính làm giảm thiểu đáng kể khối lượng tính toán, nhờ đó có thể áp dụng đối với các bài toán có khối lượng dữ liệu lớn. Thuật toán khá đơn giản về mặt thực thi. Nên em quyết định lựa chọn đề tài luận văn: “Nghiên cứu một số phương pháp rút gọn thuộc tính trong bảng quyết định không đầy đủ”. Mục tiêu của luận văn: Tập trung nghiên cứu rút gọn thuộc tính trong bảng quyết định đầy đủ từ đó làm cơ sở nghiên cứu tiếp phương pháp rút gọn thuộc tính trong bảng quyết định không đầy đủ. Đối tượng và phạm vi nghiên cứu: Các bảng quyết định đầy đủ, các bảng quyết định không đầy đủ với kích thước trung bình và lớn. 2 Phương pháp nghiên cứu - Về nghiên cứu lý thuyết: Các Định lý, Mệnh đề…đã được chứng minh dựa vào các kiến thức cơ bản và các kết quả nghiên cứu đã công bố. - Về nghiên cứu thực nghiệm: Cài đặt thuật toán, chạy thử nghiệm thuật toán. Ý nghĩa khoa học của đề tài -Đây là phương pháp được nhiều nhà khoa học nghiên cứu và đã có đóng góp trong thực tiễn. -Có thể coi luận văn là một tài liệu tham khảo khá đầy đủ, rõ ràng về các kiến thức cơ bản trong bảng quyết định không đầy đủ. Bố cục của luận văn: Gồm phần mở đầu và 3 chương nội dung, phần kết luận, danh mục tài liệu tham khảo và phụ lục. Chương 1: Trình bày các khái niệm cơ bản về bảng quyết định đầy đủ, bảng quyết định không đầy đủ, mô hình tập thô truyền thống, mô hình tập thô dung sai, trình bày phương pháp xây dựng 1 metric trên họ các tri thức trong hệ thông tin đầy đủ dựa trên khoảng cách Jaccard giữa hai tập hợp hữu hạn, trình bày phương pháp rút gọn thuộc tính trong bảng quyết định đầy đủ. Chương 2: Trình bày phương pháp xây dựng một metric trên họ các phủ trong hệ thông tin không đầy đủ dựa trên entropy Liang mở rộng, trình bày phương pháp rút gọn thuộc tính trong bảng quyết định không đầy đủ. Chương 3: Chương trình thử nghiệm trình bày các nội dung: mô tả dữ liệu, xây dựng chương trình, và kết quả thực nghiệm của thuật toán. Cuối cùng, phần kết luận nêu những đóng góp của luận văn và hướng phát 3 triển của luận văn. 4 Chương 1. TỔNG QUAN VỀ BẢNG QUYẾT ĐỊNH ĐẦY ĐỦ VÀ BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ 1.1. Bảng quyết định đầy đủ Một lớp đặc biệt của hệ 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 tin DS 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à DS = (U, C∪D, V, f) với C∩D=  . Xét bảng quyết định DS = (U, C∪D, V, f) với giả thiết mọi u∈U, mọi d∈D, d(u) đầy đủ giá trị, nếu tồn tại u∈U và c∈C sao cho c(u) thiếu giá trị thì DS được gọi là bảng quyết định không đầy đủ, trái lại DS được gọi là bảng quyết định đầy đủ. Trong luận văn này, bảng quyết định đầy đủ được gọi tắt là bảng quyết định. 1.2. Hệ thông tin Hệ thông tin là công cụ biểu diễn tri thức dưới dạng 1 bảng dữ liệu gồm p cột tương ứng với p thuộc tính và n hàng ứng với n đối tượng. 1.3. Hệ thông tin đầy đủ và mô hình tập thô truyền thống. 1.3.1. Hệ thông tin đầy đủ Một cách hình thức, hệ thông tin được định nghĩa như sau: Định nghĩa 1.1. Hệ thông tin là một bộ tứ IS= (U, A, V, f) trong đó U là một tập hữu hạn, khác rỗng các đối tượng, A là một tập hữu hạn, khác rỗng các thuộc tính, V= UV a A a với Va là tập giá trị các thuộc tính a∈A; f: U x A  Va là hàm thông tin, mọi a∈A, u∈U f(u,a)∈Va. 5 Với mọi u∈U, a∈A ta ký hiệu giá trị thuộc tính a tại đối tượng u là a(u) 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 ký hiệu bộ các giá trị bi(u) bởi B(u). Như vậy, nếu u và v là hai đối tượng, thì ta viết B(u)=B(v), nếu bi(u)=bi(v) với mọi i= 1,...,k. Cho hệ thông tin IS = (U, A, V, f), nếu tồn tại u∈U và a∈A sao cho a(u) thiếu giá trị (missing value) thì IS được gọi là hệ thông tin không đầy đủ, trái lại IS được gọi là hệ thông tin đầy đủ. Chúng ta tự hiểu hệ thông tin đầy đủ được gọi tắt là hệ thông tin. Xét hệ thông tin IS = (U, A, V, f). Mỗi tập con các thuộc tính P∈A xác định một quan hệ hai ngôi trên U, ta ký hiệu IND(P), xác định bởi: IND(P)={(u,v) ∈U x U/  a ∈P, a(u)=a(v)}. IND(P) là quan hệ P – không phân biệt được. Dễ thấy rằng IND (P) là một quan hệ tương đương trên U. Nếu (u,v)∈IND(P) thì hai đối tượng u và v không phân biệt được bởi các thuộc tính trong P. Quan hệ tương đương IND(P) xác định một phân hoạch U/P chứa đối tượng u là [u]p khi đó [u]p= {v∈U/(u,v)∈IND(P)}. Định nghĩa 1.2.[12] Cho hệ thông tin IS=(U, A, V, f), và P, Q∈A. 1) Phân hoạch U/P và phân hoạch U/Q là như nhau (viết U/P=U/Q), khi và chỉ khi  u ∈U, [u]P=[u]Q. 2) Phân hoạch U/P mịn hơn phân hoạch U/Q (viết U/P ∈U/Q), khi và chỉ khi  u ∈U, [u]P ∈[u]Q. Tính chất 1.1 [12] Xét hệ thông tin IS= ( U,A,V, f ) và P, Q∈A. 1) Nếu P∈Q thì U/Q∈U/P, mỗi lớp của U/P là một lớp hoặc hợp của một số lớp thuộc U/Q. 2) Với mọi u ∈U ta có [u]P∪Q=[u]p ∩[u]Q. 1.3.2. Mô hình tập thô truyền thống 6 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? Để 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 bằng tri thức có sẵn trong B), người ta xấp xỉ 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 xỉ tập đối tượng X thông qua tập 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 gồm 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 gồm các phần tử của U có thể thuộc vào X dựa trên tập thuộc tính B. Từ hai tập xấp xỉ nêu trên, ta định nghĩa các tập BNB(X) = BX - BX : B miền biên của X, U- BX : B miền ngoài của X. B miền biên của X là tập chứa các đối tượng có thể thuộc hoặc không thuộc X, còn B miền ngoài của X chứa các đối tượng chắc chắn không thuộc X. Sử dụng các lớp của phân hoạch U/B, các xấp xỉ 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 ≠  }. BNB(X) =  thì X được gọi là tập chính xác (exact set ), ngược lại X được gọi là tập thô (rough set). 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: POSB(D)= U XU /D ( BX ) Rõ ràng POSB(D) là tập tất cả cá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.1. Xét hệ thông tin biểu diễn các triệu chứng cúm của bệnh nhân 7 Bảng 1.1. Bảng thông tin về bệnh cúm 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 Ta có: U/{Đau đầu}={ {u1, u2, u3}, {u4, u5, u6, u7, u8}} U/{Thân nhiệt}={{u1, u4}, {u2, u5, u7}, {u3, u6, u8}} U/{Cảm cúm}={ {u1, u4, u5, u8}, {u2, u3, u6, u7, }} U/{Đau đầu, Cảm cúm}={ {u1}, {u2, u3}, {u4, u5, u8}, {u6, u7}} Như vậy, các bệnh nhân u2, u3 không phân biệt được về đau đầu và cảm cúm, nhưng phân biệt được về thân nhiệt. 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 X={u/u (Cảm cúm)=Có}={ u2, u3, u6, u7}. Khi đó: BX ={ u2, u3} BX ={ u2, u3, u5, u6, u7, u8}. Như vậy, B miền biên của X là tập hợp BNB(X)={u5, u6, u7, u8}. Nếu đặt D={Cảm cúm} thì: 8 U/D ={X1= { u1, u4, u5, u8}; X2={ u2, u3, u6, u7}}, BX 1={ u1, u4} BX 2 ={ u2, u3} POSB (D)= X U ( BX )={ u1, u2, u3, u4}. U /D 1.3.3. Tập rút gọn và tập lõi Trong bảng quyết định, các thuộc tính điều kiện được phân thành 3 nhóm: thuộc tính lõi (core attribute), thuộc tính rút gọn (reductive attribute) và thuộc tính dư thừa (redundant attribute). Thuộc tính lõi là thuộc tính 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 lõi xuất hiện trong tất cả các tập rút gọn của bảng quyết định. Thuộc tính dư thừa là những thuộc tính mà việc loại bỏ chúng không ảnh hưởng đến việc phân lớp tập dữ liệu, thuộc tính dư thừa không xuất hiện trong bất kỳ rút gọn nào của bảng quyết định. Thuộc tính rút gọn là thuộc tính xuất hiện trong một tập rút gọn nào đó của bảng quyết định. Định nghĩa 1.3. (Tập lõi dựa trên miền dương) Cho bảng quyết định DS = (U, C∪D, V,f). Thuộc tính c∈C được gọi là không cần thiết (dispensable) trong DS dựa trên miền dương nếu POSC(D)=POS(C-{c})(D). Ngược lại, c được gọi là cần thiết (indispensable). 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 dựa trên miền dương và được ký hiệu là PCORE (C). Khi đó, thuộc tính cần thiết chính là thuộc tính lõi. Theo Định nghĩa 1.3 thuộc tính không cần thiết được gọi là thuộc tính dư thừa hoặc thuộc tính rút gọn. Định nghĩa 1.4 (Tập rút gọn dựa trên miền dương) Cho bảng quyết định DS=(U, C∪D, V, f). Và tập thuộc tính R∈C. Nếu: 1) POSR (D)=POSC (D) 2) Mọi r∈R, POSR-{r} (D)≠POSC (D) 9 Thì R là một tập rút gọn của C dựa trên miền dương. Tập rút gọn định nghĩa như trên còn gọi là tập rút gọn Pawlak. Ký hiệu I (C ) PRED(C) là họ tất cả các tập rút gọn Pawlak của C. Khi đó PCORE (C) = R PRED R. Định nghĩa 1.5. Cho bảng quyết định DS = (U, C∪D, V, f). Và a∈C. Ta nói rằng a là thuộc tính rút gọn của DS nếu tồn tại 1 tập 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 rằng a U ( D ) R. là thuộc tính dư thừa của DS nếu a∈C- R PRED Ví dụ 1.2. Xét bảng quyết định về bệnh cúm cho ở Bảng 1.2 Bảng 1.2. Bảng quyết định về bệnh cúm U Mệt mỏi Đầu đầu Đau cơ Thân nhiệt Cảm cúm u1 Có Có Có Bình thường Không u2 Có Có Có Cao Có u3 Có Có Có Rất cao Có u4 Có Không Có Bình thường Không u5 Có Không Không Cao Không u6 Có Không Có Rất cao Có Bảng này có hai tập rút gọn là R1={Đau cơ, Thân nhiệt}, R2={Đâu đầu, thân nhiệt}. Như vậy tập lõi là PCORE (C)={Thân nhiệt} và Thân nhiệt là thuộc lõi duy nhất. Các thuộc tính không cần thiết bao gồm: 10 +Thuộc tính Mệt mỏi là thuộc tính dư thừa vì không tham gia vào rút gọn nào +Hai thuộc tính Đau đầu và Đau cơ là hai thuộc tính rút gọn vì đều có mặt trong một tập rút gọn. Hai thuộc tính này đều không cần thiết theo nghĩa là, từ bảng dữ liệu, có thể loại bỏ một trong hai thuộc tính này mà vẫn chuẩn đoán đúng bệnh. Tức là: POS{Đau cơ, Thân nhiệt}({Cảm cúm})= POSC({Cảm cúm}) POS{Đau đầu, Thân nhiệt}({Cảm cúm})= POSC({Cảm cúm}) 1.4. Hệ thông tin không đầy đủ và mô hình tập thô dung sai Trong phần này, em xin trình bày các khái niệm cơ bản về mô hình tập thô mở rộng trong hệ thông tin không đầy đủ dựa trên quan hệ dung sai do Marzena Kryszkiewicz [6] đề xuất. 1.4.1. Hệ thông tin không đầy đủ Như đã trình bày ở trên hệ thông tin IS=(U, A, V, f), nếu tồn tại u∈U và a∈A sao cho a(u) thiếu giá trị IS được gọi là hệ thông tin không đầy đủ. Ta biểu diễn giá trị thiếu là ‘*’ và hệ thông tin không đầy đủ là IIS= (U, A, V, f ). Xét hệ thông tin không đầy đủ IIS = (U, A, V, f ). Với tập thuộc tính P∈A ta định nghĩa một quan hệ nhị phân trên U như sau: SIM(P)={(u,v)∈U x U/  a∈P, a(u)= a(v) ∨a(u)=’*’∨a(v)=’*’}. Quan hệ SIM(P) không phải là quan hệ tương đương vì chúng có tính phản xạ, đối xứng nhưng không có tính bắc cầu. SIM (P) là một quan hệ dung sai (tolerance relation), hay quan hệ tương tự (similarity relation) trên U. Theo [6], SIM (P)=∩a∈PSIM({a}). 11 Gọi SP(u) là tập {v∈U/(u,v)∈SIM (P) }. SP(u) là tập lớn nhất các đối tượng không có khả năng phân biệt được với u trên tập thuộc tính P, còn gọi là một lớp dung sai hay một hạt thông tin. Ký hiệu tập tất cả các lớp dung sai sinh bởi quan hệ SIM (P) trên U là U/ SIM (P), khi đó các lớp dung sai trong U/ SIM (P) không phải là một phân hoạch của U mà hình thành một phủ của U vì chúng có thể giao nhau và ∪u∈U SP(u)= U. Ký hiệu tập tất các phủ của U sinh bởi các tập con thuộc tính P∈A là COVER(U). Trên COVER(U) ta định nghĩa một quan hệ thứ tự bộ phận (COVER(U),∈) như sau: Định nghĩa 1.7.[9]Cho hệ thông tin không đầy đủ IIS=(U,A,V,f) với P, Q∈A. Ta nói: 1) Phủ U/SIM(P) và phủ U/SIM(Q) là như nhau (viết U/SIM(P) = U/SIM(Q)) khi và chỉ khi  u∈U, SP(u)=SQ(u). 2) U/SIM(P) mịn hơn U/SIM(Q) (viết U/SIM(P) ∈U/SIM(Q)) khi và chỉ khi  u∈U, SP(u)∈SQ(u). Trên (COVER(U),∈), phần tử nhỏ nhất gọi là phủ rời rạc ω={SA(u)/ SA(u )= {u}, u∈U} và phần tử lớn nhất gọi là phủ một khối δ={SA(u)/ SA(u )= U, u∈U}. Tính chất 1.2. [7] Cho hệ thông tin không đầy đủ IIS =(U, A, V, f) 1) Nếu P∈Q∈A thì SQ(u)∈SP(u) với mọi u∈U. 2) Nếu P∈Q∈A thì U/SIM(Q)∈U/SIM(P). 3) Nếu P, Q ∈A thì SP∪Q(u)= SP(u)∩SQ(u) với mọi u∈U. Tương tự hệ thông tin đầy đủ, các tập P- xấp xỉ dưới và P- xấp xỉ trên của X trong hệ thông tin không đầy đủ, ký hiệu lần lượt là P X và P X được xác định như sau: 12 P X = {u∈U/ SP(u) ∈X}={u∈X/ SP(u) ∈X} P X= {u∈U/ SP(u) ∩X≠  }=∪{ SP(u)/u ∈U} Với các tập xấp xỉ nêu trên, ta gọi P- miền biên của X là tập: BN P(X)= P X P X và P- Miền ngoài của X là tập: U- P X. Ví dụ 1.3. Bảng 1.3 biểu diễn thông tin về các xe hơi là hệ thông tin không đầy đủ IIS = {U, A, V, f}với U={u1, u2, u3, u4, u5, u6}, A={a1, a2, a3, a4} với a1 (Đơn giá), a2 (KM đã đi), a3 (Kích thước), a4 (Tốc độ tối đa). Bảng 1.3. Bảng thông tin về các xe hơi Ô tô Đơn giá Km đã đi Kích thước Tốc độ tối đa u1 Cao Cao Đầy đủ Thấp u2 Thấp * Đầy đủ Thấp u3 * * Gọn nhẹ Cao u4 Cao * Đầy đủ Cao u5 * * Đầy đủ Cao u6 Thấp Cao Đầy đủ * U/SIM(A)= {SA(u1), SA(u2), SA(u3), SA(u4), SA(u5), SA(u6)}, với SA(u1)={u1}, SA(u2)={u2,u6}, SA(u3)={u3},SA(u4)={u4,u5},SA(u5)={u4, u5,u6}, SA(u6)={u2, u5,u6}. Với P={a3,a4} ta có: U/SIM(P)={SP(u1), SP(u2), SP(u3), SP(u4), SP(u5), SP(u6)}, với SP(u1)=SP(u2)={u1,u2, u6}, SP(u3)={u3}, SP(u4)=SP(u5)={u4, u5,u6},