ELMs和SVMs在多分類問題上的泛化性能比較

盧欣欣 潘麗平

1(周口師范學院計算機科學與技術學院 河南 周口 466001)2(農產品質量安全追溯技術河南省工程實驗室 河南 周口 466001)3(周口科技職業學院 河南 周口 466001)

0 引 言

由于科技的飛速發展，猛增的數據量和大幅提升的計算性能使得多分類問題越來越多地代替二分類問題，并在文本分類識別[1]、語音識別[2]、醫學圖像識別[3]等方面取得了良好的應用前景，已經成為模式識別、數據挖掘等領域的重要研究內容。

SVM是Vapnik[4]基于統計學習理論提出的最優間隔分類器，其良好的泛化能力、全局最優解和解決非線性問題的能力使其成為應用最為廣泛的分類器[5-6]。但原始SVM并不適用于多分類問題，Weston[7]最先改進SVM使其成功應用在多分類問題中。最小二乘支持向量機(LSSVM)[8]是SVM的簡化和改進形式，避免了原始SVM求解二次規劃的問題，提高了訓練速度，Suykens[9]將LSSVM擴展到多分類問題中。

ELM是Huang[10]提出的一種快速算法，它將隱層節點權值隨機確定，只需計算輸出層權值，從而大大加快了網絡的訓練速度，并且ELM本質上可直接應用于多分類問題，因而取得了廣泛應用[11-13]。核極限學習機(KELM)是Huang[14]為解決ELM結果具有隨機性而提出了基于核函數的改進算法，在遙感圖像分類[15]、基因檢測[16]等方面取得了良好的分類效果。

由文獻[17]可知：ELM和SVM均是基于單隱含層前饋神經網絡框架，而LSSVM是ELM簡化的框架結構；ELM通過最小平方優化法可擴展為SVM網絡，且具有更好的泛化性能。ELMs和SVMs均可實現相當的分類準確率，但在不同的問題條件下也表現出不同的特性[18-19]。研究發現：經典的ELM算法與SVM算法相比具有訓練速度快、適應性強等優勢；SVM算法需要花費相對更多的訓練時間；LSSVM的訓練算法比SVM的訓練算法簡單，訓練精度與SVM相當或超過SVM，但對新數據的應用卻要對整個訓練集進行處理。

本文通過在UCI數據集上的對比驗證，詳細探討了ELMs和SVMs在多分類問題上的分類準確率、對類別的敏感程度和算法運行時間等性能指標，并給出相應分析和結論。實驗表明，隨著分類數目的增加，ELMs的泛化能力相較于SVM提高得更多。

1 ELMs和SVMs簡介

1.1 支持向量機(SVM)

SVM是指通過支持向量運算的方式進行分類的分類器，是一種基于統計學習理論的有監督機器學習算法[20]，通常用來解決線性分類問題和非線性分類問題。其處理分類問題的典型模式是尋找使各類別分類間隔最大的最優分類超平面，給定一組數據作為對應的類別標簽，則由文獻[4]可得SVM求解如下優化方程：

(1)

s.t.ξi≥0,yi[wTΦ(xi)+b]≥1-ξi?i

式中：Φ為特征映射函數，w為超平面參數，ξi為分類軟間隔，C為離群點懲罰因子。

使用KKT[21]條件，則式(1)通過拉格朗日乘數法轉化為原形式的對偶問題來進行求解：

(2)

式中：αi,βi≥0為拉格朗日乘數子，通過對w、b、ξi分別求偏導可得：

(3)

則式(2)可轉化為：

(4)

最終的最優分類超平面的解為：

(5)

在使用SVM對線性分類問題求解時，分類效果對懲罰因子的選擇依賴較大，而在使用SVM對非線性分類問題求解時，核函數的形式和其參數對高維映射的效果影響較大，因此SVM在處理分類問題時還存在一定的局限性。

1.2 最小二乘支持向量機(LSSVM)

LSSVM與SVM思路基本一致，是SVM的一種演變。LSSVM是由原來的不等式約束演變成了等式約束，主要用來解決等式約束下的優化問題，其次LSSVM與SVM的最顯著區別在于LSSVM在求解時使用最小二乘損失函數：

(6)

s.t.yi[wTΦ(xi)+b]=1-ξi?i

同SVM，式(6)可轉化為拉格朗日函數來進行求解：

(7)

由式(7)分別對w、b、ξi、αi求偏導得：

(8)

