Relationship between Two FCA Approaches on Heterogeneous Formal Contexts⋆

Abstract

We show a relationship between two theoretical approaches of Formal Concept Analysis working with so-called heterogeneous formal context i.e. such context in which each object and attribute can have own data-type. One of them is presented in [19]; each value in a formal context is some Galois connection between the lattices corresponding to the appropriate object and attribute. Another approach is presented in our paper [1] and it is a unifying platform of approaches from [14] and [11], [12]. In this paper, we prove that each of them can be derived from another.

Keywords

• Formal Concept Analysis
• Galois connection
• G-ideal

Introduction

The Formal Concept Analysis is a well-known data-mining method on a rectangle matrix of data where each row corresponds to some object, each column corresponds to some attribute and a matrix field value expresses the presence of the column attribute to the row object. One of the goals of this method is to find so-called concepts – the stable (in some sense) pairs of subsets of objects and attributes. This method can be considered as a nice application of the algebraic notion of a Galois connection. The Formal Concept Analysis is based and deeply described in the classical Ganter & Wille’s book [ 9 ] where authors concentrate mainly to the so-called crisp case with binary data in the matrix. The natural question arose: What if the matrix data have a non-binary character? c 2012 by the paper authors. CLA 2012, pp. 93–102. Copying permitted only for private and academic purposes. Volume published and copyrighted by its editors. Local Proceedings in ISBN 978–84–695–5252–0, Universidad de M´alaga (Dept. Matem´atica Aplicada), Spain.

Beside the conceptual scaling from [ 9 ] which returns concepts with crisp subsets in both coordinates, some other answers arose which return concepts with fuzzy subsets at least in one coordinate: The first one was done by Burusco & Fuentes-Gonzalez [ 8 ] and it was improved (independently) by Bˇelohl´avek [ 2 ], [ 3 ] and Pollandt [ 21 ], [ 22 ] which use values from the same residual lattice for values of the matrix and for the fuzziness of subsets of the objects and the attributes. Another approach independently (and with slight differences) given by Ben Yahia & Jaoua [ 7 ], Bˇelohl´avek, Sklen´aˇr, & Zacpal [ 4 ], and Krajˇci [ 10 ] was not so symmetric – it considers fuzzy subsets in one coordinate and crisp (binary) subsets in another one. All these approaches where covered by a common platform – socalled generalized concept lattices [ 12 ], [ 13 ] which diversifies fuzziness of subsets of the attributes, fuzziness of subsets of the objects and moreover fuzziness of the matrix values.

Then Medina and Ojeda-Aciego brought the idea of multi-adjointness used in logic-programming [ 16 ], [ 17 ], [ 18 ] to the Formal Concept Analysis too [ 14 ], [ 15 ]. Because of this novelty and originality, this approach is not (at least immediately) covered by the above-mentioned generalized concept lattices.

This fact has inspired us to modify our old approach in such a way that this will work with different mutual relationships between the objects and the attributes. Moreover we work with different lattices for different rows and columns and for the matrix data. To compare with the till known approaches which works with attributes and objects of the same type, an important advantage of this new, totally diversifying, approach is the possibility to apply the Formal Concept Analysis to heterogeneous data too. This is the reason why we will call this new approach heterogeneous. We have described this approach in [ 1 ] and recall it in Section 2.

Another answer to the problem of data heterogeneity was given by [ 19 ] and [ 20 ]. In this approach, each datum in a formal context are not a simple number or other singular value but (sic!) a Galois connection which describes in a some way the behavior between the corresponding object and attribute. We recall this approach in Section 3. 2

Heterogeneous formal context

In this section we recall the basic definitions and results from [ 1 ].

Let A and B be non-empty sets. Let P = ((Pa,b, ≤Pa,b ) : a ∈ A, b ∈ B) be a system of posets and let R be a function from A×B such that R(a, b) ∈ Pa,b, for all a ∈ A and b ∈ B. Let C = ((Ca, ≤Ca ) : a ∈ A) and D = ((Db, ≤Db ) : b ∈ B) be systems of complete lattices. (For simplicity, we will omit the indices of all noticed ≤?, it will be always clear which of one is used.)

