孪生支持向量机(twin support vector machine, 简称TWSVM)是在传统支持向量机(support vector machine, 简称SVM)^{[1, 2]}的基础上发展而来的一种新型机器学习算法.为了解决二分类问题, TWSVM为每一类样本构造一个超平面, 使每类样本尽可能离本类的超平面更近, 而尽可能地远离另一类的超平面^[3].TWSVM的两个超平面通过求解两个二次规划问题(quadratic programming problems, 简称QPPs)得到, 每个QPP的约束条件都只与一类样本有关.TWSVM不但保持了SVM的优点, 而且训练速度比传统SVM要快4倍^[4].为了进一步提升TWSVM的性能, 学者们已经提出了不少改进算法^[5-21], 例如, Kumar等人提出了TWSVM的最小二乘模型, 称作最小二乘孪生支持向量机(least squares twin support vector machine, 简称LSTSVM)^[5].LSTSVM的训练过程中仅需求解线性方程组, 因此训练速度远快于TWSVM.丁世飞等人根据样本点的位置为每个训练样本赋予不同的重要性, 以降低异常点对非平行超平面的影响, 并使用基于CHKS函数的光滑算法快速求解二次规划问题, 得到了训练速度更快、鲁棒性更强的加权光滑CHKS TWSVM^[11].此外, TWSVM的应用研究也已经取得了不少成果^[22-25].

TWSVM最初是为解决二分类问题而提出来的, 不能直接用于多分类问题.现实问题中, 更加普遍的是多分类问题, 因此, 多分类孪生支持向量机(multi class twin support vector machines, 简称MTWSVMs)的研究具有现实意义^[26].除了将TWSVM与多分类支持向量机中常用策略结合得到相应的MTWSVMs外, 为了进一步提升分类能力和训练速度, 学者们还提出了不少新颖的改进算法.目前, MTWSVMs的研究已经取得了比较丰富的成果, 但是针对MTWSVMs的相关综述性研究并不多, 已有的综述性工作也没有给出全面的总结和分析.Tomar和Agarwal仅对基于LSTSVM的多分类算法进行了比较^[26].Ding等人在他们的TWSVMs综述中初步分析了偏二叉树MTWSVM和Boosting MTWSVM算法.Tomar等人介绍了Twin KVC、多生支持向量机(multiple birth support vector machine, 简称MBSVM)、决策树TWSVM、优化的有向无环图最小二乘孪生支持向量机和最小二乘Twin KSVC^[27], 但没有对它们进行归类总结, 也没有分析它们的基本思想.不同于已有工作, 本文根据MTWSVMs的子分类器的组织结构将它们分为基于“一对多”策略的MTWSVMs、基于“一对一”策略的MTWSVMs、基于“一对一对余”策略的MTWSVMs、基于二叉树的MTWSVMs、基于“多对一”策略的MTWSVMs.虽然基于有向无环图(directed acyclic graph, 简称DAG)结构的MTWSVMs具有与“一对一”MTWSVMs类似的训练过程, 但其决策过程比较特殊, 因此也单独作为一类而加以分析.本文在分类基础上对比各种MTWSVMs模型的同时, 在各个类型的MTWSVMs中又将改进模型与对应的原MTWSVMs模型进行对比.因此, 本文从多方面综合性地综述了MTWSVMs, 较已有工作更全面地总结了MTWSVMs的研究发展状况.本文称文献[4]中最初的TWSVM为标准TWSVM, TWSVMs包括标准TWSVM以及所有TWSVM的改进算法, MTWSVMs是指基于TWSVM及其改进算法的所有多分类算法.

1 二分类孪生支持向量机简介

本节介绍TWSVM的数学模型.假设在Rⁿ的空间中有m个训练样本, 它们都有n个属性, 其中有m₁个样本属于正类, m₂个样本属于负类, 它们分别用矩阵A和矩阵B来表示.矩阵A的每行各代表一个属于正类的样本点.矩阵B的每行各代表一个属于负类的样本点.

1.1 线性孪生支持向量机

对于线性可分的二分类问题, TWSVM的求解过程即在n维实数空间Rⁿ中寻找到两个非平行的超平面:

$ {x^T}{w_1} + {b_1} = 0\ 和\ {x^T}{w_2} + {b_2} = 0 $

(1)

其中, w₁和w₂是两个超平面的法向量, b₁和b₂是两个超平面的偏移量.它们一般通过求解下面两个二次规划问题而得到:

$ \left. \begin{array}{l} ({\rm{TWSVM}}1)\ \min \frac{1}{2}{(A{w_1} + {e_1}{b_1})^T}(A{w_1} + {e_1}{b_1}) + {c_1}e_2^T\xi \\ {\rm{s}}{\rm{.t}}{\rm{. }}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; - (B{w_1} + {e_2}{b_1}) + \xi \ge {e_2}, \xi \ge 0 \end{array} \right\} $

(2)

$ \left. \begin{array}{l} {\rm{(TWSVM2)}}\ \min \frac{1}{2}{(B{w_2} + {e_2}{b_2})^T}(B{w_2} + {e_2}{b_2}) + {c_2}e_1^T\eta \\ {\rm{s}}{\rm{.t}}{\rm{. }}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;(A{w_2} + {e_1}{b_2}) + \eta \ge {e_1}, \eta \ge 0 \end{array} \right\} $

(3)

其中, c₁和c₂是两个惩罚参数, e₁和e₂是元素全为1的列向量, ξ和η是松弛变量.在TWSVM的二次规划问题中, 目标函数的几何意义是每个超平面应尽可能地离本类数据点更近, 而约束条件则规定超平面要离其他类样本至少距离为1个单位.

直接求解QPPs(2)和QPPs(3)比较困难, 往往转化为其对偶问题进行求解, QPPs(2)和QPPs(3)对应的对偶问题为

$ \left. \begin{array}{l} ({\rm{TWSVM}}1)\ \max \, e_2^T\alpha - \frac{1}{2}{\alpha ^T}G{({H^T}H)^{ - 1}}{G^T}\alpha \\ {\rm{s}}{\rm{.t}}{\rm{.}}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;0 \le \alpha \le {c_1} \end{array} \right\} $

(4)

$ \left. \begin{array}{l} ({\rm{TWSVM}}2)\ \max \, e_1^T\gamma - \frac{1}{2}{\gamma ^T}P{({Q^T}Q)^{ - 1}}{P^T}\gamma \\ {\rm{s}}{\rm{.t}}{\rm{.}}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;0 \le \gamma \le {c_2} \end{array} \right\} $

(5)

其中, H=P=[A, e₁], G=Q=[B, e₂].

在得到两个分类超平面后, 线性TWSVM通过如下决策函数判定新样本的类别标签:

$ Label(x)=\underset{k=1, 2}{\mathop{\arg \min }}\, \left( {\left| {{x}^{T}}{{w}_{k}}+{{b}_{k}} \right|}/{\sqrt{w_{k}^{T}{{w}_{k}}}}\; \right) $

(6)

不难发现, 线性TWSVM的决策准则可简单描述为:样本离哪个超平面近, 就归于该超平面对应的类.

图 1所示为二维空间中线性TWSVM的示意图.

本文通过图 1说明TWSVM的几何解释.图中黑色点代表正类样本, 灰色点代表负类样本.图中两条直线表示两个超平面.黑色点都离左上角的直线近而离另一超平面远, 灰色点则反之.因此, 如果待分类的样本离左上角的直线近, 就应将其标为和黑色点同一类, 即正类; 否则, 就将其标为负类.TWSVM就是这样通过超平面来解决分类问题的.

1.2 非线性孪生支持向量机

对于非线性可分的分类问题, TWSVM结合核技术进行处理.基本思路为:首先, 将原始特征空间中的数据映射到高维再生空间中, 使得映射得到的数据样本线性可分; 然后, 在高维空间中建立TWSVM的两个超平面.用K(x, y)表示核函数, 对于非线性二分类问题, TWSVM构造如下两个基于核函数的超平面:

