基于局部有效性的選擇性決策樹(shù)集成

邵明月+胡霽芳

摘 要 集成學(xué)習(xí)通過(guò)為同一個(gè)問(wèn)題訓(xùn)練出多個(gè)個(gè)體學(xué)習(xí)器并將結(jié)論進(jìn)行合成，可以顯著地提高學(xué)習(xí)系統(tǒng)的泛化能力。本文對(duì)此進(jìn)行了研究，并通過(guò)在局部樣本空間上選擇學(xué)習(xí)器，提出了一種基于局部有效性的選擇性集成算法Lovsen。該算法使用 k 近鄰來(lái)確定個(gè)體學(xué)習(xí)器在局部樣本空間的有效性，從而為待預(yù)測(cè)的樣本選擇合適的個(gè)體學(xué)習(xí)器進(jìn)行集成。實(shí)驗(yàn)結(jié)果表明，Lovsen可以較為穩(wěn)定地生成泛化能力較強(qiáng)的決策樹(shù)集成。

關(guān)鍵詞 機(jī)器學(xué)習(xí) 集成學(xué)習(xí) 選擇性集成 決策樹(shù) 惰性學(xué)習(xí)

中圖分類號(hào)：TP181 文獻(xiàn)標(biāo)識(shí)碼：A

0引言

機(jī)器學(xué)習(xí)（Machine Learning）是對(duì)計(jì)算機(jī)如何通過(guò)經(jīng)驗(yàn)的積累，從而自動(dòng)提高系統(tǒng)性能的機(jī)制的研究。集成學(xué)習(xí)是為同一個(gè)問(wèn)題訓(xùn)練一組學(xué)習(xí)器，并將這些學(xué)習(xí)器聯(lián)合起來(lái)執(zhí)行預(yù)測(cè)任務(wù)。按照個(gè)體學(xué)習(xí)器的生成方式，目前的集成學(xué)習(xí)方法大致可以分為個(gè)體學(xué)習(xí)器可以并行訓(xùn)練的方法，以及個(gè)體學(xué)習(xí)器只能串行訓(xùn)練的方法。研究表明，集成學(xué)習(xí)是目前泛化能力最強(qiáng)的機(jī)器學(xué)習(xí)技術(shù)之一。最近的研究發(fā)現(xiàn)，從所訓(xùn)練的學(xué)習(xí)器中選擇一部分進(jìn)行集成預(yù)測(cè)，能夠得到更好的泛化能力。這種思想稱為選擇性集成（Selective Ensemble）。本文對(duì)選擇性集成進(jìn)行了研究，提出對(duì)待預(yù)測(cè)樣本所屬的局部空間進(jìn)行分析，僅利用在這個(gè)局部空間上有效的個(gè)體學(xué)習(xí)器進(jìn)行集成，從而提出了Lovsen（LOcal Validity based Selective ENsemble）算法。具體而言，在訓(xùn)練階段，產(chǎn)生一批學(xué)習(xí)器后，LOVSEN 利用 k 近鄰來(lái)估計(jì)出每個(gè)學(xué)習(xí)器最“擅長(zhǎng)”的區(qū)域，當(dāng)給出一個(gè)測(cè)試樣本時(shí)，選擇在其鄰域中的最佳學(xué)習(xí)器構(gòu)成集成。

1集成學(xué)習(xí)

1.1集成學(xué)習(xí)

集成學(xué)習(xí)的方法首先在訓(xùn)練集上訓(xùn)練出 m 個(gè)學(xué)習(xí)器，當(dāng)給出新樣本時(shí)，讓每一個(gè)學(xué)習(xí)器都進(jìn)行預(yù)測(cè)，產(chǎn)生結(jié)果。然后通過(guò)某種方法，例如相對(duì)多數(shù)投票（majority voting），產(chǎn)生集成的預(yù)測(cè)結(jié)果y。Krogh 和Vedelsby以回歸學(xué)習(xí)器的集成推導(dǎo)出重要的集成學(xué)習(xí)的泛化誤差公式，這個(gè)公式對(duì)于分類器的集成有著同樣的意義。對(duì)于n 個(gè)學(xué)習(xí)器，它們的集成的誤差E=EA，其中，E為 n 個(gè)學(xué)習(xí)器的絕對(duì)誤差的加權(quán)平均，A為 n 個(gè)學(xué)習(xí)器相對(duì)于集成的誤差的加權(quán)平均。E指示出學(xué)習(xí)器固有的誤差，A指示出這些學(xué)習(xí)器之間的差異。這個(gè)式子表明了要獲得好的集成就需要降低個(gè)體學(xué)習(xí)器的誤差并增加學(xué)習(xí)器間的差異。

1.2選擇性集成

