Minimal Negative Co-location Patterns and Effective Mining Algorithm

Abstract

A spatial co-location pattern refers to a subset of spatial features whose instances are frequently co-located in spatial. In spatial data mining, most of the existing algorithms aim to discover the positive patterns. Moreover, there are patterns with strong negative correlations in spatial, such as negative co-location patterns. The discovery of such patterns is also greatly significant in some applications. Existing negative co-location patterns mining algori-thm is time-consuming and the number of mining results is huge. To address these problems, this paper explores the upward inclusion property of the negative co-location pattern, and proposes a minimal negative co-location pattern. Based on the minimal negative co-location patterns, all prevalent negative co-location patterns can be derived. In the negative co-location pattern mining process, the calculation of table instances of the candidate patterns is the funda-mental factor that restricts the mining efficiency. In order to reduce the calculation of the table instance effectively, three pruning strategies are proposed. A large number of experiments on real and synthetic data sets verify the correctness and efficiency of the proposed algorithm. In particular, the experimental results show that the minimal negative co-location patterns can compress the number of prevalent negative co-location patterns by more than 80%.

Keywords

• spatial data mining
• spatial co-location pattern
• minimal negative co-location pattern
• upward inclusion
• compact representation