FISHDBC

Scalable, incremental hierarchical density-based clustering with a Flexible, Incremental, Scalable, Hierarchical Density-Based Clustering algorithm (FISHDBC is the acronym). This package lets you cluster arbitrary data with an arbitrary distance function you write (or reuse from somebody else's work!) — a true metric is not required, and neither is anything else beyond a number saying how dissimilar two elements are. Clustering is incremental: you can keep adding elements and re-cluster cheaply as new data arrives.

Please see the paper at https://arxiv.org/abs/1910.07283.

Approximate nearest-neighbor search is delegated to the companion anydist package, which provides it through a Hierarchical Navigable Small World graph (HNSW) — the data structure the names below refer to; see anydist for what it is and how to tune it. The freedom in the distance function is anydist's doing too. The hierarchy extraction reuses hdbscan's single-linkage labelling and cluster-tree routines, which are vendored (BSD-3, in fishdbc/_hdbscan.pyx) so clustering needs neither hdbscan nor its scikit-learn/joblib dependency chain.

Two implementations are provided:

• FISHDBC (an alias of FISHDBCFast) — the default: a Cython implementation over typed data structures, built on anydist.HNSWFast. It supports arbitrary Python distance callbacks, plus an optional built-in metric mode (euclidean, cosine, angular, dot, l1, linf, ...) that skips the Python callback entirely.
• FISHDBCPure — the pure-Python reference implementation, built on anydist.HNSWPure.

FISHDBC exists only where the compiled extension does, and does not fall back to FISHDBCPure on its own: the reference implementation runs several times slower over the same source, and a clusterer that quietly became it is a performance bug that looks like nothing at all. Importing it then raises, explaining the trade. Write from fishdbc import FISHDBCPure as FISHDBC to take it deliberately; FISHDBC.from_metric below then builds over anydist.HNSWPure as well. anydist.HNSW behaves the same way, and the two extensions are independent: a build can have either, both or neither.

Installation

pip install fishdbc

or, from a checkout of this repository:

pip install .

Windows is not supported: MSVC, the compiler Windows Pythons are built with, lacks the atomic builtins the parallel code needs. Under WSL, the Linux wheels work as usual.

PyPI has prebuilt wheels for the common platforms. Anywhere else, and from a checkout, pip compiles the extensions, so you need a C compiler with OpenMP. On macOS, fishdbc builds and runs on the OpenMP runtime that anydist ships (see anydist.get_openmp_dir()), since libomp aborts a process that loads two copies of itself; only if anydist has to be built from source too does that need Homebrew's libomp (see anydist's installation notes). For an extra speed boost on the machine you build on (at the cost of a non-portable binary):

FISHDBC_NATIVE=1 pip install .

The runtime dependencies are numpy and anydist, nothing else — deliberately, since it is what lets FISHDBC install on interpreters the wider scientific stack has not reached yet (free-threaded builds especially, where scipy and scikit-learn routinely lack wheels for months after a Python release).

The test suite likewise needs only numpy and pytest; its scikit-learn and hdbscan checks skip cleanly when those are absent.

Quickstart

FISHDBC.from_metric(metric, ...) builds a clusterer over a sensibly-configured HNSW. Its only positional argument is the distance between data elements, and it defaults to "euclidean" — so FISHDBC.from_metric() clusters numeric vectors out of the box. What FISHDBC is distinctive for, though, is that it takes a distance of your own over arbitrary objects just as happily:

from fishdbc import FISHDBC

clusterer = FISHDBC.from_metric(my_distance)
for elem in my_data:
    clusterer.add(elem)
result = clusterer.cluster()
labels = result.labels  # result is a named tuple (see Return values)

for elem in some_new_data:  # supports cheap incremental clustering
    clusterer.add(elem)
# new clustering according to the newly available data
labels = clusterer.cluster().labels

