Local Cluster Cardinality Estimation for Adaptive Mean Shift

arXiv:2508.12450 · cs.LG · Submitted 2026-08-12 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Next we'll be talking about the paper "Local Cluster Cardinality Estimation for Adaptive Mean Shift".

Jane: The paper was written by Étienne Pepin from.

Tom: Stay tuned as we take you through the paper and discuss its implications.

Title: Tom: Welcome back to the arXiv radio hour, everyone! Today we're digging into a fresh paper, and it's got a mouthful of a title: "Local Cluster Cardinality Estimation for Adaptive Mean Shift." Jane, I have to say, the moment I saw "cluster cardinality" I knew we were in for something interesting.

Jane: Oh, absolutely, Tom. And honestly, the title tells you exactly what the big idea is. Instead of just guessing how many clusters exist in a dataset, this paper tries to figure out, for each individual point, how many points belong to its own little neighborhood cluster. That's the "local cluster cardinality" part.

Tom: Right, and that feeds into something called adaptive mean shift. For our listeners who haven't heard of it, mean shift is a clustering technique where you imagine each data point rolling uphill toward a peak of density. The "shift" part is that you keep moving points toward their local average until they settle at a mode.

Jane: And the "adaptive" part is the twist. Usually, mean shift needs a bandwidth parameter — basically a fixed radius that says how far to look when computing that local average. This paper says, what if that radius changed from point to point, based on the data around that point?

Tom: Exactly. And the clever bit is how they estimate that radius. They look at the distribution of distances from each point to every other point. For a point sitting inside a cluster, that distance distribution tends to have two humps — one for the nearby points in its own cluster, and another for the rest of the dataset.

Jane: So the valley between those two humps is the natural boundary of the cluster. The paper uses a mathematical function called gamma to find that valley without needing a bandwidth parameter at all. That's huge because choosing bandwidth is often the fiddly part of mean shift.

Tom: And they claim it's scale invariant. That means if you multiply all your data by ten, the algorithm behaves exactly the same. No constants to tune for the scale of your data. That's a real practical win.

Jane: It is. And the authors show that this approach beats an older adaptive mean shift method on seven out of nine datasets. Not bad for a first prototype.

Tom: I love that they're honest about it being a prototype. There's a whole section on future improvements. But before we get ahead of ourselves, I want to bring in Lu from Tsinghua to react. Lu, what jumps out at you?

Lu: The locality property is what excites me, Tom. The gamma function at rank k only depends on the k nearest distances. So if you add or move points far away, the estimate for a local cluster doesn't change. That's a really clean theoretical property that most clustering methods don't have.

Tom: So it's not just practical — there's some elegant math underneath.

Lu: Exactly. And that locality is what makes the scale invariance possible. The parameters are read from the neighborhood, expressed in the units of that neighborhood.

Jane: And that's the hook for our next segment. We're going to dig into how they actually estimate that cluster boundary and what the gamma function really does. Stick around, folks!

Summary: Tom: Welcome back! We're still on "Local Cluster Cardinality Estimation for Adaptive Mean Shift." Last time we set the stage — the paper estimates how many points belong to each point's local cluster. Now let's talk about how they actually do it.

Jane: Right. The core idea is the distance distribution. For each point, you sort all distances to every other point. Then you compute a function called gamma at each rank. Gamma is a ratio — the variance of the distances up to that rank, divided by the squared difference between the mean and that particular distance.

Tom: And when you plot that gamma function, it dips down at the boundary between the local cluster and the rest of the data. The minimum of that dip is where they say the cluster ends.

Jane: Exactly. And there's a nice intuition here. When you're inside the cluster, the distances are all pretty similar, so the variance is low. As you start including points from other clusters, the variance jumps up, and gamma spikes. The minimum right before that spike is the cluster edge.

Tom: Meng, you're the engineer on our team. What do you think about actually implementing this?

