基于近似約簡(jiǎn)與最優(yōu)采樣的集成剪枝①

王安琪,江 峰,張友強(qiáng),杜軍威

(青島科技大學(xué) 信息科學(xué)技術(shù)學(xué)院,青島 266061)

集成學(xué)習(xí)近年來(lái)得到廣泛研究[1–5]. 為了構(gòu)建一個(gè)有效的集成分類(lèi)器,研究者提出了不同的方法來(lái)訓(xùn)練一組好而不同的個(gè)體分類(lèi)器. 現(xiàn)有的集成方法大致可分為兩類(lèi),即基于單模態(tài)擾亂的方法和基于多模態(tài)擾亂的方法,其中,第1 類(lèi)方法又包括基于重采樣的方法(如Bagging、Boosting 等)[6,7]、基于特征子空間的方法[8–10]等. 與第1 類(lèi)方法不同,基于多模態(tài)擾亂的方法[5,11,12]在訓(xùn)練個(gè)體分類(lèi)器的過(guò)程中使用了多種擾亂技術(shù),其動(dòng)機(jī)是: 很多時(shí)候單一類(lèi)型的擾亂可能不足以產(chǎn)生多樣性大的個(gè)體分類(lèi)器. 早期的集成方法通常對(duì)所有的個(gè)體分類(lèi)器進(jìn)行集成,然而,這種做法并不一定能夠保證個(gè)體分類(lèi)器之間的多樣性. 對(duì)此,研究者們進(jìn)一步提出了不同的集成剪枝方法[4,13,14]. 集成剪枝的主要目的是通過(guò)刪除一些個(gè)體分類(lèi)器來(lái)提升個(gè)體分類(lèi)器之間的多樣性(即只利用一部分多樣性大的個(gè)體分類(lèi)器來(lái)構(gòu)建集成分類(lèi)器). 研究表明,集成剪枝能夠有效提升集成學(xué)習(xí)的性能.

為了增加個(gè)體分類(lèi)器的多樣性,多模態(tài)擾亂策略被廣泛應(yīng)用于集成學(xué)習(xí),并形成了不同的基于多模態(tài)擾亂的集成方法. 例如,Lattine 等提出一種用于集成C4.5 決策樹(shù)的多模態(tài)擾亂策略[15],該策略將Bagging和隨機(jī)子空間(RSM)方法結(jié)合起來(lái). 與基于單模態(tài)擾亂的方法相比,Lattine 等的方法具有更好的性能. Altin?ay提出一種基于多模態(tài)擾亂的集成方法,該方法使用遺傳算法(GA)來(lái)選擇特征子集和最優(yōu)重采樣[16]. 實(shí)驗(yàn)結(jié)果表明: Altin?ay 的方法要優(yōu)于基于單模態(tài)擾亂的RSM方法. Zhou 等[11]提出一種集成KNN 分類(lèi)器的多模態(tài)集成算法,該算法對(duì)訓(xùn)練數(shù)據(jù)、特征空間和學(xué)習(xí)參數(shù)同時(shí)進(jìn)行擾亂. 與每一種基于單模態(tài)擾亂的方法相比,Zhou 等的方法都可以取得更好的性能.

本文從粗糙集[17]中的屬性約簡(jiǎn)技術(shù)出發(fā),提出了一種新的可同時(shí)擾亂屬性空間和訓(xùn)練集的集成剪枝算法EPA_AO. EPA_AO 的主要思路如下: (1)假設(shè)T和V分別表示訓(xùn)練集和驗(yàn)證集,我們通過(guò)近似約簡(jiǎn)技術(shù)從T的屬性集中產(chǎn)生M個(gè)近似約簡(jiǎn)AR1,…,ARM.(2)針對(duì)任意ARi(1≤i≤M),對(duì)T中的樣本進(jìn)行H次bootstrap 采樣,獲得H個(gè)采樣集S1,…,SH并從中選擇關(guān)于ARi的最優(yōu)采樣集Oi. 具體而言,對(duì)于任意采樣集Sj,我們利用ARi來(lái)對(duì)Sj進(jìn)行約簡(jiǎn),再利用分類(lèi)算法在Sj上訓(xùn)練個(gè)體分類(lèi)器Cj(1≤j≤H). 然后,利用V來(lái)分別評(píng)價(jià)個(gè)體分類(lèi)器C1,…,CH的性能,并將性能最好的個(gè)體分類(lèi)器所對(duì)應(yīng)的采樣集作為ARi的最優(yōu)采樣集Oi. (3)利用ARi以及ARi所對(duì)應(yīng)的最優(yōu)采樣集Oi來(lái)訓(xùn)練個(gè)體分類(lèi)器ICi(1≤i≤M). (4)基于多數(shù)投票的策略,將個(gè)體分類(lèi)器IC1,…,ICM集成在一起,從而得到集成分類(lèi)器.

