一種改進的偏二叉樹孿生支持向量機算法及其應用

姜佳輝,包永強2,邵 琪

(1.南京工程學院 電力工程學院，南京 211167; 2.南京工程學院 信息與通信工程學院，南京 211167)

0 引言

支持向量機(Support Vector Machines,SVM)是Vapnik等提出的針對于解決分類及回歸問題的統計學習理論[1]。與一些傳統的機器學習方法不同，SVM較好地解決了諸如求取局部極小值、模型選擇與過學習問題等。但是，SVM仍存在著一些問題，如算法復雜度高，耗時長等。孿生支持向量機(Twin Support Vector Machines,TWSVM)是一種基于SVM上發展而來的新算法，其在保持經典支持向量機原有優勢的基礎上，運算速度明顯快于后者。孿生支持向量機通過求解兩個二次規劃問題構造兩個非平行超平面，由于每個二次規劃問題的約束條件數目為經典支持向量機的一半，從而理論上其訓練速度約為經典支持向量機的4倍[2]。

傳統SVM和TWSVM最初都是為了解決二分類問題而提出的，而非直接針對于多分類問題。然而，現實中絕大多數問題通常是多分類問題，因此，針對多分類TWSVM的研究具有重要的現實意義。目前，國內外學者在多分類TWSVM的研究方面也已取得了一些進展。“一對多(one-versus-all,OVA)”作為一種最早被用于將二分類問題擴展為多分類的策略[3]，其核心思想是通過求解K個二次規劃問題(quadratic programming problem,QPP)得到K個超平面，算法具有簡單易實現的優點，但會造成數據的不平衡的現象，并存在著不可分區域；隨后Kerr等人提出了“一對一(one-versus-one,OVO)”策略[4]，對于K類分類問題，該算法在任意兩類樣本之間構造一個基于TWSVM的二分類器，需構造的二分類器總數為K(K-1)/2個。由于該算法在每個子分類器訓練時僅需用到兩個類的訓練樣本，因此較好地解決了分類過程中存在的數據不平衡問題，且加快了訓練速度；但由于其采用“投票法”作為決策策略，從而會導致存在獲得相同票數的類別，將影響最終的分類準確度；基于二叉樹的多分類孿生支持向量機(binary tree based twin support vector machine,BT-TWSVM)針對上述兩種策略中可能存在的問題而提出，對于K類分類問題，該方法先將所有類別劃分為兩個子類，訓練得到根節點子分類器；再進一步將子類劃分為兩個更小的類，訓練得到下一層分類器，以此類推，直到所有節點都只包含一個單獨類為止。BT-TWSVM分類精度高、算法復雜度低、且不存在不可分區域，因此已被廣泛應用于機械設備故障識別、圖像分類等領域[5-6]。

采用二叉樹進行的優點在于不存在不可分區域，且訓練分類器時所需的訓練樣本較少，訓練時長較少，分類效率較高。缺點在于，二叉樹分類結構存在“誤差累積”現象，即若在某個節點上發生誤分類，則這種錯誤會延續下去，該節點的后續節點分類將失去意義。因此，如何構建出一個較好的二叉樹結構，已成為當前學者們研究的一個熱點。文獻[7]通過計算各類別間的最短距離，以其進一步計算出各樣本的類間平均距離從而提出了一種新的二叉樹生成算法，但是該算法并未考慮到類內樣本的分布；文獻[8]定義了一種基于類內樣本分布的可分性測度，并將其引入二叉樹SVM的構建中，但其僅關注類內樣本的分布情況，忽略了類間樣本的聯系。基于此，本文提出了一種改進的偏二叉樹TWSVM算法，定義了一種融合了類間距離和類內分布兩種可分性測度指標的混合分離性測度β，用以最大限度地克服誤差累積現象，以此來確定最優分類二叉樹TWSVM結構。以風電機組齒輪箱作為診斷對象，提取了其一些典型故障下振動信號的時頻域特征，并利用本文所述的改進二叉樹TWSVM算法實現對齒輪箱常見多類故障的診斷。

1 孿生支持向量機

