Formal L-concepts with Rough Intents

Abstract

We provide a new approach to synthesis of Formal Concept Analysis and Rough Set Theory. In this approach, the formal concept is considered to be a collection of objects accompanied with two collections of attributes|those which are shared by all the objects and those which are possessed by at least one of the objects. We de ne concept-forming operators for these concepts and describe their properties. Furthermore, we deal with reduction of the data by rough approximation by given equivalence. The results are elaborated in a fuzzy setting.

Introduction

Formal concept analysis (FCA) [ 12 ] is a method of relational data analysis identifying interesting clusters (formal concepts) in a collection of objects and their attributes (formal context), and organizing them into a structure called concept lattice. Numerous generalizations of FCA, which allow to work with graded data, were provided; see [ 19 ] and references therein.

In a graded (fuzzy) setting, two main kinds of concept forming-operators| antitone and isotone one|were studied [ 2, 13, 20, 21 ], compared [ 7, 8 ] and even covered under a unifying framework [ 4, 18 ]. We describe concept-forming operators combining both isotone and antitone operators in such a way that each formal (fuzzy) concept is given by two sets of attributes. The rst one is a lower intent approximation, containing attributes shared by all objects of the concept; the second one is an upper intent approximation, containing those attributes which are possessed by at least one object of the concept. Thus, one can consider the two intents to be a lower and upper approximation of attributes possessed by an object.

Several authors dealing with synthesis of FCA and Rough Set Theory have noticed that intents formed by isotone and antitone operators (in both, crisp and fuzzy setting) correspond to upper and lower approximations, respectively (see e.g. [ 15, 16, 24 ]). To the best of our knowledge, no one has studied conceptforming operators which would provide both approximations being present in one concept lattice.

In this papers we present such concept-forming operators, structure of their concepts, and reduction of the data by means of rough approximations by equivalences. Due to page limitation we omit proofs of some theorems.

Preliminaries

In this section we summarize the basic notions used in the paper. Residuated Lattices and Fuzzy Sets We use complete residuated lattices as basic structures of truth-degrees. A complete residuated lattice [ 1, 14, 23 ] is a structure L xL; ^; _; b; Ñ; 0; 1y such that xL; ^; _; 0; 1y is a complete lattice, i.e. a partially ordered set in which arbitrary in ma and suprema exist; xL; b; 1y is a commutative monoid, i.e. b is a binary operation which is commutative, associative, and a b 1 a for each a P L; b and Ñ satisfy adjointness, i.e. a b b ¤ c iff a ¤ b Ñ c. 0 and 1 denote the least and greatest elements. The partial order of L is denoted by ¤. Throughout this work, L denotes an arbitrary complete residuated lattice.

Elements a of L are called truth degrees. Operations b (multiplication) and Ñ (residuum) play the role of (truth functions of) \fuzzy conjunction" and \fuzzy implication". Furthermore, we de ne the complement of a P L as a a Ñ 0.

An L-set (or fuzzy set) A in a universe set X is a mapping assigning to each x P X some truth degree Apxq P L. The set of all L-sets in a universe X is denoted LX , or LX if the structure of L is to be emphasized.

