# A Granular Reduction Algorithm Based on Covering Rough Sets

Authors: Tian Yang; Zhaowen Li; Xiaoqing Yang
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

The granular reduction is to delete dispensable elements from a covering.
It is an efficient method to reduce granular structures and get rid of the
redundant information from information systems. In this paper, we develop
an algorithm based on discernability matrixes to compute all the granular
reducts of covering rough sets. Moreover, a discernibility matrix is simplified
to the minimal format. In addition, a heuristic algorithm is proposed as well
such that a granular reduct is generated rapidly.


---

## Body

## 1. Introduction

With the development of technology, the gross of information increases in a surprising way. It is a great challenge to extract valuable knowledge from the massive information. Rough set theory was raised by Pawlak [1, 2] to deal with uncertainty and vagueness, and it has been applied to the information processing in various areas [3–8].One of the most important topics in rough set theory is to design reduction algorithms. The reduction of Pawlak's rough sets is to reduce dispensable elements from a family of equivalence relations which induce the equivalence classes, or a partition.Covering generalized rough set [9–19] and binary relation generalized rough set [20–26] are two main extensions of Pawlak's rough set. The reduction theory of covering rough sets [10, 11, 15, 23, 27, 28] plays an important role in practice. A partition is no longer a partition if any of its elements is deleted, while a covering may still be a covering with invariant set approximations after dropping some elements. Therefore, there are two types of reduction on covering rough sets. One is to reduce redundant coverings from a family of coverings, referred to as the attribute reduction.The other is to reduce redundant elements from a covering, noted as the granular reduction.It is to find the minimal subsets of a covering which generate the same set approximations with the original covering. Employed to reduce granular structures and databases as well as interactive with the attribute reduction, we think the granular reduction should be ignored by no means. In this paper, we devote to investigate granular reduction of covering rough sets.In order to compute all attribute reducts for Pawlak's rough sets, discernibility matrix is initially presented [29]. Tsang et al. [15] develop an algorithm of discernibility matrices to compute attribute reducts for one type of covering rough sets. Zhu and Wang [17] and Zhu [18] build one type of granular reduction for two covering rough set models initially. In addition, Yang et al. systematically examine the granular reduction in [30] and the relationship between reducts and topology in [31]. Unfortunately, no effective algorithm for granular reduction has hitherto been proposed.In this paper, we bridge the gap by constructing an algorithm based on discernibility matrixes which is applicable to all granular reducts of covering rough sets. This algorithm can reduce granular structures and get rid of the redundant information from information systems. Then a discernibility matrix is simplified to the minimal format. Meanwhile, based on a simplification of discernibility matrix, a heuristic algorithm is proposed as well.The remainder of this paper proceeds as follows. Section2 reviews the relevant background knowledge about the granular reduction. Section 3 constructs the algorithm based on discernibility matrix. Section 4 simplifies the discernibility matrix and proposes a heuristic algorithm. Section 5 concludes the study.


## 2. Background

