k-支持向量机（k-SVM）多分类问题的解决策略

题目描述：支持向量机（SVM）最初是为二分类问题设计的，但实际应用中常遇到多分类问题（如手写数字识别、图像分类等）。k-SVM不是指某个特定算法，而是泛指解决k类（k>2）分类问题的SVM扩展策略。主要方法有三种：一对一（One-vs-One, OvO）、一对多（One-vs-Rest, OvR）和有向无环图（DAG-SVM）。本题要求详细解释这些策略的原理、步骤及优缺点。

解题过程：

1. 问题分析

   • SVM通过寻找最优超平面（决策边界）最大化两类数据的间隔，但原生SVM只能处理二分类。
   • 多分类问题需将多个类别的判别规则组合。例如，对k=3的分类（类别A、B、C），需设计机制区分所有类别。

2. 一对多（OvR）策略

   • 原理：为每个类别训练一个二分类SVM，将该类作为正类，其余所有类作为负类。
   • 步骤：
     1. 训练k个分类器：第i个分类器将第i类数据标记为+1，其他k-1类数据标记为-1。
     2. 预测时，输入样本分别通过k个分类器，得到k个决策函数值（如符号函数输出或距离超平面的距离）。
     3. 选择决策函数值最大的类别作为预测结果（例如，距离超平面最远的正类）。
   • 举例：对k=3，训练3个分类器：
     • 分类器1：A vs [B, C]
     • 分类器2：B vs [A, C]
     • 分类器3：C vs [A, B]
       预测时，若分类器1输出距离为+2.5，分类器2输出-1.0，分类器3输出+0.5，则选择类别A。
   • 优点：仅需k个分类器，训练效率较高。
   • 缺点：训练数据不平衡（正类样本少，负类样本多），可能影响超平面位置；若多个分类器均给出正输出，需依赖决策值比较，可能产生歧义。

3. 一对一（OvO）策略

   • 原理：为每两个类别训练一个二分类SVM，忽略其他类别。
   • 步骤：
     1. 训练C(k,2) = k(k-1)/2个分类器，每个分类器针对两类数据（如类i和类j）。
     2. 预测时，样本输入所有分类器进行投票，每个分类器给出一个预测结果（i或j），最终得票最多的类别获胜。
   • 举例：对k=3，训练3个分类器：
     • 分类器1：A vs B
     • 分类器2：A vs C
     • 分类器3：B vs C
       预测时，若分类器1输出A，分类器2输出A，分类器3输出C，则A得2票，B得0票，C得1票，预测为A。
   • 优点：每个分类器训练数据仅涉及两类，数据平衡且训练简单。
   • 缺点：分类器数量随k平方增长，计算成本高；投票平局时需额外处理（如随机选择或比较决策函数值）。

4. 有向无环图（DAG-SVM）策略

   • 原理：基于OvO分类器构建有向无环图，通过层级排除减少预测计算量。
   • 步骤：
     1. 训练阶段：与OvO相同，构建k(k-1)/2个分类器。
     2. 预测阶段：使用二叉树状的有向无环图，每个节点是一个二分类器（如根节点为类1 vs 类k），根据节点输出沿边遍历，直到叶子节点得到最终类别。
   • 举例：对k=4，DAG可能结构：
     • 根节点：分类器1（类1 vs 类4）→ 若输出类1，则进入节点2（类1 vs 类3）；若输出类4，则进入节点3（类2 vs 类4）。
     • 中间节点继续判断，最终到达叶子节点（某个类别）。
   • 优点：预测只需k-1次分类器计算，效率高于OvO的k(k-1)/2次。
   • 缺点：分类器顺序影响结果，可能因路径选择产生误差。

5. 策略选择与总结

   • OvR适合k较大的场景，训练速度快；OvO通常精度更高，但计算成本大；DAG-SVM是OvO的预测优化版本。
   • 实际应用中，可结合交叉验证选择策略。现代机器学习库（如Scikit-learn）默认使用OvR或OvO实现多类SVM。