類不平衡模糊加權(quán)極限學(xué)習(xí)機(jī)算法研究*

于化龍，祁云嵩，楊習(xí)貝，左 欣

1.江蘇科技大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，江蘇 鎮(zhèn)江 212003

2.東南大學(xué) 自動化學(xué)院，南京 210096

類不平衡模糊加權(quán)極限學(xué)習(xí)機(jī)算法研究*

于化龍1,2+，祁云嵩1，楊習(xí)貝1，左 欣1

1.江蘇科技大學(xué) 計算機(jī)科學(xué)與工程學(xué)院，江蘇 鎮(zhèn)江 212003

2.東南大學(xué) 自動化學(xué)院，南京 210096

從理論上分析了樣例不平衡分布對極限學(xué)習(xí)機(jī)性能產(chǎn)生危害的原因；在該理論框架下探討了加權(quán)極限學(xué)習(xí)機(jī)在處理此類問題上的有效性及其固有缺陷；引入模糊集的思想，對傳統(tǒng)的加權(quán)極限學(xué)習(xí)機(jī)進(jìn)行了改進(jìn)，并提出了4種用于解決類不平衡問題的模糊加權(quán)極限學(xué)習(xí)機(jī)算法；最后通過20個基準(zhǔn)的二類不平衡數(shù)據(jù)集對所提算法的有效性和可行性進(jìn)行了驗證。實驗結(jié)果表明：較之加權(quán)極限學(xué)習(xí)機(jī)及幾種傳統(tǒng)的不平衡極限學(xué)習(xí)機(jī)算法，提出的算法可明顯獲得更優(yōu)的分類性能，并且與模糊加權(quán)支持向量機(jī)系列算法相比，所提算法通?？色@得與之相當(dāng)?shù)姆诸愋阅?，但時間開銷往往更小。

極限學(xué)習(xí)機(jī)；類不平衡學(xué)習(xí)；模糊加權(quán)；先驗分布信息

1 引言

極限學(xué)習(xí)機(jī)（extreme learning machine，ELM）由Huang等人[1]于2006年正式提出，經(jīng)過近十年的發(fā)展，已經(jīng)成為機(jī)器學(xué)習(xí)領(lǐng)域的研究熱點(diǎn)之一。不同于傳統(tǒng)的誤差反傳（back-propagation，BP）算法[2]，ELM通過隨機(jī)指定隱層參數(shù)，并利用最小二乘法求解輸出層權(quán)重的方式來訓(xùn)練單隱層前饋神經(jīng)網(wǎng)絡(luò)（single hidden-layer feedback network，SLFN），故其具有泛化能力強(qiáng)，訓(xùn)練速度快等優(yōu)點(diǎn)[3-4]。因ELM的上述優(yōu)點(diǎn)，其已在諸多實際領(lǐng)域中得到了具體應(yīng)用，包括人臉識別[5]、遙感圖像分類[6]、風(fēng)能模型構(gòu)建[7]、企業(yè)生命周期預(yù)測[8]、空氣質(zhì)量檢測[9]和生物信息學(xué)[10]等。

盡管ELM具有諸多優(yōu)點(diǎn)，但其也存在一個固有的缺點(diǎn)，即當(dāng)數(shù)據(jù)分布極為不平衡時，分類性能往往大幅下降[8-9,11]。實際上，類不平衡問題也是各種傳統(tǒng)分類算法所面臨的一個共性問題。所謂類不平衡問題，即數(shù)據(jù)集中的某一類樣例遠(yuǎn)多于另一類，從而導(dǎo)致以整體錯分率最小化為訓(xùn)練目標(biāo)的分類算法失效的問題。針對這一問題，前人已進(jìn)行了大量的研究，并給出了諸多解決方法，包括樣例采樣[12-13]、樣例加權(quán)（也稱代價敏感學(xué)習(xí)）[14]、分類面偏移[15]、一類分類器[16]和集成學(xué)習(xí)[17-18]等。具體到ELM，Zong等人[11]借鑒代價敏感學(xué)習(xí)的思想，提出了一種加權(quán)極限學(xué)習(xí)機(jī)（weighted extreme learning machine，WELM）算法。該算法通過為不同類的樣例賦予不同權(quán)重，從而改變其懲罰因子的方式，達(dá)到提升少數(shù)類樣例識別精度的目的，其缺點(diǎn)在于為同類樣例分配的權(quán)重均相同，并未考慮樣例先驗分布信息的作用。Vong等人[9]將ELM與隨機(jī)過采樣技術(shù)（random oversampling，ROS）相結(jié)合，并用于空氣質(zhì)量檢測，提升了空氣中固體顆粒物等級的識別率。Sun等人[8]則將SMOTE（synthetic minority oversampling technique）算法[12]引入到ELM集成學(xué)習(xí)的框架中，在企業(yè)生命周期的預(yù)測任務(wù)上獲得了很好的性能。

上述工作盡管均圍繞ELM分類器提出了相應(yīng)的不平衡學(xué)習(xí)算法，但并未在理論上對類不平衡如何危害ELM性能的原因進(jìn)行分析。故本文擬首先對該問題展開分析，并進(jìn)一步在該理論框架下對WELM算法的有效性進(jìn)行討論。接下來，考慮WELM算法未耦合樣例先驗分布信息這一缺點(diǎn)，借鑒文獻(xiàn)[14]的思想，引入模糊集的概念，分別設(shè)計了4種隸屬函數(shù)，并進(jìn)一步相應(yīng)地提出了4種用于解決類不平衡問題的模糊加權(quán)極限學(xué)習(xí)機(jī)（fuzzy weighted extreme learning machine，F(xiàn)WELM）算法。通過從Keel數(shù)據(jù)倉庫[19]中隨機(jī)抽取的20個基準(zhǔn)的二類不平衡數(shù)據(jù)集對上述算法的有效性與可行性進(jìn)行了驗證。實驗結(jié)果表明：相對于WELM算法及幾種傳統(tǒng)的類不平衡極限學(xué)習(xí)機(jī)算法，F(xiàn)WELM系列算法可獲得明顯更優(yōu)的分類性能。而與模糊加權(quán)支持向量機(jī)（fuzzy support vector machine for class imbalance learning，F(xiàn)SVM-CIL）系列算法[14]相比，F(xiàn)WELM系列算法通?？色@得與之相當(dāng)?shù)姆诸愋阅?，但時間開銷往往更小。

