A Survey on Spatial Data Mining Methods Databases and Statistics
---
paper_title: STING: A Statistical Information Grid Approach to Spatial Data Mining

paper_content:

Spatial data mining, i.e., discovery of interesting characteristics and patterns that may implicitly exist in spatial databases, is a challenging task due to the huge amounts of spatial data and to the new conceptual nature of the problems which must account for spatial distance. Clustering and region oriented queries are common problems in this domain. Several approaches have been presented in recent years, all of which require at least one scan of all individual objects (points). Consequently, the computational complexity is at least linearly proportional to the number of objects to answer each query. In this paper, we propose a hierarchical statistical information grid based approach for spatial data mining to reduce the cost further. The idea is to capture statistical information associated with spatial cells in such a manner that whole classes of queries and clustering problems can be answered without recourse to the individual objects. In theory, and confirmed by empirical studies, this approach outperforms the best previous method by at least an order of magnitude, especially when the data set is very large.
---
paper_title: Discovery of General Knowledge in Large Spatial Databases

paper_content:

Extraction of interesting and general knowledge from large spatial databases is an important task in the development of spatial dataand knowledge-base systems. In this paper, we investigate knowledge discovery in spatial databases and develop a generalization-based knowledge discovery mechanism which integrates attribute-oriented induction on nonspatial data and spatial merge and generalization on spatial data. The study shows that knowledge discovery has wide applications in spatial databases, and relatively efficient algorithms can be developed for discovery of general knowledge in large spatial databases.
---
paper_title: Density-Connected Sets and their Application for Trend Detection in Spatial Databases

paper_content:

Several clustering algorithms have been proposed for class identification in spatial databases such as earth observation databases. The effectivity of the well-known algorithms such as DBSCAN, however, is somewhat limited because they do not fully exploit the richness of the different types of data contained in a spatial database. In this paper, we introduce the concept of density-connected sets and present a significantly generalized version of DBSCAN. The major properties of this algorithm are as follows: (1) any symmetric predicate can be used to define the neighborhood of an object allowing a natural definition in the case of spatially extended objects such as polygons, and (2) the cardinality function for a set of neighboring objects may take into account the non-spatial attributes of the objects as a means of assigning application specific weights. Density-connected sets can be used as a basis to discover trends in a spatial database. We define trends in spatial databases and show how to apply the generalized DBSCAN algorithm for the task of discovering such knowledge. To demonstrate the practical impact of our approach, we performed experiments on a geographical information system on Bavaria which is representative for a broad class of spatial databases.
---
paper_title: The Contiguity Ratio and Statistical Mapping

paper_content:

The problem discussed in this paper is to determine whether statistics given for each "county" in a "country" are distributed at random or whether they form a pattern. The statistical instrument is the contiguity ratio c defined by formula (1.1) below, which is an obvious generalization of the Von Neumann (1941) ratio used in one-dimensional analysis, particularly time series. While the applications in the paper are confined to oneand two-dimensional problems, it is evident that the theory applies to any number of dimensions. If the figures for adjoining counties are generally closer than those for counties not adjoining, the ratio will clearly tend to be less than unity. The constants are such that when the statistics are distributed at random in the counties, the average value of the ratio is unity. The statistics will be regarded as contiguous if the actual ratio found is significantly less than unity, by reference to the standard error. The theory is discussed from the viewpoints of both randomization and classical normal theory. With the randomization approach, the observations themselves are the "universe" and no assumption need be made as to the character of the frequency distribution. In the "normal case," the assumption is that the observations may be regarded as a random sample from a normal universe. In this case it seems certain that the ratio tends very rapidly to normality as the number of counties increases. The exact values of the first four semi-invariants are given for the normal case. These functions depend only on the configuration, and the calculated values for Ireland, with number of counties only 26, show that the distribution of the ratio is very close to normal. Accordingly, one can have confidence in deciding on significance from the standard error.
---
paper_title: Knowledge Discovery in Databases: An Attribute-Oriented Approach

paper_content:

