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ệ<br /> <br /> MỘT SỐ VẤN ĐỀ VỀ PHỤ THUỘC HÀM VÀ PHỤ THUỘC HÀM<br /> XẤP XỈ TRONG LÝ THUYẾT TẬP THÔ VÀ ỨNG DỤNG VÀO BÀI<br /> TOÁN RÚT GỌN THUỘC TÍNH<br /> Nguyễn Bá Tường1* , Nguyễn Bá Quảng2<br /> 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<br /> 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<br /> 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<br /> 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ệ<br /> 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<br /> quyết định sử dụng độ phụ thuộc của thuộc tính.<br /> 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.<br /> <br /> 1. MỘT SỐ KHÁI NIỆM CƠ BẢN<br /> 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<br /> tham khảo [1-5].<br /> Định nghĩa 1. Quan hệ tương đương trên tập U<br /> 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<br /> xạ, đối xứng, bắc cầu.<br /> Chú ý: Thay cho (u,v) R đôi khi ta viết uRv.<br /> 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ọ<br /> các nhóm tương đương đó là U/R.<br /> Vậy U/R = {[t]R: với t  U và [t]R là lớp các phần tử t’ mà tRt’}.<br /> Định nghĩa 2. Phân hoạch của U<br /> Cho tập U hữu hạn, khác rỗng.<br /> 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<br /> kiện:<br /> (1) Tính khác rỗng: Các Ei khác rỗng.<br /> (2) Tính rời nhau: Ei  Ej =  nếu i  j.<br /> k<br /> (3) Tính đầy đủ: E<br /> i 1<br /> i = U.<br /> <br /> Bổ đề 1. Cho U là tập hữu hạn khác rỗng. Khi đó<br /> a. Với mọi quan hệ tương đương R trên U thì U/R là một phân hoạch.<br /> 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<br /> trên U để U/R = E.<br /> Chứng minh:<br /> a. Ta chứng minh U/R = {[t]R} là một phân hoạch<br /> (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.<br /> (2) Tính rời nhau: giả sử [t]R và [t’]R là hai nhóm khác nhau, ta chứng minh<br /> [t]R  [t’]R = . Thật vậy nếu [t]R và [t’]R có phần tử chung t’’ thì dễ<br /> thấy rằng [t]R = [t’’]R = [t’]R => [t]R = [t’]R vô lý.<br /> (3) Tính đầy đủ:  [ t ] = U vì phép hợp lấy với mọi t thuộc U.<br /> R<br /> t U<br /> <br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 60, 4 - 2019 161<br />  Công nghệ thông tin & Cơ sở toán học cho tin học<br /> <br /> b. Giả sử E = {E1, E2, ..., Ek} là phân hoạch của U.<br /> k<br /> Ta xây dựng quan hệ R trên U để U/R = E. Đặt R = E<br /> i 1<br /> i  Ei dễ dàng thử lại rằng R<br /> <br /> là quan hệ tương đương trên U và U/R = E đpcm.<br /> Định nghĩa 3. Hệ thông tin đầy đủ (complete information system) là S = (U, A), Trong<br /> đó U = {t1, t2, ..., tm} là tập hữu hạn, khác rỗng các đối tượng (Universe). A = {A1, A2,<br /> ..., 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<br /> 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<br /> 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-<br /> value information system).<br /> 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<br /> =(U, A) ta chỉ viết hệ thông tin S = (U, A).<br /> 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ý<br /> 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à<br /> abc thay cho {a, b, c}.<br /> Thông thường hệ thông tin được biểu diễn dạng bảng hai chiều (xem Bảng 1).<br /> Thí dụ trong Bảng 1: S = (U, A), với U = { t1, t2, t3, t4, t5, t6, t7, t8, t9, t10};<br /> A = {a, b, c, d, e}; t1.a = 1, t1.abcd = (1, 1, 1, 1), t2.abcde = (2, 1, 1, 1, 1)<br /> Bảng 1. Hệ thông tin đầy đủ.<br /> U a b c d e<br /> t1 1 1 1 1 1<br /> t2 2 1 1 1 1<br /> t3 2 1 2 2 1<br /> t4 3 2 2 2 1<br /> t5 3 2 2 2 2<br /> t6 3 2 2 3 2<br /> t7 2 2 3 3 2<br /> t8 1 2 3 1 3<br /> t9 1 3 3 1 3<br /> t10 1 3 1 1 2<br /> Định nghĩa 4. Hệ thông tin S’ = (U’, A ) là hệ thông tin con của S = (U, A) nếu U’  U.<br /> Định nghĩa 5. Hệ quyết định là hệ tin SD mà trong tập thuộc tính A có tập thuộc tính<br /> quyết định D.<br /> Vậy hệ quyết định SD = (U, A); trong đó A = C  D; C  D = . Tập C được gọi là<br /> tập thuộc tính điều kiện, D là tập thuộc tính quyết định.<br /> Phân hoạch U/C = { X1, X2, ..., Xk} là phân hoạch điều kiện.<br /> Phân hoạch U/D = {Y1, Y2, ..., Yl} là phân hoạch quyết định.<br /> Định nghĩa 6. Hệ quyết định SD = (U, C  D ) là nhất quán nếu mọi cặp t, t’U mà<br /> t.C = t’.C thì t.D = t’.D. Nói cách khác SD là nhất quán nếu các đối tượng giống nhau trên<br /> C thì giống nhau trên D.<br /> Định nghĩa 7. Cho hệ thông tin S = (U, A);<br /> Tập R  A được gọi là tập rút gọn của A nếu R là tập tối thiểu thỏa mãn<br /> U/R = U/A.<br /> <br /> <br /> 162 N. B. Tường, N. B. Quảng, “Một số vấn đề về phụ thuộc hàm … rút gọn thuộc tính.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> Thí dụ xét hệ thông tin trong Bảng 1 ta có R = acde là một rút gọn vì R là tập tối thiểu<br /> mà U/R = U/A. R tối thiểu ở đây phải hiểu rằng bỏ khỏi R một thuộc tính thì tập còn lại<br /> cho phân hoạch khác U/A. Chẳng hạn ta có R = acde là rút gọn vì U/R = U/acde<br /> =U/A và U/cde ≠ U/A, U/ade ≠ U/A, U/ace ≠ U/A, U/acd ≠ U/A.<br /> Định nghĩa 8. Cho hệ thông tin S = (U, A), X  A . Trên tập đối tượng U xác định<br /> quan hệ IND(X) như sau: IND(X) = { (t, t’)  U  U: t.X = t’.X}. Quan hệ IND(X)<br /> được gọi là quan hệ bất khả phân biệt (hay quan hệ giống nhau) trên tập thuộc tính X của<br /> các đối tượng t và t’.<br /> Rõ ràng rằng quan hệ IND(X) là quan hệ tương đương trên U. Khi đó phân hoạch<br /> U/IND(X) ta sẽ ký hiệu là U/X và U/X = { [t]X: t  U}. Trong đó [t]X = { t’  U: (t, t’) <br /> IND(X)} là lớp tương đương của đối tượng t.<br /> Định nghĩa 9. Cho hệ thông tin S = (U, A); X, Y  A. Nếu mỗi lớp tương đương của<br /> U/X là tập con của một lớp tương đương trong U/Y thì ta nói U/X mịn hơn U/Y và ký hiệu<br /> U/X  U/Y.<br /> Bổ đề 2. Cho hệ thông tin S = (U, A), X  Y  A. Khi đó với mọi t  U thì<br /> a. [t]Y  [t]X<br /> b. [t]X là hợp của một số lớp tương đương trong phân hoạch U/Y. Hay<br /> [t]X =  [t’]Y (1)<br /> c. IND(Y)  IND(X).<br /> d. U/Y  U/X.<br /> Chứng minh:<br /> a. Nếu X  Y  A thì [t]Y  [t]X. Thật vậy lấy t’  [t]Y => t.Y = t’.Y mặt khác theo<br /> giả thiết X nằm trong Y nên t.X = t’.X => t’  [t]X => [t]Y  [t]X đpcm.<br /> b. Để chứng minh mỗi lớp tương đương của U/X là hợp của một số lớp tương đương<br /> của U/Y ta giả sử rằng [t]X ={ t1, t2, ..., tk}, khi đó [t]X =[t1]X= [t2]X =...= [tk]X. Hiển nhiên<br /> rằng t1  [t1]Y, t2  [t2]Y,..., tk  [tk]Y từ đây suy ra<br /> [t]X = { t1, t2, ..., tk}  [t1]Y  [t2]Y  ...  [tk ]Y (*)<br /> Mặt khác từ chứng minh phần a. ta lại có<br /> [t1]X  [t1]Y<br /> [t2]X  [t2]Y<br /> [t3]X  [t3]Y<br /> ...<br /> [tk]X  [tk]Y<br /> Hợp hai vế ta có [t1]X  [t2]X ... [tk]X  [t1]Y  [t2]Y  ...  [tk]Y<br /> mà [t1]X  [t2]X  ...  [tk]X = [t]X nên [t]X  [t1]Y  [t2]Y  ...  [tk]Y (**)<br /> Từ (*) & (**) ta có [t]X = [t1]Y  [t2]Y  ...  [tk]Y đpcm.<br /> c. Chứng minh IND(Y)  IND(X): lấy (t, t’)  IND(Y) => t.Y = t’.Y, mặt khác vì X<br />  Y nên t.X = t’.X => (t, t’)  IND(X) => IND(Y)  IND(X) đpcm.<br /> d. Chứng minh phần d suy từ phần a.<br /> Định nghĩa 10. Cho hệ thông tin S = (U, A); X, Y  A.<br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 60, 4 - 2019 163<br />  Công nghệ<br /> nghệ thông tin & C<br /> Cơ<br /> ơ sở<br /> sở toán học cho tin học<br /> <br /> Vùng dương (positive region) của<br /> ủa X và<br /> và Y, ký hi<br /> hiệu<br /> ệu POS(X, Y) llàà hợp<br /> hợp của các nhóm của<br /> U/X đư<br /> được<br /> ợc bao hhàm<br /> àm trong các nhóm ccủa<br /> ủa U/Y. Hay<br /> POS(X, Y) =  {[t]X  U/X: [t]X  [t]Y với<br /> ới [t]Y  U/Y}.<br /> Ví dụụ xét hệ thông tin trong Bảng 1 ta có U/ab = { { t1}, {t2, t3}, {t4, t5, t6}, {t7}, {t8},<br /> {t9, t10}} và U/abc = { { t1}, {t2}, {t3}, {t4, t5, t6}, {t7}, {t8}, {t9}, {t10}}. Khi đó POS(abc,<br /> ab) = U & POS(ab, abc) = {t1}  {t4, t5, t6}  {t7}  {t8} = {t1, t4, t5, t6, t7, t8}<br /> ịnh nghĩa 11. Cho hhệệ quyết định T = (U, C<br /> Định C D );<br /> Tập<br /> ập R  C đư ợc gọi llà tập<br /> được tập rút gọn của C nếu ếu R llàà ttập<br /> ập tối thiểu thỏa m mãn<br /> ãn<br /> POS(R, D) = POS(C, D).<br /> Khi đó, R được<br /> được gọi llà tập<br /> ập rút gọn miền ddương.<br /> ương.<br /> Bổổ đề 3. Cho hhệệ thông tin S = (U, A). Khi đó với mọi bộ 3 tập thuộc tính X, Y, Z ta<br /> luôn có<br /> POS(X, Y)  POS(XZ, YZ) (2)<br /> và POS(X, Y)  POS(X, Y Y\Z)<br /> Z)<br /> Chứng minh:<br /> Chứng<br /> Lấy<br /> ấy t  POS(X, Y) ta ph ải chứng<br /> phải chứng minh t  POS(XZ, YZ).<br /> Đểể chứng minh t  POS(XZ, YZ), ta ch chứng<br /> ứng minh [t]XZ  [t]YZ.<br /> Lấy<br /> ấy t’  [t]XZ => t.XZ = t’.XZ => t.X = t’.X & t.Z = t’.Z.<br /> Vì t.X = t’.X nên t’<br /> t’<br />  [t]X mặt<br /> mặt khác vvìì t  POS(X, Y) nên [t]X  [t]Y => t’ t’  [t]Y => t.Y<br /> =t’.Y . Từ<br /> Từ t.Y = t’.Y & t.Z = t’.Z ta có t.YZ = t’.YZ => t’  [t]YZ.<br /> Suy ra POS(X, Y)  POS(XZ, YZ) đpcm.<br /> Tương tựtự ta chứng minh POS(X, Y)  POS(X, Y<br /> Y\Z).<br /> Z). L<br /> Lấy<br /> ấy t  POS(X, Y) ta ph<br /> phải<br /> ải chứng<br /> minh t  POS(X, Y\Y\Z).<br /> Z).<br /> Thật<br /> Th ật vậy vvìì với<br /> với mọi t thuộc POS(X, Y) th thìì [t]X  [t]Y m<br /> mặtặt khác theo phần a. ccủa ủa bổ đề<br /> 2 ta llại<br /> ại có [t]Y  [t]Y\\Z => [t]X  [t]Y\\Z => t  POS(X, Y Y\Z)<br /> Z) đpcn.<br /> Ví ddụụ xét hệ thống thông tin trong Bảng 1 ta có:<br /> U/a = {{ t1, t8, t9, t10 }, { t2, t3, t7 }, { t4, t5, t6 }} & U/b = {{ t1, t2, t3 }, { t9, t10 }, { t4, t5, t6, t7, t8}}.<br /> Vậyậy POS(a, b) = { t4, t5, t6 }.<br /> U/ac = {{ t1, t10 }, { t2}, {t3}, { t4, t5, t6 }, {t7}, {t8, t9}} & U/bc = {{ t1, t2}, {t 3 }, { t4, t5,<br /> t6}, {t7}, {t8, t9}, {t10}}.<br /> Vậy<br /> ậy POS(ac, bc) = {t2}  {t3}  { t4, t5, t6 } {t<br /> {t7} {t<br />  8, t9} = { t2, t3, t4, t5, t 6, t7, t8, t9}.<br /> Suy ra POS(a, b)  POS(ac, bc).<br /> ịnh nghĩa 12. Cho hhệệ thông tin S = (U, A ); X, Y  A. Ta nói Y ph<br /> Định phụ<br /> ụ thuộc hàm<br /> hàm vào<br /> X ( hay X xác đđịnh<br /> ịnh phụ thuộc hhàmàm Y) trong S, nnếu<br /> ếu với mọi cặp t, t’<br /> t’ U mà t.X = t’.X<br /> thì t.Y = t’.Y. Khi đó ta nói S th<br /> thỏa<br /> ỏa mãn<br /> mãn ph<br /> phụ àm X → Y vvàà ký hiệu:<br /> ụ thuộc hhàm hiệu: S X → Y.<br /> ịnh nghĩa 13. Cho hhệệ thông tin S = (U, A ); X, Y  A.<br /> Định<br /> Tập<br /> ập Y đđư ợc gọi llàà phụ<br /> ược phụ thuộc hhàm<br /> àm độđộ k(X→Y) vào X trong S, ký hi<br /> hiệu<br /> ệu<br /> k ( X Y )<br /> S X    Y nnếu<br /> ếu<br /> Card ( POS ( X ,Y ))<br /> k(X→Y) =<br /> k(X→Y) (3)<br /> Card (U<br /> U)<br /> <br /> <br /> 164 N. B. Tư<br /> Tường,<br /> ờng, N. B. Quảng, “Một số vấn đề về phụ thuộc h<br /> hàm<br /> àm … rút ggọn<br /> ọn thuộc tính.””<br /> thuộc tính.<br /> Nghiên ccứu<br /> ứu khoa học công nghệ<br /> <br /> Thí dụ<br /> dụ xét hệ thông tin trong Bảng 1, đặt X = ac, Y = bc ta có POS(X, Y) = { t 2, t3, t4, t5, t6,<br /> Card ( POS ( X ,Y<br /> Y )) 8 0.8<br /> t7, t8, t9}. Khi đó k(X→Y) = = = 0.8 và ta có S <br /> X   Y<br /> Card (U ) 10<br /> rằng nếu k(X→Y) = 1 th<br /> Lưu ý rằng thìì S 1 Y = S<br /> X <br />  X <br /> Y<br /> ổ đề 4. Cho h<br /> Bổ hệệ thông tin S = (U, A ); X, Y  A. Khi đó<br /> S X → Y khi vvàà ch<br /> chỉỉ khi U/X  U/Y<br /> Chứng minh:<br /> Chứng<br /> - Đi<br /> Điều<br /> ều kiện cần nếu S X → Y &  t  U, ta sẽsẽ chứng minh [t]X  [t]Y.<br /> Th ật vậy lấy t’  [t]X => t’.X = t.X và vì X → Y nên<br /> Thật nên t.Y = t’.Y => t’  [t]Y<br /> => [t]X  [t]Y => U/X  U/Y<br /> - Đi<br /> Điều<br /> ều kiện đủ nếu U/X  U/Y ta ssẽẽ chứng minh S X → Y.<br /> Th<br /> Thậtật vậ<br /> vậy<br /> y vì U/X  U/Y nên m mọi<br /> ọi t  U ta luôn có [t]X  [t]Y. L<br /> Lấy<br /> ấy t, t’  U & t.X = t’.X<br /> => t, t’  [t]X => t, t’  [t]Y => t.Y = t’.Y => S X → Y.<br /> ổ đề 5. Cho h<br /> Bổ hệệ thông tin S = (U, A ); X, Y  A. Khi đó<br /> S X → Y khi vvàà ch<br /> chỉỉ khi POS(X, Y) = U.<br /> Chứng minh:<br /> Chứng<br /> - Đi<br /> Điều<br /> ều kiện cần giả sử S X → Y ta phphải<br /> ải chứng minh POS(X, Y) = U. Theo bổ đề 4<br /> ta đđãã ch<br /> chứng<br /> ứng minh với mọi t  U thì [t]X  [t]Y. Suy ra<br /> POS(X, Y) =  {[t]X  U/X: [t]X  [t]Y với<br /> ới [t]Y  U/Y}= U.<br /> - Điều<br /> ều kiện đủ giả sử POS(X, Y) = U ta phải chứng minh S X → Y.<br /> Vì POS(X, Y) = U nên vvới<br /> ới mọi t thuộc U ta luôn có [t]X  [t]Y => nnếu<br /> ếu t.X = t’.X th<br /> thìì t.Y =<br /> t’.Y => S X → Y đpcm.<br /> 2. M<br /> MỘT<br /> ỘT SỐ TÍNH CHẤT CỦA CÁC PHỤ THUỘC H<br /> HÀM<br /> ÀM<br /> Cho hệ<br /> h thông tin S = (U, A ); X, Y, Z, V  A. Sau đây chúng ta ssẽẽ xét các tính chất<br /> của<br /> ủa phụ thuộc hhàm<br /> àm trong hhệệ thông tin S = (U, A).<br /> chất 1. Tính ph<br /> Tính chất phản<br /> ản xạ<br /> Ta luôn có S X → X. Mặt<br /> Mặt khác nếu Y  X thì S X → Y.<br /> Chứng minh:<br /> Chứng<br />  t, t’  U nnếu<br /> ếu t.X = t’.X => t.X = t’.X => S X → X. M<br /> Mặt<br /> ặt khác nếu Y  X. D<br /> Dễễ<br /> dàng thấy<br /> ấy rằng  t, t’  U nnếu<br /> ếu t.X = t’.X => t.Y = t’.Y => S X → Yđpcm.<br /> chất 2. Tính m<br /> Tính chất mở<br /> ở rộng hai vế<br /> Nếu<br /> ếu S X → Y => S XZ → YZ. Trong đó XZ = X  Z<br /> Chứng minh:<br /> Chứng<br />  t, t’  U vì S X → Y nên nên t.X = t’.X => t.Y = t’.Y.<br /> Bây giờ<br /> giờ giả sử t.XZ = t’.XZ => t.X = t’.X & t.Z = t’.Z => t.Y =t’.Y & t.Z = t’.Z =><br /> t.YZ = t’.YZ => S XZ → YZ đpcm.<br /> chất 3. Tính B<br /> Tính chất Bắc<br /> ắc cầu<br /> Với<br /> ới mọi bộ ba các tập thuộc tính X, Y, Z, nếu S X→Y<br /> X→Y & S Y → Z => S X→Z<br /> <br /> <br /> Tạp<br /> ạp chí Nghi<br /> Nghiên<br /> ên cứu<br /> cứu KH&CN quân<br /> uân sự,<br /> sự, Số 60, 4 - 2019<br /> 20 165<br />  Công nghệ<br /> nghệ thông tin & C<br /> Cơ<br /> ơ sở<br /> sở toán học cho tin học<br /> <br /> Chứng<br /> Chứng minh:<br /> Giả sử t.X = t’.X ta phải chứng minh t.Z = t’.Z. Thật vậ<br /> Giả vậyy vì S X → Y nnên ên nếu<br /> nếu t.X =<br /> t’.X thì t.Y = t’.Y và vì S Y → Z nnên ên nếu<br /> nếu t.Y = t’.Y th<br /> thìì t.Z = t’.Z =><br /> S X → Z đpcm.<br /> chất 4. Tính tựa<br /> Tính chất tựa bắc cầu<br /> ới mọi bộ bốn các tập thuộc tính X, Y, Z, V nếu S X →Y & S YZ → V => S XZ → V.<br /> Với<br /> Chứng minh:<br /> Chứng<br /> Vì S X → Y nên nên theo tính chchất<br /> ất 2 ta có S XZ → YZ vvàà vì S YZ → V nên nên theo<br /> tính ch ất 3 ta có S XZ → V đpcm.<br /> chất<br /> chất 5. Tính m<br /> Tính chất mở<br /> ở rộng trái, thu hẹp ph<br /> phải<br /> ải<br /> Với<br /> ới mọi bộ bốn các tập thuộc tính X, Y, Z, V nếu S X→ →Y Y =>S XZ → Y \ V<br /> Chứng minh:<br /> Chứng<br /> Theo tính ch ất 1 ta có S XZ → X, theo gi<br /> chất giảả thiết ta có S X → Y theo tính ch chất<br /> ất 3<br /> suy ra S XZ → Y vvàà ti tiếp<br /> ếp tục theo tính chất 1 ta lại có S Y → Y Y\\V<br /> V => theo tính ch<br /> chất<br /> ất 3<br /> ta có S XZ → Y Y\VV đpcm.<br /> chất 6. Tính ccộng<br /> Tính chất ộng đầy đủ<br /> Với<br /> ới mọi bộ bốn các tập thuộc tính X, Y, Z, V nếu S X→Y →Y & S Z → V<br /> => S XZ → YV<br /> Chứng minh:<br /> Chứng<br /> Vì S X → Y nên nên theo tính ch<br /> chất<br /> ất 2 ta có S XZ → YZ, vì vì S Z → V nnên<br /> ên theo tính<br /> chất 2 ta có S<br /> chất YZ → YV theo tính ch ất 3 ta có S XZ → YV đpcm.<br /> chất<br /> chất 7. Tính Tích llũy<br /> Tính chất ũy<br /> Với<br /> ới mọi<br /> mọi bộ bốn tập thuộc tính X, Y, Z, V nếu S X → Y & S Y → ZV<br /> => S X → XYZV<br /> Chứng minh:<br /> Chứng<br /> Theo tính ch<br /> chất<br /> ất 1 ta có S X → X (*)<br /> Theo giả<br /> giả thiết ta có S X → Y (**)<br /> Theo giả<br /> giả thiết ta có S Y → ZV<br /> Theo tính ch<br /> chất<br /> ất 3 ta có S X → ZV (***)<br /> Theo tính ch<br /> chất<br /> ất 6 cộng hai vế của (*) & (**) & (***) ta có S X → XYZV đpcm.<br /> Bổổ đề 6. Cho hhệệ thông tin S = (U, A ); X, Y  A. Khi đó<br /> S X → Y khi vvàà chỉ<br /> chỉ khi U/X = U/XY<br /> Chứng minh:<br /> Chứng<br /> - Đi<br /> Điều<br /> ều kiện cần giả sử S X → Y, ta chchứng<br /> ứng minh U/X = U/XY.<br /> Đểể chứng minh U/X = U/XY ta sẽ chứng minh  tU, t U, [t]X =[t]XY. Thật<br /> Thật vậy theo bổ đề<br /> 2  tUU ta có [t]XY  [t]X, Mặt<br /> Mặt khác theo giả thiết & tính phản xạ của phụ thuộc hhàm àm ta có<br /> S X→Y<br /> S X→X<br /> Theo tính ch<br /> chất<br /> ất cộng hai vế (tính chất 6) ta có<br /> S X → XY<br /> Theo bổ<br /> bổ đề 3 ta có [t]X  [t]XY.<br /> Vậy<br /> ậy  t  U [t]X = [t]XY => U/X = U/XY.<br /> - Đi<br /> Điều<br /> ều kiện đủ giả sử U/X = U/XY.<br /> <br /> <br /> 166 N. B. Tư<br /> Tường,<br /> ờng, N. B. Quảng, “Một số vấn đề về phụ thuộc h<br /> hàm<br /> àm … rút ggọn<br /> ọn thuộc tính.””<br /> thuộc tính.<br /> Nghiên ccứu<br /> ứu khoa học công nghệ<br /> <br /> Vì U/X = U/XY nên  t  U [t]X = [t]XY => =>t,<br /> t, t’<br /> t’<br />  U nếu<br /> nếu [t]X = [t’]X =><br /> [t]XY = [t’]XY => [t]X[t]Y = [t’]X[t’]Y => [t]Y = [t’]Y = > S X→Y<br /> Trong đđịnh<br /> ịnh nghĩa 12 ở tr ên chúng ta đã<br /> trên đã nêu định<br /> định nghĩa S thỏa m<br /> mãn<br /> ãn phụ àm X →<br /> phụ thuộc hhàm<br /> Y. Tuy nhiên trong rrất ất nhiều trtrư<br /> ường<br /> ờng hợp S không thỏa m mãn<br /> ãn phụ<br /> phụ thuộc hhàm<br /> àm<br /> X→Ym màà chỉ<br /> chỉ S’ con của S thoả mmãn<br /> ãn ph<br /> phụ hàm X → Y.<br /> ụ thuộc hàm<br /> Gọi<br /> ọi T = ((U<br /> UT, A) là hhệệ thông tin con cực đại (chứa nhiều bộ nhất) của S = (U, A) thỏa<br /> mãn X → Y. Nói cách khác T X→Y<br /> ịnh nghĩa 14. Cho hhệệ thông tin S = (U, A ); X, Y  A.<br /> Định<br /> ọi đđộ<br /> Chúng ta ggọi ộ chắc chắn của àm X → Y trong S llà<br /> ủa phụ thuộc hhàm<br /> UT<br /> c( X → Y) = . (4)<br /> |U|<br /> ằng 0  c( X → Y)  1 và nếu<br /> Rõ ràng rrằng nếu cc(( X → Y) = 1 th<br /> thìì S X → Y.<br /> ịnh lý 1. Cho hệ<br /> Định hệ thông tin S = (U, A ); X, Y  A. Khi đó ta có<br /> k(X → Y) = c(X → Y). (5)<br /> Chứng minh:<br /> Chứng<br /> Đểể chứng minh (2) ta sẽ tính UT. GiGiảả sử U/X = {[t]X: tU};<br /> t U}; U/Y={ [t]Y: t  U}.<br /> Dễễ thấy rằng nếu [t]X  [t]Y thì [t]X  UT. Như vvậyậy<br /> UT =  { [t]X: [t]X  [t]Y với<br /> ới [t]Y  U/Y } = POS(X, Y)<br /> Từừ đây suy ra c(X →Y)=card(UT)/card(U)=card(POS(X,Y))/card(U)=k(X→Y).<br /> (X→Y)=card(U )/card(U)=card(POS(X,Y))/card(U)=k(X→Y).<br /> ừ chứng minh của định lý 1 ta có thuật toán tính độ chắc chắn c(X → Y).<br /> Từ<br /> Thuật toán 1. Tính (( X → Y).<br /> Thuật<br /> Input H Hệệ thông tin S = (U, A) & X, Y  A.<br /> Output c( X → Y)<br /> Algorithm<br /> 1. UT: = ∅<br /> 2. Tính U/X, U/Y<br /> 3. For each t  U if [t]X  [t]Y then UT = UT [t]<br /> [t]X<br /> UT<br /> 4. c( X → Y): =<br /> |U|<br /> ịnh nghĩa 15. Cho hhệệ thông tin S = (U, A ); X, Y<br /> Định Y A. Cho ngư<br /> ngưỡng<br /> ỡng minc  [0, 1].<br /> Chúng ta nói ph àm X → Y ch<br /> phụụ thuộc hhàm chắc ếu c(X → Y) ≥ minc.<br /> ắc chắn trong S nnếu<br /> Bổ Nếu X → Y chắc chắn trong S th<br /> ổ đề 7. Nếu thìì XZ → YZ ch<br /> chắc<br /> ắc chắn trong S.<br /> Chứng minh:<br /> Chứng<br /> Theo bổ<br /> bổ đề 3 ta có POS(X,Y)  POS(XZ, YZ) và theo đđịnh ịnh lý 1 ta có c(XZ → YZ) =<br /> card(POS(XZ, YZ))/Card(U) ≥ card(POS(X, Y))/card(U) = c(X → Y) ≥ minc => XZ →<br /> YZ ch<br /> chắc<br /> ắc chắn trong S đpcm.<br /> 3. RÚT G<br /> GỌN<br /> ỌN THUỘC TÍNH TRONG BẢNG QUYẾT ĐỊNH SỬ DỤNG ĐỘ PHỤ THUỘC<br /> Trong phần<br /> Trong phần này,<br /> này, chúng tôi xây ddựng<br /> ựng ph<br /> phương<br /> ương pháp rút ggọnọn thuộc tính sử dụng độ phụ<br /> thuộc<br /> thu ộc từ Định nghĩa 14. Ph ương pháp bao ggồm<br /> Phương ồm các bước:<br /> b ớc: định nghĩa tập rút gọn dựa tr trên<br /> ên<br /> độộ phụ thuộc, độ quan trọng của thuộc tính dựa tr trên<br /> ên đ<br /> độộ phụ thuộc vvàà đề<br /> đề xuất thuật toán<br /> heuris<br /> heuristic<br /> tic tìm ttập<br /> ập rút gọn dựa trtrên<br /> ên độ<br /> độ quan trọng của thuộc tính.<br /> ịnh nghĩa 16. [2] Cho hhệệ quyết định T = (U, C<br /> Định C D ), đđộ<br /> ộ phụ thuộc của tập thuộc<br /> tính quyết<br /> quyết định D vvào ào ttập<br /> ập thuộc tính điều kiện C đđư<br /> ược<br /> ợc định nghĩa<br /> <br /> <br /> Tạp<br /> ạp chí Nghi<br /> Nghiên<br /> ên cứu<br /> cứu KH&CN quân<br /> uân sự,<br /> sự, Số 60, 4 - 2019<br /> 20 167<br />  Công nghệ thông tin & Cơ sở toán học cho tin học<br /> <br /> POS  C , D <br />  C D <br /> U<br /> Theo Định nghĩa 14, dễ thấy rằng  C  D   k  C  D   c  C  D <br /> Định nghĩa 17. Cho hệ quyết định T  U , C  D  , tập thuộc tính R  C được gọi là<br /> tập rút gọn của C nếu thỏa mãn<br /> 1)  R  D    C  D <br /> 2) r  R ,  R r  D    C  D <br /> Dễ thấy rằng, tập rút gọn bởi Định nghĩa 17 tương đương với tập rút gọn miền dương<br /> bởi Định nghĩa 14.<br /> Định nghĩa 18. Cho bảng quyết định T  U , C  D  với B  C và b  C  B . Độ<br /> quan trọng của thuộc tính b đối với B được định nghĩa bởi<br /> SIGB  b    Bb  D    B  D <br /> Dễ thấy rằng SIGB  b   0 . Độ quan trọng SIGB  b  đặc trưng cho chất lượng phân<br /> lớp của thuộc tính b đối với tập thuộc tính quyết định D và được sử dụng làm tiêu chuẩn<br /> lựa chọn thuộc tính cho thuật toán heuristic tìm tập rút gọn.<br /> Phần tiếp theo, chúng tôi trình bày thuật toán heuristic tìm một tập rút gọn. Ý tưởng<br /> của thuật toán là xuất phát từ tập rỗng R :  , lần lượt bổ sung vào R các thuộc tính có<br /> độ quan trọng lớn nhất cho đến khi tìm được tập rút gọn.<br /> Thuật toán ADAR (Attribute Dependency based Attribute Reduction). Thuật toán<br /> heuristic tìm một tập rút gọn sử dụng độ phụ thuộc.<br /> Đầu vào: Bảng quyết định T  U , C  D <br /> Đầu ra: Một tập rút gọn R .<br /> 1. R :  ;<br /> // Thêm dần vào R các thuộc tính có độ quan trọng lớn nhất<br /> 2. While  R  D    C  D  do<br /> 3. Begin<br /> 4. Với mỗi a  C  R tính SIG R  a    R a  D    R  D  ;<br /> <br /> 5. Chọn a m  C  R sao cho SIG R  a m   Max SIG R  a  ;<br /> aC  R<br /> <br /> 6. R : R  am  ;<br /> 7. End;<br /> // Loại bỏ các thuộc tính dư thừa trong R nếu có<br /> 8. Với mỗi a  R<br /> 9. Begin<br /> 10. Tính  R a  D  ;<br /> <br /> 11. If  Ra  D   C  D then R : R  a ;<br /> 12. End;<br /> 13. Return R;<br /> <br /> <br /> 168 N. B. Tường, N. B. Quảng, “Một số vấn đề về phụ thuộc hàm … rút gọn thuộc tính.”<br /> Nghiên cứu khoa học công nghệ<br /> <br /> Giả sử D  d  , dễ thấy độ phức tạp thời gian của thuật toán ADAR là O C U  2 2<br /> <br /> với C là số thuộc tính điều kiện, U là số đối tượng.<br /> <br /> 4. KẾT LUẬN<br /> Chúng tôi đã giới thiệu một số nghiên cứu, tính chất đặc biệt, hữu ích, có tính hệ thống,<br /> cơ bản của các khái niệm liên quan đến hệ thông tin S =(U, A), phụ thuộc hàm, phụ thuộc<br /> hàm xấp xỉ, độ chắc chắn của phụ thuộc hàm dựa trên nền lý thuyết tập thô. Đặc biệt trong<br /> bài viết chúng tôi đã tự nêu và chứng minh chặt chẽ một định lý, 7 bổ đề và 7 tính chất của<br /> khái niệm phụ thuộc hàm trong hệ thông tin. Trong bài viết chúng tôi cũng đã nêu một thuật<br /> toán tìm độ chắc chắn của phụ thuộc hàm. Chúng tôi nghiên cứu về vùng dương, ràng buộc<br /> của các tập thuộc tính trong hệ tin, hệ quyết định, trên cơ sở đó xây dựng một thuật toán<br /> heuristic tìm tập rút gọn của bảng quyết định sử dụng độ phụ thuộc của thuộc tính.<br /> TÀI LIỆU THAM KHẢO<br /> [1] Chen, D., Cui, D., Wang, C., Wang, Z. "A Rough Set-Based Hierarchical clustering<br /> Algorithm for categorical Data". International Journal of Information Technology,<br /> Vol. 12, No.3, 2006, pp 149-159.<br /> [2] Han, J., Hu,X., Lin, T.Y. "Feature Subset Selection Based on Relative Dependency<br /> between Attributes". Rough Sets and Current Trends in Computing 2004, pp 176-185.<br /> [3] Yan-Yong Guan, Hong-Kai Wang. "Set-value information systems". Information<br /> Science, vol 176, 2006, pp 2507-2525.<br /> [4] Z. Pawlak (1991). "Rough sets: theoretical aspect of reasoning about data".<br /> [5] Nguyễn Bá Tường. "Cơ sở dữ liệu quan hệ và ứng dụng". Nhà xuất bản Thông Tin và<br /> Truyền Thông, 2011.<br /> ABSTRACT<br /> FUNCTIONAL DEPENDENCIES AND APPROXIMATE FUNCTIONAL<br /> DEPENDENCIES IN ROUGH SETS THEORY AND APPLICATION IN<br /> ATTRIBUTE REDUCTION PROBLEM.<br /> In this paper, we present some concepts and properties related to the S = (U, A)<br /> information system, dependence, approximation, positive region in the set theory.<br /> On this basis, the basis for further study of the properties of the positive region, the<br /> constraints between attributes and, in particular, between the conditional properties<br /> in the decision system are the premise of the algorithms. Finally, we propose a<br /> dependency based attribute reduction algorithm in decision tables.<br /> Keywords: Partition; Relation; Approximation; Rough sets; Functional dependency; Dependency<br /> approximation; Reduct.<br /> <br /> Nhận bài ngày 30 tháng 11năm 2018<br /> Hoàn thiện ngày 24 tháng 3 năm 2019<br /> Chấp nhận đăng ngày 16 tháng 4 năm 2019<br /> <br /> Địa chỉ: 1 Đại học SP kỹ thuật Hưng Yên;<br /> 2<br /> Đại học Kiến trúc Hà Nội.<br /> *<br /> Email: quangnb1@gmail.com.<br /> <br /> <br /> <br /> <br /> Tạp chí Nghiên cứu KH&CN quân sự, Số 60, 4 - 2019 169<br />