有向無環圖的多類支持向量機分類算法

王艷， 陳歡歡， 沈毅

(哈爾濱工業大學航天學院，黑龍江哈爾濱 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—)，男，博士，教授，博士生導師，研究方向為控制系統故障診斷、飛行器控制。