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

王艳， 陈欢欢， 沈毅

(哈尔滨工业大学航天学院，黑龙江哈尔滨 150001)

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

王艳， 陈欢欢， 沈毅

(哈尔滨工业大学航天学院，黑龙江哈尔滨 150001)

为研究基于有向无环图的支持向量机分类算法以及在故障诊断问题中的应用，考虑到有向无环图的结构运算相当于一个表操作，且分类结果依赖于有向无环图中节点的排列顺序，提出一种分类算法，该算法引入基于类分布的类间分离性测度，估计各类训练数据间的分布性质，建立初始操作表单，将样本所有可能的类别按照一定顺序排列在表单中，从而重新组合有向无环图中的节点顺序，构造基于分离性测度的有向无环图的拓扑结构。通过对3个典型数据集的数值仿真研究，结果表明所提算法的性能优于传统算法。

支持向量机;有向无环图;分离性测度;故障诊断

0 引言

故障诊断与分类一直是模式识别中的重要研究领域。近年来，由Vapnik与其同事提出来的支持向量机(support vector machine，SVM)作为一个强有力的机器学习方法，已成功地应用于模式识别尤其是故障诊断与分类等领域［1－2］。其采用基于统计学习理论(statistical learning theory，SLT)的结构风险最小化原则(structural risk minimization principle，SRMP)，能有效地解决非线性、有限样本和高维等问题，通常可以提供良好的学习能力和推广能力［3－4］。

支持向量机最初是针对二元分类问题提出来的，不能直接用于多元分类问题，而大部分的故障诊断问题为多元分类情况，如何有效地把它扩展到多类情况是一个正在研究的热点问题［5］。

1 有向无环图

目前多元分类器的扩展主要是通过组合一系列二元支持向量机分类器［6］，这种方法主要有两个常用算法:1)“一对多”算法，该算法将其中一个类别的样本作为一类，其他不属于该类别的样本作为一类，依次进行训练;2)“一对一”算法，该算法组合所有可能的二元分类器，每次对其中的两个类别进行训练。然而这两个算法在实际应用中也有局限性，举例来说，任何一个分类器的错误分类都会导致不可分区域的存在，而且以上两个多元分类器的训练速度将随着训练样本数或类别数的增多而变慢［7］。

对于“一对一”算法，Platt等提出了一个新的学习架构，即有向无环图(directed acyclic graph，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个节点。

图1 有向无环图结构图Fig.1 The structure chart of directed acyclic graph

对于给定的输入样本X，从根节点出发，计算每个节点的决策函数值，若为1，则从左边进入下一节点，若为－1，则从右边进入下一节点，然后计算下一节点的值，依此类推，在最后一层叶节点处的输出就表示了X所属的类别。与树状结构不同，DAG结构具有冗余性，同一类别的样本，分类路径可能不同，与一般的决策树方法相比，更易于计算，且学习效果也更好。

DAG结构运算相当于一个表操作，在初始状态下，表中包含了所有的类，在分类时，每次对表单中的首尾两个类别进行比较，排除掉样本最不可能属于的类别，并删除表中的一个类，从而使表单中的类别数减少1，依此类推，那么当经过m－1次排除之后，表单中唯一剩下的一类即为该样本所属的类别。

DAG最后输出的分类结果对图中节点的排列顺序的依赖性很大，不同的节点的排列顺序会导致部分样本的决策路径不同，从而直接影响分类效果。本文通过引入基于类分布的类间分离性测度，估计各类训练数据间的分布性质，建立初始操作表单，将样本所有可能的类别按照一定顺序排列在表单中，从而重新组合有向无环图的节点顺序。

2 分类算法

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

图2 类间分离性测度示意图Fig.2 The diagrammatic illustration of separability measure between classes

考虑具有m个类别的训练数据X={X1，X2，…，Xm}，第i类和第j类之间的分离性测度smij(i，j=1，2，…，m)定义为

其中:dij表示第i类和第j类之间的距离;Ck(k=1，2，…，m)是各类训练样本的均值中心;lk为类Xk中的样本个数;σk表示第k类的标准差，表明了第k类的分布情况。

计算第i类和第j类间的分离性测度smij(i，j=1，2，…，m)，得到一个m×m阶的类间分离性测度矩阵，其中第k(k=1，2，…，m)行表明了第k类的分布性质。由此构造初始操作表单:

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

3)最后得到所有类别的排列 s1，s2，…，sm，此处sk∈{1，2，…，m}，k=1，2，…，m 为类标号。根据类标号的排序，建立初始操作表单［s1，s2，…，sm］，则表单中的首尾两个类别的分布性质具有最大差异，以此类推，并由此重新排列节点顺序，得到有向无环图的拓扑结构。