The argument is named metric after scikit-learn's and hdbscan's usage, which anydist follows: there too metric= is just the parameter that picks the distance, and both accept distances that are not true metrics. Nothing here requires one either: the triangle inequality may fail — cosine, one of the built-ins below, fails it — and non-metric distances are key in FISHDBC's design. This README says distance throughout for whatever your function returns.

For numeric vectors, the built-in metric mode is substantially faster than Python callbacks. Pass a metric name from anydist.metrics (like euclidean, cosine, angular, dot, l1, linf, or their aliases) — cosine being the one to reach for if you want cosine distance, since it normalizes for you. See the anydist README for the full table and for how to supply your own C/numba implementations for maximum speed.

clusterer = FISHDBC.from_metric("euclidean")  # or just FISHDBC.from_metric()
for v in vectors:
    clusterer.add(v)

"euclidean" is the default, so clustering numeric vectors in an Euclidean space takes no argument at all.

FISHDBC clusters on top of a distance-pair source — any object with an add_recording(elem) -> (i, j, dist) method, anydist.HNSW being the built-in one. FISHDBC.from_metric is a thin wrapper that constructs one; for full control over the HNSW (or to plug in a different source), build it yourself:

from fishdbc import FISHDBC
from anydist import HNSW

clusterer = FISHDBC(HNSW(my_distance, m=16, ef=100, keep_pruned=True))

The source must be empty at construction and thereafter driven only through clusterer.add — it is exposed for reading as clusterer.source, so if the source supports nearest-neighbour queries, you can ask it questions like clusterer.source.search(q, k) which answer "what is this point near?". FISHDBC itself has no search: the protocol is add_recording() alone, and a conforming source (an LSH pair generator, a kNN-graph replayer) need not support nearest-neighbor queries at all. When the elements stop coming, clusterer.drop_source() lets go of it and keeps the clustering (see Saving and loading).

A source that inserts a batch better than one element at a time — in parallel, say — can also offer update_recording(elems, num_threads=None) -> (i, j, dist), and clusterer.update then hands it the elements in chunks instead of calling add_recording for each. num_threads=None asks for the source's own default, so a source that is only safe on one thread stays on one unless the caller asks for more; anything else about how it inserts is set on the source, as HNSW(..., chunksize=...) is. The arrays it returns are handed over rather than lent: FISHDBC may write into them and keep them.

The candidate pool

FISHDBC maintains a minimum spanning tree (MST) — a small structure, n - 1 edges for n elements — from which the clustering is derived. add, add_edges and update do not update it directly: they fill a pool of candidate edges, which flush() processes and empties. cluster() and fishdbc.save flush on their own, so a saved clusterer never carries a pool (see Saving and loading); calling flush() yourself only reclaims the pool's memory at a moment of your choosing.

The pool grows with the source's ef as well as with n, and it is what dominates memory during a build, so it is bounded: max_pool_bytes, a constructor argument that defaults to 1 GiB, flushes it whenever it fills. Below the budget nothing changes, and a single flush at the end stays the fastest path. Above it, peak memory holds at about four to five times the budget on top of what the index and the clusterer keep anyway, and the extra flushes cost time: measured, a 400k-point build whose pool fills 1 GiB twice took 11% longer. Pass max_pool_bytes=None to never flush on your behalf, or a smaller budget under memory pressure. FISHDBCPure counts its pool entries at their real size on the running interpreter, several times what FISHDBC needs for each.

To understand what the MST is and how it drives clustering, see Campello et al., and McInnes and Healy for the accelerated implementation this package vendors its extraction routines from.

Clustering a graph you already have

A source is one way to produce (i, j, distance) triples. The other is to push them in directly, which is what add_edges is for — distances that already exist or are computed elsewhere: a kNN graph from another library, GPU-batched distances, pairwise scores out of a database or a pipeline.

from fishdbc import FISHDBC

clusterer = FISHDBC.from_edges(min_samples=5)
clusterer.add_edges(rows, cols, distances)  # any iterables, any length
labels = clusterer.cluster().labels  # indexed by node id

