intTypePromotion=1

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

Chia sẻ: Lâm Đức Duy | Ngày: | Loại File: PDF | Số trang:7

0
35
lượt xem
1
download

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ả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết 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 đủ trình bày 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,... Mời các bạn cùng tham khảo.

Chủ đề:
Lưu

Nội dung Text: 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 />
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2