决策过程中提出的每个判定问题都是对某个属性的测试，
每个测试的结果：
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个元素的候选划分点：
-
选取最优的划分点：
与离散属性不同，连续属性可重复使用，可作为其后代结点的划分属性
缺失值：
- 属性值缺失，如何进行划分属性选择?
- 用 无缺失样本所占比例 为权值
-
考虑 无缺失样本中的增益
- 给定划分属性，若值缺失，如何对样本进行划分
- 调整样本权值，让同一样本以不同概率划入到不同子节点中
决策树形成的分类边界是轴平行，当在真实分类边界比较复杂时，决策树需要进行大量的属性测试，开销大。
若使用斜的边界划分，则模型将大为简化。
多变量决策树：非叶节点是对属性的线性组合进行测试
