WIXLIB

Remark 2.3.– Operator assigns subsets of Y to subsets of X. A is just the set ofall attributes shared by all objects from A.– Dually, operator assigns subsets of X to subsets of Y . B is the set of all objectssharing all attributes from B.– To emphasize that and are induced by hX, Y, Ii, we use I and I .Example 2.4 (concept-forming operators). For tableIx1x2x3x4x5y1 y2 y3 y4 we have:––––––2.3{x2 } {y1 , y3 , y4 }, {x2 , x3 } {y3 , y4 },{x1 , x4 , x5 } ,X , Y ,{y1 } {x1 , x2 , x5 }, {y1 , y2 } {x1 },{y2 , y3 } {x1 , x3 , x4 }, {y2 , y3 , y4 } {x1 , x3 , x4 }, X, Y {x1 }.Formal Concepts and Concept LatticeThe notion of a formal concept is fundamental in FCA. Formal concepts are particularclusters in cross-tables, defined by means of attribute sharing.Definition 2.5 (formal concept). A formal concept in hX, Y, Ii is a pair hA, Bi of A Xand B Y such that A B and B A.For a formal concept hA, Bi in hX, Y, Ii, A and B are called the extent and intent ofhA, Bi, respectively. Note the following verbal description of formal concepts: hA, Biis a formal concept if and only if A contains just objects sharing all attributes from Band B contains just attributes shared by all objects from A. Mathematically, hA, Bi isa formal concept if and only if hA, Bi is a fixpoint of the pair h , i of concept-formingoperators.Example 2.6 (formal concept). For tableIx1x2x3x4x5y1 y2 y3 y4 the highlighted rectangle represents formal concepthA1 , B1 i h{x1 , x2 , x3 , x4 }, {y3 , y4 }ibecause{x1 , x2 , x3 , x4 } {y3 , y4 } and {y3 , y4 } {x1 , x2 , x3 , x4 }.

But there are further formal concepts. Three of them are represented by the followinghighlighted rectangles:Ix1x2x3x4x5y1 y2 y3 y4 Ix1x2x3x4x5y1 y2 y3 y4 Ix1x2x3x4x5y1 y2 y3 y4 Namely, hA2 , B2 i h{x1 , x3 , x4 }, {y2 , y3 , y4 }i, hA3 , B3 i h{x1 , x2 }, {y1 , y3 , y4 }i, andhA4 , B4 i h{x1 , x2 , x5 }, {y1 }i.The notion of a formal concept can be seen as a simple mathematization of a wellknown notion of a concept, which goes back to Port-Royal logic. According to PortRoyal, a concept is determined by a collection of objects (extent) which fall underthe concept and a collection of attributes (intent) covered by the concepts. Conceptsare naturally ordered using a subconcept-superconcept relation. The subconceptsuperconcept relation is based on inclusion relation on objects and attributes. Formally, the subconcept-superconcept relation is defined as follows.Definition 2.7 (subconcept-superconcept ordering). For formal concepts hA1 , B1 i andhA2 , B2 i of hX, Y, Ii, put hA1 , B1 i hA2 , B2 i iff A1 A2 (iff B2 B1 ).Remark 2.8.– represents the subconcept-superconcept ordering.– hA1 , B1 i hA2 , B2 i means that hA1 , B1 i is more specific than hA2 , B2 i (hA2 , B2 iis more general).– captures the intuition behind DOG MAMMAL (the concept of a dog is morespecific than the concept of a mammal).Example 2.9. Consider the following formal concepts from Example 2.6:hA1 , B1 i h{x1 , x2 , x3 , x4 }, {y3 , y4 }i, hA2 , B2 i h{x1 , x3 , x4 }, {y2 , y3 , y4 }i,hA3 , B3 i h{x1 , x2 }, {y1 , y3 , y4 }i, hA4 , B4 i h{x1 , x2 , x5 }, {y1 }i. Then:hA3 , B3 i hA1 , B1 i, hA3 , B3 i hA2 , B2 i, hA3 , B3 i hA4 , B4 i, hA2 , B2 i hA1 , B1 i,hA1 , B1 i hA4 , B4 i (incomparable), hA2 , B2 i hA4 , B4 i.The collection of all formal concepts of a given formal contxt is called a concept lattice,another fundamental notion in FCA.Definition 2.10 (concept lattice). Denote by B(X, Y, I) the collection of all formal concepts of hX, Y, Ii, i.e.B (X, Y, I) {hA, Bi 2X 2Y A B, B A}.B (X, Y, I) equipped with the subconcept-superconcept ordering is called a conceptlattice of hX, Y, Ii.– B (X, Y, I) represents all (potentially interesting) clusters which are “hidden” indata hX, Y, Ii.– We will see that hB (X, Y, I), i is indeed a lattice later.DenoteExt(X, Y, I) {A 2X hA, Bi B (X, Y, I) for some B} (extents of concepts)andInt(X, Y, I) {B 2Y hA, Bi B (X, Y, I) for some A} (intents of concepts).

