On Some Comparison Properties of Rough Sets Based on Multigranulations and Types of Multigranular Approximations of Classifications

Published Online May 2013 in MECS

Rough sets introduced by Z.Pawlak [1] have been established as an efficient model to capture impreciseness in databases. The basic rough set theory introduced by Pawlak depends upon equivalence relations defined on a universe. But from the granular computing point of view it is only single granulation. According to rough set theory a rough set is represented by a pair of crisp sets called its lower and upper approximations. The lower approximation consists of elements of the universe which certainly belong to the set with respect to an equivalence relation where as the upper approximation consists of elements which possibly belong to the set. This includes the certain elements also.

Extending the concepts of single granular rough sets, two concepts of multigranulations have been introduced in the literature, called the optimistic multigranular rough sets and the pessimistic multigranular rough sets. Several properties of these multigranular rough sets have been obtained in several papers [2, 3, 4, 5, 6, 7]. Recently in [7] some algebraic properties were obtained for multigranular rough sets, by the way comparing the two types of multigranular rough sets along with the IND rough set obtained through the intersection of a set of equivalence relations and also the union of a set of tolerance relations in case of incomplete information systems. Also, in [6] some more algebraic properties of multigranular rough sets were obtained, including the cases when the two types of multigranulations reduce to single granulation. As noted by Pawlak [8] the study of approximations of classifications [9] would shed lights on complements in case of multivalued logic. Tripathy et al [10, 11] have unified the four theorems of Busse in the sense that they established two theorems of the necessary and sufficient type from which several results including the theorems of Busse can be derived. Also, their results confirm to the prediction of Pawlak. More importantly it is shown here that there are 11 cases as far as the types of classifications from which only 5 were considered by Busse. However the other types of classifications reduce either directly or indirectly to the five cases considered by Busse. Another important aspect of these results in [10, 11] is the enumeration of possible types [8, 12, 13] of elements in a classification, which is based upon the types of rough sets introduced by Pawlak [8] and carried out further by Tripathy et al [10, 11].

The above results of approximations of classifications from the granular computing point of view depend upon single granulation. In [6] a theorem on multigranular approximation of classifications was established, which provides some sufficient conditions. In this paper we show that the result is both necessary and sufficient type. There are eight relations between the upper and lower multigranular approximations of union and intersections of rough sets. Here, we show that out of these two are actually equalities and we

On Some Comparison Properties of Rough Sets Based on Multigranulations

and Types of Multigranular Approximations of Classifications provide examples to show that proper inclusions hold true in the other six cases. Types of rough sets provide insight into the topological structures of rough sets and also multigranular rough sets. Here, we carry our research in [6] further by establishing a theorem on multigranulations, which extends a corresponding theorem on single granular approximations of classifications.

The organization of the paper is as follows. In section 2, we provide some notations and definitions to be used in the paper. In section 3 we enumerate some properties of multigranulations, which are to be used and also some results are to be proved basing upon them. In section 4, we consider the 8 inclusion properties on multigranulations resulting from the upper and lower multigranulations of union and intersections of rough sets and show that while 2 of them can be replaced by equalities, the other six cannot be done so. In section 6 we revisit the multigranular approximations of classifications and show that a sufficient type result established in [6] is actually a necessary and sufficient type one, thus modifying the corollaries derived from them. We consider the types of classifications in section 7 and show that the results established in [ 11] are extensible to the context of multigranulations. In subsequent sections we present conclusions on the work done in this article and provide a list of references of documents consulted during the preparation of this piece of work.

• II.    Definitions and Notations

• 2.1    Basic Rough set theory

In this section we provide some definitions and notations to be used throughout this paper.

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

