融入差異性的帕累托集成剪枝方法

魏苗苗 杭 杰

(南京郵電大學(xué)計(jì)算機(jī)學(xué)院，南京， 210003)

引 言

分類與回歸是監(jiān)督學(xué)習(xí)研究中的基本任務(wù)。分類與回歸最終的目標(biāo)是在一個(gè)由各種可能的函數(shù)組成的假設(shè)空間中搜索與實(shí)際目標(biāo)分類函數(shù)最接近的分類器，使該分類器盡可能精確地分類未知實(shí)例。然而，單個(gè)學(xué)習(xí)器在某些情況下的泛化性能是有限的。為了提高學(xué)習(xí)器的泛化性能，學(xué)者們提出了集成學(xué)習(xí)的思想。1997年Dietterich[1]指出集成學(xué)習(xí)將會(huì)成為機(jī)器學(xué)習(xí)領(lǐng)域的4大研究方向之首。

集成學(xué)習(xí)是使用多個(gè)學(xué)習(xí)器共同決策的過(guò)程。集成學(xué)習(xí)一般可以分為兩個(gè)步驟：(1) 產(chǎn)生多個(gè)不同的基分類器，(2) 采用某種集成策略(如投票法)來(lái)決定最終的分類結(jié)果[2]。按照基分類器之間的種類關(guān)系，可以把集成學(xué)習(xí)分為同質(zhì)集成學(xué)習(xí)和異質(zhì)集成學(xué)習(xí)[3]。同質(zhì)集成學(xué)習(xí)是集成多個(gè)同種類的基分類器，該同種類的代表分類器可以是人工神經(jīng)網(wǎng)絡(luò)、決策樹(shù)、樸素貝葉斯和K-近鄰等。而異質(zhì)集成學(xué)習(xí)是集成多個(gè)各種類別的基分類器，其中代表的基分類器有疊加法[4]和元學(xué)習(xí)法[5]等。隨著機(jī)器學(xué)習(xí)領(lǐng)域不斷深入的研究，集成學(xué)習(xí)已經(jīng)應(yīng)用到多個(gè)領(lǐng)域。在傳統(tǒng)的集成學(xué)習(xí)中，大多數(shù)的方法是先產(chǎn)生多個(gè)不同的弱分類器，再由所有的基分類器構(gòu)建一個(gè)強(qiáng)分類器。盡管這種方法可以有效地提高分類器的泛化性能，但是該方法存在一些不足：集成所有的基分類器將消耗大量的時(shí)間和空間資源；預(yù)測(cè)速度也隨著基分類器的增多而急劇下降。于是，Zhou等[6]于2002年首次提出了“選擇性集成”的概念，選擇性集成的思路是選用部分基學(xué)習(xí)器集成的效果可能比集成所有的基分類器效果更優(yōu)。

集成剪枝又稱選擇性集成、集成簡(jiǎn)化，它是在訓(xùn)練出所有基學(xué)習(xí)器之后，基于某種準(zhǔn)則，選擇一部分基學(xué)習(xí)器(所有基學(xué)習(xí)器的一個(gè)最優(yōu)子集)進(jìn)行集成，最終得到一個(gè)強(qiáng)分類器。集成剪枝的過(guò)程主要包括3步：產(chǎn)生不同的分類器；根據(jù)驗(yàn)證集選擇最優(yōu)的分類器子集；集成分類器子集。集成剪枝方法的異同主要取決于剪枝策略。剪枝策略可以根據(jù)分類器的不同劃分為基于分類問(wèn)題的剪枝策略和基于回歸問(wèn)題的剪枝策略。由于在回歸問(wèn)題中，集成剪枝問(wèn)題研究的較少且效果不明顯，所以本節(jié)主要討論基于分類問(wèn)題的剪枝策略。Tsoumakas[7]等總結(jié)了集成剪枝的多種策略，文獻(xiàn)[8-15]中將集成剪枝策略分為基于排序的剪枝，基于聚類的剪枝，基于優(yōu)化的剪枝以及其他方法的剪枝。

