Jean-François Viaud
email: jviaud@univ-lr.fr

Karell Bertet
email: kbertet@univ-lr.fr

Christophe Demko
email: cdemko@univ-lr.fr

Rokia Missaoui
email: rokia.missaoui@uqo.ca

Subdirect Decomposition of Contexts into Subdirectly Irreducible Factors

Keywords: concept lattice, congruence relation, factor lattice, arrow relation, arrow closed subcontext, compatible subcontext

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

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 [START_REF] Ferré | Reconciling Expressivity and Usability in Information Access from File Systems to the Semantic Web[END_REF][START_REF] Visani | Navigala: an Original Symbol Classifier Based on Navigation through a Galois Lattice[END_REF] or better display lattices using nested line diagrams [START_REF] Ganter | Formal concept analysis -mathematical foundations[END_REF]. Such approaches become inefficient when contexts are huge. However, the main idea of lattice/context decomposition into smaller ones is still relevant when the classification property of the initial lattice is maintained. Many lattice decompositions have been defined and studied, both from algebraic [START_REF] Demel | Fast algorithms for finding a subdirect decomposition and interesting congruences of finite algebras[END_REF][START_REF] Mihók | Unique factorization theorem and formal concept analysis[END_REF] and FCA points of view [START_REF] Ganter | Formal concept analysis -mathematical foundations[END_REF][START_REF] Funk | Algorithms for concept lattice decomposition and their applications[END_REF]. We can cite Unique Factorisation Theorem [START_REF] Mihók | Unique factorization theorem and formal concept analysis[END_REF], matrix decomposition [START_REF] Belohlavek | Discovery of optimal factors in binary data via a novel method of matrix decomposition[END_REF], Atlas decomposition [START_REF] Ganter | Formal concept analysis -mathematical foundations[END_REF], subtensorial decomposition [START_REF] Ganter | Formal concept analysis -mathematical foundations[END_REF], doubling convex construction [START_REF] Day | Congruence normality: The characterization of the doubling class of convex sets[END_REF][START_REF] Nation | Alan day's doubling construction[END_REF][START_REF] Geyer | The generalized doubling construction and formal concept analysis[END_REF][START_REF] Bertet | Doubling convec sets in lattices: characterizations and recognition algorithms[END_REF] and subdirect decomposition. The latter has been widely studied many years ago, in the field of universal algebra [START_REF] Demel | Fast algorithms for finding a subdirect decomposition and interesting congruences of finite algebras[END_REF][START_REF] Freese | Computing congruences efficiently[END_REF], and even in FCA [START_REF] Wille | Subdirekte produkte und konjunkte summen[END_REF][START_REF] Wille | Subdirekte Produkte vollständiger Verbände[END_REF][START_REF] Wille | Subdirect decomposition of concept lattices[END_REF][START_REF] Wille | Subdirect product construction of concept lattices[END_REF][START_REF] Funk | Algorithms for concept lattice decomposition and their applications[END_REF]. To the best of our knowledge, there is no new development or novel algorithms for subdirect decomposition of contexts.

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 (L i ) i∈{1,...,n} , denoted by L → L 1 ו • •×L n , is defined by two properties (see important results in [START_REF] Ganter | Formal concept analysis -mathematical foundations[END_REF]): (i) L is a sublattice of the direct product L 1 ו • •×L n , and (ii) each projection of L onto a factor is surjective. The first property establishes that each factor lattice is the concept lattice of an arrow-closed subcontext, i.e. closed according to the arrow relation between objects and attributes. This means that the decomposition can be obtained by computing specific subcontexts. The second property states that there is an equivalence between arrow-closed subcontexts and congruence relations of L, i.e., an equivalence relation whose equivalence classes form a lattice with elements closed by the meet and join operations. This means that the concepts of L can be retrieved from the factor lattices, and the classification property of L is maintained since each equivalence relation forms a partition of the elements. The last result establishes an equivalence between arrow-closed subcontexts and compatible subcontexts, i.e. subcontexts such that each concept corresponds to a concept of the initial lattice. This result gives a way to compute the morphism from L into the direct product, and thus to retrieve the concepts of L from the factor lattices. In this paper, we deduce from these results strong links between the following notions that have not been used yet together as far as we know:

-Factors of a subdirect decomposition, -Congruence relations, -Arrow-closed subcontexts and -Compatible subcontexts.

As suggested in [START_REF] Ganter | Formal concept analysis -mathematical foundations[END_REF], the contexts of the factors of a particular subdirect decomposition, namely the subdirectly irreducible subcontexts, can be obtained by a polynomial processing of each row/object of the initial context. Therefore, the subdirect decomposition of a lattice can be extended to a subdirect decomposition of its reduced context into subdirect and irreducible subcontexts.

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.

Structural framework

Throughout this paper all sets (and thus lattices) are considered to be finite.

Lattices and Formal Concept Analysis

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). for each subset X ⊂ O, we define X = {m ∈ A, j R m ∀j ∈ X} and dually,

Concept or Galois Lattice

-for each subset Y ⊂ A, we define Y = {j ∈ O, j R m ∀m ∈ Y }.
A (formal) concept represents a maximal objects-attributes correspondence by a pair (X, Y ) such that X = Y and Y = 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:

(X 1 , Y 1 ) ≤ (X 2 , Y 2 ) ⇐⇒ X 1 ⊆ X 2 ⇐⇒ Y 2 ⊆ Y 1
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 J L . Meet-irreducible elements are defined dually and their set is M L . 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.

Fig. 1. A lattice with its irreducible nodes

Fundamental Bijection A fundamental result [START_REF]L'ordre et la classification. Algèbre et combinatoire[END_REF] establishes that any lattice (L, ≤) is isomorphic to the concept lattice of the context (J L , M L , ≤), where J L and M L are the join and meet irreducible concepts of L, respectively. Moreover, this context is a reduced one.

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.

b c d f g j 2 x x x x x 3 x x x x 5 x x x 6 x x x 9 x x Fig. 2. The reduced context of the lattice in Figure 1 2

.2 Compatible and Arrow-closed Subcontexts

This section is dedicated to the equivalence between compatible and arrow-closed subcontexts.

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 (J L , M L , ≤) of a lattice (L, ≤). Arrow relations [START_REF] Crawley | Algebraic theory of lattices[END_REF][START_REF] Grätzer | General lattice theory[END_REF] form a partition of the relation ≤ (defined by not having x ≤ y) by considering the immediate predecessor j -of a join-irreducible j, and the unique immediate successor m + of a meet-irreducible m:

-j m if j ≤ m, j ≤ m + and j -≤ m. -j ↑ m if j ≤ m, j ≤ m + and j -≤ m. -j ↓ m if j ≤ m, j ≤ m + and j -≤ m. -j • m if j ≤ m, j ≤ m + and j -≤ m.
In Figure 3, the reduced context of Figure 2 is enriched with the four relations , ↑, ↓, and • in the empty cells that both correspond to the case where j ≤ m:

b c d f g j 2 × × × × × 3 × × ↓ × × 5 × × × • 6 × × × ↓ • 9 × • × • • 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 f holds since 5 ≤ 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. Equivalence theorem First let us introduce the first equivalence we need in this paper, whose proof can be found in [START_REF] Ganter | Formal concept analysis -mathematical foundations[END_REF]:

Theorem 1. Let (J, M, R ∩ J × M ) be a subcontext of (O, A, R).
The following propositions are equivalent:

-The subcontext (J, M, R ∩ J × M ) is a compatible one. -The subcontext (J, M, R ∩ J × M ) is an arrow-closed one.

Congruence Relations and Factor Lattices

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:

x R = {y ∈ E | xRy}
The set of equivalence classes, called the quotient set E/R, is:

E/R = {x R | x ∈ E}
Factor lattice A congruence relation Θ on a lattice L is an equivalence relation such that:

x 1 Θy 1 and x 2 Θy 2 =⇒ x 1 ∧ x 2 Θy 1 ∧ y 2 and x 1 ∨ x 2 Θy 1 ∨ y 2
The quotient L/Θ verifies the following statement:

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 [START_REF] Ganter | Formal concept analysis -mathematical foundations[END_REF]:

Theorem 3. Given a lattice L, the set of congruence relations on L corresponds bijectively with the set of arrow-closed subcontexts of the reduced context of L.

Congruence relations will be computed with this theorem. However, other algorithms exist [START_REF] Freese | Computing congruence lattices of finite lattices[END_REF][START_REF] Freese | Algorithms in finite, finitely presented and free lattices[END_REF].

Subdirect decompositions

In this section, we introduce the equivalence between subdirect decompositions and sets of arrow-closed subcontexts.

