六、多类分类问题

1. 某些算法原生的支持多分类，如：决策树、最近邻算法等。但是有些算法只能求解二分类问题，如：支持向量机。

2. 对于只能求解二分类问题的算法，一旦遇到问题是多类别的，那么可以将多分类问题拆解成二分类任务求解。

   即：

   • 先对原问题进行拆分，然后为拆出的每个二分类任务训练一个分类器。
   • 测试时，对这些二分类器的预测结果进行集成，从而获得最终的多分类结果。

3. 多分类问题有三种拆解方式：

   • 一对其余(One-vs-rest:OvR) 。
   • 一对一(one-vs-one:OvO) 。
   • 多对多(many-vs-many:MvM) 。

6.1 one vs rest

1. 一对其余：为每一个类别训练一个分类器。

   假设类别为 ，则训练 个分类器 ：

   • 训练 时，将类别为 的样本点定义为正类，将类别不是 的样本点定义为负类。
   • 训练 不光需要给出预测结果是否属于类别 ，还要给出置信度。

2. 预测时，对于未知的实例，用训练出来的 个分类器来预测。

   假设置信度最高的分类器为 ，则该实例的类别预测为 。

3. 缺点：非常容易陷入样本不平衡。

   即使训练集中每一类样本都是平衡的，训练每个分类器时样本反而不平衡。

6.2 one vs one

1. 一对一：为每一对类别训练一个分类器。

   假设类别为 。那么训练 个分类器 。

   分类器从原始训练集中提取类别为 的样本点作为新的训练集，然后训练 。

2. 预测时，对于未知的实例，对预测结果进行投票。

   • 首先设投票结果为

   • 然后用每个分类器 对未知实例进行预测：

     • 若预测结果是类别 ，则 。
     • 若预测结果是类别 ，则 。
   • 最终假设 最大，则该未知的实例分类为 。

3. 缺点：需要训练的分类器数量为 ，计算量太大。

6.3 many vs many

1. 多对多：每次都将若干个类作为正类，若干个其他类作为反类。

   • 正、反类的构造必须有特殊的设计，不能随意选取。
   • 通常采用纠错输出码Error Correcting Output Codes:ECOC技术。该技术将编码的思想引入类别拆分，并尽可能在解码过程中具有容错性。

2. ECOC工作过程主要分两步，假设类别为 ：

   • 编码：对 个类别进行 次划分，每次划分都将一部分类别划分为正类，一部分类别划分为反类，从而形成一个二分类训练集。

     这样一个产生 个训练集，可以训练出 个分类器。

   • 解码：用 个分类器分别对测试样本进行预测，这些预测标记组成一个编码。

     将这个预测编码与每个类别各自的编码进行比较，返回其中距离最小的类别作为最终预测结果。