HDBSCAN for Variable-Density Fleet Stops

DBSCAN for fleet stop clustering works well when stop density is roughly uniform across the dataset, but mixed fleets rarely cooperate. A single delivery network can have tight curbside drop points 15-20 meters apart in a dense urban core alongside sprawling distribution-center yards where a truck’s GPS trace wanders 100-200 meters across a loading apron while still representing one operational visit. A single eps value cannot satisfy both: tune it tight enough to separate adjacent urban stops and the depot yard fragments into a dozen spurious micro-clusters; tune it loose enough to hold the depot together and adjacent city-block stops silently merge.

HDBSCAN (Hierarchical DBSCAN) removes the single-eps constraint by building a hierarchy of clusters across a range of density thresholds and then selecting the most stable clusters from that hierarchy automatically. This page gives a self-contained Python class built on the hdbscan library with a haversine metric, extracting both hard cluster labels and the soft membership probabilities and cluster persistence scores that DBSCAN does not provide.

Compatibility and Configuration

The Clusterer

from __future__ import annotations

from dataclasses import dataclass

import numpy as np
import pandas as pd
import hdbscan


EARTH_RADIUS_M = 6_371_000


@dataclass
class HDBSCANStopClusterer:
    """
    Cluster fleet stop candidates of varying spatial density using
    HDBSCAN with a haversine metric.

    Parameters
    ----------
    min_cluster_size : int
        The smallest grouping of points HDBSCAN will consider a
        genuine cluster rather than noise. This is the primary density
        knob — unlike DBSCAN's eps, it does not encode a fixed
        distance, so it transfers reasonably well across regions of
        different density. Default 5; raise to 8-10 for high-frequency
        sampling (1 ping/5-10 s) where a real stop naturally
        accumulates many points, lower to 3 for sparse 60 s+ sampling.
    min_samples : int | None
        Controls how conservative the clustering is about calling a
        point noise. Defaults to min_cluster_size when None, which is
        the library default and a reasonable starting point. Raise
        above min_cluster_size to be more conservative (more points
        classified as noise); this smooths out sparse bridging points
        between two otherwise-distinct stop regions.
    cluster_selection_epsilon : float
        A radian distance floor merged into the hierarchy after
        fitting: clusters closer together than this value are merged
        even if HDBSCAN's stability-based selection would otherwise
        keep them separate. Use this to prevent over-fragmentation of
        naturally sparse depot yards without affecting dense urban
        regions. Default 0.0 (disabled); a typical non-zero value is
        metres_to_radians(30) for merging micro-fragments up to 30 m
        apart.
    cluster_selection_method : str
        'eom' (excess of mass, the default) favours fewer, larger,
        more stable clusters and is the safer choice for operational
        stop detection. 'leaf' produces more, smaller, finer-grained
        clusters — useful for exploratory analysis of a new region's
        stop structure but prone to over-segmenting a single depot
        into loading-bay-level sub-clusters in production use.
    """

    min_cluster_size: int = 5
    min_samples: int | None = None
    cluster_selection_epsilon: float = 0.0
    cluster_selection_method: str = "eom"

    @staticmethod
    def metres_to_radians(metres: float) -> float:
        """Convert a metric distance to the radian units HDBSCAN expects."""
        return metres / EARTH_RADIUS_M

    def _build_clusterer(self) -> hdbscan.HDBSCAN:
        return hdbscan.HDBSCAN(
            min_cluster_size=self.min_cluster_size,
            min_samples=self.min_samples,
            metric="haversine",
            cluster_selection_epsilon=self.cluster_selection_epsilon,
            cluster_selection_method=self.cluster_selection_method,
        )

    def fit(
        self,
        df: pd.DataFrame,
        lat_col: str = "latitude",
        lon_col: str = "longitude",
    ) -> pd.DataFrame:
        """
        Fit HDBSCAN over a candidate-stop point DataFrame and return it
        with cluster_id, cluster_probability, and cluster_persistence
        columns attached.

        Parameters
        ----------
        df : pd.DataFrame
            Must contain lat_col and lon_col in decimal degrees
            (WGS84). Should already be pre-filtered to stationary
            candidate points — HDBSCAN clusters spatial density, not
            temporal or velocity signals.

        Returns
        -------
        pd.DataFrame with three new columns:
            cluster_id          : int, -1 for noise
            cluster_probability : float in [0, 1], soft membership
                                   strength within the assigned cluster
            cluster_persistence : float, stability of the assigned
                                   cluster across the density hierarchy
                                   (NaN for noise points)
        """
        coords_rad = np.radians(df[[lat_col, lon_col]].to_numpy())

        clusterer = self._build_clusterer()
        labels = clusterer.fit_predict(coords_rad)

        out = df.copy()
        out["cluster_id"] = labels
        out["cluster_probability"] = clusterer.probabilities_

        persistence_by_cluster = {
            cid: float(p)
            for cid, p in enumerate(clusterer.cluster_persistence_)
        }
        out["cluster_persistence"] = out["cluster_id"].map(
            lambda cid: persistence_by_cluster.get(cid, float("nan"))
        )

        return out

    def summarize_stops(
        self,
        clustered: pd.DataFrame,
        vehicle_id_col: str = "vehicle_id",
        timestamp_col: str = "timestamp_utc",
        lat_col: str = "latitude",
        lon_col: str = "longitude",
        min_probability: float = 0.6,
    ) -> pd.DataFrame:
        """
        Aggregate clustered points into one row per discovered stop.

        min_probability filters out low-confidence cluster members
        before computing the centroid, which keeps borderline points
        (soft cluster edges) from pulling the centroid away from the
        true dense core.
        """
        confident = clustered[
            (clustered["cluster_id"] != -1)
            & (clustered["cluster_probability"] >= min_probability)
        ]

        stops = (
            confident
            .groupby([vehicle_id_col, "cluster_id"])
            .agg(
                centroid_lat=(lat_col, "median"),
                centroid_lon=(lon_col, "median"),
                arrival_time=(timestamp_col, "min"),
                departure_time=(timestamp_col, "max"),
                point_count=(lat_col, "count"),
                mean_persistence=("cluster_persistence", "mean"),
            )
            .reset_index()
        )
        stops["dwell_seconds"] = (
            stops["departure_time"] - stops["arrival_time"]
        ).dt.total_seconds()
        return stops

