Power to the Points: Local Certificates for Clusterings

on YouTube ↗37m

" summary

Proposes local, per-point confidence by inserting a query into the clustering’s Voronoi/power diagram and measuring the fractional area it steals to produce an affinity vector (simplex of weights). Computes this approximately by uniform sampling of the cell using hit-and-run and by projecting to the K‑dimensional cluster subspace, needing about O(1/ε^2) samples and running poly(K,1/ε) time (milliseconds per query in practice). Correlates strongly with EM soft assignments, improves active subsampling and model selection on digit and synthetic experiments.

AI-written summary · about

" chapters (20)

1. 0:00Intro
2. 1:44Data Mining Pipeline
3. 4:14Local Validation in Classification
4. 6:34Clustering Data
5. 7:42Validating Clusterings
6. 10:37Outlier Detection vs Local Validation
7. 15:07Regions can be shielded
8. 15:59Voronoi property of clusterings
9. 16:58Voronoi Regions of Influence
10. 20:32Incorporating cluster density
11. 22:27Generalizing to other distance spaces
12. 23:01Computing affinity vectors
13. 24:18Approximate Affinities
14. 25:24Volume Sampling
15. 27:10Dimensionality Reduction
16. 28:10Algorithm Summary
17. 29:23Clustering digits
18. 30:51Accelerating Clustering
19. 32:20Model Selection
20. 33:54Questions

" related talks

• 40mMonte Carlo Approximation Certificates for K-Means ClusteringDustin Mixon · Sublinear Algorithms and Nearest-Neighbor Search
• 34mParallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor SearchJulian Shun · Managing Parallelism 2025
• 25mConstrained Rank Aggregation and Correlation ClusteringOlgica Milenkovic · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 40mClustering Under Perturbation ResilienceColin White · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 47mAssessing the quality of a clusteringChristian Hennig · PyData London 2016
• 53mWhen Does Clustering Become Easy, and Should We Care About Other Cases?Shai Ben-David · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 47mCrowdsourcing for Clustering: Algorithms and Information-Theoretic Lower BoundsBabak Hassibi · Real-Time Decision Making
• 35mLocal Statistics, Semidefinite Programming, and Community Detection IISidhanth Mohanty · Computational Phase Transitions (Simons Institute, 2020)