Knowledge discovery in databases, or data mining, is an important issue in the development of data- and knowledge-base systems. An attribute-oriented induction method has been developed for knowledge discovery in databases. The method integrates a machine learning paradigm, especially learning-from-examples techniques, with set-oriented database operations and extracts generalized data from actual data in databases. An attribute-oriented concept tree ascension technique is applied in generalization, which substantially reduces the computational complex@ of database learning processes. Different kinas of knowledge rules, including characteristic rules, discrimination rules, quantitative rules, and data evolution regularities can be discovered efficiently using the attribute-oriented approach. In addition to learning in relational databases, the approach can be applied to knowledge discovery in nested relational and deductive databases. Learning can also be performed with databases containing noisy data and exceptional cases using database statistics. Furthermore, the rules discovered can be used to query database knowledge, answer cooperative queries and facilitate semantic query optimization. Based upon these principles, a prototyped database learning system, DBLEARN, has been constructed for experimentation.
---
paper_title: Discovery of General Knowledge in Large Spatial Databases

paper_content:

Extraction of interesting and general knowledge from large spatial databases is an important task in the development of spatial dataand knowledge-base systems. In this paper, we investigate knowledge discovery in spatial databases and develop a generalization-based knowledge discovery mechanism which integrates attribute-oriented induction on nonspatial data and spatial merge and generalization on spatial data. The study shows that knowledge discovery has wide applications in spatial databases, and relatively efficient algorithms can be developed for discovery of general knowledge in large spatial databases.
---
paper_title: Algorithms for Characterization and Trend Detection in Spatial Databases

paper_content:

The number and the size of spatial databases, e.g. for geo-marketing, traffic control or environmental studies, are rapidly growing which results in an increasing need for spatial data mining. In this paper, we present new algorithms for spatial characterization and spatial trend analysis. For spatial characterization it is important that class membership of a database object is not only determined by its non-spatial attributes but also by the attributes of objects in its neighborhood. In spatial trend analysis, patterns of change of some non-spatial attributes in the neighborhood of a database object are determined. We present several algorithms for these tasks. These algorithms were implemented within a general framework for spatial data mining providing a small set of database primitives on top of a commercial spatial database management system. A performance evaluation using a real geographic database demonstrates the effectiveness of the proposed algorithms. Furthermore, we show how the algorithms can be combined to discover even more interesting spatial knowledge.
---
paper_title: Spatial Data Mining: A Database Approach

paper_content:

Knowledge discovery in databases (KDD) is an important task in spatial databases since both, the number and the size of such databases are rapidly growing. This paper introduces a set of basic operations which should be supported by a spatial database system (SDBS) to express algorithms for KDD in SDBS. For this purpose, we introduce the concepts of neighborhood graphs and paths and a small set of operations for their manipulation. We argue that these operations are sufficient for KDD algorithms considering spatial neighborhood relations by presenting the implementation of four typical spatial KDD algorithms based on the proposed operations. Furthermore, the efficient support of operations on large neighborhood graphs and on large sets of neighborhood paths by the SDBS is discussed. Neighborhood indices are introduced to materialize selected neighborhood graphs in order to speed up the processing of the proposed operations.
---
paper_title: STING: A Statistical Information Grid Approach to Spatial Data Mining

paper_content:

Spatial data mining, i.e., discovery of interesting characteristics and patterns that may implicitly exist in spatial databases, is a challenging task due to the huge amounts of spatial data and to the new conceptual nature of the problems which must account for spatial distance. Clustering and region oriented queries are common problems in this domain. Several approaches have been presented in recent years, all of which require at least one scan of all individual objects (points). Consequently, the computational complexity is at least linearly proportional to the number of objects to answer each query. In this paper, we propose a hierarchical statistical information grid based approach for spatial data mining to reduce the cost further. The idea is to capture statistical information associated with spatial cells in such a manner that whole classes of queries and clustering problems can be answered without recourse to the individual objects. In theory, and confirmed by empirical studies, this approach outperforms the best previous method by at least an order of magnitude, especially when the data set is very large.
---
paper_title: Spatial Data Mining: A Database Approach

paper_content:

Knowledge discovery in databases (KDD) is an important task in spatial databases since both, the number and the size of such databases are rapidly growing. This paper introduces a set of basic operations which should be supported by a spatial database system (SDBS) to express algorithms for KDD in SDBS. For this purpose, we introduce the concepts of neighborhood graphs and paths and a small set of operations for their manipulation. We argue that these operations are sufficient for KDD algorithms considering spatial neighborhood relations by presenting the implementation of four typical spatial KDD algorithms based on the proposed operations. Furthermore, the efficient support of operations on large neighborhood graphs and on large sets of neighborhood paths by the SDBS is discussed. Neighborhood indices are introduced to materialize selected neighborhood graphs in order to speed up the processing of the proposed operations.
---
paper_title: Finding aggregate proximity relationships and commonalities in spatial data mining

