# Indistinguishable Element-Pair Attribute Reduction and Its Incremental Approach

Authors: Baohua Liang; Haiqi Zhang; Zhengyu Lu; Zhengjin Zhang
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

Attribute reduction is a popular approach of preprocessing data. Discernibility matrix is a typical method that focuses on attribute reduction. Faced with the processing of modern information systems with large amounts of data and rapid changes, the traditional static discernibility matrix reduction model is powerless. To overcome this shortcoming, this paper first proposes an indistinguishable element pair method that does not need to store discernibility information, which retains the advantages of institution and easy-to-understand, and at the same time effectively solves the problem of space consumption. In order to make the model adapt to the processing of dynamic data sets, we further study the incremental mechanism and design a set of dynamic reduction models, which can adjust the reduction set in time according to the changes of objects. Theoretical analysis and experimental results indicate that the proposed algorithm is obviously superior to the discernibility matrix model, and can effectively deal with the reduction of dynamic data sets.


---

## Body

## 1. Introduction

Rough sets theory (RST) is a valid mathematical tool, which was proposed by Pawlak and Skowron in 1982, for dealing with inaccurate, incomplete, and vague information [1]. RST has been widely used in many fields such as machine learning [2], data mining [3], decision supporting [4], expert system [5], pattern recognition [6], and music emotions annotation [7]. Attribute reduction is one of the hot research focuses in RST [8], which aims to delete redundant data, while keeping the distinguishing power of the original data in information systems. For the convenience of the following description, Table 1 summarizes the list of abbreviations in the article. In the last two decades, many heuristic attribute reduction approaches have been developed based on the positive region [9], discernibility matrix [10, 11], information entropy [12], fuzzy rough [13, 14], m-polar fuzzy [15, 16], and knowledge granularity [17].Table 1
The list of abbreviations.
AbbreviationOriginalRSTRough sets theoryDMADiscernibility matrix approachIEPIndistinguishable element-pairIEPAOIndistinguishable element-pair adding objectsIEPDOIndistinguishable element-pair deleting objectsCPNRCompute the positive and negative regionAmong the abovementioned approaches, DMA is a typical reduction model. Since DMA consumes a lot of space to store distinguishable information, it cannot reduce large data sets. In order to effectively express the distinguishable information among samples, Hu and Cercone [18] proposed a concise definition of a discernibility matrix. Ye and Chen [19] proposed a discernibility matrix-elements that retains all bases of 1. Yang and Sun [20] use the sample comparison of the upper and lower approximation to obtain the discernibility matrix. Dong et al. [21] proposed a fast algorithm of attribute reduction for covering the decision system with minimal elements in discernibility matrix. Wei et al. [22] proposed two discernibility matrices in the sense of entropies. However, these approaches only consider how to improve the distinguishing ability of samples, and do not consider the space consumption. In order to reduce the space computation, Jiang [10] proposed a minimal element selection tree. Li et al. [23] proposed a simple object-attribute discernibility matrix approach. Although scholars have improved the discernibility matrix, the space consumption problem has not been fundamentally solved. To overcome this deficiency, this paper proposes a method based on IEP without discernibility matrix. Firstly, we divide the data set according to conditional attributes and decision attributes and calculate the number of indistinguishable element pairs. Then, select the conditional attribute with the smallest values of IEP. Finally, repeat the abovementioned two steps until the value is 0.With the rapid development of communication and network techniques, the actual data may change over time. However, the IEP method is only suitable for static data sets. Hence, it is desired to design an incremental attribute reduction algorithm with IEP to deal with dynamic decision systems.Incremental learning is an efficient approach making full use of the precious results of the original decision system, which can obtain the efficient reduced results by recomputing the updated part of the dynamic data set. Many incremental algorithms have been proposed with different models for dynamic data. Yang proposed an incremental algorithm for updating an object or attribute [24]. Ge et al. developed an incremental attribute reduction based on a simplified discernibility matrix, which is equivalent to attribute reduction based on a positive region [25]. Liu et al. proposed a strong discernibility matrix method for incremental attribute reduction on fuzzy decision tables [26]. In literature [27], Wei proposed three new types of discernibility matrices by compacting a decision table. Zhang et al. proposed a method based on a relation matrix under the change attribute reduction in set-valued information systems [28]. Ma et al. [29] proposed a compressed binary discernibility matrix to process the group dynamic data. Obviously, the abovementioned matrix methods mainly focus on updating the elements of discernibility matrix. These approaches are ineffective in obtaining the reduction results with large-scale decision systems due to the limited memory space. Hence, we incorporate the incremental update mechanism into the IEP approach. Verifies the feasibility and efficiency of proposed algorithm through extensive experiments on UCI data sets.


## 2. Preliminaries

In this section, we review some basic concepts about rough set, discernibility matrix, and indistinguishable element-pair.


### 2.1. Basic Concepts

Definition 1.
(see [1]). Given the decision system is a quadruple tuple S=U,A,V,f, where U is a finite nonempty object set and A is a finite nonempty attribute set, V=∪a∈AVa,Va is a set of its values, and f:U×A⟶V is an information function with fx,a=Va for each a∈A and x∈U. If A=C∪D, where C is the conditional attribute set, and D is the decision attribute set. For every subset P⊆A , an indiscernibility relation INDP is defined as follows: (1)INDP=x,y∈U×U|∀a∈P,fx,a=fy,a.
Obviously, ifINDP denotes as U/P, U/P is an equivalence relation. We assume includes x, the equivalence relation x is defined as: (2)xP=y|∀a∈P,fx,a=fy,a.Definition 2.
(see [1]). Given the decision system S=U,A,V,f for every subset Y⊆U and indiscernibility relation INDP, the upper approximation set and the lower approximation set of Y can be defined by the basic set of P as follows:(3)P¯Y=x∈U|xP⊆Y,P¯Y=x∈U|xP∩Y≠∅.
The universeU is partitioned into three disjoint regions by these two approximations P¯Y and P¯Y: the positive region POSPY, the negative region P¯Y, and the boundary region BNDPY. Then the three different regions are defined as following, respectively:(4)NEGPY=U−P¯YBNDPY=P¯Y−P¯YPOSPY=P¯Y.Definition 3.
(see [18]). Let DT=U,C∪D be a decision table, C be the condition attribute set, and D be the decision attribute. The discernibility matrix in all samples is defined as MDTD=mD/ij, where:(5)mijD=c∈C:fxi,c≠fxj,c,fxi,d≠fxj,d,∅,otherwise.Definition 4.
(see [31]). Let DT=U,C∪D be a decision table, C be the condition attribute set, and D be the decision attribute. In terms of a positive region, the discernibility matrix is defined as MDTP=mijP,where:(6)mijP=c∈C:fxi,c≠fxj,c,fxi,d≠fxj,dandxi,xj∈U1,c∈C:fxi,c≠fxj,c,xi∈U1,xj∈U2,∅,otherwise.U1 is the consistent part of the decision table and U2 is the inconsistent part DT.Definition 5.
(see [22]). Let DT=U,C∪D be a decision table, C be the condition attribute set, and D be the decision attribute. The discernibility matrix in the sense of complement entropy is defined as ME/DT=mE/ij.,where:(7)mijE=c∈C:fxi,c≠fxj,c,fxi,d≠fxj,dandxi,xj∈U1c∈C:fxi,c≠fxj,c,xi∈U1,xj∈U2c∈C:fxi,c≠fxj,c,xi,xj∈U2∅,otherwise.U1 and U2 are the same as Definition 4.Theorem 1.
In the discernibility matrix information in Definition5, the total number of pairwise comparisons between elements is only related to the division of decision attributes of the data objects.Proof.
SupposeU is a nonempty finite set of data objects. U1 is the consistent part of U which belongs to the set of positive regions. U2 is the inconsistent part of U, which is included in the negative region set. The samples in U1 and U2 are not duplicated. Let U/D=D1,D2,…,Dn,Dneg,DPOS=D1∪D2∪…∪Dn, then U1=Dpos, and U2=Dneg. Suppose · is the cardinality of the data set, we can have U=Dpos+Dneg. According to Definition 5, it can be seen that there are three cases for comparison between samples.
Firstly, the positive region samples with different values of decision attribute should be compared in pairs wherexi,xj∈U1 and fxi,d≠fxj,d. Due to the symmetry of fxi,d≠fxj,d and fxj,d≠fxi,d, the sample xi and xj are compared twice, the actual number of comparisons should be halved. Let count1 be the number of comparisons between samples of the positive region set, then we can achieve the following conclusion:(8)count1=D1⋅Dpos−D1+D2⋅Dpos−D2+…+Dn⋅Dpos−Dn2=Dpos2−∑i=1nDi2/2.
Secondly, let count2 be the number of comparisons between samples of the positive region and negative region, then we havecount2=Dpos⋅Dneg where xi∈U1,xj∈U2.
Thirdly, all samples among the negative region are compared with other samples, and repeated comparisons should be subtracted, we havecount3=Dneg⋅Dneg−1/2.
Overall, the total number (TotalCount) of comparisons in discernibility matrix based on Definition 5 is as follows:(9)Totalcount=Count1+Count2+Count3=Dpos2−∑i=1nDi22+Dpos⋅Dneg+Dneg⋅Dneg−12=U2−U−∑i=1nDi2−Di2=CU2−∑i=1nCDi2=U2−U−∑i=1nDi2−Di2=CU2−∑i=1nCDi2.
Obviously, when a data set is given, the total number of comparisons is only related to the division of decision attributes, and irrelevant to conditional attributes.


### 2.2. The Presentation of the Indistinguishable Element-Pair

