# The Relationship between the Unicost Set Covering Problem and the Attribute Reduction Problem in Rough Set Theory

Authors: Qingyuan Xu; Jinjin Li
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

The unicost set covering problem and the attribute reduction problem are NP-complete problems. In this paper, the relationship between these two problems are discussed. Based on the transformability between attribute reductions and minimal solutions in unicost set covering models, two methods are provided. One is to induce an information table from a given unicost set covering model. With no doubt, it shows that the unicost set covering problem can be investigated by rough set theory. The other is to induce a unicost set covering model from a given information table. Similarly, it shows that the attribute reduction problem can be studied by set covering theory. As an application of the proposed theoretical results, a rough set heuristic algorithm is presented for the unicost set covering problem.


---

## Body

## 1. Introduction

The set covering problem (SCP) is a classical problem in operational research for combination optimization. It is popularly applied in aviation personnel scheduling, circuit design, transport vehicle route arrangement, service location, job assignment in manufacturing, selection of operators, etc. [1–3]. The SCP can be described as follows: selecting several columns from a m−row n−column 0−1 matrix M=mijm×n such that these columns can cover all rows with the least cost. The set of selected columns is called a solution of the SCP [4]. Here, (1) choosing each row must pay a certain cost. (2) mij is the i row and the j column element of M. mij=1 means that the column j covers the row i. When all rows have identical cost, for convenience, consider them as 1, the SCP is called the unicost set covering problem (USCP) [5]. This problem is also called the minimum cardinality set covering problem (MCSCP) [6] or the location set covering problem (LSCP) [7]. In this paper, we use the name of the unicost set covering problem. The SCP is a NP-complete problem [8]. Various methods have been proposed to solve it, such as branch and bound complete method [9], genetic method [10], ant colony method [11], and others [12]. Due to the increasing scale of USCP, the time complexity of these methods increases exponentially. Hence, these methods are all effective relatively and there is no efficient method absolutely to handle it, so far.Rough set theory [13] has been proved to be a useful tool in handling inexact, uncertain, and fuzzy knowledge in information tables [14]. It provides a powerful basis in discovering important data structures and classifying complex objects. Up to now, it has become a hot research area of intelligent computing. As an important concept in rough set theory, the purpose of attribute reduction is to find the minimal attribute set with the same knowledge description ability as the whole attribute set [13]. Scholars have successfully used attribute reduction in data mining [15, 16], pattern recognition [17, 18], and artificial intelligence and classification [19–21] in the past twenty years. The attribute reduction problem (ARP) attracts many researchers to study it [18, 20, 22–25]. Skowron and Rauszer proposed a beautiful method, which is effective to obtain all attribute reductions based on discernibility matrices [20]. The method constructed a discernibility function and showed that the set of all attribute reductions is the set of prime implicants of the discernibility function. However, the time complexity of this method is NP-hard [26].The cross research of set covering and rough set theory has attracted attention of some scholars. Covering-based rough sets [27] is an import interact way of set covering and rough sets. Zhu and Wang proposed three types of covering-based rough sets [28]. These models have the ability to implement other features such as multigranularity or fuzziness [29]. Based on 0-1 integer programming, Xu et al. gave an attribute reduction method to deal with the dynamic data [30]. In the variable precision rough set model, Liu et al. provided an approach to calculate the attribute reduction using set covering concepts [31]. In order to deal with the test-cost-sensitive reduction problem [32], Tan et al. presented an optimization algorithm based on set covering theory [33]. Xu et al. proposed an algorithm based on multirelation granular computing model for the USCP [34]. In this paper, we mainly build the relationship between the USCP and the ARP. Firstly, by constructing an induced information table of a given USCP, we find that computing a minimal solution or a minimum solution in a USCP can be converted to computing an attribute reduction or a minimum attribute reduction in the constructed information table. Therefore, the USCP can be converted into the APR in rough set theory. Secondly, by constructing an induced unicost set covering (USC) model according to an information table, we find that calculating an attribute reduction or a minimum attribute reduction of an information table is equal to calculating a minimal solution or a minimum solution of the constructed USCP. Therefore, the APR can also be converted into the USCP. Let the two problems to be characterized by each other, and bringing new methods mutually is the main aim of the paper. It must be noted that the ARP is a NP-complete problem [26] and the SCP is also a NP-complete problem [8], and using set covering theory to find the optimal attribute reduction with the minimum number of attribute is also NP-hard.Here, we briefly introduce the contents of the following sections. Section2 mainly introduces basic concepts of the SCP, the USCP, and the APR in rough set theory, respectively. Section 3 constructs an information table by a USC model and studies the relationship between the USCP and the ARP in the constructed information table. Section 4 constructs a USC model by an information table and considers the relationship between the ARP and the USCP in the constructed USC model. Section 5 provides a heuristic minimal solution method based on rough set theory for the USCP and followed by an example. Section 6 gives the conclusions.


## 2. Preliminaries

In this section, some basic concepts of SCP, USCP, information table, and ARP in rough sets are reviewed.


### 2.1. The SCP and the USCP

