空间 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模式挖掘研究

空间co-location模式代表了一组空间特征的子集,它们的实例在空间中频繁地关联。挖掘空间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模式是一组空间特征的子集,它们的实例在空间中频繁关联。利用co-location模式的这种特征间“共存”关系,提出了一种基于co-location模式的地址选择算法,该算法基于本体描述空间数据的分类信息,并在本体的指导下对用户感兴趣的兴趣点（Point of Interest）进行关键co-location模式挖掘,同时针对实际情况对数据进行了预处理以增加算法的有效性。在真实数据集（北京市的兴趣点数据）上的评估实验显示该算法具有较高的准确率,选择的地址具有高可靠性。     

基于CPRIP—Tree的伴生模式挖掘算法

现有的大多数空间伴生模式挖掘算法采用类似Apriori生成方法,通过自底向上,逐层检验的方式挖掘频繁模式。本文提出了一种新的基于伴生模式行实例投影树CPRIP—Tree（Co—location Pattern Row_Instance Projection Tree）的挖掘算法,该算法通过实例查找方式生成伴生模式行实例以构建CPRIP—Tree,并在其基础上上直接挖掘频繁模式。最后通过模拟数据实例分析证明了该算法较基于Apriori算法具有更高的挖掘效率。     

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

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

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

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

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

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

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.     

Spatial co-location pattern discovery without thresholds

Spatial co-location pattern mining discovers the subsets of features whose events are frequently located together in geographic space. The current research on this topic adopts a threshold-based approach that requires users to specify in advance the thresholds of distance and prevalence. However, in practice, it is not easy to specify suitable thresholds. In this article, we propose a novel iterative mining framework that discovers spatial co-location patterns without predefined thresholds. With the absolute and relative prevalence of spatial co-locations, our method allows users to iteratively select informative edges to construct the neighborhood relationship graph until every significant co-location has enough confidence and eventually to discover all spatial co-location patterns. The experimental results on real world data sets indicate that our framework is effective for prevalent co-locations discovery.     

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.