$ K\left( {{x^T}, {C^T}} \right){u_1} + {b_1} = 0\ 和\ K\left( {{x^T}, {C^T}} \right){u_2} + {b_2} = 0 $

(7)

类似于线性可分的情况, 构造下面的二次规划问题并求解得到两个非平行超平面的法向量和偏移量:

$ \left. \begin{array}{l} ({\rm{TWSVM1}})\ \min \frac{1}{2}||K(A, {C^T}){u_1} + {e_1}{b_1}|{|^2} + {c_1}e_2^T\zeta \\ {\rm{s}}{\rm{.t}}{\rm{. }}\;\;\;\;\;\;\;\;\;\;\; - (K(B, {C^T}){u_1} + {e_2}{b_1}) + \zeta \ge {e_2}, \zeta \ge 0 \end{array} \right\} $

(8)

$ \left. \begin{array}{l} ({\rm{TWSVM2}})\ \min \frac{1}{2}||K(B, {C^T}){u_2} + {e_2}{b_2}|{|^2} + {c_2}e_1^T\eta \\ {\rm{s}}{\rm{.t}}{\rm{.}}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;(K(A, {C^T}){u_2} + {e_1}{b_2}) + \eta \ge {e_1}, \eta \ge 0 \end{array} \right\} $

(9)

其中, 矩阵C代表所有训练样本, 它的每一行即为一个训练样本.

求解公式(8)和公式(9)就得到了TWSVM的两个基于核的超平面.非线性情况下, TWSVM的决策规则仍可归纳为测试样本离哪个超平面近就被归于哪个类.具体的决策函数为

$ Label(x)=\underset{k=1, 2, ..., K}{\mathop{\arg \min }}\, \left( {K(x, {{C}^{T}}){{u}_{k}}+{{b}_{k}}}/{\sqrt{u_{k}^{T}K(C, {{C}^{T}}){{u}_{k}}}}\; \right) $

(10)

2 多分类孪生支持向量机的研究进展

算法TWSVM最初是为解决二分类问题而提出来的, 因此需要结合额外的多分类扩展策略才能用于多分类问题.相比二分类问题, 多分类问题往往包含更多的数据, 不同类别的数据样本之间的分布情况也更加复杂.因此, MTWSVMs是TWSVMs研究中的一个难点.本节对MTWSVMs作一个系统的回顾.除非特别说明, 以下都考虑n维空间Rⁿ中的一个K分类问题.记训练数据集为T={(x₁, y₁), (x₂, y₂), (x₃, y₃), …, (x_m, y_m)}, 其中, x_i∈Rⁿ表示输入, 即训练样本数据; y_i∈{1, 2, 3, …, K}表示输出, 即样本标签.为表述方便, 用m_k表示第k类所包含样本的个数, 用矩阵A_k表示第k类训练数据, 并定义B_k=T/A_k, 即, B_k表示除第k类样本以外的所有训练样本.

2.1 基于“一对多”策略的多分类孪生支持向量机 2.1.1 一对多孪生支持向量机的基本数学模型

“一对多(one-versus-all, 简称OVA)”策略是最早被用于将二分类TWSVM扩展为MTWSVM的方法^{[28, 29]}.对于K分类问题, 由标准TWSVM结合OVA策略得到的一对多孪生支持向量机(one-versus-all twin support vector machine, 简称OVA TWSVM)需要为每一个类构造一个超平面, 每一个超平面都对应于一个二次规划问题.在构造对应于第k类样本的超平面时, OVA TWSVM把其中第k类作为一类, 将剩余的K-1类作为一类, 构建一个TWSVM型的QPP并求解得到一个对应于第k类样本的超平面.该方法在每次的训练中都需要全部样本参加.对于线性可分的K分类问题, OVA TWSVM分类器的第k个超平面的构建需要求解如下二次规划问题:

$ \left. \begin{array}{l} \min \frac{1}{2}||{A_k}{w_k} + e_k^{(1)}{b_k}|{|^2} + {c_k}e_k^{(2)T}{\xi _k}\\ {\rm{s}}{\rm{.t}}{\rm{. }}\;({B_k}{w_k} + e_k^{(2)}{b_k}) + {\xi _k} \ge e_k^{(2)}, {\xi _k} \ge 0 \end{array} \right\} $

(11)

其中, 求得的w_k为第k个超平面的法向量, b_k为偏移量, c_k是取值为正数的惩罚参数, e_k⁽¹⁾和e_k⁽²⁾为元素全为1的列向量.

通过求解K个QPPs得到K个超平面, 算法的训练阶段就完成了.在对新样本进行分类时, 需要计算新样本到OVA TWSVM的各个超平面的距离, 未知样本的类别就是所有超平面中与该样本离得最近的超平面所对应的那一类.亦即OVA TWSVM的决策函数为

$ Label(x)=\underset{k=1, 2, ..., K}{\mathop{\arg \min }}\, \left( {\left| {{x}^{T}}{{w}_{k}}+{{b}_{k}} \right|}/{\sqrt{w_{k}^{T}{{w}_{k}}}}\; \right) $

(12)

对于非线性分类问题, 需要先使用核技术, 即, 将数据点映射到高维空间, 然后在高维空间中建立OVA TWSVM.此时, OVA TWSVM的第k个超平面通过求解如下最优化问题而得到:

$ \left. \begin{align} &\min \frac{1}{2}||K({{A}_{k}}, {{C}^{T}}){{u}_{k}}+e_{k}^{(1)}{{b}_{k}}|{{|}^{2}}+{{c}_{k}}e_{k}^{(2)T}\xi \\ &{\rm{s}\rm{.t}\rm{. }}\ \ (K({{B}_{k}}, {{C}^{T}}){{u}_{k}}+e_{k}^{(2)}{{b}_{k}})+\xi \ge e_{k}^{(2)}, \xi \ge 0 \\ \end{align} \right\} $

(13)

不难得到, 非线性情况下OVA TWSVM的决策函数为

$ Label(x)=\underset{k=1, 2, ..., K}{\mathop{\arg \min }}\, \left( {\left| K({{x}^{T}}, {{C}^{T}}){{u}_{k}}+{{b}_{k}} \right|}/{\sqrt{u_{k}^{T}K({{C}^{T}}, {{C}^{T}}){{u}_{k}}}}\; \right) $

(14)

图 2所示为OVA TWSVM基本思想的一个示意图.图中展示的是用OVA TWSVM解决二维空间中的一个包含3个类的分类问题, 黑色点、深灰色点、浅灰色点分别表示类1、类2和类3的样本.对于该问题, 通过求解公式(13)(k=1, 2, 3)得到了3条直线.这3条直线分别表示OVA TWSVM对应于3个类的超平面.从图中不难发现, 3个超平面的特点是:类1的超平面离类1的样本点近而离类2和类3的样本点则远得多, 其他两个超平面也是离其对应类的样本点近而离其他类的样本点要远.因此, 假设待分类点离类1的超平面很近而离类2和类3的超平面很远, 则将该新样本标为类1.

OVA TWSVM思想简单易懂, 而且容易实现, 因此受到应用领域专家的青睐^[30].

2.1.2 OVA TWSVM的改进算法

OVA TWSVM需要求解K个二次规划问题, 而当训练数据较大时, 常用的求解二次规划问题的方法不但耗时长而且占用内存多.为了加快训练速度, 可以使用一对多多分类最小二乘孪生支持向量机(one-versus-all multi class least squares twin support vector machine, 简称OVA MLSTSVM)^{[31, 32]}.与OVA TWSVM一样, OVA MLSTSVM也是将K分类问题转化为寻找K个超平面的问题; 但不同于OVA TWSVM, 它最终将二次规划问题转化为线性方程组进行求解, 求解线性方程的算法相对要快速便捷, 因此, OVA MLSTSVM比OVA TWSVM要快得多.同时, OVA MLSTSVM的分类准确率总是和OVA TWSVM相近.

