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.
7 trang |
Chia sẻ: dntpro1256 | Lượt xem: 693 | Lượt tải: 0
Bạn đang xem nội dung tài liệu 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 đủ, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Tạp chí Khoa học và Giáo dục, Trường Đại học Sư phạm Huế
ISSN 1859-1612, Số 01(13)/2010: tr. 40-46
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 ĐỦ
NGUYỄN THỊ LAN ANH
Trường Đại học Sư phạm - Đại học Huế
Tóm tắt: Một trong những phương pháp xử lý giá trị thiếu trên hệ thống
thông tin không đầy đủ là mở rộng quan hệ không phân biệt được thành quan
hệ đặc trưng. Dựa vào quan hệ đó, trong bài báo này chúng tôi xây dựng một
số định nghĩa, từ đó đề xuất một thuật toán đi tìm tập rút gọn cho bảng quyết
định không đầy đủ. Ngoài ra, một phương pháp mở rộng tập đặc trưng để
khắc phục mức độ thiếu chính xác trong việc xử lý giá trị thiếu cũng được
chúng tôi nghiên cứu.
1. MỞ ĐẦU
Trong thực tế, các cơ sở dữ liệu thường chứa các giá trị thuộc tính thiếu, đó là các giá trị
thuộc tính của đối tượng nào đó mà chúng ta không xác định được. Có hai loại giá trị
thuộc tính thiếu là: Bị mất (lost), được kí hiệu là “?” và Điều kiện không quan trọng (do
not care condition), kí hiệu là “*” [1], [3], [4]. Một hệ thống thông tin IS = (U, A) [5],
[8] (tương ứng bảng quyết định DT = (U, C∪D) [5], [8]) có chứa giá trị thuộc tính thiếu
được gọi là hệ thống thông tin (tương ứng bảng quyết định) không đầy đủ.
Để xử lý các hệ thống thông tin không đầy đủ, G. Busse đã mở rộng quan hệ không
phân biệt được [5], [7], [8] thành quan hệ đặc trưng [1], [2], [3]. Với bảng quyết định
không đầy đủ ID = (U, C∪D), B⊆C, quan hệ đặc trưng R(B) là một quan hệ hai ngôi
trên U được xác định R(B) = {(x, y)∈U x U ⎢y∈KB(x)}, trong đó,
[ ]∩
*)(?,)(,
)(,()(
≠≠∈
=
xaxaBa
B xaaxK , với a(x) là giá trị của đối tượng x tại thuộc tính a, gọi là tập
đặc trưng của x. KB(x) là tập hợp nhỏ nhất chứa các đối tượng “tương tự” với x dựa vào
các thuộc tính trong B. Kí hiệu U/R(B) là họ gồm tất cả các tập đặc trưng {KB(x), x∈U}
tạo thành một phủ của U.
R(B) là một mở rộng của quan hệ không phân biệt được IND(B) lên hệ thống thông tin
không đầy đủ. R(B) có tính phản xạ, nhưng nói chung là không có tính đối xứng và bắc cầu.
Trên ID = (U, C∪D), với quan hệ đặc trưng R(B), B ⊆ C, có ba cách khác nhau để xấp
xỉ cho một tập X⊆U : xấp xỉ đơn, xấp xỉ khái niệm, xấp xỉ tập con, trong đó, chỉ có xấp
xỉ khái niệm là thích hợp cho việc sinh luật quyết định [2].
Rút gọn bảng quyết định nhằm nâng cao hiệu quả của quá trình khai phá tri thức là một
bước quan trọng. Trong bài báo này, chúng tôi đề xuất các định nghĩa về ma trận và
hàm phân biệt được, miền xác định và tập rút gọn trên bảng quyết định không đầy đủ, từ
đó đề xuất một thuật toán đi tìm tập rút gọn cho bảng quyết định này trên cơ sở quan hệ
đặc trưng. Bên cạnh đó, để khắc phục tình trạng thiếu chính xác khi xử lý thông tin
MỘT PHƯƠNG PHÁP XỬ LÝ GIÁ TRỊ THIẾU VÀ TÌM TẬP RÚT GỌN
41
không đầy đủ theo quan hệ đặc trưng, làm cho bảng quyết định trở nên không nhất
quán, chúng tôi đề xuất một phương pháp mở rộng tập đặc trưng dựa vào mức độ thiếu
thông tin của từng đối tượng.
2. RÚT GỌN TRÊN BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ
Cho bảng quyết định không đầy đủ ID = (U, C∪D).
Định nghĩa 2.1. C-Miền khẳng định của D, kí hiệu là POSC(D), được xác định:
∪
DUX
C XCDPOS
/
)()(
∈
= ,
trong đó, )(XC là tập xấp xỉ dưới khái niệm của X theo quan hệ đặc trưng R(C).
Định nghĩa 2.2. R⊆ C được gọi là một rút gọn của C trên bảng quyết định ID (hay còn
gọi là rút gọn của ID) nếu và chỉ nếu:
POSR(D) = POSC(D) và ∀R’⊂R, POSR(D) ≠ POSC(D)
Rõ ràng, định nghĩa này vẫn thỏa mãn được các tính chất của tập rút gọn khi ID là đầy đủ.
Định nghĩa 2.3. Ma trận phân biệt được của ID, ký hiệu ( )
nnij
cIDM
×
=)( , Un = ,với cij
được xác định:
( ){ }
⎪⎩
⎪
⎨
⎧
=∈∀
≠∈∃≠∧≠∧≠∧≠∈
=
xdxD:dd
xdxdDdnxcxcxcxcxcCc
c
ji
jijiiji
ij
)()(,
)()(:,*))((*))((?)()()(
nÕu
Õu
λ
với i, j=1, 2 n; xi, xj thuộc C-miền khẳng định của D.
Rõ ràng, khi ID là bảng quyết định đầy đủ thì M(ID) chính là ma trận phân biệt được
của bảng quyết định đầy đủ.
Định nghĩa 2.4. Hàm phân biệt được fID của bảng quyết định ID là một hàm logic được
xác định:
},1,,,{ * njicccf ijijijID ≤≤≠∅≠∨∧= λ , 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.
Các file đính kèm theo tài liệu này:
- 19_289_nguyenthilananh_08_nguyen_thi_lan_anh_4599_2021136.pdf