Spatial Data Mining
Spatial data mining discovers interesting, non-obvious patterns in data that has a location: maps, satellite images, GPS traces, sensor networks. The hard part is that spatial objects are related to each other by space, not just by their attribute values.
Learn these three things well: the spatial data cube with its three aggregation types, the four mining tasks (clustering, classification, association, trend), and the spatial association rule with a "near" predicate. These cover most exam questions.
1. What is Spatial Data?
Data that describes objects occupying space, with location, shape, topology and distance.
| Type | Example |
|---|---|
| Point | City location (lat, long), ATM, sensor |
| Line | Road, river, power line |
| Polygon / region | District boundary, lake, crop field |
| Raster / image | Satellite imagery, elevation grid |
Spatial objects carry implicit relationships that ordinary tables do not store:
| Relationship | Examples |
|---|---|
| Topological | intersects, contains, touches, crosses, overlaps |
| Distance-based | near, far, within 5 km |
| Directional | north of, left of |
| Hierarchical | city is inside district, district is inside state, state is inside country |
Classical algorithms assume records are independent. Nearby places are usually similar (spatial autocorrelation), so that independence assumption is broken.
2. Spatial Data Warehouse and Spatial OLAP
A spatial data warehouse stores spatial and non-spatial data together to build spatial data cubes and support spatial OLAP. Dimensions and measures can be spatial (region, area) or non-spatial (sales, population).
Spatial OLAP operations
- Roll-up along a spatial hierarchy (city to state).
- Drill-down to a finer level (state to street).
- Slice or dice with a spatial predicate (only the flood-prone region).
- Spatial join / aggregation: for example, total sales within 5 km of each outlet.
Three kinds of aggregation in a spatial cube
| Mapping | Meaning | Example |
|---|---|---|
| Spatial to non-spatial (S to N) | Aggregate spatial objects into numbers | Total sales per region |
| Non-spatial to spatial (N to S) | Derive spatial features from non-spatial values | Region shape from address records |
| Spatial to spatial (S to S) | Combine geometries | Total area per region, merged map regions |
Spatial joins are expensive, so only some cuboids are pre-computed (materialized). The rest are computed on demand from them.
3. Spatial Data Mining Tasks
| Task | Question it answers | Typical methods |
|---|---|---|
| Spatial clustering | Which objects form natural groups? | k-means, DBSCAN, CLARANS, CLIQUE, STING |
| Spatial classification / prediction | Where will a phenomenon occur? | Spatial decision trees, Bayesian classifiers, neural networks |
| Spatial association (co-location) rules | Which features appear near each other? | Spatial Apriori with "near" predicates |
| Trend and deviation analysis | How does a value change across space? | Spatial statistics, outlier detection |
| Spatial generalization | Summarise a region | AOI with spatial hierarchies |
Spatial association rule example (with a near predicate):
"Explain spatial association rules with an example." Always write the rule with its support and confidence, and mention the near / adjacent / inside predicates.
4. Methods in Detail
(a) Spatial generalization by dominant features
Label a region by the feature that dominates it:
(b) Spatial clustering
- CLARANS: randomized search for k medoids.
- DBSCAN: density-based, finds arbitrary shapes and noise.
- Clustering with obstacles: rivers and walls must not be crossed, so objects on opposite sides are not merged.
(c) Spatial classification and prediction
Use the object's own attributes plus neighbouring attributes and spatial predicates. Example: predict crop yield from soil type, rainfall and distance to a river.
(d) Mining raster databases
Regions are described by pixel patterns. Methods use spatial statistics, histogram and path analysis, and image aggregation.
(e) Spatial statistics
Moran's I and Geary's C measure spatial autocorrelation; variograms describe how similarity falls with distance. They help find spatial trends and spatial outliers.
5. Spatial Query Language and Indexing
- Extended SQL with predicates such as
INTERSECTS,CONTAINS,NEAR. - Spatial indexes make joins feasible: R-tree, R-tree, quad-tree, k-d tree, grid file*.
SELECT r.region_name, SUM(s.amount)
FROM sales_fact s, region_map r
WHERE INTERSECTS(s.location, r.geometry)
GROUP BY r.region_name;
6. Applications and Challenges
| Applications | Challenges |
|---|---|
| GIS and urban planning | Large, complex objects: costly storage and joins |
| Store-site selection, location-based services | Spatial autocorrelation breaks the independence assumption |
| Environmental and climate monitoring | Need spatial concept hierarchies for generalization |
| Flood, earthquake and landslide risk | Noisy or uncertain data (GPS errors, map scale) |
| Crop-yield prediction | Scalability of joins, index tuning and concurrency |
| Traffic and transport analysis, epidemiology | Mixed spatial and non-spatial data |
- Define spatial data mining; explain spatial relationships (5 marks).
- Spatial data cube with S to N, N to S, S to S aggregation and spatial OLAP operations (7-10 marks).
- Spatial clustering, classification and association with example rules (7-10 marks, very frequent).
- Dominant-feature generalization with its formula (5-7 marks).
- Applications and challenges (5 marks).
Frequently Asked Questions
QWhat is spatial data mining?
It is the discovery of interesting, implicit and previously unknown patterns from spatial databases, taking into account the location and spatial relationships (topological, distance, direction) between objects.
QWhat are the types of spatial data?
Points (a city), lines (a road), polygons or regions (a district) and raster or image data (a satellite picture).
QWhat is a spatial data cube?
A data cube whose dimensions or measures can be spatial (for example a region hierarchy or area) as well as non-spatial. It supports spatial OLAP: roll-up, drill-down, slice and spatial joins.
QExplain the three aggregation mappings in a spatial cube.
S to N aggregates spatial objects into numbers (total sales per region). N to S derives spatial features from non-spatial data. S to S combines geometries (merged regions, total area).
QGive an example of a spatial association rule.
with support 20% and confidence 80%. It says houses near a beach are expensive in 80% of such cases, and that this combination covers 20% of the data.
QHow is spatial clustering different from ordinary clustering?
Spatial clustering uses distance in space and must respect obstacles (rivers, walls), irregular shapes and noise. Algorithms such as DBSCAN and CLARANS are commonly used.
QWhat is spatial autocorrelation and how is it measured?
It is the tendency of nearby places to have similar values. It is measured with Moran's I or Geary's C.
QName some spatial index structures.
R-tree, R*-tree, quad-tree, k-d tree and grid file.
QList some challenges of spatial data mining.
Huge and complex data, costly spatial joins, dependence between neighbouring objects, uncertain or noisy spatial data and the need for spatial concept hierarchies.