李克文 丁勝奪 段鴻杰

（1.中國(guó)石油大學(xué)（華東）計(jì)算機(jī)與通信工程學(xué)院 青島 266580）

（2.中國(guó)石化勝利油田分公司信息中心 東營(yíng) 257000）

1 引言

分類學(xué)習(xí)算法是機(jī)器學(xué)習(xí)中的一項(xiàng)熱點(diǎn)研究?jī)?nèi)容，從傳統(tǒng)的分類算法到新型的衍生算法，解決此類問(wèn)題的方案層出不窮。黃廣斌等［1］在單隱層前饋神經(jīng)網(wǎng)絡(luò)（Single-hidden Layer Feedforward Neural Network，SLFN）的算法基礎(chǔ)上進(jìn)行改進(jìn)提出了極限學(xué)習(xí)機(jī)（Extreme Learning Machine，ELM）算法，針對(duì)傳統(tǒng)反向傳播（BP）神經(jīng)網(wǎng)絡(luò)［2］求解參數(shù)過(guò)多、神經(jīng)網(wǎng)絡(luò)訓(xùn)練時(shí)間消耗大、易陷入局部最優(yōu)等缺陷，該算法以求解線性方程組的方法取代標(biāo)準(zhǔn)算法中梯度下降方法進(jìn)行迭代求解的過(guò)程，求取最小二乘解得到輸出層權(quán)值，簡(jiǎn)化了繁瑣的迭代過(guò)程，形成一種速度快、結(jié)構(gòu)簡(jiǎn)單、泛化性能好、人工干預(yù)少的學(xué)習(xí)算法。該算法常被用于解決分類、回歸以及特征學(xué)習(xí)等問(wèn)題。

Boosting方法［3］是一種經(jīng)典的機(jī)器學(xué)習(xí)方法，在分類問(wèn)題中，提升算法通過(guò)每次迭代的結(jié)果逐步的調(diào)整次輪訓(xùn)練樣本的權(quán)重，將注意力轉(zhuǎn)移到錯(cuò)分樣本上，學(xué)習(xí)多個(gè)弱分類器后將這些弱分類器和相應(yīng)迭代代數(shù)中獲得的參數(shù)值進(jìn)行線性組合，獲得分類性能更強(qiáng)的強(qiáng)分類器。AdaBoost算法是行之有效的一種Boosting算法，它避免了標(biāo)準(zhǔn)Boosting中必須要預(yù)先計(jì)算各弱分類器分類準(zhǔn)確率下限的麻煩，簡(jiǎn)化了模型求解過(guò)程，提升了算法實(shí)用性。經(jīng)典的AdaBoost算法多被用于二分類問(wèn)題的求解，而多分類問(wèn)題在現(xiàn)實(shí)應(yīng)用中更常見(jiàn)且其識(shí)別率更亟待提高?；诖耍瑢daBoost算法擴(kuò)展改進(jìn)為多分類算法是一種可行的方案，現(xiàn)行的改進(jìn)策略主要有兩種［4］：一種方法是在標(biāo)準(zhǔn)算法的基礎(chǔ)上進(jìn)行結(jié)構(gòu)擴(kuò)展，例如AdaBoost.M1算法［5］，該改進(jìn)算法要求每個(gè)分類器的分類正確率必須超過(guò)50%，這在多分類問(wèn)題中對(duì)弱分類器的要求相對(duì)較高，會(huì)導(dǎo)致弱分類器的獲取需要付出較大的時(shí)間消耗甚至無(wú)法集成至達(dá)到目標(biāo)效果的集成分類器。AdaBoost.M2算法［5］也是一種直接擴(kuò)展方法，相對(duì)于前者，該改進(jìn)算法以誤分樣本權(quán)值和來(lái)代替錯(cuò)誤率作為選取弱分類器準(zhǔn)則，該改進(jìn)算法降低了對(duì)弱分類器的要求，弱分類器的選取難度大大減小，同時(shí)提高了對(duì)錯(cuò)分和難分樣本的關(guān)注度，但是，該舉措同時(shí)增加了算法的時(shí)間復(fù)雜度，同時(shí)增加了退化現(xiàn)象發(fā)生的風(fēng)險(xiǎn)。Adaboost.MH［6］是另一種改進(jìn)策略的代表算法，該算法將多分類問(wèn)題分解為一定數(shù)量的二分類問(wèn)題，弱分類器的獲取相對(duì)容易，但該算法的改進(jìn)思想同樣提高了算法的結(jié)構(gòu)復(fù)雜度及時(shí)間復(fù)雜度。針對(duì)上述缺陷，Zhu等［7］提出一種直接擴(kuò)展多分類算法—多類指數(shù)損失函數(shù)逐步添加模型（Stagewise Additive Modeling using a Multi-class Ex?ponential loss function，SAMME），該改進(jìn)算法改進(jìn)了傳統(tǒng)的AdaBoost算法中訓(xùn)練樣本的權(quán)值重分配公式，把對(duì)弱分類器的基本要求降低到分類精度高于1/K（K為類別總數(shù)）即可，胡金海等［8］通過(guò)實(shí)驗(yàn)證明了SAMME算法的有效性，并將該改進(jìn)算法用于發(fā)動(dòng)機(jī)相關(guān)運(yùn)行參數(shù)的數(shù)據(jù)挖掘?qū)崿F(xiàn)故障診斷，并取得了良好的效果。SAMME算法雖降低了弱分類器的選擇難度，但容易將一些效果較差的弱分類器集成到最終的強(qiáng)分類器中，造成強(qiáng)分類器的性能退化。

