“信息熵”是度量样本集合纯度常用的一种指标。
信息增益
一般而言,信息增益越大,则意味着使用属性a来进行划分所获得的“纯度提升”越大。因此,可用信息增益来进行决策树的划分属性选择。
增益率准则对可取数目较少的属性有所偏好,因此C4.5算法并不是直接选择增益率最大的候选划分属性,而是使用了一个启发式:先从候选划分属性中找出信息增益高于平均水平的属性,再从中选择增益率最高的。
CART决策树使用“基尼指数”来选择划分属性。数据集D的纯度可用基尼值来度量:
Gini(D)越小,数据集的纯度越高。
属性a的基尼指数定义为:
在候选属性集合A中,选择那个使得划分后基尼指数最小的属性作为最优划分属性,即:
剪枝是决策树学习算法对付过拟合的手段。
留出法:预留一部分数据用作验证集以进行性能评估。
预剪枝是指在决策树生成过程中,对每个结点在划分前先进行估计,若当前结点的划分不能带来决策树泛化性能提升,则停止划分并将当前结点标记为叶结点。
后剪枝则是先从训练集生成一棵完整的决策树,然后自底向上地对非叶结点进行考察,若该结点对应得子树替换为叶结点能带来决策树泛化性能提升,则将该子树替换为叶结点。
由于连续属性的可取数目不再有限,因此不能直接根据连续属性可取值来对结点进行划分。此时,连续属性离散化技术可派上用场。最简单的策略是采用二分法对连续属性进行处理,这正是C4.5决策树算法中采用的机制。
离散值:众数填充、相关性最高填充。
连续值:中位数填充、相关性最高的列做线性回归进行估计。