Research map / Learning theory and algorithms / Clustering
Generalization Performance of Ensemble Clustering: From Theory to Algorithm
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.
Derives generalization error, excess risk and consistency bounds for ensemble clustering (O(sqrt(log n/m)+1/sqrt(n))), then turns the bias-diversity decomposition into a weighted CA-matrix algorithm (GPEC) optimized by reduced gradient descent that beats SOTA ensemble clustering methods on 10 datasets.
Problem
Ensemble clustering is widely used but lacks theoretical analysis of generalization error, excess risk, and consistency; prior theory covers only single clusterings or gives O(1/sqrt(n)) without modeling base clustering randomness.
Approach
Treats base clusterings as random variables, derives generalization/excess-risk bounds and consistency conditions (m, n to infinity with m >> log n), then decomposes the finite-ensemble loss into bias and diversity terms that motivate learned base-clustering weights and high-confidence CA elements.
Key results
- Proposed method averages NMI 29.6% in the main table, exceeding the second-best method by 6.1% NMI, 7.3% ARI and 6.0% Purity on average across 10 datasets.
- Theory gives generalization error and excess risk bounds O(sqrt(log n/m)+1/sqrt(n)); consistency holds when m,n -> infinity and m >> log n.
- Excess-risk experiments on WFRN show divergence for m=log log n, constant gap for m=log n, and convergence for m=sqrt(n).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed ensemble clustering algorithm instead of comparison methods | Ensemble clustering · 10 datasets | NMI: 6.1% | Helped |
| Use the proposed ensemble clustering algorithm instead of comparison methods | Ensemble clustering · 10 datasets | ARI: 7.3% | Helped |
| Use the proposed ensemble clustering algorithm instead of comparison methods | Ensemble clustering · 10 datasets | Purity: 6.0% | Helped |
| Set α =0.1 instead of the default setting (ablation) | Proposed ensemble clustering · 10 datasets (average) | NMI: 29.6 -> 28.0 | Hurt |
| Optimize both bias and diversity rather than diversity alone | Clustering weight learning · Clustering weight analysis | NMI: 65.3 -> 71.9 | Helped |
| Optimize both bias and diversity rather than diversity alone | Clustering weight learning · Clustering weight analysis | ARI: 66.2 -> 72.4 | Helped |
| Optimize both bias and diversity rather than diversity alone | Clustering weight learning · Clustering weight analysis | Purity: 85.9 -> 90.2 | Helped |
| Set the number of base clusterings to m=log log n | Ensemble clustering · WFRN | excess risk: 1.9 | No clear effect |
| Set the number of base clusterings to m=log n | Ensemble clustering · WFRN | excess risk: 1.85 | Helped |
| Set the number of base clusterings to m=√n | Ensemble clustering · WFRN | excess risk: approximately 1.7 | Helped |
Surprising findings
- Maximizing diversity alone can assign higher weights to poorer base clusterings, dragging down consensus performance (Remark 3), so bias must be minimized jointly.
Limitations
- Necessary conditions for consistency are not addressed.
- Tightness of convergence rates for generalization error and excess risk is not established.
- The derived algorithm is only one instance of the framework.
Experimental setup
Datasets: 10 real-world clustering datasets (D1 Phishing, WFRN, among others)
Benchmarks: 10 clustering datasets (D1-D10) WFRN
Metrics: NMI ARI Purity
Baselines: CEAM CEs^2L CEs^2Q LWEA NWCA ECCMS MKKM SMKKM SEC
Builds on: co-association matrix weighted kernel k-means MKKM SimpleMKKM NWCA
Closest papers by meaning
- Simultaneous Clustering and Ensemble (AAAI 2017 · similarity 0.89)
- GoT: a Growing Tree Model for Clustering Ensemble (AAAI 2021 · similarity 0.89)
- An Evaluative Measure of Clustering Methods Incorporating Hyperparameter Sensitivity (AAAI 2022 · similarity 0.89)
- Learning Mixtures of Gaussian Processes through Random Projection (ICML 2024 · similarity 0.86)
- Enhancing Ensemble Clustering with Adaptive High-Order Topological Weights (AAAI 2024 · similarity 0.86)
- Achieving Optimal Clustering in Gaussian Mixture Models with Anisotropic Covariance Structures (NeurIPS 2024 · similarity 0.86)
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.