paper_content:

Studies two spatial knowledge discovery problems involving proximity relationships between clusters and features. The first problem is: given a cluster of points, how can we efficiently find features (represented as polygons) that are closest to the majority of points in the cluster? We measure proximity in an aggregate sense due to the nonuniform distribution of points in a cluster (e.g. houses on a map), and the different shapes and sizes of features (e.g. natural or man-made geographic features). The second problem is: given n clusters of points, how can we extract the aggregate proximity commonalities (i.e. features) that apply to most, if not all, of the n clusters? Regarding the first problem, the main contribution of the paper is the development of Algorithm CRH (Circle, Rectangle and Hull), which uses geometric approximations (i.e. encompassing circles, isothetic rectangles and convex hulls) to filter and select features. The highly scalable and incremental Algorithm CRH can examine over 50,000 features and their spatial relationships with a given cluster in approximately one second of CPU time. Regarding the second problem, the key contribution is the development of Algorithm GenCom (Generalization for Commonality extraction) that makes use of concept generalization to effectively derive many meaningful commonalities that cannot be found otherwise.
---
paper_title: Density-Connected Sets and their Application for Trend Detection in Spatial Databases

paper_content:

Several clustering algorithms have been proposed for class identification in spatial databases such as earth observation databases. The effectivity of the well-known algorithms such as DBSCAN, however, is somewhat limited because they do not fully exploit the richness of the different types of data contained in a spatial database. In this paper, we introduce the concept of density-connected sets and present a significantly generalized version of DBSCAN. The major properties of this algorithm are as follows: (1) any symmetric predicate can be used to define the neighborhood of an object allowing a natural definition in the case of spatially extended objects such as polygons, and (2) the cardinality function for a set of neighboring objects may take into account the non-spatial attributes of the objects as a means of assigning application specific weights. Density-connected sets can be used as a basis to discover trends in a spatial database. We define trends in spatial databases and show how to apply the generalized DBSCAN algorithm for the task of discovering such knowledge. To demonstrate the practical impact of our approach, we performed experiments on a geographical information system on Bavaria which is representative for a broad class of spatial databases.
---
paper_title: A Comparison of Three Exploratory Methods for Cluster Detection in Spatial Point Patterns

paper_content:

This paper compares the performances of three explorato y methods for cluster detection in spatial point patterns where the at-risk population is known. After reviewing two existing methods, Openshaw et al. (1987) and Besag and Newell (1 991), an alternative method is introduced. These three methods are then compared empirically using two point patterns drawn from a disaggregate housing database consisting of 28,832 observations. Each observation in the data set contains attributes of single-family detached dwellings in the City of Amherst, New York. This paper provides some new insights into the performance of the three methods, as previous applications have used spatially aggregated (and hence rather inaccurate) data. The paper also demonstrates the utility of GZS for this type of spatial analysis.
---
paper_title: A Mark 1 Geographical Analysis Machine for the automated analysis of point data sets

paper_content:

Abstract This paper presents the first of a new generation of spatial analytical technology based on a fusion of statistical, GIS and computational thinking. It describes how to build what is termed a Geographical Analysis Machine (GAM), with high descriptive power. A GAM offers an imaginative new approach to the analysis of point pattern data based on a fully automated process whereby a point data set is explored for evidence of pattern without being unduly affected by predefined areal units or data error. No prior information or specification of particular location-specific hypotheses is required. If geographical data contain strong evidence of pattern in geographical space, then the GAM will find it. This technology is demonstrated by an analysis of data on cancer for northern England.
---
paper_title: Local Spatial Autocorrelation Statistics: Distributional Issues and an Application

paper_content:

The statistics Gi(d) and Gi*(d), introduced in Getis and Ord (1992) for the study of local pattern in spatial data, are extended and their properties further explored. In particular, nonbinary weights are allowed and the statistics are related to Moran's autocorrelation statistic, I. The correlations between nearby values of the statistics are derived and verified by simulation. A Bonferroni criterion is used to approximate significance levels when testing extreme values from the set of statistics. An example of the use of the statistics is given using spatial-temporal data on the AIDS epidemic centering on San Francisco. Results indicate that in recent years the disease is intensifying in the counties surrounding the city.
---
paper_title: A Progressive Refinement Approach To Spatial Data Mining

