王艷， 陳歡歡， 沈毅

(哈爾濱工業(yè)大學(xué)航天學(xué)院，黑龍江哈爾濱 150001)

有向無環(huán)圖的多類支持向量機(jī)分類算法

王艷， 陳歡歡， 沈毅

(哈爾濱工業(yè)大學(xué)航天學(xué)院，黑龍江哈爾濱 150001)

為研究基于有向無環(huán)圖的支持向量機(jī)分類算法以及在故障診斷問題中的應(yīng)用，考慮到有向無環(huán)圖的結(jié)構(gòu)運(yùn)算相當(dāng)于一個(gè)表操作，且分類結(jié)果依賴于有向無環(huán)圖中節(jié)點(diǎn)的排列順序，提出一種分類算法，該算法引入基于類分布的類間分離性測(cè)度，估計(jì)各類訓(xùn)練數(shù)據(jù)間的分布性質(zhì)，建立初始操作表單，將樣本所有可能的類別按照一定順序排列在表單中，從而重新組合有向無環(huán)圖中的節(jié)點(diǎn)順序，構(gòu)造基于分離性測(cè)度的有向無環(huán)圖的拓?fù)浣Y(jié)構(gòu)。通過對(duì)3個(gè)典型數(shù)據(jù)集的數(shù)值仿真研究，結(jié)果表明所提算法的性能優(yōu)于傳統(tǒng)算法。

支持向量機(jī);有向無環(huán)圖;分離性測(cè)度;故障診斷

0 引言

故障診斷與分類一直是模式識(shí)別中的重要研究領(lǐng)域。近年來，由Vapnik與其同事提出來的支持向量機(jī)(support vector machine，SVM)作為一個(gè)強(qiáng)有力的機(jī)器學(xué)習(xí)方法，已成功地應(yīng)用于模式識(shí)別尤其是故障診斷與分類等領(lǐng)域［1－2］。其采用基于統(tǒng)計(jì)學(xué)習(xí)理論(statistical learning theory，SLT)的結(jié)構(gòu)風(fēng)險(xiǎn)最小化原則(structural risk minimization principle，SRMP)，能有效地解決非線性、有限樣本和高維等問題，通?？梢蕴峁┝己玫膶W(xué)習(xí)能力和推廣能力［3－4］。

支持向量機(jī)最初是針對(duì)二元分類問題提出來的，不能直接用于多元分類問題，而大部分的故障診斷問題為多元分類情況，如何有效地把它擴(kuò)展到多類情況是一個(gè)正在研究的熱點(diǎn)問題［5］。

1 有向無環(huán)圖

目前多元分類器的擴(kuò)展主要是通過組合一系列二元支持向量機(jī)分類器［6］，這種方法主要有兩個(gè)常用算法:1)“一對(duì)多”算法，該算法將其中一個(gè)類別的樣本作為一類，其他不屬于該類別的樣本作為一類，依次進(jìn)行訓(xùn)練;2)“一對(duì)一”算法，該算法組合所有可能的二元分類器，每次對(duì)其中的兩個(gè)類別進(jìn)行訓(xùn)練。然而這兩個(gè)算法在實(shí)際應(yīng)用中也有局限性，舉例來說，任何一個(gè)分類器的錯(cuò)誤分類都會(huì)導(dǎo)致不可分區(qū)域的存在，而且以上兩個(gè)多元分類器的訓(xùn)練速度將隨著訓(xùn)練樣本數(shù)或類別數(shù)的增多而變慢［7］。

對(duì)于“一對(duì)一”算法，Platt等提出了一個(gè)新的學(xué)習(xí)架構(gòu)，即有向無環(huán)圖(directed acyclic graph，DAG)［8］。在對(duì)多個(gè)“一對(duì)一”二元子分類器進(jìn)行組合的過程中，引入圖論中有向無環(huán)圖的思想，將多個(gè)二元分類器組合成多元分類器。對(duì)于一個(gè)m元的分類問題，DAG共含有m(m－1)/2個(gè)節(jié)點(diǎn)，對(duì)應(yīng)m(m－1)/2個(gè)二元分類器，分布于m層結(jié)構(gòu)中。其拓?fù)浣Y(jié)構(gòu)如圖1所示，頂層只含有1個(gè)節(jié)點(diǎn)，稱為根節(jié)點(diǎn)，第二層含有2個(gè)節(jié)點(diǎn)，依次類推，第i層含有i個(gè)節(jié)點(diǎn)，最底層含有m個(gè)葉節(jié)點(diǎn)，其中第j層的第i個(gè)節(jié)點(diǎn)指向第j+1層的第i個(gè)和第i+1個(gè)節(jié)點(diǎn)。

