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

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

Thêm vào BST

Báo xấu

12
lượt xem 1
download

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

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

Chủ đề:

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

Lưu

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

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.