Our aim in this section is to give a glimpse of rough set theory.LetU be a finite and nonempty set, and let R be an equivalence relation on U. R generates a partition U/R={[x]R∣x∈X} on U, where [x]R is an equivalence class of x generated by the equivalence relation R. We call it elementary sets of R in rough set theory. For any set X, we describe X by the elementary sets of R, and the two sets
(2.1)R*=∪{[x]R∣[x]R⊆X},R*=∪{[x]R∣[x]R∩X≠⌀}
are called the lower and upper approximations of X, respectively. If R*(X)=R*(X),X is an R-exact set. Otherwise, it is an R-rough set.Letℝ be a family of equivalence relations, and let A∈ℝ, denoted as IND(ℝ)=∩{R:R∈ℝ}. A is dispensable in ℝ if and only if IND(ℝ)=IND(ℝ-A). Otherwise, A is indispensable in ℝ. The family ℝ is independent if every A∈ℝ is indispensable in ℝ. Otherwise, ℝ is dependent. ℚ∈ℙ is a reduct of ℙ if ℚ is independent and IND(ℚ)=IND(ℙ). The sets of all indispensable relations in ℙ are called the core of ℙ, denoted as CORE(ℙ). Evidently, CORE(ℙ)=∩RED(ℙ), where RED(ℙ) is the family of all reducts of ℙ. The discernibility matrix method is proposed to compute all reducts of information systems and relative reducts of decision systems [29].𝒞 is called a covering of U, where U is a nonempty domain of discourse, and 𝒞 is a family of nonempty subsets of U and ∪𝒞=U.It is clear that a partition ofU is certainly a covering of U, so the concept of a covering is an extension of the concept of a partition.Definition 2.1 (minimal description [9]).
Let𝒞 be a covering of U,
(2.2)MdC(x)={K∈C∣x∈K∧(∀S∈C∧x∈S∧S⊆K⇒K=S)}
is called the minimal description of x. When there is no confusion, we omit the 𝒞 from the subscript.Definition 2.2 (neighborhood [9, 19]).
Let𝒞 be a covering of U, and N𝒞(x)=∩{C∈𝒞∣x∈C} is called the neighborhood of x. Generally, we omit the subscript 𝒞 when there is no confusion.Minimal description and neighborhood are regarded as related information granules to describex, which are used as approximation elements in rough sets (as shown in Definition 2.3). It shows that N(x)=∩{C∈𝒞∣x∈C}=∩Md(x). The neighborhood of x can be seen as the minimum description of x, and it is the most precise description (more details are referred to [9]).Definition 2.3 (covering lower and upper approximation operations [19]).
Let𝒞 be a covering of U. The operations CL𝒞:P(U)→P(U) and CL′𝒞:P(U)→P(U) are defined as follows: for all X∈P(U),
(2.3)CLC(X)=∪{K∈C∣K⊆X}=∪{K∣∃x,s.t.(K∈Md(x))∧(K⊆X)},CL′C(X)={x∣N(x)⊆X}=∪{N(x)∣N(x)⊆X}.
We call CL𝒞 the first, the second, the third, or the fourth covering lower approximation operations and CL′𝒞 the fifth, the sixth, or the seventh covering lower approximation operations, with respect to the covering 𝒞.
The operationsFH, SH, TH, RH, IH, XH,  and  VH:P(U)→P(U) are defined as follows: for all X∈P(U),
(2.4)FHC(X)=CL(X)∪(∪{Md(x)∣x∈X-CL(X)}),SHC(X)=∪{K∣K∈C,K∩X≠⌀},THC(X)=∪{Md(x)∣x∈X},RHC(X)=CL(X)∪(∪{K∣K∩(X-CL(X))≠⌀}),IHC(X)=CL(X)∪(∪{N(x)∣x∈X-CL(X)}=∪{N(x)∣x∈X}),XHC(X)={x∣N(x)∩X≠⌀},VHC(X)=∪{N(x)∣N(x)∩X≠⌀}.FH𝒞, SH𝒞, TH𝒞, RH𝒞, IH𝒞, XH𝒞, and  VH𝒞 are called the first, the second, the third, the fourth, the fifth, the sixth, and the seventh covering upper approximation operations with respect to 𝒞, respectively. We leave out 𝒞 at the subscript when there is no confusion.As shown in [32], every approximation operation in Definition 2.3 may be applied in certain circumstance. We choose the suitable approximation operation according to the specific situation. So it is important to design the granular reduction algorithms for all of these models.More precise approximation spaces are proposed in [30]. As a further result, a reasonable granular reduction of coverings is also introduced. Let ℳ𝒞=∪{Md(x)∣x∈U}, 𝒩𝒞={N(x)∣x∈U}. 〈U,ℳ𝒞〉 is the approximation space of the first and the third types of covering rough sets, 〈U,𝒞〉 is the approximation space of the second and the fourth types of covering rough sets, and 〈U,𝒩𝒞〉 is the approximation space of the fifth, the sixth, and the seventh types of covering rough sets (referred to [30] for the details). In this paper, we design the algorithm of granular reduction for the fifth, the sixth, and the seventh type of covering rough sets.Let𝒞 be a covering of U, denoting a covering approximation space. ℳ𝒞 denotes an ℳ-approximation space. 𝒩𝒞 represents an 𝒩-approximation space. We omit 𝒞 at the subscript when there is no confusion (referred to [30] for the details).


## 3. Discernibility Matrixes Based on Covering Granular Reduction

