Một phương pháp gia tăng để tính độ chính xác và độ phủ của các luật quyết định trên khối dữ liệu có tập đối tượng thay đổi

Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
Một phương pháp gia tăng để tính độ chính xác
và độ phủ của các luật quyết định trên khối
dữ liệu có tập đối tượng thay đổi
Đỗ Thị Lan Anh1,2, Trịnh Đình Thắng1
1Viện Công nghệ Thông tin, Trường Đại học Sư phạm Hà Nội 2
2Học viện Khoa học Công nghệ, Viện Hàn lâm Khoa học và Công nghệ Việt Nam
Tác giả liên hệ: Đỗ Thị Lan Anh, dothilananh@hpu2.edu.vn
Ngày nhận bài: 25/09/2018, ngày sửa chữa: 17/04/2019, ngày duyệt đăng: 22/04/2019
Xem sớm trực tuyến: 26/05/2019, định danh DOI: 10.32913/mic-ict-research-vn.v2019.n1.804
Biên tập lĩnh vực điều phối phản biện và quyết định nhận đăng: PGS.TS. Lê Hoàng Sơn
Tóm tắt: Bài báo đưa ra mô hình tăng hoặc giảm tập đối tượng của khối quyết định. Từ đó trình bày các thuật toán gia
tăng để tính ma trận độ chính xác và ma trận độ phủ của các luật quyết định trên khối dữ liệu có tập đối tượng thay đổi.
Đồng thời phát biểu và chứng minh độ phức tạp của các thuật toán này.
Từ khóa: Phương pháp gia tăng, ma trận độ chính xác, ma trận độ phủ, khối dữ liệu, khối quyết định.
Title: An incremental method for calculating accuracy and coverage of decision laws on data block having changed
object set
Abstract: The paper gives a model of increasing or decreasing the object set of a decision block. From there, we present the
incremental algorithms to calculate the precision matrix and the coverage matrix of the decision laws on the data block
having the object set changed. The complexities of these algorithms have also been stated and proved.
Keywords: Incremental method, precision matrix, coverage matrix, data block, decision block.
I. GIỚI THIỆU
Việc nghiên cứu để tìm kiếm các luật quyết định trên
bảng quyết định bằng cách đánh giá các độ đo của các luật
quyết định cũng như các cách tiếp cận gia tăng, xác định
luật quyết định, v.v. đã được nhiều nhóm tác giả nghiên cứu,
chẳng hạn như trong [1–5]. Tuy nhiên, luật quyết định trên
bảng quyết định chỉ mang tính chất thời điểm mà không
áp dụng được cho cả một quá trình, một khoảng thời gian
nào đó. Khi đó, để khắc phục nhược điểm này nhóm tác
giả đã tập trung nghiên cứu và đề xuất một mô hình và
thuật toán tương ứng để phát hiện các luật quyết định trên
khối dữ liệu [6]. Trên khối quyết định, việc nghiên cứu các
tính chất khi làm mịn hoặc làm thô các giá trị của thuộc
tính chỉ số trên khối cũng đã được nhóm tác giả quan tâm
nghiên cứu [7]. Nối tiếp theo hướng nghiên cứu trên, trong
bài báo này nhóm tác giả đã đưa một phương pháp để tính
toán gia tăng ma trận độ chính xác (Acc) và độ phủ (Cov)
của các luật quyết định khi bố sung, hay loại bỏ các đối
tượng ra khỏi khối dữ liệu, đồng thời đánh giá độ phức tạp
của các thuật toán của phương pháp này.
II. CÁC KHÁI NIỆM CƠ BẢN
1. Khối
Định nghĩa 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} với i = 1, . . . ,n là các thuộc tính. Mỗi
thuộc tính Ai có miền giá trị tương ứng là dom(Ai). Một
khối r trên 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}. Nói một cách khác,
t ∈ r(R) ⇔ t = {ti : id −→ dom(Ai)}i=1,...,n .
Khối được ký hiệu là r(R), hoặc r(id; A1, A2, ..., An), hoặc
đơn giản là r .
2. Lát cắt của khối
Định nghĩa 2 ([8]): Cho R = (id; A1, A2, ..., An), và 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 = t
i
x
}
i=1,...,n ,
1
Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
trong đó tix(x) = ti(x). Khi đó r(Rx) được gọi là mội lát
cắt trên khối r(R) tại điểm x, kí hiệu là rx . Sau đây, để cho
đơn giản ta sử dụng các kí hiệu
x(i) = (x; Ai) và 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).
3. Khối thông tin
Định nghĩa 3 ([6]): Cho R = (id; A1, A2, . . . , An) và 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, A là tập các thuộc tính chỉ số
của đối tượng, V là tập giá trị của các đối tượng ứng với
thuộc tính chỉ số x(i) và chúng được xác định như sau:
A =
n⋃
i=1
id(i), V =
⋃
x(i)∈A
Vx(i) .
Cuối cùng, f : U × A→ V là hàm thông tin thỏa mãn rằng
với mọi u ∈ U và với mọi x(i) ∈ A ta có f (u) ∈ Vx(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 4 ([6]): Cho R = (id; A1, A2, . . . , An), r là
một khối trên R, và rx là lát cắt của khối r tại x ∈ id.
Khi đó, lát cắt của khối thông tin tại x là một bộ bốn
IBx = (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, Ax 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 và được xác định như sau:
Ax =
n⋃
i=1
x(i).
Tập thứ ba trong bộ, Vx , được xác định như sau:
Vx =
⋃
x(i)∈Ax
Vx(i),
trong đó Vx(i) là tập giá trị của các đối tượng ứng với thuộc
tính chỉ số x(i). Cuối cùng, fx : Ux×Ax → Vx là hàm thông
tin thỏa mãn rằng với mọi u ∈ U và với mọi x(i) ∈ Ax ta
có f (u, x(i)) ∈ Vx(i) .
4. Khối quyết định
Định nghĩa 5 ([6]): Cho khối thông tin IB = (U, A,V, f )
với U là không gian các đối tượng và A = ∪n
i=1id
(i). Khi đó,
nếu A được chia thành hai tập C và D sao cho C = ∪k
i=1x
(i),
D = ∪n
i=k+1x
(i), x ∈ id, với 1 ≤ k < n, thì khối thông tin IB
gọi là khối quyết định và kí hiệu là 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 6 ([6]): Cho khối 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, là một bộ bố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(i)∈AxVx(i) , Dx = ∪ki=1x(i), Ax = Cx ∪ Dx , Vx =
∪n
i=k+1x
(i), vớ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(i), fx : Ux × Ax → Vx là hàm thông
tin thỏa mãn rằng với mọi u ∈ U và với mọi x(i) ∈ Ax ta
có f (u, x(i)) ∈ Vx(i) .
5. Luật quyết định trên khối và trên lát cắt
Định nghĩa 7 ([6]): Cho khối quyết định DB = (U,C∪D)
với U là không gian các đối tượng, C = ∪k
i=1x
(i), D =
∪n
i=k+1x
(i), Cx = ∪k
i=1x
(i), Dx = ∪n
i=k+1x
(i), x ∈ id. Khi đó,
U/C = {C1,C2, . . . ,Cm} ,
U/Cx = {Cx1,Cx2, . . . ,Cxtx } ,
U/D = {D1,D2, . . . ,Dh} ,
U/Dx = {Dx1,Dx2, . . . ,Dxsx } ,
tương ứng là các phân hoạch được sinh ra bởi C, Cx , D,
Dx và m, h, tx , sx lần lượt là số lớp tương đương của các
phân hoạch U/C, U/Cx , U/D, U/Dx . Một luật quyết định
trên khối có dạng
Ci −→ Dj, i = 1, . . . ,m và j = 1, . . . , h
và trên lát cắt tại điểm x có dạng
Cxi −→ Dx j, i = 1, . . . , tx, và j = 1, . . . , sx .
Mệnh đề 1 ([6]): Cho khối quyết định DB = (U,C ∪D)
với U là không gian các đối tượng C = ∪k
i=1x
(i), D =
∪n
i=k+1x
(i), Cx = ∪k
i=1x
(i), Dx = ∪n
i=k+1x
(i), x ∈ id, 1 ≤ k <
n, và các phân hoạch U/C, U/Cx , U/D, U/Dx là các phân
hoạch được sinh ra bởi bởi C, Cx , D, Dx , như trong định
nghĩa 7. Khi đó, với mọi Ci ∈ U/C và với mọi Dj ∈ U/D,
i = 1, . . . ,m, j = 1, . . . , h, ta có
Ci =
⋂
x∈id
Cxpx , Dj =
⋂
x∈id
Dxqx ,
với px ∈ {1,2, . . . , tx} và qx ∈ {1,2, . . . , sx}.
Định nghĩa 8 ([6]): Cho khối quyết định DB = (U,C ∪
D), Ci ∈ U/C, Dj ∈ U/D, Cxp ∈ U/Cx , Dxq ∈ U/Dx , với
i = 1, . . . ,m, j = 1, . . . , h, p ∈ {1, . . . , tx}, q ∈ {1, . . . , 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 được cho tương ứng như sau:
Sup(Ci,Dj) =
Ci ∩ Dj  ,
Acc(Ci,Dj) =
Ci ∩ Dj 
|Ci | ,
Cov(Ci,Dj) =
Ci ∩ Dj Dj  .
2
Tập 2019, Số 1, Tháng 9
Còn độ hỗ trợ, độ chính xác và độ phủ của luật quyết định
Cxp −→ Dxq trên lát cắt của khối tại điểm x được cho
tương ứng như sau:
Sup(Cxp,Dxq) =
Cxp ∩ Dxq  ,
Acc(Cxp,Dxq) =
Cxp ∩ Dxq Cxp  ,
Cov(Cxp,Dxq) =
Cxp ∩ Dxq Dxq  .
Từ định nghĩa trên, ta có các kết quả sau:
0 ≤ Acc(Ci,Dj) ≤ 1, 0 ≤ Acc(Cxp,Dxq) ≤ 1,
h∑
j=1
Acc(Ci,Dj) = 1,
sx∑
q=1
Acc(Cxp,Dxq) = 1,
0 ≤ Cov(Ci,Dj) ≤ 1, 0 ≤ Cov(Cxp,Dxq) ≤ 1,
m∑
j=1
Cov(Ci,Dj) = 1,
tx∑
p=1
Cov(Cxp,Dxq) = 1.
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 độ hỗ trợ, độ chính xác và độ
phủ tương ứng như sau:
Sup(C,D) = ©­­«
Sup(C1,D1) · · · Sup(C1,Dh)
...
. . .
...
Sup(Cm,D1) · · · Sup(Cm,Dh)
ª®®¬ ,
Acc(C,D) = ©­­«
Acc(C1,D1) · · · Acc(C1,Dh)
...
. . .
...
Acc(Cm,D1) · · · Acc(Cm,Dh)
ª®®¬ ,
Cov(C,D) = ©­­«
Cov(C1,D1) · · · Cov(C1,Dh)
...
. . .
...
Cov(Cm,D1) · · · Cov(Cm,Dh)
ª®®¬ .
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 ([1, 7]): Cho khối quyết định DB = (U,C ∪
D), với U là không gian các đối tượng, C = ∪k
i=1x
(i), D =
∪n
i=k+1x
(i), x ∈ id. Khi đó với mọi Ci ∈ U/C và với mọi
Dj ∈ U/D, i ∈ {1, . . . ,m} và j ∈ {1, . . . , h}, ta có
Acc(Ci,Dj) =
Sup(Ci,Dj)∑h
q=1 Sup(Ci,Dq)
,
Cov(Ci,Dj) =
Sup(Ci,Dj)∑m
p=1 Sup(Cp,Dj)
.
III. KẾT QUẢ
1. Mô hình 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
Cho khối quyết định DB = (U,C ∪ D,V, f ) như trong
định nghĩa 7. 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ỏ cũng ở khối này
M đối tượng, kí hiệu DM . Khi đó, ta cần tính các ma trận
độ chính xác Acc và ma trận độ phủ Cov trên khối và trên
lát cắt sau khi bổ sung và loại bỏ các đối tượng của khối
quyết định. Các kết quả này sẽ giúp tìm ra các luật quyết
định trên khối và trên lát cắt.
Giả sử 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 , q lớp tương đươ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 Cxi ∈ U/Cx (i = 1, . . . , tx+px)
và trong Ni đối tượng này có Ni j đối tượng được bổ sung
cho lớp Dj ∈ U/D ( j = 1, . . . , h + q), còn trên lát cắt
tại x thì trong Nxi đối tượng này có Nxi j đối tượng được
bổ sung cho lớp Dx j ∈ U/Dx ( j = 1, . . . , sx + qx). 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ó Mi j đối tượng bị loại bỏ khỏi
lớp Di ( j = 1, . . . , h), còn trên lát cắt tại x thì trong Mxi
( j = 1, . . . , sx) đối tượng bị loại bỏ khỏi lớp Dx j ∈ U/Dx .
Từ mô hình này ta có
Ni =
h+q∑
j=1
Ni j, N =
m+p∑
i=1
Ni =
m+p∑
i=1
h+q∑
j=1
Ni j,
Mi =
h∑
j=1
Mi j, M =
m∑
i=1
Mi =
m∑
i=1
h∑
j=1
Mi j,
Nxi =
sx+qx∑
j=1
Nxi j, Nx =
tx+px∑
i=1
Nxi =
tx+px∑
i=1
sx+qx∑
j=1
Nxi j,
Mxi =
sx∑
j=1
Mxi j, Mx =
tx∑
i=1
Mxi =
tx∑
i=1
sx∑
j=1
Mxi j .
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 ′x2, . . . ,C ′xtx , . . .} ,
U/D = {D′1,D′2, . . . ,D′h, . . .} ,
U/Dx = {D′x1,D′x2, . . . ,D′xsx , . . .} .
Từ định nghĩa ta thấy Ci và C ′i (i = 1, . . . ,m) chỉ khác
nhau về số lượng phần tử khi bổ sung và loại bỏ các đối
tượng, nghĩa là với mọi a ∈ C ta có f (C ′i ,a) = f (Ci,a),
3
Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
còn với các lớp từ C ′
m+1, C
′
m+2, . . ., C
′
m+p là các lớp tương
đương điều kiện hoàn toàn mới. Trên lát cắt tại x thì Cxi
và C ′xi (i = 1, . . . , tx) cũng chỉ khác nhau về số lượng phần
tử sau khi bổ sung và loại bỏ các đối tượng và với mọi
a ∈ C ta có f (C ′xi,a) = f (Cxi,a), còn với các lớp từ C ′xi
(i = tx + 1, . . . , tx + px) là các lớp tương đương điều kiện
hoàn toàn mới.
Tương tự, Di và D′i (i = 1, . . . , h) cũng chỉ khác nhau về
số lượng phần tử, nghĩa là với mọi a ∈ D ta có f (D′i,a) =
f (Di,a), còn với các lớp từ D′h+1, D′h+2, . . . ,D′h+q là các
lớp tương đương quyết định hoàn toàn mới. Trên lát cắt tại
x thì Dxi và D′xi (i = 1, . . . , sx) cũng chỉ khác nhau về số
lượng phần tử sau khi bổ sung và loại bỏ các đối tượng,
còn các lớp từ D′
hj
( j = sx +1, . . . , sx +qx) là các lớp tương
đương quyết định hoàn toàn mới.
Từ tính chất trên của các lớp tương đương điều kiện, các
lớp tương đương quyết định trên khối và trên lát cắt ta có
mối quan hệ giữa số lượng các phần tử của các lớp này
như sau:
|C ′i | =
{
|Ci | + Ni − Mi, i = 1, . . . ,m,
Ni, i = m + 1, . . . ,m + p,
|C ′i | =
{
|Ci | +∑h+qj=1 Ni j −∑hj=1 Mi j, i = 1, . . . ,m,∑h+q
j=1 Ni j, i = m + 1, . . . ,m + p,
|D′j | =
{
|Dj | +∑m+pi=1 Ni j −∑mi=1 Mi j, j = 1, . . . , h,∑m+p
i=1 Ni j, j = h + 1, . . . , h + q,
|C ′xi | =
{
|Cxi | + Nxi − Mxi, i = 1, . . . ,m,
Nxi, i = m + 1, . . . ,m + p,
|C ′xi | =
{
|Cxi | +∑sx+qxj=1 Nxi j −∑sxj=1 Mxi j, i = 1, . . . , tx,∑sx+qx
j=1 Nxi j, i = tx + 1, . . . , tx + px,
|D′x j | =
{
|Dx j | +∑tx+pxi=1 Nxi j −∑txi=1 Mxi j, j = 1, . . . , sx,∑tx+px
i=1 Nxi j, j = sx + 1, . . . sx + qx .
Mệnh đề 3: Cho khối quyết định DB = (U,C ∪D,V, f ),
AN và DM là tập các đối tượng bổ sung và loại bỏ tương
ứng đối với khối quyết định DB. Khi đó ma trận độ chính
xác trên khối quyết định sau khi bổ sung N và loại bỏ M
đối tượng với i ∈ {1, . . . ,m + p} và j ∈ {1, . . . , h + q} sẽ là
Acc(C ′,D′) = Acc(C ′i ,D′j)ix j,
với i ∈ {1, . . . ,m} và j ∈ {1, . . . , h} sẽ là
Acc(C ′i ,D′j) =
|Ci ∩ Dj | + Ni j − Mi j
|Ci | +∑h+qj′=1 Ni j′ −∑hj′=1 Mi j′ ,
với i ∈ {1, . . . ,m} và j ∈ {h + 1, . . . , h + q} sẽ là
Acc(C ′i ,D′j) =
Ni j
|Ci | +∑h+qj′=1 Ni j′ −∑hj′=1 Mi j′ ,
và với i ∈ {m + 1, . . . ,m + p} và j ∈ {1, . . . , h + q} sẽ là
Acc(C ′i ,D′j) =
Ni j∑h+q
j=1 Ni j′
.
Chứng minh: Ta lần lượt xác định giá trị của
Acc(C ′i ,D′j) theo ba trường hợp sau.
(i) i = 1, . . . ,m và j = 1, . . . , h: Theo định nghĩa, ta có
Acc(C ′i ,D′j) =
|C ′i ∩ D′j |
|C ′i |
.
Khi đó
|C ′i ∩ D′j | = |Ci ∩ Dj | + Ni j − Mi j = A1,
|C ′i | = |Ci | + Ni − Mi = |Ci | +
h+q∑
j′=1
Ni j′ −
h∑
j′=1
Mi j′ = B1.
Kết quả này cho ta
Acc(C ′i ,D′j) =
|C ′i ∩ D′j |
|C ′i |
=
A1
B1
.
(ii) i = 1, . . . ,m và j = h+1, . . . , h+q: Theo định nghĩa,
ta có
Acc(C ′i ,D′j) =
|C ′i ∩ D′j |
|C ′i |
.
Khi đó
|C ′i ∩ D′j | = Ni j = A2,
|C ′i | = |Ci | + Ni − Mi = |Ci | +
h+q∑
j=1
Ni j −
h∑
j=1
Mi j = B2.
Suy ra
Acc(C ′i ,D′j) =
|C ′i ∩ D′j |
|C ′i |
=
A2
B2
.
(iii) i = m + 1, . . . ,m + p và j = 1, . . . , h + q: Theo định
nghĩa, ta có
Acc(C ′i ,D′j) =
|C ′i ∩ D′j |
|C ′i |
.
Khi đó
|C ′i ∩ D′j | = Ni j = A3,
|C ′i | =
h+q∑
j=1
Ni j = B3.
Từ đó
Acc(C ′i ,D′j) =
|C ′i ∩ D′j |
|C ′i |
=
A3
B3
.

4
Tập 2019, Số 1, Tháng 9
Mệnh đề 4: Cho khối quyết định DB = (U,C ∪D,V, f ),
AN và DM là tập các đối tượng bổ sung và loại bỏ tương
ứng đối với khối quyết ... 1,D
′
k
) = Cov(C ′
m+1,D
′
k
) = 0. Nếu
i , m + 1 thì Acc(C ′i ,D′j∗ ) = Acc(Ci,Dj∗ ) và
Cov(C ′i ,D′j∗ ) =
|Ci ∩ DJ∗ |
|Dj∗ | + 1 .
Mặt khác, với mọi i , m + 1 và mọi j , j∗, ta có
Acc(C ′i ,D′j) = Acc(Ci,Dj) và Cov(C ′i ,D′j) = Cov(Ci,Dj).
(iii) Chỉ sinh lớp quyết định mới: Trường hợp này, x <
Dj ( j = 1, . . . , h) và tồn tại i∗ < {1, . . . ,m} sao cho x ∈ Ci∗ .
Suy ra x ∈ D′
h+1 và x ∈ C ′i∗ . Do đó Cov(C ′i∗,D′h+1) = 1 và
Acc(C ′i∗,D′h+1) =
1
|Ci∗ | + 1 .
Nếu i , i∗ thì Acc(C ′i ,D′h+1) = Cov(C ′i ,D′h+1) = 0. Nếu
k , h + 1 thì Cov(C ′i∗,D′k) = Cov(Ci∗,Dk) và
Acc(C ′i∗,D′k) =
|Ci ∩ Dk |
|Ci∗ | + 1 .
Mặt khác, với mọi i , i∗ và mọi j , h + 1 ta có
Acc(C ′i ,D′j) = Acc(Ci,Dj), và Cov(C ′i ,D′j) = Cov(Ci,Dj).
(iv) Không sinh thêm lớp điều kiện mới hoặc lớp quyết
định mới: Với trường hợp này, tồn tại i∗ ∈ {1, . . . ,m} sao
cho x ∈ Ci∗ và tồn tại j∗ ∈ {1, . . . , h} sao cho x ∈ Di∗ . Như
vậy, việc bổ sung phần tử x sẽ tăng thêm số phần tử của
Ci∗ và Di∗ . Khi đó
Acc(C ′i∗,D′j∗ ) =
|Ci∗ ∩ Dj∗ | + 1
|Ci∗ | + 1 ,
Cov(C ′i∗,D′j∗ ) =
|Ci∗ ∩ Dj∗ | + 1
|Di∗ | + 1 .
Nếu k , j∗ thì Cov(C ′i∗,D′k) = Cov(Ci∗,Dk) và
Acc(C ′i∗,D′k) =
|Ci∗ ∩ Dk | + 1
|Ci∗ | + 1 .
Nếu u , i∗ thì Acc(C ′u,D′j∗ ) = Acc(Cu,Dj) và
Cov(C ′u,D′j∗ ) =
|Cu ∩ Dj∗ | + 1
|Dj∗ | + 1 .
Nếu i , i∗ và j , j∗ thì Acc(C ′i ,D′j) = Acc(Ci,Dj) và
Cov(C ′i ,D′j) = Cov(Ci,Dj).
2) Loại bỏ phần tử x ra khỏi khối quyết định: Với trường
hợp này, tồn tại i∗ ∈ {1, . . . ,m} sao cho x ∈ Ci∗ và tồn tại
j∗ ∈ {1, . . . , h} sao cho x ∈ Dj∗ . Như vậy, việc loại bỏ phần
tử x sẽ làm giảm đi số phần tử của Ci∗ và Di∗ . Khi đó
Acc(C ′i∗,D′j∗ ) =
|Ci∗ ∩ Dj∗ | − 1
|Ci∗ | − 1 ,
Cov(C ′i∗,D′j∗ ) =
|Ci∗ ∩ Dj∗ | − 1
|Di∗ | − 1 .
Nếu k , j∗ thì Cov(C ′i∗,D′k) = Cov(Ci∗,Dk) và
Acc(C ′i∗,D′k) =
|Ci∗ ∩ Dk |
|Ci∗ | − 1 .
Thuật toán 1: Tính toán các ma trận Acc và Cov
trước khi bổ sung và loại bỏ các đối tượng
Dữ liệu vào:
• Các lớp tương đương điều kiện Ci với i = 1, . . . ,m
• Các lớp tương đương quyết định Dj với i = 1, . . . , h
Dữ liệu ra:
• Ma trận Acc(C,D) và ma trận Cov(C,D)
// Tính đồng thời cả hai ma trận Acc và Cov
for i = 1 : m do
for j = 1 : h do
Acc(Ci,Dj ) =
|Ci ∩ Dj |
|Ci | ;
Cov(Ci,Dj ) =
|Ci ∩ Dj |
|Dj | .
end
end
Nếu u , i∗ thì Acc(C ′u,D′j∗ ) = Acc(Cu,Dj∗ ) và
Cov(C ′u,D′j∗ ) =
|Cu ∩ Dj∗ |
|Dj∗ | − 1 .
Nếu i , i∗ và j , j∗ thì Acc(C ′i ,D′j) = Acc(Ci,Dj) và
Cov(C ′i ,D′j) = Cov(Ci,Dj).
Nhận xét: Khi thực hiện thao tác loại bỏ phần tử ra khỏi
khối quyết định có thể xảy ra trường hợp một lớp tương
đương điều kiện hoặc một lớp tương đương quyết định có
thể trở thành rỗng. Khi đó ta có hai trường hợp sau:
• Nếu C ′i = œ (i = 1, . . . ,m) thì Ci ∩ Dj = œ. Suy raCi ∩ Dj  = 0, nghĩa là tất cả các phần tử ở dòng i của
ma trận Acc(C ′,D′) và dòng i của ma trận Cov(C ′,D′)
đều bằng 0.
• Nếu D′j = œ (i = 1, . . . , h) thì Ci ∩ Dj = œ. Suy raCi ∩ Dj  = 0, nghĩa là tất cả các phần tử ở cột j của
ma trận Acc(C ′,D′) và cột j của ma trận Cov(C ′,D′)
đều bằng 0.
Do đó, trước khi tiến hành sinh các luật quyết định có ý
nghĩa thì ta cần thực hiện việc loại bỏ các dòng/cột của ma
trận Acc và ma trận Cov mà có toàn giá trị 0.
3. Các thuật toán tính gia tăng Acc và Cov sau khi
bổ sung và loại bỏ các phần tử
Sau đây, phương pháp tính các ma trận Acc và Cov trước
khi bổ sung và loại bỏ các đối tượng được trình bày trong
Thuật toán 1. Phương pháp tính gia tăng các ma trận Acc
và Cov sau khi bổ sung các phần tử được trình bày trong
Thuật toán 2. Phương pháp tính gia tăng các ma trận Acc
và Cov sau khi loại bỏ các phần tử được trình bày trong
Thuật toán 3. Cuối cùng, phương pháp loại bỏ dòng/cột
trong các ma trận Acc và Cov mà có toàn giá trị 0 được
trình bày trong Thuật toán 4.
7
Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
Thuật toán 2: Tính toán gia tăng các ma trận
Acc và Cov sau khi bổ sung các phần tử
Dữ liệu vào:
• Các lớp tương đương điều kiện Ci với i = 1, . . . ,m
• Các lớp tương đương quyết định Dj với j = 1, . . . , h
• Tập AN chứa N phần tử bổ sung
Dữ liệu ra:
• Ma trận Acc(C′,D′) và ma trận Cov(C′,D′)
foreach x ∈ AN do
p = 0;
for i = 1 : m + p do
q = 0;
for j = 1 : h + q do
Thực hiện trường hợp (i) của mục III.2.1;
p = p + 1 và q = q + 1;
end
if ∀x < Ci và ∃ j∗ : x ∈ Dj∗ then
Thực hiện trường hợp (ii) của mục III.2.1;
p = p + 1;
end
if ∃i∗ : x ∈ Ci∗ và ∀ j : x < Dj then
Thực hiện trường hợp (iii) của mục III.2.1;
q = q + 1;
end
if ∃i∗ : x ∈ Ci∗ và ∃ j∗ : x ∈ Dj∗ then
Thực hiện trường hợp (iv) của mục III.2.1;
end
end
end
Thuật toán 3: Tính toán gia tăng các ma trận
Acc và Cov sau khi loại bỏ các phần tử
Dữ liệu vào:
• Các lớp tương đương điều kiện Ci với i = 1, . . . ,m
• Các lớp tương đương quyết định Dj với j = 1, . . . , h
• Tập DM chứa M phần tử bị loại bỏ
Dữ liệu ra:
• Ma trận Acc(C′,D′) và ma trận Cov(C′,D′)
foreach x ∈ DM do
for i = 1 : m do
for j = 1 : h do
Thực hiện trường hợp ở mục III.2.2;
end
end
end
4. Độ phức tạp của các thuật toán tính gia tăng Acc
và Cov sau khi bổ sung và loại bỏ các phần tử trên
khối quyết định
Mệnh đề 7: Độ phức tạp thuật toán xác định Acc và
Cov là O(|U |2).
Chứng minh: Ta có lực lượng trung bình của lớp tương
đương điều kiện và lớp tương đương quyết định tương ứng
là |U |/m, |U |/h. Vì có tất cả m × h phần tử, nên để tính
độ chính xác và độ phủ của một luật số phép tính cần thực
Thuật toán 4: Loại bỏ dòng/cột trong các ma
trận Acc và Cov mà có toàn giá trị 0
Dữ liệu vào:
• Ma trận Acc(C′,D′)
• Ma trận Cov(C′,D′)
Dữ liệu ra:
• Ma trận Acc(C′,D′) và ma trận Cov(C′,D′) sau khi đã
loại bỏ dòng/cột toàn giá trị 0
// Thực hiện xóa dòng toàn giá trị 0
for i = 1 : m + p do
kt = 0;
for j = 1 : h + q do
if Acc(C′i ,D′j ) , 0 và Cov(C′i ,D′j ) , 0 then
kt = 1;
break;
end
end
if kt = 0 then
Xóa dòng i, loại bỏ C′i ;
p = p − 1;
i = i − 1;
end
end
// Thực hiện xóa cột toàn giá trị 0.
for j = 1 : h + q do
kt = 0;
for i = 1 : m + p do
if Acc(C′i ,D′j ) , 0 và Cov(C′i ,D′j ) , 0 then
kt = 1;
break;
end
end
if kt = 0 then
Xóa cột j, loại bỏ D′j ;
q = q − 1;
j = j − 1;
end
end
hiện sẽ là |U |
m
× |U |
h
× m × h = |U |2.
Do đó độ phức tạp thời gian của thuật toán này là O(|U |2).

Mệnh đề 8: Độ phức tạp thuật toán tính gia tăng Acc
và Cov khi bổ sung N đối tượng là O(N |U |2).
Chứng minh: Khi bổ sung đối tượng x, để kiểm tra
xem x thuộc lớp tương đương điều kiện nào ta cần thực hiện
sm phép so sánh, để kiểm tra x thuộc lớp tương đương quyết
định nào ta cần sh phép so sánh. Do đó, việc kiểm tra phần
tử x mới bổ sung cần sm + sh phép so sánh (sm và sh là
số lớp tương đương điều kiện và số lớp tương đương quyết
định tương ứng).
Cập nhật các ma trận Acc và Cov khi bổ sung x, ta có
bốn trường hợp sau.
(i) Nếu hình thành một lớp điều kiện mới và một lớp
quyết định mới thì cả hai ma trận Acc và Cov đều được bổ
8
Tập 2019, Số 1, Tháng 9
sung thêm một dòng mới (kí hiệu là i∗) và một cột mới (kí
hiệu là j∗). Như vậy ta có Acc(C ′i∗,D′j∗ ) = Cov(C ′i∗,D′j∗ ) =
1; Acc(C ′i∗,D′j∗ ) = Cov(C ′i∗,D′j∗ ) = 0, ( j = 1, . . . , sh);
Acc(C ′i∗,D′j∗ ) = Cov(C ′i∗,D′j∗ ) = 0, (i = 1, . . . , sm). Độ chính
xác và độ phủ của các luật còn lại không thay đổi. Do vậy,
trường hợp này chỉ cần 2(sm + sh + 1) phép gán.
(ii) Nếu chỉ hình thành lớp điều kiện mới, còn số lớp
quyết định không đổi thì hai ma trận Acc và Cov được bổ
sung thêm dòng mới i∗ và x sẽ làm ảnh hưởng đến cột j∗
của hai ma trận này. Như vậy, x ∈ C ′i∗ và x ∈ D′j∗ , suy
ra C ′i∗ ∩ D′j∗ = {x}, còn C ′u ∩ D′j∗ không đổi nếu u , i∗,
C ′i∗ ∩ D′k = œ nếu k , j∗. Từ đó ta có Acc(C ′i∗,D′j∗ ) =
Cov(C ′i∗,D′j∗ ) = 1. Nếu u , i∗ thì Acc(C ′u,D′j∗ ) không đổi và
Cov(C ′u,D′j∗ ) =
|C ′u ∩ D′j∗ |
|D′j∗ | + 1
. (1)
Nếu k , j∗ thì Acc(C ′i∗,D′k) = Cov(C ′i∗,D′k) = 0. Độ chính
xác và độ phủ của các luật còn lại không thay đổi. Do
đó, độ phức tạp trong trường hợp này phụ thuộc vào việc
tính Cov(C ′u,D′j∗ ). Khi đó, để xác định Cov(C ′u,D′j∗ ) ta cần
sm−1 phép cộng để tính tổng giá trị các phần tử của cột j∗,
sm phép tính Sup(C ′u,D′j∗ ). Với mỗi phép tính Sup(C ′u,D′j∗ )
cần (|U |/sm) × (|U |/sk) phép tính và sm phép chia. Từ đó
suy ra số phép tính cần thực hiện là
sm − 1 + sm |U |sm
|U |
sk
+ sm = 2sm +
|U |2
sk
− 1.
(iii) Nếu chỉ hình thành lớp quyết định mới, còn số lớp
điều kiện không đổi thì tương tự như trường hợp (ii) thì
ta chỉ cần thay đổi cột thành dòng: j∗ thành i∗, tổng cột
thành tổng dòng, Cov thành Acc. Như vậy, số phép tính
trong trường hợp này là 2sm + (|U |2/sm) − 1.
(iv) Nếu không hình thành lớp điều kiện mới, cũng không
hình thành lớp quyết định mới thì việc thực hiện trong
trường hợp này tương tự với việc thực hiện đồng thời cả
hai trường hợp 2 và 3. Từ đó số phép tính cần thực hiện sẽ là
2(sm + sh) + |U |
2
sm
+
|U |2
sk
− 2.
Do đó, với mỗi phần tử x được bổ sung thì trường hợp xấu
nhất ta phải thực hiện số phép tính là
2(sm + sh)
(
sm + sh +
|U |2
sm
+
|U |2
sk
− 2
)
.
Như vậy, số phép tính cần thực hiện khi bổ sung N phần
tử sẽ là
2N(sm + sh)
(
sm + sh +
|U |2
sm
+
|U |2
sk
− 2
)
.
Trong quá trình tính toán các ma trận Acc và Cov thì sm
dần tới m+p, sh dần tới h+q, do đó sm ≤ m+p, sh ≤ h+q
nên ta có thể coi sm = m + p, sh = h + q. Từ đó suy ra số
phép tính cần thực hiện để cập nhật cho các ma trận Acc
và Cov khi bổ sung N phần tử là
N(m + p + h + q)
(
2(m + p + h + q) + |U |
2
m + p
+
|U |2
h + q
− 2
)
.
Mặt khác, vì m, h ≤ |U |, suy ra độ phức tạp của thuật
toán là O(N |U |2). 
Mệnh đề 9: Độ phức tạp thuật toán tính gia tăng Acc
và Cov khi loại bỏ M đối tượng là O(M |U |2).
Chứng minh: Khi loại bỏ đối tượng x, để kiểm tra xem
x thuộc lớp tương đương điều kiện nào ta cần thực hiện sm
phép so sánh, để kiểm tra x thuộc lớp tương đương quyết
định nào ta cần sh phép so sánh. Do đó, việc kiểm tra phần
tử x để loại bỏ cần sm+ sh phép so sánh (sm và sh là số lớp
tương đương điều kiện và số lớp tương đương quyết định
tương ứng).
Cập nhật các ma trận Acc và Cov khi loại bỏ x. Khi loại
bỏ x sẽ làm thay đổi đến dòng i∗ và đến cột j∗ của các
ma trận Acc và Cov, do đó thực hiện này giống như việc
thực hiện trường hợp (iv) trong chứng minh của mệnh đề 8.
Từ đó suy ra số phép tính cần thực hiện khi xóa đi M đối
tượng trên khối quyết định sẽ là
M(sm + sh)
(
2(sm + sh) + |U |
2
sm
+
|U |2
sk
− 2
)
.
Tương tự như chứng minh ở mệnh đề 8, ta xem sm = m+ p
và sh = h + q, khi đó số phép tính cần thực hiện để cập
nhật các ma trận Acc và Cov khi loại bỏ M đối tượng là
M(m + p + h + q)
(
2(m + p + h + q) + |U |
2
m + p
+
|U |2
h + q
− 2
)
.
Do m, h ≤ |U |, suy ra độ phức tạp của thuật toán là
O(M |U |2). 
Mệnh đề 10: Độ phức tạp thuật toán xóa dòng/cột của
ma trận Acc và Cov có toàn giá trị 0 là O(|U |2).
Chứng minh: Với mỗi dòng của ma trận Acc và Cov
có toàn giá trị 0 thì ta cần thực hiện h+q phép kiểm tra và
h+q phép xóa từng phần tử của dòng này. Tiếp đó thực hiện
một phép xóa Ci ra khỏi U/C và hai phép gán. Như vậy ta
cần thực hiện 2(h+q)+3 phép tính để xóa một dòng. Trong
trường hợp xấu nhất ta cần thực hiện (m + p)(2(h + q) + 3)
phép tính để xóa hết tất cả m+ p dòng của các ma trận Acc
và Cov.
Với mỗi cột có tất cả các phần tử bằng 0 trong các ma
trận Acc và Cov thì tương tự như trên trong trường hợp xấu
nhất ta cần thực hiện (h + q)(2(m + p) + 3) phép tính để
xóa hết tất cả h + q cột của các ma trận Acc và Cov. Do
m, h ≤ |U |, suy ra độ phức tạp của thuật toán là O(|U |2).

9
Các công trình nghiên cứu phát triển Công nghệ Thông tin và Truyền thông
IV. KẾT LUẬN
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, bài báo đã phát biểu và chứng minh
một số tính chất của các ma trận Acc và Cov, đề xuất một
số thuật toán tính gia tăng của các ma trận độ chính xác và
ma trận độ phủ 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. 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, từ các kết quả đó 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] T. D. Thắng and D. T. L. Anh, “Một số thuật toán xác định
ma trận độ hỗ trợ trên khối dữ liệu có giá trị thuộc tính thay
đổi,” in Kỷ yếu Hội thảo quốc gia lần thứ XXI: Một số vấn
đề chọn lọc của Công nghệ Thông tin và Truyền thông, 2018,
pp. 216–225.
[2] C. C. Nghĩa, “Nghiên cứu các phương pháp rút gọn thuộc
tính và sinh luật quyết định theo tiếp cận tập thô mờ,” Ph.D.
dissertation, Học viện Công nghệ Bưu chính Viễn thông,
2017.
[3] D. Liu, T. Li, D. Ruan, and W. Zou, “An incremental approach
for inducing knowledge from dynamic information systems,”
Fundamenta Informaticae, vol. 94, no. 2, pp. 245–260, 2009.
[4] K. Shi and B. Yao, “Function s-rough sets and law identi-
fication,” Science in China Series F: Information Sciences,
vol. 51, no. 5, p. 499, 2008.
[5] V. Putrenko, N. Pashvnska, and S. Nazarenko, “Data mining
of network events with space-time cube application,” in 2018
IEEE Second International Conference on Data Stream Min-
ing & Processing (DSMP), 2018, pp. 79–83.
[6] T. D. Thắng, T. M. Tuyến, and D. T. L. Anh, “Khai phá luật
quyết định trên khối dữ liệu có giá trị thuộc tính thay đổi,”
in 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, 2016,
pp. 163–169.
[7] T. D. Thắng, T. M. Tuyến, D. T. L. Anh, and N. T. Quyên,
“Một số kết quả về khai phá luật quyết định trên khối dữ liệu
có giá trị thuộc tính thay đổi,” in Kỷ yếu Hội nghị Khoa học
công nghệ quốc gia lần thứ X (FAIR), 2017, pp. 623–632.
[8] T. D. Thang and T. M. 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, pp. 335–339, 2012.
Đỗ Thị Lan Anh sinh năm 1988 tại Hà
Nam. Tốt nghiệp Cử nhân Tin học tại Đại
học Sư phạm Hà Nội 2 năm 2006. Tốt
nghiệp Thạc sĩ Khoa học máy tính tại Đại
học Sư phạm Hà Nội 2 năm 2013. Hiện
tại công tác tại Viện Công nghệ Thông tin,
Trường Đại học Sư phạm Hà Nội 2 và là
nghiên cứu sinh tiến sỹ năm thứ tư tại Học
viện Khoa học Công nghệ, Viện Hàn lâm Khoa học và Công nghệ
Việt Nam. Lĩnh vực nghiên cứu bao gồm khai phá dữ liệu và cơ
sở dữ liệu.
Trịnh Đình Thắng sinh năm 1955 tại Hà
nội. Tốt nghiệp Cử nhân Toán tại Đại học
Sư phạm Hà Nội 1 năm 1977. Tốt nghiệp
Thạc sĩ Toán học tại Đại học Sư phạm
Hà Nội 1 năm 1986. Tốt nghiệp Tiến sỹ
Công nghệ thông tin tại Viện Công nghệ
Thông tin, Viện Hàn lâm Khoa học và
Công nghệ Việt Nam. Hiện công tác tại
Viện Công nghệ Thông tin, Trường Đại học Sư phạm Hà Nội 2.
Lĩnh vực nghiên cứu bao gồm cơ sở dữ liệu, khai phá dữ liệu,
mạng máy tính.
10