决策过程中提出的每个判定问题都是对某个属性的测试,
每个测试的结果:
1)导出结论
2)导出进一步判定的问题
决策树的关键是选择最优划分属性,即分支结点所包含的样本尽可能属于同一类别,结点纯度越来越高
信息熵(information entropy):度量样本集合纯度的常用指标 (越小纯度越高)
假定样本集合D中第k类样本所占比例为p_k,则D的信息熵定义为:
信息增益(information gain): 用属性a对样本集D进行划分 (信息增益越大,则纯度提升越大)
a有V个可能取值,即产生V个分支结点,D_v为属性取值为a_v的样本,赋概率为权重
如 ID3决策树学习算法 以信息增益为准则 选择增益大的为划分属性
如把编号作为属性,每个分支结点只包含一个样本,纯度已为最大,但这种决策树不具有泛化能力,无法对新样本进行有效预测
信息增益准则对可取值数目较多的属性有所偏好
为减少这种偏好带来的影响,用增益率来选择最优划分
IV(a)为属性a的固有值,a的可能取值数目越多,固有值通常越大
增益率对可取值数目较少的属性有所偏好
基尼指数(Gini Index): 从数据集中随机抽取两个样本,其类别标记不一致的概率,Gini越小,纯度越高
属性a的基尼指数:(选取划分后基尼指数小的 --- min)
剪枝(pruning)是对付过拟合的主要手段
-
预剪枝
- 结点在划分前,先分析是否可以提升泛化性能,若不能则停止划分,标记为叶节点
- 很多分支没有展开,降低了过拟合风险,训练和测试时间开销低
- 有些分支当前无法提高泛化性能,但基于其的后续划分可能会有泛化性能的显著提高。基于“贪心”,可能会欠拟合
-
后剪枝
- 先生成完整的决策树,然后自底向上对非叶节点进行考察,若将子树替换为叶节点能提升泛化性能,则替换
- 欠拟合风险小,泛化性能优于预剪枝
- 训练时间开销比 未剪枝 和 预剪枝 大的多
判断泛化性能是否提升:
- 用留出法,选取测试集&验证集
- 分析划分前后验证集精度
连续值:离散化技术
-
对连续属性a,考察包含n-1个元素的候选划分点:
-
选取最优的划分点:
与离散属性不同,连续属性可重复使用,可作为其后代结点的划分属性
缺失值:
- 属性值缺失,如何进行划分属性选择?
- 用 无缺失样本所占比例 为权值
-
考虑 无缺失样本中的增益
- 给定划分属性,若值缺失,如何对样本进行划分
- 调整样本权值,让同一样本以不同概率划入到不同子节点中
决策树形成的分类边界是轴平行,当在真实分类边界比较复杂时,决策树需要进行大量的属性测试,开销大。
若使用斜的边界划分,则模型将大为简化。
多变量决策树:非叶节点是对属性的线性组合进行测试