In spatial domains, objects present high heterogeneity and are connected by several relationships to form complex networks. Mining spatial networks can provide information on both the objects and their interactions. In this work we propose a descriptive data mining approach to discover relational disjunctive patterns in spatial networks. Relational disjunctive patterns permit to represent spatial relationships that occur simultaneously with or alternatively to other relationships. Pruning of the search space is based on the anti-monotonicity property of support. The application to the problem of urban accessibility proves the viability of the proposal.
A spatial network is a network of spatial objects, that is, objects characterized by
both a spatial localization (e.g. in a geo-referenced system) and a geometry (e.g.
an area). Nodes of spatial networks correspond to spatial objects, while links
express spatial relationships (e.g. adjacency). In some cases, links are defined on
the basis of other spatial objects (e.g. roads, railways, flights, rivers, etc.). A link
might be labeled with a numerical weight which denotes the distance between
two nodes. Although spatial networks are of great interest in the study of spatial
phenomena, such as urban accessibility, they have not yet received the attention
in data mining that they deserve. Yiu and Mamoulis [
In these, as well as in other related works, a spatial network is modeled as a graph, which simplifies the network by removing the geometry. However, this representation is sometimes oversimplified, since it considers neither the heterogeneity of spatial objects (e.g. public services and private houses should be described by different feature sets) nor the heterogeneity of the spatial relationships expressed in links (e.g. connection by bus, railway or road). This heterogeneity of spatial objects and relationships demands for different representation formalisms and, consequently, a different class of data mining methods which are able to handle this further complexity in the data.
It has been recently argued that the (multi-)relational setting [
In this paper, we extend our previous work on the task of spatial association
analysis thorough an inductive logic programming (ILP) approach [
To improve the robustness of the spatial association rule mining method there are two alternatives. First, defining a hierarchy among spatial predicates, which could be used to generalize over spatial relationships. Second, enabling the generation of disjunctive patterns, that is patterns where two or more atoms may be OR-ed to express the variance on the spatial relationship existing between two objects. In this work we follow the second approach, since the definition of a hierarchy among spatial predicates can be cumbersome in many applications. Moreover, in order to prevent the generation of meaningless disjunctions, we exploit a user-defined dissimilarity measure between spatial relationships, which could be used to prune the search space.
The paper is organized as follows. In the next section, related works and contribution of the proposed approach are presented. In Section 3, the approach is presented in detail. In Section 4 the application to a case study is reported. Finally, conclusions are drawn and future works are presented. 2
Discovering patterns in spatial networks has attracted great interest in the area
of in geographical information sciences (GIS). In his seminal work, Zhang [
The aforementioned works have common characteristic: spatial objects and networks are represented as vectors or graphs, which suffer from several limitations when heterogeneous spatial objects and relationships have to be represented. This motivates our interest in relational approaches to spatial pattern discovery. Moreover, to cope with the problem of brittleness of subsumption tests for relational patterns, we extend relational mining algorithms in order to discover disjunctive patterns, where alternative relationships between two spatial objects are allowed.
In the literature on frequent pattern mining, we found two noticeable
contributions to the problem of discovering disjunctive patterns. In [
This paper makes a contribution to the literature on spatial network mining by considering disjunctive patterns in relational formalisms, which are more appropriate to represent spatial networks with heterogeneous spatial objects and relationships. In particular, we extend a method for spatial association rule discovery in order to represent: 1. Disjunctions (e.g. (intersects(B, A) OR crosses(B, A))). They are created by exploiting a user-defined background knowledge in the form of a semantic graph, where vertices correspond to spatial relationships (e.g. intersects), while edges denote the semantic relatedness among them and are labelled with numerical weights which quantify the dissimilarity among the relationships (e.g., intersects 0↔.9 crosses); 2. Disjunctive patterns (e.g., hdistrict(A), transport line(B), (intersects(B, A) OR crosses(B, A)), is a(A, market square), is a(B, road)i ). They are extracted from a graph of patterns which is refined until user-defined input criteria are met.
The proposed approach follows a three-stepped procedure. First, it extracts the infrequent conjunctive patterns which can be upgraded to the disjunctive form. For instance, given P1 : hdistrict(A), contained in(A, B), marketplace(B)i and the similarity between contained in and overlaps, we can upgrade it to P1′ : hdistrict(A), (contained in(A, B) OR overlaps(A, B)), marketplace(B)i. Second, background knowledge is accommodated to exploit the information on the (dis)similarity among the spatial relationships in the process of generation of disjunctive patterns. Third, disjunctive patterns are produced by iteratively integrating disjunctions into the patterns by means of a pair-wise joining. For instance, given the patterns P1 : hdistrict(A), contained in(A, B), marketplace(B)i, P2 : hdistrict(A), overlaps(A, B), marketplace(B)i and assumed that contained in and overlaps are two “similar” atoms according to background knowledge, P1 and P2 are merged to form the pattern:
hdistrict(A), (contained in(A, B) OR overlaps(A, B)), marketplace(B)i. Finally, only the disjunctive patterns whose frequency exceeds the traditional minimum threshold are considered. 3
Before formally stating the data mining problem, we introduce some basic notions. In the relational setting, when handling spatial objects, different roles can be played by different sorts of data. In a spatial network, objects can be distinguished into target objects of analysis (T O) and non-target objects of analysis (N T O). By introducing this distinction we follow the usual practice in statistics of distinguishing between units of analysis and units of observation. Generalization concerns the units of analysis, while the units of observation are typically secondary data considered potentially useful to explain a phenomenon.
In this work, the target objects (units of analysis) are data on which patterns
are enumerated and contribute to compute the frequency of a pattern, while the
non-target objects (units of observation) contribute to define the former and can
be involved in a pattern. We denote the set of T O as S and the sets of N T O
by means of the sets Rk (1 ≤ k ≤ M ), where M is the number of sorts of
data that are not considered to be TO. NTOs, belonging to a set Rk, can be
organized hierarchically according to a user defined taxonomy. Target objects
and non-target objects are represented in Datalog language [
Some predicate symbols are introduced in order to express both properties and relationships of T O and N T O. The predicate symbols represent spatial relationships and can be categorized into four classes: 1) key predicate identifies the T O in DE (e.g., in the examples above, district(·)); 2) property predicates are binary predicates which define the values taken by an attribute of a T O or of an N T O; 3) structural predicates are binary predicates which relate N T O as well as T O with others N T O (e.g., in the examples above, contained in(·,·)); 4) is a predicate is a binary taxonomic predicate which associates N T O with a symbol contained in the user defined taxonomy.
The intensional part DI of the deductive database D includes the definition of the semantic graph (background knowledge) that permits us to express the dissimilarity among spatial relationships in the form of Datalog weighted edges of a graph. An example of the Datalog weighted edge is the following: external touch to - (crosses - 0.88) It states that the dissimilarity between the relationships external touch to(·,·) and crosses(·,·) is 0.88. More generally, it represents an undirected edge e between two vertices vi, vj (e.g., external touch to, crosses) with weight wij (e.g., 0.88) and it is denoted as e(vi, vj , w). A finite sequence of undirected links e1, e2, . . . , em which connects two vertices vi, vj is called path and denoted as ρ(ni, nj). The complete list of such undirected edges represents the background information on the dissimilarity among relationships and allows to join patterns by introducing disjunctions (externa touch to(A,B) OR crosses(A,B)).
Discovered patterns are conjunctions of Datalog non-ground atoms and disjunctions of non-ground atoms, which can be expressed by means of a set notation. A Datalog non-ground atom is an n-ary predicate symbol applied to n terms (either constants or variables), at least one of which is a variable. A formal definition of pattern of our interest is reported in the following: Definition 1. A disjunctive pattern P is a set of atoms and disjunctions of atoms p0(t10), (p1(t11, t21)|p2(t12, t22)| . . .), . . . , (pk(t1k, t2k)| . . . |pk+h(t1k+h, t2k+h)) where p0 is the key predicate, while pi, i = 1, . . . , k + h, is either a structural predicate or a property predicate or an is a predicate. Symbol “ | ” indicates disjunctions.
Terms tij are either constants, which correspond to values of property predicates, or variables, which identify target objects or non-target objects. Each pi is a predicate occurring in DE (extensionally defined predicate). Some examples of disjunctive patterns are the following: P1 ≡ district(A), (comes f rom(A, B)|external ends at(A, B)), shape(A, rectangle) P2 ≡ district(A), (external ends at(A, B)|runs along boundary and goes in(A, B)), transport net(A, roads) where the variables A denote target objects, and variables B denote some nontarget objects, while the predicates district(A) identify the key predicate in P1 and P2, shape(A, rectangle) and transport net(A, roads) are property predicates and the others are structural predicates. All variables are implicitly existentially quantified.
We now can give a formal statement of the problem of discovering relational frequent patterns with disjunctions: 1. Given: the extensional part DE of a deductive database D, and two thresholds minSup ∈ [0; 1], nSup ∈ [0; 1] (minSup represents a minimum frequency value while nSup represents a maximum frequency value, nSup < minSup), Find: the collection IR of the relational infrequent patterns whose support is included in [nSup; minSup). 2. Given: the collection IR, the intensional part DI of a deductive database D, and two thresholds minSup and γ ∈ [0; 1] (γ defines the maximum dissimilarity value of relationships involved in the disjunctions), Find: relational disjunctive patterns whose frequency exceeds minSup and whose dissimilarity of relationships involved in the disjunctions does not exceed γ. 3.1
The intuition underlying the discovery of pattern with disjunctions is that of extending infrequent conjunctive patterns with disjunctive forms until the threshold minSup is exceeded. Each conjunctive pattern P is associated with a statistical parameter sup(P, D) (support of P on D), which is the percentage of units of analysis in D covered by P . More precisely, a unit of analysis of a target object s ∈ S is a subset of ground atoms in DE defined as follows:
D[s] = is a(R(s)) ∪ D[s|R(s)] ∪
D[ri|R(s)],
(1) [ ri∈R(s) where R(s) is the set of NTO directly or indirectly related to s, is a(R(s)) is the set of is a atoms which define the sorts of ri ∈ R(s), D[s|R(s)] contains properties of s and relations between s and some ri ∈ R(s), D[ri|R(s)] contains properties of ri and relations between ri and some rj ∈ R(s). By assigning a pattern P with an existentially quantified conjunctive formula eqc(P ) obtained by transforming P into a Datalog query, the units of analysis D[s] are covered by a pattern P if D[s] |= eqc(P ), namely D[s] logically entails eqc(P )).
Conjunctive patterns are mined with SPADA[
The search is based on the level-wise method and implements a two-stepped procedure: i) generation of candidate patterns with k atoms (k -th level) by considering the frequent patterns with k − 1 atoms ( (k-1 )-th level); ii) evaluation of the frequency with k atoms. So, the patterns whose support does not exceeds minSup will be not considered for the next level: the patterns discarded (infrequent) at each level are rather considered for the generation of disjunctions. The collection IR is thus composed of a subset of infrequent patterns, more precisely those with support greater than or equal to nSup (and less than minSup). 3.2
The generation of disjunctive patterns is performed by creating disjunctions among similar relationships (thus similar atoms in the patterns) in accordance to the background semantic graph: two patterns which present similar atoms are joined to form only one. The implemented algorithm (see Algorithm 1) is composed of two sub-procedures: the first one (lines 2-12) creates a graph GD with the patterns of IR by exploiting the knowledge defined in DI , while the second one (lines 13-32) joins two patterns (vertices) on the basis of the information (weight) associated to their edge. The initial graph GD evolves due to joining of patterns on the vertices until the setting of minSup and γ is met (Section 3.1).
In particular, for each pair of patterns which have the same length (namely, at the same level of the level-wise search method) it checks whether they differ in only one atom and share the remaining atoms up to a redenomination of variables (line 3). Let α and β be the two atoms differentiating P from Q (α in P, β in Q), a path ρ which connects α to β (or viceversa) is searched among the weighted edges according to DI (semantic network): in the case the sum ω of the weights found in the path is lower than the maximum dissimilarity γ the vertices P and Q are inserted into GD and linked through an edge with weight ω (lines 4-9). Note that when there is more than one path between α and β, then the path with lowest weight is considered. Intuitively, at the end of the first sub-procedure, GD will contain, as vertices, the patterns which meet the condition at the line 3, and it will contain, as edges, the weights associated to the path linking the atoms differentiating the patterns.
Once we have GD, a list LD is populated with the vertices and edges of GD: an element of LD is a triple hP, Q, ωi composed of a pair of vertices-patterns (P,Q) with their relative weight. Elements in LD are ranked in ascending order with respect to the values of ω so that the pairs of patterns with lower dissimilarity will be joined for first. This guarantees that disjunctions with very similar atoms will be preferred to the others (line 13). For each element of LD whose weight ω is lower than γ the two patterns P, Q are joined to generate a pattern J composed by the conjunction of the same atoms in common to the two patterns P, Q and of the disjunction formed by the two different (but similar) atoms (lines 14-15). This joining procedure permits to have patterns with the same length of the original ones and which occur when at least one of original patterns occurs. Therefore, if a pattern J is obtained by joining P and Q, it covers a set of units of analysis equal to the union of those of P and Q: the support of J is determined as in line 16 and, generally, it is higher than the support of P and Q. In the case the support of J exceeds minSup then it can be considered statistically interesting and no further processing is necessary (lines 16-17). Otherwise, J is again considered and inserted into GD as follows. The edges which linked another pattern R of GD to P and Q are modified in order to keep the links from R to J: the weight of the edges between one pattern R and J will be set to the average value of the weights of all the edges which linked R to P and Q (lines 19-27). The modified graph GD contains conjunctive patterns (those of IR) and pattern with disjunctions (those produced by joining). Thus, GD is re-evaluated for further joins and the algorithm proceeds iteratively (line 29-30) until no additional disjunctions can be done (namely, when LD is empty or the weights ω are higher than γ). At each iteration, the patterns P and Q are removed from GD (line 32).
An explanatory example is illustrated in Figure 1. Consider the background knowledge DI on the dissimilarity among four spatial relationships and the set IR containing four infrequent conjunctive patterns as illustrated in Figure 1a and γ equal to 0.7. The first sub-procedure of the algorithm 1 analyzes P1, P2, P3, P4 and discovers that they differ in only one atom, while the other atoms are in common. Then, it creates the graph GD by collocating P1, P2, P3 in three different vertices and linking them through edges whose weights are taken from the paths ρ in DI . P4 is not considered because the vertex overlaps has dissimilarity with internal ends at higher than γ (row (1) in Figure 1b). The second sub-procedure starts by ordering the weights of the edges: the first disjunction is created by joining P1 and P3 given that the dissimilarity value is lower than γ and the lowest (row (2) in Figure 1b). Next, the pattern so created (a) (b) and P2 are checked for joining. Both have the same length and differ in only one atom. Although the first presents a disjunction and the second presents a “simple” atom, dissimilarity is lower than γ and a new disjunctive pattern is created (row (3) in Figure 1b). 4
This approach has been implemented as the extension of the system SPADA aimed to discover relational patterns with disjunctions: the system (afterwards jSP ADA) is now able to mine conjunctive patterns and disjunctive patterns as well. Here we present the application of both systems to mine spatial networks in a case study of urban accessibility. More precisely, the spatial network is obtained by analyzing both census and digital maps of Stockport, one of the ten districts in Greater Manchester and the analysis is aiming at investigating the accessibility to the Stepping Hill Hospital from the actual residence of people living far from the hospital. In this case study, transport network, namely the layers of roads, railways and bus priority lines, correspond to the links of the spatial network, while districts close to the hospital and districts distant from the hospital corresponds to the nodes of the network. In accordance with our setting defined in Section 3, districts close to the hospital are target objects while the transport network and districts distant from the hospital are non-target objects.
Property predicates define people with own cars and are no car(), one car(),
two cars(), three more cars(). Structural predicates represent binary topological
relationships between districts and roads, railways or bus lines, and correspond
to the twelve feasible relations between a region and a line according to the
9intersection model [
Experiments were performed1 by tuning the thresholds minSup, nSup, γ and the results are reported in Figure 2. A comparison between SPADA and jSPADA has been conducted by varying minSup, while, for jSPADA, the values of nSup and γ are set to 0.005 and 0.6 respectively. As we can see the histogram values reported in Figure 2a, jSPADA discovers a number of patterns that is higher than that of SPADA. Indeed, jSPADA returns a set which includes those frequent conjunctive (generated by SPADA) and those disjunctive generated by re-evaluating the infrequent conjunctive ones. Thus, as minSup increases, the range [nSup; minSup) becomes larger and, generally, more disjunctive patterns are extracted while the number of conjunctive frequent patterns decreases. It is worthy that the set of only disjunctive patterns (the complement of the set of patterns of jSPADA relative to the set of SPADA) is actually much smaller than the set of only conjunctive patterns (patterns of SPADA). For instance, when minSup=0.007 the number of disjunctive patterns amounts to 5, while the number of conjunctive patterns is 898. Thus, the problem of huge amounts of disjunctive patterns is not so relevant as in the case of conjunctive patterns. This is a clear advantage of the proposed approach since the classical problem of manual analysis of patterns is mitigated.
As expected, also the threshold nSup has influence on the patterns discovered by jSPADA. Indeed, from the figures 2c and 2d (minSup = 0.025 and γ = 0.6) we note that jSPADA is highly sensitive to nSup since the number of disjunctive patterns is reduced of one order of magnitude (from 20 to 0) while nSup is increased by factor of two (from 0.01 to 0.02). By comparing the plots (a), (c) and (d) we note that, by varying minSup, jSPADA has a limited capacity in unearthing infrequent patterns (but potentially interesting) than when varying nSup. This confirms the viability of the approach to discover new forms of interesting patterns. The sensitivity of the algorithm can be evaluated with respect to the dissimilarity of the disjunctions (Figure 2b). At high values of γ disjunctions can be created also between relationships whose similarity is small, so the patterns present disjunctions with several atoms and the final set is larger. On the contrary, lower values of γ permit to identify disjunctions only between very similar relationships, so the disjunctions present less atoms and the final set is smaller: when γ is set to 0.4, no disjunction is created since the minimum value of similarity between relationships amounted to 0.44.
A comparison between jSPADA and SPADA can also be done from a qualitative viewpoint. jSPADA enables the discovery of patterns which enrich the information extracted by SPADA. For instance, the pattern discovered by SPADA 1 Data and results are accessible at http://www.di.uniba.it/∼loglisci/jSPADA/ P1 : district(A), comes from(A, B), is a(B, road), comes from(A, C), is a(C, road) [support : 12%] is enriched by P2 discovered by jSPADA:
P2 : district(A), [comes from(A, C)|external ends at(A, C)], is a(C, road), comes from(A, B), is a(B, rail) [support : 16%] which introduces the disjunctions comes f rom(A, C)|external ends at(A, C) between two structural predicates. P2 expresses the information that the road named as C can be connected to the district named as A through two possible simultaneous or alternative ways, comes f rom(A, C) (C starts in A and terminates outside A) and external ends at(A, C) (C starts outside A and terminates inside A). Remarkably, the support of P2 is higher than that of P1. jSPADA permits also the discovery of completely novel patterns that SPADA neglects. One of these is the following:
P3 : district(A), [external ends at(A, B)|along(A, B)|comes from(A, B)], three more cars(A, [0.033; 0.114]) [support : 11.1%] which introduces a property predicate (i.e., the percentage of households owing more three cars included in [0.033;0.114]) and expresses in the disjunction three possible forms of accessibility to the district A by the transport line B. In this paper we present a relational data mining approach to discover disjunctive frequent patterns in spatial networks when considering a variance of spatial relationships existing between two objects. The introduction of disjunctions into the patterns permits to represent spatial relationships which occur simultaneously with or alternatively to others. The application to the problem of urban accessibility points out some peculiarities of the proposal. As future work, we intend to extend experiments to evaluate scalability of the approach. Acknowledgment. This work is supported by the Strategic Project PS121 ”Telecommunication Facilities and Wireless Sensor Networks in Emergency Management” funded by Apulia Region.