In addition to what is described in Section1, the mathematical formulation of the SCP model is usually described as follows [35]. Let E=e1,e2,…,em be a set of elements and S=s1,s2,…,sn∅≠sj⊆E,∪sj=E be a subsets collection of E and cover all elements in E, each subset sj associates a cost cj>0. The pair E,S is called a set covering model. S is also called a set covering of E. The SCP is to find a minimal cost set covering S′⊆S, where all elements in E can be covered and the cost is minimal. The USCP is to find a minimal set covering S′⊆S, where all elements in E can be covered and any nonempty subsets of S′ is no longer a set covering of E and S′ is also call a minimal solution of the USCP. Usually, there are several minimal solutions of a USCP, and the one with the minimum cardinal number is called the minimum solution.The SCP also can be described by the following0−1 integer programming [4]:(1)Minimize∑j=1ncjsj,(2)s.t.∑j=1nmijsj≥1,i=1,2,…,m,(3)sj∈0,1,j=1,2,…,n.Here,mij is the i row and the j column element of the 0−1 matrix M. mij=1 means that the j column covers the i row; sj flags whether the j column is included in the solution. That is, when sj takes 1, it means j column is included in the solution. cj represents the cost value of j column. Formula (1) denotes the minimal cost required for the solution; formula (2) implies that the solution must cover all lines. When formulas (1) and (2) are satisfied, let S′=s1,s2,…,sjt, where symbol t denotes transposition; then, S′ is a solution of the SCP. When all subsets in S have identical cost, for convenience, consider them as 1, and this problem is the USCP. That is, in a USCP 0−1 integer programming, formula (1) is replaced by the following formula:(4)Minimize∑j=1nsj.Here, formulas (2) and (4) imply that a solution of the USCP must cover all lines and the number of the elements in the solution must be least.Denote USCP byUSCP=E,S, where E=e1,e2,…,em is the object set and S=s1,s2,…,sn∅≠sj⊆E,∪sj=E is a set covering of E with the 0−1 matrix M=mijm×n.Note. The theory of soft sets introduced by Molodtsov [36] is a relatively new approach to discuss vagueness and getting popularity among the researchers. N-soft set, first introduced by Fatimah et al. [37], can provide a finer granular structure with higher distinguishable power [38]. Given a set covering model E,S with E=h1,h2,…,hm, S=e1,e2,…,en. Treat the elements set E=h1,h2,…,hm as the universe U, the set covering S=e1,e2,…,en as the subset A, and mij∗cj1≤i≤m,1≤j≤n as Fhi,ej [39]. The set covering model E,S is a special N-soft set, where ∀ej∈S,ej≠∅ and ∪S=E. Similarly, the USC model is a special soft set.Example 1.
In Ad-hoc sensor networks, the signal coverage is the main measure of network quality of service. Under the premise of ensuring the quality of signal coverage, how to save network construction cost as much as possible is particularly important. Let Ad-hoc sensor networks be as shown in Figure1. The five circular areas s1,s2,…,s5 are the signal coverage of the same type of sensors. e1,e2,…,e9 are nine customers, who want to receive the networks service. How to finding the optimum scheme for setting up sensors?
Consider nine service customers as objects. Then, the object setE=e1,e2,…,e9. Sets s1,s2,…,s5 are formed by customers in the signal covering range of each sensor, i.e., S=s1,s2,s3,s4,s5 with s1=e1,e2,e4,e9, s2=e1,e2,e6,e7,e8,e9, s3=e3,e4,e5,e8, s4=e1,e3,e5,e9, and s5=e2,e3,e6,e7,e8. Then, S is a set covering of E, where(5)M=mijm×n=mij9×5=110101100100111101000011001001010010110111010.
Because five sensors are the same type, Example1 is a USCP. A mininal solution of the USCP is an optimum sensors setting scheme for Example 1.
Example1 can be described by the following 0−1 integer programming:(6)Minimizefun=s1+s2+s3+s4+s5,s.t.=s1+s2+s4≥1s1+s2+s5≥1s3+s4+s5≥1s1+s3≥1s3+s4≥1s2+s5≥1s2+s5≥1s2+s3+s5≥1s1+s2+s4≥1s1,s2,s3,s4,s5=0or1.
Use Matlab2016a to run the following procedures:f = [1,1,1,1,1]ic = [1,2,3,4,5]A = [−1,−1,0,−1,0;−1,−1,0,0,−1;0,0,−1,−1,−1;−1,0,−1,0,0;0,0,−1,−1,0;0,−1,0,0,−1;0,−1,0,0,−1;0,−1,−1,0,−1;−1,−1,0,−1,0]b = [−1;−1;−1;−1;−1;−1;−1;−1;−1]lb = zeros (5,1)ub = ones (5,1)[X,fval, flag] = intlinprog (f,ic,A,b,[],[],lb,ub)
We can obtain an optimum solutionX=0,1,1,0,0t. That is, s2,s3 is the optimum scheme for setting up sensors in Example 1.
In this paper, we describe Example1 as a USCP=E,S, where E=e1,e2,…,e9 is the object set and S=s1,s2,s3,s4,s5∅≠sj⊆E,∪sj=E,1≤j≤5 is a set covering of E with the 0−1 matrix:(7)M=mijm×n=mij9×5=110101100100111101000011001001010010110111010.Figure 1
Sensor network.


### 2.2. ARP in Rough Set Theory

Rough set theory is one of the most successful tools for uncertainty management. In rough sets, information is presented by an information table or an information system. An information table is usually described as a pairIT=U,A with a mapping f from U×A to V=∪a∈AVa, where U, called the universe, is a finite and nonempty set of objects, A is a finite and nonempty set of attributes, and Va, called the a′ domains, is the value set of attribute a [13].For any nonempty attribute subsetB⊆A,(8)RB=xi,xj∈U×Ufxi,a=fxj,a,∀a∈B,where RB is called an indiscernibility relation on U w.r.t. B. It is easy to see that RB is an equivalence relation on the universe U with the partition U/RB=xiBxi∈U, where xiB=xj∈Uxi,xj∈RB is the equivalence class of xi w.r.t. B and ∀xi,xj∈U. If xi,xj∈RB, then we call xi and xj are indiscernible in the universe w.r.t. B.Attribute reduction is one of the core problems in rough sets. It is a key process for discovering important data structures and classifying complex objects. Based on the indiscernibility relation discussed above, Pawlak proposed the concept of attribute reduction in an information table. The attribute reduction is a minimal subset of attributes, which has the same indiscernibility relation asRA [40].Definition 1.
LetIT=U,A be an information table, B⊆A. If RB=RA, then we call B an attribute consistent set of IT. If B is an attribute consistent set, for ∀C⊂B, C is not a consistent set; then, we call B an attribute reduction of the IT.
Definition1 means that an attribute reduction is a minimal subset of attributes with RB=RA.
Normally, there is more than one attribute reduction in an information table. The one with the minimum cardinal number is called the minimum attribute reduction.REDIT denotes the set of all attribute reductions of an information table IT.
From the viewpoint of the importance of attribute, Skowron and Rauszer [20] define the notion of core.Definition 2.
(see [20]). Let IT=U,A be an information table with U=x1,…,xn. An attribute a∈B⊆A is dispensable in B if RB = RB−a, otherwise a is indispensable. The set of all indispensable attributes is called the core set of IT, denoted as COREIT.
COREIT is also the intersection of all attribute reductions of IT.
Scholars provided many methods for attribute reduction, where the method based on the discernibility matrix and discernibility function can compute all the attribute reductions of an information table using logical operations [20].Definition 3.
LetIT=U,A be an information table, U=x1,…,xn. For any xi,xj∈U,(1)
The discernibility set of object pairxi,xj in IT is denoted as dxi,xj=a∈Afxi,a≠fxj,a(2)
The discernibility matrix ofIT is denoted as D=dxi,xjn×n(3)
The family of nonempty discernibility set ofIT is denoted as D=dxi,xjxi,yj∈U×U,dxi,xj≠∅
Definition3 means that if dxi,xj≠∅, then object xi and object xj can be distinguished by any attribute in dxi,xj. Otherwise, object xi and object xj cannot be distinguished in IT. Obviously, dxi,xj=dxj,xi and dxi,xi=∅, The discernibility matrix D is a symmetric n×n matrix. It is usually to consider only the lower triangle or the upper triangle of the matrix. D is the simplified form of D.
ForB⊆A, then if B∩dxi,xj≠∅, it means that the attribute set B can discern the object pair xi,xj [18].Theorem 1.
(see [20]). Let IT=U,A be an information table, U=x1,…,xn, and D=dxi,xjn×n be the discernibility matrix of IT. For any attribute set B⊆A,(1)
B is a consistent set iff ∀xi,xj∈U×U,whendxi,xj≠∅,B∩dxi,xj≠∅(2)
B is an attribute reduction iff B is an attribute consistent set and ∀a∈B,∃xi,xj∈U×U, and dxi,xj≠∅∧B−a∩dxi,xj=∅Theorem 2.
(see [20]). Let IT=U,A be an information table, U=x1,…,xn, and D=dxi,xjn×n be the discernibility matrix of IT. COREIT=a∈Adxi,xj=afor somexi,xj∈U.Skowron and Rauszer [20] proposed a method to compute all the attribute reductions of an information table, which is based on notions of discernibility function and logical operation. A discernibility function fS for an IT is a Boolean function, which has m Boolean variables a1,a2,…,am corresponding to m attributes a1,a2,…,am, respectively.Definition 4.
LetIT=U,A be an information table, U=x1,…,xn:(9)fSa1,a2,…,am=∧∨dxi,xjdxi,xj∈D,where ∨dxi,xj is the disjunction of all attributes a∈dxi,xj and fSa1,a2,…,am is called the discernibility function of IT.Theorem 3.
(see [20]). Let IT=U,A be an information table and fSa1,a2,…,am be the discernibility function. An attribute subset B⊆A is an attribute reduction of IT iff ∧ar∈Bar is a prime implicant of fS.Theorem3 means that a prime implicant of discernibility function fSa1,a2,…,am is an attribute reduction of IT, and all the prime implicants of discernibility function fSa1,a2,…,am are all the attribute reductions of IT. So, we can use the disjunction ∨ and conjunction ∧ operations to compute all the attribute reductions of an information table.IffSa1,a2,…,am=∧∨dxi,xjdxi,xj∈D=∨r=1t∧k=1srak, where ∧k=1srak,r≤t are all the prime implicants of the discernibility function fS, then Br=akk≤sr, and r≤t is an attribute reduction of IT. Denote all the attribute reductions of IT by ℬ=Brr≤t.From the above conclusion, one can obtain all the attribute reductions of an information table by computing the discernibility function using Boolean operations.Example 2.
LetIT=U,A be an information table, as shown in Table 1, with U=x1,x2,x3,x4,x5,x6 and A=a1,a2,a3,a4,a5.
Table2 represents the discernibility matrix D of IT, where we only consider the upper triangle matrix. The discernibility function fS of IT is(10)fSa1,a2,a3,a4,a5=∧∨dxi,xjdxi,xj∈D=a1∨a3∨a5∧a1∨a2∨a3∧a1∨a2∨a3∨a5∧a1∨a3∧a2∨a5∧a1∨a2∨a3∨a4∨a5∧a2∧a2∨a4∧a5∧a4∨a5∧a4∧a2∨a4∨a5.
Using Boolean logical operations, we can obtain(11)fSa1,a2,a3,a4,a5=a1∧a2∧a4∧a5∨a2∧a3∧a4∧a5.
According to Theorem3, IT has two attribute reductions: a1,a2,a4,a5 and a2,a3,a4,a5. COREIT=a2,a4,a5.Table 1
The information systemIS of Example 2.
Ua1a2a3a4a5x121111x211212x312211x412212x512222x611211Table 2
The discernibility matrixD of IS in Example 2.
x1x2x3x4x5x6x1∅a1,a3,a5a1,a2,a3a1,a2,a3,a5a1,a2,a3,a4,a5a1,a3x2∅a2,a5a2a2,a4a5x3∅a5a4,a5a2x4∅a4a2,a5x5∅a2,a4,a5x6∅