The operations with L-sets are de ned componentwise. For instance, the intersection of L-sets A; B P LX is an L-set A X B in X such that pA X Bqpxq Apxq ^ Bpxq for each x P X. An L-set A P LX is also denoted tApxq{x | x P Xu. If for all y P X distinct from x1; : : : ; xn we have Apyq 0, we also write tApx1q{x1; : : : ; Apxnq{xnu.

An L-set A P LX is called normal if there is x P X such that Apxq 1, and it is called crisp if Apxq P t0; 1u for each x P X. Crisp L-sets can be identi ed with ordinary sets. For a crisp A, we also write x P A for Apxq 1 and x R A for Apxq 0.

Binary L-relations (binary fuzzy relations) between X and Y can be thought of as L-sets in the universe X Y . That is, a binary L-relation I P LX Y between a set X and a set Y is a mapping assigning to each x P X and each y P Y a truth degree Ipx; yq P L (a degree to which x and y are related by I). For L-relation I P LX Y we de ne its transpose IT P LY X as ITpy; xq Ipx; yq for all x P X, y P Y .

The composition operators are de ned by pI

J qpx; zq pI š J qpx; zq pI › J qpx; zq ª Ipx; yq b J py; zq; yPY © Ipx; yq Ñ J py; zq; yPY © J py; zq Ñ Ipx; yq yPY for every I P LX Y and J P LY Z .

A binary L-relation E is called an L-equivalence if it satis es IdX „ E (re exivity), E ET (symmetry), E E „ E (transitivity).

An L-set B P LY is compatible w.r.t. L-equivalence E P LY Y if

Bpy1q b Epy1; y2q ¤ Bpy2q: for any y1; y2 P Y .

Formal Concept Analysis in the Fuzzy Setting An L-context is a triplet xX; Y; Iy where X and Y are (ordinary) sets and I P LX Y is an L-relation between X and Y . Elements of X are called objects, elements of Y are called attributes, I is called an incidence relation. Ipx; yq a is read: \The object x has the attribute y to degree a." An L-context may be described as a table with the objects corresponding to the rows of the table, the attributes corresponding to the columns of the table and Ipx; yq written in cells of the table (for an example see Fig. 1).

A B C D

Consider the following pairs of operators induced by an L-context xX; Y; Iy. First, the pair xÒ; Óy of operators Ò : LX Ñ LY and Ó : LY Ñ LX is de ned by AÒpyq © Apxq Ñ Ipx; yq; xPX

BÓpxq © Bpyq Ñ Ipx; yq: yPY Second, the pair xX; Yy of operators X : LX Ñ LY and Y : LY Ñ LX is de ned by

AXpyq

ª Apxq b Ipx; yq;

BYpxq

xPX © Ipx; yq Ñ Bpyq: yPY

To emphasize that the operators are induced by I, we also denote the operators by xÒI ; ÓI y and xXI ; YI y. Fixpoints of these operators are called formal concepts. The set of all formal concepts (along with set inclusion) forms a complete lattice, called L-concept lattice. We denote the sets of all concepts (as well as the corresponding L-concept lattice) by BÒÓpX; Y; Iq and BXYpX; Y; Iq, i.e.

BÒÓpX; Y; Iq

When displaying L-concept lattices, we use labeled Hasse diagrams to include all the information on extents and intents. In BÒÓpX; Y; Iq, for any x P X, y P Y and formal L-concept xA; By we have Apxq ¥ a and Bpyq ¥ b if and only if there is a formal concept xA1; B1y ¤ xA; By, labeled by a{x and a formal concept xA2; B2y ¥ xA; By, labeled by b{y. We use labels x resp. y instead of 1{x resp. 1 y and omit redundant labels (i.e., if a concept has both the labels a{x and b{x { then we keep only that with the greater degree; dually for attributes). The whole structure of BÒÓpX; Y; Iq can be determined from the labeled diagram using the results from [ 2 ] (see also [ 1 ]).

In BXYpX; Y; Iq, for any x P X, y P Y and formal L-concept xA; By we have Apxq ¥ a and Bpyq ¤ b if and only if there is a formal concept xA1; B1y ¤ xA; By, labeled by a{x and a formal concept xA2; B2y ¥ xA; By, labeled by b{y (see examples depicted in Fig. 2).

A; 0:5{ ; 0:5{C; ;

C; 0:5{ ; 0:5{

L-rough concepts

We consider concept-forming operators induced by L-context xX; Y; Iy de ned as follows: De nition 1. Let xX; Y; Iy be an L-context. De ne L-rough concept-forming operators as

AM xAÒ; AXy and xB; ByO

BÓ X BY for A P LX ; B; B P LY . L-rough concept is then a xed point of xM; Oy, i.e. a pair xA; xB; Byy P LX pL LqY such that AM xB; By and xB; ByO A.1 AÒ and AX are called lower intent approximation and upper intent approximation, respectively.

That means, M gives intents w.r.t. both xÒ; Óy and xX; Yy; O then gives intersection of extents related to the corresponding intents.

We denote the set of all xed-points of xM; Oy, in correspondence with (3), as BMOpX; Y; Iq and call it L-rough concept lattice. Below, we present an analogy of the Main theorem on concept lattices for L-rough setting.

Theorem 1 (Main theorem on L-rough concept lattices). (a) L-rough concept lattice BMOpX; Y; Iq is a complete lattice with suprema and in ma de ned as follows © xAi; Bi; Biy

i ª xAi; Bi; Biy i

OM x£ Ai; x¤ Bi; £ Biy y;

i i i xp¤ AiqMO; £ Bi; ¤ Biy: i i i (b) Moreover, a complete lattice V there are mappings

xV; ¤y is isomorphic to BMOpX; Y; Iq iff : X

L Ñ V and : Y

L 1 In what follows, we naturally identify xA; xB; Byy with xA; B; By.

Theorem 2. For normal A P LX , we have AÒ „ AX, for crisp singleton A P LX , we have AÒ AX.

Proof. Since A is normal, there is x1 P X such that Apx1q

1. Then we have

AÒpyq © Apxq Ñ Ipx; yq ¤ Apx1q Ñ Ipx1; yq xPX Apx1q b Ipx1; yq ¤ ª Apxq b Ipx; yq xPX

Ipx1; yq

AXpyq

(5) for each y P Y .

For A being a crisp singleton, one can show AÒ ities in (5) to equalities.

AX by changing all inequal

\[

Since xM; Oy is de ned via xÒ; Óy and xX; Yy, one can expect that there is a strong relationship between the associated concept lattices. In the rest of this section, we summarize them.

Theorem 3. For S „ LX , let rSs denote an L-closure span of S, i.e. the smallest L-closure system containing S. We have rExtÒÓpX; Y; Iq Y ExtXYpX; Y; Iqs

ExtMOpX; Y; Iq: Proof. \„": Let A P ExtÒÓpX; Y; Iq. Then A AXX Similarly for A P ExtXYpX; Y; Iq.

\…": Let A P ExtMOpX; Y; Iq and let xB1; B2y AM. Then we have A BÓ X BY P rExtÒÓpX; Y; Iq Y ExtXYpX; Y; Iqs since BÓ P ExtÒÓpX; Y; Iq and BY P ExtXYpX; Y; Iq. xAÒ; Y yO P ExtMOpX; Y; Iq.

From Theorem 3 one can observe that no extent from ExtÒÓpX; Y; Iq and ExtXYpX; Y; Iq is lost.

Corollary 1. ExtÒÓpX; Y; Iq „ ExtMOpX; Y; Iq and ExtXYpX; Y; Iq „ ExtMOpX; Y; Iq.

In addition, no concept is lost.

Corollary 2. For each xA; By P BÒÓpX; Y; Iq there is xA; B; AXy P BMOpX; Y; Iq.

For each xA; By P BXYpX; Y; Iq there is xA; AÒ; By P BMOpX; Y; Iq.

Remark 1. One can observe from Fig. 3 that in ExtMOpX; Y; Iq there exist extents which are present neither in ExtÒÓpX; Y; Iq nor in ExtXYpX; Y; Iq. On the other hand, lower intent approximations are exactly those from IntÒÓpX; Y; Iq and upper intent approximations are exactly those from IntXYpX; Y; Iq.

With results on mutual reducibility from [ 8 ] we can state the following theorem on representation of BMO by BÒÓ.

5 { : 0 ; 5 { : 0 ; B

0 5 { : 0 ; 5 { : 0 ; 5 { : 0 1 { ; 5 { : 0 5 { : 0 5 { : 0 ; 5 { : 0 5 { : 0

A

C

0 1 { ; 1 {

A 5 { : 0 C

0 5 { : 0 5 { : 0 0 { ; ;

A 5 { : 0 ; 0 {

0 { ;

; D 1 { ;

B

D 5 { : ;

D 5 { : 0 5 { : 0 ; 5 { : 0 ; ; 5 { : 0 ; A 0 { ; C B 5 { : 0

D 5 { : 0 ; A 5 { : 0 ; B ; A 5 { : ; ; C 5 { : 0 0 { ; C 5 { : 0 0 { ; C 5 { : D 5 { : 0 m X c p

z O 0 Theorem 4. For a L-context xX; Y; Iy, consider the L-context xX; Y where J is de ned by L; J y J px; xy; ayq #Ipx; yq

Ipx; yq Ñ a if a 1; otherwise.

Then we have that BÒÓpX; Y In addition,

L; J q is isomorphic to BMOpX; Y; Iq as a lattice.

ExtÒÓpX; Y

L; J q In [ 17 ] Pawlak introduced Rough Set Theory where uncertain elements are approximated with respect to an equivalence relation representing indiscernibility.

Formally, given Pawlak approximation space xU; Ey, where U is a non-empty set of objects (universe) and E is an equivalence relation on U , the rough approximation of a crisp set A „ U by E is the pair xAóE ; AòE y of sets in U de ned by x P AóE iff for all y P U; xx; yy P E implies y P A; x P AòE iff there exists y P U such that xx; yy P E and y P A: AóE and AòE are called lower and upper approximation of the set A by E, respectively.

In the fuzzy setting, one can generalize xAóE ; AòE y as in [ 10, 11, 22 ], AóE pxq AòE pxq ©pEpx; yq Ñ Apyqq; yPU ªpApyq b Epx; yqq yPU for L-equivalence E P LU U and L-set A P LU .

Considering L-context xU; U; Ey, we can easily see that óE is equivalent to YE ; and òE is equivalent to XET . Since E is symmetric, we can also write xóE ; òE y xYE ; XE y: (6)

Note that for L-set A, AóE is its largest subset compatible with E and AòE is its smallest superset compatible with E.

Below, we deal with situation where lower and upper intent approximations are further approximated using Pawlak's approach. In other words, instead of lower intent approximation AÒ we consider the largest subset of AÒ compatible with a given indiscernibility relation E, and similarly, instead of upper intent approximation AX we consider its smallest superset compatible with E. In Theorem 5 we show how to express this setting using L-rough concept forming operators.

De nition 2. Let xX; Y; Iy be an L-context, E be an L-equivalence on Y . De ne L-rough concept-forming operators as follows:

AME xB; ByOE xAÒóE ; AXòE y;

BòEÓ X BóEY:

Directly from (6) and results in [ 5 ] we have: Theorem 5. Let xX; Y; Iy be an L-context, E be an L-equivalence on Y . We have

AME xAÒI›E ; AXI E y and xB; ByOE

BÓI›E X BYI E :

Again, for normal extents we obtain natural upper and lower intent approximations.

Theorem 6. For normal A P LX we have AÒI›E „ AXI E .

In correspondence with (3) and (4), we denote set of the set of xpoints of xME ; OE y in L-context xX; Y; Iy by BMEOE pX; Y; Iq and set of its extents and intents by ExtMEOE pX; Y; Iq and IntMEOE pX; Y; Iq, respectively.

The following theorem shows that a use of a rougher L-equivalence relation leads to a reduction of size of the L-rough concept lattices. Furthermore, this reduction is natural, i.e. it preserves extents.

Theorem 7. Let xX; Y; Iy be an L-context, and E1, E2 be L-equivalences on Y , such that E1 „ E2. Then

ExtME2OE2 pX; Y; Iq „ ExtME1OE1 pX; Y; Iq: Example 1. Fig. 4 shows L-rough concept lattice of the L-context in Fig. 1 and rough L-concept lattice approximated using the following L-equivalence relation on Y .

To demonstrate Theorem 7, the concepts with the same extents in the two lattices are connected. 5

Conclusions and further research

We proposed a novel approach to synthesis of RTS na FCA. It provides a lot of directions to be further explored. Our future research includes: Study of attribute implications using whose semantics is related to the present setting. That will combine results on fuzzy attribute implications [ 9 ] and attribute containment formulas [ 6 ].

Generalization of the current setting. Note that the operators Ò and X which compute the universal and the existential intent, need not be induced by the same relation to keep most of the described properties. Actually, this feature is used in Section 4. In our future research, we want to elaborate more on this. For instance, it can provide interesting solution of problem of missing values in a formal fuzzy context|the idea is to use Ò induced by the context with missing values substituted by 0, and X induced by the context with missing values substituted by 1.

Reduction of L-rough concept lattice via linguistic hedges As two intents are considered in each L-rough concept, the size of concept lattice can grow very large. The RST approach to reduction of data, i.e. use of rougher L-relation, directly leads to reduction of L-rough concept lattice as we showed in Theorem 7. FFCA provides other ways to reduce the size, one of them is parametrization of concept-forming operators using hedges. 0:5{ ; 0:5{

B; 1{

0:5{ ; 1{ 0:5{B

D

0:5{ 0:5{ 1{ ; 1{ 0:5{A

References

1. Radim Belohlavek . Fuzzy Relational Systems: Foundations and Principles . Kluwer Academic Publishers, Norwell, USA, 2002 .

2. Radim Belohlavek . Concept lattices and order in fuzzy logic . Ann. Pure Appl . Log., 128 ( 1-3 ): 277 { 298 , 2004 .

3. Radim Belohlavek . Optimal decompositions of matrices with entries from residuated lattices . Submitted to J. Logic and Computation , 2009 .

4. Radim Belohlavek . Sup-t-norm and inf-residuum are one type of relational product: Unifying framework and consequences . Fuzzy Sets Syst., 197 : 45 { 58 , June 2012 .

5. Radim Belohlavek and Jan Konecny . Operators and spaces associated to matrices with grades and their decompositions . In NAFIPS 2008 , pages 288 { 293 .

6. Radim Belohlavek and Jan Konecny . A logic of attribute containment , KAM '08 Proceedings of the 2008 International Symposium on Knowledge Acquisition and Modeling , pages 246 { 251 .

7. Radim Belohlavek and Jan Konecny . Closure spaces of isotone galois connections and their morphisms . In Proceedings of the 24th international conference on Advances in Arti cial Intelligence , AI ' 11 , pages 182 { 191 , Springer-Verlag, Berlin, Heidelberg, 2011 .

8. Radim Belohlavek and Jan Konecny . Concept lattices of isotone vs. antitone Galois connections in graded setting: Mutual reducibility revisited . Information Sciences , 199 : 133 { 137 , 2012 .

9. Radim Belohlavek and Vilem Vychodil . A logic of graded attributes. submitted to Arti cial Intelligence .

10. Didier Dubois and Henri Prade. Rough fuzzy sets and fuzzy rough sets . International Journal of General Systems , 17 ( 2 {3): 191 { 209 , 1990 .

11. Didier Dubois and Henri Prade. Putting rough sets and fuzzy sets together . In Roman Slowinski, editor, Intelligent Decision Support , volume 11 of Theory and Decision Library , pages 203 { 232 . Springer Netherlands, 1992 .

12. Bernard Ganter and Rudolf Wille . Formal Concept Analysis { Mathematical Foundations . Springer, 1999 .

13. George Georgescu and Andrei Popescu . Non-dual fuzzy connections . Arch. Math. Log. , 43 ( 8 ): 1009 { 1039 , 2004 .

14. Petr Hajek . Metamathematics of Fuzzy Logic (Trends in Logic) . Springer, November 2001 .

15. Robert E. Kent . Rough concept analysis: A synthesis of rough sets and formal concept analysis . Fundam. Inf. , 27 ( 2 ,3): 169 { 181 , August 1996 .

16. Hongliang Lai and Dexue Zhang . Concept lattices of fuzzy contexts: Formal concept analysis vs. rough set theory . International Journal of Approximate Reasoning , 50 ( 5 ): 695 { 707 , 2009 .

17. Zdzislaw Pawlak . Rough sets . International Journal of Computer & Information Sciences , 11 ( 5 ): 341 { 356 , 1982 .

18. Jesus Medina , Manuel Ojeda-Aciego, and Jorge Ruiz-Calvino. Formal concept analysis via multi-adjoint concept lattices . Fuzzy Sets and Systems , 160 ( 2 ): 130 { 144 , January 2009 .

19. Jonas Poelmans , Dmitry I. Ignatov , Sergei O. Kuznetsov , and Guido Dedene . Fuzzy and rough formal concept analysis: a survey . International Journal of General Systems , 43 ( 2 ): 105 { 134 , 2014 .

20. Silke Pollandt . Fuzzy Begri e: Formale Begri sanalyse von unscharfen Daten . Springer{Verlag, Berlin{Heidelberg, 1997 .

21. Andrei Popescu . A general approach to fuzzy concepts . Mathematical Logic Quarterly , 50 ( 3 ): 265 { 280 , 2004 .

22. Anna M. Radzikowska and Etienne E. Kerre . Fuzzy rough sets based on residuated lattices . In James F. Peters, Andrzej Skowron, Didier Dubois, Jerzy W. GrzymalaBusse, Masahiro Inuiguchi, and Lech Polkowski, editors, Transactions on Rough Sets II , volume 3135 of Lecture Notes in Computer Science, pages 278 { 296 . Springer Berlin Heidelberg, 2005 .

23. Morgan Ward and Robert P. Dilworth . Residuated lattices . Transactions of the American Mathematical Society , 45 : 335 { 354 , 1939 .

24. Yiyu Yao . On unifying formal concept analysis and rough set analysis . Xi'an Jiaotong University Press, 2006 .