Esther Galbrun
email: esther.galbrun@cs.helsinki.fi.

Pauli Miettinen
email: pmiettin@mpi-inf.mpg.de.

From Black and White to Full Colour: Extending Redescription Mining Outside the Boolean World *

Redescription mining is a powerful data analysis tool that is used to find multiple descriptions of the same entities. Consider geographical regions as an example. They can be characterized by the fauna that inhabits them on one hand and by their meteorological conditions on the other hand. Finding such redescriptors, a task known as niche-finding, is of much importance in biology.

Current redescription mining methods cannot handle other than Boolean data. This restricts the range of possible applications or makes discretization a prerequisite, entailing a possibly harmful loss of information. In niche-finding, while the fauna can be naturally represented using a Boolean presence/absence data, the weather cannot.

In this paper, we extend redescription mining to categorical and real-valued data with possibly missing values using a surprisingly simple and efficient approach. We provide extensive experimental evaluation to study the behaviour of the proposed algorithm. Furthermore, we show the statistical significance of our results using recent innovations on randomization methods.

Introduction

Finding multiple ways to characterize the same entities is a problem that appears in many areas of science. In medical sciences, for example, one typically wants to find a subset of patients sharing similar symptoms and similar genes. In biology, the bioclimatic constraints that must be met for a certain species to survive constitute that species' bioclimatic envelope (or niche 1 ), and finding such envelopes can help, e.g. to predict the results of global warming [START_REF] Pearson | Predicting the impacts of climate change on the distribution of species: Are bioclimate envelope models useful?[END_REF].

But this process is only semi-automatic. For instance, to find the bioclimatic envelopes, an expert first selects a species and then uses some method to find the envelope for this particular species. More complex combinations of species, or even any combinations at all, are rarely studied, as manually iterating over all possible combinations would be far too laborious.

It is here where redescription mining comes to help. In redescription mining the input contains entities with two sets of characterizing variables. The task is to find a pair of queries, one query made by combining literals with Boolean operators. A query over V is a Boolean formula with literals of V . A redescription R of D = (V L , V R , E, D L , D R ) is a pair of queries (q L , q R ) over V L and V R , respectively. For a redescription R = (q L , q R ), we use V L (R) to denote the variables of q L ; V R (R) is defined analogously.

The support of a query q on D, supp D (q), is a set {e ∈ E : q is true for e}. The support of a redescription R = (q L , q R ), supp D (q L , q R ), is the intersection of supports of q L and q R , supp(q L , q R ) = supp(q L ) ∩ supp(q R ). We will omit the subscripts when they are clear from the context.

A redescription R = (q L , q R ) is exact if and only if supp(q L ) = supp(q R ). If a redescription is not exact, it is approximate. The accuracy of a redescription R = (q L , q R ) is measured using the Jaccard coefficient

J(R) = J(q L , q R ) = |supp(q L , q R )| |supp(q L ) ∪ supp(q R )| .
Formally, redescription mining is defined as follows:

Problem 1. (Redescription Mining) Given data D = (V L , V R , E, D L , D R ) and a set of constraints C, find all redescriptions R 1 , R 2 , . . . of D that satisfy constraints in C.

We leave open the exact constraints in C for a while and will turn back to it in Subsection 5.1. The formulation of redescription mining above assumes that the describing variables are partitioned into two sets, V L and V R , and looks for a pairs of queries over these two sets, respectively. Formulations of redescription mining exist that do not include this requirement. Typically, they consider a single set of describing variables and search for pairs of queries, with the constraint that the two subsets of variables appearing in the queries of any pair be disjoint. The methods presented in this paper can be naturally adapted to that alternative formulation.

Our proposed methods could also be adapted to handle multiple data sets, i.e. settings with more than two sets of variables: V A , V B , . . . , V N , where one looks for tuples of queries (q A , q B , . . . , q N ) over the different sets of variables, respectively.

3 Related Work 3.1 Rule discovery. A characterizing property of redescription mining is its 'many views' approach, that is, it deals with entities that can be explained using different sets of variables. This approach, however, is not unique to redescription mining.

One of the most traditional 'many views' approaches is classification, though it is not typically considered as such. There the data gives one characterization of the entities and the class another. Mining a single query can be considered as a classification task. Fixing one query at a time gives us binary class labels and we try to find a good classifier to it.

Logical Analysis of Data (LAD) [START_REF] Boros | An implementation of logical analysis of data[END_REF] is a particular example among classification approaches in the presence of Boolean attributes and target. It aims at finding a perfect classifier of fixed form, e.g. a horn clause, a DNF, a CNF, or linear or quadratic Boolean formula.

Closer to the idea of redescription mining is Multi-label Classification [START_REF] Tsoumakas | Mining multi-label data[END_REF], where the goal is to learn classifiers for conjunctions of labels. Perhaps the main difference to redescription mining is this restriction to conjunctions of classes. There is also a big difference in the goals: redescription mining is descriptive while Multi-label Classification is predictive.

The common aim of mining Emerging Patterns, Constrast Set Mining and Subgroup Discovery is to find queries whose support is distributed very unevenly with respect to the target attribute.

Emerging Patterns [START_REF] Novak | Supervised descriptive rule discovery: A unifying survey of contrast set, emerging pattern and subgroup mining[END_REF] is targeted at Boolean data and uses monotone conjunctive queries, i.e. itemsets. The purpose is to find itemsets whose presence is statistically dependent on the positive or negative labelling of the objects. In the extreme case, the itemset would be present only in the positive example and would form a perfect classifier for the data at hand. However, this is not generally the case.

Contrast Set Mining [START_REF] Novak | Supervised descriptive rule discovery: A unifying survey of contrast set, emerging pattern and subgroup mining[END_REF] can be used with a nominal target attribute to identify a monotone conjunctive query that best discriminates between the objects from one class and the rest of the objects.

Subgroup Discovery [START_REF] Umek | Subgroup discovery in data sets with multi-dimensional responses: A method and a case study in traumatology[END_REF] aims in a more general sense at finding a query such that the objects in the defined subgroup have atypical values for a target attribute, possibly ordinal or numerical, compared to other objects. This is extended to several target attributes in Exceptional Model mining. In that framework, defined by Leman et al. [START_REF] Leman | Exceptional model mining[END_REF], and in its recent instance [START_REF] Van Leeuwen | Maximal exceptions with minimal descriptions[END_REF], one considers a model defined over the target attributes and tries to identify a subgroup of objects where the fitted model differs significantly from the model fitted to the rest of the data.

A related approach is presented by Garriga, Heikinheimo and Seppänen [START_REF] Garriga | Cross-mining binary and numerical attributes[END_REF]. It uses frequent itemsets on the binary attributes to form a partition of the original entities such that for each subset it is possible to construct a specific model that fits well on the numerical attributes. In other words, this approach tries to partition the original data into subgroups.

Redescription mining differs from the above techniques in that it aims at simultaneously finding multiple descriptions of a subset of entities which is not previously specified, selecting the few relevant among a potentially large set of variables. In contrast to these methods, it does not have a set of describing features and target attributes but rather several sets of describing variables. Yet, when there are two sets of describing attributes and a chosen query language, we can define a one-directional redescription problem. Queries can be built over one set of attributes, defining subgroups whose quality is measured in terms of how exactly and concisely they can be described by queries over the other set of attributes. In a sense, this can be loosely understood as a case of Exceptional Model Mining where the model is the chosen query language and fitting the model to a subgroup corresponds to finding as concise and exact a query for it over the target attributes as possible. The aim of redescription mining is then to solve this problem in both directions simultaneously.

Redescription mining was introduced in [START_REF] Ramakrishnan | Turning CARTwheels: An alternating algorithm for mining redescriptions[END_REF], and has since attained continuous research interest (e.g. [START_REF] Parida | Redescription mining: Structure theory and algorithms[END_REF][START_REF] Zaki | Reasoning about sets using redescription mining[END_REF][START_REF] Gallo | Finding subgroups having several descriptions: Algorithms for redescription mining[END_REF][START_REF] Kumar | Redescription mining: Algorithms and applications in bioinformatics[END_REF]). The approches proposed for redescription mining have been based on various ideas, including decision trees [START_REF] Ramakrishnan | Turning CARTwheels: An alternating algorithm for mining redescriptions[END_REF][START_REF] Kumar | Redescription mining: Algorithms and applications in bioinformatics[END_REF], Karnaugh maps [START_REF] Zaki | Reasoning about sets using redescription mining[END_REF], co-clusters [START_REF] Parida | Redescription mining: Structure theory and algorithms[END_REF] and frequent itemsets [START_REF] Zaki | Reasoning about sets using redescription mining[END_REF][START_REF] Gallo | Finding subgroups having several descriptions: Algorithms for redescription mining[END_REF].

