Esther Galbrun
email: galbrun@cs.bu.edu

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

Interactive Redescription Mining

Keywords: H.2.8 [Information Systems]: Database Applications-Data Mining, H.5.2 [Information Interfaces and Presentation]: User Interfaces-Data Visualization Methods Redescription Mining, Interactive Data Mining, Visualization, Brush-and-Link, Parallel Coordinates

Exploratory data analysis consists of multiple iterated steps: a data mining method is run on the data, the results are interpreted, new insights are formed, and the resulting knowledge is utilized when executing the method in a next round, and so on until satisfactory results are obtained.

We focus on redescription mining, a powerful data analysis method that aims at finding alternative descriptions of the same entities, for example, ways to characterize geographical regions in terms of both the fauna that inhabits them and their bioclimatic conditions, so-called bioclimatic niches.

We present Siren, a tool for interactive redescription mining. It is designed to facilitate the exploratory analysis of data by providing a seamless environment for mining, visualizing and editing redescriptions in an interactive fashion, supporting the analysis process in all its stages. We demonstrate its use for exploratory data mining.

Simultaneously, Siren exemplifies the power of the various visualizations and means of interaction integrated into it; Techniques that reach beyond the task of redescription mining considered here, to other analysis methods.

INTRODUCTION

The goal of data mining is to find surprising but useful new patterns and relations from the data. This process * The work was done while the author was a doctoral student at the involves multiple steps such as preparing the data, selecting and applying the data mining methods, and interpreting the results. Furthermore, it is generally iterative, with the results of the first round used to inform the decisions made in the second round, et cetera.

The analysis is -or at least should be -done by a domain expert, as only a domain expert can judge what kind of results are surprising or useful. But to allow the domain expert to perform the data analysis as effectively as possible, the process should be as seamless as possible. Typically, it is unreasonable to assume that the domain experts are proficient on using half a dozen different programs, often with arcane command-line interfaces, to deploy the full analysis process. There are two common ways to achieve the desired consistency: either via a workflow integrated into a wellknown general-purpose analysis framework, such as R or Matlab, or via a special-purpose tool specifically designed for the task at hand.

Siren takes the latter approach: it is a tool for interactively mining and visualizing redescriptions. Redescription mining [START_REF] Ramakrishnan | Turning CARTwheels: An alternating algorithm for mining redescriptions[END_REF] is a data analysis method that aims to find different ways of characterizing the same things and, vice versa, to find things that admit the same alternative characterizations. For instance, consider the task of bioclimatic niche finding [START_REF] Soberón | Niches and distributional areas: Concepts, methods, and assumptions[END_REF]: we are given a set of geographical regions (e.g. 50 km squares) with information about the species inhabiting these regions, on one hand, and the bioclimatic conditions (e.g. temperature and precipitation) encountered in each of them, on the other hand. The task is then to find a set of species and a set of bioclimatic conditions such that the bioclimatic conditions explain exactly (or as well as possible) the areas where the species live, and vice versa. Such a pair forms a redescription since it characterizes (approximately) the same area in two different ways.

An example redescription from bioclimatic niche finding characterizes Scandinavia and the Baltic as the habitat of the Moose, on one hand, and in term of its specific cold climate, on the other hand. A map plot of this redescription can be seen in the foreground of Figure 1. We will use niche finding as our example application throughout this paper, although we emphasize that redescription mining is not limited to any single application, or to any specific domain. Examples of other applications and redescription mining in general are discussed further in [START_REF] Ramakrishnan | Turning CARTwheels: An alternating algorithm for mining redescriptions[END_REF][START_REF] Galbrun | Methods for Redescription Mining[END_REF], for instance.

Siren can also be seen as a case study of the combination of various visualizations and interaction techniques into a powerful data analysis tool. Such integration could potentially also benefit methods other than redescription mining. In the next section we provide a very brief introduction to redescription mining and cover some related work. Section 3 explains the main features of Siren and why we think they are important. Section 4 outlines techniques used for implementing this tool, and Section 5 is a brief walk-through of the demonstration.

We presented a preliminary version of Siren in [START_REF] Galbrun | Siren: An interactive tool for mining and visualizing geospatial redescriptions -Demo[END_REF]. That version introduced the GUI and preliminary connections to the mining algorithm. However, it lacked visualizations other than plotting results on a map and did not have the more sophisticated interactive features of the current version. Furthermore, the underlying architecture has been significantly improved. In this paper we focus on the new features, except when necessary to understand the broader functionality. In other words, features discussed here are new compared to [START_REF] Galbrun | Siren: An interactive tool for mining and visualizing geospatial redescriptions -Demo[END_REF], unless otherwise mentioned.

More details about Siren, including videos, a user guide and further references on redescription mining are available on the associated webpage. 1

REDESCRIPTION MINING

Redescription mining is a descriptive data analysis task. It aims at simultaneously finding multiple descriptions of a subset of entities which is not previously specified [START_REF] Ramakrishnan | Turning CARTwheels: An alternating algorithm for mining redescriptions[END_REF]. This is in contrast with other methods like emerging pattern mining, contrast set mining, or subgroup discovery (see [START_REF] Novak | Supervised descriptive rule discovery: A unifying survey of contrast set, emerging pattern and subgroup mining[END_REF] for a unifying survey) or general classification methods, where target subsets of entities are specified via labels.

