吳擋平,張忠林,曹婷婷

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

1 引 言

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

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

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

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

2 多分類器組合方法

2.1 Stacking策略

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

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

2.2 投票法

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

2.3 平均概率法

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

Ci(x)=[Pi1Pi2……PiK]

向量pin表示每個(gè)類別的后驗(yàn)概率.對(duì)所有的基分類器對(duì)每個(gè)類別的后驗(yàn)概率求平均,作為元分類器的輸入為

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

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

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

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

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

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

3.1 分類算法

3.1.1 K鄰近算法

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

3.1.2 支持向量機(jī)

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

3.1.3 線性判別分析

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

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

(1)

可得總體樣本均值為：

(2)

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

(3)

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

(4)

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

3.1.4 廣義線性模型

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

(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)過(guò)logit變換后,

(7)

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

3.2 CFS-GA特征選擇算法

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

CFS是一種過(guò)濾式的特征選擇算法,其評(píng)估方法如下：

(8)

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

(9)

假設(shè)用屬性T來(lái)劃分屬性X,計(jì)算屬性T給X帶來(lái)的熵值為：

(10)

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

3.3 主成分分析(PCA)

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

PC1=a1X1+a2X2+…+akXk

(11)

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

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

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

本文利用Stacking策略的分類算法組合模型訓(xùn)練過(guò)程如下：

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

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

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

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

mod=(mod1,…,modn)

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

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

Step5.在測(cè)試集上測(cè)試組合分類模型.

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

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

4.1 實(shí)驗(yàn)1

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

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

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

在一定程度上分類器的選擇是分類器組合模型的關(guān)鍵之一.基分類器的精度過(guò)高或者過(guò)低都會(huì)影響組合模型的分類性能.從圖4可以看出所選的基分類器間的分類精度相差不大.沒有表現(xiàn)特好或者特差的分類器,這在一定程度上保證了組合模型的性能不會(huì)是因?yàn)榛诸惼鞯牟町愋远鴮?dǎo)致的分類性能降低的問(wèn)題.

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

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

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

4.2 實(shí)驗(yàn)2

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

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

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

5 結(jié)束語(yǔ)

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

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