使用二分类学习器解决多分类问题的基本思路是“拆解法”，也就是将多分类任务拆分成多个二分类任务求解。这里主要介绍如何对多分类任务进行拆分，以及对拆分的多个分类器进行集成。

主要有三种拆分策略：“一对一”（One vs One，简称OvO）、“一对其余”（One vs Rest，简称OvR）和“多对多”（Many vs Many，简称MvM）.

一、“一对一”（OvO）

假设要对N个类别进行分类。OvO将这N个类别两两配对，所以一共产生个二分类任务，对应个分类器。

• 训练阶段：按照正常的二分类算法进行训练
• 测试阶段：新样本同时提交给所有分类器，于是我们得到个分类结果，最终的结果可用过投票产生：即把被预测得到最多的类别作为最终分类结果。

例：对四个类别进行分类，A、B、C、D。

训练阶段产生6个分类器：

测试阶段，若测试的结果为：

f1(x) = A、f2(x) = C、f3(x) = A、f4(x) = C、f5(x) = D、f6(x) = C

有3个分类器的结果都为C，所以就把C作为最终的结果。可以看出一对一训练的分类器多，所以训练的速度会比较慢。

二、“一对其余”（OvR）

OvR是每次将一个类的样例作为正例、所有其他类的样例作为反例来训练N个分类器。在测试时：

• 若仅有一个分类器预测为正类，则对应的类别标记作为最终分类结果；
• 若有多个分类器预测为正类，则通常考虑各个分类器的预测置信度，选择置信度最大的类别标记作为最终结果。

同样还是以上面的问题为例，产生4个分类器：

测试阶段：

f1(x) = -1、f2(x) = -1、f3(x) = +1、f4(x) = -1

所以x属于C类。

---

比较OvR和OvO：

可以发现，OvR训练的是N个分类器，而OvO训练的是个分类器。因此OvR的存储开销和测试时间都比OvO小。但是，从训练时每个学习器使用的样本数来看：OvR每个学习器使用了所有的样本，而OvO的每个学习器只用到两个类别的样本。因此在类别很多时，OvO的训练时间往往会比OvR小。

对于预测性能取决于数据的分布，在多数情形下差别不大.

三、“多对多”（MvM）

MvM是每次将若干个类作为正类，若干个其他类作为反类。可以看出MvM是OvR和OvO更一般的形式。

对于MvM正、反类的构造一种常用的技术是“纠错输出码”（Error Correcting Output Codes，简称ECOC）.主要分为两步：

• 编码：对N个类别做M次划分，每次划分将一部分类别划分为正类，一部分类别划分为反类，从而形成一个二分类训练集；这样一共产生M个训练集，可训练出M个分类器。
• 解码：测试时，M个分类器分别对测试样本x进行预测，这样预测的结果就形成了一个编码。将这个编码与每个类别各自的编码进行比较，找到距离最短的类别作为最终分类的结果。

还是以上面问题为例，假定M=5。训练结果如下:

测试阶段：

f1(x) = -1、f2(x) = -1、f3(x) = +1、f4(x) = -1、f5(x) = +1

所以测试样本的编码为（-1，-1，+1，-1，+1），到A、B、C、D对应编码的欧式距离为。比较发现距离C类最近，所以预测的结果就是C类。

       之所以称为纠错输出码，是因为在测试阶段，即使某个分类器预测错了，但是距离可能还是最小的。例如上面的测试样本正确的编码为（-1，+1，+1，-1，+1）也就是f2出错，但是还是能产生正确的分类C。

       一般来说，对于同一个学习任务，ECOC编码越长，纠错能力越强。但是，这意味着所需要的分类器就越多，开销就越大；另一方面，对有限类别数，可能的组合数目是有限的，码长超过一定的范围后就失去了意义。

---

参考资料：周志华老师《机器学习》

两种思路：

以SVM为例

1.one-versus-rest

思想：

假设一共有1,2,3,4,5个类别的数据

对于第1类，训练一个分类器：第1类是正样本，其余类的样本都是负样本

对于第2类，训练一个分类器：第2类是正样本，其余类的样本都是负样本

以此类推，一共训练出五个分类器

在预测阶段，对于输入的待分类样本，分别从第一个分类器开始询问是否属于该类别，该分类器“承认”，就将该样本判别为该类

