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

王艷， 陳歡歡， 沈毅

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

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

王艷， 陳歡歡， 沈毅

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

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

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

0 引言

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

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

1 有向無環(huán)圖

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

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

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

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

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

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

2 分類算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)語

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

王 艷(1959—)，女，高級工程師，碩士生導(dǎo)師，研究方向為模式識別、智能控制;

陳歡歡(1984—)，女，碩士研究生，研究方向為故障診斷、優(yōu)化算法;

沈 毅(1965—)，男，博士，教授，博士生導(dǎo)師，研究方向為控制系統(tǒng)故障診斷、飛行器控制。