Meng: Well, Tom, the first thing I notice is that they compute this for every point in the dataset. That means sorting distances for each point, which is O(n2 log n) at best. For the datasets they tested, which go up to five thousand points, that's fine. But for big data, you'd need some approximation.

Jane: That's a fair point. But they also do something clever with the points that get bad estimates. If a point's minimum gamma lands right at the edge of the search window, they throw that point out of the mean shift process entirely. Those tend to be points sitting between clusters, where the estimate is unreliable.

Tom: And then after the mean shift runs, they classify those discarded points by assigning them to the nearest mode, weighted by each cluster's variance. So nothing gets left behind.

Meng: I also like that they gradually increase the kernel area during the mean shift iterations. They start small and expand up to the estimated cluster size over about a hundred steps. That prevents points far from the cluster center from pulling in neighbors from other clusters too early.

Lu: And that gradual increase is actually a clever fix for a known bias. Points near the edge of a cluster tend to overestimate the cluster cardinality because their nearest neighbors from adjacent clusters sneak in. By starting small, the mean shift can move toward the true mode before the full area is considered.

Jane: So the algorithm is really a three-step pipeline: estimate cardinality, run adaptive mean shift with those estimates, then classify the outliers. And the results? They beat the weighted adaptive mean shift on seven of nine datasets.

Tom: And on four of those, the margin was pretty solid — like zero point one five on the Steel dataset. But on USPS and Image, they lost. Jane, what do you make of that?

Jane: I think it's honest reporting. They don't have access to the other team's implementation, so they can't investigate why. But it does suggest the method isn't universally better yet.

Lu: The high-dimensional kernel they propose is interesting there. USPS has two hundred fifty-six dimensions, and that kernel performed better than the standard Gaussian one. So there's a hint that the method can be adapted for high-dimensional spaces, but it needs more testing.

Meng: And I'd want to see how it scales to millions of points before calling it production-ready.

Tom: Good point, Meng. But the paper's already thinking about improvements, and that's exactly what we're going to talk about next. Stay with us!

Improvements: Tom: Welcome back to our discussion of "Local Cluster Cardinality Estimation for Adaptive Mean Shift." We've covered the core method and the results. Now let's talk about where the authors think this can go next.

Jane: And they're refreshingly honest about the limitations. The biggest one is that the cluster boundary search uses fixed parameters — a minimum and maximum boundary for where to look for that gamma minimum. The default maximum is half the dataset size, which assumes no cluster holds more than half the points.

Meng: That assumption bit them on three datasets in the benchmark. Ionosphere, Sonar, and WDBC all have a majority class bigger than half the data. And sure enough, those are the datasets where their results were weakest.

Tom: Right, and they show that if you raise that boundary to zero point seven, the results improve on two of those three. But they don't tune it per dataset because that would require knowing the answer ahead of time.

Lu: The more elegant fix is to find the modes of the distance distribution algorithmically instead of using fixed boundaries. They suggest using one-dimensional mean shift to locate the rightmost mode — the distances to points outside the cluster — and then search for the valley before that mode.

Jane: And they also mention using kernel density estimation instead of the gamma function, once you have a good bandwidth estimate. The gamma function is nice because it's scale invariant and doesn't need a bandwidth, but a KDE might be more accurate if you can get the bandwidth right.

Meng: I like that they're thinking about the bandwidth problem from both directions. The gamma function avoids it entirely, but if you can estimate the local variance first, you can then use that to set a KDE bandwidth and get a finer-grained density estimate.

Tom: There's also the merge threshold and convergence tolerance in the mean shift loop. Those are still global constants, not derived from local data. The paper says those should eventually be data-driven too.

Lu: That's the deeper research agenda. The gamma function is local and scale invariant, but the algorithm still has three places where global assumptions creep in: the maximum boundary, the merge threshold, and the convergence tolerance. Removing those would make the whole pipeline truly adaptive.

Jane: And there's a bigger vision here. The cluster cardinality estimator could be useful beyond clustering. Any machine learning task that needs to understand local structure — outlier detection, nearest neighbor search, even semi-supervised learning — could benefit from a method that estimates local cluster size without a bandwidth.

