Clustering spatial data in R?

Question

I have bunch of data points with latitude and longitude. I want to use R to cluster them based on their distance.

I have already taken a look at this page and tried clustTool package. But I am not sure if clust function in clustTool considers data points (lat,lon) as spatial data and uses the appropriate formula to calculate distance between them.

I mean I cannot see how they differentiate between spatial data and ordinal data. I believe the distance calculation between two points on map (spatial) and two normal numbers is different. (Is it not?)

Also what happens if I want to consider a third parameter in my clustering?

Like say if I have (lat,lon) and one other parameter.

How is the distance calculated?

The other problem I have with clustTool is that it is designed with a GUI in mind. I don't know how I can skip the GUI overhead in the library because I don't need it.

What options do I have in R for cluster analysis of spatial data?

Answer 1

Here is a solution based on Find clusters of points based distance rule, but using the distm function from the geosphere package:

library(sp)
library(rgdal)
library(geosphere)

# example data from the thread
x <- c(-1.482156, -1.482318, -1.482129, -1.482880, -1.485735, -1.485770, -1.485913, -1.484275, -1.485866)
y <- c(54.90083, 54.90078, 54.90077, 54.90011, 54.89936, 54.89935, 54.89935, 54.89879, 54.89902)

# convert data to a SpatialPointsDataFrame object
xy <- SpatialPointsDataFrame(
      matrix(c(x,y), ncol=2), data.frame(ID=seq(1:length(x))),
      proj4string=CRS("+proj=longlat +ellps=WGS84 +datum=WGS84"))

# use the distm function to generate a geodesic distance matrix in meters
mdist <- distm(xy)

# cluster all points using a hierarchical clustering approach
hc <- hclust(as.dist(mdist), method="complete")

# define the distance threshold, in this case 40 m
d=40

# define clusters based on a tree "height" cutoff "d" and add them to the SpDataFrame
xy$clust <- cutree(hc, h=d)

You should get something like:

        coordinates ID clust
1 (-1.482156, 54.90083)  1     1
2 (-1.482318, 54.90078)  2     1
3 (-1.482129, 54.90077)  3     1
4  (-1.48288, 54.90011)  4     2
5 (-1.485735, 54.89936)  5     3
6  (-1.48577, 54.89935)  6     3
7 (-1.485913, 54.89935)  7     3
8 (-1.484275, 54.89879)  8     4
9 (-1.485866, 54.89902)  9     3

These next steps are just for visualization:

library(dismo)
library(rgeos)

# expand the extent of plotting frame
xy@bbox[] <- as.matrix(extend(extent(xy),0.001))

# get the centroid coords for each cluster
cent <- matrix(ncol=2, nrow=max(xy$clust))
for (i in 1:max(xy$clust))
    # gCentroid from the rgeos package
    cent[i,] <- gCentroid(subset(xy, clust == i))@coords

# compute circles around the centroid coords using a 40m radius
# from the dismo package
ci <- circles(cent, d=d, lonlat=T)

# plot
plot(ci@polygons, axes=T)
plot(xy, col=rainbow(4)[factor(xy$clust)], add=T)

Answer 2

There are functions for computing true distances on a spherical earth in R, so maybe you can use those and call the clustering functions with a distance matrix instead of coordinates. I can never remember the names or relevant packages though. See the R-spatial Task View for clues.

The other option is to transform your points to a reference system so that the distances are Euclidean. In the UK I can use the OSGrid reference system:

 data = spTransform(data,CRS("+epsg:27700"))

using spTransform from package 'rgdal' (or maybe maptools). Find a grid system for your data (the relevant UTM zone will probably do) and you'll be computing distances in metres no problem.

This is only good if your data is a small-ish area - if you have global data then you really do need to compute the spherical distance, and that's somewhere in one (or more) of the packages discussed in the R Spatial Task View:

http://cran.r-project.org/web/views/Spatial.html

Looks like you want package "geosphere", but do read the spatial task view!

Answer 3

I'd take a look at the Spatstat package. The entire package is dedicated to analysing spatial point patterns (sic). There's an excellent ebook written by Prof. Adrian Baddeley at the CSIRO which contains detailed documentation, how-to's and examples for the entire package. Take a look at chapter 19 for "Distance methods for point patterns".

That said, I'm not sure that even spatstat differentiates between spatial and ordinal data, so you might want to reproject your points into something with consistent x and y values - possibly try using rgdal (a R library for GDAL and OGR).

Answer 4

Maybe this answer comes 2 years too late, but anyway.

To my knowledge, spatial clustering requires a defined neighborhood to which the clustering is constrained, at least at the beginning. The kulldorf function in the SpatialEpi package allows for spatial clustering based on aggregated neighborhoods.

further the DBSCAN statistic available from the fpc package could be useful.

see also here for a similar discussion: https://stats.stackexchange.com/questions/9739/clustering-spatial-data-in-r

and here for an interesting paper about recent cluster algorithms, such as CHAMAELEON: http://www.cs.uiuc.edu/homes/hanj/pdf/gkdbk01.pdf

Answer 5

While not an R package, geoda might be an interesting program to examine as it is written by Luc Anselin who has contributed to spatial clustering theory, and I believe it enables some clustering (though it has been some time since I have explored it).

spdep is a great R package. It includes the skater function for spatial ’K’luster Analysis by Tree Edge Removal. It also brings other functions for spatial analysis, including spatial auto-correlation and detection of local cluster using Local Moran and other spatial statistics. It is described as follows:

A collection of functions to create spatial weights matrix objects from polygon contiguities, from point patterns by distance and tesselations, for summarising these objects, and for permitting their use in spatial data analysis, including regional aggregation by minimum spanning tree; a collection of tests for spatial autocorrelation, including global Moran's I, APLE, Geary's C, Hubert/Mantel general cross product statistic, Empirical Bayes estimates and Assunção/Reis Index, Getis/Ord G and multicoloured join count statistics, local Moran's I and Getis/Ord G, saddlepoint approximations and exact tests for global and local Moran's I; and functions for estimating spatial simultaneous autoregressive (SAR) lag and error models, impact measures for lag models, weighted and unweighted SAR and CAR spatial regression models, semi-parametric and Moran eigenvector spatial filtering, GM SAR error models, and generalized spatial two stage least squares models.

You can at least test if your points are randomly distributed spatially (presumably a useful test pre-clustering when considering spatial distances), but it can also generate other useful measures that you could input to your clustering algorithm. Finally, perhaps you might find useful questions on https://stats.stackexchange.com/ dealing with spatial clustering issues (though, more from a theoretical perspective).

Answer 6

Try leaderCluster packacge in R. Unlike many other clustering algorithms it does not require the user to specify the number of clusters, but instead requires the approximate radius of a cluster as its primary tuning parameter.

Answer 7

Check geosphere package distance function or fossil deg.dist function. You have data in degrees and need to translate it into meters or feet before doing clustering.