改进二叉树支持向量机及其TE过程故障诊断

陈柏志 石宇强 詹钧凯 邬江波

(西南科技大学制造科学与工程学院 四川绵阳 621010)

支持向量机(Support Vector Machines，SVM)，是一种建立在统计学习理论基础上的机器学习新方法[1]，它在解决小样本、非线性以及高维模式识别等问题中表现出特有的优势，并在很大程度上克服了“维数灾难”和“过学习”等问题。最初SVM是针对二分类问题设计的，而实际问题往往属于多类别分类，如故障诊断、文本分类、人脸识别等。目前，SVM解决多类分类的方法主要有一对多SVM、一对一SVM、决策有向无环图SVM和二叉树SVM等[1-4]。其中，与一对一、一对多以及决策有向无环图等SVM方法相比较，二叉树SVM具有需要训练的分类器数目最少、样本重复训练率低、分类速度快且不存在不可分区域等优点，是一种非常适合故障诊断的支持向量机多类分类算法。

二叉树SVM由于其特有的优势，近年来受到了学者的广泛关注，主要聚焦在三个方面：(1)二叉树SVM的推广能力依赖于二叉树的树形结构，类间差异性估计是设计二叉树结构的基础。样本之间欧式距离是广泛采用的度量手段。文献[5]以类间样本最短距离来度量类间的距离，让距离最远的类最先分离出来。文献[6]以类内样本间最大距离来度量类内样本分布的范围，让分布广的类最先分离出来。文献[7-8]综合考虑类间和类内样本分布的情况，将两个角度的描述合理结合起来，更全面地反映类别之间的差异性。(2)将其他方法与二叉树SVM结合起来进一步优化二叉树SVM的样本不平衡、训练时间以及精度等，文献[9-10]将二叉树与双支持向量机相结合，利用双支持向量机克服了二叉树SVM可能存在的样本不平衡问题和减少二叉树SVM的训练时间。(3)将二叉树SVM应用到实际问题中，如机械故障诊断、焊缝缺陷检测、网络入侵检测等[8,10-11]。

TE(Tennessee Eastman)过程作为一个典型的化工生产模型，具有复杂多变、非线性等特点[12]，其过程存在以下特点：(1)复杂的非线性；(2)故障发生表现出强烈的滞后性；(3)工艺参数众多且相互干扰，彼此耦合，存在部分重合。鉴于SVM在解决非线性、高维数据以及局部极小等问题的优势，是TE过程故障诊断的理想方法。

本文基于帕累托原则结合类间样本距离和类内样本分布设计了一种新的类间差异性估计策略，并提出了完全二叉树SVM的构建方法。较之前的研究，本文还探讨了完全二叉树、偏二叉树以及从上到下构造二叉树、从下到上构造二叉树的推广性能。利用标准数据集，与一对一、一对多、决策有向无环图以及其他二叉树方法作比较，评定改进算法的性能。以TE过程为故障诊断对象，基于核主成分分析提取故障特征，利用改进算法收到了令人满意的故障诊断效果。

1 改进二叉树支持向量机

1.1 SVM多类分类算法介绍

目前，SVM多类分类方法根据其指导思想大致有两类：一种是通过构造多个二类分类器并将它们组合起来完成多类分类；另一种是只使用一个SVM分类器，该分类器对SVM的原始最优化问题作适当修改从而“一次性”地计算出多类分类决策函数。第二种方法的指导思想看似简单，但它的最优化问题求解过于复杂，计算量大，而且在分类精度上也不占优势。因此，第一种方法更为常用。

第一种方法主要包括一对多(One-against-Rest,1-a-r)，一对一(One-against-one,1-a-1)，决策有向无环图(Decision Directed Acyclic Graph，DDAG)、二叉树(Binary Tree，BT)等方法。一对多方法简单，需要训练的子分类器个数少，但其缺点是当类别数较多时，训练样本的不平衡将对精度产生影响，且存在拒分区域。一对一方法训练样本是平衡的，训练精度高于一对多方法，但类别较多时，需要训练较多的子分类器，其时间复杂度大大增加，不适用类别较多的情况，并且也存在拒分区域。DDAG方法的优点是分类速度较前面两种方法有明显提高，不存在拒分区域，缺点是需要同一对一方法一样多的子分类器，并且其根节点选取的二值分类器不同其精度会有明显差异[2]。