2 理論分析

2.1 極限學(xué)習(xí)機(jī)

2006年，新加坡南洋理工大學(xué)的Huang等人[1]針對SLFN的訓(xùn)練問題，提出了極限學(xué)習(xí)機(jī)理論與算法。不同于傳統(tǒng)的BP學(xué)習(xí)算法[2]，極限學(xué)習(xí)機(jī)無需對網(wǎng)絡(luò)的權(quán)重與偏置進(jìn)行迭代調(diào)整，而是通過最小二乘法直接計算得到，故大大提升了網(wǎng)絡(luò)的訓(xùn)練速度，并在一定程度上降低了網(wǎng)絡(luò)陷入過適應(yīng)的概率。SLFN的基本結(jié)構(gòu)如圖1所示。

Fig.1 Basic structure of single-hidden-layer feedforward neural network圖1 單隱層前饋網(wǎng)絡(luò)的基本結(jié)構(gòu)圖

眾所周知，在監(jiān)督學(xué)習(xí)中，學(xué)習(xí)算法通常采用有限的訓(xùn)練樣本來生成學(xué)習(xí)模型。假設(shè)訓(xùn)練樣本集包括N個訓(xùn)練樣例，則其可表示為(xi,ti)∈Rn×Rm。其中，xi表示n×1維的輸入向量，ti表示第i個訓(xùn)練樣本的期望輸出向量。對于分類問題而言，n代表訓(xùn)練樣本的屬性數(shù)，m則代表樣本的類別數(shù)。如圖1所示，若一個具有L個隱層節(jié)點(diǎn)的單隱層前饋神經(jīng)網(wǎng)絡(luò)能以零誤差擬合上述N個訓(xùn)練樣本，則意味著存在βi、ai及bi，使得下式成立：

其中，ai和bi分別表示第i個隱層節(jié)點(diǎn)的權(quán)重與偏置；βi表示第i個隱層節(jié)點(diǎn)的輸出權(quán)重，即第i個隱層節(jié)點(diǎn)到各輸出節(jié)點(diǎn)的連接權(quán)重；G表示激活函數(shù)。則式（1）可進(jìn)一步簡化為下式：

其中：

其中，G(ai,bi,xj)表示第j個訓(xùn)練樣本在第i個隱層節(jié)點(diǎn)上的激活函數(shù)值；T為所有訓(xùn)練樣本對應(yīng)的期望輸出矩陣，通常將每個樣本所對應(yīng)類別輸出節(jié)點(diǎn)的期望輸出值設(shè)為1，其他節(jié)點(diǎn)的輸出值則設(shè)為-1；H被稱為隱層輸出矩陣，其第i列為第i個隱層節(jié)點(diǎn)在所有訓(xùn)練樣本上的輸出向量，第j行為第j個訓(xùn)練樣本在整個隱藏層中對應(yīng)的輸出向量。

在ELM中，由于所有ai和bi均是在[-1,1]區(qū)間內(nèi)隨機(jī)生成的，故輸入樣例、隱層權(quán)重與偏置、期望輸出（類別標(biāo)記）均已知，則輸出權(quán)重矩陣β的近似解即可由下式直接計算得到：

其中，H?為隱層輸出矩陣的Moore-Penrose廣義逆。根據(jù)其定義，可推知β?為該網(wǎng)絡(luò)的最小范數(shù)最小二乘解。因此，極限學(xué)習(xí)機(jī)可通過一步計算得到，而無需迭代訓(xùn)練，這就保證了神經(jīng)網(wǎng)絡(luò)的訓(xùn)練時間能被大幅縮減。同時，由于在求解過程中，約束了輸出權(quán)重矩陣β的l2范數(shù)，使其最小化，故可保證網(wǎng)絡(luò)具有較強(qiáng)的泛化性能。

2012年，Huang等人[3]又提出了ELM的優(yōu)化版本，優(yōu)化式表示如下：

其中，εi表示第i個訓(xùn)練樣本的實際輸出與期望輸出之差；h(xi)為第i個樣例xi在隱層上的輸出向量；C則為懲罰因子，用于調(diào)控網(wǎng)絡(luò)的泛化性與精確性間的平衡關(guān)系。上述優(yōu)化式可通過求解得到，給定一個具體的樣例x，其對應(yīng)的實際輸出向量可由下式求得：

其中，I表示單位矩陣；f(x)=[f1(x),f2(x),…,fm(x)]表示樣例x的實際輸出向量，并可進(jìn)一步通過下式確定該樣例的預(yù)測類標(biāo)：

2.2 類不平衡分布對極限學(xué)習(xí)機(jī)性能的影響機(jī)理

眾所周知，對于ELM而言，那些在特征空間中相鄰較近的樣例通常會有極其相似的輸出值，而在類重疊區(qū)域，多數(shù)類樣例會將少數(shù)類樣例緊密地包裹其中，它們的輸出值極為接近。為同時保證所訓(xùn)練的ELM具有較強(qiáng)的泛化能力與較低的訓(xùn)練誤差，少數(shù)類必然做出更多的犧牲。不失一般性，假設(shè)分類任務(wù)只有兩個類別，其中在ELM中，少數(shù)類對應(yīng)的期望輸出為1，而多數(shù)類的期望輸出為-1?？紤]特征空間中兩類樣例的重疊區(qū)域，從該區(qū)域分割出一個足夠小且樣例分布致密的子區(qū)域，在這一區(qū)域中多數(shù)類樣例有S個，而少數(shù)類樣例數(shù)恰好只有1個，即在此區(qū)域中，不平衡比率為S，則根據(jù)ELM的構(gòu)造機(jī)理，這S+1個樣例有極其近似的輸出值。設(shè)該少數(shù)類樣例的特征向量為x0=(x01,x02,…,x0n)，則N個多數(shù)類樣例的特征向量可表示為xi=(x01+Δxi1,x02+Δxi2,…,x0n+ Δxin),i∈{1,2,…,S}，其中，Δxij表示第i個多數(shù)類樣例與少數(shù)類樣例x0相比，在第j個特征上的變化量。則在ELM訓(xùn)練完成后，這些樣例的實際輸出可表示為：

