理解SVM（三）——扩展到多类

矫情吗；* 2022-08-14 04:50 211阅读 0赞

**理解SVM（三）——扩展到多类**

前面两个系列分别讲诉了SVM的基本原理和代码实现，如何解决线性不可分情况。这一次我们讲解一下SVM的最后一篇：SVM解决多类分类问题。

# 1. one vs. other #

这种改进SVM的方法简单粗暴，也易于理解。详细来说，比如我们的数据有5个类别。

Step 1：把类别1的样本定为正样本，其余2，3，4，5类的样本定为负样本。使用SVM分类器，得到一个二类分类器；

Step 2：把类别2的样本定为正样本，其余1，3，4，5类的样本定为负样本。使用SVM分类器，得到一个二类分类器；

Step 3：把类别3的样本定为正样本，……

Step 4：把类别4的样本定为正样本，……

Step 5：把类别5的样本定为正样本，……

Step 6：对测试样本，依次使用上面训练学习得到的5个分类器，每个分类器都可以得出结论，要么是第i类，要么就是其他（the other），直到我们发现有一个分类器说这样测试样本是我的，即可。

这样改进方法比较简单，时间复杂度也不是很高。但是，仔细想一下问题来了~有时候会出现5个分类器都说这样测试样本是自己的，或者都是不是自己的……这个时候怎么办？

如果说都是自己的，这叫分类重叠现象。这个可以选择SVM的间隔最大的那个分类器确定最终结果，或者使用投票的原则；

如果说都不是自己的，这叫不可分类现象。这个时候就不好解决了，得不到正确的结果。

此外，这种方法还有一个缺点：认为造成了类不平衡问题。而且，当数据类别很多的时候，other那一类的数据量会是one这一类的好多倍，SVM分类器会严重错误的把结果偏向于other的大类，这个时候就不是不可分类现象了，而是你SVM分类器就给直接分错了……对于类不平衡问题，我们后面的博客还会讲到。

# 2. one vs. one #

这种方法还是把多类问题转化为多个二类问题，只不过每个二类问题中都是“one vs. one”的方式。这个时候就没有类不平衡问题了。

Step 1：把类别1的样本定为正样本，类别2定为负样本。使用SVM分类器，得到一个二类分类器；

Step 2：把类别1的样本定为正样本，类别3定为负样本。使用SVM分类器，得到一个二类分类器；

……（一共有C(5, 2)=10个分类器）

Step 11：让测试样本依次通过后面的分类器做判断，每次都会得到是否为第1类还是第2类，然后给5个类别投票，选择最高的作为最后的结果（一个类得票最高为4票）。

这种方法也有分类重叠的现象。而且，当数据集类别增多的时候，我们需要学习的二类分类器就会很多，比刚才的那种one vs. other的方法多很多，时间复杂度受不了~

# 3. DAG方式 #

类似于上面“one vs. one”的方法，我们可以把每个二类分类器作为结点，构建一个有向无环图。如下图所示：

![Center][]

图中很形象的描述了该方法的决策过程，即从上而下的分类，每次分类器的结果决定了往左右哪个方向。继续判断，直到到达叶子，每个叶子对应这一个类别。该方法不需要运行每个分类器，提高了测试速度，而且避免了投票数一样大的时候分类重叠现象。但是，该方法的缺点就是“误差累积”，假设第一个节点的分类器就直接分错了，那么后面就是一直跟着错。

# 4. 基于决策树的方法 #

其实上面2，3方法需要训练的分类器的数量都是可怕的，基于决策树的方法可以减少学习二类分类器个数的问题。对于一个数据集，我们可以采用一些聚类的方法（例如Kmeas）把数据集分成两个子类，然后对两个子类进一步划分，如此循环，直到子类中只包含一个类别为止。这样，就得到了一个倒立的二叉树。最后，在二叉树各决策节点训练支持向量机分类器，这里我们就可以发现我们需要的分类器已经减少了很多了。这里，我们构造不同的树的结构（不一定是完全二叉树），就会得到不同的方法。但是使用完全二叉树结构时，需要学习的二类分类器数目是最少的。

# 5. 基于纠错输出编码的方法 #