The CARTwheels algorithm [START_REF] Ramakrishnan | Turning CARTwheels: An alternating algorithm for mining redescriptions[END_REF] is an alternating method that uses decision trees. One side of the redescription is fixed, giving binary labels for the entities and a decision tree over the other variables, that is, a good classifier with respect to those labels, is constructed. At the next step, the labelling given by this decision tree is considered as the target and a new decision tree is built on the other set of variables. The branches of the two trees that correspond to positive labels form a pair of queries that can be considered as a redescription, as well as the pair of queries associated to the negative branches. This construction based on decision trees gives the redescriptions an atypical form. Consider the example of a tree of depth two, with the first level branching variable A and the second level branching variables B and C. Then, (A ∧ B) ∨ (¬A ∧ C) is a good example of query obtained by joining branches of such a tree. The fact that the same variable occurs multiple times with and without negation can make the query difficult to interpret.

Gallo et al. [START_REF] Gallo | Finding subgroups having several descriptions: Algorithms for redescription mining[END_REF] propose two approaches to redescription mining. The first one is based on mining frequent itemsets from both data sets separately and combining them together. The second one is a greedy method that forms the basis of our work. We will therefore come back to it in more details.

A natural extension of redescription mining is storytelling [START_REF] Parida | Redescription mining: Structure theory and algorithms[END_REF], where the aim is to find consecutive redescriptors. That is, given data D = (V L , V R , E, D L , D R ), the goal is to find queries q 1 L , q 1 R , q2 L , q 2 R , . . . such that consecutive pairs of queries (q 1 L , q 1 R ), (q 1 R , q 2 L ), (q 2 L , q 2 R ), . . . all form a valid non-exact redescription. We will not cover storytelling in this paper.

3.2 Data discretization. Generalizing algorithms based on Boolean attributes to real-valued data has been a recurrent problem in data mining. Most solutions are based on some sort of preprocessing: typically categorical data is represented using one variable per category, and quantative data is turned into categorical data using some type of bucketing.

When labels are available on the original data, as is the case for Subgroup Discovery with a single output feature, a supervised discretisation method can be devised for the problem at hand. In the method proposed by Grosskreutz and Rüping [START_REF] Grosskreutz | On subgroup discovery in numerical domains[END_REF], the discretization happens within the algorithm and relies on a property of the function measuring subgroup quality to merge basic intervals in a bottom-up fashion. Yet, the end points for the basic intervals are determined as a pre-processing step in a way that is not necessarily optimal with respect to their later use.

In most settings, though, no labelling of the data is available and one has to resort to unsupervised discretization. This approach raises several questions, from the choice of the number of buckets to the size of the resulting data. A more elegant approach was provided by Srikant and Agrawal [START_REF] Srikant | Mining quantitative association rules in large relational tables[END_REF], who presented a machinery that solves most of the problems automatically. Their method is still based on a priori bucketing, and moreover, it is very specific to association rule mining, making it hard (or impossible) to apply to redescription mining.

The problem of on-the-fly discretization during a classification task was studied by Fayyad and Irani [START_REF] Fayyad | Multi-interval discretization of continuous-valued attributes for classification learning[END_REF]. Although the task is different, the results we obtained for dynamically choosing the most accurate extension shares similarities with their result.

Using redescription mining algorithms with non-Boolean data is not a new idea. Already in [START_REF] Ramakrishnan | Turning CARTwheels: An alternating algorithm for mining redescriptions[END_REF], the CARTwheels algorithm was used to mine bioinformatics data that was non-Boolean. As the algorithm requires Boolean input, the data had to be bucketed as a pre-processing step. But pre-processing typically requires considerable domain knowledge and might still be impossible or yield exponential growth in the number of variables. This is in contrast to our algorithm, where the optimal discretization is determined at each iteration within the algorithm, requiring no pre-processing. Nothing, of course, prevents users to pre-process their data, should that be needed.

Niche finding.

In biology, the problem of finding species' bioclimatic envelope is a rather new one (see, e.g. [START_REF] Soberón | Niches and distributional areas: Concepts, methods, and assumptions[END_REF] and references therein), but the idea of ecological niches dates back to the early 20th century [START_REF] Grinnell | The niche-relationships of the California Thrasher[END_REF]. There is also some level of ambiguity in what exactly is meant by the term niche [START_REF] Soberón | Niches and distributional areas: Concepts, methods, and assumptions[END_REF]. In this paper we consider a bioclimatic envelope of a (group of) species to be a set of limits in climate variables (such as monthly mean temperature) that defines the region occupied by the species 2 .

Despite the vague definition, the past ten years have seen a number of methods to model the bioclimatic envelopes. The methods are based, for example, on regression, neural networks, and genetic algorithms (see [START_REF] Soberón | Interpretation of models of fundamental ecological niches and species distributional areas[END_REF]). But to the best of the authors' knowledge, none of these methods allows automatically finding both the set of species and their envelope.

Other niche finding tasks have been formulated, for example, in a linguistic context [START_REF] Pericliev | Differentiating 451 languages in terms of their segment inventories[END_REF]. In this paper we only consider the biological problem.

In this section, we present the core of our algorithm. Various extensions to it, such as handling missing values, are presented in the next section.

4.1 Motivation and background. The redescription mining problem is defined for general Boolean queries, yet none of the proposed algorithms explores the full search space (using instead decision trees of fixed depth [START_REF] Ramakrishnan | Turning CARTwheels: An alternating algorithm for mining redescriptions[END_REF], monotone CNF and DNF formulae [START_REF] Parida | Redescription mining: Structure theory and algorithms[END_REF], or only (possibly negated) conjunctions [START_REF] Zaki | Reasoning about sets using redescription mining[END_REF]). Such restrictions are easy to understand, given the huge search space formed by all Boolean formulae (2 2 n distinct formulae can be defined over n variables). With non-Boolean data the search space is even more overwhelming. It is therefore evident that when devising an algorithm usable with real-world data, the space of all Boolean functions cannot be considered in its entireness.

Type of Boolean queries mined. How to restrict the search space? This question can be considered from at least three different perspectives: the expressive power of the resulting queries, the ease of finding them, and their interpretability. For example, monotone conjunctive queries (i.e. frequent item sets) are easy to interpret and relatively easy to find, given the monotonicity of the search space, but they lack expressive power. On the other hand, general Boolean queries have a high expressivity, but are hard to find. Furthermore, deeply nested structures and variables appearing multiple times can lead to difficulties in interpreting them.

Our aim is to restrict the search to queries that provide a good compromise between the three aforementioned properties. For this purpose, we follow the approach taken by Gallo, Miettinen and Mannila [START_REF] Gallo | Finding subgroups having several descriptions: Algorithms for redescription mining[END_REF]. First, we evaluate the queries from left to right irrelevant of the operator precedence. In other words, we only consider queries that can be parsed in linear order, without trees. For example, (a ∨ b) ∧ ¬c is such a query, but (a ∧ b) ∨ (c ∧ d) is not. Second, we allow every variable to appear only once. Queries of this type are strict generalizations of purely conjunctive or disjunctive queries, save the tautological cases a ∧ ¬a and a ∨ ¬a. We consider such queries to be relatively easy to interpret while still having a satisfying expressive power. While becoming smaller, the search space still remains exponential. Therefore, we also employ a heuristic pruning, as will be explained later.

On-the-fly bucketing versus pre-processing. Binning the variables into buckets is a standard pre-processing technique to make non-Boolean data Boolean (see Section 3.2). But it has its drawbacks. For example, the resulting data has a special structure, with all variables corresponding to different buckets of a given non-Boolean variable being mutually disjoint. The algorithms are typically not adjusted to this property.

Moreover, the bucketing must be made in a pre-processing step, and cannot be modified by the algorithm later on. If the quality of the bucketing was poor, so will be the results. But the user typically does not know whether a certain bucketing yields good results before running the algorithm, so repeated trials and errors are needed to achieve satisfactory results.

