Marco Cognetti
email: marco.cognetti@mu.ie

Marco Aggravi
email: marco.aggravi@irisa.fr

Claudio Pacchierotti
email: claudio.pacchierotti@irisa.fr

Paolo Salaris
email: paolo.salaris@unipi.it

Paolo Robuffo Giordano

Shared Control Active Perception for Human-Assisted Navigation

published or not. The documents may come

I. INTRODUCTION

In this paper, we consider a shared control framework involving a mobile robot traveling along a desired trajectory for exploration/navigation purposes, with the shape/location of the trajectory being partially controlled by a human operator. As in typical shared control scenarios [START_REF] Selvaggio | Haptic-based shared-control methods for a dual-arm system[END_REF]- [START_REF] Rahal | Caring about the human operator: haptic shared control for enhanced user comfort in robotic telemanipulation[END_REF], we envisage a division of roles between the robot and the human operator. The mobile robot is equipped with onboard sensors and has enough autonomy for implementing lower-level control actions for addressing some "local" constraints/requirements that would otherwise be hard to handle by the human operator. The latter is in charge of providing higher-level behaviors such as steering the mobile robot towards areas of interest. The operator can provide commands to the mobile robot by acting on an input device and, when haptics is included (as we do in this work), she/he can also receive a force feedback informing about what actions the robot would like to execute. The operator is then left with the choice of whether (and to what degree) follow the feedback suggestions, thus blending her/his higher-level goals with the needs of the robot. This idea is instantiated in this paper by considering a fundamental task for any mobile robot navigating in an environment: increase the information quality acquired by the robot onboard sensors, needed a proper robot state estimation.

Thus, we propose in this paper to fuse the localization capability of an active perception framework with the highlevel capabilities of a human in fulfilling a task (e.g., exploring an environment) through a shared control approach.

II. PROPOSED APPROACH

The problem described in Section I can be formulated as: Problem 1 (Online Shared Active Sensing Control): For all t ∈ [t 0 , t f ], find the optimal location of the control points

