英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料

随机森林分类器的不同分割量度分析

Vrushali Y. Kulkarni, Manisha Petare and P. K. Sinha

摘要：随机森林是一种集成的监督机器学习技术。集成原理表明, 要产生更好的精度, 集合中的基分类器应该是多样和准确的。随机森林使用决策树作为基分类器。本文对随机森林中决策树诱导归纳的不同分割量度进行了理论和实证比较, 并对其是否对随机森林的精度产生影响进行了测试。

关键词：分类；分割量度；随机森林；决策树

1 引言

随机森林是一种集成的监督机器学习技术。集成使用多个分类器, 总是比单个分类器更准确。随机森林使用决策树作为基分类器。它基于套袋法（bagging）^[1]的原理, 有两个随机过程: 一是在训练各基本决策树过程中训练数据样本的选择, 另一种是在决策树的诱导分支中属性的选择。集成原理表明, 要产生更好的精度, 在合奏中的基分类器应该是多样和准确的^[2]。

在最初的随机森林算法中, Brieman利用基尼指数作为分割量度来诱导决策树分支。基尼指数不能检测属性之间的强条件依赖性^[4]。也有各种自上而下的决策树诱导方式, 如 ID3, C4.5它们以除基尼指数之外的其他分割量度来工作^[5]。Robnik 和 Sikonja 使用五种不同的属性测度对随机森林进行实验; 森林中每五分之一的树都是使用不同的分割度量(基尼指数、增益比、MDL、模糊 ReliefF 或 ReliefF) 产生的。这有助于减少树之间的相关性, 同时保持其优势。在关于随机森林的文献调查中^[12], 我们发现在随机森林中与作属性分割量度的相关的工作较少。

有29种不同的属性分割量度^[6]，我们选择了在我们的工作中几个常用的分割量度。 在本文中，我们测试了使用不同的分割度量（信息增益，增益比，基尼指数，卡方和ReliefF）来诱导随机森林的决策树是如何影响精确度的，及一个特定的分割量度是如何改变一个决策树的效力。 为此，我们首先完成了对不同的度量的理论研究并产生一个比较模型。 在^[13]中作者已经提到，对于与决策树诱导有关的研究，实证性的比较是首选。 因此，这些结果将通过实证研究来验证并得出结论。

本文按以下顺序阐述：第2节简要介绍了本研究工作的理论基础。它们包括随机森林和用于实验的分割度量。第3节解释方法和结果。第4节做出总结。

2 理论基础

2.1 随机森林

定义: 随机森林是由树结构化分类器 {h (x、theta;k) k = 1、2,....} 集合组成的分类器, 其中 {theta;k} 是独立的相同分布的随机向量, 每个树在输入 x 上为最受欢迎的类别投下一个单元投票^[3]，随机森林生成决策树的集合。要从输入向量中对新对象进行分类, 输入向量将运行在森林中的每个树上。每棵树给出分类并做出投票。森林选择有最大选票的分类。每棵树的生长方式如下: 如果训练集中的样本数是N, 则N个样本是从原始数据中随机抽样,但有替换,这即bootstrap抽样。这个样本将是种植树的训练集。如果有 M 个输入变量, 则选择一个数字mlt;lt;M, 以便在每个节点上随机选择 m 变量, 并在这些 m 上的最佳拆分用于拆分节点。在森林生长过程中, m 的值保持恒定。每棵树都可以最大程度地生长,没有修剪。给出了随机森林的泛化误差,

=(mg(X, Y)) lt;0

边际函数给出为，

mg(X, Y) = I (hk(X) = Y) -I (hk(X) = j)

边际函数衡量出了在（X，Y）上正确分类的平均投票数在多大程度上超过为其他分类的平均投票。 随机森林的优点按照边际函数的期望值给出为，

S = (mg(X, Y))

如果rho;是基础树之间相关性的平均值, 则泛化误差的上界给出为,

le; rho;( 1 - )

因此,为了在随机森林中获得更好的精度, 基础决策树应是多种多样的、准确的。

2.2 决策树的分割度量

在决策树诱导归纳中,分割量度用于生成分裂规则。分裂规则是一个单层向前试探性的方法用于评测在树中当前节点上进行的最佳测试^[11]。

2.2.1 信息增益

该属性选择测度是基于Shannon的信息理论,它可以发现信息的价值或信息内容。因此,对于每个分割属性,计算信息增益,并选择具有最高增益的属性作为分裂属性。此属性使生成的拆分中所产生的杂质或随机性是最小的,因此它最小化了分类元组所需的信息。如果 D是整个数据集,则D的信息内容或D的熵作为

这里i = 1,2，...，m是数据集D中的类.Pi是D中任意元组属于类Ci的概率。 设A是D中的一个属性，{a1，a2，...，av}是D中属性A的不同值，使得{D1，D2，...，Dv}是基于这些值生成的分区。 这些分区可能是不纯的。 还需要多少信息才能得到准确的分类或纯分区给出为^[10]：

这个附加信息越小，分区的纯度越高。

具有最高信息增益的属性被选择用于分割。 信息增益偏向于选择具有大量值的属性。

2.2.2 增益比

增益比试图克服对多值属性的偏见。其值分布得越不平均，属性中的信息就越少^[7]。

具有最大增益比的属性被选择用于分割。

2.2.3 基尼指数

它被称为广义不等指数。 如果数据集D包含来自n种类别的例子，基尼指数定义为^[10]：

是D中类别j的相对频率。基尼指数考虑每个类别的二元分裂属性。 对于具有两个以上不同值的属性，属性的子集被考虑。 对于分区D上的二元拆分D1和D2，D的基尼指数是;

