决策树学习的目的是为了产生一棵泛化能力强，即处理未见示例能力强的决策树。

决策树学习的关键在于如何选择最优划分属性。

我们希望决策树的分支结点所包含的样本尽可能属于同一类别，即结点的“纯度”(purity)越来越高。

经典的属性划分方法

• 信息增益
• 增益率
• 基尼指数

信息增益

• “信息熵”是度量样本集合纯度最常用的一种指标。
  <div align=center></div>

属性a对样本集D进行划分所获得的“信息增益”：

<div align=center><img src="https://i.loli.net/2019/02/14/5c64eaec83d92.png"/></div>

一般而言，信息增益越大，则意味着使用a属性来进行划分所获得的“纯度提升”越大

注：信息增益对可取值数目较多的属性有所偏好

增益率

<div align=center></div>

增益率准则对可取值数目较少的属性有所偏好。

C4.5使用了一个启发式：先从候选划分属性中找出信息增益高于平均水平的属性，再从中选取增益率最高的。

基尼指数

<div align=center></div>

研究表明：划分选择的各自准则虽然对决策树的尺寸有较大影响，但对泛化性能的影响很有限。

对于数据噪声较多的，剪枝方法和程度对决策树泛化性能的影响更为显著。

剪枝处理

• “剪枝”是决策树学习算法对付“过拟合”的主要手段。
• 可通过“剪枝”来一定程度避免因决策分支过多，以致于把训练集自身的一些特点当做所有数据都具有的一般性质而导致的过拟合。

剪枝的基本策略

• 预剪枝：提前终止某些分支的生长
• 后剪枝：生成一棵完全树，再“回头”剪枝

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

• 留出法：预留一部分数据用作“验证集”以进行性能评估。