若以Δf(xj)來表示第j個多數(shù)類樣例對比少數(shù)類樣例x0在實際輸出上的變化量，則其可表示如下：

若其中的激活函數(shù)G采用的是連續(xù)函數(shù)，且同時相鄰樣例在特征空間上的變化量Δxj，隱層權(quán)重與偏置的l2范數(shù)||a||和||b||，以及輸出權(quán)重矩陣的l2范數(shù)||β||均足夠小，可保證兩個鄰近樣例實際輸出的變化量Δf(xj)足夠小?；仡櫴剑?），假定輸出權(quán)重矩陣 β已預(yù)先確定，則該致密區(qū)間的樣例子集Qsub的均方訓(xùn)練誤差可表示為：

為最小化該子集的均方訓(xùn)練誤差，可通過下式求解：

對上式進(jìn)行求解，可得該子區(qū)間內(nèi)的少數(shù)類樣例的實際輸出為：

2.3 加權(quán)極限學(xué)習(xí)機(jī)及其有效性分析

為有效緩解樣例不平衡分布對ELM所產(chǎn)生的負(fù)面影響，Zong等人[11]借鑒代價敏感學(xué)習(xí)的思想，提出了一種加權(quán)極限學(xué)習(xí)機(jī)算法，即WELM算法。該算法通過為不同類樣例賦予不同權(quán)重，從而改變懲罰因子的方式，有效降低了少數(shù)類樣例被錯分的概率。在WELM算法中，式（6）被改寫為如下形式：

其中，W為一個N×N的對角陣；Wii為第i個訓(xùn)練樣例所對應(yīng)的權(quán)重。若對少數(shù)類樣例施以比多數(shù)類樣例更大的權(quán)重，則會增大對其訓(xùn)練誤差的懲罰力度，從而相應(yīng)降低其被誤分的概率。

在文獻(xiàn)[11]中，Zong等人提供了如下兩種權(quán)重分配方法：

其中，#(ti)和AVG分別代表ti類的訓(xùn)練樣例數(shù)及所有類的平均訓(xùn)練樣例數(shù)。顯然，無論對于上述哪種權(quán)重分配方式，少數(shù)類樣例都會被賦予更大的權(quán)重，且類不平衡比率越高，不同類樣例間的權(quán)重比也將越高。

接下來，采用2.2節(jié)中所提出的理論分析框架，對算法的有效性進(jìn)行分析。設(shè)少數(shù)類樣例權(quán)重為多數(shù)類樣例權(quán)重的M倍，則式（11）可被改寫為：

為最小化加權(quán)訓(xùn)練誤差，可通過以下偏導(dǎo)式求解：

對上式進(jìn)行求解，可得封閉區(qū)間內(nèi)少數(shù)類樣例的輸出為：

由上式可見，當(dāng)權(quán)重比M與封閉區(qū)間內(nèi)的類不平衡比S十分接近時，該少數(shù)類樣例將輸出一個非常接近于0的值，即表明該樣例將出現(xiàn)于所訓(xùn)練的實際分類面附近。顯然采用該方法可有效緩解樣例不平衡分布對ELM性能所產(chǎn)生的負(fù)面影響。

3 本文算法

3.1 基本思想

盡管WELM算法能在一定程度上提升ELM在類不平衡數(shù)據(jù)上的分類性能，但其僅依照類不平衡比率為每類樣例分配一個統(tǒng)一的權(quán)重，而沒有考慮樣例在特征空間中的具體分布情況，故性能往往難以達(dá)到最優(yōu)。且根據(jù)文獻(xiàn)[14]所述，數(shù)據(jù)集中往往存在或多或少的噪聲樣例與離群樣例，它們的出現(xiàn)將會進(jìn)一步影響加權(quán)算法的性能。因此，本文擬借鑒文獻(xiàn)[14]的思想，引入模糊集的概念，充分挖掘每個樣例在特征空間中的分布信息，并對其各自的權(quán)重進(jìn)行模糊化與個性化設(shè)置，從而最大化分類性能。

3.2 隸屬函數(shù)的設(shè)計

眾所周知，對于一個模糊加權(quán)算法而言，影響其性能的最關(guān)鍵因素即是隸屬函數(shù)設(shè)計的合理性，故針對本文所要處理的類不平衡問題，在設(shè)計隸屬函數(shù)時主要應(yīng)考慮以下兩個因素的影響：（1）類不平衡比率；（2）樣本在特征空間所處的位置。

首先，考慮類不平衡比率的影響。假設(shè)在訓(xùn)練集上的整體類不平衡比率的倒數(shù)為r，即少數(shù)類與多數(shù)類樣本數(shù)之比為r，則可將兩類樣本的隸屬函數(shù)分別寫為：

接下來，考慮樣本在特征空間的具體分布信息，為不同樣本分配合理的評估函數(shù)值。借鑒文獻(xiàn)[14]的做法，分別以樣本距質(zhì)心距離及樣本至分類面距離兩個評估標(biāo)準(zhǔn)設(shè)計了如下4種評估函數(shù)。

（1）基于質(zhì)心距離的線性衰減評估函數(shù)

（2）基于質(zhì)心距離的指數(shù)化衰減評估函數(shù)

其中，α為調(diào)控因子，其取值范圍在(0,1]之間，在實際應(yīng)用中，該參數(shù)既可根據(jù)經(jīng)驗設(shè)定，也可采用內(nèi)部多折交叉驗證法選取。與線性衰減評估函數(shù)一樣，指數(shù)化的衰減評估函數(shù)的取值范圍也在(0,1]之間，且距質(zhì)心越遠(yuǎn)的樣本，其被分配的權(quán)重也越小。

（3）基于分類面距離的線性衰減評估函數(shù)

（4）基于分類面距離的指數(shù)化衰減評估函數(shù)

與基于質(zhì)心距離的指數(shù)化衰減評估函數(shù)相同，該函數(shù)也是將權(quán)重測度做了指數(shù)化處理，其與前者的唯一區(qū)別在于其測試的是樣本至初始分類面而非質(zhì)心的距離。

