基于局部有效性的选择性决策树集成

邵明月+胡霁芳

摘 要 集成学习通过为同一个问题训练出多个个体学习器并将结论进行合成，可以显著地提高学习系统的泛化能力。本文对此进行了研究，并通过在局部样本空间上选择学习器，提出了一种基于局部有效性的选择性集成算法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