對于任一非線性二分類問題，孿生支持向量機可歸結為求解如下兩個二次規劃問題：

s.t. -(K(B,C′)w(1)+e2b(1)) +q≥e2

q≥0

(1)

s.t. (K(B,C′)w(2)+e2b(2))+q≥e1

q≥0

(2)

其中:A、B分別表示兩類待分類樣本矩陣，K(·)表示核函數，e1和e2為相應維數的單位向量，c1，c2為懲罰系數，C=[AB]T，ω和b分別表示所得最優超平面的法向量和偏置，q為松弛變量。通過拉格朗日求解法求解式(1)、(2)，最終得到如下兩個超平面K(xT,CT)w(1)+b(1)=0，K(xT,CT)w(2)+b(2)=0。對于一個新的測試樣本，其距離哪個超平面近就會被歸為對應類，即決策函數為[9-10]：

(3)

2 改進的偏二叉樹TWSVM多分類算法

2.1 偏二叉樹TWSVM

偏二叉樹孿生支持向量機(Partial Binary Tree Twin Support Vector Machine,PBT-TWSVM)的基本思想是：通過構造一個偏二叉樹結構將一個含有k個類別的分類問題轉化為k-1個兩類分類問題。在處理k分類問題時，二叉樹孿生支持向量機只需生成k-1個TWSVM分類器，小于基于OVO、OVA策略所需構造的多分類器數目(k(k-1)/2、k)[11]。同時，對于位于每個節點的TWSVM二分類器來說，所參與訓練的樣本數據數量會隨著級數的增加而減少，這使得偏二叉樹孿生支持向量機具有更快快的訓練速度和測試速度。由于二叉樹結構存在著“誤差累積”現象，因此為了提高二叉樹整體的性能，在生成偏二叉樹結構時須考慮采取更為合理的策略，即越是根節點及靠近根節點的上層節點，越應當區分出分離性較優的類。

2.2 混合分離性測度

(4)

由核函數理論知K(xm,xn)=φ(xm)·φ(xn)，進一步計算上式，得:

m,n=1,2,…,k,m≠n

(5)

則類間樣本距離計算式如下：

(6)

文獻[12]指出，類內樣本距離D反映了類內樣本的分布，D值越大，則類內樣本分布越廣，應當率先被分離出來；類間樣本距離D’反映了不同類的可分離程度，該值越大，則類間可分性程度越好，越當被率先分離出來。雖然類內樣本距離和類間樣本距離是針對可分性度量的兩種不同評價標準，但兩者對于類可分性的影響程度，及其是否存在著某種內在聯系，目前還未有相關理論分析。基于此，本文通過引入權值思想將兩者結合，定義了一種類的混合分離性測度β，對于任意兩類i,j，其β的定義如下式所示：

(7)

式中，W為權值系數，0≤W≤1。式(7)反映了兩種評價標準對類別可分性共同影響又相互制約的關系。由于本文所述算法中二叉樹層次結構的確定以β為標準，顯然不同的W的取值將同時改變β，繼而改變二叉樹的層次結構，因此確定W的具體取值是影響二叉樹性能，也是影響最終分類精度的關鍵。對于W值的確定，本文引入粒子群優化算法(Particle Swarm Optimization,PSO)，文獻[13]指出，TWSVM中的懲罰系數c1，c2和高斯核函數中的參數g同樣對最終的分類精度有著較大的影響，因此為了使分類器性能達到最優，最終確定算法中共有4個待優化參數c1，c2，g，W，故在搜索空間中第i個粒子的位置表示為一個四維的向量xi={ci1,ci2,gi,Wi}。同時，算法確定以K重交叉驗證分類準確率Fitness作為適應度函數。其具體計算步驟如下：

1)設共有n類樣本。初始化參數c1，c2，g及W，載入樣本集其對應標簽集，根據K折交叉驗證的方法將各類樣本集分別對應劃分為訓練集和測試集；

