Luận văn Phụ thuộc hàm xấp xỉ và ứng dụng trong khai phá dữ liệu

; Z. Ví dụ: Cho AB -> C, C -> A, chứng minh BC -> ABC (1) C -> A (theo giả thiết) (2) BC -> AB (áp dụng luật tăng trưởng tăng (1) lên B) (3) AB -> C (theo giả thiết) (4) AB -> ABC (tăng (3)AB) (5) BC -> ABC (bắc cầu (1), (2)). Bổ đề 1: Hệ tiên đề Armstrong là đầy đủ, có nghĩa là nếu F là tập phụ thuộc hàm đúng trên quan hệ r và f : X -> Y là một phụ thuộc hàm được suy dẫn từ F nhờ hệ tiên đề Armstrong thì f đúng trên r Bổ đề 2: Tính hợp : nếu X -> Y và X -> Z thì X -> YZ . Tính tựa bắc cầu : Nếu X -> Y và WY -> Z thì XW -> Z. Tính tách: Nếu X -> Y và Z  Y thì X -> Z. Bao đóng của F được kí hiệu là F+, là tập tất cả các phụ thuộc hàm được suy diễn logic nhờ tiên đề Armstrong, 3 bổ đề trên từ F, nếu F = F+ thì F là họ đầy đủ của các phụ thuộc hàm. Bao đóng của tập thuộc tính (X+) X -> Y là một phụ thuộc hàm suy ra từ F. Khi đó X+ được gọi là bao đóng của tập thuộc tính X nếu X+ là tập tất cả các thuộc tính U được suy dẫn bắt đầu từ tập X. X+F = { A | X -> A  F+ } Thuật toán tìm bao đóng của tập thuộc tính: INPUT: X, F,U OUTPUT: X+ 11 S : = X WHILE có (Z -> Y) thuộc F với Z  S và Y⊄S DO S:= SY ENDWHILE X+ = S Phương pháp: Tính liên tiếp các tập thuộc tính X0, X1, X2,..., Xi BC0: Đặt X0 = X BC1: Nếu tồn tại phụ thuộc hàm f: Y->Z  F sao cho Y X0, Z  U thì X1=X0Z BC2: Tương tư. Until Xi = Xi+1. Kết luận X+ = Xi. Ví dụ: Cho lược đồ quan hê R(U)=(ABCDEM), với U là tập thuộc tính, tập phụ thuộc hàm F={AB -> C, C ->D, A -> E, BC ->EM} Tính bao đóng của (AB)+ BC0: Đặt X0 = AB BC1: Tồn tại A -> E  F, mà A X0, E  U vậy X1=X0E = ABE BC2: Tồn tại AB ->C F, mà AB X1, C U vậy X2=X1C = ABCE BC3: Tồn tại C -> D  F, mà C X2, D  U vậy X3=X2D= ABCDE BC4: Tồn tại BC -> EM  F, mà BC X3, EM  U vậy X4=X3M = ABCDEM BC5: Xét toàn bộ các phụ thuộc hàm thuộc F, thì X5 =X4 Vậy kết luận (AB)+ = X4 = ABCDEM 1.2.3 Định nghĩa hai tập phụ thuộc hàm tương đương: Để khám phá ra một tập hợp các FDs, sử dụng phương pháp phân vùng chia bản ghi của trường hợp này thành các nhóm dựa trên các giá trị khác nhau cho mỗi cột (thuộc tính). Đối với mỗi thuộc tính, số lượng các nhóm là bằng với số các giá 12 trị khác nhau cho các thuộc tính đó. Mỗi nhóm được gọi là một lớp tương đương. Ví dụ, hãy xem xét ví dụ liên quan được hiển thị trong bảng 1, trong trường hợp này, thuộc tính A có giá trị "1" chỉ trong bản ghi số một và hai, do đó, chúng tạo thành một lớp tương đương [1] (A) = [2] (A) = (1,2). Tương tự như vậy, thuộc tính A có giá trị của "2" trong bản ghi 3,4,5 và có giá trị "3" trong bản ghi 6,7,8. Do đó toàn bộ các lớp học tương đương đối với các thuộc tính A là bao gồm ba lớp tương đương như sau: ∏ {A} = {{1, 2}, {3, 4, 5}, {6, 7, 8}}. Các lớp tương đương đối với các thuộc tính kết hợp (B, C), ví dụ: ∏ {B, C} r = {{1}, {2}, {3, 4}, {5}, {6}, {7}, {8}}. Tuple ID A B C D E 1 1 A $ Flower 2 2 1 A Tulip 2 3 2 A $ Daffodil 0 4 2 A $ Flower 0 5 2 B Lily 0 6 3 B $ Orchid 1 7 3 C Flower 1 8 3 C # Rose 1 Bảng 1.2 : Bảng cơ sở dữ liệu quan hệ FD X → Y được suy ra khi và chỉ khi Π (x) lọc Π (Y). Trong ví dụ : thuộc tính A có các bộ sau đây của lớp tương đương: ((T1, T2), (T3, T4, T5), (T6, T7, T8)), và thuộc tính E có các tập sau của lớp tương đương: ((T1, T2), (T3, T4, T5), (T6, T7, T8)). Các lớp tương đương trong thuộc tính E được lọc bởi các lớp tương đương trong thuộc tính A, chúng ta có thể khám phá ra rằng A → E . 1.2.4 Định nghĩa phủ cực tiểu (tối thiểu) 13 Cho tập thuộc tính U và tập phụ thuộc hàm F. Nguời ta nói F là tối thiểu khi và chỉ khi: Vế phải của mỗi phụ thuộc hàm trong F chỉ có một thuộc tính độc nhất. ! X -> A  F tập F - {X -> A} tương đương với F (loại bỏ các phụ thuộc dư thừa). ! X -> A  F, Z  X | F - {X−A}{Z−A} tương đương với F (loại bỏ thuộc tính dư thừa vế trái) Thuật toán: tìm phủ tối thiểu của tập phụ thuộc hàm F, với tập thuộc tính U: INPUT: F, U OUTPUT: G (G là phủ tối thiểu của F). BC1: G = ϕ. Tách tất cả các phụ thuộc hàm f của F thành phụ thuộc hàm mà vế phải chỉ có một t thuộc tính: FOR f  F, f = X -> DO G=G{X−A,AY} BC2: Loại bỏ những phụ thuộc hàm không đầy đủ: WHILE Z  X, Z ≠ X, G ≅ G \ {f}{Z−A} DO G = G \ {f}{Z−A} BC3: Loại bỏ những phụ thuộc hàm dư thừa: FOR  f  G DO IF G \ {f} ≅ THEN G = G \ {f} BC4:RETURN (G). Ta có thể diễn giải lại thuật giải như sau: BC1: Tách tất cả các phụ thuộc hàm của F thành phụ thuộc hàm mà vế phải chỉ có một thuộc tính, Ví dụ: AB –> CD được tách thành AB ->C, AB -> D (luật tách) BC2: Loại bỏ những phụ thuộc hàm không đầy đủ. Khi loại bỏ, ta phân bịêt hai loại phụ thuộc hàm không đầy đủ sau: Loại1: Phụ thuộc hàm mà vế phải là tập con của vế trái ( loại AB -> B) Loai 2: Hai phụ thuộc hàm có vế phải giống nhau, nếu vế trái của phụ thuộc hàm này chứa vế trái của phụ thuộc hàm kia thì ta loại ra khỏi F. 14 Ví dụ: Nếu có ABC -> D và BC - >D thì ta loại ABC -> D khỏi F. BC3: Loại bỏ những phụ thuộc hàm dư thừa: Giả sử hai phụ thuộc hàm có vế phải giống nhau: f1 = X -> A và f2 = Y -> A, lúc đó nếu có A  X+F\ {f1} thì loại f1 ra khỏi F: 1.2.5 Khoá của quan hệ a) Khoá của tập thực thể Là một hoặc một tập các thuộc tính xác định duy nhất một thực thể trong một tập thực thể. b) Khoá của quan hệ Tập các thuộc tính X của một quan hệ R là một khoá nếu. Không tồn tại 2 bộ khác nhau nhưng tất cả các phần tử của X đều giống nhau, và không có tập con thực sự nào của X có tính chất này. Định nghĩa: Cho lược đồ quan hệ R(A1, A2,...,An) và tập phụ thuộc hàm F, X  A1, A2,...,An . Ta nói X là một khoá của R khi và chỉ khi X -> A1, A2,...,An  F+ (tất cả các thuộc tính phụ thuộc vào tập thuộc tính X),  YX | X-> A1A2...An  F+. Sau đây là một số định nghĩa về khoá của quan hệ: Khoá dự tuyển : là khoá của quan hệ. Một quan hệ có thể có nhiều khóa dự tuyển. Khoá chính : là khoá dự tuyển được chọn làm khoá chính của quan hệ. Khoá chính không thể rỗng ( NOT NULL). Siêu khoá : một khoá gọi là siêu khoá nếu như ta bỏ đi một hay nhiều thuộc tính bất kỳ, thì không đảm bảo phần còn lại là khóa. Khoá ngoại : (khoá liên kết ) là một hoặc một tập thuộc tính trong quan hệ R1 nhưng là khoá chính trong quan hệ R2. Một thuộc tính trong lược đồ quan hệ R(U) được gọi là thuộc tính khoá nếu nó là một thành phần của một khoá nào đó của R. Ngược lại người ta gọi là thuộc tính không khoá (thuộc tính thứ cấp). Ví dụ: Cho lược đồ quan hệ R = (ABCD) và tập phụ thuộc hàm F = { A → C, AB → DC}, khoá là {AB}. Khi đó thuộc tính A, B gọi là thuộc tính khoá, còn thuộc tính D, C gọi là thuộc tính không khóa. 15 - Thuật toán tìm tất cả các khoá của một lược đồ quan hệ Bước 1: Tạo tập thuộc tính nguồn TN, tập thuộc tính trung gian TG Bước 2: if TG = ∅ then lược đồ quan hệ chỉ có một khoá K K = TN Kết thúc Ngược lại Qua bước 3 Bước 3: Tìm tất cả các tập con Xi của tập trung gian TG Bước 4; Tìm các siêu khoá Si băng cách :  Xi if ( TNXi )+ = Q+ then Si = TNXi Bước 5: Tìm kháo bằng cách loại bỏ các siêu khoá không tối tiểu Si, Sj  S if Si  Sj then Loại Sj ra khỏi tệp siêu khóa S S còn lại chính là tập khoá cần tìm. 1.3 Phụ thuộc hàm xấp xỉ 1.3.1 Phụ thuộc hàm xấp xỉ loại 1 Đối với một số quan hệ, một số FDs có thể không đúng cho tất cả các bản ghi. Ví dụ đối với hãng ô tô. Được xác định bởi Model thông qua một kỳ vọng phụ thuộc: như Model = 323, chúng ta biết rằng của hãng Mazda với xác suất cao, nhưng có cũng là một cơ hội nhỏ của hãng BMW. Tính xấp xỉ FD được quy định bởi Model →Make. Một phụ thuộc hàm X → A được suy diễn trong r với độ lỗi g3 (X → A) = 1 - (max{|s| | s  r và X → A được suy diễn })/|r|. Với 1 số ε, 0 ≤ ε ≤ 1, chúng ta nói X->A là một phụ thuộc hàm xấp xỉ khi và chỉ khi g3(XA) nhỏ hơn ε. - Biểu diễn hình thức g3 (X → A) = 1 - ∑ c  πX max{ |c’| | c’  πx {A} and c’  c} / |r| - πX: Phân hoạch X 16 Ví dụ: Tuple ID A B C D E 1 1 A $ Flower 2 2 1 A Tulip 2 3 2 A $ Daffodil 0 4 2 A $ Flower 0 5 2 B Lily 0 6 3 B $ Orchid 1 7 1 C Flower 1 8 3 C # Rose 1 Bảng 1.2 : Bảng cơ sở dữ liệu quan hệ Trong bảng cơ sở dữ liệu bên trên. Kiểm tra phụ thuộc hàm AB không được suy diễn. Chúng ta tìm thấy các lớp tương đương: ∏ {A} = {{1, 2,7}, {3, 4, 5}, {6, 8}}. ∏ {B} = {{1}, {2, 3, 4,}, {5, 6}, {7,8}}. A không lọc được B ở các lớp khác nhau. Suy ra AB không đúng. Tuy nhiên A  B có thể đúng ở trong ví dụ, với độ đo là g3. Nếu chúng ta loại bỏ 1 vài bản ghi từ các mối quan hệ, bằng phương pháp loại trừ nhau cho việc tính toán g3. ∏ {A} = {{1, 2}, {3, 4, 5}, {6, 7, 8}}. ∏ {B} = {{1}, {2, 3, 4,}, {5, 6}, {7,8}}. Chúng ta tìm được ∏ {A} {B} = {{1}, {2}, {3,4}, {5}, {6}, {7.8}}. Lớp tương đương trong thuộc tính A {1,2} có kích thước 2 phần tử thành {1}, {2} từ ∏ {A} {B}. Do đó kích thước phần tử lớn nhất của {1}, {2} là 1. Với lớp tương đương {3, 4, 5} trong ∏ {A} thành {3, 4} và {5} từ ∏ {A} {B} . Do đó kích thước phần tử lớn nhất của {3, 4} và {5} là 2. Bổ sung công thức 17 Cuối cùng ở lớp tương đương của { 6, 7, 8} trong ∏A bằng với {6}  {7, 8} trong ∏ {A} {B}. Từ đó hàm g3 ( AB) = 1-(1+2+2)/8=0.375. Như AB = 0.375 vậy có thể nói phụ thuộc hàm AB với độ lỗi 0.375. Quá trình xử lý để khai phá ra tất cả các AFDs là quá trình xử lý tất cả các thuộc tính cho tất cả các tổ hợp. Với 5 thuộc tính {A, B, C, D, E} các tổ hợp được xác lập {, A, B, C, D, E, AB, AC, AD, AE, BC, BD, DE, CD, CE, DE, ABC, ABD, ABE, ACD, ACE, ADE, BCD,BCE, BDE, CDE, ABCD, ABCE, ABDE, ACDE, BCDE, ABCDE} tổng số 25 Bảng 1.3 : Cây khai phá tất cả các AFD. 1.3.2 Phụ thuộc hàm xấp xỉ loại 2 Cho r là một quan hệ trên tập thuộc tính R= {A1, A2...,An} trong đó các thuộc tính A1, A2,...An có thể là thuộc tính định danh(categorical), rời rạc hoặc liên tục(trường số). Đối với những thuộc tính định danh, ta tiến hành thực hiện ánh xạ tất cả các giá trị có thể tới một tập các số nguyên dương liên kề. Định nghĩa: (khoảng cách giữa 2 bộ giá trị trên tập thuộc tính) Với 2 bộ t1, t2  r, ta kí hiệu (t1(X), t2(X)) là khoảng cách giữa t1 và t2 trên tập thuộc tính X  R được xác định như sau: (t1(X), t2(X)) = max(|t1(Ai)- t2(Ai)| / max(|t1(Ai)|,|t2(Ai)|), Ai X): 18 Hàm max(x, y) là hàm chọn ra số lớn nhất trong 2 số x và y; Trường hợp max(|t1(Ai)|- |t2(Ai)|)= 0, tức t1(Ai) = t2(Ai) = 0 thì ta qui ước: |t1(Ai)- t2(Ai)|/ max(|t1(Ai)|, |t2(Ai)|) = 0 Khoảng cách giữa 2 bộ giá trị trên tập thuộc tính có thể coi là hàm số cả các đối số là các bộ giá trị của quan hệ và tập các thuộc tính. Một số tính chất của hàm khoảng cách p(t1(X), t2(X)) Định nghĩa khoảng cách p(t1(X), t2(X)) nêu trên thoả mãn các tính chất của hàm khoảng cách: A1. p(t1(X), t2(X)) >=0 với t1, t2, X tuỳ ý ; A2. p(t1(X), t2(X)) = 0  t1(X) = t2(X) p(t1(X),t2(X)) p(t1(X),t3(X)) + p(t3(X),t2(X)) Và ngoài ra cũng dễ chứng minh các tính chất: Nếu X  Y thì p(t1(X), t2(X))  p(t1(Y), t2(Y)) p(t1(XY), t2(XY)) = max(p(t1(X), t2(X)), p(t1(Y), t2(Y))) Định nghĩa 2 : Phụ thuộc hàm xấp xỉ loại 2 Giả sử X,Y  R và với một số  cho trước, 0   <1, ta nói rằng X xác định hàm Y mức  (hoặc nói rằng giữa X và Y có phụ thuộc hàm xấp xỉ loại 2 mức  ), ký hiệu là X  Y nếu với mọi cặp bộ t1, t2 r, mà p(t1(X), t2(X))   thì ta cũng có p(t1(Y), t2(Y))   Ví dụ: A B C D E 2.5 18 160 25 12 2.51 18 160.5 15 13 3.6 20 320 30 16 3.65 20 323 45 28 4.25 25 641 60 19 Bảng 1.4 : Bảng dữ liệu quan hệ số Ta thấy giữa bộ A, B có mối tương quan với cột C với  = 0.05 ta kiểm tra điều kiện phụ thuộc hàm xấp xỉ 19 với cặp hàng 1,2 ta có p(t1(AB), t2(AB)) = max (|t1(A) - t2(A)|/max(|t1(A)|, |t2(A)|), |t1(B) - t2(B)|/max(|t1(B)|, |t2(B)|) = 0.00394 < 0.05 Tương tự kiểm tra với cặp hàng 3,4 và 5,6 Vậy ta có AB > 0.05C(AB xác định C mức 0.05) Một số tính chất: - Tính chất 1 : Cho r là một qua hệ trên tập thuộc tính R. Một phụ thuộc hàm đúng trên r cũng là phụ thuộc hàm xấp xỉ loại 2 với mức  tuỳ ý (0   <1) đúng trên r Tính chất này dễ dàng suy theo định nghĩa của phụ thuộc hàm xấp xỉ loại 2 - Tính chất 2 : Cho r là một quan hệ trên R; X, Y  R, 1, 2, là 2 số sao cho 0  1  2 1Y và X > 2Y là 2 phụ thuộc hàm xấp xỉ loại 2 mức 1 và mức 2 giữa X và Y trên r, khi đó nếu X > 1Y đúng trên r thì X > 2Y cũng đúng trên r - Tính chất 3 : Tính phản xạ Nếu Y  X khi đó X > Y là phụ thuộc hàm xấp xỉ loại 2 với mức  tuỳ ý (0   <1) - Tính chất 4 : Tính bắc cầu Nếu X > Y và Y > Z thì X > Z - Tính chất 5 : Tính gia tăng Với mọi X, Y, Z  R và mức  nào đó, nếu X > Y thì XZ > YZ. 1.3.2.1 Xây dựng thuật toán kiểm tra phụ thuộc hàm xấp xỉ loại 2 Giả sử cho r = {t1, t2,.....,tn } là một quan hệ trên tập thuộc tính R và X, Y  R, với một số  cho trước ( 0   <1). Ta sẽ xây dựng thuật toán để xác định xem quan hệ r có thoả phụ thuộc hàm xấp xỉ loại 2 mức  : X > Y hay không ? Ta xét hệ xấp xỉ Er được xây dựng như sau : Er = { E()i,j = { a:| ti(a) - tj(a)| /max(|ti(a)|, |tj(a)|)  ; a  R}; ti, tj  r; 1  i < j  m} Ta gọi tập Er là một hệ xấp xỉ mức  của r Ta có mệnh đề sau: Mệnh đề 1 (Điều kiện để quan hệ thoả phụ thuộc hàm xấp xỉ loại 2) 20 Giả sử cho r = {t1, t2,...,tn} là một quan hệ trên tập thuộc tính R và X, Y  R với một số  cho trước ( 0   <1); Er là một hệ xấp xỉ mức  thoả phụ thuộc hàm xấp xỉ loại 2 mức :X > Y khi và chỉ khi :  E()i,j  Er : ( X E()i,j  Y  E()i,j ) 1.3.2.2 Ứng dụng trong thực tế hoạt động kiểm toán Hoạt động kiểm toán của kiểm toán nhà nước gắn liền với việc phát hiện ra những hiện tượng bất thường hoặc ngoại lai trong tập dữ liệu thông tin của doanh nghiệp hoặc đơn vị được kiểm toán. Trên cơ sở các hiện tượng bất thường nay, kiểm toán viên sẽ tiến hành các biện pháp nghiệp vụ để xem xét liệu có sự gian lận hoặc sai sót hay không và tiến hành xử lý. Ví dụ : THANG TONG_CP CHI_NVL TIENLUONG VAT 1 1,450,267,320 580,271,928 507,823,562 41,019,035 2 1,465,890,000 586,521,000 513,291,500 41,456,470 3 1,500,540,000 600,381,000 525,419,000 42,426,670 4 1,510,567,000 604,391,800 528,928,450 42,707,426 5 1,515,680,000 680,437,000 530,718,000 48,030,590 Bảng 1.5: Bảng cơ sở dữ liệu kiểm toán Trong trường hợp này áp dụng thuật toán xấp xỉ loại 2 chọn  = 0.01 (việc chọn giá trị  tuỳ thuộc vào điều kiện thực tế và ý kiến của các chuyên gia kinh tế) Xây dựng tập bằng nhau Er cho bảng trên ta được: E()1,2 = TONG_CP, CHI_NVL, TIENLUONG,VAT E()1,3 = E()1,4 = E()1,5 = E()2,3 = E()2,4 = E()2,5 =  E()3,4 = TONG_CP, CHI_NVL, TIENLUONG,VAT E()3,5 = TONG_CP,TIENLUONG E()4,5 = TONG_CP,TIENLUONG 21 Chúng ta thấy rằng trong E()3,5 và E()4,5 có chứa TONG_CP nhưng không chứa các thuộc tính CHI_NVL, VAT. Như vậy giữa tháng 3 và tháng 5 có sự bất thường giữa TONG_CP và CHI_NVL.; giữa TONG_CP và VAT Tương tự giữa tháng 4 và tháng 5: Khi kiểm tra kỹ chúng ta nhận thấy rằng trong tháng 5 có sự kê khai sai về chi phí nguyên vật liệu, cũng như thuế VAT (so với tháng 3, tháng 4 cùng tổng chi phí xấp xỉ như nhau(chênh lệch nhỏ hơn 1%) nhưng mức chênh lệch giữa chi phí NVL và thuế VAT lớn hơn nhiều(chênh lệch hơn 5%). Có thể đã có sự gian lận hoặc sai xót xảy ra. 1.3.3 Bao đóng xấp xỉ Đặt A + = { a: A  {a}  F+ } được gọi là bao đóng xấp xỉ của A trên s. Có thể thấy rằng A B  F+ nếu và chỉ nếu B  A+ . 1.3.3.1 Thuật toán tìm bao đóng xấp xỉ Thuật toán 1: Vào: sz = , ở đây R={ a1,..., an} tập hữu hạn các thuộc tính, Fz tập các phụ thuộc hàm xấp xỉ, A  R. Ra: Az+ bao đóng của A đối với Fz Thuật toán thực hiện như sau: Tính các tập thuộc tính A0, A1,... theo qui tắc: A0 = A Ai = Ai-1  {a} sao cho  ( C D)  F, {a}  Y và C  Ai-1 Vì A = A0  ... Ai  R, và R hữu hạn nên tồn tại một chỉ số i nào đó mà Ai = Ai+1, khi đó thuật toán dừng và Az+ = Ai Chứng minh: Ta có thể thấy rằng, R la hữu hạn các phần tử, F, là hữu hạn nên tồn tại chỉ số i sao cho Ai = Ai+1. Do vậy chúng ta có thể thấy độ phức tạp thời gian của thuật toán này là đa thức theo kích thước của sz. 22 Ví dụ: Cho bảng quan hệ sau: A B C D E 2.5 18 160 19 18 2.51 18 160.5 21 20 3.6 20 320 22 20 3.65 20 323 20 18 Ta xây dựng được một sơ đồ quan hệ với tập thuộc tính là R= và tập phụ thuộc xấp xỉ F={AB >0.05 C, AB >0.05 E, E >0.05 D} với mức xấp xỉ của  = 0.05. Áp dụng thuật toán tính bao đóng xấp xỉ trên ta dễ dàng thu được bao đóng xấp xỉ của AB = {ABCDE} 1.3.4 Khoá xấp xỉ Giả sử s = là một sơ đồ quan hệ xấp xỉ. Khi đó A là một khoá xấp xỉ của s nếu A R  F+ . Chúng ta gọi A là một khoá tối tiểu xấp xỉ của s nếu: A là một khoá xấp xỉ của s. Bất kì một tập con thực sự của A không là khoá xấp xỉ của s. 1.3.4.1 Thuật toán tìm khoá xấp xỉ của sơ đồ quan hệ Thuật toán 2: Vào: Sơ đồ quan hệ s = trong đó: F là tập phụ thuộc hàm xấp xỉ và R = { a1,..., an} là tập các thuộc tính Ra: K là một khoá xấp xỉ của s Thuật toán thực hiện như sau: Tính liên tiếp các tập thuộc tính K0, K1....,Kn như sau: K0 = R = { a1,..., an} 23 Ki = Ki-1, nếu Ki-1 - {ai} R F+, và Ki-1- {ai}, ngược lại... K = Kn là khoá tối tiểu xấp xỉ của s Chứng minh: Ta có thể thấy rằng R là hữu hạn các thuộc tính, F là hữu hạn nên sau n bước liên tiếp sẽ tồn tại Ki = Ki+1. Khi đó tồn tại một tập Ki sao cho: Ki R  F+ và bất kì một tập con nào của Ki đều không xác định R. Ví dụ: Cho sơ dồ quan hệ với tập thuộc tính là R= {A, B, C, D, E} và tập phụ thuộc xâp xỉ F={AB >0.05 C, AB >0.05 E, E >0.05 D} với mức xấp xỉ của  = 0.05. Áp dụng thuật toán trên ta có: Bước 1: Đặt K0 = R= {A, B, C, D, E} Bước 2: Tính K1 Xét K0\A = {B, C, D, E} Tính bao đóng xấp xỉ mức 0.05 của {B, C, D, E}.{B, C, D, E}+0.05 = {B, C, D, E} R, do vậy K1 =K0= {A, B, C, D} Bước 3: Tương tự ta tính được K2= K0; K3 = {A, B, D, E}; K4= {A, B, E}; K5= {A, B}. Do vậy, khoá xấp xỉ K của sơ đồ quan hệ s= là K= K5= {A, B} Dạng chuẩn 2 - NF Một quan hệ ở dạng chuẩn 2NF nếu quan hệ đó + Là 1 NF + Các thuộc tính không khoá phải phụ thuộc hàm xấp xỉ đầy đủ vào khoá chính. Dạng chuẩn 3 - NF + Là 2 NF + Các thuộc tính không khoá phải phụ thuộc xấp xỉ trực tiếp vào khoá chính. 24 Dạng chuẩn BCNF + Là 3NF + Không có thuộc tính khoá mà phụ thuộc hàm xấp xỉ vào thuộc tính không khoá. Thuật toán kiểm tra BCNF Bước 1 : Xác định khoá Bước 2 : Kiểm tra thuộc tính không khoá phải phụ thuộc hàm xấp xỉ đầy đủ vào khoá chính Bước 3 : Kiểm tra các thuộc tính không khoá phải phụ thuộc xấp xỉ trực tiếp vào khoá chính. Bước 4 : Với mỗi thuộc tính khoá kiểm tra có phụ thuộc hàm xâp xỉ vào thuộc tính khoá không. Nếu phụ thuộc thì luợc đồ quan hệ không thuộc dạng chuẩn BCNF Ví dụ 1: Cho lược đồ quan hệ U = {A, B, C, D} và tập các phụ thuộc hàm xấp xỉ với mức xấp xỉ  (A~>B, B~> A, AC ~>D) Xác định : AC hoặc BC là khoá Nếu AC là khoá ta có B~> A(thuộc tính khoá phụ thuộc hàm xấp xỉ và thuộc tính không khoá). Nếu BC là khoá ta có A~>B(thuộc tính khoá phụ thuộc hàm xấp xỉ và thuộc tính không khoá). Như vậy : Lược đồ U thuộc dạng chuẩn 3NF 25 CHƯƠNG 2 : XÂY DỰNG CÂY QUYẾT ĐỊNH 2.1 Đặt vấn đề Một trong những đích khai phá dữ liệu trong thực tế nhằm đạt đến là mô tả các mẫu dữ liệu, mỗi một sự mô tả là thể hiện những tri thức được khai phá. Sự phân lớp là quá trình nhằm đến một trong những mục đích ấy. Cây quyết định là một trong những giải pháp trực quan và hữu hiệu để mô tả quá trình phân lớp dữ liệu. Do cây quyết định rất hữu dụng nên đã có nhiều nghiên cứu để xây dựng nó mà nổi bật là các thuật toán học quy nạp như CATD, ID3, C45,.... Xây dựng cây quyết định có khả năng dự đoán cao, là một trong những mục tiêu quan trọng của khai phá dữ liệu. Để xây dựng được một cây quyết định có hiệu quả thì ngoài các thuật toán học quy nạp tốt, việc chọn mẫu huấn luyện đóng một vai trò đáng kể. Khi chọn mẫu huấn luyện, sự phụ thuộc tự nhiên giữa các thuộc tính dữ liệu trong mẫu cần phải được đề cập và ứng dụng để loại trừ nó, nhằm nâng cao hiệu quả cho cây được xây dựng [3, 5, 8, 9]. Hơn nữa, có nhiều trường hợp trong thực tế, các nhóm thuộc tính mặc dầu giữa chúng không có sự phụ thuộc theo định nghĩa của phụ thuộc hàm thông thường mà lại phụ thuộc theo kiểu tương quan hàm số nào đó, ta gọi là phụ thuộc hàm xấp xỉ. Các nhóm thuộc tính này làm phức tạp việc xác định mẫu nên tăng chi phí cho quá trình huấn luyện, quan trọng hơn là chúng gây nhiễu nên cây được xây dựng không có hiệu quả cao. Ở đây, chúng ta sẽ xét đến các phụ thuộc dữ liệu loại này nhằm xây dựng cây quyết định có khả năng dự đoán cao. 2.2 Bảng quyết định 2.2.1 Hệ thống thông tin 2.2.1.1 Định nghĩa Hệ thống thông tin là một cặp A = (U, A), với U là tập hữu hạn, khá rỗng, đượ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 u  U và a A, ta ký hiệu u(a) là giá trị của đối tượng u tại thuộc tính a. Nếu gọi Ia là tập tất cả các giá trị của thuộc tính a, thì u(a)  Ia với mọi u  U. Bây giờ, nếu B = {b1, b2,…,bk}  A là một tập con các thuộc tính thì ta sẽ ký hiệu bộ các giá trị u(bi) bởi u(B). Như vậy, nếu u và v là hai đối tượng, thì ta sẽ viết u(B) = v(B) nếu u(bi) = v(bi) với mọi i = 1,…,k. 26 2.2.1.2 Quan hệ không phân biệt được Cho hệ thống thông tin A = (U, A). Với mỗi tập con các thuộc tính B  A, tồn tại một quan hệ hai ngôi trên U, ký hiệu IND(B), xác định bởi: IND(B) = {(u,v)U×U u(B) = v(B)} IND(B) được gọi là quan hệ B – không phân biệt được. Để kiểm chứng được rằng đây là quan hệ tương đương trên U. Với V  U, ta ký hiệu IND (B/V) là quan hệ tương đương trên V, cảm sinh bởi IND(B), tức là: IND(B/V) = {(u,v)U×U u(B) = v(B)} Nếu (u,v)  IND(B) thì hai đối tượng u và v không phân biệt được bởi các thuộc tính trong B. Lớp tương đương chứa phần tử u được ký hiệu [u]B. Khi đó quan hệ IND(B) được xác định hoàn toàn bởi các lớp tương đương [u]B, u U. Tập hợp thương của quan hệ IND(B) được ký hiệu [IND(B)] hay đơn giản U/B, tức là [ IND(B)] = U/B = {[u]B / u U} và tập hợp thương của quan hệ IND(B/V) là [ IND(B/V)] hay V/B. Ví dụ U / {Màu sắc} = {{u1, u2, u6}, {u3, u5}, {u4, u7}} U / {Kích thước} = {{u1, u5}, {u3, u4}, {u2, u6, u7}} U / {Hình dáng} = {{u1, u2, u6}, {u3, u4}, {u5, u7}} U / {Màu sắc, Hình dáng} = {{u1, u2, u6}, {u3}, {u4}, {u5}, {u7}} Màu sắc Kích thước Hình dáng Xanh To Tròn Xanh Nhỏ Tròn Vàng Vừa Vuông Đỏ Vừa Vuông Vàng To Tam giác Xanh Nhỏ Tròn Đỏ Nhỏ Tam giác Hình 2.1: Bảng dữ liệu các đồ chơi 27 Như vậy các đồ chơi u1, u2 không phân biệt được về màu sắc và hình dáng, nhưng phân biệt được về kích thước. Tương tự, các đồ chơi u3, u4 không phân biệt nhau về kích thước và hình dáng, nhưng phân biệt được về màu sắc, v.v… Với một tập thuộc tính B cho trước, chúng ta có các lớp tương đương của quan hệ IND(B), thế thì một tập đối tượng V có thể diễn đạt thông qua: Cách thứ nhất là cho tương ứng bởi “miền trong” Cách thứ hai có thể xấp xỉ bởi “bao đóng” của V. Hai giá trị xấp xỉ này được gọi là tương ứng là B-xấp xỉ dưới và B-xấp xỉ trên của V, ký hiệu là lượt là BV và BV cụ thể các tập xấp xỉ này được xác định như sau:    ,BBV u U u V     ,BBV u U u V    Với các xấp xỉ trên, ta gọi B-miền biên của V là tập   \ ,BBN V BV BV và B- miền ngoài của V là tập \U BV Dễ thấy B-miền biên của V là tập chứa các đối tượng không chắc chắn thuộc hay không thuộc V, còn B-miền ngoài của V chứa các đối tượng chắc chắn không thuộc V. Với ký hiệu tập thương của quan hệ tương đương IND(B) trên U là U/B, các xấp xỉ trên và dưới của V có thể viết lại: BV =  {W U / B : W  V} BV =  {W U / B : W  V ≠ }. Bây giờ nếu B, D  A ta sẽ gọi B-miền khẳng định của D là tập được xác định như sau:     / B V U D POS D BV   U Rõ rằng  BPOS D là tập tất cả đối tượng u sao cho với mọi v  U mà u(B) = v(B) ta đều có u(D) = v(D). Nói cách khác,  BPOS D = {u  U / [u]B  [u]D} 28 Ví dụ : U Đau đầu Thân nhiệt Cảm cúm u1 Có Bình thường Không u2 Có Cao Có u3 Có Rất cao Có u4 Không Bình thường Không u5 Không Cao Không u6 Không Rất cao Có u7 Không Cao Có u8 Không Rất cao Không Bảng 2.2: Bảng các triệu chứng của bệnh nhân Các lớp không phân biệt được bởi B = {Đau đầu, thân nhiệt} là: {u1}, {u2}, {u3}, {u4}, {u5, u7}, {u6, u8}. Đặt V = {u / u(Cảm cúm) = Có} = {u2, u3, u6, u7}. Lúc đó, BV = {u2, u3} và BV = {u2, u3, u6, u7, u5, u8} . Như vậy, B-miền biên của V là tập hợp BNB(V) = {u5, u6, u7, u8}. Nếu đặt D = {Cảm cúm} thì U / D = {V1 = {u1, u4, u5, u8}; V2 = {u2, u3, u6, u7}}, BV1 = {u1, u4}; BV2 = {u2, u3},      1 2 3 4 / , , ,B V U D POS D BV u u u u   U 2.2.2 Bảng quyết định 2.2.2.1 Định nghĩa Một lớp đặc biệt của các hệ thống thông tin có vai trò quan trọng trong nhiều ứng dụng là bảng quyết định. Bảng quyết định là một hệ thống thông tin T với tập thuộc tính A được chia thành hai tập khác rỗng rời nhau C và D, lần lượt được gọi là tập thuôc tính điều kiện và tập thuộc tín quyết định. Tức là T = (U, C  D) với C  D = . Trong trường hợp không sợ bị nhầm lẫn, người ta ký hiệu T = (C  D). Bảng quyết định là mô hình thường gặp trong thực tế, khi mà giá trị dữ liệu tại các thuộc tính có điều kiện có thể cung cấp cho ta thong tin về giá trị của thuộc tính quyết định. Bảng quyết định được gọi là nhất quán nếu D phụ thuộc hàm vào C, tức 29 là với mọi u, v  U, u(C) = v(C) kéo theo u(D) = v(D). Ngược lại thì gọi là không nhất quán hay mâu thuẫn. Dễ thấy bảng quyết định là nhất quán khi và chỉ khi POS C(D) = U. Trong trường hợp bảng không nhất quán thì POS C(D) chính là tập con cực đại của U sao cho phụ thuộc hàm CD đúng. 2.2.2.2 Rút gọn thuộc tính Trong bảng quyết định, các thuộc tính điều kiện được phân thành ba nhóm: thuộc tính lõi, thuộc tính rút gọn và thuộc tính không cần thiết. Thuộc tính lõi là thuộc tính cốt yếu, không thể thiếu trong việc phân hoạch chính xác tập dữ liệu. Thuộc tính không cần thiết là những thuộc tính dư thừa, nghĩa là có thể loại bỏ một thuộc tính như vậy (không phải là tất cả!) mà không ảnh hưởng đến việc phân lớp dữ liệu. Thuộc tính của tập rút gọn nằm giữa hai tập thuộc tính trên, với một tổ hợp thuộc tính nào đó, nó là thuộc tính dư thừa và với một tổ hợp các thuộc tính khác nó có thể là cốt yếu. Cho T = (U, C  D) là một bảng quyết định, thuộc tính c  C được gọi là không cần thiết trong bảng quyết định T nếu POS C(D) = POS(C\{c})(D). Nói cách khác, c  C là không cần thiết khi và chỉ khi trên POS C(D) phụ thuộc hàm C\{c}  D nghiệm đúng; Ngược lại, c được gọi là cần thiết. Bảng quyết định T được gọi là độc lập nếu mọi thuộc tính c  C đều cần thiết. Tập tất cả các thuộc tính cần thiết trong T được gọi là lõi và được ký hiệu Core(C). Lúc đó, một thuộc tính cần thiết còn được gọi là thuộc tính lõi. Trong trường hợp không sợ bị nhầm lẫn ta có thể viết Core thay cho Core(C). Tập các thuộc tính R  C được gọi là một rút gọn của tập thuộc tính điều kiện C nếu T = (U, R  D) là độc lập và POSR(D) = POSC(D). Nói cách khác, R là tập rút gọn nếu nó là tập tối thiểu thỏa mãn POSR(D) = POSC(D). Rõ rằng là có thể có nhiều tập rút gọn của C. Ta ký hiệu Red (C) là tập tất cả rút gọn của C trong T. Một thuộc tính là cần thiết khi và chỉ khi nó thuộc vào mọi tập rút gọn của C. Điều đó được thể hiện trong mệnh đề sau. Mệnh đề 1.1 [2, 9, 11]    Re or R d C C e C R   I Ví dụ 1.3 Xét bảng quyết định về bệnh cúm cho ở Bảng 2.3. Bảng này có hai tập rút gọn là R1 = {Đau cơ, Thân nhiệt} (xem Bảng 2.4) và R2 = {Đau đầu, Thân nhiệt} (xem Bảng 2.5). Như vậy tập lõi là Core = {Thân nhiệt} và Thân nhiệt là 30 thuộc tính cần thiết duy nhất. Các thuộc tính Đau đầu, Đau cơ đều không cần thiết theo nghĩa là, từ bảng dữ liệu, có thể loại bỏ một trong hai thuộc tính này mà vẫn chuẩn đoán đúng bệnh. Tức là POS{Đau cơ, than nhiệt}({Cảm cúm}) = POSC({Cảm cúm}), POS{Đau đầu, than nhiệt}({Cảm cúm}) = POSC({Cảm cúm}), Bảng 2.3: Bảng quyết định về cúm Hình 2.4: Bảng rút gọn thứ nhất của hệ thống bệnh cúm (R1) U Đau đầu Đau cơ Thân nhiệt Cảm cúm u1 Có Có Bình thường Không u2 Có Có Cao Có u3 Có Có Rất cao Có u4 Không Có Bình thường Không u5 Không Không Cao Không u6 Không Có Rất cao Có U Đau cơ Thân nhiệt Cảm cúm u1, u4 Có Bình thường Không u2 Có Cao Có u3, u6 Có Rất cao Có u5 Không Cao Không 31 U Đau đầu Thân nhiệt Cảm cúm u1 Có Bình thường Không u2 Có Cao Có u3 Có Rất cao Có u4 Không Bình thường Không u5 Không Cao Không u6 Không Rất cao Có Bảng 2.5 : Bảng rút gọn thứ hai của hệ thống bệnh cúm (R2) 2.3 Cây quyết định 2.3.1 Xây dựng cây quyết định Trong lý thuyết quyết định (chẳng hạn quản lí rủi ro), một cây quyết định là một đồ thị của các quyết định và các hậu quả có thể của nó (bao gồm rủi ro và hao phí tài nguyên). Cây quyết định được sử dụng để xây dựng một kế hoạch nhằm đạt được mục tiêu mong muốn. Các cây quyết định được dùng để hỗ trợ quá trình ra quyết định. Cây quyết định là một dạng đặc biệt của cấu trúc cây. Trong lĩnh vực học máy, cây quyết định là một kiểu mô hình dự báo , nghĩa là một ánh xạ từ các quan sát về một sự vật/hiện tượng tới các kết luận về giá trị mục tiêu của sự vật/hiện tượng. Mỗi một nút trong tương ứng với một biến; đường nối giữa nó với nút con của nó thể hiện một giá trị cụ thể cho biến đó. Mỗi nút lá đại diện cho giá trị dự đoán của biến mục tiêu, cho trước các giá trị của các biến được biểu diễn bởi đường đi từ nút gốc tới nút lá đó. Kỹ thuật học máy dùng trong cây quyết định được gọi là học bằng cây quyết định, hay chỉ gọi với cái tên ngắn gọn là cây quyết định. Học bằng cây quyết định cũng là một phương pháp thông dụng trong khai phá dữ liệu. Khi đó, cây quyết định mô tả một cấu trúc cây, trong đó, các lá đại diện cho các phân loại còn cành đại diện cho các kết hợp của các thuộc tính dẫn tới phân loại đó. Một cây quyết định có thể được học bằng cách chia tập hợp nguồn thành các tập con dựa theo một kiểm tra giá trị thuộc tính . Quá trình này được lặp lại một cách đệ qui cho mỗi tập con dẫn xuất. Quá trình đệ qui hoàn thành khi không thể 32 tiếp tục thực hiện việc chia tách được nữa, hay khi một phân loại đơn có thể áp dụng cho từng phần tử của tập con dẫn xuất. Một bộ phân loại rừng ngẫu nhiên sử dụng một số cây quyết định để có thể cải thiện tỉ lệ phân loại. Cây quyết định cũng là một phương tiện có tính mô tả dành cho việc tính toán các xác suất có điều kiện. Cây quyết định có thể được mô tả như là sự kết hợp của các kỹ thuật toán học và tính toán nhằm hỗ trợ việc mô tả, phân loại và tổng quát hóa một tập dữ liệu cho trước. Dữ liệu được cho dưới dạng các bản ghi có dạng: (x, y) = (x1, x2, x3..., xk, y) Biến phụ thuộc y là biến mà chúng ta cần tìm hiểu, phân loại hay tổng quát hóa. x1, x2, x3 ... là các biến sẽ giúp ta thực hiện công việc đó. Ví dụ Cho mẫu huấn luyện như ở bảng 1 với thuộc tính quyết định là thuộc tính “MuaÔtô”. Chúng ta hãy dự đoán khả năng mua ô tô cho một khách hàng nào đó. Họ và tên Thành phần GĐ Công việc Phụ cấp công việc Khu vực Phụ cấp khu vực Thu nhập Mua ôtô Phù Trọng Hưng Khá Bác sỹ 80 Thị xã 20 4500 Không Dương Quang Khai Trung bình Bác sỹ 82 Thị xã 20 4000 Không Trần Trọng Minh Khang Khá Giám đốc 110 Thị xã 20 5200 Có Nguyễn Ngọc Duy Khuê Khá Bán hàng 50 T.Phố loại 2 20 2300 Có Lê Trung Kiên Khá Bán hàng 51 T.Phố loại 1 30 5000 Có Thái Xuân Lãm Trung bình Bán hàng 49 T.Phố loại 1 30 6000 Không 33 Trần Thị Kim Liễu Trung bình Giám đốc 110 T.Phố loại 1 30 6500 Có Đỗ Khánh Long Khá Bác sỹ 80 T.Phố loại 2 20 2350 Không Trần Công Mẫn Khá Bác sỹ 81 T.Phố loại 1 30 6000 Có Võ Quang Mẫn Khá Bán hàng 49 T.Phố loại 2 20 5000 Có Nguyễn Văn Nam Trung bình Bác sỹ 83 T.Phố loại 2 20 6000 Có Trần Thị Hạnh Nguyên Trung bình Giám đốc 112 T.Phố loại 2 20 4000 Có Cao Thọ Ninh Khá Giám đốc 108 Thị xã 20 5500 Có Nguyễn Bảo Phong Trung bình Bán hàng 50 T.Phố loại 2 20 5000 Không Bảng 2.7 Bảng dữ liệu điều tra khách mua ô tô Để xây dựng cây quyết định, tại mỗi nút của cây thì các thuật toán đều tính lượng thông tin nhận được trên các thuộc tính và chọn thuộc tính tương ứng có lượng thông tin tối đa làm nút phân tách trên cây - tức là các thuộc tính chia tập mẫu thành các lớp mà mỗi lớp có một phân loại duy nhất hay ít nhất thuộc tính phải có triển vọng đạt được điều này, nhằm để đạt được cây có ít nút nhưng có khả năng dự đoán cao. Như thế, thuộc tính X được chọn phải có có lượng thông tin đạt được tối đa đối với mẫu M trên thuộc tính quyết định Y, tức là X được chọn phải đạt: Gain(X,Y,M) = max{gain(Xi,Y,M), i = 1,…,n} Do đối với các thuộc tính riêng biệt X ta phải tính lượng thông tin nhận được cho X tại mỗi giá trị xi nhằm xác định vị trí tốt nhất x* cho việc phân 34 xi E(PhụCấp) Gain(PhụCấp) 112 0,8926 0,0477 110 0,7810 0,1593 108 0,7143 0,2260 83 0,6371 0,3032 82 0,8500 0,0903 81 0,7885 0,1518 80 0,9371 0,0032 51 0,9152 0,0251 50 0,9300 0,0103 lớp. Giá trị x* được chọn phải có có lượng thông tin đạt được tối đa đối với mẫu M trên thuộc tính quyết định Y, tức là x* được chọn phải đạt: Gain(x*|X,Y,M) = max{gain(xi|X,Y,M), i ={1,…,n} [8, 10]. log)( 2 1 i c i i ppSEntropy    )( || || )(),( )( v AValuesv v SEntropy S S SEntropyASGain    Entropy([9+, 5-]) = - (9/14) log2 (9/14) - (5/14) log2 (5/14) = 0.940 Tại bước lặp đầu tiên ta có: Lượng thông tin của cây đối với Y trên M là S(Y|M1) = 0,940 Gain(CôngViệc,Y,M1) = 0,246 Gain(ThànhPhầnGĐ,Y,M1) = 0,048 Gain(SốNgườiGĐ,Y,M1) = 0,029 35 Xi E(ThuNhậpGĐ) Gain(ThuNhậpGĐ) 6500 0,8926 0,0477 6000 0,9253 0,0150 5500 0,8950 0,0453 5200 0,8500 0,0903 5000 0,8380 0,1022 4500 0,9152 0,0251 4000 0,9300 0,0103 2350 0,8926 0,0477 Tương tự cho các thuộc tính còn lại, ta tìm được hàm Gain(xi|PhụCấp,Y,M1) tại giá trị x* = 83 là lớn nhất nên ta chọn để làm điểm phân tách cây tại bước này. Cây quyết định thu được cho ở hình 2. Bảng 2.8: Cây quyết định tại bước 1 trên thuộc tính phụ cấp 36 Hình 3 : Cây quyết định sau bước 2 Bảng 2.9: Cây quyết định tại bước 2 Kết luận là cây quyết định giúp ta biến một biểu diễn dữ liệu phức tạp thành một cấu trúc đơn giản hơn rất nhiều. 2.3.2 Ưu điểm của cây quyết định So với các phương pháp khai phá dữ liệu khác, cây quyết định là phương pháp có một số ưu điểm: Cây quyết định dễ hiểu. Người ta có thể hiểu mô hình cây quyết định sau khi được giải thích ngắn. Việc chuẩn bị dữ liệu cho một cây quyết định là cơ bản hoặc không cần thiết. Các kỹ thuật khác thường đòi hỏi chuẩn hóa dữ liệu, cần tạo các biến phụ (dummy variable) và loại bỏ các giá trị rỗng. Cây quyết định có thể xử lý cả dữ liệu có giá trị bằng số và dữ liệu có giá trị là tên thể loại. Các kỹ thuật khác thường chuyên để phân tích các bộ dữ liệu chỉ gồm một loại biến. Chẳng hạn, các luật quan hệ chỉ có thể dùng cho các biến tên, trong khi mạng nơ-ron chỉ có thể dùng cho các biến có giá trị bằng số. Cây quyết định là một mô hình hộp trắng. Nếu có thể quan sát một tình huống cho trước trong một mô hình, thì có thể dễ dàng giải thích điều kiện đó bằng logic Boolean. Mạng nơ-ron là một ví dụ về mô hình hộp đen, do lời giải thích cho kết quả quá phức tạp để có thể hiểu được. Có thể thẩm định một mô hình bằng các kiểm tra thống kê. Điều này làm cho ta có thể tin tưởng vào mô hình. Cây quyết định có thể xử lý tốt một lượng dữ liệu lớn trong thời gian ngắn. Có thể dùng máy tính cá nhân để phân tích các lượng dữ liệu lớn trong một thời gian 37 đủ ngắn để cho phép các nhà chiến lược đưa ra quyết định dựa trên phân tích của cây quyết định. Mở rộng cây quyết định thành đồ thị quyết định Trong cây quyết định, mọi đường đi từ nút gốc đến nút lá được tiến hành bằng các phép hội (AND). Trong đồ thị quyết định, có thể dùng các phép tuyển (OR) để kết nối ghép hai hay nhiều đường lại với nhau. Phần bù của cây quyết định là phân tích hình thái học (Morphological Analysis). 2.4 Ảnh hưởng của phụ thuộc hàm, phụ thuộc hàm xấp xỉ khi xây dựng cây quyết định Cho mẫu huấn luyện M gồm có m thuộc tính, n bộ. Mỗi thuộc tính X  M có các giá trị là {x1, x2,....,xn}. Thuộc tính quyết định trong mẫu được đánh dấu là Y còn các thuộc tính còn lại gọi là thuộc tính dự đoán. Với thuộc tính X = {x1, x2,....,xn}, ta ký hiệu |X| là số các giá trị khác nhau của của tập {x1, x2,....,xn} gọi là lực lượng của X; số lần xuất hiện giá trị xi trong X ký hiệu là |xi|. Giá trị của bộ r trên thuộc tính X được ký hiệu là r|X. Mệnh đề 1. Trên mẫu M với thuộc tính quyết định Y, nếu có phụ thuộc hàm X1 -> X2 và nếu đã chọn X1 làm nút phân tách trên cây thì mọi nút con của nó sẽ không nhận X2 làm nút phân tách. Mệnh đề 2. Trên mẫu M với thuộc tính quyết định Y, nếu có phụ thuộc hàm X1→ X2 thì lượng thông tin nhận được trên X1 không nhỏ hơn lượng thông tin nhận được trên X2. Mệnh đề 3: Nếu thuộc tính X là khoá của mẫu M thì loại X ra khỏi M để thu được cây quyết định có khả năng dự đoán tốt hơn. 38 Chương 3 : Thử nghiệm và đánh giá 3.1 Thuật toán TANE 3.1.1 Mô tả thuật toán Với L là cây cần khai phá AFD L1:= {{A} | A  R}, L2 được tính từ L1, L3 được tính từ L2... C là tất cả các tổ hợp tại mức Ll nào đó C+(X) = { A  R | B  X, X \ {A, B} → B không được suy diễn}. 1. L0:= {Ө} 2. C+( Ө):= R 3. L1:= {{A} | A  R} 4 . ℓ:= 1 5 . while Ll ≠ Ө 6 . COMPUTE-DEPENDENCIES(Ll ) 7 . PRUNE(Ll) 8 . Ll+1:= GENERATE-NEXT-LEVEL(Ll ) 9 . ℓ:= ℓ + 1 Giải thích : Giải thích : 1 L0 khởi tạo bằng rỗng 2 C+(0) bằng R 3 L1 bằng tất cả các thuộc tính trong R 4 ℓ := 1 5 while Ll # rỗng 6 Tính toán các phụ thuộc hàm trong (Ll) 7 Prune(Ll) lọc Ll để tìm kiếm và xoá các phụ thuộc hàm ko cần thiết 8 Ll+1 bằng xây dựng các phụ thuộc hàm cho mức tiếp theo 9 l := l + 1 39 Thủ tục Procedure COMPUTE-DEPENDENCIES(Lℓ ) 1 for each X  Ll do 2 C+(X):=∩AX C+(X \ {A}) 3 for each X  Ll do 4 for each A  X ∩ C+(X) do 5 if X \ {A} → A is valid then 6 output X \ {A} → A 7 remove A from C+(X) 8 remove all B in R \ X from C+(X) Thủ tục Procedure PRUNE(L) 1 for each X  Lℓ do 2 if C+(X) = Ө do 3 delete X from Lℓ 4 if X is a (super)key do 5 for each A  C+(X) \ X do 6 if A :=∩ bX C+(X  {A} \ {B}) then 7 output X → A 8 delete X from Lℓ 3.1.2 Độ phức tạp Với một bảng cơ sở dữ liệu quan hệ R có |R| thuộc tính và |r| bản ghi. Thời gian để có thể khai phá các phụ thuộc hàm xấp xỉ theo thuật toán Tane ban đầu đề xuất phụ thuộc vào số thuộc tính |R|, số bản ghi |r|. Độ phức tạp theo hàm mũ O(2| r |). 3.2 Thuật toán AFDMCEC (phát triển từ thuật toán TANE) Thuật toán AFDMCED(Approximate Functional Dependency using Mininal Conver and Equivalent Classes) :Khai phá phụ thuộc hàm xấp xỉ sử dụng Phủ tối thiểu và lớp tương đương. 40 Với bảng cơ sở dữ liệu quan hệ R với |R| thuộc tính. 2 tập thuộc tính X, Y là tập con của R. Nếu có hàm lỗi g3(XY) < ε thì phụ thuộc hàm xấp xỉ XY đúng và g3(YX) < ε thì X và Y tương đương. Ta có thể loại bỏ tập thuộc tính Y. Thuật toán đề xuất sẽ quét toàn bộ bảng có kích thước | r | bộ dữ liệu để có thể tìm thấy tất cả các lớp tươg đương cho một phức tạp thời gian của | r |. Sau đó thuật toán AFDMCEC có một vòng lặp lặp | R | lần. Do đó, cơ thể này chính có độ phức tạp thời gian của | R |. Trong mỗi lần lặp của vòng lặp này, có một cuộc gọi cho mỗi thủ tục sau đây: 1. ComputeMinimalApproximate_FD()- FD. mỗi cuộc gọi của thủ tục này có | R | lần lặp lại. Trong mỗi lặp đi lặp lại này có một vòng lặp quét tất cả các ứng cử viên trong đó mức độ của kích thước = 2 | R |. Do đó tổng thời gian của bước này là s * | R |. 2. GeneratNextLevelCandidates (Candidate_Set) thủ tục này thực hiện hai vòng lặp lồng nhau, với mỗi |R| lặp đi lặp lại trong một thời gian tổng cộng | R|2 Do đó, tổng thời gian cần thiết bằng các thuật toán AFDMCEC yêu cầu là: O( |r| + |R| (s |R|+ |R|2 )) = O(|r| + s |R| 2 + |R|3 ) 3.2.1 Phân tích thử nghiệm Theo kết quả của cả hai thuật toán chạy (Tane và AFDMCEC), đặt cùng một AFDs từ các bộ dữ liệu UCI đã được tạo ra. Cho thấy các kết quả của các lần thực tế thay đổi thuật toán cần thiết cho TANE và cho FDMCEC thuật toán cho các bộ dữ liệu với UCI số thuộc tính khác nhau và bộ dữ liệu và với các ngưỡng khác nhau ε giá trị cho các khám phá tất cả AFDs. Bảng 3.1: Thời gian thực tế cho cả hai thuật toán 41 ( TANE và AFDMCEC các thuật toán) đối với một số bộ dữ liệu UCI cho ε ngưỡng khác nhau) Từ Bảng 3.1, cùng AFDs được tìm thấy hiệu quả hơn bằng cách sử dụng thuật toán AFDMCEC với thuật toán Tane. 3.2.2 Những sự so sánh về độ phức tạp Thời gian. Bảng 3 trình bày những so sánh phức tạp thời gian đó được tính toán trước đó cho AFDMCEC thuật toán và thuật toán TANE Bảng 3.2: Thời gian phức tạp so sánh dựa trên T (n) cho cả hai thuật toán Cách tiếp cận dựa trên xem xét phân vùng của mối quan hệ và phát sinh phụ thuộc giá trị từ các phân vùng sẽ tìm kiếm thuật toán cho phụ thuộc vào chiều rộng một cách đầu tiên. Không gian tìm kiếm có thể được cắt tỉa một cách hiệu quả và làm thế nào các phân vùng và các phụ thuộc có thể được tính hiệu quả. Thử nghiệm và so sánh kết quả chứng minh rằng thuật toán nhanh chóng trong thực tế và quy mô tính chất của nó lên là cao hơn các phương pháp trước đó. Phương pháp này hoạt động tốt với các mối quan hệ lên đến hàng trăm ngàn bộ dữ liệu. Ngoài ra còn có các ứng dụng khai thác các dữ liệu khác thú vị cho các phân vùng. Các quy tắc giữa các cặp thuộc tính-giá trị có thể được tính với một thay đổi nhỏ của các thuật toán hiện nay. Một lớp tương đương tương ứng sau đó đến một sự kết hợp đặc biệt giá trị của thuộc tính thiết lập. Bằng cách so sánh các lớp học tương đương thay vì phân vùng đầy đủ, chúng ta có thể tìm luật kết hợp. 42 KẾT LUẬN Trong thời đại ngày nay, việc khám phá tri thức trong Cơ sở dữ liệu đang là một hướng quan trọng của nền CNTT thế giới. Nó có khả năng ứng dụng vào rất nhiều toán thực tế khác nhau. Bước quan trọng nhất của quá trình này là Khai phá dữ liệu, người sử dụng thu được những tri thức hữu ích từ những CSDL hoặc các nguồn khác. Chính vì thế, trước các nhu cầu của thực tế mà các nghiên cứu đã và đang không ngừng cải tiến các phương pháp khai phá dữ liệu nhằm đáp ứng ngày một tốt hơn nữa nhằm ứng dụng các phương pháp khai phá dữ liệu cho đời sống kinh tế, xã hội. Sự phụ thuộc dữ liệu có ảnh hưởng lớn đến việc trích trọn mẫu huấn luyện nhằm xây dựng xây dựng cây quyết định có hiệu quả. Việc nhận ra sự phụ thuộc dữ liệu góp phần làm cải thiện hiệu quả trong bài toán phân lớp. Việc khai phá dữ liệu ứng dụng phụ thuộc hàm xấp xỉ đã và đang được quan tâm nghiên cứu trong nhiều năm trở lại đây, với TANE, ta có thể tìm ra các phụ thuộc hàm xấp xỉ trên dữ liệu khá hiệu quả. Một trong những ứng dụng của việc tìm ra các phụ thuộc hàm xấp xỉ là xây dựng bảng quyết định. Từ đó xây dựng cây quyết định. 43 TÀI LIỆU THAM KHẢO [1] Codd E.F(1970),”A relational model for large shared data banks”, Communication ACM12,pp.377-387 [2] Demetrovics J.,Thi V.D Relations and minimal keys. Acta Cybernetica 8,3(1988), 279-285 [3] Demetrovics J.,Thi V.D On keys in the Relations Datamodel, Inform.Process Cybern.EIK 24,10 (1988), 515-519 [4] Giannella, Chris and Robertson, Edward, 2004 “On Approximation Measures for Functional Dependencies”, Inform Action Systems Archive 29(6), 483-507. [5] Huhtala, Y., Karkkainen, J., Porkka P., and Toivonen, H., 1999. “Tane: An efficient algorithm for discovering functional and approximate dependencies”. The Computer Journal, 42(2):100-111. [6] Kivinen, J., and Mannila, H., 1995. “Approximate Inference of Functional Dependencies From Relations”. Theoretical Computer Science, 149:129-149. [7] Kwok-Wa Lam, Victor C.S.Lee, Building Decision Trees Using Functional Dependencies, Processdings, of the International Conference on Information Technology: Coding and Computing(ITCC’04), 2004. 44 PHỤ LỤC Thủ tục Tính phụ thuộc hàm xấp xỉ double tinh_phuthuochamxapxi() { double tong_phan_hoach = 0; double sobanghi = 0; int [] a = new int [100002]; int vt, j, dem = 0, k, dem_1 = 0, max = 0; string tam = ""; for (int i = 0; i<=100000; i++) a[i] = 0; for (int i = 0; i<=lbX.Items.Count-1; i++) { vt = 0; dem = 0; for (j = 0; j <= lbX.Items[i].Text.Length - 1; j++) if (lbX.Items[i].Text[j] == ' ') { dem++; tam = lbX.Items[i].Text.Substring(vt, j - vt); vt = j; 45 a[Convert.ToInt32(tam)] = 1; } sobanghi = sobanghi + dem; int p; dem_1 = 0; max = 0; for (j = 0; j <= lbY.Items.Count - 1; j++) { int dem_tam = 0; vt = 0; for (k = 0; k <= lbY.Items[j].Text.Length - 1; k++) if (lbY.Items[j].Text[k] == ' ') { tam = lbY.Items[j].Text.Substring(vt, k - vt); p = Convert.ToInt32(tam); vt = k; if (a[p] == 1) { dem_tam++; dem_1++; a[p] = 2; } } if (dem_tam > max) max = dem_tam; if (dem == dem_1) break; } tong_phan_hoach = tong_phan_hoach + max; } return 1 - (tong_phan_hoach / sobanghi); } Thủ tục phân hoạch public void phanhoach(string x, ListBox lb) { lb.Items.Clear(); int i; 46 string s = ""; string [] x1= new string[100]; int sophantux1 = 0; char[] x2 = new char[100]; int sophantux2 = 0; for (int j = 0; j<= x.Length-1; j += 2) { sophantux2++; x2[sophantux2] = x[j]; } int vt; for (i = 0; i <= ListBox1.Items.Count - 1; i++) { sophantux1 = 0; vt = 0; for (int j = 0; j <= ListBox1.Items[i].Text.Length - 1; j++) if (ListBox1.Items[i].Text[j] == '+') { sophantux1++; x1[sophantux1] = ListBox1.Items[i].Text.Substring(vt, j-vt); vt = j+1; } s = ""; string xau_select = ""; xau_select = xau_select + x2[1] + " = " + "'" + x1[1] + "'"; for (int j = 2; j <= sophantux1; j++) xau_select = xau_select + " and " + x2[j] + " = " + "'" + x1[j] + "'"; string connectionstring = ConfigurationSettings.AppSettings["connectioninfo"]; SqlConnection connection = new SqlConnection(connectionstring); connection.Open(); string select = "select TupleID from bang_dulieu where " + xau_select; 47 SqlCommand comm = new SqlCommand(select, connection); SqlDataReader reader = comm.ExecuteReader(); while (reader.Read()) s = s + reader[0].ToString() + " "; lb.Items.Add(s); connection.Close(); } } Thủ tục tính số tổ hợp void sotohop(int k, int n) { lbtohop.Items.Clear(); string s = ""; int i,j, ok; int [] a = new int[100]; for (i=1; i<=k; i++) a[i] = i; while (a[1]<=n-k+1) { s = ""; ok = 0; for (j = 1; j <= k; j++) { s = s + a[j].ToString() + " "; if (kiemtra(a[j]) == 1) { ok = 0; break; } if ((k>2) && (kiemtra(a[j])) == 0) for (int p = 0; p <= lbtohop_luugiu.Items.Count - 1; p++) if (s == lbtohop_luugiu.Items[p].Text) ok = 1; } if (k <= 2) lbtohop.Items.Add(s); 48 else if (ok == 1) lbtohop.Items.Add(s); if (a[1] < (n - k + 1)) { i = k; if (a[i] == n) { while ((a[i] == (n - k + i)) && (i>1)) { i--; a[i] = a[i] + 1; } for (j = i + 1; j <= k; j++) a[j] = a[j - 1] + 1; } else a[i] = a[i] + 1; } else a[1] = n - k + 2; } } Thủ tục loại bỏ for (int i = 0; i <= lbtohop.Items.Count - 1; i++) { vt = 0; tam = ""; dem = 0; for (j = 0; j <= lbtohop.Items[i].Text.Length - 1; j++) if (lbtohop.Items[i].Text[j] == ' ') { dem++; tam = lbtohop.Items[i].Text.Substring(vt, j - vt); vt = j; a[dem] = Convert.ToInt32(tam); } string ketqua = ""; 49 string s = ""; s = s + b[a[1]]; ketqua = ketqua + lbthuoctinh.Items[(int)b[a[1]] - 64].Text; for (j = 2; j <= dem - 1; j++) { s = s + "," + b[a[j]]; ketqua = ketqua + "," + lbthuoctinh.Items[(int)b[a[j]] - 64].Text; } hienthi_thuoctinh(s); phanhoach(s, lbX); s = s + "," + b[a[dem]]; ketqua = ketqua + "->" + lbthuoctinh.Items[(int)b[a[dem]] - 64].Text; hienthi_thuoctinh(s); phanhoach(s, lbY); lbtohop_luugiu.Items.Clear(); int giu = 0; if (tinh_phuthuochamxapxi() < Convert.ToDouble(esynol.Text)) { Response.Write(ketqua); Response.Write(""); for (int k = 0; k <= lbtohop.Items.Count - 1; k++) { vt = 0; while (vt <= lbtohop.Items[k].Text.Length - 1) { vt = lbtohop.Items[k].Text.IndexOf(' ', vt) + 1; if (vt <= lbtohop.Items[k].Text.Length - 1) giu = vt; } 50 string tam_1 = lbtohop.Items[k].Text.Substring(giu, lbtohop.Items[k].Text.Length - giu); if (Convert.ToInt32(tam_1) == a[dem]) lbtohop.Items.Remove(lbtohop.Items[k]); else lbtohop_luugiu.Items.Add(lbtohop.Items[k]); } lb_loaibo.Items.Add(a[dem].ToString()); } } tohop++; }