​

文章目录

• 1、一对一（One vs. One，简称OvO）
• 2、一对其余（One vs. Rest，简称OVR）
• 3、多对多（Many vs. Many，简称MvM）

参考文章：多分类问题学习器拆分策略

现实中常遇到多分类学习任务，有些二分类学习方法可直接推广到多分类，但在更多情况下，我们是基于一些基本策略，利用二分类学习器来解决多分类问题。

不失一般性，考虑N个类别C₁，C₂，C₃，…，C_N，多分类学习的基本思路是“拆解法”，即将多分类任务拆解为若干个分类器（二分类）任务求解。具体来说，先对问题进行拆分，然后为拆出的每个二分类任务训练一个分类器；在测试时，对这些分类器的预测结果进行集成以获得最终的多分类结果。这里的关键是如何对多分类任务进行拆分，以及如何对多个分类器进行继承。最经典的拆分策略有三种：“一对一”（One vs. One，简称OvO）、“一对其余”（One vs. Rest，简称OvR）和“多对多”（Many vs. Many，简称MvM）。

1、一对一（One vs. One，简称OvO）

​给定数据集D={(x₁,y₁),(x₂,y₂),(x_m,y_m),y_i∈{C₁,C₂,…,C_n}。OvO将这N个类别两两配对,从而产生N(N-1)/2个二分类任务,例如OvO将为区分类别C_i和C_j训练一个分类器,该分类器把D中的C_i类样例作为正例,C_j类样例作为反例.在测试阶段,新样本将同时提交给所有分类器,于是我们将得到N(N-1)/2个分类结果,最终结果可通过投票产生:即把被预测得最多的类别作为最终分类结果.

2、一对其余（One vs. Rest，简称OVR）

OvR则是每次将一个类的样例作为正例、所有其他类的样例作为反例来训练N个分类器。在测试时若仅有一个分类器预测为正类，则对应的类别标记作为最终分类结果。若有多个分类器预测为正类，则通常考虑各分类器的预测置信度，选择置信度最大的类别标记作为分类结果。

OvO和OvR的对比:
OvO:训练N(N-1)/2个分类器，存储开销和测试时间大
训练只用两个类的样例，训练时间短
OvR：训练N个分类器，存储开销和测试时间小
训练用到全部训练样例，训练时间长
对于预测性能，则取决于具体的数据分布，在多数情形下两者差不多

3、多对多（Many vs. Many，简称MvM）

MvM是每次将若干个类作为正类，若干个其他类作为反类。显然，OvO和OvR是MvM的特例。
MvM的正、反类必须有特殊的设计，不能随意选取。

这里我们介绍一种最常用的MvM技术:“输出纠错码”（Error Correcting Output Codes,简称ECOC）
ECOC将编码的思想引入类别拆分中，并尽可能在解码过程中具有容错性。

ECOC的工作过程分为两个步骤:。
编码:对N个类别做M次划分，每次划分将一部分类别划为正类，一部分划为反类，从而形成一个二分类训练集;这样一共产生M个训练集，可以训练出M个分类器。

解码:M个分类器分别对测试样本进行预测，这些预测标记组成一个编码。将这个预测代码与每个类别各自的编码进行比较，返回其中距离最小的类别作为最终的预测结果。

C_i表示第i个类别；f_i表示第i个学习器

海明距离：在信息编码中，两个合法代码对应位上编码不同的位数称为码距；
计算海明距离的一种方法，就是对两个位串进行异或（xor）运算，并计算出异或运算结果中1的个数。例如110和011这两个位串，对它们进行异或运算，其结果是：110⊕011=101，异或结果中含有两个1，因此110和011之间的海明距离就等于2。

欧式距离：是一个通常采用的距离定义，指在m维空间中两个点之间的真实距离；

• ECOC编码对分类器错误有一定容忍和修正能力，编码越长、纠错能力越强（影响小，距离变化不大）。假设在预测时某个分类器出错了，例如 f₂ 出错从而导致了错误编码（-1 ，-1 ，+1，-1 ,+ 1 )，但基于这个编码仍能产生正确的最终分类结果C3。

• 然而，编码越长，意味着所需训练的分类器越多，计算、存储开销都会增大；另一方面，对有限类别数，可能的组合数目是有限的，码长超过一定范围后就失去了意义。

• 对同等长度的编码，理论上来说，任意两个类别之间的编码距离越远，则纠错能力越强。