Some Algebraic Properties of Multigranulations and an Analysis of Multigranular Approximations of Classifications

Published Online June 2013 in MECS

As noted by Pawlak[3] the study of approximation of classification would shed lights on complements in case of multivalued logic. Tripathy et al [4, 5] 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. These four theorems are important for deriving rules from information systems[6, 7]. More importantly, it is shown here that there are 11 cases as far as the types of classifications from which only five were considered by Busse. However, the other types of classifications reduce either directly or indirectly to the five cases considered by Busse. Another interesting aspect of the results in[4, 5] is the enumeration of possible types[3, 8, 9] of elements in a classification, which is based upon the types of rough sets introduced by Pawlak[3] and carried out further by Tripathy et al [4, 5].

The above results on approximation of classifications from the granular computing point of view depend upon single granulation. Recently, two types of Multigranulations using rough sets were introduced in the literature. These are termed as optimistic[10] and pessimistic[11] Multigranulation. In this paper, we have attempted to extend the results of Tripathy et al [4, 5] to the Multigranulation context. The study of types of basic rough sets from the optimistic as Multigranulation point of view is done in [12, 13] and from the pessimistic Multigranulation point of view is done in[13]. In this paper, we start with the establishment of some algebraic properties of multigranular rough sets. In fact we find out the conditions under which the two types of Multigranulations reduce to single granulation. Also, sufficient conditions for two inclusions to be equalities in the optimistic Multigranulation case, which are equalities under single granulation are obtained and are shown to be not necessary.

The organization of the rest of the paper is as follows. In section 2 we present some definitions and notations to be used throughout the paper. We state some of the existing properties of multigranulations in section 3 followed by some interesting algebraic properties on multigranulations. Section 4 comprises of some theorems on approximation of classifications in multigranulations. Some measures of quality of multigranular approximations and their properties are presented in section 5. We conclude the work done in the paper in section 6 and provide references to different sources consulted during the compilation of this work in section 7.

• II.    Definitions and Notations

• 2.2 Rough Set Approximation Based on MultiGranulations

2.1 Basic Rough Set Theory

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

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^[10] 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 [^13]. 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.

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 ^{E 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 indiscernibility relation over Q. Given any X ^— U and R ^g IND (K), we associate two subsets,

Definition 2.2.1: Let K= (U, R ) be a knowledge base, R be a family of equivalence relations, ^{X — U} and ^R , ^{S g R}. We define the optimistic multi-granular lower approximation and optimistic multi-granular upper approximation of X with respect to R and S in U as

R + S X = { x | [x]^ — X or [x]5 — X}

and

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

RX = { x g U/[x]_R — X } and RX = { x /[ x ] R A X * ф }

, called the R-lower and R-upper approximations of X respectively. The R-boundary of X is denoted by BN_r ( X ) . BN_r ( X ) = RX-RX _

^R and is given by ^R . The elements of ^{R X} 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 R ⁽ X ) * ^ф . X

Definition 2.2.2: Let K= (U, R ) be a knowledge base, R be a family of equivalence relations, ^{X — U} and ^R , S ^{g r} . We define the pessimistic multi-granular lower approximation and pessimistic multi-granular upper approximation of X with respect to R and S in U as

R * S X = { x | [x] r — X and [x]^ — X}

and

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

is said to be R-definable if and only if ^{R X = RX} _or ^BN R ( ^X )= ф .

2.3 Multi-granular Classifications

Approximations

of

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