=

具有最小基尼指数的属性被选择用于分割。 最好的分割是多样性下降幅度最大的一个。基尼趋于把最大的类整合到一个纯节点中的分裂，并将所有剩余的类整合到另一个中^[9]。

Fig. 1 Graph showing comparative OOB error for ecoli dataset

2.2.4 卡方

卡方检验使用可能性矩阵来测试可用数据元组的分布以分成不同的类别。 如果（，）表示属性A取值为的事件而属性B取值为，则卡方值按如下计算^[10]：

Fig. 2 Graph showing comparative % accuracy for ecoli dataset

其中是观测频率，是预期频率，N是数据的数量元组。 给出最高的卡方值的属性被用作最佳分割。

2.2.5 ReliefF

ReliefF是一种基于属性估计的属性选择方法。ReliefF在属性之间存在强相互依赖性时是有用的^[8]。 它对每个属性分配相关权重。 这些属性根据它们彼此接近的实例的值的区别程度进行评估。

给定一个随机选择的实例R，ReliefF搜索其最近的两个邻居：一个来自同一个类，称为最接近的H，另一个来自不同的类称为最接近的M，然后根据R，M，H的所有属性值为这些属性更新其质量估计W [A]。如果实例R和H中属性A的值是不同的，则属性A分隔同一类的两个实例是不可取的，会使负面更新被添加到质量估计W[A]中。如果实例R和M处的属性A的值不同，则属性A分离具有不同类别值的两个实例是合意的，对质量估计W [A]进行正面更新。

该过程重复m次，其中m是用户定义的参数。Diff（A，I1，I2）是计算实例I1和I2属性A之间差异的函数。对于离散属性：如果Diff（A，I1，I2）= 0：value（A，I1）=value（A，I2）；否则对于连续属性：Diff（A，I1，I2）= [value（A，I1） - value（A，I2）] /（max（A） - min（A））。

3 方法和结果

执行这个实验的目的是为了观察属性分割度量的变化对随机森林分类器精度的影响。为此，我们生成了五个不同的随机森林分类器，每个使用不同的分割度量（信息增益，增益比，卡方，基尼指数和ReliefF）。对于每一项措施，随机森林以不同的尺寸生成，即从10到300棵分成10阶。所使用的数据集全部从UCI机器学习存储库中选择，并且选择是这样的，它们已经在与随机森林分类器有关的不同的实验中使用过。表2给出了用于分析的数据集的细节。精确度值和OOB误差^[3]值也记录了下来。精确度反映出来随机森林分类器的总体性能，OOB误差估计能测量森林中单个树木的强度。 这里的OOB读数记录是森林中所有树木的OOB误差值的平均值。实验是使用10倍交叉验证完成。实验在20个数据集上进行,数据集的尺寸有所不同，但由于空间的限制，我们在这里提供对于7个数据集（在表3中给出）的读数以及其中一个数据集的图。对于所有的图表，X轴上的值显示树的数量，Y轴上的值显示OOB错误或百分比精确度。

4 结论

实验结果表明, 除了卡方外,其他分割量度在精度上没有太大的变化。信息增益和增益比为几乎所有数据集提供了可比较的结果。卡方不适合随机森林分类器。与信息增益或增益比相比, ReliefF 给出的结果略好一些, 但随机森林用ReliefF 所占用的时间更多。我们目前正在研究所有分割量度的效率方面的问题, 并将会把卡方排除在实验之外。与大多数数据集一样, 基尼指数在结果中略有滞后。考虑到理论和实证的比较, 可以得出增益比和 ReliefF 是更好的选择, 考虑到时间方面, 增益比是最好的选择。展望未来工作,我们正在生成混合决策树,其中随机森林的决策树将使用不同的分割量度生成,其对随机森林的精度度产生的影响也将被观察到。

参考文献

1. Breiman, L.: Bagging predictors, Technical report No 421, September (1994).
2. Opitz, David: Maclin, richard: popular ensemble methods: an empirical study. J. Arti. Intel.11, 169–198 (1999)
3. Brieman, Leo: Random forests. Machine Learning. 45, 5–32 (2001)
4. Sikonja, M.R.: Improving random forests. In: Boulicaut, J.F., et al. (eds): Machine Learning,ECML 2004 Proceedings, LNCS, vol. 3201, PP. 359–370, Springer, Berlin (2004).
5. Rokach, Lior: Maimon, oded: top-down induction of decision trees classifiers-a survey. IEEE trans. syst. man. cyber. part c: appli. rev. 35(4), 476–487 (2005).
6. Badulescu, L.A.: The choice of the best attribute selection measure in DecisionTree induction,Annals of University of Craiova, Math. Comp. Sci. Ser. Vol. 34 (1) (2007).
7. Mingers, J.: An empirical comparison of selection measures for decision tree induction. Mach.Learn. 3, 319–342 (1989)
8. Robnik-Sikonja, M., Kononenko, I.: Attribute dependencies, understandability, and split selection in tree based models, Machine Learning: Proceedings of the 6th International Conference(ICML), 344–353 (1999).
9. Brieman, Leo: Technical note-some properties of splitting criteria. Mach. Learn. 24, 41–47(1996)
10. Han, J., Kamber, M.: Data mining: concepts and techniques, 2nd edn. Morgan Kaufmann Publisher, San Francisco (2006)
11. Buntine, Wray: Niblet, tim: a further c

    剩余内容已隐藏，支付完成后下载完整资料

    ---

    资料编号：[22672]，资料为PDF文档或Word文档，PDF文档可免费转换为Word