于化龍，祁云嵩，楊習貝，左 欣

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

2.東南大學 自動化學院，南京 210096

類不平衡模糊加權極限學習機算法研究*

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

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

2.東南大學 自動化學院，南京 210096

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

極限學習機；類不平衡學習；模糊加權；先驗分布信息

1 引言

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

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

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

2 理論分析

2.1 極限學習機

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

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

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

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

其中：

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

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

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

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

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

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

2.2 類不平衡分布對極限學習機性能的影響機理

眾所周知，對于ELM而言，那些在特征空間中相鄰較近的樣例通常會有極其相似的輸出值，而在類重疊區(qū)域，多數(shù)類樣例會將少數(shù)類樣例緊密地包裹其中，它們的輸出值極為接近。為同時保證所訓練的ELM具有較強的泛化能力與較低的訓練誤差，少數(shù)類必然做出更多的犧牲。不失一般性，假設分類任務只有兩個類別，其中在ELM中，少數(shù)類對應的期望輸出為1，而多數(shù)類的期望輸出為-1。考慮特征空間中兩類樣例的重疊區(qū)域，從該區(qū)域分割出一個足夠小且樣例分布致密的子區(qū)域，在這一區(qū)域中多數(shù)類樣例有S個，而少數(shù)類樣例數(shù)恰好只有1個，即在此區(qū)域中，不平衡比率為S，則根據(jù)ELM的構造機理，這S+1個樣例有極其近似的輸出值。設該少數(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訓練完成后，這些樣例的實際輸出可表示為：

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

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

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

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

2.3 加權極限學習機及其有效性分析

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

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

在文獻[11]中，Zong等人提供了如下兩種權重分配方法：

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

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

為最小化加權訓練誤差，可通過以下偏導式求解：

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

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

3 本文算法

3.1 基本思想

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 本文算法描述

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

算法1基于質(zhì)心距離測度的不平衡模糊加權極限學習機

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

輸出：所訓練的分類器FWELM-C。

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

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

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

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

算法2基于分類面距離測度的不平衡模糊加權極限學習機

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

輸出：所訓練的分類器FWELM-H。

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

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

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

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

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

4 實驗結果與討論

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

采用從Keel數(shù)據(jù)倉庫[19]中隨機選取的20個二類不平衡數(shù)據(jù)集對本文算法及其比較算法的性能進行了測試。這些數(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。

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

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

4.2 結果與討論

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結束語

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

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

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

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

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

（3）將本文算法應用到各種實際領域中，從而對其有效性做進一步評估。

[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.

附中文參考文獻：

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

[13]曾志強,吳群,廖備水,等.一種基于核SMOTE的非平衡數(shù)據(jù)集分類方法[J].電子學報,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年于哈爾濱工程大學獲得博士學位，現(xiàn)為江蘇科技大學副教授、碩士生導師，主要研究領域為機器學習，數(shù)據(jù)挖掘等。發(fā)表學術論文50余篇，其中被SCI或EI檢索40余篇，主持包括國家自然科學基金、江蘇省自然科學基金、國家博士后特別資助計劃在內(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年于南京理工大學獲得博士學位，現(xiàn)為江蘇科技大學教授、碩士生導師,主要研究領域為模式識別，信號處理等。發(fā)表學術論文20余篇，其中被SCI或EI檢索10余篇，主持國家自然科學基金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.

楊習貝（1980—），男，江蘇鎮(zhèn)江人，2010年于南京理工大學獲得博士學位，現(xiàn)為江蘇科技大學副教授、碩士生導師，主要研究領域為機器學習，粒計算等。發(fā)表學術論文100多篇，其中被SCI或EI檢索60余篇，主持國家自然科學基金2項，江蘇省自然科學基金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年于東南大學獲得博士學位，現(xiàn)為江蘇科技大學講師，主要研究領域為模式識別，計算機視覺等。發(fā)表學術論文10余篇，其中被EI檢索6篇，主持江蘇省自然科學基金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(國家自然科學基金);the Natural Science Foundation of Jiangsu Province under Grant Nos.BK20130471,BK20150470(江蘇省自然科學基金);the Postdoctoral Science Foundation of China under Grant Nos.2013M540404,2015T80481(中國博士后科學基金);the Postdoctoral Research Funds of Jiangsu Province under Grant No.1401037B(江蘇省博士后基金).

Received 2016-03,Accepted 2016-05.

CNKI網(wǎng)絡優(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.