王 宏,張 強(qiáng),王 穎,郭玉潔

(東北石油大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院,大慶 163318)

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

1 相關(guān)算法介紹

1.1 極限學(xué)習(xí)機(jī)算法

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

圖1 極限學(xué)習(xí)機(jī)網(wǎng)絡(luò)

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

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

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

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

1.2 CART 決策樹回歸算法

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

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

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

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

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

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

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

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

2 ELM-CART 回歸算法

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

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

2.1 算法原理

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

假設(shè)X與Y分別為輸入和輸出變量,且Y為連續(xù)變量,訓(xùn)練集為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ù)個(gè)數(shù).

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

圖2 特征空間劃分

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

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

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

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

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

3 實(shí)驗(yàn)分析

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

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

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

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

3.2 評(píng)價(jià)指標(biāo)

本文采用均方誤差(Mean Squared Error,MSE),平均絕對(duì)誤差(Mean Absolute Error,MAE)以及R2值(RSquared)3 種評(píng)價(jià)指標(biāo).

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

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

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

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

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

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

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

表2 實(shí)驗(yàn)結(jié)果對(duì)比

4 結(jié)論與展望

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