有向无环图的多类支持向量机分类算法

2011年4月

电机与控制学报

ELECTRICMACHINESANDCONTROL

Vol.15No.4Apr．2011

有向无环图的多类支持向量机分类算法

王艳，陈欢欢，沈毅

（哈尔滨工业大学航天学院，黑龙江哈尔滨150001）

要：为研究基于有向无环图的支持向量机分类算法以及在故障诊断问题中的应用，考虑到有向无环图的结构运算相当于一个表操作，且分类结果依赖于有向无环图中节点的排列顺序，提出一种摘

该算法引入基于类分布的类间分离性测度，估计各类训练数据间的分布性质，建立初始分类算法，操作表单，将样本所有可能的类别按照一定顺序排列在表单中，从而重新组合有向无环图中的节点顺序，构造基于分离性测度的有向无环图的拓扑结构。通过对3个典型数据集的数值仿真研究，结果表明所提算法的性能优于传统算法。

关键词：支持向量机；有向无环图；分离性测度；故障诊断

中图分类号：TP18

文献标志码：A

文章编号：1007－449X（2011）04－0085－05

Multi-classsupportvectormachinebasedondirectedacyclicgraph

WANGYan，CHENHuan-huan，SHENYi

（SchoolofAstronautics，HarbinInstituteofTechnology，Harbin150001，China）

Abstract：Supportvectormachinebasedondirectedacyclicgraph（DAG）wasproposedformulti-classclassificationandappliedtomulti-classfaultdiagnosisproblems．ConsideringDAGbeingequivalenttoalistoperation，andtheclassificationperformancedependingonthenodes’sequenceinthegraph，aclas-sificationmeasurebasedonthedistributionofmulti-classdatawasintroduced．Thismethodusedsepara-bilitymeasurebetweenclasstoestimatedistributioncharacterofeachclass，establishedtheinitializationoperationlist，andorganizedallsampleclassesinthelistaccordingtocertainsequence．ThetopologystructureofDAGbasedonseparabilitymeasurewasconstructedbyrearrangingthenodes’sequenceinthegraph．Totestifytheeffectivenessoftheproposedmethod，numericalsimulationswereconductedonthreedatasetscomparedwithconventionalmethods．Theresultsshowthat，theproposedmethodhasbet-terperformanceandhighergeneralizationability．

Keywords：supportvectormachine；directedacyclicgraph；separabilitymeasure；faultdiagnosis

0引言

的机器学习方法，已成功地应用于模式识别尤其是

［1－2］

。其采用基于统计学习故障诊断与分类等领域

SLT）的结构风险最理论（statisticallearningtheory，

小化原则（structuralriskminimizationprinciple，SRMP），能有效地解决非线性、有限样本和高维等

故障诊断与分类一直是模式识别中的重要研究

领域。近年来，由Vapnik与其同事提出来的支持向SVM）作为一个强有力量机（supportvectormachine，

收稿日期：2010－11－22

60874054）；高等学校博士学科点专项科研基金（20092302110037）基金项目：国家自然科学基金（61071182，

作者简介：王艳（1959—），女，高级工程师，硕士生导师，研究方向为模式识别、智能控制；

陈欢欢（1984—），女，硕士研究生，研究方向为故障诊断、优化算法；

沈毅（1965—），男，博士，教授，博士生导师，研究方向为控制系统故障诊断、飞行器控制。

86电机与控制学报第15卷

问题，通常可以提供良好的学习能力和推广

［3－4］

。能力

支持向量机最初是针对二元分类问题提出来

的，不能直接用于多元分类问题，而大部分的故障诊断问题为多元分类情况，如何有效地把它扩展到多

［5］

类情况是一个正在研究的热点问题。

DAG结构表示了X所属的类别。与树状结构不同，

具有冗余性，同一类别的样本，分类路径可能不同，与一般的决策树方法相比，更易于计算，且学习效果也更好。

DAG结构运算相当于一个表操作，在初始状态下，表中包含了所有的类，在分类时，每次对表单中的首尾两个类别进行比较，排除掉样本最不可能属于的类别，并删除表中的一个类，从而使表单中的类

依此类推，那么当经过m－1次排除之别数减少1，

后，表单中唯一剩下的一类即为该样本所属的类别。

DAG最后输出的分类结果对图中节点的排列顺序的依赖性很大，不同的节点的排列顺序会导致部分样本的决策路径不同，从而直接影响分类效果。本文通过引入基于类分布的类间分离性测度，估计

建立初始操作表单，将各类训练数据间的分布性质，

样本所有可能的类别按照一定顺序排列在表单中，

从而重新组合有向无环图的节点顺序。

1有向无环图

目前多元分类器的扩展主要是通过组合一系列

［6］

