SVM^[1]是一种基于结构风险最小化的机器学习方法, 在解决小样本、高维问题和非线性问题等方面表现出良好的泛化能力和预测性能, 在生物医学^[2-5]、故障分析^[6-9]、图像识别^[10-12]等领域中被广泛应用, 并具有可观的分类效果^{[13, 14]}.

随着研究问题的复杂化, 现实的分类问题不单纯是二分类任务, 存在多分类的现象, 而SVM仅能用于处理二分类任务. 针对这个问题, 现有的工作已做出重要的贡献^[15-19]. 其中一对一(one-against-one, OAO)策略、一对一对余(one-against-one-against-rest, OAOAR)策略、一对多(one-against-all, OAA)策略是3种最常用的间接求解多分类问题的分解策略^[20]. 对于一个具有K个类别的多分类问题, 结合OAO策略的一对一支持向量机(one-against-one support vector machine, OAO SVM) 任选两个类别的样本, 分别作为正反两类, 构建K(K−1)/2个SVM分类器. 结合OAOAR策略的支持向量分类-回归机 (support vector classification-regression machine for K-class classification, K-SVCR)^[21]在正反两类的基础上, 增加了其余类, 减少了样本的误分. 将孪生支持向量机 (twin support vector machine, TWSVM)^[22]与OAA策略结合, Yang等人提出了MBSVM^[23], 通过将“最近”的决策方式转变为“最远”的决策方式, 有效减少了约束条件, 因而具有较低时间复杂度.

MBSVM虽然在算法效率上具有明显优势, 但其分类精度不够高. 主要原因有两点^[24], 一是用超平面进行拟合的类别之间可能相距较远, 很难使得超平面离它们同时都近; 二是约束条件较少, 二次规划问题(quadratic programming problem, QPP)的求解容易陷入局部最优. 对于第1个问题, 为达到更好的超平面拟合效果, 我们希望根据不同类别之间的相似度将所有类别划分成若干块, 块内类别的样本相似度相对较高, 块间类别的样本相似度相对较低; 对于第2个问题, 应该采用全局性更好的求解算法. ASSRFOA是一种新型的群智能优化算法, 相比于其他算法, 它继承了果蝇优化算法(fruit fly optimization algorithm, FOA)优秀的全局寻优能力, 同时通过改进候选解生成机制和搜索步长, 并引入柯西变异, 有效地改善了陷入局部最优的共性问题^[25-27]. 本文将采用ASSRFOA作为QPP的求解算法.

基于以上讨论, 本文从MBSVM存在的问题出发, 提出一种新的SVM多分类算法: 基于超球 (hypersphere)^[28]和ASSRFOA的MBSVM, 简称HA-MBSVM. 该算法框架如图1所示, 首先通过拟合超球, 获取各类样本对应超球的球心和半径. 利用球心和半径, 计算各类别之间的相似度判定值, 然后将所有类别划分成若干块, 块内类别样本相似度相对较高, 块间类别样本相似度相对较低, 最后再为各类别构建分类器并采用ASSRFOA求解QPP. 我们还引入了约束距离调节因子用以进一步提升HA-MBSVM的性能. 本文中的算法仅介绍使用了核方法的情形, 核函数选择径向基核函数(radial basis function, RBF), 规定矢量加粗表示, 标量不加粗.

综上所述, 本文的主要贡献如下.

(1)提出了一种新的SVM多分类算法. 利用拟合超球所得信息完成类别划分, 构建更准确的分类器.

(2)将ASSRFOA应用于QPP的求解, ASSRFOA良好的全局性有利于提高HA-MBSVM的性能.

(3)采用6个数据集对HA-MBSVM的性能进行评估. 实验结果表明, HA-MBSVM算法的性能优于常见的SVM多分类算法以及MBSVM.

1 相关工作

本节将介绍与HA-MBSVM密切相关的3项工作. 其中, 第1.1节介绍MBSVM^[23], 这是本文算法的改进出发点; 第1.2节介绍超球相关内容, HA-MBSVM采用文献[28]中生成超球的方法为各类别的样本拟合超球, 获取球心和半径用于后续的类别划分; 第1.3节介绍的ASSRFOA算法^[25]将用于求解QPP.

1.1 多生支持向量机

为方便讨论, 假定对于多分类问题, 有训练集:

$T = \{ ({{\boldsymbol{x}}_i}, {y_1}), \cdots , ({{\boldsymbol{x}}_l}, {y_l})\}$

(1)

其中, $\left( {{{\boldsymbol{x}}_i}, {y_i}} \right)$ 为第i个样本, ${{\boldsymbol{x}}_i} \in {R^n}$ 为特征向量, ${y_i} \in \left\{ {1, \cdots , K} \right\}$ 为类别标签, l是样本数, K为类别数.

对于训练集(1), 假设第k类样本构成矩阵 ${A_k} \in {R^{{l_k} \times n}}$ , 训练集(1)中除去第k类样本的剩余样本构成矩阵 ${B_k} = {[A_1^{\rm{T}}, \cdots , A_{k - 1}^{\rm{T}}, A_{k + 1}^{\rm{T}}, \cdots , A_K^{\rm{T}}]^{\rm{T}}}$ , $k = 1, \cdots , K,$ ${l_k}$ 为第k类样本的数量.

MBSVM每次选取一个类的样本作为负样本, 其他类的所有样本作为正样本, 寻找一个超平面, 要求该超平面离正样本尽可能近, 离负样本尽可能远, 即获得式(2)^{[22, 29]}.

$K({\boldsymbol{x}}, E){{\boldsymbol{v}}_k} + {b_k} = 0, {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} k = 1, \cdots , K$

(2)

其中, ${{\boldsymbol{v}}_k} \in {R^l}$ 和 ${b_k}$ 为模型参数, $E = {[A_1^{\rm{T}}, \cdots , A_K^{\rm{T}}]^{\rm{T}}},$ $K({\boldsymbol{x}}, E) \in {R^l}$ 为由核函数 $K({\boldsymbol{x}}, {\boldsymbol{y}})$ 产生的行向量. 为了计算 ${{\boldsymbol{v}}_k}$ 和 ${b_k}$ , 需要解决如下QPP问题, 如式(3)所示.

$\left\{\begin{array}{*{20}{l}} {\mathop {\min }\limits_{{{\boldsymbol{v}}_k}, {b_k}, {{\boldsymbol{\xi }}_k}} \dfrac{1}{2}{{\left\| {K({B_k}, E){{\boldsymbol{v}}_k} + {{\boldsymbol{e}}_{k1}}{b_k}} \right\|}^2} + {C_k}{\boldsymbol{e}}_{k2}^{\rm{T}}{{\boldsymbol{\xi }}_k}} \\ {{\text{ }}{\kern 1pt} {\rm{s.t.}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \left\{ {\begin{array}{*{20}{l}} {K({A_k}, E){{\boldsymbol{v}}_k} + {{\boldsymbol{e}}_{k2}}{b_k} \geqslant {{\boldsymbol{e}}_{k2}} - {{\boldsymbol{\xi }}_k}} \\ {{{\boldsymbol{\xi }}_k} \geqslant 0} \end{array}} \right.} \end{array} \right.$

(3)

其中, ${{\boldsymbol{\xi }}_k} \in {R^{{l_k}}}$ 为 ${A_k}$ 中样本对应松弛变量的列向量, ${C_k} > 0$ 为惩罚参数, ${{\boldsymbol{e}}_{k1}} \in {R^{l - {l_k}}}$ 和 ${{\boldsymbol{e}}_{k2}} \in {R^{{l_k}}}$ 为元素全是1的列向量, $K({A_k}, E)$ 和 $K({B_k}, E)$ 分别为由核函数 $K({\boldsymbol{x}}, {\boldsymbol{y}})$ 产生的 ${l_k} \times l$ 和 $(l - {l_k}) \times l$ 的矩阵.

由拉格朗日优化方法可将式(3)转为对偶问题(4).

$\left\{\begin{gathered} \mathop {\max }\limits_{{{\boldsymbol{\alpha }}_k}} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\boldsymbol{e}}_{k2}^{\rm{T}}{{\boldsymbol{\alpha }}_k} - \frac{1}{2}{\boldsymbol{\alpha }}_k^{\rm{T}}{R_k}{(S_k^{\rm{T}}{S_k})^{ - 1}}R_k^{\rm{T}}{{\boldsymbol{\alpha }}_k} \\ {\rm{s.t.}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} 0 \leqslant {{\boldsymbol{\alpha }}_k} \leqslant {C_k} \\ \end{gathered} \right.$

(4)

其中, ${{\boldsymbol{\alpha }}_k} \in {R^{{l_k}}}$ 为拉格朗日乘子的非负列向量, ${S _k} = [K({B_k}, E) {{\boldsymbol{e}}_{k1}}], {\kern 1pt} {\kern 1pt} {R_k} = [K({A_k}, E){\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {{\boldsymbol{e}}_{k2}}]$ . 为避免矩阵 $S_k^{\rm{T}}{S_k}$ 的病态化导致不可求逆, 需要为对偶问题(4)添加一个正则化项 $\varepsilon I$ , 其中 $\varepsilon > 0$ 为一固定的小标量, I为适当大小的单位矩阵, 于是对偶问题(4)可写成^[22]:

$\left\{\begin{array}{l} \mathop {\max }\limits_{{{\boldsymbol{\alpha }}_k}} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {{{\boldsymbol{e}}}}_{k2}^{\rm{T}}{{\boldsymbol{\alpha }}_k} - \dfrac{1}{2}{\boldsymbol{\alpha }}_k^{\rm{T}}{R_k}{(S_k^{\rm{T}}{S_k} + \varepsilon I)^{ - 1}}R_k^{\rm{T}}{{\boldsymbol{\alpha }}_k}\\ {\rm{s.t.}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} 0 \leqslant {{\boldsymbol{\alpha }}_k} \leqslant {C_k} \end{array}\right.$

(5)

由各类别对应QPP求解得到的超平面, MBSVM的决策函数计算新样本到各超平面的距离, 相距最远的超平面对应的类别即为新样本的预测类别标签.

1.2 超球

朱美琳等人提出的球结构支持向量机, 通过为每个类别拟合超球来解决多分类问题^[28]. 对于训练集(1), 当为 ${A_k}$ 拟合超球时, 假定 ${{\boldsymbol{n}}_k}$ 为最小超球的球心, ${r_k}$ 为最小超球的半径, 要求该最小超球尽可能包含 ${A_k}$ 中所有样本点, 通过引入松弛变量, 允许存在样本点位于超球外侧. 于是, 可得到如下优化问题(6).

$\left\{\begin{split}& \min \;\; {({r_k})^2} + {C_k}\sum\limits_{i = 1}^{{l_k}} {\xi _i^k} \\ & {\rm{s.t. }} \left\{ \begin{gathered} {\left\| {{\boldsymbol{x}}_i^k - {{\boldsymbol{n}}_k}} \right\|^2} \leqslant {({r_k})^2} + \xi _i^k \\ \xi _i^k \geqslant 0, \; i = 1, \cdots , {l_k} \end{gathered} \right. \end{split}\right.$

(6)

其中, ${\boldsymbol{x}}_i^k$ 为 ${A_k}$ 中第i个样本点的特征向量, $\xi _i^k$ 为 ${\boldsymbol{x}}_i^k$ 对应的松弛变量, ${C_k} > 0$ 为惩罚参数.

引入核函数并利用拉格朗日优化方法, 可将式(6)转为对偶问题(7).

$\left\{\begin{split} & \max \;\; \sum\limits_{i = 1}^{{l_k}} {\alpha _i^kK({\boldsymbol{x}}_i^k, {\boldsymbol{x}}_i^k)} - \sum\limits_{i = 1}^{{l_k}} {\sum\limits_{j = 1}^{{l_k}} {\alpha _i^k\alpha _j^kK({\boldsymbol{x}}_i^k, {\boldsymbol{x}}_j^k)} } \\ & {\rm{s.t.}} \left\{ \begin{gathered} \sum\limits_{i = 1}^{{l_k}} {\alpha _i^k} = 1 \\ 0 \leqslant \alpha _i^k \leqslant {C_k}, \; i = 1, \cdots , {l_k} \end{gathered} \right. \end{split}\right.$

(7)

其中, $\alpha _i^k$ 为式(6)中第i个约束条件对应的拉格朗日乘子. 通过求解式(7), 可以得到满足要求的拉格朗日乘子, 进而得到超球的球心和半径.

1.3 ASSRFOA具体步骤

步骤1. 初始化最大迭代次数Maxgen、果蝇种群规模Sizepop、味道浓度方差阈值 $\delta$ 和果蝇群体位置 ${{{{\boldsymbol{X}}}}}_{{\rm{axis}}}\in {R}^{D}、{{\boldsymbol{Y}}}_{{\rm{axis}}}\in {R}^{D}$ , D为待求解未知量的个数.

步骤2. 赋予果蝇个体随机的搜索方向和距离.

$\left\{ \begin{gathered} {{\boldsymbol{X}}_i} = {{\boldsymbol{X}}_{{{{\rm{axis}}}}}} + {\boldsymbol{Rand}} \\ {{\boldsymbol{Y}}_i} = {{\boldsymbol{Y}}_{{{{\rm{axis}}}}}} + {\boldsymbol{Rand}} \\ \end{gathered} \right.$

(8)

其中, ${\boldsymbol{Rand}} \in {R^D}$ , 其元素均为[−1, 1]之间的随机数, ${{\boldsymbol{X}}_i}$ 和 ${{\boldsymbol{Y}}_i}$ 为各果蝇个体基于群体位置随机分散后所处的位置, $i = 1, \cdots , {\textit{Sizepop}}$ .

步骤3. 设 ${{\boldsymbol{X}}_i} = ({p_i}, \cdots , {p_D}), {\kern 1pt} {\kern 1pt} {\kern 1pt} {{\boldsymbol{Y}}_i} = ({q_1}, \cdots , {q_D}),$ 利用式(9)计算果蝇个体到原点的间距 ${\boldsymbol{Dis}}{{\boldsymbol{t}}_i} \in {R^D}$ , 再利用式(10)计算味道浓度判定值 ${\boldsymbol{S}}{{\boldsymbol{D}}_i} \in {R^D}$ .

${\boldsymbol{Dis}}{{\boldsymbol{t}}_i} = \left(\sqrt {p_1^2 + q_1^2} , \cdots , \sqrt {p_D^2 + q_D^2} \right)$

(9)

${\boldsymbol{S}}{{\boldsymbol{D}}_i} = \left( {\frac{{sign(Rand)}}{{\sqrt {p_1^2 + q_1^2} }}, \cdots , \frac{{sign(Rand)}}{{\sqrt {p_D^2 + q_D^2} }}} \right)$

(10)

其中, 随机数 $Rand \in$ [−1, 1],sign函数如式(11)所示^[30].

$sign(x) = \left\{ \begin{gathered} 1, {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} x > 0 \\ 0, {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} x = 0 \\ - 1, {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} x < 0 \\ \end{gathered} \right.$

(11)

步骤4. 把 ${\boldsymbol{S}}{{\boldsymbol{D}}_i}$ 代入到味道浓度判定函数Fitness(即目标函数), 计算出味道浓度值 $smel{l_i}$ .

$smel{l_i} = Fitness({\boldsymbol{S}}{{\boldsymbol{D}}_i})$

(12)

步骤5. 找出果蝇种群中味道浓度值最优的果蝇, 并记录此果蝇的位置信息和相应的味道浓度值.

$[Currentbest, bestindex] = \max ({\boldsymbol{Smell}})$

(13)

其中, Currentbest为最优味道浓度值, $bestindex \in$ $\{ 1, \cdots , {\textit{Sizepop}}\}$ 为最优味道浓度值对应下标, ${\boldsymbol{Smell}}$ $= (smel{l_i}, \cdots , smel{l_{{\textit{Sizepop}}}})$ .

步骤6. 计算味道浓度方差值 ${\sigma ^2}$ , 且当迭代次数不为0时, 转至步骤7, 否则转至步骤8.

${\sigma ^2} = \frac{1}{{{\textit{Sizepop}}}}\displaystyle\sum\limits_{i = 1}^{{\textit{Sizepop}}} {{{\left(smel{l_i} - \sum\limits_{i = 1}^{{\textit{Sizepop}}} {\dfrac{{smel{l_i}}}{{{\textit{Sizepop}}}}} \right)^2}}}$

(14)

步骤7. 判断Currentbest是否优于历史最优味道浓度值Globalbest, 是则通过式(15)和式(16)保留Current-best并更新果蝇群体位置, 然后转至步骤8, 否则直接转至步骤8.

$Globalbest = Currentbest$

(15)

$\left\{ \begin{gathered} {{\boldsymbol{X}}_{{\rm{axis}}}} = {{\boldsymbol{X}}_{\textit{bestindex}}} \\ {{\boldsymbol{Y}}_{{\rm{axis}}}} = {{\boldsymbol{Y}}_{\textit{bestindex}}} \\ \end{gathered} \right.$

(16)

步骤8. 判断是否陷入局部最优, 若 ${\sigma ^2} < \delta$ , 则转至步骤9, 否则转至步骤10.

步骤9. 利用式(17)对果蝇个体位置进行柯西变异, 然后转至步骤11.

$\left\{ \begin{gathered} {{\boldsymbol{X}}_i} = {{\boldsymbol{X}}_i} + {{\boldsymbol{X}}_i} \times C(0, 1) \\ {{\boldsymbol{Y}}_i} = {{\boldsymbol{Y}}_i} + {{\boldsymbol{Y}}_i} \times C(0, 1) \\ \end{gathered} \right.$

(17)

其中, C(0, 1)为标准柯西分布.

步骤10. 根据式(18)更新果蝇个体位置, 然后转至步骤11.

$\left\{ \begin{gathered} {{\boldsymbol{X}}_i} = {{\boldsymbol{X}}_{{\rm{axis}}}} + \tau {{\rm{e}}^{\frac{{ - (\beta \times g)}}{{Maxgen}}}} \times {\boldsymbol{Rand}} \\ {{\boldsymbol{Y}}_i} = {{\boldsymbol{Y}}_{{\rm{axis}}}} + \tau {{\rm{e}}^{\frac{{ - (\beta \times g)}}{{Maxgen}}}} \times {\boldsymbol{Rand}} \\ \end{gathered} \right.$

(18)

其中, $\tau {{\rm{e}}^{\frac{{ - (\beta \times g)}}{{Maxgen}}}}$ 为搜索步长, $\tau$ 为步长调控因子, $\beta$ 为指数调节因子, g为当前迭代次数.

步骤11. 当前迭代次数不大于Maxgen, 执行步骤3至步骤10, 否则执行步骤12.

步骤12. 输出全局最优解.

2 HA-MBSVM 2.1 类别划分

在MBSVM中, 被作为正类的样本间可能相距较远, 很难构建一个超平面离它们同时都近. 于是我们尝试先将所有类别根据彼此间的相似度和给定阈值划分成若干块, 块内类别样本相似度相对较高, 块间类别样本相似度相对较低, 之后再分别以各块的样本作为约束条件来构建多个超平面, 从而避免因单个超平面难以同时有效地满足多个差异较大的类别样本的约束而导致分类器性能下降. 相似度判定值既应考虑超球球心, 也应考虑超球半径^[31], 由此我们得到如下相似度判定值的计算式(19).

${d_{ab}} = \frac{{\left\| {{{\boldsymbol{n}}_a} - {{\boldsymbol{n}}_b}} \right\|}}{{{r_a} + {r_b}}}$

(19)

其中, ${{\boldsymbol{n}}_a}$ 和 ${{\boldsymbol{n}}_b}$ , ${r_a}$ 和 ${r_b}$ 分别为第a类和第b类样本对应超球的球心和半径. ${d_{ab}}$ 值越小则两类样本相似度越高, 反之越低. 我们将所有类别从0开始标号, 得到类别标签集 ${S_0} = \{ 0, \cdots , K - 1\}$ . 由式(19)可以计算出各类别两两之间的相似度判定值, 其中的全局最大值 ${d_{\max}}$ 如式(20)所示.

${d_{\max}} = \mathop {\max }\limits_{a, b \in {S_0}, a < b} {d_{ab}}$

(20)

对 ${S_0}$ 进行一次类别划分, 将其分为差异性较大的两块, 块中的类别相似度较高, 得到此时类别划分集 $S = \{ {S_1}, {S_2}\}$ , 其中 ${S_1}$ 和 ${S_2}$ 为类别标签的集合. 然后再对各块分别进行一次类别划分, 重复上述过程, 块停止划分的标准为块中类别之间最大的相似度判定值与 ${d_{\max}}$ 的比值不大于给定阈值或块中只剩下一个类别. 由此得到最终的类别划分集 $S = \{ {S_1}, \cdots ,$ ${S_i}, \cdots , {S_m}\}$ , ${S_i} = \{ {s_{i1}}, \cdots , {s_{ij}}, \cdots , {s_{i{n_i}}}\}$ , 其中 ${s_{ij}}$ 为第i块中第j个类别标签, m为块总数, ${n_i}$ 为第i块中的标签数, $i = 1, \cdots , m$ . 完整的类别划分算法见算法1, 一次类别划分算法的细节见算法2, 用len(x)表示x中的类别标签数, 用a和b暂存类别标签, 用 $Algorithm2({d_{ab}}, {S_i})$ 表示对算法2的调用.

2.2 分类器构建

MBSVM在为各类别构建分类器时, 每次选取一个类的样本作为负样本, 其他类的所有样本作为正样本, 要求超平面离正样本尽可能近, 离负样本尽可能远. 这种做法虽然能够有效减少QPP的约束条件, 提高训练效率, 但在这种做法下, 决策函数将新样本归入相距最远的超平面对应的类别. 在样本空间中, 与某一超平面对应类别不同的样本也可能离该超平面较远, 因此相比于“最近”的决策方式, “最远”的决策方式错误分类的可能性更高.

我们利用HA-MBSVM为各类别构建分类器时, 每次选取一个类的样本作为正样本, 假设该类别标签 ${s_{ij}}$ 位于类别划分集S的块 ${S_i}$ 中, 其余块为 ${S_j} \in S(1 \leqslant j \leqslant m, j \ne i), {\kern 1pt} {\kern 1pt} {S'_i} = {S_i} - \{ {s_{ij}}\} ,$ 依次以 ${S_j}$ 和 ${S'_i}$ 中类别的样本为负样本, 构建m个子分类器(当 ${S_i}$ 中仅有 ${s_{ij}}$ 一个类别时, 构建m−1个子分类器), 即寻找m个超平面, 如式(21)所示, 要求超平面离正样本尽可能近, 离负样本尽可能远, 构建过程如图2所示.

算法1. 完整的类别划分

输入: 各类样本对应超球的球心 $\scriptstyle {{\boldsymbol{n}}_k}$ 和半径 $\scriptstyle {r_k}$ , $\scriptstyle k =$ $\scriptstyle 0, \cdots , K - 1$ ; 类别标签集 $\scriptstyle {S_0}$ ; 划分停止阈值 $\scriptstyle \xi$ .

输出: 类别划分集S.

1. 由式(19)计算出各类别两两之间的相似度判定值, 由式(20)得到其中的全局最大值 $\scriptstyle {d_{\max}}$ ;

2. $\scriptstyle flag \leftarrow true$ ;

3. $\scriptstyle S \leftarrow {S_0}$ ;

4. WHILE flag /*不断进行划分, 直到所有块均满足停止条件*/

5. $\scriptstyle flag \leftarrow false$ ;

6. FOR $\scriptstyle {S_i}$ IN S /*依次处理当前 $\scriptstyle S$ 中所有的块*/

7. $\scriptstyle {d'_{\max}} \leftarrow \mathop {\max }\limits_{a, b \in {S_i}, a < b} {d_{ab}}$ ;

8. IF $\scriptstyle len({S_i}) > 1$ AND $\scriptstyle \frac{{{d'_{{\max}}}}}{{{d_{{\rm{max}}}}}} > \xi$ THEN /*若不满足停止条件, 则进行一次类别划分*/

9. $\scriptstyle {S_{i1}}, {S_{i2}} \leftarrow Algorithm{\text{2(}}{d_{ab}}, {S_i}{\text{)}}$ ; /*调用算法2*/

10. $\scriptstyle {S_i} \leftarrow {S_{i1}}, {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} S \leftarrow S \cup \{ {S_{i2}}\}$ ;

11. $\scriptstyle flag \leftarrow true$ ;

12. END IF

13. END FOR

14. END WHILE

15. RETURN S;

假设类别 ${s_{ij}}$ 对应正样本构成矩阵 ${P_{ij}} \in {R^{{l_{ij}} \times n}}$ , 各子分类器对应负样本构成矩阵 $Q_{ij}^k \in {R^{l_{ij}^k \times n}}, k = 1, \cdots , m,$ ${l_{ij}}$ 和 $l_{ij}^k$ 分别为正样本和负样本的数量.

$K({\boldsymbol{x}}, E_{ij}^k){\boldsymbol{v}}_{ij}^k + b_{ij}^k = 0, {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} k = 1, \cdots , m$

(21)

其中, ${\boldsymbol{v}}_{ij}^k$ 和 $b_{ij}^k$ 为模型参数, $E_{ij}^k = {[P_{ij}^{\rm{T}}, {(Q_{ij}^k)^{\rm{T}}}]^{\rm{T}}}$ , $K({\boldsymbol{x}}, E_{ij}^k) \in {R^{{l_{ij}} + l_{ij}^k}}$ 为由核函数 $K({\boldsymbol{x}}, {\boldsymbol{y}})$ 产生的行向量. 类似于MBSVM, 我们有如下QPP 式(22).

$\left\{ \begin{gathered} \mathop {\min }\limits_{{\boldsymbol{v}}_{ij}^k, b_{ij}^k, {\boldsymbol{\xi }}_{ij}^k} \frac{1}{2}{\left\| {K({P_{ij}}, E_{ij}^k){\boldsymbol{v}}_{ij}^k + {\boldsymbol{e}}_{ij}^{k1}b_{ij}^k} \right\|^2} + C_{ij}^k{({\boldsymbol{e}}_{ij}^{k2})^{\rm{T}}}{\boldsymbol{\xi }}_{ij}^k \\ {\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{s.t.}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \left\{ \begin{gathered} K(Q_{ij}^k, E_{ij}^k){\boldsymbol{v}}_{ij}^k + {\boldsymbol{e}}_{ij}^{k2}b_{ij}^k \geqslant {\boldsymbol{e}}_{ij}^{k2} - {\boldsymbol{\xi }}_{ij}^k \\ {\boldsymbol{\xi }}_{ij}^k \geqslant 0 \\ \end{gathered} \right. \\ \end{gathered} \right.$

(22)

其中, ${\boldsymbol{\xi }}_{ij}^k \in {R^{l_{ij}^k}}$ 为 $Q_{ij}^k$ 中样本对应松弛变量的列向量, $C_{ij}^k > 0$ 为惩罚参数, ${\boldsymbol{e}}_{ij}^{k1} \in {R^{{l_{ij}}}}$ 和 ${\boldsymbol{e}}_{ij}^{k2} \in {R^{l_{ij}^k}}$ 为元素全是1的列向量.

算法2. 一次类别划分

输入: 各类别间的相似度判定值; 待划分块 $\scriptstyle {S_i}$ .

输出: 类别划分结果 $\scriptstyle {S_{i1}}$ 和 $\scriptstyle {S_{i2}}$ .

1. IF $\scriptstyle len({S_i}) = 2$ THEN /*若 $\scriptstyle {S_i}$ 中仅有两个类别标签, 则可直接输出结果*/

2. 将 $\scriptstyle {S_i}$ 中的两个类别标签分别作为 $\scriptstyle {S_{i1}}$ 和 $\scriptstyle {S_{i2}}$ ;

3. RETURN $\scriptstyle {S_{i1}}$ 和 $\scriptstyle {S_{i2}}$ ;

4. END IF

5. $\scriptstyle a, b \leftarrow \mathop {\arg {\kern 1pt} {\kern 1pt} \min }\limits_{a, b \in {S_i}, a < b} {\kern 1pt} {\kern 1pt} {\kern 1pt} {d_{ab}}, {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {S_{i1}} \leftarrow \{ a, b\} , {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {S_i} \leftarrow {S_i} - {S_{i1}}$ ;

6. $\scriptstyle b \leftarrow \mathop {\arg {\kern 1pt} {\kern 1pt} \max }\limits_{b \in {S_i}} {\kern 1pt} {\kern 1pt} {\kern 1pt} \sum\limits_{a \in {S_{i1}}} {{d_{ab}}} , {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {S_{i2}} \leftarrow \{ b\} , {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {S_i} \leftarrow {S_i} - {S_{i2}}$ ;

7. WHILE true /*不断将 $\scriptstyle {S_i}$ 中的类别标签分配到 $\scriptstyle {S_{i1}}$ 和 $\scriptstyle {S_{i2}}$ 中, 当 $\scriptstyle {S_i}$ 为空时输出结果*/

8. IF $\scriptstyle len({S_i}) = 0$ THEN

9. RETURN $\scriptstyle {S_{i1}}$ 和 $\scriptstyle {S_{i2}}$ ;

10. ELSE

11. $\scriptstyle b \leftarrow \mathop {\arg {\kern 1pt} {\kern 1pt} \min }\limits_{b \in {S_i}} {\kern 1pt} {\kern 1pt} {\kern 1pt} \sum\limits_{a \in {S_{i2}}} {{d_{ab}}}$ ;

12. $\scriptstyle {S_{i2}} \leftarrow {S_{i2}} \cup \{ b\} , {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {S_i} \leftarrow {S_i} - {S_{i2}}$ ;

13. IF $\scriptstyle len({S_i}) = 0$ THEN

14. RETURN $\scriptstyle {S_{i1}}$ 和 $\scriptstyle {S_{i2}}$ ;

15. ELSE IF $\scriptstyle len({S_i}) = 1$ THEN

16. IF $\scriptstyle \sum\limits_{a \in {S_i}, b \in {S_{i1}}} {{d_{ab}}} \leqslant \sum\limits_{a \in {S_i}, b \in {S_{i2}}} {{d_{ab}}}$ THEN

17. $\scriptstyle {S_{i1}} \leftarrow {S_{i1}} \cup {S_i}$ ;

18. ELSE

19. $\scriptstyle {S_{i2}} \leftarrow {S_{i2}} \cup {S_i}$ ;

20. END IF

21. RETURN $\scriptstyle {S_{i1}}$ 和 $\scriptstyle {S_{i2}}$ ;

22. ELSE

23. $\scriptstyle a \leftarrow \mathop {\arg {\kern 1pt} {\kern 1pt} \min }\limits_{a \in {S_i}} {\kern 1pt} {\kern 1pt} {\kern 1pt} \sum\limits_{b \in {S_{i1}}} {{d_{ab}}} , {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {S_{i1}} \leftarrow {S_{i1}} \cup \{ a\} ;$

24. $\scriptstyle {S_i} \leftarrow {S_i} - {S_{i1}}$ ;

25. END IF

26. END IF

27. END WHILE

2.3 约束距离调整

QPP 式(22)中的约束条件用 ${\kern 1pt} {\boldsymbol{e}}_{ij}^{k2}$ 限制负样本尽可能离超平面有1的约束距离^[23]. 但对于同一块中相似度较高的两个类别, 这一约束距离可能是不足够的, 由于两个类别的子分类器可能较为相似, 分类器对较小的距离差异不敏感, 此时样本容易被错误分类. 因此, 我们在QPP 式(22)中添加参数 $d_{ij}^k$ , 称为约束距离调节因子, 用于调整超平面与负样本之间的约束距离, 提高分类器的差异性, 由此得到QPP 式(23).

$\left\{ \begin{split}& \mathop {\min }\limits_{{\boldsymbol{v}}_{ij}^k, b_{ij}^k, {\boldsymbol{\xi }}_{ij}^k} \frac{1}{2}{\left\| {K({P_{ij}}, E_{ij}^k){\boldsymbol{v}}_{ij}^k + {\boldsymbol{e}}_{ij}^{k1}b_{ij}^k} \right\|^2} + C_{ij}^k{({\boldsymbol{e}}_{ij}^{k2})^{\rm{T}}}{\boldsymbol{\xi }}_{ij}^k \\ & {\kern 1pt} {\kern 1pt} {\kern 1pt} {\rm{s.t.}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} \left\{ \begin{array}{l} K(Q_{ij}^k, E_{ij}^k){\boldsymbol{v}}_{ij}^k + {\boldsymbol{e}}_{ij}^{k2}b_{ij}^k \geqslant {\boldsymbol{e}}_{ij}^{k2}d_{ij}^k - {\boldsymbol{\xi }}_{ij}^k \\ {\boldsymbol{\xi }}_{ij}^k \geqslant 0 \end{array} \right. \end{split} \right.$

(23)

由拉格朗日优化方法可得式(23)的对偶问题(24).

$\left\{\begin{split}& \mathop {\max }\limits_{{\boldsymbol{\alpha }}_{ij}^k} - \frac{1}{2}{({\boldsymbol{\alpha }}_{ij}^k)^{\rm{T}}}R_{ij}^k{[{(S_{ij}^k)^{\rm{T}}}S_{ij}^k + \varepsilon I]^{ - 1}}{(R_{ij}^k)^{\rm{T}}}{\boldsymbol{\alpha }}_{ij}^k + d_{ij}^k {({\boldsymbol{e}}_{ij}^{k2})^{\rm{T}}}{\boldsymbol{\alpha }}_{ij}^k\\ & {\rm{s.t.}} \; 0 \leqslant {\boldsymbol{\alpha }}_{ij}^k \leqslant C_{ij}^k \end{split} \right.$

(24)

其中, ${\boldsymbol{\alpha }}_{ij}^k \in {R^{l_{ij}^k}}$ 为拉格朗日乘子的非负列向量, $S_{ij}^k = [K({P_{ij}}, E_{ij}^k) {\boldsymbol{e}}_{ij}^{k1}], R_{ij}^k = [K(Q_{ij}^k, E_{ij}^k) {\boldsymbol{e}}_{ij}^{k2}]$ .

通过求解m个对偶问题(24), 我们得到类别 ${s_{ij}}$ 的分类器, 该分类器由m个子分类器组成. 类似地, 我们为每一个类别都构建相应的分类器, 由此得到HA-MBSVM的决策函数(25).

$f({\boldsymbol{x}}) = \arg \mathop {\min }\limits_{i, j} \frac{1}{{{N_{ij}}}}\sum\limits_{k = 1}^{{N_{ij}}} {\frac{{\left| {K({\boldsymbol{x}}, E_{ij}^k){\boldsymbol{v}}_{ij}^k + b_{ij}^k} \right|}}{{\sqrt {{{({\boldsymbol{v}}_{ij}^k)}^{\rm{T}}}K(E_{ij}^k, E){\boldsymbol{v}}_{ij}^k} }}}$

(25)

其中, $i = 1, \cdots , m, {\kern 1pt} {\kern 1pt} {\kern 1pt} j = 1, \cdots , {n_i},$ 指向类别划分集中第i块第j个类别标签, ${N_{ij}}$ 为类别 ${s_{ij}}$ 的子分类器数量. 决策函数(25)计算新样本到各类别子分类器的平均距离, 将其归入平均距离最小的类别.

2.4 求解QPP

Yang等人^[23]采用逐次超松弛迭代法(successive over relaxation, SOR)求解MBSVM中的QPP, 该方法求解速度快但求解质量不高. 为了得到性能更好的模型, 本文采用全局优化能力较好的ASSRFOA来求解QPP. HA-MBSVM关键需要求解对偶问题(24), 注意到其中有约束条件 $0 \leqslant {\boldsymbol{\alpha }}_{ij}^k \leqslant C_{ij}^k$ , 因此在利用ASSRFOA求解式(24)时, 应对 ${\boldsymbol{\alpha }}_{ij}^k$ 的候选解进行越界处理: 当候选解小于0时, 变为0; 当候选解大于 $C_{ij}^k$ 时, 变为 $C_{ij}^k$ , 当候选解介于0与 $C_{ij}^k$ 之间, 保留原值.

3 实验分析

在本节中, 我们从3方面评估所提出的HA- MBSVM算法. 第3.1节是HA-MBSVM与其他3种算法在4项评估指标下的性能对比, 第3.2节对HA-MBSVM中的部分参数进行讨论, 第3.3节是消融实验结果.

实验选用了以下6个用于多分类的数据集 ( https://github.com/renatopp/arff-datasets): iris、wine、zoo、tae、lymph和dermatology. 所有实验均在PC机(16 GB RAM, AMD Ryzen 5 5600U处理器, Windows 10操作系统)上采用Python环境实现. 数据集的具体信息见表1. 规定HA-MBSVM中生成的最小超球至少包含90%的样本点. 所有算法中的核函数选择RBF, 即式(26).

$K({\boldsymbol{x}}, {\boldsymbol{y}}) = \exp \left( - \frac{{{{\left\| {{\boldsymbol{x}} - {\boldsymbol{y}}} \right\|}^2}}}{{2{\sigma ^2}}}\right)$

(26)

其中, ${\boldsymbol{x}}$ 与 ${\boldsymbol{y}}$ 为维度相同的向量, $\sigma > 0$ 为RBF的带宽.

3.1 分类性能对比

我们将HA-MBSVM与OAO SVM、一对多支持向量机(one-against-all support vector machine, OAA SVM)、MBSVM进行性能对比, 4项评估指标分别为准确率, 查准率, 查全率和F1值, 采用5折交叉验证寻找最优参数. 具体实验设置见如下.

对于OAO SVM、OAA SVM、MBSVM, RBF带宽 ${\sigma}$ 的候选值集合为 $[{2^{ - 10}}, {2^{ - 9}}, {2^{ - 8}}, \cdots , {2^4}]$ , 惩罚参数 $C$ 的候选值集合为 $[{2^{ - 2}}, {2^{ - 3}}, {2^{ - 4}}, \cdots , {2^{12}}]$ . 对于HA-MBSVM, 在拟合超球时, RBF带宽 ${\sigma _1}$ 和惩罚参数 ${C_1}$ 的候选值集合均为 $[{2^{ - 2}}, {2^4}, {2^{10}}]$ , 类别划分停止阈值 $\xi$ 的候选值集合为 $[0.2, 0.4, 0.6, 0.8, 1]$ ; 在构建分类器时, RBF带宽 ${\sigma _2}$ 的候选值集合为 $[{2^{ - 3}}, {2^{ - 1.75}}, {2^{ - 0.5}}, \cdots , {2^7}]$ , 惩罚参数 ${C_2}$ 的候选值集合为 $[{2^3}, {2^9}, {2^{15}}]$ , 约束距离调节因子d的候选值集合为 $[{2^0}, {2^1}, {2^2}, {2^3}, {2^4}, {2^5}, {2^6}]$ . 各类别样本在拟合超球和构建分类器时使用统一的初始参数, 两个环节中的QPP使用ASSRFOA完成求解. 对于ASSRFOA中的初始化参数, 在拟合超球时的最大迭代次数Maxgen₁默认为100, 在构建分类器时的最大迭代次数Maxgen₂候选值集合为 $[90, 150, 210]$ , 其余ASSRFOA中的参数采用文献[25]中实验的取值作为默认参数值, 即种群规模Sizepop=30, 步长调控因子 $\tau$ =0.2, 指数调节因子 $\;\beta$ =2, 味道浓度方差阈值 $\delta$ = ${10^{ - 6}}$ .

表2为6个数据集上, HA-MBSVM与其他3种算法关于4项评估指标5折交叉验证的最佳(以准确率为基准)平均结果. 表3为3个对比算法在最佳平均结果下的最优参数, 表4为HA-MBSVM在最佳平均结果下的最优参数.

由表2可知, 除了dermatology数据集, HA- MBSVM在所有数据集上的所有指标均为最优或仅稍次于最优; 在iris和tae数据集上, HA-MBSVM的4项指标全部优于其他算法; 在tae数据集上, HA-MBSVM的提升幅度尤为显著, 相比于表现最差的算法, 4项指标的提升幅度可达17.53%–19.60%, 这证明了HA-MBSVM的有效性和较好的通用性. 从整体上看, HA-MBSVM在所有数据集上对MBSVM的分类性能都有所提升, 但在zoo和dermatology数据集上, 提升幅度有限, HA-MBSVM与MBSVM表现相似, 这一方面是因为这两个数据集的样本个数较少而类别数较多, 所以各类别数据分布的差异性不突出, 不易生成合适的类别划分结果, 另一方面是因为数据集本身分布相对均衡, 在不进行类别划分等操作的情况下就能达到较好的分类性能.

3.2 参数讨论

在本节中, 我们讨论类别划分停止阈值 $\xi$ 和构建分类器时RBF的带宽 ${\sigma _2}$ 对算法性能的影响.

对于 $\xi$ , 我们将HA-MBSVM中的其他参数固定为表4中的最优参数, $\xi$ 的候选值集合为[0.2, 0.4, 0.6, 0.8, 1], 在各数据集上进行5次5折交叉验证实验, 取5次实验的平均准确率为实验结果, 具体数值如表5所示. $\xi$ 用于控制类别划分的过程, $\xi$ 取值越小, 对类别标签集进行划分的次数越多, 产生的标签块越多. 由表5可见, 不同数据集的最优 $\xi$ 取值不完全相同, 但较多地集中在0.4与0.6之中. 这是因为5折交叉验证中每一折的实验都会采用相同的 $\xi$ 进行类别划分, 0.4与0.6的取值能够较好地依据每一折训练集的数据分布产生合适的类别划分结果. 除了tae和wine数据集, HA-MBSVM在其余数据集上, $\xi$ 不为1时的性能均显著优于 $\xi$ 为1时的性能, 这说明了进行类别划分再构建分类器的必要性与有效性. 此外, 同一数据集上不同 $\xi$ 取值的实验结果可能较为接近, 如iris数据集上, $\xi$ 取值为0.4与0.6时的实验结果仅相差0.0013, 这是因为相近的 $\xi$ 取值可能会产生相同的类别划分结果.

对于 ${\sigma _2}$ , 我们将HA-MBSVM中其他参数固定为表4的最优参数, ${\sigma _2}$ 的候选值集合为 $[{2^{ - 3}}, {2^{ - 1.75}}, {2^{ - 0.5}}, \cdots , {2^7}]$ , 具体实验结果如表6所示. ${\sigma _2}$ 为RBF的带宽, 利用核函数可以将样本从原始空间映射到一个更高维的特征空间, 使得样本在这个特征空间内线性可分. ${\sigma _2}$ 的改变实质上是HA-MBSVM向高维度映射的特征空间复杂度的改变. 当 ${\sigma _2}$ 增大时, 高维特征空间的复杂度降低, 线性可分程度也将降低; 而当 ${\sigma _2}$ 趋向于0时, 高维特征空间的复杂度趋向于无穷, 此时虽能将任意数据映射为线性可分, 但往往会造成严重的过拟合问题^[32]. 由表6可见, 当 ${\sigma _2}$ 取值较小时, 除iris数据集外, HA-MBSVM在其余数据集上的性能都出现严重下降, 而当 ${\sigma _2}$ 取较大值时, HA-MBSVM在所有数据集上的表现都很差, 这是高维特征空间复杂度的极端变化带来的影响. 此外, 不同数据集的最优 ${\sigma _2}$ 取值不完全相同, 但主要集中在 ${2^{0.75}}$ 和 ${2^2}$ 之中, 这是因为这两个取值相对适中, 映射的高维特征空间的复杂度能够较好地权衡样本的线性可分程度与模型的泛化能力.

3.3 消融实验

为了更好理解HA-MBSVM中不同部分对算法整体性能提升的影响, 我们设计了HA-MBSVM的5种变体, 进行全面的消融实验.首先, 我们将MBSVM设置为base模型, 以此为基础逐步添加HA-MBSVM中不同的设计组件, 得到对应的变体如下所示.

(I) base+超球与类别划分: base中的RBF带宽与惩罚参数取表3中MBSVM的最优参数, 拟合超球时RBF带宽与惩罚参数候选值集合为 $[{2^{ - 2}}, {2^4}, {2^{10}}]$ , 划分停止阈值的候选值集合为 $[0.2, 0.4, 0.6, 0.8]$ .

(II) base+ASSRFOA: base中的RBF带宽与惩罚参数取表3中MBSVM的最优参数, ASSRFOA最大迭代次数的候选值集合为 $[90, 150, 210]$ .

(III) base+“最近”的决策方式: base中的RBF带宽候选值集合为 $[{2^{ - 10}}, {2^{ - 9}}, {2^{ - 8}}, \cdots , {2^4}]$ , 惩罚参数候选值集合为 $[{2^{ - 2}}, {2^{ - 3}}, {2^{ - 4}}, \cdots , {2^{12}}]$ .

(IV) base+超球与类别划分+ASSRFOA+“最近”的决策方式: 我们通过将HA-MBSVM中的约束距离调节因子固定为1, 其余参数取表4中HA-MBSVM的最优参数来实现该变体.

(V) base+超球与类别划分+ASSRFOA+“最近”的决策方式+约束距离调节因子: 该变体即为HA-MBSVM. 我们取约束距离调节因子候选值集合为 $[{2^1}, {2^2}, {2^3}, {2^4}, {2^5}, {2^6}]$ , 其余参数取表4中的最优参数.

依据如上参数设定, 我们在各数据集上进行5次5折交叉验证实验, 最优结果作为单次实验结果, 5次实验的平均结果作为最终实验结果, 如图3所示.

由图3可知, 变体(I)、(II)、(III)在各数据集上表现不一, 从整体上看, 这3种变体无法有效提升base模型性能. 变体(I)添加了超球与类别划分模块, 但仍采用“最远”的决策方式, 在各数据集上表现均较差, 这说明“最远”的决策方式不适用于进行了类别划分的情况. 变体(II)仅将QPP求解算法换为ASSRFOA, 除了dermatology, 在其他数据集上均有两项以上的指标优于base模型, 尤其在iris和lymph上, 各指标均优于base模型, 这说明使用ASSRFOA求解QPP的有效性. 但由于变体(II)缺少超球与类别划分模块, 且未采用“最近”的决策方式和添加约束距离调节因子, 所以性能提升幅度有限. 变体(III)采用“最近”的决策方式, 但缺少超球与类别划分模块, 在各数据集上表现很不稳定, 在iris和tae上各指标均优于base模型, 但在zoo和dermatology上所有指标均不如base模型, 这说明“最近”的决策方式和超球与类别划分模块结合使用的重要性. 对于变体(IV), 仅在zoo上的查准率和F1值以及dermatology上的准确率和查全率略低于base模型, 其余数据集上4项指标均优于base模型, 这说明组合使用HA-MBSVM的各组件能有效提升base模型性能. 变体(V)在变体(IV)基础上加入约束距离调节因子, 仅在dermatology上的查准率略低于变体(IV), 而在其余数据集上4项评估指标均优于变体(IV), 这说明引入约束距离调节因子的有效性. 图3(b)与(d)可见在wine和tae上, 变体(IV)和变体(V)对base模型性能有显著提升.

4 结论

本文对MBSVM进行改进, 提出了基于超球和ASSRFOA的多生支持向量机: HA-MBSVM. 该算法利用拟合超球得到的球心和半径先进行类别划分再构建分类器, 同时运用全局优化能力较好的ASSRFOA来求解算法中的QPP, 为了调整超平面与负样本之间的约束距离, 适当提高分类器的差异性, 我们还添加了一个约束距离调节因子. 在6个数据集上的实验结果表明HA-MBSVM的整体性能优于常见的SVM多分类算法以及MBSVM. 但HA-MBSVM中涉及参数较多, 需要求解的QPP较多, 如何更高效地选取最优参数, 减少训练时间是未来的研究方向.