Study of Covering Based Multi Granular Rough Sets and Their Topological Properties

Published Online July 2015 in MECS

Data in real life are mostly imprecise by nature and so the conventional tools for formal modeling, reasoning and computing, which are crisp, deterministic and precise in characteristic are inadequate to handle them. This gives rise to the development of several imprecise models, of which rough sets introduced by Pawlak [4, 5] is one of the most efficient one. It is an excellent tool to capture impreciseness in data in a very effective manner. According to Pawlak, the knowledge of human beings depends upon their capability to classify objects of universes. Since equivalence relations on any universe induce classifications through the equivalence classes associated with them, for mathematical reasons equivalence relations were taken as the basic notions to define the basic rough sets.

A rough set is represented by a pair of crisp sets, called the lower approximation and upper approximation of the set, comprising of elements which definitely and possibly belong to it respectively with respect to the available information.

Later on it was found that the number of equivalence relations is small and so the basic rough sets have been extended in many directions. These extensions actually base on tolerance relations or any such relations which do not require the stringent restrictions of an equivalence relation [11].

The notion of information granularity was introduced by Zadeh in [23] in 1979. However, the label “Granular Computing” was suggested by Lin. Granularity relates to clumpiness of structure while granulation refers to partitioning an object into a collection of granules, with a granule being a clump of objects drawn together by indistinguishability, similarity or proximity or functionality. Granulation may be crisp or fuzzy dense or sparse and physical or mental [24]. The perspectives of granular computing are presented in [20]. From the point of view of granular computing, basic rough set theory deals with a single granulation. However, in some application areas we need to handle more than one granulation at a time and this necessitated the development of multi-granulation [22]. The notion of multi-granular rough sets (MGRS), where at least two equivalence relations are taken for granulation of a universe was introduced in two stages by Qian et al [6] and Qian et al [9]. Using similar concepts, that is taking multiple tolerance relations instead of multiple equivalence relations; incomplete rough set models based on multi-granulations was introduced in [7, 8]. The initial version of multi-granulation is now called the optimistic multi-granular rough sets [6] after the introduction of a similar notion called the pessimistic multi-granular rough sets [9]. Several fundamental properties of these types of rough sets have been studied [17, 18].

Every crisp set X in a universal set U over which an equivalence relation R is defined is associated with a pair of crisp sets called the lower approximation of X with respect to R and the upper approximation of X with respect to R. The lower approximation comprises of those elements of U, which can be definitely be characterized as belonging to X with the knowledge expressed through R and the upper approximation comprises of those elements of U which can possibly be characterized as belonging to X with respect to the knowledge expressed by R. The complement of the lower approximation of X with respect to R, in the upper approximation of X with respect to R is called the boundary of X with respect to R and comprises of the region of uncertainty of X with respect to R.

As measures of accuracy of rough sets the accuracy coefficient was introduced [5]. This notion expresses about the size of the boundary region of X with respect to R. But it does not speak anything about the internal structure of X with respect to R. To describe the later, Pawlak introduced the idea of topological characterization of X with respect to R. It depends upon the properties of the lower and upper approximations of X with respect to R. According to this characterization, there are four kinds of rough sets. As mentioned by Pawlak himself [5], in practical applications of rough sets we need to combine both types of information about the borderline region, that is, of the accuracy measure as well as the information about the topological classification of the set under consideration. Keeping this in mind, Tripathy and Mitra [12] have studied the kinds of rough sets by finding out the kinds of union and intersection of rough sets of different types. This characterization of basic rough sets has been extended to the context of both types of multi-granular rough sets and their properties have been studied [10, 13]. Tripathy and Nagaraju have studied topological properties of multi granular rough fuzzy set in [14] and pessimistic multi granular rough set in [15]. The notion of covers generalize the concept of classification or partition in the sense that the granules in case of covers may not be disjoint where as the granules for classifications must be disjoint. Several types of covering based rough sets have been introduced in literature (see for instance [21]). Following this trend the two types of MGRSs have been extended to introduce four types of covering based multi-granular rough sets (CBMGRS) [1, 2,]. In this paper, we define four kinds of CBMGRSs for each of the four types of CBMGRSs and study their properties by considering their complements, union and intersection. It is observed that there are deviations in many of the cases in this generalized context from those in the basic MGRS context. We establish the possibilities of multiple cases in the tables for topological characterizations by actually showing through examples. The structure of the paper is as follows. In section 2 we present some definitions and notations which are to be used in the sequel. In section 3, we present and discuss the results and state the concluding remarks in section 4. Finally we end up in a section on reference of the materials used for the compilation of this paper.