針對(duì)以上算法的不足，本文利用ELM極限學(xué)習(xí)機(jī)作為弱分類器，使用SAMME算法作為集成策略集成強(qiáng)分類器，并對(duì)SAMME算法的迭代過(guò)程進(jìn)行改進(jìn)，降低其容易引入較差弱分類器的風(fēng)險(xiǎn)，增強(qiáng)最終強(qiáng)分類器的分類性能。

2 ELM和SAMME算法

弱分類器的選取是提升方法中的關(guān)鍵，它決定了最終強(qiáng)分類器的組成，影響最終模型性能。合理有效的集成策略有助于增強(qiáng)最終強(qiáng)分類器的分類精度，使得最終分類模型在不同測(cè)試數(shù)據(jù)上的性能表現(xiàn)更加均衡。本節(jié)簡(jiǎn)要介紹ELM算法和SAMME算法，并進(jìn)行總結(jié)分析。

2.1 ELM算法

式（1）中，βj表示第j個(gè)隱層節(jié)點(diǎn)到網(wǎng)絡(luò)輸出節(jié)點(diǎn)之間的連接權(quán)值；wj=[wj1，wj2，…，wjn]表示輸入節(jié)點(diǎn)和第j個(gè)隱層節(jié)點(diǎn)之間的連接權(quán)值向量；bj是第j個(gè)隱層節(jié)點(diǎn)的偏置。

為了求取最優(yōu)的網(wǎng)絡(luò)參數(shù)w和β，嘗試最小化網(wǎng)絡(luò)的預(yù)測(cè)輸出和樣本真實(shí)值之間的的差值使其為零，即，可轉(zhuǎn)化為

轉(zhuǎn)化為矩陣形式為

式（3）中，H表示網(wǎng)絡(luò)隱含層的輸出向量矩陣，矩陣中的第i列即為相應(yīng)的隱層節(jié)點(diǎn)的擬合輸出值；

在實(shí)際應(yīng)用中，通常訓(xùn)練樣本數(shù)N遠(yuǎn)大于算法隱層的節(jié)點(diǎn)數(shù)，當(dāng)所選取的激活函數(shù)滿足連續(xù)可微的條件，所求網(wǎng)絡(luò)的隱含層參數(shù)w和b在訓(xùn)練過(guò)程中可以視為常數(shù)，無(wú)需調(diào)整網(wǎng)絡(luò)中全部參數(shù)。然后上述模型可以通過(guò)求解最小化問(wèn)題：得到權(quán)值向量β，根據(jù)廣義逆原理，可計(jì)算得：

式（5）中，根據(jù)線性代數(shù)的求解法則需要求解H的廣義逆矩陣H+，H表示隱層輸出矩陣。

2.2 SAMME算法

提升（boosting）算法［9］的核心思想是在每一次迭代過(guò)程中，將注意力集中到錯(cuò)分樣本上，提高錯(cuò)分樣本的權(quán)重，使其在下一輪迭代中得到更多的關(guān)注，為了保持權(quán)值的平衡，相應(yīng)的被正確分類的樣本的權(quán)重會(huì)有下降。在集成策略中，分配給性能優(yōu)異的基分類器較大的權(quán)重，使其在最終的結(jié)果表決中起到較大的作用。SAMME算法的操作流程［10］如下。

Step1給定含N個(gè)樣本的訓(xùn)練數(shù)據(jù)集：( xi，yi)，xi∈Rn，yi∈(1 ，2，…，k)=Y，其中n為樣本維數(shù)k為類別數(shù)，對(duì)訓(xùn)練樣本權(quán)值進(jìn)行等量初始化，并設(shè)定最 大 迭 代 次 數(shù)T D1=( w11，…，w1i，…w1N)，w1i=