x * c (t) = arg max xc G c (s 0 , s f ) µ , s.t. 1) q γ (x c (t), s t ) -q(t) ≡ 0, (state coherency) 2) fl(x c (τ ), s τ ) = 0 , ∀ τ ∈ [t, t f ], (flatness regularity) 3) L(x c (t), s t , s f ) = L d -L t , (fixed length) 4) usr(x c (t), s) -usr d ≡ 0, (user's task)
where L t = L(s 0 , s t ) = st s0 v(x c , σ) dσ represents the length already traveled by the robot on [t 0 , t] (and, analogously,

L(x c (t), s t , s f ) is the length of the trajectory in the future interval [s t , s f ]). Finally, v(x c , σ) = ∂γ(x c , s)/∂s 2 .
In particular, the cost function is aimed at maximizing the Shatten norm of the Constructibility Gramian (CG), that [START_REF] Salaris | Online optimal perception-aware trajectory generation[END_REF] proved it is connected to the maximum estimation uncertainty. In fact, the latter is minimized (thus maximizing the estimation performance) if the Shatten norm of the CG is maximized.

Regarding the constraints, the state coherency one is for ensuring that the optimization over the future path is coherent with the current state estimate; the flatness regularity constraint is for avoiding intrinsic singularities introduced by the flatness assumption that we performed for avoiding to integrate the robot model over the trajectory, thus saving computational time (important since we need to solve Problem 1 in realtime). Moreover, the fixed length constraint is for guaranteeing well-posedness of Problem 1, since G c could be unbounded from above if the robot has an unlimited path length. Finally, the user's task allows the human operator to modify some geometric characteristics (e.g. a specific point, the centroid, the area, and so on) of the planned path for the robot.

It is important to underline that, according to the Problem 1, the user's commands have higher priority w.r.t. maximizing the Gramian norm since the operator must have full control over the geometric properties of the path.

Moreover, we also introduce a guidance user feedback in order to make her/him aware about the possibility of increasing the amount of information collected by the robot along the future trajectory for reducing the estimation uncertainty. In particular, the feedback is computed as

f usr = βJ 4 (I κN ×κN -A N 4 )∇ xc G c (-∞, s f ) µ . (1)
with J 4 = ∂usr(xc,σ) ∂xc , A N 4 is the projector in the null-space of the four tasks in Problem 1 and β > 0 is a tunable gain.

The feedback f usr could be conveyed in different ways, e.g., as an arrow on a screen or as a kinesthetic force provided by a grounded haptic interface (both in the next Section).

III. EXPERIMENTAL RESULTS

We tested our proposed shared control approach with a unicycle robot that is equipped with a sensor that is able to measure the distance w.r.t. the four black landmarks in Figure 1. We consider four experimental modalities (N) The closed B-Spline trajectory is calculated by solving Problem 1 where the CG maximization task is removed.

In other words, the quality of the robot state estimation completely depends on the trajectory chosen by the human operator. Also, the user receives no feedback; (CG-N) The closed B-Spline trajectory of the robot is generated by solving Problem 1, including the CG maximization task. However, the user receives no feedback on how to improve the estimation of the robot state. (CG-V) As CG-N, but here the user receives visual guidance on how to move the considered trajectory point by means of an arrow defined by ( 1); (CG-H) As CG-V, but this time the user receives haptic guidance on how to move the considered trajectory point, by means of a kinesthetic force, defined by (1) and provided via the Omega.6 haptic interface. In Figure 1 the operator is asked to teleoperate the mobile robot for activating four electrical switches -in less than 90 seconds -in a given order by controlling a point (the green dot in Figure 1) on the closed B-Spline defining the trajectory of the mobile robot. The next switch to be activated is indicated in red while the already activated switches are marked in green. A switch is activated when the real robot passes through the center of its tile. However, the screen only shows the estimated robot state to the human operator (see Fig. 1(b)).

Ten participants took part to our experiment (1 woman, 9 men; age 24-37 years old). Users performed one randomized repetition of the task per experimental condition, yielding 40 trials. Operators were asked to complete the task as fast as possible, taking however into account the received feedback.

The reported results show the effectiveness and viability of the proposed shared control active perception technique. Using the active perception routine (CG-N, CG-V, CG-H) to maximize the information acquired by the robot significantly improves the performance of both tasks w.r.t. not considering the optimization of CG (N) (see Fig. 2).

The above-mentioned results confirm the importance of including an active perception term and an haptic feedback for teleoperated tasks. A video of this paper is available at https://youtu.be/yGL7i48ZisA. More details can be found in [START_REF] Cognetti | Perception-aware human-assisted navigation of mobile robots on persistent trajectories[END_REF].

Fig. 1 .

 1 Fig. 1. Power grid activation scenario. The users have to activate four switches in a certain order by having the real robot passing over them.

Fig. 2 .

 2 Fig. 2. Power grid activation results. Mean and 95% confidence interval of (a) completion time, and (b) minimum eigenvalue of P -1 (from the EKF).

This research was supported by Rennes Métropole with the "Stratégie d'attractivité durable (SAD) 2018" programme (project WH-DRONE).

2nd Italian Conference on Robotics and Intelligent Machines (I-RIM), 2020


Jérémy Besson
email: jeremy.besson@liris.cnrs.fr

Céline Robardet

Jean-François Boulicaut

Sophie Rome

Constraint-based Formal Concept Mining and its Application to Microarray Data Analysis

Keywords: Pattern discovery, constraint-based data mining, closed sets, formal concepts, microarray data analysis

come   L'archive ouverte pluridisciplinaire

Introduction

One of the most popular data mining techniques concerns transactional data analysis by means of set patterns. Indeed, following the seminal paper [START_REF] Agrawal | Mining association rules between sets of items in large databases[END_REF], hundreds of research papers have considered the efficient computation of a priori interesting association rules from the so-called frequent itemsets. Transactional data can be represented as boolean matrices (see Figure 1). Lines denote transactions and columns are boolean attributes that enable to record item occurrences. For instance, in Figure 1, transaction t 4 contains the items g 5 , g 6 , g 7 , g 8 , g 9 , and g 10 .

Items g 1 g 2 g 3 g 4 g 5 g 6 g 7 g 8 g 9 g 10 t 1 1 1 1 1 0 1 1 0 0 0 t 2 1 1 1 1 0 0 0 0 1 1 t 3 1 1 1 1 0 0 0 0 1 1 t 4 0 0 0 0 1 1 1 1 1 1 t 5 1 0 1 0 1 1 1 1 0 0 The frequent set mining problem concerns the computation of sets of attributes that are true together in enough transactions, i.e., given a frequency threshold. For instance, the set {g 1 , g 2 , g 3 } is considered frequent with a relative threshold of 30% since its frequency is 60%. It makes sense to associate to such a set, the set of transactions {t 1 , t 2 , t 3 }, i.e., the set of transactions in which all the items from {g 1 , g 2 , g 3 } occur. It provides a so-called bi-set.

The typical case of basket analysis (huge -eventually millions -number of transactions, hundreds of attributes, but sparse and lowly-correlated data) can be handled by many algorithms, including Apriori [START_REF] Agrawal | Fast discovery of association rules[END_REF] and the various Apriori-like algorithms that have been designed during the last decade. When the data are dense and highlycorrelated, these algorithms fail but the so-called condensed representations of the frequent itemsets can be computed [START_REF] Boulicaut | Frequent closures as a concise representation for binary data mining[END_REF]. For instance, efficient algorithms can compute the frequent closed sets from which every frequent set and its frequency can be derived without accessing the data [START_REF] Pasquier | Efficient mining of association rules using closed itemset lattices[END_REF][START_REF] Boulicaut | Approximation of frequency queries by mean of free-sets[END_REF][START_REF] Pei | CLOSET an efficient algorithm for mining frequent closed itemsets[END_REF][START_REF] Bastide | Mining frequent patterns with counting inference[END_REF][START_REF] Zaki | CHARM: An efficient algorithm for closed itemset mining[END_REF].

Interestingly, other important applications concern data sets with only a few transactions. This is the case for typical gene expression data analysis where items denote gene expression properties in biological situations. Here, the frequent sets denote sets of genes that are frequently co-regulated and thus can be suspected to participate to a common function within the cells. In common microarray data, the number of lines is a few tens and the number of columns is a few thousands. It is however possible to use the properties of Galois connection to compute the closed sets on the smaller dimension and derive the closed sets on the other dimension [START_REF] Rioult | Using transposition for pattern discovery from microarray data[END_REF][START_REF] Rioult | Mining concepts from large SAGE gene expression matrices[END_REF]. Notice that once every closed set is known, all the frequent sets and their frequencies are known as well.

In this paper, we consider bi-set mining in difficult cases, i.e., when the data is dense and when none of the dimensions is quite small. Bi-sets are composed of a set of lines T and a set of columns G. T and G can be associated by various relationships, e.g., the fact that all the items of G are in relation with each transaction of T . Such a bi-set is called a 1-rectangle. It is interesting to constrain further 1-rectangle set components to be closed sets: it leads to maximal 1-rectangles that are also called formal concepts or concepts [START_REF] Wille | Restructuring lattice theory: an approach based on hierarchies of concepts[END_REF]. Minimal and maximal frequency but also syntactic constraints (see, e.g., [START_REF] Ng | Exploratory mining and pruning optimizations of constrained associations rules[END_REF]) on set components can be used as well.

The contribution of this paper is twofold. First, we propose an original algorithm called D-Miner that computes concepts under constraints 1 . It works differently from other concept discovery algorithms (see, e.g., [START_REF] Ganter | Two basic algorithms in concept analysis[END_REF][START_REF] Berry | Concepts can not affor to stammer[END_REF][START_REF] Nourine | A fast algortihm for building lattices[END_REF]) and frequent closed set computation algorithms [START_REF] Pasquier | Efficient mining of association rules using closed itemset lattices[END_REF][START_REF] Boulicaut | Approximation of frequency queries by mean of free-sets[END_REF][START_REF] Pei | CLOSET an efficient algorithm for mining frequent closed itemsets[END_REF][START_REF] Bastide | Mining frequent patterns with counting inference[END_REF][START_REF] Zaki | CHARM: An efficient algorithm for closed itemset mining[END_REF]. Starting from the bi-set with all items and all transactions, D-Miner performs a depth-first search of concepts by recursively splitting into bi-sets that do not contain "0" values. D-Miner can be used in dense boolean data sets when the previous algorithms generally fail. Furthermore, thanks to an active use of userdefined monotonic constraints, it enlarges the applicability of concept discovery for matrices whose none of the dimensions is small.

A second major contribution concerns microarray data analysis. We introduce a new gene expression data mining technique based on constraint-based concept mining. Indeed, we consider a rather generic scenario where gene expression is available for two sets of biological situations, e.g., one data set about individuals that have a given pathology and another data set about individuals without this pathology. Boolean data is derived from raw microarray data and enriched with information about transcription factors. It leads to a richer boolean context from which a priori interesting concepts can be extracted. Working on an original data set, we point out one biologically relevant extracted concept that demonstrates the added-value of data enrichment with transcription factors.

Section 2 contains the needed definitions when considering constraint-based extraction of bi-sets from transactional/boolean data. Section 3 introduces the D-Miner algorithm. Proofs of D-Miner properties are given in technical Annex A. We also provide an experimental validation on artificial and benchmark data sets. For that purpose, D-Miner is compared with several efficient algorithms that compute frequent closed sets. Section 4 presents our current work on gene expression data analysis. It contains a formalization of a new interesting data mining technique for microarray data and several experimentations on real data. Finally, Section 5 concludes.

Problem setting

Let O denotes a set of objects or transactions and P denotes a set of items or properties. In Figure 1, O = {t 1 , . . . , t 5 } and P = {g 1 , g 2 , . . . , g 10 }. The transactional data is represented by the matrix r of relation R ⊆ O × P. We write (t i , g j ) ∈ r to denote that item j belongs to transaction i or that property j holds for objects i. Such a data set can be represented by means of a boolean matrix (e.g., r 1 in Figure 1).

For a typical basket analysis problem, O is the set of transactions and P corresponds to the products. The matrix then records which are the products that belong to the transactions, i.e., the products that have been purchased together. For instance, in Figure 1, we see that products identified by g 9 and g 10 are bought together in transactions t 2 , t 3 , and t 4 .

For a typical boolean gene expression data set (see, e.g., [START_REF] Becquet | Strong association rule mining for large gene expression data analysis: a case study on human SAGE data[END_REF]), O is the set of biological situations and P corresponds to the genes. The relation then records which are the genes that are, e.g., over-expressed in the biological situations. Other expression properties can be considered (e.g., strong variation, under-expression). For instance, given Figure 1, we might say that genes g 5 and g 6 are over-expressed in situations t 4 and t 5 .

The language of bi-sets is the collection of couples from L = L O × L P where L O = 2 O (sets of objects) and L P = 2 P (sets of items).

Let us now consider evaluation functions for such patterns. This is not an exhaustive list of useful primitives. We mainly consider Galois operators (denoted as φ and ψ) that have been proved extremely useful. [START_REF] Wille | Restructuring lattice theory: an approach based on hierarchies of concepts[END_REF]) If T ⊆ O and G ⊆ P, assume φ(T, r) = {g ∈ P | ∀t ∈ T, (t, g) ∈ r} and ψ(G, r) = {t ∈ O | ∀g ∈ G, (t, g) ∈ r}. φ provides the set of items that are common to a set of objects and ψ provides the set of objects that share a set of items. (φ, ψ) is the so-called Galois connection between O and P. We use the classical notations h = φ • ψ and h = ψ • φ to denote the Galois closure operators. Example 2 Let us consider again the bi-set ({t 1 , t 2 , t 3 }, {g 1 , g 2 }) and the data from Figure 1.

