[数据结构与算法]西瓜书 第四章 决策树笔记

第四章 决策树

信息熵
首先引入信息熵information entropy的概念，来度量样本数据的纯度。数据越杂乱，则信息熵越高。

信息增益
接着引入信息增益的概念，与选择的属性a相关，即用属性a来进行原始数据的划分，如果可大幅降低了数据的杂乱程度，则信息增益大，选择属性a进行区分是很不错的选择。

增益率
防止由于属性a的取值数目过多而造成的计算出信息增益极大，影响属性的选择，将信息增益/属性a的一个固有值：depends on 属性a的取值数目，但需注意增益率会对取值数目少的属性有所偏好，因此C4.5算法采取启发式：先从划分属性中寻找信息增益高于平均的属性，再从中选择增益率最高的。

基尼指数
基尼值衡量数据集的纯度（纯度 按照y的取值来判断）
属性a的基尼指数，由属性a各个取值所占比例的各部分基尼值求和得到。我们选择那个使得划分后基尼指数最小的属性作为最优划分属性。

剪枝：对付过拟合
是否能带来决策树泛化性能的提升，用验证集来判断
预剪枝 和 后件枝

连续值：
决策树也可以适用连续属性：采用二分法

缺失值的处理：

多变量决策树：