0x00 前言

之前在逻辑回归中也提到了多分类问题，但是仅仅介绍了其中一种情况。多分类还存在一些其他的方式与问题，在这里总结一遍，用作笔记。

除过那些直接可以由二分类算法推广到多分类的情况，我们就是基于一些策略利用二分类学习器来解决多分类问题。

0x01 一对一(One vs. One)

OvO策略是将N个类别，两两配对分类，一共就产生了N(N-1)/2个二分类任务。在测试阶段，我们将新样本提交给所有的分类器，一共得到N(N-1)/2个分类结果，而最终这个新样本属于哪一类，可以通过投票产生，即这N(N-1)/2个分类结果中，预测得到最多得那个分类作为最终分类结果。

0x02 一对其余(One vs. Rest)

OvR策略是将N个类别，每次分别取一类作一次正例，其余类都作为反例，一共训练N个分类器。在测试阶段，我们将新样本提交给所有分类器，一共产生N个分类结果，这N个结果中置信度最高的一个就是最终结果。

0x03 多对多(Many vs. Many)

MvM策略是每次将一部分类作为正类，一部分其他类作为反类。MvM的正反类构造不能随意选取，必须有特殊的设计。

最常用的MvM技术是“纠错输出码”(Error Correcting Output Codes)

纠错输出码是将编码的思想引入类别拆分，并尽可能在解码的过程中具有容错性。纠错输出码的工作过程：

• （1）编码：对N个类别做M次划分，每次划分将一部分类别划为正类，一部分划为反类，从而形成一个二分类训练集。这样一共产生M个训练集，可以训练出M个分类器。
• （2）解码：M个分类器分别对测试样本进行预测，这些预测标记组成一个编码，将这个预测编码与每个类别各自的编码进行比较，返回其中距离最小的类别作为最终预测结果。

类别划分时使用编码矩阵表示，目前主要的编码矩阵是二元码和三元码：

• 二元码： 每个类别有正类、反类两种情况。
• 三元码： 每个类别有正类、反类、停用类三种情况。

如图所示：

以二元码为例，图中使用五个分类器进行MvM分类，然后根据对不同类别的正反分类构成了黑白相间的编码矩阵。

在解码时，我们将样例输入到五个分类器中，得到一个长度为5的测试样例，然后跟矩阵中c1、c2、c3、c4四个类别的编码方式比较，计算其欧氏距离，距离最小的类别c3就是最终预测结果，也就是说此样例被分类到c3。

如果MvM用到的分类器越多，横轴也会越长，编码长度也就越长，这样即使有个别分类器预测错误，也不会影响最终结果。也就是说，分类器越多纠错能力越强。不过分类器越多，我们需要训练的次数也就越多，计算量就会增大，所以应当根据实际情况选择合适的分类器数量。

0x04 类别不平衡问题

在通常的分类任务中，我们默认几类几类情况的发生几率差距不是特别大，但是如果某一类情况发生几率十分大，比如99.9%，另一类发生几率特别小，比如0.1%。

这种情况下，我们的样本正例太多，反例太少，学习器往往会出现一些误差。

此时我们需要用m+表示正例数目，m-表示反例数目，观测几率就是m+/m-，这个时候我们只需要分类器预测几率高于观测几率就应判定为正例，即

但是我们的分类器是根据y/(1-y)进行决策的，为了适应它，我们只需要“再缩放”一下：

0x05 参考文档

《机器学习》——周志华