The size of a concept lattice may increase exponentially with the size of the context. When the number of nodes is too large, it becomes very difficult to generate and study such a concept lattice. A way to avoid this problem is to break down the lattice into small parts. In the subdirect decomposition, the small parts are factor lattices which are meaningful in the Formal Concept Analysis (FCA) setting. In this paper a walkthrough from a finite reduced context to its subdirect decomposition into subdirectly irreducible subcontexts and factors is given. The decomposition can be reached using three different points of view, namely factor lattices, arrow relations and compatible subcontexts. The approach is mainly algebraic since it is based on abstract lattice theory, except for the last point which is inherited from FCA. We also propose a polynomial algorithm to generate the decomposition of an initial context into subcontexts. Such a procedure can be extended to conduct an interactive exploration and mining of large contexts, including the generation of few concepts and their neighborhood.
During the last decade, the computation capabilities have promoted Formal Concept Analysis (FCA) with new methods based on concept lattices. Though they are exponential in space/time in worst case, concept lattices of a reasonable size enable an intuitive representation of data organized by a context that links objects to attributes through a binary relation. Methods based on concept lattices have been developed in various domains such as knowledge discovery and representation, database management and information retrieval where some relevant concepts, i.e. possible correspondences between objects and attributes are considered either as classifiers, clusters or representative object/attribute subsets.
With the increasing size of data, a set of methods have been proposed in
order to either generate a subset (rather than the whole set) of concepts and
their neighborhood (e.g. successors and predecessors) in an online and
interactive way [
In this paper we investigate the subdirect decomposition of a concept lattice
as a first step towards an interactive exploration and mining of large contexts.
The subdirect decomposition of a lattice L into factor lattices (Li)i∈{1,...,n},
denoted by L ,→ L1 ×· · ·×Ln, is defined by two properties (see important results in
[
As suggested in [
In this paper, we propose a subdirect and polynomial decomposition of a context into subcontexts by extending the subdirect decomposition of a lattice into factor lattices. This decomposition leads to data storage saving of large contexts. Indeed, the generation of the whole set of factor lattices can be avoided by providing an interactive generation of a few (but not all) concepts and their neighborhood from large contexts. Moreover, a focus on a specific factor lattice can be proposed to the user by generating, partially or entirely, the concept lattice and/or a basis of implications.
There are at least two reasons for studying this case of pattern management. The first one comes from the fact that users tend to be overwhelmed by the knowledge extracted from data, even when the input is relatively small. The second reason is that the community of FCA has made progress in lattice construction and exploration, and hence existing solutions can be adapted and enriched to only target useful patterns (i.e. pieces of knowledge).
This paper is organized as follows. Section 2 introduces the subdirect decomposition and the three different points of view, namely factor lattices, arrow relations and compatible subcontexts. Section 3 contains the main contribution of this paper about the subdirect decomposition and the proposed algorithms. A preliminary empirical study is presented in Section 4 while Section 5 presents future work. 2
Throughout this paper all sets (and thus lattices) are considered to be finite. 2.1
Algebraic lattice Let us first recall that a lattice (L, ≤) is an ordered set in which every pair (x, y) of elements has a least upper bound, called join x ∨ y, and a greatest lower bound, called meet x ∧ y. As we are only considering finite structures, every subset A ⊂ L has a join and meet (e. g. finite lattices are complete).
Concept or Galois Lattice A (formal) context (O, A, R) is defined by a set O of objects, a set A of attributes, and a binary relation R ⊂ O × A, between O and A. Two operators are derived: – for each subset X ⊂ O, we define X0 = {m ∈ A, j R m ∀j ∈ X} and dually, – for each subset Y ⊂ A, we define Y 0 = {j ∈ O, j R m ∀m ∈ Y }.
A (formal) concept represents a maximal objects-attributes correspondence by a pair (X, Y ) such that X0 = Y and Y 0 = X. The sets X and Y are respectively called extent and intent of the concept. The set of concepts derived from a context is ordered as follows:
(X1, Y1) ≤ (X2, Y2) ⇐⇒ X1 ⊆ X2 ⇐⇒ Y2 ⊆ Y1
The whole set of formal concepts together with this order relation form a complete lattice, called the concept lattice of the context (O, A, R). Different formal contexts can provide isomorphic concept lattices, and there exists a unique one, named the reduced context, defined by the two sets O and A of the smallest size.
This particular context is introduced by means of special concepts or elements of the lattice L, namely irreducible elements.
An element j ∈ L is join-irreducible if it is not a least upper bound of a subset not containing it. The set of join irreducible elements is noted JL. Meet-irreducible elements are defined dually and their set is ML. As a direct consequence, an element j ∈ L is join-irreducible if and only if it has only one immediate predecessor denoted j−. Dually, an element m ∈ L is meet-irreducible if and only if it has only one immediate successor denoted m+.
In Figure 1, join-irreducible nodes are labelled with a number and
meet-irreducible nodes are labelled with a letter.
Fundamental Bijection A fundamental result [
As a direct consequence, there is a bijection between lattices and reduced contexts where objects of the context are associated with join-irreducible concepts of the lattice, and attributes are associated with meet-irreducible concepts.
Figure 2 shows the reduced context of the lattice in Figure 1.
Compatible subcontexts A subcontext of a formal context (O, A, R) is a triple (J, M, R ∩ J × M ) such that J ⊂ O and M ⊂ A. A subcontext (J, M, R ∩ J × M ) of (O, A, R) is compatible if for each concept (H, N ) of (O, A, R), (J ∩ H, M ∩ N ) is a concept of (J, M, R ∩ J × M ).
Arrow relations The arrow-closed subcontexts involved in the equivalence
are based on the arrow relations between join and meet irreducible concepts of
a lattice. Consider the reduced context (JL, ML, ≤) of a lattice (L, ≤). Arrow
relations [
In Figure 3, the reduced context of Figure 2 is enriched with the four relations l, ↑, ↓, and ◦ in the empty cells that both correspond to the case where j 6≤ m: b c d f g j 2 × × × × × l 3 × l × ↓ × × 5 × × × l l ◦ 6 × × l × ↓ ◦ 9 l × ◦ × ◦ ◦
Fig. 3. Arrow relation As an illustration, let j = 5 and m = f be join-irreducible and meetirreducible nodes respectively (see Figure 1). Then, j− = 2 and m+ = c. The relation 5 l f holds since 5 6≤ f , 5 ≤ c and 2 ≤ f .
Arrow-closed subcontext A subcontext (J, M, R ∩ J × M ) of a context (O, A, R) is an arrow-closed subcontext when the following conditions are met: – If j ↑ m and j ∈ J then m ∈ M – If j ↓ m and m ∈ M then j ∈ J
As an example, the first subcontext of Figure 4 is an arrow-closed subcontext of the reduced context of Figure 3 whereas the second one is not, due to the down-arrow 6 ↓ g.
c d f g
3 x x
5 x x
6 x x
c d f g
3 x x
5 x x
Equivalence theorem First let us introduce the first equivalence we need in
this paper, whose proof can be found in [
– The subcontext (J, M, R ∩ J × M ) is an arrow-closed one. 2.3
In this section, we introduce the equivalence between congruence relations and arrow-closed subcontexts.
Quotient An equivalence relation is a binary relation R over a set E which is reflexive, symmetric, and transitive. An equivalence class of x ∈ E is: The set of equivalence classes, called the quotient set E/R, is: xR = {y ∈ E | xRy}
E/R = {xR | x ∈ E} Factor lattice A congruence relation Θ on a lattice L is an equivalence relation such that:
x1Θy1 and x2Θy2 =⇒ x1 ∧ x2Θy1 ∧ y2 and x1 ∨ x2Θy1 ∨ y2
xΘ ≤ yΘ ⇐⇒ xΘ(x ∧ y) ⇐⇒ (x ∨ y)Θy
With such an order, L/Θ is a lattice, called factor lattice. A standard theorem
from algebra, whose proof is omitted, states that:
Theorem 2. The projection L → L/Θ is a lattice morphism onto.
The second equivalence theorem We are now able to formulate the second
equivalence whose proof can be found in [
Congruence relations will be computed with this theorem. However, other
algorithms exist [
In this section, we introduce the equivalence between subdirect decompositions and sets of arrow-closed subcontexts.
Definition 1. A subdirect product is a sublattice of a direct product L1 ×· · ·×Ln of lattices Li, i ∈ {1, . . . , n} such that each projection onto a factor is surjective. The lattices Li, i ∈ {1, . . . , n} are the factor lattices. A subdirect decomposition of a lattice L is an isomorphism between L and a subdirect product which can be denoted as:
L ,→ L1 × · · · × Ln
Li
The third equivalence theorem The third and most important equivalence
whose proof can be found in [
From the three previous equivalences found in [
In the following, we exploit these four notions that, to the best of our knowledge, have not been put together yet. 1. The subdirect decomposition ensures that L is a sublattice of the factor lattice product. Moreover, each projection from L to a factor lattice is surjective. 2. The congruence relations of L indicate that factor lattices correspond to their quotient lattices, and thus preserve partitions via equivalence classes. 3. The compatible subcontexts give a way to compute the morphism from L onto its factors. 4. Arrow-closed subcontexts enable the computation of the reduced context of the factor lattices.
In the following we present the generation of a particular subdirect decomposition and show a possible usage of factor lattices. 3.2
In this section, we consider subdirect decompositions of a lattice L with its
reduced context (O, A, R) as input. From Corollary 2, a subdirect decomposition
of a lattice L can be obtained by computing a set of arrow-closed subcontexts of
(O, A, R) that have to cover O and A. There are many sets of arrow-closed
subcontexts and thus many subdirect decompositions. In particular, the
decomposition from a lattice L into L itself is a subdirect decomposition, corresponding to
the whole subcontext (O, A, R) which is clearly arrow-closed. A subdirect
decomposition algorithm has been proposed in [
In this article, we focus on the subdirect decomposition of a context into a
possibly large number of small factors, i.e. factors that cannot be subdirectly
decomposed. A factor lattice L is subdirectly irreducible when any subdirect
decomposition of L leads to L itself. A nice characterization of subdirectly
irreducible lattices can be found in [
A context (O, A, R) is one-generated if it can be obtained by arrow-closing a context with only one j ∈ J . Thus (O, A, R) is the smallest arrow-closed subcontext containing j ∈ J .
Therefore, we deduce the following result: Proposition 3. Let L be a lattice. From L, we can deduce a product lattice L1 × ... × Ln where each lattice Li is: – the concept lattice of a one-generated subcontext, – subdirectly irreducible, – a factor lattice of the subdirectly irreducible decomposition.
From this result, we propose an algorithm (Algorithm 1) to compute in polynomial time the contexts of the factor lattices L1, . . . , ...Ln of a subdirectly irreducible decomposition, with a reduced context (O, A, R) as input. The onegenerated subcontexts for each j ∈ J are obtained by arrow-closing (Algorithm 2). The subdirectly irreducible decomposition of L can then be obtained by computing the concept lattices of these subcontexts.
One can notice that the closure computed from join-irreducible concepts can also be calculated from meet-irreducible concepts.
Algorithm 1: Subdirect Decomposition
Input: A context (O, A, R) Output: List L of the contexts (Jj , Mj , Rj ) of the subdirectly irreducible factor lattices 1 L ← ∅; 2 forall the j ∈ O do 3 Compute (Jj , Mj , Rj ) = Arrow Closure((j, ∅, ∅), (O, A, R)), the one-generated subcontext span by j; 4 if L does not contain any subcontext that covers (Jj , Mj , Rj ) then 5 add (Jj , Mj , Rj ) to L return L;
Input: A subcontext (J˜, M˜ , R˜) of a context (J, M, R)
Output: Arrow-closure of (J˜, M˜ , R˜) 1 Jc = J˜; Mc = M˜ ; 2 predJ = 0; predM = 0; 3 while predM < card(Mc) or predJ < card(Jc) do 4 predJ = card(Jc); 5 predM = card(Mc); 6 forall the j ∈ Jc do 7 add to Mc all m ∈ M such that j ↑ m;
Consider the reduced context in Figure 2. Each iteration of Algorithm 1 is described by Figure 5 for each value of j, the input and output of Algorithm 2, and the three one-generated subcontexts that belong to L at the end of the process. Therefore we get three factor lattices (see Figure 6).
The first subcontext is the one on the left of Figure 4. The two other ones are: ({2}, {j}, ∅) and ({9}, {b}, ∅). The latter two subcontexts are interesting because: – They show that the initial lattice has parts which are distributive. Indeed, these two subcontexts contain exactly one double arrow in each line and each column. – They give us a dichotomy: any concept contains either 2 or j ; any concept contains either 9 or b – In the reduced context, an arrow brings a deeper knowledge than a cross. (b) First subcontext in Figure 4 (c) ({9}, {b}, ∅)
The context on the left hand-side of Figure 4 is tricky to understand. For the other ones, we have a simple relation 2 l j or 9 l b, which means that, for instance, 2 and j are some kind of complement or converse.
Figure 7 shows a factor lattice and its corresponding congruence. A subdirect decomposition of a lattice L into factor lattices L1, . . . , Ln is relevant since there exists an into morphism from L to the product lattice L1 × . . . × Ln. This morphism is specified by the bijection between compatible subcontexts and congruence relations stated by Corollary 1: Proposition 4. Let (J, M, R ∩ J × M ) be a compatible subcontext, then the relation ΘJ,M defined by:
(A1, B1)ΘJ,M (A2, B2) ⇐⇒ A1 ∩ J = A2 ∩ J ⇐⇒ B1 ∩ M = B2 ∩ M is a congruence relation, and its factor lattice is isomorphic to the concept lattice of the subcontext (J, M, R ∩ J × M ).
Algorithm 3 computes this morphism: each concept of L is computed as the product of concepts in each factor, and then marked in the product lattice. From Algorithm 3, we get the large tagged lattice product shown in Figure 8. Obviously, this algorithm is not intended to be used in a real application with large contexts since the product lattice is much more bigger than the original one, while the main goal of the decomposition is to get smaller lattices. We only use this algorithm in the empirical study.
Nevertheless, this morphism can be extended to develop basic FCA processing. Once the subdirectly irreducible decomposition of a reduced context (O, A, R) into the contexts C1, . . . , Cn is computed, an interactive exploration and mining process can easily be considered by using the following basic tasks and avoiding the generation of the lattice for the whole context (O, A, R): – Compute the smallest concept of L that contains a given subset of objects or attributes, and identify its neighborhood – Compute the smallest concept cij and its neighborhood in a subset of factors that contain a given collection of objects or attributes. Each factor Li is a specific view of data.
Input: Initial lattice L; Subcontexts (Jj, Mj, Rj); Product lattice P = L1 × . . . × Ln
Output: Product lattice P with nodes coming from L marked. 1 forall the c = (A, B) ∈ L do 2 forall the (Jj, Mj, Rj) do 3 Compute (A ∩ Jj, B ∩ Mj); 4
Mark, in P , the product node Πj(A ∩ Jj, B ∩ Mj); 4
In this section, we conduct an empirical study in order to better understand the impact of the subdirect decomposition on contexts with different density levels. All the tests were done using the java-lattices library available at: http://thegalactic.github.io/java-lattices/
A thousand of contexts of 10 observations and 5 attributes were randomly generated. The experiments have been done three times using three density values, namely 20%, 50% and 80%. Figure 9 presents the number of generated lattices according to their size and their density. We can observe two histograms with a nice gaussian shape in the first two cases, but a strange behavior in the last case. However, we roughly observe that the higher the density is, the bigger the lattices are. Therefore, the context density will have an impact on the decomposition process.
(a) Density of 20% (b) Density of 50%
(c) Density of 80%
The number of generated factors is given in Figure 10. One can observe that this number increases with the density of the initial context since the corresponding lattices have more edges. With a context density of 20%, we get 87.40% irreducible contexts. However, with a density of 80%, only 1.50% of contexts are irreducible and 70% of contexts have at least 4 factors in their decomposition. Thus, lattices are more decomposable when they come from dense contexts. Factors Density=20% Density=50% Density=80% 1 87.40% 70.50% 1.50% 2 9.70% 21.40% 9.90% 3 2.60% 6.20% 18.70% 4 0.30% 0.50% 23.40% 5 1.40% 28.50% 6 18.00%
Let us now examine the size of factors with two different density values, namely 20% and 50%. Figure 11 gives the number of cases (initial lattices) according to the number of produced factors. Of course, we observe that smaller lattices give rise to smaller factors. We can also see that in these two density cases, the largest number is obtained for factors of size 2.
(a) Density 20% (b) Density 50%
The last part of the tests aims at using contexts with a large density of 80% and computing the ratio between the number of nodes (edges resp.) of the initial lattice and the number of nodes (edges resp.) of the product lattice.
We thus get Figure 12 which shows that the higher is the number of factors, the bigger is the product lattice. Consequently, the set of useless (void) nodes in the product becomes larger as the number of factors increases.
We have also conducted experiments with 40 observations and 15 attributes, and a hundred of contexts were generated using two density values: 20% and 50%. Unfortunately, all were subdirectly irreducible.
In this paper, we have presented a polynomial algorithm for the decomposition
of a reduced context into subcontexts such that the concept lattice of each
subcontext is a subdirectly irreducible factor. This decomposition is a direct
consequence inferred from strong links between factors of a subdirect decomposition,
congruence relations, arrow-closed subcontexts and compatible subcontexts
established in [
To further investigate the subdirect decomposition, it would be interesting to
conduct large-scale experiments on real world data not only to confirm/nullify
the preliminary empirical tests but also to understand the semantics behind
the generated irreducible contexts. In particular, attributes covered by several
factors interfere in different views of data whose semantics must be interesting
to understand. Moreover, it would be useful to allow the user to interactively
select a few factors of the decomposition by mixing our approach with the one
in [
From a theoretical point of view, we think that there are strong links between
the implication basis in a quotient lattice and the one from the initial lattice. To
the best of our knowledge, this issue has never been addressed and could have
significant algorithmic impacts. However, we note that [
Since the empirical study in [