基于局部有效性的選擇性決策樹集成

邵明月+胡霽芳

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

關鍵詞 機器學習 集成學習 選擇性集成 決策樹 惰性學習

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

0引言

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

1集成學習

1.1集成學習

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

1.2選擇性集成

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

2 Lovsen 算法

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

下面，假設在每一個區域Di上，都取得了對于這個區域最優的集成 optD1，則這時的泛化誤差為：

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

3總結

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

參考文獻

[1] 陸建江.加權關聯規則挖掘算法的研究[J]. 計算機研究與發展，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] 馮玉才，馮劍琳.關聯規則的增量式更新算法[J].軟件學報，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] 羅可，吳杰.關聯規則衡量標準的研究[J]. 控制與決策，2003（08）：419-424.endprint