Subdirect product Definition 1. A subdirect product is a sublattice of a direct product L 1 ו • •×L n of lattices L i , i ∈ {1, . . . , n} such that each projection onto a factor is surjective. The lattices L i , 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 → L 1 × • • • × L n L i
The third equivalence theorem The third and most important equivalence whose proof can be found in [START_REF] Ganter | Formal concept analysis -mathematical foundations[END_REF], makes a connection with sets of arrows-closed subcontexts when they cover the initial context:

Proposition 1. Given a reduced context (O, A, R), then the subdirect decompositions of its concept lattice L correspond bijectively to the families of arrowclosed subcontexts (J j , M j , R ∩ J j × M j ) with O = ∪J j and A = ∪M j .

3 Our contribution

Main Result

From the three previous equivalences found in [START_REF] Ganter | Formal concept analysis -mathematical foundations[END_REF], we deduce the following one:

Corollary 1. Given a lattice L and its reduced context (O, A, R), we have an equivalence between:

1. The set of arrow-closed subcontexts of (O, A, R), 2. The set of compatible subcontexts of (O, A, R), 3. The set of congruence relations of L and their factor lattices.

Corollary 2. Given a lattice L and its reduced context (O, A, R), we have an equivalence between:

The families of arrow-closed subcontexts of (O, A, R) covering O and A, 2. The families of compatible subcontexts of (O, A, R) covering O and A, 3. The families (θ i ) i∈I of congruence relations of L such that ∩ i∈I θ i = ∆ with x∆y ⇐⇒ x = y. 4. The set of subdirect decompositions of L and their factor lattices.

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.

Generation of Subdirectly Irreducible Factors

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 [START_REF] Funk | Algorithms for concept lattice decomposition and their applications[END_REF]. However, all congruence relations are computed and then only pairs of relations are formed to get a decomposition. As a consequence, potentially multiple decompositions are produced with necessarily two factors.

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 [START_REF] Ganter | Formal concept analysis -mathematical foundations[END_REF]: Proposition 2. A lattice L is subdirectly irreducible if and only if its reduced context is one-generated.

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 L 1 × ... × L n where each lattice L i 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 L 1 , . . . , ...L n 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 (J j , M j , R j ) of the subdirectly irreducible factor lattices j,∅,∅),(O,A,R)), the one-generated subcontext span by j; 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).

