Add low-memory special case for Euclidean single-linkage clustering

Hi all

Single-linkage clustering in scipy uses quadratic memory, even though
it is relatively straightforward to implement using only linear memory.
I'd like to propose adding a special case to use a linear-memory
implementation for the specific case of single-linkage clustering
with Euclidean distances, which would close GitHub issue scipy#9031
("Low memory version of single linkage clustering", July 2018).
Specifically, I'd like to propose a "low-code" solution that doesn't
involve implementing new complicated algorithms and data structures,
but instead uses the existing public API of scipy, to minimize the risk
of bugs and minimize future maintenance costs. I've implemented a
proof of concept, and I'll volunteer to submit a PR if you'd like.

scipy.cluster.hierarchy.linkage() computes hierarchical clustering
with any distance metric and in any dimension of space and with
multiple different definitions of distances between clusters.
It is implemented by first computing the distance matrix with pdist()
and then working with that, and this distance matrix is the reason
that the current implementation uses quadratic memory.

For single-linkage clustering, you don't need the full distance matrix,
and scipy actually has all the parts to compute Euclidean single-linkage
clustering with quite few lines of Python code, as follows:

1. Compute the Delaunay triangulation of the input points
2. Compute the MST (Minimum Spanning Tree) on the triangulation's edges
3. Convert the MST to a single-linkage hierarchical clustering

Step 1 and 2 are implemented in scipy already; step 3 can be done in
near-linear time using Union-Find (about 20 lines of code).

Here's my proof of concept: https://github.com/Mortal/singlelinkage

I would call this approach a "low-code" solution to scipy#9031,
as it doesn't need to involve new Cython (or C++ or ...) code.
You could probably combine step 2 and 3 and implement it in Cython for
some extra speed, but I don't think it's worth it.
It would be nice to support other metrics besides the Euclidean,
but that would require replacing step 1 with some other approach
that leads to a linear-size distance graph that is a guaranteed superset
of the MST, and I'm not sure what that looks like for arbitrary metrics.

Would scipy welcome a low-code special case for hierarchical clustering
using single linkage and Euclidean distances, to solve scipy#9031?

Cheers,
Mathias
_______________________________________________
SciPy-Dev mailing list -- [email protected]
To unsubscribe send an email to [email protected]
https://mail.python.org/mailman3/lists/scipy-dev.python.org/
Member address: [email protected]