Our approach of doing the bucketing on-the-fly avoids these problems. The algorithm will select the optimal bucket for each case when necessary. This removes the need of pre-processing and repeated trials. Furthermore, our algorithm can use different buckets for the same variable in different redescriptions, should that yield better results.

4.2 Outline of the algorithm. We use a strategy similar to beam-search to explore the solution space. The basic idea is to construct queries bottom-up, starting from singleton redescriptions (i.e. both queries contain only one literal) and progressively extending them by appending operators and literals. For example, we could start with a pair (a, ¬b), and try to extend it to (a ∧ c, ¬b),

Input: Data D = (V L , V R , E, D L , D R ),
F L (S), F L (S) ← free variables for S 6: if F L (S) = ∅ or F R (S) = ∅ then 7: E ← {S} 8: while E = ∅ do 9:
for each R ∈ E do if R can be extended on side s with operator • and literal l ∈ Fs(R) then K ← {ki best redescriptions from K, with updated free variables.} 14:

E ← {R ∈ K : F L (R) = ∅ or F R (R) = ∅} 15: R ← R ∪ K 16: Filter R with constraints C 17: return R Figure 1: ReReMi: Mine data sets for redescriptions (a ∨ c, ¬b), (a ∧ ¬c, ¬b), etc.
After evaluating all possible one-step extensions, we select the best candidates and extend them in turn. This process requires a book-keeping procedure to avoid repeatedly generating the same queries, as we will explain below. When no new redescription can be generated, we move to the next initial pair. The outline of the algorithm, called ReReMi, is given in Figure 1.

Our algorithm shares similarites with the Greedy algorithm presented by Gallo et al. [START_REF] Gallo | Finding subgroups having several descriptions: Algorithms for redescription mining[END_REF]. But unlike Gallo et al., and following the idea of beam-search, we allow several extensions to be generated from a given redescription in each step. In this way we can explore the search space more extensively. Notice also our algorithm's resemblance to bottom-up frequent itemset mining algorithms. Indeed, finding redescriptions can be seen as a generalization of association rule mining [START_REF] Zaki | Reasoning about sets using redescription mining[END_REF], although without the monotonicity property.

Efficient computation of the accuracy for Boolean variables.

Given two queries, q A and q B , to decide which of the possible extensions of q A yields the best redescription, we need to compute the accuracy (i.e. Jaccard coefficient) for four different types of extensions for each Boolean variable v: J(q A ∧ v, q B ), J(q A ∧ ¬v, q B ), J(q A ∨ v, q B ) and J(q A ∨ ¬v, q B ). Doing this in a straight forward way, determining a single Jaccard coefficient requires the computation of three distinct supports over the data. But this is not necessary. To compute J(q A ∧ v, q B ), we need consider only the rows in supp(q A ) -others will never be in supp(q A ∧ v). On the other hand, rows in supp(q A ) will be in supp(q A ∨ v) in any case and can be omitted when computing J(q A ∨ v, q B ). Let us formalize this intuition.

Let E 1,0 be the set of entities for which only the first query holds (i.e. E 1,0 = supp(q A )supp(q B )), E 0,1 those for which only the second query holds, E 1,1 those for which both queries hold, and E 0,0 those for which neither of the queries hold. Finally, these sets restricted to supp(v) are denoted as E x,y (v) (e.g. E 1,0 (v) = E 1,0 ∩ supp(v)). The same notation is also used with real-valued variables and Iverson notation, as in It is well known that the Jaccard coefficient J(q A , q B ) can be expressed as

E 1,0 ([λ ≤ v ≤ ρ]). J(q A ∧ v, q B ) = |E 1,1 (v)| |E 1,0 (v)| + |E 0,1 | + |E 1,1 | J(q A ∧ ¬v, q B ) = |E 1,1 | -|E 1,1 (v)| |E 1,0 | -|E 1,0 (v)| + |E 0,1 | + |E 1,1 | J(q A ∨ v, q B ) = |E 1,1 | + |E 0,1 (v)| |E 1,0 | + |E 0,1 | + |E 1,1 | + |E 0,0 (v)| J(q A ∨ ¬v, q B ) = |E 1,1 | + |E 0,1 | -|E 0,1 (v)| |E 1,0 | + |E 0,1 | + |E 1,1 | + |E 0,0 | -|E 0,0 (v)|
(4.1) J(q A , q B ) = |E 1,1 | |E 1,0 | + |E 0,1 | + |E 1,1 |
.

Similarly, we can write J(q A ∧v,

q B ) = |E 1,1 (v)| /(|E 1,0 (v)|+|E 0,1 |+|E 1,1 |).
Analogous formulae can be derived for all different extensions (see Figure 2).

Notice that E 1,0 , E 0,1 , and E 1,1 can be computed once for a given redescription. Then, for each candidate variable, it is enough to perform three intersection operations to obtain E 1,0 (v), E 0,1 (v), and E 1,1 (v). Furthermore, E 0,0 and E 0,0 (v) can be deduced from supp(v) and E, and we do not have to consider the rows in which neither q A nor q B hold. This observation can significantly speed up the algorithm.

Adding categorical variables.

Handling the categorical variables is rather straight forward. We consider only the relation v = c, where c is the label. The above computation of Jaccard applies, as we can write, for example,

J(q A ∧ [v = c], q B ) = |E 1,1 ([v = c])| |E 1,0 ([v = c])| + |E 0,1 | + |E 1,1 | .
What is different to the Boolean case is that we must select the class label c. But this we can do easily by trying all class labels and selecting the one that improves the Jaccard most. Naturally we can use the aforementioned speedup techniques for Jaccard when selecting the label, as each label just defines different Boolean vector.

Extension to real-valued variables.

With the real-valued data, our approach is to do bucketing on-the-fly, finding the optimal bucket to add in every step. Assume that our algorithm tries to extend, say, query q A of redescription (q A , q B ) with a real-valued variable v. The algorithm considers the extended query q A ∧[λ ≤ v ≤ ρ] for different thresholds λ and ρ and selects those that maximize the accuracy of the extension. Naturally, the optimal λ and ρ are different for different extensions. The two thresholds are set simultaneously since setting one bound first and possibly the other later would prevent the greedy search from finding some of the most specific intervals.

How can we find λ and ρ efficiently? To tackle this question, we adapt our approach from the previous section, using a result similar to that of Fayyad and Irani [START_REF] Fayyad | Multi-interval discretization of continuous-valued attributes for classification learning[END_REF].

We consider only the shortest interval yielding any truth value assignment: only values in D(E, v), i.e. values taken by the variable v, can be interval bounds. We could try all possibilities, but if the data contains n entities, this can require n 2 time, quickly becoming infeasible since we have to compute the accuracies for each candidate extension. However, as for the Boolean case, only two subsets of entities for each type of extension can impact the Jaccard coefficient: those in E 1,1 and E 1,0 for conjunctions and those in E 0,1 and E 0,0 for disjunctions. Furthermore, only values separating entities from the two sets need to be considered.

• • •• • • • • • • • • • •• •• • • • • • • •• • v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 v 10 v 11
Definition 4.1. When extending a redescription with a numerical variable v, we say that value u is a lower cut point if for any fixed value w larger than u, [u, w] is the shortest interval yielding a locally optimal support for the extension. Equivalently, we say that w is an upper cut point if for any fixed value u smaller than w, [u, w] is the shortest interval yielding a locally optimal support for the extension. In addition, -∞ and +∞ can be lower and upper cut points, respectively. Example. Consider the example of extending a redescription (q A , q B ) by appending a variable v with a non-negated conjunction. The bins in Figure 3 represent the values taken by the variable, sorted in increasing order. Black circles stand for entities belonging to E 1,1 , white circles for entities from E 1,0 . Our aim is to find bounds λ and ρ that maximize

(4.2) j(λ, ρ) = |E 1,1 ([λ ≤ v ≤ ρ])| |E 1,0 ([λ ≤ v ≤ ρ])| + |E 0,1 | + |E 1,1 | .
In this example, there is one entity in E 1,1 with value v 4 , but none in E 1,0 with value v 3 . Therefore v 4 cannot be an optimal choice for λ since choosing v 3 instead would always increase the accuracy. For the same reason, -∞, v 2 , v 3 , v 7 , v 10 , and v 11 are lower cut points, as only these values can be an optimal choice for λ here. Similarily, v 1 , v 2 , v 5 and v 7 are upper cut points.

