决策树
2020-12-17 本文已影响0人
cornbig
1. 信息增益,增益率
输入:训练集 {} ;
属性集 {}
过程:函数
信息熵 是度量样本集合纯度最常用的一种指标, 假定当前样本集合D中第k类样本所占的比例为
,则的信息熵定义为
(1)
从A中选择最优划分属性 ,
ID3 决策树学习算法以信息增益为准则来划分属性。 如果把编号加入到决策树中,根据(1)计算出编号属性的信息增益为0.998, 远大于其他候选划分属性 。可以理解, ”编号“将产生17个分支,每个分支结点仅包含一个样本,这些分支结点的纯度已达到最大,然而,这样的决策树显然不具有泛化能力,无法对新样本进行有效预测。
实际上信息增益准则对可取数目比较多的属性有所偏好,为减少这种偏好带来的不利影响,C4.5决策算法不直接用信息增益,而使用“增益率”(gain ratio)来选择最优划分属性,增益率定义为:
, 其中
属性a 取值数目越多(V越大), 则IV(a)的值通常会越大, 增益率准则对可取值数目较少的属性有所偏好, 因此 C4.5 并不是直接选择增益率最大的候选划分属性,而是使用一种启发式:
先从候选划分属性中找出信息增益高于平均水平的属性,再从中选择增益率最高的。
2. 基尼指数
CART决策树 使用基尼指数来选择划分属性, 数据集的纯度可用基尼值来度量: