1. 多分类学习

对于多分类任务，有些二分类方法可直接推广到多分类（如LDA推广）。但更多情况下，基于一些基本策略，利用二分类学习器来解决多分类问题。

假设N个类别。基本思路：拆解法。将多分类任务拆分为若干个二分类任务。为每个二分类任务训练一个分类器；测试时，对这些分类器的结果进行集成获得最终结果。

关键问题：如何拆分？如何集成？

经典策略：

• 一对一（one vs one，OvO）
• 一对多（one vs rest，OvR）
• 多对多（many vs many，MvM）

1.1 一对一

• 思想：给定数据集，N个类别的堆。将N个类别堆，两两配对，一正一反。

• 分类器个数：N(N−1)/2个二分类器

• 测试：把样例提交给所有分类器。产生N(N−1)/2个结果。投票产生。

1.2 一对多

• 思想：给定数据集，N个类别的堆。一个类为正例，其余所有为反例。

• 分类器个数：N个二分类器

• 测试：把样例提交给所有分类器。若仅有一个分类器预测为0类，其余1类，则对应为0类。若有多个都是0类，则根据各个的预测置信度。置信度最大的类别标注为分类结果。

千言万语不如此幅图。

左边：N=4，则分类器有6个。新样本测试6次，然后投票。

右边：N=4，则分类器有4个。C3预测为正类，其余均负类，则最终为C3。

两种比较：

• 因分类器的多与少，OVO的存储开销和测试时间，大于OVR
• OVR训练时数据集全上，OVO仅两个类，当类别很多时，OVO训练开销比OVR可能更小。

1.3 多对多

上述两种则是多对多的特例了。

思想：每次若干个正类，若干个负类。正反类构造特殊的设计，不能随意构造。最常用的技术：纠错输出码（Error Correcting Output Codes, ECOC）

工作过程：

• 编码：将N个类做M次划分，每次划分一些是正类，一些是负类。共产生M个二分类器。
• 解码：M个分类器对新样本测试，其结果组成一个编码，与各个类别的编码比较，返回距离最小的类别为最终结果。

对于左图，第一个分类器f1将C1，C3，C4为负类，C2为正类；其余依次设置，共M个分类器。每行是对应类别的编码，长度为M。新样本测试后得到M长度的码，与各类对比，距离最近的为该类。

右图是三元码，除了正类，反类，还有个停用类。

可以看出，一对多的方式，就对应着将编码矩阵（左图）中每列设置一个正类，其余均是负类。

问题：为何叫做纠错输出码？

答：测试阶段，ECOC编码对分类器的错误有一定的容忍和修正能力。例如左图中，对测试示例的正确预测编码是（-1,+1,+1,-1,+1），但若是f2分类器出错了，预测成了（-1,-1,+1,-1,+1），仍然可以得到正确的结果。（不同类别的编码距离之间有段距离，错误不出这个距离则都可以判断正确）

一般的，对于同一个任务，ECOC编码越长，纠错能力越强。然而编码长意味着分类器数目多了，开销增大。再者，有限类别数产生的组合数目有限，码长太长会失去意义。

同等长度的编码，任意两个类别之间的编码距离越长，则纠错能力越强。码长较小时，可根据这个原则来最优化得到最优编码，但码长稍大就难以计算，这是个NP难问题。不过实际中并不需要最优编码，非最优编码可能往往已有足够好的结果。

2. 类别不平衡问题

之前的分类学习方法一个共同假设：不同类别的训练样本数目相当。

若不同类别的样例数目稍有差别，通常影响不大，但若相差悬殊则会对学习产生困扰。例如正例998个，反例2个，则学习器永远只返回新样本为正例。

类别不平衡：分类任务中不同类别的训练样例数目相差过大。

以下讨论基于正例少，反例多的情况。

实际技术中常用三种办法：

• 对反类样例降采样。
• 对正例上采样。
• 直接基于原始训练集学习，预测时将正反类比例融合进阈值中

2.1 降采样

降采样，即抛弃一些反例。代表性算法：EasyEmsemble，利用集成学习机制，将反例划分为若干个集合，供不同学习器使用。每个学习器角度看降采样了，但总体不会丢失信息。

2.2 上采样

上采样，即增加一些正例。但不能简单重复采样，否则过拟合严重。代表性算法SMOTE，通过对训练集的正例进行插值，产生额外的正例。

2.3 观测几率再缩放

正反类比例融合：预测时概率大于0.5即认为是正例。即

（3.46）

再缩放/再平衡虽然简单，但实际操作并不平凡。因为：训练集是真实样本总体的无偏采样的假设，一般并不成立。未必可有效基于训练集观测几率来估计真实几率。