CBCH (clustering-based convex hull) for reducing training time of support vector machine

Support vector machine (SVM) is an efficient machine learning technique widely applied to various classification problems due to its robustness. However, the training time grows dramatically as the number of training data increases. As a result, the applicability of SVM to large-scale datasets is somewhat limited. In SVM, only a few training samples called support vectors (SVs) affect the construction of hyperplane. Therefore, removing training data irrelevant to the SVs does not degrade the performance of SVM. In this paper the clustering-based convex hull (CBCH) scheme is introduced which allows to efficiently remove insignificant data and thereby reduce the training time of SVM. The CBCH scheme initially applies k-mean clustering algorithm to the given training data points, and then, the convex hull of each cluster is obtained. Only the vertices of the convex hulls and the data points relevant to the SVs are included as training data points. Computer simulation over various sizes and types of datasets reveals that the proposed scheme is considerably faster and more accurate than the existing SVM classifiers. The proposed algorithm is based on geometric interpretation of the SVM and applicable to both linearly separable and linearly inseparable datasets.