# Indiscernibility and Discernibility Relations Attribute Reduction with Variable Precision

Authors: Xu Li; Jianguo Tang; Bing Hu; Yi Li
Journal: Scientific Programming
 (2022)

---

## Abstract

Attribute reduction is a popular topic in research on rough sets. In the classical model, much progress has been made in the study of the attribute reduction of indiscernibility and discernibility relations. To enhance the fault tolerance of the model, concepts of both indiscernibility and discernibility relations involving uncertain or imprecise information are proposed in this paper. The attribute reductions of the relativeβ-indiscernibility relation and relative β-discernibility relation and their algorithms are proposed. When the precision satisfies certain conditions, the reduction of two relation concepts can be converted into a positive region reduction. Therefore, the discernibility matrix is used to construct the reductions of the two relation concepts and the positive region. Furthermore, the corresponding algorithm of the relative β-indiscernibility (discernibility) relation reduction can be optimized when the precision is greater than 0.5, and this is used to develop an optimization algorithm that constructs the discernibility matrix more efficiently. Experiments show the feasibility of the two relation reduction algorithms. More importantly, the reduction algorithms of the two relations and the optimization algorithm are compared to demonstrate the feasibility of the optimization algorithm proposed in this paper.


---

## Body

## 1. Introduction

The rough set (RS) theory [1, 2], proposed by Polish mathematician Zdzislaw Pawlak, is a useful data processing method for dealing with incomplete and inconsistent problems. The investigation of indiscernibility and discernibility relations between objects is an important task in RS theory. In classical RS theory, an indiscernibility relation between objects exists when all of the objects have the same attribute values. A discernibility relation exists between the objects if and only if not every attribute value of the objects is the same. Existing research has studied in-depth indiscernibility and discernibility relations in RSs [3–5] in certain research fields. For instance, in political sociology, if one side emphasizes the difference between countries, this can cause conflict to expand; on the contrary, if one side emphasizes the commonality between countries, this can provide better conditions for negotiation [6]. Because classical RS theory is sensitive to classification error, its application is quite limited, and its classification ability is poor. To overcome this limitation, the variable precision (VP) model [7, 8] is constructed using precision, which processes the data more effectively, thus advancing the development of RS theory and broadening its application to other fields.Even more in-depth research has been performed on attribute reduction, which forms the minimum subset of knowledge classification by deleting redundant or unrelated attributes according to specific rules. Attribute reduction has been studied in reference [9–14] and has been applied to fault diagnosis, risk assessment, and other fields [15]. In reference [16], a VP model that is more fault-tolerant than the RS model was proposed, and seven forms of reduction in the VP model were discussed. In reference [17–19], the concept of attribute reduction in the VP model was proposed, and through a strict proof of the corresponding discernibility matrix, a reduction algorithm based on that matrix was given. Beynon [20] studied the VP reduction by comparing different thresholds. The influence of parameters on classification was studied in the VP model [21]. Chen et al. [22] defined a fuzzy relation on condition attributes, and then, a local attribute reduction algorithm was proposed using the corresponding discernibility matrix. In addition, fuzzy relations [23–25] have been studied in [26–28]. The aim of most research on attribute reduction is to solve practical problems in different scenarios and has led to various forms of attribute reduction, such as covering reduction [29, 30], cost-sensitive reduction [31–33], local attribute reduction [22, 34, 35], incremental attribute reduction [36–38], and information entropy reduction [39, 40].Skowron et al. [41, 42] were the first to propose using the discernibility matrix to reduce attributes in information systems. This method can determine all the reductions by transforming the function in conjunctive normal form (CNF) into a function in disjunctive normal form (DNF). This method is called the discernibility matrix-based reduction method and is supported by mathematical proofs. Although its calculation complexity is high, it remains the main method to obtain all reductions.In this paper, the relativeβ-indiscernibility relation (β –IR) and relative β-discernibility relation (β −DR) of the VP model are proposed, in which VP model, probabilistic model [43], and decision-theoretic model [44] all extend RS. However, the differences among them lie in the selection of parameters. Because all the results can be obtained using the discernibility matrix, this paper is based on the discernibility matrix. Moreover, the relationships among relative β–IR reduction, relative β-DR reduction, and positive region reduction when the precision is greater than 0.5 are investigated after modifying the decision values of some objects.The structure of this paper is divided into six parts. In Section2, there are reviews of upper approximation, lower approximation, and β-approximation. In Section 3, the definition and reduction of the relative β–IR are proposed, and then, an algorithm for relative β–IR reduction is given. In Section 4, the definition and reduction of the relative β-DR are proposed, and then, an algorithm for relative β-DR relation reduction is also given. In Section 5, it is shown that when the precision is greater than 0.5, the relative β–IR (relative β-DR) reduction in a decision table is equivalent to the positive region reduction in a new decision table in which some objects’ decision values have been updated. Then, an optimization algorithm for converting the relative β–IR (relative β-DR) reduction to a positive region reduction is proposed. In Section 6, we used a naive Bayes (NB) classifier, support vector machine (SVM), and decision tree (DT) on UCI datasets to compare the accuracy after reduction and evaluate the effectiveness of the proposed algorithms. Section 7 concludes the paper.


