Esther Galbrun
email: galbrun@cs.bu.edu

Konstantinos Pelechrinis

Evimaria Terzi
email: evimaria@cs.bu.edu

Safe Navigation in Urban Environments

Advancements in mobile technology and computing have fostered the collection of a large number of civic datasets that capture the pulse of urban life. Furthermore, the open government and data initiative has led many local authorities to make these datasets publicly available, hoping to drive innovation that will further improve the quality of life for the city dwellers. In this paper, we develop a novel application that utilizes crime data to provide safe urban navigation. Given a model that allows us to estimate the relative probability of a crime on any road segment, we define two variants of the SafePaths problem where the goal is to find a short and low-risk path between a source and a destination locations. Since both the length and the risk of the path are equally important and they cannot be combined into a single objective, we approach the urban-navigation problem as a biobjective shortest path problem. Our algorithms aim to output a small set of paths that provide tradeoffs between distance and safety. While the solution space of such biobjective problems can be exponentially large, we design efficient algorithms that effectively exploit its structure and geometry. We enhance these algorithms with early-stopping criteria, which in practice lead to four times shorter running times with minimal sacrifices in the information content they provide to the user. In addition, using crime data from Chicago and Philadelphia we develop the required risk model for their street urban networks. Our experiments with this data demonstrate the efficacy of our algorithms and their practical applicability.

INTRODUCTION

A recent United Nations report states that more than 50% of the world's population currently lives in cities. This percentage is projected to increase to 70% by 2050 [START_REF]United nations-world urbanization prospects: The 2011[END_REF]. One of the main reasons for these levels of urbanization is the long-lived thought of cities as the paramount instrument for innovation and wealth creation. Nevertheless, there are side effects attached to this phenomenon. Cities have become the main source of crimes, diseases and pollution, significantly deteriorating the quality of life of their dwellers.

During the last years, local authorities have collected a large number of civic datasets that capture various aspects of urban life. These datasets include information for street constructions, crimes, bicycle routes, etc. The open government and data initiative from President Obama's administration [START_REF]President Obama's administration-open government initiative[END_REF] has further led many local authorities to systematically collect, organize and publicize such datasets. Besides the transparency of federal and local government operations, this initiative seeks the development of innovative services that will impact people's lives, from the people themselves.

In this paper, we take steps towards this direction. In particular, we focus on one of the major aforementioned problems present in almost every megacity today: crimes and public safety. We develop a novel application aiming to identify safe and short paths for people to take when they navigate the city. For this purpose, we take into consideration both the spatial constraints imposed by the structure of the city's road network as well as the criminal activity in the city. Ideally, prioritizing the safety of dwellers, one would like to provide the user with the safest path from origin s to destination t. However, such a path may incur a significant penalty in the total distance that needs to be traveled. Conversely, the shortest path between s and t may be risky. Therefore, we approach the problem of safe urban navigation as a bicriteria optimization problem where the goal is to provide users with a small collection of paths, each offering a different tradeoff between distance and safety.

As an example, consider the scenario illustrated by Figure 1: a city dweller is at the Philadelphia Museum of Art (s) and wants to return to her home on Wharton Street (t). Her shortest way to home is given by Path 1. However, according to the crime model we develop in Section 4, the itinerary indicated as Path 5 constitutes her safest option, which is also about 1.5 times longer than Path 1. Instead, our art lover may prefer one of the intermediate routes (Paths 2-4), that offer various tradeoffs between distance and risk.

Our approach in a nutshell: Our approach includes an algorithmic and a modeling component. As part of the former, we define the SafePaths problem as a biobjective shortest path problem where the goal is to output a collection of paths that offer different tradeoffs between their length and the associated risk. Of course the space of all possible paths can be extremely large and showing all such paths to the users may be overwhelming. Thus, our goal is to select a small subset of paths that gives a good summary The routes depicted as Paths 1-5 offer various compromises between distance and risk for traveling between s and t.

of the solution space and the available tradeoffs. We study two variants of this generic problem that differ on their definition of the risk of a path. In the first variant, the risk of the path is defined as the total probability of a crime happening along all its segments. In the second variant, the risk of the path is defined as the maximum risk to which the user is exposed on any segment. The key challenge in designing algorithms for these problems stems from the fact that they aim to explore and summarize a possibly exponential solution space. The algorithms we present effectively exploit the structure and the geometry of the underlying solution space and can report a representative set of paths in a matter of seconds. Moreover, we enhance these algorithms with early-stopping criteria which, in practice, lead to 4-fold reduction of the running time with minimal sacrifices in the information content they provide to the user. As part of the modeling component, we develop a framework for the crime risk on street urban networks. We focus on the US cities of Chicago and Philadelphia. After exporting their street networks from OpenStreetMap (OSM) into a graph format we use publicly available crime datasets to assign a risk score to each edge (i.e. street segment).

Roadmap:

The rest of the paper is organized as follows. Section 2 provides the necessary notation and formally defines the SafePaths problem while Section 3 describes our algorithms to solve two specific instances of the problem. Section 4 describes the civic datasets as well as the risk model we developed for the urban road networks. In Section 5 we present our experimental results, and after reviewing the related work in Section 6, we conclude in Section 7.

PROBLEM DEFINITION

In this section, we start by presenting the necessary notation and then formally define the SafePaths problem and its variants.

Preliminaries

Throughout the paper, we will represent the road network using an undirected graph G = (V, E). The nodes of the graph, V , represent intersections and the edges, E, represent the road segments that connect intersections. The focus on undirected graphs is due to the fact that our framework is targeted primarily to pedestrians, since they are more exposed to risks in urban areas. Clearly, such users can traverse street segments in both directions. However, we emphasize that this assumption is not restrictive and the proposed framework can also be used with directed graphs.

Each road segment e ∈ E is associated with two (unrelated) types of weights: its length, denoted by (e), and its risk, denoted by r(e). To reiterate, the length of edge e corresponds to the actual distance between the two intersections connected by the associated street segment, while the risk of edge e should be interpreted as the probability that a crime will be committed on that segment. The exact details of how this model is obtained are given in Section 4.

A path P on G is defined as a connected sequence of edges; a path P from a particular source, s, to a particular destination t is a connected sequence of edges such that the first edge in the sequence has its starting point in s and the last edge in the sequence has its ending point in t. When we want to specify the source and destination nodes of a path P , we denote it by Ps,t.

Clearly, the length of a path P is the sum of the lengths of its edges; that is, (P ) = e∈P (e). The risk of a path P , r(P ), is also a function of the risks of its edges, but we consider two alternative definitions for it: the total-risk, denoted by rt(P ) and the max-risk, denoted by rm(P ).

On one hand, rt(P ) is the probability of a crime happening anywhere along the path, or in other words, on any edge of P . More specifically, it is defined as follows:

rt(P ) = 1 - e∈P (1 -r(e)) .
(1)

On the other hand, rm(P ) is the highest crime probability encountered on any single edge along the path P , that is,

rm(P ) = max e∈P r(e). (2)
Note that both rt(P ) and rm(P ) have a probability interpretation. However, while rm(P ) depends only on the most risky edge of the path, rt(P ) involves the risk of all the edges in P . In both cases, we look for safe paths. That is, we want to minimize r(P ), whether it is instantiated as rt(P ) or rm(P ).

The SafePaths problem

At a high level, the SafePaths problem takes as input the road network G = (V, E) together with a pair of sourcedestination nodes, (s, t), and its goal is to provide to the user a (set of) short and safe paths between s and t.

