1、Support Vector Machine支持向量机提纲1.SVM的有关概念介绍2.SVM问题的数学表示和推导简单的最优分类面SVM广义最优分类面 SVM非线性最优分类面SVM3.支持向量机工具箱SVM的描述 支持向量机支持向量机是在统计学习理论的基础上发展出来的一种新的机器学习方法，它是统计学习理论中最年轻的部分，也是最实用的部分。Vapnik等人在20世纪60年代开始研究有限样本下的机器学习问题，随着理论研究的逐步成熟，在90年代中期，他们提出了一个较完善的基于有限样本的理论体系，即统计学习理论(Statistical Learning Theory，SLT),与传统统计学理论相比，统计
2、学习理论是一门专门研究小样本情况下，机器学习规律的理论，其核心问题是寻找一种归纳原则以实现最小化风险泛函，使其具有最佳的推广能力。传统的统计统计模式识别方法只有在样本趋向无穷大时，其性能才有理论的保证。统计学习理论（STL）研究有限样本情况下的机器学习问题。SVM的理论基础就是统计学习理论。传统的统计模式传统的统计模式识别方法在进行机器学习时，强调经验风险最小化经验风险最小化。而单纯的经验风险最小化会产生“过学习问题”，其推广能力较差。推广能力推广能力是指:将学习机器(即预测函数,或称学习函数、学习模型)对未来输出进行正确预测的能力。“过学习问题过学习问题”：某些情况下，当训练误差过小反而会导
3、致推广能力的下降。例如：对一组训练样本(x,y),x分布在实数范围内，y取值在0，1之间。无论这些样本是由什么模型产生的，我们总可以用y=sin(w*x)去拟合，使得训练误差为0 统计学习理论统计学习理论是小样本统计估计和预测学习的最佳理论。模式识别问题的一般描述 已知：n个观测样本train set，(x1,y1),(x2,y2)(xn,yn),学习到一个假设H=f(x,w)作为预测函数,其中w是广义参数.满足条件：期望风险最小 损失函数),(),(,()(yxdFwxfyLwR ),(1),(0),(,(wxfywxfywxfyL 期望风险R(w)要依赖联合概率F(x,y)的信息，实际问题
4、中无法计算。一般用经验风险Remp(w)代替期望风险R(w)nwxfyLnwRniiiemp错错分分数数 1),(,(1)(一般模式识别方法的问题 经验风险最小不等于期望风险最小，不能保证分类器的推广能力;经验风险只有在样本数无穷大趋近于期望风险，需要非常多的样本才能保证分类器的性能;需要找到经验风险最小和推广能力最大的平衡点。SVM的理论基础 根据统计学习理论，学习机器的实际风险由经验风险值和置信范围值两部分组成。而基于经验风险最小化准则的学习方法只强调了训练样本的经验风险最小误差，没有最小化最小化置信范围值，因此其推广能力较差。Vapnik 与1995年提出的支持向量机（Support V
5、ector Machine,SVM）以训练误差作为优化问题的约束条件，以置信范围值最小化作为优化目标，即SVM是一种基于结构风险最小化结构风险最小化准则的学习方法，其推广能力明显优于一些传统的学习方法。支持向量机最早是运用于两类分类问题，且大多数情况是非线性的。其基本思想是：其基本思想是：首先通过一个非线性变换将输入空间中的向量映射到一个高维的特征空间，然后再在这个高维特征空间中求解最优分类超平面，而这种非线性变换是通过定义适当的内积（核）函数来实现的，也就是说，将高维特征空间中的特征向量和特征空间中向量的内积化为原空间中的核函数计算。目标：找到一个超平面，使得它能够尽可能多的将两类数据点正确
6、的分开，同时使分开的两类数据点距离分类面最远。解决方法：构造一个在约束条件下的优化问题，具体的说是一个受限二次规划问题,求解该问题，得到分类器。线性判别函数和判别面 一个线性判别函数(discriminant function)是指由x的各个分量的线性组合而成的函数 两类情况:对于两类问题的决策规则为 如果g(x)=0，则判定x属于C1 如果g(x)=0，则判定x属于C1，如果g(x)0是一个常数，它控制对错分样本惩罚的程是一个常数，它控制对错分样本惩罚的程度。度。问题求解 将上述问题表示成拉格朗日乘子式Kuhn-Tucker条件iiiiiiiiiibwxyCwL)(1|212000)(100
7、00iiiiiiiiiiiiiiiiiwbwxyCLybLxyw 得到 只要确定，便可解出w,b0000)(100iiiiiiiiiiiiiiiiCbwxyCyxyw 将上述条件代入L中 新的优化问题iiiiiiiiiiiiiCybwxywL)(|2120021,iiiijijijijiiiyCxxyyL 已知：n个观测样本，(x1,y1),(x2,y2)(xn,yn)求解 根据，求得w,b，得到最优分类面0021max,iiiijijijijiiiyCxxyy 非线性分类面 非线性可分的数据样本在高维空间有可能转化为线性可分。在训练问题中，涉及到训练样本的数据计算只有两个样本向量点乘的形式
8、使用函数 ,将所有样本点映射到高为空间，则新的样本集为 设函数nm:),().(),(11nnyxyx)()(),(2121xxxxKSVM的一般表示 已知：n个观测样本，(x1,y1),(x2,y2)(xn,yn)求解 最优非线性分类面为00),(21max,iiiijijijijiiiyCxxKyybxxKybxxybxwxgiiiiiiii),()()()()(支持向量机 上节所得到的最优分类函数为：该式只包含待分类样本与训练样本中的支持向量的内积 运算，可见,要解决一个特征空间中的最优线性分类问题,我们只需要知道这个空间中的内积运算即可。对非线性问题,可以通过非线性变换转化为某个高维空
9、间中的线性问题,在变换空间求最优分类面.这种变换可能比较复杂,因此这种思路在一般情况下不易实现.*1()sgnsgn()liiiif xwxby x xb SVM本质上是两类分类器.常用的SVM多值分类器构造方法有:支持向量机 核:11221,21,21212,(,)()().(,.)()(),.,()=()|:()()(,)lnKx zXK x zxzXFxxxxxxXFxxXx xx xxxx x 核是一个函数对所有满足这里 是从输入空间 到特征空间 的映射将输入空间 映射到一个新的空间例如(,)()()iiiiK x yxy*1()sgn(,)liiiif xy K x xb.),(21
10、为输入向量为输入向量dxxxx.),(sgn(1为为输输出出函函数数bxxKwyisii .),(,),(),(21个个支支持持向向量量的的内内积积与与输输入入向向量量是是sxxxKxxKxxKs.为为权权值值iiiyaw 通常的内核函数 线性内核 径向基函数内核RBF 多项式内核 S形内核jijixxxxK),(qjijixxxxK 1)(),(|exp),(22jijixxxxK)(tanh(),(cxxxxKjiji支持向量机作为一种在统计学习理论基础上发展起来的机器学习方支持向量机作为一种在统计学习理论基础上发展起来的机器学习方法是目前运用于数据挖掘和模式识别的一个非常强大的工具。具有
11、法是目前运用于数据挖掘和模式识别的一个非常强大的工具。具有以下优点：以下优点：1.模型结构简单，参数较少；2.建模所需要的样本较少，专门针对小样本情况；3.具有较好的泛化能力，对新样本往往能显示出较好的推广能力；4.能够较好的处理非线性和高维数的问题；5.有多种核函数可供选择，建立不同的分类曲面，解决不同类型数据的问题；6.从理论上，算法得到的是全局最优，解决了神经网络方法无法避免的局部最优问题。常用的模型评价方法 1.旁置法（holdout method）：将全部数据集划分为相互独立的训练集、验证集和测试集。第一阶段，对训练集进行训练，以一种或多种学习算法创建分类器，构建模型的基本结构；第二
12、阶段，将训练好的分类器用于验证集，根据最好的测试成绩，优化参数或者选择最优参数；第三阶段，将经过优化的分类器用于测试集，计算模型预测的误差。有时为了减少旁置法在取样时不均匀造成的偏差，可以重复整个过程，每次取不同的随机样本进行训练和测试，将多次得到的误差取平均得到一个综合误差率，即重复旁置法。常用的模型评价方法 2.交叉验证(cross-validation)：首先将数据集大致均分为n个子集，比如 n=5,10，20等。每次将其中一个子集旁置作为测试集，其它的n-1个子集合并作为训练集，轮流进行。每个样本都将有一次作为测试对象，而n-1次参加某个学习方案的训练，即n折交叉验证。最后将每次的误差
13、估计值平均而得到一个综合误差估计。其中10折交叉验证在实践中被认为是标准方法，而5折或20折也经常用到，其效果相差不大。为了得到更加可靠的误差估计，可以采用相同的学习方案在相同的数据集上重复10次不同的10折交叉验证（即每次对数据集的划分不同），然后取其均值。3.留一法(leave-one-out)：留一法可以理解为特殊的交叉验证：即m折（m为数据集的样本总数）交叉验证。每次将数据集中的一个样本作为测试集，而其它全部作为训练集。最后将m个误差结果取均值。留一法的优点时，每次让尽可能多的样本参与训练。它的试验结果具有确定性，因为每个样本均有一次单独作为测试集，不存在随机取样。4.自引导法(boo
14、tstrap)：基于统计学中的有放回重复抽样产生训练集。设数据集的样本总数为m，用又放回的方式在数据集中随机抽取m个样本作为训练集。不可避免的，在训练集中会有一些重复的样本，而原来的数据集中也会有一些样本没有被抽取到，将这些未被抽到的样本作为测试集。用训练集训练一个学习系统，并用测试集计算误差率。由于训练集可能含有较多的重复样本，所以得到的结果一般较为悲观。所以将测试集误差率e1和训练集数据计算的重新代入误差率e2（即训练集自测试误差率）进行组合，得到最终的误差率估计值e=0.632*e1+0.368*e2.然后将整个自引导过程重复进行几次，取得不同的又放回重复抽样的样本作为训练集，测试结果误
15、差率取平均值。值得一提的是值得一提的是，在随机抽取训练集时，我们可以采用分层技术。确保在训练集和测试集中每个类别或者数据段的比例相当。这种做法是非常有必要的，可以防止训练集和测试集数据的样本代表性不一致而产生的偏差。对应分层技术，有分层旁置、分层n折交叉验证，而留一法和自引导法则不能采用分层。常用的分类模型评价指标 1.真阳性(TP):阳性数据中被预测为阳性的数据2.假阳性(FP):阴性数据中被预测为阳性的数据3.真阴性(TN):阴性数据中被预测为阴性的数据4.假阴性(FN):阳性数据中被预测为阴性的数据真阳性(TP),假阳性(FP),真阴性(TN),假阴性(FN)1.灵敏度(Sensitiv
16、ity,Sn):对于阳性的数据，能够预测成“真”的比例2.特异性(Specificity,Sp):对于阴性的数据，能够预测成“假”的比例3.准确性(Accuracy,Ac):对于整个数据集预测正确的比例FNTPTPSnFPTNTNSp4.马修相关系数(Mathew correlation coefficient,MCC):当阳性数据的数量与阴性数据的数量差别较大时，能够更为公平的反映预测能力，值域-1,1FNTNFPTPTNTPAc)()()()()()(FNTNFPTPFPTNFNTPFPFNTNTPMCC5.ROC5.ROC曲线曲线 是用真阳性率和假阳性率作图得出的曲线，它可表示灵敏度和特
17、异度之间的关系。（底下面积越大越好，永不会是1，只能接近1）ROC曲线也可用来比较两种和两种以上诊断试验的诊断价值，从而帮助临床医师作出最佳选择。ROC曲线是一种全面、准确评价诊断试验非常有效的方法，并可以比较两种或多种诊断试验的诊断价值，除了直观方法比较外，还可以计算ROC曲线下的面积，来比较几种诊断试验的诊断效率。ROC曲线下的面积越大，越接近1.0，其诊断的真实度越高，越接近0.5，其诊断的真实度越差。回归模型评价指标 21122112111)()()()(liiliiliiliiliiliiliiiyylxfxflyxfyxflr皮尔逊相关系数 r 的值介于-1到1之间，用来度量实验值
18、和预测值之间的线性相关性。若相关系数r=0,则表示二者之间没有线性相关关系；若r 0，则说明二者之间成正相关；反之，若r traindata.txt 完整的命令格式为:svm-scale l xlower-u xupper-y ylower yupper-s scale_rule yuandata.txt resultdata.txt svm-scale-r scale_rule chentestdata.txttestdata.txt3.现在是通过gridregression.py函数进行参数寻优。Python.exe F:libsvm-2.88pythongridregression.py
19、-svmtrain F:libsvm-2.88windowssvm-train.exe-gnuplot F:gnuplotbinpgnuplot.exe-log2c-10,10,1-log2g-10,10,1-log2p-10,10,1-v 10-s 3-t 2 F:libsvm-2.88windowschentraindata.txt F:python26gridregression_data.parameter.txt回车 到F:Python26中会有一个gridregression_data.parameter出现，打开看结果.最后一行分别为c,g,p,mse。其中mse没有多大用，当然
20、小点更好。上图是我的结果：c=8.0 g=2.0 p=0.25 mse=0.387105.参考：有人做的data训练时c=256.0,g=0.25,p=2.0,mse=88.1545，而test测试时mse=401.938也用了.5.用最优参数训练模型svm-train-s 3-t 2-c 8.0-g 2.0-p 0.25 chentraindata.txt chentrain.model6.训练好了紧接着对test文件预测svm-predict chentestdata.txt chentrain.model.txt chenout.txtWindows下会多一个chenout.txt文件，
21、得出的预测结果在out里面。如果还需要其它的评价指标，打开out和test文件比较一下结果差多少，自己去算吧。数据为1986年到2000年的交通量p=493 372 445;372 445 176;445 176 235;176 235 378;235 378 429;.378 429 561;429 561 651;561 651 467;651 467 527;467 527 668;.527 668 841;668 841 526;841 526 480;526 480 567;480 567 685t=176 235 378 429 561 651 467 527 668 841 52
22、6 480 567 685 507;LIB-SVM课堂训练：问题：问题：1.利用利用matlab将数据随机划分为训练集和测试集，比例为将数据随机划分为训练集和测试集，比例为2:1,并将并将其转化成其转化成lib-svm要求的格式要求的格式.2.将其进行归一化处理；将其进行归一化处理；3.训练网络，确定参数训练网络，确定参数4.反复试验，调整网络参数，选择最佳方案，保存网络；反复试验，调整网络参数，选择最佳方案，保存网络；5.用训练好的网络对测试集进行预测，并评价。用训练好的网络对测试集进行预测，并评价。课后作业：对于对于data.csv提供的数据分别进行提供的数据分别进行ann和和svm试验。试验。基本要求：基本要求：同课堂训练；增加要求：增加要求：将数据分为训练集、验证集、测试集进行旁置法测试；学有余力的同学可以考虑交叉验证。
