[数据结构与算法]机器学习（四）决策树回顾总结

一、决策树

一般的，一颗决策树包含一个根节点、若干个内部节点和若干个叶节点；叶结点对应于决策结果，其他结点则对应于一个属性测试；
每个结点包含的样本集合根据属性测试的结果被划分到子节点中；根节点包含了样本全集； 
（根节点就是开始，内部节点代表了不同的属性，叶节点代表决策结果。）

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

二、划分选择

决策树学习的关键在于：如何选择最优的划分属性，也就是说这么多属性，怎么去分配节点位置，随着划分过程的不断进行，我们希望决策树的
分支节点所包含的样本尽可能属于同一类别。也就是说 “越纯” 越好，这样大家都是一条船上的蚂蚱。

三、信息增益 — ID3 决策树

增益增益准则对可取数目较多的属性有所偏好。 ID3决策树学习算法 就是以信息增益为准则来选择划分属性。

信息熵

信息熵 （information entropy）是度量样本集合纯度最常用的一种指标；熵越小，纯度越高。信息量越少

$$Ent(D)=?\sum _{K=1}^{|y|}{P}_k{\log }_2{P}_k，$$

其中，$P_k$ 代表样本集 $D$ 中第 $k$ 类样本所占的比例，$k=1,2,3,.....|y|$，$Ent(D)$ 代表样本集合 $D$ 的信息熵。

我们都知道样本越多的分支节点对于决策树的影响越大，所以我们可以计算出用属性 a 对样本集 D 进行划分所获得的 信息增益

西瓜书中的例子，看完计算过程也就知道该怎么去选择节点。

因为属性“纹理”的信息增益最大，所以选他作为化分属性。

四、增益率 — C4.5 决策树

增益率准则对可取数目较少的属性有所偏好。C4.5 决策树算法不直接使用信息增益，而是使用“增益率”来选择最优划分属性。

五、基尼指数 — CART 决策树

基尼指数越小，代表越纯。 CART决策树 使用“基尼指数”来选择划分属性。

六、剪枝处理

剪枝是决策树学习算法应对 “过拟合”的主要手段。

（1）预剪枝

预剪枝：在决策树生成过程中，对每个结点划分前先进性评估，若当前结点不能带来决策树的泛化应能提升，则停止划分当前节点
并标记为叶节点（直接给结果）。

预剪枝的优缺点

优点：预剪枝因为使得决策树的很多分支没有“展开”，这不仅降低了过拟合的风险，还显著减小了决策树训练时间开销和测试时间开销。

缺点：但是，有些分支在当前划分虽然不能提升泛化性能，甚至可能导致性能下降，但在其基础上再次进行划分有可能使泛化性能显著提高。

“贪心”带来了欠拟合的风险。  

（2）后剪枝

后剪枝：先从训练集合中生成一颗完整的决策树，然后从下往上对非叶结点考察，若将该结点对应的子树替换为叶结点能够提高泛化性能，
则将该子树替换为叶结点。

后剪枝的优缺点

优点：后剪枝通常比预剪枝保留更多的分支，所以在一般情况下，后剪枝欠拟合风险很小，泛化性能优于预剪枝。

缺点：但是，后剪枝在生成决策树后进行的，自下而上对所有非叶结点逐一考察，因此训练时间开销过大。