To improve the speed of computing optimal extensions, we need to identify lower and upper cut points efficiently. To that end, we present succinct characterisations of the cut points for different types of extensions. We use (v 1 , v 2 , . . . , v k ) to denote the values taken by the variable v for entities in E 1,1 or E 1,0 , that is, values in D(E 1,0 ∪ E 1,0 , v), sorted in increasing order. Similarly, the values in D(E 0,0 ∪ E 0,1 , v) ordered increasingly are denoted as (v 1 , v 2 , . . . , v l ). Proposition 4.1. For a non-negated conjunction, a lower cut point is a value v i such that

v i ∈ D(E 1,1 , v) and v i-1 ∈ D(E 1,0 , v), or -∞ if i = 1 and v i ∈ D(E 1,1 , v). An upper cut point is a value v j such that v j ∈ D(E 1,1 , v) and v j+1 ∈ D(E 1,0 , v), or +∞ if j = k and v j ∈ D(E 1,1 , v).
For a negated conjunction, a lower cut point is a value

v i such that v i ∈ D(E 1,0 , v) and v i-1 ∈ D(E 1,1 , v), or -∞ if i = 1 and v i ∈ D(E 1,0 , v). An upper cut point is a value v j such that v j ∈ D(E 1,0 , v) and v j+1 ∈ D(E 1,1 , v), or +∞ if j = k and v j ∈ D(E 1,0 , v).
For a non-negated disjunction, a lower cut point is a value

v i such that v i ∈ D(E 0,1 , v) and v i-1 ∈ D(E 0,0 , v), or -∞ if i = 1 and v i ∈ D(E 0,1 , v). An upper cut point is a value v j such that v j ∈ D(E 0,1 , v) and v j+1 ∈ D(E 0,0 , v), or +∞ if j = l and v j ∈ D(E 0,1 , v).
For a negated disjunction, a lower cut point is a value

v i such that v i ∈ D(E 0,0 , v) and v i-1 ∈ D(E 0,1 , v), or -∞ if i = 1 and v i ∈ D(E 0,0 , v). An upper cut point is a value v j such that v j ∈ D(E 0,0 , v) and v j+1 ∈ D(E 0,1 , v), or +∞ if j = l and v j ∈ D(E 0,0 , v).
Proof. We concentrate on the case of non-negated conjunction; other cases are similar. The aim is to maximize j(λ, ρ) (cf. Equation 4.2). We start with the lower bound λ. First, suppose v i ∈ D(E 1,1 , v). Then v i must occur in E 1,0 and we have

|E 1,0 ([v i ≤ v ≤ ρ])| > |E 1,0 ([v i+1 ≤ v ≤ ρ])| while |E 1,1 ([v i ≤ v ≤ ρ])| = |E 1,1 ([v i+1 ≤ v ≤ ρ])|. Hence, j(v i , ρ) < j(v i+1 , ρ)
. So v i is not an optimal value for λ. Second, if v i-1 ∈ D(E 1,0 , v), following a similar reasoning, we notice that j(v i-1 , ρ) > j(v i , ρ) and v i is not an optimal value for λ. Finally, in case v 1 ∈ D(E 1,1 , v), setting λ = v 1 can be optimal and we simply leave the lower bound undefined, i.e. we use the half-line (-∞, ρ] that yields the same support.

The case of the upper bound ρ is analogous.

If v i ∈ D(E 1,1 , v), then v i ∈ D(E 1,0 , v) and we have |E 1,0 ([λ ≤ v ≤ v i-1 ])| < |E 1,0 ([λ ≤ v ≤ v i ])| while |E 1,1 ([λ ≤ v ≤ v i-1 ])| = |E 1,1 ([λ ≤ v ≤ v i ])|.
Hence, j(λ, v i-1 ) > j(λ, v i ) and v i is not an optimal value for ρ. On the other hand, if v i+1 ∈ D(E 1,0 , v) then j(λ, v i-1 ) > j(λ, v i ) and v i is not an optimal value for ρ. Finally, when v k occurs in E 1,1 for the last index k, setting ρ = v k can be optimal and we use the half-line [λ, +∞) which is equivalent with respect to the support.

The case of negated conjunctions is the reverse of this. Again, we only need to consider entities in E 1,0 or in E 1,1 , but this time we will try to find an interval [λ

≤ v ≤ ρ] such that the set |E 1,0 ([λ ≤ v ≤ ρ])| is large while |E 1,1 ([λ ≤ v ≤ ρ])| is small, so as to maximize (4.3) j(λ, ρ) = |E 1,1 | -|E 1,1 ([λ ≤ v ≤ ρ])| |E 1,0 | -|E 1,0 ([λ ≤ v ≤ ρ])| + |E 0,1 | + |E 1,1 | .
The case of disjunctions is very similar to conjunctions, but focusing on entities in E 0,1 and E 0,0 instead of E 1,1 and E 1,0 , respectively.

For non-negated disjunctions the aim is to maximize

(4.4) j(λ, ρ) = |E 1,1 | + |E 0,1 ([λ ≤ v ≤ ρ])| |E 1,0 | + |E 0,1 | + |E 1,1 | + |E 0,0 ([λ ≤ v ≤ ρ])| ,
that is, we try to maximize the number of entities in E 0,1 while minimizing that in E 0,0 . The aim for negated disjunctions is to maximize

(4.5) j(λ, ρ) = |E 1,1 | + |E 0,1 | -|E 0,1 ([λ ≤ v ≤ ρ])| |E| -|E 0,0 ([λ ≤ v ≤ ρ])| ,
the reverse of the non-negated case, similarly to conjunctions.

To search for an optimal bucket for variable v, we only need to consider upper and lower cut points. Denoting by n λ the number of lower cut points and by n ρ the number of upper cut points, the size of the search space is (n λ + 1)(n ρ + 1). In many cases, this is considerably smaller than the naïve n 2 (but see Section 5.2 for a method to deal with large (n λ + 1)(n ρ + 1)).

4.6

Putting it all together: The ReReMi algorithm. As we mentioned previously, the algorithm starts by evaluating all possible pairs of singleton redescriptions (i.e. literals) and keeps only the k p best pairs (line 2). Alternatively, it is possible to extend all pairs with accuracy higher than some threshold or exhaust all the pairs in order to discover redescriptions with low first level accuracy. But after some number of initial pairs, a drop in the accuracy of the generated redescriptions can typically be observed. Limiting k p is therefore reasonable.

Generating the initial pairs from real-valued data requires some extra work. There are two options. First, if one of the matrices (say D L ) is Boolean while the other is real-valued, we create the initial pairs by considering redescriptions R = (v L , ∅) for each v L ∈ V L , and extending their right-hand side using the standard on-the-fly bucketing approach. Second, if both sides are real-valued, an exhaustive search of all possible intervals needs to be performed. This might be computationally very expensive, and in Section 5.3 we present a method to find the initial pairs faster with possible loss in accuracy.

Each of the initial pairs is extended in turn (lines 3-15), selecting at each step the k i most promising candidates (line 13). A value of 4 for k i , for example, enables to keep the candidates for both operators and both sides on the first step. Two sets of variables, F L (R) ⊂ V L and F R (R) ⊂ V R , are associated to each redescription R. They contain the variables that can be used to expand that redescription, which we call the free variables of R. The free variables are determined so as to avoid generating several times the same redescription. The variables leading from R to some already generated one-step extension, i.e. redescriptions obtained by appending one literal to it, are not free for R; this includes the variables that appear in R.

For the purpose of determining free variables, the algorithm maintains a list of the redescriptions generated so far. We assign a set of keys to every redescription, one for each literal involved. The redescriptions can be indexed using these keys in space bounded by the number of explored redescriptions multiplied by a factor quadratic in the maximal allowed query length. Then, given any redescription containing l literals, we can retrieve the sets of redescriptions associated to each of its keys in l accesses to the index. Its one-step extensions are the redescriptions of length l + 1 in the intersection of these sets.

