A multi-relational approach to spatial classification

Richard Frank, Martin Ester, Arno J. Knobbe

Abstract

Predicting spatial phenomena, such as crime occurrences or business profitability, requires understanding the complex relationships between geographic entities. Traditional spatial data mining often relies on arbitrary distance-based buffers that fail to capture the nuances of urban density and spatial trends. This paper summarizes the UnMASC (Unified Multi-relational Aggregation-based Spatial Classifier) framework, which utilizes Voronoi-based neighborhood definitions and extended Inductive Logic Programming (ILP) to improve spatial classification accuracy. By integrating multi-feature and spatial aggregations, the framework demonstrates significant performance gains in predicting crime patterns within real-world urban datasets.

Introduction

In spatial analysis, the properties of a single location are rarely independent of its surroundings. Defining a "neighborhood" is a fundamental challenge for computational models. Traditional propositional data mining treats data points as independent rows, while multi-relational data mining (MRDM) typically relies on explicit links like foreign keys. In geography, however, relationships are implicit; there is no natural "foreign key" linking a building to a nearby park.

Existing methods often use "buffer zones"—fixed radii around a point of interest. These are problematic because they are non-adaptive; a 500-meter radius represents vastly different contexts in rural versus dense urban environments. Furthermore, simple proximity models often ignore "spatial trends," where the influence of a feature (such as income or property value) changes directionally across space.

The UnMASC Framework

In his 2010 PhD thesis, Richard Frank introduced the UnMASC framework to bridge the gap between traditional data mining and the implicit world of spatial geography. The framework introduces three core innovations:

1. Adaptive Voronoi-Based Neighborhoods

Instead of fixed-distance buffers, UnMASC employs Voronoi diagrams to partition space. In this model, two entities are considered neighbors if their Voronoi cells share a boundary. This approach is non-parametric and adaptive, automatically scaling neighborhood definitions based on the local density of entities. This respects Tobler’s First Law of Geography—that "near things are more related than distant things"—without requiring arbitrary user-defined thresholds.

2. Extended Inductive Logic Programming (ILP)

The framework extends ILP, a machine learning technique that generates human-readable logic rules (Horn Clauses), to handle complex spatial relationships. Two new types of aggregation are introduced:

  • Multi-Feature Aggregation (MFA): This captures correlations between different features, such as whether property values increase as proximity to transit hubs decreases.
  • Spatial Aggregation (SA): This directly incorporates spatial trends and autocorrelations into the rule-learning process, allowing the model to identify patterns that emerge over a geographic gradient.

3. Scalable Parallelized Learning

Calculating spatial relationships across millions of entity pairs is computationally intensive. UnMASC utilizes a client-server model to parallelize rule evaluation. This allows the system to test multiple candidate rules simultaneously across multi-core processors, making it feasible to process large-scale urban datasets efficiently.

Experimental Evaluation

The framework was tested using a massive, custom-built Crime Data-Warehouse (CDW). This dataset integrated five years of real-world RCMP crime records from the Police Information Retrieval System (PIRS), property assessment data from the British Columbia Assessment Authority (BCAA), and infrastructure data including road networks and public transit locations.

Experiments focused on three specific urban crime scenarios: commercial burglary in Burnaby, high-density residential burglary in Burnaby, and auto-theft in Surrey.

Key Results

The Voronoi-based approach significantly outperformed traditional methods. In the Burnaby commercial burglary dataset, UnMASC achieved a precision of 64.2%, compared to 51.8% for buffer-zone models and 50.8% for models ignoring neighborhood context entirely.

The inclusion of multi-feature and spatial aggregations improved the "FOIL-Gain," a measure of rule quality. This allowed the system to identify nuanced patterns, such as finding that high-rise buildings were more susceptible to burglary when a trend of increasing property values moved toward a specific commercial hub.

Furthermore, the parallelized implementation provided a 5.5x speedup on a 6-CPU system, demonstrating the framework's scalability for real-world applications.

Discussion and Conclusion

One of the primary advantages of the UnMASC framework is the legibility of its outputs. Unlike "black box" neural networks, the ILP-generated rules are logical statements that can be easily validated and interpreted by criminologists and urban planners.

While the current framework excels at spatial analysis, it remains "time-blind." Future research could integrate temporal trends to account for how neighborhoods evolve over months or years. Additionally, moving beyond "greedy" search strategies toward more robust optimization techniques like randomized restarts could further refine rule discovery.

By treating space as a relative network rather than a fixed grid, UnMASC provides a more accurate and interpretable method for spatial classification, with clear implications for public safety and urban development.

Reference: Frank, R. (2010). A Multi-Relational Approach to Spatial Classification. PhD Thesis, Simon Fraser University.

Summary updated

Abstract

Spatial classification is the task of learning models to predict class labels based on the features of entities as well as the spatial relationships to other entities and their features. Spatial data can be represented as multi-relational data, however it presents novel challenges not present in multi-relational problems. One such problem is that spatial relationships are embedded in space, unknown a priori, and it is part of the algorithm's task to determine which relationships are important and what properties to consider. In order to determine when two entities are spatially related in an adaptive and non-parametric way, we propose a Voronoi-based neighbourhood definition upon which spatial literals can be built. Properties of these neighbourhoods also need to be described and used for classification purposes. Non-spatial aggregation literals already exist within the multi-relational framework, but are not sufficient for comprehensive spatial classification. A formal set of additions to the multi-relational data mining framework is proposed, to be able to represent spatial aggregations as well as spatial features and literals. These additions allow for capturing more complex interactions and spatial occurrences such as spatial trends. In order to more efficiently perform the rule learning and exploit powerful multi-processor machines, a scalable parallelized method capable of reducing the runtime by several factors is presented. The method is compared against existing methods by experimental evaluation on a real world crime dataset which demonstrate the importance of the neighbourhood definition and the advantages of parallelization.
BibTeX
@inproceedings{frank2009multi,
  author = {Richard Frank and Martin Ester and Arno J. Knobbe},
  title = {{A multi-relational approach to spatial classification}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2009},
  doi = {10.1145/1557019.1557058},
}
Figure