本文的工作主要包括3 個(gè)部分: 首先,在粗糙集中引入近似約簡(jiǎn)的概念,并提出一種計(jì)算近似約簡(jiǎn)的算法; 其次,設(shè)計(jì)出一種基于近似約簡(jiǎn)與最優(yōu)采樣的多模態(tài)擾亂策略: 通過(guò)近似約簡(jiǎn)來(lái)擾亂屬性空間,并通過(guò)最優(yōu)采樣技術(shù)來(lái)擾亂訓(xùn)練集; 最后,基于上述多模態(tài)擾亂策略,提出一種集成剪枝算法. 該算法通過(guò)計(jì)算近似約簡(jiǎn)及其對(duì)應(yīng)的最優(yōu)采樣集,可以在保證個(gè)體分類(lèi)器性能的前提下,有效提升個(gè)體分類(lèi)器的多樣性. 證據(jù)KNN (K-近鄰)分類(lèi)算法[18]簡(jiǎn)單、有效,并且在許多領(lǐng)域都得到了廣泛應(yīng)用. 相對(duì)于傳統(tǒng)的KNN 算法,證據(jù)KNN 算法通常具有更好的性能. 因此,在實(shí)驗(yàn)中我們使用證據(jù)KNN 算法來(lái)訓(xùn)練個(gè)體分類(lèi)器. 我們利用多個(gè)UCI 數(shù)據(jù)集來(lái)比較EPA_AO 與現(xiàn)有的集成學(xué)習(xí)算法的性能. 實(shí)驗(yàn)結(jié)果表明,EPA_AO 具有更好的分類(lèi)性能.

1 預(yù)備知識(shí)

在粗糙集理論中,信息系統(tǒng)是一個(gè)四元組IS= (U,A,V,f),其中,U是一個(gè)非空、有限的對(duì)象集;A是一個(gè)非空、有限的屬性集;V=∪a∈AVa是所有屬性論域的并集(Va表示屬性a的值域);f:U×A→V是一個(gè)信息函數(shù),使得對(duì)任意a∈A,u∈U,f(u,a)∈Va[17,19]. 如果進(jìn)一步把屬性集A劃分為條件屬性集C和決策屬性集D,則這種特殊的信息系統(tǒng)被稱(chēng)為決策表DT= (U,C,D,V,f).

定義1. 不可分辨關(guān)系. 給定決策表DT= (U,C,D,V,f),對(duì)任意B?C∪D,我們將由B所確定的不可分辨關(guān)系IND(B)定義為[17,19]:

不可分辨關(guān)系IND(B)實(shí)際上是U上的一個(gè)等價(jià)關(guān)系,它將U劃分為多個(gè)不相交的等價(jià)類(lèi). 令U/IND(B)表示IND(B)所對(duì)應(yīng)的所有等價(jià)類(lèi)的簇,我們稱(chēng)U/IND(B)為由IND(B)所確定的論域U的劃分. 對(duì)任意u∈U,令[u]B表示U/IND(B)中包含對(duì)象u的等價(jià)類(lèi)[17,19].

定義2. 正區(qū)域. 給定決策表DT= (U,C,D,V,f),對(duì)任意B?C,我們將D的B-正區(qū)域POSB(D)定義為[17,19]:

定義3. 核屬性. 給定決策表DT= (U,C,D,V,f),對(duì)任意b∈C,如果POSC?(D)≠POSC(D),則我們稱(chēng)b是C中相對(duì)于D的一個(gè)核屬性[17,19].