圖1 有向無環(huán)圖結(jié)構(gòu)圖Fig.1 The structure chart of directed acyclic graph

對(duì)于給定的輸入樣本X，從根節(jié)點(diǎn)出發(fā)，計(jì)算每個(gè)節(jié)點(diǎn)的決策函數(shù)值，若為1，則從左邊進(jìn)入下一節(jié)點(diǎn)，若為－1，則從右邊進(jìn)入下一節(jié)點(diǎn)，然后計(jì)算下一節(jié)點(diǎn)的值，依此類推，在最后一層葉節(jié)點(diǎn)處的輸出就表示了X所屬的類別。與樹狀結(jié)構(gòu)不同，DAG結(jié)構(gòu)具有冗余性，同一類別的樣本，分類路徑可能不同，與一般的決策樹方法相比，更易于計(jì)算，且學(xué)習(xí)效果也更好。

DAG結(jié)構(gòu)運(yùn)算相當(dāng)于一個(gè)表操作，在初始狀態(tài)下，表中包含了所有的類，在分類時(shí)，每次對(duì)表單中的首尾兩個(gè)類別進(jìn)行比較，排除掉樣本最不可能屬于的類別，并刪除表中的一個(gè)類，從而使表單中的類別數(shù)減少1，依此類推，那么當(dāng)經(jīng)過m－1次排除之后，表單中唯一剩下的一類即為該樣本所屬的類別。

DAG最后輸出的分類結(jié)果對(duì)圖中節(jié)點(diǎn)的排列順序的依賴性很大，不同的節(jié)點(diǎn)的排列順序會(huì)導(dǎo)致部分樣本的決策路徑不同，從而直接影響分類效果。本文通過引入基于類分布的類間分離性測(cè)度，估計(jì)各類訓(xùn)練數(shù)據(jù)間的分布性質(zhì)，建立初始操作表單，將樣本所有可能的類別按照一定順序排列在表單中，從而重新組合有向無環(huán)圖的節(jié)點(diǎn)順序。

2 分類算法

在對(duì)訓(xùn)練數(shù)據(jù)評(píng)估各類間的分離度時(shí)，通常采用歐氏距離衡量類間分離性測(cè)度［7］。如圖2所示，兩類間的距離相等，但離散度卻存在很大差異。由圖可見，歐氏距離并不能很全面客觀地代表其類間的分離度，這直接影響了在分類建模中的難易程度，因此引入一種基于類分布的類間分離性測(cè)度來評(píng)定各類間的分離性質(zhì)。

圖2 類間分離性測(cè)度示意圖Fig.2 The diagrammatic illustration of separability measure between classes

考慮具有m個(gè)類別的訓(xùn)練數(shù)據(jù)X={X1，X2，…，Xm}，第i類和第j類之間的分離性測(cè)度smij(i，j=1，2，…，m)定義為

其中:dij表示第i類和第j類之間的距離;Ck(k=1，2，…，m)是各類訓(xùn)練樣本的均值中心;lk為類Xk中的樣本個(gè)數(shù);σk表示第k類的標(biāo)準(zhǔn)差，表明了第k類的分布情況。

計(jì)算第i類和第j類間的分離性測(cè)度smij(i，j=1，2，…，m)，得到一個(gè)m×m階的類間分離性測(cè)度矩陣，其中第k(k=1，2，…，m)行表明了第k類的分布性質(zhì)。由此構(gòu)造初始操作表單:

1)對(duì)于每一類，都存在m－1個(gè)與其他類的分離性測(cè)度值。首先，分別對(duì)每一類的這些值按從小到大的順序進(jìn)行排列，并重新編號(hào)。例如，第k類與其他類間分離性測(cè)度值為 smkt(t=1，2，…，m，t≠k)，按從小到大的順序重新排列為≤≤…≤。

3)最后得到所有類別的排列 s1，s2，…，sm，此處sk∈{1，2，…，m}，k=1，2，…，m 為類標(biāo)號(hào)。根據(jù)類標(biāo)號(hào)的排序，建立初始操作表單［s1，s2，…，sm］，則表單中的首尾兩個(gè)類別的分布性質(zhì)具有最大差異，以此類推，并由此重新排列節(jié)點(diǎn)順序，得到有向無環(huán)圖的拓?fù)浣Y(jié)構(gòu)。

3 仿真研究及結(jié)果分析

