Multiclass Spectral Clustering
- Stella X. YU and Jianbo SHI
International Conference on Computer Vision (ICCV'01), 2003.
We propose a principled account on multiclass spectral clustering.
Given a discrete clustering formulation, we first solve a relaxed
continuous optimization problem by eigendecomposition. We clarify
the role of eigenvectors as a generator of all optimal solutions.
We then solve an optimal discretization problem, which finds a
nearly global-optimal discrete solution closest to the continuous
optima. Our method is robust to random initialization and converges
faster than other clustering methods. Flexible initialization also
allows us to obtain nearly optimal solutions with special
requirements. Extensive experiments on real image segmentation
clustering, spectral graph partitioning, kmeans, image segmentation