給定決策表DT= (U,C,D,V,f),C中所有核屬性的集合被稱(chēng)為C相對(duì)于D的核.

定義4. 約簡(jiǎn). 給出決策表DT= (U,C,D,V,f),對(duì)任意B?C,如果POSB(D)=POSC(D)并且對(duì)任意b∈B,POSB?(D)≠POSB(D),則我們稱(chēng)B為C相對(duì)于D的一個(gè)約簡(jiǎn)[17,19].

接下來(lái),我們分析證據(jù)KNN 的原理. 證據(jù)KNN是由Denoeux 所提出的一種分類(lèi)算法[18],它將訓(xùn)練樣本在輸入空間不同部分的分布信息融入到傳統(tǒng)的KNN中,其主要思想是: 從所有訓(xùn)練樣本中計(jì)算出測(cè)試樣本t的k個(gè)最近鄰,將每個(gè)最近鄰都作為支持t所屬類(lèi)的證據(jù),然后結(jié)合所有最近鄰的基本概率賦值來(lái)得到t的類(lèi)別[18].

令L ={l1,…,lh}表示由h個(gè)類(lèi)標(biāo)簽所組成的標(biāo)簽集,T= {(u1,C(u1)),…,(ug,C(ug))}表示由g個(gè)樣本所組成的訓(xùn)練樣本集,T中每個(gè)樣本都用一個(gè)二元組(uj,C(uj))來(lái)表示,其中,uj表示第j個(gè)樣本,C(uj)∈L表示uj所屬的類(lèi)別標(biāo)簽,1≤j ≤ g.令Nw= {(v1,C(v1)),…,(vk,C(vk))}?T表示T中距離當(dāng)前的測(cè)試樣本tw最近的k個(gè)訓(xùn)練樣本(即tw的k-最近鄰),Nw中每個(gè)元素也用一個(gè)二元組(vj,C(vj))來(lái)表示,其中,vj表示tw的第j個(gè)最近鄰,C(vj)∈L表示vj所屬的類(lèi)別標(biāo)簽,1≤j ≤k.對(duì)于tw的任意一個(gè)最近鄰vj(1≤j ≤ k),如果C(vj)=lp∈L,則我們將 (vj,lp)看作是支持tw被分類(lèi)為lp的一個(gè)獨(dú)立證據(jù).

每一個(gè)獨(dú)立證據(jù) (vj,lp)的可信任度都由一個(gè)基本概率賦值函數(shù)來(lái)度量,即該基本概率賦值函數(shù)的值越大,則證據(jù) (vj,lp)的可信任度越高. 具體而言,(vj,lp)中所包含的分布信息將采用以下的基本概率賦值函數(shù)來(lái)刻畫(huà):Ew,j({lp})=β,Ew,j(L)= 1?β.在上述基本概率賦值函數(shù)中,β∈[0,1],β的具體取值由vj與tw的距離d(vj,tw)所決定(通常情況下,距離越大,則β越小). 很多學(xué)者通過(guò)定義相似函數(shù)來(lái)描述β與距離d(vj,tw)的關(guān)系,例如Denoeux 將相似函數(shù)定義成[18]: β=β0×e?γs×d(v j,tw)2.在上面的相似函數(shù)中,0 <β0<1 是一個(gè)預(yù)先指定的參數(shù),而γs> 0 則是另一個(gè)預(yù)先指定的參數(shù). 對(duì)任意vi,vj∈Nw,如果i≠j,則Ew,i與Ew,j是相互獨(dú)立的,這是因?yàn)檫@兩個(gè)基本概率賦值函數(shù)是由不同的訓(xùn)練樣本所生成的. 利用證據(jù)理論的組合規(guī)則,將Ew,1,…,Ew,k都組合起來(lái),從而獲得Ew=⊕vi∈NwEw,i.在獲得Ew之后,就可以利用其來(lái)計(jì)算tw相對(duì)于各個(gè)類(lèi)標(biāo)簽的置信度 函數(shù),從而實(shí)現(xiàn)對(duì)測(cè)試樣本tw的分類(lèi).