## 2. Preliminary

An information table [1, 2, 5] is also called an information system. It is assumed that the knowledge in an information table is described and represented by a set of rows and a set of columns, in which rows and columns denote objects and attributes, respectively. The information table is a tuple S=U,At,Va|a∈At, Ia|a∈At, where U is a universal set, At is a attribute set, Va is nonempty set of values for an attribute a, and Ia:U⟶Va is a function such that each x∈U takes a value Iax on attribute a. Given A⊆At, the equivalence relation is defined by RA=x,y|x,y∈U×U,Iax=Iay for each a∈A. Moreover, an equivalence class for x on a set of attribute A is denoted as xA=y|x,y∈RA. It can be easily seen that this equivalence relation is reflexive, symmetric, and transitive. For A⊆At, the quotient set is denoted by U/A=A1,A2,…,Al, where xA∈U/A.InS=U,At, if C is a set of condition attributes and D is a set of decision attributes, where At=C∪D and C∩D=∅, then an information table is called a decision table. In this paper, a decision table S is written as U,C∪D, where C=a1,a2,…,am, D=d1,d2,…,dt, and Rd=∩i=1tRdi. For the convenience of proof, a set of decision attributes is written as a singleton set, namely D=d.Definition 1.
(see [1, 2]). Let U,C be an information system and X be a subset of U, B⊆C. The lower and upper approximations of X are as follows:(1)R¯X=x|xR⊆X,R¯X=x|xR∩X≠∅.Definition 2.
(see [1, 2]). Let U,C∪D be a decision table in which U/D is a quotient set induced by D. The positive region is defined as follows:(2)PosCD=∪i=1lRC¯Di,where Di∈U/D.
That is, for eachxC, if xC⊆PosCD, then xC is contained in xD. Conversely, if xC is contained in xD, then xC⊆PosCD.Definition 3.
(see [19]). Let U,C∪D be a decision table, where B⊆C. If it satisfies the following conditions,(3)PosCD=PosBD,for anyB'⊂B,PosBD≠PosB'D.then B is called the positive region reduction of C.
Given a decision table, its corresponding discernibility matrix [11] of positive region reduction MP=mpijs×n is as follows:(4)mpij=a|a∈C,xi,xj∉Ra,xi∈PosCD,xi,xj∉RD,∅,otherwise..
In a matrixF, s is equal to PosCD, n is the cardinality of U, and PosCD is the cardinality of the positive region.Definition 4.
(see [34]). Given X⊆U, for each x∈U, the characteristic function λXx is defined as follows:(5)λXx=1,x∈X,0,x∉X..Lemma 1 (see [7, 34]).
For positive integersi∈1,2,…,n, where xiR is an equivalence class on relation R and X⊆U, WRλX is expressed as follows:(6)WRλX=x1R∩Xx1R,x2R∩Xx2R,…,xnR∩XxnRT,where T denotes the transpose.
Forxi∈U, xiR∩X/xiR=λRxi,x1/xiRλXx1+λRxi,x2/xiRλXx2+…+λRxi,xn/xiRλXxn, where λRxi,xj=1 if and only if xi,xj∈R.Definition 5 (see [7, 34]).
LetR be an equivalence relation on U, β∈0,1. Then, the β -approximation of X is defined as(7)RβX=x|PX|xR≥β,where PX|xR=xR∩X/xR.Theorem 1 (see [3, 4]).
LetR be an equivalence relation on U. Then, for any subset X⊆U, then λRβX=WRλXβ, where Xβ denotes the β-cut set of fuzzy set X.Lemma 2 (see [3, 4]).
For a decision table, suppose thatμCD=WRCλD1,WRCλD2,…,WRCλDl, where Di is a decision class of objects with a decision value that is equal to fdi. Then, bijn×l is a fuzzy matrix denoted as(8)μCDx1μCDx2⋮μCDxn=x1C∩D1x1Cx1C∩D2x1C⋯x1C∩Dlx1Cx2C∩D1x2Cx2C∩D2x2C⋯x2C∩Dlx2C⋮⋮⋱⋮xnC∩D1xnCxnC∩D2xnC⋯xnC∩DlxnC,where bij=xiC∩Dj/xiC=PDj|xiC, i is a positive integer, and j is a positive integer.Theorem 2 (see [7, 34]).
GivenU,C∪D, ∀x∈U, for β∈0,1,(9)μCDβ=λRCβD1x,λRCβD2x,…,λRCβDlx.The proof of Theorem2 is shown in reference [34]. In this section, μCDβ was introduced using the β-cut set of fuzzy set X. In Section 3, the relative β-indiscernibility relation is proposed for decision tables, and then, the corresponding discernibility matrix is proposed.