1 L ← ∅; 2 forall the j ∈ O do 3 Compute (J j , M j , R j ) = Arrow Closure((
4 if L does not contain any subcontext that covers (J j , M j , R j ) then 5 add (J j , M j , R j ) to L 6 if L contains a subcontext covered by (J j , M j , R j ) then 7 delete it from L 8 return L; Algorithm 2: Arrow Closure Input: A subcontext ( J, M , R) of a context (J, M, R) Output: Arrow-closure of ( J, M , R) 1 J c = J; M c = M ; 2 pred J = 0; pred M = 0; 3 while pred M < card(M c ) or pred J < card(J c ) do 4 pred J = card(J c ); 5 pred M = card(M c ); 6 forall the j ∈ J c do 7 add to M c all m ∈ M such that j ↑ m; 8 forall the m ∈ M c do 9 add to J c all j ∈ J such that j ↓ m; 10 Return (J c , M c , R ∩ J c × M c ) j Arrow Closure Con- tained in L Input Output ( J, M , R) Jc Mc 2 (2, ∅, ∅) {2} {j} × 3 (3, ∅, ∅) {3} {c} 5 ( 5
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. The context on the left hand-side of Figure 4 is tricky to understand. For the other ones, we have a simple relation 2 j or 9 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.

Onto Morphism and FCA

A subdirect decomposition of a lattice L into factor lattices L 1 , . . . , L n is relevant since there exists an into morphism from L to the product lattice L 1 × . . . × L n . 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:

(A 1 , B 1 )Θ J,M (A 2 , B 2 ) ⇐⇒ A 1 ∩ J = A 2 ∩ J ⇐⇒ B 1 ∩ M = B 2 ∩ 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 C 1 , . . . , C n 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 c ij and its neighborhood in a subset of factors that contain a given collection of objects or attributes. Each factor L i is a specific view of data.

Experiments

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: Fig. 8. Ugly tagged lattice product 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. 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. 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. 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.

Conclusion and future work

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 [START_REF] Ganter | Formal concept analysis -mathematical foundations[END_REF].

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 [START_REF] Funk | Algorithms for concept lattice decomposition and their applications[END_REF].

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 [START_REF] Valtchev | On the merge of factor canonical bases[END_REF] tackle a similar issue in case of a vertical decomposition of a context into subcontexts.

Since the empirical study in [START_REF] Snelting | Concept lattices in software analysis[END_REF] show that many real-life contexts are subdirectly irreducible, we plan to (i) identify cases in which a context is necessarily irreducible, and (ii) study, compare and combine other decompositions, in particular the Fratini congruence [START_REF] Duquenne | Lattice drawings and morphisms[END_REF], and the reverse doubling convex construction [START_REF] Day | Congruence normality: The characterization of the doubling class of convex sets[END_REF][START_REF] Nation | Alan day's doubling construction[END_REF][START_REF] Geyer | The generalized doubling construction and formal concept analysis[END_REF][START_REF] Bertet | Doubling convec sets in lattices: characterizations and recognition algorithms[END_REF]. Finally, the construction of a lattice from its factor lattices can be done based on the optimization principles behind the relational join operation in databases.

  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:

Fig. 4 .

 4 Fig. 4. Arrow-closed and non-arrow-closed subcontexts of the context in Figure 3

Fig. 5 .

 5 Fig. 5. Iterations of Algorithm 1 for the reduced context in Figure 2

Fig. 6 .

 6 Fig. 6. The three factor lattices of the decompostion with their subcontext as caption

Fig. 7 .

 7 Fig. 7. Factor lattice and congruence

Algorithm 3 :

 3 Into morphismInput: 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);

Fig. 9 .

 9 Fig. 9. Number of lattices per size.

Fig. 10 .

 10 Fig. 10. Proportion of the number of factors in the subdirect decomposition of the contexts according to their density

Fig. 11 .

 11 Fig. 11. Number of cases according to the number of generated factors.


Jean-Franc ¸ois Viaud
email: jviaud@univ-lr.fr

Karell Bertet
email: kbertet@univ-lr.fr

Christophe Demko
email: cdemko@univ-lr.fr

Rokia Missaoui
email: rokia.missaoui@uqo.ca

Jean-Franc ¸ois Viaud

Lattice decompositions through methods using congruence relations

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 management, databases or 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.

. Such approaches become inefficient when contexts are huge. However, the main idea of lattice/context decomposition into smaller ones is still relevant when the classification property of the initial lattice is maintained. Many lattice decompositions have been defined and studied, both from an algebraic

point of view [START_REF] Demel | Fast algorithms for finding a subdirect decomposition and interesting congruences of finite algebras[END_REF][START_REF] Mihók | Unique factorization theorem and formal concept analysis[END_REF] or from an FCA point of view [START_REF] Ganter | Formal concept analysis -mathematical foundations[END_REF][START_REF] Funk | Algorithms for concept lattice decomposition and their applications[END_REF]. We can cite the Unique Factorisation Theorem [START_REF] Mihók | Unique factorization theorem and formal concept analysis[END_REF], the matrix decomposition [START_REF] Belohlavek | Discovery of optimal factors in binary data via a novel method of matrix decomposition[END_REF], the Atlas decomposition [START_REF] Ganter | Formal concept analysis -mathematical foundations[END_REF], the subtensorial decomposition [START_REF] Ganter | Formal concept analysis -mathematical foundations[END_REF], the subdirect decomposition, or the doubling convex construction.

The subdirect decomposition has been widely studied many years ago, in the field of universal algebra [START_REF] Demel | Fast algorithms for finding a subdirect decomposition and interesting congruences of finite algebras[END_REF][START_REF] Freese | Computing congruences efficiently[END_REF][START_REF] Freese | Computing congruence lattices of finite lattices[END_REF][START_REF] Freese | Algorithms in finite, finitely presented and free lattices[END_REF], and even in FCA [START_REF] Wille | Subdirekte produkte und konjunkte summen[END_REF][START_REF] Wille | Subdirekte Produkte vollständiger Verbände[END_REF][START_REF] Wille | Subdirect decomposition of concept lattices[END_REF][START_REF] Wille | Subdirect product construction of concept lattices[END_REF][START_REF] Funk | Algorithms for concept lattice decomposition and their applications[END_REF]. To the best of our knowledge, there is no new development or novel algorithms for subdirect decomposition of contexts. The doubling convex construction has also been widely studied [START_REF] Day | Congruence normality: The characterization of the doubling class of convex sets[END_REF][START_REF] Nation | Alan day's doubling construction[END_REF][START_REF] Geyer | The generalized doubling construction and formal concept analysis[END_REF][START_REF] Bertet | Doubling convec sets in lattices: characterizations and recognition algorithms[END_REF], mainly from a theoretical point of view, in order to characterize lattices that can be obtained by such decomposition.

In this chapter, 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 (L i ) i∈{1,...,n} , denoted by L → L 1 × • • • × L n , is defined by two properties (see important results in [START_REF] Ganter | Formal concept analysis -mathematical foundations[END_REF]): (i) L is a sublattice of the direct product L 1 × • • • × L n , and (ii) each projection of L onto a factor is surjective. The first property establishes that each factor lattice is the concept lattice of an arrow-closed subcontext, i.e. closed according to the arrow relation between objects and attributes. This means that the decomposition can be obtained by computing specific subcontexts. The second property states that there is an equivalence between arrow-closed subcontexts and congruence relations of L, i.e., an equivalence relation whose equivalence classes form a lattice with elements closed by the meet and join operations. This means that the concepts of L can be retrieved from the factor lattices, and the classification property of L is maintained since each equivalence relation forms a partition of the elements. The last result establishes an equivalence between arrow-closed subcontexts and compatible subcontexts, i.e. subcontexts such that each concept corresponds to a concept of the initial lattice. This result gives a way to compute the morphism from L into the direct product, and thus to retrieve the concepts of L from the factor lattices. In this chapter, we deduce from these results strong links between the following notions that have not been used yet together as far as we know:

• Factors of a subdirect decomposition, • Congruence relations, • Arrow-closed subcontexts and • Compatible subcontexts.

As suggested in [START_REF] Ganter | Formal concept analysis -mathematical foundations[END_REF], the contexts of the factors of a particular subdirect decomposition, namely the irreducible subdirect subcontexts, can be obtained by a polynomial processing of each row/object of the initial context. Therefore, the subdirect decomposition of a lattice can be extended to a subdirect decomposition of its reduced context into subdirect and irreducible subcontexts.

In this chapter, we propose a subdirect and polynomial decomposition of a context into subcontexts by extending the subdirect decomposition of a lattice into factors lattices.

After studying the subdirect decomposition, we investigate a new procedure named reverse doubling construction to reduce the size of data. It is based on the previous work of A. Day. The doubling convex procedure was first designed by Day [START_REF] Day | Splitting lattices generate all lattices[END_REF][START_REF] Day | Congruence normality: The characterization of the doubling class of convex sets[END_REF], then generalized [START_REF] Geyer | The generalized doubling construction and formal concept analysis[END_REF] and widely studied [START_REF] Day | Doubling convex sets in lattices and a generalized semidistributivity condition[END_REF][START_REF] Nation | Alan day's doubling construction[END_REF][START_REF] Bertet | Doubling convec sets in lattices: characterizations and recognition algorithms[END_REF]. Intuitively, this construction consists in doubling into a lattice L a convex subset C of nodes of L. In this chapter, we propose a "reverse doubling construction" which consists in removing from a lattice L a doubling convex set until no duplicated convex set exists. Hovewer, our procedure could end with the only conclusion that there is no convex to be removed. When successively applying the reverse doubling construction to a lattice L and a convex set C, and Day's doubling construction, the lattice L is recovered. Our only hypothesis is that lattices are finite. We can deduce, at least, two interesting consequences from this second decomposition:

• Like in the first case, from an "information retrieval" point of view, the search space is thus reduced and hence easier to analyse. • From a "knowledge discovery" point of view, learning which information is doubling and redundant is important.

More generally, as for any reduction technique, we can deduce the following consequences:

• less data to store means smaller storage space.

• less data to exploit means faster computations.

Studies concerning the doubling convex construction can be organized according to the following chronological sequence of events:

• The first one corresponds to the orginal work of Day [START_REF] Day | Splitting lattices generate all lattices[END_REF][START_REF] Day | Congruence normality: The characterization of the doubling class of convex sets[END_REF][START_REF] Day | Doubling convex sets in lattices and a generalized semidistributivity condition[END_REF][START_REF] Nation | Alan day's doubling construction[END_REF], who introduced the procedure. At the very beginning, only intervals were doubled. • Then, further generalizations were developped that lead to the present general doubling convex method [START_REF] Geyer | The generalized doubling construction and formal concept analysis[END_REF]. • In parallel, characterisations of lattices obtained by iterating the doubling convex construction were investigated [START_REF] Day | Splitting lattices generate all lattices[END_REF][START_REF] Day | Congruence normality: The characterization of the doubling class of convex sets[END_REF][START_REF] Day | Doubling convex sets in lattices and a generalized semidistributivity condition[END_REF][START_REF] Nation | Alan day's doubling construction[END_REF][START_REF] Bertet | Doubling convec sets in lattices: characterizations and recognition algorithms[END_REF]. • In this chapter, we define a reverse procedure which removes a convex from a lattice whenever it is possible.

Being able to recover the full lattice from the smaller one and a convex inside, means that all the information is contained in the small lattice. Thus we only need to consider the sub-context that defines the small lattice. In other words, only a part of the data is relevant. Consequently, one need only to access or even keep a smaller part of the data. This is obviously an interesting way to manage big data.

These two decompositions, namely the sub-direct decomposition and the reverse doubling construction, lead 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 FCA has made progress in lattice construction and exploration, and hence existing solutions can be adapted and enriched to only target useful patterns.

This chapter is organized as follows. The next section gives the background needed to introduce the two decompositions. Then, the next two sections present the two decompositions. We conclude in the last section with some perspectives.

Structural framework

Throughout this paper all sets (and thus lattices) are considered to be finite.

Lattices and Formal Concept Analysis

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). A (formal) concept represents a maximal objects-attributes correspondence by a pair (X,Y ) such that X = Y and Y = 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:

Concept or Galois Lattice

(X 1 ,Y 1 ) ≤ (X 2 ,Y 2 ) ⇐⇒ X 1 ⊆ X 2 ⇐⇒ Y 2 ⊆ Y 1
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 J L . Meet-irreducible elements are defined dually and their set is M L . 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 2.1.2, join-irreducible nodes are labelled with a number and meet-irreducible nodes are labelled with a letter.

Fundamental Bijection

A fundamental result [START_REF] Barbut | L'ordre et la classification. Algèbre et combinatoire[END_REF] establishes that any lattice (L, ≤) is isomorphic to the concept lattice of the context (J L , M L , ≤), where J L and M L are the join and meet irreducible concepts of L, respectively. Moreover, this context is a reduced one.

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.

Table 2.1.3 shows the reduced context of the lattice in Figure 2.1.2. When needed, operators • introduced in subsection 2.1.2 will be written • L to stress the fact that they are used with the reduced context of the lattice L.

Table 1 The reduced context of the lattice in Figure 2.1.2 b c d f g j 2 x x x x x 3 x x x x 5 x x x 6 x x x 9 x x

Compatible and Arrow-closed Subcontexts

This section is dedicated to the equivalence between compatible and arrow-closed subcontexts.

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 (J L , M L , ≤) of a lattice (L, ≤). Arrow relations [START_REF] Crawley | Algebraic theory of lattices[END_REF][START_REF] Grätzer | General lattice theory[END_REF] form a partition of the relation ≤ (defined by not having x ≤ y) by considering the immediate predecessor j -of a join-irreducible j, and the unique immediate successor m + of a meet-irreducible m:

• j m if j ≤ m, j ≤ m + and j -≤ m. • j ↑ m if j ≤ m, j ≤ m + and j -≤ m. • j ↓ m if j ≤ m, j ≤ m + and j -≤ m. • j • m if j ≤ m, j ≤ m + and j -≤ m.
In Figure 2

b c d f g j 2 × × × × × 3 × × ↓ × × 5 × × × • 6 × × × ↓ • 9 × • × • • 2.2.3 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 2 is an arrow-closed subcontext of the reduced context of Table 2.2.2 whereas the second one is not, due to the downarrow 6 ↓ g. 2

.2.2 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 chapter, whose proof can be found in [START_REF] Ganter | Formal concept analysis -mathematical foundations[END_REF]:

Theorem 1. Let (J, M, R ∩ J × M) be a subcontext of (O, A, R).
The following propositions are equivalent:

• The subcontext (J, M, R ∩ J × M) is a compatible one. • The subcontext (J, M, R ∩ J × M) is an arrow-closed one.

Congruence Relations and Factor Lattices

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:

x R = {y ∈ E | xRy}
The set of equivalence classes, called the quotient set E/R, is:

E/R = {x R | x ∈ E} 2.

Factor lattice

A congruence relation Θ on a lattice L is an equivalence relation such that:

x 1 Θ y 1 and x 2 Θ y 2 =⇒ x 1 ∧ x 2 Θ y 1 ∧ y 2 and x 1 ∨ x 2 Θ y 1 ∨ y 2
The quotient L/Θ verifies the following statement:

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 [START_REF] Ganter | Formal concept analysis -mathematical foundations[END_REF]: Theorem 3. Given a lattice L, the set of congruence relations on L corresponds bijectively with the set of arrow-closed subcontexts of the reduced context of L.

Congruence relations will be computed with this theorem. However, other algorithms exist [START_REF] Freese | Computing congruence lattices of finite lattices[END_REF][START_REF] Freese | Algorithms in finite, finitely presented and free lattices[END_REF].

Subdirect decompositions

In this section, we introduce the equivalence between subdirect decompositions and sets of arrow-closed subcontexts.

Subdirect product Definition

1. A subdirect product is a sublattice of a direct product L 1 × • • • × L n of lattices L i , i ∈ {1, .
. . , n} such that each projection onto a factor is surjective. The lattices L i , 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 → L 1 × • • • × L n L i

The third equivalence theorem

The third and most important equivalence whose proof can be found in [START_REF] Ganter | Formal concept analysis -mathematical foundations[END_REF], makes a connection with sets of arrows-closed subcontexts when they cover the initial context:

Proposition 1. Given a reduced context (O, A, R), then the subdirect decompositions of its concept lattice L correspond bijectively to the families of arrow-closed subcontexts (J j , M j , R ∩ J j × M j ) with O = ∪J j and A = ∪M j .

The doubling convex construction

The second decomposition, presented in this chapter is based on Alan Day's doubling convex construction [START_REF] Day | Splitting lattices generate all lattices[END_REF][START_REF] Day | Congruence normality: The characterization of the doubling class of convex sets[END_REF][START_REF] Day | Doubling convex sets in lattices and a generalized semidistributivity condition[END_REF][START_REF] Nation | Alan day's doubling construction[END_REF]. First recall that a subset C ⊂ L C of a lattice L C is convex if it satisfies the following condition: for all x, y ∈ C such that x ≤ y, if z ∈ L C satisfies x ≤ z ≤ y then z ∈ C. Roughly, a convex set contains all its intervals. Now we can give the doubling convex construction of Day. Let C ⊂ L C be a convex set of a lattice L C , let L C [C] = L C \C ∪ (C × {0, 1}). Define the following order on L C [C]:

• x ≤ y if x ≤ y in L C • (x, i) ≤ y if x ≤ y in L C • x ≤ (y, j) if x ≤ y in L C • (x, i) ≤ (y, j) if x ≤ y in L C and i ≤ j.
With this order L C [C] is a lattice. For instance consider the lattice L C of Figure 2.5. A convex set C is identified with red nodes. After applying Day's construction, the lattice of Figure 2.5 is obtained. The two occurrences of the convex set are identified with green and pink nodes.

Our construction is based on the two following theorems proved by W. Geyer [START_REF] Geyer | The generalized doubling construction and formal concept analysis[END_REF].

( * ) R ∩ ((O\J) × (A\M)) = / 0
Later on, the previous condition ( * ) will be referred as the Geyer's Condition. Now we are searching for an arrow-closed sub-context that satisfies the Geyer's Condition.

Using theorem 3, it is equivalent to search for an arrow-closed sub-context or a congruence relation. Now recall that it is possible to give a lattice structure to the set of congruence relations in the following manner. First, the binary relations can be ordered by the inclusion. Then the set of congruence relations can be ordered that way. Moreover, the intersection of two congrence relations is still a congruence relation; thus we get the meet operation. As usual, the join operation is not so easy. However, given a set of congruence relations, it is sufficient to consider the smallest congruence relations containing all of them.

With this lattice structure on the congruence relations, we can state the following result of Day [START_REF] Day | Congruence normality: The characterization of the doubling class of convex sets[END_REF]: Theorem 5. Let L be a congruence normal lattice and Θ a congruence relation which is an atom, i.e. a successor of the bottom element. Then, there exists a convex set C such that L is isomorphic to L/Θ [C].

Notice that congruence normality has not been defined because it will not be used in this chapter. Notice also that Day is more explicit about the convex C, but we will give a new construction of it.

3 Subdirect decomposition into subdirectly irreducible factors

Main Result

From the three previous equivalences found in [START_REF] Ganter | Formal concept analysis -mathematical foundations[END_REF], we deduce the following one: Corollary 1. Given a lattice L and its reduced context (O, A, R), we have an equivalence between:

1. The set of arrow-closed subcontexts of (O, A, R), 2. The set of compatible subcontexts of (O, A, R), 3. The set of congruence relations of L and their factor lattices.

Corollary 2. Given a lattice L and its reduced context (O, A, R), we have an equivalence between:

1. The families of arrow-closed subcontexts of (O, A, R) covering O and A, 2. The families of compatible subcontexts of (O, A, R) covering O and A, 3. The families (θ i ) i∈I of congruence relations of L such that ∩ i∈I θ i = ∆ with x∆ y ⇐⇒ x = y. 4. The set of subdirect decompositions of L and their factor lattices.

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.

Generation of Subdirectly Irreducible Factors

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 [START_REF] Funk | Algorithms for concept lattice decomposition and their applications[END_REF]. However, all congruence relations are computed and then only pairs of relations are formed to get a decomposition. As a consequence, potentially multiple decompositions are produced with necessarily two factors.

In this chpater, 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 contains L itself as a factor. A nice characterization of subdirectly irreducible lattices can be found in [START_REF] Ganter | Formal concept analysis -mathematical foundations[END_REF]: Proposition 2. A lattice L is subdirectly irreducible if and only if its reduced context is one-generated.

A reduced context (O, A, R) is one-generated if it can be obtained by arrowclosing 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 L 1 × ... × L n where each lattice L i 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 L 1 , . . . , ...L n of a subdirectly irreducible decomposition, with a reduced context (O, A, R) as input. The one-generated 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 (J j , M j , R j ) of the subdirectly irreducible factor lattices

1 L ← / 0; 2 forall the j ∈ O do 3 Compute (J j , M j , R j ) = Arrow Closure(( j, / 0, / 0), (O, A, R
)), the one-generated subcontext span by j; 4 if L does not contain any subcontext that covers (J j , M j , R j ) then 5 add (J j , M j , R j ) to L 6 if L contains a subcontext covered by (J j , M j , R j ) then Consider the reduced context in Figure 2.1.3. Each iteration of Algorithm 1 is described by Figure 3 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 5). The context on the middle of Figure 2 is tricky to understand. For the other ones, we have a simple relation 2 j or 9 b, which means that, for instance, 2 and j are some kind of complement or converse.

