基于ELM的改進CART決策樹回歸算法①

王 宏,張 強,王 穎,郭玉潔

(東北石油大學 計算機與信息技術學院,大慶 163318)

在機器學習中,回歸問題同分類問題一樣一直是一個兼具魅力和挑戰(zhàn)的熱門研究領域.回歸建模過程是通過算法學習尋找已有數(shù)據(jù)之間的關聯(lián),求得一個復雜函數(shù),然后給出預測結果,常用的回歸算法有多元線性回歸[1]、支持向量機[2]、決策樹[3]、極限學習機[4]、人工神經(jīng)網(wǎng)絡[5]等.決策樹算法由于具有抽取規(guī)則簡單、對數(shù)據(jù)缺失值不敏感、模型易于構建、速度快、效率高等特點,深受相關學者專家重視.CART (Classification And Regression Tree)決策樹廣泛應用于分類和回歸問題,本文主要針對研究回歸問題,目前CART 回歸樹在醫(yī)學,農(nóng)業(yè),環(huán)境,石油,煤炭,電力,氣象等諸多領域都得到了大量的研究和應用,效果顯著,對專業(yè)研究、生產(chǎn)實踐都起到幫助和指導作用.比如Sut 等[6]將回歸樹應用于顱腦損傷死亡率的預測;Müller 等[7]將增強回歸樹用于比較阿爾巴尼亞和羅馬尼亞的耕地放棄決定因素的研究;Park 等[8]使用回歸樹建立了預測水庫系統(tǒng)中的葉綠素的應激響應模型來控制藻華;Larraondo 等[9]提出一種基于循環(huán)回歸樹的機場天氣預報系統(tǒng);董紅召等[10]將回歸樹用于城市交通道路氮氧化物濃度的預測研究;鄭向群等[11]提出一種空間數(shù)據(jù)挖掘算法,使得空間關系變得簡單,以此提高了算法效率;杜春蕾等[12]提出一種改進的CART算法決策樹模型,用來處理煤層底板突水數(shù)據(jù)預測,縮短了算法運行的時間,也提高了準確率;劉云翔等[13]引入Fayyad邊界判定定理,使得挑選屬性最優(yōu)閾值的速度更快,提高了運行效率;畢云帆等[14]將梯度提升機與決策樹相結合得到梯度提升決策樹,提高了電力短期負荷預測精度;李正方等[15]調(diào)整決策樹生成過程使其具有增量學習的能力,提高了在氣象信息系統(tǒng)中的實用性等等.很多專家學者們深入研究決策樹相關算法,并對決策樹算法做出很多的改進優(yōu)化,并憑借這些改進算法更好的適應解決了相應研究領域的問題,也獲得了良好的效果,但決策樹本身仍存在一些問題有待研究改進,如葉節(jié)點的輸出值計算方式為該節(jié)點處全部樣本的平均值,即模型訓練好后的預測輸出值為有限個定值,這種預測輸出值計算方法并不合理,并沒有實現(xiàn)真正意義上的回歸預測,導致回歸預測的準確性大大降低,降低了泛化的能力,可能在一些特定數(shù)據(jù)集上表現(xiàn)良好,但不適合廣泛的應用于一般數(shù)據(jù)集.因此,為了提高準確性,本文提出了該ELM-CART 算法,希望在回歸樹創(chuàng)建過程中,通過在葉節(jié)點對樣本子集分別采用ELM(Extreme Learning Machine)算法快速建模,以此來構建合理的預測輸出值,提高預測準確性,增強泛化能力,實現(xiàn)真正意義上的回歸預測.

1 相關算法介紹

1.1 極限學習機算法

二十一世紀初,黃廣斌等提出極限學習機算法[16].在此之前,單隱層前饋神經(jīng)網(wǎng)絡(Single Hidden Layer Feedforward Neural Network,SLFN)是基于梯度的算法訓練而成的,而極限學習機并沒有采用梯度算法,而是隨機生成輸入層權重和隱藏層偏置.然后通過已知數(shù)據(jù)的輸入,在使得損失函數(shù)最小的情況下,得到輸出層權重,到此整個極限學習機就訓練完成了,通過已知的輸入層權重,隱藏層偏置以及輸出層權重就可以直接計算測試數(shù)據(jù)的預測值了.與其他算法比,ELM 學習速度快、訓練參數(shù)少、泛化能力強[17].其網(wǎng)絡結構如圖1所示.

圖1 極限學習機網(wǎng)絡

