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

That is actually very interesting. Does it have support for scipy-like
linkage matrices?

If not, there are a few downstream packages that would heavily benefit from
code ported from sklearn (ie skbio, and seaborn), so there are few folks
(including myself) that could review of there is interest within scipy for
long term maintenance.

Best,
Jamie

On Wed, Jul 5, 2023 at 4:42 PM Julien Jerphanion <[email protected]> wrote:

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

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