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

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

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

Mining regional co-location patterns with kNNG

Spatial co-location pattern mining discovers the subsets of features of which the events are frequently located together in geographic space. The current research on this topic adopts a distance threshold that has limitations in spatial data sets with various magnitudes of neighborhood distances, especially for mining of regional co-location patterns. In this paper, we propose a hierarchical co-location mining framework accounting for both variety of neighborhood distances and spatial heterogeneity. By adopting k-nearest neighbor graph (kNNG) instead of distance threshold, we propose “distance variation coefficient” as a new measure to drive the mining operations and determine an individual neighborhood relationship graph for each region. The proposed mining algorithm outputs a set of regions with each of them an individual set of regional co-location patterns. The experimental results on both synthetic and real world data sets show that our framework is effective to discover these regional co-location patterns.     

空间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模式及演化模式,预测了co-location模式的演化规律,更好地实现了对珍稀植物的动态跟踪和保护.     

CPM-MCHM:一种基于极大团和哈希表的空间并置模式挖掘算法

空间并置(co-location)模式挖掘是指在大量的空间数据中发现一组空间特征的子集,这些特征的实例在地理空间中频繁并置出现.传统的空间并置模式挖掘算法通常采用逐阶递增的挖掘框架,从低阶模式开始生成候选模式并计算其参与度(空间并置模式的频繁性度量指标).虽然这种挖掘框架可以得到正确和完整的结果,但是带来的时间和空间开...     

基于co-location模式和本体的地址选择算法

选址问题是任何一个商业机构都要面临的重大决策问题之一,它受多种因素制约,比如社会经济学、地质学、生态学以及决策者的特定需求等。现有的选址方法（通常被经济学家采用）大多利用主观评价,可扩展性差。空间co-location模式挖掘是空间数据挖掘的一个重要研究方向。一个频繁co-location模式是一组空间特征的子集,它们的实例在空间中频繁关联。利用co-location模式的这种特征间“共存”关系,提出了一种基于co-location模式的地址选择算法,该算法基于本体描述空间数据的分类信息,并在本体的指导下对用户感兴趣的兴趣点（Point of Interest）进行关键co-location模式挖掘,同时针对实际情况对数据进行了预处理以增加算法的有效性。在真实数据集（北京市的兴趣点数据）上的评估实验显示该算法具有较高的准确率,选择的地址具有高可靠性。     

On discovering co-location patterns in datasets: a case study of pollutants and child cancers

We intend to identify relationships between cancer cases and pollutant emissions by proposing a novel co-location mining algorithm. In this context, we specifically attempt to understand whether there is a relationship between the location of a child diagnosed with cancer with any chemical combinations emitted from various facilities in that particular location. Co-location pattern mining intends to detect sets of spatial features frequently located in close proximity to each other. Most of the previous works in this domain are based on transaction-free apriori-like algorithms which are dependent on user-defined thresholds, and are designed for boolean data points. Due to the absence of a clear notion of transactions, it is nontrivial to use association rule mining techniques to tackle the co-location mining problem. Our proposed approach is focused on a grid based transactionization? of the geographic space, and is designed to mine datasets with extended spatial objects. It is also capable of incorporating uncertainty of the existence of features to model real world scenarios more accurately. We eliminate the necessity of using a global threshold by introducing a statistical test to validate the significance of candidate co-location patterns and rules. Experiments on both synthetic and real datasets reveal that our algorithm can detect a considerable amount of statistically significant co-location patterns. In addition, we explain the data modelling framework which is used on real datasets of pollutants (PRTR/NPRI) and childhood cancer cases.     

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

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

领域驱动的高效用co-location模式挖掘方法

空间并置（co-location）模式是指其实例在空间邻域内频繁共现的空间特征集的子集。现有的空间co-location模式挖掘的有趣性度量指标,没有充分地考虑特征之间以及同一特征的不同实例之间的差异;另外,传统的基于数据驱动的空间co-location模式挖掘方法的结果常常包含大量无用或是用户不感兴趣的知识。针对上述问题,提出一种更为一般的研究对象--带效用值的空间实例,并定义了新的效用参与度（UPI）作为高效用co-location模式的有趣性度量指标;将领域知识形式化为三种语义规则并应用于挖掘过程中,提出一种领域驱动的多次迭代挖掘框架;最后通过大量实验对比分析不同有趣性度量指标下的挖掘结果在效用占比和频繁性两方面的差异,以及引入基于领域知识的语义规则前后挖掘结果的变化情况。实验结果表明所提出的UPI度量是一种兼顾频繁和效用的更为合理的度量指标;同时,领域驱动的挖掘方法能有效地挖掘到用户真正感兴趣的模式。     

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

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

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

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

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

空间co-location(并置)模式是指实例在空间中频繁关联的一组空间特征的子集.在空间数据挖掘中,现有算法主要针对的是正模式的挖掘,而空间中还存在着具有强负相关性的模式,如负co-location模式,这类模式的挖掘在一些应用中同样具有重要的意义.现有的负co-location模式挖掘算法的时间复杂度较高,挖掘到的...     

