基于最大樹聚類的多超球體一類分類算法及其應(yīng)用研究

劉麗娟 陳 果

南京航空航天大學(xué)，南京，210016

0 引言

相對(duì)于多類分類算法對(duì)樣本數(shù)量的要求較高，一類分類[1-4]方法僅僅需要一類樣本對(duì)象。如狀態(tài)監(jiān)測(cè)與故障診斷運(yùn)行狀態(tài)中，相對(duì)于大量正常狀態(tài)的樣本，異常狀態(tài)的樣本往往很少，而且表現(xiàn)出各種各樣的異常模式[5]，而其主要任務(wù)是識(shí)別狀態(tài)正常與否，采用一類分類法就能有效解決該問(wèn)題。

一類分類器僅需一類樣本通過(guò)機(jī)器學(xué)習(xí)生成一個(gè)閉合的超球體作為該類樣本的決策邊界。如果測(cè)試樣本點(diǎn)在超球體的外面，則認(rèn)為這些樣本點(diǎn)是異常樣本(野點(diǎn))，反之則判斷為正常樣本。但是在實(shí)際應(yīng)用中發(fā)現(xiàn)，即使是正常狀態(tài)的訓(xùn)練樣本，在數(shù)據(jù)分布或者結(jié)構(gòu)信息上還是會(huì)存在差異(特別是當(dāng)訓(xùn)練樣本的數(shù)據(jù)是成簇分布時(shí))，如果只按照單超球體一類分類建模，那么構(gòu)造的單個(gè)超球體不僅包圍了訓(xùn)練數(shù)據(jù)，而且還包圍了簇間的空白區(qū)域[6]，這樣一來(lái)很可能將非正常的樣本也錯(cuò)誤地判為正常樣本。雖然通過(guò)引入核函數(shù)，調(diào)節(jié)核參數(shù)(如高斯核參數(shù))可以使上述情況有所改善，但是這無(wú)法從根本上解決問(wèn)題。因此本文采用多個(gè)超球體來(lái)覆蓋訓(xùn)練樣本，研究了基于最大樹聚類的多超球體[7-8]一類分類器，分別將該方法應(yīng)用于仿真數(shù)據(jù)、UCI標(biāo)準(zhǔn)數(shù)據(jù)集以及轉(zhuǎn)子故障診斷三個(gè)實(shí)例中，并且與常用的基于單超球體的一類分類方法進(jìn)行了比較，結(jié)果表明了該方法的有效性。

1 單超球體一類分類器

一類分類器針對(duì)一類對(duì)象(如故障診斷中的正常運(yùn)行狀態(tài)，為正類)，而相對(duì)于該類對(duì)象的其他對(duì)象(如故障診斷中的非正常運(yùn)行狀態(tài)，為負(fù)類)統(tǒng)稱異常對(duì)象(野點(diǎn))。單超球體一類分類器本質(zhì)上是尋找一個(gè)能夠包含全部正類樣本的最小超球體，在球體外的點(diǎn)視為野點(diǎn)。設(shè)有一個(gè)正類樣本集{x1，x2，…，xN}，將該正類樣本集全部樣本包圍的最小球體的半徑設(shè)為R，球心設(shè)為a,為了實(shí)現(xiàn)錯(cuò)誤劃分和區(qū)域范圍之間的折中，在優(yōu)化過(guò)程中引入松弛變量，此時(shí)樣本集滿足：

(1)

定義Lagrange函數(shù)：

(2)

其中，C為懲罰因子，ξi為對(duì)應(yīng)第i個(gè)樣本的松弛變量，Λ={αi}，對(duì)應(yīng)的Lagrange系數(shù)αi≥0，γi≥0。將式(2)分別對(duì)R和α求偏微分，并令其等于0，得到相關(guān)的優(yōu)化方程如下：

(3)

引入高斯徑向基核函數(shù)K(x,y)，即

(4)

用核函數(shù)K(x,y)替代(x,y)，得到對(duì)應(yīng)的優(yōu)化方程：

(5)

實(shí)際上，根據(jù)KKT(Karush-Kuhn-Tucker)條件，大部分αi為0，只有一小部分αi>0，而與這些不為零的αi所對(duì)應(yīng)的樣本點(diǎn)決定了超球體邊界的構(gòu)成，為此，將這些樣本點(diǎn)稱為支持對(duì)象(support objection)。

對(duì)于待定狀態(tài)數(shù)據(jù)z，其到球心的距離的平方為

(6)