在TWSVM基础上得到的二分类方法投影孪生支持向量机(projection twin support vector machine, 简称PTSVM)在复杂交叉数据的处理方面具有优秀的性能.Li等人将PTSVM与OVA策略相结合, 得到了多分类递归投影孪生支持向量机(multiple projection twin support vector machine, 简称Multi-PTSVM)^[33].不同于OVA TWSVM, Multi PTSVM为每一个类寻找最佳投影轴, 使得该类样本投影后尽可能集中, 而其他类样本投影后离本类投影中心尽可能地远.Multi PTSVM继承了PTSVM在处理复杂交叉数据集时高效的优点, 在复杂交叉数据的应用中分类性能优于OVA TWSVM.由于Multi PTSVM需要求解二次规划问题, 使得训练速度有提升空间.为了提升Multi PTSVM的训练速度, Yang等人参考LSTSVM设计得到了多分类最小二乘投影孪生支持向量机(multiple least squares recursive projection twin support vector machine, 简称MLSPTSVM)^[34].MLSPTSVM将Multi PTSVM模型中的不等式约束改为等式约束, 然后将二次规划问题转化为线性方程组.该算法只需求解线性方程组, 在保持分类性能的同时, 具有更快的训练速度.

数据不平衡现象不但在二分类问题中存在, 在多分类问题中更为普遍.在分类问题中, 如果某一类样本数目要明显多于其他类, 则在分类器训练过程中样本数目少的类很难发挥作用, 这会严重影响得到的分类器的性能.为了使OVA LSTSVM更好地处理数据不平衡的多分类问题, Tomar和Agarwal在损失函数中为每一个样本添加了一个与其所属类别的样本数目相关的权重^[35].他们的权重分配基本原则是:为样本数据少的类别赋予较大的权重, 而为样本数目大的类别赋予较小的权重.该算法在一定程度上克服了数据不平衡可能造成的性能损失, 相对于原OVA LSTSVM, 在处理数据不平衡问题时性能有一定的提升.

损失函数对基于TWSVM的分类算法具有决定性影响.Shao等人用加权线性损失替换TWSVM中的Hinge损失, 得到了加权线性损失孪生支持向量机(weighted linear loss twin support vector machine, 简称WLTSVM), 并结合“一对多”思想, 得到了可用于多分类问题的Multiple WLTSVM^[36].Multiple WLTSVM和OVA MLSTSVM都是将分类问题转化为求解线性方程组, 因此, Multiple WLTSVM的训练速度接近OVA MLSTSVM.它们之间的本质区别是, 选用了不同的损失函数来估计错分风险.这也造成两者在几何解释上稍有不同, Multiple WLTSVM与OVA TWSVM一样, 在为某一类构造超平面时都要求其他类的样本尽可能地远离该超平面.而OVA LSTSVM则不同, 它要求其他类样本尽可能均匀地处于离该超平面距离为1的平行超平面的两侧.因此, Multiple WLTSVM的泛化性能更接近OVA TWSVM.

2.1.3 基于“一对多”策略的多分类孪生支持向量机的优缺点

OVA策略原理简单而且容易实现.基于OVA策略的MTWSVMs只需为每个类构造一个超平面, 每类的超平面与该类样本接近.不难发现, 这类多分类算法继承了TWSVM的思想, 是TWSVM的一种自然扩展.这类算法的缺点有:

●   其一, 模型中的每个QPP或者等价的线性方程组的约束条件个数是K-1个类的样本数目, 约束条件较多.而约束的数目越多, 训练速度就越慢.当训练数据为大规模数据时, 这类算法的效率往往较低, 所以这类算法对于样本规模较大的多分类问题不适用;

●   其二, 在训练某一类的超平面时, 该类算法将这个类视为正类, 而将其他K-1个类全部视为负类, 这就造成了数据不平衡现象.如果不对数据不平衡现象进行处理, 则会导致训练得到的分类器性能不佳, 从而影响分类时的准确率, 因此, 需要额外的数据不平衡处理方法;

●   其三, 该类方法性能存在“木桶现象”, 即:如果有一个分类器的性能比较低, 就会严重影响整个分类器的泛化性能;

●   其四, 这类方法存在不可分区域, 即:存在与两个超平面距离相近的区域, 在该区域的样本点难以判别其类别^[26].

2.2 基于“一对一”策略的多分类孪生支持向量机 2.2.1 一对一孪生支持向量机的数学模型

“一对一(one-versus-one, 简称OVO)”策略分类方法最早是由Knerr为多分类SVM而提出来的, 将该策略与标准TWSVM相结合, 得到的一对一孪生支持向量机(one-versus-one twin support vector machine, 简称OVO TWSVM)具有比OVO SVM更好的分类性能^[36].对于K类分类问题, 该算法是在任意两类样本间构建一个二分类TWSVM子分类器, 总共需要构造K(K-1)/2个二分类TWSVM, 也即构造K(K-1)个超平面.OVO TWSVM的每个二分类器的生成只需要用到训练样本中的两类数据, 实现K类分类问题中两类的区分.具体地, 对于线性可分的分类问题, 在训练i, j两类样本间的二分类器时, 需要获取两个超平面:

$ {{x}^{T}}{{w}_{ij}}+{{b}_{ij}}=0\ 和\ {{x}^{T}}{{w}_{ji}}+{{b}_{ji}}=0 $

(15)

为获取以上两个超平面的法向量和偏移, 需要解决如下二次规划问题:

$ \left. \begin{align} &{{\text{min}}} \ \frac{1}{2}||{{A}_{i}}{{w}_{ij}}+e_{ij}^{(1)}{{b}_{ij}}|{{|}^{2}}+\frac{{{c}_{ij}}}{2}e_{ij}^{(2)T}{{\xi }_{ij}} \\ &{\rm{s}\rm{.t}\rm{. }}\ \ ({{A}_{j}}{{w}_{ij}}+e_{ij}^{(2)}{{b}_{ij}})+{{\xi }_{ij}}\ge e_{ij}^{(2)}, {{\xi }_{ij}}\ge 0 \\ \end{align} \right\} $

(16)

$ \left. \begin{align} &{{\text{min}}} \ \frac{1}{2}||{{A}_{j}}{{w}_{ji}}+e_{ij}^{(2)}{{b}_{ji}}|{{|}^{2}}+\frac{{{c}_{ji}}}{2}e_{ij}^{(1)T}{{\xi }_{ji}} \\ &{\rm{s}\rm{.t}\rm{.}}\ \ ({{A}_{i}}{{w}_{ji}}+e_{ij}^{(1)}{{b}_{ji}})+{{\xi }_{ji}}\ge e_{ij}^{(1)}, {{\xi }_{ji}}\ge 0 \\ \end{align} \right\} $

(17)

构造完所有二分类子分类器后, 就可以联合它们进行新样本的类别决策了.OVO TWSVM一般采用“投票法”进行类别的判断.“投票法”将所有类别作为“候选者”, 而每个二分类子分类器都是“选民”.每个“选民”有且仅有一张“选票”, 只能投给一名“候选者”.在决定待分类样本x的归属时, 依次用OVO TWSVM的K(K-1)/2个二分类TWSVM进行判别, 如果i, j两类间的分类函数将新样本x分到i类, 则该子分类器将“票”投给了i类, 第i类的“得票”加1;否则, j类得到该“选票”.当遍历完K(K-1)/2个二分类TWSVM后, 根据“票数”来确定待分类样本x所属的类别.样本x将被分到“票数”最高的那个类.

对于训练数据非线性可分的情况, OVO TWSVM在训练i, j两类样本间的分类器时, 需要解决如下最优化问题:

$ \left. \begin{align} &{\text{min}} \frac{1}{2}||K({{A}_{i}}, {{C}^{T}}){{w}_{ij}}+e_{ij}^{(1)}{{b}_{ij}}|{{|}^{2}}+\frac{{{c}_{ij}}}{2}\xi _{ij}^{T}{{\xi }_{ij}} \\ &{\rm{s}\rm{.t}\rm{.}}\ \ (K({{A}_{j}}, {{C}^{T}}){{w}_{ij}}+e_{ij}^{(2)}{{b}_{ij}})+{{\xi }_{ij}}=e_{ij}^{(2)}, {{\xi }_{ij}}\ge 0 \\ \end{align} \right\} $

