Kernel Bisecting k-means clustering for SVM training sample reduction

This paper presents a new algorithm named kernel bisecting k-means and sample removal (KBK-SR) as a sampling preprocessing for SVM training to improve the scalability. The novel clustering approach kernel bisecting k-means in the KBK-SR tends to fast produce balanced clusters of similar sizes in the kernel feature space, which makes KBK-SR efficient and effective for reducing training samples for nonlinear SVMs. Theoretical analysis and experimental results on three UCI real data benchmarks both show that, with very short sampling time, our algorithm dramatically accelerates SVM training while maintaining high test accuracy.