样例约简支持向量机

Instance Reduction Support Vector Machine

支持向量机(support vector machine,SVM)仅利用靠近分类边界的支持向量构造最优分类超平面,但求解SVM需要整个训练集,当训练集的规模较大时,求解SVM需要占用大量的内存空间,寻优速度非常慢。针对这一问题,提出了一种称为样例约简的寻找候选支持向量的方法。在该方法中,支持向量大多靠近分类边界,可利用相容粗糙集技术选出边界域中的样例,作为候选支持向量,然后将选出的样例作为训练集来求解SVM。实验结果证实了该方法的有效性,特别是对大型数据库,该方法能有效减少存储空间和执行时间。

In support vector machine （SVM）, the optimal classification hyperplane is constructed only from a subset of samples （support vectors） near the boundary. However, solving SVM is based on whole training set, when the training set is very large, it will take a long time to search the optimal solution and require a great amount of mem- ory. In order to deal with this problem, this paper presents a method named instance reduction for selecting the can- didate support vectors. In the proposed method, almost all support vectors are nearby the boundary of classification, the instances used as candidate support vectors in boundary region can be selected by tolerance rough set technique. The SVM is trained from the selected instances. The experimental results show that the proposed method is effective and can efficiently reduce the computational complexity both of time and space especially on large databases.