The difficulty with this high-level problem definition is that clearly, the shortest path (in terms of length) is not necessarily the one with the smallest risk and vice versa. Therefore, the problem we actually want to solve is a bicriteria optimization problem, where the goal is to minimize both the length as well as the risk of the reported path. Of course, there are multiple ways of formalizing, and subsequently, solving such a bicriteria optimization problem. One way to approach it is by combining the two objectives, the length and the risk of the path, into a single objective and ask for the path Ps,t minimizing the weighted combination: Ps,t = arg min P s,t α × (P s,t ) + β × r(P s,t ) , where α and β are appropriately-tuned real-valued coefficients and r(P ) encodes the max or the total risk of P .

Although such a formulation could be an option, it has its shortcomings. First, it is not straightforward to appropriately define the parameters α and β since they depend on the user preference. In this particular case, setting them is even more difficult because (P ) and r(P ) are not measured in comparable units. This latter point also highlights that finding a single path that optimizes the above objective does not have a direct and intuitive interpretation since it is a single solution that optimizes a summation of distances and probabilities.

Exploring the set of all possible paths P: Instead of combining the two objectives into a single one and finding a unique solution with respect to that composite objective, we take a different approach. We look for a small set of paths that provide tradeoffs between the two objectives.

Every path P from s to t is a 2-dimensional point with its x-coordinate corresponding to (P ) and its y-coordinate corresponding to r(P ) (see Figure 2 for an example). Clearly, there are many paths from s to t, corresponding to different 2-dimensional points. Therefore, in order to exhaustively explore the solution space one needs to consider all possible paths and investigate the tradeoffs they offer in terms of length versus risk. From a practical perspective, such an exhaustive exploration of the solution space is infeasible, simply because the number of possible paths can be exponential in the input size.

However, if P is the set of all possible paths from s to t, then not all of these paths are of interest to the user. For instance, consider two paths P1 and P2, such that (P1) ≤ (P2) and r(P1) < r(P2): P1 is better than P2 both in terms of length and risk. In this case, we say that P2 is dominated by P1. Obviously, solutions in P that are dominated by other solutions need not be considered. Since the notion of domination of paths is important for the rest of the discussion we provide a formal definition below.

Definition 1. Given two paths P and P and assuming that their lengths and risks can be computed using functions () and r(), respectively, which are to be minimized, we say that P dominates P if (P ) ≤ (P ) and r(P ) ≤ r(P ) and at least one of the two inequalities is strict, that is, either (P ) < (P ) or r(P ) < r(P ).

We are also not interested in returning equivalent paths, i.e. paths P and P for which (P ) ≤ (P ) and r(P ) ≤ r(P ). In such cases we break ties arbitrarily.

Given the above, we are now ready to define the SafePaths problem:

Problem 1 (SafePaths). If P is the set of all possible paths from s to t, our goal is to select a small subset of these paths S ⊆ P such that for every path P ∈ S, P is neither dominated by nor equivalent to any other path P ∈ S.

Observe that in the above discussion we kept the definition of the risk of the path generic, using r(P ) to denote indistincly the max risk as well as the total risk. We call the instance of the SafePaths problem where the risk of the path is computed using rt(P ) (Equation (1)) the Total-Paths problem. On the other hand, when the risk of P is computed using rm(P ) (Equation ( 2)), we call the corresponding problem the Max-Paths problem.

Observe that Problem 1 asks for a "small" subset of nondominated paths. One can naturally wonder what the right number of paths is. Here we aim to provide the end user with a set of paths that she can easily parse. At the same time, this set should adequately represent the space of nondominated paths.

ALGORITHMS

In this section, we present our algorithms for Total-Paths and Max-Paths. Given a source-destination pair (s, t), the common goal of our algorithms for both problems is to efficiently explore the space of nondominated paths from s to t.

Our algorithms can be more easily understood if we visualize every path P ∈ P as a 2-dimensional point, with its x-coordinate corresponding to (P ) and its y-coordinate corresponding to r(P ). An example of a 2-dimensional representation of some of the paths of P is shown in Figure 2.

For a fixed (s, t) pair, there are two important paths: the shortest path, denoted by P * , and the safest path, denoted by P * r . If they two coincide, then the point that corresponds to the shortest and safest solution dominates all others, and our algorithms report this as the only solution.

When these two paths are distinct, they are both nondominated. Furthermore, they define the "region" of our solutions in their 2-dimensional representation. In fact, all the nondominated solutions will have lengths in the interval [ (P * ), (P * r )] and risks in the interval [r(P * r ), r(P * )]. We propose recursive algorithms for both versions of the SafePaths problem that share the same high-level principle. Starting with the shortest and the safest paths, P * and P * r , they consider in each iteration a pair of nondominated paths Pu and P l and search for an intermediate nondominated path Pi inside the subintervals [ (P l ), (Pu)] and [r(Pu), r(P l )] that they define within the original intervals. This process is repeated recursively with the pairs (Pu, Pi) and (Pi, P l ) until convergence.

Despite their common high-level description, the details of our algorithms for Total-Paths and Max-Paths differ. We describe them in turn in Sections 3.1 and 3.2. We also present speedups which can be applied to both algorithms and lead to significant computational savings, in Section 3.3

Computing shortest paths: In all our algorithms we will often use the Dijkstra shortest path routine. We use the notation Dijkstra(G, f ()) to indicate that we run the Dijkstra shortest-path algorithm on input graph G with weights on edges defined by function f (). That is, the output of Dijkstra(G, f ()) is a path P in G minimizing e∈P f (e).

Algorithms for the Total-Paths

First, let us take a closer look at the two objectives of the Total-Paths problem. For every path P the length of the path, (P ), is written as a summation of the lengths of the edges in P . Moreover, the total risk of the path, rt(P ), given in Equation ( 1), can equivalently be minimized as a summation, namely, as the sum of the negative logarithms of one minus the risk of the edges along the path. Therefore, both our objectives can be computed as summations of (appropriately-defined) weights of the graph edges.

The solution space: Exploring the solution space of such "sum-sum" biobjective shortest path problem is a long-studied research topic and there exist many approaches that aim to find nondominated points [START_REF] Mehlhorn | Resource Constrained Shortest Paths[END_REF] under given thresholds, or identify -pareto sets of points [START_REF] Diakonikolas | Small approximate pareto sets for biobjective shortest paths and other problems[END_REF][START_REF] Vassilvitskii | Efficiently computing succinct trade-off curves[END_REF]. By definition, anpareto set has the following property: every nondominated point is within distance in each of the dimensions from a point in the -pareto set. The problem with identifying all nondominated paths is that there can be exponentially many of them. As a result, finding them can be computationally expensive. Furthermore, reporting an exponential number of solutions to the end user can be very overwhelming in practice and thus, unrealistic and impractical. The advantage of reporting the -pareto set of paths is that they contain a polynomial number of points. However, the known algorithmic techniques for computing them can lead to fairly inefficient algorithms in practice.

In order to avoid such impractical algorithms and outputs, we consider the following alternative: if P is the set of all paths between s and t, we are content with reporting the lower convex hull of P, defined with respect to the 2dimensional representation of the points. We denote the set of points in the lower convex hull as H. Clearly, H ⊆ P and all points in H correspond to nondominated paths.

