UN CO RR EC TE D PR O O F Intuitionistic fuzzy rough sets: at the cross- roads of imperfect knowledge Chris Cornelis, Martine De Cock and Etienne E. Kerre Department of Applied Mathematics and Computer Science, Ghent University, Fuzziness and Uncertainty Modelling Research Unit, Krijgslaan 281 (S9), B-9000 Ghent, Belgium E-mail: {chris.cornelis, martine.decock, etienne.kerre}@rug.ac.be Abstract: Just like rough set theory, fuzzy set theory addresses the topic of dealing with imperfect knowledge. Recent investiga- tions have shown how both theories can be combined into a more flexible, more expressive framework for modelling and processing incomplete information in information systems. At the same time, intuitionistic fuzzy sets have been proposed as an attractive extension of fuzzy sets, enriching the latter with extra features to represent uncertainty (on top of vagueness). Unfortunately, the various tentative definitions of the concept of an ‘intuitionistic fuzzy rough set’ that were raised in their wake are a far cry from the original objectives of rough set theory. We intend to fill an obvious gap by introducing a new definition of intuitionistic fuzzy rough sets, as the most natural generalization of Pawlak’s original concept of rough sets. Keywords: rough set theory, intuitionistic fuzzy set theory, L-fuzzy set theory, incomplete information, lower and upper approximation 1. Introduction As a new trend in the attempts to combine the best of several worlds, very recently all kinds of suggestions for approaches merging rough set theory and intuitionistic fuzzy set theory have started to appear. The present evolution vividly reminds us of the origin of fuzzy rough set theory, as the (so far) happy marriage of fuzzy set theory and rough set theory. A remarkable difference, however, is that in the latter case a long engagement period with intense discussions concerning the relation between fuzzy set theory and rough set theory preceded the marriage, (and in a way is still going on, simultaneously with the research on the new hybrid theory). So far, this comparison stage seems very limited for the combination of intuitionistic fuzzy set theory and (fuzzy) rough set theory. As far as we know, only Çoker (1998) went into the matter by claiming that fuzzy rough sets are intuitionistic fuzzy sets (Chakra- barty et al., 1998; Samanta & Mondal, 2001; Jena & Ghosh, 2002; Rizvi et al., 2002), which appears to be shattering the dream of a new hybrid theory. On the other hand, there exist many views on the notion ‘rough set’ which can be grouped into two main streams. Several suggested options for fuzzification have led to an even greater number of views on the notion ‘fuzzy rough set’. Typically, under the same formal umbrella, they can be further generalized to the notion ‘L-fuzzy rough set’ where the membership degrees are taken from some suitable lattice L which is not necessarily the unit interval. On top of this, there exist semantically different interpretations of intuitionistic fuzzy set theory (which is a special kind of L-fuzzy set theory). Needless to say, when trying to compare and/or to combine rough set theory, fuzzy set theory and intuitionistic fuzzy set theory, one finds oneself at a complicated crossroads with an abundance of possible ways to proceed. The aim of this paper is to provide the reader with a road map. We do this by mapping out research results obtained so far in the literature, as well as by exploring by our- selves a very important road which was virgin territory until now. However, before we can prepare a hybrid theory, it is absolutely necessary to check the origin of all ingredients, for they can have an important influence on the flavour of the resulting product! For this reason we start the paper with a short overview of all set theoretical models involved (Section 2). Making such a study forces us into thinking about relationships between them. Staying within the scope of the paper, we will only focus on intuitionistic fuzzy set theory versus fuzzy rough set theory (Section 3). After a critical examination of the added value of a hybrid intuitionistic fuzzy rough set theory, in Section 4 we present an overview of existing approaches (all originated independently from the others). Finally we fill an obvious gap by a very natural generalization of Pawlak’s original concept of a rough set. Article_______________________________________ Journal: EXSY H Disk used ED: Ramesh: Pgn by: solly Article : 02005003 Pages: 10 Despatch Date: 8/8/2003 260 ________________________________________________________________ Expert Systems, November 2003, Vol. 20, No. 5 BWUK EXSY 02005003.PDF 08-Aug-03 16:38 226131 Bytes 10 PAGES UN CO RR EC TE D PR O O F 2. Short overview of some set theoretical models 2.1. Rough set theory Rough sets, remarkably enough, are not a uniquely defined notion. A very accurate classification of various ap- proaches to definitions was given by Yao (1996). For our purposes, it is sufficient to distinguish between two main streams in the literature, denoted ‘Pawlak rough sets’ and ‘Iwinski rough sets’, respectively; both come with their own particular perception of the notion ‘rough set’. Pawlak rough sets The first stream was initiated by Pawlak (1982) who launched rough set theory as a framework for the construction of approximations of concepts when only incomplete information is available. The available information consists of a set A of examples (a subset of a universe X, X being a non-empty set of objects we want to say something about) of a concept C, and a relation R in X. R models ‘indiscernibility’ or ‘indistinguishability’ and therefore generally is a tolerance relation (i.e. a reflexive and symmetrical relation) and in most cases even an equivalence relation (i.e. a transitive tolerance relation). In this paper we will use R-foresets to denote equivalence classes. The R-foreset of an element y of X is the set Ry ¼ {x|(x, y)AR}. The couple (X, R) is called an approximation space. Rough set analysis makes statements about the membership of some element x of X to the concept C of which A is a set of examples, based on the indistinguishability between x and the elements of A. To arrive at such statements, A is approximated in two ways. The lower and upper approximations of A in (X, R) are respectively the following subsets of X: A ¼ fyjy 2 X and Ry � Ag �AA ¼ fyjy 2 X and Ry \ Ag The underlying meaning is that �AA is the set of elements possibly belonging to the concept C (weak membership), while A is the set of elements necessarily belonging to C (strong membership); for y belongs to A if all elements of X indistinguishable from y belong to A (hence there is no doubt that y also belongs to A), while y belongs to �AA as soon as an element of A is indistinguishable from y. If y belongs to the boundary region �AA=A, then there is doubt, because in this case y is at the same time indistinguishable from at least one element of A and at least one element of X that is not in A. A set A is called definable if A ¼ �AA (Radzikowska & Kerre, 2002). The existing variety in terminology on this concept of definability might indicate the high importance individual researchers attach to it. Thiele for instance uses the term ‘R-exact’ as a synonym for ‘definable’ (see Thiele, 1998). Pawlak (1982) defines a ‘composed set’ as a finite union of equivalence classes. In 1985 he generalizes this definition to any union of equivalence classes; it can be verified that this notion of composed set coincides with that of definable set. Still other terms to denote the same notion are mentioned in Iwinski (1987). A similar phenomenon occurs concerning the definition of the concept ‘rough set’: some authors say that a set A in X is a ‘rough set’ if A 6¼ �AA (see for example Komorowski et al., 1999). Hence they call a set ‘rough’ if the boundary region is not empty, i.e. if there is at least one object which cannot be classified with certainty as a member of the concept, nor as a member of its complement. Pawlak (1982), on the other hand, originally defined a rough set (A1, A2) as the class of all sets that have A1 and A2 respectively as lower and upper approximations. This convention is also adopted by Thiele (2001). Still others call (A1, A2) a rough set (in (X, R)) as soon as there is a set A in X such that A ¼ A1 and �AA ¼ A2 (see for example Radzikowska & Kerre, 2002); (A1, A2) is then also called the rough set of A. Without loss of generality of the discussion, we follow the latter approach. Rough set theory is strongly related to Gentilhomme’s (1968) flou set theory. A flou set in a universe X is a couple (A1, A2) satisfying A1DA2DX. The first coordinate A1 is called the certain area, the second coordinate A2 the area of maximal extension and A2}A1 the flou zone (or vague zone). The idea of dividing the universe into three areas is a very strong linkage between flou sets and rough sets. One could say that with the introduction of rough set theory an important next step forward was made, providing a semantically justifiable and computationally feasible way to construct the three areas involved, by approximating a set A by its lower and upper approximations. One can verify that for a reflexive relation R A � A which justifies the statement that all rough sets are flou sets. Interestingly enough, given a flou set (A1, A2) in X, it is not always possible to find an approximation space (X, R) such that (A1, A2) is a rough set in (X, R). To illustrate this, we rely on the fact that if the relation R is symmetrical then Að Þ � A � ðAÞ Example 1 Suppose that A2 contains one more element than A1, i.e. A2 ¼ A1,{x0}, x0 in X \A1. If (A1, A2) is the rough set of A then A1 ¼ A � A � A ¼ A2 Hence either A1 ¼ ACA2 or A1CA ¼ A2. In the first case A1 ¼ A implies A ¼ A. Hence ðAÞ ¼ �AA and, because of the symmetry of R, �AA DA, which contradicts AC �AA ¼ A2. In the second case a similar line of reasoning leads to the contradiction ADA. Iwinski rough sets The second stream in the literature was initiated by Iwinski (1987), who did not use an equivalence Expert Systems, November 2003, Vol. 20, No. 5 ________________________________________________________________ 261 EXSY : 02005003 BWUK EXSY 02005003.PDF 08-Aug-03 16:38 226131 Bytes 10 PAGES UN CO RR EC TE D PR O O F relation as an initial building block to define the rough set concept. Instead he departed from a complete subalgebra B of the Boolean algebra P(X) of subsets of X and defined a rough set as a pair of sets (A, B) with A in B, B in B and ADB. At the mathematical level this approach coincides with the one outlined by Pawlak (B being the class of definable sets) (Iwinski, 1987). At the semantic level there is a significant difference: although Iwinski’s formulation provides an elegant mathematical model (Yao, 1996), the absence of the equivalence relation and the set of examples to be approximated makes it hard to interpret. Despite its short history, rough set theory has already been applied successfully in many knowledge-based systems. We refer to (Komorowski et al., (1999) for an extensive overview of achievements in the field. 2.2. L-fuzzy set theory From fuzzy setsy Fuzzy set theory was introduced by Zadeh (1945) as a framework for modelling the vagueness present in everyday life (and in particular, in natural language). A fuzzy set A in a universe X is characterized by an X-[0, 1] mapping, usually denoted by A or by mA, called the membership function. For all x in X, A(x)corresponds to the degree to which x belongs to A. While fundamental research on the theory is still very topical, the application of the fuzzy set theoretical representation of vague concepts also has many working applications nowadays. The rapid growth of the series Studies in Fuzziness and Soft Computing (Kacprzyk, 1992–2002), consisting of both monographs and edited volumes, is a striking illustration of the continuous evolution and the high number of achievements in this field. y to L-fuzzy sets The mapping of elements of the universe to the interval [0, 1], however, implies a crisp, linear ordering of these elements, making [0, 1]-valued fuzzy set theory inadequate to deal with incomparable information. From the beginning therefore some attention has been paid to other partially ordered sets as well. In 1967 Goguen formally introduced the notion of an L-fuzzy set with a membership function taking values in a lattice L. In this paper we assume that (L, rL) is a complete lattice with smallest element 0L and greatest element 1L. An L-fuzzy set A in a universe X is a mapping from X to L, again called the membership function. The L-fuzzy set A is said to be included in the L-fuzzy set B, usually denoted by ADB, if A(x)rL B(x) for all x in X. An L-fuzzy set R in X � X is called a binary fuzzy relation on X. For all x and y in X, R(x, y) expresses the degree to which x and y are related through R. For every y in X, the R-foreset of y is an L-fuzzy set in X, denoted as Ry and defined by Ry(x) ¼ R(x, y) for all x in X. Logical operators L-fuzzy set theoretical operations such as complement, intersection and union can be defined by means of suitable generalizations of the well-known connectives from Boolean logic. Negation, conjunction, disjunction and implication can be generalized respectively to negator, triangular norm, triangular conorm and implicator, all mappings taking values in L. More specifically, a negator in L is any decreasing L-L mapping N satisfying N(0L) ¼ 1L. It is called involutive if N(N(x)) ¼ x for all x in L. A triangular norm (t-norm for short) T in L is any increasing, commutative and associative L 2-L mapping satisfying T(1L, x) ¼ x, for all x in L. A triangular conorm (t-conorm for short) S in L is any increasing, commutative and associative L 2-L mapping satisfying S(0L, x) ¼ x, for all x in L. The N- complement of an L-fuzzy set A in X as well as the T- intersection and the S-union of L-fuzzy sets A and B in X are the L-fuzzy sets coN(A), A-T B and A,S B defined by coNðAÞðxÞ ¼ NðAðxÞÞ A \T BðxÞ ¼ TðAðxÞ; BðxÞÞ A [S BðxÞ ¼ SðAðxÞ; BðxÞÞ for all x in X. The dual of a t-conorm S in L with respect to a negator N in L is a t-norm T in L defined as T(x, y) ¼ N(S(N(x), N(y))). An implicator in L is any L2-L mapping I satisfying I(0L, 0L) ¼ 1L, I(1L, x) ¼ x for all x in L. Moreover we require I to be decreasing in its first, and increasing in its second, component. If S and N are respectively a t-conorm and a negator in L, then it is well known that the mapping IS,N defined by IS;Nðx; yÞ ¼ SðNðxÞ; yÞ is an implicator in L, usually called S-implicator (induced by S and N). Likewise, if T is a t-norm in L, the mapping IT defined by ITðx; yÞ ¼ supfljl 2 L and Tðx; lÞ �L yg is an implicator in L, usually called the residual implicator (of T). The partial mappings of a t-norm T in L are sup- morphisms if T sup i2I xi; y � � ¼ sup i2I Tðxi; yÞ for every family I of indexes. Examples It is easy to verify that the meet and the join operation on L are respectively a t-norm and a t-conorm on L. We denote them by TM and SM respectively. Also A-B is a shorter notation for A-TMB, while A,B corresponds to A,SMB. The [0, 1]-[0, 1] mapping Ns defined as Ns(x) ¼ 1 � x, for all x in [0, 1], is a negator on [0, 1], often called the standard negator. For a [0, 1]-fuzzy set A, coNsðAÞ is commonly denoted by co(A). Table 1 depicts the values of well-known t-norms and t-conorms on [0, 1], for all x and y in [0, 1]. The first column of Table 2 Q1 Q2 262 ________________________________________________________________ Expert Systems, November 2003, Vol. 20, No. 5 EXSY : 02005003 BWUK EXSY 02005003.PDF 08-Aug-03 16:38 226131 Bytes 10 PAGES UN CO RR EC TE D PR O O F shows the values of the S-implicators on [0, 1] induced by the t-conorms of Table 1 and the standard negator Ns, while the second column lists the values of the corresponding residual implicators. Finally we mention that an L-fuzzy relation R on X is called an L-fuzzy T-equivalence relation if it is reflexive (R(x, x) ¼ 1L, for all x in X), symmetrical (R(x, y) ¼ R(y, x), for all x and y in X) and T-transitive (T(R(x, y), R(y, z))rR(x, z), for all x, y and z in X). When L ¼ {0, 1}, L-fuzzy set theory coincides with traditional set theory, in this context also called crisp set theory. {0, 1}-fuzzy sets, {0, 1}-fuzzy relations,y are usually also called crisp sets, crisp relations,y. When L ¼ [0, 1], fuzzy set theory in the sense of Zadeh is recovered. [0, 1]-fuzzy sets, [0, 1]-fuzzy relations,y are commonly called fuzzy sets, fuzzy relations,y. Furthermore it is customary to omit the indication ‘in [0, 1]’ when describing the logical operators, and hence to talk about negators, triangular norms etc. Yet another interesting choice for L gives rise to intuitionistic fuzzy set theory, as described below. 2.3. Intuitionistic fuzzy set theory A particularly interesting lattice of membership degrees leads to intuitionistic fuzzy set (IFS) theory (Atanassov, 1999). This theory basically defies the claim that, from the fact that an element x ‘belongs’ to a given degree (say mA(x)) to a fuzzy set A, it naturally follows that x should ‘not belong’ to A to the extent 1 � mA(x), an assertion implicit in the concept of a fuzzy set. On the contrary, IFSs assign to each element x of the universe both a degree of membership mA(x) and one of non-membership nA(x) such that mA(x) þ nA(x)r1, thus relaxing the enforced duality nA(x) ¼ 1 � mA(x) from fuzzy set theory. Obviously, when mA(x) þ nA(x) ¼ 1 for all elements of the universe, the traditional fuzzy set concept is recovered. By complementing the membership degree with a non- membership degree that expresses to what extent the element does not belong to the IFS, such that the sum of the degrees does not exceed 1, a whole spectrum of knowledge not accessible to fuzzy sets can be accessed. The applica- tions of this simple idea are manyfold indeed: it may be used to express positive as well as negative preferences; in a logical context, with a proposition a degree of truth and one of falsity may be associated; within databases, it can serve to evaluate the satisfaction as well as the violation of relational constraints. More generally, IFSs address the fundamental two-sidedness of knowledge, of positive versus negative information, and by not treating the two sides as exactly complementary (like fuzzy sets do), a margin of hesitation is created. This hesitation is quantified for each x in X by the number pA(x) ¼ 1 � mA(x) � nA(x). IFSs can be considered as special instances of L-fuzzy sets (Deschrijver et al., 2002). Let (L*,rL*) be the complete, bounded lattice defined by L� ¼ fðx1; x2Þ 2 ½0; 1�2jx1 þ x2 � 1g ðx1; x2Þ �L� ðy1; y2Þ , x1 � y1 and x2 � y2 The units of this lattice are denoted 0L* ¼ (0, 1) and 1L* ¼ (1, 0). For each element xAL*, by x1 and x2 we denote its first and second components, respectively. An IFS A in a universe X is a mapping from X to L*. For every xAX, the value mA(x) ¼ (A(x))1 is called the membership degree of x to A; the value nA(x) ¼ (A(x))2 is called the non-member- ship degree of x to A; and the value pA(x) is called the hesitation degree of x to A. Just as L*-fuzzy sets are called IFSs, L*-fuzzy relations are called IF relations. Logical operators The terms IF negator, IF t-norm, IF t- conorm and IF implicator are used to denote respectively a negator in L*, a t-norm in L*, a t-conorm in L* and an implicator in L*. A t-norm T on L* (respectively t-conorm S) is called t-representable (Deschrijver et al., 2002) if there exists a t-norm T and a t-conorm S on [0, 1] (respectively a t-conorm S0 and a t-norm T0 on [0, 1]) such that, for x ¼ (x1, x2), y ¼ (y1, y2)AL*, Tðx; yÞ ¼ ðTðx1; y1Þ; Sðx2; y2ÞÞ Sðx; yÞ ¼ ðS0ðx1; y1Þ; T0ðx2; y2ÞÞ T and S (respectively S0 and T0) are called the representants of T (respectively S). Finally, denoting the first projection mapping on L* by pr1, we recall from Deschrijver et al., (2002) that the [0, 1]-[0, 1] mapping N defined by N(a)¼ pr1N(a, 1� a) for all a in [0, 1] is an involutive negator on [0, 1], if N is an involutive negator on L*. N is called the negator induced by N. Furthermore N(x1, x2)¼ (N(1� x2),1� N(x1)), for all x in L*. Examples The standard IF negator is defined by Ns(x) ¼ (x2, x1), for all x in L*. The meet and the join Table 1: Triangular norms and conorms on [0, 1] t-norm t-conorm TM(x, y) ¼ min(x, y) SM(x, y) ¼ max(x, y) TP(x, y) ¼ x,y SP(x, y) ¼ x þ y � x,y TW(x, y) ¼ max(x þ y � 1, 0) SW(x, y) ¼ min(x þ y, 1) Table 2: S-implicators and residual implicators on [0, 1] S-implicator Residual implicator ISM;Nsðx; yÞ ¼ maxð1 � x; yÞ ITM ðx; yÞ ¼ 1 if x � y y else � ISP;Nsðx; yÞ ¼ 1 � x þ x; y ITP ðx; yÞ ¼ 1 if x � y y x else � ISW;Nsðx; yÞ ¼ minð1 � x þ y; 1Þ ITW ðx; yÞ ¼ minð1 � x þ y; 1Þ Expert Systems, November 2003, Vol. 20, No. 5 ________________________________________________________________ 263 EXSY : 02005003 BWUK EXSY 02005003.PDF 08-Aug-03 16:38 226131 Bytes 10 PAGES UN CO RR EC TE D PR O O F operators on L* are respectively the IF t-norm TM and the IF t-conorm SM defined by TMðx; yÞ ¼ ðminðx1; y1Þ; maxðx2; y2ÞÞ SMðx; yÞ ¼ ðmaxðx1; y1Þ; minðx2; y2ÞÞ Combining TW and SW of Table 1 gives rise to the t- representable IF t-norm TW and IF t-conorm SW defined by TWðx; yÞ ¼ ðmaxð0; x1 þ y1 � 1Þ; minð1; x2 þ y2ÞÞ SWðx; yÞ ¼ ðminð1; x1 þ y1Þ; maxð0; x2 þ y2 � 1ÞÞ However, TL and SL are also possible extensions of TW and SW to IF theory: TLðx; yÞ ¼ ðmaxð0; x1 þ y1 � 1Þ; minð1; x2 þ 1 � y1; y2 þ 1 � x1ÞÞ SLðx; yÞ ¼ ðminð1; x1 þ 1 � y2; y1 þ 1 � x2Þ; maxð0; x2 þ y2 � 1ÞÞ They are not, however, t-representable. All of these IF t- conorms induce IF S-implicators ISM;Nsðx; yÞ ¼ðmaxðx2; y1Þ; minðx1; y2ÞÞ ISW;Nsðx; yÞ ¼ðminð1; x2 þ y1Þ; maxð0; x1 þ y2 � 1ÞÞ ISL; Nsðx; yÞ ¼ðminð1; y1 þ 1 � x1; x2 þ 1 � y2Þ; maxð0; y2 þ x1 � 1ÞÞ while the IF t-norms have residual IF implicators: ITMðx; yÞ ¼ 1L� if x1 � y1 and x2 � y2 ð1 � y2; y2Þ if x1 � y1 and x2oy2 ðy1; 0Þ if x14y1 and x2 � y2 ðy1; y2Þ if x14y1 and x2oy2 8>>< >>: ITWðx; yÞ ¼ ðminð1; 1 þ y1 � x1; 1 þ x2 � y2Þ; maxð0; y2 � x2ÞÞ ITL equals TsL;Ns. 2.4. Fuzzy rough set theory The two main streams in the perception of the notion ‘rough set’ both invoke generalizations to a ‘fuzzy rough set’ notion, intended to approximate a fuzzy set in a fuzzy approximation space, i.e. defined by a fuzzy relation. 1 Many people worked on the fuzzification of upper and lower approximations in the spirit of Pawlak (e.g. Nakamura, 1988; Dubois & Prade, 1990; Yao, 1997, 1998; Thiele, 1998; Radzikowska & Kerre, 2002). In doing so, the central focus moved from elements’ indistinguish- ability (with respect to their attribute values in an information system) to their similarity, again with respect to those attribute values: objects are categorized into classes with ‘soft’ boundaries based on their similarity to one another. A concrete advantage of such a scheme is that abrupt transitions between classes are replaced by gradual ones, allowing an element to belong (to varying degrees) to more than one class. An example at hand is an attribute in an information table that records ages: in order to restrict the number of equivalence classes, the classical rough set theory advises to discretize age values by a crisp partition of the universe, e.g. using intervals [0, 10], [10, 20],y. This does not always reflect our intuition, however: by imposing such harsh boundaries, a person who has just turned 11 will not be taken into account in the [0, 10] class, even when he is only at a minimal remove from full membership in that class. A general definition of fuzzy rough set, absorbing earlier suggestions in the same direction, was given by Radzi- kowska and Kerre (2002). Paraphrasing the following relations which hold in the crisp case y 2 A , ð8x 2 XÞððx; yÞ 2 R ) x 2 AÞ y 2 �AA , ð9x 2 XÞððx; yÞ 2 R and x 2 AÞ they define the lower and upper approximations of a fuzzy set A in X as the fuzzy sets A and �AA in X, constructed by means of an implicator I, a t–norm T and a fuzzy T- equivalence relation R in X: AðyÞ ¼ inf x2X IðRðx; yÞ; AðxÞÞ AðyÞ ¼ sup x2X TðRðx; yÞ; AðxÞÞ for all y in X. For an element y in X, its membership degree in the lower approximation of A is determined by looking at the elements resembling y (the foreset Ry) and by computing to what extent Ry is contained in A. Its membership degree in the upper approximation on the other hand is determined by the overlap between Ry and A. Technically, these operations amount to taking the super- direct image and the direct image respectively of A under the fuzzy relation R, (De Cock, 2002). A couple of fuzzy sets (A1, A2) is called a rough set in the approximation space (X, R, T, I) if there exists a fuzzy set A such that A ¼ A1 and �AA ¼ A2. A suggestion for fuzzification of the second stream view was launched by Nanda and Majumdar (1992). Bearing in mind Iwinski’s original view one would expect a fuzzy rough set to be a couple (A, B) of fuzzy sets A and B, both coming from some kind of algebra and such that ADB. However, Nanda and Majumdar chose to construct something that might be called ‘the fuzzy rough set of a rough set’. Starting from an Iwinski rough set, i.e. a couple (P, Q) of sets P and Q in X, a fuzzy rough set is a couple of fuzzy sets (A, B). A is a fuzzy set in P, while B is a fuzzy set in Q. Furthermore the first should be included in the second. When trying to express such a requirement one 1 Yao (1997) used ‘fuzzy rough set’ to denote the approximation of a crisp set in a fuzzy approximation space, whereas in his view a ‘rough fuzzy set’ gives an approximation of a fuzzy set in a crisp approximation space. Most authors, like us, use ‘fuzzy rough sets’ as a general term to cover ‘fuzzified rough set theory’. 264 ________________________________________________________________ Expert Systems, November 2003, Vol. 20, No. 5 EXSY : 02005003 BWUK EXSY 02005003.PDF 08-Aug-03 16:38 226131 Bytes 10 PAGES UN CO RR EC TE D PR O O F already notices that it is not very convenient that both fuzzy sets are defined on different universes. This is why authors introduce their own ‘tricks’ for extending the universe (e.g. extending the universes of A and B to X (Chakrabarty et al., 1998; Çoker, 1998), extending the smaller universe (that of A) to the bigger one (that of B) (Samanta & Mondal, 2001)). In the literature we did not find any semantic motivation behind this kind of fuzzy rough sets, or any applications using them. Still for many authors this notion of fuzzy rough set seems to be an attractive starting point for the introduction of intuitionistic fuzzy rough sets (Chakrabarty et al., 1998; Samanta & Mondal, 2001; Jena & Ghosh, 2002). Before we go into that topic, however, we will focus on the links between fuzzy rough set theory and IFS theory. 3. Fuzzy rough set theory versus IFS theory Along with the lower and upper approximations, rough set theory provides two kinds of membership: if an element belongs to the lower (respectively upper) approximation of A, we are dealing with strong (respectively weak) member- ship of A (Pawlak, 1982). It is very natural to extend this idea to fuzzy rough set theory: the strong membership function of A is the membership function of the lower approximation of A, while the weak membership function of A is the membership function of the upper approxima- tion of A. In IFS theory we are also dealing with two kinds of functions, namely a membership function m and a non- membership function n such that m � coðnÞ ð1Þ Note that the strong membership function of the fuzzy rough set can be considered as the membership function m of an IFS, while the complement of the weak membership function of the fuzzy rough set can be used as the non- membership function n. This remark (Çoker, 1998) immediately reveals the strong link between rough set theory and IFS theory. One might even argue that IFS theory could really draw profit from fuzzy rough set theory, because the latter brings a means to construct the membership and non-membership functions of an IFS from a fuzzy set of examples and a fuzzy information relation (a fuzzy relation modelling similarity). It is a far greater challenge, however, to imagine what we could do if the input fed to a knowledge-based system carries information not only about the positive side but also about the negative side. How can we additionally benefit if the set of examples is IF, if the information relation is IF? To answer this question, in the next section we lift the study yet one level higher, by exploring different ways of introducing the concept ‘intuitionistic fuzzy rough set’. Keeping in mind what we learned in this section, we expect it to be ‘a couple of couples of functions’ (be it (strong or weak) membership functions, or non-membership func- tions). 4. Intuitionistic fuzzy rough sets A very natural way to extend concepts from fuzzy set theory to their generalizations in IFS theory is the replacement of [0, 1] by L* as the evaluation set for the membership degrees. � Doing so in Nanda and Majumdar’s view on fuzzy rough sets leads to Chakrabarty et al.’s (1998), approach to intuitionistic fuzzy rough sets; they construct an IF rough set (A, B) of a rough set (P, Q). A and B are both IFSs in X such that A � B; i:e: mA � mB and nA nB From this point of view the lower approximation A and the upper approximation B are both IFSs. In other words, the strong membership is itself characterized by a membership function mA and a non-membership function nA, while the membership function mB and the non-membership function nB together constitute the weak membership. In this way we can reflect hesitation on the strong and the weak membership. Jena and Ghosh (2002) reintroduce the same notion. � Samanta and Mondal (2001) also introduce this notion but they call it a rough IF set. Furthermore they also define their concept of IF rough set, looking at it from a different angle: in their approach an IF rough set is a couple (A, B) such that A and B are both fuzzy rough sets (in the sense of Nanda and Majumdar) and A is included in the complement of B, i.e. A � coðBÞ ð2Þ Even though we omit the details of the definition of complement and inclusion of fuzzy rough sets here (cf. (Samanta and Mondal (2001) for the full story), the reader can still compare (2) to (1) to see that A refers to membership of the IF rough set, while B corresponds to non-membership. � Obviously to Samanta and Mondal an intuitionistic fuzzy rough set (A, B) is a generalization of an IFS in which membership and non-membership functions are no longer fuzzy sets but fuzzy rough sets A and B. Note that for Chakrabarty et al. on the other hand an intuitionistic fuzzy rough set (A, B) is a generalization of a fuzzy rough set, in which upper and lower approximations are no longer fuzzy sets but IFSs A and B. � In contrast to the proposals above, the approach of Rizvi et al. (2002) is along the lines of Pawlak’s rough sets, explicitly indicating how lower and upper approx- imations of an IFS should be derived in an approxima- tion space. Rizvi et al. describe their proposal as ‘rough intuitionistic fuzzy set’, and in comparison with the Expert Systems, November 2003, Vol. 20, No. 5 ________________________________________________________________ 265 EXSY : 02005003 BWUK EXSY 02005003.PDF 08-Aug-03 16:38 226131 Bytes 10 PAGES UN CO RR EC TE D PR O O F approaches above one could say that it is again about having a hesitation margin on the weak and strong memberships, i.e. on the upper and lower approxima- tions. The hesitation margin on the lower and upper approximations can be seen as a consequence of the hesitation margin of the original IFS to be approxi- mated. Remarkably enough, the lower and upper approximations themselves are not IFSs in X but IFSs in the class of equivalence classes of R! The question remains unanswered why the definition of Radzikowska and Kerre (2002) — which has existed already in a more specific form for more than a decade — did not undergo the natural transformation process towards intuitionistic fuzzy rough set theory until now. In the remainder of this paper it becomes clear that it in fact leads to a mathematically elegant and semantically interpretable concept whereas the above-mentioned pro- posals all suffer from various drawbacks making them less eligible for applications. Until now we have been using the notations A and �AA to denote the lower and the upper approximation of A (whatever A may be), tacitly assuming that the (fuzzy) relation as well as the t-norm and the implicator are used. This was done not only for ease of notation, but also to keep a uniform notation throughout all the different models. However, to maintain clearness in the remainder, we switch to a slightly different notation. Furthermore from now on we assume that T is an IF triangular norm, I an IF implicator and R an IF T- equivalence relation in X. Together they constitute the approximation space (X, R, T, I). We use A and B to denote IFSs in X. As usual we start by defining concepts of lower and upper approximation. Definition 1 The lower and upper approximations of A are respectively the IFSs RkIA and RmTA in X defined by R #I AðyÞ ¼ inf x2X IðRðx; yÞ; AðxÞÞ R "T AðyÞ ¼ sup x2X TðRðx; yÞ; AðxÞÞ for all y in X. We say that a couple of IFSs (A1, A2) is an intuitionistic fuzzy rough set in the approximation space (X, R,T, I) if there exists an IFS A such that RkIA ¼ A1 and RmTA ¼ A2. The lower approximation of A is included in A, while A is included in its upper approximation. Proposition 1 (De Cock, 2002) RkIADADRmTA. The following propositions describe how the lower and upper approximations behave with respect to a refinement of the IFS to be approximated, or a refinement of the IF relation that defines the approximation space. Proposition 2 (De Cock, 2002) If ADB then RkIAD RkIB and RmTADRmTB. Proposition 3 (De Cock, 2002) If R1 and R2 are IF T- equivalence relations such that R1DR2 then R1 #I A R2 #I A R1 "T A � R2 "T A We now define a concept of definability, similar to the one in rough set theory. Definition 2 A is called definable if and only if RkIA ¼ RmTA. In classical rough set theory, a set is definable if and only if it is a union of equivalence classes. This property no longer holds in intuitionistic fuzzy rough set theory. However, if we imply sufficient conditions on the IF t-norm T and the IF implicator I defining the approximation space, we can still establish a weakened theorem. For the proof we rely on the following two propositions. Proposition 4 (De Cock, 2002) If the partial mappings of T are sup-morphisms and I is the residual implicator of T then the following are equivalent (1) A ¼ RkIA (2) A ¼ RmTA Proposition 5 (De Cock, 2002) If the partial mappings of T are sup-morphisms and I is the residual implicator of T then R "T ðR "T AÞ ¼ R "T A R #I ðR #I AÞ ¼ R #I A Corollary 1 If the partial mappings of T are sup- morphisms and I is the residual implicator of T then R "T ðR #I AÞ ¼ R #I A R #I ðR "T AÞ ¼ R "T A Theorem 1 If the partial mappings of T are sup-morphisms and I is the residual implicator of T then any union of R- foresets is definable, i.e. ð9BÞ B � X and A ¼ [ z2B Rz ! implies R #I A ¼ R "T A Proof Due to the symmetry and the T-transitivity of R and the fact that the partial mappings of T are sup- morphisms, we obtain R "T AðyÞ ¼ sup x2X TðRðx; yÞ; AðxÞÞ ¼ sup x2X TðRðx; yÞ; sup z2B Rðz; xÞÞ ¼ sup z2B sup x2X TðRðx; yÞ; Rðz; xÞÞ � sup z2B Rðz; yÞ ¼AðyÞ 266 ________________________________________________________________ Expert Systems, November 2003, Vol. 20, No. 5 EXSY : 02005003 BWUK EXSY 02005003.PDF 08-Aug-03 16:38 226131 Bytes 10 PAGES UN CO RR EC TE D PR O O F Proposition 1 now implies A ¼ RmTA. Combining this result with Proposition 4 we obtain the definability of A. The following example illustrates that the opposite of Theorem 1 does not generally hold, i.e. not every definable set corresponds to a union of R-foresets. Example 2 Let X ¼ {x0}, R(x0, x0) ¼ (1, 0), A(x0) ¼ (0.5, 0.5). Then R "T Aðx0Þ ¼ TðRðx0; x0Þ; Aðx0ÞÞ ¼ ð0:5; 0:5Þ ¼ Aðx0Þ That is, A is definable. Since the only R-foreset is Rx0 and Rx0(x0)>L* A(x0) we cannot rewrite A as a union of R- foresets. Under the same conditions implied on T and I as in Theorem 1, the SM-union and TM-intersection of two definable IFSs is definable. This is a corollary of the next proposition. Proposition 6 (De Cock, 2002) If the partial mappings of T are sup-morphisms and I is the residual implicator of T then R "T ðA [ BÞ ¼ R "T A [ R "T B R #I ðA \ BÞ ¼ R #I A \ R #I B with AB and A-B defined as in Section 2.2, i.e. A [ BðxÞ ¼ ðminðmAðxÞ; mBðxÞÞ; maxðnAðxÞ; nBðxÞÞÞ A \ BðxÞ ¼ ðmaxðmAðxÞ; mBðxÞÞ; minðnAðxÞ; nBðxÞÞÞ Proposition 7 Let T be a t-representable IF t-norm such that T ¼ (T, S) and such that S(x, y) ¼ 1 � T(1 � x, 1 � y), and let R1, R2 be two fuzzy T-equivalence relations such that R1(x, y)rR2(x, y), for all x and x in X. Then R defined by Rðx; yÞ ¼ ðR1ðx; yÞ; 1 � R2ðx; yÞÞ for x and y in X, is an IF T-equivalence relation. Proof Reflexivity and symmetry of R follow immediately from the corresponding properties of R1 and R2. To prove T-transitivity, let x, y and zAX. TðRðx; yÞ; Rðy; zÞÞ ¼ðTðR1ðx; yÞ; R1ðy; zÞÞ; Sð1 � R2ðx; yÞ; 1 � R2ðy; zÞÞÞ ¼ðTðR1ðx; yÞ; R1ðy; zÞÞ; 1 � TðR2ðx; yÞ; R2ðy; zÞÞÞ �L� ðR1ðx; zÞ; 1 � R2ðx; zÞÞ ¼Rðx; zÞ Example 3 Let X ¼ [0, 100], and let the fuzzy TW- equivalence relation Ec on X be defined by Ecðx; yÞ ¼ max 1 � jx � yj c ; 0 � � for all x and y in X, and with real parameter c>0. Obviously, if c1rc2 then Ec1ðx; yÞ � Ec2ðx; yÞ. By Proposi- tion 7, ðEc1; coðEc2ÞÞ is an IF TW-equivalence relation. Example 4 Figure 1 shows the membership function mA and the non-membership function nA of the IFS A in the universe X ¼ [0, 100]. Using the non-t-representable IF t- norm TL, its residual IF implicator ITL and the IF relation R defined by Rðx; yÞ ¼ ðE40ðx; yÞ; 1 � E40ðx; yÞÞ for all x and y in [0, 100] we computed the lower approximation of A( ¼ A1) as well as the upper approxima- tion of A( ¼ A2). They are both depicted in Figure 1. An IFS A is characterized by means of a membership function mA and a non-membership function nA. A natural question which arises is whether the lower approximation and the upper approximation of A could be defined in terms of the lower and the upper approximation of mA and nA (all within the proper approximation spaces of course). Generally such a ‘divide and conquer’ approach is every- thing but trivial in IFS theory, and sometimes even impossible. However, some conditions implied on the logical operators involved can allow for some results in this direction. Particularly attractive are the t-representable t- norms and t-conorms, and the S-implicators that can be associated with them. Lemma 1 For every family (ai, bi)iAI in L* sup i2I ðai; biÞ ¼ sup i2I ai; inf i2I bi � � inf i2I ðai; biÞ ¼ inf i2I ai; sup i2I bi � � Proposition 8 Let T be t-representable such that T ¼ (T, S), let N be an involutive negator on [0, 1], and let I Figure 1: A (solid lines), and the upper (broken lines) and lower (dotted lines) approximations of A. Expert Systems, November 2003, Vol. 20, No. 5 ________________________________________________________________ 267 EXSY : 02005003 BWUK EXSY 02005003.PDF 08-Aug-03 16:38 226131 Bytes 10 PAGES UN CO RR EC TE D PR O O F be the S-implicator on [0, 1] induced by S and N. Then R "T A ¼ ðmR "T mA; ðcoNðnRÞÞ #I nAÞ Proof For all y in X R "T AðyÞ ¼ sup x2X TðRðx; yÞ; AðxÞÞ ¼ sup x2X ðTðmRðx; yÞ; mAðxÞÞ; SðnRðx; yÞ; nAðxÞÞÞ ¼ðsup x2X TðmRðx; yÞ; mAðxÞÞ; inf x2X IðNðnRðx; yÞÞ; nAðxÞÞÞ ¼ððmR "T mAÞðyÞ; ðcoNðnRÞ #I nAÞðyÞÞ Proposition 9 Let S be a t-representable IF t-conorm such that S ¼ (S, T), let N be an involutive IF negator, let I be the IF S-implicator induced by S and N, let N be the negator on [0, 1] induced by N and let I be the S-implicator induced by S and N. Then R #I A ¼ ððconRÞ #I mA; coðcoNmRÞ "T nAÞ Proof For all y in X R #I AðyÞ ¼ inf x2X IðRðx; yÞ; AðxÞÞ ¼ inf x2X SðNðRðx; yÞÞ; AðxÞÞ ¼ inf x2X SððNð1 � nRðx; yÞÞ; mAðxÞÞ; supx2XTð1 � NðmRðx; yÞÞ; nAðxÞÞÞ ¼ðinf x2X IðconRðx; yÞ; mAðxÞÞ; sup x2X TðcoðcoNðmRÞÞðx; yÞÞ; nAðxÞÞÞ ¼ððconR #I mAÞðyÞ; ðcoðcoNðmRÞÞ "T nAÞðyÞÞ Observe that in both propositions on the ‘fuzzy level’ the approximations are taken under the membership function mR, or something semantically very much related such as the N-complement of the non-membership function nR or once even the standard complement of the N-complement of mR. Presented in this way, the resulting formulae look quite complicated. For better understanding, assume for a moment that the negator N is the standard negator, and that the IF relation R is in reality a fuzzy relation, i.e. mR ¼ co(nR); then the formulae reduce to R "T A ¼ ðmR "T mA; mR #I nAÞ R #I A ¼ ðmR #I mA; mR "T nAÞ Apparently in this case the membership function of the upper approximation of A is the upper approximation of the membership function of A, while the non-membership function of the upper approximation of A is the lower approximation of the non-membership function of A. For the lower approximation of A the dual proposition holds. Example 5 Figure 2 shows the same IFS A we used in Example 4. However, to compute its lower approximation A1 and its upper approximation A2, this time we used the t- representable IF t-norm TW, its residual IF implicator and the IF relation R defined by Rðx; yÞ ¼ ðE30ðx; yÞ; E50ðx; yÞÞ for all x and y in [0,100]. 5. Conclusion Rough sets and IFSs both capture particular facets of the same notion—imprecision. In this paper, it was shown how they can be usefully combined into a single framework encapsulating the best of (so far) largely separate worlds. The link, on the syntactical level, between fuzzy rough sets and IFSs, identified by Çoker, has not proven much of an obstacle in this sense: indeed, by allowing each ingredient to retain its own distinguishing semantics, it was possible to create an end product which is both syntactically sound and semantically meaningful. We feel especially justified in our cause since we have exploited to the fullest a time- honoured adage: namely, that to every object there is a positive and a negative side which need to be addressed individually in order to come up with a true representation of that object. Future work will involve tailoring this general framework to the specific needs of everyday applications. Acknowledgement Chris Cornelis and Martine De Cock would like to thank the Fund for Scientific Research Flanders—FWO for funding the research reported in this paper. Figure 2: Upper (broken lines) and lower (dotted lines) approximations of A. 268 ________________________________________________________________ Expert Systems, November 2003, Vol. 20, No. 5 EXSY : 02005003 BWUK EXSY 02005003.PDF 08-Aug-03 16:38 226131 Bytes 10 PAGES UN CO RR EC TE D PR O O F References ATANASSOV, K.T. (1999) Intuitionistic Fuzzy Sets, Heidelberg: Physica. CHAKRABARTY, K., T. GEDEON and L. KOCZY (1998) Intuitionistic fuzzy rough sets, in Proceedings of the Fourth Joint Conference on Information Sciences, 211–214. ÇOKER, D. (1998) Fuzzy rough sets are intuitionistic L-fuzzy sets, Fuzzy Sets and Systems, 96, 381–383. DE COCK, M. (2002) A thorough study of linguistic modifiers in fuzzy set theory, PhD thesis (in Dutch), Ghent University. DESCHRIJVER, G., C. CORNELIS and E.E. KERRE (2002) Intuitio- nistic fuzzy connectives revisited, in Proceedings of the 9th International Conference on Information Processing and Manage- ment of Uncertainty in Knowledge-based Systems, 1839–1844 DUBOIS, D. and H. PRADE (1990) Rough fuzzy sets and fuzzy rough sets, International Journal of General Systems, 17, 191–209. GENTILHOMME, Y. (1968) Les ensembles floues en linguistique, Cahiers de Linguistique Théorique, 5, 47–63. GOGUEN, J. (1967) L-fuzzy sets, Journal of Mathematical Analysis and Applications, 18, 145–174. IWINSKI, T.B. (1987) Algebraic approach to rough sets, Bulletin of the Polish Academy of Science and Mathematics, 35, 673–683. JENA, S.P. and S.K. GHOSH (2002) Intuitionistic fuzzy rough sets. Notes on Intuitionistic Fuzzy Sets 8, 1, 1–18. KACPRZYK, J. (ed.) (1992–2002) Studies in Fuzziness and Soft Computing, Heidelberg: Physica, Vols 1–100. KOMOROWSKI, J., Z. PAWLAK, L. POLKOWSKI and A. SKOWRON (1999) Rough sets: a tutorial, in Rough Fuzzy Hybridization: A New Trend in Decision-Making, S.K. Pal and A. Skowron (eds), Singapore: Springer. NAKAMURA, A. (1988) Fuzzy rough sets, Note on Multiple-Valued Logic in Japan, 9, 1–8. NANDA, S. and S. MAJUMDAR (1992) Fuzzy rough sets, Fuzzy Sets and Systems, 45, 157–160. PAWLAK, Z. (1982) Rough sets, International Journal of Computer and Information Sciences, 11 (5), 341–356. PAWLAK, Z. (1985) Rough sets and fuzzy sets, Fuzzy Sets and Systems, 17, 99–102. RADZIKOWSKA, A.M. and E.E. KERRE (2002) A comparative study of fuzzy rough sets, Fuzzy Sets and Systems, 126, 137–156. RIZVI, S., H.J. NAQVI and D. NADEEM (2002) Rough intuitionistic fuzzy sets, in Proceedings of the 6th Joint Conference on Information Sciences, H.J. Caulfield, S. Chen, H. Chen, R. Duro, V. Honavar, E.E. Kerre, M. Lu, M.G. Romay, T.K. Shih, D. Ventura, P.P. Wang and Y. Yang (eds), 101–104. SAMANTA, S.K. and T.K. MONDAL (2001) Intuitionistic fuzzy rough sets and rough intuitionistic fuzzy sets, Journal of Fuzzy Mathematics, 9 (3), 561–582. THIELE, H. (1998) Fuzzy rough sets versus rough fuzzy sets—an interpretation and a comparative study using concepts of modal logic, Technical Report ISSN 1433-3325, University of Dort- mund. THIELE, H. (2001) Generalizing the explicit concept of rough set on the basis of modal logic, in Computational Intelligence in Theory and Practice, B. Reusch and K.H. Temme (eds), Berlin: Physica. YAO, Y.Y. (1996) Two views of the theory of rough sets in finite universes, International Journal of Approximate Reasoning, 15 (4), 291–317. YAO, Y.Y. (1997) Combination of rough and fuzzy sets based on alpha-level sets, in Rough Sets and Data Mining: Analysis for Imprecise Data, T.Y. Lin and N. Cercone (eds), Baston, MA: Kluwer Academic, 301–321. YAO, Y.Y. (1998) A comparative study of fuzzy sets and rough sets, Information Sciences, 109, 227–242. ZADEH, L.A. (1965) Fuzzy sets, Information and Control, 8, 338–353. The authors Chris Cornelis Chris Cornelis received the BSc and MSc degrees in computer science from Ghent University, Belgium, in 1998 and 2000, respectively, and is currently working towards his PhD degree, sponsored by a grant from the National Science Foundation—Flanders. His research interests involve mathematical models of imprecision, including interval-valued fuzzy sets, intuitionistic fuzzy sets, L-fuzzy sets, rough sets and various combinations of these. He has applied these models in approximate reasoning, possibility theory and data mining. Martine De Cock Martine De Cock received an MSc degree in computer science and a teaching degree at Ghent University in 1998. In 2002 she obtained a PhD in computer science with a thesis on the representation of linguistic modifiers in fuzzy set theory. Currently she is working in the Fuzziness and Uncertainty Modelling Research Unit (Ghent University) as a postdoctoral researcher of the Fund of Scientific Research—Flanders (FWO). Her current research interests include rough set theory, L-fuzzy set theory, fuzzy association rules, and the representation of approximate equality. Etienne E. Kerre Etienne E. Kerre was born in Zele, Belgium, on 8 May 1945. He obtained his MSc degree in mathematics in 1967 and his PhD in mathematics in 1970 from Ghent University. Since 1984, he has been a lecturer, and since 1991 a full professor, at Ghent University. He is a referee for more than 30 international scientific journals, and also a member of the editorial board of international journals and conferences on fuzzy set theory. He has been an honorary chairman at various international conferences. In 1976, he founded the Fuzziness and Uncertainty Modelling Re- search Unit (Ghent University) and since then his research has been focused on the modeling of fuzziness and uncertainty, and has resulted in a great number of contributions in fuzzy set theory and its various general- izations, and in evidence theory. He has been particularly involved in the theories of fuzzy relational calculus and of fuzzy mathematical structures. Over the years he has also been a promotor of 16 PhDs on fuzzy set theory. His current research interests include fuzzy and intuitionistic fuzzy relations, fuzzy topology and fuzzy image processing. He has authored or co-authored 11 books, and more than 100 papers in international refereed journals. Q3 Q4 Q5 Q6 Expert Systems, November 2003, Vol. 20, No. 5 ________________________________________________________________ 269 EXSY : 02005003 BWUK EXSY 02005003.PDF 08-Aug-03 16:38 226131 Bytes 10 PAGES