2 近似約簡(jiǎn)與EPA_AO 算法

在粗糙集中,給定決策表DT= (U,C,D,V,f),一個(gè)約簡(jiǎn)R是條件屬性集C的最小子集,它能充分識(shí)別具有不同類(lèi)別的對(duì)象. 理論上已經(jīng)證明,基于約簡(jiǎn)R所訓(xùn)練的分類(lèi)器與基于C所訓(xùn)練的分類(lèi)器具有相等的分類(lèi)能力[20]. 一些學(xué)者提出在C的每一個(gè)約簡(jiǎn)上訓(xùn)練一個(gè)個(gè)體分類(lèi)器,并利用這些個(gè)體分類(lèi)器來(lái)構(gòu)建集成分類(lèi)器. 由于C的約簡(jiǎn)與C具有相同的區(qū)分能力,因此,基于這些約簡(jiǎn)所構(gòu)建的個(gè)體分類(lèi)器不僅可以保證個(gè)體分類(lèi)器的分類(lèi)能力,還可以保證每個(gè)個(gè)體分類(lèi)器之間具有較好的差異性,降低個(gè)體分類(lèi)器訓(xùn)練的復(fù)雜度,從而高效率地訓(xùn)練出性能優(yōu)異的分類(lèi)器. 也就是說(shuō),我們可以利用粗糙集的屬性約簡(jiǎn)技術(shù)來(lái)擾亂屬性空間. 然而,利用屬性約簡(jiǎn)技術(shù)對(duì)屬性空間進(jìn)行擾亂時(shí)將面臨以下問(wèn)題: 約簡(jiǎn)個(gè)數(shù)過(guò)少. 很多時(shí)候,在決策表DT中,只存在少量的C的約簡(jiǎn). 如果沒(méi)有足夠多的約簡(jiǎn),那么我們就不能訓(xùn)練出足夠多的個(gè)體分類(lèi)器. 特別是,如果只存在一個(gè)約簡(jiǎn),那么我們就只能獲得一個(gè)個(gè)體分類(lèi)器. 為解決上述問(wèn)題,本文提出近似約簡(jiǎn)的概念,通過(guò)放寬對(duì)約簡(jiǎn)的嚴(yán)格要求(即C的約簡(jiǎn)必須與C具有完全相同的區(qū)分能力),可以獲得足夠多的C的近似約簡(jiǎn).下面,我們首先在粗糙集中引入近似約簡(jiǎn)的概念,利用近似約簡(jiǎn)我們可以構(gòu)建足夠多的個(gè)體分類(lèi)器; 其次,我們將近似約簡(jiǎn)與最優(yōu)采樣技術(shù)相結(jié)合,從而設(shè)計(jì)出一種新的多模態(tài)擾亂策略; 最后,基于上述多模態(tài)擾亂策略提出集成剪枝算法EPA_AO.

2.1 近似約簡(jiǎn)

近似約簡(jiǎn)是對(duì)粗糙集中經(jīng)典的約簡(jiǎn)概念的推廣.前面提到給定決策表DT= (U,C,D,V,f),如果R是C的約簡(jiǎn),則R與C必須具有完全相同的區(qū)分能力,即|POSR(D)| = |POSC(D)|. 根據(jù)上述嚴(yán)格的要求,我們可以得到關(guān)于C的約簡(jiǎn),但是往往約簡(jiǎn)的數(shù)量不夠多. 對(duì)此,有必要對(duì)上述要求進(jìn)行適當(dāng)?shù)胤艑?即要求R的區(qū)分能力不需要完全等于C,而是在一定程度上近似等于C. 基于上述考慮,我們可以提出近似約簡(jiǎn)的概念.與約簡(jiǎn)不同,近似約簡(jiǎn)的區(qū)分能力可以小于C.

定義5. 近似約簡(jiǎn). 給定決策表DT= (U,C,D,V,f),對(duì)任意AR?C,如果|POSC(D)| ≥ |POSAR(D)| ≥δ×|POSC(D)|,則AR被稱(chēng)為C相對(duì)于D的δ-近似約簡(jiǎn),其中,δ∈(0,1]是一個(gè)給定的閾值.