In the original Pawlak's rough sets, a family of equivalence classes induced by equivalence relations is a partition. Once any of its elements are deleted, a partition is no longer a partition. The granular reduction refers to the method of reducing granular structures and to get rid of redundant information in databases. Therefore, granular reduction is not applicable to the original Pawlak's rough sets. However, as one of the most extensions of Pawlak's rough sets, a covering is still working even subject to the omission of its elements, as long as the set approximations are invariant. The purpose of covering granular reduction is to find minimal subsets keeping the same set approximations. It is meaningful and necessary to develop the algorithm for covering granular reduction.The quintuple (U,𝒞,CL,CH) is called a covering rough set system (CRSS), where 𝒞 is a covering of U, CL and CH are the lower and upper approximation operations with respect to the covering 𝒞, and 〈U,𝒜𝒞〉 is the approximation space. According to the categories of covering approximation operations in [30], there are two kinds of situations as follows.(1)
If𝒜𝒞=𝒞 or 𝒜𝒞=ℳ𝒞, then 𝒜𝒞⊆𝒞: thus; 𝒜𝒞 is the unique granular reduct of 𝒞. There is no need to develop an algorithm to compute granular reducts for the first, the second, the third, and the fourth type of the covering rough sets.(2)
If𝒜𝒞=𝒩𝒞, generally, 𝒜𝒞 is not a subset of 𝒞. Consequently, an algorithm is needed to compute all granular reducts of 𝒞 for the fifth, the sixth, and the seventh type of covering rough set models.Next we examine the algorithm of granular reduction for the fifth, the sixth, and the seventh type of covering rough sets. Let𝒞 be a covering of U, since 𝒩𝒞={N(x)∣x∈U}, and 𝒩𝒞 is the collection of all approximation elements of the fifth, the sixth, or the seventh type of lower/upper approximation operations. 𝒩𝒞 is called the 𝒩-approximation space of 𝒞. Given a pair of approximation operations, the set approximations of any X⊆U are determined by the 𝒩-approximation spaces. Thus, for the fifth, the sixth, and the seventh type of covering rough set models, the purpose of granular reduction is to find the minimal subsets 𝒞′ of 𝒞 such that 𝒩𝒞=𝒩𝒞′. The granular reducts based on the 𝒩-approximation spaces are called the 𝒩-reducts. Nred(𝒞) is the set of all 𝒩-reducts of 𝒞, and NI(𝒞) is the set of all 𝒩-irreducible elements of 𝒞 (referred to [30] for the details).In Pawlak's rough set theory, for every pair ofx,y∈U, if y belongs to the equivalence class containing x, we say that x and y are indiscernible. Otherwise, they are discernible. Let ℝ={R1,R2,…,Rn} be a family of equivalence relation on U, Ri∈ℝ. Ri is indispensable in ℝ if and only if there is a pair of x,y∈U such that the relation between x and y is altered after deleting Ri from ℝ. The attribute reduction of Pawlak's rough sets is to find minimal subsets of ℝ which keep the relations invariant for any x,y∈U. Based on this statement, the method of discernibility matrix to compute all reducts of Pawlak's rough sets was proposed in [29]. In covering rough sets, however, the discernibility relation between x,y∈U is different from that in Pawlak's rough sets.Let𝒞 be a covering on U, (x,y)∈U×U. Then we call (x,y) indiscernible if y∈N(x), that is, N(y)⊆N(x). Otherwise, (x,y) is discernible. When 𝒞 is a partition, the new discernibility relation coincides with that in Pawlak's. It is an extension of Pawlak's discernibility relation. In Pawlak's rough sets, (x,y) is indiscernible if and only if (y,x) is indiscernible. However, for a general covering, if N(y)⊆N(x) and N(y)≠N(x), that is, y∈N(x) and x∉N(y), (y,x) is discernible while (x,y) is indiscernible. Thereafter, we call these relations the relations of (x,y) with respect to 𝒞. The following theorem characterizes these relations.Proposition 3.1.
Let𝒞={Ci∣i=1,2,3,…,n} be a covering on U, and let 𝒞x={Ci∈𝒞∣x∈Ci}.(1)
y∈N(x) if and only if 𝒞x⊆𝒞y.(2)
y∉N(x) if and only if there is Ci∈𝒞 such that x∈Ci and y∉Ci.Proof.
(
1
)
y
∈
N
(
x
)
=
∩
𝒞
x
⇔ for any Ci∈𝒞x, y∈Ci⇔ for any Ci∈𝒞x, Ci∈𝒞y⇔𝒞x⊆𝒞y.
(
2
) It is evident from (1).Theorem 3.2.
Let𝒞 be a covering on U, Ci∈𝒞. Then 𝒩𝒞≠𝒩𝒞-{Ci} if and only if there is (x,y)∈U×U whose discernibility relation with respect to 𝒞 is changed after deleting Ci from 𝒞.Proof.
Suppose that𝒩𝒞≠𝒩𝒞-{Ci}, then there is at least one element x∈U such that N𝒞(x)≠N𝒞-{Ci}(x), that is, N𝒞(x)⊂N𝒞-{Ci}(x). Since N𝒞-{Ci}(x)-N𝒞(x)≠⌀, suppose that y∈N𝒞-{Ci}(x)-N𝒞(x), then y∈N𝒞-{Ci}(x) and y∉N𝒞(x). Namely, (x,y) is discernible with respect to 𝒞, while (x,y) is indiscernible with respect to 𝒞-{Ci}.
Suppose that there is(x,y)∈U×U whose discernibility relation with respect to 𝒞 is changed after deleting Ci from 𝒞. Put differently, (x,y) is discernible with respect to 𝒞, while (x,y) is indiscernible with respect to 𝒞-{Ci}. Then we have y∈N𝒞-{Ci}(x) and y∉N𝒞(x), so y∈N𝒞-{Ci}(x)-N𝒞(x). Thus, N𝒞(x)≠N𝒞-{Ci}(x). It implies 𝒩𝒞≠𝒩𝒞-{Ci}.The purpose of granular reducts of a covering𝒞 is to find the minimal subsets of 𝒞 which keep the same classification ability as 𝒞 or, put differently, keep 𝒩𝒞 invariant. In Theorem 3.2, 𝒩𝒞 is kept unchanged to make the discernibility relations of any (x,y)∈U×U invariant. Based on this statement, we are able to compute granular reducts with discernibility matrix.Definition 3.3.
LetU={x1,x2,…,xn}, 𝒞 be a covering on U. M(U,𝒞) is an n×n matrix (cij)n×n called a discernibility matrix of (U,𝒞), where(1)
cij=⌀, xj∈N(xi),(2)
cij={C∈𝒞∣xi∈C,xj∉C}, xj∉N(xi).This definition of discernibility matrix is more concise than the one in [11, 15] due to the reasonable statement of the discernibility relations. Likewise, we restate the characterizations of 𝒩-reduction.Proposition 3.4.
Consider thatNI(𝒞)={C∣cij={C} for some cij∈M(U,𝒞)}.Proof.
For anyC∈NI(𝒞), 𝒩𝒞≠𝒩𝒞-{C}, then there is (xi,xj)∈U×U such that xj∈N𝒞-{C}(xi) and xj∉N𝒞(xi). It implies that xi∈C and xj∉C. Moreover, for any C′∈𝒞-{C}, since xj∈N𝒞-{C}(xi), we have xi∈C′ if xi∈C′. Thus, cij={C}.
Ifcij={C} for some cij∈M(U,𝒞), then xi∈C and xj∉C. And for any C′∈𝒞-{C}, if xi∈C′, then xi∈C′, that is, xj∈N𝒞-{C}(xi) and xj∉N𝒞(xi), then N𝒞-{C}(xi)≠N𝒞(xi). Namely, 𝒩𝒞≠𝒩𝒞-{C}, which implies C∈NI(𝒞).Proposition 3.5.
Suppose that𝒞′⊆𝒞, then 𝒩𝒞=𝒩𝒞′ if and only if 𝒞′∩cij≠⌀ for every cij≠⌀.Proof.
𝒩
𝒞
=
𝒩
𝒞
′
⇔ for any (xi,xj)∈U×U, xj∉N𝒞(xi) if and only if xj∉N𝒞′(xi),
⇔ for any (xi,xj)∈U×U, there is C∈𝒞 such that xi∈C and xj∉C if and only if there is C′∈𝒞′ such that xi∈C′ and xj∉C′,
⇔ for any cij≠⌀, 𝒞′≠⌀.Proposition 3.6.
Suppose that𝒞′⊆𝒞, then 𝒞′∈Nred(𝒞) if and only if 𝒞′ is a minimal set satisfying 𝒞′∩cij≠⌀ for every cij≠⌀.Definition 3.7.
LetU={x1,x2,…,xn}, let 𝒞={C1,C2,…,Cm} be a covering of U, and let M(U,𝒞)=(cij)n×n be the discernibility matrix of (U,𝒞). A discernibility function f(U,𝒞) is a Boolean function of m Boolean variables, C1¯,C2¯,…,Cm¯, corresponding to the covering elements C1,C2,…,Cm, respectively, defined as f(U,𝒞)(C1¯,C2¯,…,Cm¯)=∧{∨(cij)∣cij∈M(U,𝒞),cij≠⌀}.Theorem 3.8.
Let𝒞 be a family of covering on U, let f(U,𝒞) be the discernibility function, and let g(U,𝒞) be the reduced disjunctive form of f(U,𝒞) by applying the multiplication and absorption laws. If g(U,𝒞)=(∧𝒞1)∨⋯∨(∧𝒞l), where 𝒞k⊆𝒞, k=1,2,…,l and every element in 𝒞k only appears once, then Nred(𝒞)={𝒞1,𝒞2,…,𝒞l}.Proof.
For everyk=1,2,…,l, ∧𝒞k≤∨cij for any cij∈M(U,𝒞), so 𝒞k∩cij≠⌀. Let 𝒞k′=𝒞k-{C} for any C∈𝒞k, then g(U,𝒞)≨∨t=1k-1(∧𝒞t)∨(∧𝒞k′)∨(∨t=k+1l(∧𝒞t)). If for every cij∈M(U,𝒞), we have 𝒞k′∩cij≠⌀, then ∧𝒞k′≤∨cij for every cij∈M(U,𝒞), that is, g(U,𝒞)≥∨t=1k-1(∧𝒞t)∨(∧𝒞k′)∨(∨t=k+1l(∧𝒞t)), which is a contradiction. It implies that there is ci0j0∈M(U,𝒞) such that 𝒞k′∩ci0j0=⌀. Thus, 𝒞k is a reduct of 𝒞.
For any𝒞′∈Red(𝒞), we have 𝒞′∩cij≠⌀ for every cij∈M(U,𝒞), so f(U,𝒞)∧(∧𝒞′)=∧(∨cij)∧(∧𝒞′)=∧𝒞′, which implies ∧𝒞′≤f(U,𝒞)=g(U,𝒞). Suppose that, for every k=1,2,…,l, we have 𝒞k-𝒞′≠⌀, then for every k, there is 𝒞k∈𝒞k-𝒞′. By rewriting g(U,𝒞)=(∨k=1l𝒞k)∧Φ, ∧𝒞′≤∨k=1l𝒞k. Thus, there is Ck0 such that ∧𝒞′≤𝒞k0, that is, 𝒞k0∈𝒞′, which is a contradiction. So 𝒞k0⊆𝒞′ for some k0, since both 𝒞′ and 𝒞k0 are reducts, and it is evident that 𝒞′=𝒞k0. Consequently, Red(𝒞)={𝒞1,𝒞2,…,𝒞l}.Algorithm 3.9.
Consider the following:
input: 〈U,𝒞〉,
output: Nred(𝒞) and NI(𝒞)// The set of all granular reducts and the set of all 𝒩-irreducible elements.Step 1:M(U,𝒞)=(cij)n×n, for each cij, let cij=⌀.Step 2: for eachxi∈U, compute N(xi)=∩{C∈𝒞∣xi∈C}.Ifxj∉N(xi),cij={C∈𝒞∣xi∈C,xj∉C}.Step 3:f(U,𝒞)(C1¯,C2¯,…,Cm¯)=∧{∨(cij)∣cij∈M(U,𝒞),cij≠⌀}.Step 4: computef(U,𝒞) to g(U,𝒞)=(∧𝒞1)∨⋯∨(∧𝒞l)// where 𝒞k⊆𝒞,k=1,2,…,l, and every element in 𝒞k only appears once.Step 4: outputNred(𝒞)={𝒞1,𝒞2,…,𝒞l}, NI(𝒞)=∩Nred(𝒞).Step 5: end.The following example is used to illustrate our idea.Example 3.10.
Suppose thatU={x1,x2,…,x6}, where xi,i=1,2,…,6 denote six objects, and let Ci,i=1,2,…,7 denote seven properties; the information is presented in Table 1, that is, the ith object possesses the jth attribute is indicated by a * in the ij-position of the table.Table 1
Objects
C
1
C
2
C
3
C
4
C
5
C
6
C
7
x
1
*
*
*
*
*
x
2
*
x
3
*
*
*
x
4
*
*
*
*
*
*
x
5
*
*
*
x
6
*
*{
x
1
,
x
2
,
x
3
} is the set of all objects possessing the attribute C1, and it is denoted by C1={x1,x2,x3}. Similarly, C2={x1,x4}, C3={x3,x4,x5}, C4={x1,x4,x5}, C5={x1,x4,x6}, C6={x3,x4}, and C7={x1,x4,x5,x6}. Evidently, 𝒞={C1,C2,C3,C4,C5,C6,C7} is a covering on U.Then,N(x1)={x1}, N(x2)={x1,x2,x3}, N(x3)={x3}, N(x4)={x4}, N(x5)={x4,x5}, and N(x6)={x4,x6}.The discernibility matrix of(U,𝒞) is exhibited as follows:
(3.1)(⌀{C2,C4,C5,C7}{C2,C4,C5,C7}{C1}{C1,C2,C5}{C1,C2,C4}⌀⌀⌀{C1}{C1}{C1}{C3,C6}{C3,C6}⌀{C1}{C1,C6}{C1,C3,C6}{C3,C6}{C2,C3,C4,C5,C6,C7}{C2,C4,C5,C7}⌀{C2,C5,C6}{C2,C3,C4,C6}{C3}{C3,C4,C7}{C4,C7}⌀⌀{C3,C4}⌀{C5,C7}{C5,C7}⌀{C5}⌀),(3.2)f(U,Δ)(C1¯,C2¯,C3¯,C4¯,C5¯,C6¯,C7¯)=∧{∨(cij)∣i,j=1,2,…,6,cij≠⌀}=(C2∨C4∨C5∨C7)∧(C2∨C4∨C5∨C7)∧C1∧(C1∨C2∨C5)∧(C1∨C2∨C4)∧C1∧C1∧C1∧(C3∨C6)∧(C3∨C6)∧(C1)∧(C1∨C6)∧(C1∨C3∨C6)∧(C3∨C6)∧(C2∨C3∨C4∨C5∨C6∨C7)∧(C2∨C4∨C5∨C7)∧(C2∨C5∨C6)∧(C2∨C3∨C4∨C6)∧C3∧(C3∨C4∨C7)∧(C4∨C7)∧(C3∨C4)∧(C5∨C7)∧(C5∨C7)∧C5=(C5∧C1∧C3∧C4)∨(C5∧C1∧C3∧C7).SoNred(𝒞)={{C1,C3,C4,C5},{C1,C3,C5,C7}}, NI(𝒞)={C1,C3,C5}. As a result, Table 1 can be simplified into Table 2 or Table 3, and the ability of classification is invariant. Obviously, the granular reduction algorithm can reduce data sets as shown.Table 2
Objects
C
1
C
3
C
4
C
5
x
1
*
*
*
x
2
*
x
3
*
*
x
4
*
*
*
x
5
*
*
x
6
*Table 3
Objects
C
1
C
3
C
5
C
7
x
1
*
*
*
x
2
*
x
3
*
*
x
4
*
*
*
x
5
*
*
x
6
*
*