將式(8)中前三個等式代入第四個等式，可得：

(9)

式中：Y=[y1,y2,…,yN]T,α=[α1,α2,…,αN]T,Z=[y1Φ(x1),y1Φ(x2),…,yNΦ(xN)]T。

令Ω=ZZT，根據Mercer條件，有：

Ωi,j=yiyjκ(xi,xj)

(10)

將式(10)代入式(9)，求解線性方程，得到的結果與式(5)相同。

與SVM相比，LSSVM算法求解速度更快，但其預測精度比SVM稍差。

1.3 極限學習機(ELM)

ELM是一種基于單隱含層的人工神經網絡模型求解算法[10]，它的優勢是僅需設置隱藏層節點數，使用最小二乘法求解隱含層到輸出層的權值即可，不需要進行循環迭代。與BP神經網絡等相比，ELM具有快速學習、高準確度、泛化能力以及盡可能地減少人工干預等特點。ELM的目標是最小化訓練誤差的同時最小化輸出權值的范數來求解單隱層前饋神經網絡[10]。

有L個隱層節點、N個數據點的ELM的隱層節點輸出矩陣H可定義為：

在靜力分析中，除了應力分布圖外，管道的位移形變圖也是作為衡量管道是否安全的一個重要指標。管道的位移形變主要是其管道所受載荷與管道的約束之間相互作用的結果。倘若管道所受載荷過大，超過了管道約束力并且超過了管道材料的屈服極限，那么就會造成管道的極大彎曲甚至破裂，最終造成泄漏甚至爆炸等事故[6]。

(11)

式中：h(·)為隱層單元激活函數，W=[w1,w2,…，wL]為隱層單元隨機確定權值，B=[b1,b2,…，bL]為隱層和輸出層之間偏置。

則ELM可被定義為如下形式：

(12)

式中：β為隱層和輸出層之間權值，Y=[y1,y2,…，yN]∈{-1,1}為樣本標簽，ξ=[ξ1,ξ2,…，ξN]為預測誤差矩陣，C為懲罰因子。

由式(12)可得β為：

(13)

式中：H+為H的Moore-Penrose廣義逆矩陣。

最終ELM的解為：

(14)

1.4 核極限學習機

為進一步提高ELM的穩定性和泛化能力[14]，將核函數的思想引入ELM，從而構成核極限學習機(KELM)。與ELM相比，KELM用核映射的方式取代隨機映射，有效解決了“維數災難”和隨機設置隱藏層參數帶來的穩定性差的問題，從而降低計算復雜度。KELM多用于特征學習以及多分類問題當中。KELM可表示為：

(15)

2 實驗與結果分析

2.1 實驗數據

表1 實驗數據集的基本信息

續表1

為了消除各維數據間數量級差別，避免因為輸入輸出數據數量級差別較大而引起的訓練誤差，本文對所有的輸入數據均進行了如下的歸一化處理，將數據歸一化到[0,1]區間：

xk=(xk-xmin)/(xmax-xmin)

(16)

式中：xmin為數據序列中的最小值，xmax為數據序列中的最大值。

2.2 實驗環境簡介

本文所使用SVM程序來自libsvm-3.12，LSSVM程序為LS-SVMLab-1.7，ElMs程序來自極限學習機官方網站，程序運行環境為：MATLAB R2010b，Windows 7系統。

2.3 實驗結果分析

2.3.1單一數據集(Amazon)結果分析

為了對比ELMs和SVMs在多分類問題上的泛化性能，首先選取Amazon數據集進行實驗分析。對Amazon數據集采取逐類增加的方式，類別數目從3類依次增加到10類，分別記錄ELMs和SVMs的分類準確率。數據集采取獨立隨機劃分的方式，每次選取70%的數據作為訓練集，余下30%作為測試集，并進行十次獨立劃分，分別計算ELMs相對于SVMs在不同類別數目下的平均分類準確率，實驗結果如表2所示，ELMs相較于SVMs分類準確率增長情況如表3所示。

表2 ELMs和SVMs在Amazon數據集上隨著類別數目增多平均分類準確率 %

表3 在Amazon數據集上隨著類別數目增多ELMs相較于SVMs分類準確率增長情況 %

為清晰展示實驗結果，根據表3的結果繪制了ELMs相對于SVMs在各類別泛化能力增長情況圖，結果如圖1所示。

圖1 在同一數據集Amazon下不同類別劃分ElMs相較于SVMs泛化性能比較

