Luận án Khai phá luật quyết định trên mô hình dữ liệu dạng khối

a=x(i) C, Va là tập các giá trị hiện có của thuộc tính chỉ số điều kiện a, các giá trị w và y của a được làm thô thành giá trị mới z. C= ( ) 1, k i i x id x =  , D= ( ) 1, n i i k x id x = +  , và Cx= ( ) 1 k i i x = , Dx= ( ) 1 n i i k x = + , xid. U/C={C1,C2,,Cm}, U/Cx= 1 2{ , ,..., }xx x xtC C C , U/D={D1,D2,,Dg}, U/Dx= 1 2{D , ,..., }xx x xhD D , Cp, Cq  U/C, (f(Cp,a)=w, f(Cq,a)=y), DxhU/Dx, h=1..hx. Khi đó, nếu Cp, Cq được làm thô thành lớp tương đương điều kiện mới Cs, (f(Cs,a)=z ) và trên lát cắt rx hai lớp tương đương điều kiện Cxi, Cxj (Cp Cxi, Cq Cxj) được làm thô cảm sinh thành Cxk thì: i) CxiCxj = Cxk ii)  DxhU/Dx: Sup(Cxi,Dxh)+Sup(Cxj,Dxh) = Sup(Cxk,Dxh), với h=1,2,,hx. Chứng minh i) Giả sử ta có: x CxiCxj  x Cxi hoặc x Cxj. Nếu x Cxi thì do hai lớp tương đương Cxi, Cxj được làm thô thành lớp tương đương Cxk  f(x,a) = f(Cxi,a) = f(Cxk,a) = z. Mặt khác, áp dụng kết quả của định lý 2.1 ta có aj  a: f(Cxi,aj) = f(Cxj,aj) = f(Cxk,aj)  f(x,aj) = f(Cxi,aj) = f(Cxj,aj) = f(Cxk,aj)  xCxk. Hoàn toàn tương tự, khi x Cxj ta cũng chứng minh được xCxk. 44 Vậy suy ra: (Cxi  Cxj )  Cxk (5) Ngược lại, giả sử xCxk, vì Cxi và Cxj được làm thô thành Cxk nên áp dụng kết quả của định lý 2.1 ta có: aj  a: f(Cxi,aj)= f(Cxj,aj)= f(Cxk,aj)  f(x,aj) = f(Cxi,aj) = f(Cxj,aj). Mặt khác, do xCxk  f(x,a)=z mà z được làm thô từ w và y  f(x,a)=w hoặc f(x,a)=y. Nếu f(x,a)=w  f(x,a) = f(Cxi,a) = w  xCxi. Nếu f(x,a)=y  f(x,a) = f(Cxj,a) = y  xCxj. Vậy xCxi hoặc xCxj  xCxiCxj. Do đó, từ xCxk  xCxiCxj. Vậy: Cxk  (CxiCxj) (6) Kết hợp (5) và (6) ta có: CxiCxj = Cxk. ii) Vì Cxi, Cxj là các lớp tương đương điều kiện, nên ta có: CxiCxj=. Mặt khác: DxhU/Dx: Sup(Cxk,Dxh)=|Cxk  Dxh| = |(Cxi  Cxj)Dxh| = |(Cxi Dxh)(CxjDxh)|. Ta có: CxiCxj=  (Cxi  Dxh)  (Cxj  Dxh) = . Suy ra: Sup(Cxk,Dxh)= |(CxiDxh)  (CxjDxh)| = |(CxiDxh)|+ |(CxjDxh)| = Sup(Cxi,Dxh) + Sup(Cxj,Dxh). Vậy suy ra:  DxhU/Dx: Sup(Cxi,Dxh)= Sup(Cxi,Dxh) + Sup(Cxj,Dxh) với h=1,2,,hx. Như vậy, ta thấy hai dòng của ma trận độ hỗ trợ trên lát cắt rx tương ứng với hai lớp tương đương điều kiện Cxi, Cxj được kết hợp thành một dòng mới tương ứng với lớp tương đương điều kiện Cxk. Giá trị mỗi phần tử của dòng mới tương ứng với Cxk là tổng giá trị hai phần tử của hai dòng tương ứng với Cxi và Cxj. 2.3.2 Làm mịn, thô các lớp tương đương quyết định trên khối và trên lát cắt Mệnh đề 2.7 Cho khối quyết định DB = (U,CD,V,f), a=x(i) D, Va là tập các giá trị hiện có của thuộc tính chỉ số quyết định a, giá trị z của a được làm mịn thành hai giá trị mới w và y. C = ( ) 1, k i i x id x =  , D = ( ) 1, n i i k x id x = +  , và Cx= ( ) 1 k i i x = , Dx= ( ) 1 n i i k x = + , xid. U/C ={C1,C2,,Cm}, U/Cx= 1 2{ , ,..., }xx x xtC C C , 45 U/D ={D1,D2,,Dg}, U/Dx= 1 2{D , ,..., }xx x xhD D , Khi đó, nếu lớp tương đương quyết định Ds U/D (f(Ds,a)=z) được làm mịn thành hai lớp tương đương quyết định mới Dp,Dq (f(Dp,a)=w, f(Dq,a)=y, với w,yVa) nào đó thì trên lát cắt rx, tồn tại lớp tương đương Dxi thỏa mãn: Ds  Dxi , cũng được làm mịn thành hai lớp tương đương quyết định mới Dxi’ và Dxi’’ sao cho: Dp Dxi’, Dq Dxi’’ (f(Dxi’,a)=w, f(Dxi’’,a)=y). Ta nói trên lát cắt rx thì lớp tương đương quyết định Dxi được làm mịn cảm sinh một phần thành hai lớp tương đương quyết định mới Dxi’ và Dxi’’ bởi sự làm mịn của Ds thành hai lớp tương đương quyết định mới Dp, Dq. Việc chứng minh mệnh đề này tương tự như chứng minh của mệnh đề 2.3. Mệnh đề 2.8 Cho khối quyết định DB=(U,CD), a = x(i) D, Va là tập các giá trị hiện có của thuộc tính chỉ số quyết định a, giá trị z của a được làm mịn thành hai giá trị mới w và y. C = ( ) 1, k i i x id x =  , D = ( ) 1, n i i k x id x = +  , và Cx = ( ) 1 k i i x = , Dx = ( ) 1 n i i k x = + , xid. U/C ={C1,C2,,Cm}, U/Cx = 1 2{ , ,..., }xx x xtC C C , U/D ={D1,D2,,Dg}, U/Dx = 1 2{D , ,..., }xx x xhD D , Ds U/D, Dxi  U/Dx, Ds  Dxi, CxjU/Cx, s=1..k, i=1..hx, j=1..tx. Khi đó, nếu Ds (f(Ds,a)=z) được làm mịn thành hai lớp tương đương quyết định mới Dp, Dq (f(Dp,a)=w, f(Dq,a)=y và trên lát cắt rx, Dxi được làm mịn cảm sinh một phần thành hai lớp tương đương quyết định mới Dxi’ và Dxi’’ thì: i) Dxi = Dxi’  Dxi’’, ii)  CxjU/Cx: Sup(Cxj,Dxi) = Sup(Cxj,Dxi’) + Sup(Cxj,Dxi’’), với j=1,2,,tx. Chứng minh Do cách làm mịn của lớp tương đương quyết định Dxi ta thấy rằng: Dxi = Dxi’Dxi’’. Theo giả thiết ta có: Dxi được làm mịn cảm sinh một phần thành hai lớp tương đương quyết định mới Dxi’ và Dxi’’  Dxi = Dxi’  Dxi’’ và Dxi’ Dxi’’ = . Mặt khác: CxjU/Cx: Sup(Cxj,Dxi) = |CxjDxi| = |Cxj(Dxi’Dxi’’)| = 46 |(CxjDxi’)(CxjDxi’’)|. Ta có: Dxi’Dxi’’ =   (CxjDxi)(CxjDxi’’) = . Suy ra: Sup(Cxj,Dxi) = |(CxjDxi’)(CxjDxi’’)| = |(CxjDxi’)|+ |(CxjDxi’’)| = Sup(Cxj,Dxi’) + Sup(Cxj,Dxi’’). Vậy ta suy ra: CxjU/Cx: Sup(Cxj,Dxi) = Sup(Cxj,Dxi’) + Sup(Cxj,Dxi’’), với j=1,2,,tx. Từ kết quả này ta thấy: cột tương ứng với lớp tương đương quyết định Dxi trong ma trận độ hỗ trợ đối với lát cắt rx sẽ được tách thành hai cột mới tương ứng với hai lớp tương đương quyết định mới Dxi’ và Dxi’’. Do đó, để tính giá trị của các phần tử của hai cột mới này trong ma trận độ hỗ trợ đối với lát cắt rx thì đầu tiên ta tính các giá trị Sup(Cxj, Dxi) với j=1,2,,tx. Sau đó, ta suy ra các giá trị Sup(Cxj, Dxi’’) là hiệu giữa Sup(Cxj, Dxi) và Sup(Cxj, Dxi’) với j=1,2,,tx. Mệnh đề 2.9 Cho khối quyết định DB = (U,CD,V,f ), a=x(i) D, Va là tập các giá trị hiện có của thuộc tính chỉ số quyết định a, các giá trị w và y của a được làm thô thành giá trị mới z. C = ( ) 1, k i i x id x =  , D = ( ) 1, n i i k x id x = +  , và Cx = ( ) 1 k i i x = , Dx = ( ) 1 n i i k x = + , xid. U/C={C1,C2,,Cm}, U/Cx= 1 2{ , ,..., }xx x xtC C C , U/D={D1,D2,,Dg}, U/Dx= 1 2{D , ,..., }xx x xhD D , Khi đó, nếu hai lớp tương đương quyết định Dp,Dq, (f(Dp,a)=w, f(Dq,a)=y) nào đó được làm thô thành lớp tương đương quyết định mới Ds U/D (f(Ds,a)=z) thì trên lát cắt rx tồn tại hai lớp tương đương quyết định Dxi, Dxj thỏa mãn: Dp Dxi, Dq Dxj, cũng được làm thô thành lớp tương đương quyết định mới Dxk sao cho: Ds  Dxk . Ta nói trên lát cắt rx thì hai lớp tương đương quyết định Dxi, Dxj được làm thô cảm sinh thành Dxk bởi sự làm thô của hai lớp tương đương quyết định Dp,Dq thành lớp tương đương quyết định Ds. Việc chứng minh mệnh đề này tương tự như chứng minh của mệnh đề 2.5. Mệnh đề 2.10 Cho khối quyết định DB = (U, CD), a=x(i) D, Va là tập các giá trị hiện có 47 của thuộc tính chỉ số quyết định a, các giá trị w và y của a được làm thô thành giá trị mới z. C = ( ) 1, k i i x id x =  , D = ( ) 1, n i i k x id x = +  , và Cx = ( ) 1 k i i x = , Dx= ( ) 1 n i i k x = + , xid. U/C ={C1,C2,,Cm}, U/Cx= 1 2{ , ,..., }xx x xtC C C , U/D={D1,D2,,Dg}, U/Dx= 1 2{D , ,..., }xx x xhD D , Dp, Dq  U/D, (f(Dp,a)=w, f(Dq,a)=y), CxhU/Cx, h=1..tx. Khi đó, nếu Dp, Dq được làm thô thành lớp tương đương quyết định mới Ds, (f(Ds,a)=z) và trên lát cắt rx hai lớp tương đương quyết định Dxi, Dxj (Dp Dxi, Dq Dxj) được làm thô cảm sinh thành Dxk thì: i) Dxi  Dxj = Dxk ii)  CxhU/Cx: Sup(Cxh,Dxi) + Sup(Cxh,Dxj) = Sup(Cxh,Dxk), với h=1,2,,tx. Chứng minh i) Giả sử ta có: u Dxi Dxj  u Dxi hoặc u Dxj. Nếu u Dxi thì do hai lớp tương đương Dxi, Dxj được làm thô thành lớp tương đương Dxk  f(u,a) = f(Dxi,a) = f(Dxk,a) =z. Mặt khác, áp dụng kết quả của định lý 2.1 ta có ar  a: f(Dxi,ar) = f(Dxj,ar) = f(Dxk,ar)  f(u,ar) = f(Dxi,ar) = f(Dxj,ar)= f(Dxk,ar)  uDxk. Hoàn toàn tương tự, khi u Dxj ta cũng chứng minh được uDxk. Vậy suy ra: (Dxi  Dxj )  Dxk. (7) Ngược lại, giả sử uDxk, vì Dxi và Dxj được làm thô thành Dxk nên áp dụng kết quả của định lý 2.1 ta có: ar  a: f(Dxi,ar)= f(Dxj,ar) = f(Dxk,ar)  f(u,ar) =f(Dxi,ar) = f(Dxj,ar). Mặt khác, do uDxk  f(u,a)=z mà z được làm thô từ w và y  f(u,a)=w hoặc f(u,a)=y. Nếu f(u,a)=w  f(u,a)=f(Dxi,a)= w  uDxi. Nếu f(u,a)=y  f(u,a)=f(Dxj,a)= y  uDxj. Vậy uDxi hoặc uDxj  uDxiDxj. Do đó, từ uDxk  uDxi Dxj. Vậy: Dxk(DxiDxj) (8) Kết hợp (7) và (8) ta có: Dxi  Dxj = Dxk. 48 ii) Vì Dxi, Dxj là các lớp tương đương quyết định, nên ta có: Dxi  Dxj=. Mặt khác: CxhU/Cx: Sup(Cxh,Dxk)=|CxhDxk| = |(DxiDxj)Cxh| = |(Dxi Cxh)(DxjCxh)|. Ta có: DxiDxj =   (DxiCxh)(DxjCxh) = . Suy ra: Sup(Cxh,Dxk)= |(CxhDxi)(CxhDxj)| = |(CxhDxi|)|+ |(CxhDxj)| = Sup(Cxh,Dxi) + Sup(Cxh,Dxj). Vậy suy ra: CxhU/Cx: Sup(Cxh,Dxi) + Sup(Cxh,Dxj) = Sup(Cxh,Dxk), với h=1,2,,tx. Như vậy, ta thấy hai cột của ma trận độ hỗ trợ trên lát cắt rx tương ứng với hai lớp tương đương quyết định Dxi, Dxj được làm thô cảm sinh thành một cột mới tương ứng với lớp tương đương quyết định Dxk. Giá trị mỗi phần tử của cột mới tương ứng với Dxk là tổng giá trị hai phần tử của hai cột tương ứng với hai lớp tương đương quyết định Dxi và Dxj. 2.3.3 Làm mịn cảm sinh hoàn toàn thuộc tính chỉ số trên lát cắt. Mệnh đề 2.11 Cho khối quyết định DB = (U,CD,V,f), a = x(i) C, Va là tập các giá trị hiện có của thuộc tính chỉ số điều kiện a, giá trị z của a được làm mịn thành hai giá trị mới w và y. C = ( ) 1, k i i x id x =  , D = ( ) 1, n i i k x id x = +  , và Cx = ( ) 1 k i i x = , Dx = ( ) 1 n i i k x = + , xid. U/C = {C1, C2, , Cm}, U/Cx = 1 2{ , ,..., }xx x xtC C C , U/D = {D1, D2, , Dg}, U/Dx= 1 2{D , ,..., }xx x xhD D , }m,...,2,1{E;CC Ej jxi =   , với Cj  U/C. Khi đó, nếu các lớp tương đương điều kiện Cj, j  E, (f(Cj,a)=z) trên khối được làm mịn thành hai lớp tương đương điều kiện mới Cj1, Cj2 (f(Cj1,a)=w, f(Cj2,a)=y, với w,yVa ) nào đó thì trên lát cắt rx, lớp tương đương Cxi, cũng được làm mịn thành hai lớp tương đương điều kiện mới Cxi’ và Cxi’’ sao cho:  Ej 2j''xi Ej 1j'xi CC;CC  == , (f(Cxi’,a)=w, f(Cxi’’,a) = y). 49 Ta nói trên lát cắt rx thì Cxi được làm mịn cảm sinh hoàn toàn thành hai lớp tương đương điều kiện mới Cxi’ và Cxi’’ bởi sự làm mịn của Cj thành hai lớp tương đương điều kiện mới Cj1, Cj2 , j  E. Chứng minh Theo giả thiết ta có: các lớp tương đương điều kiện Cj, (f( t jC ,a)=z) trên khối được làm mịn thành hai lớp tương đương điều kiện mới Cj1, Cj2, (f(Cj1,a)=w, f(Cj2,a)=y, với w,yVa ) và ta có:  Ej 2j''xi Ej 1j'xi CC;CC  == Từ đó suy ra: y)a,C(f)a,C(f,w)a,C(f)a,C(f Ej 2j''xi Ej 1j'xi ====   Mà ta có: Cxi = Cxil  Cxi’’ , Cxil  Cxi’’ = . Như vậy, CxiU/C, (f(Cxi, a)=z) được làm mịn thành hai lớp tương đương điều kiện mới Cxi’, Cxi’’ và (f(Cxi’ ,a)=w, f(Cxi’’ ,a)=y, với w,yVa). Mệnh đề 2.12 Cho khối quyết định DB = (U, CD, V, f), a= x(i) D, Va là tập các giá trị hiện có của thuộc tính chỉ số quyết định a, giá trị z của a được làm mịn thành hai giá trị mới w và y. C = ( ) 1, k i i x id x =  , D = ( ) 1, n i i k x id x = +  , và Cx = ( ) 1 k i i x = , Dx = ( ) 1 n i i k x = + , xid. U/C = {C1, C2, , Cm},U/Cx = 1 2{ , ,..., }xx x xtC C C , /D ={D1, D2, , Dg}, U/Dx = 1 2{D , ,..., }xx x xhD D , }k,...,2,1{E;DD Ej jxi =   , với Dj  U/D. Khi đó, nếu các lớp tương đương quyết định Dj, j  E (f(Dj,a)=z) trên khối được làm mịn thành hai lớp tương đương quyết định mới Dj1, Dj2 (f(Dj1,a)=w, f(Dj2,a)=y, với w,yVa ) thì trên lát cắt rx, lớp tương đương Dxi cũng được làm mịn thành hai lớp tương đương quyết định mới Dxi’ và Dxi’’ sao cho:  Ej 2j''xi Ej 1j'xi DD;DC  == , (f(Dxi’,a)=w, f(Dxi’’,a)=y). ' ''( , ) w, ( )xi xif C a f C a y= = 50 Ta nói trên lát cắt rx thì Dxi được làm mịn cảm sinh hoàn toàn thành hai lớp tương đương quyết định mới Dxi’ và Dxi’’ bởi sự làm mịn của Dj thành hai lớp tương đương quyết định mới Dj1, Dj2, j  E. Việc chứng minh mệnh đề này tương tự như chứng minh mệnh đề 2.11 trên. 2.3.4 Thuật toán khai phá luật quyết định trên khối có giá trị thuộc tính thay đổi (MDLB_VAC) * Các kí hiệu dùng trong thuật toán (MDLB_VAC): - Khối quyết định DB = (U,CD,V,f); - Thuộc tính chỉ số a = x(i) = (x, Ai) C với i = 1..n, x id ; Va là tập các giá trị hiện có của thuộc tính chỉ số a, giá trị z của a được làm mịn thành hai giá trị mới w và y. - Tập thuộc tính chỉ số điều kiện trên khối: C = ( ) 1, k i i x id x =  , tập thuộc tính chỉ số quyết định trên khối: D = ( ) 1, n i i k x id x = +  . - Tập thuộc tính chỉ số điều kiện trên lát cắt x: Cx = ( ) 1 k i i x = , tập thuộc tính chỉ số quyết định trên khối: Dx = ( ) 1 n i i k x = + , xid. - Ci là các lớp tương đương điều kiện trên khối CiU/C, i =1..m, Dj là các lớp tương đương quyết định trên khối DjU/D, j = 1..g. - Cxt là các lớp tương đương điều kiện trên lát cắt x: CxtU/Cx, t=1,2,,tx, Dxh là các lớp tương đương quyết định trên lát cắt x: Dxh U/D, h=1,2,,hx. * Thuật toán MDLB_VAC khai phá luật quyết định trên khối có giá trị thuộc tính thay đổi Đầu vào: - Các lớp tương đương điều kiện Ci , i=1,2,,m; Cxt ,t=1,2,,tx - Các lớp tương đương quyết định Dj, j=1,2,,g; Dxh, h=1,2,,hx - Thuộc tính chỉ số a = x(i) được làm thô, làm mịn. Đầu ra: Luật quyết định trên khối Ci → Dj Phương pháp: Thuật toán gồm các bước sau: 51 - Bước 1: Tính ma trận độ hỗ trợ Sup (C,D) của khối ban đầu. - Bước 2: Tính gia tăng ma trận độ hỗ trợ trên khối Sup(C’,D’) sau khi làm thô/mịn giá trị thuộc tính chỉ số. (Thuật toán 2.4, 2.5. 2.6, 2.7) - Bước 3: Tính ma trận độ chính xác Acc(C’,D’), ma trận độ phủ Cov(C’,D’) sau khi làm thô/mịn giá trị thuộc tính chỉ số từ ma trận Sup(C’,D’) (Thuật toán 2.8) - Bước 4: Sinh luật quyết định trên khối. Thuật toán 2.4: Tính ma trận độ hỗ trợ trên khối quyết định và trên lát cắt sau khi làm thô các giá trị của thuộc tính điều kiện. Vào: - Các ma trận độ hỗ trợ trên khối, trên lát cắt tại x. - Thuộc tính chỉ số điều kiện a = x(i) được làm thô. - Các giá trị w và y của a được làm thô thành z. Ra: Ma trận độ hỗ trợ trên khối và trên lát cắt tại x sau khi làm thô. Phương pháp // Tìm tất cả các cặp lớp tương đương điều kiện Cp, Cq được hợp thành lớp tương đương điều kiện Cs mới. 1. CC = : // tập chứa các cặp lớp tương đương được hợp lại thành một lớp mới. 2. For p = 1 to m-1 do 3. for q = p + 1 to m do 4. Begin 5. if (f(Cp,a) = w and f(Cq,a) = y) or (f(Cp,a) = y and f(Cq,a) = w) then 6. begin 7. kiemtra = 1; 8. for k = 1 to |C| do //|C| là số các thuộc tính chỉ số điều kiện trên khối. 9. begin 10. If (ak  a and f(Cp,ak)  f(Cq,ak)) then 11. begin 12. kiem tra= 0; 13. break; 14. end; 15. end; 52 16. If kiemtra = 1 then lưu (Cp, Cq) vào CC; 17. end; 18. end; // Tính ma trận độ hỗ trợ trên khối sau khi làm thô. 19. For each (Cp, Cq) in CC 20. begin 21. for j = 1 to g do 22. begin 23. Sup(Cs, Dj ):= Sup(Cp, Dj)+ Sup(Cq, Dj); 24. end; 25. Xóa 2 dòng tương ứng với Cp, Cq; 26. Bổ sung dòng tương ứng với Cs; 27. end. // Tính ma trận độ hỗ trợ cho lát cắt tại x sau khi làm thô. // Tìm tất cả các cặp lớp tương đương điều kiện Cxp, Cxq được hợp thành lớp tương đương điều kiện mới Cxs. 1. CCx = : // tập chứa các cặp lớp tương đương được hợp lại thành một lớp mới. 2. For p = 1 to tx-1 do 3. for q = p + 1 to tx do 4. Begin 5. if (f(Cxp,a) = w and f(Cxq,a) = y) or (f(Cxp,a) = y and f(Cxq,a) = w) then 6. begin 7. kiemtra = 1; 8. for k = 1 to |Cx| do //|Cx| là số các thuộc tính chỉ số điều kiện trên lát cắt tại x (x  id) 9. begin 10. If (ak  a and f(Cxp,ak)  f(Cxq,ak)) then 11. begin 12. kiem tra= 0; 53 13. break; 14. end; 15. end; 16. If kiemtra = 1 then lưu (Cxp, Cxq) vào CCx; 17. end; 18. end; // Tính ma trận độ hỗ trợ trên khối sau khi làm thô. 19. For each (Cxp, Cxq) in CCx 20. begin 21. for j = 1 to hx do 22. begin 23. Sup(Cxs, Dxj ):= Sup(Cxp, Dxj)+ Sup(Cxq, Dxj); 24. end; 25. Xóa 2 dòng tương ứng với Cxp, Cxq; 26. Bổ sung dòng tương ứng với Cxs; 27. end. Kết thúc Thuật toán 2.5: Tính ma trận độ hỗ trợ trên khối quyết định và trên lát cắt sau khi làm mịn giá trị của thuộc tính điều kiện. Vào: - Ma trận độ hỗ trợ trên khối quyết định và trên lát cắt tại điểm x. - Thuộc tính chỉ số điều kiện a được làm mịn. - Tập W các đối tượng có giá trị z trên thuộc tính chỉ số a được làm mịn thành w. - Tập Y các đối tượng có giá trị z trên thuộc tính chỉ số a được làm mịn thành y. Ra: - Ma trận độ hỗ trợ (Sup) trên khối quyết định và trên lát cắt tại điểm x sau khi làm mịn giá trị z của thuộc tính chỉ số điều kiện a. Phương pháp // Tìm ma trận độ hỗ trợ trên khối quyết định sau khi làm mịn giá trị z của thuộc tính chỉ số điều kiện a. // Tìm lớp tương đương điều kiện Cs được tách thành 2 lớp mới Cp, Cq. 1. For s = 1 to m do 54 2. begin 3. if f(Cs, a) = z and Cs  W   and Cs  Y   then 4. begin 5. Cp = ; Cq = ; 6. for each u in Cs do 7. begin 8. if (f(u, a) = w) then bổ sung u vào Cp 9. else if (f(u, a) = y) then bổ sung u vào Cq; 10. end; 11. end; 12. end; // Tính ma trận độ hỗ trợ trên khối quyết định sau khi làm mịn giá trị z. 13. For j = 1 to g do Sup(Cq, Dj) = Sup(Cs, Dj) – Sup(Cp, Dj); 14. Xóa dòng tương ứng với Cs; 15. Bổ sung 2 dòng tương ứng với Cp, Cq; // Tìm lớp tương đương điều kiện Cxs được tách thành 2 lớp tương đương điều kiện mới Cxp, Cxq. 16. For s = 1 to tx do 17. begin 18. if f(Cxs,a)=z and Cxs  W   and Cxs  Y   then 19. begin 20. Cxp := ; Cxq := ; 21. for each u in Cxs do 22. begin 23. if (f(u,a) = w) then bổ sung u vào Cxp 24. else if (f(u, a) = y) then bổ sung u vào Cxq; 25. end; 26. end; 27. end; // Tính ma trận độ hỗ trợ trên lát cắt tại x sau khi làm mịn giá trị z. 28. For j = 1 to hx do 55 29. begin 30. Tính Sup(Cxp, Dj); 31. Sup(Cxq, Dj) = Sup(Cxs, Dj) – Sup(Cxp, Dj); 32. end; 33. Xóa dòng tương ứng với Cxs; 34. Bổ sung 2 dòng tương ứng với Cxp, Cxq; Kết thúc Thuật toán 2.6: Tính ma trận độ hỗ trợ trên khối quyết định và trên lát cắt sau khi làm thô các giá trị của thuộc tính quyết định. Vào: - Các ma trận độ hỗ trợ trên khối, trên lát cắt tại x. - Thuộc tính chỉ số quyết định a = x(i) được làm thô. - Các giá trị w và y của a được làm thô thành z. Ra: - Ma trận độ hỗ trợ trên khối và trên lát cắt tại x sau khi làm thô. Phương pháp // Tìm tất cả các cặp lớp tương đương quyết định Dp, Dq được hợp thành lớp tương đương quyết định Ds mới. 28. CC = : // tập chứa các cặp lớp tương đương được hợp lại thành một lớp mới. 29. For p = 1 to g-1 do 30. for q = p + 1 to g do 31. Begin 32. if (f(Dp,a) = w and f(Dq,a) = y) or (f(Dp,a) = y and f(Dq,a) = w) then 33. begin 34. kiemtra = 1; 35. for k = 1 to |D| do //|D| là số các thuộc tính chỉ số quyết định trên khối. 36. begin 37. If (ak  a and f(Dp,ak)  f(Dq,ak)) then 38. begin 39. kiem tra= 0; 40. break; 41. end; 56 42. end; 43. If kiemtra = 1 then lưu (Dp, Dq) vào CC; 44. end; 45. end; // Tính ma trận độ hỗ trợ trên khối sau khi làm thô. 46. For each (Dp, Dq) in CC 47. begin 48. for i = 1 to m do 49. begin 50. Sup(Ci, Ds)= Sup(Ci, Dp)+ Sup(Ci, Dq); 51. end; 52. Xóa 2 dòng tương ứng với Dp, Dq; 53. Bổ sung dòng tương ứng với Ds; 54. end. // Tính ma trận độ hỗ trợ cho lát cắt tại x sau khi làm thô. // Tìm tất cả các cặp lớp tương đương quyết định Dxp, Dxq được hợp thành lớp tương đương quyết định mới Dxs. 28. CCx =  // tập chứa các cặp lớp tương đương được hợp lại thành một lớp mới. 29. For p = 1 to hx-1 do 30. for q = p + 1 to hx do 31. Begin 32. if (f(Dxp,a) = w and f(Dxq,a) = y) or (f(Dxp,a) = y and f(Dxq,a) = w) then 33. begin 34. kiemtra = 1; 35. for k = 1 to |Dx| do //|Dx| là số các thuộc tính chỉ số quyết định trên lát cắt tại x (x  id) 36. begin 37. If (ak  a and f(Dxp,ak)  f(Dxq,ak)) then 38. begin 39. kiem tra= 0; 57 40. break; 41. end; 42. end; 43. If kiemtra = 1 then lưu (Dxp, Dxq) vào CCx; 44. end; 45. end; // Tính ma trận độ hỗ trợ trên khối sau khi làm thô. 46. For each (Dxp, Dxq) in CCx 47. begin 48. for i = 1 to tx do 49. begin 50. Sup(Cxi, Dxs ):= Sup(Cxi, Dxp)+ Sup(Cxi, Dxq); 51. end; 52. Xóa 2 dòng tương ứng với Dxp, Dxq; 53. Bổ sung dòng tương ứng với Dxs; 54. end. Kết thúc Thuật toán 2.7: Tính ma trận độ hỗ trợ trên khối quyết định và trên lát cắt sau khi làm mịn giá trị của thuộc tính quyết định. Vào: - Ma trận độ hỗ trợ trên khối quyết định và trên lát cắt tại điểm x. - Thuộc tính chỉ số quyết định a được làm mịn. - Tập W các đối tượng có giá trị z trên thuộc tính chỉ số a được làm mịn thành w. - Tập Y các đối tượng có giá trị z trên thuộc tính chỉ số a được làm mịn thành y. Ra: - Ma trận độ hỗ trợ trên khối quyết định và trên lát cắt tại điểm x sau khi làm mịn giá trị z của thuộc tính chỉ số quyết định a. Phương pháp // Tìm ma trận độ hỗ trợ trên khối quyết định sau khi làm mịn giá trị z của thuộc tính chỉ số quyết định a. // Tìm lớp tương đương quyết định Ds được tách thành 2 lớp mới Dp, Dq. 35. For s = 1 to g do 58 36. begin 37. if f(Ds, a) = z and Ds  W   and Ds  Y   then 38. begin 39. Dp = ; Dq = ; 40. for each u in Ds do 41. begin 42. if (f(u, a) = w) then bổ sung u vào Dp 43. else if (f(u, a) = y) then bổ sung u vào Dq; 44. end; 45. end; 46. end; // Tính ma trận độ hỗ trợ trên khối quyết định sau khi làm mịn giá trị z. 47. For i = 1 to m do Sup(Ci, Dp) = Sup(Ci, Ds) – Sup(Ci, Dp); 48. Xóa dòng tương ứng với Ds; 49. Bổ sung 2 dòng tương ứng với Dp, Dq; // Tìm lớp tương đương quyết định Dxs được tách thành 2 lớp tương đương quyết định mới Dxp, Dxq. 50. For j = 1 to hx do 51. begin 52. if f(Dxj,a)=z and Dxj  W   and Dxj  Y   then 53. begin 54. Dxp = ; Dxq = ; 55. for each u in Dxs do 56. begin 57. if (f(u,a) = w) then bổ sung u vào Dxp 58. else if (f(u, a) = y) then bổ sung u vào Dxq; 59. end; 60. end; 61. end; // Tính ma trận độ hỗ trợ trên lát cắt tại x sau khi làm mịn giá trị z. 62. For i = 1 to tx do 59 63. begin 64. Tính Sup(Cxi, Dxp); 65. Sup(Cxi, Dxq) = Sup(Cxi, Dxs) – Sup(Cxi, Dxp); 66. end; 67. Xóa dòng tương ứng với Dxs; 68. Bổ sung 2 dòng tương ứng với Dxp, Dxq; Kết thúc Thuật toán 2.8: Tính ma trận độ chính xác và ma trận độ phủ sau khi làm thô, mịn giá trị thuộc tính chỉ số Vào: Ma trận độ hỗ trợ sau khi làm thô hoặc làm mịn giá trị thuộc tính chỉ số. Ra: Ma trận độ chính xác và ma trận độ phủ sau khi làm thô hoặc làm mịn giá trị thuộc tính chỉ số. Phương pháp: //Áp dụng mệnh đề 1.1 1. SupN = 0; //Vecto tổng dòng gồm n giá trị để tính Acc 2. SupM = 0; //Vecto tổng cột gồm m giá trị để tính Cov // Tính tổng 3. For i =1 to m do 4. for j = 1 to g do 5. begin 6. SupN(j) = SupN(j) + Sup(Ci, Dj); 7. SupM(i) = SupM(i) + Sup(Ci, Dj); 8. end; // Tính Acc, Cov 9. For i=1 to m do 10. for j=1 to g do 11. begin 12. Acc(Ci,Dj) = ; )N(Sup )D,C(Sup j ji 13. Cov(Ci,Dj) = )M(Sup )D,C(Sup i ji ; 60 14. end; Kết thúc. *Ý nghĩa thuật toán MDLB_VAC khai phá luật quyết định trên khối khi giá trị thuộc tính thay đổi: Khi giá trị thuộc tính thay đổi (làm mịn hoặc làm thô giá trị thuộc tính) dẫn đến việc thay đổi của các lớp tương đương và làm ảnh hưởng đến luật quyết định thu được. Để tìm ra luật quyết định sau sự thay đổi về giá trị thuộc tính này, thay vì tính toán tuần tự theo phương pháp của thuật toán MDLB thì thuật toán MDLB_VAC sử dụng phương pháp tính toán gia tăng giúp giảm bớt quá trình tính toán mà chỉ tính những dòng, cột bị thay đổi so với ma trận các giá trị đo ban đầu. 2.4 Độ phức tạp của các thuật toán tính ma trận Sup trên khối và lát cắt. Mệnh đề 2.13 Thuật toán tính ma trận độ hỗ trợ cho khối quyết định và cho lát cắt tại điểm xid cùng có độ phức tạp là O(|U|2). Chứng minh Thật vậy, với mỗi Ci ta cần xác định: Sup (Ci, Dj) = |Ci  Dj| với j = 1, 2,, g. Như vậy ta cần thực hiện số phép so sánh và đếm là |Ci|*|U|, từ đó suy ra khi i chạy từ 1..m ta sẽ có số phép so sánh và đếm là |U| * |U| = |U|2. Do đó ta thấy độ phức tạp thời gian của thuật toán tính ma trận độ hỗ trợ cho khối quyết định là O(|U|2). Để tính độ phức tạp thời gian của thuật toán tính ma trận độ hỗ trợ cho lát cắt tại điểm xid thì ta cần xác định Sup(Cxi, Dxj) = |Cxi  Dxj| với i = 1, 2,tx, j = 1, 2,,hx. Ta thấy với mỗi Cxi thì: |Cxi  Dxj| với j = 1, 2,, hx, cần thực hiện số phép so sánh và đếm là |Cxi|*|U|, từ đó suy ra khi i chạy từ 1..tx ta sẽ có số phép so sánh và đếm là |U| * |U| = |U|2. Vậy ta có độ phức tạp thời gian của thuật toán tính ma trận đ