Pretty nifty project. This is a lot more than most "feedback on my project" posts here. I spent some time (way more than I meant to) looking through the core implementation (_clarans.py, _fast_clarans.py, _core.pyx), and there are a few things I'd consider investigating, roughly in order of importance:
float32 precision with precomputed distances
If someone passes a float32 matrix with metric='precomputed', the search buffers stay float32. clarans_delta and fastpam1_delta then sum the deltas through the fused floating type, so they accumulate in float32 too. But _delta_tolerance() uses a threshold of roughly 1e-12 * abs(cost), which is extremely small relative to float32 precision (around 1e-7) and potentially much smaller than accumulated rounding error.
I wrote a quick standalone NumPy reproduction of the delta sum (not your actual package) that compared float32 accumulation against float64 accumulation of the same float32 values. On a few thousand points or more, the difference was several orders of magnitude larger than the tolerance. That doesn't prove the library accepts bad swaps, but it suggests the tolerance may be too small to reliably distinguish rounding noise from a genuine improvement on that path.
Accumulating in double precision seems like a relatively straightforward improvement, and it might also be worth revisiting the tolerance using np.finfo(dtype).eps and the expected accumulation error. A test that runs float32 and float64 versions of the same precomputed matrix and compares the results would help show whether it matters in practice.
Sampling with replacement
Both _sample_candidate methods use randint, so the same candidate can come up more than once while others never get checked. That's standard for CLARANS, so it's not a bug. But sampling without replacement might be worth benchmarking, especially on smaller datasets where max_neighbors is close to or larger than the neighborhood size.
For FastCLARANS, shuffling the non-medoid indices and walking through them would be O(n), and exhausting that list without an improving swap would establish a local optimum. Classic CLARANS would need to account for every candidate–medoid pair to make the same guarantee, since each candidate can be swapped with multiple medoids.
Distance computation backends
_setup_distance_engine() selects between SciPy's cdist, scikit-learn's DistanceMetric, and pairwise_distances depending on the input and metric.
I'd consider adding parametrized tests comparing equivalent metrics across those paths, particularly for sparse inputs, zero vectors, and cosine distance. Different implementations can handle numerical edge cases differently, and inconsistent distances could be difficult to diagnose.
Small docstring issue
The CLARANS.fit docstring says CLARANS avoids caching the full distance matrix "compared with FastCLARANS," but FastCLARANS doesn't cache it either, and its own Notes section says so. It looks left over from an earlier version.
What to add next
I'd add evidence before more features. A comparison against established implementations (ELKI's FastCLARANS, the kmedoids package) on standard datasets, reporting final cost, runtime, and memory usage, would help validate the results and show where your implementation fits compared to existing options.
I'd also keep the infrastructure in check. There's a lot here already: multiple distance backends, Cython kernels, Python fallbacks, buffer reuse, threading, and a big regression suite. Some of it is probably justified, but before adding more I'd make sure you can say why each piece exists, what problem it solves, and what would break without it. With numerical code, a change you don't fully understand might not crash anything. It might just give slightly wrong answers.
Overall, pretty solid work! I hope some of this is useful!
Thanks a lot for the deep dive and the reproduction script! You're spot on about float32: ELKI uses doubles everywhere, so borrowing its 1e-12 threshold breaks on float32 noise. I'll accumulate deltas in double internally and scale tolerance with np.finfo(dtype).eps.
I also checked ELKI's source and saw Schubert explicitly used an in-place Fisher-Yates shuffle in FastCLARANS.java, so I'll switch FastCLARANS to sample without replacement to match. I'll get the backend parity tests added, fix the docstring, and prioritize benchmarks against ELKI over new features.
what made you decide it wasnt suitable for the journal submission? knowing where you feel it falls short right now would make it a lot easier to give targeted feedback on the structure
My main worry was scope and novelty. Since the project implements existing algorithms (CLARANS and FastCLARANS) instead of introducing a new method, I wasn't sure if JOSS would consider it too narrow or lacking "substantial scholarly effort."
2
u/gofuckadick 1d ago
Pretty nifty project. This is a lot more than most "feedback on my project" posts here. I spent some time (way more than I meant to) looking through the core implementation (
_clarans.py,_fast_clarans.py,_core.pyx), and there are a few things I'd consider investigating, roughly in order of importance:If someone passes a float32 matrix with
metric='precomputed', the search buffers stay float32.clarans_deltaandfastpam1_deltathen sum the deltas through the fusedfloatingtype, so they accumulate in float32 too. But_delta_tolerance()uses a threshold of roughly1e-12 * abs(cost), which is extremely small relative to float32 precision (around1e-7) and potentially much smaller than accumulated rounding error.I wrote a quick standalone NumPy reproduction of the delta sum (not your actual package) that compared float32 accumulation against float64 accumulation of the same float32 values. On a few thousand points or more, the difference was several orders of magnitude larger than the tolerance. That doesn't prove the library accepts bad swaps, but it suggests the tolerance may be too small to reliably distinguish rounding noise from a genuine improvement on that path.
Accumulating in double precision seems like a relatively straightforward improvement, and it might also be worth revisiting the tolerance using
np.finfo(dtype).epsand the expected accumulation error. A test that runs float32 and float64 versions of the same precomputed matrix and compares the results would help show whether it matters in practice.Both
_sample_candidatemethods userandint, so the same candidate can come up more than once while others never get checked. That's standard for CLARANS, so it's not a bug. But sampling without replacement might be worth benchmarking, especially on smaller datasets wheremax_neighborsis close to or larger than the neighborhood size.For FastCLARANS, shuffling the non-medoid indices and walking through them would be O(n), and exhausting that list without an improving swap would establish a local optimum. Classic CLARANS would need to account for every candidate–medoid pair to make the same guarantee, since each candidate can be swapped with multiple medoids.
_setup_distance_engine()selects between SciPy'scdist, scikit-learn'sDistanceMetric, andpairwise_distancesdepending on the input and metric.I'd consider adding parametrized tests comparing equivalent metrics across those paths, particularly for sparse inputs, zero vectors, and cosine distance. Different implementations can handle numerical edge cases differently, and inconsistent distances could be difficult to diagnose.
The
CLARANS.fitdocstring says CLARANS avoids caching the full distance matrix "compared with FastCLARANS," but FastCLARANS doesn't cache it either, and its own Notes section says so. It looks left over from an earlier version.I'd add evidence before more features. A comparison against established implementations (ELKI's FastCLARANS, the
kmedoidspackage) on standard datasets, reporting final cost, runtime, and memory usage, would help validate the results and show where your implementation fits compared to existing options.I'd also keep the infrastructure in check. There's a lot here already: multiple distance backends, Cython kernels, Python fallbacks, buffer reuse, threading, and a big regression suite. Some of it is probably justified, but before adding more I'd make sure you can say why each piece exists, what problem it solves, and what would break without it. With numerical code, a change you don't fully understand might not crash anything. It might just give slightly wrong answers.
Overall, pretty solid work! I hope some of this is useful!
1
u/Faveret_Demcho 1d ago
what made you decide it wasnt suitable for the journal submission? knowing where you feel it falls short right now would make it a lot easier to give targeted feedback on the structure