第四章 决策树

决策树是一种树形结构：树中每个内部节点表示一个特征上的判断，每个分支代表一个判断结果的输出，每个叶子节点代表一种分类结果

决策树的建立过程

1. 特征选择:选取有较强分类能力的特征。
2. 决策树生成:根据选择的特征生成决策树。
3. 决策树也易过拟合，采用剪枝的方法缓解过拟合。

信息熵

熵 Entropy：信息论中代表随机变量不确定度的度量（数据的混乱程度）

• 熵越大，数据的不确定性度越高，信息就越多
• 熵越小，数据的不确定性越低

条件熵=A的占比*A的条件熵+B的占比 *B的条件熵

信息增益：特征a对训练数据集D的信息增益g(D，a)，定为集合D的熵H(D)与特征a给定条件下D的熵H(D|a)之差。

• 信息增益=（信息）熵-条件熵

ID3决策树

ID3决策树构建流程

1. 计算每个特征的信息增益
2. 使用信息增益最大的特征将数据集 拆分为子集
3. 使用该特征(信息增益最大的特征)作为决策树的一个节点
4. 使用剩余特征对子集重复上述(1，2，3)过程

不足：偏向于选择种类多的特征作为分裂依据，

C4.5决策树

信息增益率=信息增益/特征熵

• 缓解ID3树中存在的不足

信息增益率的本质

• 特征的信息增益 ÷特征的内在信息
• 相当于对信息增益进行修正，增加一个惩罚系数
• 特征取值个数较多时，惩罚系数较小;特征取值个数较少时，惩罚系数较大。
• 惩罚系数:数据集D以特征a作为随机变量的熵的倒数。

CART决策树

Cart模型是一种决策树模型，它即可以用于分类，也可以用于回归。

• Cart回归树使用平方误差最小化策略，
• Cart分类生成树采用的基尼指数最小化策略。

基尼值：从数据集D中随机抽取两个样本，其类别标记不一致的概率。（基尼值越小，表示数据集D的纯度越高）

基尼指数：选择使划分后基尼系数最小的属性作为最优化分属性。

1. 信息增益(ID3)、信息增益率值越大(C4.5)，则说明优先选择该特征。

2. 基尼指数值越小(cart)，则说明优先选择该特征。

CART回归树和 CART分类树的不同之处在于

• CART 分类树预测输出的是一个离散值，CART 回归树预测输出的是一个连续值
• CART分类树使用基尼指数作为划分、构建树的依据，CART回归树使用平方损失
• 分类树使用叶子节点多数类别作为预测类别，回归树则采用叶子节点里均值作为预测输出

决策树正则化——剪枝

决策树剪枝是一种防止决策树过拟合的一种正则化方法（提高其泛化能力）

剪枝：把子树的节点全部删掉，使用用叶子节点来替换

剪枝的方法：

1. 预剪枝:指在决策树生成过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化性能提升，则停止划分并将当前节点标记为叶节点;

2. 后剪枝:是先从训练集生成一棵完整的决策树，然后自底向上地对非叶节点进行考察，若将该节点对应的子树替换为叶节点能带来决策树泛化性能提升，则将该子树替换为叶节点。