## 2.1. The SCP and the USCP

In addition to what is described in Section1, the mathematical formulation of the SCP model is usually described as follows [35]. Let E=e1,e2,…,em be a set of elements and S=s1,s2,…,sn∅≠sj⊆E,∪sj=E be a subsets collection of E and cover all elements in E, each subset sj associates a cost cj>0. The pair E,S is called a set covering model. S is also called a set covering of E. The SCP is to find a minimal cost set covering S′⊆S, where all elements in E can be covered and the cost is minimal. The USCP is to find a minimal set covering S′⊆S, where all elements in E can be covered and any nonempty subsets of S′ is no longer a set covering of E and S′ is also call a minimal solution of the USCP. Usually, there are several minimal solutions of a USCP, and the one with the minimum cardinal number is called the minimum solution.The SCP also can be described by the following0−1 integer programming [4]:(1)Minimize∑j=1ncjsj,(2)s.t.∑j=1nmijsj≥1,i=1,2,…,m,(3)sj∈0,1,j=1,2,…,n.Here,mij is the i row and the j column element of the 0−1 matrix M. mij=1 means that the j column covers the i row; sj flags whether the j column is included in the solution. That is, when sj takes 1, it means j column is included in the solution. cj represents the cost value of j column. Formula (1) denotes the minimal cost required for the solution; formula (2) implies that the solution must cover all lines. When formulas (1) and (2) are satisfied, let S′=s1,s2,…,sjt, where symbol t denotes transposition; then, S′ is a solution of the SCP. When all subsets in S have identical cost, for convenience, consider them as 1, and this problem is the USCP. That is, in a USCP 0−1 integer programming, formula (1) is replaced by the following formula:(4)Minimize∑j=1nsj.Here, formulas (2) and (4) imply that a solution of the USCP must cover all lines and the number of the elements in the solution must be least.Denote USCP byUSCP=E,S, where E=e1,e2,…,em is the object set and S=s1,s2,…,sn∅≠sj⊆E,∪sj=E is a set covering of E with the 0−1 matrix M=mijm×n.Note. The theory of soft sets introduced by Molodtsov [36] is a relatively new approach to discuss vagueness and getting popularity among the researchers. N-soft set, first introduced by Fatimah et al. [37], can provide a finer granular structure with higher distinguishable power [38]. Given a set covering model E,S with E=h1,h2,…,hm, S=e1,e2,…,en. Treat the elements set E=h1,h2,…,hm as the universe U, the set covering S=e1,e2,…,en as the subset A, and mij∗cj1≤i≤m,1≤j≤n as Fhi,ej [39]. The set covering model E,S is a special N-soft set, where ∀ej∈S,ej≠∅ and ∪S=E. Similarly, the USC model is a special soft set.Example 1.
In Ad-hoc sensor networks, the signal coverage is the main measure of network quality of service. Under the premise of ensuring the quality of signal coverage, how to save network construction cost as much as possible is particularly important. Let Ad-hoc sensor networks be as shown in Figure1. The five circular areas s1,s2,…,s5 are the signal coverage of the same type of sensors. e1,e2,…,e9 are nine customers, who want to receive the networks service. How to finding the optimum scheme for setting up sensors?
Consider nine service customers as objects. Then, the object setE=e1,e2,…,e9. Sets s1,s2,…,s5 are formed by customers in the signal covering range of each sensor, i.e., S=s1,s2,s3,s4,s5 with s1=e1,e2,e4,e9, s2=e1,e2,e6,e7,e8,e9, s3=e3,e4,e5,e8, s4=e1,e3,e5,e9, and s5=e2,e3,e6,e7,e8. Then, S is a set covering of E, where(5)M=mijm×n=mij9×5=110101100100111101000011001001010010110111010.
Because five sensors are the same type, Example1 is a USCP. A mininal solution of the USCP is an optimum sensors setting scheme for Example 1.
Example1 can be described by the following 0−1 integer programming:(6)Minimizefun=s1+s2+s3+s4+s5,s.t.=s1+s2+s4≥1s1+s2+s5≥1s3+s4+s5≥1s1+s3≥1s3+s4≥1s2+s5≥1s2+s5≥1s2+s3+s5≥1s1+s2+s4≥1s1,s2,s3,s4,s5=0or1.
Use Matlab2016a to run the following procedures:f = [1,1,1,1,1]ic = [1,2,3,4,5]A = [−1,−1,0,−1,0;−1,−1,0,0,−1;0,0,−1,−1,−1;−1,0,−1,0,0;0,0,−1,−1,0;0,−1,0,0,−1;0,−1,0,0,−1;0,−1,−1,0,−1;−1,−1,0,−1,0]b = [−1;−1;−1;−1;−1;−1;−1;−1;−1]lb = zeros (5,1)ub = ones (5,1)[X,fval, flag] = intlinprog (f,ic,A,b,[],[],lb,ub)
We can obtain an optimum solutionX=0,1,1,0,0t. That is, s2,s3 is the optimum scheme for setting up sensors in Example 1.
In this paper, we describe Example1 as a USCP=E,S, where E=e1,e2,…,e9 is the object set and S=s1,s2,s3,s4,s5∅≠sj⊆E,∪sj=E,1≤j≤5 is a set covering of E with the 0−1 matrix:(7)M=mijm×n=mij9×5=110101100100111101000011001001010010110111010.Figure 1
Sensor network.


