极小负co-location模式及有效的挖掘算法

来源：计算机科学与探索杂志2021年第2期北京时间：

作者：王光耀, 王丽珍, 杨培忠, 陈红梅

单位：云南大学 信息学院，昆明 650504

摘要：空间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模式,向上包含,紧凑表示