一種改進(jìn)的偏二叉樹孿生支持向量機(jī)算法及其應(yīng)用

姜佳輝,包永強(qiáng)2,邵 琪

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

0 引言

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

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

采用二叉樹進(jìn)行的優(yōu)點(diǎn)在于不存在不可分區(qū)域，且訓(xùn)練分類器時(shí)所需的訓(xùn)練樣本較少，訓(xùn)練時(shí)長(zhǎng)較少，分類效率較高。缺點(diǎn)在于，二叉樹分類結(jié)構(gòu)存在“誤差累積”現(xiàn)象，即若在某個(gè)節(jié)點(diǎn)上發(fā)生誤分類，則這種錯(cuò)誤會(huì)延續(xù)下去，該節(jié)點(diǎn)的后續(xù)節(jié)點(diǎn)分類將失去意義。因此，如何構(gòu)建出一個(gè)較好的二叉樹結(jié)構(gòu)，已成為當(dāng)前學(xué)者們研究的一個(gè)熱點(diǎn)。文獻(xiàn)[7]通過計(jì)算各類別間的最短距離，以其進(jìn)一步計(jì)算出各樣本的類間平均距離從而提出了一種新的二叉樹生成算法，但是該算法并未考慮到類內(nèi)樣本的分布；文獻(xiàn)[8]定義了一種基于類內(nèi)樣本分布的可分性測(cè)度，并將其引入二叉樹SVM的構(gòu)建中，但其僅關(guān)注類內(nèi)樣本的分布情況，忽略了類間樣本的聯(lián)系?；诖耍疚奶岢隽艘环N改進(jìn)的偏二叉樹TWSVM算法，定義了一種融合了類間距離和類內(nèi)分布兩種可分性測(cè)度指標(biāo)的混合分離性測(cè)度β，用以最大限度地克服誤差累積現(xiàn)象，以此來確定最優(yōu)分類二叉樹TWSVM結(jié)構(gòu)。以風(fēng)電機(jī)組齒輪箱作為診斷對(duì)象，提取了其一些典型故障下振動(dòng)信號(hào)的時(shí)頻域特征，并利用本文所述的改進(jìn)二叉樹TWSVM算法實(shí)現(xiàn)對(duì)齒輪箱常見多類故障的診斷。

1 孿生支持向量機(jī)

對(duì)于任一非線性二分類問題，孿生支持向量機(jī)可歸結(jié)為求解如下兩個(gè)二次規(guī)劃問題：

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(·)表示核函數(shù)，e1和e2為相應(yīng)維數(shù)的單位向量，c1，c2為懲罰系數(shù)，C=[AB]T，ω和b分別表示所得最優(yōu)超平面的法向量和偏置，q為松弛變量。通過拉格朗日求解法求解式(1)、(2)，最終得到如下兩個(gè)超平面K(xT,CT)w(1)+b(1)=0，K(xT,CT)w(2)+b(2)=0。對(duì)于一個(gè)新的測(cè)試樣本，其距離哪個(gè)超平面近就會(huì)被歸為對(duì)應(yīng)類，即決策函數(shù)為[9-10]：

(3)

2 改進(jìn)的偏二叉樹TWSVM多分類算法

2.1 偏二叉樹TWSVM

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

2.2 混合分離性測(cè)度

(4)

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

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

(5)

則類間樣本距離計(jì)算式如下：

(6)

文獻(xiàn)[12]指出，類內(nèi)樣本距離D反映了類內(nèi)樣本的分布，D值越大，則類內(nèi)樣本分布越廣，應(yīng)當(dāng)率先被分離出來；類間樣本距離D’反映了不同類的可分離程度，該值越大，則類間可分性程度越好，越當(dāng)被率先分離出來。雖然類內(nèi)樣本距離和類間樣本距離是針對(duì)可分性度量的兩種不同評(píng)價(jià)標(biāo)準(zhǔn)，但兩者對(duì)于類可分性的影響程度，及其是否存在著某種內(nèi)在聯(lián)系，目前還未有相關(guān)理論分析?；诖耍疚耐ㄟ^引入權(quán)值思想將兩者結(jié)合，定義了一種類的混合分離性測(cè)度β，對(duì)于任意兩類i,j，其β的定義如下式所示：