## 2.2. ARP in Rough Set Theory

Rough set theory is one of the most successful tools for uncertainty management. In rough sets, information is presented by an information table or an information system. An information table is usually described as a pairIT=U,A with a mapping f from U×A to V=∪a∈AVa, where U, called the universe, is a finite and nonempty set of objects, A is a finite and nonempty set of attributes, and Va, called the a′ domains, is the value set of attribute a [13].For any nonempty attribute subsetB⊆A,(8)RB=xi,xj∈U×Ufxi,a=fxj,a,∀a∈B,where RB is called an indiscernibility relation on U w.r.t. B. It is easy to see that RB is an equivalence relation on the universe U with the partition U/RB=xiBxi∈U, where xiB=xj∈Uxi,xj∈RB is the equivalence class of xi w.r.t. B and ∀xi,xj∈U. If xi,xj∈RB, then we call xi and xj are indiscernible in the universe w.r.t. B.Attribute reduction is one of the core problems in rough sets. It is a key process for discovering important data structures and classifying complex objects. Based on the indiscernibility relation discussed above, Pawlak proposed the concept of attribute reduction in an information table. The attribute reduction is a minimal subset of attributes, which has the same indiscernibility relation asRA [40].Definition 1.
LetIT=U,A be an information table, B⊆A. If RB=RA, then we call B an attribute consistent set of IT. If B is an attribute consistent set, for ∀C⊂B, C is not a consistent set; then, we call B an attribute reduction of the IT.
Definition1 means that an attribute reduction is a minimal subset of attributes with RB=RA.
Normally, there is more than one attribute reduction in an information table. The one with the minimum cardinal number is called the minimum attribute reduction.REDIT denotes the set of all attribute reductions of an information table IT.
From the viewpoint of the importance of attribute, Skowron and Rauszer [20] define the notion of core.Definition 2.
(see [20]). Let IT=U,A be an information table with U=x1,…,xn. An attribute a∈B⊆A is dispensable in B if RB = RB−a, otherwise a is indispensable. The set of all indispensable attributes is called the core set of IT, denoted as COREIT.
COREIT is also the intersection of all attribute reductions of IT.
Scholars provided many methods for attribute reduction, where the method based on the discernibility matrix and discernibility function can compute all the attribute reductions of an information table using logical operations [20].Definition 3.
LetIT=U,A be an information table, U=x1,…,xn. For any xi,xj∈U,(1)
The discernibility set of object pairxi,xj in IT is denoted as dxi,xj=a∈Afxi,a≠fxj,a(2)
The discernibility matrix ofIT is denoted as D=dxi,xjn×n(3)
The family of nonempty discernibility set ofIT is denoted as D=dxi,xjxi,yj∈U×U,dxi,xj≠∅
Definition3 means that if dxi,xj≠∅, then object xi and object xj can be distinguished by any attribute in dxi,xj. Otherwise, object xi and object xj cannot be distinguished in IT. Obviously, dxi,xj=dxj,xi and dxi,xi=∅, The discernibility matrix D is a symmetric n×n matrix. It is usually to consider only the lower triangle or the upper triangle of the matrix. D is the simplified form of D.
ForB⊆A, then if B∩dxi,xj≠∅, it means that the attribute set B can discern the object pair xi,xj [18].Theorem 1.
(see [20]). Let IT=U,A be an information table, U=x1,…,xn, and D=dxi,xjn×n be the discernibility matrix of IT. For any attribute set B⊆A,(1)
B is a consistent set iff ∀xi,xj∈U×U,whendxi,xj≠∅,B∩dxi,xj≠∅(2)
B is an attribute reduction iff B is an attribute consistent set and ∀a∈B,∃xi,xj∈U×U, and dxi,xj≠∅∧B−a∩dxi,xj=∅Theorem 2.
(see [20]). Let IT=U,A be an information table, U=x1,…,xn, and D=dxi,xjn×n be the discernibility matrix of IT. COREIT=a∈Adxi,xj=afor somexi,xj∈U.Skowron and Rauszer [20] proposed a method to compute all the attribute reductions of an information table, which is based on notions of discernibility function and logical operation. A discernibility function fS for an IT is a Boolean function, which has m Boolean variables a1,a2,…,am corresponding to m attributes a1,a2,…,am, respectively.Definition 4.
LetIT=U,A be an information table, U=x1,…,xn:(9)fSa1,a2,…,am=∧∨dxi,xjdxi,xj∈D,where ∨dxi,xj is the disjunction of all attributes a∈dxi,xj and fSa1,a2,…,am is called the discernibility function of IT.Theorem 3.
(see [20]). Let IT=U,A be an information table and fSa1,a2,…,am be the discernibility function. An attribute subset B⊆A is an attribute reduction of IT iff ∧ar∈Bar is a prime implicant of fS.Theorem3 means that a prime implicant of discernibility function fSa1,a2,…,am is an attribute reduction of IT, and all the prime implicants of discernibility function fSa1,a2,…,am are all the attribute reductions of IT. So, we can use the disjunction ∨ and conjunction ∧ operations to compute all the attribute reductions of an information table.IffSa1,a2,…,am=∧∨dxi,xjdxi,xj∈D=∨r=1t∧k=1srak, where ∧k=1srak,r≤t are all the prime implicants of the discernibility function fS, then Br=akk≤sr, and r≤t is an attribute reduction of IT. Denote all the attribute reductions of IT by ℬ=Brr≤t.From the above conclusion, one can obtain all the attribute reductions of an information table by computing the discernibility function using Boolean operations.Example 2.
LetIT=U,A be an information table, as shown in Table 1, with U=x1,x2,x3,x4,x5,x6 and A=a1,a2,a3,a4,a5.
Table2 represents the discernibility matrix D of IT, where we only consider the upper triangle matrix. The discernibility function fS of IT is(10)fSa1,a2,a3,a4,a5=∧∨dxi,xjdxi,xj∈D=a1∨a3∨a5∧a1∨a2∨a3∧a1∨a2∨a3∨a5∧a1∨a3∧a2∨a5∧a1∨a2∨a3∨a4∨a5∧a2∧a2∨a4∧a5∧a4∨a5∧a4∧a2∨a4∨a5.
Using Boolean logical operations, we can obtain(11)fSa1,a2,a3,a4,a5=a1∧a2∧a4∧a5∨a2∧a3∧a4∧a5.
According to Theorem3, IT has two attribute reductions: a1,a2,a4,a5 and a2,a3,a4,a5. COREIT=a2,a4,a5.Table 1
The information systemIS of Example 2.
Ua1a2a3a4a5x121111x211212x312211x412212x512222x611211Table 2
The discernibility matrixD of IS in Example 2.
x1x2x3x4x5x6x1∅a1,a3,a5a1,a2,a3a1,a2,a3,a5a1,a2,a3,a4,a5a1,a3x2∅a2,a5a2a2,a4a5x3∅a5a4,a5a2x4∅a4a2,a5x5∅a2,a4,a5x6∅


