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

Julien Jerphanion <[email protected]> Fri, 07 Jul 2023 06:20:40 +0000

Newsgroups	gmane.comp.python.scientific.devel
Message-ID	<A9P4qSx_rEpP4O8kucreL886eoJtLoUGii0t2lkNTyYXXkfwJbN4-AQWLLKR8KiWtOUJIHGVnQDPvJZwCRpVxhYtQ8sHPZOyVhVSdKmOY2Q=@jjerphan.xyz>

After profiling some runs on this `AgglomerativeClustering(linkage='single')`,
the bottleneck is present in `mst_linkage_core` [1].

This computes a distance matrice and performs operations on it suboptimally [2].

Fortunately, this implementation can be optimized as part of some current efforts on
improving some patterns of computations [3].

I will add an item indicating that `mst_linkage_core` can be optimized.

Best Regards,

Julien.

1: https://github.com/scikit-learn/scikit-learn/blob/main/sklearn/cluster/_agglomerative.py#L559C33-L559C49
2: https://github.com/scikit-learn/scikit-learn/blob/main/sklearn/cluster/_hierarchical_fast.pyx#L428-L506
3: https://github.com/scikit-learn/scikit-learn/issues/25888

------- Original Message -------
On Thursday, July 6th, 2023 at 2:16 PM, Julien Jerphanion <[email protected]> wrote:


> Hi,
> 

> OK, thank you for reporting that. I do not think `AgglomerativeClustering` would be suitable for now.
> 

> The implementation uses a UnionFind, but it seems that other parts of the
> implementations are costly.
> 

> I can look into that when I get time one day.
> 

> Julien.
> 

> 

> ------- Original Message -------
> On Wednesday, July 5th, 2023 at 11:50 PM, Mathias Rav [email protected] wrote:
> 

> 

> 

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

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

> > Hi Julien
> 

> > Thanks for the pointer! I just tried to run AgglomerativeClustering with
> > linkage="single" on 10k, 20k, 40k, 80k 2-d points and the runtimes
> > indicate a super-quadratic time complexity: 0.33, 1.45, 5.96, 24.2 s.
> 

> > Given that my use case involves around 200k points in 3-d,
> > I'd like something closer to O(N log N) time - is that possible with
> > AgglomerativeClustering?
> 

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

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

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