一对一 (OvO) 多类分类器

引言

多类别分类（multiclass classification）是指将输入样本分配到三种或三种以上离散类别中的一个的目标。这个问题在机器学习中很常见，应用领域包括图像识别、自然语言处理、生物信息学以及医学诊断。与旨在区分两个类别的二元分类不同，多类别分类问题更难解决，需要更复杂的解决方案。

例如，水果分类系统可以对苹果、香蕉、橙子和梨的图像进行分类。这些算法试图通过将问题转化为一组更简单的任务或直接处理多个类别来实现这一点。

一对一（OvO）在解决多类别问题中的作用

一对一（OvO）策略是一种非常流行的方法，用于将多类别分类问题简化为多个二元分类问题。在此方法中，我们为所有可能的类别对训练一个单独的二元分类器。在分类过程中，这些分类器对它们训练的两个类别中的一个进行投票。然后，通过对输入样本的所有成对分类器进行投票，并将输入样本分配给获得多数票的类别来做出最终预测。

与一对多（OvR）的比较

另一种更流行的多类别分类方法是一对多（OvR）策略。在 OvR 中，我们为每个类别训练一个二元分类器，将该类别的样本与其余样本的总和分开。OvR 是一个很好的系统，但在实现和性能特征方面与 OvO 有很大不同。

一对一（OvO）多类别分类器的工作原理

成对分类

OvO 多类别分类包括将多类别问题分解为一组二元问题。对于具有 n 个唯一类别的 n 个类别的数据集，OvO 会为每对可能的类别创建一个二元分类器。计算总分类器数量的公式如下：

分类器数量 = n(n−1)/2

对于每个分类器，都考虑属于两个类别的样本，并训练它们区分这两类，而忽略其余类别。通过这种方法，每个分类器的复杂度都降低了，仅专注于区分两个类别。让我们以一个包含 3 个类别（A、B 和 C）的问题为例，OvO 将为以下对创建分类器：

• 分类器 1：A vs. B
• 分类器 2：A vs. C
• 分类器 3：B vs. C

分配给特定决策边界的分类器会发生变化，决策边界是分类器负责分类的两个类别之间的边界。

投票机制

在训练完所有成对分类器后，测试阶段采用投票模式的组合预测，从所有成对分类器中获取最终预测。如果一个新样本需要分类，则

• 一旦测试样本获得了其特征，每个二元分类器都会对其进行调优以区分的两个类别中的一个进行投票。
• 将这些投票汇总起来，选择获得最多投票的类别作为最终类别的预测。

例如，在一个三类问题（A、B、C）中，考虑给定样本的成对分类器的预测：

• 分类器 1（A vs. B）：预测 A
• 分类器 2（A vs. C）：预测 C
• 分类器 3（B vs. C）：预测 B

每个类别的投票如下：

• 类别 A：1 票
• 类别 B：1 票
• 类别 C：1 票

如果出现平局，可以使用更多策略来打破平局，例如使用分类器的置信度分数或随机选择。

使用的二元分类器

• 支持向量机（SVM）：SVM 在 OvO 中很受欢迎，因为它们适用于处理复杂的决策边界。它们在高维空间中表现良好，并且在特征数量超过样本数量时具有抗过拟合性。
• 逻辑回归：它是逻辑回归的一个二元分类模型，对于线性可分数据集来说是一种简单有效的方法。它以概率形式输出，因此可用于 OvO 中的基于置信度的投票。
• 决策树：决策树在计算时间方面诊断成本较低，并且由于它们可以处理非线性关系，因此适用于小型数据集。它们是可解释的，并且可以扩展到随机森林等集成方法以获得更好的性能。
• k-近邻（k-NN）：k-近邻（k-NN）使用特征空间中找到的 k 个最近邻的类别标签的多数投票。它是一种非参数方法，当训练数据有簇时效果很好。
• 朴素贝叶斯分类器：一种基于贝叶斯定理的概率分类器，假设特征之间是独立的。在文本分类和稀疏数据等问题中，它效率很高，并且效果很好。

一对一（OvO）多类别分类器的数学框架

所需分类器数量的公式