• II.    Definitions and Notations

• A.    Basics of Rough Set

Let U be a universe of discourse and R be an equivalence relation over U . By U/R we denote the family of all equivalence classes of R , referred to as categories or concepts of R and the equivalence class of an element x ∈ U is denoted by [x] R . By a knowledge base, we understand a relational system K = ( U , P ) , where U is as above and P is a family of equivalence relations over U . For any subset Q ( ≠ φ ) ⊆ P, the intersection of all equivalence relations in Q is denoted by IND(Q) and is called the indiscernbility relation over Q. Given any X ⊆ U and R ∈ IND (K), we associate two subsets,           R X = L { Y ∈ U / R : Y ⊆ X }           and

RX = L{Y∈U/R:YП X ≠ φ} , called the R-lower and R-upper approximations of X respectively. The R-boundary of X is denoted by BNR (X) and is given by BN (X) =RX -RX. The elements of RX are those elements of U, which can certainly be classified as elements of X, and the elements of RX are those elements of U, which can possibly be classified as elements of X, employing knowledge of R. We say that X is rough with respect to R if and only if RX ≠RX , equivalently BN (X) ≠φ. X is said to be R-definable if and only if RX = RX , or BN (X) =φ.

In the view of granular computing (proposed by L. A. Zadeh), an equivalence relation on the universe can be regarded as a granulation, and a partition on the universe can be regarded as a granulation space [23, 24]. For an incomplete information system, similarly, a tolerance relation on the universe can be regard as a granulation, and a cover induced by the relation can be regarded as a granulation space. Several measures in knowledge base closely associated with granular computing, such as knowledge granulation, granulation measure, information entropy and rough entropy. Qian et al put forth the optimistic multigranular rough set model [6] which is based on multiple equivalence relations. Another such model called pessimistic multigranular rough set was introduced in [9]. Some applications of multigranular rough sets to approximate equalities is made in [18, 19] and applications to approximation of classifications is done in [16, 17]. In [8] an extension of MGRS, rough set model based on multi tolerance relations in incomplete information systems is developed.

• B.    Basics of Covering Based Rough Sets

As stated in the introduction, a cover is a generalization of partition on any universe. So, basic rough sets have been extended to this context by defining Covering Based Rough Sets (CBRS) were introduced by many authors. A nice account of these sets from the covering based rough approximations point of view can be found in [21]. We state below these rough set definitions.

Definition 2.1: Let U be a universe and C = {C 1 , C 2 … C n } be a family of non-empty subsets of U that are overlapping in nature. If C=U , then C is called a covering of U . The pair ( U , C) is called a covering approximation space. For any X c U , the covering lower and upper approximations of X with respect to C can be defined as follows

C (X ) = U{ Ci с X , i € 1,2,......, n }                    (1)

C (X ) = U{ Ci n X * ф , i € 1,2,......, n }                  (2)

The pair ( C ( X ), C ( X )) is called covering based rough set associated with X with respect to cover C if C (X ) ^ C ( X ) , i.e., X is said to be roughly definable with respect to C. Otherwise X is said to be C-definable.

Definition 2.2: Given a covering approximation space (U, C) for any x € U , sets mdc (x) and MD (x) are respectively called minimal and maximal descriptors of x with respect to C, mdc (x) = { M € C / x € M and

( V N € C such that x € N and N c M ) => M = N }

It is a set of all minimal covers containing x where a minimal cover containing x be one for which no proper sub cover containing x exists.

MD _c ( x ) = { M € C / x € M and

( V N € C such that x € N and N ^ K ) => M = N }