Meng: That's a stretch, but I can see it. If you have a robust way to say "these k points form a coherent local group," that's a building block for lots of algorithms.

Tom: And the authors are clear that the cardinality estimator itself is a new task. They're not claiming it's solved. They're inviting the community to study it properly.

Jane: Which is exactly the kind of honest, open research we love to highlight. Before we wrap up, I want to bring in Lalam to give us the big-picture take.

Lalam: Thank you, Jane. The most impactful vision here is a clustering method that requires no user-supplied parameters at all — no number of clusters, no bandwidth, no distance threshold. That would democratize clustering for non-experts. Think of biologists analyzing gene expression, urban planners segmenting city data, or social scientists finding communities in survey responses. They often don't know how many clusters to expect, and they shouldn't have to guess. This paper is a step toward that world, and the authors are honest that it's an early step.

Tom: Lalam, that's a beautiful way to frame it. And it leads us right into our conclusion. Stay with us for the wrap-up.

Conclusion: Tom: And we're back for the final stretch on "Local Cluster Cardinality Estimation for Adaptive Mean Shift." Jane, give us the one-minute summary.

Jane: Gladly. This paper introduces a way to estimate, for each point in a dataset, how many points belong to its local cluster. It does this by looking at the distribution of distances from that point to all others, finding the valley between the two modes of that distribution, and using that valley as the cluster boundary. The gamma function they use is scale invariant and local, which means no bandwidth parameter and no sensitivity to distant points.

Tom: And that estimate feeds into an adaptive mean shift algorithm, where the kernel radius and bandwidth are set per point based on its own neighborhood. The results are competitive — better than the weighted adaptive mean shift on seven of nine datasets, and on par with general clustering benchmarks, all without being told the number of clusters.

Meng: I'd add that the engineering is solid. The gradual area increase and the rejection of bad estimates are practical touches that make the method work on real data. But scaling to large datasets is still an open question.

Lu: And the theoretical foundation is clean. The locality property is genuinely novel, and the path to removing the remaining global parameters is clear.

Jane: So what's the takeaway for our listeners? If you're doing clustering and you're tired of guessing the number of clusters or fiddling with bandwidth, this paper is worth a read. It's not the final answer, but it's a promising direction.

Tom: And we should say goodbye to this paper. It's been a pleasure — "Local Cluster Cardinality Estimation for Adaptive Mean Shift" by Étienne Pepin. We'll be watching to see where this research goes.

Jane: Absolutely. And next up on the arXiv radio hour, we've got a paper on — well, you'll have to tune in to find out. Thanks for listening, everyone!

Tom: See you next time!

Étienne Pepin

cs.LG

Submitted: 2026-08-12

Comments: 24 pages, 9 figures

Code: https://github.com/pEtienn/Adaptive-mean-shift-based-on-local-cluster-cardinality-estimation

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 59/100

Key concepts

Local Cluster Cardinality
This concept refers to estimating how many points belong to a specific local cluster around a data point. Instead of guessing the total number of clusters, the researchers calculate this value for each individual point by examining its surrounding neighborhood and distances.
Adaptive Mean Shift
Mean shift is a clustering technique that moves data points toward density peaks. The 'adaptive' aspect means that instead of using a fixed radius (bandwidth), this the algorithm adjusts its search area based on the local data distribution, allowing it to find clusters without manual tuning.
Gamma Function
The gamma function is a mathematical tool used to estimate cluster boundaries. It is calculated by dividing the variance of distances up to a certain rank by the squared difference between the mean and that specific distance. The minimum point of this function indicates where a cluster ends.

Terminology

Summary

Summary

This paper presents an adaptive mean shift clustering algorithm where every parameter used at a point is derived from that point’s own distance distribution. The distance distribution from a point to all others is used to estimate the cardinality of the local cluster by identifying a local minimum in the density of that distribution; the statistics of the identified subset then set the bandwidth and the kernel radius threshold applied at that point.

