Introduction
Clustering is a fundamental yet challenging task in unsupervised learning. Because there is no ground truth, different algorithms or parameter settings often yield inconsistent results. Consensus clustering (or ensemble clustering) addresses this by aggregating multiple "basic partitions" into a single, robust final result. Historically, the field has been divided between heuristic methods and objective-function-based approaches. This paper introduces a unifying "embedding perspective" that bridges these gaps and provides a roadmap for extending consensus clustering to broader machine learning tasks.
A Unified Embedding Perspective
The authors propose a three-step framework that reframes consensus clustering as a representation learning process:
- Information Summary ($\Gamma(\Pi) \to S$): Multiple basic partitions are converted into a co-association matrix ($S$). This matrix serves as a similarity graph where entries represent the frequency with which pairs of points are clustered together.
- Embedding ($S \to Q$): The co-association matrix is decomposed into a representation matrix ($Q$). This "embedding" step maps the data into a new space that captures the consensus structure.
- Partitioning ($Q \to \pi$): A final clustering algorithm, such as K-means, is applied to the embedding $Q$ to produce the final consensus partition.
Theoretical Unification through Utility Functions
By viewing consensus clustering through this lens, the authors show that diverse methods—ranging from binary coding to spectral decomposition—share a common underlying logic. For instance, K-means-based Consensus Clustering (KCC) can be seen as clustering high-dimensional binary embeddings. Spectral Ensemble Clustering (SEC) is shown to be equivalent to performing weighted K-means on a specific graph embedding, offering a significant computational advantage over traditional $O(n^3)$ spectral methods.
The table above demonstrates how different utility functions (e.g., $U_c$ for K-means, $U_H$ for entropy-based) can be decomposed into components that fit the embedding framework, allowing for a standardized comparison of objective-based methods.
Key Insights: Efficiency and Regularization
One of the most significant insights is that the co-association matrix acts as a "robust graph" that captures data structure more effectively than simple distance-based graphs. Furthermore, the paper highlights the efficiency of weighted K-means as a proxy for spectral decomposition, enabling scalable consensus clustering on large datasets.
Beyond simple clustering, the utility functions used in this framework can act as powerful regularizers. In Domain Adaptation, the consensus structure of source data can guide the clustering of unlabeled target data, improving performance in cross-domain tasks.
Extensions and Applications
The embedding perspective allows consensus clustering to solve non-traditional problems:
- Feature Selection: Consensus labels can serve as "pseudo-labels" to identify the most informative raw features.
- Outlier Detection: By using "Holoentropy" in the partition space, researchers can identify data points that deviate from the consensus, which is often more effective than searching for outliers in the original high-dimensional space.
Future Directions
While the embedding perspective provides a strong theoretical foundation, several challenges remain. Current methods typically follow a two-stage "generate-then-fuse" approach; moving toward end-to-end learnable models could further optimize performance. Additionally, improving the interpretability of clusters formed in the embedding space and establishing more rigorous theoretical bounds for convergence are key areas for future research.
Summary updated