[ x an element x e U is denoted by ■*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 indiscernibility relation over Q. Given any X — U and R e IND (K), we associate two subsets, RX = {x e U / [x]R — X} and

RX = { x /[ x Ь П Х * ф } _n

R         , called the R-lo wer and R-upper approximations of X respectively. The R-boundary of X BN (X )

is denoted by      R       and is given л BN (x) = RX - RX .   ,          DV     , by R              . The elements of     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 BNR (X) * ф . X is said to be R-definable if j 1 г RX = RX BN (X) =ф and only if RX = RX or R       .

• 2.2    Rough Set Approximation Based on Multigranulations

The concept of granular computing was introduced by Zadeh. According to this concept 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. As mentioned earlier, from the granular computing point of view, two types of Multigranulations have been defined using rough sets.

The optimistic multigranular rough sets were introduced by Qian [2] as follows. We note that in the beginning there was only one type of Multigranulation and it was not named as optimistic. After the development of a second type of Multigranulation, the first one was called optimistic and the second one was called as pessimistic. We note that we are considering double granulation only. For granulations of higher order, the definitions and properties are similar. The notations used for the two types of Multigranulations were different in the original papers. But we follow the notations used in a recent paper by Tripathy et al [5]. That is we use R+S for optimistic Multigranulation and ^R * S for pessimistic Multigranulation, where R and S are two equivalence relations on U.

Definition 2.2.1: Let K= (U, R) be knowledge base, R be a family of equivalence relations, and R, S e R. We define the optimistic multigranular lower approximation and optimistic multigranular upper approximation of X with respect to R and S in U as

R + S X = { x | [x]R — X or [x]s — X} and

R + S X = ~ (R + S(~ X)).(2)

Definition 2.2.2 : Let K= (U, R ) be a knowledge base,

R be a family of equivalence relations, ^{X — U} and ^R , S ^{e R}. We define the pessimistic multigranular lower approximation and pessimistic multigranular upper approximation of X with respect to R and S in U as

R * S X = { x | [x]^ с X and [x] s с X }        (3)

and

R * S X =   ~ ( R * S (~ X )).                      ₍₄₎

• 2.3    Multigranular Approximations of Classifications

We recall that a classification F = ^{{ X 1, X 2,..., Xn }} of a      universe      U      is      such      that

n

X QX; = ф fori ^ jand U Xl = U .

i ^j                   k = 1   ^k

The approximations (lower and upper) of a classification F was defined by Busse as

RF = { RX1, RX 2,..., RXn }                    z₅.

(R + S)(X) с X с (R + S)(X) (9) (R+S)(ф)= ф = (R+S)(ф), Г (10) (R+S)(U)=U=(R+S)(U) J (R+S)(~X)=~(R+S)(X) (11) (R+S)(X)=RX SX (12) (R + S)(X) = RXUSX (13) (R+S)(X) = (S+R)(X),' ^ (14) (R+S)(X) = (S+R)(X) J (R + S)(X П Y) с (R + S)X П (R + S)Y (15) (R + S)(XUY) э (R + S)X U (R + S)Y (16) (R + S)(XUY) э (R + S)XU(R + S)Y (17) (R + S)(Xn Y) с (R + S)X A(R + S)Y (18) and

RF = { RX1, RX 2,... RXn }

R+SF={R+SX1 ,R+SX2,...,R+SX_n} and                                 f

R+SF={R+SX1,R+SX2,...R+SXn}

R*SF={R*SX1 ,R*SX2,...,R*SXn} and

• III.    Properties of Multigranulations

• 3.1    Properties of Optimistic Multigranular RoughSets

• 3.2    Properties of Pessimistic Multigranular Rough Sets

We present below some properties of multigranulations which shall be used in this paper to establish the results.

The following properties of the optimistic multigranular rough sets were established in [2].

The following properties of the pessimistic multigranular rough sets which are parallel to the properties in 3.1 were established in [3].

(R * S)(X) с X с (R * S)(X)(19)

(R * S) ( ф ) = ф = (R * S)( ф ), (R * S) (U) = U = (R * S)(U) (20)

(R*S)(~ X) =~ (R*S)(X)(21)

(R*S)(X)=RX SX(22)

(R*S)(X) = RXUSX(23)

(R*S)(X)= (S*R)(X), (R*S)(X) = (S*R)(X)(24)

• (R * S)(X П Y) C (R * S)X П (R * S)Y(25)

• (R * S)(X UY) э (R * S)X U (R * S)Y(26)

• (R * S)(X UY) э (R * S)X U (R * S)Y(27)

• (R * S)(X П Y) с (R * S)X П (R * S)Y(28)

• IV.    Comparison Results

The inclusions (25) and (26) have been established in [3]. But we establish below that actually these two inclusions can be replaced with equalities.

Theorem 4.1: Equality holds true in the inclusions (25) and (26).

Proof:

Proof for (25)

Using (23) and property of upper approximation of union of rough sets, we have

R * S ( x и г ) = R ( x U r ) U S ( х U y ) = Rx u Ry U sx u Sy = ( Rx U sx )U( Ry U Sy ) = R * SXUR * S y

Proof for (26)

Using (22) and property of lower approximation of intersection of rough sets, we have

R * S ( X U Y ) = R ( X A Y ) A S ( X A Y )

= rxARYAsxAsy

= ( RX A SX )A( RY A SY )

= R * S XC\R * SY

Theorem 4.2 The inclusion relations in (15) - (18) and (27) and (28) we cannot replace inclusions by equalities.

Proof: We shall provide examples to illustrate that proper inclusions hold in all the above cases.

Let us take

U   ^{ x i , ^X 2 , ^x g , ^X 4 , ^X 5 , ^X 6 , x y , ^X 8^} ,

^U / ^{R   { { X} 1 , ^X 7 ^}, ^{{ X} 2 , ^X 3 , ^X 4 , ^X 5 , ^X 6 ^}, ^{{ X} 8 ^{} }} ,

^U / ^{S   { { X} 1 , ^X 2 ^}, ^{{ X} 3 , ^X 4 , ^X 5 ^} , ^{{ X} 6 , ^X 7 , ^X 8 ^}},

X = { X 4 , x ₅, X 6 , X 7 , X 8 } and Y = { X 2 , x ₃, X 5 , x^ x ₈}.

1          X Q Y = { x. , X. , x. }. _c

Then we have              5  6  8     So,

R + S ( XHY ) = { X 8 }.

R + S ( X ) = { x₆ , x ₇, x ₈} and

^R + S ^{( Y} )  ^{{ x} 2 , ^x 3 , ^x 6 , x ₈^}.

„     R + S ( X )A R + S(Y ) = { X, , X }. c •

Hence,                        68 So, in (15)

proper inclusion holds.

Again, ~ ^X = ^{{ X} 1 ^{, X} 2 ^{, X} 3 ^} and ~ Y = ^{{ X} 1 ^{, X 4, X} 7 ^}.

So,

R + S ( X ) = ~ R + S (~ X ) = ~ { x , x ₂} ^{ x ₃, x 4 , x₅, x ₆, x ₇, x ₈ ^} ,

R + S ( Y ) = ~ R + S (~ Y ) = ~ { x , x ₇}

^{ x ₂, ^X 3 , ^X 4 , ^X₅, ^X 6 , ^X 8 ^} .

X U Y   {x2 , X3, x4, X5 , X6 , X7 , X8} and hence ~ (X U Y) = {x1}.

So,

R + S (~ ( X U Y )) = ф .

R + S ( X U Y ) = U .

Hence, in (16) proper inclusion holds.

Next,

R + S ( X U Y ) = { x ₂, x ₃, x ₄, x ₅, x ₆, x 7 , x 8 } and

R + S ( X ) U R + S ( Y ) = { x ₂, x ₃, x ₆, x ₇, x ₈}.

So, in (17) proper inclusion holds.

Next,

~(XAY) = {X1, x2, x3, x4, x7} and so R + S (~ (X A Y)) = {xx, x2, x3, x7}.

Hence,

R + S ( X A Y ) = ~ R + S (~ ( X A Y ))

{ X 1 , X 2 , X 3 , X 7 } = { X 4 , X 5 , X 6 , X 8 }.

Also, R + S ( X >n R + S ( Y ) = { X 3 , X 4 , X 5 , X 6 , x ₈}. So, in (18) proper inclusion holds.

Now,

R * S ( X U Y ) = { x ₃, x 4 , x ₅, x ₆, x ₈},

R * S ( X ) = { x ₈ } and R * S ( Y ) = ф

So, proper inclusion holds in (27). Finally,

R * S (~( X A Y )) = { X i }.

Hence, R * S ( X A Y ) = { x ₂, x ₃, x ₄, x ₅, x ₆, x ₇, x ₈}.

As

~’ -A^{-    { X} 1 , x ₂, x ₃^}, R * S (~ X ) = ф .

Similarly,

~ Y = { X ,, x ₄, x ₇} and so R * S (~ Y ) = ф .

Hence, R * S ( Y ) = U .

Hence, R * S ( ^X )^П R * ⁵ ( Y ) = ^U = R * S ( ^ХПУ )• So, strict inclusion holds in (28).

This completes the proof.

• V.    Results on Multigranular Approximation of Classifications

We recall that a classification F = { X 1, X 2,..., Xn } of a universe U is such that n

• X- ПХ; = ф fori * jand U Xi = U .

^{i j}                   k = 1 ^k

The approximations (lower and upper) of a classification F was defined by Busse as

RF = {RX1, RX2,..., RXn } and

RF = { RX1, RX 2,... RXn }

For any two equivalence relations R and S over U, the lower and upper optimistic multigranular rough approximations and pessimistic multigranular approximations are defined in a natural manner as

^3 x e R + S (|J X j ) j e I C

^ x e ~ R + S (~ U Xj ) ,X c j

^ x e R + S(U Xj )

j e I

^ R + s (|J X j ) * ф .

j e I

This proves the converse of (i).

Again,

R * S dj X j ) * ф j e I

^ 3x e U such that

^[ X ^] R C U ^X j and ^[ x ^] S c [J X j .

Z       X

Z       X

R+SF={R+SX1 ,R+SX₂,...,R+SX_n} and                                      ■

R+SF={R+SX1,R+SX2,...R+Sxn}

^[ x ^] r A U ^X j = ^ф and [ x ^] s A U X j = ^ф .

R*SF={R*SX1 ,R*SX₂ ,...,R*SX_n} and                                  >

R*SF={R*SX1,R*SX2,...R*SXn}

Thus,

[ x ] R cfu X j

V ^{j e} I C     J

Hence,

J

(. ^

S c U X j .

V j ^e I C    J

C

J

So,

Extending the results of Grzymala Busse, two theorems on approximations of classifications were established by Tripathy et al [ 11]. Out of these two results one was extended fully to the setting of both optimistic and pessimistic multigranulations in [6]. However, only one part of the other was established in the following form.

V j ^e I C

C

So,

That is x e R * S [J Xj

• J C

.

Theorem 5.1: For any i _c n

R + S(UX,) * ф ^ U R + SX. * U.

• (1)           i e I               i e I C

R*S(UXJ * ф ^ U R*SX. * U.

• (ii)       j = ‘   j           >I C          ^j

Here we shall show that even the opposite implications in (i) and (ii) hold true. Thus the second theorem in [6] also holds in its complete form for both types of multigranulations.

Proof of the converses of (i) and (ii) above:

R+S

V j ^e I C

Hence , R * S J X, * U .

VjeIC   J      This proves the converse of (ii).

As a result of the above theorem, the corollaries to the above theorems also change and we state these corollaries in their complete form.

Corollary 5.1: For each

R + S(U X) * ф ^ R + SX- * U.

• (i)         ^{i e I}                             for each^{j e}

R*S(U XJ * ф ^ R*SX. * U.

• (ii)         ^{ieI                     J}        for each^{j e}

Corollary 5.2: For each

(i) R+S X ≠ φ ⇔ R+S( X ) ≠ U. ⁱj ≠ i   ^j

(ii) R*S X ≠ φ ⇔ R*S( X ) ≠ U.

i∈ Nn ,                           j≠i  j i∈N

Corollary 5.3: If there exists        ⁿ such that

R + SX ≠ φ

• (i)           ⁱ        if and only if for each

j( ≠ i) ∈ N n , ^R+SXj ^{≠ U.}

R*SX ≠ φ

• (ii)           ⁱ        if and only if for each

• 6.1    Basic Types of Classifications

j( ≠ i) ∈ Nn,^R*SXj ^{≠ U.}

Type-1: If ^{R ∗ S X ≠ φ andR ∗ SX ≠ U} then we say that X is roughly ^{R ∗ S} -definable.

Type-2: If ^{R ∗ S X = φ andR ∗ SX ≠ U} then we say that X is internally R ∗ S -definable.

Type-3: If R ∗ S X ≠ φ and R ∗ SX = U then we say that X is externally R ∗ S -definable.

Type-4: If ^{R ∗ S X = φ andR ∗ SX = U} then we say that X is totally R ∗ S -definable.

Let R and S be equivalence relations on U and F =

be a classification of U. We extend the five basic types of classifications introduced by Busse [1] as follows:

i ∈ N

Corollary 5.4: For all

R+S X ≠ φ ⇔ R+SX ≠ φ foralli ∈ N .

• (i)   ⁱⁱⁿ

R*S X ≠ φ ⇔ R*SX ≠ φ foralli ∈ N .

• (ii)   ^{ii     n}

• VI. Types of Multigranular Classifications

Classifications are of great interest in the process of learning from examples and deriving rules from classifications generated by single decisions. The types of multigranular approximations of rough sets were introduced in [4] and their properties were studied. We present below the types of rough sets.

Definition 6.1: An optimistic Multi-granulation Rough Set X can be classified into following four types

Type-1: If ^{R + S X ≠ φ andR + SX ≠ U} then we say that X is roughly R+S-definable.

R + S X = φ andR + SX ≠ U

Type-2: If                               then we say that X is internally R+S- definable.

R + S X ≠ φ andR + SX = U

Type-3: If                               then we say that X is externally R+S-definable.

R + S X ≠ φ andR + SX = U

Type-4: If                               then we say that X is totally R+S-definable.

Definition 6.1.1: We say that F is strongly R+S (R*S) definable weak in U if and only if there exists a number i ∈ N         R + S X ( R ∗ S X ) ≠ φ .

• n such that

Definition 6.1.2: We say that F is roughly R+S(R*S)-definable strong in U (or of Type-1) if and R+SX(R∗SX)≠φ only if      ii    for each

Definition 6.1.3: We say that F is internally R+S (R*S)- undefinable weak in U if and only if R+SX(R∗SX)≠φ iifor each     n and there exists j∈N         r+SX (R∗SX )≠U.

• ⁿ such that     ^jj

Definition 6.1.4: We say that F is externally R+S (R*S)-undefinable strong in U (or of Type-2) if and only if

R+SX (R∗SX)≠φ    R+SX(R∗SX)≠U ii  and   iifor i∈N. each     n

Definition 6.1.5:    We say that F is totally R+S

(R*S)-undefinable in U (or of Type-4) if and only if R + S X ( R ∗ S X ) = φ ⁱⁱ  and

R + SX ( R ∗ SX ) = U        i ∈ N .

ⁱⁱ for each    ⁿ

Definition 6.2: An optimistic Multi-granulation

Rough Set X can be classified into following four types

• 6.2    Further Types of Multigranular Classifications

A beautiful analysis of the types of classifications is provided in [11] and it has been found there that only five of these have been considered by Busse, where as all the other six types either reduce directly or transitively to one of these five cases. We see that the logic and properties of lower and upper approximations used there in remains same for both types of multigranulations. So, the conclusions remain same in case of multigranulations. Only for completeness we state below the other six types of classifications.

Definition 6.2.1: We say that F is internally R+S (R*S)-undefinable (weak-1) in U if and only if ³ i such .. . R + SX ( R * SX ) = ф , 3 j , .. . t hat ^{i i} and such that

R + SX ( R * SX ) * U .

Definition 6.2.2: We say that F is internally R+S

(R*S)-undefinable (weak-2) in U if and only if ³ i such

R + S X ( R * S X ) = ф

and

V j R + SX, ( R * SX, ) * U .

Definition 6.2.3: We say that F is internally R+S (R*S)-undefinable (weak-3) in U if and only if V/ R+SX (R * SX) = Ф A  3j    ,     t i       ii     and     such that

R + SX, ( R * SX, ) * U .

Definition 6.2.4: We say that F is of T-4 with respect to R+S (R*S) in U if and only if

R + SX,(R * SX,) = ф           л i        ii       and

_V j R + SX ( R * SX ) * U .

Definition 6.2.5: We say that F is totally R+S (R*S)- undefinable (weak-1) in U if and only if 3i such t R+SX (R * SX) = ф A  3j    .     t that       ii     and     such that

R + SX ( R*SXj ) = U .

Definition 6.2.6: We say that F is totally R+S (R*S)-undefinable (weak-2) in U if and only if

Vz R + SX (R * SX,) = ф     ,   3j     , i       ii     and      such that

R + SX ( R*SXj ) = U .

• 6.3    General Result on Types of Classifications With Respect to Multigranulations

The following theorem provides the number of possibilities from each of the five basic forms of classifications with respect to the types of elements in them. Since the proof is similar to that of the basic one, we avoid it here.

Theorem 6.3.1 : Let F = {X ,X ,...X } be a classification of U. then for n ~ 3, the number of possibilities in terms of types of elements Xi,i  1,2,...n with respect to both the types of multigranulations (optimistic and pessimistic) is 2(n+1).

• VII. Conclusions

The inclusion properties for lower and upper multigranular approximations were found to be inclusions so far. In this paper, we have shown that out of the eight possibilities two for pessimistic multigranulation are equalities and provided examples to show that in the other six cases the inclusions cannot be replaced with equalities. A theorem on types of classifications which was only sufficient type as established in [6] could be proved to be of necessary and sufficient type. This leads to modifications to the results derived from the theorem. An important theorem established in case of single granulation on the number of possibilities of classifications in terms of types of their elements has been extended to the case of multigranulations. This can now be used in generation of multigranular rules from databases, which is untouched so far.