基于几何思想的快速支持向量机算法

为了快速地进行分类,根据几何思想来训练支持向量机,提出了一种快速而简单的支持向量机训练算法——几何快速算法。由于支持向量机的最优分类面只由支持向量决定,因此只要找出两类样本中所有支持向量,那么最优分类面就可以完全确定。该新的算法根据两类样本的几何分布,先从两类样本的最近点开始;然后通过不断地寻找违反KKT条件的样本点来找出支持向量;最后确定最优分类面。为了验证新算法的有效性,分别利用两个公共数据库,对新算法与SMO算法及DIRECTSVM算法进行了实验对比,实验结果显示,新算法的分类精度虽与其他两个方法相当,但新算法的运算速度明显比其他两个算法快。

A Fast Algorithm of SVM Based on Geometry

In the paper, based on geometry theory, a new fast iterative algorithm for support vector machine(SVM) classifier design is presented. It is known that the optimal hyper-plane of SVM is completely constructed using its support vectors. Once all support vectors of two classes are identified, the optimal hyper-plane can be determined. Based on geometric distribution of the trained sample points, the new algorithm establishes an initial candidate support vectors set by locating the two closest points of the two opposite class. The new algorithm starts from two closest points of the opposite classes to seek the support vectors accumulatively. The new algorithm continually seeks the points which are the violators of KKT condition as support vectors. At last, the new algorithm acquires all support vectors and establishes an optimal hyper-plane. To validate the new algorithm, some experiments which compare the new algorithm with the SMO algorithm and DIRECTSVM algorithm are performed. The experimental results have shown the generalization ability of the new algorithm is the same as that of SMO algorithm and DIRECTSVM algorithm. The speed of the new algorithm is superior to the other two algorithms.