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 đủ

MỘT PHƯƠNG PHÁP XỬ LÝ GIÁ TRỊ THIẾU<br /> VÀ TÌM TẬP RÚT GỌN TRÊN BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ<br /> NGUYỄN THỊ LAN ANH<br /> Trường Đại học Sư phạm - Đại học Huế<br /> Tóm tắt: Một trong những phương pháp xử lý giá trị thiếu trên hệ thống<br /> thông tin không đầy đủ là mở rộng quan hệ không phân biệt được thành quan<br /> 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<br /> 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<br /> định không đầy đủ. Ngoài ra, một phương pháp mở rộng tập đặc trưng để<br /> khắc phục mức độ thiếu chính xác trong việc xử lý giá trị thiếu cũng được<br /> chúng tôi nghiên cứu.<br /> <br /> 1. MỞ ĐẦU<br /> 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ị<br /> 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ị<br /> 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<br /> not care condition), kí hiệu là “*” [1], [3], [4]. Một hệ thống thông tin IS = (U, A) [5],<br /> [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<br /> được gọi là hệ thống thông tin (tương ứng bảng quyết định) không đầy đủ.<br /> Để xử lý các hệ thống thông tin không đầy đủ, G. Busse đã mở rộng quan hệ không<br /> 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<br /> không đầy đủ ID = (U, C∪D), B⊆C, quan hệ đặc trưng R(B) là một quan hệ hai ngôi<br /> trên U được xác định R(B) = {(x, y)∈U x U ⎢y∈KB(x)}, trong đó,<br /> K B ( x) =<br /> ∩ [(a, a( x)], 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<br /> a∈B,a ( x )≠?,a ( x )≠*<br /> <br /> đặ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<br /> 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}<br /> tạo thành một phủ của U.<br /> 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<br /> 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.<br /> 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<br /> 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<br /> xỉ khái niệm là thích hợp cho việc sinh luật quyết định [2].<br /> 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<br /> 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à<br /> 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ừ<br /> đó đề 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ệ<br /> đặ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<br /> Tạp chí Khoa học và Giáo dục, Trường Đại học Sư phạm Huế<br /> ISSN 1859-1612, Số 01(13)/2010: tr. 40-46<br /> <br /> MỘT PHƯƠNG PHÁP XỬ LÝ GIÁ TRỊ THIẾU VÀ TÌM TẬP RÚT GỌN…<br /> <br /> 41<br /> <br /> không đầy đủ theo quan hệ đặc trưng, làm cho bảng quyết định trở nên không nhất<br /> 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<br /> thông tin của từng đối tượng.<br /> 2. RÚT GỌN TRÊN BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ<br /> Cho bảng quyết định không đầy đủ ID = (U, C∪D).<br /> Định nghĩa 2.1. C-Miền khẳng định của D, kí hiệu là POSC(D), được xác định:<br /> <br /> POSC ( D) =<br /> <br /> ∪C( X ) ,<br /> <br /> X ∈U / D<br /> <br /> trong đó, C (X ) là tập xấp xỉ dưới khái niệm của X theo quan hệ đặc trưng R(C).<br /> Đị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<br /> gọi là rút gọn của ID) nếu và chỉ nếu:<br /> POSR(D) = POSC(D) và ∀R’⊂R, POSR(D) ≠ POSC(D)<br /> 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 đủ.<br /> <br /> ( )<br /> <br /> Định nghĩa 2.3. Ma trận phân biệt được của ID, ký hiệu M ( ID) = cij<br /> <br /> n× n<br /> <br /> , n = U ,với cij<br /> <br /> được xác định:<br /> <br /> {<br /> <br /> }<br /> <br /> ⎧⎪ c ∈ C c( xi ) ≠ c( x j ) ∧ (c( xi ) ≠ ? ) ∧ (c( xi ) ≠ *) ∧ (c( x j ) ≠ *) , nÕu ∃d ∈ D : d ( xi ) ≠ d ( x j )<br /> cij = ⎨<br /> ⎪⎩λ , nÕu ∀d ∈ D:d ( xi ) = d ( x j )<br /> <br /> với i, j=1, 2… n; xi, xj thuộc C-miền khẳng định của D.<br /> <br /> 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<br /> của bảng quyết định đầy đủ.<br /> Đị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<br /> xác định:<br /> <br /> f ID = ∧{∨cij* , cij ≠ ∅, cij ≠ λ ,1 ≤ i, j ≤ n} , trong đó: n = U , ∨ cij* = {c*⏐c∈cij}.<br /> Giao các ∨ cij* cho ta tập tất cả các rút gọn của ID.<br /> 3. THUẬT TOÁN TÌM TẬP RÚT GỌN TRÊN BẢNG QUYẾT ĐỊNH KHÔNG ĐẦY ĐỦ<br /> 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<br /> 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.<br /> Thuật toán Timrutgon<br /> Input: Bảng quyết định không đầy đủ ID = (U, C∪D);<br /> Output: Một rút gọn P của C;<br /> Method:<br /> <br /> 42<br /> <br /> NGUYỄN THỊ LAN ANH<br /> <br /> 1.<br /> <br /> Begin<br /> <br /> 2.<br /> <br /> Tính POSC(D);<br /> <br /> 3.<br /> <br /> P:=∅;<br /> <br /> 4.<br /> <br /> For với mỗi ai ∈C do<br /> <br /> 5.<br /> <br /> Begin<br /> <br /> 6.<br /> <br /> P:= P ∪ {ai};<br /> <br /> 7.<br /> <br /> Tính các tập đặc trưng KP(xi), xi∈ U;<br /> <br /> 8.<br /> <br /> Tính các tập xấp xỉ dưới P(X ) , X∈ U/D;<br /> <br /> 9.<br /> <br /> Tính POSP(D);<br /> <br /> 10. If POSP(D) = POSC(D) then break;<br /> 11. End;<br /> 12. For với mỗi a ∈P do<br /> 13. If POSP\{a}(D) = POSC(D) then P:= P\{a};<br /> 14. End.<br /> Mệnh đề 3.1. Thuật toán trên là đúng đắn.<br /> ! Chứng minh<br /> - 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<br /> luôn tồn tại P để POSP(D) = POSC(D).<br /> - Từ dòng 12, 13 suy ra P là cực tiểu.<br /> 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).<br /> 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,<br /> m là số thuộc tính điều kiện.<br /> ! Chứng minh<br /> Độ 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 411) 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)<br /> (dòng 7) là O(n), tính các tập xấp xỉ dưới P(X ) (dòng 8) và POSP(D) (dòng 9) là O(n).<br /> Độ 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<br /> có độ phức tạp tính toán là O(mn2).<br /> Trong thực tế, thông thường m ε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<br /> xác cho phép.<br /> (ii) εi ≤ ε0 và εj ≤ ε0: cả hai đối tượng xi và xj đều “xác định”; do đó, sự không nhất<br /> 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<br /> hoặc trong quá trình thu thập dữ liệu.<br /> (iii) εi ≤ ε0 và εj > ε0 : xi xác định còn xj chứa quá nhiều giá trị thiếu.<br /> 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<br /> 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<br /> đế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ự<br /> “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<br /> được K C* ( xi ) và dùng nó trong giai đoạn sinh luật quyết định.<br /> 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<br /> 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<br /> nhưng có giá trị quyết định khác nhau.<br /> Chọn ε0 = 0.5. Ta có : ε1 =<br /> <br /> k1 0<br /> k<br /> 3<br /> = = 0 < ε 0 ; ε 4 = 4 = = 0.6 > ε 0<br /> C 5<br /> C 5<br /> <br /> ⇒ Loại đối tượng 4 ra khỏi KC(1) , tập đặc trưng mở rộng K C* (1) = {1}. Lúc này,<br /> <br />