OvO 多类别方法为每个类别对训练一个二元分类器。使用组合公式，可以从数学上确定所需的二元分类器总数：

分类器数量 = n(n−1)/2

其中

• n：表示数据集中类的总数。
• n(n−1)/2：表示唯一类别对的总数。

示例

如果有 n=5 个类别，所需的二元分类器数量将是 5(5−1)/2 = 5×4/2 = 10 个分类器。

这有助于通过聚合进行准确的多类别预测，但每对类别都会进行比较，因此实际上所有类别对都会被比较。

成对分类的决策边界

OvO 策略包括运行该策略中的每个二元分类器，以创建与特定类别对相关的决策边界的变化。这些边界在特征空间中分离这两个类别。

关键特性

• 特定类别的决策区域：每个分类器定义超平面（在高维空间中）将特征空间划分为两个区域，用于分类成对的两个类别。
• 局部范围：每个分类器处理的数据集仅限于两个类别，因此决策边界可以针对这两个特定类别之间的差异进行很好的优化。
• 重叠处理：如果组合多个分类器，则最终预测基于投票，其中在所有成对分类器中获得最高票数的类别获得多数票，以做出最终预测。
• 可视化：二元分类器在二维空间中的决策边界是线性的（例如，支持向量机）或非线性的（例如，k-NN），具体取决于使用的算法。这些边界仅对配对类别是唯一的，并且在区分方面很稳健。

复杂度分析

OvO 类方法在训练和测试阶段的计算权衡是独特的。

训练复杂度

• 事实上，由于训练了 n(n−1)/2 个分类器，总训练时间将随着类别的数量急剧增加。
• 每个二元分类器仅使用派生子集中存在的类别对中的元素进行训练。这减少了每个分类器需要处理的数据集的大小，但同时，总计算负载随着分类器数量的增加而增加。

示例

对于 n=10 个类别

分类器数量 = 10(10−1)/2 = 45

根据底层二元分类器（SVM 或逻辑回归）的复杂程度，训练时间会有所不同。

测试复杂度

• 在预测阶段，运行所有 n(n−1)/2 个分类器以处理单个测试实例的复杂度。
• OvO 算法由于其决策时间与类别的数量成正比，因此计算量很大。

与一对多（OvR）相比的权衡

• OvO 的训练复杂度降低了，因为一次只涉及两个类别。
• 然而，这确实是以分类器总数较少为代价的，并且对于高 n 值，OvO 的计算成本仍然高于 OvR。

一对一（OvO）多类别分类器的优点

降低单个分类器的复杂度

• 简化的二元任务：在 OvO 方法中，每个分类器都经过训练，仅区分两个类别；因此，这种方法在同时处理所有类别方面更加简化。
• 每个二元分类器的训练数据集更小：OvO 中的每个二元分类器处理一对类别；因此，用于训练每个分类器的数据集大小要小得多。事实上，这加快了每个分类器的训练时间，并使模型能够专注于仅两个类别之间的细微差别。
• 提高决策准确性：OvO 分类器比同时学习所有类别的分类器能做出更好、更具体的决策。

在处理类别对之间的不平衡方面性能有所提高

• 局部类别平衡：类别不平衡是多类别分类中的一个重要挑战。因此，OvO 在由该分类器必须预测的两个类别组成的平衡数据集上训练每个二元分类器。
• 提高对少数类别的敏感性：在全局多类别基础上，少数类别可能会被忽略，但它们在成对训练中被同等对待。通过确保这些类别有足够的代表性，可以确保这些类别的分类表示和准确性更好。
• 多类别问题的鲁棒性：OvO 中的投票机制不会丢失少数类别的预测，因为它们会为每个成对投票做出贡献，从而可以为最终预测做出贡献。

在小型数据集上的可伸缩性

• 有效利用有限数据：在数据集大小有限的情况下，OvO 的优势在于仅使用与二元分类器正在比较的两个类别相关的数据。
• 过拟合风险降低：在小型子集上训练过拟合的风险较低，尤其是在目标有限或嘈杂的情况下。
• 可扩展到增加的类别数：OvO 在类别数量增加方面是可扩展的，因为它执行成对分类。在较小的、集中的数据集上训练每个分类器可以抵消分类器数量的增加。