通過對上述評估函數(shù)進(jìn)行分析，可以看出其優(yōu)點(diǎn)在于：（1）充分挖掘了訓(xùn)練樣本的先驗分布信息，并可根據(jù)不同樣本的重要度對其權(quán)重進(jìn)行個性化的設(shè)置；（2）對噪聲樣本與離群樣本賦予了較小的權(quán)重，可最大限度降低其對所訓(xùn)練分類器質(zhì)量的負(fù)面影響。綜上，可對各類模糊加權(quán)準(zhǔn)則的隸屬函數(shù)進(jìn)行總結(jié)，如表1所示。

Table 1 Membership functions of 4 fuzzy weighted rules表1 4種模糊加權(quán)準(zhǔn)則的隸屬函數(shù)

在表1中，F(xiàn)WELM-CL表示基于質(zhì)心距離線性衰減評估函數(shù)的模糊加權(quán)準(zhǔn)則，F(xiàn)WELM-CE表示基于質(zhì)心距離指數(shù)化衰減評估函數(shù)的模糊加權(quán)準(zhǔn)則，F(xiàn)WELM-HL表示基于分類面距離線性衰減評估函數(shù)的模糊加權(quán)準(zhǔn)則，而FWELM-HE則表示基于分類面距離指數(shù)化衰減評估函數(shù)的模糊加權(quán)準(zhǔn)則，上述各準(zhǔn)則均建立在ELM分類器基礎(chǔ)上。

3.3 本文算法描述

采用上一節(jié)所提供的4種模糊加權(quán)準(zhǔn)則，給出了如下兩大類共4種模糊加權(quán)極限學(xué)習(xí)機(jī)算法的一般性描述。

算法1基于質(zhì)心距離測度的不平衡模糊加權(quán)極限學(xué)習(xí)機(jī)

輸入：訓(xùn)練樣本集X={(xi,yi)|i=1,2,…,N}，隱層節(jié)點(diǎn)數(shù)L，懲罰因子C，內(nèi)部交叉驗證的折數(shù)E。

輸出：所訓(xùn)練的分類器FWELM-C。

步驟1對原始的訓(xùn)練樣本集X進(jìn)行劃分，分別得到少數(shù)類樣本集X+及多數(shù)類樣本集X-。

步驟2分別計算X+及X-的質(zhì)心位置，記為cen+及cen-。

步驟3若采用線性衰減評估函數(shù)，則計算每個樣本xi與其同類質(zhì)心的歐式距離dceni，從中選出距離兩類質(zhì)心的最遠(yuǎn)距離，并采用式（21）計算各個樣本的評估函數(shù)值(xi)，最后采用表1中FWELM-CL所提供的方法計算每個樣本的隸屬函數(shù)值，設(shè)置模糊加權(quán)矩陣W；若采用指數(shù)化的衰減評估函數(shù)，則計算每個樣本xi與其同類質(zhì)心的歐式距離dceni，預(yù)設(shè)調(diào)控參數(shù)α的取值范圍及取值間隔λ，并將訓(xùn)練樣本集X隨機(jī)均分為E折，采用式（22），以內(nèi)部E折交叉驗證的方式確定最優(yōu)的調(diào)控參數(shù)值β，最后采用已確定的最優(yōu)參數(shù)α計算訓(xùn)練集X中各個樣本的評估函數(shù)值(xi)，并進(jìn)一步采用表1中FWELM-CE所提供的方法計算每個樣本的隸屬函數(shù)值，對模糊加權(quán)矩陣W進(jìn)行設(shè)置。

步驟4以L和C作為參數(shù)，調(diào)用WELM算法[11]訓(xùn)練分類器FWELM-C。

算法2基于分類面距離測度的不平衡模糊加權(quán)極限學(xué)習(xí)機(jī)

輸入：訓(xùn)練樣本集X={(xi,yi)|i=1,2,…,N}，隱層節(jié)點(diǎn)數(shù)L，懲罰因子C，內(nèi)部交叉驗證的折數(shù)E。

輸出：所訓(xùn)練的分類器FWELM-H。

步驟1對原始的訓(xùn)練樣本集X進(jìn)行劃分，分別得到少數(shù)類樣本集X+及多數(shù)類樣本集X-。

步驟2以L和C作為參數(shù)，調(diào)用原始的ELM算法訓(xùn)練一個分類器。

步驟3若采用線性衰減評估函數(shù)，則計算每個樣本在所訓(xùn)練分類器上實際輸出值的絕對值，將其作為距離測度，并從中找出各類樣本至分類超平面的最大距離，進(jìn)而采用式（23）計算各個樣本的評估函數(shù)值(xi)，最后采用表1中FWELM-HL所提供的方法計算每個樣本的隸屬函數(shù)值，設(shè)置模糊加權(quán)矩陣W；若采用指數(shù)化的衰減評估函數(shù)，則計算每個樣本在所訓(xùn)練分類器上實際輸出值的絕對值，將其作為距離測度，并預(yù)設(shè)調(diào)控參數(shù)α的取值范圍及取值間隔λ，將訓(xùn)練樣本集X隨機(jī)均分為E折，采用式（24），以內(nèi)部E折交叉驗證的方式確定最優(yōu)的調(diào)控參數(shù)值α，最后采用已確定的最優(yōu)參數(shù)α計算訓(xùn)練集X中各個樣本的評估函數(shù)值(xi)，并進(jìn)一步采用表1中FWELM-HE所提供的方法計算每個樣本的隸屬函數(shù)值，對模糊加權(quán)矩陣W進(jìn)行設(shè)置。

步驟4以L和C作為參數(shù)，調(diào)用WELM算法[11]訓(xùn)練分類器FWELM-H。

從上述算法流程可以看出，與傳統(tǒng)的WELM算法相比，無論是采用線性衰減評估函數(shù)，還是指數(shù)化的衰減評估函數(shù)，算法的時間復(fù)雜度都會有一定幅度的增加。具體到線性衰減評估函數(shù)，由于其僅涉及到每個樣本與質(zhì)心間距離的度量以及最大距離的選取，故其在時間復(fù)雜度上的增量為O(N)，即其僅與訓(xùn)練樣本的規(guī)模N有關(guān)。而對于指數(shù)化的衰減評估函數(shù)，由于加入了一個內(nèi)部交叉驗證的參數(shù)尋優(yōu)過程，必然使其時間復(fù)雜度大幅增加，具體的增量為O(EN/λ)，即其不但與訓(xùn)練樣本數(shù)有關(guān)，同時也與參數(shù)α的調(diào)整步長λ及內(nèi)部交叉驗證的折數(shù)E密切相關(guān)。折數(shù)越大，步長越小，則時間復(fù)雜度自然也越高。當(dāng)然，基于“天下沒有免費(fèi)午餐”理論[21]，這些增加的時間開銷也有助于幫助人們找到更優(yōu)的距離測度，從而使分類性能得到進(jìn)一步提升。