We consider data that contains entities with two sets of characterizing variables, such as the fauna and bioclimatic conditions. In this setting, the redescription mining task consists in finding a pair of queries, one query for each set of variables, such that both queries describe (almost) the same set of entities. We refer to the two sets of variables as left and right hand side data, and the queries over them, respectively, as left and right hand side queries. A redescription is simply a pair of queries over variables from the two sets. The support of a query is the subset of entities for which the query holds 1 http://www.cs.helsinki.fi/u/galbrun/redescriptors/siren/ true. The accuracy of a redescription is measured by the Jaccard coefficient (denoted as J) of the supports of its two queries; p-values indicating how likely it is to observe such an overlap for independent queries can be used to reject uninteresting redescriptions.

Several algorithms for redescription mining have been proposed over the years and in principle Siren can use any of them as the method to mine the redescriptions. To the best of our knowledge, however, only the ReReMi algorithm [START_REF] Galbrun | From Black and White to Full Colour: Extending Redescription Mining Outside the Boolean World[END_REF] can handle numerical or categorical data and missing values. It is therefore our algorithm of choice.

Our example application here is bioclimatic niche-finding. The aim is to determine the bioclimatic constraints that must be met for a certain species to survive, called the species' bioclimatic envelope, or niche [START_REF] Grinnell | The niche-relationships of the California Thrasher[END_REF]. Finding such envelopes could help, for instance, 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]. Unlike other tools developed over the past ten years to model the bioclimatic envelope, such as BIOMOD [START_REF] Thuiller | Biomod -a platform for ensemble forecasting of species distributions[END_REF], redescription mining allows automatically finding both the set of species and their envelope.

While we cannot cover other applications in this demonstration proposal due to space constraints, we refer the interested user to the aforementioned web page where we give three other example applications from different domains.

THE FEATURES OF SIREN

Siren provides a complete environment for redescription mining, from loading the data to finally exporting the results into various formats, through mining, visualizing, and editing the redescriptions. Siren allows for a seamless interaction with both the mining and visualization, enabling the user to interactively edit the redescriptions in the visualizations and to call the mining algorithm, e.g. to extend the current results. In what follows, we cover some of the main features of Siren and argue why they are important.

Mining. Obviously, the core of Siren is mining the redescriptions. Having just a GUI atop the mining algorithm is not enough, however, in particular because mining all the redescriptions from a dataset can be a time-consuming task. To avoid extensive waiting times, mining redescriptions in Siren is an asynchronous any-time process, meaning that the user will start seeing results from the mining algorithm as soon as the first (partial) results are ready. The user can start working with and editing these redescriptions while the mining algorithm continues in the background. While Siren was capable of doing this already in [START_REF] Galbrun | Siren: An interactive tool for mining and visualizing geospatial redescriptions -Demo[END_REF], we have improved the implementation of the asynchronous computations to take full benefit from the multiple cores in modern CPUs. Furthermore, the new asynchronous model allows Siren to off-load heavy computational tasks to an external server.

When exploring the data, the user often wants to extend existing redescriptions, either those returned by the algorithm or else some queries she has constructed herself, e.g. to test a hypothesis about the data. Siren allows to use an existing redescription as a starting point for the mining process. The user can also select only one side of the redescription to be extended. In bioclimatic niche finding, for example, this can be used to see how good a bioclimatic envelope the algorithm can find for a specific combination of species.

Furthermore, the user may specify a subset of entities that she wants to be emphasized during the mining process. For example, if the user wants to add some entities (in this case, geographic areas) to the support of the redescription shown in Figure 1, she can ask Siren to extend the given redescription with emphasis on including them in the support. In other words, the user can manipulate a redescription both through its queries and through its support.

The user can also disable variables and/or entities so that they will not be used in the mining process. For example, there can be known anomalous areas (e.g. coastal regions or valleys in mountain ranges) that the user might want to exclude, to prevent them from affecting the algorithm. The user can also disable the entities after the mining is done, in which case Siren will automatically update the support and accuracy of all redescriptions.

Visualizing. Visualization is the key to understanding the results of the mining process. As, for example, Heer and Shneiderman [START_REF] Heer | Interactive dynamics for visual analysis[END_REF] argued, having multiple concurrent visualizations of the same data reinforces their explanatory power. While the preliminary version of Siren was only capable of plotting redescriptions on a map, multiple different visualizations of the entities are now available. They are also applicable to data without spatial coordinates, thereby lifting the restriction to geospatial data.

The simplest of these visualizations are the various projections of the data into the 2D space. Different types of projections have been studied intensively, and Siren provides a number of them, including Karhunen-Loève transform (i.e. PCA), multi-dimensional scaling and various scatter plots. Figure 2 (a) and (b) are two alternative projections for the same example redescription, namely a scatter plot and an isomap embedding. In all visualizations, colors encode whether an entity belongs to the support of the left hand side query (denoted as E10), the right hand side query (E01), or both (E11). Here, we use red, blue, and purple respectively. Adding new projections is straightforward due to the modular nature of Siren. Computing these projections for larger datasets can be computationally intensive, but that too can be off-loaded to an external server.

Parallel coordinates plots [START_REF] Inselberg | Parallel coordinates: Visual multidimensional geometry and its applications[END_REF] are particularly suited for visualizing redescriptions. In such a plot, the entities are represented by lines going through a series of parallel vertical axes, one for each literal appearing in the queries. The position where a line crosses an axis indicates the value of the associated variable for the corresponding entity. For each literal, the range of values that make the truth assigment hold is represented by a grey interval box. An extra axis separates the two sides and registers the support of the queries. Figure 2 (c) shows an example of a parallel coordinates plot. The same color code is used for the entities as with other visualizations. In addition, grey lines represent entities that do not support either query (E00).

