Support vector clustering through proximity graph modelling

Abstract

Support vector machines (SVMs) have been widely adopted for classification, regression and novelty detection. Recent studies (A. Ben-Hur et al., 2001) proposed to employ them for cluster analysis too. The basis of this support vector clustering (SVC) is density estimation through SVM training. SVC is a boundary-based clustering method, where the support information is used to construct cluster boundaries. Despite its ability to deal with outliers, to handle high dimensional data and arbitrary boundaries in data space, there are two problems in the process of cluster labelling. The first problem is its low efficiency when the number of free support vectors increases. The other problem is that it sometimes produces false negatives. We propose a robust cluster assignment method that harvests clustering results efficiently. Our method uses proximity graphs to model the proximity structure of the data. We experimentally analyze and illustrate the performance of this new approach.