Input: A subcontext ( J, M, R) of a context (J, M, R) Output: Arrow-closure of ( J, M, R) 1 J c = J; M c = M; 2 pred J = 0; pred M = 0; 3 while pred M < card(M c ) or pred J < card(J c ) do 4 pred J = card(J c ); 5 pred M = card(M c ); 6 forall the j ∈ J c do 7 add to M c all m ∈ M such that j ↑ m; 8 forall the m ∈ M c do 9 add to J c all j ∈ J such that j ↓ m; 10 Return (J c , M c , R ∩ J c × M c )
Figure 10 shows a factor lattice and its corresponding congruence.

Onto Morphism and FCA

A subdirect decomposition of a lattice L into factor lattices L 1 , . . . , L n is relevant since there exists an into morphism from L to the product lattice L 1 × . . . × L n . This Proposition 4. Let (J, M, R ∩ J × M) be a compatible subcontext, then the relation Θ J,M defined by:

(A 1 , B 1 )Θ J,M (A 2 , B 2 ) ⇐⇒ A 1 ∩ J = A 2 ∩ J ⇐⇒ B 1 ∩ M = B 2 ∩ 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 4. 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 C 1 , . . . ,C n 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 c i j and its neighborhood in a subset of factors that contain a given collection of objects or attributes. Each factor L i is a specific view of data.

because we do not use the congruence normality hypothesis. Hovewer, the first step of our construction is to compute atoms of the lattice of congruence relations. From Theorem 3, we know that these congruence relations correspond to arrow-closed sub-contexts. Then from Theorem 4 of Geyer, we only need to check if these arrowclosed sub-contexts, that are just good candidates, satisfy the Geyer's condition. If none of these sub-contexts is valid, the decomposition is not possible. Otherwise, each one of these sub-contexts generates a lattice L C that is appropriate. The last step consists in identifying the convex set C in L C .

To illustrate the reverse doubling convex construction, we will use the lattice given in Figure 4.1 and its reduced Table 4.1, already filled with arrows.

Fig. 8 The lattice used to illustrate the reverse doubling convex decomposition. Nodes in green and pink correspond to the two occurrences of the doubled convex.

The lattice of Congruence Relations

A reduced context (O, A, R) of a lattice L is supposed to be given.

