程玉勝，張宗堂，李海濤，劉振

(海軍潛艇學(xué)院 航海觀通系，山東 青島 266000)

對(duì)于兩分類問(wèn)題，如果其中一類的樣本數(shù)量遠(yuǎn)多于另一類，則這個(gè)問(wèn)題就稱為不平衡數(shù)據(jù)分類問(wèn)題，其中，數(shù)量多的一類為多類，數(shù)量少的為少類。近年來(lái)，不平衡數(shù)據(jù)分類問(wèn)題成為了機(jī)器學(xué)習(xí)的熱點(diǎn)問(wèn)題之一，在郵件過(guò)濾[1]、軟件缺陷預(yù)測(cè)[2]、醫(yī)療診斷[3]、DNA數(shù)據(jù)分析[4]等領(lǐng)域得到了廣泛的研究。在水聲目標(biāo)識(shí)別中，各種船舶、航行器、生物等目標(biāo)種類繁多，不同種類之間的數(shù)量也相差較大，這也就形成了不平衡數(shù)據(jù)分類問(wèn)題，但它在水聲領(lǐng)域的研究較少。

集成學(xué)習(xí)及其改進(jìn)算法[5-8]常用來(lái)解決不平衡數(shù)據(jù)分類問(wèn)題，選擇性集成學(xué)習(xí)是一種新興的集成學(xué)習(xí)算法，它是在一定策略下從全部基分類器中挑選一部分來(lái)組成最終集成分類器，文獻(xiàn)[9]通過(guò)理論分析，提出了“many could be better than all”理論：對(duì)于有監(jiān)督學(xué)習(xí)，給定一組基分類器，選擇其中一部分進(jìn)行集成或許比選擇全部要好。

選擇性集成的核心是差異性，研究者從軟件工程[10]、信息論[11]、統(tǒng)計(jì)學(xué)[12]等領(lǐng)域提出了有關(guān)差異性的度量方法，并在此基礎(chǔ)上提出了許多選擇性集成算法[13-14]。直觀上看，基分類器之間的差異性越大，那么它們就可以“取長(zhǎng)補(bǔ)短”，使得最終的集成分類器有較好的泛化性。選擇性集成學(xué)習(xí)算法在不平衡數(shù)據(jù)分類問(wèn)題上得到了一定的應(yīng)用，文獻(xiàn)[15]將幾種選擇性集成方法進(jìn)行改造，提出了RE-GM、MDM-Imb、BB-Imb等算法，試驗(yàn)結(jié)果表明改進(jìn)算法在不平衡數(shù)據(jù)集上性能有所提高，文獻(xiàn)[16]采用重采樣、集成算法與差異性提高方法相結(jié)合來(lái)處理不平衡問(wèn)題。

本文從差異性和不平衡性2方面出發(fā)，首先通過(guò)間隔理論揭示了單純?cè)黾硬町愋詿o(wú)法提高泛化性的原因，然后通過(guò)將間隔的概念在分類器空間擴(kuò)展，定義了間隔度量，通過(guò)間隔度量刻畫(huà)了不同基分類器對(duì)樣本不平衡性的影響，從而選擇出有利于少類目標(biāo)分類正確率提高的基分類器，結(jié)合差異性和不平衡性2方面因素，通過(guò)差異性度量增加差異性并通過(guò)間隔度量?jī)A向于少類目標(biāo)，從而構(gòu)建了間隔和差異性融合的選擇性度量，根據(jù)選擇性度量對(duì)基分類器進(jìn)行篩選，形成間隔和差異性融合的選擇性集成算法(margin and diversity fusion selective ensemble algorithm，MDSE)，提高集成算法對(duì)少類目標(biāo)的分類能力。

1 間隔理論

AdaBoost算法是集成學(xué)習(xí)中Boosting算法族的核心算法，它本質(zhì)上是一種元算法，任何有監(jiān)督基分類算法均可通過(guò)AdaBoost算法進(jìn)行集成，它在統(tǒng)計(jì)學(xué)、機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘等方面得到了廣泛的應(yīng)用。間隔理論[17]是AdaBoost算法的重要理論基礎(chǔ)，成功地解釋其不易過(guò)擬合等性質(zhì)。本研究用假設(shè)C(H)是基分類器空間H的凸包，集成分類器f∈C(H)可以表示為：

f=∑αihiwith ∑αi=1 andαi≥0

(1)

式中hi是權(quán)重為αi的基分類器。樣本(xi,yi)關(guān)于由L個(gè)基分類器組成的集成分類器f的間隔定義為：

(2)

間隔的重要作用是它能夠刻畫(huà)分類系統(tǒng)的泛化性，文獻(xiàn)[18]推導(dǎo)出集成分類器泛化誤差界與其間隔統(tǒng)計(jì)特征的關(guān)系。