Definition 1 (Galois connection

Definition 2 (Frequency) The frequency of a set of items

G ⊆ P in r is |ψ(G, r)|. The frequency of a set of objects T ⊆ O in r is |φ(T, r)|. Example 1 Given Figure 1, let us consider the bi-set (T, G) where G = {g 1 , g 2 } and T = {t 1 , t 2 , t 3 }. The frequency of G is |ψ(G, r 1 )| = |{t 1 , t 2 , t 3 }| = 3, the frequency of T is |φ(T, r 1 )| = |{g 1 , g 2 , g 3 , g 4 }| = 4. Notice that, for this bi-set, T = ψ(G, r 1 ) but G = φ(T,
{g 1 , g 2 } satisfies C minfreq (r 1 , 3, G). The set {g 1 , g 2 } is not closed: h({g 1 , g 2 }, r 1 ) = φ(ψ({g 1 , g 2 }, r 1 ), r 1 ) = {g 1 , g 2 , g 3 , g 4 }. An example of a closed set on items is {g 1 , g 2 , g 3 , g 4 }: h({g 1 , g 2 , g 3 , g 4 }, r 1 ) = {g 1 , g 2 , g 3 , g 4 }. Also, the set of objects {t 1 , t 2 , t 3 } is closed: h ({t 1 , t 2 , t 3 }, r 1 ) = {t 1 , t 2 , t 3 }.
The closure of a set of items G, h(G, r), is the maximal (w.r.t. set inclusion) superset of G which has the same frequency than G in r. A closed set of items is thus a maximal set of items which belong to a given set of transactions. For instance, the closed set {g 1 , g 3 } in r 1 (see Figure 1) is the largest set of items that are shared by transactions t 1 , t 2 , t 3 and t 5 . r) and G = φ(T, r) [START_REF] Wille | Restructuring lattice theory: an approach based on hierarchies of concepts[END_REF]. A concept is thus a maximal 1-rectangle.

Definition 5 (1-rectangles and 0-rectangles

) A bi-set (T, G) is a 1-rectangle iff ∀g ∈ G and ∀t ∈ T , (t, g) ∈ r. A bi-set (T, G) is a 0-rectangle in r iff ∀t ∈ T and ∀g ∈ G then (t, g) ∈ r. Definition 6 (Concept) (T, G) is called a formal concept or concept in r when T = ψ(G,
Given the Galois connection, concepts are built on closed sets and each closed set of items (resp. objects) is linked to a closed set of objects using ψ (resp. items using φ) [START_REF] Wille | Restructuring lattice theory: an approach based on hierarchies of concepts[END_REF]. In other terms, for a concept (T, G) in r, constraint C Close (T, r)∧C Close (G, r) is satisfied. Notice also that the collection of concepts is obviously included in the collection of 1-rectangles.

Example 3

Given Figure 1, ({t 1 , t 2 , t 3 }, {g 1 , g 2 }) is a 1-rectangle but it is not a concept. Twelve bi-sets are concepts in r 1 . ({t 2 , t 3 }, {g 1 , g 2 , g 3 , g 4 , g 9 , g 10 }) and

({t 1 , t 2 , t 3 , t 5 }, {g 1 , g 3 }) are examples of concepts in r 1 .
Other interesting primitive constraints can be defined, e.g., syntactic constraints on each set component of a bi-set. A typical example is to enforce that a given item belongs or does not belong to the item set component.

Many data mining processes on transactional data can be formalized as the computation of bi-sets whose set components satisfy combinations of primitive constraints.

Mining the frequent sets of items is specified as the computation of {G ∈ L P | C minfreq (r, γ, G) satisfied}. We can then provide the bi-sets of the form {(T, G) ∈ L O ×L P | C minfreq (r, γ, G)∧T = ψ(G, r)}. These bi-sets are frequent sets of attributes associated to the objects in which they occur. Another typical post-processing of frequent sets is to compute frequent association rules from the frequent sets and keep the ones with enough confidence [START_REF] Agrawal | Fast discovery of association rules[END_REF].

An important data mining task concerns frequent closed set mining, i.e., the computation of Θ 1 = {G ∈ L P | C minfreq (r, γ, G) ∧ C Close (G, r) satisfied}. This task has been studied a lot as the computation of a condensed representation for the frequent sets [START_REF] Pasquier | Efficient mining of association rules using closed itemset lattices[END_REF][START_REF] Boulicaut | Frequent closures as a concise representation for binary data mining[END_REF]. We illustrate in Section 3.3 the computation of such collections using Charm, Ac-Miner, and Closet. Frequent (closed) sets of objects can be desired as well.

The collection

Θ 2 = {(T, G) ∈ L O × L P | C Close (G, r) ∧ T = ψ(G, r)} is the collection of concepts. We have also Θ 2 = {(T, G) ∈ L O × L P | C Close (T, r) ∧ G = φ(T, r)}.
Let us point out that this provides a strategy for computing concepts by first choosing to compute the closed sets on the smaller dimension.

When we use our algorithm D-Miner in Section 3.3, we compute

Θ 3 = {(T, G) ∈ L O × L P | C minfreq (r, γ, G) ∧ C Close (G, r) ∧ T = ψ(G, r)}, i.e.
, the sets from Θ 1 to which we associate sets of transactions that support them (using ψ).

Definition 7 (Transposition) If r ⊆ O × P, its transposition is t r ⊆ P × O where (g, t) ∈ t r ≡ (t, g) ∈ r. Property 1 If G ⊆ P is a set of items and T ⊆ O is a set of objects, we have ψ(T, t r) = φ(T, r) and φ(G, t r) = ψ(G,

r). As a result, we have also h(T, t r) = h (T, r) and h (G, t r) = h(G, r). The proof of these properties is straightforward.

These observations explain why it is possible to compute the whole collection of concepts as

Θ = {(T, G) ∈ L O × L P | h(G, r) = G ∧ T = ψ(G, r)} when |P| < |O| or as Θ = {(T, G) ∈ L O × L P | h (T, r) = T ∧ G = φ(T, r)} otherwise.
In this second case, the same algorithm can be used after a simple transposition since h (T, r) = h(T, t r) and φ(T, r) = ψ(T, t r).

We are currently applying concept discovery techniques on typical microarray data sets (see Section 5).

In such applications, we can get dense boolean contexts that are hard to process if further user-defined constraints are not only specified but also pushed deeply into the extraction algorithms. Using user-defined constraints enables to produce putative interesting concepts before any post-processing phase. Indeed, concept discovery techniques can provide huge collection of patterns (e.g., we report in Section 5 an output of more than 5 millions of concepts) and supporting post-processing on such collections is hard or even impossible. It motivates the a priori use of constraints on both L O and L P . Typical examples concern constraints on the size of T and G. It leads to the extraction of frequent concepts. Furthermore, the key issue for pushing user-defined constraints deeply into the mining algorithms is a clever use of specialization relations on the pattern language. For instance, it is well-known that pushing monotonic or anti-monotonic (w.r.t. a specialization relation) constraints can drastically reduce the amount of needed resources during an extraction (see, e.g., [START_REF] Ng | Exploratory mining and pruning optimizations of constrained associations rules[END_REF][START_REF] Jeudy | Optimization of association rule mining queries[END_REF]). Let us now introduce our specialization relation on bi-sets. ,σ,φ(T,r)). When considering frequent concept mining, we use monotonic constraints on the size of sets but any other monotonic constraint could be used as well.

Definition 8 (Specialization relation and monotonicity) Our specialization relation on bi-sets from

L = L O ×L P is defined by (T 1 , G 1 ) ≤ (T 2 , G 2 ) iff T 1 ⊆ T 2 and G 1 ⊆ G 2 . A constraint C is said anti-monotonic w.r.t. ≤ iff ∀α, β ∈ L such that α ≤ β, C(β) ⇒ C(α). C is said monotonic w.r.t. ≤ iff ∀α, β ∈ L such that α ≤ β, C(α) ⇒ C(β). Definition 9 (Frequent concept) A concept (T, G) is called frequent when constraint C t (r, σ 1 , T ) (resp. C g (r, σ 2 , G)) if |T | ≥ σ 1 (resp. |G| ≥ σ 2 ). These constraints are both monotonic w.r.t. ≤ on L O × L P . Notice that the constraint C t (r, σ, T ) ≡ |T | ≥ σ ≡ C minfreq (r
We choose to enforce the symmetry of our extractor on L O and L P to be able to transpose the matrix without loosing the possibility of using the constraints. Indeed, as explain earlier, where there are few objects and many items, we first perform a simple transposition to reduce the extraction complexity.

D-Miner

D-Miner is a new algorithm for extracting concepts (T, G) under constraints. It builds simultaneously the sets T and G and it uses monotonic constraints w.r.t. our specialization relation, simultaneously on L O and L P , to reduce the search space. Its originality is to construct simultaneously closed set on L O and L P such that it enables to push monotonic constraints on the two set components.

Principle

A concept (T, G) is such that all its items and objects are in relation by R. Thus, the absence of relation between an item g and an object t generates two concepts, one with g and without t, and another one with t and without g. D-Miner is based on this observation.

Let us denote by H a set of 0-rectangles (Definition 5) such that it is a cover of the false values (0) of the boolean matrix r, i.e., ∀g ∈ P and ∀t ∈ O such that (t, g) ∈ r, it exists at least one element (X, Y ) of H such that t ∈ X and g ∈ Y .

The elements of H are called cutters. The principle of D-Miner consists in starting with the couple (O,P) and then splitting it recursively using the elements of H until H is empty and thus each couple is a

1-rectangle. An element (a, b) of H is used to cut a couple (X, Y ) if a ∩ X = ∅ and b ∩ Y = ∅.
By convention, one defines the left son of (X, Y ) by (X \ a, Y ) and the right son by (X, Y \ b).

This principle enables to obtain all the concepts, i.e., the maximal 1-rectangles (see Example 4) but also some non maximal ones (see Example 5). Therefore, we will explain how to prune them to obtain all the concepts and only the concepts.

The construction of H is a key phase since its elements are used to recursively split couples of sets: H must be as small as possible to reduce the depth of recursion and thus execution time. On another hand, one should not waste too much time to compute H. H contains as many elements as lines in the matrix. Each element is composed of the attributes valued by '0' in this line.

Time complexity for computing H is in O(|O| × |P|). It is thus easy to compute it and computing time is negligible w.r.t. the one of the cutting procedure. Furthermore, using this definition makes easier the pruning of 1-rectangles that are not concepts.

We now provide examples of D-Miner executions considering only the constraints that enforce a bi-set to be a concept. The use of monotonic constraints on L O and L P is presented later.

Example 4 Assume

O = {t 1 , t 2 , t 3 } and P = {g 1 , g 2 , g 3 }. Relation r 2 is defined in Table 1 (left).
Here, H is {(t 1 , g 1 ), (t 3 , g 2 )}. D-Miner algorithm starts with (O, P). Figure 2 illustrates this process. We get four 1-rectangles that are the four concepts for this boolean context. Notice that for the sake of simplicity, we do not use here the standard notation for set components within bi-sets: a bi-set like (t

1 t 2 t 3 , g 1 g 2 g 3 ) denotes ({t 1 , t 2 , t 3 }, {g 1 , g 2 , g 3 }). g 1 g 2 g 3 t 1 0 1 1 t 2 1 1 1 t 3 1 0 1 g 1 g 2 g 3 t 1 0 0 1 t 2 1 0 1 t 3 0 0 1
) (t 1 t 2 t 3 , g 1 g 2 g 3 ) (t 1 , g 1 ) (t 2 t 3 , g 1 g 2 g 3 ) (t 3 , g 2 ) (t 2 , g 1 g 2 g 3 ) (t 2 t 3 , g 1 g 3 ) (t 1 t 2 t 3 , g 2 g 3 ) (t 3 , g 2 ) (t 1 t 2 , g 2 g 3 ) (t 1 t 2 t 3 , g 3 )
Figure 2: Concept construction on r 2 (Example 4)

Example 5 Assume now the relation r 3 as given in Table 1 (right). Computing

H provides {(t 1 , g 1 g 2 ), (t 2 , g 2 ), (t 3 , g 1 g 2 )}. Figure 3 illustrates D-Miner execution. Some bi-sets are underlined and this will be explained in Example 6. From Figure 3, we can see that (t 2 , g 2 ) and (t 3 , g 1 g 2 ) from H are not used to cut (t 1 t 2 t 3 , g 3 ) because {g 2 } ∩ {g 3 } = ∅ and {g 1 g 2 } ∩ {g 3 } = ∅. The computed collection of bi-sets is:

(t 1 t 2 t 3 , g 1 g 2 g 3 ) (t 1 , g 1 g 2 ) (t 2 t 3 , g 1 g 2 g 3 ) (t 2 , g 2 ) (t 3 , g 1 g 2 g 3 ) (t 3 , g 1 g 2 ) (∅,g 1 g 2 g 3 ) (t 3 , g 3 ) (t 2 t 3 , g 1 g 3 ) (t 3 , g 1 g 2 ) (t 2 ,g 1 g 3 ) (t 2 t 3 , g 3 ) (t 1 t 2 t 3 , g 3 ) (t 2 , g 2 ) (t 1 t 2 t 3 , g 3 ) (t 3 , g 1 g 2 ) (t 1 t 2 t 3 , g 3 )
{(t 1 t 2 t 3 , g 3 ), (t 2 , g 1 g 3 ), (∅, g 1 g 2 g 3 ), (t 3 , g 3 ), (t 2 t 3 , g 3 )}
We see that (t 3 , g 3 ) ≤ (t 1 t 2 t 3 , g 3 ) and (t 2 t 3 , g 3 ) ≤ (t 1 t 2 t 3 , g 3 ) and thus these 1rectangles are not concepts.

To explain why the method computes the concepts and some subsets of them, we introduce a new notation. Let r[T, G] denote the reduction of r on objects from T and on items from 4). Property 2 Let (X, Y ) be a leaf of the tree and H L (X, Y ) be the set of cutters associated of the left branches of the path from the root to (X, Y ). Then (X, Y ) is a concept iff Y contains at least one item of each itemset of H L (X, T ). It means that when trying to build a right son (X, Y ) (i.e., to remove some elements from Y ), we must check that ∀(a, b) ∈ H L (X, Y ), b∩Y = ∅. This constraint is called the left cutting constraint.