二叉树SVM是一种采用二叉树结构来构造SVM多类分类的算法，其构造过程如下：将所有类别依据某种策略划分成两个子类，再将这两个子类分别划分成两个次子类，如此循环下去，直到所有的类别都作为一个单独节点为止，此节点也就是二叉树中的叶子节点。二叉树SVM方法可以避免传统的一对多、一对一方法存在的不可分区域，并且只需构造k-1个子分类器，其分类时平均需要经过log2k个子分类器，分类速度大大提高，缺点是二叉树的结构对整个模型的分类精度有较大的影响，可能存在“误差累积”现象，上层节点发生的分类错误，会把这种错误延续下去，使后续节点的分类失去意义，并且分类错误越靠近根结点，模型推广性能越差。因此，二叉树SVM的关键是如何设计有效的二叉树结构。上述4种SVM多类分类方法对比如表1所示。

1.2 类间差异性估计

为了避免“误差累积”现象，应该让最容易分割的类率先分离出来，也就是要尽可能的去估计类别之间的差异性，类别之间差异性越大越容易分割。然而由于各个类别数据的真实分布情况无法得知，只能利用有限的样本集的分布情况去近似估计真实数据的类别差异性。在先前的研究中，学者分别使用了多种策略对类别差异性进行描述，其策略大致有两个方面:一是采用不同类别样本之间的欧氏距离来度量类别之间的距离，二是利用类内样本分布半径作为类别分布区域大小的度量，或者是综合考虑类间距离和类内样本分布的影响，从实际的分类效果来看[7-8]，综合考虑两个方面的策略能更好地估计类间差异性。但是这些方法也存在一些问题，当训练样本数据存在测量误差或者方法误差即所谓的“野值”，导致数据的散布较大，由此生成比实际所占区域更大的超球体半径，同时这些“野值”由于距离超球体中心较远，因此在计算方差或者超球体中心时容易造成偏差，这样就会带来层次误差，误差逐层累积，导致分类精度降低。

表1 SVM多类分类方法对比Table 1 Comparison of SVM multi-class classification methods

如图1所示，各个类别的样本在高维空间是各自聚集在一起的，形成了超球体中心点，按照距离中心点的远近将数据的分布范围由内到外可分为核心圈、计算半径圈以及边界圈。核心圈内的数据是类别最具代表性的数据，具有明显的类别特征；计算半径圈是将类别所有样本都纳入半径计算过程得到的；边界圈是依据距离中心点最远的样本划分的，包含了类别所有的样本。

图1 类分布示意图Fig.1 Schematic diagram of class distribution

19世纪末期的意大利经济学家兼社会学家维弗利度·帕累托提出“重要的少数与琐碎的多数”原理，该原理指出在特定领域20%的少数达到总体贡献度的80%，掌握该20%的因子就能控制全局，这就是著名的帕累托法则，也称80/20效应。

根据帕累托法则，结合前面的分析，可以得出，分类样本中20%的数据能够代表核心圈的分布情况，80%的样本能够代表计算半径圈的分布情况。

核心圈内的样本距离其类别中心点最近，是具有明显类别特征的样本，与其他类别样本的距离较远，不会存在样本重叠现象。在此，采用核心圈样本最近类间距离来衡量类间距离。核心圈样本最近类间距离越大，类间距离越远，类别之间的差异性越大，反之亦然。核心圈样本最近类间距离定义如下：

计算i,j类核心圈样本的最近距离

min(di,jker)=min{‖xiker-xjker‖}

(1)

计算半径圈内的样本反映了同类样本的整体有效分布情况。在此，采用计算半径圈内样本平均密度来衡量类内样本的分布情况。平均密度小，表明样本分布得越紧密，反之亦然。类内计算半径圈内样本平均密度定义如下：

(2)

其中ximax表示计算半径圈内的样本，nimax表示计算半径圈内的样本数目。类内计算半径圈内样本的均值

(3)

根据类间距离大且类内样本分布得越紧密集中的类间差异性越大的原则，设计的类间差性估计策略要能够体现两方面的因素，具体形式为：