(18)

$ \left. \begin{align} &{\text{min}} \frac{1}{2}||K({{A}_{j}}, {{C}^{T}}){{w}_{ji}}+e_{ij}^{(2)}{{b}_{ji}}|{{|}^{2}}+\frac{{{c}_{ji}}}{2}\xi _{ji}^{T}{{\xi }_{ji}} \\ &{\rm{s}\rm{.t}\rm{. }}\ \ (K({{A}_{i}}, {{C}^{T}}){{w}_{ji}}+e_{ij}^{(1)}{{b}_{ji}})+{{\xi }_{ji}}=e_{ij}^{(1)}, {{\xi }_{ji}}\ge 0 \\ \end{align} \right\} $

(19)

构建好OVO TWSVM后, 对新样本进行类别标签预测时, 与线性情况下一样, 一般采用“投票”法.

下面结合图 3说明OVO TWSVM.

图 3所示为使用OVO TWSVM解决二维空间中的三分类问题示意图.取公式(18)和公式(19)的i和j为1和2并求解, 可以得到一个能够对类1和类2进行分类的二分类TWSVM, 即图 3所示的子分类器1.通过类似方法得到子分类器2和子分类器3, 它们共同构成了解决该三分类问题的OVO TWSVM.假设图 3所示空心点是待分类的点, 下面以确定图中空心点的类别为例说明OVO TWSVM的决策过程, 也即“投票法”的使用过程.

●   首先, 使用子分类器1, 计算空心点到子分类器1的两个超平面的距离.因为空心点离子分类器1对应于类1的超平面更近, 因此类1得1票;

●   类似地, 计算空心点到子分类器2的两个超平面的距离.因为空心点离子分类器2对应于类1的超平面更近, 因此类1再得1票;

●   计算空心点到子分类器3的两个超平面的距离.因为空心点离子分类器3对应于类2的超平面更近, 因此类2得1票.

最终, 类1得到2票, 类2得到1票, 类3得到0票.OVO TWSVM将待分类样本归为类1.

2.2.2 OVO TWSVM的改进算法

将最小二乘思想引入OVO TWSVM, 就可以使得求解K(K-1)个二次规划问题转化为求解K(K-1)个线性方程组的问题.Tomar等人在详细分析了几种基于LSTSVM的多分类方法后认为:一对一多分类最小二乘孪生支持向量机(one versus one multi class least squares twin support vector machine, 简称OVO MLSTSVM)具有更好的分类性能, 训练速度快而且分类精度高^[26].类似于LSTSVM, OVO MLSTSVM将OVO TWSVM中的不等式约束改为等式约束, 然后将等式约束代入目标函数, 进而将二次规划问题化为无约束求最小值问题.对无约束求最小值问题的目标函数求导, 就得到了等价的线性方程组, 通过求解方程组, 就能得到原二次规划的解.OVO MLSTSVM的预测阶段与OVO MTWSVM完全一样, 也采用“投票法”.OVO MLSTSVM具有与OVO TWSVM接近的分类精度, 但其训练速度要远快于OVO TWSVM.

2.2.3 基于“一对一”策略的多分类孪生支持向量机的优缺点

基于OVO策略的MTWSVMs及其改进算法的优点是每个子分类器在训练时只需要两个类的训练样本, 因此每个子分类器处理的样本较少, 训练很快就能完成^[37].虽然基于OVO策略的多分类孪生支持向量机及其改进算法需要构造的超平面数目较多, 但当样本规模很大而所含类别数不是特别大时, 相比于OVA MTWSVMs, 整体所需的训练时间依然更少.对于每个子分类器, 训练样本只涉及两类, 两类别之间的样本数目是相对平衡的, 因此往往不需要额外的手段来处理数据不平衡问题就能训练得到性能较好的子分类器, 进而使得整个分类模型有更高的分类准确率.这类多分类算法的缺点是:当训练数据包含的类别数很大时, 需要训练的子分类器个数太多.随着样本类别数K的增加, 训练的子分类器个数按平方倍增加, 这使得整个分类系统变得复杂.此外, 这类方法在决策阶段需要遍历所有子分类器, 因此样本类别数很大时, 分类判决的速度也很慢.另一个问题是, 这类方法存在不可分现象, 即:采用“投票法”进行决策时, 可能存在多个获得票数一样的类别, 随机将样本判为其中一类或者直接判为序号最靠前的一类都会影响了分类的精度.

2.3 基于有向无环图的多分类孪生支持向量机 2.3.1 有向无环图多分类孪生支持向量机的基本思想

DAG TWSVM采用图论中的有向无环图将多个二分类TWSVM组合成多分类器.如果图中每条边都有单一的方向, 并且图中无环, 这样的图就称为有向无环图^[38].对于K类问题, DAG TWSVM采用与OVO TWSVM一样的方式构造K(K-1)/2个二分类TWSVM.不同的是, DAG TWSVM将这些子分类器分布于K层DAG结构中^[39].DAG TWSVM的DAG中顶层只有一个节点, 称为根节点, 第i层含i个节点, 如果1 < i < K这些节点称为内部节点, 则第K层即最底层含K个节点, 称为叶子节点.这些节点由有向边连接, 第j层的第i个节点指向第j+1层的第i个和第i+1个节点.每个内部节点都是一个子分类器, 即一个二分类TWSVM, 叶子节点为最终的分类类别.一个3层的DAG拓扑结构如图 4所示.对测试样本进行分类时, DAG TWSVM不采用“投票法”, 该类方法先将测试样本输入根节点分类器, 根据根节点分类器的输出值, 判定走向左侧或右侧子节点, 再根据下一层内部节点分类器的输出值, 继续选择左侧或者右侧前进, 直至走到某一叶子节点, 就得到了该测试样本的类别^[40].

2.3.2 DAG TWSVM的改进算法

Tomar等人将LSTSVM与DAG相结合, 得到了基于DAG的最小二乘多分类孪生支持向量机(directed acyclic graph multiclass least squares twin support vector machine, 简称DAG MLSTSVM)^[26].该方法的训练和分类过程与DAG MTWSVM类似, 不同的是, 该算法继承了LSTSVM的优点, 即训练过程只需处理线性方程组.最小二乘思想的引入, 在保证分类精度的同时提升了算法的整体运行速度.

Chen等人发现, DAG依然具有树形结构所固有的缺点, 即误差会在向下传递的过程中累积并放大^[41].因此, 应将分类性能好的二分类子分类器尽可能地安排在DAG的上层, 而将误差大的二分类子分类器安排在接近DAG的叶子节点处.考虑到二分类器的性能很大程度上取决于训练数据集不同类别之间可分性的大小, Chen等人参考核参数选择中距离判断的思想设计了基于类内和类间样本间平均距离的数据类可分性评判准则, 并结合该准则设计得到了最优有向无环图孪生支持向量机(optimal directed acyclic graph multiclass twin support vector machine, 简称ODAG TWSVM).ODAG TWSVM提升了分类精度, 但也增加了训练时间开销; 并且随着数据类别的增大, 计算类可分性值的额外开销也会增加, 带来的分类器性能提升也越明显.

在DAG MLSTSVM的基础上, 张谢锴等人引入马氏距离得到了基于马氏距离的多分类孪生支持向量机^[42].该方法利用了马氏距离的全局性提升了算法的泛化能力, 对于数据方差大的数据集, 其分类结果要好于DAG TWSVM.

李侃等人为了对多传感器感应到的目标进行分类, 设计了一种带置信度的最小二乘投影孪生支持向量机, 并结合DAG策略提出了多路有向无环图支持向量机^[43].该算法的每个节点除了输出分类结果以外, 还会输出一个该分类结果的置信度.为了合理安排DAG结构, 该算法使用最小超球体矩对类进行排序, 优先选择平均最小超球体矩大的类别进行训练, 得到上层的子分类器, 以减少累计误差.该算法在多传感器探测目标分类问题的应用中取得了预期的效果.