↑ × × • • × × 10 × × × × ↓ ↓ × × 14 ↑ × ↓ × • • ↓ ↓ 19 × × × ↓ × × × × 33 × ↑ • • × × ↓ ↓ 15 × ↑ × ↑ • × × 28 × ↑ × ↑ • × × 7 ↑ ↑ × × • • • × 26 ↑ ↑ × × • • • × 13 × ↑ × • × × × ×
In Subsection 2.3, we introduced congruence relations. As a particular kind of binary relation, the set of congruence relations inherits a structure of lattice: it is a sublattice of the lattice of binary relations which is ordered by inclusion. Using Theorem 3, this lattice is also the lattice of arrow-closed sub-contexts. As explained previously, we aim at finding the atoms of that lattice. To that end, we introduce a new context, namely the context of arrow-closed subcontexts, which is defined and computed as follows. We first compute one-generated arrow-closed sub-contexts. Definition 2. A context (J, M, R) is one-generated if it can be obtained by arrowclosing a context with only one j ∈ J. Thus (J, M, R) is the smallest arrow-closed subcontext containing j ∈ J.

The set of such one-generated sub-contexts contains all join-irreducible arrowclosed sub-contexts of the lattice of arrow-closed sub-contexts. Thus, the set of onegenerated sub-contexts generates the lattice of arrow-closed sub-contexts. The onegenerated sub-contexts are stored as observations of a new context in the following way: an arrow-closed is characterized by its set of attributes, since it is closed. Thus the newly generated context has the same set of attributes, namely A. Since, onegenerated sub-contexts are computed by closing one j ∈ O, they can be identified with that j. So the set of observations of the newly generated context is O. At last, there is a cross in the new context between j and a if and only if the arrow-closed sub-context generated by j contains the attributes a.

From this context, we can deduce the lattice of arrow-closed sub-contexts and in particular its atoms.

From the lattice of Figure 4.1, we compute the Table 4.2 of one-generated arrowclosed sub-contexts and then we get the lattice of congruence relations given in Figure 4.2. Notice that Table 4.2 has been reduced after computation. In this particular case, there are two atoms.

Using only one of these atoms, namely the one containing observation 25, we get the arrow-closed subcontext of Table 4.4, which satisfies Geyer's condition. Then, its concept lattice, which is also the factor lattice of the selected congruence relation, can be compute, and visualize on First remark that using theorem 4 which gives a necessary and sufficient condition, we already know that L is obtained by the doubling construction from L C . Thus, each concept of L C gives rise to one concept in L if and only if it is not in C and two concepts in L if and only if it is in C.

Let us be more precise about these two concepts, and first let us recall some notations: (O, A, R) is the reduced context of the big lattice L. We consider (J, M, R∩ J × M) a atom in the lattice of arrow-closed sub-contexts whi ch satifies the Geyer's condition. From this context, we can deduce L C the lattice from which a convex has been removed. Let c be a concept of L C . Since (J, M, R ∩ J × M) is a compatible sub-context, using Theorem 1, c can be written as

c = (H ∩ J, N ∩ M) with (H, N) a concept of L. Since c is a concept, we have (H ∩ J) = N ∩ M and (N ∩ M) = H ∩ J.
Recall, from the end of Subsection 2.1.3, that these operations are written • L in the reduced context (O, A, R) of L; thus we also have H L = N and N L = H. Now, we can conclude that, if c = (H ∩ J, N ∩ M) is not in the convex, it comes from the unique concept of L, namely (H, N) and thus we must have

((H ∩ J) LL , (H ∩ J) L ) = (H, N) = ((N ∩ M) L , (N ∩ M) LL ). In the other case, we have ((H ∩ J) LL , (H ∩ J) L ) = ((N ∩ M) L , (N ∩ M) LL ).
From this point, we can state a simpler condition for a concept to be in the convex set:

Proposition 5. A concept c = (H ∩ J, N ∩ M) is in the convex if and only if (H ∩ J) L ⊆ (N ∩ M) or (N ∩ M) L ⊆ (H ∩ J)
Proof. We have previously seen that if c is in the convex then ((H ∩ J) LL , (H ∩ J) L ) = (H, N) = ((N ∩ M) L , (N ∩ M) LL ). So both inclusions are true and actually are equalities.

Suppose, reciprocally, that we have the first one (H ∩ J) L ⊂ (N ∩ M). We obtain the same result dually in the second case. First we prove that the inclusion is an equality. Indeed, since

(J, M, R ∩ J × M) is a subcontext of (O, A, R), we have (H ∩ J) ⊂ (H ∩ J) L . However (H ∩ J) = (N ∩ M), so (N ∩ M) ⊂ (H ∩ J) L and dually (H ∩ J) ⊂ (N ∩ M) L . Therefore, we deduce that (H ∩ J) L = (N ∩ M), and then (N ∩ M) L = (H ∩ J) LL . Moreover, (H ∩ J) ⊂ (N ∩ M) L =⇒ (N ∩ M) LL ⊂ (H ∩ J) L , and with (N ∩ M) = (H ∩ J) L , we deduce that (N ∩ M) = (N ∩ M) LL , since (N ∩ M) ⊂ (N ∩ M) LL . Now from (H ∩ J) L = (N ∩ M) = (N ∩ M) LL and (N ∩ M) L = (H ∩ J) LL , we get ((H ∩ J) L , (H ∩ J) LL ) = ((N ∩ M) LL , (N ∩ M) L ).
This means that a concept ((H ∩ J), (N ∩ M)) in the small lattice L C that satisfies the condition (H ∩ J) L ⊂ (N ∩M) or (N ∩M) L ⊂ (H ∩J) comes from a unique concept in the lattice L, namely the concept ((H ∩ J) LL , (H ∩ J) L ) = ((N ∩ M) L , (N ∩ M) LL ) = (H, N).

Conversely, if ((H ∩J), (N ∩M)) does not satisfy the previous condition, it comes from two concepts ((H ∩ J) LL , (H ∩ J) L ) = ((N ∩ M) L , (N ∩ M) LL ) in L. Thus to get L from L C , one needs to double these concepts and then these concepts are exactly the ones of the convex.

In Figure 4.4, nodes of the convex C are in red, and when the doubling construction is applied on that lattice, with this convex set, the lattice from Figure 4.4 is obtained. This lattice is obtained from the reduced context given in the table 4.4, which is one of the two atomes of the lattice 4.2.

All computations were done using the Galactic project available at : http://thegalactic.github.io/ Lattices were drawn with ConExp available at : http://conexp.sourceforge.net/ Fig. 11 The factor lattice obtained by the reverse doubling decomposition.

Table 6 The reduced context of the factor lattice given in

Conclusion and future work

In this chapter, we have presented two decompositions of lattices based on congruence relations. In the fisrt section, different points of view and constructions about these relations were given. Then we presented a particular case of the widely studied subdirect decomposition. To further investigate the subdirect decomposition, it would be interesting to conduct large-scale experiments on real world data to understand the semantics behind the generated irreducible contexts. In particular, attributes covered by several factors interfere in different views of data whose semantic must be interesting to understand. Moreover families of arrow-closed subcontext covering the initial context could be used as universal index. It would be useful to allow the user to interactively select a few factors of the decomposition by mixing o ur approach with the one in [START_REF] Funk | Algorithms for concept lattice decomposition and their applications[END_REF]. Since the empirical study in [START_REF] Snelting | Concept lattices in software analysis[END_REF] show that many real-life contexts are subdirectly irreducible, we plan to identify cases in which a context is necessarily irreducible.

In the previous section, a new decomposition, based on Day's construction, was given which uses again congruence relations. Day's doubling construction has been widely studied [START_REF] Day | Congruence normality: The characterization of the doubling class of convex sets[END_REF][START_REF] Nation | Alan day's doubling construction[END_REF][START_REF] Geyer | The generalized doubling construction and formal concept analysis[END_REF][START_REF] Bertet | Doubling convec sets in lattices: characterizations and recognition algorithms[END_REF], but to our knowledge, this decomposition has never been done.

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 [START_REF] Valtchev | On the merge of factor canonical bases[END_REF] tackle a similar issue in case of a vertical decomposition of contexts into subcontexts.

To go further, we plan to study, compare and combine other decompositions, in particular the Fratini congruence [START_REF] Duquenne | Lattice drawings and morphisms[END_REF] which exploits again a congruence relation and atlas decomposition [START_REF] Ganter | Formal concept analysis -mathematical foundations[END_REF] which uses different tools.

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 X = {m ∈ A, j R m ∀ j ∈ X} and dually, • for each subset Y ⊂ A, we define Y = { j ∈ O, j R m ∀m ∈ Y }.

Fig. 1 A

 1 Fig. 1 A lattice with its irreducible nodes

  .2.2, the reduced context of Figure2.1.3 is enriched with the four relations , ↑, ↓, and • in the empty cells that both correspond to the case where j ≤ m:As an illustration, let j = 5 and m = f be join-irreducible and meet-irreducible nodes respectively (see Figure2.1.2). Then, j -= 2 and m + = c. The relation 5 f holds since 5 ≤ f , 5 ≤ c and 2 ≤ f .

