基于空间占有度的主导并置模式挖掘

传统的空间并置模式挖掘旨在发现空间中实例频繁共存的特征子集.目前空间并置模式的大多数研究都将模式的频繁性作为兴趣度度量.然而,在实际应用场景中,用户往往不仅对特征集的频繁性感兴趣,而且对它的完整性也感兴趣.结合并置模式的频繁性和完整性,提出主导空间并置模式(dominant spatial co-location pa...     

空间co-location模式挖掘中的模糊技术初探

空间并置（co-location）模式是指其特征的实例在地理空间中频繁并置出现的一组空间特征的集合。传统co-location模式挖掘通常由用户给定一个邻近阈值来确定实例的邻近关系，使用单一的邻近阈值来判定两个空间实例的邻近性可能会造成邻近关系的缺失，也没有考虑距离大小的不同对邻近关系的影响。同时，传统方法主要利用频繁性阈值来衡量模式的频繁性，存在着算法效率对频繁性阈值较为敏感的问题。由于频繁并置的特征间具有较高的邻近度，因此利用聚类算法可以将其聚集在一起，加之邻近以及特征间的并置都是模糊的概念，因此将模糊集理论与聚类算法相结合，研究了空间co-location模式挖掘中的模糊挖掘技术，在定义模糊邻近关系的基础上，定义了度量特征之间邻近度的函数，基于特征邻近度利用模糊聚类算法挖掘co-location模式，最后通过广泛的实验验证了提出方法的实用性、高效性及鲁棒性。     

含关键特征的显著Co-location模式挖掘研究

空间Co-location模式是一组在空间中频繁并置的空间特征的子集。空间Co-location模式挖掘通常假设空间实例之间相互独立,然而,在实际应用中,不同空间特征、不同实例之间往往相互作用或依赖。空间Co-location关键特征是指对模式具有主导作用的特征。在频繁模式中,识别含关键特征的Co-location模式并摘取模式中的关键特征,为用户提供更精简的挖掘结果,提高Co-location模式的可用性,对Co-location模式挖掘具有重要意义。本文首先定义了含有关键特征的显著频繁Co-location模式新概念,以及一系列度量指标以识别显著频繁Co-location模式中的关键特征;其次,给出了一个挖掘显著频繁Co-location模式和关键特征的算法;最后,在模拟和真实数据集上进行了大量的实验,验证了所提出算法的效果及性能。     

基于图数据库的空间频繁并置模式挖掘

空间频繁并置模式(SPCP)是一组空间特征的子集,它们的实例在地理空间中频繁地出现在一起.基于内存物化实例邻近关系并搜索模式实例效率较高,但实例信息会被重复存储.图数据库技术能高效地对具有复杂关联关系的数据建模,但基于实例邻近关系图移植已有的挖掘方法不能发挥图遍历的优势.针对上述问题,探索了基于图数据库的空间频繁并置模...     

模糊特征的top-k平均效用co-location模式挖掘

空间并置(co-location)模式是指在空间邻域内空间特征的实例频繁地出现在一起所形成的非空特征子集.人们已经对确定数据和不确定数据的top-k空间co-location模式挖掘进行了相关研究,但是针对模糊特征的top-k平均效用co-location模式挖掘的研究还没有.提出模糊特征的top-k平均效用co-lo...     

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

空间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模式是其实例在空间邻域内频繁并置出现的一组空间特征集.传统的空间co-location模式挖掘方法通常假设空间实例相互独立,并采用参与度作为模式有趣性的唯一度量指标,没有考虑不同特征或相同特征不同实例在空间邻域内所产生的影响差异,因此挖掘的结果往往缺乏相关性和可解释性.文中提出了一种星型高影响...     

空间亚频繁co-location模式的主导特征挖掘

空间co-location模式是一组空间特征的子集,它们的实例在邻域内频繁并置出现。通常,空间co-location模式挖掘方法假设空间实例相互独立,并采用空间实例参与到模式实例的频繁性（参与率）来度量空间特征在模式中的重要性,采用空间特征的最小参与率（参与度）来度量模式的有趣程度,忽略了空间特征间的某些重要关系。因此为了揭示空间特征间的主导关系而提出主导特征co-location模式。现有主导特征模式挖掘方法是基于传统频繁模式及其团实例模型进行挖掘,然而,团实例模型可能会忽略非团的空间特征间的主导关系。因此,基于星型实例模型,研究空间亚频繁co-location模式的主导特征挖掘,以更好地揭示空间特征间的主导关系,挖掘更有价值的主导特征模式。首先,定义了两个度量特征主导性的指标;其次,设计了有效的主导特征co-location模式挖掘算法;最后,在合成数据集和真实数据集上通过大量实验验证了所提算法的有效性以及主导特征模式的实用性。     

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

飞速发展的物联网技术不断催生海量带有时间和空间属性的数据集.这些数据集掀起了以空间co-location模式挖掘为代表的空间数据挖掘研究的高潮.传统空间co-location模式挖掘研究主要发现空间中频繁并置出现的特征的子集.特征在模式内部是无序的,特征之间的地位是平等的.例如,co-location模式{看守所,刑警中队,武警中队}表示看守所附近往往存在刑警中队和武警中队,反之亦然.然而,由于空间分布密度差异显著存在,现实中存在特征地位不平等的模式,这些模式中的某些特征(核特征)附近频繁地出现其它特征(非核特征)的实例,而这些非核特征附近不一定频繁地出现核特征的实例.例如,某些肿瘤疾病与某些污染源的关系.在传统模型中,用户为了发现感兴趣的模式不得不将频繁性阈值设置得很低,以至于忽略了模式中特征的主从关系.本文聚焦于前述现象,研究在空间数据集中挖掘核特征与非核特征组成的有趣模式.首先,基于核邻居定义空间co-location核频繁模式(简称核模式)的概念.核邻居与最近邻息息相关,它不仅遵从地理学第一定律而且能排除无关实例的干扰.其次,提出核模式的有趣性度量理论,分析核模式具有的性质,如...     

MLCPM-UC:一种基于模式实例分布均匀系数的多级co-location模式挖掘算法

空间co-location(并置)模式是一组空间特征的子集,其实例在空间中频繁地邻近出现.由于空间数据同时存在关联性和异质性,co-location模式实例的分布或在整个研究区域中全局出现(全局co-location模式),或在研究区域的局部区域出现(区域co-location模式),从而提出了多级co-location模式挖掘.当前的多级co-location模式挖掘方法存在两个问题:1)已有的多级co-location模式挖掘方法忽略了模式在空间中的分布特性,未能准确区分全局和区域co-location模式;2)已有的多级模式挖掘方法将全局非频繁co-location模式作为候选区域co-location模式,导致候选区域co-location模式数量过多.针对以上问题,首先,定义了模式的实例分布均匀系数,在考虑模式频繁性的同时考虑了模式在空间中的分布情况,从而正确、高效地识别出全局和区域co-location模式.其次,基于模式的实例分布均匀系数,设计了一个有效的多级co-location模式挖掘算法,提出了有效的剪枝策略以提高算法效率.最后,在真实和合成数据集上进行了广泛的实验,验证了所提方法的正确性和高效性.     

