Semidefinite spectral clustering
SCIE
SCOPUS
- Title
- Semidefinite spectral clustering
- Authors
- Kim, J; Choi, S
- Date Issued
- 2006-11
- Publisher
- PERGAMON-ELSEVIER SCIENCE LTD
- 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 peformed 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 SDR Numerical experiments with several data sets, demonstrate the useful behavior of our semidefinite spectral clustering, compared to existing spectral clustering methods. (c) 2006 Pattern Recognition Society. Published by Elsevier Ltd. All rights reserved.
- Keywords
- clustering; convex optimization; multi-way graph equipartitioning; semidefinite programming; spectral clustering; MATRICES
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/23848
- DOI
- 10.1016/j.patcog.2006.05.021
- ISSN
- 0031-3203
- Article Type
- Article
- Citation
- PATTERN RECOGNITION, vol. 39, no. 11, page. 2025 - 2035, 2006-11
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.