A fast training algorithm for SVM via clustering technique and Gabriel graph

The training time for Support vector machine (SVM) depends largely on the size of the training set, which makes it impractical for large data sets. This paper presents a new method to reduce the size by combining two supplementary algorithms. The training data is partitioned into several pair-wise disjoint clusters by using k-means clustering algorithm. Then, the representatives of these clusters can be edited by Gabriel graph algorithm, based on which we can approximately identify the support vectors and nonsupport vectors. After de-clustering the marginal boundary clusters represented by support vectors and deleting the internal clusters represented by non-support vectors, the number of training data can be significantly reduced, thereby speeding up the training process. The proposed method was tested on both the artificial data and real data. Experiment results show that replacing the training set with the edited set obtained from Gabriel graph algorithm and k-means clustering technique as the training set, significantly reduces the training time for SVM, yet the classification accuracy remains nearly undegraded.