G. When a bi-set (X, Y ) is split by a cutter (a, b) ∈ H, then (X \ a, Y ) (the left son) and (X, Y \ b) (the right son) are generated. If a concept (C X , C Y ) exists in r[X \ a, Y ] such that C Y ∩ b = ∅ then (C X ∪ a, C Y ) is a concept in r[X, Y ]. Indeed, given our technique for computing H, (a, Y \ b) is a 1-rectangle (see Figure

Example 6 We take the context used for Example 5 (see Table 1 on the right).

1-rectangles (t 3 , g 3 ) and (t 2 t 3 , g 3 ) are pruned using Property 2. (t 3 , g 3 ) comes from the left cutting of (t 1 t 2 t 3 ,g 1 g 2 g 3 ) and then the left cutting of (t 2 t 3 , g 1 g 2 g 3 ). The items of (t 3 , g 3 ) must contain at least one item of {g 1 , g 2 } and one item of {g 2 }, i.e., the precedent left cutter set of items. It is not the case and thus (t 3 , g 3 ) is pruned. (t 2 t 3 , g 3 ) comes from just one left cutter: (t 1 ,g 1 g 2 ). It contains neither g 1 nor g 2 . Consequently, nodes that are underlined in Figure 3 are pruned.

Algorithm

Before cutting a bi-set (X, Y ) by a cutter (a, b) in two bi-sets (X\a, Y ) and (X, Y \b), two types of constraints must be checked, first the monotonic constraints and then the left cutting constraint. Closeness property (or maximality) is implied by the cutting procedure.

D-Miner is a depth-first method which generates bi-sets ordered by relation ≤. Monotonic constraints w.r.t. either O or P are used to prune the search space: if (X, Y ) does not satisfy a monotonic constraint C then none of its sons satisfies C and it is unnecessary to cut (X, Y ). Constraint C is a conjunction of a monotonic constraint C t on O and a monotonic constraint C g on P. Algorithms 1 and 2 contain the pseudo-code of D-Miner. First, the set H of cutters is computed. Then the recursive function cutting() is called.

Function cutting cuts out a bi-set (X, Y ) with the first cutter H[i] that satisfies the following constraints.

g (a, b) ← H[i] If (i ≤ |H| -1) // i-th cutter is selected If ((a ∩ X = ∅) or (b ∩ Y = ∅)) Q ← Q ∪ cutting((X, Y ), H, i + 1, H L ) Else If C t (r, σ 1 , X \ a) is satisfied H L ← H L ∪ (a, b) Q ← Q ∪ cutting((X\a, Y ), H, i + 1, H L ) H L ← H L \ (a, b) If C g (r, σ 2 , Y \b) is satisfied ∧ ∀(a , b ) ∈ H L , b ∩ Y \b = ∅ Q ← Q ∪ cutting((X, Y \b), H, i + 1, H L ) Else Q ← (X, Y ) Return Q
second cutting of (X, Y ), two constraint checking are needed. First the monotonic constraints on Y \b (i.e., C g (Y \ b)) is checked and then we prune redundant concepts using left cutters.

It is possible to optimize this algorithm. First, the order of the elements of H is important. The aim is to cut as soon as possible the branches which generate non-maximal 1-rectangles. Then, H is sorted by decreasing order of size of the itemset component. Moreover, to reduce the size of H, the cutters which have the same set of items are gathered:

∀(a 1 , b 1 ), (a 2 , b 2 ) ∈ H, if b 1 = b 2 then H = H \ {(a 1 , b 1 ), (a 2 , b 2 )} ∪ (a 1 ∪ a 2 , b 1 )
. Finally, if |P| > |O|, we transpose the matrix to obtain a set H of minimum size.

Experimental validation

We compare the execution time of D-Miner with those of Closet [START_REF] Pei | CLOSET an efficient algorithm for mining frequent closed itemsets[END_REF], Ac-Miner [START_REF] Boulicaut | Approximation of frequency queries by mean of free-sets[END_REF][START_REF] Boulicaut | Free-sets: a condensed representation of boolean data for the approximation of frequency queries[END_REF] and Charm [START_REF] Zaki | CHARM: An efficient algorithm for closed itemset mining[END_REF]. Closet, Ac-Miner and Charm are efficient algorithms that compute frequent closed sets. These algorithms are based on different techniques. For instance, Closet and Charm perform a depth-first search for frequent closed sets. Ac-Miner computes level-wise the frequent free sets and then output their closures, i.e., the frequent closed sets. An algorithm like Pascal [START_REF] Bastide | Mining frequent patterns with counting inference[END_REF] does the same even though the free sets are here called key patterns. On another hand, D-Miner can be used to compute frequent concepts and thus frequent closed sets. It motivates this experimental validation where we extract frequent closed sets for various frequency thresholds on artificial data sets and two benchmark data sets from the UCI repository. As we explained earlier, it is easy to provide concepts from closed sets on O or P and, in these experiments, we just compare the execution time of closed set mining algorithms like Closet or Charm without the small extra-time for concept generation.

We use Zaki's implementation of Charm [START_REF] Zaki | CHARM: An efficient algorithm for closed itemset mining[END_REF] and Bykowski's implementations of Ac-Miner [START_REF] Boulicaut | Approximation of frequency queries by mean of free-sets[END_REF][START_REF] Boulicaut | Free-sets: a condensed representation of boolean data for the approximation of frequency queries[END_REF] and Closet [START_REF] Pei | CLOSET an efficient algorithm for mining frequent closed itemsets[END_REF]. For a fair comparison, in every experiment, we transpose the matrices to have the smaller number of columns for Closet, Ac-Miner and Charm and to have the smaller number of lines for D-Miner. Indeed, the computation complexity depend on the number of columns for Closet, Ac-Miner and Charm and on the number of lines for D-Miner. The minimal frequency threshold is given as a relative frequency w.r.t. the total number of objects/items. All extractions have been performed on a Pentium III (450 MHz, 128 Mb).

In Annex B, we present the execution time of the four algorithms on several artificial data sets generated with the IBM2 generator. We generated 60 dense data sets by varying the number of columns (300, 700 and 900 columns), the number of lines (100 and 300 lines) and the density of "1" values (15 % and 35 %). For each combination of parameters, we generated 5 data sets. Table 2 of Annex B provides the mean and the standard deviation of execution time (in seconds) used by each algorithm on data sets with 15% density. We observe that d-miner succeeds to extract closed sets in contexts where other algorithms do not succeed. Table 3 of Annex B provides the mean and the standard deviation of execution time (in seconds) used by each algorithms on data sets with 35% density. For this type of data, the superiority of d-miner is even more obvious.

In Figure 5, we show the needed execution time for frequent closed pattern extraction on the benchmark "Mushroom". Its derived boolean context contains 8 124 lines and 120 columns. One of the well accepted biological hypothesis is to consider that most of the specific properties of a cell result from the interaction between its genes and its cellular environment. At a molecular level, functional adaptation involves quantitative and qualitative changes in gene expressions. Analysis of all the RNA transcripts present in a cell or in a tissue (named the transcriptome) offers unprecedented opportunities to map the transitions between an healthy state and a pathological one. It has motivated a huge effort for technologies that could monitor simultaneously the expression level of a large number of genes [START_REF] Derisi | Exploring the metabolic and genetic control of gene expression on a genomic scale[END_REF][START_REF] Velculescu | Serial analysis of gene expression[END_REF]. The cDNA microarray technology [START_REF] Derisi | Exploring the metabolic and genetic control of gene expression on a genomic scale[END_REF] is such a powerful tool for the global analysis of gene expression and thus for identifying genes related to disease states and targets for clinical intervention. The data generated by these experiments can be seen as expression matrices in which the expression level (real value) of genes are recorded in various situations. Life scientists are facing an unprecedent data-analysis challenge since the large data sets generated from microarray analysis (involving thousands of genes) are not easily analyzed by classical one-by-one genetics. They need new techniques that can support the discovery of biological knowledge from these data sets. Indeed, the logical step which follows the identification of groups of co-regulated genes is the discovery of the common mechanism which coordinated the regulation of these genes. Typical techniques support the search for genes and situations with similar expression profiles. This can be achieved with hierarchical clustering (e.g., [START_REF] Eisen | Cluster analysis and display of genome-wide expression patterns[END_REF]), biclustering (e.g., [START_REF] Robardet | Comparison of three objective functions for conceptual clustering[END_REF][START_REF] Jiang | Cluster analysis for gene expression data: A survey[END_REF]), CPA and statistical analysis (e.g., [START_REF] Dudoit | Bioconductor R packages for exploratory analysis and normalization of cDNA microarray data[END_REF]). Frequent set mining has been studied as a complementary approach for the identification of a priori interesting set of genes and situations (see, e.g., [START_REF] Becquet | Strong association rule mining for large gene expression data analysis: a case study on human SAGE data[END_REF]). In that case, boolean matrices are built that record expression properties of the genes (e.g., over-expression, strong variation).

Our concrete application concerns the analysis of DNA microarray data. Each DNA microarray contains the RNA expression level of about 20 000 genes before and after a perfusion of insulin in their skeletal muscle [START_REF] Rome | Microarray profiling of human skeletal muscle reveals that insulin regulates 800 genes during an hyperinsulinemic clamp[END_REF]. For each gene and each subject we take the logarithm of the ratio between the two measures. In our experimentation 10 DNA microarrays have been made, 5 for healthy persons and 5 for type 2 diabetic patients.

Statistical preprocessing has lead to the selection of 8 171 genes. Among these genes, many of them (more than 10%) are differently expressed between the healthy and the diabetic persons. A subset of such data is given in Figure 7 to illustrate the discretization procedure and the enrichment of the data. Assume that here, we have 5 genes (g 1 , g 2 , g 3 , g 4 , g 5 ) and two sets of biological situations (H composed of the two healthy subjects and D composed of three diabetic patients). The first two situations correspond to gene expression level for healthy people, H ={h 1 , h 2 }, and the three following ones correspond to gene expression level for diabetic patients, D ={d 1 , d 2 , d 3 }. A positive value (resp. negative value) means that the gene is up-regulated (resp. down-regulated) in the situation. We are interested in genes with strong variation under the insulin clamp. Figure 8 provides a boolean context for the expression data from Figure 7. A value "1" for a biological situation and a gene means that the gene is up (greater than |t|) or down (lower than -|t|) regulated in this situation. On this toy example, we choose a threshold t = 0.3. The discretization of the gene expression data into boolean expression properties is however a complex task (see, [START_REF] Becquet | Strong association rule mining for large gene expression data analysis: a case study on human SAGE data[END_REF] for a discussion). It is out of the scope of this paper to discuss further this issue. Let us now propose an original enrichment for this kind of boolean context. Additional information on, e.g., molecular functions, biological processes and the presence of transcription factors, are useful to interpret the extracted bi-sets or concepts. Transcription factors (TF) are proteins which specifically recognize and bind DNA regions of the genes. Following the binding, the expression of the gene is increased or decreased. A gene is usually regulated by many TF, and a TF can regulate different genes at the same time. In our current application, the challenge for the biologist is the identification of a combination of TF associated to a group of genes which are regulated in the group of healthy subjects but not in the diabetic group. To the best of our knowledge, no data mining technique supports such an analysis. We have been looking for the transcription factors that can bind to the regulatory region of each gene of the microarray data. For that purpose, we have used EZ-Retrieve, a free software for batch retrieval of coordinated-specified human DNA sequences [START_REF] Zhang | Ezretrieve: a web-server for batch retrieval of coordinate-specified human dna sequences and underscoring putative transcription factor-binding sites[END_REF]. In Figure 9, we continue with our toy example by considering two transcription factors tf 1 and tf 2 . A value "1" for a gene and a transcription factor means that this transcription factor regulates the gene. We have a value "0" otherwise. It is now possible to merge the boolean data about biological situations and transcription factors into a unique boolean context (see Figure 10). Such a context encodes information about different gene properties that are biologically relevant: its expression level for healthy people, its expression level for diabetic patient and the regulation by transcription factors. The set O is thus partitioned into the set H, the set D and a set of transcription factors F.

Genes

Genes g 1 g 2 g 3 g 4 g 5 H h 1 1 1 1 0 1 h 2 0 0 0 0 1 D d 1 0 1 1 0 0 d 2 0 1 1 1 1 d 3 1 0 1 1 0
Genes g 1 g 2 g 3 g 4 g 5 F tf 1 1 1 0 1 0 tf 2 1 0 0 1 1
Genes g 1 g 2 g 3 g 4 g 5 H h 1 1 1 1 0 1 h 2 0 0 0 0 1 D d 1 0 1 1 0 0 d 2 0 1 1 1 1 d 3 1 0 1 1 0 F tf 1 1 1 0 1 0 tf 2 1 0 0 1 1
Figure 10: An enriched microarray boolean context For technical reasons, 600 genes among the 8 171 ones for which expression value is available have been processed. Among these 600 genes, 496 genes have unknown functions and thus the list of the transcription factors that might regulate them is not available. We finally got a list of 94 transcription factors that can regulate 304 genes. In other terms, the boolean context we have has 104 objects (94 transcription factors and 10 biological situations, 5 for healthy individuals and 5 for diabetic patients) and 304 genes. Concept discovery from such a boolean context is already hard. Furthermore, after discretization, we got a dense boolean context with 17% of the cells containing the true value (i.e., "1"). In such a situation, available algorithms for mining closed sets can turn to be intractable. Furthermore, in a short term perspective, we will get much more transcription factors and much more genes (up to several hundreds or thousands).

The challenge that has been proposed by the biologists is as follows. The potentially interesting bi-sets are concepts that involve a minimum number of genes (more than γ) to ensure that the extracted concepts are not due to noise. They must also be made of enough biological situations from D and few biological situations of H or vice versa. In other terms, the potentially interesting bi-sets (T, G) are concepts that verify the following constraints as well:

(|T H | ≥ 4 ∧ |T D | ≤ 2 ∧ |G| ≥ γ) ( 1 ) ∨ (|T D | ≥ 4 ∧ |T H | ≤ 2 ∧ |G| ≥ γ) ( 2
)
where T H and T D are the subsets of T that concern respectively the biological situations from H (healthy individuals) and the ones from D (for diabetic patients). Notice that this constraint which is the disjunction of Equation ( 1) and Equation ( 2) is a disjunction of a conjunction of monotonic and anti-monotonic constraints on L O and L P . Using D-Miner, we push the monotonic ones.

Comparison with other algorithms

The execution time for computing frequent closed sets on this biological data with Closet, Ac-Miner, Charm and D-Miner is shown on Figure 11. Notice that the data are particular: there are very few frequent concepts before the relative frequency threshold 0.1 on genes (5 534 concepts) and then the number of concepts increases very fast (at the lowest frequency threshold, there are more than 5 millions of concepts). In this context, extracting putative interesting concepts needs for a very low frequency threshold, otherwise almost no concepts are provided. Consequently D-Miner is much better than the other algorithms for this application because it succeeds to extract concepts when the frequency threshold is lower than 0.06 whereas it is impossible with the others.

End users, e.g., biologists, are generally interested in a rather small subset of the extracted collections. These subsets can be specified by means of user-defined constraints that can be checked afterwards (post-processing) on the whole collection of concepts. It is clear however that this approach leads to tedious or even impossible post-processing phases when, e.g., more than 5 millions of concepts are computed (almost 500M bytes of patterns). It clearly motivates the need for constraint-based mining of concepts.

Extraction of concepts under constraints

Let us first extract the concepts which contain at least 4 among the 5 situations associated to the diabetic patients and at least γ genes. The first constraint is monotonic on L O whereas the second one is monotonic on L P . Figure 12 presents the number of concepts verifying the constraints when γ vary. Using these constraints, we can reduce drastically the number of extracted concepts while selecting relevant ones according to end users. However, the small number of biological situations associated to the diabetic patients in our data set strongly constrain the size of the extracted collection: only 323 concepts satisfy C t (r, 4, T D ). Thus, in this data set, this single constraint appears to be quite selective and the extraction can be performed with any frequent closed set extraction algorithm using the constraint C t (r, 4, T D ). 234 concepts are obtained and can be post-processed in order to check constraint C g (r, γ, G) afterwards.

Notice however that, in other data sets, using simultaneously these two constraints can make the extraction possible whereas the extraction using only one of the two constraints and a post-processing strategy can be intractable. To illustrate this point, let us consider two constraints C t (r, γ 1 , T ) and C g (r, γ 2 , G) on L O and L P . In Figure 13, we plot the number of concepts obtained when γ 1 and γ 2 vary. It appears that using only one of the two constraints does not reduce significantly the number of extracted concepts (see values when γ 1 = 0 or γ 2 = 0). However, when we use simultaneously the two constraints, the size of the concept collection decreases strongly (the surface of the values forms a basin). For example, the number of concepts verifying the constraints C g (r, 10, G) and C t (r, 21, T ) is 142 279. The number of concepts verifying the constraints C g (r, 10, G) and C t (r, 0, T ) is 5 422 514. The number of concepts verifying the constraints C g (r, 0, G) and C t (r, 21, T ) is 208 746. The gain when using simultaneously both constraints is very significant.

The aim of our work with biologists is to extract concepts in larger microarray data sets. In this context the use of conjunction of constraints on genes, biological situations and transcription factors appears to be crucial.

Biological interpretation of an extracted concept

To validate the biological relevancy of the bi-sets that can be extracted on our biological data, let us consider one of the concepts D-Miner has computed. It contains 17 genes Hs.2022, Hs.184, Hs.1435, Hs.21189, Hs.25001, Hs.181195, Hs.295112, Hs.283740, Hs.12492, Hs.2110, Hs.139648, Hs.119, Hs.20993, Hs.89868, Hs.73957, Hs.57836 and Hs.302649 which are all potentially regulated by the same 8 transcription factors (c-Ets-, MZF1, Ik-2, CdxA, HSF2, USF, v-Myb, AML-1a). This association holds for 4 healthy subjects. This concept is very interesting as it contains genes which are either up-regulated or down-regulated after insulin stimulation, based on the homology of their promotor DNA sequences. In other terms, common transcription factors can regulate these genes either positively or negatively. Moreover this association does not occur in the muscle of the type 2 diabetic patients. Using traditional tools (e.g., the well known Eisen clustering tool [START_REF] Eisen | Cluster analysis and display of genome-wide expression patterns[END_REF]), the biologist would separate these genes into two groups: one containing the over-expressed gene, and the other the down-regulated ones. However, it is well-accepted that following an external cell stimulus, transcription factors regulate positively a set of genes and at the same time, down-regulated other sets of genes. To build the regulatory networks biologists need tools like D-Miner to extract concepts containing genes regulated by the same set of transcription factors. Among the 12 genes, one has already been suspected to be linked with insulin resistance, a pathological state associated with diabetes (Hs.73957, the RAS-associated protein RAB5A [START_REF] Rome | Microarray profiling of human skeletal muscle reveals that insulin regulates 800 genes during an hyperinsulinemic clamp[END_REF]). Finally, some genes among the 12 have unknown functions because the human genome is not fully annoted. Based on the results we obtained from D-Miner we can now group these genes with other genes having common regulatory behaviors during the type 2 diabetes.

Conclusion

Computing formal concepts has been proved useful in many application domains but remains extremely hard from dense boolean data sets like the one we have to process nowadays for gene expression data analysis. We have described an original algorithm that computes concepts under monotonic constraints. First, it can be used for closed set computation and thus concept discovery. Next, for difficult contexts, i.e., dense boolean matrices where none of the dimension is small, the analyst can provide monotonic constraints on both set components of desired concepts and the D-Miner algorithm can push them into the extraction process. We are now working on the biological validation of the extracted concepts. We have also to compare D-Miner with new concept lattice construction algorithms like [START_REF] Berry | Concepts can not affor to stammer[END_REF].

• If C X ∩ A = ∅ and C Y ∩ B = ∅ then (X k-1 \ A, Y k-1 ), the left son, contains (C X , C Y )
. This left son is always generated by the algorithm. Hypothesis (1) is thus verified for rank k. Furthermore, as

C Y ∩ B = ∅ and H L k = H L k-1 ∪ (A, B), hypothesis (2)
is also verified.

• We have proved that (C X , C Y ) ⊆ (L X , L Y ). Let us now prove that (L X , L Y ) = (C X , C Y ).
In Section A.1, we have proved that each leaf is a 1-rectangle. Thus a leaf is at the same time a superset of (C X , C Y ) and a 1-rectangle and thus (C X , C Y ) = (L X , L Y ).

A.4 L ⊆ C

We have proved in Section A.1 that each leaf is a 1-rectangle. Then we have proved that each concept is associated to a leaf. We now prove that each leaf is a concept.

A leaf (L X , L Y ) is a concept if and only if ⎧ ⎨ ⎩ (L X , L Y ) is a 1-rectangle ∃x ∈ O \ L X such that ∀y ∈ L Y , (x, y) ∈ r (1) ∃y ∈ P \ L Y such that ∀x ∈ L X , (x, y) ∈ r (2)
Let us now prove by contradiction Property (1) and then Property (2).

• Assume that it exists x ∈ O \ L X such that ∀y ∈ L Y , (x, y) ∈ r. Let (x, B) be an element of H. This 0-rectangle exists because either x is in relation with all the elements of P and, in that case, it leads to a contradiction because if x ∈ H then all the tree nodes contains x while we assume x ∈ L X .

or, it exists B ⊆ P such that ∀y ∈ B, (x, y) ∈ r. (x, B) is, in this case, unique given the computation of H.

Let (A X , A Y ) be the ancestor of (L X , L Y ) before being cut by (x, B). (L X , L Y ) has to be a descendant of (A X \ x, A Y ) which is the left son of (A X , A Y ). This is due to the fact that x ∈ L X (see Figure 14). By the construction of the tree, the left son of (A X , A Y ) contains B but, by hypothesis (∀y ∈ L Y , (x, y) ∈ r), L Y does not contain B. To get that one of the descendants of (A X \ x, A Y ) does not contain any element of B, it is needed that one of these descendants is a right son of another one. Let us denote by (A , B ) the 0-rectangle which leads to a right son without elements from B. To enable this cutting, it is needed that B ∩ B = ∅. Consequently, each descendant contains at least an element of B and it contradicts the fact that L Y ∩ B = ∅.

• Let us assume that it exists y ∈ P \ L Y such that ∀z ∈ L X , (z, y) ∈ r. Let (A X 1 , A Y 1 ) and (A X 2 , A Y 2 ) be two ancestors of (L X , L Y ) such that (A X 1 , A Y 1 )

(A X 1 , A Y 1 ), y ∈ A Y 1 (x, B), y ∈ B (A X 2 , A Y 2 ) (• • • ) (• • • ) (L X , L Y ), x ∈ L X

B Experimentations on synthetic data sets

We have discussed in Section 3.3 our complementary experimental validation of D-Miner on several artificial data sets. We generated 60 dense data sets by varying the number of columns (300, 700 and 900 columns), the number of lines (100 and 300 lines) and the density of "1" values (15 % and 35 %). For each combination of parameters, we generated 5 data sets. Table 2 (resp. Table 3 provides the mean (column mean) and the standard deviation (column sd) of execution time (in seconds) used by each algorithm on the 5 data sets with 15% density (resp. 35% density). The parameter σ denotes the used frequency threshold. For each data set and each value of σ, we also report the number of frequent concepts (line FrC).

Figure 1 :

 1 Figure 1: Example of a boolean context r 1

r 1 ). Definition 3 (Definition 4 (

 34 Constraints on frequencies) Given a set of items G ⊆ P and a frequency threshold γ, the minimal frequency constraint is denoted C minfreq (r, γ, G) ≡ |ψ(G, r)| ≥ γ. The maximal frequency w.r.t. a threshold γ is C maxfreq (r, γ , G) ≡ |ψ(G, r)| ≤ γ . These constraints can be defined easily on sets of objects as well: C minfreq (r, γ, T ) ≡ |φ(T, r)| ≥ γ and C maxfreq (r, γ , T ) ≡ |φ(T, r)| ≤ γ . Closed set and C Close constraint) A set of items G ⊆ P is closed when it satisfies constraint C Close in r and C Close (G, r) ≡ h(G, r) = G. Dually, for sets of objects T ⊆ O, we have C Close (T, r) ≡ h (T, r) = T .

Figure 3 :

 3 Figure 3: Concept construction on r 3 (Example 5)

1 Figure 4 :

 14 Figure 4: Building a non maximal 1-rectangle

  First, (X, Y ) must have an non empty intersection with H[i]. If it is not the case, cutting is called with the next cutter. Before cutting (X, Y ) into (X\a, Y ), we have to check the monotonic constraint on X\a (i.e., C t (X\a)) to try to prune the search space. (a, b) is inserted into H L , the set of cutters in the left cutting. Then cutting is called on (X\a, Y ) and (a, b) is removed from H L . For the Algorithm 1: D-Miner Input : Relation r with n objects and m items, O the set of objects, P the set of items, C t and C g are monotonic constraints on O and P. Output : Q the set of concepts that satisfy C t and C g H L ← empty() H is computed from r Q ← cutting((O, P), H, 0, H L ) Algorithm 2: cutting Input: (X, Y ) a couple of 2 O × 2 P , H the list of cutters, i the depth of the iteration, H L a set of precedent cutters in left cuttings, C t a monotonic constraint on O, C g a monotonic constraint on P. Output: Q the set of concepts that satisfy C t and C

Figure 5 :Figure 6 : Connect4 4 An application to microarray data analysis 4 . 1

 56441 Figure 5: Mushroom

Figure 8 :

 8 Figure 8: Example of boolean microarray data r 4

Figure 9 :

 9 Figure 9: Transcription factors for r 4

Figure 11 :

 11 Figure 11: Extended microarray data analysis

Figure 12 :

 12 Figure 12: Number of concepts w.r.t. the minimum number of genes γ for |T D | ≥ 4

Figure 13 :

 13 Figure 13: Extended microarray data analysis (2)

Figure 15 :

 15 Figure 15: Secondillustration: x ∈ L X ∧ (x, y) ∈ r ⇒ ¬ (∀x ∈ L X , (x, y) ∈ r)

Table 1 :

 1 Contexts r 2 for Example 4 (left) and r 3 for Examples 5 and 6 (right

Table 2 :

 2

Execution time on data sets with 15% of density (-iff time ≥ 10 min)

A preliminary version of this paper has introduced D-Miner in[START_REF] Besson | Constraint-based mining of formal concepts in transactional data[END_REF].

http://miles.cnuce.cnr.it/ palmeri/datam/DCI/datasets.php

Acknowledgment The authors thank Mohammed Zaki who has kindly provided his CHARM implementation. Jérémy Besson is funded by INRA. This work has been partially funded by the EU contract cInQ IST-2000-26469 (FET arm of the IST programme).

A Proofs

We first prove that all tree leaves are different from each other in Section A.2. Thus the leaves can be considered as a set denoted by L. In a second step we prove that L is equal to the collection of concepts denoted by C:

• We prove in Section A.3 that C ⊆ L • We prove in Section A.4 that L ⊆ C Section A.1 is a preliminary step to facilitate these proofs.

A.1 All tree leaves are 1-rectangles

Let (L X , L Y ) be a D-Miner tree leaf. Let us demonstrate that ∀i ∈ L X , ∀j ∈ L Y , (i, j) ∈ r. We suppose first the contrary, that is, it exists i ∈ L X and j ∈ L Y such that (i, j) ∈ r. Thus, following definition of H, it exists (A, B) ∈ H such that i ∈ A and j ∈ B. By definition of the algorithm, each element of H is used on the path from the root to each tree leaf. Let (A X , A Y ) be the ancestor of (L X , L Y ) cut by (A, B). The order relation implies that

A.2 All tree leaves are different

Let (L X 1 , L Y 1 ) and (L X 2 , L Y 2 ) be two D-Miner tree leaves. Let (A X , A Y ) be the smallest common ancestor of these two leaves and (A, B) be the H element used to cut it. We suppose, without loss of generality, that (L X 1 , L Y 1 ) is the left son of (A X , A Y ) and that (L X 2 , L Y 2 ) is its right son. By definition of the algorithm, each of the left successors of (A X , A Y ) does not contain elements of A thus

Each of the right successors of (A X , A Y ) contains all elements of A and thus

A.3 C ⊆ L

Let us demonstrate that for each concept (C X , C Y ), there exists a path from the root node (O, P) to this concept:

• In a first step we recursively demonstrate that the path is such that:

We denote by H L k (X k , Y k ) the set of elements of H which leads to a left branch on the path from (X 0 , Y 0 ) to (X k , Y k ). The recurrence hypotheses are the following:

Base By definition of formal concepts, each concept (C X , C Y ) is included in the root node, i.e., C X ⊆ X 0 and C Y ⊆ Y 0 . Hypothesis (1) is thus verified for rank 0. Furthermore, H L 0 = ∅ and thus hypothesis (2) is verified for rank 0 as well.

Induction Let us suppose that hypotheses (1) and ( 2) are verified for rank k -1 and let us prove that they are still true at rank k when the node

) and 1) and ( 2). * Otherwise, given the definition of formal concepts, only one of the two following conditions is verified:

This son is generated by the algorithm because hypothesis ( 2) is verified for the rank k -1.

)), and thus hypothesis (1) is verified.

is the father of (A X 2 , A Y 2 ), y ∈ A Y 1 and y ∈ A Y 2 . We denote by (x, B) the 0-rectangle which is used to cut (A X 1 , A Y 1 ) (see Figure 15). Given the algorithm principle, these two ancestors exist and (

By construction of H, x belongs only to one element of H.

) and all its descendants also contain x. Nevertheless, we have proved that

The hypothesis ∀z ∈ L X , (z, y) ∈ r is contradicted by the fact that (x, y) ∈ r (x and y belong to the same 0-rectangle).