## 3. Inducing an Information Table from a USC Model

In this section, we induce an information table from a USC model and give an example to explain the inducing process. Then, we discuss the relationship between the USCP and the ARP in the induced information table.Definition 5.
Given aUSCP=E,S with E=e1,e2,…,em, S=s1,s2,…,sn∅≠sj⊆E,∪sj=E, and M=mijm×n, we call the pair IT=U,A be an induced information table of the USCP, where U=E∪em+1=e1,e2,…,em,em+1, A=S=s1,s2,…,sn, and the mapping f is constructed as follows:(a)
fei,aj=i×mij,1≤i≤m,1≤j≤n(b)
fem+1,aj=0,1≤j≤n
Note. The induced information table IT=U,A, constructed by a USC model as above, is a special N-soft set, where ∀ei∈U,Fei,sj=0ori1≤i≤m,1≤j≤n, and Fem+1,sj=01≤j≤n.Example 3.
The inducedIT of the USCP in Example 1 is shown in Table 3.Table 3
The inducedIS of the USCP in Example 1.
Us1s2s3s4s5e111010e222002e300333e440400e500550e606006e707007e808808e999090e1000000Theorem 4.
Given aUSCP=E,S with E=e1,e2,…,em, S=s1,s2,…,sn∅≠sj⊆E,∪sj=E, M=mijm×n. IT=U,A is the induced information table. For ∀ei,ek∈U, i≠k, dei,ek=sjmij=1ormkj=1,1≤j≤n and dei,ek≠∅.Proof of Theorem 4.
(1) We prove that, for∀ei,ek∈U,i≠k, sjmij=1ormkj=1,1≤j≤n⊆dei,ek. (a) ∀1≤j≤n, if mij=1andmkj=0, according to Definition 5, then 1≤i≤mandfei,sj=i×mij=i, 1≤k≤m+1,fek,sj=k×mij=0when1≤k≤morfek,sj=0whenk=m+1, so fei,sj≠fek,sj,sj∈dei,ek; (b) similarly, ∀1≤j≤n, if mij=0andmkj=1, then 1≤i≤m+1andfei,sj=i×mij=0when1≤i≤morfei,sj=0wheni=m+1, 1≤k≤m,fek,sj=k×mij=k, so fei,sj≠fek,sj,sj∈dei,ek; (c) ∀1≤j≤n, if mij=1andmkj=1, then 1≤i≤m,1≤k≤m,fei,sj=i, fei,sj=k because i≠k, fei,sj≠fek,sj, sj∈dei,ek. Combining (a), (b), and (c) with Definition 3, we have that, for ∀ei,ek∈U and i≠k,∀1≤j≤n, if mij=1ormkj=1 then sj∈dei,ek, sjmij=1ormkj=1,1≤j≤n⊆dei,ek.
(2) We prove that, for∀ei,ek∈U,i≠k, dei,ek⊆sjmij=1ormkj=1,1≤j≤n. ∀ei,ek∈U, i≠k,∀s∈dei,ekand∀1≤j≤n, (a) assume 1≤i≤m,1≤k≤m, fei,sj=i×mij,andfek,sj=k×mkj because fei,sj≠fek,sj,i≠k, i×mij≠k×mkj and according to Definition 5, mij=0andmkj=1,ormij=1andmkj=0, so s∈sjmij=1ormkj=1,1≤j≤n. (b) Assume 1≤i≤m,k=m+1, according to Definition 5, fei,sj=i×mij, and fek,sj=0 because fei,sj≠fek,sj, mij=1. (c) Assume i=m+1,1≤k≤m, according to Definition 5, fei,sj=0, and fek,sj=k×mkj because fei,sj≠fek,sj, mkj=1. Combining (a) and (b) with (c), we obtain that, for ∀ei,ek∈U, i≠k,∀s∈dei,ek,s∈sjmij=1ormkj=1,1≤j≤n, so dei,ek⊆sjmij=1ormkj=1,1≤j≤n.
By (1) and (2), we get that, for∀ei,ek∈U, i≠k, dei,ek=sjmij=1ormkj=1,1≤j≤n.
(3) Here, we provedei,ek≠∅. (a) Assume 1≤i≤m,k=m+1, then ∃sj∈S and mij=1, so sj∈dei,ek and dei,ek≠∅. (b) Similarly, assume 1≤k≤m,i=m+1, then ∃sj∈S and mkj=1, so sj∈dei,ek and dei,ek≠∅. (c) Assume 1≤i≤m,1≤k≤m, then ∃sj∈S and mkj=1, ∃sl∈S and mkl=1, so sj∈dei,ek,sl∈dei,ek, and dei,ek≠∅.Theorem 5.
Given aUSCP=E,S with E=e1,e2,…,em, S=s1,s2,…,sn∅≠sj⊆E,∪sj=E, M=mijm×n, the induced information table IT=U,A. For S′⊆S,S′ is a set covering of the USCP iff S′ is an attribute consist set of the induced IT.Proof of Theorem 5.
1⇒ Suppose S′⊆S is a set covering of the USCP. Then, for ∀ei,ek∈U×U,i≠k, (a) when 1≤i≤m,1≤k≤m, ∃st∈S′,sl∈S′ and mit=1,mkl=1. Because dei,ek=sjmij=1ormkj=1,1≤j≤n, so st∈dei,ekandsl∈dei,ek, thus S′∩dei,ek≠∅; (b) when i=m+1,1≤k≤m, ∃st∈S′,mkt=1, so st∈dei,ek, thus S′∩dei,ek≠∅; (c) similarly, when k=m+1,1≤i≤m, ∃st∈S′,mit=1, so st∈dei,ek, thus S′∩dei,ek≠∅. Combining (a) and (b) with (c), we have that S′∩dei,ek≠∅. By Theorem 1, one sees that S′ is an attribute consist set of the induced IT.
2⇐ Suppose S′⊆S is an attribute consist set of the induced IT. Then, for ∀ei,ek∈U×U,i≠k,dei,ek≠∅,S′∩dei,ek≠∅∀ei∈E, dei,em+1≠∅, and S′∩dei,em+1≠∅ because dei,em+1=sjmij=1,1≤j≤n, there is at least one sj∈S′andsj∈dei,em+1, thus mij=1, sj covers the element ei, and one gets that S′ is a set covering of the USCP.
Combining (1) with (2), it completes the proof.Theorem 6.
Given aUSCP=E,S with E=e1,e2,…,em, S=s1,s2,…,sn∅≠sj⊆E,∪sj=E and M=mijm×n, the induced information table IT=U,A. For S′⊆S,S′ is a minimal solution of the USCP iff S′ is an attribute reduction of the induced IT.Proof of Theorem 6.
1⇒ Suppose S′⊆S is a minimal solution of the USCP. Then, ∀sj∈S′, 1≤j≤n, S′−sj is no longer the set covering of the USCP. Thus, there is at least one ei∈E, ∀st∈S′−sj,mit=0, dei,em+1∩S′−sj=∅, by Theorem 1 (2) and Theorem 4, one sees that S′ is an attribute reduction of the induced IT.
2⇐ Suppose S′⊆S is an attribute reduction of the induced IT. Then, for ∀sj∈S′, ∃ei,ek∈U×U,i≠k,dei,ek∩S′−sj=∅. Thus, for ∀st∈S′−sj,mit=0andmkt=0, i.e., S′−sj does not cover ei and ek, S′−sj is no longer a set covering of the USCP. Hence, S′ is a minimal solution of the USCP.
Combining (1) with (2), it completes the proof.Theorem 7.
Given aUSCP=E,S with E=e1,e2,…,em, S=s1,s2,…,sn∅≠sj⊆E,∪sj=E, and M=mijm×n, the induced information table IT=U,A. For S′⊆S,S′ is a minimum solution of the USCP iff S′ is a minimum attribute reduction of the induced IT.Proof of Theorem 7.
It can be directly concluded by Theorem6.Theorem 8.
Given aUSCP=E,S with E=e1,e2,…,em, S=s1,s2,…,sn∅≠sj⊆E,∪sj=E, and M=mijm×n, the induced information table IT=U,A. For sj∈S, sj is a core of the induced IT iff ∃ei∈E,mij=1 and ∀st∈S,st≠sj,mit=0.Proof of Theorem 8.
1⇒ Suppose sj∈S is a core of the induced IT. By Theorem 2, ∃ei,ek∈U,i≠k,dei,ek=sj. Thus, by Theorem 4, (a) when 1≤i≤m,1≤k≤m, mij=1,mkj=1, ∀1≤t≤n,t≠j, and mit=0,mkt=0. (b) When 1≤i≤m,k=m+1, mij=1,mkj=0, ∀1≤t≤n,t≠j, and mit=0,mkt=0. (c) When 1≤k≤m,i=m+1, mkj=1,mij=0, ∀1≤t≤n,t≠j, and mit=0,mkt=0. Hence, combining (a) and (b) with (c), if sj∈S, then sj is a core of the induced IT, ∃ei∈E,mij=1 and ∀st∈S,st≠sj,mit=0.
2⇐ Suppose sj∈S, ∃ei∈E,mij=1 and ∀st∈S,st≠sj,mit=0. Because ∀st∈S,mm+1t=0, by Theorem 4, dei,em+1=sj. According to Theorem 2, sj∈COREIT, i.e., sj is a core of the induced IT.
Combining (1) with (2), it completes the proof.
From Theorem8, if 1≤i≤m, ∃1≤j≤n,mij=1, and ∀1≤t≤n,t≠j,mit=0, then sj is a core of the induced S.
Definition5 and Theorems 6 and 7 make it possible to use attribute reduction methods to compute a minimal solution or the minimum solution of a USCP. Thus, the USCP can be solved by using rough set theory.
In the following example, we illustrate how to compute a minimal solution or the minimum solution of a USCP by calculating an attribute reduction or the minimum attribute reduction of the constructed information table.Example 4.
The discernibility matrixD of IT constructed by the USCP in Example 1 can be represented in Table 4, where we only consider the upper triangle matrix.
By Table4, the discernibility function fS of the induced IT is as follows:(12)fSs1,s2,s3,s4,s5=∧∨dei,ekdei,ek∈D=s1∨s2∨s4∨s5∧s1∨s2∨s3∨s4∨s5∧s1∨s2∨s3∨s4∧s1∨s2∨s4∧s1∨s2∨s3∨s5∧s1∨s2∨s5∧s1∨s3∨s4∨s5∧s3∨s4∨s5∧s2∨s3∨s4∨s5∧s1∨s3∨s4∧s1∨s3∧s3∨s4∧s2∨s5∧s2∨s3∨s5∧s1∨s2∨s4.
Using Boolean logical operations, we can obtain(13)fSs1,s2,s3,s4,s5=s1∧s3∧s5∨s1∧s4∧s5∨s1∧s2∧s4∨s3∧s4∧s5∨s2∧s3.
According to Theorem3, the induced IT has five attribute reductions: s1,s3,a5, s1,s4,s5, s1,s2,s4, s3,s4,s5, and s2,s3, where s2,s3 is the unique minimum attribute reduction. By Theorem 2, there is no core in the induced IT.
By Theorem6, we get that s1,s3,a5, s1,s4,s5, s1,s2,s4, s3,s4,s5, and s2,s3 are all minimal solutions of the USCP in Example 1, and s2,s3 is the unique minimum solution.Table 4
The discernibility matrixD of the IS induced by the USCP in Example 1.
e1e2e3e4e5e6e7e8e9e10e1∅s1,s2,s4,s5s1,s2,s3,s4,s5s1,s2,s3,s4s1,s2,s3,s4s1,s2,s4,s5s1,s2,s4,s5s1,s2,s3,s4,s5s1,s2,s4s1,s2,s4e2∅s1,s2,s3,s4,s5s1,s2,s3,s5s1,s2,s3,s4,s5s1,s2,s5s1,s2,s5s1,s2,s3,s5s1,s2,s4,s5s1,s2,s5e3∅s1,s3,s4,s5s3,s4,s5s2,s3,s4,s5s2,s3,s4,s5s2,s3,s4,s5s1,s2,s3,s4,s5s3,s4,s5e4∅s1,s3,s4s1,s2,s3,s5s1,s2,s3,s5s1,s2,s3,s5s1,s2,s3,s4s1,s3e5∅s2,s3,s4,s5s2,s3,s4,s5s2,s3,s4,s5s1,s2,s3,s4s3,s4e6∅s2,s5s2,s3,s5s1,s2,s4,s5s2,s5e7∅s2,s3,s5s1,s2,s4,s5s2,s5e8∅s1,s2,s3,s4,s5s2,s3,s5e9∅s1,s2,s4e10∅


