Một thuật toán tìm tập rút gọn trong báng quyết định không đây đủ

MỘT THUẬT TOÁN TÌM TẬP RÚT GỌN
TRONG BÁNG QUYẾT ĐỊNH KHÔNG ĐÂY ĐỦ
HOÀNG THỊ LAN GIAO
Khoa CNTT, Trường Đại học Khoa học- Đại học Huế
Abstract. The aim of this work is to generalize the concept of knowledge reduction to class of incomplete decision tables. By innovating the method of J. Liang and z. Xu [3], which based on rough entropy, we establish a heuristic algorithm for finding a reduct of incomplete decision table. The time complexity of this algorithm is o(kn? log n), where k is the number of conditional attributes and n is the number of objects in data table.
Tóm tắt. Bài báo mở rộng khái niệm rút gọn tri thức lên lớp các bảng quyết định không đầy đủ. Bang cách cải tiến phương pháp của Jiye Liang và Zongben Xu [3], dựa vào entropy thô đã thiết lập một thuật tóan Heuristic để tìm rút gọn của bảng quyết định không đầy đủ. Độ phức tạp của thuật toán này là o^kn2 logn), với k là số thuộc tính điều kiện và n là số đối tượng trong bảng.
MỞ ĐẦU
Đối với các mô hình dữ liệu lớn, rất dl xãy ra tình trạng dữ liệu bị thiếu bởi nhiều lý do khác nhau. Việc rút gọn tri thức sẽ gặp khó khăn trong các hệ thống thông tin không đầy đủ nói chung và đặc biệt trong bảng quyết định, các luật quyết định đưa ra sẽ không đầy đủ. Thông thường, dữ liệu thiếu thông tin rơi vào một trong ba trường hợp [9]: không có thông tin về dữ liệu (không biết một người nào đó có số điện thoại hay không), không tồn tại (không có chức vụ), tồn tại nhưng không biết (ngày sinh). Trong khuôn khổ bài báo, ta chỉ nghiên cứu bảng quyết định không đầy đủ với giá trị thuộc tính bị mất do tồn tại nhưng không biết. Một thuật toán tìm tập rút gọn dựa vào khái niêm entropy thô với bảng chứa dữ liệu bị thiếu loại này cũng đã được đề xuất.
CÁC KHÁI NIỆM
2.1. Hệ thống thông tin không đầy đú
Cho A = (u, A) là một hệ thống thông tin với u là tập hữu hạn, khác rỗng các đối tượng và A là tập hữu hạn, khác rỗng các thuộc tính. Với mỗi u G u và a G A ta, ký hiệu u(a) là giá trị thuộc tính a của đối tượng u. Nếu X c A là, một tập các thuộc tính ta, ký hiệu u(x) là bộ gồm các giá, trị u(a) với a G X. Vì vậy, nếu u và V là hai đối tượng thuộc u, ta, sẽ nói u(x) = v(x) nếu u(a) = v(a) với mọi thuộc tính a G X. Tập tất cả, các giá, trị của, thuộc tính a là Va.
Bảng quyết định là một hệ thống thông tin với tập thuộc tính A gồm hai tập con rời nhau c và D, trong đó tập c được gọi là tập thuộc tính điều kiện và D là tập thuộc tính quyết định.
Hệ thống thông tin A được gọi là không đầy đủ nếu tồn tại thuộc tính a G A và, đối tương u G u mà giá trị ư(a) bị mất hay nói cách khác Va chứa giá trị null. Giá trị này trong bảng chúng ta sẽ ký hiệu bởi ký tự .
Tương tự như vậy, ta có khái niệm bảng quyết định không đầy đủ.
2.2. Quan hệ không phân biệt được trên hệ thống thông tin không đầy đú
Cho hệ thống thông tin A = (u, A). Với mỗi tập con các thuộc tính B c A, ta định nghĩa quan hệ hai ngôi IND(B) trên u xác định bởi:
IND(B) = {(«, v)eư xư I u(B) = v(B)}.
IND(B) được gọi là quan hệ B— không phân biệt được. Dl kiểm chứng được rằng đây là một quan hệ tương đương trên u.
Nếu (u, v) G IND(B) thì hai đối tượng u và V không phân biệt được bởi các thuộc tính trong B. Lớp tương đương chứa phần tử u được ký hiệu [ư]p. Khi đó quan hệ IND(B) được xác định hoàn toàn bởi các lớp tương đương [u]b, u E u. Tập hợp thương của quan hệ IND(B) được ký hiệu U/B, tức là U/B = {[u]b I u E V}.
Trong trường hợp hệ thống không đầy đủ, ta định nghĩa quan hệ hai ngôi trên u, ký hiệu SIM(B), với mỗi B c A.
Định nghĩa 2.1. [3]
SIM(B) = {(«, v) E u X u I Va G B, ư(a) = v(a) hoặc ư(a) = * hoặc v(a) = *}.
Rõ ràng,
SIM(B) = Pl SIM({Ỉ>}).
feeB
Ký hiệu Sb(u) = {/’ G u I (ư, v) E SIM(B)} và gọi là lớp tolerance của quan hệ SIM(B), Sb(Ù) là tập tối đa các đối tượng V không phân biệt được với u bằng tập thuộc tính B. Khi đó trên u ta phân lớp các đối tượng dựa vào quan hệ SIM(B), mỗi lớp là một tập Sb(Ù), u E u. Họ các lớp này được ký hiệu B/SIM(B), đây là một phủ của u (UueB^(u) = ^)’ V;l mỗi phần tử trong họ này đều khác rỗng do quan hệ SIM(B) có tính phản xạ (>Sb(u) D {"})■ Nói chung, đây không phải là một phân hoạch của u và SIM(B) cũng không phải là một quan hệ tương đương. Tuy nhiên, trong trường hợp hệ thống đầy đủ, quan hệ SIM(B) trùng với quan hệ IND(B), và khi đó Sb(u) = [u]b, Vư G u hay B/SIM(B) = U/B.
Ví dụ 2.1. Xét hệ thống thông tin không đầy đủ với ba thuộc tính: A ={Thân nhiệt, Đau đầu, Đau cơ} cho trong Bảng 1.
Bảng 1
u
Thân nhiệt
Đau đầu
Đau cơ
1
cao
*
không
2
rất cao
có
có
3
*
không
không
4
cao
có
có
5
cao
*
có
6
bình thường
có
không
7
bình thường
không
có
8
*
có
*
Ta có:
SA(1) = {1,3,8}; SA(2) = {2,8};
Sa(3) = {1,3};Sa(4) = {4,5,8};
Sa(5) = {4, 5, 8}; SA(6) = {6, 8};
SA(T) = {7}; Sa(8) = {1, 2,4, 5,6, 8}.
Ỉ7/SIM(A) = {{1, 8}; {2, 8}; {1, 3}; {4, 5, 8}; {4, 5, 8}; {6, 8}; {7, 8}; {1, 2,4, 5, 6, 8}}.
Với B = { Thân nhiệt, Đau cơ}.
Sb(1) = {1, 3, 8}; >Sb(2) = {2,8};
S*b(3) = {1, 3, 6, 8}; Sb(4) = {4, 5, 8};
Sb(5) = {4, 5, 8}; Sb(6) = {3, 6, 8};
Sb(7) = {7, 8}; Sb(8) = {1, 2, 3,4, 5, 6, 7, 8}.
Định nghĩa 2.2. Thuộc tính điều kiện c G c được gọi là không cốt yếu trong bảng quyết định T nếu [7/SIM(ơ \ {c}) = [7/SIM(ơ \ {c} u D). Ngược lại, c được gọi là cốt yếu.
Bảng quyết định không đầy đủ T được gọi là độc lập nếu mọi thuộc tính c G c đều cốt yếu. Tập tất cả các thuộc tính cốt yếu trong T được gọi là lõi và được ký hiệu Core(C'). Từ đây, ta quy ước viết Core thay cho Core(C').
Định nghĩa 2.3. Tập các thuộc tính R C 6' được gọi là một rút gọn của tập thuộc tính điều kiẹn c nếu T' = (U, R u 2?) là độc lập và V/SIM(E) = V/SIM(E u DỴ
Rõ ràng là có thể có nhiều tập rút gọn của c. Ta ký hiệu RED(C') là tập tất cả các rút gọn của c trong T. Một thuộc tính là cốt yếu khi và chỉ khi nó thuộc vào mọi tập rút gọn của c.
Hai định nghĩa trên là sự mở rộng của các định nghĩa về thuộc tính không cốt yếu và rút gọn trong bảng quyết định (đầy đủ). Rõ ràng khi T đầy đủ, ta có
U/SIM(C \ {c}) = U/SIM((C \ {c}) u D)
U/(C\{c}) = U/((C\{c})UD)
Card(ỊỊ(Ơ \ {c})) = Card(ỊỊ(Ơ \ {c})UP)
c là thuộc tính không cốt yếu (theo [2]).
ENTROPY THÔ
Khái niệm entropy thô đã được giới thiệu trong [1, 6], ở đây, ta nhắc lại khái niệm entropy thô của tri thức trong hệ thống không đầy đủ do Jiye Liang và Zongben Xu đề xuất.
Định nghĩa 3.1. Cho hệ thống thông tin không đầy đủ A = (u, A) vàB c A. Entropy thô của tri thức B là giá trị
£<B) A "
với Card(B) = n, |Sb(o;) I là ký hiệu của Card (Sb (re)) và logic là ký hiệu của log2ír. Khi đó ———— là xác suất để một đối tượng trong u thuộc lớp Sb(xA và	—-T là xác suất của
n	'	|Sb(ía)|
một đối tượng trong lớp Sb(xì) và bằng Xị.
Từ định nghĩa trên, ta có các tính chất của entropy thô trong hệ thống thông tin không đầy đủ A = (u, A) [3].
Tính chất 3.1. Cho P,Q c A. Nếu tồn tại một song ánh h : B/SIM(P) B/SIM(Q) sao cho
|A(5pk))| = \Sp(xi))\,i = 1,2, ••• ,\u\,
thì
E(P) = E(Q).
Điều này có nghĩa là entropy thô của tri thức là bất biến đối với tập các lớp B/SIM(P) đẳng cấu.
Tính chất 3.2. (Đơn điệu giảm) Cho B,c c A. Nếu B C c (rõ ràng khi đó U/SĨM(C) C B/SIM(B)) thì E(ơ) < E(BỴ
Tính chất này chỉ ra rằng số lớp tolerance trong B/SIM(B) càng lớn thì entropy thô của tri thức càng giảm.
Tính chất 3.4. (Tương đương) Cho c c A. Khi đó B/SIM(Ơ) = B/SIM(A) nếu và chỉ nếu E(c) = E(Ã).
Như vậy, nếu tập c c A thì sự phân lớp của quan hệ SIM(Ơ) tương đương với sự phân lớp của quan hệ SIM(A) khi và chỉ khi entropy của hai tập thuộc tính này bằng nhau.
Tính chất 3.5. (Cực đại) Cho c c A. Giá trị cục đại của entropy thô của tri thức c bằng Ip|log|u\, đạt đuợc khi Sc(x) = u\/x G u. Lúc đó B/SIM(Ơ) = {p}.
Entropy đạt cực đại khi mọi lớp của B/SIM(Ơ) đều bằng u. Điều đó cũng có nghĩa là thông tin nhận được từ tập thuộc tính tương ứng có độ tin cậy bé nhất.
Tính chất 3.5. (Cực tiểu) Cho c c A. Giá trị cục tiểu của entropy thô của tri thức c bằng 0, đạt được khi Sc(x) = {:/•}¥:/• G u.
Entropy đạt cực tiểu khi mỗi lớp tolerance chỉ chứa đúng một phần tử và như vậy thông tin nhận được dựa vào tập thuộc tính tương ứng chắc chắn nhất.
Mệnh đề 3.1. Cho T = ([7, c u D) là bảng quyết (Lịnh không đầy (Lủ. Khi ãó, tâp R C 6' là một rút gọn của tập thuộc tính điều kiện c trong bảng nếu và chỉ nếu R là tập tối tiểu thoả mãn E(R) = E(R u D).
Chứng minh. Đặt T' = (U,Ru D).
R là tập rút gọn
o T'độc lập vằU/SIM(JĨ) = U/SIM(R u n)
o Vc G R, U/SIM(R \ {c}) ỹỂ U/SIM(R \ {c} u D) và U/SIM(R) = U/SIM(RCD)
o R là tập tối tiểu và E(R) = E(RUD)
( theo tính chất tương đương)
Ý NGHĨA CỦA THUỘC TÍNH
Định nghĩa 4.1. Cho T = (u, c u D) là bảng quyết định không đầy đủ. Y nghĩa của thuộc tính c trong c, ký hiệu sigCỴ|cT.(c), được xác định
^ổơ\{c}(e) = E(C \ {c}) - E(c \ {c} u p).
Mệnh đề 4.1.
0 < sigc\{c}(c) < |u|log|u|.
c G c là thuộc tính cốt yếu trong c nếu và chỉ nếu sigCỴ|cT.(c) > 0. Khi đó,
Core(C') = {c G c I sigGỴ{c}(c) > 0}.
Chứng minh.
0 < E(c \ {c}) — E(c \ {c} u p) vì 6' \ {c} c c \ {c} u D. Mặt khác, theo tính chất
cực tiểu E(c \ {c} u D) 0 và tính chất cực đại thì E(c \ {c}) Iu\logIu\. Ta có \u\log\u\> E(C\{c})	E(C\{c}) - E(C\{c}CD) > 0 hay 0 < siỡc\{c}(C) < |u|log|u|.
c G c là thuộc tính cốt yếu trong c nếu và chỉ nếu U/SIM(C'\{c}) ỹỂ U/SIM(C\{c}UP).
Tức là, E(C \ {c}) — E(C \ {c} u D) > 0 hay sigCỴ|cT.(c) > 0. Rõ ràng, khi đó Core(C) = {c G c I sigGỴ{c}(c) > 0}.	■
Định nghĩa 4. 2. Cho T = (U, CCD) là bảng quyết định không đầy đủ, R C c và c G C\R. Y nghĩa của thuộc tính c đối với R, ký hiệu sig^(c), được xác định
sigR^c) = E(R UP) — E(R u {c} u D).
THUẬT TOÁN TÌM TẬP RÚT GỌN
Dựa vào các tính chất của entropy thô và ý nghĩa của một thuộc tính, bài báo đề xuất một thuật toán Heuristic tìm tập rút gọn trong bảng quyết định không đầy đủ. Thuật toán này xuất phát từ tập lõi (bởi vì mọi tập rút gọn đều chứa tập lõi) và tìm cách bổ sung các thuộc tính cho đến khi nhận được tập rút gọn thực sự. Thuộc tính được ưu tiên chọn bổ sung tại mỗi bước là thuộc tính có ý nghĩa lớn nhất. Cụ thể, thuật toán có thể được trình bày chi tiết như sau.
Vào. Bảng quyết định không đầy đủ T = ([7, c u D).
Ra: Một rút gọn R của T.
Phương pháp
Bl. Tính Core(C') := {c G c I sigCỴ|cT.(c) > 0}
B2. R := Core(C')
B3. Tính E(R) và E(RUD)
B4. While E(R) ỹỂ E(RUD) do
For c G c \ R do
Tính sig^(c)
Chọn c sao cho sig^(c) = max{sigR(c') I c’ G c \ R}
R := R u {c}
Tính E(R),E(RUD)
B5. R := 7? \ Core(C')
B6. For c G R do
If E((R \ {c}) u Core(C')) = E((R \ {c}) u Core(C') u D) then
R := R \ {c}
B7. R := EUCore(C')
Độ phức tạp tính toán của thuật toán này được xác định bởi vòng lặp while ở B4. (vòng lặp này thực hiện tối đa Card(C') lần, do sau mỗi bước, số thuộc tính được chọn tăng lên 1). Tại mỗi bước của vòng lặp, ta cần tính sig^(c), với mỗi c G c \ R và, tính E(R), E(RU D). Việc tính sig^(c) cũng đưa về tính entropy thô. Vì vậy, nếu gọi n là số đối tượng trong bảng quyết định và k là số thuộc tính điều kiện tương ứng, thì tại mỗi bước của vòng lặp ta cần tính tối đa k giá trị entropy thô. Mặt khác, dựa vào công thức của entropy thô, ta đánh giá được độ phức tập tính toán của phép toán này là O(n2logn), vì mỗi lần tìm một lớp Ỉ7/SIM(B), ta phải sắp xếp các đối tượng trong u với độ phức tạp của phép sắp xếp là O(nlogn). Như vậy có thể khẳng định độ phức tạp tính toán của thuật toán là O(fen2logn).
Ví dụ 5.1. Xét bảng quyết định trong [11] được cho bởi Bảng 2.
Bảng 2
u
C1
C2
C3
c4
d
U}
low
2
compact
4
high
u2
low
4
sub
6
low
u3
medium
4
compact
4
high
Uị
high
2
compact
6
low
u5
high
4
compact
4
low
Uq
low
4
compact
4
high
Uỵ
high
4
sub
6
low
u8
low
2
sub
6
low
Bảng 2 lưu thông tin về 8 chiếc xe hơi nhận được thông qua các thuộc tính điều kiện c = {cỵ(weight), c2(Door), c3(Size), ci(Cylinder)} và thuộc tính quyết định D = {d(Mileage)}.Trong bảng này, ta có tập thuộc tính lõi là {ci} và có hai tập rút gọn Rỵ = {ci, C3}, R2 = {ci, c4}.
Giả sử vì một lý do nào đó ta không có được thông tin đầy đủ như trên, một số giá trị của các thuộc tính bị mất (Bảng 3)
Bảng 3
u
C1
C2
C3
c4
d
U}
low
2
compact
4
high
u2
*
4
sub
6
low
u3
medium
4
compact
4
high
U4
high
2
compact
*
low
u5
high
4
*
4
low
Uq
low
4
compact
4
high
Uỵ
high
*
sub
6
low
u8
low
2
sub
6
low
Thực hiện từng bước thuật toán trên ta thu được kết quả sau:
Bl. Tìm lõi:
Xét C1
ScMciỊơt) =
{«1, T|}:
Sc\{ci}(u2) =
{U2, w};
SC\{C1}(U3) =
{U3,U5,U6};
Sc\{ci}(u4) =
{«1, Ỉ(|Ị:
SC\{C1}(U5) =
{U3,U5,U6};
Sc\{ci}(u6) =
{U3,U5,U6};
Sc\{ci}(u7) =
{u2, u7, u8};
Sc\{ci}(us) =
{u7, Us}-
SíCUDỴxiciịiui) =
{^1},
S(CUD)\{C1}(U2) =
{U2, u7},
SíCUDỴxiciịius) =
{u3,u6},
S^CUD^Ri}^) =
{"l}-
SíCUDỴxiciịius) =
{ư5,ư6},
^(GUDJXtcjiw) =
{U3,U6},
l‘’(C'U.D)\{c1}(w) =
{u2, u7, u8},
l‘’(C'U.D)\{c1}(w) =
{u7, Us}.
Sigc\{ci}^) = E(c \ {C1}) - E((c \ {C1}) u D)
= >3 - ĩ > «■
Do đó C1 là thuộc tính cốt yếu.
Xét C2
Sc\{c2}(ui) =
{ui,u6};
S(CUDỴ\{c2}(ui) =
{ui,u6},
SC\{c2}(u2) =
{u2, u7, u8};
S(CUD)\{c2}(u2) =
{u2, u7, u8},
SC\{c2}(us) =
{"3}:
S(CUD)\{c2}(u3) =
{^3},
SC\{c2}(u4) =
{u4 ,u5}-
S(C'UD)\{c2}(u4) =
{U4 ,u5},
-ScVca}^) =
{ư4,ư5};
‘S'(C'U.D)\{C2}('U'5) =
{ư4,ư5},
{ưi,ư6};
S(CUD)\{c2}(uô) =
{ưi,ư6},
-S’c'Xicajiw) =
{ư2,ư7};
S(CUD)\{c2}(U7) =
{U2, u7},
SC\{c2}(us) =
{ư2,ư8};
S(gJUD)\{c2}tu8) =
{u2,u8}.
SigC\{cẠc2) = E(c \ {c2}) - E((c \ {c2}) u D) = 0.
Do đó c2 không phải là thuộc tính cốt yếu, tương tự, C3 vàc4 cũng không phải là thuộc tính cốt yếu. Hay nói cách khác Core = {ci}.
Đặt R := {d}.
Tính E(R) và E(RU D).
Sr(ui) =
{ưi, u2, u6, ư8};
Srud(ui) =
{ưi,ư6},
Sr(u2) =
{ // , u2ì u3ì ư4, //5. Uỹ, u7ì a8 |:
Srud(u2Ì =
{u2, u4, U5, u7, ư8},
Sr(u3) =
{U2,U3}-,
SrudÍUs) =
{^3},
Sr(u4) =
{u2, u4, U5, //7}:
SrudÍie) =
{u2, u4, U5, //7}.
Sr(u5) =
{u2, u4, U5, //7}:
SrudÍus) =
{u2, u4, U5, u7},
Sr(uq) =
{«1, Uq, u8}-
SrudÍUg) =
{ưi,ư6},
Sr(ut) =
{u2, u4, U5, //7}:
SrudÍuĩ) =
{u2, U4U3,7/7}.
Sr(u8) =
{ưi, u2, u6, ư8};
Srud(us) =
{ư2,ư8}.
B4. Ta có, E(R) ỹỂ E(R u DỴ Vì vậy chúng ta sẽ kiểm tra xem trong ba thuộc tính còn lại thuộc tính nào có ý nghĩa hơn đối với R để chọn bổ sung vào R.
Trước hết ta xét SigR(c2) = E(R u D) — E(R u {c2} u D).
Sru{c2}ud(ui) =
{^1},
Sru{c2}Ud(u2) =
{ư2,ư5,ư7},
Sru{c2}ud(us) =
*-\RU{c2}U.d(V4)
{ư4, //7}.
Sru{c2}Ud(u5) =
{ư2,ư5,ư7},
Sru{c2}ud(uô) =
{w},
Sru{c2}Ud(u7) =
{u2, u4, U5, ư7},
*-\RU{c2}U.d(V8)
{ư8}.
Sign(c2) = -((3 X 4 X ln4 + 3 X 2 X ln2 + 5 X ln5) - (2 X 3 X ln3 + 4 X ln4 + 2ln2)). 8
Tương tự ta có
SigR(c3) = |((3 X 4 X ln4 + 3 X 2 X ln2 + 5 X ln5) - (3 X ln3 + 2 X 4 X ln4 + 4 X 2 X ln2)), 8
Szỡ_r(c4) = -((3 X 4 X ln4 + 3 X 2 X 1112 + 5 X 1115) — (3 X 1113 + 2 X 4 X 1114 + 4 X 2 X 1112)). 8
Như vậy sigRÍcv) lớn nhất và ta chọn C2 bổ sung vào R.
Bây giờ ta xét R = {ci, C2}, ta có E(R) ỹỂ E(RU DỴ Do đó lại tính tiếp SigR(cs) và SigR(c4).
Sru{c3}ud(ui) =	{"l}:
Sru{c3}ud(u3) =	{"3};
Sru{c3}Ud(u5) =	{112,115,117}',
Sru{c3}Ud(iE) =	{112,115,117}',
Sru{c3}Ud(u2) =	{112,115,117},
Sru{c3}udM =	{"1},
Sru{c3}Ud(u6) =	{w},
Sru{c3}ud(iis) =	{w}-
Sru{c4}ud(ui) =	{"1};
Sru{c4}Ud(u3') =	{^3};
Sru{c4}ud(u5') =	{^5};
Sru{c4}ud(uĩ) =	{ư2,^4,w};
Sru{c4}Ud(uz') =	{112,117},
Sru{c4}Ud(u4) =	{114,117},
Sru{c4}Ud(u6) =	{w},
SrìJ{c4}1J£>(w) =	{w}.
SigR(cs) = -((2 X 3 X ln3 + 4 X ln4 + 2 X ln2) - (3 X 3 X ln3)) 8
và
Szỡ_r(c4) = -((2 X 3xln3 + 4x ln4 + 2 X ln2) — (2 X 2 X ln2 + 3 X ln3)). 8
Nên ta chọn C4 vào R. Lúc này, với R = {ci, C2, C4} ta có E(R) = E(R u D).
B5 và B6. Theo trên ta có {ci, C2} không phải là tập rút gọn. Ta chỉ còn xét {ci, C4}.
-S'{ci,c4}('^l) =	{ui,ư6};
S{c4,c4}(u2) =	{112,114,117,113}',
S{ci,c4}(.us) =	{"3}:
‘5,{c1,c4}(u4) =	{"2- 114, 115, «7};
8{c4,c4} (^5)	{/f1,115}5
8{c4,c4}(w)	{tíi , Ug};
S{c4,c4}(u7) =	{112,114,117}',
S{ci,c4}(us) =	{u2,Us}',
S{c4,c4}ud(ir) =
S{c1,c4}Ud(u2) =	{lÍ2,U4,U7,Us},
8{c4,c4}Ud(u3) =	{113},
8{c1,c4}udM =	{112,114,115,117},
8{c1,c4}ud(u5') =	{"l-'/r,}.
8{c1,c4}ud(ii6) =
‘S,{c1,c4}U£>(w) =	{112,114,117},
S{c1,c4}Ud(i18) =	{112,113}-
Rõ ràng, L?({ci, C4}) = L?({ci, C4} u DỴ Vì C1 là thuộc tính cốt yếu và {ci} không phải là tập rút gọn. Vậy tập rút gọn đối với bảng quyết định không đầy đủ này là R = {ci, C4}.
TÀI LIỆU THAM KHẢO
T. Beaubouef, p. E. Petry, G. Arora, Information-theoretic measures of uncertainty for rought sets and rough relational databases, Information Sciences 109 (1998) 535-563.
Hoàng Thị Lan Giao, Một số thuật toán tìm tập rút gọn của bảng quyết định sử dụng các phép toán của đại số quan hệ, Tap chí Khoa hoc, Khoa hoc Tư nhiên và Công nghê, Đại học Quốc gia HàNội, 21 (2PT) (2005) 41-48.
Jiye Liang, Zongben Xu, The algorithm on knowledge reduction in incomplete information systems, International Journal of Uncertainty, Fizziness and Knowledge-Based Systems 10 (1) (2002) 93-103.
Jerzy w. Grzymala Busse, Data with missing Attribute Values: Generalization of Indis- cernibility Relation and Rule Induction, Vol. 1, Published in Transactions on Rough Sets, Springer - Verlag, 2004 (78-95).
z.Pawlak, Rough Sets - Theoretical Aspects of Reasoning about Data, Kluwer Academic Publishers, Dordrecht, 1991.
D.Slezak, Approximate reducts in decision table, Pro. of IPMU’96, Granada, July 1-5, 1996 (1159-1164).
J. Stefanowski and A. Tsoukias, Incomplete information tables and rough classification, Computational Intelligence 17 (2001) 545-566.
A. Skowron, c. Rauszer, The discernibility matrices and functions in information systems, Intelligent Decision Support, Handbook of Applications and Advances of the Rough Sets Theory, Kluwer, Dordrecht, 1992 (331-362).
Ho Thuần, Hoàng Thị Lan Giao, Mở rộng một số toán tử quan hệ lên cơ sở dữ liệu thiếu thông tin, Tạp chí Tin học và Diều khiển học 19 (4) (2003) 359-365.
Hồ Thuần, Hoàng Thị Lan Giao, Một thuật toán tìm tập rút gọn sử dụng ma trận phân biệt được, Chuyên san Các công trình nghiên cứu triển khai Viễn thông và CNTT (15) (tháng 12/2005) 83-87.
Nhận bài ngày 5 - 10 - 2008
Xiaohua Hu, Jianchao han, T. Y. Lin, “A new rough sets model based on database systems, Fundamenta Informaticae XX (2004) 1-18.