The Sum-Recursive algorithm: The pseudocode of Sum-Recursive, our algorithm for finding the paths in H, is given in Figure 3. At a high level, the algorithm is a recursive algorithm that repeatedly calls the sum-rec routine. This routine takes as input two nondominated paths Pu and P l and assigns to every edge e of the original graph a composite weight f (e) = r(e) -λ (e), where λ is a real number that depends on the length and the total risk of paths Pu and P l according to the following rule:

λ = r(Pu) -r(P l ) (Pu) -(P l ) .
The shortest path Pi of graph G with weights assigned by f () is computed by Dijkstra(G, f ()). This new path is added to the set H and is used for recursively calling the sum-rec

Algorithms for the Max-Paths

Again, let us take a closer look at the two objectives of the Max-Paths problem. For every path P the length of the path (P ) is again the summation of the lengths of the edges in P . However, now the max-risk of the path, rm(P ), is the maximum of the risks of the edges in P (cf. Equation (2)). Therefore, one of our objectives can be written as a summation of edge lengths and the other as the max of the edges risks, resulting in a "sum-max" biobjective problem. The solution space: This "sum-max" biobjective problem turns out to have a more structured solution space than the "sum-sum" problem we studied in the previous section. More specifically, we have the following observation: Proposition 2. Any set of nondominated and nonequivalent paths in the solution space of the Max-Paths has size polynomial to the size of the input.

The proof is based on the following fact: since the risk of a path corresponds to the risk of a single edge along the path, there can be only as many distinct values for the path risks as there are edges in the network and there can be at most one nondominated path for every such distinct value. The Max-Exhaustive algorithm: The exhaustive algorithm for finding the nondominated paths is straightforward: first, find P * and report this as a nondominated path. Then, identify in P * the edge with the maximum risk and remove from the original graph all edges with risk greater or equal to that value. Find again the shortest path in this reduced subgraph and add the new path into the set of nondominated solutions. Iterate the above process until the source and target are no longer connected. This algorithm, that 6: ρ ← (r(Pu) + t(P l ))/2 7: if ∃e ∈ E, t(P l ) < r(e) < ρ then 8:

P i ← Dijkstra(G r(e)<ρ , ())

9:

if P i = P l then 10:

S ← S ∪ {P i } 11:
max-rec(P i , P l , S)

12:

max-rec(Pu, P i , S) The Max-Recursive algorithm: Instead of going over possible risk thresholds in decreasing order, like Max-Exhaustive, Max-Recursive proceeds by recursion. The pseudocode is given in Figure 4.

At line 8, Max-Recursive runs the Dijkstra routine on G r(e)<ρ , the subgraph obtained from G after removing all edges with risk greater or equal to ρ. By doing so, it identifies the shortest path Pi in G such that rm(P ) < ρ. For algorithmic purposes, we need to remember the threshold with which a path P has been discovered, which we denote by t(P ). Indeed, upon finding Pi, we know that there is no nondominated path with risk between t(P l ) and r(Pi), so we can leave out that range. Given two paths Pu and P l , max-rec considers as risk threshold ρ the mean of r(Pu) and t(P l ). If there exist edges with risk between t(P l ) and ρ, and hence potentially paths with rm inside that range, the Dijkstra routine is run to identify the shortest such path. max-rec iterates with Pu and the new path, as well as with the new path and P l , if they differ.

With Max-Recursive, we need to compute the safest path in the input graph G upfront in order to initiate the recursions. This is done by the Safest routine in the pseudocode of Max-Recursive as follows. First, we compute the minimum spanning tree (MST) of the graph considering the risks of the edges as the weights. The risk ρ * s,t of the safest path between a given pair (s, t) is the maximum risk encountered along the unique path from s to t in this spanning tree. Then, we compute the shortest path verifying this risk threshold by running the Dijkstra routine on G r(e)≤ρ * s,t to obtain P * r . Note that its length will generally differ from the length of the path connecting s and t in the spanning tree.

Figure 2 illustrates a run of this algorithm. First, the shortest path (P * ) and safest path (P * r ) are found, then ρ1 is used as threshold, finding P1. The next thresholds are ρ4 and ρ2 in the upper and lower side respectively, and so on.

Since we are not looking for a unique solution we explore both sides after a binary split. Thus, the worst-case complexity of this approach is the same as the exhaustive search. In fact, the advantage of Max-Recursive only appears when combined with the approximation speedup discussed in the next section, which cannot be applied to Max-Exhaustive.

Computational speedups

In this section we describe our strategies for speeding up the above algorithms, applicable to both versions of the SafePaths problem. Approximation via early stopping: The running time of our algorithms for both versions of the SafePaths problem depend linearly on the number of points in the set of paths returned by the algorithms. Therefore, one way of speeding up the algorithms is by reporting a subset of those paths. Hence, by restricting the number of iterations of the Sum-Recursive and the Max-Recursive we contribute to both of our aforementioned objectives, i.e., reducing the runtimes and limiting the size of the reported solution sets.

Specifically, consider the shortest and the safest paths with 2-dimensional representations ( (P * ), r(P * )) and ( (P * r ), r(P * )) respectively, defining a rectangle of area A. Before calling the recursive routine with two paths Pu and P l , we check the area of the unexplored rectangle between them. If this area becomes smaller than a chosen fraction γ of A we stop the iteration. With sum-rec, the unexplored rectangle for paths Pu and P l is delimited by ( (Pu), r(Pu)) and ( (P l ), r(P l )). With max-rec, it is delimited by ( (Pu), r(Pu)) and ( (P l ), t(P l )), since we know there is no nondominated path with risk between t(P l ) and r(P l ). In Figure 2 for instance, with γ = 0.1, since the hatched area is smaller than onetenth of A, the total area of the solution space (delimited by a grey solid line), the recursive routine is not called for P3 and P2. In summary, the choice of γ directly limits the number of iterations and the number of paths in the solution; larger γ results in fewer paths returned and shorter runtimes.

Pruning: Our pruning strategy, which we call the Ellipse pruning, is based on the following observation: any path between s and t that is longer than the safest path, will be dominated by it.

This observation has the following consequence: if L is the length of the safest path between s and t, then any node u such that the sum of the distances "as the crow flies" from s to u and u to t is greater than L cannot be part of the solution. This criterion defines an ellipse with foci s and t and major axis of length L. Hence, after finding P * r we can safely remove any node that lies outside the ellipse, thereby reducing the size of the graph processed in subsequent calls to the Dijkstra routine.

This observation is pictorially depicted in Figure 5. The safest path between s and t is shown in green and its length L defines the length of the major axis of the ellipse drawn in red. Any node located outside this ellipse can be discarded from further computations for the pair (s, t).

We combine the Ellipse pruning with another simple pruning technique: we split the area that corresponds to the city (or neighborhood) of interest into a grid and project the graph G on this grid. Then, instead of considering the original graph we only consider the grid cells that are included into or overlap with the ellipse, for instance, the eleven cells marked with a star in the example shown in Figure 5.

Note that the Ellipse pruning reduces the size of the input graph, without sacrificing the accuracy. That is, the set of nondominated paths before and after the Ellipse pruning remains the same.

MODELING CRIME DATA

In this section, we describe the civic datasets that we will use in our experiments. More specifically we explain how we combined data from different sources in order to form the input to our algorithms.

Urban road network: We extract the actual road network of a city using OpenStreetMap (OSM) [1]. OSM is a crowdsourcing-based open platform, which aims to make the world map freely available. The OSM community has developed a number of tools that facilitate the integration of OSM maps with a variety of applications. For our purposes we make use of the osm4routing parser [START_REF]osm4routing[END_REF], that exports the map of interest from an OSM format (appropriate for traditional GIS systems) to a graph-based format (appropriate for graph-based algorithms).

