Abstract: To solve the problems of heavy computation, time consuming, data skew and  the errors made in the category prediction of the points near the optimal hyperplane existing in one of the traditional Support Vector Machine（SVM） multi-class classification algorithms—1-vs-all, an improved method is proposed. For the given k-class-dataset, this paper takes all the data belonging to rare categories as the sparse point, wraps the dense points of each category with the corresponding super ball, enlarges the super ball on the principle of the balance between positive and negative samples in it and the radius minimum, and then trains the samples in each super ball for the corresponding SVM classifier. In the testing stage, it predicts the test points in the dense area under the traditional 1-vs-all category prediction criterion and uses the K Nearest Neighbour（KNN） algorithm for the category prediction of the test points in sparse area. In terms of the time consuming and classification precision in test result, the improved algorithm is better than the traditional one. It is proven that, to some degree, the improved algorithm can solve the above problems existing in traditional 1-vs-all algorithm.

Key words: Support Vector Machine（SVM）, 1-vs-all, K Nearest Neighbour（KNN）, data skew

摘要： 针对传统支持向量机（SVM）多分类一对多算法存在的运算量大、耗时长、数据偏斜以及对最优超平面附近点分类易出错问题，提出了一种改进方法。将数据空间分为密集区和稀疏区，各类中密集点归于密集区，其余归于稀疏区。将每类中密集点连同它附近的点用于训练得到相应的SVM分类器。在测试阶段，对密集区的待测样本用传统的一对多判别准则来做类别预测；对稀疏区的待测样本则采用K近邻（KNN）算法。数值实验结果表明，改进的算法在耗时和分类精度上都优于原算法，对解决一对多算法存在的问题有较好的成效。

关键词: 支持向量机（SVM）, 一对多, K近邻（KNN）, 数据偏斜