其中,輸出層權重為βi,激活函數(shù)為g(x),輸入層權重為Wi=[wi,1,wi,2,···,wi,n]T>,bi為第i個隱層單元偏置.算法學習的期望是最小化真實值與輸出值的誤差,可以矩陣表示為:

式(2)中,輸出層權重用 β表示,而T表示期望的輸出,隱藏層節(jié)點的輸出用H表示,其具體形式可表示為:

網(wǎng)絡中隨機生成輸入權重Wi和隱層偏置bi,然后得到輸出矩陣H,這時,極限學習機的訓練過程就可以看做是線性問題的求解過程,因此,通過以下公式就可以求解出輸出權重 β,可表示為:

其中,H+是矩陣H的Moore-Penrose 廣義逆,且可證明求得的解 β的范數(shù)是最小并且唯一的.

1.2 CART 決策樹回歸算法

在經(jīng)典機器學習算法中,決策樹相關算法一直是研究熱門,因其獨特的樹形結構有利于快速處理數(shù)據(jù),表達數(shù)據(jù)之間的關聯(lián).分類回歸樹算法簡稱CART 算法[18,19].最初是由Breiman[20]于1984年提出的,可生成分類樹或回歸樹.與ID3[21]不能處理連續(xù)型數(shù)據(jù)相比,CART 引入二元切分法即可處理連續(xù)型數(shù)據(jù),且適合于對多特征變量的復雜數(shù)據(jù)進行建模,具有抽取規(guī)則簡單、準確度高、可解釋性強的優(yōu)勢,但算法穩(wěn)定性差,容易過擬合.

假設X與Y分別為輸入和輸出變量,且Y為連續(xù)變量,給定訓練數(shù)據(jù)集:

對于輸入空間的劃分,子空間及其輸出值與葉節(jié)點一一對應.這里通過依次遍歷每個特征變量及其對應的每個特征值,假設當前切分變量為第j個變量,對應切分特征值為s,即可劃分并定義兩個區(qū)域:

通過上述步驟,輸入空間將被不停的分割成L個子空間 α1,α2,…,αL,每個子空間 αl都包含部分的樣本數(shù)據(jù)和輸出值 βl,這時模型的解可表示為:

假設此時已經(jīng)完成輸入空間的劃分,這時的損失函數(shù)的誤差大小可以采用平方誤差來對比,通過平方誤差最小化的準則,確定最優(yōu)切分點和預測值.又根據(jù)最小二乘的原理可知,子空間 αl上的所有輸出yi的均值即為βl的最優(yōu)值,即可表示為:

劃分輸入空間的關鍵是如何選擇最優(yōu)的切分屬性j和屬性值s,用公式表達為:

通過遍歷全部的輸入特征變量及其特征值,就可以找到當前最優(yōu)的切分點(j,s),然后根據(jù)切分點劃分當前空間為兩個子區(qū)域,此時若這兩個子區(qū)域無法再劃分時,即可得到相應的最優(yōu)輸出值,表示為:

根據(jù)以上步驟,若該區(qū)域仍可繼續(xù)劃分,則對該區(qū)域重復上述步驟,直到整個回歸樹完全不可劃分停止.

2 ELM-CART 回歸算法

相比于線性回歸,樹回歸更適合處理復雜非線性的問題,即便如此,當輸入數(shù)據(jù)特征維度較高,特征之間關系相對更加復雜時,構建全局模型往往導致準確性較低.考慮到提高回歸預測的準確性,可以將輸入數(shù)據(jù)集劃分成若干個子集更易于建模.

經(jīng)研究發(fā)現(xiàn)一般回歸樹在建立過程中,就是將輸入數(shù)據(jù)樣本空間劃分成若干個子樣本空間,每個子樣本空間都有唯一確定的輸出值,這是因為在葉節(jié)點采用該節(jié)點處的樣本平均值作為模型回歸預測值,也就是說回歸樹擬合出來的是一個分段零階函數(shù),這些有限的離散定值極大程度上降低了決策樹在回歸問題上的預測準確率,因此,本文認為回歸樹葉節(jié)點處的樣本子集還可以做進一步的處理,這里可以對每一個子集分別進行建模,充分利用葉節(jié)點處樣本子集內(nèi)部的特征關系,理論上是可以達到提高整個回歸預測準確率的效果.結合ELM 優(yōu)點,本文提出一種對CART 回歸樹算法的改進算法——基于ELM的改進CART 決策樹回歸算法(an improved regression algorithm for CART decision tree based on ELM,簡稱ELM-CART 算法).