由于降低學(xué)習(xí)器之間的相關(guān)性可以提高集成的泛化能力，因此研究者們把目光集中在如何通過(guò)加入擾動(dòng)產(chǎn)生這樣的學(xué)習(xí)器上。而 Zhou 等人則把目光放到已經(jīng)構(gòu)造出的學(xué)習(xí)器上：在構(gòu)造好一組學(xué)習(xí)器后通過(guò)篩選掉其中“壞的”學(xué)習(xí)器，從而得到高質(zhì)量的集成。

2 Lovsen 算法

集成學(xué)習(xí)器LE的泛化誤差E可以定義為：E=dxp（x）I（LE（x）yx），Gasen通過(guò)取得最佳的LE使得上式右端最小得：EGASEN=dxp（x）I（L（x）yx）又注意到和式∑與積分∫的可加性，將樣本空間D分割為n個(gè)不交疊的區(qū)域{D1，D2，…，Dn}，即D=Di。從而，可以等價(jià)地寫作：

下面，假設(shè)在每一個(gè)區(qū)域Di上，都取得了對(duì)于這個(gè)區(qū)域最優(yōu)的集成 optD1，則這時(shí)的泛化誤差為：

這說(shuō)明了在樣本空間的子區(qū)域上分別優(yōu)化集成，將取得不壞于在整個(gè)空間上進(jìn)行的優(yōu)化更強(qiáng)的泛化能力。并且粗糙地說(shuō)，劃分的子區(qū)域數(shù)量越多，泛化能力越強(qiáng)。但是，值得注意的是，定理 1 成立的前提是當(dāng)子區(qū)域增多的時(shí)候，在各子區(qū)域上取得的最優(yōu)集成的泛化能力沒(méi)有降低。

3總結(jié)

本文基于 Zhou 等人提出的選擇性集成思想，通過(guò)分析局部化與泛化能力的關(guān)系，提出了一種新的選擇性集成方法Lovsen。Lovsen在對(duì)具體樣本進(jìn)行預(yù)測(cè)時(shí)，根據(jù)該樣本的近鄰，動(dòng)態(tài)選擇合適的學(xué)習(xí)器構(gòu)成集成。以 J4.8 決策樹(shù)作為基學(xué)習(xí)器的實(shí)驗(yàn)表明，Lovsen具有較高的泛化能力和較為穩(wěn)定的性能。Lovsen算法有兩個(gè)參數(shù)需要確定。一個(gè)是近鄰數(shù) k，用于確定局部區(qū)域的范圍。在實(shí)驗(yàn)中比較了 k =3 和 k =5 兩種配置，結(jié)果表明這兩種配置對(duì)算法沒(méi)有很大的影響。但是不保證其他的 k 值對(duì)算法會(huì)有較大的影響。另一個(gè)參數(shù)是校正函數(shù) F，在實(shí)驗(yàn)中比較了兩種校正函數(shù)和不使用校正函數(shù)對(duì)算法的影響。以下幾個(gè)方面的內(nèi)容值得進(jìn)一步研究：（1）Lovsen使用了 HVDM 來(lái)度量離散值之間的距離。利用其他最近發(fā)現(xiàn)的離散屬性距離度量方法，例如 SDM以及使用樣本流形（manifold）上的距離度量，是否能夠使算法更準(zhǔn)確地尋找出近鄰樣本。 （2） 是否有其他更穩(wěn)定的校正函數(shù)，以及校正函數(shù)引入的閾值參數(shù)€%d對(duì)算法會(huì)造成什么樣的影響。（3）當(dāng)校正函數(shù)不能完全提供無(wú)噪音的訓(xùn)練樣本時(shí)，在 k 近鄰上選擇完全預(yù)測(cè)正確的個(gè)體學(xué)習(xí)器這一要求過(guò)于苛刻。是否存在其它選擇方式，例如在 k 近鄰上選擇預(yù)測(cè)“基本正確”的個(gè)體學(xué)習(xí)器。（4）是否存在其他的局部化方法，例如使用決策樹(shù)對(duì)樣本進(jìn)行劃分。

參考文獻(xiàn)

[1] 陸建江.加權(quán)關(guān)聯(lián)規(guī)則挖掘算法的研究[J]. 計(jì)算機(jī)研究與發(fā)展，2002，（10）：1281-1286.

[2] Cheung D W. Efficient mining of association rules in distributed databases[J]. IEEE Transactions on Knowledge and Data Engineering，1996，8（6）：910-921.

[3] Ganter B， Wille R. Formal Concept Analysis：Mathematical Foundations[M]. Berlin：Springer 1999. 131-139.

[4] 馮玉才，馮劍琳.關(guān)聯(lián)規(guī)則的增量式更新算法[J].軟件學(xué)報(bào)，1998，9（4）：301-306.

[5] Srkant R， AgrawalR. Mining association rules [A]. Proc of the 21th International Conference on Very Large Database[C]. Zurich， Switerland，Sept 1995.407-419.

[6] 羅可，吳杰.關(guān)聯(lián)規(guī)則衡量標(biāo)準(zhǔn)的研究[J]. 控制與決策，2003（08）：419-424.endprint