Báo cáo nghiên cứu khoa học: " XỬ LÝ THÔNG TIN KHÔNG ĐẦY ĐỦ DỰA VÀO QUAN HỆ ĐẶC TRƯNG"

Chia sẻ: Nguyễn Phương Hà Linh Linh | Ngày: | Loại File: PDF | Số trang:11

Thêm vào BST

Báo xấu

56
lượt xem 6
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Trên thực tế, các cơ sở dữ liệu thường không đầy đủ vì nhiều nguyên nhân. Có nhiều tác giả (Kononenko,Pyle, Quinlan, Lobo…) đã đề xuất các cách xử lý khác nhau. Bài báo này đưa ra một cách tiếp cận trên cơ sở mở rộng quan hệ Không phân biệt được trong lý thuyết tập thô, đó là quan hệ đặc trưng ñược đề xuất bởi Jerzy W.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Báo cáo nghiên cứu khoa học: " XỬ LÝ THÔNG TIN KHÔNG ĐẦY ĐỦ DỰA VÀO QUAN HỆ ĐẶC TRƯNG"

TẠP CHÍ KHOA HỌC, Đại học Huế, Số 50, 2009 XỬ LÝ THÔNG TIN KHÔNG ĐẦY ĐỦ DỰA VÀO QUAN HỆ ĐẶC TRƯNG Hoàng Thị Lan Giao Trường Đại học Khoa học, Đại học Huế Nguyễn Thị Lan Anh Trường Đại học Sư phạm, Đại học Huế TÓM TẮT Trên thực tế, các cơ sở dữ liệu thường không đầy đủ vì nhiều nguyên nhân. Có nhiều tác giả (Kononenko,Pyle, Quinlan, Lobo…) đã đề xuất các cách xử lý khác nhau. Bài báo này đưa ra một cách tiếp cận trên cơ sở mở rộng quan hệ Không phân biệt được trong lý thuyết tập thô, đó là quan hệ đặc trưng ñược đề xuất bởi Jerzy W. Grzymala-Busse. Một thuật toán sinh luật quyết định trên bảng quyết định không đầy đủ - thuật toán NewLEM2 - cũng được chúng tôi xây dựng bằng cách sử dụng quan hệ đặc trưng này. I. Mở đầu Bài báo này sử dụng kỹ thuật xử lý thông tin không đầy đủ dựa vào quan hệ đặc trưng - là một mở rộng của quan hệ không phân biệt được - do Jerzy W. Grzymala - Busse đề xuất. Theo hướng tiếp cận này, giá trị thuộc tính thiếu trên hệ thống thông tin không đầy đủ được chia làm hai loại: giá trị bị mất và giá trị điều kiện không quan trọng. Trên cơ sở quan hệ đặc trưng, ba loại xấp xỉ: xấp xỉ đơn, xấp xỉ khái niệm, xấp xỉ tập con được xây dựng để xấp xỉ cho một tập khái niệm và dùng xấp xỉ khái niệm để sinh luật. Trong bài báo này, chúng tôi đề xuất một thuật toán để tìm phủ địa phương của một tập khái niệm cho trước, trên cơ sở đó sinh luật quyết định mô tả các đối tượng thuộc tập hợp này. II. Hệ thống thông tin - Quan hệ đặc trưng 2.1. Hệ thống thông tin Hệ thống thông tin là một cặp A = (U,A) trong đó U là một tập hữu hạn khác rỗng các đối tượng được gọi là tập vũ trụ; A là một tập hữu hạn khác rỗng các thuộc tính sao cho với mọi a ∈ A, a : U → Va (Va được gọi là tập giá trị của a), kí hiệu a(u) (hoặc u(a)) là giá trị của đối tượng u tại thuộc tính a. 2.2.Bảng quyết định Bảng quyết định là một hệ thống thông tin có dạng DT = (U, C ∪ D) trong đó C ∩ D = ∅. D gọi là tập thuộc tính quyết định (hay quyết định) và C là tập thuộc tính điều kiện. Không mất tính tổng quát, có thể xét tập thuộc tính quyết định D chỉ gồm một phần 39
tử d. Lúc đó, bảng quy ế t đ ị nh DT s ẽ đ ượ c vi ế t d ướ i d ạ ng DT = (U, C ∪ {d}) (hay đ ể c ho đ ơ n gi ả n là DT = (U,C,d) ), d∉C. Tuy nhiên, trên thực tế, tập dữ liệu thu được thường không đầy đủ mà bị thiếu một số giá trị thuộc tính trên một số đối tượng nào đó - tức là chứa giá trị thiếu - vì nhiều lí do khác nhau. Một hệ thống thông tin như thế được gọi là hệ thống thông tin không đầy đủ - tương ứng ta có bảng quyết định không đầy đủ. Trên bảng quyết định không đầy đủ, giá trị thuộc tính bị thiếu được chia làm hai loại [3,4,6,7]: Giá trị bị mất, giá trị này được kí hiệu là “?”: ban đầu, giá trị tại thuộc tính đó của đối tượng đang xét vẫn có và có ảnh hưởng đến việc phân lớp quyết định của đối tượng. Tuy nhiên, vì lý do nào đó mà giá trị này bị xóa đi và hiện tại chúng ta không thể xác định được. Giá trị điều kiện không quan trọng, giá trị này được kí hiệu là “*”: giá trị ban đầu của đối tượng trên thuộc tính đang xét không được lưu lại do không có ý nghĩa trong việc ra quyết định phân lớp đối tượng đó. Cho b ả ng quy ế t đ ị nh không đ ầ y đ ủ D T = (U,C,D). V ớ i thu ộ c tính a ∈ C, v ∈ V a , kí hi ệ u t = (a,v) là cặp thuộc tính-giá trị; [t]: khối (block) của t, là tập tất cả các đối tượng trong U có giá trị trên thuộc tính a bằng v. Lúc đó, nếu tồn tại một đối tượng x sao cho a(x) = ?, nghĩa là giá trị của x tại thuộc tính a bị mất, thì x không thuộc vào bất kỳ một khối [(a,v)] nào với mọi giá trị v của a; nếu tồn tại một đối tượng x sao cho a(x) = *, nghĩa là giá trị của x tại thuộc tính a là điều kiện không quan trọng, thì x thuộc vào mọi khối [(a,v)] với mọi giá trị v của a. Bảng 1 là một ví dụ của bảng quyết định không đầy đủ. Bảng 1: Bảng quyết định không đầy đủ U Temperature Headache Nausea Flu yes 1 high ? no yes 2 Very-high Yes yes no 3 ? No no yes 4 high Yes yes no 5 high ? yes no 6 Normal Yes no no 7 Normal No yes yes 8 * Yes * Với bảng quyết định cho ở Bảng 1, ta có các khối của các cặp thuộc tính - giá trị: 40
[(Headache,no)] = {3,7} [(Temperature, high)] = {1,4,5,8} [(Nausea,yes)] = {2,4,5,7,8} [(Temperature, Very-high)] = {2,8} [(Nausea,no)] = {1,3,6,8} [(Temperature, Normal)] = {6,7,8} [(Headache,yes)] = {2,4,6,8} Cho x ∈U; B⊆C. Tập đặc trưng KB(x) của đối tượng x được định nghĩa: I [(a, a( x)] K B ( x) = a∈B , a ( x ) ≠?,a ( x ) ≠* Ví dụ, với Bảng 1 đã cho: KC(1) = K(1,Temperature) ∩ K(1, Headache) ∩ K(1,Nausea) = {1,4,5,8} ∩ U ∩ {1,3,6,8} = {1,8} Tương tự, ta có: KC(2) = {2,8} KC(5) = {4,5,8} KC(7) = {7} KC(3) = {3} KC(6) = {6,8} KC(8) = {2,4,6,8} KC(4) = {4,8} J.W.Grzymala-Busse đã mở rộng quan hệ B-không phân biệt được lên hệ thống thông tin không đầy đủ thành quan hệ đặc trưng R(B) được định nghĩa như sau: R(B) = {(x,y) ∈U2 y∈KB(x)}, ở đây B ⊂ C R(B) có tính phản xạ, nhưng nói chung không có tính đối xứng và tính bắc cầu. Tập đặc trưng của X theo quan hệ đặc trưng R(B) cũng có thể xác định: KB(x) = {y (x,y) ∈ R(B)} III. Xấp xỉ trên, xấp xỉ dưới Cho X ⊆U. X được gọi là tập khái niệm nếu ∀x,y∈X, d(x) = d(y). Trên bảng quyết định không đầy đủ, với X⊆U là một tập khái niệm và quan hệ đặc trưng R(B), người ta xây dựng ba cách xấp xỉ tập X như sau : 3.1. Xấp xỉ đơn: xây dựng các tập xấp xỉ dựa vào các tập đơn B-xấp xỉ dưới đơn của X là tập hợp: U {x } B(X ) = x ∈U , K B ( x ) ⊆ X B-xấp xỉ trên đơn của X là tập hợp: U {x } B(X ) = x ∈U , K B ( x ) ∩ X ≠ ∅ 41
3.2. Xấp xỉ tập con: xây dựng các tập xấp xỉ dựa vào các tập con của U B-Xấp xỉ dưới tập con của X: U K B (x) B(X ) = x ∈U , K (x)⊆ X B B-Xấp xỉ trên tập con của X: U B(X ) = K B ( x) x∈U , K B ( x ) ∩ X ≠∅ Vì quan hệ đặc trưng R(B) có tính phản xạ nên với mỗi tập khái niệm X, B-xấp xỉ d ướ i đ ơ n và B-x ấ p x ỉ t rên đ ơ n l ầ n l ượ t là các t ậ p con c ủ a B-x ấ p x ỉ d ướ i t ậ p con và B-xấp xỉ trên tập con của X. IV. Xấp xỉ khái niệm: được định nghĩa bằng cách thay không gian U trong định nghĩa của xấp xỉ tập con bằng tập khái niệm X. B-xấp xỉ dưới khái niệm của X: U K B (x) B(X ) = x∈ X , K (x)⊆ X B B-xấp xỉ trên khái niệm của X: U B(X ) = K B (x) x∈ X , K B ( x ) ∩ X ≠ ∅ Với Bảng 1 và hai tập khái niệm X1, X2 được xác định X1 = {1,2,4,8} và X2 = {3,5,6,7} thì: Tập C-xấp xỉ dưới đơn và tập C-xấp xỉ trên đơn tương ứng của X1 và X2 là: C ( X 1 ) = {1,2,4}; C ( X 1 ) = {1,2,4,5,6,8} C ( X 2 ) = {3,7}; C ( X 2 ) = {3,5,6,7,8} Tập C-xấp xỉ dưới tập con và C-xấp xỉ trên tập con của X1, X2 lần lượt là: C ( X 1 ) = {1,2,4,8}; C ( X 1 ) = {1,2,4,5,6,8} C ( X 2 ) = {3,7}; C ( X 2 ) = {3,4,5,6,7,8} Tập C-xấp xỉ dưới khái niệm và C-xấp xỉ trên khái niệm của X1, X2: C ( X 1 ) = {1,2,4,8}; C ( X 1 ) = {1,2,4,6,8} C ( X 2 ) = {3, 7}; C ( X 2 ) = {3,4,5,6,7,8} Ta dễ dàng nhận thấy rằng B-xấp xỉ dưới khái niệm và B-xấp xỉ dưới tập con của X là như nhau; B-xấp xỉ trên khái niệm là tập con của B-xấp xỉ trên tập con, đồng thời là tập nhỏ nhất chứa tập X. 42
Theo [3], B-xấp xỉ khái niệm thích hợp cho việc sinh luật nhất. Trong trường hợp bảng quyết định đang xét là đầy đủ, ba loại xấp xỉ đơn, xấp xỉ tập con và xấp xỉ khái niệm là trùng nhau. Nhưng đối với bảng quyết định không đầy đủ thì điều này chưa chắc đúng. V. Sinh luật trên bảng quyết định Theo [3], quá trình sinh luật trên bảng quyết định không đầy đủ sử dụng khối thuộc tính-giá trị bao gồm các bước: tính các khối thuộc tính - giá trị, tính tập đặc trưng và quan hệ đặc trưng, tính các tập xấp xỉ, các khối thuộc tính - giá trị kiểu liên tục (nếu có), sinh luật; trong đó bước sinh luật được thực hiện bằng thuật toán LEM2. Thuật toán này khai phá không gian tìm kiếm là các bộ thuộc tính-giá trị, tìm ra một phủ địa phương, chính là tập các thành phần điều kiện của tập luật mô tả tập đối tượng đang xét. Tuy nhiên, theo [10,11], ta có thể làm giảm độ phức tạp của quá trình khai phá luật bằng cách rút gọn bảng quyết định trước khi tiến hành quá trình sinh luật. Như vậy, thay vì thực hiện việc tính các khối thuộc tính-giá trị, tính tập đặc trưng, quan hệ đặc trưng,… và sinh luật trên một bảng dữ liệu lớn, ta chỉ tiến hành trên bảng nhỏ hơn, đơn giản hơn. Ngoài ra, để cải thiện tốc độ thực hiện thuật toán, trong bài báo này chúng tôi sẽ đề xuất một thuật toán mới cũng nhằm tìm kiếm một phủ địa phương mô tả tập khái niệm cho trước là thuật toán NewLEM2. Cho V là tập xấp xỉ dưới hoặc tập xấp xỉ trên khác rỗng của một tập khái niệm có giá trị thuộc tính quyết định là w. Với một tập các bộ thuộc tính-giá trị bất kỳ T = {t = (a,v)}, ký hiệu [T ] = I [t ] t∈T Khi đó, tập V được gọi là phụ thuộc vào tập T nếu và chỉ nếu ∅ ≠ [T ] ⊆ V . T được gọi là phức cực tiểu (minimal complex) của V nếu và chỉ nếu V phụ thuộc vào T và không tồn tại T’ con của T sao cho V phụ thuộc vào T’. Phức cực tiểu T của tập xấp xỉ V chính là phần điều kiện của một luật quyết định đúng với các đối tượng x thuộc [T]. Gọi τ là họ các tập khác rỗng thuộc tính-giá trị, τ ≠ ∅. τ được gọi là phủ địa phương (local covering) của V khi và chỉ khi thỏa mãn các điều kiện sau: Mỗi phần tử T của τ là một phức cực tiểu của V ∪T∈τ[T] = V và τ cực tiểu, nghĩa là τ có số phần tử nhỏ nhất. Như vậy, τ chính là tập nhỏ nhất gồm các phức cực tiểu mô tả một cách đầy đủ tập xấp xỉ V của tập khái niệm X và việc đi tìm τ chính là đi tìm phần điều kiện của tập các luật quyết định mô tả tập V. Thuật toán NewLEM2 trình bày dưới đây làm nhiệm vụ đi tìm tập τ đó. 43
Ta thấy rằng, tập xấp xỉ khái niệm của một tập khái niệm X chính bằng hợp của những tập đặc trưng KC(x) của các đối tượng x trong X mà KC(x) ⊆ V và một phức cực tiểu nếu đúng với một đối tượng x thì cũng đúng với các đối tượng khác thuộc cùng tập đặc trưng của nó. Vì vậy, thay vì tìm T bằng cách “nhặt” từng bộ thuộc tính-giá trị t sao cho [t] chứa nhiều xi thuộc V nhất như trong thuật toán LEM2, chúng ta sẽ tìm T cho cả một tập đặc trưng; đồng thời, thay vì tìm t trong tập tất cả các cặp thuộc tính-giá trị thì chỉ cần tìm trong số các cặp thuộc tính-giá trị tương ứng với các thuộc tính điều kiện mà giá trị của đối tượng ứng với tập đặc trưng đang xét tại thuộc tính đó là xác định bằng thuật toán NewLEM2. Thuật toán NewLEM2 là một cải tiến của thuật toán LEM2, cũng nhằm mục đích xây dựng phủ tối tiểu các phức cực tiểu của một tập xấp xỉ khái niệm của một tập khái niệm, tức là đi tìm tất cả các vế trái của các luật quyết định mô tả tập (xấp xỉ) khái niệm đó. Với mỗi x thuộc V mà lớp đặc trưng của nó là con của V, ta sẽ rút gọn tập thuộc tính mô tả KC(x), tức là đi tìm C’ ⊂ C nhỏ nhất mà KC’(x) ⊆ V. Sau đó, loại khỏi C’ những bộ t thừa. C’ chính là T: phức cực tiểu mô tả KC’(x). Quá trình tìm phức cực tiểu được tiếp tục với các x còn lại trong V cho tới khi mọi đối tượng đều được miêu tả bởi một phức cực tiểu tương ứng nào đó. Thuật toán cụ thể như sau: Thuật toán NewLEM2 Input: Tập xấp xỉ khái niệm V của tập khái niệm X; Output: Phủ địa phương τ của V; Begin 1. 2. G := V; τ:= ∅; 3. while G ≠∅ 4. begin 5. T := ∅; 6. Chọn x ∈ G đầu tiên sao cho KC(x) ⊆ V và K C ( x) ∩ G là lớn nhất. 7. TV(x):={t = (a,a(x)) (a∈C) và (a(x) xác định)}; 8. while T = ∅ or [T] ⊄ V 9. begin 10. Chọn một bộ t∈ TV(x) đầu tiên sao cho [t ] ∩ G là lớn 11. nhất; ưu tiên chọn bộ t∈TV(x) sao cho với mọi (y∈[T]) và (y∉V) thì y∉[t] T := T ∪ {t} ; 12. G :=[t]∩G ; 13. 14. TV(x):= TV(x)-T ; end {while 9} 15. 44
for mỗi t ∈ T do 16. if [T –{t}] ⊆ V then T := T –{t}; 17. τ:= τ ∪ {T}; 18. V − UT∈τ [T ] ; 19. G := end {while 4}; 20. for mỗi T ∈ τ do 21. S ∈τ −{T } [S ] = V then τ := τ - {T}; U if 22. end {procedure}. 23. Chứng minh tính đúng đắn của thuật toán: V phụ thuộc T : [T] ⊆ V (i) Vì T = {t = (a,v) a(x) =v, a∈C, v∈Va, v≠*, v≠? } và KC(x) = I[a, a( x)] , do a∈C a(x) xaùc ñònh đó, khi TV(x) = ∅, ta sẽ có [T] = KC(x). Mà KC(x) ⊆ V. Vậy [T] ⊆ V. T cực tiểu (ii) Từ dòng 16,17 => T cực tiểu. U [T ] = V (iii) T ∈τ U [T ]⊆ V. Theo (i), ∀T ∈τ, [T] ⊆ V => T ∈τ M ặ t khác, c ứ m ỗ i l ầ n th ự c hi ệ n vòng l ặ p t ừ d òng 4-20, ta thu đ ượ c [T] = K C’ (x) v ớ i C’ ⊂ C v à K C (x) ⊆ V, ∀ x ∈ V. U [T ] ⊇ V UK UK ( x) ⊇ V ( Vì KC(x) ⊆ KC’(x) và ( x) = V ) hay => C' C x∈V x∈V U [T ] = V. Vậy T ∈τ τ cực tiểu. (iv) Từ dòng 21, 22 => τ cực tiểu. Ví dụ, xét bảng quyết định không đầy đủ ở Bảng 1, tập khái niệm X= {1,2,4,8}. Tập xấp xỉ dưới khái niệm V = C ( X ) = { ,2,4,8}. Quá trình sinh luật bằng thuật toán 1 NewLEM2 như sau: Ta có các tập đặc trưng của các đối tượng thuộc V là K C (1) = {1,8}; K C (2) = {2,8}; KC(4) = {4,8}; KC(8) = {2,4,6,8}. § Đầu tiên, khởi gán G := V = {1,2,4,8}; τ := ∅; 45
§ Thực hiện vòng lặp ngoài cùng (dòng 4-20): • T := ∅ ; • Trong số các x∈G mà KC(x) ⊆ V, ta chọn x = 1 vì đây là phần tử đầu tiên có K C ( x) ∩ G lớn nhất. • TV(1) = {(Temperature,high), (Nausea,no)} • Lúc này, T = ∅, bắt đầu thực hiện vòng lặp trong (dòng 9-15): − Vì [(Temperature, high)] ∩ G = 3 > [( Nausea, no)] ∩ G = 2 − chọn t = (Temperature,high) − T = T ∪ {t} = {(Temperature,high)}; − G = [t] ∩ G = {1,4,5,8}∩{1,2,4,8} = {1,4,8}; − TV(1) = {(Nausea,no)}; • [T] = {1,4,5,8}⊄ V nên tiếp tục thực hiện vòng lặp từ dòng 9-15: Tương tự như trên, ta chọn được t = (Nausea,no) ⇒ T = {(Temperature,high), (Nausea,no)}; G = {1,8}; [T] = {1,8}⊆ V ⇒ τ = {{(Temperature,high), (Nausea,no)}}; U τ [T ] = {2,4}≠∅ nên chúng ta tiếp tục vòng lặp ngoài § Đến đây, G = V − T∈ (4-20): • T := ∅ ; • Trong số hai phần tử của G, chọn x = 2 vì K C (2) ∩ G = K C (4) ∩ G =1 và 2 là phần tử đầu tiên. • TV(2) = {(Temperature,Very-high),(Headache,yes), (Nausea,yes)} • T = ∅, bắt đầu thực hiện vòng lặp trong (dòng 9-15): − Chọn t = (Headache,yes) vì [( Headache, yes)] ∩ G = 2, lớn nhất − T = T ∪ {t} = {(Headache,yes)} − G = [t] ∩G = {2,4} − TV(2) = {(Temperature,Very-high), (Nausea,yes)} • [T] = {2,4,6,8} ⊄ V, tiếp tục thực hiện vòng lặp trong: Chọn t = (Nausea,yes); T = {(Headache, yes), (Nausea, yes)}; G = {2,4}, [T] = {2,4,8} ⊆ V 46
⇒ τ = {{(Temperature,high), (Nausea,no)}, {(Headache,yes), (Nausea,yes)} }; U τ [T ] = ∅, thoát khỏi vòng lặp. § Lúc này, G = V − T∈ § Loại bỏ T dư thừa khỏi τ (dòng 21-22), kết quả thu được τ = {{(Temperature,high), (Nausea,no)}, {(Headache,yes), (Nausea,yes)} } Vậy, tập luật chắc chắn gồm 2 luật: § (Headache,yes) ∧(Nausea,yes) (Flu,yes) § (Temperature, high) ∧(Nausea,no) (Flu,yes) Trong trường hợp sử dụng thuật toán LEM2, tập luật chắc chắn tương ứng với tập khái niệm X ={1,2,4,8} [3] là: § (Temperature, high) ∧(Headache,yes) (Flu,yes) § (Temperature,Very high) (Flu,yes) § (Temperature, high) ∧(Nausea,no) (Flu,yes) Nhận xét: Tập luật chắc chắn sinh ra cho tập X ={1,2,4,8} của bảng quyết định không đầy đủ trên bằng cách dùng thuật toán NewLEM2 tốt hơn so với dùng thuật toán LEM2: số lượng luật ít hơn, đúng với nhiều đối tượng hơn. Gọi n là số phần tử của tập V, m là số thuộc tính điều kiện của bảng quyết định không đầy đủ đang xét ( m = card(C)). Theo [8], ta có độ phức tạp tính toán của thuật toán LEM2 là O(mn2). Bây giờ, ta sẽ tính độ phức tạp tính toán của thuật toán NewLEM2: vòng lặp ngoài cùng (từ dòng 4 đến dòng 20) sẽ được thực hiện tối đa là n lần. Ở phần tính phức T (bắt đầu từ dòng 9), tương ứng với mỗi đối tượng x, thuật toán phải thực hiện tối đa là m lần vì phải kiểm tra hết mọi cặp thuộc tính-giá trị (a,a(x)) trong TV(x), a ∈ C (card(TV(x)) ≤ m). Tại bước loại bỏ t dư thừa (tương ứng ở dòng 16-17), do T có tối đa m cặp thuộc tính-giá trị nên bước này có độ phức tạp tính toán là O(m). Từ dòng 21-22 (loại T dư thừa), độ phức tạp tính toán là O(n2) vì τ có tối đa n phần tử, ứng với mỗi phần tử phải kiểm tra n-1 lần (dòng 22). Lúc đó, độ phức tạp tính toán của thuật toán NewLEM2 là O(n2). Ở đây, chúng ta cần để ý một điều là việc tính các tập đặc trưng KC(x), x∈V được thưc hiện trước khi tiến hành bước sinh luật quyết định cho dù sử dụng thuật toán LEM2 hay NewLEM2. Vì vậy, để tiện cho việc so sánh độ phức tạp tính toán của hai thuật toán này, chúng ta có thể xem độ phức tạp tính toán của bước tính KC(x) trong thuật toán NewLEM2 là 1. 47
Như vậy, độ phức tạp tính toán của thuật toán NewLEM2 là O(n2) bé hơn độ phức tạp tính toán của thuật toán LEM2 là O(mn2). Tuy nhiên, trong thực tế, khi sử dụng thuật toán NewLEM2, chúng ta có thể rút gọn thời gian tìm kiếm các bộ t (dòng 9 đến 15) đi n lần so với LEM2. Điều này có ý nghĩa rất lớn vì các cơ sở dữ liệu thực thường chứa rất nhiều đối tượng, nghĩa là n rất lớn. Thuật toán LEM2 và NewLEM2 chỉ mới sinh ra phần điều kiện của tập luật chắc chắn (nếu tập đối tượng dùng để huấn luyện là xấp xỉ dưới) hoặc có thể chấp nhận được (nếu dùng tập xấp xỉ trên để huấn luyện). Trường hợp sinh luật chắc chắn, giá trị quyết định của các luật sinh ra từ một tập khái niệm chính là giá trị quyết định của các đối tượng thuộc tập hợp đó. Tuy nhiên, trong trường hợp dùng tập xấp xỉ trên để sinh luật thì giá trị quyết định của từng luật được xác định: trong số các đối tượng thỏa phần điều kiện của luật đang xét, xác định số lượng của từng nhóm đối tượng có giá trị quyết định giống nhau, giá trị quyết định của luật chính là quyết định của nhóm có số phần tử lớn nhất. VI. Kết luận Dựa vào các khái niệm của lý thuyết tập thô nguyên thủy và quan hệ đặc trưng, chúng tôi đã đưa ra một thuật toán tìm phủ địa phương cho một tập khái niệm và sinh luật cho tập hợp này. Thuật toán có độ phức tạp tính toán bé hơn thuật toán do Grzymala-Busse đưa ra, nên hiệu quả hơn về thời gian tính toán và chất lượng của tập luật cũng có thể tốt hơn. TÀI LIỆU THAM KHẢO 21. Nguyễn Thị Lan Anh, Nghiên cứu các phương pháp mở rộng quan hệ không phân biệt được trên hệ thống thông tin không đầy đủ, Luận văn thạc sĩ khoa học ngành Khoa học máy tính, Đại học Huế, 2008. 22. Hoàng Thị Lan Giao, Cơ sở dữ liệu với thông tin không đầy đủ, Luận văn thạc sĩ khoa học ngành Tin học, Trường Đại học Bách khoa Hà Nội, 1998. 23. Grzymala-Busse J.W, 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 (2004), 78-95. 24. Grzymala-Busse J.W. 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, 2004. 25. Grzymala-Busse J.W. Chapter 13 Rule Induction, Data Mining and Knowledge Discovery Handbook, Springer US, Part II, (2005), 277-294. 26. Grzymala-Busse J.W. Rough Set Strategies to Data with Missing Attribute Values, Proceedings of the Workshop on Foundations and New Directions in Data Mining, 48
associated with the third IEEE International Conference on Data Mining, November 19- 22, Melbourne, FL, USA, (2003), 56-63. 27. Grzymala-Busse J.W., Siddhaye S. 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, July 4-9, vol.2, (2004), 923-930. 28. Leifler O. Comparison of LEM2 and a Dynamic Reduct Classification Algorithm, Master’s thesis, performed in Artificial Intelligence & Integrated Computer Systems Division Dept. of Computer and Information Science at Linkopings universitet, (2002). 29. Pawlak Z. Rough Sets, International Journal of Computer and Information Sciences, grammars.grlmc.com, 1982. 30. Skowron A. Rough Sets and Boolean Reasoning, Granular computing: an emerging paradigm, (2001), 95-124. 31. Skowron A., Zhong N. Rough Sets in KDD, Tutorial Notes, 2000. DEALING WITH INCOMPLETE DATA BASED ON CHARACTERISTIC RELATION Hoang Thi Lan Giao College of Sciences, Hue University Nguyen Thi Lan Anh College of Pedagogy, Hue University SUMMARY The databases in practice usually contain missing values for several reasons. Many methods dealing with this value have been developed. In this article, we present an approach which is based on the extention of Indiscernibility Relation in Rough Sets known as the Characteristic Relation of Jerzy W. Grzymala-Busse. Using this relation, we propose new algorithm - NewLEM2 - which induces decision rules in incomplete decision table. 49