取任一支持對(duì)象xs，則球體半徑的平方為

(7)

依據(jù)下式可判斷z是否為正類樣本：

(8)

2 基于最大樹聚類的多超球體一類分類器

單超球體一類分類器在進(jìn)行建模時(shí)，沒(méi)有考慮到樣本間的分布結(jié)構(gòu)以及同類樣本之間存在的差異，因此本文采用多超球體來(lái)代替單超球體覆蓋訓(xùn)練樣本。圖1中，“o”表示的是正常樣本，“*”表示的是異常樣本。圖1a所示是采用單超球體覆蓋訓(xùn)練樣本的示意圖，圖1b所示是采用多超球體覆蓋訓(xùn)練樣本的示意圖。通過(guò)比較發(fā)現(xiàn)圖1b的方法較之于圖1a的方法具有更高的識(shí)別率。

(a)單超球體

(b)多超球體圖1 單超球體與多超球體比較圖

相對(duì)于單超球體的一類分類器，多超球體一類分類器首先要對(duì)訓(xùn)練樣本進(jìn)行聚類，然后對(duì)聚類后的各子類分別進(jìn)行一類支持向量機(jī)分類器學(xué)習(xí)，最后得到對(duì)應(yīng)的多個(gè)超球體一類分類模型。

2.1 聚類

本文采用最大樹[9-10]聚類算法進(jìn)行聚類。用絕對(duì)值減數(shù)法：

(9)

2.2 基于最大樹聚類的多超球體一類分類法流程

基于最大樹聚類的多超球體一類分類法具體的過(guò)程如下：

(1)對(duì)所得樣本數(shù)據(jù)進(jìn)行特征提取，得到對(duì)應(yīng)的訓(xùn)練樣本集、測(cè)試樣本集。

(2)將訓(xùn)練樣本集按最大樹聚類算法聚為多個(gè)子類。根據(jù)所聚成的子類個(gè)數(shù)將訓(xùn)練樣本集的各個(gè)子類分別進(jìn)行一類支持向量機(jī)分類器學(xué)習(xí)，得到各個(gè)子類所對(duì)應(yīng)的單超球體，各子類對(duì)應(yīng)的單超球體相組合就構(gòu)成對(duì)應(yīng)于訓(xùn)練樣本集的多超球體一類分類模型。

(3)采用得到的多超球體一類分類模型對(duì)測(cè)試樣本集進(jìn)行決策。只要存在一個(gè)超球體能包含測(cè)試樣本，就將該測(cè)試樣本視為正常類；若沒(méi)有一個(gè)超球體能包含該測(cè)試樣本，就將該測(cè)試樣本視為異常類。

圖2是其對(duì)應(yīng)的流程圖，可以看出當(dāng)訓(xùn)練樣本集聚類為一個(gè)子類(即m=1)時(shí)，所得的多超球體分類模型就是單超球體分類模型。即單超球體一類分類器可以看作是多超球體一類分類器將其對(duì)應(yīng)的訓(xùn)練樣本集聚為一個(gè)子類的特例。

圖2 算法流程

3 實(shí)驗(yàn)與應(yīng)用

3.1 仿真數(shù)據(jù)實(shí)驗(yàn)

為了驗(yàn)證基于最大樹聚類的多超球體一類分類法的可行性，本文首先選用圖1所示的具有聚類特性的仿真數(shù)據(jù)進(jìn)行驗(yàn)證。從圖1可以看出，正常樣本聚類特征明顯，傾向于聚為3個(gè)子類。

隨機(jī)選擇正常樣本的2/3作為訓(xùn)練樣本，剩余的1/3樣本作為正類測(cè)試樣本，所有的異常樣本作為負(fù)類測(cè)試樣本。采用最大樹聚類法(α取0.5)，選取聚類子類數(shù)10以內(nèi)對(duì)應(yīng)的結(jié)果，如圖3所示。根據(jù)圖3a所示的參數(shù)λ與聚類后子類數(shù)c的關(guān)系,圖3b所示的誤差平方和Je與聚類后子類數(shù)c的關(guān)系，選取參數(shù)λ=0.88，聚類后聚為3個(gè)子類，這一點(diǎn)與圖1中樣本簇分布的趨勢(shì)一致。

(a)參數(shù)λ與子類數(shù)關(guān)系(b)子類數(shù)與誤差平方和關(guān)系圖3 仿真數(shù)據(jù)聚類結(jié)果

