Research map / Learning theory and algorithms / Clustering
Average Sensitivity of Hierarchical $k$-Median Clustering
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a low-average-sensitivity hierarchical k-median algorithm by combining the CLNSS 2-RHST greedy method with the exponential mechanism, with provable sensitivity O(k ln n / ε) and approximation guarantees, and shows single linkage and deterministic CLNSS have Ω(n) sensitivity.
Problem
Hierarchical k-median clustering in Euclidean space is sensitive to random point deletions, and it is unknown whether CLNSS and other hierarchical clustering algorithms are stable under the average sensitivity measure.
Approach
Replace the greedy center selection in the CLNSS algorithm (run on a randomly shifted 2-RHST) with exponential-mechanism sampling of centers, with the temperature tied to the current tree cost, to trade a small approximation loss for low average sensitivity.
Key results
- The proposed algorithm has average sensitivity O(k ln n / ε) and expected cost O(d log Λ (1+ε)^k) times OPT, with running time O(dn log Λ + n^3).
- Single linkage and the deterministic CLNSS variant are shown to have average sensitivity Ω(n) on constructed worst-case instances.
- Experiments show the proposed algorithm, with k=4, has lower average sensitivity than linkage methods and CLNSS on most real datasets, with sensitivity decreasing as ε increases, while single linkage shows lower sensitivity on some real data with strong cluster structure.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add exponential-mechanism center selection to CLNSS | Hierarchical k-median clustering · Hierarchical Euclidean k-median | average sensitivity: CLNSS: at least Ω(n); proposed algorithm: O(k ln n/ε) | Helped |
| Increase ε | Proposed algorithm · Synthetic regression dataset (500 points) | average sensitivity | Helped |
| Increase ε | Proposed algorithm · Real-world datasets | average sensitivity | Helped |
| Use the proposed algorithm instead of linkage-based algorithms and CLNSS | Hierarchical clustering · Real-world datasets, k=4 | average sensitivity | Helped |
| Use the proposed algorithm instead of Ward's method or complete linkage | Hierarchical clustering · Real-world datasets | k-median cost | Hurt |
| Use the proposed algorithm instead of average linkage, single linkage, or CLNSS | Hierarchical clustering · Real-world datasets | k-median cost | Helped |
Surprising findings
- Single linkage shows low average sensitivity on real-world datasets with strong cluster structure, despite its Ω(n) worst-case bound.
- Single linkage produces significantly higher k-median costs than other methods, offsetting its robustness.
Limitations
- Worst-case average sensitivity of single linkage and deterministic CLNSS is Ω(n), so stability depends on data structure.
- Experiments estimate an upper bound on average sensitivity using a fixed random seed rather than the exact quantity.
- The choice of ε trades off approximation ratio against sensitivity and has no universal setting.
Experimental setup
Datasets: Iris Wine Wholesale Diabetes WDBC Digits Yeast scikit-learn synthetic regression dataset
Benchmarks: Iris Wine Wholesale Diabetes WDBC Digits Yeast synthetic line and RHST datasets
Metrics: average sensitivity (expected symmetric difference under del k-median cost
Baselines: CLNSS algorithm single linkage complete linkage average linkage Ward's method
Builds on: CLNSS algorithm exponential mechanism average sensitivity 2-RHST
Closest papers by meaning
- Parallel and Efficient Hierarchical k-Median Clustering (NeurIPS 2021 · similarity 0.92)
- Ultrametric Cluster Hierarchies: I Want ‘em All! (NeurIPS 2025 · similarity 0.88)
- Dynamic Algorithm for Explainable $k$-medians Clustering under $\ell_p$ Norm (NeurIPS 2025 · similarity 0.88)
- Learning-Augmented Algorithms for $k$-median via Online Learning (NeurIPS 2025 · similarity 0.88)
- Efficient Constrained K-center Clustering with Background Knowledge (AAAI 2024 · similarity 0.88)
- Expected Probabilistic Hierarchies (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.