2.3.3 基于有向无环图的多分类孪生支持向量机的优缺点

基于DAG的MTWSVMs的优点是, 在进行判别时, 不需要对每个分类函数进行计算.对于K类分类问题, 通过对K-1个分类器的判决就可得出一个未知样本所属的类别.与“投票法”相比, 分类需要调用的分类器个数明显减少, 从而提高了分类的速度.此外, DAG TWSVMs不存在拒分区域, 泛化性能更好.该类方法的缺点包括:其一, 该类方法在训练时存在与一对一分类方法同样的缺点, 即, 训练的子分类器个数与样本的类别数有关, 随着类别数K的增加, 分类器个数呈平方倍增加, 使得分类判决的速度太慢; 其二, DAG存在从上层节点到下层节点的“误差累积”现象, 假如在某一节点处发生了错误的判别, 这种错误将会一直累积并在向下传递的过程中被放大, 直到整个判决过程的结束.同时, 当样本类别数目很多时, 得到的累积误差将会更大.判别出错情况发生得越早, 这种累积效应越明显, 对分类性能造成的影响越大.因此, 在分类精度方面, 基于DAG的MTWSVMs分类方法往往不如基于OVO的MTWSVMs分类方法.

2.4 基于“一对一对余”策略的多分类孪生支持向量机 2.4.1 Twin KSVC的数学模型

OVO TWSVM由多个二分类TWSVM组合而成, 决策阶段也是依赖这些二分类TWSVM.OVO TWSVM的子分类器总是将样本划分到两个类的其中一类, 然而当测试样本不属于当前子分类器对应的两个类的任何一类时, 该测试样本可能与该两类差异都很大, 这就可能造成当前子分类器对该测试样本的判决是无意义的, 进而产生随机性“投票”.为了避免这种随机性, Xu等人在KSVC的基础上提出了一种新的多分类孪生支持向量机, 称作Twin KSVC^[44].该方法将训练样本组织为“一对一对余”形式, 即:每个子分类器将样本分为正类、负类, 还有一部分既不属于正类又不属于负类, 称为其余类, 对应的输出为{1, 0, +1}.Twin KSVC的子分类器是在二分类TWSVM基础上修正得到的一种变型.为表述方便, 此处作特殊符号说明, 本节使用A, B分别表示一个类, C表示除A, B外的其余类.Twin KSVC的子分类器的数学模型可表述为如下二次规划:

$ \left. \begin{align} &{\text{min}} \ \frac{1}{2}||A{{w}_{1}}+{{e}_{1}}{{b}_{1}}|{{|}^{2}}+{{c}_{1}}e_{2}^{T}\xi +{{c}_{2}}e_{3}^{T}\eta \\ &{\rm{s}\rm{.t}\rm{. }}\ \ \ -(B{{w}_{1}}+{{e}_{2}}{{b}_{1}})+\xi \ge {{e}_{2}} \\ &\ \ \ \ \ \ \ \ \ -(C{{w}_{1}}+{{e}_{3}}{{b}_{1}})+\eta \ge {{e}_{3}}(1-\varepsilon ) \\ &\ \ \ \ \ \ \ \ \ \ \xi \ge 0{{e}_{2}}, \eta \ge 0{{e}_{3}} \\ \end{align} \right\} $

(20)

$ \left. \begin{align} &{\text{min}} \ \frac{1}{2}||B{{w}_{2}}+{{e}_{2}}{{b}_{2}}|{{|}^{2}}+{{c}_{3}}e_{1}^{T}{{\xi }^{*}}+{{c}_{4}}e_{3}^{T}{{\eta }^{*}} \\ &{\rm{s}\rm{.t}\rm{. }}\ \ (A{{w}_{2}}+{{e}_{1}}{{b}_{2}})+{{\xi }^{*}}\ge {{e}_{1}} \\ &\ \ \ \ \ \ \ \rm{ }(C{{w}_{2}}+{{e}_{3}}{{b}_{2}})+{{\eta }^{*}}\ge {{e}_{3}}(1-\varepsilon ) \\ &\ \ \ \ \ \ \ \ \ {{\xi }^{*}}\ge 0{{e}_{1}}, {{\eta }^{*}}\ge 0{{e}_{3}} \\ \end{align} \right\} $

(21)

Twin KSVC通过求解上面的二次规划问题构造两个超平面, 要求正类和负类离各自的超平面尽可能地近, 而其余的样本离这两个超平面的距离都要至少为1.上面的两个二次规划问题一般通过其对偶问题进行求解.

$ \left. \begin{align} &{\text{max}} -\frac{1}{2}{{\gamma }^{T}}N{{({{H}^{T}}H)}^{-1}}{{N}^{T}}\gamma +e_{4}^{T}\gamma \\ &{\rm{s}\rm{.t}\rm{. }}\ \ 0\le \gamma \le F \\ \end{align} \right\} $

(22)

$ \left. \begin{align} &{\text{max}} -\frac{1}{2}{{\rho }^{T}}P{{({{G}^{T}}G)}^{-1}}{{P}^{T}}\rho +e_{5}^{T}\rho \\ &{\rm{s}\rm{.t}\rm{. }}\ \ 0\le \rho \le {{F}^{*}} \\ \end{align} \right\} $

(23)

其中, F=[c₁e₁; c₂e₃], F^*=[c₃e₁; c₄e₃], e₄=[e₂; e₃(1-ε)], e₅=[e₁; e₃(1-ε)], H=[A, e₁], G=[B, e₂], M=[C, e₃], N=[G, M], P=[H; M].

Twin KSVC也采用“投票法”来确定新样本的最终类别.即:如果子分类器输出为+1, 则对应于正类的类别增加1票; 如果输出为1, 对应于负类的那个类增加1票; 否则, 任何类都不得票.最终, 票数最多的类别即为新样本的所属类别.Xu等人将该算法应用到说话人识别(speaker recognition), 仿真实验结果表明了算法的有效性^[44].

2.4.2 Twin KSVC的改进算法

Twin KSVC子分类器的训练需要全部数据的参与, 因此速度相对慢.Nasiri等人^[45]将最小二乘思想引入到Twin KSVC, 得到了最小二乘Twin KSVC, 缩写为LST KSVC.LST KSVC和Twin KSVC一样, 每个子分类器输出结果可能为{1, 0, +1}.最小二乘思想的引入, 提升了算法的训练速度.LST KSVC将Twin KSVC中不等式约束用等式约束加以替换, 采用二次损失函数估计分类误差, 最终, 通过求解线性方程组就可以解决分类问题.LST KSVC不但具备更快的训练速度, 而且保持了Twin KSVC所具有的高分类准确率.

现实生活中, 获取数据标签不是一个简单的任务, 尤其是现在数据量庞大, 很多情况下都不能获得所有数据点的分类标签信息, 因此, 半监督问题越来越受到关注.Khemchandani和Pal针对半监督多分类问题提出了拉普拉斯多分类孪生支持向量机(multi-category Laplacian least squares twin support vector machine, 简称Lap LST KSVC)^[46].Lap LST KSVC能够在充分利用有标签训练数据的同时, 将无标签数据所包含的流形信息也利用起来, 以提升算法的泛化性能.Lap LST KSVC与Twin KSVC采用相同的“一对一对余”策略, 为了使用无标签数据信息, Lap LST KSVC使用流形正则化项技术发现无标签数据中的流形结构, 将数据量更大的无标签数据应用到分类中, 不仅适用于更多实际情况, 而且提升了算法的性能.由于采用了最小二乘思想, 不论是线性还是非线性情况, Lap LST KSVC的模型都能很容易地转化为一系列线性方程组, 因此, Lap LST KSVC的训练速度也较快.

2.4.3 基于“一对一对余”策略的多分类孪生支持向量机的优缺点

