Finding Probabilistic Prevalent Colocations in Spatially Uncertain Data Sets
Authors:
- 13 December 2011
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 25 (4) , 790-804
Abstract
A spatial colocation pattern is a group of spatial features whose instances are frequently located together in geographic space. Discovering colocations has many useful applications. For example, colocated plant species discovered from plant distribution data sets can contribute to the analysis of plant geography, phytosociology studies, and plant protection recommendations. In this paper, we study the colocation mining problem in the context of uncertain data, as the data generated from a wide range of data sources are inherently uncertain. One straightforward method to mine the prevalent colocations in a spatially uncertain data set is to simply compute the expected participation index of a candidate and decide if it exceeds a minimum prevalence threshold. Although this definition has been widely adopted, it misses important information about the confidence which can be associated with the participation index of a colocation. We propose another definition, probabilistic prevalent colocations, trying to find all the colocations that are likely to be prevalent in a randomly generated possible world. Finding probabilistic prevalent colocations (PPCs) turn out to be difficult. First, we propose pruning strategies for candidates to reduce the amount of computation of the probabilistic participation index values. Next, we design an improved dynamic programming algorithm for identifying candidates. This algorithm is suitable for parallel computation, and approximate computation. Finally, the effectiveness and efficiency of the methods proposed as well as the pruning strategies and the optimization techniques are verified by extensive experiments with “real + synthetic” spatially uncertain data sets.Keywords
This publication has 28 references indexed in Scilit:
- Efficiently Mining Co-Location Rules on Interval Data2010
- An order-clique-based approach for mining maximal co-locationsInformation Sciences, 2009
- A Tree-Based Approach for Frequent Pattern Mining from Uncertain Data2008
- A Decremental Approach for Mining Frequent Itemsets from Uncertain Data2008
- Mining Frequent Itemsets from Uncertain Data2007
- Mining Co-Location Patterns with Rare Events from Spatial Data SetsGeoInformatica, 2006
- Efficient discovery of multilevel spatial association rules using partitionsInformation and Software Technology, 2005
- Discovering colocation patterns from spatial data sets: a general approachIEEE Transactions on Knowledge and Data Engineering, 2004
- Discovering Spatial Co-location Patterns: A Summary of Results2001
- Knowledge Discovery in Spatial Databases1999