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

Julien Jerphanion <[email protected]> Thu, 06 Jul 2023 12:16:29 +0000

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

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]

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

-----BEGIN PGP PUBLIC KEY BLOCK-----

xsFNBFhax+kBEADWCcFOgTPAO8LnpohB8lh+qOaKyNmC8K5EunMwt35J9mxd
XNLy3BbNli5fFU2xl9AqFXj3GeeBvENdQn2jwbDSfzMGpRAZ8KD8nYNgZFsP
tckakrpcmS69BF/I/6sdA9o9FP//MoZCEx+yQ7xaA9LRdQA9caFgtmpuqdYJ
PPI/IWJLKVjyMjrr+KwGFHfo68sWlkW7dq4dN5sFud1oT0ZnzVEjo+xKV+x/
e7JwpMI5bTz4KXe3ChUJfBZ4ArQHRIiPSqWh980Pr20RGXrCcVJkbChBE0XI
KIHefBIHH88zg8LmiL0R3bfEtUCPAJQBSHzcUcPG8mdCOvkYx1fNxddWyp1t
H8BFhpbE/foMkXLZq6YtwV4cYPISiJkV7WKKCtwiOqtMcIlI6uwrM0SkGQap
8ZQ6K2Q757+IkPLtgcvCCrv/f1iECcJtMKqO3oG1zSSjjqd1TtfKN+LlcQ+m
r5/KiO2iMgVQipOrVfVgEU6CD7Gdn09mY4cnpy8g+WdYuhTcuLF0RlUKM2YW
kCCyYgjZQ9hq0qYWzmJ7Il0zHts9nRBoaT/QNRS/qRQChNteGjUjwnRy7oOD
MHLoIKfjKQa8sDMHfPgllIgb5o45zkZ2FHorZebfj4rgHPK8Zhu+pZ2/3KMp
Jagh1KTAdVnwwCiyRlvJ6TCAIHX5gSIpcZsrpwARAQABzSUiZ2l0QGpqZXJw
aGFuLnh5eiIgPGdpdEBqamVycGhhbi54eXo+wsF1BBABCAAfBQJcUa/7BgsJ
BwgDAgQVCAoCAxYCAQIZAQIbAwIeAQAKCRBWtpCpfC41uM1CD/46igjsRn1h
xJ0CDIBOKD21zghRQ6KDSUzewAgeFb9xS9WVLeSQUjjge0/d7HI7sywohj0a
iW8HGxHQDQ+JtYVamyDR+RRL1Kggh3n30da35kFTl1PKEmWllt0/IWeturzG
fhLwHxMBTDid1uh7PB/CATM70PEFjNfYvFMcNF7zaBt0pmSqC2u34Ba8vfVL
1irJiEfb7kyZ9SOOjsCd/7rvjASmMDbbiUIdVMEezz3pmqe4jUQkQJ2EY4Z6
unD9IvIxmSVE9Shw9sTy526RbI3ZdWXX69H+QpivSDFXweZ2rl3gSS3y40eD
v1dSiuxJwzmCV/Iyz2WmBREAqY14aZx7d3/E6+btL5qRXQggYezbmTxs4sa4
JZ3WIIGpEEpwxFEYN7SSU9OTM+XsKFvMqVfnyAYmGXGY9apQ06i28G0B4Zku
ZH50pKmkO/M0hzDCEF9TeGmCALwsY4wtIhJZJvTqePRKAR2RZP8HNdM8aKkl
LJSVAxynXSn9FyjZHFsi8GGalV3IS+W8t2pL9dBvkZi99AqBXddnVtoy+qqW
LYSybLjopWFfcBB80QkHC8MuSBs06je5rZ56t46nRqaEP6iDSE29dutPAPxE
WLuaqUssm/m7J4Ov+E7LPx/xlJjslklKSG/iEQqmjW/j1kccUfd1EYm837wB
xGiwGgtKCnyL0c7BTQRYWsfpARAAyyYE/CYuT+ObFp/MmweRw3VH+sKXm+2n
/yzixsNDVptVfcGnh22mrlRGZDPVJmjFIGwUrJrfzv0yatwNmy3DVoQhDte4
70W8wEeKN0lVvCRceLJx2k8EN40qfRTuhMwXQFv4lZaR0Zyv/u6Kj7SSlklH
Qb5J/hcQjH+WRwx5/g8GNJRHr5U5RTu1X/e0GeJWp1GYsCNJH5VtdMr8WRwb
9NtAEVAvqWG/EIR4oyCh9kquq/RXR2AZhNp/WOu+4EkICOTaqy65PCEjpRAg
C9aoR4LV6T2uTDe/7SltANU9sG5eeTuOUs2Hdjqr1l4oBgcF3aFbPTWLVR45
2H8uwi0ukXWACEr8ijQJLcTzEC4LhEUlvMqnkaD8maE4zdGX9Te3Owvc8NxI
9GSPopZOKNzn96IohFJbymmc67NDhuWfgHOPNt3+hthseVpplxVtDDJjaTRx
XDMZUOZ1cT2qllAj18DGRwARfrNhWTqdkh+64kkdlazbb8wnxM1ZFBn8SBrx
5v0uc2JQxqA60sJiszr6qYNx8RPwAXXVmZV+b9s01iIiyCVkQ/BJE+TfVa+o
mj5w/Afb+QZGDjZjz/bgqgTAEJcfFA6ABgVizdPuP6LgLdnibTQZL6XOftVn
FlLYJBSIZxQhx9c1ymlTXplNzldg7L5esOouwt2F+BxvMns4CS0AEQEAAcLB
XwQYAQgACQUCXFGv+wIbDAAKCRBWtpCpfC41uEzIEAC0I6SJX9+KF70YLD5z
jLDAwXXdkMu28p+s4oso4CQs8AxvAHZK/JmAeVRNmD/H/74D+gsQcA3xwOGZ
GzcTPiF8k1z/Ves6s2de826WFgRfawCmabTsLUCzq6imEVl3XuFtxu6nOea2
1TDeFdJk++hLpqcT3c2jRnA2outtlH+fqXbQQlo5sC2GYmv/hHIuxHFaAPdC
X8hYMbYtDQfdTwXl4ZVqQAsh4iWGIY9o+MqFACao7iaLgHe3FXVhnchwZh2I
zW3fAXMO9A55GgacRcIZl0N6m/Bou+WTInoKooTXAS2mAry3ri4ke1hcWINj
AOMhWjJq6L+zTfNw2sTrrKUDJg4TrcZU5UXHZH1KMnm9/hXDWdIwCUbleIF3
IOn/Kki1PiQyi9p941IYU7LtDGh0KBtYUlYpIfefDYckkfyuRpEXXFTnkgWt
bAlJqh52H1eaftSUq6CQ0UP2IkvJLYtYtAUGqIbgULhLUcdSlDrVZ1GX8CkI
9KtLHW8et+112ztrdDkEddExRWhQtS6pIokOIS6puZwQqGUkFB7xW146Ox/w
RiFQTDOYejzdPEZhUBfsVYsbcbV2Fp0nCTw2/dAheQlCIwmjcZG4fJLoJzP2
nlNptimf14lh7Mas+p7yYqzhpBNCw0lZ41RKwrePTDITe/50IBIgOp9XtTE0
WFaaDg==
=/cO6
-----END PGP PUBLIC KEY BLOCK-----

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