4 實驗結(jié)果與討論

4.1 數(shù)據(jù)集與參數(shù)設(shè)置

采用從Keel數(shù)據(jù)倉庫[19]中隨機(jī)選取的20個二類不平衡數(shù)據(jù)集對本文算法及其比較算法的性能進(jìn)行了測試。這些數(shù)據(jù)集具有不同的樣例數(shù)、特征數(shù)與類不平衡比率，具體信息如表2所示。

本文實驗的硬件環(huán)境為：Intel酷睿i53210M，CPU主頻2.2 GHz，內(nèi)存4 GB，硬盤1 TB；操作系統(tǒng)為Windows 7；編程環(huán)境為Matlab2013a。

為展示本文算法的有效性，將其與多個算法進(jìn)行了實驗比較，包括ELM[3]、WELM1[11]、WELM2[11]、RUSELM、ROS-ELM[9]及SMOTE-ELM[8]。同時，為保證比較結(jié)果的公正性，本文對不同算法的參數(shù)進(jìn)行了統(tǒng)一設(shè)置，其中ELM中隱層節(jié)點(diǎn)數(shù)L及懲罰因子C均給定了統(tǒng)一的取值范圍，采用Grid Search策略確定最優(yōu)的參數(shù)組合，具體取值范圍為L∈{20,40,…, 400}，C∈{2-20,2-18,…,220}。此外，考慮到ELM算法具有隨機(jī)性，故對上述每種算法，其分類結(jié)果均以10次外部隨機(jī)5折交叉驗證取均值的方式給出。針對本文算法，其特有的4個參數(shù)α、λ、E及Δ參照文獻(xiàn)[14]進(jìn)行設(shè)定，即α的取值范圍為[0.1,1.0]，取值間隔λ為0.1，內(nèi)部交叉驗證折數(shù)E取值為5，Δ的取值為10-6。SMOTE算法中最重要的參數(shù)k參照文獻(xiàn)[12]將其設(shè)置為缺省值5。除整體分類精度Accuracy外，本文也采用類不平衡學(xué)習(xí)領(lǐng)域中最為常用的兩種性能評價測度F-measure和G-mean來比較各類算法的性能，有關(guān)這兩種性能測度，可參見文獻(xiàn)[15]。

Table 2 Information of used datasets in this paper表2 本文所用數(shù)據(jù)集信息

4.2 結(jié)果與討論

圖2分別展示了各類基于ELM的不平衡學(xué)習(xí)算法在Accuracy、F-measure及G-mean等3種測度上的實驗結(jié)果。從該圖的比較結(jié)果可以得出如下結(jié)論：

（1）與傳統(tǒng)的ELM算法相比，各種不平衡學(xué)習(xí)算法不但無助于提升分類的整體精度，而且通常還會導(dǎo)致這一測度值下降。尤其在那些不平衡比率較高的數(shù)據(jù)集上，其性能下降的幅度還往往較大。事實上，這一現(xiàn)象并不難解釋：傳統(tǒng)分類器通常是以整體錯分率最小為訓(xùn)練目標(biāo)，而不平衡學(xué)習(xí)算法則追求不同類樣本在分類精度上的平衡，故在正常情況下，前者的精度必然高于后者，這也是在不平衡學(xué)習(xí)領(lǐng)域為何通常不采用整體分類精度作為性能評價測度的主要原因。

（2）從F-measure和G-mean兩種測度上可以看出，在絕大多數(shù)不平衡數(shù)據(jù)集上，無論采用采樣技術(shù)、傳統(tǒng)加權(quán)技術(shù)還是模糊加權(quán)技術(shù)，均可有效緩解不平衡分布對分類器性能所產(chǎn)生的負(fù)面影響。上述技術(shù)與ELM算法相比，在性能上均可得到或多或少的提高。

（3）與隨機(jī)降采樣技術(shù)RUS相比，采用過采樣技術(shù)ROS或SMOTE通常能獲得更好的分類性能，尤其在如poker-8_vs_6和abalone19這樣的極度不平衡數(shù)據(jù)集上，這種現(xiàn)象表現(xiàn)得要更為明顯。這一現(xiàn)象其實易于解釋：因為在極度不平衡的數(shù)據(jù)集上進(jìn)行隨機(jī)降采樣，會移除大量包含有重要分類信息的多數(shù)類樣本，使訓(xùn)練集的絕對樣例規(guī)模大幅減小，從而導(dǎo)致生成質(zhì)量較差的分類模型。

（4）與隨機(jī)過采樣技術(shù)ROS相比，SMOTE策略并未展現(xiàn)出明顯更優(yōu)的性能，盡管根據(jù)前人研究，SMOTE能有效解決ROS易于出現(xiàn)過適應(yīng)的問題。究其原因，不難發(fā)現(xiàn)：ELM具有較強(qiáng)的泛化性能，故其可有效抵制過適應(yīng)現(xiàn)象的出現(xiàn)[3-4]。

（5）傳統(tǒng)加權(quán)策略僅能獲得與過采樣策略大致相當(dāng)?shù)男阅?，對兩種傳統(tǒng)的加權(quán)策略進(jìn)行對比，會發(fā)現(xiàn)WELM1往往在G-mean測度上表現(xiàn)得更好，而WELM2在F-measure上則有著明顯更為優(yōu)異的表現(xiàn)。事實上，該現(xiàn)象的出現(xiàn)與二者的權(quán)重分配規(guī)則有著密切的聯(lián)系，前者調(diào)整得更為激進(jìn)，而后者則采用了相對溫和的調(diào)整策略。

