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.

Spatial ordering and encoding for geographic data mining and visualization

Geographic information (e.g., locations, networks, and nearest neighbors) are unique and different from other aspatial attributes (e.g., population, sales, or income). It is a challenging problem in spatial data mining and visualization to take into account both the geographic information and multiple aspatial variables in the detection of patterns. To tackle this problem, we present and evaluate a variety of spatial ordering methods that can transform spatial relations into a one-dimensional ordering and encoding which preserves spatial locality as much possible. The ordering can then be used to spatially sort temporal or multivariate data series and thus help reveal patterns across different spaces. The encoding, as a materialization of spatial clusters and neighboring relations, is also amenable for processing together with aspatial variables by any existing (non-spatial) data mining methods. We design a set of measures to evaluate nine different ordering/encoding methods, including two space-filling curves, six hierarchical clustering based methods, and a one-dimensional Sammon mapping (a multidimensional scaling approach). Evaluation results with various data distributions show that the optimal ordering/encoding with the complete-linkage clustering consistently gives the best overall performance, surpassing well-known space-filling curves in preserving spatial locality. Moreover, clustering-based methods can encode not only simple geographic locations, e.g., x and y coordinates, but also a wide range of other spatial relations, e.g., network distances or arbitrarily weighted graphs.     

Summary statistics for measuring the relationship among three types of points in multivariate point patterns

In multivariate spatial point patterns’ statistical analysis, conventional summary statistics can only detect the dependence between two types of points, and cannot be used to detect the dependence among three types of points. New summary statistics are proposed which can be used to detect the influence of the presence the kth type points on the relationship between the ith and the jth type points when the relationship between the ith and the jth type points is positive correlation (or negative correlation, or no spatial interaction), can also be used to infer information about the type of correlation and the range of interaction in multivariate point patterns. In order to reduce the edge-effects the border method to estimate the proposed summary statistics is applied. A simulation and a real example are used to illustrate the proposed methodologies.     

A mathematical morphology based method for hierarchical clustering analysis of spatial points on street networks

Spatial clustering analysis is an important issue that has been widely studied to extract the meaningful subgroups of geo-referenced data. Although many approaches have been developed in the literature, efficiently modeling the network constraint that objects (e.g. urban facility) are observed on or alongside a street network remains a challenging task for spatial clustering. Based on the techniques of mathematical morphology, this paper presents a new spatial clustering approach NMMSC designed for mining the grouping patterns of network-constrained point objects. NMMSC is essentially a hierarchical clustering approach, and it generally consists of two main steps: first, the original vector data is converted to raster data by utilizing basic linear unit of network as the pixel in network space; second, based on the specified 1-dimensional raster structure, an extended mathematical morphology operator (i.e. dilation) is iteratively performed to identify spatial point agglomerations with hierarchical structure snapped on a network. Compared to existing methods of network-constrained hierarchical clustering, our method is more efficient for cluster similarity computation with linear time complexity. The effectiveness and efficiency of our approach are verified through the experiments with real and synthetic data sets.     

Spatio-Temporal Analysis with the Self-Organizing Feature Map

Spatio-temporal pattern recognition problems are particularly challenging. They typically involve detecting change that occurs over time in two-dimensional patterns. Analytic techniques devised for temporal data must take into account the spatial relationships among data points. An artificial neural network known as the self-organizing feature map (SOM) has been used to analyze spatial data. This paper further investigates the use of the SOM with spatio-temporal pattern recognition. The principles of the two-dimensional SOM are developed into a novel three-dimensional network and experiments demonstrate that (i) the three-dimensional network makes a better topological ordering and (ii) there is a difference in terms of the spatio-temporal analysis that can be made with the three-dimensional network. Received 21 October 1999 / Revised 11 February 2000 / Accepted 2 May 2000     

Spatial persistence

