MachineLearning

南瓜书：https://datawhalechina.github.io/pumpkin-book/#/chapter4/chapter4

决策树

策略：分而治之

三种停止条件：

• 当前结点所含样本全属于同一类别，无需再分
• 属性集不够用或者所有样本在所有属性上取值相同，无法再分
• 当前结点包含的样本集合为空

熵：表示随机变量不确定性的度量

假定当前样本集合中第类样本所占比例为，样本类别总数为则的信息熵定义为：

的值越小，则的纯度越高

我们通过信息增益确定分类的好坏，定义为中在属性上取值的样本集合：

但是信息增益有很大的缺点：对可取值数目较多的属性有所偏好，比如将“编号”作为一个属性，因此引出增益率的概念。

如何折中属性取值与信息增益？先从候选划分属性中找出信息增益高于平均水平的，再从中选出增益率最高的。

当然除了信息增益率，也有基于其他思想的划分方法，比如基于基尼指数。但是根据研究表明，划分选择的各种准则对泛化性能的影响很有限。对泛化效果影响更显著的反而是剪枝方法和程度。

为什么？剪枝的本质是对付过拟合。

剪枝有两种策略：

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

https://www.bilibili.com/video/BV1gG411f7zX?t=353.8&p=28