It is a set of all maximal covers containing x where a maximal cover containing x be one for which no proper super cover containing x exists.

• C.    Basics of Multi Granular Rough Sets

The first instance of defining rough sets from the multigranular point of view is due to Qian et al in [6]. At first this was called only multigranular rough sets and after the other type of multigranular rough sets being defined by the the same set of authors, it was termed as the optimistic multigranular rough sets.

Definition 2.3: Let K= ( U , R ) be a knowledge base, R be a family of equivalence relations, X c U and M , N € R. We define the optimistic multi-granular lower approximation and upper approximation of X in U as

M + N ( X ) = U{ x /[ x ]^ c X or [ x ] c X } (5)

M + N ( X ) = ( M + N ( X^е )) ^е (6)

Another kind of multi-granular rough sets called pessimistic multi-granular rough sets was introduced by Qian et al [9]. Now, they call the above type of multi-granular rough sets as the optimistic multi-granular rough sets.

Definition 2.4: Let K= (U, R ) be a knowledge base, R be a family of equivalence relations, X c U and M , N € R. We define the pessimistic multi-granular lower approximation and upper approximation of X in U as

M * N ( X ) = U{ x / [ x ]_m c Xand [ x ]^ c X }            (7)

M * N ( X ) = ( ( M * N )( X^е )) ^е                      (8)

• D.    Basics of Covering Based Multi Granular Rough Sets

The notions of covering based multigranular rough sets are introduced in [1, 2, 3] and several of their properties were studied. There are several such definitions. But, we shall focus on Multi-granulation rough sets extended to covering approximation space which have been obtained by employing the notions of minimal and maximal descriptors. Four types of CBMGRS have been introduced. These four types of CBMGRS are defined as follows.

Definition 2.5: Let (U, C) be a covering approximation, C , C₂ € C be covers in C, for any X c U, its first type lower and upper approximations with respect to C 1 and C 2 are defined as follows