In addition, when the query on either side of the redescription has reached the maximum number of variables, all remaining free variables for that side are removed. Among the selected candidates, those that have some free variables are put into the set E of redescriptions to be extended during the next iteration (lines 14). The loop ends when E is empty, that is, when there is no extendible redescription left.

Extensions to the Algorithm

With the basic algorithm presented in the previous section, we now turn to study some extensions to it. We first start by studying the possible constraints one can apply for the redescriptions, then present two methods that can be used to speed up the algorithm (possibly trading off some accuracy) with real-valued data. Finally, we explain how to extend the algorithm to handle missing values.

5.1 Constraints on the redescriptions. In this section, we discuss the different constraints one can apply to redescriptions. The accuracy is a simple constraint: leave out all redescriptions with accuracy lower than some threshold. But in addition to being accurate, we would like the redescriptions to be statistically significant. That is, the support of a redescription (q L , q R ) should carry some new information, given the support of the queries. To measure this, we test against the null-model representing the case in which the two queries would be independent. We compute a p-value that represents the probability that two random queries with marginal probabilities (i.e. the fraction of entities supporting them) equal to those of q L and q R have an intersection equal to or larger than |supp(q L , q R )|. This probability uses the binomial distribution and is given by

pvalM(q L , q R ) = |E| s=|supp(q L ,q R )| |E| s (p R ) s (1 -p R ) |E|-s , where p R = |supp(q L )| |supp(q R )| / |E| 2 .
The higher the p-value, the more likely it is to observe such a support for independent queries, and the less significant the query.

Similarly, when appending a literal l to a redescription, we would like it to be as informative as possible. On one hand, if q A and l have very similar supports, q A ∨ l will not carry much more information than the original q A , so we want q A and l to be as uncorrelated as possible and intersect less than would occur randomly. On the other hand, when extending q A to q A ∧ l we expect q A and l to be correlated and intersect more than would occur randomly. Hence we define pvalE(q s , ∧l) = pvalM(q s , l) and pvalE(q s , ∨l) = 1 -pvalM(q s , l).

Also important are the size of the support of the redescriptions and the number of entities by which each variable contributes to it, since redescriptions characterizing too few entities or almost all of them are of no interest.

These constraints on p-value and support can be applied more or less strictly during the beam search, using thresholds to penalize or simply disqualify candidate redescriptions that do not comply with them. The redescription p-value and support size can also be used to filter out uninteresting results a posteriori. Of course, the stricter the constraints applied within the candidate selection, the faster the search, but the more likely it becomes to miss candidates that would expand to acceptable redescriptions.

The type of query can also be selected, for example to disallow negations or use only disjunctions. Most of the constraints need not be tuned for good results, but they can be used to incorporate domain knowledge or to guide the algorithm to search for special redescriptors.

Interval approximation.

In cases where the search space of possible intervals is still too large (i.e. (n λ + 1)(n ρ + 1) is too big, cf. Section 4.5), we use a faster search to find an interval whose accuracy is a good lower bound to the optimal one. Let (t 0 , t 1 , . . . , t n λ +nρ+1 ) be the ordered list of cut points (as per Proposition 4.1), with the special cases t 0 = -∞ and t n λ +nρ+1 = +∞. Let l, i, and u be any indices such that S 1 = [t l , t i ], S 2 = [t i , t i+1 ], and S 3 = [t i+1 , t u ] are valid intervals. Note that we can have t i = t i+1 = w, when the value w is both a lower and an upper cut point.

On one hand, if the accuracy obtained by merging intervals S 1 and S 2 is lower than that of S 2 alone, then merging S 1 , S 2 , and S 3 yields lower accuracy than S 2 alone or merging S 2 and S 3 , for any interval S 3 . That is, if j(t l , t i+1 ) < j(t i , t i+1 ), then j(t l , t u ) < max(j(t i , t i+1 ), j(t i , t u )).

We use this property to find the best interval by upward aggregation. Starting with the first interval, we construct at each iteration an interval of the form I i = [λ i , t i ]. We go through the possible optimal values in ascending order, while keeping track of the best accuracy encountered:

λ i+1 = t i if j(λ i , t i+1 ) < j(t i , t i+1 ), and λ i+1 = λ i otherwise
On the other hand, if the accuracy obtained by merging intervals S 1 and S 2 is greater than that of S 2 alone, there might still be an interval S 3 such that merging S 2 and S 3 yields a higher accuracy than S 1 , S 2 and S 3 together. That is, even if j(t i , t i+1 ) < j(t l , t i+1 ), it does not necessarily follow that j(t i , t u ) < j(t l , t u ). Therefore, we also compute the best interval using downward aggregation, starting with the last interval and iterating over the possible optimal values in reverse order. Then we combine the two best intervals to eliminate possible undesirable values on either ends. Let I u and I d denote the best intervals found using upward and downward aggregations, respectively. The final interval returned is either I u , I d , or I u ∩ I d , depending on which maximizes j(). Using this method, we can compute an interval that approximates the optimal accuracy in O(n λ + n ρ ). This is especially useful in cases where the rows in E 1,0 and E 1,1 (for conjunctions) or E 0,1 and E 0,0 (for disjunctions) are not clearly separated, saving heavy computations when encountering variables that are intuitively poor extensions.

5.3

Approximating the initial pairs for real-valued data. The approximate search presented in Section 5.2 might not be sufficient to find the initial pairs in reasonable time. This is especially the case when the data contain dense variables with many different values on both sides. We then resort to unsupervised bucketing to reduce the number of intervals tested and make the computation tractable.

During the initial pair generation, when the number of intervals to test for a given pair of variables exceeds a predefined threshold, different values of the variables are aggregated together to construct non-overlapping contiguous buckets. Only the intervals corresponding to the bounds of the buckets are tested. The agressiveness of the method can be adapted by tuning the threshold on the original number of intervals and the number of entities that can be grouped.

Unlike with usual pre-bucketing approaches, the static buckets are only used for this special cases of initial pair generation; during the later extension steps, the algorithm determines the intervals dynamically as described previously.

Handling missing values.

Real-world data often contains missing values, i.e. cases where not all values are known for all entities. In order to handle such data, we consider the extended truth value set {True, False, Missing}. Any truth value assignment for a variable with missing values will lead to Missing as the value for those entites. When evaluating Boolean queries, the following new cases emerge: the negation of Missing is Missing; the value of X ∧ Missing is False if X is False and Missing otherwise; the value of X ∨ Missing is True if X is True and Missing otherwise.

With missing values, there are five new groups of entities given a redescription (q A , q B ): either q A or q B can be Missing while the other is True or False, or they are both Missing. Following the notation of already-defined sets E 1,0 , E 0,1 , E 1,1 and E 0,0 , we denote these sets by E 1,? , E 0,? , E ?,1 , E ?,0 , and E ?,? .

The presence of missing values requires us to re-define how we compute the quality of the redescription, i.e. the Jaccard coefficient. A common approach is to ignore those entities that have missing values. With relatively few missing values that are evenly distributed, this should give a reasonably good estimate of the true accuracy. We call this method rejective Jaccard, denoted J R , to distinguish from the cases with no missing values.

The rejective Jaccard has its problems, though. If the missing values are not evenly distributed, we may have to reject too much data to be able to obtain reasonable estimates. Therefore, we also consider two other estimates: the optimistic Jaccard (J O ) and the pessimistic Jaccard (J P ), defined as follows:

J O (q A , q B ) = |E 1,1 | + |E 1,? | + |E ?,1 | + |E ?,? | |E 1,0 | + |E 0,1 | + |E 1,1 | + |E 1,? | + |E ?,1 | + |E ?,? | (5.6) J P (q A , q B ) = |E 1,1 | |E 1,0 | + |E 0,1 | + |E 1,1 | + |E 0,? | + |E ?,0 | + |E ?,? | . (5.7)
The optimistic Jaccard gives the upper bound and the pessimistic the lower bound of the Jaccard coefficient when truth values are assigned to the missing values. In other words, the optimistic Jaccard corresponds to the accuracy obtained if one could assign truth values to the missing values in the most favorable way while the pessimistic Jaccard is the accuracy that would result from an adversarial assignment of the missing values.

These three accuracy measures change the way our algorithm behaves by changing the objective function. Optimizing J O , for example, means that we try to find a maximum upper bound, while optimizing J P means we try to find a maximum lower bound. We study these effects in Section 6.4.