(4)

类间差异性估计策略具体计算步骤如下：

步骤1 建立训练样本集{xi,yi},yi={1,2,…,k}，k为类别数，然后将训练样本的各特征值归一化，线性调整到[-1,+1]。

步骤2 依据公式(3)，计算每个类别的超球体中心ci。

步骤4 对各个类别的样本取重新排序后前20%的样本依据公式(1)计算min(di,jker)，取前80%的样本依据公式(2)和(3)计算σimax，σjmax，最后依据公式(4)求出i,j类的类别差异度Ii,j。

步骤5 按照上述步骤计算得出各类间的差异性SI=Iij，i,j=1,2,…,k,i≠j。构造表示类间差异性的对称矩阵

1.3 改进的二叉树支持向量机算法设计

如图2所示，二叉树支持向量机有两种结构，一种是偏二叉树，在判断节点处由一个类作为正类与余下的类别作为负类构造分类超平面；一种是完全二叉树，在判断节点处由多个类与多个类构造分类超平面。尽管偏二叉树构造过程简单，但是对于类别数较多的样本集来说，树的深度大，测试平均时间比完全二叉树长，同时容易造成样本不均衡。

图2 完全二叉树与偏二叉树示意图Fig.2 Schematic diagram of complete binary trees and partial binary trees

与常见的从上到下构造策略不同的是，哈夫曼树(Huffman Tree，HT)是从下往上构造的二叉树结构，其思想是将当前认为最不好分的两类率先生成决策节点。从构造思想上看，基于这种构造思路得到的上层决策节点是全局最优解，其整体分类效果可能优于从上往下构造的二叉树结构，但其实际生成的树形结构往往倾向于偏二叉树，其原因在于往上的构造过程中形成的由多个类别构成的决策节点在与单个类别的叶子节点估计类间差异性时占有很大的优势，已生成的决策节点容易与叶子节点生成上一层的决策节点，其总体形态偏向于偏态树。

完全二叉树克服了偏态树的缺点，特别是类别数较多时，其性能优势更加明显。为了生成完全二叉树或者近似完全二叉树，具体算法步骤如下：

步骤1 对于k类问题，求出差异性估计矩阵SI，并将各类的类别标号由小到大存入集合C中；

步骤2 从SI中找出差异性最大(maxIi,j)的两个类i和j，将i类样本存入集合C1中，将j类样本存入集合C2中，并从C中删除i,j类标号；

步骤3 若C=φ，则转到步骤5；

步骤4 在SI中查找类m(m∈C)分别与i,j类的差异性，若Ii,m

步骤5 将C1作为二叉树的左子树，C2作为二叉树的右子树。将C1中对应的样本标记为正类，C2中对应的样本标记为负类，至此，得到一个子分类器；

步骤6 令C=C1，直到C1只包含一个类别不可再分为止，此时左子树构造结束。否则，返回步骤2，将C1进一步分割成左右子树；

步骤7 令C=C2，直到C2只包含一个类别不可再分为止，此时右子树构造结束。否则，返回步骤2，将C2进一步分割成左右子树。

2 标准数据集实验

2.1 实验数据与实现

为了评价改进算法的性能，本文使用UCI数据库[13]的Win,Segment,Optdigits,Satimage 4个标准数据集(表2)，将本文所提改进算法与一对一、一对多、DDAG 3种常规SVM分类算法进行实验测试对比的同时，还与从上到下构造的偏二叉树(偏BT)、哈夫曼树(HT)、偏哈夫曼树(偏HT)3种二叉树算法进行实验测试对比。本文所有算法均采用VC++编程，在LIBSVM工具包基础上修改实现。实验平台为AMD A10-7400P，4GB RAM，操作系统为Windows 7 SP1。

为了避免取值范围更大的属性占更多优势，本文对样本数据全部进行标准分归一化预处理，将属性范围调整到[-1,+1]。SVM的核函数采用径向基核函数，具体形式为：K(x,xi)=exp{-γ‖x-xi‖2}。同时由于模型的推广能力与核参数γ、惩罚参数C有关，为了保证参数搜索空间的完备性以及对训练数据集获得更好的误差估计，将网格寻优和交叉验证共同作用，参数C的寻优空间为[21,22,…,28]，参数γ的寻优空间为[2-4,2-3,…,20]，共8×5=40种组合，采用十折交叉验证，从而获得推广能力最佳的(C,γ)组合。实验结果如表3所示(表中所有精度值保留两位有效小数)。

