Research map / Learning theory and algorithms / Clustering
k-HyperEdge Medoids for Clustering Ensemble
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.
Formulates clustering ensemble as a k-HyperEdge Medoids discovery problem and proposes CEHM, which initializes hyperedges via k-medoids on base clusters, then diffuses and adjusts them with a hyperedge loss, evaluated on 20 datasets against nine ensemble methods.
Problem
Clustering ensembles face a trade-off: clustering-view methods are efficient but sensitive to unreliable base clusters, while sample-view methods (co-association based) perform well but require costly pairwise sample relations, typically at least O(n^2).
Approach
Treat each base cluster as a hyperedge and select k non-overlapping hyperedge medoids: k-medoids on base clusters gives the initial hyperedges (clustering view), which are then diffused to cover all samples and adjusted by assigning each sample to the hyperedge with highest belonging degree, reducing a hyperedge loss (sample view) without building a pairwise matrix.
Key results
- CEHM attains the highest average NMI on most of the 20 datasets versus nine ensemble baselines, e.g. NMI 0.5994 vs 0.4931 for the best baseline on statlog-shuttle and 0.6994 vs 0.6482 on ecoli (0.7007 vs 0.6493 for ECPCS-MC).
- CEHM has the lowest running time among the compared methods except U-SENC, which is designed for large-scale data via downsampling.
- The hyperedge loss decreases monotonically during the adjustment step, converging in no more than 30 iterations on the tested datasets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace the strongest listed baseline with CEHM | clustering ensemble · iris | NMI: 0.7128 -> 0.7456 | Helped |
| Replace the strongest listed baseline with CEHM | clustering ensemble · wine | NMI: 0.8961 -> 0.9039 | Helped |
| Replace the strongest listed baseline with CEHM | clustering ensemble · seeds | NMI: 0.7316 -> 0.7320 | Helped |
| Replace the strongest listed baseline with CEHM | clustering ensemble · heart | NMI: 0.3054 -> 0.3072 | Helped |
| Replace the strongest listed baseline with CEHM | clustering ensemble · ecoli | NMI: 0.6493 -> 0.7007 | Helped |
| Replace the strongest listed baseline with CEHM | clustering ensemble · energy | NMI: 0.5853 -> 0.5853 | No clear effect |
| Replace the strongest listed baseline with CEHM | clustering ensemble · mushroom | NMI: 0.2486 -> 0.3359 | Helped |
| Use CEHM instead of U-SENC | clustering ensemble · statlog-shuttle | NMI: 0.4931 -> 0.5994 | Helped |
| Replace the strongest listed baseline with CEHM | clustering ensemble · PenDigits | NMI: 0.7550 -> 0.7567 | Helped |
| Replace the strongest listed baseline with CEHM | clustering ensemble · USPS | NMI: 0.5613 -> 0.5818 | Helped |
Surprising findings
- Several baselines (EC-CMS, PTGP, U-SENC, DREC, PTA, Voting) run out of memory on the largest datasets, while CEHM does not.
Limitations
- Theoretical guarantees rely on assumptions (g-approximate initialization, bounded density ratios) that may not hold in practice.
- Cluster weights are set equally and not studied.
- Experiments use base clusterings generated by k-means only.
Experimental setup
Datasets: iris wine seeds heart soybean-train ecoli dermatology low-res-spect breast-cancer-wisc-diag energy lbp-riu-gris semeion
Benchmarks: iris wine seeds heart soybean-train ecoli dermatology low-res-spect breast-cancer-wisc-diag energy lbp-riu-gris semeion
Metrics: NMI ARI running time
Baselines: U-SENC DREC EC-CMS PTGP ECPCS-MC PTA WCT WTQ Voting
Builds on: k-medoids co-association matrix evidence accumulation clustering hypergraph partitioning
Closest papers by meaning
- Generalization Performance of Ensemble Clustering: From Theory to Algorithm (ICML 2025 · similarity 0.85)
- GoT: a Growing Tree Model for Clustering Ensemble (AAAI 2021 · similarity 0.85)
- Global Optimal K-Medoids Clustering of One Million Samples (NeurIPS 2022 · similarity 0.85)
- Enhancing Ensemble Clustering with Adaptive High-Order Topological Weights (AAAI 2024 · similarity 0.82)
- Average Sensitivity of Hierarchical $k$-Median Clustering (ICML 2025 · similarity 0.82)
- Ultrametric Cluster Hierarchies: I Want ‘em All! (NeurIPS 2025 · similarity 0.82)
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.