存在的问题：

分类重叠现象：某个待分类样本被多个分类器“认领”（可以计算该样本与这些分类器对应超平面的距离，选择距离最远的）

不可分类现象：所有分类器都不“认领“”某个待分类样本（设置一个“其他类，专门用来存放异常类”，容易造成数据集偏斜问题？？？）

ps：这种方式会有数据集偏斜问题（因为是一对多），影响分类面划分的准确性，如下图：

数据集偏斜问题：在分类问题中某一类的样本数量与其他样本数据量相差较大（在分类的时候，数量多的正类可以把分类面向负类的方向“推”，因而影响了结果的准确性。）

解决方案：用“惩罚因子”让分类器对于样本数少的那一类的样本更加重视（软间隔的时候不能忽略，因为本来就少）

在确定惩罚因子的时候可以根据两种类别的数量或者利用超球的体积来衡量样本的空间分布

参考链接：https://blog.csdn.net/qq_26898461/article/details/50481792

2.one-versus-one

思路：

对于五分类问题

每一个分类器只负责分类两个类别，避免了数据集的偏斜问题，但是k个类别就要训练k*(k-1)/2个分类器

例如：

第一个分类器：负责二分类1,2

第二个分类器：负责二分类1,3

第二个分类器：负责二分类1,4.....以此类推，要想得到五分类器，需要训练10个分类器

待分类样本询问每一个分类器所属的类别，然后进行投票，票数最多的那个类别就作为预测类别

还是会存在分类重叠的问题，但是不会有不可分类问题（不可能所有类别的票数都为0）

改进的方法：

按照下图的方式组织one-vs-rest二分类器：

（有向无环图，因此这种方法也叫做DAG SVM）

这样在分类时,我们就可以先问分类器“1对5”（意思是它能够回答“是第1类还是第5类”），如果它回答5，我们就往左走，再问“2对5”这个分类器，如果它还说是“5”，我们就继续往左走，这样一直问下去，就可以得到分类结果。好处在哪？我们其实只调用了4个分类器（如果类别数是k，则只调用k-1个），分类速度飞快，且没有分类重叠和不可分类现象！

缺点在哪？假如最一开始的分类器回答错误（明明是类别1的文章，它说成了5），那么后面的分类器是无论如何也无法纠正它的错误的（因为后面的分类器压根没有出现“1”这个类别标签），其实对下面每一层的分类器都存在这种错误向下累积的现象

解决方法：

根节点的选取：（也就是如何选第一个参与分类的分类器），我们总希望根节点少犯错误为好，因此参与第一次分类的两个类别，最好是差别特别特别大，大到以至于不太可能把他们分错；或者我们就总取在两类分类中正确率最高的那个分类器作根节点，或者我们让两类分类器在分类的时候，不光输出类别的标签，还输出一个类似“置信度”的东东，当它对自己的结果不太自信的时候，我们就不光按照它的输出走，把它旁边的那条路也走一走

参考链接：https://blog.csdn.net/qq_26898461/article/details/50481803

                                                                   "微信公众号" 

本文同步更新在我的微信公众号里，地址：https://mp.weixin.qq.com/s/jfQNQ0mMe7a-k3IQNL_YAg

本文同步更新在我的知乎专栏里，地址：https://zhuanlan.zhihu.com/p/40485461

1. 摘要

贝叶斯分类器是一类分类算法的总称，这类算法均以贝叶斯定理为基础，故统称为贝叶斯分类器。而朴素贝叶斯分类器是贝叶斯分类器中最简单，也是最常见的一种分类方法。并且，朴素贝叶斯算法仍然是流行的十大挖掘算法之一，该算法是有监督的学习算法，解决的是分类问题。该算法的优点在于简单易懂、学习效率高、在某些领域的分类问题中能够与决策树、神经网络相媲美。但由于该算法以自变量之间的独立（条件特征独立）性和连续变量的正态性假设为前提，就会导致算法精度在某种程度上受影响。

2. 贝叶斯分类器的基础

要想学习贝叶斯算法的要领，我们需要先了解先验概率、后验概率的概念。

先验概率：是指根据以往经验和分析得到的概率。

举个例子：如果我们对西瓜的色泽、根蒂和纹理等特征一无所知，按照常理来说，西瓜是好瓜的概率是60%。那么这个概率P（好瓜）就被称为先验概率。