Usage:

clusterer = HDBSCANStopClusterer(
    min_cluster_size=5,
    min_samples=5,
    cluster_selection_epsilon=HDBSCANStopClusterer.metres_to_radians(30),
    cluster_selection_method="eom",
)

clustered = clusterer.fit(candidate_points, lat_col="latitude", lon_col="longitude")
stops = clusterer.summarize_stops(clustered, min_probability=0.6)
print(stops.sort_values("mean_persistence", ascending=False).head())

Expected output shape: fit() returns the input DataFrame with cluster_id, cluster_probability, and cluster_persistence appended, one row per input point. summarize_stops() collapses that to one row per (vehicle_id, cluster_id) pair with centroid, arrival/departure, point count, and mean persistence.

Execution and Tuning Guidelines

• min_cluster_size — the primary density-independence knob. Because HDBSCAN evaluates stability across a range of thresholds rather than committing to one fixed radius, this parameter transfers across urban and depot-yard regions in the same fit far better than DBSCAN’s eps does. Start at 5 and inspect the resulting noise fraction; raise it if traffic-signal-length halts are surviving as spurious tiny clusters, lower it if genuine low-traffic rural stops are being discarded as noise.
• min_samples — leave at the library default (equal to min_cluster_size) initially. Raising it independently makes the algorithm more conservative about calling anything a dense core, which is the right move if bridging points between two adjacent but distinct depot zones are causing them to merge.
• cluster_selection_epsilon — the targeted fix for over-fragmented sparse regions. A depot yard where GPS scatter naturally spans 40-80 meters can still split into two or three micro-clusters under eom selection; setting this to metres_to_radians(30) or similar merges anything closer than that floor without touching already-well-formed dense urban clusters, which sit far below the epsilon distance already.
• cluster_selection_method — 'eom' is the production default; only switch to 'leaf' for one-off exploratory analysis of a new operational region where you want to see the full fine-grained cluster structure before deciding on downstream aggregation rules.

Use cluster_persistence_ as a quality gate before auto-promoting a discovered grouping into a named location: a low-persistence grouping (roughly below 0.1-0.15 in typical fleet data) is a candidate for manual review rather than automatic promotion, since it only barely qualified as a dense region across the density hierarchy.

Common Pitfalls

Up: DBSCAN for Fleet Stop Clustering | Stop Detection & Dwell Time Analytics

Related

• DBSCAN for Fleet Stop Clustering — the fixed-eps foundation this page extends for mixed-density fleets
• Tuning DBSCAN eps and min_samples for Delivery Truck Stops — k-distance elbow methodology for single-density regions where DBSCAN alone is sufficient
• Kalman Filtering for GPS Noise Reduction — upstream smoothing that tightens spatial dispersion before either clustering method runs
• Sliding-Window Variance Stop Detection — a temporal alternative for isolating candidate stationary points before spatial clustering