The estimator built this way is scale invariant, since the γ function it rests on is unchanged when the data is multiplied by a positive constant, so no length constant has to be chosen for the scale of the data. It is also local: γ evaluated at rank k depends only on the k nearest distances, and the mean shift kernel is truncated at the estimated cluster radius, so data lying beyond that radius neither enters the estimate of the local cluster nor contributes to the weighted mean. This contrasts with kernel density estimation, which in its basic form measures density in a neighborhood of fixed size and needs a bandwidth chosen for the dataset as a whole.

The local cluster cardinality is estimated using distance distributions, which are the distribution of distances from one point to other points. The algorithm searches for the minimum density between the leftmost mode (representing the local cluster) and the rightmost mode of the distance distributions. In the model, this point delineates the boundary of the local cluster and determines its cardinality. The estimated cardinality is then used to calculate statistics on the local cluster, such as its distance variance. Finally, this information is used during the mean shift process to adapt the bandwidth and define a distance threshold for selecting points to include in the local average.

The γ function is defined as γ(y(k)) = s2 / (ȳ − y(k))2, where y(k) = [y(1),..., y(k)], ȳ is the sample mean and s2 is the sample variance of the k nearest distances. The γ function has high values before the first mode, which prevents the minimum from being found before the first mode, and it is scale-invariant since multiplying the data by a positive constant leaves it unchanged. The locality property follows directly from the equation: γ(y(k)) is computed from y(1),..., y(k) only, so distances beyond rank k do not appear in it.

The algorithm works in three steps. In the Cluster Cardinality Estimation step, a cluster cardinality n̂i is estimated for each point xi, points with a cluster cardinality estimate affected by the maximum boundary limit are labelled bad and removed from the set of points used during the mean shift, and statistics are computed on the local distance distribution between xi and the closest n̂i points. In the Adaptive Mean Shift step, all points move iteratively towards their mode, starting with each point p1,i, computing the weighted average p2,i in the sphere including nk∗ points around it, and repeating iteratively until reaching the mode or the maximum number of iterations. The parameter nk∗ increases progressively over 100 steps, from minBoundary to n̂k, which is a gradual mean shift area increase designed to counteract the positive bias in cardinality estimates for points far from cluster modes. In the final step, Classify Points With Bad Estimates, all points that had a bad cluster size estimation are classified by assigning them to the closest cluster, weighing distances by the clusters’ bandwidth.

The algorithm takes as input a dataset X along with minimum and maximum boundary parameters for cluster cardinality estimation, with default values of 5 and n/2, respectively. The mean shift loop carries two constants that the estimator does not: the merge threshold δ, which is the first percentile of the nearest-neighbor distances of the dataset, and the convergence tolerance ϵ, which is an absolute quantity of 10−5 in the implementation.

Two variations of the Gaussian kernel were tested. The Gaussian kernel is K(x; h, ω) = exp(−x2/2h2) if x ≤ ω and 0 if x > ω, where x is the distance, ω is the distance threshold equal to y(n̂i), and h is the bandwidth, currently the standard deviation of the local distance distribution. The high-dimensional kernel is K(x; h, ω, a, s, x̄) = exp(−(max[x−(x̄−as),0])2/2h2) if x ≤ ω and 0 if x > ω, which offsets distances closer to zero to avoid two issues in high-dimensional spaces: the distance between a point and itself being zero on the first iteration, and preventing very small values when distances are very large.

The algorithm was compared against the weighted adaptive mean shift algorithm of Ren et al. 2014 on nine datasets (Iris, Yeast, Steel, USPS, CTG, Letter, Image, Pen, Wave), with the same preprocessing of normalizing features to have zero mean and unit variance. The results show the algorithm obtains a higher Rand index than WAMS on seven of the nine datasets, and a higher Rand index than every published baseline (WAMS, k-means, EM, single-linkage) in the table on the same seven. The margins are uneven: four of the seven lie between 0.034 and 0.152, on Steel, CTG, Pen and Iris, while Yeast, Wave and Letter are won by 0.011, 0.007 and 0.004. The two exceptions are USPS and Image. The high-dimensional kernel often performs slightly worse than the Gaussian kernel, except on the USPS dataset, which has the highest number of dimensions by far.

