Lý thuyết tập thô

5 Chương 2. KIẾN THỨC CƠ BẢN 2.1. LÝ THUYẾT TẬP THÔ Lý thuyết tập thô(Rough Set Theory) được phát triển bởi Zdzislaw Pawlak[12] vào đầu những năm 1980 được xem như một cách tiếp cận mới để phát hiện tri thức và nó tạo thành một cơ sở vững chắc cho các ứng dụng khai phá dữ liệu, vấn đề nỗi bật của lý thuyết tập thô là việc đưa ra ý tưởng để giải quyết tính mơ hồ và không chắc chắn của hệ thông tin. Thêm vào đó, việc sử dụng rút gọn (Reduct) thay vì toàn bộ tập thuộc tính điều kiện trong quá trình khai phá dữ liệu đã loại bỏ được những thông tin dư thừa, thiếu chính xác. Rút gọn chính là tập các thuộc tính quan trọng và cần thiết nhất trong CSDL, do đó việc tìm các rút gọn hoàn toàn tự nhiên và cần thiết. Chương này trình bày về các khái niệm trong lý thuyết tập thô và các thuật toán tìm các rút gọn và lõi. 2.1.1. Các khái niệm 2.1.1.1. Hệ thông tin Hệ thông tin (Information System) là một cặp (U, A) với U là tập hữu hạn khác rỗng các đối tượng (còn được gọi là tập vũ trụ các đối tượng), và A là tập hữu hạn khác rỗng các thuộc tính. Với mỗi thuộc tính Aa ∈ , ta ký hiệu Va là tập các giá trị của thuộc tính a (hay còn gọi là miền của thuộc tính a). Nếu Ux ∈ và Aa ∈ , ta ký hiệu aVax ∈)( là giá trị thuộc tính a của đối tương x. U Đau đầu Đau cơ Thân nhiệt u1 Không Có Cao u2 Có Không Cao u3 Có Có Rất cao u4 Không Có Bình thường u5 Có Không Cao u6 Không Có Rất cao Bảng 2.1. Một ví dụ về Hệ thông tin 6 Xem ví dụ đơn giản về hệ thông tin trong Bảng 2.1, ta có tập vũ trụ },,,,,{ 654321 uuuuuuU = , tập các thuộc tính =A {Đau đầu, Đau cơ, Thân nhiệt}. 2.1.1.2. Bảng quyết định Bảng quyết định (Decision Table) là một hệ thống thông tin có dạng ),( AUT = với DCA ∪= và φ≠∩ DC , trong đó C là tập các thuộc tính điều kiện (Condition Attributes) và D là tập các thuộc tính quyết định (Decision Attributes). Trong một số trường hợp, người ta ký hiệu ),( DCT = . U Đau đầu Đau cơ Thân nhiệt Cúm u1 Không Có Cao Có u2 Có Không Cao Có u3 Có Có Rất cao Có u4 Không Có Bình thường Không u5 Có Không Cao Không u6 Không Có Rất cao Có Bảng 2.2. Một ví dụ về Bảng quyết định Bảng quyết định trong Bảng 2.2 tương tự như Bảng 2.1, nhưng thêm vào thuộc tính “Cúm” với Vcúm = {Có, Không}. Tập thuộc tính =A {Đau đầu, Đau cơ, Thân nhiệt, Cúm}, trong đó tập thuộc tính điều kiện C = {Đau đầu, Đau cơ, Thân nhiệt} và tập thuộc tính quyết định D = {Cúm}. 2.1.1.3. Quan hệ không phân biệt được Quan hệ không phân biệt được (Indiscernibility Relation): Hệ thống thông tin ),( DCAUT ∪== , với mỗi tập AB ⊆ xác định một quan hệ không phân biệt được )(BIND được định nghĩa như sau: { })()(,|),()( yaxaBaUUyxBIND =∈∀×∈= Nếu (x, y) ∈ IND(B), ta nói rằng x và y là không phân biệt được ứng với tập thuộc tính B. Quan hệ không phân biệt được còn gọi là một quan hệ tương đương và chia tập vũ trụ U thành một họ các lớp tương đương, họ các lớp tương đương này được xem như là sự phân lớp và được ký hiệu U/IND(B). 7 Ví dụ : Xét Bảng 2.2 minh họa cho quan hệ không phân biệt được. Nhận thấy các bệnh nhân u2, u3, u5 không phân biệt được với thuộc tính “Đau đầu”, bệnh nhân u2, u5 không phân biệt được với thuộc tính “Đau đầu”, “Đau cơ”… U/IND({Đau đầu}) = {{u2, u3, u5}, {u1, u4, u6}} U/IND({Đau đầu, Đau cơ}) = {{u1, u4, u6}, {u2, u5}, {u3}} U/IND({Đau đầu, Đau cơ, Thân nhiệt}) = {{u1}, {u2, u5}, {u3}, {u4}, {u6}} U/IND({Cúm}) = {{u1, u2, u3, u6}, {u4, u5}} 2.1.1.4. Xấp xỉ Xem từ Bảng 2.2 ta nhận thấy rằng khái niệm Cúm hay Không cúm không thể định nghĩa được với các thuộc tính “Đau đầu”, “Đau cơ”, “Nhiệt độ”. Vì bệnh nhân u2 và u5 có cùng các triệu chứng, tức là có cùng giá trị các thuộc tính điều kiện “Đau đầu”, “Đau cơ”, “Nhiệt độ” nhưng bệnh nhân u2 bị cúm còn u5 thì không. Bởi vậy, lý thuyết tập thô đưa ra định nghĩa hai tập, gọi là xấp xỉ dưới và xấp xỉ trên. Xấp xỉ dưới (Lower Approximation) trong trường hợp Bảng 2.2 là tập tất cả các bệnh nhân có thể phân biệt được bệnh cúm rõ ràng, xấp xỉ trên (Upper Approximation) là tập các bệnh nhân không thể phân biệt được bệnh cúm. Cho bảng quyết định ),( DCAUT ∪== và UXAB ⊆⊆ , . Xấp xỉ dưới và xấp xỉ trên của tập X tương ứng với B, ký hiệu theo thứ tự là XB và XB được định nghĩa như sau: }][|{ XxUxXB B ⊆∈= }][|{ φ≠∩∈= XxUxXB B với [x]B là lớp tương đương chứa phần tử x của quan hệ IND(B) Rõ ràng XBXXB ⊆⊆ . Tập XBXBXBN B \)( = được gọi là B-miền biên của X, là các đối tượng không thể quyết định thuộc về X hay không khi dựa trên các thuộc tính của B. Còn tập XBU \ là B-miền ngoài của X, là các đối tượng không thuộc về X dựa trên các thuộc tính của B. 8 2.1.1.5. Miền dương Với bảng quyết định ),( DCAUT ∪== và AQB ⊆, . Miền dương (Positive Region) của phân lớp U/IND(Q) tương ứng với tập thuộc tính B ký hiệu )(QPOSB được định nghĩa như sau: )()( )( XBQPOS QINDXB ∈ = U Khi đó )(QPOSB được gọi là B-miền dương của Q. Hay nói cách khác, )(QPOSu B∈ nếu và chỉ nếu )()( BvBu = kéo theo )()( QvQu = với mọi Uv ∈ . Ví dụ: Xét bảng quyết định cho trong Bảng 2.2, với X= {x | Cúm(x) = Có} = {u1, u2, u3, u6}. Ta có:
=XC {u1, u3, u6}
=XC {u1, u2, u3, u5, u6}
=XBNC {u2, u5}
=− XCU {u4}
=)(DPOSC C XCó ∪ C XKhông={u1, u3, u6} ∪ {u4}={u1, u3, u4, u6} 2.1.1.6. Thuộc tính cần thiết và không cần thiết Định nghĩa 1. Một thuộc tính Cc j ∈ được gọi là không cần thiết (Dispensable) trong T nếu: )()( }\{ DPOSDPOS jCCC = Định nghĩa 2. Một thuộc tính Cc j ∈ được gọi là cần thiết (Indispensable) trong T nếu: )()( }\{ DPOSDPOS jcCC ≠ Ví dụ: Xét bảng quyết định T cho trong Bảng 2.2, ta có: =)(DPOSC C XCó ∪ C XKhông={u1, u3, u6} ∪ {u4}={u1, u3, u4, u6} POSC\{Đau đầu}(D)={u1, u3, u6} ∪ {u4}={u1, u3, u4, u6} POSC\{Đau cơ}(D)={u1, u3, u6} ∪ {u4}={u1, u3, u4, u6} POSC\{Thân Nhiệt}(D)={u3} ∪ φ ={u3} Vậy ta có thể kết luận: 9
Thuộc tính “Đau đầu”, “Đau cơ” không cần thiết trong T
Thuộc tính “Thân nhiệt” cần thiết trong T 2.1.1.7. Mức độ phụ thuộc liên quan Với bảng quyết định ),( DCUT ∪= , mức độ phụ thuộc liên quan (Relative Dependency) của D trên B ( CB ⊆ ) được định nghĩa như sau: U DPOS Dk BB )()( == γ Nếu k = 1: D phụ thuộc hoàn toàn vào B Nếu k < 1: D phụ thuộc một phần vào B (phụ thuộc mức độ k) 2.1.1.8. Rút gọn và lõi Định nghĩa 1. Tập thuộc tính CF ∈ được gọi là một phân biệt (Discern) của C nếu và chỉ nếu thỏa điều kiện: )()( DPOSDPOS CF = Định nghĩa 2. Một phân biệt R được gọi là một rút gọn (reduct) của C nếu và chỉ nếu thỏa điều kiện: )()(, DPOSDPOSRR CR ≠⊂′∀ ′ Hiển nhiên một tập thuộc tính điều kiện có ít nhất một rút gọn. Tập tất cả các rút gọn của C ký hiệu RED(C) Có thể nói, nếu F là một phân biệt thì )(CREDR ∈∃ và FR ⊆ Định nghĩa 3. Giao của tất cả các rút gọn được gọi là lõi (core), ký hiệu CORE(C) I )( )( CREDR RCCORE ∈ = Lõi là tập hợp tất cả các thuộc tính cần thiết trong T, lõi được chứa trong tất cả các rút gọn, và lõi có khả năng là tập rỗng. Ví dụ: Với bảng quyết định T cho trong Bảng 2.2. Xét R1 = {Đau cơ, Thân Nhiệt}, ta có: =)( 1 DPOS R {u1, u3, u4, u6} = )(DPOSC 10 POS{Đau cơ}(D) =φ ≠ )(DPOSC POS{Thân Nhiệt}(D) ={u3, u4, u6} ≠ )(DPOSC Suy ra {Đau cơ, Thân Nhiệt} là một rút gọn của C. Tương tự, ta cũng có R2={Đau đầu, Thân nhiệt} là một rút gọn của C. Vậy C có hai rút gọn R1, R2. Lõi của C: 21)( RRCCORE ∩= = {Thân nhiệt} Định nghĩa 4. Một thuộc tính Cc j ∈ được gọi là thuộc tính rút gọn nếu nó là một phần tử của rút gọn. Ví dụ: Với các rút gọn tìm được trong ví dụ trên, “Đau cơ” và “Đau đầu” là hai thuộc tính rút gọn. Theo lý thuyết tập thô, dựa trên bảng quyết định trong Bảng2.2, để có được mô hình phân lớp tốt cho thuộc tính “Cúm”, chúng ta cần thông tin của thuộc tính “Thân nhiệt” cùng với thông tin của thuộc tính “Đau đầu” hoặc “Đau cơ”, hai thuộc tính “Đau đầu” và “Đau cơ” không cần thiết trong cùng một lúc.  Nhận xét: Rút gọn và lõi là hai khái niệm quan trọng trong lý thuyết tập thô, một rút gọn là tập con của tập thuộc tính điều kiện, tìm được bằng cách loại bỏ đi các thuộc tính thừa mà không làm mất đi sức mạnh phân loại của bảng quyết định, hay nói cách khác rút gọn là tập thuộc tính điều kiện cực tiểu có khả năng quyết định giống như toàn tập thuộc tính điều kiện. Thuật toán tìm các rút gọn và lõi sẽ được trình bày cụ thể trong phần kế tiếp. 2.1.1.9. Ma trận khả phân Giả sử tập vũ trụ },...,,{ 21 nuuuU = . Ma trận khả phân (hay ma trận phân biệt được) của T, ký hiệu nnijDis mD ×= )( là một ma trận đối xứng mà mỗi phần tử của nó là một tập hợp các thuộc tính, được xác định như sau:     ≠∈ = = )()(| )()( cucuCc DuDu m ji ji ij λ Như vậy, mij là tập hợp gồm tất cả các thuộc tính điều kiện có thể xếp các đối tượng ui và uj vào các lớp tương đương khác nhau theo phân hoạch trên U , nếu , nếu ngược lại. 11 đối với thuộc đó. Nếu φ=ijm thì bảng quyết định là không nhất quán (có hai đối tượng ui và uj bằng nhau trên C nhưng khác nhau trên D). Giá trị λ hàm ý rằng cặp đối tượng ui và uj không phân biệt trên tập thuộc tính quyết định. Nếu R là một rút gọn thì với mỗi Rba ∈, ta có Dis({a}) ≠ Dis({b}). Ví dụ: Xét bảng quyết định trong Bảng 2.2, ma trận khả phân trong Bảng 2.3, trong đó Các ký hiệu Đ, C, N tượng trưng tương ứng cho các thuộc tính “Đau đầu”, “Đau cơ”, “Thân nhiệt”. U u1 u2 u3 u4 u5 u6 u1 λ u2 λ λ u3 λ λ λ u4 {N} {Đ, C, N} {Đ, N} λ u5 {Đ, C} φ {C, N} λ λ u6 λ λ λ {N} {Đ, C, N} λ Bảng 2.3. Ma trận khả phân xây dựng từ Bảng 2.2 Từ ma trận phân biệt được trong Bảng 2.3, ta có thể kết luận bảng quyết định cho trong Bảng 2.2 là không nhất quán, vì φ=25m . Ví dụ: Xét một bảng quyết định khác trong Bảng 2.4: U Bằng Cấp Kinh nghiệm Tiếng Anh Lời giới thiệu Tuyển dụng x1 Cao học 2-3 năm Lưu loát Xuất sắc Chấp nhận x2 Cao học 1 năm Lưu loát Bình thường Từ chối x3 Trung cấp 1 năm Lưu loát Tốt Từ chối x4 Đại học Hơn 3 năm Lưu loát Bình thường Chấp nhận x5 Đại học 2-3 năm Lưu loát Bình thường Từ chối x6 Đại học Hơn 3 năm Lưu loát Xuất sắc Chấp nhận x7 Cao học Hơn 3 năm Không Tốt Chấp nhận x8 Trung cấp 1 năm Không Xuất sắc Từ chối Bảng 2.4. Một ví dụ về Bảng quyết định Các ký hiệu b, k, t, l tương trưng tương ứng cho các thuộc tính “Bằng cấp”, “Kinh nghiệm”, “Tiếng Anh”, “Lời giới thiệu". Dựa vào ma trận khả phân (Bảng 2.5) ta có thể kết luận bảng quyết định trong Bảng 2.4 là nhất quán. 12 U x1 x2 x3 x4 x5 x6 x7 x8 x1 λ x2 {k,l} λ x3 {b,k,l} λ λ x4 λ {b,k} {b,k,l} λ x5 {b,l} λ λ {k} λ x6 λ {b,k,l} {b,k,l} λ {k,l} λ x7 λ {k,t,l} {b,k,t} λ {b,k,t,l} λ λ x8 {b,k,t} λ λ {b,k,t,l} λ {b,k,t} {b,k,l} λ Bảng 2.5. Ma trận khả phân xây dựng từ Bảng 2.4 2.1.1.10. Hàm khả phân Hàm khả phân f của một hệ thống thông tin là hàm số bool được định nghĩa như sau: tffff ...21 ∧∧= với },|{ λ≠∈∨= ijiji mmccf Ví dụ: Hàm khả phân tương ứng với ma trận khả phân trong Bảng 2.5 )()()()( tkblblkblkf ∨∨∧∨∧∨∨∧∨= )()( lkbkb ∨∨∧∨∧ )()()( tkblkblkb ∨∨∧∨∨∧∨∨∧ )( ltkbk ∨∨∨∧∧ )()( ltkblk ∨∨∨∧∨∧ )( tkb ∨∨∧ )( lkb ∨∨∧ 2.1.2. Thuật toán tìm các rút gọn Thông thường, bảng quyết định có nhiều hơn một rút gọn. Có thể nói rút gọn đóng vai trò khá quan trọng lĩnh vực khai phá dữ liệu, việc tìm tất cả các rút gọn trong bảng quyết định là một vấn đề rất khó khăn và được rất nhiều nhà nghiên cứu quan tâm, Skowron[2] đã chứng minh rằng tìm tất cả các rút gọn là 13 một bài toán với độ phức tạp là NP-khó, bởi vì thời gian tính toán các rút gọn tăng theo hàm mũ với số lượng các thuộc tính. Thuật toán mà luận văn sử dụng để tìm tất cả các rút gọn là thuật giải di truyền. A.Ohrn[3] đã sử dụng một thuật giải di truyền tìm các rút gọn được Wroblewski[8] đề xuất để tích hợp vào bộ công cụ ROSETTA – đây là bộ công cụ được sử dụng trong nhiều các ứng dụng phân tích dữ liệu với những hiệu quả đáng khích lệ. 2.1.2.1. Hitting Set Cho tập hợp },{ NiSS i ∈= là tập các phần tử có được từ vũ trụ U, một hitting set là tập UH ⊆ sao cho φ≠∩ iSH với i∀ . Nếu loại bỏ bất kỳ nguyên tử (element) nào trong H đều làm H không còn là hitting set nữa, khi đó H là minimal hitting set. HS(S) là tập tất cả các hitting set có được từ S và MHS(S) là tập tất cả các minimal hitting set. Ví dụ: Cho tập S gồm các phần tử như sau: S = {S1= {1, 2, 3, 4}, S2 = {1, 2, 4}, S3 = {1, 2}, S4 = {2, 3}, S5 = {4}} => MHS(S) = {H1={1, 3, 4}, H2={2, 4}} Việc tìm minimal hiting set ở ví dụ này có thể xem như là vấn đề của giáo viên và lớp học. Có tất cả 5 lớp học {S1, S2, S3, S4, S5} và 4 giáo viên 1, 2, 3, 4. Giáo viên 1, 2, 3, 4 có thể dạy lớp S1, giáo viên 1, 2, 4 có thể dạy lớp S2, giáo viên 1, 2 có thể dạy lớp S3,... Ta muốn tìm số giáo viên ít nhất mà có thể dạy tất cả các lớp, đó chính là tìm minimal hitting set, ở ví dụ này ta thu được tập MHS(S) gồm 2 minimal hiting set. 2.1.2.2. Rút gọn và Hiting set Rút gọn là tập thuộc tính nhỏ nhất có khả năng quyết định giống như toàn bộ tập thuộc tính điều kiện C, nói cách khác rút gọn R là tập các thuộc tính nhỏ nhất mà hai đối tượng bất kỳ trong bảng quyết định nếu phân biệt được dựa vào C+D thì cũng phân biệt được dựa vào R+D. Với ma trận khả phân, việc tìm rút 14 gọn chính là tìm tập thuộc tính nhỏ nhất R mà giao của R với từng phần tử (khác λ và khácφ ) trong ma trận khả phân đều khác rỗng. Như vậy, vấn đề tìm các rút gọn dễ dàng chuyển thành vấn đề tìm các minimal hitting set với tập tập S chính là các phần tử (khác λ và khácφ ) trong ma trận khả phân. 2.1.2.3. Tìm Minimal Hitting Set với thuật giải di truyền Thuật giải di truyền (Genetic Algorithm-GA) là kỹ thuật giúp giải quyết vấn đề bằng cách mô phỏng sự tiến hóa của con người hay của sinh vật nói chung (dựa trên thuyết tiến hóa muôn loài của Darwin) trong điều kiện qui định sẵn của môi trường, mục tiêu của GA không nhằm đưa ra lời giải chính xác tối ưu mà đưa ra lời giải tương đối tối ưu. Để tìm minimal hitting set bằng thuật giải di truyền chúng ta sử dụng chuỗi nhị phân để biểu diễn các phần tử (cá thể), mỗi chuỗi nhị phân được xem là nhiễm sắc thể (chromosome) tương ứng với một cá thể, mỗi bit ứng với mỗi element được xem là gen (genome) và tập hợp các cá thể được xem là quần thể (population). Chẳng hạn, các phần tử và các minimal hiting set trong ví dụ phần 2.1.2.1 có thể được mã hóa thành các nhiễm sắc thể như sau: { }{0,0,0,1} S{0,1,1,0},S{1,1,0,0},S{1,1,0,1},S{1,1,1,1},S 54321 ======S { }{0,1,0,1}H {1,0,1,1},H)( 21 ===SMHS Các toán tử di truyền được sử dụng để tìm các minimal hiting set bao gồm: lai ghép (crossover), đột biến (mutation), chọn lọc (selection), nghịch chuyển (inversion) và tồn tại (obtain). Toán tử lai ghép: Giả sử có hai nhiễm sắc thể },...,,{ 112111 nsssS = và },...,,{ 222212 nsssS = , chọn một số nguyên ngẫu nhiên từ ),0( nr ∈ , hai nhiễm sắc thể con được lai ghép từ S1 và S2 là: },...,,,...,,{ 212112113 nrr sssssS += },...,,,...,,{ 111222214 nrr sssssS += 15 Toán tử đột biến: Giả sử có nhiễm sắc thể },...,,{ 112111 nsssS = , chọn một số ngẫu nhiên ],0( nr ∈ , S3 là nhiễm sắc thể đột biến của S1: },...,,1,,...,{ 21111112113 nrrr ssssssS +− −= Toán tử nghịch chuyển: Với r và l là số ngẫu nhiên, giả sử nhiễm sắc thể },...,,...,,,...,,{ 1,1,11,1112111 nlrlrrr sssssssS ++++= , S2 là nghịch chuyển của S1: },...,,...,,,...,,{ 1,11,1,1112112 nlrrlrr sssssssS ++++= Toán tử chọn lọc: Giả sử có m cá thể trong quần thể, ta muốn chọn ra [m/2] cá thể và loại bỏ các cá thể còn lại, các cá thể được chọn phải đảm bảo độ thích nghi “fitness”. Hàm thích nghi (fitness function) trong thuật giải di truyền tìm các minimal hitting set phụ thuộc vào 2 yếu tố: số lượng các element trong cá thể (càng ít càng tốt) và số lượng tập giao khác rỗng của cá thể với các phần tử trong tập S - tập cần tìm các minimal hitting set (càng nhiều càng tốt). Hàm thích nghi được định nghĩa như sau: S SBSS C BC Bf ii φ≠∩∈+−= |)( Toán tử tồn tại: Giả sử tồn tại tập SS i ∈ chỉ có 1 element ( 1)( =iScard ), khi đó tất cả các hiting set cần phải chứa element này, nghĩa là gen của các nhiễm sắc thể ứng với element này phải luôn luôn bằng 1, ta gọi toán tử này là “obtain”.  Thuật giải GA tìm các minimal hitting set[8] Bước 1. Phát sinh ngẫu nhiên iSSk ** nhiễm sắc thể để tạo thành quần thể ban đầu, với k là một hằng số. Bước 2. Kiểm tra xem có điều kiện dừng nào thỏa mãn hay không? nếu có thì dừng quá trình. Ở thuật toán này, điều kiện dừng là số thế hệ vượt ngưỡng cho phép T. Bước 3. Sử dụng toán tử chọn lọc để chọn lựa những cá thể tốt, loại bỏ những cá thể xấu từ quần thể. 16 Bước 4. Sử dụng các toán tử lai ghép, đột biến, nghịch chuyển và tồn tại để tạo các nhiễm sắc thể con. Bước 5. Kết hợp các nhiễm sắc thể con với quần thể hiện tại để tạo quần thể mới bằng toán tử chọn lọc. Bước 6. Quay lại bước 2. Thuật toán này có độ phức tạp là O(n|Si|). 2.1.3. Thuật toán tìm rút gọn tối ưu Trong rất nhiều ứng dụng, không cần thiết phải tìm tất cả các rút gọn mà chỉ cần một rút gọn là đủ. Luận văn sử dụng thuật toán loại trừ ngược heuristic[13] dựa vào số lượng các giá trị của thuộc tính điều kiện – được gọi là card, từ các ví dụ thực tế nhóm tác giả [13] đã có nhận xét rằng thuộc tính có giá trị card càng lớn thì càng càng thiết. Khởi gán R = C, tại mỗi bước lặp chọn thuộc tính Rq ∈ có giá trị card là thấp nhất và loại q ra khỏi R cho đến khi R là một rút gọn. Bằng cách tiếp cận này ta có thuật toán heuristic mới tìm rút gọn tối ưu như sau: Input: Bảng quyết định nhất quán ),( DCT = Output: Một rút gọn R của T Generate_Optimal_Reduct(T) { φ== QCR , for (mỗi thuộc tính Rq ∈ ) })(,{ ><∪= qcardqQQ while ( φ≠Q ) { =q thuộc tính có card nhỏ nhất trong Q if ( 1)(}{ =− DqRγ ) }{qRR −= } return R } 17 2.1.4. Tập thô và rời rạc hóa dữ liệu 2.1.4.1. Giới thiệu Rời rạc hoá dữ liệu là quá trình tiền xử lý dữ liệu có vai trò quan trọng trong lĩnh vực khai phá dữ liệu. Đây là quá trình ánh xạ các giá trị số liên tục vào các giá trị khoảng nhất định để tăng độ tổng quát của thông tin, đơn giản hoá việc biểu diễn cũng như xử lý trên các giá trị số tạo điều kiện thuận lợi cho quá trình tìm kiếm tri thức. Đã có rất nhiều thuật toán được sử dụng trong rời rạc hoá dữ liệu như: thuật toán rời rạc hoá theo khoảng cách, thuật toán đơn giản, các thuật toán dựa trên tiêu chuẩn thống kê..., tuy nhiên không có một thuật toán nào được xem là tối ưu và hiệu quả nhất. Việc lựa chọn thuật toán vẫn còn phụ thuộc vào dạng dữ liệu mà chúng ta cần xử lý. Ở đây luận văn tìm hiểu thuật toán sử dụng suy diễn nhị phân theo cách tiếp cận thô do nhóm tác giả Nguyễn Hùng Sơn[10], thuật toán đã được thử nghiệm và tích hợp vào bộ công cụ ROSETTA, việc thử nghiệm này cho các kết quả rất khả quan. 2.1.4.2. Tập thô và bài toán rời rạc hóa dữ liệu Rời rạc hoá dữ liệu được hiểu là một hàm số: aa CVQ →: với Va là miền giá trị của thuộc tính a cần rời rạc hoá và Ca là bộ giá trị rời rạc mà thuộc tính a có thể nhận được sau khi tiến hành rời rạc hoá. Với mỗi giá trị aVv ∈ , hàm rời rạc hoá sẽ gán cho nó một nhãn aCc ∈ tương ứng, nhãn c sẽ được sử dụng thay cho các giá trị thực v của dữ liệu trong quá trình phân tích. Bài toán rời rạc hoá dữ liệu được phát biểu theo lý thuyết tập thô như sau: Với bảng quyết định nhất quán ),( DCUT ∪= và tập vũ trụ U = {x1, x2,.., xn}, giả sử mọi thuộc tính Ca ∈ là liên tục với Va là miền giá trị của thuộc tính a: R )r ,[l = V aaa ⊂ và D là thuộc tính phân lớp. Ta tiến hành rời rạc hóa thuộc tính a, nghĩa là phân hoạch Va thành các khoảng như sau: 18 { }),[),...,,[),...,,[ 1110 akakaiaiaaaaa rppppplpP === ++ trong đó kaaa ppp <<< ... 10 với k là số giá trị sau khi rời rạc hoá. Mỗi phân hoạch Pa được xác định duy nhất nhờ một tập các điểm cắt t