TL;DR
This paper introduces "cluster ensembles," a framework for combining multiple existing clusterings of data without access to the original features. They propose a mutual information-based objective function and three efficient algorithms (CSPA, HGPA, MCLA) to achieve this, demonstrating their effectiveness in improving clustering quality, enabling distributed clustering, and enhancing robustness.
What Problem Does This Paper Address?
The paper tackles the challenge of combining multiple, potentially disparate, clusterings of a dataset into a single, consolidated clustering. This is particularly relevant in scenarios where the original data or clustering algorithms are inaccessible (knowledge reuse) or when data is distributed across different locations. Traditional ensemble methods for classification and regression are well-established, but combining clusterings presents unique challenges due to the symbolic nature of cluster labels and the need to establish correspondences between clusters from different sources. The authors aim to provide a robust and efficient solution for this "cluster ensemble problem."
Methods
The core of the paper lies in its novel approach to defining and solving the cluster ensemble problem:
- Objective Function: They propose maximizing the Average Normalized Mutual Information (ANMI) between the consensus clustering and the individual input clusterings. This objective function quantifies how well a combined clustering "agrees" with the existing ones, using a normalized mutual information metric.
- Hypergraph Representation: A key step for their algorithms is transforming the set of clusterings into a hypergraph representation. Each cluster from an individual partitioning becomes a hyperedge, and the vertices represent the objects.
- Consensus Algorithms: Three efficient algorithms are introduced:
- Cluster-based Similarity Partitioning Algorithm (CSPA): This method first computes pairwise similarity between objects based on how often they appear together in the input clusterings. This similarity matrix is then used to recluster the objects.
- HyperGraph Partitioning Algorithm (HGPA): This approach directly partitions the hypergraph, aiming to minimize the number of hyperedges cut while maintaining balanced partitions. It's described as a direct approach to approximating the ANMI objective.
- Meta-CLustering Algorithm (MCLA): This algorithm views the problem as a cluster correspondence problem. It groups similar clusters (meta-clusters) and then assigns objects to the meta-cluster they belong to most strongly.
A "supra-consensus" function is also proposed, which automatically selects the best performing consensus algorithm for a given dataset.
Datasets
The authors evaluate their methods on two artificial and two real-world datasets:
- 2D2K: An artificial dataset with 500 points in two 2D Gaussian clusters.
- 8D5K: An artificial dataset with 1000 points from five 8D Gaussian clusters.
- PENDIG: A real-world dataset for pen-based handwritten digit recognition, containing 7494 training and 3498 test cases with 16 features.
- YAHOO: A real-world dataset for text clustering, derived from Yahoo! news categories, with 21839 documents and 2903 features.
Key Insights and Ideas
- Knowledge Reuse without Features: The most significant insight is the ability to combine clusterings effectively using only the cluster labels, without needing access to the original data features or algorithms. This opens up new possibilities for leveraging existing, potentially proprietary, clustering results.
- Mutual Information as a Unifying Objective: Using normalized mutual information as the objective function provides a principled way to measure agreement between clusterings, even when they have different numbers of clusters or different interpretations.
- Diverse Algorithms for Different Scenarios: The paper highlights that no single consensus algorithm is universally best. MCLA excels in low noise/diversity, while CSPA and HGPA perform better in high noise/diversity settings, suggesting the utility of having multiple options.
- Robustness through Ensembling: Cluster ensembles can significantly improve robustness, especially in scenarios where individual clusterers might be unreliable or when dealing with noisy data. The supra-consensus function further enhances this by selecting the best performing ensemble.
- Enabling Distributed Clustering: The framework is shown to be effective for distributed scenarios where data cannot be centralized, allowing for efficient combination of clusterings from different sources.
Key Results
- Improved Quality: In Feature-Distributed Clustering (FDC) experiments, the consensus clustering consistently outperformed individual subspace clusterings, often by a significant margin. For example, in the YAHOO dataset, combining 20 clusterings yielded a quality 156% higher than the average individual clustering.
- Robustness: In Robust Centralized Clustering (RCC) experiments, the consensus function was shown to be robust to the inclusion of poor or distractive clusterings, achieving significantly better results than individual algorithms or random clustering. For the YAHOO dataset, RCC's average quality was 15% higher than the average of other algorithms.
- Efficiency: The proposed consensus algorithms (HGPA, MCLA) are significantly more efficient than a greedy optimization approach, with HGPA being the fastest. This efficiency is crucial for handling large datasets.
- Speedup in Distributed Settings: In Object-Distributed Clustering (ODC), the framework demonstrated substantial speedups (e.g., 64-fold for 2D2K) while retaining a high percentage of the clustering quality.
Limitations and Future Work
- Computational Complexity: While CSPA is O(n²kr), HGPA and MCLA are more efficient (O(nkr) and O(nk²r²), respectively). However, for very large datasets, even these can be computationally intensive. The greedy approach is noted as being intractable for large datasets.
- Hypergraph Partitioning Limitations: HGPA's reliance on standard hypergraph partitioning means it has no provision for partially cut hyperedges, which can be problematic when cluster sizes are imbalanced.
- Varying Number of Clusters: While the framework allows for clusterers to provide different numbers of clusters (k), most experiments used a fixed k. Further investigation is needed to understand the robustness of the consensus clustering to varying k values.
- Future Work: The authors suggest theoretical analysis of the ANMI objective, exploration of greedy optimization schemes, understanding the biases of the proposed algorithms, and extending application scenarios to hybrid FDC, ODC, and RCC settings. They also highlight the potential for cluster ensembles in federated data mining systems.
Summary updated