目录
一、预备知识
1.信息熵：
2.条件熵：
3.信息增益
4.基于信息增益选择分割特征的过程
5. C4.5算法
6.C435算法选择特征的策略
7 基尼不纯度：
二. 决策树的核心概念
1.树的结构
2.关键算法
三. 决策树的构建过程
1.特征选择
2.递归分割
3.停止条件
四. 决策树的优缺点
优点
缺点
五. 解决过拟合的方法
剪枝（Pruning）
集成方法
六. 应用场景
一、预备知识
1.信息熵：
是衡量数据集纯度的指标，熵越大，数据集的纯度越低。假设数据集S包含n个类别，第i类样本出现的概率为(pi)，则数据集S的熵(H(S))计算公式为
2.条件熵：
用于衡量在给定一个属性的条件下，数据集的不确定性。设属性A，其所有可能值为v，(Sv)是数据集S中在属性A上取值为v的子集，则给定属性A的条件下，数据集S的条件熵(H(S|A))计算公式为
3.信息增益
衡量使用属性A来分割数据集S后，得到的纯度提升，即数据集S关于属性A的信息增益
4.基于信息增益选择分割特征的过程
- 初始化：将所有训练样本集放在根节点。
- 计算信息增益：对于当前节点，计算所有候选特征的信息增益。分别计算数据集的熵\(H(S)\)和每个特征的条件熵\(H(S|A)\)，然后通过公式\(Gain(S,A)=H(S)-H(S|A)\)得出每个特征的信息增益。
- 选择最佳特征：选择信息增益最大的特征作为当前节点的分裂特征。因为信息增益越大，说明使用该特征进行划分后，数据集的纯度提升越大，对分类的贡献也就越大。
- 节点分裂：根据所选特征的每个不同取值，将当前节点划分为多个子节点，每个子节点包含该特征取值下对应的所有样本。
- 递归构建：对于每个子节点，递归地执行计算信息增益、选择最佳特征和节点分裂的步骤，直到满足停止条件，如所有样本属于同一类别、没有更多特征可供选择或最大信息增益小于预先设定的阈值等。
5. C4.5算法
- 分裂信息：C4.5 算法引入了一个分裂信息（split information）的项来惩罚取值较多的特征，计算公式为
分裂信息本质上也是熵的概念，只不过是按照特征的取值计算概率来计算熵，与样本的分类无关。特征取值越多，分裂信息的最大值越大。 - 增益率计算：增益率的计算公式为
即信息增益与分裂信息的比值。对于取值较多的特征，其分裂信息较大，会弱化信息增益大的优势，从而减少对高基数特征的偏向。