## 4. Inducing a USC Model from an Information Table

From the analysis above, we know that a USC model can induce an information table, and the USCP can be transformed into the ARP in the induced information table. One can derive a minimal solution or the minimum solution of a USCP by calculating an attribute reduction or the minimum attribute reduction of the constructed information table. Conversely, in this section, we are interested in whether a given information table can induce a USC model and the ARP is corresponding to the USCP.In what follows, with the help of the simplified discernibility set proposed by Yao and Zhao [18], we construct a USCP model from a given information table, and the ARP is corresponding to the USCP. Thus, we give an example to explain the constructing process. Then, we discuss the connection between the ARP and the constructed USCP.Definition 6.
(see [18]). For a matrix element dxi′,xj′≠∅, if ∅≠dxi′,xj′⊂dxi,xj, let dxi′,xj′ absorb and replace another element dxi,xj, and we call the process element absorption.Definition 7.
(see [18]). For a discernibility matrix D=dxi,xjn×n, if we use element absorption to process all the elements in it, and then it can be converted into another simplified discernibility matrix D′=d′xi,xjn×n. We call the process matrix absorption and call D′ the simplified discernibility matrix of D.
In Definition7, we can see that no elements in D′ can be absorbed by each other. Yao and Zhao point out that the discernibility matrix D′ has the same set of attribute reductions as the discernibility matrix D [18], so do D′ and D.Example 5.
The simplified discernibility matrixD′ of D in Example 2 can be represented in Table 5 as follows, where we only consider the upper triangle matrix.
Using the simplified discernibility matrixD′, we can obtain(14)fSa1,a2,a3,a4,a5=∧∨dxi,xjdxi,xj∈D′=a2∧a4∧a5∧a1∨a3.
Using Boolean logical operations, we have(15)fSa1,a2,a3,a4,a5=a1∧a2∧a4∧a5∨a2∧a3∧a4∧a5.
The result is the same as Example2.
Inspired by the result proposed by [18], in the following, we construct an induced USC model from a given information table by using the simplified discernibility matrix.Table 5
The simplified discernibility matrixD′ for the IS in Example 2.
x1x2x3x4x5x6x1∅a5a2a2a2a1,a3x2∅a2a2a2a5x3∅a5a4a2x4∅a4a2x5∅a2x6∅Note. The simplified discernibility matrix D′ is not the unique one simplified discernibility matrix of D. The ordering in which different elements are absorbed can obtain different simplified discernibility matrix. Nevertheless, all the absorbed matrices have the same set of attribute reductions as the discernibility matrix D [18].Definition 8.
Given an information tableIT=U,A, U=x1,x2,…,xm, A=a1,a2,…,an, and D′=d1,d2,…,dt:(1)
AssignD′ as an object set E, that is, E=d1,d2,…,dt(2)
Assign a covering setS=sa1,sa2,…,sanwithsaj=diaj∈di,1≤i≤t,1≤j≤n
The object setE and the covering set S constitute a USC model with the t−row n−column 0−1 matrix
M=mijt×n as follows:(a)
mij=1ifaj∈di,1≤j≤n,1≤i≤t(b)
mij=0ifaj∉di,1≤j≤n,1≤i≤t
TheUSCP=E,S is called the induced USC model of the given IT.
In Definition8, for ∀di∈E, di≠∅, there is at least ∃aj∈A,aj∈di, such that di∈saj and di∈∪j=1nS. Thus, we have ∪j=1nS=E, i.e., S is exactly a set covering of E. Hence, the pair E,S is a USCP.Example 6.
Construct an induced USCP model from theIT in Example 2.
According to Table5, D′=a2,a4,a5,a1,a3, and assign the object set E=e1,e2,e3,e4=D′=a2,a4,a5,a1,a3, i.e., e1=a2, e2=a4, e3=a5, and e4=a1,a3. Assign a covering set S=e4,e1,e4,e2,e3. The object set E and the covering set S constitute the induced USC model of the IT in Example 2, where(16)M=mij4×5=01000000100000110100.Theorem 9.
Given an information tableIT=U,A, U=x1,x2,…,xm, A=a1,a2,…,an, and D′=d1,d2,…,dt, the induced USCP=E,S with E=d1,d2,…,dt, S=s1,s2,…,sn, and the 0−1 matrix M=mijt×n. For B⊆A, B is an attribute consistent set of the given IT iff S′=sajaj∈B is a set covering of the induced USCP.Proof of Theorem 9.
1⇒ Suppose B is an consistent set of the given IT. Then, for ∀di∈D′, B∩di≠∅, that is, there is at least ∃aj∈B and aj∈di, according to Definition 8, so di∈saj, di is covered by saj. Hence, S′=sajaj∈B covers di. Thus, S′=sajaj∈B is a set covering of the induced USCP.
2⇐ Suppose S′=sajaj∈B is a set covering of the induced USCP. Then, for ∀di∈E, ∃sj∈S′,di∈saj, according to Definition 8, aj∈di, so aj∩di≠∅. Hence, B∩di≠∅, B is an attribute consistent set of the given IT.
Combining (1) with (2), it completes the proof.
Similar to Section3, we can easily obtain some results.Theorem 10.
Given an information tableIT=U,A, U=x1,x2,…,xm, A=a1,a2,…,an, and D′=d1,d2,…,dt, the induced USCP=E,S with E=d1,d2,…,dt, S=s1,s2,…,sn, anf the 0−1 matrix M=mijt×n. For B⊆A, B is an attribute reduction of the given IT iff S′=sajaj∈B is a minimal solution of the induced USCP.Proof of Theorem 10.
By Theorems1 and 9, it can easily be proved.Theorem 11.
Given an information tableIT=U,A, U=x1,x2,…,xm, A=a1,a2,…,an, and D′=d1,d2,…,dt, the induced USCP=E,S with E=d1,d2,…,dt, S=s1,s2,…,sn, and the 0−1 matrix M=mijt×n. For B⊆A, B is a minimum attribute reduction of the given IT iff S′=sajaj∈B is a minimum solution of the induced USCP.Proof of Theorem 11.
By Theorem10, it is easy to prove.Theorem 12.
Given an information tableIT=U,A, U=x1,x2,…,xm, A=a1,a2,…,an, and D′=d1,d2,…,dt, the induced USCP=E,S with E=d1,d2,…,dt, S=s1,s2,…,sn, and the 0−1 matrix M=mijt×n. For an attribute aj∈A, aj is a core of the given IT iff ∃di∈E,di=aj in the induced USCP.Proof of Theorem 12.
1⇒ Suppose aj∈A, aj is a core of the given IT. Then, ∃di∈D′, di=aj. According to Definition 8, di∈E, ∃di∈E,di=aj in the induced USCP.
2⇐ Suppose ∃di∈E,di=aj in the induced USCP, according to Definition 8, di=aj∈D′, by Theorem 2, we have that aj is a core of the given IT.
Combining (1) and (2), it completes the proof.
From Theorems10 and 11, we can see that an attribute reduction or a minimum attribute reduction of a given information table is a solution or the minimum solution of the constructed USCP. Thus, the ARP can be converted into the USCP.
We can obtain all of the minimal solution of the constructedUSCP in Example 6 by using Matlab: X=1,1,0,1,1t and 0,1,1,1,1t. That is, a1,a2,a4,a5 and a2,a3,a4,a5 are all attribute reductions of the information table IT in Example 2. And by Theorem 12, a2,a4,a5 is the core set.


