SVM多分类之一对一与一对多

冒泡~今天是在实验室划水的最后一天啦!
明天就可以回我滴厦门啦~来更个新！

关于SVM的基本原理可参考之前写过的《探索SVM（支持向量机）之旅》那个时候主要是理论了解也就知道个大概（虽然现在也只是了解更多一点罢了）
之前更多把SVM定义在二分类问题上今天着重记录的是SVM完成多分类。

SVM多分类

SVM算法最初是为二值分类问题设计的，当处理多类问题时，就需要构造合适的多类分类器。构造多分类器可以采用直接法或者间接法。 但是若采取直接法即SVM直接在目标函数上进行修改的话，将多个分类面的参数求解合并到一个最优化问题上，显然难度太大，其计算复杂度比较高，实现起来比较困难，只适合用于小型问题中。
所以重点讲一下间接法

间接法的分类：一对多、一对一

一对多（one-versus-rest,简称OVR SVMs）

训练时依次把某个类别的样本归为一类,其他剩余的样本归为另一类，这样k个类别的样本就构造出了k个SVM。分类时将未知样本分类为具有最大分类函数值的那类。
举个例子：假如我有四类要划分（也就是有存在四个Label），他们是A、B、C、D。　于是我在抽取训练集的时候，分别选取四个训练集如下：
1.A所对应的向量作为正集，B，C，D所对应的向量作为负集；
2.B所对应的向量作为正集，A，C，D所对应的向量作为负集；
3.C所对应的向量作为正集，A，B，D所对应的向量作为负集；
4.D所对应的向量作为正集，A，B，C所对应的向量作为负集；
{可以概括为自己一类为正集其余类为负集，N个类别（N个label）有N个训练集}
使用这四个训练集分别进行训练，然后的得到四个训练结果文件。在测试的时候，把对应的测试向量分别利用这四个训练结果文件进行测试。
最后每个测试都有一个结果f1(x),f2(x),f3(x),f4(x)。
于是最终的结果便是这四个值中最大的一个作为分类结果。
评价：
优点：训练k个分类器，个数较少，其分类速度相对较快。
缺点：①每个分类器的训练都是将全部的样本作为训练样本，这样在求解二次规划问题时，训练速度会随着训练样本的数量的增加而急剧减慢；
②同时由于负类样本的数据要远远大于正类样本的数据，从而出现了样本不对称的情况，且这种情况随着训练数据的增加而趋向严重。解决不对称的问题可以引入不同的惩罚因子，对样本点来说较少的正类采用较大的惩罚因子C；
③还有就是当有新的类别加进来时，需要对所有的模型进行重新训练。
{补充：有以下两个问题：
1.一个是一个样本可能同时属于几个类
那么看一下这个样本到各个超平面的距离，哪个远判给哪个
2.另一个是一个样本可能不属于任何一个
这样这个样本属于第N+1类，这个类的数目远大于N类之和，所以会造成数据偏斜问题}

一对一（one-versus-one,简称OVO SVMs或者pairwise）

其做法是在任意两类样本之间设计一个SVM，因此k个类别的样本就要设计k(k-1)/2个SVM。
当对一个未知样本进行分类时，最后得票最多的类别即为该未知样本的类别。
Libsvm（一个好用的包）中的多类分类就是根据这个方法实现的
{关于libsvm的使用说明等可以参考（https://www.cnblogs.com/jingyesi/p/4237155.html）}
举个例子：
　　假设有四类A,B,C,D四类。在训练的时候我选择A,B; A,C; A,D; B,C; B,D;C,D所对应的向量作为训练集（4X3/2=6），然后得到六个训练结果，在测试的时候，把对应的向量分别对六个结果进行测试，然后采取投票形式，最后得到一组结果。
投票是这样的：
　　A=B=C=D=0;
　　(A,B)-classifier 如果是A win,则A=A+1;otherwise,B=B+1;
　　(A,C)-classifier 如果是A win,则A=A+1;otherwise, C=C+1;
　　...
　　(C,D)-classifier 如果是C win,则C=C+1;otherwise,D=D+1;
　　The decision is the Max(A,B,C,D)
（也就是通过看投票的分数来看分类情况）
评价：这种方法虽然好,但是当类别很多的时候,model的个数是n*(n-1)/2,代价还是相当大的。与一对多相比不会有样本不属于任何一类的情形出现，但是复杂度变大了。

参考资料（https://blog.csdn.net/weixin_42296976/article/details/81946047）
（https://blog.csdn.net/xfchen2/article/details/79621396）

End~
一个半月的实验室划水要结束啦~
希望回家的小李也会更新!