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ạ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.