Metadata-Version: 2.4
Name: fishdbc
Version: 1.0.0
Summary: FISHDBC: flexible, incremental, scalable, hierarchical density-based clustering for arbitrary data and distance measures
Author-email: Matteo Dell'Amico <della@linux.it>
License-Expression: BSD-3-Clause
Project-URL: Homepage, https://gitlab.com/bobtables/fishdbc
Project-URL: Paper, https://arxiv.org/abs/1910.07283
Keywords: clustering,density-based,hierarchical,incremental,hdbscan,non-metric
Classifier: Development Status :: 5 - Production/Stable
Classifier: Intended Audience :: Developers
Classifier: Intended Audience :: Science/Research
Classifier: Programming Language :: Python :: 3
Classifier: Programming Language :: Cython
Classifier: Topic :: Scientific/Engineering :: Artificial Intelligence
Requires-Python: >=3.10
Description-Content-Type: text/markdown
License-File: LICENSE
Requires-Dist: anydist>=1.0.2
Requires-Dist: fast-unionfind
Requires-Dist: numpy
Provides-Extra: test
Requires-Dist: pytest; extra == "test"
Requires-Dist: scikit-learn; extra == "test"
Dynamic: license-file

# 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](https://gitlab.com/bobtables/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](https://github.com/scikit-learn-contrib/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

```sh
pip install fishdbc
```

or, from a checkout of this repository:

```sh
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):

```sh
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:

```python
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](https://gitlab.com/bobtables/anydist) for the full table and
for how to supply your own C/numba implementations for maximum speed.

```python
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:

```python
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](#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](https://en.wikipedia.org/wiki/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](#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.](https://dl.acm.org/doi/abs/10.1145/2733381), and [McInnes and
Healy](https://arxiv.org/abs/1705.07321) 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.

```python
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 `add`s.

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](https://hdbscan.readthedocs.io/en/latest/api.html#hdbscan) —
`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](https://hdbscan.readthedocs.io/en/latest/_modules/hdbscan/hdbscan_.html):

- **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](http://docs.scipy.org/doc/scipy/reference/cluster.hierarchy.html)).
- **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](https://hdbscan.readthedocs.io/en/latest/advanced_hdbscan.html)
— 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:

```python
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:

```python
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:

```python
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:

```python
# 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:

```python
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](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.