3 仿真研究及结果分析

将基于有向无环图的支持向量机应用于多元分类问题。实验选取机器学习领域中的3个典型测试数据集［9］来进行测试，所有样本数据都分成训练样本和测试样本。表1简要描述了这3个数据集:1)双螺杆挤出机故障数据集，包含正常状态、双螺杆的止推轴承润滑不够以及两根螺杆之间的间隙出现了严重偏差、机头杂质过多造成机头压力偏高4种状态(分别由 D11、D12、D13、D14 表示)，数据属性为料筒的温度(沿料筒分布的5个热电偶采集到的5个点的温度)、油泵电压和主电机电流;2)柴油机故障数据集，包含正常状态、进排气门间隙极小、进排气门间隙极大、排气门轻度漏气、排气门严重漏气5种状态(分别用 D21、D22、D23、D24、D25 表示)下的缸盖表面振动信号经小波变换处理后所得的数据。3)UCI机器学习公用数据库的伺服电机系统数据集，该系统输出值是调整时间，即系统处在一个设定的位置时，对阶跃指令响应并运行到位的时间，根据该时间数值，可均等划分为6种类别(分别用D31、D32、D33、D34、D35、D36 表示)，数据集包含167 个样本，分别由电机类型、导轨螺纹类型、位置环比例增益以及速度环比例增益这4个属性描述。

表1 3个数据集的简要描述Table 1 A brief description of the three data sets

应用有向无环图方法，得到3个数据集的初始操作表单，如表2所示，由此重新排列节点顺序，得到基于分离性测度的有向无环图DAGsm的拓扑结构(图3)。以双螺杆挤出机数据集为例，顶层根节点为 SVM1－3，第二层节点为 SVM2－3、SVM1－4，第三层节点为 SVM4－3、SVM2－4、SVM1－2，最底层叶节点为 D13、D14、D12、D11。

表2 3个数据集的初始操作表单Table 2 The initial operation list of the three data sets

实验采用两种方法:第一种是“训练测试法”，即将数据集分成训练集和测试集，分别用来进行训练和测试，算法的准确率等于M/N，其中N为测试集样本数，M为得到正确分类的测试样本数(表3);第二种是“交叉验证法”，即将数据集随机分成几等份，其中的一份作为测试集，余下的数据合成训练集，算法的准确率为多次训练测试的平均值(表4，将总样本分为3等份的3折交叉验证)。同时，在相同的软硬件环境下记录各算法的平均运行时间，以比较其性能(表5)。

表3 4种算法的测试精确度Table 3 The test accuracies of 4 motheds

表4 4种算法的3折交叉验证平均精度Table 4 The average accuracies of methods by 3-fold cross

表5 4种算法的执行时间Table 5 The execution times of 4 methods/s

图3 3个数据集的DAGsm拓扑结构Fig.3 The DAGsm Topological Structure of the three data sets

与“一对多”算法和“一对一”算法相比，有向无环图能解决不可分区域问题，具有更高的预测精确度，而且只需使用较少的二元支持向量机子分类器，执行速度也比“一对多”算法和“一对一”算法都快，因此具有更好的泛化性能。基于分离性测度的有向无环图DAGsm，通过引入基于类分布的类间分离性测度，初始化操作表单，重新排列节点顺序，构造有向无环图的拓扑结构，较标准DAG、“一对多”和“一对一”算法均得到更好的预测效果。

在表6中，以伺服电机系统数据集为例记录了各子分类器在3折交叉验证后的分类误差均值及标准差。由于被子分类器正确分类的样本仍有可能在最后的投票中被错误地标定为其它类别，而被子分类器错误分类的样本也有可能在最后的投票中被纠回到正确的分类，所以不同的统计方法往往得到不同的分类误差。鉴于实验的目的是为了反映各分类方法相对各子分类器的性能改善，因此我们采用各子分类器错误分类的样本数除以该子分类器所涉及到的样本总数来表示分类误差，并不计入由于其他子分类器的错误投票所导致的错误分类。从具体的统计数据来看，虽然子分类器处理的对象不一致，但平均分类误差仍然是所提方法最佳;而更小的标准差也说明各子分类器的平均性能一致性更好。

表6 对伺服电机系统进行3折交叉验证Table 6 3-fold cross validation for servo motor system

4 结语

