Relations between Proto-fuzzy Concepts, Crisply Generated Fuzzy Concepts, and Interval Pattern Structures Vera V. Pankratieva and Sergei O. Kuznetsov State University Higher School of Economics, Pokrovskiy bd., 11, Moscow 101000, Russia, vera.pankratieva@gmail.com, skuznetsov@hse.ru Abstract. Relationships between proto-fuzzy concepts, crisply gener- ated fuzzy concepts, and pattern structures are considered. It is shown that proto-fuzzy concepts are closely related to crisply generated fuzzy concepts in the sense that the mappings involved in the definitions co- incide for crisp subsets of attributes. Moreover, a proto-fuzzy concept determines a crisp subset of attributes, which generates a (crisply gen- erated) fuzzy concept. However, the reverse is true only in part: given a crisp subset of attributes, one can find a proto-fuzzy concept whose intent includes (but not necessarily coincides with) the given subset of attributes. Interval pattern concepts are shown to be related to crisply generated formal concepts. In particular, every crisply closed subset of objects is an extent of an interval pattern concept. 1 Introduction Various approaches to extending the basic definitions of the Formal Concept Analysis to numerical and more complex data representations were proposed in the last three decades. An important direction of this research is related to fuzzy concept analysis, see [2] for an overview of various approaches to fuzzy concept lattices and some relationships between fuzzy concept lattices and con- cept lattices of l-cuts of formal fuzzy contexts. A relationship between ordinary Galois connections and fuzzy Galois connections was given in [3]. In this pa- per we try to establish relationships between most important notions of several approaches to fuzzy concept analysis. We show how crisply generated fuzzy con- cepts (R. Belohlavek, V. Sklenar, and J. Zacpal [4]), proto-fuzzy concepts (in- troduced by O. Kridlo and S. Krajci in [5]), and pattern structures (B. Ganter and S.O. Kuznetsov [6]), in particular interval pattern structures, are related. It is shown that proto-fuzzy concepts are closely related to crisply generated fuzzy concepts in the sense that the mappings involved in the definitions coincide for crisp subsets of attributes. Also, each proto-fuzzy concept determines a crisp subset of attributes, which generates a (crisply generated) fuzzy concept. How- ever, the reverse is true only in part: given a crisp subset of attributes, one can find a proto-fuzzy concept whose intent includes (but not necessarily coincides with) the given subset of attributes. Relations between Concepts 51 Interval pattern concepts, which are particular case of pattern structures, are shown to be related to crisply generated formal concepts. In particular, every crisply closed subset of objects is an extent of an interval pattern concept. The paper is organized as follows. The second section contains main defini- tions of FCA and their extensions to fuzzy data. The third section describes re- lations between crisply-generated fuzzy concepts and proto-fuzzy concepts. The relationship between fuzzy concepts and interval pattern concepts is described in the fourth section. 2 Fuzzy Contexts and Formal Concepts We start with a set X of objects, a set Y of attributes, and a fuzzy relation I between X and Y . This means that a truth degree I(x, y) ∈ L, where L is the set of values of some complete residuated lattice L, see, e.g., [1], is assigned to each pair (x, y), x ∈ X, y ∈ Y . The element I(x, y) is interpreted as the degree to which attribute y applies to object x. The triple hX, Y, Ii is called a formal fuzzy context. In paper [3] the following mappings are introduced. Fuzzy sets A ∈ LX and B ∈ LY are mapped into fuzzy sets A↑ ∈ LY and B ↓ ∈ LX according to the formulas V A↑ (y) = (A(x) → I(x, y)), x∈X ↓ V B (x) = (B(y) → I(x, y)) y∈Y for y ∈ Y and x ∈ X. Definition 1 ([4]). A formal fuzzy concept hA, Bi consists of a fuzzy set A of objects (the extent of the concept) and a fuzzy set B of attributes (the concept intent) such that A↑ = B and B ↓ = A. The set of all formal fuzzy concepts is denoted by B(X, Y, I). Definition 2 ([4]). A formal fuzzy concept hA, Bi ∈ B(X, Y, I) is said to be crisply generated if there exists a crisp subset Bc ⊆ Y such that A = Bc↓ (thus, B = Bc↓↑ ). Strictly speaking, such crisply generated concepts should be called crisply attribute-generated fuzzy concepts in contrast to crisply object-generated fuzzy concepts which can be defined in a similar way. There is another approach to generalization of formal concept analysis to the case of fuzzy contexts, which was developed in paper [5]. Given a fuzzy context hX, Y, Ii, define its l-cuts Il , l ∈ L, as Il = {(x, y) ∈ X × Y : I(x, y) ≥ l} and introduce the mappings ↑l : 2X → 2Y and ↓l : 2Y → 2X : ↑l (A) = {y ∈ Y : (∀x ∈ A)I(x, y) ≥ l}, A ⊆ X, ↓l (B) = {x ∈ X : (∀y ∈ B)I(x, y) ≥ l}, B ⊆ Y. 52 Vera V. Pankratieva, Sergei O. Kuznetsov Definition 3 ([5]). A pair hA, Bi ∈ 2X × 2Y is called an l-concept if and only if ↑l (A) = B and ↓l (B) = A, which means that the pair hA, Bi is a formal concept in the l-cut hX, Y, Il i, which is a binary context. The set of all concepts in the l-cut is denoted by Kl . S Definition 4 ([5]). Triples hA, B, li ∈ 2X × 2Y × L such that hA, Bi ∈ Kk k∈L and l = sup{k ∈ L : hA, Bi ∈ Kk } are called proto-fuzzy concepts. The set of all proto-fuzzy concepts is denoted by KP . Definition 5 ([5]). Let B ⊆ Y be an arbitrary set of attributes. We define the contraction of the set of proto-fuzzy concepts subsistent to the set B as P KB = {hA, li ∈ 2X × L : (∃B ′ ⊇ B)hA, B ′ , li ∈ KP }. P Thus, the elements of the set KB are proto-fuzzy concepts (in the fuzzy context hX, Y, Ii) “contracted to the subset B.” Definition 6 ([5]). Define the mappings ⇑: LX → 2Y , ⇓: 2Y → LX as follows: for any subset A of objects and any subset B of attributes let [ P ⇑ (Ã) = {B ⊆ Y : (∀x ∈ X)(∃hA, li ∈ KB x ∈ A & l ≥ Ã(x)}; P ⇓ (B)(x) = sup{l ∈ L : (∃hA, li ∈ KB ), x ∈ A}. The mapping ⇑ takes a fuzzy subset of objects à to a (crisp) set of at- tributes B ⊆ Y . The mapping ⇓ takes a crisp subset of attributes B ⊆ Y to a fuzzy subset of objects Ã. 3 Relationship between crisply generated fuzzy concepts and proto-fuzzy concepts Consider a fuzzy context hX, Y, Ii with k objects and n attributes (i.e., |X| = k, |Y | = n) b1 b2 · · · bn a1 d11 d12 . . . d1n a2 d21 d22 . . . d2n .. .. . . ak dk1 dk2 . . . dkn Relations between Concepts 53 and take some (crisp) intent B ⊆ Y to which some proto-fuzzy concepts may be contracted. To compute ⇓ (B), we write the set B in the form of an n-tuple (b1 , b2 , . . . , bn ), where bi = 1 if and only if the intent B contains the ith attribute. Then P ⇓ (B)(x) = sup{l ∈ L : (∃hA, li ∈ KB ) x ∈ A}. Evaluating ⇓ (B) at the element x1 gives P ⇓ (B)(x1 ) = sup{l ∈ L : (∃hA, li ∈ KB ) x1 ∈ A}. This means that it is necessary to find a cut that corresponds to the maximum value of l and contains a proto-fuzzy concept (including the elements of the top row) which may be contracted to B. In order that all entries d1j that correspond to unit jth attributes be con- tained in some l-cut, it is necessary that the condition V d1j ≥ l be satisfied for all such indices j. If we take the infimum d∗ = d1j over all j such that bj =1 bj = 1, then all d1j are not less than d∗ . Therefore, all d1j are contained in the d∗ -cut and, hence, they belong to some proto-fuzzy concept in this cut. Such proto-fuzzy concept may consist of the top row contracted to B, unless it may be extended to other rows to form a rectangular (i.e., if the contraction of any other row to B contains elements which are less than d∗ ). It may also happen that the d∗ -cut contains a rectangular that consists of at least two rows and can be contracted to B. Such rectangular presents a proto-fuzzy concept, since this ∗ is a formal concept which doesV not occur higher than at the d -cut. Thus, a1 =⇓ (B)(x1 ) = d1j . bj =1 The same for all other objects xi . As a result, we arrive at a fuzzy set   ^ ^ ^ ⇓ (B) = (a1 , a2 , . . . , ak ) =  d1j , d2j , · · · dkj  . bj =1 bj =1 bj =1 Now let us compute the result of the mapping ↓ applied to the crisp set of attributes B = (b1 , b2 , . . . , bn ): ^ B ↓ (x) = (B(y) → I(x, y)). y∈Y Here and in what follows, computations are performed in the framework of the lattice with the L à ukasiewicz logical connectives (however, most of the statements seem to hold also for the general case), so a → b = min{1 − a + b, 1}, and a ∧ b = min{a, b}. Let us compute B ↓ (x1 ) — the result of the evaluation of the mapping ↓ at the element x1 : ^ ^ B ↓ (x1 ) = (B(y) → I(x1 , y)) = (b1 → d11 , b2 → d12 , . . . , bn → d1n ). y∈Y The values bj that are equal to zero are inessential, since the corresponding implication evaluates to 1: min{1 − 0 + d1j , 1} = 1. For the values bj which are 54 Vera V. Pankratieva, Sergei O. Kuznetsov equal to 1, we have bj → d1j = 1 − 1 + d1j = d1j . Thus, to determine the result of the mapping, it is necessary V to find the infimum over all elements of the top row. Therefore, B ↓ (x1 ) = d1j . The same for all other objects. bj =1 As a result, we obtain   ^ ^ ^ B ↓ = (a1 , a2 , . . . , ak ) =  d1j , d2j , . . . , dkj  . bj =1 bj =1 bj =1 Thus, we arrive at Theorem 1. The mapping ⇓ coincides with the mapping ↓ restricted to crisp subsets of attributes.1 For an arbitrary k-tuple A = (a1 , . . . , ak ) by l A = (l a1 , . . . , l ak ) we denote the l-cut of A, i.e., the crisp k-tuple whose components are defined as ( l 1, aj ≥ l, aj = 0, aj < l. W W Theorem 2. Let A = (a1 , . . . , ak ) = Bc↓ , B = Bc↓↑ . Denote l = Bc↓ = ai and consider the set Z = (z1 , . . . , zk ) such that zi = 0 if ai < l and zi = 1 if ai = l. Then (z1 , z2 , . . . , zk ) × 1 B corresponds to some proto-fuzzy concept in the l-cut that may be contracted to 1 B. Proof. Consider the rows that correspond to ai = l. The elements that stay at the intersection of these rows with 1 B belong to the l-cut. This rectangular cannot be extended to other rows, since any other row contracted to 1 B contains elements which are less than l. However, it may happen that it may be extended to columns which correspond to zero components of Bc . In the case of such extension we obtain in the l-cut a proto-fuzzy concept which may be contracted to Bc . ⊓ ⊔ Remark 1. The statement that this procedure gives a proto-fuzzy concept (rather than a contraction of one) is, in general, not valid. Example. Consider a fuzzy context and its 0.5-cut given by the following tables: 1 0.7 1 0.7 0.5-cut 0.2 0.2 0.2 0.5 0.7 XX 0.3 0.3 0 0.7 0.8 XX 0.5 0.5 0.8 0.8 0.2 XXX 0.5 0.5 0.7 0.7 0.4 XXX 1 When this text was already prepared for publication, the authors discovered the work [7], which contains related results. Relations between Concepts 55 Take Bc = (1, 0, 1, 0).WThen Bc↓ = A = (0.2, 0.3, 0.5, 0.5); A↑ = B = (1, 0.7, 1, 0.7); ↓ B = (0.2, 0.3, 0.5, 0.5); ai = 0.5; Z = (0, 0, 1, 1). As a result, Z × Bc = (0, 0, 1, 1) × (1, 0, 1, 0) corresponds to the context 0000 0000 1010 1010 Theorem 3. Let A = (a1 , . . . , ak ) = Bc↓ and B = Bc↓↑ . For any i, 1 ≤ i ≤ k, specify a k-tuple Zi by the formula ( j 1, aj ≥ ai , zi = 0, aj < ai . Then the context Zi × Bc corresponds to a proto-fuzzy concept in the ai -cut of the original context, which may be contracted to Bc . The proof of this theorem is similar to that of Theorem 2. Theorem 4. Suppose that the l-cut contains a proto-fuzzy formal concept. Then there exists an n-tuple Bc satisfying the following conditions: 1. Bc↓ = (a1 , . . . , ak ), where ai ≥ l if this proto-fuzzy concept involves the ith object and ai < l, otherwise; 2. the n-tuple Bc is closed with respect to crisp components (or just crisply closed); that is, 1 (Bc↓↑ ) = Bc . Proof. Define the n-tuple Bc = (b1 , . . . , bn ) as follows: bi = 1 if and only if the given proto-fuzzy concept involves the ith attribute. Then, in accordance with the definition of a proto-fuzzy concept, we have Bc↓ = A = (a1 , . . . , ak ), where ai ≥ l if this proto-fuzzy concept involves the ithe object and ai < l, otherwise. Let us show that the n-tuple Bc obtained in this way satisfies Property 2. Suppose, by contradiction, that there is an attribute j such that Bc (j) = bj = 0 and Bc↓↑ (j) = 1. Then there exists an object i that belongs to the given formal concept and satisfies the condition dij < l (or else the attribute j belongs to the given formal concept and Bc (j) = bj = 1). Now, taking into account the inequality Bc↓ (i) ≥ l, we obtain Bc↓↑ (j) ≤ 1 − Bc↓ (i) + dij ≤ 1 − l + dij < 1 − l + l = 1. This estimate means that the n-tuple 1 (Bc↓↑ ) has no nonzero components other than those of Bc . ⊓ ⊔ 56 Vera V. Pankratieva, Sergei O. Kuznetsov By Theorem 3 the context l A × Bc may be considered a contraction of some proto-fuzzy concept to Bc . In order to find out whether the context l A × Bc determines a proto-fuzzy concept or a contraction of some proto-fuzzy concept, we consider the closure B = A↑c of the crisp n-tuple l A = Ac . Following the lines of the proof of Theo- rem 3 one can show that the context Ac × l B is a contraction of some proto-fuzzy concept to Ac . On the other hand, the n-tuple Ac = l A was defined as the l-cut of the n- tuple A, which is the closure of the crisp n-tuple Bc of attributes. For this reason, the n-tuple Ac cannot be majorized by a greater (crisp) n-tuple “possessing” the attributes Bc and, therefore, the context Ac × l B cannot be considered a nontrivial contraction of some proto-fuzzy concept to Ac . 4 Relationship between fuzzy formal concepts and pattern structures Definition 7. Let G be a set of an arbitrary nature, (D, ⊓) be a meet-semilattice, and let there be a mapping δ : G → D. The triple (G, D, δ), where D = (D, ⊓), is called a pattern structure, provided that the set δ(G) := {δ(g)|g ∈ G} generates a complete subsemilattice (Dδ , ⊓) of (D, ⊓). Each complete semilattice of this kind has lower and upper bounds, which we denote by 0 and 1, respectively. For a pattern structure (G, D, δ) we define the derivation operators acting on subsets A ⊆ G as l A¤ := δ(g) g∈A and on the semilattice elements d ∈ D as d¤ := {g ∈ G|d ⊑ δ(g)}. Example. Consider the following fuzzy context: object 1 0.2 0.2 0.5 0.7 object 2 0.3 0 0.7 0.8 object 3 0.5 0.8 0.8 0.2 object 4 0.5 0.7 0.7 0.4 Relations between Concepts 57 The set G is the set of all objects. The closure operator applied to a sub- set A of objects gives an n-tuple (the length of which is equal to the number of attributes — in this case, n = 4) of shortest intervals which cover the values of the corresponding attributes for all objects of the subset A. For instance, for the subset A = {1, 2} of objects we have {1, 2}¤ = d12 = {[0.2; 0.3], [0; 0.2], [0.5; 0.7], [0.7; 0.8]} and d¤12 = {1, 2}. As in the binary case, a pair (A, d), A ⊆ G, d ∈ D, satisfying the conditions A¤ = d, d¤ = A, is said to comprise a pattern concept. Thus, the pair ({1, 2}, {[0.2; 0.3], [0; 0.2], [0.5; 0.7], [0.7; 0.8]}) is a pattern concept. Now let us compute {1, 3}¤ . We have {1, 3}¤ = d13 = {[0.2; 0.5], [0.2; 0.8], [0.5; 0.8], [0.2; 0.7]} and d¤ 13 = {1, 3, 4}. Subsets of objects may be considered as crisp n-tuples (of objects), where n = |G|, extents are then closed crisp n-tuples. Object implication is defined as usual: for sets A, C ⊆ G we write A → C iff A¤ ⊑ C ¤ , where ⊑ is a natural subsumption relation associated to ⊓: X ⊑ Y iff X ⊓ Y = X. In particular, there is an object implication ai → aj (ai , aj ∈ G) if the row of the context corresponding to ai (i.e., a¤ i ) is component-wise smaller than the row of the context corresponding to aj (i.e., a¤ j ). Theorem 5. If the set of all extents of interval pattern concepts coincides with the set of all crisply closed n-tuples, then the context contains no implications. Proof. Assume that all (crisp) n-tuples that correspond to closed subsets of objects (i.e., such that A¤¤ = A) are crisply closed and there are no other crisply closed n-tuples. Then suppose, by contradiction, that the formal context contains an implication ai → aj . Since the context contains no identical rows, all objects are closed. In particular, a¤¤ i = ai . Consider the crisp n-tuple Ai that corresponds to the object ai (0, . . . , 0, 1, 0, . . . , 0) | {z } | {z } i−1 n−i and its image A↑i under the mapping ↑. It is easily seen that A↑i is a fuzzy n- tuple that coincides with the ith row of the context. Since every component of the fuzzy n-tuple A↑i is not greater than the corresponding component of the jth row, the closure A↑↓i contains 1 at the jth component. Thus, the n-tuple Ai is not crisply closed. The contradiction obtained proves the theorem. ⊓ ⊔ Theorem 6. For any crisply closed n-tuple the corresponding subset of objects is closed. 58 Vera V. Pankratieva, Sergei O. Kuznetsov Proof. Consider an arbitrary crisply closed n-tuple A. The tuple A↑ consists of the row minima for the support of the crisp n-tuple A. The fact that A is crisply closed means that A↑↓ = A, that is, none of the rows dominate A↑ . Hence, the corresponding extent is closed, since no other row falls within the interval between the minimum and the maximum values. ⊓ ⊔ Thus, the set of crisply closed n-tuples is contained in the set of extents of interval formal concepts. Corollary 1. In order that the set of crisply closed n-tuples coincide with the set of extents of interval pattern concepts it is necessary that each pattern concept satisfy the following condition: the minima of the intervals comprise an n-tuple which is not less than any object intent of an object not contained in the extent of the interval pattern concept. Proof. Follows directly from Theorems 5 and 6. ⊓ ⊔ 5 Conclusions In this work, we studied relations between various generalizations of formal con- cept analysis to the case of numerical values. The known approaches include proto-fuzzy concepts, crisply generated fuzzy concepts, and pattern structures. It was shown that proto-fuzzy concepts and fuzzy concepts have much in common: the mappings involved in their definitions coincide for crisp subsets of attributes. Also, each proto-fuzzy concept determines a crisp subset of attributes, which generates a (crisply generated) fuzzy concept. However, the reverse is true only in part: any crisp subset of attributes is a contraction of the intent of some proto-fuzzy concept, but not necessarily the intent itself. Interval pattern concepts, which are particular case of pattern structures, were shown to be related to crisply generated formal concepts. In particular, every crisply closed subset of objects is an extent of an interval pattern concept. Sufficient conditions are derived under which no other extents of interval pattern concepts exist. Further research in this area would go in the following directions: – introduce “two-sided” (double) pattern structures and study their relation- ship with fuzzy formal concepts; – find a minimal (canonical) fuzzy context that induces a lattice of fuzzy con- cepts isomorphic to a given one; – elaborate new methods for fuzzy data analysis on the basis of the results obtained. References 1. Hájek, P., Metamathematics of Fuzzy Logic, Kluwer, Dordrecht, 1998. Relations between Concepts 59 2. Bělohlávek, R., Vychodil V.: What is a fuzzy concept lattice?, in CLA 2005, pp. 34-45, 2005. 3. Belohlavek R.: Fuzzy Galois connections. Math. Logic Quarterly 45,4 (1999), 497- 504. 4. Bělohlávek, R., Sklenář, V., Zacpal, J.: Crisply Generated Fuzzy Concepts, in: B. Ganter and R. Godin (Eds.): ICFCA 2005, LNCS 3403, pp. 268–283, 2005 (Springer-Verlag, Berlin, Heidelberg, 2005). 5. O. Krı́dlo, S. Krajči, Proto-fuzzy Concepts, Their Retrieval and Usage, in: B. Gan- ter and R. Godin (Eds.): CLA 2008, pp. 83–95, ISBN 978-80-244-2111-7, Palacký University, Olomouc, 2008. 6. B. Ganter and S.O. Kuznetsov, Pattern Structures and Their Projections, preprint MATH-AL-14-2000, Technische Universität Dresden, Herausgeber, Der Rektor, November 2000. 7. O. Krı́dlo, S. Krajči, Fuzzy concept lattice is made by proto-fuzzy concepts, in: J.P. Carvalho, D. Dubois, U. Kaymak, and J.M.C. Sousa (Eds.): Proceedings of the Joint 2009 International Fuzzy Systems Association World Congress and 2009 European Society of Fuzzy Logic and Technology Conference, Lisbon, Portugal, July 20-24, 2009, pp. 1252–1257.