基于支持向量机的分类法

主讲：周润景教授单位：电子信息工程学院基于支持向量机的分类法目录支持向量机的简介支持向量机的基本思想支持向量机的几个主要优点多类分类问题MATLAB实现方法结论支持向量机的简介从观测数据中学习归纳出系统运动规律，并利用这些规律对未来数据或无法观测到的数据进行预测一直是智能系统研究的重点。传统学习方法中采用的经验风险最小化（ERM）虽然误差最小化，但不能最小化学习过程的泛化误差。ERM不成功的例子就是神经网络中的过学习问题。为此由Vapnik领导的AT&TBell实验室研究小组在1963年提出的一种新的非常有潜力的分类技术，支持向量机(SupportVectorMachine,SVM）是一种基于统计学习理论的模式识别方法，主要应用于模式识别领域。支持向量机的基本思想是在样本空间或特征空间构造出最有超平面，使得超平面与不同类样本集之间的距离最大，从而达到最大的泛化能力。支持向量机的基本思想SVM是从线性可分情况下的最优分类面发展而来的，基本思想可用下图的两类线性可分情况说明。实心点和空心点代表两类样本，实线P0、P1为分类线。两个虚线分别为过各类中离分类线最近的样本且平行于分类线的直线，它们之间的距离叫做分类间隔。支持向量机的基本思想所谓最优分类线就是要求分类线不但能将两类正确分开（训练错误率为零），而且使分类间隔最大。分类线方程为此时分类间隔为，使间隔最大等价于使最小，则可以通过求的极小值获得分类间隔最大的最优超平面。这里的约束条件为：RbRwbxwm,,0w/22w2/2wnibxwyii,...,101).(支持向量机的基本思想该约束优化问题可以用Lagrange方法求解，令其中为每个样本的拉氏乘子，由L分别对b和ｗ导数为0，可以导出：)1).((21),,(12bxwywbwLiimii0iiimiiimiixywy110支持向量机的基本思想因此，解向量有一个由训练样本集的一个子集样本向量构成的展开式，该子集样本的拉氏乘子均不为0，即支持向量。拉氏乘子为0的样本向量的贡献为0，对选择分类超平面是无意义的。于是，就从训练集中得到了描述最优分类超平面的决策函数即支持向量机，它的分类功能由支持向量决定。这样决策函数可以表示为：)).(sgn()(1bxxyxfiimii支持向量机的优点（1）它是专门针对有限样本情况的，其目标是得到现有信息下的最优解而不仅仅是样本数趋于无穷大时的最优值；（2）算法最终将转化成为一个二次型寻优问题，从理论上说，得到的将是全局最优点，解决了在神经网络方法中无法避免的局部极值问题；（3）算法将实际问题通过非线性变换转换到高维的特征空间(FeatureSpace)，在高维空间中构造线性判别函数来实现原空间中的非线性判别函数，特殊性质能保证机器有较好的推广能力，同时它巧妙地解决了维数问题，其算法复杂度与样本维数无关。多类分类问题基本的支持向量机仅能解决两类分类问题，一些学者从两个方向研究用支持向量机解决实际的多类分类问题：一个方向就是将基本的两类支持向量机(Binary-classSVM，BSVM)扩展为多类分类支持向量(Multi-ClassSVM，MSVM)，使支持向量机本身成为解决多类分类问题的多类分类器;另一方向则相反,将多类分类问题逐步转化为两类分类问题,即用多个两类分类支持向量机组成的多类分类器。多类分类问题多类分类支持向量机MSVM：实际应用研究中多类分类问题更加常见，只要将目标函数由两类改为多类(k类)情况，就可以很自然地将BSVM扩展为多类分类支持向量机MSVM，以相似的方式可得到决策函数。多类分类问题基于BSVM的多类分类器(1)1-a-r分类器(One-against-restclassifiers)这种方案是为每个类构建一个BSVM，如图，对每个类的BSVM，其训练样本集的构成是：属该类的样本为正样本，而不属于该类的其他所有样本为都是负样本，即该BSVM分类器就是将该类样本和其他样本分开。所以在1-a-r分类器过程中训练样本需要重新标注，因为一个样本只有在对应类别的BSVM分类器是是正样本，对其他的BSVM分类器都是负样本。类A类B类C分类超平面多类分类问题(2)1-a-1分类器(One-against-oneclassifiers)对1-a-1分类器，解决k类分类问题就需要个BSVM，因为这种方案是每两个类别训练一个BSVM分类器，如图，最后一个待识别样本的类别是由所有个BSVM“投票”决定的。类A类B类C分类超平面多类分类问题(3)多级BSVM分类器这种方案是把多类分类问题分解为多级的两类分类子问题，如图，两种典型方案，其中A、B、C、D、E、F分别为7个不同的类ABCDEFABCDEFBDACACEFEFACBDEFACEFBDABCDBDFEABCDFEMATLAB实现方法设计流程:MATLAB实现方法matlab中所需调用函数●model=svmtrain(train_labels,train_metrix,[‘libsvm_options‘])--train_labels：训练集的标签--train_metrix：训练集的属性--libsvm_options：一些选项参数--model：训练得到的分类模型●[predict_label,accuracy]=svmpredict(test_labels,test_metrix,model)--test_labels：测试集的标签--test_metrix：测试集的属性--model：由svmtrain得到的分类模型--predict_label：预测得到的测试集的标签--accuracy：分类准确率MATLAB实现方法在程序开始要将数据归一化处理，归一化的程序如下：functionnormal=normalization(x,kind)ifnargin2kind=2;%kind=1or2表示第一类或第二类规范化end[m,n]=size(x);normal=zeros(m,n);%%normalizethedataxto[0,1]ifkind==1fori=1:mma=max(x(i,:));mi=min(x(i,:));normal(i,:)=(x(i,:)-mi)./(ma-mi);MATLAB实现方法endend%%normalizethedataxto[-1,1]ifkind==2fori=1:mmea=mean(x(i,:));va=var(x(i,:));normal(i,:)=(x(i,:)-mea)/va;endendMATLAB实现方法SVM的MATLAB完整源程序如下：clear;clc;loadSVM;train_train=[train(1:4,:);train(5:11,:);train(12:19,:);train(20:30,:)];%手动划4分类train_target=[target(1:4);target(5:11);target(12:19);target(20:30)];test_simulation=[simulation(1:6,:);simulation(7:11,:);simulation(12:24,:);simulation(25:30,:)];test_labels=[labels(1:6);labels(7:11);labels(12:24);labels(25:30)];MATLAB实现方法%train_train=normalization(train_train',2);%test_simulation=normalization(test_simulation',2);%train_train=train_train';%test_simulation=test_simulation';%bestcv=0;%forlog2c=-10:10,%forlog2g=-10:10,%cmd=['-v5-c',num2str(2^log2c),'-g',num2str(2^log2g)];%将训练集分为5类%cv=svmtrain(train_target,train_train,cmd);%if(cv=bestcv),%bestcv=cv;bestc=2^log2c;bestg=2^log2g;%endMATLAB实现方法%end%end%fprintf('(bestc=%g,g=%g,rate=%g)\n',bestc,bestg,bestcv);%cmd=['-c',num2str(bestc),'-g',num2str(bestg)];%model=svmtrain(train_target,train_train,cmd);model=svmtrain(train_target,train_train,'-c2-g0.2-t1');%核函数[predict_label,accuracy]=svmpredict(test_labels,test_simulation,model);holdofff=predict_label';index1=find(f==1);index2=find(f==2);MATLAB实现方法index3=find(f==3);index4=find(f==4);plot3(simulation(:,1),simulation(:,2),simulation(:,3),'o');line(simulation(index1,1),simulation(index1,2),simulation(index1,3),'linestyle','none','marker','*','color','g');line(simulation(index2,1),simulation(index2,2),simulation(index2,3),'linestyle','none','marker','','color','r');line(simulation(index3,1),simulation(index3,2),simulation(index3,3),'linestyle','none','marker','+','color','b');line(simulation(index4,1),simulation(index4,2),simulation(index4,3),'linestyle','none','marker','','color','y');box;gridon;holdon;xlabel('A');ylabel('B');zlabel('C');title('支持向量机分析图');MATLAB实现方法程序运行完之后，出现如图分类结果图。在MATLAB命令窗口出现如下结果：Accuracy=96.6667%(29/30)(classification)predict_label=111111222223333332333333444444从图中可以看出分类正确率为96.6667%，其中有一个分错了。四、总结◆SVM具有优良的学习能力和推广能力，能够有效的克服“维数灾难”和“过学习”的问题。而SVM的参数是影响分类精度、回归预测的重要因素。仿真结果表明，预测结果可靠，可以为数据提供很好的参考价值信息。