=Paper=
{{Paper
|id=Vol-1466/paper01
|storemode=property
|title=Subset-Generated Complete Sublattices as Concept Lattices
|pdfUrl=https://ceur-ws.org/Vol-1466/paper01.pdf
|volume=Vol-1466
|dblpUrl=https://dblp.org/rec/conf/cla/KauerK15
}}
==Subset-Generated Complete Sublattices as Concept Lattices==
https://ceur-ws.org/Vol-1466/paper01.pdf
Subset-generated complete sublattices
as concept lattices?
Martin Kauer and Michal Krupka
Department of Computer Science
Palacký University in Olomouc
Czech Republic
martin.kauer@upol.cz
michal.krupka@upol.cz
Abstract. We present a solution to the problem of finding the complete
sublattice of a given concept lattice generated by given set of elements.
We construct the closed subrelation of the incidence relation of the cor-
responding formal context whose concept lattice is equal to the desired
complete sublattice. The construction does not require the presence of
the original concept lattice. We introduce an efficient algorithm for the
construction and give an example and experiments.
1 Introduction and problem statement
One of the basic theoretical results of Formal Concept Analysis (FCA) is the
correspondence between closed subrelations of a formal context and complete
sublattices of the corresponding concept lattice [2]. In this paper, we study a re-
lated problem of constructing the closed subrelation for a complete sublattice
generated by given set of elements.
Let hX, Y, Ii be a formal context, B(X, Y, I) its concept lattice. Denote by
V the complete sublattice of B(X, Y, I) generated by a set P ⊆ B(X, Y, I).
As it is known [2], there exists a closed subrelation J ⊆ I with the concept
lattice B(X, Y, J) equal to V . We show a method of constructing J without
the need of constructing B(X, Y, I) first. We also provide an efficient algorithm
(with polynomial time complexity), implementing the method. The paper also
contains an illustrative example and results of experiments, performed on the
Mushroom dataset from the UCI Machine Learning Repository.
2 Complete lattices and Formal Concept Analysis
Recall that a partially ordered set U is called a complete lattice
W if each V its subset
P ⊆ U has a supremum andWinfimum. We denote these V by P and P , respec-
tively. A subset V ⊆ U is a -subsemilattice (resp. W-subsemilattice, resp.V com-
plete sublattice)
W V of U , if for each P ⊆ V it holds P ∈ V (resp. P ∈ V,
resp. { P, P } ⊆ V ).
?
Supported by the IGA of Palacký University Olomouc, No. PrF 2015 023
c paper author(s), 2015. Published in Sadok Ben Yahia, Jan Konecny (Eds.): CLA
2015, pp. 11–21, ISBN 978–2–9544948–0–7, Blaise Pascal University, LIMOS
laboratory, Clermont-Ferrand, 2015. Copying permitted only for private and
academic purposes.
12 Martin Kauer and Michal Krupka
W
For a subset P ⊆ U we denote by CW P W the -subsemilattice of U generated
by P , i.e. the smallest (w.r.t. set inclusion) -subsemilattice Wof U containing P .
CW P always exists and V is equal to the intersection of all -subsemilattices of
U containing P . The -subsemilattice of U generated by P and the complete
sublattice of U generated by P are defined similarly and are denoted by CV P
and CWV P , respectively.
The operators CW , CV , and CWV are closure operators on the set U . Recall
that a closure operator on a set X is a mapping C : 2X → 2X (where 2X is the
set of all subsets of X) satisfying for all sets A, A1 , A2 ⊆ X
1. A ⊆ C A,
2. if A1 ⊆ A2 then C A1 ⊆ C A2 ,
3. CC A = C A.
Concept lattices have been introduced in [4], our basic reference is [2]. A (for-
mal ) context is a triple hX, Y, Ii where X is a set of objects, Y a set of attributes
and I ⊆ X × Y a binary relation between X and Y specifying for each object
which attributes it has.
For subsets A ⊆ X and B ⊆ Y we set
A↑I = {y ∈ Y | for each x ∈ A it holds hx, yi ∈ I},
B ↓I = {x ∈ X | for each y ∈ B it holds hx, yi ∈ I}.
The pair h↑I , ↓I i is a Galois connection between sets X and Y , i.e. it satisfies
1. If A1 ⊆ A2 then A↑2I ⊆ A↑1I , if B1 ⊆ B2 then B2↓I ⊆ B1↓I .
2. A ⊆ A↑I ↓I and B ⊆ B ↓I ↑I .
The operator ↑I ↓I is a closure operator on X and the operator ↓I ↑I is a closure
operator on Y .
A pair hA, Bi satisfying A↑I = B and B ↓I = A is called a (formal ) concept
of hX, Y, Ii. The set A is then called the extent of hA, Bi, the set B the intent of
hA, Bi. When there is no danger of confusion, we can use the term “an extent
of I” instead of “the extent of a concept of hX, Y, Ii”, and similarly for intents.
A partial order ≤ on the set B(X, Y, I) of all formal concepts of hX, Y, Ii is
defined by hA1 , B1 i ≤ hA2 , B2 i iff A1 ⊆ A2 (iff B2 ⊆ B1 ). B(X, Y, I) along with
≤ is a complete lattice and is called the concept lattice of hX, Y, Ii. Infima and
suprema in B(X, Y, I) are given by
* !↓I ↑I +
^ \ [
hAj , Bj i = Aj , Bj , (1)
j∈J j∈J j∈J
* !↑I ↓I +
_ [ \
hAj , Bj i = Aj , Bj . (2)
j∈J j∈J j∈J
Subset-generated complete sublattices as concept lattices 13
One of immediate consequences of (1) and (2) is that the intersection of any
system of extents, resp. intents, is again an extent, resp. intent, and that it can
be expressed as follows:
!↑I !↓I
\ [ \ [
Bj = Aj , resp. Aj = Bj ,
j∈J j∈J j∈J j∈J
for concepts hAj , Bj i ∈ B(X, Y, I), j ∈ J.
Concepts h{y}↓I , {y}↓I ↑I i where y ∈ Y are attribute concepts. Each concept
hA, Bi isVinfimum of some attribute concepts (we say the set of all attribute con-
cepts is -dense in B(X, Y, I)). More specifically, T hA, Bi, is infimum of attribute
concepts h{y}↓I , {y}↓I ↑I i for y ∈ B and A = y∈B {y}↓I .
↑I ↓I
W Dually, concepts h{x} , {x}↑I i for x ∈ X are object
T concepts, they are
-dense in B(X, Y, I) and for each concept hA, Bi, B = x∈A {x}↑I .
A subrelation J ⊆ I is called a closed subrelation of I if each concept of
hX, Y, Ji is also a concept of hX, Y, Ii. There is a correspondence between closed
subrelations of I and complete sublattices of B(X, Y, I) [2, Theorem 13]: For
each closed subrelation J ⊆ I, B(X, Y, J) is a complete sublattice of B(X, Y, I),
and to each complete sublattice V ⊆ B(X, Y, I) there exists a closed subrelation
J ⊆ I such that V = B(X, Y, J).
3 Closed subrelations for generated sublattices
Let us have a context hX, Y, Ii and a subset P of its concept lattice. Denote by
V the complete sublattice of B(X, Y, I) generated by P (i.e. V = CWV P ). Our
aim is to find, without computing the lattice B(X, Y, I), the closed subrelation
J ⊆ I whose concept lattice B(X, Y, J) is equal to V .
If B(X, Y, I) is finite, V can be obtained by alternating applications of the
closure operators CW and CV to P : we set V1 = CW P , V2 = CV V1 , . . . , and,
generally, VW W = CV Vi−1 for even i > 1. The
i = C Vi−1 for odd i > 1 and Vi V
sets Vi are -subsemilattices (for odd i) resp. -subsemilattices (for even i) of
B(X, Y, I). Once Vi = Vi−1 , we have the complete sublattice V .
Note that for infinite B(X, Y, I), V can be infinite even if P is finite. Indeed,
denoting F L(P ) the free lattice generated by P [3] and setting X = Y = F L(P ),
I = ≤ we have F L(P ) ⊆ V ⊆ B(X, Y, I). (B(X, Y, I) is the Dedekind-MacNeille
completion of F L(P ) [2], and we identify P and F L(P ) with subsets of B(X, Y, I)
as usual.) Now, if |P | > 2 then F L(P ) is infinite [3], and so is V .
We always consider sets Vi together with the appropriate restriction of the
ordering on B(X, Y, I). For each i > 0, Vi is a complete lattice (but not a complete
sublattice of B(X, Y, I)).
In what follows, we construct formal contexts with concept lattices isomor-
phic to the complete lattices Vi , i > 0. First, we find a formal context for the
complete lattice V1 . Let K1 ⊆ P × Y be given by
hhA, Bi, yi ∈ K1 iff y ∈ B. (3)
14 Martin Kauer and Michal Krupka
As we can see, rows in the context hP, Y, K1 i are exactly intents of concepts
from P .
Proposition 1. The concept lattice B(P, Y, K1 ) and the complete lattice V1 are
isomorphic. The isomorphism assigns to each concept hB ↓K1 , Bi ∈ B(P, Y, K1 )
the concept hB ↓I , Bi ∈ B(X, Y, I).
Proof. Concepts from V1 are exactly those with intents equal to intersections of
intents of concepts from P . The same holds for concepts from B(P, Y, K1 ).
Next we describe formal contexts for complete lattices Vi , i > 1. All of the
contexts are of the form hX, Y, Ki i, i.e. they have the set X as the set of objects
and the set Y as the set of attributes (the relation K1 is different in this regard).
The relations Ki for i > 1 are defined in a recursive manner:
x ∈ {y}↓Ki−1 ↑Ki−1 ↓I for even i,
for i > 1, hx, yi ∈ Ki iff (4)
y ∈ {x}↑Ki−1 ↓Ki−1 ↑I for odd i.
Proposition 2. For each i > 1,
1. Ki ⊆ I,
2. Ki ⊆ Ki+1 .
Proof. We will prove both parts for odd i; the assertions for even i are proved
similarly.
1. Let hx, yi ∈ Ki . From {y} ⊆ {y}↓Ki−1 ↑Ki−1 we get {y}↓Ki−1 ↑Ki−1 ↓I ⊆
{y}↓I . Thus, x ∈ {y}↓Ki−1 ↑Ki−1 ↓I implies x ∈ {y}↓I , which is equivalent to
hx, yi ∈ I.
2. As Ki ⊆ I, we have {y}↓Ki ↑Ki ↓I ⊇ {y}↓Ki ↑Ki ↓Ki = {y}↓Ki . Thus, x ∈
{y}↓Ki yields x ∈ {y}↓Ki ↑Ki ↓I .
We can see that the definitions of Ki for even and odd i > 1 are dual. In
what follows, we prove properties of Ki for even i and give the versions for odd
i without proofs.
First we give two basic properties of Ki that are equivalent to the defini-
tion. The first one says that Ki can be constructed as a union of some specific
rectangles, the second one will be used frequently in what follows.
Proposition 3. Let i > 1.
S
1. If i is even then Ki = y∈Y {y}↓Ki−1 ↑Ki−1 ↓I × {y}↓Ki−1 ↑Ki−1 . If i is odd then
S
Ki = x∈X {x}↑Ki−1 ↓Ki−1 ↑I × {x}↑Ki−1 ↓Ki−1 .
2. If i is even then for each y ∈ Y , {y}↓Ki = {y}↓Ki−1 ↑Ki−1 ↓I . If i is odd then
for each x ∈ X, {x}↑Ki = {x}↑Ki−1 ↓Ki−1 ↑I .
Proof. We will prove only the assertions for even i.
1. TheS “⊆” inclusion is evident. We will prove the converse inclusion. If
hx, yi ∈ y0 ∈Y {y 0 }↓Ki−1 ↑Ki−1 ↓I × {y 0 }↓Ki−1 ↑Ki−1 then there is y 0 ∈ Y such that
x ∈ {y 0 }↓Ki−1 ↑Ki−1 ↓I and y ∈ {y 0 }↓Ki−1 ↑Ki−1 . The latter implies {y}↓Ki−1 ↑Ki−1 ⊆
Subset-generated complete sublattices as concept lattices 15
{y 0 }↓Ki−1 ↑Ki−1 , whence {y 0 }↓Ki−1 ↑Ki−1 ↓I ⊆ {y}↓Ki−1 ↑Ki−1 ↓I . Thus, x belongs to
{y}↓Ki−1 ↑Ki−1 ↓I and by definition, hx, yi ∈ Ki .
2. Follows directly from the obvious fact that x ∈ {y}↓Ki if and only if
hx, yi ∈ Ki .
A direct consequence of 2. of Prop. 3 is the following.
Proposition 4. If i is even then each extent of Ki is also an extent of I. If i
is odd then each intent of Ki is also an intent of I.
Proof. Let i be even. 2. of Prop. 3 implies that each attribute extent of Ki is an
extent of I. Thus, the proposition follows from the fact that each extent of Ki
is an intersection of attribute extents of Ki .
The statement for odd i is proved similarly except for i = 1 where it follows
by definition.
Proposition 5. Let i > 1. If i is even then for each y ∈ Y it holds
{y}↓Ki−1 ↑Ki−1 = {y}↓Ki ↑Ki = {y}↓Ki ↑I .
If i is odd then for each x ∈ X we have
{x}↑Ki−1 ↓Ki−1 = {x}↑Ki ↓Ki = {x}↑Ki ↓I .
Proof. We will prove the assertion for even i. By Prop. 4, {y}↓Ki is an extent
of I. The corresponding intent is
{y}↓Ki ↑I = {y}↓Ki−1 ↑Ki−1 ↓I ↑I = {y}↓Ki−1 ↑Ki−1 (5)
(by Prop. 4, {y}↓Ki−1 ↑Ki−1 is an intent of I). Moreover, as Ki ⊆ I (Prop. 2), we
have
{y}↓Ki ↑Ki ⊆ {y}↓Ki ↑I . (6)
We prove {y}↓Ki−1 ↑Ki−1 ⊆ {y}↓Ki ↑Ki . Let y 0 ∈ {y}↓Ki−1 ↑Ki−1 . It holds
{y 0 }↓Ki−1 ↑Ki−1 ⊆ {y}↓Ki−1 ↑Ki−1
(↓Ki−1 ↑Ki−1 is a closure operator). Thus, {y}↓Ki−1 ↑Ki−1 ↓I ⊆ {y 0 }↓Ki−1 ↑Ki−1 ↓I
and so by 2. of Prop. 3, {y}↓Ki ⊆ {y 0 }↓Ki . Applying ↑Ki to both sides we obtain
{y 0 }↓Ki ↑Ki ⊆ {y}↓Ki ↑Ki proving y 0 ∈ {y}↓Ki ↑Ki .
This, together with (5) and (6), proves the proposition.
Proposition 6. Let i > 1 be even. Then for each intent B of Ki−1 it holds
B ↓Ki = B ↓I . Moreover, if B is an attribute intent (i.e. there is y ∈ Y such that
B = {y}↓Ki−1 ↑Ki−1 ) then hB ↓Ki , Bi is a concept of I.
If i > 1 is odd then for each extent A of Ki−1 it holds A↑Ki = A↑I . If A is an
object extent (i.e. there is x ∈ X such that A = {x}↑Ki−1 ↓Ki−1 ) then hA, A↑Ki i
is a concept of I.
16 Martin Kauer and Michal Krupka
Proof.S We will prove the assertion for even S
i. Let B be an intent of Ki−1 . It holds
B = y∈B {y} (obviously) and hence B = y∈B {y}↓Ki−1 ↑Ki−1 (since ↓Ki−1 ↑Ki−1
is a closure operator). Therefore (2. of Prop. 3),
!↓Ki
[ \ \
B ↓Ki = {y} = {y}↓Ki = {y}↓Ki−1 ↑Ki−1 ↓I
y∈B y∈B y∈B
!↓I
[
= {y}↓Ki−1 ↑Ki−1 = B ↓I ,
y∈B
proving the first part.
Now let B be an attribute intent of Ki−1 , B = {y}↓Ki−1 ↑Ki−1 . By 2. of Prop. 3
it holds B ↓I = {y}↓Ki . By Prop. 5, B ↓I ↑I = {y}↓Ki ↑I = {y}↓Ki−1 ↑Ki−1 = B.
Now we turn to complete lattices Vi defined above. We have already shown
in Prop. 1 that the complete lattice V1 and the concept lattice B(P, Y, K1 ) are
isomorphic. Now we give a general result for i > 0.
Proposition 7. For each i > 0, the concept lattice B(P, Y, Ki ) (for i = 1)
resp. B(X, Y, Ki ) (for i > 1) and the complete lattice Vi are isomorphic. The
isomorphism is given by hB ↓Ki , Bi 7→ hB ↓I , Bi if i is odd and by hA, A↑Ki i 7→
hA, A↑I i if i is even.
Proof. We will proceed by induction on i. The base step i = 1 has been already
proved in Prop. 1. We will do the induction step for even i, the other case is
dual.
As Vi = CV Vi−1 , we have to
1. show that the set W = {hA, A↑I i | A is an extent of Ki } is a subset of
B(X, Y, I), containing Vi−1 and
2. find for each hA, A↑Ki i ∈ B(X, Y, Ki ) a set of concepts from Vi−1 whose
infimum in B(X, Y, I) has extent equal to A.
1. By Prop. 4, each extent of Ki is also an extent of I. Thus, W ⊆ B(X, Y, I).
If hA, Bi ∈ Vi−1 then by the induction hypothesis B is an intent of Ki−1 (i − 1
is odd). By Prop. 6, B ↓Ki = B ↓I = A is an extent of Ki and so hA, Bi ∈ W .
2. Denote B = A↑Ki . For each y ∈ Y , {y}↓Ki−1 ↑Ki−1 is an intent of Ki−1 . By
Prop. 3 and the induction hypothesis,
h{y}↓Ki , {y}↓Ki−1 ↑Ki−1 i = h{y}↓Ki−1 ↑Ki−1 ↓I , {y}↓Ki−1 ↑Ki−1 i ∈ Vi−1 .
T of the infimum (taken in B(X, Y, I)) of these concepts for y ∈ B
Now, the extent
is equal to y∈B {y}↓Ki = B ↓Ki = A.
If X and Y are finite then 2. of Prop. 2 implies there is a number n > 1
such that Kn+1 = Kn . Denote this relation by J. According to Prop. 7, there
are two isomorphisms of the concept lattice B(X, Y, J) and Vn = Vn+1 = V . We
will show that these two isomorphisms coincide and B(X, Y, J) is actually equal
to V . This will also imply J is a closed subrelation of I.
Subset-generated complete sublattices as concept lattices 17
Proposition 8. B(X, Y, J) = V .
Proof. Let hA, Bi ∈ B(X, Y, J). It suffices to show that hA, Bi ∈ B(X, Y, I). As
J = Kn+1 = Kn we have J = Ki for some even i and also J = Ki for some odd i.
We can therefore apply both parts of Prop. 6 to J obtaining A = B ↓J = B ↓I
and B = A↑J = A↑I .
Algorithm 1 uses our results to compute the subrelation J for given hX, Y, Ii
and P .
Algorithm 1 Computing the closed subrelation J.
Input: formal context hX, Y, Ii, subset P ⊆ B(X, Y, I)
Output: the closed subrelation of J ⊆ I whose concept lattice is equal to CWV P
J ← relation K1 (3)
i←1
repeat
L←J
i←i+1
if i is even then
J ← {hx, yi ∈ X × Y | x ∈ {y}↓L ↑L ↓I }
else
J ← {hx, yi ∈ X × Y | y ∈ {x}↑L ↓L ↑I }
end if
until i > 2 & J = L
return J
Proposition 9. Algorithm 1 is correct and terminates after at most max(|I| +
1, 2) iterations.
Proof. Correctness follows from Prop. 8. The terminating condition ensures we
compare J and L only when they are both subrelations of the context hX, Y, Ii
(after the first iteration, L is a subrelation of hP, Y, K1 i and the comparison
would not make sense).
After each iteration, L holds the relation Ki−1 and J holds Ki (4). Thus,
except for the first iteration, we have L ⊆ J before the algorithm enters the
terminating condition (Prop. 2). As J is always a subset of I (Prop. 2), the
number of iterations will not be greater than |I| + 1. The only exception is
I = ∅. In this case, the algorithm will terminate after 2 steps due to the first
part of the terminating condition.
4 Examples and experiments
Let hX, Y, Ii be the formal context from Fig. 1 (left). The associated con-
cept lattice B(X, Y, I) is depicted in Fig. 1 (right). Let P = {c1 , c2 , c3 } where
18 Martin Kauer and Michal Krupka
I y1 y2 y3 y4 y5
x1 × ×
y1 y2 y3
x2 × × × x5 x4
x3 × ×
x4 × y4 y5
x5 × x1 x2 x3
Fig. 1: Formal context hX, Y, Ii (left) and concept lattice B(X, Y, I), together
with a subset P ⊆ B(X, Y, I), depicted by filled dots (right).
c1 = h{x1 }, {y1 , y4 }i, c2 = h{x1 , x2 }, {y1 }i, c3 = h{x2 , x5 }, {y2 }i are concepts
from B(X, Y, I). These concept are depicted in Fig. 1 by filled dots.
First, we construct the context hP, Y, K1 i (3). Rows in this context are intents
of concepts from P (see Fig.W2, left). The concept lattice B(P, Y, K1 ) (Fig. 2,
center) is isomorphic to the -subsemilattice V1 = CW P ⊆ B(X, Y, I) (Fig. 2,
right). It is easy to see that elements of B(P, Y, K1 ) and corresponding elements
K1 y1 y2 y3 y4 y5
y1 y2 y1 y2 y3
c1 × × x5 x4
c2 c3
c2 ×
c3 × y4 y4 y5
c1 x1 x2 x3
y3 , y5
Fig. 2: Formal
W context hP, Y, K1 i (left), the concept lattice B(P, Y, K1 ) (center)
and the -subsemilattice CW P ⊆ B(X, Y, I), isomorphic to B(P, Y, K1 ), depicted
by filled dots (right).
of V1 have the same intents.
Next step is to construct the subrelation K2 ⊆ I. By (4), K2 consists of ele-
ments hx, yi ∈ X ×Y Vsatisfying x ∈ {y}↓K1 ↑K1 ↓I . The concept lattice B(X, Y, K2 )
is isomorphic to the -subsemilattice V2 = CV V1 ⊆ B(X, Y, I). K2 , B(X, Y, K2 ),
and V2 are depicted in Fig. 3.
The subrelation K3 ⊆ I is computed again by (4). K3 consists of elements
hx, yi ∈ X × Y satisfying y ∈ {x}↑K2 ↓K2 ↑I . The result can be viewed in Fig. 4.
Subset-generated complete sublattices as concept lattices 19
K2 y1 y2 y3 y4 y5 x 3 , x4
x1 × ×
y1 y2 y1 y2 y3
x2 × × · x5 x4
x5
x3 · ·
x4 · y4 y4 y5
x5 × x1 x2 x1 x2 x3
y3 , y5
Fig. 3: Formal
V context hX, Y, K2 i (left), the concept lattice B(X, Y, K2 ) (center)
and the -subsemilattice V2 = CV V1 ⊆ B(X, Y, I), isomorphic to B(X, Y, K2 ),
depicted by filled dots (right). Elements of I \ K2 are depicted by dots in the
table.
K3 y1 y2 y3 y4 y5 x 3 , x4
x1 × ×
y1 y2 y1 y2 y3
x2 × × × x5 x4
x5
x3 · ·
x4 · y4 y3 y4 y5
x5 × x1 x2 x1 x2 x3
y5
Fig. 4: Formal
W context hX, Y, K3 i (left), the concept lattice B(X, Y, K3 ) (center)
and the -subsemilattice V3 = CW V2 ⊆ B(X, Y, I), isomorphic to B(X, Y, K3 ),
depicted by filled dots (right). Elements of I \ K3 are depicted by dots in the
table. As K3 = K4 = J, it is a closed subrelation of I and V4 = CV V3 = V3 is
a complete sublattice of B(X, Y, I).
Notice that already V3 = V2 but K3 6= K2 . We cannot stop and have to
perform another step. After computing K4 we can easily check that K4 = K3 .
We thus obtained the desired closed subrelation J ⊆ I and V4 = V3 is equal to
the desired complete sublattice V ⊆ B(X, Y, I).
In [1], the authors present an algorithm for computing a sublattice of a given
lattice generated by a given set of elements. Originally, we planned to include
a comparison between their approach and our Alg. 1. Unfortunately, the algo-
rithm in [1] turned out to be incorrect. It is based on the false claim that (using
our notation) the smallest element V of V , which is greater than or equal to an
element v ∈ B(X, Y, I), is equal to {p ∈ P | p ≥ v}. The algorithm from [1]
fails e.g. on the input depicted in Fig. 5.
20 Martin Kauer and Michal Krupka
p2
p1 v p3
Fig. 5: An example showing that the algorithm from [1] is incorrect. A complete
lattice with a selected subset P = {p1 , p2 , p3 }. The least element of the sublattice
V generated by P which is greater than or equal to v is p1 ∨ v. The algorithm
incorrectly chooses p2 and “forgets” to add p1 ∨ v to the output.
The time complexity of our algorithm is clearly polynomial w.r.t. |X| and
|Y |. In Prop. 9 we proved that the number of iterations is O(|I|). Our experi-
ments indicate that this number might be much smaller in the practice. We used
the Mushroom dataset from the UC Irvine Machine Learning Repository, which
contains 8124 objects, 119 attributes and 238710 concepts. For 39 different sizes
of the set P , we selected randomly its elements, 1000 times for each of the sizes.
For each P , we ran our algorithm and measured the number n of iterations, af-
ter which the algorithm terminated. We can see in Tbl. 1 maximal and average
values of n, separately for each size of P . From the results in Tbl. 1 we can see
|P |(%) Max n Avg n |P |(%) Max n Avg n |P |(%) Max n Avg n
0.005 11 7 0.25 6 3 0.90 5 3
0.010 10 6 0.30 6 3 0.95 4 3
0.015 10 5 0.35 6 3 1 4 3
0.020 10 5 0.40 5 3 2 4 3
0.025 8 5 0.45 5 3 3 4 3
0.030 8 4 0.50 5 3 4 4 3
0.035 8 4 0.55 6 3 5 4 2
0.040 7 4 0.60 5 3 6 4 2
0.045 10 4 0.65 4 3 7 4 2
0.050 8 4 0.70 5 3 8 3 2
0.100 6 4 0.75 6 3 9 3 2
0.150 6 4 0.80 6 3 10 3 2
0.200 6 4 0.85 4 3 11 3 2
Table 1: Results of experiments on Mushrooms dataset. The size of P is given
by the percentage of the size of the concept lattice.
that the number of iterations (both maximal and average values) is very small
compared to the number of objects and attributes. There is also an apparent
decreasing trend of number of iterations for increasing size of P .
Subset-generated complete sublattices as concept lattices 21
5 Conclusion and open problems
An obvious advantage of our approach is that we avoid computing the whole con-
cept lattice B(X, Y, I). This should lead to shorter computation time, especially
if the generated sublattice V is substantially smaller than B(X, Y, I).
The following is an interesting observation and an open problem. It is men-
tioned in [2] that the system of all closed subrelations of I is not a closure
system and, consequently, there does not exist a closure operator assigning to
each subrelation of I a least greater (w.r.t. set inclusion) closed subrelation.
This is indeed true as the intersection of closed subrelations need not be a closed
subrelation. However, our method can be easily modified to compute for any
subrelation K ⊆ I a closed subrelation J ⊇ K, which seems to be minimal in
some sense. Indeed, we can set K1 = K and compute a relation J as described
by Alg. 1, regardless of the fact that K does not satisfy our requirements (intents
of K need not be intents of I). The relation J will be a closed subrelation of I
and it will contain K as a subset. Also note that the dual construction leads to
a different closed subrelation.
Another open problem is whether it is possible to improve the estimation of
the number of iterations of Alg. 1 from Prop. 9. In fact, we were not able to
construct any example with the number of iterations greater than min(|X|, |Y |).
References
1. Bertet, K., Morvan, M.: Computing the sublattice of a lattice generated by a set of
elements. In: Proceedings of Third International Conference on Orders, Algorithms
and Applications. Montpellier, France (1999)
2. Ganter, B., Wille, R.: Formal Concept Analysis – Mathematical Foundations.
Springer (1999)
3. Whitman, P.M.: Free lattices II. Annals of Mathematics 43(1), pp. 104–115 (1942)
4. Wille, R.: Restructuring lattice theory: an approach based on hierarchies of concepts.
In: Rival, I. (ed.) Ordered Sets, pp. 445–470. Boston (1982)