An example use case for the multiple visualizations is to study why some entities are not included in the support of both queries. To facilitate the analysis of such situations, Siren provides brush-and-link capabilities. The user can select (brush) an entity or a set of entities by clicking them or by drawing a polygon around them on any of the visualizations and the corresponding entities are highlighted in all associated visualizations. This way, the user can use the map to select areas of interest then use the 2D projections to quickly see whether these areas behave anomalously compared to other areas. In our example redescription, some areas where the Moose lives do not appear in the support of the climate query (drawn in red). We select three of them and notice from the two projections that the coastal areas of Norway (32VLM4 and 33WUP4) have a climatic profile which is clearly distinct from most covered areas, unlike the area in southern Sweden (33VUD3). From the parallel coordinates plot we then determine that raising the upper bound on February maximum temperature would allow to cover the latter area.

Editing. A redescription can be edited from any visualization by using the text fields under the plot. Thus, the user might adjust the conditions in the queries, add or remove variables, as well as build entirely new redescriptions by hand. Upon editing a query, the plot and the statistics of the redescriptions are recomputed to account for the modifications. This behavior was already implemented in the preliminary version of Siren. Now, it is also possible to edit the queries directly from the parallel coordinates plot by dragging the interval boxes to modify the bounds or categories for the variables. Continuing with our example, we can simply drag the top of the second grey box up to the highlighted line to include the area in the support (and some other areas as well). This will trigger the update of all the associated visualizations and re-computation of the statistics of the redescription.

IMPLEMENTATION DETAILS

Siren is available as a desktop program. Both Siren and ReReMi are implemented in Python to ensure cross-platform compatibility. The interface is built with the wxPython Open Source cross-platform GUI toolkit and relies on the matplotlib library for the visualizations. The 2D projections are implemented as modular functions that take a numpy matrix as an input and output a list of 2D points. Most of the projections call the corresponding routines from the scikit-learn package.

In Siren, all mining and projection tasks are handled in separate processes, using Python's standard multiprocessing library. Multiple independent computations can thus be run simultaneously, fully exploiting modern multi-core CPU architectures. The tasks can either be run locally or be off-loaded to an external server. The communication between Siren and the computational server are also handled with multiprocessing and we use a server-client architecture, so that a single server can serve multiple Siren clients by spawning a new worker for each job request.

DEMONSTRATION SCENARIO

In the demonstration we will present Siren following a usage scenario of finding bioclimatic niche with redescription mining, unless the audience prefers some other application.

After a brief explanation of the concepts underlying redescription mining and the chosen application scenario, we will demonstrate the features of Siren. In particular, we will highlight how the multiple visualizations together with the brush-and-link workflow support a better understanding and interpretation of the redescriptions and how the interface intuitively allows to impart domain knowledge to the mining process, so as to improve the results in subsequent iterations.

For the interest of time, we will start with few pre-mined redescriptions, but will then invite the audience to edit these redescriptions and to use the mining algorithm to extend them. Since Siren is a fully functional program that anyone can download from the web page, the demonstration can be fully interactive, with the users directly trying out the tool, possibly on their own datasets.

We have prepared a short video showing a sample walkthrough of the demonstration. It can be seen in the aforementioned accompanying web page.

CONCLUSIONS

Siren provides a seamless environment for interactively mining, visualizing, and editing redescriptions. Its multiple visualizations, coordinated plots, brush-and-link workflow, and tight integration to the mining algorithm make it a very effective exploratory data analysis tool.

This tool also provides a case study on the power of various means of visualization and interaction which are potentially relevant in the context of other exploratory data analysis methods as well.

Figure 1 :

 1 Figure 1: The Siren interactive mining and visualization tool. The panel in the background contains a list of redescriptions while the foreground panel displays the map plot of a selected redescription.

Figure 2 :

 2 Figure 2: Alternative visualizations of the redescription shown in the foreground panel of Figure 1. Three selected entities are highlighted across the different visualizations.


Esther Galbrun
email: galbrun@cs.helsinki.fi

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

Siren: An Interactive Tool for Mining and Visualizing Geospatial Redescriptions [Demo]

Keywords: H.2.8 [Information Systems]: Database Applications-Data Mining Algorithms, Design Redescription Mining, Interactive Data Mining

We present Siren, an interactive tool for mining and visualizing geospatial redescriptions. Redescription mining is a powerful data analysis tool that aims at finding alternative descriptions of the same entities. For example, in biology, an important task is to identify the bioclimatic constraints that allow some species to survive, that is, to describe geographical regions in terms of both the fauna that inhabits them and their bioclimatic conditions.

Using Siren, users can explore geospatial data of their interest by visualizing the redescriptions on a map, interactively edit, extend and filter them 1 .

To demonstrate the use of the tool, we focus on climatic niche-finding over Europe, as an example task. Yet, Siren is by no means limited to a particular dataset or application.

INTRODUCTION

Finding multiple ways to characterize the same entities is a problem that appears in many areas of science. In medical sciences, one might want to find a subset of patients sharing 1 More details about Siren's features, additional screenshots and a demonstration video are available online at http:// www.cs.helsinki.fi/u/galbrun/redescriptors/siren/. KDD'12, August 12-16, 2012, Beijing, China. XXX.

similar symptoms and similar genes. Describing geographical regions in terms of both their bioclimatic conditions and the fauna that inhabits them is another example -and a task of great importance for biologists. A simple example of a redescription in this setting could state that areas where Moose live are areas where February's maximum temperature is between -10 and 0 degrees Celsius and July's maximum temperature between 12 and 25 degrees Celsius. This is the redescription shown in the front panel of Figure 1.

However, finding such alternative descriptions of the data generally requires to manually fix the query on one side before looking for the best matching query on the other side, using some type of classification. This typically prevents queries involving more than one variable to be tested. Redescription Mining aims at solving this tedious task by automatically identifying the best redescriptions.