In particular, each node v in the exported graph G corresponds to an intersection, while each edge e represents a street segment that connects two intersections. osm4routing provides additional information about the intersections and the street segments as node and edge attributes. Specifically, the geographical location (latitude/longitude pair) of each node is provided. Each edge e is annotated with a variety of features. The following ones are of particular interest for our study:

-Length (e), the physical length of the corresponding street segment. It is the length value we associate with every edge in our input graph. -Geometry Γ(e), a sample set of discrete latitude/longitude points from the street segment. It essentially provides information about the actual geographic shape of the street segment. -Accessibility flags, indicators that capture the accessibility of a street segment by car, bicycle and foot. Here, we consider the pedestrian street network of Chicago and Philadelphia. We obtained the OSM maps for the metropolitan areas of these two cities from Metro Extracts [START_REF]Osm metro extracts[END_REF].

Crime datasets: In addition to the above, we also use two civic datasets made available by the cities of Chicago 1 and Philadelphia 2 that encode information about crimes in the two cities for the one year period between October 2012 and September 2013. Their formats do not align, as it is true with the majority of civic datasets made available from different cities even when they aim to convey the same information. Nevertheless, some basic information that both Risk model: A risk model for the urban road network is essentially an assignment of a risk score r to each edge that is proportional to the probability of a crime happening on the corresponding street segment. Note that we do not intend to infer the exact risk probability of individual edges with this model. Rather, we are interested in the relative values of r for different edges and the fact that they can be interpreted as probabilities.

Our model is built in a two-step process. First, we use the geographic coordinates of the crime incidents to compute a spatial density for the crime activity by applying a Gaussian kernel density estimation (KDE). Given n points of crime incidents c1, c2, ..., cn on a 2-dimensional plane, the Gaussian kernel estimates the density of crime activity at point p as:

λ(s) = 1 nh 2 n i=1 1 √ 2π exp(- ||ci -p|| 2 2 2h 2 ), (3)
where ||ci -p||2 is the euclidean distance between points ci and p and h is the bandwidth used. The bandwidth h dictates the spread of the Gaussian kernel that is centered at each datapoint and hence, it controls the smoothness of the estimated density. Small values of h can capture more detail while large values of h lead to smoother estimation. In other words, it is the analogue of the bin width of a histogram. We determine h according to Scott's rule [START_REF] Scott | Multivariate Density Estimation: Theory, Practice, and Visualization[END_REF]. Figure 6 visualizes the estimated densities for the two cities. As we can observe, crimes are not uniformly distributed over the metropolitan areas of the two cities but there are hotspots of crimes, something expected based both on our experience as city-dwellers as well as on existing literature in a variety of fields (e.g. [START_REF] Chainey | The utility of hotspot mapping for predicting spatial patterns of crime[END_REF][START_REF] Ratcliffe | Crime Mapping: Spatial and Temporal Challenges[END_REF]).

Once the density function is estimated, we evaluate it on the actual road segments. For this purpose, we make use of the geometry Γ(e) of each edge e of the road network. Evaluating Equation (3) on every point ξ i ∈ Γ(e) and summing up we obtain the crime density Λ(e) on road segment e: Λ(e) = ξ i ∈Γ(e) λ(ξ i ). Finally, we compute the risk weights for every edge e as the normalized densities: 7 depicts the empirical distributions of edge lengths (left) and risks (right) over the two networks. In both cities, most edges span a short geographic distance, that is, less than 250m. There are few edges spanning long distances, 4km and above (not shown), that most likely correspond to highways. Similarly, the distributions of risks are highly right-skewed for both cities, which essentially indicates that while most edges are assigned low risk values, there exist street segments that are comparatively dangerous and exhibit much higher risk values.

We point out that our model does not involve time, but can be easily extended with a temporal dimension. In particular, we can quantize the time depending on the granularity required by the application (e.g. hourly bins) and consider separately crimes that happened during each time period. Then the density (Equation (3)) and the final risk values (Equation ( 4)) will also be functions of time, and we will be able to set the weights according to the time of the query from the user, resulting in a time dependent version of the SafePaths problem. Nevertheless, handling the temporal dimension is beyond the scope of our work and we ignore it in our experiments.

EXPERIMENTS

In this section, we present an experimental assessment of our proposed methods. Our main objective is to evaluate the practical utility of our algorithms. We focus on two aspects: (i) the representativeness of the small set of nondominated paths that our algorithms return and (ii) their runtime.

We build our evaluation benchmark by sampling node pairs from both cities. To ensure a good coverage of scenarios involving short distances, which are of particular interest for a pedestrian urban navigation system, we perform distance-aware sampling. More specifically, we sample 100 nodes for each city. Then, for each of these source nodes, we divide the remaining nodes into classes based on their distance "as the crow flies" from the source. Considering Table 2: Summary of the solution sizes. We indicate the total number of solutions, number of singletons and of twopaths solutions (|S| = 1 and |S| = 2) and number of approximations multi-paths solutions identical to the exact solution. We run our algorithms for the Total-Paths and the Max-Paths problems for each of the pairs on their respective road network. For each run, we obtain a set of paths offering different tradeoffs between distance and safety. For instance, Figure 1 depicts an actual solution of 5 paths to the Total-Paths problem for a pair of nodes in Philadelphia.

Total-Paths

The 2-dimensional representation of a solution consisting of 8 paths to Max-Paths for a pair of nodes in Chicago is plotted in blue in Figure 2. As we explained previously, a path P can be represented in a 2-dimensional space by a point whose x and y-coordinates correspond to (P ) and r(P ) respectively. Given a pair of nodes, the shortest and safest paths joining them, P * and P * r , define a rectangle R. A solution to the SafePaths problem is a set of paths S including P * and P * r . In the 2-dimensional space, S can be represented with a curve that starts from P * , ends at P * r and passes through intermediate nondominated paths in S across R. Formally, given a solution S = (P * , P1, P2, . . . , P * r ), where the paths are ordered by increasing length, the corresponding curve is defined by: ( (P * ), r(P * )), ( (P1), r(P * )), ( (P1), r(P1)), ( (P2), r(P1)), . . . ( (P * r ), r(P * r )). Based on this representation, each solution is associated with an area: the area of R located under the curve. Continuing on our example in Figure 2, the area associated with the 8-paths solution is colored in blue. Paths offering good tradeoffs correspond to points close to the bottom left corner of R. Hence, solutions containing good tradeoffs are associated with small areas (relative to the total area of R).

Approximations: The representativeness of our algorithms can be captured through their goodness of approximation as compared to the exact algorithms for the corresponding problems. In particular, we compare the exact algorithms Sum-Recursive (for Total-Paths) and Max-Exhaustive (for Max-Paths), to both recursive algorithms with applying the approximation via early stopping -described in Section 3.3. For the latter we use three different values for the stopping criterion γ, namely, 0.05, 0.10 and 0.20. We denote each of the above four runs for either problem by E, A5, A10 and A20, respectively.

Our goal is to evaluate the ability of our proposed approx- imations to capture the landscape of nondominated paths.