## 5. A Rough Set Heuristic Algorithm for USCP

Based on the discussion above, the relationship between the USCP and the ARP is established. One can investigate the USCP by rough set theory and discuss the ARP of an information table via set covering theory.In this section, based on rough set theory, we propose a heuristic algorithm based on rough set theory for USCP as an application of the proposed theoretical results.There is no doubt that the method based on discernibility function can compute all attribute reductions or an minimum attribute reduction, but the time complexity of it is NP-hard [26]. However, finding an attribute reduction based on heuristic algorithms can dramatically reduce the time complexity. By eliminating irrelevant states or unlikely possibilities, heuristic algorithms can lessen the computational efficiently. The classical heuristic algorithms are discernibility matrix methods [41–43], positive-region methods [44–46], and information entropy methods [23, 47, 48]. Information entropy methods usually use entropy to measure the importance of knowledge. They usually make the entropy as a heuristic function and select the more important knowledge based on the entropy gradually to construct an attribute reduction.The notion of entropy is introduced by Shannon, and Slezak applied Shannon’s entropy to compute an attribute reduction in information table [23].Definition 9.
(see [23]). Given an information table as IT=U,A. ∀B⊆A and(17)HB=−∑i=1rXiUlog2XiU,where HB is called the entropy of B.
Here,Xi∈U/RB=X1,X2,…,Xr, and · means the number of elements in a set. If HB=HA, then B is an attribute reduction of IT [23, 47]. The significance of attribute set B can be measured by HB.Definition 10 (see [23]).
Given an information tableIT=U,A. B⊆A, ∀a∉B, and(18)Siga,B=HB∪a−HB,where Siga,B is called the significance of attribute a w.r.t. B.
Now, we construct a rough set heuristic algorithm for USCP via the entropy.
By Algorithm1, we can compute a minimal solution of a given USCP by selecting the most important attribute one by one according to its entropy.
In Algorithm1, step 2 selects all cores according to Theorem 8 and its time complexity is O (mn). The time complexity of step 3 is O (mn). Step 4 is the most important step. It selects the most import attribute in S−Red w.r.t. the Red. Its time complexity is O (U2A) [46], that is, O (m2n). So, the time complexity of Algorithm 1 is O (m2n).Algorithm 1:A rough set heuristic algorithm for USCP.
Input: A USCP=E,S with E=e1,e2,…,em, S=s1,s2,…,sn, M=mijm×n;Output: A minimal solution.(1)
LetRed=∅;(2)
For all1≤i≤m, if ∃1≤j≤n,mij=1 and ∀1≤t≤n,t≠j,mit=0, then let Red=Red∪sj;(3)
Induce an information systemIS=U,S from the given USCP;(4)
While (HRed≠HS) do {(i)
For allaj∈S−Red, compute Sigsj,Red, if Hsj∪Red=HS, Red=Red∪sj and go to Step 5;(ii)
LetSigst,Red=maxSigsj,Redaj∈S−Red;(iii)
LetRed=Red∪st; }(5)
ReturnRed, that is, Red is a minimal solution of the USCP.Example 7.
Compute a minimal solution of the givenUSCP in Example 1 by using Algorithm 1.Input: the USCP=E,S in Example 1.(1)
LetRed=∅.(2)
For all1≤i≤m, there is not a 1≤j≤n,mij=1 and ∀1≤t≤n,t≠j,mit=0, so Red=∅.(3)
In Example3, we have induced the information table IT=U,S from the given USCP, see it.(4)
U/RS=e1,e2,e3,e4,e5,e6,e7,e8,e9,e10, HS=−∑i=1rXi/Ulog2Xi/U=−∑i=1101/10log21/10=−10×1/10log21/10=−log21/10=3.3219.(i)
Red=∅, HRed=0≠HS, do {U/Rs1=e3,e5,e6,e7,e8,e10,e1,e2,e4,e9,Sigs1,Red=Hs1=−6/10log26/10+4×1/10log21/10=1.7710;U/Rs2=e3,e4,e5,e10,e1,e2,e6,e7,e8,e9,Sigs2,Red=Hs2=−4/10log24/10+6×1/10log21/10=2.5219;Sigs3,Red=Hs3=1.7710;Sigs4,Red=Hs4=1.7710;Sigs5,Red=Hs5=2.1610;Sigst,Red=maxSigsj,Redaj∈S−Red=Sigs2,Red=2.5219;LetRed=Red∪s2=s2. }(ii)
Red=s2, Hs2=2.5219≠HS, do {U/Rs1,s2=e3,e5,e10,e1,e2,e4,e6,e7,e8,e9,Hs1,s2=2.8464,Sigs1,Red=Hs1,s2−Hs2=2.8464−2.5219=0.3245;Hs2,s3=3.3219=HS, Red=s2,s3 and goto Step5. }(5)
Returns2,s3, that is, s2,s3 is a minimal solution of the USCP.
The minimal solutions2,s3 computed by Algorithm 1 is the same as the result computed by Matlab and computed by discernibility function.