## 4. The Simplification of Discernibility Matrixes

For the purpose of finding the set of all granular reducts, we have proposed the method by discernibility matrix. Unfortunately, it is at least an NP problem, since the discernibility matrix in this paper is more complex than the one in [33]. Accordingly, we simplify the discernibility matrixes in this section. In addition, a heuristic algorithm is presented to avoid the NP hard problem.Definition 4.1.
LetM(U,𝒞)=(cij)n×n be the discernibility matrix of (U,𝒞). For any cij∈M(U,𝒞), if there is an nonempty element ci0j0∈M(U,𝒞)-{cij} such that ci0j0⊆cij, let cij′=⌀; otherwise, cij′=cij, then we get a new discernibility matrix SIM(U,𝒞)=(cij′)n×n, which called the simplification discernibility matrix of (U,𝒞).Theorem 4.2.
LetM(U,𝒞) be the discernibility matrix of (U,𝒞), and SIM(U,𝒞) is the simplification discernibility matrix, 𝒞′⊆𝒞. Then 𝒞′∩cij≠⌀ for any nonempty element cij∈M(U,𝒞) if and only if 𝒞′∩cij′≠⌀ for any nonempty element cij′∈SIM(U,𝒞).Proof.
If𝒞′∩cij≠⌀ for every cij≠⌀ and cij∈M(U,𝒞), it is evident that 𝒞′∩cij′≠⌀ for every cij′≠⌀ and cij′∈SIM(U,𝒞).
Suppose that𝒞′∩cij′≠⌀ for every cij′≠⌀ and cij′∈SIM(U,𝒞). For any nonempty cij∈M(U,𝒞), if there is an nonempty element ci0j0∈M(U,𝒞)-{cij} such that ci0j0⊆cij, and for any nonempty element ci1j1∈M(U,𝒞)-{cij,ci0j0}, ci1j1⊈ci0j0, then ci0j0′=ci0j0≠⌀. Since 𝒞′∩ci0j0′≠⌀, then 𝒞′∩ci0j0≠⌀; thus, 𝒞′∩cij≠⌀. If ci0j0⊈cij for any nonempty element ci0j0∈M(U,𝒞)-{cij}, then cij′=cij. Since 𝒞′∩cij′≠⌀, then 𝒞′∩cij≠⌀. Thus, 𝒞′∩cij≠⌀ for every nonempty cij∈M(U,𝒞).Proposition 4.3.
Suppose that𝒞′⊆𝒞, then 𝒞′∈Nred(𝒞) if and only if 𝒞′ is a minimal set satisfying 𝒞′∩cij′≠⌀ for every cij′≠⌀ and cij′∈<?brm?>SIM(U,𝒞).Proposition 4.4.
Consider that∪{cij′∣cij′∈SIM(U,𝒞)}=∪Nred(𝒞).Proof.
Suppose thatC∈∪{cij′∣cij′∈SIM(U,𝒞)}, then there is cij′∈SIM(U,𝒞) such that C∈cij′ and cij′∩NI(𝒞)=⌀. For any cij′∈SIM(U,𝒞), if C∈cij′, let cij1={C}. Otherwise, cij1={Cij}, where Cij∈cij′. Suppose that M1(U,𝒞)=(cij1)n×n; it is easy to prove that C∈∪{cij1∣cij1∈M1(U,𝒞)}∈Nred(𝒞). Thus, C∈∪Nred(𝒞).
Suppose thatC∈∪Nred(𝒞), then there is 𝒞k∈Nred(𝒞) such that C∈𝒞k. From Proposition 4.3, we know that 𝒞k is a minimal set satisfying 𝒞k∩c′ij≠⌀ for every cij′≠⌀ and cij′∈SIM(U,𝒞). So there is a cij′∈SIM(U,𝒞) such that C∈cij′, or else C is redundant in 𝒞k. Thus, C∈∪{cij′∣cij′∈SIM(U,𝒞)}.
In summary,∪{cij′∣cij′∈SIM(U,𝒞)}=∪Nred(𝒞).Proposition 4.5.
LetSIM(U,𝒞)=(cij′)n×n be the simplified discernibility matrix of (U,𝒞), then SIM(U,𝒞) is the minimal matrix to compute all granular reducts of 𝒞, that is, for any matrix M0(U,𝒞)=(dij)n×n where dij⊆cij′, M0(U,𝒞) can compute all granular reducts of 𝒞 if and only if dij=cij′ for 1≤i,j≤n.Proof.
Ifdij=cij′ for 1≤i,j≤n, then M0(U,𝒞)=SIM(U,𝒞), and M0(U,𝒞) can compute all granular reducts of 𝒞.
Suppose that there is a nonemptyci0j0′∈SIM(U,𝒞) such that di0j0⊂ci0j0′. If |ci0j0′|=1, suppose that ci0j0′={C0}, then di0j0=⌀. From the definition of the simplification discernibility matrix, we know that C0∉cij′ for any cij′∈SIM(U,𝒞)-{ci0j0′}, then C0∉dij for any dij∈M0(U,𝒞). So M0(U,𝒞) cannot compute any granular reducts of 𝒞. If |ci0j0′|≥2, we suppose that di0j0≠⌀. Then there is a C∈(ci0j0′-di0j0), and let ci0j01={C}. For any cij′∈SIM(U,𝒞)-{ci0j0′}, if C∈cij′, let cij1=⌀. Otherwise, let cij1={Cij} where Cij∈cij′-ci0j0′. Let M1(U,𝒞)=(cij1)n×n and 𝒞′=∪{cij1∣cij1∈M1(U,𝒞)}, and it is easy to prove that 𝒞′∈Nred(𝒞). However, 𝒞′∩di0j0=⌀, that is, M0(U,𝒞) cannot compute all granular reducts of 𝒞. Thus, if M0(U,𝒞) can compute all granular reducts of 𝒞, then dij=cij′ for 1≤i,j≤n.From the above propositions, we know that the simplified discernibility matrix is the minimal discernibility matrix which can compute the same reducts as the original one. Hereafter, we only examine simplified discernibility matrixes instead of general discernibility matrixes. The following example is used to illustrate our idea.Example 4.6.
The discernibility matrix of(U,𝒞) in Example 3.10 is as follows:
(4.1)(⌀{C5}⌀{C1}⌀⌀⌀⌀⌀⌀⌀⌀{C3}⌀⌀⌀⌀⌀⌀⌀⌀⌀⌀⌀⌀⌀{C4,C7}⌀⌀⌀⌀⌀⌀⌀⌀⌀),f(U,Δ)(C1¯,C2¯,C3¯,C4¯,C5¯,C6¯,C7¯)=∧{∨(cij′)∣i,j=1,2,…,6,cij≠⌀}=C5∧C1∧C3∧(C4∨C7)=(C5∧C1∧C3∧C4)∨(C5∧C1∧C3∧C7).
So Nred(𝒞)={{C1,C3,C4,C5},{C1,C3,C5,C7}}, NI(𝒞)={C1,C3,C5}.From the above example, it is easy to see that simplified discernibility matrix can simplify the computing processes remarkably. Especially when𝒞 is a consistent covering proposed in [30], that is, Nred(𝒞)={NI(𝒞)}, the unique reduct Nred(𝒞)={∪{cij′∣cij′∈SIM(U,𝒞)}}.Unfortunately, although the simplified discernibility matrixes are more simple, the processes of computing reducts by discernibility function are still NP hard. Accordingly, we develop a heuristic algorithm to obtain a reduct from a discernibility matrix directly.LetM(U,𝒞)=(cij)n×n be a discernibility matrix. We denote the number of the elements in cij by |cij|. For any C∈𝒞, ||C|| denotes the number of cij which contain C. Let cij∈M(U,𝒞), if for any C∈NI(𝒞), C∉cij, then cij′=cij. Since ∪{cij′∣|cij′|≥2}=∪Nred(𝒞)-NI(𝒞), if |cij′|≥2, then the elements in cij′ may either be deleted from 𝒞 or be preserved. Suppose that C0∈∪{cij′∣|cij′|≥2}, if ||C0||≥||C|| for any C∈∪{cij′∣|cij′|≥2}, C0 is called the maximal element with respect to the simplified discernibility matrix SIM(U,𝒞). The heuristic algorithm to get a reduct from a discernibility matrix directly proceeds as follows.Algorithm 4.7.
Consider the following:
input: 〈U,𝒞〉,
output: granular reducts redStep 1:M(U,𝒞)=(cij)n×n, for each cij, let cij=⌀.Step 2: for eachxi∈U, compute N(xi)=∩{C∈𝒞xi∈C}.Ifxj∉N(xi),cij={C∈𝒞∣xi∈C,xj∉C}//getthediscernibilitymatrix.Step 3: for eachcij∈M(U,𝒞),if there is a nonempty elementci0j0∈M(U,𝒞)-{cij} such thatci0j0⊆cij, let cij=⌀ // get the simplified discernibility matrix.Step 4: for eachCi∈∪M(U,𝒞), compute ||Ci|| and select the maximalelementC0 of SIM(U,𝒞).For eachcij∈M(U,𝒞),ifC0∈cij,letcij={C0}.Step 5: if there iscij∈M(U,𝒞) such that |cij|⩾2,return to Step 3;elseoutput red=∪M(U,𝒞).Step 5: end.Example 4.8.
The simplified discernibility matrix of(U,𝒞) in  Example 3.10 is as follows:
(4.2)(⌀{C5}⌀{C1}⌀⌀⌀⌀⌀⌀⌀⌀{C3}⌀⌀⌀⌀⌀⌀⌀⌀⌀⌀⌀⌀⌀{C4,C7}⌀⌀⌀⌀⌀⌀⌀⌀⌀).
For a maximal elementC4 of SIM(U,𝒞), let c531={C4}, then we get M1(U,𝒞) as follows:
(4.3)(⌀{C5}⌀{C1}⌀⌀⌀⌀⌀⌀⌀⌀{C3}⌀⌀⌀⌀⌀⌀⌀⌀⌀⌀⌀⌀⌀{C4}⌀⌀⌀⌀⌀⌀⌀⌀⌀).
Thus,{C1,C3,C4,C5}=∪{cij1∣cij1∈M1(U,𝒞)} is a granular reduct of 𝒞.
For a maximal elementC7 of SIM(U,𝒞), let c531={C7}, then we get M2(U,𝒞) as follows:
(4.4)(⌀{C5}⌀{C1}⌀⌀⌀⌀⌀⌀⌀⌀{C3}⌀⌀⌀⌀⌀⌀⌀⌀⌀⌀⌀⌀⌀{C7}⌀⌀⌀⌀⌀⌀⌀⌀⌀).
Thus, {C1,C3,C5,C7}=∪{cij2∣cij2∈M2(U,𝒞)} is also a granular reduct of 𝒞.From the above example, we show that the heuristic algorithm can avoid the NP hard problem and generate a granular reduct from the simplified discernability matrix directly. With the heuristic algorithm, the granular reduction theory based on discernability matrix is no longer limited to the theoretic level but applicable in practical usage.


## 5. Conclusion

In this paper, we develop an algorithm by discernability matrixes to compute all the granular reducts with covering rough sets initially. A simplification of discernibility matrix is proposed for the first time. Moreover, a heuristic algorithm to compute a granular reduct is presented to avoid the NP hard problem in granular reduction such that a granular reduct is generated rapidly.



---

*Source: 970576-2012-08-30.xml*