A Robust Convex Formulation for Ensemble Clustering

Junning Gao, Makoto Yamada, Samuel Kaski, Hiroshi Mamitsuka, Shanfeng Zhu

Introduction

Clustering is a cornerstone of data science, yet no single algorithm—be it k-means, spectral clustering, or hierarchical methods—is universally optimal for every dataset. Ensemble clustering addresses this by aggregating multiple clustering results into a single, stable consensus. However, the quality of this consensus is often compromised by "noisy" or anomalous input partitions that fail to capture meaningful patterns.

Existing state-of-the-art methods, such as Weighted Consensus Clustering (WCC) and Instance-wise weighted Non-negative Matrix Factorization (INA), attempt to mitigate this. Yet, they rely on non-convex optimization, making them highly sensitive to initialization and prone to getting trapped in local optima. To overcome these hurdles, researchers have introduced Robust Convex Ensemble Clustering (RCEC), a framework that guarantees a globally optimal solution while systematically filtering out noise.

Methodology: Convexity and Regularization

RCEC reformulates ensemble clustering as a convex regularization problem. The core objective function balances three critical components:

  1. Fidelity: Ensuring the consensus remains faithful to the input cluster assignment matrix $L$.
  2. Low-Rank Structure: Utilizing the nuclear norm ($\|X\|_*$) to encourage a clear, low-dimensional structure in the learned consensus matrix.
  3. Anomalous Cluster Filtering: The "secret sauce" of RCEC is the application of the $\ell_{2,1}$ group-norm. This enforces column-wise sparsity, effectively shrinking the weights of noisy or anomalous clusters to zero.
Illustration of the ensemble clustering input matrix $L$, highlighting normal versus anomalous clusters.

By adopting a convex formulation, RCEC eliminates the need for "lucky" initializations. The authors provide an efficient iterative multiplicative updating rule that ensures rapid convergence, typically within 20 iterations.

Experimental Evaluation

The authors evaluated RCEC against several benchmarks, including synthetic data designed to test robustness, text datasets (Tr11, K1b), and the ORL face recognition image dataset.

Key Results

  • Robustness to Noise: In synthetic experiments, RCEC demonstrated remarkable resilience. As the number of "extremely anomalous" partitions increased, the performance of traditional methods like HBGF and NMFC dropped significantly. In contrast, RCEC maintained a high Normalized Mutual Information (NMI) score.
  • Superior Accuracy: On real-world datasets, RCEC consistently outperformed competitors such as ECMC and INA in terms of NMI.
  • Efficiency and Stability: Unlike non-convex methods that require multiple runs to find a stable result, RCEC's convexity means it only needs to be run once to find the global optimum, making it faster in practical applications.
Comparison of NMI performance as the number of anomalous partitions increases. The proposed RCEC method maintains high performance compared to existing techniques.

Conclusion and Future Directions

RCEC represents a significant step forward in making ensemble clustering more robust and reliable. By leveraging convex optimization and $\ell_{2,1}$ regularization, it provides a principled way to handle low-quality input data.

However, some challenges remain. The model's performance depends on two hyperparameters ($\lambda$ and $\beta$) that require tuning. Additionally, while efficient for moderate datasets, the $O(K^3 + NK^2)$ complexity suggests a need for further optimization in extremely large-scale ensembles. Future work may also explore extending the model to handle probabilistic or "fuzzy" cluster assignments rather than strictly binary inputs.

Summary updated

Abstract

We formulate ensemble clustering as a regularization problem over nuclear norm and cluster-wise group norm, and present an efficient optimization algorithm, which we call Robust Convex Ensemble Clustering (RCEC). A key feature of RCEC allows to remove anomalous cluster assignments obtained from component clustering methods by using the group-norm regularization. Moreover, the proposed method is convex and can find the globally optimal solution. We first showed that using synthetic data experiments, RCEC could learn stable cluster assignments from the input matrix including anomalous clusters. We then showed that RCEC outperformed state-of-the-art ensemble clustering methods by using real-world data sets.
BibTeX
@inproceedings{gao2016robust,
  author = {Junning Gao and Makoto Yamada and Samuel Kaski and Hiroshi Mamitsuka and Shanfeng Zhu},
  title = {{A Robust Convex Formulation for Ensemble Clustering}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure