用于多类分类的最大间隔超椭球支持向量机

多类分类中支持向量机效率低的问题，提出基于马氏距离的超椭球支持向量机（M3HE-SVM），通过正交化消除特征相关性和尺度不一致性，优化最大边界计算，实验表明在合成数据、UCI和大规模数据集上分类精度和效率均优于传统方法，具有强鲁棒性和泛化能力。

　　

丁凯 | 孟明珠 | 尹菲菲

天津科技大学人工智能学院，天津，300457，中国

摘要

为了解决基于支持向量机（SVM）的多分类方法效率低的问题，超球面支持向量机已被广泛采用。然而，它仍然面临特征相关性和特征尺度不一致等挑战。为了克服这些限制，本文提出了一种最大间隔超椭球面支持向量机（M³HE-SVM）方法。与传统方法使用欧几里得距离不同，该方法采用马氏距离来测量最大间隔，旨在不仅实现特征去相关、消除维度差异和隐式特征选择，还能进一步捕捉数据的几何信息和总体概率分布。在三类数据集上进行了大量实验：（1）包含线性可分性、非线性分布、类别不平衡和非球形结构以及高维多类数据的各种代表性合成数据集；（2）来自加州大学欧文分校（UCI）机器学习库的多个真实世界数据集；（3）大规模真实世界数据集和NDC数据集。实验结果表明，M³HE-SVM在分类准确性和测试效率方面均优于最大间隔超球面支持向量机（M³HS-SVM）和其他传统方法，表现出强大的鲁棒性和泛化能力。

引言

SVM [（Cortes和Vapnik，1995）]及其扩展 [（Ke等人，2018a），（Suykens和Vandewalle，1999），（Khemchandani和Chandra，2007），（Ke等人，2018b）]已广泛用于二元分类分析，并显示出优越的性能。然而，在现实世界中，多分类问题更为常见，例如文本分类 [（Al-Habib等人，2023）]、面部检测 [（Darma等人，2023）]、基因识别 [（Zeng和Chen，2024）]、图像分割 [（Priyadharsini等人，2024）] 和时间序列分析 [（Behera和Kumar，2025）]。尽管有持续的研究，但将SVM的二元分类方法扩展到多分类仍然存在一些挑战 [（Hsu和Lin，2002），（Iosifidis和Gabbouj，2016），（Blanco等人，2023）。

对于k类分类（其中k>2）的SVM框架，两种主要策略是“全部一起”策略 [（Shao等人，2013）] 和分解策略。在“全部一起”策略中，将分类问题视为一个大规模优化问题。然而，这种方法往往难以解决，可能不适用于实际应用。另一方面，分解策略将k类分类问题分解为多个二元分类问题。有三种类型的分解策略：（1）一对所有（OAR）[（Bottou等人，1994），（Tomar和Agarwal，2015）]。这种方法训练k个二元分类器，每个分类器用于区分一个类和其他类。新样本根据“胜者通吃”方案进行标记。注意，这种方法容易导致不平衡问题。（2）一对一（OAO）[（Tajima等人，2021），（Yang等人，2013）]。这种方法使用分解策略训练（总共k(k-1)/2个）二元分类器来区分一个类和另一个类。在分类新点时，使用多数投票等方法。然而，这种方法也可能导致不良结果，因为它没有利用剩余类的样本信息。（3）一对一对所有（OAO-ALL）[（Angulo等人，2003），（Xu等人，2013），（Hua和Ding，2015），（Ding等人，2017），（Qiang等人，2020），（Nasiri等人，2015）：这种方法考虑所有样本信息来构建输出为{-1,0,1}的子分类器（总共k(k-1)/2个），因此可以提供比前两种策略更好的预测结果。这种方法的代表性模型有K-SVCR [（Ding等人，2017）]、Twin-KSVC [（Qiang等人，2020）] 和LST-KSVC [（Nasiri等人，2015）]，它们分别基于SVM、TWSVM和LSSVM。然而，这种方法的时间复杂度较高，因为它在每个子分类器中都使用了所有样本，使得大规模分类问题更难以处理。使用超平面作为子分类器的主要问题是确定多分类问题决策边界的复杂性，而且可能会忽略重要的数据特征，导致性能不佳。

因此，出现了一系列超球面分类器，如SVDD [（Sch?lkopf等人，2001），（Tax和Duin，2004）]、SSLM [（Wu和Ye，2009）]、超球面SVM分类器（THSVM）[（Peng和Xu，2013）]、MMTSSVM [（Xu，2016）]、Pin-M³HM [（Xu等人，2018）]、KNN-M³VHM [（Xu等人，2019）]、MVE-SSR-SSLM [（Cao等人，2020）]、hype-sphere SVM（M³HS-SVM）[（Ke等人，2024）] 等 [（Ke等人，2023）-（Borah和Gupta，2021）]。更具体地说，Sch?lkopf等人通过扩展SVM引入了一类分类，寻找包含几乎所有样本的超球面描述（SVDD）。Peng等人旨在在特征空间中生成两个超球面，使一个类包含尽可能多的样本，并且与其他类保持尽可能远的距离（THSVM）[（Peng和Xu，2013）]。MMTSSVM [（Xu，2016）] 找到两个同心的球体来捕获多数类并排斥少数类，增加球体之间的间隔。然而，这些超球面分类器不适合多分类，并且在测试阶段缺乏稀疏性。M³HS-SVM使用单个优化模型而不是多个子分类器来找到k个决策函数。在对偶问题中，只有少量的支持向量决定了最终的超球面，由于稀疏性，从而提高了性能并降低了测试成本。然而，我们发现使用欧几里得距离测量最大间隔可能导致分类性能不佳，因为忽略了训练数据的维度和特征之间的相关性。为了解决这个问题，我们提出了超椭球面SVM（M³HE-SVM），它使用马氏距离来测量训练样本之间的最大间隔和距离。M³HE-SVM继承了M³HS-SVM的优点，如最大间隔和用于非线性可分问题的核技术，同时通过归一化和正交化实现了特征去相关。此外，引入马氏距离克服了特征维度对分类结果的影响，从而提高了泛化能力和鲁棒性，这一点在许多合成数据集、真实世界数据集和UCI数据集上的实验中得到了验证。

总之，为了强调我们M³HE-SVM的优势，表1提供了我们的方法与最近相关方法在几个关键特征方面的比较，如二次规划的数量、时间复杂度、决策边界、距离度量和几何灵活性。显然，我们的方法只需要一次二次规划（QP）即可实现多分类。此外，通过使用马氏距离度量，它实现了去相关和尺度不变性，从而更精确地捕捉几何流形和结构信息。值得注意的是，时间复杂度没有进一步增加。

本文的结构如下。第2节介绍相关工作。第3节介绍所提出的最优模型。第4节报告实验结果。最后，我们在第5节总结我们的工作并介绍未来要进行的研究计划。

相关工作

多类M³HS-SVM和距离测量概念的简要描述

为了方便起见，本文中使用了以下符号。对于k类分类问题，我们的训练样本为：