Ensemble clustering using semidefinite programming with applications
Open Access
- 22 December 2009
- journal article
- research article
- Published by Springer Nature in Machine Learning
- Vol. 79 (1-2) , 177-200
Abstract
In this paper, we study the ensemble clustering problem, where the input is in the form of multiple clustering solutions. The goal of ensemble clustering algorithms is to aggregate the solutions into one solution that maximizes the agreement in the input ensemble. We obtain several new results for this problem. Specifically, we show that the notion of agreement under such circumstances can be better captured using a 2D string encoding rather than a voting strategy, which is common among existing approaches. Our optimization proceeds by first constructing a non-linear objective function which is then transformed into a 0-1 Semidefinite program (SDP) using novel convexification techniques. This model can be subsequently relaxed to a polynomial time solvable SDP. In addition to the theoretical contributions, our experimental results on standard machine learning and synthetic datasets show that this approach leads to improvements not only in terms of the proposed agreement measure but also the existing agreement measures based on voting strategies. In addition, we identify several new application scenarios for this problem. These include combining multiple image segmentations and generating tissue maps from multiple-channel Diffusion Tensor brain images to identify the underlying structure of the brain.Keywords
This publication has 38 references indexed in Scilit:
- Ensemble clustering using semidefinite programming with applicationsMachine Learning, 2009
- Brain tissue segmentation based on DTI dataNeuroImage, 2007
- Multi-classifier framework for atlas-based image segmentationPattern Recognition Letters, 2005
- Simultaneous Truth and Performance Level Estimation (STAPLE): An Algorithm for the Validation of Image SegmentationIEEE Transactions on Medical Imaging, 2004
- Distance measures for PCA-based face recognitionPattern Recognition Letters, 2004
- Fast approximate energy minimization via graph cutsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2001
- Normalized cuts and image segmentationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2000
- Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric conesOptimization Methods and Software, 1999
- SDPT3 — A Matlab software package for semidefinite programming, Version 1.3Optimization Methods and Software, 1999
- An Algorithm for Euclidean Sum of Squares ClassificationBiometrics, 1977