Other than the different accuracy measures, the missing values are rather straight forward to implement. We need to keep track of the new sets, E 1,? , E 0,? , E ?,1 , E ?,0 , and E ?,? , for efficient computation of the different versions of Jaccard (cf. Section 4.3), but this does not alter the main principle. Similarly with real-valued data, having missing values only adds notational complexity -the concepts remain the same.

Experimental Evaluation of Algorithm's Properties

We now turn to the experimental evaluation of our algorithm. We divide this in three parts. The first part (this section) studies the various properties of our algorithm with both synthetic and real-world data. The next two sections compare our algorithm to other methods and present a real-world application of our algorithm, namely biological niche finding.

But before starting with the experiments, we explain a method for assessing the significance of the results based on randomizations and explain the data sets used.

An implementation of the ReReMi algorithm and the synthetic data generator are available online3 .

6.1 Assessing the significance with randomization methods. When mining the redescriptions, we compute various p-values in order to prune uninteresting rules. But these p-values are based on assumptions about the distribution of 0s and 1s in the (bucketed) data. Given the generality of our algorithm, we cannot assume the distributions to model exactly the underlying distribution of values. Hence, we also use property-preserving randomization methods. Such methods sample random matrices that share some property with the original matrix. The algorithm is then re-run using a random matrix as an input, and this process is repeated multiple times. If the results with random matrices contain multiple redescriptions that have same or higher accuracy than some redescription found from the original data, that redescription is deemed insignificant; otherwise it is significant (with respect to the property preserved by the randomization method).

For these experiments, we used two randomization methods. The first method permutes the matrix, preserving the values of the matrix. On symmetric matrices, we used a variation that preserves their symmetry: only the upper-right triangle was permuted, and the lower-left triangle was copied from there. The property of a matrix having the same values is not a very strong one. Hence, we also used a method to preserve the distribution of values in columns and rows of the matrix [START_REF] Ojala | Randomization methods for assessing data analysis results on real-valued matrices[END_REF]. This method is called swap-randomization. While swap-randomization is in many ways stronger than permutation, the latter is used for two reasons. First, its use is suggested in [START_REF] Ojala | Randomization methods for assessing data analysis results on real-valued matrices[END_REF]. Second, unlike swap-randomization, permutation can preserve symmetrical matrices.

6.2

The real-world data sets. For the real-world data, we used two basic data sets: DBLP and Bio. The former is obtained from the DBLP data base 4 , and its entities are authors. The first matrix defines the conferences in which each of them has published, while the second defines other authors with whom each of them has published. The entities of the latter data set are spatial areas, In each panel, the left-hand box is the distribution of accuracies with missing data and using the corresponding accuracy measure (M) and the right-hand box is the distribution of accuracies of the same redescriptions computed over full data and using normal Jaccard (F).

Applied to some two hundred synthetic Boolean matrix pairs with conservative noise the algorithm managed to find all planted queries. In the case of destructive noise and fully Boolean data, the algorithm managed to find the planted queries in only about 40% of the data sets, but always found queries with higher accuracy than that of the planted redescription. The algorithm cannot be considered faulty is these cases: It behaved as assumed, finding the redescriptions with the highest accuracies.

Applied to synthetic data sets where one matrix is Boolean and the other real-valued, both with conservative noise, the algorithm managed to find the planted redescriptions or equivalent in 76 cases out of 80. The planted redescriptions that were not found had contributions below the acceptance threshold. Thus, the algorithm again worked as assumed.

Experiments with missing values.

As for the full data, our first experiment with missing values is on synthetic data. We removed values from synthetic Boolean matrices with planted redescriptions (cf. Section 6.3) uniformly at random. We removed 1%, 5%, and 10% of the values (zeroes or ones) and replaced them with markers for missing values. Then we mined them with our algorithm and checked how well the planted redescriptions were discovered.

For the planted redescriptions with conservative noise, the planted redescription was found in 97% of the cases. With increasing ratio of missing values the algorithm more often did not found the complete planted redescription but rather one or several fragments of high accuracies.

We report the distributions of the accuracies in Figures 4 (conservative noise) and 5 (destructive noise). The results compare the different variations of the Jaccard (rejective, pessimistic, and optimistic) as well as their estimates to the true Jaccard computed over the full data (i.e. with no missing values).

