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

ề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: 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 x thuộc lớp NA with x in AN do i* = -1; //lớp điều kiện của x sẽ tìm j* = -1; //lớp quyết định của x sẽ tìm for i = 1 to m do //tìm trong các lớp điều kiện if (x in Ci) then i* = i; // tìm thấy x thuộc lớp Ci break; end if; // Nếu i* = -1 thì x không thuộc Ci nào, tạo thêm lớp mới Cm+1. if i* = -1 then i* = m + 1; //Cập nhật tập lớp điều kiện Bổsung Cm+1 vào U/C; Tạo dòng (m + 1) mới = 0 cho ma trận Sup; m = m + 1; end if; end for; for j = 1 to h do //tìm trong các lớp quyết định if (x in Dj) then j* = j; //Tìm thấy x thuộc lớp Dj break; end if; // Nếu j* = -1 thì x không thuộc Dj nào, tạo thêm lớp mới Dh+1 if j* = -1 then j* = h + 1; Bổ sung Dh+1 vào U/D; Tạo cột (h + 1) mới = 0 cho ma trận Sup; h = h + 1; end if; //Cập nhật phần tử ma trận Sup tương ứng Sup(Ci*, Dj*) = Sup(Ci*, Dj*) + N end if; end for; End. Sinh các luật quyết định có ý nghĩa Kết thúc 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ỏ lớp đối tượng thuần nhất 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’) 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 định chứa x’. with x’ in MD do i* = -1; //lớp điều kiện của x’ sẽ tìm j* = -1; //lớp quyết định của x’ sẽ tìm for i = 1 to m do //tìm trong các lớp điều kiện if (x’ in Ci) then i* = i; // tìm thấy x’ thuộc lớp Ci break; end if; end for; for j=1 to h do //tìm trong các lớp quyết định if (x’ in Dj) then j* = j; //tìm thấy x’ thuộc lớp Dj break; end if; end for; //Cập nhật phần tử của ma trận Sup tương ứng Sup(Ci*, Dj*)=Sup(Ci*, Dj*) - M; 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.