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 corresponding 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.
Introduction and problem statement
Complete lattices and Formal Concept Analysis
For a subset P ⊆ U we denote by CWP the W-subsemilattice of U generated by P , i.e. the smallest (w.r.t. set inclusion) W-subsemilattice of U containing P . CWP always exists and is equal to the intersection of all W-subsemilattices of U containing P . The V-subsemilattice of U generated by P and the complete sublattice of U generated by P are defined similarly and are denoted by CVP and CWVP , 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
Concept lattices have been introduced in [4], our basic reference is [2]. A (formal ) 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 A2↑I ⊆ A1↑I , 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, B1i ≤ hA2, B2i 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
^ hAj , Bj i =
j∈J
[ Aj
j∈J
[ Bj
j∈J
!↑I ↓I
!↓I ↑I +
+
, \ Bj .
j∈J
(
\ Aj = j∈J [ Bj j∈J !↓I , 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 is infimum of some attribute concepts (we say the set of all attribute concepts is V-dense in B(X, Y, I)). More specifically, hA, Bi, is infimum of attribute concepts h{y}↓I , {y}↓I ↑I i for y ∈ B and A = Ty∈B{y}↓I .
Dually, concepts h{x}↑I ↓I , {x}↑I i for x ∈ X are object concepts, they are W-dense in B(X, Y, I) and for each concept hA, Bi, B = Tx∈A{x}↑I .
A subrelation J ⊆ I is called a closed subrelation of I if each concept of hX, Y, J i 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 = CWVP ). 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 = CWP , V2 = CVV1, . . . , and, generally, Vi = CWVi−1 for odd i > 1 and Vi = CVVi−1 for even i > 1. The sets Vi are W-subsemilattices (for odd i) resp. V-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
isomorphic 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.
(
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, Kii, 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: for i > 1, hx, yi ∈ Ki iff x ∈ {y}↓Ki−1 ↑Ki−1 ↓I for even i, y ∈ {x}↑Ki−1 ↓Ki−1 ↑I for odd i.
(
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 definition. 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.
1. If i is even then Ki = Sy∈Y {y}↓Ki−1 ↑Ki−1 ↓I × {y}↓Ki−1 ↑Ki−1 . If i is odd then
Ki = Sx∈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. The “⊆” inclusion is evident. We will prove the converse inclusion. If hx, yi ∈ Sy0∈Y {y0}↓Ki−1 ↑Ki−1 ↓I × {y0}↓Ki−1 ↑Ki−1 then there is y0 ∈ Y such that x ∈ {y0}↓Ki−1 ↑Ki−1 ↓I and y ∈ {y0}↓Ki−1 ↑Ki−1 . The latter implies {y}↓Ki−1 ↑Ki−1 ⊆ {y0}↓Ki−1 ↑Ki−1 , whence {y0}↓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 y0 ∈ {y}↓Ki−1 ↑Ki−1 . It holds {y0}↓Ki−1 ↑Ki−1 ⊆ {y}↓Ki−1 ↑Ki−1 (↓Ki−1 ↑Ki−1 is a closure operator). Thus, {y}↓Ki−1 ↑Ki−1 ↓I ⊆ {y0}↓Ki−1 ↑Ki−1 ↓I and so by 2. of Prop. 3, {y}↓Ki ⊆ {y0}↓Ki . Applying ↑Ki to both sides we obtain {y0}↓Ki ↑Ki ⊆ {y}↓Ki ↑Ki proving y0 ∈ {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. Proof. We will prove the assertion for even i. Let B be an intent of Ki−1. It holds B = Sy∈B{y} (obviously) and hence B = Sy∈B{y}↓Ki−1 ↑Ki−1 (since ↓Ki−1 ↑Ki−1 is a closure operator). Therefore (2. of Prop. 3),
B↓Ki = = [ {y} y∈B
!↓Ki [ {y}↓Ki−1 ↑Ki−1 y∈B y∈B
!↓I = \ {y}↓Ki = \ {y}↓Ki−1 ↑Ki−1 ↓I
y∈B = B↓I , 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 = CVVi−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. Now, the extent of the infimum (taken in B(X, Y, I)) of these concepts for y ∈ B is equal to Ty∈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.
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 CWVP
J ← relation K1 (
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, K1i and the comparison would not make sense).
After each iteration, L holds the relation Ki−1 and J holds Ki (
Let hX, Y, Ii be the formal context from Fig. 1 (left). The associated concept lattice B(X, Y, I) is depicted in Fig. 1 (right). Let P = {c1, c2, c3} where
I y1 y2 y3 y4 y5 x1 × × x2 × × × x3 × × x4 × x5 × y1 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, K1i (
Next step is to construct the subrelation K2 ⊆ I. By (
The subrelation K3 ⊆ I is computed again by (
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 algorithm in [1] turned out to be incorrect. It is based on the false claim that (using our notation) the smallest element of V , which is greater than or equal to an element v ∈ B(X, Y, I), is equal to V{p ∈ P | p ≥ v}. The algorithm from [1] fails e.g. on the input depicted in Fig. 5.
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 experiments 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, after 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 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 .
An obvious advantage of our approach is that we avoid computing the whole concept 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 mentioned 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 |).