A Multi-scale Method for Mining Significant Spatial Co-location Patterns

doi:10.11947/j.AGCS.2016.20150371

Abstract

Abstract: Spatial co-location patterns discovery aims to detect spatial features whose instances are frequently located in geographic proximity. Such patterns can reveal unknown regularity in geographic phenomena and they are helpful for decision-making. However, due to the little prior knowledge, it is difficult to specify thresholds for neighbor distance and prevalence index.As a result, the outcomes of most algorithms always include insignificant or even erroneous patterns. A pattern-reconstruction-based approach was proposed to discover only significant co-location patterns. Firstly, we introduce a new definition of MNND, which can identify the lower and upper bounds of neighbor distance threshold. Then, a null model was constructed based on the pattern reconstruction. On basis of that, selection of prevalence threshold is replaced by hypothesis testing. Finally, significant colocation patterns were mined at multiple distances and the results were evaluated by the notion of lifetime. The experimental results show that our approach could avoid the subjectivity in determining those thresholds, thereby improving the correctness and robustness.

Key words: data mining, spatial co-location, statistical significant patterns, pattern reconstruction, multi-scale

CLC Number:

P208

HE Zhanjun, LIU Qiliang, DENG Min, CAI Jiannan. A Multi-scale Method for Mining Significant Spatial Co-location Patterns[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(11): 1335-1341.

References

[1] 李光强, 邓敏, 朱建军. 基于Voronoi图的空间关联规则挖掘方法研究[J]. 武汉大学学报(信息科学版), 2008, 33(12): 1242-1245. LI Guangqiang, DENG Min, ZHU Jianjun. Spatial Association Rules Mining Methods Based on Voronoi Diagram[J]. Geomatics and Information Science of Wuhan University, 2008, 33(12): 1242-1245.
[2] 谢超, 陈毓芬, 王英杰. Apriori算法在ACViS中用户行为监测数据挖掘中的应用研究[J]. 测绘学报, 2010, 39(4): 397-403. XIE Chao, CHEN Yufen, WANG Yingjie. Application of Apriori Algorithm in User Action Monitoring Data Mining in Adaptive Cartographic Visualization System[J]. Acta Geodaetica et Cartographica Sinica, 2010, 39(4): 397-403.
[3] 田晶, 王一恒, 颜芬, 等. 一种网络空间现象同位模式挖掘的新方法[J]. 武汉大学学报(信息科学版), 2015, 40(5): 652-660. TIAN Jing, WANG Yiheng, YAN Fen, et al. A New Method for Mining Co-location Patterns between Network Spatial Phenomena[J]. Geomatics and Information Science of Wuhan University, 2015, 40(5): 652-660.
[4] HUANG Yan, SHEKHAR S, XIONG Hui. Discovering Colocation Patterns from Spatial Data Sets: A General Approach[J]. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(12): 1472-1485.
[5] YOO J S, SHEKHAR S, SMITH J, et al. A Partial Join Approach for Mining Co-Location Patterns[C]//Proceedings of the 12th Annual ACM International Workshop on Geographic Information Systems. New York: ACM, 2004: 241-249.
[6] YOO J S, SHEKHAR S. A Joinless Approach for Mining Spatial Colocation Patterns[J]. IEEE Transactions on Knowledge and Data Engineering, 2006, 18(10): 1323-1337.
[7] XIAO Xiangye, XIE Xing, LUO Qiong, et al. Density Based Co-Location Pattern Discovery[C]//Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM, 2008.
[8] EICK C F, PARMAR R, DING Wei, et al. Finding Regional Co-Location Patterns for Sets of Continuous Variables in Spatial Datasets[C]//Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM, 2008.
[9] DING Wei, EICK C F, YUAN Xiaojing, et al. A Framework for Regional Association Rule Mining and Scoping in Spatial Datasets[J]. GeoInformatica, 2011, 15(1): 1-28.
[10] MOHAN P, SHEKHAR S, SHINE J A, et al. A Neighborhood Graph based Approach to Regional Co-Location Pattern Discovery: A Summary of Results[C]//Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM, 2011: 122-132.
[11] QIAN Feng, CHIEW K, HE Qinming, et al. Mining Regional Co-Location Patterns with k NNG[J]. Journal of Intelligent Information Systems, 2014, 42(3): 485-505.
[12] YOO J S, BOW M. Mining Spatial Colocation Patterns: A Different Framework[J]. Data Mining and Knowledge Discovery, 2012, 24(1): 159-194.
[13] QIAN Feng, HE Qinming, CHIEW K, et al. Spatial Co-Location Pattern Discovery Without Thresholds[J]. Knowledge and Information Systems, 2012, 33(2): 419-445.
[14] BARUA S, SANDER J. Mining Statistically Significant Co-location and Segregation Patterns[J]. IEEE Transactions on Knowledge and Data Engineering, 2014, 26(5): 1185-1199.
[15] GELFAND A E, DIGGLE P, GUTTORP P, et al. Handbook of Spatial Statistics[M]. Boca Raton, Florida: CRC Press, 2010.
[16] BARUA S, SANDER J. Mining Statistically Sound Co-Location Patterns at Multiple Distances[C]//Proceedings of the 26th International Conference on Scientific and Statistical Database Management. New York: ACM, 2014.
[17] ILLIAN J, PENTTINEN A, STOYAN H, et al. Statistical Analysis and Modelling of Spatial Point Patterns[M]. Chichester: Wiley, 2008.
[18] WIEGAND T, HE Fangliang, HUBBELL S P. A Systematic Comparison of Summary Characteristics for Quantifying Point Patterns in Ecology[J]. Ecography, 2013, 36(1): 92-103.
[19] WIEGAND T, MOLONEY K A. Handbook of Spatial Point-Pattern Analysis in Ecology[M]. New York, NY: Chapman and Hall/CRC Press, 2014.
[20] WITKIN A. Scale-Space Filtering: A New Approach to Multi-Scale Description[C]//Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing. San Diego, California, USA: IEEE, 1984: 150-153.
[21] LEUNG Y, ZHANG Jiangshe, XU Zongben. Clustering by Scale-Space Filtering[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(12): 1396-1410.
[22] PEI Tao, ZHU A-Xing, ZHOU Chenghu, et al. A New Approach to the Nearest-Neighbour Method to Discover Cluster Features in Overlaid Spatial Point Processes[J]. International Journal of Geographical Information Science, 2006, 20(2): 153-168.