Fig. 2

 2 Fig. 2 Arrow-closed and non-arrow-closed subcontexts of the context inTable 2.2.2 c d f g 3 x x 5 x x 6 x x

Fig. 3 A

 3 Fig. 3 A lattice L C with nodes of a convex set C in red.

Fig. 4

 4 Fig. 4 The lattice of Figure 2.5 with the convex set doubled. Nodes of each convex are coloured in green and pink.

7 delete

 7

Fig. 5

 5 Fig.5The three factor lattices of the decompostion with their subcontext as caption

Fig. 6

 6 Fig. 6 Factor lattice and congruence

Figure 4 . 4 .

 44 The two atoms identified in Figure4.2 satisfy Geyer's condition. So the lattice given in Figure4.1 has two decompositions.4.4 Finding the convexGiven a lattice L C satisfying the previous conditions of subsection 4.3, the last step is to identify in L C nodes of a convex set C such that L = L C [C].

Fig. 10

 10 Fig.10The initial lattice. Nodes in green and pink correspond to the two occurrences of the doubled convex.

Figure 4

 4

Table 2

 2 Reduced context of Table 2.1.3 filled with arrow relations

Table 3

 3 Iterations of Algorithm 1 for the reduced context in Table 2.1.3

	j	Arrow Closure		Contained in L
		Input	Output
		( J, M, R)	J c	M c
	2	(2, / 0, / 0)	{2}	{ j}	×
	3	(3, / 0, / 0)	{3}	{c}
	5	(5, / 0, / 0) {3, 5, 6} {c, d, f , g} ×
	6	(6, / 0, / 0)	{6}	{d}
	9	(9, / 0, / 0)	{9}	{b}	×

Table 4

 4 The reduced context of the lattice given in Figure4.1

	2 4 8 12 14 25 20 27 16
	9

Algorithm 3: Into morphism

Input: Initial lattice L; Subcontexts (J j , M j , R j ); Product lattice P = L 1 × . . . × L n Output: Product lattice P with nodes coming from L marked.

Mark, in P, the product node Π j (A ∩ J j , B ∩ M j ); Fig. 7 Lattice product in which nodes of the initial lattice appear in red [START_REF] Crawley | Algebraic theory of lattices[END_REF]

Reverse doubling convex

In this section, we describe the reverse doubling construction which itself uses congruence relations.

Given a lattice L, we recall that we are looking for a lattice

Main steps

Before giving into details about this decomposition, let us give the main steps of our construction. Given a finite lattice L, we are searching a lattice L C and a con-

From Theorem 5, we know that good candidates can be obtained from factor lattices, spanned by a congruence relation which is an atom. It is important to note that we only get good candidates Table 5 The reduced context computed to get the lattice of congruence relations (

The factor lattice

We are now given a list of arrow-closed sub-contexts, which correspond to atom congruence relations.

The second step is to remove from this list the following contexts:

• The empty context. In the particular case where the initial lattice has only two congruence relations, there is only one atom, namely the bottom element. This case is excluded since it gives rise to a trivial decomposition. • Any context that does not satisfy Geyer's Condition.

After this removal process, our list could be empty. Since the Geyer's condition is necessary and sufficient, we can conclude that the original lattice can not be processed through the reverse doubling construction.

On the opposite side, any remaining context generates a lattice L C such that there exists a convex set C so that the initial lattice L satisfies L = L C [C].


Jean-Franc ¸ois Viaud

Karell Bertet
email: kbertet@univ-lr.fr

Christophe Demko
email: cdemko@univ-lr.fr

Rokia Missaoui
email: rokia.missaoui@uqo.ca

The Reverse Doubling Construction

Keywords: Concept lattice, congruence relation, factor lattice, arrow relation, arrow closed subcontext, compatible subcontext, doubling convex

It is well known inside the Formal Concept Analysis (FCA) community that a concept lattice could have an exponential size in the data. Hence, the size of concept lattices is a critical issue in the presence of large real-life data sets. In this paper, we propose to investigate factor lattices as a tool to get meaningful parts of the whole lattice. These factor lattices have been widely studied from the early theory of lattices to more recent work in the FCA field. This paper contains two parts. The first one gives background about lattice theory and formal concept analysis, and mainly compatible sub-contexts, arrow-closed sub-contexts and congruence relations. The second part presents a new decomposition called "reverse doubling construction" that exploits the above three notions used for the doubling convex construction investigated by Day. Theoretical results and their proofs are given as well as an illustrative example.

INTRODUCTION

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 expressed by a formal 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 management, databases or 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 in an on-line and interactive way [START_REF] Ferré | Reconciling expressivity and usability in information access from file systems to the semantic web[END_REF][START_REF] Visani | Navigala: an Original Symbol Classifier Based on Navigation through a Galois Lattice[END_REF] or better display lattices using nested line diagrams [START_REF] Ganter | Formal concept analysismathematical foundations[END_REF]. Such approaches become inefficient when contexts are huge. However, the main idea of lattice/context decomposition into smaller ones is still relevant when the classification property of the initial lattice is maintained. Many lattice decompositions have been defined and studied, either from an algebraic point of view [START_REF] Demel | Fast algorithms for finding a subdirect decomposition and interesting congruences of finite algebras[END_REF][START_REF] Mihók | Unique factorization theorem and formal concept analysis[END_REF] or from an FCA point of view [START_REF] Ganter | Formal concept analysismathematical foundations[END_REF][START_REF] Funk | Algorithms for concept lattice decomposition and their applications[END_REF]. We can cite the Unique Factorisation Theorem [START_REF] Mihók | Unique factorization theorem and formal concept analysis[END_REF], the matrix decomposition [START_REF] Belohlavek | Discovery of optimal factors in binary data via a novel method of matrix decomposition[END_REF], the Atlas decomposition [START_REF] Ganter | Formal concept analysismathematical foundations[END_REF], the subtensorial decomposition [START_REF] Ganter | Formal concept analysismathematical foundations[END_REF], the subdirect decomposition [START_REF] Demel | Fast algorithms for finding a subdirect decomposition and interesting congruences of finite algebras[END_REF][START_REF] Freese | Computing congruences efficiently[END_REF][START_REF] Freese | Computing congruence lattices of finite lattices[END_REF][START_REF] Freese | Algorithms in finite, finitely presented and free lattices[END_REF][START_REF] Wille | Subdirekte produkte und konjunkte summen[END_REF][START_REF] Wille | Subdirekte Produkte vollständiger Verbände[END_REF][START_REF] Wille | Subdirect decomposition of concept lattices[END_REF][START_REF] Wille | Subdirect product construction of concept lattices[END_REF][START_REF] Funk | Algorithms for concept lattice decomposition and their applications[END_REF], or the doubling convex construction. The doubling convex construction has also been widely studied [START_REF] Day | Congruence normality: The characterization of the doubling class of convex sets[END_REF][START_REF] Nation | Alan day's doubling construction[END_REF][START_REF] Geyer | The generalized doubling construction and formal concept analysis[END_REF][START_REF] Bertet | Doubling convec sets in lattices: characterizations and recognition algorithms[END_REF], mainly from a theoretical point of view in order to characterize lattices that can be obtained by such decomposition. In this paper, we investigate a new method named reverse doubling construction to reduce the size of data. In other words, we propose a new method to construct a smaller lattice from a given one. It is based on the previous work of Day about the doubling convex construction [START_REF] Day | Splitting lattices generate all lattices[END_REF][START_REF] Day | Congruence normality: The characterization of the doubling class of convex sets[END_REF]. Such a method has then be generalized [START_REF] Geyer | The generalized doubling construction and formal concept analysis[END_REF] and further widely studied [START_REF] Day | Doubling convex sets in lattices and a generalized semidistributivity condition[END_REF][START_REF] Nation | Alan day's doubling construction[END_REF][START_REF] Bertet | Doubling convec sets in lattices: characterizations and recognition algorithms[END_REF]. Intuitively, this construction consists in doubling into a lattice L a convex subset C of nodes of L. In this paper, we propose a "reverse doubling construction" which aims at removing from a lattice L a doubled convex set until no duplicated convex set exists. However, there may be no convex to remove and hence no changes in the initial lattice structure. When the reverse doubling construction successively applied to an assumed finite lattice L and a convex set C, and following the Day's doubling construction, the initial lattice L is recovered without any loss of information.

Studies about the doubling convex construction can be organized according to the following chronological sequence of events:

• The first one corresponds to the original work of Day [START_REF] Day | Splitting lattices generate all lattices[END_REF][START_REF] Day | Congruence normality: The characterization of the doubling class of convex sets[END_REF][START_REF] Day | Doubling convex sets in lattices and a generalized semidistributivity condition[END_REF][START_REF] Nation | Alan day's doubling construction[END_REF], who introduced the construction. At the very beginning, only intervals were doubled.

• Further generalizations were developed that lead to the general doubling convex method [START_REF] Geyer | The generalized doubling construction and formal concept analysis[END_REF].

• In parallel, characterizations of lattices obtained by iterating the doubling convex construction were investigated [START_REF] Day | Splitting lattices generate all lattices[END_REF][START_REF] Day | Congruence normality: The characterization of the doubling class of convex sets[END_REF][START_REF] Day | Doubling convex sets in lattices and a generalized semidistributivity condition[END_REF][START_REF] Nation | Alan day's doubling construction[END_REF][START_REF] Bertet | Doubling convec sets in lattices: characterizations and recognition algorithms[END_REF].

• In this paper, we define a reverse construction which removes a convex from a lattice whenever it is possible.

Being able to recover the full lattice from the smaller one and a convex inside, means that all the information is contained in the small lattice. Thus we only need to consider the sub-context that defines the small lattice. In other words, only a part of the data is relevant. Consequently, one needs only to access or even keep a smaller part of the data. This is obviously an interesting way to manage big data that are nowadays ubiquitous in many real-life applications.

This paper is organized as follows. The next section as well as the appendix give the background needed to understand the rest of the article. Then, Section 3 presents the decomposition method while an example serves as an illustration in Section 4. Conclusion and future work are given in Section 5.

STRUCTURAL FRAMEWORK

Throughout this paper all sets (and thus lattices) are considered to be finite.

This work takes place in the framework of Formal Concept Analysis (FCA) [START_REF] Ganter | Formal concept analysismathematical foundations[END_REF] which deals with formal contexts, i.e. data represented as binary matrices. From a formal context, a concept lattice is deduced. An example of a formal Figure 1: A lattice with its irreducible nodes context is given in Table 1 and its associated concept lattice is given in Figure 1.

Lattices and Formal Concept Analysis

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 X = {m ∈ A, j R m ∀ j ∈ X} and dually, • for each subset Y ⊂ A, we define Y = { j ∈ O, j R m ∀m ∈ Y }.
Table 1 is an example of a formal context where X in a cell ( j, m) means that object j has the attribute m.

A(formal) concept represents a maximal objectsattributes correspondence by a pair (X,Y ) such that X = Y and Y = 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:

(X 1 ,Y 1 ) ≤ (X 2 ,Y 2 ) ⇐⇒ X 1 ⊆ X 2 ⇐⇒ Y 2 ⊆ Y 1 (1)
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). 1 b c d f g j 2 x x x x x 3 x x x x 5 x x x 6 x x x 9

