- Trang Chủ
- Quản trị mạng
- Phương pháp gia tăng ma trận độ hỗ trợ trên khối dữ liệu và trên lát cắt khi tập đối tượng thay đổi
Xem mẫu
- Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Huế, ngày 07-08/6/2019
DOI: 10.15625/vap.2019.00048
PHƯƠNG PHÁP GIA TĂNG MA TRẬN ĐỘ HỖ TRỢ TRÊN KHỐI DỮ LIỆU
VÀ TRÊN LÁT CẮT KHI TẬP ĐỐI TƯỢNG THAY ĐỔI
Trịnh Đình Thắng1, Đỗ Thị Lan Anh2, Trần Minh Tuyến3, Cao Hồng Huệ4
1,2,4
Viện Công nghệ Thông tin, Trƣờng Đại học Sƣ Phạm Hà Nội 2
3
Đại học Công Đoàn
thangdhsp2@hpu2.edu.vn, lananh.cntt.sp2@gmail.com, tuyentm@dhcd.edu.vn, hue.ch1124@gmail.com
TÓM TẮT: Báo cáo đề xuất phương pháp gia tăng để tính gia tăng ma trận độ hỗ trợ, từ đó tính ma trận độ chính xác và ma trận
độ phủ trên khối dữ liệu có tập đối tượng thay đổi để sinh các luật quyết định. Các thuật toán để tính gia tăng ma trận độ hỗ trợ trên
khối quyết định và trên các lát cắt của nó cũng đã được đề xuất khi tăng hoặc giảm tập đối tượng… Độ phức tạp của các thuật toán
này trên khối quyết định và trên lát cắt cũng đã được phát biểu và chứng minh. Ngoài ra, việc so sánh độ phức tạp thời gian của hai
phương pháp gia tăng tính Sup và tính Acc, Cov cũng đã được đề cập ở đây.
Từ khóa: Phương pháp gia tăng, ma trận độ hỗ trợ, ma trận độ chính xác, ma trận độ phủ, khối dữ liệu, khối quyết định.
I. GIỚI THIỆU
Quá trình nghiên cứu một mô hình và thuật toán để phát hiện các luật quyết định khi tập đối tƣợng trên khối dữ
liệu thay đổi đã đƣợc các tác giả quan tâm nghiên cứu. Mục tiêu của bài báo này là từ mô hình bổ sung và loại bỏ đối
tƣợng ra khỏi khối dữ liệu, đề xuất thuật toán tính gia tăng ma trận độ hỗ trợ trên khối dữ liệu và trên các lắt cắt của nó,
sau đó tính ma trận độ chính xác và ma trận độ phủ làm cơ sở để tìm ra các luật quyết định có ý nghĩa trên khối dữ liệu
và trên lát cắt khi tập các đối tƣợng thay đổi. Độ phức tạp tính toán của các thuật toán này cũng đã đƣợc phát biểu và
chứng minh ở đây.
II. CÁC KHÁI NIỆM CƠ BẢN
2.1 Khối
Định nghĩa 2.1[1] Gọi R = (id; A1, A2, ..., An) là một bộ hữu hạn các phần tử, trong đó id là tập chỉ số hữu hạn
khác rỗng, Ai (i=1..n) là các thuộc tính. Mỗi thuộc tính A i (i=1..n) có miền giá trị tương ứng là dom(A i). Một khối r
trên R, kí hiệu r(R) gồm một số hữu hạn phần tử mà mỗi phần tử là một họ các ánh xạ từ tập chỉ số id đến các miền
trị của các thuộc tính Ai (i=1..n).
Nói một cách khác:t r(R) t = {ti : id dom(Ai)}i=1..n.
Ta kí hiệu khối đó là r(R) hoặc r(id; A1, A2,..., An ), đôi khi nếu không sợ nhầm lẫn ta kí hiệu đơn giản là r.
2.2 Lát cắt của khối
Định nghĩa 2.2 [2], [3] Cho R = (id; A1, A2,..., An), r(R) là một khối trên R. Với mỗi x id ta kí hiệu r(Rx) là
một khối với Rx = ({x}; A1, A2,..., An) sao cho:
tx r(Rx) tx = {tix = ti } i=1..n , t r(R), t = {ti : id dom(Ai)}i=1..n , ở đây tax(x) = ti(x), i =1..n.
x
Khi đó r(Rx) được gọi là một lát cắt trên khối r(R) tại điểm x, đôi khi ta kí hiệu là rx.
Sau đây, để cho đơn giản ta sử dụng các kí hiệu: x(i) = (x; Ai ) ; id(i) = {x(i) | x id}. Ta gọi x(i) (x id, i = 1..n)
là các thuộc tính chỉ số của lƣợc đồ khối R = (id; A1,A2,...,An ).
2.3 Khối thông tin
Định nghĩa 2.3: [4] Cho lược đồ khối R = (id; A1, A2, ... , An ), r là một khối trên R. Khi đó khối thông tin là một
()
bộ bốn IB = (U, A, V, f) với U là tập các đối tượng thuộc r gọi là không gian các đối tượng, ⋃ là tập các
thuộc tính chỉ số của đối tượng, ⋃ () (i)
( ) , V ( i ) là tập giá trị của các đối tượng ứng với thuộc tính chỉ số x , f là
x
hàm thông tin UxA V thỏa mãn: u U, x A ta có f(u, x ) Vx( i ) .
(i) (i)
Khi đó, ta gọi f(u, x(i)) là giá trị của đối tƣợng u tại thuộc tính chỉ số x(i).
Định nghĩa 2.4: [4] Cho lược đồ khối R = (id; A1, A2, ... , An ), r là một khối trên R, rx là lát cắt của khối r tại
điểm x id. Khi đó lát cắt của khối thông tin tại x là một bộ bốn IB x = (U, Ax, Vx, fx) với U là tập các đối tượng thuộc r
()
gọi là không gian các đối tượng, ⋃ là tập các thuộc tính chỉ số của đối tượng trên lát cắt tại x, Vx ( i ) là tập
(i) (i)
giá trị của các đối tượng ứng với thuộc tính chỉ số x , fx là hàm thông tin UxAx Vx thỏa mãn: u U, x Ax ta có
(i)
f(u, x ) Vx ( i ) , Vx = Vx( i ) .
x( i ) Ax
- 380 PHƢƠNG PHÁP GIA TĂNG MA TRẬN ĐỘ HỖ TRỢ TRÊN KHỐI DỮ LIỆU VÀ TRÊN LÁT CẮT KHI TẬP…
2.4 Khối quyết định [4]
n
(i )
Định nghĩa 2.5 Cho khối thông tin IB k= (U,A,V,f)n với U là không gian các đối tượng, A = id . Khi đó nếu A
i 1
được chia thành 2 tập C và D sao cho: C= x,(i )D = x,(i )thì khối thông tin IB gọi là khối quyết định và kí hiệu là
i 1, x id i k 1, x id
DB=(U,C D,V,f), với C là tập các thuộc tính chỉ số điều kiện và D là tập các thuộc tính chỉ số quyết định.
Ta có thể kí hiệu khối quyết định một cách đơn giản là: DB=(U, C D).
Định nghĩa 2.6: Cho khối quyết định DB=(U,C D,V,f), với C là tập các thuộc tính chỉ số điều kiện và D là tập
các thuộc tính chỉ số quyết định. Khi đó lát cắt của khối quyết định tại x (x id)k là một bộ nbốn DBx = (U, Cx Dx, Vx, fx )
với U là tập các đối tượng thuộc r gọi là không gian các đối tượng, Cx= x , Dx= x ( i,) Ax= Cx Dx, Vx= Vx ,
(i )
(i )
(i )
i 1 i k 1 x A x
(i)
Vx( i ) là tập các giá trị của các đối tượng ứng với thuộc tính chỉ số x , fx là hàm thông tin UxAx Vx thỏa
mãn: u U, x(i) Ax ta có f(u, x(i)) Vx( i ) .
2.5 Luật quyết định trên khối và trên lát cắt
Định nghĩa 2.7 [4] Cho khối quyết định DB = (U, C D), với U là không gian các đối tượng:
k n
C= ,D= , Cx= x ( i ), D x= x ( i ,) x id.
i 1 i k 1
Khi đó: U/C={C1,C2,…,Cm}, U/Cx= {Cx1, Cx 2 ,..., Cxt } , U/D={D1,D2,…,Dh}, U/Dx= {D x1, Dx 2 ,..., Dxs } ,
x x
tương ứng là các phân hoạch được sinh ra bởi C, Cx, D, Dx. Một luật quyết định trên khối có dạng: Ci Dj, i=1..m,
j=1..h và trên lát cắt tại điểm x có dạng: Cxi Dxj , i=1..tx, j=1..sx .
Mệnh đề 2.1 Cho khối quyết định DB = (U, C D), với U là không gian các đối tượng:
k n
x (i ) x (i )
C= , D= , Cx= i 1
, Dx=i k 1
, x id,
U/C={C1,C2,…,Cm}, U/Cx= {Cx1 , Cx 2 ,..., Cxtx } ,
U/D={D1,D2,…,Dh}, U/Dx= {D x1 , Dx 2 ,..., Dxs } .
x
Khi đó: Ci U/C , Dj U/D ta có: Ci = ,Dj = với px {1,2,…,tx }, qx {1,2,…,sx }.
Định nghĩa 2.8 Cho khối quyết định DB=(U,C D), Ci U/C, Dj U/D, Cxp U/Cx, Dxq U/Dx, i=1..m, j=1..h,
p {1,2,…,tx }, q {1,2,…,sx }, x id. Khi đó, độ hỗ trợ, độ chính xác và độ phủ của luật quyết định Ci Dj trên khối
là: - Độ hỗ trợ: Sup(Ci,Dj) = |Ci Dj)|,
- Độ chính xác: Acc(Ci,Dj) =
- Độ phủ: Cov(Ci,Dj) = ,
còn đối với luật quyết định Cxp Dxq trên lát cắt của khối tại điểm x là:
- Độ hỗ trợ: Sup(Cxp,Dxq) = |Cxp Dxq)|,
| C xp Dxq |
- Độ chính xác: Acc(Cxp,Dxq) = ,
| C xp |
| C xp Dxq |
- Độ phủ: Cov(Cxp,Dxq) = .
| Dxq |
Ta có thể biểu diễn độ đo của các luật quyết định trên khối dƣới dạng các ma trận độ đo nhƣ sau:
- Ma trận độ hỗ trợ:
Sup(Ci,Dj)mxn =
- Ma trận độ chính xác:
Acc(Ci,Dj)mxn =
- Ma trận độ phủ:
Cov(Ci,Dj)mxn =
- Trịnh Đình Thắng, Đỗ Thị Lan Anh, Trần Minh Tuyến, Cao Hồng Huệ 381
Với các luật quyết định trên các lát cắt của khối thì ta cũng có các ma trận độ hỗ trợ, độ chính xác và độ phủ
tƣơng tự.
Mệnh đề 2.2
k n
Cho khối quyết định DB = (U, C D), với U là không gian các đối tượng:C = x (,i ) D = x (.i )
i 1, x id i k 1, x id
Khi đó Ci U/C, Dj U/D, (i=1..m, j=1..h) ta có:
Sup(Ci , D j ) Sup(Ci , D j )
Acc(Ci, Dj ) = h , Cov(Ci, Dj ) = m .
Sup(Ci , Dq ) Sup(C p , D j )
q 1 p 1
3. Kết quả nghiên cứu
3.1 Tính toán gia tăng độ hỗ trợ khi bổ sung và loại bỏ các đối tượng trên khối quyết định và trên lát cắt
k n k n
(i )
Cho khối quyết định DB= (U, C D, V, f), trong đó: C = x, (D
i)
= ,x C x= ,xD x =
(i )
x, (xi ) id.
i 1, x id i k 1, x id i 1 i k 1
U/C={C1,C2,…,Cm}, U/C x= {Cx1 , Cx 2 ,..., Cxtx } , U/D={D1,D2,…,Dh}, U/D x= {D x1 , Dx 2 ,..., Dxs } .
x
Giả sử, ta cần bổ sung vào khối quyết định này N đối tƣợng, kí hiệu AN và loại bỏ khỏi khối quyết định này M
đối tƣợng, kí hiệu DM.
Khi bổ sung N đối tƣợng vào khối quyết định thì N đối tƣợng này sẽ sinh thêm p lớp tƣơng đƣơng điều kiện
mới đối với tập U/C, px lớp tƣơng đƣơng điều kiện mới đối với tập U/Cx và q lớp tƣơng đƣơng quyết định mới đối với
tập U/D và qx lớp tƣơng đƣơng quyết định mới đối với tập U/Dx. Kí hiệu Ni là số đối tƣợng đƣợc bổ sung cho lớp Ci
U/C (i=1.. m+p), Nxi là số đối tƣợng đƣợc bổ sung cho lớp C xi U/Cx (i=1..tx+px) và trong Ni đối tƣợng này có Nij đối
tƣợng đƣợc bổ sung cho lớp Dj U/D (j=1.. h+q). Nhƣ vậy có Nij đối tƣợng đƣợc bổ sung cho cho cả Ci và Dj, nghĩa là
bổ sung cho Ci Dj, do đó Sup(Ci, Dj) tăng thêm Nij. Khi đó, trên lát cắt tại x thì trong Nxi đối tƣợng này có Nxij đối
tƣợng đƣợc bổ sung cho lớp Dxj U/Dx, (j=1.. sx+qx), nên sẽ có Nxij đối tƣợng đƣợc bổ sung cho cả Cxi và Dxj, nghĩa là
bổ sung cho Cxi Dxj, do đó Sup(Cxi, Dxj) tăng thêm Nxij.
Tƣơng tự, trong M đối tƣợng bị loại bỏ có Mi đối tƣợng bị loại khỏi lớp Ci U/C (i=1.. m), có Mij đối tƣợng bị
loại bỏ khỏi lớp Dj (j=1.. h). Do vậy, có Mij đối tƣợng bị loại bỏ khỏi cả Ci và Dj, nghĩa là loại bỏ khỏi Ci Dj, do đó
Sup(Ci, Dj) giảm đi Mij. Khi đó, trên lát cắt tại x thì trong Mxi (i=1..tx) đối tƣợng bị loại bỏ khỏi lớp Cxi U/Cx có Mxij
(j=1.. sx), đối tƣợng bị loại bỏ khỏi lớp Dxj U/Dx , nên sẽ có Mxij đối tƣợng bị loại bỏ khỏi cả Cxi và Dxj, nghĩa là bị
loại bỏ khỏi Cxi Dxj, do đó Sup(Cxi, Dxj) giảm đi Mxij.
Ta kí hiệu các lớp tƣơng đƣơng sau khi bổ sung và loại bỏ các đối tƣợng đó là:
U’/C={C’1,C’2,…,C’m,…}, U’/Cx= {C ' x1, C ' x 2 ,..., C ' xt ...} , U’/D={D’1,D’2,…,D’h…}, U’/D x= {D' x1, D ' x 2 ,..., D ' xs ...} .
x x
Khi đó ta có:
Sup(C’i, D’j) = Sup(Ci, Dj) + Nij – Mij, i=1..m+p, j=1..h+q
ở đó Mij = 0 và Sup(Ci, Dj)=0, i=m+1..m+p, j=h+1..h+q vì ta chỉ loại bỏ các đối tƣợng trong các lớp tƣơng đƣơng có
chỉ số i=1..m, j=1..h.
Sau khi tính đƣợc Sup(C’i, D’j) thì ta xác định đƣợc ma trận độ hỗ trợ Sup(C’, D’) và từ đó việc tính các ma
trận Acc(C’, D’) và Cov(C’, D’) đƣợc thực hiện dễ dàng nhờ mối quan hệ giữa Acc và Cov với Sup đã đƣợc định
nghĩa.
Nhận xét: Trƣớc khi tính các ma trận Acc(C’, D’) và Cov(C’, D’) ta thực hiện các thao tác xóa dòng/cột trong ma
trận Sup(C’, D’) mà có toàn giá trị 0 nếu có.
3.2 Các thuật toán tính gia tăng ma trận độ hỗ trợ khi bổ sung và loại bỏ các đối tượng.
Các thuật toán tính các ma trận Sup(C, D), Acc(C, D) và Cov(C, D) khi chƣa tiến hành bổ sung và loại bỏ các
đối tƣợng đã đƣợc nêu ra trong [4], ở đây ta xem xét thuật toán tính gia tăng ma trận Sup(C’, D’), sau đó thực hiện các
thao tác xóa dòng/cột trong ma trận Sup(C’, D’) mà có toàn giá trị 0 nếu có. Từ đó tính các ma trận Acc(C’, D’) và
Cov(C’, D’) để rút ra các luật quyết định có ý nghĩa. Các bƣớc cơ bản của quá trình này đƣợc thể hiện qua sơ đồ khối
sau đây:
- 382 PHƢƠNG PHÁP GIA TĂNG MA TRẬN ĐỘ HỖ TRỢ TRÊN KHỐI DỮ LIỆU VÀ TRÊN LÁT CẮT KHI TẬP…
Bắt đầu
Tính ma trận Sup(C, D)
Tính gia tăng ma trận Sup(C’, D’) sau khi bổ
sung/loại bỏ đối tƣợng
Loại bỏ dòng/cột toàn giá trị 0 ra khỏi ma trận
Sup(C’, D’) nếu có
Tính các ma trận Acc(C’, D’) và
Cov(C’, D’)
Sinh các luật quyết định
có ý nghĩa
Kết thúc
Thuật toán 3.1: Tính gia tăng ma trận Sup(C’, D’), khi bổ sung các đối tượng.
Vào: - Các lớp Ci, Dj.
- Tập AN gồm N đối tƣợng đƣợc bổ sung.
- Ma trận Sup(C, D).
Ra: Ma trận Sup(C’, D’).
// Tìm lớp điều kiện và lớp quyết định end for;
chứa x
for j = 1 to h+q do //tìm trong các lớp
p = 0; q = 0; quyết định
for each x in AN do if (x in Dj) then
i* = -1; //lớp điều kiện của x sẽ tìm j* = j; //Tìm thấy x thuộc lớp Dj
j* = -1; //lớp quyết định của x sẽ tìm break;
for i = 1 to m + p do //tìm trong các end if;
lớp điều kiện
// Nếu j* = -1 thì x không thuộc Dj nào,
if (x in Ci) then tạo thêm lớp mới Dh+q+1 với q là biến trong
chương trình
i* = i; // tìm thấy x thuộc lớp Ci
if j* = -1 then
break;
j* = n + q + 1;
end if;
Bổ sung Dh+q+1 vào U/D;
// Nếu i* = -1 thì x không thuộc Ci nào, tạo
thêm lớp mới Cm+p+1, với p ở đây là biến trong Tạo cột (q + 1) mới = 0 cho ma trận
chương trình. Sup;
if i* = -1 then q = q + 1;
i* = m + p + 1; end if;
//Cập nhật tập lớp điều kiện //Cập nhật phần tử ma trận Sup tương ứng
Bổsung Cm+p+1 vào U/C; Sup(Ci*, Dj*) = Sup(Ci*, Dj*) +1
Tạo dòng (p + 1) mới = 0 cho ma trận end if;
Sup;
end for;
p = p + 1;
End for each.
end if;
Từ thuật toán 3.1 ta thấy: đầu tiên thuật toán xác định đối tƣợng x đƣợc bổ sung thuộc vào lớp điều kiện hay
lớp quyết định nào. Khi đó có 4 trƣờng hợp xảy ra, cụ thể nhƣ sau:
(i) Nếu x ∉ Ci và x ∉ Dj nào, nghĩa là việc bổ sung x hình thành thêm một lớp điều kiện mới và một lớp
quyết định mới. Khi đó, ma trận Sup đƣợc bổ sung thêm một dòng mới ký hiệu i* và một cột mới ký hiệu j*. Ta gán
giao của dòng i* và cột j* là 1, các phần tử khác còn lại của dòng i* và cột j* đƣợc gán bằng 0.
- Trịnh Đình Thắng, Đỗ Thị Lan Anh, Trần Minh Tuyến, Cao Hồng Huệ 383
(ii) Nếu x ∉ Ci và ∃ j* ∈{1,…,h}: x ∈Dj* nghĩa là việc bổ sung x chỉ hình thành một lớp điều kiện mới và
làm ảnh hƣởng đến cột j*. Suy ra, ma trận Sup đƣợc bổ sung thêm một dòng mới i*. Khi đó, ta tăng giá trị của ô
(i*,j*) lên 1, các phần tử khác còn lại của dòng i* đƣợc gán bằng 0 và của cột j* không đổi.
(iii) Nếu ∃ i*∈{1,…,m}: x∈ Ci* và x ∉ Dj nghĩa là việc bổ sung x chỉ hình thành một lớp quyết định mới
và làm ảnh hƣởng đến dòng i*. Khi đó, ma trận Sup đƣợc bổ sung thêm cột mới j* và ta tăng giá trị của ô (i*,j*) lên
1, các phần tử còn lại của cột j* đƣợc gán bằng 0, còn các phần tử của dòng i* không đổi.
(iv) Nếu ∃i*∈{1,…,m}: x ∈Ci* và ∃ j*∈{1,…,n}: x ∈Dj* nghĩa là việc bổ sung x không hình thành lớp
điều kiện mới và cũng không hình thành lớp quyết định mới. Nhƣ vậy, x làm ảnh hƣởng đến dòng i* và cột j* của
ma trận Sup, khi đó ta tăng giá trị của ô (i*,j*) lên 1, các phần tử còn lại không thay đổi.
Tiếp tục thực hiện nhƣ vậy cho đến khi duyệt hết N đối tƣợng đƣợc bổ sung, ta thu đƣợc ma trận Sup(C’, D’).
Thuật toán 3.2: Tính gia tăng ma trận Sup(C’, D’), khi loại bỏ các đối tượng.
Vào: - Các lớp Ci, Dj.
- Tập DM gồm M đối tƣợng bị loại bỏ.
- Ma trận Sup(C, D).
Ra: Ma trận Sup(C’, D’).
// Tìm lớp điều kiện và lớp quyết định end for;
chứa x’.
for j=1 to h do //tìm trong các lớp
for each x’ in DM do quyết định
i* = -1; //lớp điều kiện của x’ sẽ tìm if (x’ in Dj) then
j* = -1; //lớp quyết định của x’ sẽ tìm j* = j; //tìm thấy x’ thuộc lớp Dj
for i = 1 to m do //tìm trong các lớp break;
điều kiện
end if;
if (x’ in Ci) then
end for;
i* = i; // tìm thấy x’ thuộc lớp Ci
//Cập nhật phần tử của ma trận Sup tương ứng
break;
Sup(Ci*, Dj*)=Sup(Ci*, Dj*) - 1;
end if;
end for each;
Thuật toán 3.3: Tính gia tăng ma trận Sup(C’x, D’x), khi bổ sung các đối tượng đối với lát cắt tại x.
Vào: - Các lớp Cxi, Dxj.
- Tập AN gồm N đối tƣợng đƣợc bổ sung.
- Ma trận Sup(Cx, Dx).
Ra: Ma trận Sup(Cx’, Dx’).
// Tìm lớp điều kiện và lớp quyết định if i* = -1 then
chứa y AN
i* = tx + px + 1;
Px = 0; qx = 0;
//Cập nhật tập lớp điều kiện
for each y in AN do
Bổsung ( ) vào U/Cx;
i* = -1; //lớp điều kiện của y sẽ tìm
Tạo dòng (px + 1) mới = 0 cho ma
j* = -1; //lớp quyết định của y sẽ tìm trận Sup;
for i = 1 to tx + px do //tìm trong các px = px + 1;
lớp điều kiện
end if;
if (y in Cxi) then
end for;
i* = i; // tìm thấy y thuộc lớp Cxi
for j=1 to sx+qx do //tìm trong các
break; lớp quyết định
end if; if (y in Dxj) then
// Nếu i* = -1 thì y không thuộc Cxi nào, tạo j* = j; //Tìm thấy y thuộc lớp Dxj
thêm lớp mới ( ) , với px ở đây là biến
break;
trong chương trình.
- 384 PHƢƠNG PHÁP GIA TĂNG MA TRẬN ĐỘ HỖ TRỢ TRÊN KHỐI DỮ LIỆU VÀ TRÊN LÁT CẮT KHI TẬP…
end if; Tạo cột (qx+ 1) mới = 0 cho ma trận Sup;
// Nếu j* = -1 thì y không thuộc Dxj nào, tạo qx = qx + 1;
thêm lớp ( ) với qx là biến trong chương
end if;
trình
//Cập nhật phần tử ma trận Sup tương ứng
if j* = -1 then
Sup(Cxi*, Dxj*) = Sup(Cxi*, Dxj*) +1
j* = sx + qx + 1;
end for;
Bổ sung ( ) vào U/Dx;
End for each.
Thuật toán 3.4: Tính gia tăng ma trận Sup(C’x, D’x), khi loại bỏ các đối tượng đối với lát cắt tại x.
Vào: - Các lớp Cxi, Dxj.
- Tập DM gồm M đối tƣợng bị loại bỏ.
- Ma trận Sup(Cx, Dx).
Ra: Ma trận Sup(Cx’, Dx’).
// Tìm lớp điều kiện và lớp quyết định for j=1 to sx do //tìm trong các lớp
chứa y’. quyết định
for each y’ in DM do if (y’ in Dxj) then
i* = -1; //lớp điều kiện của y’ sẽ tìm j* = j; //tìm thấy y’ thuộc lớp Dxj
j* = -1; //lớp quyết định của y’ sẽ tìm break;
for i = 1 to tx do //tìm trong các lớp end if;
điều kiện
end if;
if (y’ in Cxi) then
//Cập nhật phần tử của ma trận Sup tương ứng
i* = i; // tìm thấy y’ thuộc lớp Cxi
Sup(Cxi*, Dxj*)=Sup(Cxi*, Dxj*) - 1;
break;
end for;
end if;
End for each;
end for;
Định lý 3.1: Thuật toán tính gia tăng ma trận Sup để phát hiện các luật quyết định khi bổ sung, loại bỏ đối
tượng ra khỏi khối dữ liệu có cùng kết quả với thuật toán tính gia tăng ma trận Acc và ma trận Cov khi chạy trên
cùng tập dữ liệu.
Chứng minh.
Ta thấy cả hai phƣơng pháp trích rút luật quyết định cùng chọn độ chính xác và độ phủ để đƣa ra xem xét.
Do đó, để chứng minh hai thuật toán có cùng kết quả, ta chứng minh quá trình thực hiện thuật toán tính gia tăng ma
trận Sup sẽ thu đƣợc ma trận Acc và ma trận Cov giống với thuật toán tính gia tăng Acc và Cov khi chạy trên cùng
một tập dữ liệu.
Thật vậy, theo thuật toán tính gia tăng ma trận Sup ta có: Sup(Ci’, Dj’) = Sup(Ci, Dj) + Nij – Mij
với i = 1,…, m+p, j =1, …, h+q).
Trong đó:
Mij = 0 và Sup(Ci, Dj) = 0 với i = m+1,…, m+p; j= h+1,…, h+q.
Từ công thức trên ta thấy, Nij – Mij chính là phần giá trị đƣợc bổ sung cho ma trận Sup khi bổ sung, loại bỏ đối
tƣợng ra khỏi khối dữ liệu, phần bổ sung này có thể biểu diễn dƣới dạng một ma trận, ký hiệu là INC(N,M), ma trận
này gọi là ma trận gia tăng, đƣợc biểu diễn nhƣ sau:
𝑁 − 𝑀 … 𝑁 ℎ − 𝑀 ℎ 𝑁 ,ℎ … 𝑁 ,ℎ 𝑞
⋮ ⋮ ⋮ ⋮
𝑁𝑚 − 𝑀𝑚 … 𝑁𝑚ℎ − 𝑀𝑚ℎ 𝑁𝑚,ℎ … 𝑁𝑚,ℎ 𝑞
𝐼𝑁𝐶(𝑁, 𝑀) 𝑁𝑚 , … 𝑁𝑚 ,ℎ 𝑁𝑚 ,ℎ … 𝑁𝑚 ,ℎ 𝑞
⋮ ⋮ ⋮ ⋮
𝑁𝑚 𝑝, ⋯ 𝑁𝑚 𝑝,ℎ 𝑁𝑚 𝑝,ℎ … 𝑁𝑚 𝑝,ℎ 𝑞
- Trịnh Đình Thắng, Đỗ Thị Lan Anh, Trần Minh Tuyến, Cao Hồng Huệ 385
Khi đó, ta có ma trận Sup đƣợc tính nhƣ sau:
Sup(C’, D’) = Sup(C,D) + INC(N, M) =
𝑆𝑢𝑝(𝐶 , 𝐷 )+𝑁 − 𝑀 … 𝑆𝑢𝑝(𝐶 ℎ , 𝐷 ℎ ) + 𝑁 ℎ − 𝑀 ℎ 𝑁 ,ℎ … 𝑁 ,ℎ 𝑞
⋮ ⋮ ⋮ ⋮
𝑆𝑢𝑝(𝐶𝑚 , 𝐷𝑚 ) + 𝑁𝑚 − 𝑀𝑚 … 𝑆𝑢𝑝(𝐶𝑚ℎ , 𝐷𝑚ℎ ) + 𝑁𝑚ℎ − 𝑀𝑚ℎ 𝑁𝑚,ℎ … 𝑁𝑚,ℎ 𝑞
𝑁𝑚 , … 𝑁𝑚 ,ℎ 𝑁𝑚 ,ℎ … 𝑁𝑚 ,ℎ 𝑞
⋮ ⋮ ⋮ ⋮
𝑁𝑚 𝑝, ⋯ 𝑁𝑚 𝑝,ℎ 𝑁𝑚 𝑝,ℎ … 𝑁𝑚 𝑝,ℎ 𝑞
(1) Tính Acc(C’i, D’j) từ ma trận Sup(C’, D’) :
Từ kết quả tính Sup(C’, D’) ở trên, dựa vào công thức tính Acc theo Sup ta có:
| Ci D | N ij
j M ij
h q h
, i 1..m, j 1..h,
| Ci | N ij' M ij'
j' 1 j' 1
N ij
Acc(C 'i , D ' j ) h q h
, i 1..m, j h 1..h q,
| Ci | N ij' M ij'
j' 1 j' 1
N ij
h q
, i m 1..m p, j 1.. h q
N ij
j 1
Đây chính là công thức tính gia tăng của Acc(Ci’, Dj’) nhƣ đã biết. (1)
(2) Tính Cov(C’i, D’j) từ ma trận Sup(C’, D’) :
Cũng từ kết quả tính Sup(C’, D’) ở trên, dựa vào công thức tính Cov theo Sup ta tính đƣợc:
| Ci D | N ij
j M ij
m p m
, i 1..m, j 1..h,
| Dj | N i'j M i'j
i' 1 i' 1
N ij
Cov (C 'i , D ' j ) m p m
, i m 1..m p, j 1..h ,
| Dj | N i'j M i'j
i' 1 i' 1
N ij
m p
, i 1..m p, j h 1.. h q
N i'j
i' 1
Đây cũng chính là công thức tính gia tăng của Cov(Ci’, Dj’) nhƣ đã biết. (2)
Từ các nhận xét (1) và (2) ta suy ra điều phải chứng minh.
Đối với mỗi lát cắt tại điểm x id ta có kết quả sau:
Định lý 3.2: Thuật toán tính gia tăng ma trận Sup để phát hiện các luật quyết định khi bổ sung, loại bỏ đối
tượng ra khỏi khối dữ liệu xét trên lát cắt tại x id có cùng kết quả với thuật toán tính gia tăng ma trận Acc và ma
trận Cov khi chạy trên cùng tập dữ liệu xét trên lát cắt tại x id .
Việc chứng minh định lý này cũng hoàn toàn tƣơng tự nhƣ chứng minh của định lý 3.1 ở trên.
3.3 Độ phức tạp thuật toán của các thuật toán tính gia tăng
Mệnh đề 3.1: Độ phức tạp thời gian của thuật toán tính gia tăng ma trận Sup khi bổ sung N đối tượng là
O(N|U|).
Chứng minh:
Từ thuật toán tính gia tăng ma trận Sup ta thấy: để kiểm tra một đối tƣợng x đƣợc bổ sung thuộc vào lớp điều
kiện hay lớp quyết định nào ta cần m’+h’ phép tính (m’, h’ là kích thƣớc ma trận tại thời điểm trƣớc khi bổ sung).
Tiếp theo, để cập nhật Sup(Ci*, Dj*) chỉ mất một số phép gán và 1 phép cộng.
- 386 PHƢƠNG PHÁP GIA TĂNG MA TRẬN ĐỘ HỖ TRỢ TRÊN KHỐI DỮ LIỆU VÀ TRÊN LÁT CẮT KHI TẬP…
Mặt khác, ta cũng có thể coi m’=m+p, n’=n+q, đồng thời m, n |U|. Do đó, khi bổ sung một đối tƣợng, thuật
toán có độ phức tạp là O(|U|). Suy ra, khi bổ sung N đối tƣợng thì thuật toán có độ phức tạp là O(N|U|).
Mệnh đề 3.2: Độ phức tạp thời gian của thuật toán tính gia tăng ma trận Sup khi loại bỏ M đối tượng là
O(M|U|).
Chứng minh:
Lập luận tƣơng tự nhƣ ở mệnh đề 3.1 ta suy ra độ phức tạp của thuật toán tính gia tăng ma trận Sup khi loại bỏ
M đối tƣợng là O(M|U|).
Từ các mệnh đề 3.1 và 3.2 về độ phức tạp thời gian của các thuật toán tính gia tăng ma trận Sup khi bổ sung và
loại bỏ đối tƣợng ta có mệnh đề sau:
Mệnh đề 3.3: Độ phức tạp thời gian của thuật toán tính gia tăng ma trận Sup để trích rút các luật quyết định
có ý nghĩa khi bổ sung, loại bỏ các đối tượng là O(|U|2).
Đối với hai thuật toán tính gia tăng ma trận Sup khi bổ sung hay loại bỏ các đối tƣợng ra khỏi khối dữ liệu xét
trên lát cắt của khối tại điểm x id ta cũng có kết quả tƣơng tự thể hiện ở hai mệnh đề dƣới đây.
Mệnh đề 3.4: Độ phức tạp thời gian của thuật toán tính gia tăng ma trận Sup khi bổ sung N đối tượng xét
trên lát cắt của khối tại điểm x id là O(N|U|).
Mệnh đề 3.5: Độ phức tạp thời gian của thuật toán tính gia tăng ma trận Sup khi loại bỏ M đối tượng xét trên
lát cắt của khối tại điểm x id là O(M|U|).
3.3 So sánh hai phương pháp tính gia tăng
Hai phƣơng pháp tính gia tăng để phát hiện các luật quyết định cùng sử dụng mô hình bổ sung, loại bỏ đối
tƣợng ra khỏi khối dữ liệu với yêu cầu và giả thiết bài toán nhƣ nhau; cùng sử dụng cách tiếp cận gia tăng theo tiếp
cận tập thô; cùng xét trên khối quyết định đầy đủ với các giá trị thuộc tính đã đƣợc rời rạc hóa; cùng chọn cả độ chính
xác và độ phủ của luật để đánh giá mức độ mô tả của các luật quyết định có ý nghĩa đƣợc trích rút và cho cùng một
kết quả khi chạy trên cùng một khối dữ liệu.
Tuy nhiên sự khác nhau của chúng đƣợc thể hiện ở bảng dƣới đây:
Bảng 1. Bảng so sánh hai phƣơng pháp tính gia tăng
Thuật toán tính Thuật toán tính gia tăng Acc, Cov
gia tăng Sup
Phƣơng pháp thực hiện Chỉ lƣu ma trận độ hỗ trợ. Lƣu cả hai ma trận độ Acc và ma trận
Cov.
Tính ma trận Acc và Chỉ cập nhật cho phần tử bị thay Cập nhật cho tất cả các phần tử của
Cov khi bổsung /loại đổi trong ma trận Sup. dòng/cột trong cả 2 ma trận Acc và Cov.
bỏ một đối tƣợng Việc tính 2 ma trận Acc và Cov
chỉ thực hiện một lần.
Độ phức tạp tính toán O(|U|2) O(|U|3)
Trên cơ sở bảng so sánh trên, ta thấy thuật toán tính gia tăng Sup đƣợc đề xuất thực hiện tốt hơn so với thuật
toán tính gia tăng Acc và Cov đã đƣợc công bố.
IV. KẾT LUẬN
Trên thực tế những thay đổi do việc bổ sung và loại bỏ các phần tử trên khối quyết định là hay xảy ra, bài báo
đã đề xuất các thuật toán tính gia tăng ma trận độ hỗ trợ Sup trên khối quyết định và trên lát cắt. Từ các thuật toán
đề xuất, độ phức tạp của chúng cũng đã đƣợc phát biểu và chứng minh. Ngoài ra, việc so sánh độ phức tạp giữa thuật
toán tính gia tăng ma trận độ hỗ trợ và thuật toán tính gia tăng các ma trận Acc và Cov khi tập các đối tƣợng thay đổi
cũng đƣợc đề cập ở đây. Những kết quả nói trên là cơ sở để giúp tính gia tăng ma trận độ chính xác và ma trận độ phủ
trên khối và trên lát cắt nhanh hơn, tiết kiệm thời gian hơn, từ đó tìm ra các luật quyết định có ý nghĩa trên khối và
trên lát cắt khi tập đối tƣợng trên khối quyết định có thay đổi. Các kết quả này cũng góp phần làm phong phú thêm
ứng dụng của lí thuyết thiết kế mô hình cơ sở dữ liệu dạng khối.
TÀI LIỆU THAM KHẢO
[1] Trịnh Đình Thắng, Mô hình dữ liệu dạng khối, NXB Lao động, Hà Nội, 2011.
[2] Trịnh Đình Thắng, Trần Minh Tuyến, Phép dịch chuyển lược đồ khối và vấn đề biểu diễn bao đóng, khóa trong
mô hình dữ liệu dạng khối, Kỷ yếu Hội thảo quốc gia lần thứ XIII “Một số vấn đề chọn lọc của Công nghệ Thông
tin và Truyền thông”, (276-286), 08/2010.
- Trịnh Đình Thắng, Đỗ Thị Lan Anh, Trần Minh Tuyến, Cao Hồng Huệ 387
[3] Trinh Dinh Thang, Tran Minh Tuyen, Key and key attributes set, non-key attributes set with translation of block
schemes, International Journal of Advanced Research in Computer Science, vol. 3, No.3, (335-339), India, 2012.
[4] Trịnh Đình Thắng, Trần Minh Tuyến, Đỗ Thị Lan Anh, Khai phá luật quyết định trên khối dữ liệu có giá trị thuộc
tính thay đổi, Kỉ yếu Hội thảo quốc gia lần thứ XIX:"Một số vấn đề chọn lọc của Công nghệ Thông tin và Truyền
thông", (163-169), 2016.
[5] Liu, D., Li, T., Ruan, D., Zou, W. (2009), “An incremental approach for inducing knowledge from dynamic
information systems”, Fundam. Inform., (94), (245-260), 2009.
[6] Shi, K., Yao, B. (2008), “Function S-rough sets and decision law identification”. Science in China Series F:
Information Sciences 51, (499-510), 2008.
THE INCREMENTAL METHOD OF SUPPORT MATRIC ON THE DATA BLOCK
AND SLICE WHEN THE OBJECT SET CHANGES
Trinh Dinh Thang, Do Thi Lan Anh, Tran Minh Tuyen, Cao Hong Hue
ABSTRACT: The paper proposes an incremental method to calculate the support matrix, therefore calculating the accuracy
matrix and coverage matrix on the data block that have object set changes to generate decision laws. The incremental algorithms
calculating of the support matrix on the decision block and its slices was also proposed when increasing or decreasing the object
set ... The complexity of these algorithms on the decision block and slices were also stated and demonstrated. In addition, the
comparison complexity time of two incremental methods for caculating Sup and Acc, Cov was also mentioned here.
nguon tai.lieu . vn