由上述定義可以看出,近似約簡(jiǎn)AR的區(qū)分能力不需要完全等于C(即|POSC(D)| ≥ |POSAR(D)|),而是近似等于C(即 |POSAR(D)| ≥δ×|POSC(D)|),且近似的程度由閾值δ來(lái)控制.δ的值越大,則AR的區(qū)分能力越接近于C,特別是當(dāng)δ=1 時(shí),近似約簡(jiǎn)AR就變成經(jīng)典的約簡(jiǎn). 接下來(lái),我們給出算法1,用于計(jì)算C中所有的近似約簡(jiǎn).

算法1. 近似約簡(jiǎn)的計(jì)算輸入: 決策表DT= (U,C,D,V,f),其中,U={u1,…,ug},C={a1,…,an}; 參數(shù)S 與MI,其中,S 是預(yù)先給定的近似約簡(jiǎn)的數(shù)量,MI 是最大迭代次數(shù).輸出: 近似約簡(jiǎn)集SAR.初始化: Core ← ?,SAR ← ?,其中,Core 表示所有核屬性的集合.1)采用計(jì)數(shù)排序的方法來(lái)計(jì)算D 的C-正區(qū)域POSC (D)[19].2)對(duì)任意 1≤ j ≤ n,循環(huán)執(zhí)行下列語(yǔ)句:3)采用計(jì)數(shù)排序的方法來(lái)計(jì)算POSC-aj;4)如果POSC-aj(D)≠ POSC (D),則Core ← Core∪{aj}.5)Remain ← C – Core.6)如果Remain=?,則SAR ← SAR∪C,并跳轉(zhuǎn)到步驟17).7)如果Remain≠?,則對(duì)任意 1≤ i ≤ MI,循環(huán)執(zhí)行下列語(yǔ)句:8)Temp ← Core;9)從Remain 中隨機(jī)選擇一個(gè)屬性a;10)Temp←Temp∪{a},Remain ← Remain – {a};11)對(duì)任意屬性b∈Remain,計(jì)算b 相對(duì)于Temp 和D 的重要性Sig (b,Temp,D),其中,Sig (b,Temp,D)= (|POSTemp∪(D)|–|POSTemp(D)|)/ |U|;12)選擇Remain 中重要性最大的屬性bmax;13)Temp ← Temp∪{bmax},Remain ← Remain – {bmax};14)重復(fù)執(zhí)行步驟11)–13),直到滿足近似約簡(jiǎn)的條件,即|POSTemp(D)≥ δ×|POSC (D)|;?15)如果Temp SAR,則SAR ← SAR∪{Temp};16)如果 |SAR| = S,則結(jié)束當(dāng)前循環(huán).17)輸出SAR.

對(duì)任意B?C,計(jì)算D的B正區(qū)域POSB(D)的時(shí)間復(fù)雜度通常為O(|U|2). 在算法1 中,我們通過(guò)計(jì)數(shù)排序的方法[21]來(lái)計(jì)算POSB(D),時(shí)間復(fù)雜度僅為O(|B|×|U|).在最壞的情況下,算法1 的時(shí)間復(fù)雜度為O(MI×|C|3×|U|),空間復(fù)雜度為O(|U|+|C|).

2.2 算法EPA_AO

由于只采用近似約簡(jiǎn)來(lái)擾亂屬性空間可能還不足以保證個(gè)體分類(lèi)器的多樣性,因此,本文將近似約簡(jiǎn)與最優(yōu)采樣技術(shù)結(jié)合在一起來(lái)實(shí)現(xiàn)一種多模態(tài)的擾亂,即不僅對(duì)屬性空間進(jìn)行擾亂,而且還利用最優(yōu)采樣技術(shù)來(lái)擾亂訓(xùn)練集. 在上述多模態(tài)擾亂策略的基礎(chǔ)上,我們提出了集成剪枝算法EPA_AO. 在EPA_AO 中,對(duì)于每個(gè)近似約簡(jiǎn)ARi(1≤i≤M),我們首先對(duì)訓(xùn)練集進(jìn)行多次bootstrap 采樣,然后選擇關(guān)于ARi的最優(yōu)采樣集Oi. 與其他采樣集相比,在Oi上訓(xùn)練的個(gè)體分類(lèi)器具有最高的分類(lèi)性能. 我們最終利用近似約簡(jiǎn)ARi以及ARi所對(duì)應(yīng)的最優(yōu)采樣集Oi來(lái)訓(xùn)練個(gè)體分類(lèi)器ICi(1≤i≤M),并對(duì)IC1,…,ICM進(jìn)行集成.