与基于OVO的MTWSVMs相比, 基于“一对一对余”策略的多分类孪生支持向量机的子分类器构造的两个超平面不但满足各个超平面离本类尽可能近而离另一个类尽可能远的要求, 而且充分利用了其他K-2个类的信息, 要求其他K-2类的样本离正负类的超平面都距离至少为1个单位.这类方法采用{1, 0, +1}形式的输出, 避免了OVO策略中可能出现的随机“投票”, 因此, 这类方法的泛化性能更好一些.但是这类方法的子分类器需要求解一个具有K-1类样本数目的约束的二次规划问题, 子分类器比较复杂, 时间复杂度高于OVO TWSVMs.为了提升训练速度, 应该结合最小二乘等加速策略.这类方法同样采用“投票”法进行新样本的分类, 也可以采用类似DAG的决策规则来加快决策速度.

2.5 基于二叉树的多分类孪生支持向量机 2.5.1 二叉树多分类孪生支持向量机的基本思想

基于二叉树的多分类孪生支持向量机(binary tree based twin support vector machine, 简称BT TWSVM)针对基于一对一结构和一对多结构的MTWSVMs中存在的拒分问题而提出, 这类方法先将训练数据中的所有类别划分为两个组, 一组看作正类, 另一组看作负类, 训练得到根节点子分类器; 然后, 每个组又划分为两个更小的组, 训练得到下一层的子分类器.以此继续, 直到划分出最终类别.每次划分后, 两类分类问题的规模是逐级下降的.BT TWSVM的思路如图 5所示, 图中展示的是一个五分类问题的分类二叉树, 每个节点对应一个二分类TWSVM, 根节点的二分类TWSVM是将第1类~第3类的样本一起看作正类样本, 将第4类~第6类的样本看作负类样本进行训练得到的.因此, 如果一个新样本被根节点分为正类, 则该新样本可能是属于第1类~第3类中的一个; 之后, 由根节点的孩子节点继续缩小新样本可能所属类的范围, 直至确定其所属类别.BT TWSVM不存在不可分区域, 分类精度高, 算法复杂度低, 已被应用于钢带表面缺陷识别、彩色图像分类等领域^[47-51].

2.5.2 二叉树多分类孪生支持向量机的改进算法

聂盼盼等人^[50]为了减少BT TWSVM中的误差向下传递和累计, 使用k均值算法先对训练数据集进行聚类, 再使用聚类中心间距离代表类间距离, 类间距离越大的分组方式, 就对应二叉树中越上层的节点, 以此得到合理的二叉树结构.他们将这种方法应用于入侵检测, 得到了很好的效果.

Khemchandan等人将Laplacian TWSVM与二叉树相结合, 得到可以用于半监督多分类的TB Lap TWSVM^[51].其训练过程与BT TWSVM一样, 只是子分类算法选用的是Lap TWSVM而不是TWSVM.TB Lap TWSVM能够将无标签数据的信息利用起来, 以有效处理半监督多分类问题, 具有较低的时间复杂度和较高的分类性能.

谢娟英等人^[52]将孪生支持向量机与偏二叉树相结合, 得到了偏二叉树多分类孪生支持向量机.该方法首先选取类1作为正类, 第2类~第K类作为负类训练, 得到根节点子分类器; 然后, 将类2作为正类, 类3~类K作为负类, 训练得到根节点的子节点.依次继续, 直至训练得到第K-1类和第K类的二分类器.该方法总是选取一个类作为正类, 剩余多个类作为负类, 容易出现数据不平衡现象.谢娟英等人对正负类实施不同的惩罚系数来克服这一缺陷.该算法的缺点是利用偏二叉树来解决多分类问题, 树的层多, 所需训练时间也长, 而利用偏二叉树的优点是实现简单.

李秋林等人提出了一种基于二叉树和超球孪生支持向量机的多分类算法^[53].为了减少累计误差, 该方法使用一种以类样本分布情况、超球体半径或超长方体为依据生成二叉树的方法.为了加快训练速度, 该方法使用坐标轮换法和收缩技术求解超球孪生支持向量机子分类器的规划问题.该算法训练速度较快, 分类精度较高, 适合数据稀疏性较强的多分类问题.

为了得到良好的二叉树结构, Shao等人提出了“最优分离原则”^[54].该原则包含两条:在将众多的类分为两组的过程中, 称分组是满足最优分离原则的, 如果该分组得到两个组的数据的距离在所有可能的分组中是最大的; 称分组满足最优分离原则, 如果该分组得到的两组数据的分类错误率是所有分组中最低的.根据以上原则, Shao等人提出了最优分离树孪生支持向量机(best separating decision tree twin support vector machine, 简称DTTSVM). DTTSVM通过合理的二叉树结构, 可以较好地消除累积误差, 从而得到更好的分类结果.

2.5.3 基于二叉树的多分类孪生支持向量机的优缺点

基于决策二叉树的MTWSVMs采用广为人知的二叉树, 使得算法具有简单的结构, 容易实现.

这类MTWSVMs的一个重要特点和优点是解决了一对多和一对一方法中存在的不可分问题, 从而算法本身更加稳健.对于K类分类问题, 该方法只需要训练K-1个二分类器, 并且随着二叉树层次的增加, 训练的规模不断缩小, 训练的时间也随之减少, 训练阶段时间复杂度较低; 分类判决时不一定需要对每个分类器进行计算, 从而减少了分类判决所需时间.缺点在于:决策二叉树的结构是影响分类器性能的关键因素, 结构不同的决策树, 其训练速度和分类能力都有较大差异.因此, 该方法的关键是构建合理的树结构.当树结构趋于满二叉树时, 这种分类方法的训练和分类速度达到最佳.树形结构必然存在累计误差, 因此越是上层的节点越应该合理设计, 从而减少累计误差.

2.6 基于“多对一”策略的多分类孪生支持向量机 2.6.1 多生支持向量机

Yang人^[55]将TWSVM与“多对一(all-versus-one, 简称AVO)”策略相结合, 提出了多生支持向量机(multiple birth support vector machine, 简称MBSVM).MBSVM因其较低的算法复杂度而受到学者关注.MBSVM每次仅选取一个类作为负类, 剩下的类都当作正类构建一个TWSVM型的QPP.MBSVM的每个QPP的约束条件只与一类样本有关, 因此, MBSVM的二次规划模型中, 约束条件较“一对多”策略实现的MTWSVMs要少得多. MBSVM共需求解K个二次规划问题以获得K个分类超平面.对于线性情况, MBSVM的求解过程即在Rⁿ空间中寻找到K个非平行的超平面, 这K个超平面通过求解下面的一组二次规划得到:

$ \left. \begin{align} &\underset{{{w}_{k}}, {{b}_{k}}, {{\xi }_{k}}}{\mathop{\min }}\, \, \frac{1}{2}||{{B}_{k}}{{w}_{k}}+{{e}_{k1}}{{b}_{k}}|{{|}^{2}}+{{c}_{k}}e_{k2}^{T}{{\xi }_{k}} \\ &{\rm{s}\rm{.}\, \rm{t}\rm{.}}\ \ \ ({{A}_{k}}{{w}_{k}}+{{e}_{k2}}{{b}_{k}})+{{\xi }_{k}}\ge {{e}_{k2}} \\ &\ \ \ \ \ \ \ \ {{\xi }_{k}}\ge 0 \\ &\ \ \ \ \ \ \ \ \ k=1, 2, ..., K \\ \end{align} \right\} $

(24)

当需要对新样本进行分类时, 只需将该样本代入到已经确定好的K个超平面表达式, 新样本将被分入距离最远的超平面对应的类, 即决策函数为

$ Label(x)==\underset{j=1,2,...,K}{\mathop{\arg \max }}\,\left( {({{x}^{T}}{{w}_{j}}+{{b}_{j}})}/{\sqrt{w_{j}^{T}{{w}_{j}}}}\; \right) $

(25)

注意, MBSVM采用的是“max”的决策方式, 这与TWSVM是完全不同的.

2.6.2 其他基于“多对一”策略的多分类孪生支持向量机

