一种改进的偏二叉树孪生支持向量机算法及其应用

姜佳辉,包永强2,邵 琪

(1.南京工程学院 电力工程学院，南京 211167; 2.南京工程学院 信息与通信工程学院，南京 211167)

0 引言

支持向量机(Support Vector Machines,SVM)是Vapnik等提出的针对于解决分类及回归问题的统计学习理论[1]。与一些传统的机器学习方法不同，SVM较好地解决了诸如求取局部极小值、模型选择与过学习问题等。但是，SVM仍存在着一些问题，如算法复杂度高，耗时长等。孪生支持向量机(Twin Support Vector Machines,TWSVM)是一种基于SVM上发展而来的新算法，其在保持经典支持向量机原有优势的基础上，运算速度明显快于后者。孪生支持向量机通过求解两个二次规划问题构造两个非平行超平面，由于每个二次规划问题的约束条件数目为经典支持向量机的一半，从而理论上其训练速度约为经典支持向量机的4倍[2]。

传统SVM和TWSVM最初都是为了解决二分类问题而提出的，而非直接针对于多分类问题。然而，现实中绝大多数问题通常是多分类问题，因此，针对多分类TWSVM的研究具有重要的现实意义。目前，国内外学者在多分类TWSVM的研究方面也已取得了一些进展。“一对多(one-versus-all,OVA)”作为一种最早被用于将二分类问题扩展为多分类的策略[3]，其核心思想是通过求解K个二次规划问题(quadratic programming problem,QPP)得到K个超平面，算法具有简单易实现的优点，但会造成数据的不平衡的现象，并存在着不可分区域；随后Kerr等人提出了“一对一(one-versus-one,OVO)”策略[4]，对于K类分类问题，该算法在任意两类样本之间构造一个基于TWSVM的二分类器，需构造的二分类器总数为K(K-1)/2个。由于该算法在每个子分类器训练时仅需用到两个类的训练样本，因此较好地解决了分类过程中存在的数据不平衡问题，且加快了训练速度；但由于其采用“投票法”作为决策策略，从而会导致存在获得相同票数的类别，将影响最终的分类准确度；基于二叉树的多分类孪生支持向量机(binary tree based twin support vector machine,BT-TWSVM)针对上述两种策略中可能存在的问题而提出，对于K类分类问题，该方法先将所有类别划分为两个子类，训练得到根节点子分类器；再进一步将子类划分为两个更小的类，训练得到下一层分类器，以此类推，直到所有节点都只包含一个单独类为止。BT-TWSVM分类精度高、算法复杂度低、且不存在不可分区域，因此已被广泛应用于机械设备故障识别、图像分类等领域[5-6]。

采用二叉树进行的优点在于不存在不可分区域，且训练分类器时所需的训练样本较少，训练时长较少，分类效率较高。缺点在于，二叉树分类结构存在“误差累积”现象，即若在某个节点上发生误分类，则这种错误会延续下去，该节点的后续节点分类将失去意义。因此，如何构建出一个较好的二叉树结构，已成为当前学者们研究的一个热点。文献[7]通过计算各类别间的最短距离，以其进一步计算出各样本的类间平均距离从而提出了一种新的二叉树生成算法，但是该算法并未考虑到类内样本的分布；文献[8]定义了一种基于类内样本分布的可分性测度，并将其引入二叉树SVM的构建中，但其仅关注类内样本的分布情况，忽略了类间样本的联系。基于此，本文提出了一种改进的偏二叉树TWSVM算法，定义了一种融合了类间距离和类内分布两种可分性测度指标的混合分离性测度β，用以最大限度地克服误差累积现象，以此来确定最优分类二叉树TWSVM结构。以风电机组齿轮箱作为诊断对象，提取了其一些典型故障下振动信号的时频域特征，并利用本文所述的改进二叉树TWSVM算法实现对齿轮箱常见多类故障的诊断。

1 孪生支持向量机