2)按照式(5)、(6)、(7)分別計算各類訓練樣本兩兩之間的混合分離性測度值，并將所得值按從小到大進行排列。構造第一個二叉樹節點時，將β值最小對應的兩類訓練樣本(記為C1、C2)作為正負類樣本進行訓練，得到第n-1層葉子節點，然后合并該層節點的兩類樣本作為一類，分別計算其與其余n-2類樣本的混合分離性測度值，取值最小的一類(記為C3)再與其作為正負樣本進行訓練，依此類推。構造二叉樹節點的問題即可歸結為如式(1)、(2)所示求取TWSVM兩個非平行超平面的問題。重復上述過程，直至得到根節點，二叉樹建立完成，由此可以保證位于根節點的TWSVM分類器能夠將可分性最好的一類率先分離出來。具體二叉樹構建過程示意圖如圖1所示，按照由下至上的順序構建整個PBT-TWSVM分類器；

3)將測試樣本輸入至圖1所示二叉樹中進行判斷，待分類樣本從根節點進入，依次由上至下經過各分類器，各TWSVM分類器按照式(3)的規則進行決策，得出樣本最終所屬類別，繼而得出分類準確率；

4)分別更換訓練集和測試集，重復步驟2)、3)共K次，取K次所得分類準確率的平均值作為最終適應度函數Fitness。

圖1 PBT-TWSVM示意圖

2.3 本文算法描述

結合上面的定義分析，本文基于PSO改進的PBT-TWSVM算法具體流程如圖2所示。

圖2 本文算法流程圖

其中，適應度值的計算即按照2.2節中所述相關步驟進行。與傳統多分類SVM算法相比，本文所提出的PBT-TWSVM算法的優勢在于：(1)二叉樹TWSVM對于測試樣本無需經過所有的二值分類器，只要識別出類別即可停止運算，從而節省了測試時間；(2)利用偏二叉樹結構進行分類，其克服了“一對多”和“一對一”方法中存在不可分區域的問題，訓練時只需構造n-1個TWSVM二分類器，且訓練樣本規模隨二叉樹層數的增加而減少，減小了訓練時間；(3)另外利用混合分離性測度作為偏二叉樹的生成算法，其綜合考慮了樣本類內和類間距離對于類可分性的影響與否及具體影響程度，將越容易區分的類盡可能地優先分離出來，能夠最大程度上地克服二叉樹中的“誤差累積”現象，使算法具有更強的泛化能力，從而獲得更優的分類性能。

2.4 仿真分析

為了驗證本文提出的基于混合分離性測度的PBT-TWSVM算法在非線性多分類問題中的性能，采用UCI標準數據庫中的Auto-mpg、Balance兩個標準數據集作為實驗數據，仿真實驗均在PC機上(內存為256 MB、CPU為800 MHz)基于Matlab R2015a環境實現。表1為各數據集的樣本個數、維數及類別數說明。

表1 測試數據集信息

將如下各多分類算法：(1)傳統支持向量機(SVM)；(2)一對一孿生支持向量機(OVO TWSVM)；(3)僅考慮類間距離時的偏二叉樹孿生支持向量機(即式(7)中W=0時)；(4)本文算法，對上述算法分別進行測試并將分類的結果進行統計，對比結果如表2所示(其中測試時長單位為秒)。對于前三種算法，其對應SVM核函數亦均采用高斯核函數，并且對應參數均采用PSO優化，并均以五折交叉驗證的分類準確率作為對應適應度函數。

表2 不同算法對測試數據分類結果

從表2的結果可以看出，首先相較于傳統SVM，另外三種基于TWSVM的多分類算法在運算速率上均有顯著提高，且兩種基于偏二叉樹TWSVM的算法相較于一對一TWSVM在運算時長上也具有明顯的優勢；其次，針對數據集Auto-mpg，上述四種方法無論是運用哪種它們的分測試精度都相差無幾，而對于數據集Balance，分類準確率則有了大幅地提高，這進一步反映了偏二叉樹TWSVM算法相較于傳統SVM及1-v-1TWSVM更適合于數據量大、特征數多樣本的處理；同時可以發現，對于樣本規模較大的Balance數據集，應用本文的基于類混合分離性測度的改進PBT-TWSVM算法相較于僅考慮類間樣本距離時的PBT-TWSVM算法在分類準確率上有了顯著提高，達4.1個百分點，這說明了混合考慮類內和類間距離構建的二叉樹分類器具有更優的分類性能。