本文从支持向量机在故障诊断与分类方面的应用出发，提出并分析研究了一种多类支持向量机分类算法。该算法的基本思路是，考虑到传统算法的局限，为了得到更高的推广性能，引入基于类分布的类间分离性测度，估计训练数据间的分布性质，重新组合有向无环图的节点顺序，应用支持向量机进行二元分类，得到一个多元支持向量机分类器。该算法与一般的“一对多”和“一对一”算法相比，其主要特点是，有向无环图能解决不可分区域问题，具有更高的预测精确度，且只需使用较少的二元支持向量机子分类器，具有较快的执行速度和更好的泛化性能。为了验证算法的有效性，本文利用双螺杆挤出机故障、柴油机排气门故障和伺服电机系统分类等3个数据集，利用所提算法进行了数值仿真研究，仿真结果表明该算法对3种典型故障诊断数据均可达到更好的性能和更高的精度以及更快的运行速度。将该算法用于实际系统，探讨并解决其应用中存在的问题，是下一步重点研究内容。

［1］ YAN Weiwu，SHAO Huihe.Application of support vector machine nonlinear classifier to fault diagnosis［C］//Proceedings of the 4thWorld Congress on Intelligent Control and Automation，June 10－14，2002，Shanghai，China.2002(4):2697 －2700.

［2］ LI Ye，CAI Yunze，YIN Rupo，et al.Fault diagnosis based on support vector machine ensemble［C］//Proceedings of the 4th International Conference on Machine Learning and Cybernetics，August 18－21，2005，Guangzhou，China.2005:3309－3314.

［3］ VAPNIK V N.An overview of statistical learning theory［J］.IEEE Transactions on Neural Networks，1999，10(5):88 －99.

［4］ WANG Xizhao，LU Mingzhu，HUO Jianbing.Fault diagnosis of power transformer based on large margin learning classifier［C］//Proceedings of the 5thInternational Conference on Machine Learning and Cybernetics，August 13 － 16，2006，Dalian，China.2006:2886－2891.

［5］ HSU ChihWei，LIN ChihJen.A comparison of methods for multiclass support vector machines［J］.IEEE Transactions on Neural Networks，2002，13(2):415 －425.

［6］ WANG Xiaodan，SHI Zhaohui，WU Chongming，et al.An improved algorithm for decision-tree-based SVM［C］//Proceedings of the 6thWorld Congress on Intelligent Control and Automation，June 21 －23，2006，Dalian，China.2006:4234 －4238.

［7］ FUMITAKE Takahashi，SHIGEO Abe.Decision-tree-based multiclass support vector machines［C］//Proceedings of the 9thInternational Conference on Neural Information Processing.2002:1418－1422.

［8］ FENG Jun，CHEN Dong E.Handwritten similar Chinese characters recognition based on multi-class pair-wise support vector machines［C］//Proceedings of the 4thInternational Conference on Machine Learning and Cybernetics，August 18－21，2005，Guangzhou，China.2005:4405－4409.

［9］ MERZ C J，MURPHY P M.UCI Repository of machine learning databases.Department of Information and Computer Science，University of California，Irvine，1998，http://www.ics.uci.edu/～mlearn/MLRepository.html.

(编辑:于智龙)

Multi-class support vector machine based on directed acyclic graph

WANG Yan， CHEN Huan-huan， SHEN Yi
(School of Astronautics，Harbin Institute of Technology，Harbin 150001，China)

Support vector machine based on directed acyclic graph(DAG)was proposed for multi-class classification and applied to multi-class fault diagnosis problems.Considering DAG being equivalent to a list operation，and the classification performance depending on the nodes’sequence in the graph，a classification measure based on the distribution of multi-class data was introduced.This method used separability measure between class to estimate distribution character of each class，established the initialization operation list，and organized all sample classes in the list according to certain sequence.The topology structure of DAG based on separability measure was constructed by rearranging the nodes’sequence in the graph.To testify the effectiveness of the proposed method，numerical simulations were conducted on three datasets compared with conventional methods.The results show that，the proposed method has better performance and higher generalization ability.

support vector machine;directed acyclic graph;separability measure;fault diagnosis

TP 18

A

1007－449X(2011)04－0085－05

2010－11－22

国家自然科学基金(61071182，60874054);高等学校博士学科点专项科研基金(20092302110037)

王 艳(1959—)，女，高级工程师，硕士生导师，研究方向为模式识别、智能控制;

陈欢欢(1984—)，女，硕士研究生，研究方向为故障诊断、优化算法;

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