DBSCAN vs Streaming Clustering · Batch Density Clustering Against Online Methods

DBSCAN’s contract is transductive

The scikit-learn user guide draws a hard distinction between transductive and inductive clustering: transductive methods “are not designed to be applied to new, unseen data.” DBSCAN is listed as transductive, with use cases including non-flat geometry, uneven cluster sizes, and outlier removal. Its geometry is described as “distances between nearest points.”¹

For a fitted DBSCAN model, the clustering result describes the dataset supplied to that fit. It is not a reusable assignment function for future observations. The documented operations are fit and fit_predict:

from sklearn.cluster import DBSCAN

def fit_batch(X, eps):
    return DBSCAN(eps=eps).fit_predict(X)

A new call with a new X is another batch fit, not a documented update to the previous result.

The neighborhood controlled by eps can be written as:

N_eps(p) = { q : dist(p, q) <= eps }

The same eps applies across the supplied dataset. The scikit-learn guide calls its selection “crucial” for the dataset and distance function. If eps is too small, most data remains unclustered and is labeled -1 for noise. If it is too large, nearby clusters can merge, potentially returning the entire dataset as one cluster.² Neither case defines a mechanism for adapting the fitted partition as new observations arrive.

DBSCAN has no incremental estimator contract

The absence of an incremental API is explicit. A local API-shape check on scikit-learn 1.9.1 found no partial_fit method on DBSCAN; the checked public fitting methods were fit and fit_predict.⁴

The implementation structure reinforces that contract. The API reference states that scikit-learn “bulk-computes all neighborhood queries.”³ The neighborhood relation is therefore computed for the observations in a batch rather than maintained through a documented point-update operation. Adding another observation can add candidates to existing eps neighborhoods, but DBSCAN exposes no API that incorporates those candidates into prior neighborhood state, core status, or labels.

These are separate issues:

• Estimator contract: there is no partial_fit operation that accepts new observations and updates an existing DBSCAN model.
• Computation model: the current implementation performs all neighborhood queries in bulk.
• Parameter contract: eps is selected for the dataset and distance function; it is not recalibrated or merged by an incoming batch.

Reducing the current implementation’s memory use would not, by itself, add an incremental contract. Likewise, implementing a neighborhood calculation with less memory would still leave the fitted-versus-streaming boundary unresolved unless the API also defined how prior state changes.

Memory: the neighborhood graph and the batch boundary

For this implementation, the API reference gives memory complexity as O(n.d), where d is the average number of neighbors. The dot denotes multiplication in this notation; d is not the data dimensionality.³ The documented worst case is O(n^2), which can occur when eps is large and min_samples is low. By comparison, the original DBSCAN used linear memory, O(n). The reference also warns that nearest-neighborhood queries can attract higher memory depending on the selected algorithm.

The API documents several ways to reduce this cost without changing DBSCAN into an online estimator:

• Precompute sparse radius neighborhoods in chunks with NearestNeighbors.radius_neighbors_graph, then pass the assembled graph to DBSCAN with metric="precomputed".
• Remove near-duplicate points and represent their counts with sample_weight.
• Use OPTICS when its variable-radius behavior and lower memory usage are appropriate.

The precomputed graph path still has a batch boundary:

from sklearn.cluster import DBSCAN

def fit_precomputed_neighborhoods(neighborhoods, eps):
    model = DBSCAN(
        eps=eps,
        metric="precomputed",
    )
    return model.fit_predict(neighborhoods)

Chunking changes how the radius queries are computed and stored. It does not define an update operation for the assembled graph: DBSCAN still receives one neighborhood representation for the dataset being clustered.

OPTICS is explicitly documented as better suited than scikit-learn’s current DBSCAN implementation to large datasets. It finds core samples while retaining hierarchy for a variable neighborhood radius. Its scikit-learn implementation nevertheless performs nearest-neighborhood searches on all points before constructing the reachability order. It also omits the heap used for expansion candidates, giving the documented implementation O(n^2) time complexity.⁵

That makes OPTICS a large-data and varying-density alternative, not a streaming solution. The cited implementation still begins with all points. Sparse graph chunking, duplicate compression, and OPTICS can change the batch algorithm’s storage or density model; none makes the fitted estimator absorb observations incrementally.

BIRCH replaces points with an incremental CF-tree