When the shortest and the safest paths coincide (i.e. |S| = 1) or when there are no intermediate paths between P * and P * r (i.e. |S| = 2), the approximations trivially return the same solution as the exact algorithms. Solutions containing intermediate paths (i.e. |S| > 2) are called multi-paths solutions. The counts of singletons and two-paths solutions found for both cities and both problems are reported in Table 5. In addition, we also report the number of multi-paths solutions found with the approximations that are identical to the exact solutions. For instance, with the stricter approximation A5 for the Total-Paths problem in Chicago, 111 + 182 + 520 = 813 solutions out of 2400 obtained are identical to the exact solutions, as compared to only 630 with the looser approximation A20. The difference is even more pronounced for the Max-Paths problem.

Still, we would like to measure the quality of the approximations beyond strict equality of the solution sets. For this purpose, we compare the area associated with the solution obtained with an approximation, denoted as SA, with the area associated with the solution returned by the exact algorithm, denoted as SE. Note that since the approximate solution is a subset of the exact solution, we have SE/SA and While remaining of high quality (average area ratios SE/SA almost always lie above 0.8), the approximations clearly deteriorate for larger distances and especially for A20. This is due to the fact that the average number of paths in the solutions returned by the exact algorithms increases as distances expand while the number of paths in the solutions with approximations is capped. The number of paths per solution averages between 7.83 and 16.33 and reaches up to 144 for the exact algorithms, while approximate solutions never contain more than 8 paths, with an average between 2.93 and 4.3 depending on the scenario. As expected, the runtime scales linearly with the size of the solution. Hence, com-bining the algorithms with approximations yields notable reductions in the runtimes, especially for larger distances.

In summary, by using moderate approximations (e.g. A10) we obtain very satisfactory solutions containing a small number of paths, with shorter and more predictable runtimes, supporting the practical utility of our algorithms.

For the same problem, discrepancies arise between the two cities due to characteristics of their respective road networks and crime distributions. For instance, because of the Delaware river that runs through Philadelphia, the walking distance between nodes on either side of the river is much greater than their distance "as the crow flies". Hence, the closer distance classes contain pairs for which the shortest path is much longer than expected. Besides, crime locations are more spatially clustered in Chicago (see Figure 6) so the KDE for the crime activity is less regular, yielding a greater variety of risk thresholds in the Max-Paths problem.

Pruning: Next, we investigate the benefits of applying the Ellipse pruning described in Section 3.3. These pruning techniques discard nodes that are too far away from s and t to be part of nondominating solutions. The first pruning technique, denoted by LN, filters individual nodes while the second, denoted by LG uses a grid and filters entire cells at once. Both techniques only affect the runtime of the algorithms without impacting the solutions.

For this experiment, we focus on the Sum-Recursive and Max-Recursive algorithms combined with approximation using γ = 0.10, as they represent the most practical scenario. The runtimes in seconds on the Chicago network for these algorithms with and without the pruning techniques are reported in Figure 5.

LN drastically reduces the size of the input graph of the Dijkstra routines, as witnessed by the very short span of runtimes. However, the pruning operation itself imposes a large overhead which takes away most of the benefits of using this method. This is particularly evident for the Total-Paths problem, where the average runtime with the pruning is almost equivalent to the average runtime of the original algorithm, if not greater.

On the contrary, LG does not suffer from this drawback. While selecting whole cells at once is suboptimal in terms of the reduction of the graph, it can be performed more efficiently, resulting in an overall gain for both problems. Tuning the size of the grid provides a means to adjust the balance between stringency and speed of pruning. Here, after a short exploration, we chose a grid of 20 × 20 cells.

When the source and target nodes are far apart, the ellipse covers the graph almost entirely. Then, no node can be discarded and pruning only adds overhead runtime. However, such situations can be easily detected and the pruning can be abandoned.

RELATED WORK

Our work is related to research on modeling crime events and on recommending routes to city dwellers, as well as to theoretical work on biobjective optimization problems. Here, we review these lines of research and their connections to our framework.

Crime event models: Crime events are neither random nor uniform [START_REF] Ratcliffe | Crime Mapping: Spatial and Temporal Challenges[END_REF], but they exhibit spatial and temporal patterns. Large research efforts focus on the development of specialized systems for crime mapping [START_REF] Maltz | Mapping Crime in Its Community Setting: Event Geography Analysis[END_REF][START_REF] Chainey | GIS and Crime Mapping[END_REF][START_REF] Scott | Extend crime analysis with arcgis spatial statistics tools[END_REF] that can be used by law enforcement agencies to study and analyze crime patterns and to inform their decisions on strategies against crime. While these methods can visualize events in the physical urban environment, there is also a large volume of urban and social literature that attempts to explain the reasons behind the observed patterns of crimes [START_REF] Brantingham | Patterns in Crime[END_REF][START_REF] Cohen | Social change and crime rate trends: a routing activity approach[END_REF][START_REF] Cornish | The Reasoning Criminal: Rational Choice Perspectives on Offending[END_REF]. Such theories can also provide guidelines for policies that aim to prevent crimes. For instance, environmental criminology studies the relation between crime events and the spatio-temporal context of people's activities [START_REF] Brantingham | Patterns in Crime[END_REF]. Apart from these theories, there is a surge in studies that aim to identify and exploit patterns in historical crime data, hoping to forecast crimes (e.g. [START_REF] Wang | Learning to detect patterns of crime[END_REF][START_REF] Yu | Crime forecasting using spatio-temporal pattern with ensemble learning[END_REF][START_REF] Liu | A comparison of logistic regression, classification and regression tree, and neural network model in predicting violent re-offending[END_REF][START_REF] Berk | Statistical procedures for forecasting criminal behavior: A comparative assessment[END_REF]). These efforts have produced an arsenal of software tools that is available to law enforcement for proactive policing (e.g. COPLINK [START_REF] Hauck | Using coplink to analyze criminal-justice data[END_REF], ESRI's GIS platform [START_REF]Predicting crime using analytics and big data[END_REF]).

While we are unable to present an exhaustive account of the corresponding literature, we emphasize here that our study is complementary in two ways: firstly, we propose computational methods relying on combinatorial algorithms that use crime data to recommend routes. Secondly, our algorithms could be combined with forecasting systems that project/update the probabilities of crime in the various street segments for upcoming path queries.

Urban navigation: Systems with new navigation objectives that go beyond the shortest path have recently appeared in the literature [START_REF] Ayala | An evaluation of multiobjective urban tourist route planning with mobile devices[END_REF][START_REF] Maruyama | P-tour: A personal navigation system for tourism[END_REF][START_REF] Choudhury | Automatic construction of travel itineraries using social breadcrumbs[END_REF][START_REF] Gionis | Customized tour recommendations in urban areas[END_REF][START_REF] Gonzalez | Adaptive fastest path computation on a road network: A traffic mining approach[END_REF][START_REF] Kanoulas | Finding fastest paths on a road network with speed patterns[END_REF][START_REF] Sharker | Health-optimal routing in pedestrian navigation services[END_REF][START_REF] Yuan | T-drive: Enhancing driving directions with taxi drivers' intelligence[END_REF]. Such objectives include the recommendation of healthy routes (i.e. maximizing physical activity) [START_REF] Sharker | Health-optimal routing in pedestrian navigation services[END_REF], routes tailored to the personal interests and spatiotemporal constraints of users [START_REF] Ayala | An evaluation of multiobjective urban tourist route planning with mobile devices[END_REF][START_REF] Maruyama | P-tour: A personal navigation system for tourism[END_REF][START_REF] Choudhury | Automatic construction of travel itineraries using social breadcrumbs[END_REF][START_REF] Gionis | Customized tour recommendations in urban areas[END_REF], or routes that take into account traffic information gathered from historical speed patterns and GPS devices [START_REF] Gonzalez | Adaptive fastest path computation on a road network: A traffic mining approach[END_REF][START_REF] Kanoulas | Finding fastest paths on a road network with speed patterns[END_REF][START_REF] Yuan | T-drive: Enhancing driving directions with taxi drivers' intelligence[END_REF]. To the best of our knowledge we are the first to consider the biobjective problem of safe and short routes.

