机器学习入门 9-8 OvR与OvO
机器学习入门 9-8 OvR与OvO
本系列是《玩转机器学习教程》一个整理的视频笔记。本小节主要介绍能够将二分类算法解决多分类任务的两种方法OvR和OvO，并通过sklearn封装的逻辑回归实现OvR和OvO，最后使用sklearn实现通用二分类算法的OvR和OvO。
解 决 多 分 类 的 逻 辑 回 归 算 法
前面几个小节详细介绍了逻辑回归这种机器学习算法，它是通过回归的方式来解决分类问题。逻辑回归算法只能解决二分类问题，不过我们可以通过一些策略方法使逻辑回归算法同样能够解决多分类问题。
让只能解决二分类问题的算法能够解决多分类的策略方法有两种：OvR和OvO。当然这两种方法不仅适用于逻辑回归算法，而是一种几乎能够改造所有二分类算法的通用方法。
OvR（One vs Rest）
首先来看OvR（One vs Rest），通过OvR的英文名可以知道是一对剩余的所有，不过在其它一些机器学习教材或者资料中可能将OvR称为OvA（One vs All），它们两个表达的意思是一样的。不过称为OvR更为准确一些，并且在Sklearn文档中也是使用OvR命名的。
什么叫做一对剩余的所有呢？比如对于下图的四分类任务。
这里用四种不同颜色的点来代表四种不同的类别，很显然对于这样的四分类任务不能直接使用只能解决二分类问题的逻辑回归算法来处理。不过我们可以将其转换为二分类问题，相应的选取其中某一个类别，比如此时选择红色类别，而对于剩下的三个类别将它们称为其它类别，这也是One vs Rest的含义所在，红色类别为One剩下的所有类别为Rest。
至此就将四分类问题转换成了二分类问题。当然这个转换二分类的过程不仅仅包含红色类别，还有其余三种类别对应的二分类，相对应的就会有四种二分类的情况。具体如下图所示。
使用OvR的方式将二分类算法转换为多分类，具体的训练和测试步骤如下，这里为了方便使用上面四个类别每个类别只有一个样本的数据集为例。
- 训练过程
首先需要将数据集分成4份，每一份都将数据集转换成对应二分类的数据集。
然后将每一份数据集都使用一个单独的分类器进行训练。
- 测试过程
如果通过OvR解决n个类别的分类任务，就需要转换成n个二分类任务。当评估测试样本类别的时候，只需要在n个二分类数据集上训练好的n个分类器上计算对应类别的概率值，最后选择n个分类器上概率值最大的类别作为最终测试样本的类别。
不过显然使用OvR处理多分类任务提升了计算的时间复杂度。如果处理一个二分类问题用的时间是T的话，处理n个二分类就需要使用n * T这么多时间。
OVO（One vs One）
OvO（One vs One），通过OvO的英文名可以知道是一对一的意思。这里依然使用拥有四个类别的四分类为例，每个类别用一个不同颜色的样本点来表示。
OvO就是每次直接挑选出其中的两个类别。比如这里挑出红色和蓝色这两个类别，然后对红色和蓝色两个类别进行二分类。
至此就将四分类的问题转换成了二分类问题。对于四分类来说，这个过程可以重复进行，四个类别每次选出两个类别，一共有 C(4, 2) = 6个不同两两类别对，也就是形成6个二分类任务。
对于6个二分类问题，每一个二分类都可以估计出预测新样本属于对应两个类别中的哪一个类别，然后这6个分类结果进行投票选择分类结果数量最多的类别作为新样本点的类别。
使用OvO的方式将二分类算法转换为多分类，具体的训练和测试步骤如下，这里为了方便使用上面4个类别每个类别只有一个样本的数据集为例。
- 训练过程
首先需要将数据集分成C(4, 2) = 6份，每一份都将数据集转换成对应二分类的数据集。
然后将每一份数据集都使用一个单独的分类器进行训练。
- 测试过程
当使用OvO的方式处理n个类别的n分类任务时，需要进行C(n, 2) = n * (n - 1) / 2个二分类对。当评估测试样本类别的时候，只需要在C(n, 2)个二分类数据集上训练好的C(n, 2)个分类器上估计出对应类别，最后选择估计数量最多的类别作为最终测试样本的类别。
比如使用OvO处理拥有10个类别的手写数字识别的问题，一共需要进行C(10, 2) = 45次二分类任务。显然这种OvO方式消耗的时间要比前面介绍的OvR消耗的时间要多，这是因为C(n, 2) = n * (n - 1) / 2是一个n方级别的数字，而对于OvR来说我们只需要进行n次二分类任务。虽然时间上OvO要比OvR慢很多，但是OvO的分类结果更加准确，这是因为对于OvO我们每次都是使用真实的两个类别进行比较，没有像OvR那样将剩余的所有类别都保留混淆了其它的类别信息，所以OvO更倾向于估计新来的测试样本真实的属于哪一个类别。
LogisticRegression 中 的 OvR 和 OvO
前几个小节一直使用前两个类别的鸢尾花数据集，但其实鸢尾花本身有三个类别，这里使用完整的三个类别的鸢尾花数据集。为了方便可视化，特征依然先选择前两个特征，不过在最后会使用三个类别完整特征的鸢尾花数据集进行实验。加载完数据集之后，使用train_test_split将数据集划分为训练集和测试集。
了解了OvR以及OvO的基本原理，可以非常容易的实现一个底层的OvR和OvO。不过sklearn中的LogisticRegression自动添加了支持多分类任务的功能，甚至我们不需要添加额外的参数使用默认参数值就可以让LogisticRegression实现多分类。
注意到调用fit函数之后返回的字符串中有一个名为multi_class的参数，它的默认值是"ovr"，也就是说sklearn中的LogisticRegression默认支持多分类，并且默认使用OvR的方式。
接下来看一看使用LogisticRegression使用OvR实现多分类的分类准确度。
准确度只有65%左右，效果并不是很好。不过我们只是使用了鸢尾花数据集的前两个特征，我们并没有充分的利用数据集的全部信息。
绘制使用OvR实现三分类的决策边界。
接下来看一看如何在LogisticRegression中使用OvO的方式实现多分类。
由于参数multi_class默认值为'ovr'，如果要使用OvO需要更改参数multi_class的参数值，要使用OvO的方式需要将multi_class参数设置为'multinomial'（并不是'ovo'）。不过这里sklearn设置的稍微复杂一些，当我们使用OvO的方式实现多分类的时候，还需要传入solver参数，这是因为sklearn实现LogisticRegression并不是使用简单的梯度下降法，而是使用了其它更快的优化算法。当我们使用OvO这种多分类方法的话，默认的solver = 'liblinear'这种优化算法就会失效，我们必须要传入一个新的优化算法，这里将solver设置为'newton-cg'。
接下来训练模型，看看使用OvO实现多分类的分类准确度。
使用OvO方式分类准确度为78%左右，显然比使用OvR的65%的准确率要高很多，使用OvO方式实现多分类虽然耗时但是分类的结果更加准确。
绘制使用OvO实现三分类的决策边界。
从决策边界上也可以看出OvO的决策边界比OvR的决策边界要更加准确。
之前为了可视化只保留了鸢尾花数据集的前两个特征，不过鸢尾花数据集本身是有四个特征的。接下来尝试一下使用鸢尾花的全部特征，来看看使用OvR和OvO两种实现多分类方式的准确度。
对于LogisticRegression算法来说使用OvR实现多分类的分类准确度为94%左右，使用OvO实现多分类的分类准确度为100%，这也再次验证了使用OvO方式的分类结果比使用OvR方式的分类结果要更加准确。不过由于鸢尾花数据集本身比较小，所以不能看出来使用OvO方式的耗时更长。
实 现 通 过 二 分 类 算 法 的 OvR 和 OvO
对于LogisticRegression二分类算法来说，sklearn封装的LogisticRegression中自动融合了OvR和OvO实现多分类的方式，只需要在实现的时候传入对应的参数即可。不过前面提到OvR和OvO是一种通用的方式，它们几乎可以适用于所有的二分类算法，不过sklearn为我们封装了OvR类和OvO类，这样我们可以用任意的二分类算法应用这两个类来完成多分类任务。
- 使用sklearn封装的OneVsRestClassifier类
这里使用log_reg作为二分类器。输出的分类准确度和使用LogisticRegression调用参数实现OvR的结果是一致。
- 使用sklearn封装的OneVsOneClassifier类
这里使用log_reg作为二分类器。输出的分类准确度和使用LogisticRegression调用参数实现OvO的结果是一致。
我们使用OneVsRestClassifier和OneVsOneClassifier就可以对所有的二分类器进行多分类任务，甚至我们可以编写自己的算法模块，当然必须要遵循sklearn的设计标准都可以传入这两个类中，让二分类算法可以完成多分类任务。
这一章整体的介绍了LogisticRegression算法，它拓展了线性回归的方式，通过估计概率值的方式将回归问题转换成二分类问题。LogisticRegression在实际应用中使用非常广泛。
这一章介绍了分类任务，但是对于分类任务还有很多值得讨论的地方，其中非常重要的地方就是如何来评价分类器的准确度，之前的学习中一直使用accuracy分类准确度的方式来评价分类器的好坏，其实这种评价标准在一些情况下存在非常严重的缺陷。接下来将会用一整章来介绍分类任务的各种指标。