算法2. EPA_AO 算法輸入: 訓(xùn)練集TS = (U1,C1,D1,V1,f1); 驗(yàn)證集VS = (U2,C2,D2,V2,f2);參數(shù)H,其中,H 表示為選擇最優(yōu)采樣集而提前生成的bootstrap 采樣集的個(gè)數(shù).輸出: 集成分類(lèi)器EC.1)利用算法1 計(jì)算出TS 中的所有近似約簡(jiǎn)(令A(yù)R1,…,ARM 分別表示這些近似約簡(jiǎn)).2)對(duì)任意 1≤ i ≤ M,循環(huán)執(zhí)行下列語(yǔ)句:3)利用ARi 對(duì)TS 進(jìn)行約簡(jiǎn),并且令TSreduced = (U1*,ARi,D1,V1*,f1*)為約簡(jiǎn)后的訓(xùn)練集.4)利用ARi 對(duì)VS 進(jìn)行約簡(jiǎn),并且令VSreduced = (U2*,ARi,D2,V2*,f2*)為約簡(jiǎn)后的驗(yàn)證集.5)對(duì)任意 1≤ j ≤ H,循環(huán)執(zhí)行下列語(yǔ)句:6)對(duì)TSreduced 中的U1*進(jìn)行bootstrap 采樣,生成采樣集Sj;7)利用給定的分類(lèi)算法在采樣集Sj 上訓(xùn)練一個(gè)個(gè)體分類(lèi)器Cj;8)利用VSreduced 來(lái)評(píng)價(jià)個(gè)體分類(lèi)器Cj 的性能.9)從C1,…,CH 中選取分類(lèi)性能最好的個(gè)體分類(lèi)器Cmax 以及Cmax 所對(duì)應(yīng)的采樣集Smax,并且令Oi = Smax 表示關(guān)于近似約簡(jiǎn)ARi的最優(yōu)采樣集,其中,1≤ Cmax ≤ H.10)將Cmax 作為最終由近似約簡(jiǎn)ARi 以及最優(yōu)采樣集Oi 所訓(xùn)練的個(gè)體分類(lèi)器ICi.11)基于多數(shù)投票的策略,將個(gè)體分類(lèi)器IC1,…,ICM 集成在一起,從而得到集成分類(lèi)器EC.

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

為了評(píng)價(jià)EPA_AO 的有效性,我們開(kāi)展了相關(guān)實(shí)驗(yàn). 實(shí)驗(yàn)采用9 個(gè)來(lái)自于UCI 機(jī)器學(xué)習(xí)庫(kù)的數(shù)據(jù)集,并使用證據(jù)KNN 算法來(lái)生成個(gè)體分類(lèi)器. 關(guān)于這9 個(gè)數(shù)據(jù)集的具體信息見(jiàn)表1.

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

我們基于Java 實(shí)現(xiàn)了EPA_AO. 在實(shí)驗(yàn)中,對(duì)于表1 中的任意數(shù)據(jù)集T,我們首先使用等寬度算法對(duì)T中每一個(gè)連續(xù)型屬性進(jìn)行離散化處理,其中,bins=5;其次,我們將T隨機(jī)劃分成一個(gè)訓(xùn)練集Train (占樣本總數(shù)的50%)和一個(gè)測(cè)試集Test (剩下50%的樣本);然后,由于我們要為EPA_AO 提供一個(gè)單獨(dú)的驗(yàn)證集VS來(lái)獲得當(dāng)前近似約簡(jiǎn)AR的最優(yōu)采樣集,因此我們從Train 中隨機(jī)選擇50%的樣本來(lái)生成VS.

