基于核的最优子空间（KOS）：一种数据分类方法

《Machine Learning and Knowledge Extraction》：Kernel-Based Optimal Subspaces (KOS): A Method for Data Classification Lakhdar Remaki

　　

支持向量机（Support Vector Machine, SVM）是一种广受欢迎的基于核（kernel-based）数据分类方法，已在广泛的实际应用中展现出较高效率。然而，SVM 仍存在若干局限性，包括：优化过程可能失败，尤其是在高维空间中；计算成本本质上较高；缺乏一种系统性的多分类处理方案；难以处理类别不平衡问题；以及实时或动态分类的代价过高。本文提出一种替代方法，称为基于核的最优子空间（Kernel-based Optimal Subspaces, KOS），其属于核子空间方法（kernel subspace methods）家族。从数学上看，该方法与核主成分分析（Kernel PCA, KPCA）相似，在获得与 SVM 可比性能的同时，能够克服上述缺陷。

该方法基于计算映射数据到最优特征子空间（feature subspaces）的最小距离。由于不需要优化过程，KOS 具有鲁棒、快速且易于实现的特点。最优子空间可独立构建，因此该方法具有高度并行化能力，尤其适用于动态分类与实时应用。此外，类别不平衡问题可通过将大类别划分为较小子类的方式得到自然处理，从而在特征空间中构造出大小适宜的子子空间。

该文发表于《Machine Learning and Knowledge Extraction》，核心目标是提出一种可替代支持向量机（Support Vector Machine, SVM）的核分类方法。研究背景在于，SVM 虽然长期被视为高性能核分类器，但其方法论基础建立在优化求解之上，因此在高维场景、多分类任务、类别不平衡问题以及动态增删类别的应用环境中，往往面临计算代价高、扩展性有限、实现复杂和实时性不足等现实瓶颈。尤其是在多分类问题中，SVM 通常需要构造大量分离超平面；在类别极不均衡时，又往往依赖权重调整或合成样本等额外技术，这些策略可能缺乏统一原则，且可能改变原始数据结构。因此，开展一种不依赖优化、能够直接在核诱导特征空间中完成判别、并自然适配多分类与不平衡场景的新方法，具有明确的理论价值与应用意义。

围绕上述问题，研究人员提出了基于核的最优子空间（Kernel-based Optimal Subspaces, KOS）方法。该方法首先通过 Mercer 核将原始属性空间中的样本映射到高维特征空间，再针对每一个类别独立构造最优特征子空间。对于待分类样本，不再像 SVM 那样寻找分离超平面，而是计算其特征向量到各类别最优子空间的距离，并依据最小距离准则确定其类别归属。方法构造上，KOS 采用适当正交分解（Proper Orthogonal Decomposition, POD）建立每个类别的子空间基，并从几何与代数两方面证明其“最优性”：几何上，POD 基在同维正交基中对原始特征数据给出最优逼近；代数上，POD 子空间是包含该类映射数据的最小子空间。研究还证明，理论上存在 Mercer 核可使不同属性类别映射到彼此分离、甚至正交的特征子空间中，这为 KOS 的可分性奠定了理论基础。

在方法上，研究人员系统推导了未中心化与中心化两种特征空间表述。对于每一类别，先由核函数构造相关矩阵，再计算其特征值与特征向量，并据此得到 POD 模态（modes）及样本在各类别子空间中的投影坐标，最终通过毕达哥拉斯型距离表达式完成分类判别。由于整个过程中仅涉及核矩阵特征对（eigenpairs）的求解，而不涉及超平面优化，因此方法在实现上更直接，也避免了高维优化失败、舍入误差累积等问题。与 SVM 相比，KOS 在类别数增加时仅需线性增长的独立子空间构造，而不需要二次规模增长的分类边界求解。

研究人员还针对类别不平衡问题提出了内生性的解决方案。其思想并非对少数类进行过采样，也不引入人工属性，而是将样本数明显偏大的类别拆分为若干规模接近参考类大小的子类，并将这些子类在特征空间中分别表示为多个子空间，但在分类决策时仍共同对应同一原始类别。这样，原本过大的类别被分解为更平衡的局部结构，既保留了原始数据分布形态，又提高了分类判别的公平性与稳定性。论文实验明确显示，该策略在 Leukemia 和 Shuffle 等高度不平衡数据上带来了显著性能增益。

在 RBF 核（radial basis function kernel）参数学习方面，论文强调 KOS 不需要像软间隔 SVM 那样同时学习惩罚参数 C 与核宽度参数，仅需学习 ?? 或等价的 ??。研究人员提出按类别直径对 ?? 进行缩放，将其写为 ??=??D，其中 D 为类内最大距离、?? 在 0.1 到 1 之间离散搜索。该策略借鉴多尺度理论思想，使核尺度与类别几何尺寸相协调，既降低参数搜索复杂度，又有助于避免 RBF 协方差矩阵病态化。

用于开展研究的关键技术方法主要包括以下几类。其一，采用 Mercer 核映射与 RBF 核构造特征空间表示；其二，利用适当正交分解（POD）在每个类别上独立构造最优特征子空间，并给出中心化与未中心化两套公式；其三，采用基于投影坐标与最小距离的子空间判别准则实现分类；其四，通过大类拆分策略处理类别不平衡；其五，利用按类直径重缩放的参数学习策略确定 RBF 核参数。实验样本来自 LIBSVM 与 OpenML 数据库，包含二维合成数据、二分类和多分类高维真实数据集。

