目录

1 绪论

2 模型

3 决策树面试总结

1 绪论

         决策树算法包括ID3、C4.5以及C5.0等，这些算法容易理解，适用各种数据，在解决各种问题时都有良好表现，尤其是以树模型为核心的各种集成算法，在各个行业和领域都有广泛的应用。

         决策树是一种树结构，从根节点出发，每个分支都将训练数据划分成了互不相交的子集。分支的划分可以以单个特征为依据，也可以以特征的线性组合为依据。决策树可以解决回归和分类问题，在预测过程中，一个测试数据会依据已经训练好的决策树到达某一叶子节点，该叶子节点即为回归或分类问题的预测结果。

        从概率论的角度理解，决策树是定义在特征空间和类空间上的条件概率分布。每个父节点可以看作子树的先验分布，子树则为父节点在当前特征划分下的后验分布。

        决策树中的每一条路径都对应是划分的一个条件概率分布. 每一个叶子节点都是通过多个条件之后的划分空间，在叶子节点中计算每个类的条件概率，必然会倾向于某一个类，即这个类的概率最大。

2 模型

2.1 ID3

1. 信息熵：信息熵用来度量样本集合的纯度。信息熵值越小，D 的纯度越高。

1. 信息增益：信息增益用来描述一次划分之后纯度的提升有多大。分裂节点前后不确定性提升了多少。 用不同的属性划分样本，会得到不同的信息增益。在 ID3 决策树算法中，我们取能使信息增益最大，即划分后纯度提升（不确定性降低）最大的属性作为当前决策树的划分属性。

1. 信息增益率(c4.5)：使用信息增益当作 cost function 会对可取值数目较多的属性有所偏好，使用信息增益率可以减小这种偏好。添加一个权重，一个特征取值个数越多那么折算越大。折算系数就是特征的熵。

    -- IV 是属性 a 的固有值，a 的可能取值数目越多(V 越大)，IV(a) 的值通常越大，信息增益率就会减小。显然信息增益率偏好可取值数目少的属性，不能直接使用它当作 cost function，在 C4.5 决策树算法中，先从侯选属性里找出信息增益高于平均值的属性们，再从中选取信息增益率最高的。

信息增益就是互信息。

       互信息： 描述的是两个随机变量之间相互依赖的程度。具体而言，互信息指获得一个随机变量后，观察另一个随机变量所获得的“信息量”。

https://blog.csdn.net/weixin_36480255/article/details/112640356

互信息、交叉熵、KL散度等公式 信息量、熵、最大熵、联合熵、条件熵、相对熵、互信息，信息增益_熵和信息量-CSDN博客

3 决策树面试总结

ref : https://blog.csdn.net/Heitao5200/article/details/103762474

1 . 决策树和条件概率分布的关系？

决策树可以表示成给定条件下类的条件概率分布，P（A｜B）。我们知道贝叶斯分类中采用贝叶斯定律以及条件独立假设，使用极大似然以及先验概率求得寻找能在当前输入X最大的概率y P（Y=y｜X=x）。

2. 信息增益比相对信息增益有什么好处？

• 使用信息增益时：模型偏向于选择取值较多的特征
• 使用信息增益比时：对取值多的特征加上的惩罚，对这个问题进行了校正。

3 ID3算法—>C4.5算法—> CART算法

ID3:

1. ID3算法没有考虑连续特征，比如长度，密度都是连续值，无法在ID3运用。这大大限制了ID3的用途。
2. ID3算法采用信息增益大的特征优先建立决策树的节点，偏向于取值比较多的特征;
3. ID3算法对于缺失值的情况没有做考虑;
4. ID3算法没有考虑过拟合的问题;

C4.5:

1. 连续的特征离散化
2. 使用信息增益比
3. 通过剪枝算法解决过拟合；

C4.5算法常选择后剪枝的方法消除决策树的过度拟合

C4.5的不足：

1. C4.5生成的是多叉树
2. C4.5只能用于分类，如果能将决策树用于回归的话可以扩大它的使用范围。
3. C4.5由于使用了熵模型，里面有大量的耗时的对数运算,如果是连续值还有大量的排序运算

CART算法:(二叉树)

1. 可以做回归，也可以做分类，
2. 使用基尼系数来代替信息增益比
3. CART分类树离散值的处理问题，采用的思路是不停的二分离散特征。
4. CART剪枝分为预剪枝和后剪枝两种主要方式；

4 决策树怎么防止过拟合？

1. 预剪枝(提前停止)：控制深度、当前的节点数、分裂对测试集的准确度提升大小
2. 限制树的高度，可以利用交叉验证选择
3. 利用分类指标，如果下一次切分没有降低误差，则停止切分；
4. 限制树的节点个数，比如某个节点小于100个样本，停止对该节点切分
5. 后剪枝(自底而上)：生成决策树、交叉验证剪枝：子树删除，节点代替子树、测试集准确率判断决定剪枝。在决策树构建完成之后，根据加上正则项的结构风险最小化自下向上进行的剪枝操作. 剪枝的目的就是防止过拟合，是模型在测试数据上变现良好，更加鲁棒。

5 如果特征很多，决策树中最后没有用到的特征一定是无用吗？

不是无用的，从两个角度考虑：

1. 特征替代性，如果可以已经使用的特征A和特征B可以提点特征C，特征C可能就没有被使用，但是如果把特征C单独拿出来进行训练，依然有效
2. 决策树的每一条路径就是计算条件概率的条件，前面的条件如果包含了后面的条件，只是这个条件在这棵树中是无用的，如果把这个条件拿出来也是可以帮助分析数据.

6 .决策树的优缺点？

优点:

1. 简单直观，生成的决策树很直观。
2. 基本不需要预处理，不需要提前归一化，处理缺失值。
3. 使用决策树预测的代价是O(log2m)O(log2m)。 m为样本数。
4. 既可以处理离散值也可以处理连续值。很多算法只是专注于离散值或者连续值。
5. 可以处理多维度输出的分类问题。
6. 相比于神经网络之类的黑盒分类模型，决策树在逻辑上可以得到很好的解释
7. 可以交叉验证的剪枝来选择模型，从而提高泛化能力。
8. 对于异常点的容错能力好，健壮性高。

缺点:

1. 决策树算法非常容易过拟合，导致泛化能力不强。可以通过设置节点最少样本数量和限制决策树深度来改进。
2. 决策树会因为样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习之类的方法解决。
3. 寻找最优的决策树是一个NP难的问题，我们一般是通过启发式方法，容易陷入局部最优。可以通过集成学习之类的方法来改善。
4. 有些比较复杂的关系，决策树很难学习，比如异或。这个就没有办法了，一般这种关系可以换神经网络分类方法来解决。
5. 如果某些特征的样本比例过大，生成决策树容易偏向于这些特征。这个可以通过调节样本权重来改善。