3 實驗分析

3.1 平臺搭建

為進一步驗證本文所提出算法在齒輪箱故障模式識別方面的有效性，在實驗室搭建了風電機組齒輪箱故障模擬試驗臺來作為實際驗證。其示意圖如圖3所示。實驗中，電機模擬風輪轉矩輸入，其轉速通過連接變頻器控制，以模擬風輪轉速的時變特性。輸入端連接驅動電機和聯軸器，驅動電機通過二級齒輪箱傳動后連接負載電機。在試驗臺上分別人為模擬了A、行星輪磨損、B、行星輪點蝕、C、行星輪斷齒、D、滾動軸承內圈裂紋、E、軸承保持架損壞五種不同工況，分別采集了各故障情況下的原始振動信號。實驗中，調節變頻器控制齒輪轉速為1000 r/min，系統采樣頻率設置為10 kHz，每組樣本均為連續采樣。

圖3 風電機組齒輪箱故障模擬試驗臺

采集到的各工況下的原始振動信號如圖4所示。

圖4 齒輪箱各工況下原始振動信號

3.2 齒輪箱振動信號特征提取

從圖4中的齒輪箱原始時域信號中難以提取其故障特征，因此本文中進一步采用了時頻域聯合特征提取的方法來提取有效的特征。提取出每種工況下原始樣本各100組，并采用文獻[14]中所述方法，分別提取信號的小波包能量特征、小波域倒譜能量特征以及五個時域因子作為21維聯合特征參數，具體特征列表如表3所示。

表3 時頻特征向量列表

3.3 齒輪箱故障工況識別

建立起特征樣本集：(xi,yi)，xi∈R21為樣本輸入，yi∈{1,2,3,4,5}，i=1,2,3,4，5為樣本輸出，分別代表行星輪磨損、行星輪點蝕、行星輪斷齒、軸承裂紋、保持架壞五種工況類型。利用本文算法進行故障識別，其中，交叉驗證中各類分別采用80組(80%)數據作為訓練集，20組(20%)作測試集。圖5為經本文算法所得的PSO適應度曲線圖，從圖中可知應用本文算法獲得的故障識別準確率較高，達93.75%。

圖5 PSO適應度曲線圖

為了進一步驗證本文所述算法性能上的優點，仍舊采取2.4節仿真試驗中所述三種多分類算法與本文算法進行對比驗證(對于第四種本文所述算法，W取經PSO優化所得值0.2501)。最終所得結果如表4所示。

表4 不同算法識別結果對比

從表4各算法所得實驗結果對比可知，在診斷時長方面，幾種基于孿生支持向量機的算法在運算速度上要明顯快于傳統支持向量機；在識別率方面，基于類混合分離性測度的本文算法雖然在識別用時上要略大于僅考慮類間樣本距離時的PBT-TWSVM，但在分類準確率上前者卻比后者高出了近四個百分點，這與合理的二叉樹層次結構設計有關，由此也進一步證明了本文所述改進算法在實際多分類應用問題性能方面的優越性。

4 結論

本文結合孿生支持向量機和二叉樹兩種算法的優勢，分析了二叉樹孿生支持向量機多分類算法的原理及特點，提出了一種改進的PBT-TWSVM多分類算法，定義了一種加權樣本類內距離和類間距離的混合分離性測度β，并運用PSO算法對權重及TWSVM參數進行了優化，以各最優化后的參數的確立了最終的PBT-TWSVM分類器模型；

通過UCI數據集仿真試驗，對傳統SVM、1-v-1TWSVM、基于類間距離的PBT-TWSVM和本文基于混合分離性測度的PBT-TWSVM四種算法在性能上進行了對比分析，結果表明，本文所述算法在分類準確度方面具有絕對優勢，尤其是在解決較大規模的多分類問題時，這種優勢更為明顯；將本文算法引入至風電機組齒輪箱的故障診斷中，同樣獲得了較好的故障識別效果。