基于Voronoi图的空间Co-Location核模式挖掘  

Mining Co-Location Core Patterns in Spatial Data Sets Based on the Voronoi Diagram

作　　者：邹目权 王丽珍[1] 吴萍萍[1] 杨培忠 ZOU Mu-Quan;WANG Li-Zhen;WU Ping-Ping;YANG Pei-Zhong(Department of Computer Science and Engineering,Yunnan University,Kunming 650500;School of Information Engineering,Kunming University,Kunming 650214)

机构地区：[1]云南大学计算机科学与工程系,昆明650500 [2]昆明学院信息工程学院,昆明650214

出　　处：《计算机学报》2022年第9期1908-1925,共18页Chinese Journal of Computers

基　　金：国家自然科学基金(61966036,61662086,62066023);云南省科学创新团队项目(2018IIC019);昆明学院科学研究项目(XJZZ1706)资助

摘　　要：飞速发展的物联网技术不断催生海量带有时间和空间属性的数据集.这些数据集掀起了以空间co-location模式挖掘为代表的空间数据挖掘研究的高潮.传统空间co-location模式挖掘研究主要发现空间中频繁并置出现的特征的子集.特征在模式内部是无序的,特征之间的地位是平等的.例如,co-location模式{看守所,刑警中队,武警中队}表示看守所附近往往存在刑警中队和武警中队,反之亦然.然而,由于空间分布密度差异显著存在,现实中存在特征地位不平等的模式,这些模式中的某些特征(核特征)附近频繁地出现其它特征(非核特征)的实例,而这些非核特征附近不一定频繁地出现核特征的实例.例如,某些肿瘤疾病与某些污染源的关系.在传统模型中,用户为了发现感兴趣的模式不得不将频繁性阈值设置得很低,以至于忽略了模式中特征的主从关系.本文聚焦于前述现象,研究在空间数据集中挖掘核特征与非核特征组成的有趣模式.首先,基于核邻居定义空间co-location核频繁模式(简称核模式)的概念.核邻居与最近邻息息相关,它不仅遵从地理学第一定律而且能排除无关实例的干扰.其次,提出核模式的有趣性度量理论,分析核模式具有的性质,如基于核参与率反单调性的先验原理等.再次,提出基于Voronoi图的核邻居计算思想,避免了传统co-location模式挖掘中为计算邻近关系需要用户预先设定距离阈值等问题.同时,扩展传统的对称的空间邻近关系到不对称的核邻居关系,使其与特征的不平等地位相适应.此外,针对点、线、面等不同几何形状的空间实例,提出基于凹包理论的经典Voronoi图的扩展方法.最后,在合成数据与真实数据上对比验证了Core Pattern Mining(CPM)算法的效果与效率.实验高效地发现了有别于经典co-location模式的有趣模式,它们具有可理解性.With the development of the Internet of Things(IoT),massive spatio-temporal data sets are collected.It has set off the climax of spatial data mining research that is represented by spatial co-location pattern mining.The traditional spatial co-location pattern mining is mainly used to find subsets of spatial feature sets from given spatial data sets.Spatial features in the subsets are frequently co-occurrence in the geographic space.For example,the co-location pattern{detention center,criminal police squadron,armed police squadron}reveals that there are always detention centers and criminal police squadrons near armed police squadrons and vice versa.That is to say,spatial features(e.g.,the detention center and criminal police squadron)are generally thought to be disordered and equal in each pattern in default.However,there are interesting patterns whose spatial features have unequal status because distribution densities of different spatial features tend to be different.In detail,some spatial features,which are called core features in this paper,are surrounded by the others,but the others may have no such properties.The distribution relationship between cancer cases and pollution sources is an example.To find this kind of patterns,which is called the co-location core pattern in this paper,users have to set low prevalence thresholds with neglection of those differences in the traditional co-location pattern mining.Interestingly,co-location core patterns reveal underlying subordinative compounds.Thus,this paper focuses on the unequal status of spatial features to propose theorems and methods to discover core features and their surrounding features in spatial data sets.Firstly,the prevalent co-location core pattern is defined on core neighbors.Core neighbors are strongly related to nearest neighbors.Not only do they obey the first law of geography well but they also eliminate noise from instances of unrelated features.Secondly,The prevalence measure theory of the core pattern is proposed.The prevalence of a co-locati

关 键 词：空间数据挖掘 co-location核模式 核邻居 VORONOI图 核参与度 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]