二元支持向量机分类器，这种方法主要有两个常用算法：1）“一对多”算法，该算法将其中一个类别的样本作为一类，其他不属于该类别的样本作为一类，依次进行训练；2）“一对一”算法，该算法组合所有可能的二元分类器，每次对其中的两个类别进行训练。然而这两个算法在实际应用中也有局限性，举例来说，任何一个分类器的错误分类都会导致不可分区域的存在，而且以上两个多元分类器的训练

［7］

速度将随着训练样本数或类别数的增多而变慢。“一对一”Platt等提出了一个新的学对于算法，

习架构，即有向无环图（directedacyclicgraph，DAG）［8］。在对多个“一对一”二元子分类器进行组引入图论中有向无环图的思想，将多个合的过程中，

二元分类器组合成多元分类器。对于一个m元的DAG共含有m（m－1）/2个节点，分类问题，对应

m（m－1）/2个二元分类器，分布于m层结构中。其拓扑结构如图1所示，顶层只含有1个节点，称为根节点，第二层含有2个节点，依次类推，第i层含有i个节点，最底层含有m个叶节点，其中第j层的第i个节点指向第j+1层的第i个和第i+1个节点。

SVM1-4（1、2、3、4）非1SVM2-1（2、3、4）非2SVM3-4（3、4）非34非4非23非4非4SVM1-3（1、2、3）非1非3SVM1-2（1、2）非3非12非212分类算法

在对训练数据评估各类间的分离度时，通常采

［7］

用欧氏距离衡量类间分离性测度。如图2所示，两类间的距离相等，但离散度却存在很大差异。由图可见，欧氏距离并不能很全面客观地代表其类间的分离度，这直接影响了在分类建模中的难易程度，因此引入一种基于类分布的类间分离性测度来评定各类间的分离性质。

（a）b）（图2

Fig．2

类间分离性测度示意图

Thediagrammaticillustrationofseparabilitymeasurebetweenclasses

SVM2-3（2、3）X2，考虑具有m个类别的训练数据X=｛X1，

…，Xm｝，j=第i类和第j类之间的分离性测度smij（i，1，2，…，m）定义为

smij=

dij

，σi+σj

1

x，lk∑x∈Xk

（1）（2）（3）

Fig．1

图1有向无环图结构图

Thestructurechartofdirectedacyclicgraph

dij=‖Ci－Cj‖，Ck=σk=

对于给定的输入样本X，从根节点出发，计算每

个节点的决策函数值，若为1，则从左边进入下一节点，若为－1，则从右边进入下一节点，然后计算下一节点的值，依此类推，在最后一层叶节点处的输出就

1

‖x－Ck‖。

lk－1∑x∈Xk

其中：dij表示第i类和第j类之间的距离；Ck（k=1，

2，…，m）是各类训练样本的均值中心；lk为类Xk中

第4期王艳等：有向无环图的多类支持向量机分类算法87

的样本个数；σk表示第k类的标准差，表明了第k类的分布情况。

j=计算第i类和第j类间的分离性测度smij（i，

1，2，…，m），得到一个m×m阶的类间分离性测度2，…，m）行表明了第k类的分矩阵，其中第k（k=1，

布性质。由此构造初始操作表单：

1）对于每一类，都存在m－1个与其他类的分离性测度值。首先，分别对每一类的这些值按从小到大的顺序进行排列，并重新编号。例如，第k类与

2，…，m，t≠其他类间分离性测度值为smkt（t=1，

k），按从小到大的顺序重新排列为smk≤smk≤…≤smk

m－1

1

2

盖表面振动信号经小波变换处理后所得的数据。

3）UCI机器学习公用数据库的伺服电机系统数据集，该系统输出值是调整时间，即系统处在一个设定的位置时，对阶跃指令响应并运行到位的时间，根据该时间数值，可均等划分为6种类别（分别用D31、D32、D33、D34、D35、D36表示），数据集包含167个样

分别由电机类型、导轨螺纹类型、位置环比例增本，

益以及速度环比例增益这4个属性描述。

表1

Table1

数据集双螺杆挤出机

3个数据集的简要描述

Abriefdescriptionofthethreedatasets

类别数目

456

总样本数目

92150167

属性数目

784

。

1

2）然后根据值smk（k=1，2，…，m），按从大到

小的顺序，对相应的类别进行排序。当存在两个或两个以上的类别具有相同的smk时，再比较他们的

1smk2大小。如此下去，smk2，…，若他们的smk，

1

柴油机伺服电机系统

smkm－1都相同，则把类标号小的类排在前面。比如

11对第i类和第j类进行比较，若smi＜smj，则第j类11排在第i类之前；若smi＞smj，则第i类排在第j类1122之前；若smi=smj，则继续比较smi和smj的大

应用有向无环图方法，得到3个数据集的初始