后验概率：事情已经发生，要求这件事情发生的原因是由某个因素引起的可能性的大小。

举个例子：假如我们了解到判断西瓜是否好瓜的一个指标是纹理。一般来说，纹理清晰的西瓜是好瓜的概率大一些，大概是75%。如果把纹理清晰当作一种结果，然后去推测好瓜的概率，那么这个概率P（好瓜|纹理清晰）就被称为后验概率。后验概率类似于条件概率。

联合概率：设二维离散型随机变量（X，Y）所有可能取得值为，记则称 为随机变量X和Y的联合概率。计算如下：

举个例子：在买西瓜的案例中，P（好瓜，纹理清晰）称为联合分布，它表示纹理清晰且是好瓜的概率。关于它的联合概率，满足以下乘法等式：

其中，P(好瓜|纹理清晰)就是后验概率，表示在“纹理清晰”的条件下，是“好瓜”的概率。P(纹理清晰|好瓜)表示在“好瓜”的情况下，是“纹理清晰”的概率。

全概率：如果事件组满足：

全概率公式的意义在于：当直接计算P（A）较为困难时，而 

的计算较为简单时，可以利用全概率公式进行计算P（A）。

举个例子：上面联合概率概念买西瓜的例子中，我们要计算P（好瓜，纹理清晰）联合概率时，需要知道P（纹理清晰）的概率。那么，如何计算纹理清晰的概率呢？实际上可以分为两种情况：一种是好瓜状态下纹理清晰的概率，另一类是坏瓜状态下纹理清晰的概率。纹理清晰的概率就是这两种情况之和。因此，我们可以推导出全概率公式：

贝叶斯定理：贝叶斯公式是建立在条件概率的基础上寻找事件发生的原因（即大事件A已经发生的条件下，分割中的小事件的概率），设 是样本空间Ω的一个划分，则对任一事件A（P(A)>0)，有贝叶斯定理：

对于每个特征x，我们想要知道样本在这个特性x下属于哪个类别，即求后验概率P(c|x)最大的类标记。这样基于贝叶斯公式，可以得到：

好了，学习完上面的先验概率、后验概率、联合概率、全概率、贝叶斯定理后，我们来小试牛刀一下：

西瓜的状态分为两种：好瓜与坏瓜，概率分别为0.6和0.4，并且好瓜里面纹理清晰的概率是0.8，坏瓜里面纹理清晰的概率是0.4。那么，我现在挑了一个纹理清晰的瓜，该瓜是好瓜的概率是多少？

很明显，这是一个后验概率问题，我们可以直接给出公式：

对公式里面出现的概率一个一个分析：

后验概率：P（纹理清晰|好瓜）=0.8

先验概率：P（好瓜）=0.6

后验概率：P（纹理清晰|坏瓜）=0.4

先验概率：P（坏瓜）=0.4

由上面分析的数值，我们可以直接求解上式：

这样，我们就计算得到了纹理清晰的情况下好瓜的概率是0.75。上面计算后验概率P（好瓜|纹理清晰）的公式就是利用了贝叶斯定理。

3. 朴素贝叶斯分类器

不难发现，基于贝叶斯公式（公式1）来估计后验概率P(c|x)的主要困难在于：类条件概率P(x|c)是所以属性上的联合概率（即x代表的是多个属性），难以从有限的训练样本直接估计而得。为了避开这个障碍，朴素贝叶斯分类器（naive Bayes classifier）采用了“属性条件独立性假设”:对已知类别，假设所有属性相互独立。换言之，假设每个属性独立地对分类结果发生影响。

朴素贝叶斯的算法步骤：

1. 设某样本属性集合其中 n 为属性数目，为x在第i属性上的取值。

2. 把这个样本划分为类别集合c中的某一类，。

3.  计算后验概率：

其中，，体现了朴素贝叶斯的精髓：每个特征相互独立。

那么，如何计算出 呢？首先找到一个已知类别分类集合，在这个集合中统计特征属性在各个类别下的条件概率，即得到我们要计算的。

值得注意的是：上式中的分母部分,对于所有的类别来说都是一样的。因此可以省略，针对不同的 ，仅需要比较的分子部分。