F _i+C2 ( X ) = { x € U / Q md _{c 1} ( x ) c Xor[\md_c^ ( x ) c X } (9)

F ( X ) = { x € U /(D md_{c i} ( x ))П X ^ ф and (П md c ₂ ( x )) П X ^ ф }  (10)

Definition 2.6: Let (U, C) be a covering approximation, C , C₂ € C be covers in C, for any X c U, its second type lower and upper approximations with respect to C 1 and C 2 are defined as follows

S_Cv(XX ) = { x € U / U md_{C 1} ( x ) c Xor U md c ₂ ( x ) c X }   (11)

S_{C 1+} C ₂( X ) = { x € U /(U md _q( x ))П X ^ ф and (U md c ₂( x ))П X ^ ф } (12)

Definition 2.7: Let ( U , C) be a covering approximation, C ₁, C ₂ €C be covers in C, for any X c U , its third type lower and upper approximations with respect to C 1 and C 2 are defined as follows

T_Ci+c^ ( X ) = { x € U / Q MD _C ( x ) c X or MMD_c ( x ) c X }   (13)

^TC_{X +} C ₂ ( X ) = { x € U /(П MD_{C 1} ( x ))П X ^ Ф and (П MD c ₂ ( x )) П X ^ ф }   (14)

Definition 2.8: Let ( U , C) be a covering approximation, C_x , C₂ € C be covers in C, for any X c U , its fourth or last type lower and upper approximations with respect to C 1 and C 2 are defined as follows

L_Ci+C2 ( X ) = { x € U / U MD _C ( x ) c X or U MD _C2 ( x ) c X }   (15)

L_Cv ( XX ) = { x € U Z(U MD_C ( x ))П X ^ ф and (U MD_{C 2}( x )) П X ^ ф } (16)

• E.    Topological characterization and four kinds of Covering Based Multi Granular Rough Sets

Topology of a set is a concept that specifies details about set regions, namely, interior, exterior and boundary. These details of set regions are determined in terms of lower and upper approximations of a set. Based on the values of these approximations one can categorize a set into four kinds. The kinds of first of the four types of CBMGRS are given as below. Similar definitions can be provided for the other three types of CBMGRSs.

Let K= (U, C ) be a knowledge base, and q, c 2 ^C . Let X c U, then based on the above topological characterization first type of CBMGRS can be categorized into the following four kinds.

If Fc^( (X) * ф and Fc + C2 (X) * U, then we say that X is roughly definable. (K-1)(17)

If FCx+C2 (X) = ф and FCi+C2 (X) * U, then we say that X is internally un-definable. (K-2)(18)

If FC1+C2 (X) * ф and F+C2 (X) = U , then we say that X is externally un-definable. (K-3)(19)

If Fc, + c2 (X) = ф and F^+c2 (X) * U, then we say that X is totally un-definable. (K-4)(20)

• a. Properties of first type of CBMGRS

Several properties of CBMGRSs can be obtained, which are parallel to those of the basic unigranular rough sets. The proof of the following properties is so trivial and given in [20].

Fc 1+C 2 (~ X)=~      (X)(21)

FZ (~ x )=~ Fc 1+c 2 ( x )

Fc 1+C 2 (XUY) О Fc 1+C 2 (X )U F^ (Y)(23)

F^ ( xu y ) о F^( x w F^ (y )(24)

Fc 1+C 2 (XUY) о Fc 1+C 2 (X )П Fc 1+c 2 (Y)(25)

F^ (xn y ) c F+C; ( x )п FC;;:; (y )(26)

• III.    Topological Properties of CBMGRS

It was noted by Pawlak that any fruitful application of rough sets should take care of their two aspects; namely the accuracy measures and the topological criterion. After its inception by Pawlak [5] the study of topological criterion was not attended by researchers until in [12] Tripathy et al studied the kinds of complement of a rough set, kinds of union and intersection of two rough sets. Similar study has been carried for different generalised rough sets including those for multigranular rough sets. A detailed account of these studies can be found in [19].

Topological properties of first type CBMGRS are determined and shown in the four tables given in the following sections. In Table 1 we show different topological characterization kinds of complementation operation of first type CBMGRS. In Table 2 we show the different topological characterization kinds for the result of the union operation between of two first type CBMGRS of some kind. Similarly Table 3 gives the different topological characterization kinds for the result of the intersection operation of two first CBMGRS of some kind. These results will be very much useful and essentially needed for further studies in approximation of classifications and rule generation. Proofs are given for few entries of each table to notify that the entries are right as a sample. Further examples are given to justify that multiple entries are possible under union and intersection of two first type CBMGRS of some kind.

• A.    Kinds of Complement of CBMGRS

The kinds of the complement of a CBMGRS can be derived from those of the CBMGRS. Here we focus on CBMGRS of the first type. The properties for other types are same.

Table 1. Kinds of complement of CBMGRS

X	~X
K-1	K-1
K-2	K-3
K-3	K-2
K-4	K-4

Proof for entry 2:

Suppose X is of kind K - 2 with respect to F_c^ + F_c .

Then from (21) and (22) we can prove that

Thus ~ Xisofkind K - 3.

A similar proof can be given for rest of the entries of the above table.

• B.    Kinds of union of CBMGRS of first type

The kinds of union of two CBMGRSs of different kinds can be obtained from those of the individual ones. In Table 2, we summarize the results. It can be observed that some of the entries in the table are multiple in characters. This shows that we cannot get unique results in these cases. The most flexible one is that in entry (2, 2) where all the four cases are possible.

Table 2. Kinds of union of two CBMGRS of first type

u	Kind of Y with respect to F C 1 + C 2
Kind of X with Respect to F C 1 + C 2		K-1	K-2	K-3	K-4
	K-1	K-1/ K-3	K-1/K-3	K-3	K-3
	K-2	K-1/ K-3	K-1/K-2 / K-3/K-4	K-3	K-3/ K-4
	K-3	K-3	K-3	K-3	K-3
	K-4	K-3	K-3/K-4	K-3	K-3/ K-4

Proof of cell (1, 1):

Let X and Y be of kind K-1. Then we have

!,+C 2 (X) * ф and      (X) * UFc+cSy) * ф and Fc;::; * u

From the properties (23) and (24) we obtain, F c 1 + C 2 ( XUY ) * Ф and F ( ^X ) = U or * U

Thus X Y is either of kind K-1 or K-3 with respect to F C 1 ⁺ F C 2 .

Proof of cell (1, 3):

Let X be of kind K-1 and Y be of kind K-3. Then from the definitions of K-1 and K-3 CBMGRS we have

Given X is of kind K-1. Then we have F _Ci+C2( X ) = ф and F_Ci+(XX ) * U and given that Y is of kind K-3. Then we have F _{c+ C2}( X ) *ф and F C? ( x ) = и .

From the properties (23) and (24) we obtain that F_Cv + C ₂ (X U Y) * ф and F C (X U Y) = U. Thus X IJy is either of kind K-3 with respect to F_; + F_; .

In a similar manner proofs for other entries can be provided.

Example to justify the Proof of cell (1, 1):

Let (U, C) be a covering approximation space, C , C₂ ^ C where

U = { x , , x 2 , X 3 , x 4 }   C , = {{ x , , x 2 },{ x 2 , x 3 , x ₄},{ x 3 , x 4 }}

C2 = {{ xi, X3M x2, x4},{ X,, x2, xJ,{ x4}} mdcx (xi) = {{xi, x 2}}, mdc, (x2) = {{xi, x 2},{ x 2, x3, x4}} mdCx (x3) = {{x3, x4}}, mdCx (x4) = {{x3 , x4}} mdc г (xi ) = {{xi, x3},{ xi, x2 , x4 }}, mdc г (x 2 ) = {{x2 , x4}} mdc2 (x3) = {{xi,x3}}, mdc (x,) = {{x4}}

Case 1: If both X and Y is of kind K-1 then (X Y) will be of kind K-1.

F c i + C 2 ( Y ) = { X i } * ф ,   F c , + ; 2 ( Y ) = { X i } * U

Thus Y is of kind K — 1.

X U Y = { X i , x 2 }

F c i + C 2 ( X U Y ) = { X i , x 2 } * ф , F C ( X U Y ) = { X i , x 2 } * U Thus X U Y is of kind K — 1.

Case 2: If both X and Y is of kind K-1 then (X Y) will be of kind K-3.

F c i + c 2 ( X ) = { X i , X 2 } * ф , F c i + c 2 ( X ) = { X i , X 2 } * U

Thus X is of kind K — i.

F c i + c 2 ( Y ) = { X i , X 3 } * ф ,   F c i + c 2 ( Y ) = {^} * U

Thus Y is of kind K — i.

X U Y = { x , , x 2 , x 3 }

F c i + c 2 ( x u y ) = { x ,, x 2 , x 3 } * ф , F C ; ; ; ; ( x u y ) = { x„ x 2 , x 3 , x 4 } = u ThusXVjYisofkindK — 3.

• C.    Kinds of intersection of CBMGRS of first type

The kinds of intersection of two CBMGRSs of different kinds can be obtained from those of the individual ones. In Table 3, we summarize the results. It can be observed that some of the entries in the table are multiple in characters. This shows that we cannot get unique results in these cases. The most flexible ones are those in entries (3, 3), (3, 4) and (4, 3) where all the four cases are possible.

Table 3. Kinds of intersection of two CBMGRS

n	Kind of Y with respect to F C i + C 2
Kind of X with respect to F с 1 + C 2		K-1	K-2	K-3	K-4
	K-1	K-1/ K-2	K-1 / K-2	K-1/K-2	K-1/ K-2
	K-2	K-1 / K-2	K-2	K-1/ K-2	K-2
	K-3	K-1/ K-2	K-3	K-1/K-2/ K-3/ K-4	K-1/K-2 K-3/K-4
	K-4	K-1/ K-2	K-2	K-1/K-2/ K-3/K-4	K-2/ K-4

Proof for cell (1, 1):

Suppose X and Y both are of kind K-1, then we have

F с (X) = ф and Fc c (X) * U

C i + ; 2 v           г                C i + C 2 ^v

Fr c (Y) = ф and Fc c (Y) * U

; 1 + с 2 ^х                             C i + C 2 ^х

From the properties of (25) and (26) we have

F _C1+C2( XdY ) * ф and

F ;_v + ; ₂ ( X d Y )* ф or F ;_v + ; ₂ ( X d Y )* U

Thus X Y is either of kind K-1 or K-2 with respect to F .

^C 1 ^{+ C} 2

Proof for cell (1, 2):

Suppose X is of kind K-1 and Y is of kind K-2, then we have

F ;_x + с ₂ ( X ) * ф and F ;_x + с ₂ ( X ) * U

F ; , + с 2 ( Y ) = ф and  F ; , + с 2 ( Y ) = U

From the properties of (25) and (26) we have

FCx+;2(XDY) = ф or   FCx+;2(XDY)*ф and

F ;, + ; ₂ ( X U Y ) * U

Thus X Y is either of kind K-1 or K-2 with respect to F .

C 1 + C 2

Example to justify proof of cell (1, 1):

Let (U, C) be a covering approximation space, C , C₂ ^ C where

U = { x 1 ,x 2 , x 3 , x 4 }, C i = {{ x 1 ,x 2 },{ x 2 , x 3 , x 4 },{ x 3 , x 4 }}

C2 = {{ xi, x3},{ x 2, x4},{ xi, x2, x4},{ x4}} mdct (xi) = {{xi, x2}}, mdc, (x 2) = {{xi, x 2},{ x2, x3, x4}} mdC , (x3 ) = {{x3 , x4 }}, mdC , (x4 ) = {{x3 , x4 }} mdC , (xi ) = {{xi , x3 }, {xi , x2 , x4 }} , mdC , (x2 ) = {{x2 , x4 }} mdC2 (x3 ) = {{xi , x3 }}, mdC2 (x4 ) = { {x4}}

Case 1: If both X and Y is of kind K-1 then (X Y) will be of kind K-1.

F C i + C 2 ( X ) = { x i , x 2 } *Ф , F C i + C 2 ( X ) = { x i , x 2 } * U

Thus X is of kind K — i.

F C i + C ₂ ^(Y ) = ^{ x i , x 2 , x 3^} * Ф , F C i + C2( Y^ = ^{ x i , ^x 2 , x 3^} * U

Thus Y is of kind K — i.

X A Y = { x 2 , x 3 }

F C i + C 2 ( X A Y ) = { x 3 } * Ф , F C ^+ C ^ ( X A Y ) = { x 2 , x 3 } * U

ThusXfW is of kind K — i.

Case 2: If both X and Y is of kind K-1 then (X Y) will be of kind K-2.

Let U,C 1 ,C 2 and all minimal descriptors for each element with respect covers C 1 ,C 2 are the same as in case 1.

F C i + C 2 ( X ) = { x 2 } * ф , F C i + C 2 ( X ) = { x 2 , x 3 } * U

Thus X is of kind K — i.

F C i + C 2 ( Y ) = { x„x 3 } * Ф , F C i + C 2 ( Y ) = { x 2 , x 3 } * U

Thus Y is of kind K — i.

F C i + C 2 ( X A Y ) = ф , F C i + C 2 ( X A Y ) = { x 3 } * U

Thus XC\Yis of kind K — 2.

In a similar manner the results for rest of the entries of the table can be obtained.

• V. Conclusion

The basic rough set model introduced by Pawlak as a model of uncertainty depends upon partitions of a universe and also is unigranular from the granular computing point of view. Hence it has been extended in several directions and a recent development is the notion of covering based multigranular rough sets (CBMGRS). Two important characteristics of rough sets which are essential for its use in real life situations are the accuracy measure and the topological characterisation. In this paper, we introduced and studied topological characterisation of four types of CBMGRS. In fact, four kinds of each type of CBMGRS were defined and the kinds of complement of a CBMGRS, union operation of two CBMGRSs and intersection of two CBMGRSs are obtained. The tables show multiple entries, which we established through proofs or counter examples.