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

劉麗娟 陳 果

南京航空航天大學，南京，210016

0 引言

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

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

1 單超球體一類分類器

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

(1)

定義Lagrange函數(shù)：

(2)

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

(3)

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

(4)

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

(5)

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

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

(6)

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

(7)

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

(8)

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

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

(a)單超球體

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

相對于單超球體的一類分類器，多超球體一類分類器首先要對訓練樣本進行聚類，然后對聚類后的各子類分別進行一類支持向量機分類器學習，最后得到對應的多個超球體一類分類模型。

2.1 聚類

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

(9)

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

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

(1)對所得樣本數(shù)據(jù)進行特征提取，得到對應的訓練樣本集、測試樣本集。

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

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

圖2是其對應的流程圖，可以看出當訓練樣本集聚類為一個子類(即m=1)時，所得的多超球體分類模型就是單超球體分類模型。即單超球體一類分類器可以看作是多超球體一類分類器將其對應的訓練樣本集聚為一個子類的特例。

圖2 算法流程

3 實驗與應用

3.1 仿真數(shù)據(jù)實驗

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

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

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

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

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

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

3.2 UCI標準數(shù)據(jù)集實驗

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

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

(a)Sonar1 樣本三維分布圖

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

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

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

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

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

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

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

表2 多超球體一類分類器與單超球體一類分類器對標準數(shù)據(jù)集的實驗結(jié)果

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

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

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

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

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

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

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

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

4 結(jié)語

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

[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ā)動機轉(zhuǎn)子故障智能診斷[J].機械科學與技術,2010, 29(9):1177-1181.

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

[7] 戴蒙,林家駿,劉云翔.基于FCM聚類的多超球體一類分類數(shù)字圖像隱藏信息[J].中國圖像圖形學報,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] 肖健華. 智能模式識別方法[M]. 廣州: 華南理工大學出版社, 2006.

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

[11] Duda R O,Hart P E,Stork D G.模式分類[M].李宏東,姚天翔,等,譯.2版.北京：機械工業(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].計算機應用,2008,28(1):134-135.

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