基于Stacking策略的穩(wěn)定性分類器組合模型研究

吳擋平,張忠林,曹婷婷

(蘭州交通大學 電子與信息工程學院,蘭州 730070)

1 引 言

分類是數(shù)據(jù)挖掘和機器學習的基本問題,對于如何提高分類器的分類性能是當下主要的研究目的之一.傳統(tǒng)的分類器的學習系統(tǒng)是由給定的訓練樣本集,使用已有的學習器(如支持向量機、決策樹等)進行訓練產(chǎn)生一個模型,再用訓練好的模型來預測新的測試樣例,后根據(jù)模型的預測結(jié)果來對學習器的分類性能進行分析[1].然而隨著數(shù)據(jù)量的不斷增加和數(shù)據(jù)的多元化,傳統(tǒng)的分類算法已經(jīng)無法滿足對現(xiàn)有數(shù)據(jù)的處理以及實際問題的解決.對單個學習器的組合學習,使得在分類問題中顯示出了強大的優(yōu)越,從而使得組合分類算法在分類問題中得到了極大的關(guān)注.

現(xiàn)最流行的組合分類算法Boosting[2]和Bagging[3]方法.Bagging中使用的重采樣技術(shù)使得每個弱分類器的分類性能是獨立的,因此這些弱分類器可以并行的構(gòu)造.隨機森林[4]就是最典型的代表,它是由Breiman于2001年提出的一種基于決策樹的集成算法.Bagging方法的分類性能在于其基分類器的穩(wěn)定性,它對于不穩(wěn)定性的分類算法分類效果較好(決策樹[5]、神經(jīng)網(wǎng)絡等),但是對于穩(wěn)定的分類器集成效果就不是很理想.文獻[6]元慧等人提出了一種基于特征選擇的SVM Bagging集成方法,采用不同的特征選擇方法構(gòu)建子學習器,以增加不同子學習器間的差異性,與Bagging不同,Boosting方法中基分類器的訓練集取決前一個基分類器的分類性能,對前一個分類器分錯的樣例按較大的概率出現(xiàn)在下一個基分類器的訓練集中,雖然提高了組合分類算法的泛化性能,但有可能會出現(xiàn)過分偏向于一些很難分的樣例,從而有時會導致算法的性能降低(其中C5.0就是采用Boosting方式的組合算法).He等人[7]針對Boosting很難應用在KNN上和對噪聲較敏感的問題,提出了基于組合模型的BK-NN算法,通過距離度量計算的優(yōu)化以及重置數(shù)據(jù)集的多樣性,提高了泛化性能.文獻[8]提出了基于圖模型的自適應K近鄰算法,為了改進KNN算法性能將Boosting技術(shù)映射到基于圖的方法中.

針對Bagging[10]和Boosting[11]兩種組合算法在分類任務中對穩(wěn)定性的分類器集成效果并不理想且改善效果均十分有限的問題,本文利用Stacking[9]策略的兩層式疊加框架,結(jié)合特征降維技術(shù),提出了一種基于Stacking策略的穩(wěn)定性分類器組合模型.

本文首先利用一種過濾式的特征選擇算法對數(shù)據(jù)集進行預處理,消除一些冗余特征以簡化組合分類模型；然后在基于Stacking算法的多分類器組合方法上,將SVM、KNN、GLM和LDA四種穩(wěn)定性學習算法作為初級分類器進行組合學習,次級分類器采用邏輯回歸算法,實驗部分主要對本文的組合算法與單個算法以及其他幾種集成算法的對比分析,結(jié)果表明基于Stacking策略的穩(wěn)定性分類器組合模型能夠獲得更好的分類精度.

2 多分類器組合方法

2.1 Stacking策略

對于Stacking策略,作為一種異構(gòu)分類器集合的技術(shù).該方法被認為是實現(xiàn)集合中基分類器多樣性的工具,以此提高組合分類的準確性.它采用兩層框架的結(jié)構(gòu),如圖1所示.具體的訓練過程為：首先Stacking方法調(diào)用不同類型的分類器對數(shù)據(jù)集進行訓練學習,然后將各分類器得到的訓練結(jié)果組成一個新的訓練實例作為元分類器的輸入.最終元分類器的輸出結(jié)果為最終的結(jié)果輸出.Stacking是一種通用框架,可看作是許多集成方法的推廣[12].

圖1 Stacking算法框架Fig.1 Stacking algorithm framework

2.2 投票法