（6）在某些數(shù)據(jù)集上，采用不平衡學(xué)習(xí)算法不但難以提高分類性能，甚至?xí)斐煞诸愋阅艿南陆?，如winconsin數(shù)據(jù)集。需要從數(shù)據(jù)分布的角度對這一現(xiàn)象加以解釋，因不平衡數(shù)據(jù)對分類器產(chǎn)生危害的大小是由多因素所決定的，如不平衡比率、不同類樣本在特征空間的離散度、訓(xùn)練樣本的總規(guī)模以及噪聲樣本的比例等。相信在上述數(shù)據(jù)集上，兩類樣本的離散度應(yīng)該較大，且噪聲樣本的比例較小，故并未對原始分類器產(chǎn)生性能上的危害。

Fig.2 Comparative results of various algorithms onAccuracy,F-measure and G-mean圖2 各類算法Accuracy、F-measure及G-mean測度上的實驗比較結(jié)果

（7）與傳統(tǒng)的不平衡學(xué)習(xí)算法相比，本文所采用的4種模糊加權(quán)算法在性能上均有較大幅度的提升，尤其是基于分類面距離測度的兩種算法表現(xiàn)得更為優(yōu)異，其在14個數(shù)據(jù)集上獲得了最高的F-measure值，在12個數(shù)據(jù)集上獲得了最高的G-mean值。由此可見，對處于類重疊區(qū)域的樣例施以較大的權(quán)重更易于獲得精細(xì)且公正的分類面。

（8）對比兩類評估函數(shù)，指數(shù)化的衰減評估函數(shù)表現(xiàn)明顯更優(yōu)。原因在于其通過調(diào)整步長來選取最優(yōu)的距離度量標(biāo)準(zhǔn)，從而能更好地契合樣本的先驗分布。當(dāng)然，這種性能上的提升是以更多的時空代價換取而來的。

進(jìn)一步，在表3中給出了10種比較算法在各數(shù)據(jù)集上的運(yùn)行時間。從該表可以看出:

（1）對任一算法而言，其運(yùn)行時間均與樣本規(guī)模密切相關(guān)，樣本規(guī)模越大，所需花費(fèi)的時間也越多。

Table 3 Running time of various algorithms表3 各類算法的運(yùn)行時間比較 s

（2）RUS-ELM算法在每個數(shù)據(jù)集上所花費(fèi)的時間幾乎都是最少的。這一現(xiàn)象在那些極度不平衡數(shù)據(jù)集上表現(xiàn)得尤為明顯，這主要是大量多數(shù)類樣本被刪除所致。

（3）與ELM算法相比，兩種WELM算法的時間開銷通常要更大。這主要是由于在式（7）的計算中添加了模糊加權(quán)矩陣W所致，且其時間開銷與樣本規(guī)模線性相關(guān)。

（4）與ROS-ELM算法相比，SMOTE-ELM算法的時間開銷明顯要更大。其主要原因在于前者僅是簡單復(fù)制現(xiàn)有樣本，而后者則要做大量的距離計算及排序操作。

（5）本文所提出的幾種模糊加權(quán)算法的時間復(fù)雜度明顯高于其他算法。究其原因不難發(fā)現(xiàn)，上述算法需對每個樣本單獨(dú)進(jìn)行計算，進(jìn)而做個性化的加權(quán)操作，因此不可避免地消耗了大量的計算資源。

（6）采用指數(shù)化衰減函數(shù)的加權(quán)算法在時間復(fù)雜度上要明顯高于采用線性衰減函數(shù)的算法。這主要是因為前者增加了一個內(nèi)部交叉驗證的參數(shù)尋優(yōu)過程所致。

接下來，采用FSVM-CIL系列算法[14]與本文算法進(jìn)行了實驗比較。特別地，在FSVM-CIL系列算法中，除使用本文的4種評估函數(shù)外，還采用了基于超球中心距離測度的線性衰減評估函數(shù)（FSVM-SL）和指數(shù)化的衰減評估函數(shù)（FSVM-SE）。參照文獻(xiàn)[14]的做法，SVM采用RBF核函數(shù)，參數(shù)通過Grid Search策略確定。鑒于前文已分析得出分類精度不適于評價不平衡學(xué)習(xí)算法性能的結(jié)論，故在本組實驗中僅給出了各算法在F-measure和G-mean測度上的實驗比較結(jié)果，分別如表4和表5所示，其中每個數(shù)據(jù)集上的最優(yōu)結(jié)果以粗體顯示。

從表4及表5的結(jié)果可以看出，與FSVM-CIL系列算法相比，本文所提出的FWELM系列算法并未體現(xiàn)出弱勢，或者說二者的性能大致相當(dāng)。具體到F-measure測度，F(xiàn)WELM系列算法在9個數(shù)據(jù)集上獲得

了最優(yōu)結(jié)果，F(xiàn)SVM-CIL系列算法則獲得了11個最優(yōu)結(jié)果。而在G-mean測度上，F(xiàn)WELM與FSCM-CIL系列算法在全部20個數(shù)據(jù)集上所獲得的最優(yōu)結(jié)果之比則為12∶8。同時，也觀察到在不同數(shù)據(jù)集上，兩類算法所得到的結(jié)果往往相差較大，如在vowel0和shuttle_2_vs_5數(shù)據(jù)集上，F(xiàn)SVM-CIL系列算法的性能要明顯優(yōu)于FWELM系列算法，而在pima和abalone19數(shù)據(jù)集上，結(jié)果則恰好完全相反。相信上述現(xiàn)象的出現(xiàn)是由分類器本身的特性所決定的，ELM和SVM均各自擅長處理不同分布的數(shù)據(jù)集。此外，在實驗中也對上述兩個系列算法的運(yùn)行時間進(jìn)行了記錄，比較結(jié)果如表6所示。

Table 4 Comparative results of FWELM and FSVM-CIL series algorithms on F-measure表4 FWELM與FSVM-CIL系列算法在F-measure測度上的實驗比較結(jié)果

Table 5 Comparative results of FWELM and FSVM-CIL series algorithms on G-mean表5FWELM與FSVM-CIL系列算法在G-mean測度上的實驗比較結(jié)果