## 3. Relativeβ-Indiscernibility Relation Reduction

GivenU,C∪D, with the quotient set U/D=D1,D2,…,Dl induced by the equivalence relation RD, we first define the relative β−indiscernibility relation for β∈0,1.Definition 6.
Given a setB, the relative β-indiscernibility relation is defined as follows:(10)IndBβD=x,y|x,y∈U,μBDxβ=μBDyβ,where μBDxβ=xB∩D1/xB,xB∩D2/xB,…,xB∩Dl/xBβ and β∈0,1.
For a binary relationIndBβD on U, because ∀x,x∈IndBβD, it is reflexive. If ∀x,y∈IndBβD, then y,x∈IndBβD, and it is symmetric. ∀x,y,z∈U, ∀x,y∈IndBβD and y,z∈IndBβD, then x,z∈IndBβD, and hence, it is transitive. Because relation IndBβD satisfies the above three properties, it is an equivalence relation.
In the decision table presented in Table1, the condition set C contains a1,a2,a3, and D is a decision attribute set. Here, U/C=x1,x2,x3,x4,x5,x6,x7 and U/D=D1,D2,D3, where D1=x1,x3, D2=x2x4,x5,x6, and D3=x7. For different values of the threshold β, IndBβD may be different.
Ifβ=0.3, then by Theorem 2, we have μCDx10.3=μCDx20.3=1,1,0, μCDx30.3=μCDx40.3=μCDx50.3=1,1,0, μCDx60.3=0,1,0, and μCDx70.3=0,0,1.
Ifβ=0.6, then by Theorem 2, we have μCDx10.6=μCDx20.6=0,0,0, μCDx30.6=μCDx40.6=μCDx50.6=0,1,0, μCDx60.6=0,1,0, and μCDx70.6=0,0,1.
According to Definition6, we have, for example, x1,x3∈IndC0.3D and x3,x6∉IndC0.3D; however, x1,x3∉IndC0.6D, x3,x6∈IndC0.6D.Table 1
Decision table.
UCDa1a2a3x11110x21110x30100x40101x50101x61001x70112Definition 7.
GivenU,C∪D, if B⊆C satisfies the following two conditions:(a)
IndCβD=IndBβD(b)
foranyB′⊂B,IndB′βD≠IndCβDthen B is the reduction of the relative β–IR.
Given a decision table, a corresponding discernibility matrixMβ=mijβn×n for the relative β–IR is as follows:(11)mijβ=a|a∈C,xi,xj∉Ra,xi∈PosCD,ifxi,xj∉IndCβD∅,otherwise,where n is U.Lemma 3.
LetU,C∪D be a decision table and ∀x,y∈U×U. If x,y∉IndCβD, then mijβ≠∅.Proof.
Ifx,y∉IndCβD, then ∃Dk∈U/D s.t. xiC∩Dk/xiCβ≠xjC∩Dk/xjCβ. Thus, xi,xj∉RC. Hence, there exists as∈C such that xi,xj∉Rs. Then, mijβ≠∅.Theorem 3.
LetU,C∪D be a decision table. For B⊆C, the following three conditions are equivalent:(a)
IndCβD=IndBβD(b)
ifmijβ≠∅, mijβ∩B≠∅(c)
ifx,y∈RB, then x,y∈IndCβDProof.
a⇒b Let mijβ≠∅. Then, there exists xi,xj∉IndCβD. Using proof by contradiction, suppose mijβ∩B=∅. Then, xi,xj∈RB. Thus, by Definition 6, xi,xj∈IndBβD, which leads to a contradiction.
b⇒c Using proof by contradiction, assume xi,xj∉IndCβD. By Lemma 3, mijβ≠∅. From condition (b), mijβ∩B≠∅, and hence, aS∈mijβ∩B, namely, xi,xj∉RB, which is a contradiction.
c⇒a In this case, xi,xj∈IndCβD holds if and only if μCDxiβ=μCDxjβ, namely, for each Dk∈U/D, xiC∩Dk/xiCβ≠xjC∩Dk/xjCβ, B⊆C, ∀x∈U. Then, xB=∪s=1lysC, which is the partition of xB with respect to RC. We have two cases:(i)
IfysC∩Dk/ysC≥β, then xB∩Dk/xB=∑s=1lysC∩Dk/ysCysC/xB≥β∑s=1lysC/xB=β(ii)
IfysC∩Dk/ysC<β, then xB∩Dk/xB=∑s=1lysC∩Dk/ysCysC/xB≥β∑s=1lysC/xB=β
ByI and II, μCDxiβ=μBDxiβ and μCDxjβ=μBDxjβ if and only if xi,xj∈IndBβD. Thus, Theorem 3 is proved.Corollary 1.
LetU,C∪D be a decision table. If ∅≠B⊆C and precision β∈0,1], then B is the reduction of the relative β–IR if and only if it is a minimal subset, which satisfies mijβ∩B≠∅ for any mijβ≠∅.Using Corollary1, we present the following algorithm for the relative β-lR reduction for U,C∪D.Algorithm 1: The algorithm of the relative β-lR reduction.
Input:U,C∪DOutput: reduction results of C(1)
mijβ=∅, Bi=∅;(2)
for each x in Udo(3)
computeμCDxβ;(4)
endforor in Udofxor in Udo fx(7)
ifxi,xj∉IndCβD thenmijβ=mijβ∪ai,ai∈C.(8)
endif(9)
endfor(10)
endfor(11)
execute CNF to DNF function(12)
return allBi.// Bii=1,2,…,k is one of the attribute reductions.Considering the decision table given in Table1, when β=0.6, the discernibility matrix is constructed as follows:(12)∅∅a1,a3a1,a3a1,a3a2,a3a1∅∅a1,a3a1,a3a1,a3a2,a3a1a1,a3a1,a3∅∅∅∅a3a1,a3a1,a3∅∅∅∅a3a1,a3a1,a3∅∅∅∅a3a2,a3a2,a3∅∅∅∅Ca1a1a3a3a3C∅.The discernibility function in CNF isf=a1+a3a2+a3a1a3. From CNF to DNF, we have f=a1a3. Thus, the subset a1a3 is the unique attribute reduction of the relative β–IR.


