一種改進的ELM-SAMME算法及應用研究?

李克文 丁勝奪 段鴻杰

（1.中國石油大學（華東）計算機與通信工程學院 青島 266580）

（2.中國石化勝利油田分公司信息中心 東營 257000）

1 引言

分類學習算法是機器學習中的一項熱點研究內容，從傳統的分類算法到新型的衍生算法，解決此類問題的方案層出不窮。黃廣斌等［1］在單隱層前饋神經網絡（Single-hidden Layer Feedforward Neural Network，SLFN）的算法基礎上進行改進提出了極限學習機（Extreme Learning Machine，ELM）算法，針對傳統反向傳播（BP）神經網絡［2］求解參數過多、神經網絡訓練時間消耗大、易陷入局部最優等缺陷，該算法以求解線性方程組的方法取代標準算法中梯度下降方法進行迭代求解的過程，求取最小二乘解得到輸出層權值，簡化了繁瑣的迭代過程，形成一種速度快、結構簡單、泛化性能好、人工干預少的學習算法。該算法常被用于解決分類、回歸以及特征學習等問題。

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

針對以上算法的不足，本文利用ELM極限學習機作為弱分類器，使用SAMME算法作為集成策略集成強分類器，并對SAMME算法的迭代過程進行改進，降低其容易引入較差弱分類器的風險，增強最終強分類器的分類性能。

2 ELM和SAMME算法

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

2.1 ELM算法

式（1）中，βj表示第j個隱層節點到網絡輸出節點之間的連接權值；wj=[wj1，wj2，…，wjn]表示輸入節點和第j個隱層節點之間的連接權值向量；bj是第j個隱層節點的偏置。

為了求取最優的網絡參數w和β，嘗試最小化網絡的預測輸出和樣本真實值之間的的差值使其為零，即，可轉化為

轉化為矩陣形式為

式（3）中，H表示網絡隱含層的輸出向量矩陣，矩陣中的第i列即為相應的隱層節點的擬合輸出值；

在實際應用中，通常訓練樣本數N遠大于算法隱層的節點數，當所選取的激活函數滿足連續可微的條件，所求網絡的隱含層參數w和b在訓練過程中可以視為常數，無需調整網絡中全部參數。然后上述模型可以通過求解最小化問題：得到權值向量β，根據廣義逆原理，可計算得：

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

2.2 SAMME算法

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

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

Step2對t=1，2，…，T，執行1）～4）。

1）對經過Dt加權的訓練數據進行訓練，求得使偽誤差率最小的弱分類器ht(x)；

2）計 算ht(x)的 分 類 錯 誤 率 ：

3）計算ht(x)的系數

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

Step3構建所得弱分類器的線性組合，結合step2中式（3）所得系數得到最終強分類器：

3 改進的ELM-SAMME算法

為了使SAMME算法在一定迭代次數下達到更優的分類精度，對該算法的樣本權值及基分類器的權值分配過程進行改進，將該計算法記為IELM-SAMME，該算法的流程圖如圖1所示。

圖1 IELM-SAMME算法流程

Step1對于給定訓練數據集：( xi，yi)，xi∈Rm，yi∈(1 ，2，…，k)，其中k為類別數，初始化樣本的權重：

Step2接下來的迭代過程t=1，2，…，T中，重復執行1）～4）。

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

2）計算相應的權重誤差：

計算各個類別樣本的召回率Rtk，比較得到最低的召回率min Rtk，將該類視為難分類，求取該類別樣本在本次迭代中識別正確的樣本權值和

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

4）為下次迭代更新樣本權值：

這里Zt為規范化因子，它使訓練數據在下一輪迭代中的權值向量Dt+1成為一個概率分布。

Step3最終的強分類器可以通過對所得的弱分類器進行多數投票得到：

4 實驗結果及分析

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

在衡量各個分類算法在不同數據集上的分類性能表現時，僅僅選取準確率作為最終評價標準往往不能真實反映其分類性能，這是為了避免在不平衡數據集上最終評判結果的不公平性。在本實驗中，選取G-mean和F1值作為實驗結果的性能評價指標［12］，其定義如下：

最終實驗結果如表2、表3所示，在表1所示的10個數據集上本文的IELM-SAMME方法G-mean值和F1值比單獨使用ELM算法時取得效果都要好，這說明SAMME算法的應用取得了顯著的成效，從結果中還可以看出改進方法尤其對不平衡率較高的樣本集的識別效果有了較明顯的提升。將改進方法與AdaBoost方法進行比較可以看出改進方法相比于AdaBoost方法在大部分數據集上都有提升，尤其在Ecoli等不平衡率較高的數據集上的提升尤為明顯。而在平衡數據集如Iris上，改進方法獲得了與傳統方法相當的水平。該方法與未改進的ELM-SAMME算法進行比較僅在Iris、Wine等數據集上略差于ELM-SAMME方法。

表1 15個UCI數據集及其相關特征

表2 各算法在10個數據集上的平均G-mean值

表3 各算法在10個數據集上的平均F1值

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

表4 各算法在10個數據集上的平均G-mean值

表5 各算法在10個數據集上的平均F1值

5 結語

本文以極限學習機為弱學習器，以SAMME算法為集成策略，在標準的SAMME算法的基礎上進行了有針對性的改進，提升了算法對數據集中召回率最低的種類數據的識別敏感度，增強了算法在眾多數據集尤其不平衡率較高的數據集上的分類性能，為進行相關分類研究的進行提供了參考。相比于其他算法，該算法中基學習器的計算消耗較大，集成算法的時間消耗以及執行效率都有待提高。此外，盡管目前針對極限學習機的一些分類算法被提出，但是將其應用于不平衡數據的分類應用相對較少，將極限學習機算法擴展到半監督和無監督學習任務的研究極少，以上都是有待解決的問題。