4. 如果 ，则样本在属性集 x下属于。

 温馨提示：如果对上面的算法步骤有点困惑，可以先看下面的例子，然后再回过头来理解朴素贝叶斯的算法步骤，理解效果会更好一点。

4. 朴素贝叶斯分类实例

我们已经了解了贝叶斯定理和朴素贝叶斯算法，可能你对上面的朴素贝叶斯算法还很困惑。这一小节，我们用一个实例来熟悉朴素贝叶斯算法。

我们还以买西瓜为实例。现在，我们有包含10个样本的数据集，这组数据集是以纹理、色泽、敲声为特征判断是好瓜还是坏瓜。数据集如下：

其中，纹理分为：清晰和模糊，色泽分为：青绿和乌黑，敲声分为：浊响、沉闷和清脆。不同的特征值组合对应着两类：好瓜还是坏瓜。

现在，我从超市中挑选了一个西瓜，它的纹理清晰、色泽青绿、敲声沉闷。我们可以根据样本数据集和朴素贝叶斯算法来计算该西瓜是好瓜还是坏瓜。

（1）首先，计算好瓜的情况：

先验概率：P（好瓜）=6/10=0.6

条件概率：P（纹理清晰|好瓜）=4/6=2/3

条件概率：P（色泽青绿|好瓜）=4/6=2/3

条件概率：P（敲声沉闷|好瓜）=2/6=1/3

计算后验概率P（好瓜|纹理清晰、色泽青绿、敲声沉闷）分子部分：

P（好瓜）x P（纹理清晰|好瓜）x P（色泽青绿|好瓜）x P（敲声沉闷|好瓜）= 0.6 × (2 / 3) × (2 / 3) × (1 / 3) = 4 / 45。

（2）然后，计算坏瓜的情况：

先验概率：P（坏瓜）=4/10=0.4

条件概率： P(纹理清晰|坏瓜) =1/4=0.25

条件概率： P(色泽青绿|坏瓜) =1/4=0.25

条件概率： P(敲声沉闷|坏瓜) =1/4 =0.25

计算后验概率P（坏瓜|纹理清晰、色泽青绿、敲声沉闷）分子部分：

P(坏瓜) × P(纹理清晰|坏瓜) × P(色泽青绿|坏瓜) × P(敲声沉闷|坏瓜) = 0.4 × 0.25 × 0.25 × 0.25 = 1 / 160。

（3）比较好瓜、坏瓜类别中的后验概率：

P（好瓜|纹理清晰、色泽青绿、敲声沉闷）> P（坏瓜|纹理清晰、色泽青绿、敲声沉闷）,即4/45 > 1/160，所以预测该纹理清晰、色泽青绿、敲声沉闷西瓜为好瓜。

5. 关于朴素贝叶斯容易忽略的点

（1）由上文看出，计算各个划分的条件概率 是朴素贝叶斯分类的关键性步骤，当特征属性为离散值时，能很方便的统计训练样本中各个划分在每个类别中出现的频率即可用来估计 ，下面重点讨论特征属性是连续值的情况。

当特征属性为连续值时，通常假定其值服从高斯分布（也称正态分布）。即：

则：

因此只要计算出训练样本中各个类别中此特征项划分的各均值和标准差，代入上述公式即可得到需要的估计值。均值与标准差的计算在此不再赘述。

（2） 另一个需要讨论的问题就是当怎么办，当某个类别下某个特征项划分没有出现时，就是产生这种现象，这会令分类器质量大大降低。为了解决这个问题，我们引入Laplace校准，它的思想非常简单，就是对每个类别下所有划分的计数加1，这样如果训练样本集数量充分大时，并不会对结果产生影响，并且解决了上述频率为0的尴尬局面。

6. 朴素贝叶斯分类器的优缺点

（1）优点：

1）简单易懂、学习效率高。

2）分类过程中时空开销小。

（2）缺点：

算法以自变量之间的独立（条件特征独立）性和连续变量的正态性假设为前提，会导致算法精度在某种程度上受影响。

Reference：

【1】《机器学习》，周志华著。

【2】通俗易懂！白话朴素贝叶斯

【3】Machine Learning -- Naive Bayes(朴素贝叶斯)

【4】教你明白啥是朴素贝叶斯分类器

【5】带你理解朴素贝叶斯分类算法