空间极大co-location模式挖掘研究

空间co-location模式代表了一组空间特征的子集,它们的实例在空间中频繁地关联。挖掘空间co-location模式的研究已经有很多,但是针对极大co-location模式挖掘的研究非常少。提出了一种新颖的空间极大co-location模式挖掘算法。首先扫描数据集得到二阶频繁模式,然后将二阶频繁模式转换为图,再通过极大团算法求解得到空间特征极大团,最后使用二阶频繁模式的表实例验证极大团得到空间极大co-location频繁模式。实验表明,该算法能够很好地挖掘空间极大co-location频繁模式。     

A fast space-saving algorithm for maximal co-location pattern mining

Real space teems with potential feature patterns with instances that frequently appear in the same locations. As a member of the data-mining family, co-location can effectively find such feature patterns in space. However, given the constant expansion of data, efficiency and storage problems become difficult issues to address. Here, we propose a maximal-framework algorithm based on two improved strategies. First, we adopt a degeneracy-based maximal clique mining method to yield candidate maximal co-locations to achieve high-speed performance. Motivated by graph theory with parameterized complexity, we regard the prevalent size-2 co-locations as a sparse undirected graph and subsequently find all maximal cliques in this graph. Second, we introduce a hierarchical verification approach to construct a condensed instance tree for storing large instance cliques. This strategy further reduces computing and storage complexities. We use both synthetic and real facility data to compare the computational time and storage requirements of our algorithm with those of two other competitive maximal algorithms: “order-clique-based” and “MAXColoc”. The results show that our algorithm is both more efficient and requires less storage space than the other two algorithms.     

