您确定要删除吗?

取消
首页 算法大全 应用模型 分析软件 算法学院数据中心 关于本站
在线咨询
400-820-6981
意见反馈
返回顶部

决策树学习的常见问题(三):属性选择的其他度量标准

发布时间:2017-03-29

信息增益度量在一个内在偏置,它偏袒具有较多值得属性。举一个极端的例子,考虑属性Date,它有大量的可能值(例如,March 4,1979)。要是我们把这个属性加到表3-2的数据中,它在所有属性中有最大的信息增益。这是因为单独Date就可以完全预测训练数据的目标属性。于是这个属性会被选作树的根节点的决策属性并形成一棵深度为一级但却非常宽的树,这棵树可以理想地分类训练数据,但它不是一个好的预测器(predictor)。

属性Date出了什么问题呢?简单地讲,是因为太多的可能值必然把训练样例分割成非常差的目标函数预测器。

避免这个不足的一种方法是用其他度量而不是信息增益来选择决策属性。一个可以选择的度量标准是增益比率(gain ratio)(Quinlan 1986)。增益比率通过加入一个被称作分裂信息(split information)的项来惩罚蕾西Date的属性,分裂信息用来衡量属性分裂数据的广度和均匀性:

其中,到是c个值的属性A分割S而形成的c个样例子集。注意分裂信息实际上就是S关于属性A的各值的熵。这与我们前面对熵的使用不同,在那里我们只考虑S关于学习到的树要预测的目标属性值的熵。

增益比率度量是用前面的增益度量和这里的分裂信息度量来共同定义的,即:

请注意,分裂信息项阻碍选择值为均匀分布的属性。例如,考虑一个含有n个样例的集合被属性A彻底分割。这时分裂信息的值为log2 n。相反,一个布尔属性B分割同样的n个实例,如果恰好平分两半,那么分裂信息是1。如果属性A和B产生同样的信息增益,那么根据增益比率度量,显然B得分更高。

使用增益比率代替增益来选择属性产生的一个实际问题是,当某个Si使|Si||S|时,分母可能为0或非常小。如果某个属性对于S的所有样例有几乎相同的值,这时要么导致增益比率未定义,要么是增益比率非常大。为了避免选择这种属性,我们可以采用这样一些启发式规则,比如先计算每个属性的增益,然后进队那些增益高过平均值的属性应用增益比率测试(Quinlan 1986)。

除了信息增益,Lopez de Mantaras(1991)介绍了另一种直接针对上述问题而设计的基于距离的(distance-based)度量。这个度量标准定义了数据划分间的一种距离尺度。每个属性的评估根据它产生的划分与理想划分(也就是完美分类训练数据的划分)间的距离。然后选择划分最接近完美划分的属性。Lopez de Mantaras(1991)定义了这个距离度量,郑密昂了他不偏向有大量值的属性,并报告了其实验研究,说明这种方法产生的决策树的预测精度与增益法和增益比率法得到的结果没有明显的差别。而且这种距离度量避免了增益比率度量的实际困难。在他的试验中,对于属性值个数茶艺非常大的数据集,这种方法产生了效果很好的较小的树。

此外,学者们还提出了许多种属性选择亮度(例如,Breiman et al. 1984,Mingers 1989a,Kearns & Mansour 1996,Dietterich et al.1996)。Mingers(1989a)提供了实验分析,比较了针对不同问题的集中选择亮度的有效度。他报告了使用不同属性选择度量产生的未修剪决策树的大小的显著差异。然而在他的试验中,不同的属性选择度量对最终精度的影响小于后修剪的成都和方法对最终精度的影响。