從表6的結(jié)果中不難看出，當(dāng)采用同一評估函數(shù)時，F(xiàn)SVM-CIL系列算法往往需要消耗更多的訓(xùn)練時間，且隨著樣本集規(guī)模的增長，特征數(shù)的增加，運(yùn)行時間上的差距也會呈現(xiàn)逐步拉大的趨勢。該現(xiàn)象較易從理論上得到解釋，因ELM分類器是基于最小二乘的思想，故可直接計算得到，而SVM則需要解決一個相對復(fù)雜的二次優(yōu)化問題。因此與FSVM-CIL系列算法相比，本文所提出的FWELM系列算法有明顯更低的時間復(fù)雜度，可在一定程度上滿足實際應(yīng)用的需要。

5 結(jié)束語

本文從理論上分析了樣例不平衡分布對極限學(xué)習(xí)機(jī)性能產(chǎn)生危害的原因，并在該理論框架下探討了傳統(tǒng)的加權(quán)極限學(xué)習(xí)機(jī)算法的有效性及其固有缺陷，提出了4種模糊加權(quán)極限學(xué)習(xí)機(jī)算法。上述算法能有效抽取訓(xùn)練集中樣例的先驗分布信息，并據(jù)此對各樣例的重要度進(jìn)行評估，從而對每個樣例的權(quán)重進(jìn)行模糊化與個性化的設(shè)置，以達(dá)到排除噪聲，離群樣例的影響及細(xì)化分類面的目的。采用20個二類不平衡數(shù)據(jù)集對上述方法的有效性與可行性進(jìn)行了驗證，實驗結(jié)果突出展示了所提算法的以下兩個特點(diǎn)：相比采用同種分類器的其他不平衡學(xué)習(xí)算法，能有效提升分類性能；相比采用不同分類器的同種學(xué)習(xí)算法，通常具有更小的時空開銷。

Table 6 Running time of FWELM and FSVM-CIL series algorithms表6FWELM與FSVM-CIL系列算法的運(yùn)行時間比較 s

在未來的研究工作中，希望能在以下幾方面做一些擴(kuò)展性的工作：

（1）對現(xiàn)有隸屬函數(shù)進(jìn)行改進(jìn)，將其應(yīng)用于多類不平衡分類問題。

（2）在充分挖掘全局分布信息的基礎(chǔ)上，擬進(jìn)一步結(jié)合樣例的局部先驗分布信息，設(shè)計更為合理的隸屬分配函數(shù)，從而使分類面得到進(jìn)一步細(xì)化，性能得到進(jìn)一步提升。

（3）將本文算法應(yīng)用到各種實際領(lǐng)域中，從而對其有效性做進(jìn)一步評估。

[1]Huang Guangbin,Zhu Qinyu,Siew C K.Extreme learning machine:theory and applications[J].Neurocomputing,2006, 70(1/3):489-501.

[2]Rumelhart D E,Hinton G E,Williams R J.Learning representations by back-propagation errors[J].Nature,1986,323: 533-536.

[3]Huang Guangbin,Zhou Hongming,Ding Xiaojian,et al.Extreme learning machine for regression and multiclass classification[J].IEEE Transactions on System,Man and Cybernetics:Part B Cybernetics,2012,42(2):513-529.

[4]Huang Gao,Huang Guangbin,Song Shiji,et al.Trends in extreme learning machine:a review[J].Neural Networks, 2015,61:32-48.

[5]Choi K,Toh K A,Byun H.Realtime training on mobile devices for face recognition applications[J].Pattern Recognition,2011,44(2):386-400.

[6]Samat A,Du Peijun,Liu Sicong,et al.E2LMs:ensemble extreme learning machines for hyperspectral image classification[J].IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing,2014,7(4):1060-1069.

[7]Wan Can,Xu Zhao,Pinson P,et al.Probabilistic forecasting of wind power generation using extreme learning machine[J]. IEEE Transactions on Power Systems,2014,29(29):1033-1044.

[8]Sun S J,Chang C,Hsu M F.Multiple extreme learning machines for a two-class imbalance corporate life cycle prediction[J].Knowledge-Based Systems,2013,39(3):214-223.

[9]Vong C M,Ip W F,Wong P K,et al.Predicting minority class for suspended particulate matters level by extreme learning machine[J].Neurocomputing,2014,128(5):136-144.

[10]Lu Huijuan,An Chunlin,Ma Xiaoping,et al.Disagreement measure based ensemble of extreme learning machine for gene expression data classification[J].Chinese Journal of Computers,2013,36(2):341-348.

[11]Zong Weiwei,Huang Guangbin,Chen Yiqiang.Weighted extreme learning machine for imbalance learning[J].Neurocomputing,2013,101(3):229-242.

[12]Chawla N V,Bowyer K W,Hall L O.SMOTE:synthetic minority over-sampling technique[J].Journal of Artificial Intelligence Research,2002,16(1):321-357.

[13]Zeng Zhiqiang,Wu Qun,Liao Beishui,et al.A classification method for imbalance data set based on kernel SMOTE [J].Acta Electronica Sinica,2009,37(11):2489-2495.

[14]Batuwita R,Palade V.FSVM-CIL:fuzzy support vector machines for class imbalance learning[J].IEEE Transactions on Fuzzy Systems,2010,18(3):558-571.

[15]Yu Hualong,Mu Chaoxu,Sun Changyin,et al.Support vector machine-based optimized decision threshold adjustment strategy for classifying imbalanced data[J].Knowledge-Based Systems,2015,76:67-78.

[16]Maldonado S,Montecinos C.Robust classification of imbalanced data using one-class and two-class SVM-based multiclassifiers[J].Intelligent DataAnalysis,2014,18(1):95-112.

[17]Yu Hualong,Ni Jun.An improved ensemble learning method for classifying high-dimensional and imbalanced biomedicine data[J].IEEE/ACM Transactions on Computational Biology and Bioinformatics,2014,11(4):657-666.

[18]Park Y,Ghosh J.Ensembles of α-trees for imbalanced classification problems[J].IEEE Transactions on Knowledge and Data Engineering,2014,26(1):131-143.

[19]Alcalá-Fdez J,Fernandez A,Luengo J,et al.KEEL datamining software tool:data set repository,integration of algorithms and experimental analysis framework[J].Journal of Multiple-Valued Logic and Soft Computing,2011,17(2/3): 255-287.

