Efficient clustering (unknown number of clusters; optionally online) by greedily picking exemplars

Describe the workflow you want to enable

Cluster a dataset (many samples) where distances are small within clusters and large between clusters. Memory requirements and runtime should be low.

Describe your proposed solution

If a sample's distance to all exemplars (that were defined so far) is above a user-defined threshold, concatenate that sample to the exemplars. Continue with the next samples.

The runtime requirements seem to be in O(n_samples*n_clusters), and memory requirements in O(n_clusters).

In practice this seemed to be by far the fastest and most memory-economic clustering algorithm for my dataset (as said: many samples, well separated clusters).

Here's the code:

DISTANCE_THRESHOLD = 100

# Initialize array of exemplars using the first sample, in order to avoid cheking in each loop iteration whether the exemplar array is empty.
exemplars = samples[0:1,:]

for batch in batches:
    # If one of the new samples is far away from all exemplars, concatenate it to the exemplars.
    while (distances_to_nearest_exemplars := (distance_matrix := scipy.spatial.distance.cdist(batch, exemplars)).min(axis=1)).max() > DISTANCE_THRESHOLD:
        new_exemplar_index = distances_to_nearest_exemplars.argmax()
        exemplars = np.concatenate([exemplars, batch[new_exemplar_index:new_exemplar_index+1,:]])
        # TODO check whether keeping exemplars in a list rather than a Numpy array is faster.
        # `distance_matrix.argmax(axis=1)` can be used to compute cluster assignments for the samples.
        # Deleting the sample from the batch is optional because the sample will be below the threshold after recomputing the ditances
        #   (which the `while` loop recomputes anyway in order to avoid adding several similar samples from the same batch).
        # `scipy.spatial.distance.cdist` seems faster than `scipy.spatial.distance_matrix`.

Optionally, exemplars (centroids) can be updated whenever desired by averaging the samples assigned to their cluster so far.

Describe alternatives you've considered, if relevant

I tried various clustering algorithms from sklearn for (very) large n_samples, but they were too memory-hungry and slow.

Additional context

As a bonus, the algorithm is applicable to online clustering.

Knowing the number of clusters is not necessary.

If a specific number of clusters is desired, this can be achieved as described below.

Centroids can be updated in the end (see above) and iteratively merged, if a cluster hierarchy (or a smaller number of clusters) is desired. (To get a larger number of clusters first, the threshold can be set low.)

Start with the issue's standalone Python example and the scikit-learn clustering overview it links to; no repository file or test entry point is identified. Determine whether the proposed threshold-based exemplar algorithm can be specified as a scikit-learn clustering estimator, including unknown cluster counts, online processing, and low-memory behavior; completion would require a decided API and corresponding implementation and tests.