Let ⊙ = ((•a,b) : a ∈ A, b ∈ B) be a system of operations such that •a,b is from Ca × Db to Pa,b and it is isotone and left-continuous in both arguments, i. e. 1a) c1 ≤ c2 implies c1 •a,b d ≤ c2 •a,b d for all c1, c2 ∈ Ca and d ∈ Db, 1b) d1 ≤ d2 implies c •a,b d1 ≤ c •a,b d2 for all c ∈ Ca and d1, d2 ∈ Db, 2a) if c •a,b d ≤ p for some d ∈ Db, p ∈ Pa,b and for all c ∈ X ⊆ Ca then sup X •a,b d ≤ p, 2b) if c •a,b d ≤ p for some c ∈ Ca, p ∈ Pa,b and for all d ∈ Y ⊆ Db then c •a,b sup Y ≤ p.

Then the tuple hA, B, P, R, C, D, ⊙i will be called a heterogeneous formal context.

Notice that if Ca = Db and •a,b is commutative these conditions can be reduced to these two: 1) c1 ≤ c2 implies c1 •a,b d ≤ c2 •a,b d for all c1, c2, d ∈ Ca = Db, 2) if c •a,b d ≤ p for some d ∈ Ca = Db, p ∈ P and for all c ∈ X ⊆ Ca = Db then sup X •a,b d ≤ p.

Let F be the set of all functions f with the domain A such that f (a) ∈ Ca, for all a ∈ A (i. e., more formally, F = Qa∈A Ca) and G be the set of all functions g with the domain B such that g(b) ∈ Db, for all b ∈ B. (i. e. G = Qb∈B Db).

Define the following mapping ր : G → F : If g ∈ G then ր(g) ∈ F is defined by = ^ ր(gi).

i∈I 2) Let {fi : i ∈ I} ⊆ F . Then ւ _ fi ! = ^ ւ(fi).

i∈I

By a concept we will understand a pair hg, f i from G × F such that ր(g) = f and ւ(f ) = g.

Lemma 2. If hg1, f1i and hg2, f2i are concepts then g1 ≤ g2 iff f1 ≥ f2.

This lemma allows to define the following ordering of concepts: hg1, f1i ≤ hg2, f2i iff g1 ≤ g2 (or equivalently f1 ≥ f2).

The poset of all such concepts ordered by ≤ will be called a heterogeneous concept lattice and denoted by HCL(A, B, P, R, C, D, ⊙, ւ, ր, ≤).

The following theorem shows that the word lattice in its name corresponds with reality.

Theorem 2. (The Basic Theorem on Heterogeneous Concept Lattices) 1) A heterogeneous concept lattice HCL(A, B, P, R, C, D, ⊙, ւ, ր, ≤) is a complete lattice in which and * * In this section, we recall the basic definitions and results of approach from [ 19 ], [ 20 ] which is inspired by the (homogeneous) approach from [ 23 ].

Let A and B be non-empty sets. Let C = ((Ca, ≤Ca ) : a ∈ A) and D = ((Db, ≤Db ) : b ∈ B) be systems of complete lattices. Let G = ((φa,b, ψa,b) : a ∈ A, b ∈ B) be a system of (antitone) Galois connection s.t. (φa,b, ψa,b) is a Galois connection from (Ca, ≤Ca ) to (Db, ≤Db ). (Again we will omit the indices of all noticed ≤?.)

Define the following mapping ↑ : G → F : If g ∈ G then ↑(g) ∈ F is defined by (↑(g))(a) = ^ ψa,b(g(b)).

b∈B and

* α(a, c) ≥ β(b, d) iff d ≤ φa,b(c) iff c ≤ ψa,b(d). 4

Heterogeneous approach can be expressed by connectional one In this section, we modify method from [ 19 ] which was used for the proof that connectional approach covers a generalized approach from [ 11 ] and [ 12 ]. It used a notion of G-ideals defined in [ 24 ].

Let (L, ≤L), (M, ≤M ) be complete lattices. Then J ⊆ L × M is called a G-ideal of L × M when the following conditions hold: 1) If (ℓ, m) ∈ J and (ℓ′, m′) ≤ (ℓ, m) (coordinate-wise, i.e. ℓ′ ≤ ℓ and m′ ≤ m) then (ℓ′, m′) ∈ J . 2) If {(ℓi, mi) : i ∈ I} ⊆ J then (Wi∈I ℓi, Vi∈I mi), (Vi∈I ℓi, Wi∈I mi) ∈ J .

If I = ∅ then (0L, 1M ), (1L, 0M ) ∈ J .