We examine the spatial version of the persistence problem. In temporal reasoning, this is the problem of determining whether or not the validity of a fact at some point in time persists until another point in time, given that certain events or processes may happen in between. We show that its analog does intuitively exist in spatial reasoning, and review under the aspect of transferability to space different approaches for achieving persistence in temporal reasoning. Finally, we present reasoning with generalized spatial Allen relations as an instance of reasoning under the assumption of spatial persistence.This author has partially been supported under grant numbers A18/XXXXX/62090/3414014 and A18/XXXXX/62090/F3414025 by the University of Auckland Research Fund.     

Quasi-plus sampling edge correction for spatial point patterns

A widely applicable edge correction method for estimating summary statistics of a spatial point pattern is proposed. We reconstruct point patterns in a larger region containing the sampling window by matching sampled and simulated kth nearest neighbour distance distributions of the given pattern and then apply plus sampling. Simulation studies show that this approach, called quasi-plus sampling, gives estimates with smaller root mean squared errors than estimates obtained by using other popular edge corrections. We apply the proposed approach to real data and yield an estimate of a summary statistic that is more plausible than that obtained by a popular edge correction.     

Spatial monitoring of geographic patterns: an application to crime analysis

This paper describes a new procedure for detecting changes over time in the spatial pattern of point events, combining the nearest neighbor statistic and cumulative sum methods. The method results in the rapid detection of deviations from expected geographic patterns. It may also be used for various subregions and may be implemented using time windows of differing length to search for any changes in spatial pattern that may occur at particular time scales. The method is illustrated using 1996 arson data from the Buffalo, NY, Police Department.     

用探测性的归纳学习方法从空间数据库发现知识

将探测性数据分析,面向属性的归纳和Ｒｏｕｇｈ集方法结合起来,形成了一种灵活通用的探测性归纳米学习方法ＥＩＬ,可以从空间数据库中发现普遍知识,属性依赖,分类知识等多种知识,同时提出了和总结了多种生成空间数据库概念层次结构的方法用于归纳学习,用中国分省农业统计数据的发掘试验说明了ＥＩＬ的可行性和有效性。     

A test for multidimensional clustering tendency

This paper examines a d-dimensional extension of the Cox-Lewis statistic and investigates its power as a function of dimensionality in discriminating among random, aggregated and regular arrangements of points in d-dimensions. It was motivated by the Clustering Tendency problem which attempts to prevent the inappropriate application of clustering algorithms and other exploratory procedures. After reviewing the literature, the d-dimensional Cox-Lewis statistic is defined and its distribution under a randomness hypothesis of a Poisson spatial point process is given. Analytical expressions for the densities of the Cox-Lewis statistic under lattice regularity and under extreme clustering are also provided. The powers of Neyman-Pearson tests of hypotheses based on the Cox-Lewis statistic are derived and compared. Power is a unimodal function of dimensionality in the test of lattice regularity, with the minimum occurring at 12 dimensions.The power of the Cox-Lewis statistic is also examined under hard-core regularity and under Neyman-Scott clustering with Monte Carlo simulations. The Cox-Lewis statistic leads to one-sided tests for regularity having reasonable power and provides a sharper discrimination between random and clustered data than other statistics. The choice of sampling window is a critical factor. The Cox-Lewis statistic shows great promise for assessing the gross structure of data.     

Detecting and tracking regional outliers in meteorological data

Detecting spatial outliers can help identify significant anomalies in spatial data sequences. In the field of meteorological data processing, spatial outliers are frequently associated with natural disasters such as tornadoes and hurricanes. Previous studies on spatial outliers mainly focused on identifying single location points over a static data frame. In this paper, we propose and implement a systematic methodology to detect and track regional outliers in a sequence of meteorological data frames. First, a wavelet transformation such as the Mexican Hat or Morlet is used to filter noise and enhance the data variation. Second, an image segmentation method, λ-connected segmentation, is employed to identify the outlier regions. Finally, a regression technique is applied to track the center movement of the outlying regions for consecutive frames. In addition, we conducted experimental evaluations using real-world meteorological data and events such as Hurricane Isabel to demonstrate the effectiveness of our proposed approach.     

基于GIS的空间分析及其发展研究