根據(jù)聚類的結(jié)果，分別采用單超球體一類分類器和多超球體一類分類器進(jìn)行學(xué)習(xí)，兩種算法中涉及的懲罰因子C與高斯核參數(shù)σ，均采用文獻(xiàn)[12-14]中提到的粒子群優(yōu)化算法對(duì)其進(jìn)行參數(shù)自適應(yīng)優(yōu)化。兩種算法在最優(yōu)參數(shù)下得到的識(shí)別率如表1所示。其中，T為正類訓(xùn)練樣本數(shù)；T1為正類測(cè)試樣本數(shù)；T2為負(fù)類測(cè)試樣本數(shù)；N為支持向量個(gè)數(shù)；R1為正類識(shí)別率；R2為負(fù)類識(shí)別率；R為平均識(shí)別率，R=(R1+R2)/2。

表1 多超球體一類分類器與單超球體一類分類器對(duì)仿真數(shù)據(jù)的實(shí)驗(yàn)結(jié)果

表1所示結(jié)果表明，當(dāng)訓(xùn)練樣本呈聚類特征分布時(shí)，多超球體一類分類算法相對(duì)于單超球體一類分類算法具有優(yōu)越性。

3.2 UCI標(biāo)準(zhǔn)數(shù)據(jù)集實(shí)驗(yàn)

為了進(jìn)一步驗(yàn)證該算法的可行性。本文選取UCI數(shù)據(jù)庫(kù)中的Sonar這個(gè)兩類數(shù)據(jù)集產(chǎn)生兩個(gè)單類數(shù)據(jù)來(lái)驗(yàn)證。獲取的Sonar數(shù)據(jù)集包含兩類，分別記為Sonar1、Sonar2。首先對(duì)獲取的數(shù)據(jù)在信息量保持0.95的情況下，得到主成分分析(principle component analysis，PCA)特征壓縮后的兩類樣本數(shù)據(jù)。圖4a與圖4b分別是部分Sonar1和Sonar2數(shù)據(jù)取最大3維主分量的可視化分布圖，從一定程度上反映了高維數(shù)據(jù)簇分布的趨勢(shì)。

和仿真實(shí)驗(yàn)中一樣，分別針對(duì)每一類樣本集，隨機(jī)選取其中的2/3樣本作為正類訓(xùn)練樣本，剩余的1/3同類樣本作為正類測(cè)試樣本，另一類的1/3樣本作為負(fù)類測(cè)試樣本。圖5、圖6分別是對(duì)Sonar1及Sonar2采用最大樹聚類法(α取0.2)，對(duì)應(yīng)聚類子類數(shù)10以內(nèi)的結(jié)果。因此Sonar1、Sonar2分別取：參數(shù)λ=0.87、聚類后聚為3個(gè)子類以及參數(shù)λ=0.88、聚類后聚為3個(gè)子類。

(a)Sonar1 樣本三維分布圖

(b)Sonar2 樣本三維分布圖圖4 Sonar數(shù)據(jù)集的可視化分布圖

(a)參數(shù)λ與子類數(shù)關(guān)系(b)子類數(shù)與誤差平方和關(guān)系圖5 Sonar1聚類的結(jié)果

(a)參數(shù)λ與子類數(shù)關(guān)系(b)子類數(shù)與誤差平方和關(guān)系圖6 Sonar2聚類的結(jié)果

同時(shí)采用粒子群優(yōu)化算法對(duì)多超球體一類分類器與單超球體一類分類器兩種算法中涉及的懲罰因子C與高斯核參數(shù)σ進(jìn)行參數(shù)自適應(yīng)優(yōu)化，兩種算法在最優(yōu)參數(shù)下得到的識(shí)別率如表2所示。

從表2可以看出，Sonar1中多超球體的平均識(shí)別率要比單超球體的平均識(shí)別率提高了近15%，而Sonar2中兩種方法的平均識(shí)別率比較接近，這是由于Sonar2的數(shù)據(jù)聚類特征不是很明顯，這與圖4b的三維可視圖的分布是相符的。對(duì)標(biāo)準(zhǔn)數(shù)據(jù)多超球體一類分類器首先考慮了數(shù)據(jù)內(nèi)部的簇分布情況，其對(duì)正負(fù)類樣本的平均識(shí)別率總體上與單超球體一類分類器相比均有所提高，可見(jiàn)該算法的有效性。

3.3 轉(zhuǎn)子故障診斷