More formally, we consider data that contains entities with two sets of characterizing variables, e.g. the fauna and the bioclimatic conditions. We refer to the two sets of variables as left and right hand side data, and the queries over them, respectively, as left and right hand side queries. The task consists in finding a pair of queries, one query for both sets of variables, such that both queries describe (almost) the same set of entities. Section 4 presents requisite background information about that problem.

The results of redescription mining, the redescriptions, can be approached from two points of view. On one hand, by considering the variables and conditions appearing in the queries, which provide valuable information in themselves; On the other hand, by studying the support set of the redescriptions, i.e. the subset of entities where both queries of a redescription hold. When the data is geospatial, that is, the entities are connected to geographical locations, the latter approach becomes even more important. A meaningful geospatial redescription should define coherent areas using expressive queries. The goal of Siren is to facilitate the analysis of redescriptions using both of the approaches simultaneously.

Mining data is generally an iterative process, the results obtained at one step giving rise to hypotheses which will be tested at a further step, and redescription mining is no exception. Providing means to the user to easily interact with the mining process greatly improves the analysis. When dealing with geospatial data, visualizing the results on a map is crucial in order to interpret them. To answer these needs, we present Siren, an interactive tool for mining and visualizing geospatial redescriptions.

Alternatively, experimenting with Siren provides an efficient way for unfamiliar users to learn about redescription mining. The underlying concepts can be easily understood while visualizing the redescriptions and interacting with the system. Hence, it can also be used for educational purposes.

EXAMPLE APPLICATIONS

Our main example for demonstrating Siren is an application to bioclimatic niche-finding.

Indeed, an important problem in biology, niche-finding, is a particular instance of redescription mining. The bioclimatic constraints that must be met for a certain species to survive constitute that species' bioclimatic envelope, or niche [START_REF] Grinnell | The niche-relationships of the California Thrasher[END_REF]. 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]. A number of methods, involving regression, neural networks, and genetic algorithms (see [START_REF] Soberón | Interpretation of models of fundamental ecological niches and species' distributional areas[END_REF]) have been developed over the past ten year to model the bioclimatic envelope, BIOMOD [START_REF] Thuiller | Biomod -a platform for ensemble forecasting of species distributions[END_REF] being a good example of a modelling tool used in this domain. But to the best of our knowledge, none of these methods allows automatically finding both the set of species and their envelope.

We give an example of the application of Siren on this task using data that describes spatial areas of Europe, squares of side roughly 50 kilometers. The left hand side data contains information about the mammals living in these areas, while the right hand side consists of bioclimatic variables.

The data comes from two publicly available datasets: 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].

Nonetheless, Siren is a flexible tool that can be used with different datasets from various application domains. For instance, it could help in sociological studies, with the exploration of statistical and political data. On the web page, we outline a usage scenario based on census statistics and electoral campaign funding of U.S. continental counties, as an alternative example.

USE-CASE SCENARIO

We exemplify the usage of Siren by going through a generic work-flow of mining geospatial redescriptions, detailing typical steps in the process. A screenshot of the system, displaying a list of redescriptions with one particular redescription plotted on a map is shown in Figure 1.

Initial redescription mining.

A natural starting point for the analysis of any given data is to use a redescription mining algorithm to find an initial set of redescriptions. This can be done withing Siren by running the extension mechanism on an empty redescription.

Extending a redescription.

Sometimes the user wants to focus only on one of the queries, on some particular variable of interest or on a part of an existing redescription. Siren allows the user to auto- matically extend a given redescription, i.e. let the algorithm add new literals to the queries to make the redescription as accurate as possible.

The extension mechanism of Siren is based on the beam search implemented in the ReReMi algorithm [START_REF] Galbrun | From Black and White to Full Colour: Extending Redescription Mining Outside the Boolean World[END_REF]. In this case, the intermediate redescriptions explored during the search are returned at each step, allowing to study more specific alternative extensions to a redescription that were discarded from the beam because they were not among the best extensions at some point of the search.

In the climatic niche-finding task, for instance, we might select a species, say, the Southwestern Water Vole and look for best extensions starting from that single variable. Returned extensions can be visualized side by side and compared as shown in Figure 2. Here, the best found extension has accuracy 0.665 (per Jaccard coefficient): This redescription indicates that areas where any of the four species lives correspond to areas where the maximum temperature in March is above 11.2 degrees Celsius, the average temperature in January between 0.51 and 11.333 degrees Celsius and the average precipitations in October and November range from 42.75 to 131.81 millimeters and from 50.556 to 176.75 millimeters, respectively.

Editing a redescription.

It is typical that the user wants to edit some of the obtained redescriptions. For example, some results might be overly complex, or have exceedingly precise boundaries for numerical variables. The user can easily select a redescription to modify, open it in a map panel and edit it. Boundaries can be altered, literals added or removed. Siren updates the map and important statistics (accuracy, p-value, etc.) of the redescription, allowing the user to see the effects of the modifications immediately and verify, e.g. whether the new redescription would still be acceptably accurate.

Continuing with our example above, we might want to reduce the precision of the climatic constraints to integers. We could edit the query as follows:

[11 ≤ t + 3 ] ∧ [0 ≤ t = 1 ≤ 12] ∧[42 ≤ p = 10 ≤ 132] ∧ [50 ≤ p = 11 ≤ 177]
, and obtain a redescription of slightly decreased accuracy.

Using subsets of variables.

Siren allows the user to specify variables to temporarily avoid when extending or mining redescriptions.