空间分析是基于地理对象空间布局的地理数据分析技术,GIS的空间分析功能偏弱已经严重地阻碍了其作为空间数据分析和研究工具的使用。新兴的智能计算技术为空间分析提供了新的机遇和发展契机,神经网络、进化计算和人工生命在基于GIS的空间分析建模应用上具有巨大潜力。研究发现基于GIS空间分析的发展将向时空分析领域拓展,同时急待建立基于智能计算技术的时空分析的有效模型和统一框架,形成GIS与时空分析模型高度融合的时空决策平台。     

一种基于密度的空间数据流在线聚类算法

为了解决空间数据流中任意形状簇的聚类问题,提出了一种基于密度的空间数据流在线聚类算法(On-line density-based clustering algorithm for spatial datastream,OLDStream),该算法在先前聚类结果上聚类增量空间数据,仅对新增空间点及其满足核心点条件的邻域数据做局部聚类更新,降低聚类更新的时间复杂度,实现对空间数据流的在线聚类.OLDStream算法具有快速处理大规模空间数据流、实时获取全局任意形状的聚类簇结果、对数据流的输入顺序不敏感、并能发现孤立点数据等优势.在真实数据和合成数据上的综合实验验证了算法的聚类效果、高效率性和较高的可伸缩性,同时实验结果的统计分析显示仅有4%的空间点消耗最坏运行时间,对每个空间点的平均聚类时间约为0.033 ms.     

空间索引技术-回顾与展望

空间数据库系统通过引入空间索引机制来提高空间数据操作的效率。迄今人们已经提出了许多空间索引方法,文章回顾了这些方法的基本思想,并根据它们所采用的基础数据结构和存储空间数据的方法将现有的空间索引方法进行分类。最后,简要的讨论了空间索引方法的发展方向。     

Knowledge-based spatiotemporal linear abstraction

We present a theoretical framework and a case study for reusing the same conceptual and computational methodology for both temporal abstraction and linear (unidimensional) space abstraction, in a domain (evaluation of traffic-control actions) significantly different from the one (clinical medicine) in which the method was originally used. The method, known asknowledge-based temporal abstraction, abstracts high-level concepts and patterns from time-stamped raw data using a formal theory of domain-specific temporal-abstraction knowledge. We applied this method, originally used to interpret time-oriented clinical data, to the domain of traffic control, in which the monitoring task requires linear pattern matching along both space and time. First we reused the method for creation of unidimensional spatial abstractions over highways, given sensor measurements along each highway measured at the same time point. Second, we reused the method to create temporal abstractions of the traffic behaviour, for the same space segments, but during consecutive time points. We defined the corresponding temporal-abstraction and spatial-abstraction domain-specific knowledge. Our results suggest that (1) the knowledge-base temporal-abstraction method is reusable over time and unidimensional space as well as over significantly different domains; (2) the method can be generalised into a knowledge-based linear-abstraction method, which solves tasks requiring abstraction of data along any linear distance measure; and (3) a spatiotemporal-abstraction method can be assembled, from two copies of the generalised method and a spatial-decomposition mechanism, and is applicable to tasks requiring abstraction of time-oriented data into meaningful spatiotemporal patterns over a linear, decomposable space, such as traffic over a set of highways.     

空间数据库的聚类方法

1 引言近年来,数据库的数量和单个数据库的容量都大大增长了。比如,空间物体数据库包括几十亿个望远镜图像,NASA地球观测系统每小时都会产生50GB的数据。这么大的数据量已经远远超出了人为分析解释的能力范围。数据库中的知识发现(KDD)是识别数据中有价值的、新的、潜在有用的、可理解的模式的一     

空间数据挖掘研究综述

信息化的发展使得更多的空间数据被使用,因此获取空间知识也就越来越重要和有意义,并使得空间数据挖掘成为一个很有前途的研究领域。本文系统概括了空间分类和预测、空间聚类、空间孤立点和空间关联规则4类空间数据挖掘方法及其进展,最后探讨了空间数据挖掘的未来发展方向。