paper_content:

The goal of this thesis is to analyze methods for mining of spatial data, and to determine environments in which efficient spatial data mining methods can be implemented. In the spatial data mining process, we use (1) non-spatial properties of the spatial objects and (2) attributes, predicates and functions describing spatial relations between described objects and other features located in the spatial proximity of the described objects. The descriptions are generalized, transformed into predicates, and the discovered knowledge is presented using multiple levels of concepts. ::: We introduce the concept of spatial association rules and present efficient algorithms for mining spatial associations and for the classification of objects stored in geographic information databases. A spatial association rule describes the implication of one or a set of features (or predicates) by another set of features in spatial databases. A spatial classification process is a process that assigns a set of spatial objects into a number of given classes based on a set of spatial and non-spatial features (predicates). ::: The developed algorithms are based on the progressive refinement approach. This approach allows for efficient discovery of knowledge in large spatial databases. A complete set of spatial association rules can be discovered, and accurate decision trees can be constructed, using the progressive refinement approach. Theoretical analysis and experimental results demonstrate the efficiency of the algorithms. The completeness of the set of discovered spatial association rules is shown through the theoretical analysis and the experiments show that the proposed spatial classification algorithm allows for better accuracy of classification than the algorithm proposed in the previous work [37]. ::: The results of the research have been incorporated into the spatial data mining system prototype, GeoMiner. GeoMiner includes five spatial data mining modules: characterizer, comparator, associator, cluster analyzer, and classifier. The SAND (Spatial And Nonspatial Data) architecture has been applied in the modeling of spatial databases. The GeoMiner system includes the spatial data cube construction module, the spatial on-line analytical processing (OLAP) module, and spatial data mining modules. A spatial data mining language, GMQL (Geo-Mining Query Language), is designed and implemented as an extension to Spatial SQL, for spatial data mining. Moreover, an interactive, user-friendly data mining interface has been constructed and tools have been implemented for visualization of discovered spatial knowledge. (Abstract shortened by UMI.)
---
paper_title: Discovery of spatial association rules in geographic information databases

paper_content:

Spatial data mining, i.e., discovery of interesting, implicit knowledge in spatial databases, is an important task for understanding and use of spatial data- and knowledge-bases. In this paper, an efficient method for mining strong spatial association rules in geographic information databases is proposed and studied. A spatial association rule is a rule indicating certain association relationship among a set of spatial and possibly some nonspatial predicates. A strong rule indicates that the patterns in the rule have relatively frequent occurrences in the database and strong implication relationships. Several optimization techniques are explored, including a two-step spatial computation technique (approximate computation on large sets, and refined computations on small promising patterns), shared processing in the derivation of large predicates at multiple concept levels, etc. Our analysis shows that interesting association rules can be discovered efficiently in large spatial databases.
---
paper_title: Density-Based Clustering in Spatial Databases: The Algorithm GDBSCAN and Its Applications

paper_content:

The clustering algorithm DBSCAN relies on a density-based notion of clusters and is designed to discover clusters of arbitrary shape as well as to distinguish noise. In this paper, we generalize this algorithm in two important directions. The generalized algorithm—called GDBSCAN—can cluster point objects as well as spatially extended objects according to both, their spatial and their nonspatial attributes. In addition, four applications using 2D points (astronomy), 3D points (biology), 5D points (earth science) and 2D polygons (geography) are presented, demonstrating the applicability of GDBSCAN to real-world problems.
---

Title: A Survey on Spatial Data Mining Methods, Databases, and Statistics
Section 1: INTRODUCTION
Description 1: This section introduces the concept of spatial data mining, its applications, and the challenges associated with spatial data analysis.

Section 2: DEFINITION OF SPATIAL DATA MINING
Description 2: This section defines spatial data mining and discusses its unique aspects, such as spatial relationships and the temporal aspects of spatial data.

Section 3: SPATIAL DATA MINING TASKS
Description 3: This section categorizes and describes the primary tasks involved in spatial data mining, including summarization, classification, clustering, association rules, and trend analysis.

Section 4: COMPARISON OF SDM APPROACHES
Description 4: This section compares the various methods and approaches in spatial data mining, highlighting the differences and similarities between statistical and database approaches.

Section 5: CONCLUSION AND RESEARCH ISSUES
Description 5: This section summarizes the key findings and methodologies discussed in the paper and outlines potential research areas and challenges in spatial data mining.