邵明月+胡霽芳

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

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

中圖分類號：TP181 文獻標識碼：A

0引言

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

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

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

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

1.2選擇性集成

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

2 Lovsen 算法

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

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

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

3總結(jié)

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

參考文獻

[1] 陸建江.加權(quán)關(guān)聯(lián)規(guī)則挖掘算法的研究[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é)報，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ī)則衡量標準的研究[J]. 控制與決策，2003（08）：419-424.endprint