Statistically Sound Interaction Pattern Discovery from Spatial Data

Abstract

Spatial interaction pattern mining is the process of discovering patterns that occur due to the interaction of Boolean features from a spatial domain. A positive interaction of a subset of features generates a co-location pattern, whereas a negative interaction of a subset of features generates a segregation pattern. Finding interaction patterns is important for many application domains such as ecology, environmental science, forestry, and criminology. Existing methods use a prevalence measure, which is mainly a frequency based measure. To mine prevalent patterns, the known methods require a user defined prevalence threshold. Deciding the right threshold value is not easy and an arbitrary threshold value may result in reporting meaningless patterns and even not reporting meaningful patterns. Due to the presence of spatial auto-correlation and feature abundance, which are not uncommon in a spatial domain, random patterns may achieve prevalence measure values higher than the used threshold just by chance, in which case the existing algorithm will report them. To overcome these limitations, we introduce a new definition of interaction patterns based on a statistical test. For the statistical test, we propose to design an appropriate null model which takes spatial auto-correlation into account. To reduce the computational cost of the statistical test, we also propose two approaches. Existing mining algorithms also use a user provided distance threshold at which the algorithm checks for prevalent patterns. Since spatial interactions, in reality, may happen at different distances, finding the right distance threshold to mine all true patterns is not easy and a single appropriate threshold may not even exist. In the second major contribution of this thesis, we propose an algorithm to mine true co-locations at multiple distances. Our approach does not need thresholds for the prevalence measure and the interaction distance. An approximation algorithm is also proposed to prune redundant patterns that could occur in a statistical test. This algorithm finally reports a minimal set of patterns explaining all the detected co-locations. We evaluate the efficacy of our proposed approaches using synthetic and real data sets and compare our algorithms with the state-of-the-art co-location mining approach.