(7)

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

1)設(shè)共有n類樣本。初始化參數(shù)c1，c2，g及W，載入樣本集其對(duì)應(yīng)標(biāo)簽集，根據(jù)K折交叉驗(yàn)證的方法將各類樣本集分別對(duì)應(yīng)劃分為訓(xùn)練集和測(cè)試集；

2)按照式(5)、(6)、(7)分別計(jì)算各類訓(xùn)練樣本兩兩之間的混合分離性測(cè)度值，并將所得值按從小到大進(jìn)行排列。構(gòu)造第一個(gè)二叉樹節(jié)點(diǎn)時(shí)，將β值最小對(duì)應(yīng)的兩類訓(xùn)練樣本(記為C1、C2)作為正負(fù)類樣本進(jìn)行訓(xùn)練，得到第n-1層葉子節(jié)點(diǎn)，然后合并該層節(jié)點(diǎn)的兩類樣本作為一類，分別計(jì)算其與其余n-2類樣本的混合分離性測(cè)度值，取值最小的一類(記為C3)再與其作為正負(fù)樣本進(jìn)行訓(xùn)練，依此類推。構(gòu)造二叉樹節(jié)點(diǎn)的問題即可歸結(jié)為如式(1)、(2)所示求取TWSVM兩個(gè)非平行超平面的問題。重復(fù)上述過程，直至得到根節(jié)點(diǎn)，二叉樹建立完成，由此可以保證位于根節(jié)點(diǎn)的TWSVM分類器能夠?qū)⒖煞中宰詈玫囊活惵氏确蛛x出來。具體二叉樹構(gòu)建過程示意圖如圖1所示，按照由下至上的順序構(gòu)建整個(gè)PBT-TWSVM分類器；

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

4)分別更換訓(xùn)練集和測(cè)試集，重復(fù)步驟2)、3)共K次，取K次所得分類準(zhǔn)確率的平均值作為最終適應(yīng)度函數(shù)Fitness。

圖1 PBT-TWSVM示意圖

2.3 本文算法描述

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

圖2 本文算法流程圖

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

2.4 仿真分析

為了驗(yàn)證本文提出的基于混合分離性測(cè)度的PBT-TWSVM算法在非線性多分類問題中的性能，采用UCI標(biāo)準(zhǔn)數(shù)據(jù)庫(kù)中的Auto-mpg、Balance兩個(gè)標(biāo)準(zhǔn)數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)，仿真實(shí)驗(yàn)均在PC機(jī)上(內(nèi)存為256 MB、CPU為800 MHz)基于Matlab R2015a環(huán)境實(shí)現(xiàn)。表1為各數(shù)據(jù)集的樣本個(gè)數(shù)、維數(shù)及類別數(shù)說明。

表1 測(cè)試數(shù)據(jù)集信息

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

表2 不同算法對(duì)測(cè)試數(shù)據(jù)分類結(jié)果

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

3 實(shí)驗(yàn)分析

3.1 平臺(tái)搭建

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

圖3 風(fēng)電機(jī)組齒輪箱故障模擬試驗(yàn)臺(tái)

采集到的各工況下的原始振動(dòng)信號(hào)如圖4所示。

圖4 齒輪箱各工況下原始振動(dòng)信號(hào)

3.2 齒輪箱振動(dòng)信號(hào)特征提取

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

表3 時(shí)頻特征向量列表

3.3 齒輪箱故障工況識(shí)別

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

圖5 PSO適應(yīng)度曲線圖

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

表4 不同算法識(shí)別結(jié)果對(duì)比

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

4 結(jié)論

本文結(jié)合孿生支持向量機(jī)和二叉樹兩種算法的優(yōu)勢(shì)，分析了二叉樹孿生支持向量機(jī)多分類算法的原理及特點(diǎn)，提出了一種改進(jìn)的PBT-TWSVM多分類算法，定義了一種加權(quán)樣本類內(nèi)距離和類間距離的混合分離性測(cè)度β，并運(yùn)用PSO算法對(duì)權(quán)重及TWSVM參數(shù)進(jìn)行了優(yōu)化，以各最優(yōu)化后的參數(shù)的確立了最終的PBT-TWSVM分類器模型；

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