In both figures, it is clear that the rejective Jaccard is the best. With conservative noise (Figure 4 In each panel, the left-hand box is the distribution of accuracies with missing data and using the corresponding accuracy measure (M) and the right-hand box is the distribution of accuracies of the same redescriptions computed over full data and using normal Jaccard (F).

Jaccards are close to the true Jaccards. Pessimistic Jaccard is the second-best option. While its estimates look bad (Figures 4(b) and 5(b)), the true Jaccards are almost as good as those with rejective Jaccard. One has to remember that the estimate of the pessimistic Jaccard is only the lower bound, and therefore having very low estimate is not bad in itself. The last option, optimistic Jaccard (Figures 4(c) and 5(c)) has the worst behaviour with higher level of missing values (although with 1% and 5% of missing values the true Jaccards are slightly better than those of pessimistic Jaccard).

As the missing values were evenly scattered over the data, the good behaviour of rejective Jaccard was no surprise.

Next, we experimented with the Bio small data set, generating copies with 1% or 5% of randomly chosen values removed. For each setting, we generated 10 copies and mined them. We compared the queries found in the data with missing values to thoses found in the full data. We only used rejective Jaccard due to its good performance with synthetic data.

The results are reported in Figure 6. With 1% of missing values the results are almost as good as the results with full data, but with 5% of missing values the true Jaccards are somewhat worse, even if the estimates are still high.

6.5 From Boolean to Numerical: the DBLP data. The purpose of this experiment is to study the behaviour of our algorithm with two versions of the same data, one Boolean and one numerical. For this we used the two variants of the DBLP data: DBLP B and DBLP N .

Some results with DBLP N are presented in Table 2, while some example results with DBLP B are in Table 3. In all tables, J stands for the Jaccard, supp is the support of the redescription, and the p-value is computed as in Section 5.1.

For these experiments, we disabled negations to allow later comparison (see Section 7.2). Comparing the two tables, it is obvious that DBLP N contains more information, allowing ReReMi to find more accurate redescriptions (the best Jaccard in Table 2 is 0.625). But the rules are also more specific than those in Table 3, with small support and often requiring multiple publications in the same conference, making them possibly harder to interpret than those of Table 3. Yet, in both cases the algorithm correctly identifies subfields of computer science and well-known authors from those fields.

6.6 Approximating the initial pairs. To study the effects of approximating the initial pairs, we took the climate data of the Bio small data set and divided it into two: the monthly average temperatures and monthly average rainfall. This gave us two real-valued data sets with 12 variables each. We call this data Climate.

This seemingly small data set is already hard for exhaustive initial pairs selection due to the nature of the data: almost each data point contains different values. Consequently, the exhaustive search was not able to finish in two days.

Instead of exhaustive search we used the binning-based initial-pairs searching method explained in Section 5.3. We tried different bin sizes, ranging from 10 to 100. We compared this with fully pre-bucketing approach, bin size again ranging from 10 to 100.

The results were clear. There was very little variation between different bin sizes for initial pairs in terms of accuracy: the smaller bins gave overall slightly better results, but all sizes had top-20 redescriptions with accuracy clearly above 0.8 with bests above 0.9. Pre-bucketing approaches, on the other hand, were clearly inferior, with the best results (obtained with bin size 10) being below 0.7.

In terms of speed, the pre-bucketed approaches were the fastest, with even the slowest (bin size 10) taking less than 4 minutes. The fastest method with initial bins (bin size 100) took roughly 10 times longer, 38 minutes. The slowest method (initial bin size 10) took one day and 24 minutes. In all the methods with initial bins, the time differences are explained by the time spent on constructing the initial pairs; after that, they all took roughly the same time.

The results were as expected. Using binning only for initial pairs (as opposed to working with pre-bucketed data) gave much better results, but also took more time. It is, however, noteworthy that increasing the bin size used for selecting the initial pairs did not have considerable effect on the quality. Apparently, the algorithm was able to overcome the possibly weaker initial pairs in later phases. 6.7 Running times. Does our algorithm scale? The data sets we used were not extremely large (although DBLP F is already of considerable size), but we feel confident to say that our algorithm is scaling reasonably well. All experiments were conducted in a single core of an 8 core Intel Xeon 2.8 GHz processor and with 32 GB of memory.

The statistics of the running times on the different data sets are presented in Table 4. There we can see that original data takes much more time to run than randomized data. This is because with randomized data, there are less potential redescriptions, and the algorithm can prune the search space much faster. The longest time required, 1 hour with DBLP F , is still very good, especially when one remembers that the algorithm needs to be run only once for the original data.

To evaluate more precisely the evolution of our algorithm's running time with respect to the size of the data, we generated synthetic matrices of increasing sizes. As we just mentionned, the running times on random data is not representative. Therefore, we need to insure that some redescriptions are present in the synthetic data. Thus, we constructed diagonal block matrices, where the blocks on the diagonal are matrices obtained as described in Section 6.3 while off-diagonal blocks are filled with randon noise. We used original matrices of size 500 × 10 for the fully Boolean setting and of size 250 × 10 for the setting where one side is Boolean and the other real-valued. We let our algorithm run on ten such synthetic data sets for each studied size. The algorithm consists of two major steps: firstly, computing singleton redescriptions by trying out all pairs of variables and secondly extending the best pairs in turn. In the case of fully Boolean data, the computation of initial pairs clearly dominates as the data grows larger, since it is quadratic in the number of columns while finding extension is linear. The running times remain reasonable even for very large data sets. When real-valued data is involved, the running times are much greater, as expected. Therefore we had to restrict the experiments to smaller data sets. The running times for that experiment are displayed in Figure 7. The increase in running times is due to the fact that extending a redescription is no longer linear and the search for initial pairs also has increased complexity.

Experimental Comparison Against Other Methods

With the previous sections results showing that our algorithm has solid performance, we can now turn to comparing our algorithm to other methods.

  nonnegative integers kp and ki, constraints C. Output: A set of redescriptions, R. 1: R ← ∅ 2: I ← {kp best initial singleton redescriptions } 3: for S ∈ I do 4:

10 :

 10 for side s ∈ {L, R} and operator • ∈ {∨, ∧} do 11:

12 :

 12 K ← K ∪ {best such extension of R admitting constraints C} 13:

Figure 2 :

 2 Figure 2: Formulae for computing the Jaccard coefficient for different extensions.

Figure 3 :

 3 Figure 3: Example of repartition of the entities for one variable. Each bin represents a value taken by the variable. Black circles stand for entities belonging to E 1,1 , white circles for entities from E 1,0 .

Figure 4 :

 4 Figure4: Distribution of redescription accuracies with missing values, conservative noise, and different accuracy measures. The three panels of subplots correspond to, from left to right, 1%, 5%, and 10% of missing values. In each panel, the left-hand box is the distribution of accuracies with missing data and using the corresponding accuracy measure (M) and the right-hand box is the distribution of accuracies of the same redescriptions computed over full data and using normal Jaccard (F).

Figure 5 :

 5 Figure5: Distribution of redescription accuracies with missing values, destructive noise, and different accuracy measures. The three panels of subplots correspond to, from left to right, 1%, 5%, and 10% of missing values. In each panel, the left-hand box is the distribution of accuracies with missing data and using the corresponding accuracy measure (M) and the right-hand box is the distribution of accuracies of the same redescriptions computed over full data and using normal Jaccard (F).

Figure 7 :

 7 Figure 7: Running times for mining redescriptions on synthetic data of increasing sizes with one side Boolean and the other real-valued.

Table 4 :

 4 Running times for the different data sets. For mean time, '-' denotes that there was only one data set.

	Data Set	mean	max
	DBLP F	-	60min
	DBLP F permuted	5min 16s	6min 32s
	DBLP F swap	16min	18min
	DBLP N	-	7min
	DBLP B	-	1min
	Bio	-	10min
	Bio permuted and swap	6min 48s	10min 30s

i.e. we consider realized niches using correlative methods (see[START_REF] Pearson | Predicting the impacts of climate change on the distribution of species: Are bioclimate envelope models useful?[END_REF]).

http://www.cs.helsinki.fi/u/galbrun/redescriptors/

http://www.informatik.uni-trier.de/ ~ley/db

Details of the grid can be found in www.fmnh.helsinki.fi/english/botany/afe/index.html.

Namely www, sigmod, vldb, icde, kdd, sdm, pkdd, icdm, edbt, pods, soda, focs, stoc, stacs, icml, ecml, colt, uai and icdt.

Acknowledgements

The authors are grateful to Dr. Jussi Eronen for helpful comments and suggestions.

. The data itself is composed from two publicly available data bases: European mammal atlas [START_REF] Mitchell-Jones | The atlas of European mammals[END_REF] and Worldclim climate data [START_REF] Hijmans | Very high resolution interpolated climate surfaces for global land areas[END_REF]. The mammals data contains presence/absence information of mammal species in Europe, and the climate data contains minimum, average, and maximum monthly temperatures as well as average monthly precipitation. Notice that the mammals data is Boolean while the climate data is continuous. We created variations of these two basic data sets for specific purposes. From the DBLP data we created three variations: DBLP F , DBLP N , and DBLP B . The first, DBLP F , is a big data set with 6455 authors and 304 conferences containing information on how many times each author has published in each conference and with each other author. The second, DBLP N , also contains numerical information but is restricted to 19 hand-picked conferences 6 and 2345 authors. The third, DBLP B , is like DBLP N , but Boolean: every positive value of DBLP N is replaced with 1. This data is identical to the one used by Gallo et al. [START_REF] Gallo | Finding subgroups having several descriptions: Algorithms for redescription mining[END_REF].

For the Bio data, we constructed two variations. The basic Bio data contains the whole data while smaller Bio small concentrates only on Northern Europe (specifically, areas between 50 and 71 degrees North). Also, it does not include monthly maximum or minimum temperatures, leaving only monthly average temperature and average precipitation.

The statistics of the real-world data sets used in the experiments are presented in Table 1.

Finding planted redescriptions.

To study the behaviour of our algorithm we first apply it to synthetic data. The idea is to generate data with planted redescriptions and check whether our algorithm is able to recover the redescriptions. Generating matrices such that, for example, no subset of the query forms an exact redescription, is not trivial.

To generate a pair of synthetic Boolean 500 × 10 matrices, we plant on both matrices one Boolean formula, either conjunction or disjunction over 3 variables with 50 supporting rows, such that the resulting redescription is exact. Then we add random noise of density between 0.01 and 0.1. The noise can either be conservative or destructive, leaving the redescription exact or not. A synthetic real-valued data matrix is then obtained replacing ones and zeros by values uniformly sampled from the intervals [0.75, 1] and [0, 0.25], respectively. q L q R J supp p-value The first experiment with real-world data mirrors the experiments with synthetic data: the task is to study how well our algorithm finds redescriptions from the data. But as we cannot know all redescriptions present in the real-world data, we narrow our scope to monotone conjunctive redescriptions from Boolean data. These redescriptions are simply bi-directional association rules, and hence can be found by mining all frequent itemsets from both data matrices and using the itemset pairs as redescriptions. This gives us the ground truth, against which we can compare our algorithm.

For these experiments we used the DBLP B data (see Section 6.2). We used the Eclat frequent itemset miner [START_REF] Zaki | Scalable algorithms for association mining[END_REF]. The redescriptions were generated as follows: first, all closed frequent itemsets with support greater than 5 were mined for both data sets. The itemsets were then combined into redescriptions. Only those with accuracy greater than 0.1, support above 10 but below 100 (inclusive), and p-value higher than 0.01 were retained. The same parameters were set to ReReMi, and it was only allowed to find monotone conjunctive redescriptions.

The best four redescriptions found using Eclat had a Jaccard similarity between 0.366 and 0.333. ReReMi found exactly the same redescriptions. After these four redescriptions, the Eclat approach found several redundant redescriptions: they were minor variations of the first four redescriptions. ReReMi did not report these redundant redescriptions, which we consider a positive feature -the user should not be overwhelmed by the quantity of results.

The next non-redundant redescription found by Eclat approach was also found by ReReMi. The same trend continued throughout the results: Eclat approach found several thousands of redescriptions, but most of them were redundant.

Applying Eclat on swapped and permuted randomized copies of the original data (500 pairs of matrices for each method) following the same approach did not return any redescription. Therefore all original redescriptions are considered significant with respect to these null hypotheses.

While these experiments cannot guarantee that ReReMi will always find the best redescriptions, they suggest that it is able to find most of the important ones.

Comparison to the work of Gallo et al.

As we used the same data set as Gallo et al. [START_REF] Gallo | Finding subgroups having several descriptions: Algorithms for redescription mining[END_REF], DBLP B , we compared the results obtained with ReReMi to theirs. Following [START_REF] Gallo | Finding subgroups having several descriptions: Algorithms for redescription mining[END_REF], we did not allow negations. The example results were already presented in Table 3.

The results obtained by ReReMi had higher Jaccard similarity than those obtained by Gallo et al.: the highest accuracy they report is 0.35, while ReReMi returns a redescription with accuracy 0.5, and 9 redescriptions have accuracy above 0.35.

An effect of the beam search is illustrated by the following for example. The results presented by Gallo et al. contain the following redescription of accuracy 0.30:

Our results do not contain this redescription, but

instead, with accuracy 0.34. Indeed, when starting from the intial pair (SDM, P. S. Yu), keeping at each step only the best candidate does not allow to find this redescription as it is obtained from a candidate ranked lower during the extension process. While allowing for a better exploration of the search space, our algorithm required only a third of Greedy's running time (3 min) with the same data. This shows that the proposed algorithm is faster yet more exhaustive on Boolean redescription mining than the Greedy algorithm. Otherwise the results are similar; both algorithms identify sets of conferences from different fields of computer science together with well-known authors from those fields. Both algorithms are also able to identify interdisciplinary researchers, say, theoretical machine learners who publish in both machine learning and theoretical conferences (row 1 of Table 3).

7.3

Comparison to CARTwheels and pre-bucketing numerical data. We now turn to another algorithm for mining redescriptions, CARTwheels [START_REF] Ramakrishnan | Turning CARTwheels: An alternating algorithm for mining redescriptions[END_REF]. We used the implementation of CARTwheels provided by the authors. Because of this, we do not have any control over the results reported by CARTwheels (e.g. minimum support, type of queries, p-values).

Boolean data. First, we tried CARTwheels with DBLP B . The algorithm returned in total 35 redescriptions before running out of the available 32 GB of memory. Of these, only 5 were retained after removing rules with p-value higher than 0.05. All of the remaining redescriptions had p-values between 0.0111 and 0.02, making them insignificant on the highest significance level (99%). The rules also covered almost the whole data, having at least 1567 (of 2345) rows in the support. This high support is a consequence of using mostly negated variables. Results are reported in Table 5.

As can be seen from Table 5, the results have high accuracy, which is not surprising, given their high support. Results also have many negations, making them less interesting. We let ReReMi find results with negations, too, and while we were not able to find results with as high accuracy (results omitted), they all had p-values essentially 0. We conclude that while CARTwheels finds more accurate redescriptions, they are somewhat insignificant, and less interesting than the ones found by ReReMi.

Pre-bucketing numerical data. In this section, we compare our on-the-fly bucketing approach to CARTwheels with bucketing as a pre-processing step.

To bucket the data, one has to select the bucketing method. For a fair comparison, we used three different methods with a number of buckets per variable varying between 10 and 150, ran CARTwheels for all of these configurations, and selected the best results. The three methods were (1) buckets of equal width, where the range of the values in a column was divided into equally long buckets; (2) buckets of equal height, where each bucket contained approximately equally many entities; and (3) segmentation, where the entities were separated into segments (i.e. buckets) minimizing the sum-of-square distances to the segment's mean (the segmentation was obtained using Bellman's algorithm [START_REF] Bellman | On the approximation of curves by line segments using dynamic programmming[END_REF]).