The discernibility matrix algorithm records the differences between samples by different values of conditional attributes between them, and the amount of distinguishable information measures the importance of the attributes. The larger the value, the more important the attribute. For the discernibility matrix proposed in literature [24] and literature [22], the number of comparisons between samples in the discernibility matrix is determined when the data set is given. Among the samples to be compared, the value of certain condition attributes is either the same or different. The same values of one conditional attribute mean being indistinguishable, while different means being distinguishable. If the amount of distinguishable information is larger, the amount of indistinguishable information is smaller when the total number of comparisons does not change. Here, we use the amount of indistinguishable information to measure the importance of conditional attributes.Definition 6.
SupposeU is a universe that is nonempty finite data set, A is a conditional attribute set. U/A=X1,X2,⋯Xn is the division of data set U on conditional attribute A and U/D=Y1,Y2,⋯,Ym,Yneg is the division on decision attribute D. Yneg is the division of inconsistent samples in decision attributes The indistinguishable element-pair of A relative to D is defined as follows:(10)IEPUD|A=∑i=1nCXi2−∑k=1mCXi∩Yk2,where CXi2=Xi⋅Xi−1/2.
In fact, all data objects among the subdivisionXi are indistinguishable from each other. There are CXi2 pairs. However, among these element pairs, some comparisons should be subtracted due to some data objects with the same decision attribute value. We have the definition of indistinguishable element-pair.
The asterisked (∗) data objects belong to the negative region setExample 1.
SupposeU is a simplified decision table without repeated samples in Table 2. A is a conditional attribute and D is a decision attribute. Let A=a∪b , the data objects x9,x10 belong to the negative region, Let U/D=x1,x2,x3,x4,x5,x6,x7,x8,x9,x10. and U/A=1,2,5,6,3,4,9,7,8,10.In subdivisions U/A, the underlined data objects have the same decision attribute value. Data set U has three subdivisions U1=1,2,5,6,U2=3,4,9 and U3=7,8,10 on conditional attribute A. According to Definition 6, we have indistinguishable information of the three subdivisions as follows:(11)IEPU1D|A=C42−C22−C22,IEPU2D|A=C32,IEPU3D|A=C32−C22,IEPUD|A=IEPU1D|A+IEPU2D|A+IEPU3D|A=9.Table 2
Simplified decision table.
NoabcD11001212013120141212510226103270013800239123∗10003∗Theorem 2.
The smaller the indistinguishable element pair, the stronger the distinguishing ability.Proof.
According to Theorem1, if the data set is given, the number of data objects in the positive and negative regions is also definite. Obviously, according to Definition 5, the number of comparisons between all data objects in the data set is also an invariable number. Suppose TotalCount is the total number of comparisons and the indistinguishable element-pair based on conditional attribute A is IEPUD|A, then the discernibility element-pair’s TotalCount-IEPUD|A. So, the smaller the IEPUD|A, the bigger the TotalCount-−IEPUD|A, the stronger the discernibility.Theorem 3.
Given the decision systemS=U,C∪D and B⊆P⊆C. Then U/D|P is detailed of U/D|B, and we have IEPUD|P≤IEPUD|BProof.
LetU/B=x1,x2,⋯,xj∪xj+1,xj+2,⋯,xn and U/P=x1,x2,⋯,xj,xj+1,⋯,xn. Suppose xj∪xj+1 is a subdivision of U/B. The detail subdivision based on P is xj and xj+1 and xj∩xj+1=∅, the other subdivision is unchanged. Let U/D=Y1,Y2,⋯,Ym. For convenience below, let Δ=∑i=1∧i≠j∧i≠j+1nCXi2−∑k=1mCXi∪Yk2,Xj=x,Xj+1=y,∑k=1mXj∩Yk=ax,∑k=1mXj+1∩Yk=by and 0≤a,b≤1, we have the result as follows:(12)IEPUD|B=Δ+CXj∪Xj+12−∑k=1mCXj∪Xj+1∩Yk2=Δ+x+yx+y−12−ax+byax+by−12IEPUD|P=Δ+Cxj2+Cxj+12−∑k=1mCxj∩Yk2−∑k=1mCxj+1∩Yk2=Δ+xx−12+yy−12−axax−12−byby−12IEPUD|B−IEPUD|P=xy−axby.
Since0≤a,b≤1, IEPUD|B−IEPUD|P=Cxi∪xj2(13)−Cxi2−Cxj2≥0,WeaveIEPUD|P≤IEPUD|BTheorem 4.
LetS=U,C∪D be a decision table and U is a data set without duplicate samples, then IEPUD|C=0.Proof.
AssumeU/C=U1,U2,…,Un, Since U′ is a data set without duplicate samples, U1=U2=…=Un=1, So IEPUD|C=∑i=1n0.Definition 7.
LetS=U,C∪D be a decision table and B⊆C. U is a data set without duplicate samples. Then B is a relative reduction based on the following indistinguishable element-pair of S if B satisfies:(1);
IEPUD|B=IEPUD|C(2);
∀a∈B,IEPUD|B−a≠IEPUD|BDefinition 8.
(see [30]). Let S=U,A be an information system. For any a∈A the value of object x about attribute a is fa,x. Let Disa=xi,xj|fa,xi≠fa,xj and DisA=∪a∈ADisa, we called Dis(a) and Dis(A) the discernibility relations in terms of a and A, respectively.Definition 9.
(see [30]). Suppose U=x1,x2,⋯,xn, let MS=cijn×n denote a n×n matrix, where cij=a∈A:fa,xi≠fa,xj for xi,xj∈DisA, otherwise cij=∅, MS is called the discernibility matrix of the information system S=U,A.


## 2.1. Basic Concepts

Definition 1.
(see [1]). Given the decision system is a quadruple tuple S=U,A,V,f, where U is a finite nonempty object set and A is a finite nonempty attribute set, V=∪a∈AVa,Va is a set of its values, and f:U×A⟶V is an information function with fx,a=Va for each a∈A and x∈U. If A=C∪D, where C is the conditional attribute set, and D is the decision attribute set. For every subset P⊆A , an indiscernibility relation INDP is defined as follows: (1)INDP=x,y∈U×U|∀a∈P,fx,a=fy,a.
Obviously, ifINDP denotes as U/P, U/P is an equivalence relation. We assume includes x, the equivalence relation x is defined as: (2)xP=y|∀a∈P,fx,a=fy,a.Definition 2.
(see [1]). Given the decision system S=U,A,V,f for every subset Y⊆U and indiscernibility relation INDP, the upper approximation set and the lower approximation set of Y can be defined by the basic set of P as follows:(3)P¯Y=x∈U|xP⊆Y,P¯Y=x∈U|xP∩Y≠∅.
The universeU is partitioned into three disjoint regions by these two approximations P¯Y and P¯Y: the positive region POSPY, the negative region P¯Y, and the boundary region BNDPY. Then the three different regions are defined as following, respectively:(4)NEGPY=U−P¯YBNDPY=P¯Y−P¯YPOSPY=P¯Y.Definition 3.
(see [18]). Let DT=U,C∪D be a decision table, C be the condition attribute set, and D be the decision attribute. The discernibility matrix in all samples is defined as MDTD=mD/ij, where:(5)mijD=c∈C:fxi,c≠fxj,c,fxi,d≠fxj,d,∅,otherwise.Definition 4.
(see [31]). Let DT=U,C∪D be a decision table, C be the condition attribute set, and D be the decision attribute. In terms of a positive region, the discernibility matrix is defined as MDTP=mijP,where:(6)mijP=c∈C:fxi,c≠fxj,c,fxi,d≠fxj,dandxi,xj∈U1,c∈C:fxi,c≠fxj,c,xi∈U1,xj∈U2,∅,otherwise.U1 is the consistent part of the decision table and U2 is the inconsistent part DT.Definition 5.
(see [22]). Let DT=U,C∪D be a decision table, C be the condition attribute set, and D be the decision attribute. The discernibility matrix in the sense of complement entropy is defined as ME/DT=mE/ij.,where:(7)mijE=c∈C:fxi,c≠fxj,c,fxi,d≠fxj,dandxi,xj∈U1c∈C:fxi,c≠fxj,c,xi∈U1,xj∈U2c∈C:fxi,c≠fxj,c,xi,xj∈U2∅,otherwise.U1 and U2 are the same as Definition 4.Theorem 1.
In the discernibility matrix information in Definition5, the total number of pairwise comparisons between elements is only related to the division of decision attributes of the data objects.Proof.
SupposeU is a nonempty finite set of data objects. U1 is the consistent part of U which belongs to the set of positive regions. U2 is the inconsistent part of U, which is included in the negative region set. The samples in U1 and U2 are not duplicated. Let U/D=D1,D2,…,Dn,Dneg,DPOS=D1∪D2∪…∪Dn, then U1=Dpos, and U2=Dneg. Suppose · is the cardinality of the data set, we can have U=Dpos+Dneg. According to Definition 5, it can be seen that there are three cases for comparison between samples.
Firstly, the positive region samples with different values of decision attribute should be compared in pairs wherexi,xj∈U1 and fxi,d≠fxj,d. Due to the symmetry of fxi,d≠fxj,d and fxj,d≠fxi,d, the sample xi and xj are compared twice, the actual number of comparisons should be halved. Let count1 be the number of comparisons between samples of the positive region set, then we can achieve the following conclusion:(8)count1=D1⋅Dpos−D1+D2⋅Dpos−D2+…+Dn⋅Dpos−Dn2=Dpos2−∑i=1nDi2/2.
Secondly, let count2 be the number of comparisons between samples of the positive region and negative region, then we havecount2=Dpos⋅Dneg where xi∈U1,xj∈U2.
Thirdly, all samples among the negative region are compared with other samples, and repeated comparisons should be subtracted, we havecount3=Dneg⋅Dneg−1/2.
Overall, the total number (TotalCount) of comparisons in discernibility matrix based on Definition 5 is as follows:(9)Totalcount=Count1+Count2+Count3=Dpos2−∑i=1nDi22+Dpos⋅Dneg+Dneg⋅Dneg−12=U2−U−∑i=1nDi2−Di2=CU2−∑i=1nCDi2=U2−U−∑i=1nDi2−Di2=CU2−∑i=1nCDi2.
Obviously, when a data set is given, the total number of comparisons is only related to the division of decision attributes, and irrelevant to conditional attributes.