MBSVM的二次规划问题通过松弛迭代法求解, 得到的解往往精度不高.Ju等人提出的非平行超平面多分类支持向量机(nonparallel hyperplanes support vector machine for multi class clasification, 简称NHCMC)继承了MBSVM的思想, 即, 采用“多对一”结构和“max”的决策方式^[56].不同于MBSVM, NHCMC的模型可以通过序列最小优化算法求解, 并且不必区分线性和非线性情况, 核方法可以直接应用.NHCMC算法与MBSVM一样, 在样本类别多时, 算法复杂度方面具有优势.值得注意的是:NHCMC的二次规划问题与SVM的模型一样可以使用最小序列优化算法, 因此, NHCMC训练速度快, 最小序列优化算法求解的结果精度较高, 从而, NHCMC算法较MBSVM稳定并且往往具有更好的分类准确率.该算法的不足在于, 其理论依据有待进一步充实.

Xu等人将孪生超球支持向量机与“多对一”多分类策略相结合, 得到了孪生超球多分类支持向量机(twin hyper sphere support vector machine, 简称THKSVM))^[57].THSKVM在训练过程中不需要进行矩阵的求逆操作, 因此训练速度快, 可以应用于大规模分类问题.此外, THKSVM为每个类构造一个超球而不是超平面, 能够更准确地获取和利用训练数据的信息, 获取更好的分类面.

文献[58]提出了一种基于1范数正则项的孪生支持向量机, 并使用多对一策略将该算法推广至多分类.该多分类方法通过求解线性方程组以解决分类问题, 并且不需要进行大规模的矩阵求逆运算, 因此训练速度快.缺点是分类精度一般, 泛化能力有待提高.

针对MBSVM在处理数据存在交叉的多分类问题时效果不佳的情况, 文献[59, 60]在多生支持向量机中添加一个修正项, 使得生成的超平面与对应类的样本之间距离尽量大而离其他类样本尽量远的同时, 每个该类样本与超平面之间的距离都尽量相等.在对新样本进行预测阶段, 不同于MBSVM将待分类点简单地分到离该点最远的超平面所对应的类, 该算法首先判断带分类点离各分类超平面的距离是否落入对应的一个区间内, 在满足此条件的分类超平面之间进行比较, 最后确定分类结果.与MBSM相比, 改进算法在处理数据存在交叉的多分类问题时效果更佳.

2.6.3 基于“多对一”策略的多分类孪生支持向量机的优缺点

基于AVO的MTWSVMs每次仅选取一个类作为负类, 剩下的类都当作正类来构建超平面, 得到的超平面离一个类远, 而尽可能靠近其余类的样本.这样做的优点是时间复杂度低, 约为O(m³/K²).基于OVA策略的MTWSVMs的时间复杂度为O(m³K), 因此类别数目K较大时, 基于AVO方法的MTWSVMs在训练速度方面具有明显优势.此外, 该类方法和OVA MTWSVMs一样, 具有思想简单、容易实现的优点.

这类方法的缺点是分类精度不够高, 其原因有两点.

●   其一是这种方法的约束条件少, 因此容易陷入局部最优, 应采取全局性更好的二次规划求解算法;

●   其二是被作为正类的那些类之间可能相距较远, 很难使得超平面离它们同时都近.

综上所述, 基于AVO方法的MTWSVMs适合分类类别K较大、但精度要求不太高的应用情景.

2.7 方法对比

本节的前6个小节已经对6类MTWSVMs的原理、数学模型、研究发展作了详细介绍, 也简要分析了各类算法的优缺点.为了更加清晰地展现各类方法之间的优势和劣势, 本小节对MTWSVMs进行更深入的对比分析.

首先对比分析基于OVO的MTWSVMs和基于OVA的MTWSVMs, 这两种是最早被提出的MTWSVMs.这两种方法相比, 基于OVO的MTWSVMs的优势是不会导致数据不平衡现象, 分类准确率更高; 而基于OVA的MTWSVMs由于每一步训练将多个类看作一个类, 因此常伴随数据不平衡现象.与此同时, 基于OVA的MTWSVMs还忽略了被看作一个类的那些类别之间的差别, 因此分类准确率往往不高.但是OVA MTWSVMs算法的思想简单明了, 容易实现, 因此在所要处理的问题不是非常复杂的时候, 领域专家往往还是会选择应用OVA MTWSVMs.在训练速度上, OVO MTWSVMs在训练集较大时训练速度要明显快于OVA MTWSVMs.分类问题规模小时, 建议选择使用OVA MTWSVMs.

DAG MTWSVMs是为了提升OVO MTWSVMs的决策速度而提出来的, 并且解决了OVO MTWSVMs存在的拒分区域问题.但在决定整个算法执行速度的训练速度上, DAG MTWSVMs与OVO MTWSVMs是相同的.此外, 由于DAG MTWSVMs的DAG是一个层次结构, 因此, DAG MTWSVMs会存在累计误差, 对算法性能造成一定的影响.总体上说, DAG MTWSVMs和OVO MTWSVMs不论是在算法时间复杂度上还是在分类准确率方面都表现相当.因为DAG MTWSVMs的决策时间相对较短, 因此, 当待分类样本数量远多于训练样本时, 应该选用DAG MTWSVMs代替OVO MTWSVMs.

基于二叉树的MTWSVMs解决了OVA MTWSVMs和OVO MTWSVMs都存在的拒分问题.与OVA MTWSVMs相比, 这类方法并非每步训练都需要使用所有训练数据, 基于二叉树的MTWSVMs随着训练步骤的增加和二叉树层次的增加, 训练的规模不断下降, 总体的训练速度快于OVA MTWSVMs.但是基于决策二叉树的MTWSVMs的实现较为复杂, 因此, 当所处理的问题并不复杂时, 直接选用OVA MTWSVMs更好.与OVO MTWSVMs相比, 基于二叉树的MTWSVMs仅需K-1个子分类器, 加之使用二叉树结构组织其子分类器, 因此整个分类器结构更加简洁、稳定.与DAG MTWSVMs相比, 基于决策二叉树的MTWSVMs的累计误差现象更加明显, 因此, 在构造二叉树结构的过程中要更加注重结构的优化, 而DAG MTWSVMs的累计误差相对要少得多.在训练数据集给定之后, DAG MTWSVMs的层次是确定的, 而基于决策二叉树的MTWSVMs的层数不够确定, 如果构造成偏二叉树, 则会增加算法的训练时间.

基于“一对一对余”策略的多分类孪生支持向量机的每个子分类器以{+1, 0, -1}的形式标注样本, 这使得每个子分类器在处理两类样本的同时识别其他类的样本, 避免了OVO策略中对其他类样本的随机“投票”.因此, 基于“一对一对余”策略的多分类孪生支持向量机在保持了OVO MTWSVMs的优点的同时获得了更加优秀的鲁棒性.但是, 基于“一对一对余”策略的多分类孪生支持向量机为识别其他类的样本需要处理两类约束条件, 模型求解难度大于OVO MTWSVMs.与基于二叉树的MTWSVMs相比, 基于“一对一对余”策略的多分类孪生支持向量机的优势是不存在累计误差, 不需要结构优化.但是, 基于“一对一对余”策略的多分类孪生支持向量机依然存在拒分区域, 而且训练速度往往比基于二叉树的MTWSVMs要慢.

与OVO MTWSVMs, DAG MTWSVMs以及二叉树MTWSVMs相比, 基于AVO的MTWSVMs和OVA MTWSVMs一样具有原理易懂、实现简单的优点.同时, 和OVA MTWSVMs一样, 基于AVO的MTWSVMs训练过程中也将多类看作一类, 从而出现数据不平衡问题.与OVA MTWSVMs相比, 基于AVO的MTWSVMs模型中约束条件更少, 求解更加简单.训练速度上, 基于AVO的MTWSVMs总是快于基于OVA的MTWSVMs.基于AVO的MTWSVMs与基于OVO的MTWSVMs相比具有的优势是所需训练的子分类器个数少.因此, 当分类问题包含许多个类别时, 基于AVO的MTWSVMs总体结构依然简单, 而OVO MTWSVMs将会是一个包含许多子分类器的复杂分类系统.当所需处理的问题包含的类别很大时, 基于AVO的MTWSVMs的时间复杂度要低于其他5类方法.因此, AVO MTWSVMs适合包含类别多的分类问题.但是, 基于AVO的MTWSVMs的分类准确率总体上要比其他5类方法要差.