在研究结果部分，论文首先保留并展开了“3.1. 2D Test Cases”这一部分。研究人员在连通集合、非连通集合及螺旋结构三类逐步增难的二维非线性分类场景中验证了 KOS 的能力。结果表明，在固定 ??=1.2 的条件下，KOS 能够成功分离上述复杂非线性数据，说明其并非仅适用于线性或简单分布场景，而是在核映射后具备稳定的几何判别能力。

在“3.2. Higher-Dimension Test Cases”中，研究人员将方法推广至 LIBSVM 和 OpenML 中的高维二分类与多分类真实数据。采用准确率与宏平均精确率（macro-precision）评价性能，证明 KOS 可在真实复杂数据中保持有效。

在“3.2.1. KOS vs. SVM”中，论文将 KOS 与 LIBSVM 实现的 SVM 进行系统比较。结果显示，KOS 总体上取得了与 SVM 可比的分类性能，而在参数学习上仅需调节单一核参数，显著简化了建模过程。更重要的是，在类别不平衡的 Leukemia 与 Shuffle 数据中，拆分类别后的性能分别由 67.64% 提升到 82.35%、由 80.6% 提升到 99.9%，直接验证了所提不平衡处理机制的有效性。

在“3.2.2. Comparison with KNN and KPCA”中，研究人员将 KOS 与核神经网络（Kernel Neural Networks, KNNs）及 KPCA 比较。结果表明，KOS 整体上优于所采用的 KNN 模型，尤其在不平衡数据上优势更明显；相较于理论上更接近的 KPCA，KOS 也呈现更好的综合表现。论文将这种差异归因于 POD 的 snapshot 表述：它既简化了到子空间距离的计算，又通过将类内样本视为代表元素的时序形变来强化类内凝聚性；而 KPCA 的子空间距离依赖逆变换重构，会引入额外优化步骤，从而影响精度与时间效率。

在“3.2.3. Feature Space Orthogonality”中，论文进一步考察特征子空间的可分性。研究人员通过主角（principal angles）和弦距离（chordal distance）度量不同类别子空间间的正交性，发现整体上子空间越接近正交，方法性能通常越好。这一结果从实验角度支持了论文此前关于“子空间分离性”重要性的理论分析。同时，研究也指出正交性并非唯一决定因素，因为训练数据对真实分布的代表性同样关键。

在“3.2.4. CPU Time Discussion”中，研究人员比较了 KOS、SVM、KNN 与 KPCA 的计算时间。尽管不同实现语言存在差异，论文仍通过校正后时间进行公平讨论，结果显示 KOS 显著快于 SVM，快于 KNN，并与 KPCA 大体相当；而即使不做 CPU 时间重缩放，KOS 依然快于 SVM。这与其无需优化、仅需独立求解核矩阵特征对的算法结构高度一致。

在“3.2.5. Complexity Analysis”中，论文给出了复杂度层面的正式比较。SVM 在多分类场景下需处理数量级为 O(n²) 的优化问题；若采用 Newton 法，每次迭代复杂度为 O(d³)，整体复杂度可表示为 O(kn²d³)。相比之下，KOS 对每个类别只需求解一次规模与类大小相关的特征值问题，总复杂度为 O(nc³)。在 d 与 c 视为常数、类别数 n 增大时，SVM 与 KOS 分别退化为 O(n²) 和 O(n)，由此说明 KOS 关于类别数具有线性伸缩性，这也是其适于多分类与动态分类的重要原因。

在“3.3. KOS: Main Advantages Compared to SVM”中，论文总结了 KOS 相较 SVM 的七项主要优势：实现更简洁；无优化因而更鲁棒；复杂度随类别数线性增长；运行时间更优；天然适合并行计算；在动态增删类别时只需局部更新；并且能够通过类别拆分自然处理类别不平衡。这些优势并非停留在概念层面，而是与理论推导、实验结果和复杂度分析相互印证。

论文讨论部分的核心在于，KOS 虽然在思想上属于核子空间方法，但其通过 POD 建模类别结构，替代了 SVM 的分离超平面范式，从而在保持相近分类性能的同时，系统性缓解了 SVM 在高维、多类、动态场景和不平衡数据上的若干固有问题。论文并未声称正交子空间在实践中必然实现，而是审慎指出：选用无限维特征空间核，如 RBF 核，可提高子空间分离的可能性，但真实效果仍受样本代表性与核参数选择影响。这种表述使全文在理论理想性与工程现实性之间保持了较好的平衡。

研究结论部分可译为：本文提出了一种 SVM 的替代方法，即基于核的最优子空间（KOS），其属于核子空间方法家族。该方法通过在特征空间中构造最优子空间，并依据未见属性向量到这些子空间的最小距离进行分类。论文给出了一些理论基础及其证明，表明 POD 子空间在如下意义下是最优的：它们是包含特征类别的最小子空间，其基系统则是数据的最佳代表。文中推导了实际实现所需的全部公式。针对类别不平衡问题，研究提出了一种简单直观的处理机制，无需额外预处理或重采样技术。基于二维数据及真实高维多分类数据集的实验结果表明，KOS 达到了与优化后 SVM 相当的性能。论文还将该方法与 KNNs 和 KPCA 进行了比较。除准确率之外，KOS 相比 SVM 还具有多项实际优势：更易实现、显著更快、更加鲁棒、能够系统处理类别不平衡、适用于动态分类任务，并且关于类别数具有高度并行性。这些优势使 KOS 成为在广泛应用场景中替代 SVM 的有力方案。