k-近邻关系下的空间高效用核模式挖掘

空间数据挖掘旨在从空间数据库中发现和提取有价值的潜在知识.空间co-location(共存)模式挖掘一直以来都是空间数据挖掘领域的重要研究方向之一,其目的 是发现一组频繁邻近出现的空间特征子集,而空间高效用co-location模式挖掘则考虑了特征的效用属性.二者在度量空间实例的邻近关系时一般都需要预先给定一个距离阈值...     

实例位置模糊的空间co-location模式挖掘研究

实例位置模糊在许多领域里都有着非常重要的应用,比如生物医学图像数据库和地理信息系统(geographic information system,GIS)。研究了实例位置模糊的空间co-location模式挖掘问题。定义了实例位置模糊的空间co-location模式挖掘的相关概念,包括实例位置模糊、位置参与率等;给出了基本算法来挖掘实例位置模糊的co-location模式;提出了两种改进算法,即基于网格的距离计算和减枝候选模式,以提高挖掘性能,加快co-location规则的产生。通过大量的实验,说明了基本算法及其改进算法的效果和效率。     

基于改进列计算的空间并置模式挖掘方法

空间并置（co-location）模式挖掘旨在发现空间特征间的关联关系,是空间数据挖掘的重要研究方向。基于列计算的空间并置模式挖掘方法（CPM-Col算法）避开挖掘过程中最耗时的表实例生成操作,直接搜索模式的参与实例,成为当前高效的方法之一。然而,回溯法搜索参与实例仍是该方法的瓶颈,尤其在稠密数据和长模式下。为加速参与实例的搜索,充分利用CPM-Col算法搜索参与实例时得到的行实例,在不增加额外计算的前提下对CPM-Col算法进行两点改进。首先,将CPM-Col算法搜索到的行实例存储为部分表实例,利用子模式的部分表实例快速确定参与实例,避免了大量实例的回溯计算。其次,在CPM-Col算法获得一条行实例后,利用行实例的子团反作用于第一个特征,得到第一个特征的参与实例,避免了这些实例的回溯搜索。由此,提出了基于改进列计算的空间并置模式挖掘算法（CPM-iCol算法）,并讨论了算法的复杂度、正确性和完备性。在合成数据和真实数据集上进行了实验,与经典的传统算法join-less和CPM-Col算法对比,CPM-iCol算法明显降低了挖掘的时间,减少了回溯的次数。实验结果表明,该算法比CPM-Col具有更好的性能和可扩展性,特别在稠密数据集中效果更加明显。     

An order-clique-based approach for mining maximal co-locations

Most algorithms for mining spatial co-locations adopt an Apriori-like approach to generate size-k prevalence co-locations after size-(k − 1) prevalence co-locations. However, generating and storing the co-locations and table instances is costly. A novel order-clique-based approach for mining maximal co-locations is proposed in this paper. The efficiency of the approach is achieved by two techniques: (1) the spatial neighbor relationships and the size-2 prevalence co-locations are compressed into extended prefix-tree structures, which allows the order-clique-based approach to mine candidate maximal co-locations and co-location instances; and (2) the co-location instances do not need to be stored after computing some characteristics of the corresponding co-location, which significantly reduces the execution time and space required for mining maximal co-locations. The performance study shows that the new method is efficient for mining both long and short co-location patterns, and is faster than some other methods (in particular the join-based method and the join-less method).