定理1從訓(xùn)練樣本集上的一個(gè)分布Dist中獨(dú)立隨機(jī)抽取N(N>5)個(gè)訓(xùn)練樣本組成集合Dtr，對(duì)任意的θ>0，每一個(gè)集成分類器f∈C(H)在Dtr上至少以1-δ的概率滿足泛化誤差界：

(3)

式中：

(4)

2 集成分類器泛化性與差異性的關(guān)系

對(duì)于一個(gè)分類系統(tǒng)，其泛化誤差直接決定了分類性能的好壞。在選擇性集成學(xué)習(xí)中，雖然差異性是關(guān)鍵因素，但很多試驗(yàn)表明，并不是差異性越大，泛化性就越好。這就使得研究者需要從理論角度解釋這個(gè)問(wèn)題，文獻(xiàn)[19]通過(guò)對(duì)多種常用差異性度量的總結(jié)，引入最小化間隔，給出了最大化差異性和間隔最大化的一致條件。但其試驗(yàn)發(fā)現(xiàn)差異性與最小間隔又不是完全正比關(guān)系。從定理1可以看出，決定系統(tǒng)泛化性的是間隔的統(tǒng)計(jì)特征而不是最小化間隔，因此，本文從理論上推導(dǎo)出差異性度量與間隔統(tǒng)計(jì)特征的關(guān)系式，從而給出單純?cè)黾硬町愋圆⒉灰欢芨纳品夯缘脑颉?/p>

根據(jù)間隔的定義，得到訓(xùn)練樣本集全部間隔的均值為：

(5)

由于：

(6)

(7)

兩式相加得：

(8)

因此，基分類器的識(shí)別正確率為：

(9)

對(duì)于平均識(shí)別正確率：

(10)

文獻(xiàn)[20]總結(jié)了6種差異性度量，根據(jù)上文符號(hào)將它們統(tǒng)一歸納為：

(11)

式中：div是基分類器的差異性度量；a、b、c為常數(shù)；li是對(duì)樣本識(shí)別錯(cuò)誤的基分類器的權(quán)重之和與L的乘積。

由于：

(12)

(13)

因此：

(14)

(15)

