Formal concept analysis is a method of exploratory data analysis that aims at the extraction of natural clusters from objectattribute data tables. The clusters, called formal concepts, are naturally interpreted as human-perceived concepts in a traditional sense and can be partially ordered by a subconcept-superconcept hierarchy. The hierarchical structure of formal concepts (so-called concept lattice) represents a structured information obtained automatically from the input data table. This paper presents a preliminary study in which we deal with the problem of how further information additionally supplied with the basic object-attribute data table can be utilized. The additional information we consider has the form of a binary relation on the set of objects. Primarily, we focus on equivalence relations. Equivalences can be used modeling similarity, indistinguishability, etc.-a kind of information quite often supplied/available with a collection of objects. We aim at emphasizing two aspects. First, the additional information can provide a criterion for the relevance/importance of formal concepts. Only concepts which are in an appropriate sense compatible with the additional information are considered important. Second, selecting only important concepts means a reduction of the overall concept lattice which helps to make the resulting set of formal concepts more readable.
Patterns in data The search for interesting patterns in data has traditionally
been a challenging problem. In the pre-computer era, the extent of efficiently
analyzable data was small and the patterns looked for in the data were
simple patterns easily recognizable and graspable by humans. Computers made it
possible to analyze large amounts of data as well as to look for new kinds of
patterns in the data. Formal concept analysis (FCA) [
Formal concept analysis In its basic setting, formal concept analysis deals with input data in the form of a table with rows corresponding to objects and columns corresponding to attributes which describes a relationship between the objects and attributes. The data table is formally represented by a so-called formal context which is a triplet hX, Y, Ii where I is a binary relation between X and Y , hx, yi ∈ I meaning that the object x has the attribute y. For each A ⊆ X denote by A↑ a subset of Y defined by
A↑ = {y | for each x ∈ X : hx, yi ∈ I}.
Similarly, for B ⊆ Y denote by B↓ a subset of X defined by
B↓ = {x | for each y ∈ Y : hx, yi ∈ I}.
That is, A↑ is the set of all attributes from Y shared by all objects from A (and similarly for B↓). A formal concept in hX, Y, Ii is a pair hA, Bi of A ⊆ X and B ⊆ Y satisfying A↑ = B and B↓ = A. That is, a formal concept consists of a set A (extent) of objects which fall under the concept and a set B (intent) of attributes which fall under the concept such that A is the set of all objects sharing all attributes from B and, conversely, B is the collection of all attributes from Y shared by all objects from A. The set B (X, Y, I) = {hA, Bi | A↑ = B, B↓ = A} of all formal concepts in hX, Y, Ii can be naturally equipped with a partial order ≤ (modeling the subconcept-superconcept hierarchy, e.g. dog ≤ mammal) defined by
hA1, B1i ≤ hA2, B2i iff A1 ⊆ A2 (or, equivalently, B2 ⊆ B1).
Under ≤, B (X, Y, I) happens to be a complete lattice, called a concept lattice,
the basic structure of which is described by the so-called main theorem of concept
lattices [
Theorem 1. (1) The set B (X, Y, I) is under ≤ a complete lattice where the infima and suprema are given by ^ hAj , Bj i = h \ Aj , ( [ Bj )↓↑i , _ hAj , Bj i = h( [ Aj )↑↓, \ Bj i . (1) j∈J j∈J j∈J j∈J j∈J j∈J (2) Moreover, an arbitrary complete lattice V = hV, ≤i is isomorphic to B (X, Y, I) iff there are mappings γ : X → V , μ : Y → V such that (i) γ(X) is W-dense in V, μ(Y ) is V-dense in V; (ii) γ(x) ≤ μ(y) iff hx, yi ∈ I. Our aim Formal concept analysis thus treats both the individual objects and the individual attributes as distinct entities for which there is no further information available except for the relationship I saying which objects have which attributes. However, more often than not, both the set of objects and the set of attributes are supplied by an additional information. Further processing of the input data (formal context) should therefore take the additional information into account. Particularly, the conceptual clustering should take the additional information into account so that only those concepts which are in an appropriate sense compatible with the additional information are considered relevant. In this paper, we consider the additional information in the form of a binary relation on the set of objects. Our primary interest is in equivalence relations, describing similarity, insdistinguishability, etc., on objects. The main aim is to utilize the additional information to reduce the size of the resulting concept lattice. Section 2 provides a formal treatment of our approach, Section 3 presents illustrating examples, Section 4 gives some remarks on future research. 2
Concept lattices of contexts with binary relations In what follows, we briefly present the conception and formal treatment of our approach.
Definition 1. A formal context with a binary relation (R-context, for short) is a structure hX, Y, I, ≡i (written also hhX, ≡i, Y, Ii) where hX, Y, Ii is a formal context and ≡ is a binary relation on X.
Remark 1. (1) We are primarily interested in case when ≡ is an equivalence relation. Then x1 ≡ x2 means that objects x1 and x2 are equivalent from some point of view (similar, indistuinguishable).
(2) Equivalence ≡ may be supplied by an expert or may result from some previous analysis or external source. For example, objects from X may be partitioned by some clustering (based on attributes from Y or some other data available) or some convention (a catalogue). Such a partition gives naturally a rise to an equivalence relation.
If ≡ represents an indistinguishability (or intended indistinguishability), it might be desirable to consider only those formal concepts which do not separate indistinguishable objects. We call such formal concepts compatible. Definition 2. For an R-context hhX, ≡i, Y, Ii, a formal concept hA, Bi ∈ B (X, Y, I) is called compatible with ≡ if for each x1, x2 ∈ X, if x1 ∈ A, and x1 ≡ x2 or x2 ≡ x1, then x2 ∈ A.
Compatible concepts are thus certain formal concepts from B (X, Y, I) satisfying a natural restriction with respect to ≡. The set of all formal concepts from B (X, Y, I) which are compatible with ≡ will be denoted by B (hX, ≡i, Y, I), i.e.
B (hX, ≡i, Y, I) = {hA, Bi ∈ B (X, Y, I) | for each x1, x2 : x1 ∈ A, x1 ≡ x2 or x2 ≡ x1 implies x2 ∈ A}.
The following lemma is obvious. Lemma 1. If ≡ is symmetric then hA, Bi ∈ B (X, Y, I) is compatible with ≡ iff for each x1, x2 ∈ X, if x1 ∈ A and x1 ≡ x2 then x2 ∈ A
For an equivalence ≡ on X, compatible formal concepts are unions of ≡classes (recall that an ≡-class corresponding to x ∈ X is a set [x]≡ = {x0 ∈ X | x ≡ x0}; the collection of all ≡-classes is denoted by X/ ≡). Theorem 2. A formal concept hA, Bi ∈ B (X, Y, I) is compatible with ≡ iff A is a union of some ≡-classes, i.e. there is A ⊆ X/ ≡ such that A = S A. Proof. The proof is almost evident (it follows from Definition 2 and the definition of an equivalence class). 2
It is obvious that B (hX, idX i, Y, I) = B (X, Y, I), i.e. if ≡ is the identity on X then any formal concept of B (X, Y, I) is compatible with ≡ (this agrees with the intended way of restriction by ≡). The same holds true for ≡= ∅ (the restriction formulated by ≡ is empty), i.e. B (hX, ∅i, Y, I) = B (X, Y, I). More generally, we can proceed as follows. For a formal context hX, Y, Ii denote by =∼X the binary relation defined on X by x1 =∼X x2 if and only if for each y ∈ Y : hx1, yi ∈ I iff hx2, yi ∈ I. (2) In other words, x1 =∼X x2 if and only if x1 and x2 have the same set of attributes, i.e. if h{x1}↑↓, {x1}↑i = h{x2}↑↓, {x2}↑i. Obviously, =∼X is an equivalence relation on X. We have the following statement.
Theorem 3. B (hX, ≡i, Y, I) = B (X, Y, I) if and only if for each x1, x2 ∈ X, x1 ≡ x2 implies x1 ∼=X x2.
Proof. We omit the proof (due to the limited scope). 2 Corollary 1. B (hX, ≡i, Y, I) = B (X, Y, I) if and only if for each x1, x2 ∈ X, if x1 and x2 are separated by some y ∈ Y , then x1 6≡ x2.
The next theorem shows a natural result saying that the more restrictions, the less formal concepts satisfying the restrictions.
Theorem 4. If ≡1 ⊆ ≡2 then B (hX, ≡2i, Y, I) ⊆ B (hX, ≡1i, Y, I). Proof. Trivial. 2
Given a formal context hX, Y, Ii and a binary relation ≡ on X, a natural question arises for what binary relations Q on X we have B (hX, ≡i, Y, I) = B (hX, Qi, Y, I), i.e. what Q are restrictive to the same extent as ≡. We will answer the question with respect to the operations of equivalential closure. For a binary relation R, the equivalential closure will be denoted by RE. By definition, RE is the least equivalence relation containing R (i.e. R ⊆ RE). Theorem 5. For an R-context hhX, ≡i, Y, Ii we have
B (hX, red(≡)i, Y, I) = B (hX, ≡i, Y, I) = B ¡hX, ≡Ei, Y, I¢ where red(≡) is any relation such that red(≡) ⊆≡ −idX − ≡2 and for each x1red(≡)x2 we have x2¬red(≡)x1 (i.e. red(≡) is an equivalential reduction of ≡). Furthermore, for each binary relation Q on X satisfying red(≡) ⊆ Q ⊆≡E we have B (hX, Qi, Y, I) = B (hX, ≡i, Y, I).
Proof. We omit the proof (due to the limited scope).
Theorem 6. B (hX, ≡i, Y, I) equipped with ≤ is a complete lattice in which arbitrary infima coincide with infima in B (X, Y, I), i.e. it is a complete V-sublattice of B (X, Y, I).
Proof. It can be shown (we omit details) that for any hAi, Bii ∈ B (hX, ≡i, Y, I) we have hTi Ai, (Ti Ai)↑i ∈ B (hX, ≡i, Y, I). That is, B (hX, ≡i, Y, I) is closed under arbitrary infima from B (X, Y, I) which gives the claim. 2
It can be shown by an easy example that suprema in B (hX, ≡i, Y, I) do not generally coincide with suprema in B (X, Y, I). 3
We now present illustrative examples. We assume that the reader is familiar with Hasse diagrams which will be used for visualization of concept lattices and attribute hierarchies. We label the nodes corresponding to formal concepts by boxes containing concept descriptions. For example, ({1, 3, 7}, {3, 4}) is a description of a concept the extent of which consists of objects 1, 3, and 7, and the intent of which consists of attributes 3 and 4.
Example 1. The following example shows the effect of reduction of the number of formal concepts. Consider the formal context hX, Y, Ii in Tab. 1 .
The concept lattice B (X, Y, I) corresponding to formal context hX, Y, Ii contains 19 formal concepts and is depicted in Fig. 1. Consider furthermore the equivalence relation ≡ given by the type of fund. There are four ≡-classes corresponding to stock funds, bond funds, mixed funds and money funds. The set of all formal concepts from B (X, Y, I) which are compatible with ≡ contains 6 formal concepts and is depicted in Fig. 2.
Example 2. The following example demonstrates that the restriction can be quite extensive. Consider the formal context hX, Y, Ii in Tab. 2 . The concept lattice B (X, Y, I) corresponding to formal context hX, Y, Ii contains 21 formal concepts and is depicted in Fig. 3. Consider furthermore an equivalence ≡ induced in salary so that we have 3 classes corresponding to salary less then 13 000, salary between 13 000 and 17 000 and salary higher then 17 000. The set of all formal concepts from B (X, Y, I) which are compatible with ≡ contains 3 formal concepts and is depicted in Fig. 4. attributes: 1 - rating for 1 week <= 0, 5, 2 - rating for 1 week > 0, 5 and <= 1, 3 rating for 1 week > 1, 4 - rating for 26 weeks <= 0, 5, 5 - rating for 26 weeks > 0, 5 and <= 4, 6 - rating for 26 weeks > 4, 7 - rating for 52 weeks <= 0, 5, 8 - rating for 56 weeks > 0, 5 and <= 10, 9 - rating for 56 weeks > 10
({1,2,3,4,5,6,7,8,9,10},{}) ({3,4,9},{4}) ({1,3,5,6,7,10},{8}) ({1,4,5,6,7,10},{5}) ({8,9,10},{3}) ({2,8},{6,9}) ({1,2,6,7},{1}) ({4,9},{4,7}) ({3,5},{2,8}) ({1,5,6,7,10},{5,8}) ({8},{3,6,9}) ({2},{1,6,9}) ({4},{4,5,7}) ({9},{3,4,7}) ({3},{2,4,8}) ({5},{2,5,8}) ({10},{3,5,8}) ({1,6,7},{1,5,8}) attributes: 1 - secondary school (education), 2 - university (education), 3 - single, 4 married, 5 - lives in a flat, 6 - owns a house, 7 - owns a car
({1,2,3,4,5,6,7,8,9,10},{}) ({1,5,6,7,10},{5,8}) ({2,8},{6,9}) ({3,4,9},{4}) ({1,6,7},{1,5,8})
({},{1,2,3,4,5,6,7,8,9})
({1,2,3,4,5,6,7,8,9,10},{})
({3,7,9},{1,2,5})
({},{1,2,3,4,5,6,7})
We now comment on some further topics and future research (some of these are
studied in [
– Relation to rough sets. Having an equivalence relation on the universe set and
considering only sets which are using our terminology compatible with the
equivalence is the main idea of so-called rough sets introduced by Pawlak [
The partition corresponding to ≡ represents another clustering (more generally, we can think of a hierarchical clustering scheme). Several interesting problems arise here (constraining one clustering by the other, comparing the clusterings, measuring their mutual consistency, etc.), a work is in progress. Acknowledgement The research of the first author was supported by grant No. 201/02/P076 of the GACˇ R.