The algorithm was also evaluated using datasets and benchmark results published by Gagolewski 2022 on eight datasets (Ecoli, Glass, Ionosphere, Sonar, Statlog, WDBC, Wine, Yeast), with preprocessing of removing constant columns, centering the data, scaling columns proportionally so total variance is 1, and adding a tiny amount of noise. The results were mixed, with the algorithm performing better on some datasets. One distinct advantage over the algorithms included in this benchmark is that it does not require the number of clusters as an input, while all other algorithms except ours need at least the number of clusters as a parameter. The number of clusters the algorithm produced is reported, and it recovers the number exactly on glass, produces fewer than the reference on ecoli, and produces more on the remaining six, by a wide margin on statlog (41 against 7) and yeast (25 against 10).

The maximum boundary is the one parameter of the cluster cardinality estimation that is neither scale invariant nor local: it is a rank expressed as a fraction of n, so it depends on the size of the whole dataset rather than on the neighborhood of a point. Moving it from 0.5n to 0.7n changes the Rand index by +0.040 on WDBC and by −0.089 on Glass; the eight absolute changes have a median of 0.027 and five of the eight exceed 0.01. The default 0.5n is also a prior on cluster size, asserting that no cluster contains more than half the data. The direction of the change is systematic and follows from what the parameter asserts: on the five datasets where the assertion holds, raising the boundary hurts on all five; on the three where it fails (ionosphere, sonar, WDBC, whose largest class covers 0.641, 0.534 and 0.627 of the sample), raising it helps on sonar and WDBC and does not on ionosphere.

The two-class rows (ionosphere, sonar, WDBC) should be read with caution, as the Rand index counts agreeing pairs and takes a large value under an uninformative partition; the one cluster column gives the size of that effect, and on ionosphere the algorithm scores below that floor at both boundaries.

The paper notes that the cardinality estimator remains a work in progress, with potential for significant improvement and broader applicability beyond clustering tasks. The proposed improvements include mode finding algorithmically rather than via fixed boundaries, using kernel density estimation with an appropriate bandwidth, and clearly defining the task and establishing robust evaluation criteria. The paper concludes that three parts of the algorithm fall outside the scale-invariant and local properties: the maximum boundary is a rank expressed as a fraction of the dataset size; the decision to discard a point’s estimate is taken against that boundary and therefore depends on n; and the mean shift loop uses a merge threshold and an absolute convergence tolerance rather than the local scale. Removing the maximum boundary would address the first two and is the improvement to make first.

The appendix provides the full algorithms (Cluster Size Estimation and Clustering), proofs that distances in high dimensions tend toward a normal distribution and that the distance between nearest and farthest neighbors tends toward a constant independent of dimension, and proofs that Euclidean distances from the mean in normal isotropic multivariate distributions follow a chi distribution with d degrees of freedom and scale parameter σ, and that interpoint distances between two points randomly sampled from N (µ, σ2Id) follow a chi distribution with d degrees of freedom and scale parameter √σ2.

Improvements for AI systems