x x 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 J L . Meetirreducible elements are defined dually and their set is M L . 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 4, nodes with with a number above are meet-irreducible while nodes with a number below are join-irreducible.

Fundamental Bijection

A fundamental result (Barbut and Monjardet, 1970) establishes that any lattice (L, ≤) is isomorphic to the concept lattice of the context (J L , M L , ≤), where J L and M L are the join and meet irreducible concepts of L, respectively. Moreover, this context is a reduced one.

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.

Table 1 in the appendix shows the reduced context of the lattice in Figure 1.

When needed, operators • introduced in subsection 2.1.2 will be written • L to stress the fact that they are used with the reduced context of the lattice L.

A sub-context consists of a binary relation between a subset of objects and a subset of attributes in the initial data. In this paper we consider particular sub-contexts for which three different equivalent definitions can be given. More details can be found in [START_REF] Viaud | Subdirect decomposition of contexts into subdirectly irreducible factors[END_REF].

• Compatible sub-contexts,

• Arrow-closed sub-contexts,

• Sub-contexts defining factor lattices and congruence relations.

In conjunction with Day's doubling construction [START_REF] Day | Splitting lattices generate all lattices[END_REF][START_REF] Day | Congruence normality: The characterization of the doubling class of convex sets[END_REF], these particular sub-contexts enable us to introduce a new construction, namely the reverse doubling construction.

REVERSE DOUBLING CONVEX

In this section, we describe the reverse doubling construction which itself uses congruence relations. Given a lattice L, we recall that we are looking for a lattice

L C containing a convex C such that L = L C [C].

Main Steps

Before giving details about this decomposition, let us provide the main steps of our construction.

Main Steps of the proof

Given a finite lattice L, we are searching a lattice L C and a convex set

C ⊂ L C such that L is isomorphic to L C [C].
1. We first use following result of Day [START_REF] Day | Congruence normality: The characterization of the doubling class of convex sets[END_REF]:

Theorem 1. Let L be a congruence normal lattice and Θ a congruence relation which is an atom, i.e. a successor of the bottom element. Then, there exists a convex set C such that L is isomorphic to

L/Θ[C].
From this theorem 1, we know that good candidates can be obtained from factor lattices, spanned by a congruence relation which is an atom.

It is important to note that we only get good candidates because we do not use the congruence normality hypothesis.

2. We next use the following equivalence whose proof can be found in [START_REF] Ganter | Formal concept analysismathematical foundations[END_REF]:

Theorem 2. Given a lattice L, the set of congruence relations on L corresponds bijectively with the set of arrow-closed subcontexts of the reduced context of L.

From this Theorem 2, we know that these congruence relations correspond to arrow-closed subcontexts. 3. Then the following theorem 3 of Geyer is used: We only need to check if the arrow-closed subcontexts that are just good candidates satisfy the Geyer's condition 2. 4. If none of these sub-contexts is valid, the decomposition is not possible. Otherwise, each one of these sub-contexts generates a lattice L C that is appropriate.

Theorem 3. Let L = L C [C]

Main Steps of the construction

The principal steps are as follows:

1. The first step of our construction is to compute atoms of the lattice of congruence relations. 2. Then we select the arrow-closed sub-contexts satisfying the Geyer's condition. Each one of these sub-contexts generates a lattice L C that is appropriate. 3. The last step consists in identifying the convex set C in L C .

The Lattice of Congruence Relations

A reduced context (O, A, R) of a lattice L is supposed to be given.

Recall that congruence relations are equivalence relations compatible with the lattice structure. As a particular kind of binary relation, the set of congruence relations inherits a structure of lattice: it is a sublattice of the lattice of binary relations which is ordered by inclusion. Using Theorem 2, this lattice is also the lattice of arrow-closed sub-contexts. As explained previously, we aim at finding the atoms of that lattice. To that end, we introduce a new context, namely the context of arrow-closed subcontexts, which is defined and computed as follows. We first compute one-generated arrow-closed sub-contexts. Definition 1. A context (J, M, R) is one-generated if it can be obtained by arrow-closing a context with only one j ∈ J. Thus (J, M, R) is the smallest arrow-closed subcontext containing j ∈ J.

The set of such one-generated sub-contexts contains all join-irreducible arrow-closed sub-contexts of the lattice of arrow-closed sub-contexts. Thus, the set of one-generated sub-contexts generates the lattice of arrow-closed sub-contexts. The one-generated subcontexts are stored as observations of a new context in the following way: an arrow-closed is characterized by its set of attributes, since it is closed. Thus the newly generated context has the same set of attributes, namely A. Since one-generated sub-contexts are computed by closing one j ∈ O, they can be identified with that j. The set of observations of the newly generated context is still O. Finally, there is a cross in the new context between object j and attribute a if and only if the arrow-closed sub-context generated by j contains the attribute a.

From this context, we can deduce the lattice of arrow-closed sub-contexts and in particular its atoms.

The Factor Lattice

We are now given a list of arrow-closed sub-contexts, which correspond to atom congruence relations.

The second step is to remove from this list the following contexts:

• The empty context. In the particular case where the initial lattice has only two congruence relations, there is only one atom, namely the bottom element. This case is excluded since it gives rise to a trivial decomposition.

• Any context that does not satisfy Geyer's Condition.

After this removal process, our list could be empty. Since the Geyer's condition is necessary and sufficient, we can conclude that the original lattice can not be processed through the reverse doubling construction.

On the opposite side, any remaining context generates a lattice L C such that there exists a convex set C so that the initial lattice

L satisfies L = L C [C].

Finding the Convex

Given a lattice L C satisfying the previous conditions of Subsection 3.3, the last step is to identify in L C nodes of a convex set

C such that L = L C [C].
Using Theorem 3 which gives a necessary and sufficient condition, we already know that L is obtained by the doubling construction from L C . Thus, each concept of L C gives rise to one concept in L if and only if it is not in C and two concepts in L if and only if it is in C.