剪枝過(guò)程中使用的剪枝策略決定了集成剪枝的方法。目前還沒(méi)有確定的最佳剪枝策略方法，已有的代表性剪枝策略使用遺傳算法進(jìn)行剪枝[6]，采用人工免疫算法進(jìn)行剪枝[16]，用聚類算法進(jìn)行剪枝[9]，2015年，Qian等又采用帕累托(Pareto)占優(yōu)的雙目標(biāo)優(yōu)化思想進(jìn)行剪枝[17]。然而采用遺傳算法和人工免疫算法剪枝的復(fù)雜度相當(dāng)高；利用聚類的中心參與集成剪枝的聚類算法也忽略了單個(gè)學(xué)習(xí)器有限的泛化性能；Pareto占優(yōu)的雙目標(biāo)優(yōu)化集成剪枝忽略了分類器之間的差異性。因此，為了改進(jìn)上述方法的不足，在Pareto集成剪枝的基礎(chǔ)上，本文提出了融入差異性的Pareto集成剪枝方法。

1 融入差異性的Pareto集成剪枝

1.1 Pareto集成剪枝方法

在工程與科學(xué)計(jì)算領(lǐng)域中，存在著許多多目標(biāo)優(yōu)化的問(wèn)題(Multi-objective optimization problem, MOP)。多目標(biāo)優(yōu)化問(wèn)題的有效解也稱為Pareto最優(yōu)解。集成剪枝方法有兩個(gè)目標(biāo)：最小化集成的基分類器的個(gè)數(shù)以及最大化集成后分類器的泛化性能。對(duì)于這兩個(gè)目標(biāo)，研究者首先想到的是將這兩個(gè)目標(biāo)通過(guò)某種數(shù)學(xué)模型整合為一個(gè)優(yōu)化目標(biāo)。雖然這種方法存在一定的道理，但是這種合二為一的方法也與最初的集成優(yōu)化目標(biāo)有所偏差。文獻(xiàn)[17]方法將最小化基分類器的個(gè)數(shù)和最大化分類器的泛化性能作為兩個(gè)單獨(dú)的優(yōu)化目標(biāo)共同優(yōu)化。

(1)

在該雙目標(biāo)優(yōu)化中，f(Hc)表示選中的|c|個(gè)分類器的泛化誤差，|c|表示集成規(guī)模。定義1介紹兩個(gè)目標(biāo)之間的Pareto占優(yōu)關(guān)系。

定義1[17]Pareto占優(yōu)或Pareto支配：令存在一個(gè)雙目標(biāo)函數(shù)φ=(φ1,φ2)，C表示所有解決方案向量的集合。若存在兩個(gè)不相等的解決方案c，c'∈C，則有

