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

Chia sẻ: ViThimphu2711 ViThimphu2711 | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

64
lượt xem 2
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài viết đư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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 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