2.1 算法原理

本算法在回歸樹創(chuàng)建過程中,采用二元切分法遞歸創(chuàng)建二叉樹,每一次將原輸入空間劃分成兩個獨立的子區(qū)域,劃分時希望劃分的兩個分支的誤差越小越好,這使得每次的劃分都是獨立且最優(yōu)的,越往樹的底層深入,節(jié)點覆蓋的樣本越少,即隨著樹的生長,估計越來越不可靠,因此可以通過設置樹停止生長的規(guī)則來提前結束樹的生長,以此避免過擬合,達到最優(yōu)樹.在決策樹生成結束后,在每一個葉節(jié)點處分別采用極限學習機對子集進行建模,以此來達到提高回歸預測的準確性,如圖2示例所示.

假設X與Y分別為輸入和輸出變量,且Y為連續(xù)變量,訓練集為D={(x1,y1),(x2,y2),···,(xN,yN)},其中xi=(xi(1),xi(2),···,xi(n))為輸入特征數(shù)據(jù),n表示為特征維數(shù),i=1,2,···,N,N表示輸入數(shù)據(jù)個數(shù).

對輸入樣本空間的劃分采用啟發(fā)式方法,每次劃分都循環(huán)遍歷當前空間中的全部特征變量及其對應的所有特征值,再依據(jù)平方誤差最小化準則唯一確定最優(yōu)的切分特征和特征值組合.假設確定當前訓練集R的第j個特征變量x(j)及其取值s為切分點,則有R1(j,s)={x|x(j)≤s}R2(j,s)={x|x(j)＞s}和兩個劃分的定義區(qū)域,因此,是否劃分以及劃分的最優(yōu)切分點選取可由式(11)和式(12)平方誤差和比較得出:

圖2 特征空間劃分

總之,就是在小于err的err1,2中,找出使得兩個子區(qū)域平方誤差和之和err1,2最小的j和s,其中,這里c,c1和c2的求解是通過ELM 模型求得的估計值.這里根據(jù)設置的隱含層節(jié)點數(shù)L,隨機初始化生成服從任意的連續(xù)概率分布的輸入權重wi和隱含層閾值bi,就可以通過下式計算得到輸出矩陣H.

這里xi為輸入向量,g(x)表示激活函數(shù),這里使用Sigmoid 函數(shù).接下來計算此時的輸出權重,基于結構風險最小化的原則,為了避免出現(xiàn)矩陣無法求逆以及防止模型的過擬合,提高算法的泛化能力和魯棒性,引入L2正則化項后,此時輸出權重的計算公式為:

其中,C為正則化系數(shù).由此根據(jù)式(13),式(14)即可分別求得當前訓練集R,R1和R2的輸出矩陣H,H1,H2和輸出權重,,,于是通過下式即可分別求得式(11),式(12)中的c,c1和c2.

于是,根據(jù)以上步驟,若該區(qū)域仍可繼續(xù)劃分,則對該區(qū)域重復上述步驟,直到整個樹完全不可劃分停止.

對數(shù)據(jù)集進行訓練過程中,控制樹的劃分次數(shù),既可以減小時間開銷;又可以防止過度劃分導致模型出現(xiàn)過擬合.因此,本算法設置3 個超參數(shù)作為算法結束條件,滿足任意一個即訓練結束:(1)樹的深度達到給定深度;(2)誤差小于容許的誤差下降值;(3)葉節(jié)點處的子區(qū)域數(shù)據(jù)量小于設定的數(shù)量.

3 實驗分析

3.1 數(shù)據(jù)選取及處理

本文測試數(shù)據(jù)來自加州大學歐文分校的UCI(University of California Irvine)數(shù)據(jù)庫,這里面的數(shù)據(jù)集主要分為分類和回歸兩大類,在很多機器學習算法的相關論文中都可以看到這些數(shù)據(jù)集的應用.本次實驗涉及的數(shù)據(jù)集分別有波士頓房價數(shù)據(jù)集,魚類毒性數(shù)據(jù)集,翼型自噪聲數(shù)據(jù)集,聯(lián)合循環(huán)電廠數(shù)據(jù)集,混凝土抗壓強度數(shù)據(jù)集,水生毒性數(shù)據(jù)集以及加利福尼亞房價數(shù)據(jù)集等,詳細介紹如表1所示.

表1 測試數(shù)據(jù)集

