On Robustness of Kernel Clustering

Clustering is an important problem which is prevalent in a variety of real world problems. One of the first and widely applied clustering algorithms is k-means, which was named by James MacQueen [15], but was proposed by Hugo Steinhaus [23] even before. Despite being half a century old, k-means has been widely used and analyzed under various settings. One major drawback of k-means is its incapability to separate clusters that are non-linearly separated. This can be alleviated by mapping the data to a high dimensional feature space and do clustering on top of the feature space [21, 9, 12], which is generally called kernel-based methods. For instance, the widely-used spectral clustering [22, 17] is an algorithm to calculate top eigenvectors of a kernel matrix of affinities, followed by a k-means on the top r eigenvectors. The consistency of spectral clustering is analyzed by [25].