=Paper=
{{Paper
|id=Vol-110/paper-6
|storemode=property
|title=Concept Lattices Constrained by Equivalence Relations
|pdfUrl=https://ceur-ws.org/Vol-110/paper7.pdf
|volume=Vol-110
|dblpUrl=https://dblp.org/rec/conf/cla/BelohlavekSZ04
}}
==Concept Lattices Constrained by Equivalence Relations==
https://ceur-ws.org/Vol-110/paper7.pdf
Concept lattices
Concept constrained
Lattices by equivalence
Constrained by
relations
Equivalence Relations
Radim BĚLOHLÁVEK, Vladimı́r SKLENÁŘ, Jiřı́ ZACPAL
Radim Bělohlávek, Vladimı́r Sklenář, and Jiřı́ Zacpal
Dept. Computer Science, Palacký University, Tomkova 40, CZ-779 00, Olomouc,
Department of Computer
Czech Republic, Science, Palacky University, Olomouc
radim.belohlavek@upol.cz
Tomkova 40, CZ-779 00 Olomouc, Czech Republic
radim.belohlavek@upol.cz
Abstract. Formal concept analysis is a method of exploratory data
analysis that aims at the extraction of natural clusters from object-
attribute 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 hierar-
chical structure of formal concepts (so-called concept lattice) represents
a structured information obtained automatically from the input data ta-
ble.
This paper presents a preliminary study in which we deal with the
problem of how further information additionally supplied with the ba-
sic object-attribute data table can be utilized. The additional informa-
tion we consider has the form of a binary relation on the set of ob-
jects. Primarily, we focus on equivalence relations. Equivalences can be
used modeling similarity, indistinguishability, etc.—a kind of informa-
tion 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 con-
cepts 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.
Keywords: formal concept analysis, concept lattice, constraint, binary relation,
similarity
1 Introduction and problem setting
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 sim-
ple 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) [6] provides methods for
finding patterns and dependencies in data which can be run automatically. The
patterns looked for are called formal concepts. The attractiveness of formal con-
cept analysis derives mainly from the fact that formal concepts are interpretable
c V. Snášel, R. Bělohlávek (Eds.): CLA 2004, pp. 58–66, ISBN 80-248-0597-9.
VŠB – Technical University of Ostrava, Dept. of Computer Science, 2004.
Concept Lattices Constrained by Equivalence Relations 59
as natural concepts well-understood by humans. Both foundations and applica-
tions (classification, software (re)engineering, document and text organization,
etc.) of formal concept analysis are well-documented (see [6] and [1], and the
references therein).
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 , B1 i ≤ hA2 , B2 i 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 [6, 9].
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
W V
(i) γ(X) is -dense in V, µ(Y ) is -dense in V;
(ii) γ(x) ≤ µ(y) iff hx, yi ∈ I.
2
60 Radim Bělohlávek, Vladimı́r Sklenář, Jiřı́ Zacpal
Our aim Formal concept analysis thus treats both the individual objects and
the individual attributes as distinct entities for which there is no further infor-
mation 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 appropri-
ate 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 lat-
tice. 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 par-
titioned 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) satis-
fying 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.
3
Concept Lattices Constrained by Equivalence Relations 61
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 S ≡ iff A
is a union of some ≡-classes, i.e. there is A ⊆ X/ ≡ such that A = 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, ≡2 i, Y, I) ⊆ B (hX, ≡1 i, 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 R E . By definition,
RE is the least equivalence relation containing R (i.e. R ⊆ R E ).
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, ≡E i, Y, I
where red(≡) is any relation such that red(≡) ⊆≡ −idX − ≡2 and for each
x1 red(≡)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
4
62 Radim Bělohlávek, Vladimı́r Sklenář, Jiřı́ Zacpal
we have B (hX, Qi, Y, I) = B (hX, ≡i, Y, I).
Proof. We omit the proof (due to the limited scope).
2
Theorem 5 shows natural bounds (in terms of transitive reduction and clo-
sure) on relation Q which are equally restrictive as ≡.
The restriction of the subconcept-superconcept hierarchy ≤ which is
defined on B (X, Y, I) makes hhX, ≡i, Y, Ii itself a partially ordered set
hB (hX, ≡i, Y, I), ≤i. The following theorem shows that hhX, ≡i, Y, Ii is itself a
complete lattice which is a reasonable substructure of the whole concept lattice
B (X, Y, I).
Theorem 6. B (hX, ≡i, Y, I) equipped with ≤ is a complete lattice inVwhich arbi-
trary infima coincide with infima in B (X, Y, I), i.e. it is a complete -sublattice
of B (X, Y, I).
Proof. It can
T be shown
T (we omit details) that for any hAi , Bi i ∈ B (hX, ≡i, Y, I)
we have h i Ai , ( i 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 Examples and discussion
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 con-
tains 19 formal concepts and is depicted in Fig. 1. Consider furthermore the
equivalence relation ≡ given by the type of fund. There are four ≡-classes cor-
responding 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 ≡ in-
duced 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.
5
Concept Lattices Constrained by Equivalence Relations 63
Table 1. Formal context from Example 1
fund type 1 2 3 4 5 6 7 8 9
1 CPI Penezniho trhu money 1 0 0 1 0 0 0 1 0
2 CSOB Akciovy stock 1 0 0 0 0 1 0 0 1
3 CSOB Bond mix bond 0 1 0 1 0 0 0 1 0
4 IKS Dluhopisovy bond 0 1 0 1 0 0 1 0 0
5 IKS Globalni mixed 0 1 0 0 1 0 0 1 0
6 IKS Penezni trh money 1 0 0 0 1 0 0 1 0
7 ISCS Sporoinvest money 1 0 0 0 1 0 0 1 0
8 ISCS Sporotrend stock 0 0 1 0 0 1 0 0 1
9 ISCS Trendbond bond 0 0 1 1 0 0 1 0 0
10 ISCS Vynosovy mixed 0 0 1 0 1 0 0 1 0
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},{})
({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})
({3,4,9},{4})
({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})
({},{1,2,3,4,5,6,7,8,9})
Fig. 1. Concept lattice corresponding to the context from Tab. 1
Table 2. Formal context from Example 2
name salary 1 2 3 4 5 6 7
1 Iva 15 000 1 0 0 1 1 0 0
2 Iva 15 000 0 0 0 1 1 0 0
3 Jirka 19 000 1 1 1 0 1 0 0
4 Jitka 14 000 1 0 1 0 0 1 1
5 Karel 15 000 1 0 0 1 0 1 1
6 Marek 13 000 0 0 1 0 1 0 0
7 Pavel 25 000 1 1 1 0 1 0 1
8 Pavla 14 000 1 0 0 1 1 0 0
9 Petr 20 000 1 1 0 1 1 0 1
10 Radim 13 000 1 0 1 0 0 1 0
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
6
64 Radim Bělohlávek, Vladimı́r Sklenář, Jiřı́ Zacpal
({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})
Fig. 2. Concepts corresponding to the context from Tab. 1 which are compatible with
≡ from Example 1
({1,2,3,4,5,6,7,8,9,10},{})
({1,3,4,5,6,7,8,9,10},{1}) ({1,2,3,6,7,8,9},{5})
({3,4,6,7,10},{3}) ({1,2,5,8,9},{4}) ({1,3,7,8,9},{1,5})
({3,4,7,10},{1,3}) ({3,6,7},{3,5}) ({1,2,8,9},{4,5}) ({1,5,8,9},{1,4}) ({3,7,9},{1,2,5}) ({3,5,9},{1,7})
({3,7},{1,2,3,5}) ({4,5,10},{1,6}) ({1,8,9},{1,4,5}) ({5,9},{1,4,7}) ({3,9},{1,2,5,7})
({4,10},{1,3,6}) ({3},{1,2,3,5,7}) ({9},{1,2,4,5,7})
({5},{1,4,6,7})
({},{1,2,3,4,5,6,7})
Fig. 3. Concept lattice corresponding to the context from Tab. 2
7
Concept Lattices Constrained by Equivalence Relations 65
({1,2,3,4,5,6,7,8,9,10},{})
({3,7,9},{1,2,5})
({},{1,2,3,4,5,6,7})
Fig. 4. Concepts corresponding to the context from Tab. 2 which compatible with ≡
from Example 2
4 Future research
We now comment on some further topics and future research (some of these are
studied in [4]).
– 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 [8].
This gave rise to so-called rough concept analysis, see e.g. [7], on which we
recently learned. An investigation of the relationship with our approach is in
progress (note that the notion of a definable formal concept as defined in [7]
coincides with our notion of a compatible formal concept; there is, however,
almost no overlap between [7] and Section 2).
– There is another interesting way to formulate a constraint. Namely, requiring
that for a formal concept hA, Bi, all objects from A are ≡-equivalent. We
elaborate more on this in [4].
– A concept lattice may be thought of as a hierarchical clustering scheme.
The partition corresponding to ≡ represents another clustering (more gen-
erally, 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 GAČR.
References
1. http://www.mathematik.tu-darmstadt.de/ags/ag1/Literatur/literatur de.html
8
66 Radim Bělohlávek, Vladimı́r Sklenář, Jiřı́ Zacpal
2. Arnauld A., Nicole P.: La logique ou l’art de penser. 1662. Also in German: Die
Logik oder die Kunst des Denkens. Darmstadt, 1972.
3. Bělohlávek R., Sklenář V., Zacpal J.: Formal concept analysis with hierarchically
ordered attributes. Int. J. General Sytems (to appear).
4. Bělohlávek R., Sklenář V., Zacpal J.: Formal concept analysis constrained by par-
titions (in preparation).
5. Birkhoff G.: Lattice Theory, 3-rd edition. AMS Coll. Publ. 25, Providence, R.I.,
1967.
6. Ganter B., Wille R.: Formal concept analysis. Mathematical Foundations. Springer-
Verlag, Berlin, 1999.
7. Kent R. E.: Rough concept analysis. In: Ziarko W. P. (Ed.): Rough Sets, Fuzzy
Sets, and Knowledge Discovery. Proc. of the Intern. Workshop RSKD’93, Springer-
Verlag, London, 1994.
8. Pawlak Z.: Rough Sets: Theortical Aspects of Reasoning About Data. Kluwer, Dor-
drecht, 1992.
9. Wille R.: Restructuring lattice theory: an approach based on hierarchies of con-
cepts. In: Rival I.: Ordered Sets. Reidel, Dordrecht, Boston, 1982, 445—470.
9