tailieunhanh - A survey on graph partitioning approach to spectral clustering

Cluster analysis is an unsupervised technique of grouping related objects without considering their label or class. The objects belonging to the same cluster are relatively more homogeneous in comparison with other clusters. The application of cluster analysis is in areas like gene expression analysis, galaxy formation, natural language processing and image segmentation etc. | Journal of Computer Science and Cybernetics, , (2015), 31–42 DOI: A SURVEY ON GRAPH PARTITIONING APPROACH TO SPECTRAL CLUSTERING SUBHANSHU GOYAL1,a , SUSHIL KUMAR1,b , M. A. ZAVERI2 , and 1 Department of Applied Mathematics & Humanities, S. V. National Institute of Technology, Surat, Gujarat 395007, India, a subhanshugoyal@; b ; c ajayshukla2@ 2 Department of Computer Science & Engineering, S. V. National Institute of Technology, Surat, Gujarat 395007, India mazaveri@ Abstract. Cluster analysis is an unsupervised technique of grouping related objects without considering their label or class. The objects belonging to the same cluster are relatively more homogeneous in comparison with other clusters. The application of cluster analysis is in areas like gene expression analysis, galaxy formation, natural language processing and image segmentation etc. The clustering problem can be formulated as a graph cut problem where a suitable objective function has to be optimized. This study uses different graph cluster formulations based on graph cut and partitioning problems. A special class of graph clustering algorithm known as spectral clustering algorithms is used for the study. Two widely used spectral clustering algorithms are applied to explaining solution to these problems. These algorithms are generally based on the Eigen-decomposition of Laplacian matrices of either weighted or non-weighted graphs. Keywords. Eigenvectors, graph cut, laplacian matrix, normalized cut, spectral clustering 1. INTRODUCTION This survey presented a framework of spectral clustering, a method which utilizes an eigenvector from the so-called data similarity matrix. Computing eigenvectors of such matrices could be potentially a very expensive operation. Thus, faster approximation algorithms for spectral clustering have appeared in the literature. This survey tries to summarize and