机器学习 学习笔记（7）多分类学习与类别不平衡
多分类学习
现实中常遇到多分类学习任务，有些二分类学习方法可以直接推广到多分类，但在更多情况下，是基于一些基本策略，利用二分类学习器来解决多分类问题。
考虑N个类别C1，C2，C3，....，CN，多分类学习的基本思路是拆解法，即将多分类任务拆为若干个二分类任务求解，具体来说，先对问题进行拆分，然后为拆出的每个二分类任务训练一个分类器，在测试时，对这些分类器的预测结果进行集成以获得最终的多分类结果，关键是如何对多分类任务进行拆分，以及如何对多个分类器进行集成。
拆分策略
最经典的拆分策略有三种：一对一One vs. One，简称OvO，一对其余One vs. Rest，简称OvR，多对多Many vs. Many，简称MvM。
给定N个分类，OvO将这个N个类别两两配对，从而产生N(N-1)/2个二分类任务，例如OvO将为区分类别Ci和Cj训练一个分类器，该分类吧D中所有的Ci类昂本作为正例，Cj类样本作为反例，在测试阶段，新样本将同时提交给所有分类器，于是将得到N(N-1)/2个分类结果，最终结果可以通过投票产生，即把预测得最多的类别作为最终分类结果。
OvR每次将一个类的样例作为正例，所有其他类的样例作为反例来训练N个分类器，在测试时若仅有一个分类器预测为正例，则其对应的类别标记作为最终分类结果，若有多个分类器预测为正例，则通过考虑各预测分类器的预测置信度，选择置信度最大的类别标记作为分类结果。
OvR只需要训练N个分类器，但是OvO需要训练N(N-1)/2个分类器，因此OvO的存储开销和测试开销时间往往比OvR更大，但在训练时，OvR的每个分类器均只用全部训练样例，而OvO的每个分类器仅用到两个类的样例，因此，在类别很多时，OvO的训练时间开销通常比OvR更小，至于预测性能，取决于具体的数据分布，多数情况下，两者差不多。
MvM是每次将若干个类作为正类，若干个其他类作为反类。OvO和OvR是MvM的特例。MvM的正类、反类构造必须有特殊的设计，不能随意选择，一种最常见的MvM技术，纠错输出码（Error Correcting Output Codes，简称ECOC）。
ECOC将编码的思想引入类别拆分，并尽可能在解码过程中具有容错性，ECOC工作过程主要分为两步：
- 编码：对N个类别做M次划分，每次划分将一部分类别作为正类，一部分划分为反类，从而形成一个二分类训练集，这样一共产生M个训练集，可训练出M个分类器。
- 解码：M个分类器分别对测试样本进行预测，这些预测标记组成一个编码，将这个预测编码与每个类别的各自的编码进行比较，返回其中距离最小的类别作为最终预测结果。
类别划分主要通过“编码矩阵”指定，编码矩阵有多种形式，常见的主要有二元码和三元码。二元码将每个类别分别指定为正类、反类，三元码在正反类之外，还可以执行停用类。
称为纠错输出码的原因是，在测试阶段，ECOC编码对分类器的错误有一定的容忍和修正能力。对同一个学习任务，ECOC编码越长，纠错能力越强，编码越长，意味着所需训练的分类器越多，计算、存储开销都会增大，另一方面，对有限类别数目可能的组合数目是有限的，码长超过一定范围后就失去了意义。
对同等长度的编码，理论上来说，任意两个类别之间的编码距离越远，则纠错能力越强。
类别不平衡问题
类别不平衡就是指分类任务中不同类别的训练样例数目差别很大的情况。
几率
反应了正例可能性与反例可能性之比值，阈值设置为0.5表明分类器认为真实正、反例可能性相同，即
，预测为正例。
当训练集中正、反例数目不同时，令m+表示正例，m-表示反例，则：
，预测为正。调整为：
，这就是类别不平衡学习的一个基本策略，再缩放。
再缩放的思想简单，但实际操作却不平凡，因为训练集是真实样本的无偏采样这个假设往往不成立。
有三类做法：欠采样、过采样、阈值移动
欠采样即直接对训练集中样例数目多的分类进行欠采样，使得正、反例数目接近。
过采样对训练集中的样例数目少的分类进行过采样，使得正、反例数目接近。
阈值移动为直接基于原始训练集进行学习，但在用训练好的分类器再进行预测时，将
嵌入决策过程中。
欠采样法的时间开销往往远小于过采样法，因为前者丢弃了很多反例，使得分类器训练集远小于初始训练集，而过采样法增加了很多正例，其训练集远远大于初始训练集。过采样法不能简单地对初始正例样本今次那个重复采样，否则会导致严重过拟合。过采样法的代表性算法SMOTE是同对训练集中的正例进行插值来产生额外的正例。欠采样法如果随机丢弃反例，可能会丢失一些重要信息，欠采样法的代表性算法是利用集成学习机制，将反例划分为若干个集合供不同的学习器使用，全局来看不会丢失重要信息。
参考
- 《机器学习》