Example 2.11. Consider the following cross-table (input data, taken from 678a b cdefg hi a: needs water to live, b: lives in water,c: lives on land, d: needs chlorophyll to produce food,e: two seed leaves, f : one seed leaf,g: can move around, h: has limbs,i: suckles its offspring.The corresponding formal context hX, Y, Ii contains the following formal concepts:C0 h{1, 2, 3, 4, 5, 6, 7, 8}, {a}i, C1 h{1, 2, 3, 4}, {a, g}i, C2 h{2, 3, 4}, {a, g, h}i,C3 h{5, 6, 7, 8}, {a, d}i, C4 h{5, 6, 8}, {a, d, f }i, C5 h{3, 4, 6, 7, 8}, {a, c}i,C6 h{3, 4}, {a, c, g, h}i, C7 h{4}, {a, c, g, h, i}i, C8 h{6, 7, 8}, {a, c, d}i,C9 h{6, 8}, {a, c, d, f }i, C10 h{7}, {a, c, d, e}i, C11 h{1, 2, 3, 5, 6}, {a, b}i,C12 h{1, 2, 3}, {a, b, g}i, C13 h{2, 3}, {a, b, g, h}i, C14 h{5, 6}, {a, b, d, f }i,C15 h{3, 6}, {a, b, c}i, C16 h{3}, {a, b, c, g, h}i, C17 h{6}, {a, b, c, d, f }i,C18 h{}, {a, b, c, d, e, f, g, h, i}i.The corresponding concept lattice B(X, Y, I) is depicted in the following 7C182.4Formal Concepts as Maximal RectanglesAlternatively, formal concepts can conveniently be defined as maximal rectangles inthe cross-table.Definition 2.12 (rectangles in hX, Y, Ii). A rectangle in hX, Y, Ii is a pair hA, Bi suchthat A B I, i.e.: for each x A and y B we have hx, yi I. For rectangleshA1 , B1 i and hA2 , B2 i, put hA1 , B1 i v hA2 , B2 i iff A1 A2 and B1 B2 .Example 2.13. Consider

Ix1x2x3x4x5y1 y2 y3 y4 In this table, h{x1 , x2 , x3 }, {y3 , y4 }i is a rectangle which is not maximal w.r.t. v.h{x1 , x2 , x3 , x4 }, {y3 , y4 }i is a rectangle which is maximal w.r.t. v.Theorem 2.14 (formal concepts as maximal rectangles). hA, Bi is a formal concept ofhX, Y, Ii iff hA, Bi is a maximal rectangle in hX, Y, Ii.Proof. Left as an exercise (by direct verification).We will see that a “geometrical reasoning” in FCA based on the idea of formal conceptsas rectangles is important.2.5Basic Mathematical Structures Behind FCA: Galois Connections andClosure OperatorsIn this section, we present the basic mathematical structures behind FCA and theirproperties. We start with the concept of Galois connections. Namely, as we will see,the concept-forming operators form a representative case of Galois connections.Definition 2.15 (Galois connection). A Galois connection between sets X and Y is a pairhf, gi of f : 2X 2Y and g : 2Y 2X satisfying for A, A1 , A2 X, B, B1 , B2 Y :A1 A2 f (A2 ) f (A1 ),(2.1)B1 B2 g(B2 ) g(B1 ),(2.2)A g(f (A)),(2.3)B f (g(B).(2.4)Definition 2.16 (fixpoints of Galois connections). For a Galois connection hf, gi between sets X and Y , the setfix(hf, gi) {hA, Bi 2X 2Y f (A) B, g(B) A}is called a set of fixpoints of hf, gi.The following theorem shows a fundamental property of concept-forming operators.Theorem 2.17 (concept-forming operators form a Galois connection). For a formal context hX, Y, Ii, the pair h I , I i of operators induced by hX, Y, Ii is a Galois connection betweenX and Y .Proof. Left as an exercise (by direct verification).We have the following direct consequence.Lemma 2.18 (chaining of Galois connection). For a Galois connection hf, gi between Xand Y we have f (A) f (g(f (A))) and g(B) g(f (g(B))) for any A X and B Y .Proof. We prove only f (A) f (g(f (A))), g(B) g(f (g(B))) is dual:“ ”: f (A) f (g(f (A))) follows from (2.4) by putting B f (A).“ ”: Since A g(f (A)) by (2.3), we get f (A) f (g(f (A))) by application of (2.1).

Another important notion related to FCA is that of a closure operator.Definition 2.19 (closure operator). A closure operator on a set X is a mapping C : 2X 2X satisfying for each A, A1 , A2 XA C(A),(2.5)A1 A2 C(A1 ) C(A2 ),(2.6)C(A) C(C(A)).(2.7)Definition 2.20 (fixpoints of closure operators). For a closure operator C : 2X 2X ,the setfix(C) {A X C(A) A}is called a set of fixpoints of C.Closure operators result from the concept-forming operators by their composition:Theorem 2.21 (from Galois connection to closure operators). If hf, gi is a Galois connection between X and Y then CX f g is a closure operator on X and CY g f is a closureoperator on Y .Proof. We show that f g : 2X 2X is a closure operator on X:(2.5) is A g(f (A)) which is true by definition of a Galois connection.(2.6): A1 A2 impies f (A2 ) f (A1 ) which implies g(f (A1 )) g(f (A2 )).(2.7): Since f (A) f (g(f (A))), we get g(f (A)) g(f (g(f (A)))).The next theorem shows that extents and intents are just the images under the conceptforming operators.Theorem 2.22 (extents and intents).Ext(X, Y, I) {B B Y },Int(X, Y, I) {A A X}.Proof. We prove only the part for Ext(X, Y, I), part for Int(X, Y, I) is dual.“ ”: If A Ext(X, Y, I), then hA, Bi is a formal concept for some B Y . By definition, A B , i.e. A {B B Y }.“ ”: Let A {B B Y }, i.e. A B for some B. Then hA, A i is a formal concept.Namely, A B B A by chaining, and A A for free. That is, A is theextent of a formal concept hA, A i, whence A Ext(X, Y, I).Closures of sets are the least extents and intents:Theorem 2.23 (least extent containing A, least intent containing B). The least extentcontaining A X is A . The least intent containing B Y is B .Proof. For extents:1. A is an extent (by previous theorem).2. If C is an extent such that A C, then A C because is a closure operator.Therefore, A is the least extent containing A.The next theorem provides a useful description of a system of extents, intents, and aconcept lattice.Theorem 2.24. For any formal context hX, Y, Ii:Ext(X, Y, I) fix( ),Int(X, Y, I) fix( ),B(X, Y, I) {hA, A i A Ext(X, Y, I)},B(X, Y, I) {hB , Bi B Int(X, Y, I)}.

Proof. For Ext(X, Y, I):We need to show that A is an extent iff A A .“ ”: If A is an extent then for the corresponding formal concept hA, Bi we have B A and A B A . Hence, A A .“ ”: If A A then hA, A i is a formal concept. Namely, denoting hA, Bi hA, A i,we have both A B and B A A. Therefore, A is an extent.For B(X, Y, I) {hA, A i A Ext(X, Y, I)}:If hA, Bi B(X, Y, I) then B A and, obviously, A Ext(X, Y, I).If A Ext(X, Y, I) then A A (above claim) and, therefore, hA, A i B(X, Y, I).For B(X, Y, I) {hA, A i A Ext(X, Y, I)}:If hA, Bi B(X, Y, I) then B A and, obviously, A Ext(X, Y, I).If A Ext(X, Y, I) then A A (above claim) and, therefore, hA, A i B(X, Y, I).Remark 2.25. The previous theorem says that in order to obtain B(X, Y, I), we can:1. compute Ext(X, Y, I),2. for each A Ext(X, Y, I), output hA, A i.There is a single condition which is equivalent to the four conditions from definitionof a Galois connection:Theorem 2.26. hf, gi is a Galois connection between X and Y iff for every A X andB Y:A g(B) iff B f (A)(2.8)Proof. “ ”:Let hf, gi be a Galois connection.If A g(B) then f (g(B)) f (A) and since B f (g(B)), we get B f (A). In similarway, B f (A) implies A g(B).“ ”:Let A g(B) iff B f (A). We check that hf, gi is a Galois connection.Due to duality, it suffices to check (a) A g(f (A)), and (b) A1 A2 implies f (A2 ) f (A1 ).(a): Due to our assumption, A g(f (A)) is equivalent to f (A) f (A) which isevidently true.(b): Let A1 A2 . Due to (a), we have A2 g(f (A2 )), therefore A1 g(f (A2 )). Usingassumption, the latter is equivalent to f (A2 ) f (A1 ).Basic behavior of Galois connections with respect to union and intersection is described by the following theorem.Theorem 2.27. hf, gi is a Galois connection between X and Y then for Aj X, j J, andBj Y , j J we have[\f(Aj ) f (Aj ),(2.9)j Jg([j Jj JBj ) \j Jg(Bj ).(2.10)

Proof. (2.9):SSFor any D Y : D f ( j J Aj ) iffT j J Aj g(D) iff for each j J: Aj g(D) ifffor each j J: D f (Aj ) iff D j JS f (Aj ). TSince D is arbitrary, it follows that f ( j J Aj ) j J f (Aj ).(2.10): dual.Not only every pair of concept-forming operators forms a Galois, every Galois connection is a concept-forming operator of a particular formal context:Theorem 2.28. Let hf, gi be a Galois connection between X and Y . Consider a formal contexthX, Y, Ii such that I is defined byhx, yi Iiff y f ({x})or, equivalently, iff x g({y}),(2.11)for each x X and y Y . Then h I , I i hf, gi, i.e., the arrow operators h I , I i induced byhX, Y, Ii coincide with hf, gi.Proof. First, we show y f ({x}) iff x g({y}):From y f ({x}) we get {y} f ({x}) from which, using (2.8), we get {x} g({y}),i.e. x g({y}).In a similar way, x g({y}) implies y f ({x}). This establishes y f ({x}) iffx g({y}).Now, for each A X we have f (A) f ( x A {x}) x A f ({x}) x A {y Y y f ({x})} x A {y Y hx, yi I} {y Y for each x A : hx, yi I} A I .Dually, for B Y we get g(B) B I .Now, using (2.9), for each A X we havef (A) f ( x A {x}) x A f ({x}) x A {y Y y f ({x})} x A {y Y hx, yi I} {y Y for each x A : hx, yi I} A I .Dually, for B Y we get g(B) B I .Remark 2.29.– Relation I induced from hf, gi by (2.11) will be denoted by Ihf,gi .– Therefore, we have established two mappings:I 7 h I , I i assigns a Galois connection to a binary relation I.h , i 7 Ih , i assigns a binary relation to a Galois connection.Therefore, we get:Theorem 2.30 (representation theorem). I 7 h I , I i and h , i 7 Ih , i are mutuallyinverse mappings between the set of all binary relations between X and Y and the set of allGalois connections between X and Y .Proof. Using the results established above, it remains to check that I Ih I , I i :We havehx, yi Ih I , I i iff y {x} I iff hx, yi I,finishing the proof.Remark 2.31. In particular, previous theorem assures that (2.1)–(2.4) fully describe allthe properties of our arrow operators induced by data hX, Y, Ii.Having established properties of h , i, we can see the duality relationship betweenextents and intents:

Theorem 2.32. For hA1 , B1 i, hA2 , B2 i B(X, Y, I),A1 A2B2 B1 .iff(2.12)Proof. By assumption, Ai Bi and Bi A i . Therefore, using (2.1) and (2.2), we getA1 A2 implies A 2 A 1 , i.e., B2 B1 , which implies B1 B2 , i.e. A1 A2 .Therefore, the definition of a partial order on B(X, Y, I) is correct.An immediate consequence of the above properties is the following theorem:Theorem 2.33 (extents, intents, and formal concepts).hInt(X, Y, I), i are partially ordered sets.1. hExt(X, Y, I), iand2. hExt(X, Y, I), i and hInt(X, Y, I), i are dually isomorphic, i.e., there is a mappingf : Ext(X, Y, I) Int(X, Y, I) satisfying A1 A2 iff f (A2 ) f (A1 ).3. hB(X, Y, I), i is isomorphic to hExt(X, Y, I), i.4. hB(X, Y, I), i is dually isomorphic to hInt(X, Y, I), i.Proof. 1.: Obvious because Ext(X, Y, I) is a collection of subsets of X and is setinclusion. Same for Int(X, Y, I).2.: Just take f and use previous results.3.: Obviously, mapping hA, Bi 7 A is the required isomorphism.4.: Mapping hA, Bi 7 B is the required dual isomorphism.We know that B(X, Y, I) (set of all formal concepts) equipped with (subconceptsuperconcept hierarchy) is a partially ordered set. Now, the question is:What is the structure of hB(X, Y, I), i?It turns out that hB(X, Y, I), i is a complete lattice (we will see this as a part of Maintheorem of concept lattices). The fact that hB(X, Y, I), i is a lattice is a “welcomeproperty”. Namely, it says that for any collection K W B(X, Y, I) of formal concepts,B(X, Y, I) contains both the “direct generalization”K of concepts from K (supreWmum of K), and the “direct specialization” K of concepts from K (infimum of K).In this sense, hB(X, Y, I), i is a complete conceptual hierarchy. Let us now look atdetails.We start with the following abstract theorem.Theorem 2.34 (system of fixpoints of closure operators). For a closure operator C on X,the partially ordered set hfix(C), i of fixpoints of C is a complete lattice with infima andsuprema given by\ Aj Aj ,(2.13)j Jj JAj C(j J[Aj ).(2.14)j JProof. Evidently, hfix(C), i is a partially ordered set.T(2.13): First, we check that for Aj fix(C)wehavej JTT Aj fix(C) (intersection offixpointsT is a fixpoint).T We need to check j J Aj C( j J Aj ).“ ”: j J Aj C(obvious (property of closure operators).TT j J Aj ) is T“ ”: We have C( j J Aj ) j J Aj iff for each j J we have C( j J Aj ) Aj

which is true. Indeed, we haveC(Aj ) Aj .Tj JTAj Aj from which we get C( j J Aj ) TTNow,since j J Aj fix(C), it is clear thatT j J Aj is the infimum of Aj ’s: first,Tj J Aj is less of equal to every Aj ; second, Tj J Aj is greater or equal to any A fix(C) which is less or equal to all Aj ’s; that is, j J Aj is the greatest element of thelower cone of {Aj j J}).WSW(2.14): We verify C( j J Aj ). Note first that since j J Aj is a fixpoint ofj J Aj WWC, we have j J Aj C( j J Aj ).SS“ ”: C( j J Aj ) is a fixpoint which is greaterorequaltoeveryA,andsoC(jj J Aj )WWSmust be greater or equal to the supremum j J Aj , i.e. j J Aj C( j J Aj ).WWSW“ ”:W Since j J ASj Aj for any j J, we get j J Aj j J Aj , and so j J Aj C( j J Aj ) C( j J Aj ).To sum up,2.6Wj JSAj C( j J Aj ).Main Theorem of Concept LatticesThe previous results enable us to formulate the following theorem characterizing thestructure of concept lattices.Theorem 2.35 (Main theorem of concept lattices, Wille (1982)). (1) B (X, Y, I) is a complete lattice with infima and suprema given by \[[\hAj , Bj i hAj , (Bj ) i ,hAj , Bj i h(Aj ) ,Bj i .(2.15)j Jj Jj Jj Jj Jj J(2) Moreover, an arbitrary complete lattice V (V, ) is isomorphic to B (X, Y, I) iff thereare mappings γ : X V , µ : Y V such that(i) γ(X) isW-dense in V, µ(Y ) isV-dense in V;(ii) γ(x) µ(y) iff hx, yi I.Remark 2.36. (1) Note that KW V is supremally dense in V iff for each v V thereexists K 0 K such that v K 0 (i.e., every element v of V is a supremum of someelements of K).Dually for infimal density of K in V (every element v of V is an infimum of someelements of K).(2) Supremally (infimally) dense sets canbe considered building blocks of V .VProof. For part (1) of the Main Theorem only: We checkj J hAj , Bj iTS h j J Aj , ( j J Bj ) i: First, hExt(X, Y, I), i hfix( ), i and hInt(X, Y, I), i hfix( ), i. That is,Ext(X, Y, I) and Int(X, Y, I) are systems of fixpoints of closure operators, and therefore, suprema and infima in Ext(X, Y, I) and Int(X, Y, I) obey the formulas from previous theorem.Second, recall that hB (X, Y, I), i is isomorphic to hExt(X, Y, I), i and dually isomorphic to hInt(X, Y, I), i.

Therefore, infima in B (X, Y, I) correspond to infima in Ext(X, Y, I) and to suprema inInt(X, Y, I).VThat is, sincej J hAj , Bj i is the infimum of hAj , Bj i’s in hB (X, Y, I), i: TheVextent of j J hAjT, Bj i is the infimum of VAj ’s in hExt(X, Y, I), i which is, according to (2.13), j J Aj . The intent of j J hAj , Bj i is the supremum of Bj ’sSin hInt(X, Y, I), i which is, according to (2.14), ( j J Bj ) . We just

Formal concept analysis (FCA) is a method of data analysis with growing popularity across various domains. FCA analyzes data which describe relationship between a particular set of objects and a particular set of attributes. Such data commonly appear in many areas of human activities. FCA produces two kinds of output from the input data.