第4章 决策树
ID3决策树选择信息增益最大的属性来划分:
信息熵:
信息增益:
C4.5决策树选择增益率大的属性来划分,因为信息增益准则对可取值数目较多的属性有所偏好.但增益率会偏好于可取值数目较少的属性,因此C4.5算法先找出信息增益高于平均水平的属性,再从中选择增益率最高的.另外,C4.5决策树采用二分法对连续值进行处理,使用时将划分阈值t作为参数,选择使信息增益最大的t划分属性.采用样本权值对缺失值进行处理,含有缺失值的样本同时划入所有结点中,但相应调整权重.
增益率:
a的固有值:
CART决策树则选择基尼指数最小的属性来划分,基尼系数反映了从数据集中随机抽取的两个样本类别不一致的概率,注意CART是二叉树,其余两种都为多叉树.
基尼值衡量的纯度:
基尼指数:
剪枝是决策树对付过拟合的主要手段,分为预剪枝和后剪枝.
预剪枝对每个结点在划分前先进行估计,若该结点的划分不能带来决策树泛化性能提升,则停止划分.预剪枝基于"贪心"本质,所以有欠拟合的风险.
后剪枝是先生成一棵完整的决策树,然后自底向上对非叶结点考察,若该结点替换为叶结点能带来决策树泛化性能提升,则将子树替换为叶结点.缺点是时间开销大.
决策树所形成的分类边界是轴平行的,多变量决策树(斜决策树)的每一个非叶结点都是一个线性分类器,因此可以产生斜的划分边界.