假设一个数据集一共有K类，我们使用L种两类分类器（不仅仅是SVM），就会得到L个分类结果，每个结果用+1和-1来表示。这样，对于K类数据集，我们就可以学习到一个K\*L的矩阵。

然后，来了一个测试样本，我们就用同一样的方法得到测试样本的长度为L的向量，拿这个向量和K\*L矩阵中的每一行做Hamming distance，距离最小的即为该测试样本的分类结果。

以上5类方法都各有优缺点，具体应用的时候可以选择效果最好的一种使用。不过现在也已经出现了很多直接面向多类分类的数据挖掘方法。后面我们再一一介绍。

注意，上文中涉及到了类不平衡学习问题，后面会专门开了专栏来说这类问题的几大解决方法，请持续关注本博客~谢谢~~

[Center]: /images/20220810/676150d35eec4866b4c5eb1fc59ea86f.png

发表评论取消回复

表情：

评论列表（有 0 条评论，211人围观）

还没有评论，来说两句吧...

相关阅读

相关 SVM之KKT条件理解

在SVM中，我们的超平面参数最终只与间隔边界上的向量（样本）有关，故称为支持向量机。求解最优超平面，即求最大化间隔，或最小化间隔的倒数：||w||2/2，约束条件为yi(w

Love The Way You Lie/ 2023年06月02日 09:12/ 0 赞/ 28 阅读

相关多元分类SVM（多类别SVM）程序使用说明

目录操作流程程序的数据格式 matlab程序操作流程首先，在这个网站上下载libsvm程序包[http://download.csdn.ne

悠悠/ 2022年09月25日 11:27/ 0 赞/ 242 阅读

相关详解SVM支持向量机算法(三:软间隔SVM和非线性SVM)

目录背景线性支持向量机(软间隔SVM) 硬间隔的问题引入松弛变量目标函数的优化生成拉格朗日函数软间隔原始问题软间隔对偶问题求解思路：

末蓝、/ 2022年09月16日 13:20/ 0 赞/ 323 阅读

相关理解SVM（三）——扩展到多类

理解SVM（三）——扩展到多类前面两个系列分别讲诉了SVM的基本原理和代码实现，如何解决线性不可分情况。这一次我们讲解一下SVM的最后一篇：SVM解决多类分类问题。

矫情吗；*/ 2022年08月14日 04:50/ 0 赞/ 212 阅读

相关支持向量机通俗导论（理解SVM的三层境界）

声明：本文转载自http://blog.csdn.net/v\_july\_v/article/details/7624837 前言动笔写这个支持向量机(suppor

怼烎@/ 2022年07月26日 05:26/ 0 赞/ 188 阅读

相关支持向量机通俗导论（理解SVM的三层境界）

> > > 支持向量机通俗导论（理解SVM的三层境界）作者： July、pluskid ；致谢：白石、J erryLead 出处：结构之法算法之道 blog 。

喜欢ヅ旅行/ 2022年07月13日 13:28/ 0 赞/ 201 阅读

相关学习SVM（三）理解SVM中的对偶问题

[ 学习SVM（一） SVM模型训练与分类的OpenCV实现][_SVM_ SVM_OpenCV] [学习SVM（二）如何理解支持向量机的最大分类间隔][SVM_]

我就是我/ 2022年06月13日 05:23/ 0 赞/ 238 阅读

相关学习SVM（五）理解线性SVM的松弛因子

[ 学习SVM（一） SVM模型训练与分类的OpenCV实现][_SVM_ SVM_OpenCV] [学习SVM（二）如何理解支持向量机的最大分类间隔][SVM_]

àì夳堔傛蜴生んèń/ 2022年06月12日 13:14/ 0 赞/ 285 阅读

相关简单通俗理解，使用SVM

一.SVM的分类表达式: y = wx+b,w表示权重，b表示偏置可以看出来，是一个线性分类器，那么就只能解决一个，就是我们输入的数据是线性可分的所以总的来说:

左手的ㄟ右手/ 2022年05月20日 06:13/ 0 赞/ 296 阅读

相关 SVM理解之核函数

核函数是什么在使用SVM分类器处理非线性问题时，核函数是绕不过的坎，其实关于核函数，首先需要记住这两句话： 1. 核函数可以使向量直接在原来的低维空间中进行内积计算

た入场券/ 2022年05月09日 00:22/ 0 赞/ 219 阅读