Minimal Negative Co-location Patterns and Effective Mining Algorithm

doi:10.3778/j.issn.1673-9418.2004040

Abstract

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%.

Key words: spatial data mining, spatial co-location pattern, minimal negative co-location pattern, upward inclusion, compact representation

摘要：

空间co-location（并置）模式是指实例在空间中频繁关联的一组空间特征的子集。在空间数据挖掘中，现有算法主要针对的是正模式的挖掘，而空间中还存在着具有强负相关性的模式，如负co-location模式，这类模式的挖掘在一些应用中同样具有重要的意义。现有的负co-location模式挖掘算法的时间复杂度较高，挖掘到的模式数量巨大。针对该问题，探索了负co-location模式的向上包含性质，提出了极小负co-location模式，证明了极小负co-location模式可推导出所有频繁负co-location模式。在负co-location模式挖掘中，计算模式的表实例是制约挖掘效率的根本因素，为此提出了3个剪枝策略有效地提高了算法的效率。在真实和合成数据集上的大量实验，验证了提出方法的正确性和高效性。特别地，大量实验结果表明极小负co-location模式可将频繁负co-location模式数量压缩80%以上。

关键词: 空间数据挖掘, 空间co-location模式, 极小负co-location模式, 向上包含, 紧凑表示

WANG Guangyao, WANG Lizhen, YANG Peizhong, CHEN Hongmei. Minimal Negative Co-location Patterns and Effective Mining Algorithm[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(2): 366-378.

王光耀, 王丽珍, 杨培忠, 陈红梅. 极小负co-location模式及有效的挖掘算法[J]. 计算机科学与探索, 2021, 15(2): 366-378.

References

[1] HUANG Y, SHEKHAR S, XIONG H. Discovering colocation patterns from spatial data sets: a general approach[J]. IEEE Transactions on Knowledge and Data Engineering, 2004, 16 (12): 1472-1485.
[2] 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, Washington, Nov 12-13, 2004. New York: ACM, 2004: 241-249.
[3] YOO J S, SHEKHAR S, CELIK M. A join-less approach for co-location pattern mining: a summary of results[C]//Procee-dings of the 2005 IEEE International Conference on Data Mining, Houston, Nov 27-30, 2005. Washington: IEEE Com-puter Society, 2005: 813-816.
[4] WANG L Z, BAO Y Z, LU J, et al. A new join-less approach for co-location pattern mining[C]//Proceedings of the 8th IEEE International Conference on Computer and Information Tech-nology, Sydney, Jul 8-11, 2008. Washington: IEEE Computer Society, 2008: 197-202.
[5] WANG L Z, BAO Y Z, LU Z Y. Efficient discovery of spatial co-location patterns using the iCPI-tree[J]. The Open Infor-mation Systems Journal, 2009, 3(2): 69-80.
[6] OUYANG Z P, WANG L Z, CHEN H M. Mining spatial co-location patterns for fuzzy objects[J]. Chinese Journal of Com-puters, 2011, 34(10): 1947-1955.
欧阳志平, 王丽珍, 陈红梅. 模糊对象的空间Co-location模式挖掘研究[J]. 计算机学报, 2011, 34(10): 1947-1955.
[7] YANG P, WANG L, WANG X. A parallel spatial co-location pattern mining approach based on ordered clique growth[C]//LNCS 10827: Proceedings of Database Systems for Advanced Applications, Gold Coast, May 21-24, 2018. Berlin, Heidelberg: Springer, 2018: 734-742.
[8] WANG X X, WANG L Z, CHEN H M, et al. Mining spatial high utility co-location patterns based on feature utility ratio[J]. Chinese Journal of Computers, 2019, 42(8): 1721-1738.
王晓璇, 王丽珍, 陈红梅, 等. 基于特征效用参与率的空间高效用co-location模式挖掘方法[J]. 计算机学报, 2019, 42(8): 1721-1738.
[9] YANG P Z, WANG L Z, WANG X X, et al. An effective approach on mining co-location patterns from spatial databases with rare features[C]//Proceedings of the 20th IEEE Interna-tional Conference on Mobile Data Management, Hong Kong, China, Jun 10-13, 2019. Piscataway: IEEE, 2019: 53-62.
[10] WANG L Z, BAO X G, CHEN H M, et al. Effective lossless condensed representation and discovery of spatial co-location patterns[J]. Information Sciences, 2018, 436/437: 197-213.
[11] WANG L Z, BAO X G, ZHOU L H. Redundancy reduction for prevalent co-location patterns[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 30(1): 142-155.
[12] HU X, WANG L Z, ZHOU L H, et al. Mining spatial maximal co-location patterns[J]. Journal of Frontiers of Computer Science and Technology, 2014, 8(2): 150-160.
胡新, 王丽珍, 周丽华, 等. 空间极大co-location模式挖掘研究[J]. 计算机科学与探索, 2014, 8(2): 150-160.
[13] WU X X, ZHANG C Q, ZHANG S C. Efficient mining of both positive and negative association rules[J]. ACM Trans-actions on Information Systems, 2004, 22(3): 381-405.
[14] ZHENG Z G, ZHAO Y C, ZUO Z Y, et al. Negative-GSP: an efficient method for mining negative sequential patterns[C]//Proceedings of the 8th Australasian Data Mining Con-ference, Melbourne, Dec, 2009. Australian Computer Society, 2009: 63-67.
[15] CAO L B, DONG X J, ZHENG Z G. e-NSP: efficient negative sequential pattern mining[J]. Artificial Intelligence, 2016, 235: 156-182.
[16] DONG X J, GONG Y S, CAO L B. F-NSP+: a fast negative sequential patterns mining method with self-adaptive data storage[J]. Pattern Recognition, 2018, 84: 13-27.
[17] JIANG Y, WANG L Z, LU Y, et al. Discovering both positive and negative co-location rules from spatial data sets[C]//Proceedings of the 2nd International Conference on Software Engineering and Data Mining, Chengdu, Jun 23-25, 2010. Piscataway: IEEE, 2010: 398-403.
[18] SHEKHAR S, HUANG Y. Discovering spatial co-location patterns: a summary of results[C]//LNCS 2121: Proceedings of the 7th International Symposium on Advances in Spatial and Temporal Databases, Redondo Beach, Jul 12-15, 2001. Berlin, Heidelberg: Springer, 2001: 236-256.