-----BEGIN PGP SIGNATURE-----
Version: ProtonMail

wsFzBAEBCAAnBYJkprCHCZBWtpCpfC41uBYhBN7b9Or9ieiZmPAnSVa2kKl8
LjW4AABtOQ//VCZzWAInPvVnSRRdGL8+XUnpBJ4BvKEOrJjyG1HxiWDsStTK
bf0XeKMQa2C3wXLGUqETmuDsEy1yQdmJnDBNyjjTqcPhpb0HOYnEdK8Gqhq8
68N+f295otWyLZ+ZNgTA2Y4Hl1AHSbSUerb6rSrN4H82JYGiwbQofINHvvyh
d4KuwDXrYY17W734+8wUw9JCOKcfzpqaxloLk4orBcDsRaKVtc9VBWs0x5Ld
7L/w6mxg5+IZ5hpYHru1jIf01q21SbZBhp5hIuZen6+e8vmcWA+OfF8AbgSg
KTfsxfUPwqEwmRkYW9/GiGZLzaegNwTxNgXFs9MMCpNubZdZ0aYwmS50Fqt0
iNVA+v73HkRk/RBpZ4mjAvLDnIZAE2B414Czp9ofbaoFRUyyYHTQsm92higJ
6zM8VexAtyx66BbPGUafNXw5+Z2PvbuIkMr65WIvq7ZRusvjpSMq8Gv6TVJh
hGK1cx69MQFfWZJHgVLhcsb3k3uQtRqtSTIHmWCzc1IU2ocjs9N9BJ4Ikk6B
RydDmYF9ZjzMH2CAJWyRis0ZA4nth8ulSVmXKMlvGd4vMir49uRGGi0zN3qb
6NnBJG+lgSWYqfxHWcg6J+XoI0j4SVsP0BTA7L9PAIgy5MzzAVxAjGx8BpLj
+RvPbxr7Vy0nuDyJzgkthLWtH+lpf4luI9c=
=F5xT
-----END PGP SIGNATURE-----