Relations between Proto-fuzzy Concepts, Crisply Generated Fuzzy Concepts, and Interval Pattern Structures

Abstract

Relationships between proto-fuzzy concepts, crisply generated 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 coincide for crisp subsets of attributes. Moreover, a proto-fuzzy concept determines a crisp subset of attributes, which generates a (crisply generated) 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.

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 concept lattices of l-cuts of formal fuzzy contexts. A relationship between ordinary Galois connections and fuzzy Galois connections was given in [ 3 ]. In this paper we try to establish relationships between most important notions of several approaches to fuzzy concept analysis. We show how crisply generated fuzzy concepts (R. Belohlavek, V. Sklenar, and J. Zacpal [ 4 ]), proto-fuzzy concepts (introduced 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. 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, 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 relations 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

A↑(y) =

V (A(x) → I(x, y)), x∈X B↓(x) = V (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 = B↓ c (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}, ↓l (B) = {x ∈ X : (∀y ∈ B)I(x, y) ≥ l}, A ⊆ X, 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, Ili, which is a binary context. The set of all concepts in the l-cut is denoted by Kl.

Definition 4 ([ 5 ]). Triples hA, B, li ∈ 2X × 2Y × L such that hA, Bi ∈ S 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

KBP = {hA, li ∈ 2X × L : (∃B′ ⊇ B)hA, B′, li ∈ KP }.

Thus, the elements of the set KBP 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 ⇑ (A˜) = [{B ⊆ Y : (∀x ∈ X)(∃hA, li ∈ KBP x ∈ A & l ≥ A˜(x)}; ⇓ (B)(x) = sup{l ∈ L : (∃hA, li ∈ KBP), x ∈ A}.

The mapping ⇑ takes a fuzzy subset of objects A˜ to a (crisp) set of attributes B ⊆ Y . The mapping ⇓ takes a crisp subset of attributes B ⊆ Y to a fuzzy subset of objects A˜. 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) 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

⇓ (B)(x) = sup{l ∈ L : (∃hA, li ∈ KBP) x ∈ A}.

Evaluating ⇓ (B) at the element x1 gives

⇓ (B)(x1) = sup{l ∈ L : (∃hA, li ∈ KBP) 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 contained in some l-cut, it is necessary that the condition d1j ≥ l be satisfied for all such indices j. If we take the infimum d∗ = V 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 does not occur higher than at the d∗-cut.

Thus, a1 =⇓ (B)(x1) = V 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

equal to 1, we have bj → d1j = 1 − 1 + d1j = d1j . Thus, to determine the result of the mapping, it is necessary to find the infimum over all elements of the top row. Therefore, B↓(x1) = V 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 lA = (la1, . . . , lak) we denote the l-cut of A, i.e., the crisp k-tuple whose components are defined as laj = (1, 0, aj ≥ l, aj < l.

Theorem 2. Let A = (a1, . . . , ak) = B↓, B = Bc↓↑. Denote l = W Bc↓ = W ai c and consider the set Z = (z1, . . . , zk) such that zi = 0 if ai < l and zi = 1 if ai = l. Then (z1, z2, . . . , zk) × 1B corresponds to some proto-fuzzy concept in the l-cut that may be contracted to 1B.

Proof. Consider the rows that correspond to ai = l. The elements that stay at the intersection of these rows with 1B belong to the l-cut. This rectangular cannot be extended to other rows, since any other row contracted to 1B 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.2 0.2 0.2 0.5 0.7 0.3 0.3 0 0.7 0.8 0.5 0.5 0.8 0.8 0.2 0.5 0.5 0.7 0.7 0.4 0.5-cut

X X

X X X X X X X X 1 When this text was already prepared for publication, the authors discovered the work [ 7 ], which contains related results.

Take Bc = (1, 0, 1, 0). Then 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); W 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 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 Theorem 3. Let A = (a1, . . . , ak) = Bc↓ and B = Bc↓↑. For any i, 1 ≤ i ≤ k, specify a k-tuple Zi by the formula zij = (1, 0, aj ≥ ai, 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. ⊓⊔

By Theorem 3 the context lA × Bc may be considered a contraction of some

proto-fuzzy concept to Bc.

In order to find out whether the context lA × Bc determines a proto-fuzzy concept or a contraction of some proto-fuzzy concept, we consider the closure B = Ac↑ of the crisp n-tuple lA = Ac. Following the lines of the proof of Theorem 3 one can show that the context Ac × lB is a contraction of some proto-fuzzy concept to Ac.

On the other hand, the n-tuple Ac = lA was defined as the l-cut of the ntuple 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 × lB 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

Example. Consider the following fuzzy context:

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 and on the semilattice elements d ∈ D as

The triple where D = (D, ⊓), is called a pattern structure, provided that the set δ : G → D.

(G, D, δ), δ(G) := {δ(g)|g ∈ G}

A¤ := l δ(g)

g∈A d¤ := {g ∈ G|d ⊑ δ(g)}. 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

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 d12 = {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 d1¤3 = {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., ai¤) is component-wise smaller than the row of the context corresponding to aj (i.e., aj¤).

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, ai¤¤ = ai. Consider the crisp n-tuple Ai that corresponds to the object ai (0, . . . , 0, 1, 0, . . . , 0) | i{−z1 } | n{−zi } and its image Ai↑ under the mapping ↑. It is easily seen that Ai↑ is a fuzzy ntuple that coincides with the ith row of the context. Since every component of the fuzzy n-tuple Ai↑ is not greater than the corresponding component of the jth row, the closure A↑↓ contains 1 at the jth component. Thus, the n-tuple Ai is i not crisply closed. The contradiction obtained proves the theorem. ⊓⊔ Theorem 6. For any crisply closed n-tuple the corresponding subset of objects is closed.

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 relationship with fuzzy formal concepts; – find a minimal (canonical) fuzzy context that induces a lattice of fuzzy concepts isomorphic to a given one; – elaborate new methods for fuzzy data analysis on the basis of the results obtained.

References

1. H´ajek, P. , Metamathematics of Fuzzy Logic , Kluwer, Dordrecht, 1998 .

2. Bˇelohl´avek, 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ˇelohl´avek, R., Sklen´aˇr, 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ˇci, Proto-fuzzy Concepts , Their Retrieval and Usage , in: B. Ganter and R. Godin (Eds.): CLA 2008 , pp. 83 - 95 , ISBN 978-80-244-2111-7, Palacky´ University, Olomouc, 2008 .

6. B. Ganter and S.O. Kuznetsov , Pattern Structures and Their Projections, preprint MATH-AL-14-2000 , Technische Universit¨at Dresden, Herausgeber, Der Rektor, November 2000 .

7. O. Kr ´ıdlo, S. Krajˇci, 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 .