## 2.2. The Presentation of the Indistinguishable Element-Pair

The discernibility matrix algorithm records the differences between samples by different values of conditional attributes between them, and the amount of distinguishable information measures the importance of the attributes. The larger the value, the more important the attribute. For the discernibility matrix proposed in literature [24] and literature [22], the number of comparisons between samples in the discernibility matrix is determined when the data set is given. Among the samples to be compared, the value of certain condition attributes is either the same or different. The same values of one conditional attribute mean being indistinguishable, while different means being distinguishable. If the amount of distinguishable information is larger, the amount of indistinguishable information is smaller when the total number of comparisons does not change. Here, we use the amount of indistinguishable information to measure the importance of conditional attributes.Definition 6.
SupposeU is a universe that is nonempty finite data set, A is a conditional attribute set. U/A=X1,X2,⋯Xn is the division of data set U on conditional attribute A and U/D=Y1,Y2,⋯,Ym,Yneg is the division on decision attribute D. Yneg is the division of inconsistent samples in decision attributes The indistinguishable element-pair of A relative to D is defined as follows:(10)IEPUD|A=∑i=1nCXi2−∑k=1mCXi∩Yk2,where CXi2=Xi⋅Xi−1/2.
In fact, all data objects among the subdivisionXi are indistinguishable from each other. There are CXi2 pairs. However, among these element pairs, some comparisons should be subtracted due to some data objects with the same decision attribute value. We have the definition of indistinguishable element-pair.
The asterisked (∗) data objects belong to the negative region setExample 1.
SupposeU is a simplified decision table without repeated samples in Table 2. A is a conditional attribute and D is a decision attribute. Let A=a∪b , the data objects x9,x10 belong to the negative region, Let U/D=x1,x2,x3,x4,x5,x6,x7,x8,x9,x10. and U/A=1,2,5,6,3,4,9,7,8,10.In subdivisions U/A, the underlined data objects have the same decision attribute value. Data set U has three subdivisions U1=1,2,5,6,U2=3,4,9 and U3=7,8,10 on conditional attribute A. According to Definition 6, we have indistinguishable information of the three subdivisions as follows:(11)IEPU1D|A=C42−C22−C22,IEPU2D|A=C32,IEPU3D|A=C32−C22,IEPUD|A=IEPU1D|A+IEPU2D|A+IEPU3D|A=9.Table 2
Simplified decision table.
NoabcD11001212013120141212510226103270013800239123∗10003∗Theorem 2.
The smaller the indistinguishable element pair, the stronger the distinguishing ability.Proof.
According to Theorem1, if the data set is given, the number of data objects in the positive and negative regions is also definite. Obviously, according to Definition 5, the number of comparisons between all data objects in the data set is also an invariable number. Suppose TotalCount is the total number of comparisons and the indistinguishable element-pair based on conditional attribute A is IEPUD|A, then the discernibility element-pair’s TotalCount-IEPUD|A. So, the smaller the IEPUD|A, the bigger the TotalCount-−IEPUD|A, the stronger the discernibility.Theorem 3.
Given the decision systemS=U,C∪D and B⊆P⊆C. Then U/D|P is detailed of U/D|B, and we have IEPUD|P≤IEPUD|BProof.
LetU/B=x1,x2,⋯,xj∪xj+1,xj+2,⋯,xn and U/P=x1,x2,⋯,xj,xj+1,⋯,xn. Suppose xj∪xj+1 is a subdivision of U/B. The detail subdivision based on P is xj and xj+1 and xj∩xj+1=∅, the other subdivision is unchanged. Let U/D=Y1,Y2,⋯,Ym. For convenience below, let Δ=∑i=1∧i≠j∧i≠j+1nCXi2−∑k=1mCXi∪Yk2,Xj=x,Xj+1=y,∑k=1mXj∩Yk=ax,∑k=1mXj+1∩Yk=by and 0≤a,b≤1, we have the result as follows:(12)IEPUD|B=Δ+CXj∪Xj+12−∑k=1mCXj∪Xj+1∩Yk2=Δ+x+yx+y−12−ax+byax+by−12IEPUD|P=Δ+Cxj2+Cxj+12−∑k=1mCxj∩Yk2−∑k=1mCxj+1∩Yk2=Δ+xx−12+yy−12−axax−12−byby−12IEPUD|B−IEPUD|P=xy−axby.
Since0≤a,b≤1, IEPUD|B−IEPUD|P=Cxi∪xj2(13)−Cxi2−Cxj2≥0,WeaveIEPUD|P≤IEPUD|BTheorem 4.
LetS=U,C∪D be a decision table and U is a data set without duplicate samples, then IEPUD|C=0.Proof.
AssumeU/C=U1,U2,…,Un, Since U′ is a data set without duplicate samples, U1=U2=…=Un=1, So IEPUD|C=∑i=1n0.Definition 7.
LetS=U,C∪D be a decision table and B⊆C. U is a data set without duplicate samples. Then B is a relative reduction based on the following indistinguishable element-pair of S if B satisfies:(1);
IEPUD|B=IEPUD|C(2);
∀a∈B,IEPUD|B−a≠IEPUD|BDefinition 8.
(see [30]). Let S=U,A be an information system. For any a∈A the value of object x about attribute a is fa,x. Let Disa=xi,xj|fa,xi≠fa,xj and DisA=∪a∈ADisa, we called Dis(a) and Dis(A) the discernibility relations in terms of a and A, respectively.Definition 9.
(see [30]). Suppose U=x1,x2,⋯,xn, let MS=cijn×n denote a n×n matrix, where cij=a∈A:fa,xi≠fa,xj for xi,xj∈DisA, otherwise cij=∅, MS is called the discernibility matrix of the information system S=U,A.


## 3. The Algorithm Based on Indistinguishable Element-Pair

The indistinguishable element-pair algorithm obtains the importance of attributes by means of discernibility matrix information and does not create the discernibility matrix. We should compute the positive region and negative region at first, then achieve the simplified decision table. Reduce the calculation of duplicate data objects, saving a lot of time.


### 3.1. Compute the Positive and Negative Region (CPNR)

