Skip to contents

Spatio-Temporal DBSCAN

Source: R/stdbscan.R
st_dbscan.Rd

Perform ST-DBSCAN clustering on points with spatial and temporal coordinates. This algorithm identifies clusters of points that are close both in space and time.

Usage

st_dbscan(x, y, t, eps_spatial, eps_temporal, min_pts)

Arguments

x

Numeric vector of x-coordinates (spatial).

y

Numeric vector of y-coordinates (spatial).

t

Numeric vector of time values. t is expected to represent elapsed time since a common origin (e.g. c(0, 6, 10)).

eps_spatial

Numeric. The spatial radius threshold. Points closer than this in space may belong to the same cluster.

eps_temporal

Numeric. The temporal threshold. Points closer than this in time may belong to the same cluster.

min_pts

Integer. Minimum number of points required to form a core point (standard DBSCAN parameter).

Value

An integer vector of length length(x) with cluster assignments:

  • -1: noise point

  • >=1: cluster ID

Details

ST-DBSCAN extends classical DBSCAN by incorporating a temporal constraint. Two points are considered neighbors if they are within eps_spatial in space and within eps_temporal in time. Clusters are expanded from core points recursively following the DBSCAN algorithm.

This function is implemented in C++ via Rcpp for performance.

References

Birant, D., & Kut, A. (2007). ST-DBSCAN: An algorithm for clustering spatial–temporal data. Data & Knowledge Engineering, 60(1), 208–221. https://doi.org/10.1016/j.datak.2006.01.013

Examples

data(geolife_traj)

geolife_traj$date_time <- as.POSIXct(
  paste(geolife_traj$date, geolife_traj$time),
  format = "%Y-%m-%d %H:%M:%S",
  tz = "GMT"
)

geolife_traj$t <- as.numeric(
  geolife_traj$date_time - min(geolife_traj$date_time)
)

st_dbscan(
  x = geolife_traj$x,
  y = geolife_traj$y,
  t = geolife_traj$t,
  eps_spatial = 3, # meters
  eps_temporal = 30, # seconds
  min_pts = 3
)
#>   [1]  1  1  1  1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
#>  [26] -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
#>  [51] -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
#>  [76] -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
#> [101] -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
#> [126] -1 -1 -1 -1 -1 -1  2  2  2  2  2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
#> [151] -1 -1 -1 -1 -1 -1 -1 -1 -1  3  3  3  3  3  3  3  3  3  3  3  3 -1 -1 -1 -1
#> [176] -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
#> [201] -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
#> [226] -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
#> [251] -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
#> [276] -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1  4  4  4  4  4  4  4  4  4
#> [301]  4  4  4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
#> [326] -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
#> [351] -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
#> [376] -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
#> [401] -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
#> [426] -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1  5  5  5  5  5  5  5
#> [451]  5  5  5  5  5  5  5  5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1