式中V為mi的方差，即間隔方差。定理1提到，間隔均值越大，同時(shí)間隔方差越小，則泛化誤差越小，在式(15)中，差異性度量與間隔均值和間隔方差成非線性關(guān)系，提高差異性度量并不能保證增大間隔均值且減小間隔方差，因此單純?cè)黾硬町愋圆⒉灰欢芙档头夯`差，所以傳統(tǒng)的差異性度量有一定的局限性。另外，由于差異性度量未考慮樣本不平衡性，因此不適合直接處理不平衡數(shù)據(jù)分類問(wèn)題，這就需要有新的度量準(zhǔn)則。

3 間隔和差異性融合的選擇性集成算法

3.1 間隔和差異性融合的選擇性度量

間隔統(tǒng)計(jì)特征作為集成分類器泛化性的良好刻畫(huà)，可以用來(lái)度量差異性，不過(guò)從間隔的定義可以看出，間隔是樣本的特征量，而差異性度量的是基分類器之間的特性，因此需要把間隔的定義擴(kuò)展到分類器空間，來(lái)刻畫(huà)基分類器對(duì)間隔大小的貢獻(xiàn)程度。

定義1基分類器hj對(duì)樣本xi的間隔貢獻(xiàn)量：

mc=yiαjhj(xi)

(16)

定義2基分類器hj對(duì)少類目標(biāo)訓(xùn)練樣本集Dp的少類間隔均值貢獻(xiàn)量：

(17)

定義3基分類器hj對(duì)多類目標(biāo)訓(xùn)練樣本集Dn的多類間隔均值貢獻(xiàn)量：

(18)

從定義可以看出，mp的值越大，基分類器對(duì)少類間隔均值的貢獻(xiàn)就越大，則基分類器對(duì)少類目標(biāo)的分類正確率就越高，因此可以將mp作為分類器選擇的一種度量，但只提高少類目標(biāo)正確率而完全忽視多類目標(biāo)并不是想要的結(jié)果，所以也需要將mn納入度量中。

定義4根據(jù)少類和多類間隔均值貢獻(xiàn)量，定義間隔度量：

Cm=λmp+(1-λ)mn

(19)

式中：λ∈[0,1]為權(quán)衡系數(shù)；Cm用來(lái)度量基分類器對(duì)兩類樣本間隔均值的貢獻(xiàn)量，可以在偏向于少類間隔均值的同時(shí)也兼顧多類間隔均值。

另一方面，傳統(tǒng)的差異性度量一般分為成對(duì)型和非成對(duì)型，二者均無(wú)法與間隔度量直接融合，因此需要做一定的改進(jìn)，本文采用Q統(tǒng)計(jì)量作為差異性度量進(jìn)行改進(jìn)。

表1中，nij表示符合相應(yīng)條件的個(gè)數(shù)。Q統(tǒng)計(jì)量Qij是在2個(gè)基分類器的聯(lián)合輸出上構(gòu)造的：

(20)

Qij越大，說(shuō)明2個(gè)分類器之間的差異性越小。

表1 2個(gè)基分類器的聯(lián)合輸出Table 1 The joint output of two base classifiers

定義5根據(jù)Q統(tǒng)計(jì)量定義差異性貢獻(xiàn)量：

(21)

從定義可以看出，Cq是hj與所有基分類器的Q統(tǒng)計(jì)量的均值的負(fù)數(shù)，Cq越大說(shuō)明該基分類器對(duì)整體的差異性貢獻(xiàn)越大。

定義6融合間隔度量和差異性貢獻(xiàn)量，定義選擇性度量：

Ms=γCm+(1-γ)Cq

(22)

式中γ∈[0,1]為權(quán)衡系數(shù)。

3.2 算法描述

選擇性度量Ms兼顧了間隔和差異性兩方面，既確保了基分類器之間的差異性，又可以篩選出對(duì)少類間隔均值貢獻(xiàn)大的基分類器，從而提高少類識(shí)別正確率，利用Ms構(gòu)造間隔和差異性融合的選擇性集成算法。MDSE算法的輸入是已經(jīng)預(yù)訓(xùn)練完成的L個(gè)基分類器、訓(xùn)練樣本集和最終子分類器集Hs的大小Ls，MDSE算法通過(guò)計(jì)算每個(gè)基分類器的間隔度量和差異性貢獻(xiàn)量得到其選擇性度量，根據(jù)選擇性度量大小由高到低排序，選擇前Ls個(gè)基分類器作為最終子分類器集并形成選擇性集成分類器Fs(xi)。MDSE算法為：

1)對(duì)訓(xùn)練樣本集進(jìn)行預(yù)訓(xùn)練；

2)Forj=1:L

Fori=1:N

計(jì)算基分類器的間隔貢獻(xiàn)量yiαjhj(xi);

計(jì)算差異性度量Qij;

End

計(jì)算少類間隔均值貢獻(xiàn)量mp和多類間隔均值貢獻(xiàn)量mn得到間隔度量Cm；

計(jì)算差異性貢獻(xiàn)量Cq得到選擇性度量Ms；

End

3)對(duì)基分類器按Ms大小由高到低排序，選擇前Ls個(gè)基分類器組成子分類器集Hs；

4 實(shí)測(cè)水聲目標(biāo)數(shù)據(jù)試驗(yàn)

4.1 數(shù)據(jù)集及評(píng)價(jià)準(zhǔn)則

試驗(yàn)采用整理得到的實(shí)測(cè)水聲目標(biāo)數(shù)據(jù)970條，其中，A類(少類)目標(biāo)140條，B類(多類)目標(biāo)830條。利用水聲目標(biāo)識(shí)別中常規(guī)的特征提取方法對(duì)數(shù)據(jù)集進(jìn)行特征提取，分別提取其調(diào)制譜特征、高階譜特征、MFCC特征和小波特征，特征維度如表2所示，將各自特征分別組成單獨(dú)的特征集，下文的試驗(yàn)將在不同特征集上分別進(jìn)行處理。

表2 試驗(yàn)數(shù)據(jù)特征維度Table 2 Feature dimension of experimental data

評(píng)價(jià)準(zhǔn)則對(duì)于評(píng)估分類性能和指導(dǎo)分類器構(gòu)建有重要作用，傳統(tǒng)的分類器一般采用總體分類精度作為評(píng)價(jià)準(zhǔn)則，但是總體分類精度并沒(méi)有考慮樣本的不平衡性，因此不再適合評(píng)價(jià)不平衡數(shù)據(jù)分類問(wèn)題。F-measure準(zhǔn)則、G-mean準(zhǔn)則和AUC準(zhǔn)則是不平衡數(shù)據(jù)分類問(wèn)題的3種常用評(píng)價(jià)準(zhǔn)則，其數(shù)值越高，說(shuō)明算法處理不平衡數(shù)據(jù)分類的性能越好。

4.2 試驗(yàn)參數(shù)設(shè)置

預(yù)訓(xùn)練中，基分類器數(shù)量取50，基分類器種類選擇決策樁。Ls是一個(gè)重要的參數(shù)，Ls過(guò)大則會(huì)增加參數(shù)數(shù)量和時(shí)間開(kāi)銷，過(guò)小則不能精確地表征數(shù)據(jù)?；诸惼髦?，選擇性度量為正的才對(duì)集成分類器有正面作用。通過(guò)不同參數(shù)下大量試驗(yàn)，對(duì)選擇性度量中值為正的基分類器個(gè)數(shù)進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)結(jié)果如圖1所示?？梢钥闯?，30作為值為正的基分類器個(gè)數(shù)的頻率最高，因此取Ls=30。

圖1 基分類器個(gè)數(shù)分布Fig.1 The number distribution of base classifiers

權(quán)衡系數(shù)中，由于首先要考慮的是偏向于少類目標(biāo)，同時(shí)兼顧多類目標(biāo)和引入差異性，因此取λ=0.6,γ=0.6。不平衡率是衡量數(shù)據(jù)不平衡性的一個(gè)重要指標(biāo)，不平衡率IR定義為多類樣本數(shù)量與少類樣本數(shù)量的比值。一般認(rèn)為，當(dāng)不平衡率大于或等于2時(shí)，數(shù)據(jù)集為不平衡數(shù)據(jù)集。

試驗(yàn)中訓(xùn)練樣本集和測(cè)試樣本集中的少類數(shù)量相同且均為70，訓(xùn)練樣本集和測(cè)試樣本集中的多類數(shù)量相同，分別取140、210、280、350，對(duì)應(yīng)的不平衡率分別是2、3、4、5。所有樣本均隨機(jī)地從樣本集中抽取，訓(xùn)練樣本集與測(cè)試樣本集互斥，每個(gè)試驗(yàn)獨(dú)立重復(fù)50次并取平均值。

4.3 試驗(yàn)結(jié)果與分析

為了驗(yàn)證MDSE算法的性能，將AdaBoost算法和基于Q統(tǒng)計(jì)量的選擇性集成算法進(jìn)行對(duì)比。利用F-measure準(zhǔn)則、G-mean準(zhǔn)則和AUC準(zhǔn)則對(duì)測(cè)試結(jié)果進(jìn)行評(píng)價(jià)，如圖2～4所示。

圖中，特征集1～4分別指調(diào)制譜特征集、高階譜特征集、MFCC特征集和小波特征集，每一個(gè)特征集中，3個(gè)柱狀圖從左到右依次是AdaBoost算法、選擇性集成算法和MDSE算法。從圖中看出，在不同特征集、不同不平衡率下，MDSE算法的3種準(zhǔn)則結(jié)果基本均高于AdaBoost算法和選擇性集成算法。對(duì)每種特征集上不同不平衡率結(jié)果求均值，得到3種準(zhǔn)則的平均結(jié)果如表3所示。平均來(lái)看，相對(duì)于AdaBoost算法和選擇性集成算法，MDSE算法在F-measure準(zhǔn)則下分別從0.26和0.32提升到0.38，在G-mean準(zhǔn)則下分別從0.39和0.43提升到0.48，在AUC準(zhǔn)則下分別從0.37和0.47提升到0.49，結(jié)果顯著提高，說(shuō)明在處理不平衡水聲目標(biāo)數(shù)據(jù)分類問(wèn)題上，MDSE算法性能相對(duì)于AdaBoost算法和選擇性集成算法有明顯改善。

圖2 F-measure準(zhǔn)則結(jié)果Fig.2 The results of F-measure

圖3 G-mean準(zhǔn)則結(jié)果Fig.3 The results of G-mean

圖4 AUC準(zhǔn)則結(jié)果Fig.4 The results of AUC

表3 不同特征集準(zhǔn)則均值結(jié)果Table 3 The criterion mean results of different feature set

5 結(jié)論

1)試驗(yàn)結(jié)果顯示，相對(duì)于AdaBoost算法和選擇性集成算法，MDSE算法在不平衡數(shù)據(jù)集上性能更優(yōu)，說(shuō)明差異性和不平衡性均對(duì)算法本身有影響。

2)對(duì)于差異性，本文證明了單純?cè)黾硬町愋詿o(wú)法改善泛化性；對(duì)于不平衡性，以間隔理論為基礎(chǔ)，提出了間隔度量來(lái)定量刻畫(huà)不平衡性。理論分析對(duì)算法提供了有力支撐，而試驗(yàn)結(jié)果則印證了算法的有效性。

本文提供了一種解決不平衡數(shù)據(jù)分類問(wèn)題的新思路，即兼顧不平衡性和差異性，有一定工程應(yīng)用前景。下一步的工作中，可以將兩分類問(wèn)題擴(kuò)展到多分類問(wèn)題進(jìn)行相應(yīng)的研究。