如表2所示，由此重新排列节点顺序，得操作表单，

到基于分离性测度的有向无环图DAGsm的拓扑结

构（图3）。以双螺杆挤出机数据集为例，顶层根节SVM1－4，点为SVM1－3，第二层节点为SVM2－3、第三SVM2－4、SVM1－2，层节点为SVM4－3、最底层叶节点D14、D12、D11。为D13、

表2

Table2

3个数据集的初始操作表单

Theinitialoperationlistofthethreedatasets

初始操作表单［D11，D12，D14，D13］［D25，D22，D21，D24，D23］［D33，D32，D34，D36，D31，D35］

2，…，m－1），小；依次下去，如果smi=smj（t=1，

j中小的类别排在前面，则把类标号i，类标号大的类别排在后面。

3）最后得到所有类别的排列s1，s2，…，sm，此处sk∈｛1，2，…，m｝，k=1，2，…，m为类标号。根据类

s1，s2，…，sm］，标号的排序，建立初始操作表单［则表单中的首尾两个类别的分布性质具有最大差异，

以此类推，并由此重新排列节点顺序，得到有向无环图的拓扑结构。

tt

数据集双螺杆挤出机

柴油机伺服电机系统

，实验采用两种方法：第一种是“训练测试法”

即将数据集分成训练集和测试集，分别用来进行训算法的准确率等于M/N，其中N为测试练和测试，

M为得到正确分类的测试样本数（表3）；集样本数，

“交叉验证法”，第二种是即将数据集随机分成几等

其中的一份作为测试集，余下的数据合成训练份，

集，算法的准确率为多次训练测试的平均值（表4，将总样本分为3等份的3折交叉验证）。同时，在相同的软硬件环境下记录各算法的平均运行时间，以比较其性能（表5）。

表3Table3

算法一对多一对一DAGDAGsm

3仿真研究及结果分析

将基于有向无环图的支持向量机应用于多元分类问题。实验选取机器学习领域中的3个典型测试数据集

来进行测试，所有样本数据都分成训练样

本和测试样本。表1简要描述了这3个数据集：1）双螺杆挤出机故障数据集，包含正常状态、双螺杆的止推轴承润滑不够以及两根螺杆之间的间隙出现了严重偏差、机头杂质过多造成机头压力偏高4种状D12、D13、D14表示），态（分别由D11、数据属性为料筒的温度（沿料筒分布的5个热电偶采集到的5个点的温度）、油泵电压和主电机电流；2）柴油机故障数据集，包含正常状态、进排气门间隙极小、进排气门间隙极大、排气门轻度漏气、排气门严重漏气5种

D22、D23、D24、D25表示）下的缸状态（分别用D21、

［9］

4种算法的测试精确度

Thetestaccuraciesof4motheds

柴油机94.12%95.29%95.29%96.47%

伺服电机系统77.81%81.05%83.44%83.96%

95%100%100%100%

双螺杆挤出机

88

表4

Table4

电机与控制学报第15卷

4种算法的3折交叉验证平均精度

Theaverageaccuraciesofmethodsby3-foldcross

双螺杆挤压机97.83%99.13%99.13%99.13%

柴油机96.42%97.33%97.33%97.88%

伺服电机系统79.%82.03%84.69%85.41%

“一对多”“一对一”执行速度也比算法和算法都快，

因此具有更好的泛化性能。基于分离性测度的有向无环图DAGsm，通过引入基于类分布的类间分离性

初始化操作表单，重新排列节点顺序，构造有测度，

、“一对多”“一向无环图的拓扑结构，较标准DAG和算法均得到更好的预测效果。对一”

在表6中，以伺服电机系统数据集为例记录了各子分类器在3折交叉验证后的分类误差均值及标

算法一对多一对一DAGDAGsm

表5

Table5

4种算法的执行时间

/s

Theexecutiontimesof4methods

准差。由于被子分类器正确分类的样本仍有可能在最后的投票中被错误地标定为其它类别，而被子分类器错误分类的样本也有可能在最后的投票中被纠

所以不同的统计方法往往得到不回到正确的分类，

同的分类误差。鉴于实验的目的是为了反映各分类

方法相对各子分类器的性能改善，因此我们采用各子分类器错误分类的样本数除以该子分类器所涉及

并不计入由于其他到的样本总数来表示分类误差，

子分类器的错误投票所导致的错误分类。从具体的

统计数据来看，虽然子分类器处理的对象不一致，但平均分类误差仍然是所提方法最佳；而更小的标准差也说明各子分类器的平均性能一致性更好。

表6

Table6

算法一对多一对一DAGDAGsm

算法一对多一对一DAGDAGsm

双螺杆挤压机

0.65930.34740.16970.1709

柴油机1.28371.44090.56560.5598