借助ZT-3多功能轉(zhuǎn)子實(shí)驗(yàn)臺(tái)以及DH5922動(dòng)態(tài)信號(hào)測(cè)試分析系統(tǒng)，在不同的轉(zhuǎn)速下采集了不平衡、不對(duì)中、碰摩以及油膜渦動(dòng)4類轉(zhuǎn)子故障樣本：不平衡25個(gè)，不對(duì)中22個(gè)，碰摩29個(gè)，油膜渦動(dòng)31個(gè)。

表2 多超球體一類分類器與單超球體一類分類器對(duì)標(biāo)準(zhǔn)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果

本文將實(shí)驗(yàn)提取的4類轉(zhuǎn)子故障的樣本數(shù)據(jù)進(jìn)行頻譜分析，得到信號(hào)頻譜后，對(duì)頻譜進(jìn)行歸一化處理，然后直接對(duì)頻譜數(shù)據(jù)在信息量保持率為95%的情況下進(jìn)行PCA特征壓縮。分別對(duì)壓縮后的4類特征樣本集建立其對(duì)應(yīng)的多超球體一類分類器：不平衡對(duì)應(yīng)所有類別、不對(duì)中對(duì)應(yīng)所有類別、碰摩對(duì)應(yīng)所有類別、油膜渦動(dòng)對(duì)應(yīng)所有類別。建立每個(gè)模型時(shí)，分別對(duì)每一類故障數(shù)據(jù)隨機(jī)選取其中2/3的樣本數(shù)據(jù)作為正類訓(xùn)練樣本集，將剩余的1/3樣本作為正類測(cè)試樣本集，將其他各故障的1/3樣本組合成負(fù)類測(cè)試樣本集，依照本文提出的基于最大樹聚類的多超球體一類分類器進(jìn)行學(xué)習(xí)。

圖7～圖10所示為采用最大樹聚類法(α均取0.6)，分別對(duì)四種轉(zhuǎn)子故障的訓(xùn)練樣本集進(jìn)行聚類的結(jié)果。圖7b中10個(gè)子類以內(nèi)聚為n個(gè)子類與n+1個(gè)子類間的誤差平方和的差距很小(小于0.001)，因此對(duì)于不平衡樣本，聚類后的子類個(gè)數(shù)仍為1。因此根據(jù)圖7～圖10所示聚類后參數(shù)λ與子類數(shù)c的關(guān)系、子類數(shù)c與誤差平方和Je的關(guān)系，分別對(duì)每一類故障選擇的參數(shù)λ以及所得的子類數(shù)是：不平衡——0.98，1；不對(duì)中——0.99，2；碰摩——0.99，2；油膜渦動(dòng)——0.98，2。

(a)參數(shù)λ與子類數(shù)關(guān)系(b)子類數(shù)與誤差平方和關(guān)系圖7 不平衡樣本聚類結(jié)果

(a)參數(shù)λ與子類數(shù)關(guān)系(b)子類數(shù)與誤差平方和關(guān)系圖8 不對(duì)中樣本聚類結(jié)果

(a)參數(shù)λ與子類數(shù)關(guān)系(b)子類數(shù)與誤差平方和關(guān)系圖9 碰摩樣本聚類結(jié)果

(a)參數(shù)λ與子類數(shù)關(guān)系(b)子類數(shù)與誤差平方和關(guān)系圖10 油膜渦動(dòng)樣本聚類結(jié)果

根據(jù)聚類后的結(jié)果采用本文提到的多超球體一類分類器建立模型，同時(shí)與常用的單超球體一類分類器比較了實(shí)驗(yàn)結(jié)果。同樣對(duì)兩種算法均以粒子群優(yōu)化算法優(yōu)化各算法中所涉及的懲罰因子C與高斯核參數(shù)σ。在最優(yōu)參數(shù)下所得到的識(shí)別率如表3所示。從表3的實(shí)驗(yàn)結(jié)果可知，由于不平衡樣本經(jīng)最大樹聚類后仍聚為一個(gè)子類，故對(duì)于不平衡樣本的單超球體一類分類算法即可看成是其多超球體一類分類算法的特例，兩者結(jié)果一樣。其他三類故障樣本經(jīng)聚類后均聚為兩個(gè)子類：不對(duì)中樣本采用多超球體一類分類算法不僅支持向量個(gè)數(shù)比單超球體一類分類法少了，且其對(duì)應(yīng)的識(shí)別率也提高了；碰摩樣本使用多超球體一類分類法后在支持向量個(gè)數(shù)增加的情況下，識(shí)別率有了提高；油膜渦動(dòng)樣本對(duì)應(yīng)的多超球體一類分類法雖然支持向量個(gè)數(shù)增加了，但是最后的識(shí)別率同樣達(dá)到了100%。由此可見(jiàn)，該算法相對(duì)于常用的單超球體一類分類法在識(shí)別率上表現(xiàn)了其有效性。