Based on the paper, here are the specific improvements I can implement in an AI system:

  • Replace fixed-bandwidth kernel density estimation with the γ-function-based estimator (Eq. 2) that identifies local cluster boundaries via minima in the distance distribution

  • The estimator requires no length constant—it automatically adapts to data scale through the variance-to-squared-distance ratio

  • Implementation: For each point, compute ordered distances to all others, evaluate γ at each rank k, find the minimum within boundaries [5, n/2], and use that rank as the cluster cardinality estimate

  • Truncate the Gaussian kernel at the estimated cluster radius (ω = y(n̂)), ensuring points beyond the local cluster contribute exactly zero weight

  • This prevents distant points from dominating the weighted mean, especially in datasets with small clusters adjacent to large ones

  • The kernel bandwidth (h) is derived from the standard deviation of the local distance distribution, not a global parameter

  • Start with a small kernel window (minBoundary = 5 points) and linearly increase to the full estimated cardinality over the first 100 iterations

  • This counteracts positive bias in cardinality estimates for points far from cluster centers, preventing premature merging with neighboring clusters

  • For datasets with many dimensions (e.g., USPS at 256 features), use the offset kernel (Eq. 6) that shifts distances by (x̄ − 4s) before applying the Gaussian

  • This prevents the self-distance of zero from dominating the first iteration and avoids numerical underflow with large distances

  • Identify points whose cardinality estimate hits the maximum boundary (indicating unreliable estimates) and exclude them from mean shift

  • After mode finding, classify these points to the nearest mode using cluster-specific distance variance (s2) as a scaling factor

  • Cluster without specifying the number of clusters—unlike k-means, EM, spectral, or Birch, which all require this input

  • Handle clusters of vastly different sizes and densities (e.g., 25 points with σ=0.7 alongside 200 points with σ=2) without parameter tuning

  • Achieve higher Rand index than weighted adaptive mean shift (WAMS) on 7 of 9 benchmark datasets, with improvements up to 0.152 (Iris: 0.958 vs 0.806)

  • Outperform k-means, EM, and single-linkage on the same benchmarks

  • Scale invariance: Multiplying all data by any positive constant produces identical clustering results—no bandwidth or distance threshold needs manual selection

  • Locality: The γ function at rank k depends only on the k nearest distances; modifying distant points cannot perturb the local cluster boundary detection

  • Adaptivity: Each point uses parameters derived from its own neighborhood statistics, not global dataset properties

  • On the UCI benchmark (Gagolewski 2022), achieves Rand indices of 0.876 (Ecoli), 0.875 (Statlog), 0.760 (Yeast) without cluster count knowledge, competitive with or exceeding algorithms given the true cluster count

  • On high-dimensional data (USPS, 256 features), the high-dimensional kernel achieves 0.746 Rand index versus 0.901 for WAMS but without requiring the number of clusters

  • The cardinality estimator can be repurposed for outlier detection, anomaly detection, or any task requiring identification of local cluster boundaries without density estimation

  • Provides statistics (mean, variance, MSD) restricted to the estimated local cluster, which can inform downstream tasks like dimensionality reduction or visualization

Caveat: The system currently assumes no cluster exceeds 50% of the data (default maximum boundary). For datasets with a dominant class (e.g., ionosphere at 64% majority), performance degrades—this is a known limitation that could be addressed by making the boundary adaptive.

Abstract

This article presents an adaptive mean shift algorithm in which every parameter used at a point is derived from that point's own distance distribution. The distance distribution from a point to all others is used to estimate the cardinality of the local cluster by identifying a local minimum in the density of that distribution; the statistics of the identified subset then set the bandwidth and the kernel radius threshold applied at that point. The estimator built this way is scale invariant, since the gamma function it rests on is unchanged when the data is multiplied by a positive constant, so no length constant has to be chosen for the scale of the data. It is also local: gamma evaluated at rank k depends only on the k nearest distances, and the mean shift kernel is truncated at the estimated cluster radius, so data lying beyond that radius neither enters the estimate of the local cluster nor contributes to the weighted mean. This contrasts with kernel density estimation, which in its basic form measures density in a neighborhood of fixed size and needs a bandwidth chosen for the dataset as a whole. Our algorithm is competitive within the adaptive mean shift family: it obtains a higher Rand index than the weighted adaptive mean shift method of Ren et al. (2014) on seven of the nine datasets of that study, four of them by more than 0.03 and three by less than 0.012, and it performs competitively on a broader clustering benchmark, in both cases without being given the number of clusters.

Sources

Related papers