상세정보
학술지
Semidefinite Spectral Clustering
- 저자
- 김재환, 최승진
- 발행일
- 200611
- 출처
- Pattern Recognition, v.39 no.11, pp.2025-2035
- ISSN
- 0031-3203
- 출판사
- Elsevier
- 협약과제
- 06MC1700, 멀티코아 CPU 및 MPU기반 크롯플랫폼 게임기술 개발, 양광호
- 초록
- 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 제안 키워드
- Clustering method, Convex Optimization, Data clustering, Data sets, Edge weights, Eigen-decomposition, Graph laplacian, Multi-way, NP-Hard problem, Numerical experiments, Pattern recognition