3 算法实验比较

本节对各种算法进行数值实验对比.实验选取各类多分类孪生支持向量机中具有代表性的算法进行比较.为了保证实验的可靠性, 本文均采用十交叉验证, 即:将数据随机均分为10份, 依次选取1份作为测试数据, 其余作为训练数据, 对每个数据集, 各种算法都要进行10次训练和测试.运行环境为2G内存, CORE 2处理器, 2.19GHz主频, Windows7操作系统.全部算法都使用Matlab2012a实现和运行.本文选用UCI机器学习数据库中几个常用的数据集对算法进行测试, 数据集的具体信息见表 1.采用RBF核作为核函数, 因为大量研究表明, RBF核函数具有比其他函数更佳的性能.表中分类精度为十交叉验证所得的平均结果.参数选择都使用网格搜索法, 选取范围为-6~6, 步长为0.5.训练数据在用于训练分类器前已进行归一化.表 2和表 3中, ACC表示对应算法的平均分类准确率, STD表示10次实验所得分类准确率的标准差.

从表 2可以看出:

●   线性情况下, 在UCI数据集上, OVO TWSVM总体分类精度是最高的, 在5个数据集上获得了最佳结果.此外, OVO TWSVM仅在一个数据集Iris上的分类准确率是最低的.但是OVO TWSVM在Vowel和Optdigits这两个样本类数超过10的数据集上表现不佳;

●   其次, ODAG TWSVM的表现也不错, 在数据集Landat上的分类精度高于其他算法, 在3个数据集上取得了最佳分类结果, 其分类结果接近OVO TWSVM, 在Glass和Balance上分类结果略好于OVO TWSVM;

●   相对地, MBSVM分类结果比较不够理想, 在3个数据上的分类精度是所有方法中最差的;

●   BT TWSVM与Twin KSVC的分类精度相当, 都在一个数据集上取得了最佳结果.

从表 3可以看出:

●   在使用RBF核的情况下, 在UCI数据集上, OVO TWSVM总体分类精度依然是最好的, 在4个数据集上获得了最佳结果, 特别是在数据集DNA上, OVO TWSVM的分类精度明显高于其他算法.此外, OVO TWSVM在所有数据集上的分类精度都不是最低的;

●   MBSVM相对分类结果比较差, 在4个数据上的分类精度是所有方法中最差的, 但也在一个数据上取得了最佳精度;

●   BT TWSVM和Twin KSVC都在两个数据集上取得了最佳结果, 在一个数据集上取得了最差结果;

●   ODAG TWSVM虽然在任何数据集上都没有取得最佳结果, 但其分类结果都接近OVO TWSVM, 在Glass和Balance上的分类结果好于OVO TWSVM.

结合以上分析可得:总体而言, OVO TWSVM和ODAG TWSVM分类性能是最佳的, 而MBSVM的分类精度有待提升.

为了验证各种算法的复杂度, 为实际应用中选择合适的多分类孪生支持向量机提供更为全面的参考, 选取Vowel和Pendigits两个数据集作进一步的实验分析.多分类孪生支持向量机的训练时间主要与分类问题的训练样本数和样本类别数有关, 为了测试各类多分类孪生支持向量机的时间复杂度与分类问题的训练样本数的关系, 分别从Pendigits的各个类别中随机抽取10%、20%、30%、40%、50%、60%、70%、80%、90%和全部样本组成类别数相同但样本数目均匀递增的10个数据集.图 6是各种算法在这10个数据集上的训练时间的折线图.实验所采用的是线性核, 因为线性核的计算占用时间少, 可以使实验中采集到的训练时间数据更加真实地反映各类多分类孪生支持向量机模型本身的时间复杂度.从图 6中可以清晰地看出, 随着样本数的增加, 各类多分类孪生支持向量机训练时间的变化趋势.OVA TWSVM和Twin KSVC的训练时间随样本数的增加而增加的速度最快, 而MBSVM则最慢.结合表 2和表 3中分类准确率的测试结果可以看出:实际应用中, 如果对分类准确率的要求并不苛刻而训练样本数量又较大, 宜采用MBSVM.如果希望尽可能地提升分类结果, 则可以选用OVO TWSVM, 因为OVO TWSVM的分类准确率总体是最高的, 并且时间复杂度也不是很高.

接着, 用包含11个类的Vowel测试各种算法训练时间随样本数目增加的变化情况以分析各算法时间复杂度随样本类别数的变化情况.取Vowel中的第1类~第4类作为第1类, 第5类~第8类作为第2类, 第9类~第11类作为第3类构成一个三分类数据集, 取Vowel中的第1类~第3类作为第1类, 第4类~第6类作为第2类, 第7类~第9类作为第3类, 第10类~第11类作为第4类构成一个四分类数据集, 按照类似做法得到五分类数据集、六分类数据集、七分类数据集、八分类数据集、九分类数据集、十分类数据集和十一分类数据集.这样得到的9个数据集包含的数据样本个数是一样的而样本类别数不同.图 7是各种算法在这10个数据集上的训练时间的折线图.

可以看出:当类别数为3和4时, 6种算法的训练速度没有很大的差别.随着训练样本类别数的增加, MBSVM的训练时间略有减少.OVA TWSVM和Twin KSVC的训练时间近似于线性增长.OVO TWSVM和Twin KSVC训练时间的增加也并不明显.结合表 2和表 3中分类准确率的测试结果可以看出:实际应用中, 如果所面临的问题包含类别数较多而分类准确率要求不是很高, 则采用MBSVM是最为快速的.若要兼顾速度和分类结果, 宜选用OVO TWSVM、ODAG TWSVM或BT TWSVM.仅在问题规模小、包含的类别数少时, 建议使用OVA TWSVM和Twin KSVC.

4 总结

将TWSVM推广到多分类是TWSVM研究中的一个重要内容, 本文对近年来MTWSVMs的研究进展进行了一个总结.已有的研究主要可分为基于“一对一”策略、“一对多”策略、DAG结构、决策二叉树结构、“一对一对余”策略和“多对一”这6种策略的MTWSVMs.各种策略有着各自的优缺点.本文以多分类TWSVM采取的策略, 也即组织子分类器的方式为依据, 分门别类地回顾了已有的MTWSVMs算法, 分析了各类算法的优缺点, 通过数值实验, 对比了各类算法中代表性的算法.MTWSVMs的研究虽然已经取得了不少成果, 但仍然存在许多问题需要继续完善.本文认为, 还需在以下几个研究方向上加以完善和改进.

(1) 理论研究.MTWSVMs的研究大多数是实验驱动的, 理论基础不够深厚.完善MTWSVMs的基础理论系统是MTWSVMs发展的基石, 因此特别值得关注;

(2) 研究MTWSVMs的并行性.现在是大数据时代, 对于比较大的数据, 几乎所有MTWSVMs的处理效率都明显不足.并行化是快速解决大型且复杂计算问题的重要方法.对MTWSVMs进行并行化, 也许是未来提升MTWSVMs处理大数据能力和效率的发展方向.MTWSVMs是否适合并行化计算、如何合理分割多计算过程以便实现并行化, 都是未解决的问题;

(3) 拓宽MTWSVMs的应用领域.目前, MTWSVMs的应用仍有限, 大部分优秀的MTWSVMs算法都仍处于理论研究阶段.为了推动多分类TWSVMs的进一步发展, 需要领域专家结合专业知识拓宽这些算法的应用领域.只有实际的应用价值, 才能让MTWSVMs得到进一步的发展.