结合SVM和KNN实现求解大规模复杂问题的分治算法  

A Divide and Conquer Algorithm combining Support Vector Machine and Nearest Neighbor Principle

作　　者：李蓉[1] 叶世伟[2] 

机构地区：[1]北京物资学院信息学院,北京101149 [2]中国科学院研究生院信息学院,北京100049

出　　处：《微计算机信息》2009年第21期212-213,256,共3页Control & Automation

基　　金：北京市属高等学校人才强教计划资助项目(PHR200906210);北京市教育委员会科研基地建设项目(WYJD200902);北京市教育委员会科技计划项目(KM200810037001)

摘　　要：针对于使用支持向量机求解大规模复杂问题存在训练时间过长和分类精度不高等困难,本文提出了一种结合支持向量机(SVM)和K-最近邻(KNN)分类的分治算法。首先对支持向量机分类机理进行分析可以得出它作为分类器实际相当于每类只选一个代表点的最近邻分类器。在此基础上,根据分治算法的基本思想将训练集划分为多个训练子集,用每个子集单独训练一个SVM,这样每个训练子集由训练后的SVM可以分别得到正例和反例的一个代表点,由这些代表点的全体构成了整个训练集的正例和反例代表点的集合,然后在这个代表点集合基础上使用KNN分类器最为整个问题的解。实验结果表明该分治算法对于大规模数据可使训练时间大幅度下降且使分类精度不同程度提高。Aiming to reduce the long training time and the improving the classing accuracy for a large scale and complicated prob- lem, this paper presents a divide and conquer algorithm combining support vector machine （SVM） and k - nearest neighbor classifi- er. We analyzed The classifying principle of SVM are analyzed and a conclusion are draw, which is that the SVM classifier equals to a nearest neighbor in which only one representative point is selected for each class. Based on this theory, the idea of this algo- rithm is dividing the training set into multiple subsets, each of which trains individually a SVM and representative points are de- rived for positive case and negative case. The whole representative points constitute the set of initial train set, based on which the k nearest neighbor classifier is applied and the solution of the whole problem are obtained. The results show that our algorithm can not only reduce the train time notability , but also improve the classing accuracy to a certain extent.

关 键 词：支持向量机 聚类中心 类代表点 核函数 特征空间 VC维 

分 类 号：TP183[自动化与计算机技术—控制理论与控制工程]