MINING CO-LOCATION PATTERNS WITH CLUSTERING ITEMS FROM SPATIAL DATA SETS

Guoqing Zhou, Qingshan Li, Guangming Deng, Tao Yue, Xiang Zhou2018 · DOI

TL;DR

This paper introduces a new type of spatial pattern called "co-location patterns with clustering items," where a feature's presence is influenced by a pair of other features. They propose a novel algorithm, extending a traditional join-based approach, to efficiently discover these patterns in large spatial datasets. This work is significant for understanding complex spatial relationships beyond simple pairwise co-occurrences.

What Problem Does This Paper Address?

Traditional co-location pattern mining focuses on identifying features that frequently appear together. For example, finding that "trees" and "rivers" are often found near each other. However, in many real-world scenarios, a feature's presence might be influenced by a combination of other features. The authors highlight that a feature C might not just depend on A or B individually, but on the pair (A, B) appearing together. This is a more nuanced relationship than previously captured. Existing co-location mining algorithms are not equipped to discover these "co-location patterns with clustering items," creating a gap in our ability to analyze complex spatial dependencies.

Methods

The core of the paper is the introduction of "clustering items" and "co-location patterns with clustering items." A "clustering item" is defined as a pair of spatial features (e.g., A and B) that are spatially neighbors within a defined distance d. A "co-location pattern with clustering items" then extends this by considering a clustering item (A, B) and one or more other features (Y) that frequently co-occur with this pair.

The proposed algorithm builds upon the "join-based approach" for traditional co-location mining. It involves several phases:

  1. Discovering Clustering Items: Identifying all pairs of spatially neighboring features in the dataset.
  2. Computing Neighbor Relationships: Establishing how individual features relate to these discovered clustering items.
  3. Generating Candidate Patterns: Combining prevalent clustering items with other features to form candidate co-location patterns with clustering items.
  4. Pruning: Eliminating candidate patterns that do not meet minimum prevalence thresholds, using both traditional prevalence-based pruning and a novel pruning method that leverages the fact that if a pair (A, B) is already a prevalent co-location, then patterns involving A and B individually might be redundant.
  5. Generating Prevalent Patterns and Rules: Identifying the final set of co-location patterns with clustering items and deriving association rules from them.

Datasets

The authors used synthetic datasets for their experimental evaluation. These datasets were generated using a spatial data generator similar to one described by Shekhar and Huang (2001). The number of spatial feature types was set to 20. The experiments varied three parameters: the number of spatial instances, the prevalence threshold (min_prev), and the spatial neighbor distance threshold (d). No new benchmarks were introduced; rather, existing generation methods were adapted.

Key Insights and Ideas

  • Beyond Pairwise Co-occurrence: The most significant insight is the formalization and mining of co-location patterns where a feature's presence is linked to a pair of other features. This allows for a richer understanding of spatial dependencies.
  • "Clustering Items" as a New Building Block: The concept of a "clustering item" (a pair of neighboring features) serves as a fundamental unit for building more complex spatial relationships.
  • Efficient Pruning is Crucial: The paper emphasizes the importance of efficient pruning strategies. The introduction of a novel pruning method that leverages existing prevalent co-locations (pairs) significantly reduces computational cost.
  • Scalability Challenges: Like traditional co-location mining, the proposed algorithm's execution time increases with the number of spatial instances, primarily due to the inherent need for join operations.

Key Results

The paper demonstrates the correctness and efficiency of their proposed algorithm through experimental evaluation on synthetic data.

  • Execution Time: The execution time of the algorithm increases significantly with the number of spatial instances, mirroring the behavior of traditional join-based co-location mining algorithms.
  • Parameter Sensitivity:
    • The parameter min_prev (minimum prevalence threshold) showed that execution time increased rapidly when it decreased below a certain point (around 0.4), but was relatively stable for higher values.
  • The parameter d (spatial neighbor distance threshold) indicated that as d increased, the running time also increased, as expected, due to a larger number of potential neighbor relationships.

Limitations and Future Work

  • Synthetic Data: The evaluation was performed on synthetic datasets. The authors acknowledge that testing on real-world datasets would be beneficial to further validate the algorithm's performance and applicability.
  • Efficiency for Large Datasets: While the algorithm is presented as an extension of an efficient join-based approach, the inherent complexity of mining spatial patterns means that further optimizations for extremely large datasets might be necessary.
  • Future Work: The authors state their intention to continue studying ways to mine co-location patterns with clustering items more efficiently.

Summary updated

Abstract

The explosive growth of spatial data and widespread use of spatial databases emphasize the need for the spatial data mining. Co-location patterns discovery is an important branch in spatial data mining. Spatial co-locations represent the subsets of features which are frequently located together in geographic space. However, the appearance of a spatial feature C is often not determined by a single spatial feature A or B but by the two spatial features A and B, that is to say where A and B appear together, C often appears. We note that this co-location pattern is different from the traditional co-location pattern. Thus, this paper presents a new concept called clustering terms, and this co-location pattern is called co-location patterns with clustering items. And the traditional algorithm cannot mine this co-location pattern, so we introduce the related concept in detail and propose a novel algorithm. This algorithm is extended by join-based approach proposed by Huang. Finally, we evaluate the performance of this algorithm.
BibTeX
@inproceedings{zhou2018mining,
  author = {Guoqing Zhou and Qingshan Li and Guangming Deng and Tao Yue and Xiang Zhou},
  title = {{MINING CO-LOCATION PATTERNS WITH CLUSTERING ITEMS FROM SPATIAL DATA SETS}},
  booktitle = {˜The},
  year = {2018},
  doi = {10.5194/isprs-archives-xlii-3-2505-2018},
}
Figure