- Trang Chủ
- Kĩ thuật Viễ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
Xem mẫu
- 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
1 Viện Công nghệ Thông tin, Trường Đại học Sư phạm Hà Nội 2
2 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
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 II. CÁC KHÁI NIỆM CƠ BẢN
1. Khối
Việc nghiên cứu để tìm kiếm các luật quyết định trên Định nghĩa 1: Gọi R = (id; A1, A2, . . . , An ) là một bộ
bảng quyết định bằng cách đánh giá các độ đo của các luật hữu hạn các phần tử, trong đó id là tập chỉ số hữu hạn
quyết định cũng như các cách tiếp cận gia tăng, xác định khác rỗng, { Ai } với i = 1, . . . , n là các thuộc tính. Mỗi
luật quyết định, v.v. đã được nhiều nhóm tác giả nghiên cứu, thuộc tính Ai có miền giá trị tương ứng là dom(Ai ). Một
chẳng hạn như trong [1–5]. Tuy nhiên, luật quyết định trên khối r trên R gồm một số hữu hạn phần tử mà mỗi phần
bảng quyết định chỉ mang tính chất thời điểm mà không tử là một họ các ánh xạ từ tập chỉ số id đến các miền trị
áp dụng được cho cả một quá trình, một khoảng thời gian của các thuộc tính { Ai }. Nói một cách khác,
nào đó. Khi đó, để khắc phục nhược điểm này nhóm tác
t ∈ r(R) ⇔ t = t i : id −→ dom(Ai ) i=1,...,n .
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 được ký hiệu là r(R), hoặc r(id; A1, A2, ..., An ), hoặc
khối dữ liệu [6]. Trên khối quyết định, việc nghiên cứu các đơn giản là r.
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 2. Lát cắt của khối
bài báo này nhóm tác giả đã đưa một phương pháp để tính Định nghĩa 2 ([8]): Cho R = (id; A1, A2, ..., An ), và r(R)
toán gia tăng ma trận độ chính xác (Acc) và độ phủ (Cov) là một khối trên R. Với mỗi x ∈ id ta kí hiệu r(Rx ) là một
của các luật quyết định khi bố sung, hay loại bỏ các đối khối với Rx = ({x}; A1, A2, . . . , An ) sao cho
tượng ra khỏi khối dữ liệu, đồng thời đánh giá độ phức tạp
tx ∈ r(Rx ) ⇔ tx = t i = t i
- ,
-
của các thuật toán của phương pháp này. x 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 đó txi (x) = t i (x). Khi đó r(Rx ) được gọi là mội lát Định nghĩa 6 ([6]): Cho khối DB = (U, C∪D,V, f ) với C
cắt trên khối r(R) tại điểm x, kí hiệu là rx . Sau đây, để cho là tập các thuộc tính chỉ số điều kiện và D là tập các thuộc
đơn giản ta sử dụng các kí hiệu 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, C x ∪D x ,Vx , fx ) với U là
x (i) = (x; Ai ) và id (i) = {x (i) | x ∈ id}.
tập các đối tượng thuộc r gọi là không gian các đối tượng,
Ta gọi x (i) (x ∈ id, i = 1, . . . , n) là các thuộc tính chỉ số của C x = ∪x (i) ∈ A x Vx (i) , D x = ∪i=1
k x (i) , A = C x ∪ D x , V =
x x
lược đồ khối R = (id; A1, A2, . . . , An ).
n
∪i=k+1 x (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
3. Khối thông tin có f (u, x (i) ) ∈ Vx (i) .
Đị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 5. Luật quyết định trên khối và trên lát cắt
I B = (U, A,V, f ) với U là tập các đối tượng thuộc r gọi là Định nghĩa 7 ([6]): Cho khối quyết định DB = (U, C∪D)
không gian các đối tượng, A là tập các thuộc tính chỉ số với U là không gian các đối tượng, C = ∪i=1 k x (i) , D =
của đối tượng, V là tập giá trị của các đối tượng ứng với ∪i=k+1 x , C = ∪i=1 x , D = ∪i=k+1 x , x ∈ id. Khi đó,
n (i) x k (i) x n (i)
thuộc tính chỉ số x (i) và chúng được xác định như sau:
U/C = {C1, C2, . . . , Cm } ,
n
U/C x = Cx1, Cx2, . . . , Cxtx ,
Ø Ø
A= id (i), V= Vx (i) .
i=1 x (i) ∈ A U/D = {D1, D2, . . . , Dh } ,
U/D x = Dx1, Dx2, . . . , Dxsx ,
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 tương ứng là các phân hoạch được sinh ra bởi C, C x , D,
đó, ta gọi f (u, x (i) ) là giá trị của đối tượng u tại thuộc tính D x và m, h, tx , sx lần lượt là số lớp tương đương của các
chỉ số x (i) . phân hoạch U/C, U/C x , U/D, U/D x . Một luật quyết định
Định nghĩa 4 ([6]): Cho R = (id; A1, A2, . . . , An ), r là trên khối có dạng
một khối trên R, và rx là lát cắt của khối r tại x ∈ id. Ci −→ D j , i = 1, . . . , m và j = 1, . . . , h
Khi đó, lát cắt của khối thông tin tại x là một bộ bốn
I Bx = (U, Ax ,Vx , fx ) với U là tập các đối tượng thuộc r gọi và trên lát cắt tại điểm x có dạng
là không gian các đối tượng, Ax là tập các thuộc tính chỉ số Cxi −→ Dx j , i = 1, . . . , tx , và j = 1, . . . , sx .
của đối tượng trên lát cắt tại x và được xác định như sau:
Mệnh đề 1 ([6]): Cho khối quyết định DB = (U, C ∪ D)
n
Ø với U là không gian các đối tượng C = ∪i=1 k x (i) , D =
Ax = x (i) .
∪i=k+1 x , C = ∪i=1 x , D = ∪i=k+1 x , x ∈ id, 1 ≤ k <
n (i) x k (i) x n (i)
i=1
n, và các phân hoạch U/C, U/C x , U/D, U/D x là các phân
Tập thứ ba trong bộ, Vx , được xác định như sau: hoạch được sinh ra bởi bởi C, C x , D, D x , như trong định
Ø
Vx = Vx (i) , nghĩa 7. Khi đó, với mọi Ci ∈ U/C và với mọi D j ∈ U/D,
x (i) ∈ A x i = 1, . . . , m, j = 1, . . . , h, ta có
Ù Ù
trong đó Vx (i) là tập giá trị của các đối tượng ứng với thuộc Ci = Cx p x , D j = Dxqx ,
x ∈id x ∈id
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 với px ∈ {1, 2, . . . , tx } và qx ∈ {1, 2, . . . , sx }.
có f (u, x (i) ) ∈ Vx (i) . Định nghĩa 8 ([6]): Cho khối quyết định DB = (U, C ∪
D), Ci ∈ U/C, D j ∈ U/D, Cx p ∈ U/C x , Dxq ∈ U/D x , với
i = 1, . . . , m, j = 1, . . . , h, p ∈ {1, . . . , tx }, q ∈ {1, . . . , sx },
4. Khối quyết định x ∈ id.
Định nghĩa 5 ([6]): Cho khối thông tin I B = (U, A,V, f ) Khi đó, độ hỗ trợ, độ chính xác và độ phủ của luật quyết
với U là không gian các đối tượng và A = ∪i=1
n id (i) . Khi đó, định Ci −→ D j trên khối được cho tương ứng như sau:
nếu A được chia thành hai tập C và D sao cho C = ∪i=1 k x (i) ,
Sup(Ci , D j ) =
- Ci ∩ D j
- ,
-
-
D = ∪i=k+1 x , x ∈ id, với 1 ≤ k < n, thì khối thông tin I B
n (i)
-
- Ci ∩ D j
-
-
gọi là khối quyết định và kí hiệu là DB = (U, C ∪ D,V, f ) Acc(Ci , D j ) = ,
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 |Ci |
-
-
- Ci ∩ D j
-
thuộc tính chỉ số quyết định. Ta có thể kí hiệu khối quyết Cov(Ci , D j ) =
-
- .
định một cách đơn giản là DB = (U, C ∪ D).
- D j
-
2
nguon tai.lieu . vn
