Một phương pháp xử lý giá trị thiếu và tìm tập rút gọn trên bảng quyết định không đầy đủ

trong đó: Un = , 
*
ijc∨ = {c
*⏐c∈cij}. 
Giao các *ijc∨ cho ta tập tất cả các rút gọn của ID. 
3. THUẬT TOÁN TÌM TẬP RÚT GỌN TRÊN BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ 
Dựa vào các định nghĩa được xây dựng ở trên, chúng tôi đề xuất một phương pháp tìm 
tập rút gọn cho bảng quyết định không đầy đủ với độ phức tạp thời gian đa thức. 
Thuật toán Timrutgon 
Input: Bảng quyết định không đầy đủ ID = (U, C∪D); 
Output: Một rút gọn P của C; 
Method: 
NGUYỄN THỊ LAN ANH 
42 
1. Begin 
2. Tính POSC(D); 
3. P:=∅; 
4. For với mỗi ai ∈C do 
5. Begin 
6. P:= P ∪ {ai}; 
7. Tính các tập đặc trưng KP(xi), xi∈ U; 
8. Tính các tập xấp xỉ dưới )(XP , X∈ U/D; 
9. Tính POSP(D); 
10. If POSP(D) = POSC(D) then break; 
11. End; 
12. For với mỗi a ∈P do 
13. If POSP\{a}(D) = POSC(D) then P:= P\{a}; 
14. End. 
Mệnh đề 3.1. Thuật toán trên là đúng đắn. 
! Chứng minh 
- Vì P = {ai ∈ C} nên P ⊆ C. Do đó, vòng lặp từ dòng 4 đến dòng 11 đảm bảo rằng 
luôn tồn tại P để POSP(D) = POSC(D). 
- Từ dòng 12, 13 suy ra P là cực tiểu. 
Vậy, P thu được là một rút gọn của C trên bảng quyết định ID (theo định nghĩa 2.2). 
Mệnh đề 3.2. Thuật toán trên có độ phức tạp là O(mn2), trong đó n là số phần tử của U, 
m là số thuộc tính điều kiện. 
! Chứng minh 
Độ phức tạp tính toán của việc tính POSC(D) (dòng 2) là O(n2). Vòng lặp FOR (dòng 4-
11) phải thực hiện tối đa m lần. Độ phức tạp của việc tính các tập đặc trưng KP(xi) 
(dòng 7) là O(n), tính các tập xấp xỉ dưới )(XP (dòng 8) và POSP(D) (dòng 9) là O(n). 
Độ phức tạp của vòng lặp FOR tiếp theo (dòng 12-13) là O(mn2). Do đó, thuật toán này 
có độ phức tạp tính toán là O(mn2). 
Trong thực tế, thông thường m<<n nên có thể bỏ qua m và do vậy độ phức tạp thời gian 
của thuật toán Timrutgon là O(n2). 
Ví dụ 3.1. Xét bảng quyết định ID = (U, C∪D) được cho ở bảng 3.1. 
MỘT PHƯƠNG PHÁP XỬ LÝ GIÁ TRỊ THIẾU VÀ TÌM TẬP RÚT GỌN 
43 
Bảng 3.1. Bảng dữ liệu hành khách 
U Nơi sinh Quốc tịch Nghề nghiệp Tôn giáo Nơi đến Quyết định 
1 HCM VN Kỹ sư Không HN Có 
2 Huế HK Doanh nhân Phật HCM Không 
3 HCM HK Tu sĩ Phật Huế Không 
4 * VN * * HN Không 
5 * HK Tu sĩ Thiên chúa HN Có 
6 HN HK Doanh nhân ? Huế Không 
Để đơn giản, kí hiệu: Nơi sinh= a1; Quốc tịch = a2; Nghề nghiệp = a3; Tôn giáo = a4; 
Nơi đến = a5. Chúng ta sẽ dùng thuật toán trên để tìm một rút gọn của C trên bảng này. 
• Các tập đặc trưng KC(u), u∈U: 
KC(1) = {1, 4} 
KC(2) = {2} 
KC(3) = {3} 
KC(4) = {1, 4} 
KC(5) = {5} 
KC(6) = {6} 
• U/D = {Xcó, XKhông}trong đó Xcó = {1, 5}, XKhông = {2, 3, 4, 6} 
{ }5)( =CóXC ; { }6,3,2)( =KhôngXC ; POSC(D) = {2, 3, 5, 6} 
• Đầu tiên, khởi tạo P = ∅. Chọn a1∈ C đưa vào trong P, ta có P = {a1}. Lúc đó, 
)( CóXP )( KhôngXP= ∅= ⇒ POSP(D) = ∅ ≠ POSC(D). 
Tương tự, đối với P = {a1, a2} và P = {a1, a2, a3}, ta cũng có được POSP(D) = ∅ ≠ 
POSC(D). Với P = {a1, a2, a3, a4}, POSP(D) = {2, 3, 5, 6}= POSC(D). Đến đây, thoát 
khỏi vòng lặp FOR. 
Với các thuộc tính a1, a2, a3, a4 trong P, lần lượt tính các { } 4...1),(\ =iDPOS iaP . Ta có: 
- { } )(1\ DPOS aP = {2, 3, 5, 6} )(DPOSC= ⇒ P:={a2, a3, a4}. 
- Tương tự, { } )(2\ DPOS aP = {2, 3, 5, 6}, { } )(3\ DPOS aP = {2, 3, 5}, { } )(4\ DPOS aP = {2, 
6}. Các giá trị này đều khác với POSC(D). 
Vậy P = {a2, a3, a4} là một rút gọn của C trên ID. 
4. TẬP ĐẶC TRƯNG MỞ RỘNG 
Cho bảng quyết định không đầy đủ ID = (U, C∪D). Gọi ε0 là hệ số nhiễu cho phép, 
ε0∈[0,1]. Giá trị này do người sử dụng quy định tùy thuộc vào yêu cầu về mức độ chính 
xác của hệ thống. Với mỗi xi bất kỳ thuộc U, gọi: 
- ki là số thuộc tính điều kiện mà giá trị của xi tương ứng tại các thuộc tính đó là 
thiếu, nghĩa là ki = card({a∈C ⎢(a(xi) = *) ∨ (a(xi) = ?)}). 
- 
C
ki
i =ε là hệ số nhiễu của xi. 
NGUYỄN THỊ LAN ANH 
44 
Định nghĩa 4.1. Cho bảng quyết định không đầy đủ ID = (U, C∪D). Tập hợp )(* iC xK 
xác định bởi: 
( ) ( ) ( ){ }00* )()(:)(\)()( εεεε >∧≤∧≠∈∃∈= jijiiCjiCiC xdxdDdxKxxKxK , 
trong đó [ ]∩
?)(*,)(
)(,)(
≠≠
=
ii xaxa
iiC xaaxK , được gọi là tập đặc trưng mở rộng của xi. 
Chúng ta có thể sử dụng )(* iC xK thay cho tập đặc trưng KC(xi) trong việc tính tập xấp xỉ, 
miền xác định và sinh luật quyết định trên bảng quyết định không đầy đủ nhằm nâng 
cao chất lựợng của tập luật thu được. 
Thật vậy, với hai đối tượng xi, xj bất kỳ trên U, có thể xảy ra trường hợp xj ∈KC(xi) 
nhưng ∃d∈D: d(xi) ≠ d(xj), nghĩa là đối tượng xj “tương tự” với đối tượng xi trên tập 
thuộc tính điều kiện nhưng chúng lại có giá trị quyết định khác nhau ; nói cách khác, 
bảng quyết định lúc này là không nhất quán. Một trong những nguyên nhân dẫn đến tình 
huống này là do các giá trị thiếu. Khi tỉ lệ các giá trị này quá lớn, mức độ chính xác 
trong việc đánh giá thông tin sẽ bị hạn chế, kết quả phân lớp có thể bị sai lệch. Chẳng 
hạn, đối với bảng quyết định được cho trong Bảng 1, đối tượng 1 hoàn toàn xác định 
trên tập thuộc tính điều kiện C, nhưng lại không thuộc vào miền xác định của D, lý do là 
vì 1 và 4 “tương tự nhau”, nhưng lại có giá trị quyết định khác nhau. Khi đó, xét các 
trường hợp sau: 
(i) εi > ε0: bản thân đối tượng xi có chứa quá nhiều giá trị thiếu so với mức độ chính 
xác cho phép. 
(ii) εi ≤ ε0 và εj ≤ ε0: cả hai đối tượng xi và xj đều “xác định”; do đó, sự không nhất 
quán xảy ra thường là do sai sót trong việc đưa ra quyết định của các chuyên gia 
hoặc trong quá trình thu thập dữ liệu. 
(iii) εi ≤ ε0 và εj > ε0 : xi xác định còn xj chứa quá nhiều giá trị thiếu. 
Các trường hợp (i) và (ii), POSC(D) không chứa xi và các đối tượng tương tự với nó trên 
tập thuộc tính C là điều phù hợp với thực tế. Đối với trường hợp (iii), nguyên nhân dẫn 
đến tình trạng không nhất quán trong bảng quyết định thường là do xj không thật sự 
“tương tự” với xi. Vì vậy, trong trường hợp này, chúng ta loại xj ra khỏi KC(xi) để thu 
được )(* iC xK và dùng nó trong giai đoạn sinh luật quyết định. 
Ví dụ 4.1. Xét bảng quyết định được cho trong Bảng 1. Bảng quyết định này không 
nhất quán vì tồn tại hai đối tượng 1 và 4 “tương tự” nhau trên tập thuộc tính điều kiện C 
nhưng có giá trị quyết định khác nhau. 
Chọn ε0 = 0.5. Ta có : 011 05
0
εε <===
C
k ; 044 6.05
3
εε >===
C
k 
⇒ Loại đối tượng 4 ra khỏi KC(1) , tập đặc trưng mở rộng )1(*CK = {1}. Lúc này, 
MỘT PHƯƠNG PHÁP XỬ LÝ GIÁ TRỊ THIẾU VÀ TÌM TẬP RÚT GỌN 
45 
{ }5,1 =CóX , { }6,3,2 =KhôngX ⇒ POSC(D) ={1, 2, 3, 5, 6}. 
5. KẾT LUẬN 
Dựa vào quan hệ đặc trưng, một mở rộng của quan hệ không phân biệt được trên hệ 
thống thông tin không đầy đủ, chúng tôi đã xây dựng các định nghĩa về miền xác định, 
ma trận và hàm phân biệt được trên bảng quyết định không đầy đủ, làm cơ sở cho việc 
tìm tất cả các tập rút gọn của bảng quyết định này. Tuy nhiên, độ phức tạp của việc tính 
tất cả các rút gọn cho một bảng quyết định là rất lớn (NP khó) và trong đa số trường 
hợp, chúng ta chỉ cần sử dụng một trong số các tập rút gọn này. Vì vậy, thuật toán tìm 
một tập rút gọn với độ phức tạp đa thức được chúng tôi xây dựng (mục 3) cũng có ý 
nghĩa thực tế nhất định. Ngoài ra, bài báo cũng đã đề xuất một phương pháp xử lý 
trường hợp không nhất quán của bảng quyết định không đầy đủ, sử dụng tập đặc trưng 
mở rộng thay cho tập đặc trưng, nhằm hạn chế mức độ thiếu chính xác khi xử lý các giá 
trị thiếu. Vì theo P.Allison [6] “cách tốt nhất để giải quyết bài toán dữ liệu thiếu là dữ 
liệu không bị thiếu” nên phương pháp được trình bày trên đây không thể tối ưu cho tất 
cả các hệ thống thiếu thông tin được, nhưng nói chung là thích hợp trong phần lớn các 
cơ sở dữ liệu thực tế. 
TÀI LIỆU THAM KHẢO 
[1] Grzymala-Busse J. W. (2003, November 19-22). Rough Set Strategies to Data with 
Missing Attribute Values. Proceedings of the Workshop on Foundations and New 
Directions in Data Mining, associated with the third IEEE International Conference 
on Data Mining. Melbourne, FL,USA, 56-63. 
[2] Grzymala-Busse J. W. (2004). Data with Missing Attribute Values: Generalization of 
Indiscernibility Relation and Rule Induction. Transactions on Rough Sets. Lecture 
Notes in Computer Science Journal Subline. Springer-Verlag. Vol.1, 78-95. 
[3] Grzymala-Busse J. W. (2004, November 1-4). Three Approaches to Missing Attribute 
Values-A Rough Set Perspective. Workshop on Foundations of Data Mining, 
associated with the fourth IEEE International Conference on DataMining. Brighton, 
UK. 
[4] Grzymala-Busse J. W., Siddhaye S. (2004, July 4-9). Rough Set Approaches to Rule 
Induction from Incomplete Data. Proceedings of the IPMU’2004, the 10th 
International Conference on Information Processing and Management of Uncertainty 
in Knowledge-Based Systems. Perugia, Italy, Vol.2, 923-930. 
[5] Pawlak Z. (1982). Rough Sets. International Journal of Computer and Information 
Sciences, Grammars.grlmc.com. 
[6] Rady E. A., El-Monsef M. M. E. Adb, El-Latif W. A. Adb (2007). A Modified Rough 
Set Approach to Incomplete Information Systems. Research Article. Journal of 
Applied Mathematics and Decision Sciences. Hindawi Pusblishing Corporation. 
[7] Skowron A. (2001). Rough Sets and Boolean Reasoning, Granular computing: an 
emerging paradigm, 95-124. 
[8] Skowron A., Zhong N. (2000). Rough Sets in KDD. Tutorial Notes. 
NGUYỄN THỊ LAN ANH 
46 
Title: A METHOD FOR DEALING WITH MISSING ATTRIBUTE VALUES AND 
FINDING REDUCTS IN INCOMPLETE DECISION TABLES 
Abstract: One of the approaches to deal with missing attribute values in incomplete 
information systems is extending the Indiscernibility relation to Characteristic relation. Based 
on this relation, in this paper, we construct some definitions which are used to illustrate the 
finding reduct in incomplete decision table algorithm. Besides, one method for expanding the 
characteristic sets to reduce the inexactitude of handling with missing attribute values is studied. 
ThS. NGUYỄN THỊ LAN ANH 
Khoa Tin học, Trường Đại học Sư phạm - Đại học Huế. 
Tel: (054) 3824004 - 0982.054139. E-mail: lananh257@gmail.com.