[20]Yu Hualong,Sun Changyin,Yang Wankou,et al.AL-ELM: one uncertainty-based active learning algorithm using extreme learning machine[J].Neurocomputing,2015,166:140-150.

[21]Wolpert D H,Macready W G.No free lunch theorems for optimization[J].IEEE Transactions on Evolutionary Computation,1997,1(1):67-82.

附中文參考文獻(xiàn)：

[10]陸慧娟,安春霖,馬小平,等.基于輸出不一致測度的極限學(xué)習(xí)機(jī)集成的基因表達(dá)數(shù)據(jù)分類[J].計算機(jī)學(xué)報,2013, 36(2):341-348.

[13]曾志強(qiáng),吳群,廖備水,等.一種基于核SMOTE的非平衡數(shù)據(jù)集分類方法[J].電子學(xué)報,2009,37(11):2489-2495.

YU Hualong was born in 1982.He received the Ph.D.degree in computer science from Harbin Engineering University in 2010.Now he is an associate professor and M.S.supervisor at Jiangsu University of Science and Technology. His research interests include machine learning and data mining,etc.

于化龍（1982—），男，黑龍江哈爾濱人，2010年于哈爾濱工程大學(xué)獲得博士學(xué)位，現(xiàn)為江蘇科技大學(xué)副教授、碩士生導(dǎo)師，主要研究領(lǐng)域為機(jī)器學(xué)習(xí)，數(shù)據(jù)挖掘等。發(fā)表學(xué)術(shù)論文50余篇，其中被SCI或EI檢索40余篇，主持包括國家自然科學(xué)基金、江蘇省自然科學(xué)基金、國家博士后特別資助計劃在內(nèi)的科研項目7項，參與國家級、省部級及市廳級項目多項。

QI Yunsong was born in 1967.He received the Ph.D.degree in computer science from Nanjing Institute of Technology in 2011.Now he is a professor and M.S.supervisor at Jiangsu University of Science and Technology.His research interests include pattern recognition and signal processing,etc.

祁云嵩（1967—），男，江蘇如皋人，2011年于南京理工大學(xué)獲得博士學(xué)位，現(xiàn)為江蘇科技大學(xué)教授、碩士生導(dǎo)師,主要研究領(lǐng)域為模式識別，信號處理等。發(fā)表學(xué)術(shù)論文20余篇，其中被SCI或EI檢索10余篇，主持國家自然科學(xué)基金1項，參與各類科研項目多項。

YANG Xibei was born in 1980.He received the Ph.D.degree in computer science from Nanjing Institute of Technology in 2010.Now he is an associate professor and M.S.supervisor at Jiangsu University of Science and Technology.His research interests include machine learning and granular computing,etc.

楊習(xí)貝（1980—），男，江蘇鎮(zhèn)江人，2010年于南京理工大學(xué)獲得博士學(xué)位，現(xiàn)為江蘇科技大學(xué)副教授、碩士生導(dǎo)師，主要研究領(lǐng)域為機(jī)器學(xué)習(xí)，粒計算等。發(fā)表學(xué)術(shù)論文100多篇，其中被SCI或EI檢索60余篇，主持國家自然科學(xué)基金2項，江蘇省自然科學(xué)基金1項，參與各類科研項目多項。

ZUO Xin was born in 1980.She received the Ph.D.degree in computer science from Southeast University in 2014. Now she is a lecturer at Jiangsu University of Science and Technology.Her research interests include pattern recognition and computer vision,etc.

左欣（1980—），女，江蘇鎮(zhèn)江人，2014年于東南大學(xué)獲得博士學(xué)位，現(xiàn)為江蘇科技大學(xué)講師，主要研究領(lǐng)域為模式識別，計算機(jī)視覺等。發(fā)表學(xué)術(shù)論文10余篇，其中被EI檢索6篇，主持江蘇省自然科學(xué)基金1項，參與各類科研項目多項。

Research on Class Imbalance Fuzzy Weighted Extreme Learning Machine Algorithm*

YU Hualong1,2+,QI Yunsong1,YANG Xibei1,ZUO Xin1
1.School of Computer Science and Engineering,Jiangsu University of Science and Technology,Zhenjiang,Jiangsu 212003,China
2.College ofAutomation,Southeast University,Nanjing 210096,China
+Corresponding author:E-mail:yuhualong@just.edu.cn

Firstly,this paper analyzes the reason that the performance of extreme learning machine(ELM)is destroyed by imbalanced instance distribution in theory.Then,based on the same theoretical framework,this paper discusses the effectiveness and inherent shortcomings of the weighted extreme learning machine(WELM).Nextly, profiting from the idea of fuzzy set,this paper proposes four fuzzy weighted extreme learning machine(FWELM) algorithms to deal with class imbalance problem.Finally,this paper verifies the effectiveness and feasibility of these four FWELM algorithms by the experiments constructing on 20 baseline binary-class imbalanced data sets.The experimental results indicate that the proposed algorithms can often acquire better classification performance than WELM algorithm and several traditional class imbalance learning algorithms in the context of ELM.In addition,in contrastwith fuzzy support vector machine for class imbalance learning(FSVM-CIL)series algorithms,the proposed algorithms can produce the comparable classification performance,but always consume less training time.

extreme learning machine;class imbalance learning;fuzzy weighting;prior distribution information

10.3778/j.issn.1673-9418.1603094

A

TP183

*The National Natural Science Foundation of China under Grant Nos.61305058,61471182,61572242(國家自然科學(xué)基金);the Natural Science Foundation of Jiangsu Province under Grant Nos.BK20130471,BK20150470(江蘇省自然科學(xué)基金);the Postdoctoral Science Foundation of China under Grant Nos.2013M540404,2015T80481(中國博士后科學(xué)基金);the Postdoctoral Research Funds of Jiangsu Province under Grant No.1401037B(江蘇省博士后基金).

Received 2016-03,Accepted 2016-05.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-05-19,http://www.cnki.net/kcms/detail/11.5602.TP.20160519.1513.008.html

YU Hualong,QI Yunsong,YANG Xibei,et al.Research on class imbalance fuzzy weighted extreme learning machine algorithm.Journal of Frontiers of Computer Science and Technology,2017,11(4)：619-632.