## 4. Relativeβ-Discernibility Relation Reduction

The relativeβ-indiscernibility relation was proposed in Section 3, and the concept of its complementary relation is proposed in this section. In contrast to the discernibility matrix of the relative β–IR(β-DR) reduction, in U,C∪D, when the precision is greater than 0.5, the decision values of some objects can be modified, and then, the relative β-discernibility relation is calculated using a positive region reduction.Definition 8.
LetU,C∪D be a decision table and B be a subset of C. The relative β-discernibility relation is defined as follows:(13)DisBβD=x,y|x,y∈U,μBDxβ≠μBDyβ,where μBDxβ=xB∩D1/xB,xB∩D2/xB,…,xB∩Dl/xBβ.
ForU,C∪D, β∈0,1, relation IndCβD and relation DisCβD are complementary to each other. For a binary relation DisCβD, if x,y∈DisCβD, then y,x∈DisCβD, and hence, it is symmetric. It is not reflexive because μCDxβ=μCDxβ for all x∈U. Moreover, it is not necessarily transitive.
For differentβ, the set of DisCβD may also be different. In Table 1, for example, let β  = 0.3. Then, x2,x5∉DisC0.3D, and x5,x6∈DisC0.3D. However, let β=0.6. We then have x2,x5∈DisC0.6D, and x5,x6∉DisC0.6D.Definition 9.
LetU,C∪D be a decision table, B⊆C. If B satisfies the following conditions:(a)
DisCβD=DisBβD(b)
for anyB'⊂B, DisB'βD≠DisCβDthen B is the reduction of the relative β-DR.
Given a decision table, its corresponding discernibility matrix isM′=m'n×n for the relative β-DR, where n is the cardinality of U. Each element m' is defined as follows:(14)m'ijβ=a|a∈C,xi,xj∉Ra,ifxi,xj∈DisCβD,∅,otherwise.Lemma 4.
LetU,C∪D be a decision table. ∀xi,xj∈U×U, if xi,xj∈DisCβD, then m'ijβ≠∅.Proof.
The proof is similar to that of Lemma3 in Section 3.Theorem 4.
LetU,C∪D be a decision table. If B⊆C, then the following conditions (a), (b), and (c) are equivalent:(a)
DisCβD=DisBβD(b)
Ifmij′β≠∅, mij′β∩B≠∅(c)
Ifx,y∈RB, then x,y∉DisCβDProof.
The proof is similar to that of Theorem3 in Section 3.Lemma 5.
LetU,C∪D be a decision table. If xi,xj∈U×U, then mijβ=m'ijβ.Proof.
For allxi,xj∈U×U, then xi,xj∈DisCβD if and only if xi,xj∉IndCβD, and hence, mijβ=m'ijβ.
Becausexi,xj∈DisCβD is the complement of a set IndCβD, it is known from equations (12) and (14) that their discernibility matrices are the same.Corollary 2.
LetU,C∪D be a decision table. If and precision β∈0,1, then B is the reduction of the relative β-DR if and only if it is a minimal subset, which satisfies mij′β∩B≠∅ for any mij′β≠∅.Using Corollary2, the algorithm of the relative β-DR reduction for U,C∪D is proposed as follows.Algorithm 2: The algorithm of the relative β-DR reduction.
Input:U,C∪DOutput: reduction results of C(1)
mijβ=∅, Bi=∅;(2)
forx in Udo(3)
computeμCDxβ;(4)
endforforin Udoxforin Udo x(5)
ifxi,xj∈DisCβDthenmij′β=mij′β∪ai,ai∈C.(6)
endif(7)
endfor(8)
endfor(9)
execute CNF to DNF function(10)
return allBi.// Bii=1,2,…,k is one of the attribute reductionsConsidering the decision table given in Table1, letting β  = 0.3, the discernibility matrix is constructed as follows:(15)∅∅∅∅∅a2,a3a1∅∅∅∅∅a2,a3a1∅∅∅∅∅a1,a2a3∅∅∅∅∅a1,a2a3∅∅∅∅∅a1,a2a3a2,a3a2,a3a1,a2a1,a2a1,a2∅Ca1a1a3a3a3C∅.The discernibility function in CNF isf=a1+a3a2+a3a1a3. From CNF to DNF, it is f=a1a3. Thus, according to Definition 9, a1a3 is the unique result in the decision table.