伺服电机系统

3.94562.87112.25932.1019

SVM1-3SVM2-3SVM4-3D13D14SVM1-4SVM1-2D11SVM2-4D12对伺服电机系统进行3折交叉验证

（a）双螺杆挤出机SVM5-3SVM2-3SVM1-3SVM4-3D23D24SVM5-4SVM5-1SVM5-2D253-foldcrossvalidationforservomotorsystem

子分类器数目

6151515

平均分类误差/（%）

7.32%4.51%3.65%3.30%

标准差/（%）3.62%2.78%2.65%2.11%

SVM2-4SVM1-4SVM2-1D21（b）柴油机SVM3-5D224结语

本文从支持向量机在故障诊断与分类方面的应用出发，提出并分析研究了一种多类支持向量机分

考虑到传统算法的类算法。该算法的基本思路是，

为了得到更高的推广性能，引入基于类分布的局限，

类间分离性测度，估计训练数据间的分布性质，重新组合有向无环图的节点顺序，应用支持向量机进行二元分类，得到一个多元支持向量机分类器。该算“一对多”“一对一”法与一般的和算法相比，其主要

有向无环图能解决不可分区域问题，具有更特点是，

高的预测精确度，且只需使用较少的二元支持向量

机子分类器，具有较快的执行速度和更好的泛化性能。为了验证算法的有效性，本文利用双螺杆挤出机故障、柴油机排气门故障和伺服电机系统分类等3个数据集，利用所提算法进行了数值仿真研究，仿真结果表明该算法对3种典型故障诊断数据均可达

SVM2-5SVM6-5SVM6-5SVM1-5D35SVM3-1SVM3-6SVM3-4SVM3-2D33SVM4-1SVM4-1SVM2-6SVM6-1D36SVM4-6SVM2-4D31D34D32（c）伺服电机系统图3Fig．3

3个数据集的DAGsm拓扑结构TheDAGsmTopologicalStructureofthethreedatasets

“一对多”“一对一”与算法和算法相比，有向无环图能解决不可分区域问题，具有更高的预测精确度，而且只需使用较少的二元支持向量机子分类器，

第4期王艳等：有向无环图的多类支持向量机分类算法

到更好的性能和更高的精度以及更快的运行速度。将该算法用于实际系统，探讨并解决其应用中存在的问题，是下一步重点研究内容。

参考文献：

［1］YANWeiwu，SHAOHuihe．Applicationofsupportvectormachine

nonlinearclassifiertofaultdiagnosis［C］//Proceedingsofthe414，2002，Shanghai，China．2002（4）：2697－2700．

［2］LIYe，CAIYunze，YINRupo，etal．Faultdiagnosisbasedon

C］//Proceedingsofthe4thIn-supportvectormachineensemble［

ternationalConferenceonMachineLearningandCybernetics，Au-2005，Guangzhou，China．2005：3309－3314．gust18－21，［3］

VAPNIKVN．Anoverviewofstatisticallearningtheory［J］．1999，10（5）：88－99．IEEETransactionsonNeuralNetworks，

［4］WANGXizhao，LUMingzhu，HUOJianbing．Faultdiagnosisof

powertransformerbasedonlargemarginlearningclassifier［C］//Proceedingsofthe5InternationalConferenceonMachineLearn-ingandCybernetics，August13－16，2006，Dalian，China．2006：2886－21．

［5］HSUChihWei，LINChihJen．Acomparisonofmethodsformulti-th

th

classsupportvectormachines［J］．IEEETransactionsonNeuralNetworks，2002，13（2）：415－425．

［6］WANGXiaodan，SHIZhaohui，WUChongming，etal．Anim-provedalgorithmfordecision-tree-basedSVM［C］//Proceedingsofthe6thWorldCongressonIntelligentControlandAutomation，June21－23，2006，Dalian，China．2006：4234－4238．

［7］FUMITAKETakahashi，SHIGEOAbe．Decision-tree-basedmulti-classsupportvectormachines［C］//Proceedingsofthe9thInter-nationalConferenceonNeuralInformationProcessing．2002：1418－1422．

［8］FENGJun，CHENDongE．HandwrittensimilarChinesecharac-tersrecognitionbasedonmulti-classpair-wisesupportvectorma-chines［C］//Proceedingsofthe4thInternationalConferenceonMachineLearningandCybernetics，August18－21，2005，Guan-gzhou，China．2005：4405－4409．

［9］MERZCJ，MURPHYPM．UCIRepositoryofmachinelearning

databases．DepartmentofInformationandComputerScience，Uni-versityofCalifornia，Irvine，1998，http：//www．ics．uci．edu/～mlearn/MLRepository．html．

WorldCongressonIntelligentControlandAutomation，June10－

（编辑：于智龙）