表3 多超球體一類分類器與單超球體一類分類器對(duì)轉(zhuǎn)子故障的識(shí)別率

4 結(jié)語(yǔ)

本文從考慮數(shù)據(jù)內(nèi)在分布的角度出發(fā)研究了一種基于最大樹聚類的多超球體一類分類算法。首先對(duì)經(jīng)PCA特征降維后的訓(xùn)練樣本集采用最大樹聚類算法實(shí)現(xiàn)聚類,得到對(duì)應(yīng)的內(nèi)在分布簇形成的各子類；然后對(duì)各簇子類分別進(jìn)行一類支持向量機(jī)分類器訓(xùn)練，并且利用粒子群優(yōu)化算法獲取最優(yōu)參數(shù)，得到各子類對(duì)應(yīng)的超球體；最后建立由各子類對(duì)應(yīng)的超球體而形成的多超球體一類分類模型。分別將該方法應(yīng)用于仿真數(shù)據(jù)、UCI標(biāo)準(zhǔn)數(shù)據(jù)集以及轉(zhuǎn)子故障數(shù)據(jù)這三個(gè)實(shí)例中，實(shí)驗(yàn)結(jié)果表明，當(dāng)樣本數(shù)據(jù)呈簇類分布時(shí)，尤其是聚類特征比較明顯時(shí)，該方法相對(duì)于常用的單超球體一類分類方法具有可行性及有效性。

[1] Juszczak P. Learning to Recognise:a Study on One-class Classification and Active Learning[D]. Delft: Delft University of Technology, 2006.

[2] Camci F, Chinnam R B. General Support Vector Representation Machine for One-class Classification of Non-stationary Classes[J]. Pattern Recognition,2008, 41: 3021-3034.

[3] Tsang I W,James T K,Li S.Learning the Kernel in Mahalanobis One-class Support Vector Machines[C]//Proceeding of the International Joint Conference on Neural Networks.Vancouver,Canada,2006:1169-1175.

[4] Tax D. One-class Classification: Concept-learning in the Absence of Counter-examples[D].Delft: Delft University of Technology,2001.

[5] 譚真臻, 陳果, 孫麗萍. 基于Hilbert譜圖特征的航空發(fā)動(dòng)機(jī)轉(zhuǎn)子故障智能診斷[J].機(jī)械科學(xué)與技術(shù),2010, 29(9):1177-1181.

[6] 馮愛(ài)民,陳松燦. 基于核的單類分類器研究[J].南京師范大學(xué)學(xué)報(bào)(工程技術(shù)版),2008,8(4):1-6.

[7] 戴蒙,林家駿,劉云翔.基于FCM聚類的多超球體一類分類數(shù)字圖像隱藏信息[J].中國(guó)圖像圖形學(xué)報(bào),2008,13(10):1918-1921.

[8] Wang D, Yeung D S, Tsang E C C. Structured One-class Classification[J].IEEE Trans. on Systems, Man, and Cybernetics-Part B:Cybernetics,2006,36(6):1283-1294.

[9] 肖健華. 智能模式識(shí)別方法[M]. 廣州: 華南理工大學(xué)出版社, 2006.

[10] 楊夢(mèng)寧,楊丹,張強(qiáng)勁.基于最大樹法的模糊圖像分割方法[J].計(jì)算機(jī)科學(xué),2005,32(8):190-191.

[11] Duda R O,Hart P E,Stork D G.模式分類[M].李宏?yáng)|,姚天翔,等,譯.2版.北京：機(jī)械工業(yè)出版社，2003.

[12] Chapelle O, Vapnik V, Bousquet O, et al. Choosing Multiple Parameters for Support Vector Machines[J]. Machine Learning,2002,46(1):131-159.

[13] 王東,吳湘濱.利用粒子群算法優(yōu)化SVM分類器的超參數(shù)[J].計(jì)算機(jī)應(yīng)用,2008,28(1):134-135.

[14] 邵信光,楊慧中,陳剛.基于粒子群優(yōu)化算法的支持向量機(jī)參數(shù)選擇及其應(yīng)用[J].控制理論與應(yīng)用,2006,23(5):740-743.