在運(yùn)行證據(jù)KNN 算法之前,我們要對(duì)β0與γs這兩個(gè)參數(shù)的取值進(jìn)行設(shè)置. 在我們的實(shí)驗(yàn)中,β0被設(shè)置為 0.95,而γs則被設(shè)置為相應(yīng)類(lèi)別訓(xùn)練樣本的平均距離的倒數(shù)[12],在經(jīng)過(guò)多次取值實(shí)驗(yàn)后,發(fā)現(xiàn)β0為0.95時(shí)證據(jù)KNN 算法訓(xùn)練出的個(gè)體分類(lèi)器精度最好. 對(duì)于EPA_AO,我們需要對(duì)S和MI 這兩個(gè)參數(shù)以及閾值δ的取值進(jìn)行設(shè)置. 在我們的實(shí)驗(yàn)中,S和MI分別被設(shè)置為10 和25,而δ則被設(shè)置為 0.9 (實(shí)驗(yàn)發(fā)現(xiàn),S設(shè)為10 時(shí)既能避免約簡(jiǎn)個(gè)數(shù)太少而影響集成分類(lèi)器的分類(lèi)性能,也不會(huì)因約簡(jiǎn)太多而影響訓(xùn)練的效率;MI設(shè)為25 時(shí)實(shí)驗(yàn)效果最佳;δ設(shè)為0.9 時(shí)能夠保證約簡(jiǎn)

后的個(gè)體分類(lèi)器的分類(lèi)能力與約簡(jiǎn)前比較接近,不會(huì)因?yàn)榉诸?lèi)能力下降太多而影響集成分類(lèi)器的整體性能).

下面,我們首先比較EPA_AO 與文獻(xiàn)[12]中所采用的RSM 方法的性能. 在文獻(xiàn)[12]中,RSM 也通過(guò)證據(jù)KNN 算法來(lái)生成個(gè)體分類(lèi)器. 證據(jù)KNN 的性能依賴(lài)于k的值,因此,對(duì)于每個(gè)數(shù)據(jù)集,我們?yōu)閗賦予不同的取值(即k= 3、k= 5 和k= 7),從而得到不同k值下的實(shí)驗(yàn)結(jié)果.

表2 給出了EPA_AO 和RSM 這兩個(gè)算法在不同k值下的分類(lèi)性能(為了避免偶然性,我們將全部實(shí)驗(yàn)都重復(fù)執(zhí)行10 遍,表2 中所列出的實(shí)驗(yàn)結(jié)果都是這10 次實(shí)驗(yàn)的平均值).

表2 EPA_AO 和RSM 算法在不同k 值下的準(zhǔn)確率

根據(jù)表2,我們可以得出這樣的結(jié)論: EPA_AO 的分類(lèi)準(zhǔn)確率在大部分?jǐn)?shù)據(jù)集上都比RSM 更高. 具體而言,如果將k設(shè)置為7,則EPA_AO 的準(zhǔn)確率在所有數(shù)據(jù)集上均要優(yōu)于RSM; 如果將k設(shè)置為 5,則EPA_AO的準(zhǔn)確率在除了Vowel 之外的其余8 個(gè)數(shù)據(jù)集上均要優(yōu)于RSM; 如果將k設(shè)置為 3,則EPA_AO 的準(zhǔn)確率在其中5 個(gè)數(shù)據(jù)集上要優(yōu)于RSM,而在另外4 個(gè)數(shù)據(jù)集上 (即Ionosphere、Sonar、Vowel 和WDBC)要低于RSM. 特別是,如果我們統(tǒng)計(jì)多個(gè)k值下的平均準(zhǔn)確率,則可以發(fā)現(xiàn)EPA_AO 的性能在總共7 個(gè)數(shù)據(jù)集上(除了Vowel 和WDBC)均要優(yōu)于GAv1 與GAv2. 由上述實(shí)驗(yàn)結(jié)果可知,本文提出的EPA_AO 算法其分類(lèi)性能明顯優(yōu)于現(xiàn)有的集成學(xué)習(xí)算法.

