Convex and concave hulls for classification with support vector machine

The training of a support vector machine (SVM) has the time complexity of O(n3)O(n3) with data number n. Normal SVM algorithms are not suitable for classification of large data sets. Convex hull can simplify SVM training, however the classification accuracy becomes lower when there are inseparable points. This paper introduces a novel method for SVM classification, called convex–concave hull. After grid pre-processing, the convex hull and the concave (non-convex) hull are found by Jarvis march method. Then the vertices of the convex–concave hull are applied for SVM training. The proposed convex–concave hull SVM classifier has distinctive advantages on dealing with large data sets with higher accuracy. Experimental results demonstrate that our approach has good classification accuracy while the training is significantly faster than the other training methods.