BIRCH takes a different structural approach. The scikit-learn API describes it as a memory-efficient, online-learning algorithm and an alternative to MiniBatchKMeans. Instead of retaining the full input dataset, it builds a Clustering Feature Tree, or CF-tree. The data is lossily compressed into Clustering Feature nodes, which contain CF subclusters; non-terminal nodes can have child nodes.⁶

Each CF subcluster maintains summary statistics rather than every raw observation:

• the number of samples;
• a linear sum, represented as an n-dimensional vector;
• a squared sum of the squared L2 norms;
• centroids, cached to avoid recalculation;
• the squared norm of each centroid.

When a point enters the tree, BIRCH finds the closest subcluster, updates its linear sum, squared sum, and sample count, and repeats the update down the tree until the relevant leaf is updated.⁷ The tree is the persistent state used by later updates; it is not a collection of independently fitted DBSCAN neighborhoods.

Two parameters control this structure:

Parameter	Default	Documented behavior
threshold	0.5	A new sample is merged with its closest subcluster only when the resulting subcluster radius is less than threshold; otherwise, a new subcluster is started. A very low value promotes splitting.
branching_factor	50	Limits each node to at most this number of CF subclusters. If an insertion exceeds the limit, the node splits into two nodes and its subclusters are redistributed.

A minimal incremental update is:

from sklearn.cluster import Birch

birch = Birch(
    threshold=0.5,
    branching_factor=50,
)

birch.partial_fit(X_batch)
labels = birch.labels_

The label scope has a strict caveat. The API documents that when partial_fit is used, labels_ contains labels for the last batch only.⁷ It is not a cumulative label history for all observations processed by the tree. With fit, the labels cover that fit’s input data; with repeated partial_fit calls, the documented label scope changes to the most recent batch.

This also means BIRCH should not inherit DBSCAN’s noise semantics by assumption. DBSCAN’s guide assigns -1 when points fail to cluster under its eps setting. The cited BIRCH contract does not define a like-for-like -1 noise label, and neither scikit-learn estimator documents a contract that inserts one point and returns a permanently stable label. BIRCH’s incremental guarantee is bounded to its documented update and summary state.

MiniBatchKMeans is online but center-based

MiniBatchKMeans provides the other online option. It updates a model consisting of centers through mini-batches rather than exposing DBSCAN’s eps neighborhoods. Its batch_size parameter controls the size of those mini-batches, while reassignment_ratio governs how readily centers with low counts can be reassigned.⁸

The default reassignment_ratio is 0.01. A higher value makes low-count centers more likely to be reassigned; the API documents that this can lengthen convergence while improving the resulting clustering. If the value is too high, convergence problems can occur, especially with a small batch.

The geometric tradeoff is more important than the update API. DBSCAN is documented in terms of nearest-point distances, local eps neighborhoods, and non-flat cluster structure. MiniBatchKMeans represents its partition with centers and refines those centers through updates. It therefore substitutes a center-based geometry for density-connected neighborhoods rather than preserving DBSCAN’s cluster semantics.

That is the cost to evaluate when selecting an online method: ingestion becomes incremental, but the representation used to define clusters is different. BIRCH controls a CF-tree with threshold and branching_factor; MiniBatchKMeans controls center assignments through mini-batches and center reassignment. Neither choice is justified solely by the presence of partial_fit, and neither should be treated as a memory-only modification of DBSCAN.

Frequently asked questions

What did the local BIRCH run retain after repeated partial fits? On scikit-learn 1.9.1, the run used Birch(n_clusters=2) and fed it five successive 100-sample make_moons batches with noise=0.05, scaling each batch independently. After 500 points, subcluster_centers_.shape was (9, 2) and the root object was _CFNode. The observed state is consistent with parameter-controlled subclusters rather than retained per-point records. These are locally reproduced values, not figures quoted from the documentation.

How can BIRCH expose CF leaves without a final global clustering step? Set n_clusters=None. In that mode, scikit-learn skips the final clustering step and returns the leaf subclusters as they are.⁷

What initialization tradeoff does MiniBatchKMeans expose through init_size? With init_size=None, the documented heuristic uses 3 * batch_size if 3 * batch_size < n_clusters; otherwise, it uses 3 * n_clusters. Initialization runs batch KMeans on a random subset, which can speed initialization at the expense of accuracy. The initialization subset needs to be larger than n_clusters.⁸

When can MiniBatchKMeans use parallel computation? Its batch_size defaults to 1024. The API states that a value above 256 * number_of_cores can be used to enable parallelism on all cores for faster computation.⁸