Step2對(duì)t=1，2，…，T，執(zhí)行1）～4）。

1）對(duì)經(jīng)過(guò)Dt加權(quán)的訓(xùn)練數(shù)據(jù)進(jìn)行訓(xùn)練，求得使偽誤差率最小的弱分類器ht(x)；

2）計(jì) 算ht(x)的 分 類 錯(cuò) 誤 率 ：

3）計(jì)算ht(x)的系數(shù)

4）訓(xùn)練數(shù)據(jù)集權(quán)值更新：Dt+1=(wt+1，1，…，wt+1，i，…wt+1，N)，其中，式中Zt為規(guī)范化因子，它使訓(xùn)練數(shù)據(jù)在下一輪迭代中的權(quán)值向量滿足概率分布。

Step3構(gòu)建所得弱分類器的線性組合，結(jié)合step2中式（3）所得系數(shù)得到最終強(qiáng)分類器：

3 改進(jìn)的ELM-SAMME算法

為了使SAMME算法在一定迭代次數(shù)下達(dá)到更優(yōu)的分類精度，對(duì)該算法的樣本權(quán)值及基分類器的權(quán)值分配過(guò)程進(jìn)行改進(jìn)，將該計(jì)算法記為IELM-SAMME，該算法的流程圖如圖1所示。

圖1 IELM-SAMME算法流程

Step1對(duì)于給定訓(xùn)練數(shù)據(jù)集：( xi，yi)，xi∈Rm，yi∈(1 ，2，…，k)，其中k為類別數(shù)，初始化樣本的權(quán)重：

Step2接下來(lái)的迭代過(guò)程t=1，2，…，T中，重復(fù)執(zhí)行1）～4）。

1）將帶有訓(xùn)練權(quán)重Dt的訓(xùn)練數(shù)據(jù)帶入ELM模型進(jìn)行擬合訓(xùn)練得到ht(x)。

2）計(jì)算相應(yīng)的權(quán)重誤差：

計(jì)算各個(gè)類別樣本的召回率Rtk，比較得到最低的召回率min Rtk，將該類視為難分類，求取該類別樣本在本次迭代中識(shí)別正確的樣本權(quán)值和

3）根據(jù)ht(xi)在第t輪迭代中分類性能的表現(xiàn)，由2）中誤差和召回率來(lái)決定此弱分類器權(quán)重分配：

4）為下次迭代更新樣本權(quán)值：

這里Zt為規(guī)范化因子，它使訓(xùn)練數(shù)據(jù)在下一輪迭代中的權(quán)值向量Dt+1成為一個(gè)概率分布。

Step3最終的強(qiáng)分類器可以通過(guò)對(duì)所得的弱分類器進(jìn)行多數(shù)投票得到：

4 實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證本文改進(jìn)方法的可行性和有效性，在如表1所示的10個(gè)UCI公共數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，其中不平衡率為少數(shù)類樣本與多數(shù)類樣本數(shù)量的比值。將本文方法首先和極限學(xué)習(xí)機(jī)（ELM）算法、以SVM為 弱 分 類 器 的AdaBoost算 法［11］、標(biāo) 準(zhǔn) 的ELM-SAMME算法的進(jìn)行結(jié)果進(jìn)行比較，本文算法為IELM-SAMME。各方法的參數(shù)設(shè)置如下：ELM中，激活函數(shù)設(shè)置為sigmoid函數(shù)，隱層節(jié)點(diǎn)數(shù)L設(shè)置為 nl（n為輸入節(jié)點(diǎn)數(shù)，l為輸出節(jié)點(diǎn)數(shù)）；SVM-AdaBoost方法中迭代次數(shù)設(shè)置為10。ELM-SAMME及本文算法中的ELM參數(shù)同上，迭代次數(shù)同樣設(shè)置為10。本文實(shí)驗(yàn)算法在8GB內(nèi)存的Intel Core（TM）i7-6700CPU@3.4GHz的計(jì)算機(jī)上運(yùn)行MATLABR2014b進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)過(guò)程中，為了減少初始化參數(shù)隨機(jī)化對(duì)算法性能的影響，進(jìn)行5次4折交叉驗(yàn)證，最后取各算法所有運(yùn)行結(jié)果的均值進(jìn)行性能比較。

在衡量各個(gè)分類算法在不同數(shù)據(jù)集上的分類性能表現(xiàn)時(shí)，僅僅選取準(zhǔn)確率作為最終評(píng)價(jià)標(biāo)準(zhǔn)往往不能真實(shí)反映其分類性能，這是為了避免在不平衡數(shù)據(jù)集上最終評(píng)判結(jié)果的不公平性。在本實(shí)驗(yàn)中，選取G-mean和F1值作為實(shí)驗(yàn)結(jié)果的性能評(píng)價(jià)指標(biāo)［12］，其定義如下：

