(2007)A survey of kernel and spectral methods for clustering书籍.pdf

Pattern Recognition 41 (2008) 176–190 /locate/pr A survey of kernel and spectral methods for clustering a ,∗ b a a Maurizio Filippone , Francesco Camastra , Francesco Masulli , Stefano Rovetta aDepartment of Computer and Information Science, University of Genova, and CNISM, Via Dodecaneso 35, I 16146 Genova, Italy bDepartment of Applied Science, University of Naples Parthenope, Via A. De Gasperi 5, I 80133 Napoli, Italy Received 19 October 2006; received in revised form 30 April 2007; accepted 29 May 2007 Abstract Clustering algorithms are a useful tool to explore data structures and have been employed in many disciplines. The focus of this paper is the partitioning clustering problem with a special interest in two recent approaches: kernel and spectral methods. The aim of this paper is to present a survey of kernel and spectral clustering methods, two approaches able to produce nonlinear separating hypersurfaces between clusters. The presented kernel clustering methods are the kernel version of many classical clustering algorithms, e.g., K-means, SOM and neural gas. Spectral clustering arise from concepts in spectral graph theory and the clustering problem is configured as a graph cut problem where an appropriate objective function has to be optimized. An explicit proof of the fact that these two paradigms have the same objective is reported since it has been proven that these two seemingly different approaches have the same mathematical foundation. Besides, fuzzy kernel clus