For example, when two variables are highly correlated, several redescriptions might contain them both. The user, however, might want to consider redescriptions with only one of these variables, not both. Siren makes that simple: the user only has to select a redescription, remove the unwanted variable from the redescription and unselect it from the list of variables, then extend the redescription again.

Alternatively, in our running example, we might want to force the algorithm to search alternative redescriptions that do not involve any precipitation. For that purpose, we simply unselect all such variables before running the extension anew. We will obtain the best extensions containing only temperatures in the bioclimatic query, such as the following redescription of accuracy 0.653: ]. Note that this redescription was not returned previously since the beam search focused on better ones involving precipitation variables.

Filtering redundant redescriptions.

It is common to see a set of redescriptions that cover approximately the same area even if they have (somewhat) different sets of variables. Indeed, redescriptions belong to the family of local patterns, with each individual pattern independently describing a subset of the data. Mining local patterns typically returns redundant results that require filtering. In such cases, it is important to be able to recognize and remove redundant redescriptions, i.e. redescriptions that do not convey significant new information, lest the user be overwhelmed with the number of found redescriptions. Again, Siren allows automatic filtering of redundant redescriptions. The user can select a redescription and ask Siren either to filter out all redescriptions that are redundant with respect to the selected one, or to go through the whole list of redescriptions filtering out all redescriptions that are redundant with respect to some earlier-encountered (i.e. better) redescription. Naturally, the decisions made by Siren can be reverted whenever the user wishes to.

For instance, the results returned during the extension mentioned previously may contain many redundant redescriptions found at different steps. We can easily sort them, e.g. by accuracy, select one of interest and filter all the following results redundant with respect to it.

Outputting the results.

Finally, Siren facilitates the distribution of the results: redescriptions can be exported in easy-to-read format and the maps associated to redescriptions can be readily converted to publication-ready graphics.

REDESCRIPTION MINING

Redescription mining aims at simultaneously finding multiple descriptions of a subset of entities which is not previously specified. This is in contrast with other methods like Emerging Patterns Mining (EPM), Contrast Set Mining (CSM) and Subgroup Discovery (SD) (see [START_REF] Novak | Supervised descriptive rule discovery: A unifying survey of contrast set, emerging pattern and subgroup mining[END_REF] for a unifying survey) or general classification methods, where target subsets of entities are specified via labels. Currently, redescription mining is a purely descriptive approach, its predictive power remains to be explored. Since its introduction in [START_REF] Ramakrishnan | Turning CARTwheels: An alternating algorithm for mining redescriptions[END_REF] various algorithms have been proposed for Boolean redescription mining, based on approaches 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], co-clusters [START_REF] Parida | Redescription mining: Structure theory and algorithms[END_REF], and frequent itemsets [START_REF] Gallo | Finding subgroups having several descriptions: Algorithms for redescription mining[END_REF].

At the core of Siren is the ReReMi redescription mining algorithm. This greedy algorithm uses an efficient on-thefly discretization technique to extend redescription mining to categorical and numerical variables. Below, we give an outline of the concepts and algorithms involved. Full details can be found in the original publication [START_REF] Galbrun | From Black and White to Full Colour: Extending Redescription Mining Outside the Boolean World[END_REF].

We consider Boolean, categorical, and numerical variables, partitioned into two sets. Boolean variables can be interpreted as a truth value assignment in a natural way. For categorical and real-valued variables, truth value assignments are induced by relations [v = c] and [a ≤ v ≤ b], respectively, where c is some category and [a, b] an interval. These truth assignments and their negations constitute literals which can be combined using the Boolean operators ∧ (and) and ∨ (or) to form queries. Then, a redescription is simply a pair of queries over variables from the two sets. The support of a query is the subset of entities for which the query holds true. The accuracy of a redescription is measured by the Jaccard coefficient of the supports of its two queries; p-values indicating how likely it is to observe such an overlap for independent queries can be used to reject uninteresting redescriptions.

We use a strategy similar to beam-search to explore the solution space. The basic idea is to construct queries bottomup, starting from singleton redescriptions (i.e. both queries contain only one literal) and progressively extending them by appending operators and literals. After evaluating all possible one-step extensions, we select the best candidates and extend them in turn. This process stops when no new redescription can be generated.

IMPLEMENTATION DETAILS

Siren and ReReMi are implemented in Python. The interface is built with the wxPython Open Source GUI toolkit, ensuring cross-platform compatibility. The matplotlib library enables to generate high quality figures, seamlessly integrated in the interface. Siren allows for simple editing of the redescriptions thanks to flexible parsing of different representations. It can handle any data provided in a compatible format.

The formulation of redescription mining presented here assumes that the describing variables are partitioned into two sets apriori, and looks for a pairs of queries over these two sets, respectively. However, this can be naturally adapted to settings with a single set of describing variables. One might then search for pairs of queries, with the constraint that the two subsets of variables appearing in the queries of any redescription be disjoint or enable the user to interactively determine the split between the variables.

CONCLUSIONS

We present Siren, a tool for mining geospatial redescriptions. It enables users to interactively mine, edit and extend redescriptions. It also features visualization of the redescriptions on a map, a key toward interpreting the results of geospatial data mining.

We will give chance to the public to experiment with Siren and together consider how this tool could be used to explore their own geospatial data and help answer their data analysis need.

Figure 1 :

 1 Figure 1: The Siren interactive mining and visualization tool. The panel in the background contains a list of redescriptions while the foreground panel displays the map of a selected redescription. In this example, left hand side queries are over fauna while right hand side queries are over monthly bioclimatic conditions, that is, temperatures and precipitation.

Figure 2 :

 2 Figure 2: Several map panels. Comparing intermediate extensions automatically generated for a chosen starting variable. Red, blue and purple represents areas where only the left hand side query holds, only the right hand side query holds and where both queries hold, respectively.


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.