Let us be more precise about these two concepts, and first let us recall some notations: (O, A, R) is the reduced context of the lattice L. We consider (J, M, R ∩ J × M) an atom in the lattice of arrowclosed sub-contexts which satifies the Geyer's condition. From this context, we can deduce L C the lattice from which a convex has been removed. Let c be a concept of L C . Recall from [START_REF] Ganter | Formal concept analysismathematical foundations[END_REF] that arrow-closed sub-contexts are also compatible ones. Since (J, M, R ∩ J × M) is a compatible sub-context, using this result, c can be written

as c = (H ∩ J, N ∩ M) with (H, N) a concept of L. Since c is a concept, we have (H ∩ J) = N ∩ M and (N ∩ M) = H ∩ J.
Recall, from the end of Subsection 2.1.3, that these operations are written • L in the reduced context (O, A, R) of L; thus we also have H L = N and N L = H. Now, we can conclude that, if c = (H ∩ J, N ∩ M) is not in the convex, it comes from the unique concept of L, namely (H, N) and thus we must have

((H ∩ J) LL , (H ∩ J) L ) = (H, N) = ((N ∩ M) L , (N ∩ M) LL ).
In the other case, we have

((H ∩ J) LL , (H ∩ J) L ) = ((N ∩ M) L , (N ∩ M) LL ).
From this point, we can state a simpler condition for a concept to be in the convex set:

Theorem 4. A concept c = (H ∩ J, N ∩ M) is in the convex if and only if (H ∩ J) L ⊆ (N ∩ M) or (N ∩ M) L ⊆ (H ∩ J) (3)
Proof. We have previously seen that if c is in the convex then:

((H ∩ J) LL , (H ∩ J) L ) = (H, N) (4) = ((N ∩ M) L , (N ∩ M) LL ) (5)
So both inclusions are true and actually are equalities.

Suppose, reciprocally, that we have the first one:

(H ∩ J) L ⊂ (N ∩ M) (6)
We obtain the same result dually in the second case.

First we prove that the inclusion is an equality. Indeed, since (J, M, R ∩ J × M) is a subcontext of (O, A, R), we have:

(H ∩ J) ⊂ (H ∩ J) L (7)
However (H ∩ J) = (N ∩ M), so:

(N ∩ M) ⊂ (H ∩ J) L (8)
and dually

(H ∩ J) ⊂ (N ∩ M) L (9)
Therefore, we deduce that (H ∩ J) L = (N ∩ M), and then (N ∩ M) L = (H ∩ J) LL .

Moreover:

(H ∩ J) ⊂ (N ∩ M) L =⇒ (N ∩ M) LL ⊂ (H ∩ J) L (10)
and with (N ∩ M) = (H ∩ J) L , we deduce that: LL , we get:

(N ∩ M) = (N ∩ M) LL (11) since (N ∩ M) ⊂ (N ∩ M) LL . Now from (H ∩ J) L = (N ∩ M) = (N ∩ M) LL and (N ∩ M) L = (H ∩ J)
((H ∩ J) L , (H ∩ J) LL ) = ((N ∩ M) LL , (N ∩ M) L ) (12)
This means that a concept ((H ∩ J), (N ∩ M)) in the small lattice L C that satisfies the condition (H ∩ J) L ⊂ (N ∩ M) or (N ∩ M) L ⊂ (H ∩ J) comes from a unique concept in the lattice L, namely the concept:

((H ∩ J) LL , (H ∩ J) L ) = (H, N) (13) = ((N ∩ M) L , (N ∩ M) LL ) (14)
Conversely, if ((H ∩ J), (N ∩ M)) does not satisfy the previous condition, it comes from two concepts in L:

((H ∩ J) LL , (H ∩ J) L ) = ((N ∩ M) L , (N ∩ M) LL ) (15)
Thus to get L from L C , one needs to double these concepts and then these concepts are exactly the ones of the convex.

EXAMPLE

To illustrate the reverse doubling convex construction, we will use the lattice given in Figure 2 and its reduced context given by Table 2 already filled with arrows. Nodes in light grey and dark grey correspond to the two occurrences of the doubled convex.

From the lattice shown in Figure 2, we compute Table 3 of one-generated arrow-closed sub-contexts and then we get the lattice of congruence relations given in Figure 3. Notice that Table 3 has been reduced after computation. In this particular case, there are two atoms.

Since the two atoms identified in Figure 3 satisfy Geyer's condition, the lattice given in Figure 2 has two decompositions.

↓ ↓ × × × × ↓ ↓ × 4 × × × ↓ ↓ ↓ ↓ ↓ ↓ 8 × × × × × × × × 12 × ↑ × • ↓ ↓ × × 14 × × ↑ • • • • • • 25 • ↑ • × × × • • × 20 • ↑ • × × × • • × 27 × × ↑ × ↑ × × × 16 × × ↑ × ↑ × × ×
Table 3: The reduced context computed to get the lattice of congruence relations (Figure 3). Using only one of these atoms, namely the one containing observation 25, we get the arrow-closed subcontext of Table 4, which satisfies Geyer's condition. Then, its concept lattice, which is also the factor lattice of the selected congruence relation, can be computed and visualized on Figure 4.

In Figure 4, nodes of the convex C are in grey, and when the doubling construction is applied on that lattice, with this convex set, the lattice from Figure 2 is obtained. Nodes in light grey and dark grey corre-Figure 3: The lattice of congruence relations of the lattice given in Figure 2 spond to the two occurrences of the doubled convex. This lattice is obtained from the reduced context given in Table 4, which is one of the two atoms of the lattice in Figure 3.

In order to test our decomposition method with respect to its ability to reduce the lattice size, a first ex- periment has been done. A series of 500 random contexts with 20 observations, 10 attributes and a density of 75% was generated. Only 42 of them (8.4%) had a non trivial decomposition. However, 17 of these contexts (40%) led to reduced lattices with a ratio of 50% while the rest (60%) of contexts led to a lattice size reduction higher than 50%. Table 5 reflects such ratios where the first column represents the lattice size reduction (i.e., the number of nodes of the reduced lattice over the number of nodes in the initial lattice) while the second column indicates the number and proportion of contexts for which the reduction ratio is in the interval given in the first column. We can then conclude that the decomposition is rarely possible, but when it occurs, it often leads to a significant reduction in the lattice size. All computations were done using the Galactic project available at http://thegalactic.github.io/ while the lattices were drawn with ConExp (see http://conexp.sourceforge.net/).

× × × 14 × × 2 × × × × 25 × × × 27 × × × × 4 × × × 8 × × × × ×

CONCLUSION AND FUTURE WORK

In this paper, a new decomposition based on Day's construction was given which uses congruence relations. Although Day's doubling construction has been widely studied, the reverse doubling construction we are investigating is, to the best of our knowledge, a new decomposition method that could be helpful in dealing with large contexts and their visualization.

To further investigate the reverse doubling construction, it would be interesting to conduct largescale experiments on very large real-life data, not only to test the potential of decomposition for lattice reduction but also its performance and scalability for such large data sets. Since noisy data occur frequently in a process of data analysis, we plan to carefully perform a preprocessing step in which efficient data cleaning techniques will be identified and used.

Since the empirical study in [START_REF] Snelting | Concept lattices in software analysis[END_REF] shows that many real-life contexts do not contain nontrivial congruence relations, we plan to formally identify cases in which the reverse doubling construction can either be used or not.

Our future work consists to study, compare and combine other decompositions with the one described in this paper. In particular the Fratini congruence [START_REF] Duquenne | Lattice drawings and morphisms[END_REF] which exploits again a congruence relation, and Atlas decomposition [START_REF] Ganter | Formal concept analysismathematical foundations[END_REF] which uses tolerance relations.

  be a lattice obtained by doubling the convex set C of the lattice L C . Note K = (O, A, R) the reduced context of L, then the reduced context K C = (J, M, R ∩ J × M) is an arrow-closed subcontext of K such that: R ∩ ((O\J) × (A\M)) = / 0 (2)

Figure 2 :

 2 Figure 2: The lattice of Figure 4 with the convex set doubled. Nodes of each convex are colored in light grey and dark grey.

Figure 4 :

 4 Figure 4: A lattice with its irreducible nodes. Nodes with a number above are meet-irreducible while nodes with a number below are join-irreducible.

Table 1 :

 1 The reduced context of the lattice in Figure

Table 2 :

 2 The reduced context of the lattice in Figure2filled with arrows.

	9 10 14 19 33 15 28 7 26 13
	2

Table 4 :

 4 The reduced context of the factor lattice given in Figure410 13 14 19 26 28 33 9 12

Table 5 :

 5 Lattice size reduction ratio and proportion of reduced lattices Ratio of the numbers of nodes Number and proportion of contexts

	50%	17 -40%
	50% to 60%	9 -21%
	60% to 70%	6 -14%
	70% to 80%	5 -12%
	80% to 90%	4 -10%
	90% to 100%	1 -3%