首先下載這些數(shù)據(jù)集文件,然后讀取不同類型文件并對格式進行處理統(tǒng)一,再對數(shù)據(jù)歸一化處理,有利于提高模型的訓練速度和準確性,最后將數(shù)據(jù)集分為訓練集和測試集,為進一步的實驗做好數(shù)據(jù)準備.

3.2 評價指標

本文采用均方誤差(Mean Squared Error,MSE),平均絕對誤差(Mean Absolute Error,MAE)以及R2值(RSquared)3 種評價指標.

MSE值越接近零,表明模型越好,其公式如下:

MAE值越小,模型也就越好,其公式如下:

R2值不同于前兩者,它的范圍為0–1 之間,并且隨著R2值增大,訓練模型的準確率也越來越高,當R2等于0 時意味著不必進行預測,常數(shù)模型直接取值的情況;相反,當R2等于1 時,意味著所有預測值跟真實值是完全相等的,也就是說模型是不犯錯的,這也是回歸分析中追求的理想結果,其公式如下:

式中,m代表樣本總數(shù),為真實平均值,yi和分別為第i個樣本的真實值和預測值.

3.3 實驗結果分析

本文基于以上標準數(shù)據(jù)集,將ELM-CART 回歸算法與回歸樹,ELM,SVR,人工神經(jīng)網(wǎng)絡算法等進行對比分析,其中回歸樹的容許誤差下降值默認設為1,切分的最小樣本數(shù)取值在10 以內(nèi);ELM的L2正則化參數(shù)C取值為100 000,隱層節(jié)點數(shù)設置有20,50,1000及1200;SVR 采用的是使用最廣泛的徑向基核函數(shù)(RBF);人工神經(jīng)網(wǎng)絡采用的是兩層及三層的神經(jīng)網(wǎng)絡;ELM-CART 算法可以設置樹的深度,一般默認為2,通過增加深度可以起到進一步劃分數(shù)據(jù)集的效果,原CART 中保留的切分最小樣本數(shù)基本同樹的深度效果一樣,隱層節(jié)點數(shù)大于20.通過MSE,MAE以及R2值3 種評價指標得到以下結果,如表2所示.

通過表2對比可知,在這些標準數(shù)據(jù)集上,本改進算法總體上在MSE,MAE,R2值的對比中都明顯優(yōu)于CART 回歸樹算法和ELM 算法,同時也總體略優(yōu)于SVR和人工神經(jīng)網(wǎng)絡.由于MSE評價指標采用平方計算使得對異常樣本更加敏感,通過對比boston_housing、airfoil_self_noise、CombinedCyclePowerPlant、ConcreteCompressiveStrength 等數(shù)據(jù)集上的MSE值,不難發(fā)現(xiàn)改進算法的MSE值相對明顯較小,這是因為在改進算法中引入了L2正則化項,添加了懲罰項使得改進算法在MSE評價指標下對比其他算法得到明顯的下降,使得模型更加適應異常樣本存在的情形.其次,對比MAE值可以看出,改進算法在這些數(shù)據(jù)集上的表現(xiàn)總體是優(yōu)于所對比算法的.接著從R2值對比來看,很明顯改進算法的結果要優(yōu)于其他算法,特別是明顯優(yōu)于CART 回歸樹算法和ELM 算法,甚至在airfoil_self_noise 等數(shù)據(jù)集上有顯著提高,表明模型的準確率也更高.利用CART 算法對數(shù)據(jù)集的劃分原理使得相關關系更緊密的樣本數(shù)據(jù)劃分到一起,從而將全局模型的構建轉化為多個局部模型的構建,使得對比CART回歸樹和ELM 明顯提高了預測的準確性.因此,改進算法是將兩個算法的優(yōu)勢結合在一起,整體而言,本文提出的改進算法達到了預期效果.

表2 實驗結果對比

4 結論與展望

本文提出了基于ELM的改進CART 決策樹回歸算法,將復雜的全局模型分解為多個相對容易的局部模型,從而降低回歸分析的難度,提高模型準確性,并結合ELM 具有的優(yōu)點,將CART 回歸樹與ELM 算法融合,彌補了CART 回歸樹算法本身的缺點與不足,達到提高回歸預測的準確率,并通過上述實驗結果對比表現(xiàn)出了改進算法的優(yōu)化效果.在接下來的工作中,將會在更多數(shù)據(jù)集上測試算法的準確性,同時將會繼續(xù)研究相關算法,以期進一步提高回歸預測精度及穩(wěn)定性.