But 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 nichefinding, while the fauna can be naturally represented using a Boolean presence/absence data, the weather cannot.

In this paper, we extend redescription mining to realvalued data 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 for both sets of variables, such that both queries describe (almost) the same set of entities. In niche-finding, the entities would be spatial locations, one set of variables would be the fauna and the other set would contain the bioclimatic variables. A very simple example of a redescription in this setting could say that the area where polar bears live is the area where May's mean temperature is between -3 and -7 degrees Celsius (indeed, this is one of the results our algorithm produces, see Section 5). Until now, the redescription mining algorithms (see [START_REF] Gallo | Finding subgroups having several descriptions: Algorithms for redescription mining[END_REF][START_REF] Parida | Redescription mining: Structure theory and algorithms[END_REF][START_REF] Ramakrishnan | Turning CARTwheels: An alternating algorithm for mining redescriptions[END_REF][START_REF] Zaki | Reasoning about sets using redescription mining[END_REF]) have not been able to handle other than Boolean data. Hence they have not been able to help in the aforementioned cases, not at least without some pre-processing.

The rest of this paper is organized as follows. The next two sections, 2 and 3, present notation and definitions, and related work, respectively. We explain our algorithm in Section 4 and report about experimental evaluation in Section 5. Section 6 concludes the paper.

Contributions. In this paper we extend redescription mining to real-valued data with an algorithm that efficiently computes the optimal discretization on-thefly. We present experimental studies with synthetic and real-world data to verify that our algorithm scales and returns good results. We also assess the significance of our results by testing them against different null models. Our primary application for real-valued redescription mining is niche-finding, to which we present interesting and intuitive results. The proposed method is also applicable to other domains, like medicine.

Notation and Definitions

This paper considers redescriptors over two sets of variables, V L and V R . The set of entities is denoted by E. We will represent the data using two matrices, D L and D R . Both matrices have |E| rows and D i has |V i | columns. The value of D L (i, j) is the value of v j ∈ V L for e i ∈ E. If I is a set of row indices (or a characterizing vector thereof), D(I, j) is the column j of D restricted to the rows in I. The data is a 5-tuple D = (V L , V R , E, D L , D R ). We identify variables in V L and V R with the corresponding columns in D L and D R when there is no risk of ambiguity.

We consider two types of variables: Boolean and real-valued. (We omit categorical data for the sake of clarity and brevity, but handling it is straight forward using the approach presented here.) If v ∈ V is Boolean, we interpret the column corresponding to it as a truth value assignment for e ∈ E in a natural way. If v ∈ V is real-valued, we consider an interval [a, b], and the truth value assignment induced by the relation v ∈ [a, b]. We will denote this truth value assignment using Iverson notation: [a ≤ v ≤ b] is the Boolean (column) vector that has 1 in the rows where v ∈ [a, b], and 0 elsewhere.

These truth assignments and their negations constitute the set of literals for variables in V . Notice that there are infinitely many intervals yielding the same truth value assignment for some v ∈ V . To avoid ambiguity, we consider only the shortest interval yielding some truth value assignment. An exception to this is the special case where the interval contains the lowest or highest value in the data set for the given variable. We then consider half-lines (-∞, b] and [a, +∞), respectively, but for the sake of brevity they are also called intervals. Notice that we can always reconstruct the interval given the data and the truth value assignment corresponding to the interval.

Literals can be combined with Boolean operators ∧ (and) and ∨ (or). A Boolean formula is 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 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 4.7.

3 Related Work 3.1 Rule discovery. Given a set of observations and a subset thereof, many methods try to find discriminative patterns for the given subset. Depending on the nature of the pattern and the type of variables observed, these techniques are called Logical Analysis of Data (LAD) [START_REF] Boros | An implementation of logical analysis of data[END_REF], Emerging Pattern Mining (EPM), Contrast Set Mining (CSM) or Subgroup Discovery (SD), to name a few (see [START_REF] Novak | Supervised descriptive rule discovery: A unifying survey of contrast set, emerging pattern and subgroup mining[END_REF] for a unifying survey of the last three).

Attempts have been made to extend Subgroup Discovery from single binary class label to multiple output variables. In [START_REF] Umek | Subgroup discovery in data sets with multi-dimensional responses: A method and a case study in traumatology[END_REF], this is done by first applying k-medoids clustering to input and output variables separately and then finding relationships between the clusters using χ 2 test of independence. In the Exceptional Model Mining framework [START_REF] Leman | Exceptional model mining[END_REF][START_REF] Van Leeuwen | Maximal exceptions with minimal descriptions[END_REF], the aim is more generally to identify a subset of the entities defined by a single binary feature or a pattern over several features such that a model fitted to that subset significantly differs from the same model fitted to the rest of the entities.

The approach presented in [START_REF] Garriga | Cross-mining binary and numerical attributes[END_REF] somewhat similarly uses frequent itemsets on the binary attributes to define subsets of the entities and then tries to form a partition of the original data with the subsets that can be best modeled using the numerical attributes.

In Multi-label Classification [START_REF] Tsoumakas | Mining multi-label data[END_REF] the goal is to learn classifiers for conjunctions of labels. It shares some similarties with redescription mining, but it can only handle conjunctions and it is a predictive approach while ours is a descriptive one.

