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ường

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