대용량 데이터에서의 서포트벡터머신 문제 해결을 위한 의사결정트리 분류 기반의 서포트벡터 후보 선택

Abstract

Support vector machines (SVMs) are a well-known classifier due to its excellent classification accuracy. It offers a hyperplane that represents the largest margin between two classes. In the computation of the hyperplane, however, it is necessary to solve a quadratic programming problem (QP). The storage cost of a QP is growing with the square of the number of training sample points, and the time complexity is proportional to the cube of the number. Thus, it is worth to study how to reduce the training time of SVMs without compromising the accuracy to prepare for large-scale problems. In this paper, we propose a novel data reduction method for reducing training time combining decision tree and relative support distance. We apply a new concept, relative support distance, to select good support vector candidates in each partition generated by decision tree. The selected support vector candidates improves the training speed for large-scale SVM problems. In experiments, we demonstrate that our approach significantly reduces the training speed, while maintaining good classification accuracy, in comparison of existing approaches.