投票法是每個基分類器對樣本的預測結(jié)果中,數(shù)量最多的類別就是最終的分類類別,相比平均后驗概率法和stacking學習法,此方法保留了每個基分類器的預測結(jié)果,但卻把每個基分類器對其他類的預測情況給忽略掉了,因此算法對基分類器的選擇和數(shù)據(jù)集變化較敏感[13].

2.3 平均概率法

平均后驗概率法是適用于基分類器或類別數(shù)過多的情況下的一種分類器集成策略.現(xiàn)假定有N個基分類器,K個類別,x為輸入數(shù)據(jù),其中第i個基分類器對應的分類結(jié)果為：

Ci(x)=[Pi1Pi2……PiK]

向量pin表示每個類別的后驗概率.對所有的基分類器對每個類別的后驗概率求平均,作為元分類器的輸入為

[(P11+…+PN1)/N…(P1K+…+PNK)/N]

即這樣數(shù)據(jù)從N*K維變?yōu)镵維,但這種方法卻掩蓋了基分類器的預測結(jié)果,因此在類別數(shù)較少的數(shù)據(jù)集中其精度往往低于基于分類器輸出方法[13].

3 基于Stacking策略的穩(wěn)定性分類器組合模型

在組合模型中,對基分類器的選取這里我們有兩種選擇：

1)選取的基分類器是同一種類型的.(比如對單個的決策樹學習器使用不同的參數(shù)訓練得到多個決策樹模型組合學習和對神經(jīng)網(wǎng)絡使用不同層數(shù)構(gòu)造多個不同結(jié)構(gòu)的訓練模型組合學習)；

2)選取的基分類器不是一個類型的,或者說是異質(zhì)的(比如對于一個分類問題.在同一個訓練集在采用支持向量機,邏輯回歸模型和K近鄰算法幾種不同的基分類器組合學習得到最終的分類模型).本文采用第二種選擇方法,基于Stacking學習法的兩層結(jié)構(gòu)框架,對幾種不同的穩(wěn)定性分類器組合學習.具體的為GLM、LDA、KNN和SVM作為第一層的分類器,也就是基分類器,廣義線性模型(GLM)也可以說是邏輯回歸作為第二層的元分類器.針對這四種常見的、在組合模型中一般不采用的穩(wěn)定性分類器的特點,提出了將這4種算法進行組合學習,從而進一步提高分類器的分類性能.下面主要介紹了這4種算法和結(jié)合的數(shù)據(jù)降維機制.

3.1 分類算法

3.1.1 K鄰近算法

K鄰近算法(K-Nearest Neighbor),是一種較傳統(tǒng)的穩(wěn)定性分類器,也是一種懶惰的學習算法,其基本思想是對預測樣例點最鄰近的K個樣例點與預測樣例點進行計算,從而判別出新樣例點的類別,達到對新樣例的分類和預測.它是一種基于距離和樣本實例的無參方法.雖然說KNN算法簡單有效,但是隨著樣本的分布不均勻增大時時,算法的分類誤差也會增大[14].

3.1.2 支持向量機

支持向量機(SVM)是一種經(jīng)典的穩(wěn)定性分類器.它是基于統(tǒng)計學習理論(Vapnik-Chervonenkis ,VC)和結(jié)構(gòu)風險最小化理論(Structural Risk Minimization,SRM)發(fā)現(xiàn)訓練子集中的最小化經(jīng)驗風險和最大化決策邊緣來控制算法的分類能力.SVM在解決二分類問題具有很好的泛化能力以及在解決非線性的高維的數(shù)據(jù)集來說具有一定的優(yōu)勢.因此在分類、識別和檢索等應用很廣泛[15].

3.1.3 線性判別分析

線性判別式分析(LDA)是一種傳統(tǒng)的穩(wěn)定性分類算法.它的核心思想是通過將高維的樣本集投影到一個矢量空間,使得樣本在新的子空間中有最大的類間 距離和最小的類內(nèi)距離[16].即類間的耦合度低,類內(nèi)的聚合度高,這樣才能使得分類效果最佳.

假設一個Pn空間有m個樣本分別為：x1,x2,…,xm,即每個x是一個n行的矩陣,其中ni表示屬于i類的樣本個數(shù),假設有j個類,則可得類i的樣本均值為：

(1)

可得總體樣本均值為：

(2)

類間離散度矩陣計算法如公式(3)所示：

(3)

類內(nèi)離散度矩陣計算如公式(4)所示：

(4)

其中ui表示類i的樣本均值；u表示總體的樣本均值；xk表示第k個樣本.

3.1.4 廣義線性模型

