Delaunay triangulation‐based spatial colocation pattern mining without distance thresholds
- 7 April 2020
- journal article
- research article
- Published by Wiley in Statistical Analysis and Data Mining: An ASA Data Science Journal
- Vol. 13 (3) , 282-304
Abstract
A spatial colocation pattern is a group of spatial features whose instances frequently appear together in close proximity to each other. The proximity of instances is generally measured by the distance between them. If the distance is smaller than a distance threshold that is specified by users, they have a neighbor relationship. However, it is difficult for users to give a suitable distance threshold and mining results also vary widely with different distance thresholds. In addition, using distance thresholds are hard to accurately obtain neighborhoods of instances in heterogeneous distribution density data sets. In this study, we propose a new method for determining the neighbor relationship of instances in space without the distance threshold based on Delaunay triangulation (DT). We design three filtering strategies, such as a feature invalid edge, a global positive edge, and a local positive edge, to constrain the original DT to accurately extract the neighborhoods of instances in space. Then, a miner called DT‐based colocation (DTC) pattern mining is developed. Different from the traditional algorithms which adopt the time‐consuming generate‐test candidate model, DTC directly collects the table instances of colocation patterns from the constrained DT by building neighboring polygons and filters prevalent patterns. We compare the results mined by DTC with by the traditional algorithms at macrolevel and microlevel on both real and synthetic data sets to prove that the DTC algorithm improves the effectiveness and fineness of mining results.Keywords
Funding Information
- The National Natural Science Foundation of China (61966036, 61662086)
- The Project of Innovative Research Team of Yunnan Province (2018HC019)
This publication has 34 references indexed in Scilit:
- Mining Statistically Significant Co-location and Segregation PatternsIEEE Transactions on Knowledge and Data Engineering, 2013
- GPU-Accelerated Collocation Pattern Discovery2013
- Spatial co-location pattern discovery without thresholdsKnowledge and Information Systems, 2012
- Exploratory analysis of the interrelations between co-located boolean spatial features using network graphsInternational Journal of Geographical Information Science, 2012
- Discovering Co-location Patterns from Spatial Domain using a Delaunay ApproachProcedia Engineering, 2012
- An adaptive spatial clustering algorithm based on delaunay triangulationComputers, Environment and Urban Systems, 2011
- An order-clique-based approach for mining maximal co-locationsInformation Sciences, 2009
- FARICS: a method of mining spatial association rules and collocations using clustering and Delaunay diagramsJournal of Intelligent Information Systems, 2009
- Testing local spatial autocorrelation usingk-order neighboursInternational Journal of Geographical Information Science, 2000
- Delaunay triangulations in TIN creation: an overview and a linear-time algorithmInternational Journal of Geographical Information Science, 1993