决策树算法概述

树模型

决策树：从根节点开始，一步步走到叶子节点（决策）
所有的数据最终都会落到叶子节点，既可以做分类也可以做回归

image.png

决策树对过滤策略的先后顺序有要求，第一步过滤掉绝大部分数据，效果比较强的，能进行大致的判断。接下来的步骤也能进行划分。
根节点：第一个选择点
非叶子节点与分子：中间过程
叶子节点：最终的决策结果

衡量标准：熵

熵：熵表示随机变量不确定性的度量（说白了就是物体内部的紊乱程度，比如杂货市场里什么都有，那肯定混乱呀；专卖店里只卖一个牌子，那就稳定多了）
公式：H(X) = - $\sum p_i * logp_i$ i=1,2,3,4,5....n
例子：A=[1,1,1,1,1,1,1,1,2,2] B=[1,2,3,4,5,6,7,8,9,1]
显然A集合的熵值要低，因为A里只有2个值，比较稳定。B中类别太多，熵值就会大很多
思考：在分类任务中，我们希望通过节点分支后数据类别的熵值大还是小呐？

image.png

信息增益：表示特征X使得类Y的不确定性减少的程度。（分类后的专一性，希望分类后的结果是同类在一起）

决策树

ID3：信息增益（问题：不适合解决非常稀松的特征种类，特征非常多。比如没法很好的处理ID类别的特征的数据。）
C4.5：信息增益率（解决ID3问题，考虑自身熵。比如自身的增益很大，原始数据熵=0.9，然后0.9/自身熵值，这个增益率就很小。解决了ID3的问题）
CART：使用GINI系数来当做衡量标准
GINI系数：Gini(p)= $\sum_{k=1}^Kp_k(1-p_k) = \sum_{k=1}^Kp_k^2$
（和熵的衡量标准类似，计算方式不相同。概率越小，越接近于1，效果越好）

连续值怎么办？

选取（连续值的）哪个分界点？

排序
进行”二分“多次尝试，每次都计算熵值。（实际上就是”离散化“的过程，遇到连续值会自动做这个”离散化“的动作）。最终找到在哪个位置切分，使得熵值最小，信息增益最大（率）最大。

决策树剪枝策略

为什么要剪枝：决策树过拟合风险很大，理论上可以完全分得开数据。（想象一下，如果树足够大，每个叶子节点就只有一个数据了，就完全分开了）
剪枝策略：预剪枝、后剪枝

预剪枝：边建立决策树边进行剪枝操作（更实用）
后剪枝：当建立完决策树后，来进行剪枝操作

预剪枝

限制深度，叶子节点个数，叶子节点样本数，信息增益量等。

后剪枝

通过一定的衡量标准 $C_{\alpha}(T) = C(T)+\alpha.|T_{leaf}|$
$C_{\alpha}(T)$ 代表最后的损失 ; C(T)代表当前节点本身的gini系数或熵值。 $\alpha$ 自己设置的平衡项。 $T_{leaf}$ 叶子节点的数目
即叶子节点越多，损失越多。 $\alpha$ 越大，越容易过拟合。