由表3及圖1可得如下結論：

(1) 對于Amazon數據集，ELMs分類器在各類別上的分類準確率均優于SVMs分類器；

(2) ELMs相較于SVM在多分類問題上隨著類別數目的增加泛化能力也越來越好，并且KELM泛化能力要稍優于ELM；

(3) ELMs相對于LSSVM并沒有表現出(2)中的特性，而是隨著類別數目的增加，ELMs相對于LSSVM的泛化能力呈現出明顯的波動性。

分別統計ELMs和SVMs隨類別增加分類準確率的下降情況，結果如表4所示。

表4 ELMs和SVMs隨類別增加分類準確率的下降情況

類數SVMLSSVMELMKELM3vs300004vs3-2.46-1.34-1.05-0.84

續表4

類數SVMLSSVMELMKELM5vs4-2.03-0.64-1.65-1.536vs5-0.64-1.010.17-0.177vs6-0.840.89-0.86-0.128vs7-0.75-1.060.11-0.529vs8-3.46-3.38-3.65-2.4710vs9-0.81-0.360.67-0.21平均值-1.38-0.86-0.78-0.73

表4可直觀表示成圖2形式。

圖2 ELMs和SVMs隨類別增加分類準確率的下降情況

由表4和圖2可知:隨類別數目的增加，ELMs分類準確率的下降速率要明顯比SVMs緩慢，說明ELMs對類別數目變化不敏感，更適用于多分類問題。ELMs相較于SVMs在同一數據集上分類穩定性更好，對數據集的寬容度更高。這樣的性能表現與其理論密切相關：SVMs依賴于高維空間映射的準確性，在類別數目較低時更容易對應映射空間找到最優解，而隨類別增加高維映射難度增加，分類準確率降低。ELMs不需要復雜映射，僅需找到對應隱層節點對應權值即可取得最優解，從而減少了其對類別數目增長的所帶來的性能損失。

為探究ELMs和SVMs算法的訓練和測試速度，分別統計了各算法在各類別下的平均運行時間，結果如表5所示。

表5 ELMs和SVMs在各類別下平均運行時間 s

續表5 s

由表5可知：

(1) ELMs和SVMs隨著類別數目的增加(即樣本數目增加)，運行時間均有所增加，SVMs算法運行時間增長幅度明顯大于ELMs。

(2) SVMs對一個分類問題需要進行復雜運算從而得到最優高維映射的所有解，而ELMs僅需計算較少參數即可得到較好的分類準確率，有效降低了運算開銷。KELM在各類別下的運行時間均最短，所需運算負荷最小，適用于快速分類。

2.3.2多數據集結果分析

為進一步探究ELMs和SVMs在多分類問題上的性能差異，選取Iris等7個多分類數據集進行實驗驗證，結果如表6、表7所示。

表6 ELMs和SVMs在不同數據集上隨著類別數目增多平均分類準確率 %

表7 在不同數據集下ELMs相較于SVMs分類準確率增長情況 %

為清晰展示實驗結果，根據表7的結果分別繪制了ELMs和SVMs在各類別的分類準確率圖和ELMs相對于SVMs在各類別泛化能力增長情況圖，結果如圖3所示。

圖3 在不同數據集下ELMs相較于SVMs泛化性能比較

由表7及圖3可得如下結論：

(1) 將圖3和圖1進行對比，可看出兩圖呈現出一致的趨勢，說明ELMs相較于SVMs在多分類問題上性能一致性更好；

(2) ELMs在所有數據集上均取得優于SVMs的分類準確率；

(3) 不同數據集下，隨著數據集的類別數目的增長，ELMs相較于SVM也同樣獲得了如單一數據集時更好的泛化能力，但是對于LSSVM上述結論并不成立，ELMs相較于LSSVM的泛化能力依然呈現出波動性，相關問題的原因可做進一步研究。

3 結 語

本文詳細比較了ELMs和SVMs在多分類問題上泛化性能的差異，并且得出如下結論：(1) ELMs相較于SVM在多分類問題上有更高的分類準確率，而且隨著分類數目的增加，ELMs的泛化能力相較于SVM提高更多，但是ELMs對于LSSVM并沒有得到上述結論；(2) ELMs相較于SVMs對數據的類別數目不敏感，分類準確率隨類別數目增加下降不明顯；(3) ELMs相較于SVMs在多分類問題上所需計算代價更小，且擁有更快的學習和訓練速度。