Top-<Emphasis Type="Italic">k</Emphasis> probabilistic prevalent co-location mining in spatially uncertain data sets

A co-location pattern is a set of spatial features whose instances frequently appear in a spatial neighborhood. This paper efficiently mines the top-k probabilistic prevalent co-locations over spatially uncertain data sets and makes the following contributions: 1) the concept of the top-k probabilistic prevalent co-locations based on a possible world model is defined; 2) a framework for discovering the top-k probabilistic prevalent co-locations is set up; 3) a matrix method is proposed to improve the computation of the prevalence probability of a top-k candidate, and two pruning rules of the matrix block are given to accelerate the search for exact solutions; 4) a polynomial matrix is developed to further speed up the top-k candidate refinement process; 5) an approximate algorithm with compensation factor is introduced so that relatively large quantity of data can be processed quickly. The efficiency of our proposed algorithms as well as the accuracy of the approximation algorithms is evaluated with an extensive set of experiments using both synthetic and real uncertain data sets.     

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.     

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

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

一种无阈值的频繁模式生成算法

在数据挖掘的关联规则挖掘算法中,传统的频繁模式挖掘算法需要用户指定项集的最小支持度。引入Top-k模式挖掘概念的改进算法虽然无需指定最小支持度,但仍需指定阈值k。针对上述问题,对传统挖掘算法进行改进,提出一种新的频繁模式挖掘算法(TNFP- growth)。该算法无需指定最小支持度或阈值,按照支持度降序排列进行模式挖掘,有序地返回频繁模式给用户。实验结果证明,该算法的执行效率更高,具有更强的伸缩性。     

Spatial co-location pattern mining for location-based services in road networks

With the evolution of geographic information capture and the emergency of volunteered geographic information, it is getting more important to extract spatial knowledge automatically from large spatial datasets. Spatial co-location patterns represent the subsets of spatial features whose objects are often located in close geographic proximity. Such pattern is one of the most important concepts for geographic context awareness of location-based services (LBS). In the literature, most existing methods of co-location mining are used for events taking place in a homogeneous and isotropic space with distance expressed as Euclidean, while the physical movement in LBS is usually constrained by a road network. As a result, the interestingness value of co-location patterns involving network-constrained events cannot be accurately computed. In this paper, we propose a different method for co-location mining with network configurations of the geographical space considered. First, we define the network model with linear referencing and refine the neighborhood of traditional methods using network distances rather than Euclidean ones. Then, considering that the co-location mining in networks suffers from expensive spatial-join operation, we propose an efficient way to find all neighboring object pairs for generating clique instances. By comparison with the previous approaches based on Euclidean distance, this approach can be applied to accurately calculate the probability of occurrence of a spatial co-location on a network. Our experimental results from real and synthetic data sets show that the proposed approach is efficient and effective in identifying co-location patterns which actually rely on a network.     

Mining Co-Location Patterns with Rare Events from Spatial Data Sets

A co-location pattern is a group of spatial features/events that are frequently co-located in the same region. For example, human cases of West Nile Virus often occur in regions with poor mosquito control and the presence of birds. For co-location pattern mining, previous studies often emphasize the equal participation of every spatial feature. As a result, interesting patterns involving events with substantially different frequency cannot be captured. In this paper, we address the problem of mining co-location patterns with rare spatial features. Specifically, we first propose a new measure called the maximal participation ratio (maxPR) and show that a co-location pattern with a relatively high maxPR value corresponds to a co-location pattern containing rare spatial events. Furthermore, we identify a weak monotonicity property of the maxPR measure. This property can help to develop an efficient algorithm to mine patterns with high maxPR values. As demonstrated by our experiments, our approach is effective in identifying co-location patterns with rare events, and is efficient and scalable for large-scale data sets.

带邻近作用的高增益率co-location模式挖掘

大多数空间co-location模式挖掘将距离阈值作为衡量不同对象实例间邻近关系的标准,进而挖掘出频繁co-location模式,并没有考虑具有邻近关系的实例间的相互影响和模式的增益率问题。在空间co-location模式挖掘过程中,引入实例间的相互作用率和对象的季均收益,定义了对象作用率、套间总收益和增益率等概念,并提出挖掘高增益率co-location模式的基础算法（NAGA）和有效的剪枝算法（NAGA_JZ）。最后通过大量的实验来验证基础算法的正确性和实用性,并对基础算法和剪枝算法的挖掘效率进行了对比,验证了剪枝算法的高效性。     

A framework of spatial co-location pattern mining for ubiquitous GIS

A spatial co-location pattern represents relationships between spatial features that are frequently located in close proximity to one another. Such a pattern is one of the most important concepts for geographic context awareness of ubiquitous Geographic Information System (GIS). We constructed a framework for co-location pattern mining using the transaction-based approach, which employs maximal cliques as a transaction-type dataset; we first define transaction-type data and verify that the definition satisfies the requirements, and we also propose an efficient way to generate all transaction-type data. The constructed framework can play a role as a theoretical methodology of co-location pattern mining, which supports geographic context awareness of ubiquitous GIS.