不同算法运行的时间结果见表4，Win数据集由于其样本数较少，运行时间过短难以比较，故省略。为了避免不同的参数对运行时间产生影响，将各个数据集的参数固定为：Segment(28,20)，Satimage(23,20)，Optdigits(23,2-4)。运行时间采用CPU时间，运行10次求平均值作为最终结果(单位为s，结果保留3位有效小数)。

表2 数据集信息统计表Table 1 Statistic information of data sets

表3 各算法最优参数及识别准确率Table 3 Optimal parameters and recognition accuracy of each algorithm

表4 各算法运行时间Table 4 Operation time of each algorithm

2.2 实验结果分析

为了对比二叉树方法与一对一、一对多、DDAG方法在精度和时间方面的优劣以及验证本文算法，将4种二叉树方法作为整体与其他3种方法进行比较的同时比较各个数据集上精度和时间的最优算法，如前面表1所描述，在精度方面，一对一、DDAG和二叉树方法相当，明显优于一对多方法，除Segment数据集上一对一方法精度最高外，其他数据集上本文算法精度最高；在训练速度方面，一对一和DDAG方法由于训练的分类器完全一样，其训练速度是一致的，一对多方法在各个数据集上的训练速度都最慢，HT、偏HT以及偏BT训练速度要明显慢于一对一和DDAG方法，但本文所提算法在Satimage数据集上训练速度最快，在Segment和Opdigits数据集上略微慢于一对一和DDAG方法；在测试速度方面，本文所提算法用时最短，二叉树方法要明显优于其他3种方法，DDAG方法要略优于一对一和一对多方法，一对一和一对多方法测试速度相当。

为了更深入更直观地比较4种二叉树算法的性能，将针对4种二叉树算法生成的树形结构进行讨论。Win数据集由于只有3个类别，4种算法生成一样的二叉树结构，其精度和时间都是一致的；在Segment数据集上，HT与本文算法生成完全一样的树形结构，其精度和时间呈现出一致的效果，偏BT精度略微高于其他3种算法，但HT和本文算法由于生成的是近似完全二叉树，其时间明显快于偏HT、偏BT；在Satimage和Optidigits数据集上，本文算法在精度上略占优势，其速度明显快于其他3种算法，特别是在类别数较多的Optidigits数据集上其速度优势更明显，本文算法生成完全二叉树结构，其树的深度比其他3种算法小很多，HT与偏HT都生成完全一致的偏二叉树结构，偏BT生成与HT、偏HT不一样的二叉树结构，HT、偏HT以及偏BT由于都是偏二叉树结构，其速度都是一致的。

3 TE过程故障诊断

3.1 TEP简介

TE过程是由Downs和Vogel[14]提出的一个仿真化工过程，根据伊斯曼化学公司的实际工艺流程模拟实现而来，具有复杂多变、非性线的特点。TEP(Tennessee Eastman Process, TEP)包括：化学反应器、冷凝器、压缩机、气液分离器、汽提塔这5个运行单元和A,B,C,D,E,F,G,H这8种成分，A,C,D,E 4种生产原料和不参与反应的惰性成分B投入装置生成产品G和H，F是反应过程中的副产品。TE过程含有41个测量变量(22个连续变量、19个成分变量)和12个操作变量，由于第12个操作变量(搅拌速度)是恒定值，所以TE过程共有52个可控的过程变量。除正常运行状态外，TE过程包括20个典型故障，其中有5个未知故障，本文利用15个已知故障进行实验，仿真产生7 700条训练数据，其中500条是无故障数据，各个故障类别均是480条数据；12 960条测试数据，960条无故障数据，各个故障类别均是800条数据。

3.2 故障特征提取