接下來(lái),我們將比較EPA_AO 與兩種基于GA (遺傳算法)的集成剪枝算法的性能. 這兩種基于GA 的集成剪枝算法是由Altin?ay 所提出[12],分別稱(chēng)為: GAv1(GA version 1)和GAv2 (GA version 2). 與本文所提出的EPA_AO 類(lèi)似,GAv1 和GAv2 也采用多模態(tài)擾亂策略來(lái)訓(xùn)練個(gè)體分類(lèi)器.

表3 給出了EPA_AO、GAv1 與GAv2 這3 個(gè)算法的分類(lèi)準(zhǔn)確率(因?yàn)镚Av1 與GAv2 能夠自動(dòng)選取最優(yōu)的k值以得到最高的準(zhǔn)確率[12],所以這里我們只給出了EPA_AO 的最優(yōu)結(jié)果,即k= 7 時(shí)的準(zhǔn)確率. 此外,我們還統(tǒng)計(jì)了EPA_AO 在不同k值下的平均準(zhǔn)確率).

根據(jù)表3,我們可以得出這樣的結(jié)論: EPA_AO 的分類(lèi)準(zhǔn)確率在大部分?jǐn)?shù)據(jù)集上都比GAv1 與GAv2 這兩個(gè)算法更高. 具體而言,如果將k設(shè)置為 7,則EPA_AO 的準(zhǔn)確率在總共8 個(gè)數(shù)據(jù)集上均要優(yōu)于GAv1 與GAv2,只是在Vowel 上表現(xiàn)差一些. 尤其是在以下4 個(gè)數(shù)據(jù)集上: Credit-g、Liver、Pima 與Vehicle,EPA_AO 的分類(lèi)準(zhǔn)確率相對(duì)于GAv1 與GAv2 這兩個(gè)算法有明顯的提升(提升了10%以上). 此外,如果我們統(tǒng)計(jì)EPA_AO 在多個(gè)k值下的平均準(zhǔn)確率,則可以發(fā)現(xiàn)EPA_AO 的性能在總共 7 個(gè)數(shù)據(jù)集上(除了Vowel 和WDBC)均要優(yōu)于GAv1 與GAv2. 由上述實(shí)驗(yàn)結(jié)果可知,本文提出的EPA_AO 算法其分類(lèi)性能明顯優(yōu)于現(xiàn)有的集成學(xué)習(xí)算法.

表3 EPA_AO、GAv1 與GAv2 的準(zhǔn)確率

4 總結(jié)

為了增加集成學(xué)習(xí)中個(gè)體分類(lèi)器的多樣性,本文提出了近似約簡(jiǎn)的概念,并由此設(shè)計(jì)出一種新的多模態(tài)擾亂策略. 該策略通過(guò)近似約簡(jiǎn)來(lái)擾亂屬性空間,并通過(guò)最優(yōu)采樣技術(shù)來(lái)擾亂訓(xùn)練集. 近似約簡(jiǎn)是對(duì)粗糙集中經(jīng)典的約簡(jiǎn)概念的擴(kuò)展,它能夠解決給定決策表中約簡(jiǎn)數(shù)量可能不足的問(wèn)題. 在上述多模態(tài)擾亂策略的基礎(chǔ)上,本文提出了集成剪枝算法EPA_AO. 實(shí)驗(yàn)結(jié)果表明,EPA_AO 算法的性能要優(yōu)于現(xiàn)有的集成算法.

由于本文在Pawlak 的經(jīng)典粗糙集模型[17]基礎(chǔ)上提出了近似約簡(jiǎn)的概念,而經(jīng)典粗糙集模型更適合于處理離散型屬性,所以,EPA_AO 需要通過(guò)某種離散化技術(shù)將所有的連續(xù)型屬性轉(zhuǎn)換為離散型屬性. 然而,屬性離散化可能會(huì)導(dǎo)致信息的丟失問(wèn)題. 因此,在下一步工作中,我們計(jì)劃將EPA_AO 擴(kuò)展到鄰域粗糙集[22]或者模糊粗糙集[23]等擴(kuò)展的粗糙集模型中,從而可以不經(jīng)過(guò)離散化過(guò)程而直接處理連續(xù)型屬性.