The three arguments are duck-typed: numpy arrays of any integer or float width, lists, tuples, array.array, range, or a lazy iterator that is never materialised. np.int32/np.float64 arrays — what anydist.HNSW produces — are the one form the Cython implementation consumes with no copy; everything else is converted on the way in. The same holds for the (i, j, dist) triples a source returns from add_recording, so a source of your own may hand back whatever is natural to build.

add_edges is the primitive; add is the same thing with a source asked for the triples first. Nodes are the integer ids in the edges: a node exists as soon as an edge names it, and an id never named is isolated and comes out as noise. With no source, the id space is yours and len() grows to cover the largest id seen. With a source, the source owns the ids and pushed edges may only relate elements it has already issued — supplementary information about existing points (a second modality, a known relation, an exact distance for a pair the ANN only approximated). A larger id is refused rather than absorbed, because it would desync the count from the source's and corrupt later adds.

Two things to know. Give every node at least min_samples neighbours: fewer leaves its core distance infinite, so it can only cluster as noise, and cluster() warns when that happens — pushing a k-nearest-neighbour graph with k < min_samples degenerates every node at once. And feed each unordered pair once: dedup=True (the default) makes a repeat harmless, but kNN graphs naturally carry both (i, j) and (j, i). FISHDBC.from_metric sets dedup=False, since an HNSW cannot report the same pair twice; turn it off yourself only if you are generating the pairs and know they are unique, which saves an O(min_samples) scan on each accepted neighbour.

Extraction-time parameters

cluster() also accepts hdbscan's extraction-time knobs — cluster_selection_epsilon, cluster_selection_persistence, max_cluster_size, cluster_selection_epsilon_max — alongside min_cluster_size, cluster_selection_method, allow_single_cluster. These parameters can be tuned cheaply without rebuilding: changing them and re-running cluster() extracts a new clustering from the existing data, so you can experiment with different parameter values at a fraction of the cost.

Return values

cluster() returns a FISHDBCResult named tuple — still a plain tuple in the same order as hdbscan.hdbscan(), so it unpacks positionally, but its fields are also accessible by name. As documented in the HDBSCAN source code:

• labels — ndarray, shape (n_samples,). Cluster labels for each point. Noisy samples are given the label -1.
• probabilities — ndarray, shape (n_samples,). Cluster membership strengths for each point. Noisy samples are assigned 0.
• cluster_persistence — array, shape (n_clusters,). A score of how persistent each cluster is. A score of 1.0 represents a perfectly stable cluster that persists over all distance scales, while a score of 0.0 represents a perfectly ephemeral cluster. These scores can gauge the relative coherence of the clusters output by the algorithm.
• condensed_tree — record array. The condensed cluster hierarchy used to generate clusters.
• single_linkage_tree — ndarray, shape (n_samples - 1, 4). The single linkage tree produced during clustering, in the scipy hierarchical clustering format (see the scipy docs).
• minimum_spanning_tree — ndarray, shape (n_samples - 1, 3). The minimum spanning tree as an edge list.

Using hdbscan's tree tools

The trees come back as plain arrays, but hdbscan's own wrappers accept exactly those arrays, so everything in Advanced HDBSCAN — dendrogram and icicle plots, to_networkx(), to_pandas(), get_clusters() — works on a FISHDBC result once you wrap it yourself. Where hdbscan would give you clusterer.condensed_tree_, construct the wrapper directly:

from hdbscan.plots import CondensedTree, SingleLinkageTree

result = clusterer.cluster()

# hdbscan's condensed_tree_ takes the tree *and* the per-point labels
ct = CondensedTree(result.condensed_tree, result.labels)
ct.plot(select_clusters=True)
graph = ct.to_networkx()

SingleLinkageTree(result.single_linkage_tree).plot()

This needs hdbscan installed (and matplotlib for the plots) — FISHDBC itself does not require either.