Biobjective shortest paths: From a computational viewpoint, our work is related to research on biobjective optimization and, more specifically, biobjective shortest paths [START_REF] Diakonikolas | Small approximate pareto sets for biobjective shortest paths and other problems[END_REF][START_REF] Mehlhorn | Resource Constrained Shortest Paths[END_REF][START_REF] Vassilvitskii | Efficiently computing succinct trade-off curves[END_REF]. Such methods either aim to identify the optimal path with respect to one objective given a threshold on the other, a problem known as the resource constrained shortest path [START_REF] Mehlhorn | Resource Constrained Shortest Paths[END_REF], or they try to report a polynomial number of points that are close enough to all nondominated points [START_REF] Diakonikolas | Small approximate pareto sets for biobjective shortest paths and other problems[END_REF][START_REF] Vassilvitskii | Efficiently computing succinct trade-off curves[END_REF]. The Total-Paths problem could potentially benefit from the above studies, had the existing methods been more efficient in practice. Thus, while we acknowledge this literature, we resort to an algorithm that only explores the lower convex hull of the solution space. In fact, this algorithm was proposed as a subroutine to the enumeration methods of Mehlhorn and Ziegelmann [START_REF] Mehlhorn | Resource Constrained Shortest Paths[END_REF]. On the other hand, the Max-Paths problem proves to have a much more structured solution space, allowing us to identify complete sets of nondominated paths.

CONCLUSIONS

In this paper, we developed practical algorithms for safe urban navigation. In particular, we formalized the SafePaths problem as a biobjective optimization problem and set as our goal to identify a small collection of nondominated paths that provide different tradeoffs between distance and safety. We explored two variants of this problem and designed efficient algorithms for solving them involving approximation and pruning techniques.

Based on civic datasets from Chicago and Philadelphia, we built a crime event model for the urban road networks of these two cities, which was obtained from OpenStreetMap. Our experimental evaluations showed the efficacy and the efficiency of our algorithms and demonstrated the practicality of biobjective optimization formulations in this setting.

Figure 1 :

 1 Figure 1: An illustrative example of safe urban navigation. The routes depicted as Paths 1-5 offer various compromises between distance and risk for traveling between s and t.

4 Figure 2 :

 42 Figure 2: The 2-dimensional representation of paths from the solution space P of a SafePaths instance.

Figure 3 :

 3 Figure 3: The Sum-Recursive algorithm for the Total-Paths problem.

4 :

 4 Input: A graph G with edge weights () and r(). Output: The set S of nondominated bicriteria paths for Max-Paths. 1: P * ← Dijkstra(G, ()) 2: P * r ← Safest(G, r()) 3: S ← {P * , P * r } max-rec(P * , P * r , S) 5: return S Routine max-rec(Pu, P l , S)

Figure 4 :

 4 Figure 4: The Max-Recursive algorithm for the Max-Paths problem.

Figure 5 :

 5 Figure 5: Illustration of the Ellipse pruning.

Figure 6 :

 6 Figure 6: KDE for crime activity in Chicago (left) and Philadelphia (right).

Figure 7 :

 7 Figure 7: Empirical probability density functions of edge lengths (left) and risks (right) for Chicago (blue dashed line) and Philadelphia (green solid line).

Figure 8 :Figure 9 :

 89 Figure 8: Results for Total-Paths on Chicago.

Figure 10 :Figure 11 :

 1011 Figure 10: Results for Total-Paths on Philadelphia.

A 10 L N L G D 1 A 10 LA 10 L N L G D 3 A 10 L N L G D 4 A 10 L N L G D 5 Figure 12 :

 1011010310410512 Figure 12: Runtime for pruning on Chicago.

Table 1 :

 1 Statistics of the road networks.

		|V |	|E|
	Chicago	57 998	91 695
	Philadelphia	55 234	82 676
	metropolitan areas of Chicago and Philadelphia, respectively.
	Their node and edge counts are given in Table 1 and as we
	can see they are fairly similar.
	Figure


Esther Galbrun
email: galbrun@cs.helsinki.fi

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

A Case of Visual and Interactive Data Analysis: Geospatial Redescription Mining

We present a method for visual and interactive geospatial redescription mining. The goal of geospatial redescription mining is to characterize geospatial areas using two different descriptions, such as their bioclimatic features and fauna. Indeed, one application of geospatial redescription mining is finding bioclimatic niches, i.e. explaining the distribution of species using their bioclimatic envelope. Allowing users to find the geospatial redescriptions in an interactive way, and to see the results in clear visualizations, is fundamental for the applicability of the method. We present several goals we think a good interactive and visual redescription mining method should fulfil, and we explain how our proposed method achieves (most of) them. Finally, we also discuss some open problems in interactive redescription mining.

Introduction

Finding multiple ways to characterize the same entities is a problem that appears in many areas of science. Describing geographical regions in terms of both their bioclimatic conditions and the fauna that inhabits them is one instance in the field of biology. 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 actually the redescription shown in the foreground panel of Figure 1.

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.

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

To analyse the redescriptions, the ability to visualize the support sets is very helpful. When building a tool for mining redescriptions from geospatial data, plotting the support on a map, as in the foreground panel of Figure 1, is a natural visualization. But a static display of the results is not enough: the user must also be able to interact with the program. This interaction can be conceptually divided into two sub-phases: interacting with the data mining algorithm and interacting with the result visualization. The analysis is an alternation of these two phases, with the user moving back-and-forth between issuing commands to find new results and examining obtained ones. We argue that a good interactive data mining tool should support both types of interaction and facilitate the alternation between different phases.

In this paper we give a systematic outline of contributive features to fulfill that aim, considering the example of mining geospatial redescriptions. We then present a pair of algorithms, ReReMi and Siren, and explain how they implement interactivity and visualization for that task. Lastly, we discuss some possible pitfalls associated with interactive, visual mining. But first, we formally define the redescription mining problem.

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]. In [START_REF] Galbrun | From Black and White to Full Colour: Extending Redescription Mining Outside the Boolean World[END_REF], we extended redescription mining to categorical and numerical variables.

More formally, we consider data that contains entities E with two sets of characterizing variables, e.g. the fauna and the bioclimatic conditions. 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 denoted using Iverson bracket [v = c] and [a ≤ v ≤ b], respectively, where c is some category and [a, b] an interval. For more details about how the actual optimal categories and intervals are chosen, please refer to [START_REF] Galbrun | From Black and White to Full Colour: Extending Redescription Mining Outside the Boolean World[END_REF]. These truth assignments and their negations constitute literals which can be combined using the Boolean operators ∧ (and) and ∨ (or) to form queries. The support of a query q is the subset of entities for which the query holds true, that is supp(q) = {e ∈ E : q is true for e}. We refer to the two sets of variables informally as left and right hand side data, and the queries over them as left and right hand side queries, denoted as q L and q R , respectively. Then, a redescription is simply a pair of queries over variables from the two sets, R = (q L , q R ). Its accuracy is measured using the Jaccard coefficient