最終實(shí)驗(yàn)結(jié)果如表2、表3所示，在表1所示的10個(gè)數(shù)據(jù)集上本文的IELM-SAMME方法G-mean值和F1值比單獨(dú)使用ELM算法時(shí)取得效果都要好，這說(shuō)明SAMME算法的應(yīng)用取得了顯著的成效，從結(jié)果中還可以看出改進(jìn)方法尤其對(duì)不平衡率較高的樣本集的識(shí)別效果有了較明顯的提升。將改進(jìn)方法與AdaBoost方法進(jìn)行比較可以看出改進(jìn)方法相比于AdaBoost方法在大部分?jǐn)?shù)據(jù)集上都有提升，尤其在Ecoli等不平衡率較高的數(shù)據(jù)集上的提升尤為明顯。而在平衡數(shù)據(jù)集如Iris上，改進(jìn)方法獲得了與傳統(tǒng)方法相當(dāng)?shù)乃?。該方法與未改進(jìn)的ELM-SAMME算法進(jìn)行比較僅在Iris、Wine等數(shù)據(jù)集上略差于ELM-SAMME方法。

表1 15個(gè)UCI數(shù)據(jù)集及其相關(guān)特征

表2 各算法在10個(gè)數(shù)據(jù)集上的平均G-mean值

表3 各算法在10個(gè)數(shù)據(jù)集上的平均F1值

經(jīng)以上對(duì)比實(shí)驗(yàn)證明了該算法的有效性，然后使用該算法和現(xiàn)行分類算法進(jìn)行比較。此組對(duì)比實(shí)驗(yàn)仍然在表1的10個(gè)UCI公共數(shù)據(jù)集上進(jìn)行，實(shí)驗(yàn)結(jié)果的性能指標(biāo)仍然使用G-mean值和F1值來(lái)評(píng)判。此組對(duì)比實(shí)驗(yàn)加入Over-Bagging［13］、Under?Bagging［14］、EasyEnsemble［15］等算法，實(shí)驗(yàn)結(jié)果如表4、表5所示。由實(shí)驗(yàn)結(jié)果可知，該改進(jìn)方法在其中的6個(gè)數(shù)據(jù)集上均取得了更好的G-mean值，在7個(gè)數(shù)據(jù)集上得到了更好的F1值。在Iris、Ecoli1、Haberman等數(shù)據(jù)集上的G-mean僅次于最優(yōu)值或近似最優(yōu)值，在Haberman、wine等數(shù)據(jù)集上的F1值僅次于最優(yōu)值。這可以解釋為在類如Iris的數(shù)據(jù)集上樣本數(shù)量相對(duì)較少且各類樣本比率相對(duì)平衡，各個(gè)算法模型較容易達(dá)到較好的擬合效果，此時(shí)各個(gè)算法的性能表現(xiàn)極有可能出現(xiàn)持平或存在較小的差距。而改進(jìn)算法在樣本量適中或者較大的數(shù)據(jù)集上表現(xiàn)較為穩(wěn)定和高效，尤其在不平衡率較高的yeast、Abalone等數(shù)據(jù)集上獲得了較其他算法都要好的效果。

表4 各算法在10個(gè)數(shù)據(jù)集上的平均G-mean值

表5 各算法在10個(gè)數(shù)據(jù)集上的平均F1值

5 結(jié)語(yǔ)

本文以極限學(xué)習(xí)機(jī)為弱學(xué)習(xí)器，以SAMME算法為集成策略，在標(biāo)準(zhǔn)的SAMME算法的基礎(chǔ)上進(jìn)行了有針對(duì)性的改進(jìn)，提升了算法對(duì)數(shù)據(jù)集中召回率最低的種類數(shù)據(jù)的識(shí)別敏感度，增強(qiáng)了算法在眾多數(shù)據(jù)集尤其不平衡率較高的數(shù)據(jù)集上的分類性能，為進(jìn)行相關(guān)分類研究的進(jìn)行提供了參考。相比于其他算法，該算法中基學(xué)習(xí)器的計(jì)算消耗較大，集成算法的時(shí)間消耗以及執(zhí)行效率都有待提高。此外，盡管目前針對(duì)極限學(xué)習(xí)機(jī)的一些分類算法被提出，但是將其應(yīng)用于不平衡數(shù)據(jù)的分類應(yīng)用相對(duì)較少，將極限學(xué)習(xí)機(jī)算法擴(kuò)展到半監(jiān)督和無(wú)監(jiān)督學(xué)習(xí)任務(wù)的研究極少，以上都是有待解決的問(wèn)題。