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

Julien Jerphanion <[email protected]> Wed, 05 Jul 2023 20:39:37 +0000

Newsgroups	gmane.comp.python.scientific.devel
Message-ID	<PLSzrUDL6XZ-BTQ9oVY7QPArQIU1aQ26PDA3qh5JtT2PH12jpFx90yjN3aLsYebId4Fpi-Ki5AV3IxUWg_AMML59MFh40Vrxxy5K2mDc7gQ=@jjerphan.xyz>

Hi Mathias,

Thank you for your proposal.

I think that \`sklearn.cluster.AgglomerativeClustering\`¹ implements what you propose.

This implementation also supports other dissimilarities such as the cosine dissimilarity and the Manhattan distance.

Best,
Julien.

1: https://scikit-learn.org/stable/modules/generated/sklearn.cluster.AgglomerativeClustering.html
\-------- Original Message --------
On Jul 5, 2023, 17:00, < [email protected]> wrote:

>
> 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]

_______________________________________________
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]

publickey - EmailAddress([email protected]) - 0xDEDBF4EA.asc (application/pgp-keys, 3.1 KB)

signature.asc (application/pgp-signature, 855 B)