Spatio-Temporal DBSCAN

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(data, eps_spatial, eps_temporal, min_pts, ...)

Arguments

data

matrix. A matrix containing, in that order, x, y and t. x (longitude) and y (latitude) are the spatial coordinates and t is the cumulative time since a common origin (e.g. c(0, 6, 10)). t must be sorted.

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.

...

Additional arguments are passed on to dbscan::frNN() and dbscan::dbscan().

Value

st_dbscan() returns an object of class stdbscan with the following components:

cluster

Integer vector with cluster assignments. Zero indicates noise points.

eps

Value of the eps_spatial parameter.

minPts

Value of the minPts parameter.

metric

Used distance metric.

borderPoints

Whether border points are considered as noise (FALSE) or not (TRUE).

eps_temporal

Value of the eps_temporal parameter.

This class is a simple extension of the dbscan class. For more details, see dbscan documentation.

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.

ST-DBSCAN is implemented using the following approach:

1. Find the spatial neighbors using Fixed Radius Nearest Neighbors (dbscan::frNN())

2. Filter the spatial neighbors by the temporal constraint

3. Apply DBSCAN on the filtered neighbors using dbscan::dbscan()

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)
)
data <- cbind(geolife_traj$x, geolife_traj$y, geolife_traj$t)

st_dbscan(
  data = data,
  eps_spatial = 3,
  eps_temporal = 30,
  min_pts = 3,
  # Extra arguments
  splitRule = "STD",
  search = "kdtree",
  approx = 1
)
#> ST-DBSCAN clustering for 468 objects.
#> Parameters: eps = 3, eps_temporal = 30, minPts = 3
#> Using euclidean distances and borderpoints = TRUE
#> The clustering contains 5 cluster(s) and 420 noise points.
#> 
#>   0   1   2   3   4   5 
#> 420   4   5  12  12  15 
#> 
#> Available fields: cluster, eps, minPts, metric, borderPoints,
#>                   eps_temporal