Redescription mining differs from these 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. This problem 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 algorithms proposed have been based on various ideas, including decision trees [START_REF] Ramakrishnan | Turning CARTwheels: An alternating algorithm for mining redescriptions[END_REF], co-clusters [START_REF] Parida | Redescription mining: Structure theory and algorithms[END_REF], and frequent itemsets [START_REF] Gallo | Finding subgroups having several descriptions: Algorithms for redescription mining[END_REF].

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 pre-processing: typically categorical data is represented using one variable per category, and quantative data is turned into cate-gorical data using some type of bucketing.

When labels are available on the original data, as it is the case for Subgroup Discovery with a single output feature, a supervised discretisation method can be devised for the problem at hand. In [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 cut 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. Moreover, it is very specific to association rule mining making it hard (or impossible) to apply to redescription mining.

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.

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 2 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]).

the set of species and their envelope.

The Algorithm

In this section, we present our algorithm. We start with some motivation of and ideas behind our design choices. Then, we give a general outline of our algorithm, before moving to some of its building blocks. First we explain how to compute the accuracy of an extended Boolean query efficiently. While important in itself, this technique also forms the basis for bucketing non-Boolean variables on the fly. Next, we give a more detailed explanation of the algorithm, and end this section by discussing the constraints that can be applied in order to retain the most interesting redescriptions.

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 (e.g. [START_REF] Ramakrishnan | Turning CARTwheels: An alternating algorithm for mining redescriptions[END_REF] uses decision trees of fixed depth, [START_REF] Parida | Redescription mining: Structure theory and algorithms[END_REF] considers monotone CNF and DNF formulae, and [START_REF] Zaki | Reasoning about sets using redescription mining[END_REF] only (possibly negated) conjunctions). 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 at least from 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 in [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 expres-sive 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 preprocessing 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 preprocessing 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), (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 similaries 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.

Input: Data D = (V L , V R , E, D L , D R ),
C ← {S} 5: if F L (S) = ∅ or F R (S) = ∅ then 6: E ← {S} 7: while E = ∅ do 8: for each R ∈ E do 9:
for side s ∈ {L, R} and operator • ∈ {∨, ∧} do 10:

if R can be extended on side s with operator • and literal l ∈ Fs(R) then 3 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 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 ). Should we do this in a straight forward way, we would have to compute three supports over the data for each accuracy. 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.

E ← {R ∈ C : F L (R) = ∅ or F R (R) = ∅}
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

E 1,0 ([λ ≤ v ≤ ρ]).
It is well known that the Jaccard coefficient J(q A , q B ) can be expressed as 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.

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)|

Extension to real-valued variables.

With the real-valued data, our approach is to do bucketing onthe-fly, finding the optimal bucket to add in every step. Assume that our algorithm tries to extend, say, query q L of redescription (q L , q R ) with a real-valued variable v. The algorithm considers the extended query q L ∧[λ ≤ 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.

The question is: how can we find λ and ρ efficiently? We can 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. 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].

Detailed explanation is provided only for nonnegated conjunctions; the other cases are analogous. Given a redescription (q A , q B ) and a variable v, our aim is to find bounds λ and ρ that maximize

(4.1) j(λ, ρ) = |E 1,1 ([λ ≤ v ≤ ρ])| |E 1,0 ([λ ≤ v ≤ ρ])| + |E 0,1 | + |E 1,1 | .
In order to do this efficiently, we will classify the values of λ and ρ that can maximize j(λ, ρ). Clearly, only the values of v occuring in entities that belong either to E 1,0 or to E 1,1 need to be considered. Furthermore, acceptable bounds for the interval are values that sepa- rate entities in E 1,0 from entities in E 1,1 . Let (v 1 , v 2 . . .) be all the values that appear in E 1,0 or in E 1,1 , some of them appearing in both, sorted in increasing order (see Figure 3 for an example). A lower cut point is a value

• • •• • • • • • • • • • •• •• • • • • • • •• • v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 v 10 v 11
v i such that v i ∈ D(E 1,1 , v) and v i-1 ∈ D(E 1,0 , 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). In the example, v 2 , v 3 , v 7 , v 10 and v 11 are lower cut points while v 1 , v 2 , v 5 and v 7 are upper cut points. We now have Proposition 4.1. The optimal value for λ is one of the lower cut points or -∞; the optimal value for ρ is one of the upper cut points or +∞.

Proof. The proof will be for the lower bound λ.

The other part is analogous. 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 λ = -∞ can be optimal.

Consider the example in Figure 3. 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.

To search for an optimal bucket for variable v, we only need to consider the points defined in Proposition 4.1. 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 .

Interval approximation.

In cases where the search space of possible intervals is still too large, we use a faster search to find an interval whose accurracy is a good lower bound to the optimal one. Let (t 0 , t 1 , . . . , t n λ +nρ+1 ) be the ordered list of possible optimal values for λ and for ρ (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 are not clearly separated, saving heavy computations when encountering variables that are intuitively poor extensions.

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. Still, for sparse data or data with only a limited number of possible values, using the approximate search when necessary, this can be done in reasonable time (cf. Subsection 5.6).

Each of the initial pairs is extended in turn (lines 3-14), selecting at each step the k i most promising candidates (line 12). A value of 4 for k i , for example, enables to keep the first step candidates for both operators and both sides. 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.

For this purpose, the algorithm maintains a list of the redescriptions generated so far. The variables leading from R to some already generated one-step extension are not free for R; this includes the variables that appear in R. 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 13). The loop ends when E is empty, that is, when there is no extendible redescription left. 4.7 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 nullmodel 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 equal to

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, 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 redescription 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 candidates 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.

Experimental Evaluation

We now turn to the experimental evaluation of our algorithm. We will start by explaining a method for assessing the significance of the results based on randomizations. Then we will report the actual experiments. The first two sets of experiments (one with synthetic and one with real-world data) are designed to evaluate the capabilities of our algorithm in covering the search space and returning the best possible redescriptions.