## 5. Optimization of the Reduction Algorithm

LetU,C∪D be a decision table with Dk∈U/D. For all x∈Dk and value dk∈Vd, let Idx=dk, which means that the object x takes the value dk in Vd. Obviously, every x in Dk has the same decision value dk for the decision attribute. Given precision β∈0.5,1, for any xC satisfying β≤xC∩Dk/xC <1, suppose xi∈xC and Idxi≠dk. Then, change the values that objects xi have for decision attribute d such that Idxi=dk, that is, xC⊆Dk′. This constructs a new quotient set U/D′, denoted by U/D′=D1′,D2′,…,Dl′. The decision table that changes the decision values of some objects using this method is called the new decision table and is denoted by U,C∪D′. Indeed, we note that Di′ may be the empty set for ∃Di′∈U/D′.Theorem 5.
LetU,C∪D be a decision table with quotient set U/D. Given precision β∈0.5,1, an updated new decision table U,C∪D′ is constructed with a new quotient set U/D′=D1′,D2′,…,Dl′. Then, μCDxβ=μCD'x1.Proof.
∀Dk∈U/D and for any xC satisfying xC∩Dk/xC≥β>0.5, by Lemma 2, we have xC∩Di/xC<0.5i≠k. Thus, xC∩Dk/xC=1 for the corresponding Dk'∈U/D', and then, by Theorem 2, μCDxβ=μCD′x1. If xC∩Dk/xC<β, then xC∩Dk'/xC<β for the corresponding Dk′∈U/D′. Then, μCDxβ=μCD′x1.Proposition 1.
Given a new decision tableU,C∪D′, where U/D′ is a new quotient set by D′ and B⊆C, B is the positive region reduction of C if and only if B is the reduction of the relative β–IR (β-DR) for β  = 1.Proof.
(⇒) If B is the attribute reduction of C, and PosCD′=PosBD′, then xC⊆Dk′ if and only if xB⊆Dk′ for ∀Dk′∈U/D', that is, xC∩Dk′/xC=xB∩Dk′/xB. Thus, μCD'x1=μBD'x1, and hence, IndC1D′=IndB1D′. Suppose B′⊂B, PosCD′≠PosB′D′. Then, there exists Dk′∈U/D′, s.t. xC⊆Dk′ and xB'⊈Dk'. Therefore,IndC1D′≠IndB′1D′.
(⇐) If IndC1D′=IndB1D′, for ∀Dk′∈U/D′ and xC⊆Dk′, if and only if xB⊆Dk′, then PosCD′=PosBD′. Suppose B′⊂B. Then, IndC1D′≠IndB'1D′, and there exists x∈PosCD′ and x∉PosB′D′. Hence, PosCD′≠PosB′D′.
From discernibility matricesMβ (equations (13) and (15)), the corresponding matrices of the two above concepts are equivalent. For U,C∪D′, B is the reduction of the relative β–IR for β=1 if and only if B is the reduction of the relative β-DR for β=1.Corollary 3.
Given a decision tableU,C∪D with precision β∈0.5,1, a new decision table U,C∪D′ is constructed. Then, B is the reduction of the relative β–IR(β-DR) with respect to U,C∪D if and only if B is the positive region for U,C∪D′.Proof.
By Theorem5 and Proposition 1, Corollary 3 clearly holds.
The above shows that the relativeβ–IR (β-DR) reduction with a precision greater than 0.5 is equivalent to positive region reduction, after modifying the decision values of some objects that satisfy the condition. When the precision of β–IR (β-DR) reduction is greater than 0.5, the decision values of some objects can be modified, and a new decision table can be constructed. In the new decision table, many heuristic algorithms can be used to calculate the positive region (Definition 3) reduction.
According to Corollary3, an optimization algorithm that converts the relative β–IR (β-DR) reduction to a positive region reduction (CRRPRR) is as follows.
When comparing the relativeβ–IR (β-DR) reduction algorithm with the Algorithm 3, the time complexity of both algorithms is OC+D×U, where C represents the number of condition attributes and D represents the number of decision attributes. For Algorithm 1 and 2, the time complexity of constructing the discernibility matrix is OU2×C and the space complexity of constructing discernibility matrix is OU2×U/D where U/D is the number of equivalent classifications induced by decision set D. For the Algorithm 3, the time complexity of calculating the positive region in the new decision table is OU×U/D×xC×Dj+xC, where U/D is the number of equivalent classifications induced by decision set D and Dj is the basis of the equivalent class Dj. Moreover, the time complexity of constructing the discernibility matrix is OPosCD′×U×C, and the space complexity of constructing discernibility matrix is OU2. The time and space complexities of the discernibility function transformation of both algorithms are the same. Obviously, the CRRPRR algorithm is better than the original algorithm.
In Table1, x1C=x1,x2, x3C=x3,x4,x5. Given precision β=0.6, x3C∩D2/x3C≥β, with D2=x2x4,x5,x6. Thus, Idx3=1 in a new decision table. For x1C∩D1/x1C<β, with D1=x1,x3, the decision values of any objects in x1C are not changed. Hence, the new decision table U,C∪D′ is shown in Table 2.
According to the CRRPRR optimization algorithm,PosCD'=x3,x4,x5,x6,x7 by Definition 2. Then, the discernibility matrix is constructed as follows:(16)a1,a3a1,a3∅∅∅a1,a2a3a1,a3a1,a3∅∅∅a1,a2a3a1,a3a1,a3∅∅∅a1,a2a3a2,a3a2,a3a1,a2a1,a2a1,a2∅Ca1a1a3a3a3C∅.
The discernibility function in CNF isf=a1+a3a1+a2a2+a3a1a3. From CNF into DNF, we have f=a1a3. Thus, a1,a3 is the unique attribute reduction of C in U,C∪D′.
It must be explained that the basic condition for the conversion of the relativeβ –IR (β −DR) reduction into positive region reduction is that the precision must be greater than 0.5. When the precision is greater than 0.5, this not only improves the fault tolerance of the model but also ensures its credibility l. If β  = 0.5 is given (e.g., as in Table 1), for x1C=x1,x2, because Idx1=0, Idx2=1, the decision values of any objects in x1,x2 cannot be modified according to the conversion method in this paper. Another case occurs when β  = 0.8. In this case, none of the decision values of any objects can be modified in Table 1, and the above conversion method is not feasible.Algorithm 3: An optimization algorithm CRRPRR.
Input: decision table U,C∪D, given β∈0.5,1Output: reduction results of C(1)
mpij=∅, Bi=∅;(2)
forx in Udo(3)
ifβ≤xC∩Dk/xC<1then(4)
IDx is modified;(5)
endif(6)
endfornew decision table (U,C∪D′) is constructed  //afor in doxPosCDfor in U do x(7)
ifxi∈PosCD,xi,xj∉RDthenmpij=mpij∪ai,ai∈C.(8)
endif(9)
endfor(10)
endfor(11)
execute CNF to DNF function(12)
return allBi.// Bii=1,2,…,k is one of the attribute reductionsTable 2
New decision table.
UCD′a1a2a3x11110x21111x30101x40101x50101x61001x70112