minimum_spanning_tree is the exception. hdbscan.plots.MinimumSpanningTree takes (mst, data) and plots the nodes at their own coordinates, projecting with t-SNE when the data has more than two dimensions, so it only makes sense when you clustered numeric vectors and can hand it that array:

from hdbscan.plots import MinimumSpanningTree

MinimumSpanningTree(result.minimum_spanning_tree, X).plot()

With an arbitrary distance over non-vector objects there is no such X, and hdbscan hits the same limit — it warns and returns None for minimum_spanning_tree_ whenever the raw data is unavailable.

Saving and loading

A clusterer pickles like anything else, and most of the time that is the whole story:

with open("c.pkl", "wb") as f:
    pickle.dump(clusterer, f)

Everything FISHDBC owns is ids and distances in plain arrays, and an anydist.HNSW pickles too — a built-in name like 'euclidean' (what FISHDBC.from_metric uses unless you say otherwise) or a module-level function travels fine. Three kinds of distance function do not: a lambda, a closure, and a C function pointer, where a raw address would be meaningless in the loading process anyway.

That is what fishdbc.save/fishdbc.load add — pickle, plus the ability to leave the distance function out and supply it on the way back in:

# the source is kept, its distance function is not
fishdbc.save(clusterer, "c.pkl", include_metric=False)
clusterer = fishdbc.load("c.pkl", metric=my_distance)

They handle the ordinary case as well: fishdbc.save(clusterer, 'c.pkl') writes a self-contained file that fishdbc.load('c.pkl') — or plain pickle.load — opens, and it raises rather than writing a file load could not open, naming the way out, so you never get an artefact that only looks self-contained.

save also calls flush() before writing, so the file holds the retained edges rather than the candidate buffer behind them — measured over 600 elements, 5x smaller at the source's ef=20 and 12x at ef=200, since the buffer grows with ef where the retained set stays at n - 1 edges. The clustering is unaffected; it is the same flush cluster() already does. Plain pickle.dump cannot do this for you (a __reduce__ with side effects would be a trap), so call flush() yourself first if you pickle directly.

include_metric=False is for the HNSW from_metric builds for you: it hands the source to anydist.save and gives it back through anydist.load, so what you pass as metric= must be the same distance the index was built with — that cannot be checked, and a different one leaves the graph answering for a distance it was not built for.

For a source of your own, include_source=False leaves the whole source out, whatever it is, and load(f, source=...) puts it back; the source's length is checked against the clusterer's, which catches a stale or a fresh one. Passing source=fishdbc.NO_SOURCE instead loads the clustering without an index at all — cluster() still answers for every min_samples it was built for and add_edges() still works, but add() has nothing to compute distances with.

clusterer.drop_source() does the same thing in memory, without a round trip through a file:

clusterer.drop_source()  # keep the clustering, release the index

The source is usually the larger half of the pair — it holds the elements and the graph over them, where the clusterer holds ids and distances — so once the elements have stopped coming this is the cheap way to shed it. It is also what makes an unpicklable distance stop mattering: with the index gone, the clusterer pickles as it is. Take clusterer.source first if you want to save or keep it; nothing is handed back, so that a drop is a drop.

Only load files you trust. save/load are built on pickle, and unpickling any file runs code that the file chooses. That is pickle's design, not something this package adds or can screen for: load sees what the file contains only after the interpreter has already executed whatever the stream asked for, and a saved clusterer normally carries a whole HNSW inside it, read back the same way. Supplying the distance yourself does not help — the code runs before your metric= is ever consulted. Treat a saved clusterer exactly as you would a .py you were about to run; it is not a safe interchange format for data from elsewhere.

Demo/Example

Look at examples/fishdbc_example.py for an interactive demo of incremental clustering and of walking the condensed tree to recover the hierarchy (it needs matplotlib and scikit-learn, which FISHDBC itself does not).

Author

Matteo Dell'Amico — della@linux.it

License

BSD 3-clause; see the LICENSE file.