Next, we will compare our algorithm against the Greedy algorithm by Gallo et al. [START_REF] Gallo | Finding subgroups having several descriptions: Algorithms for redescription mining[END_REF], to study the effects of our more exhaustive coverage of the search space on the results. Most of these experiments are conducted with fully Boolean data, as performing well with Boolean data is a requisite for performing well with non-Boolean data. We then compare our algorithm against CARTwheels, beginning with a small comparison on fully Boolean data, after which we will compare the bucketing done as pre-processing to our method.

We will conclude the experiments with some realworld examples of niche finding results. The algorithm and the synthetic data generator are available online3 .

5.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 use also propertypreserving 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 (w.r.t. the property preserved by the randomization method).

For these experiments, we used two randomization methods. The first method is to permute the matrixthis preserves the values of the matrix. In addition, we used a variation to preserve symmetric matrices: 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 swaprandomization, it can preserve symmetrical matrices.

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.

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 accuracy.

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 was assumed.

Comparison to association rule mining.

The first experiment with real-world data mirrors the experiments with synthetic data: the task is to study how well our algorithm finds the 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.

The data used for this experiment is called DBLP B . Obtained from the DBLP data base 4 , its entities are authors, with one matrix defining the conferences in which each of them has published, and the other defining other authors with whom each of them has published. This version contains 19 hand-picked conferences, 2345 authors, and is Boolean, i.e. it does not contain information on the number of times an author has published in some conference or with some co-author. The same data was used by Gallo et al. [START_REF] Gallo | Finding subgroups having several descriptions: Algorithms for redescription mining[END_REF], where more details are provided about how it was generated.

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 4 http://www.informatik.uni-trier.de/˜ley/db 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 w.r.t. 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 the same data set, DBLP B , is used also by Gallo et al. [START_REF] Gallo | Finding subgroups having several descriptions: Algorithms for redescription mining[END_REF], we compared the results obtained with ReReMi to theirs. As Gallo et al. did not allow negation, neither did we. Some results are presented in Table 1. In all tables, J stands for the Jaccard, supp is the support of the redescription, and the p-value is computed as in Section 4.7. The results obtained by ReReMi had higher Jaccard similarity than those obtained by Gallo et al.: the highest similarity they report is 0.35, while ReReMi returns a redescription with similarity 0.5, and 9 redescriptions have similarity above 0.35.

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 1).

We also tried another version of the DBLP data set, which we denote DBLP N . This is otherwise like DBLP B , but contains the information about the actual number of publications an author has had in a conference and with a co-author. Hence, instead of being Boolean, the matrices contain non-negative integers.

As can be seen from Table 2, this version of the data contains more information, allowing ReReMi to find more accurate redescriptions (the best Jaccard is 0.625). But the rules are also more specific, with small support and often requiring multiple publications in the same conference, making them possibly harder to interpret than those of Table 1. The algorithm works as assumed: it performs better when given more information; rather, the results follow from the data. The (senior) researchers who have published many times in the same conferences are simply the easiest to distinguish. Furthermore, the supports of the redescriptions in Table 1 are mostly small groups of well-known computer scientists. Hence, while the redescriptions are complex, they describe easily understandable groups.

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. On the real-valued data ReReMi's running time was naturally longer but remained very acceptable (less than 8 min).

5.5

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 3.

As can be seen from Table 3, the results have high similarity, 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 similarity (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 vary-ing 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]).

We used a different data set for these experiments, called Bio. In this data, the entities are spatial areas, that is, approximately 50 km squares over Europe 5 . The data itself is composed from two publicly available data sets: 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. This data has 2575 rows (atlas squares), 194 mammals, and 48 climate variables. Notice that the mammals data is Boolean while the climate data is continuous.

Unfortunately, CARTwheels was unable to handle this big data set. To make comparison possible, we concentrated only on Northern Europe (specifically, areas between 50 and 71 degrees North). Also, we removed monthly maximum and minimum temperatures, leaving only monthly average temperature and average precipitation. This left us with 1271 rows, 119 mammals, and 24 climatic variables. We call this data Bio small .

The results are reported in Table 4. The aim of this experiment is to study how good accuracies can be obtained with pre-processed buckets compared to ReReMi. Hence, and due to the lack of space, we do not report the actual redescriptions.

The first results are the five best (w.r.t. 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 maximum support (above 250) or too high p-value. CARTwheels can still return rather accurate redescriptions, but the quality drops quickly after the first ones. 5 Details of the grid can be found in www.fmnh.helsinki.fi/ english/botany/afe/index.html.

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 non-pruned CARTwheels, ReReMi does not return insignificant results.

We also experimented with bucketed data and Boolean ReReMi (results omitted). 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 onthe-fly bucketing of ReReMi gives the best results.

5.6 Real-world application: 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 see it positively that our algorithm returns only a reasonable amount of results.

The data was randomized using swaprandomization 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 w.r.t. these null hypotheses. The algorithm processed the full data in about 13 min.

Some of the results are in Table 5. 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. 4(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. 4(b)), the area occupied by the European Elk. The remaining redescriptions are more complex. The fifth redescription (Fig. 4(c)) covers Northern and Central Europe, while the last covers only Central Europe (Fig. 4(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.

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 realworld data sets 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 nichefinding is the one we have studied here. One of the most prominent future works would be to work together 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?

11 :

 11 C ← C ∪ {best such extension of R admitting constraints C} 12: C ← {ki best redescriptions from C} 13:

Figure 1 :

 1 Figure 1: ReReMi: Mine data sets for redescriptions

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 .

  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:

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

Acknowledgements

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