## 6. Experimental Analysis

In this section, we evaluate the performances of the proposed algorithms through some comparison experiments. In our experiments, twenty datasets from the UCI were used. All the information is shown in Table3, in which U is the cardinality of U, and C and U/D are the numbers of condition attributes and decision classes, respectively. Using tenfold cross-validation, three classifiers (kernel NB, fine Gaussian SVM, and a DT) were used to test the classification accuracies of the results after reduction. Kernel NB is a classifier that uses estimated kernel densities. The classification accuracy of fine Gaussian SVM is higher than that of SVM after the Gaussian kernel is introduced. DT is a supervised learning model that learns decision rules. The algorithms were implemented on a MacBook Pro (early 2015) with an Intel(R) Core(TM) i5 CPU at 2.7 GHz and Intel Iris Graphics 6100 GPU. The algorithms in this paper were coded in Python 3.6.8 using scikit-learn 0.20.3.Table 3
Brief description of the data sets.
IDDatasetsAbbreviationUCU/D1IrisIris150432Statlog (Heart)Sta.2701323WineWine1781334SPECT heartS.H.1672225ZooZoo1011676FlagsFlags1942877Acute inflammationsA.I.120648Computer hardwareC.H.209999LensesLen.244310SoybeanSoy.4734411E.coliE.coli3367812Haberman's survivalH.S.3063213Balance scaleB.S.6254314ServoSer.1674815Teaching assistant evaluationT.A.E.1515316CryotherapyCr.906217IonosphereIo.35134218Tic-Tac-ToeT.T.T.9589219Thoracic surgeryT.S.47016220Hayes-RothH.R.16043Because of the requirements of Algorithm 3, the accuracy of the tables in this experiment must be greater than 0.5. The runtime results for different precisions (0.7, 0.8, and 0.9) are shown in Figure1. In this figure, the yellow line represents the average time for Algorithm 3 to run for each precision. The experimental results show that Algorithm 1, Algorithm 2, and Algorithm 3 obtain the same results, but the runtime of the latter is less than that of the former. Although the cost of converting CNF to DNF is high, the advantage of the Algorithm 3 is obvious when the number of objects is large and the number of attributes is relatively small.Figure 1
Comparison of runtime (in seconds).Because the proposed algorithms can obtain all the results, the mean classification accuracy is reported. For all precision values, the classification accuracies obtained by kernel NB, fine Gaussian SVM, and DT are shown in Figures2–4, respectively.Figure 2
Classification accuracy results of kernel NB.Figure 3
Classification accuracy results of fine Gaussian SVM.Figure 4
Classification accuracy results of DT.In Figure2, in most cases, the classification accuracy of the kernel NB classifier is low for the reduction results obtained from a low precision value. For example, for the HS dataset, given precision values of 0.7, 0.8, and 0.9, the accuracy results are 81.25%, 85.66%, and 92.11%, respectively.For all data sets except for Wine, SH, and TAE, a higher precision value leads to a higher classification accuracy for the fine Gaussian SVM classifier in Figure3. However, the classification accuracy is relatively low. In most cases, when the precision is high, the reduction results lead to higher classification accuracies for the DT classifier, but the classification accuracy is low. For example, on the HR dataset, given precision values of 0.7, 0.8, and 0.9, the accuracy results are 62.33%, 70.15%, and 76.01%, respectively.This experiment demonstrates the feasibility of the concept proposed in this paper. When the precision is less than 0.5, its reliability is not high. Moreover, the CRRPRR optimization algorithm and the relativeβ–IR (β-DR) reduction algorithm could not be linked. Therefore, the precision of the algorithms must be greater than 0.5. Figures 2–4 show that when the precision is larger, the classification accuracy is higher when the results are obtained by the proposed algorithms. On the contrary, it is lower when the precision is lower.


## 7. Conclusions

This study extends the work of [5, 22, 34, 41] to investigate the relative β–IR (β-DR) for the first time using a discernibility matrix-based method. Under certain conditions, precision β>0.5, and the relationship between the relative β –IR (β −DR) reduction and positive region reduction was found by modifying some decision values, which is of a certain significance to the study of VP RSs. The corresponding optimization algorithm was then proposed. The discernibility matrix corresponding to the relative β –IR (β −DR) reduction has a high time complexity of OU2×C, whereas the time complexity for constructing a positive region reduction is much less. Therefore, when the precision β>0.5, although the reduction results are the same, the optimization CRRPRR algorithm reduces the computational complexity. In addition, because the attribute importance cannot be calculated in the relative β –IR (β −DR) reduction to obtain the results, we modified some of the decision values that satisfy the condition so that the attribute importance can also be calculated in the new decision table. The feasibility of the algorithm proposed in this paper was demonstrated by experimental analysis. In future, we will attempt to remove the restriction of equivalence relation and further study problems such as precision reduction and the relative β –IR(β −DR) reduction.



---

*Source: 5077968-2022-04-25.xml*