对于任一非线性二分类问题，孪生支持向量机可归结为求解如下两个二次规划问题：

s.t. -(K(B,C′)w(1)+e2b(1)) +q≥e2

q≥0

(1)

s.t. (K(B,C′)w(2)+e2b(2))+q≥e1

q≥0

(2)

其中:A、B分别表示两类待分类样本矩阵，K(·)表示核函数，e1和e2为相应维数的单位向量，c1，c2为惩罚系数，C=[AB]T，ω和b分别表示所得最优超平面的法向量和偏置，q为松弛变量。通过拉格朗日求解法求解式(1)、(2)，最终得到如下两个超平面K(xT,CT)w(1)+b(1)=0，K(xT,CT)w(2)+b(2)=0。对于一个新的测试样本，其距离哪个超平面近就会被归为对应类，即决策函数为[9-10]：

(3)

2 改进的偏二叉树TWSVM多分类算法

2.1 偏二叉树TWSVM

偏二叉树孪生支持向量机(Partial Binary Tree Twin Support Vector Machine,PBT-TWSVM)的基本思想是：通过构造一个偏二叉树结构将一个含有k个类别的分类问题转化为k-1个两类分类问题。在处理k分类问题时，二叉树孪生支持向量机只需生成k-1个TWSVM分类器，小于基于OVO、OVA策略所需构造的多分类器数目(k(k-1)/2、k)[11]。同时，对于位于每个节点的TWSVM二分类器来说，所参与训练的样本数据数量会随着级数的增加而减少，这使得偏二叉树孪生支持向量机具有更快快的训练速度和测试速度。由于二叉树结构存在着“误差累积”现象，因此为了提高二叉树整体的性能，在生成偏二叉树结构时须考虑采取更为合理的策略，即越是根节点及靠近根节点的上层节点，越应当区分出分离性较优的类。

2.2 混合分离性测度

(4)

由核函数理论知K(xm,xn)=φ(xm)·φ(xn)，进一步计算上式，得:

m,n=1,2,…,k,m≠n

(5)

则类间样本距离计算式如下：

(6)

文献[12]指出，类内样本距离D反映了类内样本的分布，D值越大，则类内样本分布越广，应当率先被分离出来；类间样本距离D’反映了不同类的可分离程度，该值越大，则类间可分性程度越好，越当被率先分离出来。虽然类内样本距离和类间样本距离是针对可分性度量的两种不同评价标准，但两者对于类可分性的影响程度，及其是否存在着某种内在联系，目前还未有相关理论分析。基于此，本文通过引入权值思想将两者结合，定义了一种类的混合分离性测度β，对于任意两类i,j，其β的定义如下式所示：

(7)

式中，W为权值系数，0≤W≤1。式(7)反映了两种评价标准对类别可分性共同影响又相互制约的关系。由于本文所述算法中二叉树层次结构的确定以β为标准，显然不同的W的取值将同时改变β，继而改变二叉树的层次结构，因此确定W的具体取值是影响二叉树性能，也是影响最终分类精度的关键。对于W值的确定，本文引入粒子群优化算法(Particle Swarm Optimization,PSO)，文献[13]指出，TWSVM中的惩罚系数c1，c2和高斯核函数中的参数g同样对最终的分类精度有着较大的影响，因此为了使分类器性能达到最优，最终确定算法中共有4个待优化参数c1，c2，g，W，故在搜索空间中第i个粒子的位置表示为一个四维的向量xi={ci1,ci2,gi,Wi}。同时，算法确定以K重交叉验证分类准确率Fitness作为适应度函数。其具体计算步骤如下：

1)设共有n类样本。初始化参数c1，c2，g及W，载入样本集其对应标签集，根据K折交叉验证的方法将各类样本集分别对应划分为训练集和测试集；