Theorem 5. [ 24 ] Let (L, ≤L), (M, ≤M ) be complete lattices. 1) If (φ, ψ) is an (antitone) Galois connection from (L, ≤L) to (M, ≤M ) then {(ℓ, m) : φ(ℓ) ≥M m} = {(ℓ, m) : ψ(m) ≥L ℓ} is a G-ideal on L × M . 2) If J is a G-ideal on L × M then the mappings φ : L → M and ψ : M → L defined by and φ(ℓ) = _{m ∈ M : (ℓ, m) ∈ J } ψ(m) = _{ℓ ∈ L : (ℓ, m) ∈ J } form a Galois connection from (L, ≤L) to (M, ≤M ).

Moreover, this correspondences between Galois connections and G-ideals are each other inverse.

The paper [ 19 ] uses these facts in the following way: Lemma 4. Let (L, ≤L), (M, ≤M ) be complete lattices, (P, ≤P ) be poset and • : L × M → P is isotone and left-continuous in both arguments. Then {(ℓ, m) : ℓ • m ≤ p} is a G-ideal.

Assume that we have a heterogeneous concept lattice HCL(A, B, P, R, C, D, ⊙, ւ, ր, ≤). For each a ∈ A and b ∈ B define

Ja,b = {(c, d) ∈ Ca × Db : c •a,b d ≤ R(a, b)}, by the previous Lemma 4 we know that Ja,b is a G-ideal on Ca × Db. Then again for each a ∈ A and b ∈ B define the mappings φa,b : Ca → Db and ψa,b : Db → Ca defined by

φa,b(c) = _{d ∈ Db : (c, d) ∈ Ja,b} and

ψa,b(d) = _{c ∈ Ca : (c, d) ∈ Ja,b} and we know by Theorem 5 that (φa,b, ψa,b) is a Galois connection from Ca to Db. Finally, we define mappings ↓ and ↑ as before: (↑(g))(a) = ^ ψa,b(g(b)), b∈B and Denote and, for each b ∈ B, (↑(g))(a) = ^ ψa,b(g(b)) = ^ _{c ∈ Ca : (c, g(b)) ∈ Ja,b}

b∈B b∈B = ^ _{c ∈ Ca : c •a,b g(b) ≤ R(a, b)}

b∈B (ր(g))(a) = sup{c ∈ Ca : (∀b ∈ B)c •a,b g(b) ≤ R(a, b)}.

X = {c ∈ Ca : (∀b ∈ B)c •a,b g(b) ≤ R(a, b)}

Xb = {c ∈ Ca : c •a,b g(b) ≤ R(a, b)}, then we want to prove Vb∈B sup Xb = sup X. ≥ For each b ∈ B we have Xb ⊇ X hence sup Xb ≥ sup X. It follows that

Vb∈B sup Xb ≥ sup X. ≤ Let b ∈ B. Then for each c ∈ Xb we have c •a,b g(b) ≤ R(a, b). By the left-continuity of •a,b in the first argument we have sup Xb •a,b g(b) ≤ R(a, b). Because clearly Vb′∈B sup Xb′ ≤ sup Xb, by the isotonity of •a,b in the first argument Vb′∈B sup Xb′ •a,b g(b) ≤ R(a, b). This holds for each b ∈ B, which means that Vb′∈B sup Xb′ ∈ X, hence Vb′∈B sup Xb′ ≤ sup X. ⊔⊓ 5

Connectional approach can be expressed by heterogeneous one In this section we show opposite direction to the previous one, namely that the heterogeneous approach covers the connectional one, moreover by the surprisingly simply way.

Firstly, one fact from [ 24 ] analogous to Lemma 1: Lemma 5. Let (L, ≤L), (M, ≤M ) be complete lattices and (φ, ψ) be a Galois connection from (L, ≤L) to (M, ≤M ). 1) For arbitrary subset {ℓi : i ∈ I} of L 2) For arbitrary subset {mi : i ∈ I} of M ! ! φ _ ℓi i∈I = ^ φ(ℓi).

i∈I ψ _ mi i∈I = ^ ψ(mi).

i∈I

