3

I am relatively new to clustering methods and am trying to determine the best method for clustering (or merely grouping) events that fall within a space-time window using preferably R. My goal is to group events with a unique cluster ID if events fall within a distance window of some unit measure and within a number of days.

For example, if each point represents an earthquake or a flood event, a cluster of each event will be considered the same event and will be given the same unique cluster ID if they happened within a set distance and time.

Over the last few days I've come across a number of different clustering methods, but many work on clustering events in space but not in time (i.e. not three dimensional). So naturally, I developed my own steps for clustering events in space and time based on set distances:

  1. Agglomerative Hierarchical Clustering with Space (Ward's)...then...
  2. Agglomerative Hierarchical Clustering on First Clusters with Time (Ward's)

The rationale, cluster events by a set distance, then cluster within those clusters on a set number of days. The code below is what I used for this process clustering events based off of a distance = 15 units and days = 7. The code works and each cluster has events that follow the parameters (distance 15 units, days 7). But I realized a few things:

  1. The number of clusters differ between when I cluster events by space first then time, vs time first then space.
  2. While I get events that fit my definition, I do not have a measure of events that I missed. I.e. I'm not measuring data I missed.

My question: What are the best testable methods for clustering events in a space-time window, so I don't have to chose which dimension clusters first and I can evaluate my success? I.e. Can I cluster on a multidimensional distance such as space-time at the same time?

(Note: I'm relatively new to R so I apologize if it's lengthy):

# Load packages
library(ggplot2)
library(plyr)

# Create data
numOfPoints <- 1000
numOfClustersToCreate <- 4

# Set space-time window parameters
spaceWindow <- 15
timeWindow <- 7

# Set seed for reproducibility
set.seed(22)

# Create spatial coordinates for four distinct clusters
x1 <- rpois((numOfPoints / numOfClustersToCreate), 150)
y1 <- rpois((numOfPoints / numOfClustersToCreate), 100)

x2 <- rpois((numOfPoints / numOfClustersToCreate), 20)
y2 <- rpois((numOfPoints / numOfClustersToCreate), 100)

x3 <- rpois((numOfPoints / numOfClustersToCreate), 100)
y3 <- rpois((numOfPoints / numOfClustersToCreate), 20)

x4 <- rpois((numOfPoints / numOfClustersToCreate), 5)
y4 <- rpois((numOfPoints / numOfClustersToCreate), 5)

# Create a temporal dimension representing days
days <- sample(1:365, numOfPoints, replace = TRUE)

# Create a dataframe with a unique event ID, spatial coordinates and days
testData <- data.frame(UnqID = 1:numOfPoints, LON = c(x1,x2,x3,x4),
                       LAT = c(y1,y2,y3,y4), DAYS = days)

The test data looks like: enter image description here

# Clustering method

# Calculate the distance between each point
distMatrix <- dist(testData[,2:3], method = "euclidean")

# Cluster events and then cut tree into chunks representing the space window
hcDist <- hclust(distMatrix, method = "ward.D2")
distHClust <- cutree(hcDist, h = spaceWindow)

# Store the first cluster into a cluster column
testData$Cluster1 <- distHClust

qplot(LON, LAT, data = testData, color = factor(Cluster1)) + guides(color = FALSE)

enter image description here

# Initialize a column for the second cluster
testData$Cluster2 <- rep(NA, numOfPoints)

# Store unique spatial clusters
uniqueSClusters <- unique(testData$Cluster1)

# For each cluster, cluster events based on the temporal dimension
for(i in seq_along(uniqueSClusters)){

  # Subset data
  subData <- testData[which(testData$Cluster1 == uniqueSClusters[i]),]

  # If the data does not have two events, store NA in the 2nd cluster column
  if(nrow(subData) < 2){

    testData[which(testData$Cluster1 == uniqueSClusters[i]), ]$Cluster2 <- NA
  } else {

    # Calculate a day distance matrix between each point
    dayDist <- dist(subData$DAYS)

    # Cluster events and cut by the time window
    hc <- hclust(dayDist, method = "ward.D2")
    dayHClust <- cutree(hc, h = timeWindow)

    # Store the clusterIDs in the 2nd cluster column
    testData[which(testData$Cluster1 == uniqueSClusters[i]),]$Cluster2 <- dayHClust

  }
}

# Paste together a unique character string to use as a temporary uniq ID
testData$ClusterFlag <- paste0("HC",testData$Cluster1, "SP",testData$Cluster2)

# Summarize each cluster by the number of events within each cluster
testDD <- ddply(testData, ~ClusterFlag, summarize, 
                N = length(UnqID))

# Determine the final unique IDs that have more than one event,
# and thus are actual clusters
finalClusters <- testDD[which(testDD$N > 1),]$ClusterFlag

# Initialize a final column clusterID
testData$ClusterFlagID <- rep(NA, numOfPoints)

clusterID <- 0

# Assign each column a unique ID
for(i in seq_along(finalClusters)){

  clusterID <- clusterID + 1

  clusterOI <- finalClusters[i]

  clusterIX <- testData$ClusterFlag %in% clusterOI

  testData[clusterIX,]$ClusterFlagID <- clusterID

}

qplot(LON, LAT, data = testData, color = factor(ClusterFlagID))  + guides(color=FALSE)

enter image description here

EDIT:

Date: 2017 August 7

For those concerned, though I am no expert, I found a few solutions.

  1. Space-time permutation model.

This method uses a cylindrical scanning statistic of a certain maximum shape to scan for clusters of events. This method was first developed for determining prospective disease outbreak clusters and can be utilized using the SatScan coupled with the rsatscan package for use in R. One of the downsides for using this method, for my use anyway, is that it's not technically grouping events but rather testing if the proportion of events is higher than what would otherwise be the case without a space-time interaction.

  1. ST-DBSCAN

I have yet to examine this method fully. This is a space-time extension of a DBSCAN allowing for two distances to be set as arguments. I do see that there is python code developed by the authors, of which I might have to learn how to call from R in windows.

Either way, these are two options I came across though I still do not have a definitive answer as the appropriate solution. To be honest, I'm currently leaning towards my hierarchical method described in the beginning because of time issues.

  • Please choose only one software package. If you want an answer for R, remove all references to ArcGIS. As stated in the Tour, you should ask only one question per Question. – Vince Jul 28 '17 at 19:52
  • I am facing a similar issue. I want to cluster(or merely group) the points together with that occur at a spatial window of say 10m and within a time window of 30 sec. I have a large sample space and every sample has been classified as either N03 or N04 timestamp equip_ident shift_date shift_ident 1 2018-04-29 23:54:40 O2K025 2018-04-29 00:00:00.000 3 2 2018-04-29 23:54:33 O2K025 2018-04-29 00:00:00.000 3 3 2018-04-29 23:54:28 O2K025 2018-04-29 00:00:00.000 3 4 2018-04-29 23:54:22 O2K025 2018-04-29 00:00:00.000 3 5 2018-04-29 23:54:16 O2K025 2018-04-29 00:00:00.000 3 6 2018-04-29 23:54:10 O2K02 – Sunny Soarabh Jul 2 '18 at 9:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.