In each detailed subdivision, if the decision value of the sample is different, then we put the first samplex into the negative region set and let Uneg=Uneg and ∪x the rest put the x into the positive region set and let U=Upos∪Uneg. In the process of calculating positive and negative regions, equivalence class division needs to be calculated continuously. Here is an ingenious method, which can greatly speed up the calculation speed of equivalence class partitioning. The details are described as follows: for i in range (n): list [array[i] AppendixAppendix for clarity. (i).If the data object has an integer value on the attribute, the characteristics of an integer can be used. By collecting all the objects with the same value in the same subdivision, equivalence class division can be obtained quickly and accurately.Example 2.
There are six data objects, the values of attributeA are 1, 2, 1, 3, 2, and 1, respectively. Let Array [1–6] = {1, 2, 1, 3, 2, 1}, collecting the data objects with the same value into the same list. Array [1] = Array [3] = Array [6] = 1, we have list [1] = {1, 3, 6}. Array [2] = Array [5] = 2, we have list [2] = {2, 5}. Array [4] = 3, we have list [3] = {4}.
Abovementioned all, data objects 1, 3, and 6 are divided into the same subdivision, and data objects 2 and 5 are divided into the same subdivision. (Algorithm 1)Algorithm 1: CPNR algorithm computes the positive and negative region method.
Input: U,R=∅,count=0,C,DOutput: U′,Upos′,Uneg′/∗U′ is a data set without duplicate samples, Upos′ is a positive region, data set and Uneg′ is a negative region data set. ∗/Step 1: U′=Upos′=Uneg′=∅Step 2: U″=UStep 3: while (count≤U&&R⊆C) do{Step 3.1: for anyCi⊂C−R, let R=R∪CiStep 3.2: computeU″/R=U1″,U2″,…,Un″,Step 3.3: statistics of the subdivisions regarded asUi″=1, let Upos′=Upos′∪Uik, count add 1. }Step 4: scan the remaining subdivisions.


### 3.2. The Attribute Reduction Algorithm Based on Indistinguishable Element-Pair (IEP)

Supposef (x, a) is the value of the data object x on the conditional attribute A. There have two different data objects xi and xj, if fa,xi≠fa,xj, then a is recorded in the discernibility matrix. Another way to think about it is to take down indistinguishable data objects. After research, all samples divided by the same subdivision are indistinguishable. Algorithm IEP is described as follows: (Algorithm 2)Algorithm 2: The indistinguishable element-pair algorithm (IEP).
Input:S=U,C∪DOutput: redStep 1: red←∅,B←∅Step 2: Calculate the positive region Upos and negative region Uneg with CPNRStet 3: get the simplified decision table U′ through Step 2Step 4: IEP←Sys.maxsize, IEP_list←∅Step 5: while (IEP>0) do {Step5.1: IEP(b, B, D) = min{IEP(a, B, D), a∈C−BStep 5.2:IEP_list←IEP_listb,B,DStep 5.3: delete all the subdivisions and the card is 1 ofIEP_listStep 5.4:B←B∪b}Step 6: red←B return redExample 3.
SupposeU′ is a simplified decision table without repeated samples in Table 3. Based on the definition equivalence class, we have U′/a∪D = {{1, 4},{2, 3},{5, 6∗}}.The bold data objects of the subdivision have the same value on the attribute a∪D. The asterisked (∗) data objects belong to the negative region set. Based on the Definition 6, we have IEPU′D|a=C22+0+C22=2, U′/b∪D= {{1, 2, 3, 4},{5, 6∗}}, IEPU′D|b=C42−C32+C22=4,U′/c∪D = {{1, 3, 6∗},{2, 5},{4}}, IEPU′D|c=C32−C22+C22+0 = 3, U′/e∪D = {{1, 3, 5, 6∗},{2, 4}} IEPU′D|e=C42−C22+C22=6
When the conditional attribute with the lower indistinguishable degree has a stronger distinguishing ability, we select the attribute a, and let red = {a}. If the amount of information is not zero, we enter the next cycle. On the basis of it is divided by conditional attributes {b, c, e}, we obtain the following: U′/red∪b∪D = {{1, 4},{2, 3},{5, 6∗}} IEPU′D|red∪b=C22+0+C22=2, U′/red∪c∪D = {{1}, {2}, {3}, {4}, {5}, {6}}, IEPU′D|red∪c=0, U′/red∪e∪D = {{1}, {2}, {3}, {4}, {5, 6∗}} IEPU′, D|e=0+0+0+0+C22=1.
BecauseIEPU′D|red∪c=0 is the smallest, we select c to merge into the reduced set red. Now, the amount of information is 0, and the algorithm terminates. Reduce result is red=a,c.Table 3
Example of decision table.
NoabceD10010121001131010140021252100262110∗


### 3.3. The Existing Static Reduction Algorithms

The typical discernibility matrix algorithm and the related improved algorithms constantly revise the definition of discriminant matrix from the perspective of distinguishable data objects, leading to the inevitable consumption of a large amount of space resources to store the discernibility matrix. The phenomenon of memory overflow often occurs during the reduction of large data sets, which leads to the failure to complete the reduction task.The IEP method does not need to store discernibility matrix and is suitable for reduction of large-scale data sets. In order to further verify the effectiveness of the IEP presented in this paper, let’s analyze the complexity of time and space and other similar algorithms based on discernibility matrix. In IEP algorithm,U is a decision table. Steps 2-3 focus on calculating the simplified decision table U′ and U′≤U. The time complexity of computing U′ is OUC. The time complexity of steps 5 is OC2−Red2U′. The space complexity of data set is OUC, steps 5 want space OU′. Therefore, the total time complexity of algorithm IEP is OUC+OC2−Red2·U′ and the space complexity is OUC. Table 3 shows a comparison of the time and space complexity of computing the reductions by Algorithms HU [18], DDMSE [22], and MEDA [30]. From Table 4, we can obtain the time complexity of IEP is usually much smaller than the algorithms HU because of OC2−Red2·U′+OUC is lower than OUC+OU2C2. The time complexity of the algorithm MEDA is OU2C2 . The space complexity of algorithm IEP is OUC but the space complexity of storing the discernibility matrix of HU, DDMSE is OU2C. Therefore, the space consumption of algorithm IEP is much less than that of algorithms HU, DDMSE, and MEDA.Table 4
A comparison of time and space complexity of IEP, HU, DDMSE, and MEDA.
AlgorithmTimeSpaceIEPOUC+C2−Red2·U′O|U||C|HUOUC+OU2C2O|U|2|C|DDMSEOUC+OU2C2O|U|2|C|MEDAOU2C2OU2


## 3.1. Compute the Positive and Negative Region (CPNR)

In each detailed subdivision, if the decision value of the sample is different, then we put the first samplex into the negative region set and let Uneg=Uneg and ∪x the rest put the x into the positive region set and let U=Upos∪Uneg. In the process of calculating positive and negative regions, equivalence class division needs to be calculated continuously. Here is an ingenious method, which can greatly speed up the calculation speed of equivalence class partitioning. The details are described as follows: for i in range (n): list [array[i] AppendixAppendix for clarity. (i).If the data object has an integer value on the attribute, the characteristics of an integer can be used. By collecting all the objects with the same value in the same subdivision, equivalence class division can be obtained quickly and accurately.Example 2.
There are six data objects, the values of attributeA are 1, 2, 1, 3, 2, and 1, respectively. Let Array [1–6] = {1, 2, 1, 3, 2, 1}, collecting the data objects with the same value into the same list. Array [1] = Array [3] = Array [6] = 1, we have list [1] = {1, 3, 6}. Array [2] = Array [5] = 2, we have list [2] = {2, 5}. Array [4] = 3, we have list [3] = {4}.
Abovementioned all, data objects 1, 3, and 6 are divided into the same subdivision, and data objects 2 and 5 are divided into the same subdivision. (Algorithm 1)Algorithm 1: CPNR algorithm computes the positive and negative region method.
Input: U,R=∅,count=0,C,DOutput: U′,Upos′,Uneg′/∗U′ is a data set without duplicate samples, Upos′ is a positive region, data set and Uneg′ is a negative region data set. ∗/Step 1: U′=Upos′=Uneg′=∅Step 2: U″=UStep 3: while (count≤U&&R⊆C) do{Step 3.1: for anyCi⊂C−R, let R=R∪CiStep 3.2: computeU″/R=U1″,U2″,…,Un″,Step 3.3: statistics of the subdivisions regarded asUi″=1, let Upos′=Upos′∪Uik, count add 1. }Step 4: scan the remaining subdivisions.


## 3.2. The Attribute Reduction Algorithm Based on Indistinguishable Element-Pair (IEP)

Supposef (x, a) is the value of the data object x on the conditional attribute A. There have two different data objects xi and xj, if fa,xi≠fa,xj, then a is recorded in the discernibility matrix. Another way to think about it is to take down indistinguishable data objects. After research, all samples divided by the same subdivision are indistinguishable. Algorithm IEP is described as follows: (Algorithm 2)Algorithm 2: The indistinguishable element-pair algorithm (IEP).
Input:S=U,C∪DOutput: redStep 1: red←∅,B←∅Step 2: Calculate the positive region Upos and negative region Uneg with CPNRStet 3: get the simplified decision table U′ through Step 2Step 4: IEP←Sys.maxsize, IEP_list←∅Step 5: while (IEP>0) do {Step5.1: IEP(b, B, D) = min{IEP(a, B, D), a∈C−BStep 5.2:IEP_list←IEP_listb,B,DStep 5.3: delete all the subdivisions and the card is 1 ofIEP_listStep 5.4:B←B∪b}Step 6: red←B return redExample 3.
SupposeU′ is a simplified decision table without repeated samples in Table 3. Based on the definition equivalence class, we have U′/a∪D = {{1, 4},{2, 3},{5, 6∗}}.The bold data objects of the subdivision have the same value on the attribute a∪D. The asterisked (∗) data objects belong to the negative region set. Based on the Definition 6, we have IEPU′D|a=C22+0+C22=2, U′/b∪D= {{1, 2, 3, 4},{5, 6∗}}, IEPU′D|b=C42−C32+C22=4,U′/c∪D = {{1, 3, 6∗},{2, 5},{4}}, IEPU′D|c=C32−C22+C22+0 = 3, U′/e∪D = {{1, 3, 5, 6∗},{2, 4}} IEPU′D|e=C42−C22+C22=6
When the conditional attribute with the lower indistinguishable degree has a stronger distinguishing ability, we select the attribute a, and let red = {a}. If the amount of information is not zero, we enter the next cycle. On the basis of it is divided by conditional attributes {b, c, e}, we obtain the following: U′/red∪b∪D = {{1, 4},{2, 3},{5, 6∗}} IEPU′D|red∪b=C22+0+C22=2, U′/red∪c∪D = {{1}, {2}, {3}, {4}, {5}, {6}}, IEPU′D|red∪c=0, U′/red∪e∪D = {{1}, {2}, {3}, {4}, {5, 6∗}} IEPU′, D|e=0+0+0+0+C22=1.
BecauseIEPU′D|red∪c=0 is the smallest, we select c to merge into the reduced set red. Now, the amount of information is 0, and the algorithm terminates. Reduce result is red=a,c.Table 3
Example of decision table.
NoabceD10010121001131010140021252100262110∗


## 3.3. The Existing Static Reduction Algorithms

The typical discernibility matrix algorithm and the related improved algorithms constantly revise the definition of discriminant matrix from the perspective of distinguishable data objects, leading to the inevitable consumption of a large amount of space resources to store the discernibility matrix. The phenomenon of memory overflow often occurs during the reduction of large data sets, which leads to the failure to complete the reduction task.The IEP method does not need to store discernibility matrix and is suitable for reduction of large-scale data sets. In order to further verify the effectiveness of the IEP presented in this paper, let’s analyze the complexity of time and space and other similar algorithms based on discernibility matrix. In IEP algorithm,U is a decision table. Steps 2-3 focus on calculating the simplified decision table U′ and U′≤U. The time complexity of computing U′ is OUC. The time complexity of steps 5 is OC2−Red2U′. The space complexity of data set is OUC, steps 5 want space OU′. Therefore, the total time complexity of algorithm IEP is OUC+OC2−Red2·U′ and the space complexity is OUC. Table 3 shows a comparison of the time and space complexity of computing the reductions by Algorithms HU [18], DDMSE [22], and MEDA [30]. From Table 4, we can obtain the time complexity of IEP is usually much smaller than the algorithms HU because of OC2−Red2·U′+OUC is lower than OUC+OU2C2. The time complexity of the algorithm MEDA is OU2C2 . The space complexity of algorithm IEP is OUC but the space complexity of storing the discernibility matrix of HU, DDMSE is OU2C. Therefore, the space consumption of algorithm IEP is much less than that of algorithms HU, DDMSE, and MEDA.Table 4
A comparison of time and space complexity of IEP, HU, DDMSE, and MEDA.
AlgorithmTimeSpaceIEPOUC+C2−Red2·U′O|U||C|HUOUC+OU2C2O|U|2|C|DDMSEOUC+OU2C2O|U|2|C|MEDAOU2C2OU2


## 4. Incremental Attribute Reduction Algorithm Based on Indistinguishable Element-Pair

The abovementioned algorithm IEP only adapts to the static data set. In reality, most data sets are dynamic. The traditional static methods are ineffective. Therefore, it is necessary to study some algorithms for dynamic data sets.


### 4.1. An Incremental Method to Calculate Indistinguishable Element-Pair after Adding Some Objects (IEPAO)

There are two kinds of data objects as to updating in data set: increase and decrease. Let’s introduce the first one: to increase the data objects. When some data objects are added to data set, we only need to calculate the IEP of the updating part and obtain the amount of information with the help of the previous reduction result red. If the amount of information is zero, the updated reduction result is red. Otherwise, the added part objects will be merged with the basic data, we compute the amount of information based on detailed subdivision according to attribute setred∪D.Theorem 5.
LetS=U,C∪D be a decision system, U/C∪D=X1,X2,⋯,Xm. It is assumed that UΔx is the new data objects, UΔx/C∪D=Y1,Y2,⋯,Ym′,Xi∪Yi=Xi′,1≤i≤k. According to the division of U/C∪D,UΔx/C∪D, we have U∪UΔx/C∪D=X1′,X2′,…,Xk′,Xk+1,Xk+2,…,Xm,Yk+1,Yk+2,…,Ym′. Then IEPU∪UΔxD|C=IEPUD|C+IEPUΔxD|C+UUΔx−∑i=1kXiYiProof.
See Appendix 1 for the proof process.
According to Theorem 5, the value ofIEPUD|C is related to IEPUΔxD|C, where add data objects. We propose the algorithm IEPAO based on this characteristic. (Algorithm 3)
In Table5, red is the reduction result before adding data, red′ is the final reduction result IEP can only reduce static data set the time complexity is OUC+OC2−red2·U If data objects UΔx is added, the time complexity becomes OU+UΔx·C+OC2−red2U+UΔx. The IEPAO algorithm uses the previous reduction results, the time complexity is OUΔx·C+OC−red2−red′−red2·minUΔx,U. It clearly shows that the calculation time of IEPAO is less than IEP.Algorithm 3: Incremental updating algorithm based on IEP when adding some objects (IEPAO).
Input:U,U/red∪D, red and incremental object sets UΔx, where U is the simplified decision table before update.Output: Updated reduction set red′Step 1: Mark the negative region data objects, list←U/red∪D, red′←redStep 2: Compute IEPUΔxD|red′Step 3: We may assume that U/red′∩UΔx/red′ has k subdivisions and Xi∈U,Yi∈UΔx, then compute ∑i=1kXiYi.Step 4: Compute Info=IEPUD|red′+IEPUΔxD|red′+UUΔx−∑i=1kXiYiStep 5: If Info = 0, algorithm is terminated elseWhileInfo≠0 do {Letlist←U∪UΔx/red′for a inC−red′ {ComputeIEPU∪UΔxD|red″∪a,a∗←minIEPU∪UΔxD|red″∪ared′←red′∪a∗,list←U∪UΔx/red′ }ComputeInfo=IEPU∪UΔxD|red′ }Step 6: return red′Table 5
The time complexity of each step of algorithm IEPAO.
Step noTime complexityResultStep 1OUΔxCGetUΔxStep 2OUΔx/red∪DGetIEPUΔxD|redStep 3OU/red+OUΔx/redGetU∪UΔx/redStep 4O1Get infoStep 5OUΔx•C+OC−red2−red−red2•minUΔx,UGetred′


### 4.2. Incremental Updating Attribute Reduction Algorithm When Delete Some Objects (IEPDO)

In reality, some data will be discarded after a long time. IEPDO algorithm can reduce the deleted data objects dynamically.Theorem 6.
LetS = U,C∪D be a decision system and U/C∪D=X1,X2,⋯,Xm. We assume that the deleted data object set is UΔx and UΔx/C∪D=Y1,Y2,⋯,Yk. From the definition of equivalence class divided, we have U−UΔx/C∪D=X1′,X2′,⋯,Xk′,Xk+1,⋯,Xm, where Xi′=Xi−Yi (i = 1, 2, …, k). If delete the data objects UΔx from U, the indistinguishable amount of information is IEPU−UΔxD|C, then IEPU−UΔxD|C=IEPUD|C+IEPUΔxD|C−UUΔx+∑i=1kXiYi.Proof.
(14)IEPU−UΔxD|C=CU−UΔx2−∑i=1kCXi−Yi2−∑i=k+1mCXi2=CU2+CUΔx2−UUΔx−∑i=1kCXi2+CYi2+∑i=1mXiYi−∑i=k+1mCXi2=IEPUD|C+IEPUΔxD|C−UUΔx+∑i=1kXiYi.
According to Theorem 6, the value ofIEPUD|C is related to IEPUΔxD|C where delete data objects. We propose the algorithm IEPDO based on this characteristic. (Algorithm 4)
When some objects are deleted, we have the indistinguishable information of updated data set, which needs a small amount of computation through the previous reduced result and deleted data objects. Suppose the final reduction result isred′, usually, red′ less than or equal to red and less than C. The time complexity comparison of IEPDO and IEP is provided in Table 6. Obviously, the time complexity of IEPDO is smaller than IEP.Algorithm 4: Increment updating algorithm based on IEP when delete some objects (IEPDO).
Input:U,U/red∪D, red and delete object sets UΔx, where U is the simplified decision table before update.Output: red′Step 1: Mark the deleted data objects is UΔx, list←U/red∪D, red′←redStep 2: Compute IEPUΔxD|red′;Step 3: We may assume that U/red′∩UΔx/red′ has k subdivisions and Xi∈U,Yi∈UΔx, then compute ∑i=1kXiYiStep 4: Compute Info=IEPUD|red′+IEPUΔx  D|red′−UUΔx+∑i=1kXiYiStep 5: Let list←U−UΔx/red′fora in red′ {ComputeInfo=IEPU−UΔxD|red′−a,if Info = 0 thenred′←red′−a∗ and list←U−UΔx/red′elsebreak;}Step 6: return red′Table 6
The time complexity of algorithm IEPDO and IEP.
AlgorithmTime complexityIEPOU−UΔxC+OC2−red2U−UΔxIEPDOOU−UΔxred+Ored2−red′2U−UΔx


## 4.1. An Incremental Method to Calculate Indistinguishable Element-Pair after Adding Some Objects (IEPAO)

There are two kinds of data objects as to updating in data set: increase and decrease. Let’s introduce the first one: to increase the data objects. When some data objects are added to data set, we only need to calculate the IEP of the updating part and obtain the amount of information with the help of the previous reduction result red. If the amount of information is zero, the updated reduction result is red. Otherwise, the added part objects will be merged with the basic data, we compute the amount of information based on detailed subdivision according to attribute setred∪D.Theorem 5.
LetS=U,C∪D be a decision system, U/C∪D=X1,X2,⋯,Xm. It is assumed that UΔx is the new data objects, UΔx/C∪D=Y1,Y2,⋯,Ym′,Xi∪Yi=Xi′,1≤i≤k. According to the division of U/C∪D,UΔx/C∪D, we have U∪UΔx/C∪D=X1′,X2′,…,Xk′,Xk+1,Xk+2,…,Xm,Yk+1,Yk+2,…,Ym′. Then IEPU∪UΔxD|C=IEPUD|C+IEPUΔxD|C+UUΔx−∑i=1kXiYiProof.
See Appendix 1 for the proof process.
According to Theorem 5, the value ofIEPUD|C is related to IEPUΔxD|C, where add data objects. We propose the algorithm IEPAO based on this characteristic. (Algorithm 3)
In Table5, red is the reduction result before adding data, red′ is the final reduction result IEP can only reduce static data set the time complexity is OUC+OC2−red2·U If data objects UΔx is added, the time complexity becomes OU+UΔx·C+OC2−red2U+UΔx. The IEPAO algorithm uses the previous reduction results, the time complexity is OUΔx·C+OC−red2−red′−red2·minUΔx,U. It clearly shows that the calculation time of IEPAO is less than IEP.Algorithm 3: Incremental updating algorithm based on IEP when adding some objects (IEPAO).
Input:U,U/red∪D, red and incremental object sets UΔx, where U is the simplified decision table before update.Output: Updated reduction set red′Step 1: Mark the negative region data objects, list←U/red∪D, red′←redStep 2: Compute IEPUΔxD|red′Step 3: We may assume that U/red′∩UΔx/red′ has k subdivisions and Xi∈U,Yi∈UΔx, then compute ∑i=1kXiYi.Step 4: Compute Info=IEPUD|red′+IEPUΔxD|red′+UUΔx−∑i=1kXiYiStep 5: If Info = 0, algorithm is terminated elseWhileInfo≠0 do {Letlist←U∪UΔx/red′for a inC−red′ {ComputeIEPU∪UΔxD|red″∪a,a∗←minIEPU∪UΔxD|red″∪ared′←red′∪a∗,list←U∪UΔx/red′ }ComputeInfo=IEPU∪UΔxD|red′ }Step 6: return red′Table 5
The time complexity of each step of algorithm IEPAO.
Step noTime complexityResultStep 1OUΔxCGetUΔxStep 2OUΔx/red∪DGetIEPUΔxD|redStep 3OU/red+OUΔx/redGetU∪UΔx/redStep 4O1Get infoStep 5OUΔx•C+OC−red2−red−red2•minUΔx,UGetred′


## 4.2. Incremental Updating Attribute Reduction Algorithm When Delete Some Objects (IEPDO)

In reality, some data will be discarded after a long time. IEPDO algorithm can reduce the deleted data objects dynamically.Theorem 6.
LetS = U,C∪D be a decision system and U/C∪D=X1,X2,⋯,Xm. We assume that the deleted data object set is UΔx and UΔx/C∪D=Y1,Y2,⋯,Yk. From the definition of equivalence class divided, we have U−UΔx/C∪D=X1′,X2′,⋯,Xk′,Xk+1,⋯,Xm, where Xi′=Xi−Yi (i = 1, 2, …, k). If delete the data objects UΔx from U, the indistinguishable amount of information is IEPU−UΔxD|C, then IEPU−UΔxD|C=IEPUD|C+IEPUΔxD|C−UUΔx+∑i=1kXiYi.Proof.
(14)IEPU−UΔxD|C=CU−UΔx2−∑i=1kCXi−Yi2−∑i=k+1mCXi2=CU2+CUΔx2−UUΔx−∑i=1kCXi2+CYi2+∑i=1mXiYi−∑i=k+1mCXi2=IEPUD|C+IEPUΔxD|C−UUΔx+∑i=1kXiYi.
According to Theorem 6, the value ofIEPUD|C is related to IEPUΔxD|C where delete data objects. We propose the algorithm IEPDO based on this characteristic. (Algorithm 4)
When some objects are deleted, we have the indistinguishable information of updated data set, which needs a small amount of computation through the previous reduced result and deleted data objects. Suppose the final reduction result isred′, usually, red′ less than or equal to red and less than C. The time complexity comparison of IEPDO and IEP is provided in Table 6. Obviously, the time complexity of IEPDO is smaller than IEP.Algorithm 4: Increment updating algorithm based on IEP when delete some objects (IEPDO).
Input:U,U/red∪D, red and delete object sets UΔx, where U is the simplified decision table before update.Output: red′Step 1: Mark the deleted data objects is UΔx, list←U/red∪D, red′←redStep 2: Compute IEPUΔxD|red′;Step 3: We may assume that U/red′∩UΔx/red′ has k subdivisions and Xi∈U,Yi∈UΔx, then compute ∑i=1kXiYiStep 4: Compute Info=IEPUD|red′+IEPUΔx  D|red′−UUΔx+∑i=1kXiYiStep 5: Let list←U−UΔx/red′fora in red′ {ComputeInfo=IEPU−UΔxD|red′−a,if Info = 0 thenred′←red′−a∗ and list←U−UΔx/red′elsebreak;}Step 6: return red′Table 6
The time complexity of algorithm IEPDO and IEP.
AlgorithmTime complexityIEPOU−UΔxC+OC2−red2U−UΔxIEPDOOU−UΔxred+Ored2−red′2U−UΔx


## 5. Experiment Analysis

In this section, lots of experiments are conducted on both static and dynamic data sets to verify the efficiency of the proposed attribute reduction algorithms. In the experiments, fifteen data sets are downloaded from UCI. Table7 displays the basic information of each data set, where U represents the number of samples, C represents the number of conditional attributes, D represents the number of decision classes, and Type represents the decision system is consistency (Y in short) or inconsistency (N in short), respectively. For the convenience of the following description, the data set Letters recognition is abbreviated as Letters, Mammographic Mass as Mass. All the character or string features are normalized into an integer. All of the experiments have been implemented on a PC with Windows 10, Core™ i7-10710U CPU 1.10 GHz 1.61 Hz and 8 G memory. All of the algorithms are coded in python, and the used software isPyCharm Community Edition 2020.2.3 × 64 and Weak3.2.Table 7
A description of data sets.
DatasetUCDConsistency?Mushroom8124222YAudiology2267024YBlance-scale62543YBreast28692YCar172864YLetters200001726YTicdata20005822852YGene3190603YNursery1296085YHandwritten56206410YMass83062NHepatitis155192NConnect-467557423YChess kr-kp3196362YSpect heart267222N


### 5.1. Performance Comparison between Algorithm IEP and Other Discernibility Matrix Algorithms Based on Static Data Sets

In experiment, we consider the fifteen data sets from UCI listed in Table7. These selected data sets are reasonably distributed, including large data sets for Letters and small data sets for Hepatitis, Audiology, consistent data sets (Gene and Mushroom, etc.), and inconsistent data sets (Mass and Spect heart). In order to show the time effect of each algorithm, we refer to the SpeedupRatio= Tbaseline/T method proposed by literature [31], is the executing time of a typical algorithm. Tbaseline reaches its maximum when the typical algorithm cannot perform the reduction task. Then SpeedupRatio∈0,∞.For the different data sets, the SpeedupRatio of IEP and the other three algorithms (Hu, DDMSE, and MEDA) is also different. Table8 shows the SpeedupRatio of IEP, Hu, DDMSE, and MEDA. The data in bold indicates that the algorithm runs the fastest on a certain data set. In Table 8, we have the unpredictable speed of Hu, DDMSE, and MEDA on Letters and Connect-4 data sets because these two data sets are too large. The SpeedupRatios of IEP are 1.6109 and 2.4286, respectively, on data sets Audiology and Hepatitis. Since the values are greater than 1, the speed of IEP is faster than Hu on Audiology and Hepatitis. From Table 8, IEP is the fastest but the difference is not obvious among the Hu, DDMSE and MEDA based on small data sets. Overall, the SpeedupRatio is related to U2·C. The smaller the U2·C, the faster the speed.Table 8
A speedup ratio comparison of IEP, MEDA, HU, and DDMSE.
Data setSpeedup ratioIEPMEDAHUDDMSEMushroom81.9164.372310.6954Audiology1.61091.583910.7454Blance-scale17.8579.191211.1220Breast5.45714.340911.2566Car41.63910.529111.2320Letters∞———Ticdata200019.302118.110811.5578Gene26.47134.575610.5976Nursery1397.6534.36813.5097Handwritten54.57511.017110.4773Mass22.389013.433311.0824Hepatitis2.428621.847810.9884Connect-4∞———Chess kr-kp26.76011.79711.3320Spect heart10.06002.08610.9860The bolded values are the fastest speed ratio.Table9 shows the reduction and performance time of the comparisons of four algorithms. In Table 9, time is measured in seconds, red is reduction and the data in bold represents the minimum reduction time of many algorithms. The IEP takes only 1.953 seconds to reduce the Mushroom data set, while DDMSE takes 230.071 seconds. The main reason is that DDMSE modifies the definition of discernibility information to improve the distinguishing ability, leading to the increasing number of compared element pairs. Then, it makes the space for storing discernibility matrix larger and larger. On data sets Letters and Connect-4, IEP can quickly and effectively obtain the reduction results, while Hu, DDMSE, and MEDA cannot complete the reduction task due to insufficient memory. On the small data set Breast and Balance-scale, IEP needs to waste 0.035 seconds, while the other three algorithms take 0.191,0.152 and 0.044 seconds respectively. For the reduction on a small data set, the time effect of IEP and other algorithms is not obvious.Table 9
A time and reduced comparison IEP, MEDA, HU, and DDMSE.
Data setsIEPMEDAHUDDMSERedTime (s)RedTime (s)RedTime (s)RedTime (s)Mushroom41.953536.594159.9814230.071Audiology140.293140.298130.472140.633Lance-scale40.03540.06840.62540.557Breast90.03590.04490.19190.152Car60.13360.52665.53864.495Letters125.892—∞—∞—∞Ticdata2000237.724238.23223149.0852395.701Gene102.5931015.0011068.63910114.863Nursery81.32853.67981844.8668525.649Handwritten74.6888251.5587255.8487536.041Mass50.05450.0951.20951.117Hepatitis80.03990.04680.08580.086Connect-43464.358—∞—∞—∞Chess kp-kr292.222933.0592959.4072944.568Spect heart180.035180.1685180.3521180.357The time shown in bold is the least time.Compared with other discernibility matrix algorithms, IEP has less time consumption, while getting the same reduction results based on the same data sets. Especially, the reduction effect is more obvious on large-scale data sets.


### 5.2. Time Comparison of IEPAO and IEP When Adding Data Objects

In the following experiments, we select nine data sets for dynamic update experiments from Table7. For each data set, 50% of the data objects are randomly selected as the original object set, and the remaining data are randomly generated at the proportions of 10%, 20%, 30%, 40%, and 50% as incremental object sets, respectively. The incremental part is divided into 5 groups of experiments, each group is executed 10 times and computes the average time. Experimental results are outlined in Figure 1. In the experiment of IEP, time statistics do not include the calculating time of original objects.Figure 1
The time comparison of IEP and IEPAO when adding data objects. (a) Chess kr-kp. (b) Connect-4. (c) Gene. (d) Handwritten. (e) Hepatitis. (f) Letters. (g) Mushroom. (h) Nursery. (i) Ticdata2000.
(a)(b)(c)(d)(e)(f)(g)(h)(i)In each subfigures of Figure1, the x-coordinate represents the increment ratio, and the unit is the proportion of the increased part of the data in the total data. The value of the y-coordinate y is the time of computing reduction in different incremental, which are measured by seconds. In Figure 1, the curve with a five-pointed star mark shows the change in the running time of IEPAO, while the curve with a circle mark indicates the variation of IEP.It can be seen in Figure1 that as the size of data set expands, the time of calculating reduction will increase. The calculation time of IEPAO is much less than IEP. The main reason for this phenomenon is that when we add the new objects into the data set, IEPAO only needs to calculate the added part of the data, and then combine the previous reduction results in obtaining the changed result quickly. But, IEP can only process static data sets. When new data is added, it takes longer time to recalculate the original data and the added part. On the whole, the performance of IEPAO is relatively stable in Figure 1. With the increase of updated data, the calculation time is also increasing. But, IEPAO has an anomaly in that the calculation time decreased as the data increasing. The subfigure (f) of Figure 1 displays that IEPAO takes 4.543 seconds to reduce the Letters data set with a 20% increment, and 4.253 seconds to reduce the data with 30% increment. The main reason is that when the data increases, it accelerates the division of data on conditional attributes. Since the amount of information is zero based on subdivision of cardinality 1, these objects are constantly deleted during the reduction process to accelerate the convergence speed.


### 5.3. Time Comparison of IEPDO and IEP When Deleting Data Objects

The same as Section5.2, nine data sets are selected in Table 7. Take the original data of each data sets as the basic data, and randomly select 10%, 20%, 30%, 40%, and 50% objects in the remaining data to delete respectively. Use IEP and IEPDO to reduce the updated data. Each group of data was selected to repeat the experiment for 10 times and averaged the time of 10 times. The experimental results show in Figure 2. In each subfigure of Figure 2, x-axis represents the proportion of decrement data objects, while y-axis represents the computational time. The time is measured by seconds. The curve with five-pointed star mark in Figure 2 shows the change in the running time of the IEPDO, whileFigure 2
The time comparison of IEP and IEPDO when deleting data objects. The curve with circle mark shows the calculation time variation form of IEP. (a) Chess kr-kp. (b) Connect-4. (c) Gene. (g) Mushroom. (h) Nursery. (i) Ticdata2000.
(a)(b)(c)(d)(e)(f)(g)(h)(i)As shown in Figure2, when we delete some data objects from data set, the computational time of IEP and IEPDO will decrease accordingly. In the same computing environment, IEPDO takes less time than IEP. The IEPDO method only needs to calculate the updated objects when deleting data objects. Some updated objects when deleting data objects. Some conditional attributes with zero indistinguishable element-pair are removed from the reduction set. However, IEP takes longer time because of calculating the reduced data set from all conditional attributes. For the IEP selected, it takes 0.0338 seconds on the decreased 30% data objects of Hepatitis, while taking 0.0352 seconds to compute the deleted 40% data. It costs 1.233 seconds to calculate the decrease of 30% data of Nursery but takes 1.2451 seconds on the decrease of 40% data. Why the calculation time increases with the decreasing data is that the speed of dividing equivalence class is slowed down as it randomly selects some weak distinguish power on conditional attributes. The performance of IEPDO is relatively stable. By deleting data, the calculation time decreases. From nine subfigure of Figure 2, when we reduce the large-scale data, the time-consuming effect of IEPDO is more obvious with the decreased data objects, while the effect is not significant on small data sets, such as data sets of Chess kr-kp and Hepatitis.


### 5.4. Classification Accuracy Analysis of IEP, IEPAO, and IEPDO

In this section, the precision of classification is calculated on the selection of reducts obtained by the algorithms IEP, IEPAO, and IEPDO. Firstly, we take 50% of objects of each data set in nine data sets from Table7 as the basic data set, the rest 50% data as the incremental objects and select the algorithms IEP and IEPAO to reduce. Secondly, we delete 50% of objects randomly from each data set, using the algorithms IEP and IEPDO to process. Then, the classification accuracies are acquired by using J48, NaiveBayes (NB), RandomForest (RF), SMO classifier, and 10-fold cross-validation. The experimental results are shown in Tables 10 and 11.Table 10
A comparison of IEP and IEPAO on classification accuracy.
Data setJ48RFNBSMOIEP (%)IEPAO (%)IEP (%)IEPAO (%)IEP (%)IEPAO (%)IEP (%)IEPAO (%)Chess kr-kp99.436899.436899.092699.092688.329288.329295.431895.4318Connect-480.900683.657382.109985.075672.202774.790880.200282.4056Gene65.705368.092370.376272.903167.242469.641266.677169.4532Handwritten65.320367.562971.975772.908462.686864.098567.402170.2341Hepatitis79.354882.509482.580684.562080.000183.800780.000183.0924Letters87.515089.331895.205095.205060.250062.678076.625079.9138Mushroom100.00100.00100.00100.0098.609198.6091100.00100.00Nursery97.052597.052599.066499.066490.324190.324193.078793.0787Ticdata200082.022584.452180.149883.409777.902679.809482.715786.7732The bold values are the classification accuracy with the best classification performance.Table 11
A comparison of IEP and IEPDO on classification accuracy.
Data setJ48RFNBSMOIEP (%)IEPAO (%)IEP (%)IEPAO (%)IEP (%)IEPAO (%)IEP (%)IEPAO (%)Chess kr-kp99.436899.436899.292599.292599.292599.292596.731596.7315Connect-481.603884.427083.324186.082173.452877.563281.203284.3158Gene67.346769.934172.347875.931868.246371.348468.874172.5629Handwritten66.863069.458272.936074.934863.686865.537668.805374.6523Hepatitis81.337284.982384.236786.589281.020684.934182.569085.6538Letters88.851091.442696.002796.872161.243364.562977.453781.8942Mushroom100.00100.00100.00100.0098.804299.3589100.00100.00Nursery98.252598.912699.152199.152191.548291.548293.678893.6788Ticdata200083.324186.378282.458286.489278.978982.347284.532187.7626The bold values are the classification accuracy with the best classification performance.From Table10, it is clear that when some objects are added into the information systems, the average classification accuracy of the reduction found by incremental algorithm IEPAO is better than those of algorithm IEP in data sets Chess, Connect-4, Gene, Handwritten, Hepatitis, Letters and Ticdata2000 are coincide with those of algorithm IEP in data sets, e.g., Chess kr-kp, Mushroom, and Nursery. The experimental results show that the incremental algorithm IEPAO can find a feasible attribute reduction when incremental algorithm IEPAO replaces algorithm IEP. Moreover, the algorithm IEPAO can obtain high-quality attribute reduction with less time consumption. Similarly, when some objects are deleted from the original object set, the average classification accuracy of the reduction obtained by the algorithm IEPDO is better than IEP in data sets Connect-4, Gene, Handwritten, Hepatitis, Letters, and Ticdata2000.Accordingly, we can conclude that the incremental algorithm IEPDO can find a feasible attribute reduction.Hence, the experimental results verified that the proposed incremental methods IEPAO and IEPDO can obtain an efficient attribute reduction and provide a quick data preprocessing method for dynamic data sets.


## 5.1. Performance Comparison between Algorithm IEP and Other Discernibility Matrix Algorithms Based on Static Data Sets

In experiment, we consider the fifteen data sets from UCI listed in Table7. These selected data sets are reasonably distributed, including large data sets for Letters and small data sets for Hepatitis, Audiology, consistent data sets (Gene and Mushroom, etc.), and inconsistent data sets (Mass and Spect heart). In order to show the time effect of each algorithm, we refer to the SpeedupRatio= Tbaseline/T method proposed by literature [31], is the executing time of a typical algorithm. Tbaseline reaches its maximum when the typical algorithm cannot perform the reduction task. Then SpeedupRatio∈0,∞.For the different data sets, the SpeedupRatio of IEP and the other three algorithms (Hu, DDMSE, and MEDA) is also different. Table8 shows the SpeedupRatio of IEP, Hu, DDMSE, and MEDA. The data in bold indicates that the algorithm runs the fastest on a certain data set. In Table 8, we have the unpredictable speed of Hu, DDMSE, and MEDA on Letters and Connect-4 data sets because these two data sets are too large. The SpeedupRatios of IEP are 1.6109 and 2.4286, respectively, on data sets Audiology and Hepatitis. Since the values are greater than 1, the speed of IEP is faster than Hu on Audiology and Hepatitis. From Table 8, IEP is the fastest but the difference is not obvious among the Hu, DDMSE and MEDA based on small data sets. Overall, the SpeedupRatio is related to U2·C. The smaller the U2·C, the faster the speed.Table 8
A speedup ratio comparison of IEP, MEDA, HU, and DDMSE.
Data setSpeedup ratioIEPMEDAHUDDMSEMushroom81.9164.372310.6954Audiology1.61091.583910.7454Blance-scale17.8579.191211.1220Breast5.45714.340911.2566Car41.63910.529111.2320Letters∞———Ticdata200019.302118.110811.5578Gene26.47134.575610.5976Nursery1397.6534.36813.5097Handwritten54.57511.017110.4773Mass22.389013.433311.0824Hepatitis2.428621.847810.9884Connect-4∞———Chess kr-kp26.76011.79711.3320Spect heart10.06002.08610.9860The bolded values are the fastest speed ratio.Table9 shows the reduction and performance time of the comparisons of four algorithms. In Table 9, time is measured in seconds, red is reduction and the data in bold represents the minimum reduction time of many algorithms. The IEP takes only 1.953 seconds to reduce the Mushroom data set, while DDMSE takes 230.071 seconds. The main reason is that DDMSE modifies the definition of discernibility information to improve the distinguishing ability, leading to the increasing number of compared element pairs. Then, it makes the space for storing discernibility matrix larger and larger. On data sets Letters and Connect-4, IEP can quickly and effectively obtain the reduction results, while Hu, DDMSE, and MEDA cannot complete the reduction task due to insufficient memory. On the small data set Breast and Balance-scale, IEP needs to waste 0.035 seconds, while the other three algorithms take 0.191,0.152 and 0.044 seconds respectively. For the reduction on a small data set, the time effect of IEP and other algorithms is not obvious.Table 9
A time and reduced comparison IEP, MEDA, HU, and DDMSE.
Data setsIEPMEDAHUDDMSERedTime (s)RedTime (s)RedTime (s)RedTime (s)Mushroom41.953536.594159.9814230.071Audiology140.293140.298130.472140.633Lance-scale40.03540.06840.62540.557Breast90.03590.04490.19190.152Car60.13360.52665.53864.495Letters125.892—∞—∞—∞Ticdata2000237.724238.23223149.0852395.701Gene102.5931015.0011068.63910114.863Nursery81.32853.67981844.8668525.649Handwritten74.6888251.5587255.8487536.041Mass50.05450.0951.20951.117Hepatitis80.03990.04680.08580.086Connect-43464.358—∞—∞—∞Chess kp-kr292.222933.0592959.4072944.568Spect heart180.035180.1685180.3521180.357The time shown in bold is the least time.Compared with other discernibility matrix algorithms, IEP has less time consumption, while getting the same reduction results based on the same data sets. Especially, the reduction effect is more obvious on large-scale data sets.


## 5.2. Time Comparison of IEPAO and IEP When Adding Data Objects

In the following experiments, we select nine data sets for dynamic update experiments from Table7. For each data set, 50% of the data objects are randomly selected as the original object set, and the remaining data are randomly generated at the proportions of 10%, 20%, 30%, 40%, and 50% as incremental object sets, respectively. The incremental part is divided into 5 groups of experiments, each group is executed 10 times and computes the average time. Experimental results are outlined in Figure 1. In the experiment of IEP, time statistics do not include the calculating time of original objects.Figure 1
The time comparison of IEP and IEPAO when adding data objects. (a) Chess kr-kp. (b) Connect-4. (c) Gene. (d) Handwritten. (e) Hepatitis. (f) Letters. (g) Mushroom. (h) Nursery. (i) Ticdata2000.
(a)(b)(c)(d)(e)(f)(g)(h)(i)In each subfigures of Figure1, the x-coordinate represents the increment ratio, and the unit is the proportion of the increased part of the data in the total data. The value of the y-coordinate y is the time of computing reduction in different incremental, which are measured by seconds. In Figure 1, the curve with a five-pointed star mark shows the change in the running time of IEPAO, while the curve with a circle mark indicates the variation of IEP.It can be seen in Figure1 that as the size of data set expands, the time of calculating reduction will increase. The calculation time of IEPAO is much less than IEP. The main reason for this phenomenon is that when we add the new objects into the data set, IEPAO only needs to calculate the added part of the data, and then combine the previous reduction results in obtaining the changed result quickly. But, IEP can only process static data sets. When new data is added, it takes longer time to recalculate the original data and the added part. On the whole, the performance of IEPAO is relatively stable in Figure 1. With the increase of updated data, the calculation time is also increasing. But, IEPAO has an anomaly in that the calculation time decreased as the data increasing. The subfigure (f) of Figure 1 displays that IEPAO takes 4.543 seconds to reduce the Letters data set with a 20% increment, and 4.253 seconds to reduce the data with 30% increment. The main reason is that when the data increases, it accelerates the division of data on conditional attributes. Since the amount of information is zero based on subdivision of cardinality 1, these objects are constantly deleted during the reduction process to accelerate the convergence speed.


## 5.3. Time Comparison of IEPDO and IEP When Deleting Data Objects

The same as Section5.2, nine data sets are selected in Table 7. Take the original data of each data sets as the basic data, and randomly select 10%, 20%, 30%, 40%, and 50% objects in the remaining data to delete respectively. Use IEP and IEPDO to reduce the updated data. Each group of data was selected to repeat the experiment for 10 times and averaged the time of 10 times. The experimental results show in Figure 2. In each subfigure of Figure 2, x-axis represents the proportion of decrement data objects, while y-axis represents the computational time. The time is measured by seconds. The curve with five-pointed star mark in Figure 2 shows the change in the running time of the IEPDO, whileFigure 2
The time comparison of IEP and IEPDO when deleting data objects. The curve with circle mark shows the calculation time variation form of IEP. (a) Chess kr-kp. (b) Connect-4. (c) Gene. (g) Mushroom. (h) Nursery. (i) Ticdata2000.
(a)(b)(c)(d)(e)(f)(g)(h)(i)As shown in Figure2, when we delete some data objects from data set, the computational time of IEP and IEPDO will decrease accordingly. In the same computing environment, IEPDO takes less time than IEP. The IEPDO method only needs to calculate the updated objects when deleting data objects. Some updated objects when deleting data objects. Some conditional attributes with zero indistinguishable element-pair are removed from the reduction set. However, IEP takes longer time because of calculating the reduced data set from all conditional attributes. For the IEP selected, it takes 0.0338 seconds on the decreased 30% data objects of Hepatitis, while taking 0.0352 seconds to compute the deleted 40% data. It costs 1.233 seconds to calculate the decrease of 30% data of Nursery but takes 1.2451 seconds on the decrease of 40% data. Why the calculation time increases with the decreasing data is that the speed of dividing equivalence class is slowed down as it randomly selects some weak distinguish power on conditional attributes. The performance of IEPDO is relatively stable. By deleting data, the calculation time decreases. From nine subfigure of Figure 2, when we reduce the large-scale data, the time-consuming effect of IEPDO is more obvious with the decreased data objects, while the effect is not significant on small data sets, such as data sets of Chess kr-kp and Hepatitis.


## 5.4. Classification Accuracy Analysis of IEP, IEPAO, and IEPDO

In this section, the precision of classification is calculated on the selection of reducts obtained by the algorithms IEP, IEPAO, and IEPDO. Firstly, we take 50% of objects of each data set in nine data sets from Table7 as the basic data set, the rest 50% data as the incremental objects and select the algorithms IEP and IEPAO to reduce. Secondly, we delete 50% of objects randomly from each data set, using the algorithms IEP and IEPDO to process. Then, the classification accuracies are acquired by using J48, NaiveBayes (NB), RandomForest (RF), SMO classifier, and 10-fold cross-validation. The experimental results are shown in Tables 10 and 11.Table 10
A comparison of IEP and IEPAO on classification accuracy.
Data setJ48RFNBSMOIEP (%)IEPAO (%)IEP (%)IEPAO (%)IEP (%)IEPAO (%)IEP (%)IEPAO (%)Chess kr-kp99.436899.436899.092699.092688.329288.329295.431895.4318Connect-480.900683.657382.109985.075672.202774.790880.200282.4056Gene65.705368.092370.376272.903167.242469.641266.677169.4532Handwritten65.320367.562971.975772.908462.686864.098567.402170.2341Hepatitis79.354882.509482.580684.562080.000183.800780.000183.0924Letters87.515089.331895.205095.205060.250062.678076.625079.9138Mushroom100.00100.00100.00100.0098.609198.6091100.00100.00Nursery97.052597.052599.066499.066490.324190.324193.078793.0787Ticdata200082.022584.452180.149883.409777.902679.809482.715786.7732The bold values are the classification accuracy with the best classification performance.Table 11
A comparison of IEP and IEPDO on classification accuracy.
Data setJ48RFNBSMOIEP (%)IEPAO (%)IEP (%)IEPAO (%)IEP (%)IEPAO (%)IEP (%)IEPAO (%)Chess kr-kp99.436899.436899.292599.292599.292599.292596.731596.7315Connect-481.603884.427083.324186.082173.452877.563281.203284.3158Gene67.346769.934172.347875.931868.246371.348468.874172.5629Handwritten66.863069.458272.936074.934863.686865.537668.805374.6523Hepatitis81.337284.982384.236786.589281.020684.934182.569085.6538Letters88.851091.442696.002796.872161.243364.562977.453781.8942Mushroom100.00100.00100.00100.0098.804299.3589100.00100.00Nursery98.252598.912699.152199.152191.548291.548293.678893.6788Ticdata200083.324186.378282.458286.489278.978982.347284.532187.7626The bold values are the classification accuracy with the best classification performance.From Table10, it is clear that when some objects are added into the information systems, the average classification accuracy of the reduction found by incremental algorithm IEPAO is better than those of algorithm IEP in data sets Chess, Connect-4, Gene, Handwritten, Hepatitis, Letters and Ticdata2000 are coincide with those of algorithm IEP in data sets, e.g., Chess kr-kp, Mushroom, and Nursery. The experimental results show that the incremental algorithm IEPAO can find a feasible attribute reduction when incremental algorithm IEPAO replaces algorithm IEP. Moreover, the algorithm IEPAO can obtain high-quality attribute reduction with less time consumption. Similarly, when some objects are deleted from the original object set, the average classification accuracy of the reduction obtained by the algorithm IEPDO is better than IEP in data sets Connect-4, Gene, Handwritten, Hepatitis, Letters, and Ticdata2000.Accordingly, we can conclude that the incremental algorithm IEPDO can find a feasible attribute reduction.Hence, the experimental results verified that the proposed incremental methods IEPAO and IEPDO can obtain an efficient attribute reduction and provide a quick data preprocessing method for dynamic data sets.


## 6. Conclusions and Further Study

Attribute reduction can effectively eliminate redundant information. Though the discernibility matrix method is one of the intuitive and effective reduction methods, it cannot deal with the reduction of large-scale data sets effectively because of memory overflow. The attribute reduction mechanism based on IEP can effectively solve the problem of space consumption analyzed in this paper. During the reduction process, IEP effectively prunes the subdivisions with cardinality 1, which speeds up the calculation of equivalence class division. IEP has better time and space effects in reduction, but it only adapts to the environment of static data sets. Considering the constant updating of data, in reality, IEPAO and IEPDO are proposed on the basis of IEP to deal with the reduction of adding data objects and deleting data objects respectively. As to IEP, the entire data set has to be reduced again and consumed a lot of time with the data changes. IEPAO and IEPDO only compute the changed part data and combine the previous reduction results, which can obtain the data set with fewer redundancies and better outcomes.Of course, the algorithm proposed has some shortcomings in this paper. For example, (1) The IEP method can only reduce integer or character data, but cannot adapt to process other types of data. (2) The incremental update algorithm proposed in this paper does not consider the changes in attributes and values.In the future, we will conduct the research from the following aspects: design an increment algorithm adapting to different types of data; develop a reduction method regarding the change values of data objects; propose an incremental mechanism with adding and deleting some attributes. Additionally, those approaches should adapt to an incomplete decision system.



---

*Source: 6876144-2022-09-29.xml*