廣義線性模型(GLM)在處理二分類問題上應用最廣泛的是Logistic回歸模型.適用于輸入變量與輸出變量間為線性關(guān)系,它將樣例的屬性特征整合為線性組合來當作輸入變量,其使用logistic函數(shù)將輸入變量 映射到(0,1)區(qū)間上,則可知y=1的概率簡單定義為：

(5)

其中x是n維特征向量,g(x)=B0+B1X1+....+BnXn是logistic函數(shù),如圖2所示.

圖2 logistic函數(shù)圖Fig.2 Graph of logistic function

則y=0概率為：

p(y=0/x)=1-p(y=1/x)

(6)

經(jīng)過logit變換后,

(7)

可以看出使用廣義線性模型是將非線性回歸形式問轉(zhuǎn)化為一個線性回歸形式求解.建模學習二分類問題并根據(jù)AIC評分準則來選擇最優(yōu)的模型.

3.2 CFS-GA特征選擇算法

利用遺傳算法進行特征選擇時,通常以學習算法的分類精度和選擇的特征子集大小作為適應度函數(shù).雖然這種方法在某種程度上是依據(jù)GA具有的全局搜索能力找到最優(yōu)解,但是當數(shù)據(jù)量較大時它的性能不是很好且復雜度較大.考慮將適應度函數(shù)設置成一種過濾型的算法.因此本文應用了CFS-GA特征選擇算法對數(shù)據(jù)進行降維,以簡化模型和提高模型的分類精度.該算法中,遺傳算法GA將樣例的特征子集看作染色體 對其進行二進制編碼；利用CFS啟發(fā)值作為GA的適應度 函數(shù)對個體進行評價；CFS值越大的個體遺傳到下一代的概率越大.結(jié)合GA的全局搜索特性,該算法可保證所得特征子集是全局最優(yōu)的[17].

CFS是一種過濾式的特征選擇算法,其評估方法如下：

(8)

假如有變量X,其可能的取值有n種,每一種取到的概率為Pi,那么X的熵就定義為：

(9)

假設用屬性T來劃分屬性X,計算屬性T給X帶來的熵值為：

(10)

其中屬性T有k個取值,所以特征T給X屬性帶來的信息增益為：IG(T)=H(X)-H(X|T).信息增益越大,X與T的相關(guān)性就越大.

3.3 主成分分析(PCA)

PCA是一種數(shù)據(jù)降維技術(shù).它的目標是將原始變量重新組合成新的相關(guān)性小的綜合變量的表示,并使新的變量盡可能多的表達原始的變量信息,所得的相關(guān)性較小的綜合變量稱為主成分.假設將原始變量X1,X2,…,XK通過線性轉(zhuǎn)換變成一組相互無關(guān)的變量PC1,PC2,…,PCn,在這種變換中,保持原始變量X1,X2,…,XK的總方差之和不變,則PC1具有最大方差,PC2作為次方差,以此類推,從而得到一組不相關(guān)的變量,得到對數(shù)據(jù)的降維目的.如第一主成分PC1為：

PC1=a1X1+a2X2+…+akXk

(11)

3.4 利用Stacking策略的穩(wěn)定性分類器組合模型實現(xiàn)

每個基分類器間的訓練是相互獨立的,利用特征選擇算法FCS-GA對數(shù)據(jù)集降維,然后分別在每個基分類器上訓練模型,得到的模型經(jīng)過Logistic回歸模型檢驗分析,得出各個模型的擬合度檢驗p值,選擇最優(yōu)的組合模型分類.Stacking組合算法框架如圖3所示.

圖3 Stacking策略的分類算法組合模型框架Fig.3 Stacking strategy classification algorithm combination model structure

本文利用Stacking策略的分類算法組合模型訓練過程如下：

Step1.利用CFS-GA算法對數(shù)據(jù)集D進行特征選擇,去除一些冗余特征和與類別不相關(guān)的特征.得到新的數(shù)據(jù)集D′；

Step2.將數(shù)據(jù)集D′切分為訓練集和測試集,在訓練集上利用交叉驗證法訓練n個基分類器,得到n個模型,作為第二層元分類器的輸入樣本mod；

D={(xi,yi),i=1,…,m}

mod={fi(x),j=1,…,N}

mod=(mod1,…,modn)

Step3.利用數(shù)據(jù)預處理技術(shù)主成分分析法(PCA)對輸入樣本集models進行降維處理；

Step4.使用處理后的樣本集訓練元分類器,通過交叉驗證法選擇合適的參數(shù),得到最終的分類結(jié)果.

Step5.在測試集上測試組合分類模型.

