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

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

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

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

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

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

1 間隔理論

AdaBoost算法是集成學(xué)習(xí)中Boosting算法族的核心算法，它本質(zhì)上是一種元算法，任何有監(jiān)督基分類算法均可通過AdaBoost算法進(jìn)行集成，它在統(tǒng)計學(xué)、機器學(xué)習(xí)和數(shù)據(jù)挖掘等方面得到了廣泛的應(yīng)用。間隔理論[17]是AdaBoost算法的重要理論基礎(chǔ)，成功地解釋其不易過擬合等性質(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個基分類器組成的集成分類器f的間隔定義為：

(2)

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

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

(3)

式中：

(4)

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

對于一個分類系統(tǒng)，其泛化誤差直接決定了分類性能的好壞。在選擇性集成學(xué)習(xí)中，雖然差異性是關(guān)鍵因素，但很多試驗表明，并不是差異性越大，泛化性就越好。這就使得研究者需要從理論角度解釋這個問題，文獻(xiàn)[19]通過對多種常用差異性度量的總結(jié)，引入最小化間隔，給出了最大化差異性和間隔最大化的一致條件。但其試驗發(fā)現(xiàn)差異性與最小間隔又不是完全正比關(guān)系。從定理1可以看出，決定系統(tǒng)泛化性的是間隔的統(tǒng)計特征而不是最小化間隔，因此，本文從理論上推導(dǎo)出差異性度量與間隔統(tǒng)計特征的關(guān)系式，從而給出單純增加差異性并不一定能改善泛化性的原因。

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

(5)

由于：

(6)

(7)

兩式相加得：

(8)

因此，基分類器的識別正確率為：

(9)

對于平均識別正確率：

(10)

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

(11)

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

由于：

(12)

(13)

因此：

(14)

(15)

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

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

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

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

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

mc=yiαjhj(xi)

(16)

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

(17)

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

(18)

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

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

Cm=λmp+(1-λ)mn

(19)

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

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

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

(20)

Qij越大，說明2個分類器之間的差異性越小。

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

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

(21)

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

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

Ms=γCm+(1-γ)Cq

(22)

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

3.2 算法描述

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

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

2)Forj=1:L

Fori=1:N

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

計算差異性度量Qij;

End

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

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

End

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

4 實測水聲目標(biāo)數(shù)據(jù)試驗

4.1 數(shù)據(jù)集及評價準(zhǔn)則

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

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

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

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

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

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

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

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

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

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

圖中，特征集1～4分別指調(diào)制譜特征集、高階譜特征集、MFCC特征集和小波特征集，每一個特征集中，3個柱狀圖從左到右依次是AdaBoost算法、選擇性集成算法和MDSE算法。從圖中看出，在不同特征集、不同不平衡率下，MDSE算法的3種準(zhǔn)則結(jié)果基本均高于AdaBoost算法和選擇性集成算法。對每種特征集上不同不平衡率結(jié)果求均值，得到3種準(zhǔn)則的平均結(jié)果如表3所示。平均來看，相對于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é)果顯著提高，說明在處理不平衡水聲目標(biāo)數(shù)據(jù)分類問題上，MDSE算法性能相對于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)試驗結(jié)果顯示，相對于AdaBoost算法和選擇性集成算法，MDSE算法在不平衡數(shù)據(jù)集上性能更優(yōu)，說明差異性和不平衡性均對算法本身有影響。

2)對于差異性，本文證明了單純增加差異性無法改善泛化性；對于不平衡性，以間隔理論為基礎(chǔ)，提出了間隔度量來定量刻畫不平衡性。理論分析對算法提供了有力支撐，而試驗結(jié)果則印證了算法的有效性。

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