將基于有向無環(huán)圖的支持向量機(jī)應(yīng)用于多元分類問題。實(shí)驗(yàn)選取機(jī)器學(xué)習(xí)領(lǐng)域中的3個(gè)典型測(cè)試數(shù)據(jù)集［9］來進(jìn)行測(cè)試，所有樣本數(shù)據(jù)都分成訓(xùn)練樣本和測(cè)試樣本。表1簡要描述了這3個(gè)數(shù)據(jù)集:1)雙螺桿擠出機(jī)故障數(shù)據(jù)集，包含正常狀態(tài)、雙螺桿的止推軸承潤滑不夠以及兩根螺桿之間的間隙出現(xiàn)了嚴(yán)重偏差、機(jī)頭雜質(zhì)過多造成機(jī)頭壓力偏高4種狀態(tài)(分別由 D11、D12、D13、D14 表示)，數(shù)據(jù)屬性為料筒的溫度(沿料筒分布的5個(gè)熱電偶采集到的5個(gè)點(diǎn)的溫度)、油泵電壓和主電機(jī)電流;2)柴油機(jī)故障數(shù)據(jù)集，包含正常狀態(tài)、進(jìn)排氣門間隙極小、進(jìn)排氣門間隙極大、排氣門輕度漏氣、排氣門嚴(yán)重漏氣5種狀態(tài)(分別用 D21、D22、D23、D24、D25 表示)下的缸蓋表面振動(dòng)信號(hào)經(jīng)小波變換處理后所得的數(shù)據(jù)。3)UCI機(jī)器學(xué)習(xí)公用數(shù)據(jù)庫的伺服電機(jī)系統(tǒng)數(shù)據(jù)集，該系統(tǒng)輸出值是調(diào)整時(shí)間，即系統(tǒng)處在一個(gè)設(shè)定的位置時(shí)，對(duì)階躍指令響應(yīng)并運(yùn)行到位的時(shí)間，根據(jù)該時(shí)間數(shù)值，可均等劃分為6種類別(分別用D31、D32、D33、D34、D35、D36 表示)，數(shù)據(jù)集包含167 個(gè)樣本，分別由電機(jī)類型、導(dǎo)軌螺紋類型、位置環(huán)比例增益以及速度環(huán)比例增益這4個(gè)屬性描述。

表1 3個(gè)數(shù)據(jù)集的簡要描述Table 1 A brief description of the three data sets

應(yīng)用有向無環(huán)圖方法，得到3個(gè)數(shù)據(jù)集的初始操作表單，如表2所示，由此重新排列節(jié)點(diǎn)順序，得到基于分離性測(cè)度的有向無環(huán)圖DAGsm的拓?fù)浣Y(jié)構(gòu)(圖3)。以雙螺桿擠出機(jī)數(shù)據(jù)集為例，頂層根節(jié)點(diǎn)為 SVM1－3，第二層節(jié)點(diǎn)為 SVM2－3、SVM1－4，第三層節(jié)點(diǎn)為 SVM4－3、SVM2－4、SVM1－2，最底層葉節(jié)點(diǎn)為 D13、D14、D12、D11。

表2 3個(gè)數(shù)據(jù)集的初始操作表單Table 2 The initial operation list of the three data sets

實(shí)驗(yàn)采用兩種方法:第一種是“訓(xùn)練測(cè)試法”，即將數(shù)據(jù)集分成訓(xùn)練集和測(cè)試集，分別用來進(jìn)行訓(xùn)練和測(cè)試，算法的準(zhǔn)確率等于M/N，其中N為測(cè)試集樣本數(shù)，M為得到正確分類的測(cè)試樣本數(shù)(表3);第二種是“交叉驗(yàn)證法”，即將數(shù)據(jù)集隨機(jī)分成幾等份，其中的一份作為測(cè)試集，余下的數(shù)據(jù)合成訓(xùn)練集，算法的準(zhǔn)確率為多次訓(xùn)練測(cè)試的平均值(表4，將總樣本分為3等份的3折交叉驗(yàn)證)。同時(shí)，在相同的軟硬件環(huán)境下記錄各算法的平均運(yùn)行時(shí)間，以比較其性能(表5)。

表3 4種算法的測(cè)試精確度Table 3 The test accuracies of 4 motheds

表4 4種算法的3折交叉驗(yàn)證平均精度Table 4 The average accuracies of methods by 3-fold cross

表5 4種算法的執(zhí)行時(shí)間Table 5 The execution times of 4 methods/s