2)按照式(5)、(6)、(7)分别计算各类训练样本两两之间的混合分离性测度值，并将所得值按从小到大进行排列。构造第一个二叉树节点时，将β值最小对应的两类训练样本(记为C1、C2)作为正负类样本进行训练，得到第n-1层叶子节点，然后合并该层节点的两类样本作为一类，分别计算其与其余n-2类样本的混合分离性测度值，取值最小的一类(记为C3)再与其作为正负样本进行训练，依此类推。构造二叉树节点的问题即可归结为如式(1)、(2)所示求取TWSVM两个非平行超平面的问题。重复上述过程，直至得到根节点，二叉树建立完成，由此可以保证位于根节点的TWSVM分类器能够将可分性最好的一类率先分离出来。具体二叉树构建过程示意图如图1所示，按照由下至上的顺序构建整个PBT-TWSVM分类器；

3)将测试样本输入至图1所示二叉树中进行判断，待分类样本从根节点进入，依次由上至下经过各分类器，各TWSVM分类器按照式(3)的规则进行决策，得出样本最终所属类别，继而得出分类准确率；

4)分别更换训练集和测试集，重复步骤2)、3)共K次，取K次所得分类准确率的平均值作为最终适应度函数Fitness。

图1 PBT-TWSVM示意图

2.3 本文算法描述

结合上面的定义分析，本文基于PSO改进的PBT-TWSVM算法具体流程如图2所示。

图2 本文算法流程图

其中，适应度值的计算即按照2.2节中所述相关步骤进行。与传统多分类SVM算法相比，本文所提出的PBT-TWSVM算法的优势在于：(1)二叉树TWSVM对于测试样本无需经过所有的二值分类器，只要识别出类别即可停止运算，从而节省了测试时间；(2)利用偏二叉树结构进行分类，其克服了“一对多”和“一对一”方法中存在不可分区域的问题，训练时只需构造n-1个TWSVM二分类器，且训练样本规模随二叉树层数的增加而减少，减小了训练时间；(3)另外利用混合分离性测度作为偏二叉树的生成算法，其综合考虑了样本类内和类间距离对于类可分性的影响与否及具体影响程度，将越容易区分的类尽可能地优先分离出来，能够最大程度上地克服二叉树中的“误差累积”现象，使算法具有更强的泛化能力，从而获得更优的分类性能。

2.4 仿真分析

为了验证本文提出的基于混合分离性测度的PBT-TWSVM算法在非线性多分类问题中的性能，采用UCI标准数据库中的Auto-mpg、Balance两个标准数据集作为实验数据，仿真实验均在PC机上(内存为256 MB、CPU为800 MHz)基于Matlab R2015a环境实现。表1为各数据集的样本个数、维数及类别数说明。

表1 测试数据集信息

将如下各多分类算法：(1)传统支持向量机(SVM)；(2)一对一孪生支持向量机(OVO TWSVM)；(3)仅考虑类间距离时的偏二叉树孪生支持向量机(即式(7)中W=0时)；(4)本文算法，对上述算法分别进行测试并将分类的结果进行统计，对比结果如表2所示(其中测试时长单位为秒)。对于前三种算法，其对应SVM核函数亦均采用高斯核函数，并且对应参数均采用PSO优化，并均以五折交叉验证的分类准确率作为对应适应度函数。

表2 不同算法对测试数据分类结果

从表2的结果可以看出，首先相较于传统SVM，另外三种基于TWSVM的多分类算法在运算速率上均有显著提高，且两种基于偏二叉树TWSVM的算法相较于一对一TWSVM在运算时长上也具有明显的优势；其次，针对数据集Auto-mpg，上述四种方法无论是运用哪种它们的分测试精度都相差无几，而对于数据集Balance，分类准确率则有了大幅地提高，这进一步反映了偏二叉树TWSVM算法相较于传统SVM及1-v-1TWSVM更适合于数据量大、特征数多样本的处理；同时可以发现，对于样本规模较大的Balance数据集，应用本文的基于类混合分离性测度的改进PBT-TWSVM算法相较于仅考虑类间样本距离时的PBT-TWSVM算法在分类准确率上有了显著提高，达4.1个百分点，这说明了混合考虑类内和类间距离构建的二叉树分类器具有更优的分类性能。