The CARTwheels algorithm was unable to handle the full Bio data, so we used Bio small instead.

The results are reported in Table 6. The aim of this experiment is to study how good accuracies can be obtained with pre-processed buckets compared to ReReMi.

The first results are the five best (with respect to the accuracy) from CARTwheels using 10 buckets of approximately equal number of entities (this method produced the best overall results, although 10 segments gave very similar results). The redescriptions have again very high accuracy, and, again, they cover almost all of the studied area. Furthermore, two of them are clearly insignificant and one is not very significant, according to the p-values. Results of this type are rarely of any interest for users, as they do not convey any interesting information. We pruned out results that had too high support (leaving less than 250 entities uncovered) or too high p-value. CARTwheels can still return rather accurate redescriptions, but the quality drops quickly after the first ones.

The last results in this experiment are from ReReMi. As CARTwheels obtained almost all of its results using negations, we allowed also ReReMi to use negations. As can be seen, ReReMi positions itself between non-pruned and pruned CARTwheels. But unlike the nonpruned CARTwheels, ReReMi does not return insignificant results.

We also experimented with bucketed data and Boolean ReReMi. The results were similar to those with pruned CARTwheels, but without the quick drop in accuracy. Also, they were considerably worse than the results with ReReMi using on-the-fly bucketing.

We conclude that with similar constraints, the on-the-fly bucketing of ReReMi gives the best results, although in this application, not allowing negations could be considered more reasonable an option.

8 Real-world application: Finding bioclimatic envelopes.

Our final experiment is a real-world application of finding bioclimatic envelopes.

ReReMi was run on full Bio data for a maximum of 100 initial pairs, minimum score for the initial pairs 0.2, minimum support 15, minimum number of uncovered entities 500, and minimum contribution 3, disallowing negated variables. This was done because the negated variables can lead to counterintuitive redescriptions in this type of application. The algorithm found 69 redescriptions within these constraints. Again, we regard it positively that our algorithm returns only a reasonable amount of results.

The data was randomized using swap-randomization and permutation. With both methods, 500 random matrices were generated, and in both cases the best redescription had lower accuracy than the lowest original accuracy. Hence, all redescriptions were considered significant with respect to these null hypotheses. The algorithm processed the full data in about 13 minutes.

Some of the results are displayed in Table 7. The redescriptions have varying support sizes: some cover only a small part of the data, while others cover almost the whole data. Yet, they all have very high accuracy. The first two redescriptions cover exactly the same area. They represent the Svalbard archipelago (see Fig. 8(a)). The climate in Svalbard is so different from other areas that it allows multiple ways to define it, causing multiple redescriptions. The fourth redescription has only European Elk on the left hand side, but the right hand side is more complex, characterizing very accurately the environment in Scandinavia and Baltia (Fig. 8(b)), the area occupied by the European Elk. The remaining redescriptions are more complex. The fifth redescription (Fig. 8(c)) covers Northern and Central Europe, while the last covers only Central Europe (Fig. 8(d)).

We point out that while the results of [START_REF] Garriga | Cross-mining binary and numerical attributes[END_REF] are superficially similar, the differences in the methods used and the goals pursued make the results incomparable.

Conclusions

We have presented a new algorithm to mine redescriptions from real-valued data. Unlike previous algorithms, ours does not require any pre-processing when used with non-Boolean data. It is based on a beam-search type of method. We have shown with both synthetic and real-world data sets Table 7: Example redescriptions from Bio data: t min X , t max X , and t avg X stand for minimum, maximum, and average temperature of month X in degrees Celsius, and p avg X stands for average precipitation of month X in millimeters. 7. Green circles, cyan plus crosses and magenta plus signs respectively indicate areas where both queries hold, only the left query holds and only the right query holds.

that our algorithm performs better than its peers. In particular, the experiments show the benefits of on-the-fly bucketing against pre-processing. The non-Boolean redescription mining has many applications in various fields of science, of which niche-finding is the one we have studied here. One of the most prominent future works would be to collaborate with biologists and ecologists and explore the true value of redescription mining in finding the bioclimate envelopes. Also other fields should be considered. Medical data describing patients where the matrices would contain genetic or physiological characteristics and symptoms, respectively, is one example.

While our algorithm seems to be working fine, it is by no means the final word. Building better algorithms is, as always, an important future direction. For a concrete example, the selection of initial pairs seems to have space for improvements.

Finally, having proofs of the behaviour of the algorithms is important. Is there, for example, an algorithm for real-valued redescription mining for which one can prove that it finds a redescription, provided that the redescription is sufficiently strong?