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

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

Trang 1

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

Trang 2

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

Trang 3

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

Trang 4

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

Trang 5

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

Trang 6

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

Trang 7

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

Trang 8

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

Trang 9

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

Trang 10

Tải về để xem bản đầy đủ

pdf 129 trang nguyenduy 03/05/2024 1010
Bạn đang xem 10 trang mẫu của tài liệu "Luận án Khai phá luật quyết định trên mô hình dữ liệu dạng khối", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.

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

Luận án Khai phá luật quyết định trên mô hình dữ liệu dạng khố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 
 (i)
 Cho khối quyết định DB = (U,CD,V,f), a=x 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 = , D = , và Cx= , Dx= , x id. 
 x
 U/C ={C1,C2,,Cm}, U/C = , 
 45 
 x
 U/D ={D1,D2,,Dg}, U/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 
 k n
của Ds thành hai lớp tương đương quyết định mớix ()Di p, Dq. x()i
 Việc chứng minh mệnh đề này tương tựi =như1 chứng ikminh=+1 của mệnh đề 2.3. 
Mệnh đề 2.8 
 (i)
 Cho khối quyết định DB=(U,CD), a = x 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 = , D = , và Cx = , Dx = , x id. 
 k n
 x 
 U/C ={C1,C2,,Cm}, U/Cx()i = x()i , 
 i= 1, x id i= k +1, x id
 x 
 U/D ={D1,D2,,Dg}, U/D = , 
 x x
 Ds U/D, Dxi U/D , Ds  Dxi, Cxj U/C , 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 
 {CCC , ,..., }
(f(Dp,a)=w, f(Dq,a)=y và trên lát cắt rx, Dx12xi được x làm xt xmịn cảm sinh một phần thành 
hai lớp tương đương quyết định mới D{Dxi’ và ,DDDxi’’,..., thì: }
 x12 x xhx
 i) Dxi = Dxi’  Dxi’’, 
 x
 ii)  Cxj U/C : 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’’ = . 
 x
 Mặt khác: Cxj U/C : 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’’). 
 x
 Vậy ta suy ra: Cxj U/C : 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’’. k n
 x()i x()i
 Do đó, để tính giá trị của các phần tử củai=1 hai cột mớiik=+ này1 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 
 (i)
 Cho khối quyết định DB = (U,CD,V,f ), a=x 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. k n
 x()i x()i
 i= 1, x id i= k +1, x id
 C = , D = , và Cx = , Dx = , x id. 
 x
 U/C={C1,C2,,Cm}, U/C = , 
 x
 U/D={D1,D2,,Dg}, U/D = {CCC , ,..., }, 
 x12 x xtx
 Khi đó, nếu hai lớp tương đương{D quyết ,DD định ,..., Dp,D }q, (f(Dp,a)=w, f(Dq,a)=y) nào 
 x12 x xhx
đó đượ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 
 (i)
 Cho khối quyết định DB = (U, CD), a=x 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 = , D = , và Cx = , Dx= , x id. 
 x
 U/C ={C1,C2,,Cm}, U/C = , 
 x
 U/D={D1,D2,,Dg}, U/D = , 
 x
 Dp, Dq U/D, (f(Dp,a)=w, f(Dq,a)=y), Cxh U/C , 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 
 k n
 ()i ()i
hai lớp tương đương quyết định Dxi, Dxj (Dp Dxxi, Dq Dxj) đượcx làm thô cảm sinh 
 i=1 ik=+1
thành Dxk thì: 
 i) Dxi  Dxj = Dxk 
 x
 ii)  Cxh U/C : 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 
 k n
 ()i ()i
 f(u,a) = f(Dxi,a) = f(Dx xk,a) =z. x
 i= 1, x id i= k +1, x id
 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. 
 {CCC , ,..., }
 Vậy suy ra: (Dxi  Dxj )  Dxk. x 12 x xt x (7) 
 Ngược lại, giả sử u Dxk, vì Dxi {Dvà D ,xjDD được ,..., làm thô } thành Dxk nên áp dụng kết 
 x12 x xhx
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=. 
 x
 Mặt khác: Cxh U/C : 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). 
 x
 Vậy suy ra: Cxh U/C : 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ỗk trợ trên látn cắt rx tương ứng với hai 
 x()i x()i
lớp tương đương quyết định Dxi, Dxj được làm thôi=1 cảm sinhik=+ thành1 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 
 (i)
 Cho khối quyết định DB = (U,CD,V,f), a = x C, Va là tập các giá trị hiện 
 k n
có của thuộc tính chỉ số điều kiệnx()i a, giá trị z củax()i a được làm mịn thành hai giá trị mới 
w và y. i= 1, x id i= k +1, x id
 C = , D = , và Cx = , Dx = , x id. 
 U/C = {C , C , , C }, U/Cx = , 
 1 2 m {CCC , ,..., }
 x12 x xtx
 x
 U/D = {D1, D2, , Dg}, U/D = , 
 {D ,DD ,..., }
 x12 x xhx
 Cxi =  C j;E  {1,2,..., m}, với Cj U/C. 
 j E
 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: 
 C = C ;C = C , (f(Cxi’,a)=w, f(Cxi’’,a) = y). 
 xi'  j1 xi''  j2
 j E j E
 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 
 t
 Theo giả thiết ta có: các lớp tương đương điều kiện Cj, (f(C j ,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ó: 
 Từ đó suy ra: f (C ,a) = f ( C ,a) = w,f (C ,a) = f ( C ,a) = y 
 xi'  j1 xi''  j2
 j E k n j E
 x()i x()i
 i=1 ik=+1
 f( Cxi' , a )== w, f ( C xi '' a ) y
 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 
 (i)
 Cho khối quyết định DB = (U, CD, V, f), a= x 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ị 
 k n
mới w và y. x()i x()i
 i= 1, x id i= k +1, x id
 C = , D = , và Cx = , Dx = , x id. 
 x 
 U/C = {C1, C2, , Cm},U/C = , 
 x {CCC , ,..., }
 /D ={D1, D2, , Dg}, U/D = x12 x xtx , 
 {D ,DD ,..., }
 x12 x xhx
 Dxi =  D j;E  {1,2,...,k}, với Dj U/D. 
 j E
 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: 
 C = D ;D = D , (f(Dxi’,a)=w, f(Dxi’’,a)=y). 
 xi'  j1 xi''  j2
 C = j E C ;C = j E C
 xi'  j1 xi''  j2
 j E j E
 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); 
 (i) 
 - Thuộc tính chỉ số a = x = (x, Ai) C vớik i = 1..n, n x id ; Va là tập các giá 
 x()i x()i
trị hiện có của thuộc tính chỉ số a, giá trị z củai =a1 được làmik =+mịn1 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 = , tập thuộc tính chỉ số 
quyết định trên khối: D = . 
 - Tập thuộc tính chỉ số điều kiện trên lát cắt x: Cx = , tập thuộc tính chỉ 
 k n
số quyết định trên khối: Dx = x()i , x id. x()i
 i= 1, x id i= k +1, 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. 
 x
 - Cxt là các lớp tương đương điều kiện trên lát cắt x: Cxt U/C , 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 
 (i)
 - Thuộc tính chỉ số a = x đượ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

File đính kèm:

  • pdfluan_an_khai_pha_luat_quyet_dinh_tren_mo_hinh_du_lieu_dang_k.pdf
  • pdfTÓM TẮT T.ANH- LAN ANH.pdf
  • pdfTÓM TẮT T.VIỆT- LAN ANH.pdf
  • pdftrích yếu luận án tiến sĩ.pdf