圖3 3個(gè)數(shù)據(jù)集的DAGsm拓?fù)浣Y(jié)構(gòu)Fig.3 The DAGsm Topological Structure of the three data sets

與“一對(duì)多”算法和“一對(duì)一”算法相比，有向無環(huán)圖能解決不可分區(qū)域問題，具有更高的預(yù)測(cè)精確度，而且只需使用較少的二元支持向量機(jī)子分類器，執(zhí)行速度也比“一對(duì)多”算法和“一對(duì)一”算法都快，因此具有更好的泛化性能。基于分離性測(cè)度的有向無環(huán)圖DAGsm，通過引入基于類分布的類間分離性測(cè)度，初始化操作表單，重新排列節(jié)點(diǎn)順序，構(gòu)造有向無環(huán)圖的拓?fù)浣Y(jié)構(gòu)，較標(biāo)準(zhǔn)DAG、“一對(duì)多”和“一對(duì)一”算法均得到更好的預(yù)測(cè)效果。

在表6中，以伺服電機(jī)系統(tǒng)數(shù)據(jù)集為例記錄了各子分類器在3折交叉驗(yàn)證后的分類誤差均值及標(biāo)準(zhǔn)差。由于被子分類器正確分類的樣本仍有可能在最后的投票中被錯(cuò)誤地標(biāo)定為其它類別，而被子分類器錯(cuò)誤分類的樣本也有可能在最后的投票中被糾回到正確的分類，所以不同的統(tǒng)計(jì)方法往往得到不同的分類誤差。鑒于實(shí)驗(yàn)的目的是為了反映各分類方法相對(duì)各子分類器的性能改善，因此我們采用各子分類器錯(cuò)誤分類的樣本數(shù)除以該子分類器所涉及到的樣本總數(shù)來表示分類誤差，并不計(jì)入由于其他子分類器的錯(cuò)誤投票所導(dǎo)致的錯(cuò)誤分類。從具體的統(tǒng)計(jì)數(shù)據(jù)來看，雖然子分類器處理的對(duì)象不一致，但平均分類誤差仍然是所提方法最佳;而更小的標(biāo)準(zhǔn)差也說明各子分類器的平均性能一致性更好。

表6 對(duì)伺服電機(jī)系統(tǒng)進(jìn)行3折交叉驗(yàn)證Table 6 3-fold cross validation for servo motor system

4 結(jié)語

本文從支持向量機(jī)在故障診斷與分類方面的應(yīng)用出發(fā)，提出并分析研究了一種多類支持向量機(jī)分類算法。該算法的基本思路是，考慮到傳統(tǒng)算法的局限，為了得到更高的推廣性能，引入基于類分布的類間分離性測(cè)度，估計(jì)訓(xùn)練數(shù)據(jù)間的分布性質(zhì)，重新組合有向無環(huán)圖的節(jié)點(diǎn)順序，應(yīng)用支持向量機(jī)進(jìn)行二元分類，得到一個(gè)多元支持向量機(jī)分類器。該算法與一般的“一對(duì)多”和“一對(duì)一”算法相比，其主要特點(diǎn)是，有向無環(huán)圖能解決不可分區(qū)域問題，具有更高的預(yù)測(cè)精確度，且只需使用較少的二元支持向量機(jī)子分類器，具有較快的執(zhí)行速度和更好的泛化性能。為了驗(yàn)證算法的有效性，本文利用雙螺桿擠出機(jī)故障、柴油機(jī)排氣門故障和伺服電機(jī)系統(tǒng)分類等3個(gè)數(shù)據(jù)集，利用所提算法進(jìn)行了數(shù)值仿真研究，仿真結(jié)果表明該算法對(duì)3種典型故障診斷數(shù)據(jù)均可達(dá)到更好的性能和更高的精度以及更快的運(yùn)行速度。將該算法用于實(shí)際系統(tǒng)，探討并解決其應(yīng)用中存在的問題，是下一步重點(diǎn)研究內(nèi)容。

［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

國家自然科學(xué)基金(61071182，60874054);高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金(20092302110037)

王 艷(1959—)，女，高級(jí)工程師，碩士生導(dǎo)師，研究方向?yàn)槟Ｊ阶R(shí)別、智能控制;

陳歡歡(1984—)，女，碩士研究生，研究方向?yàn)楣收显\斷、優(yōu)化算法;

沈 毅(1965—)，男，博士，教授，博士生導(dǎo)師，研究方向?yàn)榭刂葡到y(tǒng)故障診斷、飛行器控制。