(a)c弱占優(yōu)于c'，當(dāng)滿足φ1(c)φ1(c')并且φ2(c)φ2(c')時(shí)，表示為c弱占優(yōu)于c'。

(b)c占優(yōu)于c'，當(dāng)滿足c弱占優(yōu)于c'且同時(shí)滿足φ1(c)<φ1(c')或者φ2(c)<φ2(c')，表示為c占優(yōu)于c'。

若在所有解決方案的集合C中，若沒(méi)有任一個(gè)方案占優(yōu)于c，那么c就是Pareto最優(yōu)的解決方案。而初始化解決方案c的方法是隨機(jī)產(chǎn)生的一個(gè)由0，1組成的向量，并將此向量放入候選方案集合C中；然后通過(guò)迭代更新C中的解決方案。每次迭代都將在C中隨機(jī)挑選一個(gè)解決方案c，給c一定的擾動(dòng)使之生成c′；若C中沒(méi)有任何一個(gè)方案能夠占優(yōu)于c′，則將c′加入集合C中，同時(shí)將集合C中被c′弱占優(yōu)的方案去除。而對(duì)于每次迭代過(guò)程中生成的c′，文獻(xiàn)中采用可變深度搜索[17](Variable depth search，VDS)的方法(見(jiàn)算法2)，搜索出與c′相距一個(gè)漢明距離的所有解決方案。在這些解決方案中若能搜索出可占優(yōu)于c′的解決方案，則用該占優(yōu)的解決方案代替c′。將c′從C中去除。深度優(yōu)先搜索的方法是有序的局部貪心搜索，每次搜索都選擇局部最優(yōu)解。為了避免重復(fù)搜索，算法中引入一個(gè)L變量，用于記錄已被搜索過(guò)了的路徑。最終從候選集合C中選出泛化誤差最低的解決方案作為雙目標(biāo)的問(wèn)題的解。

算法1Pareto集成剪枝

輸入：

一系列已訓(xùn)練的分類器H={hα}nα=1，第一個(gè)目標(biāo)函數(shù)f(Hc)，第二個(gè)目標(biāo)|c|,評(píng)價(jià)準(zhǔn)則evaluation

輸出：argminc∈Cevaluation(c)

1．令F(c)=(f(Hc),|c|)為待優(yōu)化的雙目標(biāo)函數(shù)。

2．初始化c為一個(gè)n維向量，元素由0,1隨機(jī)組成。

3．Repeat

4．在集合C中隨機(jī)抽取一個(gè)方案c

7.C=(C-{z∈C|c'弱占優(yōu)于z})∪{c′}

8.Q=VDS(e，c')

9.forq∈Q

11.C=(C-{z∈C|q弱占優(yōu)于z})∪{q}

算法2可變深度搜索(Variable depth search，VDS)

輸入:一個(gè)偽布爾函數(shù)e,一個(gè)解決方案c

輸出：Q

(1)Q=?，L=?

(2) 令N(·)為與解決方案c相距一個(gè)漢明距離的所有解決方案的集合

(3) While

Vc={y∈N(c)|(yk≠ck?k∈L)}=?

(4) 選擇使得e達(dá)到最小值的y∈Vc

(5)Q=Q∪{y}

(6)L=L∪{k|yk≠ck}

(7)c=y

在該雙目標(biāo)優(yōu)化中，第1個(gè)目標(biāo)是最大化分類準(zhǔn)確率，第2個(gè)目標(biāo)是最小化剪枝后分類器的個(gè)數(shù)，即集成規(guī)模。算法1的(6～7)和(9～11)步已經(jīng)決定了搜索的路徑方向，因此不會(huì)存在只優(yōu)化其中一個(gè)目標(biāo)的問(wèn)題。VDS只是搜索局部最優(yōu)值，不影響最優(yōu)解決方案的搜索方向。評(píng)價(jià)準(zhǔn)則evaluation可以根據(jù)側(cè)重點(diǎn)來(lái)選取，更加側(cè)重分類準(zhǔn)確則在剪枝后的集合C中根據(jù)f(Hc)函數(shù)選取最優(yōu)的解決方案，若更加側(cè)重集成分類器的規(guī)模，則根據(jù)分類器的個(gè)數(shù)|c|選取。采用已選取的分類結(jié)果在驗(yàn)證集上的泛化誤差來(lái)衡量泛化性能f(Hc)，f(Hc)越小代表泛化性能越高；將差異性和泛化誤差都?xì)w一化到(0,1)之間，使得目標(biāo)結(jié)果g(c)滿足越接近0泛化性能越好、差異性越大。剪枝過(guò)程完成后，采用熵度量[18]衡量分類器之間的差異性，該差異性也被歸一化到(0,1)之間，且越接近0差異性越小。算法1中的(3)循環(huán)的次數(shù)設(shè)為|-n2logn-|[17],實(shí)驗(yàn)選出最優(yōu)的分類器子集之后，采用多數(shù)投票的方法進(jìn)行集成。

1.2 融入差異性的集成剪枝

分類器集成中的差異性學(xué)習(xí)途徑通?？梢苑譃閮煞N，隱性差異性和顯性差異性。隱性差異性是指通過(guò)不同的數(shù)據(jù)訓(xùn)練不同的基分類器，隱性地使得各分類器具有差異性，如Bagging[19],Boosting[20]；顯性差異性是指最大化某個(gè)與差異性相關(guān)的目標(biāo)函數(shù)來(lái)集成不同的分類器，如半定規(guī)劃[21]。本文研究的差異性是隱性差異性與顯性差異性的組合，實(shí)驗(yàn)前期使用Bagging[19]訓(xùn)練不同的基分類器，后期使用融入差異性的目標(biāo)函數(shù)對(duì)分類器進(jìn)行剪枝，使之為集成提供差異較大的基分類器的集合。差異性是提高集成泛化能力的必要條件，對(duì)于提高集成學(xué)習(xí)的泛化能力具有重要意義，有關(guān)差異性的研究是研究集成學(xué)習(xí)的基礎(chǔ)。Ali等[22]指出只有當(dāng)分類器集合中各個(gè)分類器具有顯著的互補(bǔ)性，它們的集成效果才能充分體現(xiàn)。

Pareto集成剪枝方法可以提高分類精確度、縮減集成規(guī)模，然而在分類器差異性這方面的工作仍是空白。集成學(xué)習(xí)需要有差異性，分類器之間的差異性可以確保分類器之間的相互獨(dú)立性，若一系列分類器的集成效果突出，那么分類器之間的差異應(yīng)足夠包含分類的錯(cuò)分類型。在差異性研究的基礎(chǔ)上，本文提出了融入差異性的帕累托集成剪枝方法(Pareto ensemble pruning with diversity, PEPD)。該方法將差異性的度量融入Pareto集成剪枝算法的第1個(gè)目標(biāo)中，第2個(gè)目標(biāo)仍是集成規(guī)模。因此，PEPD算法可以同時(shí)優(yōu)化精準(zhǔn)度，差異性以及集成規(guī)模這3個(gè)目標(biāo)。

差異性學(xué)習(xí)和分類器準(zhǔn)確率度量在集成學(xué)習(xí)中有著不同目的和算法處理過(guò)程。因此，實(shí)施這些不同的學(xué)習(xí)策略算法最初是分開(kāi)的、獨(dú)立的。Yin等[23]提出將差異性與稀疏性線性相加為一個(gè)優(yōu)化目標(biāo)的方法。而本文是在該P(yáng)areto占優(yōu)的雙目標(biāo)優(yōu)化的基礎(chǔ)上，在泛化目標(biāo)中線性增加了差異性度量，以增加差異性對(duì)于剪枝策略的影響。第1個(gè)優(yōu)化目標(biāo)更改為泛化誤差和差異性的線性結(jié)合體：minc(μf(Hc)+λd(Hc))，第2個(gè)優(yōu)化目標(biāo)仍是集成規(guī)模min|c|。那么融入差異性的帕累托集成剪枝方法的目標(biāo)函數(shù)可以表示成

(2)

其中，融入差異性的集成d(Hc)表示該|c|個(gè)分類器之間的差異性。μ(0<μ<1)和λ(0<λ<1)是調(diào)節(jié)泛化誤差和差異性之間所占比重的參數(shù)，μ+λ=1。根據(jù)數(shù)據(jù)集的不同對(duì)參數(shù)μ、λ進(jìn)行調(diào)節(jié)。為了減少f(Hc)和d(Hc)函數(shù)值本身對(duì)優(yōu)化目標(biāo)即線性函數(shù)的影響，實(shí)驗(yàn)中將f(Hc)和d(Hc)都進(jìn)行了歸一化處理。

算法3融入差異性的Pareto集成剪枝算法

輸入：

一系列已訓(xùn)練的分類器H={hα}nα=1，第1個(gè)目標(biāo)函數(shù)g(c)=μf(Hc)+λd(Hc)，第2個(gè)目標(biāo)|c|,評(píng)價(jià)準(zhǔn)則evaluation

輸出：argminc∈Cevaluation(c)

1．令F(c)=(g(c),|c|)為待優(yōu)化的雙目標(biāo)函數(shù)。

2．初始化c為一個(gè)n維向量，元素由0,1隨機(jī)組成。

3．Repeat

4． 在集合C中隨機(jī)抽取一個(gè)方案c

7.C=(C-{z∈C|c'弱占優(yōu)于z})∪{c'}

8.Q=VDS(e，c')

9.forq∈Q

11.C=(C-{z∈C|q弱占優(yōu)于z})∪{q}

將該融入差異性的改進(jìn)算法與算法1相比較，首先將輸入的第一個(gè)優(yōu)化目標(biāo)改為g(c)=μf(Hc)+λd(Hc)；其次，在每一次的占優(yōu)、弱占優(yōu)的比較中，目標(biāo)函數(shù)φ1=μf(Hc)+λd(Hc)，φ2=|c|，即在每1次的迭代比較中，都會(huì)將分類器子集的分類準(zhǔn)確率，各分類器間的差異性以及集成規(guī)模做對(duì)比。若某解決方案c的第1個(gè)目標(biāo)優(yōu)于另一解決方案c′的第1個(gè)優(yōu)化目標(biāo)，而c的第2個(gè)優(yōu)化目標(biāo)劣于c′的第2個(gè)優(yōu)化目標(biāo)，即|c|>|c′|。它們都不滿足任一方占優(yōu)或弱占優(yōu)另一方的情況，那么將這兩個(gè)解決方案均加入解決方案集合C中。直到某次迭代中存在其他方案能夠占優(yōu)于c或c′，將c或c′頂替出集合。若不存在其他解決方案可以占優(yōu)c、c′，則在挑選最終解決方案時(shí)，按照evaluation進(jìn)行篩選。evaluation是按照相同集成規(guī)模選擇具有最優(yōu)第1目標(biāo)的剪枝方案，為確保集成剪枝方法不降低集成分類精準(zhǔn)度，因此在不同集成規(guī)模時(shí)也選擇最優(yōu)第1目標(biāo)的剪枝方案。

1.3 差異性度量

單分類器之間的差異性在集成學(xué)習(xí)中起著至關(guān)重要的作用。然而到目前為止，在學(xué)術(shù)界還沒(méi)有一個(gè)可被公認(rèn)的差異性的定義，因此，明確定義分類器之間的差異性比較困難。Kuncheva等對(duì)比了不同差異性度量的方法并且分析了它們與集成準(zhǔn)確率之間的關(guān)系[24]。這些度量差異性的方法可以分為成對(duì)的差異性度量(Q統(tǒng)計(jì)量，相關(guān)系數(shù)，不一致度量以及雙錯(cuò)度量)和非成對(duì)的差異性度量(熵度量，KW方差以及難點(diǎn)度量)兩個(gè)類別。為了驗(yàn)證融入差異性的集成剪枝方法確實(shí)對(duì)集成泛化性能有提升作用，可以在差異性度量的兩類方法中分別選取一個(gè)度量方法。

已知剪枝后的分類器個(gè)數(shù)θ=|c|，則剪枝后的分類器可表示為Hc={h1,h2,…,hθ}，N表示測(cè)試集中的樣本數(shù)。根據(jù)剪枝后的分類器對(duì)測(cè)試樣本的預(yù)測(cè)，可構(gòu)造一個(gè)矩陣W=[wα,j]θ×N用于度量分類器之間的差異性。當(dāng)wα,j=1時(shí)，表示第α個(gè)分類器對(duì)測(cè)試集中第j個(gè)樣本的正確預(yù)測(cè)，反之，wα,j=0表示錯(cuò)誤預(yù)測(cè)。兩種差異性度量的方法詳述如下。

(1) 不一致度量

(3)

其中

(4)

d(Hc)=1-DIS

(5)

(2) 熵度量

(6)

(7)

d(Hc)=1-ENT

(8)

其中，不一致度量為成對(duì)的差異性度量方法，熵度量為非成對(duì)的差異性度量方法。兩種度量方法都將差異性d(Hc)限定在(0,1)范圍之間，d(Hc)越接近于0代表差異性越大，反之d(Hc)越接近于1代表差異性越小，與泛化誤差函數(shù)f(Hc)恰好保持一致收斂。

表1 實(shí)驗(yàn)中的8個(gè)真實(shí)數(shù)據(jù)集

2 實(shí)驗(yàn)評(píng)價(jià)與分析

2.1 數(shù)據(jù)集

為驗(yàn)證提出的融入差異性的Pareto剪枝方法的有效性，選擇8個(gè)公開(kāi)的UCI數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。數(shù)據(jù)集的詳細(xì)信息如表1所示。若實(shí)例個(gè)數(shù)為r，根據(jù)數(shù)據(jù)集的大小將數(shù)據(jù)集劃分為3種規(guī)模：小規(guī)模數(shù)據(jù)(010 000)。每個(gè)規(guī)模的數(shù)據(jù)都選取2-3個(gè)數(shù)據(jù)集，則數(shù)據(jù)集的大小可以從270涵蓋到19 020。實(shí)驗(yàn)將對(duì)比多個(gè)數(shù)據(jù)集在不同剪枝方法下的泛化能力以及分類器之間的差異性，如表1所示每個(gè)數(shù)據(jù)集對(duì)應(yīng)一個(gè)編號(hào)，圖1～6中的橫坐標(biāo)對(duì)應(yīng)的編號(hào)也如此。

2.2 評(píng)價(jià)度量

在評(píng)價(jià)模型的性能時(shí)，評(píng)價(jià)指標(biāo)起著至關(guān)重要的作用。對(duì)于分類器的集成，通常的評(píng)價(jià)指標(biāo)有分類精準(zhǔn)度、錯(cuò)誤率或差異性來(lái)衡量。本實(shí)驗(yàn)將泛化誤差和差異性綜合為一個(gè)評(píng)價(jià)度量，即

g(c)=μf(Hc)+λd(Hc)

(9)

其中f(Hc)為分類器子集的泛化誤差函數(shù)，d(Hc)為熵度量(非成對(duì)的差異性度量方法之一)或者不一致度量(成對(duì)的差異性度量方法之一)。由于泛化誤差函數(shù)和差異性函數(shù)都?xì)w一化到(0,1)之間，而且值越小泛化性能及差異性能越好，參數(shù)μ，λ滿足μ+λ=1，可以分別定義為0.5和0.5，也可以根據(jù)數(shù)據(jù)集的不同做適當(dāng)?shù)恼{(diào)整。第1個(gè)優(yōu)化目標(biāo)分別融入兩種不同差異性度量方法(熵度量和不一致度量)作為評(píng)價(jià)準(zhǔn)則，將該改進(jìn)算法剪枝后的分類器之間的差異性與Pareto集成剪枝后的分類器之間的差異性做對(duì)比實(shí)驗(yàn)，使用熵度量方法衡量剪枝后分類器間的差異性。

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

2.3.1 實(shí)驗(yàn)結(jié)果

本實(shí)驗(yàn)主要對(duì)比Bagging集成、Pareto集成剪枝方法以及融入差異性的Pareto集成剪枝方法，分別記為Bagg, Bagg_Prun和Bagg_Div_Prun。選擇對(duì)數(shù)據(jù)擾動(dòng)比較敏感的k近鄰分類器[25]和C4.5決策樹(shù)分類器[26]分類器用于實(shí)驗(yàn)。隨機(jī)抽取數(shù)據(jù)集的60%用于訓(xùn)練分類模型(Train)，余下40%的數(shù)據(jù)中一半作為驗(yàn)證集(Validation)，另一半作為測(cè)試集(Test)。根據(jù)數(shù)據(jù)集的大小訓(xùn)練出多個(gè)基分類器，數(shù)據(jù)集較大則訓(xùn)練的基分類器個(gè)數(shù)較多，反之訓(xùn)練個(gè)數(shù)較少。將基分類器在測(cè)試集上的預(yù)測(cè)結(jié)果轉(zhuǎn)化為一個(gè)預(yù)測(cè)矩陣P=[p1,p2,…,pn]，代表n個(gè)分類器對(duì)同一個(gè)測(cè)試集的不同預(yù)測(cè)結(jié)果向量，其中pα={p1α,p2α,…,pTα}表示第α(α∈[1,n])個(gè)分類器在T個(gè)測(cè)試樣本中的預(yù)測(cè)結(jié)果，ptα表示第α個(gè)分類器對(duì)第t個(gè)測(cè)試樣本的預(yù)測(cè)值，預(yù)測(cè)正確則ptα=1，反之ptα=-1。

2.3.2 結(jié)果分析

實(shí)驗(yàn)對(duì)比了集成學(xué)習(xí)和集成剪枝的預(yù)測(cè)效果，以及融入差異性的集成剪枝和未融入差異性的集成剪枝的預(yù)測(cè)效果。如表2，3所示，表中粗體數(shù)字代表融入差異性的集成剪枝方法得到更優(yōu)的分類效果。如圖1，2所示，集成剪枝后的預(yù)測(cè)能力比集成學(xué)習(xí)的預(yù)測(cè)能力稍強(qiáng)，加入差異性的集成剪枝比沒(méi)有加入差異性的剪枝策略泛化性能高。如圖3，4所示，集成學(xué)習(xí)中基分類器的規(guī)模較大，而兩種集成剪枝的基分類器規(guī)模相當(dāng)且都比集成學(xué)習(xí)的規(guī)模要小許多，剪枝后的泛化性能與集成學(xué)習(xí)的泛化性能相當(dāng)或者稍高，表明剪枝策略在不降低泛化性能的基礎(chǔ)上有效減少集成學(xué)習(xí)的時(shí)間和空間資源的消耗，融入差異性的集成剪枝與Pareto集成剪枝方法集成規(guī)模相當(dāng)，但能獲得更高的泛化性能(圖1,2所示)。分別采用不一致度量(成對(duì))和熵度量(非成對(duì))的差異性度量方法融入目標(biāo)1中，再綜合泛化誤差對(duì)剪枝模型進(jìn)行篩選。最后統(tǒng)一使用熵度量的方法分別衡量?jī)煞N剪枝方法(PEP與PEPD)的分類器之間的差異性，實(shí)驗(yàn)結(jié)果如圖5，6所示。圖5,6表明，融入差異性的集成剪枝策略確實(shí)能夠提升分類器之間的差異性。

表2 基于KNN的不同集成剪枝方法準(zhǔn)確率對(duì)比

表3 基于C4.5的不同集成剪枝方法準(zhǔn)確率對(duì)比

圖1 基于KNN的不同集成方法準(zhǔn)確率

圖2 基于C4.5的不同集成方法準(zhǔn)確率

圖3 基于KNN的不同集成剪枝方法集成規(guī)模

圖4 基于C4.5的不同集成剪枝方法集成規(guī)模

圖5 融入不一致度量后Bagg-Div-Prun, Bagg-Prun的差異性

圖6 融入熵度量后Bagg-Div-Prun, Bagg-Prun的差異性

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

集成剪枝方法一般以獲得高泛化性能和低集成規(guī)模為目標(biāo)，傳統(tǒng)的集成剪枝根據(jù)某種數(shù)學(xué)變換將泛化性能和集成規(guī)模轉(zhuǎn)化為一個(gè)待優(yōu)化目標(biāo)。該方法雖然可以改善集成學(xué)習(xí)的泛化性能，但是與集成剪枝的初衷有所偏離。目前，研究者們根據(jù)經(jīng)濟(jì)學(xué)原理中的Pareto思想提出了采用雙目標(biāo)優(yōu)化的方法解決分類器的子集篩選問(wèn)題。該方法更加直觀地解決原始問(wèn)題，而不是將原問(wèn)題轉(zhuǎn)化。本文提出的融入差異性的集成剪枝方法是基于Pareto集成剪枝的思想，并在原雙目標(biāo)的基礎(chǔ)上增加了一個(gè)目標(biāo)即分類器間的差異性。多個(gè)角度剪枝，不僅考慮了分類器的分類準(zhǔn)確率、集成規(guī)模，還考慮了分類器之間的差異性對(duì)集成系統(tǒng)的影響。該過(guò)程的優(yōu)勢(shì)展現(xiàn)在：(1)融入差異性的Pareto集成剪枝策略確實(shí)比沒(méi)有融入差異性的Pareto集成剪枝策略更優(yōu)；(2)融入差異性的剪枝策略在泛化性能上的優(yōu)勢(shì)來(lái)自于差異性，具有相當(dāng)規(guī)模的集成分類器個(gè)數(shù)時(shí)，融入差異性的剪枝策略比沒(méi)有融入差異性的剪枝策略的泛化性能高。此外，將該融入差異性的集成剪枝策略應(yīng)用于更多的分類器以及多標(biāo)簽問(wèn)題中是一個(gè)值得研究的方向。

參考文獻(xiàn):

[1] Dietterich T G. Machine learning research[J].AI Magazine, 1997, 18(4): 97.

[2] Dietterich T G. Ensemble methods in machine learning[C]∥Multiple Classifier Systems. Springer Berlin Heidelberg:[s.n.], 2000: 1-15.

[3] Yu Shixin. Feature selection and classifier ensembles: A study on hyperspectral remote sensing data[D]. Antwerpen, Belgi?:Universiteit Antwerpen, 2003.

[4] Wolpert D H. Stacked generalization, neural networks[M]. Oxford, UK: Pergamon Press, 1992: 241-259.

[5] Ricardo V, Youssef D.A perspective view and survey of meta-learning[J]. Artificial Intelligence Review, 2002, 18(2):77-95.

[6] Zhou Zhihua, Wu Jianxin, Tang Wei, et al. Ensembling neural networks: Many could be better than all[J].Artif Intell, 2002,(137):239-263.

[7] Tsoumakas G, Partalas I, Vlahavas I. An ensemble pruning primer[C]//Applications of Supervised and Unsupervised Ensemble Methods. Berlin, Heidelberg:Springer,2009: 1-13.

[8] 張春霞,張講社. 選擇性集成學(xué)習(xí)算法綜述[J]. 計(jì)算機(jī)學(xué)報(bào), 2011, 34(8): 1399-1410.

Zhang Chunxia, Zhang Jiangshe. A survey of selective ensemble learning algorithms[J]. Chinese Journal of Computers, 2011, 34(8): 1399-1410.

[9] Li Kai,Huang Houkuan,Ye Xiuchen, et al. A selective approach to neural network ensemble based on clustering technology//Procof the International Conference on Machine Learning and Cybernetics.Banff,Canada:[s.n.], 2004: 3229-3233.

[10] Zhou Z H, Tang W. Selective ensemble of decision trees[C]//Rough Sets, Fuzzy Sets, Data Mining, and Granular Computing. Berlin, Heidelberg:Springer, 2003: 476-483.

[11] Kim M J, Kang D K. Classifiers selection in ensembles using genetic algorithms for bankruptcy prediction[J]. Expert Systems with Applications, 2012, 39(10): 9308-9314.

[12] Zhang Y,Burer S, Street W N. Ensemble pruning via semi-definite programming[J]. The Journal of Machine Learning Research, 2006, 7: 1315-1338.

[13] Partalas I, Tsoumakas G, Vlahavas I. A study on greedy algorithms for ensemble pruning[R]. Technical Report TR-LPIS-360-12, Department of Informatics. Aristotle University of Thessaloniki, Greece, 2012.

[14] Tsoumakas G, Angelis L, Vlahavas I. Selective fusion of heterogeneous classifiers[J]. Intelligent Data Analysis, 2005, 9(6): 511-525.

[15] Partalas I, Tsoumakas G, Vlahavas I. Pruning an ensemble of classifiers via reinforcement learning[J]. Neurocomputing, 2009, 72(7): 1900-1909.

[16] Castro Pablo A, Dalbem d, et al. Designing ensembles of fuzzy classification systems: An immune-inspired approach[C]∥Proceedings of the 4th International Conference on Artificial Immune System. Berlin, Heidelberg:Springer,2005:469-482.

[17] Qian C, Yu Y, Zhou Z H. Pareto ensemble pruning[C]//Proceedings of the 29th AAAI Conference on Artificial Intelligence. Austin, Texas, Palo Alto,USA:AAAI Press,2015:2935-2941.

[18] Kuncheva, L I, Christopher J W. Measures of diversity in classifier ensembles and their relationship with the ensemble accuracy[J].Machine Learning,2003, 51: 181-207.

[19] Breiman L. Bagging predictors[J]. Machine Learning, 1996, 24(2): 123-140.

[20] Friedman J, Hastie T,Tibshirani R. Additive logistic regression: A statistical view of boosting (with discussion and a rejoinder by the authors)[J]. The Annals of Statistics, 2000, 28(2): 337-407.

[21] Zhang Y,Burer S, Street W N. Ensemble pruning via semi-definite programming[J]. The Journal of Machine Learning Research, 2006, 7: 1315-1338.

[22] Ali K M,Pazzani M J. On the link between error correlation and error reduction in decision tree ensembles[M]. Irvine: University of California, 1995.

[23] Yin X C, Huang K, Yang C, et al. Convex ensemble learning withsparsity and diversity[J]. Information Fusion, 2014, 20: 49-59.

[24] Kuncheva L I, Christopher J W. Measures of diversity in classifier ensembles and their relationship with the ensemble accuracy[J].Machine Learning, 2003,51: 181-207.

[25] Liao Y,Vemuri V R. Use of k-nearest neighbor classifier for intrusion detection[J]. Computers & Security, 2002, 21(5): 439-448.

[26] Friedl M A, Brodley C E. Decision tree classification of land cover from remotely sensed data[J]. Remote Sensing of Environment, 1997, 61(3): 399-409.