SVM-K NN 分类器—
——一种提高SVM 分类精度的新方法李
蓉，叶世伟，史忠植
（1.中国科技大学研究生院（北京）计算机教学部，北京100039；2.中国科学院计算技术研究所智能信息处理实验室，
北京100080）摘要：本文提出了一种将支持向量机分类和最近邻分类相结合的方法，形成了一种新的分类器.首先对支持
向量机进行分析可以看出它作为分类器实际相当于每类只选一个代表点的最近邻分类器，同时在对支持向量机分类时出错样本点的分布进行研究的基础上，在分类阶段计算待识别样本和最优分类超平面的距离，如果距离差大于给定阈值直接应用支持向量机分类，否则代入以每类的所有的支持向量作为代表点的K 近邻分类.数值实验证明了使用
支持向量机结合最近邻分类的分类器分类比单独使用支持向量机分类具有更高的分类准确率，同时可以较好地解决应用支持向量机分类时核函数参数的选择问题.
关键词：
支持向量机；最近邻分类；类代表点；核函数；特征空间；VC 维
中图分类号：
TP301
文献标识码：
A
文章编号：
0372-2112（2002）05-0745-04
SVM-!NN Classifier —
——A New Method of lmproving the Accuracy of SVM Classifier LI Rong ，YE Shi-wei ，SHI Zhong-zhi
（1.Dept.of Computing ，Graduate School ，Science and Technology Uniuersity of China ，Beijing 100039，China ；2.National Key Laboratory of Intelligent Information Technology Process ，The Institute of Computing Technology ，Chinese Academy of Sciences ，Beijing 100080，China ）
Abstract ：A new algorithm that combined Support Vector Machine
（SVM ）with K Nearest neighbour （K NN ）is presented and it comes into being a new classifier.The classifier based on taking SVM as a 1NN classifier in which only one representative point is selected for each class.In the class phase ，the algorithm computes the distance from the test sample to the optimal super-plane of SVM in feature space.If the distance is greater than the given threshold ，the test sample would be classified on SVM ；otherwise ，the K NN al-gorithm will be used.In K NN algorithm ，we select every support vector as representative point and compare the distance between the testing sample and every support vector.The testing sample can be classed by finding the k-nearest neighbour of testing sample.The numerical experiments show that the mixed algorithm can not only improve the accuracy compared to sole SVM ，but also better solve the problem of selecting the parameter of kernel function for SVM.
Key words ：support vector machine ；nearst neighbour algorithm ；representative point ；kernel function ；feature space ；VC Di-mension
!引言
统计学习理论是一种专门的小样本统计理论，为研究有
限样本情况下的统计模式识别和更广泛的机器学习问题建立了一个较好的理论框架，同时也发展了一种模式识别方法—支持向量机（Support Vector Machine ，简称SVM ），在解决小样
本、非线形及高维模式识别问题中表现出许多特有的优势，并
能够推广应用到函数拟合等其他机器学习问题中［1］.目前，
统计学习理论和SVM 已经成为国际上机器学习领域新的研究热点并已被应用于人脸识别、文本识别、手写体识别等领域.
在对SVM 的研究中，提高它的分类能力（泛化能力）是所有研究的出发点和归宿.SVM 和其他分类方法相比具有较高的分类精度，但目前在SVM 的应用中还存在一些问题，如对不同的应用问题核函数参数的选择较难，对较复杂问题其分类精度不是很高以及对大规模分类问题训练时间长等.已有
的解决方法包括建立分类性能的评价函数，然后对SVM 中的
核函数的参数进行优化，或者使用直推方法［1］
对给定待样本设计最优的SVM ；所有这些方法的设计和计算都非常复杂，实现的代价都很高.
我们对SVM 分类时错分样本的分布进行分析发现，SVM
分类器和其它的分类器一样［1］
，其出错样本点都在分界面附近，这提示我们必须尽量利用分界面附近的样本提供的信息以提高分类性能.由SVM 理论知道，分界面附近的样本基本上都是支持向量，同时SVM 可以看成每类只有一个代表点的最近邻（Nearst Neighbour ，NN ）分类器（详细推导见附录）.所以结合SVM 和NN ，对样本在空间的不同分布使用不同的分类法.具体地，当样本和SVM 最优超平面的距离大于一给定的阈值，即样本离分界面较远，则用SVM 分类，反之用K NN 对测试样本分类.在使用K NN 时以每类的所有的支持向量作为
收稿日期：2001-06-15；修回日期：2001-10-06
第5期2002年5月电子学报ACTA ELECTRONICA SINICA Vol.30No.5May 2002
代表点组，这样增加的运算量很少.实验证明了使用支持向量机结合最近邻的分类器分类比单独使用支持向量机分类具有更高的分类准确率，同时可以较好地解决应用支持向量机分类时核函数参数的选择问题.
2SVM、!NN分类器简介
2.1SVM分类器
SVM是一种建立在统计学习理论基础上的分类方法［l］.它主要基于以下三种考虑（l）基于结构风险最小化，通过最小化函数集的VC维来控制学习机器的结构风险，使其具有较强的推广能力.（2）通过最大化分类间隔（寻找最优分类超平面）来实现对VC维的控制，这是由统计学习理论的相关定理保证的.（3）而SVM在技术上采用核化技术，根据泛函中的Mercer定理，寻找一个函数（称核函数）将样本空间中内积对应于变换空间中的内积，即避免求非线形映射而求内积.
2.2!NN分类器
近邻法（简称NN）是模式识别非参数法中最重要的方法之一，NN的一个很大特点是将各类中全部样本点都作为“代表点”［l］.lNN是将所有训练样本都作为代表点，因此在分类时需要计算待识别样本x到所有训练样本的距离，结果就是与x最近的训练样本所属于的类别.K NN是lNN的推广，即分类时选出x的I个最近邻，看这I个近邻中的多数属于哪一类，就把x分到哪一类.
3SVM-!NN分类器实现
3.1对SVM分类机理的分析
在本文中，通过对SVM的分类机理分析，找到了SVM和NN分类器之间的联系，此联系由下面的定理给出：定理1SVM分类器等价于每类只选一个代表点的l-NN 分类器.
证明见附录.
区域"，如分类用SVM，只计离
测
为
支
练
分
两
示.
旋
示
螺
问
题.
差，
的
年
惩罚参数C=5，分类阈值!选为0.8.选择了四组不同的核函数参数测试，比较两种算法对不同参数的分类效果.实验结果如表1所示.
（2）文本分类实验：
将下载的5642个中文网页后通过人工方式将其分为十三类后，对各个类标明其输出.这时一个多类分类问题，针对此多类问题我们构造了SVM多值分类器，构造方法采取一对
一方式［4］，训练了!（+1）
2
（=13）个SVM二值子分类器.
本次实验所选取的核函数为感知机核函数（x，x
i
）=tanh（g !（x?x i）+c），大量数据测试证明对于网页分类数据，采用感知机核函数在分类准确率和速度上均优于其它核函数.在此实验中错误惩罚参数C=5，分类阈值!取为0.6.除了对综合测试集进行测试外，我们还从中选取了有代表性几个类分别测试，测试结果如表2所示.
表!双螺旋线分类SVM和K SVM算法比较核参数分类算法圈数：2圈数：3圈数：4
g=0.5
SVM54.7312%50.9241%47.1546% KSVM49.3677%48.4618%50.0917%
g=0.05
SVM61.6282%50.9241%50.6731% KSVM95.7631%86.3446%81.0137%
g=0.03
SVM81.6002%82.1874%72.8237% KSVM92.8041%86.3446%85.1858%
g=0.01
SVM95.9519%87.8010%57.6668% KSVM95.7631%86.3446%85.1876%
表"对于文本分类SVM和K SVM算法比较
核参数分类
算法
综合类工业类体育类生活类政治类
g=2
SVM65.1423%56.9759%83.8684%63.3834%75.7044% KSVM68.8713%60.3927%88.8192%64.5993%78.3995%
g=0.5
SVM66.6612%59.888%83.3060%66.4731%81.4176% KSVM69.1269%62.0845%87.9798%65.5740%82.2401%
g=0.1
SVM46.2187% 2.9668%59.4340%26.8909%87.9119% KSVM64.1182%61.8701%85.3217%54.3182%89.1481%
g=0.05
SVM30.2999%0%31.3306%0%92.7028% KSVM64.0689%61.3808%82.9425%51.1887%93.9405%
（3）实验分析
从实验的结果数据可以得出两个结论：一是使用SVM-K NN分类可以减轻对核函数参数选择的敏感程度，缓解对参数选择的困难.对于SVM分类器，核函数参数的选择是非常重要但很困难的.如表1中当参数g=0.5、g=0.01及表2中的g=0.5、g=0.05，SVM的分类性能差别很大.对于同一参数，问题不同分类效果差别也很大，如上表1中g=0.01，对圈数为二、三的螺旋线，SVM的分类效果很好，但对于四圈的螺旋线，SVM的识别率不如选择g=0.03的识别率.带入K SVM算法后，对于参数的选择不是很敏感.如表1中的g= 0.05和g=0.01，K SVM算法的效果差别很小，性能比较稳定.
第二个结论是使用SVM-K NN分类器在一定程度上比使用SVM具有更好的性能.针对四圈情况，数据的线形不可分程度高，使用SVM分类性能低，而使用K SVM算法分类精度
提高较明显.而当实际问题相对好分时（表1中的二、三圈螺旋线），二者的分类效果差别不大.这是因为当实际问题比较易分时，SVM训练后所得到支持向量个数少，在K SVM中所选取的代表点也少；实际问题复杂程度高时，SVM训练后所得到支持向量个数多，K SVM算法所携带的信息更高，而此时SVM 分别对正反例支持向量组仅合成一个代表点，损失的信息也相对较多.
#结论
本文将SVM和K NN分类器相结合构造了一种新的分类器，该分类器基于将SVM分类器等价于对每类支持向量只取一个代表点的1NN分类器，针对当测试样本在分界面附近时容易分错的情形引入K NN分类选取每个支持向量作为代表点.SVM-K NN分类器是一种通用的分类算法，使用该分类器的分类准确率比单纯使用SVM分类器一般有不同程度的提高，并且该分类器在一定程度上不受核函数参数选择的影响，具有一定的稳健性.进一步的工作是从SVM的分类机理得到启发，不一定采用每个支持向量作为代表点，而对它们进行组合选取多个代表点进行分类.
附录：定理!证明
已知线性可分样本集为（x
i
，y
i
），i=1，…，l，x
i"R
d，y"｛-1，+1｝为类别标志，d空间维数.最优分类面问题可以表示成如下优化问题的对偶问题
W（"）=#l
i=1
"i-
1
2
#l
i，j=1
"i"j y i y j（x i?x j）（1）约束条件为：
0$"i，i=1，…，I与#l
i=1
"i y i=0（2）根据Kuhn-tucker条件，这个优化问题的解必须满足
"i（y i［（w，x i）-J］-1）=0，i=1，…，l（3）相应的分类函数也变为
f（x）=Sgn#
i
y i"i?（x i，x）-
()J（4）首先分别利用正、反例支持向量组成两个代表点#（x）+ =
1
C
#l
y
i=
1，i=1
"i#（x i），#（x）-=
1
C
#l
y
i=-
1，i=1
"i#（x i）.其中#
y
i=
1
"i=
#
y
i=-
1
"i=C（根据目标函数对偶问题的等式约束条件#
l
i=1
"i y i=
0），对于最优解w=#l
i=1
"i#（x i）=C（#（x）+-#（x）-），由式（3）对任意正例的样本有"i（（w，#（x i））-J-1）=0，从而有
0=#
y
i=
1
"i（（w，#（x i））-J-1）
=（w，#
y
i=
1
"i#（x i））-C?J-C
=（C（#（x）+-#（x）-），C#（x）+）-C?J-C
=C［C（（#（x）+-#（x）-，#（x）+））-J-1］（5）这样有J=C（#（x）+-#（x）-，#（x）+）-1
同样由式（3），对任意反例的样本有
747
第5期李蓉：SVM-K NN分类器———一种提高SVM分类精度的新方法
J=C（（!（x）+-!（x）-，!（x）-））+1（6）由（式（5）+式（6））/2可得
J=C
2
（（!（x）+-!（x）-，!（x）++!（x）-））
=C
2
（（x+，x+）-（x-，x-））（7）
在SVM的分类过程代入1NN分类，可得到下式：
g（x）=!!（x）-!（x）-!2-!!（x）-!（x）+!2
=2（x，x+）-2（x，x-）+（x-，x-）-（x+，x+）
=2
C
"
i
"i y i（x，x i）+
C
2
［（x-，x-）-（x+，x+ {}）］
（由式（7）可得）=2
C
"
i
"i y i（x，x i）-
{}J（8）
参考文献：
［1］Vapnik V N.The Nature of Statisticai Learning Theory［M］.NY：Springer Veriag.
［2］边肇祺，张学工.模式识别［M］.北京：清华大学出版社.2000.［3］Vapnik V N.Estimation of dependencies based on empiricai data［R］.
Beriin：Springer Veriag，1982.
［4］Burges C J C.A tutoriai on support vector machines for pattern recogni-tion［J］.Data Mining and Knowiedge Discvery，1998，2（2）.［5］Weston J，Watkins C.Muiti-ciass support vector［J］.machines.Royai Hoiioway Coiiege，Tech Rep：CSK-TR-98-04，1998.
［6］Thorston Joachims.Text Categorization With Support Vector Machine：iearning with reievant features［R］.University Dortmund，1998.
作者简介：
李蓉女，1973年生于北京，1996年于北
京理工大学获工学学士位，1999年进入中国科技
大学研究生院（北京）计算机软件专业攻读硕士
学位，2000年10月至今在中科院计算技术研究
所智能信息处理开放实验室做硕士论文，师从于
史忠植研究员，研究方向为机器学习、神经计算，
已发表学术论文3篇.
叶世伟男，1968年生于四川，分别于1991年、1993年、1996年于四川师范大学、北京大学、中科院计算技术研究所获得理学学士、理学硕士和工学博士学位，现任中科院研究生计算机教学部院副教授，主要研究方向为神经计算、优化理论，已发表学术论文十余篇
###############################################
.
2002国际存储展览暨技术研讨会在京召开
由信息产业部电子信息产品管理司、中国电信、国家邮政局及中国计算机学会信息存储技术专业委员会支持，中国电子信息产业发展研究院（CCID）主办，赛迪展览公司承办的“2002国际存储展览暨技术研讨会（Storage Infoworid2002）”4月25~27日在北京中国国际科技会展中心隆重举行.信息产业部苟仲文副部长参加开幕主题演讲并致欢迎辞，随后在信息产业部有关司局领导的陪同下饶有兴趣地参观了展览会，并与参展企业代表亲切座谈.来自各有关部委和行业用户部门的三十多位领导和近千余名专业人士出席了展览及研讨会.
Sotrage Infoworid2002聚焦存储领域热点，汇聚如EMC、SUN、HP、Network Appiiance、Xiotech、Seagate、CA、Auspex、RC、Spectra Logic、VERITAS、Ouantum、Maxtor、SONY、ANEKtek、清华同方、亚美联等三十余家国内外知名存储软硬件厂商、存储系统集成商、存储技术开发商及相关的经销商和渠道合作伙伴，内容涵盖网络存储、光存储、移动存储、存储软件及存储应用解决方案.EMC公司在展会上推出了一系列高级、整合并经过验证的业务连续性解决方案；Sun公司的Storage ONE体系架构提供了一个开放、集成化和自动的存储管理解决方案；Network Appiiance作为数据存储和内容传输领域的世界领先者，为当今数据激增的企业提供开放的网络存储解决方案；亚美联公司作为国内首家完全自主知识产权的企业级存储产品供应商，推出的国内第一套达到国际先进技术水平的企业级存储系统Estor NAS18/2800、Estor SAN产品系列；Spectra Logic 公司的Spectra64000企业级磁带库、昆腾公司的基于磁盘的产品系列———第一款产品Ouantum DX30等都在展会上亮相.
在两天半的研讨会中，来自EMC、SUN、HP、XIOtech、CA、Spectra Logic、清华同方等公司的国内外存储专家，将从存储的最新动态、发展方向、最新技术、解决方案和成功案例等方面发表精彩演讲.
IT界称2001为存储年，而2002年将为中国存储市场迎来又一高峰.Storage Infoworid2002作为国内IT存储领域举办的权威盛会，必将以优质的服务为国内外关注中国存储市场发展的厂商及用户架起供需沟通的桥梁.
847电子学报2002年
支持向量机算法推导及其分类的算法实现 摘要：本文从线性分类问题开始逐步的叙述支持向量机思想的形成，并提供相应的推导过程。简述核函数的概念，以及kernel在SVM算法中的核心地位。介绍松弛变量引入的SVM算法原因，提出软间隔线性分类法。概括SVM分别在一对一和一对多分类问题中应用。基于SVM在一对多问题中的不足，提出SVM 的改进版本DAG SVM。 Abstract：This article begins with a linear classification problem, Gradually discuss formation of SVM, and their derivation. Description the concept of kernel function, and the core position in SVM algorithm. Describes the reasons for the introduction of slack variables, and propose soft-margin linear classification. Summary the application of SVM in one-to-one and one-to-many linear classification. Based on SVM shortage in one-to-many problems, an improved version which called DAG SVM was put forward. 关键字：SVM、线性分类、核函数、松弛变量、DAG SVM 1. SVM的简介 支持向量机(Support Vector Machine)是Cortes和Vapnik于1995年首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度，Accuracy）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力。 对于SVM的基本特点，小样本，并不是样本的绝对数量少，而是与问题的复杂度比起来，SVM算法要求的样本数是相对比较少的。非线性，是指SVM擅长处理样本数据线性不可分的情况，主要通过松弛变量和核函数实现，是SVM 的精髓。高维模式识别是指样本维数很高，通过SVM建立的分类器却很简洁，只包含落在边界上的支持向量。
SVM分类器原理 SVM定义 ?SVM是一种基于统计学习理论的机器学习方法，它是由Boser,Guyon, Vapnik在 COLT-92上首次提出，从此迅速发展起来。 ?Vapnik V N. 1995. The Nature of Statistical Learning Theory. Springer-Verlag, New York. ?Vapnik V N. 1998. Statistical Learning Theory. Wiley-Interscience Publication, John Wiley&Sons, Inc. ?SVM在解决小样本、非线性及高维模式识别问题中表现出许多特有的优势，并能够 推广应用到函数拟合等其他机器学习问题中.目前已经在许多智能信息获取与处理领域都取得了成功的应用。 SVM方法的特点 ?SVM 的最终决策函数只由少数的支持向量所确定,计算的复杂性取决于支持向量的 数目,而不是样本空间的维数,这在某种意义上避免了“维数灾难”。 ?少数支持向量决定了最终结果,这不但可以帮助我们抓住关键样本、“剔除”大量冗余 样本,而且注定了该方法不但算法简单,而且具有较好的“鲁棒”性。这种“鲁棒”性主要体现在: ?①增、删非支持向量样本对模型没有影响; ?②支持向量样本集具有一定的鲁棒性; ?③有些成功的应用中,SVM 方法对核的选取不敏感。 SVM 应用 ?近年来SVM 方法已经在图像识别、信号处理和基因图谱识别等方面得到了成功的 应用,显示了它的优势。 ?SVM 通过核函数实现到高维空间的非线性映射,所以适合于解决本质上非线性的分 类、回归和密度函数估计等问题。 ?支持向量方法也为样本分析、因子筛选、信息压缩、知识挖掘和数据修复等提供了 新工具。 SVM训练算法 ?传统的利用标准二次型优化技术解决对偶问题的方法,是SVM训练算法慢及 受到训练样本集规模制约的主要原因。 ?目前已提出了许多解决方法和改进算法,主要是从如何处理大规模样本集的
SVM分类器设计 1.引言 支撑矢量机（SVM）是90年代中期发展起来的基于统计学习理论的一种机器学习方法，通过寻求结构化风险最小来提高学习机泛化能力，实现经验风险和置信范围的最小化，从而达到在统计样本量较少的情况下，亦能获得良好统计规律的目的。SVM分类器在推广性和经验误差两方面能达到平衡，是目前比较盛行的分类器。 1.1 什么是SVM分类器 所谓支持向量机，顾名思义，分为两个部分了解，一什么是支持向量，简单来说，就是支持或者是支撑平面上把两类类别划分开来的超平面的向量点；二这里的“机”是什么意思。“机（machine,机器）”便是一个算法。在机器学习领域，常把一些算法看做是一个机器，如分类机(当然，也叫做分类器)，而支持向量机本身便是一种监督式学习的方法它广泛的应用于统计分类以及回归分析中。 SVM的主要思想可以概括为两点：⑴它是针对线性可分情况进行分析；(2)对于线性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分，从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能。 1.2 SVM分类器的优点和缺点 优点： (1)由于核函数隐含一个复杂映射，经验误差小，因此针对小样本数据利用支持向量能够完成线性或非线性规划问题；推广性和经验误差平衡。 (2)SVM 的最终决策函数只由靠近边界的少数的支持向量所确定,计算的复杂性取决于支持向量的数目,而不是样本空间的维数,这在某种意义上避免了“维数灾难”。 (3)少数支持向量决定了最终结果,这不但可以帮助我们抓住关键样本、“剔除”大量冗余样本,而且注定了该方法不但算法简单,而且具有较好的“鲁棒”性。这种“鲁棒”性主要体现在:①增、删非支持向量样本对模型没有影响;②支持向量样本集具有一定的鲁棒性; ③有些成功的应用中,SVM 方法对核的选取不敏感 缺点： (1)在训练分类器时 ,SVM的着眼点在于两类的交界部分 ,那些混杂在另一类中的点往往无助于提高分类器的性能 ,反而会大大增加训练器的计算负担 ,同时它们的存在还可能造成过学习 ,使泛化能力减弱 .为了改善支持向量机的泛化能力。 (2)SVM算法对大规模训练样本难以实施。由于SVM是借助二次规划来求解支持向量，而求解二次规划将涉及m阶矩阵的计算（m为样本的个数），当m数目很大时该矩阵的存储和计算将耗费大量的机器内存和运算时间。 (3)用SVM解决多分类问题存在困难。经典的支持向量机算法只给出了二类分类的算法，而在数据挖掘的实际应用中，一般要解决多类的分类问题。可以通过多个二类支持向量机的组合来解决。主要有一对多组合模式、一对一组合模式和SVM决策树；再就是通过构造多个分类器的组合来解决。主要原理是克服SVM固有的缺点，结合其他算法的优势，解决多类问题的分类精度。如：与粗集理论结合，形成一种优势互补的多类问题的组合分类器1.3 SVM分类器当前研究热点 (1)针对大样本数据训练难度问题，对SVM算法的改进。例如J.Platt的SMO算法、T.Joachims的SVM、C.J.C.Burges等的PCGC、张学工的CSVM以及O.L.Mangasarian等的SOR算法。 (2)如何降低边界混杂点(即所谓统计误差导致的“不干净”点)导致的不必要的训练计算负担，增强泛化能力。这种思路聚焦于样本数据预处理的探索，例如NN-SVM。 (3)分类器设计思想之间的融合以及取长补短。例如[2]采样支撑矢量机和最近邻分类相
支持向量机SVM分类算法 SVM的简介 支持向量机(Support Vector Machine)是Cortes和Vapnik于1995年首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中[10]。 支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度，Accuracy）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力[14]（或称泛化能力）。 以上是经常被有关SVM 的学术文献引用的介绍，我来逐一分解并解释一下。 Vapnik是统计机器学习的大牛，这想必都不用说，他出版的《Statistical Learning Theory》是一本完整阐述统计机器学习思想的名著。在该书中详细的论证了统计机器学习之所以区别于传统机器学习的本质，就在于统计机器学习能够精确的给出学习效果，能够解答需要的样本数等等一系列问题。与统计机器学习的精密思维相比，传统的机器学习基本上属于摸着石头过河，用传统的机器学习方法构造分类系统完全成了一种技巧，一个人做的结果可能很好，另一个人差不多的方法做出来却很差，缺乏指导和原则。所谓VC维是对函数类的一种度量，可以简单的理解为问题的复杂程度，VC维越高，一个问题就越复杂。正是因为SVM关注的是VC维，后面我们可以看到，SVM解决问题的时候，和样本的维数是无关的（甚至样本是上万维的都可以，这使得SVM很适合用来解决文本分类的问题，当然，有这样的能力也因为引入了核函数）。 结构风险最小听上去文绉绉，其实说的也无非是下面这回事。 机器学习本质上就是一种对问题真实模型的逼近（我们选择一个我们认为比较好的近似模型，这个近似模型就叫做一个假设），但毫无疑问，真实模型一定是不知道的（如果知道了，我们干吗还要机器学习？直接用真实模型解决问题不就可以了？对吧，哈哈）既然真实模型不知道，那么我们选择的假设与问题真实解之间究竟有多大差距，我们就没法得知。比如说我们认为宇宙诞生于150亿年前的一场大爆炸，这个假设能够描述很多我们观察到的现象，但它与真实的宇宙模型之间还相差多少？谁也说不清，因为我们压根就不知道真实的宇宙模型到底是什么。 这个与问题真实解之间的误差，就叫做风险（更严格的说，误差的累积叫做风险）。我们选择了一个假设之后（更直观点说，我们得到了一个分类器以后），真实误差无从得知，但我们可以用某些可以掌握的量来逼近它。最直观的想法就是使用分类器在样本数据上的分类的结果与真实结果（因为样本是已经标注过的数据，是准确的数据）之间的差值来表示。这个差值叫做经验风险Remp(w)。以前的机器学习方法都把经验风险最小化作为努力的目标，但后来发现很多分类函数能够在样本集上轻易达到100%的正确率，在真实分类时却一塌糊涂（即所谓的推广能力差，或泛化能力差）。此时的情况便是选择了一个足够复杂的分类函数（它的VC维很高），能够精确的记住每一个样本，但对样本之外的数据一律分类错误。回头看看经验风险最小化原则我们就会发现，此原则适用的大前提是经验风险要确实能够逼近真实风险才行（行话叫一致），但实际上能逼近么？答案是不能，因为样本数相对于现实世界要分类的文本数来说简直九牛
SVM入门（十）将SVM用于多类分类 从SVM的那几张图可以看出来，SVM是一种典型的两类分类器，即它只回答属于正类还是负类的问题。而现实中要解决的问题，往往是多类的问题（少部分例外，例如垃圾邮件过滤，就只需要确定“是”还是“不是”垃圾邮件），比如文本分类，比如数字识别。如何由两类分类器得到多类分类器，就是一个值得研究的问题。 还以文本分类为例，现成的方法有很多，其中一种一劳永逸的方法，就是真的一次性考虑所有样本，并求解一个多目标函数的优化问题，一次性得到多个分类面，就像下图这样： 多个超平面把空间划分为多个区域，每个区域对应一个类别，给一篇文章，看它落在哪个区域就知道了它的分类。 看起来很美对不对？只可惜这种算法还基本停留在纸面上，因为一次性求解的方法计算量实在太大，大到无法实用的地步。 稍稍退一步，我们就会想到所谓“一类对其余”的方法，就是每次仍然解一个两类分类的问题。比如我们有5个类别，第一次就把类别1的样本定为正样本，其余2，3，4，5的样本合起来定为负样本，这样得到一个两类分类器，它能够指出一篇文章是还是不是第1类的；第二次我们把类别2 的样本定为正样本，把1，3，4，5的样本合起来定为负样本，得到一个分类器，如此下去，我们可以得到5个这样的两类分类器（总是和类别的数目一致）。到了有文章需要分类的时候，我们就拿着这篇文章挨个分类器的问：是属于你的么？是属于你的么？哪个分类器点头说是了，文章的类别就确定了。这种方法的好处是每个优化问题的
规模比较小，而且分类的时候速度很快（只需要调用5个分类器就知道了结果）。但有时也会出现两种很尴尬的情况，例如拿一篇文章问了一圈，每一个分类器都说它是属于它那一类的，或者每一个分类器都说它不是它那一类的，前者叫分类重叠现象，后者叫不可分类现象。分类重叠倒还好办，随便选一个结果都不至于太离谱，或者看看这篇文章到各个超平面的距离，哪个远就判给哪个。不可分类现象就着实难办了，只能把它分给第6个类别了……更要命的是，本来各个类别的样本数目是差不多的，但“其余”的那一类样本数总是要数倍于正类（因为它是除正类以外其他类别的样本之和嘛），这就人为的造成了上一节所说的“数据集偏斜”问题。 因此我们还得再退一步，还是解两类分类问题，还是每次选一个类的样本作正类样本，而负类样本则变成只选一个类（称为“一对一单挑”的方法，哦，不对，没有单挑，就是“一对一”的方法，呵呵），这就避免了偏斜。因此过程就是算出这样一些分类器，第一个只回答“是第1类还是第2类”，第二个只回答“是第1类还是第3类”，第三个只回答“是第1类还是第4类”，如此下去，你也可以马上得出，这样的分类器应该有5 X 4/2=10个（通式是，如果有k个类别，则总的两类分类器数目为k(k-1)/2）。虽然分类器的数目多了，但是在训练阶段（也就是算出这些分类器的分类平面时）所用的总时间却比“一类对其余”方法少很多，在真正用来分类的时候，把一篇文章扔给所有分类器，第一个分类器会投票说它是“1”或者“2”，第二个会说它是“1”或者“3”，让每一个都投上自己的一票，最后统计票数，如果类别“1”得票最多，就判这篇文章属于第1类。这种方法显然也会有分类重叠的现象，但不会有不可分类现象，因为总不可能所有类别的票数都是0。看起来够好么？其实不然，想想分类一篇文章，我们调用了多少个分类器？10个，这还是类别数为5的时候，类别数如果是1000，要调用的分类器数目会上升至约500,000个（类别数的平方量级）。这如何是好？ 看来我们必须再退一步，在分类的时候下功夫，我们还是像一对一方法那样来训练，只是在对一篇文章进行分类之前，我们先按照下面图的样子来组织分类器（如你所见，这是一个有向无环图，因此这种方法也叫做DAG SVM）
SVM分类器的原理及应用 姓名：苏刚学号：1515063004学院：数学与计算机学院 一、SVM分类器的原理 SVM法即支持向量机(Support Vector Machine)法，由Vapnik等人于1995年提出，具 有相对优良的性能指标。该方法是建立在统计学习理论基础上的机器学习方法。通过学习算法，SVM可以自动寻找出那些对分类有较好区分能力的支持向量，由此构造出的分类器可以 最大化类与类的间隔，因而有较好的适应能力和较高的分准率。该方法只需要由各类域的边 界样本的类别来决定最后的分类结果。支持向量机算法的目的在于寻找一个超平面H(d),该 超平面可以将训练集中的数据分开，且与类域边界的沿垂直于该超平面方向的距离最大，故SVM法亦被称为最大边缘(maximum margin)算法。待分样本集中的大部分样本不是支持向量，移去或者减少这些样本对分类结果没有影响，SVM法对小样本情况下的自动分类有着较好的 分类结果. SVM方法是通过一个非线性映射p，把样本空间映射到一个高维乃至无穷维的特征空间中（Hilbert空间），使得在原来的样本空间中非线性可分的问题转化为在特征空间中的线性 可分的问题。简单地说，就是升维和线性化。升维，就是把样本向高维空间做映射，一般情 况下这会增加计算的复杂性，甚至会引起“维数灾难”，因而人们很少问津。但是作为分类、回归等问题来说，很可能在低维样本空间无法线性处理的样本集，在高维特征空间中却可以 通过一个线性超平面实现线性划分（或回归）。一般的升维都会带来计算的复杂化，SVM方 法巧妙地解决了这个难题：应用核函数的展开定理，就不需要知道非线性映射的显式表达式；由于是在高维特征空间中建立线性学习机，所以与线性模型相比，不但几乎不增加计算的复 杂性，而且在某种程度上避免了“维数灾难”。这一切要归功于核函数的展开和计算理论。 选择不同的核函数，可以生成不同的SVM，常用的核函数有以下4种： ⑴线性核函数K(x,y)=x·y； ⑵多项式核函数K(x,y)=[(x·y)+1]^d； ⑶径向基函数K(x,y)=exp(-|x-y|^2/d^2）； ⑷二层神经网络核函数K(x,y)=tanh(a(x·y)+b）；
SVM的常用多分类算法概述 摘要：SVM方法是建立在统计学习理论基础上的机器学习方法，具有相对优良的分类性能，是一种非线性分类器。最初SVM是用以解决两类分类问题，不能直接用于多类分类，当前已经有许多算法将SVM推广到多类分类问题，其中最常用两类：OAA和OAO算法，本文主要介绍这两类常用的多分类算法。 关键词：SVM；多分类；最优化 自从90年代初V. Vapnik提出经典的支持向量机理论（SVM），由于其完整的理论框架和在实际应用中取得的很多好的效果，在模式识别、函数逼近和概率密度估计领域受到了广泛的重视。SVM方法是建立在统计学习理论基础上的机器学习方法，具有相对优良的分类性能。SVM是一种非线性分类器。它的基本思想是将输入空间中的样本通过某种非线性函数关系映射到一个特征空间中，使两类样本在此特征空间中线性可分，并寻找样本在此特征空间中的最优线性区分平面。它的几个主要优点是可以解决小样本情况下的机器学习问题，提高泛化性能，解决高维问题、非线性问题，可以避免神经网络结构选择和局部极小点问题。 1. SVM方法 若样本集Q={（x i，y i）|i=1,……,L}∈R d*{-1,+1}是线性可分的。则存在分类超平面w T x+b=0,x∈R d对样本集Q中任一（x i，y i）都满足： 在空间R d中样本x=（x1，…, x d）r到分类超平面的距离d=|w T*x+b|/||w||，其中 ||w||= . 当存在x 使得w T x i+b=±1, 则图1中超平面的分类间隔 margin = 2/ ‖w ‖。 使分类间隔margin 最大的超平面即为最优分类超平面。寻找最优分类超平面的问题将转化为求如下一个二次规划问题: minΦ( w) =1/2‖w ‖ 满足约束条件： y i ( w T x i + b) ≥1 , i = 1 ,2 , ?, L 采用Lagrange 乘子转换为一个对偶问题,形式如下: 满足约束条件:
ENVI4.3 支持向量机分类原理、操作及实例分析 一、支持向量机算法介绍 1.支持向量机算法的理论背景 支持向量机分类（Support Vector Machine或SVM）是一种建立在统计学习理论（Statistical Learning Theory或SLT）基础上的机器学习方法。 与传统统计学相比，统计学习理论（SLT）是一种专门研究小样本情况下及其学习规律的理论。该理论是建立在一套较坚实的理论基础之上的，为解决有限样本学习问题提供了一个统一的框架。它能将许多现有方法纳入其中，有望帮助解决许多原来难以解决的问题，如神经网络结构选择问题、局部极小点问题等；同时，在这一理论基础上发展了一种新的通用学习方法——支持向量机（SVM），已初步表现出很多优于已有方法的性能。一些学者认为，SLT和SVM正在成为继神经网络研究之后新的研究热点，并将推动机器学习理论和技术的重大发展。 支持向量机方法是建立在统计学习理论的VC维（VC Dimension）理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力。 支持向量机的几个主要优点有： （1）它是专门针对有限样本情况的，其目标是得到现有信息下的最优解而不仅仅是样本数趋于无穷大时的最优值； （2）算法最终将转化成为一个二次型寻优问题，从理论上说，得到的将是全局最优点，解决了在神经网络方法中无法避免的局部极值问题； （3）算法将实际问题通过非线性变换转换到高维的特征空间(Feature Space)，在高维空间中构造线性判别函数来实现原空间中的非线性判别函数，特殊性质能保证机器有较 好的推广能力，同时它巧妙地解决了维数问题，其算法复杂度与样本维数无关； 2.支持向量机算法简介 通过学习算法，SVM可以自动寻找那些对分类有较大区分能力的支持向量，由此构造出分类器，可以将类与类之间的间隔最大化，因而有较好的推广性和较高的分类准确率。 最优分类面（超平面）和支持向量
SVM算法推导及其分类的算法实现 摘要：本文从线性分类问题开始逐步的叙述支持向量机思想的形成，并提供相应的推导过程。简述核函数的概念，以及kernel在SVM算法中的核心地位。介绍松弛变量引入的SVM算法原因，提出软间隔线性分类法。概括SVM分别在一对一和一对多分类问题中应用。基于SVM在一对多问题中的不足，提出SVM 的改进版本DAG SVM。 Abstract：This article begins with a linear classification problem, Gradually discuss formation of SVM, and their derivation. Description the concept of kernel function, and the core position in SVM algorithm. Describes the reasons for the introduction of slack variables, and propose soft-margin linear classification. Summary the application of SVM in one-to-one and one-to-many linear classification. Based on SVM shortage in one-to-many problems, an improved version which called DAG SVM was put forward. 关键字：SVM、线性分类、核函数、松弛变量、DAG SVM 1. SVM的简介 支持向量机(Support Vector Machine)是Cortes和Vapnik于1995年首先提出的，它在解决小样本、非线性及高维模式识别中表现出许多特有的优势，并能够推广应用到函数拟合等其他机器学习问题中。支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的，根据有限的样本信息在模型的复杂性（即对特定训练样本的学习精度，Accuracy）和学习能力（即无错误地识别任意样本的能力）之间寻求最佳折衷，以期获得最好的推广能力。 对于SVM的基本特点，小样本，并不是样本的绝对数量少，而是与问题的复杂度比起来，SVM算法要求的样本数是相对比较少的。非线性，是指SVM擅长处理样本数据线性不可分的情况，主要通过松弛变量和核函数实现，是SVM 的精髓。高维模式识别是指样本维数很高，通过SVM建立的分类器却很简洁，只包含落在边界上的支持向量。
SVM分类器设计 （控制工程XXXXXXXX） 一、问题表述 对“data3.m”数据，用其中一半的数据采用非线性SVM算法设计分类器并画出决策面，另一半数据用于测试分类器性能。比较不同核函数的结果。（注意讨论算法中参数设置的影响。） 二、方法描述 SVM方法是通过一个非线性映射p，把样本空间映射到一个高维乃至无穷维的特征空间中（Hilbert空间），使得在原来的样本空间中非线性可分的问题转化为在特征空间中的线性可分的问题．简单地说，就是升维和线性化．升维，就是把样本向高维空间做映射，一般情况下这会增加计算的复杂性，甚至会引起“维数灾难”，因而人们很少问津．但是作为分类、回归等问题来说，很可能在低维样本空间无法线性处理的样本集，在高维特征空间中却可以通过一个线性超平面实现线性划分（或回归）．一般的升维都会带来计算的复杂化，SVM方法巧妙地解决了这个难题：应用核函数的展开定理，就不需要知道非线性映射的显式表达式；由于是在高维特征空间中建立线性学习机，所以与线性模型相比，不但几乎不增加计算的复杂性，而且在某种程度上避免了“维数灾难这一切要归功于核函数的展开和计算理论． 选择不同的核函数，可以生成不同的SVM，常用的核函数有以下4种： ⑴线性核函数K(x,y)=x·y； ⑵多项式核函数K(x,y)=[(x·y)+1]^d； ⑶径向基函数K(x,y)=exp(-|x-y|^2/d^2） ⑷二层神经网络核函数K(x,y)=tanh(a(x·y)+b）． SVM的主要思想可以概括为两点：⑴它是针对线性可分情况进行分析，对于线性不可分的情况，通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分，从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能；Vapnik等人在多年研究统计学习理论基础上对线性分类器提出了另一种设计最佳准则。其原理也从线性可分说起，然后扩展到线性不可分的情况。甚至扩展到使用非线性函数中去，这种分类器被称为支持向量机（Support Vector Machine，简称SVM）。支持向量机的提出有很深的理论背景。 三、算法实现 X =load('data.txt'); n = length(X);%总样本数量 y = X(:,4);%类别标志 X = X(:,1:3); TOL = 0.0001;%精度要求 C = 1;%参数，对损失函数的权重 b = 0;%初始设置截距b Wold = 0;%未更新a时的W(a) Wnew = 0;%更新a后的W(a) for i = 1 : 50%设置类别标志为1或者-1 y(i) = -1;
SVM 1.判断题 (1) 在SVM训练好后，我们可以抛弃非支持向量的样本点，仍然可以对新样本进行分类。(T) (2) SVM对噪声（如来自其他分布的噪声样本）鲁棒。(F) 2．简答题 现有一个点能被正确分类且远离决策边界。如果将该点加入到训练集，为什么SVM的决策边界不受其影响，而已经学好的logistic回归会受影响？ 答：因为SVM采用的是hinge loss，当样本点被正确分类且远离决策边界时，SVM给该样本的权重为0，所以加入该样本决策边界不受影响。而logistic回归采用的是log损失，还是会给该样本一个小小的权重。 3．产生式模型和判别式模型。（30分，每小题10分） 图2：训练集、最大间隔线性分类器和支持向量（粗体） （1）图中采用留一交叉验证得到的最大间隔分类器的预测误差的估计是多少（用样本数表示即可）? 从图中可以看出，去除任意点都不影响SVM的分界面。而保留所有样本时，所有的样本点都能被正确分类，因此LOOCV的误差估计为0。 （2）说法“最小结构风险保证会找到最低决策误差的模型”是否正确，并说明理由。(F) 最小结构风险（SRM）只能保证在所有考虑的模型中找到期望风险上界最小的模型。 （3）若采用等协方差的高斯模型分别表示上述两个类别样本的分布，则分类器的VC维是多少？为什么？ 等协方差的高斯模型的决策边界为线性，因为其VC维维D+1。题中D=2.
4、SVM 分类。（第1~5题各4分，第6题5分，共25分） 下图为采用不同核函数或不同的松弛因子得到的SVM 决策边界。但粗心的实验者忘记记录每个图形对应的模型和参数了。请你帮忙给下面每个模型标出正确的图形。 (1)、211min , s.t.2N i i C ξ=??+ ? ?? ∑w ()00, 1, 1,....,, T i i i y w i N ξξ≥+≥-=w x 其中0.1C =。 线性分类面，C 较小， 正则较大，||w||较小，Margin 较大, 支持向量较多（c ） (2)、211min , s.t.2N i i C ξ=??+ ? ?? ∑w ()00, 1, 1,....,, T i i i y w i N ξξ≥+≥-=w x 其中1C =。 线性分类面，C 较大， 正则较小，||w||较大，Margin 较小 支持向量的数目少（b ） (3)、()111 1max ,2N N N i i j i j i j i i j y y k ααα===??- ??? ∑∑∑x x 1 s.t. 0, 1,....,, 0N i i i i C i N y αα=≤<==∑ 其中()()2 ,T T k '''=+x x x x x x 。 二次多项式核函数，决策边界为二次曲线 (d)
SVM入门（六）线性分类器的求解——问题的转化，直观角度 让我再一次比较完整的重复一下我们要解决的问题：我们有属于两个类别的样本点（并不限定这些点在二维空间中）若干，如图， 圆形的样本点定为正样本（连带着，我们可以把正样本所属的类叫做正类），方形的点定为负例。我们想求得这样一个线性函数（在n维空间中的线性函数）： g(x)=wx+b 使得所有属于正类的点x+代入以后有g(x+)≥1，而所有属于负类的点x-代入后有g(x-)≤-1（之所以总跟1比较，无论正一还是负一，都是因为我们固定了间隔为1，注意间隔和几何间隔的区别）。代入g(x)后的值如果在1和-1之间，我们就拒绝判断。 求这样的g(x)的过程就是求w（一个n维向量）和b（一个实数）两个参数的过程（但实际上只需要求w，求得以后找某些样本点代入就可以求得b）。因此在求g(x)的时候，w才是变量。
你肯定能看出来，一旦求出了w（也就求出了b），那么中间的直线H就知道了（因为它就是wx+b=0嘛，哈哈），那么H1和H2也就知道了（因为三者是平行的，而且相隔的距离还是||w||决定的）。那么w是谁决定的？显然是你给的样本决定的，一旦你在空间中给出了那些个样本点，三条直线的位置实际上就唯一确定了（因为我们求的是最优的那三条，当然是唯一的），我们解优化问题的过程也只不过是把这个确定了的东西算出来而已。 样本确定了w，用数学的语言描述，就是w可以表示为样本的某种组合： w=α1x1+α2x2+…+αn x n 式子中的αi是一个一个的数（在严格的证明过程中，这些α被称为拉格朗日乘子），而x i是样本点，因而是向量，n就是总样本点的个数。为了方便描述，以下开始严格区别数字与向量的乘积和向量间的乘积，我会用α1x1表示数字和向量的乘积，而用
SVM 的分类原理 SVM 的主要思想可以概括为两点: (1) 它是针对线性可分情况进行分析,对于线性不可分的情况,通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分,从而使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能; (2) 它基于结构风险最小化理论之上在特征空间中建构最优分割超平面,使得学习器得到全局最优化,并且在整个样本空间的期望风险以某个概率满足一定上界。支持向量机的目标就是要根据结构风险最小化原理,构造一个目标函数将两类模式尽可能地区分开来,通常分为两类情况来讨论, (1) 线性可分,(2) 线性不可分。 1. 1 线性可分情况 在线性可分的情况下,就会存在一个超平面使得训练样本完全分开,该超平面可描述为: w ·x + b = 0 (1) 其中,“·”是点积, w 是n 维向量, b 为偏移量。 最优超平面是使得每一类数据与超平面距离最近的向量与超平面之间的距离最大的这样的平面. 最优超平面可以通过解下面的二次优化问题来获得： 满足约束条件： , i = 1 ,2 ,3 ,......, n. (3) 在特征数目特别大的情况,可以将此二次规划问题转化为其对偶问题： (4) (5) (6)
满足约束条件: (7) 这里是Lagrange 乘子, 是最优超平面的法向量, 是最优超 平面的偏移量,在这类优化问题的求解与分析中, KKT条件将起到很重要的作用,在(7) 式中,其解必须满足： (8) 从式(5) 可知,那些 = 0 的样本对分类没有任何作用,只有那些 > 0 的样本才对分类起作用,这些样本称为支持向量,故最终的分类函数为： (9) 根据f ( x) 的符号来确定X 的归属。 1. 2 线性不可分的情况 对于线性不可分的情况,可以把样本X 映射到一个高维特征空间H,并在此空间中运用原空间的函数来实现内积运算,这样将非线性问题转换成另一空间的线性问题来获得一个样本的归属. 根据泛函的有关理论,只要一种核函数满足Mercer 条件,它就对应某一空间中的内积,因此只要在最优分类面上采用适当的内积函数就可以实现这种线性不可分的分类问题. 此时的目标函数为： （10） 其相应的分类函数为: （11） 1. 3 内积核函数 目前有三类用的较多的内积核函数：第一类是 （12）