We use it in the following way: Theorem 7. Let (L, ≤L), (M, ≤M ) be complete lattices and (φ, ψ) be a Galois connection from (L, ≤L) to (M, ≤M ). Let • : L × M → ({0, 1}, ≤) be defined in the following way: ℓ • m = (0 if φ(ℓ) ≥ m (iff ψ(m) ≥ ℓ),

1 elsewhere.

Then • is isotone and left-continuous in both arguments.

Proof. Because of duality, it is enough to prove isotonity and left-continuity in the first argument.

– Let ℓ1, ℓ2 ∈ L where ℓ1 ≤ ℓ2 and m ∈ M . We want to prove that ℓ1 • m ≤ ℓ2 • m.

– If ℓ2 • m = 1, the inequality is trivial. – If ℓ2 •m = 0, then by the definition φ(ℓ2) ≥ m. Because (φ, ψ) be a Galois connection and ℓ1 ≤ ℓ2, we have φ(ℓ1) ≥ φ(ℓ2) which by transitivity implies φ(ℓ1) ≥ m. So, by the definition ℓ1 • m = 0 hence ℓ1 • m ≤ ℓ2 • m. – Let m ∈ M , X ⊆ L and ℓ • m ≤ p for all ℓ ∈ X. We want to prove that sup X • m ≤ p.

– If p = 1, the inequality is trivial. – If p = 0, then by the definition φ(ℓ) ≥ m for all ℓ ∈ X which means Vℓ∈X φ(ℓ) ≥ m. Because (φ, ψ) is a Galois connection, by Lemma 5 we have Vℓ∈X φ(ℓ) = φ(supℓ∈X ℓ). This implies φ(supℓ∈X ℓ) ≥ m, so, by the definition supℓ∈X ℓ • m = 0.

Assume that we have a connectional concept lattice CCL(A, B, C, D, G, ↓, ↑, ≤). For each a ∈ A and b ∈ B take the same Pa,b = ({0, 1}, ≤), R(a, b) = 0 (sic!) and •a,b : Ca × Db → Pa,b such that for all c ∈ Ca and d ∈ Db, c •a,b d = (0 if φa,b(c) ≥ d (iff ψa,b(d) ≥ c),

1 elsewhere.

By Theorem 7 •a,b is isotone and left-continuous in both arguments, so we have a frame for heterogeneous approach a we can define the mappings ր and ւ as before.

Proof. We prove ր = ↑ only, the second equality can be proved dually. Let g ∈ G and a ∈ A. Then by the definitions we have (ր(g))(a) = sup{c ∈ Ca : (∀b ∈ B)c •a,b g(b) ≤ R(a, b)} = = sup{c ∈ Ca : (∀b ∈ B)c •a,b g(b) ≤ 0} = = sup{c ∈ Ca : (∀b ∈ B)ψa,b(g(b)) ≥ c} = = sup{c ∈ Ca : ^ ψa,b(g(b)) ≥ c} = ^ ψa,b(g(b)) = (↑(g))(a).

b∈B b∈B ⊔⊓ 6

Conclusions

In this paper we recall two rather new common platform for till-known fuzzifications of the Formal Concept Analysis which work on the context without limitation of the same data-types of objects and/or attributes. The first one arises, defined in [ 1 ], as rather straightforward extension of the previous so-called generalized approach from [ 11 ] and [ 12 ] to such heterogeneous context. The second one, from [ 19 ] and [ 20 ] is based on interesting idea to put some Galois connection to each field of the table. We show that each of these two approaches covers and is covered by the other one (in some canonical way).

In the end, let us say one “philosophical” aspect about our approach (that from Section 2). In this case, a pair consisting of some • and some value is put into each field of the table. The part • can be understood as behavior of the corresponding object with respect to the corresponding attribute. This behavior can be known long before than data come to the table, hence it can be thought as metadata. Data can change through the time but this metadata are fixed. In other words, we divide information on relationship of an object and an attribute to the stable and dynamic part. (Of course, this division has meaning only in the case that we consider possible changing of the data in the table.) In our opinion, the connectional approach has not this advantage, because it mixes metadata and data parts.

Then we can formulate this problem: In Section 5 we can see a surprising (and maybe suspicious) transformation of connectional approach to heterogeneous with the data part constantly equal to 0, i.e. all this is transformed to metadata part. The question is: Is there some other (natural, canonical) transformation which is not constant?

References

1. L '. Antoni , S. Krajˇci, O. Kr´ıdlo, B. Macek , L. Piskova´, On heterogeneous formal contexts. Submitted to Fuzzy Sets and Systems .

2. R. Bˇelohla´vek, Fuzzy concepts and conceptual structures: induced similarities , JCIS′98 , Vol. I, pp. 179 - 182 , Durham, USA, 1998

3. R. Bˇelohl´avek, Concept Lattices and Order in Fuzzy Logic , Annals of Pure and Applied Logic , 128 ( 2004 ), 277 - 298

4. R. Bˇelohla´vek, V. Sklena´ˇr, J. Zacpal , Crisply generated fuzzy concepts , in: B. Ganter and R . Godin (Eds.): ICFCA 2005, Lecture Notes in Computer Science 3403 , pp. 268 - 283 , Springer-Verlag, Berlin/Heidelberg, 2005 .

5. R. Bˇelohla´vek, V. Vychodil, Reducing the size of fuzzy concept lattices by hedges , FUZZ-IEEE 2005 , USA, 663 - 668 , ISBN: 0 - 7803 -9159-4

6. R. Bˇelohla´vek, V. Vychodil, Formal concept analysis and linguistic hedges , submitted to International Journal of General Systems , 2012

7. S. Ben Yahia , A. Jaoua , Discovering knowledge from fuzzy concept lattice . In: Kandel A., Last M. , Bunke H. : Data Mining and Computational Intelligence , 169 - 190 , Physica-Verlag, 2001

8. A. Burusco , R. Fuentes-Gonzalez , The study of L-fuzzy concept lattice , Mathware & Soft Computing 3 ( 1994 ), 209 - 218

9. B. Ganter , R. Wille , Formal Concept Analysis , Mathematical Foundation, Springer Verlag 1999, ISBN 3-540-62771-5

10. S. Krajˇci, Cluster based efficient generation of fuzzy concepts , Neural Network World 13,5 ( 2003 ) 521 - 530

11. S. Krajˇci, A generalized concept lattice , Logic Journal of IGPL , 13 ( 5 ): 543 - 550 , 2005 .

12. S. Krajˇci, The basic theorem on generalized concept lattice , CLA 2004 , Ostrava , proceedings of the 2nd international workshop, eds. V. Sna´ˇsel, R. Bˇelohla´vek , ISBN 80-248-0597-9 , 25 - 33

13. S. Krajˇci, Every Concept Lattice With Hedges Is Isomorphic To Some Generalized Concept Lattice , CLA 2005, proceedings of CLA 2005 : The 3rd international conference on Concept Lattice and Their Applications, eds. V. Sn´aˇsel, R. Bˇelohla´vek , ISBN 80-248-0863-3 , 1 - 9

14. J. Medina , M. Ojeda-Aciego: Multi-adjoint t-concept lattices , Information Sciences 180 ( 5 ), pp. 712 - 725 , 2010 .

15. J. Medina , M. Ojeda-Aciego , J. Ruiz-Calvin˜o, Formal concept analysis via multiadjoint concept lattices . Fuzzy Sets and Systems , 160 ( 2 ), 130 - 144 , 2009 .

16. J. Medina , M. Ojeda-Aciego , A. Valverde , P. Vojta´ˇs, Towards biresiduated multiadjoint logic programming . Lect. Notes in Artificial Intelligence , 3040 : 608 - 617 , 2004 .

17. J. Medina , M. Ojeda-Aciego , P. Vojta´ˇs, Multi-adjoint logic programming with continuous semantics. Logic programming and Non-Monotonic Reasoning , LPNMR' 01 , 351 - 364 , Lect. Notes in Artificial Intelligence 2173 , 2001 .

18. J. Medina , M. Ojeda-Aciego , P. Vojta´ˇs, Similarity-based unification: a multiadjoint approach . Fuzzy Set and Systems , 146 : 43 - 62 , 2004 .

19. J. Po ´cs, Note on generating fuzzy concept lattices via Galois connections , Information Sciences 185 ( 1 ), pp. 128 - 136 , 2012 .

20. J. Po ´cs, On possible generalization of fuzzy concept lattices using dually isomorphic retracts , Information Sciences 210 , pp. 89 - 98 , 2012 .

21. S. Pollandt, Fuzzy Begriffe, Springer, 1997

22. S. Pollandt, Datenanalyse mit Fuzzy-Begriffen, in: G. Stumme, R. Wille: Begriffliche Wissensverarbeitung. Methoden und Anwendungen , Springer, Heidelberg 2000 , 72 - 98

23. A. Popescu , A general approach to fuzzy concepts , Mathematical Logic Quarterly 50 ( 3 ) ( 2004 ), pp. 265 - 280

24. Z. Shmuely , The structure of Galois connections , Pacific Journal of Mathematics , Vol. 54 , No. 2 , 1974 , pp. 209 - 225