J(R) = J(q L , q R ) = |supp(q L ) ∩ supp(q R )| |supp(q L ) ∪ supp(q R )| .
We compute a p-value that represents the probability that two random queries with marginal probabilities (i.e. the fraction of entities supporting them) equal to those of q L and q R have an intersection equal to or larger than |supp(q L , q R )|. This probability uses the binomial distribution and is given by

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

The task consists in finding significant accurate redescriptions, in other words, pairs of queries, one query for both sets of variables, such that both queries describe almost the same set of entities.

When the data is geospatial, that is, the entities are connected to geographical locations, the task is called geospatial redescription mining. A meaningful geospatial redescription should define coherent areas using expressive queries.

Niche-finding is a particular instance of geospatial redescription miningand a task of great importance for biologists. 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 years to model the bioclimatic envelope, Maxent [START_REF] Phillips | Maximum entropy modeling of species geographic distributions[END_REF] and BIOMOD [START_REF] Thuiller | Biomod -a platform for ensemble forecasting of species distributions[END_REF], being good examples of modelling tools used in this domain. The former provides a graphical user interface while the latter is a text-based tool. But to the best of our knowledge, none of these methods allows automatically finding both the set of species and their envelope.

Goals for Interactive and Visual Redescription Mining

In this section we discuss our goals for an interactive and visual redescription mining tool. Some of these goals are general to any interactive and visual data mining tool (and we spend less time on discussing why they are desirable), some are specific to redescription mining. We divide the discussion between interaction and visualization, though we emphasize that these goals are not independent.

Visualization of Results

As a basis for our discussion, we use the taxonomy of interactions for visual analytics proposed by Heer and Shneiderman [START_REF] Heer | Interactive dynamics for visual analysis[END_REF]. The bold-face terms correspond to their taxonomy.

The most fundamental goal when designing a tool for visual data analysis is, of course, to have a good visualization. With geospatial redescriptions, a map is the most natural option. Thus our tool should be able to plot the redescriptions on a map. But in order to effectively select the content of the visualizations, the user needs means to filter and sort the results mined. In the case of redescription mining, the user should be able to sort the returned redescriptions based on different criteria, such as accuracy, support size, statistical significance, or query length (i.e. number of literals). To some extent, filtering can be regarded as sorting with a cut-off value. Hence, sorting should naturally use the same criteria and similar results display as sorting. Additional criteria might affect sorting, including the described geographical area and redundancy.

During the analysis, the user should be allowed to derive new data. That is, new variables obtained by aggregating existing variables might better capture the studied phenomenon. Hence, their introduction during the mining process would support the analysis. While modifying the way the information is represented, deriving new variables is also a means to interact with the mining process.

In order to manipulate the views, the user needs to be able to select the data he wants to visualize. In the present case, he can primarily choose a redescription to plot. Then, he can edit the queries, modifying literals and altering the bounds of real-valued variables. The user might need to navigate inside the view, typically looking first at the redescription over the whole area, before zooming and panning to see more details. On a high level, the user might only be able to see whether either query hold on a region. Focusing on particular area, he might obtain more detailed information about the actual state of the variables and what makes a query hold or not in a particular location, for instance by clicking or hovering over a dot in the map. Several views and the data might need to be coordinated. Modifications made to a redescription should be reflected immediately on the map(s). In addition, it could be useful to allow the user to bind maps together, so that panning and zooming are applied to all maps simultaneously. In that way, detailed comparison of the support of different redescriptions would be facilitated. Maps can be opened in detachable tabs, to be inspected side by side or sequentially and be organized using the system's or a dedicated windows tiling.

For any interactive tool, undo and redo are minimal functionalities to allow reverting actions, making interaction safe and comfortable. The user should be able to save the current status of the analysis process, i.e. all current redescriptions, opened lists and maps to punctuate the process. Recording the interaction history and turning it into editable and parameterizable macros provides a mean to repeat a sequence of actions and automate repetitive tasks. The tool should support annotation in order to keep track of the thought path during the analysis. For example, this could be achieved by generating annotable screen shots of the current window of interest, and by adding comments to the interaction history and macros. Organizing the history and macros into blocks would help to further clarify the logical structure of the analysis. Furthermore, with the ability to link to objects in the current environment, such as redescriptions, groups of entities or literals, these could be explicitly related to each other. Data analysis is often a collaborative effort, involving several users. Then, sharing information becomes crucial. Easy export and import of redescriptions lists, maps and macros, possibly with comments and annotations is a very important feature towards that aim. Finally, giving clear names to the actions and providing feedback on their application helps guiding users along the analysis process. Example macros with detailed explanations, to be replayed step-by-step, represent a good means to introduce new users to the tool. These latter goals pertain automating interactions, attaching a meaning to sequences of interactions, allowing segmented interactivity, e.g. when different users collaborate, using the tool in turn. Hence they are also closely tied to the interaction with the mining process, to which we now turn.

Interaction with the Mining Process

A desirable behavior for an interactive program is the production of meaningful results at any time. In other words, if the mining process is stopped, it can nevertheless return results which are valid, albeit possibly partial. This is related to the possibility to obtain preliminary results while the mining is still underway. Such a feature contributes to the ability of the program to respond quickly to instructions from the users. It is also possible to first run the algorithm allowing only short queries, say, at most a couple of literals on either side, and let the user choose the ones that seem promising and should be further extended. Low latency or even instantaneity is a core quality of an interactive tool and is important to catch and keep the user's attention. At least, the tool should provide instant feedback about what is happening.

The automation level of the whole mining process could be adaptative. From fully manual, where the users writes down redescriptions and the tools simply evaluates them, to fully automated where the program mines the list of best redescriptions using static predefined constraints, it could also be partially automated, with the tool suggesting best extensions at each step and asking for approval from the user.

Consider extending an existing redescription with a real-valued literal. Instead of a map plot based on their geographical location, a figure where the areas are represented as colored dots plotted along the x-axis depending on the value taken by the chosen variable would be useful for determining the optimal interval for that variable. Indeed, the user could observe which values occur in locations that belong to different parts of the current redescription. Then, he could fix the bounds in consequence, for example using sliders. The tool could even indicate which are the best bounds but also update the best corresponding upper bound when the user moves the lower bound, and vice versa. This is a prime example of instant interaction with the mining process through apt visualization.

Proper interactivity with the program also requires allowing the user to specify constraints for the search. Possible constraints include specifying variables or geographical areas that should be excluded from the redescriptions or modifying the minimum acceptable accuracy. For such constraints that constitute filtering criteria, there can be three different degrees of integration with the algorithm, that is, depending on how far they are pushed into the mining process instead of applied a posteriori. The degree zero of integration happens when the user manually filters the raw output. Instead, the program can automatically filter its results before reporting. The highest degree of integration implies incorporating such filtering criteria during the search to avoid generating the unwanted results in the first place. Still, a compromise needs to be found between supporting deep integration and accepting a broad range of constraints, e.g. through a flexible specification framework. Indeed, these are typically two conflicting goals.

More generally, the user should be able to specify interest and lack of it. Selecting a redescription to be edited and extended is a way of expressing curiosity towards the involved conditions or area. Similarly, he should be able to prevent the algorithm to search further in directions he deems uninteresting. One way of doing so is to merely pick out variables or locations that should be ignored.

Another way is to select a redescription and specify that results of this kind are of no interest.

Our Proposed Tool

