Một số tính chất của ma trận SUP trên khối dữ liệu khi bổ sung và loại bỏ lớp đối tượng thuần nhất

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

Thêm vào BST

Báo xấu

18
lượt xem 2
download

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

Bài viết phát biểu và chứng minh một số tính chất tính gia tăng ma trận độ hỗ trợ, từ đó xác định ma trận độ chính xác và ma trận độ phủ trên khối dữ liệu khi bổ sung và loại bỏ lớp đối tượng thuần nhất để sinh các luật quyết định có ý nghĩa.

Chủ đề:

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

Lưu

Nội dung Text: Một số tính chất của ma trận SUP trên khối dữ liệu khi bổ sung và loại bỏ lớp đối tượng thuần nhất

Kỷ yếu Hội nghị KHCN Quốc gia lần thứ XIII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR), Nha Trang, ngày 8-9/10/2020 DOI: 10.15625/vap.2020.00186 MỘT SỐ TÍNH CHẤT CỦA MA TRẬN SUP TRÊN KHỐI DỮ LIỆU KHI BỔ SUNG VÀ LOẠI BỎ LỚP ĐỐI TƯỢNG THUẦN NHẤT Trịnh Đình Thắng1, Đỗ Thị Lan Anh1, Trần Minh Tuyến2 Viện Công nghệ thông tin, Trường Đại học Sư phạm Hà Nội 2 1 2 Đại học Công đoàn thangdhsp2@hpu2.edu.vn, lananh.cntt.sp2@gmail.com, tuyentm@dhcd.edu.vn TÓM TẮT: Bài báo phát biểu và chứng minh một số tính chất tính gia tăng ma trận độ hỗ trợ, từ đó xác định ma trận độ chính xác và ma trận độ phủ trên khối dữ liệu khi bổ sung và loại bỏ lớp đối tượng thuần nhất để sinh các luật quyết định có ý nghĩa. Các thuật toán để tính gia tăng ma trận độ hỗ trợ trên khối quyết định 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 khi bổ sung và loại bỏ lớp đối tượng thuần nhất cũng đã được phát biểu và chứng minh ở đây. Từ khóa: 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 Khi nghiên cứu mô hình và thuật toán để khai phá các luật quyết định trên khối dữ liệu với tập đối tượng thay đổi thì việc tính gia tăng các ma trận Sup, Acc, Cov luôn được các tác giả quan tâm. 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 và chứng minh một số tính chất của các ma trận độ hỗ trợ, độ chính xác và độ phủ trên khối dữ liệu khi bổ sung và loại bỏ các lớp đối tượng. Từ các tính chất này, bài báo đề xuất các thuật toán tính gia tăng của các ma trận tương ứng cùng độ phức tạp tính toán. Các kết quả của việc tính gia tăng các ma trận Acc và Cov sẽ là cơ sở để tìm ra các luật quyết định có ý nghĩa trên khối dữ liệu khi bổ sung và loại bỏ các lớp đối tượng. 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 Ai (i=1..n) có miền giá trị tương ứng là dom(Ai). 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 , ở đây t∈ r(R), t = { ti : id → dom(Ai)}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. 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, n 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 =  id (i ) là tập các thuộc tính chỉ số của i =1 đối tượng, V = V x( i ) , 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), f là hàm thông tin UxA → x ( i ) ∈A V thỏa mãn: ∀u∈U, ∀ x(i)∈ A ta có f(u, x(i))∈ 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).
Trịnh Đình Thắng, Đỗ Thị Lan Anh, Trần Minh Tuyến 343 Đị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 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,𝐴𝑥 = ⋃𝑛𝑖=1 𝑥 (𝑖) 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 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) (i) f(u, x(i))∈ V ( i ), Vx =  V.x (i ) x x( i ) ∈ Ax 2.4. Khối quyết định n Định nghĩa 2.5 [4] Cho khối thông tin IB k= (U,A,V,f) với U là không gian các đối tượng, A =  id . Khi đó (i ) n i =1 nếu A được chia thành 2 tập C và D sao cho: C =  x , D =i =k  (i ) (i ) x , thì khối thông tin IB gọi là khối quyết định và kí +1, x∈id i =1, x∈id 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 2.6 [4] 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) là một bộ bốn DBx = (U, Cx∪Dx, k n  x, Dx= i =k +1 x , Ax= Cx∪Dx, (i ) 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= (i ) i =1 V x=  Vx ( 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 là hàm thông tin UxAx →Vx thỏa x ( i ) ∈Ax 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: n k n ,D=  Cx =  x , D = i =k +1 x , x∈id. x (i ) C= x (i ), (i ) i = k +1, x∈id i =1 Khi đó: U/C = {C1,C2,…,Cm}, U/C x = {C x1 , C x 2 ,..., C xt } , U/D = {D1,D2,…,Dh}, U/Dx = {D x1 , Dx 2 ,..., Dxsx } , 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[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 , Dx=  x (i ), x∈id, i =1 (i ) i = k +1 U/C={C1,C2,…,Cm}, U/Cx= {C x1 , C x 2 ,..., C xtx } , U/D={D1,D2,…,Dh}, U/Dx= {D x1 , Dx 2 ,..., Dxs } . x Khi đó: ∀Ci∈ U/C,∀Dj∈ U/D ta có: Ci = , Dj = D x∈id xqx với px∈{1,2,…,tx }, qx∈{1,2,…,sx }. Định nghĩa 2.8 [4] 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 | - Độ phủ: Cov(Cxp,Dxq) = | C xp ∩ 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 (C1 , D1 ) ... Sup (C1 , Dh )  Sup(C, D) = Sup(Ci,Dj)mxn =    ...   Sup (C , D ) ... Sup (C , D )   m 1 m h 
344 MỘT SỐ TÍNH CHẤT CỦA MA TRẬN SUP TRÊN KHỐI DỮ LIỆU KHI BỔ SUNG VÀ LOẠI BỎ LỚP ĐỐI TƯỢNG… - Ma trận độ chính xác:  Acc(C1 , D1 ) ... Acc(C1 , Dh )    Acc(C, D) = Acc(Ci,Dj)mxn =  ...   Acc(C , D ) ... Acc(C , D )   m 1 m h  - Ma trận độ phủ:  Cov(C1 , D1 ) ... Cov(C1 , Dh )  Cov(C, D) = Cov(Ci,Dj)mxn =    ...   Cov(C , D ) ... Cov(C , D )   m 1 m h  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 [4] 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(C , D ) q =1 i q ∑ Sup(C p =1 p , Dj ) III. KẾT QUẢ NGHIÊN CỨU 3.1. Tính toán gia tăng độ hỗ trợ khi bổ sung, loại bỏ lớp đối tượng thuần nhất trên khối quyết định k n Cho khối quyết định DB = (U, C∪D, V, f), trong đó: C =  x ( i ), D =  x ( i ) , U/C = {C1,C2,…,Cm}, i =1, x∈id i = k +1, x∈id U/D={D1,D2,…,Dh}. Định nghĩa 3.1 k n Cho khối quyết định DB= (U, C∪D, V, f), trong đó: C = i =1,x∈id x , D =  x , U/C = {C1,C2,…,Cm}, U/D = = (i ) (i ) i = k +1, x∈id {D1,D2,…,Dh}. Khi đó lớp đối tượng NX được gọi là thuần nhất đối với khối quyết định DB nếu như các đối tượng của NX nhận các giá trị như nhau trên tất cả các thuộc tính chỉ số, nghĩa là: f(u, x(i))= f(u’, x(i)) ∀ x(i)∈ C, ∀ u,u’∈ NX. • Bổ sung lớp đối tượng thuần nhất vào khối quyết định Giả sử, ta cần bổ sung vào khối quyết định này một lớp đối tượng mới gồm N đối tượng, kí hiệu NA. Sau khi bổ sung ta kí hiệu các lớp tương đương điều kiện và các lớp tương đương quyết định tương ứng là: U’/C={C’1,C’2,…,C’m…}, U’/D={D’1,D’2,…,D’h…}. Ở đây đối với i = 1..m thì các lớp tương đương điều kiện Ci và C’i có mô tả giống nhau (nghĩa là ∀ x(i)∈ C ta có: f(u, x )= f(u’, x(i)) với u∈Ci và u’∈C’i), chúng chỉ khác nhau về số phần tử. Hoàn toàn tương tự đối với các lớp tương (i) đương quyết định Dj và D’j với j = 1..h. Khi bổ sung lớp đối tượng NA vào khối quyết định thì xảy ra 4 khả năng sau: 1) Lớp NA được bổ sung này sẽ sinh thêm 1 lớp tương đương điều kiện mới đối với tập U’/C, kí hiệu C’m+1 gồm N phần tử và 1 lớp tương đương quyết định mới đối với tập U’/D, kí hiệu D’h+1 gồm N phần tử. Khi đó, ma trận Sup có thêm một dòng mới là m+1 và có thêm cột mới là h+1. Mệnh đề 3.1 k n Cho khối quyết định DB= (U, C∪D, V, f), trong đó: C =  x , D =  x (i ) (i ) , U/C = {C1,C2,…,Cm}, U/D = i =1, x∈id i = k +1, x∈id {D1,D2,…,Dh}. Khi đó nếu ta bổ sung vào khối này lớp đối tượng thuần nhất NA mà sinh thêm lớp tương đương điều kiện mới đối với tập U’/C, kí hiệu C’m+1 gồm N phần tử và lớp tương đương quyết định mới đối với tập U’/D, kí hiệu D’h+1 gồm N phần tử thì ta có: i) Sup(C’m+1, D’h+1) = | C’m+1 ∩ D’h+1| = N, ii) Sup(C’m+1, D’j) = 0 với j = 1..h, iii) Sup(C’i, D’h+1) = 0 với i = 1..m, iv) Sup(C’i, D’j) = Sup(Ci, Dj) với i = 1..m , j = 1..h.
Trịnh Đình Thắng, Đỗ Thị Lan Anh, Trần Minh Tuyến 345 Chứng minh i) Khi bổ sung lớp đối tượng thuần nhất NA vào khối quyết định mà sinh thêm 1 lớp tương đương điều kiện mới đối với tập U’/C, kí hiệu C’m+1 gồm N phần tử và 1 lớp tương đương quyết định mới đối với tập U’/D, kí hiệu D’h+1 gồm N phần tử thì khi đó 2 lớp tương đương C’m+1 và D’h+1 chứa cùng số phần tử bổ sung này. Do vậy, theo định nghĩa của độ đo Sup ta có: Sup(C’m+1, D’h+1) = | C’m+1 ∩ D’h+1| = N. ii) Vì C’m+1 chỉ chứa các phần tử mới bổ sung, còn D’j với j = 1..h chỉ chứa các phần tử cũ nên 2 lớp tương đương này không thể có phần tử chung. Từ đó suy ra: Sup(C’m+1, D’j) = 0 với j = 1..h. iii) Tương tự như ở ii), vì D’h+1 chỉ chứa các phần tử mới bổ sung, còn C’i với ij = 1..m chỉ chứa các phần tử cũ nên 2 lớp tương đương này không thể có phần tử chung. Từ đó suy ra: Sup(C’i, D’h+1) = 0 với i = 1..m. iv) Các lớp tương đương điều kiện và quyết định cũ với i = 1..m , j = 1..h thì không có gì thay đổi sau khi bổ sung nên giá trị Sup của chúng cũng không thay đổi. Vậy ta có: Sup(C’i, D’j) = Sup(Ci, Dj) với i = 1..m , j = 1..h. 2) Lớp NA được bổ sung này sẽ sinh thêm 1 lớp tương đương điều kiện mới đối với tập U’/C, kí hiệu C’m+1 gồm N phần tử và không sinh thêm lớp tương đương quyết định mới đối với tập U’/D ⇒ ∃ j*∈ {1,2,…,h} sao cho NA ⊆ D’j* . Khi đó, ma trận Sup có thêm một dòng mới là m+1 và không sinh thêm cột mới. Mệnh đề 3.2 n k Cho khối quyết định DB= (U, C∪D, V, f), trong đó: C =i =1,x∈id x , D = (i )  x , U/C = {C1,C2,…,Cm}, U/D = (i ) i = k +1, x∈id {D1,D2,…,Dh}. Khi đó nếu ta bổ sung vào khối này lớp đối tượng thuần nhất NA mà sinh thêm lớp tương đương điều kiện mới đối với tập U’/C, kí hiệu C’m+1 gồm N phần tử và không sinh thêm lớp tương đương quyết định mới đối với tập U’/D, ∃ j*∈ {1,2,…,h} sao cho NA ⊆ D’j* thì ta có: i) Sup(C’m+1, D’j*) = | C’m+1 ∩ D’j* | = N, ii) Sup(C’m+1, D’j) = 0 với j = 1..h và j ≠ j*. iii) Sup(C’i, D’j) = Sup(Ci, Dj) với i = 1..m , j = 1..h. Chứng minh i) Khi ta bổ sung vào khối quyết định lớp đối tượng thuần nhất NA mà sinh thêm lớp C’m+1 gồm N phần tử và ∃ j*∈ {1,2,…,h} sao cho NA ⊆ D’j* thì khi đó số phần tử chung của 2 lớp tương đương này sẽ là N. Do đó theo định nghĩa của Sup ta có: Sup(C’m+1, D’j*) = | C’m+1 ∩ D’j* | = N. ii) Vì lớp C’m+1 gồm N phần tử mới được bổ sung, còn các lớp D’j với j ≠ j*, j = 1..h lại chỉ gồm các phần tử cũ nên chúng không thể có phần tử chung được. Từ đó suy ra: Sup(C’m+1, D’j) = 0 với j = 1..h và j ≠ j*. iii) Do các lớp C’i với i = 1..m chỉ gồm các phần tử cũ, còn các phần tử của lớp D’j với j ≠ j* cũng chỉ gồm các phần tử cũ, riêng D’j* thì được bổ sung thêm N phần tử mới. Như vậy các phần tử chung của 2 lớp tương đương C’I và D’j với i = 1..m, j = 1..h không thay đổi so với ban đầu. Vì vậy ta có: Sup(C’i, D’j) = Sup(Ci, Dj) với i = 1..m , j = 1..h. 3) Lớp NA được bổ sung này không sinh thêm lớp tương đương điều kiện mới đối với tập U’/C ⇒ ∃ i*∈ {1,2,…,m} sao cho NA ⊆ C’i* . Tuy nhiên, nó lại sinh ra lớp tương đương quyết định mới, kí hiệu D’h+1. Khi đó, ma trận Sup có thêm 1 cột mới là h+1 và không sinh thêm dòng mới. Mệnh đề 3.3 k n Cho khối quyết định DB= (U, C∪D, V, f), trong đó: C =i =1,x∈id x , D =  x , U/C = {C1,C2,…,Cm}, U/D = (i ) (i ) i = k +1, x∈id {D1,D2,…,Dh}. Khi đó nếu ta bổ sung vào khối này lớp đối tượng thuần nhất NA mà không sinh thêm lớp tương đương điều kiện mới đối với tập U’/C, ∃ i*∈ {1,2,…,m} sao cho NA ⊆ C’i* và sinh thêm lớp tương đương quyết định mới đối với tập U’/D kí hiệu D’h+1 thì ta có: i) Sup(C’i*, D’h+1) = | C’i* ∩ D’h+1| = N, ii) Sup(C’i, D’h+1) = 0 với i = 1..m và i ≠ i*. iii) Sup(C’i, D’j) = Sup(Ci, Dj) với i = 1..m , j = 1..h.
346 MỘT SỐ TÍNH CHẤT CỦA MA TRẬN SUP TRÊN KHỐI DỮ LIỆU KHI BỔ SUNG VÀ LOẠI BỎ LỚP ĐỐI TƯỢNG… Chứng minh i) Vì theo giả thiết ta có lớp NA được bổ sung này không sinh thêm lớp tương đương điều kiện mới đối với tập U’/C ⇒ ∃ i*∈ {1,2,…,m} sao cho NA ⊆ C’i*. Trong khi đó lớp tương đương quyết định mới D’h+1 có N phần tử mới bổ sung, vì vậy lớp C’i* và lớp D’h+1 sẽ có N phần tử chung. Điều đó chứng tỏ rằng: Sup(C’i*, D’h+1) = | C’i* ∩ D’h+1| = N. ii) Ta thấy các lớp tương đương điều kiện C’i với i = 1..m và i ≠ i* chỉ chứa các phần tử cũ, còn lớp tương đương quyết định D’h+1 lại chỉ chứa các phần tử mới nên C’i và D’h+1 không thể có phần tử chung. Do vậy ta có: Sup(C’i, D’h+1) = 0 với i = 1..m và i ≠ i*. iii) Vì các lớp tương đương quyết định D’j , j = 1..h chỉ chứa các phần tử cũ, còn các lớp tương đương điều kiện C’i với i = 1..m và i ≠ i* chỉ chứa các phần tử cũ, riêng lớp C’i* thì được bổ sung các phần tử mới nên C’i và D’j với i = 1..m , j = 1..h có các phần tử chung không thay đổi so với trước. Từ đó suy ra: Sup(C’i, D’j) = Sup(Ci, Dj) với i = 1..m, j = 1..h. 4) Lớp NA được bổ sung này không sinh thêm lớp tương đương điều kiện mới đối với tập U’/C ⇒ ∃ i*∈ {1,2,…,m} sao cho NA ⊆ C’i* và không sinh thêm lớp tương đương quyết định mới đối với tập U’/D ⇒ ∃ j*∈ {1,2,…,h} sao cho NA ⊆ D’j* . Khi đó, ma trận Sup không sinh thêm dòng mới và không sinh thêm cột mới: Mệnh đề 3.4 k n Cho khối quyết định DB= (U, C∪D, V, f), trong đó: C =  i =1, x∈id x (i ) , D = x (i ) , U/C = {C1,C2,…,Cm}, U/D = i = k +1, x∈id {D1,D2,…,Dh}. Khi đó nếu ta bổ sung vào khối này lớp đối tượng thuần nhất NA mà không sinh thêm lớp tương đương điều kiện mới đối với tập U’/C, ∃ i*∈ {1,2,…,m} sao cho NA ⊆ C’i* và không sinh thêm lớp tương đương quyết định mới đối với tập U’/D, ∃ j*∈ {1,2,…,h} sao cho NA ⊆ D’j* thì ta có: i) Sup(C’i*, D’j*) = | C’i* ∩ D’j*| = | Ci* ∩ Dj*| + N, ii) Sup(C’i, D’j) = | C’i ∩ D’j| = Sup(Ci, Dj) với i ≠ i* và j ≠ j*. Chứng minh i) Theo giả thiết thì khi bổ sung lớp đối tượng thuần nhất NA không sinh thêm lớp tương đương điều kiện mới, do đó ∃ i*∈ {1,2,…,m} sao cho NA ⊆ C’i* và cũng không sinh thêm lớp tương đương quyết định mới, nghĩa là ∃ j*∈ {1,2,…,h} sao cho NA ⊆ D’j* . Do vậy hai lớp tương đương C’i* và D’j* có số phần tử chung tăng thêm N. Từ đó ta có: Sup(C’i*, D’j*) = | C’i* ∩ D’j*| = | Ci* ∩ Dj*| + N. ii) Với i ≠ i* và j ≠ j* thì các lớp tương đương điều kiện và các lớp tương đương quyết định đều chỉ gồm các phần tử cũ mà không được bổ sung các phần tử mới nên số phần tử chung của chúng không thay đổi so với trước khi được bổ sung. Vì vậy ta có: Sup(C’i, D’j) = | C’i ∩ D’j| = Sup(Ci, Dj) với i ≠ i* và j ≠ j*. • Loại bỏ lớp đối tượng thuần nhất ra khỏi khối quyết định Khi loại bỏ lớp đối tượng thuần nhất MD ra khỏi khối quyết định thì: 5) Lớp MD bị loại bỏ này sẽ thuộc vào 1 lớp tương đương điều kiện nào đó của tập U/C, ∃ i*∈ {1,2,…,m} sao cho MD ⊆ Ci* và cũng thuộc vào 1 lớp tương đương quyết định nào đó của tập U/D, ∃ j*∈ {1,2,…,h} sao cho MD ⊆ Dj* . Khi đó, ma trận Sup không sinh thêm dòng mới và không sinh thêm cột mới. Mệnh đề 3.5 k n Cho khối quyết định DB= (U, C∪D, V, f), trong đó: C = x , D = x (i ) (i ) , U/C = {C1,C2,…,Cm}, U/D = i =1, x∈id i = k +1, x∈id {D1,D2,…,Dh}. Khi đó, nếu ta loại bỏ từ khối này lớp đối tượng thuần nhất MD mà không sinh thêm lớp tương đương điều kiện mới đối với tập U’/C, ∃ i*∈ {1,2,…,m} sao cho MD ⊆ Ci* và không sinh thêm lớp tương đương quyết định mới đối với tập U’/D, ∃ j*∈ {1,2,…,h} sao cho ND ⊆ Dj* thì ta có: i) Sup(C’i*, D’j*) = | C’i* ∩ D’j*| = | Ci* ∩ Dj*| - M, ii) Sup(C’i, D’j) = | C’i ∩ D’j| = Sup(Ci, Dj) với i ≠ i* và j ≠ j*. Chứng minh
Trịnh Đình Thắng, Đỗ Thị Lan Anh, Trần Minh Tuyến 347 i) Theo giả thiết ta có: khi loại bỏ khỏi khối quyết định lớp đối tượng thuần nhất MD thì ∃ i*∈ {1,2,…,m} sao cho MD ⊆ Ci* và ∃ j*∈ {1,2,…,h} sao cho MD ⊆ Dj*. Như vậy, cả 2 lớp tương đương C’i* và D’j* đều bị bớt đi M phần tử chung thuộc lớp đối tượng thuần nhất MD. Do vậy ta có: Sup(C’i*, D’j*) = | C’i* ∩ D’j*| = | Ci* ∩ Dj*| - M. ii) Vì các lớp tương đương điều kiện và quyết định C’i , D’j với i ≠ i* và j ≠ j* đều không bị loại bỏ phần tử nào nên các phần tử chung của chúng không bị thay đổi sau loại bỏ. Từ đó suy ra: Sup(C’i, D’j) = | C’i ∩ D’j| = Sup(Ci, Dj) với i ≠ i* và j ≠ j*. 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ỏ lớp đối tượng thuần nhất 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 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: Bắt đầu Tính gia tăng ma trận Sup(C’, D’) sau khi bổ Tính ma trận Sup(C, D) sung/loại bỏ lớp đối tượng thuần nhất Tính các ma trận Acc(C’, D’) và Loại bỏ dòng/cột toàn giá trị 0 ra khỏi ma trận Cov(C’, D’) Sup(C’, D’) nếu có Sinh các luật quyết định Kết thúc có ý nghĩa Thuật toán 3.1: Tính gia tăng ma trận Sup(C’, D’), khi bổ sung lớp đối tượng thuần nhất Vào: - Các lớp Ci, Dj. - Lớp NA gồm N đối tượng thuần nhất được bổ sung. - Ma trận Sup(C, D). Ra: Ma trận Sup(C’, D’). Begin // Tìm lớp điều kiện và lớp quyết định chứa end for; x thuộc lớp NA for j = 1 to h do //tìm trong các lớp with x in AN 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 // Nếu j* = -1 thì x không thuộc Dj nào, i* = i; // tìm thấy x thuộc lớp Ci tạo thêm lớp mới Dh+1 break; if j* = -1 then end if; j* = h + 1; // Nếu i* = -1 thì x không thuộc Ci nào, tạo Bổ sung Dh+1 vào U/D; thêm lớp mới Cm+1. Tạo cột (h + 1) mới = 0 cho ma trận Sup; if i* = -1 then h = h + 1; i* = m + 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+1 vào U/C; Sup(Ci*, Dj*) = Sup(Ci*, Dj*) + N Tạo dòng (m + 1) mới = 0 cho ma trận Sup; end if; m = m + 1; end for; end if; End.
348 MỘT SỐ TÍNH CHẤT CỦA MA TRẬN SUP TRÊN KHỐI DỮ LIỆU KHI BỔ SUNG VÀ LOẠI BỎ LỚP ĐỐI TƯỢNG… 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 lớp NA 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à N, 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. (ii) Nếu x ∉ Ci và ∃ j* ∈{1,…,h}: x ∈Dj* nghĩa là việc bổ sung lớp NA 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 N, 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 lớp NA 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 N, 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 lớp NA 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, lớp NA 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 N, các phần tử còn lại không thay đổi. Sau khi hoàn thành 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ỏ lớp đối tượng thuần nhất. Vào: - Các lớp Ci, Dj. - Lớp MD gồm M đối tượng thuần nhất bị loại bỏ. - Ma trận Sup(C, D). Ra: Ma trận Sup(C’, D’). Begin // Tìm lớp điều kiện và lớp quyết end for; định chứa x’. for j=1 to h do //tìm trong các lớp with x’ in MD 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*) - M; end if; End. 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.6: Độ 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 lớp đối tượng thuần nhất là O(|U|). Mệnh đề 3.7: Độ 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ỏ lớp đối tượng thuần nhất là O(|U|). IV. KẾT LUẬN Việc bổ sung và loại bỏ lớp các đối tượng thuần nhất trên khối quyết định là hay xảy ra, bài báo đã phát biểu và chứng minh một số tính chất và đề 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. 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 trong trường hợp riêng 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 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”, pp. 276-286, 08/2010.
Trịnh Đình Thắng, Đỗ Thị Lan Anh, Trần Minh Tuyến 349 [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, India, Vol. 3, No.3, pp. 335-339, 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”, pp. 163-169, 2016. [5] Liu, D., Li, T., Ruan, D., Zou, W., “An incremental approach for inducing knowledge from dynamic information systems”, Fundam. Inform., (94), pp. 245-260, 2009. [6] Shi, K., Yao, B., “Function S-rough sets and decision law identification”. Science in China Series F: Information Sciences 51, pp. 499-510, 2008. SOME PROPERTIES OF THE SUPPORT MATRIX ON THE DATA BLOCK WHEN ADDING AND REMOVING HOMOGENEOUS OBJECT CLASSES Trinh Dinh Thang, Do Thi Lan Anh, Tran Minh Tuyen ABSTRACT: The paper states and demonstrates some properties of the support matrix incremental calculation, thereby defining the accuracy matrix and the coverage matrix on the data block when adding and removing homogeneous object layers, to generate meaningful decision laws. The algorithms to calculate the increase of the support matrix on the decision block have also been proposed when increasing or decreasing the object set,... The complexity of these algorithms on the block determines when adding and removing a homogeneous object class has also been presented and proved correct here.