BROWSE
Detail
Journal Article
Semidefinite Spectral Clustering
Cited 3 time in 
Share 
Share
- Authors
- Jae Hwan Kim, Seung Jin Choi
- Issue Date
- 2006-11
- Citation
- Pattern Recognition, v.39, no.11, pp.2025-2035
- ISSN
- 0031-3203
- Publisher
- Elsevier
- Language
- English
- Type
- Journal Article
- Abstract
- Multi-way partitioning of an undirected weighted graph where pairwise similarities are assigned as edge weights, provides an important tool for data clustering, but is an NP-hard problem. Spectral relaxation is a popular way of relaxation, leading to spectral clustering where the clustering is performed by the eigen-decomposition of the (normalized) graph Laplacian. On the other hand, semidefinite relaxation, is an alternative way of relaxing a combinatorial optimization, leading to a convex optimization. In this paper we employ a semidefinite programming (SDP) approach to the graph equipartitioning for clustering, where sufficient conditions for strong duality hold. The method is referred to as semidefinite spectral clustering, where the clustering is based on the eigen-decomposition of the optimal feasible matrix computed by SDP. Numerical experiments with several data sets, demonstrate the useful behavior of our semidefinite spectral clustering, compared to existing spectral clustering methods. © 2006 Pattern Recognition Society.
- KSP Keywords
- Clustering method, Convex Optimization, Data clustering, Data sets, Edge weights, Eigen-decomposition, Graph laplacian, Multi-way, NP-Hard problem, Numerical experiments, Pattern recognition