## 6. Conclusions

This paper has established the relationship between the USCP and the ARP. The results have shown that finding a minimal or a minimum solution of a USC model is equivalent to finding an attribute reduction or a minimum attribute reduction in the induced information table. Also, finding an attribute reduction or a minimum attribute reduction of an information table is equivalent to finding a minimal or a minimum solution in the induced USC model. The results have provided the two problems to be characterized by each other and bring new methods mutually. As an application, a rough set heuristic algorithm for USCP has been given.In practical applications, data is always not free. In view of this situation, Min et al. formally defined test-cost-sensitive decision system [49]. In test-cost-sensitive decision system, there is a test cost for each data item. The test-cost-sensitive ARP is to find a reduction which has the minimal cost [32]. In addition, in the SCP, each subset sj associates a cost cj>0. The SCP is to find a minimal cost set covering where the cost is minimal. Our future work will plan to discuss the relationship between the test-cost-sensitive ARP and the SCP. In this paper, the induced information table constructed by a USC model is an N-soft set. Parameter reduction is an active area of research in soft set theory as well [50]. Discussing the relationship between the parameter reduction problem and the SCP is also a future work of us. In rough set theory and granular computing, one normally considers measures of granularity, as discussed in Section 5. It might be interesting to look at other measures, for example, complexity measures [51]. In the future research, we will study the attribute reduction problem based on complexity measure.



---

*Source: 5359691-2020-06-16.xml*