Một số vấn đề về phụ thuộc hàm và phụ thuộc hàm xấp xỉ trong lý thuyết tập thô và ứng dụng vào bài toán rút gọn thuộc tính

Bài viết trình bày một số khái niệm và tính chất liên quan đến hệ thông tin S = (U, A), phụ thuộc hàm, phụ thuộc xấp xỉ, vùng dương trong lý thuyết tập thô.
Nội dung trích xuất từ tài liệu:
Một số vấn đề về phụ thuộc hàm và phụ thuộc hàm xấp xỉ trong lý thuyết tập thô và ứng dụng vào bài toán rút gọn thuộc tính Nghiên cứu khoa học công nghệ MỘT SỐ VẤN ĐỀ VỀ PHỤ THUỘC HÀM VÀ PHỤ THUỘC HÀM XẤP XỈ TRONG LÝ THUYẾT TẬP THÔ VÀ ỨNG DỤNG VÀO BÀI TOÁN RÚT GỌN THUỘC TÍNH Nguyễn Bá Tường1* , Nguyễn Bá Quảng2 Tóm tắt: Trong bài viết này chúng tôi trình bày một số khái niệm và tính chất liên quan đến hệ thông tin S = (U, A), phụ thuộc hàm, phụ thuộc xấp xỉ, vùng dương trong lý thuyết tập thô. Chúng tôi nghiên cứu các tính chất của vùng dương, các ràng buộc giữa các thuộc tính và đặc biệt giữa các thuộc tính điều kiện trong hệ quyết định, trên cơ sở đó xây dựng thuật toán heuristic tìm tập rút gọn trong bảng quyết định sử dụng độ phụ thuộc của thuộc tính. Từ khóa: Phân hoạch; Quan hệ; Xấp xỉ; Tập thô; Phụ thuộc hàm; Phụ thuộc xấp xỉ; Rút gọn thuộc tính. 1. MỘT SỐ KHÁI NIỆM CƠ BẢN Hầu hết các định nghĩa, khái niệm cơ bản trong bài viết này được trích từ các tài liệu tham khảo [1-5]. Định nghĩa 1. Quan hệ tương đương trên tập U R là quan hệ tương đương trên tập U nếu R  U  U và R thỏa mãn ba tính chất phản xạ, đối xứng, bắc cầu. Chú ý: Thay cho (u,v) R đôi khi ta viết uRv. Quan hệ tương đương R trên U sẽ chia U thành các nhóm tương đương, ta ký hiệu họ các nhóm tương đương đó là U/R. Vậy U/R = {[t]R: với t  U và [t]R là lớp các phần tử t’ mà tRt’}. Định nghĩa 2. Phân hoạch của U Cho tập U hữu hạn, khác rỗng. Họ E = {E1, E2, ..., Ek} các tập con của U là phân hoạch của U nếu E thỏa mãn 3 điều kiện: (1) Tính khác rỗng: Các Ei khác rỗng. (2) Tính rời nhau: Ei  Ej =  nếu i  j. k (3) Tính đầy đủ: E i 1 i = U. Bổ đề 1. Cho U là tập hữu hạn khác rỗng. Khi đó a. Với mọi quan hệ tương đương R trên U thì U/R là một phân hoạch. b. Với mọi phân hoạch E = { E1, E2, ..., Ek} của U luôn tồn tại quan hệ tương đương R trên U để U/R = E. Chứng minh: a. Ta chứng minh U/R = {[t]R} là một phân hoạch (1) Tính khác rỗng: với mọi t thì [t]R khác rỗng vì ít nhất chứa t. (2) Tính rời nhau: giả sử [t]R và [t’]R là hai nhóm khác nhau, ta chứng minh [t]R  [t’]R = . Thật vậy nếu [t]R và [t’]R có phần tử chung t’’ thì dễ thấy rằng [t]R = [t’’]R = [t’]R => [t]R = [t’]R vô lý. (3) Tính đầy đủ:  [ t ] = U vì phép hợp lấy với mọi t thuộc U. R t U Tạp chí Nghiên cứu KH&CN quân sự, Số 60, 4 - 2019 161  Công nghệ thông tin & Cơ sở toán học cho tin học b. Giả sử E = {E1, E2, ..., Ek} là phân hoạch của U. k Ta xây dựng quan hệ R trên U để U/R = E. Đặt R = E i 1 i  Ei dễ dàng thử lại rằng R là quan hệ tương đương trên U và U/R = E đpcm. Định nghĩa 3. Hệ thông tin đầy đủ (complete information system) là S = (U, A), Trong đó U = {t1, t2, ..., tm} là tập hữu hạn, khác rỗng các đối tượng (Universe). A = {A1, A2, ..., An} là tập hữu hạn, khác rỗng các thuộc tính. Giá trị (thông tin) của đối tượng t U tại thuộc tính a  A là t.a. Tương tự với mọi t  U và X  A, khi đó t.X là chiếu của t lên X. Nếu giá trị của đối tượng t tại a có nhiều hơn một giá trị thì hệ thông tin là đa trị (a set- value information system). Trong bài viết này ta chỉ xét hệ thông tin đầy đủ, nên thay cho hệ thông tin đầy đủ S =(U, A) ta chỉ viết hệ thông tin S = (U, A). Trong bài viết ta sẽ dùng các ký tự X, Y, Z, V, W,... để chỉ các tập thuộc tính và các ký tự thường a, b, c, d, e,... để chỉ các thuộc tính, mặt khác ta dùng XY thay cho X  Y và abc thay cho {a, b, c}. Thông thường hệ thông tin được biểu diễn dạng bảng hai chiều (xem Bảng 1). Thí dụ trong Bảng 1: S = (U, A), với U = { t1, t2, t3, t4, t5, t6, t7, t8, t9, t10}; A = {a, b, c, d, e}; t1.a = 1, t1.abcd = (1, 1, 1, 1), t2.abcde = (2, 1, 1, 1, 1) Bảng 1. Hệ thông tin đầy đủ. U a b c d e t1 1 1 1 1 1 t2 2 1 1 1 1 t3 2 1 2 2 1 t4 3 2 2 2 1 t5 3 2 2 2 ...