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
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.Agglomerat... \-------- Original Message -------- On Jul 5, 2023, 17:00, < m@git.strova.dk> 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 -- scipy-dev@python.org To unsubscribe send an email to scipy-dev-leave@python.org https://mail.python.org/mailman3/lists/scipy-dev.python.org/ Member address: git@jjerphan.xyz
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 <git@jjerphan.xyz> 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.Agglomerat... -------- Original Message -------- On Jul 5, 2023, 17:00, < m@git.strova.dk> 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 -- scipy-dev@python.org To unsubscribe send an email to scipy-dev-leave@python.org https://mail.python.org/mailman3/lists/scipy-dev.python.org/ Member address: git@jjerphan.xyz _______________________________________________ SciPy-Dev mailing list -- scipy-dev@python.org To unsubscribe send an email to scipy-dev-leave@python.org https://mail.python.org/mailman3/lists/scipy-dev.python.org/ Member address: jamietmorton@gmail.com
On Wed, 05 Jul 2023 20:39:37 +0000 Julien Jerphanion <git@jjerphan.xyz> 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
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 <m@git.strova.dk> wrote:
On Wed, 05 Jul 2023 20:39:37 +0000 Julien Jerphanion git@jjerphan.xyz 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 -- scipy-dev@python.org To unsubscribe send an email to scipy-dev-leave@python.org https://mail.python.org/mailman3/lists/scipy-dev.python.org/ Member address: git@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/_aggl... 2: https://github.com/scikit-learn/scikit-learn/blob/main/sklearn/cluster/_hier... 3: https://github.com/scikit-learn/scikit-learn/issues/25888 ------- Original Message ------- On Thursday, July 6th, 2023 at 2:16 PM, Julien Jerphanion <git@jjerphan.xyz> 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 m@git.strova.dk wrote:
On Wed, 05 Jul 2023 20:39:37 +0000 Julien Jerphanion git@jjerphan.xyz 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 -- scipy-dev@python.org To unsubscribe send an email to scipy-dev-leave@python.org https://mail.python.org/mailman3/lists/scipy-dev.python.org/ Member address: git@jjerphan.xyz_______________________________________________
SciPy-Dev mailing list -- scipy-dev@python.org To unsubscribe send an email to scipy-dev-leave@python.org https://mail.python.org/mailman3/lists/scipy-dev.python.org/ Member address: git@jjerphan.xyz
participants (4)
-
Jamie Morton -
Julien Jerphanion -
m＠git.strova.dk -
Mathias Rav