X* П X • = ф for i ^ j and U Xv = 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 = { RX_X , IX ,... 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

R+SF={R+SX₁ ,R+SX2,...,R+SX_n} and                                    •

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

R*SF={R*SX₁,R*SX₂,...,R*SX_n} ^and                                     •

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

• III.    Properties of Multigranulations

• 3.1    Properties of Optimistic Multigranular Rough Sets

• 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 [10, 11].

(R + S) (X) о X о (R + S)(X)	(9)
(R+S)( ф )= ф = (К+8)( ф ),
•	(10)
(R+S) (U)= U=(R+S)(U)
(R+S) (~X)=~(R+S)(X)	(11)
(R + S) (X) = R X   S X	(12)
( R + 5 )( X ) = RX U 5X	(13)
(R+S) (X) = (S+R)(X),^	(14)
(R+S)(X) = (S+R)(X)
(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)(X П Y) о (R + S)X П (R + S)Y(18)

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

(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) о (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)

• 3.3    Algebraic Properties of Multigranulations

In this section we establish some algebraic properties of both types of Multigranulations. It is interesting to find conditions or the cases under which the two types of Multigranulations reduce to single granulation rough sets. In this section we find out the solutions to this problem.

Theorem 3.3.1: Let R and S be two equivalence relations on U and ^о . Then

R+SX=RXandR+SX=RX when S = U x U                       (29)

R*SX= RXandR*SX= RX when S = {(x, x) |x G U }.                     (30)

Proof of (29)

^{[ X} lv = ^U .

In     this      case         ^S          So     that

[x]g о X is not satisfied for any X other than U itself.

So, if ^X ^ ^U then ^[ x ^{] S £} X is not satisfied for any x in U. Hence R + SX =       { ^x /[ ^{x ]} R ^£ X or

^[ x ^] S £ X } reduces to { ^{x /[ x ]} R ^£ X } = RX .

Д. R + SX=~R + S(~X) =~R(~X) = RX .

Proof of (30)

T                          [xlc = {x}, Vx e U..

In this case       ^S                 So that

[x] _c £ X is satisfied for any x e X.

^S                         Hence,

R * SX = {x / [x^ с X and [x]5 £ X}     reducest0

{x/[x]p £ X} RY A R^SX^X.

l jR     j = RX. As —S £  , it is not necessary to consider elements x outside X.

_Also R * SX = ~ R * S (~ X ) = ~ R (~ X ) = RX .

The proofs of the following properties of Multigranulations follow from their definitions:

So, clearly the condition given is sufficient for the equality to hold. As expected, it follows from Theorem 3.3.1 and the following steps that the equality holds when S = ^{U x U} .

R + S ( X U Y ) = R ( X U Y ),      u      с-    1

, as above. Similarly,

R + SX = RX _and R + SY = RY

.

Again,

. So, the condition is not necessarily true.

R X S Y = Uand R Y S X= U

Theorem 3.3.4:                              is a sufficient but not necessary condition for

R+S (X Y) = R+S X R +S Y.

Theorem 3.3.2: With the same notations as in Theorem 3.3.1, the following properties are satisfied by ‘+’ and ‘*’

R + S X = S + R X and R + SX = S + RX

(R + S) + TX = R + (S + T)X   , and

( R + S ) + TX = R + ( S + T ) X

Proof: We note that the following property hold for optimistic Multigranulation:

R + S (X Y) =

R +S X R + S Y ( R X S Y) ( R Y S X)

So, the condition is clearly sufficient for the equality to hold. As expected, it follows from Theorem 3.3.1 and the following steps that equality holds when S = ^{U x U .}

R * SX = S * RX and R * SX = S * RX have     R+S(X Y)=     R(X Y),

( R * S ) * TX = R * ( S * T ) X ^_d

( R * S ) * TX = R * ( S * T ) X

Next, we prove two theorems which provide sufficient conditions for equality to hold in two inclusions in the Multigranulation case, which were true without any condition in the single granulation case.

Theorem 3.3.3: ["J = * "nd [ R^ n SX J = * is a sufficient but not necessary condition _f R + S ( X U K ) = ( R + SX )U( R + SY ) for                                                 .

Proof: We note that the following property hold for optimistic Multigranulation:

R + S ( XV3Y ) = ( R + SX ) U ( R + SY )U

[ RX SY ]  [ RY SX ]

R + SX = RXand R + SY = RY. ^ (RXUSY) ^ RX and (RY USX) ^ RY. _c .1 -1,1 1 1 г•

• IV.    Theorems on Approximations of Classifications in Multi-Granulations

We use the notation in this section as

Nn = {1, 2,3,.... n }

For any I c N_n I C denotes the complement .

of I in Nn.

Theorem 4.1: For any I ⊂ Nn

---- и X_i

• ^{R + S} ( ^{i ∈ I}    ) = U, if and only if

• R+S( j∈IC  j ) = φ.(37)

R ∗ S ( X_i ) = U

• i ∈ I             if and only if

R ∗ S (      X ) = φ .

• j∈IC j(38)

Proof: We only prove (37). The proof of (38) is similar. Only instead of (1) we have to use (2).

R*S(X )=Uifandonlyif R*S ( X )= φ .

• (ii)            ij∈ij

Proof: Taking I = {i} in Theorem 4.1 we get these results i∈N

Corollary 4.3: For each

X_j (i) ^R+S ( X i ) = φ if and if ^R+S (^{j ≠ i}   ) = U.

R*S (X ) = φ ifandonlyif ^R*S( _{j ≠ i}^Xj^{) = U.}

The proof follows from the equivalences below.

• _ и X_j

^{R + S} ( ^{j ∈ IC}    ) = φ

⇔ ^{R + S} ( U \ ^{i ∈ IXi} ) = φ

— и ^X

⇔    ^{~ R + S} ( ^{i ∈ I  i} ) = φ (by (1))

и X_i

⇔ ^{R + S} ( ^{i ∈ I} ) = U

Corollary 4.1:     Let F, U, R and S be as in section 3.

• (i)    If ^{R + S} ( i ∈ I^Xi ) = U, then ^{R + S} X j = ^φ for each j ∈ I^C.

IfR*S( и X ) = Uthen R+S (X ) = φ

• (ii)     ^{i ∈ I ij}

C foreachj ∈ I .

Proof: Taking I = {i}^C in Theorem 4.1 we get this result.

Coro llary 4.4: (i) If there exists ^{i ∈ Nn} such that

R+SX =U            j( ≠ i) ∈ N , ^{R+S X}j ^{= φ .}

i     then for each i∈ N          R *SX = U

(ii)If there exists       ⁿ such that         ⁱ

R*S X = φ .

for each j(≠ i) ∈Nn,j

Proof: (i) From Corollary 4.2,

R+SX =U⇒R+S( X )=φ ij≠i

⇒ R + S X = φ ; for each j ≠ i.

Proof of (ii) is similar.

Proof: By Theorem 4.1 and from the hypothesis we get

_  _ и X_j

R + S   ^C      φ

( j∈       ) =    . Now, as и Xj

R+SXj ⊆ R+S( j∈I     ) for each j ∈ IC the conclusion in (i) follows.

Proof of (ii) is similar.

Theorem 4.2: For any I ⊂ N ,

I I X.             U R + S

• (i)    R + S ( ^{i ∈ I} ) ≠ φ ⇒   ^{j ∈ IC}

  X j ^≠ U.

  
  

R*S( и X ) ≠φ⇒   R*SX ≠ j∈I jj∈IC          j

• (ii)

  U.

  
  

Proof: By (16)

Corollary 4.2: For each ^{i ∈ Nn} ,

Xj

(i)R+S( Xi) = U if and only if R+S(j∈i) =

R+S( U X )≠φ⇒ j∈I

∃x ∈ Usuch that [x]  ⊆ и X or[x]S ⊆ j∈I jj∈I

X.

[x]_R А(.U X )= φ or[x]_S  ( X )= φ .

^R    j ∈ I^Cjj ∈ I^Cj

Thus

CC

[x]_R ⊆ (    X ) or[x]_S ⊆ (    X ) .

j ∈ I^CjS     j ∈ I^Cj

So,

R*SX ≠ U.

x ∈ R+S ( X )^C. j ∈ I^C

Hence,                         This implies that x∉(R+S(    Xj)C)C.

j∈IC x∉R+S(   X ).

So,               ^{j ∈ I}          This proves that

R + S(    X ) ≠ U.

j ∈ I^C

The proof of (ii) is similar.

Corollary 4.5: For each

n

,

R+S ( X ) ≠ φ

• (i)    If        ^{i ∈ I}         then

each ^{j ∈ I} .

R + SX ≠ U for

R*S ( X ) ≠ φ

• (ii)    If       ^{i ∈ I}          then

each ^{j ∈ I} .

R*SX ≠ U j       for

R+S(   X ) ≠ U.

Proof: We have by Theorem 4.2      ^{j ∈ I}

Hence,as

R +S(    X ) ⊇ R +S(X ), ∀ j ∈ I^C, itfollows

Cjj

C thatR+SX ≠ Uforeachj ∈ I .

Proof of (ii) is similar.

Corollary 4.6: For each ^{i ∈ Nn ,}

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

(ii)R*SX ≠φ⇒ R*S( X ) ≠ U. ij≠i i∈N

Corollary 4.7: If there exists        ⁿ such that

^{R +S X ≠} φ                    j( ≠ i) ∈ N ,

• (i)           i        then for each

R + SX ≠ U.

R*S X ≠ φ             j( ≠ i) ∈ N ,

• (ii)        i      then for each

Proof:     (i) From corollary 4.6 we get

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

R+S( X ) ⊇ R+SX ,forj ≠ i;

So, as    j≠i jj we get the result. Proof of (ii) is similar.

Corollary 4.8: If for all ^{i ∈ Nn,}

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

• (i)

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

• (ii)          iin

Proof: As

R + S X ≠ φ for every i ∈ N_n,itfollowsfrom

R+S( X ) ⊇R+SX (k≠i)     R+S( X )≠φ j≠i jkthat     j≠i j

Thus from Corollary 4.7 it follows that

R + SX ≠ Uforalli ∈ N_n.

Proof of (ii) is similar.

• V. Some Properties of Measures of Uncertainty

• 5.1    Accuracy of Multigranular Approximations

In this section we introduce two measures, which describe inexactness of multigranular approximate classifications. These are extensions of the corresponding concepts used in the single granulation case.

We follow the same notations as used in the previous sections.

The accuracy of optimistic multigranular approximation of F by R and S is defined as

n

∑ card(R + SX )

• в r+s (F) = i=--------- .

∑ card(R + SX )

i=1              i                  (39)

The accuracy of pessimistic multigranular approximation of F by R and S is defined as

Some Algebraic Properties of Multigranulations and

an Analysis of Multigranular Approximations of Classifications

n

∑ card(R *SX ) i=1               ⁱ

P r*S ^(F)   n      ----

∑ card(R *SX )

i=1               ⁱ

Theorem 5.3.1: For any classification F in U,

(i)F is (R+S)-definable if and only if

P r+s (^f) = Y r+s (F) = 1.

As in the single granulation case, this measure expresses the percentage of possible correct decisions when classifying objects employing the knowledge of R and S taken together (optimistic or pessimistic manner).

(ii)F is ( ^{R * S} )-definable if and only if

P r*s ^{(f) y} r*s ^(f)  1-

5.2 Quality of Multigranular Approximations

The quality of optimistic multigranular approximation of F by R and S if given as

^Y R+S ^(F )

n

∑ card(R + SX) i=1

card(U)

Theorem 5.3.2: For any classification F in U and equivalence relations R and S on U,

_(i)0 ^ P r+s (F) ^ Y r+s (F) ^ 1.

_(ii)0 ^ P r*s (F) ^ Y r*s (F) ^ 1.

The quality of pessimistic multigranular

approximation of F by R and S if given as

Y r*s ( ^F)

n

∑ card(R * SX) i=1

card(U)

As in the single granulation case, this measure expresses the percentage of objects which can be correctly classified to classes of F employing the knowledge of R and S taken together (optimistic or pessimistic manner).

5.3 Theorems on Approximations of Classifications

Some properties of these measures were established in[5]. We find that the same proofs work for both the multigranular cases. So, we only state below the results without any proof. We need the following additional definition.

VI. Conclusions

In this paper, we have introduced the notions of multigranular approximations of classifications for both types of Multigranulations. This is important from the rough set point of view as we use classifications for basic Multigranulations. We have established theorems, which are extensions of their single granulation versions. However, one of these results could not be extended in its full generality. We have proved some algebraic properties of Multigranulations, one of which answers the cases when Multigranulation reduces to single granulations. This result is important from the point of view that one would be interested to check the validity of conclusions obtained from Multigranulations by reducing to established results in the single granulation case. Also, we have illustrated this feature by trying to establish two equalities, which hold in the single granulation case but are not true in the Multigranulation case.

Definition 5.3.1: (i) We say that a classification F is (R+S)-definable if and only if

R+S F=R+SF

or equivalently

R+S X = R+SX ;i = 1, 2,...n.

+S _i+S _i;      ,  ,...n.              ₍₄₄₎

(ii) We say that classification F is ( ^{R * S} )-definable if and only if

R*S F=R*SF

or equivalently

R*S X = R*SX ;i = 1, 2,...n.

S _iS _i;       ,  ,...n.                ₍₄₆₎