4 實驗分析

本文在PC機(CPU為2.5GHz ,內(nèi)存為4.0GB)上,基于weka平臺的特征選擇算法和R語言中的caret軟件包進行實驗.算法實驗數(shù)據(jù)直接來源于UCI數(shù)據(jù)庫,數(shù)據(jù)的描述如表1所示.

4.1 實驗1

本文利用PCA降維技術(shù)處理組合模型的輸入樣本,即提取與觀測變量相關(guān)性大的特征進行組合學習.這里以UCI數(shù)據(jù)集中的皮馬印第安人糖尿病數(shù)據(jù)集為例,首先對組合模型的基分類器性能進行詳細分析(這里使用箱線圖可視化技術(shù)來比較基分類器的性能)如圖4所示；然后利用散點圖分析法來對比基分類器間的相關(guān)性如圖5所示.從而為模型的選擇提供了一個可靠的方案.

表1 實驗數(shù)據(jù)集Table 1 Experimental data sets

圖4 基分類器的分類性能對比Fig.4 Comparison of classification performance of base classifiers

在一定程度上分類器的選擇是分類器組合模型的關(guān)鍵之一.基分類器的精度過高或者過低都會影響組合模型的分類性能.從圖4可以看出所選的基分類器間的分類精度相差不大.沒有表現(xiàn)特好或者特差的分類器,這在一定程度上保證了組合模型的性能不會是因為基分類器的差異性而導致的分類性能降低的問題.

圖5 基分類器間的相關(guān)性分析Fig.5 Correlation analysis among base classifiers

從圖5基分類器間的相關(guān)性分析圖可以看出GLM和LDA間的相關(guān)性較大,其他幾個分類器的相關(guān)性較小,PCA處理是依據(jù)相關(guān)性大小來提取主成分,將相關(guān)性較大的因素刪除,提取相關(guān)性較小的因素.因此PCA在數(shù)據(jù)集Diabetes上的主成分提取數(shù)為3(訓練得到的基分類器數(shù)是4個).表2描述了FCS-GA特征選擇算法和PCA提取的主成分數(shù)的結(jié)果.其中FCA-GA算法是基于weka平臺進行實驗.

表2 特征處理的結(jié)果Table 2 Result of feature processing

4.2 實驗2

實驗1給出了基分類器與特征選擇算法的關(guān)系,實驗采用表1的公共數(shù)據(jù)集,在R語言環(huán)境下編程.與單個的分類算法(CART、KNN、SVM、LDA、GLM)和集成算法(AdaBoost、C50、Bagging、RF)以及文獻[10]和文獻[11]的算法進行分類精度的對比,實驗結(jié)果如表3所示.

表3 分類器間的分類精度對比Table 3 Comparison of classifier in classification accuracy

從測試結(jié)果來看,Ionosphere數(shù)據(jù)集上預測最佳結(jié)果達到約 98%的分類準確率.整體上本文的穩(wěn)定性分類器組合模型在泛化性能上都要優(yōu)于單個的穩(wěn)定性分類器和其他幾種集成算法,取得了較好的分類效果.選取四種較簡單的分類器組合學習,不管是在算法的分類精度上還是在算法的復雜度上都要優(yōu)于現(xiàn)有的一些集成算法,進一步可以總結(jié)出本文提出的基于Stacking策略的穩(wěn)定性分類器組合模型為二分類問題在分類性能上提出了一個可行的參考方案.

5 結(jié)束語

Stacking方法最為一種組合學習方法,相比于Boosting和Bagging組合方法來說,理論的研究較少,由于它在算法上的靈活性和可擴展性較強,因此在各種算法的集成大賽中較受歡迎.大部分研究者主要是通過擾動樣本和選取不穩(wěn)定分類算法來提高組合算法的泛化性能,一般不建議采取穩(wěn)定性的算法作為基分類器.因此出現(xiàn)了以決策樹、神經(jīng)網(wǎng)絡等分類精度高的不穩(wěn)定性分類算法為基分類器的大量組合算法的研究,而相對于一些穩(wěn)定性分類算法的組合就相對來說較少且改善效果有限,而且分類效果一般在二分類的問題上就表現(xiàn)不是很好.

因此本文提出用Stacking方法來提高一些在模型的組合中不常采用作為基分類器、比較穩(wěn)定的、簡單速度快的分類算法進行組合學習,結(jié)果驗證它在二分類問題上取得了較好分類效果.下一步的工作是在本文算法的基礎(chǔ)上拓展到多分類任務中,能夠在多分類認為中達到較好的表現(xiàn).