Về một vấn đề tương đương liên quan đến tập rút gọn trong bảng quyết định

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

Thêm vào BST

Báo xấu

19
lượt xem 1
download

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

Mục tiêu của bài viết này là trình bày một kết quả mang tính tương đương của họ các tập rút gọn trong bảng quyết định nhất quán với hệ Sperner. Từ đó nhận được một số kết quả liên quan đến các đặc trưng tổ hợp của các tập rút gọn.

Chủ đề:

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

Lưu

Nội dung Text: Về một vấn đề tương đương liên quan đến tập rút gọn trong bảng quyết định

Kỷ K yếu Hội nghị KHCN Quốc giaa lần thứ XII về Nghiên cứu cơ bản b và ứng dụng g Công nghệ thôông tin (FAIR); H Huế, ngày 07-08/6/2019 DOI: D 10.15625//vap.2019.00068 VỀ MỘ ỘT VẤN Đ ĐỀ TƯƠ ƠNG ĐƯƠ ƠNG LIÊN N QUAN ĐẾN TẬ ẬP RÚT GỌN G TR RONG BẢ ẢNG QUYYẾT ĐỊNH H Vũ V Đức Thi Đại họcc quốc gia Hà nội Email: vdthi@vnu.ed v du.vn TÓM T TẮT: Hướ ớng khai phá dữ ữ liệu xử dụng llí thuyết tập thô ô đã được nhiều u tác giả trên thhế giới nghiên ccứu và phát triển ứng dụng, đã đ đạt được nhiều kết quả khả quan, đặc biệt nnghiên cứu về các c tập rút gọn trong bảng quyyết định. Các C tập rút gọn trong bảng quyyết định đã đượ ợc ứng dụng nh hiều trong thực tiễn. Bài báo n ày liên quan chhặt chẽ đến các tập rút gọn trrong bảng quyếết định nhất quáán. Trong bài bbáo này, tác giả ả nghiên cứu phhát triển những đặc trưng tổ hợ ợp của các tập rút gọn. Hệ Sperner S là một hệ h tổ hợp đã đư ược nhiều nhà kkhoa học nghiên cứu và phát triển. t Tác giả chhứng minh về vvấn đề tương đưương của họ các c tập rút gọn trong bảng quyyết định nhất quuán với hệ Sperrner. Trên cơ sở s này, chúng tta thu được cácc kết quả liên quuan đến các đặc đ trưng tổ hợpp của các tập rúút gọn. Keywords: K Sperrner system, redduct set, consisttent decision tab ble. Việc tìm m kiếm các tậập rút gọn đónng vai trò quan n trọng trong việc xử lí thônng tin trên bảảng quyết định h. Mục tiêu của c rút gọn thuuộc tính là loạại bỏ các thuộcc tính dư thừaa để tìm ra các thuộc tính cơơ bản phục vụ cho việc xử lí thông tin. Về V thực chất, việc v rút gọn thhuộc tính là tììm tập con nhỏ nhất của tập p các thuộc tínnh để bảo toànn thông tin phân lớp trên bảng b quyết địnnh. Trong bài báo này, chúúng tôi chỉ đề cập tới các bảng b quyết địnnh nhất quán. Trên thực tiễn, tùy theo từ ừng bài toán cụ c thể, chúng ta có thể chuyyển bảng quyếết định không nhất quán vềề bảng quyết đđịnh nhất quán n. Mục tiêu chính c b này là trìnnh bày một kếết quả về tính tương đương của bài báo g của họ các tậập rút gọn tronng bảng quyết định nhất quán q với hệ Spperner. Từ đó,, chúng ta nhậận được một số ố kết quả liên quan đến các đặc trưng tổ hhợp của các tậ ập rút gọn. 1. NHỮNG KHÁI K NIỆM CƠ BẢN Phần nàày cung cấp m một số khái niệệm cơ bản đượ ợc dùng trong g bài báo. Các khái niệm nàyy có thể xem trong [1, 3, 4, 4 6]. Định nghĩa n 1.1. Hệ thông tin là m một bộ bốn S = ( U, A, V,, f ) trong đóó U là tập hữuu hạn, khác rỗ ỗng các đối ượng; A là tậập hữu hạn, khác rỗng cáác thuộc tính; V  tư V a A a với Va làà tập giá trị ccủa thuộc tính a  A ; f : U  A  Va là hàm thhông tin, a  A, u  U f  u, a  Va . Với mọọi u  U , a  A , ta ký hhiệu giá trị th huộ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 conn các thuộc tính thì ta ký hiệệu bộ các giá ttrị bi  u  bởi B  u  . Như vậy, nếu u và v v là hai đối tượng, thì ta vviết B  u   B  v  nếu bi  u   bi  v  với mọi i  1,..., k . Định nghĩa n 1.2. Bảnng quyết địnhh là một hệ thô ông tin S = (U U, A, V, f) vớới A= C D và C  D   . Bảng quyết q định S được đ gọi là nhhất quán nếu D phụ thuộc hàm h vào C, tứ ức là với mọi u, v  U , C  u   C  v  kéo theo D  u   D  v  . Ngược lại tthì gọi là không ng nhất quán haay mâu thuẫn. C được gọi là tậập thuộc tính đi điều kiện và D là tập thuộc tíính quyết định Thông thường t D = {d}} chứa một thuuộc tính Định nghĩa n D  U, C  D,V , f  và tậpp thuộc tính 1.3. Choo bảng quyết địnnh nhất quán DS R  C . R đượcc gọi là tập rút r gọn nếu: - với mọi m cặp đối tượ ợng u, v thì R R(u) = R(v) kéo o theo D(u) = D(v) m E là tập conn thực sự của R thì tồn tại cặp u, v để E(u) = E(v) không kééo theo D(u) = D(v) - với mọi
Vũ Đức Thi 535 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 PRED  C  là họ tất cả các tập rút gọn của C. Cho R  a1 ,..., an  là tập hữu hạn, khác rỗng các thuộc tính, mỗi thuộc tính ai có miền giá trị là D  ai  . Quan hệ r trên R là tập các bộ h1 ,..., hm  với h j : R   D  ai  ,1  j  m là một hàm sao cho ai R h j  ai   D  ai  . Cho r  h1 ,..., hm  là một quan hệ trên tập thuộc tính R  a1 ,..., an  . Phụ thuộc hàm (PTH) trên R là một dãy ký tự có dạng A B với A, B  R. PTH A B thỏa mãn quan hệ r trên R nếu h , h  r   a  A  h  a  h  a   b  B  h b  h b  . Đặt i j i j i j Fr   A, B  : A, B  R, A  B là họ đầy đủ các PTH thỏa mãn quan hệ r. Ký hiệu P  R  là tập các tập con của R. Cho F  P  R   P  R  . Ta nói rằng F là một họ f trên R nếu với mọi A, B, C , D  R 1  A, A  F .  2   A, B   F ,  B, C   F   A, C   F .  3  A, B   F , A  C , D  B   C , D   F .  4   A, B   F ,  C , D   F   A  C , B  D   F . Rõ ràng là Fr là một họ f trên R. Nếu F là một họ f trên R thì có một quan hệ r trên R sao cho Fr = F. Ký hiệu F là tập tất cả các PTH được dẫn xuất từ F bằng việc áp dụng các quy tắc 1   4  .  Sơ đồ quan hệ (SĐQH) s là một cặp  R, F  với R là tập thuộc tính và F là tập các phụ thuộc hàm trên R. Ký   hiệu A  a : A  a  F  , A  được gọi là bao đóng của A trên s. Dễ thấy A  B  F  khi và chỉ khi B  A   . Tương tự ký hiệu Ar  a : A  a  F   , A r  được gọi là bao đóng của A trên quan hệ r. Cho s  R, F  là SĐQH trên R, a  R . Đặt  as  A  R: A a , B:  B a  B  A . Khi đó, as  được gọi là họ các tập tối thiểu của thuộc tính a trên s. Tương tự, cho r là một quan hệ trên R và a  R . Đặt  ar  A  R : A  a ,  B :  B  a  B  A  . Khi đó,   r a được gọi là họ các tập tối thiểu của thuộc tính a trên r. Gọi   P  R là một hệ Sperner trên R nếu với mọi A, B   kéo theo A  B . Dễ thấy Kas, Kar là các hệ Sperner trên R. Với tập  là một hệ Sperner trên R, ta định nghĩa tập  1 như sau:  1   A  R :  B      B  A  và nếu  A  C    B    B  C  Dễ thấy  1 cũng là một hệ Sperner trên R. Nếu  là một hệ Sperner trên R đóng vai trò là tập các khóa tối 1 thiểu của quan hệ r (hoặc SĐQH s) thì  là họ tất cả các tập không phải khóa lớn nhất của r (hoặc của s), gọi là tập các phản khóa. Nếu  là một hệ Sperner trên R đóng vai trò là họ các tập tối thiểu của thuộc tính a trên r (hoặc trên    ar (hoặc    as ), thì  1  ar  (hoặc  1  as  ) là họ tất cả các tập lớn nhất không 1 1 s), hay phải là tập tối thiểu của thuộc tính a, được định nghĩa như sau [1] :     A  R : A  a  F , A  B  B  a  F  , 1 r   a r r     A  R : A  a  F , A  B  B  a  F  . 1 s   a
536 VỀ MỘT VẤN ĐỀ TƯƠNG DƯƠNG LIÊN QUAN ĐẾN TẬP RÚT GỌN TRONG BẢNG QUYẾT ĐỊNH Chúng ta có thể thấy khái niệm tập tối thiểu của thuộc tính trên quan hệ r tương đương khái niệm tập rút gọn trong bảng quyết định nhất quán. 2. KẾT QUẢ Trong phần này, chúng tôi trình bày các kết quả của bài báo. Đầu tiên, chúng tôi trình bày một bổ đề cần thiết sau.  Bổ đề 2.1. [5] Cho bảng quyết định nhất quán DS  U , C  d  , V , f với  C  c1 , c2 ,..., cn  , U  u1 , u2 ,..., um  . Xét quan hệ r  u1 , u2 ,..., um  trên tập thuộc tính R  C  d  . Đặt   r   Eij :1  i  j  m với Eij  a  R : a  ui   a  u j   Đặt  d  A   r : d  A,  B   r : d  B, A  B .  d   dr  1 Thì . Ở đây dr là họ các tập tối thiểu của thuộc tính d  trên quan hệ r Định lí 2.2. [2] Cho trước bảng quyết định DS = (U, C {d}, V, f) thì (Kdr) -1 là hệ Sperner trên C. Ngược lại nếu K là hệ Sperner trên C thì tồn tại một bảng quyết định nhất quán DS = (U, C {d}, V, f) để K= (Kdr) -1 Trên cơ sở Định lí 2.2, nếu K là hệ Sperner trên C. Giả sử K = { A1,…,Am }. Chúng ta xây dựng bảng quyết định DS = ( U, C {d}, V, f) như sau: U = {u0, u1,…, um} với mọi c C : c(u0) = 0 và d(u0) = 0. Với mọi i, i = 1,… m và c là phần tử của C. Chúng ta đặt c(ui) = 0 nếu c Ai. Ngược lại c(ui) = i. Đặt d(ui) = i. Với R = C {d}. Có thể thấy K= (Kdr) -1 . Sau đây, chúng tôi đưa ra một thuật toán từ một hệ Sperner bất kỳ tìm tập phản khóa của nó. Thuật toán 2.3 [8] (Tìm tập phản khóa) Vào: = ,…, là hệ Sperner trên R. Ra: Bước 1: Ta đặt = − : ∈ . Hiển nhiên = . Bước q+1: (q < m). Ta giả thiết rằng = ∪ ,…, , ở đây ,…, chứa và = ∈ ∶ ⊈ . Đối với mỗi i (i = 1, ..., ) ta tìm các phản khóa của trên tương tự như . Kí pháp chúng là , … , . Đặt = ∪ ∶ ∈ é ℎ ⊄ , 1 ≤ ≤ . 1 ≤ ≤ . Cuối cùng ta đặt = Định lý 2.4 [8] Với mọi q (1 ≤ ≤ ), = ,…, có nghĩa là = . Rõ ràng, K và là xác định duy nhất lẫn nhau và từ định nghĩa của có thể thấy thuật toán của chúng ta không phụ thuộc vào thứ tự của dãy , … , . Đặt = ∪ ,…, và (1 ≤ ≤ − 1) là số các phần tử . Trên cơ sở này ta có: Mệnh đề 2.5. Độ phức tạp thời gian tồi nhất của Thuật toán 2.3 là Θ(| | ∑ . ). − , nếu > Ở đây: = 1 , ế =
Vũ Đức Thi 537 Rõ ràng trong mỗi bước thuật toán ta có là hệ Sperner trên R. Ta biết rằng ([8]) kích thước của hệ Sperner [ / ] [ / ] bất kỳ trên R không vượt quá , ở đây n = | |. Có thể thấy xấp xỉ bằng 2 / /( . / ). Từ đó độ phức tạp thời gian tồi nhất của thuật toán trên không nhiều hơn hàm số mũ theo n. Trong trường hợp mà ≤ (q= 1, ..., m-1), | | | | | dễ thấy rằng độ phức tạp thuật toán không lớn hơn Θ(| ). Như vậy, trong các trường hợp này độ phức tạp của Thuật toán 2.3 tìm là đa thức theo | |, | |, à | |. Có thể thấy nếu số lượng các phần tử của K là nhỏ thì Thuật toán 2.3 rất hiệu quả, nó chỉ đòi hỏi thời gian đa thức theo | |. Dựa trên các kết quả đã trình bày ở trên, chúng tôi trình bày kết quả về sự tương đương giữa các họ tất cả các tập rút gọn của một bảng quyết định nhất quán bất kỳ với các hệ Sperner. Định lí 2.6. Cho trước bảng quyết định nhất quán DS = (U, C ∪ {d}, V, f) thì PRED  C  (họ tất cả các tập rút gọn của C) là hệ Sperner trên C. Ngược lại nếu K là hệ Sperner trên C thì tồn tại một bảng quyết định nhất quán DS = (U, C ∪ {d}, V, f) để K= PRED (C). Chứng minh: Cho trước bảng quyết định nhất quán DS = (U, C ∪ {d}, V, f). Có thể thấy, theo định nghĩa của tập rút gọn, họ PRED (C) là hệ Sperner trên C. Giả sử K = { A1,…,An } là một hệ Sperner trên C. Trên cơ sở thuật toán 2.3, từ K chúng ta xây dựng tập phản khóa K-1 . Giả sử K-1 = { B1,...,Bm}. Chúng ta xây dựng bảng quyết định nhất quán DS = ( U, C∪{d}, V, f) như sau: U = {u0, u1,…, um} với mọi c ∈ C : c(u0) = 0 và d(u0) = 0. Với mọi i, i = 1,…m và c là phần tử của C. Chúng ta đặt c(ui) = 0 nếu c ∈ Bi. Ngược lại c(ui) = i. Đặt d(ui) = i. Với R = C ∪ {d}. Trên cơ sở Bổ đề 2.1 và Định lí 2.2, chúng ta có K-1= (Kdr) -1 . Trên cơ sở này và dựa trên định nghĩa của hệ Sperner, tập phản khóa và định nghĩa các tập rút gọn của bảng quyết định nhất quán, chúng ta có K = PRED (C). Kết quả đã được chứng minh xong. Trên cơ sở kết quả này, chúng ta có thể thấy ngay việc nghiên cứu họ tất cả các tập rút gọn của bảng quyết định nhất quán DS = (U, C ∪ {d}, V, f) chính là nghiên cứu các hệ Sperner trên C. Hệ Sperner là hệ tổ hợp đã được nhiều nhà khoa học trong lí thuyết tổ hợp trên thế giới nghiên cứu. Như vậy, nhiều đặc trưng tổ hợp của tập rút gọn sẽ được sáng tỏ. Trên cơ sở của Định lí 2.6 và Mệnh đề 2.5, chúng ta có ngay hệ quả sau: Hệ quả 2.7. Cho trước bảng quyết định nhất quán DS = (U, C ∪ {d}, V, f) thì PRED  C  (họ tất cả các tập [ / ] rút gọn của C) có lực lượng không vượt quá , ở đây n = |C|. LỜI CẢM ƠN: Chúng tôi xin cảm ơn sự tài trợ của Đề tài “Nghiên cứu thiết kế xây dựng thiết bị tường lửa chuyên dụng tích hợp kỹ thuật mật mã của ngành Cơ yếu” mã số 01/2018/ KCM. TÀI LIỆU THAM KHẢO [1] Demetrovics J., Thi V. D., Quang H. M., Anh N. V. (2018). An Method to reduc the size of consistent decision tables. Acta Cybernetica V 23, pp. 1039- 1054 [2] Demetrovics J., Thi V. D., Duong T. H., Giang N. L. (2015). On the time complexity of the problem related to reduct of consistent decision tables. SERDICA J. of computing. Bugarian Academy of Sciences V 9, N 2, pp. 101- 110 [3] Demetrovics J. and Thi V. D. (1995), “Some remarks on generating Armstrong and inferring functional dependencies relation”, Acta Cybernetica 12, pp. 167-180. [4] Nguyen Long Giang, Vu Duc Thi (2011), “Some Problems Concerning Condition Attributes and Reducts in Decision Tables”, Proceeding of the Fifth National Symposium “Fundamental and Applied Information Technology Research” (FAIR), Bien Hoa, Dong Nai, pp. 142-152. [5] Nguyễn Long Giang, Vũ Đức Thi (2011), “Thuật toán tìm tất cả các rút gọn trong bảng quyết định”, Tạp chí Tin học và Điều khiển học, T.27, S.3, tr. 199-205. [6] Pawlak Z. (1991), “Rough sets: Theoretical Aspects of Reasoning About Data”, Kluwer Academic Publishers. [7] Vũ Đức Thi (2018), “ Một vấn đề thuật toán liên quan đến tập rút gọn trong bảng quyết định nhất quán “. Kỷ yếu hội nghị quốc gia về “ Nghiên cứu cơ bản và ứng dụng công nghệ thông tin” lần thứ XI, Hà Nội, tr. 150-157. [8] Vu Duc Thi (1986), “ Minimal keys and antikeys “ Acta Cybernetica 7, 4, pp 361-371
538 VỀ MỘT VẤN ĐỀ TƯƠNG DƯƠNG LIÊN QUAN ĐẾN TẬP RÚT GỌN TRONG BẢNG QUYẾT ĐỊNH ON AN EQUIVALENCE PROBLEM RELATED TO THE REDUCT SET IN THE DECISION TABLE Vu Duc Thi ABSTRACT: The data mining using the theory of rough set was more of the authors in the world of research and development applications, has achieved many positive results, particularly the study of reduction in the decision table. The reduct sets in decision tables have been applied in practice. This paper is closely related to the reductions in the consistent decision table. In this paper, the author of the study develops the combinational characteristics of reduct sets. The Sperner system is a combinational system that has been researched and developed by many scientists. We show that the equivalence problem of reductions in the consistent decision table with the Sperner system. On this basis, we obtain results concerning the combinational characteristics of reduct sets. Keywords: Sperner system, reduct set, consistent decision table.