TE过程含有大量的监控工艺参数，这些工艺参数之间存在较强的相关性，并且反应器温度、压力、原料进料量等容易发生阶跃变化，呈现出强非线性。而核主成分分析通过将原始数据映射到高维空间进行主成分分析，达到线性可分和特征降维的效果，在过程监测领域得到广泛应用。通过核主成分分析，选取少数的核主成分就可以表征过程主要的变化信息，实现过程特征提取，缩短了支持向量机的训练时间和训练精度。本文核主成分分析采用径向基核函数，特征值贡献率确定为95%，核参数通过达到贡献率时所需核主成分数最少与支持向量机训练结果最优共同经验确定γ=2-12，选取23个核主成分。核主成分分析结果如表5所示。

表5 TEP训练样本核主成分分析结果Table 5 Analysis results of kernel principal component in TEP training samples

3.3 TEP故障诊断

将原始训练集和测试集通过核主成分变换成新的训练集和测试集，对于每个算法选择其十折交叉验证的平均分类精度最好情况下对应的惩罚参数C和核函数参数γ。对于本文算法的每个两类问题，如果正类和负类样本数目差别太大，则令C1=n1×C/n，C2=n2×C/n，其中n1和n2分别表示两类问题中的正、负类样本数目，n=n1+n2。各算法的实验结果如表6所示。

表6 各算法故障诊断识别准确率Table 6 Recognition accuracy of fault diagnosis of each algorithm

4 结论

(1)在分析类间差异性估计策略的基础之上，基于帕累托原则以核心圈样本最近类间距离和类内计算半径圈样本平均密度建立了类间差异性估计策略，提出了改进二叉树SVM的算法步骤。

(2)利用标准数据集，通过与其他SVM多类分类方法比较，所提算法识别准确率高，训练和测试时间短，验证了该算法的优越性。

(3)基于核主成分分析提取TE过程故障特征，应用改进的完全二叉树SVM进行故障诊断，收到了较传统SVM多类分类算法更好的故障识别率。

[1] VAPNIK V N. The nature of statistical learningtheory[M]. NewYork:Springer,1995.

[2] HSU C W, LIN C J. A comparison of methods for multiclass support vector machines[J]. IEEE Transactions on Neural Networks, 2002,13(2):415- 425.

[3] PLATT J C, CRISTIANINI N, SHAWE TAYLOR J. Large margin DAGs for multiclass classification[J]. In:Advances in Neural Information Processing Systems,MIT press,2000,12:547-553.

[4] CHEONG S, OH S H, LEE S Y. Support vector machines with binary tree architecture for multiclass classification[J]. Neural Information Processing Letters and Reviews,2004,2(3):47-51.

[5] XIA S Y, LI J X, XIA L Z, et al.Tree structured support vector machines for multiclass classification[A]// Lecture Notes in Computer Science[C].Berlin,Heidelberg:Springer-Verlag,2007:392-398.

[6] 唐发明,王仲东,陈绵云.支持向量机多类分类算法研究[J].控制与决策，2005,20(7):746-749.

[7] 赵海洋，徐敏强，王金东.改进二叉树支持向量机及其故障诊断方法研究[J].振动工程学报,2013,26(5):764-770.

[8] 罗爱民,沈才洪,易彬,等.基于改进二叉树多分类SVM的焊缝缺陷分类方法[J].焊接学报,2010,31(7):51-54.

[9] 谢娟英,张兵树,汪万紫.基于双支持向量机的偏二叉树多类分类算法[J].南京大学学报(自然科学版),2011,47(4):354-363.

[10] 聂盼盼,臧洌,刘雷雷.基于对支持向量机的多类分类算法在入侵检测中的应用[J].计算机应用,2013,33(2):426-429.

[11] 朱新才，邓星,周雄,等.二叉树支持向量机的旋转机械故障诊断[J].重庆大学学报，2013，36(7)：21-26.

[12] 李宏光,夏丽君.改进的FP-growth算法及其在TE过程故障诊断中的应用[J].北京工业大学学报,2016,42(5):697-706.

[13] MURPHY P M, AHA D W. UCI repository of machine learning databases[EB/OL]. http://www.ics.uci.edu/mlearn/MLRepository.html.

[14] DOWNS J J, VOGEL E F.A plantwide industrial process control problem[J]. Computers and chemical engineering,1993,17(3):245-255.