3 实验分析

3.1 平台搭建

为进一步验证本文所提出算法在齿轮箱故障模式识别方面的有效性，在实验室搭建了风电机组齿轮箱故障模拟试验台来作为实际验证。其示意图如图3所示。实验中，电机模拟风轮转矩输入，其转速通过连接变频器控制，以模拟风轮转速的时变特性。输入端连接驱动电机和联轴器，驱动电机通过二级齿轮箱传动后连接负载电机。在试验台上分别人为模拟了A、行星轮磨损、B、行星轮点蚀、C、行星轮断齿、D、滚动轴承内圈裂纹、E、轴承保持架损坏五种不同工况，分别采集了各故障情况下的原始振动信号。实验中，调节变频器控制齿轮转速为1000 r/min，系统采样频率设置为10 kHz，每组样本均为连续采样。

图3 风电机组齿轮箱故障模拟试验台

采集到的各工况下的原始振动信号如图4所示。

图4 齿轮箱各工况下原始振动信号

3.2 齿轮箱振动信号特征提取

从图4中的齿轮箱原始时域信号中难以提取其故障特征，因此本文中进一步采用了时频域联合特征提取的方法来提取有效的特征。提取出每种工况下原始样本各100组，并采用文献[14]中所述方法，分别提取信号的小波包能量特征、小波域倒谱能量特征以及五个时域因子作为21维联合特征参数，具体特征列表如表3所示。

表3 时频特征向量列表

3.3 齿轮箱故障工况识别

建立起特征样本集：(xi,yi)，xi∈R21为样本输入，yi∈{1,2,3,4,5}，i=1,2,3,4，5为样本输出，分别代表行星轮磨损、行星轮点蚀、行星轮断齿、轴承裂纹、保持架坏五种工况类型。利用本文算法进行故障识别，其中，交叉验证中各类分别采用80组(80%)数据作为训练集，20组(20%)作测试集。图5为经本文算法所得的PSO适应度曲线图，从图中可知应用本文算法获得的故障识别准确率较高，达93.75%。

图5 PSO适应度曲线图

为了进一步验证本文所述算法性能上的优点，仍旧采取2.4节仿真试验中所述三种多分类算法与本文算法进行对比验证(对于第四种本文所述算法，W取经PSO优化所得值0.2501)。最终所得结果如表4所示。

表4 不同算法识别结果对比

从表4各算法所得实验结果对比可知，在诊断时长方面，几种基于孪生支持向量机的算法在运算速度上要明显快于传统支持向量机；在识别率方面，基于类混合分离性测度的本文算法虽然在识别用时上要略大于仅考虑类间样本距离时的PBT-TWSVM，但在分类准确率上前者却比后者高出了近四个百分点，这与合理的二叉树层次结构设计有关，由此也进一步证明了本文所述改进算法在实际多分类应用问题性能方面的优越性。

4 结论

本文结合孪生支持向量机和二叉树两种算法的优势，分析了二叉树孪生支持向量机多分类算法的原理及特点，提出了一种改进的PBT-TWSVM多分类算法，定义了一种加权样本类内距离和类间距离的混合分离性测度β，并运用PSO算法对权重及TWSVM参数进行了优化，以各最优化后的参数的确立了最终的PBT-TWSVM分类器模型；

通过UCI数据集仿真试验，对传统SVM、1-v-1TWSVM、基于类间距离的PBT-TWSVM和本文基于混合分离性测度的PBT-TWSVM四种算法在性能上进行了对比分析，结果表明，本文所述算法在分类准确度方面具有绝对优势，尤其是在解决较大规模的多分类问题时，这种优势更为明显；将本文算法引入至风电机组齿轮箱的故障诊断中，同样获得了较好的故障识别效果。