流程

根结点 包含样本全集

结点 对应一个属性测试

子结点 包含结点中属性测试的结果

叶结点 对应决策结果

决策树需进行学习过程和预测过程

学习过程：通过对训练样本的分析来确定 划分属性(内部节点所对应的属性)

预测过程：从根结点开始，沿着划分属性构成的 判定顺序列 进行属性值判别 直到叶结点

可用于回归任务（只用得出预测值）的决策树算法

三种停止条件

1、样本为同一类别，没有需要划分的属性了

2、有属性但是全部样本属性值一样无需划分

3、没有样本

学习过程

对划分属性(结点)的选择

信息增益

Y是类别

K类是指结果类别

P是每类别的占比

信息熵是所有 plog2p的总和

信息增益是 划分前的信息熵 - 划分后的信息熵（分支结点的信息熵 ：p变为每种种属性值内类别占比 plog2p 再乘该属性值集合占比的和）

信息增益最大（分支结点的信息熵最小，每种类别的概率小）的属性被选为划分属性（信息增益越大，则意味着使周属性 α 来进行划分所获得的"纯 度提升"越大）

信息增益准则对可取值数目较多的属性有所偏好，为减少这种 偏好可能带来的不利影响，著名的 C4.5 决策树算法 [Quinlan， 1993J 不直接使 用信息增益，而是使用"增益率"

属性信息熵(负数）越小的时候增益率越大  因此增益率准则对可取值数目较少的属性有所偏

C4.5 算法并不是直接选择增益率最大的候选划分属性，而是使用了一个启发式先从候选划分属性中找出信息增益高于平均水平的属性，再从 中选择增益率最高的.

基尼指数

基尼值等于 正例比率和反例比率的积

反映了从数据集 D 中随机抽取两个样本，其类别标记 不一致的概率.（方差）越小，数据集的纯度越高（类别标记越一致，大部分为一类）

某属性的基尼指数为 该属性各值的基尼值的和 基尼指数最小的属 性作为最优划分属性（该属性划分下的结果会更趋于一致）

剪枝处理 （判断是否需要该属性测试）

剪枝 是决策树学习算法对付"过拟合"(由于学习器把某种不具普遍性的特征纳入判别正例的标准而导致分类错误）的主要手段 通过主动 去掉一些分支（判断是否需要该属性测试）来降低过拟合的风险.

预剪枝

在决策树生成过程中，对每个结点（对应一个属性测试）在划 分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划 分并将当前结点标记为叶结点（决策结果）（该属性对结果的关联性不大）

后剪枝

先从训练集生成一棵完整的决策树， 然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能提升，则将该子树替换为叶结点.

判断决策树泛化性能是否提升

留出法（预留一部分数据用作"验证集"以进行性 能评估）

样本属性取值若为特殊值（连续值或者缺失值）

连续值处理

离散化技术 二分法

对所有样本中该属性的连续值排序后的每两个值的中位点作为候选划分点 对这些候选划分点计算其信息增益（以中位点的值作为分类标准) 选出信息增益最大的中位值 作为划分点

每个属性对应一个坐标轴，每个样本都对应该空间中的一个数据点，分类样本即对空间区域分块。

二分法所学习出的决策树所形成的分类边界有一个明显的特点: 轴平行(axis-parallel) ，即它的分类边界由若干个与坐标轴平行的分段组成.（某属性值是否大于某一值）

优缺点:具有好的解释性，但当学习任务复杂时需要很多段划分，开销大。

多变量决策树

使用斜的划分边界，则能简化决策树。每个结点是属性的线性组合，而不只是对某个属性。

缺失值处理

现实任务中常会遇到不完整样本，即样本的某些属性值缺失。（某些样本由于特殊原因无法得知某些属性的值） 如果放弃不完整样本进行学习则是对数据信息极大的浪费

我们需解决两个问题

(1) 如何在属性值缺失的情况 F进行划分属性选择?

选择出不缺失该属性的样本，对该样本进行该属性的信息增益的计算

用这种方法计算所有属性的信息增益并比较，选择信息增益最大的作为划分属性。

(2) 给定划分属性?若样本在该属性上的值缺失，如何对样本进行划分?

根据对应的属性值划分完所有无缺失值的样本后，将每个属性值按照（子结点）包含的样本比例放入所有子结点。

选划分点依据无缺失值样本的信息增益，其他样本按概率放入子结点。

总结

信息增益用于对属性的选择

存在连续值时先假设后选择 (先依次假设属性的划分点 计算信息增益 这些假设值中信息增益的最大值即为改属性的信息增益 并对应划分点 结点即包含属性一个划分点)

当分类任务复杂时把针对单一属性的结点替换成多个属性（变量）的线性组合（多变量决策树）

样本有缺失值时 选择属性时不加入含该属性缺失值的样本 选完后将缺失值样本按概率同时放入所有结点