In this section, we present our proposed tool, which consists of a pair of algorithms, ReReMi and Siren. First, we explain how it implement interactivity and visualization for redescription mining. Then, we give a concrete illustration of its usage by means of a use case. The current version of the tool is only able to achieve part of the goals stated in the previous section. In this section we focus on presently available features-the others are châteaux en Espagne.

The Algorithms

Siren is an interactive tool for mining and visualizing geospatial redescriptions. 3At its core is the ReReMi redescription mining algorithm [START_REF] Galbrun | From Black and White to Full Colour: Extending Redescription Mining Outside the Boolean World[END_REF].

This greedy algorithm uses an efficient on-the-fly discretization technique to extend redescription mining to categorical and numerical variables. It considers queries over such variables that can be parsed in linear order, without trees, with every variable allowed to appear only once. They constitute a subset of Boolean formulae that provides a good compromise between expressive power, difficulty of the search, and interpretability.

Yet, the search space remains exponential and we still resort to heuristic pruning. 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. 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.

Redescriptions with too high p-value can be filtered out during the search. We exploit some simple observations to make the computation of accuracy more efficient. This allows to evaluate candidates faster, which is particularly important for an interactive tool.

Owing to his beam-search-like behaviour, ReReMi is an any-time algorithm. The intermediate redescriptions explored during the search are returned at each step. This way, the user is able to see the candidates present in the beam and might stop the extension process if he so wishes. The possiblilitty to remove a candidate from the beam, cutting off a less promising branch from the search, remains to be implemented.

In Siren, threading is employed to delegate mining tasks to ReReMi in the background. This preserves the tool's responsiveness while the communication is maintained to provide feedback about the ongoing mining, to return results as they are obtained and to allow the user to directly interact with the process.

Finally, Siren allows automatic filtering of redundant redescriptions. That is, redescriptions that cover approximately the same area even if they have (somewhat) different sets of variables. 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.

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.

Use Case

We exemplify the usage of Siren by going through a generic work-flow of mining geospatial redescriptions, detailing typical steps in the process. This specific example concerns the application of Siren on the task of bioclimatic niche finding using data that describes spatial areas of Europe, squares of side roughly 50 kilometers. The left hand side data contain information about the mammals that live in these areas, while the right hand side consists of bioclimatic variables 4 . Nonetheless, Siren is a flexible tool that can be used with different datasets from various application domains.

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 within Siren by running the extension mechanism on an empty redescription. Following the principle of first providing an overview of the results then focusing on specific items, the redescriptions found are presented as a list from which the user can select a redescription of his choice to examine more closely and plot on the map. Figure 1 shows two panels, containing an overview of the current results as a list, in the background, and a single redescription plotted on a map, in the foreground. The list supports sorting and filtering on various criteria.

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 automatically extend a given redescription, i.e. let the algorithm add new literals to the queries to make the redescription as accurate as possible.

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. Here, the best found extension has accuracy 0.665 (per Jaccard coefficient):

Southwestern Water Vole ∨ Gray Dwarf Hamster ∨ Savi's Pine Vole ∨ Mediterranean Monk Seal [11.2 ≤ t + 3 ] ∧ [0.51 ≤ t = 1 ≤ 11.333] ∧ [42.75 ≤ p = 10 ≤ 131.81] ∧[50.556 ≤ p = 11 ≤ 176.75],
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.

Returned extensions can be plotted on maps opened inside several windows, so as to be visualized side by side and compared as shown in Figure 2. 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 instantly 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. 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:

Southwestern Water Vole ∨ Cape Hare ∨ Savi's Pine Vole ∨ Mediterranean Monk Seal ([11.2 ≤ t + 3 ] ∧ [20.1 ≤ t + 7 ≤ 32.9] ∧ [0.51 ≤ t = 1 ≤ 11.333]) ∨ [34.0 ≤ t + 8
]. Note that this redescription was not returned previously since the beam search focused on better ones involving precipitation variables. In addition to basic parameter tuning, this feature allows the user to specify additional constraints, thereby interacting with the mining process to adjust it according to his interest and what appears most promising during the analysis.

Filtering redundant redescriptions. 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.

Sharing the results. Finally, Siren facilitates distributing 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.

Discussion

This paper presents a tool for interactive and visual redescription mining. While we believe that the goals-and the methods we present to achieve them-are easy to accept as reasonable, we want to point out that there are still many open problems, both conceptual and technical, that need to be solved.

In the heart of interactive data mining is the user's ability to tell the algorithm that he wants more or less certain type of results. In principle, this is not a problem in Siren: the user simply selects a redescription he wants to remove from the beam search or extend more. The problem, however, is that there can be (and usually are) other, similar redescriptions that the user might also want to remove or extend. He can do that manually, of course, but with larger number of redescriptions, the process becomes unbearably tedious very soon.

A solution to this problem would be to remove (or extend) all similar redescriptions. But how to define the similarity? To give an example, consider a case when the user finds a redescription saying that the area where the Polar Bear lives is the area with January's mean temperature below -20 degrees Celsius, in other words, Polar Bear lives in cold. This is hardly a surprising result, and the user might want to remove it (and other similar results) from the search. But we can characterize the cold areas using other variables than just January's mean temperature, so it is not enough to just stop extending any redescription with Polar Bear and January's mean temperature in it. Also, we cannot just remove all the redescriptions with Polar Bear-that could remove some very interesting redescriptions, too. Finally, we could consider the area in which the redescription holds. But even that leaves a lot to be hoped for: if we remove all redescriptions that contain that area, we probably remove too many redescriptions, but if we instead remove redescriptions contained in the area, we probably miss most of the redescriptions we should remove.

The problem of removing and extending similar redescriptions is closely related to that of redundancy reduction. There are often multiple redescriptions that represent the same phenomenon (think of the Polar Bears living in the cold areas), and ideally, we would like to present only one of them to the user. In other words, we do not want to present to the user any redescriptions that do not add any (or add only marginally) new information over the redescriptions he has already seen. But as with deciding which redescription is similar to a selected one, also quantifying the redundancy between redescriptions is a difficult problem.

When interpreting a redescription, one should always bear in mind the assumptions attached to it. For example, whether some variables were disabled or whether the focus was put on some area when it was generated. Hence, keeping track of the constraints used when mining a redescription is essential. However, if the user is allowed to stop the extension process, modify the constraints and resume the search, this might be fairly intricate and interpretation of the results become impossible.

The goal of data mining is to find new and interesting information from the data. In interactive data mining in general, and with the tools discussed in this paper in particular, the user can guide the data mining method towards the results he prefers. This raises new problems. First, we have to control that the data supports the results the user finds and second, we must be careful that the user actually finds new information, not just the information he already knew.

The first problem, making sure that the obtained results are supported by the data, is ages old in sciences. In short, it is the question of testing the significance of a hypothesis, and there is a vast body of statistical literature about it. Our proposed algorithms mitigate the problem by computing a p-value, but as it is based on a fixed null hypothesis, it is not adequate in every case.

The second problem is more conceptual: taken to an extreme, the interactivity removes the data mining from the interactive data mining. If the user more or less directly tells the algorithm the redescription he wants to see, the Siren program turns into a mere plotting interface. Even on the less extreme case, the user can easily (an unwittingly) guide the algorithm towards the kind of results he wanted to see. Together with the fact that we can only check against a fixed null hypothesis, this causes a considerable risk of false findings. The onus is on the user to make sure he does not misuse the algorithm.

Fig. 2 .

 2 Fig. 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.

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

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